Nova Patents
EP1521210B9

Similarity calculation method and device

Abstract

This record has no abstract on file.

EP1521210B9, drawing sheet 1
Sheet 1 of 42

Term

Term ended

Expired 26 June 2023, 3.2 years ago.

  1. Priority
  2. Filed
  3. Granted
  4. Expired
  5. Today

13 claims: 13 independent, 0 dependent

  1. c-en-01-0001
    A similarity calculation method of determining similarity between two feature vectors, a registered vector (g) and an input vector (f), being representative of an acoustic signal or a video signal, each of the two feature vectors having N corresponding components, N being an integer greater than zero, the method including the following steps:a transform step (S41, S52) in which a predetermined transform operation (S41, S52) is implemented to the two feature vectors (f, g. ),a division step (S41, S52) in which the two transformed feature vectors (f', g') are divided component-wise into a plurality of partial vectors (f1, f2, g1, g2),a recording step (S42, S43) in which the plurality of partial vectors (g1, g2) constituting the transformed registered feature vector (g') are recorded,a hierarchical distance calculation step ( S53, S54, S57, S58, S60, 563. S64) in which the distance between the two feature vectors (f', g') transformed at the transform step (S41, S52) is calculated in a predetermined order based on the predetermined transform operation (S41, S52), wherein the distance calculation is performed between respective components constituting partial vectors (f1, f2, g1, g2) in a component-wise hierarchical manner in order from the partial vector (f1, g1) of the uppermost component order,a threshold value comparison step (S55, S61) in which an integrated value of distances calculated incrementally for hierarchically higher-order components (i) of the two transformed feature vectors (f', g') is compared with a threshold value (S) set in advance,a control step (S55, S56, S57, S58, S61, S62, S63, S64) in which distance calculation is controlled in accordance with a result of the threshold value comparison at the threshold value comparison step (S55, S61), andan output step (S65) in which, as the similarity, the integrated value of the calculated distances up to the last components (i) of the two transformed feature vectors (f', g') is outputted,wherein, at the control step (S55, S56, S57, S58, S61, S62, S63, S64), control is conducted such that the distance calculation is truncated in the case where the integrated value of distances calculated up to a certain component order is greater or equal to the threshold value and such that the distance calculation between next higher-order components is performed in the case where the integrated value of distances calculated up to a certain component order is below the threshold value,and wherein distance calculation is performed such that, in a first step, only the partial vector (g1) of the uppermost component order of the plurality of partial --> vectors (g1, g2) recorded in the recording step is retrieved and the distance calculation is performed between respective components constituting the partial vectors (f1, g1) of the uppermost component order in a component-wise hierarchical manner, and wherein only in the case where the integrated value of calculated distances between all components constituting the partial vectors (f1, g1) of the uppermost component order is below the threshold value, in a second step the partial vector (g2) of the next lower component order of the plurality of partial vectors (g1, g2) of the transformed registered feature vector (g') recorded in the recording step (S42, S43) is retrieved and distance calculation between respective components constituting partial vectors (f2, g2) of the next lower component order is performed.
  2. c-en-01-0002
    The similarity calculation method as set forth in claim 1, wherein the predetermined transform operation (S41, S52) is a transform operation which performs sequencing of order of respective components constituting the two feature vectors (f, g) in accordance with magnitude of dispersion of the respective components, and the distance calculation between the two feature vectors (f', g') transformed at the transform step (S41, S52) is performed in order from components of large dispersion at the hierarchical distance calculation step (S53, S54, S57, S58. S60, S63, S64).
  3. c-en-01-0003
    The similarity calculation method as set forth in claim 1, wherein the predetermined transform operation (S41, S52) is a Discrete Cosine Transform operation or Discrete Fourier Transform operation, and the distance calculation between the two feature vectors (f', g') transformed at the transform step (S41. S52) is performed in order from low frequency component at the hierarchical distance calculation step (S53, S54, S57, S58, S60, S63, S64).
  4. c-en-01-0004
    The similarity calculation method as set forth in claim 1, wherein, the predetermined transform operation (S41, S52) is Walsh-Hadamard Transform operation, and the distance calculation between the two transformed feature vectors (f', g') is performed in order from low frequency component at the hierarchical distance calculation step (S53, S54, S57, S58, S60, S63, S64).
  5. c-en-01-0005
    The similarity calculation method as set forth in claim 1, wherein the predetermined transform operation (S41, S52) is a Karhunen-Loeve transform operation, and the distance calculation between the two feature vectors (f', g') transformed at the transform step is performed in order from component of large eigenvalue --> at the hierarchical distance calculation step (S53, S54, S57, S58, S60, S63, S64).
  6. c-en-01-0006
    The similarity calculation method as set forth in claim 1, wherein the feature vector (a) is obtained by extracting power spectrum coefficients (Sq) within a predetermined time period of an acoustic signal, the power spectrum coefficients (Sq) being the components of the feature vector (a).
  7. c-en-01-0007
    The similarity calculation method as set forth in claim 1. wherein the feature vector (a) is obtained by extracting linear predictive coefficients within a predetermined time period of an acoustic signal.
  8. c-en-01-0008
    The similarity calculation method as set forth in claim 1, wherein the feature vector (a) is obtained by extracting parameters indicating intensities of frequency components within respective frames of an encoded acoustic signal, the parameters being components of the feature vector (a).
  9. c-en-01-0009
    The similarity calculation method as set forth in claim 1, wherein the feature vector (v) is obtained by acquiring image frames from signal value of representative image within respective predetermined time periods of a video signal, preparing an average image (100) of the acquired image frames within the respective predetermined time periods, and preparing a block average image (110) by dividing the average image (100) into X × Y small blocks in breadth and width directions and averaging the values within respective small blocks and by arranging the small blocks in order of R. G, B, the values of the block average image (110) arranged in order of R. G. B being the components of the feature vector (v).
  10. c-en-01-0010
    The similarity calculation method as set forth in claim 1, wherein the feature vector (v) is obtained by preparing histogram with respect to signal values of luminance and/or color of image frame within a predetermined time period of a video signal, the signal values of luminance and/or color being the components of the feature vector (v).
  11. c-en-01-0011
    A similarity calculating apparatus adapted for determining similarity between two feature vectors, a registered vector (g) and an input vector (f), being representative of an acoustic signal or a video signal, comprising:transform means (30. 31) which is adapted to implement a predetermined transform operation to the two feature vectors (f, g), -->dividing means (30, 31) which is adapted to take out, in a predetermined order based on the predetermined transform operation, respective components constituting the two feature vectors (f', g') transformed by the transform means (30, 31) to divide them into a plurality of partial vectors (f1, g1, f2, g2),recording means (32, 33) which are adapted to record the plurality of partial vectors (g1, g2) constituting the transformed registered feature vector (g'),hierarchical distance calculating (34) means which is adapted to perform a distance calculation between the two feature vectors (f', g') transformed by the transform means (30, 31) in a predetermined order based on the predetermined transform operation, wherein the distance calculating means (34) is adapted to perform, in a component-wise hierarchical manner, the distance calculation between respective components constituting partial vectors (f1, g1, f2, g2) in order from the partial vector (f1, g1) of the uppermost component order, andthreshold value comparing means (35) which is adapted to compare an integrated value of distances calculated incrementally for hierarchically higher-order components of the two transformed vectors (f', g',) by the distance calculating means (34) with a threshold value (S) set in advance,a control means which is adapted to control the distance calculation in accordance with a result by the threshold value comparing means (34), andoutput means which is adapted to output, as the similarity, the integrated value of distances calculated up to the last components of the two transformed feature vectors (f', g'),wherein the control means is operative so that in the case where integrated value of distances calculated up to a certain component order is above the threshold value as the result of comparison by the threshold comparing means (35), a control is performed so as to truncate the distance calculation, and in the case where the integrated value of distances calculated up to a certain component order is below the threshold value the distance calculation is performed between the next higher-order components,and wherein the hierarchical distance calculating means (34) is operative so that, in a first step, only the partial vector (g1) of the uppermost component order of the plurality of partial vectors (g1, g2) recorded in the recording means is retrieved and the distance calculation is performed between respective components constituting the partial vectors (f1, g1) of the uppermost component order in a component-wise hierarchical manner, and wherein only in the case where the integrated value of calculated distances calculated between all components constituting the partial vectors (f1, g1) of the uppermost component order is below the threshold value (S), in a second step the partial vector (g2) of the next lower component order of the plurality --> of partial vectors (g1, g2) of the transformed registered feature vector (g') recorded in the recording means (33) is retrieved and the distance calculation between respective components constituting partial vectors (f2, g2) of one lower component order is performed.
  12. c-en-01-0012
    A program for allowing a computer to execute similarity calculation processing for determining similarity between two feature vectors (f, g,), a registered vector (g) and an input vector (f), being representative of an acoustic signal or a video signal, the program comprising:a transform step (S41, S52) in which a predetermined transform operation is implemented to the two feature vectors (f, g),a division step (S41, S52) in which the two transformed feature vectors (f', g') are divided component-wise into a plurality of partial vectors (f1, g1, f2, g2),a recording step (S42, S43) in which the plurality of partial vectors (g1, g2) constituting the transformed registered feature vector (g') are recorded,a hierarchical distance calculation step (S53, S54, S57, S58, S60, S63, S64) in which the distance between the two feature vectors (f', g') transformed at the transform step is calculated in a predetermined order based on the predetermined transform operation (S41. S52), wherein the distance calculation is performed between respective components constituting partial vectors (f1, g1, f2, g2) in a component-wise hierarchical manner in order from the partial vector (f1, g1) of the uppermost component order,a threshold value comparison step (S55, S61) in which an integrated value of distances calculated incrementally for hierarchically higher-order components (i) of the two transformed feature vectors is compared with a threshold value (S) set in advance,a control step (S55, S56, S57, 558. S61, S62, S63, S64) in which distance calculation is controlled in accordance with a result of the threshold value comparison at the threshold value comparison step (S55, S61), andan output step (S65) in which, as the similarity, the integrated value of the calculated distances up to the last components (i) of the two transformed feature vectors (f', g') is outputted,wherein, at the control step (S55, S56, S57, S58, S61, S62, S63, S64), control is conducted such that the distance calculation is truncated in the case where the integrated value of distances calculated up to a certain component order is greater or equal to the threshold value (S) and the distance calculation between next higher-order --> components is performed in the case that the integrated value of distances calculated up to a certain component order is below the threshold value,and wherein distance calculation is performed such that, in a first step, only the partial vector (g1) of the uppermost component order of the plurality of partial vectors (g1, g2) recorded in the recording step is retrieved and the distance calculation is performed between respective components constituting the partial vectors (f1, g1) of the uppermost component order in a component-wise hierarchical manner, and wherein only in the case where the integrated value of calculated distances between all components constituting the partial vectors (f1, g1) of the uppermost component order is below the threshold value, in a second step the partial vector (g2) of the next lower component order of the plurality of partial vectors (g1, g2) of the transformed registered feature vector (g') recorded in the recording step (S42, S43) is retrieved and the distance calculation between respective components constituting partial vectors (f2, g2) of the next lower component order is performed.
  13. c-en-01-0013
    A computer readable medium adapted so that a program for allowing a computer to execute similarity calculation processing which determines similarity between two feature vectors (f, g), a registered vector (g) and an input vector (f), being representative of an acoustic signal or a video signal is recorded, the program including:a transform step (S41, S52) in which a predetermined transform operation is implemented to the two feature vectors (f, g)a division step (S41) in which the two transformed feature vectors (f', g') are divided component-wise into a plurality of partial vectors (f1, g1, f2, g2),a recording step (S42, S43) in which the plurality of partial vectors (g1, g2) constituting the transformed registered feature vector (g') are recorded,a hierarchical distance calculation step ( S53, S54, S57, S58, S60, S63, S64) in which the distance calculation between the two feature vectors (f', g') transformed at the transform step is calculated in a predetermined order based on the predetermined transform operation (S41, S52), wherein the distance calculation is performed between respective components constituting partial vectors (f1, g1, f2, g2) in a component-wise hierarchical manner in order from the partial vector (f1, g1) of the uppermost component order,a threshold value comparison step (S55, S61) in which an integrated value of distances calculated incrementally for hierarchically higher-order components (i) of the two transformed feature vectors (f', g') is compared with a threshold value (S) set in advance, -->a control step (S55, S56, S57, S58, S61, S62, S63, S64) in which distance calculation is controlled in accordance with a result of the threshold value comparison at the threshold value comparison step (S55, S61), andan output step (S65), in which, as the similarity, the integrated value of the calculated distances up to the last components (i) of the two transformed feature vectors (f', g') is outputted,wherein, at the control step (S55, S56, S57, S58, S61, S62, S63, S64), control is conducted such that the distance calculation is truncated in the case where the integrated value of distances calculated up to a certain component order is greater or equal to the threshold value (S) and the distance calculation between next higher-order components is performed in the case that the integrated value of distances calculated up to a certain component order is below the threshold value,and wherein distance calculation is performed such that, in a first step, only the partial vector (g1) of the uppermost component order of the plurality of partial vectors (g1, g2) recorded in the recording step is retrieved and the distance calculation is performed between respective components constituting the partial vectors (f1, g1) of the uppermost component order in a component-wise hierarchical manner, and wherein only in the case where the integrated value of calculated distances between all components constituting the partial vectors (f1, g1) of the uppermost component order is below the threshold value (S), in a second step the partial vector (g2) of the next lower component order of the plurality of partial vectors (g1, g2) of the transformed registered feature vector (g') recorded in the recording step (S42, S43) is retrieved and the distance calculation between respective components constituting partial vectors (f2, g2) of the next lower component order is performed.
Independent claims13