Method and apparatus for data compression

Abstract

A method and apparatus is shown for compressing a stream of data for storage, transmission or display while preserving maximum, minimum, and other valuable data features. The method and apparatus utilize a first and a second pair of error boundary lines to generate best fit trend segments of the data stream. The first and second pair of error boundary lines are modified as data samples of the data stream are received such that all of the data samples are either on one of the first and second pair of error boundary lines or in an area between the first and second pair of error boundary lines. The first and second pair of error boundary lines are then used to generate the best fit trend segments.

I claim: 
     
       1. A method for compressing a data stream representative of measured values by a transducer having data samples with at least first and second degrees of freedom, the method comprising the steps of: (A) receiving first and second data samples of the data stream from the transducer;   (B) generating a first pair and a second pair of error boundaries, each of the first pair and the second pair including an upper boundary and a lower boundary separated by a predetermined error value, wherein the upper boundary of the first pair includes the second data sample, the lower boundary of the first pair includes the first data sample, the upper boundary of the second pair includes the first data sample, and the lower boundary of the second pair includes the second data sample;   (C) receiving a next data sample of the data stream from the transducer;   (D) discarding the next data sample and repeating step (C) when a value of the next data sample is greater than the lower boundary of the second pair of error boundaries and is less than the upper boundary of the first pair of error boundaries;   (E) recognizing a segment end condition when the value of the next data sample is greater than the upper boundary of the second pair of error boundaries or the value of the next data sample is less than the lower boundary of the first pair of error boundaries;   (F) if a segment end condition does not exist: i) modifying at least one of the first and second pairs of error boundaries such that each boundary of the first pair and the second pair of error boundaries includes at least one previous data sample and such that for each one of the pair of error boundaries, all previous data samples are either contained within an area between the upper boundary and the lower boundary of the one of the pair of error boundaries or are located on one of the upper boundary and the lower boundary of the one of the pair of error boundaries;   ii) continuing from step (C); and     (G) if a segment end condition does exist, generating a best fit line segment of the data samples received in steps (A) and (C) thereby compressing a segment of the data stream.   
     
     
       2. The method of claim 1, wherein the step of modifying at least one of the first and second pairs of error boundaries includes steps of: generating a convex hull defining an area, the convex hull having vertex points corresponding to the next data sample and at least two data samples received previous to the next data sample, the area of the convex hull and the vertex points including the next data sample and all previous data samples of the data stream;   modifying the first pair of error boundaries such that the upper boundary of the first pair includes the next data sample, the lower boundary of the first pair includes a first lower vertex point of the vertex points, and the upper boundary and lower boundary of the first pair are separated by the predetermined error value.   
     
     
       3. The method of claim 2, wherein the step of modifying further includes steps of: determining whether a value of any one of the vertex points of the convex hull is less than the lower boundary of the first pair of error boundaries; and   if the value of any of the vertex points is less than the lower boundary of the first pair, adjusting the upper boundary and the lower boundary such that the upper boundary of the first pair includes the next data sample, the lower boundary of the first pair includes a second lower vertex point of the vertex points, and the upper boundary and the lower boundary of the first pair are separated by the predetermined error value.   
     
     
       4. The method of claim 3, wherein the step of modifying further includes a step of: adjusting the second pair of error boundaries such that the lower boundary of the second pair includes the next data sample, the upper boundary of the second pair includes a first upper vertex point of the vertex points, and the upper boundary and the lower boundary of the second pair are separated by the predetermined error value.   
     
     
       5. The method of claim 4, wherein the step of modifying further includes steps of: determining whether the value of any one of the vertex points of the convex hull is greater than the upper boundary of the second pair of error boundaries; and   if the value of any of the vertex points is greater than the upper boundary of the second pair, adjusting the upper boundary and the lower boundary of the second pair such that the lower boundary of the second pair includes the next data sample, the upper boundary of the second pair includes a second upper vertex point of the vertex points, and the upper boundary and the lower boundary of the second pair are separated by the predetermined error value.   
     
     
       6. The method of claim 5, wherein step (G) includes steps of: determining whether the first pair of error boundaries is equivalent to the second pair of error boundaries;   if the first pair is equivalent to the second pair, generating a best fit line segment, wherein the best fit line segment is equal to a set of points equidistant from the upper boundary and the lower boundary of the first pair of error boundaries;   if the first pair is not equivalent to the second pair: i) selecting an interpolation data point to replace the next data sample, the interpolation data point being selected such that a modification of at least one of the first pair and the second pair of error boundaries to include the interpolation point, results in the first pair of error boundaries being equivalent to the second pair of error boundaries; and   ii) generating a best fit line segment, wherein the best fit line segment is equal to a set of points equidistant from the upper boundary and the lower boundary of the first pair of error boundaries.     
     
     
       7. The method of claim 6, further comprising a step of: storing data representative of the best fit line segment.   
     
     
       8. The method of claim 7, wherein the data representative of the best fit line segment includes: a data point of one of the first and second pair of error boundaries; an indication of whether the data point is a data point of the upper boundary or the lower boundary of the one of the first pair and the second pair of error boundaries; and a distance from the best fit line segment to a previous best fit line segment. 
     
     
       9. The method of claim 8, wherein step (F) includes a step of: modifying the at least one of the first and second pairs of error boundaries only when a distance from the upper boundary to the lower boundary of the at least one of the first and second pairs of error boundaries increases by a predetermined factor as a result of the modification.   
     
     
       10. The method of claim 1, wherein step (G) includes steps of: determining whether the first pair of error boundaries is equivalent to the second pair of error boundaries;   if the first pair is equivalent to the second pair, generating a best fit line segment, wherein the best fit line segment is equal to a set of points equidistant from the upper boundary and the lower boundary of the first pair of error boundaries;   if the first pair is not equivalent to the second pair: i) selecting an interpolation data point to replace the next data sample, the interpolation data point being selected such that a modification of at least one of the first pair and the second pair of error boundaries to include the interpolation point, results in the first pair of error boundaries being equivalent to the second pair of error boundaries; and   ii) generating a best fit line segment, wherein the best fit line segment is equal to the set of points equidistant from the upper boundary and the lower boundary of the first pair of error boundaries.     
     
     
       11. The method of claim 1, further comprising a step of: storing data representative of the best fit line segment.   
     
     
       12. The method of claim 1, further comprising a step of: transmitting data representative of the best fit line segment.   
     
     
       13. The method of claim 12, wherein the data representative of the best fit line segment includes: a data point of one of the first and second pair of error boundaries; an indication of whether the data point is a data point of the upper boundary or the lower boundary of the one of the first pair and the second pair of error boundaries; and a distance from the best fit segment to a previous best fit line segment. 
     
     
       14. The method of claim 1, wherein step (F) includes a step of: modifying the at least one of the first and second pairs of error boundaries only when a distance from the upper boundary to the lower boundary of the at least one of the first and second pairs of error boundaries increases by a predetermined factor as a result of the modification.   
     
     
       15. A computer storage module incorporating stored instructions for execution on a general purpose computer to compress a data stream having data samples including first and second data samples having first and second degree of freedom, the general purpose computer having an input to receive the data samples of the data stream and an output to provide an output signal representative of best fit line segments of the data stream, the storage module comprising: a first set of instructions executable by the computer to generate a first pair and a second pair of boundaries, each of the first pair and the second pair including an upper boundary and a lower boundary separated by a predetermined error value, wherein the upper boundary of the first pair includes the second data sample, the lower boundary of the first pair includes the first data sample, the upper boundary of the second pair includes the first data sample, and the lower boundary of the second pair includes the second data sample;   a second set of instructions executable by the computer to discard a next data sample when a value of the next data sample is greater than the lower boundary of the second pair of error boundaries and less than the upper boundary of the first pair of error boundaries;   a third set of instructions executable by the computer to recognize a segment end condition when the value of the next data sample is greater than the upper boundary of the second pair of error boundaries or the value of the next data sample is less than the lower boundary of the first pair of error boundaries;   a fourth set of instructions executable by the computer, if a segment end condition does not exist, to modify at least one of the first and second pairs of error boundaries such that each boundary of the first pair and the second pair of error boundaries includes at least one of the data samples and such that for each one of the pair of error boundaries, a value of each data sample received by the computer since a last segment end condition is not greater than the upper boundary and not less than the lower boundary of the one of the pair of error boundaries; and   a fifth set of instructions executable by the computer to, if a segment end condition does exist, generate a best fit line segment of all data samples of the data stream received by the computer since a last segment end condition and prior to the segment end condition thereby compressing segments of the data stream.   
     
     
       16. The computer storage module of claim 15, wherein the fourth set of instructions further includes instructions executable by the computer to: generate a convex hull defining an area, the convex hull having vertex points corresponding to the next data sample and at least two data samples received by the computer before the next data sample, the area of the convex hull and the vertex points including the next data sample and all data samples received by the computer since the last segment condition; and   adjust the first pair of error boundaries such that the value of the next data sample is not greater than the upper boundary of the first pair and the value of the next data sample is not less than the lower boundary of the first pair, the upper boundary and the lower boundary of the first pair are separated by the predetermined error value, and the lower boundary of the first pair includes a first lower vertex point of the vertex points.   
     
     
       17. The computer storage module of claim 16, wherein the fourth set of instructions further includes instructions executable by the computer to: determine whether a value of any one of the vertex points of the convex hull is less than the lower boundary of the first pair of error boundaries; and   if the value of any one of the vertex points is less than the lower boundary of the first pair, adjust the upper boundary and the lower boundary such that the upper boundary of the first pair includes the next data sample, the lower boundary of the first pair includes a second lower vertex point of the vertex points, and the upper boundary and the lower boundary of the first pair are separated by the predetermined error value.   
     
     
       18. The computer storage module of claim 15, wherein the fifth set of instructions further includes instructions executable by the computer to: determine whether the first pair of error boundaries is equivalent to the second pair of error boundaries; and   if the first pair is equivalent to the second pair, generate a best fit line segment, wherein the best fit line segment is equal to a set of points equidistant from the upper boundary and the lower boundary of the first pair of error boundaries;   if the first pair is not equivalent to the second pair, select an interpolation data point to replace the next data sample, the interpolation data point being selected such that a modification of at least one of the first pair and the second pair of error boundaries to include the interpolation point, results in the first pair of error boundaries being equivalent to the second pair of error boundaries; and   generate a best fit line segment, wherein the best fit line segment is equal to the set of points equidistant from the upper boundary and the lower boundary of the first pair of error boundaries.   
     
     
       19. The computer storage module of claim 18, further comprising a sixth set of instructions executable by the computer to: store data representative of the best fit line segment.   
     
     
       20. The computer storage module of claim 19, wherein the data representative of the best fit line segment includes: a data point of one of the first and second pair of error boundaries; an indication of whether the data point is a data point of one of the upper boundary and the lower boundary of the one of the first pair and the second pair of error boundaries; and a distance from the best fit line segment to a previous best fit line segment. 
     
     
       21. The computer storage module of claim 15, wherein the fourth set of instructions further includes instructions executable by the computer to: modify the at least one of the first and second pairs of error boundaries only when a distance from the upper boundary to the lower boundary of the one of the first and second pairs of error boundaries increases by a predetermined factor as a result of the modification.   
     
     
       22. An apparatus for compressing a data stream into a series of best fit trend line segments, the data stream having a plurality of data samples, the apparatus comprising: means for receiving data samples of the plurality of data samples;   means for generating a first pair and a second pair of parallel error boundaries, each of the first pair and the second pair including an upper boundary and a lower boundary separated by a predetermined error value, wherein the upper boundary of the first pair includes a second data sample, the lower boundary of the first pair includes a first data sample, the upper boundary of the second pair includes the first data sample, and the lower boundary of the second pair includes the second data sample;   means for discarding data samples in an area between the upper boundary of the first pair of error boundaries and the lower boundary of the second pair of error boundaries;   means for modifying at least one of the first and second pairs of error boundaries such that each line of the first pair and the second pair of error boundaries includes at least one data sample received by the apparatus and such that for each one of the pair of error boundaries, all data samples of the plurality of data samples received by the apparatus since a last segment end condition are either contained within an area between the upper boundary and the lower boundary of the one of the pair of error boundaries or are located on one of the upper boundary and the lower boundary;   means for generating a best fit line segment of data samples received by the means for receiving and thereby compressing the data stream.   
     
     
       23. The apparatus of claim 22, wherein the means for modifying includes: means for generating a convex hull defining an area, the convex hull having vertex points corresponding to data samples of the plurality of data samples, the area of the convex hull and the vertex points including all data samples of the data stream received by the apparatus since the last segment end condition;   means for adjusting the first pair of error boundaries such that the upper boundary of the first pair includes a latest data sample, the lower boundary of the first pair includes a first lower vertex point of the vertex points, and the upper boundary and lower boundary of the first pair are separated by the predetermined error value.   
     
     
       24. The apparatus of claim 23, wherein the means for modifying further includes: means for determining whether any of the vertex points of the convex hull are below the lower boundary of the first pair of error boundaries; and   means for pivoting and rolling the upper boundary and the lower boundary such that the upper boundary of the first pair includes the latest data sample, the lower boundary of the first pair includes a second lower vertex point of the vertex points, and the upper boundary and the lower boundary of the first pair are separated by the predetermined error value.   
     
     
       25. The method of claim 22, wherein an out of bounds data sample corresponds to a data sample that lies outside an area between the upper boundary of the first pair and the lower boundary of the second pair and wherein the means for generating a best fit line includes: means for selecting an interpolation data point to replace an out of bounds data sample, the interpolation data point being selected such that a modification of at least one of the first pair and the second pair of error boundaries to include the interpolation point, results in the first pair of error boundaries being equivalent to the second pair of error boundaries; and   means for generating a best fit trend line segment, wherein the best fit trend line segment is equal to a set of points having an equal distance from the upper boundary and the lower boundary of the first pair of error boundaries.   
     
     
       26. The apparatus of claim 22, further comprising: means for storing data representative of the best fit trend line segment.   
     
     
       27. The apparatus of claim 26, wherein the data representative of the best fit line segment includes: a data point of one of the first and second pair of error boundaries; an indication of whether the data point is a data point of one of the upper boundary and the lower boundary of the one of the first pair and the second pair of error boundaries; and a distance from the best fit line segment to a previous best fit line segment. 
     
     
       28. The apparatus of claim 22, further comprising: sampling means for sampling an analog stream of data to generate the data samples and provide the data samples to the means for receiving.   
     
     
       29. The apparatus of claim 28, wherein the sampling means includes: means for sampling the analog stream at a selected sample rate to provide a predetermined time interval between each of the data samples.   
     
     
       30. The apparatus of claim 28, wherein each of the data samples has a first degree of freedom and a second degree of freedom, and wherein the first degree of freedom of each data sample is stored as an incremental value from the first degree of freedom of a previous data sample. 
     
     
       31. The apparatus of claim 22, further comprising a display, coupled to the means for generating a best fit line, that displays the data stream as a series of best fit lines.