Nén ảnh phân đoạn

Tröôùc heát , em xin chaân thaønh caûm ôn caùc thaày , caùc coâ trong khoa Coâng Ngheä Thoâng Tin, tröôøng Kyõ Thuaät Coâng Ngheä , nhöõng ngöôøi ñaõ trao cho em raát nhieàu kieán thöùc quí baùu ñeå em coù ñöôïc ngaøy hoâm nay . Xin chaân thaønh caûm ôn thaày Ñoaøn Coâng Huøng , ngöôøi ñaõ cho em yù töôûng , vaø thaày Leâ Ngoïc Anh , ngöôøi ñaõ taän tình giuùp ñôû em trong suoát quaù trình thöïc hieän ñoà aùn . Cuoái cuøng , xin ñöôïc caùm ôn gia ñình , caùc baïn beø vaø taát caû moïi ngöôøi ñaõ giuùp ñôû em raát nhieàu ñeå em coù theå hoaøn thaønh ñoà aùn toát nghieäp . Xin chaân thaønh caûm ôn . MUÏC LUÏC Chöông I : Môû ñaàu . I.Giôùi thieäu . II.Lyù thuyeát toång quan veà neùn soá lieäu . II.1.Caùc khaùi nieäm veà neùn soá lieäu . II.2.Caùc kyõ thuaät veà neùn soá lieäu . II.2.1. Neùn khoâng toån hao ( Lossless Compression ). II.2.2. Neùn toån hao ( Lossy Compression ). Chöông II.Tìm hieåu veà neùn aûnh . I.Lòch söû phaùt trieån . II. Caùc kyõ thuaät neùn phoå bieán . II.1.Neùn thoáng keâ vaø töø ñieån . II.2.Neùn coù maát . II.3.Ñieàu bieán sai soá . II.4.Neùn ñaùp öùng . Chöông III.Neùn aûnh phaân ñoaïn – Fractal Image Compression . I.Lòch söõ coâng ngheä neùn aûnh Fractal . II . Söï phaân ñoaïn . III.IFS – Iterated Function Systems . III.1.IFS laø gì ? III.2.IFS cô baûn . III.3.Neùn aûnh vôùi IFS. III.4.Neùn aûnh vôùi PIFS. Chöông IV : Maõ hoùa vaø giaûi maõ . I . Löôïc ñoà maõ hoùa . I.1 Söï phaân chia khoái . I.1.1. Löôïc ñoà phaân chia ngang doïc truyeàn thoáng . I.1.2. Löôïc ñoà phaân chia ngang doïc ñöôïc hieäu chænh . I.1.3. So saùnh . I.2. Domain Block Pool . I.3. Chuyeån ñoåi affine ( Haøm maõ hoùa) . I.3.1. Duøng Vector . I.3.2. Duøng ma traän . I.3.3. Tính thu goïn - Contractive. I.3.3.1. Ma traän tam giaùc. I.3.3.2. Giaùm saùt caùc giaù trò phaàn töû. I.3.4. So saùnh. I.3.4.1. Maõ hoaù run-length . I.3.4.2. Maõ hoùa Ziv-lempel. I.3.4.3. Maõ hoùa tieân ñoaùn tröôùc . I.4. Löôïng töû hoùa . I.5. Maõ hoùa Fractal vôùi aûnh maøu . I.5.1. RIFS – Recurrent IFS . I.5.2. Caùc phöông thöùc maõ hoùa Fractal cho aûnh maøu . I.5.3. Caùc keát quaû moâ phoång vaø ñaùnh giaù . II . Löôïc ñoà giaûi maõ . II.1. Löôïc ñoà giaûi maõ . II.2. Söï phuï thuoäc ñoä phaân giaûi . Chöông V. Thieát keá chöông trình. I . Caùc module chính . II . Löu ñoà chöông trình . III . Chi tieát taïi moãi böôùc . IV . Löu ñoà khoái chöùc naêng . Chöông VI. Thöû nghieäm so saùnh vaø höôùng phaùt trieån . I . Thöû nghieäm . II . So saùnh vôùi moät vaøi phöông thöùc maõ hoùa thoâng duïng . III . Öu khuyeát ñieåm vaø phöông höôùng phaùt trieån . Chöông VII . Keát Luaän . Phuï luïc vaø taøi lieäu tham khaûo. CHÖÔNG I Môû Ñaàu Giôùi thieäu . Lyù thuyeát toång quan veà neùn soá lieäu . Caùc khaùi nieäm veà neùn soá lieäu . Caùc kyõ thuaät veà neùn soá lieäu . Neùn khoâng toån hao ( Lossless Compression ). Neùn toån hao ( Lossy Compression ). I . Giôùi thieäu . Trong thôøi ñaïi ngaøy nay , vôùi söï phaùt trieån maïnh meõ cuûa khoa hoïc coâng ngheä thoâng tin , vieäc öùng duïng tin hoïc haàu nhö ñaõ vaøo trong taát caû moïi lónh vöïc hoaït ñoäng saûn xuaát cuûa con ngöôøi ôû caùc nöôùc ñaõ vaø ñang phaùt trieån treân theá giôùi . ÔÛ nöôùc ta , nhaèm goùp phaàn vaøo coâng cuoäc Coâng Nghieäp Hoaù – Hieän Ñaïi Hoùa , vaán ñeà tin hoïc hoùa ñaõ vaø ñang ñöôïc trieån khai . Vieäc öùng duïng tin hoïc vaøo coâng taùc quaûn lyù vaø ñieàu haønh taïi caùc cô quan xí nghieäp ngaøy caøng cao vaø ñem laïi nhieàu hieäu quaû thieát thöïc . Bãn caûnh âoï, âäöng nghéa våïi noï laì váún âãö læu træî vaì xæí lyï dæî liãûu. Cuìng våïi thåìi gian, sæû cáûp nháût, læu træî dæî liãûu ngaìy caìng nhiãöu, âiãøn hçnh laì mäüt säú coâng ty xuaát nhaäp khaåu , coâng ty kinh doanh caùc dòch vuï haøng hoùa , du lòch , ... våïi mäüt khäúi læåüng låïn dæî liãûu cáön læu træ î. Vç váûy, váún âãö âæåüc âàût ra laì laìm sao læu træî dæî liãûu êt täún keïm nháút maì váùn âaím baío tênh an toaìn vaì chênh xaïc cuía noï ? Do âoï, viãûc tçm ra phæång phaïp giaím dung læåüng læu træî maì váùn âaïp æïng âæåüc yãu cáöu trãn laì ráút cáön thiãút. Chuïng ta tháúy ràòng: ngaìy nay våïi sæû phaït triãøn væåüt träüi trong cäng nghãû pháön cæïng, dung læåüng âéa cæïng tàng lãn mäüt caïch âaïng kãø vaì nhanh choïng. Mäüt loaût âéa cæïng khäng ngæìng tàng lãn vãö dung læåüng ra âåìi trong khi giaï thaình saín pháøm laûi haû. Bãn caûnh âoï coìn coï caïc thiãút bë læu træî khaïc nhæ bàng tæì, âéa quang , ñóa DVD vôùi dung löôïng treân 4.7G ... cuîng âæåüc sæí duûng räüng raîi. Tuy nhiãn, cuîng chênh vç lyï do naìy maì caïc nhaì láûp trçnh thæåìng sæí duûng báút cæï taìi nguyãn naìo coï thãø, kãút quaí laì nhiãöu saín pháøm pháön mãöm ra âåìi nhæng coï kêch thæåïc ráút låïn, chiãúm haìng tràm Mbyte. Thãm vaìo âoï, nhiãöu lénh væûc saín xuáút aïp duûng nhæîng pháön mãöm khaïc nhau, âãø âaïp æïng âæåüc nhu cáöu naìy âoìi hoíi ngæåìi sæí duûng tiãúp cáûn nhiãöu hån vaì taûo thoïi quen læu træî nhiãöu saín pháøm pháön mãöm, ngoaìi ra laì viãûc xæí lyï nhiãöu táûp tin vaì nhiãöu loaûi dæî liãûu khaïc nhau. Do váûy, neïn dæî liãûu váùn laì váún âãö cáön thiãút âæåüc thæûc hiãûn træåïc khi læu træî. Song song våïi váún âãö trãn, mäüt lénh væûc khäng thãø khäng kãø âãún laì maûng maïy tênh. Ngaìy nay, maûng maïy tênh maì moüi ngæåìi âãöu nhàõc âãún laì maûng Internet -maûng cuía caïc maûng- Coï thãø noïi ràòng: Internet laì maûng thäng tin toaìn cáöu vaì säú ngæåìi kãút näúi vaìo maûng âaî lãn âãún vaìi chuûc triãûu ngæåìi. Vç váûy, nhu cáöu truyãön thäng ráút låïn. Táút caí moüi ngæåìi âãöu muäún coï thãø tçm kiãúm thäng tin báút luáûn chuïng åí âáu, âãöu muäún chia seí thäng tin, thiãút bë våïi ngæåìi khaïc hoàûc quaín lyï thäng tin vaì thæûc hiãûn toaìn bäü caïc taïc vuû naìy mäüt caïch nhanh choïng, dãù daìng våïi âäü an toaìn chênh xaïc cao. Ngoaìi ra, hiãûn nay åí næåïc ta ngaønh du lòch ñeå giôùi thieäu vôùi baïn beø theá giôùi veà ñaát nöôùc , veà con ngöôøi , cuõng nhö caùc coâng ty saûn xuaát muoán cho theá giôùi bieát ñeán caùc saûn phaåm mang ñaäm baûn saéc daân toäc ñoøi hoûi raát nhieàu dung löôïng löu tröõ . Do âoï, bãn caûnh viãûc caíi tiãún pháön cæïng nhæ: Modem, âæåìng truyãön... ta coìn phaíi tçm caïch giaím dung læåüng dæî liãûu cáön thiãút træåïc khi truyãön âãø giaím âæåüc thåìi gian truyãön vaì bäü nhåï. Âäúi våïi maûng Internet, thæûc hiãûn täút âiãöu âoï cho pheïp giaím âæåüc cæåïc phê truy cáûp maûng. Váûy neïn dæî liãûu laì gç ? Ta coï thãø khaïi quaït : Neïn laì quaï trçnh giaím dung læåüng cáön thiãút maì váùn biãøu diãùn cuìng mäüt dæî liãûu cho træåïc . Trong truyãön thäng säú liãûu , neïn laì mäüt kyî thuáût âæåüc aïp duûng mäüt caïch linh hoaût cho luäöng thäng tin âang truyãön . Cäng nghãû bãn trong vãö cå baín cuîng nhæ nhau trong caí hai træåìng håüp laì: loaûi boí thäng tin dæ thæìa hoàûc biãøu thë thäng tin dæåïi daûng chàût cheî hån âãø giaím täøng säú byte phaíi truyãön qua phæång tiãûn truyãön thäng nhàòm giaím âãún tháúp nháút thåìi gian chiãúm phæång tiãûn cuía mäüt cuäüc truyãön âaî cho. Âäúi våïi neïn dæî liãûu trãn maïy PC, coï nhiãöu thuáût toaïn neïn khaïc nhau âæåüc thiãút kãú cho nhiãöu loaûi dæî liãûu khaïc nhau nhæ: vàn baín, hçnh aính, ám thanh... Trong phaûm vi cuía âäö aïn, ta chè xeït âãún caïc phæång phaïp hình aûnh . II . Lyù thuyeát toång quan veà neùn soá lieäu . II.1. Caùc khaùi nieäm veà neùn soá lieäu . Neïn säú liãûu laì quaï trçnh laìm giaím säú liãûu cáön thiãút âãø biãøu diãùn cuìng mäüt læåüng thäng tin cho træåïc. Caïc kyî thuáût neïn säú liãûu coï thãø âæåüc thæûc hiãûn bàòng phán cæïng chuyãn duûng hoàûc pháön mãöm. Caïc kyî thuáût neïn säú liãûu bàòng pháön cæïng âoìi hoíi phaíi coï caïc pháön cæïng âàûc biãût âæåüc thiãút kãú thêch håüp våïi bàng thäng cäú âënh cuía maûng truyãön säú liãûu. Caïc kyî thuáût neïn säú liãûu bàòng pháön mãöm âæåüc thæûc hiãûn trãn maïy tênh caï nhán (PC) coï thãø duìng neïn file vàn baín, caïc file aính âæåüc nháûp vaìo tæì scaner hoàûc camera vaì caïc file ám thanh. Trong khaïi niãûm vãö neïn, ta cáön phán biãût giæîa säú liãûu vaì thäng tin. Säú liãûu (data) duìng âãø biãøu diãùn vaì truyãön taíi thäng tin (information), cuìng mäüt læåüng thäng tin cho træåïc ta coï thãø biãøu diãùn bàòng caïc læåüng säú liãûu khaïc nhau. Âån vë âo säú liãûu (dung læåüng) laì bit (binary digit). Mäüt bit säú liãûu vãö màût toaïn hoüc âæåüc biãøu diãùn bàòng mäüt chæî säú nhë phán 0 vaì 1, vãö màût âiãûn âæåüc biãøu diãùn bàòng 1 trong 2 mæïc âiãûn aïp qui æåïc... Mäüt bit thäng tin âæåüc âënh nghéa laì læåüng thäng tin. Giaí sæí P laì xaïc suáút cuía mäüt kyï hiãûu, thç læåüng thäng tin chæïa trong kyï hiãûu âoï âæåüc âënh nghéa laì -Log2P bêt, cäng thæïc naìy chênh laì entropy cuía kyï hiãûu. Váûy Entropy laì gç? Trong lénh væûc lyï thuyãút thäng tin sæí duûng thuáût ngæî entropy laì âån vë âo thäng tin âæåüc maî hoïa trong mäüt thäng âiãûp. Entropy cuía mäüt thäng âiãûp caìng cao thç thäng tin noï chæïa âæûng caìng nhiãöu. Entropy cuía toaìn bäü thäng âiãûp laì täøng entropy cuía caïc kyï hiãûu thaình pháön. Entropy phuû thuäüc vaìo xaïc suáút xuáút hiãûn cuía kyï hiãûu, mäüt kyï hiãûu coï xaïc suáút xuáút hiãûn cao thç thäng tin chæïa âæûng trong noï tháúp vaì seî cáön êt bêt hån âãø maî hoïa. II.2 . Caùc kyõ thuaät neùn soá lieäu . II.2.1 . Neùn khoâng toån hao ( Lossless Compression ) . Neïn khäng täøn hao coìn âæåüc goüi laì neïn khäng nhiãùu (Noiseless) hay neïn khäng läùi (Free Error), âaím baío khäng máút maït thäng tin sau quaï trçnh maî hoaï vaì giaíi maî (noï taûo laûi mäüt baín sao chênh xaïc cuía säú liãûu sau quaï trçnh maî hoaï vaì giaíi maî). Kyî thuáût naìy sæí duûng trãn nhæîng nguäön säú liãûu âaím baío âäü chênh xaïc cao khi læu træî hoàûc truyãön âi nhæ caïc cå såí dæî liãûu, caïc baíng tênh âiãûn tæí, caïc vàn baín ...Vç våïi caïc táûp tin naìy, viãûc máút maït duì chè mäüt bit thäng tin laì âiãöu khäng thãø âæåüc. Neïn täøn hao coï caïc phæång phaïp maî hoaï nhæ: phæång phaïp maî hoaï Huffman, maî hoaï säú hoüc, maî hoaï LZW... II.2.2 . Neùn toån hao ( Lossy Compression ) . Neïn täøn hao laì kyî thuáût neïn cháúp nháûn máút maït mäüt læåüng thäng tin nháút âënh âãø âaût âæåüc hiãûu quaí neïn cao. Coï thãø noïi mäüt caïch tæång tæû: Neïn täøn hao= Laìm trån + Neïn khäng täøn hao. Laìm trån laì quaï trçnh thæûc hiãûn mäüt pheïp biãún âäøi naìo âoï (nhæ: biãún âäøi säú liãûu tæì miãön thåìi gian sang miãön táön säú bàòng pheïp biãún âäøi Furiã råìi raûc goüi laì FFT ( Fast Fourier Transform), hoàûc pheïp biãún âäøi Cosin råìi raûc goüi laì DCT (Discrete Cosine Transform)....), tiãúp âoï laì quaï trçnh læåüng tæí hoaï. Säú liãûu caìng âæåüc laìm trån thç máút maït thäng tin caìng nhiãöu vaì tè säú neïn caìng cao. Neïn täøn hao thêch håüp våïi caïc file hçnh aính, ám thanh âæåüc säú hoaï. Háöu hãút caïc kyî thuáût neïn täøn hao âãöu coï thãø âæåüc âiãöu chènh âãø cán bàòng giæîa âäü chênh xaïc vaì hiãûu quaí neïn. Caïc phæång phaïp neïn täøn hao nhæ: phæång phaïp JPEG, phæång phaïp Wavelet, phæång phaïp MPEG... CHÖÔNG II Lòch Söû Neùn AÛnh Lòch söû phaùt trieån . Caùc kyõ thuaät neùn phoå bieán . Neùn thoáng keâ vaø töø ñieån . Neùn coù maát . Ñieàu bieán sai soá . Neùn ñaùp öùng . I. Lòch söû phaùt trieån . Con ngöôøi giao tieáp vôùi maùy tính chuû yeáu thoâng qua maøn hình , vì theá ñoà hoïa chính laø söï quan taâm chính cuûa caùc nhaø thieát keá vaø caùc laäp trình vieân treân theá giôùi . Caùc nhaø laäp trình ñaõ maát raát nhieàu thôøi gian vaø noå löïc ñeå phaùt trieån giao dieän ñoà hoïa ngöôøi duøng ( Graphical User Interface – GUI ) . Haøng trieäu con ngöôøi vaø haøng tæ Dollars ñaõ ñöôïc chi ra ñeå taïo moät cuoäc caùch maïng môùi trong vieäc hieån thò döõ lieäu . Con ngöôøi ñaõ chi moät soá tieàn raát lôùn duøng cho vieäc taïo ra caùc giao dieän ngöôøi duøng GUI nhö laø Microsoft Windows hay Motif - khaû naêng hieån thò caùc hình aûnh ñoà hoïa phöùc taïp nhö laø caùc phöông tieän truyeàn thoáng ( ti vi hay taïp chí ) . Ñieàu naøy ñaõ taïo ra phaàn meàm môùi , ñöôïc thieát keá ñeå taän duïng caùc khaû naêng treân . Caùc chöông trình söû duïng kyõ thuaät ñoà hoïa phöùc taïp thöôøng thaáy laø trong caùc öùng duïng maùy tính nhö : troø chôi , giaùo duïc , internet , thieát keá ñoà hoïa … Caùc chöông trình naøy ñang raát phoå bieán hieän nay . Caùc hình aûnh maø chuùng söû duïng thì tieâu toán raát nhieàu khoaûng troáng treân ñóa , ñieàu maø raát khoù khaên cho caùc coâng ngheä löu tröõ hieän thôøi Trong caùc maùy tính cuûa IBM , boä hieån thò VGA coù leû laø chaáp nhaän ñöôïc cho khaû naêng ñoà hoïa maøu chaát löôïng cao . Boä VGA coù theå hieån thò ñöôïc 256 maøu trong moät baûng 262144 maøu . Ñieàu naøy cho pheùp boä VGA hieån thò ñöôïc caùc hình aûnh coù saéc thaùi lieân tuïc , nhö laø hình chuïp , vôùi moät ñoä trung thöïc chaáp nhaän ñöôïc . Nhöng vaán ñeå ôû ñaây chính laø vieäc löu tröõ caùc hình aûnh naøy trong moät chöông trình . Vôùi moät boä VGA ñöôïc ñeà caäp ôû treân thì moät hình aûnh coù 256 maøu vôùi 200 doøng vaø 320 coät , vôùi moãi moät ñieåm chuùng tieâu toán moät pixel . Ñieàu naøy coù nghóa laø vôùi moät hình aûnh nhö treân , chuùng seõ tieâu toán ít nhaát laø 64KB . Con soá naøy laø khoâng lôùn ñoái vôùi caùc öùng duïng chæ söû duïng khoaûng 100 – 200 hình aûnh cho vieäc truy caäp . Nhöng ñoái vôùi caùc coâng ngheä nhö hieän nay thì vieäc söû duïng töø vaøi ngaøn ñeán vaøi traêm ngaøn laø chuyeän khoâng theå traùnh khoûi . Cho moät ví duï veà boä phaän baùn leû cuûa moät sieâu thò , giaû söû chuùng caàn 10000 hình aûnh ñeå löu tröõ thì ta phaûi maát 640MB ( ñoái vôùi aûnh 200x320 ) , thì ñaây laø moät con soá thaät khoâng hôïp lyù tí naøo . II . Caùc kyõ thuaät neùn phoå bieán . Trong suoát moät thaäp kæ tröôùc , coâng vieäc nghieân cöùu cho muïc ñích löu tröõ caùc hình aûnh ñaõ coù moät soá keát quaû raát khaû quan . Trong nhöõng naêm cuoái 1970 vaøñaàu 1980 , haàu heát caùc phöông phaùp neùn aûnh chæ taäp trung vaøo söû duïng coâng ngheä neùn khoâng maát ( lossless compression ) truyeàn thoáng . Caùc ñònh daïng file neùn phoå bieán söû duïng coâng ngheä naøy laø PCX , GIF , BMP … Chuùng laøm giaûm dung löôïng caùc file goác töø 10% - 90% dung löôïng ban ñaàu . Khi vieäc söû duïng caùc hình aûnh ñoà hoïa taêng leân , caùc ñònh daïng file nhö laø PCX trôû khoâng thoõa ñaùng nöõa . Laøm giaûm ñi moät nöõa kích thöôùc cuûa file laø moät ñieàu ñaùng laøm , nhöng trong khi ñoù nhöng ngöôøi thieát keá vaø ngöôøi söû duïng ñang saøi heát caùc khoaûng troáng treân oå ñóa cuûa hoï moät caùch nhanh choùng bôûi caùc öùng duïng ña phöông tieän ñang laøm chuùng trôû neân khoâng coøn tính khaû thi . II.1 . Caùc phöông phaùp neùn thoáng keâ ( Statistical Compression ) vaø töø ñieån ( Dictionary Compression ) . Caùc chöông trình truyeàn thoáng vaø caùc döõ lieäu treân maùy tính thì ñaùp öùng raát toát vieäc neùn treân neàn taûng lôïi duïng söï thoáng keâ möùc ñoä thay ñoåi trong taàn soá xuaát hieän cuûa caùc kí töï rieâng leû vaø chuoãi caùc kí tö hay moät cuïm kí töï . Heä thoáng treân neàn taûng töø ñieån thaät söï ñöôïc nguïy trang döôùi lôùp voû chöông trình thoáng keâ . Tuy nhieân , coù moät soá caùc kieåu neùn khoâng coù khuynh höôùng neùn toát ñoái vôùi caùc hình aûnh coù saéc maøu lieân tuïc . Vaán ñeà chính ôû ñaây coù moät soá chöông trình baét nguoàn töø söï thaät laø caùc ñieåm aûnh trong caùc aûnh chuïp coù khuynh höôùng traûi roäng ra treân toaøn boä phaïm vi cuûa chuùng . Neáu caùc maøu saéc trong moät hình aûnh ñöôïc ñaùnh daáu nhö laø moät bieåu ñoà thoáng keâ treân cô sôû taàn soá xuaát hieän , thì bieåu ñoà ñoù khoâng coù “nhoïn” ( spiky ) nhö chuùng ta mong muoán neùn thoáng keâ thöïc thi . Thaät söï , treân vieäc vaän haønh laâu daøi , caùc bieåu ñoà veà hình aûnh soáng ñoäng coù khuynh höôùng laø phaúng . Ñieàu naøy coù nghóa laø moãi maõ ñieåm aûnh ñeàu coù cuøng cô hoäi theå hieän nhö baát kyø ñieåm naøo khaùc . Caùc chöông trình neùn treân neàn taûng töø ñieån ñeàu gaëp nhöõng vaán ñeà töông töï . Caùc aûnh treân neàn taûng chuïp ñöôïc queùt leân thì khoâng coù caùc ñaëc tính döõ lieäu chung ñeå taïo ra nhieàu söï xuaát hieän cuûa caùc cuïm ( phrase ) gioáng nhau . Xeùt moät hình aûnh coù caáu truùc ñöôøng ngang nhö beà maët cuûa moät ngoâi nhaø baèng goã , noù coù theå cho ta caùc chuoãi töông töï trong moät soá haøng lieân tieáp . Thaät khoâng may , bôûi vì söï ña daïng cuûa theá giôùi thöïc , caùc ñaëc tính gioáng nhau treân moãi haøng seõ coù khuynh höôùng khaùc nhau ( khoâng ñaùng keå ) ñoái vôùi caùi ban ñaàu . Vöôït ra ngoaøi moät chuoãi hai möôi ñieåm aûnh , moät hoaëc hai ñieåm seõ thay ñoåi bôûi moät böôùc ñôn giaûn töø vieäc queùt aûnh tröôùc vaø sau . Vaø trong khi söï khaùc nhau ñoù laø ñuû nhoû ñeå chuùng trôû neân hoaëc laø khoâng phaùt hieän ñöôïc hoaëc laø khoâng coù nghóa ñoái vôùi maét con ngöôøi . Caùc chuoãi coù söï so khôùp chính xaùc ñoái vôùi phöông thöùc neùn naøy seõ ñöôïc söû duïng . Bôûi vì söï thay ñoåi khoâng ñaùng keå , chieàu daøi cuûa caùc chuoãi so khôùp coù khuynh höôùng trôû neân nhoû ñi . Ñieàu naøy seõ laøm haïn cheá hieäu quaû cuûa vieäc neùn . II.2 . Neùn toån hao ( Lossy compression ) . Cuõng gioáng nhö caùc döõ lieäu aâm thanh , caùc hình aûnh ñoà hoïa coù moät thuaän lôïi treân caùc taäp tin döõ lieäu maùy tính truyeàn thoáng : chuùng coù theå ñöôïc hieäu chænh trong suoát chu trình neùn / giaûi neùn maø khoâng laøm aûnh höôûng ñeán söï caûm nhaän cuûa ngöôøi duøng . Vieäc thay ñoåi thöù yeáu moät caùch chính xaùc cuûa boùng ñieåm aûnh ( shade pixel ) laø ôû ñaây vaø coù theå deã daøng hoaøn thaønh neáu vieäc hieäu chænh ñöôïc laøm moät caùch caån thaän . Bôûi vì caùc aûnh ñoà hoïa treân maùy tính thì thoâng thöôøng ñöôïc queùt leân töø theá giôùi thöïc , chuùng thoâng thöôøng taïo ra moät theå hieän khoâng thöïc söï hoaøn chænh cuûa aûnh chuïp hoaëc cuûa moät soá phöông tieän in khaùc . Chöông trình neùn toån hao khoâng laøm maát ñi söï töï nhieân cô baûn cuûa hình aûnh thì môùi haún laø khaû thi . Ñöa ra phöông phaùp neùn coù maát cho caùc hình aûnh ñoà hoïa laø ñieàu hoaøn toaøn coù theå thöïc hieän ñöôïc , nhöng chuùng ta thöïc thi noù nhö theá naøo ? Caùc nhaø nghieân cöùu ñaõ thöû söû duïng moät vaøi coâng ngheä töông töï vôùi coâng ngheä laøm vieäc treân gioïng noùi , nhö laø maõ hoùa sai soá ( Differential Coding ) vaø maõ hoùa ñaùp öùng ( Adaptive Coding ) , nhöng chuùng ñaõ khoâng nhö mong ñôïi . Lí do chính laø söï khaùc nhau cô baûn giöõa döõ lieäu aâm thanh vaø hình aûnh . Döõ lieäu aâm thanh ñöôïc laáy maãu söû duïng caùc ñònh daïng truyeàn thoáng thì coù ñaëc tröng laëp ñi laëp laïi ( repetitive ) . AÂm thanh , bao goàm caû gioïng noùi , ñöôïc taïo ra töø caùc soùng sine , laëp laïi moãi giaây taïi moãi thôøi ñieåm . Maëc duø doøng vaøo taïi boä DAC treân maùy tính bao goàm haøng taù caùc taàn soá khaùc nhau ñöôïc theâm vaøo vôùi nhau thì soùng sine noùi chung vaãn keát hôïp ñeå taïo ra daïng soùng laëp ( repetitive waveforms ) . Tính laëp laïi töï nhieân cuûa döõ lieäu aâm thanh coù theå duøng cho vieäc neùn . Caùc coâng ngheä nhö laø maõ hoùa ñoaùn tröôùc tuyeán tính ( Linear Predictive Coding ) vaø söï ñieàu bieán maõ xung sai soá ñaùp öùng ( Adaptive Differential Pulse Code Modulation ) ñaõ lôïi duïng ñieàu naøy ñeå maõ hoùa caùc doøng aâm thanh vôùi xaùc xuaát töø 50 – 90 phaàn traêm . Khi söï nghieân cöùu baét ñaàu treân vieäc neùn caùc aûnh ñoà hoïa , caùc aûnh soá hoùa ñaõ ñöôïc aùp duïng vôùi caùc coâng ngheä töông töï vaø ñaõ coù moät vaøi söï thaønh coâng . Khôûi ñaàu , caùc nhaø nghieân cöùu thöïc hieän treân vieäc neùn caùc doøng döõ lieäu ñöôïc löôùi hoùa ( rasterized data ) . Khi caùc hình aûnh ñöôïc soá hoùa , noù seõ hieån thò nhö laø moät chuoãi tuaàn töï caùc ñieåm aûnh . Moät doøng taïi moät thôøi ñieåm ñöôïc hieån thò treân maøn hình seõ laøm vieäc töø traùi sang phaûi vaø töø treân xuoáng döôùi . Vì theá , moät laùt moûng cuûa hình aûnh seõ ñöôïc veõ khi moãi doøng hoaøn thaønh , cho ñeán khi hình aûnh ñöôïc hieån thò ñaày ñuû treân maøn hình . Khi ñöôïc soá hoùa , caùc ñieåm aûnh coù kích thöôùc töø moät ñeán hai möôi boán bit . Caùc maøn hình ñoà hoïa ngaøy nay söû duïng 8 bit ñeå xaùc ñònh moät ñieåm aûnh . II.3 . Söï ñieàu bieán sai soá ( Differential Modulation ) . Söï ñieàu bieán sai soá phuï thuoäc vaøo khaùi nieäm raèng caùc döõ lieäu tín hieäu töông töï coù khuynh höôùng bieán thieân trong caùc maãu trôn mòn ( smooth patterns ) , vôùi caùc böôùc nhaûy caên baûn trong bieân ñoä tín hieäu laø ngoaïi leä , khoâng theo nguyeân taéc . Trong döõ lieäu tín hieäu aâm thanh , ñieàu naøy laø ñuùng mieãn sao tæ leä laáy maãu cuûa tín hieäu laø moät vaøi caùi gì ñoù cao hôn thaønh phaàn taàn soá cöïc ñaïi . Söï ñieàu bieán sai soá cuûa moät tín hieäu aâm thanh lôïi duïng vieäc naøy baèng caùch maõ hoùa moãi maãu tín hieäu nhö laø moät söï khaùc nhau töø chính nhöõng maãu tröôùc ñoù ( predecessor ) . Ví duï nhö moãi maãu aâm thanh laø taùm bit thì moät heä thoáng maõ hoùa sai soá coù theå maõ hoùa söï khaùc nhau giöõa caùc maãu laø boán bit , neùn döõ lieäu ban ñaàu ñöôïc 50% . Nhöõng phaàn maát ñi cho ta thaáy raèng söï khaùc nhau khoâng phaûi luoân luoân ñöôïc maõ hoùa khi söû duïng phöông phaùp sai soá chuaån . Caùc tín hieäu coù theå cao hôn giôùi haïn maõ hoùa hoaëc vieäc maõ hoùa coù theå quaù keùm ñeå ñieàu chænh moät söï khaùc nhau nhoû . Khía caïnh maát ñi naøy cuûa maõ hoùa sai soá coù theå ñöôïc giaùm saùt ñuû toát ñeå maø coù theå ñöa ra moät tín hieäu hoaøn chænh . Söï ñieàu bieán sai soá thì coù nhieàu vaán ñeà hôn ñoái vôùi vieäc neùn caùc döõ lieäu ñoà hoïa . Caùc ñieåm aûnh trong hình coù theå khoâng chaéc chaén phuï thuoäc vaøo söï bieán thieân leân xuoáng trong vieäc taêng ñoä mòn hình aûnh . Caùc ñöôøng phaân chia roõ raøng giöõa caùc thaønh phaàn khaùc nhau cuûa moät hình aûnh chính laø qui taéc . Ñieàu naøy coù nghóa laø moät heä thoáng tin duøng maõ hoùa sai soá thì caàn phaûi ñieàu chænh söï sai leäch caû lôùn laãn nhoû giöõa caùc maãu , giôùi haïn söï taùc ñoäng cuûa noù . Moät soá hình aûnh coù ñaëc tính keùo daøi lieân tuïc cuûa döõ lieäu , nghóa laø caùc ñieåm aûnh coù moät ít hoaëc laø khoâng coù söï khaùc nhau , vaø vì theá vieäc neùn ñöôïc thöïc hieän raát toát . Nhöng ngöôïc laïi , moät soá nôi trong aûnh laïi coù söï thay ñoåi saéc thaùi ñoät ngoät , vaø vieäc neùn seõ khoâng theå toát ñöôïc ôû nhöõng nôi ñoù . Noùi chung , giaûi thuaät maõ hoùa sai soá caùc hình aûnh ñoà hoïa thì döôøng nhö khoâng coù taïo ra moät coâng ngheä neùn toát hôn giaûi thuaät neùn khoâng toån hao toát nhaát . Noù khoâng laøm phaùt sinh ra moät lôïi ích to lôùn caàn thieát naøo trong söï phaùt trieån coâng ngheä neùn . II.4 . Maõ hoùa ñaùp öùng ( Adaptive Coding ) . Maõ hoùa ñaùp öùng ( thöôøng ñöôïc söû duïng chung vôùi maõ hoùa sai soá ) thì döïa vaøo vieäc tieân ñoaùn tröôùc caùc thoâng tin veà saéc thaùi caùc ñieåm aûnh treân neàn taûng caùc ñeåm aûnh ñöôïc thaáy ôû tröôùc ñoù . Cho moät ví duï , neáu möôøi ñieåm aûnh cuoái cuøng trong moät aûnh saéc xaùm ( gray scale ) thì taát caû giaù trò ñieåm aûnh naèm trong khoaûng 45 – 50 , moät heä thoáng neùn ñaùp öùng coù theå döï ñoaùn caùc ñieåm aûnh keá tieáp seõ cuøng naèm trong moät vuøng vôùi xaùc xuaát raát cao . Moät löôïc ñoà maõ hoùa döïa treân neàn taûng entropy , nhö maõ hoùa Huffman hay Arithmetic , coù theå gaùn xaùc suaát xuaát hieän vaøo caùc maõ môùi . Giaû söû raèng phöông phaùp döï ñoaùn cho pheùp chuùng ta taïo ra moät söï tieân ñoaùn veà xaùc suaát xuaát hieän cuûa caùc pixel , chuùng ta seõ coù : Previous Row -1,-1 -1,0 -1,1 Current Row 0,-1 0,0 Target Pixel A B C D Hình 1 . Adaptive coding Haàu heát caùc löôïc ñoà ñaùp öùng döïa vaøo vieäc söû duïng moät vaøi caùc ñieåm aûnh chung quanh nhö laø moät phaàn cuûa söï tính toaùn cho xaùc xuaát xuaát hieän cuûa upcomming pixel . Trong hình treân , moät ñieåm aûnh ñöôïc maõ hoùa ñöôïc theå hieän taïi vò trí (0,0) . Coøn caùc ñieåm aûnh khaùc nhö A, B ,C ,D ñöôïc duøng moät caùch bình thöôøng trong vieäc tính toaùn xaùc suaát xuaát hieän . Söï döï ñoaùn caùc giaù trò upcoming cuûa pixel ñích ( target ) coù theå ñöôïc laøm treân cô baûn moät vaøi phöông trình döï ñoaùn : A B C (A + C) / 2 (A + D) / 2 (A + ( C + D ) / 2 ) / 2 (A + ( C – B )) (A + (( D – B) / 2)) Hình 2 . Söï döï ñoaùn ñieåm aûnh . Moät soá coâng ngheä söû duïng caùc döõ lieäu treân ñeå tính toaùn haàu heát giaù trò coù theå coù cuûa ñieåm aûnh ñích , vaø sau ñoù chuùng hieäu chænh löôïc ñoà maõ hoùa . Trong khi caùc vieäc tính toaùn ñoù cho ra keát quaû khaû quan thì moät laàn nöõa noù ñöôïc xem nhö laø moät kyõ thuaät khoâng hieäu quaû trong coâng ngheä neùn aûnh . CHÖÔNG III Neùn AÛnh Phaân Ñoaïn _Fractal Image Compression_ Lòch söõ coâng ngheä neùn aûnh Fractal . Söï phaân ñoaïn . IFS – Iterated Function Systems . IFS laø gì ? IFS cô baûn . Neùn aûnh vôùi IFS . Neùn aûnh vôùi PIFS . I . Lòch söû coâng ngheä neùn aûnh fractal . Thuaät töø Fractal ñaàu tieân ñöôïc söû duïng bôûi Benoit Mandelbrot ñeå chæ ñònh nhöõng ñoái töôïng ... OÂng ñaõ thöïc hieän moät ví duï ñöôïc moâ taû bôûi phöông trình cho thaáy moät söï ña daïng voâ haïn cuûa caùc chi tieát ñoù . Ñieàu naøy coù theå ñöôïc xem nhö la moät daïng cuûa vieäc neùn : phöông trình töï noù coù theå ñöôïc moâ taû vôùi moät vaøi caùc bit thoâng tin hoaëc ñöôïc theå hieän trong moät chöông trình ngaén , nhöng hình aûnh keát quaû seõ caàn moät löôïng voâ haïn caùc bit ñeå theå hieän nhö laø moät taäp caùc ñieåm aûnh . Chöông trình FracInt phoå bieán coù theå phaùt sinh raát nhieàu nhöõng hình aûnh tinh teá töø nhöõng coâng thöùc ñôn giaûn ( one-line formulars ) . Michael Barnsley vaø baïn ñoàng nghieäp cuûa oâng ta ñaõ nhaän thaáy ñöôïc tieàm naêng cuûa phöông thöùc Fractal cho vieäc neùn aûnh . Barnsley ñaõ phaùt trieån hoïc thuyeát Heä Thoáng Chöùc Naêng Ñöôïc Laëp Laïi ( Iterated Function Systems ) , vieát taét laø IFS , ñaàu tieân ñöôïc giôùi thieäu bôûi J.Hutchinson naêm 1981 . Sau khi phaùt haønh cuoán saùch “Fractals Everywhere” naêm 1988 thì neùn Fractal trôû neân laø moät chuû ñeà raát thôøi thöôïng . Ñieàu haáp daãn cuûa coâng ngheä naøy laø tæ leä neùn haáp daãn cuûa noù , taêng töø 10000 leân 1 . Thaät khoâng may , tæ leä neùn ñoù coù theå ñaït ñöôïc chæ vôùi nhöõng hình aûnh ñöôïc caáu truùc ñaëc bieät vaø chæ vôùi söï trôï giuùp ñaùng keå cuûa ngöôøi höôùng daãn tieán trình neùn . Quaù trình naøy ñöôïc bieát nhö laø “Graduate Student Algorithm” ( taïm dòch laø “ Giaûi Thuaät Sinh Vieân Toát Nghieäp “ ) . Nghóa laø cho moät sinh vieân toát nghieäp vaøo moät vaên phoøng vaø traïm laøm vieäc ñoà hoïa , khoùa cöûa laïi , chôø cho ñeán khi ngöôøi sinh vieân ñoù tìm ra ñöôïc moät IFS toát nhaát cho hình aûnh , vaø môû cöûa ra . Tieán trình neùn naøy khoâng theå hoaøn thaønh moät caùch töï ñoäng , thaäm chí vôùi sieâu maùy tính . Vì theá , vieäc neùn döïa treân neàn taûng IFS hoùa ra khoâng thöïc teá . Naêm 1988 , oâng Arnaud Jacquin , moät hoïc troø cuûa Barnsley ñaõ taïo ra moät ñieåm moác cuûa vieäc neùn . Thay cho vieäc tìm ra moät IFS cho moät hình aûnh hoaøn chænh , oâng ñaõ coù nhöõng yù töôûng veà söï phaân chia hình aûnh thaønh nhöõng vuøng ( range ) khoâng choàng laáp vaø tìm ra moät IFS rieâng cho moãi aûnh phaân chia ñoù . Ñieàu naøy seõ bieán vaán ñeà phöùc taïp treân thaønh moät taùc vuï coù theå quaûn lyù ñöôïc , ñieàu maø coù theå ñöôïc laøm moät caùch töï ñoäng . Trong luaän vaên tieán só , oâng ta ñaõ phaùt trieån lyù thuyeát Heä Thoáng Chöùc Naêng Laëp Laïi Ñöôïc Phaân Chia ( Partitioned Iterated Function Systems ) , vieát taét laø PIFS , vaø thöïc hieän moät phieân baûn veà giaûi thuaät cuûa oâng ta trong phaàm meàm . Naêm 1991 , Barnsley vaø Sloan ñaït ñöôïc baèng saùng cheá Myõ veà coâng ngheä naøy . Coâng ty cuûa hoï , Iterated Systems , thì baùn nhöõng saûn phaåm phaàn meàm vaø phaàn cöùng söû duïng noù , nhöng khoâng coù tung ra chi tieát veà coâng ngheä naøy . Ñaëc bieät , FIF ( Fractal Image Format) ñöôïc söû duïng bôûi caùc saûn phaåm cuûa Iterated Systems thì caøng khoâng ñöôïc moâ taû roäng raõi . Chính vì ñieàu naøy maø neùn aûnh Fractal khoâng ñöôïc söû duïng thöïc teá nhieàu nhö laø caùc coâng ngheä khaùc . Tuy nhieân , neùn Fractal vaãn laø chuû ñeà cuûa vieäc nghieân cöùu , vaø noù ñaõ thaät söï chöùng minh ñöôïc tính öu vieät nhaát cho caùc öùng duïng , nôi maø tæ leä neùn cao raát ñöôïc quan taâm . PIFS cuõng coù teân laø Local Iterated Function Systems ( LIFS – taïm dòch laø Heä Thoáng Chöùc Naêng Ñöôïc Laëp Laïi Cuïc Boä ) , vaø Barnsley laïi coøn söû duïng caû thuaät töø “Fractal Tranform” , taát caû chuùng ñeàu noùi ñeán cuøng moät coâng ngheä . II . Söï phaân ñoaïn . Baát cöù moät ñoái töôïng hình hoc bình thöôøng naøo cuõng ñeàu coù lieân quan ñeán scale . Cho moät ví duï , moät hình troøn khi quan saùt noù baèng vieäc söû duïng moät cöûa soå lôùn hôn laø toaøn boä hình troøn ñoù , khi nhìn thoâng qua cöûa soå naøy , baïn seõ thaáy noù laø moät hình troøn . Tieáp tuïc , khi quan saùt noù baèng moät cöûa soå nhoû hôn chu vi cuûa noù thì ta seõ thaáy noù nhö laø moät voøng cung ñöôøng troøn . Vaø khi quan saùt noù baèng moät cöûa soå raát nhoû , chuùng ta seõ töôûng noù laø bao goàm raát nhieàu caùc ñöôøng nhoû xíu . Hình 3. Quan saùt hình troøn taïi caùc möùc ( scale ) khaùc nhau . Hình 4 . Tam giaùc Sierpinski . Nhöng ñoái vôùi moät ñoái töôïng Fractal , coù khoâng moät möùc quan saùt laø lôùn hay nhoû thì hình daïng vaø nhöõng gì phöùc taïp trong noù ñeàu khoâng thay ñoåi , khoâng coù caùch naøo ñeå chia caét noù vaøo trong moät boä tích hôïp caùc ñoái töôïng con , bôûi vì caùc thaønh phaàn treân noù coù tính töông töï nhau treân toaøn boä khung hình vaø thaät phöùc taïp ( xem hình tam giaùc Sierpinski ) . Baát cöù phaàn naøo , khi phoùng lôùn leân , ñeàu trôû thaønh moät tam giaùc Sierpinski . Tính töï gioáng nhau ( seft-similarity ) ñoù laø moät ñaëc tính heát söùc quan troïng cuûa kyõ thuaät neùn aûnh Fractal vaø laø moät ñaëc tính noåi baäc ñeå nhaän daïng kyõ thuaät naøy trong caùc kyõ thuaät neùn khaùc . Trong quaù trình xöû lyù hình aûnh , caùc öùng duïng Fractal taäp trung vaøo hai phaàn chính : 1 . AÙp duïng daáu hieäu vaø chieàu ( khoâng gian ) nhö laø moät ñaëc tröng vaøo trong phaân ñoaïn aûnh , phaân tích boá cuïc , … 2 . AÙp duïng IFS ( Iterated Function Systems ) vaøo trong quaù trình neùn aûnh . Heä thoáng maõ hoùa vaø giaûi maõ Fractal ñöôïc theå hieän trong sô ñoà beân dö._.ôùi . Taïi giai ñoaïn maõ hoùa , cho moãi khoái range , moät chuyeån ñoåi thu nhoû vaø khoái domain ñuôïc tìm thaáy , sau ñoù söï chuyeån ñoåi thu nhoû vaø vò trí cuûa caùc domain seõ ñöôïc truyeàn ñi ñeán ñaàu ra thoâng qua moät keânh . ÔÛ giai ñoaïn giaûi maõ , hình aûnh ñöôïc taùi taïo laïi söû duïng caùc chuyeån ñoåi vaø vò trí caùc khoái domain ôû treân baèng vieäc laëp nhieàu laàn coâng vieäc naøy Encoding system … Channel… Decoding system Hình 5 . Sô ñoà maõ hoùa vaø giaûi maõ . III . Iterated Function System ( IFS ) laø gì ? Chuùng ta ñieàu thaáy raèng taát caû caùc hình aûnh phöùc taïp coù theå thu ñöôïc töø nhöõng coâng thöùc ñôn giaûn . Vieäc ñöa ra moät coâng thöùc seõ deã daøng daãn xuaát ra moät hình aûnh töông öùng . Nhöng neáu ñi theo moät höôùng ngöôïc laïi , töø aûnh ñeán coâng thöùc , thì ñieàu naøy seõ laø khaû thi hôn , noù seõ cho moät tæ leä neùn tuyeät vôøi . Thay cho vieäc theå hieän moät aûnh nhö laø moät trình töï caùc giaù trò ñieåm aûnh , hình aûnh coù theå ñöôïc khôûi taïo laïi töø moät coâng thöùc , ñieàu maø seõ toán raát ít dung löôïng löu tröõ . Ta haõy thöû xeùt moät ví duï sau : Giaû söõ raèng ñeå theå hieän moät caùi ñóa troøn maøu ñen treân neàn traéng , ta phaûi lieät keâ taát caû caùc ñieåm aûnh treân caùi ñóa ñoù vôùi hai chieàu ngang vaø doïc , thì ngöôïc laïi , ta coù theå ñöa ra moät phöông trình cho aûnh naøy , chæ ñònh noù nhö laø moät taäp caùc ñieåm (x,y) : (x – a)2 + (y – b)2 < r2 ÔÛ ñaây , r laø baùn kính cuûa caùi ñóa vaø ( a,b ) laø taâm cuûa noù . Phöông trình naøy thì quaù ñuû ñeå khôûi taïo laïi hình aûnh chieác ñóa . Hôn nöõa , hình aûnh naøy coù theå ñöôïc khôûi taïo laïi taïi baát kyø ñoä phaân giaûi naøo ( maø ñieàu naøy laø khoâng theå khi ta theå hieän chuùng baèng taäp caùc ñieåm aûnh ) . Coù moät söï khaùc nhau töông töï giöõa caùc font kí töï coù theå co giaõn vaø caùc font coá ñònh ( ñöôïc taïo ra töø caùc ñieåm aûnh ). Nhöng caùc hình aûnh trong theá giôùi thöïc thì khoâng phaûi luùc naøo cuõng ñöôïc theå hieän nhö moät phöông trình ñôn giaûn . Thaät khoù ñeå tìm ra moät coâng thöùc moâ taû chính xaùc hình aûnh ñoù . YÙ töôûng cho ñieàu naøy laø lôïi duïng tính töï gioáng nhau ( seft-similarity ) trong moät hình aûnh ñeå tìm ra söï theå hieän gaàn ñuùng nhö laø moät phaân ñoaïn ( caùi maø seõ phoâ baøy ra tính töï gioáng nhau ôû moãi möùc khaùc nhau ) . Thay cho vieäc ñöa ra moät phöông trình roõ raøng ñöôïc thoõa maõn bôûi taát caû caùc ñieåm cuûa hình aûnh , thì Fractal ñöôïc ñònh nghóa nhö laø moät giaûi phaùp ñieåm coá ñònh ( fixed-point ) cuûa IFS . IV . Thuaät toaùn IFS cô baûn . Moät aùnh xaï töø moät taäp vaøo chính noù thì ñöôïc goïi laø co laïi ( contractive ) neáu noù laøm giaûm khoaûng caùch : khoaûng caùch giöõa f(x) vaø f(y) thì nhoû hôn khoaûng caùch giöõa 2 ñieåm x vaø y . Ví duï nhö haøm f(x) = x/2 ñöôïc ñònh nghóa treân taäp caùc soá thöïc laø co laïi ñöôïc . Bieåu dieãn ñònh lyù aùnh xaï thu nhoû ( Contractive Mapping ) moät caùch ngaén goïn , raèng aùnh xaï co laïi coù moät ñieåm ñöôïc coá ñònh duy nhaát , nghóa laø giaù trò x thì töông ñöông vôùi f(x) = x . Hôn nöõa , ñieåm ñöôïc coá ñònh coù theå thu ñöôïc bôûi vieäc baét ñaàu töø baát kyø ñieåm x0 naøo vaø cöù vieäc tính theo trình töï : x1 = f(x0) x2 = f(x1) = f( f(x0) ) vv… Trình töï treân seõ hoäi tuï veà moät ñieåm duy nhaát . Cho moät ví duï, baét ñaàu vôùi giaù trò x0 = 1 vaø aùp duïng cho haøm f(x) = x/2 , chuùng ta seõ thu ñöôïc keát quaû laø 1 , 1/2, 1/4 , 1/8, … vaø cuoái cuøng chuùng seõ tieán veà 0 . Ví duï treân ñöa ra moät taäp caùc soá thöïc IR nhöng ñònh lyù aùnh xaï hoäi tuï cuõng aùp duïng cho caùc chieàu khoâng gian khaùc , ôû ñaây laø hình aûnh 2 chieàu . Moät IFS bao goàm taäp höõu haïn caùc aùnh xaï hoäi tuï w1 … wn treân taäp IR2 . Moät IFS coù theå ñöôïc aùp duïng cho aûnh traéng ñen nhö sau . Moãi ñieåm x ( ñen ) cuûa aûnh ñöôïc aùnh xaï thaønh N ñieåm w1(x)… wN(x) . Hoäi cuûa taát caû nhöõng ñieåm keát quaû thì taïo ra moät hình aûnh traéng ñen khaùc . Vì vaäy , IFS seõ chuyeån ñoåi moät aûnh naøy sang moät aûnh khaùc . IFS thì töï noù laø moät aùnh xaï hoäi tuï . Vaø vaäy noù coù moät ñieåm coá ñònh duy nhaát ( unique fixed point ) beân trong taäp taát caû aûnh ñen traéng . Vì theá , baèng vieäc baét ñaàu töø moät aûnh tuøy yù vaø aùp duïng laëp laïi IFS thì tieán trình seõ hoäi tuï thaønh moät aûnh duy nhaát , caùi maø chæ phuï thuoäc vaøo IFS chöù khoâng coøn phuï thuoäc vaøo hình aûnh ban ñaàu . Vaäy thöïc chaát vieäc giaûi neùn Fractal laø nhö theá naøo? Boä giaûi neùn chæ caàn bieát moâ taû cuûa IFS vaø nhö vaäy laø coù theå taùi taïo hình aûnh töø ñoù . Phöông phaùp naøy laøm vieäc baát chaáp daïng chính xaùc cuûa IFS , mieãn laø noù hoäi tuï . IFS coù theå ñöôïc ví nhö laø moät boä maùy sao cheùp ñaët bieät ; Noù taïo ra N baûn sao thu nhoû cuûa aûnh goác , vaø daùn chuùng laïi vôùi nhau . Moãi baûn sao ñöôïc laøm giaûm ñi laø vì moãi wi laø moät hoäi tuï . Baèng vieäc laáy ñaàu ra vaø cho laïi vaøo ñaàu vaøo thì hình aûnh ñöôïc phaùt sinh taïi moãi böôùc ngaøy caøng gioáng vôùi aûnh ban ñaàu vaø quaù trình seõ hoäi tuï thaønh moät aûnh ñieåm coá ñònh duy nhaát , cuõng ñöôïc goïi laø attractor cuûa IFS . Hình aûnh keát quaû laø moät Fractal , bôûi vì noù chöùa ñöïng caùc baûn sao thu nhoû cuûa chính noù taïi taát caû caùc möùc . Ta seõ thaáy chi tieát hôn neáu chuùng ta phoùng to moät phaàn cuûa aûnh leân . Vì tính chaát töï gioáng nhau ( Seft – Similarity ) naøy , aûnh ñöôïc neùn söû duïng IFS thì xöùng ñaùng vôùi teân goïi laø neùn aûnh Fractal ( Fractal Image Compression ) . Treân ñaây , chuùng ta chæ ñeà caäp ñeán hình aûnh ñen traéng ( gray scale ) nhöng noù cuõng coù theå ñöôïc aùp duïng cho caùc aûnh maøu . Vaán ñeà naøy chuùng ta seõ thaûo luaän ôû phaàn sau . V . Neùn aûnh vôùi IFS . Moät IFS cho moät söï xaáp xæ toát cuûa moät hình aûnh I neáu ñieåm coá ñònh cuûa IFS laø moät aûnh gaàn töông ñoàng vôùi I . Muïc ñích laø ñeå tìm moät taäp caùc aùnh xaï hoäi tuï w1 … wN ñeå hoäi vôùi W cuûa taát caû caùc aùnh xaï coù ñieåm coá ñònh gaàn vôùi I . Ñieàu naøy thì thaät khoâng khaû thi bôûi vieäc ta phaûi thöû vaøi aùnh xaï , tính toaùn caùc ñieåm coá ñònh keát quaû , so saùnh noù vôùi I vaø baét ñaàu laïi vôùi nhöõng aùnh xaï khaùc cho ñeán khi moät caùi hôïp nhaát ñöôïc tìm thaáy . Thay vaøo ñoù , chuùng ta seõ thöû tìm ra moät aùnh xaï hoäi tuï W sao cho W(I) thì gaàn gioáng vôùi I . Ñònh lyù Collage cuûa Barnsley noùi raèng neáu W(I) laø ñuû gaàn vôùi I thì ñieåm coá ñònh W∞(1) = W(W(W … W(1) … )) cuõng gaàn vôùi I . AÛnh W(I) thì bao goàm vieäc caét daùn ( hoäi laïi ) cuûa taát caû caùc aûnh thu nhoû Wj(I) . Vôùi söï giuùp ñôõ cuûa ñònh lyù Collage , vaán ñeà treân coù theå ñöôïc baét ñaàu laïi nhö laø vieäc tìm kieám moät ngheä thuaät caét daùn toát cho aûnh . Ñaây laø nôi maø söï khoù khaên thöïc söï baét ñaàu . Noùi chung laø khoâng khaû thi ñeå tìm ra moät ngheä thuaät caét daùn toát moät caùch töï ñoäng . Moät ngöôøi phaûi höôùng daãn tieán trình neùn bôûi vieäc caét hình aûnh ban ñaàu thaønh töøng phaàn ñeå moãi phaàn troâng gioáng nhö laø moät phieân baûn thu nhoû cuûa toaøn boä hình aûnh , vaø hoäi taát caû caùc phaàn ñoù laïi . Ví duï nhö moät ngöôøi seõ quyeát ñònh laø moät nhaùnh cuûa caây coù theå ñöôïc xem laø moät phieân baûn thu nhoû cuûa toaøn boä caây ( chuùng coù theå bò meùo moù ) . Moãi laàn caùc phaàn ñöôïc xaùc ñònh, maùy tính coù theå daãn xuaát ra nhöõng aùnh xaï vaø vì theá ta coù moät IFS cho aûnh naøy . Coù raát nhieàu söï linh hoaït trong vieäc choïn löïa caùc aùnh xaï , mieãn sao chuùng laø hoäi tuï , vaø nhöõng haøm Affine thì luoân ñöôïc söû duïng ôû ñaây . Trong khoâng gian moät chieàu , haøm affine coù daïng nhö sau : ƒ(x) = a*x + b ÔÛ ñaây , a vaø b laø haèng soá . Trong khoâng gian 2 chieàu , hình aûnh cuûa moät ñieåm X coù toïa ñoä ( x,y) laø : ƒ(X) = A*X + B Vaø ôû ñaây , A laø ma traän 2 chieàu vaø B laø moät vector haèng soá . Ma traän A xaùc ñònh vieäc quay , ñoä nghieâng , vaø möùc ( scale ) cho aûnh , vector B thì xaùc ñònh söï bieán ñoåi . Ñieàu kieän coù tính hoäi tuï treân ƒ coù theå ñöôïc bieåu thò nhö ñieàu kieän treân heä soá cuûa ma traän A : heä soá scale phaûi nhoû hôn 1 . Sau khi taát caû söï chuyeån ñoåi affine ñaõ ñöôïc choïn , IFS coù theå ñöôïc theå hieän laïi ôû daïng thu goïn bôûi vieäc maõ hoùa caùc heä soá cuûa taát caû caùc söï bieán ñoåi . Neáu moät caùch caét daùn toát ñöôïc tìm thaáy , thì toång soá löôïng caùc chuyeån ñoåi affine laø nhoû hôn raát nhieàu toång soá löôïng caùc pixel trong aûnh , vì theá vieäc maõ hoùa caùc heä soá ñoøi hoûi ít bit hôn nhieàu so vôùi vieäc lieät keâ taát caû caùc giaù trò pixel . Ñieàu naøy giaûi thích taïi sao vieäc maõ hoùa aûnh söû duïng IFS laø moät daïng cuûa neùn döõ lieäu . Vieäc neùn laø toån hao bôûi vì vieäc duøng IFS cho ta hình aûnh saéc neùt nhöng khoâng baèng vôùi aûnh goác . Caùi khoù khaên chính cuûa tieán trình neùn laø tìm ra beân trong aûnh nhöõng phieân baûn thu nhoû cuûa toaøn boä aûnh . Hình aûnh trong theá giôùi thöïc thöôøng chöùa nhieàu caùi töông töï vôùi noù , nhöng chæ ôû giöõa nhöõng phaàn ñöôïc choïn cuûa aûnh . Böôùc ñoät phaù ôû ñaây laø: vôùi moãi phaàn ñöôïc chia trong aûnh goác , tìm moät IFS cuïc boä cho moãi phaàn ñoù . Vôùi phöông phaùp môùi naøy thì cuoái cuøng chuùng cuõng trôû neân khaû thi trong vieäc thöïc hieän töï ñoäng tieán trình neùn vaø hôn theá nöõa laø ñeå thöïc hieän noù trong moät khoaûng thôøi gian cho pheùp . VI . Neùn aûnh vôùi Partitoned Iterated Function Systems – PIFS . Nhö ñaõ noùi ôû phaàn tröôùc , neùn laø moät coâng vieäc laøm giaûm ñi söï dö thöøa döõ lieäu . ÔÛ ñaây cuõng töông töï nhö theá , caùc giaûi thuaät neùn aûnh cuõng nhö laø löôïng töû hoùa vector ( Vector Quantization ) vaø neùn Fractal ( Fractal Compression ) coù söï tham gia cuûa PIFS baèng vieäc laøm giaûm söï dö thöøa cuûa hình aûnh ñaàu vaøo . Nhöõng phöông phaùp neùn caùc file vaên baûn thì laø khoâng maát döõ lieäu ( lossless ) , ngöôïc laïi phöông phaùp neùn aûnh laø chæ tìm moät söï xaáp sæ vaø vì theá chuùng luoân coù maát . Löôïng töû hoùa vector ( Vector Quantization ) söû duïng töø ñieån ( hoaëc laø saùch maõ – codebook ) chöùa caùc maãu pixel . Hình aûnh vaøo ñöôïc phaân chia thaønh caùc khoái pixel nhoû , vaø moãi khoái ñöôïc maõ hoùa nhö moät maãu töông öùng vôùi haàu heát caùc maãu coù saün trong töø ñieån . Thöôøng thì moät khoái coù cuøng kích thöôùc vôùi caùc maãu töï ñieån nhöng taát caû caùc khoái khoâng caàn phaûi nhö vaäy , chuùng coù theå coù kích thöôùc khaùc nhau . Boä giaûi maõ phaûi coù phieân baûn cuûa töø ñieån vaø nhö vaäy chuùng coù theå deã daøng khôûi taïo laïi moät aûnh xaáp xæ vôùi hình aûnh ban ñaàu baèng vieäc keát hôïp laïi caùc maãu töø ñieån ñöôïc chæ ñònh bôûi boä maõ hoùa . Neùn Fractal vôùi PIFS thì töông töï vôùi löôïng töû hoùa vector , nhöng trong tröôøng hôïp naøy khoâng coù töï ñieån beân ngoaøi . Hình aûnh ñaàu vaøo töông taùc vôùi töø ñieån cuûa chính noù . Boä giaûi maõ khoâng coù hình aûnh ban ñaàu , nhöng noù coù theå ñöôïc taùi taïo baèng vieäc laëp laïi chu trình PIFS . Vì töø ñieån chæ laø moät cuoán saùch maõ aûo ( virtual codebook ) . Boä neùn tröôùc heát phaân chia hình aûnh ban ñaàu thaønh moät taäp caùc range khoâng choàng laáp ( range – taïm dòch laø vuøng ) . Caùc range naøy thoâng thöôøng laø nhöõng hình vuoâng hay hình chöõ nhaät , nhöng noù cuõng raát toát vôùi caùc hình laø tam giaùc . Cho moãi range , boä neùn seõ tìm moät phaàn cuûa hình aûnh ban ñaàu , ñöôïc goïi laø domain ( domain – taïm dòch laø mieàn ) , caùi maø töông töï vôùi range . Moät domain ñoùng vai troø laø moät maãu pixel trong vieäc löôïng töû hoùa , nhöng ôû ñaây noù phaûi lôùn hôn range ñeå chaéc raèng vieäc aùnh xaï töø domain sang range laø söï hoäi tuï trong caùc chieàu khoâng gian . Noùi chung , boä neùn phaûi tìm kieám caùc domain , caùi maø lôùn hôn gaáp hai laàn range ( nhöng tæ leä khaùc laø coù theå ) . Traùi vôùi range , domain coù theå choàng laáp ñöôïc . Hình 6. AÛnh “sunset” vôùi caùc range vaø domain ñöôïc tìm thaáy . Hình cho thaáy hai range vaø hai domain töông öùng . Chuùng ñöôïc choïn baèng giaûi thuaät neùn ñöôïc laøm noåi baäc leân . Giaûi thuaät ñaõ tìm thaáy söï töông töï ( similarity ) giöõa hai phaàn khoâng lieân quan vôùi nhau trong aûnh : moät range naèm ôû treân trôøi beân phaûi vaø moät domain naèm keà beân , lôùn gaáp 2 laàn range , ôû beân traùi . Giaûi thuaät coøn tìm thaáy moät range naèm trong domain , ôû döôùi ñaùm maây . Trong tröôøng hôïp naøy thì range vaø domain thì choàng laáp leân nhau . Söï töông töï naøy thì khaù laø phoå bieán trong aûnh theá giôùi thöïc vaø neùn fractal ñaõ lôïi duïng ñieàu naøy . Ñeå öôùc ñònh söï gioáng nhau giöõa moät domain D vaø moät range R , boä neùn phaûi tìm moät aùnh xaï toát nhaát coù theå töø domain sang range , ñeå cho aûnh w(D) caøng gaàn vôùi aûnh R thì caøng toát. Khi chuùng ta ñaõ ñaït ñöôïc böôùc treân thì nhöõng chuyeån ñoåi affine laø thuaän lôïi cho muïc ñích naøy , nhöng nhöõng chuyeån ñoåi khoâng tuyeán tính cuõng coù theå ñöôïc söû duïng mieãn sao chuùng laø hoäi tuï . Nhöõng söï chuyeån ñoåi hai chieàu ñaõ ñöôïc duøng ñeå chuyeån ñoåi hình aûnh ñen traéng . Ba chieàu cho hình aûnh xaùm , trong ñoù hai cho caùc chieàu khoâng gian vaø moät cho thaønh phaàn ñoä choùi . Khi ñoù moät aùnh xaï affine ñöôïc keát hôïp töø moät thaønh phaàn hình hoïc ( thaønh phaàn aùnh xaï domain sang range) vaø moät thaønh phaàn ñoä choùi (thaønh phaàn thay ñoåi caùc giaù trò maät ñoä pixel ) . Hoaøn toaøn ñuùng nhö vaäy , moät ñieåm (x,y) vôùi ñoä choùi z töông öùng vôùi moät domain Di ñöôïc aùnh xaï thaønh : Caùc haèng soá vaø chæ ñònh thaønh phaàn hình hoïc , haèng soá ci vaø bi chæ ñònh thaønh phaàn ñoä choùi . ci theå hieän ñoä töông phaûn vaø nhoû hôn moät ñeå chaéc raèng söï aùnh xaï laø hoäi tuï trong chieàu ñoä choùi . bi theå hieän thaønh phaàn ñoä saùng ñöôïc söû duïng sau khi ñoä töông phaûn ñöôïc laøm giaûm . Trong thöïc teá , boä neùn khoâng theå xaùc ñònh roõ raøng haèng soá vaø cho moãi domain . Chuùng ngaàm ñöôïc xaùc ñònh bôûi kích thöôùc töông ñoái, phöông höôùng vaø vò trí cuûa domain ñoái vôùi range . Trong tröôøng hôïp ñaëc bieät , neáu boä neùn chæ tìm kieám nhöõng domain chính xaùc lôùn gaáp 2 laàn range thì nhaân toá möùc ( scaling factor) thoâng thöôøng ñöôïc daãn xuaát töø giaù trò , seõ thöïc söï ñöôïc söû duïng vaø baèng 0.5 . Töông töï , neáu caùc domain vaø range ñöôïc giôùi haïn laø caùc hình vuoâng, coù 8 söï ñònh höôùng coù theå coù cuûa domain gaén lieàn vôùi hình vuoâng : quay 4 vaø ñoái xöùng 4 . Vì theá 3 bit laø ñuû ñeå maõ hoùa höôùng. Cuoái cuøng haèng soá chuyeån ñoåi ñöôïc xaùc ñònh bôûi vò trí goùc treân beân traùi cuûa domain . Quaù trình ñôn giaûn hoùa ñöôïc moâ taû ôû treân döôøng nhö quaù phöùc taïp nhöng chuùng thöïc söï caàn thieát ñeå laøm giaûm ñi söï phöùc taïp veà nhöõng tæ leä coù theå deã daøng quaûn lyù ñöôïc . Theo lyù thuyeát , caùc range vaø domain coù theå coù hình khoai taây thay cho hình vuoâng , caùc aùnh xaï hoäi tuï coù theå khoâng coù tuyeán tính thay cho caùc aùnh xaï affine , … Tuy nhieân , khoâng gian tìm kieám seõ trôû neân quaù lôùn vaø keát quaû laø vieäc neùn trôû neân cöïc kyø chaäm cho vieäc söû duïng thöïc teá . Nhöng thaäm chí vôùi caùc aùnh xaï affine ñôn giaûn , vieäc tìm kieám domain toái öu cho moät range cho tröôùc coù theå vaãn laø moät haønh ñoäng xa vôøi . Vôùi moät range R cho tröôùc , boä neùn phaûi kieåm tra soá löôïng caùc domain coù theå . Vôùi moãi domain D , boä neùn phaûi tìm ra moät aùnh xaï affine toái öu töø D sang R . Khoaûng caùch nhoû nhaát giöõa aûnh R vaø aûnh w(D) chính laø aùnh xaï toát nhaát w , nôi maø khoaûng caùch ñöôïc laáy trong chieàu ñoä choùi , chöù khoâng phaûi trong caùc chieàu khoâng gian . Nhö vaäy , moät khoaûng caùch coù theå ñöôïc ñònh nghóa trong nhieàu caùch , nhöng ñeå ñôn giaûn cho vieäc tính toaùn , ta söû duïng ñaïi löôïng RMS ( Root Mean Square ) . Vôùi moät range vaø moät domain cho tröôùc thì khoaûng caùch RMS chæ phuï thuoäc vaøo ñoä töông phaûn ci vaø ñoä saùng bi . Khoaûng laø nhoû nhaát khi thaønh phaàn daãn xuaát ra caû 2 laø ñeàu baèng 0 . Vì theá ta coù theå thu ñöôïc ci vaø bi baèng caùch giaûi quyeát 2 phöông trình tuyeán tính ñôn giaûn . Khi maø khoaûng caùch RMS giöõa range vaø caùc domain ñöôïc choïn ñaõ ñöôïc xaùc ñònh , boä neùn seõ choïn moät domain vôùi khoaûng caùch nhoû nhaát , maõ hoùa aùnh xaï affine töông öùng , vaø tieáp tuïc vôùi caùc range keá tieáp . CHÖÔNG IV Maõ Hoùa Vaø Giaûi Maõ Löôïc ñoà maõ hoùa . Söï phaân chia khoái . Domain Block Pool . Chuyeån ñoåi affine ( Haøm maõ hoùa) . Löôïng töû hoùa . Maõ hoùa Fractal vôùi aûnh maøu . Löôïc ñoà giaûi maõ . Löôïc ñoà giaûi maõ . Söï phuï thuoäc ñoä phaân giaûi . I . Löôïc ñoà maõ hoùa Fractal . Phaân Ñoaân . Taïo Domain Block Pool Chuyeån ñoåi affine Löôïng töû hoùa FRC file TGA file Hình 7 . Löôïc ñoà maõ hoùa . I.1. Söï phaân chia khoái . Nhö ñaõ noùi ôû treân , neùn Fractal laø bieán ñoåi caùc domain sang range , nhöng laøm theá naøo ñeå phaân chia caùc domain vaø caùc range ñoù thì laïi laø moät vaán ñeà caàn quan taâm . Maëc duø khoâng quan troïng laém nhöng noù cuõng quyeát ñònh moät phaàn veà chaát löôïng vaø thôøi gian neùn . Thöïc söï khoâng khaû thi khi ta phaûi tìm kieám toaøn boä taát caû nhöõng gì coù theå cuûa söï phaân chia hình aûnh trong nhöõng khoái range vôùi caùc hình vaø kích thöôùc khaùc nhau . Neáu khoâng coù moät löôïc ñoà söï phaân chia - PS ( Partition Scheme ) - hôïp lyù thì quaù trình neùn seõ khoâng khaû thi . Ñieàu naøy ñaõ giaûi thích taïi sao laø söï phaân chia hình aûnh laïi laø moät coâng ñoaïn quan troïng trong quaù trình neùn aûnh . Trong thöïc teá , yeâu caàu ñeå coù moät löôïc ñoà phaân chia nhanh vaø toái öu laø coù theå . Coù moät vaøi phöông phaùp khaùc nhau ñeå choïn löïa caùc khoái hình cuûa caáu truùc PS . ÔÛ ñaây , ta chæ quan taâm ñeán khoái hình chöõ nhaät vaø hình vuoâng vì chuùng ñôn giaûn vaø coù khaû naêng toái öu cao . Yeâu caàu laø thieát keá moät phöông thöùc hieäu quaû taïo ra ít söï toån haïi thoâng tin nhaát trong giai ñoaïn neùn ñeå ñaït ñöôïc toác ñoä neùn cao nhaát . Moät hình aûnh ñöôïc phaân chia vaøo trong moät maûng hai chieàu cuûa khoái pixel kích thöôùc BxB , ñöôïc goïi laø khoái range . Cho ví duï , kích thöôùc cuûa moät aûnh laø , 512x512 hoaëc 256x256 , thì khoái range seõ laø , , , . Caùc khoái range thöôøng ñöôïc maõ hoùa theo haøng bôûi thöù töï cuûa caùc haøng , maûng 2 chieàu cuûa caùc khoái range coù theå ñöôïc xem nhö laø moät daãy caùc maûng moät chieàu , nghóa laø . R11 R13 R21 R12 R22 … R2n R1n … … … … Rmn … … … … … Rm3 … Rm1 … Rm2 R23 R14 … R24 … … … … … Rm4 … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … … Hình 8 . Söï phaân chia moät hình aûnh thaønh moät taäp caùc khoái range . I.1.1 . Löôïc ñoà phaân chia hình vuoâng ( Quadtree ) vaø ngang doïc truyeàn thoáng (conventional horizontal vertical parition scheme ) . Ñaây laø moät phöông thöùc ñôn giaûn ñöôïc ñöara laàn ñaàu tieân bôûi Jacquin . Luùc baét ñaàu , PS chöùa caùc hình vuoâng coù kích thöôùc baèng nhau . Sau ñoù , trong suoát quaù trình neùn , moät hình vuoâng seõ ñöôïc phaân chia thaønh boán hình vuoâng con töông öùng cho ñeán khi ñaït ñöôïc chaát löôïng neùn yeâu caàu . Söï choïn löïa naøy laø hình vuoâng ñeå cho söï phaân chia cuûa noù cho moät caûi tieán lôùn nhaát veà chaát löôïng hình aûnh . Hình 9. aûnh “Lena” ñöôïc phaân chia theo daïng hình vuoâng ( Quadtree ) . Moät phöông phaùp khaùc laø phaân chia caùc khoái theo chieàu ngang vaø doïc thaønh caùc khoái nhoû coù daïng hình chöõ nhaät . Thoâng tin gôïi nhôù ñoái vôùi moãi khoái chöùa ñöïng daáu hieäu ñeå bieát raèng coù hay khoâng khoái naøy ñaõ ñöôïc phaân chia thaønh caùc khoái nhoû hôn ( moät bit ) . Ñieàu naøy xaùc ñònh soá löôïng caùc bit ñöôïc yeâu caàu , chuùng phuï thuoäc vaøo kích thöôùc caùc khoái ñöôïc phaân chia . Hình cho ta caùi nhìn kó hôn veà moät PS ngang doïc : Hình 10. aûnh “Lena” vôùi PS ngang doïc truyeàn thoáng . Tröôøng hôïp naøy cho ta söï linh hoaït vaø chaát löôïng aûnh toát hôn laø phöông phaùp PS Quadtree . Ñieàu baét buoät ñeå phaân tích moät soá löôïng lôùn söï khaùc nhau cho moãi söï phaân chia khoái daãn ñeán yeâu caàu tính toaùn cao . Ñaây laø söï haïn cheá cuûa öùng duïng PS ngang doïc thöïc teá . Moät caùch ñeå taêng toác cho phöông phaùp naøy laø söû duïng moät vaøi tieâu chuaån chaát löôïng ñôn giaûn . Trong khi toái öu hoùa PS thì raát deã daøng ñeå laøm giaûm toái ña vieäc ñaùnh giaù toång theå cuûa caùc khoái khaùc nhau ñöôïc tính toaùn laø : trong ñoù , M laø soá löôïng caùc khoái trong PS , Ni bieåu thò soá löôïng pixel trong khoái thöù i , laø söï sai soá caùc giaù trò pixel ñoái vôùi khoái thöù i . Vôùi vieäc söû duïng tieâu chuaån E ôû treân , PS ñöôïc toái öu hoùa khaù nhanh maëc duø chaát löôïng neùn aûnh teä hôn ñaùng keå so vôùi phöông phaùp truyeàn thoáng Quadtree . Söï trôû ngaïi naøy laøm haïn cheá öùng duïng thöïc tieãn cuûa phöông phaùp PS ñôn giaûn hoùa doïc ngang ( SHV PS – Simplied Horizontaly Verticaly Partition Scheme ) . Hình 11. Ví duï aûnh “Lena” vôùi löôïc ñoà phaân chia SHV PS . I.1.2 . Löôïc ñoà phaân chia ngang doïc ñöôïc hieäu chænh (modified horizontal vertical parition scheme ) . Moät yù töôûng maø chuùng ta ñöa ra ñaây laø thieát keá moät bieán theå thoûa hieäp , ñieàu maø ñoøi hoûi gaùnh naëng tính toaùn cho söï toái öu PS ( PS Optimization ) coù theå so saùnh ñöôïc vôùi Quadtree nhöng cho ra moät chaát löôïng neùn aûnh gaàn vôùi giôùi haïn coù theå ñaït ñöôïc cuûa phöông phaùp HV PS . Ñieàu naøy coù nghóa laø soá löôïng caùc bieán theå coù theå cuûa söï phaân chia khoái seõ ñöôïc laøm giaûm ñaùng keå so vôùi HV PS truyeàn thoáng trong khi vaãn giöõ ñöôïc tính deã daøng ñaùp öùng cuûa PS naøy . Ñeå coù ñöôïc thoûa hieäp naøy , chuùng ta ñöa ra moät phöông phaùp môùi maø chuùng ta goïi laø PS ngang doïc ñöôïc hieäu chænh – Modified Horizontal Vertical PS ( MHV PS ) . Söï giôùi haïn ñaët ra theo caùch phaân chia khoái naøy laø taïi moãi böôùc , moät khoái ñöôïc phaân chia ngang hoaëc doïc thaønh hai khoái daïng hình chöõ nhaät coù kích thöôùc baèng nhau . Chính vì theá , taïi moãi böôùc , noù caàn ñeå xem xeùt hai bieán theå coù theå coù . Neân nhôù raèng ñoái vôùi Quadtree chæ phaân tích chæ moät bieán theå trong khi ñoù phöông phaùp HV truyeàn thoáng thì coù soá löôïng bieán theå laø( M – 1)(N – 1) , trong ñoù M vaø N bieåu thò kích thöôùc khoái ñöôïc phaân chia theo chieàu ngang vaø doïc . Ñieàu naøy coù nghóa laø ñoái vôùi phöông phaùp ñöôïc ñöa ra ôû treân thì gaùnh naëng tính toaùn coù theå taêng leân ít nhaát gaáp hai laàn so vôùi Quadtree , nhöng noù duø sao ñi chaêng nöõa thì tieâu toán thôøi gian cuõng ít hôn möôøi laàn so vôùi phöông phaùp HV truyeàn thoáng . Yeâu caàu boä nhôù cho vieäc ghi nhaän PS ñoái vôùi phöông phaùp ñöôïc ñöa ra laø cuõng nhoû hôn nhieàu so vôùi HV PS . Traùi vôùi phöông phaùp HV truyeàn thoáng , phöông phaùp MHV PS thì khoâng caàn nhôù chæ muïc haøng hoaëc coät cuûa khoái ñöôïc phaân chia . Ñieàu naøy cho pheùp söû duïng tieát kieäm boä nhôù cho vieäc phaân chia boå xung moät vaøi khoái . Nhöng buø laïi , phöông phaùp naøy laïi maát ñi söï linh hoaït vaø chaát löôïng neùn aûnh thì keùm ñi . Moät söï thuaän lôïi cuûa MHV PS raát höõu ích laø nhö sau . Giaû söû raèng kích thöôùc caùc khoái hình vuoâng ban ñaàu laø luõy thöøa cuûa hai ( nhö 16x16 , 32x32 ,…) . Sau ñoù , taïi taát caû caùc giai ñoaïn cuûa söï toái öu PS , kích thöôùc cuûa caùc khoái con ñaït ñöôïc laø cuõng laø luyõ thöøa cuûa hai ( nhö 16x8, 32x16, … ) . Ñieàu naøy cho ta söï thuaän lôïi trong vieäc ñaït ñöôïc söï keát hôïp cuûa PS bôûi phöông phaùp MHV trong coâng ngheä neùn aûnh lai gheùp , trong tröôøng hôïp ñaëc bieät , noù coù theå söû duïng caû phöông phaùp chuyeån ñoåi rôøi raïc DCT Hình 12 . Ví duï MHV PS vôùi aûnh “Lena” . I .1.3 . Thöïc hieän phaân tích neùn aûnh Fractal treân löôïc ñoà phaân chia doïc ngang truyeàn thoáng vaø ñöôïc hieäu chænh . Vieäc so saùnh hieäu quaû cuûa caùc phöông phaùp neùn aûnh Fractal ñoái vôùi boán phöông phaùp toái öu PS ñöôïc thöïc hieän treân aûnh “Lena” ( 512x512 ) . Ba tæ leä neùn khaùc nhau – 400 , 80 vaø 16 töông öùng vôùi tæ leä bpp laø 0.02 , 0.1 vaø 0.5 ñaõ ñöôïc xem xeùt . Keát quaû ñaït ñöôïc theå hieän trong baûng 1 . Chaát löôïng aûnh ñöôïc giaûi neùn ñöôïc bieåu thò bôûi PSNR . Baûng 1 .Hieäu quaû neùn aûnh Fractal vôùi Quadtree , HV , SHV vaø MHV PS . Nhö chuùng ta thaáy , vieäc söû duïng MHV PS cho taát caû caùc tröôøng hôïp luoân cho PSNR ( 0.2 … 1.0 ) toát hôn so vôùi Quadtree . Cuõng taïi ñoù , PSNR cuûa MHV ñoái vôùi HV truyeàn thoáng thì khoâng lôùn hôn 0.4dB . Söï khaùc nhau naøy ñöôïc giaûi thích laø boä nhôù ñöôïc yeâu caàu cho vieäc löu tröõ döõ lieäu cuûa MHV thì ít hôn so vôùi HV truyeàn thoáng . Ñeå chöùng minh ñieàu naøy , baûng 2 seõ cho ta thaáy löôïng bit trung bình ñeå maõ hoùa thoâng tin cuûa caùc phöông phaùp . Ñieàu naøy cho pheùp söû duïng nhieàu khoái trong MHV hôn laø HV , vaø vì theá laøm taêng chaát löôïng giaûi neùn aûnh PSNR . Baûng 2. Soá bit trung bình ñöôïc yeâu caàu cho vieäc löu tröõ cho moät khoái . Ñeå coù moät söï saùng taïo trong vieäc tính toaùn phöùc taïp cuûa moät phöông thöùc ñöôïc xem xeùt , chuùng ta ñaùnh giaù yeâu caàu thôøi gian khi ñaït ñöôïc moät PS toái öu . Bôûi vì PS toái öu coù thôøi gian thaáp nhaát chính laø Quadtree , cho neân trong baûng 3 chuùng ta seõ ñöa ra caùc tæ leä thôøi gian ñöôïc so saùnh vôùi Quadtree . Ta seõ thaáy raèng thôøi gian ñöôïc yeâu caàu cho MHV lôùn gaàn gaáp ba laàn so vôùi Quadtree , trong khi ñoù thì HV truyeàn thoáng thì laïi caàn soá thôøi gian lôùn gaàn gaáp 255 laàn . Baûng 3 . So saùnh thôøi gian giöõa caùc PS ñoái vôùi Quadtree . I.2 . Domain Block Pool . Nhö chuùng ta ñaõ noùi ôû treân , ñoái vôùi moãi khoái range , moät khoái domain vaø aùnh xaï caàn thieát ñöôïc tìm thaáy sao cho khoái range vaø khoái domain trôû thaønh moät caëp toát nhaát . Vaäy thì chuùng ta seõ tìm kieám chuùng ôû ñaâu ? Caâu traû lôøi laø chính ôû giöõa Domain Block Pool. Domain Block Pool bao goàm caùc hình vuoâng kích thöôùc 2Bx2B trong hình aûnh goác vaø laø moät taäp caùc khoái domain . Noù coù theå ñöôïc sinh ra baèng caùch tröôït moät cuûa soå coù kích thöôùc 2Bx2B beân trong aûnh goác bôûi boû qua pixel töø traùi qua phaûi vaø töø treân xuoáng döôùi . 2B Domain Block 2B Hình 13 . Moät Domain Block Pool . Neáu aûnh laø thì seõ coù khoái . Cho ví duï , neáu kích thöôùc cuûa aûnh laø , kích thöôùc moät khoái range laø , böôùc nhaûy thì coù khoái domain ôû trong moät Domain Block Pool. ÔÛ ñaây , chuùng ta xem hoà khoái domain laø . So saùnh khoái range vôùi taát caû khoái domain trong Domain Block Pool töøng caëp moät , tìm ra caëp toát nhaát . Vaø laøm theá naøo ñeå tìm ra chuùng ? Chuùng ta haõy tìm hieåu veà chuyeån ñoåi affine , moät coâng ñoaïn heát söùc quan troïng trong quaù trình neùn vaø giaûi neùn Fractal . I.3 . Chuyeån ñoåi affine . ÔÛ phaàn treân , chuùng ta ñaõ bieát raèng maõ hoùa khoái fractal söû duïng caùc chuyeån ñoåi affine ,trong ñoù vector laø moät hình aûnh . Moãi phaàn töû trong vector thì theå hieän moät ñieåm aûnh . Cho hình aûnh saéc xaùm ( gray scale ) , ta thöôøng söû duïng 8bit/pixel vaø hình aûnh maøu laø 24bit/pixel . Caùc khoái range khoâng choàng laáp coù kích thöôùc nhoû thì ñöôïc aùnh xaï töø nhöõng khoái domain lôùn hôn . Caùc khoái range thöôøng coù kích thöôùc 8x8 pixel vaø caùc khoái domain laø 16x16 pixel . Kích thöôùc khaùc nhau giöõa caùc domain vaø caùc range laø ñeå ñaûm baûo raèng vieäc aùnh xaï laø thu nhoû . Vieäc aùnh xaï bao goàm caùc chuyeån ñoåi hình hoïc , boá trí vaø khoái cuøng vôùi söï co laïi cuûa caùc khoái domain vôùi kích thöôùc nhoû nhaát ñeå coù theå ñaùp öùng ñöôïc caùc khoái range . Ñieåm coá ñònh ( fixed point ) cuûa vieäc maõ hoùa khoái Fractal laø moät hình aûnh trong ñoù = ƒ() . Söï taùi taïo laïi hình aûnh ñöôïc maõ hoùa thaønh caùc khoái Fractal seõ cho chuùng ta ñieåm coá ñònh . Trong vieäc maõ hoùa haøm , haàu heát caùc haøm thoâng thöôøng phaûi coù 5 ñieàu kieän sau ñaây : 1 . Söï haïn cheá phaïm vi cuûa ƒ . Phaïm vi cuûa ƒ neân naèm trong domain cuûa ƒ , nghóa laø ƒ : A --> A. Ñieàu naøy laø caàn thieát vì ñieåm coá ñònh ñöôïc ñònh nghóa laø . Noù cuõng caàn thieát cho söï taùi taïo baèng voøng laëp vaø cuõng toát cho vieäc ñònh nghóa ñieåm coá ñònh theo caùc caùch khaùc - khôûi taïo laïi maø khoâng caàn voøng laëp. Cho tröôøng hôïp ñoù thì ñieàu kieän naøy theo sau ñoù phaûi ñöôïc söûa ñoåi. 2 . Söï meùo moù ( Distortion ) . Söï meùo moù cuûa vieäc maõ hoùa laø do söï khaùc nhau giöõa ñieåm coá ñònh p*vaø hình aûnh ban ñaàu p0 . Vì theá vieäc coá gaéng tìm ra ñieåm coá ñònh sao cho caøng gaàn vôùi hình aûnh ban ñaàu caøng toát laø ñieàu raát caàn thieát . 3. Khaû naêng neùn ( Compression ) . Ñeå coù moät heä soá neùn toát thì haøm neùn phaûi coù khaû naêng theå hieän ñöôïc moät caùch hieäu quaû. Ñaây laø ñieàu quan troïng nhaát bôûi vì muïc tieâu cuûa maõ hoùa laø ñaït ñöôïc moät heä soá neùn toát nhaát. ÔÛ ñaây seõ coù moät vaøi söï phöùc taïp bôûi vì haøm thoâng thöôøng seõ coù nhieàu caáp ñoä töï do hôn laø hình aûnh. 4. Tính thu goïn ( Contractivity ) . Caùc haøm coù tính thu nhoû ñöôïc laø moät vaán ñeà quan troïng trong vieäc taùi taïo hình aûnh cuûa ñieåm coá ñònh töø haøm . Vì ñieåm coá ñònh ñöôïc xaùc ñònh laø , p* coù theå ñöôïc taùi taïo baèng vieäc xöû lyù phöông trình naøy . Nhöng ñieàu naøy caàn khaû naêng tính toaùn lôùn vaø vì theá noù tieâu toán raát nhieàu thôøi gian . Lyù thuyeát ñieåm coá ñònh cuûa Banach cho ta ñieàu ñoù neáu haøm laø thu nhoû .Chuùng ta coù theå söû duïng caùc phöông thöùc sau ñeå khôûi taïo laïi hình aûnh töø moät haøm . Ñeå cho coù cuøng höôùng vôùi p0 nhöng ñöôïc choïn tuøy yù . Baèng vieäc laëp laïi theo phöông trình naø._.