Home / Problem Set 12 / Finding Smiley

Finding Smiley

The questions below are due on Monday May 17, 2021; 10:00:00 PM.
You are not logged in.

If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.csail.mit.edu) to authenticate, and then you will be redirected back to this page.


A skeleton for your code is provided here.

1) Preliminaries

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

In this x[n], there is a single occurrence of the pattern -1, -1, 1. It occurs starting at n=1 and ending at n=3. In this case, it is relatively easy for us to find the location of this pattern by looking at x[n]. But imagine a much longer sequence of 1's and -1's; in that case, it might be difficult to look and find the location of the sequence of interest.

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.

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).

Enter your answer below as a Python list with h[0] at its center, i.e.:

[h[-m], h[-(m-1)], \ldots, h[-1], h[0], h[1], \ldots h[m-1], h[m]]

Values not explicitly represented in the list will be assumed to be 0.

Hint: you may wish to think of the "flip-and-shift" method of computing the output of a convolution.

h[n] =~

What value will (x*h) have at locations that match the pattern of interest exactly?

Check Yourself 1:

If we had wanted to target a different pattern in the input, how could we construct an appropriate filter h such that convolving the input with h gives a signal whose maximum value occurs at the location of the target in the original sequence?

2) Find Smiley

A similar approach can be used to find 2-dimensional signals by generalizing the convolution operator to two dimensions:

y[n, m] = (x*h)[n, m] = \sum_{k=-\infty}^\infty \sum_{l=-\infty}^\infty x[k,l]h[n-k, m-l]

Download the file smiley.png. This is a 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 following smiley face:

(the contents of this file are also available in the lab distribution as little_smiley.png)

Come up with a plan for using a matched filter to find the smiley face within the image. What will your filter look like? How will you implement it in code?

2.1) Implementation

Now implement your strategy and use it to find the location of the center of the smiley face in smiley.png. Enter that location in the box below, as a tuple (row, column), where row is in the range [-height/2, height/2], and column is in the range [-width/2, width/2]:

Location of smiley's center:

3) Smiley Party

Now download the following files:

Each of these is similar to the file above, except that it contains multiple copies of the smiley face. Use your filter from above to answer the following questions about these images:

How many copies of the smiley were in multismiley1.png?

What were the locations of the centers of the smileys in multismiley1.png? Enter your answer as a list of (row, column) tuples, where row is in the range [-height/2, height/2], and column is in the range [-width/2, width/2].

How many copies of the smiley were in multismiley2.png?

What were the locations of the centers corners of the smileys in multismiley2.png? Enter your answer as a list of (row, column) tuples, where row is in the range [-height/2, height/2], and column is in the range [-width/2, width/2].

3.1) A Problem?

Also download weirdsmiley.png, and look at it. What should your matched filter find as the location(s) of smiley(s) in that image?

Now try running your filter on it. One common implementation of the matched filter for this problem will find both the actual smiley and the pure white square in this example.

Check Yourself 2:

If your filter found the pure white square, why would this happen? Walk through the convolution by hand for each piece.

If your filter had this problem, fix it. Importantly, you should try to fix this in such a way that your filter still involves only running a single convolution, and not using a second pass after the fact to verify that peaks in the filter's output are actually smileys.

Describe in detail your process for locating the smileys in the images. You are welcome to include relevant pieces of code.

If necessary, how did you fix the problem with the pure white square being noticed as a smiley?

Formatting Help