Apparatus and method for extracting outline data and encoding image data using the outline data

• US 5,748,777 A
• Filed: 01/24/1995
• Issued: 05/05/1998
• Est. Priority Date: 01/24/1992
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Ishida, Yoshihiro, Yamakawa, Junichi, Katayama, Akihiro
• Primary Examiner(s): Johns, Andrew
• Assistant Examiner(s): Davis, Monica S.
• Application Number:
  US08/377,509
• Time in Patent Office: 1,197 Days
• Field of Search: 382/199, 382/203, 382/206, 382/201, 382/202, 382/204, 382/232
• US Class Current: 382/199
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/421 by analysing segments intersecting the pattern
• CPC Class Codes: G06V 10/469 Contour-based spatial representations, e.g. vector-coding

Abstract

An outline extraction method and apparatus which extracts a line of interest from image data in order of raster scanning and detects outline vectors of the pixels in the line of interest. The detected outline vectors are sequentially stored in a memory, a state of connection between the stored outline vectors and the other outline vectors in the line of interest is determined, and the outline of the image data is extracted based on the state. Accordingly, coordinates of an intersecting point of the outline of the image data with the coordinate axis of the outline vector is obtained and the image data is coded by generating coded data indicating a white run length and black run length for every line from the coordinates of the intersecting point.

Claims

1. An outline data extraction apparatus for processing a raster-scan signal representing an image, and producing a signal representative of an outline of the image, said apparatus comprising:

input means for inputting image data including black and white pixels in a raster scanning form, in units of one scan line of image data;

a processor comprising extraction means for extracting vector data surrounding each black pixel in each scan line of the image data input by said input means, wherein said extracted vector data for each black pixel comprises a plurality of outline vectors surrounding each black pixel and incoming and outgoing vectors for each of said outline vectors, wherein an incoming vector of one of said outline vectors has an end point which is a start point of said one of said outline vectors, and wherein an outgoing vector of one of said outline vectors has a start point which is an end point of said one of said outline vectors

storage means for storing the vector data extracted by said extraction means into an outline vector table;

wherein said processor further comprises updating means for updating the incoming and outdoing vectors in the outline vector table for each of said outline vectors, both in the case when two incoming and outgoing vectors are present in the outline vector table for one of the outline vectors, and in the case when a vector in the outline vector table overlaps one of the outline vectors; and

a memory for registering the updated incoming and outgoing vectors stored in the outline vector table and outputting the updated outline vector table.

2. The apparatus according to claim 1, wherein said input means inputs the image data as coded image data, and wherein said apparatus further comprises decoding means for decoding said coded image data into decoded image data, wherein

said extraction means extracts the vector data of a black pixel in the decoded image data for one scan line.

3. The apparatus according to claim 2, wherein the coded image data indicates white run length and black run length for every line.

4. The apparatus according to claim 2, wherein the coded image data is data indicating a transition point either from a white pixel to a black pixel from a black pixel to a white pixel on the scan line and the difference of the positions of the transition points between the scan lines.

5. The apparatus according to claim 2, wherein the coded image data are codes which are sequentially generated for every pixel.

8. An apparatus according to claim 1, wherein said vector data of each black pixel are determined by a perimeter of each black pixel.

9. An apparatus according to claim 1, further comprising:

outline forming means for forming an outline of the image data based upon the vector data and the incoming and outgoing vectors registered by said register means; and

memory means for storing the outline of the image data formed by said outline forming means, wherein an image pattern is obtained by filling dots in said outline stored in said memory means.

16. An apparatus according to claim 1, wherein the vector data has four vectors representing a rectangle for a black pixel.

17. An apparatus according to claim 16, wherein the four vectors are formed by mutually combining horizontal vectors and vertical vectors.

18. An apparatus according to claim 16, wherein the four vectors are defined between pixels.

6. An outline data extraction method for processing a raster-scan signal representing an image, and producing a signal representative of an outline, said method comprising the steps of:

inputting image data including black and white pixels in a raster scanning form, in units of one scan line of image data;

extracting vector data surrounding each black pixel in each scan line of the image data input in said inputting step, wherein the extracted vector data for each black pixel comprises a plurality of outline vectors surrounding each black pixel and incoming and outgoing vectors for each of said outline vectors, wherein an incoming vector of one of said outline vectors has an end point which is a start point of said one of said outline vectors, and wherein an outgoing vector of one of said outline vectors has a start point which is an end point of said one of said outline vectors;

storing the vector data extracted in said extraction step into an outline vector table;

updating the incoming and outgoing vectors in the outline vector table for each of said outline vectors, both in the case when two incoming and outgoing vectors are present in the outline vector table for one of the outline vectors, and in the case when a vector in the outline vector table overlaps one of the outline vectors; and

registering the updated incoming and outgoing vectors stored in the outline vector table and outputting the updated outline vector table.

7. The method according to claim 6, wherein, in said inputting step, the image data is input as coded image data;

and further comprising;

a decoding step for decoding the coded image data into decoded image data, wherein, in said extracting step, the vector data of a black pixel is extracted in the decoded image data for one scan line.

10. An method according to claim 6, wherein said vector data of each black pixel are determined by a perimeter of each black pixel.

11. An method according to claim 6, further comprising the steps of:

forming an outline of the image data based upon the vector data and the incoming and outgoing vectors registered in said registering step; and

storing the outline of the image data formed in said forming step, wherein an image pattern is obtained by filling dots in the outline.

19. The method according to claim 6, wherein, in said inputting step, the image data is input as coded image data, and further comprising the step of decoding the coded image data into decoded image data, wherein the vector data of black pixels are extracted in the decoded image data for one scan line.

20. The method according to claim 19, wherein the coded image data indicates white run length and black run length for every line.

21. The method according to claim 19, wherein the coded image data is data indicating a transition point either from a white pixel or black pixel to a black pixel or white pixel on the scan line and the difference of the positions of the transition points between the scan lines.

22. The method according to claim 19, wherein the coded image data are codes which are sequentially generated for every pixel.

23. The method according to claim 6, wherein the vector data has four vectors representing a rectangle for a black pixel.

24. The method according to claim 23, wherein the four vectors are formed by mutually combining horizontal vectors and vertical vectors.

25. The method according to claim 23, wherein the four vectors are defined between pixels.

40. The apparatus according to claim 7, further comprising:

outline forming means for forming an outline of the image data based upon said vector data and the connection information of the vector data; and

memory means for storing the outline of the image data formed by said outline forming means,

wherein an image pattern is obtained by filing dots in the outline stored in said memory means.

12. An apparatus for processing a raster-scan signal representing image data including black pixels, identifying and extracting outline data from the image data, and producing a signal representative of the outline, said apparatus comprising:

input means for inputting image data including black and white pixels in a raster scanning form, in units of one scan line of image data;

a processor comprising extraction means for extracting vector data surrounding each black pixel in each scan line of the image data input by said input means, wherein the extracted vector data for each black pixel comprises a plurality of outline vectors surrounding each black pixel and incoming and outgoing vectors for said plurality of outline vector, wherein an incoming vector of one of said outline vectors has an end point which is a start point of said one of said outline vectors, and wherein an outgoing vector of one of said outline vectors has a start point which is an end point of said one of said outline vectors;

storage means for storing the vector data into an outline vector table;

wherein said processor further comprises deleting means for deleting vector data stored in the outline vector table, which has an opposite direction to the direction of outline vector data to be registered, and for updating the incoming and outgoing vectors related to deleted vector data; and

a memory for registering the vector data and the incoming and outgoing vectors stored in the outline vector table and outputting the updated outline vector table.

13. An apparatus according to claim 12, wherein said extraction means comprises:

means for converting the image data of the black pixels in each scan line into outline vectors, and for storing the outline vectors into a memory;

detecting means for detecting each outline vector in a scan line of outline vectors stored in said memory that is connected to an outline vector in a next following scan line; and

combining means for combining each detected outline vector in the scan line with the connected outline vector in the next following scan line.

26. The apparatus according to claim 12, wherein said input means inputs the image data as coded image data, and wherein said apparatus further comprises decoding means for decoding the coded image data into decoded image data, and wherein said extraction means extracts the vector data of black pixels in the decoded image data for one scan line.

27. The apparatus according to claim 26, wherein the coded image data indicates white run length and black run length for every line.

28. The apparatus according to claim 26, wherein the coded image data is data indicating a transition point either from a white pixel or black pixel to a black pixel or white pixel on the scan line and the difference of the positions of the transition points between the scan lines.

29. An apparatus according to claim 26, wherein the coded image data are codes which are sequentially generated for every pixel.

30. An apparatus according to claim 12, wherein the vector data has four vectors representing a rectangle for a black pixel.

31. An apparatus according to claim 30, wherein the four vectors are formed by mutually combining horizontal vectors and vertical vectors.

32. An apparatus according to claim 30, wherein the four vectors are defined between pixels.

14. A method for processing a raster-scan signal representing image data including black pixels, identifying and extracting outline data from the image data, and producing a signal representative of the outline, said method comprising the steps of:

inputting image data including black and white pixels in a raster scanning form, in units of one scan line of image data;

extracting vector data surrounding each black pixel in each scan line of the image data, wherein the vector data for each black pixel comprises a plurality of outline vectors surrounding each black pixel and incoming and outgoing vectors for said plurality of outline vector, wherein an incoming vector of one of said outline vectors has an end point which is a start point of said one of said outline vectors, and wherein an outgoing vector of one of said outline vectors has a start point which is an end point of said one of said outline vectors;

storing the vector data and the incoming and outgoing vectors into an outline vector table;

deleting vector data stored in the outline vector table, which has an opposite direction to the direction of outline vector data to be registered;

updating the incoming and outgoing vectors related to deleted vector data in said deleting step; and

registering the updated vector data and the incoming and outgoing vector data in the outline vector table and outputting the updated outline vector table.

15. A method according to claim 14, further comprising the steps of:

detecting each of the vector data in a scan line stored in said outline vector table, that is connected to vector data in a next following scan line; and

combining each of the detected vector data in the scan line with the vector data in the next following scan line.

33. The method according to claim 14, wherein, in said inputting step, the image data is input as coded image data, and further comprising the step of decoding the coded image data into decoded image data, wherein the vector data of black pixels are extracted in the decoded image data for one scan line.

34. The method according to claim 33, wherein the coded image data indicates white run length and black run length for every line.

35. The method according to claim 33, wherein the coded image data is data indicating a transition point either from a white pixel or black pixel to a black pixel or white pixel on the scan line and the difference of the positions of the transition points between the scan lines.

36. The method according to claim 33, wherein the coded image data are codes which are sequentially generated for every pixel.

37. The method according to claim 14, wherein the vector data has four vectors representing a rectangle for a black pixel.

38. The method according to claim 37, wherein the four vectors are formed by mutually combining horizontal vectors and vertical vectors.

39. The method according to claim 37, wherein the four vectors are defined between pixels.