# Finding Smiley

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.

## Code

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.

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

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] =~

**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:

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]:

## 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:

`multismiley1.png`

?

`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].

`multismiley2.png`

?

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

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

Formatting Help