Television transmission system using transform coding

• US 4,831,440 A
• Filed: 03/24/1988
• Issued: 05/16/1989
• Est. Priority Date: 04/10/1987
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Habraken, Egidius A. P. Woudsma, Borgers, Stephanus M. C.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US07/172,603
• Time in Patent Office: 418 Days
• Field of Search: 358/133, 358/138, 358/13, 364/725
• US Class Current: 375/240.2
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

A television transmission system for digital picture signals in which each picture is split up into sub-pictures of NxN pixels for the purpose of reducing the bit rate. Each sub-picture is subjected to a two-dimensional discrete cosine transform (DCT) for determining basic picture weighting factors (coefficients) which are converted by adaptive coding into code words of variable length. This two-dimensional DCT is realized by multiplying the pixels of each row of the sub-picture by the NxN DCT matrix (one-dimensional transform). Consequently, an NxN array of product elements is obtained. The transposed version thereof is once more multiplied by the NxN DCT matrix. Such a one-dimensional transform includes three main steps. In a first main step, the pixels of a row are converted in a first iteration step, into N/2 sum elements u₁,i and N/2 difference elements v₁,i. In a subsequent iteration step, the N/2 sum elements u₁,i are converted into N/4 further sum elements u₂,i and N/4 further difference elements v₂,i. This process is repeated until only two sum elements are left. The difference elements obtained in each step are used to determine a plurality of auxiliary sum elements in still further iteration steps. The remaining two sum elements, the difference elements and the auxiliary sum elements are each multiplied in the second main step by an associated linear combination of elements of the DCT matrix. Of the sub-products thus obtained, selected one'"'"'s of those products are added together or are subtracted from each other in the third main step so that the desired product elements are obtained.

Claims

1. A television transmission system for the transmission of a picture represented by a digital picture signal from an encoding station to a decoding station, the encoding station having means for partitioning the picture into sub-pictures each of N×

N pixels, and having a picture transform circuit adapted to perform a two-dimensional forward discrete cosine transform on each of the sub-pictures for generating an array of N×

N basis picture weighting factors, said picture transform circuit being constituted by a cascade arrangement of two one-dimensional forward discrete cosine transformers each adapted to perform a forward transform in which an array of 1×

N data elements d_o to d_N-1 applied to the transformer is transformed into an array of 1×

N product elements p_o to p_N-1, characterized in that the forward transform comprises the following steps;

(a) the iterative determination of two sum elements and N-2 difference, elements by performing Q iteration steps, starting from the N data elements d_o to d_N-1, in which in the q-th iteration step, the q-th order sum elements u_q,r and the q-th order difference elements v_q,r are obtained for which it holds that;

space="preserve" listing-type="equation">u.sub.q,r =u.sub.q-1,2 -q+1.sub.N-r-1

space="preserve" listing-type="equation">v.sub.q,r =u.sub.q-1,r -u.sub.q-1,2 -q+1.sub.N-r-1

r=0, 1, 2, . . . 2^-q N-1

q=1, 2, 3, . . . Q

u_o,r =dr

u_o,N-r =d_N-r

Q is the largest integer which is smaller than or equal to -1+² logN;

(b) the iterative determination of a number of auxiliary sum elements by performing a number of further iteration steps on the difference elements obtained in the q-th iteration step in accordance with step a), while in the j-th further iteration step, the j-th order auxiliary sum elements w_q,j,m are obtained for which it holds that;

space="preserve" listing-type="equation">w.sub.q,j,m =w.sub.q,j-1,m +w.sub.q,j-1,2 -q-j+1.sub.N-1-m

m=0, 1, 2, . . . 2^-q-j N-1

j=1, 2, . . . ² log(2^-q N)

w_q,o,m =v_q,m

w_q,o,2 -q_N-1-m =v_q,2 -q_N-1-m

(c) generating sub-product elements by multiplication of each of the two sum elements u_Q,o and u_Q,1 obtained in step (a), as well as the difference elements v_q,r and the auxiliary sum elements w_q,j,m with the associated multiplication factors from a collection of multiplication factors, each multiplication factor being constituted by a linear combination of elements of the discrete cosine transform matrix; and

(d) generating the product elements of the array of 1×

N product elements P_o to P_N-1 by making linear combinations of said sub-product elements.

2. A television transmission system as claimed in claim 1, in which the decoding station is provided with an inverse picture transform circuit adapted to perform a two-dimensional inverse discrete cosine transform on a received array of N×

N basis picture weighting factors for generating a sub-picture of N×

N pixels of a transmitted picture, said inverse picture transform circuit being constituted by a cascade arrangement of two one-dimensional inverse discrete cosine transformers which are each adapted to perform an inverse transform in which an array of 1×

N product elements p_o to p_N- 1 applied to the transformer is converted into an array of 1×

N data elements, characterized in that the inverse transform is the transposed version of the forward transform.

3. An encoding station for use in a television system as claimed in claim 1, which, for the purpose of transmission of a picture represented by a digital picture signal, is provided with means for partitioning said picture into sub-pictures of N×

N pixels each, and a picture transform circuit which is adapted to perform a two-dimensional forward discrete cosine transform on each sub-picture for generating an array of N×

N basis picture weighting factors, said picture transform circuit being constituted by a cascade arrangement of two one-dimensional forward discrete cosine transformers which are each adapted to perform a forward transform in which an array of 1×

N data elements d_o to d_N- 1 applied to the transformer is transformed into an array of 1×

N product elements p_o to p_N- 1, characterized in that the forward transform comprises the following steps;

(a) the iterative determination of two sum elements and N-2 difference elements by performing Q iteration steps, starting from the N data elements d_o to d_N- 1 in which in the q-th iteration step, the q-th order sum elements u_q,r and the q-th order difference elements v_q,r are obtained for which it holds that;

space="preserve" listing-type="equation">u.sub.q,r =u.sub.q-1,r +u.sub.q-1,2 -q+1.sub.N-r-1

space="preserve" listing-type="equation">v.sub.q,r =u.sub.q-1,r -u.sub.q-1,2 -q+1.sub.N-r-1

r=0, 1, 2, . . . 2^-q N-1

q=1, 2, 3, . . . Q

u_o,r =d_r

u_o,N-r =d_N-r

Q is the largest integer which is smaller than or equal to -1+² logN;

(b) the iterative determination of a number of auxiliary sum elements by performing a number of further iteration steps on the difference elements obtained in the q-th iteration step in accordance with step (a), while in the j-th further iteration step, the j-th order auxiliary sum elements w_q,j,m are obtained for which it holds that;

space="preserve" listing-type="equation">w.sub.q,j,m =w.sub.q,j-1,m +w.sub.q,j-1,2 -q-j+1.sub.N-1-m

m=0, 1, 2, . . . 2^-q-j N-1

j=1, 2, . . . ² log(2^-q N)

w_q,o,m =v_q,m

w_q,o,2 -q_N-1-m =v_q,2 -q_N-1-m

(c) generating sub-product elements by multiplication of each of the two sum elements u_Q,o and u_Q,1 obtained in step (a), as well as the difference elements v_q,r and the auxiliary sum elements w_q,j,m with associated multiplication factors from a collection of multiplication factors, each multiplication factor being constituted by a linear combination of elements of the discrete cosine transform matrix; and

(d) generating the product elements of the array of 1×

N product elements P_o to P_N-1 by making linear combinations of said sub-product elements.

4. A decoding station for use in a television system as claimed in claim 3, said decoding station being adapted to receive basis picture weighting factors which are transmitted by the encoding station, and being provided with an inverse picture transform circuit adapted to perform a two-dimensional inverse discrete cosine transform on a received array of N×

N basis picture weighting factors for generating a sub-picture of N×

N pixels of a transmitted picture, said inverse picture transform circuit being constituted by a cascade arrangement of two one-dimensional inverse discrete cosine transformers which are each adapted to perform an inverse transform in which an array of 1×

N product elements p_o to p_N-1 applied to the transformer is converted into an array of 1×

N data elements, characterized in that the inverse transform is the transposed version of the forward transform.