跳到主要內容

臺灣博碩士論文加值系統

(3.236.84.188) 您好!臺灣時間:2021/08/03 09:50
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:何霈豪
研究生(外文):Pei Hao Ho
論文名稱:路徑分割演算法及其在影像處理之應用
論文名稱(外文):A path partition algorithmand its application to image processing
指導教授:吳邦一
指導教授(外文):Bang Ye Wu
學位類別:碩士
校院名稱:樹德科技大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:中文
論文頁數:32
中文關鍵詞:路徑分割子路徑灰階影像降階
外文關鍵詞:p-partitiongray-level imageL2-norm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:194
  • 評分評分:
  • 下載下載:24
  • 收藏至我的研究室書目清單書目收藏:0
給定一條路徑,上面有n個正整數權值的節點,minimum L2 p-partition的問題是如何在這條路徑中分割成p個子路徑,其每個子路徑權重的平方和為最小。在這篇論文中,我們提出了時間複雜度O(pnlogn)的演算法來解決這個問題。另外,我們研究如何在灰階影像降階上使用這個演算法。我們使用四種演算法Naive、Greedy、MUP與L2-norm,並比較它們的執行時間和壓縮品質。實驗結果為L2-norm的演算法比MUP更有效率,比另外兩者的壓縮品質更好。
Given a path with a positive weight on each vertex, the minimum L2 p-partition problem is to find a way to cut the path into p subpaths such that the sum of squares of the subpath weights is minimized. In this thesis, we propose an O(pnlogn) time algorithm for the problem. In addition, we studied how to use this algorithm to compress a gray-level image by reducing the number of gray-levels. We investigated the running times and the effects of four algorithms, named Naive, Greedy, MUP and L2-norm. The experience results show that L2-norm algorithm is efficient than MUP and is effective than the other two algorithms.
中文摘要 i
英文摘要 ii
目錄 iii
表目錄 iv
圖目錄 v
第一章 緒論 - 1 -
1.1 前言 - 1 -
1.2 目標函數的介紹 - 1 -
1.3 先前研究結果 - 3 -
1.4 研究目的與問題 - 3 -
1.5 論文架構 - 4 -
第二章 有效率的演算法求L2-norm的路徑分割 - 5 -
2.1 前言 - 5 -
2.2 一般動態規劃的方法 - 5 -
2.3 有效率的演算法 - 9 -
第三章 路徑切割之演算法應用於影像降階之研究 - 14 -
3.1 前言 - 14 -
3.2 路徑切割方法介紹 - 15 -
3.2.1 Naive - 15 -
3.2.2 Greedy - 16 -
3.2.3 Min difference - 17 -
3.2.4 L2-norm - 18 -
3.3 實驗 - 19 -
第四章 結論 - 25 -
參考文獻 - 26 -
附錄一 BMP檔案格式 - 28 -
1. R.I. Becker, S.R. Schach, and Y. Perl. A shifting algorithm for min-max tree partitioning, J. ACM, 29:58-67, 1982.

2. R. Becker, I. Lari, M. Lucertini, and B. Simeone, A polynomial-time algorithm for max-min partitioning of ladders, Theory Comput. Systems, 34:353-374, 2001.

3. M. Lucertini, Y. Perl and B. Simeone, Most uniform path partitioning and its use in image processing, Discrete Appl. Math. 42:227-256, 1993.

4. M. Liverani, A. Morgana, B. Simeone, and G. Storchi, Path equipartition in the Chebyshev norm, Europ. J. Opl. Res., 123:428-436, 2000.

5. E.L. Aparo and B. Simeone, Equipartizione su un grafo: una applicazione all’informatica medica, in Applicazioni del calcolo, I. Galligani edt., CNR, Rome, 77-86, 1975. (In Italian)

6. G. Messe, Partitions of chains with minimum imbalance, Cahiers du Centre d’Etudes de Recherche Operationelle, 27:235-245, 1985.

7. C.D. Simone, M. Lucertini, S. Pallotino, and B. Simeone, Fair dissections of spiders, worms and caterpillars, Networks, 20:323-344, 1990.

8. M. Schr”oder, Gebiete optimal aufteilen, PhD thesis, University Karlsruhe, Germany, 2001.

9. R. Becker and Y. Perl, The shifting algorithm technique for the partitioning of trees, Discrete Appl. Math., 62:15-34, 1995.

10. R. Becker, B. Simeone and Y.-I Chiang, A shifting algorithm for continuous tree partitioning, Theor. Comput. Sci., 282:353-380, 2002.

11. S. Kundu and J. Misra, A linear tree partitioning algorithm, SIAM J. Comput, 6:151-154, 1977.

12. Y. Perl and S.R. Schach, Max-min tree partitioning, J. ACM, 28:5-15, 1981.

13. Bang Ye Wu, Pei-Hao Ho, An efficient algorithm for the minimum L2 path partition , Proceedings of the 2006 Symposium on Applications of Information, Management and Communication Technology, Taiwan, CD-ROM, C1-4, 2006, R.O.C.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文