JPH11110542A - Method and device for extracting pattern and medium recorded with program therefor - Google Patents

Abstract

PROBLEM TO BE SOLVED: To easily extract a pattern despite deformation such as the parallel movement, rotation or slight distortion of a partial area by finding the degree of correspondence for each corresponding candidate point, while using a distance between the corresponding candidate point of any arbitrary feature point on a 1st pattern and the correspondent candidate point of the nearby feature point. SOLUTION: Feature points (i) are respectively arranged on a 1st pattern X and a 2nd pattern Y and the plural corresponding candidate points, to which it is possible for the feature point (i) on the 1st pattern X to be corresponded to, are found from among the feature points (i) arranged on that 2nd pattern Y. Then, the degree of correspondence for each corresponding candidate point is found, while using the distance between any arbitrary feature point (i) on the 1st pattern X and a nearby feature point (u) with that feature point (i) as a center and the distance between the corresponding candidate point of the feature point (i) and a corresponding candidate point K' of the nearby feature point (u). Thus, constant collation is also enabled with respect to parallel movement, rotation or distortion of the pattern.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a method for determining whether a model image or a model pattern exists in whole or in part in an input image or pattern such as an image recognition or pattern identification device. The present invention relates to a pattern extraction device, a pattern extraction method, and a recording medium on which a program is recorded, which is capable of judging a pattern and extracting an area when the pattern exists.

[0002]

2. Description of the Related Art Conventionally, in the field of image recognition, a system for detecting a specific person's face from an image in which many people's faces are captured, a human face or a specific pattern included in an image, or the like. A system that detects a specific terrain pattern from a wide terrain map, or a system that monitors the environment or system status using images and issues a warning when a specific pattern appears. There has been proposed a pattern extraction method capable of determining whether or not a specific image or pattern serving as a model or a part thereof is present in a pattern, and extracting the region when it exists.

As one of such pattern extraction methods, template matching is performed by using a specific pattern to be extracted as a template, obtaining a correlation while moving the pattern on an image or pattern to be extracted, and detecting a location having a large correlation. There is a technique called. However, in this case, when it is desired to detect a portion that matches or partially matches a pattern obtained by geometrically deforming (for example, rotating or scaling) a specific pattern from target images or patterns, It is necessary to prepare many templates according to the deformation pattern to be detected, and the calculation time becomes enormous.

On the other hand, dynamic link matching (WKKonenetal. "A Fast Dynamic Link Matching Algo
rithm for Invariant Pattern Recognition ", Neural
Networks, Vol. 7, pp. 1019-1030, 1994) is one of the recognition methods using dynamic features of a neural network. Since this method does not use a template, it has a strong advantage against deformation such as parallel movement, rotation, and distortion of the model pattern. However, since all feature points between two patterns are virtually connected by a connection called a dynamic link, the number of feature points increases when the area of an image or a pattern is increased, and the number of links increases accordingly. There is a problem that the number of calculations increases as a result, and the amount of calculation required for matching also becomes enormous. In addition, when a model image is included in a part of a target pattern, a secondary extraction method using information such as dynamic link strength is required to specify where the region is located. Becomes

[0005]

SUMMARY OF THE INVENTION The present invention has been proposed to solve the above-mentioned problems of the conventional pattern extraction technology. The translation, rotation,
It is an object to easily detect regardless of deformation such as slight distortion or the number of existing regions.

[0006] Another object of the present invention is to provide a feature amount between two patterns based on a plurality of feature points arranged on two patterns and feature amounts obtained from local pattern information of each feature point. An object of the present invention is to reduce the amount of calculation and to extract similar patterns at a high speed by comparing the similarity and the like.

[0007]

According to the first aspect of the present invention, there is provided the following:
In the pattern extracting method, it is determined whether or not the pattern X of the first pattern exists in the second pattern, and when the pattern X exists, an area corresponding to the first pattern is extracted from the second pattern. Feature points are arranged on the pattern X and the second pattern Y, respectively, and a plurality of feature points on the first pattern X that may correspond to the feature points from the feature points arranged on the second pattern Y are described. A corresponding candidate point k is obtained, and a distance between an arbitrary feature point i on the first pattern X and a nearby feature point u centered on the feature point i, a correspondence candidate point k of the feature point i and the nearby feature point u are calculated. It is characterized in that the degree of correspondence of each corresponding candidate point k is obtained using the distance between the corresponding candidate points k ′.

According to a second aspect of the present invention, in obtaining the corresponding candidate point k, for each feature point on the first pattern X and the second pattern Y, a feature amount is extracted from information around the feature point, The similarity is determined by comparing the feature amounts of the first pattern X and the second pattern Y, and the correspondence is obtained from the similarity and the distance.

A tenth aspect of the present invention captures the first and second aspects of the present invention from the viewpoint of an apparatus. That is, the invention according to claim 10 determines whether or not the first pattern X exists in the second pattern, and when it exists, the area corresponding to the first pattern is determined from the second pattern. In a pattern extraction device to be extracted, a feature point setting unit for arranging feature points on the first pattern X and the second pattern Y, and a pattern around each feature point arranged by the feature point setting unit A feature amount extraction unit that extracts a feature amount from the information; and a feature point of the first pattern X and a feature point of the second pattern Y by comparing the feature amounts of the first pattern X and the second pattern Y. And a first pattern X based on the similarity between the feature points.
A corresponding candidate point calculating unit for obtaining a plurality of corresponding candidate points k on the second pattern Y to which the above feature points may correspond, the similarity, and an arbitrary feature point i on the first pattern X And the distance between the corresponding candidate point k of the feature point i and the corresponding candidate point k ′ of the nearby feature point u of the feature point i, using It is characterized in that it has a correspondence determination unit that repeatedly calculates the correspondence of the candidate point k, and a corresponding point extraction unit that extracts the correspondence candidate point k having a high correspondence.

[0010] Claims 1, 2, 1 having such a configuration.
In the invention of No. 0, each feature point i on the first pattern X is compared with each feature point i on the second pattern Y based on the similarity between the feature points on the first pattern X and the feature points on the second pattern Y. A plurality of corresponding candidate points k are selected from the feature points j. Next, based on the similarity, the distance between neighboring feature points u on the first pattern X, and the distance of each corresponding candidate point k, k ′ on the second pattern Y,
The degree of correspondence of the corresponding candidate point k is obtained by repeated calculation, and a corresponding candidate point k having a high degree of correspondence is extracted. That is, if a certain corresponding candidate point k on the second pattern Y really corresponds to the feature point i on the first pattern X, the second pattern of the neighboring feature point u of the feature point i The corresponding candidate point k ′ on Y also exists near the corresponding candidate point k of the feature point i. Therefore, the distance between the feature point i on the first pattern X and its neighboring feature point u, the corresponding candidate point k of the feature point i on the second pattern Y and the corresponding candidate point k ′ of the nearby feature point u are By comparing with the distance of
And the degree of correspondence with the corresponding candidate point k can be determined easily and quickly.

Further, in the present invention, the above-mentioned processing of comparing the degree of matching of the distances is performed on a plurality of neighboring feature points u present around a certain feature point i, and the calculation results for each neighboring feature point u are integrated. Thus, the degree of correspondence of the corresponding candidate point k corresponding to the feature point i is determined. The degree of correspondence obtained in this way is supported by the plurality of nearby feature points u, and the accuracy is high. Further, the same calculation is performed for each feature point i on the first pattern X to determine which partial region of the second pattern Y corresponds to the whole or a part of the first pattern X, Can be determined to what extent.

According to a third aspect of the present invention, a feature point having a similarity not less than a predetermined predetermined number and a similarity greater than or equal to a predetermined similarity threshold is determined when finding the corresponding candidate point k. k, when one of the above two conditions is satisfied first, the corresponding candidate point k of the feature point i
Is a condition that no further increase is made, or one of the conditions can be selected. According to an eleventh aspect of the invention, the invention of the third aspect is captured from the viewpoint of an apparatus. That is, claim 1
In the invention of the first aspect, the correspondence candidate point calculation unit may arrange, for an arbitrary feature point i on the first pattern X, feature points j on the second pattern Y having a large similarity to the point in descending order. When the corresponding candidate point k is set, a condition that the upper limit number of candidate points does not exceed a predetermined number, a condition that a feature point having a similarity equal to or more than a predetermined similarity threshold is set as a corresponding candidate point k, It is characterized in that when any one of the two conditions is satisfied first, any one of the conditions that the corresponding candidate point k of the feature point i does not increase any more can be selected.

According to the third and eleventh aspects of the present invention, when selecting the corresponding candidate points k on the second pattern, the number of the corresponding candidate points k is limited according to a predetermined condition. Therefore, the number of corresponding candidate points k to be compared does not increase without limit, and the processing speed can be improved by limiting the number of subsequent calculations. In particular, by limiting the number of corresponding candidate points k using the similarity between a feature point and its corresponding candidate point k as a threshold, corresponding candidate points k with low similarity can be eliminated, and high extraction accuracy and processing speed can be achieved. Can be secured.

According to a fourth aspect of the present invention, in determining the degree of correspondence of the corresponding candidate point k, an initial value of the degree of correspondence of each of the corresponding candidate points k is determined, and each feature point on the first pattern X and its corresponding point are determined. The distance between neighboring feature points and the second between each corresponding candidate point
Of the first pattern X
Between the feature points in the pattern and the corresponding candidate point k in the second pattern Y
Calculating the degree of coincidence between the distances, calculating the weighted sum of the degrees of correspondence for each of the corresponding candidate points k of the feature points on the first pattern X, and finding the fitness for each of the corresponding candidate points k It is characterized by.

According to the fourth aspect of the present invention having the above configuration, the correspondence between the correspondence candidate point k of a certain feature point i and the correspondence candidate point k ′ of a neighboring feature point u located around the feature point i is determined. The degree is calculated, and the degree of correspondence between the neighboring feature point u and the corresponding candidate point k ′ is obtained in consideration of the degree of the matching of the distances. In this case, when there are a plurality of corresponding candidate points k ′ for the neighboring feature point u, the degree of matching of the distance is calculated for each corresponding candidate point k ′, and each corresponding candidate The degree of correspondence of the point k 'is obtained, and then the degree of correspondence of each of the corresponding candidate points k' is totaled. Then, this processing is performed on a plurality of neighboring feature points u located around the feature point i, and the degree of correspondence in consideration of the degree of matching of the distance obtained for the corresponding candidate point k ′ of each neighboring feature point u ( If there are a plurality of corresponding candidate points k ′, the totalized corresponding degrees) are further totalized to obtain the matching degree of the corresponding candidate points k. In this way, for a feature point i, all its corresponding candidate points k
Is obtained for all the feature points i, and the fitness for all the feature points i is obtained. The goodness of fit obtained in this way is calculated for each feature point i
And the corresponding degree of the corresponding candidate point k are supported by the distance between the surrounding plurality of neighboring feature points u and the corresponding candidate point k ′, and are determined by the feature point i and the corresponding candidate point k. A more reliable correspondence can be obtained as compared to a correspondence or similarity, or a correspondence determined in consideration of only the distance between a feature point i and a single neighboring feature point u around the feature point i. .

According to a fifth aspect of the present invention, when determining the degree of correspondence of the correspondence candidate point k, the characteristic point i on the first pattern X is determined.
On the second pattern Y indicated by the corresponding candidate point k,
When the position on the second pattern Y indicated by the corresponding candidate point k ′ of the neighboring feature point u of the feature point i is equal, the degree of matching of the corresponding candidate point k ′ of the neighboring feature point u is suppressed. . According to the fifth aspect of the present invention having such a configuration, when the matching degrees are obtained for all the feature points i and the corresponding candidate points k of the respective feature points i are determined according to the matching degrees, the corresponding candidate points of the certain feature point i are determined. It relates to the processing when k and the corresponding candidate point k ′ of the neighboring feature point u match. That is, in reality, the first
Since a certain feature point i on the pattern X and its neighboring feature point u do not match, their corresponding candidate points k and k ′ on the second pattern Y also cannot match. Therefore, in the present invention, in such a situation, the corresponding candidate points k and k ′ are suppressed by suppressing the degree of matching of the neighboring feature points u.
Avoid matches.

According to a sixth aspect of the present invention, in obtaining the degree of correspondence of the corresponding candidate point k, the value of the degree of correspondence of each corresponding candidate point k is updated in accordance with the degree of matching, and the amount of change in the degree of correspondence is reduced. In the case of being equal to or greater than a predetermined threshold, the calculation of the degree of matching, the suppression of the degree of matching of the neighboring feature points, and the updating of the degree of correspondence are repeatedly performed, and the updating of the degree of correspondence is terminated when the degree of matching is smaller than the threshold. I do. In the invention according to claim 6 having such a configuration, each feature point i is given to each feature point i on the basis of the degree of matching between each corresponding candidate point k obtained for each feature point i as described above. Update the degree of correspondence that was being used. in this case,
If the update is advanced to some extent, the amount of change in the degree of correspondence due to the update is reduced, and even if the update is further advanced, the extraction accuracy is not improved. Therefore, by determining the threshold value in advance, the update process is terminated within an effective range,
Performs arithmetic processing efficiently.

According to a twelfth aspect of the present invention, there is provided the fourth aspect of the present invention.
6 is a view of the invention of No. 6 from the viewpoint of an apparatus. That is,
The invention according to claim 12, wherein the degree-of-correspondence determining unit determines an initial value of the degree of correspondence of each corresponding candidate point k, each feature point i on the first pattern X and its neighboring features. The distance between the points u and the distance between the corresponding candidate points k and k ′ on the second pattern Y are obtained, and the distance between the feature points in the first pattern X and the distance between the feature points in the second pattern Y are calculated. Is calculated for each corresponding candidate point k of the feature points on the first pattern X, and the weighted sum of the corresponding degrees is calculated. A fitness calculating unit for determining the degree, the position on the second pattern Y indicated by the corresponding candidate point k of the feature point i on the first pattern X, and the corresponding candidate point k of the nearby feature point u of the feature point i When the positions on the second pattern Y indicated by 'are the same, the neighboring feature points u are determined according to the fitness of the corresponding candidate point k of the feature point i. A neighborhood matching suppression unit that suppresses the matching degree of the corresponding candidate point k ′, a correspondingness updating unit that updates the value of the correspondingness degree of each corresponding candidate point k according to the degree of the matching degree, and a change amount of the correspondingness degree Is greater than or equal to a predetermined threshold, the relevance calculation unit, the neighborhood relevance suppressing unit and the processing by the correspondence renewal unit are repeated, and a convergence determination unit that ends the renewal of the relevance when the value is smaller than the threshold. It is characterized by having. According to the twelfth aspect of the present invention having such a configuration, it is possible to realize a pattern extracting apparatus that sequentially executes the pattern extracting method according to the fourth, fifth, and sixth aspects.

According to a seventh aspect of the present invention, when determining the degree of correspondence of the correspondence candidate point k, a characteristic point i on the first pattern X is determined.
The corresponding candidate point k having the highest degree of relevance in is determined in advance,
When the same point is included in the corresponding candidate point k ′ of the nearby feature point u of the feature point i, the matching degree of the corresponding candidate point k ′ of the nearby feature point u is suppressed. Claim 1
A third aspect of the present invention captures the seventh aspect of the present invention from the viewpoint of an apparatus. In other words, in the invention of claim 13, the neighborhood matching degree suppression unit obtains the corresponding candidate point k having the highest matching degree at the feature point i on the first pattern X, and the same point as the feature point i is determined. When included in the corresponding candidate point k ′ of the nearby feature point u, the degree of matching of the corresponding candidate point k ′ of the nearby feature point u is suppressed by a predetermined value.

According to the seventh and thirteenth aspects of the present invention having the above configuration, the characteristic point i
If the corresponding candidate point k having the highest matching degree among the plurality of corresponding candidate points k and the neighboring feature point u of the feature point i and the corresponding candidate point k ′ match, The matching degree between the feature point u and the corresponding candidate point k ′ is suppressed. Further, when a candidate point k having a low degree of matching among a plurality of candidate points k of the feature point i, a nearby feature point u of the feature point i and the corresponding candidate point k ′ match. Does not suppress the degree of matching between the neighboring feature point u and the corresponding candidate point k ′. In this manner, the corresponding candidate point k having a low degree of matching does not suppress the degree of matching between the neighboring feature point u having a higher degree of matching and the corresponding candidate point k ′.

According to an eighth aspect of the present invention, when determining the degree of correspondence of the correspondence candidate point k, the characteristic point i on the first pattern X is determined.
The correspondence degree is updated by a predetermined amount for the corresponding candidate point k having the highest degree of conformity. Claim 14
The present invention is an embodiment in which the invention of claim 8 is grasped from the viewpoint of an apparatus. That is, the invention of claim 14 is that the correspondence updating unit updates the correspondence by a predetermined amount for the correspondence candidate point k having the highest fitness at the feature point i on the first pattern X. Features. According to the invention of claims 8 and 14 having such a configuration, the update processing is not performed for all the corresponding candidate points k, and the feature point i
Is performed only for the corresponding candidate point k having the highest matching degree. That is, since the update processing is performed only on the corresponding candidate point k that is most likely to be extracted, the arithmetic processing is simplified, and the degree of correspondence of the candidate points that are likely to be corresponded is further emphasized. Can be differentiated from the corresponding candidate point k.

According to a ninth aspect of the present invention, when the correspondence is initialized and the correspondence is updated, a process for normalizing the correspondence to be within a certain range is added. According to a fifteenth aspect of the present invention, the invention of the ninth aspect is captured from the viewpoint of an apparatus. That is, claim 15
In the invention, the correspondence degree initialization unit and the correspondence degree update unit include:
It is characterized by adding a process for normalizing so that an arbitrary degree of correspondence falls within a certain range. According to the ninth and fifteenth aspects of the present invention, for example, when initializing the degree of correspondence of a certain feature point i, the similarity of the feature point i is divided by the sum of the similarities of the feature points i. In the case of the use or the standardization at the time of updating, the maximum limit value and the minimum limit value of the degree of correspondence are determined in advance, and the updated degree of correspondence falls within this range. In this way, the bias of the initial value and the update value of the degree of correspondence is eliminated, and the subsequent arithmetic processing is also facilitated.

The inventions of claims 16 and 17 relate to a recording medium on which a program for realizing the invention of claims 1 and 10 is recorded. According to the invention of claims 16 and 17 having such a configuration, the pattern extraction method and apparatus of the present invention can be widely provided using a recording medium.

[0024]

DESCRIPTION OF THE PREFERRED EMBODIMENTS Embodiments of the present invention will be specifically described with reference to the drawings. Each function of the embodiment described below is realized by predetermined software controlling a computer and peripheral devices. In this specification, “... means corresponding to each function and each process” The invention and the embodiments have been described assuming a virtual circuit block such as "." Therefore, for each block, each hardware element or software element that realizes this does not correspond one-to-one.

(1) Configuration of Embodiment (1-1) Overall Configuration of Pattern Extraction Apparatus FIG. 1 The pattern extraction apparatus 1 of this embodiment is typically realized as a computer program. So,
The program is recorded on a storage medium such as a hard disk or a CD-ROM, and loaded and executed on a memory of a computer as needed. A computer that executes the pattern extracting apparatus 1 includes an input unit 2 including a keyboard, a mouse, a storage device, or a data reading unit from a network, for inputting data to the apparatus. , A printer, and other output means 3 are provided.

The pattern extracting apparatus 1 of the present embodiment determines whether or not the first pattern X exists in the second pattern Y. A region corresponding to the pattern X is extracted. As shown in FIG. 1, the region includes the following units.

(1) First pattern X and second pattern Y
A feature point setting unit 10 for arranging feature points on each of them; (2) A feature amount extraction unit 20 that extracts a feature amount from pattern information around each feature point arranged by the feature point setting unit 10. (3) A similarity calculation unit that calculates the similarity between the feature points of the first pattern X and the feature points of the second pattern Y by comparing the feature amounts of the first pattern X and the second pattern Y, respectively. 30.

(4) Corresponding candidate point calculation for obtaining a plurality of corresponding candidate points k on the second pattern Y which may correspond to the feature points on the first pattern X based on the similarity between the characteristic points. Part 40. (5) The similarity, the distance between an arbitrary feature point i on the first pattern X and a nearby feature point u centered on the feature point i, the corresponding candidate point k of the feature point i, and the vicinity of the feature point i Feature point u
And a distance between the corresponding candidate points k ′, the corresponding degree determining unit 5 that repeatedly calculates the degree of correspondence of each corresponding candidate point
0. (6) A corresponding point extracting unit 60 for extracting a corresponding candidate point k having a high degree of correspondence.

(1-2) Correspondence Determining Unit 50 FIG. 2 As shown in FIG. 2, the correspondence degree deciding unit 50 is composed of the following parts. (7) A correspondence initializing unit 51 that determines an initial value of the correspondence of each corresponding candidate point k. (8) The distance between each feature point i on the first pattern X and its neighboring feature point u and the distance on the second pattern Y between the corresponding candidate points k and k ′ are obtained, The degree of coincidence between the distance between the feature points i and u in the first pattern X and the distance between the corresponding candidate points k and k ′ in the second pattern Y is calculated. A fitness calculating unit 52 that calculates a weighted sum of the degrees of correspondence for each of the corresponding candidate points k of the feature points and obtains a degree of fitness for each of the corresponding candidate points k. (9) The position on the second pattern Y indicated by the corresponding candidate point k of the feature point i on the first pattern X and the second position indicated by the corresponding candidate point k ′ of the neighboring feature point u of the feature point i When the positions on the pattern Y are equal to each other, the neighborhood suitability that suppresses the fitness of the corresponding candidate point k ′ of the neighboring feature point u by a predetermined amount or an amount corresponding to the fitness of the corresponding candidate point k of the feature point i. Suppressor 53. (10) The correspondence updating unit 54 that updates the value of the correspondence of each corresponding candidate point k according to the magnitude of the matching. (11) When the amount of change in the degree of correspondence is equal to or greater than a predetermined threshold, the degree-of-fit calculating section 52 and the neighborhood-degree matching suppressing section 53
And a convergence determining unit 55 that repeats the processing by the correspondence degree updating unit 54 and ends the update of the correspondence degree when the value becomes smaller than the threshold value.

(2) Operation of Pattern Extraction Device The operation of the pattern extraction device 1 according to the present embodiment will be described below. (2-1) Input of Pattern In extracting the first pattern X from the second pattern by the pattern extraction device 1 of the present embodiment, first, the input unit 2 is used to search for a search pattern. A certain first pattern X and a second pattern Y to be searched are input. In this case, each pattern is input as image data composed of a large number of pixels, and each pixel holds various information according to the properties and functions of the image data. For example, the color, shading, brightness, transparency, normal vector, and the like of the pixel.

FIG. 3 shows an example of the input patterns X and Y. In this example, an elliptical feature is formed by using a mouse or the like from the entire first image G read from the storage means of the computer. A certain area including a target portion is designated, and this is set as a first pattern X. Of course, the first pattern X itself can be stored in a file in advance without specifying an area at the time of input, and the first pattern X can be directly input by specifying the file name. On the other hand, from the whole image H prepared by directly reading from an image input device such as a video camera or by reading from a storage unit, the second pattern Y is used as a region for searching for the presence or absence of the first pattern X. specify. Also in this case, the whole read image H
Can be used as the second pattern Y. In the present embodiment, the first pattern X input as described above has an elliptical area P, and the second pattern Y has the area P
Includes a region Q having a shape rotated.

The operation of designating a partial area such as the first pattern X and the second pattern Y from the entire image G or H can be automatically performed by software of a computer. . For example, the entire image is divided into a plurality of regions according to a predetermined standard such as a coordinate system and a hue,
By assigning each divided area to the first pattern X and the second pattern Y, and performing the extraction process for each divided area in order, it is possible to detect a similar pattern from all the images.

(2-2) Setting of feature points i and j FIGS. 3 and 4 The pattern extraction device 1 of the present embodiment
Feature point setting unit 10 that sets a plurality of feature points for first pattern X and second pattern Y input from
It has. When the first pattern X and the second pattern Y are two-dimensional patterns such as images, as shown in FIG. 4, the feature point setting unit 10 has a density substantially smaller than the number of pixels and has a substantially equal interval from each other. Place feature points. For example, for the first pattern X, N feature points (i =
,..., N), and the second pattern Y is N
_Y feature points (j = 1,..., N _Y ) are arranged. At this time, the position vectors of the feature points i and j on each pattern are written as a (i) and b (j), respectively.

(2-3) Extraction of Feature Amount The feature extraction unit 20 is provided at the subsequent stage of the feature point setting unit 10. The feature amount extracting unit 20 extracts a feature amount having one or more elements based on local pattern information centered on each feature point, and holds the feature amount for each feature point.
For example, the feature amount of the feature point i on the first pattern X is J _X
(i) The feature amount of the feature point j on the second pattern Y is J
_{Let Y} (j). This feature amount is calculated using pixel information in the vicinity of each feature point. R _f is the radius of a circle indicating the vicinity range. As shown in FIG. 4, the feature amount may be calculated from a range that includes another feature point located nearby (hereinafter, referred to as a nearby feature point). There are various ways of giving specific feature amounts. For example, in the case of a grayscale image, a method of taking a histogram of grayscale values of pixels around a feature point, dividing the distribution into several sections, and using a vector having the count number in each section as an element as a feature amount (vector) is known. is there. Also,
A method of applying two-dimensional filter processing such as Gabor wavelet around each feature point and using the output as a feature amount,
Other methods can be employed.

(2-4) Calculation of Similarity A similarity calculation unit 30 is provided downstream of the feature amount extraction unit 20. The similarity calculating unit 30 calculates the similarity between the feature points of the first pattern X and the second pattern Y using the feature amounts of the feature points of the first pattern X and the second pattern Y as input. I do. Hereinafter, the similarity between the feature point i on the first pattern X and the feature point j on the second pattern Y is represented as T (i, j). For example, assuming that a coefficient vector obtained as a result of filtering by the Gabor wavelet is a feature amount, the similarity calculating unit 30 calculates the similarity T (i, j) between J _X (i) and J _Y (j).

(Equation 1) It is possible.

(2-5) Calculation of Corresponding Candidate Points k and k ′ In the subsequent stage of the similarity calculating section 30, a corresponding candidate point calculating section 4 is provided.
0 is provided. The corresponding candidate point calculating unit 40 calculates a corresponding candidate point k (k = 1,..., M (i)) for each feature point i based on the similarity obtained by the similarity calculating unit 30. I do. The corresponding candidate point k indicates a feature point on the second pattern Y that is likely to correspond to each feature point i on the first pattern X, and M (i) indicates the corresponding candidate point k of the feature point i. Indicates a number. At this time, the second of the k-th corresponding candidate point k of the feature point i
Is expressed as p (i; k) on the pattern Y,
(i; k) is equal to one of b (j). FIG.
Shows an example of a certain feature point i on the first pattern X and its corresponding candidate point k (k = 1,..., M (i)).
Thus, a plurality of corresponding candidate points k exist for each feature point i on the first pattern.

In this embodiment, the corresponding candidate point calculating section 40 has the following features. That is, the number of feature points N _Y following integers second pattern Y in more than a candidate point upper limit number N _C, the threshold value of similarity and T _theta. In the corresponding candidate point calculation unit 40, the similarity T (i,
In j), it is assumed that sorting in descending order based on the value of the similarity when i is fixed is performed. At this time, as the corresponding candidate point k of the feature point i, the feature point j on the second pattern Y having a large similarity is sequentially adopted. When any of the following conditions is satisfied, the corresponding candidate point of the feature point i is The process of setting k is stopped. The conditions are as follows: (a) The number of corresponding candidate points k of one feature point has reached N _C. (b) The similarity T (i, j) is equal to or _smaller than _Tθ . (c) The number of corresponding candidate points k of one feature point has reached NC, or the similarity T (i, j) is equal to or _smaller than _Tθ .

There are three types. In the present embodiment,
Although one of these three conditions is selected, only one of the three conditions may be used. According to this condition, in the example of FIG. 5, the similarity with the feature point i is high, and the threshold T
Corresponding candidate points k = 1, k = 2, k = 3 _{exceeding θ} are selected, and other corresponding candidate points are excluded from targets of the extraction processing.

(2-6) Determination of Correspondence In the subsequent stage of the correspondence candidate point calculator 40, the correspondence determiner 5
0 is provided. In the correspondence degree determination unit 50, the similarity and each feature point i on the first pattern X and its nearby feature point u (u∈Ω _i , where Ω _i is a set of nearby feature points of the feature point i) Based on the distance and the distance between the corresponding candidate points of the feature point i and the neighboring feature point u, the degree of correspondence w (i; k) of each corresponding candidate point k is repeatedly calculated. That is,
Although there are a plurality of corresponding candidate points k for the feature point i,
Whether any of these corresponding candidate points k is a true corresponding point cannot be determined simply by the similarity. Therefore, as shown in FIG. 6, the distance dx between the feature point i and the nearby feature point u, and the distance between each corresponding candidate point k of the feature point i and the corresponding candidate point k ′ of the nearby feature point u of the feature point i. By comparing dy, the closer the distance, the higher the degree of correspondence.

FIG. 7 shows, for each feature point i-1, i, i + 1, the position vector p of each corresponding candidate point k (k = 1,..., M (i)) obtained as described above. (i-1; k)
, P (i; k), p (i + 1; k) and their corresponding degrees w (i-1; k)
, W (i; k) and w (i + 1; k).
As is apparent from FIG. 7, a plurality of correspondence candidate points having different degrees of correspondence are associated with each feature point. The correspondence degree determination unit 50 is provided for obtaining the correspondence degree of each of the correspondence candidate points k.
1, a fitness calculation unit 52, a neighborhood fitness suppression unit 53, a correspondence update unit 54, and a convergence determination unit 55. Hereinafter, each of these units will be described.

(2-6-1) Initialization of Correspondence The correspondence initializing unit 51 calculates the correspondence w (i) of the correspondence candidate point k of the feature point i on the first pattern X based on the similarity. ; k). For example, when the k-th corresponding candidate point of the feature point i on the first pattern X is the feature point m (i; k) on the second pattern Y, the feature point i and the corresponding candidate point m (i; Using the similarity T (i, m (i; k)) with k), the initial value of the correspondence w (i; k) can be given as follows, for example.

[0042]

(Equation 2) further,

(Equation 3) The initial value of the degree of correspondence w (i; k) of the corresponding candidate point k thus obtained is the similarity T between the corresponding candidate point k and the feature point i.
Without using (i, m (i; k)) as it is, the correspondence w (i; k) obtained by substituting the similarity is used as the correspondence w (i; k) of each correspondence candidate point k. Of the total.

(2-6-2) Calculation of Fitness The fitness calculating unit 52 calculates the distance | a (i) − between the feature point i on the first pattern X and its neighboring feature point u (u∈i). a (u) |
And the distance | p (i; k) − on the second pattern Y between the corresponding candidate points k and k ′ of the feature point i and the neighboring feature point u.
p (u; k ') | is calculated, and this is calculated as the feature point i
For each corresponding candidate point k, the weighted sum of the corresponding degrees w (i; k) and w (u; k ') is calculated, and the fitness f (i; k)
Is calculated. This suitable degree is determined by the corresponding candidate point k of the feature point i.
Indicates how much is supported by the position and degree of correspondence of the corresponding candidate point k ′ of the surrounding nearby feature point u.

FIG. 8 schematically shows an example of the position on the second pattern Y of the corresponding candidate point of the feature point on the first pattern X. In the figure, p indicates the position p (i; k) of the corresponding candidate point k of the feature point i on the first pattern X, and p ′ (k)
And p ″ (k) indicate the position of the k-th corresponding candidate point of the two neighboring feature points of the feature point i. As can be seen from this figure, if the feature point i and the corresponding candidate point k actually correspond, the distance between the nearby feature point u of the feature point i, the corresponding candidate point k of the feature point i, and the nearby feature Corresponding candidate point k 'of point u
Should be equal. Therefore, the matching degree calculation unit 52 calculates the distance between the feature point i on the first pattern X and the nearby feature point u, the corresponding candidate point k of the feature point i on the second pattern Y, and the nearby feature point. By comparing the distance between u and the corresponding candidate point k ′, the degree of matching between the feature point i and the corresponding candidate point k is determined.

That is, the fitness calculating unit 52 first initializes the fitness f (i; k) of the corresponding candidate point k of the feature point i to zero, and then initializes all the neighboring feature points u of the feature point i. Is calculated as follows for the corresponding candidate point k ′.

[0046]

(Equation 4) Here, E (dX, dY) is a distance function indicating how similar the distance dX on the first pattern X is to the distance dY on the second pattern Y. Specifically, for example,

(Equation 5) here,

(Equation 6) It is. FIG. 9 shows | dY−dX | and E (dX,
dY).

FIG. 10 is a flow chart of the above equation 4, and each step will be described below. (Step 110) One corresponding candidate point k having a feature point i
And initialize its fitness to zero. (Step 120) One of the neighboring feature points u of the feature point i is selected as a first neighboring feature point u, and one of the corresponding candidate points k ′ is selected as a first corresponding candidate point k ′. (Step 130) The feature point i and the first neighboring feature point u
, And the degree of similarity between the distance between the corresponding candidate point k and the first corresponding candidate point k ′ is calculated using the distance function. The obtained value of the distance function is multiplied by the degree of correspondence between the neighboring feature point u and the first corresponding candidate point k ′, and the value is added to the fitness of the initialized feature point i and the corresponding candidate point k. .

(Step 140) After a new degree of conformity is obtained, the process returns to step 120 according to step 140, selects a second corresponding candidate point k 'of the first neighboring feature point u, and executes step 130. repeat. When this processing is performed for all the corresponding candidate points k ′ of the first neighboring feature point u, the correspondence taking into account the distance function values of all the corresponding candidate points k ′ of the first neighboring feature point u of the feature point i is taken into account. The degree is added as the matching degree of the corresponding candidate point k. Further, the processing of steps 120 and 130 is performed not only for the first neighboring feature point u, but also for all neighboring feature points u around the feature point i.

(Step 150) A value obtained by multiplying the degree of matching obtained as a result of step 140 by the degree of matching of the corresponding candidate point k of the feature point i is defined as a new degree of matching between the feature point i and the corresponding candidate point k. substitute. (Step 160) By executing the processing of the steps 110 to 150 for all the corresponding candidate points k of the feature point i, it is possible to obtain the degree of conformity of all the corresponding candidate points k of the feature point i. This goodness-of-fit is determined by the feature point i
In addition to the similarity between the feature point i and each corresponding candidate point k, the distance between the feature point i and the nearby feature point u and the distance between the corresponding candidate point k of the feature point i and the corresponding candidate point k ′ of the nearby feature point u The degree of similarity is added.

(2-6-3) Suppression of neighborhood suitability FIG. 11 The neighborhood suitability suppressing unit 53 sets p (u;) at the same position as p (i; k).
k ') with respect to the fitness f (i; k)
(u; k '). That is, in the real image, the feature point i
Since the corresponding candidate point k ′ of the neighboring feature point u does not match the corresponding candidate point k of the feature point i, the matching degree of the corresponding candidate point k ′ is reduced according to the following equation, for example.

[0051]

(Equation 7) Here, H (x) is a non-negative function.

In this embodiment, H (f (i; k)) is set as follows.

[0053]

(Equation 8) Here, argmaxl_f (i; l) means the value of l at which f (i; l) is maximized when i is fixed, and β is a positive number.

In the process of suppressing the degree of matching, the corresponding candidate point k having the highest degree of matching in the feature point i on the first pattern X is obtained, and H (f
(i; k)) is a value obtained by multiplying the degree of conformity between the feature point i and the corresponding candidate point k by a predetermined value β.
, H (f (i; k)) is set to 0. In this way, among the corresponding candidate points k ′ of the neighboring feature point u of the feature point i,
The matching degree of the feature point i that matches the corresponding candidate point k having the highest matching degree is suppressed, and the matching degree is not suppressed for the corresponding candidate points k ′ that match the other corresponding candidate points k. As a result, even if the corresponding candidate point k ′ of the neighboring feature point u of the feature point i matches the corresponding candidate point k of the feature point i, the matching candidate point k having a low possibility of matching actually matches. This eliminates the inconvenience of suppressing the degree of matching between the nearby feature point u that may be present and the corresponding candidate point k ′.

Hereinafter, the process of suppressing the degree of conformity of the nearby feature point u will be described with reference to each step of the flowchart shown in FIG. (Step 210) First, a corresponding candidate point k of a feature point on the first pattern X is selected. (Step 220) A nearby feature point u of the feature point i and a corresponding candidate point k ′ are selected. (Step 230) If the corresponding candidate point k of the feature point i is
The positions of the feature points i and the corresponding candidate points k ′ of the neighboring feature points u are compared, and if they match, the procedure proceeds to step 240, and if they are different, the procedure proceeds to step 250.

(Step 240) For a nearby feature point u having a corresponding candidate point k ′ that matches the corresponding candidate point k, the degree of conformity of the corresponding candidate point k ′ is suppressed according to the above equation (7). (Step 250) The same processing is repeated for all the corresponding candidate points k ′ of the neighboring feature point u of the feature point i. Furthermore,
The same processing is repeated for all the neighboring feature points u of the feature point i. (Step 260) The above steps are performed by using the first pattern X
The same process is repeated for all the corresponding candidate points k of the above feature point i, and thereafter, for all the feature points i on the first pattern X.

By suppressing the fitness as described above, the corresponding candidate point k and the corresponding candidate point k ′ of all the feature points i on the first pattern X and the neighboring feature points u are matched. Can be avoided. Also, the nearby feature point u
Includes a corresponding candidate point k ′ that matches the highest-matching corresponding candidate point k of the feature point i, the corresponding candidate point k ′ Since the degree of suppression is suppressed, the corresponding candidate point k having a high degree of matching can be made higher, and clear differentiation from other corresponding candidate points k having a low degree of matching can be performed.

(2-6-4) Updating of the degree of correspondence After the processing for suppressing the degree of conformity of the candidate point k ′ for the correspondence of the neighboring feature point u has been performed for all the feature points i as described above, The degree updating unit 54 updates the value of the degree of correspondence of each corresponding candidate point according to the magnitude of the obtained degree of matching.
As shown in the flowchart of FIG. 12, the corresponding candidate point k of the feature point i is selected,

(Equation 9) Then, the old correspondence is stored, and the correspondence is updated by the following equation.

[0059]

(Equation 10) Here, F (x) is a function for updating the correspondence w (i; k) according to the magnitude of the fitness f (i; k). In the present embodiment, F (f (i; k)) is set as follows. In the following equation, γ is a positive number.

[0060]

[Equation 11] As can be seen from Expression 11, in the present embodiment, as in the case of the suppression of the fitness, the matching candidate k having the greatest fitness at the feature point i on the first pattern X The degree of correspondence is updated by an amount corresponding to.

For all the feature points i, the above 10
After the correspondence is updated by the equation, the correspondence w (i; k) obtained for each feature point i is normalized for comparison.
For example, in the correspondence updating unit 54, as in the case of the normalization in the correspondence initializing unit 51, the correspondence updating unit 5
In step 4, after updating the degree of correspondence w (i; k) for all feature points i and corresponding candidate points k, the same processing as in the above equation 3 is performed. Alternatively, the maximum limit value W _max and the minimum limit value W _min of the degree of correspondence are determined in advance,

(Equation 12) There is also a method.

(2-6-5) Judgment of Convergence As described above, the degree of correspondence is updated for all the feature points i and the corresponding candidate points k. It is obtained by changing the degree of matching between the point i and the corresponding candidate point k in consideration of the degree of matching of the corresponding candidate point k ′ of the neighboring feature point u of each feature point i. Therefore, even if the degree of matching is determined for a certain feature point i, when determining the degree of matching of the corresponding candidate point k for the next feature point i, the already determined first feature point i and its corresponding candidate The fitness of point k may change. The reason is,
This is because the first feature point i is a neighboring feature point u when viewed from the next feature point i.

Therefore, each feature point i and its corresponding candidate point k obtained on the basis of the fitness that may change in this way
May have changed from the originally calculated value at the time when the calculation of the degree of correspondence has been completed for all the feature points i. If the amount of change is large, it is necessary to calculate again. Therefore, in the present embodiment, by repeating this updating operation several times, when the degree of correspondence between each feature point i and its corresponding candidate point k reaches a state where it does not change to a certain degree or more, each feature point i and its corresponding The final correspondence of the candidate point k is determined.

In order to perform this processing, the convergence determining unit 55 of the present embodiment calculates the change amounts of all the degrees of correspondence.
Then, the process returns to step S2. That is, the convergence determination unit 55
After updating all the degrees of correspondence in the degree-of-correspondence updating unit 54, the sum of changes between the old degree of correspondence and the new degree of correspondence is calculated as in the following equation:

(Equation 13) Updating of the degree of correspondence is repeated until Er becomes equal to or less than a predetermined value.

The processing of updating the degree of correspondence and determining the convergence in the degree-of-correspondence updating section 54 is executed according to the flowchart of FIG. (Step 310) A feature point i on the first pattern X and its corresponding candidate point k are selected. (Step 320) Convergence determination processing after (step 35)
The old correspondence degree w _old (i; k) is stored for use in 0). (Step 330) Using the function F (f (i; k)) for updating the degree of correspondence w (i; k) according to the magnitude of the degree of conformity f (i; k), the degree of correspondence w ( i; k) is updated.

(Step 340) The above processing is repeated for all the corresponding candidate points k of the feature point i on the first pattern X, and when this is completed, the above-mentioned processing is performed for all the corresponding candidate points k of the other feature point i. Is repeated. (Step 350) For each feature point i, after a new correspondence is obtained, the sum Er of the old correspondence saved in step 320 and the newly obtained correspondence is calculated, and this change Er is calculated. If the total sum Er becomes equal to or less than a certain value, the process proceeds to the next corresponding point extraction process. On the other hand, the sum of changes E
If r does not fall below the certain value, the process returns to step 110 shown in FIG. 10, and the relevance and the corresponding degree based on it are calculated again for all the feature points i. In this case, as shown in steps 120 and 150, when determining a new correspondence, the correspondence obtained according to the processing of FIGS. 10, 40, and 50 is used. The fitness of each feature point i with the corresponding candidate point k eventually converges to a certain range.

(2-7) Extraction of Corresponding Points As described above, after the degree of correspondence between each feature point i and the corresponding candidate point k converges to a constant value, only the corresponding candidate points having a high degree of correspondence are extracted. Then, it is displayed on the output means 3 such as a display. That is, the corresponding point extracting unit 60 extracts corresponding points on the pattern Y at each feature point on the pattern X by, for example, the following method. First, as a first method, among corresponding candidate points of each feature point on the pattern X,
If there is one whose correspondence exceeds a predetermined threshold, the feature point is displayed on the pattern X, and the one having the highest correspondence among the correspondence candidate points exceeding the threshold is displayed. The corresponding points of the feature points are displayed on the pattern Y. In the second method, all the corresponding candidate points exceeding the threshold value in the first method are displayed on the pattern Y as corresponding points. At the time of display, if the display brightness or the like is changed according to the value of the degree of correspondence, it is possible to display how strong the correspondence is.

(3) Effects of Embodiment In the present embodiment having the above configuration, corresponding candidate points k and k corresponding to a certain feature point i of the first pattern X and its nearby feature point u. Is corrected in consideration of the distance between the points, and the correspondence candidate points k and k ′ are corrected.
Can be extracted anywhere in the second pattern Y. Further, since it is not necessary that the distance between the feature point i and the neighboring feature point u and the distance between the corresponding candidate points k and k ′ completely match, not only the area that completely matches the first pattern X is used. That is, it is also possible to extract regions that are similar to some extent. Also, since the calculation of the degree of conformity and the degree of correspondence is performed only for a predetermined number of feature points i and a plurality of neighboring feature points u located around the feature points i without performing the comparison of the feature amounts for all the pixels, the calculation amount is small. And the extraction process can be executed at high speed.

(4) Other Embodiments The present invention is not limited to the above-described embodiment, but includes the number of feature points i on each pattern, and neighboring feature points selected from around the feature point i. The number of u can be freely set. In addition, the degree of correspondence between the feature point i and the corresponding candidate point k is determined based on the similarity. The method of determining the similarity is also appropriately selected according to the characteristics of the image data to be compared. it can. Furthermore, other methods can also be used to standardize the initial value of the degree of correspondence or the degree of correspondence to be updated.

[0070]

As described above, according to the present invention, the comparison between two patterns is performed based on the similarity of the feature amounts of local patterns possessed by a plurality of feature points arranged on the pattern. , A pattern extraction method and apparatus that enables invariant matching even with respect to translation, rotation, and distortion of a pattern, and also enables extraction of a partially coincident region, and a medium recording a program that realizes these. can do.

[Brief description of the drawings]

FIG. 1 is a block diagram showing an embodiment of a pattern extraction device according to the present invention.

FIG. 2 is a block diagram illustrating an example of a correspondence degree determination unit 50.

FIG. 3 shows a first pattern X and a second pattern X input from an input unit.
FIG. 6 is a diagram showing an example of a pattern Y.

FIG. 4 is a diagram showing an example of an arrangement of feature points and an extraction range of a feature amount.

FIG. 5 is a diagram showing an example of a plurality of correspondence candidate points k for a certain feature point i.

FIG. 6 is a diagram illustrating an example of a distance between a certain feature point i and its corresponding candidate point k, and the distance between a plurality of corresponding candidate points k ′ of a nearby feature point u of the feature point i.

FIG. 7 is a schematic diagram showing positions of one of the corresponding candidate points k of a certain feature point i and a plurality of corresponding candidate points k ′ of a nearby feature point u on a second pattern Y.

FIG. 8 is a schematic diagram illustrating an arrangement of feature points i of a first pattern X and a second pattern Y, and a degree of correspondence between corresponding feature points k of each feature point i.

FIG. 9 shows a distance function E (dX, dY) in the fitness calculating section 52.
5 is a graph showing a specific example of (1).

FIG. 10 is a flowchart illustrating an example of processing of a fitness calculating unit 52;

FIG. 11 is a flowchart illustrating an example of a process of a neighborhood suitability suppressing unit 53;

FIG. 12 is a flowchart illustrating an example of processing of a correspondence updating unit and a convergence determining unit 55;

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 10 ... Feature point setting part 20 ... Feature amount extraction part 30 ... Similarity calculation part 40 ... Correspondence candidate point calculation part 50 ... Correspondence determination part 51 ... Correspondence initialization part 52 ... Conformity calculation part 53 ... Neighborhood conformity suppression Unit 54 ... correspondence updating unit 55 ... convergence determining unit 60 ... corresponding point extracting unit

Claims (17)

[Claims] 1. A pattern extraction method for determining whether a first pattern X exists in a second pattern, and extracting an area corresponding to the first pattern from the second pattern when present. In the method, a feature point is arranged on each of the first pattern X and the second pattern Y, and a first feature point is selected from the feature points arranged in the second pattern Y.
A plurality of corresponding candidate points k which may correspond to the feature points on the pattern X of the first pattern X are obtained, and the distance between an arbitrary feature point i on the first pattern X and the neighboring feature point u centered on the feature point i Candidate point k for feature point i
A pattern extraction method, wherein a degree of correspondence of each corresponding candidate point is obtained by using a distance between the corresponding candidate point k ′ of the neighboring feature point u. 2. Finding the correspondence candidate point k, for each feature point on the first pattern X and the second pattern Y, extracting a feature amount from information around the feature point;
2. The pattern extraction method according to claim 1, wherein the similarity is determined by comparing the feature amounts of the pattern X and the second pattern Y, and the correspondence is obtained from the similarity and the distance. 3. A condition that, when obtaining the corresponding candidate point k, the predetermined number does not exceed a predetermined number, and a condition that a feature point having a similarity greater than or equal to a predetermined similarity threshold is set as the corresponding candidate point k. A condition that the corresponding candidate point k of the feature point i is not further increased when any of the two conditions is satisfied first, or that any one of the conditions can be selected. 3. The pattern extraction method according to claim 2, wherein: 4. When determining the degree of correspondence of the corresponding candidate point k, an initial value of the degree of correspondence of each of the corresponding candidate points k is determined. The distance and the distance between the corresponding candidate points on the second pattern Y are obtained, and the distance between the feature points in the first pattern X and the distance between the corresponding candidate points in the second pattern Y are calculated. Calculating a degree of coincidence, calculating a weighted sum of the degrees of correspondence for each of the corresponding candidate points k of the feature points on the first pattern X, and finding a degree of fitness for each corresponding candidate point k. 3. The pattern extraction method according to claim 1, wherein the pattern is extracted. 5. When determining the degree of correspondence of the corresponding candidate point k, the position of the feature point i on the first pattern X on the second pattern Y indicated by the corresponding candidate point k and the vicinity of the feature point i Feature point u
The matching degree of the corresponding candidate point k 'of the neighboring feature point u is suppressed when the positions on the second pattern Y indicated by the corresponding candidate points k' are equal to each other. Pattern extraction method. 6. When determining the degree of correspondence of the corresponding candidate point k, the value of the degree of correspondence of each corresponding candidate point k is updated in accordance with the magnitude of the degree of matching, and the amount of change in the degree of correspondence is determined by a predetermined threshold. In the above case, the calculation of the degree of matching, the suppression of the degree of matching of the neighboring feature points, and the updating of the degree of correspondence are repeatedly performed, and the updating of the degree of correspondence is terminated when the degree of matching becomes smaller than a threshold. The pattern extraction method according to claim 5. 7. In determining the degree of correspondence of the corresponding candidate point k, a corresponding candidate point k having the highest degree of matching at the feature point i on the first pattern X is determined, and the same point as the feature point i is determined.
Is included in the corresponding candidate point k ′ of the nearby feature point u,
7. The pattern extraction method according to claim 4, wherein the matching degree of the corresponding candidate point k 'of the neighboring feature point u is suppressed. 8. A method for determining the degree of correspondence of the corresponding candidate point k, wherein the degree of correspondence is updated by a predetermined amount with respect to the corresponding candidate point k having the highest fitness at the feature point i on the first pattern X. The pattern extraction method according to claim 4, 5, 6, or 7, wherein 9. The method according to claim 4, wherein, when the correspondence is initialized or the correspondence is updated, a normalization process is performed so that an arbitrary correspondence falls within a certain range. The pattern extracting method according to claim 6 or claim 8. 10. A pattern extraction for determining whether or not a first pattern X exists in a second pattern, and extracting an area corresponding to the first pattern from the second pattern when present. In the apparatus, a feature point setting unit for arranging feature points on the first pattern X and the second pattern Y, respectively, for each feature point arranged by the feature point setting unit, a feature amount is obtained from pattern information around the feature point. And a feature amount extraction unit that extracts the feature points of the first pattern X and the second pattern Y by comparing the feature amounts of the first pattern X and the second pattern Y.
A similarity calculation unit that calculates the similarity of the feature points of the pattern Y, and a plurality of features on the second pattern Y that may correspond to feature points on the first pattern X based on the similarity between the feature points. A corresponding candidate point calculating unit for obtaining a corresponding candidate point k, a distance between an arbitrary feature point i on the first pattern X and a nearby feature point u centered on the similarity, A correspondence determining unit for repeatedly calculating the correspondence of each corresponding candidate point k using the distance between the correspondence candidate point k and the correspondence candidate point k ′ of the neighboring feature point u of the feature point i; And a corresponding point extracting unit for extracting a corresponding candidate point k having a high value. 11. The correspondence candidate point calculation unit, for an arbitrary feature point i on the first pattern X, sorts feature points j on the second pattern Y having a large degree of similarity with that point in descending order. A condition that the upper limit number of candidate points does not exceed a predetermined number when setting a corresponding candidate point k; a condition that a feature point having a similarity greater than or equal to a predetermined similarity threshold is set as a corresponding candidate point k; 11. The pattern according to claim 10, wherein when any one of the two conditions is satisfied first, the condition that the corresponding candidate point k of the feature point i does not increase any more can be selected. Extraction device. 12. A correspondence initializing unit for determining an initial value of the correspondence of each correspondence candidate point k, each feature point i on the first pattern X and its neighboring feature point u The distance between the feature points in the second pattern Y and the distance between the feature points in the first pattern X are determined by calculating the distance between the corresponding candidate points k and k ′ on the second pattern Y. The degree of matching of the candidate point distances is calculated, and a weighted sum of the degrees of correspondence is calculated for each corresponding candidate point k of the feature point on the first pattern X, and the degree of matching for each corresponding candidate point k is calculated. A degree-of-fit calculating unit to be obtained; a position on the second pattern Y indicated by the corresponding candidate point k of the feature point i on the first pattern X; and a nearby feature point u of the feature point i
Are the same on the second pattern Y indicated by the corresponding candidate point k ′, the matching degree of the corresponding candidate point k ′ of the neighboring feature point u is determined according to the matching degree of the feature point i at the corresponding candidate point k. A neighborhood matching suppression unit that suppresses, a correspondence updating unit that updates the correspondence value of each corresponding candidate point k according to the magnitude of the matching, and a case where the amount of change in the correspondence is equal to or greater than a predetermined threshold value Comprises a convergence determining unit that repeats processing by the fitness calculating unit, the neighborhood fitness suppressing unit, and the correspondence updating unit, and ends the updating of the fitness when it becomes smaller than a threshold. The pattern extraction device according to claim 10 or 11. 13. The neighborhood matching degree suppression unit obtains a corresponding candidate point k having the highest matching degree at a feature point i on the first pattern X, and determines the same point as the feature point i.
Is included in the corresponding candidate point k ′ of the nearby feature point u,
13. The pattern extracting apparatus according to claim 12, wherein the degree of conformity of the corresponding candidate point k 'of the neighboring feature point u is suppressed by a predetermined value. 14. The correspondence updating unit updates a correspondence of a feature point i on the first pattern X by a predetermined amount with respect to a correspondence candidate point k having the highest matching degree. 14. The pattern extraction device according to claim 12 or 13. 15. The apparatus according to claim 12, wherein the correspondence initializing unit and the correspondence updating unit add a process for normalizing the correspondence so that the arbitrary correspondence falls within a certain range. The pattern extraction device according to claim 14. 16. Pattern extraction for determining whether a first pattern X exists in a second pattern and, if present, extracting an area corresponding to the first pattern from the second pattern. In the method, a feature point is arranged on each of the first pattern X and the second pattern Y, and a first feature point is selected from the feature points arranged in the second pattern Y.
A plurality of corresponding candidate points k which may correspond to the feature points on the pattern X of the first pattern X are obtained, and the distance between an arbitrary feature point i on the first pattern X and the neighboring feature point u centered on the feature point i Candidate point k for feature point i
A medium for recording a program for realizing a pattern extraction method characterized in that a degree of correspondence of each corresponding candidate point k is obtained by using a distance between the corresponding candidate point k ′ of the neighboring feature point u. 17. Pattern extraction for judging whether a first pattern X exists in a second pattern and extracting an area corresponding to the first pattern from the second pattern when present. In the apparatus, a feature point setting unit for arranging feature points on the first pattern X and the second pattern Y, respectively, for each feature point arranged by the feature point setting unit, a feature amount is obtained from pattern information around the feature point. And a feature amount extraction unit that extracts the feature points of the first pattern X and the second pattern Y by comparing the feature amounts of the first pattern X and the second pattern Y.
A similarity calculation unit that calculates the similarity of the feature points of the pattern Y, and a plurality of features on the second pattern Y that may correspond to feature points on the first pattern X based on the similarity between the feature points. A corresponding candidate point calculating unit for obtaining a corresponding candidate point k, a distance between an arbitrary feature point i on the first pattern X and a nearby feature point u centered on the similarity, A correspondence determining unit for repeatedly calculating the correspondence of each corresponding candidate point k using the distance between the correspondence candidate point k and the correspondence candidate point k ′ of the neighboring feature point u of the feature point i; And a corresponding point extracting unit for extracting a corresponding candidate point k having a high score.