May 96 Challenge
- Jan 96 Challenge
- Feb 96 Challenge
- Mar 96 Challenge
- Apr 96 Challenge
- Jun 96 Challenge
- Jul 96 Challenge
- Aug 96 Challenge
- Sep 96 Challenge
- Oct 96 Challenge
- Nov 96 Challenge
- Dec 96 Challenge
Volume Number: 12
Issue Number: 5
Column Tag: Programmer’s Challenge
Programmer’s Challenge 
By Bob Boonstra, Westford, Massachusetts
Note: Source code files accompanying article are located on MacTech CD-ROM orsource code disks.
Edge Detector
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 */
);
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
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
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.
Two Months Ago Winner
The response to the Words the Reverse Challenge was overwhelming. I don’t know if it
was due to allowing C++ and Pascal entries, or to the relative simplicity of the
problem, but I received a record 45 entries to this Challenge. The Challenge was to
write code that would reverse the order of words in a block of input text while
preserving intervening white space and special characters, and adjusting
capitalization of the reversed words to match that of corresponding input words. It is