JP3763966B2 - Image recognition method, apparatus and recording medium - Google Patents

Description

[0001]
BACKGROUND OF THE INVENTION
The present invention relates to an image recognition method, apparatus, and recording medium that accurately extract a predetermined pattern from an input document image.
[0002]
[Prior art]
Various methods have been proposed as image recognition methods for color images. For example, the present applicant needs to perform image recognition when performing color image recognition processing on a color image, in particular, a pattern in which an image to be extracted is drawn according to a predetermined rule. A color image recognition method has been proposed that recognizes an object at high speed by compressing the amount of data without affecting the rotation while ensuring a large amount of information (see Japanese Patent Laid-Open No. 8-263661).
[0003]
[Problems to be solved by the invention]
However, in the image recognition method described above, since the distance between the basic marks (elements) is used to determine whether the pattern is a recognition target pattern, for example, as shown in FIG. 7, each basic mark (A1, A2) is determined. ) Cannot be extracted with inverted patterns (B1, B2) having the same distance.
[0004]
An object of the present invention is to provide an image recognition method, apparatus, and recording medium that can identify an inverted pattern by using a distance between basic marks and a vector outer product.
[0005]
[Means for Solving the Problems]
In order to achieve the above object, according to the first aspect of the present invention, a predetermined element is extracted from the input document image, a predetermined pattern composed of the plurality of extracted elements is extracted, and the extracted pattern is extracted. An image recognition method for recognizing whether or not the input document image is a predetermined document image based on the pattern, and using the extracted one element as a reference, between the reference element and another element. The distance is obtained, the distance is checked against the dictionary, the element that matches the first distance in the dictionary is element 1, the element that matches the second distance in the dictionary is element 2, and the element 1 and element the distance between the 2 (hereinafter, a third distance) is obtained, further the vector from the reference element to the element 1, to the element 2 from the reference element Obtains an outer product of a vector, when the third distance and the outer product is consistent with the value of the dictionary, the reference element, the element 1, the configuration pattern from the element 2, extracting a predetermined pattern It is characterized by.
[0006]
The invention according to claim 2 is characterized in that an inverted pattern is identified based on the outer product.
[0007]
According to the third aspect of the present invention, an element extracting means for extracting a predetermined element from the input document image, a dictionary in which the distance between the elements and the vector outer product are registered, and the predetermined element composed of the plurality of extracted elements. of a pattern extracting means for extracting a pattern, the input document image based on the extracted pattern is an image recognition apparatus recognizes whether a predetermined document image, said pattern extraction means, said Using one extracted element as a reference, a distance between the reference element and another element is obtained, the distance is compared with the dictionary, and an element that matches the first distance in the dictionary is element 1, The element that matches the second distance in the dictionary is element 2, and the distance between the element 1 and element 2 (hereinafter referred to as the third distance) is obtained. Further the vector to the element 1 from the reference element, obtains the outer product of the vector to the element 2 from the reference element, when the third distance and the outer product is consistent with the value of the dictionary, the reference A pattern composed of elements, element 1 and element 2 is extracted as the predetermined pattern.
[0008]
The invention described in claim 4 is a computer-readable recording medium recording a program for causing a computer to realize the image recognition method described in claim 1 or 2.
[0009]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings.
<Example 1>
FIG. 1 shows the configuration of an embodiment of the present invention. In the figure, 1 is an image input unit that optically reads a document to be recognized and the like, 2 is an image binarization unit that creates a binarized image from a color image input by the image input unit, and 3 is from a binarized image. Basic element extraction unit for extracting basic elements (basic marks in the above-mentioned publication), 4 is a memory for storing the coordinates of basic elements, 5 is a dictionary in which distances between elements and vector outer products are registered, and 6 is a plurality of basic elements A basic pattern extracting unit for extracting a basic pattern, 7 a memory for storing element candidates, 8 a determining unit for determining whether or not an input document is a recognition target document based on the extracted basic pattern, and 9 for determining It is an output part which outputs a result.
[0010]
FIG. 2 shows an example of a document to be certified and a basic pattern example thereof. As shown in FIG. 2, the present embodiment will be described by taking as an example a case where a repetitive pattern printed on the entire surface of the recognition target document 21 such as a ticket is detected and recognized. Further, the basic pattern 23 constituting the repetitive pattern will be described by taking, as an example, a pattern having a basic element (black circle) 22 at each vertex of a triangle indicated by a broken line in the drawing.
[0011]
First, the image binarization unit 2 excludes a character portion that is not a repetitive pattern to be detected in the example of the document in FIG. 2 (for example, extracts pixels having a value equal to or greater than a predetermined threshold), and repeats the pattern. Only binary images are generated.
[0012]
Next, the basic element extraction unit 3 extracts basic elements (black circles in this example) using the method described in the image recognition method of the above-mentioned publication. In the example of FIG. 2, elements 0, 1, and 2 are extracted. The basic element coordinate position extracted here (for example, the coordinate position x0, y0 of the element 0) is stored in the basic element coordinate storage memory 4.
[0013]
The basic pattern extraction unit 6 sequentially reads out the coordinate positions of the basic elements stored in the basic element coordinate storage memory 4 and determines whether or not a condition as a basic pattern is satisfied. An example of the basic pattern will be described with reference to FIG. 2. The basic pattern 23 is a triangle composed of three elements 0, 1, and 2. The distance between element 0 and element 1 is r1, and the distance between element 0 and element 2 is as follows. Is r2, and the distance between element 1 and element 2 is r3. Here, first, assuming that one basic element in the triangular basic pattern is a reference element (element 0 in FIG. 2), the determination is performed by using the distance from other basic elements and the vector outer product.
[0014]
FIG. 3 is a flowchart of basic pattern determination processing. First, the basic pattern extraction unit 6 reads the coordinates of an unprocessed basic element (= target element) from the memory 4 that stores the coordinates of the basic element, and assumes that this is the reference element (= element 0) (step 0). 101).
[0015]
Next, element 1 and 2 candidates for element 0 are searched (step 102). When the distance between the element 0 candidate of interest and other elements in the vicinity of the candidate is obtained, the distance is compared with the dictionary 5 and matches the distance in the dictionary (or the distance is within a predetermined range). The element number is added to the candidate list in the element candidate storage memory 7 as a candidate for that element.
[0016]
FIG. 4 shows an example of searching for element candidates. In the figure, circle numbers 0 to 10 are extracted basic elements, which are element numbers 0 to 10, respectively. If the element 0 candidate of interest is now element number 5, element numbers 7 and 8 that match the distance r1 in the dictionary centered on the element of interest and element numbers 1 and 10 that match the distance r2 are selected as element candidates. . Thus, the element 1 candidate group (element numbers 7 and 8) and the element 2 candidate group (element numbers 1 and 10) when the element of interest is element 0 are determined and written to the element candidate storage memory 7.
[0017]
If there are element candidates in all of the elements 1 and 2 (step 103), the process proceeds to the next step 104 because there is a possibility of a basic pattern. If there is no element candidate, it is determined that the pattern is not a basic pattern, and the process returns to step 101 to move to the next element 0 candidate (element number 6 in the example of FIG. 4).
[0018]
Focusing on one element of the element 1 candidate group (step 104), assuming that this is element 1, search for element 2 is performed (step 105). FIG. 5 shows a first search example of element 2. Element number 7 is selected as element 1 candidate 1 from the element 1 candidate group. Then, the distance between element number 7 and element number 1 which is a candidate for element 2 and the distance between element number 7 and element number 10 which is a candidate for element 2 are obtained.
[0019]
Further, an outer product of a vector from the element 0 candidate (element number 5) to the element 1 candidate (element number 7) and a vector from the element 0 candidate to the element 2 candidate (element number 1), and an element 0 candidate (element number) The outer product of the vector from 5) to the element 1 candidate (element number 7) and the vector from the element 0 candidate to the element 2 candidate (element number 10) is obtained.
[0020]
Here, the outer product is (X1-X0) where the coordinates of the element 0 candidate are (X0, Y0), the coordinates of the element 1 candidate are (X1, Y1), and the coordinates of the element 2 candidate are (X2, Y2). * (Y2-Y0)-(X2-X0) * (Y1-Y0).
[0021]
A supplementary explanation will be given with reference to FIG. 7 that the vector cross product is effective in determining the inversion pattern. Considering the point A (A1, A2) and the point B (B1, B2) that are in the reverse positions with respect to the origin O, the conventional determination method using only the distance cannot identify both. However, using vector cross product,
The outer product of the vectors A1 and A2 is (X1-X0) * (Y2-Y0)-(X2-X0) * (Y1-Y0),
The outer product of the vectors B1 and B2 is (-X1-X0) * (Y2-Y0)-(-X2-X0) * (Y1-Y0) =-{(X1 + X0) * (Y2-Y0)-(X2 + X0) * (Y1-Y0)}. Here, if X0 = 0 and Y0 = 0,
The outer product of the vectors A1 and A2 is X1Y2-X2Y1
The outer product of the vectors B1 and B2 is-(X1Y2-X2Y1)
Since the sign is inverted, the point A and the point B at the inversion position can be identified.
[0022]
Compare both the distance and the vector cross product obtained as described above with the dictionary 5, and when both match the values in the dictionary, or when the values are within a predetermined range (step 106), pay attention. Assuming that element 2 for element 0 and element 1 exist, a flag is set and the element number is stored (step 107). In other words, if the flag is set, there is a possibility that the elements 1 and 2 exist at a predetermined position with respect to the element 0 of interest, and a pattern including these elements is detected as a basic pattern. It will be. When all the elements have not been processed, the processing is transferred to the next element 1 candidate (step 104).
[0023]
In the example of FIG. 5, the distance between element number 7 and element number 1 and the distance between element number 7 and element number 10 centering on element number 7 which is element 1 candidate 1 do not satisfy the condition of r3 in the dictionary. (Step 106), proceeding to Step 108 and Step 104, the element number 8 is selected as the next element 1 candidate 2 from the element 1 candidate group.
[0024]
As shown in FIG. 6, the distance between element numbers 8-1 and the distance between element numbers 8-10 are obtained centering on element number 8 as in FIG. Further, an outer product of a vector from the element 0 candidate (element number 5) to the element 1 candidate (element number 8) and a vector from the element 0 candidate to the element 2 candidate (element number 1), and an element 0 candidate (element number) The outer product of the vector from 5) to the element 1 candidate (element number 8) and the vector from the element 0 candidate to the element 2 candidate (element number 10) is obtained.
[0025]
In the example of FIG. 6, when the distance between the element numbers 8 and 1 and the outer product thereof both match the values in the dictionary 5 or when the values are within a predetermined range (step 106), the element number 1 Becomes an element 2 candidate. Since there is element 2 (element number 1) for element 0 (element number 5) and element 1 (element number 8) of interest, a flag is set and the element numbers (5, 8, 1) are set. And stored in the element candidate storage memory 7 (step 107). As a result, a pattern composed of element numbers (5, 8, 1) for which a flag is set is detected as a basic pattern. The basic pattern extraction unit 6 performs the above processing on all elements. The determination unit 8 reads out the basic pattern extracted as described above from the element candidate storage memory 7, and uses a condition such that the number of the basic patterns is equal to or greater than a predetermined number in the target document to determine whether the document is a recognition target document. The determination result is output to the output unit 9.
[0026]
<Example 2>
FIG. 8 shows an embodiment when the present invention is realized by software. When the present invention is realized by software, as shown in FIG. 8, a computer system including a CPU, a memory, a display device, a hard disk, a keyboard, a CD-ROM drive, a scanner, etc. is prepared, and a computer such as a CD-ROM is prepared. On the readable recording medium, a program for realizing the image recognition function of the present invention, a dictionary, and the like are recorded. A document image to be processed is stored in a hard disk or the like. When the program is started, the original image data is read, image recognition processing is executed, and the recognition result is output to a display or the like.
[0027]
【The invention's effect】
As described above, according to the present invention, the predetermined pattern composed of the reference element and the other element is extracted based on the distance between the reference element and the other element and the vector outer product. The predetermined pattern can be recognized with high accuracy, and the inverted pattern can be identified.
[Brief description of the drawings]
FIG. 1 shows a configuration of an embodiment of the present invention.
FIG. 2 shows an example of a document to be certified and an example of its basic pattern.
FIG. 3 is a process flowchart of basic pattern determination.
FIG. 4 shows an example of searching for element candidates.
FIG. 5 shows a first search example of element 2;
FIG. 6 shows a second search example of element 2;
FIG. 7 is a diagram for explaining that a vector cross product is effective in determining an inversion pattern.
FIG. 8 shows a configuration example when the present invention is realized by software.
[Explanation of symbols]
DESCRIPTION OF SYMBOLS 1 Image input part 2 Image binarization part 3 Basic element extraction part 4 Basic element coordinate storage memory 5 Dictionary 6 Basic pattern extraction part 7 Element candidate storage memory 8 Judgment part 9 Output part

Claims (4)

A predetermined element is extracted from the input document image, a predetermined pattern composed of the extracted elements is extracted, and the input document image is a predetermined document image based on the extracted pattern. An image recognition method for recognizing whether or not an extracted element is used as a reference, a distance between the reference element and another element is obtained, the distance is compared with a dictionary, The element matching the first distance is element 1, the element matching the second distance in the dictionary is element 2, and the distance between the element 1 and element 2 (hereinafter referred to as the third distance) is obtained. and a vector from the reference element to the element 1, obtains an outer product of a vector from the reference element to the element 2, the third distance and the cross product is pre When match the value of the dictionary, the image recognition method, characterized in that said reference element, the element 1, the configuration pattern from the element 2 is extracted as the predetermined pattern.   The image recognition method according to claim 1, wherein an inverted pattern is identified based on the outer product. Element extraction means for extracting predetermined elements from the input document image, a dictionary in which distances between elements and vector outer products are registered, and pattern extraction means for extracting a predetermined pattern composed of the plurality of extracted elements with the door, the input document image based on the extracted pattern is an image recognition apparatus recognizes whether a predetermined document image, said pattern extraction means, based on the one of the elements the extracted The distance between the reference element and another element is obtained, the distance is checked against the dictionary, the element that matches the first distance in the dictionary is element 1, and the second distance in the dictionary elements that match the element 2, the distance between the element 1 and the element 2 (hereinafter, the third distance) seeking further the reference elementary And vector to the element 1 from obtains an outer product of a vector from the reference element to the element 2, when the third distance and the outer product is consistent with the value of the dictionary, the reference element, the element 1 An image recognition apparatus that extracts a pattern composed of elements 2 as the predetermined pattern.   A computer-readable recording medium on which a program for causing a computer to realize the image recognition method according to claim 1 or 2 is recorded.

Images