Multimedia searching method using histogram

• US 7,003,518 B2
• Filed: 09/10/2001
• Issued: 02/21/2006
• Est. Priority Date: 09/08/2000
• Status: Expired due to Fees

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: LG Electronics, Inc. (LG Corporation)
• Inventors: Lee, Jin-Soo, Kim, Hyeon-Jun
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/948,936
• Publication Number:
  US 20020062309A1
• Time in Patent Office: 1,625 Days
• Field of Search: 707/100, 707/102, 707/5, 707/2, 707/3, 707/104, 707/101, 707/6, 707/103, 715/501.1, 382/166, 382/162, 345/585, 358/515
• US Class Current: 1/1
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Disclosed is a multimedia searching method and apparatus that can achieve a high performance and provide a interoperability by defining a histogram using uniformly quantized bin values as a standard histogram, and a comparative search can be performed using a search histogram having non-uniformly-quantized bin values based on the standard histogram. The non-uniformly quantized bin values of the search histogram can be determined for each application by non-uniformly combining the uniformly-quantized bin values. According to a method, the histogram is defined as a standard histogram, and a comparative search is performed by converting the standard histogram. Further, a standard histogram obtained by uniformly quantizing a given color space can be converted into a search histogram (e.g., determined for a certain application) by non-uniformly combining the bins obtained by uniformly quantizing the color space into the N partial regions.

Claims

1. A computer-implemented multimedia searching method using a second histogram that expresses feature information of multimedia, comprising:

uniformly dividing a first histogram using a range value; and

performing a search using the second histogram, wherein the second histogram is generated by non-uniformly combining the uniformly-divided first histogram in accordance with the range value.

2. The method as claimed in claim 1, wherein the second non-uniformly-divided histogram is converted in accordance with an object group to be searched.

3. The method as claimed in claim 2, wherein if the object group to be searched is a single object group, the first uniformly-divided histogram is non-uniformly combined and used to match a characteristic of the histogram, while if the object group is not the single object group and it is difficult to define the characteristic of the histogram, the first uniformly-divided histogram is used.

4. The method as claimed in claim 1, wherein the first histogram is obtained by dividing a color space into N partial regions.

5. A computer-implemented multimedia searching method using a histogram that expresses feature information of multimedia, comprising:

uniformly dividing information for expressing the histogram;

non-uniformly converting the uniformly-divided histogram information according to a specified application; and

performing a multimedia search for the corresponding specified application using the non-uniformly-converted histogram information.

6. The method as claimed in claim 5, wherein the uniform division is performed for whole regions of the information for expressing the histogram.

7. The method as claimed in claim 5, wherein the uniform division is performed by uniformly dividing at least two regions based on a threshold value of the information for expressing the histogram in different numbers for the respective regions.

8. The method as claimed in claim 5, wherein the multimedia searching method is performed in a case where the histogram is used for a multimedia search in a limited range in the specified application, and wherein the non-uniformly-converted histogram information is determined for each specified application.

9. A computer-implemented multimedia searching method using a histogram that respective bin values are expressed by N bits, the method comprising:

forming a histogram using the bin values uniformly-quantized into 2^N as a standard histogram; and

converting the standard histogram into a converted histogram having non-uniformly-quantized bin values corresponding to a specified application by non-uniformly combining the 2^N uniformly-quantized bin values; and

performing a comparative search using the converted histogram.

10. The method as claimed in claim 9, wherein the non-uniformly combining the uniformly-quantized bin values of 2^N is implemented by converting the uniformly-quantized bin values into the non-uniformly-quantized bin values in a manner that as the bin values become closer to 0, the bin values are more closely quantized by combining the smaller number of the uniformly-divided bin values as close to 0 as the values are.

11. The method as claimed in claim 9, wherein the non-uniformly combining the uniformly-quantized bin values of 2^N is implemented by converting the uniformly-quantized bin values into the non-uniformly-quantized bin values in a manner that bin values greater than a threshold are more closely quantized than remaining bin values less than the threshold.

12. The method as claimed in claim 9, wherein the histogram is obtained by dividing a color space into N partial regions.

13. The method as claimed in claim 9, wherein a plurality of converted histograms are predetermined before the comparative search is performed.

14. A computer-implemented multimedia searching method using a histogram that respective bin values are expressed by N bits, the method comprising:

(a) defining the histogram using the bin values obtained by performing a semi-uniform quantization for the bin values of 2^N as a standard histogram, wherein the semi-uniform quantization performs a close uniform division for the bin values lower than a threshold value and performs a sparse uniform division for the bin values higher than the threshold value;

(b) converting the standard histogram into a histogram having non-uniformly-quantized bin values optimized for a specified application by non-uniformly combining the quantized bin values of 2^N; and

(c) performing a comparative search using the converted histogram.

15. The method as claimed in claim 14, wherein the step of non-uniformly combining the quantized bin values of 2^N is implemented by converting the uniformly-quantized bin values into the non-uniformly-quantized bin values in a manner that as the bin values become closer to 0, the bin values are more closely quantized by combining the smaller number of the uniformly-divided bin values as close to 0 as the values are.

16. A computer-implemented multimedia searching method using a histogram having N bins obtained by dividing a color space into N partial regions, the method comprising:

defining the histogram obtained by uniformly quantizing the given color space into the N partial regions as a standard histogram;

converting the standard histogram into a histogram having the bins representing the non-uniformly-quantized color space corresponding to a specified application by non-uniformly combining the bins obtained by uniformly quantizing the color space into the N partial regions; and

performing a comparative search using the converted histogram.

17. The method as claimed in claim 16, wherein the non-uniformly combining the bins representing the color space uniformly-quantized into the N regions is implemented in a manner that the regions having a lower purity are more closely quantized based on brightness and purity axes by combining a smaller number of the uniformly-divided values based on the brightness and purity axes.

18. The method as claimed in claim 16, wherein the non-uniformly combining the bins representing the color space uniformly-quantized into the N regions is implemented in a manner that the regions having a lower purity are more sparsely quantized based on a hue by combining a larger number of the uniformly-divided values based on the hue.

19. The method as claimed in claim 16, wherein a plurality of converted histograms are predetermined before the comparative search is performed.

20. A computer-implemented multimedia searching method using a histogram having N bins obtained by dividing a color space into N partial regions, the method comprising:

defining the histogram obtained by more closely uniform-quantizing the color space in the regions having a purity lower than a threshold value and by more sparsely uniform-quantizing the color space in the regions having a purity higher than the threshold value as a standard histogram;

converting the histogram into a histogram having the bins representing the non-uniformly-quantized color space optimized for a specified application by non-uniformly combining the bins obtained by quantizing the color space into the N partial regions; and

performing a comparative search using the converted histogram.

21. The method as claimed in claim 20, wherein the non-uniformly combining the bins representing the color space quantized into the N regions is implemented in a manner that the regions having a lower purity are more closely quantized based on brightness and purity axes by combining a smaller number of the uniformly-divided values based on the brightness and purity axes.

22. The method as claimed in claim 20, wherein the non-uniformly combining the bins representing the color space uniformly quantized into the N regions is implemented in a manner that the regions having a lower purity are more sparsely quantized based on a hue by combining a larger number of the uniformly-divided values based on the hue.

23. A computer-implemented method for forming a histogram that expresses feature information, comprising:

(a) forming a standard histogram by performing a uniform quantization or a semi-uniform quantization with respect to information for expressing the histogram as a multimedia feature; and

(b) converting the standard histogram into a converted histogram having a non-uniformly quantized feature corresponding to a specified application, wherein the converted histogram is formed by non-uniformly combining the uniformly quantized feature information of the standard histogram.

24. The method as claimed in claim 23, wherein the semi-uniform quantization is performed by uniformly dividing some regions closely and uniformly dividing other regions sparsely, based on a threshold value.

25. The method of claim 23, wherein the histogram is obtained by dividing a color space into N partial regions.