Xử Lý Ảnh Chương 8 Final

Chia sẻ bởi Thái Thanh Tùng | Ngày 14/10/2018 | 26

Chia sẻ tài liệu: Xử Lý Ảnh Chương 8 Final thuộc Tư liệu tham khảo

Nội dung tài liệu:

8

nén dữ liệu ảnh
image compression
8.1 Tổng quan về nén dữ liệu ảnh
Chương này nhằm cung cấp một số khái niệm (thuật ngữ) như: nén, tỉ lệ nén, các ý tưởng dẫn tới các phương pháp nén khác nhau và cách phân loại, đánh giá các phương pháp nén.
8.1.1 Một số khái niệm
Nén Dữ liệu (Data Compression)
Nén dữ liệu là quá trình làm giảm lượng thông tin "dư thừa" trong dữ liệu gốc và do vậy, lượng thông tin thu được sau nén thường nhỏ hơn dữ liệu gốc rất nhiều. Với dữ liệu ảnh, kết quả thường là 10 : 1. Một số phương pháp còn cho kết quả cao hơn. Theo kết quả nghiên cứu được công bố gần đây tại viện kỹ thuật Georgie, kỹ thuật nén fractal cho tỉ số nén là 30 trên 1[6].
Ngoài thuật ngữ "nén dữ liệu”, do bản chất của kỹ thuật này nó còn có một số tên gọi khác như: giảm độ dư thừa, mã hoá ảnh gốc.
Từ hơn hai thập kỷ nay, có rất nhiều kỹ thuật nén đã được công bố trên các tài liệu về nén và các phần mềm nén dữ liệu đã xuất hiện ngày càng nhiều trên thương trường. Tuy nhiên, chưa có phương pháp nén nào được coi là phương pháp vạn năng (Universel) vì nó phụ thuộc vào nhiều yếu tố và bản chất của dữ liệu gốc. Trong chương này, chúng ta không thể hy vọng xem xét tất cả các phương pháp nén. Hơn nữa, các kỹ thuật nén dữ liệu chung đã được trình bày trong nhiều tài liệu chuyên ngành. ở đây, chúng ta chỉ đề cập các phương pháp nén có đặc thù riêng cho dữ liệu ảnh.
Tỷ lệ nén (Compression rate)
Tỷ lệ nén là một trong các đặc trưng quan trọng nhất của mọi phương pháp nén. Tuy nhiên, về cách đánh giá và các kết quả công bố trong các tài liệu cũng cần được quan tâm xem xét . Nhìn chung, người ta định nghĩa tỷ lệ nén như sau:
Tỷ lệ nén = x %
với r là tỷ số nén được định nghĩa: r = kích thước dữ liệu gốc/ kích thước dữ liệu thu được sau nén. Như vậy hiệu suất của nén là : (1 - tỷ lệ nén) x %.
Trong các trình bày sau, khi nói đến kết quả nén, chúng ta dùng tỷ số nén, thí dụ như 10 trên 1 có nghĩa là dữ liệu gốc là 10 phần sau khi nén chỉ có 1 phần.
Tuy nhiên, cũng phải thấy rằng những số đo của một phương pháp nén chỉ có giá trị với chính sự nén đó, vì rằng hiệu quả của nén còn phụ thuộc vào kiểu dữ liệu định nén. Tỷ lệ nén cũng chỉ là một trong các đặc trưng cơ bản của phương pháp nén. Nhiều khi tỷ lệ nén cao cũng chưa thể nói rằng phương pháp đó là hiệu quả hơn các phương pháp khác, vì còn các chi phí khác như thời gian, không gian và thậm chí cả độ phức tạp tính toán nữa. Thí dụ như nén phục vụ trong truyền dữ liệu: vấn đề đặt ra là hiệu quả nén có tương hợp với đường truyền không.
Cũng cần phân biệt nén dữ liệu với nén băng truyền. Mục đích chính của nén là giảm lượng thông tin dư thừa và dẫn tới giảm kích thước dữ liệu. Tuy vậy, đôi khi quá trình nén cũng làm giảm băng truyền tín hiệu số hoá thấp hơn so với truyền tín hiệu tương tự.
8.1.2 Các loại dư thừa dữ liệu
Như trên đã nói, nén nhằm mục đích giảm kích thước dữ liệu bằng cách loại bỏ dư thừa dữ liệu. Việc xác định bản chất các kiểu dư thừa dữ liệu rất có ích cho việc xây dựng các phương pháp nén dữ liệu khác nhau. Nói một cách khác, các phương pháp nén dữ liệu khác nhau là do sử dụng các kiểu dư thừa dữ liệu khác nhau. Người ta coi có 4 kiểu dư thừa chính:
Sự phân bố ký tự
Trong một dãy ký tự, có một số ký tự có tần suất xuất hiện nhiều hơn một số dãy khác. Do vậy, ta có thể mã hoá dữ liệu một cách cô đọng hơn. Các dãy ký tự có tần xuất cao được thay bởi một từ mã nhị phân với số bít nhỏ; ngược lại các dãy có tần xuất thấp sẽ được mã hoá bởi từ mã có nhiều bít hơn. Đây chính là bản chất của phương pháp mã hoá Huffman (xem mục 8.2.2).
Sự lặp lại của các ký tự
Trong một số tình huống như trong ảnh, 1 ký hiệu (bít "0" hay bít "1") được lặp đi lặp lại một số lần. Kỹ thuật nén dùng trong trường hợp này là thay dãy lặp đó bởi dãy mới gồm 2 thành phần: số lần lặp và kí hiệu dùng để mã. Phương pháp mã hoá kiểu này có tên là mã hoá loạt dài RLC (Run Length Coding). Phương pháp mã hoá RLC sẽ được trình bày trong mục 8.2.1.
Những mẫu sử dụng tần suất
Có thể có dãy ký hiệu nào đó xuất hiện với tần suất tương đối cao. Do vậy, có thể mã hoá bởi ít bít hơn. Đây là cơ sở của phương pháp mã hoá kiểu từ điển do Lempel-Ziv đưa ra và có cải tiến vào năm 1977, 1978 và do đó có tên gọi là phương pháp nén LZ77, LZ78. Năm 1984, Terry Welch đã cải tiến hiệu quả hơn và đặt tên là LZW (Lempel-Ziv- Welch). Phương pháp nén này sẽ được trình bày trong 8.2.3.
Độ dư thừa vị trí
Do sự phụ thuộc lẫn nhau của dữ liệu, đôi khi biết được ký hiệu (giá trị) xuất hiện tại một vị trí, đồng thời có thể đoán trước sự xuất hiện của các giá trị ở các vị trí khác nhau một cách phù hợp. Chẳng hạn, ảnh biểu diễn trong một lưới hai chiều, một số điểm ở hàng dọc trong một khối dữ lệu lại xuất hiện trong cùng vị trí ở các hàng khác nhau. Do vậy, thay vì lưu trữ dữ liệu, ta chỉ cần lưu trữ vị trí hàng và cột. Phương pháp nén dựa trên sự dư thừa này gọi là phương pháp mã hoá dự đoán.
Cách đánh giá độ dư thừa như trên hoàn toàn mang tính trực quan nhằm biểu thị một cái gì đó xuất hiện nhiều lần. Đối với dữ liệu ảnh, ngoài đặc thù chung đó, nó còn có những đặc thù riêng. Thí dụ như có ứng dụng không cần toàn bộ dữ liệu thô của ảnh mà chỉ cần các thông tin đặc trưng biểu diễn ảnh như biên ảnh hay vùng đồng nhất. Do vậy, có những phương pháp nén riêng cho ảnh dựa vào biến đổi ảnh hay dựa vào biểu diễn ảnh. Các phương pháp này sẽ lần lượt trình bày trong mục 8.3 và 8.4.
8.1.3 Phân loại các phương pháp nén
Có nhiều cách phân loại các phương pháp nén khác nhau. Cách thứ nhất dựa vào nguyên lý nén. Cách này phân các phương pháp nén thành 2 họ lớn:
Nén chính xác hay nén không mất thông tin: họ này bao gồm các phương pháp nén mà sau khi giải nén ta thu được chính xác dữ liệu gốc.
Nén có mất mát thông tin: họ này bao gồm các phương pháp mà sau khi giải nén ta không thu được dữ liệu như bản gốc. Trong nén ảnh, người ta gọi là các phương pháp "tâm lý thị giác". Các phương pháp này lợi dụng tính chất của mắt người, chấp nhận một số vặn xoắn trong ảnh khi khôi phục lại. Tất nhiên, các phương pháp này chỉ có hiệu quả khi mà độ vặn xoắn là chấp nhận được bằng mắt thường hay với dung sai nào đó.
Cách phân loại thứ hai dựa vào cách thức thực hiện nén. Theo cách này, người ta cũng phân thành hai họ:
Phương pháp không gian (Spatial Data Compression): các phương pháp thuộc họ này thực hiện nén bằng cách tác động trực tiếp lên việc lấy mẫu của ảnh trong miền không gian.
Phương pháp sử dụng biến đổi (Transform Coding): Gồm các phương pháp tác động lên sự biến đổi của ảnh gốc mà không tác động trực tiếp như họ trên [6].
Có một cách phân loại khác nữa, cách phân loại thứ ba, dựa vào triết lý của sự mã hoá. Cách này cũng phân các phương pháp nén thành 2 họ:
Các phương pháp nén thế hệ thứ nhất: Gồm các phương pháp mà mức độ tính toán là đơn giản, thí dụ như việc lấy mẫu, gán từ mã, v,..., v.
Các phương pháp nén thế hệ thứ hai: Dựa vào mức độ bão hoà của tỷ lệ nén.
Trong các phần trình bày dưới đây, ta sẽ theo cách phân loại này.
Cũng còn phải kể thêm một cách phân loại thứ tự do Anil.K.Jain nêu ra. Theo cách của Jain, các phương pháp nén gồm 4 họ chính:
Phương pháp điểm.
Phương pháp dự đoán.
Phương pháp dựa vào biến đổi.
Các phương pháp tổ hợp (Hybrid).
Thực ra cách phân loại này là chia nhỏ của cách phân loại thứ ba và dựa vào cơ chế thực hiện nén. Xét một cách kỹ lưỡng nó cũng tương đương cách phân loại thứ ba.
Nhìn chung, quá trình nén và giải nén dữ liệu có thể mô tả một cách tóm tắt theo sơ đồ hình 8.1 dưới đây.

Quá trình nén
Dữ liệu gốc Dữ liệu nén
Quá trình giải nén

Hình 8.1 Sơ đồ chức năng quá trình nén dữ liệu

8.2 Các phương pháp nén thế hệ thứ nhất
Trong lớp các phương pháp này, ta lần lượt xem xét các phương pháp:
- Mã hoá loạt dài RLC (Run Length Coding)
- Mã hoá Huffman
- Mã hoá LZW(Lempel Ziv-Wench)
- Mã hoá khối (Block Coding).
8.2.1 Phương pháp mã hoá loạt dài
Phương pháp mã hoá loạt dài lúc đầu được phát triển dành cho ảnh số 2 mức: mức đen (1) và mức trắng (0) như các văn bản trên nền trắng, trang in, các bức vẽ kỹ thuật.
Nguyên tắc của phương pháp là phát hiện một loạt các bít lặp lại, thí dụ như một loạt các bit 0 nằm giữa hai bit 1, hay ngược lại, một loạt bit 1 nằm giữa hai bit 0. Phương pháp n

* Một số tài liệu cũ có thể bị lỗi font khi hiển thị do dùng bộ mã không phải Unikey ...

Người chia sẻ: Thái Thanh Tùng

Dung lượng: 1,08MB| Lượt tài: 0

Loại file: DOC

Nguồn : Chưa rõ

(Tài liệu chưa được thẩm định)

Tải tài liệu

Báo cáo sai sót

Đề suất chỉnh sửa , phân lại mục