Source Coding for Line Drawings (Chain, Delta, Image, Opta, Rate-Distortion Function).

Abstract

This dissertation considers problems in source coding of line drawing images such as h and writing, maps, drawings and trajectories. In particular, this dissertation focuses on two major problems: (1) given a fixed rate, how can one encode line drawings so that an accurate reproduction is obtained from their binary representations, (2) given a fixed encoding rate, what is the theoretical limit to the reproduction accuracy. For the first problem, this dissertation introduces and analyzes a new class of chain codes. These are called delta codes because of their similarity to delta modulation for waveforms. This dissertation proposes a specific encoding rule for delta codes that makes the reproduction behave nicely and , consequently, makes it possible to calculate the per-length average rate and per-length average area-of-error distortion. Such calculations are first made for delta codes applied to infinite straight lines, and then to infinite slowly curving lines. The performance analysis shows the expected result: for infinite straight and slowly curving lines, delta codes outperform other chain codes with the same link type set. For the second problem, r and om line drawing models and bounds to their OPTA (Optimum Performance Theoretically Achievable) functions are discussed. Considered is a r and om waveform model that consists of one deterministic and one r and om coordinate. The deterministic coordinate of the model is chosen to be linear in time. With properly selected parameters, this model has two useful properties: realistic smoothness and mathematical tractability. As distortion measures, per-length average distance and average squared distance distortion measures are considered. These have the advantage that they are well defined for any curving lines and any reproductions. Since one coordinate of the model is deterministic, its OPTA function can be related to the OPTA or the rate-distortion function of its r and om coordinate. Using such an approach, upper and lower bounds to the OPTA functions for stationary ergodic Gaussian r and om waveform models are derived.