Visual surveillance produces a significant amount of raw video data that can be time consuming to browse and analyze. In this work, we present a video synopsis methodology called "scene adaptive online video synopsis via dynamic tube rearrangement using octree (SSOcT)" that can effectively condense input surveillance videos. Our method entailed summarizing the input video by analyzing scene characteristics and determining an effective spatio-temporal 3D structure for video synopsis. For this purpose, we first analyzed the attributes of each extracted tube with respect to scene geometry and complexity. Then, we adaptively grouped the tubes using an online grouping algorithm that exploits these scene characteristics. Finally, the tube groups were dynamically rearranged using the proposed octree-based algorithm that efficiently inserted and refined tubes containing high spatio-temporal movements in real time. Extensive video synopsis experimental results are provided, demonstrating the effectiveness and efficiency of our method in summarizing real-world surveillance videos with diverse scene characteristics.