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

\((a,b)\;=\sum\nolimits_{i=1}^nmax(a_i,\;b_i)\)

Histogram intersection in normalized form between 0..1;

\((a,b)\;=\;\frac{\sum_{i=1}^n(a_i,b_i)}{max(\sum_{i=1}^na,\sum_{i=1}^nb)\;}

\)

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.

\((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)\;}\)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