Abstract:
Images captured in a digital form are stored in a digital storage device with already-stored images by determining if a percentage of a finite storage capacity of the digital storage device needed to store the captured and already stored images in the storage device exceeds a pre-set threshold value, wherein storage used of the finite storage capacity to store images may exceed the pre-set threshold value. If the percentage of storage space needed to store the captured and already stored images in the storage device exceeds the pre-set threshold value, then at least one of the captured and already stored images are compressed and all of the captured and already stored images, including all of the compressed images of the captured image and the already stored image, are stored in the storage device.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation of U.S. application Ser. No. 10/353,765, filed Jan. 28, 2003, now U.S. Pat. No. 7,551,787 B2, issued Jun. 23, 2009. 
    
    
     FIELD OF THE INVENTION 
     This invention relates generally to data compression and recompression and, more particularly, to a technique for incrementally storing additional images in a given storage area. 
     BACKGROUND INFORMATION 
     Compression associated with data, especially data in the form of images, generally is “lossy compression”, although, as will be described presently; in some instances, “lossless compression” may be used. Standard well-known “lossy compression” techniques, such as JPEG, sacrifice fine details in the image to gain storage efficiency, minimizing file size. The degree of compression in the stored image is referred to as its “quality” or “Q” factor. 
     It is often the case that the amount of information to be stored exceeds the resource available to hold it. For example, a vacationing user may have a digital camera with one “FLASH ROM”. If conditions are conducive to photography and opportunities are abundant, the photographer may fill the non-volatile storage before the vacation is completed. If new opportunities for photographs present themselves, the photographer must decide whether to delete images to make room for others. 
     It is, therefore, an object of this invention to provide a technique (method, system, apparatus, article of manufacture, signal-bearing media) to adaptively adjust compression quality of data to permit the incremental storage into a predetermined space-of-objects, which may be lossily-compressed. 
     For expository purposes, the invention will be described in terms of a digital camera, i.e. a camera which records images as compressed files in a fixed-size non-volatile storage, although this should not be construed as limiting the scope of the invention. The invention can be practiced in any situation which allows for lossy data compression. It is also useful in some situations where lossy compression is not acceptable, but where a plurality of lossless compression schemes are available, the denser ones requiring more time or resource to execute. Although the storage described herein is customarily semiconductor non-volatile storage, the invention is not limited to that type; rotating magnetic (disk) storage, tape storage, or any other digital storage may be utilized. 
     SUMMARY OF THE INVENTION 
     In one embodiment, a method of storing multiple captured images in digital form includes storing an image captured in a digital form in a first format in a digital storage device with an image already stored in the digital form in the storage device, and determining if a percentage of a finite storage capacity of the digital storage device needed to store the captured and already stored images in the storage device exceeds a pre-set threshold value, wherein storage used of the finite storage capacity to store images may exceed the pre-set threshold value. If the percentage of storage space needed to store the captured and already stored images in the storage device is determined to exceed the pre-set threshold value, then the method compresses at least one of the captured and already stored images and stores all of the captured and already stored images, including all of the compressed images of the captured image and the already stored image, in the storage device. 
     In another embodiment, a device for storing multiple captured images in digital form includes a digital storage device operatively connected to a structure to capture an image in a digital form, wherein the digital storage device has a finite storage capacity for storing the images in the digital form. The device embodiment thus stores an image captured in a digital form in a first format in a digital storage device with an image that is already stored in the digital form in the storage device, and determines if a percentage of a finite storage capacity of the digital storage device that is needed to store the captured and already stored images in the storage device exceeds a pre-set threshold value, wherein the storage used of the finite storage capacity to store images may exceed the pre-set threshold value. The device embodiment automatically compresses at least one of the captured and already stored images if the determined percentage of storage space needed to store the captured and already stored images exceeds the pre-set threshold value, and stores all of the captured and already stored images, including all of the compressed images of the captured image and the already stored image in the storage device. 
     In another embodiment, a computer program product for storing multiple captured images in digital form includes a computer readable storage device having computer executable program code stored thereon. The program code comprises instructions which, when executed on a programmable device, cause the programmable device to store an image captured in a digital form in a first format in a digital storage device with an image that is already stored in the digital form in the storage device, and to determine if a percentage of a finite storage capacity of the digital storage device that is needed to store the captured and already stored images in the digital storage device exceeds a pre-set threshold value, wherein the storage used of the finite storage capacity to store images may exceed the pre-set threshold value. The programmable device is also thereby further caused to automatically compress at least one of the captured and the already stored images if the determined percentage of storage space needed to store the captured and already stored images exceeds the pre-set threshold value, and to store all of the captured and the already stored images, including all of the compressed images, the captured image and the already stored image, in the storage device. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a conceptual representation of the operation of a digital camera; 
         FIG. 2  shows a flow chart for processing to store an image; 
         FIG. 3  shows storage partially filled with images compressed at a medium quality; 
         FIG. 4  shows the storage as an additional image is added which fills the storage past the adaptive compression threshold value; 
         FIG. 5  shows the storage after the adaptive compression technique has operated and the images are re-stored at lower quality; 
         FIG. 6  shows the storage after an additional image has been stored; 
         FIG. 7  shows a user interface screen where the user may select adaptive compression and establish defaults; 
         FIG. 8  shows a flow chart of an alternate embodiment in which the quality of captured images is not revised, but new images are stored at progressively lower qualities as successive thresholds are crossed; 
         FIG. 9  shows empty storage with quality adjustment threshold values; 
         FIG. 10  shows storage after images have been captured, where the alternate embodiment technique has been utilized; and 
         FIG. 11  shows a user interface screen where the user may select adaptive compression and establish defaults for the alternate embodiment. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring now to the drawings and, for the present, to  FIG. 1 , the operation of a digital camera is illustrated. Image  10  is imaged by lens  12  onto Charge-Coupled-Device (CCD) array  14 . A CCD array is an array of cells. When the cells are exposed to light, each cell accumulates electrical charge proportional to the amount of incident light. After the image is captured, the cells may be operated like a shift register, i.e. to shift the charges to an Analog Front End (AFE)  16 . Some CCD devices are constructed with red, green and blue filters over various cells, to sample the amount of light of each color, at each image point. One such device is the FTF3020-C Full Frame Image Sensor manufactured by Philips Semiconductors. The AFE  16  comprises a programmable gain amplifier and an Analog-to-Digital Converter (ADC). A typical AFE  16  is the HD49334NP produced by Hitachi, Ltd. The AFE  16  is controlled by a Digital Signal Processor (DSP)  18 . The DSP  18  executes instructions in instruction memory  20  and causes the image content to be successively shifted out of the CCD array  14  and sampled (converted to digital form) by AFE  16 . The digital data representing the captured image is stored in data memory  22 . DSP  18  performs compression on the captured image data and stores the compressed image in non-volatile memory  200 , also see  FIG. 3 . 
     Compression on color images is performed on three separate images captured as the red, green and blue contributions. Each is treated as a gray-scale image. DSP  18  can perform lossless or lossy compression. 
     Lossless compression may involve run-length encoding, which is well-known. Run-length encoding is performed by replacing a sequence of repeated identical values with one instance of the value and a count. A more advanced coding, Lempel-Ziv encoding, stores repeated sequences of values in a dictionary and makes reference to them by their dictionary indices. A suitable method is described in U.S. Pat. No. 4,814,746 to Miller and Wegman, assigned to International Business Machines Corp., and incorporated herein by reference. When lossless compression is reversed, the decompressed data is identical to the original data prior to compression. 
     However, the invention in the preferred embodiment works best with lossy compression. The degree of compression can be varied, resulting in less or more loss of fine detail in the image and correspondingly greater or lesser size of the compressed image. In the well-known JPEG scheme, devised by the Joint Photographic Experts Group, the image is divided into blocks. The image data is transformed using the discrete cosine transform (similar to the Fourier transform) to the frequency domain. The result is a series of coefficients, the first representing the base (DC) intensity, and subsequent ones each representing intensity at finer levels of detail. An image of higher compression (and greater loss) has fewer coefficients in the series. Compression techniques in the JPEG format are shown and described in U.S. Pat. No. 5,677,689, dated Oct. 14, 1997, which is also incorporated herein by reference. When lossy compression is reversed, the decompressed data is not the same as the original data. Some detail, depending upon the degree of compression, will have been lost. 
     Image recompression with a higher compression factor may be performed by expanding the image from the compressed frequency-domain format (which resides in nonvolatile memory  200 ) into data memory  22  in image format, and then recompressing it at a higher compression factor. However, the preferred way to recompress the image is to recompress it directly in the frequency domain, by copying the data, while deleting higher order coefficients (in the JPEG format). Direct data recompression in the frequency domain is shown and described in U.S. Pat. No. 6,128,413 entitled Mapping Through Interval Refinement, incorporated herein by reference. The image may be manipulated directly in nonvolatile memory  200  or by copying it to data memory  22 . 
     As indicated previously, the present invention will be described as it is embodied in a digital camera. However, there are many other uses to which this technique can be applied. For example, in recorded speech, a digital answering machine or other types of voice-mail re-compresses messages to make room for more messages. In recorded audio, an MP3 player, or a computer that loads it, could compress the audio a bit more to get more pieces onboard. (MP3 is itself lossy compression of sampled audio). In video, a motion video camera could recompress its data in a manner similar to a still camera. The technique of the invention can be used to compress other data that represents time-series; for example, digitized ECG waveforms. 
     In one embodiment for carrying out the invention, each image is stored in nonvolatile storage, uncompressed, as it is captured. Subsequently, storage is checked to see whether an adaptive threshold percentage or value of storage capacity, e.g. 90 percent, has been exceeded. If the uncompressed image exceeds this threshold value, the image is compressed by a Q1 factor so that the area it covers is lower than the threshold value, and then stored in storage at this Q1 compression factor. When a new image is captured, storage is checked to see if the storage of the new image would exceed the threshold value and, if not, then the new image is stored in the uncompressed form. If the threshold value is exceeded, then existing images are recompressed by a factor of Q2 and the new image is compressed either by a factor of Q1 or Q2. This continues until the compression has reached a given Qn level. The adjusting of the compression of Q factor is described in said U.S. Pat. No. 5,677,689. Also, the adjusting of a digital camera to store at a given Q factor is well known. 
     With respect to the amount of compression that can be effectively utilized, it is difficult to perceive the difference between an original 11 KB image and one compressed to 2 KB. In fact, it is difficult to even perceive a difference down to about 1.5 KB. Thus, compression in excess of 6:1 and even up to about 8:1 can be achieved without the significant loss of perceived clarity of image. 
     This sequence, which is a signal in the form of a program or set of instructions for a computer contained on a medium, such as a magnetic disc or a semi-conductor chip, is depicted in the flow chart shown in  FIG. 2 . A new image is captured at  100 . The image is stored at the current quality level in step  102 . After the image is stored, the storage used is checked, as shown in step  104 . If the threshold is not exceeded, the compression exits, at step  108 . This condition is shown in  FIG. 3 , where  200  represents the non-volatile storage used, and  202  represents the threshold for reducing the quality or Qn of compression. If the threshold is exceeded when tested in step  104 , then all the images are recompressed at a lower quality level Qx, as shown in step  106 . 
       FIG. 4  depicts the storage  200  shown in  FIG. 3  after an additional image has been added and the threshold is exceeded after carrying out step  102 . The storage used in non-volatile storage  200  exceeds threshold  202 . 
       FIG. 5  depicts the storage  200  shown in  FIG. 4  once the compression in step  106  has been carried out. Threshold  202  (e.g. 90 percent) is no longer exceeded, and the images are stored with less detail at a more compressed Qn Value. Storage use is reduced, and additional images may be stored before subsequent quality reduction is required. 
       FIG. 6  shows the condition of the storage  200  shown in  FIG. 5  after an additional image has been stored. The compression process  106  may be carried out starting out with the images stored lowest in storage  200 , with each successive image being copied lower in storage as space is made available from the previous image, or by other techniques, such as using free storage at the top of storage  200  (above threshold  202 ) or by using another storage device for intermediate storage, or by compressing each image in place and storing new images in fragmented storage. 
       FIG. 7  shows a screen  300  which may be presented to a user to select whether adaptive compression is used, which quality level to initially use, and the lowest quality level the user will accept. This prevents the user from inadvertently storing too much information and reducing quality below an acceptable value. The user may also set the threshold higher (i.e. higher than 90 percent), which higher threshold will cause more frequent compression once exceeded. A lower threshold will cause compression sooner, reducing quality sooner. 
     There are alternate modes for practicing the present invention in which the steps may be carried out in another sequence. As each image is captured, the threshold is tested. If threshold is exceeded, the quality level is reduced and all stored images are re-compressed before the current image is stored. This method is inferior in some circumstances because it requires processing before the current image is stored, which may interfere with an immediately-subsequent capture. The method depicted in  FIG. 2  is more amenable to compression via “background processing” once all images are safely stored. 
       FIGS. 8-11  represent an alternate mode for practicing the present invention. ( FIG. 8  also represents a program or set of instructions for a computer contained on a medium, such as a magnetic disc, or a semi-conductor chip.) In this mode, captured images are never re-compressed. One or more thresholds are defined and, as each threshold is exceeded, new images are captured and compressed at successively lower quality levels. 
     With reference to  FIG. 8 , after each image is captured at step  400 , the threshold is tested at step  402 . If the pre-set threshold is exceeded, the quality or Qn level is reduced and the current image and all subsequent images are stored at the new quality level at step  406 . The process is exited at step  408 , regardless of whether the threshold was exceeded. 
       FIG. 9  depicts storage  202  with several thresholds  502 ,  504 , and  506  at which quality is to be successively reduced. 
       FIG. 10  depicts the storage and thresholds once images have been captured, using the alternate technique shown in  FIG. 8 . In  FIG. 10 , images captured after each threshold is exceeded are first captured and then reduced to lower quality or Q levels. 
       FIG. 11  depicts a screen  600  presented to a user that can be used to configure a device utilizing the alternate embodiment. 
     The foregoing description of various aspects of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and obviously, many modifications and variations are possible. Such modifications and variations that may be apparent to a person skilled in the art are intended to be included within the scope of the invention as defined by the accompanying claims.