Method for rapidly skeletonizing graph of binary digital image

Abstract

The invention relates to a method for rapidly skeletonizing a graph of a binary digital image. The method comprises the steps of (1) scanning the image and calculating the local maximum, (2) generating a graph skeleton based on an algorithm of a distance function, and (3) deleting wrong skeleton branches, finding out skeleton endpoints of wrong graph skeleton branches generated by the step two, and deleting the wrong skeleton branches, wherein eight pixels which do not belong to the current skeleton endpoints do not have the local maximum or only have one local maximum, the difference of coordinate values between the eight pixels and the skeleton endpoints of the wrong graph skeleton branches in an image coordinate space is equal to 0 or 1, and the skeleton endpoints only have foreground pixels on one side inside a neighborhood in the binary image coordinate space. The skeleton generated by the algorithm is substantially in accordance with the skeleton generated by a main current international refinement algorithm. The algorithm is simple in structure, convenient to implement and efficient in operation. Computation complexity of the algorithm is O (n2) +O (m2) =O (n2). The algorithm is in accordance with a Davies algorithm. Computational results of the algorithm are remarkably superior to the Davies algorithm.

Description

technical field [0001] The invention belongs to an image processing method for thinning graphics in a binary digital image to obtain its skeleton, in particular to a method for quickly skeletonizing graphics in a binary digital image. Background technique [0002] Similar skeletalization methods at home and abroad are often used in Optical Character Recognition (OCR) and some image processing algorithms based on image shape, such as Hough Transformation (Hough Transformation, HT) image algorithm, so it is used to obtain the thinning algorithm of graphic skeleton It has important industrial application value and academic theoretical significance. [0003] The concept of graphic bones in binary images was first proposed by Blum in 1967. Bones refer to the collection of the centers of the largest inscribed circles that are tangent to the local boundaries of the area in the area composed of foreground pixels. See H. Blum, "A transformation for extracting new descriptors of shap...

AI Technical Summary

Problems solved by technology

Unlike modern thinning algorithms, this algorithm does not use additional, complex data structures to assist the algorithm except for the two-dimensional matrix, nor does it use a lookup table for giving the calculated value of the distance function, so the algorithm structure Simple, easy to analyze and implement, but its refinement effect attenuates with the increase of graph complexity

Images