clustering_similar_images_pHash.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is adapated from the original code written by Kruttika Nadig for the Tattle blog on 30th October 2020: https://web.archive.org/web/20230608205800/https://blog.tattle.co.in/clustering-similar-images-with-phash/\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***\n",
    "___"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Image hashing is a technique for generating distinct \"fingerprints\" of images which can be used to identify and group together similar images. \"phash\" is one of the most popular and effective hashing algorithms. We tried it on 10k images from our archive and had promising results. This blog is a walkthrough of how we constructed the phashes with the [Imagehash library](https://web.archive.org/web/20230608205800/https://pypi.org/project/ImageHash/), created easily navigable clusters (groups) of images whose fingerprints (hashes) are identical, and found images that are similar to a query image. An elegant feature of phashes is that similar images will have similar hashes. To know how the hashing algorithm works, check out this [other blog](http://www.hackerfactor.com/blog/index.php?/archives/432-Looks-Like-It.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import necessary libraries\n",
    "import imagehash\n",
    "import os\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "from PIL import Image\n",
    "from datetime import date, datetime, timedelta\n",
    "from time import perf_counter\n",
    "import wget\n",
    "import matplotlib.pyplot as plt\n",
    "import matplotlib.image as mpimg\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Steps\n",
    "\n",
    "### 1. Loading and hashing images\n",
    "We define a function to load images from a local folder called \"images\" in a loop, generate their phashes and store them in a dictionary:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_hashes(path):\n",
    "    hashfunc = imagehash.phash\n",
    "    failed = []\n",
    "    total = 0\n",
    "    success = 0\n",
    "    image_filenames = []\n",
    "    image_filenames += [file for file in os.listdir(path)]\n",
    "    images = {}\n",
    "    for img in image_filenames:\n",
    "        if img.split(\".\")[-1] in [\"jpg\", \"jpeg\", \"png\"]:\n",
    "            try:\n",
    "                phash = hashfunc(Image.open(os.path.join(path, img)).convert(\"RGBA\"))\n",
    "                images[img] = str(phash)\n",
    "                success +=1\n",
    "            except Exception:\n",
    "                failed.append(img)\n",
    "                continue\n",
    "            total +=1\n",
    "    print(\"phash generated for {} of {} images\".format(success, total))\n",
    "    return images"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calling the function and timing its execution in seconds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "start = perf_counter()\n",
    "hashes = get_hashes(os.getcwd()+\"/images\")\n",
    "delta = perf_counter() - start\n",
    "print(delta)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2. Cluster creation\n",
    "Next, we load the hashes into a Pandas dataframe for easier viewing and data manipulation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df = pd.DataFrame.from_dict(hashes, orient=\"index\", columns = [\"phash\"])\n",
    "df.reset_index(inplace=True)\n",
    "df.rename(columns={\"index\":\"filename\"}, inplace=True)\n",
    "df.head(3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next two cells convert the image filenames into their public URLs which can be opened for quick image viewing."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "def add_url(filename):\n",
    "    url = \"https://s3.ap-south-1.amazonaws.com/sharechat-scraper.tattle.co.in/\" + filename\n",
    "    return url"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df[\"img_urls\"] = df[\"filename\"].map(add_url)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then we apply some grouping, aggregation and sorting operations to the data and see the image clusters emerge -"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "grouped = df.groupby(by=\"phash\").agg({\"filename\":\"size\", \"img_urls\":list})\n",
    "grouped.rename(columns={'filename':'count'}, inplace=True)\n",
    "sorted = grouped.sort_values(\"count\", ascending=False)\n",
    "sorted.reset_index(inplace=True)\n",
    "sorted.head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output of the cell above shows the first five rows of the transformed data. The \"phash\" column contains distinct image hashes. The \"count\" column shows us how many images are clustered together, i.e. they share the same phash and therefore will have similar visual content. The \"img_urls\" column will let us look at the images inside each cluster by clicking on their URLs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "len(sorted)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've created 9665 image clusters out of the initial 10,800 images. This looks like an unhelpful result, and it indeed is, because we haven't specified how many images a cluster should contain for it to be considered a cluster. Let's fix that now. Since we're just exploring, we'll be lenient and keep the minimum number of images per cluster low. We'll compare results with n=2 and n=5."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Number of clusters when minimum number of images is 2:\", len(sorted[sorted[\"count\"] >= 2]))\n",
    "print(\"Number of clusters when minimum number of images is 5:\", len(sorted[sorted[\"count\"] >= 5]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3. Querying\n",
    "We now have a dataframe of 655 clustered images where each cluster contains at least two images that share the same phash. What if we get a new image, and want to check if there are any images similar to it in our data? We can use the phashes to compare the images. When we defined the get_hashes() function above, we converted the hashes into hex strings to make them more compact and readable. To compare the hashes, we first convert them back into their original form (binary arrays). Then we calculate the Hamming distance between the binary arrays. A Hamming distance of up to 10 is a decent indicator for similarity, so we can use that as a threshold for returning similar images. Let's use the phash of the biggest cluster (the one with 34 images) as a query and see what we get:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Find similar images\n",
    "query = \"81d07fffe0611a85\"\n",
    "matches = {}\n",
    "for i, row in sorted.iterrows():\n",
    "    # Convert hash hex string to original hash (binary array) \n",
    "    diff = imagehash.hex_to_hash(query) - imagehash.hex_to_hash(row[\"phash\"])\n",
    "    # phashes with Hamming distance less than 10 are likely to be similar images\n",
    "    \n",
    "    if diff <= 10:\n",
    "        print(\"Found match: \", row[\"phash\"])\n",
    "        print(\"Hamming distance from query:\", diff)\n",
    "        matches[row[\"phash\"]] = row[\"img_urls\"]\n",
    "        print(\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The query returns three phashed clusters whose Hamming distance from the query is less than or equal to 10. The first cluster, as we can see from its phash, is our query itself. The second and third clusters contain images that are near-duplicates of the images in the query cluster. Let's open an image from the query cluster, plus one image each from the second and third clusters, to see what makes them similar and yet different:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add the first image from each matched cluster to a list of images along with its local path\n",
    "images = []\n",
    "for i in matches.values():\n",
    "    img_path = \"images/\" + i[0].split(\"/\")[-1]\n",
    "    images.append(img_path)\n",
    "\n",
    "# Load and display the images\n",
    "img_arrays = []\n",
    "for img in images:\n",
    "    img_arrays.append(mpimg.imread(img))\n",
    "\n",
    "plt.figure(figsize=(15,15))\n",
    "columns = 3\n",
    "for i, image in enumerate(img_arrays):\n",
    "    plt.subplot(len(images) / columns + 1, columns, i + 1)\n",
    "    plt.xticks([])\n",
    "    plt.yticks([])\n",
    "    plt.imshow(image)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4. Conclusion\n",
    "The images from the matched clusters are very similar to the query image - only the borders are different. This demonstrates that phashes are useful not only for finding identical images (first cluster returned by the query) but also near-duplicates / similar ones with minor variations (second and third clusters returned by the query)\n",
    "More about Hamming distance:\n",
    "Hamming distance is a metric for comparing two binary data strings. While comparing two binary strings of equal length, Hamming distance is the number of bit positions in which the two bits are different. The image hashes we have generated have 64 bits each. Hashes generated with the Imagehash library have a method that allows us to get the Hamming distance simply by subtracting one hash from another as in the Querying section above. If we're feeling curious and want to do this calculation ourselves, we can modify the library's hex_to_hash() function so that it returns ordinary binary arrays that don't have this special method. Then we follow the following steps to get the Hamming distance -\n",
    "1. XOR the two hashes we want to compare\n",
    "2. Count the number of 1s (or Trues) in the result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Modify Imagehash library func to return array instead of ImageHash obj\n",
    "\n",
    "def hex_to_hash(hexstr):\n",
    "\t\"\"\"\n",
    "\tConvert a stored hash (hex, as retrieved from str(Imagehash))\n",
    "\tback to a Imagehash object.\n",
    "\tNotes:\n",
    "\t1. This algorithm assumes all hashes are either\n",
    "\t   bidimensional arrays with dimensions hash_size * hash_size,\n",
    "\t   or onedimensional arrays with dimensions binbits * 14.\n",
    "\t2. This algorithm does not work for hash_size < 2.\n",
    "\t\"\"\"\n",
    "\thash_size = int(np.sqrt(len(hexstr)*4))\n",
    "\t#assert hash_size == numpy.sqrt(len(hexstr)*4)\n",
    "\tbinary_array = '{:0>{width}b}'.format(int(hexstr, 16), width = hash_size * hash_size)\n",
    "\tbit_rows = [binary_array[i:i+hash_size] for i in range(0, len(binary_array), hash_size)]\n",
    "\thash_array = np.array([[bool(int(d)) for d in row] for row in bit_rows])\n",
    "\treturn hash_array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "xor = hex_to_hash(\"87d03e7ee0259e85\") ^ hex_to_hash(\"81d07fffe0611a85\")\n",
    "xor "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Count the number of 1s \n",
    "np.count_nonzero(xor != 0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Verifying that we get the same distance using the library method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "imagehash.hex_to_hash(\"87d03e7ee0259e85\") - imagehash.hex_to_hash(\"81d07fffe0611a85\")"
   ]
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}