Process and apparatus for extracting and recognizing figure elements using division into receptive fields, polar transformation, application of one-dimensional filter, and correlation between plurality of images

• US 6,005,984 A
• Filed: 12/11/1992
• Issued: 12/21/1999
• Est. Priority Date: 12/11/1991
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Okamoto, Hiroaki, Kawakami, Susumu, Morita, Toshihiko, Yasukawa, Yusuke, Inamoto, Yasushi, Hasegawa, Fumi
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): MEHTA, BHAVESH M
• Application Number:
  US07/987,954
• Time in Patent Office: 2,566 Days
• Field of Search: 382/16, 382/22, 382/41, 382/49, 382/94, 382/199, 382/276, 382/281, 382/293, 382/302, 395/94
• US Class Current: 382/276
• CPC Class Codes: G06V 10/449 Biologically inspired filters, e.g. difference of Gaussians [DoG] or Gabor filters
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis

Abstract

An image processing process wherein an image is divided into small areas, a polar transformation is applied to the image in each of the small areas, and image processing is performed based on the result of the polar transformation. Further, each of a plurality of images is divided into small areas, a polar transformation is applied to the image in each of the small areas for each of the plurality of images, and correlation is obtained between the results of the polar transformation for the plurality of images. One-dimensional filter processing is applied to the polar-transformed output.

Claims

1. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector; and

a third step for applying one-dimensional filtering on the polar-transformed image.

2. An image processing process according to claim 1, wherein the one-dimensional filtering is one-dimensional first differential filtering.

3. An image processing process according to claim 2, further comprising a fifth step for extracting a figure element corresponding to an edge existing in each of the small areas of the original image, based on the result of the processing of one-dimensional first differential filtering.

4. An image processing process according to claim 1, wherein, in the third step, a plurality of one-dimensional first differential filtering are applied at the same time to the result of the polar transformation, wherein the plurality of one-dimensional first differential filtering have different characteristics, respectively, and

the fourth step comprises a sub-step for synthesizing results of the plurality of one-dimensional first differential filtering.

5. An image processing process according to claim 1, wherein the one-dimensional filtering is one-dimensional filtering by a skeleton filter the characteristics of which can be expressed by a δ

-function.

6. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformation image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector;

a third step for applying one-dimensional second differential filtering on the solar-transformed image; and

a fourth step for extracting a figure element corresponding to a line existing in each of the small areas of the original image from the result of the one-dimensional second differential filtering.

7. An image processing process according to claim 6, wherein, in the third step, a plurality of one-dimensional second differential filtering are applied at the same time to the result of the polar transformation, wherein the plurality of one-dimensional second differential filtering have different widths, respectively, and

the fourth step comprises a sub-step for synthesizing the results of the plurality of one-dimensional second differential filtering.

8. An image processing process according to claim 6 further comprising another step after the third step for dividing the results of the plurality of one-dimensional second differential filtering into positive signals and negative signals, respectively;

and

the fourth step comprises;

a first sub-step for synthesizing the positive signals obtained from the plurality one-dimensional second differential filtering to output the synthesized result, and

a second sub-step for synthesizing the negative signals obtained from the plurality of one-dimensional second differential filtering to output the synthesized result.

9. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the solar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)=dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector;

a third step for applying one-dimensional second differential filtering on the polar-transformed image;

a fourth step for inverting the polarity of the result of the one-dimensional second differential filtering; and

a fifth step for extracting a figure element corresponding to a gap existing in each of the small areas of the original image from the result of the inverting.

10. An image processing process according to claim 9, wherein the third step comprises:

a first sub-step for applying a plurality of one-dimensional second differential filtering at the same time to the result of the polar transformation, wherein the plurality of types of one-dimensional second differential filtering have different widths, respectively, and

a second sub-step for synthesizing the results of the plurality of first differential filtering.

11. An image processing process according to claim 9, further comprising:

another step before the third step for applying a plurality of one-dimensional first differential filtering at the same time to the result of the polar transformation, wherein the plurality of one-dimensional first differential filtering have different widths, respectively; and

an additional step for synthesizing the results of the plurality of first differential filtering.

12. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector;

a third step for applying one-dimensional first differential filtering on the polar-transformed image; and

a fourth step for extracting a figure element corresponding to an edge existing in each of the small areas of the original image from the result of the third step.

13. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector;

a third step for applying one-dimensional first differential filtering on the polar-transformed image;

a fourth step for applying one-dimensional second differential filtering on the result of the one-dimensional first differential filtering; and

a fifth step for extracting a figure element corresponding to an edge existing in each of the small areas of the original image from the result of the fourth step.

14. An image processing process according to claim 13, further comprising an additional step, before the fourth step, for separating the result of the one-dimensional differential filtering into positive and negative signals;

and

the fourth step comprises;

a first sub-step for applying one-dimensional second differential filtering on the positive and negative signals, respectively, and

a second sub-step for synthesizing the results of one-dimensional second differential filtering obtained from the positive and negative signals, for outputting the synthesized result.

15. An image processing process according to claim 13, wherein, in the third step, a plurality of one-dimensional first differential filtering are applied at the same time to the result of the polar transformation, where the plurality of types of one-dimensional first differential filtering have different widths, respectively, and

in the fourth step, one-dimensional second differential filtering is applied on the results of the plurality of types of one-dimensional first differential filtering to obtain a plurality of results of the one-dimensional second differential filtering, and

the fifth step comprises a sub-step for synthesizing the results of the plurality of one-dimensional second differential filtering.

16. An image processing process according to claim 15 further comprising another step for separating the results of the plurality of one-dimensional differential filtering into positive signals and negative signals, respectively;

in the fourth step, one-dimensional second differential filtering is applied to the positive signals and negative signals obtained from the plurality of one-dimensional differential filtering to output a plurality of positive signals and a plurality of negative signals, and

the another step comprises;

a first sub-step for synthesizing the plurality of positive signals to output the synthesized result, and

a second sub-step for synthesizing the plurality of negative signals to output the synthesized result.

17. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector;

a third step for applying one-dimensional second differential filtering on the polar-transformation image;

a fourth step for extracting a figure element corresponding to a line existing in each of the small areas of the original image based on the result of the third step and for producing a fourth step result;

a fifth step for applying one-dimensional first differential filtering on the polar-transformed image and for producing a fifth step result; and

a sixth step for extracting a line which does not coincide with the line obtained in the fourth step, from the fifth step result, as a figure element corresponding to an edge existing in each of the small areas of the original image.

18. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector;

a third step for applying one-dimensional second differential filtering on the polar-transformed image;

a fourth step for extracting a candidate of a figure element corresponding to a line existing in each of the small areas of the original image from the result of the third step;

a fifth step for applying one-dimensional first differential filtering on the polar-transformed image;

a sixth step for extracting a candidate of a figure element corresponding to an edge existing in each of the small areas of the original image from the result of the fourth step; and

a seventh step for extracting figure elements corresponding to a line and an edge, respectively, existing in each of the small areas of the original image from the candidates of the figure elements corresponding to the line and the edge of the fourth and sixth steps.

19. An image processing process comprising:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to each pixel in the original image in each of the small areas, and obtaining a curve on a predetermined dual plane as a polar-transformed image element of each pixel in the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, each pixel of the original image in each of the small areas corresponds to said vector, and said curve as said polar-transformed image element which is polar-transformed from each pixel corresponds to said n-dimensional hyperplane;

a third step for obtaining an accumulated polar-transformed image on the dual plane by accumulatively storing in a memory having a storage area for each pixel on the dual plane, a value of each pixel in the original image, as a value of each pixel constituting said curve on the dual plane; and

a fourth step for applying one-dimensional filtering on the accumulated polar-transformed image in each of the small areas.

20. An image processing process according to claim 19, wherein, in the fifth step, a point at which a peak of the values accumulatively stored in the memory is located in the polar-transformed image on the dual plane, is recognized as a line existing in each of the small areas of the original image.

21. An image processing apparatus comprising:

a first means for dividing an original image into small areas;

a second means for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector; and

a one-dimensional filter for applying one-dimensional filtering on the polar-transforming image.

22. An image processing apparatus comprising:

first means for dividing an original image into small areas;

second means for applying polar transformation to each pixel in the original image in each of the small areas, and obtaining a curve on a predetermined dual plane as a polar-transformed image element of each pixel in the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, each pixel of the original image in each of the small areas corresponds to said vector, and said curve as said polar-transformed image element which is polar-transformed from each pixel corresponds to said n-dimensional hyperplane;

a memory having a storage area for each pixel on the dual plane;

third means for obtaining an accumulated polar-transformed image on the dual plane by accumulatively storing in the memory, a value of each pixel in the original image, as a value of each pixel constituting said curve on the dual plane; and

a one-dimensional filter for applying one-dimensional filtering on the accumulated polar-transformed image.

23. A computer readable product storing at least one program which, when executed by a processor, causes the processor and its associated hardware to carry out the steps of:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a solar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector; and

a third step for applying one-dimensional filtering on the polar-transformed image.

24. A program executing machine containing a computer readable product storing at least one program which, when executed by the program executing machine, causes the program executing machine and its associated hardware to carry out the steps of:

a first step for dividing an original image into small areas;

a second step for applying polar transformation to the original image in each of the small areas, to obtain a polar-transformed image of the original image in each of the small areas, where the polar transformation is a transformation between an n-dimensional hyperplane containing an origin in an (n+1)-dimensional Affine space, and a vector passing through the origin and perpendicular to the n-dimensional hyperplane, at least one image element of each of the original images in each of the small areas corresponds to one of said n-dimensional hyperplane and said vector, and a polar-transformed image element which is polar-transformed from each of said at least one image element corresponds to the other of said n-dimensional hyperplane and said vector; and

;

a third step for applying one-dimensional filtering on the polar-transformed image.

25. An image processing process comprising:

dividing an original image into small areas;

applying polar transformation to the original image in each of the small areas, wherein said polar transformation comprises an n-dimensional hyperplane containing an origin in an (n+1)-dimensional affine space and a vector passing through the origin and perpendicular to the n-dimensional hyperplane; and

applying one-dimensional filtering to the result of the polar transformation.