DRAFT
This is the first article in the series on Image Comparison using Local Binary Patterns.
Complete code is on github lbp-matcher
We will start off by looking at different methods of comparing histograms.
- Histogram Intersection
- Log Likehood
- Chi Squared
- Kullback Leibler Divergence
All our operations will be performed on 8bpp(bits per pixel) images anything that is not in that format will be up and down converted accordingly.
Model representation is very simple it contains nothing more than a simple array of bins that will contain our histogram data. As we build the system the model might change.
Our model will contain 256 bins each bin representing gray intensity in 8 bpp image with 0 being black and 255 being white.
struct LBPModel
{
static const int_t bin_size = 256;
int_t bins[bin_size] = {};
};
Histogram Intersection
This is the basic method of comparing two histograms. The idea here is to take the minimum value of the two bins.
Histogram Intersection
[latex](a,b)\;=\sum\nolimits_{i=1}^nmax(a_i,\;b_i)[/latex]
Histogram intersection in normalized form between 0..1;
[latex]
(a,b)\;=\;\frac{\sum_{i=1}^n(a_i,b_i)}{max(\sum_{i=1}^na,\sum_{i=1}^nb)\;}
[/latex]
Complete equation with branchless execution and normalization. Branchless execution can provide us with two benefits first there is no IF condition checking so we could gain performance but not necessarily, second it prevents timing attack analysis. Here we are only interested in performance. We will take a look at the generated assembly down the road and do quick performance analysis of our algorithm.
[latex](a,b)\;=\;\frac{\frac12\sum_{i=1}^n(a_i+b_i\;-\;\vert a_i-b_i\vert)}{max(\sum_{i=1}^na,\sum_{i=1}^nb)\;}[/latex]
Here we have couple examples of how this calculation was actually performed. This has been copied from the excel spreadsheet which can be found in the git repo.
Example 1 – High similarity
Bin[a] Bin[b] Result
1 1 2 = A2+B2-ABS(A2-B2)
2 2 4 = A3+B3-ABS(A3-B3)
3 3 6
4 4 8
5 5 10
Value 15.00 = 0.5 * SUM(C2:C6)
Normalized 1.0 = C8 / MAX(SUM(A2:A6), SUM(B2:B6))
Example 2 – Medium similarity
In this example bin[b] has couple different values but it is still pretty close.
Bin[a] Bin[b] Result
1 2 2
2 2 4
3 3 6
4 4 8
5 2 4
Value 12.00
Normalized 0.8
Example 3 – Low similarity
Here our histograms are quite different so our similarity is very low.
Bin[a] Bin[b] Result
1 20 2
2 2 4
3 3 6
4 4 8
5 20 10
Value 15.00
Normalized 0.3
Implementation
double HistogramComparison::scoreHistogramIntersection(const LBPModel &model, const LBPModel &sample) const
{
double d = 0,s1 = 0,s2 = 0;
// branch less execution
for (int_t i = 0; i < model.bin_size; ++i)
{
d += model.bins[i] + sample.bins[i] - std::abs(model.bins[i] - sample.bins[i]);
s1 += model.bins[i];
s2 += sample.bins[i];
}
return (0.5 * d) / std::fmax(s1, s2);
}
Log Likelihood
Implementation
double HistogramComparison::scoreLogLikelihood(const LBPModel &model, const LBPModel &sample) const
{
double d = 0;
for (int_t i = 0; i < model.bin_size; ++i)
{
if (model.bins[i] > 0)
{
d += sample.bins[i] * std::log(model.bins[i]);
}
}
return -d;
}
Chi Squared
Implementation
double HistogramComparison::scoreChiSquared(const LBPModel &model, const LBPModel &sample) const
{
double d = 0;
for (int_t i = 0; i < model.bin_size; ++i)
{
double q = sample.bins[i] + model.bins[i];
if (q != 0)
{
double d1 = std::pow(sample.bins[i] - model.bins[i], 2);
d += d1 / q;
}
}
return d;
}
Kullback Leibler Divergence
Implementation
double HistogramComparison::scoreKullbackLeiblerDivergence(const LBPModel &model, const LBPModel &sample) const
{
double d = 0;
for (int_t i = 0; i < model.bin_size; ++i)
{
double p = model.bins[i];
double q = sample.bins[i];
if (p != 0 && q != 0)
{
d += p * std::log(p / q);
}
}
return d;
}
References :
http://www.ariel.ac.il/sites/ofirpele/publications/ECCV2010.pdf
https://en.wikipedia.org/wiki/Grayscale
https://en.wikipedia.org/wiki/Likelihood_function
https://www.mathjax.org/
http://www.imatheq.com/imatheq/com/imatheq/math-equation-editor.html
http://www.wiris.com/editor/demo/en/mathml-latex