A Novel Two-Scan Connected-Component Labeling Algorithm

This chapter proposes a novel two-scan labeling algorithm. In the first scan, all conventional two-scan labeling algorithms process image lines one by one, assigning each foreground pixel a provisional label, finding and resolving label equivalences between provisional labels. In comparison, our proposed method first scans image lines every four lines, assigns provisional labels to foreground pixels among each three lines, and finds and resolves label equivalences among those provisional labels. Then, it processes the leaving lines from top to bottom one by one, and for each line, assigns provisional labels to foreground pixels on the line, and finds and resolves label equivalences among the provisional labels and those assigned to the foreground pixels on the lines immediately above and below the current line. With our method, the average number of times for checking pixels for processing a foreground pixel will decrease; thus, the efficiency of labeling can be improved. Experimental results demonstrated that our method was more efficient than conventional label-equivalence-based labeling algorithms.