mirror of
https://github.com/saymrwulf/nvidia-AI.summerschool17-notebooks.git
synced 2026-11-20 09:52:58 +00:00
626 lines
378 KiB
Text
626 lines
378 KiB
Text
|
|
{
|
||
|
|
"metadata": {
|
||
|
|
"name": "042-distance-transform"
|
||
|
|
},
|
||
|
|
"nbformat": 3,
|
||
|
|
"nbformat_minor": 0,
|
||
|
|
"worksheets": [
|
||
|
|
{
|
||
|
|
"cells": [
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Title: Distance Transform\n",
|
||
|
|
"Author: Thomas Breuel\n",
|
||
|
|
"Institution: UniKL"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": true,
|
||
|
|
"input": [
|
||
|
|
"\n",
|
||
|
|
"from scipy.ndimage import filters\n",
|
||
|
|
"def ims(image,**kw):\n",
|
||
|
|
" size = kw.get(\"s\",8)\n",
|
||
|
|
" if \"s\" in kw: del kw[\"s\"]\n",
|
||
|
|
" subplots(1,1,figsize=(size,size))\n",
|
||
|
|
" gray(); imshow(image,**kw)\n",
|
||
|
|
"def imp(image,**kw):\n",
|
||
|
|
" subplots(1,1,figsize=(6,6))\n",
|
||
|
|
" gray(); imshow(image,interpolation='nearest',**kw)\n",
|
||
|
|
"def imrow(*args,**kw):\n",
|
||
|
|
" size = kw.get(\"s\",8)\n",
|
||
|
|
" if \"s\" in kw: del kw[\"s\"]\n",
|
||
|
|
" n = len(args)\n",
|
||
|
|
" gray()\n",
|
||
|
|
" subplots(1,n,figsize=(n*size,size))\n",
|
||
|
|
" for i,im in enumerate(args):\n",
|
||
|
|
" subplot(1,n,i+1); imshow(im,**kw)\n",
|
||
|
|
"def rescale(image):\n",
|
||
|
|
" return (image-amin(image))/max(1e-4,amax(image)-amin(image))"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 20
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Distance Transform via Grayscale Morphology\n",
|
||
|
|
"============================================"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"In nonlinear filters, we considered a special kind of grayscale operation:\n",
|
||
|
|
"morphological filtering with a filter constructed from the distance\n",
|
||
|
|
"from the central pixel. Let us look at this on a much simpler image.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"image = zeros((100,100))\n",
|
||
|
|
"image[64,64] = 1\n",
|
||
|
|
"image[30,40] = 1\n",
|
||
|
|
"image[40,30] = 1\n",
|
||
|
|
"image[50,10] = 1\n",
|
||
|
|
"imrow(image)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAdwAAAHaCAYAAACq+vjoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAFshJREFUeJzt3f9vVfX9wPHXhSIwqaJAy5fCEEcLBVGYXxJ/2OZIMTGC\nTAjZTBgx6i9miRoTt79AylwyMdtPbjHNTFR+csw4M4nRbPHLYrpN59hwYkcHtxUpVykUSi/n88M+\ndiOOL0L76to+HslJcy+Xc195G/PknHvObakoiiIAgGE1YaQHAIDxQHABIIHgAkACwQWABIILAAkE\nFwASXFRwX3rppViyZEksXrw4tm3bNlQzAcCYU7rQ+3Cr1Wo0NTXFrl27Yt68eXHDDTfEM888E0uX\nLv33zkulIRsUAEaDM2X1go9wf//738dXvvKVWLhwYUyaNCm+/e1vxy9/+csLHhAAxrILDu7+/ftj\n/vz5g48bGhpi//79QzIUAIw1Fxxcp4sB4PxdcHDnzZsXnZ2dg487OzujoaFhSIYCgLHmgoN7/fXX\nx/vvvx8dHR3R398fzz33XKxbt24oZwOAMaPmgv9iTU385Cc/iVtvvTWq1Wrcc889p12hDAD82wXf\nFnReO/c5LwDjzJDfFgQAnD/BBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsA\nCQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeAC\nQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4\nAJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABII\nLgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAE\nggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEg\nwTmD29nZGbfcckssW7Ysli9fHk888URERPT09ERLS0s0NjbGmjVrolKpDPuwADBalYqiKM72gq6u\nrujq6orrrrsuent746tf/Wo8//zz8dRTT8XMmTPjkUceiW3btsXhw4ejtbX19J2XSsM6PAD8rzlj\nVosv6I477ihefvnloqmpqejq6iqKoijK5XLR1NT0uddGhM1ms9ls42o7k3Me4f6njo6O+PrXvx5/\n/vOfY8GCBXH48OGIf+09rrzyysHHn3GEC8B4c6asnvdFU729vbFhw4bYvn171NbWnvZnpVJJXAHg\nLM4ruCdPnowNGzbE5s2bY/369RERUV9fH11dXRERUS6Xo66ubvimBIBR7pzBLYoi7rnnnmhubo4H\nH3xw8Pl169ZFW1tbRES0tbUNhhgA+Lxzfob7u9/9Lr72ta/FihUrBk8bb926NW688cbYtGlT7Nu3\nLxYuXBg7duyI6dOnn75zp5kBGGfOlNUvdNHUFyW4AIw3F33RFABw4QQXABIILgAkEFwASCC4AJBA\ncAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAk\nEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsA\nCQQXABLUjPQA8L+spqbmtC0iYmBg4LQN4HwILpzFtGnT4oorrhjcIiIqlUocPnx4cAM4H4ILZzFt\n2rSYM2dOzJ8/PxYsWBClUin27dsXnZ2dcfLkScEFzpvgwlnU1tbGnDlzorGxMZqbm2PChAkxZcqU\nGBgYiJ6enpEeDxhFBBfO4rMj3MWLF8eqVatiwoQJcfLkyahUKrFv376RHg8YRQQXzuL48eNx+PDh\nKJfLsXfv3pgwYUIcOHAgenp6oq+vb6THA0YRwYWzOHLkSJTL5cHTyKVSKfbu3Rvlcjl6e3tHejxg\nFBFcOIve3t4ol8sxMDAQlUolIiI+/vjjOHjwYBw5cmSEpwNGk1JRFMWw7bxUGq5dQ4opU6actkX8\n6zTzf24A/+lMWRVcABhCZ8qqr3YEgASCCwAJBBcAEgguACQQXABIILgAkEBwASCB4AJAAsEFgASC\nCwAJBBcAEgguACQQXABIILgAkEBwASCB4AJAAsEFgASCCwAJBBcAEgguACQQXABIILgAkEBwASCB\n4AJAAsEFgASCCwAJBBcAEgguACQQXABIILgAkEBwASCB4AJAAsEFgASCCwAJBBcAEtSM9ACMHzU1\nNTF58uSYPHlyXHLJJTFp0qQ4ceJEnDhxIvr7++PEiRNx6tSpkR4TYFgILmmmTp0aM2bMiBkzZsTM\nmTNj2rRpcejQofj4448HfwouMFad1ynlarUaK1eujLVr10ZERE9PT7S0tERjY2OsWbMmKpXKsA7J\n2DBlypSYNWtWLFq0KFasWBE33nhjLF26NObPnx/Tp0+Pmhr//gPGrvMK7vbt26O5uTlKpVJERLS2\ntkZLS0vs2bMnVq9eHa2trcM6JGPD1KlTTwvuTTfdFM3NzTF//vy44oorBBcY084Z3H/+85/x4osv\nxr333htFUURExM6dO2PLli0REbFly5Z4/vnnh3dKxoQpU6bEzJkz48tf/nIsX748Vq1aFU1NTTFv\n3ry4/PLLY+LEiSM9IsCwOechxUMPPRSPPfZYfPrpp4PPdXd3R319fURE1NfXR3d39/BNyJjR19cX\nH330UezduzemTp0aH3/8cbz33nvR2dkZhw8fjoGBgZEeEWDYnDW4L7zwQtTV1cXKlSvj1Vdf/a+v\nKZVKg6ea4WyOHz8eBw8ejL1790a1Wo0DBw7EP/7xj+js7IxKpRLVanWkRwQYNmcN7uuvvx47d+6M\nF198MY4fPx6ffvppbN68Oerr66Orqytmz54d5XI56urqsuZlFOvr64uDBw9GtVqNTz75JC699NLo\n6emJnp6eqFQqjnCBMa1UfPbB7Dm89tpr8aMf/Sh+9atfxSOPPBIzZsyI73//+9Ha2hqVSuW/Xjjl\nyJf/VFNTE5MmTRq8B7empib6+/vj5MmTgz/dFgSMdmfK6he6LPSzgP7gBz+ITZs2xc9//vNYuHBh\n7Nix4+InZMwbGBiIgYGB6OvrG+lRANKd9xHuBe3cES4A48yZsuq7lAEggeACQALBBYAEggsACQQX\nABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALB\nBYAEggsACQQXABIILgAkEFwASCC4AJBAcAEggeACQALBBYAEggsACQQXABIILgAkEFwASCC4AJBA\ncAEggeACQIKakR7gf8WXvvSlmDp16uBWFEUcO3Ys+vr6oq+vL44fPz7SIwIwigluRJRKpaitrY26\nurqoq6uLWbNmRbVajY8++mhwE1wALobgxr+DO2/evFi0aFFcffXV0d/fHx988EFMnDgxjh07FocO\nHRrpMQEYxQT3/1122WUxd+7caGpqimuvvTZOnDgREyZMiGPHjkVXV9dIjwfAKCe48a8j3EsuuSRq\na2tj5syZMXfu3Dh+/Hjs27cvpk2bFpdccslIjwjAKCe4EVEURRw5ciQOHDgQf/vb32LChAnR398f\nf//736OrqyuOHj060iMCMMoJbpwe3M9OI588eTI6Ozujq6srent7R3pEAEY5wf1/nwX36NGj0d3d\nHadOnYpKpRKVSsURLgAXrVQURTFsOy+VhmvXQ27ixIkxceLEqKmpiYkTJ0ZRFFGtVk/bAOBczpRV\nwQWAIXSmrPpqRwBIILgAkEBwASCB4AJAAsEFgASCCwAJBBcAEgguACQQXABIILgAkEBwASCB4AJA\nAsEFgASCCwAJBBcAEgguACQQ
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 21
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We now construct a mask in which each pixel value gives the distance from the central pixel.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"ys,xs = mgrid[:128,:128]\n",
|
||
|
|
"r = hypot(ys-64,xs-64)\n",
|
||
|
|
"imrow(r)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAHbCAYAAAAXnJnGAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsfV3MbldV9XpR1Cgo8afnBIppopa2tFT+aqIJiNhGjZBG\nsTEQKIoab4wYEyM3SryQQ7wR9MYYgieIYK9qY9DEJtafqIjBiCRq1dBYCT03tSICAqXfhd+ui9k5\nxxhzrrV/3vLM5M2znzXnGHOutfeeY6/n/Tt77LHHHmsnO9nJTnayk51sF3vK3gWc7GQnO9nJTvbF\nbCchPtnJTnayk51sRzsJ8clOdrKTnexkO9pJiE92spOd7GQn29FOQnyyk53sZCc72Y52EuKTnexk\nJzvZyXa06UL8h3/4h+26665r3/It39Le+ta3zqY/2clOdrKTnexJZWczf4/40Ucfbc95znPavffe\n2571rGe1F7/4xe0973lPu/7662elONnJTnayk53sSWVfOpPsr//6r9s3f/M3t2uuuaa11toP//AP\nt9/7vd/7AiE+OzubmfJkJzvZyU52snNh0b53qhB/9KMfbc9+9rMff3/11Ve397///W4xb37zm9sv\n/uIvfkFx3isbQ9gMZ19bFsd4Mvne/va3t5/6qZ+Sa2B1q/Njvsy4mtuLiXC/9Vu/1V7/+tdDfubL\n5KvglHHVr8T9zu/8Tnv1q18t8WxhmYdsFJv12bF3vetd7XWve10a543176s+FB/hPH/m2Bv7jd/4\njfaTP/mT0+roX5mf+ar5qrX0r5cuXWpvetObaO4or1rLl3zJl7TIpgqxeiO++c1vbvfdd19rrbWX\nvOQl7aUvfenjvr1EuCqmvc/DV/MxrkgUMiI4IqAVoUfjiNPOLSO+SMhm4CKfKrRZ/iNbXzfrBeoc\nLY+Xg11LZ2dnMs7mjmIyPpsvwi7jnp9hopies68hytfHoXrQXNkcGMarOaoV1ZkZ9zj73HbtorXv\nX++77772p3/6p+66WZsqxM961rPagw8++Pj7Bx98sF199dVPiFt2wr/wC78giU7GP0OEM7mQOFTz\nRT7Lm8FU8lUEtsJZeZ8VUWWsivN8o2Kq4L1r4clkWSHsRXsLXMXHhFPhRYKFcOzaRMKyjC14dR6q\nD4lq1afms+uDfBGPV8tLX/rSxzeZZ2dn7Zd+6ZfculqbLMQvetGL2j//8z+3Bx54oD3zmc9sv/u7\nv9ve8573uLEveclLymI6W4QrQjUT1x/fcsstMGYtsVVErira6Fj13XzzzSWctQyHivPGtxDiG2+8\n8ZBCzARmjXyt/d+a3XTTTbJI9DjrizjW9CGxyc7Hcr3whS8si5u3TiyfIpiK+K+N+47v+I4Up517\nBhfZ1J+abq21P/iDP2hvfOMb26OPPtre8IY3tDe96U1fmPDsrD366KOPTyIroko8wmd8/WsWl82X\nnZPFVmqJfBVslnMPnxozMsZqytrk23N163cRo1iPK+JXYiv8/fstfVGM9SNfBcP47HEUg2qJcrJa\nsvEKLuNDfqW2pz71qfFD1GwhZrYIsSq0/fiWIozEriKUI+KdxVRzzOJFx3v7lPeMD8Uq46q/GruH\nqQKsxGUE2PMrYs1y7CnIqgh7YxWeET5FyDxsVkwZjnEfQYy/7Mu+7FhC/LnPfa619kTh68Uq8nu+\n6HXEZ/MpeUeEdQbnDN9MniMJcMZnx9VbZG1BPqIYqwLMYqs+G6eIsH1/3nxrCGjWh+JVnkotkTj2\nuD3EOIrpfYcU4khsPMFVxWxEhFXxy+ZT68zMb21flgMdR/EqZpYPxancDJ+Nr8RUYtewjDiOxETN\nVo1X8EcQVxWTFdARbFUoM7FVYWdrtacYR77DCfFnP/vZ1hoXwCOIsCJUVQGtircaO+KLao2wDO/F\nbCnMVeFkt0dVfM+T6Ko2Q5yrPuuvivVeopwV56pgZuMzPlRfRmQrOIZZU4wZZnn/5V/+5eG9PPWn\nplUbFaqZItznzYhetUaEYyKytRhnH0qQj4n92r6sKCJ+Ba9i1ZhM3JbWNyVW3xK7xjzOzvjv0y4W\n5fdwW/j6176+aE7VfGvPg8V681U4FVx0ftkaepyqD+XLXuu77Ig/85nPUMHcSoSr+aq1KDX0NsI5\n26ceV3JUOdW6KoKoCuyoEGdjjyDI6u43E1vdxaJYJTfbla7hU3etKv+WO1/l1YtHu0r2OlKnskse\n8an5vuIrviK8dw+zI1ZFU8ErvtF86lwQDmEQf6YW1afmVWpkuVWcwulhMpwZHOMYFeSswO4lyGzX\nVYmdseOq1Nba2Dpmd3XRcSY2qn3GrrlyHqKdanbnq3AquNaajJ21M87U6tkuQtyaJk7qa8U3km/t\n+qPjtUU5I8aMM3usiqwi3iNjVdEexaj+WZiKzRCuDOdoPq8B9ruYSNQ8XN90M/lQTPWBBglyZs2Q\n2Cm+aA6eOLG5KgKo1hKJo/owNEuMvfMUzv+xre7iJeHZWfv0pz/dWnuiGPWiZP3R64hvRr4ZdTKe\nGbWodVpThVIRyJm45XiGUKr5VP61fMjWvI1ZE6ngtvB5Hx2O5EAfhaJ8W+K82qOPSjP5GD7Do3BV\na2HxEXellmy+r/zKrwzv092E2AqJKhIjIrxWvpE6MzyzOJhPxShcisBmakDjLI8ao/Ki2BFfJmYm\nztoaAqzEZH3KGBLlylhVTFktigBlcyDeEWGdIeaKyGXrPqIYt9baV33VVx1LiD/1qU89aUSYCZbC\n6eFnCyzLZ8fUPGp+FafkYz51TOVXuNf0Idv49l1FnNf2zRDlflwVaCaWSgzDVfKq4ujFriHU1YeD\nijiy2Nli3I8fTog/+clPtta2E+Het6YIMzFFnCquj8v4rBBHmEq+Sm2VGma/V8RXHRv1ZWJm4hRb\nQ3yVmKyPCagXM/KeiSPDzBLXqggv75kYI9+oCKMaRnAK59pibPM97WlPO54QPxlEuCKUIzg1Vpl7\nbyMCr3CoxwpPBjfqU/OxWNVXiZuF82xNAVZiVV+GQxXljM+OZ4XXwyocFfHyamYCk82XFdPZuAwn\nexCZme/pT396eH/u9utLs0RRjd9S9PvXLI7lG8EqgpQVYBXDxrz3SIgrPIpPzZeJy/rVmJm4iKsq\nxswW3qjes7P4V0EQDnFEnCM+G9PHWly/nn08mk/E5+VDtXi8Ud4sJ8sXnQelTpQHrUfkW+as1hr5\nKvmQHeb3iNkrEwokEluK8Mw61LlXXiO8Ug86VjH9vKwp+dj7qk/lZ+OjYovq3dIyuRXRzgipgouE\ngeWYKcqqkCAuJhJI4Psx5lsMiXuWE72yOXjxy/sRwVXFEa0De7jK5kO2qxD3xyPCZ5u655+ZL1OL\nkjcjhtnYioiq+TJxXl0VAdzCp9aCYjONGa1DpcEf1bI7nwquNX8919gN23xMLFHdaqOP8lXqXriq\n58WOjwonyrmVGEdrwgRcyYdstz/o0do8UbR8zD9ThFE9Xk1qPrVOdV7KOmR9an4vjq2VwjPi897P\nHlMbMRLi82SoqVZ3jZ55OzsW6zXbKH7U5zX3vl5FsJlIzRImW1NmZ5vdpSs7zH6dlHyzxRidy9Fa\nkB3mL2uNiKLXAFVxquRDNSABy+Sr4DIclXg2p6jO3pBQKnV6uKoPjSu4TJySM/JlePc0JkB9HLJo\nvpkdrxeLxCLKl/VlxUm1imArPo87s0NVhCqD69+39sRzvaYY23yeiI7kQ3bY7xFnfBnsjHw2b0ZI\nqzUiXNS41xBezxfVyQQOjWfzqT4Fk8GhGpmh+Ez+Pc3bxczc/ar5s01dFeqMz2vwfa5lTN3tqv4R\ncbJ1Kuuh7Jo9DnW33a8V4pm1FihftEbZfMwOuSNeUxRn5bNikxXU6vxQDb1VRXXUF83Dq83zq/kq\nPJ6pHApOvekU/pHYLS0Sm8hmiTTaHaN8yk7Lvs/4UH70cSjDKflGfLYuZceqChGKQTh1/WY9mKyZ\nr78/PDvcjjjrU7FHyYfWQMV5
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 24
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"This expression will compute the distance transform now.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"from scipy.ndimage import morphology,filters\n",
|
||
|
|
"print r.shape\n",
|
||
|
|
"dt = morphology.grey_erosion((1-image)*amax(r),size=r.shape,structure=-r)\n",
|
||
|
|
"imshow(dt)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stdout",
|
||
|
|
"text": [
|
||
|
|
"(128, 128)\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 26,
|
||
|
|
"text": [
|
||
|
|
"<matplotlib.image.AxesImage at 0x4b83a10>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAP0AAAD8CAYAAAC8aaJZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztvV+sXcV1P76uA9K3gjQoUXyvjEFG1NjYgIGaRk2rlsQ1\nSFGgbqDQPwKLklZVVSlEeWhe20rYKA+BlDxFCLlBgvDSlkaEpm4UQsufFjkpEXXqFNnIobYfQt2U\nJC3EPr+HdJx1P/581lqzz7nn3P44S9rae8+smVmzZj5rrZm99zkLo9FoZHOa05zeNrRm1gLMaU5z\nmi7NQT+nOb3NaA76Oc3pbUZz0M9pTm8zmoN+TnN6m9Ec9HOa09uMxgL9U089ZZs3b7aNGzfafffd\nNymZ5jSnOa0gLQx9Tn/q1CnbtGmT7d+/3y688EK77rrr7NFHH7XLL7980jLOaU5zmiAN9vT/+I//\naD/zMz9jGzZssHPPPdd+4zd+w/7qr/5qkrLNaU5zWgE6Z2jB1157zS666KIz9+vXr7cXXnhhGc/C\nwsJwyeY0pzmNRSqIHwz6KqC3bdtm27ZtMzOzq666yq688kobjUY2Go3s9OnTg6+jtIy3KYTxmJl9\n+ctftl/5lV9ZVq6V8XysXZ/neXwa5iMfUrYCe+655+znf/7n07FgY7awsLAsvV1jGqa3NH/0pO/f\nv99uuOEGyq+ONWvWDErHfH9fvf7zP/9zu+uuu8K6fVpWb8bj89XZ837ta1+zZ5555kz6H//xH8t5\nMBj0F154oR09evTM/dGjR239+vVn8W3bts3uvPPOiYE8OnqMwpC6zDjQW7o3Kp63XWfnoaD3hknR\nwsICrQeBORqNlvH6NG8IfBoCHGVrdaxZs+asPM+D+UinT5+mPFk69tvzV65xrCM9eX5Mr/JgPraF\n5Uajkf3SL/2SXX/99Wf0uCKg3759u33729+2I0eO2Lp16+wLX/iCPfroo5R3HPCNA+hKm5kXx+gg\nAr0COeZ5vagzgjQCfhX0LK215XmUl2e8XobMy58+ffrMdZPZ8ynweuoFvm/H52egZCBTZ3bNDE7m\nEDyIsR1Wj58nzBApGgz6c845xx588EG78cYb7dSpU3b33XfTnfurrroq9ZrqWoGXRQNYrgp4JteG\nDRvC8ma2LN8PhgI/RgE+Tw2o4kFat25dCHoEt28rmzQIYlVPIxZqY3tr1qyxDRs20D55Q+BDWOSp\nAt8DPgJ0dt3msa8nK6vAGoG7Gcc1a9Ysaw/LekPsy7LxQRr8yK5CCwsL9jd/8zcl0LVrda4agQjw\n40YbkRFQRovdt7TojHxZmtJ/dO/T0Cv7fMXDgI2gV/zqYEajpWH9Ea9Kz9bilTLVOti6XKUP4Yt4\nzz33XDlPBnv6KiHgfNqkwBwZktbeJAxBJLvKb2nqzK4jXfbq3mz5OhEJPXg7Mw/NeBDgzFNnMnrv\nHHlr7wUVr9JRq8PMlnlR7B+rC88sdFfhPJZlHprJ4KMBFpn4ulXkoGgqoO9de/cAcdIbf5MyAL2A\nx7RInz3EJjPmKeA3HpXX5MkArowEA7LZcpBnYTyWVYbN5zO9RwaEgQnHCoGngIjlIhCrOlndmBfR\nioN+CLBaR9pZAa0X8OPyYPsVnqgvPs/ns7woTRGbABkw/QRTRgHLRFThMVu+9q6mZ7vuXoZGymti\nWQYiNVbIw4xkBG5MR3kqdSNPRDMN7ysg9PzVo/d5fmtjnFDf1+PzmPyez+spOjPeiBTgccIpD4He\nG3mZUVCH5/Ehde8ufMRb9f7sOkpjAFWhdxaSI0DZY0HFH0UOyngoWhXh/bjH0Ed3Q+TCXfvIGKjr\nyiRTExV1i5St3/01Azx6CQ/Ydo3pip+F/Wp97kmt6zNj0HgYEKProeMRjWWlTq8vf62AnHl5vFc0\ns/C+5zHeNAGP6U0OtUHYA37kw3R2VpQZAhbi+TIejP6MkwqvWz3Ky/u61ZrcE278RWE6hvosmmnj\n4z0o6392nT2eYwBj465Cf18G54NaSime3rkzddCztAh8at1eAW0PT69cZtwoYbq/Z9fqPBT0ZvHm\nnc/3oG7pyqP7azYpFUUeuneTzpdV+fiMu7IEYABV4XS7xvRsfc68MvZJrc/ZPTMO1TGZ2pq+56gA\nPlu3j2MUMrki0DPAe14shzxeb6hHpltGOPDRBGNenuUpr+/rY+G+2XKv6fkq4X0W6kf5zDiw60j/\nvo4WZSDoWFk2tll4HuX5elU5lF3R1Dx9E0aBreUrYPlrpohe0E76BZ5Ilpan+oP5vm/sGqnlqfU8\nruUbT+TlVajPvL7yLqPRaBnAIoMQpWc78qy/bJ6o6wz0LMxW9UfrczXWaj5EYX5Wd0RTAX0ThoGL\n5fUArHI9LuB7++DvW1kmGyvn8/DaE0vHicd40bP76x7gq+gBD7VmR4MwzvN47F+PAa2AntXv04eA\n28vpI46KAUDgszojmlp476/VZlkEPHVU1vw9gEcgV+XxfVD5yMP0o3QX6beR8vQ+HyeHAja79m0y\ngHsgK1K7973A79msY/3115lOWFkFbmZ0FGhbnV5eZTwqdbA6GU3N07frHkArYPVs8g0BfK/RaXLh\nvU/318wYYBl2zijiY+BuZViYz9bvvhwDPQIZjQOmRxttnjLgZ8YgMwrMMEdnLBPVU1m3R14cI4ts\nX6Di7acK+qFAykDbyxMBPvP0Xq6oLc/H+oL5XkfReQghqPHs62YhvAcvTjgFUrYEQFBnoPWUATcC\n+zigj6KjCvgingqIGfAzGWfu6ZU1VOthtck3bpRQATwOvOfDtMrBymBapCd2HkJ+EjDwIk9rT4Hf\nk1qzs3oawH0dVeD7/mehPZ4bvwrzo7HAuipeuYenagBYZKbqyGjqnr6ljQvUSQEe75ucLS17TNez\nIel1oNIZz7jk6/AgRm8fresz8Ddi4T3L86CrAB/1gI/b2FoaZWE6RuD4PDVuPWt7tW/Qw8PkipZr\n2ZyZ+kaeT8sA2XgV0Fn9Gaj9tfLwao2ftZHJGMmM+mHncSlbx+PkwQmH4FekwvuWN8TjK+8fGU1/\nHQGblYmAyAwG4xkn9EfdKyMVyapoqs/pm5DtrAA/NJzOjAgDdGX/APvSe7D6fRpeo5489RgAFbL7\nvMi7+zJ4j15YhfdITf4hHp9FCkNAH3lc7BMbF2YwGA8zBj3eXYG7Ev5HNNXn9P7critePAuxo3oy\nILJ2mIdXxkgtCzJwZ4DPJnGFcC3fykdrUBbW+3LtHtfyfrzx7TvmoZXHx7GJ1uG9/Io3q5PxZx4a\nx9inVcsOCf9XjadvAjVSAFBg6wFzBjbWbsV4MCD3yIbtMplUWnStCAcfDYCaLCwsx/zqs/jRaHSW\n5/b5Zss9PrZV0QGu7SN+putoL4DxVdbobCx9XqVeJie79geLWBhNdU3f7jGvF0CVo6e+cTcWsS++\nTtRBZBAinVWAjnpvpECsDIHPZ+t99PJ4qMdybFlQfdYepWeGMvLoyKO8rQIo1h8ZB5amjIavm8mD\n48ryFc1k9z4CQAWUrewknwKwvYesDfT+1ef2Kk3pCa/ZPRLz5Czd8/uwnAE/osaPH6Q0vTCwNmLA\nVxMYddN41G4+nn17yhD48hlAsSy2ifzVNJRRLQWwnK9P0VRBb1YDvveeKx0BZDv0FeD7MtVHeCw/\n0xPLZ8TAgqBHL9/GSoWIzAiwUL/pA8szYGf9jZ7XRyDFfOYd2VgoQ6HSfLvopStlFR/TnzISUf2K\nVgXo2zkC2NCNuqwskwHLYJ4CuHqxKDIUPj/TD9MjI2bpMUxHYHtQe37l6X15zGehfEtXwFf9ZTv2\nystG3teX9zrKAOrrUEYh0icDNKvXp7OwXdWJ6ZmXN5vBG3ksLQPwpB6VZfVUZMnqmdTLOiwv0rEK\n283OXq8qsLK6svYiuRi4MQz38vn62BofwZN531Yf1o2yR7w+nYEv8/TM+7LxYrKpev5PefrMADDg\nMIBFa2msa1zDMQTwvaCPDIHS
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 26
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"print amin(dt),amax(dt)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "stream",
|
||
|
|
"stream": "stdout",
|
||
|
|
"text": [
|
||
|
|
"0.0 66.1891229735\n"
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 27
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"(explanation)\n",
|
||
|
|
"\n",
|
||
|
|
"How does this work?\n",
|
||
|
|
"\n",
|
||
|
|
"- we start with an image having zero at the sources and a large value elsewhere\n",
|
||
|
|
"- at a given location, we subtract the structuring element from each surrounding value\n",
|
||
|
|
"- at zero pixels, this gives the distance from the center of the mask\n",
|
||
|
|
"- elsewhere, it gives a large value\n",
|
||
|
|
"- the minimum over the mask is then the closest distance to a zero pixel"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"If you look at the output image (ignoring the top left and bottom left corners),\n",
|
||
|
|
"the gray values are proportional to the minimum distance of each pixel from\n",
|
||
|
|
"the white pixels in the original image.\n",
|
||
|
|
"That is because we effectively placed a mask on each original white pixel,\n",
|
||
|
|
"and assigned as the output value the minimum of the values in the overlapping masks,\n",
|
||
|
|
"where each value represents the distance to the center of the mask.\n",
|
||
|
|
"\n",
|
||
|
|
"This is a common and very useful operation, but there are much more efficient\n",
|
||
|
|
"ways of computing it."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Distance Transform via the Brushfire Algorithm\n",
|
||
|
|
"============================================="
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"The operation we hinted at above is called the *Euclidean distance transform*.\n",
|
||
|
|
"It assigns, to each input pixel, the distance of that pixel from the nearest\n",
|
||
|
|
"white (or black, depending on the definition) input pixel.\n",
|
||
|
|
"Here is an illustration of that.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"imrow(image,morphology.distance_transform_edt(1-image))"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAA5oAAAGyCAYAAACFlbv5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnV/MrcdV3uc4sUOauFig+lj2CXVDk8ZOhAHFqSioBUVO\nJSQqJFBaqUIGAdfADc0tVxiBVNGmlyjyFWpuSgNCVZtKRFSopBIgJETiSKlDcpzYKeYk8SG2sX16\nAe/ReHk9az1rZt69v3Pe5yd9ev/MzJo1s/9889uzv3Mu3bhx40YTQgghhBBCCCEWcce5ExBCCCGE\nEEIIcXsh0RRCCCGEEEIIsRSJphBCCCGEEEKIpUg0hRBCCCGEEEIsRaIphBBCCCGEEGIpEk0hhBBC\nCCGEEEuZEs3/9t/+W3vPe97T3vWud7Vf+ZVfWZWTEEIIIQbR72YhhBAXgUuj/4/mq6++2v7JP/kn\n7ZOf/GR74IEH2qOPPtp+8zd/sz300EOrcxRCCCEEgX43CyGEuCi8ebThpz/96faP//E/bg8++GBr\nrbV/82/+Tfuv//W/vu6X2aVLl6YTFEIIIXoGPx89BPrdLIQQ4hx4v5uHRfPq1avtHe94x83rK1eu\ntD/8wz8cDSeEEEKISdjfzZ/61Kfaxz72sfaTP/mT7caNGzd/Wmv0daXuTNvtHLW35SiWvW/Lon7Q\n8b//9//eHnvssbTeyNHLCdVDY/Dw7qM+ozhZTJY/+IM/aP/sn/2z4fat5R+e2PLqtb0f1bd1vDaV\n+szxf/yP/9E+9KEPpfW8c6+OrYvqVPqJyrPrSt3Rtk8++WT7qZ/6qXA+qn1Fc8XEzvqx9e+44w56\n3DNl0fPAMiyaKKAQQgghzgP7u/ljH/tY+5M/+ZP2sY99rD3yyCPtkUceaa2dXjI39pbMqF97Xuln\n5DhTN8s9Ou+JxJKNEbWvYMe1Bzdu3Nht3Xrp0qWb+ffnlbbZMWvXWqPj2JiVnGfrZnls42DqstdM\n3a1fO2d9PlGe2zV6jnlxbXkfKyrL+snyZMbkldlYv/d7v9c+9alPpa+rYdF84IEH2he/+MWb11/8\n4hfblStXRsMJIYQQYhL2d/Pjjz/ebty4cfPY2nkks6/HShaqz/blnTNxqseVgmlj2rpZDAsrmqxU\nzIri3qK5gqpEIiFgZbKSg31usHGskG2x2ByysXjSlvWZyfXIdUWuvXxtuZd7Jms2ViSFti3qJ5K8\nSDCzMWWxbty40f7Fv/gX7Qd/8Adv3vulX/olt+2waL7//e9vn/vc59rTTz/d7r///vaf//N/br/5\nm785Gk4IIYQQk7C/m2/cuNEeeeSRk0omEicrRow4ViRzVByZ+u985zupnPvx2fNRac3ieH2ie+cU\nzQceeOAkopktzGepiihqzwpoX++d73xna+2NO2dsPLYvpj4jfGhXEY2BzWNGNrf3QyRyrGCiXUlv\njCi2bcv0a0ESz8TOYlVeR8Oi+eY3v7l99KMfbf/yX/7L9uqrr7af/umf1r9qJ4QQQpyRyu/m7Ouy\nGyNS6bXdrvujrbdSHPeWzBs3btwUTaY9moMR4YziRefo3jlF88qVKycRzRkqX2GttJ/tf+Mf/aN/\nRMVndiOrO4rVr+dWd3IZsavIphertda++7u/O+2ncl0dw2xby4y8MrEigX1d/jd2fHXv+cmREEKI\nY3LRF6UXnUuXLrX/+T//Z2uN27mM6rFix5QxkpmdM/1F99j42RGVse28Nkj+othe/SwGihNxztdk\nZa251bVtsmvUFsWzZUxbdMxioXvo6J2zsZlzVI7qZNd71fWuZ9qiWN79Sh7ZGCv97NnmTW96k/s+\nMLyjKYQQQohbE1aq7H32OqubyVUmqijfc0rmatFk+mVjW1jRjGJE7S8ily7N7SpW4m1lUZ2tfEU/\nVWy7/trLvXKOym2d1rhdSa8uasvUja7tHK2I5d2v5IHG2OPNKarrtfFysXVRzOx5LNEUQgghDkhF\nyNjrrC6qk52z4laVzEz6RkWzeozEcEY2V4jmSPtzky2WR6iKITqOkrXP+o2kz5OjKOcVspmNqSJ2\ns1J4SuFk2lqQFPaxmTlFbVDfjHxm/Uk0hRBCiIPBCpctz66R7CHpZEUwy/MiSaZE89amKldenVHJ\nXC2n0Ri8stbeKBCZqNq2SDa92F4/Wc6zu5/Mdc855JWt3+eY7Xp644rEFvVjc8qQaAohhBAHoypV\nfd3smpHOqE+m32wMjEh652x5VH/kiO5V22b1vLhRn1H7KN65iRb33n0295XiV9mFiqSPyWl0B7Ii\neSjf1mLBtO36+my/jPRV6kc5jcbu8cpmxI8VSzsuVmztfRTTQ6IphBBCHIxRkYquK5LJ5oH6PYdk\n7imaFQHNRBPVidqsEM1q3RXsveMXfV1xpo8tXiR9lR3FkRwYsfWu2bJsx9OOeStH+TFyGNUZjRnV\nRcJYjWVjZOPy2qAxRvGrYpvl7CHRFEIIIQ5IRaRsnf4ayR6qx/YdxbNxo+toLJXyvWRypYx610wZ\nK6osewtn9lVDj2hhzcTfS2qrcUd3YJEgZiKLBI2VzdbeKGfsDioz/orksfczSYxyHN3RjMpGY3mM\nirAtQ+UWiaYQQghxMEYlytZn4iLRrOQRxY6u0VhGJPPcQhkJYiST0TUS0lnRnG0bsVr4mP5ae6Ms\njeTD7lqOSijb/0h5ZR6YncVMNrNcGEGKJLony9vWtTuxNo4XK8rTK4vyimKxu5Qz8lqRW4mmEEII\ncTCqohfVtyJmy7Ic0HlVKrNxVMbsnWfzEsUYaV852vOorNpmVHROKYMMmeAgPKGwMdlYo4wIqs2d\nlbqRcm8+ojnJ8kQiZ8dh73n9jkghs6PJfv11hchVpBA9B6NY3vyhMq88Ek6JphBCCHEwGDFiJdPG\nRfeQHDHSd27JZOpmZdncMke2jD3PrrO6EecWTbToZyQJLZ4Zscx25FbtZjLtshyy2Gg8o7JZOUey\nEwle1C9q09+v7Gja8yjXrB9LVXxRzowkenmyZVt59FySaAohhBAHJJK17BjJXn8v6jsSoUj2Vkpm\nZYxRXLasMr/V9mguo7peGxQjqs/EPCXe4rciR63FOzWoPSuJe4N2Bys5Z7Jp+xuVzT5P77yv593L\n+kVxolis2I1KW1S3Wj+bD1vPG4tXZ2Qn1kOiKYQQQhyM1ZLZxx29ZsqqksnGqs5J1u+saKI4WQy2\nD49INpnrLN6pYGQjk8yZ/pjymd3MSACZnbJKrpW+qrJp227XrMhVJHFUMEel0Xu8+7JT7GhGOXjY\n+bZlXgxGPCWaQgghxMGoSBNbf1Y4s7qskFbz9NqtksxRwWTmCN1jYntUxJIVs9WyyUhhtGAe6Yvd\npZwp9wQO5VHpK2vLxK7UZ+TTlqPrqlCulLNZsWMFlRG7LG4WC5HJsFfG3u+RaAohhBAHIxOkqKwq\nV6sEk+kry3fm3OuDEbqqSFZijpRHsoOuRyRztD6isvO4SjYzZuUzy5MRRiTCjDDaOH1OjGzaMUTy\nacuz61WCWRGoVTuaXn+ZhNu82LheHe8x8fpAcUd2LhESTSGEEOKAVKSpUmbvo2u2bpRjFMs7z+Rt\npWSiOploorZR3jPlXj0mRpXRdsyuyWrYHUFbPytndjXZnKI6TG6VXc6ROCi/bazZ9R47mkg6V+9o\nRv2xO5rZ4+y18XLM5BDND8q5ikRTCCGEOBhVyWSkqq/f98PIXHQd5cDEGhnjiCyyc8OKZnTM6lfL\ns+tIUFlG2lZ2MVdxjj4jvJ1GVoTZcnve9x3JZp+Xl6OlIomrBDP72ifT1hvHih1NL69+/NFcovhe\njlFbZoxMPIREUwghhDgYFVkbkUwkVdW6SMaqsbz2bF5sv8zcRG3ZOLbuivLsOmrHcpHkDTG7c+nV\nrUhha75szYyjMk5mB5fZ6WRzZ3dN2evWOHll8ujbRvVndjRtnb5uJHlZW6/Mey6jsijPbJwWiaYQ\nQghxMFhZWilVM5JZOR9pw8TK
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 28
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"This is closely related to the Voronoi diagram in computational geometry.\n",
|
||
|
|
"In fact, we can see this connection more closely by performing a *feature transform*.\n",
|
||
|
|
"Here, not the distance, but the coordinates of the source pixel, are returned.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"ix = morphology.distance_transform_edt(1-image,return_indices=1,return_distances=0)\n",
|
||
|
|
"imrow(image,ix[0],ix[1])"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAABVkAAAGmCAYAAABm74SVAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3cmPZVli1/Hfne99980xD5kx5lhzdQ3dXRZdltX2oiUL\nyZJhY/fC/AHgBWbrFYVAQkbgHQuvEL2CNm1hyYu2hJg2CATYNCDKNK2usuSuzIx48x1YpM+p9yKy\ncojpTd+PdJUZ9aoiTtyKeOfd3zv3d5yyLEsBAAAAAAAAAC7EnfYAAAAAAAAAAGCeEbICAAAAAAAA\nwCUQsgIAAAAAAADAJRCyAgAAAAAAAMAlELICAAAAAAAAwCUQsgIAAAAAAADAJVwqZP3X//pf6/79\n+7pz547+3t/7e1c1JgAAlhrzKwAA14M5FgBwXZyyLMuL/Id5nuvevXv6oz/6I+3s7Oj999/XP/tn\n/0wPHjy46jECALA0mF8BALgezLEAgOvkX/Q//I//8T/q+PhY+/v7kqS//tf/uv7lv/yXExOU4ziX\nHiAAYLFd8L2+hcX8CgC4Csyv5zHHAgCuwlfNsRcOWX/yk5/o1q1b9uPd3V39h//wHy766QAAgF5+\nfv3Od76j//7f/7uazaYePXqkR48eqdfrqSgK5Xmuoii4wAYAYMzLzrG//uu/rv/6X/+rfu7nfk5p\nmqpSqSgMQzmOI9d15TgOYexz/OEf/qF+6Zd+adrDmEucu4vhvF0c5+7V/eZv/uZXPnbhkJVJBQCA\nq/ey8+uPfvQjPXr0SKPRSEEQqNVqKYoiDQYDe+R5fs2jBQBgfrzsHPuf//N/1ueff65/9+/+nfb2\n9nTnzh073wZBIN/3uR4GgCXxv/7X/9L//t//+6X+3QuHrDs7O/rxj39sP/7xj3+s3d3di346AACg\nl59f7969q6IodOvWLQ0GAw2HQ0VRpNPTU5VlqeFweJPDBgBg5r3sHPvWW2/pv/yX/6K3335bvu+r\n0+koDEPFcSxJ8jzvxsYMAJiu4+NjHR8f24//8A//8Cv/XfeiX+S9997T//yf/1OffvqphsOh/vk/\n/+f65V/+5Yt+OgAAoFebX1dXVxXHsWq1mprNpprNptI0VRRFct0LT/EAACykV5ljNzY2NBqNNBgM\n1Ol01O12NRgMlGUZdTwvcHR0NO0hzC3O3cVw3i6Oc3e1LryS1fd9/eN//I/1S7/0S8rzXL/xG7/B\nrowAAFzSq8yvq6urkp6uqAmCQEVRKEkSWxfgeZ7tZ83znItCAMBSe5U5dmNjQ0VRqCgKSU+rBkxV\ngJlzXdelo/UZxld84dVw7i6G83ZxnLur5ZTXeMXFRAMAeBGCv1fnOI6+853vnPvnZrXN6empOp2O\ner2e+v2+BoOB+v2+vVAEACw+5teLcRxHv/7rv37un/u+rziOFUWRoihSGIa2ozUIAq59AWBJ/OZv\n/uZXzrEXXskKAABmi+d5iqJIjuMoDENFUaSTkxPb0UrICgDAxZRlqdFopLIslWWZsixTHMdyHIeN\nsAAAkghZAQBYGJ7nKY5jhWGoSqWiMAxtwMrFHwAAF1cUhUajkbIsk+M4yvPcBqysGgYASISsAAAs\nDMdx5Hme3fU4z3MlSaI0Te3mHXme24OLQgAAXk5ZlhPz5nA4tB2tphvddLSy+SQALCdCVgAAFpRZ\n2VqtVuU4zrmOVkJWAAAuxtQHmPmUjlYAACErAAALaryjNYoidTod29E6GAymPTwAAOaWqQ+goxUA\nYBCyAgCwoMxK1iiKVBSFgiBQURQaDodyXVd5nk97iAAAzCU6WgEAZxGyAgCwoExHqxFFkZIk0XA4\npKMVAIBLONvROhqNNBwObUer7/tyXVee59HRCgBLgpAVAIAl4XmekiRRURRyXdd2tJqDkBUAgIsx\nK1vpaAWA5UXICgDAkvB93/bFhWGoMAxtbQAdrQAAXBwdrQAAQlYAAJaE6WgNw1BlWcr3fRVFocFg\nwMUfAACXYELW0Wh0rqMVALAceMYHAGAO1Wo1u1omz3NlWfbC2/0dx5HjOLYbznS0pmmqLMs0HA7t\n56OjFQCwrL744gu5rqsgCOT7vu1XfZ6X7Wg1Pa0AgMVDyAoAwBxaXV213W/9fl9FUSjP81f6HKY+\noFaryfO8iY7WXq93TSMHAGC2ffbZZwrDUJVKRWmaqlKpvPLmVWc7WoMgsD2trutyBwkALCBCVgAA\n5tDKyooGg4GePHlib/m/SMiaJImtETg9PbUdrWyEBQBYVp999pmSJFGr1ZLruoqi6JVv+zchq/kz\njmOVZSnHcRQEwTWNHAAwTYSsAADMoXa7rV6vp6IoNBwO1el0XvlzmHA1iiKVZSnP8+wmWKywAQAs\nq88//1zValWu6yqOYxVF8cqfw8zPpqqnKAobsJqwFQCwWAhZAQCYQ0EQaDQayfO8C992aC78jCiK\nVKlUbDfrcDi0fa9Zll3l8AEAmFnD4VCj0Uh5nqsoigvd2WH+G/NnlmW2PsB1XTpaAWABEbICAABJ\nX3a01uv1iY7WXq/HRlgAAFxCnud2ZSsdrQCwmAhZAQCApMmO1iiKznW0AgCAi/mqjlbXdeloBYAF\nQcgKAAAkfdnRai78TEdrv9+3K28AAMCrM9UDZsVqURQErACwYAhZAQCYU67rKgxDJUmier2uIAhs\nf2qWZa8cip7taDWfu1qtKs9zjUajic8PAMCiMm8ynpycKAxDDYdDBUEg3/ftLf6vqizLiY7W4XBo\nu9U9z5v4OwBg/hCyAgAwp1zXVRRFqtVq9hZ/06NaFIXyPL/U5zf1AWZVq+lnpaMVALDo8jxXr9fT\n48ePVRSFut2u0jRVmqY2DL2MoihsR2tRFArD0Ha0ErICwHwiZAUAYE6Z2/tN2BqGoTzPU1EUGgwG\nVxaymq9zcnIix3GUZRkdrQCAhWZC1qIo1Ov1VKvVlOe5PM9TkiRX8vmHw6HtaDVvXrquq7Is2QgL\nAOYQISsAAHPKrKQJw1DS09v7TcDa6XQu/fl935fv+xObc7AJFgBgGWRZZoNWx3E0GAxswFoUxaU/\nv+loHY1GdjXr+JwOAJg/hKwAAMyx8R5V13Xluu6VrX4xn8f8SUcrAGCZjHeomlD0KqtyzOcqy9J2\ntJpQl45WAJg/hKwAAOCljHe0+r5v+1l7vR4hKwAAl2A6Ws3fTT+rqQICAMw+QlYAAPBSTMhq/nzy\n5IntaO31etMeHgAAc+tsR+v4xpMAgPlAyAoAAF5KEAQTq1kJWAEAuBrjHa2SbBc6Ha0AMD8IWQEA\nWBCu6yqKIqVpqizLNBgMbG/qaDS6kh658Z7WIAhUqVTs5x7/WtQHAAAWidkE6/Hjx/J9X5VKxd7O\nHwSBXNe99NcYn6fNylY6WgFgfhCyAgCwIDzPUxRFqtVq8jxPvV5P3W5XvV5PeZ4rz/Mr/XpBEDyz\no1USISsAYKGYOzceP36sPM9VrVaVpqmq1aoNP6+SCVklOloBYF4QsgIAsCA8z1McxzZsjaJIjuMo\nz3P1+/0r/3pnO1pPTk4kyd7qCADAosjzXN1uV1mWqdvtqt/vK89zu6r1Or7ecDhUnucajUaK41hJ\nkhCwAsAMI2QFAGBBmFsJoyiS9HSlqakNuOoVNubzB0Fgb290HEej0YiOVgDAwsmybKKHfDgc2oC1\nKIor/3rjd6A4jmM3wTJzPABg9hCyAgCwYMZ7U83fb+LrmfqAer0uSXS0AgAWjnljsSzLK+k6f9mv\nOd7RKsl2s5oDADB9hKwAAOBKmI2wzN9NH6xERysAAJcx3tGaZZnCMFQYhoqiiJAVAGYEISsAALgS\n47stmz8lOloBALis8Y7W4XCoJEnkOI5837fzLQBgughZAQDAlTAdrUmS2Nsox29tBABgEd1EbcDZ\njlYTsIZheO1fGwDwcghZAQBYUJ7nKY5j1Wo1FUWhwWCg0Whkj+u+KDQrWrMss5timYP6AADAPMuy\nTN1uV48ePZLrukqSxN7CH4bh
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 29
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"If we just want the Voronoi region corresponding to the source pixel at (64,64), we can ask for it as follows.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"imrow(image,(ix[0]==64)*(ix[1]==64))"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAA5oAAAGyCAYAAACFlbv5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3WuMXHd9//HP3M7c7/fLmTlzn51d78XetXPDMY0cJETS\nlKRpixQiBPRBVQkQEvRpnhBHVCpB9BFCyPojAXmUBkRRGyGjVlwqFAoRTeuIZB1jxw6NsyZ2Yju2\n5/+g3WnW6/ue2bM7835JR9H6jHe/ObL92/eey7gGg8FAAAAAAADYxO30AAAAAACA8UJoAgAAAABs\nRWgCAAAAAGxFaAIAAAAAbEVoAgAAAABsRWgCAAAAAGy1odD84Q9/qF6vp3a7raeeesqumQAAwG1i\nbQYAbAWu230fzUuXLqnb7er5559XuVzW0tKSvv3tb2tqasruGQEAwE1gbQYAbBXe2/2N//Zv/6ZW\nqyXLsiRJf/7nf65/+Id/WLOYuVyuDQ8IAMD73ebPRycCazMAwAlXW5tv+9LZY8eOyTTN4ceVSkXH\njh273U8HAAA2iLUZALBV3HZo8hNRAAC2FtZmAMBWcduhWS6XdfTo0eHHR48eVaVSsWUoAABw61ib\nAQBbxW2H5uLiol5++WUtLy/rwoUL+u53v6sHH3zQztkAAMAtYG0GAGwVt/0wIK/Xq6997Wv60Ic+\npEuXLumTn/wkT7UDAMBBrM0AgK3itt/e5KY+OfeKAABsxlNnN4a1GQBgN1ufOgsAAAAAwNUQmgAA\nAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAA\nAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAA\nAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAA\nWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABb\nEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsR\nmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGaAAAAAABbEZoAAAAAAFsRmgAAAAAAWxGa\nAAAAAABbEZoAAAAAAFsRmgAAAAAAW3mdHgAAAAAAsPX5fD4FAgEFg0EFAgF5vV698sorV30toQkA\nAAAAuKFQKKRCoaB8Pq9CoaBwOHzN0OTSWQAAAADADQWDQRWLRU1NTemOO+7Q3r17r/lazmgCAAAA\nAG4oFAqpWCyq1+tpz549KhQK13wtoQkAAAAAWMfn88nv9ysQCMjv96tarapWq8myLFmWpWKxeM3f\nS2gCAAAAANYJhULK5/PK5XLK5/NqNBpqt9vK5XLy+/3X/b2EJgAAAABgnXA4rFKppE6no06no2q1\nqmKxSGgCAAAAAG5PKBRSqVTS1NSUdu/erVKppGAwqFAoRGgCAAAAANbz+XwyDGO4ud1r35SkUqmo\nWq2q0Wio1Wopl8vd9OcmNAEAAABgAkWjUWWzWeVyOeVyOfl8vjX7K5WK2u22stmsDMO4pc9NaAIA\nAADABIpGozJNU+12W+12W4FAYM3+VCqlUqlEaAIAAAAAbk4kElGlUtH09LSWlpYUiUTW7Pf7/QqF\nQgqHw4QmAAAAAGA9n8+3ZisWi6pWq2q1Wur1eorFYrZ9LUITAAAAACZALBZTJpNRJpNRNptVp9NR\ns9lUOp2W12tvGhKaAAAAADABVu/JbDabarVaMk1T5XKZ0AQAAAAA3J5YLKZqtaodO3Zo165dSqfT\nCofDikQi8ng8tn4tQhMAAAAAxpDX612z5fN5VatVdTodzc7OKhQKje5rj+wzAwAAAAAcE4/HlU6n\nlU6nlclkNDU1pXq9rlQqJbfbPdKvTWgCAAAAwBiKx+Oq1WpqNBpqNpsyTVOVSkWpVMr2S2WvRGgC\nAAAAwBiKx+OqVquanZ3Vzp07lUwmFYlERnJP5pUITQAAAADYhjwez5rtStlsVrVaTb1eTzt37pRh\nGJs2G6EJAAAAANuM2+1WMplUOp1WKpVSKpVa95rp6WlZlqVkMjnyezKvRGgCAAAAwDbjdruVSqVk\nWZYajYYsy1r3mkqlItM0lUwm5XK5NnU+QhMAAAAAthmXy6VkMql6va75+XnNzc2te000GlUsFlM0\nGuWMJgAAAABgPbfbLbfbLZfLpWAwqEwmI8uyNDMzoz179jg93ho3zNqjR4/qgx/8oKanpzUzM6Ov\nfvWrkqRTp05p//796nQ6uv/++7WysjLyYQEAmHSsywAwmTwej1KplOr1uhYWFvSBD3xAO3bsULVa\nVTwed3q8dVyDwWBwvRecOHFCJ06c0Pz8vM6cOaNdu3bp2Wef1Te/+U1lMhl94Qtf0FNPPaW33npL\nBw4cWPvJN/k6YADA+LvBsjX2NrIuS6zNALBdGYYhy7JUr9dVr9dlWZaq1epwM03TkblcLtdV1+Yb\nntEsFAqan5+XJEUiEU1NTenYsWN67rnn9Pjjj0uSHn/8cT377LM2jwwAAK7EugwAk2n14T/vP6M5\nOzu7Zc9o3tI9msvLy/rlL3+pPXv26OTJk8rn85KkfD6vkydPjmRAAABwdazLADBeXC7X8MqTK69A\nMQxDmUxGjUZDc3NzW+6ezCvddGieOXNGDz/8sJ5++mlFo9E1+95/QAAAwOixLgPAePH5fEokEkok\nEkomk4pEImv2BwIBzczMyDRNxWIxh6aUDh06pEOHDt3wdTcVmu+9954efvhhPfbYY3rooYck/c9P\nS0+cOKFCoaDXX39duVxuQwMDAICbw7oMAOPH5/Mpm82qVqvJsqzhVSqr90AahqFarSbTNNf9gHEz\n7du3T/v27Rt+/MQTT1z1dTcMzcFgoE9+8pPq9/v67Gc/O/z1Bx98UAcPHtQXv/hFHTx4cLjQAQCA\n0WFdBoDx5PP5lMlk1Gq1NDc3p2azuWa/x+NRIpFQPB539IzmzbrhU2f/9V//VXv37tXs7OzwMpwn\nn3xSu3fv1qOPPqrXXntNlmXpmWeeUSKRWPvJuWwHAGCzSX/q7EbWZYm1GQC2qkwmo7179+ree+/V\n3r17NTc3d9XXbbV/x6/11NkbhuZGvygAAHaa9NDcKNZmANgaDMNQPB4fbqVSSXNzc5qfn9f8/Py6\nM5pb1bVC85aeOgsAAAAA2DjDMJTNZlWtVlWr1Yb3ZpbLZYXDYafH2zBCEwAAAAA22Wpottttzc7O\nqt1uK5lMKpFIEJoAAAAAgFtnGIZyuZza7bYWFxfV7/fldrvlcrnkdrudHm/DCE0AAAAAGDHDMBSL\nxYZbpVJRt9tVuVxWPB6XYRhOj2grQhMAAAAARiwQCCifz8s0zeF9mfV6XaVSSaFQyOnxbEdoAgAA\nAMCI+f1+5fN5dTod7dixQ41GQ6lUSqlUaizuybwSoQkAAAAAI+b3+5XL5dTpdLR7926122253W55\nPJ6xuCfzSoQmAAAAAGxQIBBQNBodblfec5nP59Vut1Uul5VIJBQMBh2adHMQmgAAAACwQcFgUMVi\nUZVKRZVKRbFYbM3+eDyuZrOpYrE49pEpEZoAAAAAsGHBYFCFQkG9Xk/T09PKZrPr9qfTaaXT6bF8\n+M+VCE0AAAAA2KBQKKRisaher6c9e/aoUqms2b96P6bX65XXO/4ZNv7/hwAAAABgs0AgoEgkonA4\nrEgkolarpWazqXK5rHQ6rXg87vSIjiI0AQAAAOAWrZ7BrFQqKpfLsixLrVZLuVxOfr/f6fEcR2gC\nAAAAwC0KhUIqlUqamppSv9+XaZrKZrPKZDKEpghNAAAAALhl4XB4GJp33nmnSqWSfD6fvF6vfD6f\n0+M5jtAEAAAAgCsEg0GFw2GF
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 30
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"The Euclidean distance transform is closely related to binary morphological operations\n",
|
||
|
|
"with circular structuring elements: the latter are simply a thresholding of the former.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"imrow(morphology.distance_transform_edt(1-image)<10)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAHYCAYAAACRCOtoAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X9s2/Wdx/GXke2UxD17tE4a2w0ZjdsmaZPSFaZO2rG7\nKEVCo+sAMWBiFaA7aQjdmKbBSfd3m3Cc7uBu99cOtmg7rfDHCXpTF/W6adxOlEHpXTpITnFKkzZ2\nkuZHv16dtLVdvvdHL6Zx2rS4zvfj2M+H9BWNv26+73xJ8qo/H38+b5dt27YAAIARt5kuAACASkYQ\nAwBgEEEMAIBBBDEAAAa5nbyYy+Vy8nIAAJSEpd4XzStiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAM\nIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAA\ngwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwKAlg/jpp59WXV2dtm7dmnvshz/8\noZqbm9Xe3q6HHnpIyWQyd66rq0vRaFSbN2/W4cOHl69qAADKhb2E//zP/7SPHz9ub9myJffY4cOH\n7cuXL9u2bdsvvvii/eKLL9q2bdsff/yx3d7ebqfTafvUqVP2hg0bcs+bJ4mDg4ODg6PijqUs+Yr4\nq1/9qr7whS8seKyzs1O33Xblr335y1/W6OioJOntt9/W448/Lo/Ho8bGRjU1Nen9999f6tMDAFDx\nbmmO+PXXX9cDDzwgSUokEopEIrlzkUhE8Xj81qoDAKDMFRzE+/btk9fr1RNPPHHd57hcrkI/PQAA\nFcFdyF/66U9/qkOHDunXv/517rFwOKwzZ87kPh4dHVU4HL71CgEAKGdLziDbtn3q1KkFb9b61a9+\nZbe0tNiTk5MLnjf/Zq1Lly7Zn3zyiX3XXXfZn376KW/W4uDg4OCo+GMpS5597LHH7Pr6etvj8diR\nSMR+7bXX7KamJruhocHetm2bvW3bNvu73/1u7vn79u2zN2zYYG/atMnu7e1dfLESuBkcHBwcHBxO\nH0tx/X9AOoI5YwBAJVoqatlZCwAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYA\nwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogB\nADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhi\nAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCC\nGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCI\nIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAg5YM4qef\nflp1dXXaunVr7rGZmRl1dnZq48aN2rVrlyzLyp3r6upSNBrV5s2bdfjw4eWrGgCAMrFkED/11FPq\n7e1d8Fh3d7c6Ozs1ODiojo4OdXd3S5L6+/v1xhtvqL+/X729vXr22Wf16aefLl/lAACUgSWD+Ktf\n/aq+8IUvLHjs4MGD2rt3ryRp7969euuttyRJb7/9th5//HF5PB41NjaqqalJ77///jKVDQBAefjc\nc8QTExOqq6uTJNXV1WliYkKSlEgkFIlEcs+LRCKKx+NFKhMAgPJ0S2/WcrlccrlcS54HAADX97mD\nuK6uTuPj45KksbEx1dbWSpLC4bDOnDmTe97o6KjC4XCRygQAoDx97iDevXu3enp6JEk9PT3as2dP\n7vEDBw4onU7r1KlTisViuvfee4tbLQAA5cZewmOPPWbX19fbHo/HjkQi9uuvv25PT0/bHR0ddjQa\ntTs7O+1z587lnr9v3z57w4YN9qZNm+ze3t5Fn08SBwcHBwdHxR1Lcf1/QDqCOWMAQCVaKmrZWQsA\nAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAG\nAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKI\nAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMI\nYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAg\nghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAw\niCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMCggoO4q6tLra2t2rp1q5544gldunRJMzMz6uzs1MaN\nG7Vr1y5ZllXMWgEAKDsFBfHw8LB+/OMf6/jx4/rDH/6gy5cv68CBA+ru7lZnZ6cGBwfV0dGh7u7u\nYtcLAEBZKSiI/+RP/kQej0dzc3PKZrOam5tTKBTSwYMHtXfvXknS3r179dZbbxW1WAAAyk1BQXzH\nHXfoBz/4gRoaGhQKhRQIBNTZ2amJiQnV1dVJkurq6jQxMVHUYgEAKDcFBfHJkyf1yiuvaHh4WIlE\nQqlUSj//+c8XPMflcsnlchWlSAAAylVBQXzs2DF95Stf0Zo1a+R2u/XQQw/p6NGjWrduncbHxyVJ\nY2Njqq2tLWqxAACUm4KCePPmzXrvvfd04cIF2batI0eOqKWlRQ8++KB6enokST09PdqzZ09RiwUA\noNy4bNu2C/mLf/u3f6uenh7ddttt2r59u/7lX/5F58+f16OPPqrTp0+rsbFRb775pgKBwGcXY6ga\nAFCBloragoO4EAQxAKASLRW17KwFAIBBBDEAAAYRxAAAGEQQAwBgEEEMAIBBBDEAAAYRxAAAGEQQ\nAwBgEEEMAIBBBDEAAAYRxAAAGEQQAwBgEEEMAIBBBDEAAAYRxAAAGOQ2XQCAm+dyueTxeHKH0z2+\ns9msMpmMstmsstmso9cGyhVBDKwgXq9X9fX1CoVCCoVC8nq9jl5/ampKiURCY2Njmp6edvTaQLki\niIEVxOPxKBwOq729Xe3t7aqurnb0+idPnlRfX5/m5uYIYqBICGJgBfF6vQqFQmpvb1dHR4cCgYCj\n1z927JhmZ2c1MjLi6HWBckYQAyXO5/PJ7/fL7/crHA6rublZd955p2pra7V69WpHawmHw4pGo5qc\nnJQkWZalZDKpZDLJnDFQIIIYKHGBQEBNTU25IxqNKhQKye12/sd3vhZJCgaDGhoaUiwW0+zsLEEM\nFIggBkrcfPjt3LlTbW1tCgQCCgQC8ng8RmqJRqMKBoNqaGhQTU1Nbqj64sWLjtcDlAOCGCgBbrdb\nHo9Hbrd70Svd+vp6RaNRbdu2Tdu3bzdU4RU+n08+n0+RSEShUEjJZFLxeFyxWGxB3bZtK5PJ5A7b\ntg1WDZQ2ghgoAYFAILcsac2aNQvOzQ9J+/1+Q9Vdm9frzb2DW5JmZ2dz5y5dupRb5pRIJJROp02V\nCZQ8ghgoAfNDvu3t7brrrrsWnFu7dq3C4bDj75C+EY/Ho1AoJOnKfPHVYZtKpXTixAlJ0uTkJEEM\nLIEgBkrAfBDv3Llz0fCz2+2W1+s1Mie8lPmlVMFgUM3NzQuGn8+dOydJOnv2rAYGBkyVCKwIBDFQ\nAtxut6qrq+X3+xcNTZcql8ulqqoqVVVVXfO8z+dTVVWV49twAisNTR+AEsEbmoDKRBADAGAQQ9OA\nAfldlFavXq3bb7/dyCYdy8Hlcsnr9aqmpkaBQICuTcASyuOnHlhh8rsotbS0lOQSpULlL20aGRmh\naxNwHQQxYEB+F6WGhoaSXKJU
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 25
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Brushfire Algorithm"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Let's look at how the brushfire algorithm is implemented. \n",
|
||
|
|
"\n",
|
||
|
|
"We start with some useful variables and coordinate arrays.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"h,w = image.shape\n",
|
||
|
|
"ys,vs = mgrid[:h,:w]"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 126
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"During the algorithm, we keep track of the source of each pixel (the closest \"on\" pixel) in the `sources` array.\n",
|
||
|
|
"\n",
|
||
|
|
"We also keep track of the shortest distance to a particular point so far in the `dists` array (initialized to a large value).\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"sources = 9999999*ones((h,w,2))\n",
|
||
|
|
"dists = 9999999*ones((h,w))"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 127
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"At the location of the source pixels, the `sources` is the coordinates of the pixel itself and the distance is zero.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"for u,v in zip(ys[image>0],xs[image>0]):\n",
|
||
|
|
" sources[u,v,0] = u\n",
|
||
|
|
" sources[u,v,1] = v\n",
|
||
|
|
" dists[u,v] = 0"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 128
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We build a little iterator to find the neighbors of a current pixel.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"def neighbors(p):\n",
|
||
|
|
" for i in range(-1,2):\n",
|
||
|
|
" for j in range(-1,2):\n",
|
||
|
|
" q = array([i,j])+p\n",
|
||
|
|
" if i==0 and j==0: continue\n",
|
||
|
|
" if amin(q)<0: continue\n",
|
||
|
|
" if q[0]>=h: continue\n",
|
||
|
|
" if q[1]>=w: continue\n",
|
||
|
|
" yield q "
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 129
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We also need a FIFO queue.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"class FIFO:\n",
|
||
|
|
" def __init__(self):\n",
|
||
|
|
" self.left = []\n",
|
||
|
|
" self.right = []\n",
|
||
|
|
" def __len__(self):\n",
|
||
|
|
" return len(self.left)+len(self.right)\n",
|
||
|
|
" def push(self,x):\n",
|
||
|
|
" self.left.append(x)\n",
|
||
|
|
" def pop(self):\n",
|
||
|
|
" if len(self.right)<1:\n",
|
||
|
|
" while(len(self.left)>0): self.right.append(self.left.pop())\n",
|
||
|
|
" return self.right.pop()"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 130
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We initialize the FIFO queue with the initial pixels in the source array.\n",
|
||
|
|
"\n",
|
||
|
|
"This says that the neighbors of these pixels need to be updated.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"fifo = FIFO()\n",
|
||
|
|
"for p in zip(ys[image>0],xs[image>0]):\n",
|
||
|
|
" fifo.push(p)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 131
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"The main loop of the algorithm takes a pixel from the queue of pixels whose neighbors need to be updated, and then checks whether we have found a shorter path to any neighbors than we previously knew about. If yes, we update its info and add the new pixel to the queue.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"while len(fifo)>0:\n",
|
||
|
|
" p = fifo.pop()\n",
|
||
|
|
" source = sources[p[0],p[1]]\n",
|
||
|
|
" for q in neighbors(p):\n",
|
||
|
|
" ndist = norm(q-source)\n",
|
||
|
|
" if ndist<dists[q[0],q[1]]:\n",
|
||
|
|
" y,x = q\n",
|
||
|
|
" dists[y,x] = ndist\n",
|
||
|
|
" sources[y,x,0] = source[0]\n",
|
||
|
|
" sources[y,x,1] = source[1]\n",
|
||
|
|
" fifo.push(q)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [],
|
||
|
|
"prompt_number": 132
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"imshow(dists)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "pyout",
|
||
|
|
"prompt_number": 133,
|
||
|
|
"text": [
|
||
|
|
"<matplotlib.image.AxesImage at 0x56cf850>"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAP0AAAD8CAYAAAC8aaJZAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJztvV+sXcV1P76uA9K3gjQoUXyvjEFG1NjYgIGaRk2rlsQ1\nSFGgbqDQPwKLklZVVSlEeWhe20rYKA+BlDxFCLlBgvDSlkaEpm4UQsufFjkpEXXqFNnIobYfQt2U\nJC3EPr+HdJx1P/581lqzz7nn3P44S9rae8+smVmzZj5rrZm99zkLo9FoZHOa05zeNrRm1gLMaU5z\nmi7NQT+nOb3NaA76Oc3pbUZz0M9pTm8zmoN+TnN6m9Ec9HOa09uMxgL9U089ZZs3b7aNGzfafffd\nNymZ5jSnOa0gLQx9Tn/q1CnbtGmT7d+/3y688EK77rrr7NFHH7XLL7980jLOaU5zmiAN9vT/+I//\naD/zMz9jGzZssHPPPdd+4zd+w/7qr/5qkrLNaU5zWgE6Z2jB1157zS666KIz9+vXr7cXXnhhGc/C\nwsJwyeY0pzmNRSqIHwz6KqC3bdtm27ZtMzOzq666yq688kobjUY2Go3s9OnTg6+jtIy3KYTxmJl9\n+ctftl/5lV9ZVq6V8XysXZ/neXwa5iMfUrYCe+655+znf/7n07FgY7awsLAsvV1jGqa3NH/0pO/f\nv99uuOEGyq+ONWvWDErHfH9fvf7zP/9zu+uuu8K6fVpWb8bj89XZ837ta1+zZ5555kz6H//xH8t5\nMBj0F154oR09evTM/dGjR239+vVn8W3bts3uvPPOiYE8OnqMwpC6zDjQW7o3Kp63XWfnoaD3hknR\nwsICrQeBORqNlvH6NG8IfBoCHGVrdaxZs+asPM+D+UinT5+mPFk69tvzV65xrCM9eX5Mr/JgPraF\n5Uajkf3SL/2SXX/99Wf0uCKg3759u33729+2I0eO2Lp16+wLX/iCPfroo5R3HPCNA+hKm5kXx+gg\nAr0COeZ5vagzgjQCfhX0LK215XmUl2e8XobMy58+ffrMdZPZ8ynweuoFvm/H52egZCBTZ3bNDE7m\nEDyIsR1Wj58nzBApGgz6c845xx588EG78cYb7dSpU3b33XfTnfurrroq9ZrqWoGXRQNYrgp4JteG\nDRvC8ma2LN8PhgI/RgE+Tw2o4kFat25dCHoEt28rmzQIYlVPIxZqY3tr1qyxDRs20D55Q+BDWOSp\nAt8DPgJ0dt3msa8nK6vAGoG7Gcc1a9Ysaw/LekPsy7LxQRr8yK5CCwsL9jd/8zcl0LVrda4agQjw\n40YbkRFQRovdt7TojHxZmtJ/dO/T0Cv7fMXDgI2gV/zqYEajpWH9Ea9Kz9bilTLVOti6XKUP4Yt4\nzz33XDlPBnv6KiHgfNqkwBwZktbeJAxBJLvKb2nqzK4jXfbq3mz5OhEJPXg7Mw/NeBDgzFNnMnrv\nHHlr7wUVr9JRq8PMlnlR7B+rC88sdFfhPJZlHprJ4KMBFpn4ulXkoGgqoO9de/cAcdIbf5MyAL2A\nx7RInz3EJjPmKeA3HpXX5MkArowEA7LZcpBnYTyWVYbN5zO9RwaEgQnHCoGngIjlIhCrOlndmBfR\nioN+CLBaR9pZAa0X8OPyYPsVnqgvPs/ns7woTRGbABkw/QRTRgHLRFThMVu+9q6mZ7vuXoZGymti\nWQYiNVbIw4xkBG5MR3kqdSNPRDMN7ysg9PzVo/d5fmtjnFDf1+PzmPyez+spOjPeiBTgccIpD4He\nG3mZUVCH5/Ehde8ufMRb9f7sOkpjAFWhdxaSI0DZY0HFH0UOyngoWhXh/bjH0Ed3Q+TCXfvIGKjr\nyiRTExV1i5St3/01Azx6CQ/Ydo3pip+F/Wp97kmt6zNj0HgYEKProeMRjWWlTq8vf62AnHl5vFc0\ns/C+5zHeNAGP6U0OtUHYA37kw3R2VpQZAhbi+TIejP6MkwqvWz3Ky/u61ZrcE278RWE6hvosmmnj\n4z0o6392nT2eYwBj465Cf18G54NaSime3rkzddCztAh8at1eAW0PT69cZtwoYbq/Z9fqPBT0ZvHm\nnc/3oG7pyqP7azYpFUUeuneTzpdV+fiMu7IEYABV4XS7xvRsfc68MvZJrc/ZPTMO1TGZ2pq+56gA\nPlu3j2MUMrki0DPAe14shzxeb6hHpltGOPDRBGNenuUpr+/rY+G+2XKv6fkq4X0W6kf5zDiw60j/\nvo4WZSDoWFk2tll4HuX5elU5lF3R1Dx9E0aBreUrYPlrpohe0E76BZ5Ilpan+oP5vm/sGqnlqfU8\nruUbT+TlVajPvL7yLqPRaBnAIoMQpWc78qy/bJ6o6wz0LMxW9UfrczXWaj5EYX5Wd0RTAX0ThoGL\n5fUArHI9LuB7++DvW1kmGyvn8/DaE0vHicd40bP76x7gq+gBD7VmR4MwzvN47F+PAa2AntXv04eA\n28vpI46KAUDgszojmlp476/VZlkEPHVU1vw9gEcgV+XxfVD5yMP0o3QX6beR8vQ+HyeHAja79m0y\ngHsgK1K7973A79msY/3115lOWFkFbmZ0FGhbnV5eZTwqdbA6GU3N07frHkArYPVs8g0BfK/RaXLh\nvU/318wYYBl2zijiY+BuZViYz9bvvhwDPQIZjQOmRxttnjLgZ8YgMwrMMEdnLBPVU1m3R14cI4ts\nX6Di7acK+qFAykDbyxMBPvP0Xq6oLc/H+oL5XkfReQghqPHs62YhvAcvTjgFUrYEQFBnoPWUATcC\n+zigj6KjCvgingqIGfAzGWfu6ZU1VOthtck3bpRQATwOvOfDtMrBymBapCd2HkJ+EjDwIk9rT4Hf\nk1qzs3oawH0dVeD7/mehPZ4bvwrzo7HAuipeuYenagBYZKbqyGjqnr6ljQvUSQEe75ucLS17TNez\nIel1oNIZz7jk6/AgRm8fresz8Ddi4T3L86CrAB/1gI/b2FoaZWE6RuD4PDVuPWt7tW/Qw8PkipZr\n2ZyZ+kaeT8sA2XgV0Fn9Gaj9tfLwao2ftZHJGMmM+mHncSlbx+PkwQmH4FekwvuWN8TjK+8fGU1/\nHQGblYmAyAwG4xkn9EfdKyMVyapoqs/pm5DtrAA/NJzOjAgDdGX/APvSe7D6fRpeo5489RgAFbL7\nvMi7+zJ4j15YhfdITf4hHp9FCkNAH3lc7BMbF2YwGA8zBj3eXYG7Ev5HNNXn9P7critePAuxo3oy\nILJ2mIdXxkgtCzJwZ4DPJnGFcC3fykdrUBbW+3LtHtfyfrzx7TvmoZXHx7GJ1uG9/Io3q5PxZx4a\nx9inVcsOCf9XjadvAjVSAFBg6wFzBjbWbsV4MCD3yIbtMplUWnStCAcfDYCaLCwsx/zqs/jRaHSW\n5/b5Zss9PrZV0QGu7SN+putoL4DxVdbobCx9XqVeJie79geLWBhNdU3f7jGvF0CVo6e+cTcWsS++\nTtRBZBAinVWAjnpvpECsDIHPZ+t99PJ4qMdybFlQfdYepWeGMvLoyKO8rQIo1h8ZB5amjIavm8mD\n48ryFc1k9z4CQAWUrewknwKwvYesDfT+1ef2Kk3pCa/ZPRLz5Czd8/uwnAE/osaPH6Q0vTCwNmLA\nVxMYddN41G4+nn17yhD48hlAsSy2ifzVNJRRLQWwnK9P0VRBb1YDvveeKx0BZDv0FeD7MtVHeCw/\n0xPLZ8TAgqBHL9/GSoWIzAiwUL/pA8szYGf9jZ7XRyDFfOYd2VgoQ6HSfLvopStlFR/TnzISUf2K\nVgXo2zkC2NCNuqwskwHLYJ4CuHqxKDIUPj/TD9MjI2bpMUxHYHtQe37l6X15zGehfEtXwFf9ZTv2\nystG3teX9zrKAOrrUEYh0icDNKvXp7OwXdWJ6ZmXN5vBG3ksLQPwpB6VZfVUZMnqmdTLOiwv0rEK\n283OXq8qsLK6svYiuRi4MQz38vn62BofwZN531Yf1o2yR7w+nYEv8/TM+7LxYrKpev5PefrMADDg\nMIBFa2msa1zDMQTwvaCPDIHS
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 133
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Some comments on this algorithm:\n",
|
||
|
|
"\n",
|
||
|
|
"- this is a serial implementation, the way you would write it in C\n",
|
||
|
|
"- you can write faster array-based implementations\n",
|
||
|
|
"- there are some faster algorithms for implementing distance transform\n",
|
||
|
|
"\n",
|
||
|
|
"The algorithm assumes that all pixels within a Voronoi cell are path connected to the source; this assumption is not true for a few pixels. There are fixes for this that make the algorithm a little more complicated."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "heading",
|
||
|
|
"level": 1,
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Other Applications"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Euclidean distance transformations have many uses outside strict image processing.\n",
|
||
|
|
"For example, here is a simple application to robot navigation.\n",
|
||
|
|
"\n",
|
||
|
|
"Assume we have a circular robot platform and we want to see where that\n",
|
||
|
|
"platform can navigate on a floorplan."
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"We start by reading in the floorplan as an image.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"floorplan = mean(imread(\"floorplan.png\"),axis=2)\n",
|
||
|
|
"floorplan = (floorplan>amax(floorplan)/2.0)\n",
|
||
|
|
"imrow(floorplan)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAFqCAYAAADGClkWAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzs3XlcjGv/B/DPtCmKQypUSrYWHFkSp5Il65FdJ1uynhIt\nKHVQCSnZlyydUKKyHdk5FDnZspMkhFZSUlpo+f3hZx5pZppqZu6a+b5fL6/ndF/Xfd2f6Ylv93Zd\nrIqKigoQQgghhBFSTAcghBBCJBkVYkIIIYRBVIgJIYQQBlEhJoQQQhgkI+oDslgsUR+SEEIIYRy3\nZ6MZOSP29PRERUUF/eHyh74/9D2i7xF9j+rLH/oeCeb7wwtdmiaEEEIYRIWYEEIIYRAjhdjc3JyJ\nwzYY9P2pHn2Pqkffo+rR96h69D3iTRDfH1ZFdRevBYzFYlV7vZwQQggRJ7xqH12aJoQQQhhEhZgQ\nQghhEBViQgghhEFUiAkhhBAGUSEmhBBCGESFmBBCCGEQFWJCCCGEQVSICSGEEAZRISaEEEIYRIWY\nEEIIYRAVYkIIIYRBVIgJIYQQBlEhJoQQQhhEhZgQQghhEBViQgghhEFUiAkhhBAGUSEmhBBCGESF\nmBBCCGEQFWJCCCGEQVSICSGEEAZRISaEEEIYJMN0AEH68uULPn78yHQMQuq1Zs2aoVGjRkzH4Kqo\nqAj5+flMx+BKWloaysrKTMcgYkSsCvG///6LwMBA6OrqMh2FkHrpxIkTOHbsGLp06cJ0FK6Cg4Nx\n/fp1tG7dmq/+e/fuha2trZBT/c/JkyeRmJgosuMR8SdWhRgApkyZgj/++AMAYGtri7t37zKciJD6\n4927d3j//j3TMaq1YMEC9OnTh6++p0+fxrp164Sc6H9OnjwpsmMRySB2hfhHL168wIMHD5iOQQib\nu7s7oqKiICsry/c+eXl52LhxI8aMGVOlTV1dHWlpaXyPNW7cOAwYMIDv/oQQ4RPrQkxIfWRqagpF\nRUW++z9//lyIaQghTKNCTIgILVu2DIWFhTXer2nTpkJIQwipD6gQk1orKChAbGxsjfdLTk7G2bNn\nq2x/9uwZXr58iYqKCgBAWVkZZGS+/YgOHz68bmGF4ObNm8jJycFff/2FVatW8bVPkyZN0KRJEyEn\nI4Q0JFSICQAgJiYGu3fvrtE+SkpKMDc3r/GxDA0NsWDBgirb3dzc4O/vz3GfM2fO1Pg4wjZw4EBE\nR0czHYMQ0sBRIZYwUlJS7LPMH9na2uLgwYMMJCKEEMlGhVjCtGnTBmfPnkXXrl2ZjkIIIQQ0xaVY\nWr9+PddLxmlpaTh37pxoAxFCCOGKzojFQGlpKdLS0jB58mSkpaVh0aJFuHnzJt6/fw8VFRWm43H1\n+vXrSl/n5eXx3bc+KC4uZjoCIUQMUCFuwO7fv8+e5efr1684efIkWrRogT///BNOTk6YP38+IiMj\nGc31MxaLxX4qesWKFXyPqa2tLYhohBBS71AhbqA6deqEIUOGwNHREbKyspUK1cqVKzFw4EDo6+sL\n9Jjz5s3j6ynhT58+ISsrq9p+SUlJVbb169cPM2fORHBwcLV9mTZt2jTcvHmT6RiEkAaOCnED8fr1\na6Snp2PRokUAeBcmVVVVqKio4PDhwzh16hR+//33Su1v3rzB9evX2V+XlZXB1NS02gy6urpo2bJl\ntf1mzJgBDw+PavtxIiMjg/T09CrbO3bsWKvxhKlx48ZMRyCEiAG+CnFZWRl69eoFDQ0NnDx5Ejk5\nObCyssLr16+hra2NyMhI/PLLLwAAX19fBAcHQ1paGlu2bMGQIUOE+gHEna+vL1JTU9GqVSsoKysj\nLi6Or/2io6PBYrEQGBhYqRD/9ddfWL16NbZt28beJiUlhe3bt1c75ogRI+gSMSGECBhfhXjz5s3Q\n19dnrxG6du1aWFhYwNXVFX5+fli7di3Wrl2LhIQEREREICEhAWlpaRg8eDCSkpIgJUUPZ9dUTk4O\ntLS0cPHiRXTp0gWNGjWq0UIB3/08EYaVlRVWr16NFy9eQFVVlb29JnMfE0IIEZxqK2RqairOnDmD\n2bNnsx+yiYqKgo2NDQDAxsYG//zzD4Bva51aW1uz71l26NABt27dEmJ88XLixAls2rQJ48ePh4uL\nC/Lz82FsbAxFRUW+ivCFCxewa9cu6OjogMViYfHixQDAcRHzJk2aQFFRkf2HEEIIM6o9I3Z2dsa6\ndevw6dMn9rasrCyoqakBANTU1NgP5qSnp8PY2JjdT0NDg+MSbV5eXuz/Njc3r9U0ieIkMTER7u7u\nmDp1Kn777Tc4OTnVaP93795h3rx5GDduHDw8PODm5oZOnToB+DZ15cuXL4URWyQGDhzIcTrM+sDH\nxwdPnz5FSkoK01EIIfVMTEwMYmJi+OrLsxCfOnUKqqqqMDQ05Dogi8UCi8XiOganth8LsaT69OkT\nNm7ciA0bNsDY2Bjnz5+v8f7h4eGwt7eHuro6Zs2aBQcHhyrv4h46dAjx8fFwdnbGxo0bBfkRuPr6\n9SuKioqq7ZeXl4cuXbpU2f7jQ1Dx8fHsqy/11fcrD0z58ZdkQkj98PNJpre3N9e+PAtxXFwcoqKi\ncObMGRQXF+PTp0+YNm0a1NTUkJmZiVatWiEjI4N9r1FdXR1v375l75+amgp1dfU6fhzxUV5ejh07\ndgD4ttLQ8OHDeU5iwcmbN28QFRWFhIQE3L9/Hy4uLigqKkLPnj05jhUREYHIyEjcv38f79+/r/Nn\n+PEhL27y8vKQmZlZbT8FBQWen19aWrrG3x9J9NdffzEdgRBSBzwL8Zo1a7BmzRoAwJUrVxAQEIDQ\n0FC4urpi//79cHNzw/79+zFmzBgAgKWlJSZPngwXFxekpaXh+fPnMDIyEv6naACWL1+OS5cuYdOm\nTQAABweHGu2/ZcsWhIWFQU9PDxkZGcjPz8emTZugp6cHJSWlavePiYlBamoqZGRksGDBArRo0YLd\nVlZWhn79+vGVY+vWrdX2UVFRQbt27fgaj9QdP/+ffDdu3DghJiGE1EaN3iP+fpl56dKlmDRpEv7+\n+2/260sAoK+vj0mTJkFfXx8yMjLYsWMHz8vW4qykpASvXr2CjY0NPn36hICAAPj4+PC9f1lZGZ4/\nfw7g22tDEydOBIvFws2bNxEQEICRI0fyPdbHjx/RqVMnpKSkwMDAABcvXkS3bt3Y7dLS0nj8+DH/\nH44QQojA8F2I+/fvj/79+wMAWrRogX///ZdjPw8Pj1pP5iAO/vvvP5w5cwZSUlJQUFBAdHR0jSd+\nCAkJwbNnz/DgwQOcPn0ay5Ytg4KCAi5fvlzrsezs7PD06VOMHTsWT58+rdEYhBBChIdm1hIgTU1N\n/PHHH+xpJ78/WV7TMQICArB27Vq4uLhg586ddR7Lzs4OioqK7ElXCKnvLC0tIScnx1dffp5HIKQ+\no0JcRzExMexLzj8+qMav69ev4/nz53B3d0d6ejq2bduG3bt3o6ysrMZj3bhxA0lJSdi/f3+t8xBS\nH0RFRaFPnz589RX0nOrVKSwsxOXLl0V6TCJ4CgoK6Nu3L9MxAFAhrrPhw4fjypUraNSoUY32s7W1\nBQD06dMHnp6ecHJyQuvWraGtrY358+fXaKzs7GwsWbIERkZG0NLSwqVLl2q0PyGEfytXrsSbN2+Y\njkHqaNWqVUhOTmY6BgAqxHVWUFAAOTk5REVF4ddff622f3BwMObOnYukpCS0b98eoaGhKCkpgZSU\nVI0fbNu7dy/mzJkDLS0tJCUlQVpaurYfgxDCpxkzZjAdgQjAqlWrmI7ARoW4jqSlpeHi4oJly5Zx\nfZI5LCwMAHD69GlkZGTA3t4eW7ZsYU8ZWhPfxzp79iz69++P0tLS2ocnRMLp6Ojw/eoePy5duiTS\ne9ZTpkwR2bGEpbi4GDo6OvD390eLFi0wYsQIoR7v+fPn2LBhg1CPUVNUiAWgV69eCAgIwMSJE3H4\n8GH29j179uDo0aMwNTXFsmXL
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 45
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Now the distance transform gives us the distance of each floor pixel from some obstacle. A circular robot platform of radius 15 pixels cannot navigate closer than 15 pixels to any obstacle. As we can see from the thresholded image, a robot can navigate every room of the exhibit, but it cannot get behind the structure in the bottom left.\n",
|
||
|
|
"\n"
|
||
|
|
]
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "code",
|
||
|
|
"collapsed": false,
|
||
|
|
"input": [
|
||
|
|
"dt = morphology.distance_transform_edt(floorplan)\n",
|
||
|
|
"imrow(dt,dt>15)"
|
||
|
|
],
|
||
|
|
"language": "python",
|
||
|
|
"metadata": {},
|
||
|
|
"outputs": [
|
||
|
|
{
|
||
|
|
"output_type": "display_data",
|
||
|
|
"png": "iVBORw0KGgoAAAANSUhEUgAAA6EAAAFMCAYAAAA6HrpfAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnXe0HNWx9fdNBAEWIkiAEE/PZPHAhmcLzMNGJpsMBoFE\nEJllm2SyZYwEz+QMXjiQEUaAWeRgDHogopCNwWCyjS1LQhJJCAwI3fT9oa+u9tSt02Gme3pC/da6\na2Z6erpPn+6Ze3bvqjotvb29vXAcx3Ecx3Ecx3GcKtBadAMcx3Ecx3Ecx3Gc5sFFqOM4juM4juM4\njlM1XIQ6juM4juM4juM4VcNFqOM4juM4juM4jlM1XIQ6juM4juM4juM4VaO92jtsaWmp9i4dx3Gc\nBscLvVeG/292HMdxsibqf3PVRSgAXHXVVeju7kZ3dzd6enpKnstred7b24vu7m709vait7cXPT09\nAEoPql4HH9OmTcMWW2xRdDMKx/thMVH9IANEeWxtbUVLSwtaWlrQ2tra97qtra3vdWtrK9ra2vqW\nATC/b7JMvl/yvSvq+1bu9ZBFH8lz/mtvb+97v6Ojo2+ZLJdH/R7/lcNVV12FY489tqzP1iosdOTc\n8HM+X/x4ySWX4NRTTy05h3wuBwwYUNQhNRT1+r80ayZOnIiJEycW3YzC8X5YjPfDYrwfFuP9sIS4\nvoi7uVmICJVBsP7TApQHxPpR/lnW8z/N7u5udHZ2Ft2MwvF+WExUP0QN1nnA3tPT0yemWltb+74r\nso71XZNH/n51d3cDQCHft3Kvhyz6iI811DbeBz/v7u5GS0tLibBvbW0t+9puxO+FJUL5poE8sgCV\nPu3q6uo7lz09PWhra+s7b47jOI7j1BeFiNCurq6gANWOaEiAxg0W6wEZWDU73g+LSdIPMuC2xBX/\n9fb29g3So0Ro6KaP/r6JI1oNKr0eKumjECHBKfuT13q9rq6ussMcG/V7oftI0M41P/b09KCzs7Pk\n/MnNBBehjuM4jlN/FOqEdnV19Q2G+TkL0CghCtS3Ezp48OCGczrKwfthMXH9EBWyaAksdoskfFF/\n96KiD6wbP7XQD1FYfQSgX/hmqI+itsuPvC9xR1kYcT+Wy6abbtqQ3wsrbFo/6uv7G9/4RokTqsOp\nHSdLRo0aVXQTagLvh8V4PyzG+2Ex3g9LqLQvWnqrrOJaWlpw7rnnmm5oKEzQCskF6luAOk5aePCu\nB+osrkL5jUD/UPiQCNXfOaA+vm+V9pHOA+XnnOMZlQMqy10cLUG7waHQ6ZATaolP/hs6dGhdXJ+1\nTEtLi/eh4ziOkxlx/1dqIhxXXkv4mR4Y68JERYQIOk7R6Dy5UJ4ju3v8fRHXjr9jWoxa0Qf19H2r\ntI9C2wT6h93qHFD+vZLlTn90Lqh2raMEaKiwlOM4juM49UXh4bhxg+KQEAVQVw6N41SCNWDXA3QO\nKw19N6KKgkVFH9TDdy1NH0k4LhB/TDrs1nLtpAiR9F0j5nJmgQ7FZYHPzy0Xm28msBB1se84juM4\n9Ufh1XFDYbnWwNgKyQVqe2DsOJWiQxl5QK4Ltej8RnaJ2AktpzK1UKvfN+4n3UciZKSPuF+0k8YC\nSbubUc6nCFHpU6c/VlGiOCdUzptVlMjDnh3HcRynPilMhHZ1dUUK0NDgWDuhfhfcaQa44mtPT0/f\nIF3nOUYh1Vrjvm9WZWoRnrX8fYvro56eHrS3t8cWWQrlK4rYZMdTC3bpQycMn6ckOaFagFoFuBzH\ncRzHqS8KE6E82GVRauWFWg4NgIaYpsVxkqCdI+1+8oDcynGUz0ZFIEQVKQJq//sW1Ucs0qWvtICx\nqt3qEFz5fbLEqLufyQiJfMsJjcsFjatq7DiO4zhObVKICNX5nzwI1oPjKBHqd8CdZkIP2NkNkkcZ\nkEtFMg5RFYEVCofXN364SFGtC1Ah1Ec8H6gWLSJ+9DbY+eScz5AT6i5oGKs6Lt804GJSIQEqN1z0\n63q4Lh3HcRzHKaXwnNBy8kN5UOwDEKdZ4EG6nu/ScoNkHfksEP7uhb5v9XbTJ9RHLFhCLrE811Vw\nRQhZwlOH4zphrKJEISdUFydi8a+LS3m/O47jOE79UagTqsNxtSCVsFzLoeFBnw9CnEZGD955EB4K\nLRV0/l3U9y0q+qDWK+TG9ZGIdEt8shDiQkO68FCU+PRquPHocGkAJcJTC06rsBSfV76p4DiO4zhO\nfVFoTqj1aOWHRhUo8gGI0yxIKCIXaomajkXnNwLhG0DWNEn6hk89fN+i+shyjENhtxx+y0WHZBn3\nh+eCJifkgupiRKHqzzoH2sNxHcdxHKc+KcwJjRKhOj9UHrn6JA+I6yFM0HHKhV06Hpxrd6+9ffHX\n2ao+ym6eVRgsKh9bV8mtxUF/0j7S6+siRNxXWohqAephuOlJ4oSyKOUcUC6+xTcWdE6vUzvcc889\nmDBhQtHNcJzMaWlpwUsvvVR0M0o4+uijMW3atKKbUcJf/vKXopvg1DCFilAufBLlisYNjB2n0QkV\nJOrp6ekTn8BiIRoKHxVhZd3w0d83EaX8Ha3171vSPmKhyWJUFxzSbidvTwSQh+GmJ8m0LKFcUO1s\ne3Xc2uLOO+/EMcccg3nz5hXdFMfJHa4n8Lvf/Q4bb7wx1l9//arse/78+ZgyZQr23XffquyvXLiP\nJk+ejI033hgbbbRRgS1yaonCnVDtblohgdYfuxGO0+jw4FyHI0aFOPJgHkA/Fy/N963W52SM6iNe\nh11TLTitfE9LgHK/OfHo4k/yGHJCQ3OC8rQstezMNxsPP/wwTjnlFLz66qtFN8VxCmHffffFkCFD\nMGzYMPzxj3/MdV/HHnssHnroIbzzzju57idrxowZg1VXXRWDBw/GX//616Kb49QAhYhQ7TAkHRDr\n4im17sw4TlawoLSElTxa04ew6xf3fdOuKL+u9QF/XB9ZuZ+6j7jQk/xO6dxQ7j8nGVqEcpEiHYKr\nKxtbOaFeHbd2+P3vf4+dd9656GY4TuHMmzcP8+bNw8EHH4ybb745l31cdNFF+MUvfpHLtqvB+++/\nj/fffx/77rsvfve73xXdHKdgCnNCtasQ5UjEiVAfhDiNDrtD1hQjcdVbAZQIq9D3LXTjpx4iD6w+\nkmPX1W8tsc79o8NuBXnd2dlZ1GHWLUmLEsn5YzHKBYjkvHgYbvE88sgj2HPPPYtuhuPUFJMmTcIb\nb7yB6dOnZ7rd4447DldddVWm2yyKO++8ExtttJFHTzQ5hTqh1kBYOzVR7qi7oU4zoAu16OWW62kV\n0ZF1k37frGlbavWmT1QfWcJcV7oNCVDrN8rzQMtDu6FcQEtPxcLXcFtbWz8HFEC/Gw1O9Xn44Yfx\n5ZdfFt0Mx6k5/vrXv+LNN9/MLEf0448/rrmiQ5Xy+uuv469//Sv+67/+q+imOAVRmBPKz6OcUT1Y\nDglRx2lURGDp6Sh0zmfUd4ldpDTfN/2dq9WbPlYfiZsGwHQ+Q+G1lriR154HWj5Jcpe5GBE7oOxu\nuwNaO1xxxRVFN8FxapIvvvgCDz30UGYidObMmbnnmlab3t5e3HXXXS5Cm5iW3iqPKFtaWnDIIYeg\ns7MTXV1d5qNepp/LH+eqOU4jI2GJ7e3tJX8dHR0lz+W19djS0hL5PePv2KJFi/rcUP6+1aoIBZL3\nkX6MWsavXfxkQ1woLv9xOK48Wn8HHHBAzV6X9UJLS0uqPtxkk03wyiuv5Ngix6l/svpd4kiSRsN/\nuxuXuP8rhYXjstOgc9Z0PpYVQqj/HKdRkS+xTL9ihdpazwH0+47pZaHvGGDP5yvPa400fZTk90c7\noR5xkQ1agAIoCcO1KuLqyrg+YHEcx3Gc+qcQEcroQbD1XihXi/PWHKdRsarf8vcihPW9Cn3X5L2Q\naNMVc2uNUB/Ficeo/hBcgFaONUWLOMuhMFzOCbVCcV2QOo7jOE79UrgIjSI0wNDitFbdGcfJgo6O\nDtO1Y+KKtHB+pPVelCjV37eu
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"prompt_number": 46
|
||
|
|
},
|
||
|
|
{
|
||
|
|
"cell_type": "markdown",
|
||
|
|
"metadata": {},
|
||
|
|
"source": [
|
||
|
|
"Of course, we could have obtained the same result with a morphological operation,\n",
|
||
|
|
"using the footprint of the robot as the mask.\n",
|
||
|
|
"However, the distance transform actually gives us the locally best\n",
|
||
|
|
"place to navigate in order to stay as far away from the walls as possible\n",
|
||
|
|
"(the *medial axis transform*).\n",
|
||
|
|
"\n",
|
||
|
|
"Such computations are often carried out using polygonal approximations in\n",
|
||
|
|
"computational geometry.\n",
|
||
|
|
"The resulting computational geometry algorithms can become quite complex\n",
|
||
|
|
"and spend a lot of resources on computing sub-pixel effects.\n",
|
||
|
|
"On the other hand, they are resolution independent and can\n",
|
||
|
|
"cope more easily with rotations."
|
||
|
|
]
|
||
|
|
}
|
||
|
|
],
|
||
|
|
"metadata": {}
|
||
|
|
}
|
||
|
|
]
|
||
|
|
}
|