Introduction

This project explored several different methods of finding the maximum intensity in an image. Finding the maximum intensity is a useful tool in image analysis, but can be time-consuming considering each pixel must be examined. This project attempts to find the maximum intensity by examining 1-15% of the pixels in a given image.

A second portion of the project extends the concept to a higher dimension, attempting to match an arbitrary polgon to the shape of a star based on the image’s properties.

Methods Used

For the first part of the project, three methods were explored: simulated annealing, gradient ascent, and random probes. Two images were tested. A range of zero to fifteen percent of the pixels were examined for each image, for each method. The two following images were the test images. (Horse pictures were used to remind what they look like since I haven’t had time to make it to the farm in WEEKS. Bombay, the horse that threw me, looks like the one on the left, but is 14.2 hands.)

For the second part of the project, many ideas were explored, but unfortunately the results were not quite as useful as I would have liked.

As a primary step, the ring of points was expanded to fall entirely outside of the star shape, and the lengths between each segment were equalized (to a degree). The expansion of the ring used the gradient to guide the motion.

Then, several different ideas were explored:

Gradient descent
Insuring concave/convex patterns by checking if pi+2 was to the right of the line from pi to pi+1
Gradient along a line segment. As a way of checking to see if a given segment crossed the star, a rough approximation of the gradient along each line segment was computed. Unfortunately I could not come up with an adequate penalty following the detection of this condition. I believe this energy function would have been the most useful in the shape matching.

Results

The following graphs represent the results for part one of the project.

The graphs do reveal some interesting results.

· Scale eight performed poorly for both images

· for Test image 1, scale 16 was best

· for Test image 2, scale 4 was best.

Image 1 Image2

For test image 1, scale sixteen probably provided the best results due to the high amount of contrast in the image. Using a larger scale smooths out the high frequencies, allowing for easier gradient ascent.

For test image 2, there is not a greal deal of contrast. Probably just the slight blurring effect of scale four was sufficient to smooth out the high intensity jumps. More blurring removed the detail we were looking for.

In either case, blurring is an essential element to the algorithm.

For part two, a quicktime movie is included to show my attempt at optimization for the star shape. I truly believe the most useful characteristic would have been the gradient along the line. Given more time, perhaps better penalty methods could have been developed.

Movie file