Current MS Students/Ziba Rostamian/Prospectus Draft
From CSWiki
Anomaly Detection in Moving Objects
Contents |
[edit] What I am planning to accomplish
My plan is to study Learning Finite Automata and compare couple of algorithms that build probabilist automaton to learn or detect the patterns inside a given data set. My altimate goal is to detect anomaly of moving objects using CSSR(Causal State Splitting Reconstruction) algorithm. The CSSR(Causal State Splitting Reconstruction) algorithm will be used to detect normal/abnormal situations and uses the results for anomaly detection.
- What is anomalies?
The set of data points that are considerably different than remainder of the data.
One interesting problem related to the subject is to find a drunk drivers or whoever drives in a suspicious way.
[edit] Issues to be investigated
Based on the characteristics of the application that I am going to examine and also the detection methods that I will use the issues can be slightly different however there are some major difficulties in common no matter which method I use.
[edit] Multiple Object Traking
Finding real-time algorithm that solves the problem of Multiple-Target tarcking in which an unknown number of targets appears and disappears at random times, itself is not an easy task to do.
Under the most general setup, a varying number of distinguishable targets are moving continuously in a given region and the position of moving targets are sampled at random intervals. The measurements of the positions are noisy with detection probabilty less than one. Targets arise at random in space and time. Each targets persists independently for a random length of time and then ceasses to exit. A track is defined as a path in space-time traveled by a target.
Now the problem is to find a partition of observation such that each element of a partition is a collection of observation generated by a single target. However due to the noise in observation, we can not except to find the exact solution.
(a) An example of observation (each circle represents an observation and numbers represnt observation times) (b) An example of partitioning the observation.
[edit] Huge amout of complex data
Due to the sheer volume of data associated with moving objects, it is challenging to develop a method that can efficiently and effectively detect anomalies. A day of observation of a typical scene may contain tens of thousands of moving objects of various sizes (people, groups, bicycles, motorbikes, cars, trucks, etc.)There also exist substantial complexities of possible abnormal behaviour, which may accour at arbitrary level of abstraction and be associaated with different time and location granularities.
[edit] Why this is academically interesting
Doing this research requires a considerable amount of time to study and experiment the algorithm. Even finding a suitable application to study this algorithm has been an issue for me so far.
[edit] Intended audience
Anomaly detection in massive moving objects has many important applications, especially in surveillance, law enforcement, and homeland security. Therefore, different communities can be inteded audience of this work.
[edit] Why this is MS-level work
In order to accomplish what I am planning to do I need to have a good understanding of sensor networks, statistics and probabilistic theories and good program skills. To acquire this I need to read a lot of papers, only to get familiar with the notations that are required to continue the problem.
[edit] Previous work
At present, there are devices and systems that can detect and count human traffic, in shopping malls or terminal stations of various public transportation vehicles. These systems make use of overhead sensors across wide aisles of several meters or computer vision algorithms to interpret camera images. Systems utilizing camera systems also require sufficiently bright lighting.
- Most available techniques for detecting moving objects have been designed for scenes acquired by a stationary camera. These methods allow to segment each image into a set of regions representing the moving objects by using a background differencing algorithm. Background subtraction detects moving objects by subtracting estimated background models from images. This method is sensitive to illumination changes and small movement in the background, e.g. leaves of trees. There is a method to estimate illumination changes and small movement in the background However, a common problem of background subtraction is that it requires a long time for estimating the background models. It usually takes several seconds for background model estimation because the speed of illumination changes and small movement in the background are very slow.
- There is a short list of publication using CSSR algorithm. Here is the list.
There is a paper related to what I am going to do on the list, however I couldn’t get a copy of it.Here is the abstract of the paper.
Title: "Determination of vehicle behavior based on distributed sensor network data"
Authors: Friedlander, David; Phoha, Shashi; Brooks, Richard R.
Abstract
Vehicle tracking can be done automatically based on data from a distributed sensor network. The determination of vehicle behavior must currently be done by humans. Behaviors of interest include searching, attacking and retreating. The purpose of this paper is to show an approach for the automatic interpretation of vehicle behaviors based on data from distributed sensor networks. The continuous dynamics of the sensor network are converted into symbolic dynamics by dividing its phase space into hypercubes and associating a symbol with each region. When the phase-space trajectory enters a region, its corresponding symbol is emitted into a symbol stream. Substrings from the stream are interpreted as a formal language defining the behavior of the vehicle. The formal language from the sensor network is compared to the languages associated with known behaviors of interest. Techniques for performing quantitative comparisons between formal languages are presented. The abstraction process is shown to be powerful enough to distinguish two simple behaviors of a robot based on data from a pressure sensitive floor.
To make the problem clear I provided a summery of a paper for detecting abnormal moving objects.
Automatic Anomaly Detection in Massive Moving Objects
- Summery
In anomaly detection applications, the objective is to detect abnormal conditions occuring within the monitored system by analyzing observable process data. To this end, models are often constructed to charactrize normal and abnormal behaviors. A model may represent the possible and un acceptable operational dynamics of a monitored process. Finite state machine (FSM) representations of system components can be formulated and composed to describe relevant operations of integrated system.
to detect anomalies, it is needed not only a set of sensors to retrieve process data but also an observer to integrate and analyze the collected process information. Thus optimizing sensor configurations and rigorously synthesizing their corresponding observers are important design goals.
let's look at this example again:
There is a larg number of vessels sailing near american coats. Manually trace enormous numbers of moving object and identify suspicious ones is not realistic.Therefore it's highly desirable to develop automated tools that can evaluate the behavior of all maritime vessels and flag the suspicious ones.
In the paper, they study the problem and propose an effective and scalable classification methods for detecting anomalous behavior in moving object.
[edit] Movement Motifs
They assumed the input data consists of a set of labeled movments paths, P = {p_1, p_2, ...} while each path is a sequence of time-related opints of an object. For each object there is a set of none-spatiotemporal attributes that describe non-motion related properties, such as "size" and "type".
It is necessary to extract movements motifs at certain heigher abstraction (not in precision of seconds and inches) level in order to perform efficient and meaningful analysis.
Considering two ship movements showing above they share similar movements except an extra loop in the dashed path. the make semantically meaningful comparisons between moving objects, extract movements motifs at a proper level for further classification.
A movement motif is a prototypical movement pattern of an object, often pre-defined domain experts. For example straight line, right turn, U-turn, loop,etc. Let there be M defiend motifs {m_1, m_2,... m_M}. A movement path is then transformed to a sequence of motifs with other oiecess of information.
They also assumed that the motif extractor is able to extract some spatiotempral information. Using such information they can derive a set of attributes, duration, avg-speed, etc.
Three ships has been shown on above picture. They are moving in an area that contains an important landmark, The left and right ships have the same movement shapes except that the left one makes its circle around a landmark. This extra piece of information combined with the movement motif can be crucial in decision making. If they had the information that left ship made that extra move late an night with very low speed it's possible case of abnormal movement.
The vector of such information can be use to feed into some learinig machine. But since the number of distict values for each attribute is very larg they used different approach. They propose an extraction process which will smooth out the high granularity values and extract higher level features. For example, the excat distance from a ship to a landmark is unimportant and it is enough to consider "rather close-to it" in comparision with most other ships.
They then applied a clustering method to extract that high level features. Once we have clustered information getting a vector of high level features we can classify the movement of an object.
[edit] Brief literature review
Probabilistic Automaton: A probabilistic automaton is a finite automaton with transition probabilities which represents a distribution over the set of all strings defined over a finite alphabet.
Markov Process: Markov chain or Markov process in the stochastic process with Markov property. having the Markov property means that, given the present state, future states are independent of the past states.
Hidden Markove Model: A hidden Markov model (HMM) is a statistical model in which the system being modeled is assumed to be a Markov process with unknown parameters, and the challenge is to determine the hidden parameters from the observable parameters.
The definition of CSSR algorithm.
[edit] Anticipated challenge(s)
There are two mechanisms for anomaly detection. Classification and clustering. Unsing classification requires us to have a tarining set and finding a good training set can also be challenging. Clustering performs automated grouping without using training set. My plan is to build a classifier that separate the data to normal/abnormal groups.
[edit] Challenges
- Finding a good training set
- Distance measure
During the training part of the process, the algorithm will build a machine to be used for estimating similar situations in future. The output of the algorithm is probabilistic automaton. Then when a new data comes, in order to estimate its distribution I have to build a machine for it and compare it with what I got from training process. Therefore I need to study computation of standard distance between probablistic automata.
- Decoding the observation
Although the observation could be in the precison of seconds and inches but in order to perform effient and semantically meaninful analysis it's necessary to extract infromation at certain higher abstraction level from the sequence of observation. For example a path has been traveled by an object can be a set of straight line, U-turn, left turn and right turn combination.
[edit] Anticipated approach to each challenge
My plane is to use CSSR algorithm to learn a model. CSSR algorithm seems to be capable of using a very large dataset for learning a model of object motion through the scene. This is necessary in order to effectively model active, complex scenes where the number of observed objects per hour reaches several hundred or more.
Before studying the problem more in details I can’t talk about the anticipated approach for each challenges.
[edit] What I bring to this work
[edit] My relevant background and experience ( CS590)
- I have been studing a lot of papers related to the area of learing or perdicting a phenomenon using automatons such as HMMs even before taking the 590 class.
- I have also passed some related courses such as Machine Learning, Data Mining in CSULA during last couple of quarters. Currently I have Artificial Intelligence course. I am also taking 594 which I believe some Learning Probabilistic Automaton concepts is going to be covered in this course.
- During thoses courses I have studied a different learning methods. I also done some learning project such as using genetic programing to find out the location of an object by a tank, building decision tree to predict a type of forest given some attributes, implementing k-mean algorithm to cluster the different type of forests and currently I am working on detecting a face pose using different methods such as ANN and PCA.
[edit] What I find interesting about this work
After studying the concept of HMM, even for a short period of time I found the subject interesting and I wanted to investigate sufficient amount of time to study the learning automaton more deeply.
