Methods and apparatus for reproducing a gray scale raster represented elongate graphic image including vectorizing a skeleton of the image by determining a midpoint between two detected endpoints of the image

• US 5,734,756 A
• Filed: 02/01/1995
• Issued: 03/31/1998
• Est. Priority Date: 02/01/1995
• Status: Expired due to Fees

• Current Assignee: ScanVec Co. (1990) Ltd. (Scanvec Amiable LTD)
• Original Assignee: ScanVec Co. (1990) Ltd. (Scanvec Amiable LTD)
• Inventors: Sherman, Alexander, Eintracht, Zvi
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/382,481
• Time in Patent Office: 1,154 Days
• Field of Search: 382/258, 382/259, 382/286, 382/288, 345/135, 364/474.03, 395/104
• US Class Current: 382/259
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A method for generating a vector representation of the skeletal configuration of an elongate graphic image from a raster representation thereof, the method comprising providing a gray scale raster representation of the graphic image, for at least one of a plurality of lines of the raster representation, performing the following processes at least once: employing the gray scale raster representation to determine two path endpoints and computing a midpoint between the two endpoints.

Claims

1. A method for generating a vector representation of the skeletal configuration of an elongate graphic image from a raster representation thereof, the method comprising:

providing a gray scale raster representation of the graphic image;

for at least on of a plurality of lines of the raster representation, performing the following processes at least once;

employing the gray scale raster representation to determine two path endpoints; and

computing a midpoint between the two endpoints; and

generating the vector representation using the computed midpoints for the lines of the raster representation.

2. A method according to claim 1 and also comprising generating a centerline to fit the midpoints.

3. A method according to claim 2 and also comprising performing a physical operation along the centerline.

4. A method according to claim 2 wherein said plurality of lines of the raster representation includes at least one set of at least three segments having adjacent ends, and wherein said step of generating a centerline comprises generating a centerline for each of the segments, thereby to define at least one set of at least three centerlines having adjacent ends, said method also comprising:

for each said set of at least three centerlines;

for each centerline from among said at least three centerlines, computing a tangent to that centerline at that centerline'"'"'s adjacent end; and

connecting pairs of adjacent centerline ends so as to minimize angular separation between the tangents to the connected centerlines at their respective connected ends.

5. A method according to claim 1 and also comprising performing a physical operation along a centerline of the skeletal configuration of the graphic image which fits the midpoints.

6. A method according to claim 5 wherein the physical operation comprises cutting.

7. A method according to claim 5 wherein the physical operation comprises routing.

8. A method according to claim 5 wherein the physical operation comprises engraving.

9. A method according to claim 5 wherein the physical operation comprises painting.

10. A method according to claim 5 wherein the physical operation comprises printing.

11. A method according to claim 1 wherein said gray-scale representation providing process comprises gray-scale scanning of a graphic image.

12. A method according to claim 1 wherein the processes performed at least once for at least one line are performed at least once for at least one column and at least once for at least one row.

13. A method according to claim 12 and also comprising:

selecting a plurality of skeleton pixels; and

replacing each skeleton pixel with the midpoint computed for a line in which the skeleton pixel is included.

14. A method according to claim 13 wherein said line comprises the row in which the skeleton pixel is included, if the endpoints for that row are closer together than the endpoints for the column in which the skeleton pixel is included, and

wherein said line comprises the column in which the skeleton pixel is included, if the endpoints for that column are closer together than the endpoints for the row in which the skeleton pixel is included.

15. A method according to claim 1 wherein at least one line from among said Plurality of lines comprises a row.

16. A method according to claim 1 wherein at least one line from among said plurality of lines comprises a column.

17. A method for identifying midpoints lying along the skeletal configuration of a graphic image from a raster representation thereof, the method comprising:

providing a gray scale raster representation of the graphic image;

for each of a plurality of lines of the raster representation;

determining two path endpoints using the gray scale raster representation; and

computing a midpoint between the two endpoints.

18. A method according to claim 17 wherein said gray-scale representation providing process comprises gray-scale scanning of a graphic image.

19. An apparatus for generating a vector representation of the skeletal configuration of an elongate graphic image from a raster representation thereof, the apparatus comprising:

a gray-scale scanner operative to perform gray-scale scanning of a graphic image, thereby to generate a gray scale raster representation of the graphic image;

an endpoint identifier operative to determine two path endpoints for each of a plurality of lines of the gray scale raster representation;

a midpoint computer operative to compute a midpoint between the two endpoints; and

a vector generator operative to generate the vector representation using the computed midpoints for the lines of the raster representation.

20. Apparatus according to claim 19 wherein the endpoint identifier and midpoint computer operate on each of a plurality of rows and on each of a plurality of columns and wherein the midpoints computed for lines which are generally parallel to the skeletal configuration of the graphic image are substantially disregarded.

21. Apparatus according to claim 19 and also comprising mechanical apparatus for performing a mechanical operation along the centerline of the skeletal configuration of the graphic image.

22. Apparatus according to claim 19 wherein the mechanical apparatus comprises a cutter.

23. Apparatus according to claim 19 wherein the mechanical apparatus comprises a router.

24. Apparatus according to claim 19 wherein the mechanical apparatus comprises an engraver.

25. Apparatus according to claim 19 wherein the mechanical apparatus comprises a painter.

26. Apparatus according to claim 19 wherein the mechanical apparatus comprises a printer.

27. An apparatus operative to identify midpoints lying along the skeletal configuration of a graphic image from a raster representation thereof, the apparatus comprising:

a gray-scale scanner operative to perform gray-scale scanning of a graphic image, thereby to generate a gray scale raster representation of the graphic image;

an endpoint identifier operative to determine two path endpoints using the gray scale raster representation; and

a midpoint computer operative to compute a midpoint between the two endpoints.