1. Abstract

2. Introduction

首先，我們要先了解 shot change 的一些型態，目前已知較有名的是 Hard cut、Fade、Dissolve等：

• Hard cut ，顧名思義就是說這個是一個很明顯的變換，現在這個frame 和下一個frame 完全不一樣，很直接的就換了畫面。
• Fade，不像 hard cut一樣是那麼的直接換了畫面，它的畫面切換方式是漸漸改變的，比方說漸漸的暗掉，然後再從一個黑的畫面漸漸的亮起來，變成另外一個場景了。
• Dissolve，比fade還更”混淆”，他是兩個場景在同一時間出現，同時混合，一個漸漸沒有，一個漸漸出來，最後變成另一個場景：

上圖，黑色的線是原本的場景，黃色的線是等一下將變成的場景，它們是混在一起的，也因此幾乎是很難去偵測有了變化，兩個frame之間幾乎一樣，這一種的shot change目前沒有較可靠的algorithm可以有較可靠的偵測。不過還好，在現實生活中的影片，有超過90%是屬於hard cut，另外的10%是其它種類，dissolve尤其少見，通常是刻意的攝影技巧造成的，也因此，雖然dissolve目前偵測不太準，但還沒那麼遭糕。

以下將針對各種shot change介紹常用的偵測方法：

1. 首先是 hard cut，這種型態的shot change是最普遍常見的，也是較好偵測的。Color histogram differences，這個algorithm的想法是說，如果場景沒有變化的話，那麼兩個frame的顏色分怖不會差太多，因此我們可以比較兩兩frame之間的顏色分怖，如果超過一個threshold，則判定為有shot change。
   
   CHD即兩兩frame相比較的值，代表的是兩個 frame間顏色的histogram差，超過一個值即可能為shot change，詳細的利用將在下面說明。
   
2. 再來是dissolve，這種型態的變化將不能用顏色的分怖來偵測了，因為場景的變換是由漸漸變暗，然後亮出來( 或是變亮然後暗回來)變成另外一個場景了，這樣的話，兩個frame之間的顏色分怖將只有微小的變化，因此，我們改用標準差來偵測(Standard Derivation of Pixel Intensities)，這個algorithm的想法是，一個"正常"的畫面，應該會有許多的顏色，所以顏色的分怖就會較廣，也因此顏色分怖會有個標準差的值，如果畫面是一片黑或一片亮，則標準差就會接近零，所以：
   
           
   
   縱軸是標準差，橫軸是frame，我們看到當標準差接近0，就是說畫面差不多是一片黑色或是一片白色，而如果標準差從接近零漸漸變大，就是畫面漸漸的跑出來，相對的，標準差從大變小就是畫面漸漸的消失(變一片暗或一片亮)。如上圖，在標準差有變化的地方，我們偵測出有 fade型態的shot change。
   
3. 再來是dissolve，如之前說的，這種型態的shot change 很難偵測，有許多專家試著要找出個 algorithm來偵測，不過目前為止的正確率並不好，且誤判率太高，還沒有個有效的 algorithm可以較正確的偵測它。

 

3. Implementation

接下來將介紹我所作的事情，我將實作Color histogram differences來偵測hard cut的 shot change。首先，我們先介紹這個algorithm的作法，如之前簡介過的，它偵測 cut 的原理是利用一個觀念 ”如果場景沒有變化的話，那麼現在的frame和下一個frame的顏色應該不會差太多”，因此我們就把影片一個一個frame抓進來，分別去算出每個frame的顏色分怖，接著兩兩相減看看，如果其顏色分布差超過一個threshold 則有可能為 cut ，而下面將介紹我所用的兩種方法：

◎法一 ( 訂定 threshold，合併相近的 )：

我們要如此做時就有個技巧，有時候說不定明明沒有換場景，只是因為頭轉個方向，所以臉上的顏色變暗了點，就以為顏色變化了，而判定有shot change，就造成了誤判。所以我們為了讓它不要太過 "敏感"，可以將顏色減少，本來一個 pixel 的顏色可以分成 RGB 三個顏色分別介於 0~255 之間，我們定義 0~63 之間是同一個顏色，64~127、128~191、192~255 也分別是一個顏色，所以原本 0~255 有 256種顏色，現在變成只有 4 種顏色了，也就是 R有4種、G也4種、B也4種，結論是我們重新定義的顏色將只有 64 色 (RGB分別4種， 4*4*4 =64)。

接著，當我們收到一個frame，分別去讀取該frame上的每一個pixel，看看他是什麼顏色，創一個 64 長度的array Color_count[64]，代表那64色，讀到一個顏色，就把對應的array的值加一，也就是計算出這一個frame上，每一個顏色出現過幾次，儲存在 Color_count[64] 這個 array。每一個frame都分別計算自己的Color_count[64]值，接下來就可以算 CHD 值了：

for (i=2 ; i<=m_frame_no ; i++){         for (j=0 ; j<64 ; j++){              CHD[i-1] += (float)abs(color_count1[j]-color_count2[j]) ;         }         CHD[i-1] = CHD[i-1] / (m_height * m_width);      }

將1和2，2和3，… n 和 n+1 的frame分別兩兩相減，求出其 CHD值( 介於 0~1 間 )，並outpout出來，大概形如：

0.151681 1 0.108404 2 0.232221 3 0.255824 4 0.189063 5 0.259186 6 0.123816 7 0.130871 8 0.061435 9 0.012902 10 0.022348 11 0.028835 12 0.716193 13 0.840696 14 0.187263 15 0.027391 16 0.027628 17

例如 0.716193 13 就是說第 13 和第 14 frame 的 CHD 差距達到 0.716193 ，所以可見得 13和14 frame的顏色有很打大的差別，很有可能是場景變換了。既然有了一個影片的兩兩frame間的CHD值了，我們就可以試著去偵測 cut 了，首先我們必需要定出個 threshold 來判定超過該值的即為 cut，而這個threshold 將可由 try-and-error 來試著找出個較為理想的值。經由篩選過後，我們得到的結果類似下面：

737 740 742 743 744 1126 1495 1496 1567

我們發現有一個缺陷，那就是有時候會有許多很相近的frame，連續的被我們判定為 cut，然而在現實生活中的影片，除非是刻意做的特效，不然是不太可能會有連續的一直換畫面，因此我們應該要把相近的合起來，這一整塊是個gradual shot change(漸漸的場景變化)。然而這也不太有用，因為如之前所說的，利用顏色變化將無法偵測 fade和 dissolve那種兩兩frame間差距不大的 shot change type，如果真的偵測出來了，也要是因為真的剛好它兩兩間的frame顏色有差到一個值，所以才被我們偵測出來。不管如何，由於畫面並不太可能在短時間內有那麼多連續的變化，我們還是要把他合成 gradual shot change，可以定義一個值，如果兩兩結果的差在這個值內，就可以合併。再經由進一步的處理後，可以得到形如下的結果：

<!DOCTYPE refSeg SYSTEM "shotBoundaryReferenceSegmentation.dtd"> <refSeg src=".mpg" creationMethod="MANUAL" totalFNum="56718"> <trans type="GRAD" preFNum="351" postFNum="360"/> <trans type="CUT" preFNum="371" postFNum="372"/> <trans type="GRAD" preFNum="738" postFNum="745"/> <trans type="CUT" preFNum="1126" postFNum="1127"/> <trans type="GRAD" preFNum="1495" postFNum="1497"/> <trans type="CUT" preFNum="1567" postFNum="1568"/> <trans type="CUT" preFNum="2374" postFNum="2375"/> <trans type="CUT" preFNum="2564" postFNum="2565"/> <trans type="CUT" preFNum="2785" postFNum="2786"/> <trans type="GRAD" preFNum="3216" postFNum="3218"/> <trans type="CUT" preFNum="4311" postFNum="4312"/> <trans type="CUT" preFNum="4745" postFNum="4746"/> </refSeg>

我們把他output 成 XML 的形式，因為等下將可利用 Trecvid 機構的sample影片以及標準答案來憑斷所做的結果(才有公信力)，我採用的是Trecvid2003，並測試了其中 3 個影片。下圖為法一的流程：

◎ 法二( 向旁邊的frame比較 )：

由於後來又有看到了 paper 用這個方法，所以也試著做看看。

這個方法的想法是，如果某兩個frame之間是個 cut ，那麼它將符合兩件事：

1. 該 frame 應該是往前後 w 個frame 裡面(共 2w+1 frame 裡面) CHD 值最大的。
2. 而且它的值還應該要是旁邊那 2w 個 CHD 值的平均的某個 alpha 倍以上。

所以我們就可以把法一做出來的 CHD 值的檔案，拿來跑這個方法了，發現正確率有提升，不過誤判率卻也變高了。

 

4. Experimental Results

我試了 19980203_CNN.mpg (31:12)以及 19980224_ABC.mpg (28:28) 和 20010614.1647460.mpg (20:04) 這三個影片，其中前兩個是播報新聞的影片，第三個是一個在演講廳的影片。

◎ 法一：

Trecvid2003的程式將會分成兩種結果：cut和gradual，而我們將注視於 cut 的結果而已，因為看 gradual的是不太有意義的，理由是我們使用 color histogram difference 本來就會不太偵測的出來 fade、dissolve 、以及除了這三種以外的其他類，所以就算偵測出來，也只是運氣好，剛好這個漸漸變化的 gradual shot change 中有兩兩相差比較大，因此我們找出的gradual shot change 本來就只會是冰山一角，有找到是剛好它真的有變化較大，所以gradual 出來的正確率對我們是沒有意義的。我們之前要把相近的結果合在一起成gradual，可以說只是要將它們排除掉，以免影響到 cut 的結果。經由多次的測試 threshold 以及多接近的 CHD該合併，最後找出較好的結果是 threshold = 0.25 以及相差在 10 frame內的就合併，出來的結果如下：

影片	Cut 數量	正確率	誤判率
19980203_cnn.mpg	290	75.5 %	27.2 %
19980224_abc.mpg	299	86.9 %	36.4 %
20010614.1647460.mpg	8	100 %	0 %

【說明】：正確率 = (我們找到且真正屬於正確答案的 cut 數) / ( cut 數 )

                    誤判率 = (我們找到是 cut 但卻不是正確答案的 cut 數 ) / (cut 數 )

其中 20010614.1647460.mpg 這個影片， 20分鐘只有 8次場景轉換，而且它除了 cut 外，完全沒有其他的形態了，也因此我們成功的完全找到正確結果。而另外兩個影片，就比較沒有那麼正確了，原因是，我有去比較看過為什麼該有的結果確沒有抓出來，發現有一個 cut 它的 CHD 值居然只有 0.04 ，因此當然不會被找出來，我去追蹤影片中該frame，發現這是一個很黑的夜晚，雖然場景變了，可是畫面確差不多都是一片很黑，所以才會被判定兩個frame的顏色變化不大也就抓不出 cut 了。

至於不該是cut 的卻判斷出是 cut 原因則有許多，很有可能是剛好這是一個很動態的畫面，雖然是在同一個場景，但是因為太動態了，瞬間的顏色變化太大，又或是剛好一片雲通過把陽光遮住，畫面變的較灰暗，等下雲又飄走了，突然畫面又變亮了，可是卻其實在同一場景。又或是 gradual 消的沒有完全，比方：

310 ~350 整個是一個 fade 或 dissolve等 gradual shot change，我們如果視相差10以內要合併，則會變 [310~318]是gradual , 332是cut，[345~350]是gradual，如此一來我們就沒有消完全， 332 就被誤判為 Cut 了。

◎ 法二：

影片	Cut 數量	正確率	誤判率
19980203_cnn.mpg	290	89.3 %	52.7 %
19980224_abc.mpg	299	95.3 %	54.5 %
20010614.1647460.mpg	8	100 %	0 %

我們發現正確率有提升了，然而誤判率卻也跟著升高，而推其原因我想可能是因為：

351	352	353
354	355	356
357	358	359
		0.000000 350 0.637334 351 1.211742 352 0.703835 353 0.331700 354 0.167756 355 0.091335 356 0.478788 357 1.208191 358 0.289276 359 0.140720 360 0.075071 361
360

從左上角往右看分別是 351~ 360 frame，我們可以看到352 , 359 這兩個CHD符合了法二要的兩個條件，也因此被判定為cut ，然而這整個 351~ 360 應該是一個 gradual 的變化，而不是有cut，由於我們不像法一會把超過某個threshold的frame中，相近的合併，藉以排除掉可能是在gradual中誤判是cut的。因此如果有 gradual中的某幾個 CHD真的達到了那兩個條件，也就會誤判，而至於改善方法就是，除了做cut 外，還要做gradual的偵測，然後把gradual的結果中有判定是cut的拿掉那樣。而另一個缺點是，由於有window的關係，假如真的有連續的 cut發生，在那附近將只會有一個人被抓出。

而關於這個缺點，我本來的想法是說，是不是可以說，當 CHD 值超過一個 threshold後，就不用管 window了，然而這邊卻有一個反例：

50847	50848	50849
50850	50851	50852
50853	50854	50855

結論是，想要偵測 cut ，只用顏色的話，只可以抓個大概，而用來用去，往往會有一好沒兩好，一方面改善了，卻又漏出了其他的缺點，想要cut 偵辦的好，勢必要有其的的方法來輔助。

5. Future work

由於 threshold 在某些情況下並不是每個影片都適用的，所以可能可以想辦法不要只是定下了一個公用的 threshold ，相對的，經由影片的變化，逐漸的一直算出較合適的 local threshold [3]。也許可以想出其他偵測 Cut 的方法( 比方說用 edge 的變化 )，一起來求結果。而由於只用顏色來判斷 cut，很容易會和其他種類的 type 影響，也可去實作偵測其他type 的 shot change，得到 gradual 的結果，再拿來扣除掉在 color histogram difference誤判的，以得到較正確的結果。而也可以考慮加入聲音的辨識，來輔助判斷是否有 shot change，這都是可以發展的目標。

6. References

[1] Comparison of Automatic Shot Boundary Detection Algorithms, Rainer Lienhart1, Microcomputer Research Labs, Intel Corporation, Santa Clara, CA 95052-8819, Rainer.Lienhart@intel.com
[2] J. Canny. A Computational Approach to Edge Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 8, No. 6, pp. 34-43, Nov. 1986.
[3] B.-L. Yeo and B. Liu. Rapid Scene Analysis on Compressed Video. IEEE Transactions on Circuits and Systems for Video Technology, Vol. 5, No. 6, December 1995.
[4] New Enhancements to Cut, Fade, and Dissolve Detection Process in Video Segmentation. Ba Tu Truong Department of Computer Science Curtin Unversity of Techonology GPO Box U1987, Perth, 6845, W. Australia truongbt@cs.curtin.edu.au