1. Field of the Invention
This invention relates to improved apparatus for error correction of digital data, and in particular to correction of digital data representing a pictorial image.
2. Description Relative to the Prior Art
While much digital data, such as that derived from computation and general data processing has no redundancy, data generated by digital processing of images is characterized by substantial amounts of redundant information. The established method of converting images into digital data entails projecting the image onto a sensor having an analog output, and then scanning the sensor and digitizing its output. The redundancy inherent in the image is carried over into the resultant digital data stream; the digital values themselves exhibiting the redundancy of the original pictorial image.
Referring to FIG. 1, a scene 10 is scanned in horizontal segments by an optical scanning device 12 whose output is a raster 14 containing the pictorial information in the form of electrical analog signals. The scanning device 12 may be any one of the optical scanners known in the art; for example, the laser scanner, kinescope scanner, or CCD sensor and associated scanning circuits. The electrical signals are then sequentially digitized by means of a sampling analog to digital converter 16 whose output is the digital representation of the image intensity on a line by line basis. Such image samples are conventionally referred to as "pixels". Generally, the digitizer 16 output comprises the pixel value expressed in binary form wherein eight bits per sample correspond to a 256 level gray scale of image intensity. A digital eight bit sample is usually designated as a "byte", however, a byte may be defined to contain any discrete number of bits. This binary coded representation of the digital values of the samples is called "pulse code modulation", or PCM. Usually the image is digitized to allow either electromagnetic transmission or magnetic recording of the PCM encoded samples.
In FIG. 1, the line 18 represents a left-to-right scan across the "sky" portion 19 of the scene 10, and it will be appreciated that the image intensity across such a scan will be essentially constant. Similarly, the intensity of the scan of the line 20 across the sky remains essentially constant until the edge of the "cloud" 22 is encountered, and then the image intensity changes to another essentially constant value for the duration of the scan across the "cloud". Upon completion of the scan of the cloud, the intensity and the sample values then revert to the values representative of the "sky" 19. Such scans result in sample values that are highly redundant because there is little detail in the portions of the scene being sampled. On the other hand, the detailed portions of the scene which consist of rapidly changing intensities result in samples of limited redundancy; during the scan 23 across the "tree" 25, rapidly varying sample values of intensity are generated. Thus, the data is characterized by non-redundant bytes derived from scans of detailed portions of the image such as the "tree" 25, and by redundant byte values derived from scans of the "sky" 19 or the "cloud" 22 where the intensity changes little, if at all.
The present inventor's copending application, Ser. No. 023,327, U.S. Pat. No. 4,761,782 focuses attention on the use of image redundancy for error correction after the transmission or storage of the digitized image data. Aberrations such as fading in an electro-magnetic transmission channel, or dropouts in a magnetic tape storage channel cause signal loss and upon recovery of the data, attendant errors. These errors result in easily discernible, detrimental streaking in the recovered image. The teaching of the above copending application ameliorates this problem by utilizing the available image redundancy as the basis for error correction in the recovered image data. It teaches the grouping of the digitized bytes representative of an image into data blocks whereby the redundant information present in the image becomes replicated in the data block and results in some of the bytes having essentially the same, or nearly the same, digital values as other bytes within the same block. Prior to transmission or storage, each block is analyzed for redundant sample values, i.e. values which are either identical or which only vary within predetermined boundaries, and check bits are accordingly affixed to the block. The configuration of the check bits defines the nature and the extent of the redundancy in the bytes comprising the block. The block containing data and check bits is then transmitted or stored. The recovered data, which has been subject to induced errors during transmission or storage, is analyzed to ascertain whether the bytes comprising the block still contain the same redundancy specified by the affixed check bits. If an error has occurred, the resultant redundancy of the received data will generally be reduced; at least one of the recovered pixels in the block will be different from what it originally was due to the error. The above mentioned copending application teaches re-encoding the received data to derive new check bits based on the received data which are then compared to the original check bits as received. This comparison generates a "syndrome" having the value "0" if the check bits derived from the received data are the same as the original check bits, and having the value "1" if the re-encoded check bits do not agree with the original check bits. A syndrome of value 1 flags an error and the fact that the data in the block has changed during transmission. As described in the copending application, if an error has occurred, the received data bytes are then compared among themselves to ascertain which data pattern is characteristic of the majority of received bytes. This majority pattern is assumed to be the correct pattern for all the bytes of the block including the bytes in error. The bytes in error are then corrected in accordance with the instructions inherent in the configuration of the original check bits. The correction restores the data patterns to their original configuration, and, attendantly, restores the amount of redundancy that was originally present in the block.
The check bits are not derived from the actual values of the data bits as is characteristic of many codes known in the art. The check bits reflect the fact that "patterns" of data bits within the block are the same, but the check bits do not explicitly define the structure of these patterns.
In considering the teaching of the prior art, it is advantageous to provide a listing of various check bit symbols used in describing the technique.
Sx=check bit x derived from data before transmission, PA1 SxR=received value of check bit Sx after transmission PA1 Sx*=re-encoded value of Sx derived from data as received after transmission PA1 SCx=value of syndrome calculated from SxR and Sx*, where for m check bits PA1 x=0,1,2 . . . m-1. PA1 127=01111111 PA1 128=10000000 PA1 132=10000100 PA1 129=10000001 PA1 127=01111111.
A prior art embodiment employs a two bit check pattern, S1, S0, which is attached to each block of n pixels to provide an 8n+2 bit block. Check bits are assigned in accordance with the following rules:
TABLE I ______________________________________ S1 S0 CONDITION ______________________________________ 1 1 Three most significant bits of all n pixels form indentical patterns 1 0 Only the two most significant bits of all n pixels form identical patterns 0 1 Only the most significant bits of all n pixels are the same 0 0 None of the above ______________________________________
The above assignment of check bits reflects the degree of redundancy carried by the three most significant bits of the n pixels comprising a block. For example, the check bits 1,1 indicate that the n pixels have the highest redundancy in their three most significant bits, i.e. the three most significant bit patterns for all n pixels are the same. On the other hand, the check bits 0,0 indicate that there is no redundancy among the most significant bits of the n pixels, i.e. all of the patterns are different. The intermediate cases of 1,0 and 0,1 reflect in-between conditions of redundancy.
It will be appreciated that the prior art technique depends upon the image redundancy as expressed in the three most significant binary bits of the pixel binary representation. Because of the structure of binary representation, it is possible that certain values of redundancy will fail to encode in a manner correctly representing the redundancy value. For example, a block may consist of digitized image values of 127, 128, 132, 129, 127. Encoded into an eight bit binary representation, these values are:
While it is clear by consideration of the actual magnitudes of these pixels that the information is highly redundant, neither the three most significant bits of the binary values of the five pixels are the same, nor are the two most significant bits, nor are the most significant bits themselves, the same. Due solely to the structure of binary representation, these five pixels appear to be completely non-redundant rather than highly redundant. This occurs at the transition between the numbers 127 and 128 in binary representation because all the bits switch in value with the result that values just above the transition point and values just below it have no similarity in the high order bit positions. A similar "boundary" problem also occurs for pixels having digitized binary values in the region of 256, and 64. It will be appreciated that because of this characteristic large undetected errors may occur at these boundary points. For example, it is clear that if the most significant bit of the binary number 128 is subject to error and changes from 1 to 0, the resultant pixel value instead of being 128 is 0; a level change of 50 percent of full scale, (i.e. 256), that is not corrected in the prior art due to coding failure at the boundary.
An analysis of typical images containing redundancy shows that from 7 to 15 percent of blocks may fail to incorporate a block's true redundancy value when utilizing the techniques of the prior art. This is partially due to the redundancy characteristics of the image and partially due to the above described boundary problem. The mere occurrence of pixel values which straddle a boundary region is not sufficient in itself to cause errors in the reproduced image. It is necessary that a transmission error or, say, a magnetic tape storage dropout error simultaneously occur with the incidence of the pixel value in the boundary region. Because the joint probability of these two conditions occurring simultaneously is very small, acceptable error correction in many applications is provided by the technique of the prior art. For the processing of the highest quality images wherein the occurrence of any large pixel errors, even if rare, is unacceptable, additional correcting power is required. The present invention provides that power by completely eliminating the source of the errors due to the boundary problem.