-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathdct.py
137 lines (115 loc) · 4.34 KB
/
dct.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
https://en.wikipedia.org/wiki/Discrete_cosine_transform
"""
import math
import unittest
import random
def get_dct(input_values):
"""
Apply DCT on list of numbers input_values,
return list with same number of elements
"""
matrix_size = len(input_values)
result = [0.0] * matrix_size
if matrix_size > 0:
for outer_index in range(matrix_size):
for index in range(matrix_size):
result[outer_index] += (input_values[index]
* math.cos(math.pi / matrix_size
* outer_index * (index + 0.5)))
result[0] *= 1.0 / math.sqrt(2.0)
for index in range(matrix_size):
result[index] *= math.sqrt(2.0 / matrix_size)
return result
def get_idct(input_values):
"""Inverse DCT on list of numbers input_values"""
matrix_size = len(input_values)
result = [0.0] * matrix_size
for outer_index in range(matrix_size):
result[outer_index] = input_values[0] / math.sqrt(2.0)
for index in range(1, matrix_size):
result[outer_index] += (input_values[index]
* math.cos(math.pi / matrix_size
* index * (outer_index + 0.5)))
for index in range(matrix_size):
result[index] *= math.sqrt(2.0 / matrix_size)
return result
def get_2d_dct(input_matrix):
"""Apply DCT on 2D matrix (nested list) of numbers input_matrix, return same size matrix"""
matrix_size = len(input_matrix)
def c_factor(i):
if i == 0:
return 1.0 / math.sqrt(2.0)
return 1.0
def cos_term(inner, outer):
return math.cos(math.pi * outer * (2.0 * inner + 1.0) / (2.0 * matrix_size))
if matrix_size > 0:
result = []
for i in range(matrix_size):
result.append([0.0] * matrix_size)
for i in range(matrix_size):
for j in range(matrix_size):
for x in range(matrix_size):
for y in range(matrix_size):
result[i][j] += input_matrix[x][y] * cos_term(x, i) * cos_term(y, j)
result[i][j] *= c_factor(i) * c_factor(j) * 2.0 / matrix_size
return result
def get_2d_idct(input_matrix):
"""
Apply Inverse DCT on 2D matrix (nested list) of
numbers input_matrix, return same size matrix
"""
matrix_size = len(input_matrix)
def c_factor(i):
if i == 0:
return 1.0 / math.sqrt(2.0)
return 1.0
def cos_term(inner, outer):
return math.cos(math.pi * inner * (2.0 * outer + 1.0) / (2.0 * matrix_size))
if matrix_size > 0:
result = []
for i in range(matrix_size):
result.append([0.0] * matrix_size)
for i in range(matrix_size):
for j in range(matrix_size):
for x in range(matrix_size):
for y in range(matrix_size):
result[i][j] += (c_factor(x) * c_factor(y) * input_matrix[x][y]
* cos_term(x, i) * cos_term(y, j))
result[i][j] *= 2.0 / matrix_size
return result
class TestDCT(unittest.TestCase):
"""
Test class for DCT functions
"""
def test_1d(self):
"""
1-dimensional DCT tests
"""
random.seed()
for _iteration in range(10):
for list_len in range(100):
x = list(map(lambda x: random.uniform(-10000, 10000), [0.0] * list_len))
dct_x = get_dct(x)
idct_x = get_idct(dct_x)
for i in range(list_len):
self.assertAlmostEqual(x[i], idct_x[i])
def test_2d(self):
"""
2-dimensional DCT tests
"""
random.seed()
for _iteration in range(10):
for list_len in range(2, 16):
x = []
for i in range(list_len):
x.append(list(map(lambda x: random.uniform(-10000, 10000), [0.0] * list_len)))
dct_x = get_2d_dct(x)
idct_x = get_2d_idct(dct_x)
for i in range(list_len):
for j in range(list_len):
self.assertAlmostEqual(x[i][j], idct_x[i][j])
if __name__ == '__main__':
unittest.main()