{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# CSE 152 : Introduction to Computer Vision, Spring 2018 – Assignment 4\n", "### Instructor: Ben Ochoa\n", "### Assignment Published On: Wednesday, May 9, 2018\n", "### Due On: Wednesday, May 23, 2018, 11:59 PM" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Instructions\n", "* Review the academic integrity and collaboration policies on the course website.\n", "* This assignment must be completed individually.\n", "* This assignment contains both math and programming problems.\n", "* All solutions must be written in this notebook\n", "* For the Math problems you may use Markdown/LATEX or you can work it out on paper and upload the scanned copy after merging with the .ipynb PDF. Remember to show work and describe your solution.\n", "* Programming aspects of this assignment must be completed using Python in this notebook.\n", "* If you want to modify the skeleton code, you can do so. This has been provided just to provide you with a framework for the solution.\n", "* You may use python packages for basic linear algebra (you can use numpy or scipy for basic operations), but you may not use packages that directly solve the problem.\n", "* If you are unsure about using a specific package or function, then ask the instructor and teaching assistants for clarification.\n", "* You must submit this notebook exported as a pdf. You must also submit this notebook as .ipynb file.\n", "* You must submit both files (.pdf and .ipynb) on Gradescope. You must mark each problem on Gradescope in the pdf.\n", "* It is highly recommended that you begin working on this assignment early." ] }, { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "## Problem 1 (Programing): Corner detection (20 points)\n", "In this section, we will implement a detector that can find corner features in our images. To detect corners, we rely on the matrix N defined as:\n", "\n", "$$N=\\left[ \\begin{array}{cc}\n", "\\sum\\limits_w I_x^2 & \\sum\\limits_w I_x I_y\\\\\n", "\\sum\\limits_w I_x I_y & \\sum\\limits_w I_y^2\n", "\\end{array} \\right]$$\n", "\n", "where w is the window about the pixel, and $I_x$ and $I_y$ are the gradient images in\n", "the x and y direction, respectively. \n", "\n", "1. (10 points) Implement a procedure that filters an image using a 2D Gaussian kernel and computes the horizontal and vertical gradients Ix and Iy. You cannot use built in routines for smoothing. Your code must create your own Gaussian kernel by sampling a Gaussian function. You can use built-in functions to perform convolution. The width of the kernel should be ±3σ. Include images of the two components of your gradient Ix and Iy on the image warrior1 for σ = 1, σ = 3, and σ = 5.
\n", "\n", "2. (10 points) Implement a procedure to detect corner points in an image. The corner detection algorithm should compute the minor (i.e., smallest) eigenvalue $\\lambda_{min}$ of the matrix C at each pixel location in the image and use that as a measure of its cornerness score. Run non-maximal suppression, such that a pixel location is only selected as a corner if its minor eigenvalue is greater than that of its 8 neighboring pixels. Have your corner detection procedure return the top n non-maximally suppressed corners. Test your algorithm on warrior1 with n = 50 corners. Show corner detection results and report the parameters used.\n", " \n", "Figure 1: x-component of the gradient \n", " \n", "Figure 2: detected corner points on dino image\n", "\n", "Note:\n", "* An example of what your x-component of the gradient should look like is shown in figure 1 and corners should look like as shown in figure 2 above\n", "* You can use scipy.ndimage.filters.convolve or scipy.ndimage.filters.correlate function to perform 2D convolution for computing gradient images" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import numpy as np\n", "from imageio import imread\n", "import matplotlib.pyplot as plt\n", "from scipy.ndimage.filters import convolve\n", "from scipy.ndimage.filters import gaussian_filter\n", "def rgb2gray(rgb):\n", " return np.dot(rgb[...,:3], [0.299, 0.587, 0.114])\n", "\n", "def corner_detect(image, nCorners, smoothSTD, windowsize):\n", " \"\"\"Detect corners on a given image.\n", "\n", " Args:\n", " image: Given a grayscale image on which to detect corners.\n", " nCorners: Total number of corners to be extracted.\n", " smoothSTD: Standard deviation of the Gaussian smoothing kernel.\n", " windowSize: Window size for corner detector and non maximum suppression.\n", "\n", " Returns:\n", " Detected corners (in image coordinate) in a numpy array (n*2).\n", " Ix: X component of the gradient\n", " Iy: Y component of the gradient\n", "\n", " \"\"\"\n", "\n", " \"\"\"\n", " Your code here:\n", " \"\"\"\n", " return corners, Ix, Iy" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# detect corners on warrior and matrix sets\n", "# adjust your corner detection parameters here\n", "nCorners = 50\n", "smoothSTD = 2\n", "windowSize = 11\n", "\n", "# read images and detect corners on images\n", "img_war = imread('p4/warrior/warrior1.png')\n", "crns_war ,Gradient_X, Gradient_Y = corner_detect(rgb2gray(img_war), nCorners, smoothSTD, windowSize)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def show_corners_result(imgs, corners):\n", " fig = plt.figure(figsize=(8, 8))\n", " ax1 = fig.add_subplot(111)\n", " ax1.imshow(imgs, cmap='gray')\n", " ax1.scatter(corners[:, 0], corners[:, 1], s=35, edgecolors='r', facecolors='none')\n", " plt.show()\n", " \n", "def show_gradient_result(Gx,Gy):\n", " fig = plt.figure(figsize=(8,8))\n", " ax2 = fig.add_subplot(121)\n", " ax2.imshow(Gx, cmap='gray')\n", " \n", " ax3 = fig.add_subplot(122)\n", " ax3.imshow(Gy, cmap='gray')\n", " plt.show()\n", "\n", "show_gradient_result(Gradient_X,Gradient_Y)\n", "show_corners_result(img_war, crns_war)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem 2 (Programing): Sparse Stereo Correspondences (20 points)\n", "\n", "For this part of this assignment, we will try to find correspondences between detected corners on stereo image pairs. Extract a 9×9 patch of neighboring pixels around each corner point x in warrior0 and corner point x’ in warrior1. Consider matching x to a corner point x’ in warrior1 if the Normalized Sum of Squared Differences (NSSD) distance between the two patches is less than some threshold $\\tau_{a}$ and the ratio of distance between closest match and next best match for x with other points is less than matching ratio $r_{match}$ (also check the same for x’) . This qualifies if corner pair (x,x’) is unique enough to be matched. Display the images of detected matches, and report the number of correct matches and the number of incorrect matches (by visual inspection). Specify which value of $\\tau_{a}$ and $r_{match}$ you used.\n", "\n", " \n", "Figure 3: Predicted corner point matches on sample images. \n", "\n", "Note:\n", "* An example of what your plots should look like on image pair are shown in Figure 3\n", "* You can discard corner points that are close to the boundary of the image, such that extracting a patch around that corner point would go outside the boundary of the image.\n", "* The NSSD distance between two image patches P1 and P2 is the sum of squared differences between each pixel in the patch after normalizing each patch by their mean and variance.
\n", "NSSD($W_1,W_2$) $=\\sum_{i,j}\\left | \\tilde{W_1} (i,j) - \\tilde{W_2} (i,j) \\right |^2$ where \n", "$\\tilde{W} = \\frac{W - \\overline{W}}{\\sqrt{\\sum_{k,l}(W(k,l) - \\overline{W})^2}}$ is a mean-shifted and normalized version of the window." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def ssd_match(img1, img2, c1, c2, R):\n", " \"\"\"Compute SSD given two windows.\n", "\n", " Args:\n", " img1: Image 1.\n", " img2: Image 2.\n", " c1: Center (in image coordinate) of the window in image 1.\n", " c2: Center (in image coordinate) of the window in image 2.\n", " R: R is the radius of the patch, 2 * R + 1 is the window size\n", "\n", " Returns:\n", " SSD matching score for two input windows/patches.\n", "\n", " \"\"\"\n", "\n", " \"\"\"\n", " Your code here:\n", " \"\"\"\n", "\n", " return matching_score" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [ "def naive_stereo(img1, img2, corners1, corners2, R, SSDth, R_match):\n", " \"\"\"Compute SSD given two windows.\n", "\n", " Args:\n", " img1: Image 1.\n", " img2: Image 2.\n", " corners1: Corners in image 1 (nx2)\n", " corners2: Corners in image 2 (nx2)\n", " R: Radius of the patch to match SSD\n", " SSDth: SSD matching score threshold\n", " R_match: ratio of distance between closest match and next best match\n", "\n", " Returns:\n", " SSD matching result a list of tuple (c1, c2), \n", " c1 is the 1x2 corner location in image 1, \n", " c2 is the 1x2 corner location in image 2. \n", "\n", " \"\"\"\n", "\n", " \"\"\"\n", " Your code here:\n", " \"\"\"\n", "\n", " return matching" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# detect corners on warrior sets\n", "# adjust your corner detection parameters here\n", "nCorners = 20\n", "smoothSTD = 2\n", "windowSize = 11\n", "\n", "# read images and detect corners on images\n", "imgs_war = []\n", "crns_war = []\n", "for i in range(2):\n", " img_war = imread('p4/warrior/warrior' + str(i) + '.png')\n", " imgs_war.append(rgb2gray(img_war))\n", " corner_war,_,_=corner_detect(imgs_war[i], nCorners, smoothSTD, windowSize)\n", " crns_war.append(corner_war)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# match corners\n", "R = 15\n", "SSDth = 100\n", "R_match= 5\n", "print(crns_war.shape)\n", "matching_war = naive_stereo(imgs_war/255, imgs_war/255, crns_war, crns_war, R, SSDth, R_match)\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# plot matching result\n", "def show_matching_result(img1, img2, matching):\n", " fig = plt.figure(figsize=(8, 8))\n", " plt.imshow(np.hstack((img1, img2)), cmap='gray') \n", " i=0\n", " for p1, p2 in matching:\n", " plt.scatter(p1, p1, s=35, edgecolors='r', facecolors='none')\n", " plt.scatter(p2 + img1.shape, p2, s=35, edgecolors='r', facecolors='none')\n", " plt.plot([p1, p2 + img1.shape], [p1, p2])\n", " plt.annotate(i, (p1,p1))\n", " plt.annotate(i, (p2+img1.shape,p2))\n", " i=i+1\n", " plt.show()\n", " \n", "show_matching_result(imgs_war, imgs_war, matching_war)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Problem 3 (Programing): Estimating the Fundamental Matrix (20 points)\n", "\n", "The geometry of two camera views are related by the fundamental matrix F, which maps a point in one image to the corresponding epipolar line in the other image. Given eight or more image point correspondences x ↔ x’ between the two views, a linear estimate of the fundamental matrix can be computed using the direct linear transformation (DLT) algorithm. Typically before estimating the fundamental matrix from an image pair, one must perform outlier rejection (e.g., using RANSAC) in an attempt to remove false matches. However, for this problem we will assume that we have a set of relatively clean correspondences (i.e., no false matches) provided in cor1 and cor2.\n", "\n", "1. (15 points) Implement linear estimation of the fundamental matrix using the DLT algorithm (with data normalization) by writing the function computeF_DLT(x, x') to estimate the fundamental matrix F. Do not forget to enforce the rank-2 constraint on the fundamental matrix. Using your developed computeF_DLT, estimate the fundamental matrix F from the point correspondences provided in cor1 and cor2
\n", "2. (5 points) Additionally, in a separate figure, select any 3 points x in the warrior0 image not contained in cor1 and plot the corresponding epipolar lines l’ = Fx on warrior1. Each epipolar line should pass through the corresponding point in warrior1.\n", " \n", "Figure 4. Example of corresponding epipolar lines\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "x = np.load(\"./p4/warrior/cor1.npy\") #corners from image 1 to learn fundamental matrix\n", "x_dash = np.load(\"./p4/warrior/cor2.npy\") # corresponding corners from image 2 to learn fundamental matrix\n", " \n", "# Part 1:\n", "\n", "def toHomo(x):\n", "# converts points from inhomogeneous to homogeneous coordinates \n", " return np.vstack((x,np.ones((1,x.shape))))\n", "\n", "def fromHomo(x):\n", "# converts points from homogeneous to inhomogeneous coordinates \n", " return x[:-1,:]/x[-1,:]\n", "\n", "def computeF_DLT(x,x_dash): # inputs:\n", " # x: 2D points in image 1\n", " # x_dash: corresponding 2D points in image 2\n", " # output:\n", " # F_DLT: the DLT estimate of the Fundamental matrix\n", " \"\"\"your code here\"\"\"\n", "\n", " return F_DLT/np.sqrt(np.sum(F_DLT**2))\n", "\n", "F_DLT = computeF_DLT(x,x_dash)\n", "print(F_DLT)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# Part 2:\n", "\n", "def epipolar_lines(img1,img2, cor1, cor2, F):\n", " \"\"\"Plot epipolar lines on image given image, corners\n", "\n", " Args:\n", " img1: Image 1.\n", " img2: Image 2.\n", " cor1: Corners in homogeneous image coordinate in image 1 (3xn)\n", " cor2: Corners in homogeneous image coordinate in image 2 (3xn)\n", " F: Fundamental Matrix\n", " output:\n", " point1: points in image1 (i.e. cor1)\n", " lines: corresponding lines in image 2\n", "\n", " \"\"\"\n", " \n", " \"\"\"\n", " Your code here:\n", " \"\"\"\n", " return points1, lines ##return points and lines in the form of a tuple i.e. a tuple of three points and \n", " #a tuple of three lines" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "I1 = imread('p4/warrior/warrior0.png')\n", "I2 = imread('p4/warrior/warrior1.png')\n", "from matplotlib.patches import Circle\n", "from matplotlib.path import Path\n", "import matplotlib.patches as patches\n", "def draw_lines(img1, points1, img2, lines):\n", " # Use for plotting epipolar lines\n", " fig = plt.figure(figsize=(20,10))\n", " ax1, ax2 = fig.add_subplot(1, 2, 1), fig.add_subplot(1, 2, 2)\n", "\n", " # Plot points on img1\n", " ax1.imshow(img1, cmap='gray')\n", " for elem in points1:\n", " circ = Circle((elem, elem),10)\n", " ax1.add_patch(circ)\n", "\n", " # Plot corresponding Epipolar lines on img2\n", " ax2.imshow(img2, cmap='gray')\n", " codes = [Path.MOVETO,Path.LINETO]\n", " for line in lines:\n", " slope = -1*line/line\n", " intercept = -1*line/line\n", " verts = [(0, slope*0+intercept), \n", " (img2.shape, slope*(img2.shape)+intercept)]\n", " path = Path(verts, codes)\n", " ax2.add_patch(patches.PathPatch(path, color='green', lw=2.0))\n", " plt.show()\n", "points1,lines=epipolar_lines(I1,I2, toHomo(crns_war[0:3,:].T), toHomo(crns_war[0:3,:].T), F_DLT) \n", "draw_lines(I1,points1,I2,lines)" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "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.6.3" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false } }, "nbformat": 4, "nbformat_minor": 2 }