ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYÊN THÔNG
NGUYỄN HÀ AN
MỘT SỐ KĨ THUẬT NÉN ẢNH VÀ ỨNG DỤNG
LUẬN VĂN THẠC SĨ: CÔNG NGHỆ THÔNG TIN
Thái Nguyên, năm 2014
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
ii
LỜI CẢM ƠN
Trên thực tế không có thành công nào mà không gắn liền với những sự hỗ trợ,
giúp đỡ dù ít hay nhiều, dù trực tiếp hay gián tiếp của người khác. Trong suốt thời
gian học tập tại trường Đại học Công nghệ thông tin và Truyền thông – Đại học Thái
Nguyên tôi đã nhận được rất nhiều sự giúp đỡ của thầy cô, bố mẹ, bạn bè và những
người thân.
Với lòng biết ơn sâu sắc tôi xin chân thành cảm ơn đến quý thầy cô trong trường
Đại Học Công nghệ thông tin và Truyền thông – Đại học Thái Nguyên, đặc biệt thày
PGS.TS. Phạm Việt Bình, cùng với các quý thầy cô ở Viện Công nghệ thông tin, đặc
biệt thày PGS.TS. Đỗ Năng Toàn, PGS.TS. Đặng Văn Đức, PGS.TSKH. Nguyễn
Xuân Huy, đã truyền đạt vốn kiến thức quý báu cho tôi. Và đặc biệt các thầy cô đã
tạo điều kiện cho tôi làm luận văn tốt nghiệp với đề tài: “Một số kỹ thuật nén ảnh và
ứng dụng”.
Xin chân thành cám ơn các thầy cô công tác tại Phòng Đào tạo, trường Đại học
công nghệ thông tin và truyền thông, Đại học Thái Nguyên, đặc biệt thầy Lê Hùng
Linh và cô Vân đã tạo điều kiện để các học viên Hải Phòng hoàn thành khóa đào tạo
sau đại học về công nghệ thông tin.
Tôi xin chân thành cảm ơn thầy Đỗ Trung Tuấn đã tận tình giúp đỡ hướng dẫn
tôi qua từng buổi học trên lớp cũng như nhưng buổi nói chuyện thảo luận nghiên cứu
đề tài. Nếu không có sự hướng dẫn, chỉ bảo tận tình của thầy thì thiết nghĩ bài báo
cáo này sẽ khó có thể hoàn thành được.
Với đề tài còn khá mới mẻ và vốn kiến thức còn hạn chế nên bài tiểu luận còn có
nhiều sai sót trong quá trình tiếp cận đề tài. Tôi rất mong sự góp ý của các quý thầy
cô và các bạn để bài tiểu luận được hoàn thiện hơn nữa. Một lần nữa tôi xin chân
thành cảm ơn thầy cô và các bạn.
Học viên gửi lời biết ơn đến gia đình và người thân, đã chia sẻ những khó khăn
trong việc hoàn thành khóa học và viết luận văn này.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
iii
MỤC LỤC
LỜI CẢM ƠN..............................................................................................................ii
DANH MỤC TỪ VIẾT TẮT VÀ NGHĨA CỦA TỪ VIẾT TẮT ........................... v
DANH MỤC CÁC BẢNG, HÌNH VẼ......................................................................vi
PHẦN MỞ ĐẦU.......................................................................................................... 1
CHƢƠNG 1 ................................................................................................................. 3
KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ BÀI TOÁN NÉN ẢNH .................................. 3
1.1. Khái quát về xử lý ảnh....................................................................................... 3
1.1.1. Giới thiệu.................................................................................................... 3
1.1.2. Một số vấn đề trong xử lý ảnh. .................................................................. 4
1.1.2.1. Một số khái niệm cơ bản ......................................................................... 4
1.1.2.2. Nắn chỉnh biến dạng ............................................................................... 4
1.1.2.3. Khử nhiễu ................................................................................................ 5
1.1.2.6. Nhận dạng ............................................................................................... 6
1.1.2.7. Nén ảnh ................................................................................................... 7
1.2. Bài toán nén ảnh ................................................................................................ 8
1.2.1. Giới thiệu.................................................................................................... 8
1.2.2. Các cách tiếp cận bài toán nén ảnh .......................................................... 10
1.3. Kết luận chương .............................................................................................. 10
CHƢƠNG 2 ............................................................................................................... 11
MỘT SỐ KĨ THUẬT NÉN ẢNH ............................................................................ 11
2.1. Nén bảo toàn .................................................................................................... 11
(Run-Length Encoding) .......... 12
2.1.1.1. Ý tưởng của thuật toán .......................................................................... 12
2.1.1.2. Thuật toán.............................................................................................. 14
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
iv
............................................................................ 14
2.1.3. Đánh giá thuật toán .................................................................................. 20
2.2. Nén không bảo toàn ......................................................................................... 21
2.2.1. Nén JPEG ................................................................................................. 22
2.2.1.1. Ý tưởng của thuật toán .......................................................................... 22
2.2.1.2. Thuật toán nén ảnh JPEG ...................................................................... 22
2.2.2. Kỹ thuật nén AIC (Advanced Image Coding) ......................................... 28
2.2.2.1. Giới thiệu............................................................................................... 29
2.2.2.2. Nén và chất lượng ảnh AIC khi so sánh với JPEG và JPEG-2000 ....... 30
2.2.2.3. Thuật toán AIC ...................................................................................... 30
2.2.2.4. Các kết quả - AIC.................................................................................. 42
1.3. Kết luận chương .............................................................................................. 42
CHƢƠNG 3 ............................................................................................................... 43
CHƢƠNG TRÌNH ỨNG DỤNG TRUYỀN ẢNH QUA MẠNG ......................... 43
3.1. Bài toán truyền ảnh qua mạng ......................................................................... 43
3.2. Lựa chọn chương trình nén ảnh trên JPEG ..................................................... 43
3.3. Thử nghiệm nén ảnh JPEG .............................................................................. 44
3.3.1. Sơ đồ thực hiện bài toán ứng dụng .......................................................... 44
3.3.2. Các tham số thử nghiệm ........................................................................... 45
3.3.3. Một số kết quả thử nghiệm....................................................................... 46
3.3.4. Đánh giá chương trình thử nghiệm .......................................................... 51
3.4. Kết luận chương .............................................................................................. 51
KẾT LUẬN ................................................................................................................ 52
...................................................................................... 52
2. Một số hạn chế ............................................................................................... 52
................................................................ 53
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
v
TÀI LIỆU THAM KHẢO ........................................................................................ 54
PHỤ LỤC................................................................................................................... 55
DANH MỤC TỪ VIẾT TẮT VÀ NGHĨA CỦA TỪ VIẾT TẮT
3D
Ba chiều
DIB
Device Independent Bitmap
DTC
Disrete Cosine Transformation
FDCT
Forward Disrete Cosine Transformation
IDCT
Inverse Disrete Cosine Transformation
MPEG
JPEG
Joint Photographic Expert Group
ES
Bar
Vạch
camera
Máy chụp ảnh, có thể dùng như máy quay video
VHS
FORTRAN
Ngôn ngữ lập trình FORTRAN
Fourier
Tên nhà toán học, đề xuất phép biến đổi tín hiệu
AIC
Advanced Image Coding
IPTV
Truyền hình số IP
IT
Công nghệ thông tin
PSNR
Peak Signal to Noise Ratio
pixel
Điểm ảnh
RGB
Ba màu đỏ, lục, xanh lam
toolbox
Hộp công cụ
PEL
Picture Element
AVC
Advanced Video Coding
CABAC
Context adaptive binary arithmetic coding
ITU-T
Liên hiệp viễn thông quốc tế
ISO/IEC
Tổ chức tiêu chuẩn hóa quốc tế và Ủy ban kỹ thuật
điện tử quốc tế
PSNR
tỉ số tín hiệu đỉnh trên nhiễu
LZW
Jacob và Abraham Ziv
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
vi
DANH MỤC CÁC BẢNG, HÌNH VẼ
Hình 1. 1. Quá trình xử lý ảnh ........................................................................... 3
Hình 1. 2. Các bước cơ bản trong một hệ thống xử lý ảnh ............................... 4
Hình 1. 3. Ảnh thu nhận và ảnh mong muốn .................................................... 4
Hình 1. 4. Quá trình hiển thị và chỉnh sửa, lưu trữ ảnh thông qua DIB ............ 9
Hình 1.5. Sự chuyển đổi giữa các mô hình biểu diễn ảnh ................................. 9
Bảng 2.1. Cấu trúc từ điển của các phần tử mã ............................................... 15
Bảng 2.2. Ví dụ cơ chế nén LZW .................................................................... 16
Hình 2.3. Sơ đồ thuật toán nén LZW .............................................................. 18
Hình 2.5: Quá trình nén ảnh theo chuẩn JPEG................................................ 22
Hình 2.6. Quá trình giải nén ảnh theo chuẩn JPEG. ........................................ 23
Hình 2.7: Hình minh họa về khối Zig-Zag. ..................................................... 28
Hình 2.8. So sánh ảnh gốc và ảnh nén ............................................................. 30
Hình 2.9. Sơ đồ khối nén AIC và giải nén AIC. ............................................. 31
Hình 2.10. Ảnh chuyển đổi sang kênh RGB. .................................................. 31
Hình 2.11. Ảnh chuyển đổi sang kênh YCbCr ................................................ 32
Hình 2.12. Hình ảnh khi chia thành các khối. ................................................. 33
Hình 2.13. Khối 8x8 với 25 điểm ảnh. ............................................................ 34
Hình 2.14. Các chế độ dự đoán khối ............................................................... 36
Hình 2.15. Quá trình dự đoán .......................................................................... 37
Hình 2.16. Ảnh độ chói dư thừa ...................................................................... 38
Hình 2.17. Hình so sánh các kỹ thuật nén ảnh khác nhau. .............................. 42
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
vii
Hình 3.1. Sơ đồ nén ảnh bằng JPEG ............................................................... 44
Hình 3.2. Sơ đồ thực hiện bài toán ứng dụng .................................................. 45
Hình 3.3. Giao diện chương trình ứng dụng .................................................... 46
Hình 3.4. Giao diện chương trình chạy thử ..................................................... 47
Hình 3.5. Cửa sổ thông báo hoàn tất quy trình nén ảnh .................................. 47
Hình 3.6. Kết quả sau khi thử nghiệm với ảnh *.gif ....................................... 48
Hình 3.7. Thử nghiệm với ảnh JPEG. ............................................................. 50
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
PHẦN MỞ ĐẦU
Cuộc cách mạng thông tin kỹ thuật số đã đem lại những thay đổi sâu sắc trong xã
hội và trong cuộc sống của chúng ta. Bên cạnh những thuận lợi mà thông tin kỹ thuật số
mang lại cũng nảy sinh những thách thức mới cho quá trình đổi mới này. Sự ra đời
những phần mềm có tính năng rất mạnh, các thiết bị mới như máy ảnh kỹ thuật số, máy
quét chất lượng cao, máy in, máy ghi âm kỹ thuật số…đã giúp con người có thể sáng
tạo, xử lý và thưởng thức các dữ liệu đa phương tiện (multimedia data). Mạng Internet
toàn cầu đã biến thành một xã hội ảo, nơi diễn ra quá trình trao đổi thông tin trong mọi
lĩnh vực chính trị, quân sự, quốc phòng, kinh tế, thương mại...vv. Trao đổi thông tin qua
các kênh truyền thông công khai đã, đang và sẽ được sử dụng phổ biến trong kỷ nguyên
công nghệ số hiện đại này. Và chính trong môi trường mở và tiện nghi như thế xuất hiện
những khó khăn trong việc truyền tải một lượng lớn các file ảnh, file text, các file dữ
liệu đa phương tiện… đi cùng một lúc. Do vậy đã có rất nhiều phần mềm nén và giải
nén dữ liệu ra đời.
Hiện nay, phổ biến và được sử dụng nhiều nhất là phần mềm nén và giải nén
„WinRAR ZIP archive‟. Phần mềm này bổ trợ và hữu ích tiện lợi cho người sử dụng. Dù
dung lượng các file có lớn đến đâu chỉ cần nhấp chuột là nó trở nên nhỏ gọn và dễ dàng
gửi đi một cách nhanh chóng. Phần mềm nay rất dễ cài đặt và dễ sử dụng. Bên cạch đó
phần mềm Matlab cũng khá phổ biến và tiện ích trong các bài toán số học, logic …
ngoài ra phần mềm Matlab cũng được ứng dụng rộng dãi trong xử lý ảnh số (Indexed
Images), ảnh cường độ (Intensity Images), ảnh nhị phân (Binary Images), ảnh RGB
(RGB Images)….
Nén ảnh là một bộ phận chiếm tỉ lệ lớn nhất trong các chương trình ứng dụng, các
phần mềm nén dữ liệu sử dụng nhiều trong dữ liệu đa phương tiện bởi lượng thông tin
được trao đổi bằng hình ảnh và video là rất lớn và hơn nữa nén ảnh cũng đóng vai trò
hết sức quan trọng trong hầu hết các ứng dụng thông tin trên mạng internet cũng như
trong các trang web quản cáo. Chính vì thế mà vấn đề này đã nhận được sự quan tâm rất
lớn của các cá nhân, tổ chức, trường đại học, và viện nghiên cứu trên thế giới...vv.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
2
Tôi tin rằng lĩnh vực nghiên cứu này có nhiều hứa hẹn trong tương lai gần và dần trở
thành một hướng đi mới trong lĩnh vực nén ảnh trên ngôn ngữ lập trình C Sharp 2010.
Trong luận văn này chúng ta sẽ đi sâu vào nghiên cứu các kĩ thuật nén ảnh và sử dụng
ngôn ngữ lập trình C Sharp 2010 để giải quyết bài toán ứng dụng nén ảnh của mình.
Cấu trúc luận văn
Luận văn gồm có các chương:
Chương 1: Khái quát về xử lý ảnh và bài toán nén ảnh
Chương 2: Một số kĩ thuật nén ảnh
Chương 3: Chương trình ứng dụng truyền ảnh qua mạng
Cuối khóa luận là phần kết luận và danh sách các tài liệu tham khảo, phụ lục
chương trình.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
3
CHƢƠNG 1
KHÁI QUÁT VỀ XỬ LÝ ẢNH VÀ BÀI TOÁN NÉN ẢNH
1.1. Khái quát về xử lý ảnh
1.1.1. Giới thiệu
Con người thu nhận thông tin qua các giác quan, trong đó thị giác đóng vai trò
quan trọng nhất. Những năm trở lại đây với sự phát triển của phần cứng máy tính, xử lý
ảnh và đồ họa đó phát triển một cách mạnh mẽ và có nhiều ứng dụng trong cuộc sống.
Xử lý ảnh và đồ họa đóng vai trò quan trọng trong tương tác người máy.
Quá trình xử lý ảnh được xem như là quá trình thao tác ảnh đầu vào nhằm cho kết
quả mong muốn. Kết quả đầu ra của một quá trình xử lý ảnh có thể là một ảnh „tốt hơn‟
hoặc một kết luận.
Hình 1. 1. Quá trình xử lý ảnh
Ảnh có thể xem là tập hợp các điểm ảnh và mỗi điểm ảnh được xem như là đặc
trưng cường độ sáng hay một dấu hiệu nào đó tại một vị trí nào đó của đối tượng trong
không gian và nó có thể xem như một hàm n biến P(c1, c2, c3, ….., cn). Do đó, ảnh trong
xử lý ảnh có thể xem như ảnh n chiều.
Sơ đồ tổng quát của một hệ thống xử lý ảnh:
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
4
Hình 1.2. Các bƣớc cơ bản trong một hệ thống xử lý ảnh
1.1.2. Một số vấn đề trong xử lý ảnh.
1.1.2.1. Một số khái niệm cơ bản
* Ảnh và điểm ảnh:
Điểm ảnh được xem như là dấu hiệu hay cường độ sáng tại 1 toạ độ trong không
gian của đối tượng và ảnh được xem như là 1 tập hợp các điểm ảnh.
* Mức xám, màu
Là số các giá trị có thể có của các điểm ảnh của ảnh
1.1.2.2. Nắn chỉnh biến dạng
Ảnh thu nhận thường bị biến dạng do các thiết bị quang học và điện tử.
Hình 1.3. Ảnh thu nhận và ảnh mong muốn
Để khắc phục người ta sử dụng các phép chiếu, các phép chiếu thường được xây
dựng trên tập các điểm điều khiển.
Giả sử ( Pi , Pi ' )i 1, n có n các tập điều khiển
Tìm hàm f: Pi f ( Pi ) sao cho
2
n
f ( Pi
Pi
'
min
i 1
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
5
Giả sử ảnh bị biến đổi chỉ bao gồm: Tịnh tiến, quay, tỷ lệ, biến dạng bậc nhất
tuyến tính. Khi đó hàm f có dạng:
f (x, y) = (a1x + b1y + c1, a2x + b2y + c2)
Ta có:
n
n
( f ( Pi ) Pi ' ) 2
(a1 xi
i 1
a2 xi
b2 yi
c2
yi,
2
m
n
b1
xi, ) 2
c1
i 1
Để cho
a1
b1 yi
n
a1 xi2
i 1
n
n
b1 xi yi
i 1
n
c1
by
i 1
n
i 1
n
yi xi,
c1 yi
i 1
n
a1 x1
i 1
xi xi,
i 1
n
2
1 i
a1 xi yi
i 1
n
c1 xi
i 1
n
b1 yi
i 1
xi,
nc1
i 1
Giải hệ phương trình tuyến tính tìm được a1, b1, c1.
Tương tự tìm được a2, b2, c2.
⇒ Xác định được hàm f
1.1.2.3. Khử nhiễu
Có 2 loại nhiễu cơ bản trong quá trình thu nhận ảnh
Nhiễu hệ thống: là nhiễu có quy luật có thể khử bằng các phép biến đổi
Nhiễu ngẫu nhiên: vết bẩn không rõ nguyên nhân → khắc phục bằng các phép
lọc
1.1.2.4. Chỉnh mức xám
Nhằm khắc phục tính không đồng đều của hệ thống gây ra. Thông thường có 2
hướng tiếp cận:
Giảm số mức xám: Thực hiện bằng cách nhóm các mức xám gần nhau thành một
bó. Trường hợp chỉ có 2 mức xám thì chính là chuyển về ảnh đen trắng. Ứng
dụng: In ảnh màu ra máy in đen trắng.
Tăng số mức xám: Thực hiện nội suy ra các mức xám trung gian bằng kỹ thuật
nội suy. Kỹ thuật này nhằm tăng cường độ mịn cho ảnh
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
6
1.1.2.5. Trích chọn đặc điểm
Các đặc điểm của đối tượng được trích chọn tuỳ theo mục đích nhận dạng trong
quá trình xử lý ảnh. Có thể nêu ra một số đặc điểm của ảnh sau đây:
Đặc điểm không gian: Phân bố mức xám, phân bố xác suất, biên độ, điểm uốn
v.v..
Đặc điểm biến đổi: Các đặc điểm loại này được trích chọn bằng việc thực hiện
lọc vùng (zonal filtering). Các bộ vùng được gọi là “mặt nạ đặc 10 điểm” (feature mask)
thường là các khe hẹp với hình dạng khác nhau (chữ nhật, tam giác, cung tròn v.v..)
Đặc điểm biên và đƣờng biên: Đặc trưng cho đường biên của đối tượng và do
vậy rất hữu ích trong việc trích trọn các thuộc tính bất biến được dùng khi nhận dạng đối
tượng. Các đặc điểm này có thể được trích chọn nhờ toán tử gradient, toán tử la bàn,
toán tử Laplace, toán tử “chéo không” (zero crossing) v.v..
Việc trích chọn hiệu quả các đặc điểm giúp cho việc nhận dạng các đối tượng ảnh
chính xác, với tốc độ tính toán cao và dung lượng nhớ lưu trữ giảm xuống.
1.1.2.6. Nhận dạng
Nhận dạng tự động (automatic recognition), mô tả đối tượng, phân loại và phân
nhóm các mẫu là những vấn đề quan trọng trong thị giác máy, được ứng dụng trong
nhiều ngành khoa học khác nhau. Tuy nhiên, một câu hỏi đặt ra là: mẫu (pattern) là gì?
Watanabe, một trong những người đi đầu trong lĩnh vực này đã định nghĩa: “Ngược lại
với hỗn loạn (chaos), mẫu là một thực thể (entity), được xác định một cách ang áng
(vaguely defined) và có thể gán cho nó một tên gọi nào đó”. Ví dụ mẫu có thể là ảnh của
vân tay, ảnh của một vật nào đó được chụp, một chữ viết, khuôn mặt người hoặc một ký
đồ tín hiệu tiếng nói. Khi biết một mẫu nào đó, để nhận dạng hoặc phân loại mẫu đó có
thể:
Hoặc phân loại có mẫu (supervised classification), chẳng hạn phân tích phân
biệt (discriminant analyis), trong đó mẫu đầu vào được định danh như một thành phần
của một lớp đã xác định.
Hoặc phân loại không có mẫu (unsupervised classification hay clustering) trong
đó các mẫu được gán vào các lớp khác nhau dựa trên một tiêu chuẩn đồng dạng nào đó.
Các lớp này cho đến thời điểm phân loại vẫn chưa biết hay chưa được định danh.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
7
Hệ thống nhận dạng tự động bao gồm ba khâu tương ứng với ba giai đoạn chủ
yếu sau đây:
Thu nhận dữ liệu và tiền xử lý.
Biểu diễn dữ liệu.
Nhận dạng, ra quyết định.
Bốn cách tiếp cận khác nhau trong lý thuyết nhận dạng là:
Đối sánh mẫu dựa trên các đặc trưng được trích chọn.
Phân loại thống kê.
Đối sánh cấu trúc.
Phân loại dựa trên mạng nơ-ron nhân tạo.
Trong các ứng dụng rõ ràng là không thể chỉ dùng có một cách tiếp cận đơn lẻ để
phân loại “tối ưu” do vậy cần sử dụng cùng một lúc nhiều phương pháp và cách tiếp cận
khác nhau. Do vậy, các phương thức phân loại tổ hợp hay được sử dụng khi nhận dạng
và nay đã có những kết quả có triển vọng dựa trên thiết kế các hệ thống lai (hybrid
system) bao gồm nhiều mô hình kết hợp.
Việc giải quyết bài toán nhận dạng trong những ứng dụng mới, nảy sinh trong cuộc
sống không chỉ tạo ra những thách thức về thuật giải, mà còn đặt ra những yêu cầu về
tốc độ tính toán. Đặc điểm chung của tất cả những ứng dụng đó là những đặc điểm đặc
trưng cần thiết thường là nhiều, không thể do chuyên gia đề xuất, mà phải được trích
chọn dựa trên các thủ tục phân tích dữ liệu.
1.1.2.7. Nén ảnh
Nhằm giảm thiểu không gian lưu trữ. Thường được tiến hành theo cả hai cách
khuynh hướng là nén có bảo toàn và không bảo toàn thông tin. Nén không bảo toàn thì
thường có khả năng nén cao hơn nhưng khả năng phục hồi thì kém hơn. Trên cơ sở hai
khuynh hướng, có 4 cách tiếp cận cơ bản trong nén ảnh:
Nén ảnh thống kê: Kỹ thuật nén này dựa vào việc thống kê tần xuất xuất hiện của
giá trị các điểm ảnh, trên cơ sở đó mà có chiến lược mã hóa thích hợp. Một ví dụ
điển hình cho kỹ thuật mã hóa này là *.TIF
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
8
Nén ảnh không gian: Kỹ thuật này dựa vào vị trí không gian của các điểm ảnh để
tiến hành mã hóa. Kỹ thuật lợi dụng sự giống nhau của các điểm ảnh trong các
vùng gần nhau. Ví dụ cho kỹ thuật này là mã nén *.PCX
Nén ảnh sử dụng phép biến đổi: Đây là kỹ thuật tiếp cận theo hướng nén không
bảo toàn và do vậy, kỹ thuật thướng nến hiệu quả hơn. *.JPG chính là tiếp cận
theo kỹ thuật nén này.
Nén ảnh Fractal: Sử dụng tính chất Fractal của các đối tượng ảnh, thể hiện sự lặp
lại của các chi tiết. Kỹ thuật nén sẽ tính toán để chỉ cần lưu trữ phần gốc ảnh và
quy luật sinh ra ảnh theo nguyên lý Fractal.
1.2. Bài toán nén ảnh
1.2.1. Giới thiệu
Ảnh trên máy tính là kết quả thu nhận theo các phương pháp số hoá được nhúng
trong các thiết bị kỹ thuật khác nhau. Quá trình lưu trữ ảnh nhằm 2 mục đích:
Tiết kiệm bộ nhớ
Giảm thời gian xử lý
Việc lưu trữ thông tin trong bộ nhớ có ảnh hưởng rất lớn đến việc hiển thị, in ấn và
xử lý ảnh được xem như là 1 tập hợp các điểm với cùng kích thước nếu sử dụng càng
nhiều điểm ảnh thì bức ảnh càng đẹp, càng mịn và càng thể hiện rõ hơn chi tiết của ảnh
người ta gọi đặc điểm này là độ phân giải.
Việc lựa chọn độ phân giải thích hợp tuỳ thuộc vào nhu cầu sử dụng và đặc trưng
của mỗi ảnh cụ thể, trên cơ sở đó các ảnh thường được biểu diễn theo 2 mô hình cơ bản
1.2.1.1. Mô hình Raster
Đây là cách biểu diễn ảnh thông dụng nhất hiện nay, ảnh được biểu diễn dưới
dạng ma trận các điểm (điểm ảnh). Thường thu nhận qua các thiết bị như camera,
scanner. Tuỳ theo yêu cầu thực thế mà mỗi điểm ảnh được biểu diễn qua 1 hay nhiều bít
Mô hình Raster thuận lợi cho hiển thị và in ấn. Ngày nay công nghệ phần cứng
cung cấp những thiết bị thu nhận ảnh Raster phù hợp với tốc độ nhanh và chất lượng cao
cho cả đầu vào và đầu ra. Một thuận lợi cho việc hiển thị trong môi trường Windows là
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
9
Microsoft đưa ra khuôn dạng ảnh DIB (Device Independent Bitmap) làm trung gian.
Hình 1.4 thể hiện quy trình chung để hiển thị ảnh Raster thông qua DIB
Một trong những hướng nghiên cứu cơ bản trên mô hình biểu diễn này là kỹ thuật
nén ảnh các kỹ thuật nén ảnh lại chia ra theo 2 khuynh hướng là nén bảo toàn và không
bảo toàn thông tin nén bảo toàn có khả năng phục hồi hoàn toàn dữ liệu ban đầu còn nén
không bảo toàn chỉ có khả năng phục hồi độ sai số cho phép nào đó. Theo cách tiếp cận
này người ta đã đề ra nhiều quy cách khác nhau như BMP, TIF, GIF, PCX…
Hiện nay trên thế giới có trên 50 khuôn dạng ảnh thông dụng bao gồm cả trong
đó các kỹ thuật nén có khả năng phục hồi dữ liệu 100% và nén có khả năng phục hồi với
độ sai số nhận được.
Hình 1.4. Quá trình hiển thị và chỉnh sửa, lƣu trữ ảnh thông qua DIB
1.2.1.2. Mô hình Vector
Biểu diễn ảnh ngoài mục đích tiết kiệm không gian lưu trữ dễ dàng cho hiển thị
và in ấn còn đảm bảo dễ dàng trong lựa chọn sao chép di chuyển tìm kiếm… Theo
những yêu cầu này kỹ thuật biểu diễn vector tỏ ra ưu việt hơn.
Trong mô hình vector người ta sử dụng hướng giữa các vector của điểm ảnh lân
cận để mã hoá và tái tạo hình ảnh ban đầu ảnh vector được thu nhận trực tiếp từ các thiết
bị số hoá như Digital hoặc được chuyển đổi từ ảnh Raster thông qua các chương trình số
hoá
Công nghệ phần cứng cung cấp những thiết bị xử lý với tốc độ nhanh và chất
lượng cho cả đầu vào và ra nhưng lại chỉ hỗ trợ cho ảnh Raster. Do vậy, những nghiên
cứu về biểu diễn vectơ đều tập trung từ chuyển đổi từ ảnh Raster.
Hình 1.5. Sự chuyển đổi giữa các mô hình biểu diễn ảnh
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
10
1.2.2. Các cách tiếp cận bài toán nén ảnh
1.2.2.1. Bài toán nén ảnh
Cho đầu vào một bức ảnh chụp em bé có dạng ảnh *.jpeg có size: 160KB. Ta cần
nén bức ảnh này thành một bức ảnh mới có kích thước không đổi và có size nhỏ hơn rất
nhiều so với file ảnh ban đầu, bức ảnh có độ nét có thể chấp nhận được. Sau đó ta có thể
gửi bức ảnh cho bạn bè, người thân của em bé qua mạng cũng như qua các thiết bị lưu
trữ dữ liệu. Từ bài toán trên ta có 2 cách tiếp cận bài toán như sau:
1.2.2.2. Tiếp cận nén bảo toàn
Bức ảnh sau khi nén cho kích thước ảnh giống như kích thước ban đầu ảnh mới
có dạng ảnh *.jpeg có size: 138KB. Trong khi ảnh cũ có size: 160KB. Sau khi giải nén
cho ảnh mới có size như size ảnh ban đầu. Cách tiếp cận bảo toàn cho ta bức ảnh mới có
độ nén thấp chỉ vài chục phần trăm. Nhưng ảnh sau khi giải nén không bị mất mát dữ
liệu, điều này rất cần cho nén ảnh chụp X – quang hay các loại ảnh chụp trong ngành y
tế, cũng như các ảnh chụp trong ngành thiên văn học các ngành này đòi hỏi độ chính xác
cao.
1.2.2.3. Tiếp cận nén không bảo toàn
Bức ảnh sau khi nén cho kích thước ảnh giống như kích thước ban đầu ảnh mới
có dạng ảnh *.jpeg có size: 36,1KB. Trong khi ảnh cũ có size: 160KB. Sau khi giải nén
cho ảnh mới có size mới là 155KB nhỏ hơn size ban đầu là 5KB. Sai số này có thể chấp
nhận được cho các ảnh chụp phong cảnh cũng như các ảnh nghệ thuật. Phương pháp này
không đòi hỏi độ chính xác cao. Ảnh mới cho chất lượng ảnh có độ nét cao có thể chấp
nhận được và phương pháp này được sử dụng rộng dãi trong các lĩnh vục nén ảnh số
cũng như nén các loại video số,…
1.3. Kết luận chƣơng
Chương này đã trình bày khái quát về xử lý ảnh. Các cách biểu diễn ảnh cũng
như các cách nén ảnh từ đó đặt ra bài toán nén ảnh và đưa ra cách thức giải quyết bài
toán nén ảnh. Từ đó em chọn cách nén ảnh không bảo toàn để giải quyết bài toán ứng
dụng nén ảnh rồi truyền qua mạng đều này được thể hiện ở chương 3.
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
11
CHƢƠNG 2
MỘT SỐ KĨ THUẬT NÉN ẢNH
2.1. Nén bảo toàn
Dữ liệu, đặc biệt là văn bản, đồ họa luôn chứa trong nó những chuỗi thông tin giống
hệt nhau lặp đi lặp lại. Việc nén dữ liệu được thực hiện bằng cách thay thế nhiều ký tự
thông tin lặp đi lặp lại bằng các ký tự khác, và tạo ra chỉ một bản sao của những đoạn dữ
liệu bị lặp lại này. Cũng có cách khác tỉ mỉ hơn dùng những mã có độ dài khác nhau mã
hóa cho các ký tự khác nhau giúp cho các ký tự này chiếm ít chỗ hơn. Cách gì thì cách
nhưng phải làm sao vừa thu nhỏ được kích thước file vừa giữ được sự toàn vẹn của dữ
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
12
liệu.
(Run-Length Encoding)
Mã hoá theo độ dài loạt RLE (Run-Length Encoding) là một thuật toán nén dựa trên
sự cắt bớt các dư thừa về không gian (loại dư thừa đơn giản nhất trong một tập tin là các
đường chạy dài gồm các kí tự lặp lại, một vài hình ảnh có vùng màu lớn không đổi đặc
biệt đối với ảnh nhị phân), các vùng dữ liệu hằng của các tập tin chương trình, một số
tập tin văn bản,... Loạt được định nghĩa là dãy các phần tử điểm ảnh (pixel) liên tiếp có
cùng chung một giá trị.
2.1.1.1. Ý tưởng của thuật toán
Ý tưởng của thuật toán này là phát hiện một loạt các điểm ảnh lặp lại liên tiếp, ví dụ:
11000011. Ta thấy điểm ảnh có giá trị 0 xuất hiện nhiều lần liên tiếp thay vì phải lưu trữ
toàn bộ các điểm ảnh có giá trị 0 ta chỉ cần lưu trữ chúng bằng cách sử dụng các cặp (độ
dài loạt, giá trị).
Ví dụ 1:
Cho một chuỗi nguồn t:
t = 22222222222131313131300000002727272727272727
Ta sẽ có chuỗi mới:
(11 2) (5 13) (7 0) (8 27)
Tỷ lệ nén = 21/8 = 2.625
Đối với ảnh đen trắng chỉ sử dụng 1 bit để biểu diễn 1 điểm ảnh thì phương pháp
này tỏ ra rất hiệu quả, ta thấy điều đó qua ví dụ sau:
Cho một chuỗi nguồn f:
F = 0000000000011111111111110000001111111111111111111110000000
Ta có chuỗi mới:
(11, 13, 6, 21, 7)
Tỷ lệ nén = 58 bit/(5*4 bit) = 2,9 (chỉ sử dụng 4 bit để thể hiện độ dài loạt và
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
13
không thể hiện giá trị loạt vì ảnh đen trắng chỉ có 2 giá trị bit là 0 hoặc là 1)
Chú ý: đối với ảnh chiều dài của một dãy lặp có thể lớn hơn 255, nếu ta dùng 1
byte để lưu trữ chiều dài thì sẽ không đủ. Giải pháp được dùng là tách chuỗi đó thành 2
chuỗi: một chuỗi có chiều dài là 255, chuỗi kia có chiều dài còn lại.
Ví dụ 2:
Ta có một chuỗi nguồn: d = 5 7 9 11 13 18 28 38 48
Chuỗi kết quả sau khi mã hoá:
1 5 1 7 1 9 1 11 1 13 1 18 1 28 1 38 1 48
Tỷ lệ nén = 9/18 = 0,2
Như vậy chuỗi sau khi mã hoá đã lớn hơn nhiều chuỗi nguồn ban đầu.
Do đó cần phương pháp cải tiến để xử lý những trường hợp như trên tránh làm
mở rộng chuỗi dữ liệu nguồn nghĩa là chỉ mã hoá độ dài loạt dữ liệu lặp lại. Người ta đã
đưa ra cách đó là thêm kí tự tiền tố vào trước độ dài loạt, việc giải mã được thực hiện
nếu gặp kí tự tiền tố với độ dài loạt và giá trị điểm ảnh theo sau.
Ví dụ 3:
Ta có chuỗi nguồn:
d = 5 8 4 8 8 8 8 8 8 8 8 10 10 10 10 10 10 10 10 10
Giả sử kí tự tiền tố là “+” ta có: 5 8 4 + 7 8 + 9 10
Tỷ lệ nén = 19/9 = 2,1
Tuy nhiên trong một số trường hợp các điểm ảnh có độ tương quan với nhau về
giá trị mức xám như trong ví dụ dưới đây ta có thể tiến hành xử lý như sau.
Ví dụ 4:
Ta có một chuỗi nguồn:
d = 5 7 9 11 13 18 28 38 48 58 55 60 65 70 75 80 85 90 95 100
Ta có dựa vào độ tương quan này để có được hiệu quả nén cao, bằng việc áp
Số hóa bởi Trung tâm Học liệu
http://www.lrc-tnu.edu.vn/
- Xem thêm -