2 # Fast discrete cosine transform algorithms (Python)
4 # Copyright (c) 2020 Project Nayuki. (MIT License)
5 # https://www.nayuki.io/page/fast-discrete-cosine-transform-algorithms
7 # Permission is hereby granted, free of charge, to any person obtaining a copy of
8 # this software and associated documentation files (the "Software"), to deal in
9 # the Software without restriction, including without limitation the rights to
10 # use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
11 # the Software, and to permit persons to whom the Software is furnished to do so,
12 # subject to the following conditions:
13 # - The above copyright notice and this permission notice shall be included in
14 # all copies or substantial portions of the Software.
15 # - The Software is provided "as is", without warranty of any kind, express or
16 # implied, including but not limited to the warranties of merchantability,
17 # fitness for a particular purpose and noninfringement. In no event shall the
18 # authors or copyright holders be liable for any claim, damages or other
19 # liability, whether in an action of contract, tort or otherwise, arising from,
20 # out of or in connection with the Software or the use or other dealings in the
27 # DCT type II, unscaled. Algorithm by Byeong Gi Lee, 1984.
28 # See: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.3056&rep=rep1&type=pdf#page=34
29 def transform(vector
):
33 elif n
== 0 or n
% 2 != 0:
37 alpha
= [(vector
[i
] + vector
[-(i
+ 1)]) for i
in range(half
)]
38 beta
= [(vector
[i
] - vector
[-(i
+ 1)]) /
39 (math
.cos((i
+ 0.5) * math
.pi
/ n
) * 2.0)
41 alpha
= transform(alpha
)
42 beta
= transform(beta
)
44 for i
in range(half
- 1):
45 result
.append(alpha
[i
])
46 result
.append(beta
[i
] + beta
[i
+ 1])
47 result
.append(alpha
[-1])
48 result
.append(beta
[-1])
52 # DCT type III, unscaled. Algorithm by Byeong Gi Lee, 1984.
53 # See: https://www.nayuki.io/res/fast-discrete-cosine-transform-algorithms/lee-new-algo-discrete-cosine-transform.pdf
54 def inverse_transform(vector
, root
=True, indent
=0):
62 elif n
== 0 or n
% 2 != 0:
68 for i
in range(2, n
, 2):
69 alpha
.append(vector
[i
])
70 beta
.append(vector
[i
- 1] + vector
[i
+ 1])
71 print (idt
, "n", n
, "alpha 0", end
=" ")
72 for i
in range(2, n
, 2):
74 print ("beta 1", end
=" ")
75 for i
in range(2, n
, 2):
76 print ("%d+%d" % (i
-1, i
+1), end
=" ")
78 inverse_transform(alpha
, False, indent
+1)
79 inverse_transform(beta
, False, indent
+1)
82 y
= beta
[i
] / (math
.cos((i
+ 0.5) * math
.pi
/ n
) * 2)
84 vector
[-(i
+ 1)] = x
- y
85 print (idt
, " v[%d] = alpha[%d]+beta[%d]" % (i
, i
, i
))
86 print (idt
, " v[%d] = alpha[%d]-beta[%d]" % (n
-i
-1, i
, i
))
90 def inverse_transform2(vector
, root
=True):
96 elif n
== 0 or n
% 2 != 0:
102 for i
in range(2, n
, 2):
104 beta
.append(("add", i
- 1, i
+ 1))
105 inverse_transform2(alpha
, False)
106 inverse_transform2(beta
, False)
107 for i
in range(half
):
109 y
= ("cos", beta
[i
], i
)
110 vector
[i
] = ("add", x
, y
)
111 vector
[-(i
+ 1)] = ("sub", x
, y
)
115 if __name__
== '__main__':
117 ops
= inverse_transform(vector
)