Method for determining orientation of contour line segment in local area and for determining straight line and corner

• US 5,586,199 A
• Filed: 06/02/1993
• Issued: 12/17/1996
• Est. Priority Date: 10/02/1991
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Maruyama, Tsugito, Morita, Toshihiko, Kanda, Shinji, Wakitani, Jun
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/070,450
• Time in Patent Office: 1,294 Days
• Field of Search: 382/21, 382/22, 382/23, 382/24, 382/25, 382/27, 382/197, 382/199, 382/201, 382/202, 382/203, 382/205
• US Class Current: 382/197
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/443 by matching or filtering
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

The present invention relates to a method for determining an orientation of a line segment in a contour in a local area of a binary contour image. The number of pixels having a predetermined value and located in each orientation in the local area, is obtained, and it is determined that a line segment exists in an orientation in which the number of pixels is large. Further, when it is determined that the number of pixels located in each of a plurality of orientations and having a predetermined value is greater than a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof, it is determined that a line segment exists in said each orientation. Two orientations in which large numbers of pixels are located are detected, and it is determined whether the point is a constituent of a line segment, a line segment of the sub-straight-line form, or a near-corner point, depending on angles made by the two orientations is equal to 180°, or a difference of the angles made by the two orientations from 180°. Contiguously arrayed pixels in the same orientation are detected as a line segment. A position and an orientation are obtained from points near a corner, and representative values of the positions and orientations of contiguously arrayed near-corner points are determined.

Claims

1. A method for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in a plurality of orientations around one of pixels, located in the local area and having said first predetermined value, wherein the pixels are stored in the storage memory unit; and

a second step for determining that a local line segment exists in an orientation in which the number of pixels located in the orientation is greater than a second predetermined value using the processing unit.

2. A method according to claim 1, wherein in said second step, it is determined that line segments exist in a plurality of orientations in which said numbers of pixels are the first largest and the second largest, respectively.

3. A method according to claim 2, wherein in said local area, first and second patterns are set in said first step;

the first pattern being constituted by a first plurality of sectorial areas around the center pixel; and

the second pattern being constituted by a second plurality of sectorial areas each of which is arranged around the center pixel, where the locations of the sectorial areas in the second pattern are different from the locations of the sectorial areas in the first pattern by a predetermined range of azimuth around the center pixel;

one of the sectorial areas in each of the first and second patterns are obtained where the number of pixels located in said one of the sectorial areas in the first pattern is greater than a second predetermined value, and the number of pixels located in said one of the sectorial areas in the second pattern is greater than the second predetermined value, respectively; and

it is determined that a line segment exists in an orientation in which said one of the sectorial areas in the first pattern and said one of the sectorial areas in the second pattern are overlapped.

4. A method according to claim 1, wherein said plurality of orientations are obtained by determining an angle made between a straight line passing through each of the pixels having said first predetermined value in each of said local area and the center pixel in the local area, and a straight line in a predetermined orientation passing through the center pixel.

5. A method according to claim 1, wherein the operation of obtaining the number of pixels is performed by counting the numbers of pixels in a plurality of sectorial areas around the center pixel.

6. A method according to claim 1, wherein in said local area, first and second patterns are set in said first step;

the first pattern being constituted by a first plurality of sectorial areas around the center pixel; and

the second pattern being constituted by a second plurality of sectorial areas each of which is arranged around the center pixel, where the locations of the sectorial areas in the second pattern are different from the locations of the sectorial areas in the first pattern by a predetermined range of azimuth around the center pixel; and

it is determined that a line segment exists in an orientation in which one of the sectorial areas in the first pattern and one of the sectorial areas in the second pattern are overlapped, where the number of pixels located in said one of the sectorial areas in the first pattern is greater than a second predetermined value, and the number of pixels located in said one of the sectorial areas in the second pattern is greater than the second predetermined value, respectively.

7. A method according to claim 1, wherein in the operation of determining the orientation of the local line segment in said local area is performed when there exists at least one pixel having said first predetermined value and located adjacent to the center pixel of the local area.

8. A method according to claim 1, wherein in the operation of determining the orientation of the local line segment in said local area is performed when there exists at least one pixel having a value not equal to said first predetermined value and located adjacent to the center pixel of the local area.

9. A method for determining an orientation of a local line segment included in a contour in a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in a plurality of orientations around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit; and

a second step for determining in each of the plurality of local areas that a local line segment exists in an orientation in which the number of pixels located in the orientation is greater than a second predetermined value using the processing unit.

10. A method according to claim 9, wherein said plurality of pixels located at the centers of a plurality of local areas, are all pixels having said first predetermined value and located in the binary contour image.

11. A method for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for obtaining the numbers of pixels located in a plurality of orientations around one of pixels, located in the local area and having a first predetermined value, wherein the pixels are stored in a storage memory unit;

a second step for determining whether or not the number of pixels located in each orientation is greater than a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit; and

a third step for determining that a local line segment exists in said each orientation when the number of pixels located in each orientation is greater than a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit.

12. A method according to claim 11, wherein the operation of the first step is performed around each of the pixels located in the local area and having the first predetermined value, and the operations of said second and third steps are performed for said each of the pixels.

13. A method according to claim 11, wherein in said first step, the operation of obtaining the number of pixels is performed by counting the numbers of pixels in a plurality of sectorial areas around the center pixel.

14. A method for determining an orientation of a local line segment included in a contour in a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in a plurality of orientations around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit; and

a second step for determining whether or not the number of pixels located in each orientation is greater than a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit; and

a third step for determining that a local line segment exists in said each orientation when the number of pixels located in each orientation is greater than a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit.

15. A method for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for obtaining the numbers of pixels located in a plurality of orientations around one of pixels located in the local area and having a first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for obtaining a difference between the number of pixels located in each orientation and a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit; and

a third step for determining that a local line segment exists in a certain orientation when the difference for the orientation is greater than a second predetermined value using the processing unit.

16. A method according to claim 15, wherein said second predetermined value is equal to zero.

17. A method for determining an orientation of a local line segment included in a contour in a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in a plurality of orientations around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit; and

a second step for obtaining a difference between the number of pixels located in each orientation and a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit; and

a third step for determining that a local line segment exists in a certain orientation when the difference for the orientation is greater than a second predetermined value using the processing unit.

18. A method for detecting a line segment from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for counting the numbers of pixels each having a first predetermined value and located in each of a first plurality of sectorial areas around each pixel having the first predetermined value and located at the center of each of a plurality of local areas, and counting the numbers of pixels each having the first predetermined value and located in each of a second plurality of sectorial areas around said each pixel having the first predetermined value and located at the center of each of the plurality of local areas, where the locations of the second plurality of sectorial areas are different from the locations of the first plurality of sectorial areas, wherein the pixels are stored in the storage memory unit;

a second step for obtaining for each of the first and second patterns a difference between the number of pixels located in each orientation and a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit;

a third step for obtaining for each of the first and second patterns an orientation corresponding to one of the areas for which the difference is greater than a second predetermined value using the processing unit; and

a fourth step for obtaining an overlapping area in which one of the first plurality of sectorial areas and one of the second plurality of sectorial areas are overlapped, where the number of pixels located in said one of the first plurality of sectorial areas is greater than the second predetermined value, and the number of pixels located in said one of the second plurality of sectorial areas is greater than the second predetermined value, respectively; and

for determining that a local line segment exists in an orientation corresponding to said overlapping area using the processing unit.

19. A method for detecting a line segment from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in each of a plurality of orientations around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value wherein the pixels are stored in the storage memory unit;

a second step for determining in each of the plurality of local areas that a local line segment exists in a certain orientation when the number of pixels located in the orientation is greater than a second predetermined value using the processing unit;

a third step for determining in each of the plurality of local areas that a straight local line segment passing through said each of the plurality of pixels exists in the local area when two local line segments are determined to exist in the second step, and the orientations of the two local line segments differ by 180°

from each other using the processing unit; and

a fourth step for determining a group of pixels as a candidate of a line segment when the pixels in the group are contiguously arrayed and it is determined in the third step that local line segments in the same orientation pass through the respective pixels in the respective local areas using the processing unit.

20. A method according to claim 19, wherein in the operation of determining the orientation of the local line segment in each local area is performed when there exists at least one pixel having said first predetermined value and located adjacent to the center pixel of the local area.

21. A method according to claim 19, wherein in the operation of determining the orientation of the local line segment in each local area is performed when there exists at least one pixel having a value not equal to said first predetermined value and located adjacent to the center pixel of the local area.

22. A method according to claim 19, further comprising,

a step for obtaining a correlation coefficient from coordinates of pixels contiguously arrayed where the straight local line segments pass through the pixels;

and

a step for detecting as the candidate of a line segment when the correlation coefficient is greater than a second predetermined value.

23. A method according to claim 19, further comprising,

a step for detecting first and second local line segments which are determined in said second step, as constituents of a nearly-straight local line segment when the orientation of the second local line segment differs from the orientation of the first local line segment by an angle not equal to 180°

and within a predetermined range of azimuth from the orientation of the first local line segment;

a step for detecting a first series of pixels constituted by contiguously arrayed pixels connecting second and third series of contiguously arrayed pixels, as a connection portion connecting between line segments respectively constituted by second and third series of pixels when the second series of pixels constitutes a first candidate which is determined in the fourth step as a candidate of a line segment, and the straight local line segments in a first orientation pass through the respective pixels in the second series of pixels, the third series of pixels constitutes a second candidate which is determined in the fourth step as a candidate of a line segment, and the straight local line segments in a second orientation pass through the respective pixels in the third series of pixels, a nearly-straight local line segment passing through each of the pixels constituting the first series of pixels is detected;

an orientation of one of the first and second local line segments constituting the nearly-straight local line segment passing through a first pixel in the first series of pixels adjacent to the second series of pixels is equal to said first orientation;

an orientation of one of the first and second local line segments constituting the nearly-straight local line segment passing through a second pixel in the first series of pixels adjacent to the third series of pixels is equal to said second orientation; and

the first series of pixels do not contain a candidate of a line segment.

24. A method according to claim 23, further comprising a step for detecting first and second line segments wherein the first line segment is constituted by said second series of pixels and pixels contiguously arrayed from the first pixel to an arbitrary point in the first series of pixels, and the second line segment is constituted by the third series of pixels and pixels contiguously arrayed from the second pixel to the arbitrary point in the first series of pixels.

25. A method according to claim 24, said arbitrary point in the first series of pixels is a middle point of the first series of pixels.

26. A method according to claim 19, further comprising the steps of:

(a) determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined in the second step exceeds a predetermined angle value;

(b) obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously;

(c) obtaining for each group representative values of the coordinates of the respective pixels in the group;

(d) obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group; and

(e) obtaining a representative value of the orientations of all of the pixels in each group.

27. A method according to claim 26, further comprising the steps of:

(f) obtaining pairs of the representative values of the orientations of the corners, from among the representative values of the orientations of the corners obtained in the step (e);

(g) obtaining line segments connecting points corresponding to the representative values of coordinates of the corners in the respective pairs obtained in the step (f);

(h) obtaining two pairs of corners in which the line segments connecting the points corresponding to the representative values of coordinates of the corners intersect; and

(i) obtaining a tetragon by searching for candidates of line segments connecting four corners in the above two pairs, from among the candidates of line segments obtained in the fourth step.

28. A method for detecting a line segment from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for counting the numbers of pixels each having a first predetermined value and located in each of a plurality of sectorial areas around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for determining in each of the plurality of local areas that a local line segment exists in an orientation corresponding to one of the sectorial areas when the number of pixels located in the sectorial area is greater than a second predetermined value using the processing unit;

a third step for determining in each of the plurality of local areas that a straight local line segment passing through said each of the plurality of pixels exists in the local area when two local line segments are determined to exist in the second step, and the orientations of the two local line segments differ by 180°

from each other using the processing unit; and

a fourth step for determining a group of pixels as a candidate of a line segment when the pixels in the group are contiguously arrayed and it is determined in the third step that local line segments in the same orientation pass through the respective pixels in the respective local areas using the processing unit.

29. A method for detecting a line segment from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit, comprising:

a first step for counting the numbers of pixels each having a first predetermined value and located in each of a first plurality of sectorial areas around each pixel having the first predetermined value and located at the center of each of a plurality of local areas, and counting the numbers of pixels each having the first predetermined value and located in each of second plurality of sectorial areas around said each pixel having the first predetermined value and located at the center of each of the plurality of local areas, where the locations of the second plurality of sectorial areas are different from the locations of the first plurality of sectorial areas, wherein the pixels are stored in the storage memory unit;

a second step for obtaining an overlapping area in which one of the first plurality of sectorial areas and one of the second plurality of sectorial areas are overlapped, where the number of pixels located in said one of the first plurality of sectorial areas is greater than a second predetermined value, and the number of pixels located in said one of the second plurality of sectorial areas is greater than the second predetermined value, respectively; and

for determining that a local line segment exists in an orientation corresponding to said overlapping area using the processing unit;

a third step for determining in each of the plurality of local areas that a straight local line segment passing through said each pixel exists in the local area when two local line segments are determined to exist in the second step, and the orientations of the two local line segments differ by 180°

from each other using the processing unit; and

a fourth step for determining a group of pixels as a candidate of a line segment when the pixels in the group are contiguously arrayed and it is determined in the fourth step that local line segments in the same orientation pass through the respective pixels in the respective local areas using the processing unit.

30. A method for detecting a line segment from a contour in a binary contour image implemented by a processing unit accessing a storage means unit, comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in each of a plurality of orientations around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value wherein the pixels are stored in the storage memory unit;

a second step for obtaining a difference between the number of pixels located in each orientation and a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the processing unit;

a third step for determining that a local line segment exists in a certain orientation when the difference for the orientation is greater than a second predetermined value using the processing unit;

a fourth step for determining in each of the plurality of local areas that a straight local line segment passing through said each of the plurality of pixels exists in the local area when two local line segments are determined to exist in the third step, and the orientations of the two local line segments differ by 180°

from each other using the processing unit; and

a fifth step for determining a group of pixels as a candidate of a line segment when the pixels in the group are contiguously arrayed and it is determined in the fourth step that local line segments in the same orientation pass through the respective pixels in the respective local areas using the processing unit.

31. A method for detecting a line segment from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

a first step for counting the numbers of pixels each having a first predetermined value and located in each of a plurality of sectorial areas around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for obtaining a difference between the number of pixels located in each area and a sum of the numbers of pixels in orientations adjacent to said each areas on both sides thereof using the processing unit;

a third step for determining that a local line segment exists in an orientation of one of the areas when the difference for the area is greater than a second predetermined value using the processing unit;

a fourth step for determining in each of the plurality of local areas that a straight local line segment passing through said each of the plurality of pixels exists in the local area when two local line segments are determined to exist in the third step, and the orientations of the two local line segments differ by 180°

from each other using the processing unit; and

a fifth step for determining a group of pixels as a candidate of a line segment when the pixels in the group are contiguously arrayed and it is determined in the fourth step that local line segments in the same orientation pass through the respective pixels in the respective local areas using the processing unit.

32. A method for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in each of a plurality of orientations around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for determining in each of the plurality of local areas that a local line segment exists in an orientation corresponding to one of the sectorial areas when the number of pixels located in the sectorial area is greater than a second predetermined value using the processing unit;

a third step for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined in the second step exceeds a predetermined angle value using the processing unit;

a fourth step for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously using the processing unit;

a fifth step for obtaining for each group representative values of the coordinates of the respective pixels in the group using the processing unit;

a sixth step for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group using the processing unit; and

a seventh step for obtaining a representative value of the orientations of all of the pixels in each group using the processing unit.

33. A method according to claim 32, wherein in the operation of determining the orientation of the local line segment in each local area is performed when there exists at least one pixel having said first predetermined value and located adjacent to the center pixel of the local area.

34. A method according to claim 32, wherein in the operation of determining the orientation of the local line segment in each local area is performed when there exists at least one pixel having a value not equal to said first predetermined value and located adjacent to the center pixel of the local area.

35. A method according to claim 32, wherein said representative values of the coordinates are average values of the coordinates.

36. A method according to claim 32, wherein said representative values of the corner orientations of all of the pixels in the group are average values of the corner orientations of all of the pixels in the group.

37. A method for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in each of a plurality of sectorial areas around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for determining in each of the plurality of local areas that a local line segment exists in an orientation corresponding to one of the sectorial areas when the number of pixels located in the sectorial area is greater than a second predetermined value used in the processing unit;

a third step for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined in the second step exceeds a predetermined angle value used in the processing unit;

a fourth step for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously used in the processing unit;

a fifth step for obtaining for each group representative values of the coordinates of the respective pixels in the group used in the processing unit;

a sixth step for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group used in the processing unit; and

a seventh step for obtaining a representative value of the orientations of all of the pixels in each group used in the processing unit.

38. A method for detecting a position of a corner from a contour in a binary contour image implemented by a central processing unit accessing a storage memory unit comprising:

a first step for counting the numbers of pixels each having a first predetermined value and located in each of a first plurality of sectorial areas around each pixel having the first predetermined value and located at the center of each of a plurality of local areas, and counting the numbers of pixels each having the first predetermined value and located in each of a second plurality of sectorial areas around said each pixel having the first predetermined value and located at the center of each of the plurality of local areas, where the locations of the second plurality of sectorial areas are different from the locations of the first plurality of sectorial areas, wherein the pixels are stored in the storage memory unit;

a second step for obtaining two overlapping areas in each of which one of the first plurality of sectorial areas and one of the second plurality of sectorial areas are overlapped, where the number of pixels located in said one of the first plurality of sectorial areas is greater than a second predetermined value, and the number of pixels located in said one of the second plurality of sectorial areas is greater than the second predetermined value, respectively; and

for determining that a local line segment exists in each of orientations corresponding to said overlapping area using the processing unit;

a third step for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined in the second step exceeds a predetermined angle value using the processing unit;

a fourth step for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously using the processing unit;

a fifth step for obtaining for each group representative values of the coordinates of the respective pixels in the group using the processing unit;

a sixth step for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group using the processing unit; and

a seventh step for obtaining a representative value of the orientations of all of the pixels in each group using the processing unit.

39. A method for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in a plurality of orientations around each of a plurality of pixels respectively located at the centers of a plurality of local areas and each having said first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for obtaining a difference between the number of pixels located in each orientation and a sum of the numbers of pixels in orientations adjacent to said each orientation on both sides thereof using the central processing unit;

a third step for determining that a local line segment exists in a certain orientation when the difference for the orientation is greater than a second predetermined value using the processing unit;

a fourth step for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined in the second and third steps exceeds a predetermined angle value using the processing unit;

a fifth step for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously using the processing unit;

a sixth step for obtaining for each group representative values of the coordinates of the respective pixels in the group using the processing unit;

a seventh step for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group using the processing unit; and

an eighth step for obtaining a representative value of the orientations of all of the pixels in each group using the processing unit.

40. A method according to claim 39, wherein the operation of the second step is made when the number of pixels located in the orientation and having the first predetermined value, is equal to or more than a third predetermined value.

41. A method for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

a first step for obtaining the numbers of pixels each having a first predetermined value and located in each of a plurality of sectorial areas around each of a plurality of pixels respectively located at the centers of a plurality of local areas--and each having said first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for obtaining a difference between the number of pixels located in each sectorial area and a sum of the numbers of pixels in sectorial areas adjacent to said each sectorial area on both sides thereof using the processing unit;

a third step for determining that a local line segment exists in an orientation corresponding to a sectorial area when the difference for the sectorial area is greater than a second predetermined value using the processing unit;

a fourth step for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined in the second and third steps exceeds a predetermined angle value using the processing unit;

a fifth step for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously using the processing unit;

a sixth step for obtaining for each group representative values of the coordinates of the respective pixels in the group using the processing unit;

a seventh step for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group using the processing unit; and

an eighth step for obtaining a representative value of the orientations of all of the pixels in each group using the processing unit.

42. A method for detecting a line segment from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

a first step for counting the numbers of pixels having a first predetermined value and located in a plurality of sectorial areas which are arranged around each of a plurality of pixels located in the binary contour image and having the first predetermined value, wherein the pixels are stored in the storage memory unit;

a second step for determining for each of the plurality of pixels located in the binary contour image and having the first predetermined value, that a local line segment exists in an orientation, corresponding to one of the sectorial areas, from said each of the plurality of pixels, when the number of pixels located in the sectorial area is greater than a second predetermined value using the processing unit;

a third step for determining for each of the plurality of pixels located in the binary contour image and having the first predetermined value, that first and second local line segments which are determined to exist in the second step constitute a straight local line segment passing through said each of the plurality of pixels when the orientations of said first and second local line segments differ by 180°

from each other using the processing unit;

a fourth step for determining for each of the plurality of pixels located in the binary contour image and having the first predetermined value, that third and fourth local line segments constitute a nearly-straight local line segment corresponding to the straight local line segment obtained in the third step when the orientation of the third local line segment is within a predetermined range of azimuth from the orientation of one of the said first and second local line segments constituting the straight local line segment determined in the third step, the orientation of the fourth local line segment is within a predetermined range of azimuth from the orientation of the other of said first and second local line segments, and the difference between the orientations of the above third and fourth local line segments is not equal to 180°

using the processing unit; and

a fifth step for determining a series of pixels as constituents of a candidate of a line segment when the pixels in the series are contiguously arrayed, at least one of the pixels in the series is the pixel through which the straight local line segment is determined in the third step to pass, the respective orientation of at least one straight local line segment which is determined to pass through said at least one of the pixels in the series is the same, and a nearly-straight local line segment, corresponding to said straight local line segment which is determined to exist in the third step for one of said at least one of the pixels, is determined in the fourth step for each of the pixels other than said at least one pixel in the series using the processing unit.

43. A method according to claim 42, further comprising a step for determining that a first candidate of a line segment is a first line segment extending to a first pixel, located nearest a shared pixel, among a first series of pixels, a second candidate of a line segment is a second line segment extending to a second pixel, located nearest the shared pixel, among a second series of pixels, and the first and second line segments are connected by a connection portion constituted by a series of pixels contiguously arrayed from the first pixel to the second pixel located nearest the shared pixel;

when the first series of pixels constitutes the first candidate which is determined as a candidate of a line segment in the fifth step, the orientation of the straight local line segment which is determined in the third step to pass through one of said at least one of the pixels in the first series of pixels is equal to a first orientation, the second series of pixels constitutes the second candidate which is determined as a candidate of a line segment in the fifth step, the orientation of the straight local line segment which is determined in the third step to pass through one of said at least one of the pixels in the second series of pixels is equal to a second orientation which is different from the first orientation, and the first and second series of pixels share said shared pixel.

44. An apparatus for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the number of pixels of the contour points existing in each of a plurality of orientations around a pixel of the contour point in the local area using a processing unit;

filter means for obtaining a difference between the number of pixels of the contour points located in said each of the plurality of orientations, and a sum of the numbers of pixels of the contour points located on both sides of said each orientation; and

local line segment orientation determining means for obtaining an orientation in which the difference is greater than a predetermined number, as an orientation in which a line segment exists.

45. An apparatus for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including a storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the number of pixels of the contour points existing in each of a plurality of orientations around a pixel of the contour point, located at the center of the local area using the processing unit;

filter means for obtaining a difference between the number of pixels of the contour points located in said each of the plurality of orientations, and a sum of the numbers of pixels of the contour points located on both sides of said each orientation; and

local line segment orientation determining means for obtaining an orientation in which the difference is greater than a predetermined number, as an orientation in which a line segment exists.

46. An apparatus for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a first plurality of sectorial areas around the center of the local area, and obtaining the numbers of pixels of the contour points located in each of a second plurality of sectorial areas around the center of the local area, where the locations of the second plurality of sectorial areas are different from the locations of the first plurality of sectorial areas, using the processing unit;

filter means for obtaining for each of the first and second patterns a difference between the number of pixels of the contour points located in each of the plurality of sectorial areas and a sum of the numbers of pixels of the contour points in orientations adjacent to said each orientation on both sides thereof;

in-pattern orientation determining means for obtaining for each of the first and second patterns an orientation corresponding to one of the areas for which the difference is greater than a predetermined value; and

local line segment orientation determining means for obtaining two overlapping areas in each of which one of the first plurality of sectorial areas and one of the second plurality of sectorial areas are overlapped, where the number of pixels located in said one of the first plurality of sectorial areas is greater than a second predetermined value, and the number of pixels located in said one of the second plurality of sectorial areas is greater than the second predetermined value, respectively; and

for determining that a local line segment exists in orientations corresponding to said overlapping areas.

47. An apparatus for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a plurality of orientations around each of a plurality of pixels of the contour points respectively located at the centers of a plurality of local areas using the processing unit;

local line segment orientation detecting means for determining that a local line segment exists in a certain orientation when the number of pixels located in the orientation is greater than a predetermined value;

local line segment detecting means for determining that a straight local line segment passing through said each of the plurality of pixels exists in the local area when two local line segments are determined to exist by the local line segment orientation detecting means, and the orientations of the two local line segments differ by 180°

from each other; and

line segment candidate detecting means for determining that a group of contiguously arrayed pixels constitute a candidate of a straight local line segment when line segments in the same orientation pass through the contiguously arrayed pixels in the local area.

48. An apparatus for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a plurality of sectorial areas around each of a plurality of pixels of the contour points respectively located at the centers of a plurality of local areas using the processing unit;

local line segment orientation detecting means for determining that a local line segment exists in an orientation corresponding to one of the sectorial areas when the number of pixels located in the sectorial area is greater than a predetermined value;

local line segment detecting means for determining that a straight local line segment passing through said each of the plurality of pixels exists in the local area when two local line segments are determined to exist by the local line segment orientation detecting means, and the orientations of the two local line segments differ by 180°

from each other; and

line segment candidate detecting means for determining that a group of contiguously arrayed pixels constitute a candidate of a straight local line segment when line segments in the same orientation pass through the contiguously arrayed pixels in the local area.

49. An apparatus for determining an orientation of local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels each having a first predetermined value and located in each of a first plurality of sectorial areas around each pixel having the first predetermined value and located at the center of each of a plurality of local areas, and obtaining the numbers of pixels each having the first predetermined value located in each of a second plurality of sectorial areas around said each pixel having the first predetermined value and located at the center of each of the plurality of local areas, where the locations of the second plurality of sectorial areas are different from the locations of the first plurality of sectorial-areas using the processing unit;

local line segment orientation determining means for obtaining two overlapping areas in each of which one of the first plurality of sectorial areas and one of the second plurality of sectorial areas are overlapped, where the number of pixels located in said one of the first plurality of sectorial areas is greater than a second predetermined value, and the number of pixels located in said one of the second plurality of sectorial areas is greater than the second predetermined value, respectively; and

for determining that a local line segment exists in each of orientations corresponding to said overlapping areas;

local line segment detecting means for determining that a straight local line segment passing through said each pixel exists in the local area when two local line segments are determined to exist by the local line segment orientation detecting means, and the orientations of the two local line segments differ by 180°

from each other; and

line segment candidate detecting means for determining that a group of contiguously arrayed pixels constitute a candidate of a straight local line segment when line segments in the same orientation pass through the contiguously arrayed pixels in the local area.

50. An apparatus for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a plurality of orientations around each of a plurality of pixels of the contour points respectively located at the centers of a plurality of local areas using the processing unit;

filter means for obtaining a difference between the number of pixels of the contour points located in said each of the plurality of orientations, and a sum of the numbers of pixels of the contour points located on both sides of said each orientation;

local line segment orientation detecting means for determining that a local line segment exists in a certain orientation when the difference for the orientation is greater than a predetermined value;

local line segment detecting means for determining, when first and second local line segments are determined to exist by the local line segment orientation detecting means, and the orientations of the first and second local line segments differ by 180°

from each other, that a straight local line segment passing through said each of the plurality of pixels exists in the local area; and

line segment candidate detecting means for determining that a group of contiguously arrayed pixels constitute a candidate of a straight local line segment when line segments in the same orientation pass through the contiguously arrayed pixels in the local area.

51. An apparatus for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a plurality of sectorial areas around each of a plurality of pixels of the contour points respectively located at the centers of a plurality of local areas;

filter means for obtaining a difference between the number of pixels of the contour points located in said each of the plurality of sectorial areas, and a sum of the numbers of pixels of the contour points located in sectorial areas on both sides of said each sectorial area;

local line segment orientation detecting means for determining that a local line segment exists in an orientation corresponding to a sectorial area when the difference for the sectorial area is greater than a predetermined value;

local line segment detecting means for determining that a straight local line segment passing through said each of the plurality of pixels exists in the local area, when line segments are determined to exist by the local line segment orientation detecting means, and the orientations of the local line segments differ by 180°

from each other; and

line segment candidate detecting means for determining that a group of contiguously arrayed pixels constitute a candidate of a straight local line segment when line segments in the same orientation pass through the contiguously arrayed pixels in the local area.

52. An apparatus for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a plurality of orientations around each of a plurality of pixels of the contour points respectively located at the centers of a plurality of local areas;

local line segment orientation detecting means for determining that a local line segment exists in a certain orientation when the number of pixels for the orientation is greater than a predetermined value;

near-corner-point detecting means for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined by the local line segment orientation determining means exceeds a predetermined angle value;

near-corner-point series detecting means for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously;

corner representative value determining means for obtaining for each group representative values of the coordinates of the respective pixels in the group;

near-corner-point corner-orientation determining means for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group; and

corner-orientation representative value determining means for obtaining a representative value of the orientations of all of the pixels in each group.

53. An apparatus for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a plurality of sectorial areas around each of a plurality of pixels of the contour points respectively located at the centers of a plurality of local areas using the processing unit;

local line segment orientation detecting means for determining that a local line segment exists in an orientation corresponding to a sectorial area when the number of pixels for the sectorial area is greater than a predetermined value;

near-corner-point detecting means for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined by the local line segment orientation determining means exceeds a predetermined angle value;

near-corner-point series detecting means for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously;

corner representative value determining means for obtaining for each group representative values of the coordinates of the respective pixels in the group;

near-corner-point corner-orientation determining means for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group; and

corner-orientation representative value determining means for obtaining a representative value of the orientations of all of the pixels in each group.

54. An apparatus for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels each having a first predetermined value and located in each of a first plurality of sectorial areas around each pixel having the first predetermined value and located at the center of each of a plurality of local areas, and obtaining the numbers of pixels each having the first predetermined value and located in each of the second plurality of sectorial areas around said each pixel having the first predetermined value and located at the center of each of the plurality of local areas, where the locations of the second plurality of sectorial areas are different from the locations of the first plurality of sectorial areas using the processing unit;

local line segment orientation determining means for obtaining two overlapping areas in each of which one of the first plurality of sectorial areas and one of the second plurality of sectorial areas are overlapped, where the number of pixels located in said one of the first plurality of sectorial areas is greater than a second predetermined value, and the number of pixels located in said one of the second plurality of sectorial areas is greater than the second predetermined value, respectively; and

for determining that a local line segment exists in each of orientations corresponding to said overlapping areas;

near-corner-point detecting means for determining in each of the plurality of local areas that the pixel located at the center of the local area is a near-corner point when an absolute value of a difference between 180° and

a difference between the orientations of the two local line segments determined by the local line segment orientation determining means exceeds a predetermined angle value;

near-corner-point series detecting means for obtaining a group of pixels which are determined as the near-corner point, and are arrayed contiguously;

corner representative value determining means for obtaining for each group representative values of the coordinates of the respective pixels in the group;

near-corner-point corner-orientation determining means for obtaining for each group as a corner orientation of the near-corner points a mean orientation of the orientations of the two local line segments in the local area containing at the center of the local area each pixel in the group; and

corner-orientation representative value determining means for obtaining a representative value of the orientations of all of the pixels in each group.

55. An apparatus for detecting a position of a corner from a contour in a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

contour image information holding means, including the storage memory unit, for holding information indicating at least coordinates of contour points of the binary contour image;

pixel number counting means, including the processing unit, for obtaining the numbers of pixels of the contour points located in each of a plurality of orientations around each of a plurality of pixels of the contour points respectively located at the centers of a plurality of local areas using the central processing unit;

filter means for obtaining a difference between the number of pixels of the contour points located in said each of the plurality of orientations, and a sum of the number of pixels of the contour points in orientations on both sides of said each orientation;

local line segment orientation detecting means for determining that a local line segment exists in a certain orientation when the difference for the orientation is greater than a predetermined value;

local line segment detecting means for determining that a straight local line segment passing through said each of the plurality of pixels exists in the local area, when line segments are determined to exist by the local line segment orientation detecting means, and the orientations of the local line segments differ by 180°

from each other; and

line segment candidate detecting means for determining that a group of contiguously arrayed pixels constitute a candidate of a straight local line segment when line segments in the same orientation pass through the contiguously arrayed pixels in the local area.

56. A method for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a central processing unit accessing a storage memory unit comprising the steps of:

obtaining the numbers of pixels located in a plurality of orientations around one of pixels located in the local area and having a predetermined value, wherein the pixels are stored in the storage memory unit;

obtaining a sum of the numbers of pixels in orientations adjacent to each of the plurality of orientations on both sides thereof;

obtaining a difference between the number of pixels located in said each orientation and said sum using the processing unit; and

determining that local line segments exist in two orientations among said plurality of orientations when said difference obtained in the third step is the largest and the second largest in said two orientations, respectively, using the processing unit.

57. A method for determining an orientation of a local line segment in a contour in a local area of a binary contour image implemented by a processing unit accessing a storage memory unit comprising:

a first step for obtaining the numbers of pixels each located in a plurality of orientations around one of pixels located in the local area, wherein the pixels are stored in the storage memory unit; and

a second step for determining that a local line segment exists in an orientation in which the number of pixels located in the orientation is greater than predetermined value, wherein the pixels are stored in the storage memory unit.