Chapel by Example
Image Processing
The Chapel programming language, designed as a modern alternative to Fortran or C for high performance computing by emphasizing parallel processing and array operations, would seem to be a good fit for image processing. In 2015 we set out to learn the language to see if this was true, writing several imaging programs. Our notes grew into a general introduction to the language, with each chapter using a different imaging task to demonstrate Chapel's features. Unfortunately language changes in Version 1.18 (released in April 2018) to memory management and class initialization broke the foreign function interface to C code and the PNG library needed to read and write images, so the programs will only compile and run in earlier versions. You can download the text as a PDF file, and the programs are available as a tarball or a zip archive.
The first program develops this link to C libraries. It reads an image, changes some pixels, and saves the result. To do this we need to know about Chapel's types, variables, procedures including input/output arguments, structural types (classes and records), and program modules.
The next program converts an image into a new color space. This is a straightforward calculation and introduces the rest of the basic language: statements, expressions, enumerations, tuples, and arrays and domains.
Original image in RGB color space (left) and B* component of CIE LA*B* space (right).
Array operations are a key part of Chapel. They are backed by domains, which specify the indices behind the arrays. Chapel provides several operations for modifying domains, taking subsets or intersections and preventing invalid references. The third program implements a convolution to explore these options, specifically, a Gabor filter, which has a steerable, directional kernel that can highlight edges at different angles.
Asymmetric Gabor filter kernel at 30 degrees (left). 0 degree filter (middle) and 45 degree (right) applied to an image.
In the next example we get to parallel processing. Chapel has two ways of working in parallel. The first splits data into smaller independent pieces, looping over a domain for example. We modify the color conversion routine to do this, and also to determine the smallest and largest color coordinate of the transformed image. The second method divides work at the task level, running functions independently. Our example here is a bank of Gabor filters at angles between 0 and 180 degrees.
We continue exploring parallel processing with a program that uses k-means clustering to find similar colors in an image. This introduces us to Chapel's standard libraries. We also write a version using atomic variables to avoid thread conflicts.
k-means Clusters from Macbeth chart. Size of dot indicates number of pixels in cluster.
Much of Chapel's expressiveness comes from its use of its type system, and that's the focus of the next program. We write a custom loop iterator that proceeds in a circle of a given radius around a point, and use it to implement a FAST corner detector that looks for light-dark transitions along the circumference. We then study generic types and build a custom list that can store potential corners with a figure-of-merit that we can sort with the standard library and use to pick the best candidates.
FAST corners marked by crosses.
The final example doesn't need any new Chapel features, but uses most of what has been presented in the previous chapters. The program is a RANSAC matching of points between two images that may be shifted, rotated, or scaled. It implements a generic kd tree storing corners so they can be found quickly by position, and then makes many attempts in parallel to find the best alignment. It uses the FAST corner detector, color conversion to extract a greyscale image, and the C library to create and save an image showing the final mapping.
RANSAC mapping of features to a rotated, scaled, and shifted version of original.