基於圖形密度之自動化揉皺紙張中摺痕網路偵測

Automatic Ridge Network Detection in Crumpled Paper Based on Graph Density

黃茂聞(Huang, Marvin)

指導教授 ： 許秋婷

國立清華大學/電機資訊學院/資訊工程學系/碩士(2011年)

https://doi.org/10.6843/NTHU.2011.00502

摘要

在揉皺的紙張(crumpled paper)中，存在有特定且複雜的結構。物理學家一般稱這種結構為摺痕網路(ridge network)。而現今存在的文獻也證明因為其複雜的結構而導致自動化偵測摺痕網路是一個很困難的問題。在這篇論文中，基於我們所提出的密度準則，我們建立了一個自動化偵測的步驟。我們將摺痕網路描述為一個加權圖(weighted graph)，其中加權圖中的邊是揉皺紙張中的摺痕，而點(nodes)即是這些摺痕的交點。首先我們根據摺痕的強度(ridge response)來計算出點的位置以及邊的權重並以此建立圖。接著我們制定了一個圖形密度(graph density)的準則來評估偵測出來的摺痕網路。最後，藉由最大化圖形密度的準則，我們提出了一個邊連接(edge linking)方法來建立加權圖。我們的實驗結果也證明了結合圖形密度準則、點偵測方法以及邊連接方法可以有效的完成自動化摺痕網路偵測。

關鍵字

摺痕

並列摘要

Crumpled sheets of paper tend to exhibit specific and complex structure, which is usually described as ridge network by physicists. Existing literature has showed that it is difficult to automate ridge network detection in crumpled paper because of its complex structure. In this thesis, we attempt to develop an automatic detection process in terms of our proposed density criterion. We model the ridge network as a weighted graph, where the nodes indicate the intersections of ridges and the edges are the straightened ridges detected in crumpled paper. We construct the weighted graph by first detecting the nodes and then determining the edge weight using the ridge responses. Next, we formulate a graph density criterion to evaluate the detected ridge network. Finally, we propose an edge linking method to construct the graph by maximizing the proposed density criterion. Our experimental results show that, with the density criterion, our proposed node detection together with the edge line linking method could effectively automate the ridge network detection.

並列關鍵字

ridge network ； graph density

參考文獻

[2] C. A. Andresen and A. Hansen, “Ridge Network in Crumpled Paper,” Physical Review E, 2007.

[3] J. Canny, “A Computational Approach to Edge Detection,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-8, No, 6, November 1986.

[4] R. Laganiere and R. Elias, “The Detection of Junction Feature in Images,” ICASSP, 2004.

[5] J. Ohkubo and K. Tanaka, “Nonadditive Volume and Community Detection Problem in Complex Networks,” Journal of the Physical Society of Japan, Vol. 75, No. 11, November 2006.

[6] S. Berlemont and J. C. O. Marin, “Combining Local Filtering and Multiscale Analysis for Edge, Ridge, and Curvilinear Objects Detection,” IEEE Transactions on Image Processing, Vol. 19, No. 1, January 2010.