association_hungarian.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Z-Zy5R377k8C"
   },
   "source": [
    "# Association Bounding Boxes with the Hungarian Algorithm\n",
    "\n",
    "This notebook demonstrates how to associate bounding boxes between successive frames in a video. This will provide the ability to not just detect, but also track objects. The `linear_sum_assignment` function in the `scipy.optimize` module implements the actual Hungarian Algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 51
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 685,
     "status": "ok",
     "timestamp": 1582133921013,
     "user": {
      "displayName": "Jeremy Cohen",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AAuE7mCv0k4RfFpV9oL2DeIvSvWyPOGBJwNG392F1TiFwg=s64",
      "userId": "01957346698928395081"
     },
     "user_tz": -60
    },
    "id": "lkFrXEr31UKq",
    "outputId": "cb8a6862-3b1b-4baf-9287-9e067890b1e4"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[100, 120, 130, 330], [300, 350, 400, 400], [577, 138, 709, 244]]\n",
      "[[50, 400, 100, 550], [99, 120, 132, 333], [302, 352, 406, 400]]\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "from scipy.optimize import linear_sum_assignment\n",
    "import numpy as np\n",
    "\n",
    "# Detections at timestep N - 1.\n",
    "A = [100, 120, 130, 330]\n",
    "B = [300, 350, 400, 400]\n",
    "C = [577, 138, 709, 244]\n",
    "\n",
    "# Detections at timestep N\n",
    "D = [50, 400, 100, 550]  # Should match no frame.\n",
    "E = [99, 120, 132, 333]  # Should match frame A.\n",
    "F = [302, 352, 406, 400] # Should match frame B.\n",
    "\n",
    "old = [A,B,C]\n",
    "new = [D,E,F]\n",
    "print(old)\n",
    "print(new)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "Cc2PDuhJ2ZWI"
   },
   "source": [
    "## Using the IOU Metric\n",
    "\n",
    "Compute the intersection-over-union (IOU) metric for each pair of bounding boxes, then use these values at input to the Hungarian Algorithm matrix.\n",
    "\n",
    "1. Create a matrix and store the IOU for all boxes.\n",
    "2. Apply the Hungarian Algorithm.\n",
    "3. Identify false positives and false negatives."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "pX7yTGkG33g-"
   },
   "outputs": [],
   "source": [
    "def compute_iou(box_1, box_2):\n",
    "    \n",
    "    \"\"\"\n",
    "    Computes the IOU metric for a pair of bounding boxes.\n",
    "    \"\"\"\n",
    "    \n",
    "    xA = max(box_1[0], box_2[0])\n",
    "    yA = max(box_1[1], box_2[1])\n",
    "    xB = min(box_1[2], box_2[2])\n",
    "    yB = min(box_1[3], box_2[3])\n",
    "    inter_area = max(0, xB - xA + 1) * max(0, yB - yA + 1)\n",
    "    \n",
    "    # Calculate Union(A,B) = A + B - Inter(A,B)\n",
    "    box1_area = (box_1[2] - box_1[0] + 1) * (box_1[3] - box_1[1] + 1)\n",
    "    box2_area = (box_2[2] - box_2[0] + 1) * (box_2[3] - box_2[1] + 1)\n",
    "    union_area = (box1_area + box2_area) - inter_area\n",
    "\n",
    "    # Compute and return the IOU metric.\n",
    "    return inter_area / float(union_area)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 690,
     "status": "ok",
     "timestamp": 1582133981598,
     "user": {
      "displayName": "Jeremy Cohen",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AAuE7mCv0k4RfFpV9oL2DeIvSvWyPOGBJwNG392F1TiFwg=s64",
      "userId": "01957346698928395081"
     },
     "user_tz": -60
    },
    "id": "yKt2hAcc1s5-",
    "outputId": "600d8e5f-3d4e-4ae5-8541-97bd1de12fdc"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0.         0.89898294 0.        ]\n",
      " [0.         0.         0.8909091 ]\n",
      " [0.         0.         0.        ]]\n"
     ]
    }
   ],
   "source": [
    "# Compute the IOU matrix for the old boxes and new boxes.\n",
    "\n",
    "iou_matrix = np.zeros((len(old), len(new)), dtype=np.float32)\n",
    "\n",
    "for i, old_box in enumerate(old):\n",
    "\n",
    "    for j, new_box in enumerate(new):\n",
    "\n",
    "        iou_matrix[i][j] = compute_iou(old_box, new_box)\n",
    "\n",
    "print(iou_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 85
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 512,
     "status": "ok",
     "timestamp": 1582134005564,
     "user": {
      "displayName": "Jeremy Cohen",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AAuE7mCv0k4RfFpV9oL2DeIvSvWyPOGBJwNG392F1TiFwg=s64",
      "userId": "01957346698928395081"
     },
     "user_tz": -60
    },
    "id": "TffZoXXc4LWU",
    "outputId": "bf5dac65-a909-4186-e5aa-163e23916621"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Match Matrix\n",
      "[[0. 1. 0.]\n",
      " [0. 0. 1.]\n",
      " [0. 0. 0.]]\n"
     ]
    }
   ],
   "source": [
    "# Go through the IOU matrix and replace positive values with 1.0, always\n",
    "# take the maximum value (if there are two positive values).\n",
    "\n",
    "for idx, iou in enumerate(iou_matrix):\n",
    "\n",
    "    iou_matrix[idx] = [1 if (x == max(iou) and max(iou) > 0) else 0 for x in iou]\n",
    "\n",
    "print(\"Match Matrix\")\n",
    "print(iou_matrix)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 483,
     "status": "ok",
     "timestamp": 1582134067543,
     "user": {
      "displayName": "Jeremy Cohen",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AAuE7mCv0k4RfFpV9oL2DeIvSvWyPOGBJwNG392F1TiFwg=s64",
      "userId": "01957346698928395081"
     },
     "user_tz": -60
    },
    "id": "wPDGZWny4mYf",
    "outputId": "a7b0daaf-0083-4ed3-fd8b-8f7114842586"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Hungarian Matrix\n",
      "[0 1 2]\n",
      "[1 2 0]\n"
     ]
    }
   ],
   "source": [
    "# Invoke the Linear Assignment Method (Hungarian Algorithm)\n",
    "\n",
    "hungarian_row, hungarian_col = linear_sum_assignment(-iou_matrix)\n",
    "\n",
    "print(\"Hungarian Matrix\")\n",
    "print(hungarian_row)\n",
    "print(hungarian_col)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "3ldjPnM24kaH"
   },
   "outputs": [],
   "source": [
    "# Create lists for matches, unmatched detections, and unmatched trackings.\n",
    "\n",
    "matches, unmatched_trackers, unmatched_detections = [], [], []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 68
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 354,
     "status": "ok",
     "timestamp": 1582134591555,
     "user": {
      "displayName": "Jeremy Cohen",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AAuE7mCv0k4RfFpV9oL2DeIvSvWyPOGBJwNG392F1TiFwg=s64",
      "userId": "01957346698928395081"
     },
     "user_tz": -60
    },
    "id": "HyfnplL6jwbc",
    "outputId": "852628a5-b940-4418-fe7b-ef55ae00ce5e"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1]\n",
      " [1 2]\n",
      " [2 0]]\n"
     ]
    }
   ],
   "source": [
    "# Reshape the hungarian matrix to make it easier to use.\n",
    "\n",
    "hungarian = np.array(list(zip(hungarian_row, hungarian_col)))\n",
    "\n",
    "print(hungarian)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 136
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 640,
     "status": "ok",
     "timestamp": 1582134594780,
     "user": {
      "displayName": "Jeremy Cohen",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AAuE7mCv0k4RfFpV9oL2DeIvSvWyPOGBJwNG392F1TiFwg=s64",
      "userId": "01957346698928395081"
     },
     "user_tz": -60
    },
    "id": "wjvUvqYFjoXP",
    "outputId": "e65ef25d-a120-4630-e1e0-98ec9bc27e42"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Matches\n",
      "[[0 1]\n",
      " [1 2]]\n",
      "Unmatched Detections\n",
      "[[50, 400, 100, 550]]\n",
      "Unmatched Trackers\n",
      "[[577, 138, 709, 244]]\n"
     ]
    }
   ],
   "source": [
    "for h in hungarian:\n",
    "    \n",
    "    if(iou_matrix[h[0], h[1]] < 0.3):\n",
    "        \n",
    "        unmatched_trackers.append(old[h[0]])\n",
    "        unmatched_detections.append(new[h[1]])\n",
    "        \n",
    "    else:\n",
    "        \n",
    "        matches.append(h.reshape(1, 2))\n",
    "    \n",
    "if(len(matches) == 0):\n",
    "\n",
    "    matches = np.empty((0, 2), dtype=int)\n",
    "    \n",
    "else:\n",
    "    \n",
    "    matches = np.concatenate(matches, axis=0)\n",
    "\n",
    "print(\"Matches\")\n",
    "print(matches)\n",
    "print(\"Unmatched Detections\")\n",
    "print(unmatched_detections)\n",
    "print(\"Unmatched Trackers\")\n",
    "print(unmatched_trackers)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "nmOt7EiqkXCg"
   },
   "outputs": [],
   "source": [
    "for t, trk in enumerate(old):\n",
    "    \n",
    "    if(t not in hungarian[:,0]):\n",
    "\n",
    "        unmatched_trackers.append(t)\n",
    "\n",
    "for d, det in enumerate(new):\n",
    "\n",
    "    if(d not in hungarian[:,1]):\n",
    "\n",
    "        unmatched_detections.append(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 119
    },
    "colab_type": "code",
    "executionInfo": {
     "elapsed": 696,
     "status": "ok",
     "timestamp": 1582134601851,
     "user": {
      "displayName": "Jeremy Cohen",
      "photoUrl": "https://lh3.googleusercontent.com/a-/AAuE7mCv0k4RfFpV9oL2DeIvSvWyPOGBJwNG392F1TiFwg=s64",
      "userId": "01957346698928395081"
     },
     "user_tz": -60
    },
    "id": "iF9OwM975ck-",
    "outputId": "8f9a3858-bbc0-4571-ebb4-deb121a40362"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Matched Detections\n",
      "[([99, 120, 132, 333], [100, 120, 130, 330]), ([302, 352, 406, 400], [300, 350, 400, 400])]\n",
      "Unmatched Detections\n",
      "[[ 50 400 100 550]]\n",
      "Unmatched Trackers\n",
      "[[577 138 709 244]]\n"
     ]
    }
   ],
   "source": [
    "# Now display the matched bounding boxes.\n",
    "\n",
    "display_match = []\n",
    "\n",
    "for matching in matches:\n",
    "\n",
    "    display_match.append((new[matching[1]], old[matching[0]]))\n",
    "\n",
    "print(\"Matched Detections\")\n",
    "print(display_match)\n",
    "print(\"Unmatched Detections\")\n",
    "print(np.array(unmatched_detections))\n",
    "print(\"Unmatched Trackers\")\n",
    "print(np.array(unmatched_trackers))       "
   ]
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "association_hungarian.ipynb",
   "provenance": []
  },
  "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.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}