Graph based thinning of graphical objects
AssigneeCanon Kabushiki Kaisha
InventorRadovan V. Krtolica
Life of this patent
Estimating the term…
Abstract
Methods and apparatus for creating a skeletal representation (400A) of a pixel image (100) composed of connected components (110 and 120). The skeletal representation (400A) is obtained by dividing each connected component (110) into a line segment having plural slices, calculating a minimal bounding rectangle (MBR) of each line segment, replacing each line segment with a thin line approximately formed by centroid pixels of the slices (112S) inside the MBR, and connecting the resulting thin lines (410 and 420). One of the many benefits of using the disclosed methods and apparatus is that the resulting thin lined graph (400A), i.e., the skeletal representation, is isomorphic to the original pixel image (100).
Claims22
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.
An apparatus for producing a skeletal representation of a connected component of a pixel image, the connected component comprising at least one line segment, the apparatus comprising:
- a component depicter that receives the connected component as input, and produces a connected graph and slices representing the connected component;
- and
- a component thinner, coupled to the component depicter, that receives the slices as input and produces the skeletal representation of the connected component, the component thinner comprising:
- a thin-liner that replaces each line segment of the connected component with a thin line segment, called a thin-line, having a width of M pixels, where M is a non-negative integer;
- and
- a connector that connects every first thin-line that is not connected to any other thin-line to a second thin-line to produce the skeletal representation, the connector comprising:
- an adder that adds 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 connecting results in a thin connected graph which includes all thin-lines, and the thin connected graph is isomorphic to the connected component.
A computer-readable medium containing a computer program for producing a skeletal representation of a connected component of a pixel image, the connected component comprising at least one line segment, the program comprising:
- a depiction module that receives the connected component as input, and produces a connected graph and slices representing the connected component;
- and
- a thinner module that receives slices as input and produces the skeletal representation of the connected component, the thinner module comprising:
- a thin-liner module that replaces 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 pixels of the thin-line at least substantially overlap with centroid pixels of pixel runs constituting the line segment that corresponds to the thin-line;
- and
- a connecting module that connects every first thin-line that is not connected to any other thin-line to a second thin-line, to produce the skeletal representation, the connecting module comprising:
- an adding module that adds 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 connecting results in a thin connected graph which includes all thin-lines, and the thin connected graph is isomorphic to the connected component.
Dependencies are inferred from the claim text.