智慧型影像監測系統之物體追蹤
902519 曾惠淇
Advisor : 賴尚宏 教授
一、研究目的
這個計畫主要目的是應用在監視系統上，建立出一個安全性的監視系統，能夠追蹤所有在鏡頭裡移動的物體的軌跡，能夠進一步作一些判斷來發現可能正有犯罪意圖的人，或是作一些分析以獲得其他所需的資訊。
二、研究問題簡介
一般監視系統拍攝影片時，攝影機是靜止沒有運動的，且背景相對於攝影機也沒有整體的位移產生(靜止背景)，如此得到一段連續影像。如何在這一連串的影像序列中，建立背景影像並偵測出移動的物體，然後將移動的物體個別分離出來並且追蹤它們，這便是我們的問題所在。
三、研究方法及步驟
我們系統設計的基礎假設有兩個：
1. 背景相對於攝影機是固定不動的，最多只能容忍輕微的晃動。
2. 影片裡任一畫素中，背景出現的時間，需要比任何單一前景還多。
(因為我們統計是以最常出現的顏色群，當作我們的背景圖素代表，所以若前景出現超出背景，偵測結果將會錯誤。)
我們系統需要影片來回播放三次來完成移動物體偵測與分割。第一次播放，主要是在分析背景，利用交叉的統計長條圖來找出每個圖素在R、G、B、normalized R、normalized G五個色頻中的代表分佈間距；接著利用第一次分析的結果，進行第二次播放的動作，分別將五色頻中，座落在鎖定的背景分佈間距裡的點統計起來，利用所有收集到的背景點，來統計建立五個高斯分佈曲線來代表每一個圖性，並另取每一個曲線的mean值來當作背景代表色；第三次播放，則是實際做移動物體偵測分離。
以下是這個流程的flow chart：
我們將問題分成幾個要解決的步驟：
1. 背景分析
2. 背景統計
3. 前景偵測
4. 陰影及光影變化的消除
5. 克服整體輕微搖動及背景小範圍常規運動
6. 加速系統運算效能
7. 利用Component Labeling來找出Connected Components(框出移動中物體)
8. 追蹤moving objects的track
1. 背景分析
我們將影片分成背景和有運動的前景。
已知假設影片中裡的任一畫素中，背景出現的時間需要比任何單一前景還多，於是我們便可以統計出最常出現的顏色群來當作背景圖素代表。
考慮到可行性和速度的問題，不可能每個pixel都作處理，所以我們需要作quantize和長條圖(histogram)統計，求出背景中每個pixel在五個色頻中分佈的主區間，五色頻分別為紅、藍、綠(由影片中直接取得)、正規後的紅、正規後的藍(分別用紅藍原色除以三色頻的總合)。
在實作上，我們假設五個色頻之間的關係是獨立，即其分佈機率可由五個分佈曲線求出再相乘得到。在統計時，我們將五色頻獨立分開做，在採計資料時， quantize將值域等分16部份來當作我們每個bin的橫跨區間（例如R分佈在0-255之間，所以每個bin表示16個色值）。在這邊，我們利用一個交叉的長條圖來做統計，因例如我們取0~15為一個bin、16~31為下一個，若我們的背景資料分佈於14~19，不論我們取哪一個bin當做有興趣的間距，都會造成捨棄上的誤差，造成統計出來的mean值偏離，而variance也被低估，所以，也就是我們在上述的兩個bin中，插入一個bin負責統計8~23的分佈，理論上，如剛所述主要分佈於14~19的背景，會讓8~23的bin大於0~15和16~31兩個，我們就能避免掉因為quantize所產生的邊緣問題。
在影片跑過一次後，我們分別針對每個pixel的每個色頻，在31個interval（16個正常間距、15個跨組間距）所統計到的個數，鎖定一個最多份佈的區間，當作我們背景分佈的鎖定區域，也就是假設所有這個區間以外的顏色分佈，為其他雜亂前景。
2. 背景統計
有了背景中每個pixel在五個色頻中分佈的主區間後，就可以進行統計工作，產生高斯分佈，建構背景分佈模型。當我們在做實際上移動物體偵測的時候，就可以有個參考的機率分佈，判斷為前景還是背景。
取每個點統計出的mean值為代表色，我們即可得到一個不含前景的背景圖像。而取得的高斯分布可幫助我們依每個pixel在不同色頻上的變異量訂出前景的threshold。
實作上，我們可以分別累加輸入值和其平方，並紀錄已經納入多少個點，只要保留這些資訊，而不用真的將每個值的分佈先暫存下來，我們就可以用此三值求得mean、variance。
3. 前景偵測
我們假設五色頻的分佈都是各自獨立的，即機率分佈各自沒有相對關係， 於是將一張影像中的每一個像素跟都背景像素的五色頻相比，若落於背景分佈的容忍範圍內，就將之歸為背景，反之為前景。即若輸入的色彩資訊，對比於其同一位置的背景模型，若距mean值左右在標準差的某個倍率內，則判定其為背景，反之為前景。
為了速度與準確率的考量，我們先只考量RGB三個色頻，在沒有大規模光影變化或是攝影機雜訊的情況下，我們就能得到不錯的結果，而且也在這一部份，把大部份背景點給刪除。
4. 陰影及光影變化的消除
由於陰影及光影變化主要都是亮度變化，並不會影響組成色的比例，因為我們可以將所以判定為前景的點，再用normalized R和normalized G這兩色頻去檢驗，若發現和背景組成比例類似的，就改判為背景。normalized R和normalized G這兩色頻所代表的資訊是R和G在RGB中的組成比例。
5. 克服整體輕微搖動及背景小範圍常規運動
影片中難免會有攝影機的小晃動，或背景中有一些物體如樹會來回作常規的小幅度擺動，這可能會影響邊界會有一些錯位產生雜點。我們可以到輸入的前景點對應到的背景點附近，找一個最相似的背景點分佈，若這個點的高斯分佈能容忍這個前景，即改判為背景，或取前景點附近跟背景點最相似的點，改判斷這個點和背景分佈的差異，若能找到一點在容忍範圍內，則改判為背景。
6. 加速系統運算效能
統計背景模型時，不需要每一張影像、圖素都做，只要間隔取一定張數，就可以很容易的取得有代表性的背景分佈。由一個像素代替附近小local window也能使速度加快許多。
7. 利用Component Labeling來找出Connected Components(框出移動中物體)
前面5個步驟做完後，就能找出所有被判定為前景的部分了，但此時所得到的前景結果，除了移動的物體外，仍然有許多小雜點的雜訊干擾。為了能偵測出移動的物體，然後將移動的物體個別用框框分離出來並且追蹤它們，此時需用Component Labeling來找出有大面積的Connected Components(相對於小雜點)。
Component Labeling 簡略的Algorithm如下：
| Recursive Connected Components Algorithm 1. Scan the image to find an unlabeled 1 pixel and assign it a new label L. 2. Recursively assign a label L to all its 1 neighbors. 3. Stop if there are no more unlabeled 1 pixels. 4. Go to step 1. |
實作上，因受限於影片的解析度的關係，被判定為前景的pixel常斷斷續續，無法完美的形成一個Connected Component，或是有兩個Connected Components重疊而成了一個，使之中會有空隙，因此在assign its neighbors(Step 2)時，有可能遇到已經給其他label了的一小塊component的情形，此時為了增快效率，於是將pixel個數少的那一component的label，全部重新assign成另一個個數比較多的label，使其成一個Connected Component。
8. 追蹤moving objects的track
經由前面7個步驟所判斷出來的前景，還是可能包括不是moving objects前景的光影變化，於是我判斷為moving objects前景的條件是：
1. object的size要有一定程度大小
2. 並且在前一個frame的同位置附近必須也有前景，或是由影片的邊緣進入(表第一次進入，前一個frame同位置附近沒有前景)
將判斷為moving objects前景的中點連續標在影片上，即為其moving tracks。當此moving object離開畫面後(即前一個frame有前景，但現在這一個frame同位置附近沒有前景了)，我便將畫面上所有屬於這個離開的object的track消去。
此步驟在實作上的困難為，由於每個frame中同個moving object被標的label很可能不一樣，所以必須不停的update frame中track，將此moving object所對應到的track(目前是對應到上一個frame的label) update成對應到現在這個frame的object label，如此一來整條track才會屬於同一個moving object，最後要消去track時才能正確消去。
四、實作結果
l 影片一：只有一個moving object的情況。
輸入影片: 輸出影片:
l 影片二：剛好object1離開畫面的同時，object2從同地進入畫面，於是整條track判斷為
同一moving object的track。(把object1和object2當成同一物體，在邊緣迴轉)
輸入影片: 輸出影片:
五、專題製作心得
這次的專題是我第一次接觸到這類型的程式—寫一個智慧型影像監測系統，這是之前在修過的課堂上，寫過的homework、project中，都不曾接觸過的程式類型。學長推薦我可以選擇使用BCB或是VC來當tool，由於要結合學長之前的程式，所以我採用VC。
剛開始接觸到一個全新型態的程式，我花了許多時間在學習、看懂這些新的東西，又由於我的專題只有我一個人一組，所以更需要花加倍的時間來做準備。雖然老師和學長都提供了許多paper可以作為參考，但由於這也是我第一次看paper，很多都是有看沒有懂，於是經歷了一段完全不知道應該如何著手的過渡時期，光是想要把從影片中抓到的frame轉成圖片，寫這種小功能我就寫了3.4天，完全不知道該怎麼寫。
感謝後來學長的指導，再加上我不斷的try& error，終於讓我稍微摸熟了這新的程式，並且開始著手寫我的專題程式，並且得以順利達到我專題的目標。
這次專題我學到許多，因為這次的專題，讓我第一次有讀paper的機會，雖然經常還是有看沒有懂，但至少我跨出了第一步，相信以後讀paper的機會會越來越多，我也能慢慢的駕輕就熟。此外，雖然這次是自己一個人一組，無法體驗到與同伴分工合作一起完成一件project的感覺，但是也讓我學會了如何自己慢慢去看懂前人寫好的code，學會如何de這類程式的bug，學會如何從一個不算小的程式中著手去撰寫、發展自己想要的功能。有些寫了很久的東西，後來寫好以後才發現，其實都是一些很簡單的觀念，只是因為當時不得其門而入，所以才會覺得很困難，但現在經過這次專題之後，我對於tracking of video object motion有了一定程度的了解了，也越來越有興趣了，相信這對於我以後的發展會非常有幫助！