Nén ảnh sử dụng biến đổi Wavelet và ứng dụng trong các dịch vụ dữ liệu đa phương tiện di động

t và ( ),a b tψ . Các hàng của ma trận tương ứng với các giá trị của a và các cột tương ứng với các giá trị của b do cách tính biến đổi Wavelet theo tích vô hướng đã trình bày ở trên: ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )* , ,, , a b a bf t g t f t g t dt f t t f t t dtψ ψ∞ ∞−∞ −∞= ⇒ =∫ ∫ (3.11) 3.1.2. Biến đổi Wavelet rời rạc Việc tính toán các hệ số Wavelet tại tất cả các tỉ lệ là một công việc hết sức phức tạp. Nếu tính toán như vậy sẽ tạo ra một lượng dữ liệu khổng lồ. Để giảm thiểu công việc tính toán người ta chỉ chọn ra một tập nhỏ các giá trị tỉ lệ và các vị trí để tiến hành tính toán. Hơn nữa nếu việc tính toán được tiến hành tại các tỷ lệ và các vị trí trên cơ sở luỹ thừa cơ số 2 thì kết quả thu được sẽ hiệu quả và chính xác hơn rất nhiều. Quá trình chọn các tỷ lệ và các vị trí để tính toán như trên tạo thành lưới nhị tố (dyadic). Một phân tích như trên hoàn toàn có thể thực hiện được nhờ biến đổi Wavelet rời rạc (DWT). Do đó, việc tính toán biến đổi DWT thực chất là sự rời rạc hoá biến đổi Wavelet liên tục (CWT); việc rời rạc hoá được thực hiện với sự lựa chọn các hệ số a và b như sau: 2 ; 2 ; ,m ma b n m n Z= = ∈ (3.12) Việc tính toán hệ số của biến đổi Wavelet có thể dễ dàng thực hiện bằng các băng lọc số nhiều nhịp đa kênh, một lý thuyết rất quen thuộc trong xử lý tín hiệu. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Shift n m = -2 m = -1 m = 0 m = 1 m = 2 Hình 3.1. Minh hoạ lưới nhị tố dyadic với các giá trị của m và n 3.2. Tính chất của biến đổi Wavelet Tất cả chúng ta đều biết rằng biến đổi Fourier là một biến đổi đã và đang được áp dụng rộng rãi trong nhiều ngành khoa học và kỹ thuật khác nhau. Biến đổi Fourier chuyển một hàm tín hiệu từ miền thời gian sang miền tần số. Sử dụng biến đổi Fourier ta có thể biết được trong tín hiệu ( )f t có các thành phần tần số nào. Tuy nhiên biến đổi Fourier có một nhược điểm cơ bản là với một tín hiệu ( )f t ta không thể biết được rằng tại một thời điểm t thì tín hiệu có các thành phần tần số nào. Một phép biến đổi tốt hơn biến đổi Fourier phải là phép biến đổi có đầy đủ tính năng của biến đổi Fourier và có khả năng xác định xem tại một thời điểm t bất kỳ trong tín hiệu ( )f t có thành phần tần số nào. Phép biến đổi Wavelet ra đời đã khắc phục được các nhược điểm của biến đổi Fourier trong phân tích tín hiệu. Biến đổi Wavelet dù chỉ làm việc với các tín hiệu một chiều (liên tục hoặc rời rạc) nhưng sau khi biến đổi xong ta thu được một hàm số hai biến hoặc một tập các cặp giá trị ( ),W a b minh họa các thành phần tần số khác nhau của tín hiệu xảy ra tại thời điểm t . Các giá trị ( ),iW a b tạo thành một cột (i=1, 2,...., n) cho biết một thành phần tần số có trong những thời điểm t nào và các giá trị ( ), iW a b tạo thành hàng cho biết tại một thời điểm t của tín hiệu ( )f t có các thành phần tần số nào. Được nghiên cứu từ trước những năm 80 của thế kỷ trước và cũng đã Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh được ứng dụng trong một số ngành khoa học và công nghệ khác nhau nhưng biến đổi Wavelet vẫn là một lĩnh vực đang và sẽ tiếp tục được nghiên cứu và phát triển cũng như ứng dụng rộng rãi hơn nữa. Tham số b trong biến đổi Wavelet cho biết khoảng dịch của hàm Wavelet mẹ và độ phân giải các tần số khác nhau của ( )f t được minh họa bởi hệ số tỷ lệ chính là a. Biến đổi Wavelet ngày càng được áp dụng rộng rãi đặc biệt là trong xử lý tiếng nói, xử lý ảnh số. Tín hiệu tiếng nói là tín hiệu một chiều nhưng do đặc điểm của tiếng nói là tín hiệu không dừng nên việc sử dụng Fourier là không đủ để phân tích một cách đầy đủ các đặc trưng của tiếng nói. Khác với tín hiệu tiếng nói, xử lý tín hiệu ảnh số là xử lý tín hiệu hai chiều và do đặc điểm của ảnh số là bao giờ cũng có tính định hướng và tính định vị. Tính định hướng của một ảnh nghĩa là trong ảnh bao giờ cũng có một số ít các thành phần tần số nhưng các thành phần tần số này trải rộng trên toàn bộ không gian ảnh còn tính định vị của ảnh chính là tính chất biểu thị rằng tại một vùng của ảnh có thể có rất nhiều thành phần tần số. Ảnh biểu thị tính định vị rõ nhất chính là ảnh có nhiều biên vùng phân tách rõ rệt, tại các đường biên bao giờ cũng có nhiều thành phần tần số khác nhau, còn hầu hết các ảnh có tông liên tục đều là những ảnh có tính định hướng. Ngoài ra người ta thường áp dụng một cách kết hợp biến đổi Wavelet với các hàm Wavelet thích hợp với dạng tín hiệu cần khảo sát và phép phân tích đa phân giải để việc xử lý tín hiệu tiếng nói và hình ảnh đạt hiệu quả cao hơn. Trước khi xem xét ứng dụng của phân tích đa phân giải trong nén ảnh, chúng ta xem xét lý thuyết về đa phân giải trong phân tích tín hiệu. Giả sử chúng ta cần xấp xỉ hoá một tín hiệu liên tục có dạng một hàm bình phương khả tích ( )f x bằng một tập các giá trị rời rạc (ví dụ hàm ( )f x là hàm cường độ sáng của ảnh). Phép xấp xỉ đơn giản thực Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh hiện dựa trên lý thuyết phép lấy trung bình và dựa vào hàm xấp xỉ là hàm ( )xϕ có dạng: ( ) [ )1 0,1 0 x xϕ ⎧ ∈⎪= ⎨⎪⎩ c¸c gi¸ trÞ cßn l¹i (3.13) Việc tính toán các giá trị xấp xỉ của hàm ( )f x theo hàm ( )xϕ sẽ được viết như sau: ( ) ( )n n A f x f x nϕ= −⎡ ⎤⎣ ⎦ ∑ (3.14) với nf là chính là giá trị xấp xỉ của hàm ( )f x trong khoảng [ ); 1n n + . Đây chính là giá trị trung bình của hàm ( )f x trong khoảng [ ); 1n n + được cho bởi biểu thức: ( )1nn nf f x+= ∫ (3.15) Như vậy chúng ta có thể xấp xỉ hoá hàm ( )f x bằng một tập các hàm tương tự như hàm ( )xϕ và phép xấp xỉ hoá hàm ( )f x cho bởi: ( ) ( ) ( ) ( ), n A f x x n f x x nϕ ϕ= − −⎡ ⎤⎣ ⎦ ∑ % (3.16) Ở đây ( )xϕ% được gọi là hàm trọng và ( )xϕ là hàm nội suy, để xấp xỉ ( )xϕ thoả mãn: ( ) ( ) [ ],x x n nϕ ϕ δ− =% (3.17) Việc phải thoả mãn điều kiện 3.17 là để đảm bảo rằng hàm ( )f x có thể được xấp xỉ hoá bằng một tổ hợp tuyến tính của các hàm ( )x nϕ − . Ngoài ra hai hàm ( )xϕ% và ( )xϕ phải được chuẩn hoá để thoả mãn: ( ) ( )2 2 1x dx x dxϕ ϕ= =∫ ∫ % (3.18) Trong thực tế, hàm ( )f x thường được giả thiết là có chu kỳ nguyên và chúng ta chỉ cần một số hữu hạn các tổ hợp tuyến tính để xấp xỉ hoá hàm ( )f x . Chúng ta có thể thay đổi độ phân giải của phép xấp xỉ bằng cách Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh thay đổi hệ số tỷ lệ của các hàm ( )xϕ% và ( )xϕ . Cho ( ) ( )22 2jj jx xϕ ϕ= và ( ) ( )22 2jj jx xϕ ϕ=% % , chúng ta có xấp xỉ: ( ) ( ) ( ) ( ), 2 2j j j j j k A f x f x x k x kϕ ϕ− −= − −⎡ ⎤⎣ ⎦ ∑ % (3.19) của hàm ( )f x là các phép chiếu trực giao của hàm ( )f x lên không gian lấy ( ){ }2j j k x kϕ − ∈ − làm cơ sở. Việc thay đổi giá trị của j sẽ làm thay đổi mức độ chính xác của phép xấp xỉ hàm ( )f x của chúng ta như trên hình 3.2. Hình 3.2. Phân tích đa phân giải áp dụng cho biểu diễn tín hiệu Hàm ( )xϕ được gọi là hàm tỷ lệ và chúng ta thấy hàm này có một tính chất đặc biệt là các hàm ứng với độ phân giải thứ j (tức là có chiều rộng 2 j− ) là trường hợp đặc biệt của các hàm có độ phân giải thứ 1j + (chiều rộng 12 j− − ) bởi vì các hàm có độ phân giải j có thể dễ dàng biểu diễn từ các hàm có độ phân giải 1j + . Điều đó dẫn tới: 1j jV V +⊂ Vì vậy chúng ta có thể biểu diễn hàm ( )f x theo các mức phân giải khác nhau dựa trên các phép chiếu trực giao của hàm ( )f x lên các không gian jV . Chính vì thế người ta định nghĩa một phép phân tích đa phân giải như sau: Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh *. Một phân tích đa phân giải bao gồm một chuỗi không gian bao hàm nhau: 2 1 0 1 2.... ...V V V V V− −⊂ ⊂ ⊂ ⊂ (3.20) thoả mãn: ( )2j j Z V L R −−− ∈ =U (3.21) { }0j j Z V ∈ =I (3.22) Tính bất biến tỷ lệ ( ) ( ) 02 jjf x V f x V∈ ⇔ ∈ (3.23) Tính bất biến dịch: ( ) ( )0 0f x V f x n V n Z∈ ⇔ − ∈ ∀ ∈ (3.24) Tính tồn tại của cơ sở Tồn tại 0Vϕ∈ với ( ){ }x n n Zϕ − ∈ (3.25) là một cơ sở trực chuẩn của 0V *. Nếu chúng ta gọi ( ) ( ) mV A f x proj f x=⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦ là hình chiếu trực giao của ( )f x lên mV , thì ta có: ( ) ( )lim mm Vproj f x f x→−∞ =⎡ ⎤⎣ ⎦ (3.26) Trên đây là cơ sở lý thuyết của phép phân tích đa phân giải với tín hiệu 1D tổng quát. Việc áp dụng trong tín hiệu ảnh (tín hiệu 2D) có thể dễ dàng mở rộng từ việc phân tích đa phân giải 1D, chúng ta sẽ xét tới ở phần áp dụng trong JPEG2000 ở phần sau 3.3. Giới thiệu một số họ Wavelet 3.3.1. Biến đổi Wavelet Haar Biến đổi Haar Wavelet là biến đổi đơn giản nhất trong các phép biến đổi Wavelet. Hình vẽ 3.2 cho thấy dạng của hàm ( )tψ với biến đổi Haar. Do tính chất đơn giản của biến đổi Haar mà nó được ứng dụng tương đối nhiều trong nén ảnh, khi áp dụng biến đổi này để nén ảnh thì Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh thuật toán nén ảnh trên máy tính có một số điểm khác với công thức toán học của biến đổi Haar Hình 3.3. Hàm ( )tψ của biến đổi Haar 3.3.2. Biến đổi Wavelet Meyer Yves Meyer là một trong những nhà khoa học đã đặt nền móng cho phép biến đổi Wavelet. Phép biến đổi Wavelet mang tên Meyer cũng là một phép biến đổi thông dụng, biến đổi này có khả năng phân tích tín hiệu tốt hơn nhiều so với biến đổi Haar. Dạng của hàm ( )tψ với biến đổi Meyer cho ở hình vẽ: Hình 3.4: Hàm ( )tψ của biến đổi Meyer 3.3.3. Biến đổi Wavelet Daubechies Giống như Meyer, Daubechies cũng là một nhà khoa học có công lao to lớn trong việc nghiên cứu phát triển phép biến đổi Wavelet. Biến đổi Daubechies là một trong những phép biến đổi phức tạp nhất trong biến đổi Wavelet. Họ biến đổi này được ứng dụng hết sức rộng rãi, biến đổi Wavelet áp dụng trong JPEG2000 là một biến đổi trong họ biến đổi Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Wavelet Daubechies. Dưới đây là một số hàm ( )tψ trong họ biến đổi Wavelet Daubechies: Hình 3.5. Hàm ( )tψ của họ biến đổi Daubechies n với n=2, 3, 7, 8 3.4. Một số ứng dụng nổi bật của Wavelet Phần này chỉ nêu ra các lĩnh vực mang tính chất tổng quát các ứng dụng của Wavelet với tính chất giới thiệu và gợi mở. 3.4.1. Nén tín hiệu Do đặc điểm của mình, Wavelet đặc biệt tốt khi sử dụng để nén hay phân tích các tín hiệu không dừng; đặc biệt là tín hiệu ảnh số và các ứng dụng nén tiếng nói, nén dữ liệu. Việc sử dụng các phép mã hoá băng con, băng lọc số nhiều nhịp và biến đổi Wavelet rời rạc tương ứng với loại tín hiệu cần phân tích có thể mang lại những hiệu quả rất rõ rệt trong nén tín hiệu. Do tính chất chỉ tồn tại trong các khoảng thời gian rất ngắn (khi phân tích tín hiệu trong miền thời gian tần số) mà các hệ số của biến đổi Wavelet có khả năng tập trung năng lượng rất tốt vào các hệ số biến đổi. Các hệ số mang thông tin chi tiết của biến đổi Wavelet thường rất nhỏ và có thể bỏ qua mà không ảnh hưởng tới việc mã hoá dữ liệu (trong phương Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh pháp mã hoá ảnh hay tiếng nói là những tín hiệu cho phép mã hoá có tổn thất thông tin). 3.4.2. Khử nhiễu Tính chất của biến đổi Wavelet mà chúng ta đã xét tới trong phần ứng dụng cho nén tín hiệu được mở rộng bởi Iain Johnstone và David Donohos trong các ứng dụng khủ nhiễu cho tín hiệu. Phương pháp khử nhiễu này được gọi là Wavelet Shrinkage Denoising (WSD). Ý tưởng cơ bản của WSD dựa trên việc tín hiệu nhiễu sẽ lộ rõ khi phân tích bằng biến đổi Wavelet ở các hệ số biến đổi bậc cao. Việc áp dụng các ngưỡng loại bỏ tương ứng với các bậc cao hơn của hệ số Wavelet sẽ có thể dễ dàng loại bỏ nhiễu trong tín hiệu. 3.4.3. Mã hoá nguồn và mã hoá kênh Sở dĩ Wavelet được ứng dụng trong mã hoá nguồn và mã hoá kênh vì trong mã hoá nguồn thì chúng ta cần khả năng nén với tỷ lệ nén cao còn trong mã hoá kênh thì cần khả năng chống nhiễu tốt. Biến đổi Wavelet kết hợp với một số phương pháp mã hoá như mã hoá Huffman hay mã hoá số học có thể thực hiện được cả hai điều trên. Vì thế sự sử dụng biến đổi Wavelet trong mã hoá nguồn và mã hoá kênh là rất thích hợp. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh CHƯƠNG 4:CHUẨN NÉN ẢNH TĨNH DỰA TRÊN BIẾN ĐỔI WAVELET – JPEG2000 4.1. Lịch sử ra đời và phát triển chuẩn JPEG2000 Như chúng ta đã biết, sự ra đời của JPEG mang lại nhiều lợi ích to lớn về nhiều mặt. JPEG có thể giảm nhỏ kích thước ảnh, giảm thời gian truyền và làm giảm chi phí xử lý ảnh trong khi chất lượng ảnh là khá tốt. Tuy nhiên cho đến nay người ta mới chỉ ứng dụng dạng thức nén có tổn thất thông tin của JPEG vì mã hoá không tổn thất của JPEG là khá phức tạp. Để việc nén ảnh có hiệu quả hơn, Ủy ban JPEG đã đưa ra một chuẩn nén ảnh mới là JPEG2000. JPEG2000 sử dụng biến đổi Wavelet và các phương pháp mã hoá đặc biệt để có được ảnh nén ưu việt hơn hẳn JPEG. JPEG2000 hiện vẫn đang tiếp tục được phát triển, nhưng phần I đã được tổ chức ISO chấp nhận là chuẩn nén ảnh quốc tế áp dụng cho ảnh tĩnh. Chuẩn nén ảnh JPEG2000 mà xương sống là biến đổi Wavelet với tính năng vượt trội so với JPEG chắc chắn sẽ được sử dụng trong các server nội dung để chuyển đổi định dạng ảnh trong mạng di động. Chính vì thế, mục đích của chương này không chỉ giới thiệu một chuẩn nén ảnh dựa trên biến đổi Wavelet phổ biến mà còn đưa ra một lựa chọn nhằm giải quyết toàn cục bài toán đặt ra ơ phần mở đầu. 4.2. Các tính năng của JPEG2000 JPEG2000 có nhiều chức năng đặc biệt hơn mọi chuẩn nén ảnh tĩnh khác như JPEG hay GIF. Dưới đây là các chức năng ưu việt của JPEG2000 so với các chuẩn nén ảnh tĩnh khác ¾ Cho chất lượng ảnh tốt nhất khi áp dụng nén ảnh tĩnh có tổn thất. ¾ Sử dụng được với truyền dẫn và hiển thị luỹ tiến về chất lượng, độ phân giải, các thành phần màu và có tính định vị không gian. ¾ Sử dụng cùng một cơ chế nén ảnh cho cả hai dạng thức nén. ¾ Truy nhập và giải nén tại mọi thời điểm trong khi nhận dữ liệu. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh ¾ Giải nén từng vùng trong ảnh mà không cần giải nén toàn bộ ảnh ¾ Có khả năng mã hoá ảnh với tỷ lệ nén theo từng vùng khác nhau ¾ Nén một lần nhưng có thể giải nén với nhiều cấp chất lượng tuỳ theo yêu cầu của người sử dụng Hiện tại, ISO và uỷ ban JPEG đã đưa ra khuyến nghị thay thế JPEG bằng JPEG2000. 4.3. Các bước thực hiện nén ảnh theo chuẩn JPEG2000 ¶nh m· ho¸ Xö lý tr−íc biÕn ®æi BiÕn ®æi thuËn liªn thµnh phÇn BiÕn ®æi thuËn riªng thµnh phÇn L−îng tö ho¸ M· ho¸ Gi¶i m· ho¸ Gi¶i l−îng tö ho¸ BiÕn ®æi ng−îc riªng thµnh phÇn BiÕn ®æi ng−îc liªn thµnh phÇn Xö lý sau biÕn ®æi ¶nh sau khi m· ho¸¶nh gèc ¶nh kh«i phôc (a) (b) Hình 4.1: Trình tự mã hoá (a) và giải mã JPEG2000 (b) 4.3.1. Xử lý trước biến đổi Do sử dụng biến đổi Wavelet, JPEG2000 cần có dữ liệu ảnh đầu vào ở dạng đối xứng qua 0. Xử lý trước biến đổi chính là giai đoạn đảm bảo dữ liệu đưa vào nén ảnh có dạng trên. Ở phía giải mã, giai đoạn xử lý sau biến đổi sẽ trả lại giá trị gốc ban đầu cho dữ liệu ảnh. 4.3.2. Biến đổi liên thành phần Giai đoạn này sẽ loại bỏ tính tương quan giữa các thành phần của ảnh. JPEG2000 sử dụng hai loại biến đổi liên thành phần là biến đổi màu thuận nghịch (Reversible Color Transform - RCT) và biến đổi màu không thuận nghịch (Irreversible Color Transform - ICT) trong đó biến đổi thuận nghịch làm việc với các giá trị nguyên, còn biến đổi không thuận nghịch làm việc với các giá trị thực. ICT và RCT chuyển dữ liệu ảnh từ không gian màu RGB sang YCrCb. RCT được áp dụng trong cả hai dạng thức nén có tổn thất và không tổn thất, còn ICT chỉ áp dụng cho nén có tổn thất. Công thức của biến đổi thuận và ngược của hai phép biến đổi Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh ICT và RCT cho ở phần phụ lục. Việc áp dụng các biến đổi này trước khi nén ảnh không nằm ngoài mục đích làm tăng hiệu quả nén. Các thành phần Cr, Cb có ảnh hưởng rất ít tới sự cảm nhận hình ảnh của mắt trong khi thành phần độ chói Y có ảnh hưởng rất lớn tới ảnh. Chúng ta có thể thấy rõ hơn điều này trên hình vẽ 4.3: Hình 4.2: Minh hoạ ảnh với RGB và YCrCb 4.3.3. Biến đổi riêng thành phần (biến đổi Wavelet) Biến đổi riêng thành phần được áp dụng trong JPEG2000 chính là biến đổi Wavelet. Để đảm bảo tính toàn vẹn thông tin cũng phải áp dụng các phép biến đổi thuận nghịch hoặc không thuận nghịch. Do phép biến đổi Wavelet không phải là một phép biến đổi trực giao như biến đổi DCT mà là một phép biến đổi băng con nên các thành phần sẽ được phân chia thành các băng tần số khác nhau và mỗi băng sẽ được mã hóa riêng rẽ. JPEG2000 áp dụng biến đổi Wavelet nguyên thuận nghịch 5/3 (IWT) và biến đổi thực không thuận nghịch Daubechies 9/7. Việc tính toán biến đổi trong JPEG2000 này sẽ được thực hiện theo phương pháp Lifting (Công thức cụ thể của phương pháp Lifting và biến đổi Wavelet trong JPEG2000 cho ở phần phụ lục). Sơ đồ của phương pháp Lifting 1D áp dụng trong JPEG2000 trên hình 4.3.Việc tính toán biến đổi Wavelet 2D suy ra từ biến đổi Wavelet 1D theo các phương pháp phân giải ảnh tuỳ chọn. Trong JPEG2000 có 3 phương pháp phân giải ảnh nhưng phương pháp được sử dụng nhiều nhất chính là phương pháp kim tự tháp. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Odd / Even Split U-P + + X[n] Xe[n] c[n] d[n]Xo[n] Ke Ko MergeP-U + + X[n] c[n] d[n] 1/Ke 1/Ko Hình 4.3: Phương pháp Lifting 1D dùng tính toán biến đổi Wavelet Do biến đổi Wavelet 5/3 là biến đổi thuận nghịch nên có thể áp dụng cho nén ảnh theo cả hai phương pháp, có tổn thất và không tổn thất trong khi biến đổi 9/7 chỉ áp dụng cho nén ảnh theo phương pháp có tổn thất thông tin. 4.3.4.Lượng tử hoá - Giải lượng tử hoá Các hệ số của phép biến đổi sẽ được tiến hành lượng tử hoá. Quá trình lượng tử hoá cho phép đạt tỷ lệ nén cao hơn bằng cách thể hiện các giá trị biến đổi với độ chính xác tương ứng cần thiết với mức chi tiết của ảnh cần nén. Các hệ số biến đổi sẽ được lượng tử hoá theo phép lượng tử hoá vô hướng. Các hàm lượng tử hoá khác nhau sẽ được áp dụng cho các băng con khác nhau và được thực theo biểu thức: ( ) ( ) ( ),, sgn ,U x yV x y U x y⎢ ⎥= ⎢ ⎥∆⎣ ⎦ (4.1) với ∆ là bước lượng tử, ( ),U x y là giá trị băng con đầu vào; ( ),V x y là giá trị sau lượng tử hoá. Trong dạng biến đổi nguyên, đặt bước lượng tử bằng 1.Với dạng biến đổi thực thì bước lượng tử sẽ được chọn tương ứng cho từng băng con riêng rẽ. Bước lượng tử của mỗi băng do đó phải có ở trong dòng bít truyền đi để phía thu có thể giải lượng tử cho ảnh. Công thức giải lượng tử hoá là: ( ) ( ) ( ), , sgn ,U x y V x y r V x y= + ∆⎡ ⎤⎣ ⎦ (4.2) Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh r là một tham số xác định dấu và làm tròn, các giá trị ( ) ( ), ; ,U x y V x y tương ứng là các giá trị khôi phục và giá trị lượng tử hoá nhận được. JPEG2000 không cho trước r tuy nhiên thường chọn 12r = . 4.3.5. Mã hoá và kết hợp dòng dữ liệu sau mã hoá JPEG2000 theo khuyến nghị của uỷ ban JPEG quốc tế có thể sử dụng nhiều phương pháp mã hoá khác nhau cũng như nhiều cách biến đổi Wavelet khác nhau để có thể thu được chất lượng ảnh tương ứng với ứng dụng cần xử lý. Điều này giúp cho JPEG2000 mềm dẻo hơn nhiều so với JPEG. Việc áp dụng các phương pháp mã hoá khác nhau cũng được mở rộng sang lĩnh vực nén ảnh động bằng biến đổi Wavelet. Trong thực tế các phương pháp mã hoá ảnh được áp dụng khi nén ảnh bằng biến đổi Wavelet cũng như JPEG2000 thì có hai phương pháp được coi là cơ sở và được áp dụng nhiều nhất: phương pháp SPIHT và phương pháp EZW. Hiện nay JPEG2000 vẫn được áp dụng mã hoá bằng hai phương pháp này và một phương pháp phát triển từ hai phương pháp này là phương pháp mã hoá mặt phẳng bít. Vì thế ở đây chúng ta sẽ xem xét hai phương pháp này. Việc kết hợp dòng dữ liệu sau mã hoá của JPEG2000 thực chất là để thực hiện các tính năng đặc biệt của JPEG2000 như tính năng ROI v.v... 4.3.6. Phương pháp mã hoá SPIHT Có thể thấy rằng dù áp dụng biến đổi Wavelet nào hay cùng với nó là một phép phân giải ảnh nào thì trong các băng con có số thứ tự thấp cũng là những thành phần tần số cao (mang thông tin chi tiết của ảnh) trong khi những băng con có số thứ tự cao hơn thì sẽ chứa những thành phần tần số thấp (mang thông tin chính về ảnh). Điều đó nghĩa là các hệ số chi tiết sẽ giảm dần từ băng con mức thấp (HH1 chẳng hạn) (ứng với thành phần tần số cao) xuống băng con mức cao (ứng với thành phần tần số thấp) và có tính tương tự về không gian giữa các băng con, ví dụ như Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh một đường biên của hình vẽ trong ảnh sẽ tồn tại ở cùng một vị trí trên các băng con đó (tương ứng với mức độ phân giải của băng con ấy). Điều này đã dẫn tới sự ra đời của phương pháp SPIHT (Set partitioning in hierarchical trees - phương pháp mã hoá phân cấp theo phân vùng). Phương pháp SPIHT được thiết kế tối ưu cho truyền dẫn luỹ tiến. Điều này có nghĩa là tại mọi thời điểm trong quá trình giải nén ảnh theo phương pháp mã hoá này thì chất lượng ảnh hiển thị tại thời điểm ấy là tốt nhất có thể đạt được với một số lượng bít đưa vào giải mã tính cho tới thời điểm ấy. Ngoài ra, phương pháp này sử dụng kỹ thuật embedded coding; điều đó có nghĩa là một ảnh sau nén với kích cỡ (lưu trữ) lớn (tỷ lệ nén thấp) sẽ chứa chính dữ liệu sau nén của ảnh có kích cỡ (lưu trữ) nhỏ (tỷ lệ nén cao). Bộ mã hoá chỉ cần nén một lần nhưng có thể giải nén ra nhiều mức chất lượng khác nhau. Giả sử gọi các pixel trong một ảnh p cần mã hoá là pi, j. Áp dụng một phép biến đổi Wavelet T nào đó cho các pixel trong ảnh để tạo ra các hệ số của phép biến đổi Wavelet là ci, j. Các hệ số này tạo ra một ảnh biến đổi là C. Phép biến đổi này được viết dưới dạng toán tử như sau: C=T(p). Trong phương pháp truyền dẫn luỹ tiến với ảnh thì bộ mã hoá sẽ bắt đầu quá trình khôi phục (giải nén) ảnh bằng cách đặt các giá trị của ảnh khôi phục từ các hệ số biến đổi là cˆ . Sử dụng các giá trị giải mã của các hệ số biến đổi để tạo ra một ảnh khôi phục (vẫn chưa áp dụng biến đổi ngược Wavelet) là cˆ và sau đó áp dụng biến đổi ngược Wavelet để tạo ra ảnh cuối cùng là pˆ . Chúng ta có thể viết dưới dạng toán tử như sau: ( )1ˆ ˆp T c−= . Nguyên tắc quan trọng của phương pháp truyền dẫn ảnh theo kiểu luỹ tiến chính là phương pháp này luôn truyền đi các giá trị mang thông tin quan trọng hơn của ảnh đi trước. Sở dĩ làm như vậy là do các thông tin đó chính là các thông tin sẽ làm giảm thiểu nhiều nhất độ méo dạng của ảnh (sự sai khác giữa ảnh gốc và ảnh khôi phục). Đây chính là lý do tại sao phương pháp SPIHT luôn truyền đi Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh các hệ số lớn trước và cũng là một nguyên tắc quan trọng của phương pháp này. Một nguyên tắc nữa là các bít có trọng số lớn bao giờ cũng mang thông tin quan trọng nhất trong dữ liệu nhị phân. Phương pháp SPIHT sử dụng cả hai nguyên tắc này; nó sắp xếp các hệ số biến đổi và truyền đi các bít có trọng số lớn nhất. Quá trình giải mã có thể dừng lại ở bất kỳ một bước nào ứng với giá trị ảnh cần mã hoá yêu cầu. Đây chính là cách mà phương pháp mã hoá SPIHT làm tổn thất thông tin. 4.3.7. Phương pháp mã hoá EZW Phương pháp mã hoá EZW (Embedded Zerotree Wavelet Encoder) cũng dựa trên cơ sở phép mã hoá luỹ tiến (progressive coding) giống như phương pháp mã hoá SPIHT. Phương pháp này chủ yếu dựa trên khái niệm về cây zero (zerotree). Về cơ bản, thuật toán này dựa trên hai nguyên tắc như đã trình bày ở phần phương pháp mã hoá SPIHT. Sau đây chúng ta sẽ xem xét các khái niệm cơ bản của thuật toán: Cây tứ phân: Sau khi áp dụng biến đổi Wavelet ứng với các mức phân giải khác nhau chúng ta có thể biểu diễn các hệ số biến đổi dưới dạng một cây. Ta thấy rằng với cây biểu diễn này cứ mỗi nút cha thì có 4 nút con. Sở dĩ có được điều này là do quá trình biến đổi Wavelet ở các tỷ lệ khác nhau. Ta gọi đây là các cây tứ phân (quadtree). Sơ đồ cây tứ phân được minh hoạ ở hình 4.5. Level 3 Level 2 Level 1 LL LH1 HL1 HH1 (a) (b) Hình 4.4: Minh hoạ cây tứ phân (a) và sự phân mức (b) Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Cây zero (zerotree): Cây zero là một cây tứ phân, trong đó tất cả các nút của nó đều nhỏ hơn nút gốc. Một cây như vậy khi mã hoá sẽ được mã hoá bằng một đối tượng duy nhất và khi giải mã thì chúng ta cho tất cả các giá trị bằng không. Ngoài ra để có thể mã hoá được các hệ số Wavelet trong trường hợp này, giá trị của nút gốc phải nhỏ hơn giá trị ngưỡng đang được xem xét ứng với hệ số Wavelet đó Sau khi có đủ các khái niệm cần thiết về cây tứ phân và cây zero, chúng ta có thể trình bày nguyên lý hoạt động của thuật toán. Thuật toán sẽ mã hoá các hệ số theo thứ tự giảm dần. Chúng ta sẽ dùng một giá trị gọi là ngưỡng (threshold) và sử dụng ngưỡng này để tiến hành mã hoá các hệ số biến đổi. Các hệ số được mã hoá theo thứ tự từ vùng tần số thấp đến vùng tần số cao. Và chỉ những hệ số có giá trị tuyệt đối lớn hơn hoặc bằng ngưỡng thì mới được mã hoá. Tiếp theo giảm ngưỡng và tiếp tục làm như vậy cho tới khi ngưỡng đạt tới một giá trị nhỏ hơn giá trị của hệ số nhỏ nhất. Cách giảm giá trị ngưỡng ở đây thực hiện tương đối đặc biệt, giá trị của ngưỡng giảm xuống một nửa so với trước đó. Bộ giải mã phải biết các mức ngưỡng này thì mới có thể giải mã ảnh thành công. Nhưng khi ta đi từ nút cha đến nút con trong cây tứ phân thì nó vẫn có 3 nút con. Vậy ta phải đi theo nhánh có nút con nào trước. Hay nói một cách đầy đủ hơn ta di chuyển từ hệ số này đến hệ số khác theo thứ tự như thế nào. Có nhiều cách di chuyển khác nhau, tuy nhiên hai cách di chuyển trên hình 4.6 được sử dụng nhiều nhất. Raster Scan Morton Scan Hình 4.5: Hai cách sắp xếp thứ tự các hệ số biến đổi Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Việc sắp xếp này còn phải được quy ước thống nhất giữa quá trình mã hoá và quá trình giải mã để việc giải mã ảnh được thành công. Trên đây chỉ là nguyên lý cơ bản của phương pháp mã hoá EZW. Chi tiết về thuật toán mã hoá có thể xem ở phần chương trình. Hiện nay phương pháp mã hoá này được áp dụng ngày càng nhiều nén ảnh động. Phương pháp này cho tỉ lệ nén và độ tin cậy giải mã cao. Ngoài ra phương pháp EZW rất dễ triển khai trên máy tính bởi phương pháp này không yêu cầu việc lập trình quá phức tạp. 4.4. So sánh chuẩn JPEG2000 với JPEG và các chuẩn nén ảnh tĩnh khác Một tính năng quan trọng và là ưu điểm rõ nét nhất của JPEG2000 so với JPEG cũng như các chuẩn nén ảnh khác như MPEG 4 VTC hay JPEG - LS v. v.... là JPEG2000 đưa ra cả hai kỹ thuật nén có tổn thất và không tổn thất theo cùng một cơ chế mã hoá nghĩa là JPEG2000 thực hiện tất cả các dạng thức của JPEG chỉ bằng một cơ chế mã hoá duy nhất. Nếu xét về sự tồn tại của hai kỹ thuật này thì JPEG cũng có khả năng nén ảnh có tổn thất và không tổn thất thông tin. Tuy nhiên với JPEG thì cơ chế mã hoá với hai dạng này là khác nhau và rất khó để sử dụng cả hai dạng này cùng lúc cho cùng một ứng dụng. Do đó, có thể thấy rằng JPEG có tính mềm dẻo hơn bất kỳ chuẩn nén ảnh tĩnh nào trước đây. Hơn thế, chúng ta đã thấy rằng tất cả các phương pháp thiết kế cho chuẩn JPEG2000 đều ưu việt và có nhiều tính năng hơn so với JPEG; ngoài ra những thống kê về thực tế cho thấy với cùng một tỷ lệ nén và một loại ảnh thì ảnh được nén bởi JPEG2000 hầu như luôn có chất lượng tốt hơn so với JPEG. Chúng ta xem xét hai ảnh trên hình 4.7 để thấy rõ điều này, ảnh bên trái được nén theo JPEG còn ảnh bên phải được nén theo JPEG2000 Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh JPEG JPEG2000 JPEG JPEG2000 Hình 4.6: So sánh JPEG và JPEG2000 Tính năng ưu việt thứ hai của JPEG2000 so với JPEG chính là trong dạng thức nén có tổn thất thông tin, JPEG2000 có thể đưa ra tỷ lệ nén cao hơn nhiều so với JPEG. Các phần mềm nén ảnh JPEG hiện tại (kể cả Photoshop) cũng chỉ thiết kế để có thể nén được tới tỷ lệ 40:1 nhưng với JPEG2000 thì tỷ lệ nén có thể lên tới 200:1. Theo công thức tính PSNR trong đơn vị dB, chúng ta có: (b là số bít dùng biểu diễn một pixel trên ảnh gốc) ⎟⎠ ⎞⎜⎝ ⎛ −−= 12 RMSElog20)dB(PSNR b Với hai ảnh ở hình 4.6, sự so sánh về tham số PSNR cho trên bảng 4.1. Để có thể so sánh dễ dàng hơn, ta xét ảnh được nén với các tỷ lệ khác nhau (đo lường bởi hệ số bít/pixel hay bpp). Tất cả các số liệu trên bảng đều cho thấy JPEG2000 nén ảnh tốt hơn là JPEG; hơn thế hệ số PSNR mà chúng ta xét trong bảng được đo trong hệ đơn vị logarit. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Bit per pixel 0. 125 0. 50 2.00 Ảnh 1 theo JPEG 24.42 31.17 35. 15 Ảnh 1 theo JPEG2000 28. 12 32.95 37. 35 Ảnh 2 theo JPEG 22.6 28. 92 35. 99 Ảnh 2 theo JPEG2000 24.85 31.13 38. 80 Bảng 4.1: So sánh JPEG và JPEG2000 Tính năng ưu việt thứ 3 của JPEG2000 so với JPEG là chuẩn nén ảnh này có thể hiển thị được các ảnh với độ phân giải và kích thước khác nhau từ cùng một ảnh nén. Với JPEG thì điều này là không thể thực hiện được. Sở dĩ có điều này là do JPEG2000 sử dụng kỹ thuật phân giải ảnh và mã hoá đính kèm mà chúng ta đã nói tới ở phần mã hoá ảnh theo JPEG2000. Tính năng này là một lợi thế đặc biệt quan trọng của JPEG2000, trong khi JPEG cũng như các chuẩn nén ảnh tĩnh trước đây phải nén nhiều lần để thu được chất lượng với từng lần nén khác nhau thì với JPEG2000 ta chỉ cần nén một lần còn chất lượng ảnh thì sẽ được quyết định tuỳ theo người sử dụng trong quá trình giải nén ảnh theo JPEG2000. Một tính năng ưu việt nữa của JPEG2000 là tính năng mã hoá ảnh quan trọng theo vùng (ROI - Region of Interest) mà chúng ta đã đề cập trong phần mã hoá ảnh theo JPEG2000. Chất lượng của toàn bộ ảnh cũng được thấy rõ trên hình 4.7. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 4.7: Minh hoạ tính năng ROI Như chúng ta thấy trên hình 4.7, chất lượng của vùng ảnh được lựa chọn tăng cao hơn khi vùng đó được áp dụng phương pháp nén ảnh ROI. JPEG2000 còn có một khả năng đặc biệt ưu việt hơn so với JPEG, đó chính là khả năng vượt trội trong khôi phục lỗi. Đó là khi một ảnh được truyền trên mạng viễn thông thì thông tin có thể bị nhiễu; với các chuẩn nén ảnh như JPEG thì nhiễu này sẽ được thu vào và hiển thị, tuy nhiên với JPEG2000, do đặc trưng của phép mã hoá có thể chống lỗi, JPEG2000 có thể giảm thiểu các lỗi này tới mức hầu như không có. Sau khi xem xét các tính năng vượt trội của JPEG2000 so với JPEG (chuẩn nén ảnh thông dụng nhất hiện nay) chúng ta so sánh chức năng của JPEG2000 với một số chuẩn nén ảnh như là JPEG - LS; PNG; MPEG 4 VTC qua bảng 4.2 (Dấu + biểu thị chuẩn đó có chức năng tương ứng, số dấu + càng nhiều thì chuẩn đó thực hiện chức năng tương ứng càng tốt) dấu - biểu thị chuẩn tương ứng không hỗ trợ tính năng đó) Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh JPEG2000 JPEG - LS JPEG MPEG -4 VTC PNG Khả năng nén ảnh không tổn thất +++ ++++ + - +++ Khả năng nén ảnh có tổn thất +++++ + +++ ++++ - Khả năng luỹ tiến trong khôi phục ảnh +++++ - ++ +++ + Kỹ thuật mã hoá theo vùng ROI +++ - - + - Khả năng tương tác với các vật thể có hình dạng bất kỳ - - - ++ - Khả năng truy nhập ngẫu nhiên dòng bít của ảnh nén ++ - - - - Tính đơn giản ++ +++++ +++++ + +++ Khả năng khôi phục lỗi +++ ++ ++ +++ + Khả năng thay đổi tỷ lệ nén +++ - - + - Tính mềm dẻo (khả năng nén nhiều loại ảnh khác nhau) +++ +++ ++ ++ +++ Bảng 4.2: So sánh tính năng của JPEG2000 với các chuẩn nén ảnh tĩnh khác Từ bảng trên chúng ta có thể thấy các tính năng vượt trội và khả năng ưu việt của JPEG2000 so với các chuẩn nén ảnh tĩnh trước đây. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh CHƯƠNG 5:ỨNG DỤNG WAVELET TRONG CÁC DỊCH VỤ DỮ LIỆU ĐA PHƯƠNG TIỆN TRONG THÔNG TIN DI ĐỘNG 5.1. Nén ảnh bằng Wavelet Trong các chương trước chúng ta đã thấy được ưu điểm của Wavelet trong ứng dụng nén ảnh tĩnh. Chương này xin đưa ra một giải pháp đó là vừa sử dụng biến đổi Wavelet để khai thác khả năng nén cao, chất lượng hình ảnh đảm bảo (kỹ thuật nén ảnh bằng Wavelet thông thường) mà vẫn phù hợp với môi trường thông tin di động có băng thông hẹp, tốc độ bít thấp và thường xuyên bị nhiễu kênh, hiệu ứng fading. Một cách tiếp cận đáp ứng được các yêu cầu trên đó là: kỹ thuật nén ảnh bằng Wavelet hiệu năng với hai đặc tính quan trọng trong thuật toán: (i) giảm thiểu năng lượng tính toán để thực hiện nén ảnh và (ii) giảm thiểu năng lượng khi truyền thông cho các ứng dụng đa phương tiện trong mạng di động mà vẫn đảm bảo chất lượng của ảnh. Chi tiết của kỹ thuật sẽ trình bầy ở phần dưới đây. 5.2.1. Sơ đồ khối tổng quát Hình 5.1. Sơ đồ khối quá trình nén ảnh bằng Wavelet Hình 5.1 chỉ ra sơ đồ khái quát quá trình nén ảnh (mã hoá nguồn). Quá trình đó như sau: ảnh mẫu được đưa qua một phép biến đổi để tạo thành tập hệ số biến đổi. Các hệ số này tiếp tục được lượng tử hoá (chia cho các giá trị cố định cho trước) để giảm dung lượng dữ liệu. Đầu ra của Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh bước này là một luồng các số nguyên mà mỗi một trong số đó tương ứng với một chỉ số nhị phân được lượng tử hoá. Bước cuối cùng là mã hoá: các luồng dữ liệu được chuyển thành chuỗi các từ mã nhị phân (binary symbol) theo cách: các từ mã nhị phân có độ dài ngắn mã hoá cho các số nguyên có xác suất xuất hiện cao. Điều này làm giảm số bít cần truyền. Các nguyên lý mã hoá như vậy là: Huffman [4] và RLC (mã chạy dài) [4]. Có nhiều thuật toán sử dụng cho nén ảnh như: dựa theo phép biến đổi, lượng tự hoá véctơ hoặc mã hoá băng con. Việc lựa chọn thuật toán trong truyền thông đa phương tiện di động không chỉ phụ thuộc vào tỉ số nén đạt được, chất lượng ảnh khôi phục mà còn liên quan đến năng lượng tiêu hao cũng như khả năng trống lại lỗi bít cao hơn. Gần đây nhóm JPEG đã phát triển chuẩn nén ảnh dựa trên biến đổi Wavelet gọi là JPEG2000 với nhiều ưu điểm. Tuy nhiên thống kê cho thấy bước biến đổi Wavelet trong quá trình nén tiêu tốn hơn 60% thời gian CPU. Như vậy nếu tối ưu các đặc điểm của thuật toán ở bước biến đổi thì năng lượng và hiệu suất nén có thể được cải thiện đáng kể. Do đó ta tập trung vào tối ưu năng lượng tiêu hao ở bước biến đổi. 5.1.2. Biến đổi Wavelet Phép biến đổi Wavelet thuận sử dụng sự phân ly 1D (một chiều) để chuyển tập các mẫu 1D thành hai băng: băng con thông thấp (Li) và băng con thông cao (Hi). Băng Li là phiên bản có độ phân giải thấp của ảnh gốc được lấy mẫu xuống (downsampled), băng Hi biểu thị thông tin dư thừa của ảnh gốc (chỉ cần thiết khi cần khôi phục hoàn toàn ảnh gốc từ băng thông thấp). Quá trình phân ly băng con 2D chỉ là sự mở rộng quá trình phân ly băng con 1D. Toàn bộ quá trình chính là sự thực hiện quá trình phân ly 1D hai lần: đầu tiên theo hàng, rồi theo cột. Theo cách này, băng con thông thấp Li tạo thành khi phân ly theo hàng lại tiếp tục được phân ly theo cột tạo thành băng con LLi và LHi. Tương tự như vậy, băng con Hi tiếp tục được phân ly thành HLi và HHi. Sau mức biến đổi đầu tiên, ảnh Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh có thể tiếp tục được phân ly bằng cách áp dụng quá trình phân ly 2D cho băng con LLi. Như vậy ảnh có thể được biến đổi ở nhiều mức. Hình 5.2 dưới đây minh hoạ quá trình phân ly ảnh 3 mức. Hình 5.2. (a) Biến đổi Wavelet 2D mức 3 và (b) Minh hoạ bằng ảnh “CASTLE” 5.1.3. Tính toán năng lượng tiêu hao Để thực hiện biến đổi Wavelet cần chọn một bộ lọc cho nó. Ở đây ta chọn bộ lọc có cặp Daubechies 5-tap / 3-tap do những ưu điểm sau của nó: • Kết quả sau bộ lọc Wavelet có chứa thông tin điểm ảnh lân cận và như thế loại bỏ được hiệu ứng khối mà biến đổi DCT gặp phải • Có tính chất đối xứng và định vị cho phép dễ dàng phát hiện đường viền, tính toán nhanh, ảnh nén có chất lượng cao. • Dễ dàng thực hiện bằng phần cứng vì nó chỉ gồm các bộ cộng và bộ dịch nhị phân (không phải là các bộ ghép kênh và bộ chia). (thực tế có thể chọn nhiều cặp bộ lọc khác nhau cho biến đổi Wavelet, lựa chọn cặp Daubechies 5-tap/ 3-tap ở mục này và các mục sau đều mang tính chất cục bộ, kết quả cuối cùng vẫn không mất tính tổng quan) Phương trình của bộ lọc Daubechies 5-tap/3-tap là: ⎥⎦ ⎤⎢⎣ ⎡ +−++−=+ ⎥⎦ ⎤⎢⎣ ⎡ ++−+++−+−−= 2 ]22[]12[2]2[]12[ 4 2]22[]12[2]2[6]12[2]22[]2[ nxnxnxnH nxnxnxnxnxnL (5.1) Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Để xác định hiệu năng của mỗi thuật toán, chúng ta sử dụng một ma trận không phụ thuộc vào việc thực hiện thuật toán. Chúng ta phân tích hiệu năng của nó bằng cách xác định số lần các phép toán cơ bản được thực hiện khi đầu vào cho trước, tiếp đó xác định định lượng các hoạt động chuyển mạch và đó chính là năng lương tiêu hao. Lấy ví dụ, trong phép phân ly Wavelet thuận sử dụng ở bộ lọc trên, cần 8 phép toán cộng - A(Add) và dịch - S(Shift) để chuyển những điểm ảnh mẫu thành một hệ số thông thấp. Tương tự như vậy, sự phân ly thông cao cần 2 phép toán dịch và 4 phép toán cộng. Chúng ta lập mô hình tiêu hao năng lượng của sự phân ly thông thấp/cao bằng cách đếm số các phép toán và xem chúng như là tải tính toán (computational load). Như vậy có 8*S (phép dịch) + 8*A (phép cộng) là tải tính toán cần cho một điểm ảnh trong quá trình phân ly thông thấp và 2S + 4A phép toán cho thông cao. Với một ảnh đầu vào cho trước kích thước M x N và quá trình phân ly được áp dụng với L mức biến đổi, khi đó chúng ta có thể đánh giá được tổng tải tính toán như sau: Giả sử trước tiên chúng ta áp dụng quá trình phân ly theo chiều ngang. Nhưng do tất cả các điểm ảnh ở vị trí chẵn được phân ly thành các hệ số thông thấp và các điểm ảnh ở vị trí lẻ được phân ly thành các hệ số thông cao, tổng tải tính toán trong quá trình phân ly chiều ngang sẽ là 1/2MN(10S+12A). Lượng tải tính toán trong quá trình phân ly theo chiều dọc cũng dễ nhận ra. Do kích thước của ảnh giảm theo hệ số 4 sau mỗi mức biến đổi, tổng tải tính toán có thê được biểu diễn bằng công thức sau: Tải tính toán với biến đổi Wavelet thường – CW: ∑ = − − − +≤− −+=+= K l l L l SAMNSAMNSAMNC 1 1W )1012(3 4 41 41)1012( 4 1)1012( (5.2) Ngoài các phép toán số học, bước biến đổi cũng bao gồm một số lượng lớn các lần truy nhập bộ nhớ. Do vậy năng lượng tiêu hao trong các Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh lần truyền dữ liệu nội và ngoại hệ thống có thể đáng kể, chúng ta ước lượng tải truy nhập dữ liệu (data-acces load) bằng cách đếm tổng số các lần truy nhập bộ nhớ trong quá trình thực hiện biến đổi Wavelet. Tại một mức biến đổi, mỗi điểm ảnh sẽ được đọc hai lần và được ghi hai lần. Do vậy, với cùng một điều kiền cũng như cùng phương pháp đánh giá như trên, tổng tải truy nhập dữ liệu rút ra bằng số các toán tử đọc và ghi” Tải truy nhập dữ liệu với biến đổi Wavelet thường: ∑ = − ≤== L l lREAD MNCC 1 1WRITE_WW_ 3 8 4 12 (5.3) Năng lượng tính toán tổng được tính bằng tổng trọng số của tải tính toán và tải truy nhập dữ liệu. Từ kết quả tiến hành thực nghiệm, ta thấy rằng thực hiện các phép cộng tiêu tốn năng lượng gấp đôi so với thực hiện phép dịch và năng lượng tiêu tốn cho tải truy nhập dữ liệu gấp 2.7 lần tải tính toán. Chúng ta cũng ước lượng năng lượng truyền thông bằng C*R, trong đó C là kích thước của ảnh nén (tính bằng bít) và R là tổn hao năng lượng để truyền một bít bằng bộ phát RF. Như vậy ta đã phân tích biên độ và nguồn gốc của tổn hao năng lượng trong biến đổi Wavelet, tiếp theo chúng ta sẽ trình bầy các kỹ thuật để tối thiểu năng lượng tiêu hao cũng như năng lượng truyền thông yêu cầu cho việc nén ảnh bằng Wavelet và truyền vô tuyến. 5.2. Thuật toán nén ảnh bằng Wavelet hiệu năng - EEW Trong phần này, chúng ta trình bầy thuật toán EEW (Effective Energy Wavelet) - một thuật toán biến đổi bằng Wavelet mà mục đích là tiết kiệm năng lượng trong khi chất lượng ảnh chỉ bị ảnh hưởng ít nhất. EEW khai thác phân bố số học của các hệ số thông cao để khéo léo loại bỏ một số lượng lớn các mẫu trong quá trình nén ảnh. Hình 5.3 minh hoạ phân bố các hệ số thông cao (high-pass coefficients) sau khi áp dụng biến đổi Wavelet hai mức cho ảnh mẫu Lena kích thước 512 x 512. Chúng ta cũng quan sát thấy là các hệ số thông cao thường được biểu Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh diễn bằng các giá trị số nguyên nhỏ. Lấy ví dụ, 80% các hệ số thông cao ở mức 1 (level 1) đều không vượt quá 5. Chính bởi sự phân bố số học của các hệ số thông cao và ảnh hưởng của bước lượng tử hoá đối với các hệ số có giá trị nhỏ, chúng ta có thể làm tròn các hệ số thông cao bằng 0 (và do đó loại bỏ được phép toán liên quan đến chúng) và do đó suy hao chất lượng ảnh chỉ ở mức nhỏ. Cách tiếp cận này có hai ưu điểm chính. Thứ nhất, bởi vì các hệ số thông cao không cần phải tính toán, EEW làm giảm năng lượng tính toán tiêu hao trong quá trình nén ảnh bằng Wavelet bằng cách giảm số lượng các phép toán đã được thực hiện. Thứ hai, bởi vì bộ mã hoá và giải mả là kỹ thuật làm tròn (ước lượng), vì thế không có thông tin yêu cầu được truyền qua kênh vô tuyên, do đó giảm được năng lượng tiêu hao cần có. Hình 5.3. Phân bố số học các hệ số thông cao sau phép biến đổi Wavelet mức 2 Sử dụng kỹ thuật ước lượng ở trên chúng ta đã xây dựng được thuật toán gồm hai kỹ thuật hạn chế tiêu hao năng lượng: hạn chế tính toán và truyền thông cho các hệ số thông cao: Kỹ thuật đầu tiên là loại bỏ băng con ít ý nghĩa nhất. Trong số 4 băng con ta thấy băng con đường chéo (HHi) là ít ý nghĩa nhất (xem hình 5.2), và là ứng cử viên sáng giá để loại bỏ ở trong bước biến đổi Wavelet. Chúng ta gọi kỹ thuật này là kỹ thuật “loại bỏ HH”. Ở kỹ thuật thứ 2, thì chỉ những băng con có ý nghĩa nhất (chứa thông tin độ phân giải thấp, LLi) được giữ lại còn các băng Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh thông cao khác (LHi, HLi và HHi) đều được loại bỏ. Chúng ta gọi kỹ thuật này là kỹ thuật “loại bỏ H*” (tất cả các băng con thông cao đều bị loại bỏ trong bước biến đổi). Tiếp theo chúng ta sẽ trình bầy chi tiết về các kỹ thuật loại bỏ HH và H* và so sánh hiệu năng của hai kỹ thuật này với thuật toán sử dụng Wavelet nguyên bản (được xem là thuật toán biến đổi Wavelet không loại bỏ thông tin (đã được đề cập trong mục 5.2.2 và 5.2.3). 5.2.1. Hiệu năng của các kỹ thuật loại bỏ Để thực hiện các kỹ thuật loại bỏ HH và H* (EEW), chúng ta thay đổi phép biến đổi Wavelet như mô tả trong hình 5.4. Như đã giải thích ở mục 5.2.2, trong quá trình biến đổi Wavelet, mỗi ảnh đầu vào được thực hiện phép biến đổi theo hàng rồi đến cột và phân ly ảnh thành bốn băng con (LL, LH, HL, HH). Tuy nhiên, để thực hiện kỹ thuật loại bỏ HH, thì sau khi thực hiện biến đổi theo hàng, các hệ số thông cao chỉ được đưa vào bộ lọc thông thấp mà không được đưa vào bộ lọc thông cao trong bước biến đổi theo cột tiếp theo (trong hình 5.4 bên dưới <HH Elimination>, ký hiệu là những hình có bóng sáng). Cách làm này đã loại bỏ băng con đường chéo HH. Còn để thực hiện kỹ thuật loại bỏ H*, ảnh đầu vào được xử lý chỉ cho qua bộ lọc thông thấp trong cả quá trình thực hiện biến đổi hàng và cột. Và như vậy chúng ta cũng loại bỏ được tất cả các bước phân ly thông cao trong quá trình biến đổi. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 5.4: Dữ liệu sau phép biến đổi Wavelet với hai kỹ thuật loại bỏ HH và H* Để ước lượng hiệu năng của các kỹ thuật EEW ở trên, chúng ta sẽ tiến hành tính tải tính toán và tải truy nhập dữ liệu theo phương pháp đã đề cập trong mục 5.2.3. Chúng ta giả thiết rằng, các kỹ thuật tính toán chỉ được áp dụng ở E mức biến đổi đầu tiên trong tổng số L mức. Lý do là bởi vì ưu điểm của các hệ số thông cao thực hiện loại bỏ càng ý nghĩa ở các mức biến đổi thấp. Trong kỹ thuật loại bỏ HH, tải tính toán trong quá trình thực hiện biến đổi theo hàng bằng với thuật toán Wavelet thường. Tuy nhiên, trong quá trình thực hiện biến đổi theo cột băng con thông cao là kết quả từ phép biến đổi theo dòng trước, băng con HH không được tính. Kết quả trong mục 5.2.3 chỉ ra rằng làm như vậy có thể tiết kiệm 1/4MN(4A+2S) các phép toán cho tải tính toán ( nghĩa là tiết kiệm được 7.4% so với thuật toán Wavelet thường). Và vì thế, tổng tải tính toán có thể được tính như sau: 1 1 1 1 (22 19 ) 1 1(12 10 ) 2 4 4 E L HH l l l l E MN A SC MN A S− − = = + += + +∑ ∑ (5.4) Bởi vì băng con thông cao sau phép biến đổi theo hàng vần cần để tính băng con HL trong phép biến đổi theo cột nên chúng ta có thể tiết kiệm số lần “đọc” trong kỹ thuật loại bỏ HH. Tuy nhiên, chúng ta chỉ tiết Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh kiệm được 1/4 các lần “ghi” (tiết kiệm 25%) trong quá trình thực hiện phép biến đổi theo cột. Do vậy kết quả băng con HH được gán trước bằng 0 trước khi quá trình biến đổi được thực hiện. Do vậy, tổng tải truy cập dữ liệu sẽ được tính: ∑ ∑ = += −− +== E l L El llHHWRITEWREADHHREAD MNMNCCC 1 1 11___ 4 12 4 1 4 7, (5.5) Kỹ thuật loại bỏ H* cho kết quả đáng kể trong việc tiết kiệm năng lượng tính toán bởi đã có 3 trong tổng số 4 băng con được loại bỏ. Phần tới chúng ta sẽ tập trung mô tả và minh hoạ các kỹ thuật trên 5.3.2. Các kết quả thực nghiệm Phần này chúng ta sẽ tiến hành thực nghiệm để xem xết kết quả tiết kiệm năng lượng tính toán từ việc áp dụng kỹ thuật loại bỏ trên. Thực chất là chúng ta sẽ tập trung vào khả năng tiết kiệm năng lượng tính toán và truyền thông sử dụng các kỹ thuật trên đồng thời cũng xét ảnh hưởng của chúng đến chất lượng ảnh. 5.3.2.1. Ảnh hưởng đến năng lượng tính toán và chất lượng ảnh 5.3.2.2. Ảnh hưởng đến năng lượng truyền thông và chất lượng ảnh 5.4. Các tham số nén ảnh bằng Wavelet 5.4.1. Thay đổi mức biến đổi Wavelet 5.4.2. Thay đổi các mức lượng tử 5.5. Truyền ảnh trên mạng 5.5.1. Phương pháp lựa chọn tham số động 5.5.2. Kết quả thực nghiệm Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh KẾT LUẬN Kết quả đạt được và ứng dụng của luận văn Luận văn đã trình bầy các kỹ thuật nén ảnh, các nguyên lý nén và một số khái niệm quan trọng trong lĩnh vực xử lý ảnh. Tác giả cũng đã tập trung trình bầy các nguyên lý nén có tổn hao điển hình đang là các kỹ thuật cốt lõi của các chuẩn nén (JPEG, JPEG2000, MPEG,…). Với mục đích của luận văn là nghiên cứu về kỹ thuật nén ảnh sử dụng biến đổi Wavelet từ đó áp dụng trong các dữ liệu đa phương tiện di động, nên tác giả cũng đã đi sâu nghiên cứu cơ sở lý thuyết của phép biến đổi này đồng thời cũng giới thiệu chuẩn nén ảnh JPEG2000 – là chuẩn nén phổ biến dựa trên biến đổi Wavelet. Hơn nữa chuẩn này cũng sẽ là một lựa chọn hiệu quả bổ sung chuẩn JPEG đang được sử dụng trong các server chuyển đổi định dạng ảnh. Luận văn cũng đã giới thiệu một thuật toán nén ảnh bằng Wavelet hiệu năng không chỉ cho hiệu suất nén ảnh cao, chất lượng ảnh truyền đảm bảo do ưu điểm của Wavelet, mà trên hết còn tiết kiệm năng lượng xử lý, năng lượng truyền thông cho ảnh trên mạng. Điều này hứa hẹn có thể xây dựng một bộ mã hoá ảnh tiết kiệm năng lượng xử lý, thời gian truyền mà vẫn phù hợp với điều kiện băng thông thấp, ràng buộc về chất lượng dữ liệu trong các mạng thông tin di động. Hướng phát triển nghiên cứu Tác giả xin đề cập một số hướng nghiên cứu trong tương lai: • Luận văn mới đưa ra ứng dụng Wavelet cho ảnh tĩnh trong dữ liệu đa phương tiện di động. Những ưu điểm của Wavelet khiến nó có thể áp dụng cho âm thanh, video, khử nhiễu, bảo mật,… • Có rất nhiều họ Wavelet khả dụng, có thể lựa chọn nhiều cặp Wavelet khác mà không nhất thiếtchỉ lựa chọn cặp 5-tap/3-tap. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh • Nghiên cứu khả năng ứng dụng chuẩn JPEG2000 cho dữ liệu đa phương tiện trong thông tin di động nhằm tương thích dữ liệu hình ảnh giữa các thuê bao, khữ nhiễu, khôi phục lỗi mất gói tin ảnh,… • Nghiên cứu thêm về các giải thuật SPIHT, EWZ ứng dụng trong thông tin di động. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh PHỤ LỤC Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh TÀI LIỆU THAM KHẢO 1. Martin Vetterli - Jelena Kovacevic - “Wavelet and Subband Coding”(1995) 2. Satish Kumar - “An Introduction to Image Compression” (10/2001) 3. Jin Li - “Image Compression - the Mechanics of the JPEG2000”(2001) 4. David Salomon - “Data Compression - The Complete Reference” (2001) 5. Lương Mạnh Bá - TS. Nguyễn Thanh Thuỷ - “Nhập môn xử lý ảnh số”(1999) 6. Nguyễn Kim Sách – “Xử lý ảnh và video số” – NXB KHKT, 1997 7. Đỗ Hoàng Tiến, Vũ Đức Lý – “Truyền hình số” – NXB KHKT, 2000 8. PGS. TS. Hồ Anh Tuý - “Xử lý tín hiệu số” (2002) 9. Thomas Sikora – “MPEG-1 and MPEG-2 Digital Video Coding Standards”. 10. Borko Furht, Stephen W.Smoliar, Hong Jiang Zhang – “Video and Image Processing in multimedia systems”. 11. Thomas Sikora – “Digital Video Coding Standards and Their Role in Video” Communications - Signal Processing for Multimedia, J.S. Byrnes (Ed), IOS Press, 1999. 12. Anil K. Jain - “Fundamental of Digital Image Processing”(1994) 13. Geoffrey Davis - Arina Nosratinia - “Waveled-Based Image Encoding - Overview” (1997) 14. Michael David Adams - “JPEG2000 - The Next Standard for Still Image Compressing” (12/2002) 15. Y. Kheong Chee - “Information Theory and Its Application to Image Coding” (11/1995) 16. Geoffrey Davis - Roger Claypoole - Wim Sweldens - Richard G.Baraniuk - “Nonlinear Wavelet transform for Image Coding via lifting” (8/1999) 17. Michael David Adams - “Reversible Wavelet Transform and their Application to embedded image compression”(1999) Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh 18. Michael David Adams - Faouzi Kossentini - Touraji Ebrahimi - “JPEG2000: The Next Generation Still Image Compression Standard” (2000) 19. R. Calderbank - I. Daubechies - Wim Sweldens - “Wavelet transform that map integer to integer”(1998) 20. Website: 21. Website: 22. Website: “ISO/IEC Standard 15444 JPEG2000- Final Committee Draft” (2001)