Techniques*for*analysis*and*visualiza4on*of*large‐scale*LIDAR*scan*data*of*urban*environments*Dr.*Patrick*Flynn*and*Alexandri*Zavodny*fl[email protected]*and*[email protected]**University*of*Notre*Dame*This%research%sponsored%by%a%gi1%from%the%NAVTEQ%Corpora;on.%%Introduc4on*• What*is*LIDAR?*Acquisi4on*System*• Typically*aMach*mul4ple*scanners*to*cover*a*larger*range*• Track*vehicle’s****loca4on*with*GPS****and*IMUs*• Obtain*color*with**mul4ple*mounted**cameras*Data*Fusion*Raw*Scanner*Data*Vehicle*GPS*Trace*Vehicle*IMU*Log*Fusion*Points*as*(la4tude,*longitude,*eleva4on,*color)*Color*Camera*Imagery*Data*Acquisi4on*• Different*scanners*provide*very*different*data:*Acquisi4on*Details*• SICK*scanners:*– High*precision*(10mm)*– Low*density*(27,000*points/sec*max.*per*scanner)*– Total*campus:*95,809,671*points*(from*all*3)*• Velodyne*scanner:*– Lower*precision*(2cm*)*– Very*high*density*(1.5*million*points/sec)*– Total*campus:*3,157,484,707*points*Region*Extrac4on*• Want*to*iden4fy*underlying*surface*models*from*point*sampling*• Look*for*sets*of*points*that*lie*in*the*same*plane*Region*Extrac4on*–*Related*Work*• Popular*research*topic*for*digital*archaeology[1‐3],*aerial*land*surveys[4‐6],*urban*planning*applica4ons,*and*more[7,8].*• However,*most*papers*rely*on*structured%scan*data*– Sta4onary*plalorms[3,4,7]*and*single‐laser*mobile*plalorms[9]*can*exploit*structure*Planar*Region*Extrac4on*• We*u4lize*a*region‐growing)approach*• Our*approach*consists*of*4*main*steps:*– Computa4on*of*‘planarity*measures’*– Region*growing*– Region*combina4on*– Region*pruning*Planar*Region*Extrac4on:**Planarity*Measures*• For*speed*and*accuracy,*only*grow*regions*from*points*with*planar*neighborhoods*• Establish*‘planarity*measures’*for*each*point*in*two*passes:*• Pass*1:*– Compute*surface*normal*approxima4on***********for*each*point*€ NiPlanar*Region*Extrac4on:**Planarity*Measures*• Pass*2:*– Compute*the*variance*of*normals*within*the*neighborhood*€ PM(Ps) =∠(Navg, Nii|N |∑)2NPlanar*Region*Extrac4on:**Region*Growing*• Given*a*seed*point******,*fit*a*plane*to*the*point’s*neighborhood*• Itera4vely,*add*points*near*the*edge*of*the*region*that*fit*this*planar*equa4on*• Re‐fit*plane*and*re‐evaluate*membership,*but*only*allow*plane*normal*to*change*slowly:**€ N =14Nold+34Nnew€ PsPlanar*Region*Extrac4on:**Region*Growing*• Globally:*– Points*are*sorted*based*on*planarity*measure.*– Do:*• A*region*is*grown*from*the*most*planar*point.*• Points*found*in*this*region*are*removed.*– Un4l:*the*next‐best*planarity*measure*is*above*a*threshold.*Planar*Region*Extrac4on:*Region*Combina4on*• Region*growing*will*find*all*globally*planar*regions*(ideally)*• Locally*planar*regions*will*be*fragmented:*Planar*Region*Extrac4on:*Region*Combina4on*• Combine*regions*that:*– Are*close*in*space*– Have*similar*planar*normals*Planar*Region*Extrac4on:*Region*Pruning*• Noise*regions*ooen*are*iden4fied:*• Prune*regions*based*on*average*planarity*measure*of*cons4tuent*points*Paralleliza4on*• Region*combina4on*also*works*for*globally*planar*regions,*if*fragmented*• This*observa4on*allows*us*to*split*the*dataset*into*spa-ally)coherent)pieces*and*process*these*subsets*separately*Results*• We*established*a*hard*accuracy*metric*based*on*a*hand‐created*ground*truth*• Per‐region*metrics:*– Ground*truth*regions*correctly*iden4fied*(match)*– Ground*truth*regions*not*iden4fied*(miss)*– Iden4fied*regions*that*are*not*in*ground*truth*(bogus)*– For*correctly*matched*regions,*the*percentage*of*points*shared*between*the*two*(region*accuracy)*• Per‐point*metrics:*– True/false*posi4ves/nega4ves*for*region*membership*Results*• Conducted*experiments*over*a*variety*of*subsets*with*varying*thresholds*and*neighborhood*defini4ons*for*SICK*data*• Best*parameters*gave,*on*average:*True)Posi-ves)99.63%)True)Nega-ves)87.44%*False)Posi-ves)12.56%*False)Nega-ves)0.37%)Matched)88.62%)Missed)7.23%)Bogus)25.05%*Region)Accuracy)90.36%)Region*Extrac4on*• Ques4ons?*Visualiza4on:*Mesh*Genera4on*• Points*are*just*samples;*what*is*the*underlying*model?*Mesh*Genera4on*–*Related*Work*• Solid*representa4ons*are*preferable*in*many*applica4ons,*including*visualiza4on[1],*object*modeling[7,8],*urban*planning[10],*and*more.*• Most*work*in*the*area*exploits*structure*from*scan*data,*which*is*lost*on*scalable*plalorms.*Mesh*Genera4on*• Our*approach*uses*extracted*regions*as*input:*• And*each*region*can*be*triangulated*in*2D*Mesh*Genera4on*• In*2D,*outline*extrac4on*is*done*via*a*modified*convex*hull*approach*Mesh*Genera4on*• Once*we*have*an*ordered*outline*for*a*region,*we*triangulate*using*an*ear‐cuung*method*[TODO]*Mesh*Genera4on*• Once*we*have*an*ordered*outline*for*a*region,*we*triangulate*using*an*ear‐cuung*method*[TODO]*Mesh*Genera4on*• Once*we*have*an*ordered*outline*for*a*region,*we*triangulate*using*an*ear‐cuung*method*[TODO]*Mesh*Genera4on*• Once*we*have*an*ordered*outline*for*a*region,*we*triangulate*using*an*ear‐cuung*method*[TODO]*Mesh*Genera4on*• Once*we*have*an*ordered*outline*for*a*region,*we*triangulate*using*an*ear‐cuung*method*[TODO]*Mesh*Genera4on:*Single*Region*Points*detected*as*belonging*to*a*single*region*Mesh*Genera4on:*Single*Region*Simplified*outline*aoer*outline*extrac4on*Mesh*Genera4on:*Single*Region*Triangulated*region,*with*texture*generated*from*nearby*points*Mesh*Genera4on:*Single*Region*Textured*triangula4on,*with*wireframe*overlaid*Mesh*Genera4on*• Triangula4ng*regions*independently*causes*boundary*issues:*Mesh*Genera4on*• Global*unifica4on*step*iden4fies*shared*borders*and*corners*among*all*regions*• Uses*these*guidelines*to*snap*outlines*Mesh*Genera4on*• Perform*the*stages*in*this*order:*– Global*edge*unifica4on*– Outline*extrac4on*and*simplifica4on*– Surface*triangula4on*– Texture*genera4on*Mesh*Genera4on*Future*Work*• Improved*mesh*and*texture*genera4on*using*camera*images*instead*of*point*colors*• Improved*region*segmenta4on*using*domain‐specific*knowledge*• Cross‐4me*change*detec4on*using*ex tracted*regions*Thank*you!*• Ques4ons?*•