Apparatus and method for unequal error protection in multiple-description coding using overcomplete expansions

• US 6,460,153 B1
• Filed: 03/26/1999
• Issued: 10/01/2002
• Est. Priority Date: 03/26/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chou, Philip A., Mehrotra, Sanjeev, Wang, Albert S.
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/276,955
• Time in Patent Office: 1,285 Days
• Field of Search: 714/746, 714/776, 348/403, 348/405, 348/845.1
• US Class Current: 714/746
• CPC Class Codes: H04N 19/89 involving methods or arrangements for detection of transmission errors at the decoder

Abstract

A projection onto convex sets (POCS)-based method for consistent reconstruction of a signal from a subset of quantized coefficients received from an N×K overcomplete transform. By choosing a frame operator F to be the concatenization of two or more K×K invertible transforms, the POCS projections are calculated in R^K space using only the K×K transforms and their inverses, rather than the larger R^N space using pseudo inverse transforms. Practical reconstructions are enabled based on, for example, wavelet, subband, or lapped transforms of an entire image. In one embodiment, unequal error protection for multiple description source coding is provided. In particular, given a bit-plane representation of the coefficients in an overcomplete representation of the source, one embodiment of the present invention provides coding the most significant bits with the highest redundancy and the least significant bits with the lowest redundancy. In one embodiment, this is accomplished by varying the quantization stepsize for the different coefficients. Then, the available received quantized coefficients are decoded using a method based on alternating projections onto convex sets.

Claims

1. A computerized method of enhancing the recoverability of a set of data x having K dimensions for transmission on an erasure channel, the method comprising:

generating an overcomplete expansion y of the set cf data x using an N×

K multiple description overcomplete expansion y=Fx, wherein N>

K and wherein at least some of the last N−

K rows of F are not duplicative of any of the first K rows; and

quantizing the coefficients of y to unequal resolution.

2. The method of claim 1, wherein the unequal quantization resolution is based on a significance of coefficients to data recovery.

3. The method of claim 1, wherein the set of data has a bit-significant representation, and wherein the overcomplete expansion of the set of data provides coding most significant bits with a higher redundancy and least significant bits with a lower redundancy.

4. The method of claim 1, wherein the set of data is a source image having a bit-plane representation, and wherein coefficients of the overcomplete expansion of the source image provide coding the most significant bits with a higher redundancy and the least significant bits with a lower redundancy.

5. The method of claim 4, further comprising:

varying the quantization stepsize for the different coefficients.

6. The method of claim 5, further comprising:

receiving at least some of the quantized coefficients; and

decoding the received quantized coefficients using a method based on alternating projections onto convex sets in order to generate a recovered set of data.

7. A computer-readable medium having instructions stored thereon for causing a computer to perform the method of claim 1.

8. A computerized system for enhancing the recoverability of a set of data for transmission on an erasure channel, the system comprising:

a component for generating a multiple-description overcomplete expansion of the set of data wherein unequal encoding is employed.

9. The system of claim 8, wherein the unequal encoding is based on a significance of data to its recovery.

10. The system of claim 8, wherein the set of data has a bit-significant representation, and wherein the overcomplete expansion of the set of data provides coding most significant bits with a higher redundancy and least significant bits with a lower redundancy.

11. The system of claim 8, wherein the set of data is a source image having a bit-plane representation, and wherein the coefficients of the overcomplete expansion of the source image provide coding the most significant bits with a higher redundancy and the least significant bits with a lower redundancy.

12. The system of claim 11, further comprising

means for varying the quantization stepsize for the different coefficients.

13. The system of claim 12, further comprising

means for receiving at least some of the quantized coefficients;

and

means for decoding the received quantized coefficients using a method based on alternating projections onto convex sets.

14. The system of claim 8, further comprising a computer-readable medium having instructions stored thereon for causing a computer to operatively control the means for generating the overcomplete expansion.

15. A computerized method of reconstructing data after a transmission on an erasure channel, the method comprising:

providing an initial set of data x having K dimensions;

overcompletely transforming the set of data x to a multiple-description overcomplete expansion set of data y having N dimensions, where N>

K; and

quantizing the coefficients of y to unequal resolution.

16. The method of claim 15, wherein the set of data is a source image having a bit-plane representation, and wherein coefficients of the overcomplete expansion of the source image provide coding the most significant bits with a higher redundancy and the least significant bits with a lower redundancy.

17. The method of claim 16, further comprising:

varying the quantization stepsize for the different coefficients.

18. The method of claim 17, further comprising:

transmitting the set of data y on the channel;

receiving a set of data y′

from the channel; and

iteratively transforming the received set of data y′

using projections onto convex sets that use at least two different K×

K transforms including;

(a) initializing t;

(b) setting an initial point in F₁P;

(c) transforming p₁(t) into the coordinate system of F₂;

(d) projecting p₂(t) onto F₂Q;

(e) transforming q₂(t+1) into the coordinate system of F₁;

(f) projecting q₁(t+1) onto F₁P;

(g) checking for convergence and if not sufficiently converged then iterating (c) through (g); and

(h) reconstructing {circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1) in order to generate a recovered set of data;

wherein;

F₁ and F₂ are each K×

K transforms, and n=1 or 2.

19. The method of claim 15, further comprising:

transmitting the set of data y on the channel;

receiving a set of data y′

from the channel; and

iteratively transforming the received set of data y′

using projections onto convex sets that use at least two different K×

K transforms including;

(a) initializing t;

(b) setting an initial point in F₁P;

(c) transforming p₁(t) into the coordinate system of F₂;

(d) projecting p₂(t) onto F₂Q;

(e) transforming q₂(t+1) into the coordinate system of F₁;

(f) projecting q₁(t+1) onto F₁P;

(g) checking for convergence and if not sufficiently converged then iterating (c) through (g); and

(h) reconstructing {circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1) in order to generate a recovered set of data;

wherein;

F₁ and F₂ are each K×

K transforms, and n=1 or 2.

20. The method of claim 19, wherein:

(a) initializing further includes initializing t=0;

(b) starting further includes setting an initial point p₁(0) such that for each index i, $p_{1,i}<br><br>\left(0\right)={\hat{y}}_{1,i}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\in <br><br>R_1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$p_{1,i}<br><br>\left(0\right)=0<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\notin <br><br>R_1;<br><br>$

(c) transforming p₁(t) further includes transforming p₁(t) into the coordinate system of F₂ using p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) projecting p₂(t) further includes projecting p₂(t) onto F₂Q such that for each index i;

$q_{2,i}<br><br>\left(t+1\right)=\min <br><br>\left\{\max <br><br>\left\{p_{2,i}<br><br>\left(t\right),l_{2,i}\right\},u_{2,i}\right\}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\in <br><br>R_2<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$q_{2,i}<br><br>\left(t+1\right)=p_{2,i}<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\notin <br><br>R_2;<br><br>$

(e) transforming q₂(t+1) further includes transforming q₂(t+1) into the coordinate system of F₁ using q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) projecting q₁(t+1) further includes projecting q₁(t+1) onto F₁P such that for each index i;

$p_{1,i}<br><br>\left(t+1\right)=\min <br><br>\left\{\max <br><br>\left\{q_{1,i}<br><br>\left(t+1\right),l_{1,i}\right\},u_{1,i}\right\}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\in <br><br>R_1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$p_{1,i}<br><br>\left(t+1\right)=p_{2,i}<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\notin <br><br>R_1;<br><br>\mathrm{and}$

(g) checking further includes checking for convergence by testing ∥

p_n(t+1)−

p_n(t)∥

²>

ε

, and if so then setting t←

t+1 and iterating (c) through (g); and

(h) reconstructing {circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1), wherein n=1 or 2,

and wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup> is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . ,K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . ,K} is the set of indices of the descriptions received of ŷ

₂.

21. The method of claim 20, wherein the (a) initializing t, (b) setting an initial point in F₁P, (c) transforming p₁(t) into the coordinate system of F₂, (d) projecting p₂(t) onto F₂Q, (e) transforming q₂(t+1) into the coordinate system of F₁, (f) projecting q₁(t+1) onto F₁P, (g) checking for convergence and if not sufficiently converged then iterating (c) through (g);

and (h) reconstructing {circumflex over (x)}=F_n<sup>−

1</sup>p_n(t+1) are performed in the order listed.

22. The method of claim 19, wherein:

(a) initializing further includes initializing t=0;

(b) starting further includes setting an initial point p₁(0) such that for each index i, $\begin{array}{cc}{p}_{1,i}<br><br>\left(0\right)={\hat{y}}_{1,i}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\in <br><br>R_i<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}\\ p_{1,i}<br><br>\left(0\right)=0<br><br>\text{\hspace{1em}<br><br>}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\notin <br><br>R_1;<br><br><br><br>\text{\hspace{1em}<br><br>}\end{array}$

(c) transforming p₁(t) further includes transforming p₁(t) into the coordinate system of F₂ using p₂(t)=F₂(F₁<sup>−

1</sup>p₁(t))=F₁₂p₁(t);

(d) projecting p₂(t) further includes projecting p₂(t) onto F₂Q such that for each index i;

$\begin{array}{cc}{q}_{2,i}<br><br>\left(t+1\right)=\min <br><br>\left\{\max <br><br>\left\{p_{2,i}<br><br>\left(t\right),l_{2,i}\right\},u_{2,i}\right\}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\in <br><br>R_2<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}\\ q_{2,i}<br><br>\left(t+1\right)=p_{2,i}<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\notin <br><br>R_2;<br><br><br><br>\text{\hspace{1em}<br><br>}\end{array}$

(e) transforming q₂(t+1) further includes transforming q₂(t+1) into the coordinate system of F₁ using q₁(t+1)=F₁(F₂<sup>−

1</sup>q₂(t+1))=F₂₁q₂(t+1);

(f) projecting q₁(t+1) further includes projecting q₁(t+1) onto F₁P such that for each index i;

$\begin{array}{cc}{p}_{1,i}<br><br>\left(t+1\right)=\min <br><br>\left\{\max <br><br>\left\{q_{1,i}<br><br>\left(t+1\right),l_{1,i}\right\},u_{1,i}\right\}& \mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\in <br><br>R_1<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}\\ p_{1,i}<br><br>\left(t+1\right)=p_{2,i}<br><br>\left(t\right)<br><br>\text{\hspace{1em}<br><br>}& \text{\hspace{1em}<br><br>}<br><br>\mathrm{if}<br><br>\text{\hspace{1em}<br><br>}<br><br>i\notin <br><br>R_1;<br><br>\mathrm{and}\end{array}$

(g) checking further includes checking for convergence by testing ∥

p₁(t+1)−

p₁(t)∥

²>

ε

, and if so then setting t←

t+1 and iterating (c) through (g)

and wherein;

F₁ and F₂ are each K×

K transforms,

F₁<sup>−

1</sup> is the inverse transform of F₁, F₂<sup>−

1</sup> is the inverse transform of F₂,

ŷ

₁ is a quantized version of y₁, ŷ

₂ is a quantized version of y₂, such that ŷ

₁ componentwise lies between respective lower and upper quantization cell boundary vectors l₁≦

ŷ

₁≦

u₁ and ŷ

₂ componentwise lies between respective lower and upper quantization cell boundary vectors l₂≦

ŷ

₂≦

u₂,

R₁⊂

{1, . . . ,K} is the set of indices of the descriptions received of ŷ

₁, and

R₂⊂

{1, . . . ,K} is the set of indices of the descriptions received of ŷ

₂.

23. The method of claim 22, wherein operations are performed in the order listed.