Programming with C++ Concepts
The new concepts mechanism slated for inclusion in the
next revision of C++, C++0x, allows the specification of
“concepts”, as used in the specification of the Standard
Template Library, directly in code.
The concepts mechanism allows for retroactive,
lightweight, low-cost, non-intrusive adaptation of types through
the use of the concept_map feature; a
concept_map specifies how and in what way a type
satisfies the modeling relationship to a concept.
A concept_map can also be used to adapt, say, concept
A to another concept B. This allows
types that model the concept A to be used anywhere
the concept B is required. In particular, we provide
an adaptation between the concepts of Adobe's (Boosts) Generic
Image Library (GIL) and the Boost Graph Library (BGL). This
adaptation allows images that satisfy the concepts of the GIL to
be used in any algorithm that requires concepts that satisfy the
BGL. More information about the adaptation is available in the
paper “Programming with C++ Concepts” , currently
under revision and in progress for submission for publication.
Installing Concept GCC r681 Alpha 7 prerelease
Please refer to the ConceptGCC
website for instructions on how to install the compiler. It is
important that the proper version of the compiler is checked out
from the SVN repository: all the code in this document was
compiled with ConceptGCC Alpha 7 prerelease, revision number 681.
Installing libpng
This code depends on libpng. Please refer to your distro-management software for installation instructions.
Path
The Makefile for this project assumes that ConceptGCC Alpha 7
prerelease r681 is in your PATH under the name
“conceptg++”; it assumes that libpng is in your
LIBRARY_PATH.
Running the code
There should be (at least) the three executables:
ff_compare.exec (flood-fill),
sega_compare.exec (segmentation), and
bbh_compare.exec (backbone-heal). These are entirely
self-contained executables. Run them as indicated below:
Floodfill
The executable ff_compare.exec requires three input
arguments. The first argument is the number of repetitions, the
second argument is the step-size of the images, and the third
argument is the number of steps to take. The second and third
arguments are used to generate the images, where the images are
step-size×[1..number-of-steps] in size. An example is given:
./ff_compare.exec 10 20 50
Generates 50 images from size 20×20 to 1000×1000, and
runs both the GIL-directly-written and BGL-adapted code 10 times,
each.
Segmentation
The executable sega_compare.exec requires four input
arguments. The first three are identical to the three input
arguments for floodfill. The fourth arguments specifies the
“similarity” factor. Similarity is measured in
percentile and represents how close the intensity value of two
pixels must be for the pixels to be considered
‘similar’, i.e., to be put into the same
partition. Since the procedurally generated images use
character-values for the red-channel of the pixel (in a
four-channel pixel), this number must be low, i.e., around 0.001
to create a reasonable partition of the image. An example is given:
./sega_compare 10 20 50 0.001
Generates 50 images from size 20×20 to 1000×1000, and
runs both implementations of the algorithm. For each procedurally
generated image, large valeus for the fourth parameter will result
in a single, global segment for the partition. For small values
(below the threshold of about 0.003), there should be
~side_len*2 segments of the partition. (This number
depends upon round-off error in the set of pixels which are marked
in the procedurally generated image.)
Backbone-Healing
The executable bbh_compare.exec performs
“backbone-healing”. However, in this context, the
healing operation simply finds the lowest-energy path through a
topographic map. That is, the code procedurally generates a hill
(low-point is the upper-left hand corner and the peak is at the
lower-right hand corner). A deep ravine is cut through the
‘hill’ diagonally from the upper-left to the
lower-right. The two “end-points” are in the top
1/5th of the image on the far left hand side and just
below the ravine at near the lower-right hand side. The path (for
a large enough image) should go straight to the right, follow the
ravine, and go straight down. An example of generating and running
this follows:
./bbh_compare.exec 10 5 8
The parameters are the same as the Floodfill program; note that
this algorithm is quartic, i.e., O(n4) for the
second argument, with a large coefficient. Images as small as
100×100 can take 1–2 minutes to run.