Patent ID: 6788814
Filing Date: 2004-09-07
Classification: G06K

Abstract:
A method for obtaining a skeletal representation of a connected component of a pixel image, the connected component comprising at least one line segment, the method comprising the steps of:depicting the connected component as a connected graph, said step of depicting comprising: modeling the connected component by dividing the connected component into slices; representing each slice by one of a set of nodes; and connecting two of the nodes with an edge when two of the slices represented by the two nodes are adjacent to each other within the connected component, wherein the nodes and the edges constitute at least a part of the connected graph; and thinning the connected component, said step of thinning comprising: replacing each line segment of the connected component with a thin-line segment, having a width of M pixels, where M is a non-negative integer; and connecting every first thin-line that is not connected to any other thin-line to a second thin-line, to produce the skeletal representation, the step of connecting comprising: adding N pixels that are not part of any thin-line to connect the first thin-line to the second thin-line, where N is a natural number; wherein the step of connecting results in a thin connected graph which includes all thin-lines, and the thin connected graph is isomorphic to the connected component.