Shortest path methods in representation and compression of signals and image contours

Abstract

Signal compression is an important problem encountered in many applications. Various techniques have been proposed over the years for adressing the problem. The focus of the dissertation is on signal representation and compression by the use of optimization theory, more shortest path methods.

Several new signal compression algorithms are presented. They are based on the coding of line segments which are used to spproximate, and thereby represent, the signal. These segments are fit in a way that is optimal given some constraints on the solution. By formulating the compession problem as a graph theory problem, shortest path methods can be applied in order to yeild optimal compresson with respect to the given constraints.

The approaches focused on in this dissertaion mainly have their origin in ECG comression and is often referred to as time domain compression methods. Coding by time domain methods is based on the idea of extracting a subset of significant signals samples to represent the signal. The key to a successful algoritm is a good rule for determining the most significant samples. Between any two succeeding samples in the extracted smaple set, different functions are applied in reconstruction of the signal. These functions are fitted in a wy that guaratees minimal reconstruction error under the gien constraints. Two main categories of compression schemes are developed:

1. Interpolating methods, in which it is insisted on equality between the original and reconstructed signal at the points of extraction.

2. Non-interpolating methods, where the inerpolatian restriction is released.

Both first and second order polynomials are used in reconstruction of the signal. There is solso developed an approach were multiple error measures are applied within one compression algorithm.

The approach of extracting the most significant smaples are further developed by measuring the samples in terms of the number of bits needed to encode such samples. This way we develop an approach which is optimal in the ratedistortion sense.

Although the approaches developed are applicable to any type of signal, the focus of this dissertaion is on the compression of electrodiogram (ECG) signals and image contours, ECG signal compression has traditionally been