# Hierarchical Segmentation of Automotive Surfaces and Fast Marching Methods

**View the full content.**View Full Document

0 0 11 views

**Unformatted text preview:**

Hierarchical Segmentation of Automotive Surfaces and Fast Marching Methods Prasad N Atkar David C Conner Aaron Greenfield Howie Choset Alfred A Rizzi BioRobotics Lab Microdynamic Systems Laboratory 1 Automated Trajectory Generation Generate trajectories on curved surfaces for material removal deposition Maximize uniformity Minimize cycle time and material waste Spray Painting Complete Coverage Uniform Coverage Cycle time and Paint waste Programming Time Bone Shaving CNC Milling 2 Challenges Deposition Complex deposition patterns Pattern Spray Gun Warping of the Deposition Pattern Non Euclidean surfaces Target Surface High dimensioned searchspace for optimization 35 08 0 Micr 3 Related Research Index Optimization Simplified surface with simplified deposition patterns Suh et al Sheng et al Sahir and Balkan Asakawa and Takeuchi Speed Optimization Global optimization Antonio and Ramabhadran Kim and Sarma 4 Overview of Our Approach Divide the problem into smaller sub problems Understand the relationships between the parameters and output characteristics Develop rules to reduce problem dimensionality Solve each sub problem independently Dimensionality Reduction Constraints Rule Based Planning Model Based Planning Path Variables Simulation Output System Parameters Output Characteristics 5 Our Approach Decomposition Segment surface into cells Topologically simple monotonic Low surface curvature Generate passes in each cell y t x Select start curve Optimize end effector speed Optimize index width and generate offset curve Repeat offsetting and speed optimization 6 Rules for Trajectory generation Avoid painting holes cycle time paint waste Select passes with minimal geodesic curvature uniformity Minimize number of turns cycle time paint waste 7 Choice of Start Curve Select a geodesic curve Select spatial orientation minimizing number of turns Average Normal Select relative position with respect to boundary minimizing geodesic curvature 8 Effect of Surface Curvature Not a geodesic Offsets of geodesics are not geodesics in general geodesic Geodesic curvature of passes depends on surface curvature Gauss Bonnet Theorem 9 Selecting position of Start Curve Select start curve as a geodesic Gaussian curvature divider 10 Speed and Index Optimization Speed optimization Minimize variation in paint profiles along the direction of passes Index optimization Minimize variation in paint deposition along direction orthogonal to the passes 11 Offset Pass Generation Implementation Marker points Self intersections difficulty Initial front Topological changes Images from http www imm dtu dk mbs downloads levelset040401 pdf Front at a later instance Marker pt soln 12 Level Set Method Sethian Assume each front at is a zero level set of an evolving function of z x t Solve the PDE H J eqn given the initial front x t 0 http www imm dtu dk mbs downloads levelset040401 pdf 13 Fast Marching Method Sethian x t 0 is single valued in t if F preserves sign T x is the time when front crosses x H J Equation reduces to simpler Eikonal equation T 0 given T 3 Using efficient sorting and causality compute T x at all x quickly 14 FMM Similarity with Dijkstra Similar to Dijkstra s algorithm Wavefront expansion O N logN for N grid points Improves accuracy by first order approximation to distance 15 FMM Contd 1 1 Dijkstra FMM First order approximation For 2 D grid In our example 16 FMM on triangulated manifolds Evaluate finite difference on a triangulated domain Basis two linearly independent vectors C 5 2 Front A T A 10 4 5 B T B 8 grad Dijkstra T C min T A 5 T B 5 13 FMM T C 8 4 12 17 Hierarchical Surface Segmentation Segment surface into cells Advantages Improves paint uniformity cycle time and paint waste Requirements Low Geodesic curvature of passes Topological monotonicity of the passes 18 Geometrical Segmentation To improve uniformity of paint deposition Minimize Geodesic curvature of passes Restrict the regions of high Gaussian curvature to boundaries 19 Geometrical Segmentation Watershed Segmentation on RMS curvature of the surface Maxima of RMS sqrt k12 k22 2 Maxima of Gaussian curvature k1k2 http cmm ensmp fr beucher wtshed html Four Steps Minima detection Minima expansion Descent to minima Merging based on Watershed Height 20 Topological Segmentation Improves paint waste and cycle time by avoiding holes Orientation of slices Planar Surfaces cycle time minimizing Extruded Surfaces based on principal curvatures Surfaces with non zero curvature maximally orthogonal section plane Symmetrized Gauss Map Medial Axis 21 Pass Based Segmentation Improves cycle time and paint waste associated with overspray Segment out narrow regions Generate slices at discrete intervals 22 Region Merging Merge Criterion Minimize sum of lengths of boundaries reduce boundary illeffects on uniformity Merge as many cells as possible such that each resultant cell is Geometrically simple Inspect boundaries Topologically monotonic single connected component of the offset curve and spray gun enters and leaves a given cell exactly once Partition directed connectivity graph such that each subgraph is a trail 23 Region Merging Results Segmented Merged Segmented Segmented Merged Merged 24 Summary Rules to reduce dimensionality of the optimal coverage problem Gauss Bonnet theorem to select the start curve Fast marching methods to offset passes Hierarchical Segmentation of Surfaces 25 Future Work Cell Stitching Optimize ordering in which cells are painted Optimize overspray to minimize the cross boundary deposition Optimize end effector velocity 26 Thank You Questions 27