第 28 卷 第 4 期 计 算 机 辅 助 设 计 与 图 形 学 学 报 Vol. 28 No.4 2016 年 4 月 Journal of Computer-Aided Design & Computer Graphics Apr. 2016 一 种 针 对 移 动 相 机 的 实 时 视 频 背 景 减 除 算 法 孙 丰 1,2), 秦 开 怀 1)*, 孙 伟 3) 1), 郭 华 源 1) ( 清 华 大 学 计 算 机 科 学 与 技 术 系 北 京 100084) 2) ( 中 国 卫 星 海 上 测 控 部 试 验 技 术 部 江 阴 214431) 3) ( 陆 航 研 究 所 航 电 研 究 室 北 京 100021) (qkh-dcs@tsinghua.edu.cn) : 提 取 移 动 相 机 拍 摄 视 频 中 的 前 景 时, 采 用 基 于 稠 密 光 流 或 像 素 点 轨 迹 的 算 法 估 算 相 机 运 动 会 造 成 算 法 非 常 耗 时, 为 此 提 出 一 种 简 单 有 效 的 实 时 视 频 背 景 减 除 算 法. 首 先 用 基 于 超 像 素 的 区 域 增 长 预 处 理 算 法 得 到 可 能 是 前 景 的 超 像 素 ; 然 后 基 于 分 块 相 对 光 流 的 背 景 特 征 点 筛 选 算 法 来 估 算 相 机 运 动 ; 最 后 检 查 光 流 与 相 机 运 动 的 一 致 性, 得 到 背 景 减 除 的 最 终 结 果. 实 验 结 果 表 明, 该 算 法 可 以 实 时 处 理 大 小 为 640 480 像 素 的 视 频, 且 前 景 检 测 准 确 度 优 于 同 类 算 法. : 背 景 减 除 ; 移 动 相 机 ; 实 时 ; 区 域 增 长 ; 超 像 素 :TP391.41 A Real-Time Background Subtraction Algorithm for Freely Moving Cameras Sun Feng 1, 2), Qin Kaihuai 1)*, Sun Wei 3), and Guo Huayuan 1) 1) (Department of Computer Science and Technology, Tsinghua University, Beijing 100084) 2) (Department of Experimental Techniques, Satellite Marine Tracking and Control Department of China, Jiangyin 214431) 3) (Avionics Laboratory, Institute of Army Aviation, Beijing 100021) Abstract: To extract moving foreground from a video captured by a moving camera, dense optical flow or point trajectories are often introduced to handle the camera motion, but they make the moving foreground extraction very slow. To solve this problem, a simple and effective real-time algorithm for moving camera background subtraction is proposed. Firstly, a superpixel-based region growing algorithm is proposed to preprocess the input image frames. Then, the camera motion is estimated in a block-based fashion with a background feature-point filtering method based on the relative flow. Finally, the background subtraction result is obtained via a verification process based on the accordance of the optical flow and the camera motion. Experimental results show that the proposed algorithm can process a 640 480 video in real-time. In addition, the foreground detection accuracy of the proposed algorithm outperforms other real-time moving foreground extraction methods. Key words: background subtraction; moving cameras; real-time; region growing; superpixel,,.,,. 2015-04-27 2016-01-12. 基 金 项 目 (20131019394). 孙 丰 (1983 ),,,, ; 秦 开 怀 (1958 ),,,,,, 3D ; 孙 伟 (1983 ),,,, ; 郭 华 源 (1979 ),,,.
第 4 期, 等 : 573, ( ), [1]. ( ),,.,,. [2], 3 [3], (random sample consensus, RANSAC) [4]., [5]., Berger [6],,,, 1.6 s.,,, GPU [7],.,. [8], ;,,. [9],, ;, 300 200 6s. [10],, ;., [10],,. [11],. [12], 2 ;,,.,,,.,.,.,.,, ;,,, ;.,, GPU CPU., [10]. [13],, ; [13], [13]., [13] Markov,. 1 本 文 算 法 描 述 1.. 1.1 基 于 超 像 素 的 区 域 增 长,,..
574 计 算 机 辅 助 设 计 与 图 形 学 学 报 第 28 卷 1 2, 2a, 2b (, ). 2a,, ;,. a. b. 2, [14],,., [15]. Step3. While C { Step4. S s, R[i]. Setp5. i++, D=0, N. Step6. While D<T { Step7. s N. Step8. S arg min S ( s, R[ i]). m s N d Step9. D=S d (S m,r[i]), S m R[i], s=s m. Step10. R[i], N S m } Step11. N C }. 1, T T c Dc (1 c) D g. 3. 3a, 3b. 3b,,. 15., 1.2.3,. S ( x, y) c D ( x, y) (1 c) D ( x, y) (1) d c g, D c ( x, y), D g ( x, y ). RGB 4 096, 36., (1), c,, c Dc /( Dc Dg), D c, D g. 算 法 1.. I S T.. R. Step1. i 0, C. Step2. C. a. b. 3 1.2 运 动 一 致 性 验 证 1.2.1, (Kanade-Lucas- Tomasi, KLT) [16].,,. [10],, RANSAC.
第 4 期, 等 : 575,, [17]., X ( x, yzw,, ), p. p QX K[ I 0] X ;, K, Q 3 4. R T, X, p K [ R T] X, p p. 2 : 1), p KRX, 1 p KX, p ( KRK ) p HR p, p p H R. 2),, z=0. Q 3, p [ Q1, Q2, Q4] X HX, p [ Q1, Q2, Q4 ] X HX, 1 p ( HH ) p H p. p p H. 2,. RANSAC, RANSAC.,. I 1, I 2 p, p, I 1 A,, I 1 p b A ; I 2 p b A p b A, V b pb A Vb pb A (2) 2 Vb Vb t T p f, 2 f, V f V (2);, Vf pf AV, f pf A. (2). t (2). 4,,., (2)., t 1.0. 2 A A arg min Vpa V p a,, Vpa p a., P e p b, pb F Pe 100. p b Hopkins [18] 10, RANSAC., 2 1.0. P e 0.32%, RANSAC P e 0.36%. 4,,,. 1.2.2,,., A,, a p 4
576 计 算 机 辅 助 设 计 与 图 形 学 学 报 第 28 卷 N A p B, pb N A. 算 法 2.. I 1, I 2 F, N, F min.. H. Step1. I 1, I 2 N N Step2. For i=1: N N { Step3. H[] i,. Step4. i r=1 P(i,r). Step5. i N i P B H[ N] pb P(i,r). Step6. r P(i,r) F min. Step7. P(i, r) h, H[ k] h}., 3 3 8, 4., 10.,. 1.2.3, KLT,. p ( x, y,1) i, 2 H T T ph H[] i p ( wx, wy,1), p pf ( dx, dy). 2 2 D xy, ( wx dx x) ( wy dy y). D xy, T fg,,. T fg 2.0. 2 实 验 及 结 果 分 析 GPU CPU, C++, CUDA OpenCV,, GPU [15], OpenCV GPU KLT. Intel i7 3.5 GHz CPU, NVIDIA GeForce Titan GPU., Hopkins,,., 1 600, 8 8 64,. [8,10], 5. 5a Hopkins a. b. c. [8] d. [10] e. 5
第 4 期, 等 : 577 Cars1 6, Cars3 11, Cars8 16, People1 19 Peopel2 16. 5b 5a, 5c [8], 5d [10], 5e. [9] : P, R F (F-score, F), [10] 1.,,,, [10]. 640 480 28 /s, ; [10], 45 /s,,.,. 表 1 同 类 算 法 前 景 准 确 率 结 果 及 比 较 [10] P R F P R F Cars1 0.653 0.979 0.783 0.640 0.336 0.441 Cars2 0.727 0.706 0.716 0.399 0.130 0.196 Cars3 0.742 0.877 0.804 0.640 0.210 0.316 Cars4 0.694 0.627 0.658 0.676 0.271 0.387 Cars5 0.686 0.720 0.703 0.724 0.152 0.251 Cars6 0.620 0.682 0.650 0.726 0.190 0.302 Cars7 0.687 0.957 0.800 0.657 0.287 0.399 Cars8 0.692 0.975 0.810 0.653 0.447 0.531 People1 0.486 0.861 0.621 0.887 0.497 0.637 People2 0.732 0.866 0.794 0.834 0.602 0.699 0.680 0.829 0.747 0.664 0.300 0.414 3 结 语.,,.,,,,,,.,,,., ;,.,.,,,,.,,,. 参 考 文 献 (References): [1] Bouwmans T. Traditional and recent approaches in background modeling for foreground detection: an overview[j]. Computer Science Review, 2014, 11/12: 31-66 [2] Sheikh Y, Javed O, Kanade T. Background subtraction for freely moving cameras[c] //Proceedings of the 12th IEEE International Conference on Computer Vision. Los Alamitos: IEEE Computer Society Press, 2009: 1219-1225 [3] Tomasi C, Kanade T. Shape and motion from image streams under orthography: a factorization method[j]. International Journal of Computer Vision, 1992, 9(2): 137-154 [4] Fischler M A, Bolles R C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography[j]. Communications oft he ACM, 1981, 24(6): 381-395 [5] Cui X Y, Huang J Z, Zhang S T, et al. Background subtraction using low rank and group sparsity constraints[c] //Proceedings
578 计 算 机 辅 助 设 计 与 图 形 学 学 报 第 28 卷 of the 12th European Conference on Computer Vision. Heidelberg: Springer, 2012, Part I: 612-625 [6] Berger M, Seversky L M. Subspace tracking under dynamic dimensionality for online background subtraction[c] //Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2014: 1274-1281 [7] Sundaram N, Brox T, Keutzer K. Dense point trajectories by GPU-accelerated large displacement optical flow[c] //Proceedings of the 11th European Conference on Computer Vision. Heidelberg: Springer, 2010, Part I: 438-451 [8] Kawk S, Lim T, Nam W, et al. Generalized background subtraction based on hybrid inference by belief propagation and bayesian fltering[c] //Proceedings of IEEE International Conference on Computer Vision. Los Alamitos: IEEE Computer Society Press, 2011: 2174-2181 [9] Lim J W, Han B H. Generalized background subtraction using superpixels with label integrated motion estimation[m] //Lecture Notes in Computer Science. Heidelberg: Springer, 2014, 8693: 173-187 [10] Yi K M, Yun K, Kim S W, et al. Detection of moving objects with non-stationary cameras in 5.8 ms: bringing motion detection to your mobile device[c] //Proceedings of IEEE Conference on Computer Vision and Pattern Recognition Workshops. Los Alamitos: IEEE Computer Society Press, 2013: 27-34 [11] Qian Sheng, Zhan Chenbin, Chen Zonghai, et al. A background subtraction algorithm based on biological vision characteristics[j]. Journal of University of Science and Technology of China, 2014 44(4): 270-277(in Chinese) ( 钱 生, 张 陈 斌, 陈 宗 海, 等. 基 于 生 物 视 觉 特 性 的 背 景 减 除 算 法 [J]. 中 国 科 学 技 术 大 学 学 报, 2014, 44(4): 270-277) [12] Cui Zhigao, Li Aihua, Feng Guoyan. A moving object detection algorithm using multi-frame homography constraint and Markov random fields model[j]. Journal of Computer-Aided Design & Computer Graphics, 2015, 27(4):621-632(in Chinese) ( 崔 智 高, 李 艾 华, 冯 国 彦. 采 用 多 组 单 应 约 束 和 马 尔 可 夫 随 机 场 的 运 动 目 标 检 测 算 法 [J]. 计 算 机 辅 助 设 计 与 图 形 学 学 报, 2015, 27(4): 621-632) [13] Wang C, Guo Y W, Zhu J, et al. Video object Co-segmentation via subspace clustering and quadratic pseudo-boolean optimization in an MRF framework[j]. IEEE Transactions on Multimedia, 2014, 16(4): 903-916 [14] Verma O P, Hanmandlu M, Susan S, et al. A simple single seeded region growing algorithm for color image segmentation using adaptive thresholding[c] //Proceedings of the International Conference on Communication Systems and Network Technologies. Los Alamitos: IEEE Computer Society Press, 2011: 500-503 [15] Schick A, Fischer M, Stiefelhagen R. Measuring and evaluating the compactness of superpixels[c] //Proceedings of the 21st International Conference on Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2012: 930-934 [16] Tomasi C, Kanade T. Detection and tracking of point features[r]. Pittsburgh: Carnegie Mellon University, 1991 [17] Zamalieva D, Yilmaz A, Davis J W. A multi-transformational model for background subtraction with moving cameras[m] //Lecture Notes in Computer Science. Heidelberg: Springer, 2014, 8689: 803-817 [18] Tron R, Vidal R. A benchmark for the comparison of 3D motion segmentation algorithms[c] //Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2007: 1-8