Lossless & Non-Degrading Lossing DCT-Based Coding

[Rock Brentwood]

This may be old news, or it may be something entirely novel; in either
case, I've not seen any literature reference on the following.

In the (relatively) new JPEG 2000 standard, you have both a lossing
and lossless variety based on different forms of the wavelet
transform; the lossless version making special use of certain magic
number properties. This leads, naturally, to the question of whether
the something similar can be accomplished with the Discrete Cosine
Transform (DCT); and whether there are magic numbers that work there
too.

A lossless approximation to 1-dimensional DCT-baaed coding should be
achievable by using this transformation matrix for the forward
transform:

17 17 17 17 17 17 17 17
24 20 12 6 -6 -12 -20 -24
23 7 -7 -23 -23 -7 7 23
20 -6 -24 -12 12 24 6 -20
17 -17 -17 17 17 -17 -17 17
12 -24 6 20 -20 -6 24 -12
7 -23 23 -7 -7 23 -23 7
6 -12 20 -24 24 -20 12 -6

and its transpose

17 24 23 20 17 12 7 6
17 20 7 -6 -17 -24 -23 -12
17 12 -7 -24 -17 6 23 20
17 6 -23 -12 17 20 -7 -24
17 -6 -23 12 17 -20 -7 24
17 -12 -7 24 -17 -6 23 -20
17 -20 7 6 -17 24 -23 12
17 -24 23 -20 17 -12 7 -6

for the inverse transform, in place of the forward and inverse DCT.
This should also be sufficient to ALSO provide the basis for a *non-
degrading* lossing transform; i.e., a transform where
Dequantization -> Inverse Transform -> Forward Transform ->
Quantization
yields the identity operator.

Both transforms are amenable to factoring. For instance, the forward
transform:
A0 = 17 a0 + 17 a1 + 17 a2 + 17 a3 + 17 a4 + 17 a5 + 17 a6 + 17 a7
A1 = 24 a0 + 20 a1 + 12 a2 + 6 a3 - 6 a4 - 12 a5 - 20 a6 - 24 a7
A2 = 23 a0 + 7 a1 - 7 a2 - 23 a3 - 23 a4 - 7 a5 + 7 a6 + 23 a7
A3 = 20 a0 - 6 a1 - 24 a2 - 12 a3 + 12 a4 + 24 a5 + 6 a6 - 20 a7
A4 = 17 a0 - 17 a1 - 17 a2 + 17 a3 + 17 a4 - 17 a5 - 17 a6 + 17 a7
A5 = 12 a0 - 24 a1 + 6 a2 + 20 a3 - 20 a4 - 6 a5 + 24 a6 - 12 a7
A6 = 7 a0 - 23 a1 + 23 a2 - 7 a3 - 7 a4 + 23 a5 - 23 a6 + 7 a7
A7 = 6 a0 - 12 a1 + 20 a2 - 24 a3 + 24 a4 - 20 a5 + 12 a6 - 6 a7
can be rewritten as
A0 = 17 (s0734 + s1625), A4 = 17 (s0734 - s1625)
A2 = 23 d0734 + 7 d1625, A6 = 7 d0734 - 23 d1625
A1 = 6 (4 d07 + d34) + 4 (5 d16 + 3 d25)
A3 = 4 (5 d07 - 3 d34) - 6 (d16 + 4 d25)
A5 = 4 (3 d07 + 5 d34) - 6 (4 d16 - d25)
A7 = 6 (d07 - 4 d34) - 4 (3 d16 - 5 d25)
where
s07 = a0 + a7, s16 = a1 + a6, s25 = a2 + a5, s34 = a3 + a4,
d07 = a0 - a7, d16 = a1 - a6, d25 = a2 - a5, d34 = a3 - a4,
s0734 = s07 + s34, s1625 = s16 + s25,
d0734 = s07 - s34, d1625 = s16 - s25.
Other more efficients methods may be devised to better handle A1, A3,
A5 and A7.

The matrices are both orthogonal (up to an overall factor); their
product is 2312 times the identity matrix. Their orthogonality (up to
rescaling) is easily verified, since the requirement reduces to the
conditions:
4*17^2 = 2*(23^2 + 7^2) = 24^2 + 20^2 + 12^2 + 6^2 = 2312/2
24*20 = 24*12 + 12*6 + 6*20
which are all integer identities. The matrix approximates 24 times the
DCT matrix, or 48 times the normalized DCT matrix.

It is the ONLY relatively prime integer solution that lies entirely in
the range -100 to 100 whose coefficients have the same ordering
relation as those of the DCT matrix. The only other relatively prime
integer solutions in the range -500 to 500 satisfying the ordering
property are the solutions with the following two sets of coefficients
(116, 113, 96, 85, 78, 41, 12, -12, -41, -78, -85, -96, -113, -116)
(120, 113, 100, 85, 60, 41, 30, -30, -41, -60, -85, -100, -113, -120)
in place of
(24, 23, 20, 17, 12, 7, 6, -6, -7, -12, -17, -20, -23, -24)
both solutions having divisors apprxomately equal to 240 + 5/12
relative to the normalized DCT matrix.

There are only 5 other relatively prime solutions in the range -1000
to 1000 satisfying the ordering property. They are the ones whose
coefficients are drawn from the respective sets:
(618, 575, 428, 425, 396, 175, 24, -24, -175, -396, -425, -428, -575,
-618)
(660, 607, 606, 493, 384, 343, 148, -148, -343, -384, -493, -606,
-607, -660)
(696, 607, 580, 493, 348, 343, 174, -174, -343, -348, -493, -580,
-607, -696)
(816, 623, 600, 577, 552, 527, 34, -34, -527, -552, -577, -600, -623,
-816)
(912, 721, 660, 629, 556, 521, 78, -78, -521, -556, -629, -660, -721,
-912)
Their divisors are approximately 1202, 1394 + 5/12, 1394 + 5/12, 1632
and 1779 relative to the normalized DCT matrix.

Denoting the DCT coefficients in order by
1 > A > B > C > D > E > F > G > 0 > g > f > e > d > c > b > a > -1
the DCT matrix can be written compactly in the form
D D D D D D D D
A C E G g e c a
B F f b b f F B
C g a e E A G c
D d d D D d d D
E g A C c a G e
F b f B B f b F
G e C a A c E g
with the relations
(a, b, c, d, e, f, g) = (-A, -B, -C, -D, -E, -F, -G)
4 D^2 = 2 (B^2 + F^2) = A^2 + C^2 + E^2 + G^2 = 1/2
AC = AE + EG + GC
The normalized DCT matrix is 1/2 this matrix.

Let T, T' denote the integer matrix and its transpose; and let t, t'
denote the DCT matrix and its transpose. Then one has the properties:
T T' = 8 D^2 I = T' T.
t t' = 4 I = t' t.
T ~ 24 t and T' ~ 24 t' for the first integer solution listed.
The normalized DCT matrix is t/2 and its inverse is t'/2.

For the 2-dimensional DCT, the transformation matrix is the tensor
product
t (x) t
(using (x) to denote the tensor product symbol). For the integer
transform, one can replace this by any of the following tensor
products:
T (x) T, T' (x) T'
or
T (x) T', T' (x) T.

The latter two give a closer approximation to t (x) t, but lose the
vertical <-> horizontal symmetry.

[glen herrmannsfeldt]

Rock Brentwood <federat...@netzero.com> wrote:
> This may be old news, or it may be something entirely novel; in either
> case, I've not seen any literature reference on the following.

(snip on JPEG2000)

> A lossless approximation to 1-dimensional DCT-baaed coding should be
> achievable by using this transformation matrix for the forward
> transform:

> 17 17 17 17 17 17 17 17
> 24 20 12 6 -6 -12 -20 -24
> 23 7 -7 -23 -23 -7 7 23
> 20 -6 -24 -12 12 24 6 -20
> 17 -17 -17 17 17 -17 -17 17
> 12 -24 6 20 -20 -6 24 -12
> 7 -23 23 -7 -7 23 -23 7
> 6 -12 20 -24 24 -20 12 -6

> and its transpose

(snip)

> The matrices are both orthogonal (up to an overall factor); their
> product is 2312 times the identity matrix.

I haven't followed JPEG, or DCT based compression, in all that
much detail, but I always thought that the matrix with small integer
coefficients would not have an inverse, appropriately scaled, with
small integer coefficients. That is, that some rounding was done.

> It is the ONLY relatively prime integer solution that lies entirely in
> the range -100 to 100 whose coefficients have the same ordering
> relation as those of the DCT matrix.

Some years ago, I went to a talk about the ICT, Integer Cosine
Transform, I believe before I knew about JPEG. The ICT is designed
for the case where encoding is done on a processor without hardware
multiply, without a lot of memory available, and with a limited time
available. Also, when the decoding can be done on a fast processor,
with hardware multiply and divide, and when time is not limited.
(Specifically, for the CDP1802 processor.)

I presume it could be used the other way around, when a slow processor
is available for decoding, and a fast processor for encoding.

-- glen