CS-184: Computer GraphicsLecture #19: More Motion CaptureProf. James O’BrienUniversity of California, BerkeleyV2006-F-19-1.02TodayMore Motion Capture3Motion GraphsHand build motion graphs often used in gamesSignificant amount of work requiredLimited transitions by designMotion graphs can also be built automaticallyTransition GraphsFlipStandRunWalkSitTripDance4Motion GraphsSimilarity metricMeasurement of how similar two frames of motion areBased on joint angles or point positionsMust include some measure of velocityIdeally independent of capture setup and skeletonCapture a “large” database of motions5Motion GraphsCompute similarity metric between all pairs of framesMaybe expensivePreprocessing stepThere may be too many good edgesTo appear in the ACM SIGGRAPH conference proceedings2. The motion should not penetrate any objects in the environ-ment.3. The body should be at a particular position and orientation ata particular time.4. A particular joint should be at a particular position (andmaybe having a specific velocity) at a specific time.5. The motion should have a specified style (such as happy orenergetic) at a particular time.Finding paths in the motion graph that satisfy the hard con-straints and optimize soft constraints involves a graph search. Un-fortunately, for even a small collection of motions, the graph G hasa large number of edges and straightforward search of this graph iscomputationally prohibitive. The main reason is the need to enu-merate many paths. There are, in general, many perfectly satisfac-tory motions that satisfy the constraints equally well. For example,if we require only that the person be at one end of a room at frame 0and near the other end at frame 5000, unless the room is very large,there are many motions that satisfy these constraints.4 Randomized SearchThe motion graph is too hard to search with dynamic programmingas there are many valid paths that satisfy the constraints equallywell. There may be substantial differences between equally validpaths — in the example above, whether you dawdle at one side ofthe room or the other is of no significance. This suggests summa-rizing the graph to a higher level and coarser presentation that iseasier to search. Branch and bound algorithms are of no help here,because very little pruning is possible.In order to search the graph G in practical times, we need to dothe search at a variety of levels where we do the large scale mo-tion construction first and then “tweak” the details so that the mo-tion is continuous and satisfies the constraints as well as possible.Coarser levels should have less complexity while allowing us to ex-plore substantially different portions of the path space. In such arepresentation, every level is a summary of the one finer level. LetG!← G!!← G!!!← · · · ← Gn← G be such a hierarchical represen-tation where G!is the coarsest level and G is the finest. We will firstfind a path in G!and then push it down the hierarchy to a path in Gfor synthesis.4.1 Summarizing the GraphAll the edges between two nodes s and t can be represented in amatrix Pst. The (i, j)’th entry of Pstcontains the weight of theedge connecting sito tjand infinity if there is no such edge. Inthe appendix A, we give one natural cost function C(si, tj) for edgeweights. We now have:(Pst)i j=!C (si, tj) if there is an edge from sito tj∞ otherwise.The cost function explained in section A causes the P matrices tohave non-infinite entries to form nearly elliptical groups (figure 2).This is due to the fact that if two frames are similar, most probablytheir preceding and succeeding frames also look similar.In order to summarize the graph, we cluster the edges of G.We now have G!, whose nodes are the same as the nodes of G,and whose edges represent clusters of edges of G in terms of theirf romFrame and toFrame labels. We require that, if there is a cutbetween two sequences represented by an edge between two nodesin G, there be at least one edge between the corresponding nodes inClusteringWalking , frame iRunning, frame jWalking RunningFrameiFramejFigure 2: Every edge between two nodes representing different mo-tion clips can be represented as a matrix where the entries corre-spond to edges. Typically, if there is one edge between two nodesin our graph, there will be several, because if it is legal to cut fromone frame in the first sequence to another in the second, it will usu-ally also be legal to cut between neighbors of these frames. Thismeans that, for each pair of nodes in the graph, there is a matrixrepresenting the weights of edges between the nodes. The i, j’thentry in this matrix represents the weight for a cut from the i’thframe in the first sequence to the j’th frame in the second sequence.The weight matrix for the whole graph is composed as a collectionof blocks of this form. Summarizing the graph involves compress-ing these blocks using clustering.G!. If this were not the case, our summary would rule out potentialpaths. In order to insure that this condition holds and because thegraph is very large, we cluster edges connecting every pair of nodesin G separately. We cluster unconnected edge groups of G from theP matrices (defined between every pair of nodes) using k-means[Bishop 1995]. The number of clusters is chosen asma joraxislengthminoraxislengthfor each group where the axis lengths refer to the ellipse that fits tothe cluster (obtained through Principal Component Analysis).The nodes of G!are the same as the nodes of G. The edges con-necting nodes in G!are cluster centers for clusters of edges connect-ing corresponding nodes in G. The centers are computed by takingthe average of the edges in terms of f romFrame, toFrame and costvalues. At this point, every edge in G!represents many edges in G.We would like to have a tree of graph representations whose rootis G!, and whose leaves are G. We use k-means clustering to spliteach cluster of edges in half at each intermediate level and obtaina hierarchical representation G!← G!!← G!!!← · · · ← Gn← G forthe original graph G. This is an instance of Tree-Structured VectorQuantization [Gersho and Gray 1992].Thus, in our summarized graph G!, each edge is the root of abinary tree and represents all the edges in close neighborhood interms of the edge labels. Note that the leaf edges are the edges inthe original graph and intermediate edges are the averages of all theleaf edges beneath them. A path in G represents a sequence of
View Full Document
Unlocking...