{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Sliding window histogram\n\n\nHistogram matching can be used for object detection in images [1]_. This\nexample extracts a single coin from the ``skimage.data.coins`` image and uses\nhistogram matching to attempt to locate it within the original image.\n\nFirst, a box-shaped region of the image containing the target coin is\nextracted and a histogram of its greyscale values is computed.\n\nNext, for each pixel in the test image, a histogram of the greyscale values in\na region of the image surrounding the pixel is computed.\n``skimage.filters.rank.windowed_histogram`` is used for this task, as it employs\nan efficient sliding window based algorithm that is able to compute these\nhistograms quickly [2]_. The local histogram for the region surrounding each\npixel in the image is compared to that of the single coin, with a similarity\nmeasure being computed and displayed.\n\nThe histogram of the single coin is computed using ``numpy.histogram`` on a box\nshaped region surrounding the coin, while the sliding window histograms are\ncomputed using a disc shaped structural element of a slightly different size.\nThis is done in aid of demonstrating that the technique still finds similarity\nin spite of these differences.\n\nTo demonstrate the rotational invariance of the technique, the same test is\nperformed on a version of the coins image rotated by 45 degrees.\n\nReferences\n----------\n.. [1] Porikli, F. \"Integral Histogram: A Fast Way to Extract Histograms\n in Cartesian Spaces\" CVPR, 2005. Vol. 1. IEEE, 2005\n.. [2] S.Perreault and P.Hebert. Median filtering in constant time.\n Trans. Image Processing, 16(9):2389-2394, 2007.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import numpy as np\nimport matplotlib\nimport matplotlib.pyplot as plt\n\nfrom skimage import data, transform\nfrom skimage.util import img_as_ubyte\nfrom skimage.morphology import disk\nfrom skimage.filters import rank\n\n\nmatplotlib.rcParams['font.size'] = 9\n\n\ndef windowed_histogram_similarity(image, selem, reference_hist, n_bins):\n # Compute normalized windowed histogram feature vector for each pixel\n px_histograms = rank.windowed_histogram(image, selem, n_bins=n_bins)\n\n # Reshape coin histogram to (1,1,N) for broadcast when we want to use it in\n # arithmetic operations with the windowed histograms from the image\n reference_hist = reference_hist.reshape((1, 1) + reference_hist.shape)\n\n # Compute Chi squared distance metric: sum((X-Y)^2 / (X+Y));\n # a measure of distance between histograms\n X = px_histograms\n Y = reference_hist\n\n num = (X - Y) ** 2\n denom = X + Y\n denom[denom == 0] = np.infty\n frac = num / denom\n\n chi_sqr = 0.5 * np.sum(frac, axis=2)\n\n # Generate a similarity measure. It needs to be low when distance is high\n # and high when distance is low; taking the reciprocal will do this.\n # Chi squared will always be >= 0, add small value to prevent divide by 0.\n similarity = 1 / (chi_sqr + 1.0e-4)\n\n return similarity\n\n\n# Load the `skimage.data.coins` image\nimg = img_as_ubyte(data.coins())\n\n# Quantize to 16 levels of greyscale; this way the output image will have a\n# 16-dimensional feature vector per pixel\nquantized_img = img // 16\n\n# Select the coin from the 4th column, second row.\n# Co-ordinate ordering: [x1,y1,x2,y2]\ncoin_coords = [184, 100, 228, 148] # 44 x 44 region\ncoin = quantized_img[coin_coords[1]:coin_coords[3],\n coin_coords[0]:coin_coords[2]]\n\n# Compute coin histogram and normalize\ncoin_hist, _ = np.histogram(coin.flatten(), bins=16, range=(0, 16))\ncoin_hist = coin_hist.astype(float) / np.sum(coin_hist)\n\n# Compute a disk shaped mask that will define the shape of our sliding window\n# Example coin is ~44px across, so make a disk 61px wide (2 * rad + 1) to be\n# big enough for other coins too.\nselem = disk(30)\n\n# Compute the similarity across the complete image\nsimilarity = windowed_histogram_similarity(quantized_img, selem, coin_hist,\n coin_hist.shape[0])\n\n# Now try a rotated image\nrotated_img = img_as_ubyte(transform.rotate(img, 45.0, resize=True))\n# Quantize to 16 levels as before\nquantized_rotated_image = rotated_img // 16\n# Similarity on rotated image\nrotated_similarity = windowed_histogram_similarity(quantized_rotated_image,\n selem, coin_hist,\n coin_hist.shape[0])\n\nfig, axes = plt.subplots(nrows=2, ncols=2, figsize=(10, 10))\n\naxes[0, 0].imshow(quantized_img, cmap='gray')\naxes[0, 0].set_title('Quantized image')\naxes[0, 0].axis('off')\n\naxes[0, 1].imshow(coin, cmap='gray')\naxes[0, 1].set_title('Coin from 2nd row, 4th column')\naxes[0, 1].axis('off')\n\naxes[1, 0].imshow(img, cmap='gray')\naxes[1, 0].imshow(similarity, cmap='hot', alpha=0.5)\naxes[1, 0].set_title('Original image with overlaid similarity')\naxes[1, 0].axis('off')\n\naxes[1, 1].imshow(rotated_img, cmap='gray')\naxes[1, 1].imshow(rotated_similarity, cmap='hot', alpha=0.5)\naxes[1, 1].set_title('Rotated image with overlaid similarity')\naxes[1, 1].axis('off')\n\nplt.tight_layout()\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.1"
}
},
"nbformat": 4,
"nbformat_minor": 0
}