Diffusion distance for histogram comparison
View Patent ↗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.
1. A method of comparing a first histogram h 1 to a second histogram h 2 , comprising determining a diffusion distance that is a function of h 1 , h 2 and a diffusion filter wherein the diffusion distance is
K
(
h
1
,
h
2
)
=
∑
l
=
0
L
k
(
d
l
(
x
)
)
,
wherein
d
0
(
x
)
=
h
1
(
x
)
-
h
2
(
x
)
and
d
l
(
x
)
=
[
d
l
-
1
(
x
)
*
ϕ
(
x
,
σ
)
]
↓
2
and wherein L is a number of pyramid layers, σ is the constant standard deviation for φ and ↓ 2 denotes half size downsampling.
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 1 and h 2 .
4. The method of claim 3 , wherein T(x,t)=T 0 (x,0)*φ(x,t), where φ(x,t) is the Gaussian filter.
5. The method of claim 4 , wherein T 0 (x,0)=h 1 −h 2 .
6. The method of claim 4 , wherein
ϕ
(
x
,
t
)
=
1
(
2
π
)
1
/
2
t
exp
{
-
x
2
2
t
2
}
.
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 1 to a second histogram h 2 , comprising:
a processor; and
application software operable on the processor to determine a diffusion distance that is a function of h 1 , h 2 and a diffusion filter wherein the diffusion distance is
K
(
h
1
,
h
2
)
=
∑
l
=
0
L
k
(
d
l
(
x
)
)
,
wherein
d
o
(
x
)
=
h
1
(
x
)
-
h
2
(
x
)
and
d
l
(
x
)
=
[
d
l
-
1
(
x
)
*
ϕ
(
x
,
σ
)
↓
2
and wherein L is a number of pyramid layers, σ is the constant standard deviation for φ and ↓ 2 denotes half size downsampling.
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 1 and h 2 .
13. The system of claim 12 , wherein T(x,t)=T 0 (x,0)*φ(x,t), where φ(x,t) is the Gaussian filter.
14. The system of claim 13 , wherein T 0 (x,0)=h 1 −h 2 .
15. The system of claim 13 , wherein
ϕ
(
x
,
t
)
=
1
(
2
π
)
1
/
2
t
exp
{
-
x
2
2
t
2
}
.
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.