Day: September 8, 2017

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

This is a series of small articles on Image Comparison using Local Binary Patterns.
Topics I like to cover will include

• Histogram Comparsion
• Local Binary Patterns
• Perceptual Hashing

From there we will go into building a system that can recognize same words/images in a document.