李戰(zhàn)明 ， 施穎迪

（1．蘭州理工大學 電氣工程與信息工程學院，甘肅 蘭州 730050；2．蘭州理工大學 甘肅省工業(yè)過程先進控制重點實驗室，甘肅 蘭州 730050）

隨著計算機視覺和微電子技術的不斷發(fā)展，圖像拼接已廣泛應用于虛擬現(xiàn)實、計算機視覺、航空航天、軍事應用、醫(yī)學圖像處理、遙感圖像處理等多個領域[1]。視頻序列的圖像拼接是圖像拼接的一個方面，主要是將多幀視頻序列拼接為一幅視野范圍更大的圖像，從而更直觀的反映視頻序列的主要內容。

在視頻序列的拼接中，相鄰幀之間的重復率較高，若對每相鄰的視頻幀都進行一次拼接，不僅會耗費大量的時間，而且隨著拼接幀數(shù)量的不斷增加，拼接效果也會越來越差。利用關鍵幀拼接表示整個視頻序列成為一種有效的方法。文獻[2]中提出基于自適應模板匹配的視頻圖像拼接技術，算法的限制條件較多，容易因為外界干擾而造成拼接失敗。參考文獻[3]中提出將長視頻分段，采用場景流算法拼接的一種視頻序列的拼接技術，但這種方法需要描繪視頻流從起點到終點的最短流形，實時性不高，同時由于要對每列像素構建圖卡，需要內存空間大。

針對以上問題，提出了一種視頻序列拼接的新方法。首先，采用改進的幀間聚類的算法提取視頻的關鍵幀，然后利用尺度不變特征點提取算法提取關鍵幀的特征點，結合最近鄰算法（Nearest Neighbor-NN）進行特征點匹配，采用引導互匹配法[4]和投票過濾法提高匹配精度。再次，結合隨機抽樣一致性RANSAC（Random Sample Consensus）魯棒估計算法得到所選幀間的單映矩陣，利用LM（Levenberg-Marquardt）非線性最小化迭代算法對得到的矩陣的進行精煉，最后，利用單映矩陣的級聯(lián)性，并通過加權融合的方法完成視頻序列的無縫拼接，取得了較好的效果。

1 幀間的單映變換矩陣及關鍵幀選取判定

1.1 幀間單映變換矩陣的概念

單映矩陣變換是一種常用的幀間變換模型，主要適用于任意場景空間攝像機為旋轉或者縮放運動，或者空間為平面場景和任意攝像機的運動。 單映矩陣變換表示為：

對于相鄰的關鍵幀，可以直接采用上述幀間變換模型，但是對于非相鄰的關鍵幀，可以利用單映矩陣的級聯(lián)性質，得到非相鄰關鍵幀之間的單映變換矩陣。

假設第k幀、第h幀為非相鄰的關鍵幀，以 第k幀作為參考幀，第h幀為目標幀，利用單映矩陣的級聯(lián)性質，可以得到兩非相鄰關鍵幀的單映變換矩陣。

其中，Hh，t，Ht，n，…，Hm，l，Hl，k分別是第 k 幀、第 h 幀之間的相鄰關鍵幀的單映變換矩陣，如圖 1所示。

圖1 單映矩陣的級聯(lián)示意圖Fig.1 Cascade figure of homography matrix

1.2 關鍵幀的選取

在進行視頻拼接的過程中，幀間重疊度比較高，數(shù)據(jù)冗余量大，而關鍵幀的使用很大程度上減少了視頻處理的數(shù)據(jù)量。在拍攝視頻影像時，由于場景中目標的運動或攝像機本身的操作（如變焦、搖鏡頭等）的影響，一個鏡頭僅用一幅關鍵幀不能很好地代表該鏡頭的內容，常需用幾幅關鍵幀。原則上講，關鍵幀應能提供一個鏡頭內容盡量豐富的概要。

歐式幀差法提取關鍵幀是通過判斷視頻序列之間的相似度來提取關鍵幀，計算幀與幀之間的幀差歐氏距離，利用它來計算幀差均值，幀差方差以及幀差的差異系數(shù)來作為衡量幀與幀之間相關程度的數(shù)據(jù)量標準，根據(jù)幀差歐氏距離的最大值與最小值計算出相應的平均值，并以此作為一個判別關鍵幀的閾值，對相應的視頻幀序列進行判別，提取關鍵幀的幀數(shù)，得到相應視頻幀序列的關鍵幀。借助于歐式幀差法的提取關鍵幀的基本思路，文中采用改進的幀差聚類的算法來提取關鍵幀，即將鏡頭中的幀計算特定的特征值，然后根據(jù)特征值的聚類將鏡頭分為幾個關鍵簇，最后根據(jù)特征值的分類計算關鍵幀，本文是在聚類[5]的基礎上實現(xiàn)的，文中選取幀差歐式距離、幀差均值和和幀差方差作為特定的特征值，同時求取幀差歐式距離、幀差均值和幀差方差的最大值、最小值和極值，通過最大值和最小值求得中間值，比較極值和中間值的大小，去掉小于中間值的極值點，剩下的點當做關鍵簇，再比較關鍵簇和定義的關鍵幀的數(shù)目，若大于定義的關鍵幀的數(shù)目，再利用特征值選取關鍵幀。

算法的實現(xiàn)過程：

1）假設視頻 f1，f2，…，fn代表一個視頻序列，計算視頻序列的幀差，即計算相鄰兩幀之間的每個對應的像素的灰度（亮度）變化。相鄰兩幀對應點的灰度（亮度）差為

其中：fn（i，j）、 fn+1（i，j）分別代表第 n 幀和第 n+1 幀像素（i，j）的灰度（亮度）。 然后利用公式（1）計算相鄰幀的幀差值，根據(jù)選取的視頻總幀數(shù)，設定計算幀數(shù)的范圍，將得到的幀差值進行比較，選取幀差值最大的相鄰幀數(shù)。

旅游精準扶貧的新媒體營銷運作模式初探 ………………………………………………………………… 任傳陽 楊永德（2/21）

2）計算幀差的歐式距離，公式如下

3）計算幀差之間的均值，公式如下：

其中，M、N為圖像的尺寸，n為總的幀數(shù)。

4）計算幀差的方差，公式如下：

5）計算幀差的歐式距離、均值和方差的最大值、最小值以及極值，利用最大值最小值求取中間值，比較中間值和極值的大小，去掉小于中間值的極值。剩下的組成關鍵簇，若關鍵簇大于定義的幀數(shù)，重復步驟 2），3），4），5）得到關鍵幀，反之輸出關鍵幀。

采用改進的幀間聚類算法提取關鍵幀，一定程度上可以滿足視頻序列拼接的需要。

2 特征點提取與匹配

2.1 特征點提取

視頻圖像的拍攝大多是通過手持相機或者是固定在某些平臺而獲取的影像，由于相機的運動和外界的干擾，很容易造成視角和尺度的偏差，為了克服上述干擾，采用SIFT（Scale Invariant Feature Transform）算法完成圖像序列特征點的提取。

該算法是在空間域和尺度域上同時進行特征點的計算與提取的，因此得到的特征點具有尺度不變性，能夠正確的提取尺度和視角變化較大的圖像序列中存在的特征點，有效地克服了輸入圖像中的噪聲干擾。

2.2 特征點匹配

SIFT的匹配算法是通過計算兩個特征點描述符之間的歐氏距離得到的。即找出與特征點描述符pi歐氏距離最近和次近的兩個鄰居特征點描述符 qi′和 qi″， 然后計算pi與 qi′以及pi與qi″兩組描述符之間歐氏距離的比值r。如比值r小于規(guī)定閾值則視為匹配成功，（pi，qi′）點對則為一對匹配點，否則匹配失敗。這種匹配方法簡便快捷，但會產(chǎn)生誤匹配。因此文中采用引導互匹配及投票過濾兩種技術來提高匹配精度。

1）引導互匹配法：該方法的思想是縮小特征點搜索范圍，并采用互映射的方法減少錯誤匹配。假設圖像變換矩陣的當前估計為H，根據(jù)對極幾何特性，H規(guī)定了點x在對極線Hx周圍的搜索范圍。因此應在對極線Hx周圍的一定區(qū)域內搜索點x的匹配點。此外，根據(jù)互映射原理，即匹配點對之間的映射關系的對稱性，對于匹配點對{pi?qi′}，在進行匹配映射時，應存在這兩點間的對應關系{pi→qi′}和{pi←qi′}。

2）投票過濾法：使用投票過濾法消除誤匹配的理論依據(jù)如下：在兩幅相關的圖像序列中，相機的旋轉和尺度變化均相對穩(wěn)定，因此連接圖像中各組匹配點對所形成的向量之間的偏差應符合某一規(guī)律。假設特征點pi和pj分別與特征點qi和 qj相對應，即{pi?qi′} 與{pjqj′}是正確的匹配點對，則向量Ei=qi-pi與Ej=qj-pj應具有相同特性（長度，方向）。本文綜合考慮兩方面因素，首先計算圖像序列中所有匹配點對的橫縱坐標距離差的平均值，并將其記為該圖像序列組的標準匹配閥值。然后，刪除圖像序列組中橫縱坐標距離差與標準匹配閥值相差太遠的匹配點對。即采用刪除橫縱坐標之差距離平均值太遠的錯誤匹配點對的投票過濾方法來提高匹配精度。

3 拼接算法的實現(xiàn)及相關實驗

3.1 拼接算法的實現(xiàn)

1）采用改進的幀間聚類算法提取出關鍵幀。

2）利用SIFT算法提取關鍵幀中的特征點，采用最近鄰算法計算特征點之間的匹配。

3）對于相鄰的關鍵幀，利用RANSAC魯棒估計算法[6]得到相鄰關鍵幀之間的最大的一致點集和單映矩陣H的估計，具體步驟為：①選擇四組對應點組成一個隨機樣本并且估計矩陣H的參數(shù)；②對假設的每組對應計算距離d；③計算與H一致的內點數(shù)；（選擇具有最多內點數(shù)的H，在數(shù)目相等時，選擇內點標準方差最小的那個解）。

4）由初始H值迭代精煉變換矩陣，這里采用了 LM（Levenberg-Marquardt）[7]非線性最小化迭代算法，具體算法流程如下：

①對步驟 2）中得到的每個特征點（x，y）計算對應點（x′，y′）；

②計算對應點之間的誤差 e=I′（x′，y′）－I（x，y）；

③計算變換矩陣 H 各分量 hi（i=0，1，…，7）相對于誤差 ei的偏導數(shù)：

④解H增量函數(shù)得到Δh，修正H。

⑤判斷誤差值e，若誤差減小但未小于閥值，則繼續(xù)計算新的Δh，否則增大λ值，重新計算Δh；

⑥當誤差e小于規(guī)定閾值時，停止計算，得到精煉的H。

5）引導匹配：用估計的H去定義對極限附近的搜索區(qū)域，進一步確定特征點的對應。

6）反復迭代4）、5）直到對應點的數(shù)目穩(wěn)定為止。

7）對非相鄰關鍵幀利用單映矩陣的級聯(lián)性進行計算，獲取對應的圖像變換矩陣。

8）根據(jù)獲得的變換矩陣H將對應的關鍵幀進行變換，確定兩幀直接的重合區(qū)域，并將目標關鍵幀和參考關鍵幀映射到一幅空白圖像中形成拼接圖。

9）采用加權融合算法[8]處理圖像拼接縫問題，對圖像進行加權平滑處理以達到無縫拼接。

3.2 相關實驗

實驗采用手持數(shù)碼相機采集兩段視頻，利用改進的幀間聚類算法提取出關鍵幀，并采用拼接算法實現(xiàn)了關鍵幀所表示的視頻序列的無縫拼接，效果比較理想。

圖2是一段82幀的視頻，根據(jù)改進的幀間聚類的算法提取出的關鍵幀為第 10幀、29幀、41幀、49幀、60幀、71幀（圖2（a-f），圖3為關鍵幀所表示的視頻序列拼接的效果圖，圖4為剪切之后的拼接效果圖。

圖2 關鍵幀所表示的視頻序列拼接效果圖Fig.2 The video mosaic based on keyframes

圖5 是一段118幀的視頻，根據(jù)改進的幀間聚類的算法提取出的關鍵幀為第10幀、19幀、34幀、45幀、54幀、64幀、75 幀、84 幀、105 幀（圖 5（a-i），圖 6 為關鍵幀所表示的視頻序列拼接的效果圖，圖7為剪切之后的拼接效果圖。

圖3 剪切之后的拼接效果圖Fig.3 The result of clipped video mosaic

圖4 關鍵幀所表示的視頻序列Fig.4 Keyframes sequence extraction

圖5 關鍵幀所表示的視頻序列拼接效果圖Fig.5 The video mosaic based on keyframes

圖6 剪切之后的拼接效果圖Fig.6 The result of clipped video mosaic

4 結束語

采用改進的幀間聚類算法的提取關鍵幀，并利用SIFT算法提取特征點，使用最近鄰算法結合引導互匹配和投票過濾法提高匹配精度，利用RANSAC魯棒估計得到關鍵幀間的單映矩陣H，并使用LM算法精煉單映矩陣H，獲取關鍵幀之間的重疊區(qū)域，結合級聯(lián)單映矩陣和加權融合算法實現(xiàn)視頻序列的無縫拼接。

圖7 剪切之后的拼接效果圖Fig.7 The result of clipped video mosaic

[1]Xiaobo Gao，Xianmei Fang.Research on Image Mosaic Algorithm Based on Computer Wizard Vector Field Algorithm[J].Intelligent Computing Theories，2013:156-162.

[2]薛艷.基于自適應模板匹配的視頻圖像[D].安徽:合肥工業(yè)大學，2009.

[3]郭李云，歐陽寧，莫建文.長視頻序列拼接[J].計算機工程與應用，2011，47（14）:183-185.GUOLi-yun， OUYANGNing， MO Jian-wen.Long video sequence[J].Computer Engineering and Application，2011，47（14）:183-185.

[4]郭禾，傅新元，陳鋒，等.任意視角的多視圖立體匹配系統(tǒng)[J].計算機工程與設計，2007，28（12）:2873-2877.GUO He，F(xiàn)U Xin-yuan，CHEN Feng，et al.Integrated multiview stereo matching system with arbitrary viewpoints[J].Computer Ergineering and Design，2007，28（12）:2873-2877.

[5]Patricia Cotic，Zonko Jaglicic，Ernst Niederl-eithinger， et al.Image fusion for improved detection of near-surface defects in NDT-CE using unsupervised clustering methods[J].Journal of Nonde structive Evaluation，2014.

[6]Zhaoxia Fu，Liming Wang.Optimized design of automatic image mosaic.Multimedia Tools and Applications，2014，72（1）:503-514.

[7]楊敏.基于Levenberg-Marquardt算法的圖像拼圖研究 [J].電子工程師，2007，33（10）:43-45.YANG Min.Research on Image Registration Based on Levenberg-Marquardt algorithm[J].Electronic Engineer，2007，33（10）:43-45.

[8]Richard Szeliski.Computer vision:algorithms and applications[M].German Springer，2010.