Image analysis – Image compression or coding – Predictive coding
Reexamination Certificate
1998-05-18
2003-01-28
Chen, Wenpeng (Department: 2624)
Image analysis
Image compression or coding
Predictive coding
C382S239000, C382S130000, C382S132000
Reexamination Certificate
active
06512853
ABSTRACT:
The present invention relates to a method and apparatus for compressing digital image data.
Images are commonly stored and transmitted in digital form. Where such images include greyscale, the value of the greyscale of each pixel is provided in digital form, typically, in binary code. In images where a large range of greyscale values are required, for example, in X-rays, it is not unusual to code the greyscale levels in eight bit binary codes, thus giving 256 levels of greyscale. In general, such images are provided in raster format which comprise a plurality of horizontal scan lines, each line containing a plurality of individuals pixels, each of which is assigned a greyscale value which specifies the level of greyscale corresponding to that point in the image. Typically, the level of greyscale is defined in each pixel by an eight to twelve bit code. Because of the large number of bits which are used for defining the level of greyscale in each pixel, an image stored in raster format requires a relatively large storage capacity, and additionally, takes up a lot of bandwidth on communication channels for transmission of the image. Even in the case of a black and white image with greyscale, the storage capacity is high. In the case of colour images, where three primary colours and the corresponding intensities of the respective colours are required to define each pixel of a colour image, the storage capacity is increased by a factor of three. Various attempts have been made to compress such images, however, such attempts to date suffer from a number of disadvantages. Firstly, many compression methods are not lossless, in other words, between compression and decompression, part of the digital data making up the image is lost, and an accurate reconstruction of the image after decompression cannot be prepared. While in some applications such losses are acceptable, they are entirely unacceptable in many cases, typically, in images relating to medicine and diagnostic medicine, for example, X-rays and the like. Image compression systems which are essentially lossless suffer from the disadvantage that the compression ratio is relatively low, and thus in many cases, little saving on the storage space or the bandwidth occupied by such images in the transmission thereof is gained. Even where compression ratios are reasonable, such image compression systems tend to be relatively complex, complicated and time-consuming, and also may require large storage space to effect the compression. Typical image compression systems are described in U.S. Pat. No. 4,809,350, European Patent Specification No. 0,479,563 and European Patent Specification No. 0,536,801. The image compression methods described in these three specifications suffer from one or more of the disadvantages discussed above.
There is therefore a need for a method for compressing digital image data which overcomes the problems of known digital image data systems and which provides lossless or effectively lossless compression, while at the same time providing reasonable compression.
The present invention is directed towards providing such a method and apparatus for compressing digital image data.
The term “region” as used throughout this specification and the claims means one pixel or a group of adjacent pixels.
According to the invention, there is provided a method for compressing digital image data, the method comprising the steps of
sequentially scanning a plurality of regions of the image data and determining the actual value of the data in respective regions,
predicting the value of image data in at least some of the regions based on the determined actual values of some of the already scanned regions which are adjacent the region for which the image data is being predicted,
comparing the predicted value with the corresponding actual value of each region for which a prediction is made, and
computing the value of the difference between the respective predicted values and the corresponding actual values, and
compressing the respective difference values,
characterised in that
at least three predictions of data value are made for each region for which a prediction is being made, the predicted value which produces the median difference value of the difference values between the respective three predicted values and the actual value is selected, and the median difference value is compressed for each region for which a prediction is made, the respective predicted values for each region being based on the actual value or values of a different scanned region or regions and/or a different combination or combinations of scanned regions to those for which the others of the predictions for that region are based.
In one aspect of the invention, the digital image data is scanned region by region as a matrix array of regions.
In another aspect of the invention, one of the predictions of data value of a region for which a prediction is being made is based on the data value of the adjacent region in the column in which the region for which the prediction is being made lies.
In another aspect of the invention, one of the predictions of data value of a region for which a prediction is being made is based on the data value of the adjacent region in the row in which the region for which the prediction is being made lies.
Preferably, one of the predictions of data value of a region for which a prediction is being made is based on the gradient of data values of two regions approaching the region for which the prediction is being made. Advantageously, the prediction of the data value takes into account the slope of the gradient.
In one aspect of the invention, one of the two regions on which a prediction is based lies closer to the region for which the prediction is being made than the other of the said two regions, and the region of the said two regions which is closest to the region for which the prediction is being made is weighted.
In another aspect of the invention, one of the predictions of data value of a region for which a prediction is being made is based on the data values of three regions which are adjacent to the region for which the prediction is being made, one of the said regions lying in the same column, and the other of said regions lying in the same row as the region for which the prediction is being made, the third region being located between the said other two regions and being used for determining the gradient of the data values between the respective said other two regions and the region for which the prediction is being made.
Preferably, a prediction of the data value of every region of the digital image is made.
In one aspect of the invention, the respective median difference values are compressed by encoding the median difference values with respective variable length codes, unique codes being assigned to the respective median difference values.
Preferably, the shortest code is assigned to the most frequently occurring median difference value, and the longest code is assigned to the least frequently occurring median difference value.
Advantageously, the codes are different for the positive and negative values of the same absolute median difference values.
In one aspect of the invention, the codes assigned to the median difference values are binary codes.
Advantageously, the bit length of the longest code for the median difference values does not exceed the bit length of the data value of any region.
In one aspect of the invention, the actual data of a region is retained instead of the median difference value for that region should the median difference value for that region exceed a predetermined value. Preferably, a first flag means is set to indicate that the data following the flag means is the actual data value of the region.
In another aspect of the invention, a second flag means is set to indicate a run of actual data values where the median difference values of a run of regions exceeds a predetermined value. Preferably, the number of actual data values included in the run is associated with the second flag means. Advantage
Kennedy Jonathan Marshall Thomas
Kennedy Nicholas Paul
Kennedy Simon Frederick
Marshall David
Barkfort Limited
Chen Wenpeng
Nixon & Vanderhye P.C.
LandOfFree
Method and apparatus for compressing digital image data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for compressing digital image data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for compressing digital image data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3065059