Pattern Recognition: Edge-Based Segmentation

• Pattern Recognition

Segmentation

• In image processing and computer vision, segmentation divides an image into multiple regions to simplify representation and make it more meaningful and easier to analyze.
• Segmentation helps identify and isolate regions of interest (ROI) within an image, like objects and boundaries.

Edge-Based Segmentation

• It detects object edges to identify and delineate objects or regions within an image.
• Boundaries are identified by significant changes in intensity or color, indicating transitions between objects or regions.

Concept of Edge-Based Segmentation

• Edges are locations in an image where pixel intensity changes significantly because of color, brightness, or texture differences.
• Edge detection identifies these locations using operators like Sobel, Canny, and Prewitt.
• Detected edges segment the image by grouping pixels within the same boundaries (object) and separating them from others.
• This highlighting of edges separates different objects or regions.

Region-Based Segmentation

• Region-based segmentation partitions an image into regions with similar characteristics like intensity, color, or texture.
• It identifies areas that share common characteristics, making them meaningful for further analysis.
• Homogeneity is the primary concept, grouping pixels into regions sharing similar properties based on pixel intensity, color, or texture.
• Connectivity is expected, connecting neighboring pixels within a region either in a cross pattern or in a cross and diagonal pattern.

Region Growing Technique

• A simple method is region growing, wherein a seed pixel starts the region.
• The algorithm examines neighboring pixels and adds them to the region if similar properties exist.
• This continues until no more pixels can be added.

Region Growing Algorithm Explained Mathematically

• Consider an image I of size M × N, where each I(x, y) is an intensity value, seed points are chosen as starting points from region-growing process.
• A pixel p = (xp, Yp) will be added to a region if it satisfies a condition regarding the seed point or the growing region.
• The homogeneity criterion can be defined as |I(p) - I(s)| ≤ T, where I(s) is the intensity of the seed pixel, and T is a threshold.
• If the condition holds, pixel p is added to the region R, or |I(p) – µR ≤ T
• For each pixel p in R, its 4-connected or 8-connected neighbors N(p) are checked.
• If the condition is met, q is added to the region R and update the region's mean intensity, where µR = 1/|R| ∑ I(r), r∈R.
• The algorithm terminates when no more pixels can be added and the result is a segmented region R that meets the homogeneity criteria.
• In the first step the seed points initialize a region list R = S, then each neighboring pixel q ∈ N(p), is checked, if it satisfies the homogeneity criterion
• Pixel q is added to the region R if |I(q) – FR| ≤ T

Region Splitting and Merging

• This technique considers the entire image a single region at first.
• The algorithm recursively splits the image into smaller regions with a homogeneity criterion.
• If adjacent regions satisfy a merging criterion, they are merged back.
• This splitting-merging process repeats until no more changes occur.

Region Splitting and Merging Explained Mathematically

• The entire image is initially treated as a single region R0, which is then split into smaller regions and merges adjacent regions that satisfy the homogeneity criterion.
• Splitting occurs if σi > T and merging requires σij ≤ T, where T is a predefined threshold against which the region is deemed homogenous.

Region Splitting

• Quadtree Decomposition is a common method, recursively splitting each region into four equal quadrants till it satisfies the homogeneity criterion.
• Starting with the entire image R0, the region is split into four quadrants R1, R2, R3, R4 and Mathematically can be represented as: Split R¡ into {Ri1, Ri2, Ri3, Ri4} if σi > T.

Region Merging

• After the splitting process, adjacent regions are merged if they satisfy the combining homogeneity criterion.
• μij = (|Ri|· με + |Rj|·μj)/(|Ri|+|Rj|) is the mean intensity of the merged region.

Image Metrics

• I(x, y) represents the intensity value at point (x, y)
• M, N: image dimensions
• R0: the total area of the image in its initial state
• Ri: sub region of the image
• μ: average intensity of the region Rᵢ
• σ: standard deviation of the region Rᵢ values
• T: Threshold

Region Splitting Algorithm

• The entire image starts as a single region R0, which is recursively split using quadtree decomposition until all regions satisfy the homogeneity criterion or reach a minimum size.
• Adjacent regions are examined and merged where the combined region meets the homogeneity criterion
• This splitting and merging is repeated until no more operations can be performed.

Region Splitting Example

• With a grayscale image with μ₀ = 100, σ₀ = 30, and T=20, the initial region splits because it does not satisfy the homogeneity criterion.
• Each quadrant will be cheked for homogeneity before any further splits are performed.

Thresholding

• It is an early step in segmentation, mathematically represented as g(x, y) = 1 if f(x, y) > T, otherwise g(x, y) = 0 if f(x, y) ≤T,
• It is important to take care when determining the thresholds, or the results can be wrong.

Basic Global Thresholding

• Relies on the histogram of an image.
• The image histogram is partitioned using a single global threshold, making its success dependent on histogram partition quality.
• If distinct peaks exist works well, but unclear intensity gradients may cause the technique to fail.

Basic Global Thresholding Algorithm

• Select an initial estimate for T, which is typically the average grey level in the image.
• The image is segmented using T to produce two pixel groups; G1 is for pixels with grey > T and G2 has the grey levels ≤ T.
• Compute the average grey levels of pixels in μ1 to give G1 and μ2 to give G2, where a new threshold value T = (μ₁ + μ₂)/2 This is done.
• Repeat steps 2 – 4 until the difference in T in successive iterations, T∞, is satisfied, the algorithms works very well for finding suitable histogram thresholds.

Segmentation Applications

• Segmentation is used in medical imaging, for organs, tumors, or lesions detection based on intensity or texture from MRI or CT data.
• Segmentation identifies and isolates objects by similarities in color or texture for object detection.
• Segmentation divides land cover types in satellite imagery for remote sensing.

Edge-based segmentation in image processing identifies object boundaries by detecting significant intensity or color changes. Edge detection uses operators like Sobel and Canny to find locations where pixel intensity changes. This technique segments images by grouping pixels within the same object boundaries.