Coherent Filtering: Detecting Coherent Motions from Crowd Clutter

October 2, 2012 Leave a comment

Coherent motion is a universal phenomenon in nature and widely exists in many physical and biological systems. For example, the tornadoes, storms and atmospheric circulation are all caused by the coherent movements of physical particles in the atmosphere. Meanwhile, the collective behaviors of organisms such as schooling fishes and pedestrian crowd have long captured the interests of social and natural scientists. Here are examples of coherent motions in videos.

Figure 1: Coherent motions in nature.

Detecting these coherent motion patterns in crowd is the first step to organize the low-level features into semantic clusters. It will benefit high-level tasks such as scene understanding and activity analysis.

Recently I proposed a simple coherent motion detection technique called Coherent Filtering. It is published in Proceedings of 12th European Conference on Computer Vision (ECCV 2012). It is a generic clustering algorithm for analyzing time-series signals.

In our formulation, the low-level features are the keypoint trajectories (short time-series) automatically extracted from crowd video. Here are examples of the keypoint trajectories extracted from the crowd videos.

Figure 2. A) One frame of the crowd videos. B) The trajectories extracted from the videos. Colors of trajectories are randomly assigned.

Since the scenes in video are very crowded, there will be lots of dynamic noises and cluttered trajectories. Thus the purpose of the technique is to remove these noises and cluster keypoint trajectories into different coherent motion patterns. Here are some clustering results:

Figure 3. The coherent motion detection results by Coherent Filtering. Keypoints with the same color belong to the same coherent motion pattern.

The mechanism behind our technique is that it is based on a prior discovered in the particle dynamics called Coherent Neighbor Invariance. The details can be found at the project page and technical paper.

Categories: Uncategorized

Understanding Collective Crowd Behavior: A Computer Vision Approach

July 6, 2012 4 comments

Recently I publish a research paper  at IEEE Conference on Computer Vision and Pattern Recognition (CVPR) 2012, to analyze the collective crowd behavior in New York Grand Central Station. Here is the paper and project page.

Grand Central Station

Generally speaking, the objective of this project is to learn the collective crowd behavior patterns from the real video of New York Grand Central Station. And the learned collective behavior patterns are used in a lot of important applications, such as crowd simulation, collective behavior classification, and abnormality detection.

Applications

Though there are quite a lot of pedestrian walking in the station at one time(~400 population) which form a variety of collective crowd behaviors, one key fact is that instead of randomly moving, majority of these pedestrian have clear belief of the destination to reach in mind, i.e., entering from one entry and walking to one exit in other side of the station. Thus, the overall behavior of one pedestrian in the station will be largely influenced by his belief of starting point and destination, along with two other properties: his preference of movement dynamics and timing of emerging (the frequency of entering the scene from the starting point).

Three typical pedestrian-agents and their three properties.

Following this intuitive analysis, from agent-based modeling of the crowd in station, every pedestrian is driven by one type of agents with three properties: the belief of starting point and destination, movement dynamics, and the timing of emerging. And the whole crowd is modeled as a mixture of pedestrian-agents with different three properties.

For the computational modeling of the pedestrian-agents, please refer to project page and paper for detailed information. Welcome to contact me if you have any questions or suggestions. The original video of the train station and the trajectories used in my paper could be downloaded at here.

Categories: Uncategorized

Brief Introduction on Computational Modeling of Crowd Behavior

April 5, 2012 3 comments

Generally speaking, based to the subjectiveness and objectiveness of methodology, there are two major approaches for computational modeling of crowd behavior. From the objective perspective, there are physics-based approach, which regard individuals in the crowd as physical particles corresponding to some physics laws; and from the subjective perspective, there are agent-based approach, which model the individuals in the crowd as autonomous agents who would do decision making and interaction according to some rules.

I, Physics-based approach

The crowd is treated as physical fluid and particles, thus a lot of analytical methods from statistical mechanics and thermodynamics are introduced. Here are some typical research works from this kind of approach.

  • S. Ali and M. Shah. Floor fields for tracking in high density crowd scenes. In Proc. ECCV, 2008.
  • R. Hughes. The flow of human crowds. Annual Review of Fluid Mechanics, 2003.
  • A. Treuille, S. Cooper, and Z. Popovi´c. Continuum crowds. In ACM SIGGRAPH, 2006.

II, Agent-based modeling approach

Different from the physics-based approach which assumes individuals in the crowd as non-thinking physical particles, the agent_based modeling considers the individuals in the crowd as autonomous agents which actively sense the environment and make decision according to some predefined rules. This kind of approach is also close related to game theory, complex systems, emergence, and Monte Carlo simulations. Here is a nice survey on agent_based modeling,

  • E. Bonabeau. Agent_based modeling: Methods and techniques for simulating human systems. Proc. National Academy of Sciences of the United States of America, 2002.

Recently there is an online free course Model Thinking which lectured by Prof. Scott Pages from University of Michigan. I have introduced Prof. Scott’s research works on complex systems and the nice books Complexity and Diversity, the Dfference and Complex Adaptive Systems written by him in this weblog (I finish reading  these three books with great inspiration). Personally I enjoy this course quite a lot, since it not only specifically introduces the classical agent_based models used in economics, social sciences, but also generally highlight how to formulate some real-life problems from scratches using the framework of model thinking. And each lectures in the course are shorted into video clips with 15 min length (I know you would easily distract your attentions when the lecture last too long) and the contents are easy to follow and not technically intense. I sincerely recommend it to you all! Besides, this course discusses the meaning of model in real life and theoretic scientific research, on which I am meditating a lot during these time, later on I would write a article on this.

In recent years there are gradually a lot of agent_based models proposed for modeling the crowd. Here I outline two famous agent-based models in crowd behavior analysis: the social-force model proposed by Dirk Helbing and the Self-propelled particles (SPP) model proposed by Tamas Vicsek.

Social-force model 

Social-force model is proposed to formulate the behavioral process of autonomous agents, from perceiving the environments and making decision. The general framework of this process is shown in Figure 1. Furthermore, social-force model can be used to simulate the crowd panic as shown in Figure 2.

Figure 1:The framework of the behavioral process in social-force model.

Figure 2: The simulation of crowd evacuation based on social-force model.

Here are the two seminal papers on social-force model:

  • Helbing, Dirk; Molnár Péter . Social force model for pedestrian dynamics.Physical Review E 51, 1995
  • D. Helbing, I. Farkas, and T. Vicsek. Simulating dynamical features of escape panic. Nature, 2000

And you could find a lot of resource on social-force model in the following two pages maintained by Prof. Dirk Helbing and his research teams on crowd behavior analysis:

http://angel.elte.hu/panic/

http://www.trafficforum.ethz.ch/crowdturbulence/

In computer vision community, the social force model is introduced for multi-target tracking [1], abnormality detection [2], and analysis of pedestrian action and mutual interaction [3]

  • [1] R. Mehran, A. Oyama, and M. Shah. Abnormal crowd behavior detection using social force model. In Proc.CVPR, 2009.
  • [2] S. Pellegrini, A. Ess, K. Schindler, and L. Van Gool. You’ll never walk alone: Modeling social behavior for multi-target tracking. In Proc. ICCV, 2010.
  • [3] P. Scovanner and M. Tappen. Learning pedestrian dynamics from the real world. In Proc. ICCV, 2009.

Self-propelled particles (SPP) model

SPP model is proposed to model the interaction of individual in the crowd the and the formation of collective motion.

The model itself is very simple, at each time step, the individuals would coordinate its velocity directions with its neighbor individuals. When the coordination level is high, there is collective motion of the crowd emerging. as shown in Figure 3.

Figure 3: SPP model and the formation of collective motion in the crowd.

Here is the seminal paper on SPP.

Vicsek, T.; Czirok, A.; Ben-Jacob, E.; Cohen, I. & Shochet, O. Novel type of phase transition in a system of self-driven particles. Physical review letters, 1995.

In this paper, Vicsek further discussed the influence of noise on the coordination level and the phenomena of phase transition, that is, how the phase of random movements of individuals is transformed into the phase of collective motion of individuals. It is related some important topics, such as self-organization and emergence.

Materials on Agent-Based Model

February 25, 2012 1 comment

Here is a new book on Agent-Based Models of Geographical Systems published by Springer 2012.

Agent-based model is a very powerful research tools for crowd behavior analysis. I went through this book, there are two chapters directly related to crowd behavior analysis:

  1. Chapter 18:  Agent tools, techniques and methods for macro and microscopic simulation.
  2. Chapter 21: Applied Pedestrian Modeling.

 

Besides, in Chapter 12: The Integration of Agent-based Modeling and Geographical Information for Geospatial Simulation, it introduces and compares several kinds of Agent-based simulation open source toolkits.

Here I list :

  • Swarm:  developed by Center for the Study of Complex Systems at the University of Michigan.
  • MASON (Multi Agent Simulation Of Neighbourhood): developed by the Evolutionary Computational Laboratory and the Centre for Social Complexity at George Mason University
  • StarLogo: developed by Media Lab at MIT.

 

Categories: Uncategorized

Swarmanoid: Inspiring video from AAAI2011

February 24, 2012 Leave a comment

A video on heterogeneous robotic swarm system.

This swarm system is composed of three different functional robots: the Foot-bots, the Hand-bots and the Eye-bot. They have different functionality: the foot-bots have motor system and are in charge of carrying the foot-bots. The hand-bots have flexible hands and can climb and carry objects. As for the Eye-bot, it can fly and navigate, and has visual sensor that can observe and recognize object in the outside environment. This video illustrate how this distributed systems collaborate with each other and finish a complex task.

This involves a very important concept for crowd system, the diversity and complexity of the system. The individuals in the crowd should be heterogeneous, which mean each individuals have unique or outstanding ability that other individuals do not have. So there would be collaboration and collective actions emerging. The overall robustness and evolution ability of a complex system are also determined by the diversity of its individuals. In economy, this idea is supported by the the division of labor in Capitalism boost the productivity of nations.

Recently I read a book Diversity and Complexity written by Scott Page. It is a very nice introductory book on how the diversity and complexity influence the overall complex systems. When I read the book, I always think about the extreme genocides happening all over the world, such as the Khmer Rouge in Cambodia 1975-1979, the Cultural Revolution in China 1968-1978. Diversity and complexity boost the development of human society, but governments may just like a homogenous crowd, since controlling morons is much much easier than controlling the intellectuals.

 

At last, I found a website Jasmine, which is devoted to the development of the open-source hardware and software for the swarm micro-robotic platform. Each robot costs around 100 euro. It is managed by Professor Serge in University of Stuttgart, Germany, who is an export on Collective Robotics.

Categories: Uncategorized

Two recent media reports on crowd behavior analysis

December 30, 2011 Leave a comment

The media is very interested in the topic of crowd behavior analysis. Here are recent two articles published in Financial Times and the Economist respectively.

Financial Times, Dec 27, 2011

Crowd behaviour: United they stand

This articile discusses the behavior similarity and difference between the crowd of civilians in Cairo for Arab Spring and the crowd of bond traders in Chicago. Keywords: the shared social identity, informational cascade, consensus and competition of individuals in group.

The Economist, Dec 17 2011

The wisdom of the crowd

This article mainly introduces the work done by Mehdi Moussaid and Dirk Helbing, which is published recently in PNAS. In the PNAS paper, the authors proposed two simple cognitive heuristics to explain the pedestrian behavior in public place. Two crucial problems are formulated and analyzed in the paper:

  • What kind of information is used by the pedestrian?
  • How is this information processed to adapt the walking behavior?

I think this research work is well done. Two take-home ideas: 1) Pedestrian more possibly rely on simple heuristics to do decision making when receiving visual information of environment. 2) Moussaid is really good at marketing his research works, since the Economist is an influential magazine all over the world. This would draw a wide range of audiences to what his research make sense.

Categories: Uncategorized Tags: ,

Two interesting projects in SIGGRAPH Asia 2011

December 15, 2011 1 comment

Today I visited the computer graphics conference SIGGRAPH Asia 2011. With going through a lot of amazing state-of-art

graphics technologies, I spot two interesting projects which I would like to share with you.

The first  is a human-machine interaction project Influencia done by the British artist David McLellan In this project, a dozen small autonomous robots coexist and communicate with participants. Each robot has sonar and heat sensors, and movement wheel, so that it can sense the existence and movements of participants, make decision to interact with participants. Though the structure of each robot is very simple, participants can actually have generative dialogue with the robots through physical interaction. This feeling is really cool. Maybe in future we can increase the number of robots and to see how these robots can interact with each other and to see whether they could form some collective motion and intelligence.

The second is a french start-up company Galaem specficied on crowd simulation of computer graphics. Its software products include the plug-in for MAYA and C++ SDK.  Here is some demo video. These products can not only be used in movie making, but also for scientific researches and visualization. By leveraging these plug-in developed by Galaem, We can implement the research results(like the algorithm for collective motion) in 3D real model, it would be very impressive.