Đồ án Nén ảnh phân đoạn – Fractal Image Compression

ieâ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øy : (1) thì seõ thu ñöôïc ñieåm coá ñònh . Ñieàu kieän naøy thì ñuû toát ñeå döøng laïi neáu caàn thieát vì noù chæ hieäu quaû treân vieäc taùi taïo hình aûnh chöù khoâng hieäu quaû treân maõ hoùa . 5. Tính duy nhaát ( Uniqueness ) cuûa ƒ. Haøm ƒ(p) chæ coù moät ñieåm coá ñònh töông öùng p* .Ñieàu naøy coù nghóa laø phöông trình chæ coù moät caùch giaûi duy nhaát . Ñieàu naøy thì hieäu quaû ñoái vôùi maõ hôn laø ñoái vôùi hình aûnh trong cuøng moät haøm . ÔÛ ñaây taát caû caùc haøm ñeàu coá gaéng ñeå thöïc hieän ñieàu kieän naøy . I.3.1. Söû duïng Vector trong haøm maõ hoùa . Trong caùc hình aûnh maõ hoùa baèng khoái Fractal thì thoâng thöôøng ñöôïc theå hieän bôûi vector . Haøm ñöôïc bieát nhö laø moät chuyeån ñoåi affine cuûa maët phaúng . ÔÛ ñaây , khi ñoù seõ coù kích thöôùc laø n2 . Heä soá K laø moät ma traän chuyeån ñoåi coù kích thöôùc n2 x n2 vaø laø moät vector chuyeån ñoåi vôùi kích thöôùc n2 . Bôûi vì vieäc neùn yeâu caàu vector chuyeån ñoåi thoâng thöôøng ñöôïc choïn laø , trong ñoù c laø voâ höôùng vaø laø moät vector vôùi taát caû caùc phaàn töû ñeàu baèng 1 ( vector cô sôû ) . , vôùi i = 1 , ………, n2 laø giaù trò rieâng cuûa K . Baùn kính quang phoå cuûa K ñöôïc xaùc ñònh bôûi : (2) Haøm laø thu nhoû neáu ρ(K) < 1 . Löôïc ñoà laëp cho ta thaáy ñieàu ñoù neáu laø thu nhoû . nghieäm cho phöông trình naøy laø (3) Neáu khoâng laø thu nhoû thì ñieåm coá ñònh coù theå vaãn ñöôïc tính toaùn baèng caùch giaûi phöông trình baèng : (4) neáu laø moät ma traän khaû nghòch . Ma traän laø ma traän kích thöôùc n2 x n2 ñoàng nhaát . Phöông trình coù moät nghieäm giaûi duy nhaát neáu vaø chæ neáu vaø cuõng coù yeâu caàu töông töï vôùi i = 1,…..,n2 . I.3.2. Söû duïng ma traän trong haøm maõ hoùa. Bôûi vì hình aûnh thöôøng ñöôïc xem nhö laø caùc ma traän . Chuùng ta ñaõ töøng ñöôïc hoïc tröôøng hôïp maø khi ñoù ma traän ñöôïc söû duïng nhö laø caùc bieán trong haøm . ÔÛ ñaây , ta seõ thaûo luaän sô veà haøm ƒ(P) = AP + C . Moät trong caùc haøm khaù toát ñeå söû duïng khi hình aûnh ñöôïc xaùc ñònh laø caùc ma traän laø ƒ(P) = AP + C , trong ñoù A , P vaø C laø caùc ma traän kích thöôùc nxn . P laø moät ma traän aûnh , A taïo ra moät chuyeån ñoåi vaø C laø moät chuyeån ñoåi . Haøm naøy laø thu goïn neáu ρ(A) < 1 . Neáu ƒ(P) laø thu goïn thì phöông trình coù theå ñöôïc giaûi quyeát nhö sau : (5) Coøn neáu haøm khoâng coù tính thu nhoû thì ñieåm coá ñònh coù theå ñöôïc tìm thaáy bôûi phöông trình P* = AP* + C vaø noù cho ta moät nghieäm : P* = (In – A)-1C (6) trong ñoù , ma traän (In – A) phaûi laø ma traän khaû nghòch . Phöông trình coù moät nghieäm duy nhaát neáu vaø chæ neáu det(In – A) ≠ 0 , nghóa laø vôùi i = 1,……, n . Ma traän C coù theå ñöôïc choïn laø C = cE , trong ñoù c laø voâ höôùng vaø E laø ma traän vôùi taát caû caùc phaàn töû ñeàu baèng 1 . Söï choïn löïa naøy seõ sinh ra tæ leä neùn cao . Moät söï choïn löïa hôïp lyù cuûa c chính laø giaù trò trung bình cuûa aûnh goác P0 . Nhöng vôùi haøm naøy thì chuùng ta thaáy raèng P* = (In – A)-1C coù baäc 1 bôûi vì C coù baäc 1 . Trong tröôøng hôïp naøy taát caû caùc coät cuûa P* seõ trôû neân baèng nhau . Chính vì theá , chuùng ta phaûi tìm ra moät söï choïn löïa toát hôn C = cE cho ma traän C . Söï löïa choïn toát nhaát chính laø C = cIn , trong ñoù c vaãn laøvoâ höôùng vaø In laø ma traän ñoàng nhaát . Ma traän naøy coù baäc n vaø noù cho ta moät khaû naêng neùn toát ôû cuøng thôøi ñieåm . Vôùi söï choïn löïa naøy cuûa ma traän C thì nghieäm phöông trình seõ laø : P* = c(In – A) -1 . (7) Trong tröôøng hôïp vector , moät soá söï choïn löïa khaùc cuûa ma traän K ñeàu daãn ñeán cuøng moät ñieåm coá ñònh . Nhöng vôùi phöông trình ƒ(P) = AP + C chæ coù ma traän A cho nghieäm chính xaùc P* = P0 vôùi . Ma traän A coù theå ñöôïc xem nhö laø moät chuyeån ñoåi khoâng tuyeán tính cuûa ma traän P . Chuùng ta ñaõ nghieân cöùu ñaëc tính cuûa bieán ñoåi naøy nhöng noù döôøng nhö khoâng hieäu quaû nhö laø moät soá caùc bieán ñoåi khaùc ñöôïc söû duïng trong vieäc maõ hoùa chuyeån ñoåi . Trong moät soá tröôøng hôïp , noù coù theå laø yù töôûng toát ñeå môû roäng haøm thaønh ƒ(P) = A(P – C + dIn)+ C , trong ñoù d laø voâ höôùng vaø In laø ma traän ñoàng nhaát kích thöôùc nxn . Haøm naøy ñeàu coù yeâu caàu veà tính thu nhoû vaø nghieäm duy nhaát . Neáu noù coù tính thu nhoû thì ñieåm coá ñònh ñöôïc tính baèng : (8) Trong haøm naøy , ma traän C coù theå ñöôïc choïn laø C = cE maø khoâng gaây ra baát cöù vaán ñeà naøo vôùi baäc cuûa ñieåm coá ñònh . Haøm ñöôïc môû roäng naøy seõ ñöôïc söû duïng ôû phaàn sau . I.3.3 Ñieàu kieän coù tính thu nhoû cuûa caùc haøm . Taát caû ba loaïi haøm ôû treân ñeàu coù cuøng caùc yeâu caàu veà tính thu nhoû . Baùn kính quang phoå cuûa moät vaøi ma traän phaûi nhoû hôn moät . Ñoái vôùi haøm ƒ(P) = APB + C thì deã daøng ñeå thaáy raèng ρ(A) < 1 vaø ρ(B) < 1 thì cho ta moät haøm coù tính thu nhoû , suy ra ρ(A)ρ(B) < 1 . Phaàn naøy chuùng ta seõ nghieân cöùu laøm nhö theá naøo maø chuùng ta coù theå chaéc raèng ρ(X) < 1 , trong ñoù X = [xij] laø moät ma traän kích thöôùc nxn . Hai caùch khaùc seõ ñöôïc theå hieän cuøng vôùi moät tröôøng hôïp ñaëc bieät cho haøm ƒ(P) = AP + C . Trong vieäc maõ hoùa khoái Fractal , quy phaïm X , ||X|| , thöôøng ñöôïc söû duïng ñeå moâ taû tính thu nhoû vaø caùc haøm ñöôïc goïi laø haøm coù tính thu nhoû neáu ||X|| < 1 . Bôûi vì chuùng ta coù ρ(X) ≤ ||X|| thì tröôøng hôïp ||X|| < 1 laø ñuû nhöng khoâng laø ñieàu kieän caàn thieát cho ρ(X) < 1 . Tröôøng hôïp ñaëc bieät : ρ(X) < 1 < ||X|| thì ñöôïc goïi laø tính thu nhoû . Bôûi vì ||X|| < 1 laø ñuû nhöng khoâng laø ñieàu kieän caàn thieát cho tính thu nhoû , noù seõ khoâng ñöôïc söû duïng trong ñaây . I.3.3.1 . Caùc ma traän hình tam giaùc . Neáu ma traän X laø ma traän coù daïng tam giaùc thì giaù trò rieâng cuûa X seõ baèng vôùi giaù trò cuûa caùc phaàn töû treân ñöôøng cheùo .Vì theá , baèng vieäc giôùi haïn giaù trò cuûa caùc phaàn töû treân ñöôøng cheùo laïi thaønh : -1 < xij < 1 , (9) vôùi i = 1,….., n , thì ñieàu kieän ρ(X) seõ ñöôïc thoaû maõn . Baèng caùch choïn ma traän nhö laø moät ma traän daïng tam giaùc thì moät vaøi kyõ thuaät neùn cuõng seõ ñöôïc thöïc hieän . Tuy nhieân , soá löôïng caùc ma traän khaû thi X cho ñieåm coá ñònh seõ bò maát . Ñieàu naøy khoâng quaù quan troïng ñoái vôùi bôûi vì K coù nhieàu möùc töï do . Nhöng ñoái vôùi ƒ(P) = AP + C , chæ coù moät ma traän cho P* = P0 vaø vì theá A coù leû khoâng laø moät ma traän tam giaùc . Cuoái cuøng , ƒ(P) = APB + C laø khaû thi ñeå tìm ra hai ma traän tam giaùc A vaø B , ñaùp öùng ñöôïc ñieàu kieän soá hai ñöôïc neâu ra ôû treân , nhöng noù seõ coù leõ khoâng thoaû maõn ñöôïc ñieàu kieän 3 . Vì theá , ma traän daïng tam giaùc ñöôïc söû duïng toát nhaát trong tröôøng hôïp vector , . I.3.3.2 . Giaùm saùt caùc giaù trò cuûa töøng phaàn töû . Moät caùch khaùc ñeå quaûn lyù giaùtri rieâng cuûa moät ma traän laø giöõ chuùng ôû möùc thaáp . Caùc quan heä sau toàn taïi giöõa nhöõng phaàn töû cuûa moät ma traän vaø baùn kính quang phoå cuûa chuùng : (10) (11) Moät caùch ñeå thöïc hieän ñieàu naøy laø söï khaét khe trong vieäc giôùi haïn caùc phaàn töû bôûi : < xi,j < (12) Chuùng taseõ kieåm tra moät caùch deã daøng trong vieäc