Digital image comparing system

The present invention relates to a digital image comparing system.

Digital image processing systems are known, which provide for comparing two similar images, e.g. two images of similar objects, or two images of the same scene recorded at different times.

More specifically, such systems provide for comparing a detected image with a reference image to determine any differences between the two, and are used for quality control, e.g. automatic surface control (of printed circuits, fabrics, etc.) and for controlling printing processes, e.g. in the case of paper currencies, for determining any difference between a test and reference bank note, and rejecting the test note when the differences detected exceed a given threshold value.

The above systems are also used as part of automatic cartography systems, for grouping different images (e.g. satellite-recorded images of the earth's surface) by superimposing common portions of adjacent images, or for comparing images of the same scene recorded at different times.

The image processing method normally employed by known systems of the above type comprises three main steps: a first step in which reference points are selected in a first image; a second step in which reference points corresponding to those selected in the first image are selected in a second image; and a third step in which the parameters of the transformation function relating corresponding reference points in the two images are calculated, e.g. by means of a least mean square algorithm.

The reference points may be selected manually or semiautomatically. In the first case, the operator selects the reference points in the first image manually, and the selection made by the operator may be improved and refined with the aid of the computer. This method provides for selecting an extremely limited number of points.

In the second case, the image is searched for points defining reference marks or figures with given recognizable characteristics, e.g. intersecting lines, widely curving contour lines, centers of enclosed regions, figure angles, etc. The drawback of this type of selection, however, is the highly complex computing and processing work involved, and the large number of numeric operations required to calculate the function relating the corresponding reference figures or reference marks in the two images.

It is an object of the present invention to provide a digital image processing system enabling straightforward, effective comparison of two digital images.

According to the present invention, there is provided a digital image comparing system, as claimed in Claim 1.

A preferred, non-limiting embodiment of the present invention will be described by way of example with reference to the accompanying drawings, in which: <ul id="ul0001" list-style="none" compact="compact"><li>Figure 1 shows a simplified block diagram of the architecture of a digital image comparing system in accordance with the teachings of the present invention;</li><li>Figure 2 shows a more detailed diagram of the operation of individual blocks in Figure 1;</li><li>Figures 3a, 3b, 3c show images corresponding to sets of data processed successively by the system according to the present invention;</li><li>Figures 4a, 4b, 4c show images corresponding to sets of data processed successively by the system according to the present invention;</li><li>Figure 5 shows a calculating step performed by the system according to the present invention;</li><li>Figures 6 and 7 show, graphically, calculating steps performed by the system according to the present invention.</li></ul>

Number 1 in Figure 1 indicates a system for comparing digital images, and comprising a first and second data processing block 5, 6 supplied with respective data streams.

More specifically, block 5 is supplied with a first data stream I corresponding to a first (reference) image S; and block 6 is supplied with a second data stream I' corresponding to a second (detected) image S', in particular an image similar to and for comparison with image S.

Images S and S' are substantially similar, and may be: <ul id="ul0002" list-style="none" compact="compact"><li>a) images of the same subject (e.g. aerial photos of the same region) taken from different angles;</li><li>b) images of the same subject taken from the same angle but with different lighting (e.g. images recorded at different times);</li><li>c) images of the same subject taken by different devices (e.g. different cameras);</li><li>d) images of the same subject (e.g. bank notes) with small difference regions.</li></ul>

The information of images S and S' must be sufficiently structured to enable the selection of a number of reference points; and, with the exception of different lighting or small difference regions, it is assumed the relation linking the two images is approximately an affine transformation, and that no major deformation exists between images S and S'.

Data streams I and I' may comprise matrixes (e.g. square matrixes of size N x N) comprising a number of points (pixels), each with a grey level defined by a number (e.g. from 0 to 255 for an eight-bit representation).

As explained later on, block 5 processes the input data stream I, and presents three outputs 5a, 5b, 5c respectively presenting data M2, M3, P1 resulting from the processing of data stream I.

As explained later on, block 6 processes the input data stream I', and presents three outputs 6a, 6b, 6c respectively presenting data P2, P3, P4 resulting from the processing of data stream I'.

System 1 also comprises an initial estimating block 10, which is supplied with data P4 and P1 from respective second and first data processing blocks 6 and 5.

As explained later on, block 10 compares data P4 and P1 to obtain a first estimate of the set of parameters defining the function relating images S and S'.

More specifically, block 10 generates a three-dimensional vector A_o(X,Y,alpha) defining the rotation-translation function approximately relating images S and S'. That is, three-dimensional vector A_o(X,Y,alpha) defines a first approximation of to what extent image S' is translated (X,Y) and rotated about the center (alpha) in relation to reference image S.

Three-dimensional vector A_o(X,Y,alpha) is supplied to a first input 13a of a compensating block 13, which also presents a second input 13b supplied with data P3 from data processing block 6.

By means of the function defined by three-dimensional vector A_o(X,Y,alpha), compensating block 13 modifies data P3, and generates corrected data f(P3) defining an image S'' correlated with, and including a first correction of, image S'. More specifically, the correction made to data P3 provides for compensating the rotation-translation of image S' as determined in block 10.

The output of compensating block 13 is connected to a first input 17a of a refining block 17, which also presents a second input 17b supplied with data M3 from data processing block 5.

As explained later on, block 17 compares data M3 and corrected data f(P3) to obtain parameters by which to perfect the definition of the function relating images S and S' and defined approximately by vector A_o(X,Y,alpha).

In other words, the set of parameters generated by block 17 defines to what extent image S'' still differs from reference image S.

Block 17 generates a six-dimension vector dA(X,Y,c,s,r,g) defining the affine function relating images S and S''.

Vector dA(X,Y,c,s,r,g) is supplied to a block 20 by which it is combined, as explained later, with three-dimensional vector A_o(X,Y,alpha) to generate a vector A(X,Y,c,s,r,g).

Vector A(X,Y,c,s,r,g) defines more accurately than vector A_o(X,Y,alpha) the relationship between image S' and reference image S.

Vector A(X,Y,c,s,r,g) generated by block 20 is supplied to a first input 23a of a compensating block 23, which also presents a second input 23b supplied with data P2 from data processing block 6.

By means of the function defined by vector A(X,Y,c,s,r,g), compensating block 23 modifies data P2, and generates corrected data f(P2) defining an image S''' correlated with, and including a correction of, image S'. More specifically, the correction made to data P2 by block 23 is more precise than that made by block 13.

The output of compensating block 23 is connected to a first input 27a of a second refining block 27, which also presents a second input 27b supplied with data M2 from data processing block 5.

As explained later on, block 27 compares data M2 and corrected data f(P2) to obtain parameters by which to perfect the definition of the function relating images S and S' as compared with the definition made by vector A(X,Y,c,s,r,g).

In other words, the set of parameters generated by block 27 defines to what extent image S''' still differs from reference image S.

Block 27 generates a six-dimension vector dA2(X,Y,c,s,r,g) defining the affine function more closely relating images S and S'''.

Vector dA2(X,Y,c,s,r,g) is supplied to a block 30 by which it is combined, as explained later, with vector A(X,Y,c,s,r,g) to generate a vector A2(X,Y,c,s,r,g).

Vector A2(X,Y,c,s,r,g) generated by block 30 is used to correct data stream I'.

Digital image comparing system 1 according to the present invention will now be described in more detail with reference to Figure 2.

First data processing block 5 comprises a first digital filter 40 presenting an input 40a supplied with data stream I, and an output 40b communicating with the input of a second digital filter 41; digital filter 41 presents a first output 41a communicating with the input of a third digital filter 42, and a second output 41b communicating with a circuit 43; the first output 41a of digital filter 41 presents the filtered (and possibly subsampled) input signal; and the second output 41b presents the remainder, i.e. the input signal of filter 41 minus the signal filtered by it, or the complementary frequency-filtered input signal.

Digital filter 42 presents a first output 42a communicating with the input of a circuit 44, and a second output 42b communicating with a circuit 45; the first output 42a of digital filter 42 presents the filtered (and possibly subsampled) input signal; and the second output 42b presents the remainder, i.e. the input signal of filter 42 minus the signal filtered by it, or the complementary frequency-filtered input signal.

Circuits 43, 44, 45 provide for detecting the reference points of the image, which, in the embodiment described, correspond to the maximum and minimum local brightness points of the image filtered from image S or of the residual image. That is, circuits 43, 44, 45 provide for determining which are the darkest and lightest regions (pixels) in the image filtered from image S.

To distinguish the maximum from the minimum points P, each point is assigned and characterized by a binary flag indicating whether it is a maximum or minimum point. For example, FLAG=1 first type of point (local maximum point), FLAG=0 second type of point (local minimum point).

The outputs of circuits 43, 45, 44 communicate respectively with outputs 5a, 5b, 5c of data processing block 5.

Filters 40, 41, 42 are low-pass filters and conveniently implemented by two-dimensional FIR (finite-impulse-response) filters.

Filters 40, 41, 42 successively filter data stream I so that outputs 5c, 5b, 5a respectively present the low-frequency, medium-frequency and high-frequency content of image S; and filters 40, 41, 42 provide for increasingly "defocusing" image S, as shown in Figures 3a, 3b, 3c, which show images corresponding to the output data of filters 40, 41, 42 respectively.

Second data processing block 6 comprises a first digital filter 50 (identical to filter 40) presenting an input 50a supplied with data stream I', and an output 50b communicating with the input of a second digital filter 51 (identical to filter 41); digital filter 51 presents a first output 51a communicating with the input of a third digital filter 52 (identical to filter 42), and a second output 51b communicating with a circuit 53; the first output 51a of digital filter 51 presents the filtered (and possibly subsampled) input signal; and the second output 51b presents the remainder, i.e. the input signal of filter 51 minus the signal filtered by it, or the complementary frequency-filtered input signal.

Digital filter 52 presents a first output 52a communicating with the input of a circuit 54, and a second output 52b communicating with a circuit 55; the first output 52a of digital filter 52 presents the filtered (and possibly subsampled) input signal; and the second output 52b presents the remainder, i.e. the input signal of filter 52 minus the signal filtered by it, or the complementary frequency-filtered input signal.

Circuits 53, 54, 55 provide for detecting the reference points, in particular the maximum and minimum local brightness points of the image filtered from image S' or of the residual image.

The outputs of circuits 53, 55, 54 communicate respectively with outputs 6a, 6b, 6c of data processing block 6.

Filters 50, 51, 52 successively filter data stream I' so that outputs 6c, 6b, 6a respectively present the low-frequency, medium-frequency and high-frequency content of image S'; and filters 50, 51, 52 provide for increasingly "defocusing" image S', as shown in Figures 4a, 4b, 4c, which show images corresponding to the output data of filters 50, 51, 52 respectively.

Block 10 comprises a circuit 58 supplied with the data from circuits 54 and 44, and presenting an output communicating with a circuit 59 for generating three-dimensional vector A_o(X,Y,alpha).

Circuit 58 is supplied with the reference points, e.g. the local maximum and minimum points of the images filtered from images S and S' and detected by circuits 44 and 54.

Operation of circuit 58 will now be described with reference to Figure 5.

As shown in Figure 5, data P1 comprises a number of points P corresponding to the maximum and minimum local brightness regions of the low-frequency image filtered from image S; and data P4 comprises a number of points Q corresponding to the maximum and minimum local brightness regions of the low-frequency image filtered from image S'.

As a consequence of the relationship between images S and S', a corresponding relationship also exists between points P and Q; and block 10 determines the approximate relationship between images S and S' by determining a possible rotation-translation function relating points P to Q.

More specifically, an analysis is made of a first pair of points, indicated generically by P1,P2, which is compared with all the possible pairs of points Qm,Qn in image S'; and, for each pair of points Qm,Qn, the deformation and rotation-translation transformation function F resulting in points P1,P2 matching respectively with points Qm,Qn is calculated, i.e.<maths id="math0001" num=""><math display="block"><mrow><mtext>F[(P1,P2)] =========&gt;(Qm,Qn)</mtext></mrow></math><img file="EP0768618A2_D0001.tif" /></maths>

Transformation function F is characterized by a set of four parameters X, Y, alpha and delta.

Hereinafter, the deformation parameter delta is disregarded on the assumption that deformation between images S and S' is negligible.

The above operations are repeated for all the other possible pairs of points P, and circuit 58 calculates all the possible transformation functions resulting in a match between all the possible pairs of points P and Q.

Whenever a transformation function characterized by X,Y,alpha is detected, circuit 58 assigns the X,Y pair a complex-value "grade" e^^jalpha, which is added to any "grades" already assigned to the X,Y pair.

When all the possible combinations of X,Y pairs of points P,Q have been considered, each X,Y pair is assigned a complex number equal to the sum of the "grades" obtained for all the possible combinations of pairs of points P,Q.

Circuit 59 determines the X,Y pair obtaining the "grade" sum of maximum absolute value (Figure 6).

Of this grade, the alpha phase representing rotation of the transformation function is also evaluated, so that all the rotation-translation parameters X,Y,alpha are determined.

With reference to Figure 2, block 17 comprises a first circuit 63, which receives data M3 supplied by the first data processing block and representing a number of points P (Figure 7) corresponding to the local maximum and minimum (reference) points of the medium-frequency residual image of reference image S.

For each point P, circuit 63 calculates a neighborhood I defining a small portion of the image for further analysis.

The size of neighborhood I may be defined in various ways. For example, circuit 63 may calculate a circular neighborhood with a radius R equal to half the minimum distance between two points P1 and P2 of the same type (the type being defined by the binary value of the FLAG), or circular neighborhoods with a constant radius R.

In any case, the neighborhoods are calculated separately for minimum and maximum local brightness points P.

Circuit 63 cooperates with a circuit 64, which is also supplied with data M3 and corrected data f(P3) from block 13, so that it receives data corresponding to the points in image S'' (transformed points W) to which the transformation function for compensating the transformation of images S and S' has been applied (via block 13).

Circuit 64 compares points P with points W to enhance the relationship between images S'' and S'.

If the compensation made by block 13 is good, it is reasonable to assume points W come close to points P. More specifically, circuit 64 determines whether a point W falls within the neighborhood of a point P of the same type.

If it does, a matching relationship is established between point P and point W.

The function relating images S and S' is calculated by a circuit 65 cooperating with circuit 64. More specifically, circuit 65 uses the (known) least mean square algorithm, which determines the transformation function minimizing the sum of the squares of the distances between corresponding transformed points P and W. The L.M.S. algorithm of circuit 65 generates vector dA(X,Y,c,s,r,g).

Block 27 presents a structure similar to that of block 17, and comprises a first circuit 73, which receives data M2 supplied by the first data processing block and representing a number of points P (Figure 7) corresponding to the local maximum and minimum points of reference image S.

Like circuit 63 and separately for the maximum and minimum points, circuit 73 calculates a neighborhood I, e.g. a circular neighborhood with a radius R equal to half the distance between a point P and the closest point of the same type.

Circuit 73 cooperates with a circuit 74, which is also supplied with data M2 and corrected data f(P2) from block 23, so that it receives data corresponding to the points in image S''' (transformed points W') to which the transformation function for compensating the geometric relationship of images S and S' has been applied (via block 23).

Circuit 74 compares points P with points W' to enhance the relationship between images S''' and S.

If the compensation made by block 23 is good, it is reasonable to assume points W' come close to points P. More specifically, circuit 74 determines whether a point W' falls within the neighborhood of a point P of the same type.

If it does, a matching relationship is established between points P and W'.

The function relating points P and W' is calculated by a circuit 75 cooperating with circuit 74. More specifically, circuit 75 uses the least mean square algorithm, which determines the affine transformation function minimizing the sum of the squares of the distances between corresponding transformed points P and W'. Circuit 75 generates vector dA2(X,Y,c,s,r,g).

In actual use, initial estimating block 10 is supplied with data P4 and P1 including the reference points P and Q of the images filtered from images S' and S.

As described previously, block 10 compares reference points P and Q, and generates three-dimensional vector A_o(X,Y,alpha), which, by means of a rotation-translation function, defines a first approximation of the function relating images S and S'.

Three-dimensional vector A_o(X,Y,alpha) is supplied to compensating block 13 by which it is used to correct data P3 and generate corrected data f(P3) corresponding to image S'', which thus represents a first correction of detected image S' by system 1.

As described previously, block 17 compares data M3 (image S) and corrected data f(P3) to generate vector dA(X,Y,c,s,r,g), which, by means of a rotation-translation function, defines the affine function relating images S and S''.

Vector dA(X,Y,c,s,r,g) is supplied to block 20 where it is combined with three-dimensional vector A_o(X,Y,alpha) to generate vector A(X,Y,c,s,r,g) defining a second approximation of the relationship between images S and S'.

The output of block 20 is supplied to block 23 following a series of iterative computing cycles in which vector dA(X,Y,c,s,r,g) is successively "refined" by successive calculations. System 1 in fact remains in the closed loop defined by block 17, block 20 and compensating block 13 for a predetermined number of operation cycles, or until the function defined by vector A(X,Y,c,s,r,g) reaches the desired degree of approximation.

Vector A(X,Y,c,s,r,g) is supplied to compensating block 23 by which it is used to correct data P2 and generate corrected data f(P2) corresponding to image S''', which thus represents a second correction of detected image S' by system 1.

As described previously, block 27 compares data M2 (image S) and corrected data f(P2) to generate vector dA2(X,Y,c,s,r,g) defining the affine function relating images S and S'''.

Vector dA2(X,Y,c,s,r,g) is supplied to block 30 where it is combined with vector A(X,Y,c,s,r,g) to generate vector A2(X,Y,c,s,r,g) defining a third approximation of the relationship between images S and S'.

A description will now be given of the operations performed to combine vectors dA2 and A to obtain vector A2.

If A is vector (X,Y,c,s,r,g), and dA2 is vector (dX2,dY2,dc2,ds2,dr2,dg2), then vector A2 (X2,Y2,c2,s2,r2,g2) is given by the following equations:<maths id="math0002" num=""><math display="block"><mrow><mtable><mtr><mtd><mrow><mtable><mtr><mtd><mrow><mtext>X2 = dX2 + dc2X + ds2Y</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext>Y2 = dY2 + dr2X + dg2Y</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext>c2 = dc2c + ds2r</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext>s2 = dc2s + ds2g</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext>r2 = dr2c + dg2r</mtext></mrow></mtd></mtr><mtr><mtd><mrow><mtext>g2 = dr2s + dg2g</mtext></mrow></mtd></mtr></mtable></mrow></mtd></mtr></mtable></mrow></math><img file="EP0768618A2_D0002.tif" /></maths>

If vector A is the output vector of circuit 10, so that <maths id="math0003" num=""><math display="inline"><mrow><mtext>A = (X,Y,alpha)</mtext></mrow></math><img file="EP0768618A2_D0003.tif" /></maths>, the previous formulas may be worked back to by <maths id="math0004" num=""><math display="inline"><mrow><mtext>A = (X,Y,alpha)</mtext></mrow></math><img file="EP0768618A2_D0004.tif" /></maths> being equivalent to a vector <maths id="math0005" num=""><math display="inline"><mrow><mtext>A = (X,Y,c,s,r,g)</mtext></mrow></math><img file="EP0768618A2_D0005.tif" /></maths>, where <maths id="math0006" num=""><math display="inline"><mrow><mtext>c = cos(alpha)</mtext></mrow></math><img file="EP0768618A2_D0006.tif" /></maths>, <maths id="math0007" num=""><math display="inline"><mrow><mtext>s = sin(alpha)</mtext></mrow></math><img file="EP0768618A2_D0007.tif" /></maths>, <maths id="math0008" num=""><math display="inline"><mrow><mtext>g = cos(alpha)</mtext></mrow></math><img file="EP0768618A2_D0008.tif" /></maths> and <maths id="math0009" num=""><math display="inline"><mrow><mtext>r = -sin(alpha)</mtext></mrow></math><img file="EP0768618A2_D0009.tif" /></maths>.

The output of block 30 is normally supplied following a series of iterative computing cycles in which vector A2(X,Y,c,s,r,g) is successively "refined" by successive calculations. System 1 in fact remains in the closed loop defined by block 27, block 30 and compensating block 23 for a predetermined number of operation cycles, or until the function defined by vector A2(X,Y,c,s,r,g) reaches the desired degree of approximation.

Vector A2(X,Y,c,s,r,g) is supplied to a compensating block 100, which corrects data stream I' by means of the function defined by vector A2(X,Y,c,s,r,g), and generates a data set I''' (Figure 1) corresponding to an image S'''' representing the registration of reference image S.

More specifically, the points in image S'''' substantially match those in reference image S, which is therefore "covered" by image S''''.

The system according to the present invention therefore clearly provides for eliminating the drawbacks of known systems by selecting the reference points in the image fully automatically and by means of relatively straightforward computing procedures, and by permitting the selection of a large number of points, normally at least a hundred, and at any rate more than those selectable manually. System 1 also provides for reducing processing time by the reference points being selected by circuits 43,44,45 and 53,54,55, as opposed to manually or by the recognition of predetermined figures in the image.

The equation relating the various images is subsequently calculated by successive approximations (blocks 10,17 and 27) and using straightforward algorithms.

The system according to the present invention also provides for an extremely general image processing approach (the images in fact need not necessarily present recognizable figures) and may therefore be used for comparing a wide range of different images.

The algorithms used are extremely straightforward and "strong" in relation to noise, and provide for a fully automatic calculating procedure.

Clearly, changes may be made to the system as described and illustrated herein without, however, departing from the scope of the present invention.

For example, each data processing block 5, 6 may present a larger number of cascade-connected digital filters and a corresponding number of circuits for detecting the reference points of the filtered images. More generally, system 1 may present data processing blocks 5, 6 with N digital filters, N reference point detecting circuits, and N outputs, in which case, system 1 would present an initial estimating block (of the type defined by block 10) and N-1 refining blocks (like blocks 17 and 27).