Filmless Digital Camera With Selective Image Compression

1. Field of the Invention

This invention relates to a filmless digital camera in which the data representing the images are compressed in such manner as to minimize the creation of artifacts from bright spots or abrupt change in gray level while conserving data storage capacity. More particularly, the invention relates to a filmless camera having a storage capacity for a predetermined number of images and in which the compression algorithm is automatically modified to obtain the maximum fidelity in the reconstituted images while making full utilization of the storage capacity.

2. Description of Related Art

Many different algorithms for compressing image data have been devised to minimize required memory capaicty with minimum loss of image quality. One widely accepted algorithm is the Discrete Cosine Transform (DCT). For many images in different applications that compression method provides acceptable results. However, certain images upon reconstitution display artifacts in portions of the image adjacent to abrupt changes in the gray level. Many other compression methods have been devised but generally have a fixed compression procedure that is applied uniformly to all parts of the image.

Most compression techniques achieve a fairly uniform image quality level by allowing the compression ratio to change. Such techniques are inappropriate for a filmless digital camera that has a fixed amount of digital memory for image storage. The photographer would not know how many pictures could be taken before filling the memory of the camera.

One variation of the Discrete Cosine Transform is known as Adaptive DCT. The goal of the adaptation is to make the quality more uniform over the area of the image. However, an adaptive DCT would aggravate, rather than alleviate, the problem of variable compression ratio.

U.S. Pat. No. 5,034,804 to Sasaki et al. describes a digital camera in which image data from an A/D converter are recorded on a memory card serving as a recording medium. No method for controlling the quantity of recorded data for each image while providing maximum picture quality is suggested. Because of the use of replaceable memory cards, there is no need to tailor the size of the image data to record a predetermined number of images in a fixed memory base.

U.S. Pat. No. 5,016,107 to Sasson et al. also discloses the use of a memory card for recording digital image data. Again, there is no common fixed-limit memory for recording a fixed number of images. No selective compression of the images is disclosed.

U.S. Pat. No. 5,027,214 to Fujimori describes an imaging system in which a data compressing section causes variable-length encoding data compression of the digital signal. The compression results in a variable amount of digital data for different images. These data are recorded in a memory having a fixed capacity. Accordingly, the number of images that can be recorded is not known in advance, because the amount of data resulting from the compression varies from image to image. Computations provided by the Fujimori structure enables the photographer to know whether an electronic image to be newly photographed can be recorded or not. This is a device for telling the photographer he has, in effect, run out of film. Fujimori does not adjust the data recorded from the images in order to fit a predetermined number of images into the available memory. In the Fujimori patent the image data are first pre-processed using a differential pulse code that is followed by a compression step using the discrete cosine transform. Every image is processed in this manner. There is no disclosure of performing a compression operation and making a decision dependent upon the results of that compression to control the manner in which each particular image is to be treated in order to provide maximum quality while accommodating a pre-set number of images in the fixed memory. Fujimori does not suggest using the number of non-zero digital coefficients for selecting subsequent compression procedures.

U.S. Pat. No. 5,068,744 to Ito describes a still camera recording procedure in which the image is divided into data blocks and each block is individually recorded. Picture components, such as the AC and DC components, are individually recorded.

None of the earlier patents discloses the computation of a measure bearing a pre-established relation to the creation of artifacts upon the decompression of the image data as here proposed by applicant.

In a digital filmless camera it is important for the user to known in advance exactly how many images can be recorded on the available memory. To record a practical number of images, it is necessary to compress the data so that less memory is required for each image. If one of the standard compression methods is chosen, it must be selected so that any image can be recorded on a predetermined percentage of the total memory. However, the compression that can be applied to an image, while attaining an acceptable size, varies from image to image.

In accordance with the present invention, each image is individually evaluated and the compression applied in such manner as to retain maximum quality while fitting the data into the pre-assigned memory. Such a camera may have a stated image storage capacity for a designated number of images, for example, thirty-two gray scale images. Conventional compression techniques achieve a uniform image quality, but have widely varying compression ratios depending upon the content of the image. If one of those methods is used, the Quality Factor is fixed and must be set so that even in the case of the lowest compression ratio, no image requires more than the fixed memory allocated to each image to avoid the possibility of exceeding the memory capacity before all of the exposures have been made. The result is that images of a kind that could have been compressed at a higher Quality Factor and still fit within the allocated memory are compressed to the lower fixed quality required by the worst case image. In other words, applying the same compression steps to each image, irrespective of the character of the image, results in inefficient use of the memory.

One family of compression techniques achieves most of the compression by selectively reducing the precision of either the phase or amplitude of the high spatial frequency components of the image. One of the most common techniques in this family is the Discrete Cosine Transform. The "Pyramid Transform" is another example in this family.

The family of compression techniques that includes the DCT in general result in higher perceived quality for a given compression ratio than other usual techniques. However, the DCT family can create objectionable artifacts in portions of an image where the exact phase and amplitude of the high frequency components are important. The worst example is a single bright pixel. Other examples are a bright line, or sharp edge between bright and dark areas. Because these examples have significant energy at all frequencies, the DCT family also achieves a low compression ratio.

By counting the number of non-zero high frequency coefficients after quantization, it is possible to detect blocks that are likely to create artifacts when compressed by the DCT family of compression techniques. To reduce the generation of artifacts, an alternative method of compression that is not in the DCT family, may be selectively applied to these blocks.

For example, in one embodiment of this invention, the image data are generated as analog data and converted into digital data. These data representing one complete image, are divided into small discrete blocks. Each of these blocks is compressed using one of the standard compression methods such as the discrete cosine transform (DCT). Each block of compressed data is then examined and a determination made as to the probability of artifacts resulting from such compression. If the probability of artifacts is above a pre-set standard, the block of data is compressed by an alternate method, for example, by differential coding. This may result in an increased memory requirement for the blocks recorded by the alternate method. The blocks of data that are below the artifact threshold are recorded by the first compression method. Each block of data is coded to indicate the method by which it is compressed.

Prior to actual recording, the Quality Factor is adjusted to achieve a uniform image size. The Quality Factor sets the compression parameters used by both compression techniques and by the process selecting the compression techniques. The image is compressed with a trial Quality Factor. If the image uses significantly less memory than the amount allocated for each image, the Quality Factor is increased. If the image uses significantly more memory than the amount allocated for each image, the Quality Factor is decreased. This process is repeated until the compressed image is an acceptable size. By this means, the highest quality images are attained consistent with the allocated memory requirements.

In summary, (a) a Quality Factor may be used to select compression parameters; (b) for a given Quality Factor, the compressed image size may vary greatly, typically by a factor of three to one, based on the content of the particular image; (c) the Quality Factor may be adjusted to achieve an acceptable image size for any particular image; also (d) the results of the DCT compression for any block of image data may be used to estimate the probability of the generation of artifacts; and (e) an alternative compression method may be applied to those blocks with a probability of artifacts above a threshold selected by the Quality Factor. Based on these facts, the multiple compression and Quality Factor selection processes of the present invention provide optimum image quality while insuring that a predetermined number of images will fit in a predetermined amount of memory and at the same time reducing the probability of artifacts from DCT compression.

FIG. 1 is a block diagram of the primary elements of a camera embodying the invention;

FIG. 2 is an illustration of one block of data from an image showing the scanning sequence; and

FIG. 3 is a block diagram illustrating the mode of operation for compressing each image.

In this example, the digitized image from the detector of a digital camera is stored and compressed to a predetermined size range by adjusting an overall Quality Factor. The Quality Factor is determined by performing trial compressions at different Quality Factors. During compression, two techniques are available. The first technique is from the DCT family and the second is not from the DCT family. Artifacts from points, lines and edges, normally produced by DCT-like compression are suppressed by selectively switching to the non-DCT-like compression. The Quality Factor selects the quantization parameters for compression and for the threshold that selects the compression technique.

In particular, in this example the image data is divided into blocks of typically 8 by 8 pixels. A first compression of each image data block is by the DCT method. After quantization using the compression parameters selected from a table by the current Quality Factor, the number of non-zero high frequency components is counted. In this example, high frequency coefficients are all coefficients except the four by four block of coefficients nearest to the DC coefficient. If this number exceeds a threshold value, also selected from a table by the current Quality Factor, the block is recompressed using an alternative compression that may require more space in the memory but will not produce objectionable artifacts in the decompressed image. Run-length encoding of quantized pixel to pixel differences, usually referred to as differential encoding, is a suitable alternative compression technique. The compression technique used for each block is indicated by the addition of a single bit at the start of the compressed block. For the purposes of this description and the claims, the expression "alternate compression" means compression by an algorithm other than one belonging to the DCT family.

The compression parameters for the DCT compression set the quantization level for each DCT coefficient. These quantization levels are set by sensitivity studies, such as those published in the JPEG compression standard. To form the table of compression parameters, the quantization levels may be uniformly scaled. The threshold value used to control the switch to alternative compression may typically range from 4 to 24 non-zero coefficients, as the Quality Factor ranges from highest quality to lowest quality.

If such a camera is to have an assured capacity for a designated number of images, each image must be limited in memory to an allocated percentage of the total. For example, a filmless camera having a capacity for thirty-two still images would provide an available capacity for each frame equal to the total memory capacity divided by thirty two. However, if an arbitrary standard is used to determine which blocks are to be compressed by the more memory-expensive procedure, some images will be compressed into significantly less memory than is available with a resulting image of less than optimum quality. Accordingly, the standard for selecting the blocks to be compressed by the alternate procedures is variable and is automatically adjusted to provide the highest reconstituted image quality without exceeding the allocated memory capacity.

Simultaneously the compression parameters of the DCT and, optionally the alternative compression, are adjusted to yield a uniform image quality. In the case of the DCT compression, the compression parameters set the quantization level of the coefficients. For the alternative compression, in the case of difference encoding, the compression parameters may set the quantization of the differences.

In this example, the Quality Factor may range from zero to four. The compression parameters and artifact threshold associated with a Quality Factor of zero are selected so that a worst case image will compress to an acceptable size. The compression and threshold parameters used with Quality Factors one to four are set to increase compressed image size by approximately 33% for each step. Acceptable image size is then set to range from a maximum of memory size divided by the number of pictures to slightly less than 75% of that maximum.

In this example, the image would first be compressed with a Quality Factor of two. If the compressed image is of acceptable size, as defined above, the Quality Factor has been found and this trial process is terminated. If the compressed image is too large, the Quality Factor is decremented and the trial process is repeated. If the compressed image size is too small, the Quality Factor is incremented and the trial process is repeated. In any case, this trial process is terminated after three cycles. The image is then compressed and stored with the current Quality Factor.

The primary elements of the digital camera are illustrated diagrammatically in FIG. 1. An image sensor is a device that can produce a two dimensional map of values correlated to light intensity as a function of the position on the sensor in two dimensions. Image sensors include vidicons, plumbicons, CCD's (including Full Frame, Frame Transfer, and Interline Transfer), Charge Injection Devices (CID), MOS detectors (which use a Metal Oxide Semiconductor to read out a photoresistor), PhotoFET arrays, FET selected diode arrays, and Bulk Charge Modulated Devices (BCMD). In this example, the image sensor 4 is a Charge Coupled Device (CCD).

The coefficients are quantized in accordance with known procedures based on sensitivity studies. The majority of coefficients are zero after quantization. Typically, five to ten of the 64 coefficients representing one block have a finite non-zero value. Preferably a variable quantization factor is used to increase or decrease the amount of compression achieved.

The non-zero coefficients are ordered in the zig-zag scan shown in FIG. 2. The coefficient information is represented by two components for each value (a) the relative location of each non-zero coefficient; and (b) the actual number of the non-zero coefficients, that is, a five bit code followed by a three bit code. This data is Huffman coded.

The compression procedure reference above is for he most part conventional and well known in this field. However, the DCT method of compression frequently results in artifacts caused by bright points or edges in the image being recorded. These artifacts are usually in the form of a checkerboard pattern in the reconstituted image in the blocks containing these abrupt changes in intensity of the image.

It is possible to avoid this objectionable feature of DCT compression by using an alternative compression method that does not produce the artifacts. But the use of such a compression method significantly increases the amount of memory required to record the data from each image. For example, the DCT method can provide, for example, a compression ratio of nine to one. An alternative method, such as differential coding, might provide a compression ratio of one two or three to one. However, it is an object here to store as many images as possible while, for reasons of economy, limiting the memory to the smallest capacity consistent with acceptable image quality. Accordingly, it is desirable to use the DCT compression method (or similar technique) wherever it can be utilized without excessive degradation of the image quality.

In accordance with the present procedure, the DCT method is adopted for most blocks of data, but selected blocks most likely to give rise to artifacts are identified and compressed by an alternate method that does not give rise to the objectionable artifacts.

Those blocks of data that after DCT compression and quantization contain the higher number of non-zero coefficients are the ones most likely to cause artifacts on decompression. If the number of the non-zero coefficients of a block exceeds a pre-established threshold selected to provide the desired level of quality, the data is not compressed using the DCT algorithm, but is compressed by an alternate method such as differential coding. To enable correct decompression methods to be employed, each recorded block carries a one new bit code to indicate the method by which it was compressed. The bits designating the method of compression of each block may be included in the image memory or may be recorded in a separate reference table.

The data representing the image passes from the image sensor 4 through an analog-to-digital converter 5 and a buffer 6 to a sequential image block selection circuit 8. The image is compressed in a sequential mode of operation in which it is processed from top to bottom in a single pass by compressing the first row of blocks followed by the second row of blocks and continuing until the end of the image is reached. To facilitate this process, the block selection circuit 8 divides the image into square or rectangular blocks of uniform size. In this particular environment, each block represents a square of eight pixels on each side. Each block of data from the image selection circuit 8 is fed into a DCT compression circuit 12 where the data is compressed by the DCT method by at least 50%. The compressed block of data is then quantized by a quantization circuit 14 under the control of a compression parameter circuit 16. After quantization, the data representing one block of the image is analyzed by a frequency analyzer circuit 18 that counts the number of non-zero coefficients in the block. This information is fed into a compression decision circuit 22. Based upon the threshold provided by an adjustable artifact threshold control circuit 24 that is coupled to the compression decision circuit 22: (a) If the number of non-zero coefficients is below this threshold, the data representing that block is passed directly to a DCT coder 25 that encodes the quantized coefficient data and indicates that this particular block was compressed by DCT method. The bytes used by the encoded data are counted by the counter circuit 30 and (a) the encoded block of data is then recorded in the compressed image storage area 26; (b) or if the number of non-zero coefficients exceeds the threshold value, the block of data signals is relayed to an alternate compression circuit 27 where the block of data is compressed by an alternate method, such as differential coding, that does not produce objectionable artifacts in the reconstituted image. The amount of compression produced by the alternate compression circuit 27 is controlled by an adjustable parameter control circuit 28. Circuit 27 also adds a bit of data to indicate alternate compression. The data from this alternate compression method is passed through the byte counter 30 and then into the compressed image storage area 26.

A Quality Factor circuit 31 adjusts the compression parameter circuits 16 and 28 and sets the level of the artifact threshold circuit 24. It will be understood that, in practice, the functions represented between the buffer 6 and the memory 26 are not performed by separate electronic circuits but rather represent for the most part the functions performed by the software controlling the compression process.

The Discrete Cosine Transform of an 8.times.8 pixel image block produces an 8.times.8 block of DCT coefficients. These coefficients from one block of the image may be represented by the small squares 30 of a data block, generally indicated at 32 in FIG. 2. Each one of the small squares 30 represents a DCT coefficient. The upper left hand coefficient 34 represents the average spatial intensity of the block and is referred to as the DC coefficient. After the DCT coefficients are quantized, but before they are entropy encoded, DC prediction is performed, meaning that the DC term of the previous block is subtracted from the DC term of the present block prior to encoding.

Thus, each block is first compressed by the DCT method, quantized and subjected to the sequential scan indicated in FIG. 2. The high-frequency non-zero coefficients are then counted and the count compared with a preselected threshold. If the number of the non-zero coefficients exceeds the threshold, indicating that a particular block will contribute to an objectionable checker board pattern, the block is compressed by an alternate method rather than by the DCT method.

In the camera, an equal amount of memory is allocated for each image to be captured. If, for example, the camera is to have a capacity to store up to 32 images, one thirty-second part of the memory capacity will be allocated for each image. A particular image may be such that the number of data blocks having a sum of non-zero coefficients exceeding the established threshold is very large so that the above procedure would require greater memory capacity for storage than that allocated for the image. Alternatively, a particular image may have a very low sum of non-zero coefficient and require only a small part of the allocated memory.

To obtain optimum quality in the reproduced images, it is desirable to use as much of the allocated memory as possible without exceeding the memory allocation. This result is attained by first applying an arbitrary compression-determination threshold and computing the memory capacity required to store the compressed image. If this value is near the allocated memory capacity, that threshold is used as the basis for determining which blocks will be compressed by the alternative method. If the indicated memory requisite for recording exceeds the memory allocation, a higher quantization factor and a new threshold are selected and the memory requirement again computed. This process is repeated until the memory requirement is near the maximum of the allocated capacity and each block is compressed and recorded by either the DCT or the alternate method based on that threshold. If the indicated memory requirement is significantly smaller than the memory allocation, a new lower scale factor and a new threshold standard are used until the memory requirement approaches the allocated capacity. An optimum combination of quantization scale factors and thresholds is empirically determined to obtain the desired size of compressed images with few iterations, typically two.

After each data block has been examined and the method of compression selected, the data from the entire image is analyzed after compression by a memory measuring circuit 30 (FIG. 1) to determine the total memory requirement. The amount of compression of the image is adjusted to provide the highest image quality consistent with the allocated memory. As illustrated by FIG. 3, the image data is fed from a block 40 into compression circuits 42 where the image is compressed in accordance with the procedure set forth above, the initial degree of compression being established by the compression parameter control circuit 44. After compression, the image data is fed into a memory evaluator 46 where the computed memory requirements are compared with a target size established by the memory control circuit 48. If the projected memory is within the tolerance limits of the memory control circuit, the data is recorded without further processing. If the image data requires significantly more or less memory than that allocated for the image, the amount of compression is adjusted by a secondary parameter control circuit 52 that establishes a new compression parameter as a function of the deviation of the memory requirement from the amount of memory allocated for the image. The image is then returned to the compression circuits 42 where it is compressed in accordance with the revised compression parameter. This process may, if necessary, be repeated more than once to bring the memory requirements within the pre-established tolerance.

It is not always necessary to evaluate all data blocks to arrive at the highest Quality Factor that will produce a compressed image that is smaller than the per picture memory allocation. For example, if we number the rows of blocks from top to bottom, and the columns of blocks from left to right, we may perform trial compressions on only those blocks with an odd column and an odd row number, or a total of one-quarter of all blocks. For common image sizes, even a more sparse sample of data blocks will be statistically valid.

The process for treating each image is as follows: The Quality Factor is set to a mid-range value. The Quality Factor is represented by an integer with a range from zero to some small number. The mid-range Quality Factor might be three, for example. The image data is divided into data blocks representing the physical area of the image. The first sample block is then compressed with DCT with the Quality Factor set at its mid-range value. If the test for poor DCT at that Quality Factor is true, based on the number of non-zero coefficients in the block after quantization, the block is recompressed with the alternate mode of compression. However, if the test for poor DCT at the set Quality Factor is false, the output of the DCT is encoded to indicate the DCT mode of compression. The number of bytes of memory required to record the block is then computed.

After each sample block has been processed and the total number of bytes of the sample blocks determined, the memory required to record the entire image is then determined. If this is within the tolerances for the allocated image memory, the data is recorded in the memory. If the image would require memory in excess of the allocated memory, the Quality Factor is reduced and the image is compressed again. If the memory requirement is less than the tolerance of the allocated memory capacity, the Quality Factor is increased and the image is compressed again. When the memory required for the total image is within the allocated memory tolerance, the image is recorded.

The test for poor DCT at the Quality Factor means to apply a test that is a function of the Quality Factor to the output of the DCT compression. For example, count the number of high frequency terms from the DCT after quantization and compare with a table of integers produced by the Quality Factor. If the number of high frequency terms is greater than the integer in the table for the current Quality Factor, this would indicate a "poor" DCT.