Image analysis – Image compression or coding
Reexamination Certificate
1999-03-25
2002-11-05
Grant, II, Jerome (Department: 2624)
Image analysis
Image compression or coding
C358S296000
Reexamination Certificate
active
06477277
ABSTRACT:
This invention relates to a data encoding system, and more particularly but not exclusively to an encoding system for encoding, transmitting and decoding image data.
Encoding systems for encoding, transmitting and decoding image data, for example facsimile systems, are well known in the prior art. These systems comprise transceivers which are linkable to one another through one or more serial communication channels, for example a telephone link. In one of these systems, an image to be communicated from a first transceiver is conveyed therefrom as a stream of information through one or more channels to a second transceiver whereat the image is received and then reproduced. The image is partitioned at the first transceiver into a series of parallel image bands which are scanned to provide a sequence of data packets in which each band is represented by a corresponding data packet. End of line (EOL) data are inserted between each of these packets to punctuate them and thereby provide composite encoded data suitable for transmission. The packets are not each individually identifiable by an address reference defining their corresponding band position within the image but are arranged relative to one another in a sequence in which the bands are abuttable to form the image. In the sequence, the packets are said to be relatively addressed by their position therein.
These systems suffer from a problem that relatively addressed data loses spatial accuracy if EOL data has been lost as a result of data corruption. Moreover, synchronisation problems may also result when EOL data following corrupted data are not reliably recognised. Data corruption may render a received image unintelligible.
The probability of a data corruption occurring in the systems described above increases as transmission duration increases. For example, an image communicated by facsimile at standard CCITT (Consultative Committee on International Telegraph and Telephone) resolution may involve transfer of data representing approximately two million bits of information. This is described in a book “FAX: Facsimile Technology and Applications Handbook” ISBN 0 89006 495 4 McConnell, Bodson and Schaphorst 1992. If these data are communicated in uncompressed form through a communication channel at a rate of 2400 bits per second (bps), data transmission duration will be approximately fourteen minutes. Data corruption during such an interval is likely to occur in systems in which fading and interference phenomena are experienced over shorter timescales than this.
Restricted communication bandwidth limiting information communication rates to approximately 2400 bps is particularly characteristic of high frequency (HF) radio systems which operate by emitting and receiving electromagnetic radiation in a frequency range of 3 to 30 MHz. Such radio systems are prone to transmission problems such as interference, signal fading and multipath effects which may result in errors being introduced into information conveyed through them; this is particularly pertinent when transmission durations are long. Despite the problems, HF radio systems provide an important advantage of beyond line of sight communication and are presently employed, for example, in maritime applications. Techniques for coping with the transmission problems are clearly important for such systems.
Current compression techniques for reducing problems of data corruption when transmitting packets of data through error prone channels rely on using compression algorithms for decreasing redundancy in the data, thereby reducing data transmission duration . Robustness of compressed data thereby generated to transmission errors is further increased by adding error control code data to it. Such techniques decrease image transmission time although inclusion of the control code data tends to offset data size reduction benefits arising from data compression. Although such techniques are effective for removing occasional errors occurring during data transmission, a problem arises when errors occur more frequently than the control codes are able to compensate. This results in extensive damage to the compressed data on account of its reduced redundancy. These excess errors render an image conveyed to the receiving transceiver possibly unintelligible and, at best, flawed.
The error control codes described above include forward error correction (FEC) codes incorporating parity bits. Automatic repeat request (ARQ) codes are sent in reply from a second transceiver receiving data to a first transceiver transmitting the data when the data are corrupted during transmission to instruct the first transceiver to retransmit the data. In the case of prior art facsimile systems, ARQ codes returned when transmission errors have occurred invoke retransmission of an entire image to which the ARQ codes relate. Retransmission of parts of the image is not possible in these prior art systems because they are devoid of facilities for relating isolated retransmitted parts of the image together.
In a modified Huffman encoding technique, for example as used for CCITT group
3
standard facsimile, each data packet is encoded into a series of variable length codewords separated by a robust EOL code. This is described in a publication “International digital facsimile coding standards” Hunter and Robinson, Proc. IEEE-68, pp. 854-867. Although this Huffman technique which employs relative addressing is effective at limiting error propagation from one packet to another and providing data compression, it is frequently unable to provide error free conveyed images when bit error rates (BERs) of 2% or more are experienced during image transmission.
As an alternative to the Huffman technique described above, a SEA-RL (Sequential Edge Addressing—Run Length) encoding technique involves:
(i) representing an image as a two colour (black-white) image in a two dimensional array of pixel elements;
(ii) partitioning the array into bands of single pixel element width and encoding each band in terms of colour transitions and run lengths relative to a reference end of the band to provide a corresponding data packet; and
(iii) assembling the packets into a sequence of data wherein each packet is separated from its successive packet by EOL code data.
The SEA-RL technique was developed for improving transmission reliability when transmitting low resolution documents using very high frequency (VHF) radio communication apparatus arranged to transmit and receive modulated electromagnetic radiation in a frequency range of 30 MHz to 300 MHz. In the technique, run lengths correspond to sizes of groups of consecutive similar colour image pixel elements which are present in the bands. The data packets are not individually addressed in the sequence of data because relative addressing is employed where the data packets are arranged in the sequence in an order in which their respective bands are abuttable to form the image. A description of the SEA-RL technique is provided in a publication “Joint source-channel coding for raster document transmission over mobile radio” by Wyrwas and Farrell, IEE Proceedings, Vol. 136, Pt. I, No. 6 pp. 375-380, December 1989. The SEA-RL technique differs from other encoding techniques described above in that absolute rather than relative addressing of groups of image pixels is employed within each packet of data. Moreover, the technique is limited to communicating two tone black-white images only.
In the SEA-RL technique, EOL code data which punctuate data packets in a sequence are susceptible to transmission errors; corruption of EOL data may result in loss of individual packets or possibly loss of two successive packets. Due to their importance, EOL code data are therefore included in duplicate into the sequence. In a situation where one or more of the packets become corrupted in the sequence, entire retransmission of image data is required because relative addressing is employed for the packets. The SEA-RL technique is, in common with alternative techniques described above, based upon encoding an image as a se
Arthur Paul C.
Chippendale Paul
Honary Bahram
Maundrell Melville J.
Sargeant Ian
Grant II Jerome
Nixon & Vanderhye P.C.
Qinetiq Limited
LandOfFree
Data encoding system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data encoding system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data encoding system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2990333