Method and an apparatus for extracting a connected element from a binary image

• US 6,081,618 A
• Filed: 10/28/1997
• Issued: 06/27/2000
• Est. Priority Date: 05/31/1994
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Yanagishita, Hideki, Naoi, Satoshi
• Primary Examiner(s): Johns, Andrew W.
• Application Number:
  US08/959,712
• Time in Patent Office: 973 Days
• Field of Search: 382/177, 382/178, 382/179, 382/204, 382/173, 382/180, 382/282, 382/283
• US Class Current: 382/180
• CPC Class Codes: G06T 2207/10008 from scanner, fax or copier
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/18076 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

The connected element extraction device stores a binary image signal as binary image data; calculates a rectangle circumscribing a connected element; determines whether the rectangle overlaps with others and stores the label and coordinates of an overlapping rectangle; generates a label image of the overlapping rectangle; based on the label image, divides the overlapping rectangle as a parent rectangle into child rectangles and repeatedly subdivides the child-rectangle into final child rectangles which respectively have a single label; and outputs information comprising the binary image data, and the coordinates of the non-overlapping rectangle, parent-rectangle and final child-rectangles.

Claims

1. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

binary image storage means for storing therein the input binary image signal as binary image data;

labeling means for performing label processing on the binary image data and generating the label image;

rectangle calculation means, based on the label image data, for calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

overlap determination means based on the rectangle definition data for determining whether a rectangle calculated by said rectangle calculation means is an overlapping or non-overlapping rectangle depending on whether or not the rectangle overlaps with other rectangles; and

output means for outputting data comprising the binary image data, the rectangle definition data and the label image data of the overlapping rectangle, as the data for generating the connected element.

2. An apparatus according to claim 1,

wherein said overlap determination means comprises:

first determination means for determining whether one or more vertexes of the second rectangle are inside the first rectangle or whether two or more vertexes of the second rectangle are on a boundary of the first rectangle;

second determination means for determining whether one vertex of the second rectangle is on a boundary of the first rectangle or whether one vertex of the second rectangle is on a vertex of the first rectangle;

third determination means for determining whether one or more vertexes of the first rectangle are inside the second rectangle, if the determination by said determination means is positive;

fourth determination means for determining whether two vertexes of the second rectangle are on a boundary of the first rectangle;

fifth determination means for determining whether two or more vertexes of the first rectangle are on a boundary of the second rectangle, if the determination by said fourth determination means is positive; and

means for determining that the first and second rectangles overlap with each other, if the determination by any of said first, third and fifth determination means is positive.

3. An apparatus according to claim 2,

wherein said overlap determination means further comprises:

setting means for setting different positional values respectively to positional relationships that a vertex of one of the first and second rectangles is `inside`, `on a boundary of`, `on a vertex of` and `outside` the other rectangle; and

addition means for adding the positional values for four vertexes of the rectangle, and

wherein said first to fifth determination means compare the addition result with respective predetermined values and make the determination depending on the comparing.

4. An apparatus according to claim 2,

wherein said overlap determination means calculates a distance between the two rectangles and determines the rectangles as not overlapping with each other if the distance is lager than a predetermined value;

otherwise makes the determination.

5. An apparatus according to claim 1,

wherein said output means further outputs the rectangle definition data of the non-overlapping rectangle.

6. An apparatus according to claim 1,

wherein said output means represents the label image data by the label and binary image data obtained by replacing the label of the label image by a binary number 1.

7. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

binary image storage means for storing therein the input binary image signal as binary image data;

rectangle calculation means for performing label processing on the binary image data to generate the label image and calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

overlap determination means based on the rectangle definition data for determining whether a rectangle calculated by said rectangle calculation means is an overlapping or non-overlapping rectangle depending on whether or not the rectangle overlaps with others;

re-labeling means for performing label processing again on the binary image data of the overlapping rectangle and generating the label image thereof; and

output means for outputting data comprising the binary image data, the rectangle definition data and the label image data of the overlapping rectangle, as the data for generating the connected element.

8. An apparatus according to claim 7, wherein said overlap determination means comprises:

first determination means for determining one of whether at least one vertex of the second rectangle is inside the first rectangle and whether at least two vertexes of the second rectangle are on a boundary of the first rectangle;

second determination means for determining one of whether one vertex of the second rectangle is on a boundary of the first rectangle and whether one vertex of the second rectangle is on a vertex of the first rectangle;

third determination means for determining whether at least one vertex of the first rectangle is inside the second rectangle, if the determination by said determination means is positive;

fourth determination means for determining whether two vertexes of the second rectangle are on a boundary of the first rectangle;

fifth determination means for determining whether at least two vertexes of the first rectangle are on a boundary of the second rectangle, if the determination by said fourth determination means is positive; and

means for determining that the first rectangle overlaps the second rectangle, if the determination by at least one of said first determination means, said third determination means and said fifth determination means is positive.

9. An apparatus according to claim 7,

wherein said output means further outputs the rectangle definition data of the non-overlapping rectangle.

10. An apparatus according to claim 7,

wherein said output means represents the label image data by the label and binary image data obtained by replacing the label of the label image by a binary number 1.

11. A method for outputting from an input binary signal, data for generating a connected element which is an area including a same label in a label image, said method comprising the steps of:

(a) storing the input binary image signal as binary image data;

(b) labeling the binary image data by performing label processing on the binary image data stored in step (a) and generating the label image data;

(c) calculating a rectangle, based on the label image data, circumscribing a same label and rectangle definition data for defining the rectangle by the label and a position in the label image;

(d) determining that a rectangle calculated in step (c) overlaps with others based on the rectangle definition data; and

(e) outputting data comprising the binary image data, the rectangle definition data and the label image data of the overlapping rectangle, as the data for generating the connected element.

12. A method according to claim 11,

wherein said determining in step (d) comprises the steps of:

(h) determining whether one or more vertexes of the second rectangle are inside the first rectangle or whether two or more vertexes of the second rectangle are on a boundary of the first rectangle;

(i) determining whether one vertex of the second rectangle is on a boundary of the first rectangle or whether one vertex of the second rectangle is on a vertex of the first rectangle;

(j) determining whether one or more vertexes of the first rectangle are inside the second rectangle, if the determination by said determination means is positive;

(k) determining whether two vertexes of the second rectangle are on a boundary of the first rectangle;

(l) determining whether two or more vertexes of the first rectangle are on a boundary of the second rectangle, if the determination by said fourth determination means is positive; and

(m) determining that the first and second rectangles overlap with each other if the determination by any of said first, third and fifth determination means is positive.

13. A method according to claim 12,

wherein said determining in step (d) further comprises:

(n) setting different positional values respectively to positional relationships that a vertex of one of the first and second rectangles is `inside`, `on a boundary of`, `on a vertex of` and `outside` the other rectangle; and

(o) adding the positional values for four vertexes of the rectangle, and

wherein said determining in steps (h)-(l) compare the addition result in step (o) with respective predetermined values and make the determination depending on the comparing.

14. A method according to claim 12, wherein said determining in step (d) calculates a distance between the two rectangles and determines the rectangles as not overlapping with each other if the distance is larger than a predetermined value;

otherwise makes the determination.

15. A method according to claim 11,

wherein said outputting in step (e) further outputs the rectangle definition data of the non-overlapping rectangle.

16. A method according to claim 11,

wherein said outputting in step (e) represents the label image data by the label and binary image data obtained by replacing the label of the label image by a binary number 1.

17. A method for outputting from an input binary image signal, data for generating a connected element which is an area including a same label in a label image, said method comprising the steps of:

(a) storing the input binary image signal as binary image data;

(b) performing label processing on the binary image data stored in step (a), and generating the label image and calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

(c) determining that a rectangle calculated in step (b) overlaps with other rectangles based on the rectangle definition data;

(d) re-labeling the overlapping rectangle determined in step (c) by performing label processing on the binary image data of the overlapping rectangle and generating the label image thereof; and

(e) outputting data comprising the binary image data, the rectangle definition data and the label image data of the overlapping rectangle, as the data for generating the connected element.

18. A method according to claim 17,

wherein said outputting in step (e) further outputs the rectangle definition data of the non-overlapping rectangle.

19. A method according to claim 17,

wherein said outputting in step (e) represents the label image data by the label and binary image data obtained by replacing the label of the label image by a binary number 1.

20. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

detection means for detecting in the label image that a first rectangle circumscribing a first label includes a second rectangle circumscribing a second label; and

output means, based on the detecting by said detection means, for outputting data obtained by an addition/subtraction of the second rectangle to/from the first rectangle, as the data for generating the connected element having the first label.

21. An apparatus according to claim 20,

wherein said output means further outputs the label image data of the first rectangle.

23. An apparatus according to claim 21,

wherein said output means further outputs the label image data of the first rectangle.

22. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

detection means for detecting in the label image that a first rectangle circumscribing a first label overlaps with a second rectangle circumscribing a second label; and

output means, based on the detecting by said detection means, for outputting data obtained by an addition/subtraction of an area where the first and second rectangles overlap with each other, to/from the first rectangle as the data for generating the connected element.

24. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

binary image storage means for storing therein the input binary image signal as binary image data;

labeling means for performing label processing on the binary image data and generating the label image;

rectangle calculation means, based on the label image data, for calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

overlap determination means based on the rectangle definition data, for determining whether a rectangle calculated by said rectangle calculation means is an overlapping or non-overlapping rectangle depending on whether or not the rectangle overlaps with other rectangles;

division means for dividing the overlapping rectangle as a parent-rectangle into child-rectangles according to the label included in the parent-rectangle and for calculating rectangle-definition data of the child-rectangles;

label check means for checking whether the child-rectangles share a same label or different labels; and

output means for outputting data comprising binary image data, the rectangle definition data of the non-overlapping rectangle, the rectangle definition data of both the parent-rectangle and child-rectangles which share a same label, and the label image data of the parent-rectangle whose child-rectangles share different labels.

25. An apparatus according to claims 24,

wherein said output means outputs the label image data of the parent-rectangle whose child-rectangles share different labels, by the label and a binary image data obtained by replacing the label of the label image by a binary number 1.

26. An apparatus according to claim 24, wherein said label check means makes the checking by performing the label processing on the parent rectangle to generate the label image and comparing the label of the parent rectangle with those of the child rectangles.

27. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

binary image storage means for storing therein the input binary image signal as binary image data;

rectangle calculation means for performing label processing on the binary image data to generate the label image and calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

overlap determination means based on the rectangle definition data for determining whether a rectangle calculated by said rectangle calculation means is an overlapping or non-overlapping rectangle depending on whether or not the rectangle overlaps with others;

re-labeling means for performing label processing again on the binary image data of the overlapping rectangle and generating the label image thereof;

division means, based on the label image generated by said re-labeling means, for dividing the overlapping rectangle as a parent-rectangle, into child-rectangles according to the label and for calculating rectangle-definition data of the child-rectangles;

label check means for checking whether the child-rectangles share a same label or different labels; and

output means for outputting data comprising the binary image data, the rectangle definition data of the non-overlapping rectangle, the rectangle definition data of both the parent-rectangle and child-rectangles which share a same label, and the label image data of the parent-rectangle whose child-rectangles share different labels.

28. An apparatus according to claims 27,

wherein said output means represents the label image data of the parent-rectangle whose child-rectangles share a different labels, by the label and a binary image data obtained by replacing the label of the label image by a binary number 1.

29. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

binary image storage means for storing therein the input binary image signal as binary image data;

rectangle calculation means for preforming label processing on the binary image data to generate the label image and calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

overlap determination means based on the rectangle definition data, for determining whether a rectangle calculated by said rectangle calculation means is an overlapping or non-overlapping rectangle depending on whether or not the rectangle overlaps with others;

re-labeling means for performing the label processing again on the binary image data of the overlapping rectangle and generating the label image thereof;

division means, based on the label image generated by said re-labeling means, for dividing the overlapping rectangle as a parent-rectangle into child-rectangles and repeatedly subdividing the child-rectangle into final child-rectangles which respectively have a same label and for calculating rectangle-definition data of the final child-rectangle; and

output means for outputting data comprising the binary image data, the rectangle definition data of the non-overlapping rectangle, and the rectangle definition data of the parent-rectangle and the final child-rectangles calculated by said division means.

30. An apparatus according to claim 29,

wherein said division means comprises:

label comparison means for comparing the label of each child-rectangle with that of the parent rectangle; and

operator adding means for adding to each child-rectangle, an operator indicating match or mismatch depending on the comparing by said label comparison means, and

wherein said output means further outputs the operator.

31. An apparatus according to claim 30,

wherein said division means further comprises local labeling means for performing the label processing on an area enclosing a child rectangle to generate a label image of the area,

wherein said label comparison means compares the label of the child rectangle with that of the parent rectangle based on the label image generated by said local labeling means, and

wherein said operator adding means adds the operator to the child rectangle depending on the comparing by said label comparison means.

32. A method for outputting, from an input binary image signal, data for generating a connected element which is an area including a same label in a label image, said method comprising the steps of:

(a) detecting in a label image that a first rectangle circumscribing a first label includes a second rectangle circumscribing a second label; and

(b) based on the detecting in step (a), outputting data obtained by an addition/subtraction of the second rectangle to/from the first rectangle, as the data for generating the connected element having the first label.

33. A method according to claim 32, wherein said outputting in step (b) further outputs the label image of the first rectangle.

34. A method for outputting, from an input binary image signal, data for generating a connected element which is an area including a same label in a label image, said method comprising the steps of:

(a) detecting in the label image that a first rectangle circumscribing a first label overlaps with a second rectangle circumscribing a second label; and

(b) based on the detecting in step (a), outputting data obtained by an addition/subtraction of an area where the first and second rectangles overlap with each other, to/from the first rectangle.

35. A method according to claim 34, wherein said outputting in step (b) further outputs the label image of the first rectangle.

36. A method for outputting, from an input binary image signal, data for generating a connected element which is an areas including a same label in a label image, said method comprising the steps of:

(a) storing the input binary signal as binary image data;

(b) performing label processing on the binary image data stored in step (a) and generating the label image;

(c) calculating a rectangle circumscribing a same label based on the label image data, and rectangle definition data defining the rectangle by the label and a position in the label image;

(d) determining whether a rectangle calculated in step (c) is an overlapping or non-overlapping rectangle depending on whether the rectangle overlaps with other rectangles or not;

(e) dividing the overlapping rectangle as a parent-rectangle into child-rectangles according to the label included in the parent-rectangle and calculating rectangle-definition data of the child-rectangles;

(f) checking whether the child-rectangles share a same label or different labels; and

(g) outputting the binary image data, the rectangle definition data of the non-overlapping rectangle, the rectangle definition data of both the parent-rectangle and child-rectangles which share a same label, and the label image data of the parent-rectangle whose child-rectangles share different labels.

37. A method according to claim 36, wherein said outputting in step (g) represents the label-image data of the parent-rectangle whose child-rectangles share different labels, by the label and a binary image data obtained by replacing the label of the label image by a binary number 1.

38. A method according to claim 36, wherein said checking in step (f) makes the checking by performing the label processing on the parent rectangle to generate the label image and comparing the label of the parent rectangle with those of the child-rectangles.

39. A method for outputting, from an input binary image signal, data for generating a connected element which is an area including a same label in a label image, said method comprising the steps of:

(a) storing the input binary image signal as binary image data;

(b) performing label processing on the binary image data stored in step (a) to generate the label image and calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

(c) determining whether a rectangle calculated in step (b) is an overlapping or non-overlapping rectangle depending on whether or not the rectangle overlaps with others;

(d) performing label processing again on the binary image data of the overlapping rectangle and generating the label image thereof;

(e) based on the label image generated in step (d), dividing the overlapping rectangle as a parent-rectangle, into child-rectangles according to the label and calculating rectangle-definition data of the child-rectangles;

(f) checking whether the child-rectangles share a same label or different labels; and

(g) outputting the binary image data stored in step (a), the rectangle definition data of the non-overlapping rectangle, the rectangle definition data of both the parent-rectangle and child-rectangles which share a same label, and the label image data of the parent-rectangle whose child-rectangles share different labels.

40. A method according to claim 39, wherein said outputting in step (g) represents rectangle whose child-rectangles share a different labels, by the label and a binary image data obtained by replacing the label of the label image by a binary number 1.

41. A method for generating, from an input binary image signal, data for generating a connected element which is an area including a same label in a label image, said method comprising the steps of:

(a) storing the input binary image signal as binary image data;

(b) performing label processing on the binary image data to generate the label image and calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

(c) determining whether a rectangle calculated in step (b) is an overlapping or non-overlapping rectangle depending on whether or not the rectangle overlaps with others;

(d) performing the label processing on the label image data of the overlapping rectangle determined in step (c) and generating the label image thereof;

(e) based on the label image generated in step (d), dividing the overlapping rectangle as a parent-rectangle into child-rectangles and repeatedly subdividing the child-rectangle into final child-rectangles which respectively have a same label and calculating rectangle-definition data of the final child-rectangle; and

(f) outputting data comprising the binary image data, the rectangle definition data of the non-overlapping rectangle, and the rectangle definition data of the parent-rectangle and the final child-rectangles calculated in step (e).

42. A method according to claim 41,

wherein said dividing in step (e) comprises the steps of:

(g) comparing the label of each child rectangle with that of the parent rectangle; and

(h) adding to each child-rectangle, an operator indicating match or mismatch depending on said comparing in step (g), and

wherein said outputting in step (f) further outputs the operator.

43. A method according to claim 42,

wherein said dividing in step (e) further comprises the step of (i) performing the label processing on an area enclosing a child rectangle to generate a label image of the area,

wherein said comparing in step (i) compares the label of the child rectangle with that of the parent rectangle based on the label image generated in step (i), and

wherein said adding in step (h) adds the operator to the child rectangle depending on said comparing in step (i).

44. An apparatus for extracting from an input binary image signal a connected element which is an area including a same label in a label image, comprising:

rectangle calculation means for calculating a rectangle circumscribing a same label based on the label image data generated from the binary image data;

overlap detection means for detecting rectangles which overlap with each other and correspond to respective connected elements;

division means for selecting one of the overlapping rectangles detected by said overlap detection means in a pre-determined order and for dividing the selected rectangle into sub-rectangles;

sub-rectangle determination means for determining which of the connected elements the sub-rectangle belongs to;

first specification means for specifying a first connected element depending on the determination by said sub-rectangle determination means; and

second specification means for specifying a second connected element by using the first connected element specified by said first specification means.

45. An apparatus according to claim 44,

wherein, when a rectangle includes a sub-rectangle which has already been used for specifying a connected element, said second specification means specifies a connected element by using the specified connected element.

46. An apparatus according to claim 44,

wherein, when a rectangle includes a sub-rectangle which has already been used for specifying a connected element, said second specification means specifies a connected element by using a portion of the specified connected element, on which portion the rectangles overlap with each other.

47. An apparatus according to claim 44,

wherein said division means selects the overlapping rectangles detected by said overlap detection means in the order of smaller size.

48. An apparatus according to claim 44,

wherein said division means selects a rectangle included by others by priority of the overlapping rectangles detected by said overlap detection means.

49. An apparatus according to claim 44, wherein said sub-rectangle determination means comprises:

contour tracking means for performing contour tracking starting with a particular pixel within a sub-rectangle as a tracking starting pixel; and

first sub-rectangle determination means, according to a result of the contour tracking, for determining whether the sub-rectangle belongs to a connected element corresponding to the selected rectangle.

50. An apparatus according to claim 49, wherein said first sub-rectangle determination means determines that a rectangle including the tracking starting pixel is included in a connected element when a rectangle defined by maximum and minimum coordinates which are obtained by the contour tracking agrees to the rectangle circumscribing the connected element.

51. An apparatus according to claim 49, wherein said contour tracking means selects as the tracking starting, a pixel which in on the boundary of the selected rectangle and which does not belong to a non-selected rectangle.

52. An apparatus according to claim 49,

wherein said first sub-rectangle determination means determines that the sub-rectangle including the track starting pixel does not belong to a connected element corresponding to the selected rectangle, when the tracking exceeds the selected rectangle during execution of the contour tracking.

53. An apparatus according to claim 44, wherein said sub-rectangle determination means comprises:

size determination means for determining whether the selected rectangle is larger in size than a pre-determined value;

label image generation means, when the selected rectangle is determined to be larger in size than a pre-determined value by said size determination means, for generating a label image corresponding to a connected element included in the selected rectangle; and

second sub-rectangle determination means, based on the label image, for determining which of the connected elements the sub-rectangle belongs to.

54. An apparatus according to claim 53,

wherein, when a rectangle includes a rectangle which overlaps with the selected rectangle and which has already been used for specifying a connected element, said second specification means specifies a connected element of the selected rectangle by using the specified connected element.

55. An apparatus according to claim 54,

wherein said division means selects the overlapping rectangles detected by said overlap detection means in the order of smaller size.

56. An apparatus responsive to an input binary image signal for outputting data for generating a connected element which is an area including a same label in a label image, comprising:

binary image storage means for storing therein the input binary image signal as binary image data;

labeling means for performing label processing on the binary image data and generating the label image;

rectangle calculation means, based on the label image data, for calculating a rectangle circumscribing a same label and rectangle definition data defining the rectangle by the label and a position in the label image;

overlap determination means based on the rectangle definition data, for determining whether a rectangle calculated by said rectangle calculation means is an overlapping rectangle that extends and encroaches into an encompassed space of another rectangle or a non-overlapping rectangle that does not extend and encroach into an enclosed space of another rectangle in depending on whether or not the rectangle overlaps with other rectangles; and

output means for outputting data comprising the binary image data, the rectangle definition data and the label image data of the overlapping rectangle, as the data for generating the connected elements.

57. A method comprising:

generating label image data from an image, said label image data contains a plurality of labels;

generating rectangle data representing rectangles that circumscribe a same label; and

generating overlap data representing the rectangles that overlap with other rectangles.

58. A computer readable storage instructing a computer to perform a method comprising:

generating label image data from an image, said label image data contains a plurality of labels;

generating rectangle data representing rectangles that circumscribe a same label; and

generating overlap data representing the rectangles that overlap with other rectangles.

59. An apparatus comprising:

a label generator generating label image data from an image, said label image data contains a plurality of labels;

a rectangle generator generating rectangle data representing rectangles that circumscribe a same label; and

an overlap generator generating overlap data representing the rectangles that overlap with other rectangles.