(3.236.214.19) 您好!臺灣時間:2021/05/10 06:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:洪嘉祥
研究生(外文):Chia-Hsiang Hung
論文名稱:奇異吸引子的應用----碎形影像壓縮
論文名稱(外文):An Application of Strange Attractors----Fractal Image Compression
指導教授:廖思善
指導教授(外文):Sy-Sang Liaw
學位類別:碩士
校院名稱:國立中興大學
系所名稱:物理學系
學門:自然科學學門
學類:物理學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:中文
論文頁數:90
中文關鍵詞:碎形吸引子混沌維度疊代函數系統編碼自我相似性分類
外文關鍵詞:fractalattractorchaosdimensionifsencodeself-similarityclassification
相關次數:
  • 被引用被引用:1
  • 點閱點閱:281
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
碎形(Fractals)經過了十幾年來的發展與開創,其研究在當今已形成了一股熱潮。本研究從吸子(Attractor)的動力系統所產生的混沌(Chaos)現象、吸子碎形結構的維度(Dimension)問題,以及如何自動(Automatic)產生吸子開始,後來我們著手研究吸子在圖形壓縮(Image Compression)上的應用。
在1985年Barnsley和他的伙伴提出迭代函數系統(IFS)可應用於處理全域的(Global)壓縮影像的理論失敗後,到1993年,Barnsley的研究生Jacquin在他的博士論文中發表了分區迭代函數系統(PIFS)碎形影像編碼(Encode)的理論,成功的壓縮了影像,達成了將碎形應用在圖形壓縮的不可能任務。
碎形圖像因為它們具有全域的自我相似性(Self-similarity),所以可用簡單的IFS呈現出來,而一張不具有全域的自相似的生活圖像,得經由它本身的部分(Local)區域的影像重建整張圖像,Jacquin之後碎形編碼由Fisher和其他研究人員進一步研究與應用,加速了這門學科的進展,Yuval Fisher並將C程式放在全球網路上,使碎形影像壓縮,隨之快速發展,我們也由此出發提出新改進方法。
90年代起有很多人提出一些改進的方法。我們在針對初期的碎形影像壓縮作研究之後,發現改變定義域塊(Domain)的數量影響壓縮品質,因而提出參l數調整Domain pool中Domain的數目以縮短壓縮時間,並事先對每個Range和Domain作變換矩陣(Isometry)的分類,在不影響壓縮品質下,進一步縮短壓縮時間,配合利用特性(Feature)分類的原則,使搜尋Domain的範圍自動化調整,更進一步縮短了壓縮時間,並能夠提高壓縮的品質的目標,最後我們再利用碎形壓縮進一步補償碎形壓縮的失真度,使得兩次碎形壓縮的品質超越一次碎形壓縮品質的極限。
The study of Fractals has been developed and evolved for at least 10 years. Its study has been the vogue in the present world. In this research, we first discuss the phenomenon that is produced in the attractors because of the dynamical system in Chaos, the dimension problem in fractal structure, and the ways attractors are automatically produced. We then set our hand on image compression utilizing attractors.
In 1985, Barnsley and his colleagues’ proposal that image compression make use of the global Iterated Function System(IFS)failed finally. In 1993, Jacquin, a post-graduate student of Barnsley, published Partitioned Iterated Function System(PIFS)for image compression encoding theorem in his doctoral thesis that leading to image compression succeed. Image compression utilizing the property of fractals accomplished an impossible mission in the ultimate.
Fractal patterns can be reconstructed using simple IFS because they have the global self-similarity. An ordinary picture has no property of self-similarity, but it can be reconstructed using local block of itself patterns. After Jacquin’s proposal, Fisher and other researchers make a study and apply progressively for fractal encoding that make fast development in fractal image compression. Yuval Fisher put his C program on the World Wide Web site, let the study of fractal image compression grow up fast.
In the 90’s, some new better methods were proposed. Based on the earlier studies on the fractal image compression, we find that changing the number of Domains does affect the compressive quality. For this reason, we propose the factor that changes the number of Domain in Domain pool, so as to reduce the compressive time. At the same time, we use Isometry Classified for each Range and Domain beforehand. In the last, to keep the quality of compression and further reduce the compressive time, we propose the classification of features that can automatically change the range in Domain search. The classification of features not only diminishes the compressive time but also raises the quality of compression.
論文中文摘要………………………………………………...…………………Ι
論文英文摘要………………………………………………...………………...Ⅲ
誌謝………………………………………………...………………………………Ⅴ
目錄………………………………………………...………………………………Ⅵ
表目錄………………………………………………...…………………………..Ⅸ
圖目錄………………………………………………...…………………………..Ⅹ
第一章 緒論………………………………………………...……………………..1
1-1 研究源起………………………………………………………..…………..1
1-2 研究動機與目的…………………………………………………………..1
1-3 研究工具…………………………………………………………………....1
1-4 研究方法…………………………………………………………………....2
1-5 本文提要…………………………………………………………………....2
第二章 碎形影像壓縮的理論基礎……………………………….….……3
2-1 發展背景…………….….………………………………….………………3
2-2 碎形與在圖像中的自我相似性……………………………….….……3
2-2-1 康托集Cantor sets(或稱康托粉塵Cantor dust)……………….4
2-2-2 Sierpinski三角形(或稱為Sierpinski arrowhead 或gasket)…..4
2-2-3 Hilbert curve………………………………………………………….5
2-2-4 Koch曲線……………………………………………………………..6
2-2-5 碎形維度………………………………………………………………7
2-2-6 影像中的自相似性…………………………………………………...8
2-3 奇異吸引子(Strange Attractor)…………………………………..8
2-3-1 Lorenz吸引子…………………………………………………………9
2-3-2 Rossler吸引子………………………………………………………..10
2-3-3 Henon吸引子…………………………………………………………11
2-3-4 奇異吸引子的自動製造……………………………………………...11
2-4 數學理論基礎…………………………………………………………….13
2-4-1 完備距離空間(Complete Metric Space)…………………………13
2-4-2 仿射變換(Affine Transformation)………………………………14
2-5 迭代函數系統(Iterated Function Systems簡稱IFS)………..17
2-5-1 緊集合(Compact sets)和Hausdorff space………………………17
2-5-2 收縮映射定理(Contraction Mappings Theorem簡稱CMT)….18
2-5-3 貼片定理(Collage Theorem)……………………………………..19
2-5-4 確定性迭代算法..……………………………………………………20
2-5-5 隨機性迭代算法……………………………………………………..24
2-5-6 IFS的自動製造……………………………………………………….27
第三章初期的碎形影像壓縮……………………………………………...31
3-1 灰階影像的距離空間…………………………………………………...31
3-2 區塊分割…………………………………………………………………..32
3-3 灰階影像中的CMT…………………………………………………….33
3-4 影像種類與資料壓縮的概念………………………………………….37
3-5 圖像品質的判定標準與壓縮比………………………………………37
3-5-1 客觀判別標準………………………………………………………..38
3-5-2 主觀評價……………………………………………………………..40
3-5-3 壓縮比………………………………………………………………..40
3-6 初期碎形影像的壓縮與解壓縮……………………………………….42
3-6-1 初期的碎形解壓縮結果……………………………………………..44
3-6-2 初期的碎形壓縮結果………………………………………………..49
第四章快速的碎形影像壓縮……………………………………………...50
4-1 改變定義域塊的數量影響壓縮品質…………………………………50
4-1-1 增加大塊的定義域塊提升壓縮品質……………………………..…50
4-1-2 減少小塊的定義域塊縮短壓縮時間………………………………..52
4-2 變換矩陣對壓縮品質與壓縮時間的影響…………………………..55
4-2-1 減少變換矩陣使用縮短壓縮時間…………………………………..55
4-2-2 變換矩陣的分類縮短壓縮時間……………………………………..57
4-3自動化調整搜尋範圍以縮短壓縮時間─特性分類的利用………63
4-3-1 特性的定義…………………………………………………………..63
4-3-2 特性的數值分析……………………………………………………..66
4-3-3 特性分類的碎形影像壓縮結果……………………………………..69
4-4碎形壓縮補償碎形壓縮的失真度…………………………………….73
4-4-1如何將失真的碎形影像壓縮變為不失真………………...………….73
4-4-2誤差圖像平移量對兩次碎形壓縮還原品質的影響……...………….75
4-4-3在不同條件下兩次碎形壓縮造成壓縮時間與壓縮品質的影響……77
第五章結論……………………………………………………………………...79
參考文獻…………………………………………………………………………80
表目錄
表2-1 奇異吸引子的參數…………………………………………………………13
表2-2 對稱變換矩陣………………………………………………………………15
表2-3 吸引子圖形的參數…………………………………………………………30
表3-1 的大小與 的數量關係…………………………………………………32
表3-2 十進位檔範例………………………………………………………………40
表3-3 原始圖ba.bmp為 像素的圖檔,其大小為263222 byte…………40
表3-4 二進位做規則儲存時所需記憶空間的配置……………………………….41
表3-5 不同初始圖像還原後圖像 的品質……………………………………….45
表3-6 不同初始圖像產生的誤差………………………………………………….46
表3-7 ba.bmp及ba256.bmp兩圖對 大小不同的壓縮比與壓縮時間………….48
表4-1-1 n=16對不同大小的Domain pool的比較……………………………….50
表4-1-2 n=8對不同大小的Domain pool的比較…………………………………52
表4-2-1 分類後 與 相對的變換矩陣項次……………………………………..59
表4-2-2 對不同圖像使用變換矩陣與變換矩陣分類的壓縮時間和品質………..60
表4-3-1 不同圖像的特性值…..…………………………………………………....65
表4-3-2 以不同方式調整比較 的數量…………………………………………..70
表4-4-1平移量s對二次壓縮的關係………………………………………………76
表4-4-2改變特性值規範 對總壓縮時間的影響………………………………...78
圖目錄
圖2-1-1 Cantor sets…………………………………………………………………...4
圖2-2-2 Sierpinski三角形……………………………………………………………5
圖2-2-3 Hilbert curve( )…………………………………………………………6
圖2-2-4 Koch雪花曲線………………………………………………………………7
圖2-2-5邊長為 的方形,覆蓋正方形的數目為 ………………………………8
圖2-2-6圖片中有自相似性………………………………………………………….8
圖2-3-1 Lorenz吸引子…………………………………………………………….…9
圖2-3-2 Rossler吸引子……………………………………………………………..10
圖2-3-3 Henon吸引子………………………………………………………………11
圖2-3-4奇異吸引子…………………………………………………………………12
圖2-5-1經變換矩陣作用後的圖像…………………………………………………16
圖2-5-2 …………………………………………………………….17
圖2-5-3收縮映射f作用在 的點集上……………………………………………18
圖2-5-4 Sierpinki三角形…………………………………………………………....21
圖2-5-5 Sierpinki三角形……………………………………………………………22
圖2-5-6 maple leaf…………………………………………………………………..23
圖2-5-7 maple leaf…………………………………………………………………..24
圖2-5-8 Spleenworf fern…………………………………………………………….26
圖2-5-9 maple leaf…………………………………………………………………..27
圖2-5-10吸引子圖形……………………………………………………………….29
圖3-2-1 Domain block透過變換 成Range block………………………………..32
圖3-2-2 ba.bmp在解壓縮時對 所做的區塊分割……………………33
圖3-3對不同初始圖 作收縮映射 得到相同圖像……………………………..35
圖3-4資料壓縮的系統……………………………………………………………..36
圖3-5不同品質圖像的視覺效果…………………………………………………..38
圖3-6 ba.bmp為 大小………………………………………………...40
圖3-7初期碎形壓縮的流程圖……………………………………………………..42
圖3-8初期碎形解壓縮的流程圖…………………………………………………..43
圖3-9 ma256.bmp為 大小……………………………………………44
圖3-10圖大小為 ,固定 大小解壓縮時PSNR vs.疊代次數…….44
圖3-11圖大小為 ,固定 大小解壓縮時PSNR vs.疊代次數…….45
圖3-12原圖A與解壓縮之後圖A’兩圖相減在視覺上的差異……………………46
圖3-13不同的初始圖……………………………………………………………….47
圖4-1-1 n=16, 數目對壓縮時間與還原品質的關係圖……………………….50
圖4-1-2 n=16,將圖4-1-1局部放大………………………………………………51
圖4-1-3 n=16, 數目對還原品質的關係圖…………………………………….51
圖4-1-4 n=8, 數目對壓縮時間與還原品質的關係圖…………………………52
圖4-1-5 n=8,將圖4-3局部放大…………………………………………………53
圖4-1-6 n=8, 數目對還原品質的關係圖………………………………………53
圖4-2-1不用變換矩陣的壓縮流程圖………………………………………………55
圖4-2-2變換矩陣使用數量對時間與壓縮品質的關係圖…………………………56
圖4-2-3使用某一個變換矩陣對時間與壓縮品質的關係圖………………………56
圖4-2-4變換矩陣分類的流程圖……………………………………………………57
圖4-2-5 所有可能的組合…………………………………………………………59
圖4-2-6第一類的 在與 比較時所用的變換矩陣示意圖……………………...59
圖4-2-7壓縮時間與變換矩陣使用的關係………………………………………....60
圖4-2-8還原圖形品質與變換矩陣使用的關係…………………………………...61
圖4-2-9使用壓縮圖像為初始圖解壓縮的品質…………………………………...61
圖4-3-1使用特性分類的流程圖……………………………………………………63
圖4-3-2像素分佈不同的圖像………………………………………………………65
圖4-3-3特性一:標準差的值域對 與 的數量分佈……………………………66
圖4-3-4特性二:不對稱度的值域對 與 的數量分佈…………………………66
圖4-3-5特性三:相鄰的變異量的值域對 與 的數量分佈…………………...67
圖4-3-6特性四:中心與邊緣的變異量的值域對 與 的數量分佈…………...67
圖4-3-7特性七:最大梯度的值域對 與 的數量分佈…………………………68
圖4-3-8特性八:對角梯度的值域對 與 的數量分佈…………………………68
圖4-3-9調整搜尋範圍 的示意圖………………………………………………...69
圖4-3-10壓縮時間與壓縮品質的關係…………………..………………………...70
圖4-3-11壓縮時間與壓縮比的關係………………….……………………………71
圖4-3-12壓縮時間對 的關係…………………………………………………….72
圖4-3-13特性2、4、7、8的壓縮時間與壓縮比的關係…………………………72
圖4-3-14特性1、3及總特性的壓縮時間與壓縮比的關係………..…………….73
圖4-4-1左圖為原始圖像A,右圖為失真圖像A’ ……………………………….74
圖4-4-2圖4-4-2左圖失真圖像B,右圖為B圖的反相圖………………………74
圖4-4-3 B圖像素值域分佈…………………………………………………………75
圖4-4-4失真圖像B平移灰階度+130得左圖,平移+90得右圖……………...76
圖4-4-5平移量s對二次碎形壓縮的品質關係…………………………………….77
[1] 廖思善,“碎形的魅力”,科學月刊,第363期,pp.222
[2] 張志三,“漫談碎形”,牛頓出版公司,1996
[3] Alex P. Pentland, “Fractal-Based Description of Natural Scenes”, IEEE
Transactions on Pattern Analysis and Machine Intelligence, Vol. Pami, No. 6, pp. 661-674, Nov. 1984
[4] Alligood, K. T., Sauer, T. D. and Yorke, J. A., “CHAOS-An Introduction to Dynamical Systems”, Springer-Verlag New York, 1997.
[5] Falconer K., “Fractal Geometry-Mathematical Foundations and Applications”, John Wiley & Sons, 1990.
[6] Roger T. Stevens, “Fractal Programming in C”, M & T Publishing, Inc., 1989
[7] Barnsley, M. F., “Fractals Everywhere”, 2nd., Academic Press, 1993,1988.
[8] Saupe, D., Hamzaoui R. and Hartenstein H., “Fractal Image Compression An Introductory Overview”, SIGGRAPH’96 Course Notes XX, New Orleans, chapter 2, Aug. 1996.
[9] Barnsley, M. F. and Demko, S., “Iterated Function Systems and the Global Construction of Fractals”, proc. R. Soc. Lon., vol.399 A, pp.243-275, 1985.
[10] Barnsley, M. F. and Sloan, A. D., “A Better Way To Compress Images”, BYTE, PP.215-223, Jan. 1988.
[11] Jacquin, A. E., “Fractal Image Coding A Review”, proc. IEEE, vol.81, pp.1451-1465, Oct. 1993.
[12] Yuval Fisher’s site at http://inls.ucsd.edu/y/Fractals/
[13] Fisher, Y., “Fractal Image Compression──Theory and Application”, Springer-Verlag, New York, 1994.
[14] 林和 譯,“混沌──不測風雲的背後”,天下文化出版公司,1992
[15] 廖思善、洪嘉祥,“奇異吸引子”,科學月刊,第
[16] Sprott, J. C., “Automatic Generation of Strange Attractors”, Chaos and Graphics, Vol.17, No.3, pag.325-332, 1993
[17] Ning Lu, “Fractal Imaging”, Academic Press, 1997
[18] Mandelbrot, Benoit B., “The Fractal Geometry of Nature”, Freeman, 1983
[19] 金以文、魯世杰編著,“分形幾何原理及其應用”,浙江大學出版社,1998
[20] Daniel P. Huttenlocher, Gregory A. Klanderman, and William J. Rucklidge, “Comparing Images Using the Hausdorff Distance”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 15, No. 9,pp. 850-863, Sep. 1993
[21] Welstead, Stephen T., “Fractal and Wavelet Image Compression Techniques”, SPIE Press, 1999
[22] Sprott, J. C., “Automatic Generation of Iterated Function Systems”, Chaos and Graphics, Vol.18, No.3, pag.417-425, 1994
[23] 陳守吉、張立明編著,“分形與圖象壓縮”,上海科技教育出版社,1998
[24] Arnaud E. Jacquin, “Image Coding Based on a Fractal Theory of Iterated Contractive Image Transformations”, IEEE Transactions on Image Processing, Vol.1, No.1, pag.18-30, Jan. 1992
[25] D. M. Monro and F. Dudbridge, “Fractal Block Coding of Images”, Electronics Letters, 21st Vol.28 No.11, pag.1053-1055, May 1992
[26] 施威銘研究室著,“PC影像處理技術(一)──圖檔壓縮篇”,旗標出版公司,民國82年
[27] Brown, C. Wayne and Shepherd, Barry J., “Graphics File Formats──reference and guide”, Manning Publications Company, 1995
[28] Charles A. Poynton, “Frequently Asked Questions about Colour”, at:<ftp://ftp.inforamp.net//pub//users/poynton/doc/colour/colorFAQ.pdf>, 1995
[29] 黃匡庸 編著,“IBM PC繪圖技術徹底研究”,波全資訊公司,民國81年
[30] 陳廷標、夏良正 編著,“數位影像處理”,儒林圖書公司,1993
[31] Douglas J. Granrath, “The Role of Human Visual Models in Image Processing”, Processing of the IEEE, Vol.69, No.5, pp.552-561, May 1981
[32] Noam Efrati, Hillel Liciztin, “Classified Block Truncation Coding-Vector Quantization:An edge sensitive image compression algorithm”, Signal Processing:Image Communication 3, pag.275-283, 1991
[33] Robert M. Gray, “Vector Quantization”, IEEE ASSP magazine, vol. 1, pag.4-29, April 1984
[34] K. F. Loe, W. G. Gu and K. H. Phua, “Speed-up Fractal Image Compression with a Fuzzy Classifier”, Signal Processing:Image Communication 10, pag.303-311, 1997
[35] C. K. Lee and W. K. Lee,“Fast Fractal Image Block on Local Variance”, IEEE Transactions on Image Processing, Vol.7, No.6, pag.888-891, June 1998
[36] Sang-Moon Lee and Sung-Woong Ra, “Fast fractal encoding algorithm using variances of image blocks’, Electronics Letters, Vol.34, No.10, pag.971-973,14th May 1998
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔