Image analysis – Image compression or coding – Pyramid – hierarchy – or tree structure
Reexamination Certificate
1999-11-05
2002-04-16
Mehta, Bhavesh (Department: 2621)
Image analysis
Image compression or coding
Pyramid, hierarchy, or tree structure
C358S426010, C382S237000
Reexamination Certificate
active
06373988
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a method and a device for image and video compression for efficient storage or transmission of images, in particular sparse bi-level images.
BACKGROUND OF THE INVENTION AND PRIOR ART
In recent years there has been an increased interest in video telephony and video conferences. One problem associated with video communication is that it normally requires a large amount of bandwidth. Although there has been a tremendous development in transmission technologies and bandwidth is getting cheaper there still exists a need to code the information in an efficient way, and thereby reduce the amount of bandwidth required. In the future, video compression is also likely to become very important in wireless multimedia communication systems, since the bandwidth of the radio frequency spectrum is a limited resource.
There are basically two different strategies that can be employed in order to compress data. The first strategy is to remove statistical redundancy. This is done by choosing a more efficient representation for the data. If there is no statistical redundancy in the data that can be removed and there still is a need for further compression, some of the information from the original data must be removed.
This latter technique is called lossy compression and is common in coding of audio and video, where features of sound and images that humans find less perceptible are removed. Most video compression techniques consist of a number of filtering and transformation steps that remove redundancy or unimportant details from the data.
In some applications it is desired to efficiently compress two-dimensional bitmaps. Such an application can, for example, be when transmitting bit plane coded images plane by plane. A bitmap of an entire bit plane or a part thereof must then be further processed in order to get a compact bitstream that can be transmitted or stored in an efficient way.
There exists a number of standard methods for compressing bi-level images, e.g. ITU-T G4, ISO JBIG and Quadtree coding.
Also, U.S. Pat. No. 4,261,018 describes a method for progressively transmitting a binary black and white image. The method divides such a binary image into smaller and smaller blocks until such a block is found to be consisting of only white or only black elements. When a certain size of small block is reached no further sub-division is performed, and the small blocks still comprising both white and black elements are coded.
The problem with the above methods is that they are not optimized, and therefore provide relatively poor results, for a number of different output patterns produced by a number of different algorithms, for example the algorithm described in our co-pending International patent application PCT/SE96/00943.
SUMMARY OF THE INVENTION
It is an object of the present invention to overcome the problems associated with the prior art and to increase the efficiency and performance in coding of bi-level images or matrices.
This object is obtained with a method and a device for coding binary matrices, in particular sparse binary matrices, a matrix is gradually partitioned into sub-matrices. During the gradual partitioning the number of binary ones are counted for each resulting sub-matrix. If a resulting sub-matrix does not consist of mixed symbols no further partitioning of that sub-matrix is required. The counted number of binary ones for each sub-matrix is then coded and transmitted.
Hence, for a bi-level image the method can comprise the following steps:
The bi-level image is first transformed into a labelled binary tree. The tree is then traversed and the values in the nodes are efficiently entropy coded with arithmetic coding. Each node in the binary tree obtained represents a specific area of the image. The values in the nodes contain the number of white pixels in the corresponding area of the image.
Thus, for a bi-level image, for example a bitmap where white pixels are coded with the binary symbol 1 and a black pixels with the binary symbol 0, a scheme can be designed in the following manner.
First, the number of binary ones in the bitmap are counted and the resulting number is placed in the root node of a binary tree.
The bitmap is then divided into two parts and the number of binary ones in each of the two parts is counted. The sum of the two numbers thus obtained will be equal to the number in the previous root node.
The binary tree is then extended by placing these two numbers as leaves to the root node.
Each sub-image obtained in this manner, which is not completely filled with either binary ones or zeros, is then divided again and the above steps are performed again.
Finally, when all sub-images of the original bitmap only consist of either only black or white pixels, the binary tree representing such a division is coded.
Such coding can for example be performed by means of entropy coding the sum in the root node, and then entropy coding the leaves of the node. This is preferably done using arithmetic coding. Since the sum of the two leaves is known from their node only one of the two leaves needs to be coded. The input to the arithmetic coder is the symbol denoting the number and a distribution function suitable for the type of image to be coded.
The way of dividing the bitmap is preferably predefined and known both by the coder and the decoder. Since the partitioning in such a case is coded implicitly, no information regarding the partitioning needs to be transmitted to the decoder.
This way of coding bi-level images has been found to provide very good results in terms of compression ratio. It has also been found to be particularly suited for coding bi-level images where the number of whites or blacks are known to be very dominant, so called sparse bi-level images.
REFERENCES:
patent: 4261018 (1981-04-01), Knowlton
patent: 4858017 (1989-08-01), Torbey
patent: 5392133 (1995-02-01), Nakajima
patent: 5442458 (1995-08-01), Rabbani et al.
patent: 5881173 (1999-03-01), Ohmori
patent: 5978507 (1999-11-01), Shackleton et al.
patent: 0 701 375 (1996-03-01), None
patent: 2 725 060 (1996-03-01), None
Einarsson Torbjörn
Passaggio Filippo
Thorell Per
Bayat Ali
Mehta Bhavesh
Telefonaktiebolaget LM Ericsson
LandOfFree
Lossless image compression with tree coding does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Lossless image compression with tree coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lossless image compression with tree coding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2876593