5.0-tl-fundamental-matrix.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fundamental Matrix and RANSAC\n",
    "\n",
    "In this exercise, you will learn:\n",
    "- how to estimate the fundamental matrix $F$ that geometrically relates two views of the same scene\n",
    "- how to make your estimation more robust to outliers and noise which is important in practice\n",
    "\n",
    "For some functions we already provide some draft implementation that you just need to complete. This is supposed to help you identifying the next steps. Still, if it does not fit your idea you may ignore it.\n",
    "\n",
    "## 1. Setup\n",
    "\n",
    "Load all libraries and both views that we will work with. In this exercise you are given two views again and matching key points which we extracted in advance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "from PIL import Image\n",
    "from scipy import signal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from matplotlib.patches import ConnectionPatch\n",
    "\n",
    "# use this function to visualize the matches\n",
    "def plot_matches(img1, img2, keypoints1, keypoints2):\n",
    "    fig, axes = plt.subplots(1,2,figsize=(16,7))\n",
    "    \n",
    "    # draw images\n",
    "    axes[0].imshow(img1)\n",
    "    axes[1].imshow(img2)\n",
    "    \n",
    "    # draw matches\n",
    "    for kp1, kp2 in zip(keypoints1, keypoints2):\n",
    "        c = np.random.rand(3)\n",
    "        con = ConnectionPatch(xyA=kp1, coordsA=axes[0].transData,\n",
    "                              xyB=kp2, coordsB=axes[1].transData, color=c)\n",
    "        fig.add_artist(con)\n",
    "        axes[0].plot(*kp1, color=c, marker='x')\n",
    "        axes[1].plot(*kp2, color=c, marker='x')\n",
    "    \n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load images\n",
    "view1 = np.array(Image.open(\"data/exercise3/view1.png\")) / 255\n",
    "view2 = np.array(Image.open(\"data/exercise3/view2.png\")) / 255\n",
    "\n",
    "# Load matching keypoints\n",
    "with np.load(\"data/exercise4/keypoints.npz\") as data:\n",
    "    keypoints1 = data[\"view1\"]\n",
    "    keypoints2 = data[\"view2\"]\n",
    "    \n",
    "plot_matches(view1, view2, keypoints1, keypoints2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1. Fundamental Matrix\n",
    "We begin with computing the fundamental matrix $F$ which defines the epipolar constraints for two views of two uncalibrated cameras. It determines the lines corresponding points can lie on. If we have a total of eight pairs of corresponding points this matrix can be estimated using the 8-point algorithm discussed in the lecture, see slide deck \n",
    "\n",
    "Your task now is to use eight point matches and compute the fundamental matrix $F$ by performing a direct linear transform and then decompose the resulting matrix using SVD. You might want to look at the slides again.\n",
    "\n",
    "Hint: Use `numpy.linalg.svd` for singular value decomposition and do not forget to rescale the point coordinates to obtain stable results (this is termed 'conditioning' on the slides)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_fundamental_svd(kps1, kps2):\n",
    "    \"\"\"\n",
    "    Estimate fundamental matrix using SVD \n",
    "    :param kps1: keypoints extracted from view1 in homogeneous coordinates\n",
    "    :param kps2: keypoints extracted from view2 in homogeneous coordinates\n",
    "    \"\"\"\n",
    "    # condition points\n",
    "    \n",
    "    # collect equations\n",
    "    \n",
    "    # solve for fundamental matrix using SVD\n",
    "\n",
    "    # uncondition F\n",
    "    \n",
    "    # make rank 2\n",
    "        \n",
    "    return F"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compute F from a set of 8 point matches"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check your code by visualizing the epipolar lines of you key points. We provide the function for this below. What do you see?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def visualize_epipolar_lines(img1, img2, keypoints1, keypoints2, F):\n",
    "    \"\"\"\n",
    "    :params img1: view 1\n",
    "    :params img2: view 2\n",
    "    :params keypoints1: the key points from view 1 matching\n",
    "                        with the key points from view 2\n",
    "                        --> they are expected to be in homogenous coordinates\n",
    "    :params keypoints2: the key points from view 2 matching\n",
    "                        with the key points from view 1\n",
    "                        --> they are expected to be in homogenous coordinates\n",
    "    :params F: the fundamental matrix\n",
    "    \"\"\"\n",
    "    fig, axes = plt.subplots(1,2,figsize=(16,7))\n",
    "    \n",
    "    # draw images\n",
    "    axes[0].imshow(img1)\n",
    "    axes[1].imshow(img2)\n",
    "    res = img1.shape[:2]\n",
    "    \n",
    "    for color_index, (kp1, kp2) in enumerate(zip(keypoints1, keypoints2)):\n",
    "        c = np.random.rand(3)\n",
    "        \n",
    "        # plot points\n",
    "        axes[0].plot(kp1[0], kp1[1], color=c, marker='o',markersize=5)\n",
    "        axes[1].plot(kp2[0], kp2[1], color=c, marker='o',markersize=5)\n",
    "        \n",
    "        # compute epi lines\n",
    "        epi_line_2 = kp1[None,...] @ F\n",
    "        epi_line_1 = F @ kp2[None,...].T\n",
    "        \n",
    "        # plot lines\n",
    "        for i, line in enumerate([epi_line_1, epi_line_2]):\n",
    "            line = line.flatten()\n",
    "            fn = lambda x: (line[0]*x + line[2]) / -line[1]\n",
    "            xs = np.arange(res[1])\n",
    "            axes[i].plot(xs, fn(xs), c=c)\n",
    "    \n",
    "    axes[0].set_ylim((res[0],0))\n",
    "    axes[1].set_ylim((res[0],0))\n",
    "    \n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Also, compute the algebraic error, i.e. how well is the epipolar contraint $x_0^TFx_1=0$ met.\n",
    "Furthermore, calculate the geometric error, i.e. are the points far away from the epipolar lines.\n",
    "What do the algebraic and geometric error values show you?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def algebraic_error(keypoints1, keypoints2, F):\n",
    "    errors = []\n",
    "    for kp1, kp2 in zip(keypoints1, keypoints2):\n",
    "        error = np.abs(kp1[None,...] @ F @ kp2[None,...].T)\n",
    "        errors.append(error.item())\n",
    "    return errors\n",
    "\n",
    "def geometric_error(keypoints1, keypoints2, F):\n",
    "    errors = []\n",
    "    for kp1, kp2 in zip(keypoints1, keypoints2):\n",
    "        x1F = kp1[None,...] @ F\n",
    "        Fx2 = F @ kp2[None,...].T\n",
    "        x1Fx2 = x1F @ kp2[None,...].T\n",
    "        \n",
    "        part1 = 1/(x1F.flatten()[0] ** 2 + x1F.flatten()[1] ** 2)\n",
    "        part2 = 1/(Fx2.flatten()[0] ** 2 + Fx2.flatten()[1] ** 2)\n",
    "        \n",
    "        error = np.sqrt(x1Fx2 ** 2 * (part1 + part2))\n",
    "        errors.append(error.item())\n",
    "    return errors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Robust estimation using RANSAC\n",
    "As some of the point matches suffer from noise or are even incorrect. The risk of obtaining an incorrect fundamental matrix by relying just on eight points is high. Hence, we are looking for a more robust version of estimating $F$. To do this, the RANSAC algorithm was introduced in the lecture. Your final task is to complete the implementation for fundamental matrix estimation by using RANSAC. You can compare the errors and epipolar lines of a robustly estimated $F$ with the one from the previous task."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_fundamental_ransac(keypoints1, keypoints2, num_samples=8, threshold=5, iterations=5000, min_inliers=30):\n",
    "    \"\"\"\n",
    "    Optimizes fundamental matrix parameters using RANSAC algorithm\n",
    "    :params keypoints1: the key points from view 1 matching\n",
    "                        with the key points from view 2\n",
    "                        --> they are expected to be in homogenous coordinates\n",
    "    :params keypoints2: the key points from view 2 matching\n",
    "                        with the key points from view 1\n",
    "                        --> they are expected to be in homogenous coordinates\n",
    "    :param num_samples: the number of samples to draw in each iteration\n",
    "    :param threshold: determines the error value at which we decide for inlier or outlier\n",
    "    :iterations: maximum number of iterations\n",
    "    :returns: fundamental matrix and a binary mask indicating the inlier points in keypoints1 and keypoints2\n",
    "    \n",
    "    \"\"\"\n",
    "        \n",
    "    return F, inlier_mask "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "F, inliers = find_fundamental_ransac(...)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now visualize again the epipolar lines and compute the errors. What has changed?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}