LSH.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import pickle\n",
    "from lshash.lshash import LSHash\n",
    "\n",
    "import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open('Data/feature_matrix/fc6_full_dress.p','rb') as f:\n",
    "    feat_dresses = pickle.load(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "lsh = LSHash(8,feat_dresses.shape[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "start = time.time()\n",
    "for i in range(feat_dresses.shape[0]):\n",
    "    lsh.index(feat_dresses[i,:],extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "start = time.time()\n",
    "r = lsh.query(feat_dresses[101,:], num_results=10, distance_func=\"euclidean\")\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "lsh = LSHash(8,feat_dresses.shape[1])\n",
    "bin_dresses = (feat_dresses>0)\n",
    "\n",
    "start = time.time()\n",
    "for i in range(bin_dresses.shape[0]):\n",
    "    lsh.index(list(bin_dresses[i,:]),extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "start = time.time()\n",
    "r = lsh.query(feat_dresses[101,:], num_results=10, distance_func=\"hamming\")\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "r = lsh.query(feat_dresses[100,:], num_results=10, distance_func=\"hamming\")\n",
    "print('H {}'.format(r[1][1]))\n",
    "r = lsh.query(feat_dresses[100,:], num_results=10)\n",
    "print('H {}'.format(r[1][1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "len(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "list(bin_dresses[101,:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from IPython.display import display\n",
    "import PIL\n",
    "from PIL import ImageDraw\n",
    "\n",
    "\n",
    "\n",
    "def draw_bbox(bbox):\n",
    "    img = PIL.Image.open('Data/DeepFashion/'+bbox['image_name']).convert('RGBA')\n",
    "    \n",
    "    lx = bbox['x_1']\n",
    "    ly = bbox['y_1']\n",
    "    ux = bbox['x_2']\n",
    "    uy = bbox['y_2']\n",
    "    rect = PIL.Image.new('RGBA', img.size, (255,255,255,0))\n",
    "    d = ImageDraw.Draw(img)\n",
    "    d.rectangle(((lx,ly), (ux,uy)), outline=\"red\")\n",
    "    return PIL.Image.alpha_composite(img,rect)\n",
    "\n",
    "def gen_pairs(N,image_df,lsh,feature_matrix):\n",
    "    img_index = np.random.randint(image_df.shape[0],size=N)\n",
    "\n",
    "    for i in img_index:\n",
    "        j = 0\n",
    "        match = lsh.query(feature_matrix[i,:], num_results=N+5)\n",
    "        dist = match[j][1]\n",
    "        n = match[j][0][1]\n",
    "        while dist<=0:\n",
    "            j += 1\n",
    "            dist = match[j][1]\n",
    "            n = match[j][0][1]\n",
    "\n",
    "        display(draw_bbox(image_df.iloc[i]))\n",
    "        display(draw_bbox(image_df.iloc[n]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "bbox = pd.read_table('Data/DeepFashion/list_bbox.txt',sep='\\s+')\n",
    "cat = pd.read_table('Data/DeepFashion/list_category_img.txt',sep='\\s+')\n",
    "dresses = bbox[cat['category_label'] == 41]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "gen_pairs(3,dresses,lsh,feat_dresses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "lsh16 = LSHash(16,feat_dresses.shape[1])\n",
    "\n",
    "start = time.time()\n",
    "for i in range(feat_dresses.shape[0]):\n",
    "    lsh16.index(feat_dresses[i,:],extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "gen_pairs(3,dresses,lsh16,feat_dresses)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def test_pairs(N,image_df,lsh,feature_matrix):\n",
    "    img_index = np.random.randint(image_df.shape[0],size=N)\n",
    "    cat_match = []\n",
    "    for i in img_index:\n",
    "        j = 0\n",
    "        match = lsh.query(feature_matrix[i,:], num_results=N+5)\n",
    "        dist = match[j][1]\n",
    "        n = match[j][0][1]\n",
    "        while (dist<=0 & j<len(match)-1):\n",
    "            j += 1\n",
    "            dist = match[j][1]\n",
    "            n = match[j][0][1]\n",
    "\n",
    "        cat_match.append(image_df.iloc[i]['category_label'] == image_df.iloc[n]['category_label'])\n",
    "        \n",
    "    return cat_match"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# FULL SET\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class MacOSFile(object):\n",
    "    def __init__(self, f):\n",
    "        self.f = f\n",
    "\n",
    "    def __getattr__(self, item):\n",
    "        return getattr(self.f, item)\n",
    "\n",
    "    def read(self, n):\n",
    "        if n >= (1 << 31):\n",
    "            buffer = bytearray(n)\n",
    "            pos = 0\n",
    "            while pos < n:\n",
    "                size = min(n - pos, 1 << 31 - 1)\n",
    "                chunk = self.f.read(size)\n",
    "                buffer[pos:pos + size] = chunk\n",
    "                pos += size\n",
    "            return buffer\n",
    "        return self.f.read(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "df = bbox.join(cat,lsuffix='_',rsuffix='')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open('Data/feature_matrix/fc6_full_set.p','rb') as f:\n",
    "    feat = pickle.load(MacOSFile(f))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "n = np.reshape(np.sqrt(np.sum(feat**2,axis=1)),(-1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "feat_norm = feat/n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LSH 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "lsh8 = LSHash(8,feat.shape[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "107.985\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "for i in range(feat.shape[0]):\n",
    "    lsh8.index(feat[i,:],extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.168\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "r = lsh8.query(feat[100,:], num_results=10)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "287.934 s\n",
      "0.530 match\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "matches = test_pairs(100,df,lsh8,feat)\n",
    "print('{:.3f} s'.format(time.time()-start))\n",
    "print('{:.3f} match'.format(np.mean(matches)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LSH 8 Normalized Vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "lsh8 = LSHash(8,feat.shape[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "121.935\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "for i in range(feat.shape[0]):\n",
    "    lsh8.index(feat_norm[i,:],extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2562.426 s\n",
      "0.584 match\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "matches = test_pairs(1000,df,lsh8,feat_norm)\n",
    "print('{:.3f} s'.format(time.time()-start))\n",
    "print('{:.3f} match'.format(np.mean(matches)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.731\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "r = lsh8.query(feat_norm[101,:], num_results=10,distance_func='euclidean')\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LSH 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113.795\n"
     ]
    }
   ],
   "source": [
    "lsh12 = LSHash(12,feat.shape[1])\n",
    "start = time.time()\n",
    "for i in range(feat.shape[0]):\n",
    "    lsh12.index(feat[i,:],extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.623\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "r = lsh12.query(feat[100,:], num_results=10)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "393.631 s\n",
      "0.527 match\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "matches = test_pairs(1000,df,lsh12,feat)\n",
    "print('{:.3f} s'.format(time.time()-start))\n",
    "print('{:.3f} match'.format(np.mean(matches)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LSH 12 Normalized vector"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113.865\n"
     ]
    }
   ],
   "source": [
    "lsh12 = LSHash(12,feat_norm.shape[1])\n",
    "start = time.time()\n",
    "for i in range(feat_norm.shape[0]):\n",
    "    lsh12.index(feat_norm[i,:],extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "346.085 s\n",
      "0.553 match\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "matches = test_pairs(1000,df,lsh12,feat_norm)\n",
    "print('{:.3f} s'.format(time.time()-start))\n",
    "print('{:.3f} match'.format(np.mean(matches)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## LSH 16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "113.558\n"
     ]
    }
   ],
   "source": [
    "lsh16 = LSHash(16,feat.shape[1])\n",
    "start = time.time()\n",
    "for i in range(feat.shape[0]):\n",
    "    lsh16.index(feat[i,:],extra_data = i)\n",
    "print('{:.3f}'.format(time.time()-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.024\n",
      "111.052812539\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "r = lsh16.query(feat[100,:], num_results=10)\n",
    "print('{:.3f}'.format(time.time()-start))\n",
    "print(r[1][1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "58.639 s\n",
      "0.512 match\n"
     ]
    }
   ],
   "source": [
    "start = time.time()\n",
    "matches = test_pairs(1000,df,lsh16,feat)\n",
    "print('{:.3f} s'.format(time.time()-start))\n",
    "print('{:.3f} match'.format(np.mean(matches)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[100, 28121, 22351]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(m[0][1] for m in r[0:3])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def write_pairs(N,k,image_df,lsh,feature_matrix):\n",
    "    img_index = np.random.randint(image_df.shape[0],size=N)\n",
    "    \n",
    "    pairs = []\n",
    "    \n",
    "    for i in img_index:\n",
    "        j = 0\n",
    "        match = lsh.query(feature_matrix[i,:], num_results=N+5)\n",
    "        dist = match[j][1]\n",
    "        n = list(m[0][1] for m in match[j:(j+k)])\n",
    "        while (dist<=0 & j<len(match)-1):\n",
    "            j += 1\n",
    "            dist = match[j][1]\n",
    "            n = list(m[0][1] for m in match[j:(j+k)])\n",
    "        \n",
    "        s = image_df.iloc[i]['image_name']\n",
    "        for m in n:\n",
    "            s = s + \"\\t\" + image_df.iloc[m]['image_name']\n",
    "        pairs.append(s)\n",
    "        \n",
    "    return pairs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "with open('fc6_full_LSH.txt', 'w') as f:\n",
    "    f.write('\\n'.join(write_pairs(300,3,df,lsh16,feat)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "289222"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "feat.shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env",
   "language": "python",
   "name": "env"
  },
  "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}