|
|
||||
|
| |||||||||||||||||||||||
|
Computer Vision and Image Understanding
Volume 93, Issue 2, February 2004, Pages 206-220 |
| ||||
|
|
||||
Note A linear-time component-labeling algorithm using contour tracing technique
Fu Chang
, 
, Chun-Jen Chen and Chi-Jen Lu
Institute of Information Science, Academia Sinica, 128 Academia Road, Section 2, Nankang, Taipei 115, Taiwan
Received 8 August 2003; accepted 8 September 2003. ; Available online 10 October 2003.
Abstract
A new linear-time algorithm is presented in this paper that simultaneously labels connected components (to be referred to merely as components in this paper) and their contours in binary images. The main step of this algorithm is to use a contour tracing technique to detect the external contour and possible internal contours of each component, and also to identify and label the interior area of each component. Labeling is done in a single pass over the image, while contour points are revisited more than once, but no more than a constant number of times. Moreover, no re-labeling is required throughout the entire process, as it is required by other algorithms. Experimentation on various types of images (characters, half-tone pictures, photographs, newspaper, etc.) shows that our method outperforms methods that use the equivalence technique. Our algorithm not only labels components but also extracts component contours and sequential orders of contour points, which can be useful for many applications.
Author Keywords: Component-labeling algorithm; Contour tracing; Linear-time algorithm
Article Outline
1. Introduction
Researchers often face the need to detect and classify objects in images. Technically, image objects are formed out of components that in turn are made of connected pixels. It is thus most equitable to first detect components from images. When objects have been successfully extracted from their backgrounds, they also need to be specifically identified. For the latter purpose, component contour is often a useful resource for identifying objects. There are methods that identify objects from either chain codes [5] or Fourier descriptors [12], which are derived from object contours. There are also methods that match object contours against certain stochastic models [9]. These methods demonstrate that both component and contour labeling is an effective method for detecting and identifying two-dimensional objects.
In this paper, we present a method that simultaneously labels contours and components in binary images. This method is applicable in areas in which we must detect components and also classify them by means of certain contour features. Document analysis and recognition (DAR) in particular is an area for which our method is beneficial. High-order objects, such as half-tone pictures, characters, textlines, and text regions, need to be classified in order to effectively perform DAR [1]. Components are the basic ingredients of all high-order objects. Labeling components is therefore a commonly used technique for extracting high-order objects. The objective of DAR is not simply to extract high-order objects, but to recognize individual characters found within textual areas. There are many methods that employ certain contour features for classifying characters [2, 10 and 16].
Our method labels each component using a contour tracing technique. This method is based on the principle that a component is fully determined by its contours, just as a polygon is fully determined by its vertices. This method also provides a procedure for finding all component pixels. We scan an image the same way as it would be encountered by a scanner, i.e., from top to bottom and from left to right per each line. When an external or internal contour is encountered, we use a contour-tracing procedure [6] to complete the contour and assign a label, say L, to all pixels on the contour. When the contour is traced back to its starting point, we resume scanning at that point. Later on, when the contour pixels labeled L are visited again, we assign the same label L to black pixels that lie next to them.
Our method has the following advantages. First, it requires only one pass over the image. Contour points are visited more than once due to the aforementioned contour tracing procedure, but no more than a constant number of times. Second, it does not require any re-labeling mechanism. Once a labeling index is assigned to a pixel, its value is unchanged. Third, we obtain as by-products all contours and sequential orders of contour pixels. Fourth, experimental results show that our algorithm is faster than traditional component-labeling algorithms.
Our paper is organized as follows. A review of five traditional component-labeling algorithms is given in Section 2. The details of our method are described in Section 3. Analysis and proof of our algorithm are provided in Section 4. The experimental results of our method as compared with the five algorithms from Section 2 are discussed in Section 5. A brief conclusion is given in Section 6.
2. Review of traditional component-labeling algorithms
In this section, we review five important methods for component labeling. One of them is the first proposed method, and the other four use varied strategies in attempt to improve on the first. They all attempt to re-label component pixels according to an equivalence relation induced by 8-connectivity. The first method proposed by Rosenfeld and Pfaltz [13] performs two passes over a binary image. Each point is encountered once in the first pass. At each black pixel P, a further examination of its four neighboring points (left, upper left, top, and upper right) is conducted. If none of these neighbors carries a label, P is assigned a new label. Otherwise, those labels carried by neighbors of P are said to be equivalent. In this case, the label of P is replaced by the minimal equivalent label. For this purpose, a pair of arrays is generated, one containing all current labels and the other the minimal equivalent labels of those current labels. In the second pass, label replacements are made.
Haralick [8] designed a method to remove the extra storage required for the pair of arrays proposed in the first method. Initially, each black pixel is given a unique label. The labeled image is then processed iteratively in two directions. In the first pass, conducted from the top down, each labeled point is reassigned the smallest label among its four neighboring points. The second pass is similar to the first, except that it is conducted from the bottom up. The process goes on iteratively until no more labels change. The memory storage of this method is small, but the overall processing time varies according to the complexity of the image being processed.
The method proposed by Lumia et al. [11] compromises between the two previous methods. In the first top-down pass, labels are assigned to black pixels as in the first method. At the end of each scan line, however, the labels on this line are changed to their minimal equivalent labels. The second pass begins from the bottom and works similarly as the top-down pass. It can be proved that all components obtain a unique label after these two passes.
Fiorio and Gustedt [4] employ a special version of the union-find algorithm [15] in that it runs in linear time for the component-labeling problem (see also Dillencourt et al. [3]). This method consists of two passes. In the first pass, each set of equivalent labels is represented as a tree. In the second pass, a re-labeling procedure is performed. The operation used in the union-find technique serves to merge two trees into a single tree when a node in one tree bears an 8-connectivity relationship to a node in the other tree.
The method proposed by Shima et al. [14] is particularly suitable for compressed images in which a pre-processing procedure is required to transform image elements into runs. A searching step and a propagation step are exercised iteratively on the run data. In the searching step, the image is encountered until an unlabeled run (referred to as focal run) is found and is assigned a new label. In the propagation step, the label of each focal run is propagated to contiguous runs above or below the scan line.
3. Our method
In our method, we scan a binary image from top to bottom and from left to right per each line. We first provide an overview of this method as follows. Conceptually, we can divide the operations into four major steps that are illustrated in Figs. 1A–D.
Fi ag:.eof tce_rdorig1&r>