Kỹ thuật nén ảnh Fractal

Mục lục
Phụ lục………………………………………………………………………..24
............................................................................................................................1
Lời giới thiệu.....................................................................................................2
1. Lý thuyết hình học Fractal.......................................................................3
2. Phương pháp nén ảnh Fractal.................................................................4
2.1.Iterated Function System (IFS).......................................................4
2.2.Tính chất không phụ thuộc vào độ phân giải của quá trình xây dựng
ảnh..................................................................................................................6
2.3.Nguyên lý quá trình nén ảnh....................................................................7
2.4.Nén ảnh với Partitioned Iterated Function Systems................................8
2.5.Ánh xạ và cách tìm ánh xạ.....................................................................10
2.6.Hướng mở rộng nén ảnh màu................................................................13

3.Kỹ thuật nén ảnh Fractal với thuật toán di truyền...............................14
3.1. Sơ lược về thuật toán di truyền.............................................................14
3.2. Sử dụng thuật toán di truyền trong kỹ thuật nén ảnh fractal................15
3.2.1. Áp dụng thuật toán di truyền.........................................................15
3.2.2. Vấn đề tổ chức dữ liệu khi kết hợp với kỹ thuật QuadTree..........15
3.3. Toán tử lai ghép....................................................................................18
3.4. Toán tử đột biến....................................................................................19
3.5. Cụ thể hoá giải thuật thành chương trình.............................................19

Tổng kết...........................................................................................................23
Phụ Lục............................................................................................................24
* Show Histogram.......................................................................................31
Phụ lục………………………………………………………………………..24

1

Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Lời giới thiệu
Dữ liệu hình ảnh là một dạng dữ liệu quan trọng, được lưu trữ, chuyển tải và sử
dụng rất nhiều trong ngành công nghệ thông tin hiện đại. Cách mô tả hình ảnh để xử
lý bằng máy tính hiện nay là mô tả bằng ma trận điểm: ảnh (hình chữ nhật) được chia
thành nhiều ô bằng một lưới, mỗi ô được đại diện bằng một điểm gọi là điểm ảnh
(pixel: picture element) và các điểm ảnh này được bố trí thành một lưới hình chữ
nhật có thứ tự giống như các ô tương ứng tạo thành hình ảnh. Tập hợp các điểm ảnh
đó có thể mô tả được hình ảnh ban đầu là do độ phân giải của mắt người là hữu hạn.
Thế nhưng cách lưu trữ này rất tốn kém: một bức ảnh thông thường có thể chứa hàng
triệu điểm ảnh (ví dụ như một bức ảnh ở độ phân giải 1600x1200 - rất thường gặp ở
các máy ảnh số cao cấp - có 1.920.000 điểm ảnh) nên chúng có thể có kích thước đôi
khi đến hàng chục Megabytes. Do đó cần phải sử dụng các phương pháp nén ảnh để
giảm không gian lưu trữ và giảm thời gian, chi phí khi chuyển tải.
Các kỹ thuật nén ảnh nói riêng và rất nhiều kỹ thuật nén dữ liệu nói chung đều
dựa trên cùng một tư tưởng, đó là giảm kích thước bằng cách chỉ lưu trữ một lần các
đối tượng dữ liệu “giống nhau”. Hai khối dữ liệu khác nhau đối với máy tính có thể
là giống nhau đối với con người. Vì vậy ta có các lớp kỹ thuật nén mất dữ liệu
(Lossy Compression). Lớp giải thuật này được gọi là mất dữ liệu là do nó chấp nhận
mất một số thông tin ít có giá trị với con người trong quá trình nén để tăng tỉ số nén.
Ví dụ tiêu biểu là JPEG (Joint Photographic Experts Group), nó có khả năng nén ảnh
nhanh chóng và hiệu quả: trong các trường hợp thường gặp thì tỉ số nén tối đa mà kỹ
thuật JPEG đạt được mà chất lượng ảnh còn chấp nhận được là khoảng 25:1. Đó là
một tỉ số nén rất cao, do vậy kỹ thuật nén JPEG được chấp nhận rộng rãi và được coi
như là một tiêu chuẩn đối với các phương pháp nén ảnh.
Một phương pháp khác thuộc lớp các giải thuật nén mất dữ liệu đang được phát

triển là phương pháp nén ảnh fractal. Cơ sở của phương pháp này là hình học fractal,
một bộ môn của toán học mới được phát triển khoản hơn 30 năm gần đây nhờ có sự
giúp sức của các máy tính mạnh.

2
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

1. Lý thuyết hình học Fractal
Fractal là thuật ngữ do Benoît Mandelbrot, một nhà nghiên cứu của công ty
IBM người Mỹ gốc Ba Lan (thời trẻ, Mandelbrot sống và học ở Pháp), đưa ra để chỉ
các đối tượng có sự giống nhau giữa các phần của chính nó ở các tỉ lệ khác nhau.
Tính chất này được gọi là tính tự-tương tự (self-similarity). Môn hình học nghiên
cứu các vật thể fractal dựa trên cơ sở khai triển các công thức đệ quy, mà các công
thức đệ quy phi tuyến (thực tế là một cách thể hiện khác của phương trình vi phân
phi tuyến) là không thể giải được bằng các phương pháp toán học tất định
(deterministic). Việc giải các phương trình này chỉ có thể tiến hành bằng máy tính,
bằng cách tính từng điểm một, do vậy việc nghiên cứu các vật thể fractal chỉ phát
triển khi xuất hiện các máy tính có khả năng tính toán đủ mạnh (trước đó, có nhà
khoa học đã phải tính bằng tay và vẽ trên giấy các điểm của một quá trình hỗn loạn!).
Hình học fractal có khả năng mô phỏng tự nhiên mạnh mẽ và các đối tượng nghiên
cứu của nó trải rộng trong rất nhiều ngành khác nhau do cơ sở của nó là phương trình
vi phân phi tuyến mà mọi quá trình thực trong tự nhiên đều chịu sự chi phối của các
quy luật phi tuyến.
Các vật thể fractal (đơn giản và nhân tạo) có một tính chất đặc biệt, là mặc dù
chúng có hình dạng cực kỳ phức tạp mà điển hình là tập Mandelbrot, hay lá cây
dương xỉ, nhưng lại có thể được tạo ra bằng cách áp dụng nhiều lần một công thức
đơn giản. Người đặt nền móng cho kỹ thuật nén ảnh fractal là Michael Barnsley,

cũng là một nhà nghiên cứu về các đối tượng fractal, đã đề ra ý tưởng rằng nếu từ
công thức ta có thể tạo ra hình ảnh thì ta có thể làm ngược lại, tìm công thức từ một
hình ảnh cho trước và lưu trữ công thức này thay vì lưu trữ ma trận điểm của ảnh,
sau đó ta có thể áp dụng công thức tìm được để tái tạo lại hình ảnh.
Tất nhiên các vật thể trong tự nhiên là không thể mô tả được bằng các công
thức đơn giản, do vậy cần phải tìm được một dạng hàm có khả năng mô tả được hình
ảnh. Barsnley đưa ra được một dạng hàm trong không gian hai chiều có khả năng
này, và việc lưu trữ ảnh trở thành lưu trữ một tập hợp các hàm biến hình trong không
gian hai chiều, gọi là Iterated Function System: hệ thống các hàm lặp, IFS. IFS là
khái niệm trung tâm của kỹ thuật nén ảnh fractal.
3
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

2. Phương pháp nén ảnh Fractal
2.1.Iterated Function System (IFS)
Một ánh xạ f(x) là ánh xạ co nếu như khoảng cách của hai ảnh được tạo bởi ánh
xạ đó nhỏ hơn khoảng cách giữa hai nguyên ảnh: |f(x), f(y)| < |x, y|. Ví dụ ánh xạ f(x)
= x/2 là co đối với trường số thực. Các ánh xạ co có tính chất quan trọng là nếu ta áp
dụng lặp đi lặp lại một ánh xạ co đối với một điểm x0 bất kỳ như sau:
x1 = f(x0)
x2 = f(x1) = f(f(x0))
…..
xn = f(xn-1)
thì lim(xn) khi n tiến ra vô cùng sẽ là một điểm cố định (còn gọi là điểm hút, attractor
của ánh xạ) không phụ thuộc vào x0 mà chỉ phụ thuộc vào ánh xạ, trong trường hợp
ví dụ trên thì đó là 0. Các phương pháp lặp để giải phương trình và hệ phương trình
như phương pháp Newton, đã lợi dụng tính chất này của ánh xạ co (và hệ quả là kết

quả của các phương pháp lặp cũng có tính chất fractal). Định nghĩa vừa nêu chỉ nói
đến các ánh xạ trong không gian một chiều nhưng tính chất co có thể có ở tất cả các
loại ánh xạ trong không gian nhiều chiều hơn và khái niệm khoảng cách có thể là
một hàm bất kỳ nào đó. Tính chất co là tính chất quyết định của IFS.
Một IFS là một tập hợp (hữu hạn) các ánh xạ co w1..wn trên mặt phẳng R2. IFS
tác động lên một khu vực hữu hạn của mặt phẳng và mỗi ánh xạ wi thu nhỏ một khu
vực của mặt phẳng rồi chép lên một vùng khác của mặt phẳng. Như vậy thông qua
IFS, một hình ảnh được biến đổi thành một hình ảnh khác. Nếu sau khi áp dụng lần
lượt các ánh xạ của IFS lên một hình ảnh I 0 bất kỳ ta lại áp dụng tiếp IFS lên chính
hình ảnh kết quả I1 của nó và lặp đi lặp lại quá trình này, ta sẽ có dãy các hình ảnh I 2,
I3, I4 … mà các ảnh kết quả càng ngày càng giống nhau hơn sau mỗi lần lặp do tính
chất co của các ánh xạ trong IFS. Và do các ánh xạ thu nhỏ ảnh lại rồi chép ảnh thu
nhỏ lên một vùng của ảnh nên sau mỗi lần áp dụng IFS, các chi tiết nhỏ hơn lại xuất
hiện vì mỗi lần lặp, IFS tạo ra các chi tiết bị thu ngày một nhỏ, các chi tiết này tạo
nên hình ảnh và do đó sẽ còn tiếp tục bị thu nhỏ trong các lần lặp tiếp theo. (Hiện
tượng này cũng tương tự như việc các vòng hồi tiếp trong các thiết bị điện tử biến
đổi đầu vào của chúng theo tín hiệu ra để ổn định thông số mạch, và là nguyên nhân
của tính chất “resolution independence” của ảnh giải nén theo kỹ thuật fractal sẽ
4
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

được nói tới trong mục tiếp theo). Các hình ảnh I n ngày càng tiến gần đến (nhưng về
mặt toán học thì không bao giờ trùng) một hình ảnh cố định, gọi là điểm hút
(attractor) của IFS. Điểm hút này chỉ phụ thuộc vào IFS mà không phụ thuộc vào
hình ảnh ban đầu. Trong thực tế, ta có thể đạt tới hình ảnh không thay đổi chỉ sau vài
(khoảng 8 - 10) vòng lặp do kích thước của chi tiết được sinh thêm bị giới hạn bởi
khả năng phân giải của thiết bị raster (đơn vị pixel). Hình ảnh do IFS tạo ra là fractal

do tính chất lặp của phương pháp sinh ảnh này và nó có chứa các bản sao thu nhỏ
của chính nó với nhiều tỷ lệ khác nhau. Đó là lý do tại sao phương pháp này được
gọi là Fractal Image Compression: phương pháp nén ảnh fractal.
Ví dụ về IFS
Hãy hình dùng một cái máy PhôtôCopy đặc biệt có chức năng giảm kích thước
một ảnh xuống một nửa rồi lại tự sinh ra nó 3 lần. Xem hình vẽ. Điều
gì sẽ xảy ra nếu kết quả này lại được chuyển vào máy Phôtô này lần
nữa. Chúng to có thể thấy được rằng tất cả các bản copy này dường
như có vẻ hội tụ tới một ảnh cuối cùng ( Như ảnh 2c). Bởi vì máy này
đã làm giảm ảnh đầu vào, bất kì một ảnh bất kì khác được đặt khởi
đầu ở máy copy này thì chúng sẽ được thu nhỏ lại tới một điểm khi
chúng ta thực hiện lặp lại quá trình Phô tô này.

Hình vẽ : Một chiếc máy phô tô copy đặc biệt

5
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Hình vẽ : Hình ảnh các image được sinh ra sau một số lần lặp
Như vậy ta có thể thấy rằng cách thức ảnh đầu vào được biến đổi sẽ xác định ảnh
cuối cùng sẽ như thế nào

2.2.Tính chất không phụ thuộc vào độ phân giải của quá trình xây dựng
ảnh
Quá trình xây dựng ảnh bằng IFS có một tính chất đặc biệt: quá trình này có thể
xây dựng nên ảnh ở kích thước bất kỳ mà không tạo thành các khối pixel có trị giống
nhau, tức là nó có thể phóng lớn một hình ảnh lên mà hình ảnh vẫn có các chi tiết

nhỏ. Tính chất đặc biệt này được gọi là “resolution independence”, tính độc lập về độ
phân giải. Sở dĩ ảnh tạo bởi IFS có tính chất này là do ảnh là fractal, có các chi tiết ở
mọi kích thước. Đây là tính chất đặc trưng chỉ có ở kỹ thuật nén fractal.

6
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

2.3.Nguyên lý quá trình nén ảnh
Quá trình được nêu ở trên là quá trình giải nén ảnh. Đó là một quá trình đơn
giản và nhanh chóng. Nhưng vấn đề là phải tìm một ảnh tốt nhất tương ứng với một
ma trận cho sẵn và phải càng sử dụng ít phép biến đổi càng tốt. Bài toán này được
gọi là bài toán ngược. Đó chính là làm sao tìm được một IFS có thể mô tả được một
hình ảnh cho trước (có nghĩa là có thể sử dụng IFS đó để xây dựng lại hình ảnh đã
cho với sai số có thể chấp nhận được). Bài toán này được gọi là “inverse problem”
(bài toán đảo) và nó phức tạp hơn nhiều bậc so với việc xây dựng hình ảnh từ một
IFS cho trước. Các thuật toán đề ra để giải quyết bài toán này đều có độ phức tạp
tính toán rất lớn và việc giảm bớt độ phức tạp của nó vẫn là một vấn đề đang được
nghiên cứu..
Việc tìm được một IFS phù hợp với một hình ảnh cho trước là không thể thực
hiện được bằng cách chọn và thử từng ánh xạ, tính toán rồi tìm ánh xạ khác cho tới
khi tìm được một IFS vừa ý mà cần phải thực hiện một cách chặt chẽ. Thuật toán đầu
tiên do Michael Barnsley đưa ra để thực hiện việc này lợi dụng tính tự-tương tự của
đối tượng fractal:
-

Tìm trên bức ảnh một vùng tương tự với toàn bộ bức ảnh (tức là có thể biến
đổi thành nhau thông qua một phép biến hình nào đó).


-

Tìm ánh xạ tương ứng.

-

Sau khi tìm được toàn bộ các ánh xạ, ta đã có IFS cần tìm.

Giải thuật này giống một ý tưởng hơn là một thuật toán thông thường và thực tế
là không khả thi do hai lý do chính: việc đi tìm một vùng trong ảnh tương tự với toàn
bộ bức ảnh là không thể thực thực hiện được ngay cả khi có một máy tính thật mạnh
và ngay cả khi có thể thực hiện được việc đó đi chăng nữa thì trong các bức ảnh
thường gặp, cũng không có nhiều vùng tương tự với toàn bộ bức ảnh. (Thực tế giải
thuật này này vẫn có thể là khả thi nếu ta có một “universal mapping”, một ánh xạ có
thể biến hoá từ một hình ảnh bất kỳ thành một hình ảnh khác, nhưng một ánh xạ như
vậy có lẽ không tồn tại và nếu tồn tại thì việc lưu trữ nó có lẽ còn tốn chỗ ít nhất là
bằng lưu trữ toàn bộ bức ảnh, bởi chính nó chứa toàn bộ thông tin của bức ảnh).

7
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Một khía cạnh quan trọng trong giải thuật này mang tính quyết định đối với kỹ
thuật nén ảnh fractal, đó là định nghĩa lại khái niệm tương tự. Khái niệm hai hình ảnh
tương tự ở đây được hiểu là hai hình ảnh này có thể được biến đổi thành nhau nhờ
một phép biến hình (ánh xạ) nào đó. Việc chọn loại phép biến hình là rất quan trọng
đối với quá trình nén ảnh do ánh xạ đó sẽ được áp dụng nhiều lần nên độ phức tạp

của nó sẽ quyết định tốc độ nén. Hiện nay người ta đang sử dụng phép biến hình
affine mặc dù theo lý thuyết ta có thể sử dụng mọi loại ánh xạ nói chung, chỉ cần tập
hợp của chúng là co. Ánh xạ affine là ánh xạ tuyến tính, trong không gian hai chiều
có dạng:
F(X) = A*X + B
trong đó F(X) là ảnh của hình X, A là một ma trận vuông cấp 2, quyết định cách thức
biến hình như quay, co dãn, đối xứng, thay đổi độ đậm nhạt…, còn B là một vector
biểu thị độ dịch của ảnh so với nguyên ảnh. Loại ánh xạ này được chọn do tính đơn
giản, dễ tính toán của nó, mặt khác mối liên hệ “kiểu affine” cũng khá phổ biến trong
tự nhiên.
Cải tiến lớn làm cho phương pháp nén ảnh fractal trở thành có thể thực hiện
được do Arnaud Jacquin đưa ra năm 1989, đó là thay vì đi tìm tính tương tự giữa một
phần và toàn bộ bức ảnh, ta có thể đi tìm tính tương tự giữa hai vùng của bức ảnh với
nhau. Tập các hàm như thế gọi là Partitioned Iterated Function Systems (PIFS)

2.4.Nén ảnh với Partitioned Iterated Function Systems
Nội dung chính của kỹ thuật này là chia ảnh ra thành nhiều mảnh thuộc hai
loại: domain và range, trong đó các range không phủ lên nhau và lát kín bức ảnh còn
các domain lớn hơn các range (để bảo đảm tính co cho các ánh xạ) và các domain có
thể phủ lên nhau, sau đó với mỗi range ta đi tìm một domain phù hợp nhất với nó
(sau này Barnsley đã đổi chỗ hai khái niệm, tức là ánh xạ trở thành biến range thành
domain, nhưng dường như không mấy người theo cách gọi này). Đó là một công việc
nặng nhọc do có quá nhiều cặp range và domain cần so sánh nên thuật toán này rất
chậm. Có hai phương hướng cải tiến tăng tốc độ cho việc nén ảnh, đó là:
(i)

giảm số domain của bức ảnh

8
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN



Kỹ thuật nén ảnh Fractal

(ii) thu nhỏ không gian tìm kiếm tức là đối với mỗi range ta cần thực hiện ít
phép so sánh hơn.
Việc giảm số domain có thể thực hiện như sau:
-

Các domain và range là hình vuông với độ dài cạnh là 2n(1 < n < 6).

-

Buộc các domain phải bắt đầu tại các vị trí theo một ràng buộc nào đó, ví dụ
như tại các vị trí có toạ độ chẵn.

-

Cố định tỉ lệ kích thước giữa các domain và range, thường là 2.

-

Đơn giảm hoá các ánh xạ: trong khi ánh xạ affine có thể cho ra bản sao bị
quay đi một góc bất kỳ và có thể đối xứng với ảnh gốc, ở đây ta cố định góc
quay của ánh xạ là một bội số của 90 o hoặc không sử dụng các ánh xạ quay
và đối xứng, việc không sử dụng các ánh xạ loại này có thể làm giảm bớt
1/8 số domain cần so sánh.

Mô hình mã hoá được mô tả dưới đây


Hình vẽ mô tả quá trình mã hoá ảnh, với mỗi một block vùng được so sánh với các
Block miền hợp nhất

Hình vẽ mô hình của một hệ nén ảnh bằng fractal, trước tiên các khối block miền và
vùng được xác định rồi được đem so sánh để xác định các phép biến đổi

Hình vẽ mô tả quá trình giải nén
Transfomation pool : Xác định các phép biến đổi thích hợp cho đối tượng ảnh tương
ứng.
Domain pool : Chia nhỏ ảnh ra làm các khối miền với kích thước DxD
9
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Range pool : Chia nhỏ ảnh ra làm các khối vùng với kích thước BxB với BSearch : Quá trình tìm kiếm những phép biến đổi thích hợp để làm cho ma trận sai số
đạt nhỏ nhất có thể
Để cải thiện chất lượng ảnh, cầu trúc quadtree được sử dụng khi mã hoá một bức
ảnh. Cấu trúc này dựa trên việc chia nhỏ liên tiếp các ảnh thành các block có kích
thước gấp 4 lần nhau.

Các biện pháp nêu trên có vẻ quá mạnh và sẽ làm ảnh hưởng đến hiệu quả của
quá trình nén và làm giảm chất lượng nén nhưng thực tế chất lượng nén không giảm
nhiều, tuy vậy, độ phức tạp của bài toán vẫn còn quá lớn. Phương hướng cải tiến thứ
hai là giảm số lượng domain cần duyệt đối với mỗi range. Ý tưởng này được hiện
thực hoá thành phương pháp phân lớp domain (domain classification). Phương pháp
này dựa vào phân bố màu của các domain và range để phân lớp chúng, sau đó chỉ
tiến hành tìm kiếm đối với các range và domain cùng một lớp. Có nhiều cách phân

loại khác nhau, trong đó cách đơn giản và hiệu quả là chia thành 24 lớp dựa vào
tương quan giữa trị màu trung bình của bốn mảnh phần tư của hình vuông cần xét
(nếu ta sử dụng các ánh xạ quay và đối xứng thì chỉ còn chia ra được 24/8 = 3 lớp).

2.5.Ánh xạ và cách tìm ánh xạ
Ánh xạ affine tổng quát đối với một điểm ảnh đơn sắc có dạng:
 x   a1
  
f  y  =  a3
z  0
  

a2
a4
0

0   x   d1 
    
0 ×  y  +  d2 
c   z   b 

trong đó x, y là toạ độ của điểm ảnh bị tác động, z là độ chói của điểm bị tác động, ai
là các hệ số biến hình, c (contrast factor) là hệ số biến đổi độ chói (độ tương phản),
di là khoảng dịch chuyển vị trí, b (brightness offset) là độ dịch sáng của ảnh so với
nguyên ảnh. Các hệ số này đều là số thực.
Trên thực tế ánh xạ của PIFS chịu những ràng buộc bổ sung, nên các hệ số của
chúng không độc lập với nhau. Các ràng buộc của ánh xạ như sau:

10
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN

Kỹ thuật nén ảnh Fractal

-

Do góc quay chỉ có thể là 0o, 90o, 180o, 270o, ứng với mỗi góc quay có 4
cách đối xứng nhưng một nửa trong số cách kết hợp quay - đối xứng là
trùng nhau nên có 4*4/2 = 8 hướng có thể có của ảnh.

-

Vị trí của ảnh và nguyên ảnh là cố định nên ta không cần tính các hệ số di.

-

Do tỷ lệ giữa độ dài cạnh của domain và range là cố định nên ta không cần
lưu trữ các hệ số co giãn.

Với các hạn chế đó, việc áp dụng ánh xạ trở thành việc áp dụng liên tiếp 4 phép biến
đổi đơn giản hơn như sau:
-

Đầu tiên ta thực hiện một phép thu nhỏ hình ảnh.

-

Tiếp theo ta quay và đối xứng hình ảnh vừa có được.

-

Sau đó ta nhân giá trị độ chói của từng điểm ảnh với hệ số tương phản c.

-

Cộng giá trị độ chói của từng điểm ảnh với hệ số dịch sáng b.

Như vậy để tìm ánh xạ, ta cần phải biết ba giá trị: giá trị mã hoá phép quay, độ
tương phản và độ dịch sáng. Để tìm ra c và b, ta có thể sử dụng phương pháp bình
phương nhỏ nhất. Ví dụ cho 2 ma trận R=[rij], D=[dij], ta có ảnh của D qua ánh xạ là
d’ij = dij * c + b, như vậy ta có n cặp (rij, d’ij) với n là số điểm ảnh của range, nếu chúng
là giống nhau qua ánh xạ đã cho thì chúng có liên hệ bậc nhất với nhau và theo lý
thuyết bình phương nhỏ nhất, c và b của ánh xạ cần tìm là nghiệm của hệ phương trình:
n
n

 nb + c ∑ d i =∑ ri
i =1
i =1
 n
n
n
b∑ d i +c ∑ d i2 =∑ ri d i
 i =1
i =1
i =1

Có nhiều cách đánh giá “độ tốt” (fitness) của một ánh xạ, nhưng dễ dàng nhất là
sử dụng giá trị tổng bình phương sai lệch trung bình giữa ảnh của domain và range:
E ( R, D ) =

1
n

n

∑ (cd
i =1

i

+ b − ri ) 2

Giá trị này được gọi là RMS, Root Mean Square, là một thước đo khá tốt về chất
lượng của phép biến hình, và nó càng nhỏ khi range và domain càng tương tự nhau.

11
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Thế nhưng nó lại không phải là một tiêu chuẩn tốt để đánh giá về mức độ giống nhau
của hai hình ảnh đối với con người.
Tuy nhiên, việc biến đổi này phải có một giới hạn nào đó. Các phép biến đổi
này cần phải thoả mãn một tính chất gọi là contractive (chúng tôi sẽ trình bày ở phần
dưới)
Ví dụ dưới đây sẽ cho chúng ta thấy giải thuật Fractal được thực hiện như thế nào.
Giả sử rằng chúng ta thực hiện trên một bức ảnh 128 x 128 với mỗi một pixel có thể
có 256 mức xám. Chúng ta gọi bức ảnh này là ảnh Vùng (Range). Sau đó chúng ta

giảm kích thước chúng xuống (lọc thông thấp) ảnh gốc xuống còn kích thước 64x64.
Chúng ta gọi ảnh này là ảnh miền (Domain). Chúng ta chia mỗi ảnh ra thành các
khối, mỗi khối có kích thước 4x4 pixel.

Chúng ta thực hiện phép biến đổi cải thiện đối với mỗi khối.
(Di,j) = αDi,j + to
Trong đó α=[0,1], α∈ R và to = [-255,255], t0 ∈ Z
Trong trường hợp này chúng ta sẽ tìm phép biến đổi tuyến tính từ các khối miền để
chúng có thể xấp xỉ với các khối vùng. Mỗi khối miền được biến đổi và đem so sánh
với mỗi khối vùng. Các hệ số của phép biến đổi này có thể được thực hiện như sau:

12
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Trong đó n,m Ns = 2 hoặc 4 ( kích cỡ của một block)
Mỗi một phép biến đổi trên các khối miền được so sánh với các khối vùng để tìm ra
khối miền gần nhất so với khối miền
Sau khi tìm được các hệ số các của các phép biến đổi này, chúng được lưu trữ vào
một file mô tả các phép biến đổi. File này được gọi là Fractal Code Book

2.6.Hướng mở rộng nén ảnh màu
Các khía cạnh của thuật toán được nêu ở trên chỉ sử dụng cho ảnh đơn sắc (ảnh
xám, gray scale). Ảnh màu được tổ chức khác với ảnh đơn sắc, cách lưu trữ ảnh màu
hiện nay là lưu trữ trong không gian màu RGB, mỗi màu được tổng hợp từ ba màu
cơ bản là đỏ, xanh lam và xanh sẫm (Red, Green, Blue). Bởi vậy để nén ảnh màu ta
có thể tổ chức ảnh thành ba ảnh xám rồi nén riêng ba ảnh này. Rất nhiều phương
pháp nén ảnh khác như JPEG đều giải quyết như vậy. Cách tiếp cận này kém hiệu

quả vì nó không lợi dụng được sự liên quan giữa các màu của ảnh.
Cách thứ hai để nén ảnh màu là mở rộng ánh xạ affine để có thể áp dụng cho
ảnh màu. Khi đó một điểm ảnh sẽ được mô tả bằng bộ giá trị (x, y, r, g, b) trong đó x
và y là hai toạ độ của điểm ảnh trong bức ảnh, còn r, g, b lần lượt là các thành phần
màu của điểm ảnh đó. Không gian ảnh sẽ là năm chiều và ánh xạ affine lúc này có
dạng:
 x   a1
  
 y   a3
fr= 0
  
g  0
b  0
  

a2
a4
0
0
0

0
0
cr
0
0

0
0
0

cg
0

0   x   d1 
    
0   y   d2 
0  ×  r  +  br 
    
0   g   bg 
cb   b   bb 

13
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

trong đó ai là các hệ số biểu thị các phép biến hình, di biểu thị phép dời hình, còn cr,
cg, cb là hệ số tương phản tương ứng với các màu, br, bg và bb là độ dịch sáng của ánh
xạ đối với mỗi màu. Cũng giống như ánh xạ affine cho ảnh đơn sắc, có rất nhiều hệ
số trong công thức trên bị ràng buộc bởi các điều kiện khác nhau nên ta không cần
phải lưu trữ và tính toán tất cả các hệ số. Trong chương trình nén, ánh xạ vẫn được
chuyển thành bốn phép biến hình như ánh xạ ba chiều cũ. Chương trình minh hoạ
phương pháp ở phần sau sẽ sử dụng biện pháp này.
Trong không gian ảnh 5 chiều, hàm RMS để đánh giá sai số do ánh xạ gây ra
phải sửa đổi thành:

Đây chính là khoảng cách trung bình giữa hai tập hợp điểm trong không gian Đề-các
ba chiều thông thường.

3.Kỹ thuật nén ảnh Fractal với thuật toán di truyền
3.1. Sơ lược về thuật toán di truyền.
Thuật toán di truyền (Genetic Algorithm, GA) là một thuật toán tìm kiếm theo
tư tưởng mô phỏng tự nhiên. GA rất hiệu quả để tối ưu một hàm trên một tập hợp, tư
tưởng chính của GA là: cho một tập P có n đối tượng, tập này gọi là quần thể
(population), mỗi thành phần của quần thể được gọi là gene, tại mỗi bước lặp ta xét
một số cặp gene (gi, gj)∈ P, các cặp này được chọn ngẫu nhiên theo xác suất, rồi trao
đổi các thành phần của chúng với nhau hoặc chọn ngẫu nhiên một gene để biến đổi
các thành phần của nó. Sau đó áp dụng một phép lượng giá để đánh giá các gene mới
nhận được thông qua phép biến đổi, và chọn lấy các gene phù hợp để làm quần thể
cho lần lặp sau. Trong GA mỗi lần lặp được gọi là thế hệ. Ở đây quần thể gene mô
phỏng quần thể sinh vật, chúng chịu tác động của hai toán tử: toán tử đột biến và
toán tử lai ghép. Còn hàm lượng giá đóng vai trò môi trường phát triển và tiêu chuẩn
chọn lọc như đối với các sinh vật sống. Việc tiến hoá của quần thể gene đi theo chiều
hướng tốt dần lên qua mỗi lần lặp, do các cách kết hợp kém hiệu quả bị loại bỏ.

14
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Do cách tiến hành như trên, GA có thể phát sinh được hầu hết các cách kết hợp
có thể có của quần thể, nên khả năng tìm được một kết quả có thể chấp nhận được là
rất cao. Tuy vậy, do GA là một phương pháp tìm kiếm không tất định nên nó cũng
giống như các phương pháp Heusristic, tức là nói chung chỉ có thể tìm được đáp án
chấp nhận được chứ không phải là đáp án tối ưu.

3.2. Sử dụng thuật toán di truyền trong kỹ thuật nén ảnh fractal
3.2.1. Áp dụng thuật toán di truyền

Thuật toán di truyền, do cách thực hiện của mình, là một thuật toán tìm kiếm
giải pháp chấp nhận được rất mạnh và hiệu quả. Việc áp dụng thuật toán di truyền để
tìm kiếm ánh xạ trong PIFS có thể được thực hiện rất tự nhiên, bằng cách thiết lập
một quần thể có các gene là ánh xạ cho các range và tại mỗi thế hệ ta cố gắng làm tốt
các ánh xạ với hai toán tử lai ghép và đột biến. Sau một số định trước các thế hệ ta
dừng tiến hoá và sử dụng các giải pháp tìm được như là ánh xạ tối ưu.
Để tăng tốc độ hội tụ của phương pháp ta có thể cải tiến hàm lượng giá bằng
cách khi tìm được một domain phù hợp với một range hơn domain trước đó, ta tiến
hành tìm kiếm trong các domain lân cận của domain đó bởi nhiều khả năng còn có
một domain tốt hơn ở gần domain đó.
Mặt khác tốc độ của GA phụ thuộc rất nhiều vào hàm lượng giá ánh xạ nên
hàm này cần được viết rất cẩn thận. Hàm lượng giá thường rất chậm, nhất là trong
trường hợp hàm tìm ánh xạ này, và sẽ tốt hơn nếu ta có thể tìm được một hàm đơn
giản hơn có tính chất chặn trên đối với hàm lượng giá, có nghĩa là hàm lượng giá
luôn luôn nhỏ hơn hàm gần đúng này và sử dụng hàm gần đúng này thay cho hàm
chính xác trên. Khi đó, sau khi tìm được ánh xạ ta cần phải lượng giá lại bằng hàm
lượng giá chính xác trước khi có thể sử dụng.
3.2.2. Vấn đề tổ chức dữ liệu khi kết hợp với kỹ thuật QuadTree
Kỹ thuật Quadtree được sử dụng trong nén ảnh fractal để tận dụng tính tự
tương tự của ảnh ở mức cao hơn. Thay vì chỉ sử dụng một cỡ range cố định, kỹ thuật
Quadtree sử dụng nhiều cỡ range khác nhau, quá trình nén được thực hiện như sau:
tìm ánh xạ cho các range cỡ lớn nhất, nếu range nào không tìm được domain phù
hợp thì nó sẽ được tách ra làm bốn range cỡ nhỏ hơn và tiếp tục tìm ánh xạ cho các
15
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

range này. Việc tách các range dừng khi kích thước của range đạt tới mức nhỏ nhất

được định trước. Khi đó, dù ánh xạ tốt nhất tìm được có sai số lớn hơn giá trị cho
trước, ta vẫn phải chấp nhận ánh xạ này. Việc sử dụng range có kích thước biến đổi
như vậy có thể cho ra file nén có kích thước nhỏ hơn file nén của các phương pháp
khác.
Do ảnh là 24 bit màu, việc phân lớp ảnh cho cả ba màu theo cách giống như đã
thực hiện trong phương pháp Classification là không thể thực hiện được nữa, và để
tận dụng tính tự tương tự theo vùng của ảnh, tức là các ánh xạ tốt thường có range và
domain gần nhau, ta cần tổ chức các khối thông tin của các domain sao cho nếu ta
biết được toạ độ bắt đầu của các domain thì ta có thể tìm được khối thông tin của
domain đó cũng như dễ dàng tìm được các khối thông tin của các domain lân cận
domain đang xét. Cách lưu trữ tiện lợi nhất để thực hiện việc này là lưu trữ theo
mảng hai chiều. Ở đây nếu mỗi domain cách nhau n pixel, n chẵn, thì ta có toạ độ
của khối thông tin mô tả domain (x, y) sẽ là (x/n, y/n), tất nhiên x, y đều chia hết cho
n.
Trong kỹ thuật quadtree, có thể ta không phải xét toàn bộ các range ở các cỡ
nhỏ hơn do chúng nằm trong một range lớn đã tìm được domain phù hợp, mặt khác
có thể các kích thước của ảnh không chia hết cho độ dài cạnh của range ở các cỡ lớn,
do vậy khi tìm ánh xạ cho các range kích thước lớn, ở biên phải và đáy của ảnh có
thể có các vùng ảnh nhỏ hơn độ dài cạnh của range, và do đó chúng không được xét
tới. Mặt khác để giảm kích thước file, vị trí của các range không được lưu trong file
nén mà được chương trình suy ra từ vị trí tương đối của ánh xạ trong file. Do vậy các
range cần được xếp thứ tự một cách chặt chẽ. Ta có thể xếp các range theo thứ tự
như sau: nếu một range bị tách, các range con của nó sẽ được lưu trữ ngay sau nó,
khi đó ta có thể xác định được toạ độ của range mà không cần thêm ký hiệu gì đặc
biệt. Nếu sử dụng một thuật toán tìm kiếm tất định nào đó, ta có thể định thứ tự các
range theo cách như trên dễ dàng bằng cách tiến hành tìm kiếm đệ quy đối với mỗi
range, nếu không tìm được ánh xạ thì việc tìm kiếm sẽ được tiến hành đệ quy đối với
mỗi range con của nó:
Thuật toán Alg1: Tìm kiếm QuadTree:
Tất cả các thuật toán đều chỉ là mô tả hình thức.

16
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal
Vào:

x, y: toạ độ của range
size: kích thước của range.
Ra:
Không.
procedure TestRange(x, y, size)
begin
if not FindMap(x, y, size, domain) then
begin
size := size / 2;
TestRange(x
, y
, size);
TestRange(x
, y + size, size);
TestRange(x + size, y
, size);
TestRange(x + size, y + size, size)
end
else
WriteMap(x,y, size, domain)
end;

Trong đó hàm FindMap tìm ánh xạ tốt nhất cho range,
còn WriteMap viết ánh xạ ra file.
Nhưng khi sử dụng thuật toán di truyền, do cần tìm kiếm ánh xạ cho tất cả các
range cùng một cỡ trong một lần, nên ta cần khử đệ quy thủ tục đệ quy trên để có thể
giữ nguyên format của file nén. Như vậy sau mỗi lần giảm kích thước range, ta cần
tính toán, xếp các range mới theo đúng thứ tự của nó, việc này yêu cầu phải chèn
thêm một mẫu tin vào giữa một khối mẫu tin khác. Cấu trúc dữ liệu tiện lợi nhất để
có thể dễ dàng chèn thêm một mẫu tin vào sau một mẫu tin có sẵn là danh sách liên
kết. Ta sẽ sử dụng một danh sách liên kết để lưu trữ các ánh xạ. Việc ứng dụng GA
đòi hỏi phải có thể truy nhập trực tiếp vào bất cứ thành phần nào của quần thể nên
sau khi đã chèn các ánh xạ mới vào danh sách liên kết, ta sẽ tạo một mảng các con
trỏ trỏ đến các ánh xạ cần tiến hoá.
Sau đây là giải thuật nén:
Thuật toán Alg2: nén ảnh bằng quadtree đã khử đệ quy
Vào:
Width, Height: Kích thước của ảnh.
Chú ý: Phần tử mảng được đánh số từ 0 theo chuẩn của
C.
Các định danh:
MapList Danh sách liên kết các ánh xạ.
Size
Kích thước của range đang xét.
Procedure CompressImage(Width, Height)
Begin
<Tạo mảng các khối thông tin domain>
Size := MaxSize;
While Size > MinSize do begin

17
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN

Kỹ thuật nén ảnh Fractal
If(Size = MaxSize)
theo thứ tự ưu tiên hàng>
else begin
for each Map in MapList do begin
if (Map cần phải tách) then
<chèn thêm bốn ánh xạ vào sau Map>
if (Map là ánh xạ cuối cùng trong hàng) and
(Width mod 2*Size > Size) then
Map>
end;
If(Height mod 2*Size > size)then
<Chèn thêm Width div Size ánh xạ vào cuối danh sách>
end;
<Lập mảng các con trỏ trỏ đến các ánh xạ cần tiến hoá>
<Tiến hành tiến hoá>
Size := Size/2;
end;
<Xuất các ánh xạ ra file>
End;

3.3. Toán tử lai ghép
Toán tử lai ghép có nhiệm vụ xét hai ánh xạ, trao đổi domain của chúng cho
nhau, nếu ánh xạ mới nào tốt hơn thì nó sẽ được giữ lại, còn nếu ánh xạ nào không
cải thiện được thì ánh xạ cũ sẽ không bị biến đổi. Để giảm bớt thời gian thực hiện
chương trình ta có thể bỏ qua việc lai ghép nếu cả hai ánh xạ đều đã đạt yêu cầu.

Việc này là khó thực hiện nếu như trong quá trình tiến hoá ta chỉ đánh giá sai số
bằng hàm gần đúng. Khi đó ta phải kết hợp sử dụng hàm chính xác để có thể xác
định được chất lượng thực sự của ánh xạ. Nếu hàm gần đúng nhanh thì ta cũng
không cần bước này.
Thuật toán của toán tử lai ghép như sau:
Thuật toán Alg3: Toán tử lai ghép
Vào
Map1, Map2: hai ánh xạ cần được lai ghép.
Ra
Hai ánh xạ có thể đã được sửa đổi.
Nếu ánh xạ được sửa đổi hàm trả về TRUE,
nếu không, hàm trả về FALSE
Hàm OK trả về TRUE nếu ánh xạ là chấp nhận được.
Hàm TestMap trả về TRUE nếu domain được kiểm tra hoặc một
domain lân cận nào đó của nó tốt hơn domain cũ.
Thủ tục ApplyMap ghi nhận domain mới tìm được.
Function CrossBreed(Map1, Map2)
Begin

18
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal
Done := False;
If not(OK(Map1) and OK(map2)) then begin
Done := TRUE;
If TestMap(Map1, Map2.Domain) then begin
ApplyMap(Map1, Map2.Domain);
Done := TRUE

End;
If TestMap(Map2, Map1.Domain) then begin
ApplyMap(Map2, Map1.Domain)
Done := TRUE
End;
End;
Return Done
End;

3.4. Toán tử đột biến
Công việc của toán tử đột biến đơn giản chỉ là lấy một domain ngẫu nhiên, thử
xem domain đó có hợp với range cũ không, nếu hợp thì thay domain cũ bằng domain
mới. Cũng như toán tử lai ghép, ta không đột biến các ánh xạ đã đạt yêu cầu. Toán tử
đột biến ít có cơ hội thành công trên các quần thể lớn do tính không định hướng của
nó và được áp dụng với xác suất nhỏ hơn nhiều so với toán tử lai ghép.
Thuật toán Alg4: Toán tử đột biến
Vào
Map: Toán tử cần đột biến
Ra
Như Alg3
Function Mutate(Map)
Begin
Done := False;
If not(OK(Map)) then begin
Domain := Random;
If TestMap(Map, Domain) then begin
ApplyMap(Map, Domain);
Done := TRUE
End;
End;

Return Done
End;

3.5. Cụ thể hoá giải thuật thành chương trình
Chương trình minh hoạ sử dụng ngôn ngữ C++, trình dịch Microsoft Visual C+
+ 6.0, có sử dụng thư viện Microsoft Foundation Class (MFC). Chương trình chỉ hỗ
trợ ảnh Windows Bitmap 24 bit màu (24bpp BMP). Module nén/giải nén ảnh
grayscale 8bpp không được đưa vào chương trình.
5. a. Tổ chức dữ liệu.
19
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Để thao tác các range và domain, chương trình sử dụng các lớp SQUARE,
AFFINEMAP và DOMAINDATA.

Sau đây là biểu đồ UML và định nghĩa các lớp:

typedef class SQUARE
{
protected:
static PPDWORD CumRange[3];
static PPFLOAT CumRange2[3];
static PPFLOAT CumDomain2[3];
public:
static void SetCumArray(PPDWORD
Domain2[]);
LONG x;

LONG y;
LONG sLog;
float sum[3];
float sum2[3];
} *PSQUARE;

Range[],

PPFLOAT

Domain[],

PPFLOAT

PPDWORD SQUARE::CumRange[3];
PPFLOAT SQUARE::CumRange2[3];
PPFLOAT SQUARE::CumDomain2[3];
typedef class DOMAINDATA:public SQUARE
{
public:
void SetPos(LONG ox, LONG oy, LONG slog);
} *PDOMAIN;
typedef class AFFINEMAP: public SQUARE
{
public:
PDOMAIN dom; // pointer pointed to domain approriate with the map
// Map infomation:
int contrast[3]; // contrast factors (quantized)
int brightness[3]; // brightness offset values (shifted and
quantized)

20
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal
double error2; // squared error value (may be approximated value)
#ifdef APPROXIMATIVE_EVALUATION
DWORD AppError2; // Approximative error2
#endif
AFFINEMAP* next; // the next map of PIFS
AFFINEMAP(LONG ox, LONG oy, LONG slog);
} *PAFFINEMAP;

Ở đây ta kết hợp mô tả range vào ánh xạ bởi vì mỗi range cần một ánh xạ, do
vậy không cần phải thêm một lớp mô tả range. Nhưng mỗi ánh xạ cũng chỉ có một
domain, nên ở đây domain được lưu trong ánh xạ sẽ luôn là domain tốt nhất đã tìm
được đối với ánh xạ. Mỗi khi hàm FindMap tìm thấy một domain tốt hơn, nó sẽ cập
nhật ngay con trỏ dom trong AFFINEMAP. Khi chưa có domain nào được ghi nhận
thì các giá trị lỗi phải có giá trị thật lớn, lớn hơn lỗi của bất cứ ánh xạ nào có thể, để
FindMap có thể là việc được.
Để biểu diễn một pixel 24bit ta có thể dùng cấu trúc RGBTRIPLE chuẩn của
Windows, nhưng ở đây ta sử dụng một cấu trúc PIXEL tự định nghĩa cho việc này do
ta cần truy nhập một pixel giống như một mảng ba byte trong chương trình. Thứ tự
sắp xếp BGR để cấu trúc này tương thích với cấu trúc RGBTRIPLE của Windows.
typedef union PIXEL {
struct {
BYTE B;
BYTE G;
BYTE R;

};
BYTE Elem[3];
} *PPIXEL;

Ngoài ra trong chương trình còn có vài cấu trúc nữa, đó là lớp COMPACTMAP
chứa ánh xạ do module giải nén đọc từ file nén và cấu trúc DOMAININFO chứa thông
tin chung cho các domain mỗi cỡ. Lớp COMPACTMAP được sử dụng trong quá trình
giải nén còn cấu trúc DOMAININFO sử dụng cho cả quá trình nén và giải nén.
typedef struct DOMAININFO
{
int PosBits; // number of bits used for store position value of a
domain
int xDomains; // number of domains in horizontal order
int yDomains; // number of domains in vertical order
} *PDOMAININFO;
typedef class COMPACTMAP
{
public:
LONG x;
LONG y;

21
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal
LONG dx;
LONG dy;
int size;
int contrast[3];

int brightness[3];
COMPACTMAP *next;
COMPACTMAP(LONG rx, LONG ry, int rangesize)
{x = rx; y = ry; size = rangesize; }
} *PCOMPACTMAP;

Việc tìm ánh xạ chính xác được thực hiện bằng hàm FindMap. Hàm này sử
dụng công thức bình phương nhỏ nhất để tìm contrast factor, brightness offset và lỗi.

22
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Tổng kết
1. Đánh giá phương pháp nén ảnh Fractal
Phương pháp nén ảnh fractal không được sử dụng rộng rãi, một phần là do kỹ
thuật này có bản quyền, muốn sử dụng phải xin phép và trả tiền, nhưng chủ yếu là do
tốc độ nén của phương pháp này chậm hơn rất nhiều so với các phương pháp khác.
Mặc dù rất nhiều cải tiến đã được đưa ra nhưng tốc độ của kỹ thuật này vẫn chậm
hơn nhiều so với phương pháp JPEG. Mặt khác, chất lượng ảnh nén ở các tỉ số nén
trung bình cũng kém hơn so với ảnh nén cùng tỉ số bằng phương pháp nén JPEG.
Tuy nhiên ưu điểm chính của phương pháp nén ảnh fractal là nó có thể đạt tới tỉ số
nén rất cao có khi đạt đến 70:1 hay hơn nữa so với giới hạn còn chấp nhận được 25:1
của JPEG. Phương pháp này còn có hai ưu điểm khác so với các phương pháp khác
là tốc độ giải nén vượt trội và tính độc lập về độ phân giải, một tính chất có lẽ sẽ rất
hữu dụng (Tất nhiên tính độc lập về độ phân giải của ảnh giải nén là có giới hạn do
thông tin có trong ảnh gốc là có giới hạn. Ta không thể phóng lớn ảnh để đọc báo ở
khoảng cách hàng ngàn km được).

2. Một số phương hướng phát triển
Chương trình này có tỉ số nén và chất lượng ảnh rất kém so với ảnh nén bằng
phương pháp nén JPEG. Các khác biệt là có thể nhận thấy được bằng mắt thường.
Nguyên nhân của tình trạng này là do trong các ảnh thông thường, có rất nhiều chỗ
tương tự nhau, thế nhưng các vùng tương tự nhau đó không hoàn toàn giống nhau,
mặt khác phần lớn những chỗ tương tự nhau đó chỉ là tương tự nhau ở đường nét của
một đối tượng.
Để nâng cao năng lực của phương pháp, ta có thể sử dụng nhiều biện pháp như
thay đổi hình dáng range và domain, sử dụng thêm các phép quay và đối xứng trong
ánh xạ, nhưng có một hướng đi khác, hướng đi này dựa vào nhận xét, đó là các khu
vực ttương tự nhau đối với người thì chỉ khác nhau ở các chi tiết nhỏ, do vậy nếu ta
có một bộ lọc làm nhoè hình ảnh (bộ lọc soften) nhưng có thể đảo ngược được (chỉ
cần ở mức gần đúng), ta có thể giảm bớt sự khác nhau giữa hai khối ảnh do đó cải
23
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

thiện khả năng nén và chất lượng ảnh. Để có được hình ảnh ban đầu, sau khi giải nén
ta cần áp dụng một bộ lọc sharpen nghịch đảo của bộ lọc soften đã sử dụng để thu
được hình ảnh ban đầu.

Phụ Lục
MỘT SỐ KẾT QUẢ THỰC HIỆN
* Smooth: làm mờ vùng được chọn trong ảnh. Thường dùng để giảm nhiễu bằng
cách khoanh vùng có nhiều nhiễu và thực hiện smooth.

ảnh gốc

ảnh sau khi smooth

ảnh gốc được tạo với một số điểm nhiễu nhỏ. Khoanh vùng tập trung các điểm
nhiễu, thực hiện smooth. Kết quả cả vùng được chọn này bị mờ đi. Tức là giảm
nhiễu xong cũng làm mờ chi tiết ảnh. Sau sẽ dùng các phương pháp khác để khôi
phục lại các chi tiết này. Phương pháp khử nhiễu này chỉ thích hợp với những nhiễu
có mức xám là rất nhỏ so với các chi tiết ảnh. Khi đó các chi tiết sẽ bị mờ ít đồng
thời loại bỏ được nhiễu.
* Sharpen: tăng độ tương phản và làm nổi bật (accentuate) các chi tiết trong vùng
được chọn song cũng làm tăng nhiễu. Để giảm thiểu sự tăng nhiễu này ta cần
Smooth hay Reduce Noise trước. Nói chung cần tăng độ tương phản hay làm nổi bật
phần nào của ảnh thi ta khoanh vùng đó lại

24
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN


Kỹ thuật nén ảnh Fractal

Không smooth trước khi sharpen

Smooth trước khi sharpen

Trong ảnh do muốn làm nổi bật dòng chữ Hilton nên ta
chọn vùng chữ này và thực hiện hai phép biến đổi sharpen
có và không dùng smooth trước. Các vùng khác được giữ
nguyên.
 Phần ảnh gốc có chữ Hilton cần làm nổi bật.
* Shadow: tạo ra hiệu ứng bóng với ánh sáng xuất hiện từ hướng được chọn trong
một dialog box. Mỗi chi tiết của ảnh có thể rõ hơn đồng thời cũng tăng nhiễu. Dùng

tạo nhanh hiệu ứng bóng cho đối tượng của ảnh.
* Find Edges: thực hiện thao tác dò biên, phát hiện biên ảnh.

ảnh gốc

Phát hiện biên

* Rank Filters…: gồm ba phương pháp
Median : sắp xếp mỗi ma trận 3x3 pixel lân cận và thay thế pixel trung tâm với
giá trị ở vị trí giữa (median). Phương pháp này dùng để giảm nhiễu. Để thực hiện tốt
việc giảm nhiễu theo cách này ta cần khoanh vùng cẩn thận.

ảnh gốc

ảnh sau khi lọc Median

Kết quả lọc nhiễu trong trường hợp ảnh như hình trên là khá tốt. Tức là ảnh chỉ
có hai mức sáng thì nhiễu luôn được thay bằng màu hoặc của nền hoặc màu của chi
25
Lớp K12T3 - ĐH Công nghệ - ĐHQGHN