Video Search Using MPEG-7
901533 吳俊良 u901533@oz.nthu.edu.tw
901535 黃琢桂 u901535@oz.nthu.edu.tw
指導教授
賴尚宏
2005/01/18
Project Goal & Introduction
有鑒於多媒體資料的日益龐大，要找到想觀看的多媒體資料必須浪費許多時間，再加上如果是線上觀賞的多媒體影片更常常因為頻寬不足而必許浪費大量時間在等待或找尋真正想看精采鏡頭的部分，而且利用手機及PDA等行動裝置下載影片觀賞已成為一種趨勢，不過行動通訊受限於頻寬及儲存容量限制，很難迅速且完整的觀賞完整影片，我們專題的目的即希望能藉由MPEG-7的相關應用來實現Video
Search的目標，讓使用者可以即時下載或線上觀賞想要觀賞的片段，讓所有的影片搜尋都在Sever端處理，使用者僅需選擇想要觀賞的訊息。
實作的目標是善用VideoAnnEx產生出來的資訊，期望能在使用者輸入關鍵字、時間長短或者是影片的性質，與Annotation資料作一些比對和計算，而在眾多片段中，輸出幾個較適合的片段出來，提供給使用者參考。底下介紹我們的流程如下圖）及做法：
System & Algorithms Description
主要可以分為底下幾個項目
1.
Video
Sources
我們選擇以MPEG-4
Video *.mpg作為我們的處理檔案格式，處理影片種類包括新聞、體育、MTV、電影。
2.
Annotation
Tool
我們主要利用IBM的AnnEx這套免費軟體，經過處理產生相關的訊息來做為我們影像搜尋的根據，該工具可將*.mpeg的影像讀入再經由使用者設定，產生出符合mpeg-7格式的*.mp7.xml檔案，裡頭紀錄了輸入影片的相關Annotation訊息，如：使用者對該影像內容的注解，以及在時間上的切割共有多少frame或是佔多少時間，以及較特殊的region部分。按此可見AnnEx
user interface，按此可見AnnEx輸出的*.mp7.xml檔內容片段。
(AnnEx來源 http://www.alphaworks.ibm.com/aw.nsf/download/videoannex
)
3.
MPEG-7
Parser
MPEG-7
Parser會將*.mp7.xml裡的訊息（如：影像名稱、各個shot的frame數及所佔時間、shot中有哪些keyword以及region座標。）且將訊息做適當的排序給Player使用。
4. Database
Search Engine
我們用的演算法有底下幾個：
1).關鍵字比對 使用者輸入關鍵字與parse後的資料作比對，若有任何shot所帶有的關鍵字與之相符，即代表符合使用者需
求。經過測試，這樣的片段會有很多筆，還需要一些步驟來篩選。
2).將時間點上較靠近的shot合併起來 VideoAnnEx還沒有到達完美的地步，有些shot往往切的過細，為了保持shot的連貫性，應該視情況把他們連接起來，使得撥放時能更加平順連貫。
演算法：假設Ai為符合關鍵字比對的shot，Bi為不符合者，先將兩兩相鄰的Ai與Ai+1合併成Ai’及Bi與B
i+1合併成Bi’，之
後必會形成 Ai’
Bi’相鄰的狀況，若”
Ai+1’的起始時間”與”
Ai’的結束時間”相差太小(假設為20秒)，即將Ai’與Ai+1’及其之間的B’合併，這樣產生的shot較具有參考價值。考慮底下的狀況：搜尋結果在時間上的排列為A1
A2 B1 A3 B2 A4，B1佔30秒，B2佔15秒，則整理後的結果為A1’B1’A2’，其中A1’=A1A2，B1’=B1，A2’=
A3 B2 A4。
示意圖如下：
3).時間比對 使用者輸入所需影像的時間長度，與合併後的shot的時間長度比對，最接近者符合所求。
4).region座標應用 從座標可以得到region的位置與面積大小的訊息。當shot中region面積大於某一設定值(設為30000 pix*pix)且在畫面中間時，列為較有參考價
(此方法配合關鍵字比對可試著找出特寫鏡頭)。
5.
Summarization
System
在我們這個專題的最後就是實際建立一個User
Environment可以讓使用者完成Video
Personalization的目標，我們為此另外撰寫一套可以將Database
Search Engine 所產生符合搜尋條件的合適片段加以結合並且連續撥放的Media
Player。
我們利用Parser所產生的資料設定Player的Start
Frame，End
Frame以及Frame
Rate利用Timer的觀念根據上面三樣東西設定Time
Interval使得Player可以自動Reload下一個片段，如此當使用者選擇好他所想觀賞的影片以及他所設定的觀賞條件，Player就可以將影片中所有符合條件的部分加以連續撥放。雖然我們尚無法將Search
Engine所產生符合搜尋條件的合適片段加以真正結合成另一部完整影片再輸出至使用者的Video
Client，但經由這個Media
Player我們已經可以將Summarization
System的初步模型建構出來，此外這套系統也提供使用者可以跨資料夾以及跨硬碟的多檔案擷取的服務，也就是使用者能同時一次選擇多部存放在不同位置的影片，只要將檔案一次Load進來即可連續觀賞。User
Environment如下圖。
Implementation Details
1).MPEG-7
Parser：
將*.mp7.xml檔中被">"、"<"夾住的資料取出來，即可讀出如檔名、播放速度、Annotation、frame數目、起始時間、region座標等資料。因為上述資料型態有數值、有字串，本應用structure來儲存，但每部影片annotation的數目都不一樣，程式宣告時無法確定structure的大小，所以選擇將資料都寫在一個文件裡，並將annotation相關的各種資料做一些整理，以便播放器識別資料，如：檔名及其路徑前將個"$"、Annotation用大括號"{"、"}"括起來，Parser的OutPut如下圖。另外，parse完成後，將影片裡含有的Annotation名稱整理出來，供兩組方便直接選擇，而user不用打字。
2).找出與使用者輸入時間相近的片段：
將MPEG-7 Parser的輸出做一些後續處理（見上述演算法），並多存一筆資料為（annotation的frame數 - 使用者輸入秒數*30）取絕對值後再排序，挑出該值最小的三組，將其對應到的frame起始點、終點給播放器使用，可找出與使用者輸入時間長短相近的三組影片片段。
3).Close-up Shot：
在針對時間搜尋時，只針對片段中含有region且其面積大於30000者。而region的內容為四個數字，代表兩個座標，分別代表region左上角與右下角兩點，面積很好計算。
4).播Media Player：
依照算出的frame起始點、終點播放片段。
Experimental Results
只靠關鍵字的一般比對，都可以找出合適的片段，在此不多敘述。在這邊主要比較不考慮Close-up Shot（即不應用region資料）時，找出三筆時間長度相符的片段，與考慮Close-up Shot時，找出的三筆資料之間的差異。
測試的影片為"National Geographic Video - Lions of the African Night"，裡面有許多獅子的畫面，和一些其他非洲動物穿插在其中。設定的環境是使用者要尋找含有獅子或青蛙且長度約20秒的影片片段。
1).底下是沒有應用region的三個片段：
2).底下是有應用region的三個片段：
比較結果，1).的三筆搜尋結果裡都沒有含有青蛙的片段。2).的三筆裡，僅一筆含有獅子，且出現頭部近照，而另外兩筆含青蛙的部分，青蛙幾乎都佔滿整個畫面。
2).的結果，顯然都可以找出有Annotation「特寫」的影片，但有一個缺點，由於*.mp7.xml裡並沒有紀錄region佔用的時間長度，所以這些「特寫」佔的時間我們也無法得知，以致於可能會有找出的片段很長（設有5分鐘的池塘片段），特寫的部分卻很短（影片播放到一半才看到僅出現5秒的青蛙特寫，而且也沒見到獅子出現）的情況，會有這樣的結果，應是我們之前把可能相似的片段相連接起來的關係（見上述演算法）。
Conclusion/Discussion
我們利用個人電腦上的多媒體資料作為處理對象，在完成專題的同時，已能完成初步簡單的影像搜尋，例如想找私人電腦中存有孫燕姿在唱歌、陳致遠打全壘打、喬丹灌籃等等的畫面，使用者僅需選擇上述關鍵字就可找到並觀賞這些畫面，不過這個project仍有不少地方需要改進，像是region的部分在製作annotation時在同一個片段中若使用大量且重疊性高的region註解會產生混淆難以比對，使用AnnEx作切割，如果影片的變動性太大，例如每間隔兩三秒就切換場景或是動作加快加大，都會影響切割影片的次數，如果影片被切割的太過瑣碎，則在觀賞的過程中就會不斷有停格的畫面產生，縱使我們已針對這個問題作了連續撥放及自動合併shot的處理，但是畢竟還是無法非常完美的使他平滑，影片無法平順觀賞就影響了撥放品質。這個專題的最終目標是希望讓使用者能線上觀賞及下載，而我們僅完成Sever端的後製處理，要能傳輸影片及符合各項裝置的撥放規格及壓縮技術就有待繼續深入討論。
