Smiley

Files for this lab are available here.

There is no check-in associated with this lab.

Matched Filters

Consider the sequence of 1's and -1's shown below as x[n].

In this sequence, there is a single occurrence of the pattern -1, -1, 1. It occurs starting at n=1 and ending at n=3. Although it is easy to find the location of this pattern in this short example, it can be significantly more difficult to find such a pattern in larger sequences.

One strategy to automatically locate particular patterns of this type is matched filtering. This strategy involves convolving with a carefully chosen kernel h[n] such that y[n] = (x*h)[n] has its maximal value at locations that match the chosen pattern.

Part a1. Determine a matched filter h[n] that will find occurrences of the sequence -1, -1, 1. Design h[n] such that (x*h)[n] has maxima at points that are centered on the desired pattern (in the example above, there should be a maximum at n=2).

Make a plot of h[n] as a function of n.

Hint: you may wish to think about the "flip-and-shift" method for computing the result of convolution.

Part a2. What will be the value of (x*h)[n] for locations n that match the pattern of interest exactly?

Part a3. Describe a general procedure for constructing a matched filter h so that convolving the input with h gives a signal whose maximum value occurs at the location of the target in the original sequence.

Matched Filters in Two Dimensions

Our goal is to develop a similar approach to find patterns in 2-dimensional signals using two-dimensional convolution:

which is included as a file named littlesmiley.png in the lab distribution. Our goal is to locate this smiley image in a large (1921x1081) image that contains a random pattern of white pixels (value of 1) and black pixels (value of 0), as well as a single instance of the smiley image.

Implementation

We have provided a test image in a file named test.png. View this file and locate smiley visually. Let r=c=0 represent the top left pixel of the test image and determine the coordinates (r and c) of the center of smiley.

Now write a program to locate smiley in the test image. You can read the littlesmiley and test images as follows: \starttyping littlesmiley = png_read('littlesmiley.png',zero_loc='topleft') test = png_read('test.png',zero_loc='topleft') \stoptyping where the zero_loc argument specifies the pixel in the image that is assigned coordinates (r,c) = (0,0).

You could implement the matched filter idea by using convolution in the space domain, but doing the computations in the Fourier domain is much faster for large images.

Part b.

Implement the matched filter algorithm using DFTs. Verify that your program finds the correct location in the test.png image. Then find the smiley image in findsmiley.png. Include your answer (r,c) as well as the code that generated it in your lab submission.

Smiley Party

Two files, multismiley1.png and multismiley2.png contain images that are similar to the one in findsmiley.png except that there are multiple copies of the smiley image in each.

Part c1. How many copies of the smiley were in multismiley1.png? What were the locations of the centers of the smileys in multismiley1.png?

Part c2. How many copies of the smiley were in multismiley2.png? What were the locations of the centers of the smileys in multismiley2.png?

Check for False Positives

View weirdsmiley.png. How many smileys are in this image?

Now try running your matched filter program on the weirdsmiley image. Did it work as you expected?

One common implementation of the matched filter for this problem will find both the actual smiley and the pure white square in this example. If your filter found the pure white square, determine why this happens. Walk through the convolution by hand for each piece, and fix the problem (without using a second pass to detect false positives).

Part d. Describe in detail your process for locating the smileys in the images. If your program initially identified the purely white square as a smiley, describe how you fixed that problem.

Please upload a single pdf file or a single zip file that contains your answers to all parts of this problem:

Select File No file selected

Loading...