[發(fā)明專利]一種基于譜分割理論的鏡頭聚類方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 200810056096.8
• 申請(qǐng)日: 2008-01-11
• 公開(kāi)（公告）號(hào): CN101216886A
• 公開(kāi)（公告）日: 2008-07-09
• 發(fā)明（設(shè)計(jì)）人: 薛玲;李超;鐘林;李歡;熊璋
• 申請(qǐng)（專利權(quán)）人: 北京航空航天大學(xué)
• 主分類號(hào): G06K9/00
• 分類號(hào): G06K9/00;G06K9/62;G06F17/30
• 代理公司: 北京科迪生專利代理有限責(zé)任公司
• 代理人: 賈玉忠;盧紀(jì)

技術(shù)領(lǐng)域

本發(fā)明屬于視頻內(nèi)容分析與檢索領(lǐng)域，具體涉及一種對(duì)鏡頭進(jìn)行聚類的方法。

背景技術(shù)

視頻鏡頭是指語(yǔ)義上不間斷的一段視頻內(nèi)容，是視頻信息檢索的基本結(jié)構(gòu)和語(yǔ)義單元，對(duì)這些代表視頻語(yǔ)義的單元進(jìn)行聚類是視頻語(yǔ)義分析的基礎(chǔ)。當(dāng)前的聚類算法可以大致分為有監(jiān)督和無(wú)監(jiān)督兩種。有監(jiān)督聚類通過(guò)給定的樣本集對(duì)分類器進(jìn)行訓(xùn)練，分類準(zhǔn)確，但需要人工標(biāo)注樣本集。無(wú)監(jiān)督聚類算法具有自學(xué)習(xí)功能，無(wú)需訓(xùn)練樣本，但面臨著最優(yōu)化分類個(gè)數(shù)很難確定，分類結(jié)果對(duì)初始劃分較敏感等難題。

近年來(lái)，關(guān)于鏡頭聚類方法的研究有很多。目前在視頻鏡頭聚類算法中常用的估計(jì)最優(yōu)化分類個(gè)數(shù)的方法有以下幾種：(1)基于探索模式的評(píng)判準(zhǔn)則，該方法基于一種合適的信息準(zhǔn)則評(píng)判標(biāo)準(zhǔn)，遍歷所有可能出現(xiàn)的分類個(gè)數(shù)情況，得到最優(yōu)化的分類個(gè)數(shù)；(2)基于融合的估計(jì)方法，首先選取一個(gè)遠(yuǎn)大于最優(yōu)分類個(gè)數(shù)的分類數(shù)進(jìn)行聚類，聚類的結(jié)果根據(jù)信息熵最小損失原則相互融合以得到最優(yōu)的分類個(gè)數(shù)；(3)基于k-means的迭代聚類，對(duì)每個(gè)聚類的結(jié)果迭代執(zhí)行k-means算法，采用合適的信息準(zhǔn)則判斷是否終止，當(dāng)所有迭代終止時(shí)得到最優(yōu)的分類個(gè)數(shù)。

第一種方法是最簡(jiǎn)單的，得到的結(jié)果也是最客觀的，但是這種方法計(jì)算復(fù)雜度較高，且在沒(méi)有先驗(yàn)知識(shí)的情況下的搜索范圍必須足夠大。第二種方法分類過(guò)程每次融合后需重新計(jì)算融合的信息熵?fù)p失，收斂速度慢，計(jì)算復(fù)雜度高，并且無(wú)法對(duì)初始分類糾錯(cuò)。第三種方法以X-means為代表，具有收斂速度快，計(jì)算復(fù)雜度小等優(yōu)點(diǎn)，但k-means算法只考慮了類間關(guān)系，可能會(huì)出現(xiàn)將一個(gè)類割裂的錯(cuò)誤，并且沒(méi)有針對(duì)這種錯(cuò)誤的糾錯(cuò)功能。

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問(wèn)題：克服現(xiàn)有技術(shù)的不足，提供一種基于譜分割理論的鏡頭聚類方法，該方法可以在低復(fù)雜度情況下聚類算法中難以估計(jì)最優(yōu)化的分類個(gè)數(shù)，利用精確二分類的譜分割，提高了聚類結(jié)果的查全率和查準(zhǔn)率；提出的全局融合操作，具有對(duì)分類錯(cuò)誤的糾錯(cuò)功能，避免了局部最優(yōu)解問(wèn)題。

本發(fā)明的目的是這樣實(shí)現(xiàn)的：一種基于譜分割理論的鏡頭聚類方法，包括以下步驟：

(1)對(duì)每個(gè)待分類的鏡頭提取其特征向量；

(2)根據(jù)提取的特征向量，計(jì)算每?jī)深愰g的相似度；

(3)將鏡頭集構(gòu)造為一有權(quán)的無(wú)向圖，根據(jù)每?jī)社R頭類之間的相似度，使用譜分割將每個(gè)鏡頭類二分為兩個(gè)鏡頭類；

(4)用貝葉斯信息準(zhǔn)則判定此分割是否有效；有效分割的鏡頭子類迭代分割操作，無(wú)效分割的鏡頭類為終止節(jié)點(diǎn)；

(5)對(duì)譜分割最終輸出的結(jié)果，使用貝葉斯信息準(zhǔn)則判斷兩分類是否連通，根據(jù)連通性進(jìn)行融合，最終得到最優(yōu)聚類數(shù)和聚類結(jié)果。

所述步驟(1)中的特征向量的提取采用HSV顏色直方圖，并計(jì)算整個(gè)鏡頭所有幀的平均顏色直方圖作為該鏡頭的特征向量。

所述步驟(2)中計(jì)算每?jī)社R頭類之間的相似度計(jì)算公式為：

eij=e-||Hi-Hj||22σ2]]>

其中e_ij表示兩類鏡頭i、j之間的相似度，H_i，H_j分別為鏡頭s_i，s_j顏色直方圖，σ為常數(shù)。

所述步驟(3)中的方法為：譜分割的結(jié)果{A，B}滿足下式在全局范圍內(nèi)取得最小值：