JPH0219509B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to an angular difference detection device for detecting an angular difference between two congruent, similar, or similar images.

For example, in a seal matching device, which is an applied field of image processing technology, pattern matching is performed on the same plane between a matching seal impression, that is, a matching image, and a registered seal impression, that is, a reference image that is used as a reference for matching. A process of comparing the two and determining the degree of similarity between the two is often used.

However, at this time, if the angle or orientation of the image to be matched is different from the orientation of the reference image, that is, if there is an angular difference between the image to be matched and the reference image, it is difficult to perform the matching as is.

For this reason, a process is often used in which the angular difference between the two images is detected, and one of the images is rotated to remove the angular difference, thereby aligning the angles of the two images.

At this time, it is important that the angular difference between the two images can be detected accurately and in a short time.

[Prior Art] Fig. 2 is a block diagram showing the configuration of a conventional example of an angular difference detection device used for the above purpose. An image reading device outputs the density of each arranged pixel; 2 is a first image memory that stores image data read by the image reading device 1; 3 generates an address for the first image memory 2; This is an address control circuit.

4a and 4b constitute a first feature extraction circuit 4 that extracts an angle histogram indicating the angle of the image to be matched, and 4a differentiates the image data stored in the first image memory 2 by (3×3). 4b is a differentiation circuit that scans with a calculation window and obtains a spatial differential value, that is, a density gradient in each pixel, and 4b is a differentiation circuit that calculates a spatial differential value, that is, a density gradient, in each pixel. This is a histogram calculation circuit that calculates the angle histogram of the direction of density change of the image to be compared by finding the direction of the density gradient, that is, the angle, and counting the number of pixels for each angle.

Reference numeral 5 denotes a first histogram memory that stores the angle histogram extracted by the first feature extraction circuit 4, with angles from 1 degree to 360 degrees as addresses; a second histogram memory that stores the angle histogram obtained from the image; 7 is a second address control circuit that generates addresses for the first histogram memory 5 and the second histogram memory 6;
is a shift circuit that shifts the address generated by the second address control circuit 7 for the first histogram memory 5 by a fixed angle.

9 is a distance calculation circuit that calculates the distance between the angle histogram read from the first histogram memory 5 and the histogram read from the second histogram memory 6; 10 is a circuit that shifts the distance calculated by the distance calculation circuit 9; This is an output memory that stores data for each shift angle in 8.

For example, an image like that shown in FIG. 3a is displayed on the image input device 1.
When the image is observed and stored in the image memory 2, the differential circuit 4a calculates the spatial differential value, that is, the concentration gradient, at each pixel as the direction and length of the arrow, as illustrated in FIG. .

The histogram calculation circuit 4b calculates an angular histogram by counting the number of pixels for each angle in the density change direction (the direction of the arrow illustrated in FIG. 3b) obtained by the differentiating circuit 4a. The obtained angle histogram (see FIG. 3c) is stored in the first histogram memory 5.

Next, the angle histogram of the image to be matched stored in the first histogram memory 5 and the angle histogram of the reference image stored in the second histogram memory 6 are read out, and the distance calculation circuit 9 calculates the angle histogram of the reference image. Calculate the distance between angle histograms.

Next, the shift circuit 8 reads the first histogram memory 5 while shifting it one degree at a time, thereby calculating the angle between the angle histogram of the image to be matched and the angle histogram of the reference image shifted by one degree. do.

In the same way, for example, calculate the distance between two angle histograms for all shift angles up to 359 degrees every other degree, output the distance for each shift angle to the output memory 10, and select the one with the minimum distance from among them. The shift angle shown is the angle between the image to be matched and the reference image.

[Problem that the invention seeks to solve]

In the angular difference detection device with the above configuration, it is necessary to perform distance calculations, for example, 360 times while shifting the histogram of the matched image and the histogram of the reference image over the entire angular range. The problem is that it takes a long time.

[Means for solving problems]

The angular difference detection device according to the present invention includes a first feature extraction circuit that extracts an angular histogram in the direction of density change in each pixel constituting an image, and an angular difference extracted from a matched image by the first feature extraction circuit. A shift circuit that shifts the relative angle between the angle histogram to be matched and a reference angle histogram extracted from a reference image in advance, and a distance calculation circuit that calculates the distance between both histograms, Therefore, in an angular difference detection device that detects an angular difference between a matched image and a reference image, a second feature extraction circuit that extracts a peak angle corresponding to each peak of the angle histogram is provided, After shifting the angle of one angle histogram so that one of the peak angles of the histogram matches one of the peak angles of the reference histogram,
The distance of the other angle histogram is calculated only in a predetermined angle range near each peak angle of one angle histogram, and the angles of one angle histogram are further adjusted so that the correspondence of the matched peak angles shifts cyclically. The above-mentioned problem is solved by performing the distance calculation by shifting the image and detecting the angular difference between the matching image and the reference image based on the angular shift amount that minimizes the distance calculation result.

[Effect]

That is, the peak angle corresponding to each peak of the angle histogram is extracted, and 1 of each peak angle of the angle histogram to be compared and the reference histogram is extracted.
After shifting the angles so that they match, the distance calculation for the other angle histogram is limited to a predetermined angle range near each peak angle of one angle histogram, reducing the amount of calculation required for one distance calculation. , Furthermore, by shifting the angle according to the peak angle of one angle histogram, the distance calculation is performed by cyclically shifting the correspondence of the matched peak angles, so that the number of distance calculations is equal to the number of peaks. Since only a few steps are required, the total amount of calculations is drastically reduced, and angular differences can be detected in a short time.

〔Example〕

The gist of the present invention will be specifically explained below using Examples.

Figure 1 is a block diagram showing the configuration of one embodiment of the present invention, and the symbols common to those in the conventional example in Figure 2 refer to the same objects, and 11 extracts the peak angle between the image to be matched and the reference image. This is a second feature extraction circuit. Further, 8' is a shift circuit that shifts the address for the first histogram memory 5 generated by the second address control circuit 7 by a predetermined angle in accordance with the peak angle extracted by the second feature extraction circuit 11. It is.

With the above configuration, when angle histograms are stored in the first histogram memory 5 and the second histogram memory 6, respectively, in the same manner as in the conventional example, the second feature extraction circuit 11
From the angle histogram of the image to be matched stored in the first histogram memory 5 and the angle histogram of the reference image stored in the second histogram memory 6, the angle with respect to the peak (maximum value, generally there is more than one) is calculated. Extract as peak angle.

Assuming that the matching image and the reference image have rectangular outlines as illustrated in Figure 3a, four peak angles should be obtained from each angle histogram, and among these, the reference image Let θ _s be any one of the peak angles obtained from the image,
The four peak angles obtained from the matched images are expressed as (θ _s
+θ1)・(θ _s +θ2)・(θ _s +θ3) and (θ _s +θ
4).

The shift circuit 8' converts the addresses of the first histogram memory 5 generated by the second address control circuit 7 into (θ _s + θ1), (θ _s + θ2), and (θ _s +
θ3) and (θ _s + θ4), and furthermore, for each shifted angle, the angle is 2 degrees forward and backward every other degree, that is, for θ _o , it is (θ _o −2)・(θ _o − 1)・θ _o・
(θ _o +1) and (θ _o +2), total 20
Shift by the shift angle of.

The distance calculation circuit 9 reads each of the 20 types of angle histograms of the image to be matched shifted and read out from the first histogram memory 5 as described above, and the angle histograms read out from the second histogram memory in correspondence with the angles. The distance between the angle histogram of the reference image and the angle histogram of the reference image is calculated, the distance for each shift angle is output to the output memory 10, and such distance calculation is applied to each peak angle θ _s (4 pieces) of the reference angle histogram. Then, the angle between the image to be matched and the reference image is determined based on the shift angle at which the calculated distance is the minimum.

In the above example, if the distance is the sum of the absolute values of the differences, the distance can be calculated by calculating the absolute values of the differences 20 times and finding the sum for each peak angle θ _s . A desired angular difference can be obtained by calculating the distance by calculating the absolute value of the difference 20×4=80 times.

〔Effect of the invention〕

As explained above, according to the present invention, joint
The angle between two similar or similar images can be determined in a short time.

[Brief explanation of drawings]

FIG. 1 is a block diagram of an embodiment of the present invention, FIG. 2 is a block diagram of a conventional example, and FIGS. 3 a, b, and c are explanatory diagrams of a conventional example. In the figure, 4 is a first feature extraction circuit, 4a is a differentiation circuit, 4b is a histogram calculation circuit, 8 and 8' are shift circuits, 9 is a distance calculation circuit, and 11 is a second feature extraction circuit.

Claims (1)

[Scope of Claims] 1. A first feature extraction circuit that extracts an angular histogram in the direction of density change in each pixel constituting an image, and a matched angle extracted from a matched image by the first feature extraction circuit. A shift circuit that shifts the relative angle between the histogram and a reference angle histogram extracted from a reference image in advance, and a distance calculation circuit that calculates the distance between both histograms, An angular difference detection device that detects an angular difference between a matching image and a reference image, further comprising: a second feature extraction circuit that extracts peak angles corresponding to each peak of the angular histogram; After shifting the angle of one angle histogram so that one of the angles matches one of the peak angles of the reference histogram, the distance of the other angle histogram is shifted only in a predetermined angular range near each peak angle of one angle histogram. The distance calculation is performed by shifting the angle of one of the angle histograms so that the correspondence of the matched peak angles shifts cyclically, and the distance is calculated by the amount of angular shift that minimizes the distance calculation result. An angular difference detection device that detects an angular difference between a matching image and a reference image.