屬性化超圖之匹配技術在智慧型運輸系統之應用

Attributed Hyper-Graph Matching in ITS Applications

王俊明(Jung-Ming Wang)

指導教授 ： 傅楸善

共同指導教授 ： 陳世旺(Sei-Wang Chen)

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2013年)

https://doi.org/10.6342/NTU.2013.03091

摘要

在電腦視覺的研究領域中，我們常常需要匹配兩組不同的特徵點，建立它們之間的對應關係。比較常見的作法是：先計算每一特徵點的屬性值，再從每一組中各挑選一特徵點，計算兩者之間的相似程度值；當兩特徵點有極高的相似程度值時，就可以將它們配對在一起。這種配對問題在過去已經有二部圖匹配(bipartite matching)的方法，且被證明可以在多項式時間內被解決。
在進行二部圖匹配時，若同時也要考慮同一組特徵點之間的關係時，這種配對方式被稱為二次分配問題(quadratic assignment problem)。二次分配問題已被證明是無法在多項式時間內解決，因此，在過去的研究中已經提出許多方法來求近似解或特殊狀況解。圖匹配(graph matching)是相當常見用來解決二次分配問題的方法，在這種方法中，可以將每一特徵點視為圖的節點，兩特徵點之間的關係則視為圖的邊；接著，為每一節點及邊給予屬性值，就可以利用屬性值之間的相似程度進行圖匹配。
若要同時考慮同一組特徵點三者以上之間的關係時，便可以使用超圖(hyper-graph)來表示。超圖的一邊（稱為超邊）可以連接任意數量的節點，因此可以為超邊給予多元關係的屬性值。為每組特徵點建立超圖後，利用超圖匹配(hyper-graph matching)就可以達到上述的配對要求。超圖匹配在過去的研究中相當少見，除了表示上較為複雜，過去針對圖匹配所提出來的計算方法，很難直接延伸供超圖匹配使用。
為每一節點及超邊給予多種屬性值，再進行超圖匹配時，就得同時考慮不同屬性所計算出來的不同匹配結果。結合不同的匹配結果以決定特徵點匹配，就成為我們所提出的屬性化超圖匹配(attributed hyper-graph matching)。過去有針對屬性化圖匹配的研究，卻沒有屬性化超圖匹配的相關研究。就像圖匹配的方法無法直接延伸供超圖匹配使用，屬性化圖匹配的方法，亦無法直接延伸供屬性化超圖匹配使用。
在本論文中，提出一種快速有效的屬性化超圖匹配方法。主要是將各屬性值的機率分佈函數轉換至希爾伯特空間(Hilbert space)表示，使不同的屬性得以在同一種表示下進行統整結合。我們亦將此方法應用於一些智慧型運輸系統中，包括停車場空間表示、道路車輛追蹤、及攝影機畫面穩定以驗證其實用性。各應用皆有其所需挑戰的問題：在停車場空間表示中，必須處理兩組特徵點中只有少部份可供配對的問題。在道路車輛追蹤中，必須面對同一組特徵點彼此之間沒有什麼差異性的問題。最後，攝影機畫面穩定的應用中，特徵點的屬性會有相當大的變異，使得不易找到穩定的屬性供匹配。即使如此，本方法都可以得到很好的處理結果。

關鍵字

電腦視覺 ； 配對問題 ； 超圖匹配 ； 智慧型運輸系統

並列摘要

Matching two sets of feature points plays an important role in computer vision tasks. This matching can be achieved by comparing the feature values of the points. Graph matching techniques have been developed to match feature points in different sets and consider the binary relationships between points in the same set. If we consider a matching that preserves high-order relationships among points in the same set, we can introduce a hypergraph matching technique to search for correspondence according to high-order feature values. While graph matching has been widely studied, there is limited research available regarding hypergraph matching.
In this study, we formulate hypergraph matching in terms of tensors. A high-order feature is transformed and used as one of the features of a point. Then, we can reduce the hypergraph matching to a bipartite matching problem that can be solved in polynomial time. We then extend this hypergraph matching to attributed hypergraph matching (AHM) using a combination of different attributes with different orders. We perform analyses that demonstrate that this method is robust when handling noisy or missing data and can achieve inexact graph matching. To the best of our knowledge, while attributed graph matching has been heavily researched, methods for attributed hypergraph matching have not been proposed before.
We apply AHM to Intelligent Transportation System applications (ITS). In these applications, one or more cameras are mounted to monitor a traffic scene. Extracting information from the resulting video sequence may require matching techniques. Matching would be applied to obtain the correspondence between two sets of feature points, which may be extracted from two images captured from different cameras or image frames of one camera. As we may not have a priori knowledge of the distortion between the two sets of points, our AHM algorithm provides a robust scheme that can tolerate variance.
Several applications of ITS are designed to show the applicability of the proposed hypergraph matching technique. In representation of a parking lot, only part of feature points in two sets can correspond to each other, where we require the robustness to missing data in matching. In vehicle tracking, it may suffer from the problem of high degree of indiscernibility between objects. We believe that using high-order feature may increase the discernibility degree. In video stabilization, feature points are shifted because of camera motion, where we need the attributes invariant to translation, rotation, and scaling.

並列關鍵字

Computer vision ； Assignment problem ； Hypergraph matching ； Hilbert space

參考文獻

[1.1] C. H. Papadimitriou, Computational Complexity. Addison-Wesley, 1995.

[1.3] D. conte, P. Foggia, C. Sansone, and M. Vento, “Thirty Years of Graph Matching in Pattern Recognition,” Int’l Journal of Pattern Recognition and Artificial Intelligence, vol. 18, no. 3, pp. 265-298, 2004.

[1.4] K. Riesen, X. Jiang and H. Bunke, “Exact and Inexact Graph Matching: Methodology and Applications,” Managing and Mining Graph Data, vol. 40, pp. 217-247, Springer 2010.

[1.5] L. P. Cordella, P. Foggia, C. Sansone, and M. Vento, “A (Sub)graph Isomorphism Algorithm for Matching Large Graphs,” IEEE Tans. On Pattern Analysis and Machine Intelligence, vol 26, no. 20, pp.1367-1372, 2004.

[1.6] D. M. Campbell and D. Radford, “Tree Isomorphism Algorithms: Speed vs. Clarity,” Mathematical Association of America, vol. 64, no. 4, pp. 252-261, 1991.