Reconstructing Storyline Graphs from Web Community Photos

new Paper is available now.



  • Gunhee Kim and Eric P. Xing
    Reconstructing Storyline Graphs for Image Recommendation from Web Community Photos
    27th IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2014), Columbus, Ohio, USA, Jun 23-28, 2014. (Oral) (Acceptance = 104 / 1807 ~ 5.75 %)
    [Paper (PDF)] [Presentation (PPTX)] [Poster (PDF)] [1min Video (MOV)]

Matlab example code

  • We are working on a journal version. We will post the code after the Journal submission.


Motivation of Research

These days, online sharing of pictures is so easy and popular over a multitude of web platforms. Consequently, large-scale and ever-growing online visual data have led to an information overload problem. Users are often overwhelmed by the flood of unstructured pictures and videos, and struggling to grasp any meaningful information out of them.

The objective of this research is to create storyline graphs from large-scale collections of Internet images, and optionally other side information such as friendship graphs. The storyline graphs can be an effective summary that visualizes various branching narrative structure of events or activities recurring across the input photo sets of a topic class. Conceptually, the vertices in the graph correspond to dominant image clusters across the dataset, and the edges connect the vertices that sequentially recur in many photo streams.

For example, in Independence Day, various events are captured by millions of people across the U.S. and the common storylines would be parades in the morning, barbeque parties in the afternoon, and fireworks at night. If one queries the images by the term Independence Day from Google image search, they are high-quality and clearly related to the keyword, but just a set of separately retrieved images without any informative structure between them. However, the storyline graph can visualize the structure of various branching narratives of the topic.


Figure 1. Motivation for creating storyline graphs from large sets of Web photo streams with an independence+day example. The input is two-fold: (a) A set of photo streams that are independently taken by multiple users at different time and places, and (b) optionallya friendship graph. (c) The output is the storyline graph as a structural summary. The vertices are the exemplars of image clusters, and theedges connect sequentially recurring nodes across photo streams. We show the average images of nine selected node clusters in the bottom.

Method and Experiments

We formulate the storyline reconstruction problem as an inference of sparse time-varying directed graphs, and develop an optimization algorithm that successfully addresses a number of key challenges of Web-scale problems, including global optimality, linear complexity, and easy parallelization.

For evaluation, we collect about 3.3 millions of Flickr images of 24 classes, and perform quantitative experiments and user studies via Amazon Mechanical Turk, in order to show that the proposed algorithm improves other candidate methods for both storyline reconstruction and image prediction tasks.


  • This research is supported by NSF IIS-1115313, AFOSR FA9550010247, Google, and Alfred P. Sloan Foundation.