Automatic construction of a minimum size motion graph

Motion capture data have been used effectively in many areas of human motion synthesis. Among those, motion graph-based approaches have shown great promise for novice users due to their ability to generate long motions and the fully automatic process of motion synthesis. The performance of motion graph based approaches, however, relies heavily on selecting a good set of motions used to build the graph. This motion set needs to contain enough motions to achieve good connectivity and smooth transitions. At the same time, the motion set needs to be small for fast motion synthesis. Manually selecting a good motion set that achieves these requirements is difficult, especially given that motion capture databases are growing larger to provide a richer variety of human motions. Therefore we propose an automatic approach to select a good motion set. We cast the motion selection problem as a search for a minimum size subgraph from a large motion graph representing the motion capture database and propose an efficient algorithm, called the Iterative Sub-graph Algorithm, to find a good approximation to the optimal solution. Our approach especially benefits novice users who desire simple and fully automatic motion synthesis tools, such as motion graph-based techniques.