# 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.