Method of improved image/video compression via data re-ordering
A method of image and video compression including data re-ordering to improve the performance of the core compression algorithm. In the inventive method, pixel values of at least part of an image are examined and then re-ordered into a new order that has greater compactability than the original pixel order. The re-ordered pixel values are then compressed, e.g., by block transform. In the particular case of a compression scheme employing a block transform, the inventive method reduces the complexity of the transform coefficients, resulting in more efficient compression. The method may be added to existing compression algorithms with only minor modifications to the bitstream and decoder architecture.
1. A method of encoding digital image or video data having at least one frame, comprising the steps of:
a) examining pixel values of at least part of an image having an original order;
b) re-ordering the examined pixel values into a new order that has greater compactability than the original pixel order said re-ordering comprising the steps of:
i) labeling at least one of: the rows or the columns;
ii) creating an empty list to hold the evolving new row or column order;
iii) placing the first tow rows or columns labeled in said step i) in order in the new order list;
iv) computing the variance between all subsequent rows or columns and the first two rows or columns of the new order list respectively; and
v) determining if the variance between a given row or column and the first row or column on the new order list is smaller or larger than the variance between the given row or column and the last row or column on the new order list; and
c) compressing the re-ordered pixel values.
2. The method of claim 1 , further comprising the steps of:
placing the given row or column closer to the first row or column on the new order list if the variance between the given row or column and the first row or column is smaller than the variance between the given row or column and the last row or column on the new order list; and
placing the given row or column closer to the last row or column on the new order list if the variance between the given row or column and the last row or column is smaller than the variance between the given row or column and the first row or column on the new order list.
3. The method of claim 1 , further comprising the step of transmitting the compressed re-ordered data to a decoder.
4. The method of claim 1 , further comprising the step of sub-dividing the image into a plurality of partitions, each partition having a plurality of pixels.
5. The method of claim 4 , wherein partition size information is implicit and not explicitly transmitted in the bitstream.
6. The method of claim 4 , further comprising the step of parameterizing partition size information and encoding said information into the bitstream.
7. The method of claim 1 , further comprising the step of d) performing sub-pixel motion compensation on the pixel values.
8. The method of claim 7 , wherein said step d) is performed before re-ordering step b).
9. The method of claim 7 , wherein said step d) is performed after re-ordering step b).
10. The method of claim 6 , further comprising the step of using partition size information about a given partition on subsequent partitions.
11. The method of claim 1 , wherein the new order created for a given image is used to influence the re-ordering for subsequent images.
12. The method of claim 1 , further comprising the step of limiting the number of possible new orders generated in step b) wherein said limiting step utilizes at least one of a fixed codebook of predetermined data orders and an adaptive codebook of predetermined data orders.
13. The method of claim 1 , said compressing step c) further comprising the step of coding the re-arranged data via a block transform.
14. The method of claim 1 , wherein the new order created for a given partition is used to influence the re-ordering for subsequent partitions.