Image Segmentation and Clustering Part 1: Segmentation - 9

Segmentation

subdivides an image to regions or objects

Methods:

• Thresholding

• Edge Detection

• Region-Based Segmentation

clustering

Algorithms like K-means and Mean Shift, used to group similar data points.

Goal of Segmentation

Separate image into coherent “objects”

Thresholding assumption

the range of intensity levels covered by
objects of interest is different from the background.

Automatic Threshold Determination
(Iterative Thresholding)

threshold value is repeatedly calculated based on

• mean values of fg and bg pixels

• unitl threshold converges or max iterations are reached

• best for bimodal hist.

Iterative Thresholding Algorithm

1. select initial threshold t (mean/midpoint between max and min gray levels)

2. segment image using t

3. compute average internsity m1 and m2 for pixels in segemented regions

4. compute new threshold

5. repeat 2-4 until diff between t is very small

Marr Hildreth Edge Detector steps

1. smooth image w gaussian filter

2. apply laplacian to smoothed image

3. find zero crossings

• 1-2 combined w LoG

Canny Edge Detector steps

1. smoothing

2. differentiation

3. non-max suppression

4. hysteresis thresholding

• 1-2 combined w DoG

Segmentation using Edge Detection example w license plate segmentation

find shapes similar to license plate

1. find edges

2. connect edge points

3. find rectangular shapes

4. check horiz-vert proportion

Region-Based Segmentation and types

combine similar pixels in the same region

1. region growing

2. region splitting and merging

Region-Growing Segmentation

• start with seed points, group regions into larger ones based on predefined criteria

• challenges: choosing good seeds, regions might leak

Region-Growing Segmentation algorithm

1. Choose the seed pixel(s)
2. Check the neighboring pixels and add them to the region if they are similar to the seed
3. Repeat step 2 for each of the newly added pixels; stop if no more pixels can be added

region growing segmentation example:

0 1 2 0

2 5 6 1

1 4 7 3

0 2 5 1

Seed Point: 7

• Homogeneity Criterion: abs(p_i−seed)≤T

  • Threshold T=2

• Connectivity: 4-connectivity (only directly up, down, left, right).

Step 1: Initialize with Seed

• The initial region includes only the seed pixel with intensity 7.

Step 2: Check Neighbors

• Examine the seed's 4-connected neighbors:

  • Above (2nd row, 3rd column): Intensity = 6, abs(6−7)=1(add to region).

  • Below (4th row, 3rd column): Intensity = 5, abs(5−7)=2(add to region).

  • Left (3rd row, 2nd column): Intensity = 4, abs(4−7)=3 (not added).

  • Right (3rd row, 4th column): Intensity = 3, abs(3−7)=4 (not added).

Step 3: Expand the Region

• Newly added pixels (6 and 5) become the next seeds. Repeat Step 2 for each:

  • For 6 (2nd row, 3rd column):

    • Neighbor 5 (2nd row, 2nd column): abs(5−6)=1(add to region).

  • For 5 (4th row, 3rd column):

    • Neighbor 2 (4th row, 2nd column): abs(2−5)=3(not added).

Step 4: Stop When No More Pixels Satisfy Criterion

• The final region includes:

  • Seed pixel: 7

  • Added pixels: 6,5 (from above, below, and left).

Tie-breaking Mechanism

If a pixel falls within the threshold of two or more regions, there must be a rule or tie breaking mechanism to decide which region the pixel should belong to

1. first come, first serve

2. smallest region preference

3. largest region preference

4. Closest Seed

How do we choose the seed(s) in practice ?

if targets need to be detected using infrared images for example, choose the brightest pixel(s).

Without a-priori knowledge, compute the histogram and choose the gray-level values corresponding to the strongest peaks

Region Growing Disadvantages

not trivial to find good seed points

Region growth may “leak” through a single weak spot in the boundary

Region Splitting and Merging algorithm

1. If region satisfies homogeneity criteria, leave it unmodified
2. If not, split it into four quadrants and recursively apply 1 and 2 to each newly generated region. STOP when all regions in the quadtree satisfy the homogeneity criterion
3. If any two adjacent regions can be merged into a homogeneous region, merge them. STOP when no merging is possible anymore.