DIP_review_3 Image Segmentation

What’s image segmentation
- 将图像分割成其组成的区域Region或是Object, 主要依靠Image Intensity Value的性质
  - Edge-based segmentation: Discontinuity
  - Region-based segmentation: Similarity

1 Edge detection

Mainly use differential
- 一阶 $x[n] = x[n+1] - x[n] = -(x[n] - x[n+1])$ $x [n] = x [n + 1] - x [n] = - (x [n] - x [n + 1])$
  - 一阶一般会产生较为厚的edge
- 二阶 $x[n] = x[n] - x[n-1]$ $x [n] = x [n] - x [n - 1]$
  - 二阶在边界会产生光暗/暗光线(zero crossing 过零点)，光暗的先后决定边缘是如何过渡的，并且二阶更善于寻找细节

Overview

1.1 Point detection

Use laplacian filter to conv the original image and use thresholding process to find the target point.

1.2 Line detection

Use laplacian filter and you can find the double-line effect of the second derivative. Adding thresholding process can also help you to find the target line. Moreover, you can change the kernel to find the line in different directions as well.

1.3 Edge detection

1.3.1 Basic knowledge

What is edge?

edge

How to find?
- Rules
  - Seek the 1st derivative greater than a threshold
  - Seek the zero-crossingpoint on the 2nd derivative(Improvement: when intensity change is bigger than a thresholding, we think there exists an edge and set 1 at that pos)
- Steps
  - Smooth the image because the differential is really sensitive to noise
  - Detection of edge points
  - Edge localization

1.3.2 Edge Detector(Gradient to detect in every direction)

Sobel
Prewitt
Roberts
LoG
- 中心最高，向外扩散
- 和为0，因此不改变原信息
- $\sigma$ 调整Scale，同时决定kernel size的大小
Canny
- Goal:
  - Low error rate, 即是否是真的edge
  - Edge point需要被准确定位
  - Single edge point response(width), 一个就足够否则link易出错
- Overview:
  - Step1: smooth the image with a Gaussian Filter
  - Step2: Compute the gradient magnitude and angle images
  - Step3: Apply NMS(nonmaxima suppression 非最大值抑制)对gradient magnitude
  - Step4: Use double thresholding and connectivity analysis to detect and link edge
- Details:
  - Orientation quantize: 将360°分区编码进行量化
  - Non-maxima suppression: If $M(x,y)$ is greater than all its neighbors in the quantized edge direction, $G_N(x,y) =M(x,y)$ , otherwise $G_N(x,y) =0$ .(判断其角度是否是八邻域中，相同角度编码区的极大值；不是则抑制，是则保留)
  - Double thresholding edge linking
    - Strong edge $G_H(x,y) = G_N(x,y)>= T_2$
    - Weak edge $G_L(x,y) = T_1<=G_N(x,y)<= T_2$
    - Final map: 𝐺_𝐻(𝑥, 𝑦) and all edges in 𝐺_𝐿(𝑥, 𝑦) that are adjacent to at least one pixel of 𝐺_𝐻 (𝑥, 𝑦)

1.3.3 Edge Linking

Overview:
- Step1: Start with edge pixels and corresponding $M(x,y)$ and $\alpha(x,y)$
- Step2: For each edge pixel $(x,y)$ $(x, y)$ make a window $S_{xy}$ $S_{x y}$ around that pixel, for each $(s,t)\in S_{xy}$ $(s, t) \in S_{x y}$ , link $(x,y)$ $(x, y)$ to $(s,t)$ $(s, t)$ if
  - $\|M(x,y) - M(s,t)\|<=\tau_1$
  - $\|\alpha(x,y) - \alpha(s,t)\|<=\tau_2$
Boundary following
- We have edge point around a closed contour, we want to link/order them in a clock wise direction.
- Step1: Start with edge maps(binary) and choose the uppermost, leftmost point(左上) labelled 1 as the start point $b_0$ . $c_0$ is the left neighbor of $b_0$
- Step2: 检查 $b_0$ 的八邻域, 从 $c_0$ 开始, 顺时针向前. 最终 $b_1$ 是第一个 1 pixel, $c_1$ 是之前一个的 0 pixel
- Step3: 继续向前, 直到 $b = b_0$ 且下一个点找到的是 $b_1$ . 或直到 $b$ 的八邻域内不再有edge point
- Step4: The opened list of $b$ 就是边界
但此时要是图像旋转，chain code也将随之失效
Polygonal fitting
- Details
  - S1：在所有点中选择距离最远的两个点，并且明确阈值T(pixel distance)
  - S2：创建两个stack分别为Final, In process, 用直线连接栈顶的两个点
  - S3：计算当前这条线离(顺时针侧或逆时针侧)所有点的距离，并且选出最大的那个D_m和对应的点V_max
  - S4: 若D_m $>$ T, 则将V_max放在In process栈顶，并且重新回到S2
  - S5：否则将该点从In process移去，放在Final中
  - S6：若In process非空，继续S2
  - S7: 否则结束.最终Final中的点便是有序的多边形顶点
- 若T过小则会生成一个有更多顶点且smooth的结果
- 若T过大则会生成一个结构简单并且误差较大的结果
Hough Transform(霍夫变换)

2 Thresholding

2.1 Global thresholding (全局阈值处理)

2.1.1 Basic thresholding

当Intensity value histogram 存在明显的Valley时，此时可以直接使用二值化
- Step1: 选择一个初始阈值T, 并且将图像分割成两个Group
- Step2: 分别计算两个group的平均Intensity
- Step3: $T = (m1+m2)/2$
- Step4: 重复直至优解

2.1.2 Otsu’s method (大津二值化: Maximize the between-class variance)

Otsu

由于L有限，所以我们可以遍历搜索最优T

2.1.3 Improvement

降噪，因为噪声的存在会影响原始Intensity histogram
边缘提取，对在局部的目标进行处理

2.1.4 Multiple thresholds

Multi

2.2 Variable thresholding（可变阈值处理）

Image partitioning对图像进行划分然后分别对局部图像进行处理

2.2.1 RGB thresholding

独立通道，选择一个表现效果好的通道来进行阈值处理
组合通道， $\|I(x,y) - c \| < \tau$

3 Region detection

3.1 basic region growing(图像生长算法)

整体思路: 首先在待分割区域选取多个种子生长点(多种方法)，将与种子有相同或相似性质的邻域像素合并到生长的区域中，并作为新的种子点重复以上步骤直至没有新的像素点加入则区域生长完成。
关键问题: 初始化种子的选取和相似区域判定准则(相似性准则)的设定。
Step 1: 通过阈值处理得到binary seed image
Step 2: reduce seed connected components 直至一个点即得到种子seed
Step 3: 扩张，将邻域中有相似性质的像素合并到种子生长的新区域中，并且作为新种子继续扩张
Step 4：当不再有新的像素合并到区域中，生长结束

3.2 Region Splitting and Merging(图像分割与合并算法)

region_split

Step 1: 设置方差阈值，将pixel intensity与该区域的均值作差的平方和与阈值比较，来作为我们的分割和合并的准则(多种方法); 设置最小尺寸作为我们分割的结束条件
Step 2: 将每个区域 $R_i$ 分成不相交四份当 $V(R_i) == false$ ，直至最小尺寸终止
Step 3: 合并相邻区域 $R_j$ , $R_k$ , if $V(R_j \cup R_k) == true$ , 直至不再能够合并

3.3 K-means(本质是最小化组内方差)

Step 1: 选择簇心(多种方法)
Step 2: 计算每个点到每个簇心的距离，并且分配给最近的簇心
Step 3: 重新计算每个簇的簇心位置
Step 4：重复2,3直至所有点的分配不再改变

3.4 Super pixel(超像素，局部聚类)

Ad: K-means在图像处理中的改进，能够使图像更压缩，进而对之后的分割提供计算上的便利
Def: 图像中的区域是连续的且其中的pixel具有相似/相同的intensity/color
Method: Clustering 5D vectors $[r,g,b,x,y]$ $[r, g, b, x, y]$
- Step 1: 在图像平面的区域网格上采样N个位置作为Super-pixel的中心
  - 可以对选中点进行移动，将其移至3*3邻域中的最低梯度位置
- Step 2: 对于每个簇心 $m_i$ $m_{i}$ , 计算簇心与其邻域中所有点的距离
  - 只在邻域中搜索，区域大小取决于number of N
  - 将pixel分给 cluster i 如果他的距离比当前值更大