Group behavior from video: a data-driven approach to crowd simulation

ABSTRACT

Crowd simulation techniques have frequently been used to animate a large group of virtual humans in computer graphics applications. We present a data-driven method of simulating a crowd of virtual humans that exhibit behaviors imitating real human crowds. To do so, we record the motion of a human crowd from an aerial view using a camcorder, extract the two-dimensional moving trajectories of each individual in the crowd, and then learn an agent model from observed trajectories. The agent model decides each agent's actions based on features of the environment and the motion of nearby agents in the crowd. Once the agent model is learned, we can simulate a virtual crowd that behaves similarly to the real crowd in the video. The versatility and flexibility of our approach is demonstrated through examples in which various characteristics of group behaviors are captured and reproduced in simulated crowds.

REFERENCES

• 1: {ACT05} Abaci T., Cíger J., Thalmann D.: Planning with smart objects. In WSCG (Short Papers) (2005), pp. 25--28. 2
• 2: Aseem Agarwala , Aaron Hertzmann , David H. Salesin , Steven M. Seitz, Keyframe-based tracking for rotoscoping and animation, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 3: Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997 [doi>10.1023/A:1006559212014]
• 4: David C. Brogan , Nicholas L. Johnson, Realistic Human Walking Paths, Proceedings of the 16th International Conference on Computer Animation and Social Agents (CASA 2003), p.94, May 08-09, 2003
• 5: O. Burchan Bayazit , Jyh-Ming Lien , Nancy M. Amato, Better group behaviors in complex environments using global roadmaps, Proceedings of the eighth international conference on Artificial life, p.362-370, December 09-13, 2002
• 6: Stephen Chenney, Flow tiles, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028553]
• 7: Dorin Comaniciu , Visvanathan Ramesh , Peter Meer, Kernel-Based Object Tracking, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.5, p.564-575, May 2003 [doi>10.1109/TPAMI.2003.1195991]
• 8: {EBD*05} Egerstedt M., Balch T., Dellaert F., Delmotte F., Khan Z.: What are the ants doing? vision-based tracking and reconstruction of control programs. In Proceedings of IEEE International Conference on Robotics and Automation (ICRA) (2005). 2
• 9: John Funge , Xiaoyuan Tu , Demetri Terzopoulos, Cognitive modeling: knowledge, reasoning and planning for intelligent characters, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.29-38, July 1999 [doi>10.1145/311535.311538]
• 10: Brett R. Fajen , William H. Warren , Selim Temizer , Leslie Pack Kaelbling, A Dynamical Model of Visually-Guided Steering, Obstacle Avoidance, and Route Selection, International Journal of Computer Vision, v.54 n.1-3, p.13-34, August-September 2003 [doi>10.1023/A:1023701300169]
• 11: {GKM*01} Goldenstein S., Karavelas M., Metaxas D., Guibas L., Aaron E., Goswami A.: Scalable behaviors for crowd simulation. Computer & Graphics 25, 6 (2001), 983--998. 2
• 12: {HMFB01} Helbing D., Molnar P., Farkas I. J., Bolay K.: Self-organizing pedestrian movement. Environment and Planning B: Planning and Design 28 (2001), 361--383. 2
• 13: {Hug03} Hughes R. L.: The flow of human crowds. Annual Review of Fluid Mechanics 35 (2003), 169--182. 2
• 14: Zia Khan , Tucker Balch , Frank Dellaert, MCMC-Based Particle Filtering for Tracking a Variable Number of Interacting Targets, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.11, p.1805-1918, November 2005 [doi>10.1109/TPAMI.2005.223]
• 15: A. Kamphuis , M. H. Overmars, Finding paths for coherent groups using clearance, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028526]
• 16: {KS02} Kirchner A., Schadschneider A.: Simulation of evacuation processes using a bionics-inspired cellular automaton model for pedestrian dynamics. Physica A: Statistical Mechanics and its Applications 312(1--2) (2002), 260--276. 2
• 17: {LC03} Li T.-Y., Chou H.-C.: Motion planning for a crowd of robots. In ICRA '03: Proceedings of IEEE international conference on Robotics and Automation (2003), pp. 4215--4221. 2
• 18: Yu-Chi Lai , Stephen Chenney , ShaoHua Fan, Group motion graphs, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073409]
• 19: Kang Hoon Lee , Myung Geol Choi , Jehee Lee, Motion patches: building blocks for virtual environments annotated with motion data, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 20: {LD04} Lamarche F., Donikian S.: Crowd of virtual humans: A new approach for real time navigation in complex and structured environments. Computer Graphics Forum (Eurographics 2004) 23, 3 (2004), 509--518. 2
• 21: Jehee Lee , Sung Yong Shin, A hierarchical approach to interactive motion editing for human-like figures, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.39-48, July 1999 [doi>10.1145/311535.311539]
• 22: {MA06} Mount D., Arya S.: Ann: Library for approximate nearest neighbor searching, http://www.cs.sunysb.edu/algorith/implement/ann/distrib/index1.html, 2006. 5
• 23: {Mas06} Massive Software: http://www.massivesoftware.com/, 2006. 2
• 24: {MH04} Metoyer R. A., Hodgins J. K.: Reactive pedestrian path following from examples. The Visual Computer 20, 10 (2004), 635--649. 2
• 25: {MT97} Musse S. R., Thalmann D.: A model of human crowd behavior: Group inter-relationship and collision detection analysis. In Computer Animation and Simulation '97 (1997), pp. 39--51. 2
• 26: Julien Pettré , Pablo de Heras Ciechomski , Jonathan Maïm , Barbara Yersin , Jean-Paul Laumond , Daniel Thalmann, Real-time navigating crowds: scalable simulation and rendering: Research Articles, Computer Animation and Virtual Worlds, v.17 n.3-4, p.445-455, July 2006 [doi>10.1002/cav.v17:3/4]
• 27: {POSB05} Pelechano N., O'Brien K., Silverman B., Badler N.: Crowd simulation incorporating agent psychological models, roles and communication. In V-CROWDS '05: Proceedings of the First International Workshop on Crowd Simulation (2005), pp. 24--25. 2
• 28: Sang Il Park , Hyun Joon Shin , Tae Hoon Kim , Sung Yong Shin, On-line motion blending for real-time locomotion generation: Research Articles, Computer Animation and Virtual Worlds, v.15 n.3-4, p.125-138, July 2004 [doi>10.1002/cav.v15:3/4]
• 29: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.25-34, August 1987
• 30: {SGC04} Sung M., Gleicher M., Chenney S.: Scalable behaviors for crowd simulation. Computer Graphics Forum (Eurographics 2004) 23, 3 (2004), 519--528. 2
• 31: Mankyu Sung , Lucas Kovar , Michael Gleicher, Fast and accurate goal-directed motion synthesis for crowds, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073410]
• 32: Wei Shao , Demetri Terzopoulos, Autonomous pedestrians, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073371]
• 33: {Sti00} Still G. K.: Crowd Dynamics. PhD thesis, University of Warwik, 2000. 3
• 34: Adrien Treuille , Seth Cooper , Zoran Popović, Continuum crowds, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 35: {Tek02} Teknomo K.: Microscopic Pedestrian Flow Characteristics: Development of an Image Processing Data Collection and Simulation Model. PhD thesis, Tohoku University, 2002. 3
• 36: {ZN04} Zhao T., Nevatia R.: Tracking multiple humans in crowded environment. IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2 (2004), 406--413. 2

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism