ROB501H1_20229_621670879777rob501_fall_2022_midterm_soln

UNIVERSITY OF TORONTO Faculty of Applied Science and Engineering ROB501H1 F – Computer Vision for Robotics Midterm Exam Instructor: Prof. Jonathan Kelly October 31, 2022 Name : Student Number : Time allowed: 1 hour 50 minutes This exam contains 12 pages (including this cover page) and 4 questions. Answer each question in the spaces provided on the exam paper; some spaces span more than one page. You may use the back of the page for scratch work or additional space, provided you indicate clearly whether it is part of your final solution. A double-sided 8.5” × 11” aid sheet is permitted. Good luck! Distribution of Marks Question Points Score Multiple Choice 10 Short Answers 20 Long Answer – Least Squares & RANSAC 25 Long Answer – Panorama Construction 20 Total: 75 1

ROB501H1 F Computer Vision for Robotics October 31, 2022 QUESTION 1: MULTIPLE CHOICE (10 points) Select one answer only for each question. Each question is worth 2 points. (a) The SAE Levels of Driving Automation guidelines define Level 4 as which of the following? ⃝ Full Automation ⃝ Conditional Automation √ High Automation (b) An affine transformation preserves which of the following? ⃝ Angle √ Parallelism ⃝ Length ⃝ Orientation (c) Bayes’ Theorem can be stated as: p ( x | y ) = p ( y | x ) p ( x ) p ( y ) . The term p ( y ) is referred to as which of the following? ⃝ Prior √ Evidence ⃝ Posterior ⃝ Likelihood (d) Orthographic projection is a suitable approximation/model for which of the following real- world lens types only ? ⃝ Fisheye ⃝ Macro √ Telephoto ⃝ Wide-Angle (e) Choose the feature detection algorithm with the lowest computational cost. ⃝ SURF √ BRISK ⃝ SIFT Page 2 of 12

ROB501H1 F Computer Vision for Robotics October 31, 2022 (d) (5 points) What is the aperture problem ? When considering image features, what character- istic(s) should we look for in an effort to avoid this problem? Solution: When viewing only a small portion of an image (through a small aperture), textureless regions and linear edges do not fully constrain the position of the region (i.e., the neighbourhood of a point). Instead, we should look for regions that have strong gradients in two directions in image space. (e) (4 points) What, concisely, is the universal approximation theorem for MLPs? Solution: Feed-forward neural networks are universal approximators. A single hidden layer is enough to approximate (almost) any function to arbitrary accuracy given enough neurons (width). Page 4 of 12

ROB501H1 F Computer Vision for Robotics October 31, 2022 QUESTION 3: LONG ANSWER – LEAST SQUARES & RANSAC (25 points) Fitting an ellipse to a set of image plane points is a common task in robotic vision. In this question, you will walk through the problem of ellipse-fitting from end to end. (a) (4 points) To fit an ellipse, you much first choose a model. You decide to assume that the major and minor axes of the ellipse will always be aligned with the image plane x and y axes. However, the origin of the ellipse might be anywhere on the image plane. Write down your model equation(s). Solution: A possible model equation for an ellipse centred at ( c x , c y ) is a ( x − c x ) 2 + b ( y − c y ) 2 = 1 Expanding, grouping terms, and rearranging, we obtain ax 2 − 2 c x x + c 2 x + by 2 − 2 c y y + c 2 y = 1 , ax 2 + by 2 + dx + ey + f = 0 , which is the equation for a general conic section (almost, the xy term is missing). Alternatively, a model formulation that enforces positive coefficients (and hence the shape) could be a 2 ( x − c x ) 2 + b 2 ( y − c y ) 2 = 1 (b) (3 points) You choose to solve the fitting problem using least squares, given that you have a series of ( x i , y i ) , i = 1 , . . . , m , pairs as measurements, where the x i values are treated as being noise-free. Is this a linear or nonlinear least squares problem and why? Solution: If we choose the (general) conic section formulation, then this is a linear least squares problem because the model function is linear with respect to the parameters. If we choose the formulation where the parameters (coefficients) are squared, then this is a nonlinear least squares problem. Page 5 of 12

ROB501H1 F Computer Vision for Robotics October 31, 2022 (e) (2 points) Given your choice of model, what is the minimum number of ( x i , y i ) pairs required to fit the model and why? Solution: In general, one equation (pair) is required per unknown (to solve the linear problem or for the Jacobian to be full rank in the nonlinear case). The answer depends on the model that has been chosen. (f) (2 points) Given an inlier ratio of w = 50% (yikes!), how many iterations of RANSAC would be required to ensure with z = 87.5% probability that an outlier-free set of points is selected? A closed-form solution is not needed, you may simply write down the required equation, but be sure to fill in all of the values! Solution: Making use of the equation given in the RANSAC paper (and the lecture notes), assuming that four points are required: k = log (1 − z ) log (1 − w n ) = log (1 − 0 . 875) log (1 − 0 . 5 4 ) = − 3 − 0 . 0931 ≈ 33 (g) (5 points) Frustrated by outliers, but bound by limited resources, you decide to tolerate one potential outlier when implementing a modified version of RANSAC. Derive a general expres- sion for the expected number of trials k required to select a set of points with at most one outlier (in terms of w and n ). Simplify the expression as much you can. Solution: This problem has some subtleties. Since the expectation is desired, we first need to determine the probability of the event “ n number of samples were selected, con- taining at most one outlier.” The probability of drawing n samples with at most one outlier is the sum of the probabil- ities of the ways this can happen. We might draw n outlier-free samples consecutively, or draw one outlier, then draw n − 1 outlier-free samples, etc. The overall probability is b = w n + ( n 1 ) (1 − w ) w n − 1 = w n + n (1 − w ) w n − 1 The same expression for the power series that appears in the RANSAC paper can be used again, hence we have E [ k ] = 1 b = 1 w n + n (1 − w ) w n − 1 Page 7 of 12

ROB501H1 F Computer Vision for Robotics October 31, 2022 Extra space to show your work if needed. Page 8 of 12

ROB501H1 F Computer Vision for Robotics October 31, 2022 (c) (4 points) Given more than four point correspondences between images, ( x i , x ′ i ) , you decide to use least squares (again) to fit your model homography H . Considering the error or distance function only, your VP of Marketing suggests that a suitable cost is C = ∑ i d ( x ′ i , Hx i ) where d ( · , · ) is the Euclidean distance between pixel coordinates. What is wrong, potentially, with the VP’s suggestion? Solution: The VP has failed to consider that the ‘distance’ metric being applied is not symmetric. If x i and x ′ i are swapped (and the homography is inverted), the result will be different, potentially quite significantly. (d) (4 points) One of your employees argues that the best way to build panoramas is always to assemble the sub-images starting from the upper left corner of the complete panorama (given a known, final size), working sequentially from left to right. Another employee asserts that this is not the correct approach and that, instead, the maximum number of transformations applied consecutively should always be minimized. Is the second employee right or wrong? Why? Your argument should be numerical, but you do not need to use actual numbers, unless this is helpful. Solution: A simple numerical argument is sufficient. The problem is noise: feature corre- spondences are never exact, so any homography will also have error. To build a panorama, images are typically warped in sequence—each additional warping (application of an H matrix) adds distortion. In turn, applying long chains of transforms tends to yield terrible results. Therefore, the second employee is right, using the least number of consecutive transforms should give better outputs (panorama quality). Page 10 of 12

ROB501H1 F Computer Vision for Robotics October 31, 2022 Extra space to show your work if needed. (e) (5 points) Buyers tend to dislike vignetting in mosaicked images. Provide high-level pseu- docode for a simple method to reduce vignetting. Python-style code is not required—bullets are sufficient, as long as variables are clearly defined. Hint: where is there the least vignetting? Solution: A wide variety of solutions exist. The answer should make use of the fact that pixels closer to the centre of an image have less vignetting and can be used to determine what (nonlinear) correction to apply to image brightness in regions where two or more images overlap. Page 11 of 12