Luận văn thạc sĩ: Wavelet và nén hiệu ảnh.pdf (Nén hiệu ảnh)

-1- BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG LÊ TỰ QUỐC WAVELET VÀ NÉN TÍN HIỆU ẢNH Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng - Năm 2011 -2- Công trình ñược hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: PGS. TS. Lê Văn Sơn Phản biện 1: TS. Nguyễn Tấn Khôi Phản biện 2: PGS.TS. Lê Mạnh Thạnh Luận văn ñược bảo vệ trước Hội ñồng chấm Luận văn tốt nghiệp thạc sĩ kỹ thuật họp tại Đại học Đà Nẵng vào ngày 11 tháng 9 năm 2011. * Có thể tìm hiểu luận văn tại: - Trung tâm Thông tin - Học liệu, Đại học Đà Nẵng. - Trung tâm Học liệu, Đại học Đà Nẵng. -3- MỞ ĐẦU 1. Lý do chọn ñề tài Hiện nay, việc truyền tín hiệu ña phương tiện trên mạng toàn cầu ñã trở thành một nhu cầu không thể thiếu ñược. Các tín hiệu ña phương tiện bao gồm âm thanh, hình ảnh và các ñoạn phim video ñều mang ñặc ñiểm chung là kích thước lớn trong việc lưu trữ và truyền tin. Nhu cầu nén tín hiệu trước khi truyền qua mạng và giải nén ở máy trạm (nơi nhận) trở nên cấp thiết vì nó tiết kiệm ñáng kể chi phí việc truyền tải. Các giải thuật nén cho các tín hiệu ña phương tiện ñã và ñang ñược phát triển với nhiều kết qủa khả quan. Các giải thuật này ñều là các giải thuật nén mất thông tin ñể có thể nén với tỷ số nén cao. Tuy nhiên các giải thuật nén mất thông tin ñều rất nhạy cảm với sai sót trên ñường truyền. Chỉ cần sai một vài bít thì kết quả giải nén của một ảnh có thể bị sai biệt hoàn toàn. Xuất phát từ những nhu cầu như vậy tôi ñã chọn ñề tài “Wavelet và nén tín hiệu ảnh”. Trong ñề tài này tôi chỉ tập trung nghiên cứu về việc nén hình ảnh bằng cách mã hóa tín hiệu hình ảnh bằng giải thuật nén mất thông tin, nhưng sẽ chấp nhận giảm bớt tỷ lệ nén ñể tín hiệu ảnh trở nên rõ ràng và mạnh mẽ hơn, nghĩa là cho phép tín hiệu bị mất mát một phần thông tin trong quá trình truyền trên ñường truyền, nhưng vẫn khôi phục lại ñược hầu hết thông tin của một bức ảnh. 2. Mục ñích nghiên cứu Xây dựng giải pháp ñể thực hiện việc nén hình ảnh sao cho tín hiệu hình ảnh có thể ñược khôi phục gần ñúng khi bị mất mát một số gói tin trong quá trình truyền trên ñường truyền và hình ảnh sau khi nhận ñược sẽ ñạt chất lượng tốt nhất có thể. -43. Đối tượng và phạm vi nghiên cứu Trong khuôn khổ của luận văn thuộc loại nghiên cứu và ứng dụng, tôi chỉ giới hạn nghiên cứu: - Lý thuyết về nén hình ảnh. - Giải thuật nén hình ảnh. 4. Phương pháp nghiên cứu - Nghiên cứu lý thuyết và một số thuật toán nén ảnh. - Nghiên cứu, triển khai và xây dựng các giải pháp ñể nén hình ảnh sao cho hình ảnh ít mất mát thông tin nhất trong quá trình truyền trên ñường truyền và hình ảnh sau khi nhận ñược ñạt chất lượng tốt nhất giống như ảnh gốc ban ñầu. 5. Ý nghĩa khoa học và thực tiễn của ñề tài Sau khi thực hiện và nghiên cứu phép biến ñổi Wavelet dùng trong việc nén tín hiệu hình ảnh giúp cho chúng ta tiết kiệm ñược thời gian truyền ảnh qua mạng và 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 (nơi tiếp nhận), quá trình giải mã sẽ ñược 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 ban ñầu nhưng vẫn thoả mãn ñược chất lượng yêu cầu, ñảm bảo ñủ thông tin cần thiết của 1 bức ảnh. -56. Cấu trúc của luận văn Bố cục của luận văn ñược tổ chức thành 3 chương, có nội dung như sau: Chương 1: Trình bày các khái niệm về các kiểu nén ảnh, các chuẩn liên quan ñến việc nén ảnh sao cho ñạt chất lượng ảnh tối ưu nhất và các hàm toán học liên quan ñến việc nén ảnh ñể làm cơ sở tiền ñề ñể sử dụng phép biến ñổi Wavelet trong việc nén tín hiệu ảnh. Chương 2: Đi sâu vào việc trình bày các họ hàm liên quan ñến phép biến biến ñổi Wavelet và vận dụng phép biến ñổi Wavelet ñể triển khai việc nén tín hiệu ảnh. Chương 3: Đưa ra giải pháp ñể cải tiến giải thuật mã hóa cây triệt tiêu ñể các cây có thể mã hóa nằm lọt hoàn toàn vào các gói tin. Các gói tin này có thể ñược giải mã ñộc lập. Vì vậy, mỗi gói tin bị mất sẽ chỉ ảnh hưởng ñến một vùng nhỏ của ảnh. Từ ñó làm cho chất lượng hình ảnh ñược rõ nét và ñạt ñược kết quả tốt hơn. -6- Chương 1. TỔNG QUAN VỀ NÉN TÍN HIỆU ẢNH 1.1. TỔNG QUAN VỀ NÉN TÍN HIỆU ẢNH Trong chương này, tôi sẽ trình bày các nguyên lý của nén tín hiệu ảnh, bao gồm nén ảnh không mất thông tin và nén ảnh mất thông tin. Phần nén ảnh mất thông tin sẽ giới thiệu phương pháp nén số học sẽ ñược dùng trong phần cài ñặt ở bước mã hóa Entropy của quy trình nén ảnh mất thông tin. 1.2. CÁC KIỂU NÉN Một tính chất chung nhất của tất cả các ảnh ñó là tương quan giữa các pixel ở cạnh nhau lớn, ñiều này dẫn ñến dư thừa thông tin ñể biểu diễn ảnh. Dư thừa thông tin sẽ làm cho việc mã hoá không tối ưu. Do ñó công việc cần làm ñể nén ảnh là phải tìm ñược các cách biểu diễn ảnh với tương quan nhỏ nhất ñể giảm thiểu ñộ dư thừa thông tin của ảnh. Thực tế, có hai kiểu dư thừa thông tin ñược phân loại như sau: - Dư thừa trong miền không gian: tương quan giữa các giá trị pixel của ảnh, ñiều này có nghĩa rằng các pixel lân cận của ảnh có giá trị gần giống nhau (trừ những pixel ở giáp ñường biên ảnh). - Dư thừa trong miền tần số: Tương quan giữa các mặt phẳng màu hoặc dải phổ khác nhau. Trọng tâm của các nghiên cứu về nén ảnh là tìm cách giảm số bít cần thiết ñể biểu diễn ảnh bằng việc loại bỏ dư thừa trong miền không gian và miền tần số càng nhiều càng tốt. Nén tín hiệu ảnh là làm giảm số lượng các bít cần thiết ñể biễu diễn một ảnh cho trước. Mục ñích của việc nén tín hiệu ảnh là ñể dễ dàng lưu trữ và truyền tải dữ liệu. Để nén tín hiệu ảnh người ta sử dụng một dãy các phép biến ñổi dữ liệu mà khi biến ñổi ngược lại -7có thể khôi phục lại hoàn toàn chính xác ảnh gốc hoặc xấp xỉ gần giống như ảnh gốc ban ñầu. Điều ñó có nghĩa là nén tín hiệu ảnh ñược chia làm hai loại: - Loại nén ảnh không mất thông tin (có thể không phục lại hoàn toàn ảnh gốc). - Loại nén ảnh mất thông tin (có thể khôi phục lại xấp xỉ với ảnh gốc ban ñầu). Cả hai loại trên ñều ñược sử dụng rộng rãi và tùy vào mỗi ứng dụng cụ thể mà sử dụng loại nào cho tối ưu hơn và thích hợp hơn. Mã hóa không mất thông tin không ñòi hỏi chất lượng của dữ liệu và ứng dụng của nó bị giới hạn kết quả ñạt ñược khá khiêm tốn. Nén ảnh không mất thông tin thường ñược dùng cho ảnh trong y học và trong khoa học không gian, do vấn ñề pháp lý và tính duy nhất của dữ liệu. Một lĩnh vực ñáng chú ý trong lĩnh vực này liên quan ñến những vấn ñề cốt tử, chẳng hạn tòa án Hoa Kỳ lưu trữ những ảnh vân tay ñược số hóa không mất thông tin, tuy nhiên cũng ñã chuyển sang nén mất thông tin do cần thiết. Nén ảnh mất thông tin có thể cung cấp tỷ lệ nén cao hơn rất nhiều lần so với nén ảnh không mất thông tin, tùy thuộc vào kiểu dữ liệu và mức ñộ mất thông tin mà chúng ta có thể chấp nhận ñược. Nén ảnh mất thông tin ñuợc sử dụng trong việc truyền và duyệt Internet, những ứng dụng thương mại, những hội nghị trực tuyến qua video. Các máy quay video thông thường trong gia ñình thường áp dụng nén ảnh mất thông tin ñể dễ dàng lưu trữ dữ liệu video phức tạp, nhưng lại tái hiện hình ảnh với mức ñộ trung thực chấp nhận ñược cho việc sử dụng trong gia ñình. -8Nhiều ý tưởng và cách tiếp cận ñã ñược ñưa ra ñể ñạt ñược việc nén ảnh mất thông tin và không mất thông tin theo những triết lý riêng biệt và theo từng bài toán. Kết quả ñạt ñược bởi nhóm những giải thuật dẫn ñầu trong mỗi loại không sai biệt nhau nhiều, ñiều ñó chỉ ra rằng có những nguyên lý cơ bản nằm dưới tất cả các giải thuật ñó. Thực tế thì tất cả các kỹ thuật nén ảnh là dựa trên sự hiện hữu của hai ñặc tính trong dữ liệu ñể ñạt ñược việc giảm thiểu có lợi: sự dư thừa và sự không thích hợp. Một ví dụ tầm thường của sự dư thừa dữ liệu là một chuỗi nhị phân gồm toàn các số zero (số 0) hay là toàn số 1, nó không chứa ñựng thông tin và có thể ñược mã hóa bởi chỉ một bít và chiều dài của chuỗi ñể giải mã một cách chính xác. Một ví dụ quan trọng của dữ liệu không thích hợp xuất hiện trong ảnh ñộ xám với quá nhiều mức xám, ví dụ như là 12 bít hay nhiều hơn 12 bít. Kinh nghiệm thực tế cho thấy ảnh ñơn sắc 6 ñến 8 bít là giới hạn của ñộ nhạy thị giác. Bất cứ bít thêm vào nào cũng ñều không làm tăng thêm khả năng quan sát (không làm thấy rõ hơn) và có thể loại bỏ. Số lượng lớn các giải thuật nén chủ yếu khác nhau trong cách tiếp cận ñể rút ra và tận dụng hai ñặc tính dư thừa và không thích hợp này. Quan ñiểm trên cho thấy một sự khác biệt giữa mã hóa mất thông tin và mã hóa không mất thông tin. - Mã hóa không mất thông tin chỉ dựa vào ñặc tính dư thừa của dữ liệu, tận dụng những khả năng có thể xảy ra ký hiệu không giống nhau và khả năng ñoán trước ký hiệu. Nói một cách khác chuỗi các ký hiệu càng nhiều thông tin, càng xuất hiện ngẫu nhiên nhiều thì càng khó ñể mã hóa mà không mất thông tin. Thông tin trù -9mật, có ít sự dư thừa và khả năng mã hóa không mất thông tin là những khái niệm gần như ñồng nhất. - Mã hóa mất thông tin dựa trên một ñặc tính khác của dữ liệu: sự không thích hợp. Trong bất kỳ hệ thống xử lý ảnh nào, nếu các yêu cầu thực hiện không cần mức ñộ chính xác (ñộ phân giải không gian-thời gian hay khoảng biễu diễn) của dữ liệu, sự chính xác quá ñáng có thể ñược loại bỏ mà không làm mất ñi sự thể hiện. Ví dụ ảnh mức xám, khoảng biễu diễn dùng 8 bít là ñủ. Như sẽ thấy sau này, sau khi áp dụng những phép biến ñổi chọn lọc một cách khéo léo, ngay cả những ảnh 8 bít cũng có thể cho phép loại bỏ một ít dữ liệu cũng không làm giảm ñến chất lượng của ảnh. Phương pháp mã hóa mất thông tin sử dụng phép biến ñổi Wavelet ñể tách phần thích hợp với phần không thích hợp là chủ ñề chính của ñề tài. 1.3. NÉN ẢNH KHÔNG MẤT THÔNG TIN Nén ảnh không mất thông tin là một nhánh của lý thuyết thông tin do Claude Shannon ñề xuất trong một lý thuyết toán học về truyền tin. Về cơ bản, một kênh truyền tin ñược mô hình hóa như là sự truyền của một chuỗi vô tận các ký hiệu, mỗi một ký hiệu ñược rút ra từ một bộ chữ cái (alphabet) xác ñịnh. Những ký hiệu có thể xuất hiện theo một quy luật xác suất nào ñó và kênh truyền tin có thể bị “nhiễu”. Việc sử dụng hiệu qủa kênh truyền tin như vậy ñể truyền tin ñặt ra: 0 ≤ H ≤ Log 2 N = L Trong ñó: - H = 0 khi và chỉ khi tất cả ký hiệu (ngoại trừ 1) có xác suất = 0 và ký hiệu còn lại có xác suất ñơn vị. -10- H = Log2N = L khi và chỉ khi tất cả các ký hiệu có cùng xác suất, trong trường hợp này là 1 . N Trong thực tế ta luôn mã hóa những chuỗi ký hiệu hữu hạn. Tuy nhiên, ñộ ño Entropy nói trên ñược dùng như là tỷ lệ chuẩn cần ñạt ñến trong lĩnh vực này và hoàn toàn có giá trị. Kỹ thuật mã hóa không mất thông tin cố gắng làm giảm một dòng dữ liệu ñến mức Entropy của nó. Một cách tự nhiên, dòng dữ liệu càng dài và con số thống kê của dữ liệu càng ổn ñịnh thì những kỹ thuật này càng thành công trong việc tiếp cận ñến mức Entropy. Sau ñây là một số kỹ thuật mã hóa. 1.3.1. Điều xung mã vi sai (DPCM-Differential Pulse Coded Modulation) 1.3.2. Mã hóa Huffman 1.3.3. Mã hóa số học 1.4. LƯỢNG TỬ HÓA 1.5. NÉN ẢNH MẤT THÔNG TIN Giải thuật nén ảnh mất thông tin rất ña dạng, chúng ta chỉ giới hạn sự quan tâm ñến các cách mã hóa dùng phép biến ñổi. Mã hóa mất thông tin bao gồm ba khối là: - Biến ñổi. - Lượng tử hóa. - Mã hóa Entropy. Phép biến ñổi làm giảm tương quan và thu gọn vùng dữ liệu, lượng tử hóa cấp phát số bít cần thiết trên mỗi ký hiệu với ñộ chính xác tối ña như mong muốn. Bộ mã hóa biến ñổi dữ liệu ñã ñược

Luận văn thạc sĩ: Wavelet và nén hiệu ảnh

Nội dung