Method and apparatus for multi-resolution image searching

• US 5,933,546 A
• Filed: 05/06/1996
• Issued: 08/03/1999
• Est. Priority Date: 05/06/1996
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Stone, Harold S.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US08/643,691
• Time in Patent Office: 1,184 Days
• Field of Search: 382/276, 382/277, 382/278, 382/279, 382/280, 382/209, 382/210, 382/218, 382/219, 382/206, 382/207
• US Class Current: 382/278
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06T 3/4084 in the transform domain, e.g. fast Fourier transform [FFT] domain scaling
• CPC Class Codes: G06V 10/431 Frequency domain transformation; Autocorrelation
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

A multiresolution method and apparatus for searching of a database of images where the search is performed on compressed images, without first decompressing them. The method searches the database of compressed images first at a low resolution to obtain the relative quality of a match between a search template and a candidate image. If the match is below a particular threshold, the search is terminated without committing any further computational resources to the search. Conversely, if the match is above a particular threshold, the method enhances the resolution of the candidate image and then performs another match. As long as the relative quality of the match is above the particular threshold, the resolution of the candidate image is successively enhanced, until a match determination is made at a full resolution of the candidate image.

Claims

1. A content-based image search method for determining whether a candidate image matches a pattern template, the method comprising the steps of:

(a) transforming the pattern template into a wavelet pattern;

(b) transforming the candidate image into a wavelet candidate image at a first resolution;

(c) correlating the wavelet candidate image with the wavelet pattern in the Fourier domain and at the first resolution to produce a first-resolution correlation comprising a plurality of values;

(d) thresholding the first-resolution correlation by comparing each first-resolution correlation value to a predetermined first-resolution threshold value to determine whether any first-resolution correlation value meets or exceeds the first-resolution threshold value and, if so, proceeding with steps (e) through (f);

(e) correlating the wavelet candidate image with the wavelet pattern at a second resolution, utilizing at least a portion of calculations performed in the first-resolution correlation of step (c), to produce a second-resolution correlation comprising a plurality of values, the second resolution being finer than the first resolution; and

(f) thresholding the second-resolution correlation by comparing each second-resolution correlation value to a predetermined second-resolution threshold value to determine whether any second-resolution correlation value meets or exceeds the second-resolution threshold value.

3. The method of claim 1, further comprising the step of:

(g) determining that a suitable match exists between the candidate image and the pattern template if any second-resolution correlation value meets or exceeds the second-resolution threshold value.

4. The method of claim 3, wherein the second-resolution correlation is fully correlated.

5. The method of claim 1, wherein the first-resolution threshold value is equal to the second-resolution threshold value.

6. The method of claim 1, wherein the first-resolution threshold value is not equal to the second-resolution threshold value.

7. The method of claim 1, further comprising the steps of:

(g) correlating the wavelet candidate image with the wavelet pattern at a third resolution, utilizing at least a portion of calculations performed in the second-resolution correlation of step (e), to produce a third-resolution correlation comprising a plurality of values, the third resolution being finer than the second resolution; and

(h) thresholding the third-resolution correlation by comparing each third-resolution correlation value to a predetermined third-resolution threshold value to determine whether any second-resolution correlation value meets or exceeds the third-resolution threshold value.

8. The method of claim 7, further comprising the step of:

(i) determining that a suitable match exists between the candidate image and the pattern template if any third-resolution correlation value meets or exceeds the third-resolution threshold value.

9. The method of claim 8, wherein the final-resolution correlation is fully correlated.

10. The method of claim 7, wherein the first-resolution threshold value, the second-resolution threshold value, and the third-resolution threshold value are all equal.

11. The method of claim 7, wherein the first-resolution threshold value, the second-resolution threshold value, and the third-resolution threshold value are not all equal.

12. The method of claim 1, further comprising the steps of:

(g) correlating the wavelet candidate image with the wavelet pattern at a current resolution that is a finer resolution than the resolution of the previous correlation, utilizing at least a portion of calculations performed in the previous correlation, to produce a current-resolution correlation comprising a plurality of values;

(h) thresholding the current-resolution correlation by comparing each current-resolution correlation value to a predetermined current-resolution threshold value to determine whether any current-resolution correlation value meets or exceeds the current-resolution threshold value;

(i) repeating steps (g) and (h) at successively finer resolutions so long as it is determined that any current-resolution correlation value meets or exceeds the current-resolution threshold value for that correlation in step (h) until a desired final resolution is attained; and

(j) determining that a suitable match exists between the candidate image and the pattern template if any final-resolution correlation value meets or exceeds a predetermined final-resolution threshold value.

13. The method of claim 12, wherein the final-resolution correlation is fully correlated.

14. The method of claim 12, wherein the first-resolution threshold value, the second-resolution threshold value, each of the current-resolution threshold values and the final-resolution threshold value are all equal.

15. The method of claim 12, wherein the first-resolution threshold value, the second-resolution threshold value, each of the current-resolution threshold values and the final-resolution threshold value arc not all equal.

2. An apparatus for performing a content-based image search for determining whether a candidate image matches a pattern template, the apparatus comprising:

(a) means for transforming the pattern template into a wavelet pattern template;

(b) means for transforming the candidate image into a wavelet candidate image at a first resolution;

(c) means for correlating the wavelet candidate image with the wavelet pattern in the Fourier domain and at the first resolution to produce a first-resolution correlation comprising a plurality of values;

(d) means for thresholding the first-resolution correlation by comparing each first-resolution correlation value to a predetermined first-resolution threshold value to determine whether any first-resolution correlation value meets or exceeds the first-resolution threshold value;

(e) means for correlating the wavelet candidate image with the wavelet pattern at a second resolution, utilizing at least a portion of calculations performed in the first-resolution correlation by the means for correlating at the first resolution (c), to produce a second-resolution correlation comprising a plurality of values, the second resolution being finer than the first resolution, said means for correlating (e) being responsive to the means for thresholding (d) and being activated only if the means for thresholding (d) determines that any first-resolution correlation value meets or exceeds the first-resolution threshold value; and

(f) means for thresholding the second-resolution correlation by comparing each second-resolution correlation value to a predetermined second-resolution threshold value to determine whether any second-resolution correlation value meets or exceeds the second-resolution threshold value.

16. The apparatus of claim 2, further comprising:

(g) means for determining that a suitable match exists between the candidate image and the pattern template if any second-resolution correlation value meets or exceeds the second-resolution threshold value.

17. The apparatus of claim 16, wherein the second-resolution correlation is fully correlated.

18. The apparatus of claim 2, wherein the first-resolution threshold value is equal to the second-resolution threshold value.

19. The apparatus of claim 2, wherein the first-resolution threshold value is not equal to the second-resolution threshold value.

20. The apparatus of claim 2, further comprising:

(g) means for correlating the wavelet candidate image with the wavelet pattern at a third resolution, utilizing at least a portion of calculations performed in the second-resolution correlation by the means for correlating at the second resolution (e), to produce a third-resolution correlation comprising a plurality of values, the third resolution being finer than the second resolution; and

(h) means for thresholding the third-resolution correlation by comparing each third-resolution correlation value to a predetermined threshold value to determine whether any second-resolution correlation value meets or exceeds the third-resolution threshold value.

21. The apparatus of claim 20, further comprising:

(i) means for determining that a suitable match exists between the candidate image and the pattern template if any third-resolution correlation value meets or exceeds the third-resolution threshold value.

22. The apparatus of claim 21, wherein the final-resolution correlation is fully correlated.

23. The apparatus of claim 20, wherein the first-resolution threshold value, the second-resolution threshold value, and the third-resolution threshold value are all equal.

24. The apparatus of claim 20, wherein the first-resolution threshold value, the second-resolution threshold value, and the third-resolution threshold value are not all equal.

25. The apparatus of claim 2, further comprising:

(g) means for correlating the wavelet candidate image with the wavelet pattern at a current resolution that is a finer resolution than that of the previous correlation, utilizing at least a portion of calculations performed in the previous correlation, to produce a current-resolution correlation comprising a plurality of values;

(h) means for thresholding the current-resolution correlation by comparing each current-resolution correlation value to a predetermined current-resolution threshold value to determine whether any finer-resolution correlation value meets or exceeds the current-resolution threshold value;

(i) means for repeating the processing performed by the means for correlating (g) and the means for thresholding (h) at successively finer resolutions so long as it is determined that any current-resolution correlation value meets or exceeds the current-resolution threshold value for that correlation as determined by the means for thresholding (h) until a desired final resolution is attained; and

(j) means for determining that a suitable match exists between the candidate image and the pattern template if any final-resolution correlation value meets or exceeds a predetermined final-resolution threshold value.

26. The apparatus of claim 25, wherein the final-resolution correlation is fully correlated.

27. The apparatus of claim 25, wherein the first-resolution threshold value, the second-resolution threshold value, each of the current-resolution threshold values and the final-resolution threshold value are all equal.

28. The apparatus of claim 25, wherein the first-resolution threshold value, the second-resolution threshold value, each of the current-resolution threshold values and the final-resolution threshold value are not all equal.

29. A content-based image search method for determining whether a candidate image matches a pattern template, the method comprising the steps of:

(a) transforming the pattern template into a wavelet pattern comprising a plurality of pattern sub-bands at a first resolution;

(b) transforming the candidate image into a wavelet image comprising a plurality of image sub-bands at the first resolution;

(c) correlating the first-resolution wavelet image and the wavelet pattern, including the sub-steps of;

(c1) transforming all pattern sub-bands of the first-resolution wavelet pattern into the Fourier domain to produce a Fourier-transformed first-resolution pattern;

(c2) transforming all image sub-bands of the first-resolution wavelet image into the Fourier domain to produce a Fourier-transformed first-resolution image;

(c3) correlating the Fourier-transformed first-resolution image and the Fourier-transformed first-resolution pattern on a sub-band to sub-band basis in the Fourier domain to produce a first-resolution Fourier-domain sub-band correlation for each sub-band;

(c4) summing the first-resolution Fourier domain sub-band correlations to produce a first-resolution Fourier domain correlation;

(c5) inverting the first-resolution Fourier domain correlation into the pixel domain to produce a first-resolution pixel domain correlation comprising a plurality of correlation values, each correlation value being associated with a pixel position;

(c6) comparing the correlation value of the first-resolution pixel domain correlation at each pixel position with a first predetermined threshold to determine which pixel positions exceed the first threshold, thereby indicating the pixel positions of a potential match;

(d) if at least one potential match is indicated in step (c6), correlating again at a current resolution which is a finer resolution than the previous resolution, including the sub-steps of;

(d1a) performing a one-step wavelet inversion of the Fourier transforms of the previous-resolution pattern sub-bands to form an intermediate Fourier-transformed current-resolution pattern;

(d1b) butterfly transforming the intermediate Fourier-transformed current-resolution pattern to create a full Fourier-transformed current-resolution pattern;

(d2a) performing a one-step wavelet inversion of the Fourier transforms of the previous-resolution sub-bands of the image to form an intermediate Fourier-transformed current-resolution image;

(d2b) butterfly transforming the intermediate Fourier-transformed current-resolution candidate image to create a full Fourier-transformed current-resolution candidate image;

(d3) correlating the full Fourier-transformed current-resolution pattern and the full Fourier-transformed current-resolution image on a sub-band to sub-band basis in the Fourier domain to produce a current-resolution Fourier-domain sub-band correlation for each sub-band;

(d4) if the current resolution is not a final desired resolution, summing the current-resolution Fourier domain sub-band correlations to produce a current-resolution Fourier domain correlation;

(d5) inverting the current-resolution Fourier domain correlation into the pixel domain to produce a current-resolution pixel domain correlation comprising a plurality of correlation values, each correlation value being associated with a pixel position;

(d6) comparing the correlation value of the current-resolution pixel domain correlation at each pixel position with a current-resolution predetermined threshold to determine which pixel positions exceed the current-resolution threshold, thereby indicating the pixel positions of a potential match; and

(e) repeating step (d), including the sub-steps (d1a) through (d6), at successively finer resolutions so long as at least one potential match is indicated in step (d6) and until the current resolution is the desired final resolution, wherein the comparing step (d6) at the final resolution indicates the pixel positions of any match between the candidate image and the pattern template.

30. The method of claim 29, wherein the first-resolution threshold value, and each of the current-resolution threshold values including the final-resolution threshold value, are all equal.

31. The method of claim 29, wherein the first-resolution threshold value, and each of the current-resolution threshold values including the final-resolution threshold value, are not all equal.

32. A content-based image search apparatus for determining whether a candidate image matches a pattern template, the apparatus comprising:

(a) means for transforming the pattern template into a wavelet pattern comprising a plurality of pattern sub-bands at a first resolution;

(b) means for transforming the candidate image into a wavelet image comprising a plurality of image sub-bands at the first resolution;

(c) means for correlating the first-resolution wavelet image and the wavelet pattern, comprising;

(c1) means for transforming all pattern sub-bands of the first-resolution wavelet pattern into the Fourier domain to produce a Fourier-transformed first-resolution pattern;

(c2) means for transforming all image sub-bands of the first-resolution wavelet image into the Fourier domain to produce a Fourier-transformed first-resolution image;

(c3) means for correlating the Fourier-transformed first-resolution image and the Fourier-transformed first-resolution pattern on a sub-band to sub-band basis in the Fourier domain to produce a first-resolution Fourier-domain sub-band correlation for each sub-band;

(c4) means for summing the first-resolution Fourier domain sub-band correlations to produce a first-resolution Fourier domain correlation;

(c5) means for inverting the first-resolution Fourier domain correlation into the pixel domain to produce a first-resolution pixel domain correlation comprising a plurality of correlation values, each correlation value being associated with a pixel position;

(c6) means for comparing the correlation value of the first-resolution pixel domain correlation at each pixel position with a first predetermined threshold to determine which pixel positions exceed the first threshold, thereby indicating the pixel positions of a potential match;

(d) means for correlating again at a current resolution which is a finer resolution than the previous resolution, the means for correlating again being responsive to at least one of the means for comparing (c6) and the means for comparing (d6) and being activated only if at least one potential match is indicated by the means for comparing (c6) or the means for comparing (d6) at the previous resolution, comprising;

(d1a) means for performing a one-step wavelet inversion of the Fourier transforms of the previous-resolution pattern sub-bands to form an intermediate Fourier-transformed current-resolution pattern;

(d1b) means for butterfly transforming the intermediate Fourier-transformed current-resolution pattern to create a full Fourier-transformed current-resolution pattern;

(d2a) means for performing a one-step wavelet inversion of the Fourier transforms of the previous-resolution sub-bands of the image to form an intermediate Fourier-transformed current-resolution image;

(d2b) means for butterfly transforming the intermediate Fourier-transformed current-resolution candidate image to create a full Fourier-transformed current-resolution candidate image;

(d3) means for correlating the full Fourier-transformed current-resolution pattern and the full Fourier-transformed current-resolution image on a sub-band to sub-band basis in the Fourier domain to produce a current-resolution Fourier-domain sub-band correlation for each sub-band;

(d4) means for summing the current-resolution Fourier domain sub-band correlations to produce a current-resolution Fourier domain correlation if the current resolution is not a final desired resolution;

(d5) means for inverting the current-resolution Fourier domain correlation into the pixel domain to produce a current-resolution pixel domain correlation comprising a plurality of correlation values, each correlation value being associated with a pixel position;

(d6) means for comparing the correlation value of the current-resolution pixel domain correlation at each pixel position with a current-resolution predetermined threshold to determine which pixel positions exceed the current-resolution threshold, thereby indicating the pixel positions of a potential match; and

(e) means for repeating the processing performed by the means for correlating again (d), including the components (d1a) through (d6), at successively finer resolutions so long as at least one potential match is indicated by the means for comparing (d6) and until the current resolution is the desired final resolution, wherein the means for comparing (d6) at the final resolution indicates the pixel positions of any match between the candidate image and the pattern template.

33. The apparatus of claim 32, wherein the first-resolution threshold value, and each of the current-resolution threshold values including the final-resolution threshold value, are all equal.

34. The apparatus of claim 32, wherein the first-resolution threshold value, and each of the current-resolution threshold values including the final-resolution threshold value, are not all equal.