Data compression system

• US 4,809,350 A
• Filed: 01/30/1987
• Issued: 02/28/1989
• Est. Priority Date: 02/10/1986
• Status: Expired due to Term

• Current Assignee: Elscint Limited (Elbit Imaging Limited)
• Original Assignee: Elscint Limited (Elbit Imaging Limited)
• Inventors: Niv, Ron, Shimoni, Yair
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US07/008,768
• Time in Patent Office: 760 Days
• Field of Search: 382/56, 358/135, 358/136, 358/260, 358/262, 358/133
• US Class Current: 382/238
• CPC Class Codes: H04N 19/00 Methods or arrangements for coding, decoding, compressing or decompressing digital video signals

Abstract

A data compression system for use in processing diagnostic image data which uses a predictor to predict future data. The actual data is subtracted from the predicted value to obtain data related difference values. The difference values are coded by coding the most prevalent difference by a code other than the least bit code but further coding the most prevalent number by string length coding, with the most common being the coded with a least bit code, and also coding the next most common difference with a least bit code and the subsequent most prevalent differences with sequential least bit codes to provide compression ratios of over 3:1. A procedure for finding the best predictor in noisy data is provided.

Claims

1. A data compression method for compressing acquired image data to make more efficient use of memory space and to expedite the transfer of said data;

said method comprising the steps of;

aquiring image data,

using a scan geometry for scanning the aquired image data region by region in an orderly fashion to obtain at least some of the data to be compressed, said scan geometry being determined by the image data aquisition system used for aquiring the image data,

predicting further data to be compressed based on the scanned aquired image data to obtain predicted data,

obtaining difference data from differences between said predicted further data and further aquired data,

compressing the difference data by encoding the difference data to be compressed using a string length code arrangment for the most prevalent difference data,

encoding the second most prevalent data to be compressed with a replacement code that is the shortest,

encoding the sequentially next most prevalent difference data with the shortest replacement code not previously used,

the step of predicting further data comprising the steps of;

using the scan geometry used for scanning the aquired image data to scan only data regions that have not previously been scanned and are contiguous to scanned data regions,

choosing a path from available paths from all of the contiguous scanned data regions that terminate in the region being scanned for predicting purposes,

selecting path points on said chosen path that come closer to the center point of the region being scanned that path points of any other available path,

determining the values of the selected path points, and

determining the predicted value of the region being scanned using the determined values of the selected path points.

2. A data compression method for use with the data compression method of claim 1 said decompression method comprising the steps of:

recalling some of the data to be decompressed,

decompressing said recalled data,

predicting further data to be decompressed based on the decompressed recalled data, wherein the predicting step is identical to said predicting step of the compression method,

recalling further data to be decompressed,

using an inverse string-length code arrangement and an inverse efficient replacement code arrangement based on said recalled further data to obtain a difference data set and the size of said difference data set, and

adding said difference data set to a corresponding set of predicted further data, said set of predicted further data being the same size as said difference data set, to enable obtaining a set of further decompressed data.

3. The method of claim 2 wherein the second code comprises using the string length step of scanning the difference data to find strings of a specific value, determining the lengths of said strings and replacing said strings by a combination of said string lengths and said specific value.

4. The method of claim 3 wherein the string length code is an efficient replacement code of the string lengths.

5. The method of claim 2 including the step of suppressing noise in no data regions of the difference data to be compressed.

6. The method of claim 5 including the step of obtaining differences of the data to be compressed after the said suppressing of the noise.

7. The method of claim 5 wherein, the difference data to be compressed is digitized and stored in matrix elements and wherein the step of suppressing noise includes assigning data values to the no data matrix elements.

8. The method of claim 2 including the step of using look-up tables to obtain coded values.

9. The method of claim 2 including the step of programming said codes to obtain coded values.

10. The method of claim 2 including the step of using dedicated circuitry to supply said coded values.

11. The method of claim 1 wherein the step of determining the value of the region being scanned comprises extrapolating the value of the region being scanned from the determined values of the path points.

12. The method of claim 1 wherein the step of determining the value of the region being scanned comprises setting up a prediction formula using the values of the path points in the prediction formula to obtain the value of the region being scanned.

13. The method of claim 12 wherein the method of setting up the prediction formula comprises the steps of:

determining the noise level of the acquired data, and

selecting a polynomial order based on the noise level.

14. The method of claim 13 wherein the step of determining the value of the selected path points comprises:

interpolating the values of the selected path points using the values of basis points, said basis points being the known values of center points of said scanned data regions.

15. An image data compression system for compressing image data to make more efficient use of memory space and to expedite the transfer of said image data said system comprising:

acquisition means for acquiring image data to be compressed,

means for predicting the data to be acquired,

means for obtaining difference values between the acquired data and the predicted data,

means for encoding the difference values using string-length coding for the most prevalent difference values,

means for encoding the second most prevalent difference value to be compressed using a shortest replacement code,

means for encoding each sequentially next most prevalent difference values using the shortest replacement code not previously used;

said means for predicting comprising;

means for predicting data values only for regions that have not previously been scanned and are contiguous to scanned data regions,

means for choosing a path from available paths from all of said contiguous scanned data regions, said path terminating in a region being scanned,

means for specifying path points on said path, said path points coming closest to the center point of the region being scanned than path points on any other available path,

means for determining the values of the specified path points from the data of the previously scanned regions, and

means for predicting the value of the region being scanned from the determined values of the specified path points.

16. A data decompression system for use with the system of claim 15 said system comprising:

means for recalling some of the data to be decompressed,

means for decompressing said recalled data,

means for predicting further data to be decompressed based on the already decompressed recalled data,

means for using an inverse efficient replacement code and an inverse string-length code based on the recalled further data,

means further for using said used codes to obtain a difference data set and the size of said difference data set, and

means for adding said difference data set to a corresponding set of predicted further data, said set of predicted further data being of the same size as said difference set to enable obtaining a set of further decompressed data.

17. The system of claim 15 wherein the means for obtaining the inverse string-length coded values comprises means for scanning the data to determine strings of a specific value and the lengths of the strings, and

means for replacing said strings with a combination of said specific value and said string lengths.

18. The system of claim 17 wherein the said specific value is the most prevelant value.

19. The system of claim 18 including means for suppressing noise in no data regions of the data to be compressed.

20. The system of claim 19 including means for obtaining differences operated subsequent to the operation of the means for suppressing of noise.

21. The system of claim 19, including means for digitizing the data to be compressed, means for storing said digitized data in matrix elements, and wherein the means for suppressing noise includes means for assigning data values to the no data elements of said matrix.

22. The system of claim 15 including look-up tables to obtain coded values.

23. The system of claim 15 including means for programming said codes to obtain coded values.

24. The system of claim 15 including dedicated circuitry to supply said coded values.

25. The system of claim 15 wherein the means predicting the value of the region being scanned comprises means for extrapolating the value of the region being scanned from the determined values of the path points.

26. The system of claim 15 wherein the means for predicting the value of the region being scanned comprises:

computation means using the values of the path points in a prediction formula to obtain the predicted values of the region being scanned.

27. The system of claim 26 including means for setting up the prediction formula comprising:

means for selecting a polynomial order of said formula based on the noise level of the system.

28. The system of claim 27 wherein the means for determining the value of the selected path points comprises:

means for interpolating the value of the selected path points using the values of basis points, said basis points being the known values of the regions of center points of said scanned acquired data.