Methods and apparatus for reducing storage size

• US 7,974,478 B2
• Filed: 07/06/2007
• Issued: 07/05/2011
• Est. Priority Date: 08/24/2006
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Dell Products LP (Dell Technologies Inc.)
• Inventors: Brueggemann, Eric, Rao, Goutham, George, Carter, Bashyam, Murali
• Primary Examiner(s): Do; Anh Hong
• Application Number:
  US11/774,319
• Publication Number:
  US 20080050029A1
• Time in Patent Office: 1,460 Days
• Field of Search: 382/232, 382/233, 708/209, 712/E9.017, 711/113, 711/126
• US Class Current: 382/232
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: G06T 9/004 Predictors, e.g. intraframe, interframe coding

Abstract

Prediction-based compression engines are spoon-fed with sequentially efficiently compressible (SEC) streams of input data that make it possible for the compression engines to more efficiently compress or otherwise compact the incoming data than would be possible with streams of input data accepted on a TV-raster scan basis. Various techniques are disclosed for intentionally forming SEC input data streams. Among these are the tight packing of alike files or fragments into concatenation suitcases and the decomposition of files into substantially predictably consistent (SPC) fragments or segments that are routed to different suitcases according to their type. In a graphics-directed embodiment, image frames are partitioned into segment areas that are internally SPC and multidirectional walks (i.e., U-turning walks) are defined in the segment areas where these defined walks are traced during compression and also during decompression. A variety of pre-compression data transformation methods are disclosed for causing apparently random data sequences to appear more compressibly alike to each other. The methods are usable in systems that permit substantially longer times for data compaction operations than for data decompaction operations.

Claims

1. A method, comprising:

storing an image comprising a set of digital pixels having an original arrangement of rows and columns over an address space in an electronic memory;

retrieving the digital pixels from the electronic memory;

grouping at least some of the digital pixels in the set into first pixel subsets such that at least some of the first pixel subsets include non-contiguously-arranged pixels with regard to the original arrangement, wherein a statistical distribution of the digital pixels within each first pixel subset is less random as compared to a statistical distribution for the set of digital pixels;

dividing at least a portion of the address space into first address segments, each first address segment uniquely identifying a corresponding first pixel subset;

ordering the first address segments according to their predictive similarity to provide a coding order;

successively retrieving the first pixel subsets corresponding to the ordering of the first address segments; and

predictive encoding the successively retrieved first pixel subsets into first encoded symbols.

2. The method of claim 1, wherein the predictive encoding is an arithmetic encoder.

3. The method of claim 1, wherein the predictive encoding is a predictive entropy encoding.

4. The method of claim 1, further comprising:

grouping at least some of the digital pixels in the set into second pixel subsets such that at least some of the second pixel subsets include non-contiguously-arranged pixels with regard to the original arrangement, wherein a statistical distribution of the digital pixels within each second pixel subset is less random as compared to a statistical distribution for the set of digital pixels;

dividing at least a portion of the address space into second address segments, each second address segment uniquely identifying a corresponding second pixel subset;

ordering the second address segments according to their predictive similarity to provide a coding order;

successively retrieving the first pixel subsets corresponding to the ordering of the first address segments; and

predictive encoding the successively retrieved second pixel subsets into second encoded symbols.

5. The method of claim 4, further comprising comparing a compression efficiency for the first encoded symbols to a compression efficiency for the second encoded symbols to determine a best compression efficiency.

6. The method of claim 5, further comprising:

repeating the dividing, ordering, successively retrieving, and encoding steps to determine that division and ordering that produces a most efficient encoding.