視頻聚類方法、排序方法和視頻搜索方法以及相應裝置的製作方法

2023-07-31 19:39:46 4

專利名稱：視頻聚類方法、排序方法和視頻搜索方法以及相應裝置的製作方法
技術領域：
本發明涉及一種視頻聚類方法、排序方法和視頻搜索方法，具體而言，涉及一種基於視頻信息本身而非其文字描述的視頻聚類方法、排序方法和視頻搜索方法以及相應的裝置。
背景技術：
隨著網際網路和多媒體技術的迅速發展，人們可以訪問到的多媒體數據急劇增長。 視頻作為最複雜的一種多媒體數據，憑藉其多樣化的表現形式、豐富的語義內容以及便捷的記錄方式等得到了廣泛的應用和發展。與此同時，大容量存儲技術的發展使得數字視頻信息的存儲成本越來越低，這促進了數字視頻信息的大量產生和堆積。面對越來越多的海量視頻庫，如何快速有效地進行視頻內容分析和檢索就成為當前視頻信息領域研究的當務ο
傳統的搜尋引擎採用基於文本的I^ageRank技術(例如，Lawrence Page， Sergey Brin, Rajeev Motwani, Terryffinograd, 「 The PageRank Citation Ranking BringingOrder to the Web " ,1998 ；以及 Taher H. Haveliwala, " Efficient Computation of PageRank" , Stanford Technical R印ort，1999)。該技術基於這樣一種認識，即一個網頁的重要性取決於它被其他網頁連結的數量，特別是被一些已經被認定是" 重要"的網頁的連結數量。
現有的大部分所謂視頻搜尋引擎也基於文本等第三方因素來辨別視頻內容。當一個搜尋引擎爬蟲在網絡中通過URL(Uniform ResourceLocator，統一資源定位符)尋找新的圖片/視頻連結時(為簡單起見，以下以視頻為例進行說明)，它會通過HTTP協議(HyperTextTransfer Protocol，超文本傳輸協議)來提取這個網頁，並把網頁的 html (Hypertext Markup Language，文本標記語言)代碼傳輸給內容分析器。內容分析器會根據特定的html代碼(例如標籤)來尋找網頁中所包含的視頻。然後，搜尋引擎爬蟲會根據網頁html代碼中的title (名稱)、heading (標題)、keywords (關鍵詞)、 description (描述)等標籤及標籤中的屬性和/或連結到該網頁的外部連結來判斷視頻的內容。當搜尋引擎基本判斷出視頻的內容後，就會按照視頻的內容對其進行歸類。在確定了視頻的內容和分類後，搜尋引擎將分析好的數據放置到索引資料庫中，並自動為視頻生成縮略圖。當用戶進行搜索時，搜尋引擎就會根據視頻的內容、與關鍵詞的相關度等因素來對視頻進行排序，最終將較準確的搜索結果列表展示給用戶。
上述基於文本的視頻搜索方法有著先天的缺陷。首先，文字屬性標籤難以表達蘊藏在多媒體數據中的豐富內容，導致在查詢視頻時經常會出現錯誤。其次，文字屬性標籤是一種人為抽象出來的描述，這使得如果描述的標準改變，則標籤也得重新製作才能適合新的查詢要求。換句話說，特定的標籤只適合特定的查詢要求。最後，人為製作出來的文字屬性標籤受製作者的主觀因素影響很大，不同的觀察者或同一觀察者在不同條件下對同一視頻可能會給出不同的描述，因此不夠客觀且難以統一標準。
於是，基於內容的視頻檢索成了目前計算機視覺、多媒體技術領域的研究熱點。基於內容的視頻檢索是指對視頻數據中蘊涵的視覺和語義內容進行計算機處理、分析、理解及檢索，本質上包括對無序的視頻數據進行結構化、提取視覺與語義信息並保證視頻內容能夠被快速檢索(例如，HongJiang Zhang, Philippe Aigrain， DraguinPetkvic. Representation and Retrieval of Video DatainMultimedia,1997)。 近年來已實現了一些基於內容的多媒體檢索方法(例如，Ziyou Xiong, Regunathan Radhakrishnan, AjayDivakaran, Yong Rui, Thomas S. Huang. A UnifiedFramework for Video Summarization, Browsing & Retrieval :with Applications to Consumer and Surveillance Video. Academic Press, 2005 ；以及 Remco C. Veltkamp, HansBurkhardt, Hans-Peter Kriegel. State—of—the—Art inContent—Based Image and Video Retrieval, Springer，2001)，以使用人工智慧方法自動提取多媒體內容的特徵(例如，YingLi，C. C. Jay Kuo.Video Content Analysis UsingMultimodal Information :For Movie Content Extraction, Indexing and Representation. Springer, 2003 ；以及 Sagarmay Deb. Video Data Management and InformationRetrieval, IRM Press，2004)。內步索中，如何從視頻中把感興趣的對應幀的物體提取出來即進行圖像分割是一個最基本的需求。傳統上採用無監督的自底至上(bottom-up)的方式來完成上述圖像分割。但由於視頻是高維流型，單純採用自底至上的方式通常對視頻無法得到需要的結果。發明內容
有鑑於此，本發明的目的在於提供一種視頻聚類方法、排序方法和視頻搜索方法以及相應的裝置，以即使針對大規模視頻庫也能夠基於視頻內容本身達成實時、精確的視頻搜索。
為了實現上述目的，本發明提供了一種視頻聚類方法，其包括聚類步驟，用於針對視頻中的每一幀進行聚類，即將相似度高於預定閾值的多個像素聚類到一起以得到超像元。其中，所述相似度是根據像素的顏色、位置和運動特性來計算的。
為了實現上述目的，本發明還提供了一種排序方法，用於對根據本發明所提供的視頻聚類方法所得到的超像元進行排序，該排序方法包括步驟一對各超像元賦予初始的排序值，該初始的排序值不等於零；步驟二 根據各超像元的排序值計算公式，利用各超像元當前的排序值，計算各超像元新的排序值；步驟三重複步驟二，直到各超像元的排序值收斂。
為了實現上述目的，本發明還提供了一種視頻搜索方法，其包括獲取步驟，用於獲取網際網路上的視頻；聚類步驟，用於根據本發明所提供的視頻聚類方法，對通過所述獲取步驟所獲取的每個視頻進行聚類；排序步驟，用於根據本發明所提供的排序方法，對通過所述聚類步驟所得到的每個視頻的每個超像元進行排序；關鍵字提取步驟，用於針對通過所述聚類步驟所得到的每個視頻的每個超像元或超像元組，基於該超像元或超像元組的特定特徵為該超像元或超像元組賦予文字屬性標籤，其中，該特定特徵包括該超像元或超像元組的視頻特徵、視頻內容識別和/或視頻內容主體分類；索引步驟，用於根據所述關鍵字提取步驟賦予每個視頻的每個超像元或超像元組的文字屬性標籤，針對每個視頻建立索引。
為了實現上述目的，本發明提供了一種視頻聚類裝置，包括聚類部，用於針對視頻中的每一幀進行聚類，即將相似度高於預定閾值的多個像素聚類到一起以得到超像元。 其中，所述相似度是根據像素的顏色、位置和/或運動特性來計算的。
為了實現上述目的，本發明還提供了一種排序裝置，用於對通過根據本發明的視頻聚類裝置所得到的超像元進行排序，其包括初始化部，用於對各超像元賦予初始的排序值，其中，該初始的排序值不等於零；以及計算部，用於根據各超像元的排序值計算公式，利用各超像元當前的排序值，計算各超像元新的排序值。其中，所述計算部重複進行所述計算，直到各超像元的排序值收斂為止。
為了實現上述目的，本發明還提供了一種視頻搜索裝置，其包括獲取部，用於搜集視頻；根據本發明的視頻聚類裝置，用於對通過所述獲取部所搜集到的每個視頻進行聚類以得到超像元；根據本發明的排序裝置，用於對通過所述視頻聚類裝置所得到的每個視頻的每個超像元進行排序；關鍵字提取部，用於針對通過所述視頻聚類裝置所得到的每個視頻的每個超像元或超像元組，基於該超像元或超像元組的特定特徵為該超像元或超像元組賦予文字屬性標籤，其中，該特定特徵包括該超像元或超像元組的視頻特徵、視頻內容識別和/或視頻內容主體分類；以及索引部，用於根據所述關鍵字提取部賦予每個視頻的每個超像元或超像元組的文字屬性標籤，針對每個視頻建立索引。
通過基於能夠模擬人類視覺的最小實體的超像元對視頻中的像素區域進行時空域自相關和互相關分析、排序，本發明即使針對海量視頻庫也能夠達成實時、精確的視頻搜索。


圖1示出根據本發明優選實施例的視頻搜索方法的流程圖。
圖2示出超像元聚類過程前後的複雜度對比。
圖3示出利用運動矢量來計算SPR。
圖4示出一段視頻中超像元的互相關sra矩陣。
圖5示出本發明的視頻搜尋引擎的搜索結果。
圖6示出現有視頻搜尋引擎的搜索結果。
圖7示出本發明的視頻搜尋引擎的搜索結果。
圖8示出現有視頻搜尋引擎的搜索結果。
具體實施方式
以下詳細說明本發明的具體實施方式
。
人類視覺具有與生俱來的快速識別和抽象能力。在瀏覽視頻時，人的視覺和大腦的反應能力能夠幫助其輕鬆了解視頻裡的物體和背景，從而自動形成內容架構。受此啟發， 本發明旨在提供一種能夠仿真人類視覺的快速視頻搜索弓I擎技術。然而，人類這種看似十分簡單的快速視覺識別環境的能力，要想在計算機上得以實現，卻不是一件簡單的事情，因為人類視覺是一個複雜的物理化學系統。下面首先介紹一下人類視覺系統的特性。
在人的視網膜上有兩種光感受細胞，視錐細胞(Cones)和視杆細胞(Rods)。視杆細胞的感光水平低，捕捉到單個光子就能起反應，所以暗環境中的視覺主要依靠視杆細胞。 視錐細胞個頭小，密集在視網膜的中央黃斑處，在中央凹(fovea)處與後一級的神經建立甚至是一對一的連接關係，所以視覺的敏銳度(也就是常說的注意力)主要是由視錐細胞決定的。從分布上而言，在中央凹大約3度的視角內只有視錐細胞，然後視錐細胞的密度迅速降低，以至在周邊基本上只有視杆細胞。
目前對人類視覺的研究中有一點已經得到了普遍認同，即視覺系統同時具有很高的細節分辨能力和很強的全局觀察能力，而這兩種能力就是由上述視錐細胞和視杆細胞聯合實現的。具體而言，當人觀察某一個場景的時候，人眼會選擇性地採取用以採集信息的注視(fixation)運動、用以將注意力從一個目標轉移到另一個目標的跳動(saccade)運動以及用以穩定運動圖像的追隨(smoothpursuit和0ΚΝ)運動，進而產生不同的選擇性的視覺信號，以對所觀察內容進行高效率的瀏覽和檢索。例如，在通過視杆細胞大致掌握物體輪廓之後，如果想看得更清楚，人會很自然地把中央凹對準目標，用視覺敏銳度最高的部分來接受信息。這就是所謂的選擇性注意力(Selective Attention)特性。
參考人類視覺系統的選擇性注意力特性，本發明提供了一種同時兼顧細節和全局的快速視頻搜索技術。
根據本發明的一個優選實施方式，如圖1所示，本發明的視頻搜索方法主要由以下幾部分組成首先進行預處理(步驟SO)，以將視頻幀過分割(Over-kgmentation)成顏色相似的像素集合；然後進行時空域超像(Spatial Temporal Super pixel, STSP)聚類 (Clustering)，即針對過分割後的像素區域，根據每一個像素與其時間、空間鄰域中其他像素的相似性進行聚類，以產生能夠模擬人類視覺的最小實體的超像元作為後續操作的最小單位；接著進行超像元等級(Super Pixel Rank, SPR)計算，即有效地利用視頻所擁有的龐大連結構造的內在特性，將從超像元A導向超像元B的運動看作是A對B的支持投票，從而根據這個投票數來評價各超像元的重要性；最後進行附加處理，例如，根據實際應用運行一個或者多個屬性識別模塊(色彩、人臉、人體、文字、場景、車牌等等)，為所聚類出的各超像元附加上文字屬性標籤，以作為視頻檢索的輔助匹配條件。
通過上述介紹可知，超像元是本發明的搜尋引擎中的最基本實體；而超像元等級表示通過分析「視頻的連結構造」而得出的視頻內容本身的特性，其作為該搜尋引擎中表示超像元的重要性的指標，通常不會受到外部檢索(引擎)的影響。搜尋引擎對時空域超像元的屬性和標籤進行匹配搜索。在搜索最佳匹配的時候，優選不單只看投票數，對投票的超像元也進行分析，例如對「重要性」高的超像元所投的票給予較高的加權。根據這樣的分析， 得到的投票數的加權和較高的超像元會被認為相對重要，並將其在檢索結果內的出現次序相對提前。當然，如果某個超像元與某次檢索的檢索關鍵詞的相關度很低甚至沒有關聯，即使其重要性很高也對該次檢索沒有任何意義。為此，搜尋引擎優選附加使用基於文本的文字屬性標籤匹配技術，以進一步提高視頻檢索的準確度。
下面將詳細介紹上述各部分的技術細節。
1、預處理
在預處理中，對視頻的每幀進行過分割，也即把顏色或者灰度非常相近的像素聚類到一起，以減少後續超像元聚類的計算複雜度。作為一個例子，在本發明中，使用的是英特爾公司的 OpenCV 2. 1 (OpenSource Computer Vision Library)所提供的 k 領域(k NearestNeighbor)過分割算法庫FLANN。但是，本領域技術人員可知，使用任何其他的聚類算法也是可行的，只要該聚類算法能夠將視頻幀中顏色或灰度相近的像素聚類到一起即可。
2、時空域超像元聚類
在時空域超像元聚類中，對視頻中過分割後的像素區域進一步按照內容進行聚類，以便能快速有效地建立索引andexing)。也就是讓過分割後的各像素區域中顏色、紋理、亮度和/或運動相似並且距離相近的像素聚成一個個時空域上的實體即時空域超像元。該實體是後續視頻內容檢索的最小單位。
「如何把一段視頻裡的人、車和背景聚類成相應的實體」，在圖像處理領域裡已經有許多自動或半自動的算法來解決這個問題，比如向量量化(Vector Quantization)、K均值(K-means)等。但是，僅僅把顏色相似的像素聚類到一起，不是真正的時空域上的分割， 因為如果僅僅是考慮顏色相似的話，視頻裡面不同的幀中位置離得很近的物體可能無法被聚到同一類中。本發明在聚類用的特徵中加入區域位置中心信息和平均運動特徵。例如， 以往是使用R、G、B三個顏色值來表示一個像素，本發明還可以加入χ、y (區域位置中心信息)和/或dx、dy (平均運動特徵)。這七個特徵被歸一化以後成為7維特徵向量。每個過分割區域都有一個7維特徵向量。
在對每個過分割區域提取一個N(N為大於3的整數)維特徵之後，本發明依靠各個過分割區域和它們的特徵向量的相似性建立一個圖形(Graph)。該圖形中的每個節點表示一個過分割區域，該圖形中的每條連線表示兩個節點之間的相似度。聚類的過程就是把這個圖形中的一些連線切斷，讓整個圖形被打散成一些獨立聯通的子圖形(sub-Graph)。
具體來說，如果一段視頻中的所有像素組成一個圖形，並把(例如，顏色和位置) 相似的節點連接起來，連線上的權值表示這兩個節點的相似程度(按照特徵向量歸一化後的相似度計算)，那麼把視頻分割為幾個超像元的問題實際上等價於把圖形分割為幾個子圖形的問題，並且可以要求分割所得的權值最小，亦即被切斷的連線的權值之和最小。換言之，不切斷權值比較大的連線，這表示比較相似的點被保留在了同一個子圖形中，而彼此之間聯繫不大的點則被分割開。
需要說明的是，儘管以超像元聚類處理的輸入是經過上述預處理後所得到的過分割出來的像素區域作為示例進行了如上說明，然而，本領域技術人員能夠明白，預處理僅為用以減少計算複雜度的優選附加的前置處理，本發明應不限於此，換言之，超像元聚類處理的輸入也可以是未經過預處理的視頻中的每一幀。此外，超像元聚類處理的輸出是時空域超像元(STSP)。以下是將繼續以輸入為過分割出來的像素區域作為示例進行超像元聚類過程的具體描述
(1)首先根據視頻過分割的結果數據構造一個圖形，該圖形的每個節點對應一個過分割後的數據點。
(2)將相近的點用線連接起來，並且連線的權值用於表示其所連接的兩個點之間的相似度。把這個圖形用鄰接矩陣的形式表示出來，記為W。相似度小於一定閾值的連線被刪掉。這樣W是一個稀疏矩陣。
(3)把W的每一列元素加起來得到N個數，把它們放在對角線上(其他地方都是零)，組成一個NXN的矩陣，記為D，並令L = D-W。
(4)求出L的前k個特徵值(在本發明中，除非特殊說明，否則「前k個」指按照特徵值的大小從小到大的順序) λ}1; 以及對應的特徵向量{vlLi。
(5)把這k個特徵(列)向量排列在一起組成一個NXk的矩陣，將其中每一行看作k維空間中的一個向量，並使用K均值算法進行聚類。聚類的結果中每一行所屬的類別就是原來的圖形中的節點(亦即最初的N個數據點)分別所屬的類別。圖2a_2c是超像元聚類前後的複雜度對比，S卩，用比對的方式顯示超像元索引建立前後視頻內容結構的複雜度。圖加是以某像素為中心的圖形(一部分)；圖2b是以該像素為中心的過分割後的圖形；圖2c是超像元聚類以後以該像素所在超像元為中心的圖形。 由圖可知，經過超像元聚類並建立索引，視頻內容結構的複雜度(即，數據量)明顯降低。3、排序超像元等級(SPR)是本發明提出的排序機制，它有效地利用了視頻所擁有的龐大連結構造的內在特性，也即利用的是視頻內容本身所蘊含的豐富信息。從本質上來說，視頻裡面從超像元A導向超像元B的相對運動被看作是A對B的支持投票，本發明主要根據這個投票數來計算超像元的重要等級。如上所述，當人觀察某一個場景的時候，人眼會選擇性地採取注視、跳動、追隨這三種運動，進而產生不同的選擇性的視覺信號，以對所觀察內容進行高效率的瀏覽和檢索， 這就是人類視覺系統的所謂的選擇性注意力特性。受此啟發，本發明提出了 sra計算最好遵循以下三個基本原則，並且以此設計了基於計算機仿真視覺的快速排序方法(1)差異優先原則，對應於人眼的注視，產生的是超像元。這與人類視覺系統不以像素為單位進行感知，而是自動的按區域進行感知相一致。(2)運動優先原則，對應於人眼的跳動，產生的是超像元的空域連續性。(3)時域遞減原則，對應於人眼的追隨，產生的是超像元的時域連續性。基於考慮到這三個原則的仿真視覺，本發明提出了超像元等級(SPR)，作為衡量視頻內容重要性以及將其排序的工具。sra根據每個超像元的外部「連結」以及內容的數量和質量來衡量其重要性。SI^R的概念是每個對當前時空域超像(STSP)的指向就是其他STSP 都是對該STSP的一次投票，被指向的越多，就意味著被其他STSP投票越多。例如，可以如下計算SPR，假設一個鄰域空間包括4個時空域超像元A，B, C和D。 如果所有的相對運動矢量的方向都指向A，那麼A的Sra值將是B，C及D的和，即SPR(A) = SPR (B)+SPR (C)+SPR (D)繼續假設B也有運動矢量指向C，並且D也有運動矢量指向B、C。由於一個時空域超像元總共只能投1票，所以B給每個被其指向的鄰居半票。以同樣的邏輯，D投出的票只有三分之一算到了 A的Sra上(如圖3所示)。SPR(A) = SPR(B)/2+SPR(C)+SPR(D)/3換句話說，根據前N個運動矢量的總數ν平分一個超像元的sra值。在下面的公式中，V(X)表示從超像元X指向外部的前N個運動矢量的總數SPR (A) = SPR (B) /V (B) +SPR (C) /V (C) +SPR (D) /V (D)最後，各SPR被換算為一個百分比再乘上係數q，其中q為大於0且小於1的小數。 為了避免靜止的STSP的sra會是0，本發明優選地給每個STSP —個最小值l-q SPR (A) = (SPR (B) /V (B) +SPR (C) /V (C) +SPR (D) /V (D) +. . . ) * q+ (1 -q)
每個STSP的sra是由其他STSP的sra計算得到的。通過重複計算每個STSP的 SPR，如果給每個STSP —個隨機sra值(非0)，則這些STSP的sra值會趨向於穩定。具體來說，可以把STSP的sra計算問題數學建模成二維矩陣相乘的問題，並且利用類似於 I^geRank迭代的迭代算法來進行求解。該迭代算法先假定所有STSP的SI5R是相同的，並且根據這個初始值，算出各STSP的SPR的第一次迭代值，然後再根據第一次迭代值算出第二次迭代值。現有技術已經從理論上證明了不論初始值如何選取，這種迭代算法都保證了迭代值最終能收斂到真實值。這種迭代算法通常不需要任何的人工幹預。如果以像素作為基本運算單位，上面提到的二維矩陣從理論上講有像素數目平方之多個元素。如果假定某一視頻有十億個像素，那麼這個矩陣就有一百億個元素。這樣大的矩陣相乘，計算量是非常大的。採用STSP而不是像素作為基本運算單位，就可以極大地壓縮這個矩陣的大小，壓縮比可以達到一百萬比一。此外，本發明還優選地利用稀疏矩陣計算的技巧，大大縮減了計算量，並實現了這個STSP的排名算法。本發明還可以通過並行的計算機來執行上述計算，從而進一步縮短計算時間，使每次迭代計算的用時比以往短了許多。舉例來說，在圖4中，列出了一段3小時網球比賽視頻的SI3R相關矩陣。由於把整個視頻流當作了一個整體對待，本發明更符合系統論的觀點。相比之下，以前的視頻信息檢索大多把每一幀或者每一個物體當作獨立的個體對待，並且/或者只注意內容和查詢語句的相關性，而忽略了視頻內容內在的聯繫。4、關鍵字提取(附加處理)關鍵字提取是本發明的附加處理的一個例子。但是，本發明的附加處理不限於關鍵字，而是可以和各種模式識別、計算機視覺算法集成。通過應用關鍵字提取，每個超像元或者超像元組都會產生不同層次的關鍵字。提取關鍵字的方法多種多樣。舉例來說，視頻特徵如顏色、紋理、形狀輪廓、位置、空間關係等；視頻內容的識別，比如人臉、車牌、文字； 視頻內容主體的分類，比如人、車、動物、藍天等。關鍵字提取的目的，是為各個超像元賦予準確的文字屬性標籤，以供搜尋引擎使用。以下說明本發明的有益效果。針對大規模視頻信息檢索的需要，本發明從基於低層特徵STSP的視頻快速索引建立、視頻信息排序以及多模態信息融合視頻搜索三個方面實現了針對海量視頻資料庫的搜尋引擎。在基於低層特徵的視頻檢索方面，本發明提出了基於人類視覺選擇性注意力的快速視頻檢索算法，該方法利用時空域超像元這種高效索引結構來組織視頻資料庫。它包含了基於視覺相似性和時序關係的視頻內容片段(而不是視頻幀)的相似度度量，並通過基於稀疏矩陣的快速算法，在一定程度上解決了大規模視頻資料庫的快速高效建立索引的問題。在多模態信息融合的視頻檢索方面，本發明設計了一種基於關係代數的多模態信息融合的視頻內容實體排序模型(SPR)，該模型充分利用視頻包含的運動、圖像、語義概念等多模態特徵，構造了對應於多個視頻特徵的排序模塊，並創新地使用迭代關係代數表達式對整個視頻的索引信息進行排序。實驗證明，利用該視頻檢索模型對視頻片段進行檢索， 能夠取得優於基於文本或者像素的多模型視頻檢索方法的查詢結果，特別是對於包含海量數據的多概念綜合視頻查詢更為有效。
本發明提出的視頻聚類、排序及檢索方法具有如下特點(1)突破了以往基於文本表達式檢索的局限，直接對視頻信息進行分析，抽取特徵，並利用這些特徵建立索引供檢索用。(2)可從視頻提取各種各樣的圖像特徵，例如顏色、紋理、形狀輪廓、位置、空間關係等。(3)在以超像元為最小單位進行檢索的過程中，可以採用相似性匹配的方法來逐步求精以獲得精確的查詢結果。(4)即使對於內容繁雜、數據海量的多媒體資料庫，也能夠實現對視頻信息的快速檢索。捭索質量對比搜尋引擎的目的是為用戶提供高質量、高效率的搜索結果。最重要的衡量標準是返回結果的質量高相關、低錯誤率、檢索速度快。以下列出本發明的搜尋引擎和當前最常用的引擎的搜索結果。對於本發明，在建立索引圖形的時候，將相似度閾值設置為0.2，S卩，如果兩個點的相似度小於0.2，就把他們看作是不連接的。在構造索引圖形的時候，最多將N= 100個與節點最相似的點與該節點連接起來。這樣的處理可以降低運算量和存儲空間。在第一個例子中，搜集1000個視頻廣告和電視節目，並且保存所有原來的文字網頁。使用關鍵字「紅色吉普車」，利用本發明的搜尋引擎進行搜索的搜索結果首頁如圖5所示，錯誤率僅為4% (比如右下角紅色的轎車)。作為對比，同樣使用關鍵字「紅色吉普車」，利用現有視頻搜尋引擎進行搜索的搜索結果首頁如圖6所示，錯誤率高達18%。產生錯誤的主要原因是文字標籤有誤。在第二個例子中，搜集網球比賽視頻，並且保存所有原來的文字網頁。搜索條件是 「穿藍色上衣的網球運動員正面擊球」，利用本發明的視頻搜尋引擎進行搜索的搜索結果首頁如圖7所示，錯誤率僅為20%。作為對比，搜索條件同樣是「穿藍色上衣的網球運動員正面擊球」，利用現有視頻搜尋引擎進行搜索的搜索結果首頁如圖8所示，除了第一個，其餘的搜索結果全部為錯誤的。可擴展性除了高質量的搜索結果，另外一個衡量海量視頻搜尋引擎的標準是搜尋引擎的可擴展性。網際網路上的視頻是日益增長的三維數據。表1示出為了搜索每TB的視頻數據，本發明的搜尋引擎需要的存儲空間。存儲空間越小，則搜尋引擎的可擴展性越強，越能處理海量數據。表1每TB視頻數據所需要的索引數據存儲量
1權利要求
1.一種視頻聚類方法，其特徵在於，包括聚類步驟，用於針對視頻中的每一幀進行聚類，即將相似度高於預定閾值的多個像素聚類到一起以得到超像元，其中，所述相似度是根據像素的顏色、位置和/或運動特性來計算的。
2.根據權利要求1所述的視頻聚類方法，其特徵在於，每個像素以N維向量表示，其中 N為大於3的整數，該N維向量中的元素包括該像素的顏色、位置和/或運動特性，並且，所述相似度通過兩個N維向量之間的距離來計算。
3.根據權利要求1或2所述的視頻聚類方法，其特徵在於，在所述聚類步驟之前還包括預處理步驟，所述預處理步驟用於針對視頻中的每一幀， 將該幀中具有特定屬性的像素聚類到一起以得到像素區域，其中所述特定屬性包括像素的顏色和/或灰度，以及，針對通過所述預處理步驟所產生的每一像素區域進行所述聚類步驟。
4.一種排序方法，用於對通過根據權利要求1 3中任一項所述的視頻聚類方法所得到的超像元進行排序，其特徵在於，包括步驟一對各超像元賦予初始的排序值，其中，該初始的排序值不等於零； 步驟二根據各超像元的排序值計算公式，利用各超像元當前的排序值，計算各超像元新的排序值；步驟三重複步驟二，直到各超像元的排序值收斂。
5.根據權利要求4所述的排序方法，其特徵在於，所述排序值計算公式如下
6.一種視頻搜索方法，其特徵在於，包括 獲取步驟，用於搜集視頻；聚類步驟，利用根據權利要求1 3中任一項所述的視頻聚類方法，對通過所述獲取步驟所搜集到的每個視頻進行聚類；排序步驟，利用根據權利要求4或5所述的排序方法，對通過所述聚類步驟所得到的每個視頻的每個超像元進行排序；關鍵字提取步驟，用於針對通過所述聚類步驟所得到的每個視頻的每個超像元或超像元組，基於該超像元或超像元組的特定特徵為該超像元或超像元組賦予文字屬性標籤，其中，該特定特徵包括該超像元或超像元組的視頻特徵、視頻內容識別和/或視頻內容主體分類；以及索引步驟，用於根據所述關鍵字提取步驟賦予每個視頻的每個超像元或超像元組的文字屬性標籤，針對每個視頻建立索引。
7.一種視頻聚類裝置，其特徵在於，包括聚類部，用於針對視頻中的每一幀進行聚類，即將相似度高於預定閾值的多個像素聚類到一起以得到超像元，其中，所述相似度是根據像素的顏色、位置和/或運動特性來計算的。
8.根據權利要求7所述的視頻聚類裝置，其特徵在於，每個像素以N維向量表示，其中， N為大於3的整數，該N維向量中的元素包括該像素的顏色、位置和/或運動特性，並且，所述相似度通過兩個N維向量之間的距離來計算。
9.根據權利要求7或8所述的視頻聚類裝置，其特徵在於，還包括預處理部，所述預處理部用於針對視頻中的每一幀，將該幀中具有特定屬性的像素聚類到一起以得到像素區域，其中，所述特定屬性包括像素的顏色和/或灰度，以及，所述聚類部針對通過所述預處理部所產生的每一像素區域進行聚類。
10.一種排序裝置，用於對通過根據權利要求7 9中任一項所述的視頻聚類裝置所得到的超像元進行排序，其特徵在於，包括初始化部，用於對各超像元賦予初始的排序值，其中該初始的排序值不等於零；以及計算部，用於根據各超像元的排序值計算公式，利用各超像元當前的排序值，計算各超像元新的排序值；其中，所述計算部重複進行所述計算，直到各超像元的排序值收斂為止。
11.根據權利要求10所述的排序裝置，其特徵在於，所述排序值計算公式如下
12.一種視頻搜索裝置，其特徵在於，包括 獲取部，用於搜集視頻；根據權利要求7 9中任一項所述的視頻聚類裝置，用於對通過所述獲取部所搜集到的每個視頻進行聚類以得到超像元；根據權利要求10或11所述的排序裝置，用於對通過所述視頻聚類裝置所得到的每個視頻的每個超像元進行排序；關鍵字提取部，用於針對通過所述視頻聚類裝置所得到的每個視頻的每個超像元或超像元組，基於該超像元或超像元組的特定特徵為該超像元或超像元組賦予文字屬性標籤， 其中，該特定特徵包括該超像元或超像元組的視頻特徵、視頻內容識別和/或視頻內容主體分類；以及索引部，用於根據所述關鍵字提取部賦予每個視頻的每個超像元或超像元組的文字屬性標籤，針對每個視頻建立索引。
全文摘要
本發明涉及視頻信息領域，公開了一種視頻聚類方法、排序方法和視頻搜索方法以及相應裝置。該視頻聚類方法包括聚類步驟，用於針對視頻中的每一幀，將相似度高於預定閾值的多個像素聚類到一起，以得到能夠模擬人類視覺的最小實體的超像元，其中，所述相似度是根據像素的顏色、位置和/或運動特性來計算的。通過基於能夠模擬人類視覺的最小實體的超像元對視頻中的像素區域進行時空域自相關和互相關分析、排序，本發明即使針對海量視頻庫也能夠達成實時、精確的視頻搜索。
文檔編號G06F17/30GK102542066SQ20121000197
公開日2012年7月4日 申請日期2012年1月5日 優先權日2011年11月11日
發明者冉陽 申請人:冉陽