Image analysis – Image compression or coding – Lossless compression
Reexamination Certificate
2000-12-05
2002-02-12
Au, Amelia M. (Department: 2623)
Image analysis
Image compression or coding
Lossless compression
C382S246000, C358S296000, C358S296000
Reexamination Certificate
active
06347158
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to a method for encoding digital information to be transmitted from a first device to a second device, wherein the digital information is mapped according to a map of rows and columns which define a plurality of cells and wherein each of said cells has a pixel value.
In particular this invention relates to a method for compressing bitmapped images in order to transmit them from a fast computing device (server). to a relatively slow computing device (client).
BACKGROUND TO THE INVENTION
It is known to encode a series of pixel values by using Runlength encoding (RLE) method.
RLE method takes raw data, as for example a series of pixel values, and encodes the series as a series of (count value) pairs so that long sequences of the same value can be represented by a relatively small amount of data. For example, the series of values: 12 12 12 100 100 100 100 100 30 30 4 4 4 4 4 4 4 4 4 4 4 4 4 4 could be run-length encoded as:
(3,12) (5,100) (2,30) (14,4)
Such RLE method is a standard technique developed in the 50s and used in many different areas including, for example, fax machines.
It is also known from background research (using both the World Wide Web and traditional journals and textbooks) that many ideas have been presented under the names ‘area coding’ and ‘two-dimensional run-length encoding’. Unfortunately, no specific implementation details or academic references are available from any of the sources consulted. Moreover, the sources indicate that other efforts in this area use complex recursive algorithms which emphasise optimal solutions at the cost of long runtimes, and also that these other efforts are not geared for the transmission of images for real-time rendering by relatively slow computers.
This invention addresses the problem of transmitting bitmapped images from a relatively fast computing device (the server) to a relatively slow computing device (the client) in such a way that these images can be rendered quickly on the client.
Therefore it is a primary object of the present invention to provide a method for encoding bitmapped information which is simple, effective and useful for relatively slow computers for rendering of two dimensional images.
THE INVENTION
According to the present invention, there is provided a method for encoding digital information characterised by the following steps:
starting from a predetermined first cell having a certain pixel value, to determine the largest area of cells, adjacent to said first cell, having the same pixel value as said first cell;
to generate a code indicative of the row-column position of said first cell, of the dimensions of said largest area and of said pixel value common to all the cells of said area;
to proceed to a second cell, adjacent to said area and having a pixel value different from the pixel value of said first cell; and
starting from said second cell, to determine another largest area of cells, adjacent to said second cell, having the same pixel value as said second cell;
to generate a code indicative of the row-column position of said second cell, of the dimensions of said largest area and of said pixel value common to all the cells of said area;
to repeat said steps until all cells of said digital information have been encoded.
According to a variant of the present invention, in an initial step, the most prevalent pixel value V is determined, either exactly by fully enumerating all pixel values, or probabilistically by enumerating a randomly selected subset of the pixel values. All cells with pixel value V are then ignored in the basic encoding process and the output is augmented with the value V and the overall dimensions of the input.
According to a second variant of the present invention, the background pixel value V is determined by is running the basic method of the invention and choosing the pixel value which appears in the greatest number of said largest areas, rather than simply the most prevalent value on a pixel-by-pixel basis.
REFERENCES:
patent: 5621819 (1997-04-01), Hozumi
patent: 5751850 (1998-05-01), Rindtorff
patent: 5754698 (1998-05-01), Suzuki et al.
patent: 5850485 (1998-12-01), Hart
patent: 5903670 (1999-05-01), Chun et al.
patent: 0 052 335 (1981-10-01), None
Mohamed, Sherif, A., and Fahmy, Moustafa M., “Binary Image Compression Using Efficient Partitioning Into Rectangular Regions”, pp. 1888-1893, IEEE Transactions On Communications, vol. 43, No. 5, May 1995.
Masayoshi Aoki, “Rectangular Region Coding For Image Data Compression”, Pattern Recognition, vol. 11, pp. 297-312, 1979.
Richardson Tristan John
Wood Kenneth Robert
AT&T Laboratories - Cambridge Limited
Au Amelia M.
Banner & Witcoff , Ltd.
Dastouri Mehrdad
LandOfFree
Method for encoding digital information 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 for encoding digital information, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for encoding digital information will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2947773