April 1996 Programmer's Challenge
Mutant Life
Mail solutions to:
progchallenge@mactech.com
Due Date: 1 May 1996
NOTE EARLIER DUE DATE
This month´s Challenge is to write a small image-processing
application that scans a color image and identifies the boundaries of
possible objects in that image. Applications for such a program might
include image enhancement, special effects, or pattern recognition,
although those applications would use a more sophisticated approach
for detecting edges than we will be implementing for this Challenge.
The prototype for the code you should write is:
typedef enum {
redOnly=1, greenOnly, redAndGreen, blueOnly,
redAndBlue, greenAndBlue, redGreenAndBlue
} EdgeType;
void EdgeDetect(
PixMapHandle pMapH, /* find edges in this PixMap */
BitMap *bMap, /* store edges in this BitMap */
unsigned short threshold, /* color separations >= dist create an edge */
EdgeType eType /* which color components to look at */
);
Each pixel in the PixMap should be compared to the eight
(or fewer) adjacent pixels differing in position by up to one row or
column. If the pixel color is sufficiently different (as defined
below) from any of the adjacent pixels, then the bit in the
BitMap corresponding to that pixel should be set to 1.
Otherwise, the BitMap bit should be set to 0. Obviously,
pixels located in the first and last row and column will have fewer
than eight adjacent pixels.
Whether two pixels differ by enough to constitute an edge is
determined by comparing their rgb values. The distance between two
pixels is the root-mean-square difference between the color
components of their rgb values, considering only those components
specified in the input EdgeType. For example, if the
EdgeType is greenOnly, then the distance between
two pixels is the absolute value of the difference in the green
components of their colors. If the EdgeType is
redGreenAndBlue, then the distance is the square root of the
sum of the squares of the differences of the red components, the
green components, and the blue components.
As a specific example, suppose we have two pixels with (red,
green, blue) values of (0x1000, 0x2000, 0x4000) and (0x2000, 0x5000,
0xB000). The distance between these two pixels is:
redOnly: 0x1000
redAndGreen: 0x3298=sqrt(0x01000000+0x09000000)
redGreenAndBlue: 0x7AE5=sqrt(0x01000000+0x09000000+0x31000000)
Two pixels define an edge if their distance is greater than or
equal to the threshold parameter. The threshold
parameter is deliberately declared to be an unsigned short, even
though pixels can differ by a greater amount. Since the definition of
distance is symmetric, the bits corresponding to both edge pixels
would be set in the BitMap.
The BitMap will be allocated and initialized for you by
the calling routine. The storage pointed to by the BitMap
baseAddr will also be allocated and initialized to zero. The bounds
rectangles will be the same for the BitMap and the
PixMap. Your code needs to deal with pixelSize
values of 8, 16, or 32, with each case being equally weighted in the
scoring. For PixMaps with indexed pixels, you will obviously
need to look at the color table to find the rgb value corresponding
to a given index. In the 16-bit case, you should follow the rules for
converting a 5-bit color component into an 8-bit RGBColor
component value (i.e., replicating the 3 most significant bits and
appending them to constitute the least significant bits of the 8-bit
component).
This will be a native PowerPC Challenge, scored using the latest
Metrowerks C compiler. (No C++ or Pascal this month.)
Entries Due Ten Days Earlier
Although two issues may seem like a long time to wait for the
results of the Challenge, it has always been a challenge (no pun
intended) to complete the scoring of results in time for publication
two issues later. We have been searching for a way to allow a little
more time for evaluating the entries and writing the column without
introducing any additional delay between publication of the problem
and publication of the solution. The Challenge mailing list has
allowed us to deliver the Challenge to readers on a predictable
schedule wherever they live, regardless of variations in mailing
dates. We are going to use the mailing list to advance the due date
for Challenge solutions, without reducing the amount of time
available for solving the Challenge. Starting with this month�s
contest, Challenge entries will be due earlier, on the 1st of the
month printed on the front cover. We will mail the problem to the
mailing list on the 12th of the preceding month, also about ten days
earlier than before.
If you are not already a member of the Challenge mailing list, you
can join the ~300 subscribers from 25 countries already on the list
by sending email to macjordomo@listmail.xplain.com with the line �sub
challenge-A YourName�in the body.
Back to the Programmer's Challenge Page
Last modified by Bob Boonstra on 4/13/96.
|