Hãy Viết Codec Video - Phần 3: Ảnh tĩnh

Trong các phần trước của loạt bài này, chúng ta đã tìm hiểu về Biến đổi Cosine rời rạc, từ định nghĩa toán học cho đến việc triển khai nó trong các ví dụ thực tế. Ngoài ra, chúng ta đã thấy khả năng biểu diễn dữ liệu trong miền tần số của DCT có thể cho phép nén dữ liệu bị mất dữ liệu như thế nào.

Bây giờ, chúng tôi đang thực hiện bước tiếp theo. Cuối cùng chúng ta sẽ vẽ đường kết nối các dãy số trừu tượng mà chúng ta đang thảo luận với những hình ảnh thực tế mà chúng có thể biểu thị.

Đến cuối bài viết này, chúng ta sẽ khám phá lại khoảng 80% quy trình nén ảnh JPEG thực tế.

Ma trận

Trong bài viết trước, chúng tôi đã giới thiệu về 2D-DCT. Bây giờ, hãy xem xét một phiên bản được điều chỉnh một chút của công thức đó:

Các biến u và v đại diện cho độ lệch ngang và dọc của giá trị trong mảng 2D được mã hóa DCT. Hàm α(x) bằng 1/sqrt(2) nếu x == 0 và 1 nếu ngược lại. Cuối cùng, x và y đại diện cho vị trí của pixel trong ảnh nguồn.

Điều này có vẻ không rõ ràng, nhưng phép tính tương tự có thể được biểu diễn dưới dạng phép nhân ma trận ở dạng sau:

Trong công thức này, DCT là ma trận DCT, T biểu thị chuyển vị ma trận và IMG là ảnh nguồn.

Hãy nhớ rằng độ phức tạp của thao tác này tỷ lệ thuận với kích thước của hình ảnh nguồn. Để quản lý hình ảnh ở bất kỳ kích thước nào và để giảm bớt công việc, chúng tôi sẽ giới hạn các tính toán của mình ở các khối hình ảnh 8 x 8 pixel.

Mặc dù hình ảnh thực có xu hướng có độ phân giải cao hơn, nhưng chúng ta có thể nghĩ rằng chúng bao gồm nhiều khối 8x8 độc lập.

Đây là cách chúng tôi tính toán ma trận DCT tạo ra hiệu ứng mong muốn:

 var dctMatrix: [Float] = Array(repeating: 0.0, count: 8 * 8) for i in 0 ..< 8 { for j in 0 ..< 8 { let a: Float if i == 0 { a = sqrt(1.0 / 8.0) } else { a = sqrt(2.0 / 8.0) } dctMatrix[j * 8 + i] = a * cos((2.0 * Float(j) + 1) * Float(i) * Float.pi / (2.0 * 8)) } }

Giá trị của dctMatrix là:

 0.35 0.49 0.46 0.42 0.35 0.28 0.19 0.10 0.35 0.42 0.19 -0.10 -0.35 -0.49 -0.46 -0.28 0.35 0.28 -0.19 -0.49 -0.35 0.10 0.46 0.42 0.35 0.10 -0.46 -0.28 0.35 0.42 -0.19 -0.49 0.35 -0.10 -0.46 0.28 0.35 -0.42 -0.19 0.49 0.35 -0.28 -0.19 0.49 -0.35 -0.10 0.46 -0.42 0.35 -0.42 0.19 0.10 -0.35 0.49 -0.46 0.28 0.35 -0.49 0.46 -0.42 0.35 -0.28 0.19 -0.10

Như bạn thấy, nó chỉ là một dãy số. Không cần phải tính toán lại các giá trị ma trận mỗi khi chúng ta áp dụng biến đổi, vì vậy chúng ta có thể giữ chúng trong một mảng không đổi trong mã của mình.

Mã này thực hiện phép nhân ma trận 8x8:

 func matrixMul8x8(m1: [Float], m2: [Float], result: inout [Float]) { for i in 0 ..< 8 { for j in 0 ..< 8 { var acc: Float = 0.0 for k in 0 ..< 8 { acc += m1[i * 8 + k] * m2[k * 8 + j] } result[i * 8 + j] = acc } } }

Chúng tôi tính DCT 8x8 như sau:

 func dct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrixT, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrix, result: &resultBlock) return resultBlock }

DCT nghịch đảo có thể thu được đơn giản bằng cách tráo đổi ma trận DCT thông thường và ma trận chuyển vị:

 func idct(_ block: [Float]) -> [Float] { var tmpBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) var resultBlock: [Float] = Array(repeating: 0.0, count: 8 * 8) matrixMul8x8(m1: dctMatrix, m2: block, result: &tmpBlock) matrixMul8x8(m1: tmpBlock, m2: dctMatrixT, result: &resultBlock) return resultBlock }

Bức tranh lớn

Bây giờ, chúng ta đã sẵn sàng áp dụng kiến thức của mình vào những hình ảnh thực tế. Hãy làm việc với cái này:

Hãy tưởng tượng chúng ta có mã tải hình ảnh này dưới dạng một dãy số trong đó mỗi số biểu thị độ sáng của pixel tại vị trí tương ứng:

 func loadImage(width: Int, height: Int) -> [Float] { ... }

Giả sử hình ảnh là 256x256 pixel, các giá trị sau sẽ tương ứng với góc trên cùng bên trái:

 -2.00 3.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -2.00 4.00 -7.00 -6.00 -3.00 -5.00 -13.00 -9.00 -3.00 -1.00 -8.00 -7.00 -6.00 -8.00 -14.00 -12.00 -7.00 -13.00 -9.00 -15.00 -15.00 -12.00 -23.00 -22.00 -18.00 -17.00 -11.00 -15.00 -11.00 -14.00 -20.00 -20.00 -21.00 -19.00 -20.00 -20.00 -18.00 -17.00 -19.00 -19.00 -16.00 -17.00 -20.00 -19.00 -17.00 -21.00 -24.00 -21.00 -19.00 -18.00 -20.00 -22.00 -19.00 -25.00 -20.00 -22.00

Để thuận tiện về mặt toán học, thay vì biểu thị độ sáng của pixel dưới dạng một số từ 0.0 đến 255.0 , chúng tôi trừ đi 128.0 . Nói cách khác, chúng tôi căn giữa giá trị xung quanh 0.0 thay vì 128.0 .

Sau đó, chúng tôi áp dụng hàm dct cho mọi khối 8x8 của hình ảnh:

 let values: [Float] = loadImage() // convert RGB to -128.0 ... 128.0 var destinationValues: [Float] = Array(repeating: 0.0, count: values.count) for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { let block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) let resultBlock: [Float] = dct(block) storeBlock(values: &destinationValues, width: width, block: resultBlock, x: i * 8, y: j * 8) } } storeImage(destinationValues) // convert back to RGB

Kết quả là hình ảnh này:

Mặc dù hầu như không thể nhận ra nó dưới dạng một bức ảnh, nhưng vẫn có thể nhìn thấy một số mẫu (như chiếc mũ). Thật thú vị, có rất nhiều pixel đen. Trên thực tế, hầu hết các pixel đều có màu đen. Hãy phóng to một trong các khối 8x8:

Khối 8x8 này minh họa tất cả những gì về biểu diễn miền tần số. Các giá trị khác 0 có xu hướng tập trung ở góc trên cùng bên trái của khối. Khả năng xảy ra một giá trị lớn giảm đáng kể khi chúng ta di chuyển về góc dưới cùng bên phải.

Điều này chỉ ra rằng các giá trị trên cùng bên trái mang tầm quan trọng hơn đối với hình ảnh.

Chúng ta có thể chứng minh điều này bằng cách viết hàm "nén" để loại bỏ một số giá trị dưới cùng bên phải bằng cách đặt chúng thành 0.0 :

 func compress(_ block: [Float], level: Int) -> [Float] { var resultBlock: [Float] = block for y in 0 ..< 8 { for x in 0 ..< 8 { if x >= 8 - level || y >= 8 - level { resultBlock[y * 8 + x] = 0.0 } } } return resultBlock }

Sau khi điều chỉnh vòng xử lý của chúng tôi:

 for j in 0 ..< height / 8 { for i in 0 ..< width / 8 { var block = extractBlock(values: values, width: width, x: i * 8, y: j * 8) block = dct(block) block = compress(block, level: 3) block = idct(block) storeBlock(values: &destinationValues, width: width, block: block, x: i * 8, y: j * 8) } }

Chúng tôi nhận được hình ảnh này:

Hãy dành một chút thời gian để xem xét những gì đã xảy ra. Chúng tôi đã loại bỏ 39 trong số 64 giá trị cho mỗi khối hình ảnh và vẫn tạo ra hình ảnh gần giống với hình ảnh gốc. Đây là tỷ lệ nén 60% đạt được chỉ bằng cách nhân các ma trận và loại bỏ dữ liệu một cách xác định!

Khi chúng tôi loại bỏ 86% hệ số DCT, điều này sẽ xảy ra:

lượng tử hóa

Sẽ cực kỳ lãng phí nếu lưu trữ các hệ số DCT dưới dạng số dấu phẩy động, thường yêu cầu 4 byte dung lượng lưu trữ. Thay vào đó, chúng ta nên làm tròn chúng đến số nguyên gần nhất. Đối với các khối 8x8, mỗi giá trị có thể được biểu thị bằng một số nguyên 2 byte.

Hãy xem lại khối mà chúng ta đã kiểm tra trước đó. Biểu diễn số (làm tròn) của nó là:

 209 -296 -49 43 -38 22 -6 1 39 24 -37 11 -4 -3 2 6 -15 16 -17 0 13 -4 0 5 16 4 2 4 -6 4 -3 -5 -11 4 -1 3 1 -3 6 3 6 -2 2 4 -2 -2 -4 -1 -6 1 0 1 -1 0 3 -1 0 0 0 0 -1 -1 -2 1

Như chúng tôi đã xác nhận trực quan trước đó, các giá trị lớn hơn có nhiều khả năng xuất hiện gần góc trên cùng bên trái hơn. Tuy nhiên, không phải mọi khối đều tuân theo mô hình này. Đây là một khối khác từ hình ảnh của chúng tôi:

Khối này không tuân thủ phân phối chung của các giá trị DCT. Nếu chúng tôi tiếp tục loại bỏ một cách mù quáng các giá trị dưới cùng bên phải, một số phần của hình ảnh có thể hiển thị nhiều thành phần nén hơn. Để tránh điều đó, chúng ta cần quyết định khối nào cần nhiều dữ liệu hơn các khối khác.

Một giải pháp đơn giản nhưng tinh tế tận dụng thuộc tính phân cụm mà chúng tôi đã phát hiện trước đó. Nó được gọi là "lượng tử hóa." Chúng tôi chia các giá trị DCT của mình cho các hệ số khác nhau. Chúng tôi sẽ sử dụng một bảng có chứa giá trị cho từng hệ số DCT để thuận tiện:

 16.50 11.50 10.50 16.50 24.50 40.50 51.50 61.50 12.50 12.50 14.50 19.50 26.50 58.50 60.50 55.50 14.50 13.50 16.50 24.50 40.50 57.50 69.50 56.50 14.50 17.50 22.50 29.50 51.50 87.50 80.50 62.50 18.50 22.50 37.50 56.50 68.50 109.50 103.50 77.50 24.50 35.50 55.50 64.50 81.50 104.50 113.50 92.50 49.50 64.50 78.50 87.50 103.50 121.50 120.50 101.50 72.50 92.50 95.50 98.50 112.50 100.50 103.50 99.50

Các vị trí quan trọng hơn tương ứng với ước số thấp hơn và ngược lại. Chúng tôi thực hiện bước khử lượng tử hóa bằng cách nhân dữ liệu lượng tử hóa với các hệ số trong bảng.

Các hàm này lần lượt thực hiện các bước lượng tử hóa và khử lượng tử hóa:

 func quantize(_ block: [Int], table: [Float]) -> [Int] { var result: [Int] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Int(round(Float(block[i]) / table[i])) } return result } func dequantize(_ block: [Int], table: [Float]) -> [Float] { var result: [Float] = Array(repeating: 0, count: block.count) for i in 0 ..< block.count { result[i] = Float(block[i]) * table[i] } return result }

Hãy kết hợp lượng tử hóa và khử lượng tử hóa vào mã của chúng ta:

 block = dct(block) var iblock = rounded(block) iblock = quantize(iblock, table: testTable) block = dequantize(iblock, table: testTable) block = idct(block)

Đây là giao diện của khối đầu tiên khi được lượng tử hóa:

 13 -26 -5 3 -2 1 0 0 3 2 -3 1 0 0 0 0 -1 1 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Và đây là khối thứ hai:

 -5 18 -10 0 1 1 1 0 0 3 1 -2 0 1 0 0 -4 0 1 0 1 1 0 0 -1 0 0 -2 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Bạn sẽ nhận thấy rằng có nhiều giá trị khác 0 hơn trong khối thứ hai. Do đó, bước lượng tử hóa cho phép chúng tôi lưu trữ nhiều dữ liệu hữu ích hơn và loại bỏ phần còn lại.

Kết luận và điều gì tiếp theo?

Từ toán học cơ bản, chúng tôi đã thực hiện theo cách của mình để mã hóa và giải mã hình ảnh thực. Chúng tôi đã thấy trực quan cách DCT chuyển đổi dữ liệu tùy ý thành một tập hợp các tần số và cách một số tần số quan trọng hơn các tần số khác.

Sau khi chúng tôi cảm thấy thoải mái với tính năng nén cơ bản, chúng tôi đã giới thiệu khái niệm lượng tử hóa, giúp giảm thêm yêu cầu lưu trữ.

Trong phần tiếp theo, chúng ta sẽ chuyển sang hình ảnh RGB và khám phá các cách để nén dữ liệu kết quả hơn nữa.

Mã cho bài viết này có thể được tìm thấy tại https://github.com/petertechstories/image-dct