Distributing limited storage among a collection of media objects

• US 6,976,026 B1
• Filed: 03/14/2002
• Issued: 12/13/2005
• Est. Priority Date: 03/14/2002
• Status: Active Grant

• Current Assignee: DigiMedia Tech, LLC (IP Investments Group LLC)
• Original Assignee: Microsoft Corporation
• Inventors: Malvar, Henrique S., Getzinger, Thomas W.
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): PHAM, HUNG Q
• Application Number:
  US10/099,807
• Time in Patent Office: 1,370 Days
• Field of Search: 707/101, 382/232, 382/244, 382/250
• US Class Current: 1/1
• CPC Class Codes: G06T 9/00 Image coding bandwidth or redundancy reduction for static pictures H04N1/41; coding or decoding of static colour picture signals H04N1/64; methods or arrangements for coding, decoding, compressing or decompressing digital video signals H04N19/00
• CPC Class Codes: H04N 19/115 Selection of the code volume for a coding unit prior to coding
• CPC Class Codes: H04N 19/124 Quantisation
• CPC Class Codes: H04N 19/147 according to rate distortion criteria rate-distortion as a criterion for motion estimation H04N19/567
• CPC Class Codes: H04N 19/154 Measured or subjectively estimated visual quality after decoding, e.g. measurement of distortion use of rate-distortion criteria H04N19/147
• CPC Class Codes: H04N 19/172 the region being a picture, frame or field
• CPC Class Codes: H04N 19/192 the adaptation method, adaptation tool or adaptation type being iterative or recursive
• CPC Class Codes: H04N 19/196 being specially adapted for the computation of encoding parameters, e.g. by averaging previously computed encoding parameters processing of motion vectors H04N19/513
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A quality level determining the extent to which each image file is compressed is automatically computed for each image file in a set to ensure that the total size of the compressed image files does not exceed a predefined limit. The compressed size of each image file is initially determined when compressed at a predefined minimum acceptable level and at a nominal level. The relative complexity of the image files is determined based upon their high frequency energy content. As a function of the image file complexity, and starting with the compressed sizes initially determined, the appropriate quality level is determined for compressing each of the image files in an iterative process that ensures the total size of the compressed image files does not exceed the predefined limit, while retaining acceptable quality. Thus, a set of image files can be compressed optimally to fit within a limited storage.

Claims

1. A computer-implemented method for automatically selecting a quality level when compressing each of a set of image files to produce compressed image files, so that a total size of the compressed image file does not exceed a predefined limit, comprising the steps of:

(a) processing the image files to determine a maximally compressed file size for each image file when compressed to a predefined minimum quality level and to determine a nominal compressed file size when compressed to a nominal quality level, and to determine a weight for each image file based upon a high frequency energy content of the image file;

(b) identifying image files of the set that are to be compressed with the predefined minimum quality level as a function of;

(i) the maximally compressed file size of each image file when compressed to the predefined minimum quality level; and

(ii) the weight of each image file;

(c) for all other image files of the set that were not identified to be compressed with the predefined minimum quality level in step (b), determining a quality level for compressing the other image files so that each of the other image files is to be compressed to a desired size selected as a function of the weight of the image file and so that the total size of the compressed image files does not exceed the predefined limit; and

(d) compressing the image files identified in step (b) with the predefined minimum quality level, and all of the other image files not identified in step (b) with the quality level that was determined in step (c).

2. The method of claim 1, further comprising the step of limiting the quality level that is used for compressing the image files to a predetermined range that extends from the predefined minimum quality level to a substantially higher predefined maximum quality level.

3. The method of claim 1, further comprising the step of determining a scaling factor based upon a currently available space remaining for the compressed files within the predefined limit and a total of the weight of ail of the other image files, wherein the step of identifying image files that will be compressed with the predefined minimum quality level is repeated in successive passes through the set of image files, until a pass through the set of image files is completed without identifying any additional image file to be compressed to the predefined minimum quality level.

4. The method of claim 1, wherein the step of determining the quality level that will be used for compressing the other image files in step (c) comprises the steps of:

(a) determining a desired size for the compressed image file for each of the other image files in the set that was not identified in step (b) of claim 1, said desired size for the compressed image file being determined as a function of the weight of the image file;

(b) determining an optimal quality level to apply to each of the other image files to achieve the desired size when the image file is compressed; and

(c) determining a difference between the desired size and an actual size of the image file when it is compressed to the optimal quality level.

5. The method of claim 4, wherein the step of determining the optimal quality level for each image file comprises the steps of:

(a) starting with the nominal quality level, determining if the nominal compressed file size is less than the desired size by no m ore than a predefined difference, and if so, assigning the nominal quality level as the optimal quality level; and

if not,

(b) reducing a range from which to select a new quality level to try as the optimal quality level when compressing the image file, where the new quality level is determined using a model relating image quality to compressedfile size;

(c) determining if the compressed file size resulting from compressing the image file using the new quality level is less than the desired size by no more than the predefined difference, and if so, assigning the new quality level as the optimal quality level; and

if not,

(d) repeating step (b) and step (c) of this claim with successive new quality levels, until the optimal quality level is determined.

6. The method of claim 1, wherein the predefined limit is selected based upon one of:

(a) a storage capacity of a storage medium on which the compressed image files are to be stored; and

(b) a maximum permissible size of an attachment to an email, wherein the attachment comprises the compressed image files.

7. A memory media on which are stored machine instructions for carrying out the steps of claim 1.

8. A system for automatically selecting a quality level when compressing each of a set of image files to produce compressed image files, so that a total size of the compressed image files does not exceed a predefined limit, comprising:

(a) a memory in which are stored a plurality of machine instructions, said memory also storing the set of image files;

(b) a processor that is coupled to the memory, said processor executing the plurality of machine instructions, causing the processor to;

(i) determine a maximally compressed file size for each image file when compressed to a predefined minimum quality level and determine a nominal compressed file size when compressed to a nominal quality level, and determine a weight for each image file based upon a high frequency energy content of the image file;

(ii) identify image files that are to be compressed with a predefined minimum quality level as a function of;

(1) the maximally compressed file size of each image file when compressed to the predefined minimum quality level; and

(2) the weight of each image file;

(iii) for all other image files of the set that were not identified to be compressed with the predefined minimum quality level in subparagraph (ii), determining a quality level for compressing the other image files so that each of the other image files is to be compressed to a desired size selected as a function of the weight of the image file and so that the total size of the compressed image files does not exceed the predefined limit; and

(iv) compressing the image files identified in subparagraph (ii) with the predefined minimum quality level, and compressing all the other image files not identified in subparagraph (ii) with the quality level that was determined in subparagraph (iii).

9. The system of claim 8, wherein the machine instructions cause the processor to limit the quality level that is used for compressing the image files to a predetermined range that extends from the predefined minimum quality level to a substantially higher predefined maximum quality level.

10. The system of claim 8, wherein the machine instructions cause the processor to determine a scaling factor based upon a currently available space remaining for the compressed files within the predefined limit and a total of the weight of all of the other image files, and to repeat the identification of image files that will be compressed with the predefined minimum quality level in successive passes through the set of image files, until a pass through the set of image files is completed without identifying any additional image file to be compressed to the predefined minimum quality level.

11. The system of claim 8, wherein the machine instructions cause the processor to determine the quality level that will be used for compressing the other image fies in subparagraph (iii) by:

(a) determining a desired size of the compressed image file for each of the other image files in the set that was not identified in subparagraph (ii) of claim 8, said desired size being determined as a function of the weight of the image file;

(b) determining an optimal quality level to apply to each image file to achieve the desired size when the image file is compressed; and

(c) determining a difference between the desired size and an actual size of the image file when it is compressed to the optimal quality level.

12. The system of claim 11, wherein the machine instructions cause the processor to determine the optimal quality level for each image file by:

(a) starting with the nominal quality level, determining if the nominal compressed file size is less than the desired size by no more than a predefined difference, and if so, assigning the nominal quality level as the optimal quality level; and

if not,

(b) reducing a range from which to select a new quality level to try as the optimal quality level when compressing the image file, where the new quality level is determined using a model relating image quality to compressedfile size;

(c) determining if the compressed file size resulting from compressing the image file using the new quality level is less than the desired size by no more than the predefined difference, and if so, assigning the new quality level as the optimal quality level; and

if not,

(d) repeating step (b) and step (c) of this claim with successive new quality levels, until the optimal quality level is determined.

13. The system of claim 8, further comprising a storage medium on which the compressed image files are stored, wherein the machine instructions cause the processor to select the predefined size limit based upon one of:

(a) a storage capacity of the storage medium; and

(b) a maximum permissible size of an attachment to an email, wherein the attachment comprises the compressed image files.