Make Bag-of-visual-words.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Make Bag-of-visual-words\n",
    "\n",
    "* Load Image's descriptor for all images. \n",
    "* Find corresponding visual word index for each descriptor. \n",
    "* Save list of visual word index."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# For Oxford 5k dataset, You can use already provided visual words "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%time\n",
    "# Oxford 5k dataset provides already converted visual words. We could use this one\n",
    "import os \n",
    "import pickle\n",
    "\n",
    "oxf5k_visualword_dir = './data/word_oxc1_hesaff_sift_16M_1M'\n",
    "work_dir = \"./oxfk5_provided\"\n",
    "if not os.path.exists(work_dir):\n",
    "    os.mkdir(work_dir)\n",
    "\n",
    "filelist = os.listdir(oxf5k_visualword_dir)\n",
    "filelist.sort()\n",
    "# print(filelist)\n",
    "# for parent_dir, _, files in os.walk(oxf5k_visualword_dir):\n",
    "#     print(files)\n",
    "\n",
    "bow_dict = {}\n",
    "count_descriptor = 0\n",
    "image_feature_count_info = []\n",
    "for filename in filelist:\n",
    "    filepath = os.path.join(oxf5k_visualword_dir, filename)\n",
    "    image_name = filename.replace(\".txt\", \"\")    \n",
    "    visual_words = []\n",
    "    with open(filepath) as f:\n",
    "        lines = list(map(lambda x: x.strip(), f.readlines()[2:])) # ignore first two lines        \n",
    "        for l in lines:\n",
    "            val = l.split(\" \")\n",
    "            visual_word_index = int(val[0])-1 # This data use 1 to 1,000,000. convert to zero-based so 0 to 999,999  \n",
    "            visual_words.append(visual_word_index)\n",
    "            # print('{} descriptor {}'.format(filename, l))\n",
    "        count_descriptor = count_descriptor + len(lines)\n",
    "    image_feature_count_info.append((image_name, len(visual_words)))\n",
    "    bow_dict[image_name] = sorted(visual_words)\n",
    "    # break\n",
    "# print('bow_dict:', bow_dict)\n",
    "print('count_descriptor:', count_descriptor)\n",
    "\n",
    "pickle.dump(bow_dict, open(os.path.join(work_dir, 'bow_dict_word_oxc1_hesaff_sift_16M_1M_pretrained.pkl'), 'wb'))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Other case, you have to build it from scratch\n",
    "After you prepared everything, run below code\n",
    "\n",
    "## Preparation list\n",
    "\n",
    "* (image, descriptor_list) tuple\n",
    "* centroids\n",
    "\n",
    "\n",
    "## Requirements\n",
    "\n",
    "* Image name and its associated 128d descriptors\n",
    "* visual words assigner\n",
    "    * For a given 128d descriptor, it tells index of visual words. \n",
    "    * After you ran k-means clustering, you could use it to get nearest centroid's id\n",
    "\n",
    "\n",
    "\n",
    "TODO: determine design choice when we use encoding such as Product Quantization. \n",
    "1. keep centroid as PQ code. It means we always have to keep encoder parts. \n",
    "2. keep centroid as original vector. It means there is room for additional error when we assign each descriptor to the nearest centroid. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load image descriptor dictionary, and assign each descriptor to visual words\n",
    "import pickle\n",
    "import os\n",
    "import numpy as np\n",
    "import pqkmeans\n",
    "from tqdm import tqdm\n",
    "from multiprocessing import Pool, TimeoutError\n",
    "\n",
    "image_descriptor_dict_path = 'image_descriptor_dict_oxc5k_extracted_hesaff_rootsift_13M.pkl'\n",
    "\n",
    "# You should use matching encoder that was used to do PQk-means clustering. \n",
    "# encoder_save_path = 'pqencoder_100k_random_sample_from_16M.pkl'\n",
    "# cluster_center_save_path = 'clustering_centers_in_pqcode_numpy.npy'\n",
    "\n",
    "# encoder_save_path = 'pqencoder_1000k_random_sample_from_16M.pkl'\n",
    "# cluster_center_save_path = 'clustering_centers_numpy_16M_feature_1000k_coodebook_131k_cluster.npy'\n",
    "\n",
    "work_dir = \"./output_oxf5k_extracted_13M_rootsift_1M_vocab_pqkmeans_1M_codebook_train\"\n",
    "encoder_save_path = os.path.join(work_dir, 'pqencoder.pkl')\n",
    "cluster_center_save_path = os.path.join(work_dir, 'centroids_in_pqcodes.npy')\n",
    "output_bow_dict_save_path = os.path.join(work_dir, 'bow_dict.pkl')\n",
    "\n",
    "# encoder_save_path = 'encoder.pkl'\n",
    "# cluster_center_save_path = 'clustering_centers_numpy.npy'\n",
    "    \n",
    "# For PQ-kmeans clustering, we first convert query to PQ codes. \n",
    "with open(encoder_save_path, 'rb') as f:\n",
    "    encoder = pickle.load(f)\n",
    "clustering_centers_in_pqcode_numpy = np.load(cluster_center_save_path)\n",
    "# print('cluster centers shape: ', clustering_centers_in_pqcode_numpy.shape)\n",
    "\n",
    "k = clustering_centers_in_pqcode_numpy.shape[0]\n",
    "print('number of clusters:', k)\n",
    "engine = pqkmeans.clustering.PQKMeans(encoder=encoder, k=k, iteration=1, verbose=False, init_centers=clustering_centers_in_pqcode_numpy)\n",
    "    \n",
    "bow_dict = {}\n",
    "\n",
    "\n",
    "def run(val):\n",
    "    image_name, tupval = val\n",
    "    descriptors = tupval[1]\n",
    "    data_points_pqcodes = encoder.transform(descriptors)\n",
    "    # print('num_descriptors:', len(data_points_pqcodes))\n",
    "    # print('num_descriptors shape:', data_points_pqcodes.shape)\n",
    "    # TODO: speedup by using pq-kmeans assignment step. \n",
    "    # visual_words = get_assigned_center_index(data_points_pqcodes, clustering_centers_in_pqcode_numpy)\n",
    "    visual_words = engine.predict(data_points_pqcodes) # Fast assignment step. \n",
    "    \n",
    "    return (image_name, list(set(list(visual_words))))\n",
    "    \n",
    "if __name__ == \"__main__\":    \n",
    "    \n",
    "    with open(image_descriptor_dict_path, 'rb') as f:\n",
    "        # key: image_name, value: tuple of (keypoint_nparray, descriptor_nparray) \n",
    "        # descriptor_nparray: 2d numpy array of shape (num_descriptor, dim_descriptor)\n",
    "        image_descriptor_dict = pickle.load(f) \n",
    "    print('num images:', len(image_descriptor_dict))\n",
    "    \n",
    "    pool = Pool(processes=20) # start 20 worker processes\n",
    "    # print same numbers in arbitrary order\n",
    "    for image_name, bow in tqdm(pool.imap_unordered(run, image_descriptor_dict.items()), total=len(image_descriptor_dict)):        \n",
    "        bow_dict[image_name] = bow\n",
    "        \n",
    "    print('done')\n",
    "    pickle.dump(bow_dict, open(output_bow_dict_save_path, 'wb'))\n",
    "    \n",
    "# Timing: 24min for 5062 images with 16M features. 100k leanred codebook with 4 subspaces. 2^17 clusters. \n",
    "# Timing: 38min for 5062 images with 16M features. 1M leanred codebook with 8 subspaces. 2^17 clusters. "
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}