# Patch Histogram Feature

This post will introduce a new feature for binary blobs like connected components in a text.

The feature is called *patch histogram* and it's the histogram of 3x3
patches of black and white pixels. We collect all 3x3 patches and count
their frequency.

3x3 patch for a binary image contains 2^9 = 512 different combinations. For each of these combinations, we assign a number. I wrote the implementation in Python and here is a lookup table that converts all possible 3x3 patches to their ids.

patch_histogram_dict = {} for f in range(0, 512): i22 = f & 1 i21 = (f >> 1) & 1 i20 = (f >> 2) & 1 i12 = (f >> 3) & 1 i11 = (f >> 4) & 1 i10 = (f >> 5) & 1 i02 = (f >> 6) & 1 i01 = (f >> 7) & 1 i00 = (f >> 8) & 1 patch_histogram_dict[ma(i00, i01, i02, i10, i11, i12, i20, i21, i22)] = f

I was looking a *skeleton feature* that can be applied to components
after medial axis transform. However, we will use binarized connected
component images directly in this version and take a look at skeletal
version later.

Above, we used a function `ma` to convert a set of numbers to a tuple
of tuples. It's simple as

def ma(i00, i01, i02, i10, i11, i12, i20, i21, i22): return ((i00, i01, i02), (i10, i11, i12), (i20, i21, i22))

The first step in feature generation is marking each pixel of the image
with its id. Then a simple `np.histogram` call generates the
histogram.

for i in range(1, rows - 1): for j in range(1, cols - 1): s = framed[(i-1):(i+2), (j-1):(j+2)] marks[i-1, j-1] = patch_dict[ma(s[0, 0], s[0, 1], s[0, 2], s[1, 0], s[1, 1], s[1, 2], s[2, 0], s[2, 1], s[2, 2])]

=framed= is a copy of the original image with a 1 pixel frame, so that
boundary pixel are also counted without much checking. `patch_dict` is
a parameter that the function receives. Its default value is the
dictionary that we made above, but any kind of patch dictionaries can be
used.

The feature is a call to `numpy.histogram` as follows

histogram = numpy.histogram(marked_points, hist_range, density=True, bins=bins)

=marked_{points}= are the result of above pixel counting loop.
`hist_range` is the minimum and maximum value for the patch
dictionary. `density` parameter is True, so that the histogram is
normalized to 1 and feature become size invariant. `bins` is a
parameter we can set freely, but by default it's equal to the range of
elements.

The comparison can be done with standard histogram comparison methods, like EMD or Chi Square distance metrics.