Method for matching input image with reference image, apparatus for the same, and storage medium storing program for implementing the method
First Claim
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 Assignments
0 Petitions
Accused Products
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.
101 Citations
33 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (6, 7)
-
-
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. - View Dependent Claims (13, 14, 15, 17)
-
-
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. - View Dependent Claims (18)
-
-
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. - View Dependent Claims (24, 25, 26, 27, 28, 29)
-
-
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).
-
Specification