Sep 97 Challenge
Volume Number: 13
Issue Number: 9
Column Tag: Programmer's Challenge
Programmer's Challenge
by Bob Boonstra, Westford, MA
Image Locator
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.
Three Months Ago Winner
The June Challenge was to implement a Turing Machine, a finite state machine
augmented with an infinite amount of external storage. Twenty people submitted
entries, and 17 of those worked correctly. Congratulations to Ernst Munter (Kanata,
Ontario) for submitting the fastest solution and returning to the Challenge winner's
circle.
The key to success in this Challenge was being able to quickly find the rule that applied
to the current machine state and the current input symbol. A variety of techniques
were used to find the applicable rule. Hashing was used by many of the faster entries.
Ernst uses either hashing or a simple lookup table, depending on memory availability.
Others sorted the rules and used a binary search. The slower solutions typically used a
brute force approach of simply searching linearly through the rule set.
I used two types of test cases to stress the solutions. The first case involved a Turing
Machine of approximately 2300 rules that sorted an input tape with an alphabet of 30
symbols and tape lengths of about 100 symbols. This case required over 113,000
Turing Machine state changes. The second test case was a Universal Turing Machine. A
UTM is an interesting creature. Its input tape has two parts, an encoded version of the
rules (program) for another Turing Machine, which it is to execute, and the input
tape for that emulated program. The tape also contains an area where the Universal TM
maintains the state for the program being emulated. The UTM operates by looking up
the rule (or program instruction) that applies given the current state of the machine
being emulated, remembering that instruction while it moves to the current input for
the emulated machine, and then executing that instruction. The Universal Turing
Machine I used operated on a binary alphabet and consisted of 184 rules, operating on
an input tape that described a simple unary addition machine. This test case required
just under 240,000 state changes to execute.
The table below lists for each entry the execution times in milliseconds for the sort
test case and the Universal Turing Machine case, total execution time, code and data
sizes, and the programming language used. The number in parentheses after the
entrant's name is the total number of Challenge points earned in all Challenges to date
prior to this one.
Ernst Munter (246) 28.1 29.3 57.6 920 8 C++
Russ Webb 30.9 33.0 64.2 1696 140 C
Devon Carew 33.4 35.6 79.5 976 28 C
Gary Beith (24) 39.6 39.9 86.9 592 32 C
Mason Thomas (4) 47.9 40.5 89.1 740 8 C
Kevin Cutts (57) 42.4 43.9 89.7 620 32 C++
Simon Holmes à Court 44.1 42.3 90.0 744 32 C++
Juerg Wullschleger 48.5 50.4 99.7 476 8 C
Daniel Harding 96.0 63.0 159.7 2612 406 C++
Zach Thompson 93.2 64.8 161.3 1076 48 C++
Gregory Cooper (54) 107.8 84.6 192.7 668 40 C
Graham Herrick 137.0 107.2 244.8 820 16 C
Andy Scheck (17) 3239.0 158.3 3397.0 212 8 C++
Charles Higgins (20) 3238.0 167.8 3406.0 276 8 C
David Whitney 4174.0 272.3 4449.0 19800 2745
Bjorn Davidsson (6) 6565.0 165.6 6731.0 224 8 C++
Terry Noyes 6737.0 198.3 6936.0 200 8 C
R.B. ˙2736 99 C
S.A. ˙840 448 C
W.R. ˙1148 8 C++
Top 20 Contestants
Here are the Top Contestants for the Programmer's Challenge. The numbers below
include points awarded over the 24 most recent contests, including points earned by
this month's entrants.
1. Munter, Ernst 196
2. Gregg, Xan 83