Methods and apparatus for reducing storage size
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.
1. A machine-implemented data compression/decompression method comprising:
(a) within a computer, segmenting a data containing address space for a memory associated with the computer to thereby define a plurality of segments where each segment contains a consecutively addressable sequence of data containing tiles and each tile contains at least one symbol occurring in a predefined alphabet;
(b) within the memory, recording a first expression of a corresponding first boundary approximating plot that extends across the data containing address space where the first plot cuts through end tiles of two or more of said segments and where the first plot further lays to one side or another or on a predefined reference point of each tile it cuts through and the positioning of the reference point relative to the first plot deterministically indicates in accordance with a predefined system convention whether the cut-through tile is to be deemed as being wholly disposed to one side or the other of a segmentation boundary represented by the first boundary approximating plot;
(c) within the computer, beginning or discontinuing a compressing or decompressing walk through a first of said segments in response to a machine determination that a corresponding first end tile of the first segment has a reference point lying to one side or another or on the first boundary approximating plot; and
(d) within the computer, beginning or discontinuing a continuation of said compressing or decompressing walk through a second of said segments in response to a machine determination that a corresponding second end tile of the second segment has a reference point lying to one side or another or on the first boundary approximating plot, where the first and second segments are spaced apart address-wise from each other in said data containing address space.
2. The method of claim 1 wherein:
(b.1) said first recorded expression defines the first boundary approximating plot as having a linear section cutting through end tiles of at least two of the plural segments.
3. The method of claim 1 wherein:
(b.1) said first recorded expression defines at least one Bezier anchor point for thereby defining the first boundary approximating plot.
4. The method of claim 1 and further comprising:
(e) recording a second expression of a corresponding second boundary approximating plot that extends across the data containing address space where the second plot cuts through end tiles of two or more of said segments and where the second plot further lays to one side or another or on a predefined reference point of each tile it cuts through and the positioning of the reference point relative to the second plot deterministically indicates in accordance with the predefined system convention whether the cut-through tile is to be deemed as being wholly disposed to one side or the other of a second segmentation boundary represented by the second boundary approximating plot, wherein the first and second boundary approximating plots thereby identifying opposed ends of at least one of the segments; and
(f) beginning or discontinuing a second compressing or decompressing walk through a third of said segments in response to a machine determination that a corresponding first end tile of the third segment has a reference point lying to one side or another or on the second boundary approximating plot.
5. The method of claim 1 wherein said address space defines a displayable image frame and the at least one symbol contained in each tile wholly defines a corresponding pixel of the displayable image frame.
6. The method of claim 1 wherein each tile is subdivided into a plurality of tile subareas and said compressing or decompressing walk walks through all the tile subareas of tiles included in said first segment.
7. The method of claim 1 wherein said address space defines a displayable image frame and the at least one symbol contained in each tile defines a Discrete Cosine Transform (DCT) coefficient corresponding to a plurality of pixels of the displayable image frame.
8. A machine-implemented data compression method comprising:
(a) within a computer, identifying a subset of image tiles from among a matrix of image tiles where the identified subset contains data that is to be successively encoded into a more compact code stream by a compression engine, where each tile includes a plurality of digitized image pixels, and where said machine-implemented identifying step includes:
(a.1) within the computer, identifying anchor point data signals that define a plurality of anchor points, where said anchor points define a boundary approximating curve that maps across said matrix of image tiles, the boundary approximating curve cutting through at least one of said identified image tiles; and
(a.2) within the computer, determining whether a predefined center of gravity of a given one of said image tiles is to be deemed as logically lying to one side or another of the boundary approximating curve so as to thereby determine if the given one image tile is or is not a member of said subset of image tiles whose contained is to be successively compressed by the compression engine even if the boundary approximating curve cuts through the given one image tile.
9. The data compression method of claim 8 wherein said boundary approximating curve is a Bezier curve.