September 1997 Programmer's Challenge
Image Locator
Mail solutions to:
progchallenge@mactech.com
Due Date: 11:59pm EDT, 1 September 1997
Imagine yourself with a collection satellite images and the task
of finding a particular item in those images. Rather than look for a
needle in this image haystack manually, you might call on your
PowerMac to narrow down the choices for you. We'll enlist the aid of
our Programmer's Challenge participants to help you do that job
quickly. The Challenge this month is to detect the presence of a
target pattern inside a larger background image. Because the
background has been detected by an imperfect sensor, there is noise
present in the background image. Your code will need to detect the
target in the background despite this noise.
The prototype for the code you should write is:
#define topLeft(r); (((Point *)
&(r))[0])
void InitTarget(
BitMap pattern, /* image to be detected
*/
BitMap mask /* bits in
image that we care about */
);
long /* numFound */ ImageDetect(
BitMap backgroundImage, /* find the target
image in backgroundImage */
Point locations[], /* return topLeft of
matching locations here */
long maxLocations, /* max number of locations
to return */
float
noise /* allow
this fraction of mismatched bits */
);
void CleanUp(void); /* deallocate any memory allocated
by InitTarget */
Image location will take place in two steps. First, your
InitTarget routine will be called with the target pattern that you
will be looking for. Next, the ImageDetect routine will be called
multiple times with a different background image and an associated
noise threshold. ImageDetect should locate all occurrences of the
target in the background, allowing for mismatched bits up to the
noise threshold, and return the location of the pattern matches.
Finally, the CleanUp routine will be called to allow you to
deallocate any memory allocated by InitTarget.
InitTarget will be called with two BitMaps that describe the
target pattern to be detected. The pattern BitMap identifies bits
that should be set to 1, and the mask BitMap describes the bits that
you care about (1s and 0s). Any bits not in the mask are not part of
the target image, and the corresponding values in the background
image are to be ignored. InitTarget should process the target image
as desired and allocate memory to remember it.
ImageDetect will then be called multiple times (5-10 on average
for each call to InitTarget). You should locate each occurrence of
the target image in backgroundImage and return the coordinate in the
background of topLeft(pattern.bounds) in the locations array. The
noise parameter describes the fraction of target bits where the
backgroundImage is allowed to differ from the target and still be
considered a match. Up to noise times the number of 1s in the mask,
rounded down, bits may be mismatched. Normally, locations will be
large enough to hold all of the matches found, but you should not
return more than the maxLocations matches for which storage has been
allocated. The pattern matches may be returned in any order. If the
maxLocations limit is exceeded, the choice of which matches to report
is yours. ImageDetect should return the number of matches found.
Other information: The bounds rectangle for the pattern and the
mask will be identical. All bits set in the pattern will also be set
in the mask (but not the converse). The backgroundImage will
typically be the size of a large monitor (e.g., 1024x768, or
1600x1200).
This will be a native PowerPC Challenge, using the latest
CodeWarrior environment. In keeping with tradition, September is
assembly language month here at the Programmer's Challenge. Solutions
may be coded in PowerPC or 68K assembly language, C, C++, or Pascal.
Finally, we should note that the Programmer's Challenge began its
sixth year last month. During that time, the Challenge has changed
development environments, moved from 68K to PowerPC, and expanded its
selection of languages. We appreciate the participation of our
readers, without which the Challenge would not be possible. Happy
belated birthday, Programmer's Challenge.
A number of questions about this Challenge have been answered on
the Programmer's Challenge mailing list. Check
here
for the Q&A archive.
Download
test
code. for this Challenge. NOTE: This test code has been revised
twice to fix bugs, the latest revision being at 5:20pm 8/21/97.
|