Rock Brentwood
unread,Jan 24, 2012, 6:20:01 PM1/24/12You do not have permission to delete messages in this group
Either email addresses are anonymous for this group or you need the view member email addresses permission to view the original message
to
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.