TWI512642B

TWI512642B - 快速圖形比對方法

Info

Publication number: TWI512642B
Application number: TW102102775A
Authority: TW
Inventors: Juangyu Wei
Original assignee: Delta Electronics Inc
Priority date: 2013-01-25
Filing date: 2013-01-25
Publication date: 2015-12-11
Also published as: US20140212052A1; US9165215B2; TW201430718A

Description

快速圖形比對方法

本發明是有關於一種快速圖形比對方法。

圖形比對技術是藉由一個相似度指標來判斷圖形間的相似程度，一般圖形比對技術是用兩張圖形來進行比對，一張為模板影像，另一張為待測影像，比對目地是找出圖形間的最佳對應關係。最常被使用的圖形比對技術為歸一化互相關（Normalized Cross Correlation，NCC），如下之關係式所示，其特點為對光線的變化不敏感，及擁有良好的抗雜訊干擾能力。

一般圖形比對的技術是用0度至360度的模板影像與待測影像進行比對，藉此算出待測影像中物體的傾斜角度，如第1圖所示，此種方式也稱為暴力法，不但費時且資料量又大。

由此可見，上述現有的圖形比對方式，顯然仍有待加以進一步改進。為了解決上述問題，相關領域莫不費盡心思來謀求解決之道，但長久以來一直未見適用的方式被發展完成。因此，如何能更快速地進行圖形比對，實屬當前重要研發課題之一，亦成爲當前相關領域需改進的目標。

因此，本發明之技術方案是在提供一種快速圖形比對方法，其採用了角度預測法來改善暴力法的缺點，角度預測法就是在圖形比對前先建立好一張角度表，圖形比對時，就可用查表的方式計算出待測影像中物體可能傾斜的角度，藉此減少需比對的角度，達到快速圖形比對的目地。

依據本發明一實施例，一種快速圖形比對方法包括下列步驟：（a）預先將一預定角度的模板影像與0~360度的模板影像進行比對以建立一角度預測表；（b）取得一待測影像，將待測影像與預定角度的模板影像進行比對以紀錄每一位置的相似度，並從角度預測表中找出與相似度對應的多組角度；（c）將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

再者，步驟（a）包括：將預定角度為0度的模板影像與0~360度的模板影像進行比對，以記錄比對結果；判斷是否於0~360度中之每一度均比對完成；當比對完成時，基於比對結果以建立角度預測表。

在步驟（b）中，待測影像於一位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於該數值，且步驟（c）包括：取出這多組角度的模板影像與待測影像在該位置上進行比對，當比對完整張待測影像時，輸出最大的相似度。

依據本發明另一實施例，一種快速圖形比對方法包括下列步驟：（a）將一預定角度的模板影像與0~360度的模板影像進行比對以建立一角度預測表；（b）取得一待測影像，並利用圓投影法找出模板影像所對應之物體在待測影像中的區域；（c）將待測影像中的區域與預定角度的模板影像進行比對以紀錄每一位置的相似度，並從角度預測表中找出與相似度對應的多組角度；（d）將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

在步驟（c）中，待測影像於一位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於該數值，且步驟（d）包括：取出這多組角度的模板影像與待測影像在該位置上進行比對，當比對完待測影像中的區域時，輸出最大的相似度。

依據本發明又一實施例，一種快速圖形比對方法包括下列步驟：（a）預先將一預定角度的模板影像與0~360度的模板影像進行比對以建立一角度預測表；（b）取得一待測影像，利用跳點法將待測影像與預定角度的模板影像進行比對以紀錄每一跳點位置的相似度，並從角度預測表中找出與相似度對應的多組角度；（c）將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

在步驟（b）中，待測影像於一跳點位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於該數值，且步驟（c）包括：取出這多組角度的模板影像與待測影像在該跳點位置上進行比對，當比對完整張待測影像時，輸出最大的相似度。

依據本發明再一實施例，一種圖形比對方法包括下列步驟：（a）將一預定角度的模板影像與0~360度的模板影像進行比對以建立一角度預測表；（b）取得一待測影像，並利用圓投影法找出模板影像所對應之物體在待測影像中的區域；（c）利用跳點法將待測影像中的區域與預定角度的模板影像進行比對以紀錄每一跳點位置的相似度，並從角度預測表中找出與相似度對應的多組角度；（d）將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

在步驟（c）中，待測影像於一跳點位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於數值，且步驟（d）包括：取出這多組角度的模板影像與待測影像在跳點位置上進行比對，當比對完待測影像中的區域時，輸出最大的相似度。

綜上所述，本發明之技術方案與現有技術相比具有明顯的優點和有益效果。藉由上述技術方案，可達到相當的技術進步，並具有産業上的廣泛利用價值，其至少具有下列優點：
1. 大幅的減少資料計算量；以及
2. 加快圖形比對的速度。

以下將以實施方式對上述之說明作詳細的描述，並對本發明之技術方案提供更進一步的解釋。

S111~S621．．．步驟

510．．．角度預測表

520．．．待測影像

530．．．模板影像

為讓本發明之上述和其他目的、特徵、優點與實施例能更明顯易懂，所附圖式之說明如下：
第1圖是一種習知圖形比對方法的流程圖；
第2圖是依照本發明一實施例之一種快速圖形比對方法中建立角度預測表的流程圖；
第3圖是依照本發明一實施例之一種角度預測表；
第4圖是依照本發明一實施例之一種使用角度預測表的流程圖；
第5圖為第4圖之方法的示意圖；
第6圖是依照本發明另一實施例之一種使用角度預測表的流程圖；
第7圖是依照本發明另一實施例之一種圓投影法的示意圖；
第8圖是依照本發明又一實施例之一種使用角度預測表的流程圖；以及
第9圖是依照本發明再一實施例之一種使用角度預測表的流程圖。

為了使本發明之敘述更加詳盡與完備，可參照所附之圖式及以下所述各種實施例，圖式中相同之號碼代表相同或相似之元件。另一方面，眾所週知的元件與步驟並未描述於實施例中，以避免對本發明造成不必要的限制。

本發明之技術方案是一種快速圖形比對方法，其可適用於測試機台，或是廣泛地運用在相關之技術環節。值得注意的是，本技術方案之圖形比對流程可以分成兩個階段，第1階段是建立角度預測表及計算圖形比對時會用到的相關參數（如第2～3圖所示），第2階段為使用角度預測表來加快圖形比對的速度（如第4～9圖所示）。

第2圖是依照本發明一實施例之一種圖形比對方法中建立角度預測表的流程圖。如第2圖所示，在正式比對待測影像之前，可預先將一預定角度（例如：0度）的模板影像與0~360度的模板影像進行比對以建立一角度預測表。應瞭解到，在本文中所提及的步驟，除特別敘明其順序者外，均可依實際需要調整其前後順序，甚至可同時或部分同時執行。

具體而言，於步驟S111，提供一預定角度為0度的模板影像。於步驟S112，將0度的模板影像與0~360度的模板影像進行比對，以於步驟S113中記錄比對結果。接著，於步驟S114，判斷是否於0~360度中之每一度均比對完成。當比對完成時，於步驟S115，基於比對結果以建立角度預測表；反之，當未比對完成時，則回到步驟S113。

第3圖是依照本發明一實施例之一種角度預測表。如第3圖所示，當角度愈接近0度或360時，代表模板影像偏轉的幅度愈少，因此相似度也愈逼近1。

在角度預測表被建立以後，即可利用角度預測表來進行快速圖形比對，參照第4圖，第4圖是依照本發明一實施例之一種使用角度預測表的流程圖。如第4圖所示，首先，於步驟S211，取得一待測影像，於步驟S212，將待測影像與預定角度（例如：0度）的模板影像進行比對，以於步驟S213中紀錄每一位置的相似度，並於步驟S214中使用角度預測表，進而於步驟S215，從角度預測表中找出與相似度對應的多組角度。然後，於步驟S216-S219，將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

具體而言，在步驟S214-S215中，待測影像於某一位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於該數值，且於步驟S216，基於這多組角度分別相應旋轉N度模板影像，於步驟S217取出這多組角度的模板影像與待測影像在該位置上進行比對，進而於步驟S218，判斷是否比對完整張待測影像。當比對完整張待測影像時，於步驟S219，輸出最大的相似度；反之，當未比對完整張待測影像時，於步驟S220，接續使用角度預測表來進行比對。

為了對上述第4圖的方法作更具體闡述，請參照第5圖。在圖形比對時，先將待測影像520與0度的模板影像530進行逐像素的比對，並紀錄每次比對的相似度，直到整張待測影像比對完畢，然後取出待測影像上每個位置的相似度並用查表的方式找出其對應的角度。舉例來說，待測影像520在位置（20,50）的相似度的數值為0.97，則需檢查角度預測表510中哪些角度的模板的相似度大於0.97，並取出這些角度（即，0度、1度、359度）的模板影像與待測影像在位置（20,50）上進行比對，接著依此方式比對完整張待測影像並取出最高的相似度當作總結果。

另一方面，本技術方案之使用角度預測表的方法可與圓投影法合併使用，如第6圖所示，首先，於步驟S311，取得一待測影像，並於步驟S312，利用圓投影法找出模板影像所對應之物體在待測影像中的區域（即，大概位置）。於步驟S313，將待測影像中的該區域與預定角度（例如：0度）的模板影像進行比對，以於步驟S314中紀錄每一位置的相似度，並於步驟S315中使用角度預測表，進而於步驟S316，從角度預測表中找出與相似度對應的多組角度。然後，於步驟S317-S320，將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

具體而言，在步驟S315-S316中，待測影像於某一位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於該數值，且於步驟S317，基於這多組角度分別相應旋轉N度模板影像，於步驟S318取出這多組角度的模板影像與待測影像在該位置上進行比對，進而於步驟S319，判斷是否比對完整張待測影像。當比對完整張待測影像時，於步驟S320，輸出最大的相似度當作結果；反之，當未比對完整張待測影像時，於步驟S321，接續使用角度預測表來進行比對。

為了對上述的圓投影法作更具體闡述，請參照第7圖。首先，於步驟S410，計算模板影像的半徑，接著，於步驟S420建立半徑表，即中心為0，而愈往外圍則半徑數增加。然後，於步驟S430，進行圓投影轉換，半徑1的像素為(170+30+100+180+110+190+50+120)/8=122.5，同理，半徑2的像素為101.6，半徑3的像素為109.375。藉此，二維的影像資訊可降階到一維環形空間，圓投影法將每個半徑內的像素取出來做歸一化互相關計算，因為不管目標物如何的旋轉，圓環上的灰階值並不會因為旋轉而改變過大，故可用此特性進行圖形比對以找到物體在待測影像中的大概位置。

另一方面，本技術方案之使用角度預測表的方法可與跳點法合併使用，如第8圖所示，首先，於步驟S511，取得一待測影像，於步驟S512，利用跳點法將待測影像與預定角度（例如：0度）的模板影像進行比對，以於步驟S513中紀錄每一跳點位置的相似度，並於步驟S514中使用角度預測表，進而於步驟S515，從角度預測表中找出與相似度對應的多組角度。然後，於步驟S516-S519，將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

具體而言，在步驟S514-S515中，待測影像於某一跳點位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於該數值，且於步驟S516，基於這多組角度分別相應旋轉N度模板影像，於步驟S517取出這多組角度的模板影像與待測影像在該跳點位置上進行比對，進而於步驟S518，判斷是否比對完整張待測影像。當比對完整張待測影像時，於步驟S519，輸出最大的相似度；反之，當未比對完整張待測影像時，於步驟S520，接續使用角度預測表來進行比對。

實作上，上述的跳點法可為三步搜尋法、鑽石搜尋法、隔行隔列跳點法或其他規律性的跳點方式。由於各種跳點法在不同的特定情況下才能擁有良好的執行效率，因此熟習此項技藝者應視當時需要彈性選擇之適合的跳點法。

另一方面，本技術方案之使用角度預測表的方法可與跳點法、圓投影法合併使用，如第9圖所示，首先，於步驟S611，取得一待測影像，並於步驟S612，利用圓投影法找出模板影像所對應之物體在待測影像中的區域（即，大概位置）。於步驟S613，利用跳點法將待測影像中的該區域與預定角度（例如：0度）的模板影像進行比對，以於步驟S614中紀錄每一跳點位置的相似度，並於步驟S615中使用角度預測表，進而於步驟S616，從角度預測表中找出與相似度對應的多組角度。然後，於步驟S617-S620，將這多組角度的模板影像逐一與待測影像進行比對以取出最大的相似度。

具體而言，在步驟S615-S616中，待測影像於某一跳點位置的相似度為一數值，角度預測表中這多組角度的模板影像的相似度係大於該數值，且於步驟S617，基於這多組角度分別相應旋轉N度模板影像，於步驟S618取出這多組角度的模板影像與待測影像在該跳點位置上進行比對，進而於步驟S619，判斷是否比對完整張待測影像。當比對完整張待測影像時，於步驟S620，輸出最大的相似度當作結果；反之，當未比對完整張待測影像時，於步驟S621，接續使用角度預測表來進行比對。

綜合以上，本技術方案的實驗數據如下表1、表2所示，表1為使用暴力法、跳點法、圓投影法、角度預測法進行圖形比對的速度之比較，由表1可知，本文方法（即，角度預測法）比跳點法及圓投影法可更有效的加快比對速度。此外，本文方法也可與跳點法、圓投影法合併或分開使用，如表2所示，方法1為本文方法與跳點法合併使用，方法2為本文方法與圓投影法合併使用，方法3為本文方法與跳點法、圓投影法合併使用，由表2可知，本文提出的方法加上跳點法、圓投影法可獲得較佳的比對效果。

表1. 演算法效能之比較

表2. 演算法合併使用之效能比較

實作上，如上所述之本文方法的具體實施方式可採用軟體、硬體與/或軔體來執行。舉例來說，若以執行速度及精確性為首要考量，則該等單元基本上可選用硬體與/或軔體為主；若以設計彈性為首要考量，則該等單元基本上可選用軟體為主；或者，該等單元可同時採用軟體、硬體及軔體協同作業。應瞭解到，以上所舉的這些例子並沒有所謂孰優孰劣之分，亦並非用以限制本發明，熟習此項技藝者當視當時需要，彈性選擇本方法的具體實施方式。

雖然本發明已以實施方式揭露如上，然其並非用以限定本發明，任何熟習此技藝者，在不脫離本發明之精神和範圍內，當可作各種之更動與潤飾，因此本發明之保護範圍當視後附之申請專利範圍所界定者為準。

S111~S115．．．步驟

Claims

一種快速圖形比對方法，包括：
（a）預先將一預定角度的模板影像與0~360度的該模板影像進行比對以建立一角度預測表；
（b）取得一待測影像，將該待測影像與該預定角度的模板影像進行比對以紀錄每一位置的相似度，並從該角度預測表中找出與該相似度對應的多組角度；以及
（c）將該多組角度的該模板影像逐一與該待測影像進行比對以取出最大的相似度。
如請求項1所述之快速圖形比對方法，其中步驟（a）包括：
將該預定角度為0度的該模板影像與0~360度的該模板影像進行比對，以記錄比對結果；
判斷是否於0~360度中之每一度均比對完成；以及
當比對完成時，基於該比對結果以建立該角度預測表。
如請求項1所述之快速圖形比對方法，其中該待測影像於一位置的相似度為一數值，該角度預測表中該多組角度的模板影像的相似度係大於該數值，且步驟（c）包括：取出該多組角度的模板影像與該待測影像在該位置上進行比對，當比對完整張該待測影像時，輸出該最大的相似度。
一種快速圖形比對方法，包括：
（a）將一預定角度的模板影像與0~360度的該模板影像進行比對以建立一角度預測表；
（b）取得一待測影像，並利用圓投影法找出該模板影像所對應之物體在該待測影像中的區域；
（c）將該待測影像中的該區域與該預定角度的模板影像進行比對以紀錄每一位置的相似度，並從該角度預測表中找出與該相似度對應的多組角度；以及
（d）將該多組角度的該模板影像逐一與該待測影像進行比對以取出最大的相似度。
如請求項4所述之快速圖形比對方法，其中步驟（a）包括：
將該預定角度為0度的該模板影像與0~360度的該模板影像進行比對，以記錄比對結果；
判斷是否於0~360度中之每一度均比對完成；以及
當比對完成時，基於該比對結果以建立該角度預測表。
如請求項4所述之快速圖形比對方法，其中該待測影像於一位置的相似度為一數值，該角度預測表中該多組角度的模板影像的相似度係大於該數值，且步驟（d）包括：取出該多組角度的模板影像與該待測影像在該位置上進行比對，當比對完該待測影像中的該區域時，輸出該最大的相似度。
一種快速圖形比對方法，包括：
（a）預先將一預定角度的模板影像與0~360度的該模板影像進行比對以建立一角度預測表；
（b）取得一待測影像，利用跳點法將該待測影像與該預定角度的模板影像進行比對以紀錄每一跳點位置的相似度，並從該角度預測表中找出與該相似度對應的多組角度；以及
（c）將該多組角度的該模板影像逐一與該待測影像進行比對以取出最大的相似度。
如請求項7所述之快速圖形比對方法，其中步驟（a）包括：
將該預定角度為0度的該模板影像與0~360度的該模板影像進行比對，以記錄比對結果；
判斷是否於0~360度中之每一度均比對完成；以及
當比對完成時，基於該比對結果以建立該角度預測表。
如請求項7所述之快速圖形比對方法，其中該待測影像於一跳點位置的相似度為一數值，該角度預測表中該多組角度的模板影像的相似度係大於該數值，且步驟（c）包括：取出該多組角度的模板影像與該待測影像在該跳點位置上進行比對，當比對完整張該待測影像時，輸出該最大的相似度。
一種快速圖形比對方法，包括：
（a）將一預定角度的模板影像與0~360度的該模板影像進行比對以建立一角度預測表；
（b）取得一待測影像，並利用圓投影法找出該模板影像所對應之物體在該待測影像中的區域；
（c）利用跳點法將該待測影像中的該區域與該預定角度的模板影像進行比對以紀錄每一跳點位置的相似度，並從該角度預測表中找出與該相似度對應的多組角度；以及
（d）將該多組角度的該模板影像逐一與該待測影像進行比對以取出最大的相似度。
如請求項10所述之快速圖形比對方法，其中步驟（a）包括：
將該預定角度為0度的該模板影像與0~360度的該模板影像進行比對，以記錄比對結果；
判斷是否於0~360度中之每一度均比對完成；以及
當比對完成時，基於該比對結果以建立該角度預測表。
如請求項10所述之快速圖形比對方法，其中該待測影像於一跳點位置的相似度為一數值，該角度預測表中該多組角度的模板影像的相似度係大於該數值，且步驟（d）包括：取出該多組角度的模板影像與該待測影像在該跳點位置上進行比對，當比對完該待測影像中的該區域時，輸出該最大的相似度。