Multimedia searching method using histogram

• US 20020062309A1
• Filed: 09/10/2001
• Published: 05/23/2002
• Est. Priority Date: 09/08/2000
• Status: Active Grant

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: LG Electronics, Inc. (LG Corporation)
• Inventors: Kim, Hyeon-Jun, Lee, Jin-Soo
• Granted Patent: US 7,003,518 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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, which can achieve a high performance and provide a interoperability by defining a standard histogram that can be mutually searched, and optimizing the histogram for each application.

According to the method, the histogram using uniformly quantized bin values is defined as a standard histogram, and a comparative search is performed by converting the standard histogram into an optimized histogram having non-uniformly-quantized bin values optimized for a certain application by non-uniformly combining the uniformly-quantized bin values.

Also, according to the method, the histogram obtained by uniformly quantizing a given color space is defined as a standard histogram, and a comparative search is performed by converting the standard histogram into an optimized histogram having bins representing the non-uniformly-quantized color space optimized 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 multimedia searching method using a histogram that expresses feature information of multimedia, comprising the steps of:

(a) uniformly dividing the histogram; and

(b) performing a search by directly using the uniformly-divided histogram or by non-uniformly combining the uniformly-divided histogram in accordance with an object group to be searched.

2. The method as claimed in claim 1, wherein if the object group to be searched is a single object group, the 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 uniformly-divided histogram is used as it is.

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

3. A multimedia searching method using a histogram that expresses feature information of multimedia, comprising the steps of:

(a) uniformly dividing information for expressing the histogram;

(b) non-uniformly combining the uniformly-divided histogram information to be optimized for a specified application; and

(c) performing a multimedia search for the corresponding specified application using the non-uniformly-combined histogram information.

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

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

6. A multimedia searching method using a histogram that respective bin values are expressed by N bits, the method comprising the steps of:

(a) defining the histogram using the bin values uniformly-quantized (i.e., uniform-divided) into 2_N as a standard histogram,

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

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

7. The method as claimed in claim 6, wherein the step of non-uniformly combining the uniformly-quantized (i.e., uniformly-divided) 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.

8. A multimedia searching method using a histogram that respective bin values are expressed by N bits, the method comprising the steps of:

(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 specified threshold value and performs a sparse uniform division for the bin values higher than the specified 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.

9. The method as claimed in claim 8, 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.

10. A multimedia searching method using a histogram having N bins obtained by dividing a color space into N partial regions, the method comprising the steps of:

(a) defining the histogram obtained by uniformly quantizing (i.e., uniformly dividing) the given color space into the N partial regions as a standard histogram,

(b) converting the standard 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 uniformly quantizing (i.e., uniformly dividing) the color space into the N partial regions, and

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

11. The method as claimed in claim 10, wherein the step of non-uniformly combining the bins representing the color space uniformly-quantized (i.e., uniformly-divided) 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.

12. The method as claimed in claim 10, wherein the step of non-uniformly combining the bins representing the color space uniformly-quantized (i.e., uniformly-divided) 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.

14. The method as claimed in claim 13, wherein the step of 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.

15. The method as claimed in claim 13, wherein the step of 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.

13. A multimedia searching method using a histogram having N bins obtained by dividing a color space into N partial regions, the method comprising the steps of:

(a) defining the histogram obtained by more closely uniform-quantizing (i.e., uniform-dividing) the color space in the regions having a purity lower than a specified threshold value and by more sparsely uniform-quantizing the color space in the regions having a purity higher than the specified threshold value asa standard histogram,

(b) 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

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

16. A multimedia searching method using a histogram that express a multimedia feature, comprising:

(a) defining 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 an optimized histogram having non-uniformly quantized featureoptimized for a certain application by non-uniformly combining the uniformly quantized feature information using the standard histogram.