System for representing line drawings by polygonal lines

• US 5,313,529 A
• Filed: 04/16/1993
• Issued: 05/17/1994
• Est. Priority Date: 08/08/1990
• Status: Expired due to Fees

• Current Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation)
• Inventors: Itonori, Katsuhiko
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/047,075
• Time in Patent Office: 396 Days
• Field of Search: 382/21, 382/23, 382/24, 382/26, 395/143, 395/141, 358/464, 358/465
• US Class Current: 382/201
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

Abstract

A system for representing line drawings by polygonal lines. In the system, a binary digital image is scanned in a main scanning direction to form picture element connection data with a first image picture element as a start point picture element which is scanned next to a first background picture element and with a second background picture element as an end point picture element which is scanned next to a second image picture element, and the relationships between the picture element connection data are detected to provide as picture element block data a group of picture element connection data which have predetermined relationships. Further, it is determined from each picture element block data whether or not the picture element block thereof represents a straight segment, and straight line approximation data is provided according to both the uppermost picture element connection data and the lowermost picture element connection data in the picture element block when it is determined that the picture element block represents a straight segment, whereby parts of the drawing to be represented by polygonal lines are detected and processed with high efficiency.

Claims

1. A system for representing line drawings by polygonal lines comprising:

picture element connection data forming means for scanning a binary digital image in a main scanning direction to form sets of picture element connection data, each set having a start point picture element where a background picture element value of the image changes to a drawing picture element value and having an end point picture element where the drawing picture element value changes to the background picture element value, said start point picture element and said end point picture element of each set of picture element connection data lying in one scanning line in the main scanning direction;

picture element block data forming means for detecting relationships between sets of picture element connection data which are adjacent in a direction perpendicular to said main scanning direction and for forming picture element block data from sets of picture element connection data having predetermined relationships;

straight segment determining means for determining from each picture element block data whether or not the picture element block thereof represents a straight segment; and

straight line approximating means for providing straight line approximation data according to both the uppermost element connection data and the lowermost picture element connection data in said picture element block in response to a determination by said straight segment determining means that said picture element block represents a straight segment.

2. A system according to claim 1, wherein said straight segment determining means determines whether said picture element block represents a vertical or horizontal line.

3. A system according to claim 2, wherein said straight line approximating means obtains as the straight line approximation data the middle points of the uppermost picture element connection data and the lowermost picture element connection data in response to a determination by said straight segment determining means that said picture element block represents a vertical line.

4. A system according to claim 2, wherein said straight line approximating means obtains as the straight line approximation data the right and left end points in said picture element block in response to a determination by said straight segment determining means that said picture element block represents a horizontal line.

5. A system according to claim 1, further comprising image data storing means for storing said binary digital image to be scanned by said picture element connection data forming means.

6. A system according to claim 1, further comprising picture element connection data storing means for storing the picture element connection data formed by said picture element connection data forming means, and picture element block data storing means for storing the picture element block data formed by said picture element block data forming means.

7. A method for representing line drawings by polygonal lines comprising:

scanning a binary digital image in a main scanning direction to form sets of picture element connection data by detecting a start point picture element where the background picture element value of the image changes to the drawing picture element value and by detecting an end point picture element where the drawing picture element value changes to the background picture element value, said start point picture element and said end point picture element of each set of picture element connection data lying in one scanning line in the main scanning direction;

forming picture element block data by detecting relationships between sets of picture element connection data which are adjacent in a direction perpendicular to said main scanning direction and by forming picture element blocks from said sets of picture element connection data having predetermined relationships;

determining from each picture element block data whether or not the picture element block represents a straight segment; and

providing straight line approximation data according to both the uppermost picture element connection data and the lowermost picture element connection data in said picture element block in response to a determination in said determining step that said picture element block represents a straight segment.

8. A method according to claim 7, wherein said determining step includes determining whether said picture element block represents a vertical or horizontal line.

9. A method according to claim 8, wherein said providing step obtains middle points of an uppermost picture element connection data and a lowermost picture element connection data as the straight line approximation data in response to a determination in said determining step that said picture element block represents a vertical line.

10. A method according to claim 8, wherein said providing step obtains a right end point and a left end point as the straight line approximation data in response to a determination in said determining step that said picture element block represents a horizontal line.

11. A method according to claim 7, further comprising storing said binary digital image to be scanned in said scanning step.

12. A method according to claim 7, further comprising storing said picture element connection data formed in said scanning step and storing said picture element block data formed in said forming step.