Graph coloring based surveillance video synopsis

Video synopsis is an intelligent condensation approach to solve fast video browsing and retrieval for surveillance cameras. However, collision caused by unsatisfied tube rearrangement in traditional methods brings uncomfortable visual effect to users and how to mitigate the collision still remains an attracting topic. Unlike conventional methods that deal with tube rearrangement by minimizing a global energy function, we propose a novel approach by formulating it as a graph coloring problem. In our approach, all the tubes are firstly mapped into the spatial domain for analyzing their potential collision relationship. The input tube set is then represented by a graph structure, where each node stands for a tube and the edge between two nodes represents the potential collision relationship. To mitigate the collision artifacts, our method finds the mapping of tubes from original video to synopsis video by L(q)-coloring the graph, which separates tubes from their collision points. The parameter q is left tunable to make a compromise between collision artifacts and synopsis length, which can better meet users' demand of freely adjusting the compactness of synopsis video. The shifted objects are finally composited with the background image to obtain the high-quality video synopsis. Extensive experimental results show that the proposed method can generate more compact video synopsis with less collision artifacts than the existing methods.