一種多點觸摸跟蹤識別方法及其系統的製作方法
2023-07-11 10:59:31
專利名稱：一種多點觸摸跟蹤識別方法及其系統的製作方法
技術領域：
本發明涉及觸摸控制技術領域，尤其涉及一種多點觸摸跟蹤識別方法及其系統。
背景技術：
隨著觸摸控制產品的廣泛應用，觸摸控制技術已成為當今人機互動中的熱點技術。許多產品的控制都逐步被觸摸控制技術所代替，同時觸摸控制技術也在不斷挑戰新的應用環境和領域。在基於光學圖像的觸摸控制應用環境中，通常用戶希望機器能支持更多觸摸點操作以滿足不同應用需求，同時也希望機器能更加智能地理解用戶意圖，進而為用戶提供更加自然、智能的服務。在目前的觸摸控制系統中，機器通過分析用戶在觸控螢幕上移動的軌跡來判斷用戶欲執行的操作，所以機器正確地撲捉、跟蹤到觸控的軌跡就非常重要。通常，只有單點在觸控螢幕上移動時，機器通過關聯光學圖像前後幀之間的亮點就能得到正確觸摸點移動的軌跡，但隨著觸摸點數增加，該方法就不能識別前後幀的多個觸摸點之間的關係，無法分別得到各觸摸點的正確軌跡，所以需要開發更加魯棒、準確的多點跟蹤識別方法，為機器智能決策提供正確的軌跡。在目前的多點跟蹤識別方法中，主要採用兩種方法一是針對光學圖像前一幀中所有觸摸點，在後一幀中搜索歐式距離最為接近的觸摸點進行關聯。該方法簡單、實時性非常好，且目前該算法有多種改進版本，但是該方法仍無法避免歐式距離最近即為最優關聯這一錯誤認識的本質缺陷；另一方法是採用K近鄰算法，該方法為前一幀中每個觸摸點在後一幀中搜索K個歐式距離最小的觸摸點，並依距離值進行排序，然後對前一幀中每一個觸摸點關聯距離最小的觸摸點，若後一幀中某觸摸點處於前一幀中多個觸摸點的K近鄰中，則採用「最小距離通吃」的思想優先匹配，該算法實時性很好，跟蹤精度較前者好，但仍是一種局部最優方法，沒有從整體上考慮最優關聯，即仍沒有從全局角度給出評判當前關聯方式是否為最優。
發明內容
針對以上現有技術多點觸摸跟蹤的缺點，本發明要解決的技術問題在於提供一種從全局角度分析的多點觸摸跟蹤識別方法。給出了全局評判方式，可判斷當前關聯是否為最優關聯。一種多點觸摸跟蹤識別方法，包括獲取相鄰兩幀圖像中的觸摸點位置；根據所述觸摸點位置，計算前後兩幀圖像的各個所述觸摸點之間的距離；按照所述觸摸點距離從小到大的順序，逐次搜索前後兩幀圖像的觸摸點的關聯方式；分別計算每次搜索到的關聯方式的觸摸點離散度，直到後一關聯方式的觸摸點離散度首次大於前一關聯方式的觸摸點離散度，則判斷所述前一關聯方式為最優關聯方式。
本發明要解決的技術問題還在於提供一種從全局角度分析的多點觸摸跟蹤識別系統。一種多點觸摸跟蹤識別系統，包括用於獲取相鄰兩幀圖像中的觸摸點位置的觸摸點檢測模塊；用於根據所述觸摸點位置，計算前後兩幀圖像的各個所述觸摸點之間距離的距離計算模塊；用於按照所述觸摸點距離從小到大的順序，逐次搜索前後兩幀圖像的觸摸點的關聯方式的搜索模塊；用於分別計算每次搜索到的關聯方式的觸摸點離散度，直到後一關聯方式的觸摸點離散度首次大於前一關聯方式的觸摸點離散度時，判斷所述前一關聯方式為最優關聯方式的離散度計算模塊。與現有技術相比較，本發明的多點觸摸跟蹤識別方法及其系統，通過計算每個所述關聯方式中所有互相關聯的觸摸點的最小觸摸點距離，以及每個所述關聯方式下的觸摸點離散度，保證了前後幀中觸摸點關聯的準確性和魯棒性。本發明採用觸摸點距離最小的思想保證相鄰兩幀中觸摸點關聯的魯棒性，採用關聯離散度的測度準則保證相鄰兩幀間觸摸點關聯的準確性，該準則進一步從數學上驗證了觸摸點距離最小這一關聯思想的正確性。本發明的多點觸摸跟蹤識別方法及其系統能實時、準確和穩定地運行在目前的各種觸摸交互設備中。
圖1是本發明多點觸摸跟蹤識別方法的流程圖2是連續兩幀圖像的觸摸點的示意圖3是連續兩幀圖像的觸摸點表示在同一平面內的示意圖4、圖5是本發明中建立的搜索樹的結構示意圖6是經過篩選後的搜索樹的結構示意圖7是現有技術一種觸控螢幕的結構示意圖8是實施例中連續兩幀中的觸摸點示意圖9是實施例中連續兩幀圖像的觸摸點表示在同一平面內的示意圖10是實施例中建立的搜索樹的結構示意圖11是實施例中經過篩選後的搜索樹的結構示意圖12是實施例中第一次搜索結果的關聯方式的示意圖13是實施例中第二次搜索結果的關聯方式的示意圖14是實施例中的最優關聯方式的示意圖15是本發明多點觸摸跟蹤識別系統的結構示意圖16是本發明多點觸摸跟蹤識別系統一種優選實施方式的結構示意圖17是本發明多點觸摸跟蹤識別系統另一種優選實施方式的結構示意圖
具體實施例方式
請參閱圖1，圖1是本發明多點觸摸跟蹤識別方法的流程圖。
所述多點觸摸跟蹤識別方法包括以下步驟步驟S101，分別獲取相鄰兩幀圖像中的觸摸點位置；首先可檢測連續相鄰的兩幀中觸摸點個數，例如利用圖像檢測技術檢測，以及其位置，每一觸摸點稱為一節點，設連續兩幀表示為Ft與Ft+1，設Ft中有N1個節點，Ft+1幀中有N2個節點，且N1 >隊，如圖2所示。圖3則是連續兩幀的觸摸點表示在同一平面內的示意圖。步驟S102，根據所述觸摸點位置，計算前後兩幀圖像的各個所述觸摸點之間的距 1 ；在本步驟中，分別計算第一幀圖像的各個觸摸點和第二幀圖像的各個觸摸點之間的距離。如圖3所示，分別計算觸摸點1、2、3、4到觸摸點5、6和7的距離。在一個優選實施方式中，為方便分析搜索和跟蹤識別，在本步驟中，進一步執行以下步驟分別以兩幀圖像中的各個觸摸點為基礎構造兩層的搜索樹，將所述搜索樹第一層的各個觸摸點與第二層的各個觸摸點之間設為實關聯。則計算前後兩幀圖像的各個所述觸摸點之間的距離亦即計算所述搜索樹中的各個實關聯的距離。所述關聯即為兩幀圖像之間的觸摸點跟蹤識別的對應關係，例如，在圖1中，第一幀中的觸摸點1可能在第二幀中移動到觸摸點5、6或者7的位置，而觸摸點2，3和4也有可能移動到觸摸點5、6或者7的位置。因此，分別將所述第一幀中的觸摸點與第二幀中的各個觸摸點進行實關聯，標記其可能存在對應關係。作為一種優選實施方式，因為兩幀圖像中的觸摸點數不一定相同，因此，為了讓所有的關聯採用相同的數據結構，方便計算，在構造所述搜索樹時，進一步在所述搜索樹的第二層中設置與第一層的觸摸點一一對應的虛節點，並設所述虛節點與第一層的觸摸點的距離為0，將各個所述虛節點與所述第一層的各個觸摸點之間設為虛關聯；此時，如果判斷所述搜索樹的兩層之間只有虛關聯，則代表所述搜索樹的其中一層沒有觸摸點，因此可以提前結束多點觸摸跟蹤識別的操作。通過設置虛節點可以讓所有的關聯採用相同的數據結構。如圖4、圖5所示。假設第一層中的某節點(即觸摸點)a在其作用範圍中存在可實關聯的第二層節點b，但節點b優先被第一層中其它節點c關聯，在此情況下，節點a不能與節點b進行關聯，若此時節點a的作用範圍中不存在其它可實關聯的第二層節點，則節點a應不與任何第二層節點實關聯。所以，在這裡通過虛節點設置一虛關聯，且虛關聯的關聯距離設為0。再進一步地，因為需要在搜索樹的第二層中設置所述虛節點，為減少運算的數據量，在構造所述搜索樹時，首先選取相鄰兩幀圖像中觸摸點數較多的為第一層，如圖4所示；然後，以另一幀(即觸摸點數較少的一幀)為第二層進一步構造所述搜索樹，如圖5所示。這樣在增加虛節點時，只在觸摸點數較少的一層中增加，所述搜索樹兩層之間的總的關聯數量較少，因此可以減少運算的數據量。作為另一種優選實施方式，為進一步減少運算的數據量，在對所述搜索樹第一層的各個觸摸點與第二層的各個觸摸點之間進行實關聯之後，可進一步執行以下步驟分別將所述搜索樹第一層與第二層的之間的各個實關聯的距離與預設的距離閾值比較，根據比較結果對各個所述實關聯進行篩選。
具體地，所述距離閾值可以包括最大距離閾值；則，根據比較結果對各個所述實關聯進行篩選的步驟包括如果判斷所述實關聯的距離值小於所述最大距離閾值，則判斷對應的兩個觸摸點之間的實關聯合法；如果判斷所述實關聯的距離值大於所述最大距離閾值，則判斷對應的兩個觸摸點之間的實關聯不合法；經過篩選後的搜索樹的結構如圖6所示。一旦某個關聯方式中包括有上述被判斷為不合法的實關聯，則所述關聯方式也被排除，不需要再考慮，這樣就能夠進一步減少分析的關聯方式的數量，無需分析所有的關聯方式，加快了跟蹤定位的速度。進一步地，所述距離閾值還可以包括最小距離閾值；則，根據比較結果對各個所述實關聯進行篩選的步驟還包括如果判斷所述實關聯的距離值小於所述最小距離閾值，則進一步將對應的兩個觸摸點之間的實關聯劃分為最優實關聯。可以認為，當分屬兩層的兩個觸摸點之間的距離很小(小於所述最小距離閾值) 時，可以直接將兩個觸摸點判斷為同一個觸摸物在前後兩幀圖像中的觸摸點，因此判斷其為最優實關聯，所述最優實關聯即為肯定會出現在最優關聯方式中的實關聯。步驟S103，按照所述觸摸點距離從小到大的順序，逐次搜索前後兩幀圖像的觸摸點的關聯方式；前後兩幀圖像的各個所述觸摸點之間的距離即是上述步驟中建立的所述搜索樹的兩層之間的實關聯的距離。各種所述關聯方式由各個所述實關聯按照各種可能的方式互相匹配組合而成。因為，兩幀圖像中的觸摸點數不一定相同，例如第一幀中有四個觸摸點，而在第二幀中可能只有三個觸摸點，因此，搜索前後兩幀圖像的觸摸點的關聯方式時，應該按照前後兩幀圖像的觸摸點數進行適當搜索。為此，在本實施方式中，首先可按照各個所述實關聯的距離從小到大的順序，設定各個關聯方式的第一個實關聯。然後按照以下搜索條件，搜索各個所述關聯方式包含的其他實關聯1.在每一關聯方式下搜索的後一實關聯的距離大於前一實關聯的距離；2.在每一關聯方式中，一個觸摸點只對應一個實關聯；3.每一所述關聯方式所包含的實關聯個數都不超過前後兩幀的觸摸點個數中最小的一個。根據每一關聯方式的第一個實關聯，以及上述搜索條件，搜索各個所述關聯方式包含的其他實關聯，將所述第一個實關聯和其他實關聯組合成所述觸摸點的一種關聯方式。分別將各個所述實關聯以不同的方式組合，因此， 以這種方式可以搜索出所有匹配的關聯方式。搜索每一關聯方式的具體方法為首先按照各個所述實關聯的距離從小到大的順序依次設定各個關聯方式的第一個實關聯；然後再按照各個所述實關聯的距離由小到大的順序，依次搜索每一所述關聯方式的下一個實關聯；並判斷搜索到的所述實關聯的觸摸點是否已經與其他觸摸點關聯，如果是，則放棄搜索到的實關聯；否則，保存對應的實關聯；
從搜索每一所述關聯方式的第一個實關聯開始，判斷搜索到的實關聯個數是否等於前後兩幀的觸摸點個數中最小的一個，是則停止搜索，保存對應的關聯方式；否則，繼續搜索所述關聯方式的下一實關聯。在本發明中，每搜索出一個關聯方式，就執行一次步驟S104，計算所述關聯方式對應的觸摸點離散度，根據所述觸摸點離散度判斷是否得到最優關聯方式。如果判斷獲得最優關聯方式，則無需繼續計算所有匹配的關聯方式。由於兩幀圖像中的觸摸點數不一定相同，在每種匹配的關聯方式中，當確定所述關聯方式中的所有實關聯之後，將不涉及實關聯的其餘觸摸點都與虛節點設為虛關聯。對應虛關聯的觸摸點為後一幀圖像新增或者減少的觸摸點。作為一種優選實施方式，如果在步驟S102中設定所述最小距離閾值對各個實關聯進行篩選，則在本步驟中，可採用以下方式將篩選結果中包含的實關聯組合成所有匹配的關聯方式如果沒有搜索到所述最優實關聯，則將各個合法的實關聯互相匹配，搜索出前後兩幀圖像的觸摸點的各種關聯方式；如果搜索到所述最優實關聯，則將所述最優實關聯與其餘合法的實關聯互相匹配，搜索出前後兩幀圖像的觸摸點的各種關聯方式。上述步驟可以進一步對兩幀圖像中的觸摸點的關聯方式組合進行篩選。通過篩選可以減少分析的匹配的關聯方式的數量，縮小跟蹤搜索範圍，加快處理速度。步驟S104，分別計算每次搜索到的關聯方式的觸摸點離散度，直到後一關聯方式的觸摸點離散度首次大於前一關聯方式的觸摸點離散度，則判斷所述前一關聯方式為最優關聯方式。所述最優關聯方式即為本發明多點觸摸跟蹤識別系統的跟蹤識別結果，亦即為兩幀圖像之間的觸摸點跟蹤識別確認的最終的對應關係，可根據所述最優關聯方式得到觸摸點的移動方式，增加或者減少觸摸點，從而判斷用戶的觸摸操作，例如觸摸點滑動，在新的觸摸位置進行觸摸操作等，從而可以執行各種相關的觸摸控制操作。所述觸摸點離散度用於表徵每種關聯方式下，各個觸摸點之間的位置是否集中， 或者是平均距離的大小。在本實施方式中，將每個所述關聯方式的觸摸點離散度按照以下公式定義為
1 NP^-Yidl-Ciave kf
7 V i=\
1 N其中，d·. =—Σ<·
7V i=\dave_k為Cli平均值，N為所述關聯方式中實關聯的個數，Cli為所述關聯方式的中前後兩幀的互相關聯的觸摸點的距離。由於每次搜索均按照所述觸摸點距離從小到大的順序設定對應關聯方式的第一個實關聯，亦即，後一次搜索的關聯方式的第一個實關聯的距離大於前一次搜索的關聯方式的第一個實關聯的距離；而在單獨一個關聯方式中，在確定所述第一個實關聯之後，之後搜索的每個實關聯都大於前一個實關聯。因此，如果本次關聯方式的觸摸點離散度小於前一關聯方式的觸摸點離散度，則表明還未找到最優關聯方式，需繼續搜索，亦即繼續根據觸摸點的距離從小到大的順序，繼續搜索並計算下一關聯方式的觸摸點離散度，並與其前一關聯方式的觸摸點離散度比較； 如果後一關聯方式的觸摸點離散度首次大於前一關聯方式的觸摸點離散度，則判斷所述前一關聯方式為最優關聯方式，搜索結束。 下面結合具體的實施例對本發明的多點觸摸跟蹤識別方法加以詳細說明，應指出的是，所描述的實施例旨在便於對本發明的理解，對本發明不起限定作用。圖7為一觸控螢幕，圖8給出了連續兩幀中的觸摸點示意圖，圖9是實施例中連續兩幀圖像的觸摸點表示在同一平面內的示意圖。假設在t幀中有2個觸摸點，在t+Ι幀中有 4個觸摸點，則根據步驟S102，計算前後兩幀圖像的各個所述觸摸點之間的距離之後，根據算法構建搜索樹如圖10所示，t+Ι幀為第一層，t幀為第二層。圖10中實線表示兩節點進行實關聯；虛線連接表示第一層的該節點(亦即觸摸點)與虛節點關聯，並設置該虛關聯距離為0。如果不設置距離閾值對所述搜索樹包含的各個實關聯進行篩選，則直接在所述搜索樹中搜索各種可能的關聯方式。如果設置大、小距離閾值，則先對搜索樹進行剪枝，以減小搜索空間，提高搜索速率，剪枝後的搜索樹如圖11。其中最大距離閾值設為dmax = 110，最小距離閾值設為dmin = 30(本實施例中的距離只以數值表示，具體的單位根據用戶設定而定)。根據步驟S103進行最優搜索，搜索前首先判斷是否只存在虛關聯，以判斷是否需要繼續搜索。很明顯，在本實施例中前後兩層之間存在實關聯。則首先搜索到最小實關聯距離，本實施例中為節點5與節點2的距離最小d52 = 76，在搜索程序運行時可初始化一計數器C = 0，若第一層中有節點關聯到實節點，則該計數器加1。因為本實施例中第一層有4 個節點，因此需要循環對第一層搜索，直至該層所有節點都關聯為止，又因本實施例中t幀中只有2個節點，所以根據搜索條件3，在所有關聯方式中，至多只能有兩個實關聯距離，也就是說，第一層中至少有兩個節點與虛節點進行關聯。繼續進行搜索，可搜索到節點4與節點1的關聯距離d41 = 82為第一次搜索的關聯方式的次小實關聯距離，此時計數器C = 2，與t幀中節點個數相等，表明在接下來的搜索中，第一層中還未關聯的節點，都必須與虛節點進行關聯。本次搜索結果的關聯方式示意圖示於圖12。根據步驟S104計算觸摸點離散度
權利要求
1.一種多點觸摸跟蹤識別方法，其特徵在於，包括以下步驟獲取相鄰兩幀圖像中的觸摸點位置；根據所述觸摸點位置，計算前後兩幀圖像的各個所述觸摸點之間的距離；按照所述觸摸點距離從小到大的順序，逐次搜索前後兩幀圖像的觸摸點的關聯方式；分別計算每次搜索到的關聯方式的觸摸點離散度，直到後一關聯方式的觸摸點離散度首次大於前一關聯方式的觸摸點離散度時，判斷所述前一關聯方式為最優關聯方式。
2.如權利要求1所述的多點觸摸跟蹤識別方法，其特徵在於，所述計算前後兩幀圖像的各個所述觸摸點之間的距離的步驟包括分別以兩幀圖像中的各個觸摸點為基礎構造兩層的搜索樹，將所述搜索樹第一層的各個觸摸點與第二層的各個觸摸點之間設為實關聯；根據所述觸摸點位置，計算所述搜索樹中的各個實關聯的距離。
3.如權利要求2所述的多點觸摸跟蹤識別方法，其特徵在於，所述構造兩層的搜索樹的步驟包括進一步在所述搜索樹的第二層中設置與第一層的觸摸點一一對應的虛節點，並設所述虛節點與第一層的觸摸點的距離為0，將各個所述虛節點與所述第一層的各個觸摸點之間設為虛關聯；判斷所述搜索樹的兩層之間是否只有虛關聯，是則結束跟蹤識別操作。
4.如權利要求3所述的多點觸摸跟蹤識別方法，其特徵在於，以兩幀圖像中觸摸點數目較多的為第一層，另一幀為第二層構造所述搜索樹。
5.如權利要求1至4中任意一項所述的多點觸摸跟蹤識別方法，其特徵在於，所述逐次搜索前後兩幀圖像的觸摸點的關聯方式的步驟包括按照各個所述實關聯的距離從小到大的順序依次設定各個關聯方式的第一個實關聯；再按照各個所述實關聯的距離由小到大的順序，依次搜索每一所述關聯方式的下一個實關聯；判斷搜索到的所述實關聯的觸摸點是否已經與其他觸摸點關聯，如果是，則放棄搜索到的實關聯；否則，保存對應的實關聯；從搜索每一所述關聯方式的第一個實關聯開始，判斷搜索到的實關聯個數是否等於前後兩幀的觸摸點個數中最小的一個，是則停止搜索，保存對應的關聯方式；否則，繼續搜索所述關聯方式的下一實關聯。
6.一種多點觸摸跟蹤識別系統，其特徵在於，包括用於獲取相鄰兩幀圖像中的觸摸點位置的觸摸點檢測模塊；用於根據所述觸摸點位置，計算前後兩幀圖像的各個所述觸摸點之間距離的距離計算模塊；用於按照所述觸摸點距離從小到大的順序，逐次搜索前後兩幀圖像的觸摸點的關聯方式的搜索模塊；用於分別計算每次搜索到的關聯方式的觸摸點離散度，直到後一關聯方式的觸摸點離散度首次大於前一關聯方式的觸摸點離散度時，判斷所述前一關聯方式為最優關聯方式的離散度計算模塊。
7.如權利要求6所述的多點觸摸跟蹤識別系統，其特徵在於，所述多點觸摸跟蹤識別系統進一步包括用於分別以兩幀圖像中的各個觸摸點為基礎構造兩層搜索樹的搜索樹模塊，其中，所述搜索樹第一層的各個觸摸點與第二層的各個觸摸點之間設為實關聯；所述搜索模塊在所述搜索樹模塊建立的搜索樹中搜索各個所述實關聯，並根據搜索的所述實關聯組合成各個關聯方式。
8.如權利要求7所述的多點觸摸跟蹤識別系統，其特徵在於，所述搜索樹模塊進一步在所述搜索樹的第二層中設置與第一層的觸摸點一一對應的虛節點，並設所述虛節點與第一層的觸摸點的距離為0，將各個所述虛節點與所述第一層的各個觸摸點之間設為虛關聯； 並且，所述搜索樹模塊在判斷所述搜索樹的兩層之間只有虛關聯時，結束跟蹤識別操作。
9.如權利要求8所述的多點觸摸跟蹤識別系統，其特徵在於，所述搜索樹模塊以兩幀圖像中觸摸點數目較多的為第一層，另一幀為第二層構造所述搜索樹。
10.如權利要求6至9中任意一項所述的多點觸摸跟蹤識別系統，其特徵在於，所述搜索模塊在搜索前後兩幀圖像的觸摸點的關聯方式時，首先按照各個所述實關聯的距離從小到大的順序依次設定各個關聯方式的第一個實關聯；然後再按照各個所述實關聯的距離由小到大的順序，依次搜索每一所述關聯方式的下一個實關聯；並且，判斷搜索到的所述實關聯的觸摸點是否已經與其他觸摸點關聯，如果是，則放棄搜索到的實關聯；否則，保存對應的實關聯；所述搜索模塊從搜索每一所述關聯方式的第一個實關聯開始，判斷搜索到的實關聯個數是否等於前後兩幀的觸摸點個數中最小的一個，是則停止搜索，保存對應的關聯方式；否則，繼續搜索所述關聯方式的下一實關聯。
全文摘要
本發明提供一種多點觸摸跟蹤識別方法及其系統，所述方法包括分別獲取相鄰兩幀圖像中的觸摸點位置；根據所述觸摸點位置，計算前後兩幀圖像的各個所述觸摸點之間的距離；按照所述觸摸點距離從小到大的順序，逐次搜索前後兩幀圖像的觸摸點的關聯方式；分別計算每次搜索到的關聯方式的觸摸點離散度，直到後一關聯方式的觸摸點離散度首次大於前一關聯方式的觸摸點離散度，則判斷所述前一關聯方式為最優關聯方式。本發明提供的多點觸摸跟蹤識別方法。從全局出發分析，通過計算每個所述關聯方式中所有互相關聯的觸摸點的最小觸摸點距離，以及每個所述關聯方式下的觸摸點離散度，保證了前後幀中觸摸點關聯的準確性和魯棒性。
文檔編號G06F3/042GK102193689SQ20111012981
公開日2011年9月21日 申請日期2011年5月18日 優先權日2011年5月18日
發明者孫敬飛, 廖微, 肖平, 韋金汝, 駱威 申請人:廣東威創視訊科技股份有限公司