JP2856539B2 - Image feature selection processing method in generalized Hough transform - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image feature selection processing method in generalized Hough transform required for pattern recognition of an image.

[Conventional technology]

In the following description, various feature types are simply referred to as “features”, and the two-dimensional data representation of each “feature” is referred to as a “feature image”.

Conventionally, it is known to use generalized Hough transform for pattern recognition. The mode in which the generalized Hough transform process is used for pattern recognition is as follows. (I) First, a reference sample (reference sample) in a certain category is selected, and a feature image (reference feature image-each feature) obtained for each of a plurality of features having different properties using the reference sample is selected. Each time, a plurality of reference characteristic images) are extracted.

(Ii) In each of the reference feature images, for example, the center of gravity of the reference feature image is set as a “reference point,” and a plurality of points in the reference feature image in which the feature is better expressed are selected, and each is referred to as a “feature”. Point ”.

(Iii) The reference point and each feature point are associated with each other by a vector given by a value (distance r and angle α) on polar coordinates. That is, To correspond.

(Iv) When such a correspondence is obtained, the reference feature image is expressed as (r ₁ , α ₁ ), (r ₂ , α ₂ ) corresponding to the feature as a representation of the reference feature image. )… (R _j , α
_j )... (r _N , α _N ) A reference table representing a feature point sequence is prepared.

(V) Next, when an input pattern to be recognized is given, characteristic images (recognition target characteristic images) are obtained in the same manner as described above, and the following processing is performed for each characteristic image.

(Vi) A plurality of feature points are selected on the recognition target feature image corresponding to a certain feature. Assuming that the coordinates of the one feature point are (x ₁ , y ₁ ), a sequence of feature points (r ₁ , α ₁ ), (r ₂ , α ₂ )... r _j ,
α _j ) ... (r _N , α _N ) Calculate the temporary reference point given by Note that θ is an angle (θ ₁ , θ ₁ + Δ, θ ₁ + 2Δ) given in an arbitrary step.
..), But θ = 0 is set for simplicity.

(Vii) For each of the plurality of feature points (x ₂ , y ₂ ), (x ₃ , y ₃ ) on the recognition target feature image described in (vi) above,
Similarly, a temporary reference point is calculated.

(Viii) The “temporary reference point” obtained in this way is plotted on, for example, a two-dimensional plane, and the value “1” is accumulated at the plot point. That is, a frequency distribution is generated. This frequency distribution is shown as A (x, y, θ).

(Ix) In the distribution of the frequency distribution A (x, y, θ), the degree of variation at the center point of the voting result, as it were, represents the “similarity” between the recognition target pattern and the reference sample. I have. That is, if the variation is equal to or less than the threshold value and equal to or more than the threshold value for another category, the recognition target pattern is determined to belong to the category.

As described above, the generalized Hough transform has been conventionally used for pattern recognition.

In the related art, a feature image which is an input of a generalized Hough transform is defined as a combination of a plurality of feature images, which is disclosed in Japanese Patent Application No. 2-124624, “Pattern Matching Method”.
(Sano, Ishii), but how to determine a plurality of feature images and how to determine feature points has not yet been clarified.

For the method of applying a generalized Hough transform to a single feature to determine feature points, see “JLTurney,
TNMudge and RAVolz “Recognizing Partially Occl
uded Parts ", IEEE Trans, Vol. PAMI-7, No. 4, July 198
5 ", but the method of determining feature points for multiple feature images has not been clarified.

[Problems to be solved by the invention]

Determining the feature and feature point weights for the feature point value covariance matrix is an evaluation of the hit rate problem for the lookup table inherent in the generalized Hough transform. Due to quantization error)
And the evaluation of conversion errors due to differences in resolution cannot be performed, and true feature selection cannot be performed.

An object of the present invention is to solve a problem of optimally setting a combination of features when a plurality of feature images are used in combination for generalized Hough transform with respect to a given recognition problem.

[Means for solving the problem]

In order to solve the above-mentioned problem, in the present invention, the frequency distribution stored in the accumulator array, which is a generalized Hough transform output, is caused by a variation within a category (between images obtained by adding a disturbance to an image of the same object). A distance determined from a relationship with a variation between categories (between images of other objects) is used as a weight.

In this specification, "feature" is described by a feature name such as "edge direction variance", "complexity", "spreading degree", "ellipticity", or "directionality" described later. This is a so-called “feature” that is specified, and is a property that the pattern to be recognized has when performing pattern recognition and that characterizes the pattern to be recognized. In this specification, the description “category” means that the recognition target pattern corresponds to, for example, a reference pattern representing a pattern belonging to category A, and does not correspond to a reference pattern belonging to another category. In this case, such a “category” where the “recognition target pattern belongs to category A” is meant. Furthermore, it is a "part name" that specifies each part when there are four parts as described later in FIG.

(Operation)

By using the weights, feature selection that maximizes the category separation capability is performed, including the hit ratio for the reference table and the conversion error.

〔Example〕

FIG. 1 is a flowchart showing an embodiment of the present invention. In the generalized Hough transform described in the embodiment of the present invention, the pixel address (x, y) of the input image feature is ((rz, αz), z
= 1, ..., Nc) and the element of the lookup table that stores the feature point sequence Of the accumulator array A (x, y,
θ), an increment operation of A (x, y, θ): = A (x, y, θ) +1 is performed. Therefore, when the same processing is performed for many input image features as the converted output, the frequency distribution A (x,
y, θ) is generated. The following discussion holds for the conversion taking the variation of the size s into consideration.

In the following embodiment, the categories are assumed to be two-category questions of the category itself and the other categories, and the weight of each feature is calculated for each category to determine the number of feature combinations. That is, when processing for one category P is considered, there are only two categories of categories to be recognized: a category P and a category other than P (however, negation of P). The weight of each feature is calculated for each of the two categories, and the number of combinations of the features is determined.

First, the flow of processing of the feature selection method (Step 1 to Step 6) will be described.

Step 1: Feature point selection First, a reference sample is selected for each category, and a plurality of feature images having different properties are extracted from the sample image. Here, as a method for extracting a plurality of characteristic images having different properties, Japanese Patent Application No. 62-45272, “Image Feature Extraction Calculation Method” (Meguro, Sano, Ishii), Japanese Patent Application No. 62-45
No. 273 “Image feature extraction method” (Sano, Meguro, Ishii), Japanese Patent Application No. 62-60800 “Image feature extraction device” (Sano, Meguro,
Ishii), and effective extraction of multiple features is possible.
Hereinafter, the extracted feature image is referred to as a reference feature image.
Next, feature points are selected with respect to the extracted reference feature image of each feature. As feature point selection means, first, feature point selection processing is performed such as a maximum point and a minimum point in the feature distribution, or points above or below a certain threshold value, upper Nc points, lower Nc points, or the like. Thereafter, a feature point having the maximum mutual distance with the selected feature point is selected. Selecting a feature point that maximizes the mutual distance reduces the conversion error of the generalized Hough transform.

Step 2: Create reference table Create a reference table for each category and each feature for the feature point selected in Step 1. The reference table stores each feature value and a polar coordinate vector (rz, αz) (z = 1,..., Nc) of each feature point starting from the reference point (XG, YG).

Step3: Calculate feature weights For each category and each feature, extract the feature images of each feature in the category for M samples to which various disturbances (for example, indicating illumination fluctuations and object deformation) are added. ,
A generalized Hough transform is performed between the feature image and the reference table created in Step 2, and a change in the frequency distribution of the output M accumulator arrays A (x, y, θ) is examined. There are three ways to grasp the variation of this distribution: (a) examining the variation of the maximum frequency in the distribution, (b) examining the variation of the sharpness of the distribution, and (c) examining the variation of the offset value of the distribution. However, here, a case will be described in which attention is paid to the variation of the maximum frequency of (a). Here, the average value of the maximum frequency value in the accumulator array within the category is MIN
TRA and variance are VINTRA, the average of the maximum frequency values in the accumulator array between categories is MINTER, and the variance is VINT
When ER is set, the weight for each category and each feature is W = (1/8) | MINTRA−MINTER | / ((VINTRA + VINTE
R) / 2) + (1/2) 1n (((VINTRA + VINTER) 2) /
(VINTRA × VINTER)) It can be determined by the distance defined by (2). This is Bhattacha
It is a one-dimensional ryya distance. Therefore, if W is sufficiently large, the feature is stable and has high discrimination ability.

The same applies to (b) and (c).
Also, an amount obtained by combining (a), (b), and (c) (for example, a linearly weighted sum of the maximum frequency value, the sharpness of the distribution, and the offset value) may be used instead of the maximum frequency value.

Step4: Ranking of features For each category, the weight of each feature is sorted, and each feature is ranked whether it is more effective in recognizing the category.

Step 5: Evaluation of combination of features For each category, combination of reference tables is performed in order from the one with the highest feature rank. This combination method includes a method of combining with an AND condition, a method of combining with an OR condition, and a method of combining them.

The combination under the AND condition is, for example, a combination in which two features are set to be “matched together”. Also, the combination under the OR condition is, for example, a combination of two features that “satisfies only one of them and becomes a matching condition”. In the case of combining with the AND condition, the hit rate of the reference table decreases unless the variation of the feature point value within the category is small. In addition, the characteristics of the accumulator array with small variation within the category
Applying the AND condition improves discrimination ability. On the other hand, when combined under the OR condition, there is no need to perform the generalized Hough transform each time the combination is performed, and if the accumulator arrays for each category and each feature calculated in Step 3 are stored, they can be simply used as weights W. The new weighted addition produces a new accumulator array.

The discontinuation of the combination is performed when the distance calculated from the intra-category variation and inter-category variation of the accumulator array newly created by the combination is obtained in the same manner as in Step 3, and is performed when this distance is sufficiently large. The distance defined in Step 3 is related to the error rate e, and it is known that e ≦ (1/2) exp (−W) − (3). That is, the termination of the combination can be determined using the error rate e as a system parameter.

Here, when the number of samples is small, the reliability of the variance in the formula for calculating the weight of Step 3 becomes small, and a clear measure of censoring cannot be given. In such a case, the minimum value of the distribution in the category and the maximum value of the distribution between the categories are used as a measure to give the mutual difference between the maximum frequency value distribution in the accumulator array within the category and the maximum frequency value distribution in the accumulator array between the categories. The difference from the value is conceivable. Further, it is also conceivable to combine the features until the number of distributions between categories that is larger than the minimum value of the distributions within the categories (that is, the number of overlapping categories: the number of unidentifiable categories) disappears.

Step6: Iterating by changing resolution Step1 to Step5 are repeated until the error rate becomes sufficiently small.
Alternatively, the resolution of the feature image is repeated from coarse to fine until the number of unidentifiable categories becomes zero. For each resolution, it is desirable for efficiency to discontinue the combination of features as soon as possible for categories that cannot be further identified even if the number of features is increased. For these categories, identification is performed using feature images with finer resolution.

The flow of the feature selection method has been described above. Next, the matching process using the result of the feature selection will be described. The matching process is performed when an unknown sample is input.
This is a process for determining which category the sample belongs to. In the matching process, generalized Hough transform is performed on multiple feature images extracted from unknown samples and reference tables (tables joined by AND conditions or tables joined by OR conditions) obtained by the feature selection method. The category to which the unknown sample belongs is determined by determining whether or not the maximum frequency value in the accumulator array, which is the conversion output, exists at a position that sufficiently separates the intra-category distribution and the inter-category distribution.

Next, an example in which the feature selection processing method of the present invention is applied to an engine component (14 category) identification problem will be described.

FIGS. 2A, 2B, 2C, and 2D show examples of parts in four typical categories out of 14 categories. For images in this category, Japanese Patent Application No. 62-45272, "Image Feature Extraction Calculation Method" (Meguro, Sano, Ishii), Japanese Patent Application No. 62-45273, "Image Feature Extraction Method" (Sano, Meguro, Ishii) , Japanese Patent Application No. 62-60
According to the feature extraction method of No. 800 "Image Feature Extraction Device" (Sano, Meguro, Ishii), ten features with different properties given by "feature name" shown in the left half of Fig. 3 Is extracted. FIG. 3 is a diagram showing a feature list and ranks of features. These features are extracted from an image obtained by compressing an original image (512 × 512 pixels) to 128 × 128, and are finally compressed to a resolution of 32 × 32 pixels. First, feature selection is performed at a resolution of 32 × 32 pixels. For each category, eight sample images obtained by arbitrarily applying rotation and translation to the category are obtained and used for feature selection.

One reference sample is selected from these eight samples, and S
Used for the reference table creation processing of tep1 to Step2. As feature points, 50 points for each category and each feature were selected in order from the top of each feature value so that the distance from each other was maximum. Each feature value is quantized to 3 bits and stored in the reference table. In Step 3, the weight of each feature was calculated from the variation of the maximum frequency value in the accumulator array of the generalized Hough transform between and within the category using Equation (2), and the ranking of the features was performed in Step 4. The result is
This is shown in the right half of FIG. Next, in Step 5, each feature is sequentially combined under the OR condition from the feature with the highest rank, and the number of distributions between categories that is larger than the minimum value of the distribution in the category (that is, the number of overlapping categories: cannot be identified) FIG. 4 shows the results of measuring the number of categories. According to FIG. 4, it is confirmed that the number of unidentifiable categories gradually decreases as the features are combined. In each category, the number of indistinguishable categories was at most two. In other words, it falls into two categories: category 4 shown and another category.
Next, the resolution of the feature image was increased to 64 × 64, and Step 1 to Step 5 were executed only for the set of indistinguishable categories. The number of indistinguishable categories was 0 only by looking at only one type of feature.

〔The invention's effect〕

As described above, according to the present invention, the frequency distribution stored in the accumulator array, which is the generalized Hough transform output, indicates the variation between categories (between images in which disturbance is added to the image of the same object) and the variation between categories. By examining the variation (between images of other objects), it is possible to effectively select features with high stability and high category separation ability, including the hit ratio for the lookup table and the effects of conversion errors. It has become possible to easily increase the performance of the entire recognition system.

[Brief description of the drawings]

FIG. 1 is a flow chart showing an embodiment of the present invention. FIGS. 2A, 2B, 2C, and 2D show examples of parts of four typical categories out of 14 categories, and FIG. FIG. 4 shows the rank of the feature, and FIG. 4 shows the measurement results.

──────────────────────────────────────────────────続 き Continued on the front page (58) Field surveyed (Int.Cl. ⁶ , DB name) G06T 7/00

Claims (4)

(57) [Claims] An image feature selection processing method for selecting an image feature after obtaining a generalized Hough transform output of each feature image obtained from an input image and the contents of a reference table of each feature image obtained from a reference image. The variation of the frequency distribution of the generalized Hough transform output on the accumulator array when the input image varies within the category, and the accumulator array of the generalized Hough transform output when the input image differs between categories The weight is determined using the distance determined from the variation of the frequency distribution above, and the features are combined and applied in descending order of the weight,
An image feature selection processing method in the generalized Hough transform, wherein the feature combination is performed until the weighted distance becomes equal to or more than a certain value or is not further improved. 2. A generalized Hough transform according to claim 1, wherein for each feature image obtained from the reference image, a feature point having the maximum mutual distance is selected and a reference table is created. Image feature selection processing method. 3. A general method according to claim 1, wherein the category is a two-category problem of the category itself and the other categories, and the weight of each feature is calculated for each category to combine the features. An image feature selection processing method in the Hough transform. 4. The feature according to claim 1, wherein a feature in which the variation in the frequency distribution of the generalized Hough transform output in the category is smaller than the threshold value is combined by an AND condition, and the variation in the category is larger than the threshold value. An image feature selection processing method in the generalized Hough transform characterized by combining features under an OR condition.