JP3387681B2 - Feature extraction processing device - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention transforms and votes for various natural real spaces by converting points in the real space into a feature parameter space represented by a certain feature.
The present invention relates to a feature extraction processing device by a voting process for extracting features of an object, which utilizes the fact that votes are accumulated at true feature points existing in the real space.

[0002]

2. Description of the Related Art A description will be given of a feature extraction process using a normal voting process for extracting a feature of data from a plurality of input data whose features are unknown.

FIG. 5 shows a conventional feature extraction processing device. In the figure, reference numeral 1 is input data, 8 is a ballot box memory, 9 is a peak detection processing unit, 51 is a feature calculation processing unit, 52 is a voting processing control unit, 53 is a voting amount generation unit, and 54 is an address generation unit. ing.

In order to extract the characteristic of the input data, a voting box memory 8 is provided at each quantization point in the space having the characteristic to be discriminated as a parameter, and the characteristic of the input information is used as an address and the quantum at the position indicated by the information is used. The voting process is executed in the voting box memory 8 for conversion. That is, a certain voting amount is added to the value of the voting box.

In the feature extraction process using this voting process, if the voting process is performed on the feature parameter space with a smaller quantization size in order to further improve the accuracy of the extracted feature quantity, it is present in the input data. There is a problem in that the votes are not accumulated in the true feature amount because the votes are cast at a position deviated from the original voting position due to the error. Therefore, high-precision feature extraction processing is realized by weighting one input data to a plurality of ballot boxes of quantization points near the ballot box indicated by weighting.

A feature calculation processing unit 51 from one input data
The feature amount is obtained by and is input to the voting process control unit 52. In the voting processing control unit 52, the address generation unit 54 generates a plurality of addresses for voting for the feature amount of one input data, and the voting amount generation unit 53 generates the voting amount for each address. , The value of the voting box memory 8 is added to the voting amount.

For example, if the quantization size of the feature space is 0.1,
Assuming that the address of the feature parameter space closest to the features of the input data is κ = 5.5 and the range of the voting space for voting is κ ± 0.5, the voting process is 5.1, 5.2, 5.3. ···,Five.
5, ..., 5.8, 5.9 to 9 ballot boxes,
0.2, 0.4, 0.6, ..., 1.0, ..., 0.4, 0.2
Is added as the voting amount. The voting amount at the quantization point x for the characteristic κ of the input data at this time is 1-2 × | x
It is determined by −κ |.

Finally, the peak detection processing unit 9 detects the quantization point which is the peak of the voting value from the voting box memory 8 to extract the feature existing in the input data.

[0009]

In order to perform weighted voting processing, it is necessary to sequentially add voting values of different values to a plurality of voting boxes for one input data. However, there is a problem that the processing time becomes very long.

An object of the present invention is to achieve a weighted voting process while reducing the processing time.

[0011]

In the present invention, in order to solve the problems], whether to perform the voting process by comparing the evaluation values of the upper bits and the input data of the evaluation value of the quantization point feature parameter space,
A means for determining each of the quantization points, and, as a result of the determination, at the quantization points determined to vote, the lower bits of the evaluation value of the quantization points are used as the voting amount, and the votes are cast in the ballot boxes of the respective quantization points. Means for adding the absolute values of the quantities.

Further, there is provided means for simultaneously executing the above-mentioned processing at the quantization points of the characteristic parameter space by parallel processing. In addition, CAM is used as a memory for all quantization points.
(Associative memory), a means for holding the evaluation value at each quantization point and the ballot box in one word, and the processing means at the quantization point of the feature parameter space in the CAM It has a means to be expanded and executed in parallel.

[0013]

The lower bit of the evaluation value held by each of the quantizing points to vote can be used as it is as the voting amount, which is different from the conventional complicated calculation.

It is possible to speed up the voting process in parallel at all the quantization points in the feature parameter space, which is different from the conventional case where the voting to different quantization points is sequentially processed. Further, the parallel processing device can be downsized by using the CAM.

[0015]

EXAMPLE 1 FIG. 1 shows a diagram for explaining a first example of the present invention. In the figure, reference numeral 1 is input data, 2 is a voting decision processing unit, 3 is an evaluation value setting unit, 4 is an evaluation value memory, 5 is an upper bit, 6 is a lower bit, 7 is a voting operation processing unit, and 8 is a ballot box. A memory and 9 represent a peak detection processing unit.

The evaluation value setting unit 3 obtains evaluation values of all quantization points belonging to the feature parameter space,
Stored in the evaluation value memory 4. The evaluation value memory 4 is set to the upper bit P _{U of the} bit position having the same resolution as the input data 1.
5 and lower bits P _L 6. At this time, the evaluation value is
As described above, a numerical value in which the leading bit of the lower bits when divided is 1 and the other upper bits and lower bits are 0 is added in advance. For example, assuming that the input data from the outside is an integer, the upper bits of the evaluation value memory are treated as an integer part and the lower bits as a decimal part, and the evaluation value is a value in which only the first decimal place bit is 1. That is, it will be set higher by 0.5.

The voting decision processing unit 2 compares the input data I given from the outside with the high-order bits P _U of the evaluation values at all the quantization points, and votes for the voting box with P _U = I. Decide to do. For example, as in the previous example, assuming that the upper bits of the input data and the evaluation value memory are integers, the external input data is “01011” (= 13).
If it is, the voting process is performed at the quantization points with the evaluation value of 12.5 or more and less than 13.5. The evaluation value is
Since it is set to 0.5 higher, the value of the evaluation value memory is not less than 13.0 and less than 14.0, that is, if only the integer part which is the upper bit of the evaluation value memory is compared with the input data, the voting process You can decide whether to do it.

Next, the voting calculation processing unit 7 uses the value of the lower bit P _L of the evaluation value of the quantization point as it is at the quantization point determined to vote as a result of the voting decision processing unit. The value is added to the voting box memory 8.

Assuming that the lower bit P _L is in a two's complement format with the most significant bit as a sign bit, the value of the lower bit is a value that can be positive or negative. Therefore, when the data of the lower bits is positive, the voting calculation processing unit 7 adds the value of the lower bits to the read value of the voting box memory and returns it to the voting box memory 8. When the data of the lower bit is negative, the value of the lower bit is subtracted from the value of the read ballot box memory and the value is returned to the ballot box memory.

In this way, the weighted voting process is performed with the absolute value of the lower bit of the evaluation value as it is as the voting value.
Further, as another embodiment of the weighted voting process in the voting operation processing unit 7, when the data of the lower bit is negative, it is 1 when each bit of the lower bit is 0, and when it is 1, it is 0. It is also possible to perform a weighted voting process in which a value obtained by inverting all bits is used as a voting value.

Finally, the peak detection processing unit 9 detects the quantization point which becomes the peak of the voting value from the ballot box memory 8 of the voting processing unit for all the quantization points, so that the feature existing in the input data is detected. To extract.

(Embodiment 2) FIG. 2 shows another embodiment of the present invention recited in claim 2. In FIG. 2, with respect to all the quantization points (K points) on the feature parameter, the evaluation value memory 4, the ballot box memory 8, the vote determination processing unit 2, and the vote calculation processing unit 7 are independently provided for each quantization point. It has a quantized score voting processing unit 10 having.

The evaluation value setting unit 3 sets the evaluation value memory 4 of all quantization points. Next, the input data 1 is sequentially broadcast to the voting processing units 10 for all the quantization points. The voting processing unit 10 for all quantization points simultaneously executes the voting determination processing and voting calculation processing described in the first embodiment at each quantization point.

Finally, the peak detection processing unit 9 detects the quantization point which becomes the peak of the voting value from the voting box memory 8 of the voting processing unit 10 for all the quantization points, so that it exists in the input data. Extract features.

(Embodiment 3) FIG. 3 shows another embodiment of the present invention for performing parallel processing of weighted voting processing using CAM. Reference numerals in the figure correspond to those in FIG. 1, 21 is a search processing unit, 22 is CAM, 23 is a word, 24 is an evaluation value field, 25 is an upper bit, 26 is a lower bit, and 27 is a ballot box field. ing.

CAM2 as a memory for all quantization points
2 is provided, and 1 quantization point is assigned to 1 word, 1
The word 23 is divided into an evaluation value field 24 and a ballot box field 27.

The evaluation value setting unit 3 sets the value of the evaluation value field 24 of all words. Next, the input data 1 is sequentially input to the search processing unit 21. The search processing unit 21 simultaneously searches all the words, using the input data as search data for the upper bits 25 of the evaluation value field.

As a result of the search, a voting process is executed next for the word of the quantization point that matches. The voting process is described in the first and second embodiments by using the lower bit 26 of the evaluation value field of the word in the word (quantization point) determined to execute the voting process as a result of the search at the same time. As in the voting calculation process, the voting calculation processing unit 7 adds the absolute value of the value of the lower bit of the evaluation value field or the value obtained by inverting the lower bits 0 and 1 to the voting box field as the voting value. To order.

The addition processing between fields in the CAM is a known processing, and a specific processing control method will be omitted here. Finally, the peak detection processing unit extracts the feature existing in the input data by detecting the word (quantization point) that becomes the peak of the value from the voting box field of all the words.

As described above, the voting process at all the quantization points in the characteristic parameter space is executed in parallel using the CAM by using the parallel processing function between words of the CAM. (Embodiment 4) FIG. 4 shows another embodiment of the present invention for performing Hough transform processing.

As a specific example of the feature extraction process using the voting process described so far, a straight line extraction Hough transform processing device for weighted voting process that enables highly accurate straight line detection by Hough transform will be described with reference to FIG. explain.

In FIG. 4, using the processing device described in the third embodiment, the black dot coordinate data obtained from the input image 31 by the image scanning / reading device 32 is sent to the search processing portion 21.
Further, the scanning information of the image scanning reading device is input to the evaluation value setting unit 3.

First, the straight line extraction Hough transform process will be briefly described. A straight line in the image space (xy plane) can be uniquely determined by using the distance (ρ) from the origin and the inclination (θ) viewed from the X axis as parameters. Therefore, in order to extract a straight line existing in the target input image, the coordinate space having the straight line parameters ρ and θ as axes is used as the feature parameter space.

The Hough transform is a process for voting the parameters of all straight lines passing through the black point pixel (x, y) in the input image in the ballot box of the characteristic parameter space, and the parameter space By detecting the peak of the ballot box of, the straight line existing in the input image can be detected. The voting process here is performed by black dot pixels (a,
Since the straight line passing through b) is represented by ρ and θ that satisfy ρ = a cos θ + b sin θ, the curve represented by this formula is voted in the parameter space.

Next, the relationship between the present invention and the straight line extraction Hough transform processing will be described. One word 23 of the CAM 22 is assigned to one quantization point in the feature parameter space,
In the Hough transform, one straight line in the image space is in charge.

As the evaluation value at the quantization point (i, j) in the parameter space, the value of the x coordinate at which the straight line (ρ _i , θ _j ) on the image space corresponding to the quantization point intersects y = κ.
The evaluation value setting unit 3 executes the value with 0.5 added. That is, the equation for obtaining the intersection point coordinate x is x = (ρ _i / cos θ _j ) −κ tan θ _j (1), and as a result, the evaluation value f (ρ _i , θ _j ) is f (ρ _i , θ _j ) = (ρ _i / cos θ _j ) −κ tan θ _j +0.5 (2). Note that the above κ is based on the reference “1994 Electronic Information Communication
Proceedings of the Spring Meeting of the Society D-433, real-time straight line
"Extensive Hough Transform Massively Parallel Hardware Algorithm"
Corresponds to the indicated κ and changes the y-coordinate value sequentially
It is an arbitrary value. Also, add 0.5 to the x-coordinate value
This means rounding the x-coordinate value to an integer value.
It is equivalent.

With the input black point coordinates as search data,
The upper bit 25 of the evaluation value field is searched, and in the matching word, the straight line in charge is the voting target, and the lower bit 26 of the evaluation value field is left unchanged, similar to the voting calculation process described in the third embodiment. , Ballot box field 2
Add to 7.

The voting process is performed on the black dots of all input images, the peak of the voting value is detected from the resulting voting box field 27, and the straight line existing in the input image can be accurately extracted.

As a technique related to the Hough conversion process, the applicant has previously filed Japanese Patent Application No. 6-316187.
There is an issue.

[0040]

As described above, according to the present invention, the weighted voting process for highly accurate feature extraction can be executed at high speed by parallel processing, and by implementing in CAM,
The processing hardware can be miniaturized.

[Brief description of drawings]

FIG. 1 shows a first embodiment of the present invention.

FIG. 2 shows a second embodiment of the present invention.

FIG. 3 shows a third embodiment of the present invention.

FIG. 4 shows another embodiment of the present invention for performing Hough transform processing.

FIG. 5 shows a conventional example.

[Explanation of symbols]

1: Input data 2: Voting decision processing section 3: Evaluation value setting section 5: Upper bit 6: Lower bit 7: Voting calculation processing unit 8: Ballot box memory 9: Peak detection processing unit 10: Voting processor

Claims (4)

(57) [Claims] 1. In order to extract the features of the input data from a plurality of input data of which features are unknown, ballot boxes are provided at all quantization points of the feature space to be discriminated, and evaluations corresponding to each quantization point are provided. calculated values, versus to the quantized point
The process of vote for the ballot box quantization points whose values evaluation value response is corresponding to the evaluation value of the input data performed for all input data, a peak value of ballot boxes after the voting process ends In the feature extraction processing device that detects the feature point position and extracts the feature of the input data, the weighted voting value is added according to the difference between the evaluation value of the input data and the evaluation value at each quantization point. Voting processing means
And an evaluation value of the input data and an evaluation value at each quantization point,
When calculating the weighted voting value according to the difference of , the evaluation value is roughly quantized at each quantization point.
Quantization in which the upper bits of the input data and the evaluation value of the input data match
After determining the point as the quantization point to vote , the evaluation value of the input data at the quantization point determined by the vote and
Evaluation at the quantization point as a difference from the evaluation value of the quantization point
Weighted using the low-order bits that are detailed information of the value
A feature extraction processing device characterized in that a vote value is determined . 2. When determining a weighted voting value by using lower bits which are detailed information of the evaluation value, when the lower bit of the evaluation value of the quantization point is positive, the voting with the weight as it is Means for determining the value, and if the lower bit of the evaluation value of the quantization point is negative, 1's complement or 2
As a negative number represented by the complement, and means for determining a value obtained by inverting the polarity of the lower significant bit as the voting value, the feature extraction apparatus according to claim 1 Symbol placement and having. 3. The feature extraction processing apparatus according to claim 1 or 2 Symbol mounting, has one processing unit per voting process in one quantization point of the feature parameter space, a voting process in all quantization point A feature extraction processing device characterized in that it has means that can be executed in parallel. 4. An apparatus for performing the feature extraction processing according to claim 3 in parallel, wherein one word is assigned to each quantization point as a storage means of an evaluation value and a ballot box at the quantization point of the feature parameter space. A feature extraction processing device comprising an associative memory for a feature space, wherein the voting processing means according to claim 1 can be executed in parallel over all quantization points.