JP2001109882A - Method and device for image processing - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently analyze a scene by applying a geometric model. SOLUTION: The image processor 10 extracts feature points from two or more images respectively, compares and matches the feature points of one image with those of other images and execute matching of them, and analyzes the scene of the former image according to the result of the matching.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to an image processing method and an image processing apparatus for performing scene analysis of an image.

[0002]

2. Description of the Related Art A variety of processing algorithms have been developed in many technical fields with the advancement of computer performance in image processing, and great results have been obtained. One of such image processing techniques that has attracted attention is pattern matching.

[0003] Here, two point sets S = in a Euclidean d-dimensional space E ^d having different densities.
{S ₁ , ..., S _n } and Q = {Q ₁ , ..., Q _m }
Let us consider a problem of pattern matching in a case where the coordinates of points in a point set are slightly inaccurate, such as a feature point given by a corner detection algorithm. What needs to be done in such a case is to distinguish the matching point "inlier" from the non-matching point "outlier".

Given a transformation T, the accuracy of the matching can be calculated using the Hausdorff distance in percentage. That is, by using the Hausdorff distance, the accuracy of the matching is given as shown in the following equation (1) while eliminating the effect of the so-called nk outlier.

[0005]

(Equation 1)

In the above equation (1), min _k means to return the smallest k-th element, and d (·,
*) Is a distance function. The disadvantage of the Hausdorff index is that “A. Efrat and MJ Katz, Computing fair and
bottleneck matchings in geometric graphs, In Proc.
7th Annu. Internat. Sympos. Algorithms Comput., Pa
ges 115-125, 1996 ", a point may be matched more than once, in which case there is no meaningful result in visual geometry.

[0007] A recent technique of pattern matching includes H. Alt and L. Guibas, Resemblance of geometr.
ic objects, In Jorg-Rudiger Sack and Jorge Urruti
a, editors, Handbook of Computational Geometry, El
sevier Science Publishers BV North-Holland, Amst
erdam, 1998 ”. Also, Ira
ni and Raghavan, “Sandy Irani and Prabhakar Ragh
avan, Combinatorial and experimental results for r
andomized point matching algorithms, In Proc. 12th
Annual ACM Symposium on Computational Geometry, p
ages 68-77, 1996 ”, a random placement Monte Carlo method is used to find a transformation under the assumption that sets S and Q match at least densely, that is, at least some points match. This random arrangement Monte Carlo method is based on pairs of feature points that define the transformation, and is a global process.

[0008] The local processing that is very widely used in pattern matching considers a parameter space that defines the space of the transformation matrix T, and considers “Michiel Hagedoorn an”.
d Remco C. Veltkamp, Reliable and efficient patter
n matching using an affineinvariant metric, Techni
cal Report UU-CS-1997-33, Utrecht University, Depa
rtment of Computing Science, October 1997 ”and“ D.
Mount, N. Netanyahu, and J. Le Moigne, Improved al
gorithms for robust point pattern matching and app
lications to image registration, In 14th Annual AC
M Symposium on Computational Geometry, 1998 ”by applying a bifurcation limit method to these generation parameters.
Or, if rotation is allowed, a 3 × 3 matrix (T = R using homogeneous coordinates) generated by three parameters (x, y, θ) representing the amount of displacement and its direction.
^It is expressed as ² × [0, 2π]. ) Is defined.

Another technique for obtaining pattern matching is described in “T. Akutsu, H. Tamaki, and T. Tokuyam”.
a, Distribution of distances and triangles in a po
intset and algorithms for computing the largest co
mmon point set, Discreteand Computational Geometr
y, pages 207-331, 1998, there is a majority decision method, which is one of the generalizations of the so-called Hough transform.More recently, Indyk et al.
dyk, R. Motwani, and S. Venkatasubramanian, Geomet
ric matching under noise: Combinatorial bounds and
algorithms, In SODA: Symposium of Datastructures and
Algorithms 1999 ”and“ M. Gavrilov, P. Indyk, R. Mo
twani, and S. Venkatasubramanian, Geometric patter
n matching: A performance study, In Proc. of the 15
th Symp. of Comp. Geo., 1999 ”, proposes an algorithm that performs pattern matching by considering the diameter of a point set in the presence of noise. Furthermore, Cardoze and Schulman propose “Cardoze and Schul
man, Pattern matching for spatial point sets, In F
OCS: IEEE Symposium on Foundations of Computer Scie
nce (FOCS), 1988 ”, proposes a fast algorithm that relates pattern matching to number theory and performs a Fourier transform according to the diameter of a point set.

[0010]

In the field of image processing described above, for example, there is a method for efficiently performing scene analysis, such as creating a directional graph for a certain image. Requested.

However, it is often difficult to apply a geometric model to scene analysis, and the amount of calculation is enormous, and a lot of time is required for processing. Therefore, recently, there is an increasing demand for establishing a technique for efficiently performing scene analysis by applying a geometric model.

The present invention has been made in view of such circumstances, and provides an image processing method and an image processing apparatus capable of efficiently performing scene analysis by applying a geometric model. With the goal.

[0013]

According to the present invention, there is provided an image processing method comprising: a feature extracting step of extracting feature points for each of two or more images; It is characterized by comprising a matching step of comparing feature points of one image and another image to perform matching, and a scene analysis step of performing scene analysis of one image based on a result of the matching step.

According to the image processing method of the present invention, feature points of each of two or more images are extracted, and feature points of one image and another image among the two or more images are compared. And performs a scene analysis of one image based on the result of the matching.

According to another aspect of the present invention, there is provided an image processing apparatus for extracting a feature point of each of two or more images, and one of the two or more images. And a scene analysis unit that performs a scene analysis of one image based on the result of the matching by the matching unit.

In the image processing apparatus according to the present invention, the feature extracting unit extracts the feature points of each of the two or more images, and the matching unit extracts the feature points.
Among the above images, matching is performed by comparing feature points between one image and another image, and scene analysis of one image is performed by the scene analysis means based on the result of the matching.

[0017]

Embodiments of the present invention will be described below in detail with reference to the drawings.

An image processing apparatus 10 shown in FIG. 1 according to an embodiment of the present invention converts an image such as a still image and / or a moving image or a graphics image including sample data and an image from a data input unit 20. It has a function of performing a scene analysis of an image including sample data based on an image input from the data input unit 20.

As shown in FIG. 1, the image processing apparatus 10 includes a feature extraction unit 11 for extracting feature points from image data I ₁ including sample data SD, and a feature extraction unit 11 for extracting feature points from image data I ₂ input from a data input unit 20. A process for performing various processes such as performing pattern matching based on a feature extraction unit 12 for extracting feature points and two point sets indicating feature points extracted by the feature extraction unit 11 and the feature extraction unit 12 The processing unit 13 includes an evaluation unit 14 that evaluates a result of the pattern matching performed by the processing execution unit 13. The image processing apparatus 10 further includes a buffer for temporarily storing the input image data I ₁ and the input image data I ₂ ,
A memory (not shown) for storing various programs and data,
A memory or the like (not shown) is provided as a work area in various processes.

The image processing apparatus 10 includes an image data I ₁ such as a still image and / or a moving image or a graphics image picked up by a camera or the like, and a data input unit 20 holding a plurality of image data as a database, for example.
Inputting image data I ₂ held in the. The image data I ₁ and the image data I ₂ are, respectively, specifically, for example, as shown in FIG. 2, an image obtained by capturing a certain scenery, and as shown in FIG. This is a two-dimensional image on the order of about one million pixels, which is imaged in different camera directions, as is the case with the image captured and held in the data input unit 20. Sample data SD is any object in the image data I _1. The image processing apparatus 10, based on the image data I ₂ from the data input unit 20, performs a scene analysis of the image data I ₁ containing the sample data SD, for example, the image data I _1, the image data I ₁ and Scene Analysis A directional graph of the obtained image data I ₁ is output to the display unit 30. It goes without saying that the image data I ₁ and the image data I ₂ are not limited to the examples shown in FIGS. 2 and 3, respectively.

The feature extraction units 11 and 12 receive the image data I ₁ and the image data I ₂ , respectively, and input the image data I ₁
And extracting feature points from each of the image data I _2.
That is, the feature extraction unit 11 and 12, respectively, at least a portion of the image data I ₁ and the image data I _2, for example, according to instructions by the user, or, together to automatically duplicate the image data I ₁ and the image for each data I _2, feature points are extracted.

Here, the overlapping portion formed by overlapping at least a part of the image data I ₁ and the image data I ₂ is:
As shown in FIG. 4A, a point m ₁ on a two-dimensional image is obtained by imaging a point M in a three-dimensional space with a camera or the like.
The image data I ₁ and the image data I ₂ obtained by projecting the image data and the point m ₂ are overlapped as shown in FIG. For example, when the coordinates of point M in the three-dimensional space is expressed as (x, y, z), the point m ₁ and point m ₂ is
(X ₁ / w ₁ , y ₁ / w ₁ ), (x ₂ / w ₂ , y ₂
/ W ₂ ).

The feature extraction units 11 and 12 respectively control the edge of the picture included in the image data I ₁ and the image data I ₂ ,
By detecting corners, connections, etc., as many feature points as possible are extracted. At this time, the feature extraction units 11 and 12
Can preferentially extract the feature points of the image data I ₁ and the image data I ₂ located in the overlapping portion and the vicinity thereof, respectively. The feature extraction unit 11 and 12, respectively, the image data I ₁ or the image data I ₂ performs digital zoom may extract feature points. The feature extraction units 11 and 12 each supply a point set including the extracted feature points to the subsequent processing execution unit 13.

The feature extraction units 11 and 12 respectively determine the image data I ₁ and the image data I ₂ according to the overlap ratio indicating the ratio of the overlap between the image data I ₁ and the image data I _2.
And a selection signal for selecting a matching method used when adjusting the positional relationship with. That is, as shown in FIG. 5, each of the feature extraction units 11 and 12 selects a method of performing a matching process using a feature amount which is a parameter proportional to the number of feature points, as the overlap rate approaches 100%. A selection signal is generated to indicate that the matching process is to be performed using the pixel value as the overlap rate is smaller. Each of the feature extraction units 11 and 12 supplies the generated selection signal to the subsequent processing execution unit 13.

The processing executing unit 13 includes the feature extracting units 11 and 12
Performs geometric processing based on the two sets of points supplied from each of, and the selection signal. In particular, the process execution unit 13, based on the image data I ₂ from the data input unit 20, in order to perform a scene analysis of the image data I ₁ containing the sample data SD, supplied from each of the feature extraction unit 11, 12 The pattern matching of the two point sets is performed. This pattern matching processing will be described later in detail.

The processing execution unit 13 receives the selection signal
If you decide to perform matching using feature points,
Focusing on the intensity values of a plurality of pixels or the like constituting the image data I ₁ and the image data I _2, and the feature point p ₁ contained for example in the feature points S ₁ for the image data I _1, the image data I ₂
When the following expression (2) is satisfied, matching between the image data I ₁ and the image data I ₂ is performed as a condition for matching the feature point p ₂ included in the feature point group S ₂ for Recognize.

[0027]

(Equation 2)

Here, in the above equation (2), ε is ε ≧
It has a value satisfying 0, and d ₂ is a Euclidean distance. H is a matrix used when synthesizing the image data I ₁ and the image data I ₂ .

As described above, the processing execution unit 13 performs the above-described matching processing, such as the Hausdorff matching processing and the so-called Bottleneck matching processing, as described above. by using the feature points for the feature point and the image data I ₂ for the data I _1, it is possible to detect a common point.

[0030] Hausdorff matching is a process of connecting the feature point p ₁ for the image data I ₁ located in close proximity to the feature point p ₂ included in the feature point group S ₂ of the image data I ₂ . In the Hausdorff matching processing, by performing such processing, it generates a Hausdorff distance is an evaluation value indicating a degree of coincidence between the image data I ₁ and the image data I _2.

On the other hand, the bottleneck matching process is a matching process suitable for examining the similarity between the image data I ₁ and the image data I ₂ . In this bottleneck matching process, like the Hausdorff matching process generates the overlapping portion between the image data I ₁ and the image data I _2, the evaluation value indicating the similarity between the image data I ₁ and the image data I ₂ I do.

In addition to the above-described matching processing, the processing executing unit 13 can further improve the accuracy of matching by using a Monte Carlo method in which the characteristics of the feature points are used. FIG. 6 shows an example of an algorithm of the Monte Carlo method. That is, the processing execution unit 13
When performing the matching process, let k be the number of feature points required to calculate a basic transformation that can perfectly match with 2k feature points, and randomly select the number of k with k-number of feature points of the group S _2, it performs a matching process using the Monte Carlo method.

[0033] The processing execution section 13, the process of searching for the transferred amount and the rotational movement amount of the image data I ₁ and the image data I ₂ are matched to the characteristics of the image data I ₁ included in the image data I ₂ Do. That is, as shown in FIG. 7, the processing execution unit 13 selects feature points (L ₁ , L ₂ ) included in the image data I ₁ . In this case, the processing execution section 13, to avoid the area that includes a feature point (R _1, R ₂₎ contained in the image data I ₂ used in the geometrical filtering after, included in the image data I ₁ Feature points (L ₁ , L
₂ ) Select Here, the feature points (R ₁ , R ₂ ) included in the image data I ₂ are circular regions (d ₂ (L ₁ , L ₂ ) −2 μ,
d ₂ (L ₁ , L ₂ ) +4 μ). Then, the processing execution unit 13 considers the positional error of the feature points extracted by the feature extraction units 11 and 12,
Set a circular area with a large radius by μ.

Further, the processing execution unit 13 uses the geometric filtering algorithm shown in FIG. 8, the feature point p ^*
Is a feature point in contact with the feature point p. By applying this geometric filtering algorithm, the relationship between the feature point p and the feature point p ^* is expressed by the following equation (3).

[0035]

(Equation 3)

Then, the processing execution unit 13 adaptively uses a geometric filtering algorithm for the detected feature points. In the geometric filtering algorithm shown in FIG. 8, a feature point group S ₁ (L) of image data I ₁ composed of k feature points selected at random.
_1, L _2, ···, using L _k), the feature point p ₂ for the sequential image data I _2, feature points _{S 2 (R 1, R 2} , ··
, R _k ) and searches for a feature point that matches the feature point included in the feature point group S ₁ . Where R ₂ is
Circular area _{(R 1, L 1 L 2} -2μ, 4μ) are feature points included in, R ₃ is a feature points included in the circular area _{(R 2, L 2 L 3} -2μ, 4μ), R _k is a circular region (R _k−1 , L _k−1)
L _k -2μ, 4μ).

Further, the processing execution unit 13 performs matching between the image data I ₁ and the image data I ₂ by randomly combining the algorithm shown in FIG. 9 and the geometrical filtering algorithm shown in FIG. Take. Then, the processing execution unit 13 supplies the result of the matching to the evaluation unit 14.

The evaluation unit 14 receives the result of the above-mentioned matching processing from the processing execution unit 13 and evaluates the result of the pattern matching performed by the processing execution unit 13 to generate an evaluation value. The evaluation unit 14 performs the Hausdorff matching processing and the bottleneck matching processing described above as evaluation functions, and when matching is performed using pixel values, the image data I ₁ and the image data I _{2 are used.}
Detecting a pixel value of a, and generates an evaluation value by using the correlation of pixel values between these image data I ₁ and the image data I _2. The evaluation unit 14 outputs, for example, the image data I ₁ and its directed graph to the display unit 30 when the evaluation is the best. The display unit 30 may be based on a signal from the evaluation unit 14 on the display screen (not shown) the image data I ₁ and the directed graph.

The image processing apparatus 10 performs a scene analysis of the image data I ₁ based on the image data I ₂ by performing a series of processes as shown in FIG. 10, for example. Note Here, a sample data SD is any object in the image data I _1, which is selected based on the specification of the user, a series of processes will be described for performing pattern matching between the image data I _2.

Firstly, the image processing apparatus 10, as shown in the figure, in step S1, and inputs the sampled data SD in the image data I _1. Here, the image data I
₁ may be, for example, an image captured by a camera or the like, or may be, for example, selected by a user as a target of scene analysis. In addition, the image processing apparatus 10 generates a pyramid including enlarged and / or reduced image data of the input sample data SD by, for example, changing a zoom ratio.

Subsequently, the image processing apparatus 10 proceeds to step S
In step 2, the pyramid of the sample data SD generated in step S1 is supplied to the feature extraction unit 11, and the feature extraction unit 11 extracts feature points for each piece of image data forming the pyramid as described above. In the following, image data at an appropriate scale for the sample data SD is referred to as sample data SD. When extracting a feature point, the feature extraction unit 11 extracts a feature point in a predetermined three-dimensional direction of the sample data SD.

Subsequently, the image processing apparatus 10 proceeds to step S
In 3 inputs image data I ₂ from the data input unit 20. Note that the image data I ₂ does not necessarily need to be supplied from the data input unit 20, and may be, for example, data selected as a target of scene analysis by designation by a user. Further, the image processing apparatus 10
The input image data I ₂ is generated, for example, by changing the zoom ratio to generate a pyramid including enlarged and / or reduced image data.

Subsequently, the image processing apparatus 10 proceeds to step S
4, the image data I generated in step S3
_{The second} pyramid is supplied to the feature extraction unit 12. The image processing apparatus 10 uses the feature extraction units 11 and 12 to output each image data forming a pyramid of the sample data SD,
And the image data constituting the pyramid of the image data I _2, for example, according to instructions by the user, or, together to automatically duplicate, for each image data, feature points are extracted as described above. The image processing device 10
By doing so, when searching the sampled data SD which scale factor may be included in different image data I ₂ can also be varied with each other to scale, it compares the image data with each other suitable scaling factor . In the following, it is assumed to refer to image data in the appropriate scale factor for the image data I ₂ and the image data I _2. Feature extraction unit 12
, When extracting the feature points, the predetermined third image data I ₂
Extract feature points in the dimensional direction. In addition, the image processing apparatus 10 uses the feature extraction units 11 and 12 to
Referring to overlap ratio between the image data I ₁ and the image data I _2, and generates a selection signal for selecting the method of the matching process.

Subsequently, the image processing apparatus 10 proceeds to step S
At 5, initialization is performed by the processing execution unit 13.

Subsequently, the image processing apparatus 10 proceeds to step S
In step 6, the processing execution unit 13 sets the sample data SD
Selecting any of a set of feature points F ₁ from among the feature points for.

Subsequently, the image processing apparatus 10 proceeds to step S
In 7, selects any one set of the feature point F ₂ from among the feature points of the image data I ₂ by the processing execution unit 13.

Subsequently, the image processing apparatus 10 proceeds to step S
In 8, using the feature point F ₁ and the feature point F ₂ by the processing execution unit 13, performs a matching process, determines whether or not the feature point F ₁ and the feature point F ₂ coincides.

Here, if the feature points F ₁ and F ₂ do not match, the image processing apparatus 10 proceeds to step S7.
To and the process proceeds to select the other feature point F _2, performs a matching process again.

On the other hand, when the feature points F ₁ and F ₂ match, the image processing apparatus 10 generates an evaluation value by the evaluation unit 14 in step S 9.

Subsequently, the image processing apparatus 10 proceeds to step S
At 10, the processing execution unit 13 determines whether O (1) used in the so-called Hungarian theory is larger than the number of samples in the above-described processing.

Here, if O (1) is not larger than the number of samples, the image processing apparatus 10 shifts the processing to step S6, and repeats the processing from step S6 again.

On the other hand, when O (1) is larger than the number of samples, in the image processing apparatus 10, in step S11, the evaluation unit 14 previously performed the matching processing on the evaluation value generated in step S9 by the evaluation unit 14. It is determined whether the evaluation value is better than the evaluation value at that time.

[0053] Here, when the evaluation value is not satisfactory, the image processing apparatus 10, the process proceeds to step S3, and inputs the other image data I ₂ from the data input unit 20, the step S3 and subsequent steps Is repeated again.

On the other hand, when the evaluation value is good, the image processing apparatus 10, the image data I ₂ sample data SD
It is assumed that the object is the same as the above, and the result is stored in a memory or the like (not shown), and a series of processing ends.

Note that the image processing apparatus 10 performs a matching process between the sample data SD and all the image data I ₂ held in the data input unit 20 to obtain only the image data I ₂ having the best evaluation value. It can also be stored in a memory or the like (not shown).

As described above, the image processing apparatus 10 determines what the sample data SD is based on the image data I ₂ from the data input unit 20. Then, the image processing apparatus 10 performs such processing for all objects in the image data I _1, performed scene analysis of the image data I _1, is the result of the image data I ₁ and scene analysis digraph Can be output to the display unit 30.

The image processing apparatus 10 efficiently matches the feature points of the image data I ₁ and the image data I ₂ by using the above-described geometrical method in the matching process. scene analysis data I ₁ can be performed.

Hereinafter, various processes in the image processing apparatus 10 will be described in detail. In the following, the feature points in each of the above-described image data I ₁ and image data I ₂ will be referred to as a point set S and Q, respectively, and a joint detection processing, a symmetry detection processing, a pattern matching,
The process of detecting the maximum common point set and the like will be described, and these applications will also be mentioned.

[0059] The image processing apparatus 10 described above, a set of two points in Euclidean d-dimensional space E ^d S = {S _1,
, S _n }, Q = {Q ₁ ,..., Q _m }, {T (S), Q} matching when transform T in transform space T is applied to point set S Can be found to be the maximum T. Further, the image processing apparatus 10 can implement a deterministic algorithm and a random algorithm for conditionally performing pattern matching by applying a geometric constraint to the transform T.

The image processing apparatus 10 can obtain point set pattern matching almost accurately even when each point fluctuates by a certain small amount ε. This allowable swing amount ε
Varies according to d _min / 2√d expressed by the minimum distance d _min between points and the distance d between points of the point set. The image processing apparatus 10 allows an error of the maximum value of the allowable swinging amount ε instead of employing a continuous index for scoring the matching {S, Q} such as a so-called Hausdorff index or a symmetry difference index. By counting the number of one-to-one matching points as shown in FIG.

In the following description, 1ε (P, Q)
Is 1ε (P, Q) = 1 if and only if d ₂ (P, Q) ≦ 2ε, otherwise 1ε
It is assumed that the function is a {0, 1} function such that (P, Q) = 0. Further, in the following description, the score score ({S, Q}) representing the accuracy of matching is represented by a point set Q
Permutation m! Is defined as the following equation (4) using σ, which is a value that changes over the entirety of.

[0062]

(Equation 4)

Here, the definition shown in the above equation (4) holds for all ε ≧ 0.

The image processing apparatus 10 first distinguishes a matching point “inlier” from a non-matching point “outlier”, and then assigns the same label to the matching point. By performing such preliminary processing, the image processing apparatus 10 can handle the continuous distance index in R, and can improve the matching of each local minimum.

For example, the image processing apparatus 10 is based on the recently proposed “D. Mount, N. Netanyahu, and J. Le Moigne, Im.
proved algorithms for robust point pattern matchin
g and applications to image registration, In COMPG
EOM: Annual ACM Symposium on Computational Geometr
y, 1998 ”and“ M. Hagedoorn and R. Veltkamp, A gener
al method for partial point set matching, In Proce
edings of the 13th International Annual Symposium
on Computational Geometry (SCG-97), pages 406-408,
New York, June 4-6 1997, ACM Press "".
That is, the image processing apparatus 10 can find almost all of the matching transforms at the upper level, and make the matching transform more accurate for each local minimum at the lower level. Can be improved.

Schematically, the image processing apparatus 10
The geometric pattern matching is performed by the method shown in FIG. That is, the image processing apparatus 10 distinguishes and detects inliers and outliers in both the point sets S and Q as global processing based on the two input point sets S and Q and the allowable swing amount ε. , And assign the same label to the matching points. As described above, this processing is not performed by using a continuous index for scoring the matching {S, Q}, but is performed by a discontinuous index. Then, the image processing apparatus 10 performs, as a local process, the labeled point set S _l ,
Forming a Q _l, to improve the pattern matching adopts a continuous indication as described above, converted in transformation space T T
Output the set of

Since it is frequently necessary to select a candidate from extracted inaccurate feature points in visual geometry, the image processing apparatus 10 reports all transformations having a certain feature, and Count the number of different conversions.

Hereinafter, the processing in the image processing apparatus 10 will be described in detail.

First, a congruence problem in a two-dimensional, three-dimensional and d-dimensional space will be defined, and how the congruence operator is related to the symmetry of numbers will be described. Also, the relationship between the joint problem and graph theory, symmetry, and number theory will be described. In the following description, the exact matching is represented by a prefix E, and the matching including noise is represented by a prefix N. Also, in the following description, the illustration, question, report and count, respectively,
It is represented by W, Q, R, and C. So, for example,
The “EW joint problem” is a conversion T such that T (S) = Q
∈T, that is, a problem that is required to report that the point sets S and Q are congruent (denoted by S≡Q). Also, TI, TR, T
T, TH, TS, and TA are isometry, rotation, and tran, respectively.
slational), homothetic, similitud
e, which is obtained by performing isometric transformation and scaling), and represents an affine transformation group space.

The "joint problem" generally asks whether two point sets S and Q are joint. In the following description, when it is desired to emphasize and represent the environment space, a subscript is used. For example, S≡ _TH
Q indicates that the point set S is congruent with the point set Q in the similarity space. If the subscript is not explicitly indicated, “≡” is “≡ _TH ”.

Here, the following joint problem is considered.
"Two d-dimensional Euclidean n-point sets S = ｛S ₁ ,.
.., S _i = (S _{i, 1} ,... S _{i, d} ),..., S _n } and Q = {Q ₁ ,..., Q _i = (Q _{i, 1} ,.・
Q _{i, d} ),..., Q _n }, the point set S
Is congruent with the point set Q? That is, S≡
Q? "

This problem is described in the two-dimensional space E ² and the three-dimensional space E ³ as “MD Atkinson, An optimal
algorithm for geometrical congruence, J. Algorithm
s, 8: 159-172, 1987 ”and“ H. Alt, K. Mehlhorn, H. Wa
gener, and Emo Welzl, Congruence, similarity and s
ymmetries of geometric objects, Discrete Comput.Ge
om., 3: 237-256, 1988 ”, a solution can be obtained in O (n log n) time by a so-called real RAM model, but for any other dimensions, As with so-called graph isomorphism, it is difficult to find a solution.How to characterize why the difficulty of this graph isomorphism arises is described in “J. K.
obler, U. Schoning, and J. Toran, The Graph Isomor
phism Problem: Its Structual Complexity, Birkhause
r, Boston, 1993 ”, as yet.

Alt et al. Refer to the above-mentioned “H. Alt, K. Mehlhor
n, H. Wagener, and Emo Welzl, Congruence, similari
ty and symmetries of geometric objects, Discrete C
omput. Geom., 3: 237-256, 1988 ", discusses a deterministic algorithm for O ( ^nd-2 logn) time for d-dimensional point sets.
Is “Tatsuya Akutsu, On determining the congruenc
e of point sets in d dimensions, Comput. Geom. The
ory Appl., 9 (4): 247-256, 1998 ”by“ Meijer, Cry
ptology and the birthday paradox, UMAP: The Journal
of Undergraduate Mathematics and its Application
s, 17, 1996 ”, a random O ＾ ( ^nd −1/2 log ² n) time O based on the birthday paradox.
A ＾ ( ^{nd-1 / 2} ) space algorithm is proposed. Note that O ＾ (•) represents the processing capability of the randomized algorithm.

Here, it is assumed that E ^d → E ^d indicates an isometric mapping. That is, d (P, Q) = d (T (P), T
(Q)) ∀P, is Q∈E ^d. The isometric mapping is also referred to as a rigid body motion, and may or may not have reflection. Any isometric transformation T∈TI is
It can be decomposed into a d × d orthogonal matrix R _d ∈TR and a transition part t _d ∈TT. That is, T (x): = R _d
x + t _d . Note that a d × d orthogonal matrix R _d
Determines the chirality of the isometric conversion. That is, when det (R _d ) = 1, the isometric transformation is called regular, and when det (R _d ) = − 1,
The isometric transformation is said to be anomalous. Note that the synthesis of the two isometric transformations is also an isometric transformation. For example, gliding mirroring is a combination of mirroring and transition, and is used, for example, to generate regularly repeating patterns. FIG. 12 shows some examples of isometric conversion.

In the following description, only regular isometric transformation will be discussed. This is because, in the case of the irregular isometric transformation, first, a reflection transformation such as x ₁ → −x ₁ may be performed on one of the sets, for example, S. The standard form of the point set S is an object (also referred to as a category) O (S) where O (S) = O (Q) for all Q≡S.

Therefore, what needs to be done to detect congruence is to first calculate both the standard types O (S) and O (Q) of the point sets S and Q, then , These standard types O (S) and O (Q)
Is to check if are equal. Here, for a regular polyhedron, “E.Sc
hulte, Symmetry of polytopes and polyhedra, In Jac
ob E. Goodman and Joseph O'Rourke, editors, Handbo
ok of Discrete and Computational Geometry, chapter
16, pages 311-330, CRC Press LLC, Boca Raton, FL,
1997 "can be used. The Schlafli symbol {p ₁ ,..., P _d-1 } encodes the local structure of a regular polyhedron as That is, in an arbitrary (i + 1) plane F, p _i represents the number of i planes including the (i−1) plane given F. For example, a two-dimensional regular p-polygon is represented by the symbol {p} The symmetric group is a 2p-order dihedral group. Here, when p ≧ 3, it is necessary to handle transcendental numbers, but the cyclic group C _p and its reflection C _p ′ Furthermore, any d-dimensional polyhedron is described in "JE Goodman and J. O'Rourk
e, editors, Handbookof Discrete and Computational
Geometry, CRC Press LLC, Boca Raton, FL, 1997 ”, a generalized Sch
It can be uniquely expressed by a combination of lafli symbols. Therefore, given two point sets S and Q, first, the corresponding generalized Schl of the convex hull
Calculate and find afli symbols and see if they match. At this time, if the combination standard form is different between the two point sets S and Q, the result is negative. On the other hand, if the combination standard form matches the two point sets S and Q, the entire test is performed.

Next, detection of congruence on a plane will be described. A simple method for detecting congruence on a plane is described in “MD Atkinson, An optimal algorithm” above.
forgeometrical congruence, J. Algorithms, 8: 159-1
72, 1987 ", the following equations (5) and (6) are respectively calculated to obtain the respective centroids c _S , c _Q of the point sets S, Q. Perform a transition so that Lloyd c _S is mapped to Centroid c _Q.

[0078]

(Equation 5)

[0079]

(Equation 6)

This means that for any affine transformation T,
That is, c _{T (S)} = T (c _S ) holds for the rigid body motion. Here, if S≡Q, there exists a transformation T∈T such that Q = T (S), and for any T∈TA, c _Q =
Since c _{T (S)} = T (c _S ), the point sets S, Q
Each centroid c _S, c _Q of entirely consistent with each other.

Here, the coordinates of each point are represented using polar coordinates (θ, r) centered on each centroid. At this time, if there is a complete circulation pattern that matches the polar coordinates arranged in lexicographic order, for example, “DE Knuth, JH Morris, and VR Pratt, Fast
pattern matching in strings, SIAM Journal on Compu
Morting-Knuth-, ting, 6: 323-350, 1977 ”
Only then is the point set S congruent to the point set Q, as determined on the linear time axis using the Pratt algorithm. Here the cyclic pattern matching is
This can be regarded as partial character string pattern matching of a character string of length 2n in a character string of length 2n.

It should be noted that there may be a plurality of isometric transforms up to 2n = O (n), but they may or may not be S 或 い は Q. All of these are enumerated and their numbers counted for further illustration. FIG. 13 shows some examples of paired rotational symmetry. S
It is not so difficult to detect whether ≡Q or not, but it is difficult to enumerate all transformations T such that T (S) = Q. Here, the transformation group of the point set S is represented by T (S) = ｛T | T (S) =
Let it be represented as S｝. Note that “HSM Coxeter,
Introduction to Geometry, John Wiley & Sons, New Y
ork, 2nd edition, 1969 ”,“ HSM Coxeter, Regu
lar Polytopes, Dover, New York, NY, 2nd edition, 1
973 ”and“ HSM Coxeter, Regular Complex Polyto
pes, Cambridge University Press, Cambridge, Englan
d, 2nd edition, 1991 ", the symmetry group or the reflection group is also represented as T (S) = {T | T (S) = S}.

Atallah is described in “MJ Atallah, On symmetr
y detection, IEEE Trans.Comput., C-34: 663-666, 19
85 ”, an algorithm for detecting symmetry on a plane is presented.“ S. Iwanowski, Testing approximat
e symmetry in the plane isNP-hard, Theoret.Compu
t. Sci., 80: 227-262, 1991 ”,
It is known that if the point is allowed to swing, the problem becomes so-called NP difficulties. This is because, for each point, it is necessary to obtain a swing that makes the point set congruent. The improvement regarding the stability of the algorithm will be described later.

Here, the problem that makes the algorithm for detecting the similarity of point sets difficult will be described. Here, consider the following matching problem of all subset character strings. "A character string s [1.
n] and the pattern p [1. . m] and the pattern p [1. . m] is a character string s [1. . Find a Boolean array where o [i] = 1 if and only if it appears cyclically in n]. "

The problem of matching all subset character strings is described in “Richard Cole and Ramesh Hariharan, T
ree pattern matching and subset matching in random
izedO (n log ³ m) time, In Proceedings of the Twenty-
Ninth Annual ACM Symposium on Theory of Computing,
pages 66-75, El Paso, Texas, 4-6 May 1997 ”and“ Ri
chard Cole, Ramesh Hariharan, and Piotr Indyk, Tre
e pattern matching and subset matching in randomize
d O (n log ³ m) time, In Proceedings of SODA 1999, Ja
n. As shown in 1999 ”, O (n log ³ m)
It is possible to solve in time.

The sorted one-dimensional point sets S and Q can be solved within O (nm) time using a simple algorithm. Akutsu stated in the “Tatsuy
a Akutsu, On determining the congruence of point s
ets in d dimensions, Comput. Geom. Theory Appl., 9
(4): 247-256, 1998 ”, to detect whether or not the point set S is included in the point set Q, use O 、 ((m / n +
n ² ) polylog n) states that time is required. Also, recently, Cardoze and Schulman described “C
ardoze and Schulman, Pattern matching for spatial
point sets, In FOCS: IEEE Symposium on Foundations
of Computer Science (FOCS), 1988 ”
(log N + polylog Δ) algorithm. Here, N = max {n, m} and Δ
Is the diameter of the point set Q. Infinite d encoding the lattice
In crystallography treated as a dimensional point set, a crystal is classified by a transformation T, and the transformation is labeled by a transformation group. For example, two-dimensional space E ² In 17, the three-dimensional space E 320 pieces in ^3, it is known that four-dimensional space E 4783 amino crystallographic groups in ⁴ are present.

As a noise model, a sphere whose center is p and whose radius is ε is represented by the following equation (7).

[0088]

(Equation 7)

The point set including the swing is represented by the following equation (8).

[0090]

(Equation 8)

It is assumed that each point S∈S has been moved into a sphere having a radius of ε. FIG. 14 shows a point set S and a point set Sε including noise. Here, when the minimum distance d _min > ε of the point set is satisfied, the spheres centered on each point in the point set S are disjoint as shown in FIG. This is explained below,
Make the pattern matching algorithm robust.

Further, the principle of detection of congruence in a two-dimensional space can be extended to detection of congruence in a three-dimensional space. That is, both centroids of the point sets S and Q are calculated, and all points are projected on a unit sphere centered on those centroids for each set.
Next, the convex hull of the projected point is calculated. Further, an original distance from the centroid is added as a label to each projected point, and a clockwise adjacency list of corner vertices formed by mutually adjacent points of the convex hull is created.
And “JE Hopcroft and RE Tarjan, A VlogV
algorithm forisomorphism of triconnected planar g
raphs, Journal of Computer and System Sciences, 7
(3), June 1973, using a variant of the Tarjan planar graph congruence algorithm to determine whether these two annotated planar graphs are isomorphic or not (O (n log
n) Evaluate in time. Here, if scaling can be performed, the minimum distance between points is first set to “1” for all fixed dimensions, and “FP Preparat
a and MI Shamos, Computational Geometry: AnIntro
duction, Springer-Verlag, New York, NY, 1985 ”, both the point sets S and Q are O (n
Normalize within log n) time. Note that the dimension is "3"
In these cases, see “Sergei N. Bespamyatnikh, An effi
cient algorithm for the three-dimensional diameter
problem, In Proc. 9th ACM-SIAM Sympos. Discrete A
lgorithms, pages 137-146, as described in 1998 ", the diameter of the n-point set of d-dimensional space E ^d O _d (n l
og n) Since the deterministic algorithm for calculating in time is not known, the minimum distance between points is adopted.

Also, when the affine transformation (≡ _TA ) is used instead of the rigid body Euclidean motion (≡ _TI ), Sprinzak and Werman show that “J. Sprinza
k and M. Werman, Affine point matching, Pattern Re
cogn. Lett., 15: 337-339, 1994 ”.
This is particularly useful for recognizing a three-dimensional object by orthographic projection (affine transformation) from a two-dimensional image. If it is necessary to enumerate all possible O (n) transforms, it is necessary to use another valid algorithm. Wolter et al., “Jan D. Wolter, Tony C. Woo, and
Richard A. Volz, Optimal algorithms for symmetry de
tection in two and three dimensions, Thw Visual Com
puter, 1 (1): 37-48, July 1985 ”and“ Xiaoyi Jiang, Ke
ren Yu, and Horst Bunke, Detection of rotational an
d involutional symmetries and congruity of polyhedr
a, The Visual Computer, 12 (4): 193-201, 1996, ISSN0
178-2789 ", proposes an optimal quadratic time and linear space algorithm as a method for detecting the symmetry of two-dimensional and three-dimensional polyhedrons. This method is described in" K. Sugihara, Annlogn ".
algorithm for determining the congruity of polyhe
dra, J. Comput. Syst. Sci., 29: 36-47, 1984 ”, can be used to detect both symmetry and congruency as well as the optimal congruent 3D polyhedron detector. it can.

In addition, detecting congruence in higher dimensions is more difficult. Alt et al., “H. Alt and L. Guibas, R.
esemblance of geometric objects, In Jorg-Rudiger S
ack and Jorge Urrutia, editors, Handbook of Comput
ational Geometry, Elsevier Science Publishers BV
By reducing the space, as shown in North-Holland, Amsterdam, 1998, “H. Alt, K. Mehlh
orn, H. Wagener, and Emo Welzl, Congruence, simila
rity and symmetries of geometric objects, Discrete
. Comput Geom, 3:. 237-256 , O d (n shown in 1988 "
^d-2 log n) time algorithm. Actually, detection of congruence in the d-dimensional space can be realized by performing congruence detection in the (d-1) -dimensional space n times. Recently, Akutsu, as mentioned above,
uya Akutsu, On determining the congruence of point
sets in d dimensions, Comput. Geom. Theory Appl.,
9 (4): 247-256, 1998 ", a random time and space algorithm is proposed.
As a primitive method for solving whether or not Q is, any (d-1) simplex σ _S = ｛S ₁ ,.
.., S _d } and compute all x transformations to the set Q. Note that x is represented by the following equation (9).

[0095]

(Equation 9)

If each transformation corresponds to a rigid body motion, the physical identity is evaluated in O _d (n logn) time. Non-degenerate d set S = (S ₁ ,..., S _d ) and set Q
Given a subset of d points, the possible transformations to check are the different permutations of the points of the simplex σ _S , d! And these are not necessarily rigid body motions. That is, the matrix and R _d are not necessarily orthogonal. Here, all i∈ ｛1 in the affine transformation
..., to represent the transformation to give the mapping S _i → Q _i for d} the following equation (10).

[0097]

(Equation 10)

Such a conversion is calculated as shown in the following equation (11).

[0099]

[Equation 11]

Here, if R _d is described as in the following equation (12), the following equation (13) is obtained.

[0101]

(Equation 12)

[0102]

(Equation 13)

Q _{i, j} in the above equation (13) is _j of the point Q _i
The th component.

At this time, since the centroids of the sets S and Q match, it is sufficient to consider the (d-1) sets, that is, (d-2) simplexes.
Therefore, the computation time of the primitive method using linear space is O _d (n ^d log n). In the case of affine transformation, congruence is similarly detected. Here, the time complexity of a d-dimensional congruential operator to a point set using O (n ^{floor [d / 2]} ) space is O (n ^{floor [(d + 1) / 2]} log
We propose a simple deterministic algorithm such that n). Here, floor [A] is the smallest integer not less than A. This method is based on the principle that the relationship between the sets S and Q and their convex hull conv (S) and conv (Q) is expressed by the following equation (14).

[0105]

[Equation 14]

This is because the following equation (15) holds for the affine transformation T∈TA.

[0107]

(Equation 15)

Here, it is assumed that the following expressions (16) and (17) are used.

[0109]

(Equation 16)

[0110]

[Equation 17]

The image processing apparatus 10 performs a series of steps shown in FIG. 15 and FIG.
Are congruent or not.

First, as shown in FIG. 15, in step S21, the image processing apparatus 10 inputs d-dimensional n-point sets S and Q, and arranges each point of these point sets S and Q in lexicographic order. I do.

Subsequently, the image processing apparatus 10 proceeds to step S
At 22, it is determined whether or not all closest pairs of the point sets S and Q have a matching distance at O _d (n log n) time. That is, the image processing device 10
For each point S∈S, the following equations (18) and (19)
, And for each point Q∈Q, the following equation (2)
0) and the following equation (21) are calculated. For the closest pair, see “PM Vaidya, An O (nlogn) algorithm fo
r the all-nearest-neighbors problem, Discrete Comp
ut. Geom., 4: 101-115, 1989 ".

[0114]

(Equation 18)

[0115]

[Equation 19]

[0116]

(Equation 20)

[0117]

(Equation 21)

Here, if all the closest pairs of the point sets S and Q do not have a matching distance, the point sets S and Q
Q is not congruent, the image processing apparatus 10 shifts the processing to step S39 in FIG. 16, reports that the point sets S and Q are not congruent, and ends a series of processing.

On the other hand, if all the closest points of the point sets S and Q have the same distance, the image processing apparatus 10
Goes to step S23 in FIG. 15, and since the point sets S and Q are multiple sets, it is necessary to check all the densities of these elements. Therefore, in step S23, the following equation (22) is used. And the following equation (23), and all l
For ∈nn (S) ∪nn (Q), | NN
_{l (S) | = | NN} l (Q) | a determines whether or not the it. That is, the image processing apparatus 10 detects the multiplicity of the point, and thereafter handles a separate point set.

[0120]

(Equation 22)

[0121]

(Equation 23)

Here, all l∈nn (S) ∪nn
For (Q), | NN _l (S) | = | NN
If not _l (Q) |, the point sets S and Q are not congruent, and the image processing apparatus 10 proceeds to step S3 in FIG.
The process is shifted to 9 to report that the point sets S and Q are not congruent, and the series of processes ends.

On the other hand, all l∈nn (S) ∪nn
For (Q), | NN _l (S) | = | NN
_{If l} (Q) |, the image processing apparatus 10 shifts the processing to step S24 in FIG.
The point sets S and Q are both normalized by calculating a minimum inter-point distance greater than O _d (n log n) time. Therefore, the image processing apparatus 10 uses “JL Be
ntley and MI Shamos, Divide-and-conquer in mult
idimensional space, In Proc. 8th Annu. ACM Sympos.
Theory Comput. Pages 220-230, 1976 ”and“ FP Pre
parata and MI Shamos, Computational Geometry: An
Introduction, Springer-Verlag, New York, NY, 1985 ”
The As can be seen with reference, by using ≡ _TI instead of ≡ _TS, it is possible to obtain a uniform zoom value.
Non-uniform zoom values can be determined by calculating the minimum enclosed orthogonal box, but this calculation is difficult.

Subsequently, the image processing apparatus 10 proceeds to step S
At 25, calculate the centroids of the normalized set and overlay these centroids. That is, the image processing apparatus 10 sets c _S = c _Q and sets the conversion t _d to c _Q −c _S
Fixed to.

Subsequently, the image processing apparatus 10 proceeds to step S
At 26, the distances f _S (S _i ) and f _Q (Q _i ) of each point from each of the centroids c _S and c _Q are determined by the following equations (24) and (25), respectively.

[0126]

(Equation 24)

[0127]

(Equation 25)

Subsequently, the image processing apparatus 10 proceeds to step S
At 27, the associated radius functions F _S , F _Q , F
_S (r) and F _Q (r) are obtained by the following equations (26) to (29), respectively.

[0129]

(Equation 26)

[0130]

[Equation 27]

[0131]

[Equation 28]

[0132]

(Equation 29)

Subsequently, the image processing apparatus 10 executes step S
At 28, the spectrum is | F for all l
_{Q (l) | = | F} S (l) | a determines whether or not the it.

Here, when the spectrum is |
If F _Q (l) | ≠ | F _S (l) |, the point sets S and Q are not congruent, ie, O _d (n log
n) It is time, and the image processing apparatus 10 shifts the processing to step S39 in FIG. 16, reports that the point sets S and Q are not congruent, and ends a series of processing.

On the other hand, the spectrum is | F for all l.
_{Q (l) | = | F} S (l) | If it is, the image processing apparatus 10, as shown in FIG. 16, in step ^{_{S29, F S +, F Q}} +, F S -, F Q ^- , Respectively, by the following equation (3)
0) to the following equation (33).

[0136]

[Equation 30]

[0137]

(Equation 31)

[0138]

(Equation 32)

[0139]

[Equation 33]

Subsequently, the image processing apparatus 10 proceeds to step S
At 30, it is determined whether or not | F _S ⁻ | ≧ d−1.

Here, if | F _S ⁻ | ≧ d-1, the image processing apparatus 10 selects the minimum number of F _S ⁻ layers having at least d−1 points in step S31. Then, the conversion of the maximum O ((2d−3)!) = O _d (l) is checked. The image processing apparatus 10, F _Q ^- performs the same processing for.

On the other hand, when | F _S ⁻ | ≧ d−1 is not satisfied,
The image processing apparatus 10 shifts the processing to step S32, and obtains r ′ by the following equation (34).

[0143]

(Equation 34)

Subsequently, the image processing apparatus 10 proceeds to step S
33, Q ′ and S ′ are respectively expressed by the following equation (3)
5) and the following equation (36).

[0145]

(Equation 35)

[0146]

[Equation 36]

Subsequently, the image processing apparatus 10 proceeds to step S
34, "HP Lenhof and M. Smid, Sequentia
l and parallel algorithms for the k closest pairs
problem, Internat. J. Comput. Geom. Appl., 5: 273-2
88, 1995 ", the geometric graph of S ', Q' is calculated and whether they have the same number of repetition distances, ie, 1∈D (S ' ) ∪D
For l of (Q ′), | D _{S ′} (l) | = | D
_By enumerating whether or not _{Q ′} (l) | holds, all the distances of S ′ and Q ′ are listed in the sorted order, thereby obtaining O (n
² ) Judge within the time.

Here, if the geometric graphs of S ′ and Q ′ do not have the same number of repetition distances, the point sets S and Q are not congruent, and the image processing apparatus 10 proceeds to step S39. The processing is shifted to, and the fact that the point sets S and Q are not congruent is reported, and a series of processing ends.

On the other hand, when the geometric graphs of S ′ and Q ′ have the same number of repetition distances, the image processing apparatus 10 determines in step S35 that “R. Seidel, Con
structing higher-dimensional convex hulls at logar
ithmic cost per face, In Proc. 18th Annu.ACM Symp
os. Theory Comput., pages 404-413, 1986 ", the (d-2) plane F of the convex hull of S ', that is, the edge is defined as a linear program and the convex hull of Q'
It is calculated using nv (Q ′).

Subsequently, the image processing apparatus 10 proceeds to step S
At 36, the edge F is matched to any other edge of the convex hull conv (Q '), which is generally the (d-2) plane defining d-1 points. Each ridge line pair is maximum (d-1)! Define the rigid body motion.

Then, the image processing apparatus 10 proceeds to step S
At 37, for a given rigid body motion T∈T,
It is determined whether or not T (S) = Q.

Here, if T (S) = Q is not satisfied for the given rigid body motion T 点 T, the point sets S and Q are not congruent, and the image processing apparatus 10 proceeds to step S39. The processing is shifted to, and the fact that the point sets S and Q are not congruent is reported, and a series of processing ends.

On the other hand, if T (S) = Q for the given rigid body motion T∈T, the image processing apparatus 10 determines in step S38 that the point set S,
Q reports that they are congruent, and ends a series of processing.

The image processing apparatus 10 can handle not only rigid body motion but also affine transformation.

As described above, the image processing apparatus 10 can detect whether or not the point sets S and Q are congruent. For example, as shown in FIG. 17A, the image processing apparatus 10 also converts point sets S and Q having only a single point on a circle having the same radius as shown in FIG. A point set S having a plurality of points on a circle having the same radius,
It can be detected that Q is congruent. By detecting congruence in this way, the image processing apparatus 10 can, for example, convert an arbitrary object in the image data
Any object in image data from different sources can be identified.

Here, it should be noted that the points are at the non-degenerate position because both of the point sets S ′ and Q ′ are spheres centered on c _S = c _Q. This allows
In the image processing apparatus 10, the convex hull algorithm can be simplified. The time complexity of this algorithm is calculated using h, the number of facets of the convex hull conv (Q ′), and C (n, h), the time complexity of calculating all these facets. (Hn
log n + C (n, h)). For example,
“Bernard Chazelle, An optimal convex hull algorit
hm in any fixeddimension, Discrete Comput. Geom.,
10: 377-409, adopts an optimal algorithm Chazelle shown in 1993 ", the use of ^{O (n floor [d / 2} ]) ^{space, O (n floor [(d} + 1) / 2] log n) A time algorithm is obtained, see “R. Seidel, Constructing highe
r-dimensional convex hulls at logarithmic cost per
face, In Proc. 18th Annu. ACM Sympos. Theory Comp
ut., pages 404-413, 1986 ”, it is possible to use a linear memory space by using the shelling method of Seidel. The result is described in“ E. Schulte, Symmetry of
polytopes and polyhedra, In Jacob E. Goodman and J
oseph O'Rourke, editors, Handbook of Discrete and
Computational Geometry, chapter 16, pages 311-330,
It also shows that the maximum number of congruent transformations is related to the polyhedral symmetry, as described in CRC Press LLC, Boca Raton, FL, 1997. The time is T _c (n), the execution time required to check one transformation, and the point sets S, Q
T, which is the number of rigid body motions defined by (d-1)
And is expressed as O (n ^{floor [d / 2]} + tT _c (n)) time. The image processing apparatus 10 also checks the consistency of the volumes of the simplex defined in advance by these sets.

If the degree of swing of the point is smaller than the closest distance between any two points of the set S and the closest point between any two points of the set Q, the algorithm shown in FIGS. Is powerful. That is, instead of considering the decomposition in the radial direction, a pair of thin spherical layers that are disjoint may be considered. The change of the centroid with respect to the white noise is ε
Small compared to.

[0158]

(37)

[0159] The diameter of the formula (38) maximum value of the ratio delta _Q set point Q may be defined as the point distances for the smallest value of the point distance between the discrete points given by, for example, if the best Is limited by O (n ^{1 / d} ), the image processing apparatus 10 sets “P. Indyk, R. Motwa
ni, and S. Venkatasubramanian, Geometric matchingu
nder noise: Combinatorial bounds and algorithms, In
SODA: Symposium of Datastructures and Algorithms 1
At 999 ", better results can be obtained, as suggested by fixing the minimum distance to" 1 ".

[0160]

(38)

Actually, the image processing apparatus 10 uses the standard bucket method to perform the pre-processing of the point sets S and Q into the bucket of size O (Δ ^d ) by O (Δ ^d
+ Dn) time. Side of each bucket, to represent a minimum point distance of the point set Q at d _min (Q), does not exceed _{(d min (Q) -2ε)} / √d. Thus, each bucket has at most one point of the point set Q. Then, since the centroids match, the image processing apparatus 10 has the degree O _d (1) for the selected (d−2) simplex of the point set S of (d−1) points. ), The geometrical query of O (nd) for the points of the bucketed point set Q of the algebraic object, as described below, has the total cost O _d (nΔ
^{d (d-1) / 2} ). The algebraic object is also obtained for the simplex of the point set Q. Once the reference point is selected, each point of the simplex σ∈S is d
Belongs to the common part of the balls or cups. Image processing device 1
0 is the maximum (d-1)! Under the rigid transformation for each (d-2) simplex of the point set Q. The number of simplex matchings is calculated, and it is checked within O (dn) time whether there is any matching. The total cost of this algorithm is O _d (Δ ^d + min ｛λ (d, d−2,
n), nΔ ^{d (d−1) / 2} ｝ T _c (n, m)). Where λ (d, d−2, n) is “T. Akutsu, H. Tamak
i, and T. Tokuyama, Distribution of distances and
triangles in a point set and algorithms for comput
ing the largestcommon point set, Discrete and Comp
utational Geometry, pages 207-331, 1998 ”, and (d−
2) The maximum number of combined simplex copies. Here, it is clear that λ (d, d−2, n) = O (nd ⁻¹ ). Therefore, in this algorithm, the execution time for a dense point set is O _d (n ^{(d + 3) / 2} ).

It should be noted that whether Δ increases with n ^{1 / d} is controversial, and is actually related to the mismatch theory. On the other hand, if Δ is not related to n, the “shape” or principal axis of the point set may be able to be used for joint detection. When two convex layers S ′ and Q ′ are selected from the point sets S and Q, the image processing apparatus 10 needs to detect congruence at S ^d−1 . This is at least 1 /
This is possible by detecting a match of a special subset of 2 ^d , that is, a dense [0,4π] ^d−1 with a density equal to the proportion of matching points. More precisely, the image processing apparatus 10 obtains a set of n points which is a subset of the 2 ^dn point set.

[0163] Next, a description will be given symmetry detection algorithm for a set point of d-dimensional space E ^d. The algorithm used for joint detection described above is the core for efficiently finding the symmetry of a point set. Here, it is considered that all the conversions T (S) satisfying T (S) = S are listed.

The image processing apparatus 10 detects the symmetry of the two-dimensional point set S through a series of steps as shown in FIG.

First, the image processing apparatus 10 calculates the centroid c _S of the point set S in step S41, as shown in FIG. Centroid c _S, for example a two-dimensional set of points _{S = {p i = (x} i, y i)} (n = 1, ··
·, N), the centroid c _S is obtained by the following equation (39). The image processing device 10
A transformation Id, which is an identity map, is added to (S).

[0166]

[Equation 39]

Subsequently, the image processing apparatus 10 proceeds to step S
At 42, the distance f of each point from the centroid c _S
S (S _i ) is obtained by the above equation (24).

Subsequently, the image processing apparatus 10 proceeds to step S
At 43, the associated radius functions F _S , F _S (r) are determined by equations (26) and (28), respectively.

Subsequently, the image processing apparatus 10 proceeds to step S
At 44, F _S ⁺ and F _S ^- are respectively calculated by the above equation (30).
And the above equation (32).

Subsequently, the image processing apparatus 10 proceeds to step S
At 45, it is determined whether or not | F _S ⁻ | ≧ 1.

Here, if | F _S ⁻ | ≧ 1, the image processing apparatus 10 determines in step S46 that p∈F _S ⁻
Is selected, and in step S47, it is determined whether or not the axis of p⊂S at the selected point p is symmetric.

If the axis of p⊂S is symmetric, the image processing apparatus 10 reports T (S) = {symmetry axis (p⊂S), Id} in step S48. A series of processing ends.

On the other hand, if the axis of p⊂S is not symmetric, the image processing apparatus 10 determines in step S49
Report T (S) = Id, that is, identical,
A series of processing ends.

[0174] In addition, in step S45, | F _S ^- |
If ≧ 1, the image processing apparatus 10 determines in step S
At 50, for each S _i ∈F _S ⁺ , its convex hull c
onv (S _i ), and in step S51,
Using the convex hull conv (S _i ), all transformations T
(S _i ) = {T | T (S _i ) = S _i }.

Subsequently, the image processing apparatus 10 proceeds to step S
At 52, the common part of all the transformation sets, that is, the logical product, is calculated by the following equation (40).

[0176]

(Equation 40)

Then, the image processing apparatus 10 proceeds to step S
At 53, T '(S) = T (S) is reported, and the series of processing ends.

As described above, the image processing apparatus 10
The symmetry of the dimensional point set S can be detected.

The image processing apparatus 10 detects the symmetry of the d-dimensional point set S through a series of steps as shown in FIG.

First, the image processing apparatus 10 calculates the centroid c _S of the point set S in step S61 as shown in FIG. The image processing device 10 performs T (S)
Is added to the transformation Id.

Subsequently, the image processing apparatus 10 determines in step S
At 62, the distance f of each point from the centroid c _S
S (S _i ) is obtained by the above equation (24).

Subsequently, the image processing apparatus 10 determines in step S
At 63, the associated radius functions F _S , F _S (r) are determined by equations (26) and (28), respectively.

Subsequently, the image processing apparatus 10 determines in step S
64, F _S ⁺ and F _S ^- are respectively calculated by the above equation (30).
And the above equation (32).

Subsequently, the image processing apparatus 10 determines in step S
At 65, it is determined whether or not | F _S ⁻ | ≧ d−1.

Here, if | F _S ⁻ | ≧ d-1, the image processing apparatus 10 determines in step S66 that at least d−1, at most 2d−3 points
_S ^- selecting a minimum value of the layer of.

Then, the image processing apparatus 10 proceeds to step S
At 67, the conversion of the maximum O ((2d-3)!) Is checked, and at step S68, T (S) is reported, and the series of processing ends.

[0187] On the other hand, in step S65, | F _S ^- |
If not ≧ d−1, the image processing apparatus 10 calculates the convex closure conv (S _i ) for each spherical point set S _i ∈F _S ⁺ in step S69, and in step S70, calculates the symmetric By applying the arithmetic algorithm to the convex sphere, all transformations T (S _i ) =
{T | T (S _i ) = S _i } is listed.

Subsequently, the image processing apparatus 10 proceeds to step S
At 71, the common part of all the transformation sets, that is, the logical product, is calculated by the above equation (40).

Subsequently, the image processing apparatus 10 determines in step S
At 72, one that satisfies T (F _S ⁻ ) = F _S ⁻ is selected from the transform T.

Then, the image processing apparatus 10 proceeds to step S
68, T (S) = {T ｛T ′ (S) s.
t. T (F _S ⁻ ) = F _S ⁻ ｝ is reported, and a series of processing ends.

As described above, the image processing apparatus 10
The symmetry of the dimensional point set S can be detected.

The image processing device 10 can compress data based on the detected symmetry by detecting the symmetry as described above.

The time complexity of these algorithms is the time complexity of detecting congruence of a set of concentric n-points, T _d
It is represented as O (T _d (n) log n) using (n). Here, since it is not necessary to check all the conversions T∈T (S), the image processing apparatus 10 can save the check time.

By the way, since these algorithms use a real RAM model for the calculation, as described above, they have low tolerance to noise such as NP difficulty which is known as a problem for large noise. is there. However, the image processing apparatus 10 calculates the following equation (4)
In the case of 1), when determining whether T (S) = Q, noise can be allowed up to D _min / 2. Further, although the cost of the algorithm is increased by the orthogonal region inquiry algorithm coefficient, the image processing apparatus 1
A value of 0 makes these algorithms more reliable for noise ε ≦ d _min / 2√d, where Further, the image processing device 10
Gives the robustness of the algorithm for all ε represented by the following equation (43) to the algorithm by the coefficient O (d × d
! ) Can be checked.
At this time, the image processing apparatus 10 sets d! The matching point is checked by selecting the closest one of the matching points. If it is desired to obtain an accuracy of ε ≦ d _min / 2, it is necessary to accurately calculate the nearest neighbor point in a high dimension.

[0195]

[Equation 41]

[0196]

(Equation 42)

[0197]

[Equation 43]

[0198] The image processing apparatus 10 performs the above-described "PM Va
idya, An O (nlogn) algorithm for the all-nearest-nei
ghbors problem, Discrete Comput. Geom., 4: 101-115,
Based on the closest algorithm described in "1989", a similar algorithm with the same time complexity can be designed for odd dimensions.

At this time, the image processing apparatus 10 calculates the nearest neighbor graphs nn (S), nn (Q), N of the point sets S and Q.
N a (S), NN (Q), respectively, was calculated from the above equation (18) to equation (21), nn (S), NN _l
(S) is calculated by the above equation (22) and the above equation (23), respectively.
Then, it is determined whether or not | NN _l (S) | = | NN _l (Q) | for all l∈nn (S) ∪nn (Q). That is, the image processing apparatus 10 detects the multiplicity of the point, and thereafter handles a separate point set.

Here, all l∈nn (S) ∪nn
For (Q), | NN _l (S) | = | NN
_{If l} (Q) |, the point sets S and Q are not congruent. The point S∈S is constrained but k _d ≧ 2 ^d
K _d = O _d (1) =
| NN (S) | can only be the closest point. nn
If there are O _kd (1) distinct distances in (S), the image processing apparatus 10 performs a joint check on O _d (T _c (n)). Also, O _kd (1) is _added to nn (S).
If there are no separate distances, there is a distance value l. This distance value l repeats frequently, ie,
Ω (n) when n≫d.

Subsequently, after selecting the ceil [(d-1) / 2] perfectly matching edges having the distance value l, the image processing apparatus 10 has the edge value l.
A point set Q whose size is ceil [(d-1) / 2]
Find all possible combinations that exactly match the.
At this time, the image processing apparatus 10 has also added a centroid to calculate the transformation. Where ceil
[A] is the largest integer not exceeding A.

The time complexity of this algorithm is O (n
^{ceil [(d-1) / 2]} T _c (n)) = O (n ^{ceil [(d + 1) / 2]} lo
gn).

Note that the image processing apparatus 10 can apply the above-described bucketing method in a similar manner.
Since the execution time of the algorithm is a quadratic function,
The image processing apparatus 10 determines that all NN's are within O (n ² ) time.
Can be calculated.

Next, a description will be given of strict self-similarity. If there exists T ≠ Id such that T (Q) = Q, the set Q is said to have self-similarity only then. Also, when there are r different mappings from the set S to the set S itself, it is said that the set S has r-fold similarity only at that time. n or n-
When 1 is divisible by p, there exists a plane point set S having a similarity of 2p, and each has a similarity of 2n / p or 2 (n-1) / p as shown in FIG. Furthermore, due to the presence of mirroring, for any n, 2
There are sets with multiple similarities. Here, for a given integer n, a value of r such that the set S has r-fold similarity is obtained, or for a given n, r
Creating a set of n points with heavy similarity is an interesting issue. Another interesting issue is that in the space of the transformation T, also called the environment space, the characterization is performed and for given integers r and n, the distinct points of r-fold similarity The answer may be whether or not a set of n points exists. Further, it should be noted that an n-point set having r-fold similarity is necessarily a concentric sphere point for a large r. Zabrod
sky etc. are “Hagit Zabrodsky, Shmuel Peleg, and Davi
d Avnir, Symmetry as a continuous feature, Pattern
Analysis and Machine Intelligence, August 93, introduces a continuous measure of symmetry by minimizing the swing of the input points. This continuous measure is also used as a measure of the robustness of the joint detection algorithm. It is possible.

Tables 1 to 3 below summarize the results known in the geometric congruence problem. It also shows references for approximate pattern matching. Note that the approximation coefficient interacts with the noise parameter represented by the symbol ^* .

[0206]

[Table 1]

[0207]

[Table 2]

[0208]

[Table 3]

The problem in the approximation algorithm is described in “P.
J. Heffernan and S. Schirra, Approximate decision
algorithms for point set congruence, Comput. Geom.
Theory Appl., 4: 137-156, 1994 ”,“ MT Goodric
h, Joseph SB Mitchell, and MW Orletsky, Prac
tical methods for approximate geometric pattern ma
tching under rigid motion, In Proc. 10th Annu.ACM
Sympos, Comput. Geom., Pages 103-112, 1994 ”or“ A. Efrat, Finding approximate matching of points.
and segments under translation, Unpublished manus
cript, 1995 ”, it can be seen that, depending on the degree of ambiguity, the question of whether a congruence exists may not correctly report the transformation.
It occurs because the problem modeling is too simple. Here, among various randomization algorithms, “P. Indyk, R.M.
otwani, and S. Venkatasubramanian, Geometric match
ing under noise: Combinatorial bounds and algorithm
s, In SODA: Symposium of Datastructures and Algorit
hms 1999 ”, false negation, which is an algorithm that does not report a conversion even though it exists, and“ Cardoze and Schulman, Pattern
matching for spatial point sets, In FOCS: IEEE Symp
osium on Foundations of Computer Science (FOCS), 1
As shown in 988 ”, we will distinguish between false positives, which are algorithms that report the wrong conversion for some problem reduction. In the latter case, the reported conversion is the correct one. It takes a longer time to check if there is.

Theorem 1: Let S and Q be d-dimensional n-point sets. At this time, whether or not S≡Q can be detected deterministically within O (n ^{floor [(d + 1) / 2]} log n) time.

"J.-D. Boissonnat and M. Yvinec, Alg
orithmic geometry, Cambridge University Press, UK,
1998 "indicates that the largest polyhedron exists on the ^d- dimensional sphere S ^d-1 .

Here, an interesting problem is a function F related to self-similarity as shown in the following equation (44).
Sometimes the spectrum of _S (k, ε) is examined.

[0213]

[Equation 44]

However, in the above equation (44), Sε is represented by the following equation (45).

[0215]

[Equation 45]

This spectrum contributes to both the noise tolerance and the execution time of the geometric pattern matching algorithm. Where f _S (k, ε) = | F _S (k, ε) |
And In particular, if the input can be considered reliable, that is, if ε = 0, then F
_S (k, 0) = F _S (k). f _S (n)
If and only if there is an n-point set S such that = r, the n-point set has r similarities.

Further, the definition shown in the following equation (46) is made as a natural extension.

[0218]

[Equation 46]

The density function is represented by the following equation (47).

[0220]

[Equation 47]

This is described by Akutsu et al. In "T. Akutsu, H.
Tamaki, and T. Tokuyama, Distribution of distances
and triangles in a point set and algorithms for c
omputing the largest common point set, Discrete an
d Computational Geometry, pages 207-331, 1998 ”and is related to the concept of“ scalar product ”of the distance shown in the following equation (48).

[0222]

[Equation 48]

Here, as an example, the following equation (49) is used.

[0224]

[Equation 49]

However, in the above equation (49), the density function is represented by the following equation (50), and C (·) depends on non-combination parameters such as a zoom range, a surface constraint or a match diameter. Is a constraint condition.

[0226]

[Equation 50]

By doing so, it is possible to impose restrictions not only on combinations of matching but also on numerical values. For example, in a vision system, it is desirable to report only those transforms where the angle is in the range of -30 ° to + 30 ° and the zoom is in the range of 1/4 to 4. It is also desirable that all conversions that satisfy C () be reported in dictionary editing order, for example, (θ, zoom). This is referred to as constrained pattern matching.

Next, detection of whether the set S is congruent with a subset of the set Q will be described. here,
Generalization of the "joint problem" described above. The "subset congruence problem" is defined as follows. That is,
The “subset congruence problem” is defined as “two point sets S and Q
Is given, a subset Q ′ of the point set Q that satisfies S≡Q ′ is obtained, counted, one of them is shown, and all of them are reported. That is. For example, as shown in FIG. 21A, a point set S obtained by extracting features from an image or the like depicting a certain car by an angle detection program, and a point set S as shown in FIG. Given a point set Q indicating a certain scene including three copies of the point set Q, a point set S is searched from the point set Q.

In the unconstrained d-dimension, this geometric problem is described in “Tatsuya Akutsu, On determining the
congruence of point sets in d dimensions, Comput.
As described in Geom. Theory Appl., 9 (4): 247-256, 1998 ”, N
It is shown that P-complete is obtained.

Here, if | S | = 1, the problem is self-evident and there are | Q | solutions. ｜ S ｜
If = 2, the problem becomes more theoretically and applicationally more difficult and is related to the maximum number of repeating unit distances. This issue was once presented by PaulErdos. This approach can be applied to incorrect inputs, assuming that the permissible perturbation is less than the minimum point-to-point distance. A _min = max _{l = 1, ..., d} min
_{i, j = 1, ..., n, i} ≠ _j | Q _{i, l} −Q _{j, l} |
Only by multiplying (d × d!), A perturbation up to A _min / 2 can be tolerated. In this case, L ₂
L∞ is due to the existence of the closest contact which gives the same result as the closest contact. When calculating L∞NN, all possible axis permutations are performed, and for each permutation, d one-dimensional N
The closest one obtained when performing N search within logarithmic time is selected. In the orthogonal range inquiry for finding NN ′, the swing of a point within ε ≦ d _min / 2√d can be allowed. Here, d _min is given by the following equation (51).
Is represented by

[0231]

(Equation 51)

One of the features of the problem is that, as shown in FIG. 21, an outlier exists in the point set Q, but no outlier exists in the point set S, that is, all are inliers. Is mentioned. The problem basically consists of two factors. That is, first, a matching transformation T∈T is found, and then the problem of subset matching is solved. It should be noted that the problem of the same number still needs to deal with the infinite alphabet code. Since all the points of the point set S should match, the feature point pairs {S ₁ , S ₂ }, {Q ₁ ,
Given Q ₂ }, there are two ways to match them perfectly, and using these methods the rigid transformation transforms a point in S that matches a pair {Q ₁ , Q ₂ } of a set of points Q Are determined by the pair {S ₁ , S ₂ }, the image processing apparatus 10 performs a series of steps shown in FIG. Can be detected.

First, as shown in the figure, in step S81, the image processing apparatus 10 calculates a geometric graph of the sets S and Q, and uses an enumeration algorithm to define an O defined by a pair of points of the set S. Calculate all (n ² ) sorted distances and all O (m ² ) distances defined by pairs of points in set Q.

Subsequently, the image processing apparatus 10 determines in step S
82, the value D of the common distance between the sets S and Q
From (S) ∩D (Q), select l _min whose repetition distance in set Q has the minimum value _kmin represented by the following equation (52). In the case of constraint selection, the one having the maximum repetition distance in the set Q is selected.

[0235]

(Equation 52)

Subsequently, the image processing apparatus 10 determines in step S
At 83, a pair of arbitrarily selected points of the set S {S
₁ , S ₂ }, a pair of S ₁ and S ₂ such that d ₂ (S ₁ , S ₂ ) = l _min is selected. The image processing device 10 includes S ₁ ,
₂ km _min transformations T [(S ₁ ,
S ₂ ), (Q ₁ , Q ₂ )] and T [(S ₁ , S ₂ ), (Q ₂ ,
Q ₁ )].

Subsequently, the image processing apparatus 10 proceeds to step S
In 84, all other respects pairs {Q _i, Q _j} of the set Q _{of, d 2 (Q i, Q} j) = l is a _min such Q _i, for all pairs of Q _j Te, Q _i, all transformations defined by a pair of _{Q j T [(S 1,} S 2), (Q i,
Q _j )] and T [(S ₁ , S ₂ ), (Q _j , Q _i )].

Then, the image processing apparatus 10 proceeds to step S
At 85, a partial congruence is checked for each transform, all events are reported, and the sequence ends.

By doing so, the image processing apparatus 10 sets the set Q in the two-dimensional set S, Q
Can be searched for all the events of the set S.

The execution time of this algorithm is O (m ²
+ K _min T _c (n, m)). Where _kmin = O
( ^{M 4/3} ), which is approximately equal to O (m 1 ⁺ ε). T _c (n, m) is the time required to examine one transform. Note that T _c (n, m) also depends on the allowable noise parameter ε. When ε = 0, T (n, m) = n log m for a point set at an arbitrary distance. . Therefore, this algorithm uses O (N ²⁺ ε)
It can be executed in O (N ^7/3 log N) time which will be equal to the time, and the efficiency can be improved while being simple. However, it must be noted here that scaling is not allowed and that the execution time of the algorithm depends on the maximum number of iteration distances of the common distance. That is, here, the separated distance of the set Q cannot be selected. When the minimum distance between points of a point set is “1”, such a point set is said to be separated by “1”. In the image processing apparatus 10, all of these algorithms can be implemented using a linear time memory and using an arbitrary distance enumeration algorithm.

Here, when a pattern exists in a scene, it is necessary to note that at least x common distances represented by the following equation (53) exist in D (S) ∩D (Q). is there. The number of distinct distances in the set S is
It is known that it is at least Ω (n ^4/5 ). Therefore, the minimum value of the same distance in the set S is O (n ^{2−4 / 5} ) = O (n ^1.2 ) at the maximum. Further carefully consider k _min, k _min is found to be represented by the formula (54). Therefore, m≪n
If it is ^6/5 , _kmin is represented by the following equation (55).
Therefore, the upper limit of _kmin is “JE Goodman and J.
O'Rourke, editors, Handbook of Discrete and Comput
ational Geometry, CRC Press LLC, Boca Raton, FL, 1
997 ”, n ^1.2 ... ^{M 1.333} .

[0242]

(Equation 53)

[0243]

(Equation 54)

[0244]

[Equation 55]

This algorithm is based on one bar S ₁ S
₂ It is also possible to select (mechanism) in the point set S and lock it to the point set Q.

Here, the distance of the point set _Q is represented by ΔQ. Then, the processing (bucketing) of the point set Q can be performed in O (Δ ² ) time, and one transformation test can be performed within T _c (n, m) = OΔ (n) time. It is possible to do.

The image processing apparatus 10 has a set S,
When Q is d-dimensional, it is possible to detect partial congruence by going through a series of steps shown in FIG.

First, as shown in the figure, in step S91, the image processing apparatus 10 calculates the geometric graphs of the sets S and Q and adds them to the capacity d (e) and g.
(S) and g (Q).

Subsequently, the image processing apparatus 10 determines in step S
At 92, the common capacitance D (S) of the sets S and Q
全 て Activate all hyperedges that are D (Q).

Subsequently, the image processing apparatus 10 determines in step S
At 93, select V _min for which the iterative hyperedge capacity at g (Q) has the minimum value.

Subsequently, the image processing apparatus 10 determines in step S
At 94, a unidirectional δ such that d (δ _S ) = V _min
Select _S.

Subsequently, the image processing apparatus 10 determines in step S
95, the set Q such that d (σ) = V _min
For all hyperedges e, examine all exact transformations induced by V _min and σ, δ _S.

Then, the image processing apparatus 10 proceeds to step S
At 96, a partial congruence is checked for each transform, all events are reported, and the sequence ends.

In this way, the image processing apparatus 10 sets the set Q in the d-dimensional sets S and Q
Can be searched for all the events of the set S.

Theorem 2: When S is a set of n points in the two-dimensional space E ² and Q is a set of m points in the two-dimensional space E ² , it is determined whether or not the point set S exists in the point set Q. To O (m ² + min ｛m ^4/3 , m ² /
n ^4/5 ｝ T _c (n, m)) time. Here, diameter (S) = diameter
In the case of (Q), O (m log m + mT _c
(N, m)) and O (m
log m + min ｛m log m, m ² / n｝ n l
og m) can be done in time.

The results described above are described in “T. Akutsu, H. Ta
maki, and T. Tokuyama, Distribution of distances a
nd triangles in a point set and algorithms for com
puting the largest common point set, In Proc. 13th
Annu. ACM Symps. Comput. Geom., Pages 314-323, 199
It is an improvement on m≪n ^6/5 based on the spirit of 7 ”.

There are the following two limiting factors in the image processing apparatus 10. That is, first compute the geometric graph, especially the set Q, and then independently test each of the possible transforms.

When _kmin is small or m≫n, the image processing apparatus 10 calculates the geometrical graph of the sets S and Q by the following equations (56) and (57). It is not necessary to calculate all the x and y distances to be calculated. First, the image processing apparatus 10 picks up an arbitrary point pair (S ₁ , S ₂ ) of the set S. Subsequently, the image processing apparatus 10 makes a reduced ring-shaped inquiry for all i∈ [1, m]. That is, the image processing apparatus 10 makes an inquiry about a circle whose center is Q _{i and} whose radius is d ₂ (S ₁ , S ₂ ). The maximum number of common distances l is related to the probability of occurrence of n points in m circles. This is O
It is known that it is restricted by (n ^2/3 + m ^2/3 + n + m).

[0259]

[Equation 56]

[0260]

[Equation 57]

As an alternative to the geometric inquiry, the image processing apparatus 10 uses “TMChan, On enumeratin
g and selecting distances, In Proc. of the 14th Sy
mp. of Comp. Geo., 1998 ", an output-dependent algorithm may be used to enumerate only selected distances. T ₂ pairs with the same distance in set Q can be reported in O (n ^4/3 log ^8/3 n) time, ie, “T. Akutsu, H. Tama
ki, and T. Tokuyama, Distribution of distances and
triangles in a point set and algorithms for compu
ting the largest common point set, Discrete and Com
putational Geometry, pages 207-331, 1998 ”, O (n ^4/3 log ^8/3 n + t ₂ n
log m) A time algorithm is obtained. The constraint is
“TM Chan, On enumerating and selecting distanc
es, In Proc. of the 14th Symp. of Comp. Geo., 199
8 ", the output is O (n
log n + n ^2/3 k ^1/3 log ^6/3 n).

Another approach is to use a grid or multiple grids,
That is, creating a bucket as described above. Since at most one point exists at each position of the bucket, a Boolean bucket such as that shown in FIG. 24 is sufficient, for example. The image processing apparatus 10 makes an inquiry once for each point of the set Q with respect to one inquiry S ₁ S ₂ , and executes O (n) times in total, so that Check O (nΔ) positions.

Actually, when the pair of feature points (S ₁ , S ₂ ) is given, the image processing apparatus 10 sets | d ₂ (S ₁ , S ₂ )
−d ₂ (Q ₁ , Q ₂ ) | ≦ γ All pairs of points (Q ₁ , Q 2
₂ ) Select Here, γ satisfies γ ≧ 4 when the range is zoomed. This means that for each point Q _i in the set Q, the center is Q _i and the inner diameter is d ₂ (S ₁ ,
This is done by querying all points in the annulus with S ₂ ) −2ε and outer diameter d ₂ (S ₁ , S ₂ ) + 2ε. One method is to sort the distances D _S , D _Q and for a given query l, replace all pairs in the set Q whose distances range from l−2ε to l + 2ε with O (log n +
k) To report in time. Therefore, the execution time of this primitive method is O (m ² log
m + kT _c (n, m)). When the pattern matching algorithm is limited to be executed in the zoom range [z _min , z _max ], the image processing device 10
A range inquiry is performed as follows with respect to a given point pair S ₁ S ₂ (b = d ₂ (S ₁ , S ₂ )). That is,
The image processing device 10 calculates (b−2ε) * z _min ≦ d
_{2 A} set Q satisfying (Q _i , Q _j ) ≦ (b + 2ε) * z _max
Report the pair Q _i Q _j of all points in. Further, the image processing apparatus 10 may also be added to the angle of the constraints on Q _i Q _j of S ₁ S _2. For example, the image processing apparatus 10 has a tilt of 30.
制約 Restrict to only things that are not different.

Next, a data structure for a ring inquiry will be described. Problem of "annular inquiry" is, for example, those illustrated in FIG. 25 (A), as sector query shown in FIG. (B), when n point set in the "E ² are given, with respect to the ring-shaped Us And report every point in the ring. "

For this purpose, the image processing device 10
“P. Gupta, R. Janardan, and M. Smid, On intersecti
on searching problems involving curved objects, In
Proc. 4th Scand. Workshop Algorithm Theory, volum
e 824 of Lecture Notes Comput.Sci., pages 183-19
4, Springer-Verlag, 1994 ”and“ P. Gupta, R. Janarda
n, and M. Smid, Further results on generalized int
ersection searchingproblems: counting, reporting an
d dynamization, J. Algorithms, 19: 282-317, 1995 ”
Can be used. The query time required to report t points in the query ring is O (log n + t log ² n), requiring O (n ³ / log n) as the pre-processing time. In order to count, the O (log ² n) count processing time is required after the O (n ⁴ log ² n) pre-processing time. The challenge here is to report all pairs of points pq whose distances are in the range d−2ε to d + 2ε.

A practical example of grouping and inquiry is shown below. The image processing device 10 has a maximum size of | n / p |
Are created, and the processing of the total cost O (n ³ / p ³ log n / p) is performed for each group. Next, the image processing device 10 determines that R = [d−2ε, d +
For a distance range of 2ε], we report all pairs of points pq where d (p, q) ∈R. The image processing apparatus 10 calculates each point Q
The ring query is performed once for _i iQ and m times for the point set Q. Therefore, the total cost is O (n
² / p log n / p + t log ² n / p) time. In order to balance the inquiry time and the preprocessing time, p may be selected as in the following equation (58).

[0267]

[Equation 58]

At this time, there are two cases. That is, when t ≦ n ² / (p log n / p),
Choose p = n ^{1 / 2-} ε. In this case, O (n
3/2 ⁺ ε) time algorithm is obtained. Also, t ≧ n ²
/ (P log n / p), p = n / t
Select ^{1 / 3-} ε. In this case, O (t log ²
t) It becomes a time algorithm.

Since the image processing apparatus 10 cannot know the value of t in advance, the image processing apparatus 10 sets “F. Nielsen,
Algorithmes Geometriques Adoptatifs-Adoptive Compu
tational Geometry, Ph.D. thesis, isbn-2-7261-1017-
7, Nice Univ. (Franc), 1996 ”, a rough estimate is made using t ≒ 22 ^{(i / 2)} (i ≦ 2 log log t). , T, an output-dependent algorithm is obtained.

A bottleneck of this algorithm is that it is expensive to evaluate each transform independently. Therefore, the image processing apparatus 10 may not need to evaluate each conversion independently.

Here, let T (t ₂ ) be a set of transforms reported by the above-described algorithm. The image processing apparatus 10 outputs bars of different lengths of D (S) one at a time.
And repeat the process as follows. In the image processing apparatus 10, a number of different transformations t ₂ ⁽¹⁾ ,..., T ₂ ^(l) are obtained in each stage. Image processing device 1
A 0 assumes that a pattern exists and selects the first l similar distances D (S) パ タ ー ン D (Q). Subsequently, the image processing apparatus 10 calculates a common part represented by the following equation (59). Finally, the image processing device 10 calculates the score of each transform T∈T ′, and selects the one with the highest score. The total cost at this time is O (| T '
| T _c (n, m)) = O (| T ′ | n log m).

[0272]

[Equation 59]

It should be noted here that this algorithm reports all partially congruent copies.

More specifically, the image processing apparatus 10
By performing a series of steps shown in (1), pattern matching including transfer and / or rotation is performed. Here, it is assumed that the two-dimensional point sets Sε and Qε are sets having a swing of ε.

First, in step S101, the image processing apparatus 10 determines that the maximum side length is b
The orthogonal boundary region of the point set S is calculated as follows. The upper limit of the diameter of the point set S is set to Δ = √ (2b).

Subsequently, the image processing apparatus 10 determines in step S
At 102, the magnitude is ceil [Δ / ε] +2,
A one-dimensional binary Boolean bucket B _S with all elements set to “0” as initial values is created. The Boolean bucket B _S is used for bucketing the distance between points.

Subsequently, the image processing apparatus 10 determines in step S
In 103, S _j ≠ S _i any (S _i, S _j) is a point distance of a pair of _{d 2 (S i, S j} ) with respect to, the index _{l = floor [d 2 (S} i , S _j ) / ε],
_{B S [l-1],} B S [l], a mark of B _S [l + 1]. Then, the image processing apparatus 10 creates a list of point distances for each bucket B _S. However, the list of distances between points is empty in the initial state.

Subsequently, the image processing apparatus 10 determines in step S
At 104, k = 1 is set as the initial value of the stage.

Subsequently, the image processing apparatus 10 determines in step S
At 105, it is determined whether or not k ≦ ν.

Here, if k ≦ ν is not satisfied, the image processing apparatus 10 shifts the processing to step S109, and randomly selects a pair of point sets S S ₁ ^(k) and S ₂ ^(k). .

Subsequently, the image processing apparatus 10 determines in step S
At 110, let l _k = d ₂ (S ₁ ^(k) , S ₂ ^(k) ), and l
Let b _k = floor [l _k / ε]. Image processing device 10
Is P _s (lb _k −1) ∪P _s (lb _k ) ∪P _s (lb _k +
Examine all pairs (Q _i , Q _j ) of 1) and find | d ₂ (Q _i ,
Select all pairs _where Q _j ) −l _k | ≦ 2ε. The set of transforms defined by these points is denoted by T _k . Here, since it is assumed that a constant zoom is performed, only the rotation and the transition need to be considered as parameters.

Subsequently, the image processing apparatus 10 proceeds to step S
At 111, use B _S , T _k to get all possible transitions of the point set Q.

Then, the image processing apparatus 10 determines in step S
At 112, k = k + 1, and again at step S10
The processing after 5 is repeated.

On the other hand, in step S105, k ≦ ν
When the image processing apparatus 10 determines that the common transition μ is calculated by the following equation (60) in step S106. Here, in order to calculate the set T of the common transition μ, it is necessary to define when the similarity of the two transforms becomes μ overlapping. The two transforms T ₁ , T ₂ are, for all P∈S, d ₂ (T
_{When 1} (P), T ₂ (P)) ≦ μ, the similarity is referred to as μ. The image processing apparatus 10 performs an approximate inspection by sequentially inspecting the corners of the bounding box of the point set S instead of inspecting all the points of the point set S.

[0285]

[Equation 60]

Subsequently, the image processing apparatus 10 proceeds to step S
At 107, it is determined whether T metastasis triggers the event. The image processing apparatus 10 checks by, for example, bucketing the point set S, or performing 21-d binary searches. When buckets are used, the width of each bucket is ε, as shown in FIG.

Then, the image processing apparatus 10 determines in step S
At 108, a report, conversion listing, and the like are performed, and a series of processing ends.

By doing so, the image processing apparatus 10 can generate a two-dimensional point set Sε,
Pattern matching including transition and / or rotation in Qε can be performed.

The time complexity when listing all matching transforms using this algorithm is O ((Δ _S / ε)
+ N ² + m ² + ν + tt ′ + t′T _c (n, m)). In this case, it should be noted that it is Δ _Q ≧ Δ _S. However, when μ = 0, the image processing device 10
Sorts the matrix and calculates T represented by the following equation (61) within O (t log t ') time. Therefore, the time complexity is O ((Δ _S / ε) + n ² + m ² + ν +
(T log t ′) + t′T _c (n, m)).

[0290]

[Equation 61]

Here, ε is fixed at ε = d _min / 2. Here, d _min = min {d _minS , d _minQ }.

In the image processing apparatus 10, for example, when N ² is larger than the RAM memory size or when a large point set density is required in real time, a series of operations shown in FIG. Preferably, processing is performed.

First, in step S121, the image processing apparatus 10 determines that the maximum side length is b
Is calculated, and the upper limit of the diameter of the point set S is set to Δ = √ (2b).

Subsequently, the image processing apparatus 10 determines in step S
At 122, a bucket B _Q of size γ is created on the point set Q, and for each Q _i ∈Q, Q _i is added to the corresponding position. Here, as shown in FIG.
Note that there can be more than one point in a bucket.

Subsequently, the image processing apparatus 10 determines in step S
At 123, k = 1 is set as the initial value of the stage.

Subsequently, the image processing apparatus 10 determines in step S
At 124, it is determined whether k ≦ ν.

Here, if k ≦ ν is not satisfied, the image processing apparatus 10 shifts the processing to step S128, and randomly selects a pair S ₁ ^(k) and S ₂ ^(k) of the point set S. .

Subsequently, the image processing apparatus 10 determines in step S
129, l _k = d ₂ (S ₁ ^(k) , S ₂ ^(k) ), and (Q _i , Q _j ) s. t. | D
₂ (S ₁ ^(k) , S ₂ ^(k) ) − d ₂ (Q _i , Q _j ) | ≦ 2ε is searched for all pairs. In practice, the image processing device 10
Search for supersets. The set of transforms obtained from the pair of points in this way is defined as T _k .

Subsequently, the image processing apparatus 10 determines in step S
At 130, use B _Q , T _k to obtain all possible transitions of the point set Q.

Then, the image processing apparatus 10 proceeds to step S
At 131, k = k + 1 is set, and again at step S12
The processing after 4 is repeated.

On the other hand, in step S124, k ≦ ν
If the image processing apparatus 10 determines that the common transition μ is set in step S125, the image processing apparatus 10 calculates the set T of the common transition μ represented by the above equation (59) in step S125. The image processing device 10
Similar to step S106 in FIG. 26, an approximate inspection is performed by sequentially inspecting the corners of the bounding box of the point set S instead of inspecting all the points of the point set S. It should be noted that an accurate check as to whether or not the similarity is μ is possible only by examining points on the convex hull.

Subsequently, the image processing apparatus 10 executes step S
At 126, it is determined whether the transfer of T triggers an event. The image processing apparatus 10 checks by, for example, bucketing the point set S, or performing 21-d binary searches. When buckets are used, the width of each bucket is ε, as shown in FIG.

Then, the image processing apparatus 10 proceeds to step S
In step 127, a report, conversion listing, and the like are performed, and a series of processing ends.

The execution time of this algorithm is O ((Δ
_Q / γ) ² + νnΔ / γ + tt ′ + t′T _c (n, m))
It is. Here, the parameter γ needs to be tuned according to the actual purpose. The image processing apparatus 10 estimates γ through a series of steps shown in FIG.

First, as shown in the figure, the image processing apparatus 10 initializes γ by a program or a user in step S141.

Subsequently, the image processing apparatus 10 proceeds to step S
At 142, the number of transforms to test is Wσ.

Subsequently, the image processing apparatus 10 determines in step S
In 143, it is determined whether or not Wσ × check> CT (γ).

Here, if Wσ × check> CT (γ), the image processing apparatus 10 proceeds to step S144.
, A better and smaller value for γ is obtained. That is, the image processing apparatus 10 sets γ = γ / 2 or sets γ to some value selected from the point coordinates. Then, the image processing apparatus 10 repeats the processing from step S143 again.

On the other hand, if Wσ × check> CT (γ) is not satisfied, the image processing apparatus 10 returns γ in step S145, and ends the series of processing.

[0310] Thus, the image processing apparatus 10
Can be estimated.

[0311] The image processing apparatus 10 can perform scene analysis by performing pattern matching.

The image processing apparatus 10 refines the complexity analysis as follows, assuming that the point sets are dense and uniformly distributed, that is, Δ = O (√n). It is possible.

That is, each bucket has, on average, nγ
Having a point ² / delta ^2. Since the image processing apparatus 10 examines nΔ / γ of these points, a superset of pairs of points having a size of n ² γ / Δ is obtained. Therefore,
By setting γ = Δ / n ^2/3 , the image processing apparatus 10
Is the cost of pre-processing, ie, O ((Δ /
γ) ² ) and the cost of making inquiries can be balanced. Thus, the complexity of the algorithm is that for small values of μ, O (n ^4/3 + (t log
t ′) + t′T _c (n, m)). Also, t ≦ n ^4/3
It should also be noted that In the image processing apparatus 10, the number of pairs to be checked can be easily counted.

This method can be applied in all dimensions. However, in higher dimensions, it is necessary to handle d-dimensional simplex instead of simple bar method. When the dimension becomes larger than "4", the number of the same distance defined by one point set increases according to the quadratic equation. For a recent accurate boundary method for universal use of randomness in the design of the Las Vegas and Monte Carlo algorithms, see "T. Akutsu,
H. Tamaki, and T. Tokuyama, Distribution ofdistanc
es and triangles in a point set and algorithms for
computing thelargest common point set, In Proc. 1
3th Annu. ACM Symps. Comput. Geom., Pages 314-323,
1997 ”and“ T. Akutsu, H. Tamaki, and T. Tokuyama, D
istribution of distances and triangles in a point
set and algorithms for computing the largest commo
n point set, Discrete and Computational Geometry, p
ages 207-331, 1998 ".

Further, when ε satisfying ε> 0 is given,
There may be point swings that result in multiple degenerations. Such swings cause the pattern matching algorithm to slow down. Furthermore, the matching of noisy patterns is more delicate compared to the matching of exact patterns without noise. Another way is to allow the same matching for all swings given ε '. In the image processing apparatus 10, only stable matching is handled by restricting the boundary of ε to be 0, D _min / 2√2, A _min / 2, d _min / 2. .

In the above-described algorithm, for example, for the set S shown in FIG. 29A and the set Q shown in FIG. The scaling was not considered, as was the case. Therefore, hereinafter, partial congruence in the case where uniform scaling is performed will be described. If scaling is allowed, the solution to the problem will be different from that described above. In this case, fix the bar on the set Q,
It is no longer possible to adopt a method of examining the transformations due to this. The reason is simple: when S is a set of two points, there are x exact matches in the set Q represented by the following equation (62). Consider combining the results to get a more efficient algorithm. According to Elekes and Erdos, the number of similar triangles is Ω (n ² ), and the number of pairs of similar triangles is Θ (n ^3/2 ). Therefore, in the image processing device 10, the maximum number t of similar triangles in the set S is t.
_The algorithm shall be changed according to ₃ . First, the image processing apparatus 10 calculates a geometric graph of the sets S and Q in O (N ² ) time, and for each point Q _i ∈Q, a one-dimensional defined by the angle of a circulating continuous point. Map the geometric graph of. Then, the image processing device 10 attaches an annotation indicating each distance to each node.

[0317]

(Equation 62)

The triangle T _{S of the} set S = (S ₁ , S ₂ , S ₃ )
Is selected, the image processing apparatus 10 simply proceeds with the process as follows. When the set S exists,
Such triangles appear in the set Q. First, the image processing device 10 searches for all similar triangles in the set Q. Here, each match defines six possible rigid body motions to check. The total cost of this algorithm is O (N ² log N + t ₃ T _c (n, m))
= O (N ³ log N). Further, instead of selecting a triangle, the image processing apparatus 10 simply selects the k subset of the set S, and executes a similar algorithm with a total cost O
^{_{k (N 2 log N + t}} k T c (N, M)) may be executed at. Here, t _k = Ω (n), and for a large value of k, it matches the lower boundary of the repetition unit distance. The execution time of this algorithm is O (N ²⁺ ε l
og N).

Here, r = d ₂ (S ₁ , S ₂ ) / d
₂ (S ₁ , S ₃ ), α = ∠S ₂ S ₁ S ₃ . It is known that in the set Q, the angle α can be found within the maximum O (n ² log n) time.

[0320] The image processing apparatus 10 detects partial congruence through a series of steps shown in FIG.

First, as shown in the figure, in step S151, the image processing apparatus 10 calculates G (Q) and associates each node with the list of the angles that are cyclically sorted. The image processing apparatus 10 sorts the repetition angles in the radial direction.

Subsequently, the image processing apparatus 10 determines in step S
At 152, an angle 3 in G (Q)
Labels for all combinations of points are labeled O (m ² log
m) Give within time. The image processing apparatus 10 checks whether the ratio is r or 1 / r for the combination of three points. The ratio of the triangle xab to the vertex x is the ratio of the length of the side incident on x, that is, d ₂ (x, a) / d
₂ Defined by (x, b). Note that there can be many sets of three points on the same straight line. This is a pattern matching problem on S ^1. Here, a set of transforms obtained by the triangles recognized as valid is represented by T _S (Γ).

Then, the image processing apparatus 10 proceeds to step S
In 153, the set of all three valid t ₃ points is checked, and the series of processing ends.

The total cost of the algorithm at this time is O
(M ² log m + t ₃ T _c (n, m)) = O (N ³ l
og N) hours.

Actually, there is an absolute error ε, and | T
_S (Γ) | increases, the image processing device 10
Detects partial congruence by going through a series of improved steps using the iterative method shown in FIG.

[0326] First, the image processing apparatus 10, as shown in the figure, in step S161, from i to l, randomly draws a triangle gamma _i in the set S, calculates the T _S (Γ _i).

Subsequently, the image processing apparatus 10 proceeds to step S
At 162, T represented by the following equation (63) is calculated.

[0328]

[Equation 63]

Then, the image processing apparatus 10 proceeds to step S
In 163, it examines partial congruence to all conversion T∈T _S, the series of processing is terminated.

The execution time of this method is O (1N ² log
N + | T | T _c (n, m)).

[0331] When one triangle is given, the image processing apparatus 10 can find a similar triangle in the set Q by an inquiry as shown in FIG. In practice, the image processing apparatus 10 finds all matching congruent triangles and matching mirrored congruent triangles.
Further, the image processing apparatus 10, starting from Q ₁ 1 one of the selected _{points, | d 2 (S 1,} S 2) -d 2 (Q 1, Q 2) | ≦
Query whether there is any Q ₂ present in the ring defined by 2ε. The image processing apparatus 10 generates two intersecting rings for each point obtained by this inquiry.
| D ₂ (S ₁ , S ₃ ) −d ₂ (Q ₁ , Q ₃ ) | ≦ 2ε and | d
₂ (S ₂ , S ₃ ) −d ₂ (Q ₂ , Q ₃ ) | ≦ 2ε Select all points Q ₃ in the two connected elements.

The image processing apparatus 10 performs this processing by sweeping from the intersection of two algebraic rings.
(1) It can be executed in time. Therefore, the execution time of this algorithm does not change. When a subset of p points is selected, to select the i-th point, the algebraic intersection of x rings represented by the following equation (64) is calculated. However, when i ≧ 3, it collapses into one domain.

[0333]

[Equation 64]

The processing described above can be naturally extended to an arbitrary dimension, as already described in the description of the joint algorithm.

Σ _S = (S ₁ ,..., With the maximum being ε)
Consider searching for all simplexes similar to S _d ). Here, consider anchoring a similar simplex for each point Q _i ∈Q. _First , the image processing apparatus 10 first performs Ring (Q ₁ , d ₂ (S ₁ , S ₂ ) -2) on the simplex anchored at the point Q _1.
Find out all Q ₂ present inside ε, d ₂ (S ₁ , S ₂ ) + 2ε). Such Q ₂ is at most O (Δ ^d-1 )
Exists. Next, the image processing apparatus 10 sets the common part Ring (Q ₁ , d ₂ (S ₁ , S ₃ ) -2) between the rings.
ε, d ₂ (S ₁ , S ₃ ) + 2ε) ∩Ring (Q ₁ , d
₂ (S ₂ , S ₃ ) −2ε, d ₃ (S ₂ , S ₃ ) + 2ε) is searched for Q ₃ . When bucketing is performed, there are O (Δd ⁻² ) Q _{3 at} maximum. The image processing apparatus 10 searches for Q _i existing inside the common part represented by the following equation (65) by repeatedly performing such processing.

[0336]

[Equation 65]

The maximum number of such Q _i is O (Δ ^di ). Therefore, the following equation (66) exists at the maximum at the anchor point Q ₁ . That is, in the set Q,
A simplex similar to σ _S is O (n
Δ ^{d (d-1) / 2} ).

[0338]

[Equation 66]

Next, the maximum common point set (S, Q) will be described. That is, here, S′⊆S,
Find the maximum of | S ′ | that satisfies Q′⊆Q and S′≡Q ′. This is called the "maximum common set problem". The problem of finding the largest common set of k given sets is described in "T. Akutsu and MM Hall
dorsson, On the approximation of largest common su
btrees and largest common point sets, In Proc. 5th
Annu. Internat. Sympos. Algorithms Comput., Volum
e 834 of Lecture Notes Comput.Sci., pages 405-41
3, Beijing, China, 1994, Springer-Verlag "has been found to be NP-complete.

Here, consider the following maximum common point set problem. "When given two d-dimensional point sets S and Q, find the largest subset S'S that satisfies S'≡Q'⊆Q."

A simple trivial algorithm to test all x transforms represented by the following equation (67) and to choose or vote the best is O (N ⁵ log N)
Takes time. Here, N = max {n, m}.

[0342]

[Equation 67]

Now, consider the following decision problem. That is, as a k-common point set problem, when two d-dimensional point sets S and Q are given, S′⊂S, Q ′
Is there something that is ⊂Q and | S '| = | Q' | = k and S'≡Q '? "

FIG. 33 shows a maximum common point set and the next largest common point set as examples of the maximum common point set. The maximum common point set can be determined within O (log n) T _D (n, m) time. Where T _D (n, m) is the time required to solve the decision problem.

An algorithm for solving the decision problem is proposed below. As described above, the image processing apparatus 10 performs processing for each stage.
It is as shown in.

First, as shown in the figure, in step S171, the image processing apparatus 10
^{(N 2) O (m 2} ) of the pieces of distance D _S and the set Q to calculate all the pieces of distance D _Q. Here, the edge value e is e {D _S }
When it is _DQ, it is possible. Image processing device 10
Marks all possible edges and removes possible ones from D _S , D _Q.

Subsequently, the image processing apparatus 10 determines in step S
At 172, among the common distances of the sets S and Q, the one having the minimum number of repetition distances represented by the following equation (68) is selected.

[0348]

[Equation 68]

Subsequently, the image processing apparatus 10 determines in step S
In 173, to test for _{2D S (l min) * D} Q (l min) pieces all positions. T _c (n, m) = O to calculate the size of the match for one position
It takes (n log m) time. Here, m represents the size of the matching in this stage.

In the next stage, the image processing apparatus 10 limits the size of the matching to at least m and selects another distance value. The image processing device 10
To improve the speed of the algorithm, the distance d = d ₂
In performing the test on (p _i , p _j ), the point set is simplified except for a part of the outlier. Here, if there is no large "matching", it is known that at least one of the points is an outlier. Similarly, the distance of all similar, i.e., D _S -D _Q
Are always known if they always have one outlier point and do not allow scaling. The time complexity of this algorithm is O (N log N × N
^16/9 N ^{2-4 / 3} ), that is, O (N ^31/9 log n) =
O (n ^3.445 log n) hours.

In the image processing apparatus 10, the majority method is used as follows. That is, the image processing apparatus 10
Makes the rotation space discrete with a small rotation amount of O (Δ).
Next, the image processing apparatus 10 applies the well-known Ballard method in a certain fixed rotation. In the image processing apparatus 10, for the pair of points S∈S, Q∈Q, Q ′ is a ring Ring (Q, d ₂ (S, S ′) − 2).
All transformations T [S, S '; Q, Q'], T [S, S ';Q', such as exist in ε, d ₂ (S, S ') + 2ε)
Q]. The image processing apparatus 10 adds a vote every time such a conversion is found. Finally, the image processing device 10 selects or reports all the conversions that have obtained the largest votes. For example, a transformation with p votes is a size p +
It has a common point set that is 1.

Next, the maximum common point set when zooming is performed will be described. Again, a similar triangle is selected, as described above. In addition, the so-called Huff
ugh) Apply a majority algorithm similar to this to this.

The algorithms described so far all have an execution time that depends on the concept of partial symmetry. Here, two transforms are said to have partial symmetry if they match at least two points and they are equivalent modulo rotation matrices TR.

Therefore, the image processing apparatus 10 determines that a transformation T∈T that matches a point is found, ie, |
When S∩T (Q) = M where M | = r,
Subset Q ′ of Q defined by the following equation (69)
Can be computed that matches the r points of M with.

[0355]

[Equation 69]

Here, the symmetric group T (M) of M has already been added. The image processing apparatus 10 stores a list of conversions in a memory in order to avoid performing the calculation of the conversion twice.

Next, the random constraint placement method will be described. Let k be the number of point pairs needed to define the transformation T∈T. For example, for translation, rotation, uniform scaling or zoom, k = 2. here,
Assume that α% of the points match. At this time, the image processing apparatus 10 can obtain a conversion satisfying the condition with a probability of about 1-α ^k . Further, the image processing device 10
First looks for a subset of size r if the transform matches a% points when looking for the k-subset. If the subset matches at least β%, the image processing apparatus 10 tests all the sets, and rejects the conversion if the subset does not match at least β%. The image processing apparatus 10 repeats such processing O (1) times. That is, a t-time algorithm represented by the following equation (70) is obtained. Here, the following equation (71) relates to the similarity of Q, and C (•, •) is the cost of measuring the accuracy of the matching algorithm. The image processing device 1
A value of 0 can be similarly obtained by using the birthday deparadox method. X points of both sets represented by the following equation (72) are repeatedly sampled.

[0358]

[Equation 70]

[0359]

[Equation 71]

[0360]

[Equation 72]

Here, it is assumed that only the transformation T∈T that is meaningful in a certain application is of interest. For example, | d
Assume that one is interested in a transformation such that (T (S _i ), T (S _j )) − d (S _i , S _j ) | ≦ ω. here,
ω is an amount dependent on the reliability of the input. Instead of testing all of the _k -subsets (S ₁ ,..., S _k ) of Q, the image processing apparatus 10 first selects a point Q ₁ ∈Q and centers the point Q ₁ Only points inside the ring whose inner diameter is d (S ₁ , S ₂ ) −ω and whose width is 2ω are selected as Q ₂ candidates.
Here, ω is a specified parameter. Image processing device 1
0 repeatedly performs such processing and queries the set Q within the geometric range that imposes the above-described constraint on the transformation T. Here, it is assumed that the following equation (73) is the number of sets of k k points satisfying the above-described constraint. Here, t is an amount depending on the self-similarity of the point set Q.

[0362]

[Equation 73]

For example, k = 2. Here, when a pair of points {S ₁ , S ₂ } taken at random from the set S is given, the image processing apparatus 10 calculates | d (Q ₁ , Q ₂ ) −d
A pair of points of Q such that (S ₁ , S ₂ ) | ≦ ω ｛Q ₁ ,
Search for Q ₂ ｝. Ideally, the distance is d (S ₁ , S ₂ )
It is desirable to list all pairs of Q points that lie between −ω and d (S ₁ , S ₂ ) + ω, but this is a difficult problem in itself. Therefore, the image processing device 10 proceeds as follows. That is, the image processing device 10
Points Q are sequentially selected, and a ring having a radius of d (S ₁ , S ₂ ) -ω and a width of 2ω is drawn with respect to the current point Q _i . Then, the image processing apparatus 10 reports all the Q points inside the ring. Now, let t be the number of points reported in all stages. At this time, if ω = 0, t is also restricted by the number of distance repetitions in the complete geometric graph. Alternatively, t is constrained by the maximum appearance rate of m circles having m points. The appearance rate is O
(M ^4/3 ) = o (m ² ), and Erdo
According to s, this value is estimated to be O (n 1 ⁺ ε). The image processing apparatus 10 is described in “P. Gupta, R. Janarda
n, and M. Smid, On intersection searching problems
involving curved objects, In Proc.4th Scand. Wor
kshop Algorithm Theory, volume 824 of Lecture Note
s Comput.Sci., pages 183-194, Springer-Verlag, 19
94 ", create a data structure and report the t point pairs to be tested. This approach can be generalized to any dimension, but with d ≧ 4 In some cases, the number of unit distances is given by a quadratic function, and this query method can also be used to check whether a given transform T matches or not. First, check for O (1) points and then extend to the entire set.The geometric filtering in the placement method can be used as a general method, but according to the specific application, Need to tune.

The image processing apparatus 10 can synthesize images by detecting the maximum common point set as described above. For example, a panoramic synthesized image or a perspective synthesized image excellent in perspective can be obtained. Can be generated.

Next, conditional geometric hashing will be described. Geometric hashing was first performed by “Y. Lam
dan and HJ Wolfson, Geometric hashing: a general
andefficient model-based recognition scheme, In 2
nd Inter. Conf. on Comput. Vision, pages 238-249,
1988 ”, introduced by“ Y. Lamdan, JT Schwartz,
and HJ Wolfson, Object recognition by affine i
nvariant mapping, In Proc. IEEE Internat. Conf. Co
mput.Vision Pattern.Recogn., pages 335-344, 198
8 ”or“ Y. Lamdan and HJ Wolfson, On the error a
nalysis of geometric hashing, In Proc.IEEE Intern
at. Conf. Comput. Vision Pattern. Recogn., pages 2
2-27, 1991. Geometric hashing can be used to make multiple queries between a fixed set of points Q, the model, and various scenes, the point set S. Here we show how to formalize and apply geometric constraints to geometric hashing, which is roughly divided into two stages: a preprocessing stage and a query stage. The processing stage maps the model to itself, and the query stage answers within a short time whether there is a match, where the transformation from Q to S is a set of two k points. Defined by

[0366] As a pre-process of the model Q, the image processing apparatus 10 selects an arbitrary set Q out of a set consisting of k points of Q.
Select _T. Next, the image processing apparatus 10 transmits all possible permutations of the possible k! Consider all of the transforms. Image processing device 10
Creates a set T _i (Q) for a given transformation T _i , which is a transformation obtained from Q _T and another set of k points, and labels the label 'T _i ' with each point P∈T _i (Q) is stored in a hash table. That is, the image processing device 10
The label 'T _i ' is stored in H (P) using the rectangular coordinates.

[0367] Then, the image processing apparatus 10 sets the scene S
As a query of, check all k-point sets of S,
Search for all model-to-scene transformations T _i ′ that are transformations on Q _T. The image processing apparatus 10 creates a set T _i ′ (S) for each transformation T _i ′ and stores it in the hash table. More precisely, the image processing device 1
0 means that all points P _j ∈T _i ′ (S) are sequentially examined and H
One vote is added to all conversions stored in (P _j ). After examining all the transformations T _i ′, the image processing apparatus 10 selects or enumerates the one with the largest number of votes. Finally, the image processing device 10 performs a direct conversion from the model to the scene, as described later.

The operation of the geometric hashing is basically that the transform space converts its arbitrary transform into two transforms T = T ₁ × so that the transform space can be regarded as, for example, the product of matrices.
It is based on a group that can be decomposed into T _2. Therefore, the image processing apparatus 10, in order to map the set of points from the model T _Q to a set of points in the scene T _S, initially, to map the T _Q to Q _T is a set of criteria in Q, the following Map Q _T to T _S. Therefore, the following equation (74) is obtained.

[0369]

[Equation 74]

Note that the geometric filtering technique can be applied to the above-described geometric hashing.
For example, when it is desired to perform processing with a constant zoom, the image processing apparatus 10 performs a conversion whose zoom ratio is 1 / b corresponding to the current conversion represented by the following equation (75) where the zoom ratio is b. It is only necessary to check the hash table H. At this time, the term of ε is also replaced by ε / b. Since it is difficult to create a complete hash table in terms of time and memory capacity, the image processing apparatus 10 uses a random method, that is, a subset Q ′ of the model Q. Therefore, the image processing apparatus 10 checks whether or not S matches Q ′ well by using a hash table.
If S matches well against Q ', then check all pairs. If S does not match well with Q ′, the image processing apparatus 10 may lose the correct conversion, but the probability is “Sandy Irani and Prab”.
hakarRaghavan, Combinatorial and experimental resu
lts for randomized point matching algorithms, In P
roc. 12th Annual ACM Symposium on Computational Ge
ometry, pages 68-77, 1996 ".

[0371]

[Equation 75]

As described above, the image processing apparatus 10
By performing pattern matching of sample data, scene analysis of an arbitrary image can be efficiently performed. Such an image processing apparatus 10 can be applied not only to scene analysis but also to object identification, image synthesis, data compression, and the like, and can be applied to, for example, mosaic formation.

The present invention is not limited to the above-described embodiment. For example, even when scene analysis of a plurality of image data is performed, by performing the above-described processing, the scene analysis can be efficiently performed. Can be performed.

As described above, it goes without saying that the present invention can be appropriately changed without departing from the spirit of the present invention.

[0375]

As described in detail above, the image processing method according to the present invention provides a feature extraction step of extracting feature points for each of two or more images, and one of the two or more images. A matching step of comparing feature points of the image and another image to perform matching, and a scene analysis step of performing a scene analysis of one image based on a result of the matching step.

Therefore, the image processing method according to the present invention extracts feature points for each of two or more images, and compares feature points between one image and another image among the two or more images. By performing matching and performing scene analysis of one image based on the result of this matching,
For example, scene analysis can be efficiently performed using a general-purpose computer.

The image processing apparatus according to the present invention
A feature extraction unit for extracting feature points for each of the above images, a matching unit for comparing and matching feature points of one image and another image among two or more images, and a matching unit A scene analysis unit that performs a scene analysis of one image based on a result of the matching.

Therefore, the image processing apparatus according to the present invention extracts the feature points of each of the two or more images by the feature extraction means, and extracts the feature points by the matching means.
Of the above images, matching is performed by comparing feature points between one image and another image, and a scene analysis unit performs a scene analysis of one image based on a result of the matching, for example, a general-purpose image. Scene analysis can be efficiently performed by using the computer of (1).

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating a configuration of an image processing apparatus shown as an embodiment of the present invention.

FIG. 2 is a diagram illustrating an example of image data.

FIG. 3 is a diagram illustrating another example of image data.

FIGS. 4A and 4B are diagrams illustrating an overlapping portion, wherein FIG.
FIG. 3B is a diagram illustrating two pieces of image data obtained by imaging a point in a three-dimensional space and projecting the two-dimensional image on a two-dimensional image;
FIG. 6 is a diagram illustrating a state in which image data of sheets are overlapped.

FIG. 5 is a diagram for explaining changing a method of performing a matching process according to an overlap rate.

FIG. 6 is a diagram illustrating an example of an algorithm of the Monte Carlo method applied when performing a matching process in consideration of using characteristics of feature points.

FIG. 7 is a diagram illustrating a matching process performed by a process execution unit.

FIG. 8 is a diagram illustrating an example of a geometric filtering algorithm.

9 is a diagram illustrating an example of an algorithm for performing a matching process by randomly combining with the geometric filtering algorithm illustrated in FIG. 8;

FIG. 10 is a flowchart illustrating a series of processing when pattern matching of sample data is performed and scene analysis of an image is performed in the image processing apparatus.

FIG. 11 is a diagram illustrating a method of geometric pattern matching in the image processing apparatus.

FIG. 12 is a diagram showing an example of isometric conversion, showing transition, rotation, and mirroring for a certain pattern;

FIG. 13 is a diagram showing an example of a paired rotational symmetry,
(A) is a diagram showing a congruent example in which a certain pattern is rotated and a disjoint example in which an outlier exists,
(B) shows transition, transition and rotation for a certain pattern,
It is a figure which shows the example of the joint which is a mirror image.

14A and 14B are diagrams illustrating a point set and a point set including noise, wherein FIG. 14A is a diagram illustrating a case where the minimum distance between points of the point set is smaller than the radius of the sphere, and FIG. FIG. 4 is a diagram showing a case where the minimum distance between points of a point set is larger than the radius of a sphere.

FIG. 15 is a flowchart illustrating a series of processing when detecting whether or not two point sets are congruent in the image processing apparatus, and illustrates a first half of the processing;

FIG. 16 is a flowchart illustrating a series of processing when detecting whether or not two point sets are congruent in the image processing apparatus, and is a diagram illustrating processing in a latter half part.

FIG. 17 is a diagram illustrating an example of two congruent point sets, where (A) is a diagram illustrating two point sets having only a single point on a circle having the same radius; (B) is a diagram showing two point sets having a plurality of points on a circle having the same radius.

FIG. 18 is a flowchart illustrating a series of processing when detecting the symmetry of a two-dimensional point set in the image processing apparatus.

FIG. 19 is a flowchart illustrating a series of processing when detecting the symmetry of a d-dimensional point set in the image processing apparatus.

FIG. 20 is a diagram illustrating an example of a point set having similarity.

21A and 21B are diagrams for explaining a subset congruence problem, wherein FIG. 21A is a diagram showing a certain point set, and FIG.
FIG. 3 is a diagram illustrating a point set indicating a certain scene including a copy of the point set illustrated in FIG.

FIG. 22 is a flowchart illustrating a series of processing when detecting partial congruence when two sets are flat and zoom is not permitted in the image processing apparatus.

FIG. 23 is a flowchart illustrating a series of processing when detecting partial congruence when two sets are d-dimensional in the image processing apparatus.

FIG. 24 is a diagram illustrating an example of a boolean bucket.

FIG. 25 is a diagram showing an example of an annular inquiry;
(A) is a figure which shows the bucket of an annular inquiry,
(B) is a figure which shows the bucket of a sector-shaped inquiry.

FIG. 26 is a flowchart illustrating a series of processing when performing pattern matching including transfer and / or rotation in the image processing apparatus.

FIG. 27 is a flowchart illustrating a series of processing when performing pattern matching including transfer and / or rotation on a large point set density in the image processing apparatus.

FIG. 28 is a flowchart illustrating a series of processing when estimating a parameter γ in the image processing apparatus.

29A and 29B are diagrams illustrating an example of partial congruence when scaling is performed, where FIG. 29A is a diagram illustrating a certain set, and FIG. 29B is a diagram illustrating a subset and a size of the set illustrated in FIG. FIG. 9 is a diagram illustrating a set including partial congruences having different sets.

FIG. 30 is a flowchart illustrating a series of processing when detecting partial congruence in the image processing apparatus.

FIG. 31 is a flowchart illustrating a series of processes performed when detecting partial congruence in the image processing apparatus;
It is a figure explaining a series of processes improved using the iterative method.

FIG. 32 is a diagram for describing an example of an inquiry to another set by a triangle of a certain set.

FIG. 33 is a diagram illustrating an example of a maximum common point set, illustrating a maximum common point set and a next largest common point set.

FIG. 34 is a flowchart illustrating a series of processes in each stage when solving a decision problem in the image processing apparatus.

[Explanation of symbols]

10 image processing device, 11, 12 feature extraction unit, 1
3 processing execution unit, 14 evaluation unit, 20 data input unit, 30 display unit

Claims (12)

[Claims] A feature extraction step of extracting feature points of each of two or more images; and a matching step of comparing feature points of one image and another image among the two or more images to perform matching. An image processing method, comprising: a step of performing a scene analysis of the one image based on a result of the matching step. 2. The image processing method according to claim 1, wherein Hausdorff matching is performed in the matching step. 3. The image processing method according to claim 1, wherein in the matching step, bottleneck matching is performed. 4. In the matching step, a first set indicating a feature point group including all feature points of sample data as an arbitrary object included in the one image, 2. The image processing method according to claim 1, wherein pattern matching is performed with a second set indicating a feature point group including the feature points. 5. The method according to claim 1, wherein the matching step includes: an orthogonal boundary area calculating step of calculating an orthogonal boundary area of the first set, which is a two-dimensional point set; A Boolean bucket creating step of creating a binary Boolean bucket of the following; and marking the binary Boolean bucket with respect to a distance between a pair of two different feature points in the first set, A point-to-point distance list creating step of creating a point-to-point distance list for each binary Boolean bucket; a set selecting step of randomly selecting the first set pair; and a two-dimensional point set A pair selecting step of selecting all pairs of two feature points satisfying a predetermined condition from the second set; and a binary Boolean bar created in the Boolean bucket creating step. A transition detection step of obtaining all transitions of the second set by using a set of transforms defined by feature points constituting pairs selected in the pair selection step; and a set of common transitions And a discriminating step of checking whether or not the common transition calculated in the common transition set calculating step induces an event. The first set and the second set 5. The image processing method according to claim 4, wherein pattern matching including transfer and / or rotation with a set is performed. 6. The matching step includes: an orthogonal boundary area calculating step of calculating an orthogonal boundary area of the first set; a bucket creating step of creating a bucket of a predetermined size on the second set; A set selecting step of randomly selecting a pair of the first set, and a pair of selecting all pairs of two feature points satisfying a predetermined condition from the second set by using a bucketing method. Using the bucket created in the bucket creation step and the set of transformations defined by the feature points forming the pair selected in the pair selection step, all of the second set A transition detection step for calculating a transition of the common transition set; a common transition set calculation step of calculating a set of common transitions; and a discrimination step of checking whether or not the common transition calculated in the common transition set calculation step induces an event. Have The image processing method according to claim 4, wherein the performing pattern matching between the serial first set and the second set. 7. A feature extracting means for extracting feature points for each of two or more images, and matching for comparing and matching feature points of one image and another image among the two or more images. An image processing apparatus comprising: means; and scene analysis means for performing scene analysis of the one image based on a result of matching by the matching means. 8. An image processing apparatus according to claim 7, wherein said matching means performs Hausdorff matching. 9. The image processing apparatus according to claim 7, wherein said matching means performs bottleneck matching. 10. The image processing apparatus according to claim 1, wherein the matching unit includes: a first set indicating a feature point group including all feature points for sample data as an arbitrary object included in the one image; 8. The image processing apparatus according to claim 7, wherein pattern matching is performed with a second set indicating a feature point group including the feature points. 11. The matching means calculates an orthogonal boundary region of the first set, which is a two-dimensional point set, and calculates a one-dimensional binary Boolean bucket used for bucketing a distance between points. Creating and marking the binary boolean bucket with respect to the distance between pairs of two different feature points in the first set,
For each binary boolean bucket, create a list of point-to-point distances, randomly select the first set of pairs,
From the second set which is a dimensional point set, all pairs of two feature points satisfying a predetermined condition are selected, and the created binary Boolean bucket and the feature points forming the selected pair are selected. By determining all the transitions of the second set using the set of transformations defined by, calculating the set of common transitions, and checking whether the calculated common transitions trigger an event, The image processing apparatus according to claim 10, wherein pattern matching including transition and / or rotation between the first set and the second set is performed. 12. The matching means calculates an orthogonal boundary region of the first set, creates a bucket of a predetermined size on the second set, and randomly creates a pair of the first set. Selecting, using the bucketing method, selecting all pairs of two feature points satisfying a predetermined condition from the second set, and creating the bucket and the feature constituting the selected pair. Using the set of transformations defined by the points, find all the transitions in the second set, calculate the set of common transitions, and check whether the calculated common transitions trigger an event. , The first set and the second set
11. The image processing apparatus according to claim 10, wherein pattern matching is performed with a set of.