Method and apparatus for coding of spatial data

Patent metadata

Field	Value
Publication number	US-9819946-B2
Application number	US-201314390919-A
Country	US
Kind code	B2
Filing date	Apr 5, 2013
Priority date	Apr 5, 2012
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

The invention describes a method for representing geometry information to utilize for scalable coding of piecewise smooth spatial data sets. The method may also be applicable to vector data such as motion, where this data tends to exhibit piecewise smooth characteristics. The hierarchical geometry representation detailed in this invention is spatially scalable and amenable to embedded quantization and coding techniques. These features enable the geometry representation to be incorporated into highly scalable image coding schemes to attain efficient compression and output bit-streams with embedded resolution and quality scalability. Central elements of the invention are: the hierarchical representation of geometry information which describe points of discontinuity in the input data set; a rate-distortion driven estimation process to construct the geometry representation; a process to prioritize the geometry information in accordance to its influence on compression performance; and methods for efficient coding of the geometry information that facilitates resolution and quality scalability.

First claim

The invention claimed is:

1. A method for encoding spatial data sets, comprising a hierarchically organized set of breakpoints that identify discontinuities that may exist on the arcs formed between points on a hierarchical grid, the steps of performing a breakpoint dependent transformation of the spatial data samples, the step of scalable encoding of the transformed spatial data samples, the step of partitioning the breakpoints into one subset known herein as vertex breakpoints and another subset of non-vertex breakpoints, the step of scalable encoding of the vertex breakpoints, such that their locations are successively refined by the appearance of progressively more bits from an embedded bit-stream, and the step of inferring the locations of the non-vertex breakpoints from vertex breakpoints in coarser levels of the hierarchy or the same level of the hierarchy.

2. The method of claim 1 , wherein vertex breakpoints are assigned non-zero numerical values, herein known as vertex values, that identify the location of the vertex within its arc, and arcs that contain no vertex breakpoint are assigned a vertex value of zero, wherein the vertex values are subjected to an embedded bit-plane coding procedure, such that successive bit-planes of the representation provide successively more accurate information about the location of vertex breakpoints.

3. The method of claim 2 , wherein the vertex values are integers, with a sign-magnitude representation, where the most significant non-zero magnitude bit identifies the presence of a vertex breakpoint, the sign bit identifies whether the vertex breakpoint occurs in a first or a second half of the arc's line segment, and each successively less significant bit of the magnitude representation, after the first non-zero magnitude bit, refines the location of the breakpoint by a factor of two.

4. The method of claim 1 , wherein the hierarchical grid is organized into levels, such that the grid points in each level correspond to the sample locations in the spatial data set whose horizontal and vertical coordinates are both divisible by a whole number known herein as the level divisor, wherein the hierarchical grid has a dyadic structure, in which the finest level of the hierarchy has a level divisor of one, the second finest level of the hierarchy has a level divisor of two, and so forth, each successive level having a level divisor that is twice as large as that of the next finer level.

5. The method of claim 4 , wherein the arcs formed in each level consist of non-root arcs and root arcs, where the non-root arcs are formed between end grid-points that are two grid points apart and have coordinates that are both divisible by twice the level divisor, while the root-arcs are formed between end grid-points that are two grid points apart with one coordinate divisible by twice the level divisor, but not the other coordinate, this means that the line segments that connect the end grid points of both root arcs and non-root arcs have horizontal and vertical orientations on the grid; moreover root arcs appear in intersecting pairs, such that the horizontal and vertical root arcs in each intersecting pair have their line segments bisected by a grid point whose coordinates are both odd multiples of the level divisor.

6. The method of claim 5 , wherein each non-root arc that has no vertex breakpoint of its own is assigned an inferred non-vertex breakpoint at the same location as a breakpoint on the arc from the next coarser level of the hierarchy whose line segment contains that of the non-root arc, herein known as the non-root arc's parent arc, except where said parent arc does not exist or has no breakpoint, wherein non-vertex breakpoints are inferred on one or both of the root arcs in an intersecting pair, based on the occurrence and locations of breakpoints within the four adjoining non-root arcs in the same level of the hierarchy.

7. The method of claim 4 , wherein the breakpoint dependent transform starts from the finest level of the hierarchy, in which the original spatial data set is used to initialize input samples for each grid point, and progresses to the coarsest level of the hierarchy, performing the following steps for each level:
(a) the input values at each grid point are transformed into a set of output values at each grid point, using a breakpoint dependent transformation procedure;
(b) the output values for those grid points whose coordinates are both even multiples of the level divisor are transferred to the corresponding grid points in the next coarser level of the hierarchy, if any, as input values for that level; and
(c) the remaining output values for the level are interpreted as subband samples.

8. The method of claim 7 , wherein the input values for a level of the hierarchy are transformed into output values through a sequence of prediction steps, where in each prediction step, one subset of the input values is predicted from another subset of the input values, in a manner that depends upon the presence or absence of breakpoints, and the predicted input values are replaced by prediction residuals.

9. The method of claim 7 , wherein the grid points of a level are partitioned into cosets and the input values at the grid points belonging to each coset are progressively transformed into output values for the grid points of each coset through a sequence of prediction and update lifting steps, where each lifting step modifies the values within one coset by the addition of a linear combination of values from the other cosets and said linear combination depends upon the presence or absence of breakpoints, wherein three cosets are employed, the first consisting of those grid points whose coordinates are both even multiples of the level divisor, the second consisting of those grid points for which one coordinate is an odd multiple of the level divisor and the other coordinate is an even multiple of the level divisor, and the third consisting of those grid points for which both coordinates are odd multiples of the level divisor, where a first lifting step serves to predict the second coset from the first, a second lifting step serves to update the first coset based on the prediction residuals formed in the second coset by the first lifting step, a third lifting step serves to predict the third coset from the first and second cosets, a final lifting step serves to update the first and second cosets based on the prediction residuals formed in the third coset by the third lifting step, and all lifting steps are dependent on the presence or absence of breakpoints.

10. The method of claim 7 , wherein the subband samples from each level of the hierarchy are arranged into two dimensional data arrays, four for the coarsest level of the hierarchy, and three for the other levels, each rectangular array being partitioned into rectangular blocks known as subband code-blocks, where each subband code-block is independently subjected to an embedded bit-plane coding procedure.

11. The method of claim 5 , wherein the bit-stream segments produced by successive coding passes of the embedded bit-plane coding procedure for each arc-band code-block are grouped into a succession of arc-band quality layers, wherein the assignment of bit-stream segments to arcband quality layers is performed in such a way as to approximately minimize a lagrangian rate-distortion objective in which the lagrangian parameters are monotonically decreasing from the first to the last quality layer, and the distortion for a quality layer corresponds to the expected squared error distortion of the reconstructed spatial data set when all subsequent arc-band quality layers are unavailable during decoding.

12. A metho

Assignees

• Newsouth Innovations Pty Ltd

Inventors

• Taubman David Scott
• Mathew Reji Kuruvilla
• Zanuttigh Pietro

Classifications

• H04N19/167

  Position within a video image, e.g. region of interest [ROI] · CPC title

• H04N19/60

  using transform coding · CPC title

• H04N19/597

  specially adapted for multi-view video sequence encoding · CPC title

• G06T9/00 Primary

  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 title

• H04N19/176 Primary

  the region being a block, e.g. a macroblock · CPC title