_test_Scalable Recognition with a Vocabulary Tree copy.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div width=50% style=\"display: block; margin: auto\">\n",
    "    <img src=\"images/ic_logo.png\" width=\"200\">\n",
    "    <img src=\"images/sberbank_logo.png\" width=\"250\" style=\"margin-left: 10%\">\n",
    "</div>\n",
    "\n",
    "<hr width=55% style=\"float: left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Day 3\n",
    "# Computer Vision - Scalable Recognition with a Vocabulary Tree\n",
    "\n",
    "### [Antonio Stanziola](https://github.com/astanziola) & [Eduardo Pignatelli](https://github.com/epignatelli)\n",
    "\n",
    "<hr width=70% style=\"float: left\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"card\">\n",
    "    <div class=\"card-header\"><h4> ✔️ Objectives</h4></div>\n",
    "</div>\n",
    "\n",
    "The objective of this practical is to implement a system that searches for images similar to a given one. While doing so, you'll learn how images can be described as vectors and how to efficiently search for similar vectors in a large database"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "tags": []
   },
   "source": [
    "<div class=\"panel panel-default\">\n",
    "  <div class=\"panel-heading\"><h4> 📜 Outline</h4></div>\n",
    "  <div class=\"panel-body\">\n",
    "\n",
    "1. [Introduction](#1.-Introduction)\n",
    "  - The image retrieval problem\n",
    "  - CBIR pipeline\n",
    "2. [Features extraction](##2.-Features-extraction)\n",
    "  - Find keypoints\n",
    "  - Corner detectors\n",
    "  - Extract local features\n",
    "3. [Creating a visual vocabulary](##3.-Creating-a-visual-vocabulary)\n",
    "  - Why using the vocabulary?\n",
    "  - Building the tree using hierarchical k-means\n",
    "  - Indexing the database using TF-IDF (Term Frequency-Inverse Document Frequency)\n",
    "4. [Scoring and Retrieving (the online phase)](#4-Scoring-and-Retrieving-(the-online-phase))\n",
    "  - Retrieving an image from the database\n",
    "5. [Image encoding with Deep Convolutional Neural Networks](#5.Image-encoding-with-Deep-Convolutional-Neural-Networks)\n",
    "<p/>\n",
    "  </div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While we introduce the problem, let's download the data we will use throughout this session. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!python cbir/download.py"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## **1. Introduction**\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 The image retrieval problem\n",
    "\n",
    "<img src=\"images/CBIR.png\" height=\"10\" width=\"400\" align=\"right\">\n",
    "\n",
    "Content-based image retrieval (CBIR) is the process of searching for images in a large database, given a visual query for search. Technically, there are three key components in CBIR:  \n",
    "  1. Image representation\n",
    "  2. Database organisation\n",
    "  3. Image distance measurement\n",
    "\n",
    "We can further specify the definition of CBIR above.\n",
    "\n",
    "> CIBR makes use of the ***representation*** of visual content to identify relevant images in a database.\n",
    "\n",
    "<u>In this lesson we will focus on a **Query-based Image Retrieval** problem, which uses an example image as query.</u>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At the end of this session, we expect to be able to have a function as below.  \n",
    "As we go through the notebook we will learn all the ingredients to implement such function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def retrieve(database, query):\n",
    "    raise NotImplemented"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-heading alert-danger\" style=\"background-color: white; border: 2px solid; border-radius: 5px; color: #000; border-color:#AAA; padding: 10px\">\n",
    "<b>📝 Note </b>\n",
    "\n",
    "**In this session we will reproduce and implement the method from the paper that put the grounds for the Google Search from Images:**  \n",
    "***[Nister, D. and Stewenius, H., 2006, June. Scalable recognition with a vocabulary tree. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'06) (Vol. 2, pp. 2161-2168). Ieee.](https://www.imperial.ac.uk/media/imperial-college/faculty-of-engineering/bioengineering/public/directions/Directions-to-Bessemer-Level-4-Meeting-Rooms-1-and-2.pdf)***\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 CBIR pipeline\n",
    "<hr width=20% align=left>\n",
    "We can distinguish two main stages in a CBIR framework: an **offline** stage, and an **online** stage [ref]. These stages constitute the high-level architecture; individual components would make use of a mixture of techniques (including, for example, supervised and unsupervised learning).\n",
    "\n",
    "<div style=\"img {align: left}\">\n",
    "<img src=\"images/pipeline_extended.png\">\n",
    "<em>Image from Zheng et al 2017. \"SIFT meets CNN: A decade survey of instance retrieval.\"</em>\n",
    "<p/>\n",
    "</div>\n",
    "\n",
    "\n",
    "The objective of the **offline** stage is to use the image stack to build an indexed database. We tend to concentrate most of the computational effort in this stage of creation, to ease, instead, the online stage.\n",
    "It is concerned with two main operations:\n",
    "- Create a representation of the images\n",
    "- Efficiently index the images \n",
    "\n",
    "\n",
    "\n",
    "Given a *query* image, the objective of the **online** stage is to score part (or all) of the images in the database, and return the ones with the higest scores.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is how we would implement a simple CBIR system:  we will divide the CBIR into different functionalities and address each functional block as we go through the notebook. In the last part of the session, we will put everything together."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CBIR:\n",
    "    def __init__(self, dataset):\n",
    "        self.dataset = dataset\n",
    "        self.database = None  # we haven't built an indexed database yet\n",
    "        return\n",
    "    \n",
    "    #-- TASK 1\n",
    "    def find_keypoints(self, image):\n",
    "        # Implement me using MSER, please\n",
    "        raise NotImplemented\n",
    "        \n",
    "    #-- TASK 2\n",
    "    def extract_features(self, image):\n",
    "        # Implement me using SIFT, please\n",
    "        raise NotImplemented\n",
    "    \n",
    "    #-- TASK 3\n",
    "    def create_vocabulary(self, image):\n",
    "        # Implement me using extract_features and BOW, please\n",
    "        raise NotImplemented\n",
    "\n",
    "    #-- TASK 4\n",
    "    def encode(self, dataset):\n",
    "        # Implement me using vocabulary tree, please\n",
    "        raise NotImplemented\n",
    "    \n",
    "    #-- TASK 5\n",
    "    def score(self, ref_image, query_image):\n",
    "        raise NotImplemented\n",
    "    \n",
    "    #-- TASK 6\n",
    "    def retrieve(self, query):\n",
    "        # this is the function we have described above\n",
    "        raise NotImplemented"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## **2. Features Extraction**\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Find keypoints\n",
    "<hr width=20% align=left>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"margin:auto; float:right; margin-left: 50px; width: 45%\">\n",
    "<img src=\"images/features_extraction_only.jpeg\">\n",
    "<em>The decomposition of an image into several \"distinctive\" localized regions</em>\n",
    "</div>\n",
    "\n",
    "In this section we are going to learn how to implement the function:\n",
    "```python\n",
    "def find_keypoints(self, image):\n",
    "    raise features\n",
    "```\n",
    "which extract a set of keypoints later used to describe the image.\n",
    "\n",
    "Keypoints can be thought of as **landmarks** in a scene. Similar to the intuitive \"human\" notion of landmarks, keypoints are distinctive locations in space. Unlike what humans treat as a landmark, they can be computed\n",
    "directly from image data, based on the principle that landmarks should be relatively sparse, distinctive, and stable. Once landmarks have been found, they can be used as reference points around which to build descriptions of surrounding image structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Manipulating images\n",
    "\n",
    "To perform fast manipulations on the images, we will use the [open-cv library](https://docs.opencv.org/master/d6/d00/tutorial_py_root.html). We start by importing it, together with the `numpy` library and the `matplotlib` library for image plotting.\n",
    "\n",
    "We also call some functions that take care of handling our image dataset, manipulating and showing our images, and showing the landmark points that we are going to detect."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cv2\n",
    "import numpy as np\n",
    "from matplotlib import pyplot as plt\n",
    "\n",
    "import cbir\n",
    "\n",
    "# Loading the dataset\n",
    "dataset = cbir.Dataset()\n",
    "descriptor = cbir.descriptors.Orb()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's look at a random image from the dataset:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "img = dataset.get_random_image()\n",
    "\n",
    "# Plotting the image\n",
    "plt.figure(figsize=(10,10))\n",
    "dataset.show_image(img)\n",
    "plt.title(\"Random image from the dataset\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Corner detector \n",
    "\n",
    "A possible set of interesting points is given by the corners of the objects in the image. We will use the corner detector operator developed by [Harris and Stephens](https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_features_harris/py_features_harris.html), to extract them from the image.\n",
    "\n",
    "Let's start by loading an image with well defined corners. We will load it in grayscale.\n",
    "We can also freely manipulate the image using `numpy`, as in the following example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Loading and displaying an image\n",
    "img = dataset.read_image('110901.jpg')\n",
    "z = np.sin(img/10.)\n",
    "\n",
    "# Plotting functions\n",
    "plt.figure(figsize=(12,4))\n",
    "plt.subplot(121)\n",
    "dataset.show_image(img, gray=True)\n",
    "plt.title('110901.jpg')\n",
    "plt.subplot(122)\n",
    "dataset.show_image(z, gray=True)\n",
    "plt.title(\"$\\sin(I/10)$\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The opencv implementation of the detector is found in `cv2.cornerHarris()` ([here is the documentation](https://docs.opencv.org/2.4/modules/imgproc/doc/feature_detection.html?highlight=cornerharris#cornerharris)). You can try to tune the parameters of the function to improve your corner detection. You are also invited to experiment with different pitcures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "<b>📝 Action</b>\n",
    "\n",
    "Try changing the images above and the parameters of the corner detector, to see how this affect the results. Take a look at [the documentation](https://docs.opencv.org/2.4/modules/imgproc/doc/feature_detection.html?highlight=cornerharris#cornerharris) of the `cv2.cornerHarris()` function for more details about the meaning of each parameter.\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "cbir.marking.this_is_an_action_cell()\n",
    "\n",
    "\n",
    "# Corner Detector parameters\n",
    "\n",
    "# --- Add your code here ---\n",
    "block_size = 11\n",
    "kernel_size = 11\n",
    "aperture_parameter = 0.01\n",
    "treshold = 0.001\n",
    "# --- End of custom code ---\n",
    "\n",
    "\n",
    "# --- Plotting - do not remove the code below ---\n",
    "gray= cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)\n",
    "dst = cv2.cornerHarris(gray, \n",
    "                       blockSize=block_size, \n",
    "                       ksize=kernel_size, \n",
    "                       k=aperture_parameter)\n",
    "dst = dst > treshold*dst.max()\n",
    "\n",
    "plt.figure(figsize=(15,10))\n",
    "descriptor.show_corners_on_image(gray,dst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Better keypoint detectors\n",
    "\n",
    "Clearly, corners are not the only interesting locations of an image. This calls for more general and sophisticated keypoints detectors. \n",
    "\n",
    "An example of a modern keypoint detector is the [Scale Invariant Feature Transform (SIFT)](https://link.springer.com/content/pdf/10.1023/B:VISI.0000029664.99615.94.pdf) method. SIFT is an image descriptor for image-based matching and recognition developed by David Lowe (1999, 2004). This descriptor, as well as related image descriptors, are used for a large number of purposes in computer vision for point matching between different views of a 3-D scene, and view-based object recognition. The SIFT descriptor is approximately invariant to translations, rotations and scaling transformations in the image domain and robust to moderate perspective transformations and illumination variations [Lowe, 2004].\n",
    "\n",
    "Another advanced keypoint detector (and descriptor, as we will see later) is given by the [ORB detector (Oriented FAST and Rotated BRIEF](https://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_orb/py_orb.html), which is a faster but slightly less accurate version of SIFT.\n",
    "\n",
    "In the following code, you will set up an ORB detector function which you can test on different images. Now one could use this function on the entire dataset, building a list of interesting keypoints for each image. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "<b>📝 Action</b>\n",
    "\n",
    "After looking at the [documentation for the ORB detector](https://docs.opencv.org/3.4/db/d95/classcv_1_1ORB.html#adc371099dc902a9674bd98936e79739c), especially the `create()` and `detect()` methods, try implement to the function below, which takes an image as input and returns a list of [keypoints](https://docs.opencv.org/3.4/d2/d29/classcv_1_1KeyPoint.html) generated by the ORB detector.\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "cbir.marking.this_is_an_action_cell()\n",
    "\n",
    "\n",
    "def find_keypoints(image):\n",
    "    ''' This function should take an image as input and return a list\n",
    "    of keypoints as output\n",
    "    '''\n",
    "    # --- Add your code here ---\n",
    "    # Creating the detector and setting some properties\n",
    "    orb = cv2.ORB.create()\n",
    "    \n",
    "    # Detecting the keypoints\n",
    "    keypoints = orb.detect(image)\n",
    "    # --- End of custom code ---\n",
    "    return keypoints"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary outline=\"1pt\">🆘 Can't move forward? Click here to see a possible solution</summary>\n",
    "\n",
    "```python\n",
    "def find_keypoints(image):\n",
    "    ''' This function should take an image as input and return a list\n",
    "    of keypoints as output\n",
    "    '''\n",
    "    \n",
    "    # Creating the detector and setting some properties\n",
    "    orb = cv2.ORB.create()\n",
    "    \n",
    "    # Detecting the keypoints\n",
    "    keypoints = orb.detect(image)\n",
    "    \n",
    "    return keypoints\n",
    "```  \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now have a function to detect the keypoints, together with their scale and orientation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "img = dataset.read_image('110901.jpg')\n",
    "\n",
    "keypoints = find_keypoints(img)\n",
    "\n",
    "plt.figure(figsize=(15,10))\n",
    "# Only displaying every 10 keypoints\n",
    "img2 = cv2.drawKeypoints(img, keypoints[::10], None, color=(0,255,0), flags=4)\n",
    "dataset.show_image(img2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "<b>📝 Action</b>\n",
    "\n",
    "After looking at the [documentation for the ORB detector](https://docs.opencv.org/3.4/db/d95/classcv_1_1ORB.html#adc371099dc902a9674bd98936e79739c), try to change some parameters to see how the keypoints detection is affected. Note that, as a rule of thumb, a good image description requires around 1500 keypoints at different scales.\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also try it on different images while you modify its implementation / parameters, to get an idea of the weaknesses and strenghts of the method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "cbir.marking.this_is_an_action_cell()\n",
    "\n",
    "\n",
    "# Try the above on a random image of the dataset\n",
    "# --- Add your code here ---\n",
    "image_id = ...\n",
    "# --- End of custom code ---\n",
    "\n",
    "\n",
    "img = dataset.read_image('110901.jpg')\n",
    "\n",
    "keypoints = find_keypoints(img)\n",
    "\n",
    "plt.figure(figsize=(15,10))\n",
    "# Only displaying every 10 keypoints\n",
    "img2 = cv2.drawKeypoints(img, keypoints[::10], None, color=(0,255,0), flags=4)\n",
    "dataset.show_image(img2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "<br>\n",
    "\n",
    "**2.2 Extract local features**  \n",
    "<hr width=20% align=left>\n",
    "<div style=\"margin: auto; float: left; margin-right: 50px; width: 19%\">\n",
    "<img src=\"images/bow.png\">\n",
    "<em>Bag of visual words <a href=\"https://towardsdatascience.com/bag-of-visual-words-in-a-nutshell-9ceea97ce0fb\">[source]</a></em>\n",
    "</div>\n",
    "\n",
    "In this section we are going to learn how to implement the function:\n",
    "```python\n",
    "def extract_descriptors(image, keypoints):\n",
    "    return embedding\n",
    "```\n",
    "\n",
    "To summarize all the interesting features of a given image, we will implement the [\"Bag of visual words\" model](https://towardsdatascience.com/bag-of-visual-words-in-a-nutshell-9ceea97ce0fb). It borrows the \"bag of words\" concept from the natural language processing field, and implements a visual surrogate.\n",
    "\n",
    "In CBIR an image is transformed to some kind of feature space. The motivation is to achieve an implicit alignment so as to eliminate the impact of background and potential transformations or changes while keeping the intrinsic visual content distinguishable.\n",
    "\n",
    "\n",
    "Once we have obtained the features of an image, we will implement the \"Bag of visual words\" model. It borrows the concept of \"bag of words\" from the natural language processing field, and implements its visual \"equivalent\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "<b>📝 Action</b>\n",
    "\n",
    "After looking at the [documentation for the ORB detector](https://docs.opencv.org/3.4/db/d95/classcv_1_1ORB.html#adc371099dc902a9674bd98936e79739c), try implement to the function below, which takes an image and a list of keypoints as input and returns the computed ORB descriptor as output\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "cbir.marking.this_is_an_action_cell()\n",
    "\n",
    "\n",
    "def extract_descriptors(image, keypoints):\n",
    "    ''' This function should take an image and keypoints as input and return a list\n",
    "    of  ORB features as output\n",
    "    '''\n",
    "    # --- Add your code here ---\n",
    "    orb = cv2.ORB.create(1500, nlevels=32)\n",
    "    keypoints, features = orb.compute(image, keypoints)\n",
    "    # --- End of custom code ---\n",
    "    return features"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary outline=\"1pt\">🆘 Can't move forward? Click here to see a possible solution</summary>\n",
    "\n",
    "```python\n",
    "def extract_descriptors(image, keypoints):\n",
    "    ''' This function should take an image as input and return a list\n",
    "    of keypoints as output\n",
    "    '''\n",
    "    orb = cv2.ORB.create(1500, nlevels=32)\n",
    "    keypoints, features = orb.compute(image, keypoints)\n",
    "    return features\n",
    "```  \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can try the function by looking at the first **5** descriptors extracted by the algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "img = dataset.read_image('131500.jpg')\n",
    "\n",
    "keypoints = find_keypoints(img)\n",
    "features = extract_descriptors(img, keypoints)\n",
    "\n",
    "print(\"Descriptor for the 1st keypoint:\\n {}\".format(features[0]))\n",
    "print(\"Descriptor for the 2nd keypoint:\\n {}\".format(features[1]))\n",
    "print(\"Descriptor for the 3rd keypoint:\\n {}\".format(features[2]))\n",
    "print(\"Descriptor for the 4th keypoint:\\n {}\".format(features[3]))\n",
    "print(\"Descriptor for the 5th keypoint:\\n {}\".format(features[4]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we are able to extract some descriptors from the keypoints in the image, let's visualize some of them"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "img = dataset.read_image('131200.jpg')\n",
    "keypoints = find_keypoints(img)\n",
    "patches = descriptor.extract_patches(img, keypoints)\n",
    "features = extract_descriptors(img, keypoints)\n",
    "\n",
    "descriptor.show_random_descriptors(img, keypoints, patches, features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course we can try this on random images too"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "img = dataset.get_random_image()\n",
    "\n",
    "keypoints = find_keypoints(img)\n",
    "patches = descriptor.extract_patches(img, keypoints)\n",
    "features = extract_descriptors(img, keypoints)\n",
    "\n",
    "descriptor.show_random_descriptors(img, keypoints, patches, features)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You have now completed the first half of the tutorial!\n",
    "\n",
    "Here are a few resources you can consult for more technical informations of keypoints and their description:\n",
    "\n",
    "1. http:https://vision.stanford.edu/teaching/cs231a_autumn1112/lecture/lecture11_detectors_descriptors_cs231a.pdf\n",
    "2. http:https://vision.stanford.edu/teaching/cs231a_autumn1112/lecture/lecture12_SIFT_single_obj_recog_cs231a.pdf\n",
    "3. https://docs.opencv.org/3.4/db/d27/tutorial_py_table_of_contents_feature2d.html\n",
    "\n",
    "\n",
    "In particular, there is one important point to note about the keypoints we have used in this example. In contrast to Harris keypoints, which predominantly detect corners, the SIFT keypoints assign a spatial scale as well: the distinctive regions are NOT necessarily small - they can be as large as the entire image! That is, the visual fingerprints - though they are of the same dimensions (typically 128 elements) - might describe the entire scene, though in an approximate way. Details on individual smaller regions are provided by descriptors associated with keypoints of smaller spatial scale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## **Chapter 3: Creating a visual vocabulary**\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this section we are going to learn how to implement the function:\n",
    "```python\n",
    "def create_vocabulary(features):\n",
    "    # Implement me using Hierarchical kmeans\n",
    "    # return the tree and the index\n",
    "```\n",
    "\n",
    "<br>\n",
    "    <b>Why using the vocabulary?</b><br>\n",
    "Image retrieval works very well when you have a very large vocabulary. The vocabulary is the set of all the features extracted from the available data.\n",
    "\n",
    "A large vocabulary can describe the database more finely, allowing better retrieval.\n",
    "\n",
    "However, having large codebooks is unfeasible because **non-hierarchical methods do not scale well**.\n",
    "Let's see why.\n",
    "\n",
    "We have a feature, ***q***, and a list of database features ***D***.\n",
    "<u>The objective is to find the feature ***d<sub>i</sub>*** in the database, that is closed to the query feature ***q***.</u>\n",
    "We consider two cases:\n",
    "- A flat list\n",
    "- A hierarchical tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "<div style=\"margin:auto; float:left; margin-right: 50px; width: 38%;\">\n",
    "    <center>Case 1: A flat list. You can think of this as a tree with only <code>l = 1</code> levels, and <code>k = 27</code> branches.</center>\n",
    "    <center>To find the closest element in the database you perform <code>27</code> comparisons, because you compare the query feature <i><b>q</b></i> directly with all the 27 database feature <i><b>d<sub>i</sub></b></i></center>\n",
    "    <br>\n",
    "<img src=\"images/flat_list.png\">\n",
    "    <center>$k^l$</center>\n",
    "</div>\n",
    "<div style=\"margin:auto; float:right; margin-left: 50px; width: 48%;\">\n",
    "    <center>Case 1: A tree with <code>l = 3</code> levels, and <code>k = 3</code> branches.</center>\n",
    "    <center>The find the closest element in the database you perform <code>9</code> comparisons, because you compare the query feature <i><b>q</b></i> with the first <code>k = 3</code> virtual elements, up to <code>l = 3</code> levels down.</center>\n",
    "<img src=\"images/tree_27.png\">\n",
    "<center>$k * l$</center>\n",
    "</div>\n",
    "\n",
    "<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The most important contribution of the paper we implement is\n",
    "an **indexing mechanism** that enables extremely efficient\n",
    "retrieval.\n",
    "\n",
    "It proposes a **hierarchical TF-IDF** scoring using\n",
    "hierarchically defined visual words that form a vocabulary\n",
    "tree.   \n",
    "This allows much more efficient lookup of visual\n",
    "words, which enables the use of a larger vocabulary, which\n",
    "is shown to result in a significant improvement of retrieval\n",
    "quality.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"margin:auto; float:right; margin-left: 50px; width: 60%\">\n",
    "<!--     <center>How we construct this vector is key for the retrieval performance</b></center> -->\n",
    "\n",
    "<img src=\"images/tree_structure.png\">\n",
    "    <center>\n",
    "    The tree directly defines the visual vocabulary\n",
    "    and an efficient search procedure in an integrated\n",
    "        manner.\n",
    "    </center>\n",
    "</div>\n",
    "<br>\n",
    "   \n",
    "\n",
    "In this section, we provide a structure to the set of image representations collected in **1.2**.  \n",
    "We implement the [**Vocabulary tree structure**](https://ieeexplore.ieee.org/document/1641018) illustrated by Nister [ref], which uses Hierarchical KMeans to build the tree, and Term Frequency-Inverse Document Frequency to index each sample of the database."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>  \n",
    "\n",
    "> ***Recipe:***   \n",
    "> ***2.1.*** Building the tree using hierarchical k-means   \n",
    "> ***2.2*** ***Indexing*** the database using TF-IDF (Term Frequency-Inverse Document Frequency)   \n",
    "> ***2.3*** ***Scoring*** two images   \n",
    "> ***2.4*** ***Retrieving*** similar images   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "### 3.1 Building the tree using hierarchical k-means\n",
    "---\n",
    "\n",
    "<br>\n",
    "<div style=\"margin:auto; float:left; margin-right: 50px; width: 33%;\">\n",
    "<img src=\"images/kmeans.png\">\n",
    "</div>\n",
    "<br>\n",
    "\n",
    "In this section we are going to hierarchically separate the features into clusters using ***hierarchical k-means***.\n",
    "\n",
    "`k` defines the branch factor (number of\n",
    "children of each node) of the tree. First, an initial k-\n",
    "means process is run on the training data, defining k cluster\n",
    "centers. The training data is then partitioned into k groups,\n",
    "where each group consists of the descriptor vectors closest\n",
    "to a particular cluster center.\n",
    "\n",
    "The procedure is applied recursively on each of the clusters, until we reach a depth `L`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "!dot -c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "import cbir\n",
    "import numpy as np\n",
    "\n",
    "# initialise the database\n",
    "dataset = cbir.Dataset()\n",
    "subset = dataset.subset[0:10]\n",
    "orb = cbir.descriptors.Orb()\n",
    "voc = cbir.encoders.VocabularyTree(n_branches=2, depth=2, descriptor=orb)\n",
    "\n",
    "# perform hierarchical k-means clustering on the features\n",
    "features = np.array([[1.], [2.], [11.], [12.]])\n",
    "voc.fit(features)\n",
    "\n",
    "\n",
    "# plot the graph\n",
    "fig = voc.draw(labels=voc.nodes, figsize=(5, 3), node_color=\"C1\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The internal nodes of the tree are the cluster centers\n",
    "- The leaves of the node are the features we started from\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Try it out with your own features now. Remember:\n",
    "- `n_branches` controls how many nodes to create from a parent node (`k` in the picture above)\n",
    "- `depth` controls the number of levels in the tree (`L` in the picture above)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_branches = 2\n",
    "depth = 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# initialise the database\n",
    "voc = cbir.encoders.VocabularyTree(n_branches=n_branches, depth=depth, descriptor=orb)\n",
    "\n",
    "# perform hierarchical k-means clustering on the features\n",
    "voc.fit(np.random.randn(150, 1))\n",
    "\n",
    "# plot the graph\n",
    "fig = voc.draw(figsize=(20, 7), labels=voc.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br> \n",
    "\n",
    "### 3.2 Indexing the database using TF-IDF (Term Frequency-Inverse Document Frequency)\n",
    "---\n",
    "\n",
    "<div style=\"margin:auto; float:right; margin-roght: 50px; width: 40%\">\n",
    "<img src=\"images/index.png\">\n",
    "<!-- <em>Add image caption with reference</em> -->\n",
    "</div>\n",
    "<br>\n",
    "\n",
    "\n",
    "Indexing is the process of building and storing a **database table** to perform efficient **lookups**, i.e. to quickly find a specific database element.  \n",
    "In the image retrieval problem we store an index that associates an image, with its vector representation: **`image: vector`**\n",
    "\n",
    " In this section we are going to learn how to implement the function:\n",
    "```python\n",
    "def encode(dataset):\n",
    "    return indexed_database\n",
    "```\n",
    "\n",
    "In this section we provide a structure to the set of image representations collected in **1.2**.  \n",
    "We implement the [**Vocabulary tree structure**](https://ieeexplore.ieee.org/document/1641018), which uses inverted indices and hierarchical k-means to build the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***Recipe:***  \n",
    "1. Given an image, for each feature, we propagate the feature down the tree.   \n",
    "2. We start from the root of the tree, and find the closest node among its children nodes.  \n",
    "3. We apply the same procedure until we reach the bottom of the tree, a leaf.  \n",
    "4. Every time we pass through a node, we register the passage by adding +1 to the node, for that specific image.  \n",
    "\n",
    "<br>\n",
    "<div style=\"margin:auto; float:left; margin-right: 50px; width: 42%;\">\n",
    "    <center>\n",
    "    <b>Feature #1</b>\n",
    "        <br>\n",
    "    </center>\n",
    "<img src=\"images/encoded_a.png\">\n",
    "</div>\n",
    "<div style=\"margin:auto; float:right; margin-left: 50px; width: 42%;\">\n",
    "    <center>\n",
    "    <b>Feature #2</b>\n",
    "        <br>\n",
    "    </center>\n",
    "<img src=\"images/encoded_b.png\">\n",
    "</div>\n",
    "<br>\n",
    "<br>\n",
    "<div style=\"margin:auto; float:left; margin-right: 50px; width: 42%;\">\n",
    "        <center>\n",
    "            <b>...</b>\n",
    "            <br>\n",
    "    <b>Feature #3</b>\n",
    "    </center>\n",
    "<img src=\"images/encoded_c.png\">\n",
    "</div>\n",
    "<div style=\"margin:auto; float:right; margin-left: 50px; width: 42%;\">\n",
    "        <center>\n",
    "            <b>...</b>\n",
    "            <br>\n",
    "    <b>Feature #4</b>\n",
    "    </center>\n",
    "<img src=\"images/encoded_d.png\">\n",
    "</div>\n",
    "\n",
    "<!-- <em>Add image caption with reference</em> -->\n",
    "</div>\n",
    "<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"margin:auto; float:center; width: 55%;\">\n",
    "    <br>\n",
    "    <center>\n",
    "        When we have propagated all the features, we count the number of passages at each node.     \n",
    "        <b>This represents our encoded image</b>    \n",
    "    </center>\n",
    "    <img src=\"images/encoded_all.png\">\n",
    "</div>\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This results into a tf-idf scheme: when we cross a node, we leave a fingerprint on the node:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "\n",
    "# let's take a look at how we can encode an image\n",
    "image_id = \"100000\"\n",
    "\n",
    "# let's see the images we are encoding\n",
    "dataset.show_image(image_id)\n",
    "print(\"Image as perceived by us:\")\n",
    "plt.show()\n",
    "\n",
    "# as a graph\n",
    "voc.subgraph(image_id)\n",
    "print(\"Image embedding as graph:\")\n",
    "plt.show()\n",
    "\n",
    "# and its corresponding vector\n",
    "embedding = voc.embedding(dataset.read_image(image_id))\n",
    "print(\"\\nImage embedding as vector:\", embedding, \"\\n\")\n",
    "fig = plt.figure(figsize=(20, 3))\n",
    "plt.bar(np.arange(len(embedding)), embedding)\n",
    "plt.gca().set_title(\"TF-IDF\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-info\">\n",
    "<b>📝 Action</b>\n",
    "\n",
    "Change the `image_id` above and try encoding a different image\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "cbir.marking.this_is_an_action_cell()\n",
    "\n",
    "\n",
    "# --- Add your code here ---\n",
    "\n",
    "image_id = \"100000\"\n",
    "\n",
    "# --- End of custom code ---\n",
    "\n",
    "\n",
    "# --- Plotting - do not remove the code below ---\n",
    "dataset.show_image(image_id)\n",
    "print(\"Image as perceived by us:\")\n",
    "plt.show()\n",
    "\n",
    "# as a graph\n",
    "voc.subgraph(image_id)\n",
    "print(\"Image embedding as graph:\")\n",
    "plt.show()\n",
    "\n",
    "# and its corresponding vector\n",
    "embedding = voc.embedding(dataset.read_image(image_id))\n",
    "print(\"\\nImage embedding as vector:\", embedding, \"\\n\")\n",
    "fig = plt.figure(figsize=(20, 3))\n",
    "plt.bar(np.arange(len(embedding)), embedding)\n",
    "plt.gca().set_title(\"TF-IDF\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## **Chapter 4. Scoring and Retrieving (the online phase)**\n",
    "---\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- <div style=\"margin-left: 230px\"> -->\n",
    "<br>\n",
    "\n",
    "<div style=\"margin:auto; float:right; margin-left: 50px; width: 30%\">\n",
    "<img src=\"images/image_similarity.jpg\">\n",
    "</div>\n",
    "<br>\n",
    "    \n",
    "In this section we are going to learn how to implement the function:\n",
    "```python\n",
    "def score(database, image):\n",
    "    return score\n",
    "```\n",
    "\n",
    "The objective of scoring is to compare two images in their embedding form, and return a measure of their **similarity**.\n",
    "\n",
    "Once the quantization is defined, we wish to determine\n",
    "the relevance of a database image to the query image based\n",
    "on how similar the paths down the vocabulary tree are\n",
    "for the descriptors from the database image and the query\n",
    "image.\n",
    "\n",
    "<br>\n",
    "\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's grab two images from the database and get their embeddings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "# take two images by using their ids\n",
    "image_id_1 = \"104000\"\n",
    "image_id_2 = \"101000\"\n",
    "\n",
    "# read the images\n",
    "image1 = dataset.read_image(image_id_1)\n",
    "image2 = dataset.read_image(image_id_2)\n",
    "\n",
    "# and then get their embeddings\n",
    "em_1 = voc.embedding(image1)\n",
    "em_2 = voc.embedding(image2)\n",
    "\n",
    "print(\"\\nImage 1 embedding:\", em_1)\n",
    "print(\"\\n\\nImage 2 embedding:\", em_2)\n",
    "\n",
    "fig, ax = plt.subplots(1, 2, figsize=(30, 3))\n",
    "ax[0].bar(np.arange(len(em_1)), em_1)\n",
    "ax[0].set_title(\"Image 1 TF-IDF\")\n",
    "ax[1].bar(np.arange(len(em_2)), em_2)\n",
    "_ = ax[1].set_title(\"Image 2 TF-IDF\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "We can also look at their graph representations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "voc.subgraph(image_id_1)\n",
    "voc.subgraph(image_id_2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this implementation, to measure the score between two images we use <b>L2-norm</b>:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jupyter": {
     "outputs_hidden": true
    }
   },
   "source": [
    "$RMSE(x_1, x_2) = \\sqrt{\\sum(x_{1_i} - x_{2_i})^2}$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "cbir.marking.this_is_an_action_cell()\n",
    "\n",
    "def score(x1, x2):\n",
    "    \"\"\"Returns the euclidean distance between two tensors\"\"\"\n",
    "    # --- Add your code here ---\n",
    "    rmse = ...\n",
    "    # --- End of custom code ---\n",
    "\n",
    "# --- Plotting - do not remove the code below ---\n",
    "    return rmse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<details>\n",
    "  <summary outline=\"1pt\">🆘 Can't move forward? Click here to see a possible solution</summary>\n",
    "\n",
    "```python\n",
    "def score(x1, x2):\n",
    "    \"\"\"Returns the euclidean distance between two tensors\"\"\"\n",
    "    # --- Add your code here ---\n",
    "    rmse = np.sqrt(np.mean(np.square(x1 - x2)))\n",
    "    # --- End of custom code ---\n",
    "```  \n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see what is the score between the two images we have just chosen.    \n",
    "In scoring how similar the the two images are (the function is commutative), we measure the score between the two respective embeddings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-heading alert-danger\" style=\"background-color: white; border: 2px solid; border-radius: 5px; color: #000; border-color:#AAA; padding: 10px\">\n",
    "<b>📝 Note </b>\n",
    "\n",
    "Note that, because the score function we are using is a form of <b>distance </b> between two images, lower is better.    \n",
    "Lower scores means that the two images are very close!\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's create our dataset instance\n",
    "dataset = cbir.Dataset()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's create the vocabulary tree\n",
    "voc = cbir.encoders.VocabularyTree(n_branches=4, depth=4, descriptor=orb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now, let's extract the features\n",
    "# This takes about 10 minutes on a personal computer. \n",
    "# We have done it already for you and saved all the features in `data/features_orb.hdf5`. If you want to do it \n",
    "# from scratch, just delete or rename that file.\n",
    "features = voc.extract_features(dataset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We can now construct the tree using the extracted features\n",
    "voc.fit(features)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's extract the embeddings for the two following images\n",
    "image_id_1 = \"104000\"\n",
    "image_id_2 = \"104002\"\n",
    "\n",
    "# read the images\n",
    "image1 = dataset.read_image(image_id_1)\n",
    "image2 = dataset.read_image(image_id_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plot image 1\n",
    "dataset.show_image(image1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "# plot image 2\n",
    "dataset.show_image(image2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "# and then get their embeddings\n",
    "em_1 = voc.embedding(image1)\n",
    "em_2 = voc.embedding(image2)\n",
    "\n",
    "fig, ax = plt.subplots(2, 1, figsize=(20, 5))\n",
    "ax[0].bar(np.arange(len(em_1)), em_1)\n",
    "ax[0].set_title(\"Image 1 TF-IDF\")\n",
    "ax[1].bar(np.arange(len(em_2)), em_2)\n",
    "_ = ax[1].set_title(\"Image 2 TF-IDF\")\n",
    "plt.tight_layout()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "s = score(em_1, em_2)\n",
    "print(\"The score is:\", s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "### 4.2 Retrieving an image from the database\n",
    "---\n",
    "Here we bring together all the concepts we have illustrated above to build our Large-Scale CBIR system.    \n",
    "Remember that we in the previous exercise we have created an encoder:   \n",
    "a function that takes an image and returns a <b>representation</b> of it, embedding key information about its content, in a way that it is useful to retrieve similar ones.\n",
    "\n",
    "In the following exercise we will use this encoder to index a database for retrieval."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "metadata": {},
   "outputs": [],
   "source": [
    "# now that we have a tranied encoder, let's create our database for retrieval\n",
    "db = cbir.Database(dataset, encoder=voc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# And we can index all the images\n",
    "# you can use db.index() to index all the images at once\n",
    "db.index()\n",
    "\n",
    "# save the database on disk for later\n",
    "db.save()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "query = \"104000.jpg\"\n",
    "scores = db.retrieve(query)\n",
    "db.show_results(query, scores, figsize=(30, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "query = random.choice(dataset)\n",
    "scores = db.retrieve(query)\n",
    "db.show_results(query, scores, figsize=(20, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "\n",
    "## **[Optional] Chapter 5. Image encoding with Deep Convolutional Neural Networks**\n",
    "---\n",
    "\n",
    "The excercises below this point are not mandatory. They provide a wider picture on how to build an efficient image representation.\n",
    "We will illustrate how to use a pretrained image classifier to represent the features of an image\n",
    "- 4.1 Using the output probabilities of a pretrained AlexNet to get the enbedding of an image\n",
    "- 4.2 Using the one-before-the-last layer of a DCNN as features to propagate in the tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.1 Using the output probabilities of a pretrained AlexNet**\n",
    "\n",
    "In this optional assignement, we are going to replace the `encode` mapping with the outpu probabilities of *[AlexNet](https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf)*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's download a pretrained version of AlexNet from torchvision\n",
    "import torch\n",
    "import torchvision\n",
    "import matplotlib.pyplot as plt\n",
    "import cbir\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = cbir.Dataset().subset[0:100]\n",
    "db_ax_enc = cbir.Database(dataset, encoder=cbir.encoders.AlexNet())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "db_ax_enc.index()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "image_path = \"104000.jpg\"\n",
    "embedding_ax_enc = db_ax_enc.embedding(image_path)\n",
    "\n",
    "plt.figure(figsize=(20, 5))\n",
    "plt.bar(np.arange(len(embedding_ax_enc)), embedding_ax_enc)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "query = random.choice(db_ax_enc.dataset.image_paths)\n",
    "scores = db_ax_enc.retrieve(query)\n",
    "db_ax_enc.show_results(query, scores, figsize=(20, 10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**5.2 Using the features of a DCNN**\n",
    "\n",
    "We can compare the results above in which we use AlexNet as an encoder with the DESCRIPTOR+VOCABULARY method, in which -- rather than using AlexNet as an encoder -- descriptors are taken from an intermediate layer of AlexNet; these are treated as feature vectors (multiple ones for each image) which are then encoded using a vocabulary tree."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's create the vocabulary tree using descriptors generated by a neural network\n",
    "voc_nn = cbir.encoders.VocabularyTree(n_branches=4, depth=4, descriptor=cbir.descriptors.AlexNet())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Now, let's extract the features using AlexNet\n",
    "features = voc_nn.extract_features(dataset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We can now construct the tree using the extracted features\n",
    "voc_nn.fit(features)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# we create the model as usual\n",
    "db_nn = cbir.Database(dataset, encoder=voc_nn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# and now we index the database,\n",
    "# which means that we calculate the embeddings for all the images and store them in db_nn._database\n",
    "db_nn.index()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "scores = db_nn.retrieve(query)\n",
    "db_nn.show_results(query, scores, figsize=(20, 10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}