Multi-overlay variable support and order kernel-based representation for image deformation and view synthesis

Abstract

A technique for displaying 3D videos creates a representation of image deformation, such as depth maps, in terms of a function for overlaying kernels with variable support and order. By optimizing the kernel type, order and support, which are allowed to be varied across different region of the deformation, it is able to approximate the image deformations in terms of the kernel parameters. Since the number of kernel parameters is usually much smaller than that of the number of pixels, this allows a significant reduction in the storage size of the image deformation.

Claims

1. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing image deformation information in the form of depth maps as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; and using variable scale and differential category coding for compression of parameters of the kernels; and using inter-frame and/or over space prediction under changes in the position of a camera that generated the deformation information so that the method codes only the required camera compensation model and motion descriptors, predicts the scale and the sign of the kernel parameters, and codes the scale and sign difference.

2. The method of claim 1 wherein type, order and support of the kernel may be varied across different regions of the deformation, and the deformation is approximated in terms of the parameters of the kernel.

3. The method of claim 1 wherein the overlay of different objects with large depth difference is handled by considering multiple layers of the representation, in which the kernel representation of occluded objects can be approximated by inpainted data.

4. The method of claim 1 wherein the coding includes inter-coding, in which a sequence of image deformations can be coded using a reference kernel representation, a global camera compensation model or motion descriptors.

5. The method of claim 1 wherein the coding uses algorithms that focus on encoding the redundancies among integers or fixed-point numbers.

6. A method of decoding image deformation information encoded according to claim 1 into a data structure that includes overhead (in the form of an indicator of fix/variable support F/V, the number of kernels per column Px, number of kernels per row Py, kernel bandwidth/support in the x-direction hx,p and kernel bandwidth/support in the y-direction hy,p, scaling parameters and the maximum kernel order Lp or mod e.sub.p) followed by the kernel parameters, comprising the steps of: (1) reading the pad length PL, and the difference of binary digits between adjacent categories .sup.Q; (2) reading the symbols .sup.isDiff, .sup.Diff, Ref and .sup.IsSign, if they are compressed, decompress them using their respective dictionaries; (3) decoding the first chunk/block by reading the first symbol in the de-compressed .sup.isDiff, which contains all the symbols for indicating whether there is change in category for each of the kernel parameters; (4) creating .sup.v=1, 2, . . . V variables for storing the categories for the .sup.V parameters, for each of the variables .sup.v=2, 3, . . . V, if the .sup.v-th bit of the .sup.isDiff symbol is 1, read a symbol from .sup.Diff, adding the difference to the .sup.v-th variable; reading the first Ref symbol, add the reference category to each of the .sup.v-th variable and save the 1.sup.st variable as the reference category; (5) after obtaining the categories for the .sup.V parameters, obtaining the word length of each of the parameters and then reading the .sup.V parameters from the data-stream in accordance with the obtained word lengths; and (6) repeating steps (2)-(5) for subsequent chunks/blocks.

7. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing the image deformation as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; using variable scale and differential category coding for compression of parameters of the kernels; and wherein the support can be in any arbitrary shape, such as rectangles, parallelograms or polygons; the topological space represented by the support can be connected or disconnected; and the support can be fixed or variable.

8. The method of claim 7 wherein, in the fixed support mode the kernel order L.sub.p=1 and L.sub.p=2 can be represented as 0 and 1 respectively, and further using a lossless compression technique, such as an entropy coding method, to further compress the kernel order; and in the variable support mode, further compressing mode.sub.p using a lossless compression technique.

9. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing the image deformation as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; using variable scale and differential category coding for compression of parameters of the kernels; and wherein the representations can be matted together to form a multi-overlay representation, and opacity can be incorporated in each different overlay representation to support semi-transparency and reflective applications.

10. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing the image deformation as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; using variable scale and differential category coding for compression of parameters of the kernels; and wherein the support and order are in fixed support, vertical split/merge support or horizontal split/merge support.

11. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing the image deformation as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; using variable scale and differential category coding for compression of parameters of the kernels; and wherein the kernel parameters can be efficiently computed using a multiplier-less maximum likelihood approach, which can be executed sequentially or in parallel.

12. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing the image deformation as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; using variable scale and differential category coding for compression of parameters of the kernels; and wherein the objects in the foreground are segmented from the image deformation, then the image deformation at each of the objects is represented by a different overlay of kernel representation, and then the remaining background is represented by another layer of kernel representation.

13. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing the image deformation as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; using variable scale and differential category coding for compression of parameters of the kernels; and wherein the coding includes inter-coding, which is to perform inter-frame and/or over space (inter-view) prediction under changes (such as camera position) and code only the required motion parameters and new overlay layers in kernel representation.

14. The method of claim 13 including the step of compensating for global deformation, such as camera motion position of the background layer from time to time,. using a global camera compensation method.

15. The method of claim 14 wherein the deformation model is an affine54 model or a general projective transformation, and further including the steps of: detecting major motion objects and their location deformation parameters; if the motion compensation is satisfactory, compressing the resulting parameters using entropy coding; for areas where local motion compensation is unsatisfactory, coding another overlaying layer in the kernel representation; and using the motion descriptors and the new layer of kernel representation at time t, to reconstruct the kernel representation at time t+1.

16. A method of representing image deformation information for broadcast and/or storage, comprising the steps of: representing the image deformation as a function of multiple kernels that can overlay each other and have support and order, wherein objects and background are assigned to different overlays; using variable scale and differential category coding for compression of parameters of the kernels; and wherein the variable scale and differential category coding comprises the steps of: scaling the kernel parameters to fixed-point integers; performing quantization of the integers; further compressing the numbers using differential category coding whereby the parameters are grouped according to their number of binary digits according to a category table; and determining the difference of binary digits between adjacent categories.

17. The method of claim 16 wherein the variable scale differential category coding comprises the steps of: dividing all of the kernel parameters into chunks of V parameters; treating the first kernel parameter in each chunk as a reference parameter; storing the category of the reference parameter as the symbol .sup.ref; pg,34 obtaining the categories of all L parameters from the category table and at the same time, detecting whether there is a difference between the sign of the reference parameter and other remaining parameters, the pattern of which is represented using the symbol .sup.isSign; using a symbol .sup.isDiff to represent whether there is difference in category between the reference parameter and other parameters; and computing the actual difference in category for the parameters that belong to categories different from the reference parameter and using a symbol .sup.Diff to store the difference for each of the parameters.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The present invention can be more fully understood by the following detailed description of the preferred embodiments, with reference made to the accompanying drawings, wherein:

(2) FIG. 1a is an overview of conventional image domain warping and FIG. 1b is an overview of a kernel representation for view synthesis according of the present invention;

(3) FIG. 2a shows support of kernel representation in a column major ordering and FIG. 2b shows overlapping regions of the kernels according to the present invention;

(4) FIG. 3a shows a three-dimensional plot of the weighing factor for K.sub.p and FIG. 3b shows a contour plot of the weighing actor for K.sub.p according to the present invention;

(5) FIG. 4a illustrates a variable support of a kernel representation with vertical split/merge mode and FIG. 4b shows overlapping regions of the kernels according to the present invention;

(6) FIG. 5 illustrates the data structure of a kernel representation according to the present invention;

(7) FIG. 6 illustrates the data structure of a kernel representation with fixed support according to the present invention;

(8) FIG. 7 illustrates the data structure of a kernel representation with variable support according to the present invention;

(9) FIG. 8a shows a vertical split/merge variable support and FIG. 8b shows a horizontal vertical split/merge variable support according to the present invention;

(10) FIG. 9 shows the procedure for differential category coding for Q=2 according to the present invention; and

(11) FIG. 10 illustrates the data structure for differential category coding according to the present invention.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS OF THE INVENTION

(12) Mathematical Foundation

(13) Consider a pixel i(x,y) of an image I with resolution MN, where M is the number of pixel columns (width) and N is the number of pixel rows (height). x=1, 2, . . . M and y=1, 2, . . . N are the x and y coordinates of the pixel. Conventionally, the image deformation of each pixel i(x,y) can be represented as a displacement denoted by d(x,y). They can be re-written in the matrix form
D=[d.sub.1,d.sub.2, . . . ,d.sub.M], where d.sub.x=[d(x,1),d(x,2), . . . ,d(x,N)].sup.T.(1)

(14) In view synthesis, the positions of the original pixel i(x,y) in the V views are computed. The new position at the v-th view is i.sub.v(x,y), where v=1, 2, . . . , V. In the conventional representation of, the relationship of i.sub.v(x,y) and i(x,y) is given as
i.sub.v(x,y)=(x,y,v)=(i(x,y),d(x,y),v),(2)
where () is a synthesis function that modifies the position of i(x,y) to synthesize the v-th view of I. See the Stefanoski article and the article Kauff et al., Depth map creation and image-based rendering for advanced 3DTV services providing interoperability and scalability, Signal Processing: Image Communication, vol. 22, no. 2, pp. 217-234, February 2007, which is incorporated herein by reference in its entirety. For example, in generating two views from the image I and its deformation map D, i.e. v=1, 2, () can be chosen as

(15) $\left(i\left(x,y\right),d\left(x,y\right),v\right)=\{\begin{array}{cc}i\left(x,y\right)-d\left(x,y\right)/2& v=1\\ i\left(x,y\right)+d\left(x,y\right)/2& \mathrm{otherwise}\end{array}.$
In general, the synthesis function () can be a non-linear function of i(x,y), d(x,y) and v.

(16) Suppose the bit per pixel of the image deformation matrix D is 8, the data rate of D for a 1080p 30 frame per second video is data rate=(bit per pixelframe per secondMN)/10.sup.6=(83019201080)/10.sup.6=497 Mbps. Such a high data rate is undesirable for many applications. Moreover, a major limitation of conventional approaches is that there is no overlay. Consequently, it cannot support semi-transparent and reflective objects. In order to overcome this problem, a novel kernel representation is proposed for image deformation, in which the kernels can overlay with each other to provide for occlusion and matting of objects.

(17) FIG. 1. An overview of the proposed kernel representation for view synthesis. Each of the overlays, which can be semi-transparent, contains a deformation map D.sub.j and opacity .sub.j. Each of these quantities can be represented using a kernel representation with an arbitrary support. The degree of transparency and opacity can also be represented similarly using the kernel representation. The shape of the object can be further encoded using a shape codec and it can be used to further used to sharpen the image deformation of the object.

(18) The image deformation of the objects and the background are assigned to different overlays, each of which contains the deformation d(x,y) and the degree of transparency (x,y). This provides the flexibility for the user to choose whether to show the overlay or the occluded objects hidden by the overlay. The shape of each object can be further compressed using a shape codec and this shape information can be further used to sharpen the image deformation of the object. Both the image deformation d(x,y) and the transparency (x,y) can be represented by a function of different kernels, a.k.a. approximation functions in reproducing kernel Hilbert spaces. See, E. W. Cheney et al., A course in approximation theory, Brooks, (2000), which is incorporated herein by reference in its entirety. First, the objects in the foreground have to be segmented from the image deformation, e.g., using some clustering algorithms. Afterwards, the image deformation at each of the objects is represented by a different overlay of kernel representation. Finally, the remaining background is represented by another layer of kernel representation. More precisely, suppose there are J objects and the background in an image. The image deformation map D can be decomposed into J+1 overlays, i.e. D.sub.j, j=1, 2, . . . , J+1, where the first J overlays represent the objects and the J+1-th overlay represents the background, each of which is associated with a transparency or opacity value .sub.j. Let d.sub.j(x,y) and .sub.j(x,y) be the (x,y)-th element of D.sub.j and .sub.j respectively. In order to compress the data size of D.sub.j, D.sub.j is approximated as a function of different kernels, e.g., a linear combination, which is given as

(19) $\begin{array}{cc}{d}_j\left(x,y\right)f_j\left(K_{1,j}\left(a_{1,j}\right),K_{2,j}\left(a_{2,j}\right),\mathrm{.Math.},K_{P,j}\left(a_{P,j}\right)\right)=\underset{p=1}{\overset{\mathrm{Pj}}{.Math.}}{W}_{p,x,y,j}{K}_{p,j}\left(\frac{x-c_{x,p,j}}{h_{x,p,j}},\frac{y-c_{y,p,j}}{h_{y,p,j}},a_{p,j}\right),& \left(3a\right)\\ a_j\left(x,y\right)f_{a,j}\left(K_{1,j}\left(a_{1,k}\right),K_{2,j}\left(a_{2,j}\right),\mathrm{.Math.},K_{P,j}\left(a_{P,j}\right)\right)=\underset{p=1}{\overset{\mathrm{Pj}}{.Math.}}{w}_{,p,x,y,j}{K}_{p,j}\left(\frac{x-c_{x,p,j}}{h_{x,p,j}},\frac{y-c_{y,p,j}}{h_{y,p,j}},a_{,p,j}\right),& \left(3b\right)\end{array}$

(20) where f.sub.j(K.sub.1,j(a.sub.1,j), K.sub.2,j(a.sub.2,j), . . . , K.sub.P,j(a.sub.P,j)) is a function of K.sub.p,j(x,y,a.sub.p,j) to approximate d.sub.j(x,y) and K.sub.p,j(x,y,a.sub.p,j) is the p-th kernel function for the j-th layer, c.sub.x,p,j and c.sub.y,p,j are the centering parameters associated with the p-th kernel. w.sub.p,x,y is the weight of the kernel. P.sub.j is the number of kernels. h.sub.x,p,j and h.sub.y,p,j are the bandwidths of the kernel. a.sub.p,j and a.sub.,p,j are the kernel parameters of the image deformation and the transparency/opacity and they can be computed using a parameter estimation method, such as the distributed maximum likelihood method (DMLE) described in sub-section C. Hence, the synthesis function in equation (2) can be re-written as
i.sub.v,j(x,y)=(x,y,d.sub.j(x,y),v), and(4a)
i.sub.v(x,y)=.sub.j=1.sup.Ji.sub.v,j(x,y)=.sub.j=1.sup.J.sub.j(x,y,j,v),(4b)

(21) where d.sub.j(x,y) and .sub.j(x,y) can be approximated as in equation (3). Unlike the view synthesis that employs the conventional representation as in equation (2), which requires storage of all the image deformation values d(x,y) for constructing the synthesis function, the proposed kernel representation allows the construction of the synthesis function using only a few kernel parameters, the number of which is much smaller than the size of the image deformation D. As a result, the data rate can be reduced. For notation convenience, the approximation of j-th overlay of the image deformation d.sub.j(x,y) is retained and the index j in the remaining sections is omitted. The transparency/opacity .sub.j(x,y) can also be approximated similarly. Different kernels K.sub.p(x,y,a.sub.p) can be chosen, such as uniform, polynomial, triangular, spline, Epanechnikov, Logistic kernels, etc. In particular, when K.sub.p(x,y,a.sub.p) is chosen as a polynomial kernel, it can be written as

(22) $\begin{array}{cc}{K}_p\left(x,y,a_p\right)=\{\begin{array}{cc}{a}_{0,p}+\underset{l=1}{\stackrel{L}{.Math.}}\underset{k=0}{\overset{l}{.Math.}}{}_{l-k,k,p}{x}^{l-k}{y}^k& \left(x,y\right)\mathrm{Supp}\left(K_p\left(x,y,a_p\right)\right)\\ 0& \mathrm{otherwise}\end{array},& \left(5\right)\end{array}$

(23) where a.sub.p=[a.sub.0,p, a.sub.1,0,p, a.sub.0,1,p, a.sub.2,0,p, . . . , a.sub.0,L,p].sup.T are the kernel parameters. L.sub.p is the kernel order, a.sub.l,k,p are the kernel parameters. The order L.sub.p is allowed to vary across different kernels p=1, 2, . . . , P. If L.sub.p=2, K.sub.p(x,y,a.sub.p)=a.sub.0,p+a.sub.1,0,px+a.sub.0,1,py+a.sub.2,0,px.sup.2+a.sub.1,1,pxy+a.sub.0,2,py.sup.2 if (x,y)supp(K.sub.p(x,y,a.sub.p)) or 0 otherwise. supp(K.sub.p(x,y)) is the support of K.sub.p(x,y), i.e. the region where K.sub.p(x,y,a.sub.p) is non-zero. The support could be in any arbitrary shape and the topological space it represents could be connected or disconnected, such as rectangles, parallelograms or polygons. The kernel can also be separable or non-separable. See the Cheney text. For example, if a rectangular support is chosen, supp

(24) $\left(K_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right)\right)$
can be written as

(25) $\begin{array}{cc}\mathrm{supp}\left(K_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right)\right)=\left\{x\left[c_{x,p}-h_{x,p},c_{x,p}+h_{x,p}\right],y\left[c_{y,p}-h_{y,p},c_{y,p}+h_{y,p}\right]\right\}.& \left(6\right)\end{array}$

(26) From equation (6), it can be seen that the bandwidths h.sub.x,p and h.sub.y,p are also the support of the kernel

(27) $K_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right).$
Since the kernel order L.sub.p and the support (h.sub.x,p and h.sub.y,p) are allowed to be varied for all kernels K.sub.p(x,y), p=1, 2, . . . , P, this can be referred to as a kernel representation with variable order and support. The support of

(28) $K_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right)$
in equation (6) can also be chosen to overlap with the support of the other kernels.

(29) The weighing factor must satisfy w.sub.p,x,y[0,1]. If a non-overlapping kernel representation is chosen, w.sub.p,x,y is chosen as w.sub.p,x,y=1 and extra smoothing or filtering should be employed to smoothen the possible discontinuities across the kernel boundaries. Whereas in a overlapping kernel representation, w.sub.p,x,y is chosen as

(30) $\begin{array}{cc}{w}_{p,x,y}=\{\begin{array}{cc}1& x,y{S}_{p,\mathrm{non}\_\mathrm{overlap}}\\ \left(p,x,y\right)& x,y{S}_{p,\mathrm{overlap}}\\ 0& \mathrm{otherwise}\end{array},& \left(7\right)\end{array}$

(31) where S.sub.p,overlap is the subset of supp

(32) $\left(K_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right)\right)$
which overlaps with the support of other kernels. S.sub.p,non_overlap is the non-overlapping subset such that

(33) 0$S_{p,\mathrm{non}\_\mathrm{overlap}}=\mathrm{supp}\left(K_p\right).Math.\underset{ip}{.Math.}\mathrm{supp}\left(K_i\right).$
Hence, supp

(34) $\left(K_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right)\right)=S_{p,\mathrm{non}\_\mathrm{overlap}}.Math.S_{p,\mathrm{overlap}}.$
For other regions that do not lie within the support of K.sub.p, w.sub.p,x,y=0. (p,x,y)[0,1] is a weighing factor to allow a smooth transition of the approximated image deformation at the kernel boundaries and it is chosen in a manner that satisfies the following:

(35) For each x, y, the sum of all weighing factor w.sub.p,x,y at x, y must be 1, i.e.

(36) $\begin{array}{cc}\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}=1.& \left(8\right)\end{array}$

(37) In the following example of a kernel representation with a fixed support, there is an illustration of how (p, x, y) can be particularly chosen.

(38) The simplest form is a fixed support kernel with a rectangular shape with support h.sub.x,p=h.sub.x and h.sub.y,p=h.sub.y. FIG. 1a shows the support of the kernels

(39) $K_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right),$
p=1, 2, . . . , P.sub.y, P.sub.y+1, . . . 2P.sub.y, . . . P in a column major ordering, i.e. the index p is expressed as p=mP.sub.y+n. c.sub.x,p=floor(p/N)floor(M/P.sub.x) and c.sub.y,p=floor(N/P.sub.y)mod(p,N). floor( ) and mod( ) are the floor and modulo operators. In general, the kernels can also be represented in a row major ordering. FIG. 2b shows the support of four adjacent kernels extracted from FIG. 2a, in which m[1,M1], n[1,N1]. Each of the kernels, i.e. K.sub.(m1)P.sub.y.sub.+n1, K.sub.(m1)P.sub.y.sub.+n, K.sub.mP.sub.y.sub.+n1, and K.sub.p, has a horizontal support h.sub.x and a vertical support h.sub.y. The overlapping regions are shown as region A, B, and C respectively. Region A contains pixels that lie in the overlap of the four kernels. Whereas in regions B and C, they are regions with two overlapping kernels. Consider the computation of kernel parameters in K.sub.p, the support of which contains only region A, B, C, D, E, F, G, H and its non-overlapping region. The weighing factor of kernel K.sub.p can be chosen as

(40) $\begin{array}{cc}{w}_{p,x,y}=\{\begin{array}{cc}1& x,y{S}_{p,\mathrm{non}\_\mathrm{overlap}}\\ \left(p,x,y\right)& x,y{S}_{p,\mathrm{overlap}}\\ 0& \mathrm{otherwise}\end{array},& \left(9\right)\end{array}$

(41) where (p, x, y) are chosen as

(42) Region A:

(43) $\begin{array}{cc}\left(p,x,y\right)=\left(\frac{x-c_{x,p}}{h_{x,o}}\right)\left(\frac{y-c_{y,p}}{h_{y,o}}\right)& \left(10a\right)\end{array}$
Region B:

(44) $\begin{array}{cc}\left(p,x,y\right)=\left(\frac{x-c_{x,p}}{h_{x,o}}\right),& \left(10b\right)\end{array}$
Region C:

(45) $\begin{array}{cc}\left(p,x,y\right)=\left(\frac{y-c_{y,p}}{h_{y,o}}\right),& \left(10c\right)\end{array}$
Region D:

(46) $\begin{array}{cc}\left(p,x,y\right)=\left(\frac{x-c_{x,p}}{h_{x,o}}\right)\left(1-\frac{y-\left(c_{y,p}+h_y-h_{y,o}\right)}{h_{y,o}}\right),& \left(10d\right)\end{array}$
Region E:

(47) $\begin{array}{cc}\left(p,x,y\right)=1-\left(\frac{y-\left(c_{y,p}+h_y-h_{y,o}\right)}{h_{y,o}}\right),& \left(10e\right)\end{array}$
Region F:

(48) 0$\begin{array}{cc}\left(p,x,y\right)=\left(1-\frac{x-\left(c_{x,p}+h_x-h_{x,o}\right)}{h_{x,o}}\right)\left(\frac{y-c_{y,p}}{h_{y,o}}\right),& \left(10f\right)\end{array}$
Region G:

(49) $\begin{array}{cc}\left(p,x,y\right)=1-\left(\frac{x-\left(c_{x,p}+h_x-h_{x,o}\right)}{h_{x,o}}\right),& \left(10g\right)\end{array}$
Region H:

(50) $\begin{array}{cc}\left(p,x,y\right)=\left(1-\frac{x-\left(c_{x,p}+h_x-h_{x,o}\right)}{h_{x,o}}\right)\left(1-\frac{y-\left(c_{y,p}+h_y-h_{y,o}\right)}{h_{y,o}}\right).& \left(10h\right)\end{array}$

(51) FIGS. 3a and 3b show a three-dimensional and contour plot of the weighing factor for K.sub.p respectively. It can be shown that all the weighing factors

(52) $\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}$
sum to 1 for all overlapping regions A to H. For example, at region A,

(53) $\begin{array}{c}\underset{p=1}{\overset{P}{.Math.}}=w_{p,x,y}+w_{p-P_y,x,y}+w_{p-1,x,y}+w_{p-P_y-1,x,y}\\ =\left(p,x,y\right)+\left(p,x-h_x,y\right)+\left(p,x,y-h_y\right)+\\ \left(p,x-h_x,y-h_y\right)\\ =\left(\frac{x-c_{x,p}}{h_{x,o}}\right)\left(\frac{y-c_{y,p}}{h_{y,o}}\right)+\left(1-\frac{x-c_{x,p}}{h_{x,o}}\right)\left(\frac{y-c_{y,p}}{h_{y,o}}\right)+\\ \left(\frac{x-c_{x,p}}{h_{x,o}}\right)\left(1-\frac{y-c_{y,p}}{h_{y,o}}\right)+\left(1-\frac{x-c_{x,p}}{h_{x,o}}\right)\left(1-\frac{x-c_{y,p}}{h_{y,o}}\right)=1.\end{array}$

(54) The weighing factor can be chosen similarly in a manner that it satisfies

(55) $\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}=1.$
Consider a kernel representation with variable support shown in FIGS. 4a and 4b. From FIG. 4a, the horizontal and vertical support of K.sub.1 are 2h.sub.x and 2h.sub.y respectively. Whereas for K.sub.2 to K.sub.7, and K.sub.10, the supports are h.sub.x and h.sub.y. For K.sub.8, K.sub.9, K.sub.11, and K.sub.12, the supports are h.sub.xx and h.sub.ys. Consider the overlapping regions of K.sub.7, as shown in FIG. 3b. The same weighing factors w.sub.p,x,y for regions A to H can be chosen as in equation (10). For region I and J, w.sub.p,x,y should be chosen as the weighing factor in region E, i.e.

(56) $\left(p,x,y\right)=1-\left(\frac{y-\left(c_{y,p}+h_y-h_{y,o}\right)}{h_{y,o}}\right).$
For K.sub.1, the same w.sub.p,x,y should be chosen in region A and B, i.e.

(57) $\left(p,x,y\right)=1-\left(\frac{x-\left(c_{x,p}+h_x-h_{x,o}\right)}{h_{x,o}}\right).$
because they lay on the right edge of K.sub.1. It can be shown that these chosen w.sub.p,x,y will also satisfy the condition

(58) $\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}=1.$
For example, in region A,

(59) $\begin{array}{cc}\begin{array}{c}\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}=w_{7,x,y}+w_{1,x,y}+w_{6,x,y}=\left(\frac{x-c_{x,7}}{h_{x,o}}\right)\left(\frac{y-c_{y,7}}{h_{y,o}}\right)+\\ \left(1-\frac{x-c_{x,7}}{h_{x,o}}\right)+\\ \left(\frac{x-c_{x,7}}{h_{x,o}}\right)\left(1-\frac{y-c_{y,7}}{h_{y,o}}\right)\\ =\left(\frac{x-c_{x,7}}{h_{x,o}}\right)\\ \left(\frac{y-c_{y,7}}{h_{y,o}}+1-\frac{y-c_{y,7}}{h_{y,o}}\right)+\\ \left(1-\frac{x-c_{x,7}}{h_{x,o}}\right)\\ =\left(\frac{x-c_{x,7}}{h_{x,o}}\right)+\left(1-\frac{x-c_{x,7}}{h_{x,o}}\right)=1.\end{array}& \left(12\right)\end{array}$

(60) The kernel parameters can be estimated using a distributed maximum likelihood estimation (MMLE) approach. In general, the kernel parameters can be obtained from a parameter estimation method. A multiplier-less maximum likelihood estimation (MMLE) approach is used and the kernel representation in equation (4) can be re-written as

(61) 0$\begin{array}{cc}d\left(x,y\right)=\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}{K}_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}},a_p\right)+e\left(x,y|a_p\right),& \left(13\right)\end{array}$

(62) where e(x,y|a.sub.P) is the approximation error at the pixel at position (x,y) given the parameters a.sub.p. A maximum likelihood estimator can be used to obtain a.sub.p, which is given as

(63) $\begin{array}{cc}\max \left(L\left(a_p\right)\right)=\max (\underset{x,y}{.Math.}p\left(e\left(x,y|a_p\right)\right),& \left(14\right)\end{array}$

(64) where p(e(x,y|a.sub.p)) is the probability density function of e(x,y). For example, if the error e(x,y) is modeled using a Gaussian model with zero mean and variance .sup.2, i.e. e(x,y)N(0,.sup.2), the probability density function (pdf) of e(x,y) can be written as

(65) $\begin{array}{cc}p\left(e\left(x,y|a_p\right)\right)=\frac{1}{\sqrt{2{}^2}}\exp (\frac{-1}{2{}^2}(d\left(x,y\right)-\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}{K}_p{\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}},a_p\right))}^2).& \left(15\right)\end{array}$

(66) The likelihood function of a.sub.p, denoted by L(a.sub.p) is given as

(67) $\begin{array}{cc}L\left(a_p\right)=\underset{x,y}{.Math.}p(e\left(x,y|a_p\right)={\left(2{}^2\right)}^{-\mathrm{MN}/2}\underset{x,y}{.Math.}\exp (\frac{-1}{2{}^2}{\left(d\left(x,y\right)-\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}{K}_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}},a_p\right)\right)}^2).& \left(16\right)\end{array}$

(68) The solution to equation (16) is
For p=1,2, . . . ,P, a.sub.p=(.sub.p.sup.TW.sub.p.sup.2.sub.p).sup.1.sub.p.sup.TW.sub.p.sup.2d.sub.p.(17)

(69) The iteration can be executed sequentially or in parallel. For a limited choice of h.sub.x,p and h.sub.x,p, the matrices (.sub.p.sup.TW.sub.p.sup.2.sub.p).sup.1 and .sub.p.sup.TW.sub.p.sup.2 are fixed and can be pre-computed offline and the computation of a.sub.p can be implemented in a multiplier-less manner. For example, in the variable support schemes proposed, the matrix (.sub.p.sup.TW.sub.p.sup.2.sub.p).sup.1 can be pre-computed for each of the modes in equation (27). To further reduce the complexity, the image deformation map D can be decimated, which can reduce the dimension of W.sub.p and d.sub.p in applying equation (17) to compute the parameters.

(70) The model order L.sub.p can be chosen by a hypothesis test using the following null and alternative hypotheses

(71) $\begin{array}{cc}{H}_0\text{:}{a}_{0,p}=a_{1,0,p}=a_{1,1,p}=a_{2,0,p}=\mathrm{.Math.}=a_{1,k,p}=0,& \left(18a\right)\\ H_1\text{:}{a}_{l,k,p}0.& \left(18b\right)\end{array}$

(72) A test statistic is required for a hypothesis test, such as a wald-type test, t-test, Chi-square test and etc., as described in K. Mardia et al., Multivariate Analysis, Academic Press, 1980.

(73) FIG. 5 shows the data structure of the kernel representation, which is made up of an overhead and kernel parameters. As the overhead and kernel parameters are numbers, they can be converted to a binary format for storage in a digital system or transmitted through a communication channel, such as the computer network. The size of the converted data structure can be determined by counting the number of binary digits or bits. The number of bits required for storing the data structure of the kernel representation is

(74) $\begin{array}{cc}\mathrm{bits}\mathrm{for}\mathrm{kernel}\mathrm{data}\mathrm{structure}=\mathrm{overhead}+B_p\left(\underset{l=1}{\overset{L}{.Math.}}{P}_l{}_l\right),& \left(19\right)\end{array}$

(75) where B.sub.p is the number of bits per kernel parameter and .sub.l are the number of parameters for a kernel with order l and P.sub.l is the number of kernels with order l and

(76) $\underset{l=1}{\overset{L}{.Math.}}{P}_l=P.$
The number of parameters .sub.l for a kernel K.sub.p is determined from the following recurrence relationship .sub.l=.sub.l1+l+1, .sub.l=3, l=1, 2, . . . L. The recurrence relationship can be expressed as
.sub.l=(l+1)(l+2)/2.(20)

(77) The compression rate (CR) is defined as the ratio between the number of bits required to store the original image deformation matrix D and the total bits required to store the data structure of the kernel representation, which is given as

(78) $\begin{array}{cc}\mathrm{CR}=\frac{\mathrm{bits}\mathrm{for}\mathrm{storing}D}{\mathrm{bits}\mathrm{for}\mathrm{kernel}\mathrm{data}\mathrm{structure}}=\frac{\mathrm{bit}\mathrm{per}\mathrm{pixel}MN}{\mathrm{overhead}+B_p\left(\underset{l=1}{\overset{L}{.Math.}}{P}_l{}_l\right)}.& \left(21\right)\end{array}$

(79) The amount of overhead depends on the chosen support and order. Three different choices of the support and order are proposed: 1.) Fixed support, 2.) Vertical Split/Merge support and 3.) Horizontal Split/Merge support.

(80) Among the three different choices, the simplest form is a fixed support kernel with a rectangular shape, which is shown in FIG. 2a. FIG. 6 shows the data structure for the fixed support kernel in FIG. 2a. The overhead contains F/V, P.sub.x, P.sub.y, h.sub.x,p, h.sub.y,p, which are the indicator for fix/variable support, the number of kernels per column, number of kernels per row, kernel bandwidth/support in the x-direction and kernel bandwidth/support in the y-direction, respectively. P=P.sub.xP.sub.y. The kernel order L.sub.p for the p=1, 2, . . . , P-th kernel are also included. The overhead can be obtained as
overhead=B.sub.FV+B.sub.px+B.sub.py+B.sub.x+B.sub.y+B.sub.K+PB.sub.L+.sub.LB.sub.S.(22)

(81) where B.sub.FV, B.sub.px, B.sub.py, B.sub.x and B.sub.y are the bits required for storing F/V, P.sub.x, P.sub.y, h.sub.x,p and h.sub.y,p and they can be chosen as 16 bit integers. B.sub.K is the number of bit required to store the number of bit per kernel B.sub.p. B.sub.L is the number of bits required for storing a maximum order L=max(L.sub.p). B.sub.L=ceil(log.sub.2(L)), where ceil( ) is the ceiling operator. B.sub.S is the number of bits required to store the scaling parameter for fixed-point computation. Since each kernel parameter requires a different scaling, there will be totally .sub.L scaling parameter and the total number of bits required is .sub.LB.sub.S. Suppose the number of kernels is chosen as P=P.sub.xP.sub.y=256, the bit per kernel parameters is chosen B.sub.p=6 and the kernel order is fixed at L=2. B.sub.s is chosen as B.sub.s=22. The CR is given as

(82) $\begin{array}{cc}\mathrm{CR}=\frac{\mathrm{bit}\mathrm{per}\mathrm{pixel}MN}{B_{\mathrm{FV}}+B_{\mathrm{Px}}+B_{\mathrm{Py}}+B_x+B_y+P\left(B_L\right)+{}_L{B}_s+B_p\left(\underset{l=1}{\overset{L}{.Math.}}{P}_l{}_l\right)}=\frac{819201080}{1+16+16+16+16+256\left(1\right)+622+6\left(2566\right)}1715& \left(23\right)\end{array}$

(83) The total number of bits for storing the image deformation for a 1080p 30 fps video is only 966830290 kbps using the above data structure. In general, the compression ratio can be even higher if the kernel order L is allowed to vary between 1 and 2. The compression quality is usually evaluated in terms of signal-to-noise ratio (SNR)

(84) $\begin{array}{cc}\mathrm{SNR}=20{\log }_{10}\left(\frac{\mathrm{signal}}{\mathrm{approximation}\mathrm{error}}\right)=20{\log }_{10}\left(\frac{d\left(x,y\right)}{d\left(x,y\right)-\underset{p=1}{\overset{P}{.Math.}}{w}_{p,x,y}{K}_p\left(\frac{x-c_{x,p}}{h_{x,p}},\frac{y-c_{y,p}}{h_{y,p}}\right)}\right).& \left(24\right)\end{array}$

(85) Using the above configuration, the kernel representation is able to achieve a compression quality of SNR=21.47 dB.

(86) Image deformation may contain discontinuities. In order to improve the compression quality at these regions, the image deformation with vertical discontinuities can be represented using the kernel representation of vertical split/merge variable support, in which the vertical support is set to be longer than that of the horizontal support, i.e. h.sub.y,p>h.sub.x,p, and the support is allowed to vary, as shown in FIGS. 4a and 4b. In particular, the following choice is available, which is referred to as the vertical split/merge mode, and is defined as

(87) 0$\begin{array}{cc}{h}_{x,p}=\{\begin{array}{cc}2h_x& \begin{array}{c}\mathrm{No}\mathrm{dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{three}\\ \mathrm{neighbor}\mathrm{kernels}\mathrm{and}\mathrm{Kp}\mathrm{have}{L}_p=1\end{array}\\ 1/4h_x& \begin{array}{c}\mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{those}\mathrm{on}\\ \mathrm{the}\mathrm{left}\mathrm{are}\mathrm{significantly}\mathrm{larger},\end{array}\\ 1/2h_x& \mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\\ 3/4h_x& \begin{array}{c}\mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{those}\mathrm{on}\\ \mathrm{the}\mathrm{right}\mathrm{are}\mathrm{significantly}\mathrm{larger},\end{array}\\ 1& \mathrm{otherwise}.\end{array},\mathrm{and}& \left(25\right)\\ h_{y,p}=\{\begin{array}{cc}2h_y& \begin{array}{c}\mathrm{No}\mathrm{dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{three}\\ \mathrm{neighbor}\mathrm{kernels}\mathrm{and}\mathrm{Kp}\mathrm{have}{L}_p=1\end{array}\\ 1/2h_y& \mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\\ 1& \mathrm{otherwise}\end{array},& \left(26\right)\end{array}$

(88) where h.sub.y,p=2h.sub.x,p. A discontinuity detection test can be performed to identify whether the region {x[c.sub.x,ph.sub.x,p,c.sub.x,p+h.sub.x,p], y[c.sub.y,ph.sub.y,p, c.sub.y,p+h.sub.y,p]} has sufficient discontinuity. FIG. 7 shows the data structure of the kernel representation with variable support, which is similar to the fixed support counterpart shown in FIG. 6 except that the order L in the overhead is now replaced by mod e.sub.p, which store the type of chosen h.sub.x,p and h.sub.y,p:

(89) $\begin{array}{cc}{\mathrm{mode}}_p=\{\begin{array}{cc}0& h_{x,p}=h_x,h_{y,p}=h_y,L_p=1,\left(\mathrm{normal}\right),\\ 1& h_{x,p}=h_x,h_{y,p}=h_y,L_p=2,\left(\mathrm{normal}\right),\\ 2& h_{x,p}=2h_x,h_{y,p}=2h_y,L_p=1,\left(\mathrm{merge}\right),\\ 3& h_{x,p}=h_x/2,h_{y,p}=h_y/4,L_p=2,\left(\mathrm{split}\right),\\ 4& h_{x,p}=h_x/2,h_{y,p}=h_y/2,L_p=2,\left(\mathrm{split}\right),\\ 5& h_{x,p}=h_x/2,h_{y,p}=3h_y/4,L_p=2,\left(\mathrm{split}\right),\end{array}& \left(27\right)\end{array}$

(90) In this choice, the model order is allowed to vary only in the normal mode. Whereas in the merge mode and the split mode, the model orders are fixed to L.sub.p=1 and L.sub.p=2 respectively. This is to reduce the number of bits in the overhead. Since L.sub.p will always equal to 1 when the merge mode as in equations (25) and (26), it is unnecessary to reserve a mode for L.sub.p=2 for the merge mode. On the other hand, a motivation in using the split mode is to improve the approximation quality of the kernel representation at the discontinuity. Hence, it is reasonable to use the higher order, i.e. L.sub.p=2, in the kernel order. FIG. 8a. shows the variable support of the vertical split/merge mode.

(91) The difference between the horizontal split/merge mode and the vertical split/merge mode is in the choice of h.sub.x,p and h.sub.y,p. Rather than h.sub.y,p=2h.sub.x,p, we choose h.sub.x,p=2h.sub.y,p and

(92) $h_{y,p}=\{\begin{array}{cc}2h_y& \begin{array}{c}\mathrm{No}\mathrm{dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{three}\\ \mathrm{neighbor}\mathrm{kernels}\mathrm{and}\mathrm{Kp}\mathrm{have}{L}_p=1\end{array}\\ 1/4h_y& \begin{array}{c}\mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{those}\mathrm{at}\\ \mathrm{the}\mathrm{top}\mathrm{are}\mathrm{significantly}\mathrm{larger},\end{array}\\ 1/2h_y& \mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\\ 3/4h_y& \begin{array}{c}\mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{those}\mathrm{at}\\ \mathrm{the}\mathrm{bottom}\mathrm{are}\mathrm{significantly}\mathrm{larger},\end{array}\\ 1& \mathrm{otherwise}.\end{array},h_{x,p}=\{\begin{array}{cc}2h_x& \begin{array}{c}\mathrm{No}\mathrm{dis}\text{-}\mathrm{continuity}\mathrm{detected}\mathrm{and}\mathrm{three}\\ \mathrm{neighbor}\mathrm{kernels}\mathrm{and}\mathrm{Kp}\mathrm{have}{L}_p=1\end{array}\\ 1/2h_x& \mathrm{Dis}\text{-}\mathrm{continuity}\mathrm{detected}\\ 1& \mathrm{otherwise}\end{array},$ and the data structure of the kernel representation follows the vertical split/merge mode. FIG. 8b shows the variable support of the vertical split/merge mode.

(93) A distinctive advantage of this invention is its ability to perform inter-coding, i.e. to perform (inter-frame) and/or over space (inter-view) prediction under changes such as camera position, etc. and code only the required motion parameters and new overlay layers in kernel representation. For example, one may first compensate the global deformation such as camera motion position of the background layer D.sub.J+1 from time t to time t+1 using some global camera compensation method. The deformation model can be an affine model or the general projective transformation. Afterwards, major motion objects and their location deformation parameters can be detected. If the motion compensation is satisfactory, the resulting parameters can be compressed using entropy coding. For areas where local motion compensation are unsatisfactory, it can be coded another as an overlaying layer in kernel representation. This is applicable to inter-view deformation across different camera views as well as over time in prediction across successive image frames over time. Using these motion descriptors and the new layer of kernel representation of time t, the kernel representation at time t+1 can be reconstructed. Given the number of global motion parameters and that the local motion descriptors can be smaller than coding all the deformation kernel parameters, the compression ratio can be significantly increased if the images can be well predicted by the global and local motion parameters.

(94) In the fixed support mode, the kernel order L.sub.p=1 and L.sub.p=2 can be represented as 0 and 1 respectively. A lossless compression technique, such as an entropy coding method can be used to further compress the kernel order. Whereas in the variable support mode, mod e.sub.p can be further compressed using a lossless compression technique.

(95) In the present invention, a new variable scale differential category based coding technique is used to further compress the kernel parameters. First, the kernel parameters are scaled to fixed-point integers using the scaling parameters
.sub.l,k,p=round(s.sub.l,ka.sub.l,k,p),(28)

(96) where s.sub.l,k is a global scaling parameter employed for the k-th parameter of the l-th kernel order. .sub.l,k,p is the quantized parameter and it is a signed integer range from 2.sup.(B.sup.p.sup.1) to 2.sup.(B.sup.p.sup.1), where B.sub.p is the chosen bit per kernel parameters. Round( ) is the round-off operator. The round-off procedure in equation (28) is also referred to as quantization. After the kernel parameters have been scaled and quantized, they can be further compressed using the proposed differential category coding. The principle of category coding is to group the parameters according to their number of binary digits. Since parameters in most categories do not require B.sub.p bits, the data rate can be reduced. More precisely, a category table is constructed for the parameters, which is defined as
Category 0: a.sub.l,k,p=0,(29a)
Category 1: 1|a.sub.l,k,p|2.sup.q.sup.r1,(29b)
Category r: 2.sup.q.sup.r.sup.1|a.sub.l,k,p|2.sup.q.sup.r1, r=1,2, . . . ,R,(29c) where R is the total number of categories, B.sub.p is the number of bit per kernel parameter (including sign bit) defined in equation (22), q.sub.r is the number of binary digits of the kernel parameter represented by category r (excluding sign bit). q.sub.r can be chosen as

(97) $\begin{array}{cc}{q}_r=\{\begin{array}{cc}1& r=0\\ B_p-1& r=R\\ \mathrm{rQ}& \mathrm{otherwise}\end{array},\mathrm{where}Q=\mathrm{floor}\left(\frac{B_p-1}{R}\right),r=1,2,\mathrm{.Math.},R-1.& \left(30\right)\end{array}$

(98) Here, Q is the difference of binary digits between adjacent categories for category r=1, 2, . . . , R1. Since Q can be varied by choosing a different R, this can be referred to as a variable scale. For example, if B.sub.p=21 (including sign bit) and the total number of categories R=6 are chosen, then the number of binary digits required to store the kernel parameter (excluding sign bit) of category r=0, 1, 2, . . . 6 is q.sub.r=1, 3, 6, 9, 12, 15 and 20 respectively. The scale Q can be chosen to optimize the compression ratio.

(99) In the proposed variable scale differential category coding, the statistical redundancy in the occurrence of the category can be exploited. FIG. 8 shows the procedure of the proposed differential category coding. First, all the kernel parameters are divided into chunks of V parameters. In each chunk, the first kernel parameter is treated as a reference parameter. The category of the reference parameter is stored as the symbol ref. Afterwards, the categories of all L parameters are obtained from the category table. In this example, Q is chosen as Q=2. At the same time, we also detect whether there is a difference between the sign of the reference parameter and other remaining parameters, the pattern of which is represented using the symbol isSign. Afterwards, a symbol isDiff is used to represent whether there is difference in category between the reference parameter and other parameters. Finally, for the parameters belonging to categories different from the reference parameter, we compute the actual difference in category and a symbol Diff is used to store the difference for each of the parameter. Note, only parameters with the same category as the reference are omitted. As a result, only three symbols are required as shown in FIG. 9.

(100) FIG. 9 shows the procedure of Differential Category Coding for Q=2. The total number of symbols for coding the category for the above chunk is symbols. These symbols can be further compressed using entropy coding techniques such as arithmetic coding or Huffman coding. If such techniques are employed, the dictionaries for the symbols Ref, is Diff and Diff are required and they may be included as part of the overhead in the data structure shown in FIG. 4 when an update of the dictionaries are performed, say once per 30 to 60 frames. As an illustration, this example considers a signed representation, in which code the redundancy of the sign bit can be further coded using isSign. In general, other representations, such as one's complement, two's complement and etc. can also be used.

(101) FIG. 10 shows the data structure for the proposed differential category coding scheme. Apart from the symbols mentioned above, the total number of kernel parameters P.sub.L for order L is also stored/transmitted. Since P.sub.L may not be divisible by the length of each chunk V, the whole set of parameters is padded with zeros in the final chunk. Hence, the padding length has to be stored/transmitted. The storage of Q is also required. Since B.sub.p is stored/transmitted in the global overhead as shown in FIG. 4, R can be calculated using Q and B.sub.p as in equation (30) and the storage of R is not required. The data stream in FIG. 10 contains the actual binary values of the kernel parameters represented by the category coding and its total length will be smaller than that of the total stream of uncompressed kernel parameters when some of the kernel parameters belong to categories r<R. The total size of the data stream is

(102) $\begin{array}{cc}\mathrm{Total}\mathrm{size}\mathrm{of}\mathrm{data}\mathrm{stream}=\underset{u=1}{\overset{U}{.Math.}}\underset{v=1}{\overset{V}{.Math.}}{q}_{r,v},& \left(31\right)\end{array}$
where U is the total number of chunks. The symbols isDiff, Diff, isSign and ref can be further compressed using entropy coding techniques such as arithmetic coding or Huffman coding. See, S. E. Umbaugh, Digital image processing and analysis: human and computer vision applications with CVIPtools (2nd ed. ed.), Boca Raton, Fla.: CRC Press, 2010, which is incorporated herein by reference in its entirety. To further increase the compression ratio for some data with high redundancy in the kernel parameter, the kernel parameters may be subtracted from the reference parameter and only the residual is coded.

(103) The word length of the kernel parameter can be determined by the specified compression quality, such as the required precision of image deformation, tolerance of the approximation error, and etc. For example, the required range and precision of the image deformation can be specified, and the number of bits required for kernel parameter can be calculated. Alternatively, an iterative procedure may be employed to evaluate the quantization error for different chosen word lengths and the appropriate one may be chosen with least approximation error among the subset of acceptable word lengths. This concept can be applied to different number representations, such as signed representation, one's complement, two's complement, etc.

(104) For example, consider a polynomial kernel with order 2 with parameters represented using a signed representation, i.e. K.sub.p(x,y,a.sub.p)=a.sub.0,p+a.sub.1,0,px+a.sub.1,1,py+a.sub.2,0,px.sup.2+a.sub.2,1,pxy+a.sub.2,2,py.sup.2.

(105) Suppose K.sub.p(x,y,a.sub.p) is a positive integer with 8 integer bits, x and y are the positive integer coordinates within the support and it ranges from [c.sub.x,p,c.sub.x,p+h.sub.x,p] and [c.sub.y,p, c.sub.y,p+h.sub.y,p] respectively. The word length of x and y are hence determined by the size of h.sub.x,p and h.sub.y,p. For example, it can be chosen as ceil(log.sub.2(max(h.sub.x,p,h.sub.y,p))) and 2ceil(log.sub.2(max(h.sub.x,p,h.sub.y,p))) for a fixed support kernel and variable support kernel, respectively. The kernel parameters a.sub.i,j,p are floating point numbers and the required word length for storing the floating point number is to be determined. Suppose a.sub.i,j,p has .sub.a integer bits and .sub.a decimal bits and the total no. of bits are .sub.a bits, i.e. .sub.a=1+.sub.a+.sub.a (including sign bit). a.sub.i,j,p can be represented as
sb.sub.b.sub.1 . . . b.sub.0.Math.b.sub.1b.sub.2 . . . b.sub.,(32)

(106) where bit s is the sign bit and bit b.sub.k has a weight of 2.sup.k. The number in equation (32) can be expressed as

(107) $\begin{array}{cc}{a}_{i,j,p}=\left(1/2^{}\right)\underset{n=0}{\overset{+}{.Math.}}{2}^n{b}_n.& \left(33\right)\end{array}$

(108) The signed representation is denoted with .sub.a integer bits and .sub.a decimal bits in equation (33) as S(a.sub.i,j,p,.sub.a,.sub.a). Since x and y are positive integer coordinates, their signed representation are S(x,.sub.x,0) and S(y,.sub.y,0) respectively. Let d.sub.i,j,p be the product of a.sub.i,j,p and x, i.e. d.sub.i,j,p=a.sub.i,j,px.sup.iy.sup.j, and its signed representation be S(d.sub.i,j,p,.sub.d,.sub.d). S(d.sub.i,j,p,.sub.d,.sub.d) is given as
S(d.sub.i,j,p,.sub.d,.sub.d)=S(a.sub.i,j,p,.sub.a,.sub.a)(S(x,.sub.x,0)).sup.i(S(y,.sub.y,0)).sup.j.(34)

(109) where .sub.d=.sub.a+i.sub.x+j.sub.j and .sub.d=.sub.b and .sub.d=1+.sub.d+.sub.d. The total number of bits required to store the sum of all products for K.sub.p (x,y,a.sub.p)=a.sub.0,p+a.sub.1,0,px+a.sub.0,1,py+a.sub.2,0,px.sup.2+a.sub.1,1,pxy+a.sub.0,2,py.sup.2 will be

(110) $\underset{i,j,p}{\max }\left({}_{d,i,j,p}\right)+\underset{i,j,p}{\max }\left({}_{d,i,j,p}\right)+2,$
in which 2 extra bits are allocated for sign and carry bits. Since K.sub.p(x,y,a.sub.p) is of finite word length .sub.K, the number of integer bits .sub.K and decimal bits .sub.K can be expressed as

(111) $\begin{array}{cc}{}_K=\underset{i,j,p}{\max }\left({}_{d,i,j,p}\right)+1,& \left(35a\right)\\ {}_K=\underset{i,j,p}{\max }\left({}_{d,i,j,p}\right),\mathrm{and}& \left(35b\right)\\ {}_K={}_K+{}_K+1.& \left(35c\right)\end{array}$

(112) To optimize the precision of a.sub.i,j,p, the following may be employed:
.sub.d,0,p=.sub.d,1,0,p=.sub.d,0,1,p=.sub.d,2,0,p=.sub.d,1,1,p=.sub.d,0,2,p=.sub.K1, and(36a)
.sub.d,0,p=.sub.d,1,0,p=.sub.d,0,1,p=.sub.d,2,0,p=.sub.d,1,1,p=.sub.d,0,2,p=.sub.K.(36b)

(113) Then, the minimum word length for representing the kernel parameters without losing precision is
a.sub.0,p: .sub.a,0,p=.sub.a,0,p+.sub.a,0,p+1, .sub.a,0,p=.sub.K1, .sub.a,0,p=.sub.K,(37a)
a.sub.1,0,px: .sub.a,1,0,p=.sub.a,1,0,p+.sub.a,1,0,p+1, .sub.a,1,0,p=.sub.K.sub.x1, .sub.a,1,0,p=.sub.K,(37b)
a.sub.0,1,py: .sub.a,0,1,p=.sub.a,0,1,p+.sub.a,0,1,p+1, .sub.a,0,1,p=.sub.K.sub.y1, .sub.a,0,1,p=.sub.K,(37c)
a.sub.2,0,px.sup.2: .sub.a,2,0,p=.sub.a,2,0,p+.sub.a,2,0,p+1, .sub.a,2,0,p=.sub.K2.sub.x1, .sub.a,2,0,p=.sub.K,(37d)
a.sub.1,1,pxy: .sub.a,1,1,p=.sub.a,1,1,p+.sub.a,1,1,p+1, .sub.a,1,1,p=.sub.K.sub.x.sub.y1, .sub.a,1,1,p=.sub.K,(37e)
a.sub.0,2,py.sup.2: .sub.a,0,2,p=.sub.a,0,2,p+.sub.a,0,2,p+1, .sub.a,0,2,p=.sub.K2.sub.y1, .sub.a,0,2,p=.sub.K.(37f)

(114) On the other hand, if a lossy compression is allowed, the different word lengths may be specified and compared with the reconstruction error given as

(115) $\underset{x,y}{.Math.}d\left(x,y\right)-\underset{p}{.Math.}{K}_p\left(x,y,{\stackrel{\_}{a}}_p\right),$
where .sub.p are the quantized kernel parameters. Then the best word length is chosen that gives the smallest reconstruction error.

(116) The encoded data for an image deformation map received at the decoder will be either in the two formats as shown in FIGS. 6 and 7, which are the data structure for the fixed and variable support modes, respectively. The decoding procedure is summarized as follows: 1. Read the first bit (F/V) of the encoded data, where 0 and 1 indicate fixed support and variable support modes, respectively. 2. Read P.sub.x, P.sub.y, h.sub.x and h.sub.y, which are all unsigned 16 bit integers and that represent the number of kernels per column, number of kernels per row, the width and height of the image deformation map respectively. 3. Starting from the first kernel with center location (0,0), generate or compute the center location of the subsequent kernel by adding its support h.sub.x and h.sub.y. For a fixed support, the kernels can be labeled using K.sub.i,j, where i=1, 2, . . . , P.sub.x and j=1, 2, . . . P.sub.y indicate the column and row number. h.sub.x,p=floor(h.sub.x/P.sub.x) and h.sub.y,p=floor(h.sub.y/P.sub.y) can be chosen for i<P.sub.x1 and j<P.sub.y1. Otherwise, they can be chosen as h.sub.x,p=(h.sub.x(P.sub.x2)h.sub.x,p)/2 and h.sub.y,p=(h.sub.y(P.sub.y2)h.sub.y,p)/2. Whereas in the variable support mode, the above fixed kernel support can be generated first. Afterwards, read the mode parameters mod e.sub.p sequentially, which are labeled in column-major ordering. When mod e.sub.p=2 is read, merge the support of the current and the subsequent kernel. If mod e.sub.p=3, 4, or 5, it is necessary to determine whether the variable support is in vertical or horizontal split/merge mode by comparing P.sub.x and P.sub.y. If P.sub.x>P.sub.y, then the vertical split/merge mode is chosen or vice versa. Then, choose the appropriate bandwidth/support h.sub.x,p and h.sub.y,p by applying the formulas 25 and 26. 4. After generating the center locations, the displacement and transparent values can be decoded as follows

(117) $\begin{array}{cc}{\stackrel{\_}{d}}_j\left(x,y\right)=\underset{p=1}{\overset{\mathrm{Pj}}{.Math.}}{w}_{p,x,y,j}{K}_{p,j}\left(\frac{x-c_{x,p,j}}{h_{x,p,j}},\frac{y-c_{y,p,j}}{h_{y,p,j}},a_{p,j}\right),& \left(38a\right)\\ {\stackrel{\_}{}}_j\left(x,y\right)=\underset{p=1}{\overset{\mathrm{Pj}}{.Math.}}{w}_{,p,x,y,j}{K}_{p,j}\left(\frac{x-c_{x,p,j}}{h_{x,p,j}},\frac{y-c_{y,p,j}}{h_{y,p,j}},a_{,p,j}\right),& \left(38b\right)\end{array}$

(118) where K.sub.p,j() is the kernel function defined as in equation (4). Since the kernel parameters have been scaled and quantized before they are coded, a re-scaling is required before applying them to equations (22a) and (22b) for decoding
.sub.l,k,p.sub.l,k,p.Math.2.sup.sl,k,(39)

(119) where .sub.l,k,p is the quantized and scaled parameter and .sub.l,k,p is the re-scaled parameter, which is applied to equations. (38a) and (38b) for reconstruction. Equation (39) can be performed by shifting s.sub.l,k bits of .sub.l,k,p to the right. The decoding processes in (38a) and (38b) are done with integer multiplications in 16 bit arithmetic. To avoid the divisions

(120) 0$\frac{x-c_{x,p,j}}{h_{x,p,j}}\mathrm{and}\frac{y-c_{y,p,j}}{h_{y,p,j}}$
in Eqns. (38a) and (38b), the two quantities can be pre-computed as follows

(121) $\begin{array}{cc}\frac{x-c_{x,p,j}}{h_{x,p,j}}=0,\frac{1}{h_{x,p,j}},\mathrm{.Math.},1,\mathrm{for}x=\left[c_{x,p,j},c_{x,p,j}+h_{x,p,j}\right],& \left(40a\right)\\ \frac{y-c_{y,p,j}}{h_{y,p,j}}=0,\frac{1}{h_{y,p,j}},\mathrm{.Math.},1,\mathrm{for}y=\left[c_{y,p,j},c_{y,p,j}+h_{y,p,j}\right].& \left(40b\right)\end{array}$

(122) Afterwards, the computation of

(123) $K_{p,j}\left(\frac{x-c_{x,p,j}}{h_{x,p,j}},\frac{y-c_{y,p,j}}{h_{y,p,j}},a_{p,j}\right)$
can be performed in 16 bit fixed-point arithmetic.

(124) The procedure to decode the compressed kernel parameters is as follows:

(125) The structure of the encoded kernel parameters is shown in FIG. 9. The decoding procedure can be summarized as follows: 1. Read P.sub.L, pad length, and Q, which are 16 bit, 16 bit and 8 bit unsigned integers respectively. 2. Read the symbols isDiff, Diff, Ref and IsSign. If they are compressed say using entropy methods, the total number of bits required to store each of the symbols will be included at the beginning of the symbols. Hence, these symbols can be de-compressed using their respective dictionaries, which are sent over say once per 30 to 60 frames. 3. Decode the first chunk/block. Read the first symbol in the de-compressed isDiff, which contains all the symbols for indicating whether there is change in category for each of the kernel parameters. A isDiff symbol contains V1 bits, which represents the indicator for parameters v=2, 3, . . . , V. 4. Create v=1, 2, . . . V variables for storing the categories for the V parameters. For each of the variables v=2, 3, . . . V, if the v-th bit of the isDiff symbol is 1, read a symbol from Diff, add the difference to the v-th variable. Read the first Ref symbol, add the reference category to each of the v-th variable. Save the 1.sup.st variable as the reference category. 5. After obtaining the categories for the V parameters, obtain the word length of each of the parameters as in equation (20). Afterwards, read the V parameters from the data-stream in accordance with to the obtained word lengths. 6. Repeat steps 2-5 for subsequent chunks/blocks.

(126) The compression standard supports two modes of operation: 1.) Compression of 3D content such as single-view image, depth maps, stereo images, full-frame two-view images and two view depth maps. 2.) Compression of description parameters. Tables 1 and 2 summarizes the input and output format of the encoder and decoder respectively. In particular, the description parameters may be used to describe the kernel parameters for representing the depth values, transparency or opacity. The data structure of the description parameters are shown in FIG. 10. If the input contains only image, the image deformation map will be obtained by a depth estimation method.

(127) TABLE-US-00001 TABLE 1 Input and output format supported for the encoder. No. of Input Views Input Format Output Format Mode 0 (Compression of 3D content) 1 Single-view image Description Parameters A 8-16 bit per pixel depth map 1 A 8-16 bit per pixel depth Description Parameters map A 8-16 bit per pixel depth map 2 Stereo Image (side by side) Description Parameters A 8-16 bit per pixel depth map 2 Full frame Two-view Image Description Parameters A 8-16 bit per pixel depth map 2 Two 8-16 bit per pixel Description Parameters (2 sets) depth map Model 1 (Compression of description parameter) 1 Single set of description Compressed parameters parameters A 8-16 bit per pixel depth map 2 Two sets of description Two sets of compressed parameters parameters, each of which Two 8-16 bit per pixel depth map describes a view of the stereo image.

(128) TABLE-US-00002 TABLE 2 Input and output format for the Decoder. No. of Input Views Input Format Output Format Mode 0 (De-compression of 3D content) 1 Compressed parameters A 8-16 bit per pixel depth map 2 Two sets of compressed Two 8-16 bit per pixel depth map parameters Mode 1 (De-compression of description parameters) 1 Compressed parameters Description Parameters for a depth map 2 Two sets of compressed Two sets of description parameters parameters for two depth maps

(129) The disadvantage of the image deformation representation in the image domain warping method of the prior art is that since each pixel is assigned a depth value, the data size of such representation can increase substantially for a HD 3D video content, which may lead to large latency in 3DTV broadcasting. Moreover, it does not contain inter-coding. Since only a single deformation value is assigned for each particular location, the image domain warping method cannot handle the view synthesis of semi-transparent, reflective or deformable objects.

(130) The aadvantages of the multi-layer Variable Support and Order Kernel-based Representation for Image Deformation: i. It reduces significantly the data rate for transmission/storage of the image deformation. ii. Allows multiple overlays and varying transparency of image deformation. Hence, it is able to handle semi-transparent, reflective or deformable objects. iii. The shape information of the image deformation can be further compressed using a shape codec and it can be used to further sharpen the image deformation. iv. It improves the smoothness of the image deformation. v. It provides the flexibility in controlling the compression ratio and quality. vi. The ability to perform inter-coding, which leads to further improved compression ratio. vii. Efficient schemes for computing the kernel parameters, which facilitates real-time view synthesis in say an android-based 3D display device.

(131) The advantages of the Variable Scale and Differential Category Coding for Compression of Kernel Parameters are: i. The ability to determine the word length according to the specified compression quality. This provides more flexibility in controlling between the compression ratio and quality. ii. Rather than simply predicting the values of the kernel parameters, which could hardly be accurate in the context of approximating the image deformation, this invention predicts the categories of the kernel parameters and code the scale and sign difference. As a result, it is able to explore the redundancies in scale and sign of the parameters to achieve better compression ratio. iii. A variable scale is employed to form the category coding and a new method to optimize the scale is proposed and it is able to achieve a high compression ratio and a satisfactory compression quality.

(132) The proposed invention is expected to have great impact in the field of 3D video content provision. One immediate application of the invention is the 3D video content compression for online video broadcasting. Another application is 3D video format conversion.

(133) The algorithm can be included in a compression standard proposal for autostereoscopic multi-view TVs.

(134) Different 3D video content provision service and related products can be developed, such as 3D video broadcasting service, 3D video format conversion software or hardware, 3D video compression software or hardware, and etc.

(135) While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention. Additionally, many modifications may be made to adapt a particular situation to the teachings of claimed subject matter without departing from the central concept described herein. Therefore, it is intended that claimed subject matter not be limited to the particular examples disclosed, but that such claimed subject matter may also include all implementations falling within the scope of the appended claims, and equivalents thereof.