JP2962266B2 - Image alignment method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a method of aligning an image to obtain a position where an image to be aligned can be superimposed best on a reference image.

[0002]

2. Description of the Related Art In a conventional registration process between images, an index of a residual or a cross-correlation coefficient is used to evaluate the superposition of images. The alignment process using the statistical properties of the overlapping portion such as the cross-correlation coefficient requires a real number operation, which is problematic in terms of the amount of calculation. On the other hand, registration processing using residuals can be realized only by simple integer arithmetic, and has the merit that high-speed methods such as residual sequential testing can be applied in the process of calculating residuals. , Is often used. For details of these methods, see "Kyoritsu Shuppan, bi
t Separate volume "Computer Science", ACM
Computing Surveys '92, 77-119
Page, "Shokodo, Image Processing Handbook, 303-
305 "The University of Tokyo Press," Image Analysis Handbook ", pp. 707-746" and "Onoe et al.," Superposition of Images by Residual Sequential Test ", Information Processing, Vol.
17, No. 7, page 1976 "and will not be described.

[0003] As described above, the alignment processing using the residual has many advantages as compared with the alignment processing using the cross-correlation coefficient. However, in the conventional alignment processing using the residual, the alignment processing is not performed. , "The target image is completely included in the reference image", and the position where the residual is minimum is obtained. Therefore, when the size and the shape of the overlapping portion change depending on the positional relationship between the images as shown in FIG. 13, the position where the residual is minimized is not always the best result, and may lead to an incorrect result. There was a problem of high performance. Of course, such a problem is avoided in the alignment processing using the statistical property of the overlapping portion such as the cross-correlation coefficient, but the real number operation is required as described above,
Since the high-speed technique cannot be applied, a problem occurs in terms of the amount of calculation.

Therefore, as a method for obtaining the alignment result without being affected by the size and shape of the overlapping portion between the reference image and the target image, Japanese Patent Application Laid-Open No. 2-297148 discloses a method.
Japanese Patent Application Laid-Open Publication No. HEI 9-202, proposes an alignment method. In this method, the reference image and the target image are each mx
n, and the two-dimensional arrays a and b obtained by counting the number of black pixels included in each mesh are created. The two-dimensional arrays a and b are relatively shifted vertically and horizontally. An index D, which is given by the following equation and indicates the goodness of superposition, is calculated.

D = Σi, j | a (xd + i, yd + j)-
b (i, j) | × 1 / S (xd + i, yd + j), (i, j) ∈Exd, Yd: Relative position of two-dimensional arrays a, b E: Area to be operated S: Area of area E and The position where the index D is minimum is set as the approximate position of the superposition.

Next, the document physical structure of the reference image and the target image is analyzed, and each document component is extracted. Based on the extracted document component, each document component is referenced based on the approximate position. Is determined accurately.

[0007]

The above-mentioned JP-A-2-29
According to the technology described in Japanese Patent No. 7148, since the index of the residual of the overlapping area is normalized by the size of the overlapping area, the size and shape of the overlapping portion between the reference image and the target image are used. The approximate position can be obtained without being affected by the above. In addition, since each document component is extracted and the superposition position of each document component is determined based on the approximate position, accurate alignment is possible, and the amount of calculation can be reduced.

[0008] However, in the above-mentioned prior art, an image including a document is targeted, and the alignment is performed by utilizing a document component. Therefore, it cannot be applied to a general image including no document. . Of course, a method of reducing the size of the mesh to be divided to pixel units by using only the first-stage processing of the above-described conventional technique is conceivable, but this causes a problem that the amount of calculation becomes enormous.

Accordingly, the present invention solves such a problem of the prior art, and can perform accurate alignment even when the size or shape of the overlapping portion changes due to the positional relationship between images. And a method capable of high-speed alignment.

[0010]

SUMMARY OF THE INVENTION The present invention relates to a method of aligning an image to obtain a position at which an image to be aligned can be superimposed best on a reference image. Using the similarity measure obtained by normalizing the residual in the overlapping area between the reference image and the target image by the number of elements included in the overlapping area as an index of the good alignment with the image, each overlapping position of the target image with respect to the reference image is used. Among the similarity measures of the candidates, the candidate of the overlap position where the best similarity measure is obtained is set as the registration position of the target image with respect to the reference image. When calculating the similarity measure, the number of elements in the overlapping area of both images based on the candidate for the overlap position and the best similarity measure so far are used in this time. Setting a threshold for calculation abort, and calculating the residual in the overlapping region of both images by the candidate of the current overlap position, when the residual in the middle of the calculation exceeds the threshold, the remaining residual Cancel the difference calculation and proceed to the calculation of the similarity measure in the next candidate of the overlapping position.If the residual calculation is completed without exceeding the threshold, the obtained residual is calculated by the number of elements included in the overlapping area. Updating the best similarity measure with the normalized similarity measure. Further, a value obtained by multiplying the number of elements of the overlapping area by the best similarity measure up to now is set as the threshold value.

As described above, the similarity measure obtained by normalizing the residual in the overlapping area between the reference image and the target image by the number of elements included in the overlapping area is used as an index for evaluating the degree of superposition between images. In addition, accurate alignment can be performed even when the size or shape of the overlapping portion changes due to the positional relationship between the images, and when calculating the similarity measure at a certain overlapping position of the target image with respect to the reference image, the two images may overlap. The value obtained by multiplying the number of elements of the part by the best similarity measure up to now is set as a threshold value used in this similarity measure calculation, and when the residual in the middle of calculation in the overlap region exceeds the threshold, Since it is found that the best value up to that point is not updated, by canceling the residual calculation, the total calculation amount is reduced, and high-speed alignment becomes possible.

[0012]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a block diagram showing an example of the configuration of an alignment processing apparatus 100 for implementing a method according to an embodiment of the present invention. The alignment processing apparatus 100 in this example includes a control unit 1, a position parameter candidate group setting unit 2, a position parameter candidate selection unit 3, an overlapping region setting unit 4, an overlapping region element number calculating unit 5, a overlapping region element selecting unit 6, Functional units such as a residual updating unit 7, a residual initializing unit 8, a residual threshold comparing unit 9, a threshold setting unit 10, a best similarity measure updating unit 11 and a best similarity measure initializing unit 12, and a position parameter candidate memory 13, Image memory 14, overlapping area memory 15,
It has storage units such as a residual memory 16, a threshold memory 17 and a best similarity memory 18, and is connected to a communication unit 20 for performing external communication. Each element in the alignment processing apparatus 100 has the following functions and the like.

The image memory 14 is a memory for storing an image serving as a reference for the alignment processing (reference image), an image to be subjected to the alignment processing (target image), and attribute values such as the size of each image. .

The position parameter candidate memory 13 is a memory for storing a set of position parameter candidates indicating the positions of the target image with respect to the reference image.

The position parameter candidate group setting means 2 is a means for externally acquiring a set of position parameter candidates indicating a position of the target image with respect to the reference image through the communication means 20 and storing the set in the position parameter candidate memory 13. .

The position parameter candidate selection means 3 is a means for sequentially selecting position parameter candidates from the position parameter candidate group stored in the position parameter candidate memory 13 without duplication.

The overlapping area setting means 4 obtains an overlapping area of the two images when the target image is superimposed on the reference image at the position indicated by the position parameter candidate selected by the position parameter candidate selecting means 3. To the overlapping area memory 1
5 is a means for storing.

The overlapping area element number calculating means 5 is a means for calculating the number of elements included in the overlapping area obtained by the overlapping area setting means 4 and storing it in the overlapping area memory 15.

The overlapping area memory 15 stores an overlapping area between the reference image and the target image obtained by the overlapping area setting means 4.
This is a memory that holds the number of elements calculated by the overlapping area element number calculation means 5 for this overlapping area.

The overlapping area element selecting means 6 is a means for sequentially selecting elements in the overlapping area stored in the overlapping area memory 15 without overlapping.

The residual memory 16 is a memory for storing the progress of the residual calculated to obtain a similarity measure which is an index for judging the quality of the position parameter candidate selected by the position parameter candidate selecting means 3. .

The residual initialization means 8 is a means for initializing the values stored in the residual memory 16 prior to the calculation of the residual in the new overlapping area.

The residual updating means 7 obtains a residual from the pixel values of the reference image and the target image corresponding to the elements in the overlapping area selected by the overlapping area element selecting means 6,
This is a means for updating the value in the residual memory 16.

The best similarity measure memory 18 is a position parameter candidate having the best similarity measure among the position parameter candidates for which the similarity measure has already been obtained from the position parameter candidate group stored in the position parameter candidate memory 13. And a memory for holding the number of elements of the overlapping area and the similarity measure obtained by the position parameter candidates.

The best similarity measure initializing means 12 is means for initializing the contents of the best similarity measure memory 18.

The threshold setting means 10 stores, in the best similarity measure memory 18, a threshold used for determining the continuation of the processing and reducing the processing amount of the alignment processing in the processing for obtaining the residual for the overlapping area. This is a means for obtaining the best similarity measure and the number of elements of the overlapping area stored in the overlapping area memory 15 and setting the same in the threshold memory 17.

The threshold memory 17 is a memory for holding the threshold set by the threshold setting means 10.

In the process of calculating the residual for the overlap area, the residual threshold comparing means 9 compares the threshold set in the threshold memory 17 with the residual obtained up to that time to determine the residual. This is a means for determining whether or not a series of processes can be continued, and if the residual exceeds a threshold, suspends the process for obtaining the residual, thereby reducing the processing amount of the positioning process.

The best similarity measure updating means 11 is a position parameter candidate having the best similarity measure among the position parameter candidates for which the similarity measure has already been obtained from the position parameter candidate group stored in the position parameter candidate memory 13. This is a means for storing in the best similarity measure memory 18 the candidates and the number of elements and the similarity measure of the overlapping area obtained from the position parameter candidates.

The control means 1 is a means for controlling each means in accordance with a predetermined procedure in order to determine a position where the target image can be superimposed on the reference image most effectively.

FIG. 2 is a flowchart showing an example of the processing of the alignment processing apparatus 100. Hereinafter, an outline of the operation of the alignment processing apparatus 100 will be described with reference to FIGS. 1 and 2.

First, the control means 1 transmits the target image to be subjected to the positioning process and the reference image to be the reference of the positioning process from the image memory 1 through the communication unit 20.
4 (step A0). Next, the set of position parameter candidates that can be taken by the target image with respect to the reference image is stored in the position parameter candidate memory 13 by the position parameter candidate group setting means 2 (step A1). And
The best similarity measure initializing means 12 initializes the contents of the best similarity measure memory 18 (position parameter candidates to which the best similarity measure has been given, items of the number of elements in the overlapping area obtained by the position parameter candidates, and each item of the similarity measure). (Step A2).

Subsequently, the control means 1 selects one position parameter candidate from the position parameter candidate memory 13 by the position parameter candidate selection means 3 (step A3).
When the selected position parameter candidate is applied to the target image, an overlapping region, which is a portion where the target image and the reference image overlap, is determined by the overlapping region setting means 4 and set in the overlapping region memory 15 (step A4). The number of elements included in the overlapping area is calculated by the overlapping area element number calculating means 5 (step A5).
To be stored. Further, the control means 1 includes a threshold setting means 10
From the number of elements of the overlap area stored in the overlap area memory 15 and the best similarity measure stored so far in the best similarity measure memory 18 (hence, the similarity measure initially initialized in step A2) Threshold memory 17
(Step A6). This threshold value is used in the following procedure for calculating the residual in the overlapping area to determine whether or not the procedure should be interrupted.
Next, the control means 1 initializes the residual memory 16 for storing the progress of the residual calculation by the residual initializing means 8 when obtaining the residual for the overlapping area set by the overlapping area setting means 4. (Step A7).

The control means 1 reads the pixel values of the reference image and the target image corresponding to the elements in the overlapping area selected by the overlapping area element selecting means 6 from the image memory 14 and calculates the residual value from each pixel value. The value in the memory 16 is updated by the residual updating means 7 (steps A8 and A9). The updated value in the residual memory 16 is stored in the residual threshold comparing unit 9.
Is compared with the threshold value in the threshold value memory 17 (step A10). If the value in the residual value memory 16 exceeds the threshold value, the procedure for obtaining the residual value for the overlapping area is interrupted, and the process returns to step A3. The same processing as in step A3 and subsequent steps is performed on the next position parameter candidate in the position parameter candidate group. On the other hand, if the updated value in the residual memory 16 is less than the threshold value, the next element in the overlapping area is selected by the overlapping area element selecting means 6, and the value in the residual memory 16 is similarly updated. Continue the process.

When the processing for updating the values in the residual memory 16 by the residual updating means 7 for all the elements in the overlapping area is completed, based on the obtained result, the best similarity measure memory 18 Position parameter candidates, residuals of the overlap region obtained when the position parameters are applied to the target image, residuals of the overlap region obtained when the position parameters are applied to the target image, and the number of elements included in the overlap region Are updated by the best similarity measure updating means 11 (step A11). Then, returning to step A3, the next position parameter candidate of the position parameter candidate group is selected by the position parameter candidate selection means 3, and the processing after step A3 is repeated.

When all the position parameter candidates in the position parameter candidate group are selected by the position parameter candidate selection means 3 and the above processing is applied to them, the best similarity measure memory 18 stores the position parameter candidate group in the best similarity memory 18. , The position parameter giving the best similarity measure, the similarity measure of the overlapping area obtained by the position parameter, and the number of elements of the overlapping area are stored. The control unit 1 uses these values as the alignment result.

Hereinafter, the operation of the present invention will be described more specifically.

First, the reference image and the target image will be described with reference to FIG. The reference image (I) 101 serving as a reference for the positioning process and the target image (T) 102 serving as the target of the positioning process are, for example, grayscale images in which each pixel takes an integer value in the range of 0 to 255. Reference image 101
Is the pixel value of the pixel at the coordinates (x, y) of I (x, y), and similarly the pixel value of the pixel at the coordinates (x, y) of the target image 102 is T
Expressed as (x, y). The position of the target image 102 is represented by a reference image coordinate system 104 whose origin is the point at the upper left corner of the target image 102 and whose X and Y axes are parallel to the X and Y axes of the respective images.

Next, the reference image 1 will be described with reference to FIGS.
The details of the processing for finding the position where the target image 102 can be superimposed best on 01 will be described.

First, the control unit 1 reads the reference image 101 and the target image 102 into the image memory 14 via the communication unit 20 together with attribute values such as the image size (step A0). Next, position parameter candidate group setting means 2
Reads the position parameter candidate group from the outside via the communication means 20 and stores it in the position parameter candidate memory 13 (step A1).

Here, the position parameter candidate group is a set of positions that the target image 102 can take in the reference image coordinate system 104, and P = ｛(u, v) | U0 ≦ u ≦ U1, V0 ≦ v ≦ V1, u, v, U0, U1, V0, and V1 are represented as integers｝ (Equation 1).

The position parameter candidate group P stored in the position parameter candidate memory 13 is selected sequentially and without duplication by the position parameter candidate selection means 3 as described later. It is assumed that the elements of the position parameter candidate group P are sequentially numbered without duplication in the order selected by the position parameter candidate selection means 3. This number is called a position parameter number.
As an example of the position parameter number, when each element of the set P is considered as a coordinate, a number may be assigned in the order of performing raster scanning, but this number is set for convenience of explanation, It does not affect the essence of the invention.

The control means 1 calculates a similarity measure for each position parameter candidate from the group of position parameter candidates P in order to determine a position parameter at which the target image 102 best overlaps the reference image 101. I do. In the registration process according to the present invention, by using a similarity measure obtained by normalizing the residual defined in the overlapping region generated by the position parameter candidate by the number of elements of the overlapping region,
This solves the problem of residuals, which may lead to erroneous solutions under the influence of changes in the size and shape of the overlapping portion.

When a certain position parameter (u, v) of the position parameter candidate group P is applied to the target image 102, the element in the overlapping area (D) 103 in FIG. Is the set of D, the residual S (u, v) and the similarity measure A in the overlapping area 103
(U, v) is given by: S (u, v) = SUM {D, | I (p, q) -T (pu, qv) |} (Equation 2-1) A (u, v) = S (u, v) ÷ NUM (D) (Equation 2-2). Here, SUM {D, s (p, q)} is the sum of s (p, q) for all the elements (p, q) of the overlapping area D, and NUM (D) is the sum of the elements included in the overlapping area D. Number
Shown respectively. The similarity measure represents a pixel-by-pixel residual in the overlapping area 103. In the overlapping area 103,
The higher the similarity between the reference image 101 and the target image 102 is, the smaller the similarity is.

As a result of the positioning process between the reference image 101 and the target image 102, the control means 1 determines the minimum similarity measure A (u, v) among the position parameters (u, v) in the position parameter candidate memory 13. The position parameter giving v) is selected by the processing of steps A2 to A11 in FIG. Hereinafter, these processes will be described in detail.

First, the control means 1 initializes the data in the best similarity measure memory 18 by the best similarity measure initializing means 12 (step A2). Best similarity measure memory 18
Among the elements of the position parameter candidate group P, among the elements for which the similarity measure has already been obtained, the position parameter candidates (u0, v0) and the best (that is, the smallest) similarity measure A0, A0 that have been given so far. Although the number of elements R0 of the overlapping area D0 obtained by the position parameter candidate is held, at the time of initialization when the similarity measure is not obtained for one element, (u0, v0) and R0 are the initial values. A0 is initialized as A0 ← 255 (Equation 3) without being defined. The value of 255 is 0 to 25 for each image.
This is a similarity measure that is considered to be the maximum (that is, the similarity between the reference image 101 and the target image 102 is the lowest in the overlapping area 103) when the grayscale image has pixel values up to 5.

Next, after step A3 in FIG.
By updating the data in the best similarity measure memory 18 each time a similarity measure smaller than A0 in the best similarity measure memory 18 is obtained, that is, the similarity between the reference image 101 and the target image 102 is higher, the best similarity measure memory 18 is updated. , A process of always holding the similarity measure, the position parameter giving the similarity measure, and the number of elements in the overlapping area.

First, the control means 1 selects the position parameter candidates (u, v) in the position parameter candidate memory 13 in order and without duplication by the position parameter candidate selection means 3. Then, the processing of steps A4 to A11 in FIG. 2 is applied to each element.

In step A4, an overlapping area 103 where the reference image 101 and the target image 102 overlap each other, which is obtained when the selected position parameter candidate (u, v) is applied to the target image 102, is set in the overlapping area setting means 4. Sought,
It is stored in the overlapping area memory 15. Here, overlapping area 1
03 is a rectangular area represented by a set of D = {(p, q) | P0 ≦ p ≦ P1, Q0 ≦ q ≦ Q1, p, q, P0, P1, Q0, and Q1 are integers (Equation 4) Are all pixels included in. Here, P0, P1, Q0, and Q1 are integers determined by the values of the position parameter candidates (u, v) and the size of each image, and are represented by the reference image coordinate system 104.

For example, each image is (0,0) to (15
(U, v) = (80,60) (Equation 5) If D has a size of 160 × 120 pixels represented by coordinates of (9,119), then D = ｛(p, q) | 80 ≦ p ≦ 159, 60 ≦ q ≦ 119, p and q are integers｝ (Equation 6).

In the following, it is assumed that the respective elements of the overlapping area 103 are numbered in an integer from 1 in the order of selection by the overlapping area element selecting means 6 without duplication, and are referred to as overlapping area element numbers. I will. Similar to the position parameter number, as an example of the overlap area element number, a number may be assigned in the order of raster scanning of the overlap area 103, but this is set for convenience to explain the operation of the present invention. , Does not affect the essence of the present invention.

Next, in step A5, the control means 1 determines the number of elements R of the overlapping area 103 by using the overlapping area element number calculating means 5 as follows: R = NUM (D) = (P1-P0 + 1) × (Q1-Q0 + 1) (Equation 7) is obtained and stored in the overlapping area memory 15.

Next, in step A 6, the control means 1 determines the number R of elements of the overlapping area 103 obtained by the above-described overlapping area element number calculating means 5 and the best number obtained in the best similarity memory 18. From the similarity measure A0, the threshold value t defined by t ← A0 × R (Equation 8) is calculated by the threshold value setting means 10 and stored in the threshold value memory 17. This threshold value t
In steps A7 to A11 in the procedure for obtaining the residual for the overlapping area 103, the similarity measure of the overlapping area 103 obtained by the current position parameter candidate (u, v) is expected to update the current best similarity measure A0. Used to determine if there is.

Next, in step A7, the control means 1 initializes the residual of the residual memory 16 by the residual initializing means 8, and in step A8, the element of the overlapping area element number i is changed by the overlapping area element selecting means 6. Every time a selection is made, the residual memory 1 is updated by the residual updating means 7 in step A9.
The residual of 6 is updated. The residual in the overlap area 103 is defined by the above-described equation 2-1. Overlapping area 103
In the procedure for obtaining the residual in, the overlapping area element number i
For (1 ≦ i ≦ R), a partial residual S (i) defined as follows is used.

S (i) = S (i−1) + | I (p (i), q (i)) − T (p (i) −u, q (i) −v) | (Equation 9) Here, S (i): the partial residual for the overlapping area element number i, p (i): the X direction component of the element of the overlapping area element number i, q (i): the Y direction component of the element of the overlapping area element number i, is there. At this time, S (R) = residual in overlap area D (Equation 10). In the present embodiment, the residual for the overlapping region D is obtained by calculating the partial residual S (i) using Equation 9 for all the elements in the overlapping region D. The value of the partial residual S (i) is stored in the residual memory 16 and is initialized by the residual initializing means 8 as S (0) = 0 (Equation 11) at the time of initialization (step A7). Each time the element of the overlapping area element number i is selected by the overlapping area element selecting means 6 (step A8), the element is updated by the residual updating means 7 according to equation 9 (step A9).

FIG. 4 shows an example of a graph for explaining the characteristics of the residual calculation in the overlapping area D. In the graph of FIG. 4, the horizontal axis represents the overlapping area element number i, and the vertical axis represents the value of the partial residual S (i) for the overlapping area element number i. As shown in Equation 9 and the graph of FIG. 4, the partial residual S
(I) monotonically increases as the overlap area element number i increases.

FIG. 5 is a graph for explaining the threshold value t in the present invention. The graph of FIG. 5 shows the position parameter candidates (u which have been given the best similarity measures A0 and A0 among the similarity measures for each of the previously obtained position parameter candidates stored in the best similarity measure memory 18.
0, v0) and its position parameter candidates (u0, v0)
FIG. 6 illustrates the relationship of the residual S0 in the overlap region D obtained by (0). In the graph of FIG. 5, the slope of the straight line connecting the origin and the best similarity measure point 301 representing the current best similarity measure corresponds to A0. The overlap area having the number of elements and the residual of the overlap area corresponding to the point on this straight line has the same similarity measure as the overlap area D0. Number of elements in overlapping area is R
In the case of, the residual corresponding to the point on this straight line is A0 × R (Equation 12).

Since the partial residual S (i) is monotonically increasing with respect to the increase of the overlapping area element number i, if the partial residual S (i) exceeds the threshold value t, S (I
+1) to S (R) also take values larger than t. That is, S (R) ≧ S (R−1) ≧... ≧ S (i + 1) ≧ S (i)> A0 × R (Equation 13) When each side is divided by R (> 0), S (R) ÷ R ≧ S (R−1) ÷ R ≧... ≧ S (i + 1) ÷ R ≧ S (i) ÷ R> A0 × R ÷ R = A0 (Equation 14) holds. This is because when S (i) exceeds A0 × R,
The similarity measure in the overlapping area D is always larger than A0, and there is no possibility that the similarity measure in the overlapping area D will update the current best similarity measure A0 even if the processing of the overlapping area element number i + 1 or later is continued. Is shown.

For all i, if S (i) <A0 × R (Equation 15), then S (R) <A0 × R (Equation 16), the similarity measure in the overlapping area D is From Expression 16, S (R) ÷ R <A0 (Expression 17), and always has a smaller value than the best similarity measure A0.

Using these properties of the similarity measure, the residual, and the number of overlapping area elements, in this embodiment, the threshold t
(= A0 × R) is set, and the calculation amount is reduced and the best similarity measure is updated as follows.

That is, every time the partial residual S (i) is updated in step A9, the threshold t is compared with the updated partial residual in step A10, and if S (i)> t (Equation 18) holds. Then, the partial residual update process in the overlapping area D is stopped, and the procedure returns to the next position parameter candidate selection procedure (step A3). If the expression 18 has never been satisfied and the partial residuals can be updated for all overlapping region elements, the best similarity measure updating unit 11
The best similarity measure A in the best similarity measure memory 18
0, A0 given position parameter candidate (u0, v0) and the overlapping area D obtained by the position parameter candidate
A0 ← S (R) ÷ R (Equation 19-1) (u0, v0) ← (u, v) (Equation 19-2) R0 ← R (Equation 19-3) Update. Then, in order to perform the same processing for the next position parameter candidate, the process that repeats step A3 and thereafter is performed to find the one that gives the best similarity measure among all the position parameter candidates, Determine the position where the image 102 can be best superimposed.

The embodiments of the present invention have been described above.
The present invention is not limited to the above embodiments, and various additions and changes are possible. Hereinafter, the modified examples and the like will be described.

In the above embodiment, the best similarity measure is initialized by Equation 3, but if the best similarity measure can be predicted to some extent, a value closer to the solution may be set as the initial value of the minimum similarity measure. good. As can be seen from FIGS. 4 and 5, the closer the initial value of the best similarity measure is to the solution, the earlier the timing at which the residual calculation is terminated (that is, while the overlapping area element number is small), the processing is interrupted. Therefore, in this case, the calculation amount can be further reduced.

In the above-described embodiment, only the one that gives a parallel movement as a position parameter candidate is targeted. However, the present invention can also be used for more complicated position parameters such as rotation. For example, P = ｛(u, v, θ) | U0 ≦ u ≦ U1, V0 ≦ v ≦ V1, Θ0 ≦ θ, in which a parameter for clockwise rotation about the upper left corner of the image is added to the translation. Similarly, a similarity measure can be defined for ≦ {1} (Equation 20), and the amount of similarity measure calculation can be reduced by a threshold set from the similarity measure up to then and the number of overlapping area elements. It is.

In the above embodiment, the elements included in the overlapping area are all the pixels existing in the overlapping portion between the reference image and the target image. However, as shown in FIG. It is also possible to configure some of the pixels selected according to a certain rule among all the pixels existing in the region as the overlap region element 501, and configure the overlap region with these overlap region elements 501. For example, if only every other pixel in the X direction and every other pixel in the Y direction are set as the overlapping area component 501, the number of overlapping area elements can be reduced to 1/6. Yes, the amount of calculation can be reduced. Since the similarity measure in which the residual is normalized by the number of elements is used, a correct alignment result can be obtained even if the overlapping area element is selectively configured from the overlapping portion of the reference image and the target image. What is possible is a major feature of the present invention.

In the above embodiment, the position parameter candidate group is read from the outside through the communication means 20, but the position parameter candidate group may be set by referring to the image data in the image memory 14. FIG. 6 shows an example of setting the position parameter candidates of the target image 402 with respect to the reference image 401 by this method. The position parameter candidate group 403 is composed of all cases where the target image 402 overlaps the reference image 401. For example, each of the images has a size of 160 × represented by coordinates from (0,0) to (159,119). If the size is 120 pixels, P = {(u, v) | -159≤u≤159, -119≤v≤119)} (Equation 21). This makes it possible to execute the positioning process even when only an image is input without reading the position parameter candidate group from the outside. In addition,
In the above example, the position parameter candidate group composed of all cases where the target image 402 overlaps the reference image 401 is shown. However, information on the position of the camera for acquiring each image and the relative relationship between the images are shown. Is added to the image, the position parameter candidate group can be set to a more limited area by using the information.

Next, an example of the second embodiment of the present invention will be described in detail with reference to the drawings.

The example of the second embodiment is similar to the first embodiment of the present invention, when a similarity measure for a certain position parameter candidate is obtained in the registration processing between images to which an image mask is applied. By terminating the residual calculation using the threshold value, a method of reducing the overall calculation amount and applying high-speed alignment is applied.

FIG. 10 shows an example of an image mask. The image mask holds information indicating whether each pixel of the image is a valid pixel (that is, a pixel to be processed or displayed) or an invalid pixel (that is, a pixel that is not to be processed or displayed). doing. By using an image mask, only a specific range in an image can be subjected to image processing. FIG. 10 shows that pixels corresponding to an elliptical area at the center of the image are valid pixels, and elements outside the elliptical area are invalid pixels. The image processing using an image mask is described in detail in "Shokodo," Image Processing Handbook ", pp. 252 to 254, and will not be described here.

FIG. 11 is a diagram for explaining the registration process between images to which the image mask is applied. In FIG. 11, a reference image serving as a reference for the alignment processing and a target image to be subjected to the alignment processing form an overlapping area D. Among the elements of the overlapping area D, the superimposition of images is evaluated. The target for which the similarity measure, which is the index to be calculated, is an element included in the effective overlapping area E in which both the reference image and the target image have effective pixels.

As described in the first embodiment of the present invention, the number of elements included in the effective overlapping area E can be reduced even when the effective overlapping area between the images is not rectangular, such as in the alignment processing using an image mask. By terminating the residual calculation based on the threshold value obtained from the best similarity measure up to that time, the overall calculation amount is reduced, and high-speed alignment is possible.

However, when the shape of the effective overlapping area E is complicated, it may be difficult to systematically determine the number of elements included in the effective overlapping area E (the number of effective overlapping area elements). In this case, the processing cost in the process of obtaining the number of elements of the effective overlapping area increases, and a problem may occur in which the effect of the present invention of terminating the residual calculation using the threshold is lost.

In this embodiment, in order to avoid this problem and perform high-speed alignment even in the alignment process between images using an image mask, a similarity measure for a certain position parameter candidate is calculated. , A value obtained from the number of elements of the overlapping area between the reference image and the target image, the number of invalid area elements (or the number of valid area elements), and the best similarity measure up to that time is used as a threshold value. .

Hereinafter, a second embodiment of the present invention will be described in detail with reference to the drawings.

FIG. 8 is a block diagram showing an example of the configuration of a positioning apparatus 200 for implementing the method of the second embodiment of the present invention. The alignment processing apparatus 200 of this example includes a positioning processing apparatus 100 that performs the method of the first embodiment.
In the functional unit, the area element number initialization means 3
1, area element number updating means 32, area element determining means 33
However, the storage unit has a configuration in which a mask memory 34 and a region element number memory 35 are added. Each element in the alignment processing apparatus 200 has the following functions and the like.

Referring to FIG. 8, among the components of the alignment processing apparatus 200 for implementing the method according to the second embodiment of the present invention,
Control means 1, position parameter candidate group setting means 2, position parameter candidate selection means 3, overlapping area setting means 4, overlapping area element number calculating means 5, overlapping area element selecting means 6, residual updating means 7, residual initialization The means 8, the residual threshold value comparing means 9, the best similarity measure initializing means 12, the position parameter candidate memory 13, the image memory 14, the overlapping area memory 15, the residual memory 16, and the threshold memory 17 are shown in FIG. 1
It has the same function as the element of the same name described in the alignment processing apparatus 100 that performs the method of the embodiment.

Further, in FIG. 1, the threshold setting means 10, the best similarity measure updating means 11, the best similarity means having the same names as the means described in the positioning processing apparatus 100 for implementing the method of the first embodiment of the present invention. The measure memories 18 are:
It has the following functions.

The threshold setting means 10 stores, in the best similarity measure memory 18, a threshold used for determining the continuation of the processing and reducing the processing amount of the alignment processing in the processing for obtaining the residual for the overlapping area. From the best similarity measure, the number of elements of the overlapping area stored in the overlapping area memory 15, and the number of area elements stored in the area element number memory 35, and set them in the threshold memory 17.

The best similarity measure updating means 11 selects the position parameter having the best similarity measure among the position parameter candidates for which the similarity measure has already been obtained from the position parameter candidate group stored in the position parameter candidate memory 13. Candidates, the number of elements of the overlapping area obtained by the position parameter candidate, and the number of area elements and the best similarity measure indicating the number of elements of the effective overlapping area or the number of elements of the invalid overlapping area obtained by the position parameter candidate, It is stored in the best similarity measure memory 18.

During the processing, the best similarity measure memory 18 stores the best similarity measure that has been obtained up to now, the position parameter candidate to which the similarity measure has been given, and the overlapping area obtained by the position parameter candidate. This is a memory for storing the number of elements and the number of area elements.

Further, a region element number initializing unit 31, a region element number updating unit 32, and a region adding unit are added in comparison with the positioning processing apparatus 100 for executing the method of the first embodiment of the present invention in FIG. Element determination means 33, mask memory 3
4. The area element number memory 35 has the following functions.

The mask memory 34 determines whether each pixel of the image stored in the image memory 14 is an effective image (that is, a pixel to be processed or displayed) or an invalid pixel (that is, a pixel to be processed or displayed). This is a memory that stores an image mask that indicates whether the pixel is an unrecognized pixel.

The area element number memory 35 stores the number of invalid area elements indicating the number of elements in which either (or both) of the reference image and the target image are invalid pixels among the elements of the overlapping area, It is a memory for storing the number of effective area elements indicating the number of elements in which both of the images are effective pixels.

The area element number initializing means 31 is means for initializing the number of area elements in the area element number memory 35.

The area element determining means 33 determines whether or not the element of the given overlapping area is an element to be subjected to similarity measure calculation with reference to the mask memory 34.

The area element number updating means 32 is means for updating the number of area elements in the area element number memory 35 according to the type of the overlapping area element determined by the area element determining means 33.

FIG. 9 is a flowchart showing an example of the processing of the alignment processing apparatus 200.

Hereinafter, an outline of the operation of the positioning apparatus 200 will be described with reference to FIGS.

The control means 1 first reads the target image to be subjected to the positioning processing and the reference image to be the reference of the positioning processing into the image memory 14 and the respective image masks into the mask memory 34 by the communication means 20. (Step B0). Next, position parameter candidate group setting means 2
Thus, a set of position parameter candidates that can be taken by the target image with respect to the reference image is stored in the position parameter candidate memory 13 (step B1). Then, each value included in the best similarity measure memory 18 is initialized by the best similarity measure initializing means 12 (step B2).

Subsequently, the control means 1 selects one position parameter candidate from the position parameter candidate memory 13 by the position parameter candidate selection means 3 (step B3).
When the selected position parameter candidate is applied to the target image, an overlapping region, which is a portion where the target image and the reference image overlap, is determined by the overlapping region setting means 4 and set in the overlapping region memory 15 (step B4). Also, the number of all elements included in the overlapping area is calculated by the overlapping area element number calculating means 5 (step B5), and each is stored in the overlapping area memory 15. Further, the control means 1 initializes the number of invalid areas and the number of valid areas included in the overlapping area, stored in the area element number memory 35, by the area element number initializing means 31 (step B6). . Then, before starting the process of obtaining the residual for the element to be subjected to the similarity measure calculation among the elements included in the overlapping area set by the overlapping area setting means 4,
The residual memory 16 for storing the progress of the residual calculation is initialized by the residual initialization means 8 (step B7).

The control means 1 selects one element in the overlapping area by the overlapping area element selecting means 6 (step B8), and the area element determining means 33 controls the reference image and the target image stored in the mask memory 34, respectively. It is determined whether the selected overlapping area element is an effective area element to be subjected to similarity measure calculation or an invalid area element not to be subjected to similarity measure calculation from the information of the image mask (step B9).

When the selected overlapping area element is an effective area element, the positioning processing apparatus 1 according to the first embodiment is used.
In FIG. 2 which is a flowchart showing an example of the process of 00, the partial residual in the residual memory 16 is updated by the same procedure as the process of updating the partial residual (step A9) (step B10). Then, the number of area elements is updated (step B11), and the threshold setting unit 10 includes the best similarity measure stored in the best similarity measure memory 18 and the overlapped area stored in the overlapped area memory 15. A threshold is obtained from the total number of elements to be read and the number of invalid area elements or the number of valid area elements in the area element number memory 35, and is set in the threshold memory 17 (step B12). And FIG.
The partial residual in the residual memory 16 is compared with the threshold in the threshold memory 17 by the same procedure as step A10 in step B13 (step B13). If the partial residual exceeds the threshold, the similarity measure for the current position parameter Stop the calculation,
Step B3 and subsequent steps are repeated. If the partial residual is smaller than the threshold value, step B8 and subsequent steps are repeated to apply the processing to other overlapping region elements.

If the selected overlapping area element is an invalid area element, the partial residual in the residual memory 16 is updated (step B15) and stored in the area element number memory 35 by the area element number updating means 32. The number of invalid area elements and the number of valid area elements are updated (step B16), and step B8 and subsequent steps are repeated to apply processing to other overlapping area elements.

In step B8, when the processing after step B8 is applied to all the overlapping area elements generated by the current position parameter candidates, the best similarity measure updating means 11 stores the data in the residual memory 16. Partial residual, the total number of elements included in the overlapping area stored in the overlapping area memory 15, and the area element number memory 35.
The similarity measure is calculated from the number of invalid area elements or the number of effective area elements included in the overlapping area stored in the best similarity measure memory 18 and the best similarity measure stored in the best similarity measure memory 18 is updated.
At the same time, the current position parameter candidate, the total number of elements included in the overlapping area obtained by the position parameter candidate, and the number of invalid area elements or valid area elements are stored in the best similarity measure memory 18 (step B14). Then, in order to obtain a similarity measure for another position parameter candidate, the steps from step B3 are repeated.

If it is determined in step B3 that the position parameter candidate selection means 3 has applied the processing from step B4 to all the position parameter candidates,
The process ends. At this time, the similarity measure stored in the best similarity measure memory 18 is the best similarity measure for the position parameter candidate group.
Are the position parameters obtained as a result of the positioning process.

Hereinafter, the operation of the second embodiment of the present invention will be described more specifically.

In FIG. 11, it is assumed that the pixel values and positions of the reference image I601 and the target image T602 are expressed in the same manner as in the first embodiment.

In this embodiment, the image mask has the same size as the reference image and the target image, and is represented by a binary image having a value of 1 for an effective pixel and a value of 0 for an invalid pixel. . That is, the image mask of the reference image I is set to Mi (x,
y), assuming that the image mask of the target image is Mt (x, y), Mi (x, y) = 0: when I (x, y) is an invalid pixel (Equation 21-1) = 1: I (x , Y) is an effective pixel (Equation 21-2) Mt (x, y) = 0: T (x, y) is an invalid pixel (Equation 22-1) = 1: T (x, y) is In the case of an effective pixel (Equation 22-2). When the pixel at the target position (x, y) is an invalid pixel, the pixel is not subjected to image processing such as alignment processing.

Although the form of the image mask in this embodiment is a binary image for the sake of explanation, this does not limit the scope of the present invention. Any method can be used as long as it can determine whether each pixel is an effective pixel or an invalid pixel. Other forms such as a multi-valued image or a conversion table in which invalid pixel positions are recorded can also be used. Although different image masks are used for each image, a single image mask can be used as long as the size and shape of the effective pixel area of each image are the same.

First, the control means 1 reads the reference image I 601 and the target image T 602 together with the attribute values such as the image size into the image memory 14 and the respective image masks Mi and Mt into the mask memory 34 via the communication means 20. (Step B0) The position parameter candidate group setting means 2 reads the position parameter candidate group from the outside into the position parameter candidate memory 13 via the communication means 20 (Step B1). The position parameter candidate group is a set of positions that the target image T602 can take in the reference image coordinate system 604, and is expressed by Expression 1 as in the first embodiment. Each element of the position parameter candidate group P In accordance with the position parameter number, the position parameter candidate selection means 3 selects them sequentially and without duplication. The position parameter numbers are set for convenience of description, and do not affect the essence of the present invention, as in the first embodiment.

The control means 1 calculates a similarity measure for each position parameter candidate in order to determine a position parameter at which the target image T602 overlaps best with the reference image I601. A similarity measure similar to that of the embodiment, that is, a similarity measure obtained by normalizing the residual defined by the effective overlap region generated by the position parameter candidate by the number of elements of the effective overlap region is used. At this time, when a certain position parameter (u, v) of the position parameter candidate group P is applied to the target image T602, the reference image I601 and the target image T602 overlap.
, The residual S (u, v) and the similarity measure A (u, v) are: S (u, v) = SUM ｛E, | I (p, q) -T (pu) , Q−v) |｝ (Equation 23-1) A (u, v) = S (u, v) ÷ NUM (E) (Equation 23-2)

Next, as in the first embodiment, the control means 1 initializes each item included in the best similarity measure memory 18 (step B2). That is, the best (smallest) similarity measure A0 up to that point is initialized according to Equation 3.

The processing after step B3 in FIG.
Step A3 in the example of implementing the method of the first embodiment
As in the subsequent processing, A in the best similarity measure memory 18
By updating the data in the best similarity measure memory 18 each time a similarity measure smaller than 0, that is, a higher similarity between the reference image I601 and the target image T602 is obtained,
The best similarity measure, a position parameter that gives the similarity measure, and the number of elements in the overlapping area are always held.

In this embodiment, the reference image I601 and the target image T6 obtained when the position parameter candidate (u, v) is applied to the target image T602 in step B4.
02 is obtained by the overlapping area setting means 4 and stored in the overlapping area memory 15. At this time, the overlapping area D603 is all positions included in the rectangular area expressed by Expression 4, as in the example of implementing the method of the first embodiment. This overlapping area is obtained irrespective of the shape of the image mask, and the number of elements R is calculated by the overlapping area element number calculating means 5 in accordance with Expression 7 in the same manner as in the example in which the method of the first embodiment is performed. Can be obtained systematically (step B5). In the following, each element of the overlapping area D603 has an overlapping area element number as an integer without a duplication from 1 in the order selected by the overlapping area element selecting means 6, as in the example of implementing the method of the first embodiment. It shall be added. This is set for convenience in describing the operation of the present invention, and does not affect the essence of the present invention.

Each element included in the overlapping area can be classified into either an effective area element for which the similarity measure is to be calculated or an invalid area element which is not to be calculated for the similarity measure. The effective area element is an overlapping area element in which both pixels of the reference image I601 and the target image T602 are effective pixels. If one (or both) of the pixels is an invalid pixel, the element is an invalid area element. That is, the overlapping area D603 can be divided into two, an effective overlapping area E605 composed of valid area elements, and an invalid overlapping area F606 composed of invalid area elements.

As shown in Expressions 23-1 and 23-2, the similarity measure for the position parameter candidate (u, v) is defined in the effective overlapping area E605, and is processed in the same manner as in the first embodiment. In order to set the threshold value and the similarity measure itself for speeding up, it is necessary to obtain the number of elements Re (= NUM (E)) of the effective overlapping area E605. However, when the shape of the image mask is complicated, it cannot be obtained systematically, and the overlapping area D603
It is necessary to determine the number of effective area elements by checking whether or not all elements are effective area elements with reference to the image mask. However, this processing requires the same processing cost as the processing for obtaining the residual in the overlap region D603, and the effect of the reduction in the amount of calculation due to the termination of the residual calculation using the threshold in the first embodiment of the present invention is impaired. Problem. Therefore, in the present embodiment, the number of elements included in the effective overlapping area E605 is not calculated first, and the partial residual is updated while selecting each element in the overlapping area D603 in order and without duplication. In the process, this problem is solved by setting a threshold value in consideration of the number of invalid area elements included in the already processed overlapping area elements.

Therefore, the number F of invalid area elements found so far stored in the area element number memory 35
(I) and the number of effective area elements E (i) are initialized by E (0) ← 0 (Equation 24-1) F (0) ← 0 (Equation 24-2) (step B6). Further, similarly to step A7 in the example of implementing the method of the first embodiment,
The partial residual S stored in the residual memory 16 and used to determine the residual for the effective overlap area E605
(I) is initialized by S (0) ← 0 (Equation 25) (Step B7).

Next, the following processing is applied to each overlapping area element i (1 ≦ i ≦ R) included in the overlapping area D603 (step B8).

First, the area element determination means 33 determines whether the overlapping area element i is an effective area element or an invalid area element by referring to the reference image and the image mask of the target image (step B9). That is, if Mi (p (i), q (i)) = 1 and Mt (p (i) -u, q (i) v) = 1 (Equation 26-1), the overlapping area element i is valid. If the element is a region element and does not satisfy this condition, that is, Mi (p (i), q (i)) = 0 or Mt (p (i) -u, q (i) -v) = 0 (Equation 26) -2) If, the overlapping area element i is an invalid area element. Here, similarly to the description of the example of implementing the method of the first embodiment, p (i): the X-direction component of the element of the overlapping area element number i q (i): the Y of the element of the overlapping area element number i It is a directional component.

If the overlapping area element i is an invalid area element, the value of the partial residual S (i) is updated by the residual updating means 7 according to S (i) ← S (i-1) (Equation 27). E (i) ← E (i−1) (Equation 28-1) F (i) ← F (i−1) +1 (Equation 28−) 2) The number of effective area elements E (i) and the number of invalid area elements F according to
(I) is updated (step B16).

If the overlapping area element i is not an invalid area element, that is, if the overlapping area element i is an effective area element, the residual updating unit 7 executes the same processing as in the description of the example of implementing the method of the first embodiment. S (i) = S (i-1) + | I (p (i), q (i))-T (p (i) -u, q (i) -v) | The residual S (i) in the memory 16 is updated (step B10). Further, the number of effective area elements E (i) and the number of invalid area elements F
(I) is updated to E (i) ← E (i-1) +1 (Equation 30-1) F (i) ← F (i-1) (Equation 30-2) (Step B11).

FIG. 12 is a graph for explaining the threshold value T (i) in the second embodiment of the present invention. As shown in FIG. 5 for explaining the method of the first embodiment, FIG. FIG. 7 illustrates the relationship between residual parameters and the number of effective overlapping regions R0 obtained by the best similarity measure A0, A0 among the similarity measures for the respective position parameter candidates. It is. In the graph of FIG. 12, the slope of a straight line connecting the origin and the best similarity measure point 301 representing the current best similarity measure A0 corresponds to A0. The number of elements corresponding to the point on this straight line and the effective overlapping area giving the residual are the similarity measure points 30
It has the same similarity measure as the effective overlapping area obtained by the position parameter candidate giving 1.

In FIG. 12, a point 701 indicates a point corresponding to the initial threshold value. At this time, the overlapping area D60
3 is a threshold value when all of the overlapping area elements included in 3 are regarded as effective area elements. However, the overlapping area D60
5 includes an invalid area element, the threshold value is larger than the true threshold value A0 × Re for the valid area element E605, and when the residual calculation for the effective overlapping area E605 is continued without changing the threshold value, If the number of elements Re of the overlapping area element E605 is known in advance, a residual update process that is not necessary may be included.

Finding an invalid area element in the process of residual calculation is equivalent to increasing the lower limit of the number of invalid area elements included in the overlapping area D603, that is, the lower limit of the number of elements of the invalid overlapping area F606. Overlapping area D
The upper limit of the number of elements of the effective area included in the effective area 603, that is, the effective overlapping area E605 is reduced. This means that the threshold value can be reduced. In the second embodiment of the present invention, the threshold value T (i) for the overlapping area element i is calculated as follows: T (i) ← A0 × (R−F (i)) (Equation 31-1) or T (i) = A0 × (R−i + E (i)) (Equation 31-2) (Step B12).

Here, the relationship between the threshold value T (i) and the partial residual S (i) will be considered.

In this embodiment, in step B9, the area element determining means 33 determines whether the overlapping area element i is an effective area element or an invalid area element, and the overlapping area element i is not an invalid area element ( In other words, the partial residual is added based on Equation 29 only when the element is an effective area element), so that S (1) ≦ S (2) ≦ ... ≦ S (i) ≦ ... ≦ S (R) = residual in the effective overlap area E605 (Equation 32)

From equations 28-2 and 30-2, the number of invalid area elements F (i) monotonically increases with respect to i.
The number of invalid area elements F (R) when processing is applied to all overlapping area elements matches NUM (F), and each overlapping area element is always classified as either an invalid area element or a valid area element. Therefore, 0 = F (0) ≤F (1) ≤ ... ≤F (i-1) ≤F (i) ≤F (i + 1) ≤ ... ≤F (R) = NUM (F) = R-Re (Equation 33-1) 0 = E (0) ≤E (1) ≤ ... ≤E (i-1) ≤E (i) ≤E (i + 1) ≤ ... ≤E (R) = NUM (E) = Re (Equation 33-2) i = F (i) + E (i) (Equation 33-3) holds. Applying Equation 31-1 to Equation 33-1 gives T (1) = A0 × (R−F (1)) = A0 × R ≧
T (2) = A0 × (R−F (2)) ≧ ... ≧ T (i) = A
0 × (R−F (i)) ≧ ... ≧ T (R) = A0 × (R−F
(R)) = A0 × Re (Equation 34-1), and the original threshold value A0 for the effective overlap area E605
T (1) ≧ T (2) ≧... ≧ T (i) ≧... ≧ T (R) = A0 × Re (Formula 34-2) holds between × Re and T (i). This is equivalent to the threshold value T (i) determined by equation 31.
Indicates that the threshold value converges to the original threshold value for the effective overlap area E605. In FIG. 12, the point corresponding to the threshold value corresponds to the true threshold value for the effective overlap area E605 from the point 701 corresponding to the initial threshold value. This corresponds to gradually moving to the point 702.

Here, the partial residual S (i) is equal to the threshold T (i).
, Since S (i) increases monotonically, S (R) ≧ S (i)> T (i) ≧ A0 × Re (Equation 35), and each term is expressed as Re (> 0). A (u, v) = S (R) ÷ Re ≧ S (i) ÷ Re> A0 × (R−F (i)) ÷ Re ≧ A0 (Equation 36) This is because the partial residual S (i) is equal to the threshold T (i)
In the case of exceeding, it indicates that the similarity measure in the effective overlap area E605 is always larger than the best similarity measure A0, and as in the example of the method in the first embodiment, the similarity measure is equal to or less than the overlap area element i + 1. This indicates that there is no possibility of updating the best similarity measure even if the processing is continued. Therefore, the residual threshold comparing means 9 calculates the partial residual S (i) and the threshold T
By comparing (i), it is determined whether to continue the processing for the overlapping area D605 (step B13). That is, if S (i)> T (i) (Equation 37) holds, the processing for the position parameter candidate is interrupted, and the process proceeds to step B3 for the next position parameter candidate.
The subsequent similarity measure calculation processing is applied again. Equation 3
If No. 7 is not satisfied, the processing after step B8 is applied to the next overlapping area element i + 1.

Conversely, if Equation 37 does not hold for all i, ie, if S (R) ≦ T (R) (Equation 38) holds, then from Equation 31, S (R) ≦ T ( R) = A0 × (R−F (R)) = A0 × (RR−E (R)) = A0 × Re (Equation 39) When each term is divided by Re (> 0), A (u, v) = S (R) ÷ Re ≦ A0 (Equation 40), and the similarity measure of the effective overlapping area E605 updates the best similarity measure A0. Therefore, when the processing after step B9 is applied to all the overlapping area elements, the best similarity measure updating means 11 updates each item stored in the best similarity measure memory 18 (step B13).
That is, the best similarity measure, the position parameter candidate given the best similarity measure, the total number of elements of the overlapping area, the number of invalid area elements, and the number of effective area elements obtained from the position parameter candidate are represented by the best similarity measure A0 ← S (R) ÷ (R−F (R)) (Equation 41-1) Position parameter candidate ← (u, v) (Equation 41-2) Number of overlapping area elements ← R (Equation 41-3) Number of invalid overlapping area elements ← F ( R) (Equation 41-4) The number of effective overlapping area elements ← E (R) (Equation 41-5) is updated.

In the above description, step B1
5, the value of the partial residual S (i), the value of the number of effective area elements E (i) in Step B16, and the value of the number of invalid area elements F (i) in Step B11 are expressed by Equation 2
7, but have been described as being updated by Expression 28-1 and Expression 30-2, but this is for convenience of description, and the application of the present invention is not limited to this. Since the respective values do not change before and after each update process, the partial residual in the residual memory 16 and the number of effective area elements and the number of invalid area elements in the area element number memory 35 are each represented by one register. If they do, these update processes are not required. Also, since there is always the relationship of Expression 33-3 between the number of valid area elements and the number of invalid area elements, it is necessary to record / update only one of the number of valid area elements and the number of invalid area elements. Is also possible.

In the second embodiment of the present invention, the same extension as in the first embodiment is possible.

That is, in the description of the second embodiment, only the position parameter candidate that gives a parallel movement is used, but the present invention can be used for more complicated position parameters such as rotation. As shown in FIG. 7, some pixels selected according to a certain rule among all pixels existing in the overlapping portion between the reference image and the target image are set as overlapping region elements, and the overlapping region D is determined by these overlapping region elements. Can also be configured. Further, in the above description, the position parameter candidate group is read from the outside through the communication means 20, but the position parameter candidate group may be set with reference to the image data in the image memory 14. Furthermore, although the position parameter candidate group composed of all cases where the target image overlaps the reference image is shown, information on the position of the camera for acquiring each image and information indicating the relative relationship between the images are not shown. In the case where the position parameter candidate is added to an image, the position parameter candidate group can be set to a more limited area by using the information.

[0124] Positioning of an image targeted by the present invention is one of the basic processes of image processing, and therefore can be applied to various image processing fields. In the prior patent application (Japanese Patent Application No. 08-26350), the present applicant acquires a plurality of target partial images captured by an imaging device by moving the imaging device, and synthesizes a composite image from the partial image group by image synthesis processing. Although an image input device for generating images has been proposed, the present invention is of course applicable to image alignment in image synthesis processing in such an apparatus.

[0125]

As described above, according to the present invention, the following effects can be obtained.

The first effect is that the target image is superimposed best on the reference image without being affected by changes in the size and shape of the overlapping portion between the reference image and the target image. That is, it is possible to accurately determine the position at which it can be performed. This does not use the residual itself in the overlapping area between the reference image and the target image as an index,
This is because the goodness of alignment between the reference image and the target image is evaluated using the similarity measure obtained by normalizing the residual by the number of elements of the overlapping area as an index.

The second effect is that high-speed positioning can be performed. This is because, in the process of calculating the similarity measure at each overlapping position of the target image with respect to the reference image, the residual in the middle of the calculation exceeds the threshold set from the best similarity measure up to then and the number of elements in the overlapping area, This is because, when there is no longer any possibility of updating the measure, the calculation of the residual is cut off to reduce the amount of calculation.

The third effect is that, even in the alignment process between images having a complex shape using an image mask, the size and shape of the overlapping portion between the reference image and the target image are not affected by the change. That is, a position where the target image can be superimposed best on the reference image can be accurately obtained. This is not to use the residual itself in the overlapping area between the reference image and the target image as an index, but to use the similarity measure obtained by normalizing the residual by the number of elements of the overlapping area as an index to determine the position between the reference image and the target image. This is because they are evaluating the suitability.

A fourth effect is that high-speed positioning can be performed even in a positioning process between images having a complicated shape using an image mask. This is because, in the process of calculating the similarity measure at each overlapping position of the target image with respect to the reference image, the residual in the middle of the calculation is the best similarity measure up to that point, the number of elements in the overlapping area, and the similarity measure target found so far. From the number of effective area elements (or the number of invalid area elements that are not subject to similarity measure calculation), and when the threshold value is exceeded, it is determined that the best similarity measure is no longer likely to be updated. This is because the amount of calculation is reduced by terminating the calculation of the difference.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an example of a configuration of a positioning processing apparatus that performs a method of the present invention.

FIG. 2 is a flowchart illustrating an example of a process performed by a registration processing apparatus that implements the method of the present invention.

FIG. 3 is an explanatory diagram of a reference image and a target image.

FIG. 4 is a diagram illustrating an example of a graph for explaining a feature of residual calculation in an overlapping region between a reference image and a target image.

FIG. 5 is a diagram illustrating an example of a graph for explaining a threshold according to the present invention.

FIG. 6 is an explanatory diagram of a method of setting a position parameter candidate group with reference to image data in an image memory.

FIG. 7 is an explanatory diagram of an example in which some of the pixels existing in an overlapping portion between a reference image and a target image are selected as overlapping region elements.

FIG. 8 is a block diagram illustrating an example of a configuration of a positioning processing apparatus that performs the method of the present invention.

FIG. 9 is a flowchart illustrating an example of a process performed by a registration processing apparatus that implements the method of the present invention.

FIG. 10 is an explanatory diagram for explaining an image mask.

FIG. 11 is an explanatory diagram of a reference image and a target image according to a second embodiment of the present invention.

FIG. 12 is a diagram illustrating an example of a graph for explaining a threshold value according to the second embodiment of the present invention.

FIG. 13 is an explanatory diagram of a problem of the related art.

[Explanation of symbols]

 REFERENCE SIGNS LIST 1 control means 2 position parameter candidate group setting means 3 position parameter candidate selecting means 4 overlapping area setting means 5 overlapping area element number calculating means 6 overlapping area element selecting means 7 residual updating means 8 residual initializing means 9 residual threshold comparing Means 10 Threshold setting means 11 Best similarity measure updating means 12 Best similarity measure initializing means 13 Position parameter candidate memory 14 Image memory 15 Overlapping area memory 16 Residual memory 17 Threshold memory 18 Best similarity measure memory 20 Communication means 31 Initial number of area elements Converting means 32 area element number updating means 33 area element number determining means 34 mask memory 35 area element number memory 100 positioning processing apparatus 101 reference image I 102 target image T 103 overlapping area D 104 reference image coordinate system 200 positioning processing apparatus 301 Point that gives the current best similarity measure 4 1 Reference Image 402 Target Image 403 Position Parameter Candidate Group 501 Overlapping Area Element 600 Image Mask 601 Reference Image I 602 Target Image T 603 Overlapping Area D 604 Reference Image Coordinate System 605 Effective Overlapping Area E 606 Invalid Overlapping Area F 701 Initial Threshold Point 702 Optimal threshold point

Continuation of front page (58) Field surveyed (Int.Cl. ⁶ , DB name) G06T 7/00

Claims (8)

(57) [Claims] An image positioning method for determining a position where an image to be aligned can be superimposed best on a reference image, the method comprising: As an index, using a similarity measure obtained by normalizing the residual in the overlapping area between the reference image and the target image by the number of elements included in the overlapping area, among the similarity measures in the candidates for each overlapping position of the target image with respect to the reference image, In a method in which the candidate of the overlapping position where the best similarity measure is obtained is used as the alignment position of the target image with respect to the reference image, when the similarity measure of each candidate of the overlapping position of the target image with respect to the reference image is obtained, the current overlapping position From the number of elements in the overlapping region of both images by the candidate and the best similarity measure so far, the threshold for calculation discontinuation used in this similarity measure calculation is In the step of setting, and in the process of calculating the residual in the overlap region of both images due to the candidate of the current overlap position, if the residual in the middle of calculation exceeds the threshold, the remaining residual calculation is stopped and the next Proceed to the calculation of the similarity measure for the candidate of the overlapping position, and when the residual calculation is completed without exceeding the threshold, the obtained residual is best calculated by the similarity measure normalized by the number of elements included in the overlapping area. Updating the similarity measure. 2. The method according to claim 1, wherein a value obtained by multiplying the number of elements of the overlapping area by the best similarity measure so far is used as the threshold. 3. The method according to claim 2, wherein a candidate for an overlapping position of the target image with respect to the reference image is read from an external device. 4. The method according to claim 2, wherein an overlapping position of the target image with respect to the reference image is automatically set based on the reference image and the target image. 5. An image alignment method for obtaining a position at which an image to be aligned with a reference image can be superimposed best on an image as a reference by image processing using an image mask, the method comprising: As an index of good alignment with the target image, a similarity measure obtained by normalizing a residual in an overlap region between the reference image and the target image by the number of elements included in the overlap region is used, and each overlap of the target image with the reference image is used. A method of determining, from among the similarity measures of the position candidates, the candidate of the overlapping position at which the best similarity measure is obtained as the alignment position of the target image with respect to the reference image, comprising: Calculating the residual in the overlapping region of both images of the image, the similarity measure in each candidate of the overlapping position of the target image with respect to the reference image; When calculating, the number of elements in the overlapping area of both images due to the candidate for the current overlap position, the best similarity measure so far, and the number of effective area elements or similarity measure targets to be calculated for the similarity measure confirmed so far Setting a threshold for calculation termination to be used in this similarity measure calculation from the number of invalid area elements that do not result in the calculation. If the residual in the middle of the calculation exceeds the threshold, the remaining residual calculation is stopped and the next Proceed to the calculation of the similarity measure in the candidate of the overlapping position, and when the residual calculation is completed without exceeding the threshold, the obtained residual is calculated by the similarity measure normalized by the number of elements included in the overlapping area. Updating the best similarity measure. 6. The threshold value is a value obtained by multiplying the best similarity measure up to now and a value obtained by subtracting the number of invalid area elements to which processing has been applied up to the number of elements of the overlapping area. Item 5. The method for aligning images according to Item 5. 7. The method according to claim 6, wherein a candidate for an overlapping position of the target image with respect to the reference image is read from an external device. 8. The method according to claim 6, wherein an overlapping position of the target image with respect to the reference image is automatically set based on the reference image and the target image.