Robust recognizer of perceptually similar content

• US 7,266,244 B2
• Filed: 07/16/2004
• Issued: 09/04/2007
• Est. Priority Date: 04/24/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mihcak, M. Kivanc, Venkatesan, Ramarathnam
• Primary Examiner(s): LAROSE, COLIN M
• Application Number:
  US10/893,771
• Publication Number:
  US 20050022004A1
• Time in Patent Office: 1,145 Days
• Field of Search: 382/181, 382/190, 382/201, 382/206, 382/207, 382/224
• US Class Current: 382/181
• CPC Class Codes: G06F 18/00 Pattern recognition

Abstract

An implementation of a technology is described herein for recognizing the perceptual similarity of the content of digital goods. At least one implementation, described herein, introduces a new hashing technique. More particularly, this hashing technique produces hash values for digital goods that are proximally near each other, when the digital goods contain perceptually similar content. In other words, if the content of digital goods are perceptually similar, then their hash values are, likewise, similar. The hash values are proximally near each other. This is unlike conventional hashing techniques where the hash values of goods with perceptually similar content are far apart with high probability in some distance sense (e.g., Hamming). This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims.

Claims

1. A method for hashing a digital signal, the method comprising:

transforming a digital signal into a digital signal transform;

quantizing the digital signal transform;

geometric-region-growing the digital signal transform;

generating a recognition value of the digital signal.

2. A method as recited in claim 1 further comprising:

pseudorandomly segmenting the digital signal into one or more segments;

for one or more of the segments, repeating the transforming, the quantizing, and the geometric-region-growing, wherein these repeated tasks are performed on a segment rather than the entire signal;

combining one or more of the segments.

3. A method as recited in claim 1, wherein the transforming comprises a discrete wavelet transformation of the digital signal.

4. A method as recited in claim 1, wherein the transforming comprises finding the DC subband.

5. A method as recited in claim 1, wherein the quantizing comprises a multi-level quantization of the digital signal transform.

6. A method as recited in claim 1, wherein the recognition value is a hash value.

7. A method as recited in claim 1, wherein the geometric-region-growing comprises iterative geometric conversion.

8. A method as recited in claim 1, wherein the geometric-region-growing comprises self-correcting iterative filtering.

9. A method as recited in claim 1, wherein the geometric-region-growing comprises accentuating geometrically strong components of the signal while de-emphasizing the geometrically weak components of the signal.

10. A method as recited in claim 1, wherein the geometric-region-growing comprises order-statistics filtering, local smoothing, and quantizing.

11. A method as recited in claim 10, wherein the local smoothing comprises multi-dimensional linear shift-invariant filtering.

12. One or more computer-readable media having computer-executable instructions that, when executed by a computer, performs the method as recited in claim 1.

13. A computer comprising one or more computer-readable media having computer-executable instructions that, when executed by the computer, perform the method as recited in claim 1.

14. A method for hashing a digital signal, the method comprising:

transforming a digital signal into a digital signal transform;

quantizing the digital signal transform;

self-correcting iterative filtering of the digital signal transform;

generating a recognition value of the digital signal.

15. A method as recited in claim 14 further comprising:

pseudorandomly segmenting the digital signal into one or more segments;

for one or more of the segments, repeating the transforming, the quantizing, and the self-correcting iterative filtering, wherein these repeated tasks are performed on a segment rather than the entire signal;

combining one or more of the segments.

16. A method as recited in claim 14, wherein the quantizing comprises a multi-level quantization of the digital signal transform.

17. A method as recited in claim 14, wherein the recognition value is a hash value.

18. A method as recited in claim 14, wherein the self-correcting iterative filtering comprises accentuating geometrically strong components of the signal while de-emphasizing the geometrically weak components of the signal.

19. A method as recited in claim 14, wherein the self-correcting iterative filtering corn prises order-statistics filtering, local smoothing, and quantizing.

20. A computer comprising one or more computer-readable media having computer-executable instructions that, when executed by the computer, perform the method as recited in claim 14.

21. A method for hashing a digital signal, the method comprising:

pseudorandomly segmenting a digital signal into one or more segments;

for one or more of the segments;

transforming a segment into a segment transform;

quantizing the segment transform;

self-correcting iterative filtering of the segment transform;

combining one or more of the segments;

generating a recognition value of the digital signal.

22. A method as recited in claim 21, wherein the recognition value is a hash value.

23. One or more computer-readable media having computer-executable instructions that, when executed by a computer, performs the method as recited in claim 21.

24. A computer comprising one or more computer-readable media having computer-executable instructions that, when executed by the computer, perform the method as recited in claim 21.

25. A system for digital signal similarity recognition, the system comprising:

a transformer configured to transform a digital signal into a signal transform;

a quantizer configured to quantitize the signal transform;

a iterative geometric converter configured to convert the signal transform into a representation of the signal that emphasizes geometrically strong components of the signal while de-emphasizing geometrically weak components of the signal.

26. A system as recited in claim 25 further comprising:

a segmenter configured to pseudorandomly segment the digital signal into one or more segments;

a combiner configured to combine the output of the converter for one or more of the segments.

27. A system for digital signal similarity recognition, the system comprising:

a segmenter configured to pseudorandomly segment the digital signal into one or more of the segments;

a transformer configured to transform a segment into a segment transform;

a quantizer configured to quantitize the segment transform;

a iterative geometric converter configured to convert the segment transform into a representation of the segment that emphasizes geometrically strong components of the segment while de-emphasizing geometrically weak components of the segment;

a combiner configured to combine the output of the converter for one or more of the segments.

28. One or more computer-readable media having computer-executable instructions that, when executed by a computer, performs the method comprising:

transforming a digital signal into a digital signal transform;

quantizing the digital signal transform;

self-correcting iterative filteulng of the digital signal transform;

generating a recognition vaiue of the digital signal.