Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
Trước hết , em xin chân thành cảm ơn các thầy , các
cô trong khoa Công Nghệ Thông Tin, trường Kỹ Thuật
Công Nghệ , những người đã trao cho em rất nhiều kiến thức
q báu để em có được ngày hôm nay .
Xin chân thành cảm ơn thầy Đoàn Công Hùng , người
đã cho em ý tưởng , và thầy Lê Ngọc Anh , người đã tận tình
giúp đở em trong suốt quá trình thực hiện đồ án .
Cuối cùng , xin được cám ơn gia đình , các bạn bè và
tất cả mọi người đã giúp đở em rất nhiều để em có thể hoàn
thành đồ án tốt nghiệp .
Xin chân thành cảm ơn .
SVTH : Phạm Đào Minh Vũ Trang 1
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
MỤC LỤC
Chương I : Mở đầu .
I.Giới thiệu .
II.Lý thuyết tổng quan về nén số liệu .
II.1.Các khái niệm về nén số liệu .
II.2.Các kỹ thuật về nén số liệu .
II.2.1. Nén không tổn hao ( Lossless Compression ).
II.2.2. Nén tổn hao ( Lossy Compression ).
Chương II.Tìm hiểu về nén ảnh .
I.Lòch sử phát triển .
II. Các kỹ thuật nén phổ biến .
II.1.Nén thống kê và từ điển .
II.2.Nén có mất .
II.3.Điều biến sai số .
II.4.Nén đáp ứng .
Chương III.Nén ảnh phân đoạn – Fractal Image Compression .
I.Lòch sữ công nghệ nén ảnh Fractal .

II . Lược đồ giải mã .
II.1. Lược đồ giải mã .
II.2. Sự phụ thuộc độ phân giải .
Chương V. Thiết kế chương trình.
I . Các module chính .
II . Lưu đồ chương trình .
III . Chi tiết tại mỗi bước .
IV . Lưu đồ khối chức năng .
Chương VI. Thử nghiệm so sánh và hướng phát triển .
I . Thử nghiệm .
II . So sánh với một vài phương thức mã hóa thông dụng .
III . Ưu khuyết điểm và phương hướng phát triển .
Chương VII . Kết Luận .
Phụ lục và tài liệu tham khảo.
SVTH : Phạm Đào Minh Vũ Trang 3
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
CHƯƠNG
I Mở Đầu
 Giới thiệu .
 Lý thuyết tổng quan về nén số liệu .
 Các khái niệm về nén số liệu .
 Các kỹ thuật về nén số liệu .
 Nén không tổn hao ( Lossless Compression ).
 Nén tổn hao ( Lossy Compression ).
SVTH : Phạm Đào Minh Vũ Trang 4
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
I . Giới thiệu .
Trong thời đại ngày nay , với sự phát triển mạnh mẽ của khoa học công
nghệ thông tin , việc ứng dụng tin học hầu như đã vào trong tất cả mọi lónh vực
hoạt động sản xuất của con người ở các nước đã và đang phát triển trên thế giới

åí âáu, âãưu mún chia s thäng tin, thiãút bë våïi ngỉåìi khạc hồûc qun l thäng tin
v thỉûc hiãûn ton bäü cạc tạc vủ ny mäüt cạch nhanh chọng, dãù dng våïi âäü an ton
chênh xạc cao. Ngoi ra, hiãûn nay åí nỉåïc ta ngành du lòch để giới thiệu với bạn
bè thế giới về đất nước , về con người , cũng như các công ty sản xuất muốn
cho thế giới biết đến các sản phẩm mang đậm bản sắc dân tộc đòi hỏi rất nhiều
dung lượng lưu trữ . Do âọ, bãn cảnh viãûc ci tiãún pháưn cỉïng nhỉ: Modem, âỉåìng
truưn ta cn phi tçm cạch gim dung lỉåüng dỉỵ liãûu cáưn thiãút trỉåïc khi truưn âãø
gim âỉåüc thåìi gian truưn v bäü nhåï. Âäúi våïi mảng Internet, thỉûc hiãûn täút âiãưu âọ
cho phẹp gim âỉåüc cỉåïc phê truy cáûp mảng.
Váûy nẹn dỉỵ liãûu l gç ? Ta cọ thãø khại quạt : Nẹn l quạ trçnh gim dung lỉåüng
cáưn thiãút m váùn biãøu diãùn cng mäüt dỉỵ liãûu cho trỉåïc .
Trong truưn thäng säú liãûu , nẹn l mäüt k thût âỉåüc ạp dủng mäüt cạch linh
hoảt cho lưng thäng tin âang truưn . Cäng nghãû bãn trong vãư cå bn cng nhỉ
nhau trong c hai trỉåìng håüp l: loải b thäng tin dỉ thỉìa hồûc biãøu thë thäng tin
dỉåïi dảng chàût ch hån âãø gim täøng säú byte phi truưn qua phỉång tiãûn truưn
thäng nhàòm gim âãún tháúp nháút thåìi gian chiãúm phỉång tiãûn ca mäüt cüc truưn
â cho.
Âäúi våïi nẹn dỉỵ liãûu trãn mạy PC, cọ nhiãưu thût toạn nẹn khạc nhau âỉåüc thiãút
kãú cho nhiãưu loải dỉỵ liãûu khạc nhau nhỉ: vàn bn, hçnh nh, ám thanh Trong
phảm vi ca âäư ạn, ta chè xẹt âãún cạc phỉång phạp hình ảnh .
II . Lý thuyết tổng quan về nén số liệu .
II.1. Các khái niệm về nén số liệu .
Nẹn säú liãûu l quạ trçnh lm gim säú liãûu cáưn thiãút âãø biãøu diãùn cng mäüt lỉåüng
thäng tin cho trỉåïc. Cạc k thût nẹn säú liãûu cọ thãø âỉåüc thỉûc hiãûn bàòng phán cỉïng
chun dủng hồûc pháưn mãưm.
Cạc k thût nẹn säú liãûu bàòng pháưn cỉïng âi hi phi cọ cạc pháưn cỉïng âàûc biãût
âỉåüc thiãút kãú thêch håüp våïi bàng thäng cäú âënh ca mảng truưn säú liãûu. Cạc k
SVTH : Phạm Đào Minh Vũ Trang 6
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
thût nẹn säú liãûu bàòng pháưn mãưm âỉåüc thỉûc hiãûn trãn mạy tênh cạ nhán (PC) cọ thãø

Nẹn täøn hao l k thût nẹn cháúp nháûn máút mạt mäüt lỉåüng thäng tin nháút âënh
âãø âảt âỉåüc hiãûu qu nẹn cao. Cọ thãø nọi mäüt cạch tỉång tỉû: Nẹn täøn hao= Lm
SVTH : Phạm Đào Minh Vũ Trang 7
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
trån + Nẹn khäng täøn hao. Lm trån l quạ trçnh thỉûc hiãûn mäüt phẹp biãún âäøi no
âọ (nhỉ: biãún âäøi säú liãûu tỉì miãưn thåìi gian sang miãưn táưn säú bàòng phẹp biãún âäøi
Furiã råìi rảc gi l FFT ( Fast Fourier Transform), hồûc phẹp biãún âäøi Cosin råìi
rảc gi l DCT (Discrete Cosine Transform) ), tiãúp âọ l quạ trçnh lỉåüng tỉí hoạ.
Säú liãûu cng âỉåüc lm trån thç máút mạt thäng tin cng nhiãưu v tè säú nẹn cng cao.
Nẹn täøn hao thêch håüp våïi cạc file hçnh nh, ám thanh âỉåüc säú hoạ. Háưu hãút cạc
k thût nẹn täøn hao âãưu cọ thãø âỉåüc âiãưu chènh âãø cán bàòng giỉỵa âäü chênh xạc v
hiãûu qu nẹn. Cạc phỉång phạp nẹn täøn hao nhỉ: phỉång phạp JPEG, phỉång phạp
Wavelet, phỉång phạp MPEG
SVTH : Phạm Đào Minh Vũ Trang 8
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
CHƯƠNG
II Lòch Sử Nén Ảnh
 Lòch sử phát triển .
 Các kỹ thuật nén phổ biến .
 Nén thống kê và từ điển .
 Nén có mất .
 Điều biến sai số .
 Nén đáp ứng .
SVTH : Phạm Đào Minh Vũ Trang 9
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
I. Lòch sử phát triển .
Con người giao tiếp với máy tính chủ yếu thông qua màn hình , vì thế đồ
họa chính là sự quan tâm chính của các nhà thiết kế và các lập trình viên trên
thế giới . Các nhà lập trình đã mất rất nhiều thời gian và nổ lực để phát triển
giao diện đồ họa người dùng ( Graphical User Interface – GUI ) . Hàng triệu

Trong suốt một thập kỉ trước , công việc nghiên cứu cho mục đích lưu trữ
các hình ảnh đã có một số kết quả rất khả quan . Trong những năm cuối 1970
vàđầu 1980 , hầu hết các phương pháp nén ảnh chỉ tập trung vào sử dụng công
nghệ nén không mất ( lossless compression ) truyền thống . Các đònh dạng file
nén phổ biến sử dụng công nghệ này là PCX , GIF , BMP … Chúng làm giảm
dung lượng các file gốc từ 10% - 90% dung lượng ban đầu .
Khi việc sử dụng các hình ảnh đồ họa tăng lên , các đònh dạng file như là
PCX trở không thõa đáng nữa . Làm giảm đi một nữa kích thước của file là một
điều đáng làm , nhưng trong khi đó nhưng người thiết kế và người sử dụng đang
sài hết các khoảng trống trên ổ đóa của họ một cách nhanh chóng bởi các ứng
dụng đa phương tiện đang làm chúng trở nên không còn tính khả thi .
II. 1 . Các phương pháp nén thống kê ( Statistical Compression ) và từ
điển ( Dictionary Compression ) .
Các chương trình truyền thống và các dữ liệu trên máy tính thì đáp ứng
rất tốt việc nén trên nền tảng lợi dụng sự thống kê mức độ thay đổi trong tần số
xuất hiện của các kí tự riêng lẻ và chuỗi các kí tư hay một cụm kí tự . Hệ thống
trên nền tảng từ điển thật sự được ngụy trang dưới lớp vỏ chương trình thống kê
. Tuy nhiên , có một số các kiểu nén không có khuynh hướng nén tốt đối với
các hình ảnh có sắc màu liên tục .
Vấn đề chính ở đây có một số chương trình bắt nguồn từ sự thật là các
điểm ảnh trong các ảnh chụp có khuynh hướng trải rộng ra trên toàn bộ phạm
vi của chúng . Nếu các màu sắc trong một hình ảnh được đánh dấu như là một
biểu đồ thống kê trên cơ sở tần số xuất hiện , thì biểu đồ đó không có “nhọn”
( spiky ) như chúng ta mong muốn nén thống kê thực thi . Thật sự , trên việc
vận hành lâu dài , các biểu đồ về hình ảnh sống động có khuynh hướng là
phẳng . Điều này có nghóa là mỗi mã điểm ảnh đều có cùng cơ hội thể hiện như
bất kỳ điểm nào khác .
SVTH : Phạm Đào Minh Vũ Trang 11
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
Các chương trình nén trên nền tảng từ điển đều gặp những vấn đề tương

Dữ liệu âm thanh được lấy mẫu sử dụng các đònh dạng truyền thống thì
có đặc trưng lặp đi lặp lại ( repetitive ) . Âm thanh , bao gồm cả giọng nói ,
được tạo ra từ các sóng sine , lặp lại mỗi giây tại mỗi thời điểm . Mặc dù dòng
vào tại bộ DAC trên máy tính bao gồm hàng tá các tần số khác nhau được thêm
SVTH : Phạm Đào Minh Vũ Trang 12
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
vào với nhau thì sóng sine nói chung vẫn kết hợp để tạo ra dạng sóng lặp
( repetitive waveforms ) .
Tính lặp lại tự nhiên của dữ liệu âm thanh có thể dùng cho việc nén .
Các công nghệ như là mã hóa đoán trước tuyến tính ( Linear Predictive
Coding ) và sự điều biến mã xung sai số đáp ứng ( Adaptive Differential Pulse
Code Modulation ) đã lợi dụng điều này để mã hóa các dòng âm thanh với xác
xuất từ 50 – 90 phần trăm .
Khi sự nghiên cứu bắt đầu trên việc nén các ảnh đồ họa , các ảnh số hóa
đã được áp dụng với các công nghệ tương tự và đã có một vài sự thành công .
Khởi đầu , các nhà nghiên cứu thực hiện trên việc nén các dòng dữ liệu được
lưới hóa ( rasterized data ) . Khi các hình ảnh được số hóa , nó sẽ hiển thò như
là một chuỗi tuần tự các điểm ảnh . Một dòng tại một thời điểm được hiển thò
trên màn hình sẽ làm việc từ trái sang phải và từ trên xuống dưới . Vì thế , một
lát mỏng của hình ảnh sẽ được vẽ khi mỗi dòng hoàn thành , cho đến khi hình
ảnh được hiển thò đầy đủ trên màn hình . Khi được số hóa , các điểm ảnh có
kích thước từ một đến hai mươi bốn bit . Các màn hình đồ họa ngày nay sử
dụng 8 bit để xác đònh một điểm ảnh .
II. 3 . Sự điều biến sai số ( Differential Modulation ) .
Sự điều biến sai số phụ thuộc vào khái niệm rằng các dữ liệu tín hiệu
tương tự có khuynh hướng biến thiên trong các mẫu trơn mòn ( smooth patterns )
, với các bước nhảy căn bản trong biên độ tín hiệu là ngoại lệ , không theo
nguyên tắc . Trong dữ liệu tín hiệu âm thanh , điều này là đúng miễn sao tỉ lệ
lấy mẫu của tín hiệu là một vài cái gì đó cao hơn thành phần tần số cực đại .
Sự điều biến sai số của một tín hiệu âm thanh lợi dụng việc này bằng

tiếp sẽ cùng nằm trong một vùng với xác xuất rất cao . Một lược đồ mã hóa dựa
trên nền tảng entropy , như mã hóa Huffman hay Arithmetic , có thể gán xác
suất xuất hiện vào các mã mới . Giả sử rằng phương pháp dự đoán cho phép
chúng ta tạo ra một sự tiên đoán về xác suất xuất hiện của các pixel , chúng ta
sẽ có :
Hình 1 . Adaptive coding
Hầu hết các lược đồ đáp ứng dựa vào việc sử dụng một vài các điểm ảnh
chung quanh như là một phần của sự tính toán cho xác xuất xuất hiện của
SVTH : Phạm Đào Minh Vũ Trang 14
Previous Row -1,-1 -1,0 -1,1
Current Row
0,-1 0,0
Target
Pixel
A
B C D
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
upcomming pixel . Trong hình trên , một điểm ảnh được mã hóa được thể hiện
tại vò trí (0,0) . Còn các điểm ảnh khác như A, B ,C ,D được dùng một cách bình
thường trong việc tính toán xác suất xuất hiện . Sự dự đoán các giá trò
upcoming của pixel đích ( target ) có thể được làm trên cơ bản một vài phương
trình dự đoán :
Hình 2 . Sự dự đoán điểm ảnh .
Một số công nghệ sử dụng các dữ liệu trên để tính toán hầu hết giá trò có
thể có của điểm ảnh đích , và sau đó chúng hiệu chỉnh lược đồ mã hóa . Trong
khi các việc tính toán đó cho ra kết quả khả quan thì một lần nữa nó được xem
như là một kỹ thuật không hiệu quả trong công nghệ nén ảnh .
SVTH : Phạm Đào Minh Vũ Trang 15
A
B

học thuyết Hệ Thống Chức Năng Được Lặp Lại ( Iterated Function Systems ) ,
viết tắt là IFS , đầu tiên được giới thiệu bởi J.Hutchinson năm 1981 . Sau khi
phát hành cuốn sách “Fractals Everywhere” năm 1988 thì nén Fractal trở nên
là một chủ đề rất thời thượng . Điều hấp dẫn của công nghệ này là tỉ lệ nén hấp
dẫn của nó , tăng từ 10000 lên 1 .
Thật không may , tỉ lệ nén đó có thể đạt được chỉ với những hình ảnh
được cấu trúc đặc biệt và chỉ với sự trợ giúp đáng kể của người hướng dẫn tiến
trình nén . Quá trình này được biết như là “Graduate Student Algorithm” ( tạm
dòch là “ Giải Thuật Sinh Viên Tốt Nghiệp “ ) . Nghóa là cho một sinh viên tốt
nghiệp vào một văn phòng và trạm làm việc đồ họa , khóa cửa lại , chờ cho
đến khi người sinh viên đó tìm ra được một IFS tốt nhất cho hình ảnh , và mở
cửa ra . Tiến trình nén này không thể hoàn thành một cách tự động , thậm chí
với siêu máy tính . Vì thế , việc nén dựa trên nền tảng IFS hóa ra không thực
tế .
SVTH : Phạm Đào Minh Vũ Trang 17
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
Năm 1988 , ông Arnaud Jacquin , một học trò của Barnsley đã tạo ra một
điểm mốc của việc nén . Thay cho việc tìm ra một IFS cho một hình ảnh hoàn
chỉnh , ông đã có những ý tưởng về sự phân chia hình ảnh thành những vùng
( range ) không chồng lấp và tìm ra một IFS riêng cho mỗi ảnh phân chia đó .
Điều này sẽ biến vấn đề phức tạp trên thành một tác vụ có thể quản lý được ,
điều mà có thể được làm một cách tự động . Trong luận văn tiến só , ông ta đã
phát triển lý thuyết Hệ Thống Chức Năng Lặp Lại Được Phân Chia ( Partitioned
Iterated Function Systems ) , viết tắt là PIFS , và thực hiện một phiên bản về
giải thuật của ông ta trong phầm mềm .
Năm 1991 , Barnsley và Sloan đạt được bằng sáng chế Mỹ về công nghệ
này . Công ty của họ , Iterated Systems , thì bán những sản phẩm phần mềm và
phần cứng sử dụng nó , nhưng không có tung ra chi tiết về công nghệ này . Đặc
biệt , FIF ( Fractal Image Format) được sử dụng bởi các sản phẩm của Iterated
Systems thì càng không được mô tả rộng rãi . Chính vì điều này mà nén ảnh

1 . Áp dụng dấu hiệu và chiều ( không gian ) như là một đặc trưng
vào trong phân đoạn ảnh , phân tích bố cục , …
2 . Áp dụng IFS ( Iterated Function Systems ) vào trong quá trình
nén ảnh .
Hệ thống mã hóa và giải mã Fractal được thể hiện trong sơ đồ bên dưới .
Tại giai đoạn mã hóa , cho mỗi khối range , một chuyển đổi thu nhỏ và khối
domain đïc tìm thấy , sau đó sự chuyển đổi thu nhỏ và vò trí của các domain
sẽ được truyền đi đến đầu ra thông qua một kênh . Ở giai đoạn giải mã , hình
SVTH : Phạm Đào Minh Vũ Trang 19
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
ảnh được tái tạo lại sử dụng các chuyển đổi và vò trí các khối domain ở trên
bằng việc lặp nhiều lần công việc này
Hình 5 . Sơ đồ mã hóa và giải mã .
III . Iterated Function System ( IFS ) là gì ?
Chúng ta điều thấy rằng tất cả các hình ảnh phức tạp có thể thu được từ
những công thức đơn giản . Việc đưa ra một công thức sẽ dễ dàng dẫn xuất ra
một hình ảnh tương ứng . Nhưng nếu đi theo một hướng ngược lại , từ ảnh đến
công thức , thì điều này sẽ là khả thi hơn , nó sẽ cho một tỉ lệ nén tuyệt vời .
Thay cho việc thể hiện một ảnh như là một trình tự các giá trò điểm ảnh , hình
ảnh có thể được khởi tạo lại từ một công thức , điều mà sẽ tốn rất ít dung lượng
lưu trữ . Ta hãy thử xét một ví dụ sau :
Giả sữ rằng để thể hiện một cái đóa tròn màu đen trên nền trắng ,
ta phải liệt kê tất cả các điểm ảnh trên cái đóa đó với hai chiều ngang và
dọc , thì ngược lại , ta có thể đưa ra một phương trình cho ảnh này , chỉ
đònh nó như là một tập các điểm (x,y) :
(x – a)
2
+ (y – b)
2
< r

Một ánh xạ từ một tập vào chính nó thì được gọi là co lại ( contractive )
nếu nó làm giảm khoảng cách : khoảng cách giữa f(x) và f(y) thì nhỏ hơn
khoảng cách giữa 2 điểm x và y . Ví dụ như hàm f(x) = x/2 được đònh nghóa
trên tập các số thực là co lại được . Biểu diễn đònh lý ánh xạ thu nhỏ
( Contractive Mapping ) một cách ngắn gọn , rằng ánh xạ co lại có một điểm
được cố đònh duy nhất , nghóa là giá trò x thì tương đương với f(x) = x . Hơn nữa ,
điểm được cố đònh có thể thu được bởi việc bắt đầu từ bất kỳ điểm x
0
nào và cứ
việc tính theo trình tự :
x
1
= f(x
0
)
x
2
= f(x
1
) = f( f(x
0
) )
vv…
Trình tự trên sẽ hội tụ về một điểm duy nhất . Cho một ví dụ, bắt đầu với
giá trò x
0
= 1 và áp dụng cho hàm f(x) = x/2 , chúng ta sẽ thu được kết quả là 1 ,
1/2, 1/4 , 1/8, … và cuối cùng chúng sẽ tiến về 0 . Ví dụ trên đưa ra một tập các
số thực IR nhưng đònh lý ánh xạ hội tụ cũng áp dụng cho các chiều không gian
khác , ở đây là hình ảnh 2 chiều .

Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
Hình ảnh kết quả là một Fractal , bởi vì nó chứa đựng các bản sao thu
nhỏ của chính nó tại tất cả các mức . Ta sẽ thấy chi tiết hơn nếu chúng ta phóng
to một phần của ảnh lên . Vì tính chất tự giống nhau ( Seft – Similarity ) này ,
ảnh được nén sử dụng IFS thì xứng đáng với tên gọi là nén ảnh Fractal ( Fractal
Image Compression ) .
Trên đây , chúng ta chỉ đề cập đến hình ảnh đen trắng ( gray scale )
nhưng nó cũng có thể được áp dụng cho các ảnh màu . Vấn đề này chúng ta sẽ
thảo luận ở phần sau .
V . Nén ảnh với IFS .
Một IFS cho một sự xấp xỉ tốt của một hình ảnh I nếu điểm cố đònh của
IFS là một ảnh gần tương đồng với I . Mục đích là để tìm một tập các ánh xạ
hội tụ w
1
… w
N
để hội với W của tất cả các ánh xạ có điểm cố đònh gần với I .
Điều này thì thật không khả thi bởi việc ta phải thử vài ánh xạ , tính toán
các điểm cố đònh kết quả , so sánh nó với I và bắt đầu lại với những ánh xạ
khác cho đến khi một cái hợp nhất được tìm thấy . Thay vào đó , chúng ta sẽ
thử tìm ra một ánh xạ hội tụ W sao cho W(I) thì gần giống với I . Đònh lý
Collage của Barnsley nói rằng nếu W(I) là đủ gần với I thì điểm cố đònh
W
∞
(1) = W(W(W … W(1) … ))
cũng gần với I . Ảnh W(I) thì bao gồm việc cắt dán ( hội lại ) của tất cả các ảnh
thu nhỏ Wj(I) .
Với sự giúp đỡ của đònh lý Collage , vấn đề trên có thể được bắt đầu lại
như là việc tìm kiếm một nghệ thuật cắt dán tốt cho ảnh . Đây là nơi mà sự khó
khăn thực sự bắt đầu . Nói chung là không khả thi để tìm ra một nghệ thuật cắt

không bằng với ảnh gốc .
Cái khó khăn chính của tiến trình nén là tìm ra bên trong ảnh những
phiên bản thu nhỏ của toàn bộ ảnh . Hình ảnh trong thế giới thực thường chứa
nhiều cái tương tự với nó , nhưng chỉ ở giữa những phần được chọn của ảnh .
Bước đột phá ở đây là: với mỗi phần được chia trong ảnh gốc , tìm một IFS cục
bộ cho mỗi phần đó . Với phương pháp mới này thì cuối cùng chúng cũng trở
nên khả thi trong việc thực hiện tự động tiến trình nén và hơn thế nữa là để
thực hiện nó trong một khoảng thời gian cho phép .
VI . Nén ảnh với Partitoned Iterated Function Systems – PIFS .
Như đã nói ở phần trước , nén là một công việc làm giảm đi sự dư thừa
dữ liệu . Ở đây cũng tương tự như thế , các giải thuật nén ảnh cũng như là lượng
tử hóa vector ( Vector Quantization ) và nén Fractal ( Fractal Compression ) có
sự tham gia của PIFS bằng việc làm giảm sự dư thừa của hình ảnh đầu vào .
SVTH : Phạm Đào Minh Vũ Trang 23
Nén Ảnh Phân Đoạn GVHD : Ths. Lê Ngọc Anh
Những phương pháp nén các file văn bản thì là không mất dữ liệu ( lossless ) ,
ngược lại phương pháp nén ảnh là chỉ tìm một sự xấp sỉ và vì thế chúng luôn
có mất .
Lượng tử hóa vector ( Vector Quantization ) sử dụng từ điển ( hoặc là
sách mã – codebook ) chứa các mẫu pixel . Hình ảnh vào được phân chia thành
các khối pixel nhỏ , và mỗi khối được mã hóa như một mẫu tương ứng với hầu
hết các mẫu có sẵn trong từ điển . Thường thì một khối có cùng kích thước với
các mẫu tự điển nhưng tất cả các khối không cần phải như vậy , chúng có thể
có kích thước khác nhau . Bộ giải mã phải có phiên bản của từ điển và như vậy
chúng có thể dễ dàng khởi tạo lại một ảnh xấp xỉ với hình ảnh ban đầu bằng
việc kết hợp lại các mẫu từ điển được chỉ đònh bởi bộ mã hóa .
Nén Fractal với PIFS thì tương tự với lượng tử hóa vector , nhưng trong
trường hợp này không có tự điển bên ngoài . Hình ảnh đầu vào tương tác với từ
điển của chính nó . Bộ giải mã không có hình ảnh ban đầu , nhưng nó có thể
được tái tạo bằng việc lặp lại chu trình PIFS . Vì từ điển chỉ là một cuốn sách

phần độ chói . Khi đó một ánh xạ affine được kết hợp từ một thành phần hình
học ( thành phần ánh xạ domain sang range) và một thành phần độ chói (thành
phần thay đổi các giá trò mật độ pixel ) .
Hoàn toàn đúng như vậy , một điểm (x,y) với độ chói z tương ứng với
một domain Di được ánh xạ thành :










+















c
aa
aa
x
y
x
w
2,
1,
4,3,
2,1,
00
0
0
Các hằng số
ij
a
và
ij
d
chỉ đònh thành phần hình học , hằng số c
i
và b
i
chỉ đònh thành phần độ chói . c
i
thể hiện độ tương phản và nhỏ hơn một để chắc
rằng sự ánh xạ là hội tụ trong chiều độ chói . b
i
thể hiện thành phần độ sáng