CS 332

Assignment 1

Due: Friday, September 16

The first problem on this assignment reinforces some basics of MATLAB programming and helps you to begin thinking of 2D matrices as representations of images, with the value at each location representing the light intensity at a corresponding position in a 2D image. In Problems 2 and 3, you will examine the intensity changes in a natural image at multiple scales and explore how the early stages of processing in human vision can lead to a visual illusion. Two final MATLAB programming problems explore simple applications, counting the number of cells in an image of a cell culture, and recognizing fingerprints.

M-Files and images for this assignment are contained in the edges, assign1 and assign1images subfolders in the /home/cs332/download directory on the CS file server, which can be downloaded to your MAC or PC using Fetch or WinSCP. In MATLAB, set your Current Folder to the assign1 folder. In class, you will learn how to set the MATLAB search path to include the edges and assign1images folders (also see the Introduction to MATLAB document). Final submission details are given at the end of this handout.

Problem 1 (20 points): Creating an image of rectangular and circular blocks

In MATLAB, it is easy to create an image with rectangular blocks of uniform intensity. The following function adds a rectangular block to an input image and returns the modified image. The horizontal coordinates range from xleft to xright and vertical coordinates range from ytop down to ybottom.

    function newImage = addBlock(image, xleft, xright, ytop, ybottom, intensity)
    newImage = image;
    newImage(ytop:ybottom, xleft:xright) = intensity;

The commands below create an initial blank image (2D matrix of 8-bit numbers), add one gray rectangular block, and display the new image. A diagram of the image with labeled coordinates is shown below the code.

    >> image = uint8(zeros(100, 100));
    >> image = addBlock(image, 20, 80, 30, 60, 120);
    >> imtool(image);


The coordinates shown at the four corners of the image and at the borders of the gray rectangle correspond to the pixel coordinates (X,Y) printed in the bottom left corner of the Image Tool display window. In pixel coordinates, the location of the upper left corner of the gray block is (X,Y) = (20,30). In the matrix indices, the order of the two dimensions is reversed, so the matrix location of this upper left corner is image(30,20) (i.e. row 30, column 20, of the image matrix). Carefully examine the relationship between the input coordinates in the above MATLAB commands, the indices in the addBlock function, and the position and size of the block in the image.

The assign1 folder contains the addBlock function (defined in the addBlock.m code file) and a script file named makeBlocks.m that uses addBlock to create an image of three blocks with different shades of gray.

Write a MATLAB function named addCircle that adds a circular block of uniform intensity to an input image. The function should have five inputs and one output as shown in the following header:

    function newImage = addCircle(image, xcenter, ycenter, radius, intensity)

Assume that the input image is a 2D matrix of uint8 values that already exists. The circular patch of intensity should be centered at pixel location (X,Y) = (xcenter,ycenter) and should have the specified input radius and intensity. Unlike the addBlock function, you will need nested for loops to step through each location in the region of the matrix where the circle is added, to determine whether the location lies inside the circle. Think about how the range of values for the variables in the for statements can be specified in a way that avoids unnecessary computations. You can assume that this function will be called with appropriate input values that lie within the bounds of the matrix.

Store your new function in a file named addCircle.m in the assign1 folder. Be sure to place a semi-colon at the end of each statement that generates a value, to avoid unnecessary printout during execution of the function. The makeBlocks.m script contains two calls to the addCircle function that you can uncomment when your function is complete.

Problem 2 (20 points): Processing a real image

In this problem, you will describe your observations of the zero-crossings obtained from the convolution of a real image with Laplacian-of-Gaussian convolution operators of different size. The yachtScript.m script in the assign1 folder contains the processing steps needed to generate and display an image and the zero-crossings. First open this script in the MATLAB Editor to see the code that will be executed. The yacht image is a 512x480 8-bit gray-level image of a sailing scene that is displayed using imtool. The image is convolved with two Laplacian-of-Gaussian operators with w = 4 and w = 8. Two representations of the zero-crossings of each convolution are computed - the first stores the slopes of the zero-crossings (in the matrices zc4 and zc8) and the second stores only their locations (in the matrices zcMap4 and zcMap8). All of the zero-crossings are preserved in the latter representation. The two zero-crossing maps are displayed superimposed on the original image, using imtool. You can execute this script by typing

    >> yachtScript;

in the Command Window (it will take some time to compute the convolutions). The three images that are displayed may initially be superimposed in the same region of the monitor and can be dragged apart with the mouse.

Examine the behavior of the zero-crossings for the two different operator sizes. How well do they match up with intensity changes that you see in the original image? How accurately do they seem to reflect the positions of the intensity changes? Are there "spurious" zero-crossings that do not seem to correspond to real edges in the original image? Describe specific examples of features in the image that are captured well by the zero-crossings, and places where the zero-crossing contours do not seem to correspond to a real edge in the image. Observe the image and the slopes of the zero-crossings side-by-side (the zc4 and zc8 matrices can be displayed using the displayImage function, with a border of 8 and 16, respectively). Do the slopes seem to be correlated with the contrast of the corresponding intensity changes in the image?

Problem 3 (15 points): The sun illusion

We sometimes perceive contours in the visual image that do not correspond to real changes of intensity or edges in the original image. Such contours are referred to as illusory or subjective contours. Some examples of this phenomenon are shown below:


In the case of the "sun illusion" shown on the far right, we perceive a bright central disk that is not really present in the image. Sometimes we can offer a possible explanation for why these illusory contours arise, on the basis of the nature of the early processing of intensity changes that takes place in the visual system. In this problem, you will examine the zero-crossings that result from the convolution of the sun image with Laplacian-of-Gaussian operators of different size, in search for such an explanation.

The sunScript.m code file in the assign1 folder provides some initial code for analyzing a sun image created with the makeSun function. This code convolves the image with a Laplacian-of-Gaussian operator of size w = 5 and computes the zero-crossings. The image and zero-crossings are both displayed using imtool. At this scale, the zero-crossing contours surround each spoke of the sun wheel. Add code to the sunScript.m code file to generate zero-crossings from convolutions with larger Laplacian-of-Gaussian operators of size w = 10 and w = 20. Observe the zero-crossing contours obtained from all three operator sizes and describe how they change as the operator size is increased. Based on this analysis, can you offer an explanation for the sun illusion?

Problem 4 (20 points): Counting cells

This problem provides some practice with writing a MATLAB script to analyze an image of red blood cells. This image is contained in the file cells.jpg inside the assign1images folder.


Your goal is to compute a rough estimate of the number of cells in the image. Fortunately, the cells are all darker than the background and fairly well separated from one another. If you can determine the approximate number of pixels covered by a typical cell, you can then estimate the number of cells by counting the total number of dark pixels in the image and dividing this quantity by the number of pixels in a single cell.

To begin, open an empty editor window to store your script. Name the script file countCells.m and save it in your assign1 folder. The script should first load the color image cells.jpg, convert it to a gray-level image using the MATLAB rgb2gray function, and display the resulting gray-level image. Use the MATLAB help system to learn how to use rgb2gray, by executing one of the following statements in the Command Window:

    >> help rgb2gray
    >> doc rgb2gray

Your next step is to create a binary image that is a 2D matrix of values 0 and 1, where a 1 is stored at locations where the cells image contains a dark intensity value and a 0 is stored at locations of bright intensities. The following is an example of what your binary image might look like. The 1's are displayed as white and 0's are black:


To implement this step, first recall that a logical expression can be applied to an entire vector or matrix all at once, producing a vector or matrix of logical values. For example, given an image matrix named coins, the expression (coins == 100) returns a matrix of logical values (represented as 0's and 1's), in which a 1 is stored at locations where the value 100 is stored in the coins image. In the Command Window, explore different thresholds between dark and light, to find a good threshold that gives a result similar to the one displayed above. You can also use imtool and its Pixel Region tool to examine the intensity values in the original image. When you find a suitable threshold, add a statement to the countCells script to create a binary image and display this image in a new figure window.

Your final steps are to estimate (1) the number of pixels covered by all the blood cells in the image, (2) the number of pixels in a single, isolated cell, and finally, (3) the number of cells in the image, using the strategy described earlier. Given the binary representation of the cells image, how can you determine the total number of pixels corresponding to cells? To estimate the number of pixels in a single, isolated cell, create a copy of a small region of the binary image that includes a single, isolated cell. You can create a copy of a region of an image as shown in the following example:

    >> patch = image(30:60,40:80);

It may take some trial-and-error to find the indices of a rectangular region that just spans a single cell - if you use imtool to help, remember that the X and Y coordinates listed in the imtool window indicate the column and row of the corresponding matrix location. Display your small matrix to see if you succeeded in capturing a single cell. Determine the number of pixels covered by the single cell using the same strategy that you used for the full image. Add statements to the countCells script to perform these final steps and print your estimate of the number of cells in the original image (you can just omit the semi-colon at the end of the statement that performs this final calculation).

Problem 5 (25 points): Whodunit???

A heinous crime was committed in the Computer Science department this past weekend — someone stole Captain Abstraction's suit while he assumed his alter-ego as a mild-mannered computer science professor! Even more shocking — it appears to have been an inside job! The circumstances of the crime point in the direction of a CS faculty member — Takis, Sohie, Orit or Brian! One piece of evidence was left at the scene — a lone partial fingerprint. The CS332 class has been recruited by the Wellesley campus police to help nail the culprit. Fortunately we have a fingerprint on file for each of our four suspects. Your mission is to complete a MATLAB program to identify the mysterious fingerprint.

The fingerprint images for this problem can be found in the assign1images folder, and some initial code is provided in the fingerprintScript.m code file in the assign1 folder. The fingerprintScript code reads in five images that include fingerprints for the four suspects (240x256 pixel images) and the mystery partial fingerprint (a 51x51 pixel image named finger.jpg). This script also displays each of the five images in separate figure windows. There are additional commands at the end of the script that are initially commented out, which can be executed after you complete the definition of the getMatch function described below.

The goal of the program is to determine which of the four suspect fingerprint images best matches the mystery partial fingerprint image. Of course, the partial fingerprint will only match a small portion of one of the full fingerprint images. To assist in this process, define a function getMatch that has two inputs, a partial fingerprint image and full fingerprint image. This function should return a number that quantifies the best match between the partial fingerprint and the most similar patch of the input full fingerprint. The similarity between two image patches of the same size can be measured, for example, by computing the absolute difference between the values stored in corresponding locations of the two patches, and summing these differences over the patch. Be sure to add comments to your getMatch function describing your code. After completing the definition of getMatch, uncomment the statements in the fingerprintScript.m code file to obtain values for how well the partial fingerprint matches the fingerprints of Takis, Sohie, Orit and Brian. Add code to the script to use these match values to determine the culprit of this horrific crime, and print out a message with the name of the culprit. A simple string can be printed with the disp function, e.g. disp('What a blow to the CS department!').

Submission details: Hand in a hardcopy of your addCircle.m, sunScript.m, countCells.m, and getMatch.m code files and your answers to the questions for Problems 2 and 3. (To conserve paper, you can copy-and-paste the individual code files into one extended M-File that you submit.) Please also submit an electronic copy of your code files by logging into the CS file server, cs.wellesley.edu, connecting to your assign1 folder and executing the following command:

submit cs332 assign1 *.*

A separate handout will be provided on "Submitting your assignment work electronically," with more details. Please ask if you need help with this last step.