Walsh Hadamard.ipynb

{
 "metadata": {
  "name": "Walsh Hadamard"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%pylab inline\n",
      "from numba import autojit, jit, double,int_\n",
      "from scipy.ndimage.filters import gaussian_filter\n",
      "import numpy as np\n",
      "from pygco import cut_inpaint"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "\n",
        "Welcome to pylab, a matplotlib-based Python environment [backend: module://IPython.zmq.pylab.backend_inline].\n",
        "For more information, type 'help(pylab)'.\n"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "#### Walsh Hadamard Transform\n",
      "\n",
      "It looks to be too expensive to do the nearest neighbor search on the full set of patch pixels.  Following the reference, we instead will decompose each path in the Walsh-Hadamard basis.  Following _Kaiming He and Jian Sun_, [Computing Nearest-Neighbor Fields via Propagation-Assisted KD-Trees](http://research.microsoft.com/en-us/um/people/kahe/publications/cvpr12nnf.pdf), I will use the first 16 basis for the Y channel anad the first 4 for each of the CbCr channels."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def wh_patches(patch_size):\n",
      "    ''' Returns 16 x patch_size x patch_size matrix of walsh hadamard transforms '''\n",
      "    basis = np.array([[1,1,1,1],[1,1,-1,-1],[1,-1,-1,1],[1,-1,1,-1]])\n",
      "    scale = patch_size/4\n",
      "    rescaler = ones((scale,scale))\n",
      "    res = zeros((16, patch_size, patch_size))\n",
      "    idx = 0\n",
      "    for m in range(len(basis)):\n",
      "        for n in range(len(basis)):\n",
      "            res[idx,:,:] = kron(outer(basis[m,:],basis[n,:]),rescaler)\n",
      "            idx += 1\n",
      "    return res\n",
      "            \n",
      "    \n",
      "_,ax = subplots(4,4)\n",
      "\n",
      "idx = 0\n",
      "patches = wh_patches(8)\n",
      "for m in range(len(ax)):\n",
      "    for n in range(len(ax)):\n",
      "        tmp = patches[idx,:,:]\n",
      "        tmp[tmp == -1] = 0\n",
      "        ax[m,n].spy(tmp)\n",
      "        ax[m,n].xaxis.set_visible(False)\n",
      "        ax[m,n].yaxis.set_visible(False)\n",
      "        ax[m,n].set_title(str(idx))\n",
      "        idx += 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "display_data",
       "png": "iVBORw0KGgoAAAANSUhEUgAAAUQAAAD+CAYAAABCzHxhAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAADoZJREFUeJzt3XtsU3Ufx/FPB2i3dmM4BDrkMoIIYmI0QGLA6z+IBgfK\nLcGpgDFBhBAjEQOjTDGR8IdBCf8rCMSBEY2CCiSQmRgTFS8o4aLgJbgNB4yNTtZynj+er0sgds+2\nh3N+7eH9Shp14M53327vtdCzE/E8zxMAQAWuBwCAXEEQAcAQRAAwBBEADEEEAEMQAcA4CWJTU5Om\nT5+ueDyu4cOHa+vWrS7GCKUNGzZo3LhxikajmjdvnutxQuXixYtasGCBhg8frpKSEt1xxx3avXu3\n67FC4/HHH1cikVBJSYlGjBihV199NfAZnARx0aJFikajamho0DvvvKOFCxfqxx9/dDFK6AwePFjV\n1dWaP3++61FCJ51Oa+jQoTpw4ICam5u1Zs0azZo1SydPnnQ9Wii89NJL+uWXX9Tc3Kxdu3bpzTff\nDPwbTuBBbG1t1XvvvadXXnlFRUVFmjhxoiorK7Vp06agRwml6dOnq7KyUmVlZa5HCZ2ioiIlk0kN\nHTpUkvTwww+roqJCX3/9tePJwmHs2LGKRqMd/927d28NGDAg0BkCD+KRI0fUu3dvjRw5suNtt99+\nuw4dOhT0KKHGCUj+q6+v15EjRzR27FjXo4TGs88+q1gsprFjx2rlypW68847Az1+4EFsaWlRSUnJ\nZW8rLi7W+fPngx4l1CKRiOsRQq29vV1z587VU089pVGjRrkeJzQ2btyolpYW7dmzRytXrtSXX34Z\n6PEDD2I8Hldzc/Nlbzt37pyKi4uDHiXUeITon0uXLqmqqkrRaFQbNmxwPU7oRCIR3XfffZo5c2bg\nf+EaeBBHjRqldDqtY8eOdbzt22+/1W233Rb0KKHGI0R/eJ6nBQsWqLGxUTt27FCvXr1cjxRa7e3t\nisVigR4z8CDGYjE9+uijWrVqlS5cuKC6ujp9+OGHqqqqCnqUUMpkMmpra1M6nVYmk9Hff/+tTCbj\neqzQWLhwoQ4fPqwPPvhA119/vetxQqOxsVHbtm1Ta2urMpmMPvnkE9XW1qqysjLYQTwHmpqavGnT\npnmxWMwbNmyYt3XrVhdjhFIymfQikchlt5qaGtdjhcKJEye8SCTiFRYWevF4vOO2ZcsW16PlvcbG\nRu/ee+/1SktLvb59+3rjx4/3du7cGfgcEc/jD5sAQOLUPQDoQBABwBBEADAEEQAMQQQAQxABwPTO\n9gthOdMhV19VFIb9slv/sFt/Zdtv1iB29j/li7DceT3l5/0Xtt0G8bketp11VU92291ddecYnb1v\nnjIDgCGIAGAIIgAYgggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAIIgAY\ngggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAI\nIgAYgggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAIIgAYgggAxmkQjx49qmg0qqqqKpdjhFZxcbHG\njBnjeozQ2bZtm8aMGaN4PK6RI0eqrq7O9Uh5Lx6Pq7i4uOPmSm9nR5a0aNEiTZgwQZFIxOUYoXX+\n/HnXI4TOZ599puXLl+vdd9/VhAkTdOrUKXme53qsvNfS0tLx762trYrH407mcBbEbdu2qV+/frr1\n1lt17NgxV2MA3ZJMJpVMJjVhwgRJUiKRcDxR+Gzfvt3ZsZ08ZW5ublYymdTrr7/Od1cfTZo0Sfv3\n73c9RmhkMhl99dVXamho0M0336whQ4Zo8eLFamtrcz1aqLz11lvOju0kiNXV1Xr66adVXl7O02Uf\nPfPMM5o6dap+/vln16OEQn19vdrb27Vjxw7V1dXp4MGD+uabb7RmzRrXo4XGyZMndeDAAWfHDzyI\nBw8e1N69e7V06VJJ4hGij5544glNnDhRH3/8setRQqGwsFCStHjxYg0cOFBlZWV6/vnn2e9VtGnT\nJt19993Ojh/xshQpLI/ccjW4Ydgvu/UPu/VXtv1mfYToeZ4vtwsXLqi+vl719fX6888/9cILL2jG\njBk6ffq0L8fLVX58rGfPntXu3buVSqXU3t6uzZs3KxaL6ejRo+z2Kt1WrVql8ePHq6GhQU1NTZo0\naZJWrVrFbq/C7fPPP1csFlNLS4uvx+lsv4H/LXNhYWHHUw/pv68/KiwsVFlZWdCjhE57e7uqq6t1\n+PBh9erVS2PGjNHOnTs1cuRI16OFRnV1tU6fPq1Ro0YpGo1q9uzZWrFiheuxQuHtt9/WY489plgs\n5myGrE+ZAeBaw6l7AGAIIgAYgggAhiACgCGIAGAIIgCYrK9DDPsr0l0Lw37ZrX/Yrb+y7dfpz0OE\nv/z8ogrLF8Y/gghQ2HbWVT3ZbXd31Z1jdPa+ecoMAIYgAoAhiABgCCIAGIIIAIYgAoAhiABgCCIA\nGIIIAIYgAoAhiABgCCIAGIIIAIYgAoAhiABgCCIAGIIIAIYgAoAhiABgCCIAGIIIAIYgAoAhiABg\nOr0uc65eLLurcv06uH7vN9c/fj91d7dB7KqrM+X6/RbEbl3dfzxCBABDEAHAEEQAMAQRAAxBBABD\nEAHAEEQAMAQRAAxBBABDEAHAEEQAMAQRAAxBBABDEAHAEEQAMAQRAIyTIP7++++aOnWqysrKlEgk\ntHjxYmUyGRejhM5PP/2kBx54QKWlpa5HAXpsxowZqqioUEFBgfbv3x/YcZ0EccmSJerfv79OnTql\ngwcPav/+/dq4caOLUUIlnU6rsrJSjzzyiM6cOeN6HKDH7rnnHm3evFmDBg0K9CeId3oJAb8cOnRI\n69ev13XXXaeBAwfqwQcf1KFDh1yMEiqHDx/WqVOntHTpUtejAP+XJUuWSJJ69eoV6HGdPEKcPHmy\ntmzZolQqpT/++EO7du3SlClTXIwCAB2cBHH16tX64YcfVFJSoiFDhmj8+PGqrKx0MUqo3HLLLRow\nYIDWrVun9vZ21+MAeSfwIHqep8mTJ2vmzJm6cOGCTp8+raamJr344otBjxI6ffr00fvvv6+PPvpI\niUTC9ThA3ol4Wa73l+uXQuyqXL2Uahj2y279w279lW2/WR8hep7ny+3SpUsqLy/X2rVrlU6ndebM\nGU2bNk1z58715Xi5yq/9fvfdd0qlUmptbdW6des0YsQIXbx4kd324JZOp5VKpbR8+XJVVVWpra1N\n6XRajY2N6tu3r3bs2KFUKqVly5bprrvuYrdXab+e56mtrU2pVEo33XSTPv30U6VSqWD26znwxRdf\neJMmTfJKS0u9/v37e7Nnz/YaGhpcjBI6y5Yt8/r16+fF43HvoYce8o4fP+56pLyVTCa9SCRy2a2m\npsbzPM/bs2ePN3r0aK+wsNC7//77vZMnTzqeNv90tt9hw4Z5kUjEKygo6PhnEDvO+pQZAK41nLoH\nAIYgAoAhiABgCCIAGIIIAIYgAoDJ+tNuwv6KdNfCsF926x92669s+3Xy478QDD+/qMLyhfGPIAIU\ntp11VU92291ddecYnb1vnjIDgCGIAGAIIgAYgggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAIIgCY\nTs9lztUTzLsq188d9Xu/uf7x+6m7uw1iV12dKdfvtyB26+r+4xEiABiCCACGIAKAIYgAYAgiABiC\nCACGIAKAIYgAYAgiABiCCACGIAKAIYgAYAgiABiCCACGIAKAIYgAYAgiABiCCACGIAKAIYgAYAgi\nABiCCACGIAKAIYgAYDq9UH2uXzA73/m93+5e7Ls7cv1zo7vz+bmrf+T6zroqiN36eYzO3jePEAHA\nEEQAMAQRAAxBDLFx48bphhtuUGlpqSZOnKi6ujrXI+WVDRs2aNy4cYpGo5o3b96//p6XX35ZBQUF\n2rdvX8DT5b9s+z1x4oSzmQhiiNXW1uqvv/7SmTNnNGfOHM2YMcP1SHll8ODBqq6u1vz58//1148f\nP67t27ervLw84MnC4X/t1wWCGGIVFRWKRCLKZDIqKChQIpFwPVJemT59uiorK1VWVvavv/7cc89p\n7dq16tOnT8CThcP/2q8Lnb7sBvmvtLRUra2tKi8v52ldD/3bSzpqa2sVjUY1ZcoUBxOFSxAveeoq\nHiGG3NmzZ3Xu3DnNmTNHM2fOzKlPvnxx5evWzp8/rxUrVmj9+vWOJgqXK/d74403OpqEIF4TioqK\n9Nprr+nIkSP6/vvvXY+Td678JrJ69WpVVVVp6NChWX8Puu7K3cViMUeTEMRrRiaT0aVLl1RUVOR6\nlLxz5SOYffv26Y033lAikVAikdBvv/2mWbNmad26dY4mzG+5dAZPxMvyrS2Xhvx/5Op37jDsl936\nh936K9t+sz5C9Dzvqt2SyaQikchlt9WrV6umpkaRSETxeLzjVlxcfFWPnav83G1NTY1qa2s1evRo\nxeNxDRo0SHPmzNGvv/7Kbq/Cbq/8fcOHD9fevXvZ7VXa79atW1VRUaFYLKZEIqEnn3xS9fX1gew3\n6yNEALjW8GeIAGAIIgAYgggAhiACgCGIAGAIIgCYrD/cIewvwHQtDPtlt/5ht/7Ktl9+2k2I+flF\nFZYvjH8EEaCw7ayrerJbLjIFAI4RRAAwBBEADEEEAEMQAcAQRAAwBBEADEEEAEMQAcAQRAAwBBEA\nTKfnMufqCeZdlevnjvq931z/+P3U3d0GsauuzpTr91sQu3V1//EIEQAMQQQAQxABwBBEADAEEQAM\nQQQAQxABwBBEADAEEQAMQQQAQxABwHR6LnOun1OZ7/ze77V8XWY/r+vbU7m+s64KYrdclxkAHCOI\nAGAIIgAYgggAhiACgCGIAGAIIgAYgggAhiACgCGIAGAIIgAYgggAhgvVO8SF6v3Dher9w4XqAeAa\nQBABwBBEADAEEQAMQQQAQxABwBBEADAEEQAMQQQAQxABwHBdZofYr39ycbe5OFNPBPFxuNpVxMv3\nE5YB4CrhKTMAGIIIAIYgAoAhiABgCCIAGIIIAOY/gGUqtfryPS0AAAAASUVORK5CYII=\n"
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "@autojit\n",
      "def wh_decompose(patch, basis):\n",
      "    res = zeros((len(basis),))\n",
      "    for idx in range(0,len(basis)):\n",
      "        for m in range(0,8):\n",
      "            for n in range(0,8):\n",
      "                res[idx] += patch[m,n] * basis[idx,m,n]\n",
      "    res = res / 64.\n",
      "    return res\n",
      "\n",
      "@autojit                \n",
      "def ycbcr2wh(img):\n",
      "    M = img.shape[0]\n",
      "    N = img.shape[1]\n",
      "    res = zeros((M,N,24))\n",
      "    wh_basis = wh_patches(8)\n",
      "    for m in range(0,M-8):\n",
      "        for n in range(0,N-8):\n",
      "            curr_patch = img[m:m+8,n:n+8]\n",
      "            res[m,n,0:16]  = wh_decompose(curr_patch[:,:,0],wh_basis)\n",
      "            res[m,n,16:20] = wh_decompose(curr_patch[:,:,1],wh_basis[[0,1,4,5],:,:])\n",
      "            res[m,n,20:24] = wh_decompose(curr_patch[:,:,2],wh_basis[[0,1,4,5],:,:])\n",
      "    return res"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 37
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## Summary\n",
      "\n",
      "Still too slow to build from python.  Will just switch to c++ once dummy version of inpainting works."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}