Harvard Computer Science Technical Reports for 2013
- TR-01-13 [tr-01-13.pdf (219K)]
Ruonan Li, Parker Porfilio, Todd Zickler. 2013. ``Finding Group Interactions in Social Clutter''
We consider the problem of finding distinctive social interactions involving groups of agents embed-
ded in larger social gatherings. Given a pre-defined gallery of short exemplar interaction videos, and a
long input video of a large gathering (with approximately-tracked agents), we identify within the gather-
ing small sub-groups of agents exhibiting social interactions that resemble those in the exemplars. The
participants of each detected group interaction are localized in space; the extent of their interaction is
localized in time; and when the gallery of exemplars is annotated with group-interaction categories, each
detected interaction is classified into one of the pre-defined categories. Our approach represents group
behaviors by dichotomous collections of descriptors for (a) individual actions, and (b) pair-wise inter-
actions; and it includes efficient algorithms for optimally distinguishing participants from by-standers in
every temporal unit and for temporally localizing the extent of the group interaction. Most importantly,
the method is generic and can be applied whenever numerous interacting agents can be approximately
tracked over time. We evaluate the approach using three different video collections, two that involve
humans and one that involves mice.
- TR-02-13 [tr-02-13.pdf (644K)]
Nicolas Bonneel, Hanspeter Pfister. 2013. ``Sliced Wasserstein Barycenter of Multiple Densities''
The optimal mass transportation problem provides a framework for interpolating between
different probability density functions (pdfs), warping one function toward another. Interpolating between
two arbitrary pdfs can be challenging, but interpolating between more than two pdfs just remains untractable.
We propose an approximation of such interpolations based on 1D projections, that is efficiently
solved via Radon transforms. We observe the expected translational behavior of this interpolation on smooth
2D functions, and prove that it corresponds to the exact interpolant in a few particular cases.
- TR-03-13 [tr-03-13.pdf (644K)]
Peter Macko, Daniel Margo, Margo Seltzer. 2013. "Local Clustering in Provenance Graphs (Extended Version)"
Systems that capture and store data provenance, the record of how an object has arrived at its
current state, accumulate historical metadata over time, forming a large graph. Local clustering in these
graphs, in which we start with a seed vertex and grow a cluster around it, is of paramount
importance because it supports critical provenance applications such as identifying semantically meaningful
tasks in an object's history and selecting appropriate truncation points for returning an object's ancestry
or lineage. Generic graph clustering algorithms are not effective at producing semantically meaningful
clusters in provenance graphs. We identify three key properties of provenance graphs and exploit them
to justify two new centrality metrics we developed, specifically for use in performing local clustering on