Storing and reconstituting analog signals using data compression

• US 4,809,195 A
• Filed: 04/25/1986
• Issued: 02/28/1989
• Est. Priority Date: 04/26/1985
• Status: Expired due to Fees

• Current Assignee: Battelle Memorial Institute
• Original Assignee: Battelle Memorial Institute
• Inventors: Bechet, Louis
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): HERNDON, HEATHER R
• Application Number:
  US06/856,154
• Time in Patent Office: 1,040 Days
• Field of Search: 364/518, 364/520, 364/521, 340/703, 340/723, 340/729, 382/3
• US Class Current: 345/442
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06V 10/20 Image preprocessing
• CPC Class Codes: G07C 9/24 by means of a handwritten signature

Abstract

A method for storing compressed data indicative of an analog signal and reproducing that analog signal from the compressed data. The analog signal to be stored is superimposed on a rectangular coordinate system. An elementary interval is defined on the X-axis of an X-Y coordinate system for the selection of a first series of points, a second series of points (R₁, R₂, R₃) is determined by establishing a threshold ratio between the chord (C₁, C₁ '"'"') separating two non-consecutive points and the sum of the chords (C₁, C₂, C₃ ; C₁ '"'"', C₂ '"'"', C₃ '"'"') separating each of the consecutive points within two non-consecutive points. An interval (N) between these two non-consecutive points is selected to correspond to the maximum ratio below this threshold. The analog signal is reconstituted by generating a signal having a curve that is plotted by establishing between each group of three non-consecutive points a parabola with respect to the axis of symmetry corresponding to the axis of the elementary intervals.

Claims

1. A method for storing data indicative of an input analog signal in the form of rectangular coordinates X and Y values in a memory and producing an output signal substantially identical to the input analog signal from the stored data, comprising the steps of:

defining an elementary interval (T) on an X-axis of an X-Y coordinate system on which the input analog signal is superimposed and selecting a first series of points separated along the X-axis by interval T, interval (T) providing points which are sufficiently close together to enable them to be connected to form a curve similar to the curve of the input signal;

selecting a second series of points which is a subset of the first series by establishing a threshold ratio between a chord separating two non-consecutive points and the sum of chords separating each of the consecutive points within the two non-consecutive points; and

selecting an interval between these two non-consecutive points to correspond to the maximum ratio below the threshold, in that the address of the points of each group of three non-consecutive points determined in this way is established as well as the number of elementary intervals (T) between them and their respective amplitudes (a₁, ₂ and a₃);

storing in a memory, the address and the amplitude, which are the X and Y values, of the isolated points which do not come within a group of three non-consecutive points; and

generating, from the data previously stored in memory, an output analog signal corresponding to the input analog signal by establishing between each group of three-non-consecutive points a parabola with respect to an axis of symmetry corresponding to the axis of the elementary intervals from the equation;

space="preserve" listing-type="equation">Y.sub.(T) =AT.sup.2 +BT+C

in which;

A=(a₁ +a₃ -2a₂)/2T²

B=(a₃ -a₁)/2T

C=a₂.

2. A method according to claim 1 further comprising the steps of:

fixing a ratio between the number of points in the first series and the number of points in the second series,

calculating the ratio between the number of points in the first series and the number of points selected to constitute the second series,

adjusting the aforesaid threshold ratio value in dependence on the calculated ratio between the numbers of points in the first and second series, in such a manner as to adjust the calculated ratio towards the first mentioned fixed ratio between the numbers of points, and

repeating the determination of the points constituting the second series using the adjusted threshold ratio value, until the actual ratio between the number of points in the first series ad the number of points in the second series corresponds to the fixed ratio therebetween.

3. A method for numerically storing in a memory medium data representing an analog curve in a system of rectangular coordinates, comprising the steps of:

generating a signal indicative of the analog curve;

defining on one axis of the coordinate system, an elementary interval, and selecting on the curve a first series of consecutive points spaced apart by the elementary interval, the elementary interval being such as to provide points on the curve sufficiently close together that when the points are connected by chords a curve similar to the analog curve is obtainable;

determining a threshold value for the ratio between the length of the chord separating two non-consecutive points of the first series of points, and the sum of the chords respectively separating each of the consecutive points within the two non-consecutive points;

determining values of the ratio for points of the first series;

comparing the ratio values with the threshold value and selecting non-consecutive points so that the interval therebetween provides the maximum value of the ratio below the threshold;

defining a second series of points comprising each group of three non-consecutive points determined by the comparison and selection together with those points of the first series that do not come within a group of three non-consecutive points; and

storing data in a memory medium indicative of the addresses of the points of each group of three non-consecutive points as well as the number of elementary intervals between the non-consecutive points and the amplitudes of the non-consecutive points, and storing the address and amplitude which are the X and Y values, of each of the isolated points.

4. A method according to claim 3 further including the step of:

generating a second analog signal representative of the first analog signal, from the stored values of the points of the second series, the shape of the signal being formed by plotting the groups of three non-consecutive points and the isolated points, and establishing between each group of three non-consecutive points a respective parabola about an axis of symmetry corresponding to the axis of the elementary intervals, and determining the parabola from the equation

space="preserve" listing-type="equation">Y.sub.(T) =AT.sup.2 +BT+C

in which;

A=(a₁ +a₃ -2a₂)/2T²

B=(a₃ -a₁)/2T

C=a₂

and in which A₁, ² and a3 are the respective amplitudes of the points of the group of three non-consecutive points, and T is the magnitude of the elementary interval.

5. A method for storing data indicative of an input handwriting hodograph signal in the form of rectangular coordinates X and Y values in a memory and producing an output hodograph signal substantially identical to the input signal from the stored values, comprising the steps of:

superimposing the input hodograph signal on an X-Y coordinate system;

defining an elementary interval (T) on the X-axis of the coordinate system;

selecting a first series of points along the input hodograph signal, the points being spaced by interval T, interval (T) providing points which are sufficiently close together to enable them to be connected to form a curve similar to the curve of the input signal selecting a second series of points by establishing a threshold ratio between a chord separating two non-consecutive points within the two non-consecutive points and selecting an interval between these two non-consecutive points to correspond to the maximum ratio below the threshold, in that the address of the ponts of each group of three non-consecutive points determined in this way is established as well as the number of elementary intervals (T) between them and their respective amplitudes (a₁, ₂ and a3);

storing in a memory, the address and the amplitude, which are the X and Y values, of the isolated points which do not come within a group of three non-consecutive points; and

generating, from the data previously stored in memory, the output hodograph signal corresponding to the input hodograph signal by generating a signal having a shape determined as follows - establishing between each group of three non-consecutive points a parabola with respect to an axis of symmetry corresponding to the axis of the elementary intervals from the equation;

space="preserve" listing-type="equation">Y.sub.(T) =AT.sup.2 +BT+C

in which;

A=(a₁ +a₃ -2a₂)/2T²

B=(a₃ -a₁)/2T

C=a₂.

6. A method for numerically storing in a memory medium data representing an input handwriting hodograph analog signal in a system of rectangular coordinates, comprising the steps of:

generating the input hodograph signal;

superimposing the input hodograph signal on an X-Y coordinate system;

defining an elementary interval (T) on the X-axis of the coordinate system;

selecting a first series of points along the input hodograph signal, the points being spaced by interval T, interval (T) providing points which are sufficiently close together to enable them to be connected to form a curve similar to the curve of the input signal;

determining a threshold value for a ratio between the length of the chord separating two non-consecutive points of the first series of points, and the sum of the chords respectively separating each of the consecutive points within the two non-consecutive points;

determining values of the ratio for points of the first series;

comparing the ratio values with the threshold value and selecting non-consecutive points so that the interval therebetween provides the maximum value of the ratio below the threshold;

defining a second series of points comprising each group of three non-consecutive points determined by the comparison and selection together with those points of the first series that do not come within a group of three non-consecutive points; and

storing data in a memory medium indicative of the addresses of the points of each group of three non-consecutive points as well as the number of elementary intervals between the non-consecutive points and the amplitudes of the non-consecutive points, and storing the address and amplitude of each of the isolated points.

7. A method according to claim 6 further including the step of:

generating an output hodograph signal representative of the input hodograph signal, from the stored values of the points of the second series, comprising the step of plotting the groups of three non-consecutive points and the isolated points, and establishing between each group of three non-consecutive points a respective parabola about an axis of symmetry corresponding to the axis of the elementary intervals, and determining the parabola from the equation

space="preserve" listing-type="equation">Y.sub.(T) =AT.sup.2 +BT+C

in which;

A=(a₁ +a₃ -2a₂)/2T²

B=(a₃ -a₁)/2T

C=a₂

and in which a1, a₂ and a3 are the respective amplitudes of the points of the group of three non-consecutive points, and T is the magnitude of the elementary interval.

8. A method for storing compressed data indicative of an input analog sinal, comprising the steps of:

A. establishing an X-Y coordinate system with respect to the input analog signal, so that each point of the input analog signal can be described by an X.Y pair;

B. defining an elementary interval T along the X-axis, the X-Y pairs corresponding to the X values spaced at interval T constituting a first set of X Y pairs, interval T being chosen such that the first set of X,Y pairs, if connected, would substantially reconstitute the input signal;

C. selecting from said first set of X, Y pairs, a subset of X,Y pairs to be stored in a storage medium, selection being carried out in accordance with steps (a)-(l), beginning with a first point X₀, Y₀ as follows;

(a) establish a tolerance arc/chord ratio;

(b) initialize calculation;

(c) establish a jump interval which corresponds to a jump of a predetermined number of elementary intervals T along the X axis from X0, Y₀ ;

(d) determine the length of a chord C₁ from the current point being tested to the point determined by the jump interval, and determine the lengths of chords C₁, c₂, etc. from one point to the next beginning with the current point being tested to the point determined by the jump interval, and determine ratio between the sum of chords c₁, c₂, etc. and chord c₁,

(e) compare the ratio determined in step (d) with the tolerance established in step (a), if the ratio detemined in step (d) is larger than the tolerance established in step (a), go to step (f), but if the ratio determined in step (d) is smaller than the tolerance established in step (a), go to step (h);

(f) if the jump for which the ratio of the chords is greater than the tolerance is greater than 2, memorize the interval of the last jump for which the ratio of the chords is lower than the tolerance (noted at step (h)), however, if the jump is rejected, go to step (g),

(g) return to step (c)

(h) increase the jump interval established in step (c) by one and return to step (d),

(i) note the jump interval determined at step (f) and note the number of points processed up to now.

(j) if all points have not yet been processed ,go to step (k), otherwise, go to step (1);

(k) return to step (c);

(l) determine a value of an overall compression factor by comparing the number of points selected for the subset with the total number of points based on the elementary interval T and if the compression factor is greater than a predetermined amount, such that there is memory in the storage medium available, go to step (m); and

(m) reduce the initial tolerance set at step (a) to increase the number of points selected for the subset and return to step (b), the process recommencing on the basis of the new tolerance and continuing until the compression factor reaches a predetermined value; and

D. storing in the storage medium data indicative of the X, Y pairs of the subset.

9. A method for storing compressed data indicative of an input analog sinal and generating an output signal from the stored data corresponding to the input signal, comprising the steps of:

A. establishing an X-Y coordinate system with respect to the input analog signal, so that each point of the input analog signal can be described by an X, Y pair;

B. defining an elementary interval T along the X-axis, the X, Y pairs corresponding to the X values spaced at interval T constituting a first set of X, Y pairs, interval T being chosen such that the first set of X,Y pairs, if connected, would substantially reconstitute the input signal;

C. selecting from said first set of X, Y pairs, a subset of X, Y pairs to be stored in a storage medium, selection being carried out in accordance with steps (a)-(l), beginning with a first point X₀, Y₀ as follows;

(a) establish a tolerance arc/chord ratio;

(b) initialize calculation;

(c) establish a jump interval which corresponds to a jump of a predetermined number of elementary intervals T along the X-axis from X₀, Y₀ ;

(d) determine the length of a chord C₁ from the current point being tested to the point determined by the jump interval, and determine the lengths of chords c₁, c₂, etc. from one point to the next beginning with the current point being tested to the point determined by the jump interval, and determine ratio between the sum of chords c₁, c₂, etc. and chord c₁,

(e) compare the ratio determined in step (d) with the tolerance established in step (a), if the ratio determined in step (d) is larger than the tolerance established in step (a), go to step (f), but if the ratio determined in step (d) is smaller than the tolerance established in step (a), go to step (h);

(f) if the jump for which the ratio of the chords is greater than the tolerance is greater than 2, memorize the interval of the last jump for which the ratio of the chords is lower than the tolerance (noted at step (h)), however, if the jump is rejected, go to step (g),

(g) return to step (c)

(h) increase the jump interval established in step (c) by one and return to step (d),

(i) note the jump interval determined at step (f) and note the number of points processed up to now;

(j) if all points have not yet been processed, go to step (k), otherwise, go to step (1);

(k) return to step (c);

(l) determine a value of an ovreall compression factor by comparing the number of points selected for the subset with the total number of points based on the elementary interval T and if the compression factor is greater than a predetermined amount, such that there is memory in the storage medium available, go to step (m); and

(m) reduce the initial tolerance set at step (a) to increase the number of points selected for the subset and return to step (b), the process recommencing on the basis of the new tolerance and continuing until the compression factor reaches a predetermined value;

D. storing in the storage medium data indicative of the X, Y pairs of the subset; and

E. from the subset of X, Y pairs, generating an output analog signal substantially identical to the input analog signal by using parabolic interpolation to fit a curve to the various points of the subset.