Sunday, 19 January 2014

Local Binary Pattern

Local Binary Pattern

  • In this article we will look at concept of Local Binary Pattern and computation of LBP image.
  • 2D surface texture is characterize by spatial pattern and intensity/contrast.
  • Spatial Pattern is affected by rotation,scale changes ,hence for a good texture description we require a rotation and scale invariant descriptor.
  • Local binary pattern binarizes the local neighborhood of each pixel and builds a histogram on these binary neighborhood patterns.
  • Let P be the number of neighborhood pixels and R the distance from the center pixel $l_c$ and $l_p$ be neighborhood pixel.
  • A $LBP_{P,R}$ number characterizes the local texture by assigning the binomial factor $2^P$ for each sign $sgn(l_p-l_c)$ \[ LBP_{P,R} = \sum_{p=0}^{P-1} sgn(l_p - l_c) 2^p \]
  • $l_p$ for $p={0\ldots P-1}$ are a set of equally spaced pixels on a circle of radius $R$.
  • $LBP_{P,R}$ features has $2^P$ possible values.For P=8 we have a binary feature vector of length $256$.
  • Patterns are classified as uniform and non uniform.
  • Uniform pattern have single contigious regions of 0 and 1 while non uniform patterns do not.For example 01100000 is a uniform pattern while 01010000 is a example of non uniform pattern
  • we can see that there are 9 possible uniform pattern values
    0 0 0 0 0 0 0 0
    1 0 0 0 0 0 0 0
    1 1 0 0 0 0 0 0
    1 1 1 0 0 0 0 0
    1 1 1 1 0 0 0 0
    1 1 1 1 1 0 0 0
    1 1 1 1 1 1 0 0
    1 1 1 1 1 1 1 0
    1 1 1 1 1 1 1 1
  • Now consider the effect of rotation on the feature vector.
  • Rotating the image results in circular shift of values of feature vector.
  • To encorporate rotational invariance we need to assign all possible rotation of a feature vector to a single LBP value For example all the below patterns
    1 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 0 1 0 0 0
    0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0
    0 0 0 0 0 0 0 1
    \\ will be assigned to a single value.
  • In the present article however we are not considering rotational invariant features
  • Let us consider the implementation details of LBP
  • If we only consider a 3x3 neighborhood we need to threshold the rectangular region about
  • Another method would be to divide image into square blocks of size BxB.Instead of central pixel value we consider the mean value of pixels in the central block.
  • Similariy instead of considering the single pixel value in the neighborhood we would consider the mean value of pixels in the block.
  • All the pixels in the block are encoded with the same binary value 0 or 1.
  • to compute mean value over rectangular regions of image,integral images are used.
  • output of lbp images for block size 1,2 and 8 is showing in figure f1
    LBP Images
    f1
  • we can see that as block size increases,quantization effects can be seen and the information in the encoded image cannot be recognized.
  • the code for the same can be found in the git repo for OpenVisionLibrary https://github.com/pi19404/OpenVision/ in following files ImgFeatures/lbpfeatures.hpp and lbpFeatures.cpp files

Friday, 17 January 2014

Integral Image for mean and variance computation

Introduction

  • The Integral Image is used as a quick and effective way of calculating the sum of values (pixel values) in a given image – or a rectangular subset of a grid (the given image).
  • In this article we will assume that concepts of integral image is known and then proceed to see how it can be used to compute the mean and variance of a image patch.
  • Given a integral representation of an image,the sum of value of pixels in the rectangular region R with vertices A,B,C,D is given by \[ I = S(A) +S(D) -S(B) -S(C) \]
  • Dividing this quantity by the number of pixels gives us the mean value of pixels in the region. \[ \mu = \frac{I}{N} \]
  • Let us also consider the squared integral image.To obtain this all the pixel values in the image are squared then integral image is computed.
  • consider the variance about a rectangulation regions \[ v= \sum_i (x_i-\mu)^2 v= \sum_i x_i^2 - 2\sum_i x_i \mu + \mu^2 v= \sum_i x_i^2 - \mu^2 \] The summation $x_i^2$ can obtained by the square integral image and $\mu$ can be obtained by integral image computation.
  • This enables us to compute the variance of rectangular patch of image.
  • A similar method can be employed to compute the denominator variance term normalize cross correlation formula.
  • the above code can be found in git repo https://github.com/pi19404/OpenVision/tree/master/ ImgFeatures/integralImage.cpp and ImgFeatures/integralImage.hpp files.