Recently services are being offered where a customer requests a photofinisher to process (that is, chemically develop a roll of film carrying a latent image to yield a fixed image) a roll of film and also provide digitized versions of the photographic images on a storage medium, such as a floppy disk. Because photographic images require large amounts of digital data, and the floppy disk has very limited storage capacity, the digital photographic image files are typically compressed using standard compression methods.
For image compression systems, a fundamental distinction can be made between lossy and lossless compression systems. A lossless compression system will compress and decompress image data in such a way that decompressed image data is exactly the same as the originally input image data. In comparison, the decompressed image data resulting from a lossy compression system will be different from the originally input image data. The human visual system has a minimum detectable threshold that allows us to perceive as the same an original and its decompressed image that have some small amount of real difference between them. By taking advantage of this human visual system threshold, a lossy compression system can provide a higher compression rate without visible degradation in an image.
Another fundamental distinction between image compression systems can be made between variable-rate systems and fixed-rate systems. Rate refers to the number of bits required after compression to represent a given spatial unit (for example, bits/pixel, bits/image, bits/image collection, and the like). A variable-rate compression system is one that produces a variable output data rate, depending on the properties of the input image data. Conversely, a fixed-rate compression system is one that produces a constant output data rate, regardless of the input image data.
The fundamental trade-off in lossy compression systems is between compressed data rate and image quality. For a constant level of image quality, a higher rate is generally needed for an image or image region containing significant detail (that is, signal energy), as compared to a relatively low detail image or image region. A variable-rate system is well-suited to providing a constant level of image quality, since bits are expended as needed to match the image or image region characteristics. In comparison, a fixed-rate system must compromise on image quality for those images or image regions where the available number of bits is insufficient.
When photographic images are compressed using a variable rate lossy compression method, such as JPEG, it is difficult to predict what the final compressed file storage space will be because the actual image content of an individual image will impact the final file storage space of that image. It is easy to predict the size of a compressed file when a fixed compression method is employed.
In designing a compression system, an example of a variable-rate lossy compression method is the JPEG (Joint Photographic Experts Group) international standard, as described by W. B. Pennebaker and J. L. Mitchell, "JPEG: Still Image Data Compression Standard," Van Nostrand Reinhold, New York 1993. This reference and all other references cited herein are incorporated by reference. The JPEG system parameter that exerts the largest effect on the compressed data rate is the quantization table specification. There are many possible methods to adjust the JPEG quantization table in order to achieve a predictable file storage space for the image collection. The most straightforward method is to start with an initial quantization table, compress an image or collection of images, and then adjust the initial table by a multiplicative scaling factor if the desired rate is not achieved. A scaling factor greater than one results in more quantization and hence a lower rate than achieved with the initial quantization table. Likewise, a scaling factor less than one results in less quantization and hence a higher rate than that achieved with the initial quantization table. If the desired rate is not achieved after the first adjustment, this adjustment process can be iterated (that is, repeated) until the rate constraint is met. To make such an approach useful in practice, it is necessary to achieve the desired rate in only a few iterations.
When the same JPEG parameters are used to compress two different images, each image results in a different final compressed file storage space due to the contents of the different images. This makes it impossible to predict how much file storage space is required to store a collection of images until the images have actually been compressed.
When trying to guarantee that a collection of compressed images will fit on a limited storage medium such as a floppy disk, a fixed set of JPEG compression parameters could be chosen to insure that all images can be compressed to fit on the disk even if all of the images were highly detailed. Such a set of fixed compression parameters, because they are selected to accommodate the worst case scenario of all images containing high amounts of detail, will over-compress most images. Unfortunately, the more a photographic image is compressed, the more image quality that is lost. Over-compression of photographic images using a lossy compression method results in lost image quality.
In addition, when a consumer has a photographic film processed and the images thereon scanned, with some images the degree of compression required even to barely fit the images on a limited storage medium, such as a diskette, will produce compressed images with unacceptable loss in image quality.
It is therefore desirable to have a compression method that determines the minimum compression necessary for a collection of images so that the actual compressed collection will fit within a limited storage space, such as that provided by a floppy disk, without being over-compressed, so that almost all the available storage space is used. It would also be desirable if for a given collection of images, that the compression method recognizes that the compression required to fit the collection on such a fixed capacity medium produces unacceptable losses and compensates for this situation.