JP4994174B2 - Data processing apparatus and data processing method - Google Patents

Description

  The present invention relates to a data processing apparatus and a data processing method for processing various types of data such as images and sounds using an eigenspace method.

  In the conventional data processing using the eigenspace method, for example, several images related to pattern recognition are compared with a database, and a common similarity threshold is used.

  For example, when comparing a face photograph with an input face image, an improvement is made to the above method, and a model space and a variation space are separated and feature extraction is known (see Patent Document 1).

However, from the viewpoint of whether there is a part (image, word, etc.) similar to one image or a series of sounds, or a different part (image, word, etc.) exists in one image or a series of sounds. No data processing is done.
Japanese Patent Laid-Open No. 10-171988

  The present invention has been compared with the current state of data processing using the eigenspace method as described above, and its purpose is to determine whether or not a portion of a set of data is similar or dissimilar and to obtain a desired To provide a data processing device and a data processing method capable of extracting partial data.

A data processing apparatus according to the present invention includes a data dividing unit that divides processing target data into sizes of sections to be compared;
For each section divided by the data dividing means, an average value for each same row element of the data to be processed in each section is obtained, and a matrix obtained by subtracting this average value from the corresponding row element, a transposed matrix of this matrix, and A covariance matrix generating means for generating a covariance matrix by multiplication of eigenvalue, eigenvector calculating means for calculating eigenvalues and eigenvectors of the covariance matrix generated by the covariance matrix generating means, and eigenvalue / eigenvector calculating means Feature vector extraction for extracting the feature vector of each section by multiplying the multiplication result of the transposed matrix of the calculated eigenvector and the transposed matrix portion in the covariance matrix by the non-transposed matrix portion in the covariance matrix And a distance calculating means for calculating a distance between each element of the feature vector extracted by the feature vector extracting means. And a threshold setting means for setting a threshold for comparison with the distance between each element, and each element having a corresponding distance is obtained based on the threshold set by the threshold setting means, and a classification corresponding to this element is determined. And a specifying means for specifying.

  The data processing apparatus according to the present invention includes a minimum distance extraction unit that extracts a distance between each element calculated by the distance calculation unit and that is the minimum distance for each element for each section, and the specifying unit includes: The distance extracted by the minimum distance extracting means is compared with the threshold value, each element having the corresponding distance is obtained, and the category corresponding to this element is specified.

  In the data processing apparatus according to the present invention, the specifying means outputs data of the specified section.

The data processing method according to the present invention includes a dividing step of dividing the processing target data into sizes of sections to be compared;
For each segment divided by this segmentation step, the average value for each identical row element of the data to be processed in each segment is obtained, and the matrix obtained by subtracting this average value from the corresponding row element and the transposed matrix of this matrix A covariance matrix step for generating a covariance matrix by multiplication, an eigenvalue / eigenvector calculation step for calculating eigenvalues and eigenvectors of the covariance matrix generated by the covariance matrix step, and an eigenvalue / eigenvector calculation means An extraction step of extracting the feature vector of each section by multiplying the multiplication result of the transposed matrix of the eigenvector and the transposed matrix portion in the covariance matrix by the non-transposed matrix portion in the covariance matrix, and this extraction A distance calculating step for calculating a distance between each element of the feature vector extracted in the step; A threshold value setting step for setting a threshold value for comparison with the distance between, and a distance between each element calculated by the distance calculation step based on the threshold value set by the threshold value setting step and having a corresponding distance A specific step of obtaining each element and identifying a category corresponding to the element is provided.

  The data processing method according to the present invention includes a minimum distance extraction step for extracting a distance that is the minimum distance for each element for each section with respect to the distance between each element calculated by the distance calculation step, and the specifying step includes: The distance extracted by the minimum distance extracting step is compared with the threshold value, each element having the corresponding distance is obtained, and the category corresponding to this element is specified.

  In the data processing method according to the present invention, the specifying step outputs data of the specified section.

  According to the present invention, the processing target data is divided into the sizes of the sections to be compared, the feature vector is extracted for each of the divided sections, the distance between each element of the feature vector is calculated, and the distance between each element Therefore, it is possible to make a determination of similarity or dissimilarity between a part of a set of data.

  In addition, a threshold value for comparison with the distance between each element can be set, and each element having the corresponding distance is obtained based on the set threshold value, and the classification corresponding to this element is specified, so the threshold value is controlled. Thus, it is possible to freely extract a group of data within a desired similarity range.

  Further, with respect to the calculated distance between each element, the distance with the smallest distance for each element is extracted for each category, and the extracted distance is compared with the threshold value to obtain each element having the corresponding distance. Since the category corresponding to this element is specified, the portion with the highest similarity can be selected for each piece of data, and if the portion is at the predetermined similarity, the identification is performed, and the stricter Based on the criteria, it is possible to make determinations such as similarity or dissimilarity between portions of a group of data.

Embodiments of a data processing apparatus and a data processing method according to the present invention will be described below with reference to the accompanying drawings. In each figure, the same constituent elements are given the same numbers, and redundant description is omitted.
<Example 1>
FIG. 1 is a block diagram of a data processing apparatus according to the first embodiment. The data processing apparatus includes a data capturing unit 11 and captures a set of data.

The data acquisition unit 11 may acquire data from a data storage device or the like, or may accumulate data that arrives in real time to form a set of data. In addition, a certain group of data is a piece of image data or audio data such as a lecture. As a specific example, the image data shown in FIG. In the data capture unit 11, the captured data can be described as {I ₀ ,..., I _i }. In the image of FIG. 3, the luminance data (R, G, B) for each pixel corresponds to {I ₀ ,..., I _i }, and one image is composed of i pixels. ing.

  A data dividing unit 12 is arranged at the subsequent stage of the data fetching unit 11. The data dividing unit 12 constitutes a data dividing unit that divides processing target data into division sizes to be compared. The data dividing unit 12 divides the data into several division sizes according to the setting. In the example of FIG. 3A, the divided images Pic · 1 to Pic divided into one image by k (16) equal parts. Divide into k (k = 16).

The data of the segmented images Pic · 1 to Pic · k (k = 16) can be represented as {A ₁₁ ,..., A _j1 } ^T in the segmented image Pic · 1 and {A in the segmented image Pic · 2 ₁₂ ,..., A _j2 } ^T, and can be represented as {A _1k ,..., A _jk } ^{T in} the segmented image Pic · k (k = 16). T indicates a transposed matrix. By this division, j = i / k, and k = 16 includes j pixels in one segment image.

Additional _{{A 11, ···, A j1} } T, {A 12, ···, A j2} T, ···, {A 1k, ···, A jk} each element A _xy in ^T is The luminance data (R, G, B) of one pixel is shown. Next to the data dividing means 12, an average value calculating means 13 is arranged. The average value calculating means 13 calculates an average value for the elements in the same row included in the data of each section (here, the image), and the general j row (jth) element {A _j1 , ..., wherein determining the average value M _j for a _j1} can be expressed by the following equation (1).

Next to the average value calculating means 13, a covariance matrix generating means 14 is arranged. In this covariance matrix generation means 14, the result of subtraction with a general j row (jth) element {A ₁₁ ,..., A _jk } is expressed as Q _jk using the average value M _j. Then, the covariance S _{kk (k = 1, 2,..., K)} can be obtained by using the following (Expression 2). Here, Q _jk ^T represents a transposed matrix of Q _jk . For k of Q _jk ^T and Q _jk , k = 1, 2 _,.

The eigenvalue / eigenvector calculation means 15 is arranged following the covariance matrix generation means 14. The eigenvalue / eigenvector calculation means 15 calculates eigenvalues λ ₁ ,..., Λ _k and eigenvector V of the covariance S _kk by a known calculation. The eigenvalue λ and the eigenvector V can be described as in the following (Equation 3).

A feature vector extraction unit 16 is arranged following the eigenvalue / eigenvector calculation unit 15. The feature vector extracting means 16 calculates (Q _jk · V) ^T · Q _jk using the eigenvalue vector V and the above Q _jk ^T and Q _jk to obtain a feature vector. Since the calculated (Q _jk · V) ^T · Q _jk is a determinant of k rows and k columns as in (Equation 4), the elements arranged in the row direction in (Equation 4) are collected to be a feature vector. c1 to ck are obtained. _{That, c1 = {c 11, ···} , c k1} T, c2 = {c 12, ···, c k2} T, ···, ck = {c 1k, ···, c kk} T Get.

A distance calculation means 17 is arranged at the subsequent stage of the feature vector extraction means 16. The distance calculation means 17 calculates the distance between each element of the feature vectors c1 to ck. In this embodiment, when the distance between each element is d _mn , the Euclidean distance is calculated by the following (Equation 5). Is required.

  When the obtained Euclidean distance is shown by a matrix, it is k rows and k columns as shown in (Expression 6).

  A specifying unit 18 is arranged following the distance calculating unit 17. A threshold setting unit 19 is connected to the specifying unit 18. The threshold value setting means 19 sets a threshold value for comparison with the distance between the elements (the Euclidean distance). The specifying unit 18 compares the distance between the elements calculated by the distance calculating unit 17 based on the threshold set by the threshold setting unit 19 to obtain each element having the corresponding distance, and classifies the corresponding element. Is specified.

For example, it is assumed that the threshold setting unit 19 sets a value greater than 5 and less than 40 as the threshold. As a result, the specifying unit 18 obtains an element d satisfying 5 <d <40 for each element d of k rows and k columns in (Expression 6). Here, when the element d _k1 and the element d ₂₃ in k rows and k columns in (Equation 6) are selected as satisfying the above threshold condition 5 <d <40, the segments are arranged in the column direction to which the elements belong. Are identified.

That is, for the element d _k1 , the divided images {A ₁₁ ,..., A _j1 } ^T , {A ₁₂ ,..., A _j2 } ^T , ..., {A _1k,. {A ₁₁ ,..., A _j1 } ^T = Pic · 1 in the first column in A _jk } ^T is specified, and the segment image {A ₁₁ ,..., A _j1 } is specified for the element d ₂₃ . _{^{T, {a 12, ···,}} a j2} T, ···, {a 1k, ···, a jk} of the third column in _{^{T {a 13, ···, a}} j3} T = Pic 3 is specified. The identified segmented image is output to the display unit 30 and displayed.

  The data processing apparatus configured as described above can be realized by a personal computer or a computer having another processor executing the flowchart shown in FIG. The operation in this case will be described based on the flowchart shown in FIG. The program is started, and the processor takes in a set of data (S11).

The data captured by the processor in the above can be described as {I ₀ ,..., I _i }. If this data is the data of the image shown in FIG. 3A, the luminance data (R, G, B) for each pixel is {I ₀ ,. _i }, and one image is composed of i pixels as described above.

The processor divides the data to be processed into the sizes of sections to be compared (S12). In the example of FIG. 3A, one image is divided into divided images Pic · 1 to Pic · k (k = 16) divided into k (16). The data of the divided images Pic · 1 to Pic · k (k = 16) are Pic · 1 = {A ₁₁ ,..., A _j1 } ^T , and the divided images Pic · 2 = {A ₁₂ ,. _j2 },..., segmented image Pic · k (k = 16) = {A _1k ,..., A _jk } ^T.

Subsequent to step S12, the processor calculates an average value for elements in the same row included in the data of each section (S13). Here, the formula for obtaining the average value M _j is as shown in (Formula 1). As a result, in the example of the image of FIG. 3, the average value A _jk for the elements in the row direction of the matrix shown in FIG. 4 in which the divided images Pic · 1 to Pic · k (k = 16) are arranged in j rows and k columns. Will be required respectively.

  Further, the processor generates a covariance matrix using the equation shown in (Equation 2) (S14), and obtains eigenvalues λ1 to λk and an eigenvector V using this covariance matrix (S15). As already described, the eigenvalue λ and the eigenvector V are as shown in (Equation 3).

When the eigenvector V is obtained, the processor calculates (Q _jk · V) ^T · Q _jk to obtain feature vectors c1 to ck (S16). Feature vector c1~ck _{is, c1 = {c 11, ···} , c k1} T, c2 = {c 12, ···, c k2} T, ···, ck = {c 1k, ··· , C _kk } ^T.

When the feature vector c1~ck obtained, the processor, the Euclidean distance d _n mutual feature vector c1~ck determined in step S17～S25. That is, the suffix values m and n are initialized to 0 (S17), and the suffix values m and n are incremented by 1 (S18, S19). The processor detects whether the suffix values m and n are the same value (S20), and if it is detected that they are the same value, sets the maximum distance value d _max for D _mn (S21). Returning to step S19, the processing is continued.

When suffix value m, n it is discovered not identical value in step S20, the absolute value of the difference between feature vectors C _m and the feature vector C _n holds determined as D _mn (S22), the suffix value m k If the suffix value m is not greater than k, the process returns to step S19 to continue the process.

Such repeated, sought distance is the elements of the first row of equation (6), the processor then sets the D _mn as d _n (S24), suffix value n is larger than k It is detected (S25), and if the suffix value n is not greater than k, the process returns to step S18 to continue the process. By repeating this, the distance as each element in the second column, the distance as each element in the third column,..., The distance as each element in the k-th column are obtained.

  Here, in the example of FIG. 3A, the feature vectors C1 to Ck when one image is divided into divided images Pic · 1 to Pic · k (k = 16) equally divided into k (16) are set to 0 to 255. When the values are determined so as to be expressed by 256 gradations and the Euclidean distance is obtained, the values are as shown in the table shown in FIG.

  The image of FIG. 3A will be described. In the divided images Pic · 1 to Pic · k (k = 16), the divided image Pic · 1 and the divided image Pic · 3 are equal, and the divided image Pic · 2 and the divided image Pic. 4 is equal, the segmented image Pic5 and the segmented image Pic77 are equal, the segmented image Pic6 and the segmented image Pic8 are equal, the segmented image Pic10 and the segmented image Pic12 are equal, and the segmented image Pic 13 is equal to the segmented image Pic15, and the segmented image Pic14 is equal to the segmented image Pic16. Only the segmented image Pic • 9 and the segmented image Pic • 11 are slightly different.

Therefore, the distance between the partitioned image Pic • 9 and the partitioned image Pic • 11 in the table shown in FIG. 3B is “25” indicating that the distance is a slightly different partitioned image. The maximum distance d _max = “255” indicating that the distances between the completely equal segment images Pic · 1 and the segment images Pic • 3 are the same. The distances in the other combinations of the segment images (for example, the segment image Pic • 1 and the segment image Pic • 16) are “255” indicating that they are completely different.

  As described above, when the table value of k rows and k columns is obtained, the process branches to YES in step 25, and the processor branches to “threshold low” which is the set lower threshold and “threshold high” which is the larger threshold. Are used to extract all distances dn that are larger than “threshold low” and smaller than “threshold high” (S26), and a data group corresponding to the extracted distance dn is, for example, The display is output to the display unit 30 (S27).

  In the example of the image shown in FIG. 3, the “threshold low” is set to 10 and the “threshold high” is set to 36, whereby the segmented images Pic · 9 and the segmented images Pic • 11 are extracted and displayed. As described above, these segmented images Pic.9 and Pic.11 are slightly different images. Therefore, when extracting a portion having a slight image change, or “ This is suitable for performing “error search” and the like.

  Also, 4 × 4 segment images as shown in FIG. 5 are input as a single image, divided into 4 × 4 segment images, and processed in the same manner as described above. By setting “high” to 200, as shown in FIG. 6, it is possible to specify and display three segment images of Label 4, Label 5, and Label 11 in which the same person is shown. Further, by setting the “threshold low” to 160 and the “threshold high” to 168 for the image of FIG. 5, the images of Label 8 and Label 9 in which the same person is shown are identified and displayed as shown in FIG. be able to.

<Example 2>
FIG. 8 shows a block diagram of a data processing apparatus according to the second embodiment. In this data processing apparatus, the minimum distance extracting means 20 is interposed between the distance calculating means 17 and the specifying means 18 in the first embodiment. The minimum distance extraction means 20 extracts the distance between the elements calculated by the distance calculation means 17 and having the smallest distance for each element for each section. Except for the minimum distance extracting means 20, the same configuration as that of the first embodiment is adopted.

Specifically, in the Euclidean distance matrix of k rows and k columns as in (Equation 6), the elements arranged in the column direction are compared, and the smallest one is extracted. As shown in FIG. 9, k (k = 16 in FIG. 3) distances are extracted by extracting the smallest one of all columns. In the example shown in FIG. 9, distances d _k1 , d ₁₂ , d ₂₃ ,..., D _1k are extracted as minimum values as an example.

The specifying unit 18 receives the k distances extracted by the minimum distance extracting unit 20, and the threshold value is applied to the k distances to specify the data of the corresponding category. In the example of FIG. 10, when the distances d _k1 , d ₁₂ , d ₂₃ , and d _1k extracted in FIG. 9 are 30, 100, 30, and 50, the threshold condition 5 <d <40 is set. by being a distance d _k1, d ₂₃ is identified, partitioned image for the element _{d k1 {A 11, ···,} A j1} T, {A 12, ···, A j2} T ,..., {A _1k ,..., A _jk } ^T are identified as {A ₁₁ ,..., A _j1 } ^T = Pic · 1 in the first column, and for element d ₂₃ Category image _{{a 11, ···, a j1} } T, {a 12, ···, a j2} T, ···, {a 1k, ···, a jk} of the third column in the ^T {A ₁₃ ,..., A _j3 } ^T = Pic · 3 is specified, and an image corresponding to these is output and displayed.

  The data processing apparatus according to the second embodiment configured as described above can be realized by a personal computer or other computer having a processor executing the flowchart shown in FIG. In the operation in this case, step S30 is executed instead of step S24 in the flowchart shown in FIG.

In step S23, the processor detects that the suffix value m is larger than k, and the distances {d _MAX ,..., D _k1 } in the first column in FIG. The smallest one of the distances {d _MAX ,..., D _k1 } in the first row is extracted as d _n = D _mn {Minimum} (S30).

After step S30, it is detected whether the suffix value n is larger than k (S25). If the suffix value n is not larger than k, the process returns to step S18 and the processing is continued. By repeating this process, the process of extracting the smallest one is performed for all the columns, and k (k = 16 in FIG. 3) distances are extracted. As already described, in the example shown in FIG. 9, distances d _k1 , d ₁₂ , d ₂₃ ,..., D _1k are extracted as minimum values as an example.

  When the minimum value of each column is obtained as described above, the process branches to YES in step S25, and the processes of steps S26 and S27 are performed as already described in the first embodiment. In this embodiment, since the distance with the smallest distance is extracted for each element for each section, the distance with the highest similarity is extracted for each section, and further, the specifying means 18 (specifying step 26). In the case where the part has a predetermined similarity, it is possible to specify the similarity, and it is possible to determine whether the parts of the data are similar or dissimilar according to a stricter standard.

  Therefore, when the image processing shown in FIG. 5 is performed using the second embodiment, it is possible to extract a segmented image that is not the same and similar, and the segmentation is performed as shown in FIGS. 6 and 7 by changing the threshold value. Images can be extracted and displayed.

The block diagram which shows the structure of the 1st Example in the data processor which concerns on this invention. The flowchart for demonstrating operation | movement of the 1st Example in the data processor which concerns on this invention. The substitute photograph which imaged an example of the image and table for demonstrating an example of the process in the data processor which concerns on this invention. The figure for demonstrating the process of the average value calculation in the data processor which concerns on this invention. The substitute photograph which imaged an example of the image for demonstrating an example of the process in the data processor which concerns on this invention. The substitute photograph which image | photographed the 1st example of the result of processing the image of FIG. 5 by the data processor which concerns on this invention. The substitute photograph which imaged the 2nd example of the result of processing the image of FIG. 5 by the data processor which concerns on this invention. The block diagram which shows the structure of the 2nd Example in the data processor which concerns on this invention. The figure which shows the process of the minimum value extraction by the 2nd Example in the data processor which concerns on this invention. The figure which showed the process of the minimum value extraction by the 2nd Example in the data processor which concerns on this invention into which the number was put. The flowchart for demonstrating operation | movement of the 2nd Example in the data processor which concerns on this invention.

Explanation of symbols

11 Data acquisition unit 12 Data division unit 13 Average value calculation unit 14 Covariance matrix generation unit 15 Eigenvalue / eigenvector calculation unit 16 Feature vector extraction unit 17 Distance calculation unit 18 Identification unit 19 Threshold setting unit 20 Minimum distance extraction unit 30 Display unit

Claims (6)

Data dividing means for dividing the data to be processed into division sizes to be compared;
For each section divided by the data dividing means, an average value for each same row element of the data to be processed in each section is obtained, and a matrix obtained by subtracting this average value from the corresponding row element, a transposed matrix of this matrix, and Covariance matrix generating means for generating a covariance matrix by multiplication of
Eigenvalue / eigenvector calculation means for calculating eigenvalues and eigenvectors of the covariance matrix generated by the covariance matrix generation means;
The characteristic of each section is obtained by further multiplying the multiplication result of the transposed matrix of the eigenvector calculated by the eigenvalue / eigenvector calculating means and the transposed matrix part of the covariance matrix by the non-transposed matrix part of the covariance matrix. Feature vector extraction means for extracting a vector;
Distance calculating means for calculating the distance between each element of the feature vector extracted by the feature vector extracting means;
Threshold setting means for setting a threshold for comparison with the distance between each element;
A specifying means for comparing each distance between the elements calculated by the distance calculating means based on the threshold set by the threshold setting means, obtaining each element having a corresponding distance, and specifying a classification corresponding to the element; A data processing apparatus comprising: For the distance between each element calculated by the distance calculating means, a minimum distance extracting means for extracting the distance with the smallest distance for each element for each section,
The identification unit compares the distance extracted by the minimum distance extraction unit with a threshold, obtains each element having a corresponding distance, and identifies a category corresponding to the element. Data processing device. The data processing apparatus according to claim 1, wherein the specifying unit outputs data of the specified section. A division step for dividing the data to be processed into division sizes to be compared;
For each segment divided by this segmentation step, the average value for each identical row element of the data to be processed in each segment is obtained, and the matrix obtained by subtracting this average value from the corresponding row element and the transposed matrix of this matrix A covariance matrix step for generating a covariance matrix by multiplication ;
An eigenvalue / eigenvector calculation step of calculating eigenvalues and eigenvectors of the covariance matrix generated by the covariance matrix step;
The characteristic of each section is obtained by further multiplying the multiplication result of the transposed matrix of the eigenvector calculated by the eigenvalue / eigenvector calculating means and the transposed matrix part of the covariance matrix by the non-transposed matrix part of the covariance matrix. An extraction step for extracting a vector;
A distance calculating step for calculating a distance between each element of the feature vector extracted by the extracting step;
A threshold setting step for setting a threshold for comparison with the distance between each element;
A specific step of comparing each element calculated by the distance calculating step based on the threshold set by the threshold setting step, obtaining each element having a corresponding distance, and specifying a category corresponding to the element; A data processing method comprising: For the distance between each element calculated by the distance calculating step, a minimum distance extracting step for extracting the distance where the distance is the minimum for each element for each section,
The identifying step compares the distance extracted by the minimum distance extracting step with a threshold value, obtains each element having a corresponding distance, and identifies a category corresponding to the element. Data processing method. 6. The data processing method according to claim 4, wherein the specifying step outputs data of the specified section.