Cloth Parameters and Motion Capture by David Pritchard B . A . S c , University of Waterloo, 2001 A THESIS S U B M I T T E D IN P A R T I A L F U L F I L L M E N T O F THE REQUIREMENTS FOR THE DEGREE OF M a s t e r o f Science in T H E F A C U L T Y O F G R A D U A T E STUDIES (Department of Computer Science) We accept this thesis as conforming ^t^ the required/^ndard The University of British Columbia October 2003 Â© David Pritchard, 2003 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of The University of British Columbia Vancouver, Canada DE-6 (2/88) Abstract Recent years have seen an increased interest in cloth simulation. There has been little analysis, however, of the parameters controlling simulation behaviour. In this thesis, we present two primary contributions. First, we discuss a series of experiments investigating the influence of the parameters of a popular cloth simulation algorithm. Second, we present a system for motion capture of deformable surfaces, most notably moving cloth, including both geometry and parameterisation. This data could subsequently be used for the recovery of cloth simulator parameters. In our motion capture system, we recover geometry using stereo correspondence, and use the Scale Invariant Feature Transform (SIFT) to identify an arbitrary pattern printed on the cloth, even in the presence of fast motion. We describe a novel seedand-grow approach to adapt the SIFT algorithm to deformable geometry. Finally, we interpolate feature points to parameterise the complete geometry. ii Contents Abstract ii Contents iii List of Tables v List of Figures vi Acknowledgements viii 1 Introduction 1 2 Previous Work 3 3 2.1 Cloth Simulation 3 2.2 Simulation Parameter Recovery 8 2.3 Cloth Capture 10 Cloth Simulation Experiments 12 3.1 Cloth Simulator 12 3.2 Influence of Parameters 14 3.2.1 Number of patches 15 3.2.2 Timestep 16 3.2.3 Stretch, shear and bend resistance 19 3.2.4 Damping constants 19 iii 4 5 The Disparity Map 2 7 4.1 The P D E Approach 3 0 4.2 The Optimisation Approach 3 3 Parameterisation 5.1 Feature Detection 37 5.2 Matching 4 0 5.2.1 Seeding 4 3 5.2.2 Growing 4 4 5.3 Verification 4 ^ 5.4 Geometry Parameterisation 4 6 0 6 Results 5 7 Conclusions 56 Bibliography 5 iv ^ List of Tables 3.1 Parameter values for the modified scale invariant version of Baraff and Witkin's simulator 15 6.1 Number of features found, matched, and verified for selected frames. 52 6.2 Performance of our system in selected frames, measured in seconds on a Pentium IV 1.8GHz system v 53 List of Figures 1.1 Overview of cloth motion capture system 1 3.1 Explanation of colour codes in energy visualisation 15 3.2 Impact of discretisation on tablecloth drape and energy distribution. 17 3.3 Impact of timestep on drape and energy distribution 18 3.4 Impact of stretch resistance on energy distribution 20 3.5 Impact of shear resistance on drape and energy distribution 21 3.6 Impact of bend resistance on drape and energy distribution 22 3.7 Impact of stretch damping constant on energy distribution 23 3.8 Impact of shear damping constant on energy distribution. . . . . . . 24 3.9 Impact of bend damping constant on energy distribution 25 4.1 Illustration of stereo correspondence algorithms 28 4.2 Comparison of disparity map with holes, after hole-filling and after sub-pixel estimation 29 4.3 Demonstration of the foreground fattening effect 30 4.4 Illustration of Caselles' PDE-based approach for sub-pixel estimation. 32 4.5 General structure of A matrix used by optimisation approach for sub-pixel estimation 5.1 35 Illustration of capture space, world space and reference space used by feature matching algorithm 38 vi 5.2 Reference and captured feature sets 39 5.3 Oblique views used for reference image 40 5.4 Illustration of the stretch and compression constraints 42 5.5 Interpolation of (u,v) data onto a regular grid 46 5.6 Example where linear interpolation of parameter values in C results in distortion of parameters when projected into W 47 5.7 Comparison of capture space interpolation and our method 48 6.1 The Digiclops camera used for triocular video acquisition 50 6.2 Input images, parameterised geometry with checkered texture, and feature densities 6.3 54 Captured image of fast moving cloth, and resulting parameterised geometry 55 vii Acknowledgements I would like to acknowledge my supervisor, Wolfgang Heidrich, for his ideas and discussions related to this thesis. I am grateful for the assistance of several members of my department, including Eddy Boxerman, David Lowe, Robert Bridson and Michiel van de Panne. For their support, I would like to thank my parents, my brothers, and Kathryn. Finally, I would like to thank the friends who kept me sane during my research, including Dave Burke, Hendrik Kiick, Eric Brochu, Lisa Streit, Roger Tarn, Ben Forsyth, Ritchie Argue, Matthew Brown, Derek Olive, Kristin Kopra, Alex Aylett, Shuzhen Wang, Matthew Thorne and Dan Archambault. DAVID PRITCHARD The University October of British Columbia 2003 viii Chapter 1 Introduction Over the past several years, interest in computer simulated cloth algorithms has grown steadily. Recent advances in simulation algorithms allow complex and realistic looking cloth to be simulated for use in the motion picture industry. Unfortunately, it remains quite difficult to adjust the parameters of these simulations to match a given real world cloth material. It may be possible to acquire motion data for moving cloth, and subsequently recover the cloth simulation parameters that best fit this motion data. A recent paper [11] investigated this possibility, but used only 3D geometry data for the recovery. Better simulation parameter recovery would be possible if motion data contained information about stretching, shearing and bending of the cloth, and if occlusions due to folds could be better understood. Chapter 4 disparity map with holes holeâ€”filling. smooth, dense geometry dense, panunetensed geometry reliable, matched Chapter 5 Reference image, oblique views reference Figure 1.1: Overview of cloth motion capture system. 1 Chapter 6 In this thesis, we present a new method for measuring the 3D geometry and surface parameterisation of moving cloth, captured from a stereo video sequence. Stretching, shearing and bending could be calculated from the data we measure, and it may also be possible to recover cloth simulation parameters. In Chapter 2, the previous work is discussed including papers in cloth simulation, cloth parameter recovery and cloth motion capture. Chapter 3 contains an analysis of the influence of simulator parameters on a popular cloth simulation algorithm. The subsequent chapters deal with various stages of the new cloth motion capture algorithm, as shown in Figure 1.1. Chapter 4 describes the disparity map construction, Chapter 5 describes the recovery of a surface parameterisation of the cloth, and Chapter 6 demonstrates the results obtained by the cloth motion capture algorithm. The thesis closes with some conclusions and future work in Chapter 7. Some of this material has been published previously in a different form. Chapters 5 and 6 were originally part of a paper entitled Cloth Motion written with Wolfgang Heidrich. 2 Capture [88] Chapter 2 Previous W o r k 2.1 Cloth Simulation Cloth simulation has been a topic of active research in the computer graphics community since it was introduced by Terzopolous et al. [102] in 1987. We refer the reader to Bridson's Ph.D. thesis [18] for an excellent overview of recent papers in the field, and to the second chapter [14] of Breen and House's book [52] for a broader overview of the modelling techniques used in the cloth simulation literature. See also Ng and Grimsdale's survey paper [82] for a more complete review of early cloth simulation methods. Each of these sources has a distinct interpretation, and we personally tend to agree more with Bridson's analysis than with Breen's approach. Most cloth simulation techniques can be classified into three general groups: elastic deformation models, particle-based models and finite element (or continuum mechanics) models. We refer the reader to [5, 38, 39, 103, 114, 117]. Feynman [42] treated cloth draping using a thin plate flexure model in his 1986 thesis. He modelled cloth as a grid of points, invented his own energy expressions for internal strain and bending resistance and then minimised the energy using a multigrid method. In their 1987 and 1988 papers [101, 102], Terzopolous et al. considered a range of types of deformable surfaces, including cloth. They gave a broad intro3 duction to the theory of elasticity, and referred readers to texts in the calculus of variations. For their simulation, they used differential equations of motion and an implicit integration scheme, and they discretised the equations using a regular grid. In 1992, Breen et al. [13, 15, 53] adopted a different formulation for cloth. They minimised energy functions in a manner similar to Feynman, but their energies were not derived from the assumption that cloth is a continuous flexible material, nor did they use elastic shells. Instead, they modelled the static drape of cloth using a set of interacting particles, and insisted that cloth is a mechanism, not a continuum. Each particle is intended to represent the crossing-point of warp and weft threads. This interpretation is problematic, since it makes computation intractable if every thread crossing-point must be simulated. In their demonstrations, a large tablecloth was modelled using a small number of particles (51 x 51), much less than the number needed to represent every thread crossing-point. One interesting aspect of Breen et al.'s system was their consideration of material properties [16, 17]. They used a Kawabata [66] system to measure the physical properties of real cloth, and used these material properties directly in their cloth simulation model. They observed that shearing behaviour (which they called trellising) was responsible for much of the differences between materials, and for maintaining constant surface area. Later work with DeVaul [34, 54] extended the Breen algorithm to include dynamic motion. Finally, this group has also had extensive contact with the textile research community, including publication in journals in that field. Members of MIRAlab have studied the problem of generating clothes for virtual actors over the last decade. The earliest contribution of researchers at MIR A L a b was Carignan et al.'s synthesis of a full set of clothing on a digital character in a 1992 paper [25], which was a first for computer graphics at the time. This paper described collision processing and garment panel stitching, and used Terzopolous' dynamics with added damping forces. In 1995, Volino et al. [107] represented the 4 cloth mechanics using an elastic deformation model, but removed topological restrictions on the model by allowing an unstructured triangle mesh; a later 1997 paper [108] simplified their approach. More recent papers from the lab have covered a range of topics, including a comparison of integration methods [110], collision detection [109] and many other subjects [30, 47, 111]. In a 1995 paper, Provot [89, 90] used a mass-spring model for cloth, which he correctly identified as a variant of the elastic deformation models. Provot made the important observation that traditional methods of cloth simulation produce a "rubbery" appearance in the cloth motion. To get around this, most users set a high spring stiffness, but explicit integration of the resulting stiff system is slower. He introduced an ad hoc method to keep spring lengths constant, greatly reducing the elastic appearance of cloth motion. Provot also treated collision response in a later paper [91]. Researchers at the University of Tubingen have been studying cloth since the mid-1990s. Eberhardt et al. [37] improved Breen's method to include cloth motion. A later paper by Eberhardt [35] studied implicit-explicit schemes for animation using particle systems, while papers by Hauth et al. [49, 50, 51] compared the performance of a range of numerical methods and preconditioners. In an upcoming paper, Etzmufi et al. [40] establish a connection between continuum mechanics and particle systems. Finally, Etzmufi et al. [41] and Mezger et al. [79, 80, 81] studied collision response in some detail, and Eberhardt et al. [36] studied knit fabrics. More recently, a 1998 paper by Baraff and Witkin [6, 7] returned to the approach of Terzopolous et a l , and introduced a new, more efficient technique for animating cloth and clothing. One major contribution of their scheme was an implicit integration scheme using a conjugate gradient solver. Since Terzopolous' work, researchers had used explicit integration schemes, leading to either "rubbery" cloth movement or a stiff system that was hard to solve, as observed by Provot. B y using an implicit scheme, Baraff and Witkin were able to take large timesteps and avoid 5 "rubbery" looking cloth. Baraff and Witkin's system also included position and velocity constraints on individual nodes, and they followed Volino's lead by using an unstructured triangular mesh. Their force model was based on energy functions, with bend forces calculated using the dihedral angle between adjacent triangles. They simulated cloth with more nodes than previous work, demonstrating one example with 8800 vertices. Unfortunately, their bending model and integration scheme required the introduction of nonphysical damping terms to reduce instability; and their system tended to remove fine wrinkles and geometric detail in the cloth. Baraff and Witkin later extended [8] their system to solve the problem of cloth tangles when self-intersection occurs in character animation. Ascher and Boxerman [4] improved the efficiency of Baraff and Witkin's integration scheme, and demonstrated the convergence of their modified conjugate gradient method. Desbrun et al. [32, 33, 78] made major approximations to Baraff and Witkin's model to achieve realtime performance with a coarse cloth discretisation, and Kang et al. [61, 62, 63, 64, 65] made further approximations for the sake of speed. Choi and Ko [27] addressed the issue of buckling in cloth. In their 2002 paper, they observed that the behaviour of cloth is quite different under compressive and tensile forces. Cloth strongly resists a tensile force, acting like a stiff spring to preventing stretching. Under a compressive load, however, it prevents compression by buckling. Choi and K o used a heuristic model of the post-buckling shape of cloth, and introduced a more complicated spring model to separate compressive and tensile forces. They used an implicit integration scheme for efficient computation, but unfortunately required a structured rectangular mesh. A recent paper [28] addressed this limitation by extending their model to triangular meshes, and discussed instabilities in traditional formulations of shear forces. Bridson et al. [19] initially tackled cloth collision processing. Most of their 2002 paper dealt with collision detection and response, and also with friction. To process the collisions, they also introduced a new integration scheme similar to cen- 6 tral time differencing. They also adopted and corrected some of Provot's techniques. In a recent 2003 paper [20], Bridson et al. treated problems more directly related to cloth simulation, focusing particularly on the preservation of wrinkles. They noted that fine tessellation of the cloth surfaces required small timesteps when damping forces were treated with an explicit integration scheme. To resolve this, they proposed an implicit integration scheme for damping forces combined with an explicit integration scheme for internal cloth dynamics, which also avoided the excessive damping of wrinkles seen in Baraff and Witkin's work. In the same paper, Bridson et al. introduced a new bending model, based on the angle between adjacent triangles in a manner similar to Baraff and Witkin. Much of their simulation model is similar to Baraff and Witkin's approach, except for a separated treatment of compression and tensile forces, an approach first used by Choi and K o . They also treated further details of collision processing. There have been a wide range of other interesting papers touching on cloth simulation. Van Gelder et al. [104, 105] examined the relation between mass-spring models and elasticity theory. Parks and Forsyth [85] studied the generalised-a integration scheme. Hutchinson et al. [56], Zhang et al. [116], Volkov et al. [112] and Villard et al. [106] have studied adaptive refinement techniques. Aono et al. [1, 2, 3] studied the novel problem of "dart insertion" in the aerospace industry, where cloth must precisely fit a particular surface shape without wrinkles. L i et al. [70, 71, 72, 73, 74] studied the motion of cloth in an air flow. X u et al. [113] used a specialised rod-based model model to simulate curtain motion. Romero et al. [92, 93, 94] and Lario et al. [67, 68] considered parallel algorithms for cloth simulation, and Zara et al. [115] looked at solving cloth simulation using a cluster. Fuhrmann et al. [43], Mezger et al. [79, 80, 81] and Huh et al. [55] all studied collision detection in cloth simulation. 7 2.2 Simulation Parameter Recovery Louchet et al. [75] were the first to attempt to recover cloth simulation parameters from motion data. They assumed that some unspecified vision system would provide their input data, which consisted of 3D positions of gridpoints on the cloth; for their tests, they used synthetic data. They used a genetic algorithm to solve an optimisation problem, yielding five unknown cloth simulation parameters. Their cloth simulator was a simple mass-spring system, and their input data was essentially a combination of geometric and parametric (fixed gridpoint) information. Jojic [57, 58, 59, 60] considered static draped cloth, whose shape is captured via a range scanner. The cloth range data was treated as a solid surface, and a cloth simulation was run to drape the cloth over the range data. A n external force was applied to attract the cloth to the range data. The process was then repeated using different parameters until a solution was found, using an optimisation approach. For the cloth simulation, he used a simple mass-spring model. His error metric in the optimisation process included only distance from the range data. Jojic's approach had several limitations. First, he treated only static simulation parameters and did not consider dynamic movement of cloth, although his approach might be extended to include dynamic behaviour. Second, he only made use of the cloth's geometry, and did not incorporate surface parameterisation data, apart from the manually detected corners of the cloth. Third, he made several assumptions about the cloth drape, including a known drape configuration (e.g., known underlying geometry). Finally, his results were mostly synthetic and were not very convincing, and he did not attempt to work with a range of fabrics. Bhat et al. [11] adopted the same general framework as Jojic, using an optimisation technique to fit simulation parameters to range data. Their input was a video sequence under structured light, and they did consider dynamic behaviour, such as damping parameters. Their error metric was based on the fit to the video data, using both silhouette matching and a thresholded "angle map" representing re8 gions of high curvature or discontinuities. They used the cloth simulation algorithm introduced by Baraff and Witkin [6], but were forced to use explicit integration to avoid excessive damping. They also noted some problems with scale invariance of parameters in Baraff and Witkin's model, and suggested a new model for air drag forces. Like Jojic, Bhat et al. did not make use of surface parameterisation in their optimisation, although they did present some useful data about the optimisation space. They did study a range of real-world fabrics, and also tested the generalisation of their measurements by synthesising new motion using the estimated parameters. Finally, they presented a comparison of complex synthesised motion and real cloth movement, although the results were not very convincing. The effectiveness of Bhat et al.'s error metric is very unclear. In Figure 3 of their paper, they show angle map error as a function of the bend and stretch parameters, varied over one order of magnitude. In this figure, error seems to be almost independent of the bend parameter, implying that they cannot reliably measure this parameter. In Figures 8 and 9, they have a good match between the simulated cloth and the captured video of static cloth. In Figure 10, however, the match is much poorer for moving cloth. It is difficult to evaluate the quality of the results obtained by either Jojic or Bhat et al. Both show clear discrepancies between the physical data and the simulation, but it is hard to determine whether these errors are due to their own methods, or due to the cloth simulation system used in their inner simulation loop. Bhat et al. describe some problems with the damping model used by Baraff and Witkin's cloth simulation, and similar issues have been discussed at length in the cloth simulation community. Both Jojic and Bhat et al. relied only on 3D geometric data. This data should contain information about folds and wrinkles in the cloth, but cannot capture local internal deformation such as stretching and shearing. Consequently, they were 9 able to measure the relative strength of bend forces, but should have had difficulty determining the strength of stretch and shear forces. Naturally, stretch and shear forces will have some impact on the global shape and drape of the cloth, but much of the effects will be hard to detect using only geometric data. Finally, without parametric information it is very difficult to deal with occluded regions of the cloth. Near a fold, it is impossible to tell how much fabric is contained in the occluded region without parametric information. Consequently, our measurement of both geometric and parametric data is a valuable contribution to the cloth parameter measurement problem. 2.3 Cloth Capture The computer vision community has shown interest in recovering the motion of non-rigid surfaces, such as cloth. The work of Guskov et al. [44, 46] is most relevant to the problem of cloth parameterisation. Guskov used cloth with a checkered pattern printed on it, and he tracked the corners of the quads to recover sparse parametric information. In a recent paper [45], he extended his earlier work to include 3D reconstruction of the surface geometry using multiple cameras. His system was targeted at real-time performance, and could not capture a large number of feature points. His accuracy degraded as the size of the quads drops below 20 x 20 pixels. Furthermore, he could not use stereo correspondence to recover detailed geometry, since his checkered pattern lacks high-frequency texture. Torresani et al. [103] used rank constraints on optical flow to track features and reconstruct 3D geometry from monocular video data. They showed some promising results for human torso, face and shoe motion, but did not attempt the more challenging problem of cloth tracking. Their tracking approach would still require a recognition phase to form an initial correspondence between features and parametric (u,v) positions. 10 Carceroni [23, 24] attempted the extremely difficult task of recovering 3D shape, reflectance and non-rigid motion of a dynamic scene using a surfel model. His results were quite promising, demonstrating the tracked position and velocities of a sheet of patterned cloth under reasonably quick motion. His approach dealt reasonably well with difficult problems such as occlusion. Like Torresani et al., Carceroni's approach would still require an initial recognition phase to establish the starting (u,v) correspondence. Each of these methods suffers from one common failing: a relatively small number of features is tracked. Our approach tracks an order of magnitude more features than any of the previous work. Finally, all of the previous work tackled the motion tracking problem, while our approach is more of a recognition method. As a result, we do not need any temporal history to allow recognition of features in an arbitrary deformed state. There have been a number of less directly relevant efforts at cloth capture. Haddon and Forsyth [48] tracked the formation of folds and wrinkles in video sequences, but did not recover geometry or parameterisation. Ruiz and Buxton [95] attempted to improve the capture of fine wrinkles in static cloth geometry, but ignored parameterisation. 11 Chapter 3 C l o t h Simulation Experiments As part of our investigation of cloth simulation parameters, we wrote a cloth simulator. We implemented the simulator described by Baraff and Witkin [6], and released the software publicly with the name Preecloth. In Section 3.1, we discuss some corrections to Baraff and Witkin's paper. Using this simulator, we investigated the influence of each of the simulator's parameters. Details of this are discussed in Section 3.2. 3.1 Cloth Simulator For our experiments, we used a simulator based on the approach of Baraff and Witkin. However, we modified their approach to include corrections made by other researchers, as well as improvements based on our own insights. Our implementation of Baraff and Witkin's algorithm included Ascher and Boxerman's corrections [4] to the modified preconditioned conjugate gradient algorithm, as well as their improved preconditioner. Bhat et al. [11] noted issues with Baraff and Witkin's air drag formulation, and suggested corrections. We did not implement these corrections to air drag in our own cloth simulator. They also observed problems with excessive damping using the first-order implicit Euler time integration scheme used by Baraff and Witkin. 12 We note here a few corrections of our own. In particular, Baraff and Witkin's parameters are not scale-invariant. If a mesh is subdivided while all parameters are kept constant, the shape of the cloth changes substantially, beyond what would be expected through the simple introduction of a few edges for bending. Baraff and Witkin defined forces in terms of what they called condition tions func- (C), which are closely related to energy (E): E = k 2 C T (3.1) C They defined separate energies for stretching, shearing and bending. They presented a correct argument for keeping the bend condition function independent of triangle area, but defined the stretch and shear condition functions to be directly proportional to triangle area. Consequently, the stretch and shear energies are proportional to the square of the triangle area. If a triangle is refined In a standard l-to-4 split, the total energy of the four new triangles will be one quarter of the original energy. Since bend and gravity energies are independent of tessellation, this makes stretch and shear forces relatively weak at higher tessellations, and dramatically changes the shape of the cloth drape as the cloth is refined. We recommend modifying Baraff and Witkin's condition functions to be proportional to the square root of the triangle area, making the energies directly proportional to triangle area. The stretch condition function in Baraff and Witkin's equation (10) should be changed to use the square-root of the area, \ J | w â€ž ( x ) - 6â€ž|| J and the shear condition in section 4.3 of their paper should be likewise be changed, C(x) = V a w ( x ) w â€ž ( x ) . T n This will make the cloth simulation parameters independent of mesh tessellation. Bhat et al. independently made the same observation. 13 Finally, in equation (11) of Baraff and Witkin's paper, damping forces are calculated using C(x), which they defined as Correct partial differentiation of C(x) should give where m ranges over all particles influencing C . This was likely the authors' intent, but it is unclear (and even a little misleading) in their paper. 3.2 Influence of Parameters For some cloth simulation algorithms [17], the relationship between the simulator's parameters and the mechanical behaviour of real cloth has been well-established. However, Baraff and Witkin's simulator has not been subjected to such study, and it is not intuitively obvious how the simulator's parameters affect cloth motion, or how they interact. We set out to investigate the effect of the individual parameters on cloth movement. Bhat et al. [11] are the only authors to present plausible parameter values for Baraff and Witkin's cloth simulator. The base values used in our simulation are shown in Table 3.1. Bhat et al. used a different drag model, and did not use the M P C G algorithm or adaptive time stepping requiring a stretch limit. They did report stretch, shear and bend resistances and damping parameters that were within an order of magnitude of the parameters we used. To evaluate the influence of the individual parameters, a series of simulations was performed. The setup involved the draping of a tablecloth over a circular table. The cloth was modelled as a square sheet of 66 x 66 square patches with a regular split into triangles. In each experiment, only a single parameter was varied, and a number of statistics were recorded, including the appearance of the cloth and the 14 Parameter Stretch resistance Shear resistance Bend resistance Stretch clamping Shear damping Bend damping Air drag MPCG tolerance stretch limit Symbol h Value 100 10 1.0 x 10 20 2 2.0 x 10 0.1 0.01 5.0 x 10 5 6 5 Table 3.1: Parameter values for the modified scale invariant version of Baraff and Witkin's simulator. (a) Stretch energy (b) Shear energy (c) Bend energy (d) Combined Figure 3.1: Stretch, shear and bend energies are combined as the red, green and blue channels of a single image to visualise the overall energy distribution during cloth simulation. spatial distribution of stretch, shear and bend energy in the cloth. In the results that follow, spatial energy distributions are visualised by encoding the logarithm of the stretch, shear and bend energies in the red, green and blue channels of the image respectively, as shown in Figure 3.1. The experiments were limited to a single drape configuration, and only one parameter was changed at a time. Consequently, we can draw few substantial conclusions about the general behaviour of Baraff & Witkin's cloth model; we limit this section to our observations. 3.2.1 Number of patches The effect of changing the discretisation of the cloth surface is demonstrated in Figure 3.2. In this particular tablecloth example, it appears that 66 x 66 patches is 15 a sufficiently fine discretisation for a reasonable simulation. Both the final drape and the energy profile are very similar for the 66 x 66 case and the much finer 132 x 132 example. It is interesting to observe the changing energy profile in lower tessellation examples. When the surface was discretised coarsely, the cloth was very limited in its ability to bend, and was consequently forced to shear substantially. With finer discretisations, bending rose slightly and shearing dropped dramatically. The only real difference between the finest discretisations was a slight change in bending behaviour. Clearly, the appropriate level of discretisation is highly application-dependent. A discretisation of 66 x 66 was sufficient for this tablecloth, but might be a poor choice for a complicated piece of clothing with finer wrinkles and many regions of high curvature. 3.2.2 Timestep Large timesteps are known to introduce numerical damping, as demonstrated here. In this experiment a fixed timestep was used, and the damping impact can be seen in the mid-swing pose of the cloth shown in Figure 3.3 and also in the energy graph. Baraff and Witkin's "goal of using large timesteps will clearly also force the cloth motion to be damped. In terms of cloth parameter recovery, this result is quite significant. It implies that cloth parameters can only be reused in other simulations operating at the same timescaleâ€”if at all. Clearly, this behaviour needs further study if cloth parameter recovery is to be practical. When using adaptive timestepping, varying amounts of damping were introduced into the system as the timestep grew and shrank, making it difficult to compare results between different trials. To reduce the effect of this behaviour, timesteps were kept small (5 ms) in the experiments that follow. 16 patches drape (2.4 s) total energy energy (2.4 s) â€¢^1 22 x 22 33 x 33 . > 66 x 66 Time 1 ? m 99 x99 Time 132 x 132 Hole Legend Hi â€” Stretch Shear Bend Figure 3.2: Impact of discretisation on tablecloth drape and energy distribution. 17 total energy energy (0.4 s) Energy drape (0.4 s) 0.001 0.002 0.005 H n ' Â» â€¢ â€¢ Energy 0.010 0.020 Time Figure 3.3: Impact of timestep on drape and energy distribution. 18 3.2.3 Stretch, shear and bend resistance The effect of changing the cloth's resistance to stretch, shear and bend is demonstrated in Figures 3.4-3.6. Changes to the stretch resistance had little effect on the movement of the cloth. The final drape and the transient motion were essentially unaffected over a wide range of values, although the total stretch energy stored in the cloth did change. With higher stretch resistance, stretch energy reached equilibrium rapidly, and less stretch energy was stored in the cloth in the transient regime. Modifying the cloth's shear resistance had a more visible effect. With low shear resistance, the cloth's final drape showed more sag, and the shearing was quite evident in the cloth texture. When shear resistance was low, more shear energy was stored in the cloth and the cloth swung freely. When the shear resistance was higher, the cloth motion appeared highly damped. Changes to bend resistance obviously influenced the cloth's shape. With high bend resistance, relatively few wrinkles formed, and the bends that did form stored a large amount of bend energy. 3.2.4 Damping constants From our observations of both real and simulated cloth, the only aspect of cloth motion that was visibly damped was bending. Both stretching and shearing behaviour seemed to be overdamped, while bending behaviour was either underdamped or overdamped, depending on the cloth material. In the tablecloth draping experiments, the cloth either settled slowly on the table or else fell quickly onto the table and swung back and forth several times before settling to a steady state. This corresponded to overdamped and underdamped behaviour, respectively. In the energy graphs, this can generally be seen by looking for ringing behaviour in the total bend energy. The impact of the stretch damping constant was fairly minimal. 19 Subtle k st energy (2.4 s) total energy Legend a Stretch Shear Bend Figure 3.4: Impact of stretch resistance on energy distribution. 20 drape (2.4 s) energy (2.4 s) total energy Time 10 m mm? w Time 50 Wf<, Time Legend â€¢mm Stretch Shear â€” â€¢ Bend Figure 3.5: Impact of shear resistance on drape and energy distribution. 21 drape (2.4 s) energy (2.4 s) total energy x 10 - x 10 w x 10" * Legend Stretch mm* Shear Bend Figure 3.6: Impact of bend resistance on drape and energy distribution. 22 d st energy (0.32 s) total energy Legend mmm Stretch â€” Shear mm Bend Figure 3.7: Impact of stretch damping constant on energy distribution. 23 d sh energy (0.08 s) total energy 0.02 2.00 4.00 Time Legend mmt Stretch Shear Bend Figure 3.8: Impact of shear damping constant on energy distribution. damping in the motion of the cloth was evident during thefirstsecond of movement, but the final drape was unaffected. As shown in Figure 3.7, the energy graph shows changes to the transient energy distribution, with obvious damping effects in the stretch energy as the damping constant rose. Curiously, with very low stretch damping (e.g., d t < 2), the simulation could not be computed. s The shear damping constant also had only a minor effect on the cloth's behaviour. The cloth's final drape and motion were unaffected by changes to this constant. The energy graph shows predictable underdamped and critically damped behaviour in the shear energy, but the transient behaviour was brief enough that it had no major effect on the cloth's motion. Figure 3.8 shows the cloth energy distribution near the beginning of the simulation. 24 energy (0.16 s) k energy (0.52 s) total energy 10 Time 10~ 6 % 1 10 Figure 3.9: Impact of bend damping constant on energy distribution. 25 The bend damping constant had a very visible effect on the cloth's movement. As shown in the energy graphs in Figure 3.9, the bend energy was quite different as the constant was changed, and this could also be seen in the cloth's movement, particularly at the corners. The damping was predictable and followed a typical underdamped/overdamped form, but there was also some interesting smoothing. When the bending damping constant was low, fine wrinkles formed in the cloth during the early transient motion, while damping prevented these wrinkles from forming when the bending damping constant was higher. The final drape position was the same in all cases, however. 26 Chapter 4 The Disparity M a p As described in the introduction, the bulk of this thesis addresses the issue of cloth motion capture. In this chapter, some of the details of the first stage of the cloth motion capture system are discussed, covering the construction of a disparity map from input multibaseline stereo images. The output of this stage of our system is three images of equal size: a rectified greyscale camera image of the cloth and backdrop; a mask to distinguish the cloth from the backdrop; and a disparity map, from which the depth at every pixel can be inferred. The greyscale image and disparity map can be generated with a standard stereo vision system, and the mask can be easily defined using background subtraction. Rectified images and epipolar geometry are a well-understood subject in computer vision. Given a suitable system for camera calibration, it is easy to produce rectified images [84]. Stereo correspondence algorithms take two (or sometimes more) rectified greyscale images as input, and produce a disparity map d(x, y) for each pixel in one of the input images, typically stored as a greyscale image. Figure 4.1 demonstrates this process, although the disparity map shown here is somewhat idealised. The term disparity was originally used to describe the 2D vector between the positions of corresponding features seen by the left and right eyes. It 27 is inversely proportional to depth, and it is possible to define a mapping from (x, y, d) triple to a three-dimensional position. top left right Figure 4.1: Stereo correspondence algorithms take two (or more) rectified images as input and produce a disparity map. There are a wide range of stereo correspondence algorithms. We refer the reader to the excellent survey by Scharstein and Szeliski [97, 98, 99] for a taxonomy of the available techniques. We used the Sum of Absolute Differences (SAD) correlation method to reconstruct disparity maps. This is a very simple approach with a number of major artefacts, and in the remainder of this chapter we discuss our solutions to the shortcomings of S A D correlation. However, it should be noted that a more sophisticated stereo correspondence algorithm (such as the graph cuts approach) might be a more suitable solution, and could be easily substituted. The SAD correlation method yields three major types of artefacts. First, in some regions disparities are uncertain, and are left as "holes" in the disparity map, 28 as demonstrated in Figure 4.2(a). Uncertainty can occur for a variety of including insufficient texture, depth discontinuities or noisy images. () a (b) (c) Figure 4.2: (a) original disparity map with holes; (b) hole-filled integer disparity map; (c) after sub-pixel estimation. Intensity levels have been exaggerated to emphasise quantisation. Second, most disparity maps are only computed to integer precision, i.e. d(x,y) 6 Z . When these disparities are inverted to obtain depth, the resulting depthmap is visibly quantised, yielding a very jagged surface. Some algorithms attempt to calculate a fractional part for each disparity using sub-pixel estimation, but such techniques are still tentative and can produce incorrect results [100]. A n example of the errors corrected by sub-pixel estimation is shown in Figure 4.2(b). Third, window-based stereo correspondence algorithms often exhibit a "foreground fattening" effect near depth discontinuities between two objects. When this happens, samples from the far object are mistakenly measured as having the same disparity as samples on the near object, as demonstrated in Figure 4.3. The stereo system we used is prone to all three of these problems. We have developed a technique that smoothly fills holes and finds a fractional part to each disparity to create a smoother surface, but we have no way to solve the problem of foreground fattening. The fractional part is not measured from the input images, as in the traditional sub-pixel estimation algorithms used by the vision community, but is instead smoothly interpolated from the measured integer disparities. 2!) (a) (b) Figure 4.3: Demonstration of the foreground fattening effect: (a) input image, with foreground cloth on left and black background, (b) disparity map produced by stereo correspondence algorithm. We do not claim that our solution is a novel contribution to the field; we merely document our approach in the interest of thoroughness. Our solution is adapted to the particular needs of the stereo system we used, but it is likely possible to find an existing stereo system that exhibits none of these problems. In the future, we expect that standard stereo systems will solve these problems, and output from a stereo system can be used directly without the modifications described here. We have the option of operating on either the two-dimensional disparity map, or the corresponding three-dimension surface. Given the structured nature of our input data, we choose to operate directly on the disparity map in a two-dimensional manner for the sake of efficiency. 4.1 The P D E Approach Both hole-filling and sub-pixel estimation can be formulated as image interpolation problems. Image interpolation is an image-based technique that involves filling holes in an image with plausible data. The hole is not necessarily filled with smooth data, but may sometimes involve extending discontinuities at the hole edge into the hole. It has been well studied by researchers such as Bertalmio et al. [10], Caselles et al. [26] and Perez et al. [86], and is also studied as part of the larger problem of 30 image in-painting. The general approach involves fixing the boundary of the hole, and then solving a boundary-value partial differential equation (PDE) to interpolate the interior of the hole. This is equivalent to applying a diffusion process, such as isotropic diffusion or one of the many forms of anisotropic diffusion. For more details on isotropic and anisotropic diffusion, refer to Black et al. [12]. For a detailed description of the relation between diffusion and partial differential equations, see Sapiro's excellent book [96]. Caselles et al. also considered a different problem. They started with a quantised image, i.e. only a limited set of intensity values, such as multiples of 30. From this, they wished to produce a smooth image with integer intensity values using an image interpolation algorithm. This would also produce a satisfactory solution to our sub-pixel estimation problem; the disparity map can be viewed as a quantised image, and smooth interpolation of the data would be a satisfactory solution. Caselles' approach can be explained using a one-dimensional example, as shown in Figure 4.4. Suppose that the image I(x) is quantised to image I (x) by q rounding image intensities to the nearest integer multiple of 5. We aim to interpolate I (x) q to form a smooth interpolated image Ii{x). and x\ at a step edge, Iq(x\) = I (xo) q Consider two adjacent points, XQ + 6. Clearly, the intensity of the unquantised image / crossed the mid-intensity point I (xo) q + | somewhere between XQ and x\. We can take advantage of this and force the high point of each step edge down to the mid-intensity point, i.e. fix Ii(xi) = I (xo) q + f. Finally, these fixed points are interpolated. A special case is required for step edges larger than 5, in which case both the high and low side of the edge are fixed. Extension to a two-dimensional image is straightforward, with the fixed points forming closed Jordan curves in the plane. Caselles called these the boundaries of the level sets, but it should be noted that his level sets are not directly related to standard levelset methods in computer graphics [83]. 31 Disparity u - *{Â«) 35 Fixed point 2S H h H h H 1 h (a) Figure 4.4: (a) one-dimensional example of Caselles' approach, with black showing quantised disparity map and red showing disparity map after interpolation using diffusion; (b) boundaries of level sets in two-dimensional case. We implemented Caselles' approach, using a simpler isotropic diffusion process for both hole-filling and interpolation of the quantised disparity map. An isotropic diffusion processfindsa solution to V (7) = 0, 2 which is also known as Laplace's Poisson's V 2 equation, equation. (4.1) Laplace's equation is a special case of and is a classic example of an elliptic PDE. In this formula, the operator is the Laplacian, where V (/) 2 = div(W). Implementation of this approach was quite straightforward. The PDE was solved by using an explicit integration scheme, with dl /((+ A1) = /(() + At^g where g = vveÂ». 32 and A t = 1. To improve performance, a hierarchical approach was used, solving first on a low-resolution image, then using those results as the starting point for diffusion on a higher-resolution image. Initially, the results from this approach seemed reasonable. Performance was quick, requiring only about two minutes per frame. Holes were smoothly filled, showing CÂ° continuity and C continuity with the fixed hole boundary. Quantisation 1 artefacts were resolved, with CÂ° continuity. However, there were C 1 continuity problems at the fixed boundaries of the level sets used to interpolate the quantised disparity map. The diffusion process did yield C continuity on either side of the l levelset boundary line, but the derivatives on either side of the boundary were not identical. Consequently, the image gradient had clearly visible discontinuities along the boundaries of the level sets. Ultimately, more control was needed at the boundaries during diffusion. Like Caselles, we fixed the value of the function at the boundary, known in the P D E literature as imposing Dirichlet equation. Cauchy conditions conditions on the boundary value partial differential are a standard alternative, where both the value and the gradient are specified at the boundary as described in [87]. Unfortunately, Cauchy conditions cannot be used, since the gradient at the boundary is unknown; we only want the gradient on either side of the levelset boundaries to be the same. It is possible that the biharmonic equation could provide this control over the system, but we leave this as future work. 4.2 The Optimisation Approach P D E methods were satisfactory for hole-filling, but could not solve the sub-pixel estimation problem. Using a diffusion-based approach, the only way to interpolate the existing data to perform sub-pixel estimation was by introducing fixed boundaries of the level sets. However, the interpolation can be achieved in a different manner. As before, a solution to Laplace's equation (Equation 4.1) is desired, starting 33 from a variant, V ( / + A / ) = 0, (4.2) 2 with I held constant and solving for Al. A strict interpolation of the quantised data can be achieved by constraining Al to lie between â€” | and | . Under this constraint, an exact zero solution to Laplace's equation may not be found, but the equation can be solved in a least-squares sense. In other words, find Al that minimises ^ [ V ( / ^ + A/ ,,)] 2 x subject to â€” | < AI XtV 2 ' (4.3) < | . This is an optimisation problem, not a partial differen- tial equation problem. We use a finite-difference representation of the Laplacian, V ( 7 + Al) = (I + A / ) , _ i + (/ + AI) , 2 x y x y+1 + + A/) _i,â€ž + (/ + A / ) i x I + > y - 4 ( J + AJ) â€ž. (4.4) X) With a little juggling and remapping of indices, this can be expressed as a linear system A x = b. The image Al is flattened to form the vector x. Suppose that Al is w pixels wide by h pixels high. Then, the first w entries of x are filled with the top row of Al, followed by the second row, and so on. The constant coefficients of Al are placed in the A matrix, and the constant I values are placed in vector b. As shown in Figure 4.5 the matrix A is sparse with the standard 5-point Laplacian structure, sometimes known as "tridiagonal with fringes." The main diagonal represents the central count in the finite-differencing scheme, the upper and lower diagonals correspond to the right and left neighbours respectively, and the fringe diagonals correspond to the lower and upper neighbours. The value a* on the main diagonal is initially adjusted to ensure that the sum of each row is zero. 34 1 1 1 1 -a 3 1 -a-i+l 1 -a -2 n 1 1 1 1 Figure 4.5: General structure of A matrix used by optimisation approach for subpixel estimation. The neighbour count O j is equal to the sum of the other elements of the row (typically 4). The problem can now be expressed in a simple, classic form. Find x that minimises |Ax-b||, (4.5) subject to â€” | < X j < | This is a constrained linear least-squares minimisation problem. We use Matlab to solve this equation, and Matlab uses a subspace trust-region method based on the interior-reflective Newton method, as described by Coleman et al. [29]. Some small modifications are made to this scheme for practical purposes. Not all entries in I are valid, and this must be accounted for. Invalid samples are excluded from both the A and b matrix. We adjust the central count to include only the number of valid neighbour samples. Finally, for hole-filling, the boundary values surrounding the hole are included in b but excluded from A . In practical terms, this algorithm performs quite slowly. A hierarchical version performs much better, and some minor edits to Matlab's source files can improve performance to about three minutes per frame. The appearance of the results 35 is satisfactory, exhibiting both CÂ° and C continuity. 1 As noted before, the optimisation approach is only needed for sub-pixel estimation. Both the P D E and optimisation approaches produce satisfactory results for hole-filling, and the P D E approach yields better performance. 36 Chapter 5 Parameterisation The parameterisation of the cloth surface follows several stages, similar in principle to stages in many computer vision systems. First, features are detected in the intensity image. Each feature is then matched with features in a flat reference image of the cloth. The global structure of the parameterisation is analysed, and invalid features are rejected. Finally, parameter values are interpolated for every pixel in the input image. 5.1 Feature Detection For feature detection, we use Lowe's Scale-Invariant Feature Transform (SIFT) [76, 77]. Features detected using SIFT are largely invariant to changes in scale, illumination, and local affme distortions. Each feature has an associated scale, orientation and position, measured to subpixel accuracy. Features are found at edges using the scale-space image gradient. Each feature has a high-dimensional "feature vector," which consists of a coarse multiscale sampling of the local image gradient. The Euclidean distance between two feature vectors provides an estimate of the features' similarity. Lowe used SIFT features for the object recognition task, and considered only rigid objects with a very small number of degrees of freedom. See Brown and Lowe's 2002 paper [21] for an example of object recognition. A n upcoming paper 37 by the same authors [22] uses SIFT for image registration in panorama stitching, a very different problem. We make heavy use of SIFT features, but we must adapt the matching to the parameterisation of cloth, a deformable surface with a very high number of degrees of freedom. We detect features in two different images. A scan of the flattened cloth is used to obtain the reference image, a flat and undistorted view of the cloth. We use the 2D image coordinates of points in the reference image directly as (u,v) parameters for the features. This 2D parametric reference space is denoted 1Z. The second image is the input intensity image, called the captured image here. We refer to this 2D image space as the capture space, and denote it C. We also work in world space W , the three-dimensional space imaged by the stereo system. Capture space is a perspective projection of world space, and the disparity map provides a discretised mapping from capture space to world space. We map disparity values at discrete locations back to world space and use linear interpolation to obtain a continuous mapping. Finally, we also work in the feature space T. This is a 128-dimensional space containing the SIFT feature vectors for both the reference and the captured features. Capture space World space Reference space Figure 5.1: Capture space C is an image of 3D world space W . Reference space TZ is a flattened view of the cloth. After applying SIFT to the reference and captured images, we obtain two 38 sets of features, F = {r |p(r) G H,f(r) G F) r F = {c\p{c) â‚¬C,f(c) G .T } 7 c where p(x) is the position of feature x within the image, and f(x) is the feature vector associated with x. Each feature also has an associated scale s(x) G R. A n example of these feature sets is shown in Figure 5.2. Figure 5.2: (a) reference feature set F ; (b) captured feature set F . r c If we can establish a one-to-one mapping between reference features and captured features, then we know both the world space position and the reference space position of every captured feature, allowing parameterisation. In the matching stage of the algorithm described in Section 5.2, we construct this one-to-one mapping, which we label $ : C â€”â€¢ TZ. It should be noted that a one-to-one mapping is only feasible if the pattern in the reference image has no repetitions. Cloth strongly resists stretching, but permits substantial bending; folds and wrinkles are a distinctive characteristic of cloth. This behaviour means that sections of the cloth are often seen at oblique angles, leading to large affine distortions of features in certain regions of the cloth. Unfortunately, SIFT features are not invariant to large affine distortions. 39 To compensate for this, we use an expanded set of reference features. We generate a new reference image by using a 2 x 2 transformation matrix T to scale the reference image by half horizontally. We repeat three more times, scaling vertically and along axes at Â±45Â°, as shown in Figure 5.3. This simulates different oblique views of the reference image. For each of these scaled oblique views, we collect a set of SIFT features. Finally, these new SIFT features are merged into the reference feature set. When performing this merge, we must adjust feature positions, scales and orientations by using T . This approach is compatible with the recommendations - 1 made by Lowe [77] for correcting SIFT's sensitivity to affine change. Figure 5.3: Top row: a reference image and a horizontally scaled oblique view. Bottom row: other oblique views. 5.2 Matching The Euclidean distance in T given by ||f (r) â€” f (c)|| is the simplest metric for finding a match between a reference feature r 6 F and a given captured feature c 6 F . r c Unfortunately, in our tests with cloth this metric is not sufficient for good matching, and tends to produce a sizable number of incorrect matches. We would like to enforce an additional constraint while performing feature 40 matching. The spatial relationship between features can help to eliminate bad matches: any pair of features that are close in reference space must have matches which are close in capture space. The converse is not always true, since two nearby captured features may lie on opposite sides of a fold. If we could enforce this capture/reference distance constraint during the matching process, we could obtain better results. We can extend this notion by thinking about distances between features in world space. Suppose that we have complete knowledge of the cloth surface in world space (including occluded areas), and can calculate the geodesic distance in W between two captured features c , c G F : s n Ad c = g{c ,c ). c s (5.1) n Now, consider two reference features r ,r s n e F , which are hypothetical r matches for c and c . We know the distance in 7Z between r and r , but we do s n s n not know the distance between them in W. By performing a simple calibration step, we can establish a scalar multiple relating distances in these two spaces. We will multiply by a to map a distance from TZ to W , and multiply by a~ for the l r opposite mapping. Using a , the world space distance between the reference features can be r calculated. Ad = a -||p(r )-p(râ€ž)|| r r (5.2) s We will use these two distances to define the compression constraint and the stretch constraint: Ad (l r - k ) < Ad s < Ad (l c r + k) (5.3) s where k is a constant denning the maximum allowable stretch. s We refer to the lower bound on Ad as the compression constraint, and the c upper bound is called the stretch constraint. If Ad > Ad (l c 41 r + k ), s then this choice of match implies that the captured cloth is very stretched; similarly, if the compression constraint is violated, then this choice of match implies that the captured cloth is very compressed. Provided that a reasonable choice is made for k , we can safely s reject matches that violate the stretch constraint or the compression constraint. Figure 5.4 illustrates these constraints. Figure 5.4: If we fix two captured features c and c and one reference feature r , the stretch and compression constraints require the remaining reference feature to lie in a ring centred on r . The ring's inner and outer radii are derived from Equations 5.2 and 5.3. s n s s In our real-world setting, finding the geodesic distance between captured features is more difficult. In situations where the entire cloth surface between c s and câ€ž is visible, we define a straight line between c and c in C, project this line s n onto the surface in W , and integrate along the line. This will not find the geodesic distance, but will closely approximate it. Ad = c ~g{c ,c ) s While this tends to overestimate g(c ,c ), s n n (5.4) it is still preferable to computing the actual geodesic distance, which is prohibitively expensive. In some situations, sections of the cloth surface on the geodesic line between 42 c and c will be occluded. We can detect such situations using the same line s n integration method as before, scanning for discontinuities in depth along the line. When occlusion occurs, there is no way of estimating the actual geodesic distance g(c ,c ). s However, we can still use g(c ,c ), n s underestimate of g(c ,c ). s n n which in this case is likely to be an The stretch constraint can be applied to these features, but we cannot use the compression constraint, since the amount of fabric hidden in the fold is unknown at this point. In contrast to the distance metric in feature space, the stretch and compression constraints are applied to pairs of matched features. To accommodate this, we adopt a seed-and-grow approach. First, a small number of seeds are selected, and these seeds are then matched using only the feature space distance metric. For each seed, we "grow" outwards in capture space, finding nearby features and matching them. As we find features, we can use a nearby pre-matched feature to enforce the stretch constraint. 5.2.1 Seeding The seeding process is straightforward. We select a small subset of captured features F' C F , and find matches for them in a brute force manner. For each c 6 F' , we c c c compare against the entire reference feature set F , and we use the feature-space r distance between c and r G F r to define the quality of a match. To improve the speed of the brute force matching, we use Beis & Lowe's best bin first algorithm [9]; this is an approximate search in a k-d tree. (It is approximate in that it always returns a close match, but not always the best match possible.) We then sort F' c by the feature-space distance, and apply the growth process on each seed in order, from best-matched to worst. The growth process classifies captured features into three sets: matched, rejected and unknown. If a seed fails to grow, the seed itself is classified as rejected. After all seeds have been grown or rejected, we construct a new F' from the remaining unknown captured features. c 43 1 To help the process, we prefer captured features with a large SIFT scale s(c) when selecting F' . In the first iteration, F' consists of the largest features, c c followed by a smaller group, and so on until a minimum scale is reached. Large features are only found in relatively flat, undistorted, and unoccluded regions of the cloth. In these regions, the growth process will be able to proceed rapidly without encountering folds or occlusions, rapidly reducing the number of unknown features. This rapid growth reduces the number of features which must be considered as seed candidates. The use of the seeding process should be reduced as much as possible, since it cannot make use of the stretch and compression constraints, and hence must resort to relatively inefficient and unreliable brute force matching. 5.2.2 Growing The growth process is controlled with a priority queue. Each entry in the priority queue is a matched source feature c e F on the edge of the growth region. The s c queue is sorted by capture space distance from the seed, ensuring an outward growth from the seed. The queue is initialised with the seed point alone. The source features are extracted from the queue one at a time. Let us consider one such source feature, consisting of c and r = <fr(c ). To s s s grow outwards, we iterate over all features c in the neighbourhood N(c ) of c in n s s capture space. N(c ) is a circle of radius r centred on c . For a given câ€ž, the match s c s candidates are the reference space features which pass the stretch and compression constraints. These candidate features lie in a ring around r , as shown in Figure 5.4. s To select the best match among the match candidates, we use the feature space distance ||f(câ€ž) â€” f(râ€ž)|| for each candidate r â€ž . The closest match is accepted, provided that the distance in T is below a threshold. The growth process requires knowledge of neighbouring features in capture space, and neighbours within a ring in reference space. We efficiently retrieve these neighbours by performing binning in a preprocessing stage. 44 5.3 Verification The growth algorithm enforces constraints during the matching process, but it only works with two features at a time. A feature matched by the seed-and-grow process may be acceptable when compared with one of its neighbours, but it may be clearly incorrect when all neighbours are examined. During the growth process, however, it is difficult to perform any global verification, since information about the cloth is sparse and incomplete. After the seed-and-grow algorithm has completed, we can verify the accuracy of matches. At this stage, we will only reject bad matches, and will not attempt to make any changes to <fr(c). We attempt to correct two types of errors in the matching process. In the following, we will refer to the features matched during growth from a single seed as a seed group. A feature error occurs within a seed group, when a few isolated features in the group are badly matched but the bulk of the group is valid. A seed error occurs when a bad seed is accepted, in which case the entire seed group is invalid. We propose a three-stage solution to deal with these errors. The stages are very similar, so we describe the general operation first. We operate on the Delaunay triangulation of the captured features, and we use a voting scheme to determine the validity of features or seed groups. One vote is assigned to each outwards edge. For a feature, every incident edge is used; for a seed group, every edge connecting a seed group feature to a different seed group is used. The vote is decided by evaluating the stretch and compression constraints on the edge. Finally, we calculate a mean vote for each feature or seed group, and reject the features or seed groups with the poorest mean vote. We repeat the process until all features or seed groups pass a threshold mean vote. In the first stage of verification, we operate on each seed group in turn, and consider only feature errors within that seed group. Subsequently, we consider only seed errors between the seed groups. Finally, we do a repeat search for feature errors, this time operating on the entire set of remaining features. Typically, this 45 final stage helps to eliminate bad features at the edge of the seed groups. The entire verification process could be formulated as a simulated annealing algorithm. This would have the benefit of a better theoretical grounding; a continuous measure of error instead of a pass/fail threshold; and it would be easier to extend to include different types of errors. A simulated annealing scheme might also be suitable for correcting interframe errors, improving temporal coherence. This is left as future work. 5.4 Geometry Parameterisation O o o o o o o o o o H:H:::!i â€¢ â€¢ â€¢-* â€¢ â€¢ â€¢ â€¢ â€¢ â€¢ 9 disparity sample O (u, v) sample 0 o o o o o o o o o o o o o o o o o o o O o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o 0 o o o o o disparity + (u, v) sample Figure 5.5: After verification, we have dense, regular disparity samples and sparse irregular (u,v) samples. We interpolate the (u,v) samples to achieve a uniform regular sampling of both geometry and parameterisation. After verification, we are left with a set of reliable features, and a dense, regularly sampled disparity map, as shown in Figure 5.5. We would like to construct a unified representation that contains both 3D and parametric data, sampled in the same pattern. We choose to interpolate the parametric information given by the features to construct a dense, regularly sampled parametric map corresponding directly to the disparity map. A n interpolation in capture space is not sufficient, as demonstrated in Fig46 ures 5.6 and 5.7. As can be seen, linear interpolation in capture space leads to unacceptable distortions on the surface in world space. Instead, what is needed is linear interpolation along the surface (the arc in Figure 5.6). This must be extended from the one-dimensional example in the figure to a surface. 0 I 0.4 0.5 1 1 1 1 C T H W 1 Figure 5.6: Example where linear interpolation of parameter values in C results in distortion of parameters when projected into W . This problem is similar in principle to the non-distorted texture mapping problem described by Levy and Mallet [69] and others. Their technique enforced two primary constraints, perpendicularity and constant spacing of isoparametric curves on the surface. These goals are unfortunately not the same as our own: we desire constant spacing of isoparametric curves, but we would like to allow nonperpendicularity. In the language of the cloth literature, little or no stretch is permitted, while shearing may take place. Our problem is therefore subtly distinct from many of the standard problems in non-distorted texture mapping or mesh parameterisation. First and foremost, we aim to perform a pure interpolation, retaining the parameterisation at all feature points. We choose to operate on individual triangles within the capture space Delaunay triangulation of the feature points. Within each such triangle the goal, like Levy & Mallet, is to have constant spacing of isoparametric curves. We make no guarantees of C or C continuity across triangles. 1 2 Our interpolation scheme is recursive, and operates on a triangle mesh in 47 Figure 5.7: Left: capture space interpolation. Right: our interpolation method. capture space, typically a Delaunay triangulation of the input features. Parameters are known at every vertex of the mesh. Each triangle represents a curved surface patch, with the shape of the patch defined by the underlying disparity map. We recursively subdivide each triangle into four smaller triangles using the standard 4-to-l split, but with one slight difference. Instead of inserting new vertices at the capture space midpoint of each edge, we insert at the geodesic midpoint. In other words, if the endpoints of an edge are given by c\ and C2, the new vertex v G C satisfies g{c\, v) = g(v, c ) (where g is the approximate geodesic distance from 2 Equation 5.4), but it does not in general satisfy ||p(ci) - u|| = \\v â€” p(c2)||. Since this point lies midway between the endpoints, its parametric position is the average of the endpoints' parameters. We form four new triangles using the three original vertices and the three new midpoint vertices, and proceed recursively on the smaller triangles. The recursion stops when a triangle encloses exactly one disparity sample. 48 At this point, the triangle can be treated as flat. To find the parameters at the disparity sample location, we associate barycentric co-ordinates with the sample location and linearly interpolate the parameters of the triangle's vertices. This interpolation scheme still has several problems. It is possible that the correct interpolation between two features in C follows a slightly curved path in TZ, instead of the straight line path used in this interpolation algorithm. The distortion caused by this approximation should be relatively subtle. More importantly, folds should receive special treatment during interpolation. In theory, it may be possible to make a reasonable guess about the world-space position of occluded regions hidden by the fold, but we leave this as future work. The final issue in interpolation is finding an appropriate way to resist shearing. In our approach, shearing is not dealt with directly (as Levy and Mallet did), but we are not certain that this is the best decision. Cloth permits shearing, but it does also resist it. Our scheme does not explicitly incorporate this behaviour. Any algorithm which does mix stretch and shear resistance will have to choose a means of balancing resistance to these two types of forces. It is hard to envision a suitable way of balancing stretching and shearing without some knowledge of the cloth material; we leave this as future work. 49 Chapter 6 Results In this chapter, the results produced by our cloth capture system are described in detail. A 63 x 67 cm cloth was selected for capture, with line art images printed on it in a distinct, non-repeating pattern. The SIFT system detects features using edges, and line art provided a natural way of obtaining a high density of edges. The system was tested with several cloth motions. The principal test consisted of drawing one corner of the cloth along a string, over the course of 20 frames. The numbers cited here refer to this dataset. Figure 6.1: The Digiclops camera used for triocular video acquisition. 50 Input data was acquired using a triocular Digiclops camera from Point Grey Research, shown in Figure 6.1. Images were captured at a resolution of 1024 x 768 and a rate of 10 Hz. The Triclops SDK was used to create a disparity map using a Sum of Absolute Differences (SAD) correlation method, and conservative settings yielded a sparse but reliable disparity map. The stereo mask was kept to a small 7x7 window to limit foreground fattening. A mask image of the cloth was constructed by thresholding and combining the intensity and disparity images. The reference image was acquired using a flatbed scanner and image stitching tools, and was scaled down to a resolution of 992 x 1024. The feature detector found 21000 features in the reference image, and an additional 43 000 features in the oblique views of the reference image. The captured images yielded 4200-6400 features, with the number of features typically directly proportional to the visible cloth area. Feature vectors of 128 dimensions were used, but smaller sizes would also likely be suitable. The seed-and-grow algorithm accepted matches for 50-60% of the captured features. Stretch and compression of up to 10% was permitted. This margin allowed for error in our approximation of geodesic distance, g(c ,c ), s n and permitted some diagonal stretch (i.e., shear) in the cloth, but was still sufficient to perform quality matching. In the main dataset, the first ten seeds were typically sufficient to classify over 50% of F , and the first 80% of F was usually classified using the first thirty c c seeds. This process was fairly quick and efficient, and yielded a good dense map of features in the fiat regions of the cloth. Classification of the final 20% of F , however, was much slower. These feac tures were typically near folds or poorly illuminated regions of the cloth, and little growth was possible. Consequently, many of these features had to be matched with a slow brute force algorithm, and many were later rejected by the verification algorithm. Nevertheless, a few good matches were made, justifying the continued 51 search. We found that the oblique reference views for the SIFT algorithm were definitely valuable for the matching process. Of the matched captured features, over half were matched with reference features from oblique views. Some extremely oblique views were also attempted, scaling the reference image by a factor of four. These views gave very small improvements, usually amounting to less than 5% of all matches, and we therefore chose not to use them. The verification algorithm was fairly conservative in its acceptance of features, rejecting over 40% of the matched features. Table 6.1 shows the number of accepted features after feature detection, matching, and verification. As can be seen, only 46% of the detected features were accepted. Despite using a conservative verification, it was still possible to track roughly an order of magnitude more features than would be feasible with traditional motion capture or using Guskov's method. [44, 46, 45] Frame 1 6 11 16 20 Average Visible area 271k 271k 241k 207k 190k 236k Initial features 6464 6458 5710 4731 4249 5567 Matched features 4978 4966 4349 3558 3233 4408 Verified features 2980 2948 2481 2064 1861 2578 Table 6.1: Number of features found, matched, and verified for selected frames. The performance of the system is shown in Table 6.2. Matching was clearly a bottleneck in the system, and the seeding process was the slowest part of matching. The speed of matching on each frame was highly dependent on the initial success of the growth algorithm. Our final results after parameterisation are shown in Figure 6.2. A checkered texture is used to illustrate the parameterisation of the surface, but clearly any texture could be applied. 52 Frame 1 6 11 16 20 Average Hole filling, smoothing 3:15 2:53 2:34 2:47 2:17 2:46 Feature detection 0:14 0:15 0:14 0:14 0:16 0:15 Matching 2:15 2:18 2:03 1:41 1:27 1:57 Verification & parameterisation 0:36 0:42 0:33 0:28 0:25 0:34 Table 6.2: Performance of our system in selected frames, measured in seconds on a Pentium IV 1.8GHz system. Capture of fast-moving cloth was practical using this system. Figure 6.3 demonstrates one example, where the top left corner of the cloth fell and pivoted about the fixed corner in the top right. This image was taken at the start of the fall, where the left side of the cloth is moving quickly while the right side stays still. Motion blur is evident in the fast-moving left side. As can be seen, capture and parameterisation were successful in both the slow-moving and fast-moving sections of the cloth. SIFT features are scale-invariant, and consequently large features could still be found in the presence of motion blur. We are unaware of any other tracking technology that could achieve similar results. 53 Figure 6.2: Top row: input images, frames 6,11,16. Middle row: parameterised geometry with checkered texture. Bottom row: comparison of matched and verified feature density in 1Z r>4 Figure 6.3: Left: captured image of fast moving cloth. Right: parameterised geom etry. Left inset is moving quickly while right inset is still. 55 Chapter 7 Conclusions In this thesis, we have studied various aspects of cloth simulation parameters, focusing on a novel method for capturing the motion of cloth. Additionally, our experiments in Chapter 3 demonstrated the influence of the parameters of one cloth simulator, and also highlighted the damping effects of large timesteps. Our cloth capture method is based on a multi-baseline stereo algorithm to capture partial geometry, and the SIFT feature detection algorithm for recovering the parameterisation on that geometry. We employ smoothing and interpolation to fill holes in the geometry due to occlusion or lack of texture, but emphasise that a more sophisticated stereo algorithm could easily be substituted to eliminate these problems. We have presented a novel seed-and-grow algorithm for recovering the parameterisation of cloth surfaces. One of the advantages of our approach is that we can track features even if they move rapidly and are therefore blurred in the frames of the animation. None of the previous work is capable of dealing with situations like this. This success is made possible by using the SIFT approach (which works for blurred features due to its multi-resolution character), and by not relying on temporal coherence between frames (i.e. by solving the recognition tracking rather than the problem). On the down side, by not making use of frame-to-frame coher- 56 ence, we risk having cloth animations that are not as stable as they could be. In the future, we would like to apply temporal filtering to the feature positions to improve frame-to-frame coherence. This would still allow tracking of fast moving parts of the cloth, but would also stabilise slow moving and static parts, and could be achieved through a more sophisticated verification algorithm using simulated annealing. In our specific implementation, we have used a single trinocular vision system for the geometry recovery. This limits our field of view so that we can only recover single-sided cloth such as towels, curtains, and similar objects. However, it is important to note that our method will extend to calibrated camera systems with any number of cameras. Systems with many synchronised and calibrated cameras are already quite common for traditional motion capture. In our setting, they should allow us to capture objects such as clothing. Even with multiple cameras, however, there will always be regions where folds occlude sections of the cloth. The parametric information found by our algorithm could be used to estimate the area of the occluded region and hence to infer the probable geometry in occluded regions. We leave this as future work. The use of a passive algorithm such as multi-baseline stereo has the advantage that colour and possibly reflectance can be acquired at the same time as the geometry and parameterisation. Our feature detection complements the stereo geometry acquisition, as both systems benefit from a richly detailed pattern printed on the cloth. In order to preserve the possibility for colour and reflectance capture, the pattern (and hence the stereo acquisition) could be restricted to a frequency outside the visible spectrum. For example, we could print the patterns with a paint that only changes infrared reflectance. The stereo cameras would then have to operate in the infrared spectrum, similar to the setup in Light Stage 2 [31]. Finally, the captured cloth geometry and parameterisation could be used to solve the problem of cloth parameter recovery, improving the results obtained by Bhat et al. [11] 57 The premise of cloth parameter recovery is that a single set of parameters can be inferred from a series of experiments with a given cloth material, and then retargetted to novel cloth motion to imitate the material's behaviour. However, this premise may not be valid. As our experiments demonstrated, cloth behaviour in Baraff and Witkin's simulator is highly dependent on the choice of timestep, with large timesteps causing a strong damping effect on cloth motion. This makes the recovery of damping parameters ill-posed, since a given set of recovered damping parameters cannot necessarily be retargetted to yield similar motion. Instead, retargeting will produce variable amounts of damping proportional to the timestep, a parameter which cannot be recovered. Further study of this problem is necessary, including experiments with other cloth simulators. Once damping in cloth simulation models is sufficiently well understood, the cloth motion capture algorithm presented here should be a useful tool for recovering cloth simulation parameters. This area appears to be a fruitful direction for future research. 58 Bibliography [1] M . Aono. Computer-aided geometric design for forming woven cloth ites. PhD thesis, Rensselaer Polytechnic Institute, 1994. compos- [2] M . Aono, D. Breen, and M . Wozny. Fitting a woven cloth model to a curved surface: mapping algorithms. Computer-Aided Design, 26(4):278-292, April 1994. [3] M . Aono, P. Denti, D. Breen, and M . Wozny. Fitting a woven cloth model to a curved surface: dart insertion. IEEE Computer Graphics and Applications, 16(5):60-70, September 1996. [4] U . Ascher and E . Boxerman. On the modified conjugate gradient method in cloth simulation. The Visual Computer (to appear), 2003. [5] J . Ascough, H . Bez, and A . Bricis. A simple beam element, large displacement model for the finite element simulation of cloth drape. Journal of the Textile Institute, 87(1):152-165, 1996. [6] D. Baraff and A . Witkin. Large steps in cloth simulation. In Proceedings ACM SIGGRAPH 98, pages 43-54. A C M Press, 1998. [7] D. Baraff and A . Witkin. Cloth Modeling and Animation, dynamic simulation, pages 145-173. A . K . Peters, 2000. of chapter 6, Rapid [8] D. Baraff, A . Witkin, and M . Kass. Untangling cloth. ACM Transactions Graphics (ACM SIGGRAPH 2003), 22(3):862-870, July 2003. on [9] J . Beis and D. Lowe. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR 1997), pages 1000-1006. I E E E Computer Society, 1997. [10] M . Bertalmio, G . Sapiro, V . Caselles, and C. Ballester. Image inpainting. In Proceedings of ACM SIGGRAPH 2000, pages 417-424. A C M Press, 2000. 59 [11] K . Bhat, C. Twigg, J . Hodgins, P. Khosla, Z. Popovic, and S. Seitz. Estimating cloth simulation parameters from video. In Proceedings of ACM SIG'GRAPH/'Eurographics Symposium on Computer Animation (SCA 2003), pages 37-51. A C M Press, 2003. [12] M . Black, G. Sapiro, D. Marimont, and D. Heeger. Robust anisotropic diffusion. IEEE Transactions on Image Processing, 7(3):421-432, March 1998. [13] D. Breen. A particle-based cloth. model for simulating the draping behavior of woven PhD thesis, Rensselaer Polytechnic Institute, 1993. [14] D. Breen. Cloth Modeling and Animation, chapter 2, A survey of cloth modeling methods, pages 19-53. A . K . Peters, 2000. [15] D. Breen, D. House, and P. Getto. A physically-based particle model of woven cloth. The Visual Computer, 8(5-6):264-277, June 1992. [16] D. Breen, D. House, and M . Wozny. A particle-based model for simulating the draping behavior of woven cloth. Textile Research Journal, 64(ll):663-685, 1994. [17] D. Breen, D. House, and M . Wozny. Predicting the drape of woven cloth using interacting particles. In Proceedings of ACM SIGGRAPH 94, pages 365-372. A C M Press, 1994. [18] R. Bridson. Computational University, 2003. aspects of dynamic surfaces. PhD thesis, Stanford [19] R. Bridson, R. Fedkiw, and J . Anderson. Robust treatment of collisions, contact and friction for cloth animation. ACM Transactions on Graphics (ACM SIGGRAPH 2002), 21(3):594-603, July 2002. [20] R. Bridson, S. Marino, and R. Fedkiw. Simulation of clothing with folds and wrinkles. In Proceedings Computer Animation of ACM SIGGRAPH/Eurographics (SCA 2003), Symposium on pages 28-36. A C M Press, 2003. [21] M . Brown and D. Lowe. Invariant features from interest point groups. In Proceedings of British Machine Vision Conference (BMVC 2002), pages 253262, 2002. [22] M . Brown and D. Lowe. Recognising panoramas. In Proceedings of IEEE International Conference on Computer Vision (to appear). I E E E Computer Society, 2003. 60 [23] R. Carceroni. Recovering multi-view image non-rigid sequence: 3D motion, shape, a differential-geometric and reflectance approach. from PhD thesis, University of Rochester, 2001. [24] R. Carceroni and K . Kutulakos. Multi-view scene capture by surfel sampling: from video streams to non-rigid 3D motion, shape and reflectance. In Proceedings of IEEE International Conference on Computer Vision (ICCV 2001), volume 2, pages 60-67. I E E E Computer Society, 2001. [25] M . Carignan, Y . Yang, N . Magnenat-Thalmann, and D. Thalmann. Dressing animated synthetic actors with complex deformable clothes. In Computer Graphics (Proceedings of ACM SIGGRAPH 92), pages 99-104. A C M Press, 1992. [26] V . Caselles, J . - M . Morel, and C. Sbert. A n axiomatic approach to image interpolation. IEEE Transactions on Image Processing, 7(3):376-386, March 1998. [27] K . - J . Choi and H.-S. Ko. Stable but responsive cloth. ACM Transactions Graphics (ACM SIGGRAPH 2002), 21(3):604-611, July 2002. on [28] K . - J . Choi and H.-S. Ko. Extending the immediate buckling model to triangular meshes for simulating complex clothes. In Eurographics 2003 Short Presentations, pages 187-191, 2003. [29] T. Coleman and Y . L i . A reflective Newton method for minimizing a quadratic function subject to bounds on some of the variables. SIAM Journal on Optimization, 6(4): 1040-1058, 1996. [30] F. Cordier and N . Magnenat-Thalmann. Real-time animation of dressed virtual humans. Computer Graphics Forum (Eurographics 2002), 21(3):327-336, September 2002. [31] P. Debevec, A . Wenger, C. Tchou, A . Gardner, J . Waese, and T. Hawkins. A lighting reproduction approach to live-action compositing. ACM Transactions on Graphics (ACM SIGGRAPH 2002), 21(3):547-556, July 2002. [32] M . Desbrun, M . Meyer, and A . Barr. Cloth Modeling and Animation, chapter 9, Interactive animation of cloth-like objects in virtual reality, pages 219-239. A . K . Peters, 2000. [33] M . Desbrun, P. Schroder, and A . Barr. Interactive animation of structured deformable objects. In Proceedings of Graphics Interface (GI 1999), pages 1-8. Canadian Computer-Human Communications Society, 1999. 61 [34] R. DeVaul. Cloth dynamics simulation. Master's thesis, Texas A & M University, 1997. [35] B . Eberhardt, O. Etzmufi, and M . Hauth. Implicit-explicit schemes for fast animation with particle systems. In Proceedings of the Eurographics Workshop on Computer Animation and Simulation 2000 (CAS 2000). Springer-Verlag, 2000. [36] B . Eberhardt, M . Meifiner, and W. Strafier. Cloth Modeling chapter 5, Knit fabrics, pages 123-144. A . K . Peters, 2000. and Animation, [37] B . Eberhardt, A . Weber, and W. Strafier. A fast, flexible, particle-system model for cloth draping. IEEE Computer Graphics and Applications, 16(5):5259, September 1996. [38] J. Eischen and R. Bigliani. Cloth Modeling and Animation, chapter 4, Continuum versus particle representations, pages 79-122. A . K . Peters, 2000. [39] J. Eischen, S. Deng, and T. Clapp. Finite-element modeling and control of flexible fabric parts. IEEE Computer Graphics and Applications, 16(5):71-80, September 1996. [40] O. EtzmuB, J . Grofi, and W . Strafier. Deriving a particle system from continuum mechanics for the animation of deformable objects. IEEE Transactions on Visualization and Computer Graphics, 9(4):538-550, October 2003. [41] O. EtzmuB, M . Hauth, M . Keckeisen, S. Kimmerle, J . Mezger, and M . Wacker. A cloth modelling system for animated characters. In Proceedings of Graphiktag 2001. Wilhelm-Schickard-Institut fiir Informatik, Graphisch-Interaktive Systeme, Universitat Tubingen, 2001. [42] C. Feynman. Modeling the appearance of cloth. Master's thesis, Massachusetts Institute of Technology, 1986. [43] A . Fuhrmann, C. Grofi, and V. Luckas. Interactive animation of cloth including self collision detection. In Proceedings of Winter School of Computer Graphics (WSCG 2003), pages 203-208, 2003. [44] I. Guskov. Efficient tracking of regular patterns on non-rigid geometry. In Proceedings of IEEE International Conference on Pattern Recognition volume 2, pages 1057-1060. I E E E Computer Society, 2002. 62 (ICPR), [45] I. Guskov, S. Klibanov, and B . Bryant. Trackable surfaces. In Proceedings ACM 2003), SIGGRAPH/Eurographics Symposium on Computer Animation of (SCA pages 251-257. A C M Press, 2003. [46] I. Guskov and L. Zhukov. Direct pattern tracking on flexible geometry. In Proceedings of Winter School of Computer Graphics (WSCG 2002), pages 203-208, 2002. [47] S. Hadap, E. Bangerter, P. Volino, and N . Magnenat-Thalmann. Animating wrinkles on clothes. In Proceedings of IEEE Visualization 1999, pages 175182. I E E E Computer Society, 1999. [48] J. Haddon and D. Forsyth. Shading primitives: finding folds and shallow grooves. In Proceedings of IEEE International Conference on Computer Vision (ICCV 1998), pages 236-241. I E E E Computer Society, 1998. [49] M . Hauth and O. Etzmufi. A high performance solver for the animation of deformable objects using advanced numerical methods. Computer Graphics Forum (Eurographics 2001), 20(3):319-328, September 2001. [50] M . Hauth, O. Etzmufi, and W . Strafier. Numerical methods for deformable models. Technical Report WSI-2001-7, Eberhardt-Karls-Universitat Tubingen, August 2001. [51] M . Hauth, O. Etzmufi, and W. Strafier. Analysis of numerical methods for the simulation of deformable models. The Visual Computer (to appear), 2003. [52] D. House and D. Breen, editors. Cloth Modeling 2000. and Animation. A . K . Peters, [53] D. House and D. Breen. Cloth Modeling and Animation, chapter 3, Particle representation of woven fabrics, pages 55-78. A . K . Peters, 2000. [54] D. House, R. DeVaul, and D. Breen. Towards simulating cloth dynamics using interacting particles. International Journal of Clothing Science and Technology, 8(3):75-94, 1996. [55] S. Huh, D. Metaxas, and N . Badler. Collision resolutions in cloth simulation. In Proceedings of Computer Animation 2001, pages 122-127. I E E E Computer Society, 2001. [56] D. Hutchinson, M . Preston, and T. Hewitt. Adaptive refinement mass/spring simulations. In Proceedings of the Eurographics Workshop 63 for on Computer Animation and Simulation (CAS 1996), pages 31-45. Springer- Verlag, 1996. [57] N . Jojic. Computer modeling, analysis and synthesis of dressed humans. Master's thesis, University of Illinois at Urbana-Champaign, 1997. [58] N . Jojic, J. Gu, H . Shen, and T. Huang. Computer modeling, analysis and synthesis of dressed humans. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR 1998), pages 528-534. I E E E Computer Society, 1998. [59] N . Jojic and T. Huang. Estimating cloth draping parameters from range data. In Proceedings of International and 3-D Imaging, Workshop on Synthetic-Natural Hybrid Coding pages 73-76, 1997. [60] N . Jojic and T. Huang. On analysis of cloth drape range data. In Proceedings of Asian Conference on Computer Vision, pages 463-470. Springer-Verlag, 1998. [61] Y . - M . Kang and H.-G. Cho. Bilayered approximate integration for rapid and plausible animation of virtual cloth with realistic wrinkles. In Proceedings of Computer Animation, pages 203-214. I E E E Computer Society, 2002. [62] Y . - M . Kang and H.-G. Cho. Complex deformable objects in virtual reality. In Proceedings of the A CM Symposium nology 2002), (VRST on Virtual Reality Software and Tech- pages 49-56. A C M Press, 2002. [63] Y . - M . Kang, J.-H. Choi, H.-G. Cho, and D.-H. Lee. A n efficient animation of wrinkled cloth with approximate implicit integration. The Visual Computer, 17(3):147-157, May 2001. [64] Y . - M . Kang, J.-H. Choi, H.-G. Cho, D.-H. Lee, and C.-J. Park. Real-time animation technique for flexible and thin objects. In Proceedings of the Winter School of Computer Graphics (WSCG 2000), pages 322-329, 2000. [65] Y . - M . Kang, J.-H. Choi, H.-G. Cho, and C.-J. Park. A fast and stable cloth animation with approximation of implicit method. In Proceedings of Computer Graphics International (CGI 2000), pages 257-255. I E E E Computer Society, 2000. [66] S. Kawabata. The standardization and analysis Machinery Society of Japan, 1980. 64 of hand evaluation. The Textile [67] R. Lario, C. Garcia, M . Prieto, and F. Tirado. Rapid parallelization of a multilevel cloth simulator using OpenMP. In Proceedings of European Workshop on OpenMP (EWOMP 2001), 2001. [68] R. Lario, C. Garcia, M . Prieto, and F. Tirado. A parallel cloth simulator using multilevel algorithms. In Proceedings of the International Parallel and Distributed Processing Symposium, pages 403-408. I E E E Computer Society, 2002. [69] B . Levy and J.-L. Mallet. Non-distorted texture mapping for sheared triangulated meshes. In Proceedings of ACM SIGGRAPH 98, pages 343-352. A C M Press, 1998. [70] L . L i . Modeling and computer animation of cloth motion in air flow. PhD thesis, Nanyang Technological University, 1994. [71] L . L i . Cloth Modeling and Animation, 175-195. A . K . Peters, 2000. chapter 7, Aerodynamics effects, pages [72] L . L i , M . Damodaran, and R. Gay. A quasi-steady force model for animating cloth motion. In Proceedings of the International Conference on Computer Graphics (ICCG 1993), pages 357-364. North-Holland, 1993. [73] L . L i , M . Damodaran, and R. Gay. Aerodynamic force models for animating cloth motion in air flow. The Visual Computer, 12(2):84-104, February 1996. [74] L . L i , D. Murali, and R. Gay. A model for animating cloth motion. and Graphics, 20(1):137-156, January 1996. Computers [75] J. Louchet, X . Provot, and D. Crochemore. Evolutionary identification of cloth animation models. In Proceedings of the Eurographics Workshop on Computer Animation and Simulation (CAS 1995), pages 44-54. Springer-Verlag, Sep 1995. [76] D. Lowe. Object recognition from local scale-invariant features. In of IEEE International Conference on Computer Vision (ICCV Proceedings 1999), pages 1150-1157. I E E E Computer Society, 1999. [77] D. Lowe. Distinctive image features from scale-invariant keypoints. tional Journal of Computer Vision (submitted), 2003. Interna- [78] M . Meyer, G . Debunne, M . Desbrun, and A . Barr. Interactive animation of cloth-like objects in virtual reality. Journal of Visualization and Computer Animation, 12(1):1-12, February 2001. 65 \ I [79] J. Mezger, S. Kimmerle, and O. EtzmuB. Improved collision detection and response techniques for cloth animation. Technical Report WSI-2002-5, Universitat Tubingen, August 2002. [80] J. Mezger, S. Kimmerle, and O. EtzmuB. Progress in collision detection and response techniques for cloth animation. In Proceedings of 10th Pacific Conference on Computer Graphics and Applications (PG 2002), pages 444-445. I E E E Computer Society, 2002. [81] J. Mezger, S. Kimmerle, and O. EtzmuB. Hierarchical techniques in collision detection for cloth animation. In Proceedings of Winter School of Computer Graphics (WSCG 2003), pages 322-329, 2003. [82] H . Ng and R. Grimsdale. Computer graphics techniques for modeling cloth. IEEE Computer Graphics and Applications, 16(5):28-41, September 1996. [83] S. Osher and R. Fedkiw. Level Set Methods Springer Verlag, 2002. and Dynamic Implicit Surfaces. [84] D. Papadimitriou and T. Dennis. Epipolar line estimation and rectification for stereo image pairs. IEEE Transactions on Image Processing, 5(4):672-676, April 1996. [85] D. Parks and D. Forsyth. Improved integration for cloth simulation. In Eurographics 2002 Short Presentations, 2002. [86] P. Perez, M . Gangnet, and A . Blake. Poisson image editing. ACM Transactions on Graphics (ACM SIGGRAPH 2003), 22(3):313-318, July 2003. [87] W . Press, S. Teukolsky, W. Vetterling, and B . Flannery. Numerical in C. Cambridge University Press, 2nd edition, 1999. [88] D. Pritchard and W. Heidrich. Cloth motion capture. Computer Forum (Eurographics 2003), 22(3):263-271, September 2003. Recipes Graphics [89] X . Provot. Deformation constraints in a mass-spring model to describe rigid cloth behavior. In Proceedings of Graphics Interface (GI1995), pages 147-154. Canadian Computer-Human Communications Society, 1995. [90] X . Provot. Animation 5, 1997. realiste de vetements. 66 PhD thesis, Universite de Paris [91] X . Provot. Collision mid self-collision handling in cloth model dedicated to design garments. In Proceedings Animation and Simulation of the Eurographics 1997 (CAS 1997). Workshop on Computer pages 177 189. Springer-Verlag, 1997. [92] S. Romero, L. Romero, and E. Zapata. Approaching real-time cloth simulation using parallelism. In Proceedings Computation, Applied Mathematics of 16th IMACS World and Simulation, Congress on Scientific pages 220-227. Rutgers University, 2000. [93] S. Romero, L. Romero, and E. Zapata. Fast cloth simulation with parallel computers. In Proceedings of 6th, International Euro-Par Conference, pages 491-499. Springer-Verlag, 2000. [94] S. Romero, L . Romero, and E. Zapata. Parallel algorithm for fast cloth simulation. In Proceedings of /jl.h. international Conference on Vector and Parallel Processing (VECPAR 2000), pages 529 535. Springer-Verlag, 2000. [95] M . Ruiz and B. Buxton. A model-based procedure for fitting a surface to scans of clothed people. In Proceedings and Human Modeling), [96] G . Sapiro. Geometric of Scanning 2001 (Num.erisation 3D 2001. Partial Differential Equations and Image Analysis. Cam- bridge University Press, 2001. [97] D. Scharstein and R. Szcliski. A taxonomy and evaluation of dense two- frame stereo correspondence algorithms. Technical Report MSR-TR-2001-81, Microsoft Research, 2002. [98] D. Scharstein and R. Szcliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. International Journal of Computer Vision, 47(1 -3):7-42, April-June 2002. [99] D. Scharstein, R. Szeliski, and R. Zabih. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. In Proceedings of IEEE Workshop on Stereo and Multi-Baseline Vision, pages 131-140. I E E E Computer Society, 2001. [100] M . Shiniizu and M . Okutomi. Precise sub-pixel estimation on area-based matching. In Proceedings of IEEE International Conference on Computer Vision (ICCV 2001). volume 1, pages 90 97. I E E E Computer Society, 2001. 07 [101] D. Terzopolous and K . Fleischer. Deformable models. The Visual 4(6):306-331, December 1988. Computer, [102] D. Terzopolous, J. Plait,, A. Barr, and K . Fleischer. Elastically deformable models. In Computer Graphics (Proceedings of ACM SIGGRAPH 87), pages 205-214. A C M Press, July 1987. [103] L. Torresani, D. Yang, E. Alexander, and C. Breglor. Tracking and modeling non-rigid objects with rank constraints. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2001), volume 1, pages 493-500. I E E E Computer Society, 2001. [104] A . van Gclder. Approximate simulation of elastic membranes by triangulated spring meshes. Journal of Graphics Tools, 3(2):21-41, October 1998. [105] A . van Gelder and J. Wilhelms. Simulation of elastic membranes with triangulated spring meshes. Technical Report UCSC-CRL-97-12, University of California Santa Cruz, July 1997. [106] J. Villard and H . Borouchaki. Adaptive meshing for cloth animation. In Proceedings of the 11th International Meshing Roundtable (IMR 2002), pages 243 252. Sandia National Laboratories, 2002. [107] P. Volino, M . Courchesne, and N. Magnenat-Thalniann. Versatile and efficient techniques for simulating cloth and other deformable objects. In Proceedings of ACM SIGGRAPH 95, pages 137-111. A C M Press, 1995. [108] P. Volino and N . Magnenat-Thalniann. Developing simulation techniques for an interactive clothing system. In Proceedings of International Conference on Virtual Systems and Multimedia, pages 109-118. I E E E Computer Society, 1997. [109] P. Volino and N . Magnenat-Thalniann. Implementing fast cloth simulation with collision response. In Proceedings of Computer Graphics International 2000 (CGI 2000), pages 257 268. IEEE Computer Society, 2000. [110] P. Volino and N . Magnenat-Tlialinann. Comparing efficiency of integration methods for cloth simulation. In Proceedings of Computer Graphics International 2001 (CGI 2001), pages 265-274. I E E E Computer Society, 2001. [Ill] P. Volino, N . Magnenat-Thalniann, S. Jianhua, and D. Thalmann. A n evolving system for simulating clothes on virtual actors. IEEE Computer Graphics and Applications, 16(5):42-51, September 1996. 68 [112] V . Volkov and L . L i . Adaptive local refinement and simplification of cloth meshes. In Proceedings Technology of the First and Applications International (ICITA 2002), Conference on Information 2002. [113] Y.-Q. X u , C. Cheng, J. Shi, and H.-Y. Shum. Physically based real-time animation of curtains. Technical Report MSR-TR-2000-34, Microsoft Research, April 2000. [114] L . You, J . Zhang, and P. Comninos. Cloth deformation modelling using a plate bending model. In Proceedings of Winter School of Computer Graphics (WSCG 1999), pages 485-491, 1999. [115] F. Zara, F. Faure, and J . - M . Vincent. Physical cloth simulation on a P C on Parallel Graphics [116] D. Zhang and M . Yuen. Cloth simulation using multilevel meshes. & Graphics, 25(3):383-389, June 2001. Computers cluster. and In Proceedings Visualization, of 4th Eurographics Workshop pages 105-112. A C M Press, 2002. [117] Y . Zhao, T. Wong, S. Tan, and W. Chen. A model for simulating flexible surfaces of cloth objects. Computers and Structures, 63(1):133-147, April 1997. 69
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Cloth parameters and motion capture
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Cloth parameters and motion capture Pritchard, David 2003
pdf
Page Metadata
Item Metadata
Title | Cloth parameters and motion capture |
Creator |
Pritchard, David |
Date Issued | 2003 |
Description | Recent years have seen an increased interest in cloth simulation. There has been little analysis, however, of the parameters controlling simulation behaviour. In this thesis, we present two primary contributions. First, we discuss a series of experiments investigating the influence of the parameters of a popular cloth simulation algorithm. Second, we present a system for motion capture of deformable surfaces, most notably moving cloth, including both geometry and parameterisation. This data could subsequently be used for the recovery of cloth simulator parameters. In our motion capture system, we recover geometry using stereo correspondence, and use the Scale Invariant Feature Transform (SIFT) to identify an arbitrary pattern printed on the cloth, even in the presence of fast motion. We describe a novel seedand- grow approach to adapt the SIFT algorithm to deformable geometry. Finally, we interpolate feature points to parameterise the complete geometry. |
Extent | 3081560 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-10-31 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0051622 |
URI | http://hdl.handle.net/2429/14517 |
Degree |
Master of Science - MSc |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2003-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_2003-0562.pdf [ 2.94MB ]
- Metadata
- JSON: 831-1.0051622.json
- JSON-LD: 831-1.0051622-ld.json
- RDF/XML (Pretty): 831-1.0051622-rdf.xml
- RDF/JSON: 831-1.0051622-rdf.json
- Turtle: 831-1.0051622-turtle.txt
- N-Triples: 831-1.0051622-rdf-ntriples.txt
- Original Record: 831-1.0051622-source.json
- Full Text
- 831-1.0051622-fulltext.txt
- Citation
- 831-1.0051622.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051622/manifest