Source: http://www.google.com/patents/US6470469?dq=5311516
Timestamp: 2016-10-22 07:44:54
Document Index: 628552391

Matched Legal Cases: ['art 700', 'art 700', 'art 700', 'art 700', 'art 800', 'art 800', 'art 800', 'art 800']

Patent US6470469 - Reconstruction of missing coefficients of overcomplete linear transforms ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA 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...http://www.google.com/patents/US6470469?utm_source=gb-gplus-sharePatent US6470469 - Reconstruction of missing coefficients of overcomplete linear transforms using projections onto convex setsAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS6470469 B1Publication typeGrantApplication numberUS 09/276,842Publication dateOct 22, 2002Filing dateMar 26, 1999Priority dateMar 26, 1999Fee statusLapsedPublication number09276842, 276842, US 6470469 B1, US 6470469B1, US-B1-6470469, US6470469 B1, US6470469B1InventorsPhilip A. Chou, Sanjeev Mehrotra, Albert S. WangOriginal AssigneeMicrosoft Corp.Export CitationBiBTeX, EndNote, RefManPatent Citations (1), Non-Patent Citations (8), Referenced by (30), Classifications (18), Legal Events (8) External Links: USPTO, USPTO Assignment, EspacenetReconstruction of missing coefficients of overcomplete linear transforms using projections onto convex sets
US 6470469 B1Abstract
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 RK space using only the K�K transforms and their inverses, rather than the larger RN 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.
What is claimed is: 1. A computerized method of reconstructing a set of data x having K dimensions, the method comprising:
receiving a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>K; and iteratively transforming the received set of data y′ using projections onto K-dimensional convex sets as calculated with a computer to produce a set of data {circumflex over (x)} representing the reconstructed set of data x. 2. The method of claim 1, further comprising
providing an initial set of data x having K dimensions; overcompletely transforming the set of data x to a set of coefficients y having N dimensions, where N>K; quantizing the coefficients of y to obtain indices j such that each coefficient y1,i lies in the ji th quantization region and each one of the indices j correspond to a respective quantization region; entropy coding the indices j to obtain binary descriptions; and transmitting the binary descriptions on a channel. 3. The method of claim 2 wherein the transmitting on the channel further comprises:
storing the binary descriptions onto a storage medium; and reading the binary descriptions from the storage medium. 4. The method of claim 1, wherein the iteratively transforming calculation further comprises:
transforming a set of data y1 to a set of data y2 using F2F1 −1, setting components of the resulting set of data y2 corresponding to received components to those received components y2′, transforming the resulting set of data y2 to a set of data y1 using F1F2 −1, setting components of the resulting set of data y1 corresponding to received components to those received components y1′, and transforming the resulting set of data y1 to a set of data x′ using F1 −1, wherein F1 and F2 are each K�K transforms. 5. The method of claim 1, wherein the iteratively transforming calculation farther comprises:
(a) initializing a t=0; (b) setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ1,i if i∈R1 and p1,i(0)=0 if i∉R1; (c) transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1 −1p1(t))=F12p1(t); (d) projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i}, u2,i} if i∈R2 and q2,i(t+1)=p2,i(t) if i∉R2; (e) transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2 −1q2(t+1))=F21q2(t+1); (f) projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i}, u1,i} if i∈R1; and p1,i(t+1)=p2,i(t) if i∉R1; and (g) reconstructing a set of data {circumflex over (x)}=F1 −1p1(t); wherein: F1 and F2 are each K�K transforms, F1 −1 is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2. 6. The method of claim 5, wherein the iteratively transforming calculation further comprises:
(f1) checking for convergence by testing ∥p1(t+1)−p1(t)∥2>ε, and if so then setting t←t+1 and iterating (c) through (f). 7. The method of claim 6, wherein F1 is a wavelet transform and F2 is a discrete cosine transform.
8. The method of claim 1, wherein the iteratively transforming calculation further comprises:
(a) initializing a t=0; (b) setting p1,i(0)=ŷ1,i if i∈R1 (i.e., received descriptions) and p1,i(0)=0 if i∉R1; (i.e., descriptions not received) (c) for each m=1, . . . , M−1 in turn: (i) transforming pm(t) into the coordinate system of Fm+1: {tilde over (p)}m+1(t)=Fm+1Fm −1Pm(t)=Fm,m+1pm(t); and (ii) projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1: pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm 1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 (d) transforming pM(t) into the coordinate system of F1: {tilde over (p)}1(t+1)=F1FM −1pM(t)=FM,1pM(t) (e) projecting {tilde over (p)}1(t+1) onto F1P1: p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 (h) checking for convergence, and if ∥pn(t+1)−pn(t)∥2>epsilon for an n between 1 and M inclusive, then setting t←t+1 and repeating (c) through (f), otherwise performing (g); and (g) reconstructing x: {circumflex over (x)}=Fn −1pn(t+1); wherein: F1 through FM are each K�K transforms, M is an integer larger than 1, each Fm −1 is the inverse transform of Fm, ŷ1 is a quantized version of y1, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and each ŷm componentwise lies between respective lower and upper quantization cell boundary vectors lm≦ŷm≦um, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and for each m, Rm⊂{1, . . . , K} is the set of indices of the descriptions received of ŷm. 9. A computer readable medium having computer executable instructions stored thereon for performing a method of reconstructing a set of data x having K dimensions, the method comprising:
receiving a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>K; and iteratively transforming the received set of data y′ using projections onto convex sets as calculated with a computer to produce a set of data x′ representing the reconstructed set of data x. 10. The medium of claim 9, further including instructions such that the iteratively transforming further comprises:
(a) initializing a t=0; (b) setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ1,i if i∈R1 and p1,i(0)=0 if i∉R1; (c) transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1 −1p1(t))=F12p1(t); (d) projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i}, u2,i} if i∈R2 and q2,i(t+1)=p2,i(t) if i∉R2; (e) transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2 −1q2(t+1))=F21q2(t+1); (f) projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈R1 and p1,i(t+1)=p2,i(t) if i∉R1; and (g) reconstructing a set of data {circumflex over (x)}=F1 −1p1(t); wherein: F1 and F2 are each K�K transforms, F1 −1 is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2. 11. The medium of claim 10, further including instructions such that the iteratively transforming calculation further comprises:
(f1) checking for convergence by testing ∥p1(t+1)−p1(t)∥2>ε, and if so then setting t←t+1 and iterating (c) through (f). 12. The medium of claim 9, further including instructions such that the iteratively transforming further comprises:
(a) initializing a t=0; (b) setting p1,i(0)=ŷ1,i if i∈R1 (i.e., received descriptions) and p1,i(0)=0 if i∉R1; (i.e., descriptions not received) (c) for each m=1, . . . , M−1 in turn: (i) transforming pm(t) into the coordinate system of Fm+1: {tilde over (p)}m+1(t)=Fm+1Fm −1Pm(t)=Fm,m+1pm(t); and (ii) projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1: pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 (d) transforming pM(t) into the coordinate system of F1: {tilde over (p)}1(t+1)=F1FM −1pM(t)=FM,1pM(t) (e) projecting {tilde over (p)}1(t+1) onto F1P1: p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 (i) checking for convergence, and if ∥pn(t+1)−pn(t)∥2 >epsilon for an n between 1 and M inclusive, then setting t←t+1 and repeating (c) through (f), otherwise performing (g); and (g) reconstructing x: {circumflex over (x)}=Fn −1pn(t+1); wherein: F1 through FM are each K�K transforms, M is an integer larger than 1, each Fm −1 is the inverse transform of Fm, ŷ1 is a quantized version of y1, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and each ŷm componentwise lies between respective lower and upper quantization cell boundary vectors lm≦ŷm≦um, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and for each m, Rm⊂{1, . . . , K} is the set of indices of the descriptions received of ŷm. 13. A data-reconstruction system comprising:
means for receiving a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>K; and means, operatively coupled to the means for receiving, for iteratively transforming the received set of data y′ using projections onto convex sets to produce a set of data x′ representing the reconstructed set of data x. 14. The system of claim 13, wherein the means for iteratively transforming calculation further comprises:
(a) means for initializing a t=0; (b) means for setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ1,i if i∈R1 and p1,i(0)=0 if i∉R1; (c) means for transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1 −1p1(t))=F12p1(t); (d) means for projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i}, u2,i} if i∈R2 and q2,i(t+1)=p2,i(t) if i∉R2; (e) means for transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2 −1q2(t+1))=F21q2(t+1); (f) means for projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1), l1,i},u1,i} if i∈R1 and p1,i(t+1)=p2,i(t) if i∉R1; and (g) means for reconstructing a set of data {circumflex over (x)}=F1 −1p1(t); wherein: F1 and F2 are each K�K transforms, F1 −1 is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2. 15. The system of claim 14, wherein the means for iteratively transforming further comprises:
(f1) means for checking for convergence including means for testing ∥p1(t+1)−p1(t)∥2>ε, and means for setting t←t+1 and iterating means (c) through (f) if so. 16. The system of claim 13, wherein the means for iteratively transforming calculation further comprises:
(a) means for initializing a t=0; (c) means for setting p1,i(0)=ŷ1,i if i∈R1 (i.e., received descriptions) and p1,i(0)=0 if i∉R1; (i.e., descriptions not received) (c) for each m=1, . . . , M−1 in turn: (i) means for transforming pm(t) into the coordinate system of Fm+1: {tilde over (p)}m+1(t)=Fm+1Fm −1Pm(t)=Fm,m+1pm(t); and (ii) means for projecting {tilde over (p)}m+1(t) onto Fm+1,Pm+1: pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 (d) means for transforming pM(t) into the coordinate system of F1: {tilde over (p)}1(t+1)=F1FM −1pM(t)=FM,1pM(t) (e) means for projecting {tilde over (p)}1(t+1) onto F1P1: p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 (j) means for checking for convergence, and if ∥pn(t+1)−pn(t)∥2>epsilon for an n between 1 and M inclusive, then means for setting t←t+1 and repeating (c) through (f), otherwise means for going to (g); and (g) means for reconstructing x. {circumflex over (x)}=Fn −1pn(t+1); wherein: F1 through FM are each K�K transforms, M is an integer larger than 1, Fm −1 is the inverse transform of Fm, ŷ1 is a quantized version of y1, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and each ŷm componentwise lies between respective lower and upper quantization cell boundary vectors lm≦ŷm≦um, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1 and for each m, Rm⊂{1, . . . , K} is the set of indices of the descriptions received of ŷm. 17. The system of claim 14, wherein F1 is a wavelet transform and F2 is a discrete cosine transform.
18. The system of claim 14, wherein the means for iteratively transforming calculation further comprises:
means for transforming a set of data y1 to a set of data y2 using F2 F1 −1, means for setting components of the resulting set of data y2 corresponding to received components to those received components y2′, means for transforming the resulting set of data y2 to a set of data y1 using F1 F2 −1, means for setting components of the resulting set of data y1 corresponding to received components to those received components y1′, and means for transforming the resulting set of data y1 to a set of data x′ using F1 −1, wherein F1 and F2 are each K�K transforms.
means for providing an initial set of data x having K dimensions; means for overcompletely transforming the set of data x to a set of coefficients y having N dimensions, where N>K; means for quantizing the coefficients of y to obtain indices j such that each coefficient yi lies in the ji th quantization region and each one of the indices j correspond to a respective quantization region; means for entropy coding the indices j to obtain binary descriptions; and means for transmitting the binary descriptions on a channel. 20. The system of claim 19 wherein the transmitting on the channel further comprises:
means for storing the binary descriptions onto a storage medium; and means for reading the binary descriptions from the storage medium. 21. 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 set of data y having N dimensions, where N>K; 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. 22. The method of claim 21, wherein the iteratively transforming further comprises:
(a) initializing a t=0; (b) setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ1,i if i∈R1 and p1,i(0)=0 if i∉R1; (c) transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1 −1p1(t))=F12p1(t); (d) projecting p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i∈R2 and q2,i(t+1=p2,i(t) if i∉R2; (e) transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2 −1q2(t+1))=F21q2(t+1); (f) projecting q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈R1 and p1,i(t+1)=p2,i(t) if i∉R1; (g) checking for convergence by testing ∥p1(t+1)−p1(t)∥2>ε, and if so then setting t←t+1 and iterating (c) through (g); and (h) reconstructing a set of data {circumflex over (x)}=F1 −1p1(t); wherein: F1 and F2 are each K�K transforms, F1 −1 is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2. 23. The method of claim 21, wherein the iteratively transforming further comprises:
(a) initializing a t=0; (b) setting p1,i(0)=ŷ1,i if i∈R1 (i.e., received descriptions) and p1,i(0)=0 if i∉R1; (i.e., descriptions not received) (c) for each m=1, . . . , M−1 in turn: (i) transforming pm(t) into the coordinate system of Fm+1: {tilde over (p)}m+1(t)=Fm+1Fm −1Pm(t)=Fm,m+1pm(t); and (ii) projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1: pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 (d) transforming pM(t) into the coordinate system of F1: {tilde over (p)}1(t+1)=F1FM −1pM(t)=FM,1pM(t) (e) projecting {tilde over (p)}1(t+1) onto F1P1: p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 (k) checking for convergence, and if ∥pn(t+1)−pn(t)∥2 >epsilon for an n between 1 and M inclusive, then setting t←t+l and repeating (c) through (f), otherwise performing (g); and (g) reconstructing x: {circumflex over (x)}=Fn −1pn(t+1); wherein: F1 through FM are each K�K transforms, M is an integer larger than 1, each Fm −1 is the inverse transform of Fm, ŷ1 is a quantized version of y1, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and each ŷm componentwise lies between respective lower and upper quantization cell boundary vectors lm≦ŷm≦um, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and for each m, Rm⊂{1, . . . , K} is the set of indices of the descriptions received of ŷm. 24. A computer-readable medium having instructions stored thereon for causing a computer to perform the method of claim 22.
25. A computer-readable medium having instructions stored thereon for causing a computer to perform the method of claim 23.
26. A data-reconstruction mechanism for an image system, the mechanism comprising:
a module that receives a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of image data x, and wherein N>K; and a module that iteratively transforms the received set of data y′ using projections onto convex sets as calculated with a computer to produce a set of image data x′ representing the reconstructed set of image data x. 27. The mechanism of claim 26, wherein the module that iteratively transforms includes:
a module that transforms a set of data y1 to a set of data y2 using F2F1 −1, a module that sets components of the resulting set of data y2 corresponding to received components to those received components y2′, a module that transforms the resulting set of data y2 to a set of data y1 using F1F2 −1, a module that sets components of the resulting set of data y1 corresponding to received components to those received components y1′, and a module that transforms the resulting set of data y1 to a set of data x′ using F1 −1, wherein F1 and F2 are structured transforms that project onto convex sets.
28. The mechanism of claim 26, wherein the module that iteratively transforms includes:
(a) a module that initializes a t=0; (b) a module that sets an initial point p1(0) such that for each index i, p1,i(0)=ŷ1,i if i∈R1 and p1,i(0)=0 if i∉R1; (c) a module that transforms p1(t) into the coordinate system of F2 using p2(t)=F2(F1 −1p1(t))=F12p1(t); (d) a module that projects p2(t) onto F2Q such that for each index i, q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i∈R2 and q2,i(t+1)=p2,i(t) if i∉R2; (e) a module that transforms q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2 −1q2(t+1))=F21q2(t+1); (f) a module that projects q1(t+1) onto F1P such that for each index i, p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈R1 and p1,i(t+1)=p2,i(t) if i∉R1; (g) a module that checks for convergence by testing if ∥p1(t+1)−p1(t)∥2>ε, and if so then sets t←t+1 and iterates modules (c) through (g); and (h) a module that reconstructs a set of data {circumflex over (x)}=F1 −1p1(t); wherein: F1 and F2 are each K�K transforms, F1 −1 is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2. 29. The mechanism of claim 26, wherein the module that iteratively transforms includes:
(a) a module that initializes a t=0; (b) a module that sets an initial point p1(0) such that for each index i, p1,i(0)=ŷ1,i if i∈R1 (i.e., received descriptions) and p1,i(0)=0 if i∉R1; (i.e., descriptions not received) (c) for each m=1, . . . , M−1 in turn: (i) a module that transforms pm(t) into the coordinate system of Fm+1: {tilde over (p)}m+1(t)=Fm+1Fm+1Pm(t)=Fm,m+1pm(t); and (ii) a module that projects {tilde over (p)}m+1(t) onto Fm+1Pm+1: pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 (d) a module that transforms pM(t) into the coordinate system of F1: {tilde over (p)}1(t+1)=F1FM −1pM(t)=FM,1pM(t) (e) a module that projects {tilde over (p)}1(t+1) onto F1P1: p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 (l) a module that checks for convergence, and if ∥pn(t+1)−pn(t)∥2 >epsilon for an n between 1 and M inclusive, then sets t←t+1 and repeating (c) through (f), otherwise performs (g); and (g) a module that reconstructs x: {circumflex over (x)}=Fn −1pn(t+1); wherein: F1 through FM are each K�K transforms, M is an integer larger than 1, each Fm −1 is the inverse transform of Fm, ŷ1 is a quantized version of y1, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and each ŷm componentwise lies between respective lower and upper quantization cell boundary vectors lm≦ŷm≦um, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and for each m, Rm⊂{1, . . . , K} is the set of indices of the descriptions received of ŷm. 30. A computerized method of reconstructing data after a transmission on an erasure channel, the method comprising:
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 F1P; (c) transforming p1(t) into the coordinate system of F2; (d) projecting p2(t) onto F2Q; (e) transforming q2(t+1) into the coordinate system of F1; (f) projecting q1(t+1) onto F1P; (g) checking for convergence and if not sufficiently converged then iterating (c) through (g); and (h) reconstructing {circumflex over (x)}=F1 −1p1(t+1) wherein: F1 and F2 are each K�K transforms. 31. The method of claim 30, further comprising:
providing an initial set of data x having K dimensions; overcompletely transforming the set of data x to a set of data y having N dimensions, where N>K; transmitting the set of data y on the channel; and receiving a set of data y′ from the channel. 32. The method of claim 30, wherein
(a) initializing further includes initializing t=0; (b) starting further includes setting an initial point p1(0) such that for each index i, p1,i(0)=ŷ1,i if i∈R1 and p1,i(0)=0 if i∉R1; (c) transforming p1(t) further includes transforming p1(t) into the coordinate system of F2 using p2(t)=F2(F1 −1p1(t))=F12p1(t); (d) projecting p2(t) further includes projecting p2(t) onto F2Q such that for each index i: q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i∈R2 and q2,i(t+)=p2,i(t) if i∉R2; (e) transforming q2(t+1) further includes transforming q2(t+1) into the coordinate system of F1 using q1(t+1)=F1(F2 −1q2(t+1))=F21q2(t+1); (f) projecting q1(t+1) further includes projecting q1(t+1) onto F1P such that for each index i: p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈R1 and p1,i(t+1)=p2,i(t) if i∉R1; and (g) checking further includes checking for convergence by testing ∥p1(t+1)−p1(t)∥2>ε, and if so then setting t←t+1 and iterating (c) through (g). and wherein: F1 and F2 are each K�K transforms, F1 −1is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2. 33. The method of claim 30, wherein the (a) initializing t, (b) setting an initial point in F1P, (c) transforming p1(t) into the coordinate system of F2, (d) projecting p2(t) onto F2Q, (e) transforming q2(t+1) into the coordinate system of F1, (f) projecting q1(t+1) onto F1P, (g) checking for convergence and if not sufficiently converged then iterating (c) through (g); and (h) reconstructing {circumflex over (x)}=F1 −1p1(t+1) are performed in the order listed.
This application is related to co-pending application having Ser. No. 09/276,955 entitled APPARATUS AND METHOD FOR UNEQUAL ERROR PROTECTION IN MULTIPLE-DESCRIPTION CODING USING OVERCOMPLETE EXPANSIONS and assigned to the same assignee as the present application and filed on the same day herewith and incorporated by reference.
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawing hereto: Copyright� 1998-1999, Microsoft Corporation. All Rights Reserved.
Channels used to transmit data are sometimes “noisy” and can corrupt or lose portions of the data transmitted. A channel is said to “corrupt” portions of the data if it changes some data values during transmission without notice to the receiver. A channel is said to “lose” or “erase” portions of the data if it does not transmit some data values to the receiver, but notifies the receiver as to which data items were not transmitted. Accordingly, channels may be classified as “corruption” or “erasure” channels. An example of a corruption channel is a wireless communications system wherein data are occasionally corrupted due to electromagnetic noise in the atmosphere. Another example of a corruption channel is a storage system such as a magnetic disk, a Compact Disk Read-Only Memory (“CDROM”), or a Digital Versatile Disk (“DVD”), wherein data are occasionally corrupted due to scratches and dust on the recording media or due to writing or reading errors in the channels which move data onto or off from the media. An example of an erasure channel is a packet communications network wherein certain packets are lost in transmission, and wherein the receiver can detect which data are lost using packet sequence numbers and/or other means. Another example of an erasure channel is a storage system wherein the data are striped across a number of disks, any of which can fail at random, and whose failure can be detected, such that which data items are missing is known. Any corruption channel can appear, at a high level, to be an erasure channel, by appropriate low-level error detection processing. For example, a parity check or checksum word can be transmitted along with a block of data; if the received checksum does not agree with the received data, then an error is detected in the block of data, and the block of data can be considered erased by the channel. It is desirable to have ways to recover the data that is corrupted or lost. For example, image data that have either pixels or blocks that have been lost would have blank (perhaps white or black on a display monitor) or would appear to have “noise” or snow in the received images. A “pixel” is an individual picture element, and is generally represented by a single value indicating, for example, the intensity of image at a point, or the intensity of each of three colors. A “block” is a group of adjacent pixels, generally a rectangle. For example, a block could be a 16-by-16-pixel portion of a larger image.
Error-correction codes have been devised for both corruption and erasure channels, and are well known. (See S. Lin and D. J. Costello, Error Control Coding: Fundamentals and Applications, Prentice-Hall, 1983, herein Lin and Costello.) By far, the most common error-correction codes are based on linear transformations of the data to add redundancy. If x is a data vector with K elements, and F is an N�K matrix, with N≧K, then y=Fx is a vector with N elements. N−K of these elements can be considered redundant information. By transmitting the code vector y instead of x, the receiver can recover x even if some elements of y are corrupted or lost. In particular, if y is transmitted through an erasure channel, and no more than N−K elements of y are erased, then x can be recovered perfectly. For example, if x is a vector containing 3 binary elements, and F = [ 1 0 0 0 1 0 0 0 1 1 1 1 ] , then y is a vector containing 4 binary elements, the first three of which are equal to x (this is called the “systematic” part of y) and the last of which is equal to the sum of the bits in x, modulo 2. That is, the last bit of y is equal to the exclusive-OR, or parity, of x. If any three bits of y are recovered, then x can be recovered perfectly. On the other hand, if two or more bits of y are erased, then x cannot be recovered perfectly; the bits of x that are lost are unrecoverable in this case.
It is possible to apply error-correction codes to the transmission of signal data over erasure channels, by treating each signal element as a discrete M-ary symbol. However, this is inefficient. Signals need not be transmitted exactly, provided the approximation error between the signal and its reconstruction is small, on average. Applying a high-redundancy error-correction code can ensure this, but such a solution is expensive in terms of transmission capacity. An alternative is to use “unequal error protection,” which is a technique in which only the most important parts of the signal are protected with high redundancy. The less important parts are protected with low redundancy or not at all. One way to implement unequal error protection is the following. If the signal vector x contains elements that are 16-bit integers, then x can be stratified into 16 “bit-planes”. Then each bit-plane can be protected using a binary error-correction code with a redundancy commensurate with the importance of the bit-plane in approximating the signal vector x. (See for example J. Hagenauer, “Rate-Compatible Punctured Convolutional Codes (RCPC Codes) and their Applications,” IEEE Trans. on Communications, April 1988; A. Albanese, J. Bl�mer, J. Edmonds, M. Luby, and M. Sudan, “Priority Encoding Transmission,” IEEE Trans. Information Theory, November 1996; G. Davis and J. Danskin, “Joint Source and Channel Coding for Image Transmission Over Lossy Packet Networks,” SPIE Conf. on Wavelet Applic. of Digital Image Processing, August 1996.)
The present invention provides a POCS- (Projections Onto Convex Sets)- based algorithm for consistent reconstruction from multiple descriptions of overcomplete expansions. In particular, image data can benefit from the reconstructions provided by the present invention, even when too little data is available for a perfect recreation of the original image. Similarly, audio information is another type of data that can benefit. The algorithm operates in the data space RK rather than in the expanded space RN, N>K. By constructing the frame from two (or more) complete transform bases, all projections can be expressed in terms of forward or inverse transforms. Since such transforms are usually efficient to compute, the present invention can perform the reconstruction much faster than with previous methods. Indeed, the method of one embodiment provides overcomplete frame expansions of an entire image and reconstruction of the image after transmission through a channel that loses some of the coefficients.
One aspect of the present invention provides a POCS-based algorithm for consistent reconstruction of a signal xεRK from any subset of quantized coefficients yεRN in an N�K overcomplete frame expansion y=Fx, N=2K. By choosing the frame operator F to be the concatenation of two K�K invertible transforms, the projections may be computed in RK using only the transforms and their inverses, rather than in the larger space RN using the pseudo-inverse as proposed in earlier work. This enables practical reconstructions from overcomplete frame expansions based on wavelet, subband, or lapped transforms (one or more of which are used in some of the various embodiments of the present invention) of an entire image, which has heretofore not been possible.
In some embodiments, a set of data x is provided. The set of data x is overcompletely transformed to a set of coefficients y having N dimensions, where N>K. The resulting coefficients of y are quantized to obtain a set of indices j such that each coefficient yi lies in the ji th quantization region and each one of the indices j correspond to a respective quantization region. For example, the range of the coefficients of y might be −578.4 to +931.5. This range is divided into 1024 quantization regions, each assigned an index j, where each j is a number between 0 and 1023 inclusive. In some embodiments, the quantization regions are not all the same size. Subsets of the indices j are then entropy coded to obtain binary descriptions (e.g., combined into packets). The binary descriptions are then transmitted on a channel.
In some embodiments, the channel includes a storage medium, and the set of data y are stored onto a storage medium and read from the storage medium.
Another aspect of the present invention provides an apparatus and a corresponding computerized method of reconstructing a set of data x having K dimensions. The method includes receiving a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>K and the set of data y′ has ≦N dimensions. The method also includes iteratively transforming the received set of data y′ using projections onto convex sets as calculated with a computer to produce a set of data x′ representing the reconstructed set of data x.
In one embodiment, the method further includes providing an initial set of data x having K dimensions, overcompletely transforming the set of data x to a set of data y having N dimensions, where N>K; and transmitting the set of data y on a channel.
In another embodiment of the method, the transmitting on the channel further includes storing the set of data y onto a storage medium; and reading the set of data y from the medium.
FIG. 1 provides a brief, general description of a suitable computing environment in which the either the encoder-transmitter or the receiver-decoder, or both, of the invention may be implemented. The invention will hereinafter be described in the general context of computer-executable program modules containing instructions executed by a personal computer (PC). This is one embodiment of-many different computer configurations, some including specialized hardware circuits to enhance performance, that may be used to implement the present invention. Program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Those skilled in the art will appreciate that the invention may be practiced with other computer-system configurations, including hand-held devices, multiprocessor systems, microprocessor-based programmable consumer electronics, network personal computers (“PCs”), minicomputers, mainframe computers, and the like which have multimedia capabilities. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote memory storage devices.
When placed in a LAN networking environment, PC 20 connects to local network 51 through a network interface or adapter 53. When used in a WAN networking environment such as the Internet, PC 20 typically includes modem 54 or other means for establishing communications over network 52. Modem 54 may be internal or external to PC 20, and connects to system bus 23 via serial-port interface 46 in the embodiment shown. In a networked environment, program modules, such as those comprising Microsoft� Word which are depicted as residing within PC 20 or portions thereof may be stored in remote-storage device 50. Of course, the network connections shown are illustrative, and other means of establishing a communications link between the computers may be substituted.
1. J. K. Wolf, A. D. Wyner, and J. Ziv. Source coding for multiple descriptions. Bell System Technical Journal, 59(8):1417-1426, October 1980; herein “Wolf, et al.”;
2. T. M. Cover and A. El Gamal. Achievable rates for multiple descriptions. IEEE Trans. Information Theory, 28(6):851-857, November 1982; herein “Cover et al.”;
3. L. H. Ozarow. On the source coding problem with two channels and three receivers. Bell System Technical Journal, 59(8):1909-1922, October 1980; herein “Ozarow”;
4. R. Ahlswede. The rate-distortion region of a binary source for multiple descriptions without excess rate. IEEE Trans. Information Theory, 31:721-726, November 1985; herein “Ahlswede”;
5. Z. Zhang and T. Berger. Multiple-description source coding with no excess marginal rate. IEEE Trans. Information Theory, 41(2):349-357, March 1995; herein “Zhang et al.”).
6a. V. A. Vaishampayan. “Vector quantizer design in diversity systems,” In Proc. Conf. On Information Sciences, 2nd September, 1991; herein “Vaishampayan 1”;
6b. V. A. Vaishampayan. “Design of multiple-description scalar quantizers,” IEEE Trans. Information Theory, 39(3):821-834, May 1993; herein “Vaishampayan 2”;
7. V. A. Vaishampayan. “Application of multiple-description codes to image and video transmission,” In Proc. 7th Int'l Workshop on Packet Video, Brisbane, Australia, March 1996; herein “Vaishampayan 3”;
8. S. D. Servetto, K. Ramchandran, V. Vaishampayan, and K. Nahrstedt. “Multiple description wavelet based image coding,” In Proc. Int'l Conf. Image Processing, Chicago, Ill., October 1998. IEEE, herein “Servetto et al.”;
9. H. Jafarhkani and V. Tarokh. “Multiple description trellis coded quantization,” In Proc. Int'l Conf. Image Processing, Chicago, Ill., October 1998. IEEE, herein “Jafarhkani et al.”;
10. M. Srinivasan and R. Chellappa. “Multiple description subband coding,” In Proc. Int'l Conf. Image Processing, Chicago, Ill., October 1998. IEEE; herein “Srinivasan”.)
In the second approach, pioneered by Wang, Orchard, and Reibman, MD quantizers are constructed by separately describing (i.e., quantizing and coding) the N coefficients of an N�N block linear transform, which has been designed to introduce a controlled amount of correlation between the transform coefficients (see:
11. Y. Wang, M. T. Orchard, and A. R. Reibman. Multiple description image coding for noisy channels by pairing transform coefficients. In Proc. Workshop on Multimedia Signal Processing, pages 419-424. IEEE, Princeton, N.J., June 1997; herein “Wang et al. 1”,
12. M. T. Orchard, Y. Wang, V. A. Vaishampayan, and A. R. Reibman. Redundancy rate-distortion analysis of multiple description coding. In Proc. Int'l Conf. Image Processing, Santa Barbara, Calif., October 1997. IEEE; herein “Orchard et al.”,
13. V. K. Goyal and J. Kova{haeck over (c)}ević. Optimal multiple description transform coding of Gaussian vectors. In Proc. Data Compression Conference, pages 388-397, Snowbird, Utah, March 1998. IEEE Computer Society; herein “Goyal et al. 1”,
14. V. K. Goyal, J. Kova{haeck over (c)}ević, R. Arean, and M. Vetterli. Multiple description transform coding of images. In Proc. Int'l Conf. Image Processing, Chicago, Ill., October 1998. IEEE; herein “Goyal et al. 2”,
15. Y. Wang, M. T. Orchard, and A. R. Reibman. Optimal pairwise correlating transforms for multiple description coding. In Proc. Int'l Conf. Image Processing, Chicago, Ill., October 1998. IEEE; herein “Wang et al. 2”.)
In the third approach, pioneered by Goyal, Kova{haeck over (c)}ević, and Vetterli, M D quantizers are constructed by separately describing the N coefficients of an overcomplete N�K tight frame expansion (see Goyal et al. 2 cited above and
16. V. K. Goyal, J. Kova{haeck over (c)}ević, and M. Vetterli. Multiple description transform coding: robustness to erasures using tight frame expansions. In Proc. Int'l Symp. Information Theory, page 408, Cambridge, Mass., August 1998. IEEE; herein “Goyal et al. 3”.).
In this embodiment, the N-dimensional vector y 217 is scalar quantized by quantizer 218. In scalar quantization, each element yi of the N-dimensional vector y is mapped (i.e., using quantizer mapping 288) by a quantizer Qi to the index ji of the quantization interval [li, ui) which contains yi. For example, quantizer Qi may map yi to 0 if yi is between −5 and 5, to 1 if yi is between 5 and 15, to 2 if yi is between 15 and 25, and so forth, as illustrated in FIG. 2C. The output of quantizer 218 is the set of indices j 221. The inverse quantizer mapping 296 (performned by block 226) provides the received values 227, that include one or more of li, ui, ŷi.
Thus, if yi is the value 27.109, ji would be the index 3, and the interval [li,ui) would be [25,35). Often yi is represented by the midpoint or centroid of the interval, which would be ŷi=30 in this case. If the interval lengths are all constant, then the quantizer is called a uniform scalar quantizer, and the interval length is called the quantizer stepsize. This invention does not require the interval lengths to be constant, either within a quantizer or between quantizers. Thus, in other embodiments, non-uniform interval lengths are used. In particular, in one embodiment (explained further in a section below), the interval length changes between quantizers, to provide unequal redundancy encoding, based on data significance. In principle, it is also possible to perform vector quantization on the N-dimensional vector y. (See A. Gersho and R. M. Gray, Vector Quantization and Signal Compression, Kluwer, 1991, herein Gersho and Gray.) However only scalar quantization is discussed herein.
In some embodiments, each of the binary descriptions 223 is embedded into a packet that is transmitted on a packet network or channel 222. Some of the descriptions 223 may be erased in the transmission or storage channel 222. In that, case, only the indices in groups whose descriptions are received 223′ can be entropy decoded by entropy decoder 224. Entropy decoding is the inverse of entropy encoding, i.e., the process of mapping a binary string back into a set of discrete symbols. The number of indices that are entropy decoded is only N′≦N after potential erasures. Each decoded index ji 225 is an indicator of the fact that the corresponding coefficient yi lies in a particular interval [li, ui). The inverse quantizer Qi −1 226 therefore maps ji into the tuple [li, ui), possibly along with the reconstruction level ŷi (together denoted as received information 227), as illustrated in FIG. 2B. The reconstruction 290 of the vector {circumflex over (x)} from the received information li, ui, ŷi 227 can take a number of forms, described next.
Without loss of generality, assume that descriptions of the first N′ coefficients are received, and that descriptions of the last N″=N−N′ coefficients are erased. Let y′ denote the first N′ coefficients, and let y″ denote the last N″ coefficients, so that y = [ y ′ y ″ ] = [ F ′ F ″ ]   x = Fx , where F′ is N′�K and F″ is N″�K. A classical way for the decoder to reconstruct x from the received quantized coefficients ŷ′ is to use the linear reconstruction
where (F′)+ is the pseudo-inverse of F′. The pseudo-inverse can be computed from the singular value decomposition F′=U�diag (σ1, . . . ,σN′)Vt (see 17 B. Noble and J. W. Daniel. Applied Linear Algebra. Prentice-Hall, Englewood Cliffs, N.J., 2nd edition, 1997.)
as (F′)=V�diag (σ1 −1, . . . , σN′ −1)�Ut. This is equal to (F′)+=((F′)t(F′)−1(F′))t when F′ has full rank, i.e., when at least K descriptions are received (assuming any K rows of F are linearly independent). It can be shown that the reconstruction (Equation 1) has the property that x ^ lin = argmin x   y ^ ′ - F ′  x  2 . ( Equation   2 ) That is, when N′≧K, it chooses {circumflex over (x)}lin∈RK to be the coordinates of the point F′{circumflex over (x)}lin in the K-dimensional subspace spanned by the columns of F′ which is closest to ŷ∈RN′, i.e., it projects ŷ′ onto the subspace F′RN′. Furthermore, when N′<K, i.e., when the x that minimizes (Equation 2) is not unique, then the reconstruction (Equation 1) chooses an x with minimum norm.
The linear reconstruction (Equation 2) is not statistically optimal. The optimal reconstruction {circumflex over (x)}opt, which minimizes the expected (squared error) distortion E∥X−{circumflex over (X)}opt∥2, is the conditional mean of X given the descriptions yi∈[li, ui) received. That is,
{circumflex over (x)} opt =E[X|Q(F′X)=ŷ′]=E[X|l′≦F′X<u′], (Equation 3)
where the relations l′≦y′ and y′<u′ are to be taken componentwise. Unfortunately, the conditional expected value of X given that it lies in the region Q−1(ŷ′)={x:l′≦F′x<u′} is hard to compute. FIG. 3A shows for K=2 and N′=3 a region Q−1(ŷ′) 160 for some ŷ′. Note that the regions Q−1(ŷ′) for different ŷ′ are all dissimilar in general.
FIG. 3A is a graphical representation 167 of the set 160 of all possible reconstructions consistent in a quantized three-dimensional description. The three-dimensional description includes descriptions j1 163 having a quantization interval 164 with a lower limit l1 and upper limit u1, description j2 161 having a quantization interval 162 with a lower limit l2 and upper limit u2, and description j3 165 having a quantization interval 166 with a lower limit l3 and upper limit u3. The reconstructed value is somewhere within shaded area 160. Because of the effects of quantization on each of the descriptions, an area at the intersection of the descriptions remains. If only two descriptions were used, the intersection would be a square. When three descriptions are used, the area is reduced to quadrilateral 160.
Although the optimal reconstruction (Equation 3) is difficult to compute, one thing is certain: x lies in Q−1(ŷ′), and hence, since Q−1(ŷ′) is convex, the optimal reconstruction (Equation 3) lies in Q−1(ŷ′). Any reconstruction {circumflex over (x)} which does not lie in Q−1(ŷ′) is said to be inconsistent (See V. K. Goyal, M. Vetterli, and N. T. Thao. Quantized overcomplete expansions in Rn: Analysis, synthesis, and algorithms. IEEE Trans. Information Theory, 44(1):16-31, January 1998; herein “Goyal et al. 4”). Goyal et al. 4 describes one conventional POCS reconstruction method. FIG. 3, adapted from Goyal et al., shows again for K=2 and N′=3 an inconsistent reconstruction from the linear projection (Equation 1). It is intuitive that consistent reconstructions have smaller expected squared error distortion than inconsistent reconstructions. In fact, Goyal et al. show that while the expected distortion from linear reconstructions is asymptotically proportional to 1/N, the expected distortion from consistent reconstructions is O(1/N2) in at least one DFT-based case, and they conjecture this to be true under very general conditions, when the frame is tight.
FIG. 3 is a graphical representation 168 of an inconsistent reconstruction 177 from a quantized three-dimensional description. The centroid ŷ′ 187 of cube 180 would project to {circumflex over (x)}lin 177, which is a distance 176 in the subspace away from a consistent reconstruction {circumflex over (x)}con 178 (which may be thought of as in the intersection of cube 180 with plane F′RK 170). Centroid ŷ′ 187 is a distance 186 out of the subspace away from {circumflex over (x)}lin 177.
An algorithm used by some embodiments of the present invention for producing consistent reconstructions {circumflex over (x)}con∈Q−1(ŷ′) is the POCS (Projections Onto Convex Sets) algorithm (see
19. D. C. Youla. Mathematical theory of image restoration by the method of convex projections. In H. Stark, editor, Image Recovery: Theory and Applications. Academic Press, 1987; herein “Youla”.).
In the POCS algorithm for M=2 (i.e., where only two functions are used, as more fully described below), an arbitrary initial point pt∈Rn is alternately projected onto two convex sets Q⊂Rn and P⊂Rn, q t + 1 = argmin q ∈ Q   p t - q  2 ( Equation   4 ) p t + 1 = argmin p ∈ P   q t + 1 - p  2 ( Equation   5 ) until pt and qt converge to the intersection of P and Q, or if the intersection is empty, until pt and qt respectively converge to the sets {p∈P:∥p−q∥2≦∥p′−q∥2, ∀p′∈P, ∀q∈Q} and {q∈Q:∥q−p∥2≦∥q′−p∥2, ∀q′∈Q, ∀p∈P}. The POCS algorithm described above can be extended in the obvious way to more than two sets. For example, a point in the intersection of three convex sets P, Q, and R is given by the limit of r t + 1 = argmin r ∈ R   p t - r 0  2 ,  q t + 1 = argmin q ∈ Q   r t + 1 - q  2 ,  and p t + 1 = argmin p ∈ P   q t + 1 - p  2 . For consistent reconstruction of x∈RK from the quantized frame expansion ŷ′=Q(F′x)∈RN′, Goyal et al. (Goyal et al. 4) suggest alternately projecting the initial point ŷ′ onto the two convex sets Q=F′RK⊂RN′ and P=Q−1(ŷ′)⊂RN′, as shown in FIG. 3. The first projection (Equation 4) onto the linear subspace F′RK can be accomplished, as usual, by the pseudo-inverse (Equation 1). The second projection (Equation 5) onto the quantization bin Q−1(ŷ′) can be accomplished by component-wise clipping to the quantization bin. That is, the vector ŷ′, l′≦ŷ′≦u′, closest to an arbitrary vector y′∈RN′ is given component-wise by
{tilde over (y)} i′=clip(y i ′, l i , u i)=min{max{y i ′, l i }, u i}. (Equation 6)
To reduce the computational complexity of consistent reconstruction, Goyal, Vetterli, and Thao instead suggest finding {circumflex over (x)}∈Q−1(ŷ′) by solving the linear program max ct{circumflex over (x)} subject to [ F ′ - F ′ ]   x ^ ≤ [ u - l ] , for an arbitrary objective functional c. They furthermore suggest that by varying c, it may be possible to find all the vertices of Q−1(ŷ′), whereupon they can be averaged to approximate the region's centroid. (However, they do not appear to follow this latter suggestion.) Although this method avoids the high cost of computing the pseudo-inverse, the complexity of the simplex algorithm for solving the linear program is still O(KN) operations per pivot. This complexity does not present a problem when K and N are small. Goyal, Kova{haeck over (c)}ević, and Vetterli (see Goyal 3 and Goyal 2) apparently apply the algorithm for K=8 and N′ up to 10.
We are more interested in decoding multiple descriptions of overcomplete expansions based on overlapping functions, such as provided by wavelet, subband, or lapped transforms. In this case, the N�K frame operator F typically operates on an entire image at a time, for which K=512�512=262,144 is common; N may be twice that. Clearly, in such cases it is not feasible to require O(KN) operations for consistent reconstruction. For wavelet, subband, or lapped transforms, where N=K, F is sparse. In this case, consistent reconstruction can be performed using O(KL) operations, where L is the length of the support of the basis functions. Since L is usually on the order of a few hundred, such reconstruction is eminently feasible, and is used in all modern subband decoders. Both the pseudo-inverse and pivot operations destroy the sparsity of F. The present invention provides an algorithm for consistent reconstruction from multiple descriptions of overcomplete expansions that preserves the efficiency of the sparse representation of F when the basis functions have finite support L. That is, the algorithm has complexity O(KL). The algorithm of the present invention is based on POCS, but the projections are performed in the lower dimensional space RK, rather than in the space RN′.
Let F1, . . . , FM be M invertible K�K transforms. For example, F1 may be a wavelet transform (over an image x∈RK suitably extended), F2 may be the identity transform, another wavelet transform, or the same wavelet transform over a 1-pixel shift of the image and so forth for F3, . . . , FM. Note: in some embodiments as described below in FIG. 7A and FIG. 8A, M=2, and only F1 and F2 are used. However, in general, M can be any integer 2 or larger, as described below in FIG. 7B and FIG. 8B. Let the K-dimensional vectors y1=F1x, . . . , yM=FMx be the M corresponding sets of transform coefficients for x∈RK. Then y = [ y 1 ⋮ y M ] = [ F 1 ⋮ F M ]   x = Fx ( Equation   7 ) defines an overcomplete N�K frame expansion of x with redundancy N/K=M. The expansion is tight if F1, . . . , FM are orthonormal. (A frame expansion y=Fx is “tight” if there exists a positive constant M such that for all x,∥Fx∥2=M∥x∥2. In general, for the multiple description scenario, tightness of the original frame F is of little consequence, because the received frame F′ will, in general, not be tight.)
The present invention does not require orthononmality of F1, . . . , FM, but it is best if F1, . . . , FM are orthonormally related, i.e., for all i,j, Fij=FjFi −1 is orthonormal, at least approximately, to ensure convergence of the POCS algorithm.
Let ŷ1, . . . , ŷ2 be the quantized versions of y1, . . . , yM, respectively, such that ŷ1, . . . , ŷM lie (componentwise) between upper and lower quantization cell boundary vectors l1≦ŷ1≦u1 through lM≦ŷM≦uM, respectively.
Let R1⊂{1, . . . , K} be the set of indices of the descriptions received by the decoder for ŷ1, let R2⊂{1, . . . , K} be the set of indices of the descriptions received by the decoder for ŷ2 and so forth through RM. Descriptions not received by the decoder include those that have been erased as well as not sent at all.
A reconstruction {circumflex over (x)} is consistent with the received descriptions if and only if it lies in the intersection of the following M sets (where M is a number 2 or larger and a similar equation is provided for all intermediate values between 1 and M): P l = { x  :   l 1 , i ≤ ( F 1  x ) i ≤ u 1 , i ,  i ∈ R 1 }    ⋮ ( Equation   8 ) P M = { x  :   l M , i ≤ ( F M  x ) i ≤ u M , i ,  i ∈ R M } ( Equation   9 ) The following steps illustrate an exemplary basic algorithm of one embodiment of the present invention for finding a consistent reconstruction of x from the received descriptions.
1. Initialization. Start from an initial point in F1P1:
p1,i(0)=ŷ1,i if i∈R1 (i.e., received descriptions) and
p1,i(0)=0 if i∉R1; (i.e., descriptions not received)
{tilde over (p)}m+1(t)=Fm+1Fm −1Pm(t)=Fm,m+1pm(t);
b. Project {tilde over (p)}m+1(t) onto Fm+1Pm+1;
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 3. Transform pM(t) into the coordinate system of F1:
{tilde over (p)}1(t+1)=F1FM −1pM(t)=FM,1pM(t)
4. Project {tilde over (p)}1(t+1) onto F1P1:
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i},u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 5. Check for convergence. If ∥p1(t+1)−p1(t)∥2>epsilon, then set t←t+1 and go to Step 2.
{circumflex over (x)}=F1 −1p1(t+1).
5′. Checkfor convergence. If ∥pn(t+1)−pn(t)∥2>epsilon, then continue transforming and projecting until M, then set t←t+1 and go to Step 2, else:
{circumflex over (x)}=Fn −1pn(t+1).
FIG. 7A is a flowchart 700A of one embodiment of the present invention, where M=2. FIG. 7B is a flowchart 700B of another, more generalized embodiment of the present invention, where M is any number 2 or larger. FIG. 7C is a flowchart 700C of another, more generalized embodiment of the present invention, where convergence checking is performed in the middle of the loop. FIGS. 7B and 7C are otherwise identical to FIG. 7A, which will now be described. Flowchart 700A represents an embodiment used to reconstruct a set of data {circumflex over (x)} from a received set of data y′, wherein M=2 and the received data are mapped back and forth between F1P and F2Q. Block 710 performs an initialization operation to initialize a point (e.g., a vector in N dimensional space) in F1P, and to set t=0. In one such embodiment, the operations set forth in Step 1 above are performed in block 710. Control then passes to block 720. Block 720 performs an operation transforming p1(t) into the coordinate system of F2. In one such embodiment, the operations set forth in Step 1 above are performed in block 720. Control then passes to block 730. Block 730 performs an operation projecting p2(t) onto F2Q. In one such embodiment, the operations set forth in Step 3 above are performed in block 730. In one embodiment, the functions of blocks 720 and 730 are performed as a single function, labeled block 725.
Control then passes to block 760. Block 760 performs an operation checking for convergence and if not sufficiently converged, then iterating blocks 720 through 760. In one such embodiment, the operations set forth in Step 6 above are performed in block 760. Control then conditionally passes to block 770 if convergence has been achieved, otherwise control passes back to block 720. Block 770 performs an operation reconstructing {circumflex over (x)}=F1 −1p1(t+1) in order to generate a recovered set of data. In one embodiment, F1 and F2 are each K�K transforms. In some embodiments, F1 and F2 are each K�K linear transforms.
In one embodiment, the received set of data y′ are the coefficients received from an erasure channel that transmitted an overcomplete expansion of an original image x, and the recovered set of data {circumflex over (x)} represents a reconstruction of the original image. In one such embodiment, the original image x is a portion of a larger image, for example, a 512-by-512-pixel portion of a 1024-by-1024-pixel image. In another embodiment, the original image x is a portion (e.g., one frame) of a sequence of images representing a motion picture. In another embodiment, the received set of data y′ are the coefficients received froman erasure channel that transmitted an overcomplete expansion of an original audio segment x, and the recovered set of data {circumflex over (x)} represents a reconstruction of the original audio segment.
The present invention uses any number of K�K transform functions and mappings (up to M transform-and-mapping operations) to reconstruct the received data, with typical embodiments shown in FIG. 8A, FIG. 8B, and FIG. 8C. In some embodiments, the original encoding performs an overcomplete N�K frame expansion using at least portions of each of the M transforms, as described below.
FIG. 8A is a flowchart 800A of one embodiment of the present invention for the case M=2. FIG. 8B is a flowchart 800B of one embodiment of the present invention for the general case M, where the convergence test 870 is performed after a complete set of transform-mappings. FIG. 8C is a flowchart 800C of one embodiment of the present invention for the general case M, where the convergence test 870 is performed at an arbitrary point in the transform-mappings. The term “FIG. 8” refers generally to FIG. 8A, FIG. 8B, and FIG. 8C.
Flowchart 800A represents one embodiment used to generate an overcomplete expansion y from an initial set of data x, to transmit y through a lossy channel, and then to reconstruct a set of data {circumflex over (x)} from a received set of data y′. Block 201 represents a set of data x that is provided. In one embodiment, set of data x is an image, for example, a 512-by-512-pixel image (which, in some embodiments, is a portion of a large image) that is to be transmitted through erasure channel 222. Block 812 performs an overcomplete N�K frame expansion such as defined in Equation 7 above to generate set of data y 217. In one such embodiment, this is accomplished by using K�K linear transform F1 811 to generate a first set of data y1 815 and K�K linear transform F2 812 to generate a second set of data y2 816. Some or all of the first set of data y1 815 and some or all of the second set of data y2 816 are concatenated to form the set of data y 2l7. In some embodiments, block 210 implements a N�K transform F, wherein all of the first set of data y1 815 is included in y, and N−K coefficients of the second set of data y2 816 are included. In one such embodiment, the N−K coefficients of the second set of data y2 816 implement unequal error protection as further described in a section below. In some embodiments, this provides better reconstruction of the most important aspects of x, for example, the most-significant bits of pixels of an image.
In the embodiment shown, the received set of data 227 is used as input data to the iterative process that includes 830, 840, 850, 860, 870, and 880. The recovery portion of method 800 starts by generating an initial point p1(0) 829 in F1P1 using the following equations:
p 1,i(0)=ŷ 1,i if i∈R 1 and (i.e., description is received) and
p 1,i(0)=0 if i∉R 1; (i.e., description is not received)
Block 830 operates to transform p1(t) (829 or 865) into the coordinate system of F2, effectively using the inverse transform of F1 and then the F2 transform. In some embodiments, this is accomplished using a single K�K transform F12 as follows:
{tilde over (p)} 2(t)=F 2(F 1 −1 p 1(t))=F 12 p 1(t).
Block 840 operates to project p2(t) 835 onto F2P2 as follows:
p 2,i(t)=min{max{{tilde over (p)} 2,i(t),l 2,i },u 2,i} if i∈R 2 and
p 2,i(t)={tilde over (p)} 2,i(t) if i∈R 2.
{tilde over (p)} 1(t+1)=F 1(F 2 −1 p 2(t))=F 21 p 2(t).
Block 860 operates to project {tilde over (p)}1(t+1) 855 onto F1P1 as follows:
p 1,i(t+1)=min{max{{tilde over (p)} 1,i(t+1),l 1,i },u 1,i} if i∈R1 and
p 1,i(t+1)=p 2,i(t) if i∈R 1.
If ∥p1(t+1)−p1(t)∥2>∈, then set t←t+1 and go to block 830 (and, in one embodiment, load p1(t+1) from block 865 into block 829 as the next p1(t)). Block 880 operates to reconstruct x into the output block {circumflex over (x)} 202 as follows:
In FIG. 8C (which is otherwise similar to FIG. 8B), convergence checking is performed within the transformation-projection loop. In this embodiment, block 870 operates to check for convergence as follows: After the Fn−1,n transform-projection of blocks 864, 865, 866, and 867, If ∥pn(t+1)−pn(t)∥2>∈, then continue, else block 880 operates to reconstruct x into the output block {circumflex over (x)} 202 as follows: {circumflex over (x)}=Fn −1pn(t+1). After the FM1 transform-projection of blocks 894, 895, 896, and 897, set t←t+1 and go to block 830 (and, in one embodiment, load p1(t+1) from block 865 into block 829 as the next p1(t)).
The second improvement that is made in some embodiments, when the number of received descriptions N′=|R1+ . . . +|RM 51 is less than K, is to reconstruct missing components to their conditional expected values given the received descriptions. The basic algorithm already does this if y1 has a spherical density (e.g., if the components of y1 are independent identically distributed Gaussian random variables). The reason is that if y1 has a spherical density, then the subvector y1″ consisting of the erased components {y1,i}i∉R 1 has a spherical conditional density given the received components {y1,i}i∈R 1 . Furthermore, given the received components {y2,i}i∈R 2 through {ym,i}i∈R M , y1″ must lie in some linear (|R2|+ . . . +|RM|) dimensional variety. Thus, the conditional density of y1″ given all the received components is a spherical distribution in some linear variety with its mean at the point where the all-zero vector y1″=0 projects onto the linear variety. Therefore, setting the missing components in the initial point p1(0) in Step 1 of the basic algorithm will result in their being replaced, after projection in Step 3, by their conditional means given the received descriptions. Although in most circumstances the density of y1 is not spherical, it will be approximately spherical if F1 is a decorrelating transform and x is preconditioned such that it has zero mean and the variance of each y1 is constant. More precisely, if σi 2 is the variance of (F1x)i, then replace x by F1 −1 diag (σ1 −1, . . . , σK −1) F1 (x−EX). The resulting vector y1 will have approximately spherical density.
Results are presented using the given algorithm to reconstruct a K dimensional vector x. In one test, vector x is originally formed by taking the inverse DCT (discrete cosine transform; see the book by M. Vetterli and J. Kova{haeck over (c)}ević, Wavelets and Subband Coding, Prentice Hall, 1995; page 340, page 374; herein “Vetterli et al.” which provides a general reference for various types of transforms used in various embodiments of the present invention.) of a vector of transform coefficients y1, which are in turn sampled from a Gaussian distribution with mean 0 and diagonal covariance with entries inversely proportional to frequency, i.e., Y1,k˜N(0, σ2/(1+ck)), k=0, 1, . . . , k−1, where σ2 and c are constants. The vector x is then transformed using a DCT for F1 and the identity transform for F2, yielding y1=DCT(x) and y2=x. The transform coefficient vectors y1 and y2 are uniformly scalar quantized using a step size of Δ. In one experiment, K=512, σ2=1.0, Δ=0.1, and c=0.013, so that the variance ofthe last coefficient is σ2/8.
Vetterli et al. (page 374) provides the following definitions of the DCT used in one embodiment of the present invention: y 0 = 1 ( N )  ∑ n = 0 N - 1  x n ( Equation   10 ) y k = 2 N   ∑ n = 0 N - 1  x n  cos   ( 2   π  ( 2  n + 1 )  k 4  N ) ,   k = 1 , …  , N - 1 ( Equation   11 ) All of the quantized coefficients ŷ1 are transmitted, along with � of the quantized coefficients ŷ2 (randomly selected), for a redundancy of N/K=1.25. Of these 640 transmitted coefficients, random subsets are received. The reconstruction algorithm is run for each subset received. The performance of the algorithm is measured by averaging the reconstruction error over all subsets having the same number of coefficients. The performance of a comparable forward-error-correction system is also obtained. If the number of coefficients received in the FEC system is not enough to reconstruct the vector, then only the systematic portion of the received coefficients is used.
A plot of N″ vs. SNR 191 (signal-to-noise ratio) in dB (decibels) is shown in FIG. 4. There is a slight gain with the present system (as indicated by graph line 192) over the plain FEC system (as indicated by graph line 193) if all the coefficients are received. If fewer than K coefficients are received, then the present system always outperforms the FEC system. However, there is substantial loss if exactly K coefficients are received. This is due to the fact that the partition induced by the received coefficients is usually not cubic since there is a mixture of coefficients from the two transforms. Also, the point found by the POCS algorithm is not necessarily the centroid of the cell. The exact value of the loss is somewhat arbitrary; performance of the FEC system when more than K coefficients are received can be made as high as desired by reducing Δ, whereas performance of even the optimal reconstruction when fewer than K coefficients are received reaches an upper bound independent of Δ.
The present invention represents a POCS-based algorithm for consistent reconstruction of a signal x∈RK from any subset of quantized coefficients y∈RN in an N�K overcomplete frame expansion y=Fx, N=MK (where M is two or larger). By choosing the frame operator F to be the concatenation of two or more K�K invertible transforms, the projections may be computed in RK using only the transforms and their inverses, rather than in the larger space RN using the pseudo-inverse as proposed in earlier work. This enables practical reconstructions from overcomplete frame expansions based on wavelet, subband, or lapped transforms (one or more of which are used in some of the various embodiments of the present invention) of an entire image, which has heretofore not been possible.
In multiple-description quantization using overcomplete (frame) expansions as described above, an input signal x∈RK is represented by a vector y=Fx∈RN, where N>K. F is a so-called “frame operator,” whose N rows span RK. The coefficients of y are scalar quantized to obtain ŷ and then are independently entropy coded and transmitted in (up to) N descriptions. The decoder receives descriptions of only N′≦N coefficients after potential erasures, and reconstructs the signal from the received descriptions. Each received description is an encoding of the fact that some coefficient yi lies in a particular quantization interval, say [li, ui).
In the description above, a practical method and system are presented for consistent reconstruction of x given any subset of the transmitted quantization intervals [li, ui), where l≦Fx<u (pointwise). In some embodiments of the method and/or system, F has the form F = [ F 1 F 2 ] where F1 is a K�K transform, and F2 is another K�K transform, orthogonally related to F1 (i.e., F2=QF1 for some orthogonal transform Q). For example, F1 may be a wavelet transform (over an image x∈RK. suitably extended), and F2 may be the identity transform, another wavelet transform, or the same wavelet transform over a 1-pixel shift of the image. The algorithm used by the present invention reconstructs x from the received quantization intervals [li, ui) using alternating projections onto convex sets. The notation “[li, ui)” indicates the interval greater than or equal to li and less than ui.
In the description above, multiple-description quantization is compared using the above reconstruction algorithm to a systematic error-correction code, in a hypothetical transmission system. In the hypothetical transmission system, the coefficients in the K-dimensional vector y1=F1x are uniformly scalar quantized to B bits of precision, and are separately transmitted in K B-bit descriptions. Redundancy is provided by transmitting an additional N−K B-bit descriptions. In the multiple-description case, the additional descriptions encode the first N−K coefficients of the real vector y2=F2x uniformly scalar quantized to B bits of precision. In one embodiment, reconstruction is performed by the aforementioned algorithm. In the error-correction case, the additional packets contain the N−K B-bit parity check symbols from the finite field GF(2 B) generated by a systematic (N, K) error-correction code. Reconstruction is given by {circumflex over (x)}=F1 −1ŷ1 when N−K or fewer packets are lost. When more than N−K packets are lost, reconstruction is given by the same formula, with the lost coefficients set to zero in ŷ1. Results are generated in both cases by simulating random reception of N′ out of N descriptions (in repeated trials) for N′=0, . . . , N. FIGS. 11 and 12 show PSNR (peak signal-to-noise ratio) results for Lena comparing multiple-description and error control coding, with FIG. 11 showing reconstruction results for equal protection and FIG. 12 showing reconstruction results for unequal error protection. FIG. 11 shows the expected squared reconstruction error in each case as a function of N′, for the image called “Lena”. Here, F1 is the 9/7 biorthogonal wavelet transform and F2 is the separable full-image DCT. When N′<K, MD (Multiple Description) quantization outperforms error-correction coding (ECC) by up to 14 dB, while for N≧K (except at N′=N), error-correction coding outperforms MD quantization by up to 3 dB. The 3 dB loss for MD quantization is apparently due to the fact that the quantization cells in the signal domain are not cubic since the received coefficients correspond to a mixture of basis functions from the transforms F1 and F2 and hence are not orthonormal.
The above comparison is somewhat unfair to the error-correction coding approach, because, as is well known, better performance can be achieved by protecting different bits with different redundancies. If the bits of each quantized coefficient are labeled 1, . . . , B from the least to the most significant, then loss of the bth bit increases the squared error of the reconstruction in proportion to 22b. Indeed, if εK(N) is the probability that an (N,K) code cannot recover a symbol, then the optimal redundancy N/K for coding the bth bit is approximately given by 22bε′K(N)=constant, where ε′K(N) is the slope of εK(N) at N. This is a classic bit-allocation problem whose solution gives the optimal allocation of parity bits to different bit planes of the transform coefficients so as to minimize the expected squared-reconstruction error. Unequal error protection has been employed in other contexts.
This section describes embodiments that include unequal error protection for multiple-description quantization. One embodiment of the present invention is illustrated in FIG. 13 that shows components of the vectors y1=F1x and y2=F2x depicting which bits are to be transmitted in one embodiment of unequal error protection. The components of the vectors y1=F1x and y2=F2x are depicted in a sequence from left to right, while the bits of each component are depicted from most to least significant, top to bottom. The shaded region shows which bits are to be transmitted. All of the bits from the coefficients y, are transmitted, while only some of the bits from the coefficient y2 are transmitted. Looked at in one way, each bit plane (or row of bits) has its own redundancy. The most significant bits have the highest redundancy while the least significant bits have the lowest redundancy. Looked at in another way, each coefficient is quantized to its own number of bits. All of the coefficients of y1 are quantized to B bits, but the ith coefficient of y2 is quantized to bi≦B bits, with bi decreasing to 0 as the index i of the coefficient increases. The quantized coefficients are transmitted as usual; a random number of them are erased. In one embodiment, the reconstruction procedure, using the iterative algorithm of the present invention, does not change, except for the fact that the received quantization intervals [li, ui) now vary in width to reflect the unequal stepsizes for the different coefficients. These stepsizes need not be related by powers of two. Thus, in some embodiments, the stepsizes are related by powers of two; and in other embodiments, the stepsizes are not related by powers of two.
In W. Jiang and A. Ortega, “Multiple description coding via polyphase transform and selective quantization,” SPIE Conf. on Visual Communications and Image Processing, Janaury 1999, F is the concatenation of two identical K�K transforms, F1 and F2. The coefficients in F2 are quantized to lower resolution than the coefficients in F1. Reconstruction is performed simply by replacing the coefficients missing from F1 with the corresponding low-resolution coefficients from F2.
In A. C. Miguel, A. E. Mohr, and E. A. Riskin, “SPIHT for generalized multiple description coding,” submitted to IEEE Int'l Conf. on Image Processing, Kobe, Japan, 1999, F is the concatenation of four identical K�K transforms, F1, . . . , F4. The coefficients in F1 are quantized to full precision (10 bit planes). The coefficients in F2, F3, and F4, are quantized to 7, 5, and 4 bit planes, respectively, and grouped so that corresponding coefficients do not share the same binary description. Reconstruction is performed simply by replacing the coefficients missing from F1 with the corresponding low resolution coefficients from F2, F3, or F4.
Conclusion—Reconstruction of Missing Coefficients
One aspect of the present invention provides a computerized method of reconstructing a set of data x having K dimensions. The method includes receiving (220) a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>K and the set of data y′ has≦N dimensions; and iteratively transforming (890) the received set of data y′ using projections onto convex sets as calculated with a computer to produce a set of data x′ representing the reconstructed set of data x.
In one embodiment, the method further includes providing (201) an initial set of data x having K dimensions, overcompletely transforming (812) the set of data x to a set of data y having N dimensions, where N>K; and transmitting (222) the set of data y on a channel.
In yet another embodiment of the method, the iteratively transforming calculation further includes:
transforming a set of data y1 to a set of data y2 using F2F1 −1,
setting components of the resulting set of data y2 corresponding to received components to those received components y2′,
transforming the resulting set of data y2 to a set of data y1 using F1F2 −1,
setting components of the resulting set of data y1 corresponding to received components to those received components y1′, and
transforming the resulting set of data y1 to a set of data x′ using F1 −1,
wherein F1 and F2 are each K�K transforms.
In still another embodiment of the method (this embodiment involving two functions F1 and F2), the iteratively transforming calculation further comprises:
(a) initializing a t=0;
(b) setting an initial point p1(0) such that for each index i,
p1,i(0)=ŷ1,i if i∈R1 and
p1,i(0)=0 if i∉R1;
(c) transforming p1(t) into the coordinate system of F2 using
p2(t)=F2(F1 −1p1(t))=F12p1(t);
(d) projecting p2(t) onto F2Q such that for each index i,
q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i∈R2 and
q2,i(t+1)=p2,i(t) if i∉R2;
(e) transforming q2(t+1) into the coordinate system of F1 using
q1(t+1)=F1(F2 −1q2(t+1))=F21q2(t+1);
(f) projecting q1(t+1) onto F1P such that for each index i,
p1,i(t+1)=min{max{q1,i(t+1),l1,i},u1,i} if i∈R1 and
p1,i(t+1)=p2,i(t) if i∉R1; and
(g) reconstructing a set of data {circumflex over (x)}=F1 −1p1(t);
wherein: F1 and F2 are each K�K transforms, F1 −1 is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2. In one such embodiment, the iteratively transforming calculation further includes (f1) checking for convergence by testing ∥p1(t+1)−p1(t)∥2>ε, and if so then setting t←t+1 and iterating (c) through (f). In one embodiment, F1 is a wavelet transform and F2 is a discrete cosine transform.
In still another embodiment of the method (this embodiment involving M functions F1 through FM), the iteratively transforming calculation further comprises:
(b) setting p1,i(0)=ŷ1,i if i∈R1 (i.e., received descriptions) and
(c) for each m=1, . . . , M−1 in turn:
(i) transforming pm(t) into the coordinate system of Fm+1:
{tilde over (p)}m+1(t)=Fm+1Fm −1Pm(t)=Fm,m+1pm(t); and
(ii) projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1:
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 (d) transforming pM(t) into the coordinate system of F1:
(e) projecting {tilde over (p)}1(t+1) onto F1P1:
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i},u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 (f) checking for convergence, and if ∥pn(t+1)−pn(t)∥2>epsilon for an n between 1 and M inclusive,
then setting t←t+1 and repeating (c) through (f), otherwise performing (g); and
(g) reconstructing x:
{circumflex over (x)}=Fn −1pn(t+1);
wherein: F1 through FM are each K�K transforms, M is an integer larger than 1, each Fm −1 is the inverse transform of Fm, ŷ1 is a quantized version of y1, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and each ŷm componentwise lies between respective lower and upper quantization cell boundary vectors lm≦ŷm≦um, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and for each m, Rm⊂{1, . . . , K} is the set of indices of the descriptions received of ŷm.
Another aspect of the present invention is a computer readable medium having computer executable instructions stored thereon for performing a method of reconstructing a set of data x having K dimensions. The method includes receiving a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>K, and iteratively transforming the received set of data y′ using projections onto convex sets as calculated with a computer to produce a set of data x′ representing the reconstructed set of data x. In various embodiments, this computer medium includes instructions to implement the various features of the previously described method.
Yet another aspect of the present invention provides a data-reconstruction system that includes means for receiving a set of data y′, wherein the set of data y′ corresponds to a set of data y but with some coefficients missing, wherein the set of data y has N dimensions and represents an overcomplete transformation of the set of data x, and wherein N>K; and means, operatively coupled to the means for receiving, for iteratively transforming the received set of data y′ using projections onto convex sets to produce a set of data x′ representing the reconstructed set of data x.
In one embodiment of the system, the means for the iteratively transforming calculation further comprises:
(a) means for initializing a t=0;
(b) means for setting an initial point p1(0) such that for each index i,
(c) means for transforming p1(t) into the coordinate system of F2 using
(d) means for projecting p2(t) onto F2Q such that for each index i,
q2,i(t+1)=min{max{p2,i(t),l2,i},u2,i} if i ∈R2 and
(e) means for transforming q2(t+1) into the coordinate system of F1 using
(f) means for projecting q1(t+1) onto F1P such that for each index i,
(g) means for reconstructing a set of data {circumflex over (x)}=F1 −1p1(t);
wherein: F1 and F2 are each K�K transforms, F1 31 1 is the inverse transform of F1, F2 −1 is the inverse transform of F2, ŷ1 is a quantized version of y1, ŷ2 is a quantized version of y2, such that ŷ1 componentwise lies between respective lower and upper quantization cell boundary vectors l1≦ŷ1≦u1 and ŷ2 componentwise lies between respective lower and upper quantization cell boundary vectors l2≦ŷ2≦u2, R1⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ1, and R2⊂{1, . . . , K} is the set of indices of the descriptions received of ŷ2.
In another embodiment of the system, the means for iteratively transforming further includes (f1) means for checking for convergence including means for testing ∥p1(t+1)−p1(t)∥2>ε, and means for setting t←t+1 and iterating means (c) through (f) if so.
In still another embodiment of the system, the means for iteratively transforming includes:
(b) means for setting
(i) means for transforming pm(t) into the coordinate system of Fm+1:
(ii) means for projecting {tilde over (p)}m+1(t) onto Fm+1Pm+1:
pm+1,i(t)=min{max{{tilde over (p)}m+1,i(t), lm+1,i}um+1,i} if i∈R2 pm+1,i(t)={tilde over (p)}m+1,i(t) if i∉R2 (d) means for transforming pM(t) into the coordinate system of F1:
(e) means for projecting {tilde over (p)}1(t+1) onto F1P1:
p1,i(t+1)=min{max{{tilde over (p)}1,i(t+1), l1,i}, u1,i} if i∈R1 p1,i(t+1)={tilde over (p)}1,i(t+1) if i∉R1 (g) means for checking for convergence, and if ∥pn(t+1)−pn(t)∥2>epsilon for an n between 1 and M inclusive, then means for setting t←t+1 and repeating (c) through (f), otherwise means for going to (g); and
(g) means for reconstructing x:
{tilde over (x)}=Fn −1pn(t+1);
Still another aspect of the present invention provides a computerized method of reconstructing data after a transmission on an erasure channel. This method includes providing an initial set of data x having K dimensions, overcompletely transforming the set of data x to a set of data y having N dimensions, where N>K, 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. Various embodiments of this method include one or more features of the methods described above.
Thus, the present invention provides a computationally efficient and workable reconstruction of data sets having missing coefficients from overcomplete expansions. Examples of large data sets for which the present invention is suitable include images and/or sound sent over erasure channels such as packet networks, or stored on optical disks. One contribution of the present invention is the proper setup within the multiple description problem so that it becomes computationally feasible for solving the problems of interest.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6012159 *Jan 17, 1997Jan 4, 2000Kencast, Inc.Method and system for error-free data transfer* Cited by examinerNon-Patent CitationsReference1Goyal, V.K., et al., "Multiple Description Transform Coding of Images", Proceedings of the IEEE International Conference on Image Processing, Chicago, Illinios, 674-678 (Oct. 1998).2Goyal, V.K., et al., "Multiple Description Transform Coding: Robustness to Erasures Using Tight Frame Expansions", Proceedings of the IEEE International Symposium on Information Theory, Cambridge, MA, 408, (Aug. 1998).3Goyal, V.K., et al., "Quantized Overcomplete Expansion in IRN: Analysis, Synthesis, and Algorithms", IEEE TRans. Information Theory44(1), 16-31, (Jan. 1998).4 *Hein et al., "Reconstruction of Oversampled Band-Limited Signals From Sigma-Delta Encoded Binary Sequences", IEEE Transactions on Signal Processing, vol. 42, No. 4, Apr. 1994, pp. 799-811.*5 *Hemami, "Reconstruction-Optimized Lapped Orthogonal Transforms for Robust Image Transmission", IEEE Transactions on Systems for Video Technology, vol. 6, No. 2, Apr. 1996, pp. 168-181.*6Jiang, W., et al., "Multiple Description Coding Via Polyphase Transform and Selective Quantization", SPIE Conference on Visual Communications and Image Processing, 11 p. (Jan. 1999).7Miguel, A.C., et al., "SPIHT for Generalized Multiple Description Coding", Submitted to IEEE International Conference on Image Processing, Kobe, Japan, 11 p. (1999).8Youla, D.C., "Mathematical Theory of Image Restoration by the Method of Convex Projections", In: Image Recovery: Theory and Applications, Stark, H., (ed.), Academic Press, p. 29-77 (1987).* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6853318 *Dec 30, 2003Feb 8, 2005Eastman Kodak CompanyDigital image compression utilizing shrinkage of subband coefficientsUS6996097 *May 21, 1999Feb 7, 2006Microsoft CorporationReceiver-driven layered error correction multicast over heterogeneous packet networksUS7079696 *Dec 24, 2002Jul 18, 2006Canon Kabushiki KaishaImage encoding apparatus and method, image display apparatus and method, image processing system and image sensing apparatusUS7304990 *Feb 2, 2001Dec 4, 2007Bandwiz Inc.Method of encoding and transmitting data over a communication medium through division and segmentationUS7359980 *Jul 21, 2005Apr 15, 2008Microsoft CorporationProgressive streaming media renderingUS7366172 *Jul 8, 2005Apr 29, 2008Microsoft CorporationReceiver-driven layered error correction multicast over heterogeneous packet networksUS7383346 *Jul 21, 2005Jun 3, 2008Microsoft CorporationProgressive streaming media renderingUS7424493Feb 11, 2005Sep 9, 2008Microsoft CorporationReplication-based propagation mechanism for pipelinesUS7580461Aug 4, 2004Aug 25, 2009Microsoft CorporationBarbell lifting for wavelet codingUS7627037Aug 4, 2004Dec 1, 2009Microsoft CorporationBarbell lifting for multi-layer wavelet codingUS7697514 *Apr 13, 2010Microsoft CorporationReceiver-driven layered error correction multicast over heterogeneous packet networksUS7930145 *Apr 19, 2011Hewlett-Packard Development Company, L.P.Processing an input signal using a correction function based on training pairsUS8243812Aug 14, 2012Microsoft CorporationBarbell lifting for wavelet codingUS8290297 *Oct 16, 2012Mitsubishi Electric Research Laboratories, Inc.Method for editing images and videosUS8290298 *Oct 16, 2012Mitsubishi Electric Research Laboratories, Inc.Method for temporally editing videosUS8316282 *Nov 20, 2012Koninklijke Philips Electronics N.V.Coding of data streamUS20030002533 *Feb 2, 2001Jan 2, 2003Doron RajwanCoding methodUS20030099404 *Dec 24, 2002May 29, 2003Yuji KoideImage encoding apparatus and method, image display apparatus and method, image processing system and image sensing apparatusUS20050149581 *Feb 11, 2005Jul 7, 2005Microsoft CorporationReplication-based propagation mechanism for pipelinesUS20050190978 *Aug 4, 2004Sep 1, 2005Microsoft CorporationBarbell lifting for wavelet codingUS20050190979 *Aug 4, 2004Sep 1, 2005Microsoft CorporationBarbell lifting for multi-layer wavelet codingUS20050204242 *Apr 18, 2005Sep 15, 2005Microsoft CorporationReceiver-driven layered error correction multicast over heterogeneous packet networksUS20050249211 *Jul 8, 2005Nov 10, 2005Microsoft CorporationReceiver-driven layered error correction multicast over heterogeneous packet networksUS20060015633 *Jul 21, 2005Jan 19, 2006Microsoft CorporationProgressive streaming media renderingUS20060015634 *Jul 21, 2005Jan 19, 2006Microsoft CorporationProgressive streaming media renderingUS20070187344 *Feb 16, 2006Aug 16, 2007Fasteners For Retail, Inc.Merchandising systemUS20080103717 *Oct 30, 2006May 1, 2008Yacov Hel-OrProcessing an input signal using a correction function based on training pairsUS20100183242 *Jan 20, 2009Jul 22, 2010Matthew BrandMethod for Editing Images and VideosUS20100183243 *Mar 30, 2009Jul 22, 2010Brand Matthew EMethod for Temporally Editing VideosUS20100211848 *Apr 15, 2009Aug 19, 2010Maria Giuseppina MartiniCoding of data stream* Cited by examinerClassifications U.S. Classification714/746, 714/776International ClassificationH03M13/03, H03M13/35, H03M13/17, G06T11/00Cooperative ClassificationG06T2207/20052, G06T5/10, G06T2207/20056, G06T5/005, H03M13/03, H03M13/35, H03M13/17European ClassificationG06T5/10, G06T5/00D5, H03M13/35, H03M13/17, H03M13/03Legal EventsDateCodeEventDescriptionJun 18, 1999ASAssignmentOwner name: MICROSOFT CORPORATION, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:CHOU, PHILIP A.;MEHROTRA, SANJEEV;WANG, ALBERT S.;REEL/FRAME:010031/0551Effective date: 19990603Jul 22, 2003CCCertificate of correctionMar 31, 2006FPAYFee paymentYear of fee payment: 4Apr 14, 2010FPAYFee paymentYear of fee payment: 8May 30, 2014REMIMaintenance fee reminder mailedOct 22, 2014LAPSLapse for failure to pay maintenance feesDec 9, 2014FPExpired due to failure to pay maintenance feeEffective date: 20141022Dec 9, 2014ASAssignmentOwner name: MICROSOFT TECHNOLOGY LICENSING, LLC, WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:MICROSOFT CORPORATION;REEL/FRAME:034541/0001Effective date: 20141014RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services