JPH11120288A - Shift detecting method for image - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a method for detecting a shift of an image when an image process for a general document is performed. SOLUTION: An image reduction part 1 generates a reduced image S1 of an image A. A lateral black run histogram generation part 2 generates a lateral black run histogram S2. A rough longitudinal feature extraction part 4 extracts a rough longitudinal feature quantity S4. A fine longitudinal feature extraction part 6 extracts a fine longitudinal feature quantity S6. Similarly, a rough lateral feature quantity S5 and a fine lateral feature quantity S7 are extracted. A position feature quantity recording part 8 records the rough longitudinal feature quantity S4, fine longitudinal feature quantity S6, rough lateral feature quantity S5, and fine lateral feature quantity S7. The image reduction part 11 generates a reduced image S11 of an image B. A lateral black run histogram generation part 12 generates a lateral black run histogram S12. A longitudinal shift temporary detection part 14 generates a temporarily detected value S14 of the longitudinal shift. A longitudinal shift detection part 16 outputs the detected value S16 of the longitudinal shift. Similarly, the detected value S17 of the lateral shift between the images A and B is outputted from a lateral shift detection part 17.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for detecting a mutual shift between a plurality of document images of the same format, which is used, for example, in an apparatus for processing a document image in a table format.

[0002]

2. Description of the Related Art Conventionally, techniques in such a field include:
For example, there is one described in the following literature. Literature; edited by Hashimoto Shinichiro, Introduction to Character Recognition, First Edition, 57.3.2
0 Publication, Telecommunications Association, P.199-204 In order to perform processing such as character recognition on the image of the document described in the form, cut out character lines and characters based on the information on the format of the document. Perform character recognition processing. In this case, set a specific reference point on the form,
Specify the position of the field from which you want to read characters. For example, as described in the above-mentioned document, the position of the reading field is set with reference to a specific side of the form or with a specially provided reference mark as a reference point,
A character recognition process is performed on the read field using an optical character recognition device (hereinafter, referred to as OCR).

[0003]

However, setting the position of the read field in the conventional character recognition processing has the following problems. When the position of the side of the form or the like can be specified by using a scanner and a form created exclusively for the OCR, the conventional setting method of the position of the reading field is used. Use a general-purpose scanner whose position cannot be specified, or use an OC
There is an increasing demand for processing general-purpose forms that do not assume the use of R. However, when a document image of a form is read using a general-purpose scanner, the position of the side of the form cannot be specified, and the position of the document in the document image may be shifted with respect to the reading field of the scanner. It is difficult to determine the position of the side of the form and match the position of the take-out field. Also, in general-purpose forms,
There is no reference mark provided on the OCR-dedicated form.
Therefore, when a general-purpose scanner is used or a general-purpose form is processed, an image in which the format information of the general-purpose form is set and an image that needs to be processed using the information of the format are used. There has been a problem that it is necessary to detect a shift between the general-purpose forms and correct the shift.

[0004]

According to another aspect of the present invention, there is provided a method for detecting a displacement of an image, comprising a table represented by a ruled line at a reference position. An image of a first document in which a first document is described is converted into an electric signal to create a first image. And a first image reduction process for reducing the first image at a predetermined reduction rate to generate a first reduced image; and a predetermined first length in the horizontal direction in the first reduced image. For a black run composed of continuous black pixels as described above, a first horizontal black run histogram in which the number of the black pixels is totaled in the horizontal direction is created for each horizontal scanning line. Black run histogram creation processing, and for a black run composed of black pixels that are continuous in the first reduced image in a vertical direction for a predetermined second length or more, the number of the black pixels is calculated in the vertical direction. A first vertical black run / histogram creating process for creating the first vertical black run / histogram totalized for each vertical scanning line; and one or more peaks on the first horizontal black run / histogram Vertical feature that extracts the vertical position and size of the image as coarse vertical features An extraction process, a coarse / horizontal feature extraction process for extracting a horizontal position and a size of one or a plurality of peaks on the first vertical black run histogram as a coarse horizontal feature, For each of the peaks extracted as the characteristic amounts of the above, the number of black pixels on each of the horizontal scanning lines in a portion corresponding to the position of each of the peaks in the first image is counted. And a fine vertical feature value extraction process of extracting the position of each of the peaks as a fine vertical feature value of each of the peaks, and for each of the peaks extracted as the coarse horizontal feature value of each of the peaks of the first image. Count the black pixels on each vertical scanning line of the part corresponding to the position,
A fine horizontal feature value extraction process of extracting the position of the scanning line at which the count value becomes the maximum as a fine horizontal feature value at each peak is performed.

Further, an image of a second document in which a second document whose positional deviation from the position of the first document needs to be detected is described in a table of the same format as that of the first document, and the A second image is created by signalization. And a second image reduction process for reducing the second image at the same reduction rate as the first image reduction process to generate a second reduced image; and a horizontal direction in the second reduced image. A black run composed of black pixels continuous for a predetermined third length or more,
A second horizontal black run histogram creating process for creating a second horizontal black run histogram in which the number of the black pixels is totaled in the horizontal direction for each horizontal scanning line; For a black run composed of black pixels that are continuous for a predetermined fourth length or more in the vertical direction, a second vertical black run histogram in which the number of the black pixels is totaled in the vertical direction is calculated in the vertical direction. A second vertical black run / histogram generation process for each scanning line, and a plurality of predetermined positions Yi (i = 1, 2,..., N) of a plurality of peak positions of the coarse vertical feature amount. The second horizontal black run histogram is compared with the second horizontal black run histogram in the vertical direction in the shifted state, and the predetermined value Yk when the difference is the smallest is generated as a temporary vertical deviation detection value. Predetermined values Xi (i = 1, 2) in which a plurality of peak positions of the directional feature amount are prepared. ,..., N), the second vertical black run histogram is compared with the second vertical black run histogram in the horizontal direction, and the predetermined value Xk when the difference is the smallest is generated as a temporary lateral displacement detection value; For each peak of the coarse vertical feature amount, the number of black pixels in the second image portion corresponding to a position obtained by shifting the position of each peak by the vertical shift tentative detection value Yk is shown in each horizontal scanning line. For
The difference between the position of the scanning line when the count value is the largest and the position of the scanning line corresponding to each of the peaks recorded as the fine vertical feature amount is calculated, and the average value of each difference is calculated. A vertical displacement detection process for detecting a vertical displacement of the second image with respect to the first image, and for each peak of the coarse horizontal feature amount, the position of each peak is calculated by the lateral displacement temporary detection value Xk. The second position corresponding to the shifted position
The number of black pixels in the image portion is counted for each scanning line in the vertical direction, and the number of black pixels corresponding to the position of the scanning line when the count value is the largest and each of the peaks recorded as the fine horizontal feature amount And a vertical deviation detection process for detecting the average of the respective differences as a lateral deviation of the second image with respect to the first image. By combining the vertical displacement of the second image with respect to the first image and the lateral displacement of the second image detected by the lateral displacement detection processing with respect to the first image, The first of the second document
And a displacement detection process for detecting a displacement of the document from the position of the document.

By employing such a configuration, in the first image reduction processing, the first image is reduced at a predetermined reduction ratio to generate a first reduced image. In a first horizontal black run / histogram creation process, for a horizontal black run in the first reduced image, a first histogram in which the black run is projected in the horizontal direction is created for each horizontal scan line. Is done. In the first vertical black run / histogram creation process, for a vertical black run in the first reduced image, a second histogram obtained by projecting the black run in the vertical direction is generated for each vertical scan line. Created. In the coarse vertical feature amount extraction processing, the vertical position and size of one or more peaks on the first histogram are extracted as coarse vertical feature amounts. In the coarse horizontal feature value extraction processing, the horizontal position and magnitude of one or more peaks on the second histogram are extracted as coarse horizontal feature values. In the fine vertical feature value extraction process, the first peak extracted as the coarse vertical feature value is subjected to the first
The black pixels on each scanning line in the horizontal direction of the portion corresponding to the position of each peak of the image are counted, and the position of the scanning line at which the counted value is the maximum is a fine vertical feature amount at each peak. Is extracted as In the fine horizontal feature amount extraction processing, for each peak extracted as the coarse horizontal feature amount, the number of black pixels on each vertical scanning line in a portion corresponding to the position of each peak in the first image is counted. Then, the position of the scanning line at which the count value becomes maximum is extracted as a fine horizontal feature amount at each peak.

In the second image reduction processing, the second image is reduced at the same reduction ratio as in the first image reduction processing to generate a second reduced image. In the second horizontal black run / histogram creation process, for a horizontal black run in the second reduced image, a third histogram obtained by projecting the black run in the horizontal direction is generated for each horizontal scan line. Created.
In the second vertical black run / histogram creation processing, for the vertical black run in the second reduced image, a fourth histogram in which the black run is projected in the vertical direction is created for each vertical scan line. Is done. In the vertical displacement tentative detection processing, the position of each peak of the coarse vertical feature amount is determined by a predetermined value Yi (i
= 1, 2,..., N), the respective histograms forming the respective peaks and the third histogram are compared in the vertical direction, and the predetermined value Yk when the difference is the smallest is determined as the vertical deviation temporary. Generated as a detection value. In the lateral displacement temporary detection processing, the histograms forming the respective peaks in a state where the positions of the respective peaks of the coarse lateral feature amount are shifted by a predetermined value Xi (i = 1, 2,... Is compared in the horizontal direction, and the predetermined value Xk at the time when the difference is the smallest is generated as a temporary displacement detection value.

In the vertical displacement detection processing, for each peak of the coarse vertical feature amount, the black of the portion of the second image corresponding to a position where the position of each peak is shifted by the vertical displacement temporary detection value Yk. The number of pixels is counted for each scanning line in the horizontal direction, the position of the scanning line when the count value is the largest, and the position of the scanning line corresponding to each peak recorded as the fine vertical feature amount. The difference of each is taken,
The average value of the differences is detected as a vertical displacement of the second image with respect to the first image. In the lateral displacement detection process, for each peak of the coarse lateral feature amount, the number of black pixels in the portion of the second image corresponding to a position where the position of each peak is shifted by the temporary lateral displacement temporary detection value Xk is increased in the vertical direction. Is counted for each scanning line, and the difference between the position of the scanning line when the count value is the largest and the position of the scanning line corresponding to each peak recorded as the fine horizontal feature amount is respectively The average value of the differences is detected as a lateral shift of the second image with respect to the first image. In the displacement detection process, a vertical displacement of the second image detected in the vertical displacement detection process with respect to the first image, and a first displacement of the second image detected in the lateral displacement detection process. The displacement in the horizontal direction with respect to the image is combined, and the displacement of the second image with respect to the first image is detected, and the displacement of the second document with respect to the position of the first document is detected.

According to a fifth aspect of the present invention, in the case where the number of peaks extracted in the rough vertical feature amount extraction processing according to the second aspect of the present invention is equal to or less than a predetermined number, the first The length value is corrected to a small value, and the first horizontal black run histogram creation process is performed a required number of times again. The first length when the number of the peaks becomes larger than the predetermined number is obtained. And a horizontal black run threshold value correction process for recording the value of the horizontal black run threshold value as a horizontal black run threshold value. 2 is corrected to a smaller value, and the second vertical black run / histogram creation processing is performed a required number of times again. When the number of the peaks becomes larger than the predetermined number, the second length is calculated. Black run threshold correction processing to record the value of Do. Then, the horizontal black run threshold is used as the predetermined third length in the second horizontal black run / histogram creation processing, and the predetermined fourth length in the second vertical black run / histogram creation processing is used. The vertical black run threshold is used as the length.

By adopting such a configuration, when the number of peaks extracted in the rough vertical feature amount extraction processing is equal to or smaller than a predetermined number, the first length is corrected in the horizontal black run threshold correction processing. Is corrected to a small value, the first horizontal black run histogram creation process is performed a required number of times again, and the value of the first length when the number of peaks becomes larger than the predetermined number Is recorded as the horizontal black run threshold.
If the number of peaks extracted in the coarse / horizontal feature extraction processing is equal to or less than a predetermined number, the value of the second length is corrected to be small in the vertical black run threshold correction processing, and the second vertical A black run histogram creation process is performed a required number of times, and the value of the second length when the number of the peaks becomes larger than the predetermined number is recorded as a vertical black run threshold. Then, the horizontal black run threshold is used as a predetermined third length in the second horizontal black run / histogram creation processing, and the horizontal black run threshold is used as the predetermined fourth length in the second vertical black run / histogram creation processing. A vertical black run threshold is used. Therefore, even if the first document is a document of a style composed of short ruled lines, a coarse vertical feature, a coarse horizontal feature, a fine vertical feature, and a fine horizontal feature are provided. The quantity is extracted. Therefore, the above problem can be solved.

[0011]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS First Embodiment FIG. 1 is a block diagram of an image shift detecting device for implementing an image shift detecting method according to a first embodiment of the present invention.
The image shift detecting apparatus includes an image reducing unit 1 that reduces a first image A at a predetermined rate to create a reduced image S1 having a reduced resolution. The image A is a form in which a document serving as a position reference, such as a document at the time of registration of format information, is converted into an electric signal by an optical method or the like. On the output side of the image reduction unit 1, a horizontal black run / histogram creation unit 2 and a vertical black run / histogram creation unit 3
Is connected. Horizontal black run / histogram creation unit 2
In the reduced image S1, a black run in which black pixels are continuous for a predetermined length or more is detected for each scanning line in the horizontal direction, and the number of pixels constituting the black run is counted. -Create the histogram S2. The vertical black run / histogram creation unit 3 detects black runs in which black pixels continue for a predetermined length or more for each scanning line in the vertical direction for the reduced image S1, and detects pixels constituting the black runs. The number is counted to create the vertical black run histogram S3.

On the output side of the horizontal black run / histogram creation unit 2, one or more peaks are detected from the horizontal black run / histogram S2, and the position and magnitude of the peak are generated as a coarse / vertical feature amount S4. The vertical feature amount extraction unit 4 is connected. The rough vertical feature amount extraction unit 4 sets, for example, a range where the horizontal black run histogram S2 is equal to or more than a certain value as a peak, sets the sum of the count values of the histogram in this range as the size of the peak, and extracts the sum as the rough vertical feature amount S4. Is what you do. On the output side of the vertical black run / histogram creation unit 3, one or more peaks are detected from the vertical black run / histogram S3, and the position and magnitude of the peak are extracted as a coarse / horizontal feature S5. The extraction unit 5 is connected. For example, the coarse / horizontal feature extraction unit 5 sets a range where the vertical / black run histogram S3 is equal to or more than a certain value as a peak, sets the sum of the count values of the histogram in this range as the size of the peak, and generates the sum as the coarse / horizontal feature S5. Is what you do. On the output side of the coarse vertical characteristic amount extraction unit 4, a fine vertical characteristic amount extraction unit 6 is connected. The fine vertical feature amount extraction unit 6 counts the number of black pixels for each horizontal scanning line for the portion of the image A corresponding to each peak range of the coarse vertical feature amount S4, and the scanning line having the largest count value. Is extracted as the fine vertical feature amount S6 at the peak. On the output side of the coarse and horizontal feature amount extraction unit 5,
The fine horizontal feature quantity extraction unit 7 is connected. The fine horizontal feature amount extraction unit 7 counts the number of black pixels for each vertical scanning line in the portion of the image A corresponding to each peak range of the coarse horizontal feature amount S5, and the scanning line having the largest count value. Is extracted as the fine horizontal feature amount S7 at the peak. The output of the coarse / vertical feature extraction unit 4, the coarse / horizontal feature extraction unit 5, the fine / vertical feature extraction unit 6, and the fine / horizontal feature extraction unit 7 are respectively provided with a coarse / vertical feature S4, a coarse / horizontal feature. Quantity S5,
A position feature recording unit 8 that inputs the fine vertical feature S6 and the fine horizontal feature S7 and records them as the coarse vertical feature 8a, the coarse horizontal feature 8b, the fine vertical feature 8c, and the fine horizontal feature 8d, respectively. Is connected.

The image shift detecting apparatus further includes an image reducing unit 11 for reducing the second image B at a reduction rate similar to that of the image reducing unit 1 to create a reduced image S11 having a reduced resolution. I have. The image B is an optical form in which a document in which a deviation from the image A needs to be detected is described in order to specify the position of the processing target using the format information created on the image A. It is converted into an electric signal by a method or the like. On the output side of the image reducing unit 11, similarly to the horizontal black run / histogram creating unit 2 and the vertical black run / histogram creating unit 3, the horizontal black run / histogram creating unit 12 for creating the horizontal black run / histogram S12 and the vertical Vertical black run / histogram creation unit 1 for creating black run / histogram S13
3 are connected. Horizontal black run / histogram creation unit 1
The output side 2 is connected to a vertical displacement temporary detection unit 14. The vertical deviation temporary detection unit 14 determines a predetermined value Yi (i = 1, 2,
.., N) and the sum of the count values of the horizontal black run histogram S12 for the peak range and the coarse / vertical feature amount 8a
The absolute value of the difference from the peak size is calculated for each peak, and the sum thereof is used as the evaluation value. Then, Yk, which is one of the predetermined values Yi having the smallest evaluation value, is output as the temporary detection value S14 of the vertical displacement. On the output side of the vertical black run / histogram creation unit 13,
The temporary lateral displacement detection unit 15 is connected. The lateral deviation temporary detection unit 15 shifts the position of each peak of the coarse lateral characteristic amount 8b by a predetermined value Xi (i = 1, 2,..., N) prepared in advance,
Vertical black run histogram H13 for the peak range
, And the absolute value of the difference between the peak size of the coarse and horizontal feature quantity 8b is calculated for each peak, and the sum thereof is used as the evaluation value. Then, Xk, which is one of the predetermined values Xi having the smallest evaluation value, is output as a provisional detection value S15 of a lateral shift.

A vertical displacement detecting section 16 is connected to the output side of the vertical displacement temporary detecting section 14. The vertical shift detecting unit 16 shifts the position of each peak of the coarse vertical feature amount 8a by the tentative detection value S14 of the vertical shift (that is, Yk), and shifts each of the shifted peak ranges on the image B in the image B. The number of black pixels is counted for each scanning line in the direction, and the difference between the vertical position of the scanning line at which the count value is the largest and the value of the fine vertical feature value 8c corresponding to the peak position is calculated. Are output as the vertical deviation detection value S16. The output side of the provisional lateral displacement detection section 15 is connected to a lateral displacement detection section 17. The lateral shift detecting unit 17 shifts the position of each peak of the coarse and horizontal characteristic amount 8b by the temporary detected value S15 (ie, Xk) of the shift in the horizontal direction, and shifts each peak in the vertical direction on the image B for the range of the shifted peak. , The number of black pixels is counted for each scanning line, and the horizontal position of the scanning line at which the counted value is the largest, and the fine horizontal feature amount 8 corresponding to the peak position.
The difference from the value of d is taken, and the average value of all the peaks of this difference is output as the detected value S17 of the lateral shift. Each output side of the vertical shift detecting unit 16 and the horizontal shift detecting unit 17 synthesizes the detected value S16 and the detected value S17, and detects a position shift of the image B with respect to the image A.
8 is connected.

Next, the processing contents of the image shift detecting method in the image shift detecting apparatus of FIG. 1 will be described. First, the vertical position feature extraction processing (1) and the ruled line position comparison processing (2) will be described. (1) Position Feature Extraction Process FIGS. 2A, 2B, 2C, and 2D are diagrams illustrating an example of the position feature extraction process in the image displacement detection device of FIG. In this position feature extraction processing, the following (1-1)
Processing such as (1-5) is performed. (1-1) First Image Reduction Processing The image A shown in FIG. 2A is reduced to, for example, 1/8 by the image reduction unit 1 (that is, eight pixels in the vertical direction are reduced to one pixel). A reduced image S1 shown in FIG. 2B is created. In this case, if there is at least one black pixel in the range of 8 × 8 pixels on the image A corresponding to any one pixel of the reduced image S1, the image reducing unit 1 converts the one pixel on the reduced image S1 to black. To reduce. However, FIG. 2 (b) shows the reduced image S1 enlarged eight times for easy viewing. Image A corresponding to pixel D12 in reduced image S1
Since the area of the middle area D11 includes a black pixel, the pixel D12 is a black pixel. The pixel D22 in the reduced image S1 is a white pixel because there is no black pixel in the corresponding area D21 in the image A. In this image reduction processing,
When the image A is reduced to 1/8, the number of pixels becomes 1/64 of the original image, and high-speed processing can be performed in the subsequent processing.

(1-2) First Horizontal Black Run / Histogram Creation Processing The horizontal black run / histogram creation unit 2 generates, for example, a reduced image S1 of FIG. 2B having a predetermined first length L1A or more. By detecting a black run composed of black pixels having a continuous length and counting the number of black pixels constituting the black run for each horizontal scanning line, the horizontal run shown in FIG. Black orchid
A histogram S2 is created. At this time, the length L1A needs to be set in advance so as to be long enough not to detect the black pixels constituting the characters written in the table, and to be shorter than the ruled line used to detect the deviation. As a result, almost no characters are detected, and ruled lines used for detecting deviation are detected. For example, the horizontal scanning line HL in FIG.
In No. 1, since there is a black run longer than the length L1A from the vertical scanning line VL1 to the scanning line VL2, the number of black pixels constituting the black run is the count value. In the horizontal scanning line HL2, since there is no continuous black pixel having a length equal to or longer than the length L1A, the count value becomes zero.

(1-3) Rough Vertical Feature Extraction Processing In the rough vertical feature extraction unit 4, the count value is larger than the first value indicated by the broken line Lh from the horizontal black run histogram S2 in FIG. Is the start point of the peak, and the position where the count value is smaller than the value indicated by the broken line Lh is the end point of the peak,
A total value of the histogram values from the start point to the end point is detected as a peak size. For example, FIG.
At the top peak P1 of the histogram shown in FIG. 7, the distance PS1 from the side m to the start point s of the form, and the end point e from the side m
The distance PE1 and the area SP of the peak P1 are extracted as the coarse vertical feature amount S4. The other two peaks P2, P
The same applies to No. 3. (1-4) Fine Vertical Feature Extraction Process The fine vertical feature extraction unit 6 extracts, for example, the peak P1 in FIG. 2C from the image A corresponding to the range from the start point s to the end point e in FIG. As shown in d), a histogram projected in the horizontal direction is created. Then, the distance u from the side m of the position M where the value becomes the largest is extracted as the fine vertical feature amount S6 corresponding to the peak P1. FIG. 2 (c)
The fine vertical feature value S6 corresponding to the other two peaks P2 and P3 is similarly extracted. (1-5) Position feature amount recording processing The position feature amount recording unit 8 stores the coarse vertical feature amount S4 and the fine vertical feature amount S6 in the coarse vertical feature amount 8a and the fine vertical feature amount 8, respectively.
Record as c. Similarly, in the horizontal direction, the coarse horizontal feature value S5 and the fine horizontal feature value S7 are extracted, and are recorded in the position feature value recording unit 8 as the coarse horizontal feature value 8b and the fine horizontal feature value 8d, respectively.

(2) Ruled line position comparison processing FIGS. 3 (a), (b), (c), (d) and (e) illustrate an example of the processing for temporarily detecting a deviation in the image deviation detecting apparatus of FIG. FIG. 4 is a diagram illustrating an example of a deviation detection process. With reference to these figures, the ruled line position comparison processing (2-1) to (2-) for comparing the ruled line positions between the image A in FIG. 2A and the image B in FIG. 5) will be described. (2-1) Second image reduction processing The image reduction unit 11 performs the same processing as the first image reduction processing.
For example, the image B in FIG. 4 is reduced to 1/8, and a reduced image S11 shown in FIG. (2-2) Second Horizontal Black Run / Histogram Creation Processing The horizontal black run / histogram creation unit 12 performs the same processing as the first horizontal black run / histogram creation processing using, for example, a predetermined third length L2A as a threshold. The process is performed to create a horizontal black run histogram S12 shown in FIG. Length L2A
May be the same value as the length L1A. (2-3) Temporary Vertical Displacement Detection Processing The temporary vertical deviation detecting unit 14 is prepared by shifting the peak position of the coarse vertical feature amount 8a by predetermined values Y1, Y2, and Y3 (FIGS. 3C and 3C). d), peaks P1 shown in (e),
P2, P3 and the horizontal black run histogram S in FIG.
12 to generate a tentative detection value S14 of vertical displacement.
Hereinafter, methods (2-3-a) to (2-3-c) of generating the provisional detection value S14 by processing the first peak P1 will be described.

(2-3-a) As shown in FIG. 3C, when the starting point s and the ending point e of the peak P1 are shifted downward from the side m of the form by a predetermined value Y1, the starting point s and the ending point The sum of the count values of the histogram of FIG. 3B in the range of e is 0. The absolute value of the difference between the sum of the count values and the area S of the peak P1 is | 0−S | = S, and this S is the evaluation value of the peak P1. 2nd and 3rd peak P
The same processing is performed for P2 and P3, and the sum thereof is used as the evaluation value when the peaks P1, P2 and P3 deviate by Y1. (2-3-b) As shown in FIG.
Is shifted downward by a predetermined value Y2 from the side m of the form, the sum of the count values of the histogram of FIG. 3B in the range from the start point s to the end point e is S ″. The absolute value of the difference between the sum S "of the counted values and the area S of the peak P1 is | S" -S |, and is close to 0 if S "and S are substantially equal. The same processing is performed for the peaks P2 and P3, and the sum thereof is used as an evaluation value when the peaks P1, P2, and P3 are shifted by a predetermined value Y2. (2-3-c) As shown in FIG.
When the start point s and the end point e are shifted by a predetermined value Y3,
The sum of the count values of the histogram in FIG. 3B in the range from the start point s to the end point e is 0, which is the same as the case where the count is shifted by the predetermined value Y1 of (2-3-a). As a result,
Since the histogram shown in FIG. 2 (c) best matches the histogram shown in FIG. 3 (b), the evaluation value obtained by shifting the coarse vertical feature value 8b by a predetermined value Y2 becomes the smallest, and this predetermined value Y2 is It is generated as a temporary detection value S14.

(2-4) Vertical Displacement Detection Process The vertical displacement detection unit 16 shifts the position of the peak P1 of the coarse vertical feature value 8b by the temporary detection value S14 (ie, the predetermined value Y2), ie, the starting point s Fig. 4 corresponding to the time from to the end point e
For the range on the image B, a histogram of the pixels constituting the black run in the horizontal direction is created, and the vertical position M ″ at which the largest count value is obtained is obtained.
Sets the difference (M "-M) between the position M" and the position M of the fine vertical feature value in FIGS. 2D and 4 corresponding to the peak as the position shift of the peak. The vertical displacement detection unit 16
The same processing is performed for the third and third peaks P2 and P3, and the average value of the positional shifts of all the peaks is output as the detected value S16 of the vertical shift between the image A and the image B. Similarly, in the lateral direction, the lateral displacement detection unit 17
From the detected value S1 of the lateral displacement between the image A and the image B
7 is output.

(2-5) Deviation Detection Processing The deviation detection unit 18 combines the detection value S16 and the detection value S17 to detect a deviation of the image B from the position of the image A.
As described above, in the first embodiment, the positions of the histograms of the black run in the vertical direction and the horizontal direction of the reduced image S1 of the image A and the reduced image of the image B in the vertical deviation detection unit 16 and the horizontal deviation detection unit 17 By comparing the positions of the histograms of the black run in the vertical direction and the horizontal direction in S11 with each other, the detection value S1 of the vertical shift between the image A and the image B is obtained.
6 and the detection value S17 of the lateral shift are detected respectively. If there is a ruled line in the document of the form, a general scanner can be used without using a special scanner capable of detecting the edge of the form. Even in this case, it is possible to detect a slip of the form. Further, even when the position of the document with respect to the edge of the form such as a copied form is shifted from the reference position, the processing can be performed normally. In the present embodiment, the images A and B are used in the first and second image reduction processes.
Is reduced and the number of pixels is reduced, so that high-speed processing can be performed in each subsequent processing. Further, in the first and second horizontal black run / histogram creation processes, the length L1A and the length L2A are set to the same value, so that the processing programs can be shared, and the scale of the memory for storing the processing programs can be reduced. it can.

Second Embodiment FIG. 5 is a block diagram of an image misalignment detecting apparatus for implementing an image misalignment detecting method according to a second embodiment of the present invention.
Elements common to those in FIG. 1 showing the first embodiment are denoted by common reference numerals. In this image shift detecting apparatus, the horizontal black run / histogram creating unit 2, coarse vertical feature amount extracting unit 4, and horizontal black run / histogram creating unit 12 in FIG.
Instead, a horizontal black run / histogram creating unit 2A, a coarse / vertical feature amount extracting unit 4A, and a horizontal black run / histogram creating unit 12A having different configurations are connected, and the horizontal black run / histogram creating unit is connected. 2A and coarse vertical feature amount extraction unit 4
A, a horizontal black run threshold correction unit 21 is newly provided, and a horizontal black run threshold storage unit 22 is connected between the horizontal black run threshold correction unit 21 and the horizontal black run / histogram creation unit 12A. Have been. The horizontal black run / histogram creation unit 2A
For the reduced image S1, a horizontal black run having a length equal to or greater than the horizontal black run threshold value S21 supplied from the horizontal black run threshold correction unit 21 is detected for each horizontal scanning line, and this black run is configured. The horizontal black run histogram S2A is created by counting the number of pixels. The coarse and vertical feature amount extraction unit 4A detects one or a plurality of peaks from the horizontal black run histogram S2A, and outputs the position and magnitude of the peak. For example, a range in which the horizontal black run histogram S2A is equal to or more than a certain value is defined as a peak, and the sum of the count values of the histogram in the range is defined as the size of the peak.
Is generated as When the predetermined number of peaks has not been detected (for example, when no peak has been detected), the coarse vertical feature amount extraction unit 4A sends the horizontal black run threshold value correction unit 21 the horizontal black run threshold value S21. The correction is made.

The horizontal black run threshold value correcting unit 21 initially sets a predetermined initial value as a horizontal black run threshold value S21.
Provided to the histogram creation unit 2A, the coarse vertical feature amount extraction unit 4
If a predetermined number of peaks are not detected in A (for example, if no peak is detected), the horizontal black run threshold value S21 is reduced (for example, halved), and the horizontal black run histogram is again obtained. The processing is supplied to the creation unit 2A and the processing is performed again. The horizontal black run threshold value S21 that is finally used is stored in the horizontal black run threshold storage unit 22 for use in a subsequent shift detection process. The horizontal black run / histogram creation unit 12A stores the horizontal black run threshold value storage unit 22 for each vertical scanning line for the reduced image S11.
The horizontal black run having a length equal to or longer than the horizontal black run threshold value S22 stored in the horizontal direction is detected, and the number of pixels constituting the black run is counted to create a horizontal black run histogram S12A. Further, in this image shift detecting device, the vertical black run / histogram creating unit 3, the coarse / horizontal feature extracting unit 4, and the vertical black run / histogram creating unit 12 in FIG. Vertical black run / histogram creation unit 3A,
The coarse / horizontal feature extracting unit 5A and the vertical black run / histogram creating unit 13A are connected, and a vertical black run is newly added between the vertical black run / histogram creating unit 3A and the coarse / horizontal feature extracting unit 5A. A threshold correction unit 33 is provided, and a vertical black run threshold storage unit 24 is connected between the vertical black run threshold correction unit 23 and the vertical black run / histogram creation unit 13A.

The vertical black run / histogram creating unit 3A, for each of the vertical scanning lines of the reduced image S1, has a vertical black run threshold S23 supplied from the vertical black run threshold correction unit 23 in the vertical direction. Is detected, and the number of pixels constituting the black run is counted to create a vertical black run histogram S3A. The coarse / horizontal feature extraction unit 5A detects one or a plurality of peaks from the vertical black run histogram S3A, and outputs the position and size of the peak.
For example, a range in which the vertical black run histogram S3A is equal to or more than a certain value is set as a peak, and the sum of the count values of the histogram in the range is set as the size of the peak and stored as the coarse and horizontal feature amount S5A. Also, the coarse and horizontal feature amount extraction unit 5A
When the predetermined number of peaks is not detected (for example, when no peak is detected), the vertical black run threshold correction unit 23 corrects the vertical black run threshold S23. The vertical black run threshold correction unit 23 initially provides a predetermined initial value as the vertical black run threshold S23 to the vertical black run / histogram creation unit 3A, and the peak is predetermined in the coarse / horizontal feature extraction unit 5A. If the number is not detected (for example, if none is detected),
Reduce vertical black run threshold S23 (for example, to 1/2)
Then, the process is provided again to the vertical black run / histogram creating unit 3A to repeat the process. The finally used vertical black run threshold value S23 is stored in the vertical black run threshold storage unit 24 for use in the subsequent deviation detection processing.
The vertical black run / histogram creation unit 13A outputs the reduced image S1
1 for each vertical scanning line, a vertical black run having a length equal to or longer than the vertical black run threshold S24 stored in the vertical black run threshold storage unit 24 is detected, and the number of pixels constituting the black run is detected. Is counted to create a vertical black run histogram S13A. Other configurations are the same as those in FIG.

In the image shift detecting method in the image shift detecting apparatus, the following processes (1) and (2) are different from those in FIG. (1) Position Feature Extraction Processing FIG. 6 is a diagram showing a first example of the black run threshold value correction processing. FIG. 6A shows an image reduction unit for an image A to be subjected to the position feature extraction processing. 1, a reduced image S1 that has undergone the first image reduction processing is shown, a threshold L1B-1 for detecting a vertical black run is shown, and a black run histogram is shown in FIG. . FIG. 7 is a diagram showing a second example of the black run threshold value correction process. FIG. 7A shows a reduced image S1 and a threshold value L1B-2 for detecting a vertical black run. FIG. 6B shows a histogram of the black run. The vertical black run threshold correction unit 23
The threshold value L1B-1 having the length shown in FIG. 6A is held as the initial value of the threshold value of the black run. The vertical black run / histogram creation unit 3A attempts to detect a vertical black run having a length equal to or longer than the threshold L1B-1. However, the vertical black run / histogram creating unit 3A has a length equal to or longer than the threshold L1B-1 in the reduced image S1 of FIG. , There is no black run, and all the count values of the histogram become 0 as shown in FIG. For this reason, since the coarse / horizontal feature extraction unit 5A does not detect the peak of the histogram, as shown in FIG. 7A, the vertical / black run threshold correction unit 23 sets the threshold L1B, for example, to half the threshold L1B-1. -2 is the new black run threshold S2
3 to the vertical black run / histogram creation unit 3A,
The vertical black run / histogram creation unit 3A performs the vertical black run / histogram creation processing again. The vertical black run / histogram creating unit 3A determines that the vertical black runs having a length equal to or greater than the threshold value L1B-2 in the vertical direction are vertical scanning lines VL3 and VL4 in FIG.
, A histogram as shown in FIG. 7B is created. Since the coarse and horizontal feature extraction unit 5A finds two peaks P11 and P12 from this histogram, the subsequent processing is continued similarly to the first embodiment. At this time, the threshold value L1B-2 of the used vertical black run is used.
Is stored in the vertical black run threshold storage unit 34. in this way,
The ruled line in the document to be processed is the initial threshold value (that is, L1B
Even when the length is shorter than -1), the vertical black run / histogram creation processing can be performed.

(2) Ruled Line Position Comparison Processing The vertical black run / histogram creation unit 13A uses the reduced image S1
1, for each vertical scanning line, a vertical black run having a length equal to or longer than the vertical black run threshold S24 (that is, the vertical black run threshold L1B-2) stored in the vertical black run threshold storage unit 24. Is detected, the number of pixels constituting the black run is counted, and a vertical black run histogram S13A is created. Subsequent processing is the first
This is performed in the same manner as in the embodiment. In the present embodiment, the correction process of the vertical black run threshold value S23 has been described.
Similar processing is performed for the horizontal black run threshold value S21. As described above, in the second embodiment, when the vertical black run / histogram creation unit 3A cannot detect a black run longer than the predetermined threshold L1B-1, the vertical black run threshold correction unit 2A
3 sets a shorter threshold value L1B-2, so that even when processing a document in a style composed of short ruled lines, the ruled lines can be used to detect a deviation of the image B from the position of the image A. it can. In the case of processing a document in a style composed of long ruled lines as in the first embodiment,
Since the threshold value L1B-1 of the black run is not corrected, a short ruled line that is easily confused with a character or the like is not detected. Therefore, the accuracy of the vertical black run / histogram creation processing can be kept high.

The present invention is not limited to the above embodiment,
Various modifications are possible. For example, there are the following modifications. (A) In the first image reduction process, any reduction method or reduction method may be used as long as line elements such as ruled lines do not disappear during reduction. (B) In the second embodiment, the threshold L1B-2 is the threshold L
The threshold value L1B-2 has been corrected to 1/2 of 1B-1.
Is smaller than the threshold value L1B-1. (C) The present invention can be applied to all methods for detecting a shift between an image used for registering a reading position of a document and an image to be actually read.

[0028]

As described in detail above, claims 1 to 5
According to the fourth aspect, in the vertical shift detecting process and the horizontal shift detecting process, the positions of the histograms of the vertical and horizontal black runs of the first reduced image and the vertical and horizontal black positions of the second reduced image are determined. By comparing the positions of the run histograms with the positions of the run histograms, the detected value of the vertical shift and the detected value of the horizontal shift between the first image and the second image are detected, respectively. If there is a ruled line in the document of the form, the deviation of the form can be detected by using a general scanner without using a special scanner capable of detecting the edge of the form. Further, even when the position of the document with respect to the edge of the form such as a copied form is shifted from the reference position, the processing can be performed normally. Moreover, in the first and second image reduction processes, the first and second images are reduced.
Since the image is reduced and the number of pixels is reduced, high-speed processing can be performed in each subsequent processing. Further, the first and second
In the horizontal black run / histogram creation processing, the first length and the third length are set to the same value, and the first length and the third length are set in the first and second vertical black run / histogram creation processing.
Since the length is set to the same value, the processing program can be shared, and the scale of a memory or the like for storing the processing program can be reduced. According to the fifth aspect of the present invention, when a black run longer than the first length cannot be detected in the first vertical black run / histogram creation processing, the first length is reduced by the vertical black run threshold correction processing. Since the setting is performed, even when processing a document in a format composed of short ruled lines, the ruled lines can be used for detecting a deviation of the second image from the position of the first image. In addition, when processing a document having a style composed of long ruled lines similar to that of the first invention, the first length is not corrected, so that a short ruled line that is easily confused with a character or the like is not detected. Therefore, the accuracy of the vertical black run / histogram creation processing can be kept high.

[Brief description of the drawings]

FIG. 1 is a configuration diagram of an image shift detection device according to a first embodiment of the present invention.

FIG. 2 is a diagram illustrating an example of a position feature amount extraction process.

FIG. 3 is a diagram illustrating an example of a provisional deviation detection process.

FIG. 4 is a diagram illustrating an example of a shift detection process.

FIG. 5 is a configuration diagram of an image shift detecting apparatus according to a second embodiment of the present invention.

FIG. 6 is a diagram illustrating a first example of a black run threshold value correction process.

FIG. 7 is a diagram illustrating a second example of the black run threshold value correction processing.

[Explanation of symbols]

DESCRIPTION OF SYMBOLS 1 Image reduction part 2, 2A Horizontal black run / histogram creation part 3, 3A Vertical black run / histogram creation part 4, 4A Coarse vertical feature amount extraction part 5, 5A Coarse horizontal feature amount extraction part 6 Fine vertical feature amount extraction part 7 Fine horizontal feature amount extraction unit 8 Position feature amount recording unit 11 Image reduction unit 12, 12A Horizontal black run / histogram creation unit 13, 13A Vertical black run / histogram creation unit 14 Vertical displacement temporary detection unit 15 Horizontal displacement temporary detection unit 16 Vertical displacement Detector 17 Lateral shift detector 18 Displacement detector 21 Horizontal black run threshold correction unit 22 Horizontal black run threshold storage unit 23 Vertical black run threshold correction unit 24 Vertical black run threshold storage unit A First image B Second image S1 Reduction Image S2 Horizontal black run / histogram S3 Vertical black run / histogram S4 Rough vertical feature S5 Rough horizontal feature S6 Fine vertical feature S7 Fine horizontal feature S11 Reduced image S12 Horizontal black Run histogram H13 Vertical black run histogram S14 Temporary detection value of vertical deviation S15 Temporary detection value of horizontal deviation S16 Detection value of vertical deviation S17 Detection value of horizontal deviation

Claims (5)

[Claims] An image of a first document in which a first document is described in a table represented by a ruled line at a reference position is converted into an electric signal to generate a first image, and the first image is created. A position feature extraction process for detecting the ruled line in the image, and a second document that needs to detect a positional deviation from the position of the first document is described in a table in the same format as the first document. A second image is created by converting the image of the second form into an electric signal, and the position of the ruled line in the second image and the ruled line in the first image detected in the position feature extraction processing And a ruled line position comparing process for detecting a positional deviation between the respective ruled lines by comparing the positions of the ruled lines with each other and determining the positional deviation as a positional deviation between the first image and the second image. And a method for detecting an image shift. 2. The position feature extraction process includes: converting an image of a first form in which a first document is described in a table represented by a ruled line at a reference position into an electric signal to generate a first image; A first image reduction process for generating a first reduced image by reducing the first image at a predetermined reduction ratio; and a first predetermined length in a horizontal direction in the first reduced image. A first horizontal black run histogram in which the number of the black pixels is totaled in the horizontal direction for a black run composed of continuous black pixels is created for each horizontal scanning line. Horizontal black run / histogram creation processing, and for a black run composed of black pixels that are continuous for a predetermined second length or more in the vertical direction in the first reduced image, the number of black pixels is determined by the vertical A first vertical black run for creating a first vertical black run histogram totaled in the vertical direction for each vertical scanning line A histogram creation process; a coarse vertical feature amount extraction process of extracting a vertical position and a size of one or more peaks on the first horizontal black run histogram as a coarse vertical feature amount; A coarse / horizontal feature extraction process for extracting the horizontal position and magnitude of one or more peaks on the vertical / black run histogram as coarse horizontal feature amounts; and extracting the coarse vertical feature amounts as the coarse vertical feature amounts. For each peak, the number of black pixels on each scanning line in the horizontal direction in a portion corresponding to the position of each peak in the first image is counted, and the position of the scanning line at which the counted value is the maximum is determined for each peak. A fine vertical feature value extraction process for extracting as a fine vertical feature value; and for each peak extracted as the coarse horizontal feature value, a vertical position of a portion corresponding to the position of each peak in the first image. Directional Performing a fine horizontal feature amount extraction process of counting black pixels on the scanning line and extracting the position of the scanning line at which the counted value is the maximum as a fine horizontal feature amount at each peak; The processing is as follows: an image of a second document, in which a second document for which it is necessary to detect a positional shift with respect to the position of the first document, is described in a table in the same format as the first document, is converted into an electric signal. A second image reduction process for reducing the second image at the same reduction ratio as the first image reduction process to generate a second reduced image; For a black run composed of black pixels continuous in the second reduced image in a horizontal direction for a predetermined third length or more, a second horizontal black run in which the number of the black pixels is totaled in the horizontal direction A second horizontal black run for generating a histogram for each horizontal scanning line; Processing, for a black run composed of black pixels continuous in the second reduced image in the vertical direction for a predetermined fourth length or more, a second count of the number of black pixels in the vertical direction is calculated. A vertical black run / histogram generation process for generating a vertical black run / histogram for each vertical scanning line; and a predetermined value Yi ( In the state shifted by i = 1, 2,..., N), the second horizontal black run histogram is vertically compared with the second horizontal black run histogram, and the predetermined value Yk at the time when the difference is smallest is generated as a vertical deviation temporary detection value. Vertical deviation temporary detection processing, and the second vertical black run is performed in a state where the positions of the respective peaks of the coarse horizontal feature amount are shifted by a plurality of predetermined values Xi (i = 1, 2,..., N).・ Comparing the histogram with the horizontal direction, the predetermined value Xk when the difference is the smallest is laterally shifted. A lateral displacement temporary detection process that is generated as a temporary detection value; and for each peak of the coarse vertical feature amount, the position of each peak is shifted by the vertical displacement temporary detection value Yk. The number of black pixels of the portion is counted for each scanning line in the horizontal direction, and the position of the scanning line when the count value is the largest and the scanning line corresponding to each peak recorded as the fine vertical feature amount And a vertical deviation detection process of detecting an average value of the respective differences as a vertical deviation of the second image from the first image, and each of the coarse horizontal characteristic amounts. For the peaks, the number of black pixels in the portion of the second image corresponding to the position obtained by shifting the position of each peak by the lateral displacement temporary detection value Xk is counted for each scanning line in the vertical direction, and the counted value is the largest. Scanning line position when The difference between each peak and the position of the scanning line corresponding to each peak recorded as a fine horizontal feature amount is taken, and the average value of each difference is taken as the horizontal direction of the second image with respect to the first image. A lateral displacement detection process for detecting as a displacement of the first image, a vertical displacement of the second image detected by the vertical displacement detection process with respect to the first image, and a second displacement detection process of the second image detected by the lateral displacement detection process. A shift detection process for detecting a shift in the position of the second document with respect to the position of the first document by synthesizing the shift with the shift in the horizontal direction with respect to the first image. Item 1. The image shift detecting method according to Item 1. 3. The rough vertical feature amount extraction process starts at a position at which the value of the first horizontal black run histogram becomes larger than a predetermined first value set in advance and sets the predetermined first value as the starting point. Detecting as a peak having a smaller position as an end point, extracting a total of histogram values from the start point to the end point as a size of the peak, the rough horizontal feature amount extraction processing includes: A position where the value of the vertical black run histogram is larger than a predetermined second value is set as a starting point, and a position where the value is smaller than the predetermined second value is set as an end point. The sum of the values of the histogram up to the end point is extracted as the size of the peak, and the vertical misalignment temporary detection processing is performed for each peak of the coarse vertical feature amount for the second horizontal black run histogram. Each pea The sum of the count values in a range in which the start point and the end point of the peaks are shifted by the predetermined value Yi is calculated, and the difference between the calculated value and the size of each peak recorded in the coarse vertical feature amount is determined by the discrepancy between the peaks. , And the predetermined value Yi when the sum of the degrees of mismatch is minimized is detected as a vertical deviation temporary detection value Yk. The horizontal deviation temporary detection processing is performed by the second vertical black run histogram. For each peak of the coarse horizontal feature amount, the sum of count values in a range in which the start point and the end point of each peak are shifted by the predetermined value xi is calculated, and the calculated value and the coarse horizontal feature amount are calculated. Detecting the difference from the magnitude of each peak recorded in the above as the degree of inconsistency of the peak, and detecting the predetermined value Xi when the sum of the degrees of inconsistency becomes the smallest as the temporary deviation temporary detection value Xk. Claims characterized by Item 3. The method for detecting a displacement of an image according to Item 1 or 2. 4. A predetermined first length in the first horizontal black run histogram creation processing and a predetermined third length in the second horizontal black run histogram creation processing have the same value, The predetermined second length in the first vertical black run / histogram creation process and the predetermined fourth length in the second vertical black run / histogram creation process have the same value. 4. The method of detecting an image shift according to claim 1, 2, or 3. 5. When the number of peaks extracted in the rough vertical feature amount extraction processing is equal to or less than a predetermined number, the value of the first length is corrected to a small value, and the first horizontal black run is performed again. A horizontal black run threshold correction process of performing a histogram generation process a required number of times and recording the value of the first length when the number of the peaks becomes larger than the predetermined number as a horizontal black run threshold. If the number of peaks extracted in the coarse / horizontal feature extraction processing is equal to or less than a predetermined number, the value of the second length is corrected to be small, and the second vertical black run / histogram creation processing is performed again. Performing a required number of times, and performing a vertical black run threshold correction process of recording the value of the second length as a vertical black run threshold when the number of peaks is greater than the predetermined number; 2 in the horizontal black run / histogram creation processing of FIG. Using said transverse black run threshold as the length of 3,
5. The image shift according to claim 1, wherein the vertical black run threshold is used as the predetermined fourth length in the second vertical black run / histogram creation processing. 6. Detection method.