Hubbry Logo
Chain codeChain codeMain
Open search
Chain code
Community hub
Chain code
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Chain code
Chain code
Chain code
View on Wikipedia
from Wikipedia

A chain code is a lossless compression based image segmentation method for binary images based upon tracing image contours. The basic principle of chain coding, like other contour codings, is to separately encode each connected component, or "blob", in the image.

For each such region, a point on the boundary is selected and its coordinates are transmitted. The encoder then moves along the boundary of the region and, at each step, transmits a symbol representing the direction of this movement.

This continues until the encoder returns to the starting position, at which point the blob has been completely described, and encoding continues with the next blob in the image.

This encoding method is particularly effective for images consisting of a reasonably small number of large connected components.

Variations

[edit]

Some popular chain codes include:

  • the Freeman Chain Code of Eight Directions[1] (FCCE)
  • Directional Freeman Chain Code of Eight Directions[2] (DFCCE)
  • Vertex Chain Code[3] (VCC)
  • Three OrThogonal symbol chain code[4] (3OT)
  • Unsigned Manhattan Chain Code[5] (UMCC)
  • Ant Colonies Chain Code[6] (ACCC)
  • Predator-Prey System Chain Code[7][8] (PPSCC)
  • Beaver Territories Chain Code[9] (BTCC)
  • Biological Reproduction Chain Code[10] (BRCC)
  • Agent-Based Modeling Chain Code[11] (ABMCC)

In particular, FCCE, VCC, 3OT and DFCCE can be transformed from one to another[12]

Abstract Cell Coordinate Oriented Crack Code

A related blob encoding method is crack code.[13] Algorithms exist to convert between chain code, crack code, and run-length encoding.

A new trend of chain codes involve the utilization of biological behaviors. This started by the work of Mouring et al.[6] who developed an algorithm that takes advantage of the pheromone of ants to track image information. An ant releases a pheromone when they find a piece of food. Other ants use the pheromone to track the food. In their algorithm, an image is transferred into a virtual environment that consists of food and paths according to the distribution of the pixels in the original image. Then, ants are distributed and their job is to move around while releasing pheromone when they encounter food items. This helps other ants identify information, and therefore, encode information.

In use

[edit]

Recently, the combination of move-to-front transform and adaptive run-length encoding accomplished efficient compression of the popular chain codes.[14] Chain codes also can be used to obtain high levels of compression for image documents, outperforming standards such as DjVu and JBIG2.[11][10][9][8][7][6][15]

See also

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Chain code

View on Grokipedia
from Grokipedia
A chain code is a algorithm for representing the contours of objects in binary digital images by encoding the boundary as a sequence of discrete directional steps along connected pixels. Introduced by Herbert Freeman in 1961, it traces the perimeter starting from an arbitrary boundary point and records unit moves in either 4-connectivity (horizontal and vertical directions) or 8-connectivity (including diagonals), using integer codes from 0 to 3 or 0 to 7, respectively. This method provides a compact, symbolic description of shapes that preserves essential topological and geometric information while reducing storage needs compared to coordinate lists—for instance, requiring only 2–3 bits per boundary pixel. The core principle of chain codes relies on raster scanning or boundary-following algorithms to generate the sequence, which inherently supports translation invariance since it depends solely on relative directions rather than absolute positions. To achieve rotation invariance, variants like the differential (first-difference) chain code compute changes in direction rather than absolute orientations, enabling normalized comparisons of rotated s. Freeman's original formulation, detailed in his conference paper, laid the foundation for subsequent enhancements, including techniques co-developed with Feder in 1965 to improve shape matching efficiency. Over decades, chain code schemes have evolved with notable contributions from researchers like in 1973, who simplified encoding to binary turn codes, and Ernesto Bribiesca in 1999, who introduced vertex chain codes (VCC) that use vertex coordinates for enhanced invariance under translation, rotation, and scaling in both 2D and 3D contexts. Further refinements include compressed variants, such as Huffman-coded chain codes proposed in 2005, and histogram-based extensions like chain code histograms (CCH) and coherence vectors (CCCV) developed around 2006, which facilitate statistical shape analysis across diverse grid structures like triangular or hexagonal cells. These advancements address limitations in the original Freeman code, such as sensitivity to starting point and direction, while maintaining computational efficiency. In computer vision and image processing, chain codes find broad applications in shape recognition, where they enable compact feature extraction for pattern matching; medical imaging, such as quantifying cell boundaries or analyzing brain structures; and optical character recognition (OCR), supporting digit and symbol identification through boundary encoding. They also aid in object tracking, industrial manufacturing for defect detection, space exploration imagery, and defense-related surveillance by allowing efficient storage, retrieval, and comparison of contours in large datasets. Recent trends, including noise-robust injections into chain codes as of 2025, underscore their ongoing relevance in robust geometric modeling amid imperfect real-world data.

Fundamentals

Definition

Chain code is a and technique used in image processing to encode the contours of connected components, often referred to as blobs, in binary images. It achieves this by tracing the perimeter of an object by , converting the boundary into a compact sequence of directional moves rather than storing the full coordinates. This method was originally proposed by Herbert Freeman in 1961 as a way to encode arbitrary geometric configurations efficiently. The core principle of chain code involves representing a shape's boundary as a of unit-length steps along specified directions, typically employing either 4-connectivity (horizontal and vertical moves only) or 8-connectivity (including diagonals). In the 8-connectivity system, directions are encoded as integers from 0 to 7, where 0 denotes a move to the right (east), 1 to the upper-right (northeast), 2 upward (north), and so on, progressing counterclockwise in 45-degree increments. This encoding allows for a succinct description of the boundary path, preserving all topological and geometric details without loss of . To generate a chain code, an arbitrary boundary pixel is selected as the starting point, with its coordinates (x, y) explicitly transmitted to enable reconstruction. The tracing proceeds along the contour until it returns to this starting pixel, forming a closed loop that fully delineates the connected component. This approach is particularly suitable for binary images featuring a small number of large connected components, as it minimizes redundancy and storage requirements for prominent object boundaries while being less efficient for scenes with numerous tiny elements.

Boundary Representation

Chain codes represent the boundary of an object in a binary image by encoding the sequence of directional moves along its perimeter, effectively capturing the geometric structure through a compact string of integers corresponding to unit steps in predefined directions. This method, introduced by Herbert Freeman, traces the contour starting from a designated point and follows the boundary in a consistent direction, such as clockwise, to ensure a closed loop representation without gaps or overlaps. The boundary tracing process typically employs algorithms like Moore's neighborhood algorithm, which begins at the leftmost of the topmost row of the object and examines neighboring pixels in a manner to identify and follow the edge pixels. This ensures all boundary points are visited exactly once before returning to the starting point, forming a complete contour description. For connectivity, chain codes support two primary models: 4-connected, which uses four cardinal directions (0 for east/right, 1 for south/down, 2 for west/left, 3 for north/up), restricting moves to horizontal and vertical steps; and 8-connected, which expands to eight directions (0-7, starting from east and proceeding to include diagonals), allowing for more fluid approximations of curved boundaries. The choice of connectivity affects the smoothness and length of the code, with 8-connected often yielding shorter sequences for diagonal-heavy . A representative example in 4-connectivity is a simple square boundary traversed , starting from the top-left corner: the sequence "000111222333" encodes three right moves (0), three down moves (1), three left moves (2), and three up moves (3) for a 4x4 square, precisely outlining the perimeter. In 8-connectivity, the same square would use only cardinal directions but could incorporate diagonals (e.g., 1 for southeast) if the boundary includes slanted edges in more complex shapes. One key advantage of chain codes is their compact storage of contour information, requiring minimal space—often just one byte per direction—while preserving all boundary pixels losslessly, enabling exact reconstruction of the original shape by interpreting the sequence as a series of vector steps from the starting point. For instance, decoding "000111222333" repositions a cursor successively right three times, down three times, left three times, and up three times, yielding the square's exact pixel outline without interpolation errors. However, chain codes have limitations, including sensitivity to the choice of starting point, which can alter the sequence despite representing the same shape, and vulnerability to rotation, as shifting the orientation changes the directional codes; they are also not inherently scale-invariant, requiring additional processing for resized images.

Historical Development

Origins in Image Processing

Chain codes originated in the field of during the early era of , where researchers sought efficient methods to represent and analyze visual from scanned or digitized sources. Herbert Freeman introduced the concept in his seminal 1961 paper, proposing a technique for encoding arbitrary geometric configurations to enable compact storage, transmission, and machine recognition of shapes. This approach addressed the challenges of handling large volumes of on early computers, focusing on boundary descriptions to support tasks. Freeman's prototype, known as the Freeman Chain Code of Eight Directions (FCCE), utilized an 8-connected path that quantized boundary directions into eight discrete orientations spaced at 45-degree increments, allowing for a concise sequence of directional symbols to trace object contours. The method formalized the encoding process by following contours in a counterclockwise manner, preserving essential shape information while reducing data redundancy compared to pixel-by-pixel representations. This innovation built upon prior informal ideas in contour-following algorithms but provided a structured, numerical framework for digital curve representation. During the 1960s and 1970s, chain codes saw early adoption in research on topological properties of digital images and the development of shape descriptors, enabling applications in automated image analysis and recognition systems. Freeman's work laid the groundwork for subsequent variations that extended the basic encoding scheme to handle more complex boundary features.

Key Advancements

In 1965, Freeman and Jerry Feder co-developed correlation techniques for chain codes, improving shape matching efficiency by analyzing directional correlations in boundary sequences. In the 1970s, Seymour Papert simplified encoding to binary turn codes, reducing complexity for basic direction changes. During the 1970s and 1980s, differential chain codes (DCC) emerged as a significant improvement over early Freeman codes, encoding relative direction changes between successive boundary segments to mitigate sensitivity to rotations and translations. This approach, pioneered by researchers at Delft University, reduced storage requirements by exploiting correlations in boundary directions, achieving higher compression efficiency for line drawings compared to absolute direction encodings. Building on Freeman's foundational work from , the Vertex Chain Code (VCC) was developed in 1999 by Ernesto Bribiesca, emphasizing representations based on corner points or vertices rather than every along the boundary, which enhanced compactness and invariance properties. VCC uses a minimal set of symbols to describe vertex connections, allowing for more efficient storage of complex shapes while maintaining topological accuracy. During the and , chain codes saw integrations with complementary encodings such as crack codes, which trace boundaries along pixel cracks, and (RLE), enabling hybrid representations for improved compression in binary images. In 2005, Huffman-coded chain codes were proposed as a compressed variant to further optimize storage. Around 2006, histogram-based extensions like chain code histograms (CCH) and coherence vectors (CCCV) were developed, facilitating statistical shape analysis across diverse grid structures. The 3-Orthogonal Chain Code (3OT), introduced in 2005, further advanced this by using only three orthogonal symbols to represent boundaries, facilitating simpler computations for properties like the and outperforming prior codes in storage efficiency for rasterized shapes. The 2010s introduced biologically inspired variants, drawing from natural systems for more robust boundary tracing. The Ant Colonies Chain Code (ACCC) of 2018 employs swarm optimization principles, simulating trails to achieve resilient contour extraction in noisy environments. Similarly, the Predator-Prey System Chain Code (PPSCC), from 2019, models dynamic interactions akin to ecological predation for adaptive boundary detection, enhancing performance in evolving or irregular shapes. In the 2020s, chain codes have been increasingly integrated into AI-driven pipelines, particularly for post-processing contours extracted via models, as explored in agent-based simulations for bi-level . Works like Dhou's 2019 analysis highlight future applications in hybrid systems combining chain codes with neural networks for precise representation in and . As of 2025, advancements include noise-robust techniques such as direct noise injection into Freeman chain codes to model imperfections in real-world data. Algorithms for interconvertibility among major chain code formats, including Freeman Chain Code Extended (FCCE), VCC, 3OT, and Differential Freeman Chain Code Extended (DFCCE), were established to enable seamless transformations and unified processing across variants.

Types and Variations

Freeman Chain Code

The Freeman Chain Code (FCC), introduced by Herbert Freeman in , represents the boundary of a digital object as a of codes corresponding to eight possible move directions in an 8-connected grid. This original formulation, often denoted as the Freeman Chain Code of Eight Directions (FCCE), numbers the directions from 0 to 7, with each code indicating a unit move of 45 degrees: 0 for east, 1 for northeast, 2 for north, 3 for northwest, 4 for west, 5 for southwest, 6 for south, and 7 for southeast, measured counter-clockwise from the positive x-axis. The angle for direction ii is given by θi=(i×45∘)mod  360∘,\theta_i = (i \times 45^\circ) \mod 360^\circ, where i∈{0,1,…,7}i \in \{0, 1, \dots, 7\}. In the first-order FCCE, the sequence records absolute directions of each boundary step, starting from an arbitrary point and tracing the contour, typically or counter-clockwise. A second-order variant computes differences between consecutive absolute directions, reducing sensitivity to starting orientation but requiring additional normalization for full invariance, such as cyclically shifting the sequence to its lexicographically smallest form. For example, a closed boundary approximating a circle might yield a sequence like "012345670", forming an octagonal path that closes back to the starting direction. The FCCE's advantages include its simplicity, requiring only 3 bits per code for storage efficiency, and its ability to accurately capture diagonal moves inherent to 8-connectivity, enabling compact representation of irregular boundaries without loss of topological connectivity. Introduced in Freeman's seminal work, it remains the baseline for evaluating subsequent chain code variants due to its foundational role and widespread adoption in shape encoding tasks.

Differential and Vertex Variants

Modifications to the foundational Freeman chain code have introduced variants that mitigate limitations such as sensitivity to rotation and representational redundancy, particularly for smooth or polygonal boundaries. These include the differential chain code, which emphasizes relative direction changes, and vertex-based approaches that focus on corner points rather than every boundary step. The differential chain code (DCC) encodes the difference in direction between consecutive steps along the boundary, defined as di=(ni−ni−1)mod  8d_i = (n_i - n_{i-1}) \mod 8, where nin_i represents the absolute direction code at step ii. This relative encoding produces compact sequences for smooth contours, as straight lines yield repeated 0s, while gentle curves feature mostly 0s interspersed with small values like ±1 or ±2. For instance, a horizontal line segment results in an all-zeros sequence, significantly reducing storage compared to absolute codes. DCC was analyzed for its efficiency in line drawing representation, demonstrating reduced data volume without loss of information. The vertex chain code (VCC), introduced by Bribiesca, represents boundaries by traversing the vertices of regular cells composing the shape, recording the number of cell vertices in contact with the contour at each step—typically using codes 1, 2, or 3 (with 4 indicating closure). This approach only updates the code at significant vertices or corners, making it suitable for polygonal approximations where straight segments are encoded implicitly through vertex positions. VCC achieves invariance to and , and it can be normalized for starting point independence, enhancing its utility for shape recognition. By focusing on vertices, it offers gains in boundaries with long straight segments, avoiding redundant codes for collinear points. The 3-orthogonal chain code (3OT) restricts movements to three orthogonal directions (forward, left, right relative to the current orientation), using a minimal set of three symbols for encoding. This simplification facilitates hardware implementation, as it reduces the complexity of direction tracking while maintaining lossless boundary description. Proposed for applications like corner detection and computation, 3OT proves effective for binary images with orthogonal features, outperforming four-direction codes in compression for certain contours. These variants provide targeted advantages: DCC excels in compactness for smooth, continuous curves by leveraging directional stability; VCC enhances efficiency for polygonal or corner-dominated shapes through selective vertex recording; and 3OT prioritizes implementation simplicity in resource-constrained environments. While the foundational Freeman code serves as a basis for these developments, the variants address specific representational challenges without altering core boundary-tracing principles.

Algorithms and Implementation

Encoding Process

The encoding process for generating a chain code from a boundary involves systematically tracing the contour of a connected component while recording directional changes. This procedure typically employs 8-connectivity, as introduced in Freeman's framework for representing object boundaries. The process begins with identifying a starting on the boundary and proceeds through a sequential traversal until the boundary is fully enclosed, ensuring a lossless representation of the shape. To initiate encoding, the starting is selected as the leftmost (or uppermost leftmost) boundary point in the image, often the first foreground encountered in a from the top-left corner; its coordinates (x, y) are output as the initial position. Next, the initial direction is determined by examining the eight possible neighbors of the starting in a predefined order, such as from an assumed entry direction (e.g., from the west neighbor, treated as background), to identify the first adjacent boundary . The traversal follows a consistent search pattern using the , which checks the eight surrounding s in a manner starting from the previous entry direction to locate the next boundary . At each step, the direction from the current to the next is encoded as a value from 0 to 7, corresponding to the eight possible unit moves (0 for east, 1 for northeast, up to 7 for southeast). This code is appended to the sequence, and the process repeats, updating the current position and entry direction for the next check. The traversal continues until the starting is revisited and the subsequent matches the initial next , confirming closure of the boundary. The following outlines the core for 8-connected boundary tracing and chain code generation:

Initialize: Find starting boundary [pixel](/page/Pixel) b0 = (x0, y0); set entry direction c0 (e.g., west neighbor as background). Set current [pixel](/page/Pixel) b = b0; set previous entry c = c0; initialize empty chain code sequence S. While true: Examine [Moore neighborhood](/page/Moore_neighborhood) of b clockwise starting from c: check [pixels](/page/Pixel) n1 to n8. Find first foreground (boundary) [pixel](/page/Pixel) nk among n1 to n8. If nk == b0 and b == starting next [pixel](/page/Pixel) b1, break (closure detected). Append direction code d (0-7) from b to nk to S. Set c = the [pixel](/page/Pixel) preceding nk in the neighborhood check (new entry for next step). Set b = nk. Output: Coordinates (x0, y0) and sequence S.

Initialize: Find starting boundary [pixel](/page/Pixel) b0 = (x0, y0); set entry direction c0 (e.g., west neighbor as background). Set current [pixel](/page/Pixel) b = b0; set previous entry c = c0; initialize empty chain code sequence S. While true: Examine [Moore neighborhood](/page/Moore_neighborhood) of b clockwise starting from c: check [pixels](/page/Pixel) n1 to n8. Find first foreground (boundary) [pixel](/page/Pixel) nk among n1 to n8. If nk == b0 and b == starting next [pixel](/page/Pixel) b1, break (closure detected). Append direction code d (0-7) from b to nk to S. Set c = the [pixel](/page/Pixel) preceding nk in the neighborhood check (new entry for next step). Set b = nk. Output: Coordinates (x0, y0) and sequence S.

This algorithm ensures consistent tracing by always advancing to the next boundary pixel without revisiting interiors. To handle potential cracks or junctions in the boundary—such as thin gaps or branching points caused by rasterization—the check enforces a single-path traversal by prioritizing the first encountered neighbor in the ordered search, preventing gaps and maintaining connectivity without . Junctions are resolved implicitly by the rule, which selects one outgoing direction consistently. The computational complexity of the encoding process is O(N), where N is the length of the boundary in pixels, as each boundary pixel is visited exactly once during the linear traversal.

Normalization Techniques

Chain code normalization techniques render the directional sequence invariant to translation, rotation, and starting point, enabling reliable comparisons in shape analysis. Translation invariance arises naturally from the focus on relative directions in the sequence, with absolute starting coordinates managed independently during encoding. Starting point normalization treats the chain code as a circular and applies a cyclic shift to begin with the lowest code, such as the first 0 in Freeman chain code equivalents, yielding the lexicographically smallest representation. Rotation invariance for codes is obtained by subtracting an offset equal to the minimum direction value from all codes 8, aligning the to start from 0; differential chain codes, based on direction changes, are inherently robust as uniform preserve differences. The standard proceeds as follows: compute the initial chain code , identify the minimum code position, perform a cyclic shift to relocate it to the start, and apply the rotation adjustment by subtracting the minimum direction 8 for absolute codes. For instance, an original "0642" is cyclically redefined to "20642", then transformed via first differences to "6666", resulting in the normalized shape number "66666". Scale invariance, when required, involves resampling the boundary contour to a uniform length prior to chain code generation, though this extension is uncommon for traditional binary chain codes. These methods underpin effective shape matching in recognition tasks by ensuring canonical forms across transformations.

Applications

Image Compression

Chain codes facilitate the compression of contours by representing the boundary path as a compact sequence of directional instructions, rather than storing the coordinates of each boundary individually. In Freeman's chain code, for instance, an 8-connectivity variant encodes each step along the contour using one of eight possible directions, requiring only 3 bits per step (log₂(8)), which contrasts sharply with the bit cost of listing all N boundary s explicitly. This mechanism achieves substantial data reduction for smooth or structured boundaries, as the sequence length remains proportional to the number of steps, typically much shorter than exhaustive lists. To further enhance compression ratios, chain codes are often combined with preprocessing transforms and techniques. The move-to-front (MTF) transform reorganizes the sequence to prioritize frequent directions, improving subsequent encoding efficiency, while adaptive exploits statistical redundancies in the transformed data for near-optimal bit allocation. Additionally, (RLE) can be applied to handle repeated directions, such as long straight segments in contours, yielding further savings in repetitive patterns. These enhancements form a , as demonstrated in methods integrating Burrows-Wheeler transform (BWT) with MTF and , which achieve average code lengths below 2 bits per symbol on benchmark datasets. Performance evaluations highlight chain code-based methods' superiority for contour-heavy images, such as document scans, where they outperform standards like and . A 2014 study using 3-orthogonal-tilt (3OT) chain codes with reported 27% better compression than JBIG2 at 200 dpi and 65% at 600 dpi, alongside 6-35% gains over 's JB2 layer, particularly on binary objects with clear edges. Similarly, 2019 surveys of techniques, including those combining chain codes with LZ77, highlight improved efficiency for scanned documents and . Despite these advantages, chain codes exhibit limitations in handling noisy or highly irregular boundaries, where extraneous direction changes inflate the sequence length and degrade compression ratios, as the method assumes clean, connected contours traceable via boundary following algorithms.

Shape Analysis and Recognition

Chain codes facilitate feature extraction from object boundaries in binary images by encoding contours as sequences of directional symbols, enabling the of geometric and statistical properties. The perimeter PP of a is directly derived from the chain code as the length of the sequence, adjusted for directionality: for 4-directional codes, PP equals the number of codes, while for 8-directional codes, it is the count of even directions plus twice the odd directions to account for diagonal steps. , a measure of circularity, is calculated as 4πAP2\frac{4\pi A}{P^2}, where AA is the enclosed area, providing insight into elongation or irregularity. Direction histograms, generated by tallying the of each directional code in the sequence, capture angular distribution and orientation trends along the contour. In shape recognition, normalized codes serve as compact representations for matching against templates or databases. String alignment techniques, such as modified Needleman-Wunsch algorithms, compare code sequences by allowing gaps and substitutions to quantify similarity, accommodating variations in contour length or noise. Fourier descriptors can be derived from chain codes by treating the sequence as a parametric curve and applying discrete Fourier transforms to its coordinates, yielding - and scale-invariant coefficients for . Chain codes have been applied in handwritten character recognition since the , where boundary encoding distinguishes scripts by contour patterns, as in early systems using direction histograms from chain codes. In medical imaging, they trace cell contours for segmentation and analysis, such as in algorithms that vectorize boundaries from microscopic images. For geographic information systems, chain codes represent boundaries, supporting simplification by reducing code length while preserving essential . For example, in , chain codes differentiate an 'O'—characterized by a smooth, uniform sequence of directions—from a 'D', which features longer straight segments interrupted by curves. Since the 2010s, chain codes have integrated with as preprocessing steps, where embeddings of code sequences feed into convolutional neural networks for enhanced shape classification, such as in numeral recognition systems achieving high accuracy through combined Freeman codes and neural classifiers. Chain codes also enable topological analysis, computing properties like genus via the from multiple contours, as in recent methods using orthogonal chain symbols to evaluate connectivity in binary images.

Comparisons with Other Codes

Chain codes differ from crack codes in their approach to boundary tracing in binary images. Chain codes, such as the Freeman variant, trace the boundary by connecting the centers of pixels inside the object, using 8-connectivity to encode directions between adjacent pixels. In contrast, crack codes trace the cracks or boundaries between object and background pixels, employing 4-connectivity for horizontal and vertical moves. This interior-focused path in chain codes provides better preservation of object connectivity but underestimates enclosed area and lacks sub-pixel precision, whereas crack codes offer more accurate area estimation and sub-pixel boundary resolution at the cost of longer code lengths and overestimated perimeters along diagonals. Compared to (RLE), which compresses filled regions by encoding consecutive runs of identical pixels across scanlines, chain codes are specialized for contour boundaries only and do not efficiently represent interior pixels. RLE excels in compacting uniform areas within binary images, making it suitable for entire raster data, while chain codes focus on shape outlines, often leading to hybrid approaches where RLE handles region filling and chain codes describe edges. In relation to polygonal approximations, such as those generated by the Douglas-Peucker algorithm, chain codes provide pixel-precise, lossless representations of digital curves but result in verbose sequences for complex boundaries. Polygonal methods simplify these chains into fewer straight-line segments that approximate smooth shapes, achieving compactness for storage and rendering while introducing minor approximation errors. Chain codes serve as an intermediate step for deriving such polygons, preserving exact raster details that approximations may discard. Regarding performance, chain codes are simpler and more straightforward for representing boundaries in binary images compared to vector formats like , which support scalable, parametric curves but require more computational overhead for raster-to-vector conversion. However, chain codes are less efficient for complex, high-resolution images where vector representations reduce file sizes through geometric . Overall, chain codes offer advantages in lossless, discrete boundary encoding that reduces storage needs relative to full coordinate lists, enabling efficient feature extraction. Their primary disadvantages include sensitivity to , which can propagate errors along the boundary, and lack of inherent , necessitating extensions like resampling for multi-resolution analysis.

Interconversion Methods

Interconversion between chain code variants and other boundary representations is essential for integrating chain codes into diverse processing pipelines, such as combining compression with rendering or in hybrid systems. These methods typically involve mapping directional sequences to alternative encodings while preserving the original contour , often achieving linear O(N), where N is the length of the chain code sequence. Seminal works have established procedural algorithms for these translations, leveraging local transitions or boundary adjustments to ensure lossless fidelity. One key aspect of interconversion involves adapting chain codes to vertex-based representations like the Vertex Chain Code (VCC), introduced by Bribiesca in 1999. VCC encodes the boundary of shapes composed of regular cells (e.g., pixels) using symbols that represent the number of cell vertices on the contour for each boundary cell, providing invariance to translation, rotation, starting point, and scaling. While direct mapping from Freeman Chain Code of Eight Directions (FCCE) to VCC requires reconstructing the boundary pixel sequence to count vertices per cell, algorithms exist to derive VCC from pixel boundaries traced by chain codes. Converting a standard chain code to a crack code addresses the representational shift from pixel-centered boundaries (interior to pixels) to inter-pixel cracks, enabling compatibility with crack-based analyses like area estimation. The algorithm adjusts directions by rotating them 45 degrees clockwise or counterclockwise and reverses the traversal order to align the path with crack edges; for an FCCE direction d, the corresponding crack direction is (d + 1) mod 8 or equivalent, followed by path inversion. This mapping ensures the crack code traces the dual boundary without loss, as detailed in analyses of contour code properties. Reverse conversion from crack to chain code applies the inverse rotation and forward traversal, restoring the pixel-based sequence. To translate a chain code to (RLE), the algorithm simulates boundary traversal to populate row-wise run lengths, effectively rasterizing the contour into horizontal segments for image reconstruction or compression. Starting from the initial position, each directional step in the chain code updates the current row and column, appending or merging run lengths for boundary pixels encountered in that row; straight horizontal moves contribute directly to runs, while vertical or diagonal steps trigger row changes and partial run updates. This yields an RLE sequence representing the filled boundary outline. The reverse process, from RLE to chain code, employs boundary extraction algorithms that scan rows to identify edge transitions using neighborhood rules, tracing the perimeter to generate directional codes in a single pass. These extractions can operate on the RLE structure to achieve efficient contour recovery. A straightforward example of interconversion within chain code variants is between FCCE and the Differential Freeman Chain Code of Eight Directions (DFCCE), where DFCCE encodes relative turns rather than absolute directions. The forward conversion computes the differential as the modular difference between consecutive FCCE directions.

pseudocode

function fcc_to_dfcc(fcc_sequence): dfcc = [] for i in 1 to length(fcc_sequence) - 1: diff = (fcc_sequence[i+1] - fcc_sequence[i]) mod 8 dfcc.append(diff) return dfcc // Starting direction from fcc_sequence[0]

function fcc_to_dfcc(fcc_sequence): dfcc = [] for i in 1 to length(fcc_sequence) - 1: diff = (fcc_sequence[i+1] - fcc_sequence[i]) mod 8 dfcc.append(diff) return dfcc // Starting direction from fcc_sequence[0]

The reverse uses cumulative summation modulo 8, initializing with the known starting direction to reconstruct the absolute sequence. This pairwise operation ensures exact reversibility. All major chain code variants, including FCCE, VCC, the Three Orthogonal (3OT) code, and DFCCE, are interconvertible through graph-based mappings represented as transition matrices that define local symbol substitutions. For instance, FCCE (F8) maps to DFCCE (AF8) via differences 8, while VCC and 3OT connect to four-directional Freeman (F4) subsets through orthogonal projections, allowing bidirectional translations without information loss. These mappings confirm topological equivalence across representations. The linear O(N) complexity arises from the locality of each transition, making interconversions computationally efficient for large contours. Such interconversion methods facilitate hybrid systems, for example, by compressing boundaries with chain codes for storage and then rendering them as polygons via vertex lists derived from boundary reconstruction for visualization or geometric analysis. This modularity enhances applications in image processing pipelines without redundant recomputation.

References

  1. https://www.sciencedirect.com/topics/engineering/chain-code
  2. https://www.researchgate.net/publication/228903655_The_evolution_and_trend_of_chain_code_scheme
  3. https://www.researchgate.net/publication/283496289_Digit_Recognition_Using_Freeman_Chain_Code
  4. https://pmc.ncbi.nlm.nih.gov/articles/PMC12453722/
  5. https://ieeexplore.ieee.org/document/5219197
  6. https://cgm.cs.mcgill.ca/~godfried/teaching/pr-notes/chain.pdf
  7. https://www.semanticscholar.org/paper/On-the-Encoding-of-Arbitrary-Geometric-Freeman/ef2e340331efc529e59b40c95f51618b60f06a74
  8. http://engr.case.edu/merat_francis/eecs490f07/lectures/lecture23.pdf
  9. https://bohr.wlu.ca/hfan/cp467/12/notes/cp467_12_lecture18_representation.pdf
  10. http://eprints.utm.my/8535/1/LAWulandhari2008-The_Evolution_and_Trend_of.pdf
  11. https://www.eurecom.fr/publication/753/download/mm-andrju-010801.pdf
  12. https://doi.org/10.1016/S0031-3203(98)00132-0
  13. https://doi.org/10.1016/B978-0-12-597302-1.50010-4
  14. https://doi.org/10.1117/1.2052793
  15. https://doi.org/10.5220/0006688400720078
  16. https://doi.org/10.1016/j.future.2019.08.021
  17. https://doi.org/10.1016/j.future.2020.12.016
  18. https://doi.org/10.1016/j.asoc.2019.03.024
  19. https://doi.org/10.1117/1.JEI.23.1.013031
  20. https://airccse.org/journal/ijcga/papers/4214ijcga02.pdf
  21. https://onlinelibrary.wiley.com/doi/abs/10.1002/ett.4460030404
  22. https://www.sciencedirect.com/science/article/pii/S0031320398001320
  23. https://dl.acm.org/doi/10.1007/11864349_15
  24. https://www.sciencedirect.com/science/article/abs/pii/S1047320315000206
  25. https://www.csie.ntpu.edu.tw/~dalton/images/teacher/course/DIP/lecture/Chapter11.pdf
  26. https://indjst.org/download-article.php?Article_Unique_Id=INDJST170&Full_Text_Pdf_Download=True
  27. https://doi.org/10.1016/j.jvcir.2015.01.013
  28. https://doi.org/10.1016/j.dsp.2014.03.007
  29. https://doi.org/10.3390/sym11101274
  30. https://www.cs.rutgers.edu/~elgammal/classes/cs334/BinaryImageAnalysis.pdf
  31. https://www.researchgate.net/publication/308916470_Shape_based_Recognition_Using_Freeman_Chain_Code_and_Modified_Needleman-Wunsch
  32. https://hal.science/hal-00446037v1/file/ARS-Journal-SurveyPatternRecognition.pdf
  33. https://www.sciencedirect.com/science/article/pii/S0377042725002900
  34. https://inria.hal.science/inria-00120408v1/document
  35. https://www.spiedigitallibrary.org/conference-proceedings-of-spie/6279/62792M/Edge-detection-and-contour-tracing-of-medical-cell-images/10.1117/12.725262.full
  36. https://support.esri.com/en-us/gis-dictionary/chain-code
  37. https://www.cseij.org/papers/v12n1/12122cseij02.pdf
  38. https://www.worldscientific.com/doi/full/10.1142/S0218001424540120
  39. https://sfat.massey.ac.nz/research/centres/crisp/pdfs/2010_IVCNZ_155.pdf
  40. https://gisgeography.com/image-compression-encoding/
  41. https://www.sciencedirect.com/science/article/pii/0734189X88901211
  42. https://www.sciencedirect.com/topics/engineering/polygonal-approximation
  43. https://www.sciencedirect.com/topics/engineering/chain-coding
  44. https://www.ee.nthu.edu.tw/clhuang/09420EE368000DIP/chapter11.pdf
  45. http://turing.iimas.unam.mx/~ernesto/VCC.htm
  46. https://personal.math.vt.edu/hhlopez/pdfs/Papers/5paper.pdf
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.