Improve on the Linear-Time Component-Labeling Algorithm

Improve on the Linear-Time Component-Labeling Algorithm

Our proposed was accepted to the international conference on Information Technologies and Practices in 2019. The conference place is in the School of Information Technology of the Ming Chuan University in Taiwan (R.O.C.), and Conference Date on 15th March, 2019.

We provide the files of our study that the source code of the CCL, FastCCL execution file, and experiment files. These files are in the GitHub, and the hyperlink is https://github.com/laitaiyu/ImageProcessing__FastLCL

A new high-performance linear time algorithm is presented in this article using contour tracing technique and these contours is in binary images. The main step of this algorithm is to use a contour tracing technique to detect the external contour 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. Moreover, no relabeling is required throughout the entire process. This study improves LCL algorithm by Fu Chang et al. And our algorithm is faster and better than LCL algorithm. Experimentation with various types of images (characters, halftone pictures, photographs, newspaper, etc.) shows that our method outperforms methods that use the equivalence technique. Our algorithm not only labels components, and it is able to extract component contours and sequential orders of contour points, which can be useful for many applications, such as OCR (Optical Character Reader), object tracking in video analysis, etc. A comparison with LCL algorithm is made, to demonstrate that the proposed method is faster.

Chang et al. in 2004, they proposed the LCL algorithm is one of the labeling algorithms based on the contour. LCL algorithm 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 relabeling processing. 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.

However, when LCL algorithm encounters a half-tone picture or many isolated points, it tends to spend much time on contour tracing. This is a drawback. Firstly, we proposed an Isolated point processing to improve high performance. We establish an Isolated point processing to label Isolated point beforehand. To check the Isolated point, there is an advantage that has reduced unnecessary contour tracing. Because Isolated point never has a contour. The pixel is just one single point and it has no neighbor pixels. LCL algorithm encounters an Isolated point that is still tracing the contour. We improved the LCL’s disadvantages related to Isolated points. Secondly, we provided a new image processing flow to improve the processing of the half-tone picture and the Isolated point and there is no side effect. In order to add Isolated points processing, then we designed a new image processing flow. If we find the pixel is Isolated point, it should be included into Isolated processing. On the one hand, if the pixel is in contour, it should be included into contour tracing.

Isolated point processing: Each pixel is checked to see if it is isolated or not. If the pixel is an Isolated point; then, it is directed to label image. The original LCL algorithm did not regard Isolated pixels as Isolated; they were passed on as tracing the contour. However, if it is an Isolated point, there should not be any connecting pixels. Hence, there is no need to do tracing again in our proposed model.

Contour Tracing: This step traces for object contour. When a contour is traced, the connecting contour pixels are written into the contour image.

This paper proposed a high performance linear-time component-labeling algorithm. The algorithm labels object correctly at different resolutions with complex texture. The proposed approach has four advantages. Firstly, the isolated pixel is labelled directly. That is to achieve lower processing time. Secondly, the contour tracing provided all objects a label number and established a contour image at the same time. Thirdly, contour tracing is very efficient. Normally, it takes five steps to find the next position. However, this scanning method will use only the minimum steps for finding the contour. Fourthly, we improved the image processing flow with no side effects. This study is an open source research that hyperlink is https://github.com/laitaiyu/ImageProcessing__FastLCL .

[1] F. Chang, C-J. Chen, and C-J. Lu, "A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique," Computer Vision and Image Understanding, volume 93, number 2, pages 206-220, January 2004.