CSC 320 Visual Computing

0. 
   

1. In this assignment you will implement and experiment with a document scanner tool that can let
   you unwarp images based on keypoints. The functionality is similar to that of Microsoft’s Office
   Lens or Adobe Scan. This tool is based on homographies, which is a matrix transform that relates
   two planar surfaces in space as discussed in Lectures 1 and 2. Your specific task is to complete the
   technique’s implementation in the starter code. The code has an optional app that you can use to
   test your algorithm and play around with the document scanner interactively.
   
   

   Goals: The goals of this assignment are to (1) get you familiar with working with images, Python,

   and NumPy; (2) learn how to implement basic geometrical operations like transformations and map

   ping; and (3) learn some insights of what kind of difficulties arise when you geometrically manipulate

   images.
   
   

   Bonus: We suggest that you implement the transformations in the most naive way possible using for

   loops; there are ways to implement it much faster by taking advantage of NumPy and vectorization.

   Although there are no explicit bonus marks for efficient code in this assignment, you should discuss

   any improvements you made in your report. Exceptional efforts in this direction may be rewarded

   with a bonus on a case-by-case basis.
   
   

   Important: You should start by getting a high level idea of what the code does by reading this

   document. Then, try to run the reference solution by following the instructions in the section below.

   Once you get the high level idea of what the code does, take a look at app/a1/a1 headless.py (where

   the app is implemented) and viscomp/algos/a1.py (what you need to complete) to understand the

   overall flow of things. Everything you need to implement is in viscomp/algos/a1.py. You do not

   need to make any other changes. What you should not do: you may not rely on OpenCV or any

   external computer vision or image processing library to implement the assignment. You should be

   able to implement everything just purely with NumPy and Python.
   
   

   Testing your implementation: Your implementation will be tested on the teaching labs Linux

   machines, by running app/a1/a1 tests.py. Make sure you can run these tests by following the

   instructions below and check that your output looks fine.
   
   

   Part A

   Homography Algorithm (85 Marks)

   In this section, you will implement the two algorithms:

   1. Homography Matrix: Calculating a homography matrix from 2 quadrilaterals.

   2. Backward Mapping: Looping through every destination pixel and using the homography to

   find the corresponding source pixel.

   Both of these functions and their skeletons can be found in viscomp/algos/a1.py. Your implemen

   tation will wholly reside in this file. You will not need to make modification to anything else in the

   codebase.
   
   

   Part A.1: Homography Matrix: The calculate homography() function (45 marks)

   We can estimate a homography H given sufficiently many point correspondences. Usually, many

   correspondences are used to compute H. However, for this assignment, we will use the minimum

   number of correspondences needed for a unique solution: four, under the condition that the four

   points are distinct, and define a (convex) quadrilateral. You will be implementing the code for

   determining H in calculate homography().
   
   

   Let’s start by writing down the equations for a single point pi in the source image and its correspon

   dence p′ i in the destination image, shown in the Figure 2 below:

   Points pi and p′ i have known coordinates, either provided by the values in the .csv files for the

   reference solution or extracted from the user’s clicks in the interactive app. We can write them as
   
   

   Part A.2: Backward Mapping: The backward mapping() function (40 marks)

   Now that we have our homography matrix H, we can apply it to portion of the source image

   in the convex region outlined by the four source correspondence points.
   
   

   This is the task for backward mapping(), where you will pass in as input

   • transform: your 3x3 homography matrix solved for in calculate homography

   • source image: the Hs x Ws x 4 image that is used as the source to read from.

   • destination image: the Hd x Wd x 4 image that is used as the destination to write to.

   • destination coords: the 2D locations of the 4 corners on the destination.

   and return the backward mapped image. This task will require looping through every destination

   pixel, finding which points are inside the convex polygon, using the homography H to find the

   corresponding source pixel, and writing to that pixel with the destination pixel. Make sure to check

   your matrix dimensions when implementing the multiplication!
   
   

   Attention: You are expected to include very detailed comments in the code you submit, both

   at the beginning of the code segments you are asked to complete, and inline throughout your code.

   This is so the TAs can better understand the thought process behind the code you wrote. Code

   submitted with few or no comments may be flagged and/or not marked at all.