Diffusion distance for histogram comparison

• US 7,715,623 B2
• Filed: 11/13/2006
• Issued: 05/11/2010
• Est. Priority Date: 11/14/2005
• Status: Expired due to Fees

• Current Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Ling, Haibin, Okada, Kazunori
• Primary Examiner(s): Alavi; Amir
• Application Number:
  US11/598,538
• Publication Number:
  US 20070110306A1
• Time in Patent Office: 1,275 Days
• Field of Search: 382/130, 382/167, 382/168, 382/172, 382/181, 382/203, 382/209, 382/210, 382218-220, 382/254, 382260-264, 358/3.23, 358/466, 358/518, 358/534, 358/535
• US Class Current: 382/168
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching

Abstract

A new measure to compare histogram-based descriptors, a diffusion distance, is disclosed. The difference between two histograms is defined to be a temperature field. The relationship between histogram similarity and diffusion process is discussed and it is shown how the diffusion handles deformation as well as quantization effects. As a result, the diffusion distance is derived as the sum of dissimilarities over scales. Being a cross-bin histogram distance, the diffusion distance is robust to deformation, lighting change and noise in histogram-based local descriptors. In addition, it enjoys linear computational complexity which significantly improves previously proposed cross-bin distances with quadratic complexity or higher The proposed approach is tested on both shape recognition and interest point matching tasks using several multi-dimensional histogram-based descriptors including shape context, SIFT and spin images. In all experiments, the diffusion distance performs excellently in both accuracy and efficiency in comparison with other state-of-the-art distance measures. In particular, it performs as accurate as the Earth Mover'"'"'s Distance with a much greater efficiency.

Claims

1. A method of comparing a first histogram h₁ to a second histogram h₂, comprising determining a diffusion distance that is a function of h₁, h₂ and a diffusion filter wherein the diffusion distance is

2. The method as claimed in claim 1, wherein the diffusion filter is a Gaussian filter.

3. The method of claim 1, wherein the function is a temperature function T(x,t) that is related to h₁ and h₂.

4. The method of claim 3, wherein T(x,t)=T₀(x,0)*φ

(x,t), where φ

(x,t) is the Gaussian filter.

5. The method of claim 4, wherein T₀(x,0)=h₁−

h₂.

6. The method of claim 4, wherein

7. The method of claim 1, further comprising using the diffusion distance in a shape matching process.

8. The method of claim 1, further comprising using the diffusion distance in an image retrieval process.

9. The method of claim 1, further comprising using the diffusion distance in a texture analysis process.

10. A system for comparing a first histogram h₁ to a second histogram h₂, comprising:

a processor; and

application software operable on the processor to determine a diffusion distance that is a function of h₁, h₂ and a diffusion filter wherein the diffusion distance is

11. The system as claimed in claim 10, wherein the diffusion filter is a Gaussian filter.

12. The system of claim 11, wherein the function is a temperature function T(x,t) that is related to h₁ and h₂.

13. The system of claim 12, wherein T(x,t)=T₀(x,0)*φ

(x,t), where φ

(x,t) is the Gaussian filter.

14. The system of claim 13, wherein T₀(x,0)=h₁−

h₂.

15. The system of claim 13, wherein

16. The system of claim 10, wherein the software application is further operable to use the diffusion distance in a shape matching process.

17. The system of claim 10, wherein the software application is further operable to use the diffusion distance in an image retrieval process.

18. The system of claim 10, wherein the software application is further operable to use the diffusion distance in a texture analysis process.