Image analysis – Image compression or coding – Adaptive coding
Reexamination Certificate
1994-12-02
2001-01-30
Lee, Cheukfan (Department: 2722)
Image analysis
Image compression or coding
Adaptive coding
C382S245000, C382S233000, C358S438000, C358S426010
Reexamination Certificate
active
06181825
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to real time facsimile image compression. More specifically, the present invention relates to a plurality of efficient methods for the real-time encoding of bi-level graphics, e.g., facsimile images. The inventive methods are particularly suited for mobile communication applications using a 2-dimensional bit-reduction, e.g., decimation, scheme. The methods developed are particularly applicable to the coding of handwritten and typed-text and are suitable for incorporation in the middle, rather than the terminating-points, of a communications network. An apparatus specifically adapted to perform the enumerated methods is also disclosed.
BACKGROUND OF THE INVENTION
The emerging use of low-rate coding and digital transmission in mobile satellite communications and the increasing use of facsimile services have identified the desirability for visual service transparency over the same very narrow-band circuits. The economic viability of such a service, however, rests on the capability of introducing further image message compression, either in real-time or off-line during a so-called store-and-forward operation. In addition to the economic side, however, long document transmission times negatively impact the customer perceived quality of service in that, over narrow-band circuits, several minutes might be required for the transmission of documents that would normally need only seconds when transmitted through the public switch telephone network. In order to achieve these objectives, some form of image compression over and above what is provided by traditional Group 3 facsimile is needed.
Of general interest are U.S. Pat. No. 4,779,266 to Chung et al., which discloses methods and corresponding circuitry for encoding and decoding information with code patterns which engender the two-state equivalent of electronic orthogonal coding. These special code patterns, referred to as optimizing orthogonal codes, are useful in system having only two signal propagation states, e.g., optical processors and U.S. Pat. No. 4,695,971 to Reimann, which discloses circuitry for rapidly determining the greatest difference among three binary numerical values which undertakes a classification and coding of the maximum difference within a number of different numerical ranges.
References of limited interest include U.S. Pat. No. 3,971,88 to Ching et al., which discloses a synchronization system for variable length encoded signals, U.S. Pat. No. 3,938,085 to Battail, which discloses a transmission system including a transmitting station and a receiving station for operating with a systematic recurrent code, and U.S. Pat. No. 3,927,372 to Zschunke, which discloses techniques for improving the reproduction of amplitude jumps in a differential pulse code modulation (DPCM) system based on the use of maximum difference value code words.
Currently there are several methods in use for encoding bi-level graphics. These include:
a. One-dimensional Huffman Coding, which is used to encode colored (black or white) strips of picture elements (pixels) when an image is raster-scanned and digitized. A well known algorithm belonging to this class of techniques is the 1-Dimensional Run-Length Coding (RLC) which has become an international standard. See CCITT Recommendation T.4., “Standardization of Group 3 Facsimile Apparatus for Document Transmissions”, Melbourne 1988, Fascicle VI1.3 Volume VII, Pages 21-47. The 1-Dimensional RLC consists of a Huffman Code that has been suitably modified to increase its robustness in the presence of telephone network-type of impairments. The 1-Dimensional RLC is a powerful technique that permits the lossless coding of bi-level images and is able to achieve a bit-rate requirement reduction on the order of 10:1, depending on the statistical content of the image encoded. However, since group 3 facsimile messages are already encoded using this technique there can be little, if any, benefit derived by further compressing such images in the network using the same, or a modified version of this approach.
b. To increase the compression achievable, a two dimensional version of the 1-Dimensional RLC technique has also been developed. See CCITT Recommendation T.4. In the 2-Dimensional RLC method, only the first scan-line of image information is encoded in accordance to the 1-Dimensional RLC. Subsequently, the differences between adjacent lines, rather than the actual scan-lines, are encoded using a technique that is essentially the same as 1-Dimensional RLC. The 2-Dimensional RLC is also a loss-less coding method. However, because of its increased image redundancy removal, it is more susceptible to telephone network-type of transmission impairments. As a result, 1-Dimensional RLC of the actual scan-lines is used every few lines to assure that re-synchronization can be established even when some of the encoded information has been corrupted. As a result, its performance is somewhat limited. Furthermore, since, as stated earlier, group 3 facsimile messages are already encoded using this standardized technique, there can be little additional benefit realized, e.g., an additional 20%, by further compressing such images in the network using a 2-dimensional Huffman coding approach, or a variant thereof.
c. If the communications channel can be assumed to be error free, e.g., when automatic repeat request procedures are employed, a slightly more efficient method of 2-D RLC can be derived. In this method, all image scan-lines are coded on an adjacent line differential basis and 1-Dimensional RLC is not repeated for re-synchronization. This method is somewhat more efficient in that a compression ratios of the order of 20:1 can be achieved. However, the underlying error-free channel assumption is noted. This method has also been standardized, and is covered by, for example, CCITT Recommendation T.6, entitled “Facsimile Coding Schemes and Coding Control Functions for Group 4 Facsimile Apparatus” (Melbourne 1988, Fascicle VII.3, Volume VII).
d. Other techniques for the coding of facsimile images have also been used. See K. Knowlton, “Progressive Transmission of Gray-Scale and Binary Images by Simple, Efficient and Lossless Coding Scheme”, Proceedings of IEEE, pp. 885-896 (July 1980), and N. S Jayant et al., “Digital Coding of Waveforms”, Prentice Hall (1984). Some of these employ transform domain techniques and promise to be effective, but primarily only when dealing with graphical information such as gray level, or highly detailed images. As a result, such methods have not demonstrated their optimal abilities when coding bi-level handwritten graphics for mobile communication applications.
e. Another technique which has proven to be powerful is based on the segmentation of an image into many sub-images and in subsequently matching the content of these sub-images by elements drawn from a code-book of elementary images. The process is completed by transmitting over the communications channel a code-word representing the identity of the elementary image most closely resembling the image's sub-image. Such techniques combine pattern recognition principles and vector quantization and have demonstrated that significant compression ratios can be achieved, e.g., more that 100:1, if the code-book used is well suited to the image contention a microscope scale). See O. Johnsen et al., “Coding of Two-Level Pictures by Pattern Matching and Substitution”, The Bell System Technical Journal, Vol. 62, No. 8, pp. 2513-2545 (October 1983) as well as Super Fax Compression, COMSAT Laboratories Final Report under Contract MCS-10 (December 1991). Despite the impressive compression ability of these techniques, some limitations should be noted when the image structure is not well matched to the codebook contents. First, the compression ratios realized are significantly lower than 100:1. Second, these techniques are information lossy, i.e., the reconstructed image quality is degraded when compared to the original image. In particular, if the image structure is not well matche
Corcoran Franklin L.
Dimolitsas Spiros S.
Ragland Roderick J.
Tender Neil H.
Comsat Corporation
Lee Cheukfan
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Methods for performing 2-dimensional maximum differences... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for performing 2-dimensional maximum differences..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for performing 2-dimensional maximum differences... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2460823