Image analysis – Image compression or coding
Reexamination Certificate
1998-12-11
2001-04-03
Couso, Jose L. (Department: 2724)
Image analysis
Image compression or coding
C382S233000
Reexamination Certificate
active
06212301
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to systems and methods for data compression, and more particularly, to systems and methods for compressing a digital image.
BACKGROUND OF THE INVENTION
Historically, the transmission of digital images over computer networks has long been a part of modem informational technology. Special graphic formats have been developed to provide the ability to store digital images on storage media and to transmit them over computer networks. These graphic formats typically provide for compressing the image so that the image takes up less space when stored and/or takes less time to transmit over a network. Techniques have been sought and developed for the efficient compression of images in a progressive manner; that is, first an image with limited resolution is displayed, then the same image is displayed in successive stages with progressively greater resolution. Some graphic formats provide for progressive image transmission but typically for color images only. For instance, one format is based on a standard format from JPEG (Joint Photographic Experts Group). The JPEG format allows progressive transmission of color images up to about 16 million colors. Another format is the interlaced GIF (Graphics Interchange Format) created by Compuserve, Inc. The GIF format also allows progressive transmission of color images of 256 colors and even bi-level or bi-tonal images, but the compression methods do not provide for a very high level of compression, thus causing network traffic and delays when compressed images are transmitted over a network.
A very high level of compression for bi-level images is reached in Group
4
compression based on the ITU-T Group
4
specification from the ITU (International Telecommunication Union), formerly CCITT (International Consultative Committee for Telegraph and Telephone). The Group
4
compression scheme is used, for instance, in the TIFF (Tagged Image File Format) graphic format developed by Aldus Corporation and widely used for storing documents as digital images. The Group
4
compression scheme does not allow for progressive transmission but only for sequential transmission of lines in an image. This is due to a restriction on the Group
4
compression scheme whereby the compression of each row or line of the image currently being coded is based on the contents of the previous row (the reference line). Thus, the Group
4
coding scheme requires the compression of sequential lines in an image.
Therefore, one object of the invention is to provide methods for the high compression of bi-tonal and other images in a progressive manner and for on-demand enhancement of the displayed images. Another object is to provide a compression technique suitable for efficient, progressive display of images over a global network. Another object is to provide an interlacing approach to progressive compression based on multiple compression methods, including a modified Group
4
method, and adaptable to different levels of progressive compression.
SUMMARY OF THE INVENTION
The invention achieves the above objectives by providing methods for compressing a digital image in a progressive manner using the most efficient of several compression methods and transmitting a portion of the compressed image over a computer network, receiving it, decompressing it, and providing a displayed image representative of the original image.
In one aspect, the invention is understood as a method for compressing an image comprising lines of data, including the steps of (a) defining a segment of s consecutive lines in the image; (b) determining a selected line in the segment as a starting line; (c) determining a plurality of lines, beginning with the starting line, by selecting additional lines spaced by multiples of s from the starting line until no further of the additional lines can be selected from the image for the plurality of lines; (d) compressing each of the plurality of lines; (e) selecting a longest range of lines yet to be selected in the segment; (f) determining a middle line equally distant from the beginning and the end of the longest range of lines; (g) setting the middle line as the starting line; and (h) repeating steps (c) through (g) recursively until a predetermined limit of lines has been compressed.
In one embodiment, defining the segment includes setting s to a power of 2. In another embodiment, defining the segment includes defining the segment as the first s lines in the image. In an additional embodiment, determining the selected line includes determining a first line in the segment as the starting line.
In another embodiment, compressing each of the plurality of lines includes compressing each of the plurality of lines using a modified Group
4
coding scheme using a nearest previous selected line as a reference line.
In a further embodiment, determining a longest range of lines includes selecting a first longest range of lines. In an additional embodiment, the predetermined limit is based on a predetermined percentage of the total number of the lines in the image, and in a further embodiment, the predetermined percentage is preferably in the range of about 12.5% to about 50%.
In another embodiment, the method further includes transmitting a compressed plurality of lines using a communications media; receiving the compressed plurality of lines from the communications media; decompressing the compressed plurality of lines; and displaying the compressed plurality of lines as a displayed image representative of the image.
In other embodiments, compressing each of the plurality of lines includes providing a plurality of compression methods; compressing each of the plurality of lines by each of the plurality of compression methods; determining, for each line, a highest compression for the line by a selected one of the plurality of compression methods; and storing, for each of the lines, a highest compression line. In one embodiment, compressing each of the plurality of lines comprises compressing each of the plurality of lines using a Group
3
coding scheme and a modified Group
4
coding scheme. In another embodiment, storing a highest compression line includes affixing to the highest compression line an indicia identifying the selected one of the plurality of compression methods providing the highest compression. In a further embodiment, determining the highest compression for the line comprises selecting the highest compression providing a minimal bit length for the line.
REFERENCES:
patent: 4028731 (1977-06-01), Arps et al.
patent: 4222076 (1980-09-01), Knowlton
patent: 4345245 (1982-08-01), Vella et al.
patent: 4464650 (1984-08-01), Eastman et al.
patent: 4558302 (1985-12-01), Welch
patent: 4602273 (1986-07-01), Carlson
patent: 4628534 (1986-12-01), Marshall
patent: 4701745 (1987-10-01), Waterworth
patent: 4814746 (1989-03-01), Miller et al.
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5001478 (1991-03-01), Nagy
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5051745 (1991-09-01), Katz
patent: 5140321 (1992-08-01), Jung
patent: 5155484 (1992-10-01), Chambers, IV
patent: 5159667 (1992-10-01), Borrey et al.
patent: 5170266 (1992-12-01), Marsh et al.
patent: 5390262 (1995-02-01), Pope
patent: 5497434 (1996-03-01), Wilson
patent: 5623556 (1997-04-01), Murayama et al.
patent: 5724070 (1998-03-01), Denninghoff et al.
CCITT T42-Dimensional Compression Standard, http://www.rasip.fer.hr/research/c...Igorithms/adv/fakscomp/index3.html, (Copyright 1997), pp. 1-4.
The Design of Interactive Computational Media, Department of Computer Science University of Toronto, http://www/dgp.toronto.edu/csc318/week9.htm, (Winter, 1997), pp. 1-8.
Fascimile Coding Shemes and Coding Control Functions for Group 4 Fascimile Apparatus, ITU-T Recommendation T-6, International Telecommunication Union, (1988), 11 pages.
Graphics Interchange Format(sm), Version 89a, (GIF89a) CompuServe Incorporated, http://tronche.com/computer-graphics/gif/gif89a.htm1#appendix-e, (Jul. 31, 1990), pp. 1-29.
Image Data Compression, Chapter12. http://cs.sungshin.ac.k
Dedkov Anatholy F.
Warner Scott J.
Accusoft Corporation
Couso Jose L.
Do Anh Hong
Testa Hurwitz & Thibeault LLP
LandOfFree
Systems and methods for digital image compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for digital image compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for digital image compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2463206