DCT-based technique with rhombus scanning for image compression
View Patent ↗A DCT-based technique with rhombus scanning for image compression. A flipped-kernel discrete cosine transform is applied to an eight by eight pixel sub-block of the sixteen by sixteen pixel block. A visually insignificant information is removed from the eight by eight pixel sub-block. A quantization method is used to remove the visually insignificant information. A quantized discrete cosine transform coefficient is scanned of the sixteen by sixteen pixel block. The quantized discrete cosine transform coefficient is scanned according to a rhomboid pattern. A portion of a digital image may be divided into a sixteen by sixteen pixel block.
1. A computer-implemented method of digital image compression comprising:
applying a flipped-kernel discrete cosine transform to an eight by eight pixel sub-block of a sixteen by sixteen pixel block;
removing a visually insignificant information from the eight by eight pixel sub-block with a quantization method; and
scanning a quantized discrete cosine transform coefficient of the sixteen by sixteen pixel block according to a rhomboid pattern.
2. The method of claim 1 , further comprising:
dividing a portion of a digital image into the sixteen by sixteen pixel block.
3. The method of claim 2 , wherein the digital image comprises at least one of a gray-scale image and a color-image.
4. The method of claim 1 , further comprising:
quantizing a spectral coefficient of the eight by eight pixel sub-block with an eight by eight pixel quantization table.
5. The method of claim 1 , wherein removing the visually insignificant information from the eight by eight pixel sub-block with the quantization method further comprises:
dividing an eight by eight pixel sub-block component in a frequency domain by a constant; and
rounding a result of the dividing of the eight by eight pixel sub-block component in the frequency domain by the constant to a nearest integer.
6. The method of claim 1 ,
wherein the sixteen by sixteen pixel block comprises a set of four eight by eight pixel blocks,
wherein the set of four eight by eight pixel blocks comprise: an eight by eight pixel block B 1 , an eight by eight pixel block B 2 , an eight by eight pixel block B 3 , and an eight by eight pixel block B 4 ,
wherein the eight by eight pixel block B 1 comprises a first eight by eight pixel sub-block of the sixteen by sixteen pixel block,
wherein the eight by eight pixel block B 2 comprises a second eight by eight pixel sub-block of the sixteen by sixteen pixel block,
wherein the eight by eight pixel block B 3 comprises a third eight by eight pixel sub-block of the sixteen by sixteen pixel block, and
wherein the eight by eight pixel block B 4 comprises a fourth eight by eight pixel sub-block of the sixteen by sixteen pixel block.
7. The method of claim 6 ,
wherein a general quantization matrix comprises a variable Q,
wherein Q comprises:
Q
=
[
q
00
q
01
q
02
q
03
q
04
q
05
q
06
q
07
q
10
q
11
q
12
q
13
q
14
q
15
q
16
q
17
q
20
q
21
q
22
q
23
q
24
q
25
q
26
q
27
q
30
q
31
q
32
q
33
q
34
q
35
q
36
q
37
q
40
q
41
q
42
q
43
q
44
q
45
q
46
q
47
q
50
q
51
q
52
q
53
q
54
q
55
q
56
q
57
q
60
q
61
q
62
q
63
q
64
q
65
q
66
q
67
q
70
q
71
q
72
q
73
q
74
q
75
q
76
q
77
]
wherein a specified quantization matrix of the eight by eight pixel block B 1 comprises:
Q
B
1
=
[
q
77
q
76
q
75
q
74
q
73
q
72
q
71
q
70
q
67
q
66
q
65
q
64
q
63
q
62
q
61
q
60
q
57
q
56
q
55
q
54
q
53
q
52
q
51
q
50
q
47
q
46
q
45
q
44
q
43
q
42
q
41
q
40
q
37
q
36
q
35
q
34
q
33
q
32
q
31
q
30
q
27
q
26
q
25
q
24
q
23
q
22
q
21
q
20
q
17
q
16
q
15
q
14
q
13
q
12
q
11
q
10
q
07
q
06
q
05
q
04
q
03
q
02
q
01
q
00
]
wherein a specified quantization matrix of the eight by eight pixel block B 2 comprises:
Q
B
2
=
[
q
70
q
71
q
72
q
73
q
74
q
75
q
76
q
77
q
60
q
61
q
62
q
63
q
64
q
65
q
66
q
67
q
50
q
51
q
52
q
53
q
54
q
55
q
56
q
57
q
40
q
41
q
42
q
43
q
44
q
45
q
46
q
47
q
30
q
31
q
32
q
33
q
34
q
35
q
36
q
37
q
20
q
21
q
22
q
23
q
24
q
25
q
26
q
27
q
10
q
11
q
12
q
13
q
14
q
15
q
16
q
17
q
00
q
01
q
02
q
03
q
04
q
05
q
06
q
07
]
wherein a specified quantization matrix of the eight by eight pixel block B 3 comprises:
Q
B
3
=
[
q
07
q
06
q
05
q
04
q
03
q
02
q
01
q
00
q
17
q
16
q
15
q
14
q
13
q
12
q
11
q
10
q
27
q
26
q
25
q
24
q
23
q
22
q
21
q
20
q
37
q
36
q
35
q
34
q
33
q
32
q
31
q
30
q
47
q
46
q
45
q
44
q
43
q
42
q
41
q
40
q
57
q
56
q
55
q
54
q
53
q
52
q
51
q
50
q
67
q
66
q
65
q
64
q
63
q
62
q
61
q
60
q
77
q
76
q
75
q
74
q
73
q
72
q
71
q
70
]
and
,
wherein a specified quantization matrix of the of the eight by eight pixel block B 4 comprises:
QB4=Q.
8. The method of claim 6 ,
wherein the flipped kernel discrete cosine transform applied to B 1 comprises:
for sub-block B 1 (N=8),
X
B
1
(
u
,
v
)
=
2
N
C
B
1
(
u
)
C
B
1
(
v
)
∑
i
=
0
N
-
1
∑
j
=
0
N
-
1
I
B
1
(
i
,
j
)
cos
[
(
2
i
+
1
)
[
N
-
(
u
+
1
)
]
π
2
N
]
cos
[
(
2
j
+
1
)
[
N
-
(
v
+
1
)
]
π
2
N
]
where C B 1 (u) and C B 1 (v) are given by,
C
B
1
(
u
)
,
C
B
1
(
v
)
=
1
2
,
u
=
N
-
1
,
v
=
N
-
1
C B 1 (u), C B 1 (v)=1, otherwise, and
where I B 1 (i, j) is the (i,j)th element of an image represented by the sub-block B 1 , wherein the flipped kernel discrete cosine transform applied to B 2 comprises:
for sub-block B 2 (N=8),
X
B
2
(
u
,
v
)
=
2
N
C
B
2
(
u
)
C
B
2
(
v
)
∑
i
=
0
N
-
1
∑
j
=
0
N
-
1
I
B
2
(
i
,
j
)
cos
[
(
2
i
+
1
)
[
N
-
(
u
+
1
)
]
π
2
N
]
cos
[
(
2
j
+
1
)
v
π
2
N
]
where C B 2 (u) and C B 2 (v) are given by,
C
B
2
(
u
)
,
C
B
2
(
v
)
=
1
2
,
u
=
N
-
1
,
v
=
0
C B 2 (u), C B 2 (v)=1, otherwise, and
where I B 2 (i, j) is the (i,j)th element of an image represented by the sub-block B 2 , wherein the flipped kernel discrete cosine transform applied to B 3 comprises:
for sub-block B 3 (N=8),
X
B
3
(
u
,
v
)
=
2
N
C
B
3
(
u
)
C
B
3
(
v
)
∑
i
=
0
N
-
1
∑
j
=
0
N
-
1
I
B
3
(
i
,
j
)
cos
[
(
2
i
+
1
)
u
π
2
N
]
cos
[
(
2
j
+
1
)
[
N
-
(
v
+
1
)
]
π
2
N
]
where C B 3 (u) and C B 3 (v) are given by,
C
B
3
(
u
)
,
C
B
3
(
v
)
=
1
2
,
u
=
0
,
v
=
N
-
1
C B 3 (u), C B 3 (v)=1, otherwise, and
where I B 3 (i, j) is the (i,j)th element of an image represented by the sub-block B 3 , and wherein the flipped kernel discrete cosine transform applied to B 4 comprises:
for sub-block B 4 (N=8),
X
B
4
(
u
,
v
)
=
2
N
C
B
4
(
u
)
C
B
4
(
v
)
∑
i
=
0
N
-
1
∑
j
=
0
N
-
1
I
B
4
(
i
,
j
)
cos
[
(
2
i
+
1
)
u
π
2
N
]
cos
[
(
2
j
+
1
)
v
π
2
N
]
where C B 4 (u) and C B 4 (v) are given by,
C
B
4
(
u
)
,
C
B
4
(
v
)
=
1
2
,
u
=
0
,
v
=
0
C B 4 (u), C B 4 (V)=1, otherwise, and
where I B 4 (i, j) is the (i,j)th element of an image represented by the sub-block B 4 .
9. The method of claim 8 , wherein the discrete cosine transform coefficient matrix for the sixteen by sixteen block comprises:
X
=
[
X
B
1
X
B
2
X
B
3
X
B
4
]
.
10. The method of claim 1 , wherein scanning the quantized discrete cosine transform coefficient of the sixteen by sixteen pixel block according to the rhomboid pattern further comprises:
performing a rhomboid scan with the quantized discrete cosine transform coefficient of the sixteen by sixteen pixel block.
11. The method of claim 10 , further comprising:
grouping a low-pass eight by eight pixel sub-block with a high-frequency coefficient of the eight by eight pixel sub-block.
12. The method of claim 10 further comprising:
mapping the quantized discrete cosine transform coefficient to a linear array.
13. The method of claim 12 ,
wherein the quantized discrete cosine transform coefficient is represented by a variable X,
wherein the linear array comprises two hundred and fifty-six terms and is represented by a variable L, and
wherein the rhombus scanning comprises a matrix-form D.
14. The method of claim 13 , wherein the matrix-form D comprises:
D
=
[
252
245
234
219
200
177
150
119
120
151
178
201
220
235
246
253
244
233
218
199
176
149
118
90
91
121
152
179
202
221
236
247
232
217
198
175
148
117
89
65
66
92
122
153
180
203
222
237
216
197
174
147
116
88
64
44
45
67
93
123
154
181
204
223
196
173
146
115
87
63
43
27
28
46
68
94
124
155
182
205
172
145
114
86
62
42
26
14
15
29
47
69
95
125
156
183
144
113
85
61
41
25
13
5
6
16
30
48
70
96
126
157
112
84
60
40
24
12
4
0
1
7
17
31
49
71
97
127
143
111
83
59
39
23
11
3
2
8
18
32
50
72
98
128
171
142
110
82
58
38
22
10
9
19
33
51
73
99
129
158
195
170
141
109
81
57
37
21
20
34
52
74
100
130
159
184
215
194
169
140
108
80
56
36
35
53
75
101
131
160
185
206
231
214
193
168
139
107
79
55
54
76
102
132
161
186
207
224
243
230
213
192
167
138
106
78
77
103
133
162
187
208
225
238
251
242
229
212
191
166
137
105
104
134
163
188
209
226
239
248
255
250
241
228
211
190
165
136
135
164
189
210
227
240
249
254
]
.
15. The method of claim 1 , wherein a machine is caused to perform the method of claim 1 when a set of instructions embodied in a non-transitory machine-readable medium is executed by the machine.
16. A non-transitory machine-readable medium including instructions embodied therein configured to execute on a computing system, comprising:
instructions for dividing a portion of a digital image into a sixteen by sixteen pixel block;
instructions for applying a flipped-kernel discrete cosine transform to an eight by eight pixel sub-block of the sixteen by sixteen pixel block;
instructions for removing a visually insignificant information from a spectral coefficient of the eight by eight pixel sub-block with a quantization method; and
instructions for scanning a quantized discrete cosine transform coefficient of the sixteen by sixteen pixel block according to a rhomboid pattern.
17. The machine-readable medium of claim 16 , comprising instructions for processing the sixteen by sixteen pixel block of the digital image in a left-to-right direction and a top-to-bottom direction, and
comprising instructions for quantizing a spectral coefficient of the eight by eight pixel sub-block with an eight by eight pixel quantization table.
18. The machine-readable medium of claim 17 , comprising instructions for processing the sixteen by sixteen pixel block in a left-to-right fashion and a top-to-bottom fashion.
19. A method of digital image compression comprising:
transforming an eight by eight pixel sub-block of a sixteen by sixteen pixel block of a digital image into a sum of cosine functions oscillating at different frequencies with a flipped-kernel discrete cosine transform;
compressing a range of values of the sum of cosine functions into a single quantum value with a quantization method in order to remove a visually insignificant information from the eight by eight pixel sub-block; and
rhombus scanning a quantized discrete cosine transform coefficient of the sixteen by sixteen pixel block.
20. The method of claim 19 , further comprising:
placing a low-pass coefficient of an eight by eight sub-block before a high-pass coefficient of the eight by eight sub-block to facilitate an entropy coder.