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

Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------WX-------- LUẬN VĂN THẠC SỸ KHOA HỌC 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 NGHÀNH: ĐIỆN TỬ VIỄN THÔNG ĐỖ NGỌC ANH Người hướng dẫn khoa học: PGS.TS. Nguyễn Đức Thuận HÀ NỘI 2006 Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh MỤC LỤC CÁC HÌNH VẼ, BẢNG BIỂU TRONG LUẬN VĂN ..............................5 THUẬT NGỮ TIẾNG ANH ......................................................................7 LỜI GIỚI THIỆU .......................................................................................8 CHƯƠNG 1: MỞ ĐẦU..............................................................................9 1.1. Cơ sở nghiên cứu và mục đích của luận văn ...................................9 1.2. Tổ chức luận văn............................................................................10 CHƯƠNG 2:TỔNG QUAN CÁC KỸ THUẬT NÉN TRONG Mà HOÁ ẢNH..........................................................................................................11 2.1. Giới thiệu chung về nén ảnh số .....................................................11 2.2. Phân loại các kỹ thuật nén .............................................................13 2.2.1. Nén tổn hao và không tổn hao ................................................13 2.2.2. Mã hoá dự đoán và mã hoá dựa trên phép biến đổi................13 2.2.3. Mã hoá băng con.....................................................................14 2.3. Tiêu chuẩn đánh giá chất lượng mã hoá ảnh .................................14 2.4.Các kỹ thuật nén có tổn hao............................................................15 2.4.1. Kỹ thuật mã hoá băng con ......................................................15 2.4.2. Kỹ thuật mã hoá dựa trên phép biến đổi.................................19 2.4.2.1. Kỹ thuật mã hoá dựa trên phép biến đổi DCT.................19 2.4.2.2. Kỹ thuật mã hoá dựa trên phép biến đổi DWT ...............25 CHƯƠNG 3:CƠ SỞ LÝ THUYẾT BIẾN ĐỔI WAVELET...................30 3.1. Cơ sở toán học ...............................................................................30 3.1.1. Biến đổi Wavelet liên tục........................................................30 3.1.2. Biến đổi Wavelet rời rạc .........................................................32 3.2. Tính chất của biến đổi Wavelet......................................................33 3.3. Giới thiệu một số họ Wavelet ........................................................37 3.3.1. Biến đổi Wavelet Haar ............................................................37 3.3.2. Biến đổi Wavelet Meyer .........................................................38 Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh 3.3.3. Biến đổi Wavelet Daubechies .................................................38 3.4. Một số ứng dụng nổi bật của Wavelet ...........................................39 3.4.1. Nén tín hiệu.............................................................................39 3.4.2. Khử nhiễu ...............................................................................40 3.4.3. Mã hoá nguồn và mã hoá kênh...............................................40 CHƯƠNG 4:CHUẨN NÉN ẢNH TĨNH DỰA TRÊN BIẾN ĐỔI WAVELET – JPEG2000..........................................................................41 4.1. Lịch sử ra đời và phát triển chuẩn JPEG2000...............................41 4.2. Các tính năng của JPEG2000 ........................................................41 4.3. Các bước thực hiện nén ảnh theo chuẩn JPEG2000 .....................42 4.3.1. Xử lý trước biến đổi................................................................42 4.3.2. Biến đổi liên thành phần .........................................................42 4.3.3. Biến đổi riêng thành phần (biến đổi Wavelet) ........................43 4.3.4.Lượng tử hoá - Giải lượng tử hoá............................................44 4.3.5. Mã hoá và kết hợp dòng dữ liệu sau mã hoá ..........................45 4.3.6. Phương pháp mã hoá SPIHT ..................................................45 4.3.7. Phương pháp mã hoá EZW .....................................................47 4.4. So sánh chuẩn JPEG2000 với JPEG và các chuẩn nén ảnh tĩnh khác .......................................................................................................49 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...............54 5.1. Nén ảnh bằng Wavelet ...................................................................54 5.2.1. Sơ đồ khối tổng quát ...............................................................54 5.1.2. Biến đổi Wavelet .....................................................................55 5.1.3. Tính toán năng lượng tiêu hao................................................56 5.2. Thuật toán nén ảnh bằng Wavelet hiệu năng - EEW .....................58 5.2.1. Hiệu năng của các kỹ thuật loại bỏ.........................................60 5.3.2. Các kết quả thực nghiệm ........................................................62 5.3.2.1. Ảnh hưởng đến năng lượng tính toán và chất lượng ảnh 62 Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh 5.3.2.2. Ảnh hưởng đến năng lượng truyền thông và chất lượng ảnh.................................................................................................62 5.4. Các tham số nén ảnh bằng Wavelet ...............................................62 5.4.1. Thay đổi mức biến đổi Wavelet ..............................................62 5.4.2. Thay đổi các mức lượng tử .....................................................62 5.5. Truyền ảnh trên mạng...................................................................62 5.5.1. Phương pháp lựa chọn tham số động......................................62 5.5.2. Kết quả thực nghiệm...............................................................62 KẾT LUẬN...............................................................................................63 Kết quả đạt được và ứng dụng của luận văn.........................................63 Hướng phát triển nghiên cứu ................................................................63 PHỤ LỤC..................................................................................................65 TÀI LIỆU THAM KHẢO ........................................................................66 Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh CÁC HÌNH VẼ, BẢNG BIỂU TRONG LUẬN VĂN Hình 2.1 Sơ đồ bộ khái quát hệ thống nén ảnh.........................................12 Hình 2.2. Sơ đồ minh hoạ kỹ thuật mã hoá băng con – M băng con .......16 Hình 2.3 Minh hoạ quá trình phân ly băng con cây bát phân...................17 Hình 2.4. Phân ly hai ảnh mẫu thành bốn băng con .................................18 Hình 2.5. Sơ đồ bộ mã hoá theo chuẩn JPEG ..........................................23 Hình 2.6. Sắp xếp Zigzag các hệ số DCT ở bộ mã hoá............................23 Hình 2.7. Sơ đồ khối bộ giải mã theo chuẩn JPEG ..................................23 Hình 2.8. Bank lọc khôi phục lý thuyết sử dụng DWT 1D ......................28 Hình 2.9. Minh hoạ DWT hai chiều cho ảnh ............................................28 Hình 2.10(a). Minh hoạ DWT kiểu dyadic mức 3 để nén ảnh..................28 Hình 2.10(b). Minh hoạ DWT kiểu dyadic mức 3 để nén ảnh..................29 Hình 3.1. Minh hoạ lưới nhị tố dyadic với các giá trị của m và n............33 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 .............36 Hình 3.3. Hàm ( )tψ của biến đổi Haar ....................................................38 Hình 3.4: Hàm ( )tψ của biến đổi Meyer..................................................38 Hình 3.5. Hàm ( )tψ của họ biến đổi Daubechies n với n=2, 3, 7, 8........39 Hình 4.1: Trình tự mã hoá (a) và giải mã JPEG2000 (b).........................42 Hình 4.2: Minh hoạ ảnh với RGB và YCrCb ...........................................43 Hình 4.3: Phương pháp Lifting 1D dùng tính toán biến đổi Wavelet.......44 Hình 4.4: Minh hoạ cây tứ phân (a) và sự phân mức (b)..........................47 Hình 4.5: Hai cách sắp xếp thứ tự các hệ số biến đổi...............................48 Hình 4.6: So sánh JPEG và JPEG2000....................................................50 Bảng 4.1: So sánh JPEG và JPEG2000 ...................................................51 Hình 4.7: Minh hoạ tính năng ROI...........................................................52 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 ...........................................................................................................53 Hình 5.1. Sơ đồ khối quá trình nén ảnh bằng Wavelet .............................54 Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 5.2. (a) Biến đổi Wavelet 2D mức 3 và (b) Minh hoạ bằng ảnh “CASTLE” ................................................................................................56 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.........................................................................................................59 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*.........................................................................................................61 Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh THUẬT NGỮ TIẾNG ANH CWT Biến đổi Wavelet liên tục (Continuous Wavelet Transform) DCT Biến đổi Cosine rời rạc (Discrete Cosine Transform) DFT Biến đổi Fourier rời rạc (Discrete Fourier Transform) DPCM Điều xung mã vi sai (Differized Pulse Code Modulation) DWT Biến đổi Wavelet rời rạc (Discrete Wavelet Transform) EZW Wavelet cây zero (Embedded Zerotree Wavelet) HVS Hệ thống cảm nhận hình ảnh của mắt người (Human Visual System) IDWT Biến đổi Wavelet rời rạc ngược JPEG Chuẩn nén ảnh của ủy ban JPEG quốc tế (Joint Photographic Experts Group) JPEG2000 Chuẩn nén ảnh JPEG2000 Lossless Compression Kỹ thuật nén ảnh không tổn hao (không mất dữ liệu) Lossy Compression Kỹ thuật nén ảnh có tổn hao (có mất dữ liệu) MRA Phân tích đa phân giải (Multi Resolution Analysis) MSE Sai số bình phương trung bình (Mean Square Error) PCM Điều xung mã (Pulse Code Modulation) PSNR Tỷ số tín hiệu đỉnh trên nhiễu (Peak Signal to Noise Ratio) QMF Lọc gương cầu tứ phương (Quardrature Mirror Filters) RLC Mã hoá loạt dài (Run Length Coding) ROI Kỹ thuật mã hóa ảnh theo vùng (Region Of Interest) – Một tính năng mới nổi bật của JPEG2000 SPIHT Phương pháp mã hoá phân cấp theo vùng (Set partitioning in hierarchical trees) STFT Biến đổi Fourier thời gian ngắn (Short Time Fourier Transform) Wavelet Biến đổi băng con Wavelet Wavelet Decomposition Tree Cây phân giải Wavelet Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh LỜI GIỚI THIỆU Trong những năm gần đây, nhu cầu các dịch vụ dữ liệu trên mạng di động, nhất là dữ liệu đa phương tiện là rất lớn. Cùng với nhu cầu đó, vấn đề đặt ra là làm thế nào tìm được một kỹ thuật mã hoá dữ liệu then chốt (chuẩn), có hiệu quả để truyền các dữ liệu này trên mạng di động. Mục đích của luận văn là trình bầy một kỹ thuật nén ảnh sử dụng biến đổi Wavelet cho ảnh tĩnh và đặc biệt là ảnh tĩnh trong các dịch vụ dữ liệu đa phương tiện trong mạng di động. So với các kỹ thuật nén sử dụng phép biến đổi trước đây như biến đổi Fourier (FT), biến đổi cosine rời rạc (DCT), biến đổi xếp chồng (LT),.., biến đổi Wavelet (DWT) có nhiều ưu điểm không chỉ trong xử lý ảnh mà còn nhiều ứng dụng khác. Bằng chứng là sự ra đời của chuẩn nén JPEG2000 (dựa trên DWT) có tính năng vượt trội so với JPEG (DCT). Tuy nhiên chuẩn JPEG, MPEG hay ngay cả JPEG2000 cũng chỉ tập trung vào hiệu quả nén (tỉ số nén) và chất lượng ảnh mà không chú ý đến năng lượng tiêu hao trong quá trình xử lý và truyền trên mạng. Trong luận văn đã trình bầy một kỹ thuật nén ảnh trong mạng di động sử dụng biến đổi Wavelet hiệu năng không chỉ đem lại hiệu quả nén, chất lượng hình ảnh mà còn tiết kiệm năng lượng xử lý của hệ thố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. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh CHƯƠNG 1: MỞ ĐẦU 1.1. Cơ sở nghiên cứu và mục đích của luận văn Để có thể sử dụng các dịch vụ Internet không dây cũng như nhiều dịch vụ dữ liệu khác trên nền các ứng dụng di động cần có một kỹ thuật then chốt để có thể hỗ trợ truyền thông nhiều dạng dữ liệu trong thông tin di động tế bào như: thoại, văn bản, hình ảnh và video. Tuy nhiên vấn đề truyền thông nội dung đa phương tiện trong thông tin di động gặp một số khó khăn: băng thông của mạng di động tế bào, nhiễu kênh, giới hạn của pin cho các ứng dụng, tính tương thích dữ liệu giữa các thuê bao. Trong khi việc cải thiện băng thông di động cần một công nghệ mới của tương lai còn việc cải thiện giới hạn của pin không đáp ứng được sự phát triển của các dịch vụ tương lai, thì phương pháp giảm kích thước dữ liệu bằng các kỹ thuật nén là một cách tiếp cận hiệu quả giải quyết các khó khăn trên. Mặc dù cho đến nay có rất nhiều kỹ thuật nén dữ liệu đa phương tiện như: chuẩn JPEG (dựa trên biến đổi DCT), chuẩn JPEG2000 (dựa trên biến đổi Wavelet) và chuẩn MPEG, tuy nhiên những kỹ thuật này chỉ tập trung vào hiệu quả nén và cố gắng đánh mất chất lượng ảnh ít vì thế chúng bỏ qua vấn đề tiêu hao năng lượng trong quá trình nén và truyền RF (trong thông tin động). Luận văn này trình bầy một kỹ thuật hiệu quả để khắc phục những khó khăn trên cho loại dữ liệu đa phương tiện điển hình trong thông tin di động là ảnh tĩnh. Đó là kỹ thuật nén ảnh sử dụng biến đổi Wavelet thích nghi và hiệu năng cho dữ liệu đa phương tiện trong thông tin di động. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh 1.2. Tổ chức luận văn Luận văn được trình bầy thành 5 chương và 1 phụ lục. Chương 1, tác giả trình bày tóm tắt cơ sở nghiên cứu và mục đích cũng như tổ chức của luận văn. Chương 2 trình bầy khái quát các kỹ thuật nén ảnh, phân loại các nguyên lý nén và định nghĩa một số thuật ngữ được sử dụng rộng rãi như MSE, PSNR và SNR. Chương này cũng trình bầy cơ sở lý thuyết của các nguyên lý nén có tổn hao điển hình như: mã hoá băng con; mã hoá dựa trên biến đổi cosine rời rạc (DCT), biến đổi xếp chồng (LT), biến đổi Wavelet rời rạc (DWT). Chương 3 trình bầy cơ sở toán học, tính chất của biến đổi Wavelet. Nội dung của chương này là lý thuết nền tảng cho các ứng dụng Wavelet. Chương này cũng đưa ra một số họ Wavelet phổ biến và giới thiệu một số ứng dụng nổi bật của Wavelet ngoài ứng dụng để nén ảnh. Chương 4 giới thiệu tổng quan về chuẩn nén JPEG2000 dựa trên biến đổi Wavelet. Mục đích không chỉ là giới thiệu một chuẩn nén vượt trội so với chuẩn JPEG dựa trên biến đổi DCT mà còn đưa ra một lựa chọn giải quyết bài toán đặt ra trong luận văn. JPEG2000 đang từng bước được tổ chức ISO công nhận nên chắc chắn sẽ trở thành một chuẩn nén phổ biến trong các ứng dụng di động tương lai. Cũng trong chương này, tác giả trình bầy tóm tắt các bước thực hiện nén ảnh theo JPEG200 và so sánh nó với chuẩn JPEG và các chuẩn nén ảnh tĩnh khác. Chương 5 cũng là chương quan trọng nhất. Dựa trên kỹ thuật nén ảnh bằng Wavelet, luận văn đưa ra một thuật toán biến đổi ảnh bằng Wavelet hiệu năng làm giảm đáng kể năng lượng tính toán và truyền thông cần thiết cho ảnh mà vẫn đảm bảo được chất lượng bức ảnh (và như vậy giảm được giá thành dịch vụ). Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh CHƯƠNG 2:TỔNG QUAN CÁC KỸ THUẬT NÉN TRONG Mà HOÁ ẢNH 2.1. Giới thiệu chung về nén ảnh số Nén ảnh số là một đề tài nghiên cứu rất phổ biến trong lĩnh vực xử lý dữ liệu đa phương tiện. Mục đích là làm thế nào để lưu trữ bức ảnh dưới dạng có kích thước nhỏ hơn hay dưới dạng biểu diễn mà chỉ yêu cầu số bít mã hoá ít hơn so với bức ảnh gốc. Nén ảnh thực hiện được là do một thực tế: thông tin trong bức ảnh không phải là ngẫu nhiên mà có trật tự, có tổ chức. Vì thế nếu bóc tách được tính trật tự, cấu trúc đó thì sẽ biết được phần thông tin nào quan trọng nhất trong bức ảnh để biểu diễn và truyền đi với số lượng bít ít hơn so với ảnh gốc mà vẫn đảm bảo tính đầy đủ thông tin. Ở phía thu, quá trình giải mã sẽ tổ chức, sắp xếp lại được bức ảnh xấp xỉ gần chính xác so với ảnh gốc nhưng vẫn thoả mãn chất lượng yêu cầu, đảm bảo đủ thông tin cần thiết. Tóm lại, tín hiệu ảnh, video hay audio đều có thể nén lại bởi chúng có những tính chất như sau: • Có sự tương quan (dư thừa) thông tin về không gian: Trong phạm vi một bức ảnh hay một khung video tồn tại sự tương quan đáng kể (dư thừa) giữa các điểm ảnh lân cận. • Có sự tương quan (dư thừa) thông tin về phổ: Các dữ liệu thu được từ các bộ cảm biến của thiết bị thu nhận ảnh tồn tại sự tương quan đáng kể giữa các mẫu thu, đây chính là sự tương quan về phổ. • Có sự tương quan (dư thừa) thông tin về thời gian: Trong một chuỗi ảnh video, tồn tại sự tương quan giữa các điểm ảnh của các khung video (frame). Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Sơ đồ của một hệ thống nén dữ liệu tổng quát như sau: Hình 2.1 Sơ đồ bộ khái quát hệ thống nén ảnh Trong hình 2.1, bộ mã hoá dữ liệu thực hiện quá trình nén bằng cách giảm kích thước dữ liệu ảnh gốc đến một mức phù hợp với việc lưu trữ và truyền dẫn trên kênh. Tốc độ bít đầu ra của bộ mã hoá được tính là số bít cho một mẫu (điểm ảnh). Bộ mã hoá kênh thực hiện việc chuyển đổi luồng bít đã được nén thành dạng tín hiệu phù hợp cả cho việc lưu trữ và truyền dẫn, thường bộ mã hoá kênh sử dụng các kỹ thuật: mã hoá có độ dài thay đổi – RLC (Run Length Coding)[4], mã hoá Huffman[4], mã hoá số học [4]. Bộ giải mã thực hiện quá trình ngược lại so với bộ mã hoá. Trong các hệ thống nén, tỉ số nén chính là tham số quan trọng đánh giá khả năng nén của hệ thống, công thức được tính như sau: Tỉ số nén = Kích thước dữ liệu gốc / Kích thước dữ liệu nén Đối với ảnh tĩnh, kích thước chính là số bít để biểu diễn toàn bộ bức ảnh. Đối với ảnh video, kích thước chính là số bít để biểu diễn một khung hình video (video frame). Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh 2.2. Phân loại các kỹ thuật nén Các kỹ thuật nén chủ yếu được phân loại như sau: 2.2.1. Nén tổn hao và không tổn hao Trong các kỹ thuật nén không tổn hao (losses compression), ảnh khôi phục giống hoàn toàn so với ảnh gốc. Tuy nhiên, nén không tổn hao chỉ đạt được hiệu quả nén rất nhỏ. Trái lại, các kỹ thuật nén có tổn hao (lossy compression) có thể đạt được hiệu quả nén cao hơn rất nhiều mà ở điều kiện cảm nhận hình ảnh thông thường sự mất mát thông tin không cảm nhận được và vì thế vẫn đảm bảo chất lượng ảnh. Một số kỹ thuật nén có tổn hao gồm: điều xung mã vi sai – DPCM, điều xung mã – PCM, lượng tử hoá véctơ – VQ, mã hoá biến đổi và băng con. Ảnh khôi phục trong hệ thống nén có tổn hao luôn có sự suy giảm thông tin so với ảnh gốc bởi vì: phương pháp nén này đã loại bỏ những thông tin dư thừa không cần thiết. 2.2.2. Mã hoá dự đoán và mã hoá dựa trên phép biến đổi Đối với mã hoá dự đoán (predictive coding) các giá trị mang thông tin đã được gửi hay đang sẵn có sẽ được sử dụng để dự đoán các giá trị khác, và chỉ mã hoá sự sai lệch giữa chúng. Phương pháp này đơn giản và rất phù hợp với việc khai thác các đặc tính cục bộ của bức ảnh. Kỹ thuật DPCM chính là một ví dụ điển hình của phương pháp này. Trong khi đó, mã hoá dựa trên phép biến đổi (transform based coding) thì lại thực hiện như sau: trước tiên thực hiện phép biến đổi với ảnh để chuyển sự biểu diễn ảnh từ miền không gian sang một miền biểu diễn khác. Các phép biến đổi thường dùng là: DCT - biến đổi Cosine rời rạc, DWT - biến đổi Wavelet rời rạc, LT - biến đổi trồng (lapped) , tiếp đó thực hiện mã hoá đối với các hệ sộ biến đổi. Phương pháp này có hiệu suất nén cao hơn rất nhiều so với phương pháp nén dự đoán bởi vì chính các phép biến đổi (sử dụng các thuộc tính nén năng lượng của mình) đã gói gọn toàn bộ năng lượng bức ảnh chỉ bằng một số ít các hệ số, số lớn các hệ số còn lại ít có ý nghĩa hơn sẽ bị loại bỏ sau khi lượng tử hoá và như vậy lượng dữ liệu phải Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh truyền nhỏ đi rất nhiều. Trong phương pháp mã hoá dự đoán, sai lệch giữa ảnh gốc và ảnh dự đoán vẫn có ý nghĩa (còn sử dụng ở bước tiếp theo) sau khi lượng tử hoá, chính điều này làm cho phương pháp mã hoá dự đoán có nhiều dữ liệu được truyền đi hơn so với phương pháp mã hoá biến đổi. 2.2.3. Mã hoá băng con Bản chất của kỹ thuật mã hoá băng con (subband coding) là chia băng tần của tín hiệu (ảnh) thành nhiều băng con (subband). Để mã hoá cho mỗi băng con, chúng ta sử dụng một bộ mã hoá và một tốc độ bít tương ứng với tính chất thống kê của băng con. 2.3. Tiêu chuẩn đánh giá chất lượng mã hoá ảnh Để đánh giá chất lượng của bức ảnh (hay khung ảnh video) ở đầu ra của bộ mã hoá, người ta thường sử dụng hai tham số: Sai số bình phương trung bình – MSE (mean square error) và tỉ số tín hiệu trên nhiễu đỉnh – PSNR (peak to signal to noise ratio). MSE thường được gọi là phương sai lượng tử - 2qσ (quantization error variance). MSE giữa ảnh gốc và ảnh khôi phục được tính như sau: ( )22 , 1 [ , ] - [ , ]q j k MSE f j k g j k N σ= = ∑ (2.1) Trong đó tổng lấy theo j, k tính cho tổng tất cả các điểm ảnh trong ảnh và N là số điểm ảnh trong ảnh. Còn PSNR giữa hai ảnh (b bít cho mỗi điểm ảnh, RMSE là căn bậc 2 của MSE) đước tính theo công thức dB như sau: 12 log20 10 −−= b RMSEPSNR (2.2) Thông thường, nếu PSNR ≥ 40dB thì hệ thống mắt người gần như không phân biệt được giữa ảnh gốc và ảnh khôi phục. Một tham số khác hay sử dụng trong các hệ thông viễn thông đó là tỉ số tín hiệu trên nhiễu - SNR , tuy vậy SNR sử dụng cho một hệ thống né ảnh cũng có công thức dB như sau: Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh 1010log Encoder input energySNR Noise energy = (2.3) 2.4.Các kỹ thuật nén có tổn hao Trong phần này, tác giả lựa chọn trình bày hai kỹ thuật nén tổn hao cho nén ảnh tĩnh và ảnh động đó là: mã hoá băng con (subband coding) và mã hoá sử dụng phép biến đổi (transform coding). Đây là hai kỹ thuật nén điển hình và cho hiểu quả nén cũng như chất lượng ảnh cao. 2.4.1. Kỹ thuật mã hoá băng con Tư tưởng chính của kỹ thuật mã hoá băng con là: các ảnh được lấy mẫu ở đầu vào được phân ly thành các băng tần khác nhau (gọi là các tín hiệu băng con). Yêu cầu của kỹ thuật này là làm thế nào các băng con không bị chồng chéo lên nhau. Để có thể phân ly tín hiệu ở bộ mã hoá (encoder) thành các băng con, ảnh được cho qua một bank lọc (filter bank) gọi là bank lọc phân tích và mỗi đầu ra của bank lọc băng con được lấy mẫu xuống hệ số 2. Các đầu ra băng con tần số được lẫy mẫu xuống sẽ lần lượt được: lượng tử hoá độc lập bằng các bộ lọc vô hướng khác nhau, mã hoá entropy, lưu trữ và truyền đi. Ở phía bộ giải mã (decoder), quá trình được thực hiện ngược lại: giải lượng tử băng con tần số, lấy mẫu lên với hệ số 2, cho đi qua bank lọc băng con tổng hợp rồi cộng tất cả các đầu ra của bộ lọc để khôi phục lại ảnh. Các bộ lọc băng con thường được thiết kế xấp xỉ thoả mãn tiêu chuẩn của các đáp ứng tần số không chồng chéo. Mục đích là để giải tương quan các hệ số tần số kết quả. Đây chính là tính chất quan trọng mà quá trình lọc băng con cố gắng đạt được. Các bộ lọc băng con được thiết kế để là các xấp xỉ với các bộ lọc chọn tần số lý tưởng, trong đó đáp ứng tổng hợp từ tất cả các bộ lọc bao trùm tất cả băng tần của ảnh. Tuy nhiên trong thực tế, sự tương quan tổng không bao giờ đạt được do những bộ lọc này chỉ xấp xỉ với các bộ lọc lý tưởng. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 2.2 dưới đây là sơ đồ tổng quát giải thích kỹ thuật mã hoá băng con. Hình 2.2. Sơ đồ minh hoạ kỹ thuật mã hoá băng con – M băng con Các bộ lọc sử dụng trong mã hoá băng con là các bộ lọc gương tứ phương – QMF (quardrature mirror filters), do vậy chúng ta chỉ cần thiết kế các bộ lọc thông thấp có đáp ứng H(ω) còn đáp ứng của các bộ lọc thông cao là H(ω+π) chỉ là sự dịch pha 180o so với bộ lọc thông thấp. Sự chính xác của bộ lọc phụ thuộc vào số các hệ số của bộ lọc. Một trong các phương pháp mã hoá băng con đó là áp dụng sự phân ly cây bát phân để phân ly dữ liệu ảnh thành các băng tần khác nhau. Ý tưởng của phương pháp này là: trước tiên lọc và lược bỏ ảnh để phân ly ảnh thành các băng con tần số cao và thấp, sau đó tiếp tục phân ly nhưng chỉ áp dụng cho băng con tần số thấp để tạo thành các băng con tần số cao và thấp để tiếp tục lược bỏ. Kỹ thuật này rất phổ biến và cũng được Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh áp dụng trong các bộ mã sử dụng biến đổi Wavelet. Đầu ra của các băng con sau khi đã giản lược sẽ được lượng tử hoá và mã hoá độc lập. Mỗi băng con sẽ sử dụng bộ lượng tử hoá riêng và mỗi bộ lượng tử hoá này có tốc độ lấy mẫu riêng (bít/mẫu). Như vậy rõ ràng mã hoá băng con không đạt được sự nén, mà nó chỉ thực hiện việc giải tương quan dữ ảnh gốc và tập trung năng lượng của ảnh vào một số băng con. Nén chỉ đạt được là do sự lược bỏ ảnh (decimation) và do sự lượng tử hoá (quantization). Hình 2.3 Minh hoạ quá trình phân ly băng con cây bát phân Trong các hệ thống mã hoá băng con hai chiều thực tế, người ta chia miền tần số - không gian hai chiều của ảnh gốc thành các băng khác nhau ở bất kỳ mức nào. Hình 2.4 dưới đây minh hoạ việc phân ly 2 ảnh mẫu thành 4 băng con LL, HL, LH và HH ở mức đầu tiên. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 2.4. Phân ly hai ảnh mẫu thành bốn băng con Nhược điểm của kỹ thuật mã hoá băng con: Một trong những vấn để chủ yếu của kỹ thuật mã hoá băng con đó là giải quyết bài toán cấp phát bít (là số bít cấp cho mỗi băng con) để đạt được hiệu suất cao nhất. Một trong những cách thực hiện là sử dụng ý tưởng cấp phát bít tối ưu cho mỗi đầu ra băng con đã được lượng tử hoá. Tuy nhiên cách này chủ yếu thích hợp cho trường hợp tốc độ cao (≥1bít/mẫu). Trước khi đi vào nghiên cứu kỹ thuật mã hoá dựa trên phép biến đổi, chúng ta sẽ tổng kết một số nhược điểm của kỹ thuật mã hoá băng con như sau: Kỹ thuật mã hoá băng con không xác định được hệ thống mã hoá tối ưu cho các ứng dụng tốc độ bít thấp. Việc cấp phát bít tối ưu sẽ thay đổi khi tốc độ bít tổng thay đổi, điều này làm quá trình mã hoá phải lặp lại hoàn toàn cho mỗi tốc độ bít xác định. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Không hoàn toàn giải tương quan cho tất cả các băng tần, đấy là do các bộ lọc không phải là lý tưởng và có sự chồng chéo nhỏ giữa các băng tần liền kề. Do vậy luôn luôn tồn tại một sự tương quan nhỏ giữa các băng tần kề nhau và dữ liệu sẽ không được nén hoàn toàn. Kỹ thuật mã hoá băng con không hiệu quả khi thực hiện bù chuyển động trong video vì rất khó để thực hiện đánh giá chuyển động ở các băng con (sai số dự đoán là rất lớn). 2.4.2. Kỹ thuật mã hoá dựa trên phép biến đổi Một phép biến đổi là một hàm toán học được sử dụng để biến đổi một tập các giá trị này thành một tập giá trị khác và tạo ra một cách biểu diễn mới cho cùng một nguồn tin. Tất cả các phép biến đổi mà chúng ta định trình bầy dưới đây đều là không tổn hao (lossless); với sự chính xác của các phép toán số học thì các phép biến đổi vẫn bảo tồn được độ chính xác ở bất kỳ mức độ nào. Nhưng hầu hết các kỹ thuật mã hoá đều có tổn hao ở bước lượng tử hoá do có sự làm tròn giá trị cho các hệ số phép biến đổi. Phần này chúng ta sẽ trình bầy các kỹ thuật mã hoá dựa trên phép biến đổi được sử dụng trong nén ảnh. (a) Kỹ thuật mã hoá dựa trên phép biến đổi cosine rời rạc – DCT (b) Kỹ thuật mã hoá dựa trên phép biến đổi chồng – LT (c) Kỹ thuật mã hoá dựa trên phép biến đổi DWT 2.4.2.1. Kỹ thuật mã hoá dựa trên phép biến đổi DCT Phép biến đổi cosine rời rạc – DCT (Discrete Cosine Transform) biến đổi thông tin ảnh từ miền không gian sang miền tần số để có thể biểu diễn dưới dạng gọn hơn. Tính chất của nó tương tự như biến đổi Fourier, coi ảnh đầu vào (tín hiệu audio hoặc video) là các tín hiệu ổn định bất Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh biến theo thời gian. Để hiểu rõ kỹ thuật này trước hết ta cần tìm hiểu biến đổi Fourier. Biến đổi Fourier – FT Biến đổi Fourier – FT (Fourier Transform) là một phép biến đổi thuận nghịch, nó cho phép sự chuyển đổi thuận – nghịch giữa thông tin gốc (miền không gian hoặc thời gian) và tín hiệu được xử lý (được biến đổi). Tuy nhiên ở một thời điểm bất kỳ chỉ tồn tại một miền thông tin được thể hiện. Nghĩa là tín hiệu trong miền không gian không có sự xuất hiện thông tin về tần số và tín hiệu sau biến đổi Fourier không có sự xuất hiện thông tin về thời gian. FT cho biết thông tin tần số của tín hiệu, cho biết những tần số nào có trong tín hiệu, tuy nhiên nó không cho biết tần số đó xuất hiện khi nào trong tín hiệu. Nếu như tín hiệu là ổn định (stationary – có các thành phần tần số không thay đổi theo thời gian) thì việc xác định các thành phần tần số xuất hiện khi nào trong tín hiệu là không cần thiết. Phép biến đổi FT thuận và nghịch được định nghĩa như sau: X(f) = ∫ ∞ ∞− − dtetx ftjπ2)( (2.4) x(t) = ∫∞ ∞− dfefX ftjπ2)( (2.5) Phép biến đổi FT cũng có thể được áp dụng cho tín hiệu không ổn định (non-stationary) nếu như chúng ta chỉ quan tâm đến thành phần phổ nào có trong tín hiệu mà không quan tâm đến nó xuất hiện khi nào trong tín hiệu. Tuy nhiên, nếu thông tin về thời gian xuất hiện của phổ trong tín hiệu là cần thiết, thì phép biến đổi FT không có khả năng đáp ứng được yêu cầu này, đây cũng là hạn chế của phép biến đổi này. Để có biến đổi Fourier rời rạc –DFT (Discrete Fourier Transform) thì ở phép tích phân trong biểu thức toán học của biến đổi FT, ta thay bằng phép tổng và tính toán nó với các mẫu hữu hạn. Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hệ số phép biến đổi DFT thứ k._. của một chuỗi gồm N mẫu {x(n)} được định nghĩa: X(k) = ∑− = 1 0 )( N n kn NWnx , k=0,………., N-1 (2.6) Trong đó WN = e Nj /2Π− = cos (2π/N) – j sin (2π/N), còn chuỗi {x(n)} có thể khôi phục bằng DFT ngược như sau: x(n) = N 1 ∑− = −1 0 )( N k kn NWkX , n=0,………., N-1 (2.7) Định nghĩa và các tính chất của biến đổi DCT Biến đổi DCT thuận và ngược một chiều gồm N mẫu được định nghĩa như sau: DCT = X(k) = N 2 ck ∑− = ⎥⎦ ⎤⎢⎣ ⎡ +1 0 2 )12(cos)( N n N knnx π , k= 0,1,………,N-1 (2.8) IDCT = x(n) = N 2 ∑− = ⎥⎦ ⎤⎢⎣ ⎡ +1 0 2 )12(cos)( N k k N knkXc π , n= 0,1,………,N-1 (2.9) Trong đó ck = ⎩⎨ ⎧ ≠ = 0,1 0,2/1 k k Cả DCT và IDCT đều là biến đổi trực giao, tách biệt và thực. Tính chất phân tách (separable) ở đây nghĩa là biến đổi nhiều chiều của nó có thể phân tách thành các biến đổi một chiều. Tính chất trực giao ở đây nghĩa là nếu các ma trận của DCT và IDCT là không bất thường (non-singular) và thực thì biến đổi ngược của chúng có thể đạt được bằng cách áp dụng toán tử hoán vị. Cũng như biến đổi FT, DCT cũng coi dữ liệu đầu vào là tín hiệu ổn định (bất biến). Trong các chuẩn nén ảnh tĩnh vào video, người ta thường sử dụng DCT và IDCT có kích thước 8 mẫu. Bức ảnh hoặc khung ảnh video kích thước NxN được chia thành các khối không chồng chéo nhau hai chiều gọi là các ảnh con kích thước 8x8 rồi áp dụng biến đổi DCT hai chiều ở bộ mã hoá và áp dụng biến đổi IDCT ở bộ giải mã. Biến đổi DCT và IDCT 8 mẫu tạo thành các ma trận 8x8 theo công thức: Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh 2-D DCT = Xk,l = 4 )()( lckc ∑∑ = = ⎟⎠ ⎞⎜⎝ ⎛ +⎟⎠ ⎞⎜⎝ ⎛ +7 0 7 0 , 16 )12(cos 16 )12(cos m n nm lnkmx ππ (2.10) Trong đó k,l = 0,1,………..,7 2-D IDCT= xm,n = ∑∑ = = ⎟⎠ ⎞⎜⎝ ⎛ +⎟⎠ ⎞⎜⎝ ⎛ +7 0 7 0 lk, 16 1)l(2ncos 16 1)k(2mcosX 4 )()( k l lckc ππ (2.11) Trong đó m,n = 0,1,………..,7 và c(k),c(l) = ⎪⎩ ⎪⎨ ⎧ ≠+ = 0,1 0&,2/1 22 lk lk Thuật toán để tính 2-D DCT và IDCT là: thực hiện phép biến đổi 1-D lần lượt cho hàng rồi đến cột của ma trận. So sánh DCT và KLT Hiệu quả của biến đổi DCT trong việc giải tương quan tín hiệu ảnh tương đương với biến đổi Karhunen-Loeve (KLT). KLT là phép biến đổi theo khối tối ưu nhất cho nén dữ liệu ở khía cạnh thống kê bởi: nó có thể giải tương quan một cách tối ưu tín hiệu ảnh trong miền phép biến đổi (bằng cách tập trung hầu hết thông tin ảnh vào một số hệ số của phép biến đổi) và so với các phép biến đổi khác nó có thể tối thiểu hoá MSE giữa ảnh khôi phục và ảnh gốc. Nén và giải nén ảnh dựa theo phép biến đổi DCT trong JPEG JPEG là chuẩn nén số quốc tế đầu tiên cho các ảnh tĩnh có tông màu liên tục gồm cả ảnh đơn sắc và ảnh màu. Trong kỹ thuật này các khối ảnh kích thước 8x8 được áp dụng để thực hiện DCT, sau đó lượng tử hoá các hệ số rồi mã hoá entropy sau lượng tử. Đối với những ảnh màu RGB, để áp dụng kỹ thuật nén này, trước hết phải chuyển sang chế độ màu YUV (Y là thành phần chói, U và V là 2 thành phần màu). Thành phần độ chói là ảnh đơn sắc xám. Hai thành phần màu còn lại chứa thông tin về màu. Việc mã hoá và giải mã ảnh trong JPEG ở được thực hiện cho thành phần chói rồi màu. Sơ đồ khối bộ mã hoá và giải mã của JPEG như sau: Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh Hình 2.5. Sơ đồ bộ mã hoá theo chuẩn JPEG Hình 2.6. Sắp xếp Zigzag các hệ số DCT ở bộ mã hoá Hình 2.7. Sơ đồ khối bộ giải mã theo chuẩn JPEG Quá trình xử lý thành phần độ chói ở phía mã hoá được giải thích như sau: (a) Ảnh gốc được chia thành các khối ảnh (block) nhỏ kích thước 8x8 không chồng chéo lên nhau. Tiếp theo, giá trị của mỗi điểm ảnh ở Luận văn cao học ĐTVT 2004 – 2006 Đỗ Ngọc Anh mỗi khỗi khối ảnh sẽ được trừ đi 128. Lý do là do giá trị các điểm ảnh có giá trị từ 0 đến 255 (được mã hoá bởi 8 bít không dấu), áp dụng biến đổi DCT sẽ tạo ra các hệ số AC có dải giá trị từ -1023 đến +1023 (có thể được mã hoá bởi 11 bít có dấu). Nhưng hệ số DC lại có giải giá trị từ 0 đến 2040 (được mã hoá bởi 11 bít không dấu) và cần cách xử lý khác ở phần cứng hoặc phần mềm so với các hệ số AC. Chính vì thế việc trừ giá trị mỗi điểm ảnh đi 128 là để sau khi biến đổi DCT cả các hệ số DC và AC có cùng dải giá trị thuận lợi cho việc xử lý và biểu diễn. (b) Ở mỗi khối ảnh hai chiều kích thước 8x8, áp dụng biến đổi DCT để tạo ra mảng hai chiều các hệ số biến đổi. Hệ số có tương ứng với tần số không gian thấp nhất nhưng lại có giá trị lớn nhất được gọi là hệ số DC (một chiều), nó tỉ lệ với độ chói trung bình của cả khối ảnh 8x8. Các hệ số còn lại gọi là các hệ số AC (xoay chiều). Theo lý thuyết, biến đổi DCT không đem lại sự mất mát thông tin ảnh, mà đơn giản nó chỉ chuyển thông tin ảnh sang miền không gian mới thuật lợi hơn cho mã hoá ở bước tiếp theo. (c) Mảng hai chiều các hệ số biến đổi được lượng tử hoá sử dụng bộ lượng tử hóa tỉ lệ đồng nhất. Nghĩa là các hệ số sẽ được lượng tử hoá riêng lẻ và độc lập. Quá trình lượng tử hoá là dựa trên sinh lý của hệ thống mắt người: cảm nhận hình ảnh có độ nhậy kém hơn ở các hệ số tần số 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 ®æ._.