Segmentation: introduction and various techniques

• Similarity between pixels in the same region
• Discontinuity between pixels in different regions

\bigcup_{i=1}^n R_i = R \quad\text{and}\quad R_i \cap R_j = \varnothing \, \forall\,\, i,  j \, \text{ st. } (i \neq j)

• Segmentation by thresholding and Otsu’s method
• Region growing
• Watershed
• Clustering-based methods
• Model-based segmentation
• Edge-based methods
• Graph partitioning methods
• Multi-scale segmentation

P_1(k) = \sum_{i=0}^k p_i\quad\text{with } k = 0, \, 1, \, \dots, \, L-1\\[10pt]

P_2(k) = 1-P_1(k)

m_g = \sum_{i=0}^{L-1} i\cdot p_i

m(k) = \sum_{i=0}^k i \cdot p_i

m_1(k) = \dfrac{1}{P_1(k)} \sum_{i=1}^k i \cdot p_i\\[10pt]

m_2 = \dfrac{1}{P_2(k)} \sum_{i=k+1}^{L-1} i \cdot p_i

\sigma_G^2 = \sum_{i=0}^{L-1} (i-m_G)^2 \cdot p_1

\begin{aligned}
\sigma_B^2(k) &= P_1 \underbrace{(m_1-m_G)^2}_{\text{mean - general image}} + P_2 (m_2 - m_G)^2\\[20pt]

&=P_1 P_2(m_1-m_2)^2\\[5pt]

&= \dfrac{(m_g P_1 - m)^2}{P_1(1-P_1)} \quad \text{with } k \in [0, \, L-1]
\end{aligned}

\eta = \dfrac{\sigma_B^2(k)}{\sigma_G^2}

k^* \text{ st. } \sigma_B^2(k^2) = \max(\sigma_B^2(k))

\sigma_{\text{in}}^2 = P_1 \sigma_1^2 + P_2 \sigma_2^2\\[5pt]

\sigma_G^2 = \sigma_{\text{in}}^2 + \sigma_B^2

f_Q(x_i, \, y_i) =
\begin{cases}
1 &\text{iff } Q(x_i, \, y_1) \text{ is true}\\
0 &\text{iff } Q(x_i, \, y_1) \text{ is false}
\end{cases}

Q(x_i, \, y_i) \text{ is true} \iff |f(x_i, \, y_i)-f(x_s, \, y_s)| \leq T

\text{Absolute value/Manhattan}\\
d_a(\bar{x}_i, \, \bar{x}_j) = \sum_{k=1}^D \lvert x_{i,k}-x_{j,k}\rvert\\[15pt]

\text{Euclidean}\\
d_e(\bar{x}_i, \, \bar{x}_j) = \sqrt{\sum_{k=1}^D(x_{i,k}-x_{j,k})^2}\\[15pt]

\text{Minkowski}\\
d_m(\bar{x}_i, \, \bar{x}_j) = \left[\sum_{k=1}^D(x_{i,k}-x_{j,k})^p\right]^{1/p}

1. Divisive clustering: this clustering technique starts with a single cluster containing all data points and recursively divides it into smaller clusters. It operates in a top-down manner, iteratively splitting clusters based on dissimilarity measures until each cluster contains only one data point or a predefined stopping criterion is met.
2. Agglomerative clustering: this method initially represents each data point its own cluster, which are then iteratively merged based on similarity measures until a termination condition is met.

\min\left(\sum_{i=0}^k \sum_{x \in C_i} d({\bf x}, \, {\bf\mu_i})\right)\quad\text{where } d(\cdot)\text{ is an appropriate distance}

• We select k centroids. We can choose them according to two methods:
  1. Forgy method: we randomly select k centroids
  2. Random partition: we build the k clusters by randomly assigning all the points to some cluster and then computing the centroids
• We associate each point to the closest centroid

C_i = \{ {\bf x} : i = \argmin_j(d({\bf x}), \, \mu_j)\}\quad\text{for }j=1, \, \dots, \, k

• We compute the new centroids based on the aggregated points

\mu_j = \dfrac{1}{C_i} \sum_{x\in C_i}{\bf x}

• We repeat step 2 and 3 until the centroids do not sensibly move anymore

The k-means algorithm is often a good choice for clustering, but it has some problems. One issue is that you need to set the value of k (the number of clusters) before you start. This can be good or bad depending on what you are trying to do, but it doesn’t work well in every situation.

To make k-means better, we can use a density function with “modes” (peaks). When working with images, we deal with pixels, not density functions, so we need to connect the image to its density function somehow.

First, we can pick some sample points. Then, we can use a method called Kernel Density Estimation (KDE), also known as the Parzen window technique. KDE works by combining the sample points with a kernel function to guess the underlying probability density function.

The kernel (such as a Gaussian kernel) has a parameter called bandwidth or radius (denoted by \sigma). This parameter decides the size of the window around each sample point. The kernel function is centered on each sample, and its shape determines how nearby samples affect the estimated density at that point. This process smooths out the discrete sample points, creating a continuous density estimate over the range of values.

K({\bf x}) = c_k \cdot k\left(\left\|\dfrac{x}{r}\right\|^2\right) = c_k \cdot k \left(\dfrac{\left\|x^2\right\|^2}{r^2}\right)

f({\bf x}) = \dfrac{1}{N r^n} \sum_{i=1}^N K({\bf x}-{\bf x}_i) = \dfrac{c_k}{N r^n} \sum_{i=1}^N k\left(\dfrac{\|{\bf x}-{\bf x}_i\|^2}{r^2}\right)

\nabla f({\bf x}) = \dfrac{1}{N r^n} \sum_{i=1}^N \nabla K({\bf x}-{\bf x}_i)\quad\text{where } K({\bf x-x}_i)=c_k k\left(\dfrac{\|{\bf x}-{\bf x}_i\|^2}{r^2}\right)

\begin{aligned}
\nabla f({\bf x}) &= \dfrac{2c_k}{Nr^{n+2}} \sum_{i=1}^N [({\bf x}_i-{\bf x}) \cdot g({\bf y}_i)]\\

&=\dfrac{2c_k}{Nr^{n+2}}\left(\sum_{i=1}^N [{\bf x}_i \cdot g({\bf y}_i)]-{\bf x}\cdot\sum_{i=1}^N g({\bf y}_i)\right)\\

&=\dfrac{2c_k}{r^2 c_g}\left[\dfrac{c_g}{N r^n}\sum_{i=1}^N g({\bf y}_i)\right]\cdot\left[\dfrac{\displaystyle\sum_{i=1}^N {\bf x}_i \cdot g({\bf y}_i)}{\displaystyle\sum_{i=1}^N g({\bf y}_i)}-{\bf x}\right]
\end{aligned}

1. We compute the mean shift vector m(x)
2. We move the kernel window by m(x)
3. We stop when the gradient is close to 0

K(x) = c_k \cdot k_s\left(\dfrac{{\bf x}_s}{r_s}\right) \cdot k_r\left(\dfrac{{\bf x}_r}{r_r}\right)

L=\{\ell_1, \, \ell_2, \, \dots, \, \ell_m\}

E(f) = \sum_{p\in\Omega}\left[E_{\text{data}}(p, \, f_p)+\displaystyle\sum_{q\in A(p)}E_{\text{smooth}}(f_p, \, f_q)\right]

{\bf x}_i = [I_i, \, \mu_i, \, \sigma_i]^T\quad i \in [1, \, m]

E_{\text{data}}(p, \, \ell_i) = \|{\bf x}_i - {\bf x}_p \|_2^2 = \sum_{k=1}^n (x_{i, \, k}- x_{p, \, k})^2

E_{\text{smooth}}(\ell-h)=E_{\text{smooth}}(a) =
\begin{cases}
0&\text{if }a=0\\
c&\text{otherwise}
\end{cases}

E_{\text{smooth}}(\ell-h)=E_{\text{smooth}}(a)=b\cdot|a|

m_{p\to q}^t(\ell)

• Initialization: at the start of the algorithm, each node in the graphical model initializes its belief state. These beliefs represent the node’s current estimate of the probability distribution over its possible states. Typically, these initial beliefs can be set uniformly or based on some prior knowledge or observations. The equation for the message initialization at time 0 is

m_{p \to q}^0 = \min_{h \in L} (E_{\text{data}}(p, \, h) + E_{\text{smooth}}(h-\ell))

E_{\text{data}}(q, \, \ell) + \sum_{p \in A(a)} m_{p\to q}^0(\ell)

• Time update (message passing): the main step of the BP algorithm involves iteratively passing messages between neighboring nodes in the graphical model. These messages contain information about the probability distribution over states that each node sends to its neighboring nodes. At each iteration, a node computes outgoing messages to its neighboring nodes based on incoming messages it receives from other neighboring nodes. This message passing process continues for a predefined number of iterations or until a convergence criterion is met—even though convergence itself might not have been reached. The equations that describe these steps are the ones seen above in the more in depth explanation.
• Termination: the BP algorithm terminates when a stopping criterion is satisfied. This criterion could be a maximum number of iterations reached. The final label at each pixel location is determined as

j = \argmin_{1 \, \leq \, i \, \leq m}\left(c_i^{t_0}\right)