Algorithm: 4-neighborhood and 8-neighborhood region identification.

By -

1. First pass: Search the entire image R row by row and assign a non-zero value v to each non-zero pixel R(i,j). The value v is chosen according to the labels of the pixels neighbors where the property neighboring is defined by Fig 3 (‘neighbors’ outside the image R are not considered),

• If all the neighbors are background pixels (with pixel value zero), R(i,j) is assigned a new (and as yet) unused label.

• If there is just one neighboring pixel with a non-zero label, assign this label to the pixel R(i,j).

• If there is more than one non-zero pixel among the neighbors, assign the label of any one to the labeled pixel. If the labels of any of the neighbors differ (label collision) store the label pair as being equivalent. Equivalence pairs are stored in a separate data structure- an equivalence table.

2. Second pass: All of the region-pixels were labeled during the first pass but some regions have pixels with different labels (due to label collisions). The whole image is scanned again, and pixels re-labeled using the equivalence table information (for example, with the lowest value in an equivalence class).

• Label collision is a very common occurrence -- examples of image shapes experiencing this are U-shaped objects, mirrored E (∃) objects, etc.

• The equivalence table is a list of all label pairs present in an image; all equivalent labels are replaced by a unique label in the second step.

• The algorithm is basically the same in 4-connectivity and 8-connectivity, the only difference being in the neighborhood mask shape.

• It is useful to assign the region labels incrementally to permit the regions to be counted easily in second pass. Example for partial result is in Fig 3.

• The region counting task is closely related to the region identification problem.

• Object counting can be an intermediate result of region identification. If it is only to count regions with no need to identify them, a one-pass algorithm is sufficient.

clip_image002

Fig 4: Object identification in 8-connectivity. (a), (b), (c) Algorithm steps. Equivalence table after step (b): 2-5,5-6,2-4

Algorithm: Region identification in run-length encoded data

1. First pass: Use a new label for each continuous run in the first image row that is not part of the background.

2. For the second and subsequent rows, compare positions of runs. If a run in a row does not neighbor (in the 4- or 8- sense) any run in the previous row, assign its label to the new run. If the new run neighbors more than one run

in the previous row, a label collision has occurred. Collision information is stored in an equivalence table, and the new run is labeled using the label of any one of its neighbors.

3. Second pass: Search the image row by row and re-label the image

according to the equivalence table information.

If the segmented image is represented by a quad tree data structure, the following algorithm may be applied.

Comments

Post a Comment

Popular posts from this blog

Top hat transformation

By -
Image
• The top hat transformation is used as a simple tool for segmenting objects in gray-scale images that differ in brightness from background, even when the background is of uneven gray-scale. • The top hat transform is superseded by the watershed segmentation for more complicated backgrounds. • Assume a gray-level image X and a structuring element K. The residue of opening as compared to original image X ∖ (X ∘ K) constitutes a new useful operation called a Top hat transformation. • The top hat transformation is a good tool for extracting light objects on a dark but slowly changing background. Those parts of the image that cannot fit into structuring element K are removed by opening. • Subtracting the opened image from the original provides an image where removed objects stand out. • The actual segmentation can be performed by simple thresholding (Fig 18). • If an image were a hat, the transformation would extract only the top of it, provided that the structuring element is larger...
Read more

Digital Image Processing part1

By -
Image
SEGMENTATION THRESHOLDING • Segmentation is the process of partitioning a digital image into multiple segments (sets of pixels, also known as super pixels). • The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. • Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. • More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics. • Complete segmentation - set of disjoint regions uniquely corresponding with objects in the input image. • Cooperation with higher processing levels which use specific knowledge of the problem domain is necessary. • Partial segmentation - regions do not correspond directly with image objects. • Image is divided into separate regions that are homogeneous with respect to a chosen property such as bright...
Read more

Basics of Spatial Filtering,Frequency Domain filters and Homomorphic filtering

By -
Image
Basics of Spatial Filtering some neighborhood operations work with the valuesof the image pixels in the neighborhood and the corresponding values of asubimage that has the same dimensions as the neighborhood.The subimage iscalled a f i l t e r , m ask , k ernel, template, or window , with the first three terms beingthe most prevalent terminology.The values in a filter subimage are referred toas coefficients , rather than pixels. The concept of filtering has its roots in the use of the Fourier transform for signal processing in the so-called f r equency domain . This topic is discussed in more detail in Chapter 4. In the present chapter, we are interested in filtering operations that are performed directly on the pixels of an image.We use the term spatial filtering to differentiate this type of process from the more traditional frequency domain filtering. The mechanics of spatial filtering are illustrated infig.The process consists simply of moving the filter mask from point to poi...
Read more