Homework 3
Due Monday, Oct. 30, 9 a.m.

Written:

1. Given a homogeneous transform constructed from rotation matrix R
    and translation t, derive the form of the inverse.

2. Compute the rotation matrix that would result from a rotation of 30
    degrees about the axis aligned with the vector [1,1,1] (feel free
    to use Matlab to do this).

3. In the x-y plane, suppose I have a line through the origin oriented
    at 45 degrees, and I have a second line passing through y=2 and
    oriented at 30 degrees (consider the x axis 0 degrees).

    a) Write a homogeneous form for these two lines.
    b) Solve for the point of intersection from the homogeneous form.

4. Suppose you have two parallel lines in 3-space, one passing through
    the point (100,100,1000), the other through (200,200,1100).  The
    lines are parallel to the vector (1,2,1).  The lines are observed
    by a unit focal length camera at the origin.  All coordinates are in camera
    coordinates.

    a) What is the equation for each line in the image? Express it in
    the form where the first two components form a unit vector.

    b) What is their point of intersection in the image?

5. Suppose that I tell you that I have an image of N points containing
    zero or more lines. I also tell you that any line contains at least
    n points. How many samples would you need to draw to be 99.9%
    confident that there are no more remaining lines?

Implementation:

1. Implement k-means clustering on color and apply it to peppers.png.
    Do not use the the built-in Matlab function kmeans.

    Call the function

    segmentedImage = KMeans
(featureImageIn,numberofClusters,clusterCentersIn)

    where:

    segmentedImage is a gray scale image that codes each located
    cluster with a different gray value

    numberofClusters is the number of clusters to find in the image

    clusterCentersIn is an optional parameter that specifies the
    starting centers of the clusters. If this is the empty list [],
    random initialization is used.

    featureImageIn is an image where each pixel can be thought of as a
    feature vector

    Hint: When random initialization is used, it is a good idea to run
    k-means several times with different random initializations and
    keep the best (in terms of distance fit) solution.

    Hint: For debugging, a good idea is to make an artificial image
    that is easily segmented, and to pass good cluster centers to the
    function to start from.

    Write a script Problem1.m that does the following:

    1) Loads peppers.png and reduces the size of the image by a factor
       of four (use newim = imresize(peppers,1/4) for this).

    2) Applies k-means clustering with k=8 and random initialization to
       the raw RGB image and displays a gray scale image of the
       results.

    3) Create two new images that encode the x and y coordinates of
       each pixel in the image.

    4) Add these to the rgb values so that each feature vector is both
       color and location.

    5) Repeats k-mean clustering to this image and displays the results.


CS461 Only

2. Implement a line-finder using Ransac. Do this as follows:

    a) Implement a Ransac line-finder that finds all lines of a minimum
    length (in pixels) in an image with high certainty (see question
    #3). Call this function:

    lines = RansacLine
(edgeImageIn,minLength,fitDistance,desiredCertainty)

    where

    lines is an n by 3 matrix parameterizing lines in the plane
    edgeImageIn is a binary edge image
    minLength is the shortest length (in pixels) of a line that is
    expected
    fitDistance is the maximum distance a pixel may lie from a line
    desiredCertainty is the probability that no more lines remain
    before termination

    Create a script called Problem2.m that:

    1) Applies the built-in matlab Canny edge detector to the image
       circuit.tif (use edge('canny') for this).  Show the resulting
       image.

    2) Uses the matlab function "find" to get the coordinates of all of
       the pixel locations corresponding to an edge.

    3) Calls RansacLine on the resulting image with lines of length 150 pixels
       and certainty 99% (0.99). Print the equations of the lines found
       and the count of the number of lines.

       Extra Credit (5pt): Overlay the line segments found in the image
       and label them in the order found (i.e. 1, 2, 3 ...).

       Hint: When you draw point for Ransac, impose a minimum distance
       constraint so that the points must be a minimum distance
       (e.g. 30 pixels) apart.  This will improve your line fitting.