DCT (Discrete cosine transform) biến đổi cosin rời rạc

DCT (Discrete cosine transform) biến đổi cosin rời rạc

Bài viết này phác thảo quá trình xử lý DCT, trong đó chúng tôi chuyển đổi khối pixel (thường là 8x8) thành tần số không gian:

Lý thuyết

JPEG là một kỹ thuật nén tuyệt vời tạo ra nén có mất dữ liệu (mặc dù ở một chế độ, nó không mất dữ liệu). Như đã thấy từ các bài viết trước, nó có tỷ lệ nén tuyệt vời khi áp dụng cho ảnh màu. Bài này giới thiệu chuẩn JPEG và phương pháp được sử dụng để nén ảnh. Nó cũng thảo luận về chuẩn tệp JFIF xác định định dạng tệp cho ảnh được mã hóa JPEG. Cùng với các tệp GIF, JPEG hiện là một trong những chuẩn được sử dụng rộng rãi nhất để nén ảnh.

Mã hóa JPEG

JPEG là một tiêu chuẩn điển hình cho nén hình ảnh đã được Nhóm chuyên gia nhiếp ảnh chung (JPEG), một tiểu ban của ISO/IEC, đưa ra và các tiêu chuẩn được tạo ra có thể được tóm tắt như sau:

Đây là một kỹ thuật nén cho hình ảnh thang độ xám hoặc màu và sử dụng kết hợp giữa phép biến đổi cosin rời rạc, lượng tử hóa, độ dài chạy và mã hóa Huffman.

Nó là kết quả của quá trình nghiên cứu về tỷ lệ nén và chất lượng hình ảnh thu được. Các bước chính là:

Khối dữ liệu. Tạo khối dữ liệu

Mã hóa nguồn. Biến đổi cosin rời rạc và lượng tử hóa

Mã hóa entropy. Mã hóa độ dài chạy và mã hóa Huffman

Thật không may, so với GIF, TIFF và PCX, quá trình nén tương đối chậm. Nó cũng bị mất dữ liệu ở chỗ một số thông tin bị mất trong quá trình nén. Thông tin này được coi là có ít tác động đến hình ảnh được giải mã.

Tệp GIF thường lấy thông tin màu 24 bit (8 bit cho màu đỏ, 8 bit cho màu xanh lá cây và 8 bit cho màu xanh lam) và chuyển đổi thành bảng màu 8 bit (do đó giảm số bit được lưu trữ xuống còn khoảng một phần ba so với bản gốc). Sau đó, nó sử dụng nén LZW để giảm thêm dung lượng lưu trữ. JPEG hoạt động khác ở chỗ nó lưu trữ các thay đổi về màu sắc. Vì mắt rất nhạy cảm với các thay đổi về độ sáng và ít nhạy cảm hơn với các thay đổi về màu sắc, nên nếu những thay đổi này giống với bản gốc thì mắt sẽ nhận thấy hình ảnh được khôi phục rất giống với bản gốc.

Chuyển đổi màu sắc và lấy mẫu phụ

Phần đầu tiên của quá trình nén JPEG tách từng thành phần màu (đỏ, lục và lam) theo độ sáng (độ sáng) và sắc độ (thông tin màu). JPEG cho phép mất nhiều sắc độ hơn và ít độ sáng hơn vì mắt người ít nhạy cảm với sự thay đổi màu sắc hơn là với sự thay đổi độ sáng. Trong ảnh RGB, cả ba màu đều mang một số thông tin về độ sáng nhưng thành phần lục có tác động mạnh hơn đến độ sáng so với thành phần lam.

sơ đồ điển hình để chuyển đổi RGB thành độ sáng và màu là CCIR 601, chuyển đổi các thành phần thành Y (có thể tương đương với độ sáng), Cb (màu lam) và Cr (màu đỏ). Thành phần Y có thể được sử dụng làm phiên bản đen trắng của ảnh.

Mỗi thành phần được tính toán từ các thành phần RGB như sau:

Y=0,299R+0,587G+0,114B

Cb=0,1687R–0,3313G+0,5B

Cr=0,5R–0,4187G+0,0813B

Đối với độ sáng (Y), có thể thấy rằng màu xanh lá cây có hiệu ứng lớn nhất và màu xanh lam có hiệu ứng nhỏ nhất. Đối với màu đỏ (Cr), màu đỏ (tất nhiên) có hiệu ứng lớn nhất và màu xanh lục có hiệu ứng nhỏ nhất. Đối với màu xanh lam (Cb), màu xanh lam có hiệu ứng lớn nhất và màu xanh lục có hiệu ứng nhỏ nhất. Lưu ý rằng các thành phần YCbCr thường được gọi là YUV (đặc biệt là trong các hệ thống TV).

Sau đó, quá trình lấy mẫu phụ là lấy mẫu các thành phần Cb và Cr ở tốc độ thấp hơn thành phần Y. Tốc độ lấy mẫu thông thường là bốn mẫu thành phần Y cho một mẫu thành phần Cb và Cr duy nhất (4:1:1). Tốc độ lấy mẫu này thường được thiết lập với các tham số nén, tốc độ lấy mẫu càng thấp, dữ liệu nén càng nhỏ và thời gian nén càng ngắn. Tiêu đề JPEG chứa tất cả thông tin cần thiết để giải mã đúng dữ liệu JPEG.

Mã hóa DCT

DCT (biến đổi cosin rời rạc) chuyển đổi dữ liệu cường độ thành dữ liệu tần số, có thể được sử dụng để cho biết cường độ thay đổi nhanh như thế nào. Trong mã hóa JPEG, hình ảnh được phân đoạn thành các hình chữ nhật pixel 8x8. Nếu hình ảnh chứa một số thành phần (như Y, Cb, Cr hoặc R, G, B), thì mỗi thành phần trong các khối pixel được vận hành riêng biệt. Nếu một hình ảnh được lấy mẫu phụ, sẽ có nhiều khối của một số thành phần hơn các khối khác. Ví dụ, đối với mẫu 2x2, sẽ có bốn khối dữ liệu Y cho mỗi khối dữ liệu Cb hoặc Cr.

Các điểm dữ liệu trong mảng pixel 8x8 bắt đầu ở góc trên bên phải tại (0,0) và kết thúc ở góc dưới bên phải tại (7,7). Tại điểm (x, y), giá trị dữ liệu là f(x, y). DCT tạo ra một khối 8x8 mới (uxv) dữ liệu đã chuyển đổi bằng cách sử dụng công thức:

Hình 1 Phân đoạn hình ảnh trong các khối pixel 8x8

Điều này tạo ra một mảng tần số không gian F(u,v) cho biết tốc độ thay đổi tại một điểm nhất định. Đây thường là các giá trị 12 bit cho biết phạm vi từ 0 đến 1024. Mỗi thành phần chỉ định mức độ thay đổi của hình ảnh trên khối được lấy mẫu. Ví dụ:

F(0,0) cho biết giá trị trung bình của mảng 8x8.

F(1,0) cho biết mức độ thay đổi chậm của các giá trị (tần số thấp).

F(7,7) cho biết mức độ thay đổi nhanh nhất của các giá trị theo cả hai hướng (tần số cao).

Các hệ số tương đương với việc biểu diễn các thay đổi tần số trong khối dữ liệu. Giá trị trong khối trên cùng bên trái (0,0) là giá trị DC hoặc giá trị trung bình. Các giá trị ở bên phải của một hàng có tần số ngang tăng dần và các giá trị ở dưới cùng của một cột có tần số dọc tăng dần. Tuy nhiên, nhiều dải cuối cùng có các số hạng bằng không hoặc gần bằng không.

Chương trình bên dưới cung cấp chương trình C xác định DCT của khối 8x8 và Chạy mẫu 1 hiển thị chạy mẫu với các hệ số kết quả.

#include <stdio.h>

#include <math.h>

#define PI       3.1415926535897

int      main(void)

{

int      x,y,u,v;

float   in[8][8]=        {{144,139,149,155,153,155,155,155},

                                   {151,151,151,159,156,156,156,158},

                                   {151,156,160,162,159,151,151,151},

                                   {158,163,161,160,160,160,160,161},

                                   {158,160,161,162,160,155,155,156},

                                   {161,161,161,161,160,157,157,157},

                                   {162,162,161,160,161,157,157,157},

                                   {162,162,161,160,163,157,158,154}};

float   out[8][8],sum,Cu,Cv;

         for (u=0;u<8;u++)

         {

                 for (v=0;v<8;v++)

                 {

                          sum=0;

                          for (x=0;x<8;x++)

                                   for (y=0;y<8;y++)

                                   {

                                            sum=sum+in[x][y]*cos(((2.0*x+1)*u*PI)/16.0)*

                                                    cos(((2.0*y+1)*v*PI)/16.0);

                                   }

                          if (u==0) Cu=1/sqrt(2); else Cu=1;

                          if (v==0) Cv=1/sqrt(2); else Cv=1;

                          out[u][v]=1/4.0*Cu*Cv*sum;

                          printf("%8.1f ",out[u][v]);

                 }

                 printf("\n");

         }

         printf("\n");

         return(0);

}

Chương trình sử dụng khối cố định 8x8 gồm:

 144      139      149      155      153      155      155      155      

 151      151      151      159      156      156      156      158

 151      156      160      162      159      151      151      151

 158      163      161      160      160      160      160      161

 158      160      161      162      160      155      155      156

 161      161      161      161      160      157      157      157

 162      162      161      160      161      157      157      157

 162      162      161      160      163      157      158      154

 Sample run 8.1

 1257.9      2.3     -9.7     -4.1      3.9      0.6     -2.1      0.7 

    -21.0    -15.3     -4.3     -2.7      2.3      3.5      2.1     -3.1 

    -11.2     -7.6     -0.9      4.1      2.0      3.4      1.4      0.9 

     -4.9     -5.8      1.8      1.1      1.6      2.7      2.8     -0.7 

      0.1     -3.8      0.5      1.3     -1.4      0.7      1.0      0.9 

      0.9     -1.6      0.9     -0.3     -1.8     -0.3      1.4      0.8 

     -4.4      2.7     -4.4     -1.5     -0.1      1.1      0.4      1.9 

     -6.4      3.8     -5.0     -2.6      1.6      0.6      0.1      1.5 

Lưu ý rằng các giá trị của các giá trị quan trọng nhất nằm ở góc trên bên trái và nhiều thuật ngữ gần bằng không. Chính đặc tính này cho phép nhiều giá trị trở thành số không khi lượng tử hóa. Các số không này sau đó có thể được nén bằng mã hóa độ dài chạy và mã Huffman

Lượng tử hóa

Giai đoạn tiếp theo của quá trình nén JPEG là lượng tử hóa, trong đó độ lệch được đưa vào các thành phần tần số thấp hơn. JPEG chia mỗi giá trị DCT cho một hệ số lượng tử hóa, sau đó làm tròn đến số nguyên gần nhất. Vì các hệ số DCT là 8x8 nên một bảng gồm 8x8 hệ số lượng tử hóa được sử dụng, tương ứng với mỗi số hạng của đầu ra DCT. Sau đó, tệp JPEG lưu trữ bảng này để quá trình giải mã có thể sử dụng bảng này hoặc một bảng lượng tử hóa chuẩn. Lưu ý rằng các tệp có nhiều thành phần phải có nhiều bảng, chẳng hạn như một bảng cho mỗi thành phần Y, Cb và Cr.

Ví dụ, các giá trị của số hạng tần số cao được lượng tử hóa (chẳng hạn như F(7,7)) có thể có một số hạng khoảng 100, trong khi số hạng tần số thấp có thể có một hệ số là 16. Các giá trị này xác định độ chính xác của giá trị cuối cùng. Khi giải mã, các giá trị ban đầu được khôi phục (xấp xỉ) bằng cách nhân với hệ số lượng tử hóa.

Hình 2 cho thấy, đối với hệ số 100, các giá trị giữa 50 và 150 sẽ được lượng tử hóa thành 1, do đó sai số tối đa sẽ là +/-50. Sai số tối đa đối với hệ số 16 là +/-8. Do đó, sai số tối đa của giá trị cuối cùng chưa lượng tử hóa đối với hệ số tỷ lệ 100 là 1,22% (5000/4096), trong khi hệ số 16 cho sai số tối đa là 0,20% (800/4096). Vì vậy, khi sử dụng các hệ số 100 cho F(7,7) và 16 cho F(0,0), và DCT 12 bit, thì thuật ngữ F(0,0) sẽ nằm trong khoảng từ 0 đến 256 và thuật ngữ F(7,7) sẽ nằm trong khoảng từ 0 đến 41. Thuật ngữ F(0,0) có thể được mã hóa bằng 8 bit (0 đến 255) và thuật ngữ F(7,7) bằng 6 bit (0 đến 63).

Hình 2 Ví dụ về lượng tử hóa

Chương trình 2 chuẩn hóa và lượng tử hóa (đến số nguyên gần nhất) ví dụ đã cho trước đó. Để tóm tắt lại, khối 8x8 đầu vào là:

 144      139      149      155      153      155      155      155      

 151      151      151      159      156      156      156      158

 151      156      160      162      159      151      151      151

 158      163      161      160      160      160      160      161

 158      160      161      162      160      155      155      156

 161      161      161      161      160      157      157      157

 162      162      161      160      161      157      157      157

 162      162      161      160      163      157      158      154

Ma trận chuẩn hóa được áp dụng là:

 5                3                4                4                 4                3                 5                4

 4                4                5                5                 5                6                 7                12

 8                7                7                7                 7                15                11               11

 9                12               13               15               18               18                17               15

 20               20               20               20               20               20                20               20

 20               20               20               20               20                20                20               20

 20               20               20               20               20               20                20               20

 20               20               20               20               20               20                20               20

 Program 2

 #include <stdio.h>

 #include <math.h>

 #define PI       3.1415926535897

 int      main(void)

 {

 int      x,y,u,v;

 float   in[8][8]=        {

                  {144,139,149,155,153,155,155,155},

                  {151,151,151,159,156,156,156,158},

                  {151,156,160,162,159,151,151,151},

                  {158,163,161,160,160,160,160,161},

                  {158,160,161,162,160,155,155,156},

                  {161,161,161,161,160,157,157,157},

                  {162,162,161,160,161,157,157,157},

                  {162,162,161,160,163,157,158,154}};

 float   norm[8][8]=      {

          {5,3,4,4,4,3,5,4},

          {4,4,5,5,5,6,7,12},

          {8,7,7,7,7,15,11,11},

          {9,12,13,15,18,18,17,15},

          {20,20,20,20,20,20,20,20},

          {20,20,20,20,20,20,20,20},

          {20,20,20,20,20,20,20,20},

          {20,20,20,20,20,20,20,20}};

 int      out[8][8];

 float   sum,Cu,Cv;

          for (u=0;u<8;u++)

          {

                  for (v=0;v<8;v++)

                  {

                           sum=0;

                           for (x=0;x<8;x++)

                                    for (y=0;y<8;y++)

                                    {

                                             sum=sum+in[x][y]*cos(((2.0*x+1)*u*PI)/16.0)*

                                                     cos(((2.0*y+1)*v*PI)/16.0);

                                    }

                           if (u==0) Cu=1/sqrt(2); else Cu=1;

                           if (v==0) Cv=1/sqrt(2); else Cv=1;

                           out[u][v]=(int)1/4.0*Cu*Cv*sum/norm[u][v];

                           printf("%8d ",out[u][v]);

                  }

                  printf("\n");

          }

          printf("\n");

          return(0);

 }

Source code

Sau đây là tóm tắt mã Python được sử dụng:

 import cv2

 import numpy as np

 import  sys

 import matplotlib.pyplot as plt

 file1='1111'

 matrix = "[ [0, 21, 21, 22, 22, 22, 22, 22], [21, 21, 21, 21, 21, 21, 21, 21], [21, 21, 21, 21, 21, 21, 21, 21], [21,21,21,21,21,20,20,20], [22, 22, 22, 22, 21, 21, 21, 21], [24, 24, 24, 23, 23, 22, 22, 22], [26, 26, 25, 25, 24, 24, 24, 23], [27, 27, 27, 26, 25, 25, 25, 24]]"

 if (len(sys.argv)>1):

         matrix=str(sys.argv[1])

 if (len(sys.argv)>2):

         file=str(sys.argv[2])

 block = eval(matrix)

 print "Input:\n",block

 blockf = np.float32(block)  

 dst = cv2.dct(blockf)  

 print "\nDCT:\n",np.int32(dst)

 block = cv2.idct(dst)  

 print "\nInverse DCT:\n",np.int32(block) 

 x = [1, 2, 3, 4, 5, 6,7,8,9]

 y = [1, 2, 3, 4, 5, 6,7,8,9]

 x, y = np.meshgrid(x, y)

 plt.pcolormesh(x, y, block,vmin=0, vmax=255)

 plt.colorbar() 

 plt.show()

Đọc thêm các bài viết tại đây:

1.JPEG hoạt động như thế nào? 

2.JPEG thực sự là gì? Nó hoạt động như thế nào?