ONE-PASS THINNING ALGORITHM AND ITS PARALLEL IMPLEMENTATION.

Abstract

A description is given of a one-pass thinning algorithm that requires only a single cycle of parallel operations per iteration, e. g. , it removes boundary pixels at all directions simultaneously, hence no intermediate storage is required. The major difference between this algorithm and the usual 3x3 operators is that it uses two restoring templates (a 1x4 and 4x1 operator) to deal with the breakage and disappearance of horizontal and vertical two-pixel-wide limbs. Connectedness of skeletons has been verified, and limitations of the algorithm are discussed. In a comparative study, skeletons generated by this algorithm have been found to be comparable with those from various other methods. From the nature of its one-pass operation, a major implication is elucidated: thinning can be realized cost effectively by combinational logic, with processing speed limited only to the propagation delays of logic gates. The realization of such a thinning device is presented. Processing speed on the order of nanoseconds has been achieved.