CS6640 – Final Projects & ReportAssigned Nov. 17, 2010Due Mon Dec. 13 (Just before midnight)Instructor: Guido GerigTA: Miaomiao ZhangProjectsThe goal of the final project is not only to implement a basic algorithm as in the previousprojects but to build extensions based on materials published in papers, to perform tests andvalidation and provide an indepth discussion of your own implementation, your solution strategy,and your results. Each project requires reading paper(s), come up with your own solution, andbeing creative with experiments to demonstrate strengths of the method but also remainingshortcomings and limitations.You also need to write a report that summarizes your solution, tests, and provides a criticaldiscussion of results.You can choose among 3 different projects:1. Hough Transform2. Image Mosaicing3. Active Contours and SnakesEach question includes an “extra task”, where you can spend additional development effort torefine the algorithm. The “extra task” will decide about a grading of “good” versus “excellent”.A strong requirement is that you have to work fully on your own as this is your finalproject. Further, you need to implement your own code, it is not allowed to find or copy codefrom elsewhere – this would result in a fail of this final project.1 Hough TransformRequired Readings: Generalizing the Hough Transform . . ., D.H. Ballard 1981Linking Image Space and Accumulator-Space, G. Gerig, ICCV’87Notes to parameter space reduction via projection (from Gerig 1986)1.1 Detection and localization of straight linesFigure 1: Example of airport scene containing straight lines and of x-ray image of surface-mountpackaging (this is a quality control problem where chip manufacturers are trying to determinehow well the contacts align for each mounted component). The right image represents circularstructures of varying radii.1. From Project 4: Apply edge or line filtering followed by nonmaximum suppression andthresholding to extract the set of strong edge pixels.2. From Project 5: Implement the HT to detect straight lines (course notes, papers anddiscussions). Put the center into the middle of the image to allow for a more uniformparametrization.3. After incrementing the accumulator space, implement a strategy to reliably find peaks. It isrecommended to first slightly smooth the accumulator and then apply the “decrementationstrategy” as described in the Gerig-ICCV87 paper and course notes.4. The remaining peaks, after thresholding for a minimum number of votes (equals length ofline) form the set of major lines. These lines can be overlayed on the original image.5. The Gerig-ICCV87 paper outlines a strategy to additionally characterize the location andposition of a line by linking the set of image points to each remaining maximum in theaccumulator space. Implement such a strategy to detect the spatial extensions of linepieces, i.e. to calculate the set of contiguous straight line pieces that match the imagestructures.6. Do all the steps with an accumulator built by not only using point location information(x,y) but additionally the information of the normal to the edge (gradient direction).Compare solutation with and without the use of edge orientation.1.2 Detection of circular structures1. Design an HT algorithm to detect circular contours of a fixed radius. Apply it to the X-raymanufacturing image by estimating the sought radius.2. Similarly to line detection, you need to find a strategy to efficiently detect the “best”set of maxima. Again here, you might use the decrementation strategy as described inGerig-ICCV87 to minimize false maxima.Extra Task: GHT*Hint: When detecting shapes at different scales and orientation, you might need a higher di-mensional accumulator (e.g. 4-dim for (x,y,scale,rotation). In Gerig-ICCV87, there is a strategythat projects the best maxima to the 2-D x-y plane by maximum projection, but keeps infor-mation about the associated scale and rotation as additional attributes in a second buffer. Thisavoids a search for maxima in a high-dimensional accumulator.1. Implement the GHT method (see Ballard paper) to detect arbitrarily shaped 2D con-tours. Be creative to choose a picture with repetitive patterns which can vary in size andorientation but have the same shape.2. Given a specific shape to be detected in images, convert the shape contour into a list ofvectors from a reference center to the boundary, with each vector attributed by the angleof the contour normal.3. Create an R-table.4. Remember that fixed radius circle detection above can be extended to search for circleswith arbitrary radii using the GHT (i.e. in the GHT you make use of the edge gradient).This would include only a scale but not a rotation parameter. Your GHT method couldbe tested with circles first and then with shapes that vary in scale and rotations.5. Detect shapes with different rotations and scale using the R-table method of Ballard.2 MosaicingMosaicing is used to generate large pictures from sets of images taken in different spatial direc-tions. The basic algorithm for two images has been discussed as part of the course lectures ongeometric transformations.Required Readings: Course notes Geometric TransformationsMaterials: Slides CSCE 641 Computer Graphics: Image Mosaicing, Jinxiang ChaiSome hints on intensity-based mosaicing (pdf document)Figure 2: Example of for mosaicing a set of images into a virtual wide angle view (JinxiangChai, TAMU).1. From Project 3: Needs method for applying a transformation to an image with bilinearinterpolation.2. Take a set of pictures from the same viewpoint by pointing your camera in differentdirections, but ensure that there is sufficient overlap between consecutive images.3. As discussed in the course (see slides), a minimal number of 4 points define the 8 unknownto calculate the transformation between pairs of images.4. Given a series of images, remember that you need to cascade the transformations (e.g.given 5 images with the middle the reference, the neighboring image can be transformeddirectly, whereas the outermost images have to go through a transformation relative to itsneighbors and then additionally through the neighbor’s transformation).5. Experiment with different numbers of control points etc., and report your results, withpictures.2.1 Questions (to be answered in your report):• How many control points does it take to get a “good” transformation between images?• How does the algorithm