Báo cáo nén ảnh phân đoạn
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (399.44 KB, 18 trang )
Fractal Image Compression
Nén ảnh phân đoạn
Đề tài nghiêng cứu về quá
trình nén ảnh phân đoạn cho
cả ảnh GrayScale và ảnh màu
RGB
Viết chương trình ứng dụng
Nén ảnh phân đoạn là gì ?
Là quá trình phân chia hình ảnh
thành các vùng nhỏ hơn . Kế đến
tìm một IFS cho từng vùng tương
ứng và lưu trữ vào file .
IFS – Iterated Function Systems ?
IFS là một tập các ánh xạ hội tụ
( contractive ) sử dụng các chuyển đổi
affine để biến đổi hình ảnh thành công
thức .
Ánh xạ là hội tụ khi nó làm giảm đi
khoảng cách : khoảng cách giữa ƒ(x) và
ƒ(y) thì nhỏ hơn khoảng cách giữa hai
điểm x và y .
IFS – Ví Dụ
Hàm ƒ(x) = x/2 . Khởi đầu với một giá
trò x
0
=1thì hàm sẽ hội tụ về 0 .
x
1
= ƒ(x
0
) = 1/2
x
2
= ƒ(ƒ(x
0
)) = 1/4 .
…
x
n
= ƒ(…(ƒ(x
0
))…) 0 .≈
Lược đồ mã hóa
Fractal
Gồm 4 bước :
Bước 1 : Phân đoạn – partition .
Bước 2 : Tạo Domain Block Pool .
Bước 3 : Chuyển đổi affine .
Bước 4 : Lượng tử hóa .
Phân
Đoân .
Create Domain
Block Pool
Chuyển
đổi affine
Lượng
tử hóa
FRC
file
TGA file
Bước 1 : Sự Phân Đoạn .
Là việc phân chia hình ảnh thành các
range (vùng) không chồng lấp và bao
phủ toàn bộ hình ảnh .
Các range thường được phân chia
thành hình vuông , hình chữ nhật hoặc
tam giác với kích thướt tùy ý , thường là
4x4 , 4x8 …
Bước 2 : Domain Block Pool
Là những vùng chứa các Domain
(miền) . Domain là những miền
giống với range nhưng có kích
thướt lớn hơn ( thường là gấp 2
lần ) để chắc rằng sự ánh xạ từ
Domain sang Range là hội tụ .
Bước 2 (tt) :
Tạo Domain Block Pool
Bằng các trược một cửa sổ có kích thước
2Bx2B ,bỏ qua δ pixel từ trái qua phải và
từ trên xuống dưới .
Ví dụ : ảnh 256x256 , δ=4 , B=4 thì ta có:
+
−
+
−
1
2
*1
2
δδ
BMBM
Tức là ta có 65x65 khối Domain trong một
Domain Block Pool .
Bước 3 : Chuyển đổi Affine
Với một cặp range và domain tương ứng khớp
nhất , ta sử dụng hàm
cpKp
+=
)(ƒ
Nghóa là tương ứng với một Domain thứ i có
tọa độ (x,y) và độ chói là z thì sẽ là :
+
=
i
i
i
i
ii
ii
i
b
d
d
z
y
x
c
aa
aa
z
y
x
w
2,
1,
4,3,
2,1,
00
0
0
1. a
i,j
, d
i,j
: xác đònh các thành phần hình học .
2. c
i
, b
i
: thể hiện độ tương phản và độ sáng .
Bước 3 : Chuyển đổi
Affine.
(tt)
Để phương trình hội tụ thì c
i
<1 ( nghóa là
các chuyển đổi sẽ hội tụ ở độ tương
phản ) . Khi đó , phương trình sẽ có nghiệm
duy nhất :
∑
∞
=
=
0
*
i
i
cKp
Bước 4 : Lượng tử hóa .
Sau khi chuyển đổi affine , ta sẽ tiến hành
lượng tử hóa cho các thông tin cần thiết để
lưu vào file .
Lượng tử hóa là quá trình làm giảm đi số bit
cần lưu trữ .
Ví dụ như đối với thành phần hình học a
i,j
và
d
i,j
. Chỉ có 8 khả năng cho thành phần này là
quay 4 và đối xứng 4 . Cho nên chỉ cần 3 bit
để mã hóa chúng .
Độ Đo .
Để so sánh giữa Domain và Range , ta sử
dụng độ đo RMS – Root Mean Square .
Nhưng để đơn giản , ta thay RMS bằng
tổng sai số bình phương , tránh được quá
trình lấy căn thức :
∑
=
−+=
n
i
ii
rbcdbcE
1
2
)(),(
Lược Đồ Giải Mã
Fractal
Bộ Giải Nén
FRC file
Lặp i Lần
TGA file
Nạp FRC file .
Đọc các chuyển đổi affine .
Khởi tạo lại các Range bằng Pixel .
Lặp lại i lần ( thường từ 6 – 10 lần ) để phương
trình hội tụ .
Ghi vào TGA file .
Mã Hóa Cho Ảnh Màu .
Ảnh màu RGB bao gồm 3 thành phần :
Đỏ , Xanh lá cây và Xanh dương . Vì thế ,
ta sử dụng lược đồ mã hóa cho mỗi thành
phần màu riêng biệt .
Ví dụ như đối với màu đỏ , ta phân chia
thành các Range , tìm Domain màu đỏ
tương ứng trong hồ khối Domain đỏ ,
chuyển đổi affine với hàm tương ứng và
ghi vào file . Đối với 2 màu còn lại cũng
làm tương tự .
Thửỷ Nghieọm .
Keỏt quaỷ thửỷ nghieọm
Kết Luận .
Mặc dù có tỉ số nén khá thuyết phục
nhưng chương trình tỏ ra khá chậm so
với các giải thuật nén tương tự .
Mới giải quyết được với các file
TGA .
Chương trình chưa tích hợp được với
các giải thuật nén văn bản và âm
thanh .
Kết Luận (tt) .
Hướng phát triển .
Tăng tốc chương trình bằng việc cải
tiến giải thuật và sử dụng ngôn ngữ
lập trình thích hợp hơn như Matlab .
Mở rộng cho các file khác như
*.bmp , *.raw …
Tích hợp chương trình với các giải
thuật nén văn bản và âm thanh để tạo
thành một chương trình nén hoàn
chỉnh .
Xin Chaân Thaønh
Caûm Ôn
