Video scene segmentation using a novel boundary evaluation criterion and dynamic programming

Video scene segmentation is a fundamental step for video summarization and browsing, which is a very promising application of multimedia analysis. There are two key elements, namely, boundary evaluation and boundary searching, in a scene segmentation algorithm. In this paper, we propose a novel boundary evaluation criterion, including the multiple normalized min-max cut scores, which consider not only neighboring but non-neighboring scene similarities with a memory-fading model, and the maximal cross-boundary strict shot similarity, which considers both color and structure similarities. Dynamic programming with a heuristic search scheme is adopted to quickly find the global optimal scene boundary sequence. Moreover, a Monte Carlo method is adopted to improve the stability of the searching process. Experimental results on a dataset of 40 diversified videos have proven the algorithm efficient, robust, and superior to the existent methods.