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 simple graph structure, ability to generate long motions, and fully automatic synthesis of motions. The performance of a motion graph relies heavily on selecting a good set of motions 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 sub-graph 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 benefits novice users who desire simple and fully automatic motion synthesis tools, such as motion graph-based techniques.