Techniques for video retrieval based on HMM similarity

• US 7,308,443 B1
• Filed: 12/23/2004
• Issued: 12/11/2007
• Est. Priority Date: 12/23/2004
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Wolff, Gregory J., Hull, Jonathan J., Lee, Dar-Shyang
• Primary Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US11/021,717
• Time in Patent Office: 1,083 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 704/252, 704/256, 704/256.1, 704/256.2, 704 1- 9, 704/255, 704/256.3, 704/256.4, 704/256.5, 382/106, 382/305, 382228-230, 710/200, 710/220, 710/240, 715503-510
• US Class Current: 1/1
• CPC Class Codes: G06F 16/7847 using low-level visual features of the video content
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A query is received. The query may be an object containing temporal information. A query model including static and temporal components is then determined for the object. A weighting for static and temporal components is also determined. The query model is then compared with one or more search models. The search models also include static and temporal components. Search results are then determined based on the comparison. In one embodiment, the comparison may compare the static and temporal components of the query model and the search model. A weighting of the differences between the static and temporal components may be used to determine the ranking for the search results.

Claims

1. A method for searching objects using Hidden Markov Models (HMMs), the method comprising:

receiving a query for a query object containing temporal information;

constructing a query HMM for the query object, the query HMM including at least one of static and temporal components;

determining weighting information for the components in the query HMM;

comparing the query HMM with one or more search HMMs using the weighting information, wherein the comparison includes determining static difference values for the static components of the query HMM and the static components for a search HMM in the one or more search HMMs and determining temporal difference values for the temporal components of the query HMM and the temporal components for a search HMM in the one or more the search HMMs;

generating a ranking score for each of the one or more search HMMs based on the comparing step; and

presenting a ranked list of search results to a user based on the ranking score, whereby a user can access an object corresponding to at least one of the search HMMs likely to have content similar to content of the query object.

2. The method of claim 1, wherein the search results comprise one or more objects containing temporal information.

3. The method of claim 1, wherein the one or more search HMMs are generated based on the weighting information.

4. The method of claim 1, wherein comparing the one or more search HMMs with the query HMM comprises:

determining difference values between features in the query HMM and each search HMM in the one or more search HMMs.

5. The method of claim 4, further comprising determining weighted difference values using the weighting information and the difference values.

6. The method of claim 5, further comprising determining a total difference value based on the weighted difference values.

7. The method of claim 6, wherein determining the search results comprises ranking the one or more search HMMs based on their total difference values.

8. The method of claim 1, further comprising storing search HMMs in a database prior to receiving the query.

9. The method of claim 8, further comprising generating the search HMMs.

10. The method of claim 1, further comprising automatically generating the one or more search HMMs in response to receiving the query.

11. The method of claim 10, wherein the one or more search HMMs are generated based on the weighting information.

12. A method for searching objects containing temporal information, the method comprising:

receiving a query for a query object containing temporal information;

generating a query model for the query, the query model including query model static components and query model temporal components;

determining weighting information for the query model static components and query model temporal components;

comparing the query model with one or more search models for search objects containing temporal information using the weighting information, the one or more search models including search model static components and search model temporal components, wherein the comparison includes comparing the query model static components and query model temporal components with the search model static components and query model temporal components for each search model in the one or more search models; and

presenting a list of search results to a user based on the comparing step, whereby a user can access a search object corresponding to at least one of the search HMMs likely to have content similar to content of the query object.

13. The method of claim 12, wherein generating the query model comprises generating the query model based on the object containing temporal information specified.

14. The method of claim 12, wherein generating the query model comprises retrieving a query model stored for an object containing temporal information.

15. The method of claim 12, further comprising storing the one or more search models in a database prior to receiving the query.

16. The method of claim 15, further comprising generating the search models based on the search objects containing temporal information.

17. The method of claim 12, further comprising automatically generating the one or more search models in response to receiving the query.

18. The method of claim 17, wherein the one or more search models are generated based on the weighting information.

19. The method of claim 12, further comprising:

determining weighted static difference values using the weighting information; and

determining weighted temporal difference values using the weighting information.

20. The method of claim 19, further comprising determining a total difference value based on the weighted static difference values and the weighted temporal difference values.

21. The method of claim 20, wherein determining the search results comprises ranking the one or more search models based on their total difference values.

22. The method of claim 12, wherein the query model and one or more search models comprise HMMs.

23. A data processing system for searching objects using Hidden Markov Models (HMMs), the data processing system including a processor and a memory configured to store a plurality of instructions that, when executed by the processor, direct the data processing system to perform steps comprising:

receiving a query for a query object containing temporal information;

constructing a query HMM for the query object, the query HMM including at least one of static and temporal components;

determining weighting information for the components in the query HMM;

comparing the query HMM with one or more search HMMs using the weighting information, wherein the comparison includes determining static difference values for the static components of the query HMM and the static components for a search HMM in the one or more search HMMs and determining temporal difference values for the temporal components of the query HMM and the temporal components for a search HMM in the one or more the search HMMs;

generating a ranking score for each of the one or more search HMMs based on the comparing step; and

presenting a ranked list of search results to a user based on the ranking score, whereby a user can access an object corresponding to at least one of the search HMMs likely to have content similar to content of the query object.

24. The data processing system of claim 23, wherein the search results comprise one or more objects containing temporal information.

25. The data processing system of claim 23, wherein the one or more search HMMs are generated based on the weighting information.

26. The data processing system of claim 23, further comprising automatically generating the one or more search HMMs in response to receiving the query.

27. A data processing system for searching objects containing temporal information, the data processing system including a processor and a memory configured to store a plurality of instructions that, when executed by the processor, direct the data processing system to perform steps comprising:

receiving a query for a query object containing temporal information;

generating a query model for the query, the query model including query model static components and query model temporal components;

determining weighting information for the query model static components and query model temporal components;

comparing the query model with one or more search models for search objects containing temporal information using the weighting information, the one or more search models including search model static components and search model temporal components, wherein the comparison includes comparing the query model static components and query model temporal components with the search model static components and query model temporal components for each search model in the one or more search models; and

presenting a list of search results to a user based on the comparing step, whereby a user can access a search object corresponding to at least one of the search HMMs likely to have content similar to content of the query object.

28. The data processing system of claim 27, further comprising automatically generating the one or more search models in response to receiving the query.

29. The data processing system of claim 28, wherein the one or more search models are generated based on the weighting information.

30. The data processing system of claim 27, wherein the query model and one or more search models comprise HMMs.