Method and apparatus for representing an area of a raster image by a centerline

• US 7,590,268 B1
• Filed: 10/17/2005
• Issued: 09/15/2009
• Est. Priority Date: 10/17/2005
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Skirko, Peter
• Primary Examiner(s): Bali; Vikkram
• Assistant Examiner(s): ENTEZARI, MICHELLE M
• Application Number:
  US11/252,503
• Time in Patent Office: 1,429 Days
• Field of Search: 382/254
• US Class Current: 382/118
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2207/30172 Centreline of tubular or elongated structure
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes

Abstract

One embodiment of the present invention provides a system that can represent an area of a raster image by a centerline. During operation, the system receives a planar map which represents a raster image that contains a region. Note that the region corresponds to a face in the planar map whose edges correspond to the boundaries of the region. Next, the system determines a centerline for a subregion within the region which is currently represented by an outline. The system then transforms the planar map so that the subregion is represented by the centerline.

Claims

1. A method for representing an area of a raster image by a centerline, the method comprising:

using a computer to perform;

receiving a planar map which represents a raster image that contains a region, wherein a face in the planar map maps to the region in the raster image, and wherein the edges of the face map to the boundary of the region;

selecting as a subregion of the region a portion of the region whose width, as measured across the region from one boundary point to another boundary point, does not exceed a maximum-width threshold, wherein both the subregion and a portion of the region outside the subregion are currently represented by an outline comprising the edges of the face;

determining a centerline for the subregion, wherein the centerline coincides with at least a portion of a medial axis of the region;

transforming the planar map so that the subregion is represented by the centerline, and so that the portion of the region outside the subregion is represented by an outline comprising a portion of the edges of the face.

2. The method of claim 1, wherein prior to receiving the planar map, the method comprises:

receiving the raster image;

partitioning the raster image into a set of regions;

generating an initial planar map by;

creating a face for every region in the set of regions;

creating a vertex where three or more regions meet; and

creating an edge for each piece of boundary between two vertices; and

generating the planar map by merging regions in the initial planar map.

3. The method of claim 1, wherein the selecting as a subregion of the region comprises:

generating a Voronoi diagram based on the pixel locations of the outline of the region;

determining the medial axis for the region using the Voronoi diagram; and

measuring the width of the region from one boundary point to another boundary point by measuring orthogonally to the medial axis.

4. The method of claim 1, wherein transforming the planar map involves:

projecting vertices from the planar map onto the medial axis;

generating matched-pairs based on the medial axis; and

creating new faces in the planar map based on the matched-pairs.

5. The method of claim 1,

wherein the planar map is represented using a winged-edge data structure;

wherein all pixels in the region have the same color.

6. The method of claim 3, wherein the Voronoi diagram is represented using a quad-edge data structure.

7. A computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for representing an area of a raster image by a centerline, the method comprising:

receiving a planar map which represents a raster image that contains a region, wherein a face in the planar map maps to the region in the raster image, and wherein the edges of the face map to the boundary of the region;

selecting as a subregion of the region a portion of the region whose width as measured across the region from one boundary point to another boundary point does not exceed a maximum-width threshold, wherein both the subregion and a portion of the region outside the subregion are currently represented by an outline comprising the edges of the face;

determining a centerline for the subregion, wherein the centerline coincides with at least a portion of a medial axis of the region;

transforming the planar map so that the subregion is represented by the centerline, and so that the portion of the region outside the subregion is represented by an outline comprising a portion of the edges of the face.

8. The computer-readable storage device of claim 7, wherein prior to receiving the planar map, the method comprises:

receiving the raster image;

partitioning the raster image into a set of regions;

generating an initial planar map by;

creating a face for every region in the set of regions;

creating a vertex where three or more regions meet; and

creating an edge for each piece of boundary between two vertices; and

generating the planar map by merging regions in the initial planar map.

9. The computer-readable storage device of claim 7, wherein the selecting as a subregion of the region comprises:

generating a Voronoi diagram based on the pixel locations of the outline of the region;

determining the medial axis for the region using the Voronoi diagram; and

measuring the width of the region from one boundary point to another boundary point by measuring orthogonally to the medial axis.

10. The computer-readable storage device of claim 7, wherein transforming the planar map involves:

projecting vertices from the planar map onto the medial axis;

generating matched-pairs based on the medial axis; and

creating new faces in the planar map based on the matched-pairs.

11. The computer-readable storage device of claim 7,

wherein the planar map is represented using a winged-edge data structure;

wherein all pixels in the region have the same color.

12. The computer-readable storage device of claim 9, wherein the Voronoi diagram is represented using a quad-edge data structure.

13. A method for associating an emergent boundary with a subregion, the method comprising:

using a computer to perform;

receiving a raster image that contains a region;

representing an area within the region by a centerline, which creates disjoint subregions of the region and creates corresponding emergent boundaries which are distinct from the centerline;

identifying the emergent boundaries;

identifying the disjoint subregions;

associating each emergent boundary with one of the disjoint subregions;

distinguishing each emergent boundary as either an inner boundary or an outer boundary; and

pairing each inner boundary with its corresponding outer boundary.

14. The method of claim 13, wherein prior to representing an area within the region by a centerline, the method further comprises:

partitioning the raster image into a set of regions;

generating an initial planar map by;

creating a face for every region in the set of regions;

creating a vertex where three or more regions meet; and

creating an edge for each piece of boundary between two vertices; and

generating a planar map by merging regions in the initial planar map.

15. The method of claim 13, wherein representing the area within the region by the centerline involves:

generating a Voronoi diagram based on the pixel locations of the boundaries of the region;

determining a medial axis for the region using the Voronoi diagram; and

determining a centerline using the medial axis.

16. The method of claim 13, wherein identifying the disjoint subregions involves flooding the Voronoi diagram.

17. The method of claim 13,

wherein all pixels in the region have the same color.

18. The method of claim 15, wherein the Voronoi diagram is represented using a quad-edge data structure.

19. A computer-readable storage device storing instructions that when executed by a computer cause the computer to perform a method for associating an emergent boundary with a subregion, the method comprising:

receiving a raster image that contains a region;

representing an area within the region by a centerline, which creates disjoint subregions of the region and creates corresponding emergent boundaries which are distinct from the centerline;

identifying the emergent boundaries;

identifying the disjoint subregions;

associating each emergent boundary with one of the disjoint subregions;

distinguishing each emergent boundary as either an inner boundary or an outer boundary; and

pairing each inner boundary with its corresponding outer boundary.

20. The computer-readable storage device of claim 19, wherein prior to representing an area within the region by a centerline, the method further comprises:

partitioning the raster image into a set of regions;

generating an initial planar map by;

creating a face for every region in the set of regions;

creating a vertex where three or more regions meet; and

creating an edge for each piece of boundary between two vertices; and

generating a planar map by merging regions in the initial planar map.

21. The computer-readable storage device of claim 19, wherein representing the area within the region by the centerline involves:

generating a Voronoi diagram based on the pixel locations of the boundaries of the region;

determining a medial axis for the region using the Voronoi diagram; and

determining a centerline using the medial axis.

22. The computer-readable storage device of claim 19, wherein identifying the disjoint subregions involves flooding the Voronoi diagram.

23. The computer-readable storage device of claim 19,

wherein all pixels in the region have the same color.

24. The computer-readable storage device of claim 21, wherein the Voronoi diagram is represented using a quad-edge data structure.