Hidden Deletable Pixel Detection Using Vector Analysis in Parallel Thinning to Obtain Bias-Reduced Skeletons

摘要

The improvement of producing skeletons that preserve the significant geometric features of patterns is of great importance. One of feasible approaches is to develop a method embedded in a known parallel algorithm to produce bias-reduced skeletons since a bias skeleton usually degrades the preservation of significant geometric features of patterns. From our observations, bias skeletons always appear in the junction of lines which form an angle less than or near equal to 90°. In this paper, thehidden deletable pixel(HDP) which influences the speed of deleting the boundary pixels on a concave side is newly defined. Based on the comparable performance of our pseudo 1-subcycle parallel thinning algorithm (CH), a reduced form of larger support (twoL-pixel vectors, which is not the form ofk×ksupport) operated by an intermediate vector analysis about the deleted pixels in each thinning iteration is developed for HDP detection to obtain bias-reduced skeletons, which can be purchased by a reasonable computation cost. HDP restoration and parallel implementation are further considered to formulate an improved algorithm (CYS), where the connectivity preservation is guaranteed by the use ofCH's operators and HDP restoration. A set of synthetic images are used to quantify the skeleton from the geometry viewpoint and investigate the skeleton variations of using different (L)s. Based on the analyzing results, 3 ≤L≤ 9 are suggested for the current algorithm ofCYS.CYSis evaluated in comparison with two small support algorithms (AFP3andCH) and one larger support algorithm (VRCT) using the same patterns. Performances are reported by the number of iterations (NI), CPU time (TC), and number of unmatched pixels (Nunmatchfor bias-reduced measure). Results show that on the measure ofTC,CYSis approximately 2 to 3 times slower than the others, while on the measure ofNI, the four algorithms have approximately identical performance. On the measure ofNunmatch,CYSis approximately 2 to 3 times less than the others. One-pixel boundary noise is also considered for exploring the noise immunity. The results suggest that the noise immunity ofCYSandCHis identical and is better than that ofAFP3. As a result, the better bias-reduced skeletons produced byCYSmay be purchased by a reasonable computation cost.