[Next] [Previous] [Up] [Top]

IV. CONNECTED LABELLING USING LEGION

A. G-LEGION For Binary Images

It is easy to see that our graph formulation maps to a LEGION representation in a straightforward manner. Since all final LCS's contain at least one leading vertex and all vertices within the same LCS are reachable from a leading vertex, we can construct an image segmentation algorithm that utilizes a region growing technique to identify pixels within the same region of an image. Let a leading pixel or leader in an image correspond to a leading vertex in the corresponding graph, which also corresponds to a leading oscillator in LEGION. We use a leader as a seed from which a region is grown by traversing all possible pixel paths. Whereas each seed spawns exactly one distinct region in seeded region growing techniques, leaders in our algorithm may or may not produce a resultant region.

In Section II, we have shown results of a computer simulation of a LEGION network to segment black pixel regions in Fig. 4a. Here, we present our algorithm to segment binary images. A leader is a black pixel with a sufficient number of black pixels in the potential neighborhood of the corresponding leading oscillator (see (2)). The G-LEGION algorithm for binary images has the following steps:

1. Initialization

Set all pixel labels to 0;

Set current_label = 1;

2. Leader Indentification and Recruiting

For (each black pixel p) Do

If (unlabeled) AND (# of black pixel neighbors of p) Then

Set p's label to current_label;

Traverse all paths from p that consist of only unlabeled black pixels and

Set the pixel labels of all traversed pixels to current_label;

current_label = current_label + 1;

EndIf;

EndFor;

3. Background Collection

Set the label of all remaining unlabeled black pixels to -1;

All pixels are initially unlabeled (a label 0). For each unlabeled leader that is found in step 2, called Leader Identification, a region is grown and assigned a unique label in the Recruiting process. Step 2 requires only a single scan of the image. For a leader, the number of black pixels in its potential neighborhood is greater than the threshold . For example, if the potential neighborhood is a 4-nearest neighborhood and , then our algorithm will produce the same segmentation result as in the network simulation of Fig. 4. Note that sometimes it is more sensible to define as the proportion of black pixels in . Also note that an unlabeled leader may be recruited by another leader, and thus does not initiate recruiting by itself. Once an unlabeled leader is chosen, recruiting will label all unlabeled black pixels (including leaders by definition) that are reachable from the leader along graph paths consisting of only black pixels. A graph path consists of a sequence of pixels starting at the leader, and each successive pixel on the path is in the coupling neighborhood (see (3)) of the previous pixel in the path. After all unlabeled leaders receive labels, the remaining unlabeled pixels are collected into the background, which may be disjoint. For example, the small noise fragments shown in Fig. 4a will be collected into the background by this algorithm. It follows from our graph formulation that the order in which unlabeled pixels are chosen for labeling and the order in which pixels are traversed during recruiting do not affect the outcome of the algorithm.

[Next] [Previous] [Up] [Top]