All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Kullback-Leiber divergence measure in correlation of gray-scale objects

Transcript

The Second International Conference on Innovations in Information Technology (IIT’05)
1
KULLBACK-LEIBER DIVERGENCE MEASURE INCORRELATION OF GRAY-SCALE OBJECTS
M. Sohail Khalid National University of Sciences and Technology, Pakistan, soh_78@yahoo.com M. Umar Ilyas National University of Sciences and Technology, Pakistan Khawar Mahmood
COMSATS Institute of Information Technology, Lahore, Pakistan
M. Saquib Sarfaraz Technische Universitat, Berlin, Germany M. Bilal Malik National University of Sciences and Technology, Pakistan
ABSTRACT
Kullback-Leiber divergence measure is one of the commonly used distance measure that is used for computing the dissimilarity score between histograms. In this paper we show that it produces biased resultswhen correlation is computed between gray scale images or sections of images using their histograms. The biased is explored and demonstrated through numerous experiments with different sizes of objects anddifferent kind of movements between the pairs of images i.e., slow moving, fast moving, rotating bodiesetc, in cluttered and less cluttered environments. The performance of the Kullback-Leiber divergencemeasure is compared with a pixel based spatial matching criterion.
Keywords:
histogram, similarity measure, correlation.
1.
INTRODUCTION
In pattern recognition applications we often need to find the similarity between two images or twosections of images. This may be done by correlating the spatial information or by matching their spectral features. Kullback-Leiber (KL) divergence measure suggested in [1] is an informationtheoretic criterion which gives a dissimilarity score between the probability densities (spectralinformation) of two images or sections of images. H. Chen and T. Liu [2] used Kullback Leiber measure as the dissimilarity/similarity measure, they compared Bhattacharyya Coefficient [3]with different optimization techniques, they emphasized on the better performance of TrustRegion optimization over Mean Shift. Puzicha [4] presented a comparison between the performance of different measures. While considering the KL divergence as a dissimilaritymeasure all of the above authors used the color histogram of the image as an estimate to their densities. In this paper we consider the gray scale images and explored the performance of KLdivergence measure. The experiments show that KL divergence curve shows a bias in thecorrelation. The correlation between two objects and hence the actual location of the object isascertained by Mean Square Error, then KL measure graph is plotted, the maximum value of thecurve should be the actual location of the object, but there is always a drift of the maximum valueas compared to the actual location of the object.We begin with a discussion of object representation based on the image histogram. Section 3shows the representation of the weighted densities and construction of image histogram. Thedefinition of KL divergence measure and Mean Square Error appears in section 4 and 5respectively and finally section 6 presents the experiments showing the biased nature of themeasure.
The Second International Conference on Innovations in Information Technology (IIT’05)
2
2.
OBJECT REPRESENTATION
To characterize the object, first a feature space is chosen. The object is represented by its probability density function (pdf). The pdf can be estimated by m-bin histogram of object. Thehistogram is not the best nonparametric density estimate [5], but it suffices for our purposes.Other discrete density estimates can be employed also. The reference object is the one to besearched in the same image or may be in next image of a video sequence or in any image where asimilar object may be found. The candidate objects are tested against the reference object to check the similarity between them. Both the reference and the candidate objects are represented by m- bin histograms as an estimate to their pdf's. Both the pdf's are to be estimated from the data.
1...
ˆˆq{}
uum
q
=
=
1...
ˆˆ p(y){(y)}
uum
p
=
=
where
ˆq
and
ˆ p
represent the m bin histograms of reference object and the candidate object atlocation y, respectively.
3.
WEIGHTED HISTOGRAM USING KERNEL
An isotropic kernel is used, with a convex and monotonic decreasing kernel profile which assignssmaller weights to the pixels away from the center. These weights increase the robustness of estimation of the probability density function, as the pixels farther from the center are oftenaffected by clutter or interference from the background. For example Epanechnicov Kernel [5] [6]can be used. Now a histogram based on the kernel can be constructed.Let
nii
x
...1
}{
=
be the pixel locations in the region defined as the target object. The function
}...1{:
2
m Rb
→
associates the pixel at position
i
x
to the index
)(
i
xb
of its bin. Now the targetobject histogram can be constructed by computing the probability of the feature
mu
...1
=
as
∑
=
−=
niiiu
u xb xk C q
1
])([)(
ˆ
δ
Where
δ
is the Kronecker delta function and
)(
i
xk
is the kernel, spatially weighting the pixels,giving higher weights towards the center and less weights along the edges of the object. Thenormalization Constant C is derived by imposing the condition
∑
=
=
muu
q
1
1
, from that
∑
=
=
nii
xk C
1
)(1
By using the same notation the histogram
)(ˆ
y p
u
for the candidate object in the subsequent framecan be computed as
∑
=
−−=
niiiu
u xb x yk C y p
1
])([)()(
ˆ
δ
where
∑
=
−=
nii
x yk C
1
)(1
The Second International Conference on Innovations in Information Technology (IIT’05)
3
u
p
ˆ
obviously is the function of the pixel position y. The correlation between
u
q
ˆ
and differentinstances of
u
p
ˆ
can be computed by a similarity function.
4.
KULLBACK-LEIBER DIVERGENCE MEASURE
The dissimilarity function we used defines a distance among target histogram and histograms of candidates. KL divergence between p and q is defined as
1
ˆˆˆ()[p(),q]log()
muuuu
q yyq y
ρ ρ
=
≡ =
∑
The dissimilarity function inherits the properties of the kernel profile when the target andcandidate histograms are represented according to p and q.
4.1 Maximum of KL divergence measure curve
As KL divergence is a dissimilarity measure the minimum of this function will be at the pointwhere maximum similarity exists, we have normalized and inverted the function so as to see themaximum of the function at the maximum similarity point. It is expected that the maximum of this function should be the position of the moved object or the similar object in the subsequentframe or image. Here we are not concerned with the methodology or efficiency of automaticsearch, rather we are interested in the accuracy of finding the position of the object. In other words we are exploring the question that how well the peak of the function represents thecoordinates of the object which is to be searched?
5.
TARGET LOCALIZATION
By target localization we mean finding the spatial coordinates of the object in the image of interest. These coordinates can be found by using some similarity measure and finding on which pixel location this similarity measure gives the maximum value.
5.1 Mean Square Error (MSE)
MSE is an accurate matching criterion in spatial domain. Its problem is the lack of robustness dueto very narrow peak, its sharpness makes it impossible for gradient based search methods to findits maxima automatically, here we are not concerned with the efficient automatic search so fullexhaustive search may be used. MSE may not give good results with the change in illumination of the object. MSE may not prove to be a good practical solution, we can use it to assess the performance of other criteria because the maximum of this function indicates the high similarity based on the gray level of pixel intensities. The expression for the MSE is given as
221
1MSE()
niii
XY n
=
= −
∑
where
i
X
and
i
Y
are the corresponding pixels of the adjacent object windows.
5.2 Comparison of MSE and KL Divergence measure
The sharp peak of the MSE gives the exact coordinates of slightly moved or transformed object.The sharpness of the peak is not adequate for the application of gradient based optimizationmethods. Target localization by KL divergence is problematic due to its biased nature. In theexperiments we compare the peaks of Mean Square Error and KL divergence functions, there is afairly large difference between the two.
The Second International Conference on Innovations in Information Technology (IIT’05)
4
6.
EXPERIMENTS
Experiments are performed using pairs of images from many video sequences, withdifferent sizes of objects and different kind of movements i.e., slow moving, fast moving,rotating bodies etc, in cluttered and less cluttered environments.In the two adjacent frames of a video sequence, a rectangular window containing theobject is taken from the first frame and then the similarity coefficient is calculated bycorrelating the same size of windows in the subsequent frame, a 3d plot of the MeanSquare Error (MSE) is plotted against the pixel positions. The maximum of the plotshows the pixel position where best match occurs. The sharp peak of MSE shows the highmatching with the target.The KL measure plots are obtained using the same scheme. Then these plots arecompared with the MSE plots to observe the difference of the maxima of the two in termsof the pixel positions
6.1 Case I: The car sequence
Following is the experiment performed on the car sequence, the first frame and the object isspecified in Figure 1. This sequence is the example of the object with relatively cluttered background. The MSE and KL Divergence plots are shown below respectively.
Figure 1:
The first frame of car sequence the white rectangle shows the reference object which isto be searched in the subsequent frame
Figure 2a:
Mean Square Error curve between the reference object and the candidate objects inframe number 1 & 2 of car sequence. The peak shows the location where the most similar candidate exists.
The Second International Conference on Innovations in Information Technology (IIT’05)
5
Figure 2b
. The contour plot illustrates the sharpness of the peak.
Figure 3a
: KL divergence Curve between frame 1 & 2 of car sequence, left arrow shows themaximum of KL curve, the right arrow shows the actual maximum or the actual location of theobject as determined by the Mean Square Error.
Figure 3b:
The contour graph shows the nature of the peak, * shows the peak of KL surface.

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x