Repetition Coded Compression for highly correlated image data
FIELD OF INVENTION
The present invention relates to a method and system of compressing image data and other highly correlated data streams.
BACKGROUND OF INVENTION
Image and data compression is of vital importance and has great significance in many practical applications. And to choose between Lossy compression and Lossless compression depends priniarily the application.
Some applications, where an automatic analysis is done on the image or data, using algorithms, require a perfectly lossless compression scheme so as to achieve zero errors in the automated analysis.
Generally Huffman coding and other Source coding techniques are used to achieve lossless compression of image data.
In certain other applications, the human eye visually analyzes images. Since the human eye is insensitive to certain patterns in the images, such patterns are discarded from the original images so as to yield good compression of data. These schemes are termed as 'Visually Lossless' compression schemes. This is not a perfectly reversible process. In other words, the de-compressed image data is different from the original image data. The degree of difference depends on the quality of compression and also the compression ratio.
Compression schemes based on Discrete Cosine Transforms and Wavelet. Transforms followed by Lossy Quantization of data are typical examples! of visually lossless scheme.
As a general rule, it is desirable to achieve the maximum compression ratio win zero or minimum possible loss in the quality of the image. At the same time, the complexity involved in the system and the power consumed by the image compression system are very critical parameters when it comes to a hardware based implementation.
Usually, the image compression is carried out in two steps. The first step is to use a pre-coding technique, which is mostly based on signal transformations; the second step would be to further compress the date values by standard source coding techniques like Huffman and Lempel-Ziv schemes.
The initial pre-coding step is the most critical and important operation in the entire image compression scheme. The complexity involved with DCT and Wavelet based transformations is very high because of the huge number of multiplications involved in the operations. This is illustrated in the following equation.

In addition to the huge number of multiplications involved in carrying out the above DCT equation, there also happens to be a zigzag rearrangement of the image data, which involves additional complexity. This clearly proves that the above mentioned conventional schemes for image compression are not very well suited for hardware based implementation.
So, the real requirement is a image compression system which does not involve any rigorous transforms and complex calculations. It also has to be memory efficient and power efficient The present invention called as Repetition Coded Compression (RCC) is ideally suited for the above mentioned requirements. It is based on a single mathematical operation and requires zero multiplications for its implementations. Ibis results in great amount of memory efficiency, power efficiency and speed in performing me
compression. Because of the single mathematical operation, involved for implementation of the present invention, the system is perfectly reversible sad absolutely lossless. This is very important for many applications, which demand zero loss. The compression ratios are significantly higher than the existing lossless compression schemes. But if the application permits a lossy compression system, me present invention can also cater to the lossy requirements, m this case a slight modification is done to me mathematical operation so that certain amount of loss is observed in the compression and thereby resulting in much higher compression ratios. This lossy compression' system would find great applications in entertainment and telecommnunication systems.
DISADVANTAGES OF CURRENT IMAGE COMPRESSION TECHNIQUES:
There ate various Image Compression Techniques. Familiar few are JPEG. JPEG-LS. JPEG-2000. CALIC. FRACTAL and RLE.
JPEG
JPEG compression is a trade-off between degree of compression, resultant image quality and time required for compression/decompression.
Blockiness results at high image compression ratios.
It produces poor image quality when compressing text or images containing sharp edges or lines.
Gibb's effect is the name given to this phenomenon where disturbances/ripples may be seen at the margins of objects with sharp borders.
It is not suitable for 2 bit black and white images.
It is not resolution independent Does not provide for scalability, where the image is displayed optimally depending on the resolution of the viewing device.
JPEC-LS
it does not provide support for scalability, error resilience or any such functionality. Blockmess still exist at higher compression ratios.
JPEO-LS does not offer any particular support for error resilience, besides restart markers, and has not been designed win it in mind.
JPEG-MH
Jpeg-2000 do not provide any truly substantial improvement in compression efficiency and are significantly more complex than JPEG, with me exception of JPEG-LS for lossless compression.
Complexity involved in JPEG-2000 is more for a fewer enhancement in the compression ratio and efficiency.
CALIC
Although CALIC provides the best performance in lossless compression, it cannot be used for progressive image transmission as it implements a predictive-based algorithm that can work only in lossless/nearly-lossless mode. Complexity and computational cost are high.
The results show that the choice of the "best" standard depends strongly on the application at hand.
EP 0387013 discloses an apparatus for encoding an N-dimensional array of data values representing the colour content of pixels of an image. The apparatus comprises a processor that is adapted to apply an invertable difference operator to an N-dimensional array of data values in one store in each of the N-dimensions starting from respective first positions in each dimension to generate an N-dimensional array of encoded data which is stored in another store.
SUMMARY OF INVENTION
According to an aspect of the invention, there is provided a method according to claim 1.
According to another aspect of the invention, there is provided an apparatus according to claim 5.
In accordance with a preferred aspect there is provided a method of compression of image data of an image wherein each element is compared with a previous element. If they are both equal, a first value is recorded. If they are not both equal, a second value is recorded. Each element may be a pixel. The first value may be a 1, and the second value may be a 0.
The first and second values may be stored in a bit plane. For a one-dimensional compression, a single bit plane may be used to store the values. However, for a two-dimensional compression, comparison may be in both horizontal and vertical directions, a separate bit plane being used for each direction.
The bit-planes for the horizontal and vertical directions may be combined by binary addition to for a repetition coded compression bit-plane. Combining may be by binary addition, only the second values being stored for lossless reconstruction of the image. The result of the combining may be repetition coded compression data values. All other image data values may be able to be reconstructed using the repetition coded compression data values, and the bit planes for the horizontal and vertical directions.
Storage in bit planes may be in a matrix. A single mathematical operation may be performed for each element.
In accordance with an embodiment of the invention, there is provided a system for repetition coded compression comprising a camera for capturing at least one image and for supplying digital data; a reshaping block for rearranging the digital data into a matrix of image data values; a processor for receiving the matrix of image data values and compressing the image data values to form compressed data; and a memory for storage of the compressed data.
The camera may be analog. An analog-to-digital converter may be used to convert the analog image to provide the digital data.
In accordance with an embodiment of the invention, there is provided a method for compression of an image comprising capturing the image and converting the image into digital form to provide digital data. The digital data is reshaped into a digital data matrix. Repetitions in the digital data matrix and encoded into a bit-plane index, and stored data values. The compressed data is stored in a storage memory.
The bit-planes may contain information regarding the repetitions along horizontal and vertical directions. There may be further included the combining of the horizontal and vertical bit-planes by a binary addition operation to give a repetition coded compression bit-plane. There may also be included comparing the repetition coded compression bit-plane with the digital data matrix to obtain final repetition coded compression data values.
The method may further include storing and archiving the repetition coded compression data values along with the horizontal and vertical bit-planes.
The compression is preferably lossless. Alternatively, the method a method may further include compression by comparison with a threshold value to achieve lossy compression and a significantly higher compression ratio.
The method may be used for an application selected from: medical image archiving, medical image transmission, database system, information technology, entertainment, communications applications, and wireless application, satellite imaging, remote sensing, and military applications.
OBJECTS OF INVENTION
It is the primary object of invention to invent a novel technique by way of Repetition Coded Compression for higbly correlated image data. It is another object of Invention to invent a system for Repetition Coded Compression for higher correlated image data. Another object of invention is to invent a system, which is versatile in application. Farther objects of the invention will be clear from the ensuing description.
BRIEF DESCRIPTION OF FIGURES
FigBTC-1
This figure illustrates the entire image compression system based on Repetition Coded Compression on a hardware implementation.
Figure-2
This figure is a sample image of the human brain, which is captured by magnetic resonance imaging (MRI), and this sample image would be used to demonstrate the compression achieved by Repetition Coded Compression system. It is a grayscale image.
Figure-3
This figure 200ms a small region from the sample MRI image of the human brain. This zoomed region would be used for demonstrating the compression system.
Figure-4
This figure shows that (he image is made up of lot of pixels in grayscale. Figure-5
This figure shows a 36-pixel region within the sample MRI image of the human brain.
Figure-6
This figure shows the ASCII value equivalent of me image data values, which are origmaBy used for data storage. Each value requires eight bits of data memory or in other words 1 byte of data memory. Currently the 36-pixcel region requires about 288 bits or 36 bytes of data memory. It would later be demonstrated that the data could be compressed and stored with only 112 bits.
Figaro-7
This figure shows the application of Repetition Coded Compression along the Horizontal Direction in the Image Matrix This results in the Horizontal bit-plane and also the horizontal values stored.
Figure-5
This figure shows the application or Repetition Coded Compression along the Vertical Direction in the Image Matrix. This result in the Vertical bit-plane and also the vertical values stored.
Figure-9
This figure shows the combination of Horizontal and Vertical bit-planes by a binary addition operation thereby resulting in only five zero values 'which correspond to the final values store from the original image matrix.
Flgare-10
This figure shows the total memory required for the 36-pixel region before and after applying repetition coded compression. The original memory requirement was 288 bits. After applying Repetition Coded Compression the memory required was 112 bits. This proves a great amount of compression achieved.
figure-11
This figure shows the application of Repetition Coded Compression to the entire image and the size is compressed to 44,000 bits from me original 188,000 bits.
Figure-12
This figure shows the complete principle for implementation of Repetition Coded Compression.
DETAILED DESCRIPTION OF INVENTION
Image data is a highly correlated one. This means that, the adjacent data values in an image are repetitive in nature. So, if it is possible to achieve some compression out of mis repetitive property of tbe image and then apply Huffman coding or other source coding schemes, the method would be very efficient
In mis Repetition Coded Compression algorithm, each dement is compared with the previous dement If both of mem are equal then a value of '1' is stored in a Bit-plane. Otherwise a value of '0* is stored in the Bit-plane. This different value is only stored in a matrix instead of storing all tbe repeating values.
In one-dimensional RCC Method only one bit-plane is used to code the repetition in the horizontal direction.
But in two~diinemional RCC method, two bit-planes an used to code the repetitions in both the horizontal and the vertical directions. This is more efficient and gives a better compression ratio.
This clearly proves that the compression system is implemented without any multiplications and complex transformations- It is purely based on a mathematical comparison of adjacent image data values. The comparison is performed between adjacent image data values in bom the horizontal as well as vertical directions. The bit-planes formed as a result of the above-mentioned comparison in the horizontal and vertical directions are respectively combined by a binary addition method. After this the resultant bit-plane positions are called as RCC bit-planes. The zero values in the RCC bit-plane are the only ones that are to be stored for lossless reconstruction of the original image. Such values corresponding to the some locations is the original image matrix as zeros in the RCC bit-plane are called as RCC data values. All the other image data values can be reconstructed by using the RCC data values and the horizontal vertical bit-planes.
In case of a lossy system of implementation, the adjacent pixels are not only compared for repetition, but also for the difference value. If the difference
value between adjacent pixels is lesser than a given arbitrary threshold value, then the two adjacent pixels are made as the same. This further increases the number of repetitions in the image data and therefore also increases the compression ratio after Repetition Coded Compression is applied. The value of the threshold can be varied according to the requirements of the particular application and system. The higher the threshold, the better the compression ratio and also higher loss in the quality of the reconstructed image.
Figure - 1 illustrates the entire image compression system based on Repetition Coded Compression on a hardware implementation. The raw analog image signals are captured by the camera and are converted into respective, digital data by a analog to digital converter. This digital data is rearranged into a matrix of image data values by a reshaping block. The reshaped image matrix is stored in the embedded chip, which performs the entire RCC system, This therefore gives the compressed ROC data values and also the bit-planes for storage, archival and future retrieval.
Figure - 2 is a sample image of the human brain which is captured by magnetic resonance imaging (MRI) and this sample image would be used to demonstrate the compression achieved by Repetition Coded Compression system. It is a grayscale image.
Figure - 3 zooms t small region from the sample MRI image of the human brain. This zoomed region would be used for demonstrating the compression system.
Figure - 4 shows that the image is made up of lot of pixels in grayscale. Figure - 5 shows a 36-pixel region within the sample MRI image of the human brain. Figure - 6 shows the ASCII value equivalent of the image data values which ate originally used for data storage. Each value requires eight bits of data memory or in other words 1 byte of data memory. Currently the 36-pixel region requires about 2X8 bits or 36 bytes of data memory. It would later be demonstrated mat me data could be compressed and stared with only 112 bits.
Figure - 7 shows the application of Repetition Coded Compression along me Horizontal Direction in the Image Matrix This results the Horizonta bit-plane and also the horizontal values stored. Figure - 8 shows the application of Repetition Coded Compression along the Vertical Direction in the Image Matrix. This result in the Vertical bit-plane and also the vertical values stored
Figure - 9 shows the combination of Horizontal and Vertical bit-planes by a binary addition operation thereby resulting in only five Zero values which correspond to me final values store from the original image matrix. Figure -10 shows the total memory required for the 36-pixel region before and after applying repetition coded compression. The original memory requirement was
288 bits. After applying Repetition Coded Compression (he memory required was 112 bits. This proves a great amount of compression achieved
Figure - 11 shows the application of Repetition Coded Compression to the entire image and the size is compressed to 44,000 bits from the original 188,000 bits. Figure - 12 shows the complete principle for implementation of Repetition Coded Compression. Tbe image matrix is encoded along the horizontal and vertical directions and tbe respective bit-planes are derived. Further compression is achieved by combining the horizontal and vertical bit-planes by a binary addition operation. This results in the RCC bit-plane, which is logically inverted and compared with (he original image matrix to obtain the final RCC data values. These RCC data values along with the Horizontal and Vertical bit-planes are stored in the data memory lor archival and Aiturt retrieval.
The coded data can be further compressed by Huffman coding. Thus compression of tbe image data is achieved using Repetition Coded Compression System. This System is easy to implement and is very last, as it does not make use of any complex transform techniques. The real advantage is that, this method can be used for any type of image file. Here tbe system is applied only for Grayscale images. But in future it can be applied to color images also.
In case of lossy system of implementation, the adjacent pixels are not only compared for repetition, but also for the difference value. If the difference value between adjacent pixels is lesser than a given arbitrary threshold value, then the two adjacent pixels are made as the same. This further increases the number of repetitions in the image data and therefore also increases the compression ratio after Repetition Coded Compression is applied. 'Jhe value of the threshold can be varied according to the requirements of the particular application and system. The higher (he threshold, the better the compression ratio and also higher loss in the quality of the reconstructed image.
This system of Repetition Coded Compression of images can be applied to fields like Medical Image Archiving and Transmission, Database Systems, Information Technology, Entertainment, Communications & Wireless Applications, Satellite Imaging Remote Sensing, Military Applications. The invention is described with reference to a specific embodiment and the said description will in no way limit the scope of the invention.
We claim
1. A method for compressing image data of an image, the method comprising the steps of:
generating a first bit-plane, each bit-plane value of the first bit-plane being associated with a corresponding image data value, by setting a bit-plane value of the first bit-plane to a first predetermined value if the corresponding image data value is equal to an image data value horizontally adjacent to the corresponding image data value within the image, and otherwise setting that bit-plane value to a second predetermined value, wherein the second predetermined value is different from the first predetermined value;
characterised in that the image is a greyscale image or a colour image and in that the method comprises the steps of:
generating a second bit-plane, each bit-plane value of the second bit-plane being associated with a corresponding image data value, by setting a bit-plane value of the second bit-plane to the first predetermined value if the corresponding image data value is equal to an image data value vertically adjacent to the corresponding image data value within the image, and otherwise setting that bit-plane value to the second predetermined value;
selecting the image data values for which the corresponding bit-plane value of the first bit-plane and the corresponding bit-plane value of the second bit-plane are both the second predetermined value; and
storing, as compression data values (22): the first bit-plane; the second bit-plane; and the image data values selected at the step of selecting.
2. A method according to claim 1, wherein each image data value corresponds to a pixel of the image.
3. A method according to any one of the preceding claims, wherein the first predetermined value is 1, and the second predetermined value is 0.
4. A method according to any one of the preceding claims, in which the step of storing comprises:
combining the first bit-plane and the second bit-plane by binary addition to form a third bit-plane; and
using the third bit-plane to identify the image data values to store as compression data values (22).
5. An apparatus for compressing image data of an image, the apparatus being arranged to carry out a method according to any one the preceding claims.
6. A camera (10) comprising an apparatus according to claim 5.
10. A system of repetition coded compression to archive the compressed image data values and also to retrieve the same to reconstruct the origin*) image.
11. A method of repetition coded compression for lossless compression of image data values.
12. A method of repetition coded compression for lossy compression by comparison with a said threshold value to achieve significantly higher compression ratio.
13. A system of repetition coded compression for implementation of the said compression method for various applications like Medical Image Archiving and Transmission, Database Systems, Information Technology, Entertainment, Communications &, Wireless Applications, Satellite Imaging, Remote Sensing, Military Applications.
14. A system of repetition coded compression for compressing image and other highly correlated data described in the description and illustrated by fee way of drawings.
15. A method of repetition coded compression for image compression as described in the description and illustrated by the way of drawings.
Dated this 22nJ day of September, 2004.
FOR MATRIXVIEW Ltd. By their Agent
SAIMA SAGHIR ANSARI) KRISHNA & SAURASTRI
This invention it related to both a process and a system for compressing highly correlated image data. The system for comperssing image and other highly correlated data comprises means far capturing the image, means for converting to digital form, means for reshaping the data, means for encoding the repetition, means for stroing the compressed data and means for retrieving the data. The method for compressing image and other highly correlated data comprises of steps like captnring the image, converting into digital form, reshaping the data into matrix form, encoding the repetitions into a bit-plane index and stored data valoes, storing the compressed data in storage memory and retrieving the data for decompression. The system and method for compressing image and other highly correlated data is described in the description and illustrated by the way of drawings.