Đề tài 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

cao và có độ nhậy tốt hơn ở các hệ số có tần số thấp. Vì thế các hệ số được chọn sao cho thực hiện lượng tử hoá thô đối với các hệ số tần số cao và lượng tử hoá tinh đối với các hệ số có tần số thấp. Bảng lượng tử hoá được lấy tỉ lệ để tạo ra các mức nén thay đổi tuỳ theo tốc độ bít và chất lượng ảnh. Việc lượng tử hoá sẽ tạo ra rất nhiều giá trị 0, đặc biệt là ở tần số cao. Quá trình làm tròn trong khi lượng tử hoá chính là nguyên nhân chính gây ra sự tổn hao nhưng lại là nhân tố chính đem lại hiệu suất nén. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh (d) Để tận dụng ưu điểm của các hệ số đã được lượng tử có giá trị gần bằng 0, mảng hai chiều các hệ số đã được lượng tử sẽ được sắp xếp theo hình Zigzag tạo thành mảng một chiều. Cách sắp xếp này cho phép giảm thiểu năng lượng tổn hao trung bình và tạo ra dãy các giá trị bằng 0 liên tiếp. Cũng theo cách sắp xếp này, các hệ số DC được tách khỏi các hệ số AC và sử dụng kỹ thuật mã hoá điều xung mã vi sai – DPCM. (e) Bước cuối cùng của bộ mã hoá là sử dụng mã hoá entropy chẳng hạn mã hoá Huffman cho các AC và DC (sau khi đã mã hoá DPCM) để tăng thêm hiệu quả nén cũng như giảm thiểu lỗi. Ở phía giải mã, luồng bít mã hoá được giải mã entropy, sau đó mảng hai chiều các hệ số DCT đã được lượng tử hoá được giải sắp xếp Zigzag và giải lượng tử. Mảng hai chiều các hệ số DCT kết quả sẽ được biến đổi IDCT rồi cộng mỗi giá trị với 128 để xấp xỉ tạo thành các khối ảnh con kích thước 8x8. Chú ý là bảng lượng tử hoá và mã hoá entropy ở cá phía mã hoá và giải mã là đồng nhất. Hai thành phần màu cũng được mã hoá tương tự như thành phần chói ngoại trừ khác biệt là chúng được lấy mẫu xuống hệ số 2 hoặc 4 ở cả chiều ngang và dọc trước khi biến đổi DCT. Ở phía giải mã , thành phần màu sẽ được nội suy thành kích thước gốc. 2.4.2.2. Kỹ thuật mã hoá dựa trên phép biến đổi DWT Mối quan hệ giữa biến đổi Wavelet và Fourier Không giống như biến đổi Fourier chỉ thích hợp khi phân tích những tín hiệu ổn định (stationary),Wavelet là phép biến đổi được sử dụng để phân tích các tín hiệu không ổn định (non-stationary) – là những tín hiệu có đáp ứng tần số thay đổi theo thời gian. Để khắc phục những hạn chế của biến đổi FT, phép biến đổi Fourier thời gian ngắn – STFT được đề xuất. Chỉ có một sự khác biệt nhỏ giữa STFT và FT: Trong biến đổi STFT, tín hiệu được chia thành các khoảng nhỏ và Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh trong khoảng đó tín hiệu được giả định là tín hiệu ổn định. Để thực hiện kỹ thuật này cần chọn một hàm cửa sổ w sao cho độ dài của cửa sổ đúng bằng các khoảng tín hiệu phân chia. Với phép biến đổi STFT, chúng ta có thể thu được đáp ứng tần số - thời gian của tín hiệu đồng thời mà với phép biến đổi FT ta không thực hiện được. Biến đổi STFT đối với tín hiệu liên tục thực được định nghĩa như sau: X(f,t) = ∫∞ ∞− −− dtetwtx ftjπτ 2* ])()([ (2.12) Trong đó độ dài thời gian của cửa sổ là (t-τ), chúng ta có thể dịch chuyển vị trí của cửa sổ bằng cách thay đổi giá trị t và để thu được các đáp ứng tần số khác nhau của đoạn tín hiệu ta thay đổi giá trị τ . Giải thích biến đổi STFT bằng nguyên lý bất định Heissenber, nguyên lý này phát biểu là: Không thể biết được chính xác được biểu diễn thời gian - tần số của một tín hiệu (hay không thể biết các thành phần phổ của tín hiệu ở một thời điểm nhất định). Cái mà ta có thể biết là trong một khoảng thời gian nhất định tín hiệu có những băng tần nào. Đây được gọi là bài toán phân giải. Vấn đề này liên quan đến độ rộng của hàm cửa sổ mà chúng ta sử dụng. Nếu hàm cửa sổ càng hẹp thì độ phân giải càng tốt hơn và giả định tín hiệu là ổn định càng có độ chính xác nhưng độ phân giải tần số lại kém đi. Ta có các hệ quả sau: Cửa sổ hẹp -> phân giải thời gian tốt, phân giải tần số kém Cửa sổ rộng -> phân giải tần số tốt, phân giải thời gian kém Trên cơ sở cách tiếp cận biến đổi STFT, biến đổi Wavelet được phát triển để giải quyết vấn đề về độ phân giải tín hiệu (miền thời gian hoặc tần số) mà STFT vẫn còn hạn chế. Biến đổi Wavelet được thực hiện theo cách: tín hiệu được nhân với hàm Wavelet (tương tự như nhân với hàm cửa sổ trong biến đổi STFT), rồi thực hiện biến đổi riêng rẽ cho các khoảng tín hiệu khác nhau trong miền thời gian tại các tần số khác nhau. Cách tiếp Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh cận như vậy còn được gọi là: phân tích đa phân giải – MRA (Multi Resolution Analysis): phân tích tín hiệu ở các tần số khác nhau và cho các độ phân giải khác nhau. MRA khi phân tích tín hiệu cho phép: phân giải thời gian tốt và phân giải tần số kém ở các tần số cao; phân giải tần số tốt và phân giải thời gian kém ở các tần số thấp. Như vậy kỹ thuật này rất thích hợp với những tín hiệu: có các thành phần tần số cao xuất hiện trong khoảng thời gian ngắn, các thành phần tần số thấp xuất hiện trong khoảng thời gian dài chẳng hạn như ảnh và khung ảnh video. Cơ sở toán học cũng như các tính chất của biến đổi Wavelet liên tục sẽ được trình bầy chi tiết trong chương 3. Biến đổi Wavelet rời rạc – DWT Bước này có thể hiểu phép biến đổi DWT như là áp dụng một tập các bộ lọc: thông cao và thông thấp. Thiết kế các bộ lọc này tương đương như kỹ thuật mã hoá băng con (subband coding) nghĩa là: chỉ cần thiết kế các bộ lọc thông thấp, còn các bộ lọc thông cao chính là các bộ lọc thông thấp dịch pha đi một góc 180o. Tuy nhiên khác với mã hoá băng con, các bộ lọc trong DWT được thiết kế phải có đáp ứng phổ phẳng, trơn và trực giao. Hình 2.11 dưới đây minh hoạ dạng tổng quát của biến đổi DWT một chiều. Theo đó tín hiệu được cho đi qua các bộ lọc thông cao và thông thấp H và G rồi được lấy mẫu xuống (down sampling) hệ số 2 tạo thành biến đổi DWT mức 1. Biến đổi ngược thì thực hiện ngược lại: lấy mẫu lên (up sampling) hệ số 2 rồi sử dụng các bộ lọc khôi phục H’, G’ (lý tưởng là H’ và G’ chính là H, G). Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 2.8. Bank lọc khôi phục lý thuyết sử dụng DWT 1D Từ biến đổi DWT một chiều có thể mở rộng định nghĩa biến đổi DWT hai chiều theo cách: Sử dụng các bộ lọc riêng biệt, thực hiện biến đổi DWT một chiều dữ liệu vào (ảnh) theo hàng rồi thực hiện theo cột. Theo cách này nếu thực hiện biến đổi DWT ở mức 1, sẽ tạo ra 4 nhóm hệ số biến đổi. Quá trình biến đổi DWT hai chiều có thể minh hoạ như hình 2.12 dưới đây, trong đó 4 nhóm hệ số là: LL, HL, LH, HH (chữ cái đầu tiên tương ứng đã thực hiện lọc theo hàng, chữ cái thứ hai tương ứng đã thực hiện lọc theo cột). Hình 2.9. Minh hoạ DWT hai chiều cho ảnh Hình 2.10(a). Minh hoạ DWT kiểu dyadic mức 3 để nén ảnh Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 2.10(b). Minh hoạ DWT kiểu dyadic mức 3 để nén ảnh Hai thuật toán nén sử dụng DWT điển hình So với biến phép biến đổi DCT sử dụng trong chuẩn nén JPEG ra đời 1992, nén ảnh dựa trên biến đổi DWT đã có những cải tiến đáng kể. Tuy nhiên cải tiến mang tính đột phá sử dụng DWT để nén ảnh bắt đầu là kỹ thuật mã hoá – EZW (embedded zero-tree wavelet). Thuật toán EZW dựa trên khả năng khai thác các thuộc tính đa phân giải của biến đổi Wavelet để đưa ra một thuật toán ít phức tạp trong tính toán mà vẫn cho hiệu quả nén cao. Những cải tiến và nâng cấp của EZW về sau đã ra đời một số thuật toán tương tự như: SPIHT (set partitationing in hierarchical tree – cây phân cấp phân tập) và ZTE (zero-tree entropy coding – mã hoá entropy cây zero). Gần đây còn có thêm một thuật toán nữa được đề xuất đó là LS (lifting scheme) sử dụng để tạo các biến đổi Wavelet số nguyên. Kỹ thuật này sử dụng các bộ lọc Wavelet trực giao đem lại hiệu quả rất cao cho các ứng dụng nén ảnh có tổn hao. Chúng ta sẽ trình bầy 3 thuật toán điển mình này ở chương 3. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh CHƯƠNG 3:CƠ SỞ LÝ THUYẾT BIẾN ĐỔI WAVELET 3.1. Cơ sở toán học 3.1.1. Biến đổi Wavelet liên tục Biến đổi Wavelet liên tục (Continuous Wavelet Transform - CWT) của một hàm ( )f t được bắt đầu từ một hàm Wavelet mẹ (mother Wavelet) ( )tψ . Hàm Wavelet mẹ ( )tψ có thể là bất kỳ một hàm số thực hoặc phức liên tục nào thoả mãn các tính chất sau đây: Tích phân suy rộng trên toàn bộ trục t của hàm ( )tψ là bằng 0. Tức là: ( ) 0t dtψ∞ −∞ =∫ (3.1) Tích phân năng lượng của hàm trên toàn bộ trục t là một số hữu hạn, tức là: ( ) 2t dtψ∞ −∞ < ∞∫ (3.2) Điều kiện (3.2) có nghĩa là hàm ( )tψ phải là một hàm bình phương khả tích nghĩa là hàm ( )tψ thuộc không gian ( )2L R các hàm bình phương khả tích. Sau khi hàm Wavelet ( )tψ được lựa chọn, biến đổi Wavelet liên tục của một hàm bình phương khả tích ( )f t được tính theo công thức: ( ) ( ) *1, t bW a b f t dt aa ψ ∞ −∞ −⎛ ⎞= ⎜ ⎟⎝ ⎠∫ (3.3) Biến đổi này là một hàm của hai tham số thực a và b. Dấu * ký hiệu là liên hiệp phức của ( )tψ . Nếu chúng ta định nghĩa một hàm ( ),a b tψ theo biểu thức: ( ), 1a b t bt aaψ ψ −⎛ ⎞= ⎜ ⎟⎝ ⎠ (3.4) Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh chúng ta có thể viết được: ( ) ( ) ( ),, a bW a b f t t dtψ ∞ −∞ = ∫ (3.5) Theo toán học ta gọi đây là tích vô hướng của hai hàm ( )f t và ( ),a b tψ . Giá trị 1 a là hệ số chuẩn hoá để đảm bảo rằng tích phân năng lượng của hàm ( ),a b tψ sẽ độc lập với a và b : ( ) ( )2 2,a b t dt t dtψ ψ ∞ ∞ −∞ −∞ =∫ ∫ (3.6) Với mỗi giá trị của a thì ( ),a b tψ là một bản sao của ( ),0a tψ được dịch đi b đơn vị trên trục thời gian. Do đó b được gọi là tham số dịch. Đặt tham số dịch 0b = ta thu được: ( ),0 1a tt aaψ ψ ⎛ ⎞= ⎜ ⎟⎝ ⎠ (3.7) điều đó cho thấy rằng a là tham số tỷ lệ. Khi 1a > thì hàm Wavelet sẽ được trải rộng còn khi 0 1a< < thì hàm sẽ được co lại. Sau đây chúng ta sẽ định nghĩa phép biến đổi ngược của biến đổi Wavelet liên tục. Gọi ( )ωΨ là biến đổi Fourier của ( )tψ : ( ) ( ) j tt e dtωω ψ∞ − −∞ Ψ = ∫ (3.8) Nếu ( ),W a b là biến đổi CWT của ( )f t bằng hàm Wavelet ( )tψ , thì biến đổi ngược của biến đổi CWT sẽ được tính như sau: ( ) ( ) ( ),21 1 , a bf t W a b t dadbC a ψ ∞ ∞ −∞ −∞= ∫ ∫ (3.9) với giá trị của C được định nghĩa là: ( ) 2 C d ω ωω ∞ −∞ Ψ= ∫ (3.10) Biến đổi CWT chỉ tồn tại nếu C dương và hữu hạn. Do đó C được gọi là điều kiện tồn tại của biến đổi Wavelet. Cùng với hai điều kiện đã Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh nêu ở trên, đây là điều kiện thứ 3 mà một hàm cần phải thoả mãn để có thể được lựa chọn làm hàm Wavelet. Chúng ta có thể xem biến đổi CWT như là một ma trận hai chiều các kết quả của phép tính tích vô hướng giữa hai hàm ( )f 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