Lably
Skip to content

Boundary tracing

  • 9 min read
  • 4 chapters

Related on Lably

Through Digital image processing, Pixel and Computer vision

Lab · Class 10–12Handwriting RecognizerLab · Class 10–12Pixel Art ExplorerLab · Class 3–8Pixel Art (Pixel Studio)Lab · Class 8–12AR Marker Tracking

To define the boundary correctly it is necessary to introduce a topological space corresponding to the given digital image. Such space can be a two-dimensional abstract cell complex. It contains cells of three dimensions: the two-dimensional cells corresponding to pixels of the digital image, the one-dimensional cells or “cracks” representing short lines lying between two adjacent pixels, and the zero-dimensional cells or “points” corresponding to the corners of pixels. The boundary of a subset S is then a sequence of cracks and points while the neighborhoods of these cracks and points intersect both the subset S and its complement I – S.

The boundary defined in this way corresponds exactly to the topological definition and corresponds also to our intuitive imagination of a boundary because the boundary of S should contain neither elements of S nor those of its complement. It should contain only elements lying between S and the complement. This are exactly the cracks and points of the complex.

This method of tracing boundaries is described in the book of Vladimir A. Kovalevsky and in the web site.

Algorithms

Types

  • Pixel-Following: walks through cells and records them. Typically only traces an outer boundary and require post-processing when changing the size of the space. Easiest to implement
  • Vertex-Following Method: walks through edges, recording edges and corners. Typically only traces the outer boundary. Sequential edges can be removed to simplify the data
  • Run-Data-Based: processes all cells in the space. Traces all boundaries in the image. Less efficient than other types for small single boundaries since all cells have to be processed. More efficient for large, complex images since the steps per individual cell are usually less than other types

Examples

Algorithms used for boundary tracing:

  • Square tracing algorithm. Can only be used for 4-connected (non-diagonal) patterns and requires the stopping criteria to be entering the starting cell in the same direction as the beginning.
  • Moore-neighbor tracing algorithm is similar to the Square tracing algorithm with similar weaknesses but works with 8-connected (diagonal) patterns
  • Radial sweep
  • Theo Pavlidis’ algorithm tests three cells in front but the check can be short-circuited. Might fail on some patterns.
  • A generic approach using vector algebra for tracing of a boundary can be found at
  • An extension of boundary tracing for segmentation of traced boundary into open and closed sub-section is described at

Marching squares extracts contours by checking all corners of all cells in a two-dimensional field. It does not use an initial position and does not generate the contour as an ordered sequence so it does not 'trace' the contour. Has to check each cell corner for all four neighbors but since the checks are independent performance can be easily improved with parallel processing

Sign in to keep reading

3 more chapters are free with a Lably account.

More in Robotics

AnthropomorphismAttribution of human traits to non-human entitiesMeta PlatformsAmerican multinational technology conglomerateSpace probeUnmanned robotic spacecraftStereoscopyTechnique for creating or enhancing the impression of depth in an imageControl systemSystem that manages the behavior of other systemsInertial navigation systemContinuously computed dead reckoning