current page

history

user

Group Members

Vadim Ogievetsky

Project Proposal

The project would attempt to automate the generation of the http://xkcd.com/657/ visualization:

movie_narrative_charts

In particular I will try to implement an automated way to parse character interaction instructions (or, perhaps, a raw movie script) and generate an ‘action line’ for each character in a way that codes interaction with spatial proximity.

Main Goal

My main goal is to implement an efficient and effective layout algorithm that, with the users help, would generate results similar to the hand crafted images shown above. The layout algorithm will use combinations of genetic algorithms and simulated annealing to achieve the goal.

Above and Beyond

Depending on the ease of implementing the layout algorithm I would also like to consider these extensions:

  • Effective label placement – how do we label the lines in an aesthetic and uncluttered way?
  • Movie script parsing – can we automatically parse a movie script and, perhaps with some minimal help form the user, determine how to visualize it?
  • Temporal manipulation – can we automatically determine how to stretch and compress the x-axis to achieve the most clarity by giving lots of space to complicated time periods and little space to simpler time periods?
  • Important character encoding – can we have the layout ‘flow’ around some pivotal character? (e.g. how do all the characters in Star Wars interact with Luke?)

Related work

  • MatrimonialPathFinder* (still unpublished work within the Stanford Visualization department)

  • http://xkcd.com/657/ (show above)

  • Edge crossing minimization algorithm for hierarchical graphs based on Genetic Algorithms (Shen Wei-xiang, Huang Jing-wei): link

  • Differential evolution for small TSPs with constraints (Štefan Peško): [link: http://frcatel.fri.uniza.sk/users/pesko/publ/DeTSP.pdf]

  • Differential evolution - A Simple and Efficient Heuristic Strategy for Global Optimisation over Continuous Spaces (Rainer Storn, Kenneth Price): link

Initial Presentation

Initial Presentation page (+comments)

Deliverables

PlotWeaver (Demo for grading)

Paper (PDF)

Source Code (ZIP for grading)

Poster (PDF)

Additional

Tutorial page

Example plots

PlotWeaver (Latest demo)**

Source Code (ZIP latest)**


*Not the actual project name

**Not for grading – updated after submission deadline