Representing contours as sequences of one dimensional functions

Jon SporringResearch 2016

Abstract

This paper introduces a "1+1D" geometric model for representing text character contours in scanned documents. By decomposing 2D contours into a sequence of local 1D functions, the authors achieve a resolution-independent representation that is at least twice as compact as traditional 2D contour methods. The approach utilizes Monge patches, scale-space analysis, and Minimum Description Length (MDL) to optimize the balance between model complexity and accuracy.

Introduction

Storing and transmitting scanned office documents presents a significant data challenge. A single 600 DPI page can consume 4MB of raw space, despite the actual textual information being only a few kilobytes. Existing solutions like JPEG perform poorly on high-contrast text, while font-recognition systems often produce "uncanny" results if the font match is imperfect. Lossless systems like JBIG2 are efficient but often ignore the underlying geometry of characters. This research proposes an analytical, geometric representation that captures the "essence" of a character's shape while remaining highly compact and scalable.

Methodology: The 1+1D Model

The core innovation is the 1+1D Model. Traditionally, a 2D contour is modeled as two separate functions, $x(t)$ and $y(t)$. The authors argue this is redundant because a contour is inherently a 1D structure.

Their approach involves "cutting" the character contour into segments called Monge Patches. Each segment is represented as a 1D function within its own local coordinate system. To determine the optimal placement of "cuts" or knots, the system uses Gaussian smoothing (scale-space analysis) to identify semantically important points like corners while ignoring pixel-level noise.

Figure 2: Illustration of the 1+1D model showing a contour segmented by knots (black dots) with local coordinate systems defined for each segment.

The optimization process uses Minimum Description Length (MDL) to balance model accuracy against complexity. A "Split-and-Merge" algorithm iteratively adjusts knots to find the most efficient description of the shape, effectively treating geometry as a compression strategy.

Key Results and Visual Fidelity

The model was evaluated using 157 blobs extracted from a standard CCITT fax image, covering various styles and sizes. The 1+1D representation proved to be at least twice as compact as typical 2D contour representations used in resolution-independent fonts like PostScript.

Figure 3: Examples of character blobs (v, 2, p, t, T, S, e, a, é) represented by the 1+1D model. The gray areas show the original pixels, while the black lines and dots represent the analytical geometric model and its knots.

On average, each character blob was represented by just 7.5 polynomial pieces. Despite this high compression, the resulting geometric models maintained high visual fidelity, successfully capturing the structure of small, large, and italicized text. The total bitrate for the 157 test blobs was estimated at 55,957 bits.

Conclusion

The 1+1D geometric model offers a powerful middle ground between raw bitmap storage and rigid font matching. By leveraging the inherent 1D nature of contours and local coordinate systems, it achieves superior compactness and resolution independence. Future work may involve optimizing the handling of straight lines and integrating the model into standards like JBIG2 for progressive, coarse-to-fine document decoding.

Summary updated

Abstract

A sequence of one-dimensional geometric descriptions is suggested, for representing the contours of text characters (blobs) in black and white scanned textual images.This representation can be used to analytically encode alphabets of similar blobs into pseudo-fonts that are resolution independent, while simultaneously maximizing compression potential.Such a sequential one-dimensional representation was found to retain flexibility and to be at least twice as compact, when compared to two-dimensional contour representations classically used for representing generated resolution independent fonts.
BibTeX
@inproceedings{sporring2016representing,
  author = {Jon Sporring},
  title = {{Representing contours as sequences of one dimensional functions}},
  booktitle = {Research},
  year = {2016},
}
Figure