Method for matching input image with reference image, apparatus for the same, and storage medium storing program for implementing the method

• US 6,111,984 A
• Filed: 01/21/1998
• Issued: 08/29/2000
• Est. Priority Date: 06/10/1997
• Status: Expired due to Term

• Current Assignee: PFU Limited (Fujitsu Limited)
• Original Assignee: Fujitsu Limited
• Inventors: Fukasawa, Yoshio
• Primary Examiner(s): MILLER, MARTIN E
• Application Number:
  US09/009,936
• Time in Patent Office: 951 Days
• Field of Search: 382/175, 382/205, 382/209, 382/216, 382/217, 382/218, 382/289, 382/219, 382/220, 382/221, 382/194, 382/195
• US Class Current: 382/209
• CPC Class Codes: G06V 10/754 involving a deformation of the sample pattern or of the reference pattern; Elastic matching

Abstract

Matching between a reference image and an input image is performed without relying on specific elements such as line segments or tables. An edge image is generated from the reference image and divided into small blocks, and search range and search priority of each small block are determined and stored in a storage device. When an input image is input, an edge image thereof is generated. The small blocks in the reference image are retrieved in order of priority, and matching with the input image is judged. When the corresponding position of one small block is determined, the search range and search priority for other small blocks not yet judged for matching are updated on the basis of the determined corresponding position.

Claims

1. A method of matching an input image with a reference image by determining the positions of various portions in said input image corresponding to various portions of said reference image, comprising the steps of:

(a) dividing in advance said reference image into a plurality of small blocks;

(b) determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

(c) storing said small blocks together with the search range for each small block; and

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks, a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block.

2. A method according to claim 1, further comprising the step of (e) correcting, during the execution of said step (d), the search priority and search ranges for small blocks whose corresponding positions in said input image have not yet been determined, on the basis of the corresponding positions in said input image for the small blocks for which such positions have already been determined.

3. A method according to claim 2 wherein, in said step (a), said reference image is divided into a plurality of medium blocks each consisting of a plurality of small blocks, and

said step (e) includes the substeps of:

(i) calculating, for a medium block having more than a prescribed number of small blocks whose corresponding positions have already been determined, the values of transformation parameters for the entire medium block from the already determined corresponding positions of the small blocks in said medium block;

(ii) determining from said calculated values of transformation parameters the search range for each of the small blocks in said medium block whose corresponding positions have not yet been determined;

(iii) estimating from the values of transformation parameters calculated in said substep (i) the values of transformation parameters for a medium block not having more than the prescribed number of small blocks whose corresponding positions have already been determined; and

(iv) determining from said estimated values of transformation parameters the search range for each of the small blocks in said medium block that does not have more than the prescribed number of small blocks whose corresponding positions have already been determined.

4. A method according to claim 1, wherein in said step (d), the degree of skewness of said input image relative to said reference image is estimated on the basis of the small blocks whose corresponding positions have already been determined, and the determination of the positions, in said input image, of the portions corresponding to said small blocks is corrected on the basis of the value of said estimated degree of skewness.

5. A method of matching an input image with a reference image by determining the positions of various portions in said input image corresponding to various portions of said reference image, comprising the steps of:

(a) dividing in advance said reference image into a plurality of small blocks;

(b) determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

(c) storing said small blocks together with the search range for each small block; and

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks, wherein said step (d) includes the substeps of;

(i) generating in advance a reference edge image by extracting an edge of said reference image,

(ii) generating an input edge image by extracting an edge of said input image,

(iii) calculating the frequency of a distance between each of the pixels forming the edge of said input edge image and each of the pixels forming the edge of said reference edge image when said reference edge image is superimposed at an estimated corresponding position of said input edge image, and

(iv) determining the corresponding position by determining the distance whose calculated frequency exceeds a prescribed threshold as the distance between said input image and said reference image.

6. A method according to claim 5, wherein:

said substep (i) includes the substep of generating a reference upper edge image, a reference lower edge image, a reference left edge image, and a reference right edge image by extracting upper, lower, left, and right edges, respectively, in said reference image;

said substep (ii) includes the substep of generating an input upper edge image, an input lower edge image, an input left edge image, and an input right edge image by extracting upper, lower, left, and right edges, respectively, in said input image;

said substep (iii) includes the substep of calculating the frequencies of distances in vertical direction between each of the pixels forming said input upper and lower edge images and each of the pixels forming said reference upper and lower edge images, respectively, and of distances in horizontal direction between each of the pixels forming said input left and right edge images and each of the pixels forming said reference left and right edge images, respectively, when said input upper edge image, said input lower edge image, said input left edge image, and said input right edge image are superimposed on said reference upper edge image, said reference lower edge image, said reference left edge image, and said reference right edge image, respectively; and

said substep (iv) includes the substeps of;

determining the distances whose frequency calculated for the upper and lower edges exceeds a prescribed threshold and matches within prescribed error limits between the two distances as the distance between said input image and said reference image in the vertical direction, and

determining the distances whose frequency calculated for the left and right edges exceeds a prescribed threshold and matches within prescribed error limits between the two distances as the distance between said input image and said reference image in the horizontal direction.

7. A method according to claim 5, wherein said step (d) further includes the substeps of:

(v) detecting straight edge line running in one of a vertical direction and a horizontal direction in said reference image, and

(vi) when the edge extracted in substep (i) corresponds to the straight edge line detected in said substep (v), replacing a position of the edge in said reference edge image by an intercept value of said straight edge line before performing said substep (iii).

8. A method for recognizing filled-in characters from an input image generated from a form sheet filled out with characters, comprising the steps of:

(a) dividing in advance a reference image generated from a blank form sheet into a plurality of small blocks;

(b) determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

(c) storing said small blocks together with the search range for each small block;

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block;

(e) determining a character entry region in said input image corresponding to a prestored entry region on the basis of the corresponding positions determined in said step (d); and

(f) recognizing a character from an image within the character entry region determined in said step (e) in said input image.

9. A method for recognizing filled-in characters from an input image generated from a form sheet filled out with characters, comprising the steps of:

(a) dividing in advance a reference image generated from a blank form sheet into a plurality of small blocks;

(b) determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

(c) storing said small blocks together with the search range for each small block;

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks, a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block;

(e) stripping said input image of portions corresponding to said reference image on the basis of the corresponding position determined for each small block; and

(f) recognizing characters from said input image that has been stripped of portions corresponding to said reference image in said step (e).

10. A method for detecting a mismatching portion between a first image and a second image, comprising the steps of:

(a) dividing in advance said first image into a plurality of small blocks;

(b) determining for each small block a search range over which the second image is to be searched for a portion corresponding thereto in said second image;

(c) storing said small blocks together with the search range for each small block;

(d) searching said second image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said second image, of the portions corresponding to said small blocks, a search priority of each small block being based on a count of pixels of a specified type contained in the small block;

(e) stripping said second image of portions corresponding to said first image on the basis of the corresponding position determined for each small block;

(f) grouping pixels remaining in said second image that has been stripped of said portions corresponding to first image in said step (e); and

(g) determining a pixel group as representing a mismatching portion if the number of pixels arranged in said step (f) as belonging to said group exceeds a prescribed value.

11. A method for printing characters on a form sheet, comprising the steps of:

(a) dividing in advance a reference image generated from a reference form sheet into a plurality of small blocks;

(b) determining for each small block a search range over which an input image is to be searched for a portion corresponding thereto in the input image generated from a form sheet to be printed with characters;

(c) storing said small blocks together with the search range for each small block;

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks, a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block;

(e) determining a printing position in said input image corresponding to a prestored printing position on the basis of the corresponding positions determined in said step (d); and

(f) printing characters on the form sheet to be printed with characters, in accordance with the printing position determined in said step (e).

12. An apparatus for matching an input image with a reference image by determining the positions of various portions in said input image corresponding to various portions of said reference image, comprising:

search range determining means for determining, for each of a plurality of small blocks into which said reference image is divided, a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

storage means for storing said small blocks together with the search range for each small block; and

searching means for searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks, wherein said searching means determines a search priority of each small block based on a count of pixels of a specified type contained in the small block.

13. An apparatus according to claim 12, further comprising correcting means for correcting, during the execution of searching by said searching means, the search priority and search ranges for small blocks whose corresponding positions in said input image have not yet been determined, on the basis of the corresponding positions in said input image for the small blocks for which such positions have already been determined.

14. An apparatus according to claim 13, wherein said reference image is divided into a plurality of medium blocks each consisting of a plurality of small blocks, and

said correcting means includes:

means for calculating, for a medium block having more than a prescribed number of small blocks whose corresponding positions have already been determined, the values of transformation parameters for the entire medium block from the already determined corresponding positions of the small blocks in said medium block;

means for determining from said calculated values of transformation parameters the search range for each of the small blocks in said medium block whose corresponding positions have not yet been determined;

means for estimating from said calculated values of transformation parameters the values of transformation parameters for a medium block not having more than the prescribed number of small blocks whose corresponding positions have already been determined; and

means for determining from said estimated values of transformation parameters the search range for each of the small blocks in said medium block that does not have more than the prescribed number of small blocks whose corresponding positions have not yet been determined.

15. An apparatus according to claim 12, wherein said searching means estimates the degree of skewness of said input image relative to said reference image on the basis of the small blocks whose corresponding positions have already been determined and, on the basis of the value of said estimated degree of skewness, corrects the determination of the positions, in said input image, of the portion corresponding to said small blocks.

17. An apparatus according to claim 15, wherein said reference edge image generating means includes means for generating a reference upper edge image, a reference lower edge image, a reference left edge image, and a reference right edge image by extracting upper, lower, left, and right edges, respectively, in said reference image,

said input edge image generating means includes means for generating an input upper edge image, an input lower edge image, an input left edge image, and an input right edge image by extracting upper, lower, left, and right edges, respectively, in said input image,

said frequency calculating means includes means for calculating the frequencies of distances in vertical direction between each of the pixels forming said input upper and lower edge images and each of the pixels forming said reference upper and lower edge images, respectively, and of distances in the horizontal direction between each of the pixels forming said input left and right edge images and each of the pixels forming said reference left and right edge images, respectively, when said input upper edge image, said input lower edge image, said input left edge image, and said input right edge image are superimposed on said reference upper edge image, said reference lower edge image, said reference left edge image, and said reference right edge image, respectively, and

said distance determining means includes

means for determining the distances whose frequency calculated for the upper and lower edges exceeds a prescribed threshold and matches within prescribed error limits between the two distances as the distance between said input image and said reference image in the vertical direction, and

means for determining the distances whose frequency calculated for the left and right edges exceeds a prescribed threshold and matches within prescribed error limits between the two distances as the distance between said input image and said reference image in the horizontal direction.

16. An apparatus for matching an input image with a reference image by determining the positions of various portions in said input image corresponding to various portions of said reference image, comprising:

search range determining means for determining for each of a plurality of small blocks into which said reference image is divided, a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

storage means for storing said small blocks together with the search range for each small block; and

searching means for searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks, wherein said searching means includes;

reference edge image generating means for generating in advance a reference edge image by extracting an edge of said reference image,

input edge image generating means for generating an input edge image by extracting an edge of said input image,

frequency calculating means for calculating the frequency of a distance between each of the pixels forming the edge of said input edge image and each of the pixels forming the edge of said reference edge image when said reference edge image is superimposed at an estimated corresponding position of said input edge image, and

distance determining means for determining the corresponding position by determining the distance whose calculated frequency exceeds a prescribed threshold as the distance between said input image and said reference image.

18. An apparatus according to claim 16, wherein said searching further includes:

means for detecting a straight edge line running in one of a vertical direction and a horizontal direction in said reference image; and

means for replacing a position of said extracted edge in said reference edge image by an intercept value of said detected straight edge line before the frequency calculation by said frequency calculating means, when said extracted edge corresponds to said detected straight edge line.

19. An apparatus for recognizing filled-in characters from an input image generated from a form sheet filled out with characters, comprising:

dividing means for dividing in advance a reference image generated from a blank form sheet into a plurality of small blocks;

search range determining means for determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

storage means for storing said small blocks together with the search range for each small block;

searching means for searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks wherein said searching means determines a search priority of each small block on a count of pixels of a specified type contained in the small block;

entry region determining means for determining a character entry region in said input image corresponding to a prestored entry region on the basis of the corresponding positions determined by said searching means; and

means for recognizing a character from an image within the character entry region determined by said entry region determining means in said input image.

20. An apparatus for recognizing filled-in characters from an input image generated from a form sheet filled out with characters, comprising:

dividing means for dividing in advance a reference image generated from a blank form sheet into a plurality of small blocks;

search range determining means for determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

storage means for storing small blocks together with the search range for each small block;

searching means for searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks wherein said searching means determines a search priority of each small block on a count of pixels of a specified type contained in the small block and useful for performing the matching;

means for stripping said input image of portions corresponding to said reference image on the basis of the corresponding position determined for each small block; and

means for recognizing characters from said input image that has been stripped of portions corresponding to said reference image.

21. An apparatus for detecting a mismatching portion between a first image and a second image, comprising:

search range determining means for determining, for each of a plurality of small blocks into which said first image is divided, a search range over which the second image is to be searched for a portion corresponding thereto in said second image;

storage means for storing said small blocks together with the search range for each small block;

searching means for searching said second image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said second image, of the portions corresponding to said small blocks wherein said searching means determines a search priority of each small block on a count of pixels of a specified type contained in the small block;

means for stripping said second image of portions corresponding to said first image on the basis of the corresponding position determined for each small block;

means for grouping pixels remaining in said second image that has been stripped of said portions corresponding to first image; and

means for determining a pixel group as representing a mismatching portion if the number of pixels arranged as belonging to said group exceeds a prescribed value.

22. An apparatus for printing characters on a form sheet, comprising:

dividing means for dividing in advance a reference image generated from a reference form sheet into a plurality of small blocks;

search range determining means for determining for each small block a search range over which an input image is to be searched for a portion corresponding thereto in the input image generated from a form sheet to be printed with characters;

storage means for storing small blocks together with the search range for each small block;

searching means for searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks wherein said searching means determines a search priority of each small block on a count of pixels of a specified type contained in the small block;

printing position determining means for determining a printing position in said input image corresponding to a prestored printing position on the basis of the corresponding positions determined by searching means; and

means for printing characters on the form sheet to be printed with characters, in accordance with the printing position determined by said printing position determining means.

23. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for matching an input image with a reference image by determining the positions of various portions in said input image corresponding to various portions of said reference image, said method steps comprising:

(a) dividing in advance said reference image into a plurality of small blocks;

(b) determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

(c) storing said small blocks together with the search range for each small block; and

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks, a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block.

24. A program storage device according to claim 23, further comprising the step of (e) correcting, during the execution of said step (d), the search priority and search ranges for small blocks whose corresponding positions in said input image have not yet been determined, on the basis of the corresponding positions in said input image for the small blocks for which such positions have already been determined.

25. A program storage device according to claim 24, wherein in said step (a), said reference image is divided into a plurality of medium blocks each consisting of a plurality of small blocks, and

said step (e) includes the substeps of:

(i) calculating, for a medium block having more than a prescribed number of small blocks whose corresponding positions have already been determined, the values of transformation parameters for the entire medium block from the already determined corresponding positions of the small blocks in said medium block;

(ii) determining from said calculated values of transformation parameters the search range for each of the small blocks in said medium block whose corresponding positions have not yet been determined;

(iii) estimating from the values of transformation parameters calculated in said substep (i) the values of transformation parameters for a medium block not having more than the prescribed number of small blocks whose corresponding positions have already been determined; and

(iv) determining from said estimated values of transformation parameters the search range for each of the small blocks in said medium block that does not have more than the prescribed number of small blocks whose corresponding positions have already been determined.

26. A program storage device according to claim 23, wherein in said step (d), the degree of skewness of said input image relative to said reference image is estimated on the basis of the small blocks whose corresponding positions have already been determined, and the determination of the positions in said input image, of the portions corresponding to said small blocks is corrected on the basis of the value of said estimated degree of skewness.

27. A program storage device according to claim 23, wherein said step (d) includes the substeps of:

(i) generating in advance a reference edge image by extracting an edge of said reference image;

(ii) generating an input edge image by extracting an edge of said input image;

(iii) calculating the frequency of a distance between each of the pixels forming the edge of said input edge image and each of the pixels forming the edge of said reference edge image when said reference edge image is superimposed at an estimated corresponding position of said input edge image; and

(iv) determining the corresponding position by determining the distance whose calculated frequency exceeds a prescribed threshold as the distance between said input image and said reference image.

28. A program storage device according to claim 27, wherein said substep (i) includes the substep of generating a reference upper edge image, a reference lower edge image, a reference left edge image, and a reference right edge image by extracting upper, lower, left, and right edges, respectively, in said reference image,

said substep (ii) includes the substep of generating an input upper edge image, an input lower edge image, an input left edge image, and an input right edge image by extracting upper, lower, left, and right edges, respectively, in said input image,

said substep (iii) includes the substep of calculating the frequencies of distances in vertical direction between each of the pixels forming said input upper and lower edge images and each of the pixels forming said reference upper and lower edge images, respectively, and of distances in horizontal direction between each of the pixels forming said input left and right edge images and each of the pixels forming said reference left and right edge images, respectively, when said input upper edge image, said input lower edge image, said input left edge image, and said input right edge image are superimposed on said reference upper edge image, said reference lower edge image, said reference left edge image, and said reference right edge image, respectively, and

said substep (iv) includes the substeps of

determining the distances whose frequency calculated for the upper and lower edges exceeds a prescribed threshold and matches within prescribed error limits between the two distances as the distance between said input image and said reference image in the vertical direction, and

determining the distances whose frequency calculated for the left and right edges exceeds a prescribed threshold and matches within prescribed error limits between the two images as representing the distance between said input image and said reference image in the horizontal direction.

29. A program storage device according to claim 27, wherein said step (d) further includes the substeps of:

(v) detecting straight edge line running in one of a vertical direction and a horizontal direction in said reference image; and

(vi) when the edge extracted in substep (i) corresponds to the straight edge line detected in said substep (v), replacing a position of the edge in said reference edge image by an intercept value of said straight edge line before performing said substep (iii).

30. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for recognizing filled-in characters from an input image generated from a form sheet filled out with characters, said method steps comprising:

(a) dividing in advance a reference image generated from a blank form sheet into a plurality of small blocks;

(b) determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

(c) storing said small blocks together with the search range for each small block;

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block;

(e) determining a character entry region in said input image corresponding to a prestored entry region on the basis of the corresponding positions determined in said step (d); and

(f) recognizing a character from an image within the character entry region determined in said step (e) in said input image.

31. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for recognizing filled-in characters from an input image generated from a form sheet filled out with characters, said method steps comprising:

(a) dividing in advance a reference image generated from a blank form sheet into a plurality of small blocks;

(b) determining for each small block a search range over which the input image is to be searched for a portion corresponding thereto in said input image;

(c) storing said small blocks together with the search range for each small block;

(d) searching said input image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said input image, of the portions corresponding to said small blocks a search priority of each small block being determined of pixels of a specified type contained in the small block;

(e) stripping said input image of portions corresponding to said reference image on the basis of the corresponding position determined for each small block; and

(f) recognizing characters from said input image that has been stripped of portions corresponding to said reference image in said step (e).

32. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for detecting a mismatching portion between a first image and a second image, said method steps comprising:

(a) dividing in advance said first image into a plurality of small blocks;

(b) determining for each small block a search range over which the second image is to be searched for a portion corresponding thereto in said second image;

(c) storing said small blocks together with the search range for each small block;

(d) searching said second image within said search ranges for portions corresponding to said small blocks, to determine the positions, in said second image, of the portions corresponding to said small blocks a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block;

(e) stripping said second image of portions corresponding to said first image on the basis of the corresponding position determined for each small block;

(f) grouping pixels remaining in said second image that has been stripped of said portions corresponding to first image in said step (e); and

(g) determining a pixel group as representing a mismatching portion if the number of pixels arranged in said step (f) as belonging to said group exceeds a prescribed value.

33. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for printing characters on a form sheet, said method steps comprising:

(a) dividing in advance a reference image generated from a reference form sheet into a plurality of small blocks;

(b) determining for each small block a search range over which an input image is to be searched for a portion corresponding thereto in the input image generated from a form sheet to be printed with characters;

(c) storing said small blocks together with the search range for each small block;

(d) searching said input image within said search ranges for portions corresponding to said small blocks to determine the positions, in said input image, of the portions corresponding to said small blocks a search priority of each small block being determined based on a count of pixels of a specified type contained in the small block;

(e) determining a printing position in said input image corresponding to a prestored printing position on the basis of the corresponding positions determined in said step (d); and

(f) printing characters on the form sheet to be printed with characters, in accordance with the printing position determined in said step (e).