TWI423170B

TWI423170B - 多畫面中物體移動的追蹤方法

Info

Publication number: TWI423170B
Application number: TW99147315A
Authority: TW
Inventors: Shih Yuan Peng; Chung Ta Wu
Original assignee: Altek Corp
Priority date: 2010-12-31
Filing date: 2010-12-31
Publication date: 2014-01-11
Also published as: CN102568000A; TW201227616A; CN102568000B

Description

多畫面中物體移動的追蹤方法

本發明是有關於一種多畫面影像的處理方法，且特別是有關於一種多畫面物體移動的追蹤方法。

隨著科技不斷地進步，數位產品在人們的生活中也越來越普遍。為了方便記錄生活點點滴滴，手機、數位相機以及數位攝影機等等往往都具有拍攝靜態照片或是動態影片的功能。舉例來說，這些電子產品內部會配置有電荷耦合元件(Charge-coupled Device，CCD)或是互補式金屬-氧化層-半導體(Complementary Metal-Oxide-Semiconductor，CMOS)等感光元件。

在以CMOS感光元件為基礎的數位相機或是數位攝影機中，影像的下載時間(download time)會比較短，使得畫面更新率(frame rate)也比較高。

在傳統，以區塊匹配(block matching)為基礎的移動計算方法或是無考慮前一畫面移動偵測結果的演算法需要的運算資源相較龐大且耗時，在高解析度及高畫面需求下的應用將不敷使用。

以完全搜尋(full search)式的移動比對來說，為了要計算兩畫面間物體的移動關係，必須把兩畫面的所有位置都找一遍，再根據最為匹配的結果獲得物體的移動關係。當需要知道物體在下一個畫面的移動關係時，便需依此邏輯重新再找一次。雖然，完全搜尋演算法不需作額外判斷，但當影像較大且處理時間有限的情形下，要完成多畫面下的移動關係的分析將會太過耗時也無效率，進而減低實作的可能性。

本發明提供一種多畫面中物體移動的追蹤方法，能夠縮短移動決策(motion decision)的時間。

本發明提出一種多畫面中物體移動的追蹤方法，包括下列步驟。首先，取得一第一畫面中一物體的一第一位置與一第二畫面中物體的一第二位置，以根據第一位置與第二位置計算一移動向量。接著，判斷移動向量是否大於一門檻參數。當移動向量大於門檻參數時，根據移動向量，從多個預定方向中選擇一主方向。然後，從一第三畫面的第二位置上，搜尋主方向附近區域，以找出物體於第三畫面的一第三位置。當移動向量小於門檻參數時，沿這些預定方向，搜尋第三畫面的第二位置的附近區域，以找出物體於第三畫面的第三位置。

在本發明之一實施例中，這些預定方向的數量為8個，且等分360度。

在本發明之一實施例中，搜尋主方向附近區域，以找出物體於第三畫面的第三位置的步驟，包括下列步驟。首先，自這些預定方向中，找出與主方向相鄰的另兩個主方向。接著，在三個主方向上，搜尋第三畫面中的物體。

在本發明之一實施例中，搜尋主方向附近區域，以找出物體於第三畫面的第三位置的步驟，更包括下列步驟。首先，根據三個主方向上的搜尋結果，自三個主方向中選出一掃瞄方向。接著，搜尋掃瞄方向的附近區域，以找出物體於第三畫面的第三位置。

在本發明之一實施例中，多畫面中物體移動的追蹤方法，更包括當第三畫面中搜尋不到物體時，放棄第三畫面。

在本發明之一實施例中，多畫面中物體移動的追蹤方法，更包括下列步驟。首先，根據第一畫面至一第N-1畫面中物體的位置，分析物體的一移動趨勢。接著，根據移動趨勢，判斷物體於一第N畫面中的一第N位置。

在本發明之一實施例中，分析移動趨勢的步驟，包括利用一曲線配適法(curve fitting)或一線性外插法分析移動趨勢。

基於上述，本發明的多畫面中物體移動的追蹤方法可先對多個預定方向作粗掃，來縮短移動決策的時間與資料計算量，而可符合高畫面更新率的需求。此外，藉由門檻值比較等機制，可使得搜尋結果仍有一定的準確度。

為讓本發明之上述特徵和優點能更明顯易懂，下文特舉實施例，並配合所附圖式作詳細說明如下。

圖1為本發明一實施例之多畫面中物體移動的追蹤方法的流程示意圖，圖2為應用於圖1的多張連續畫面的示意圖。在圖2中，例如繪示連續的一第一畫面F1、一第二畫面F2、一第三畫面F3以及一第四畫面F4，且一物體O可沿著軌跡T移動。

請參考圖1與圖2，首先進行步驟S110，取得第一畫面F1中物體O的一第一位置(x,y)與第二畫面F2中物體O的一第二位置(x+U1,y+V1)，以根據第一位置(x,y)與第二位置(x+U1,y+V1)計算一移動向量(U1,V1)。接著進行步驟S120，判斷移動向量(U1,V1)是否大於一門檻參數，區分出物體O移動量大的情形和小的情形。在本實施例中，門檻參數可為單一數值TH(未示意於圖中)，但不以此為限。即，分別比較U1與TH以及V1與TH的大小。

圖3A為圖1之預定方向、主方向表示於畫面中的示意圖，請配合參考圖2與圖3A，當移動向量(U1,V1)大於門檻參數時，代表物體O的移動量較大，在短時間內不易方向反轉。此時，進行步驟S130，根據移動向量(U1,V1)，從多個預定方向P中選擇一主方向M1。然後進行步驟S140，從第三畫面F3的第二位置(x+U1,y+V1)上，搜尋主方向M1附近區域，以找出物體O於第三畫面F3的一第三位置(x+U2,y+V2)。在本實施例中，這些預定方向的數量可為8個，且等分360度。

也就是說，當要找第三畫面F3與第一畫面F1的相對移動關係時，直接從第二位置(x+U1,y+V1)開始找，而不是從第一位置(x,y)找起。同理，記錄下第三畫面F3與第一畫面F1的移動向量(U2,V2)，當要找出第四畫面F4中物體O與第一畫面F1中物體O的運動關係時，也是直接根據第三畫面F3記錄下的第三位置(x+U2,y+V2)作出發點開始搜尋，且可依照最可能的主方向M1粗掃，爾後才細掃。

圖4為圖3A中設定矩型的搜尋範圍的示意圖。請配合參考圖2與圖4，相對的，當移動向量(U1,V1)小於門檻參數時，代表物體O移動量接近原點，接下來的運動將有可能使得方向反轉。此時，進行步驟S150，沿這些預定方向P，搜尋第三畫面F3的第二位置(x+U1,y+V1)的附近區域S4，以找出物體於第三畫面F3的第三位置(x+U2,y+V2)。舉例來說，附近區域S4可由一矩形區域所定義出來，但不以此為限。也就是說，以目前第二位置(x+U1,y+V1)為中心設定一個矩型的搜尋範圍，並以八方向去分析以節省時間與複雜度。

圖5為本發明另一實施例之多畫面中物體移動的追蹤方法的流程示意圖，圖3B~圖3D為相鄰的三個主方向的示意圖。以下將配合圖2、圖3B~3D與圖4說明圖5的流程，但不以此為限。請先參考圖2，首先進行步驟S210，取得第一畫面F1中物體O的一第一位置(x,y)與第二畫面F2中物體O的一第二位置(x+U1,y+V1)，以根據第一位置(x,y)與第二位置(x+U1,y+V1)計算一移動向量(U1,V1)。接著進行步驟S220，判斷移動向量(U1,V1)是否大於一門檻參數。

當移動向量(U1,V1)大於門檻參數時，進行步驟S230，根據移動向量(U1,V1)，從多個預定方向P中選擇一主方向M1。然後進行步驟S240，從第三畫面F3的第二位置(x+U1,y+V1)上，搜尋主方向M1附近區域S1，以找出物體O於第三畫面F3的一第三位置(x+U2,y+V2)。步驟S240可包括步驟S242~248等多個子步驟。請參考圖3B，首先進行步驟S242，自這些預定方向P中，找出與主方向M1相鄰的另兩個主方向M2、M3。接著進行步驟S244，在三個主方向M1、M2、M3上，搜尋第三畫面F3中的物體O。也就是說，在此為了進一步節省運算資源，只取出最接近的主方向作搜尋。假設系統效率需要很高且運算資源很低的情形下，則只作最接近的90度內的主方向作搜尋。在本實施例中，即是對三個相鄰的主方向M1、M2、M3作搜尋。

然後進行步驟S246，根據三個主方向M1、M2、M3上的搜尋結果，自三個主方向M1、M2、M3中選出一掃瞄方向M1。接著進行步驟S248，搜尋掃瞄方向M1的附近區域S1，以找出物體O於第三畫面F3的第三位置(x+U2,y+V2)(如圖2所示)。亦即，比較出這三個主方向M1、M2、M3的搜尋結果與誤差，最準確且最匹配的主方向M1取出後才針對其附近作細掃的動作，藉以減少資料計算量。雖然，本實施例是以圖3B為例來說明，但隨著移動向量的不同，還可以對圖3C中三個主方向M1’、M2’、M3’對應的附近區域S2或是圖3D中三個主方向M1”、M2”、M3”對應的附近區域S3進行搜尋，以此類推。

請參考圖4，相對的，當移動向量(U1,V1)小於門檻參數時，進行步驟S250，沿這些預定方向P，搜尋第三畫面F3的第二位置(x+U1,y+V1)的附近區域S4，以找出物體於第三畫面F3的第三位置(x+U2,y+V2)。

在本實施例中，進行完步驟S240或步驟S250之後，還可進行步驟S260。在步驟S260中，當第三畫面F3中搜尋不到物體O時，則可放棄第三畫面F3。也就是說，如果在連續畫面間有一些畫面用前述的搜尋法找不到符合條件的結果時，則放棄該畫面資訊。

值得一提的是，本實施例的之多畫面中物體移動的追蹤方法可應用於其他多畫面的影像處理上面。以三維雜訊抑制(3D noise reduction)的應用為例，步驟S260所放棄的畫面便不進行時間平均濾波(temporal filter)的過程。此外，由於高畫面更新率之下，每個畫面的時間差較低。因此，若有物體在短時間內快速移動至主方向搜尋範圍外的情形發生，則可能是因為物體非常快速移動所產生。在此類狀況下，物體容易有動態模糊(motion blur)的情形，混色(blending)過程中也藉由步驟S260來放棄這種已發生動態模糊的畫面。

更進一步來說，接著還可進行步驟S270，根據第一畫面F1至一第N-1畫面(未繪示)中物體O的位置，分析物體O的一移動趨勢。然後進行步驟S280，根據移動趨勢，判斷物體於一第N畫面中的一第N位置。在本實施例中，可利用一曲線配適法或一線性外插法來分析移動趨勢，但不以此為限。也就是說，本實施例並不侷限只用前一級的結果作搜尋，也可用前N-1級的結果來推得第N畫面的物體位置。

綜上所述，本發明的多畫面中物體移動的追蹤方法可先對多個預定方向作粗掃，來縮短移動決策的時間，而可符合CMOS感光元件之高畫面更新率的需求。此外，在快速的移動分析過程中，還可藉由不同的機制加上趨勢判斷，使得結果仍有一定的準確度。

雖然本發明已以實施例揭露如上，然其並非用以限定本發明，任何所屬技術領域中具有通常知識者，在不脫離本發明之精神和範圍內，當可作些許之更動與潤飾，故本發明之保護範圍當視後附之申請專利範圍所界定者為準。

F1．．．第一畫面

F2．．．第二畫面

F3．．．第三畫面

F4．．．第四畫面

M1~M3、M1’~M3’、M1”~M3”．．．主方向

O．．．物體

S1~S4．．．附近區域

S110~S150、S210~S280．．．步驟

P．．．預定方向

T．．．軌跡

(x,y)．．．第一位置

(x+U1,y+V1)．．．第二位置

(x+U2,y+V2)．．．第三位置

圖1為本發明一實施例之多畫面中物體移動的追蹤方法的流程示意圖。

圖2為應用於圖1的多張連續畫面的示意圖。

圖3A為圖1之預定方向、主方向表示於畫面中的示意圖。

圖3B~圖3D為相鄰的三個主方向的示意圖。

圖4為圖3A中設定矩型的搜尋範圍的示意圖。

圖5為本發明另一實施例之多畫面中物體移動的追蹤方法的流程示意圖。

S110~S150．．．步驟

Claims

一種多畫面中物體移動的追蹤方法，包括：取得一第一畫面中一物體的一第一位置與一第二畫面中該物體的一第二位置，以根據該第一位置與該第二位置計算一移動向量；判斷該移動向量是否大於一門檻參數；當該移動向量大於該門檻參數時，根據該移動向量，從多個預定方向中選擇一主方向；從一第三畫面的該第二位置上，搜尋該主方向附近區域，以找出該物體於該第三畫面的一第三位置；以及當該移動向量小於該門檻參數時，沿該些預定方向，搜尋該第三畫面的該第二位置的附近區域，以找出該物體於該第三畫面的該第三位置。
如申請專利範圍第1項所述之多畫面中物體移動的追蹤方法，其中該些預定方向的數量為8個，且等分360度。
如申請專利範圍第1項所述之多畫面中物體移動的追蹤方法，其中搜尋該主方向附近區域，以找出該物體於該第三畫面的該第三位置的步驟，包括：自該些預定方向中，找出與該主方向相鄰的另兩個主方向；以及在該三個主方向上，搜尋該第三畫面中的該物體。
如申請專利範圍第3項所述之多畫面中物體移動的追蹤方法，其中搜尋該主方向附近區域，以找出該物體於該第三畫面的該第三位置的步驟，更包括：根據該三個主方向上的搜尋結果，自該三個主方向中選出一掃瞄方向；以及搜尋該掃瞄方向的附近區域，以找出該物體於該第三畫面的該第三位置。
如申請專利範圍第1項所述之多畫面中物體移動的追蹤方法，更包括：當該第三畫面中搜尋不到該物體時，放棄該第三畫面。
如申請專利範圍第1項所述之多畫面中物體移動的追蹤方法，更包括：根據該第一畫面至一第N-1畫面中該物體的位置，分析該物體的一移動趨勢；以及根據該移動趨勢，判斷該物體於一第N畫面中的一第N位置，其中N3。
如申請專利範圍第6項所述之多畫面中物體移動的追蹤方法，其中分析該移動趨勢的步驟，包括：利用一曲線配適法或一線性外插法分析該移動趨勢。