Digital media recognition apparatus and methods

• US 7,474,759 B2
• Filed: 11/13/2001
• Issued: 01/06/2009
• Est. Priority Date: 11/13/2000
• Status: Active Grant

• Current Assignee: Syte - Visual Conception, Ltd.
• Original Assignee: Pixel Velocity Incorporated
• Inventors: Sternberg, Stanley, Voiles, Thomas, Dargel, William, Lennington, John W
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US10/416,560
• Publication Number:
  US 20040133927A1
• Time in Patent Office: 2,611 Days
• Field of Search: 382/100, 382/181, 382/293, 382/294, 382/295, 382/275, 382/276, 707/6
• US Class Current: 382/100
• CPC Class Codes: G06F 16/583 using metadata automatically derived from the content
• CPC Class Codes: G06F 16/7328 Query by example, e.g. a complete video frame or video sequence graphical querying G06F16/7335
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 20/00 Scenes; Scene-specific elements control of digital cameras H04N23/60
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44

Abstract

Physical objects, including still and moving images, sound/audio and text are transformed into more compact forms for identification and other purposes using a method unrelated to existing image-matching systems which rely on feature extraction. An auxiliary construct, preferably a warp grid, is associated with an object, and a series of transformations are imposed to generate a unique visual key for identification, comparisons, and other operations. Search methods are also disclosed for matching an unknown image to one previously represented in a visual key database. Broadly, a preferred search method sequentially examines candidate database images for their closeness of match in a sequential order determined by their a priori match probability. Thus, the most likely match candidate is examined first, the next most likely second, and so forth. With respect to the recognition of video sequences and other information streams, inventive holotropic stream recognition principles are deployed, wherein the statistics of the spatial distribution of warp grid points is used to generate index keys. The invention is applicable to various fields of endeavor, including governmental, scientific, industrial, commercial, and recreational object identification and information retrieval. Extensions of the technology are also disclosed to achieve a uniform distribution of objects over the database search, a consideration which is central to scalability. In particular, a generalized method has been developed based on reticle projection, which greatly enhances the uniformity of object distributions in the collected data Thus, whereas statistical criteria are used with respect to particular embodiments in transforming a construct associated with an image, audio, text or other representation, a reticle projection may alternatively be used in attribute transformation according to alternative embodiments of the invention.

Claims

1. A method of converting a digital media object into a compact form for comparison and other purposes, comprising the steps of:

a) providing a digital media object;

b) associating an auxiliary construct with the object, wherein the auxiliary construct is a grid of points, each having an initial position; and

c) transforming the construct using one or more attributes of the object to generate a unique key representative of the object, wherein the transformation warps the grid, thereby moving some or all of the points to different positions.

2. The method of claim 1, wherein the object is a still picture.

3. The method of claim 1, wherein the object is a sequence of pictures.

4. The method of claim 3, wherein the sequence comprises motion video.

5. The method of claim 1, wherein the object is derived from a waveform.

6. The method of claim 1, wherein the object comprises text.

8. The method of claim 1, wherein the key is based on the initial and different positions of the points.

9. The method of claim 1, wherein the key uses the vector sum of the movements made by each point during the transformation thereof for comparison.

10. The method of claim 1, wherein the object is a still or motion picture, and the attributes include image size, shape, position, orientation, composition, color, or intensity.

11. The method of claim 1, wherein the transformation is performed using a reticle projection.

12. The method of claim 1, further including the step of storing the key in a database.

13. The method of claim 1, further including the step of storing supplemental information related to the object in the database.

14. The method of claim 13, wherein the supplemental information is content-related, contextual, or visually representational of the object.

15. The method of claim 1, further including the steps of:

providing a second object;

performing steps b) and c) on the second object to generate a second key; and

comparing the second key with the key in the database to determine if the objects are similar.

16. The method of claim 1, further including the steps of:

performing steps b) and c) on a plurality of objects to generate a key for each;

storing the keys in a database;

providing a search object;

performing steps b) and c) on the search object to generate a search key; and

comparing the search key to the keys stored in the database to determine if the search object is among the plurality.

17. The method of claim 16, further including the steps of:

sequentially ordering the keys in the database in accordance with a predetermined match probability prior to the step of comparing the search key.

18. The method of claim 1, including the step of deriving the object from a book, periodical or other printed mailer.

19. The method of claim 14, wherein the object is an image is derived using a camera, scanner, or other apparatus operative to convert an image into electronic form.

20. The method of claim 1, where the object is derived from another database, software application, hyperlink or web page.

21. The method of claim 1, further including the steps of:

providing the object in the form of sequential entities; and

analyzing the statistics of the construct transformations associated with the entities to generate the keys.

22. The method of claim 1, wherein the object may not be reconstructed from the key.

23. The method of claim 1, further comprising accelerating the determination of warp grid equilibrium by adjusting a warp rate of the transformation.

24. The method of claim 1, further comprising repeating the transformation until the warped grid achieves equilibrium and remains essentially unchanged with respect to the previous iteration.

25. The method of claim 1, further comprising repeating the transformation until the total offset magnitude of an equilibrium configuration of the warped grid approaches a value substantially equal to zero.

26. The method of claim 1, wherein the object is derived from an electronic waveform.

7. A method of converting a digital media object into a compact form for comparison and other purposes, comprising the steps of:

a) providing a digital media object, wherein the object is derived from a waveform, and wherein the waveform comprises audio;

b) associating an auxiliary construct with the object; and

c) transforming the construct using one or more attributes of the object to generate a unique key representative of the object.

27. The method of claim 7, wherein the auxiliary construct is a grid of points, each having an initial position.

28. The method of claim 7, wherein the object is derived from an electronic waveform.

29. A method of converting a digital media object into a compact form for comparison and other purposes, comprising the steps of:

a) providing a digital media object;

b) associating an auxiliary construct with the object;

c) transforming the construct using one or more attributes of the object to generate a unique key representative of the object, wherein the transforming includes warping the construct; and

d) repeating the transformation for a fixed number of iterations, wherein the fixed number of iterations is determined from experiments on similar media objects.

30. The method of claim 29, wherein the object is derived from an electronic waveform.

31. A method of converting a digital media object into a compact form for comparison and other purposes, comprising the steps of:

a) providing a digital media object;

b) associating an auxiliary construct with the object;

c) transforming the construct using one or more attributes of the object to generate a unique key representative of the object, wherein the transforming includes warping the construct; and

d) repeating the transformation until the warped construct achieves equilibrium and remains essentially unchanged with respect to the previous iteration.

32. The method of claim 31, wherein the object is derived from an electronic waveform.

33. A method of converting a digital media object into a compact form for comparison and other purposes, comprising the steps of:

a) providing a digital media object;

b) associating an auxiliary construct with the object;

c) transforming the construct using one or more attributes of the object to generate a unique key representative of the object, wherein the transforming includes warping the construct; and

d) repeating the transformation until the total offset magnitude of an equilibrium configuration of the warped construct approaches a value substantially equal to zero.

34. The method of claim 33, wherein the object is derived from an electronic waveform.

35. A method of converting a digital media object into a compact form for comparison and other purposes, comprising the steps of:

a) providing a digital media object;

b) associating an auxiliary construct with the object;

c) transforming the construct using one or more attributes of the object to generate a unique key representative of the object, wherein the transforming includes warping the construct, and wherein the key uses a vector sum of a movement of elements of the auxiliary construct during the transformation thereof for comparison.

36. The method of claim 35, wherein the object is derived from an electronic waveform.