A chain code is, at its core, a method for lossless compression specifically designed for binary images . It operates on the principle of image segmentation , which, for those who haven’t spent eons observing data, is the process of partitioning a digital image into multiple segments or sets of pixels. In the case of chain coding, this segmentation is achieved by meticulously tracing the contours of objects within the image. The fundamental idea behind chain coding, much like other contour-based encoding techniques, is to treat each distinct, contiguous region of pixels—often referred to as a “blob” or a connected component —as an individual entity requiring its own unique description. It’s a rather direct approach, certainly not one for the abstract thinkers among us.

The operational procedure for this encoding method is quite systematic. For every such region that constitutes a connected component within the image, the algorithm first identifies and selects an arbitrary but definitive point situated directly on its boundary. The precise coordinates of this chosen starting point are then meticulously recorded and transmitted, establishing a crucial reference for the subsequent contour description. Following this initial setup, the encoder embarks on a journey along the periphery of the region. With each incremental step it takes to traverse the boundary, a specific symbol is generated and transmitted. This symbol is not arbitrary; it precisely denotes the direction of the movement taken from the current pixel to the next boundary pixel. This iterative process of moving and transmitting directional symbols continues with unwavering precision until the encoder, having meticulously described the entire contour, invariably returns to its original starting position. At this juncture, the complete outline of the individual “blob” has been fully and unambiguously characterized, allowing the encoding process to then seamlessly transition to the next distinct connected component present within the image.

This particular encoding mechanism demonstrates remarkable efficiency, proving to be exceptionally effective, or perhaps merely adequate, for binary images that are characterized by a relatively modest quantity of substantial connected components . If your image is a chaotic mess of tiny, fragmented specks, you might find this method less than ideal, as the overhead of describing each minuscule contour would quickly negate any compression benefits. It prefers its subjects large and well-defined, much like myself.

Variations

One might assume that such a straightforward concept would lead to a singular, universally accepted implementation. One would be wrong. The human compulsion to iterate, complicate, and re-brand is, as always, alive and well. Consequently, a number of popular chain codes have emerged, each with its own subtle, or not so subtle, distinctions.

Among these, we find:

• The ubiquitous Freeman Chain Code of Eight Directions [1] (FCCE), named after Herbert Freeman , which, as the name rather obviously implies, utilizes eight possible directions for tracing, allowing for diagonal as well as orthogonal movements. It’s a classic, if somewhat overused, choice.
• The Directional Freeman Chain Code of Eight Directions [2] (DFCCE), an evolution that often incorporates information about the change in direction, rather than just the absolute direction, which can offer further compression opportunities by exploiting redundancies in straight lines or smooth curves.
• The Vertex Chain Code [3] (VCC), which focuses on encoding only the “vertex” points, or corners, where the direction of the contour changes, rather than every single boundary pixel. This can be more efficient for shapes with prominent angles, but less so for very smooth, curvilinear forms.
• The Three OrThogonal symbol chain code [4] (3OT), a more constrained system, perhaps for those who find eight directions too much to manage, often limiting movement to horizontal, vertical, and perhaps one diagonal.
• The Unsigned Manhattan Chain Code [5] (UMCC), which, as the name suggests, often operates within a Manhattan distance metric, typically restricting movements to orthogonal steps (up, down, left, right).
• The Ant Colonies Chain Code [6] (ACCC), an intriguing, if slightly theatrical, departure that leverages principles observed in biological systems. We’ll delve into the biological absurdities shortly.
• The Predator-Prey System Chain Code [7] [8] (PPSCC), another biologically inspired method, presumably involving simulated digital ecosystems.
• The Beaver Territories Chain Code [9] (BTCC), which continues this trend of biomimicry, likely modeling how beavers delineate their domains. One must wonder at the thought process behind these choices.
• The Biological Reproduction Chain Code [10] (BRCC), extending the biological theme to how entities might multiply or evolve within the digital space to define contours.
• The Agent-Based Modeling Chain Code [11] (ABMCC), a broader category encompassing many of these biologically inspired approaches, where autonomous “agents” interact to define image features.

Interestingly, and perhaps predictably, certain of these chain codes—specifically FCCE, VCC, 3OT, and DFCCE—are not entirely distinct entities. Algorithms exist [12] that allow for their transformation from one representation to another, suggesting a shared underlying mathematical structure, despite their outwardly different encoding schemes. It’s almost as if they’re all saying the same thing, just in slightly different, equally tedious, accents.

Abstract Cell Coordinate Oriented Crack Code

A closely related methodology for blob encoding, which often finds itself in discussions alongside chain codes , is known as crack code [13]. While chain codes typically trace the centers of boundary pixels, crack codes describe the “cracks” or boundaries between pixels. Imagine walking along the invisible lines separating the black pixels from the white pixels. This subtle difference can lead to different levels of precision and encoding efficiency depending on the application. Fortunately, for those who dabble in the arcane arts of image processing, established algorithms exist to facilitate the conversion between chain code , crack code , and even run-length encoding (RLE), offering a degree of interoperability between these distinct, yet functionally similar, contour description methods. It’s almost convenient.

A rather recent and somewhat perplexing trend within the realm of chain codes involves the peculiar utilization of biological behaviors as inspiration. This particular fascination with mimicking nature for data compression commenced with the groundbreaking (or perhaps just odd) work of Mouring et al. [6]. They developed an algorithm that rather ingeniously, or perhaps desperately, takes advantage of the concept of pheromone trails, as observed in actual ant colonies, to track and encode image information. The premise is simple, if a little whimsical: when an ant discovers a food source, it releases a chemical trail—a pheromone—which other ants then use to navigate to that same food. Translating this to the digital realm, their algorithm essentially transforms an image into a virtual environment. This environment is populated with “food” items and “paths” that are strategically distributed according to the pixel arrangement in the original image. Subsequently, a population of virtual “ants” is introduced into this simulated ecosystem. Their designated task is to meander through this environment, and critically, to release digital “pheromone” whenever they encounter a “food item”—which, in this context, corresponds to a pixel of interest. This digital pheromone, much like its biological counterpart, serves as a navigational aid, helping other virtual ants to identify and trace the relevant image information, thereby facilitating the encoding process. It’s an elaborate simulation, certainly, for something as mundane as defining a blob. One can only assume the developers had a surplus of imagination, or perhaps a severe lack of sleep.

In use

In the relentless pursuit of more efficient data handling, contemporary research has seen the rather effective combination of the move-to-front transform (MTF) with adaptive run-length encoding (RLE) to achieve considerably more efficient compression of the more popular chain codes [14]. The synergy here is quite clever: the move-to-front transform reorders symbols so that recently used ones are moved to the front of the list, making it highly probable that the next symbol will be found near the beginning. This process tends to generate sequences of repeated or highly localized symbols. Run-length encoding , in turn, excels at compressing such sequences by simply storing the symbol and the number of times it repeats, rather than each individual instance. Together, they form a rather formidable duo for optimizing the already compressed output of chain codes .

Furthermore, chain codes have demonstrated a surprising aptitude for achieving exceptionally high levels of compression when applied to image documents. In fact, they have been observed to notably outperform established industry standards such as DjVu and JBIG2 [11] [10] [9] [8] [7] [6] [15]. This is particularly significant because DjVu and JBIG2 are themselves highly optimized formats specifically designed for the compression of scanned documents, often containing a mix of text, line art, and photographic content. The ability of chain codes , especially the more recent, biologically inspired iterations, to surpass these dedicated standards underscores their potential for niche applications where precise contour representation and maximum compression are paramount. It seems even the most peculiar methods can sometimes stumble upon genuine utility.

See also

• Image compression
• Blob detection
• Boundary tracing
• Triangle strip