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
24 import math
, random
, unittest
25 import fastdct8
, fastdctfft
, fastdctlee
, naivedct
28 class FastDctTest(unittest
.TestCase
):
30 def test_fast_dct_lee_vs_naive(self
):
31 for i
in range(1, 12):
33 vector
= FastDctTest
.random_vector(n
)
34 expect
= naivedct
.transform(vector
)
35 actual
= fastdctlee
.transform(vector
)
36 self
.assertListAlmostEqual(actual
, expect
)
37 expect
= naivedct
.inverse_transform(vector
)
38 actual
= fastdctlee
.inverse_transform(vector
)
39 self
.assertListAlmostEqual(actual
, expect
)
42 def test_fast_dct_lee_invertibility(self
):
43 for i
in range(1, 18):
45 vector
= FastDctTest
.random_vector(n
)
46 temp
= fastdctlee
.transform(vector
)
47 temp
= fastdctlee
.inverse_transform(temp
)
48 temp
= [(val
* 2.0 / n
) for val
in temp
]
49 self
.assertListAlmostEqual(vector
, temp
)
52 def test_fast_dct8_vs_naive(self
):
53 vector
= FastDctTest
.random_vector(8)
55 expect
= naivedct
.transform(vector
)
56 expect
= [(val
/ (math
.sqrt(8) if (i
== 0) else 2))
57 for (i
, val
) in enumerate(expect
)]
58 actual
= fastdct8
.transform(vector
)
59 self
.assertListAlmostEqual(actual
, expect
)
61 expect
= [(val
/ (math
.sqrt(2) if (i
== 0) else 2))
62 for (i
, val
) in enumerate(vector
)]
63 expect
= naivedct
.inverse_transform(expect
)
64 actual
= fastdct8
.inverse_transform(vector
)
65 self
.assertListAlmostEqual(actual
, expect
)
68 def test_fast_dct_fft_vs_naive(self
):
70 for i
in range(100 + 1):
71 n
= int(round(1000**(i
/ 100)))
75 vector
= FastDctTest
.random_vector(n
)
77 expect
= naivedct
.transform(vector
)
78 actual
= fastdctfft
.transform(vector
)
79 self
.assertListAlmostEqual(actual
, expect
)
81 expect
= naivedct
.inverse_transform(vector
)
82 actual
= fastdctfft
.inverse_transform(vector
)
83 self
.assertListAlmostEqual(actual
, expect
)
86 def test_fast_dct_fft_invertibility(self
):
88 for i
in range(30 + 1):
89 n
= int(round(10000**(i
/ 30)))
93 vector
= FastDctTest
.random_vector(n
)
94 temp
= fastdctfft
.transform(vector
)
95 temp
= fastdctfft
.inverse_transform(temp
)
96 temp
= [(val
* 2.0 / n
) for val
in temp
]
97 self
.assertListAlmostEqual(vector
, temp
)
100 def assertListAlmostEqual(self
, actual
, expect
):
101 self
.assertEqual(len(actual
), len(expect
))
102 for (x
, y
) in zip(actual
, expect
):
103 self
.assertAlmostEqual(x
, y
, delta
=FastDctTest
._EPSILON
)
107 def random_vector(n
):
108 return [random
.uniform(-1.0, 1.0) for _
in range(n
)]
114 if __name__
== "__main__":