| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | May 6, 2015 |
| Latest Amendment Date: | May 30, 2017 |
| Award Number: | 1513816 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
A. Funda Ergun
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | June 1, 2015 |
| End Date: | May 31, 2020 (Estimated) |
| Total Intended Award Amount: | $539,106.00 |
| Total Awarded Amount to Date: | $807,999.00 |
| Funds Obligated to Date: |
FY 2017 = $276,345.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
2200 W MAIN ST DURHAM NC US 27705-4640 (919)684-3030 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
NC US 27708-0129 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01001718DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
This project engages experts in computational geometry, optimization, and computer vision from Duke and Stanford to develop a theoretical and algorithmic framework for analyzing large collections of trajectory data from sensors or simulations. Trajectories are functions from a time interval to a multi-dimensional space that arise in the description of any system that evolves over time.
Trajectory data is being recorded or inferred from hundreds of millions of sensors nowadays, from traffic monitoring systems and GPS sensors on cell phones to cameras in surveillance systems or those embedded in smart phones, in helmets of soldiers in the field, or in medical devices, as well as from scientific experiments and simulations, such as molecular dynamics computations in biology. Algorithms for trajectory-data analysis can lead to video retrieval systems, activity recognition, facility monitoring and surveillance, medical investigation, traffic navigation aids, military analysis and deployment tools, entertainment, and much more. Many of these application fields intersect areas of national security, as well as domains of broader societal benefit.
This project pursues a transformational approach that combines the geometry of individual trajectories with the information that an entire collection of trajectories provides about its members. Emphasis is on simple and fast algorithms that scale well with size and dimension, can handle uncertainty in the data, and accommodate streams of noisy and non-uniformly sampled measurements.
The investigators have a long track record of collaboration with applied scientists in many disciplines, and will continue to transfer their new research to these scientific fields through joint publications and research seminars, also in collaboration with several industrial partners. This project will heavily rely on the participation of graduate and undergraduate students. Participating undergraduates will supplement their education with directed projects, software development, and field studies. Data sets used and acquired for this project will be made available to the community through online repositories. Software developed will also be made publicly available.
Understanding trajectory data sets, and extracting meaningful information from them, entails many computational challenges. Part of the problem has to do with the huge scale of the available data, which is constantly growing, but there are several others as well. Trajectory data sets are marred by sensing uncertainty and heterogeneity in their quality, format, and temporal support. At the same time, individual trajectories can have complex shapes, and even small nuances can make big differences in their semantics.
A major tension in understanding trajectory data is thus between the need to capture the fine details of individual trajectories and the ability to exploit the wisdom of the collection, i.e., to take advantage of the information embedded in a large collection of trajectories but missing in any individual trajectory. This emphasis on the wisdom of the collection is one of the main themes of the project, and leads to a multitude of important problems in computational geometry, combinatorial and numerical optimization, and computer vision. Another theme of the project is to learn and exploit both continuous and discrete modes of variability in trajectory data.
Deterministic and probabilistic representations will be developed to summarize collections of trajectories that capture commonalities and differences between them, and efficient algorithms will be designed to compute these representations. Based on these summaries, methods will be developed to estimate a trajectory from a given collection, compare trajectories to each other in the context of a collection, and retrieve trajectories from a collection in response to a query. Trajectory collections will also be used to infer information about the environment and the mobile entities involved in these motions.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
This collaborative project (with Leo Guibas at Stanford University) developed a theoretical and algorithmic framework for analyzing large collections of trajectory data from sensors in physical or virtual settings, using a transformational approach that combines the geometry of individual trajectories with a joint analysis of a collection of trajectories.
Models and fast, scalable algorithms were developed for a variety of tasks described below. Some of these algorithms were used in applications to biology and computational journalism.
Many graduate and undergraduate students and three postdoctoral fellows were partially supported by this project. The PIs organized a workshop Algebraic Methods in Discrete and Computational Geometry, taught a summer course Machine Learning and Video Analysis, and wrote multiple survey papers. Results from this project were disseminated through journal and conference publications, talks, and classroom materials for advanced courses.
Technical contributions include the following:
Trajectory similarity. Computing the similarity between two trajectories is fundamental to several trajectory analysis problems, and quadratic-time algorithms are known for many classical similarity measures such as Dynamic Time Warping (DTW) and Edit Distance (ED). Recent theoretical results suggest that there is little hope to do better in general. Fast algorithms were developed to approximate DTW and ED and run in near-linear-time for well-behaved trajectories. Experiments show that these algorithms are at least an order of magnitude faster than the standard methods for long trajectories.
Subtrajectory clustering. Many types of trajectory collections exhibit patterns of shared structure. For instance, a road network in a city generates shared subtrajectories for vehicles. These subtrajectories are called pathlets. Given a collection of trajectories, an optimization method was developed to identify a small dictionary of pathlets, such that each trajectory can be well represented as a short sequence of pathlets in the presence of noise and other data artifacts. This problem was shown to be NP-Hard, and fast approximation algorithms were developed for it. Experiments show that the algorithm is robust to variations, efficient, and accurate.
Tracking cells. Several biological applications require tracking cells that are connected through a visible network of membrane junctions as they deform over time. An example is the study of dorsal closure in Drosophila melanogaster through confocal microscopy. Tracking methods were developed to describe the entire cell network as a collection of trajectories, for more robust tracking. These method consistently outperform previous cell-tracking algorithms.
Tracking hands. A new method was developed for tracking the individual fingers of a human hand from images taken with a standard camera, useful in applications ranging from gestural interfaces to scene understanding. The method compares each frame from the sensor with a database of precomputed hand poses and corresponding images, recorded with a hand-glove and cameras. Experiments show state-of-the-art accuracy and speed for both gesture classification and joint-pose regression.
Tracking multi-person trajectories in multiple videos. Joint methods were developed for two different but related video analysis scenarios: Multi-Target Multi-Camera Tracking aims to determine the position of every person at all times from video streams taken by multiple cameras. In Person Re-Identification, given a snapshot of a query person, the system retrieves from a database a list of other snapshots of people, and ranks them by decreasing similarity to the query. Experiments show that these methods outperform the state of the art.
Detecting motion boundaries. The trajectories of points that move in a video sequence are spatially piecewise continuous, and the pieces are separated by so-called motion boundaries that arise along the contours of objects that move by different motions in the scene. Methods were studied for the detection of motion boundaries and developed a system for the detection of motion boundaries, and experimental results consistently improved on the state of the art.
Analyzing insect herbivory. When developing methods for motion boundary detection, it was found that reversing the information flow in a key part of a neural network yields more accurate results. Surprisingly this reversal turned out to be beneficial in a wide variety of image-to-image classification tasks. In a collaboration with biologists, this method was used to analyze insect damage on plant specimens stored in herbaria around the world and for detecting and classifying insect herbivory into different types of leaf damage.
Querying trajectory data. Decisions based on temporal data must often also consider the history of the data. Data structures and algorithms were developed to retrieve data that satisfy a query condition with some consistency over a period of time. A stochastic model was also developed to predict, based on historical data, which properties of an object will remain durable for a long period of time (e.g., In the next five years, what is the probability that Google will remain among the top 3 most valuable tech companies). A new stochastic sampler was proposed to answer such queries efficiently.
Last Modified: 06/18/2020
Modified by: Pankaj K Agarwal
Please report errors in award information by writing to: awardsearch@nsf.gov.
