Method of searching multimedia data

• US 6,795,818 B1
• Filed: 07/03/2000
• Issued: 09/21/2004
• Est. Priority Date: 07/05/1999
• Status: Expired due to Term

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: LG Electronics, Inc. (LG Corporation)
• Inventors: Lee, Jin Soo
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US09/609,393
• Time in Patent Office: 1,541 Days
• Field of Search: 707/3, 707/5, 707/2, 707/10, 382/128, 382/305
• US Class Current: 1/1
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/43 Querying
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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

Abstract

A method of searching multimedia data is disclosed. In the present invention, weights of features in a specific image are automatically learned by grouping images stored in a search system, giving an initial weight to the grouped images to search and classify the images, determining errors from the classified results and re-sorting the error images using automatic feedback.

Claims

1. A method of searching multimedia data comprising:

a1) grouping multimedia data in a database of a search system;

b1) searching for reference multimedia data belonging to a group of k reference multimedia data and sorting the multimedia data obtained by the search, using initial weights of features in the reference group;

c1) feeding back at least one multimedia data depending upon a degree of error determined concurrently among a combination of a plurality of the sorted multimedia data; and

d1) updating said weights of features using said at least one feedback multimedia data.

2. A method of claim 1, wherein in (c1), automatically feeding back said at least one multimedia data.

3. A method of claim 1, further comprising:

e1) searching for reference multimedia data belonging to the group and sorting the multimedia data obtained by the search using updated weights of features; and

f1) repeating (c1) through (e1) until the degree of error in the sorted multimedia data meets a predetermined condition.

4. A method of claim 3, wherein in (c1), said at least one feedback multimedia data is either one of a reference multimedia data ranked below k or a non-reference multimedia data ranked within k.

5. A method of claim 4, wherein in (c1) feeding back a number of multimedia data equivalent to twice a number of reference multimedia data ranked below k.

6. A method of claim 5, wherein in (c1), feeding back less than a number of multimedia data equivalent to twice a number of reference multimedia data ranked below k, if the degree of error obtained (f1) did not decrease by a predetermined condition.

7. A method of claim 6, wherein at least one reference multimedia data and one non-reference multimedia data are fed back.

8. A method of claim 5, wherein the number of the reference multimedia data fed back is reduced to one reference multimedia data and one non-reference multimedia data through (f1).

9. A method of claim 1, wherein in (c1), said at least one feedback multimedia data is either one of a relevant multimedia data or an irrelevant multimedia data.

10. A method of claim 9, wherein in (d1), updating the weights of features proportionally to a similarity between said at least one feedback multimedia data and reference multimedia data, if said at least one feedback multimedia data is a relevant multimedia data;

and updating the weights of features proportionally to a dissimilarity between said at least one feedback multimedia data and reference multimedia data, if said at least one feedback multimedia data is an irrelevant image.

11. A method of claim 9, wherein a relevant multimedia data is a reference multimedia data ranked below k and an irrelevant multimedia data is a non-reference multimedia data ranked within k.

12. A method of claim 11, wherein a reference multimedia data ranked lower below k is selected as a relevant multimedia data if more than one reference multimedia data is ranked below k but less than all reference multimedia data are fed back, and wherein a non-reference multimedia data ranked higher within k is selected as an irrelevant multimedia data if more than one non-reference multimedia data is ranked within k but less than all non-reference multimedia data are fed back.

13. A method of claim 12, wherein a reference multimedia data ranked lower than a predetermined threshold value below k is not selected as a relevant multimedia data.

14. A method of claim 11, wherein a reference multimedia data ranked lower than a predetermined threshold value below k is not fed back.

15. A method of claim of claim 9, wherein the number of the reference multimedia data is reduced if a decrease degree of a current error is lower than a predetermined threshold value.

16. The method of claim 1, wherein said updating comprises:

calculating a relative weight W to update an existing weight of features, wherein the relative weight W is determined as follows;

17. The method of claim 16, wherein the relative weight W comprises one of a type weight Wk, an element weight We and a position weight Wp.

18. The method of claim 17, wherein a resultant relative weight is one of combined with the existing weight, added to the existing weight and modified by a prescribed function to correspond to a cumulative relative weight.

19. A computer software product that includes a medium readable by a processor, the medium having stored thereon:

a global information representing a whole image;

a spatial information representing features included in at least one portion of the image;

a weight information of a feature representing an importance of the feature element, an importance of elements depicted by a feature, and a region of the image including importance information from the spatial information; and

a sequence of instructions which when executed by said processor perform a search for reference multimedia data belonging to a group of k reference multimedia data and sort the multimedia data obtained by the search, using initial weights of features in the reference group and update the weights of features depending upon a degree of error determined among a plurality of the sorted multimedia data.

20. The computer software product of claim 19, wherein said sequence of instructions cause said processor to:

calculate a relative weight W to update an existing weight of features, wherein the relative weight W is determined as follows;

21. The computer software product of claim 20, wherein the relative weight W comprises one of a type weight Wk, an element We and a position weight Wp.

22. The computer software product of claim 21, wherein a resultant relative weight is one of combined with the existing weight, added to the existing weight and modified by a prescribed function to correspond to a cumulative relative weight.

23. A method of searching multimedia data comprising:

a) searching for reference images belonging to a group of k reference images and sorting images obtained by the search, using initial weights of features in the group;

b) feeding back at least one image depending upon a degree of error in a combination of the sorted images of the group of k reference images;

c) updating said weights of features using said at least one feedback image; and

d) re-searching for the reference images belonging to the group and re-sorting the images obtained by the search using updated weights of features.

24. A method of claim 23, wherein each image has a data structure comprising:

a global information representing a whole image;

a spatial information representing features included in at least one portion of the image; and

a weight information of a feature representing an importance of the feature element, an importance of elements depicted by a feature, and a region of the image including important information from the spatial information.

25. A method of claim 24, wherein reference images are grouped into the group of k reference images in advance.

26. A method of claim 23, wherein reference images are grouped into the group of k reference images in advance.

27. A method of claim 24, comprising repeating (b) through (d) until the degree of error in the sorted images meets a predetermined condition.

28. A method of claim 23, comprising grouping images in a database of a search system.

29. A method of searching multimedia data comprising:

a1) grouping multimedia data in a database of a search system;

b1) searching for reference multimedia data belonging to a group of k reference multimedia data and sorting the multimedia data obtained by the search, using initial weights of features in the reference group;

c1) feeding back at least one multimedia data depending upon a degree of error determined among a plurality of the sorted multimedia data;

d1) updating said weights of features using said at least one feedback multimedia data;

e1) searching for reference multimedia data belonging to the group and sorting the multimedia data obtained by the search using updated weights of features; and

f1) repeating (c1) through (e1) until the degree of error in the sorted multimedia data meets a predetermined condition.

30. The method of claim 29, wherein said updating comprises:

calculating a relative weight W to update an existing weight of features, wherein the relative weight W is determined as follows;

31. The method of claim 30, wherein the relative weight W comprises one of a type weight Wk, an element weight We and a position weight Wp.

32. The method of claim 31, wherein the resultant relative weight is one of combined with the existing weight, added to the existing weight and modified by a prescribed function to correspond to a cumulative relative weight.

33. A method of searching multimedia data comprising:

a1) grouping multimedia data in a database of a search system;

b1) searching for reference multimedia data belonging to a group of k reference multimedia data and sorting the multimedia data obtained by the search, using initial weights of features in the reference group;

c1) feeding back at least one multimedia data depending upon a degree of error in the sorted multimedia data; and

d1) updating said weights of features using said at least one feedback multimedia data, wherein updating the weights of features uses a first prescribed relationship to a similarity between said at least one feedback multimedia data and reference multimedia data, if said at least one feedback multimedia data is a relevant multimedia data; and

updating the weights of features uses a second prescribed relationship to a dissimilarity between said at least one feedback multimedia data and reference multimedia data, if said at least one feedback multimedia data is an irrelevant image.

34. The method of claim 33, wherein the first and second prescribed relationships are each a proportional relationship.

35. The method of claim 33, wherein said updating comprises:

calculating a relative weight W to update an existing weight of features, wherein the relative weight W is determined as follows;

36. The method of claim 35, wherein the relative weight W comprises one of a type weight Wk, an element weight We and a position weight Wp.

37. The method of claim 36, wherein a resultant relative weight is one of combined with the existing weight, added to the existing weight and modified by a prescribed function to correspond to a cumulative relative weight.