Method for digital quantization

• US 7,313,287 B2
• Filed: 05/21/2002
• Issued: 12/25/2007
• Est. Priority Date: 05/22/2001
• Status: Active Grant

• Current Assignee: Yuri Abramov
• Original Assignee: Yuri Abramov
• Inventors: Abramov, Yuri
• Primary Examiner(s): Couso, Jose L.
• Application Number:
  US10/478,233
• Publication Number:
  US 20040179595A1
• Time in Patent Office: 2,044 Days
• Field of Search: 382/232, 382/236, 382238-240, 382/248, 382/250, 382251-252, 348/395.1, 348/398.1, 3484001-4041, 3484071-4181, 3484201-4221, 3484301-4311, 37524002-24003, 37524011-24024
• US Class Current: 382/251
• CPC Class Codes: H04N 19/126 Details of normalisation or weighting functions, e.g. normalisation matrices or variable uniform quantisers
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/649 the transform being applied to non rectangular image segments
• CPC Class Codes: H04N 19/86 involving reduction of coding artifacts, e.g. of blockiness

Abstract

There is disclosed the use of a beehive cell arrangement of shaped quantization blocks for grouping pixels for the digital approximation of analog video information. A frame may consist of beehive-arranged hexagonal quantization cell blocks or brick-wall-arranged rectangular cell quantization blocks, where each pixel belongs only to one shaped quantization block. A beehive cell arrangement of circle-shaped quantization blocks is described for use when the frame is partitioned into overlapping quantization blocks.

Claims

1. A computer program product comprising a computer usable medium having computer readable code embodied therein for execution on a general purpose computer, said computer program product operating in a video compression-decompression system, said system applying MPEG-X series standards basic principle comprising a digital approximation of analog video information in frames, said frames comprising pixels arranged and shaped to fill the area of the frames completely, wherein the frames are partitioned into non-overlapping quantization blocks of grouped complete and incomplete pixels, and wherein the quantization blocks are encoded by a transform providing intra-block encoding-correlation among the complete and incomplete pixels,

said computer usable medium storing instructions that, when executed by the computer, cause the computer to perform a method for optimally arranging and shaping said quantization blocks of pixels into groupings, said method comprising:

determining that arrangement for which the statistical boundary error as equalized in accordance with Chebyshev'"'"'s alternance theorem, whereby;

a) all of said quantization blocks have the same shape, independent of congruence and alignment with the shape of each of said pixels;

b) each of said quantization blocks has the same environment as contiguous quantization blocks;

c) each of said quantization blocks has the lowest possible number of contiguous quantization blocks;

d) the variance of measured distances from the center of one of said quantization blocks to the centers of neighboring quantization blocks is minimized; and

e) the variance of measured common boundary lengths between one of said quantization blocks and contiguous quantization blocks is minimized.

2. The optimization method according to claim 1, wherein application of Chebyshev'"'"'s alternance theorem to qnantization blocks initially having a rectangular shape provides that said quantization blocks are arranged in a brick wall arrangement, whereby each of said quantization blocks has only six contiguous quantization blocks.

3. The optimization method according to claim 1, wherein application of Chebyshev'"'"'s alternance theorem produces quantization blocks having a hexagonal shape and being arranged in a beehive-cell arrangement, whereby each of said quantization block has only six contiguous quanitization blocks.

4. A computer program product comprising a computer usable medium having computer readable code embodied therein for execution on a general purpose computer, said computer program product operating in a video compression-decompression system, said system applying MPEG-X series standards basic principle comprising digital approximation of analog video information in frames, said frames comprising pixels arranged and shaped to fill the area of the frames completely, wherein the frames are partitioned into overlapping quantization blocks of grouped complete and incomplete pixels, and wherein the quantization blocks are encoded by a transform providing intra-block encoding-correlation among the complete and incomplete pixels, and wherein at least one said pixel belongs to more than one quantization block,

said computer usable medium storing instructions that, when executed by the computer, cause the computer to perform a method for optimally arranging and shaping said overlapping quantization blocks of pixels into groupings, comprising determining that arrangement for which the statistical boundary error is equalized in accordance with Chebyshev'"'"'s alternance theorem, whereby:

a) said overlapping quantization blocks have the same shape, independent of congruence and alignment with the shape of each of said pixels;

b) each overlapping quantization block has the same environment as contiguous overlapping quantization blocks;

c) each said overlapping quantization block has the least possible number of said contiguous overlapping quantization blocks;

d) variance of measured distances from the center of one of said overlapping quantization blocks to the centers of neighboring overlapping quantization blocks is minimized; and

e) variance of measured overlapping areas between one of said overlapping quantization blocks and contiguous overlapping quantization blocks is minimized.

5. The optimization method according to claim 4, where said overlapping quantization blocks have a circular shape and are overlapped in an arrangement similar to beehive cells, wherein said circle shape surrounds said beehive cell, and wherein each of said overlapping circular quantization block has common pixels only with six neighbor overlappinq circular quantization blocks.

6. The optimization method according to claim 5, where said circular shape comprises a polygonal circular approximation surrounding said beehive cell.

7. A computer program product comprising a computer usable medium having computer readable code embodied therein for execution on a general purpose computer, said computer program product operating in a video compression-decompression system,

said system applying MPEG-X series standards basic principle comprising a digital approximation of analog video information in frames, said frames comprising pixels arranged and shaped to fill the area of the frames completely, wherein the frames are partitioned into quantization blocks of grouped complete and incomplete pixels, and wherein the quantization blocks are encoded by a transform providing intra-block encoding-correlation among the complete and incomplete pixels,

said computer usable medium storing instructions that, when executed by a computer, cause the computer to perform a method for organization of said quantization blocks into such arrangements that at least two said video-information frames differ by said arrangements of said quantization blocks;

and wherein the statistical boundary error for each said arrangement is equalized in accordance with Chebyshev'"'"'s alternance theorem, whereby

a) all of said quantization blocks have the same shape, independent of congruence and alignment with said pixel'"'"'s shape;

b) each quantization block has the same environment as contiguous quantization blocks;

c) each of said quantization blocks has the lowest possible number of contiguous quantization blocks;

d) variance of measured distances from the center of one of said quantization blocks to the centers of neighboring quantization blocks is minimized; and

e) variance of measured common boundary lengths between one of said quantization blocks and contiguous quantization blocks is minimized.

8. The method for organization of quantization blocks according to claim 7,

wherein video-information frames have said organization of equivalent rectangular quantization blocks into a brick-wall arrangement having horizontal respective shifts of odd and even quantization blocks rows,

and wherein at least two said arrangements, associated with at least two said frames correspondingly, differ by said horizontal respective shifts of said quantization blocks rows.

9. The method for organization of quantization blocks according to claim 7, wherein video-information frames have said organization of equivalent rectangnlar quantization blocks into a brickwall arrangement having vertical respective shifts of odd and even quantization blocks columns, and wherein at least two said arrangements, associated with at least two said frames correspondingly, differ by said vertical shifts of said quantization blocks columns.

10. The method for organization of quantization blocks according to claim 7, wherein video-information frames have said organization of equivalent rectangular quantization blocks into a brick-wall arrangement, and wherein at least one said frame has said brick-wall arrangement with horizontal respective shifts of quantization blocks rows, and at least one said frame has said brick-wall arrangement with vertical respective shifts of quantization blocks columns.

11. The method for organization of quantization blocks according to claim 7, wherein video-information frames have said organization of equivalent shaped quantization blocks into a beehive cells arrangement, and wherein said beehive cells have vertexes oriented horizontally, whereby forming odd and even shaped quantization blocks columns, which are respectively shifted on vertical, and wherein at least two said arrangements, associated with at least two said frames correspondingly, differ by the respective vertical shifts of said odd and even columns of said shaped quantization blocks.

12. The method for organization of quantization blocks according to claim 7, wherein video-information frames have said organization of equivalent shaped quantization blocks into a beehive cells arrangement, and wherein said beehive cells have vertexes oriented vertically, thereby forming odd and even shaped quantization blocks rows, which are respectively shifted on horizontal, and wherein at least two said arrangements, associated with at least two said frames correspondingly, differ by the respective horizontal shifts of said odd and even rows of said shaped quantization blocks.

13. The method for organization of quantization blocks according to claim 7, wherein video-information frames have said organization of equivalent shaped quantization blocks into a beehive cell arrangement, and wherein at least one said beehive cell arrangement, associated with at least one frame, comprises said beehive cells having vertexes oriented horizontally, whereby forming odd and even shaped quantization blocks columns, which are respectively shifted on vertical, and at least one said beehive cell arrangement, associated with at least one said frame, comprises said beehive cells having vertexes oriented vertically, whereby forming odd and even shaped quantization blocks rows, which are respectively shifted on horizontal.

14. The method for organization of quantization blocks according to claim 7, wherein said pixels have rectangular shape and are arranged along straight rows and columns.

15. The method for organization of quantization blocks according to claim 7, wherein said pixels have triangular shape.

16. The method for organization of quantization blocks according to claim 7, wherein said pixels have hexagonal shape and are arranged similar to beehive cells arrangement.