Home

Object reconstruction and 3D mosaicing Outline

1. 15 16 17 18 19 20 21 22 23 24 25 Deliverable 5 1 M Okino Y Higashi Measurement of seabed topography by multibeam sonar using CFFT IEEE J Oceanic Engineering 11 4 474 479 1986 L Henriksen Real time underwater object detection based on an electrically scanned high resolution sonar Proc IEEE Symposium on Autonomous Underwater Vehicle Technology Cambridge 1994 D Sauter L Parson Spatial filtering for speckle reduction contrast enhancement and texture analysis of GLORIA images IEEE J Oceanic Engineering 19 4 563 576 1994 S Z Li Markov Random Field Modeling in Computer Vision Springer Verlag Tokyo 1995 V Murino A Trucco Markov based methodology for the restoration of underwater acoustic images International J of Imaging Systems and Technology 8 4 386 395 1997 Mignotte C Collet P P rez P Bouthemy Markov random field model and fuzzy formalism based data modeling for the sea bed classification in sonar imagery SPIE Conference on Mathematical Modeling Bayesian Estimation and Inverse Problems Colorado 3816 29 229 240 1999 S Dugelay C Graffigne J M Augustin Segmentation of multibeam acoustic imagery in the exploration of the deep sea bottom Proceedings of 13 International Conference on Pattern Recognition Vienna 437 445 1996 V Murino A Trucco Confidence based approach to enhancing underwater acoust
2. The Elaboration Settings are managed by a Settings Dialog which stores the settings into the host machine registry Each time the Data Proc Module 1s started it reads the settings from the registry and applies them See section Settings below In the following we shall review the main features of the Data Proc Module and its usage hints 4 2 MAIN DIALOG The main dialog gathers all the controls and feedback windows necessary for controlling the elaboration of the incoming data BITE Received Data Mosaic Info Save Mesh Acoustic Ne Data Meshes a IER rate Optical Nc Data j Hx Status Not Connected hd osaic Extra Gene Link Status Not connected Reset Reset Settings Gas Oil Leak Detection Reset Ponnecthe Connect Figure 12 data_proc main Dialog Box Mosaic Info this section contains information about the generated mesh The left progress bar indicates the percentage of meshes in the Mosaic buffer The reset button deletes all the meshes from the mosaic and from the Pilot Surveyor visualization module The right progress bar shows the percentage of meshes contained in the Extra Mosaic buffer Department of Computer Science University of Genova WWW disi unige it 35 ARROV Project GRD1 2004 180601 Page 36 of 42 Document ID DISI ARD 012 Deliverable 5 1 The Extra Mosaic meshes are those meshes that are not generated by the mosaic module but are single frame reconstructed and possib
3. connected components of the mesh built on single frame which have a number of triangles greater or equal than the threshold are considered for further processing e Reliability threshold a positive integer value This 1s used during on line registration It is the minimum number of vertices in the current frame to allow a reliable registration If that number is below the threshold the results of registration are not used in motion tracking and the current mesh is not inegrated in the mosaic e Subsample threshold a positive integer value This 1s used during on line registration It 1s the maximum number of points in the current frame used for registration If the number of vertices in the current frame exceeds the threshold the frame randomly subsampled e Maximum number of ICP iterations a positive integer value This is used during on line registration If the maximum number of iterations is reached the ICP algorithm will stop e Minimum residual registration error RRE a positive real value This is used during on line registration If the minimum residual error is measured the ICP algorithm will stop e Grid resolution a positive real value This is used during mosaicing It defines the edge length of square cells in which 3D space is subdivided In practice t roughly corresponds to the average length of edges of triangles in the resulting triangulation This value is fixed during setup and cannot be changed during a session It
4. only data points having an intensity value equal or greater than the threshold are considered for further processing e Range difference threshold a positive short value This is used during single frame reconstruction Only points having a difference in their range distance smaller or equal than the threshold may be considered adjacent in the mesh This threshold can be calculated automatically based on the distribution of the range difference of all points in the frame e Intensity difference threshold a positive short value This is used during single frame reconstruction Only points having a difference in their intensity smaller or equal than the threshold may be considered adjacent in the mesh This threshold may be calculated automatically based on the distribution of the intensity difference of all points 1n the frame Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 7 of 42 Document ID DISI ARD 012 Deliverable 5 1 e Level of neighbourhood a flag This is used during single frame reconstruction If flag is set triangles are built by considering pairs of points that correspond to array entries at a distance of at most two units in the range map Level 2 otherwise only pairs of points that correspond to array entries at a distance of at most one unit are considered Level 1 e Minimum size of components a positive real value This 1s used during filtering Only
5. pseudo code relative to the computation of step3 in the Single frame Reconstruction procedure 1 3 4 Step 4 Mesh generation The last step of our procedure generates the final triangular mesh by forming faces as cycles of three edges Figure 6 For each location v in the lattice the method scans the portion of adjacency list that has been populated during the three steps above spanned by the first 12 bits of the bit vector encoding it Figure 5 the remaining edges in the list will be considered from other vertices Non vacant entry Adjacency vector Figure 5 the adjacency vector of an entry in the lattice left a 3x3 block for testing for feasible semi diagonals right Lu RSS NS IA SAS O SASS eS SSG ee L i SS en ale veal Fari na nn E Va P PE EC Fd Fa E P a Fd Pa E AVR P e Fa Fa V Va E RTL Ta a a a Pa a E Fa a Va FATA e ELE hA 1 E m L ll EAA PANI rni L gs ie xL LR ara l ity erac CURT e T DIS ial Wad ead ea R Wed a r El F H LA p X pl FIL Gn nma a ed a Pea Ea all EG a FS PLA Le Le Le aera ei FALLS ERR EE tar slt ARAT mi f I M fa i m L Fi ERA MAY lA an m eal T T 5 Ls Figure 6 the result of the application of the SingleFrameReconstruction procedure Department of Computer Science University of Genova WWW disi unige 1it 15 ARROV Project GRD1 2004 180601 Page 14 of 42 Document ID DISI ARD 0
6. 1 r add a non vacant entry if the intensity of the relative vertex is higher than a given threshold IntThres otherwise add a vacant entry NULL LhnodctvO0 wl v2 v3o lLlmutrhres Test vertical adjacencies between non vacant entries f IT their radial distance is less than The input threshold m RadThsE if vl zNULL amp amp v3 NULL amp amp RaDist vl v3 lt m RadThr update the Adjacency Matrix for the output update existence and adjacency fields UpdateAdjacencyMatrix Test vertical adjacencies between non vacant entries I Er Cheir radial distance 19 less ihan the input threshold m Raciir if v2 zNULL amp amp v3 NULL amp amp RaDist v2 v3 lt m RadThr UpdateAdjacencyMatrix Test Diagonal Adjacencies between non vacant entries ascending and descending gt first good is taken Jf 2f their radial distance 25 less Chan The input tbresDolg m Bacch 1f vO0l NULD amp amp v321 NULL RaDist V0 V3 lt m RadThr UpdateAdjacencyMatrix else if vl zNULL amp amp v2 NULL amp amp RaDist vl v2 lt m_ RadThr UpdateAdjacencyMatrix Table 2 pseudo code of the first step in the Single Frame Reconstruction procedure 1 3 2 Step 2 Recovery vacant entries Once all the connections of step 1 from non vacant entries have been discovered the method considers all the entries in the lattice with no 3D point vacant entries as 1n case of a hole 1n the grid de
7. 1s important to trade off between speed and accuracy e Fusion threshold a positive real value This 1s used during mosaicing It defines the minimum distance between two vertices generated by different frames If two such vertices lie along the same grid line and are at a distance smaller than this threshold they are merged This value must be smaller than grid resolution The choice of fusion threshold should also keep into account the RRE It is also possible to automatically set fusion threshold on the basis of the RRE value 1 2 THRESHOLDING Every acoustical 1mage captured by the acoustical camera Echoscope on board ROV has 64x64 points and each point 1s described by four numbers x y z i where z represents the range information and i 1s the intensity of the point A possible way to filter the 3D data 1s to set up a threshold to the intensity of the points and the points with low intensity are filtered Figure 2 This idea is because the echoes backscattered from objects have stronger response than other cluttering interferences Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 8 of 42 Document ID DISI ARD 012 Deliverable 5 1 Acoustic Image Figure 2 initial threshold over intensities Thresholding in ARROV system 1s performed on the raw 3D point intensities among adjancent points During the filtering stage and for each acoustic frame a threshold 1s compu
8. data formats in the registration module double DEFULT 100 e Mesh Face Perimeter Threshold this threshold cut off meshes with high perimeter Used to produce better looking meshes int DEFAULT 300 Department of Computer Science University of Genova WWW disi unige it 40 ARROV Project GRD1 2004 180601 Page 41 of 42 Document ID DISI ARD 012 Deliverable 5 1 e Lazy Update Threshold this threshold tunes the refresh rate of the mosaic double DEFAULT 0 6 RANGE 0 2 4 4 5 Meshing The meshing section controls the setting of the output mesh and the pseudo texturing of the optical images Mesh Colouring Smooth Area Edit Figure 18 Meshing Settings e Mesh Colouring sets the mesh colouring mode the possible values are e fixed each mesh has a single default white colour for improved visualisation e Multi each mesh has a different colour depending on the current frame number e Colour from Images Each vertex is coloured using the information from the Optical image The colour of each face of the mesh is computed by bi linear interpolation of colours at face s vertices e Smooth Area in the case of mesh pseudo texturing the colour of each vertex 1s obtained by computing the mean value in the area around the target point in the image This area is a square whose side is 2 Smooth Area 1 int DEFAULT 1I 1f 0 the target point colour is used e Shading Mode this parameter controls whether
9. from a single range image just acquired by the 3D Echoscope Our input basically consists of Table 1 l a matrix j describing a regular lattice range image whose entries i j describe either a point in space x y z or a vacancy Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 9 of 42 Document ID DISI ARD 012 Deliverable 5 1 2 a connectivity threshold 0 used to evaluate whether or not two nodes in the lattice should be considered adjacent and 3 the lateral resolution of the sensor The output of the method is Table 1 l an adjacency matrix A containing the connection data for each entry in the input frame and 2 a single frame mesh M V F where V is a set of 3D vertices and F is a set of faces The mesh structure contains also additional information such as face and vertex normals INPUT MATRIX Vertex I ADJACENCY MATRIX Vertex A CONNECTIVITY THRESHOLD float t SINGLE FRAME MESH Mesh M LATERAL RESOLUTION double 1 Table 1 Input and output of the Single Frame Reconstruction Procedure The method considers points corresponding to non vacant entries in the lattice and it connects them pairwise to form edges cycles of three edges form triangles of the output mesh A potential edge exists between each pair of points v2 x1 y1 21 and w 2 y2 Z2 1f their radial distance 1s below some threshold 0 depending from the following form
10. registering all spatially overlapping image pairs in addition to those that are adjacent in the frame sequence The main idea is based on the introduction of the constraints arising from the pairwise registration directly on the transformation matrices without the need to go over data points again after the initial pairwise registration between all the overlapping views Global registration needs information on the overlapping between the image pairs in order to select correctly those pairs that can be registered 1 e the images with a sufficient overlapping This information 1s given by the incidence matrix computed in the pre mosaicing phase We now turn our attention to the simultaneous registration of several point sets 2 3 1 1 Chaining pairwise transformations Assume that there are M overlapping point sets or views V V each taken from a different viewpoint The objective is to find the best rigid transformations G G to apply to each set bringing them a common reference frame where they are seamless aligned Let G be the rigid transformation matrix in homogeneous coordinates that registers view j onto view i 1 Department of Computer Science University of Genova WWW disi unige it 28 ARROV Project GRD1 2004 180601 Page 29 of 42 Document ID DISI ARD 012 Deliverable 5 1 yt 173 2 3 1 where the equality holds only for the overlapping portions of the two points sets V and GV If
11. system will have to be regenerated This operation can be expensive if applied to the entire mesh and it could slow down the system Department of Computer Science University of Genova WWW disi unige it 19 ARROV Project GRD1 2004 180601 Page 20 of 42 Document ID DISI ARD 012 Deliverable 5 1 Because of observations above we decided to modify the method of the Marching Intersection Algorithm MIA 24 which exhibits an interesting approach since it allows a valid trade off between speed and accuracy and by the use of quality parameters it takes into account the reliability of input data The original MIA is based on a volumetric approach that locates the geometric intersections between the meshes built on single frames and a virtual 3D reference grid Intersections are first merged and the output mesh 1s found by joining intersection points that belong to edges of the same cell through a scheme defined in a lookup table In order to make it applicable to an on line setting we have modified the algorithm to deal with a pre computed mesh A as explained before which fits the reference grid 1 e it has its vertices on grid edges and each face is completely contained in a grid cell and a new mesh B which intersects the grid properly Furthermore in order to support real time rendering we have developed a lazy update strategy for display lists which reduces the load per frame on the graphics system So the mosaicing algori
12. to update the matrix a list of indices is attached to each vertex of the pre mosaic which contains the indices of all frames that contributed to generate that vertex through successive steps of fusion At each new frame J fusion occurs between one existing vertex of the mosaic which may have a list of one or more indices attached to and one vertex from frame jJ So the list attached to vertex resulting from fusion is obtained by appending index j to the existing list Then the incidence matrix is updated by incrementing all entries of the type j 1 for each I that were present in the list of the vertex that participated 1n fusion At the end of this processing all data from pre mosaicing are discarded while the incidence matrix 1s passed to the next phase 2 3 GLOBAL REGISTRATION Global registration aims at representing all the registered frames with respect to the same reference system A widely used approach such as the method for the on line phase to the registration of many views is to sequentially apply pairwise registration until all the views are combined These scheme do not use all the available information and do not compute the optimal solution because of the accumulation of registration errors Global registration could exploit information present in the unused overlapping view pairs distributing the registration error evenly between every pairwise registration The proposed method for the off line phase consists of locally
13. 12 Deliverable 5 1 For each pair of consecutive edges in the list a triangle of the mesh 1s generated A filter can be also applied based on the perimeters of faces to obtain a smoother distribution of face dimensions and to overcome limitations due to the radial nature of the distance used to test for point connectivity Build Mesh Procedure inte pl p2 p2 77 Pointo iH 7 724 ilhi for 1 071 lt m Width m Helght 2 2513 LE ae Matlin adJ dimim adJ dim l 1 plene Pla Po J UE while j 12 LL ac mar m me camry i Lt Dp eb Oe er paese lela Clam ECHO ue lai iLike x99 else if p3 1 p3 italut j 0 m Widthtalut j 1 to check for p2 p3 adj iTlealut ij3 lr0 akut 32 0 zz25alut 3 l alut 352 Il mL T e psl l amp ve Gd Matlp2Z m ad oinmrtoinvealgtlcbr2 LL52 v2 e91 CFacesa place new Graceodum ArrayVertex GerAri p L m ArrayVertex GetAt p2 m ArrayVertex GetAt p3 double per pface Perimeter 77 falter on face perimeter 1f perm FacePerlhres pMesh gt AddFace prace add face to mesh p2 1 ps 3325 jJ J pMesh gt BuildAdjacency first build adjacency list for each vertex if m bRemoveIsolatedVertices Remove Isolated Vertices for 1 0 1 lt NbVertex 1 CVertex3d vert GetVertex i int size GetArrayFaceNeighbor GetSize if size 0 DeleteVertex i y m bMeshBullt TRUE return 1 Table 5 pseudo code relative to the
14. 16 ARROV Project GRD1 2004 180601 Page 17 of 42 Document ID DISI ARD 012 Deliverable 5 1 corresponding 3D point was discarded Finally the definitive corresponding point of y will be the closest x of the points belonging to the neighborhood V of x If the projection of the point y falls onto an empty area this point remains without correspondence As we pointed out before the main important step 1s the projection of the 3D point onto the range image This process can be carried out by the following equation Y OFF i Jorr f 1 5 2 where Sa and sg are respectively elevation and azimuth increments according to the spherical scanning principle Iorr and Jorr are offsets and finally op are given by l j i F it i retg j Irt E 1 5 3 The parameters So Sg Iorr and Jorr are fixed by the acquisition sensor and they determine the aperture of the acquisition 1 e field of view and resolution By considering the high computational cost of the arctg operator a variation of i and j indices extraction 1s introduced From equation 1 5 3 we easily find that H La d LOO mE Lo 1 5 4 Because the possible angles o and D on the model image are known a priori 1 e according to the spherical scanning principle the values tga and tgp are stored into a table When a 3D point x y z 1s coming from a dataset the values x z and y z are computed and they are successively compared with
15. 1975 R Rivest the optimality of elias s algorithm for performing best match searches 1974 I Pitas C A Kapoutsis C P Vavoulidis Morphological iterative closest point algorithm IEEE Transaction on Image Processing 8 11 1999 C Dorai J Weng and A Jain Optimal registration of object views using range data IEEE Transactions on Pattern Analysis and Machine Intelligence 19 10 1131 1138 1997 G Godin M Greenspan A nearest neighbor method for etcient icp In IEEE Int Conf on 3 D Imaging and Modeling 3DIM 01 Quebec City Canada 2001 G Blais and M D Levine Registering multiview range data to create 3 D computer objects IEEE Transactions on Pattern Analysis and Machine Intelligence 17 8 820 824 1995 Paul J Besl Active optical imaging sensors Machine Vision and Applications pages 127 152 1988 Department of Computer Science University of Genova WWW disi unige it 34 ARROV Project GRD1 2004 180601 Page 35 of 42 Document ID DISI ARD 012 Deliverable 5 1 Appendix 1 Data Proc User Manual 4 1 PURPOSE The Data Proc Module has been developed for real time processing of data from Echoscope sensor and SIT camera thereby producing mesh data for graphics visualization The Data Proc Module receives Acoustical and Optical data from the GRL Data transfer Interface process 1t and sends out meshes to the GRL Pilot or Surveyor Module via the Mesh Transfer Interface provided by GRL
16. 4 0 22 15 UpdateAdjacencyMatrix if done Load v2 vb IntThres if v2 zNULL amp amp v5 NULL amp amp RaDist v2 v5 m RadThr if adj mat i 1 m adj dim 20 0 amp amp T 10 8 adj mat i m Width 2 m adj dim 20 0 16 9 UpdateAdjacencyMatrix jj Table 3 pseudo code relative to the computation of step2 in the Single frame Reconstruction procedure Department of Computer Science University of Genova WWW disi unige 1it l1 ARROV Project GRD1 2004 180601 Page 12 of 42 Document ID DISI ARD 012 Deliverable 5 1 lj Vacant entry _ Adjacent entries Figure 4 3x3 bock testing around a vacant entry left and the result of the application of this procedure step applied to an input range image right The results demonstrated that this step 1s able to fill some holes remained after the application of step _ 1 and to improve the result of the reconstruction Figure 4 Unfortunately too many holes remain in the final mesh and another step is necessary 1 3 3 Step 3 Improve connections find feasible semi diagonals In order to improve the resulting mesh the method tries to find feasible semi diagonal connections For each 3x3 window in the input lattice we check for the possible eight semi diagonal edges among the entries at the boundary of the window Figure 5 right At most two of the feasible semi diagonal edges can coexist and the method searches for them Table 4 Searc
17. ARROV Project GRD1 2004 180601 Page 1 of 42 Document ID DISI ARD 012 Deliverable 5 1 Object reconstruction and 3D mosaicing Author UNIVR U Castellani A Fusiello V Murino DISI L Papaleo E Puppo M Pittore Date Friday 02 July 2004 Outline INTRODUCTION WES OBIEC TIV BS icnessacstuscavessessarsceuccavesaveuasecevssasevescuavssansuasouenssassvansuevsvansecsecassuassesessuassvessvessntsaresssnes 2 1 ONLINE RECONSTRUCTION AND MOSAICING visscsssasiccesccioctencsiassrscsiactesscdusrenessestesseusti ateentiatrwiieesiametiees 3 1 1 AR OUE TURE M E A E 3 A S027 EIEEE AA AA AAE E E E 5 Pe OUI AEEA E EEEE E AEA A 5 LA T E a a E ea E AE EEEE AA 6 1 2 TORES TOL DIN ee E E A 1 3 NOLE E RAME RIEC ONS RUC TION cates eres air cacy E EEA E 8 1 3 1 Step I Find connections for non vacant CNUIICS ccccccccccccccc cece eee ccc e cece eee eee kee eee eke EEE EEA rh nn eese ssi GHEE enses enne s 9 IE V AOC AEn Cl VACANT oz ME O 10 1 3 3 Step 3 Improve connections find feasible semi diagonals ssssssssssssssesessseeseseeee rehenes 12 L34 SY oe Mesheenaral ON ecu tu cub uisum UE AU MM uU EINE MU ee eee ee eee 13 1 4 PIER NO A X 14 1 5 BAS PARE GIS PRON oeir A A A AERA E E 16 LoL REV ISS CG TOPO MON GIFU TRERERRRER RERO 16 Loa oco a E E E E E eee eee ee ee ee 18 DDS POF OCI CIE aer EEE EEEE EEE EEEE E
18. ENE EEE EE EE 18 DD ICCA V5 OCC E 18 1 6 IVI SAIC E E oeeiia 19 1 6 1 Phase I Rasterization and Intersection Management esses hehehe ene snn thee e nsns 21 Ee od 101 ee e E E AE E E E 23 1409 PICS MONTO ON a EE R A ane ae E 24 1 7 BAZY ORDA T E E E 24 1 8 U PREMANTA Eien a usin E E E EE E EE EEE EE EE EEA EE E E E E E E 25 2 OFF LINE DATA PROCESSING wists eptassteesnssatessaventersensstunsenectvysapecivesavestuesavestnesarecivesanestonsaessioveneisncesesisisnasesisveaaests 25 2 1 ACCURATE PUR WISE RE GIST TION coset ses garcons EE E 26 2 2 PREMO AIC NO T 27 29 GLOBAL RT EI IN ATION c 28 3 MULTEREBESOEUTIONAXREPRESENT S TION eien EEEE 90200103 9 1140000 01309003 907990099 1240079 990990 EEVEE EEES 31 4 EEPRERENGCBDS 2299321222991912192 299901219092291009192909091020029800000000 00028 0939000 00 029LLU ess Ua REL LU PRAETOR E EET EEE 32 Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 2 of 42 Document ID DISI ARD 012 Deliverable 5 1 Introduction WP5 Objectives Develop and establish methods for 3D object reconstruction from sensor data acquired at either a single location or multiple locations mosaicing multi resolution representation of reconstructed objects 3D reconstructi
19. aS e AN Sa Se EI SSS Em zug Em TE cm eco en NES SS i T PESE m E E i i 3 E mus NSIS SING ke ess E SS del ON vans ede SPEI SNNT cde Ju ss KENN ASSASINS DSL ESI Vi a SER CRAS NESSES um COO TIKJIKINIS ie BERRA NNESRINNCSSVP NIS Figure 7 Tiling of four meshes with different visualization options from top left to bottom right smooth simple faces wireframe with curvature wireframe and simple faces The single frame reconstruction algorithm has been successfully implemented and tested over echoscope 3D data The results show that a good mesh reconstruction 1s obtained via a local analysis of the spatial properties of the 3D data by exploiting the structure of the echoscope sensor The reconstruction algorithm depends upon two thresholds but not critically The first threshold 1s over the radial distance between 3D points in the lattice and 1s used to evaluate the adjacency relationships among the lattice entries The second threshold is over the intensity of the 3D points As we can remark looking at the next figure the intensity values are unevenly distributed over the 3D points and represent a measure of the reliability of the sensor data itself IN p NM RY WE Department of Computer Science University of Genova WWW disi unige it 15 ARROV Project GRD1 2004 180601 Page 16 of 42 Document ID DISI ARD 012 Deliverable 5 1 If we decide not to rely on the data 1n the reconstruction we c
20. ameters used during processing Note that the complete mosaic built on all meshes received is maintained as a state of the program rather than given in output The GUI allows the user to download the whole mosaic on disk by either interrupting or terminating on line operations Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 4 of 42 Document ID DISI ARD 012 Deliverable 5 1 uput er Preimnn and Orentaan Optical glabal Mesh ASO UEC calkbration data Figure 1 Data Processing Scheme Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 5 of 42 Document ID DISI ARD 012 Deliverable 5 1 1 1 1 Input A frame consists of the following data e Atime stamp in the form of a non negative integer value e Arange map in the form of two bi dimensional arrays of size 64x64 o Each entry in the first array contains a 3D point in the form of three Cartesian coordinates x y z each being a signed integer on 16 bits referring to a right handed coordinate system centered at the sensor with axes oriented as follows e x pointing from the sensor face and out perpendicular to the face of the receiver array e y horizontal pointing to the left when looking in the viewing direction e z vertical pointing upward o Each entry in the second array contains an intensity value in the form of a
21. an rise up the intensity threshold therefore excluding points out of the mesh Particularly 1n this case as showed in the figure below the resulting mesh will be much more noisy but our approach will show an optimal behavior 1n red 1n the figure are sketched the faces obtained from step two and three Therefore it 1s possible to obtain both more reliable and more dense meshes 1 5 FAST REGISTRATION In order to be able to work on line ICP needs to be modified In general the speed enhancement of ICP algorithm can be achieved by 1 reducing the number of iterations necessary to converge and 11 reducing the time spent in each iteration 1 e time spent for the calculation of the correspondences 26 Basically the first and the simplest step 1s to restrict the number of points to be registered which 1s the trade off between the registration speed and the measurement precision However this technique cannot be applied to the registration of the underwater images extremely since the already poor quality of the images A number of classical approaches such as k D tree 27 28 exist for speed up the calculation of the correspondences which has been reputed to account for the bulk of the computational complexity of ICP algorithm Another approach 1s based on the substitution of the point to point distance metric with the point to surface distance which 26 report to yield a faster convergence The acceleration of the extraction o
22. and W A Stahel Robust Statistics the Approach Based on Influence Functions Wiley Series in probability and mathematical statistics John Wiley amp Sons 1986 Lorusso D W Eggert and R B Fisher A comparison of four algorithms for estimating 3 D rigid transformations Machine Vision and Applications 9 272 290 1997 E Trucco A Fusiello and V Roberto Robust motion and correspondence of noisy 3 D point sets with missing data Pattern Recognition Letters 20 9 889 898 September 1999 Greg Turk and Marc Levoy Zippered polygon meshes from range images In Andrew Glassner editor Proceedings of SIGGRAPH 794 Orlando Florida July 24 29 1994 Computer Graphics Proceedings Annual Conference Series pages 311 318 ACM SIGGRAPH ACM Press July 1994 ISBN 0 89791 667 0 Z Zhang Iterative point matching of free form curves and surfaces International Journal of Computer Vision 13 2 119 152 1994 R K Hansen and P A Andersen A 3 D underwater acoustic camera properties and applications In P Tortoli and L Masotti eds Acoustical Imaging Plenum Press London 607 611 1996 V Murino A Trucco Three dimensional image generation and processing in underwater acoustic vision Proceedings of the IEEE 88 12 1903 1946 2000 Department of Computer Science University of Genova WWW disi unige it 32 ARROV Project GRD1 2004 180601 Page 33 of 42 Document ID DISI ARD 012 13 14
23. c a lot of time is spent for it Especially when the motion of the ROV s very slow it could be possible to disable this feature Even if there is a flag in the algorithm for its disable for the most of the cases this procedure 1s recommended Subsampling level As we mentioned before the number of points of the subsampled image influences the performance of the alignment This parameter 1s tunable by the user that can adapt the subsampling to the environment conditions Also for this parameter we have find a reasonable estimation that can be used as a default value Department of Computer Science University of Genova WWW disi unige it 18 ARROV Project GRD1 2004 180601 Page 19 of 42 Document ID DISI ARD 012 Deliverable 5 1 Number of pre aligning iterations Some iterations of the classic method for computing the closest points without re projection are needed when the two images are not close enough even if this phase is very computational expensive By testing different sequences of image pairs we verified that two iterations are sufficient for a good pre alignment 1 6 MOSAICING In general the meshes built on the single frames when represented in the same coordinate system after registration will freely overlap and intersect Jumps cracks and redundant surfaces will occur at overlaps Figure 8 Thus the simple collection of such meshes 1s not sufficient to give a final mosaic of the sensed objects Meshes must u
24. construction of the Mesh A Filter to the perimeter of a face is applied in order to improve the goodness of the mesh 1 4 FILTERING Once all the faces have been added to the mesh the isolated vertices are cut off and the normal for faces and vertices are computed adding them to the mesh structure The normal computation is split into two phases l Compute normals for faces by tak ng the external product of two independent unit vectors lying on the face itself 2 For each vertex compute the relative normal by taking the vector sum of the faces normals sharing the active vertex the neighborhood faces of the vertex The connectivity information coming from the mesh 1s used to discard connected components smaller than a given size This step called size filter greatly improves the quality of the acoustic images Department of Computer Science University of Genova WWW disi unige it 14 ARROV Project GRD1 2004 180601 Page 15 of 42 Document ID DISI ARD 012 Deliverable 5 1 g aoo00097 E651 A E a UN Spiel Dus ae EAE em Sess ES kx y Y TEET he SERENE m ARS ET ae SSE RE C Ae aka B SCC SEREDCERELLLIITELTN e pe ES EN mae Pos aE ooo D
25. ded based on a size budget and or of accuracy requirements and can be variable in space so as to support view dependent rendering Because the multi resolution model is built off line through a time intensive procedure multi resolution cannot be used on line to render the scene that is being constructed through mosaic Therefore possible applications of multi resolution modelling are e During exploration of a partially known environment being the position of the ROV with respect to such environment available 1n order to provide virtual geometries to the augmented reality module of pilot interface e During off line processing of data to ease exploration of large models The multi resolution modelling engine has been developed on the basis of the Multi Triangulation MT a general and powerful multi resolution model that is described in detail in the Appendix D5 1 1 and in references therein A software package is made available at URL http disi unige it person MagilloP MT which includes an object oriented C library and related software tools The library supports the design of applications that make use of the MT such as e MT constructors based on mesh simplification algorithms In particular a constructor 1s provided that can take in input either a triangle mesh at high resolution or simply a cloud of points terrain data only e MT clients that query an MT on the basis of resolution parameters such as o size of t
26. dian Absolute Deviations away from the median A value of k 5 2 under the hypothesis of Gaussian distribution 1s adequate 1n practice as reported in 6 since it corresponds to about 3 5 standard deviations and the range n 3 50 u43 56 contains more than the 99 9 of a Gaussian distribution The rejection rule X84 has a breakdown point of 50 any majority of the data can overrule any minority 2 2 PRE MOSAICING Pre mosaicing consists essentially of the first two phases of the mosaicing sub module as described in the previous section Such two phases are performed on the sequence of input frames initially registered with the accurate pairwise registration method described above Department of Computer Science University of Genova WWW disi unige it 2 ARROV Project GRD1 2004 180601 Page 28 of 42 Document ID DISI ARD 012 Deliverable 5 1 Once vertices undergo the fusion phase instead of generating the mesh an incidence matrix 1s updated The incidence matrix 1s a square matrix with as many rows and columns as the number of frames only the triangular part of the matrix below the diagonal is used though For each entry 1 j of the matrix a score 1s recorded which counts the number of points in the mosaic that are obtained by fusing one point from frame I with another from frame jJ The higher the score the more overlap between two different frames All entries of the incidence matrix are initially set to zero In order
27. ement of the list is a mesh which consists in turn of the following data o A name in the form of a positive integer number We may initially assume that just one new mesh is generated at each frame in this case the name of each mesh 1s the time stamp of the frame that generated it first o The number of triangles in the mesh in the form of a positive integer number o A list of triangles where each triangle is a triple of points and a point is in turn a triple of Cartesian coordinates x y z in a global coordinate system each coordinate 1n the form of a real number float Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 6 of 42 Document ID DISI ARD 012 Deliverable 5 1 A list of meshes may possibly be empty which means that no new parts of mosaic have been generated at the current frame e A 4x4 registration matrix in homogemeous coordinates it is sufficient to transmit the first three rows of the matrix each coordinate in the form of a real number double because precision is important in this case which describes current position and orientation of the sensor in a global coordinate system Graphical Viewers of the POLECAT System will maintain the current mosaic as a collection of meshes each mesh having the same structure described above Meshes received by a Viewer at a given frame can be of two kinds e New mesh a mesh that was generated in the curre
28. epicted Department of Computer Science University of Genova www disi unige it 22 ARROV Project GRD1 2004 180601 Page 23 of 42 Document ID DISI ARD 012 Deliverable 5 1 Meshi Fa Yat Za Fa TA VPN RU LV LOL IP y L ju ST ae ae ae TS s IS er E V Titty a CY vuv Vara IN Z IVA 7 ys AY af at yy vj i WO Lf EA VL V pari Fita Fi ww Va Ze V 20 a d p LI A Ad r vin vl AAA LA PS NY VAS va Ad L V 4 V Fa i 4 NWS SANSA YI la CA di Wi iF ah zy E P E IY ZI NISI vA AZ ini Z Z zi MD ND E ND NINS YN S Ti LS mS NT Frac IVA en WES AS Ww Vir 5 vl 77 A Yi aS INA W VAN AIN NEDA h N 3b MW A 14 Ez he SAN Ua x ARINI SNL p L WI N b NY Ny ry ET Lai ga 4 Wass iw Pe AN a N Pont Figure 11 Surface after rasterization left and before right 1 6 2 Phase 2 Fusion After the rasterization phase has been completed on every rasterization plane p the updated intersection lists are scanned and fusion is performed As we said before we follow the same approach as in the original MIA to merge intersections generated by A and by 5 which are close along an edge of the grid Note that 1 while 1n the original MIA many possible intersections could need to be merged together because many different frames overlap on
29. est Point In general when point correspondences are unknown the Iterated Closest Point ICP algorithm may be used For each point y from the set Y there exists at least one point on the surface of X which is closer to y than all other points in X This 1s the closest point x The basic 1dea behind the ICP algorithm 1s that under certain conditions the point correspondence provided by sets of closest points Is a reasonable approximation to the true point correspondence The ICP algorithm can be summarized 1 For each point in Y compute the closest point in X 2 With the correspondence from step 1 compute the incremental transformation R t 3 Apply the incremental transformation from step 2 to the data Y 4 If the change in total mean square error 1s less than a threshold terminate Else goto step 1 Department of Computer Science University of Genova WWW disi unige it 26 ARROV Project GRD1 2004 180601 Page 27 of 42 Document ID DISI ARD 012 Deliverable 5 1 Besl and McKay 1 proved that this algorithm is guaranteed to converge monotonically to a local minimum of the Mean Square Error MSE ICP can give very accurate results when a set 1s a subset of the other but results deteriorate with outliers created by non overlapping areas between views In this case the overlapping surface portions must start very close to each other to ensure convergence making the initial position a critical parameter Modifications t
30. f corresponding points is still open to be addressed and different innovative techniques 29 30 31 have been proposed recently 1 5 1 Reverse calibration approach In this report we propose an acceleration method based on the so called reverse calibration technique 32 The method 1s based on the fact that from the sensor we obtain data stored in both the structures of unorganized cloud of point x x y z and range image r i j 1 e a 2 5 dimensional image 33 Given a 3D point y e Y of data set and given the camera parameters it is possible to project y onto the range image of the model set 7 i j The 3D point x eX associated to r i 7 will be the hypothetic corresponding point of y In order to 1mprove the accuracy of finding correspondences it 1s possible to use the information of the connectivity given by the range image We define the neighborhood V of x as Np tea X st tea RP fmi tk jth kh wee w p where w is the dimension of a window centered on r i j and RP r i j 1s the operator that re projects the range point r 7 J onto the Euclidean 3D space It is worth noting that the range image is not dense since after the filtering a lot of points are discarded For each range point 7 i j there is a flag that indicates if the associated point is survived or not More precisely the operator RP r i j gives O if the Department of Computer Science University of Genova WWW disi unige it
31. fined by the ARROV sensor Department of Computer Science University of Genova WWW disi unige it 10 ARROV Project GRD1 2004 180601 Document ID DISI ARD 012 Page 11 of 42 Deliverable 5 1 For each vacant entry v Figure 4 left the procedure considers a 3x3 window W surrounding v and tests for connectivity between pairs of non vacant entries belonging to this W l It tests vertical and horizontal adjacencies checking existence and validity a connection can exist only if 1t do not intersect any other already existing connection 2 It tests the two diagonal adjacencies and validate each potential adjacency only if there are no existing edges crossing it Vacancies Analysis Po r2 Wiech ZI Wien ml Herne 2 27 LTE if adj mat i m adj dim m adj dim 1 0 BOOL done FALSE Load interesting entries with respect to the active 3x3 window Losgdowl v6 v3 v4 lntlhrfres double d16 d34 if vl NULL amp amp vo NULL dlo6 RaDist vl v6 if v3 NULL amp amp v4 NULL d34 RaDist v3 v4 if dlo lt m RadThr d34 lt m RadThr LE OLO 0941 UpdateAdjacencyMatrix done TRUE j else UpdateAdjacencyMatrix done TRUE j y Met eS try the erossed ones first qood ie taken if done Load vO v7 IntThres if v0 NULL amp amp v7 NULL amp amp RaDist v0 v7 m RadThr if adj mat itm Width 2 m adj dim4 14 0 amp amp Tf Q 16 adj mat i 1 m adj dim 1
32. for underwater images in which the ROV moves back and forth we can find significant overlapping also between distant views in the temporal sequence The aim of our method is to optimize the information coming from every pairwise registrations obtained by the alignment of all overlapped range images The original contribution consists in obtaining a global registration by introducing algebraic constraints on the transformations instead of data points We first perform pairwise registration between every view and each of its overlapping views thereby computing the Gij whenever it is possible By considering many equations as 2 3 3 we can build a system of equations in which the Gi j are known quantities obtained by pairwise image Department of Computer Science University of Genova WWW disi unige it 29 ARROV Project GRD1 2004 180601 Page 30 of 42 Document ID DISI ARD 012 Deliverable 5 1 registration and the matrices Gil Gi 1 1 N are unknowns to be found By decomposing the homogeneous transformation matrices G into a rotation and translation equation 2 3 3 splits 1n two f RI RR t Ritt t 2 3 5 where R is a rotation matrix and is a translation vector Although this system of equations 1s essentially linear a number of problems arise when formulating solutions that account for the non linear constraints on the components of R In order to respect these constraints the rotation matrices must be suitabl
33. g rate S and select one point every S according to the acquiring order Although the random method is more accurate the uniform method 1s quite faster For this reason we decide to implement the uniform method 1 5 3 Pre alignment We verified that the alignment based on the reverse projection could fail when the two views are not enough close In order to increase the robustness of the registration we applied for some iteration the classical ICP method without reverse projection This action permits to obtain a good pre alignment from which the reverse calibration alignment converges fast and correctly to the optimal solution 1 5 4 Speed vs accuracy As we stressed before this work aim at finding the best trade off between speed and accuracy In this section we summarize the parameters and the features of the algorithm that are crucial for the performance of the algorithm Vanish Threshold this parameter defines the stop criteria of the ICP iterations If the residual is less than this threshold the alignment 1s stopped By reducing the vanish the accuracy 1s improved but more iteration must be carried out and consequently more time is spent Although this parameter could be tuned by a user we have found experimentally its best estimation Automatic outliers rejection This procedure makes the algorithm robust to the outliers that rise when the two views are poorly overlapped Because this computation 1s based on statisti
34. h for Horizontal Semi Diagonals in a 3x3 block for i 0 i m Width m Height 1 2 i firat check BOOL done FALSE if adj mat itl m adj dim 4 1 done TRUE else if adj mat i 1 m adj dim 5 1 173m Width amp amp adJ mati m Widthtl m adj cxmrilsel done TRUE if done descendant semi diagonal Load vO vl IntThres if vO NULL amp amp vl NULL if CheckOnAdjacencyMatrix UpdateAdjacencyMatrix if done ascendant semidiag Load Qw0 vl lnt hres s 1 vO NULL amp amp vl NULL if CheckOnAdjacencyMatrix UpdateAdjacencyMatrix done TRUE Search for Vertical Semi Diagonals ror 1 07 1 lt m Width m Height 2 1 LPF 1 IT first Check BOOL done FALSE if adj mat itm Width m adj dim 10 1 done TRUE else 1r a ad mati ttm Wlidtbhbrl m adj dimt25 1 j adj mat i m Width m adj dim 11 1 done TRUE if done descendent semi diagonal Load vO vl IntThres Department of Computer Science University of Genova WWW disi unige it 12 ARROV Project GRD1 2004 180601 Document ID DISI ARD 012 Page 13 of 42 Deliverable 5 1 if vO NULL amp amp vl NULL if CheckOnAdjacencyMatrix UpdateAdjacencyMatrix done TRUE if done Load vO vl1 IntThres if vO zNULL amp amp vl1 NULL if CheckOnAdjacencyMatrix UpdateAdjacencyMatrix done TRUE ascendant semi diagonal Table 4
35. he Leak Detection Module that process t and sends out a result string as described above 5 Reset Data each Frame each time a frame arrives the old one 1s deleted Note this mode is useful for system monitoring purposes where user don t want to keep frames into the main memory 6 Save Motion Matrices if this checkbox 1s selected after every registration the resulting motion matrix 1s saved on disk 4 4 2 Filtering Filtering applies partly before the single frame reconstruction on raw acoustic data and partly after by removing small connected components in the resulting single reconstructed mesh Pre Filtering Thr an Intensity 4 Edi Thr on Radial Distance Edi Histogram Bins Edt Connected Components Aemoyal Min Conn Comp size Edi Figure 15 Pre filtering Settings e Pre filtering if active filters out points in the acoustic frame on the base of their intensity or their radial distance DEFAULT TRUE e Threshold on Intensity cut off threshold float DEFAULT 1 RANGE 0 100 e Threshold on Radial Distance cut off threshold float DEFAULT 1 RANGE 0 100 e Histogram Bins Number of Histogram Bins used to estimate the values distributions DEFAULT 100 e Connected Components Removal if active removes small connected components in the single frame reconstruction DEFAULT FALSE e Minimal Connected Components size minimum number of vertices of connected component
36. he extracted mesh o focus on an area of interest e g view frustum Department of Computer Science University of Genova WWW disi unige it 3l ARROV Project GRD1 2004 180601 Page 32 of 42 Document ID DISI ARD 012 Deliverable 5 1 o space dependent accuracy e g accuracy decreasing with distance from viewer The source codes of some demo clients are provided to ease the design of applications For further details see Appendix D5 1 1 and URL http disi unige it person MagilloP MT 4 References 1 2 3 4 5 6 7 5 9 10 11 12 M Hall ARROV Project Data Transfer Specification ARROV Project Report GRL MSH 127 1 15 2002 Mid term Report Annex VII R Bergevin M Soucy H Gagnon and D Laurendeau Towards a general multiview registration technique IEEE Transactions on Pattern Analysis and Machine Intelligence 18 5 540 547 May 1996 Hugues Hoppe Tony DeRose Tom Duchamp John McDonald andWerner Stuetzle Surface reconstruction from unorganized points Computer Graphics 26 2 71 78 July 1992 K Ikeuchi M D Wheeler Iterative estimation of rotation and tranlslation using quaternion Technical Report CMU SC 95 215 Carnegie Mellon University 1995 P Besl and N McKay A method for registration of 3 D shapes IEEE Transactions on Pattern Analysis and Machine Intelligence 14 2 239 256 February 1992 F R Hampel P J Rousseeuw E M Ronchetti
37. he mesh with the same name must be deleted from the collection held by the Viewer A modified mesh can be discriminated from a new mesh on the basis of existence of his name in the collection of meshes that form the current mosaic 1 8 USER MANUAL A Data Proc Module has been developed for real time processing of data from Echoscope sensor and SIT camera thereby producing mesh data for graphics visualization The Data Proc Module receives Acoustical and Optical data from the POLECAT Data transfer Interface process it and sends out meshes to the POLECAT Pilot or Surveyor Module via the Mesh Transfer Interface The Elaboration Settings are managed by a Settings Dialog which stores the settings into the host machine registry Each time the Data Proc Module is started it reads the settings from the registry and applies them See section Settings in the User Manual Document Appendix1 For more information on the see the Appendix 1 of this document that reviews the main features of the Data Proc Module and its usage hints 2 Off line data processing Off line data processing is obtained from the on line data processing simply by replacing the fast registration sub module with another module for accurate registration Another difference 1s that the Department of Computer Science University of Genova WWW disi unige it 25 ARROV Project GRD1 2004 180601 Page 26 of 42 Document ID DISI ARD 012 Deliverable 5 1 mosaic is not de
38. ic 1mage formation IEEE Transactions on Image Processing 8 2 270 285 1999 V Murino A Trucco C S Regazzoni A probabilistic approach to the coupled reconstruction and restoration of underwater acoustic images IEEE Transactions on Pattern Analysis and Machine Intelligence 20 1 9 22 1998 D A Danielson Vectors and Tensors in Engineering and Physics Addison Wesley Publishing Company London 1996 L V Subramaniam R Bahl Segmentation and Surface Fitting of Sonar Images for 3D Visualization Proc Sth Int Symp on Unmanned Untethered Submersible Technology Durham NH USA pp 290 298 September 1995 Cignoni P Montani C Scopigno R and Rocchini C The Marching Intersections algorithm for merging range images Technical Report B4 61 00 I E I C N R Pisa Italy June 2000 Curless B Levoy M A volumetric Method for building complex models from Range Images Computer Graphics Siggraph 96 Proceedings pp 221 227 1996 Department of Computer Science University of Genova WWW disi unige it 33 ARROV Project GRD1 2004 180601 Page 34 of 42 Document ID DISI ARD 012 Deliverable 5 1 26 27 28 29 30 31 32 33 M Levoy S Rusinkiewicz E cient variants of the icp algorithm In IEEE Int Conf on 3 D Imaging and Modeling 3DIM 01 Quebec City Canada 2001 J L Bentley Multidimensional binary search trees used for associative searching CACM 19 September
39. ige it 39 ARROV Project GRD1 2004 180601 Page 40 of 42 Document ID DISI ARD 012 Deliverable 5 1 e KT ICP parameter used to set the confidence on Translation measure from the echoscope sensor double DEFAULT 0 RANGE 0 100 e Accurate ICP uses slow ICP e Sensor Pre Alignment uses alignment data coming from echoscope sensor e X84 Rule if selected uses the X84 rule in the ICP computation e Exclude Border if selected excludes the border points from the computation e Calibration Opto Acoustic Calibration section e Calibration Matrix is the 4x3 matrix that binds 3D data from acoustic sensor with 2D data from SIT camera This matrix is used to colorize or texturise the final meshes The button Load browses for the calibration matrix file 4 4 4 Mosaic The Mosaic gathers together the meshes after filtering and single frame reconstruction applies the transformation computed by the registration module and produces a output mosaic mesh Grid Step Edit Scale Coeff Edi Pe m Thr Edi Lazy Update Update Thr 3 Edi Figure 17 Mosaicing internal settings e Grid Step size of the main grid in the mosaic This parameter tunes the overall resolution of the mosaic Note as the grid step increases it deeply affects the computation time and therefore the on line performance of the system double DEFAULT 30 e Scale Coefficient used to multiply the incoming 3D points Used for compatibility issues with
40. ion and Intersection Management This part of the algorithm analyzes every face f of one of the registered meshes searching for intersections with the virtual underlying grid G the other 1s the actual mosaic and therefore 1s already aligned at the grid For every face f the minimum enclosing box Box is computed and the f projection on each plane called rasterization planes in the x y and z directions XY XZ Y Z 1s analyzed Figure 9 i jli m LM ro ee i it i niti patte Figure 9 Rasterization procedure intersections are marked in red left the rasterization lines X axis in green right For doing this every plane is subdivided in rasterization lines 7 5 each line being orthogonal to the plane and passing through a node of the grid These lines may intersect a face at some points Then for each line all the intersections i715 7 are computed and the collection of all lines 7 l2 lm gives the set of intersections related to a given rasterization plane p Figure 9 Figure 10 Each intersection i 1s described through a class with the following instance members e icas intersection value e name for the name of the original mesh or timestamp e sgn an integer representing the sign of the face normal projection on raster line e dir anumber representing the value of the face normal projection on raster line e wanumber representing the weight of the intersectio
41. livered in input frame by frame as it 1s updated but all together at the end of processing in the form of a whole mesh In the following we will describe just the new sub modules that are inserted to perform accurate registration 2 1 ACCURATE PAIRWISE REGISTRATION Pairwise registration was addressed using the classical Iterative Closest Point ICP algorithm 1 to which we added an outlier rejection rule called X84 in order to cater for non overlapping areas between views 2 1 1 1 Two view point set registration Let us suppose that we have two sets of 3 D points which correspond to a single shape but are expressed in different reference frames We call the first of these the model set X while the other will be the dataset Y Assuming that for each point in the data set the corresponding point in the model set is known the point set registration problem consist 1n finding a 3D transformation which when applied to the data set Y minimizes the distance between the two point sets The goal of this problem can be stated more formally as follows N 23 x Ry 4 t ll 2 1 1 where R is a 3x3 rotation matrix t is a 3x1 translation vector and the subscript 7 refers to corresponding elements of the sets X and Y Efficient non iterative solutions to this problem were compared in 7 and the one based on Singular Value Decomposition SVD was found to be the best in terms of accuracy and stability 2 1 1 2 Iterated Clos
42. ly registered The reset button deletes all the meshes from the Extra Mosaic mesh buffer and from the Pilot Surveyor visualization module Gas Oil Leak Detection This window shows every message coming from the Gas Oil Leak detector 1f activated 1n the pipeline The showed message can be one of the following e DETECTOR NOT INITIALIZED Leak Detection is active but has not been properly initialised WAITING FRAMES Leak Detection is active but waiting for frames LEAK DETECTOR IS WORKING Leak Detection 1s active and computing NOTHING DETECTED No motion has been detected DETECTED A BUBBLE COLUMN Leak Detection detected a Bubble Column DETECTED A LEAK Leak Detection detected a Leak The reset button re initialises and restarts the Leak Detection module 4 3 SETTINGS The settings dialog contains a roll up control that allows for changing the elaboration pipeline and the settings for every processing module The Settings Dialog 1s modeless so it can be shown through the usual operations Note in order to make effective the changes user has to push on the Apply button When the Data Proc Module is active it reads all the settings from the registry key SoftwareNARROV DATAPROC The settings are written back in the registry when the application is closed Note in case of abnormal termination or application crash the settings can be partially or completely lost In this case user has to check at next exec
43. m sized mosaic this 1s quite unlikely Actually the hash function is defined 1n three dimensions as k x y z A x B y C z and it 1s used both on the rasterization planes setting z to zero and on the whole 3 D mosaic for cell s indexing purposes 24614 AP ce i z P n m 44 e k eee TIT 17 i 710 eee is IT rw m A pi TW ir By ff V A h ia A NW y ps Yn L2 Ay d eme 7 BS a Sr as 7 as apy US M ute n EN LE 4 Cy SET Wi E r Tai y Cu F E eu A TN EMEN SEER WILDE X r A CI Seek L m f JS Y gt a LREN cg cra SP Ld TS ena W RS NI A v BR MN Ww h A IZ n a KY y Ly td AA AAA V p y i ug SC 7N IN f E A n A T i J EA NM AI eL E TN ax W RA a an LA gt 7 YW Figure 10 Cells edges and intersection in red As we said before each intersection object has a weight w which measures the reliability of the data and it is used in the fusion phase The weight is computed by linearly interpolating the intensity values of the vertices that describe the current face If do d d are the distances of the intersection point from the vertices and Jp I are their intensities then the weight w 1s defined as follow yao dy d th dy dy thd dj d d d d d d In Figure 11 the result of the rasterization step 1s presented in the left while on the right the original mesh of a single frame is d
44. n computed as a bi linear interpolation of the weight of surrounding vertices Intersections generated by each face f are ordered with respect to their value In the Fusion phase of the algorithm 1f two intersections 7 i are closer than the fusion threshold FT a merging procedure 1s invoked When an intersection i 1s computed it 1s inserted into a bi linked list of the corresponding rasterization line as the number of rasterization lines is very big we chose to represent a rasterization plane as an associative collection hash table of lists keeping therefore only those structures containing real intersections Every time we instantiate a new list it is also added to a structure that contains all the updated or generated list of the current frame this structure 1s a queue FIFO type that 1s scanned during the fusion phase Department of Computer Science University of Genova www disi unige it 2 ARROV Project GRD1 2004 180601 Page 22 of 42 Document ID DISI ARD 012 Deliverable 5 1 Note that we assume that underlying grid to have no bounds that 1s to be virtually infinite Therefore we have to generate for each pair of coordinates a unique key as a function k x y that describes the rasterization line unfortunately it 1s quite difficult to find such a function For sake of simplicity we chose k x y A xt y where A 1s a constant usually big Of course it is possible for collisions to occur but for a mediu
45. ndergo a process of geometric fusion which produces a single mesh starting at the various registered meshes If the fusion is to be done in off line framework algorithms proposed in 24 25 serve well the purpose In the case of the on line version at a given instant of time a mesh A is given which represents the mosaic obtained from all previous frames and a new mesh B comes which is built from the current frame as explained in the Single Frame Reconstruction Step The aim is to merge such meshes in a consistent way n order to obtain a new mesh R which represents the scene spanned by both A and B This must be a fast process since the system must support real time visualization of the mosaic at each frame In particular the output of the algorithm must be used to update the graphical system with the new primitives to be rendered Unfortunately this is not simply an incremental process in which new graphical primitives are added to the existing ones at each new frame Indeed the fusion operation may change the portion of A that overlaps with B and it must overlap otherwise registration would fail tle CN rA Ss Kk NEN NG ACE i RES ANAS sy AW Cn DS Figure 8 some faces may overlap after multiple single frame meshes have been added at the model This means that some primitives rendered in previous frames will have to be substituted with new ones Eventually this means that display lists used by the graphics
46. non negative integer value unsigned integer on 8 bits optionally this may be extended to 16 bits e Pre registration information in the form of a 4x4 matrix of real double values The matrix represents a rototranslation in homogeneous coordinates actually only the first three rows of the matrix are necessary the fourth row being fixed A point from the range map when multiplied by this matrix becomes represented in a global coordinate system In order to reduce the size of data exchanged between the Data Acquisition and Pre processing module and the other modules the possibility will be considered to compress the range map prior to transmission and decompress it prior to local storage by the following mechanism e The array of intensities is run length encoded This kind of compression 1s likely to be effective since this array contains many zero values Intensity values are transmitted first e Only points corresponding to non zero intensity values are transmitted Delta encoding of point coordinates may be also considered A Statistical analysis of time saved during transmission vs additional time spent for compression decompression 1s necessary to estimate the advantages of this mechanism Compression decompression will be managed by interface methods provided by the Data Acquisition and Pre processing module 1 1 2 Output A mesh update consists of the following data e Atime stamp same as in input e A list of meshes Each el
47. nt frame In this case this mesh must be added to the collection held by the Viewer e Modified mesh a mesh which was generated in a previous frame and modified in the current frame In this case this mesh must substitute the mesh having the same name in the collection held by the Viewer An empty mesh 1 e a mesh with zero triangles means that the mesh with the same name must be deleted from the collection held by the Viewer A modified mesh can be discriminated from a new mesh based on existence of its name in the collection of meshes that form the current mosaic If the current mosaic 1s downloaded to disk 1t will be encoded as a single mesh containing all triangles of the mosaic and having the same structure described above except for the name Global download can be slow depending on the size of the mosaic so the system user should assume to either interrupt or terminate on line operations during download 1 1 3 Parameters The program needs some parameters to be either specified by the user or automatically set at startup Parameters have influence on trade off between speed and accuracy of reconstruction Some parameters can be set only at startup and remain fixed for a whole session while others can be adjusted through GUI even during on line operations e Intensity threshold a non negative integer value in the range 0 255 optionally 0 65535 if 16 bits are used for intensity values This 1s used during data thresholding
48. o the original ICP have been proposed to achieve accurate registration of partially overlapping point sets 8 9 10 We implemented a variation similar to the one proposed by Zhang 10 using robust statistics to limit the maximum allowable distance between closest points 2 1 1 3 Robust outlier rejection As pointed out by Zhang the distribution of the residuals for two fully overlapping sets approximates a Gaussian when the registration 1s good The non overlapped points skew this distribution they are outliers Therefore good correspondences can be discriminated by using an outlier rejection rule on the distribution of closest point distances To do this we employ a simple but effective rejection rule X84 6 which use robust estimates for location and scale of a corrupted Gaussian distribution to set a rejection threshold The median is a robust location estimator and the Median Absolute Deviation MAD defined as MAD med le med i j 2 1 2 Is a robust estimator of the scale 1 e the spread of the distribution It can be seen that for symmetric and moderately skewed distributions the MAD coincides with the interquartile range MAD 53 4 61 4 2 1 3 Where is the g th quartile of the distribution for example the median is 5 For normal distributions we infer the standard deviation from MAD 1 3 4 e e 0 67450 2 1 4 The X84 rule prescribes to reject values that are more than k Me
49. on occurs through a sequence of operations that process input range maps to build the mosaic mesh The following software components are present both in the on line and in the off line version possibly with different characteristics and implementation on the two versions l Data thresholding raw data in input are filtered on the basis of sensor intensity values to discard those data that appear to be spurious 2 Single frame reconstruction a mesh of triangles 1s built for each frame which interpolates range data from that frame only Mesh filtering each single frame mesh is filtered by eliminating small connected components 4 Registration meshes from different frames are registered in the same coordinate system Mosaicing registered meshes are used to compose the mosaic mesh The 3D object reconstruction software comes 1n two versions on line and off line The on line version is intended for use during ROV operation to provide feedback to the pilot on the scene spanned by sensors In this version stress 1s on fast methods that can support real time operation The off line version is intended for use during surveying sessions on data collected previously In this case stress 1s on accurate methods that can provide high quality models The on line version of reconstruction consists of a strictly sequential execution of the above five components These components might be pipelined in a multi processor architecture However in the re
50. rthogonal by dividing the matrix by the squared length of the quaternion 4 Ri c Rai q g g 2 3 7 where R q 1s the rotation matrix given by 2 TE Lm n 2l EU su 2l ATE SU R IC Zl uu sw a Te p w 2J Vw su Auw su 2 wm su s p j E 2 3 8 Department of Computer Science University of Genova 30 WWW disi unige it ARROV Project GRD1 2004 180601 Page 31 of 42 Document ID DISI ARD 012 Deliverable 5 1 This constraint 1s necessary in general to ensure the gradient accurately reflect the differential properties of a change in the quaternion parameters 3 Multi resolution representation The purpose of multi resolution modeling is to speed up the exploration of large pre computed geometric models such as seabeds and rig structures as well as mosaics of generic structures recorded from the on line data processing system during previous explorations The multi resolution modeling engine consists of e an off line phase that takes in input a large model in the form of a mesh and builds a multi resolution version of it e an on line that takes in input a multi resolution model and depending on parameters specified by the application using it returns a mesh providing a simplified version of the object to be represented The on line version works in real time and can provide a different mesh from frame to frame The resolution of the output mesh can be deci
51. s as well as parameters that need to be set by the user through GUI Multi resolution representation is intended for off line use Its main purpose is to speed up the visualisation of large meshes e g sea beds or mosaics build during previous survey sessions by concentrating the level of detail only where it 1s necessary and discarding detail elsewhere The multi resolution software consists of one construction module which builds the multi resolution model and a library to build applications that query the multi resolution model and obtain meshes at different level of detail for their purposes One example 1s a viewer that queries the multi resolution model at each frame to obtain meshes clipped at the view frustum and with a resolution decreasing with distance from the viewpoint The multi resolution software is described 1n Section 3 1 Online Reconstruction and Mosaicing 1 l ARCHITECTURE The aim of this section 1s to describe in details the ARROV on line data processing scheme The main goal of this data processing 1s to construct a model of the underwater environment and to track the ROV s motion or pose based on the processing of acoustic images optical images and the pose information from the motion sensors The program for on line 3D reconstruction receives in input a sequence of frames and produces a corresponding sequence of mesh updates Figure 1 The program 1s endowed with a GUI that allows the user to set a number of par
52. s then the fusion operator performs a shift of the intersections toward the new average location During this operation whenever we move from a virtual cell to another a couple of artificial intersections are created on all the perpendicular virtual edges the intersection touches When a new intersection is generated the algorithm analyzes the other intersections on the same virtual edge in order to verify 1f a removal operation can be applied The removal operation is performed on the currently updated raster lines 1 that is where a new intersection has been created A removal action which removes two intersections from the current raster line is performed on each pair of intersections 74 72 which e lie on the same edge cell ee e have the same name or timestamp t t 2 and e have different signs sgn zZsgnp 1 6 3 Phase 3 Mesh generation The mesh generation phase uses a modified versions of the popular marching cubes algorithm for polygonising a scalar field The basic idea is that the reconstruction of a 3D surface is completely defined if all the signed intersections of the surface with the lines of a regular grid are known The mesh construction can be seen as a sequence of single cell meshing Given the virtual 3D grid G each cell c can be indexed by its edges eoc 11c or its vertices Voc Vzc By the use of a proper container structure such as a hash table or a map we keep in memory all the nece
53. s active and connected click on the RX button and wait until a valid connection 1s set up by the data transfer mechanism 4 Click on generate button to activate the timer that polls on the data transfer and 1f any elaborates the incoming data 5 In case push on the reset buttons to reset graphics visualization Department of Computer Science University of Genova WWW disi unige it 42
54. s in the mesh int DEFAULT 6 Department of Computer Science University of Genova WWW disi unige it 38 ARROV Project GRD1 2004 180601 Page 39 of 42 Document ID DISI ARD 012 Deliverable 5 1 4 4 3 Registration Registration computes the geometric transformation that registers the current frame with the previous one The resulting transformation is a 4x4 matrix describing rotation and translation in the world coordinates Vanish Edt Reliability Up Data Edt Reliability Up Model Edt Pre Edit Max Edt Kalman Settings Use Kalman Filter Queue Edi KR ICP Edi KTICP Edi Options Accurate ICP 4 Rule Sensor Frealianment Exclude Border Figure 16 Registration Settings e Vanish cut off threshold for stopping iterations double DEFAULT 0 001 e Reliability Up Data Threshold used to decimate points from the data int DEFAULT 400 e Reliability Up Model Threshold used to decimate points from the model int DEFAULT 1000 e Pre Alignment iterations number of slow ICP iterations used to pre align data int DEFAULT 0 e Max iterations max number of iterations 1nt DEFAULT 100 e Use Kalman Filter if selected Kalman Filter 1s activated e Queue Kalman buffer queue size int DEFAULT 5 e KR ICP parameter used to set the confidence on Rotation measure from the echoscope sensor double DEFAULT 0 RANGE 0 100 Department of Computer Science University of Genova WWW disi un
55. ssary structure without allocating too much memory or degrading the performances of the overall system For cell s indexing we use the same hash function defined above using the coordinates of the origin vertex that is the vertex 0 for generating the key k x y z A x D y Cz For each virtual cell c we analyze the intersections along its edges in order to construct similarly to how we would find out an 1sosurface the vertices actually the intersections themselves and the faces of the relative portion of mesh If an edge e 1 0 T contains an intersection int than the classification of its vertices depends on the orientation of that intersection 1 e sgn Successively faces are generated from the c edges intersections configuration through a lookup table implementing all the possible intersections configurations on edges 1 7 LAZY UPDATE Every time a mesh me 1s created it 1s stored as a display list that refers directly to a list of virtual cells and the relative vertices faces The current mosaic can be seen as a collection of meshes each mesh having the same structure described above Department of Computer Science University of Genova WWW disi unige it 24 ARROV Project GRD1 2004 180601 Page 25 of 42 Document ID DISI ARD 012 Deliverable 5 1 In order to support the graphics system the algorithm keeps a geometric structure consisting of lists of active cells and a corresponding graphic structure consis
56. st of this document we will refer to a single processor implementation that communicates with the Data Acquisition and Pre processing module and the POLECAT System through a software interface as specified in 1 The main difference between the on line and the off line version is in the registration task e in the on line version registration is made only pairwise one frame with respect to the previous frame e in the off line version registration is made globally each frame with respect to all other frames that overlap with it Department of Computer Science University of Genova www disi unige it ARROV Project GRD1 2004 180601 Page 3 of 42 Document ID DISI ARD 012 Deliverable 5 1 In the off line version a preliminary pairwise registration and data fusion which is part of the mosaicing task 1s necessary in order to provide a map of overlap among different frames which 1s used next for global registration Therefore the off line version consists of a sequential execution of steps 1 2 3 4a pairwise 5a partial 4b global 5b global Mosaicing 1s indeed obtained by modifying the on line version and integrating t with the global registration software developed to this specific purpose In the following two sections we describe separately the architectures of the on line and off line versions and related components focusing also data exchange with other software modules data exchange among different component
57. ted based on a preliminary analysis of the intensity difference distributions among 3D points Once the distribution basically a simple histogram 1s defined a threshold 1s computed that filters out the far queue of the distribution itself This threshold 1s computed as follows 1 for each point in the input we compute the intensity difference with respect to its neigbours delta matrix construction and we create a histogram of the differences 2 We find the maximum of the histogram through a simple search 3 We use a user threshold parameter TH tuning how far to cut the distribution e g TH 3 4 Moving from the first bin toward greater values the integral of the distribution 1s computed until it reaches 100 TH percentage of the total integral of the distribution 5 The bin at which this condition occurs 1s used for computing the maximum difference accepted for the intensities among adjacent points Analogously we compute a parameter threshold on the connectivity distance among 3D points Note that this procedure relies on the fact the outliers represent noise points and therefore have to be filtered away Unfortunately this 1s true only 1n some cases but in some others what seem to be an outlier 1s instead a useful point for this reason this filtering procedure is used with care during the whole pipeline 1 3 SINGLE FRAME RECONSTRUCTION The next step of the Recostruction Pipeline 1s the reconstruction of a triangle mesh
58. the resulting mesh 1s shaded using the normals to the faces set to Flat or the normals to the vertices set to Smooth DEFAULT Smooth Note in case of mosaic mesh generation the shading mode 1s set to Flat by default 4 4 6 Leak Gas Oil Detection Those settings refer to the Oil Leak Detection Module whose purpose is the on line detection of Oil and Gas Leaks Department of Computer Science University of Genova WWW disi unige it 41 ARROV Project GRD1 2004 180601 Page 42 of 42 Document ID DISI ARD 012 Deliverable 5 1 Operational Mode Advanced E tent Edi Log on file Max rea Edi ain Ske Edi MO Ebede Edi Figure 19 Leak Gas Detection Settings e Operational Mode chooses the operational mode of the Leak Detector e Logon File is selected saves to a file the verbose log from the Detector e Buffer Size size of frame buffer used for detecting leaks e Extent Advanced parameter Please refer to Oil Leak Detector Manual e Max Area Advanced parameter Please refer to Oil Leak Detector Manual e Bubble Area Advanced parameter Please refer to Oil Leak Detector Manual 4 5 EXAMPLE This a usage example of the Data Proc module during usual operations 1 If necessary change the elaboration settings activating the Settings dialog by clicking on the settings button 2 First click on the Connect button in main dialog interface 3 Ifa proper data source example echoscope module i
59. the same region in this case only pairs of intersections will need merge This suggests how the on line approach 1s able to distribute the workload through time by performing only a relatively small number of operations as a new frame comes 11 our fusion process uses only those cells intersecting 5 independently from the dimension of A Merge can be viewed as a warping process that acts on meshes A and 5 by moving their vertices along edges of the reference grid in order to align them in regions of overlap For every intersection lists associated with a rasterization line each couple of consecutive intersections 7 and i with different name or timestamp jz and concordant signs are merged together if their distance 1s shorter than the fusion threshold FT taking into account the reliability of the measurement IC dbgbs if t f sgn Sn PIC dir W dir Wa Wi 25 if D FT i Fusion i i H ic TEE Department of Computer Science University of Genova WWW disi unige 1it 23 ARROV Project GRD1 2004 180601 Page 24 of 42 Document ID DISI ARD 012 Deliverable 5 1 The term d in the previous expression takes into account the fact that fusion is performed along the grid lines rather than on minimum distance direction This operation corresponds to merge two concordant surfaces which cross the same virtual cell edge If the two intersections 7 i2 lie on different virtual cell
60. the table values In this way by avoiding the arc tangent computation a dramatic improvement of the speed 1s obtained Another improvement of the speed is gained by changing the computation of the distance in the corresponding points search phase In particular as customary in literature we compare the square of the distance by avoiding the computation of the root as following L Em Tal Wm ld tT 12m 7d 1 5 5 summary of the algorithm In summary the algorithm for speed up the finding of corresponding points 1s given by the following steps For each 3D data point y e Y e find i and j by using equations 1 5 4 and 1 5 3 e project y on to the model range image r i J Department of Computer Science University of Genova WWW disi unige it 17 ARROV Project GRD1 2004 180601 Page 18 of 42 Document ID DISI ARD 012 Deliverable 5 1 e find the hypothetic corresponding point x e find the neighborhood N of x e find the definitive corresponding point x 1f 1t exists 1 5 2 Subsampling The points of the data set are sub sampled in order to reduce the number of point used for registration We test two different subsampling methods random and uniform In both of them the size of the sub set 1s fixed a priori The random method computes the subset by generating different random number and consequently by calling the random function several times The uniform method simply calculates the subsamplin
61. thm can be divided into three main phases l Rasterization and Intersection management 2 Fusion with cleaning and removal operations 3 Mesh generation and Lazy Update It takes as input e asingle frame mesh SFM with time stamp t e a registration matrix AM in homogeneous coordinates which describes current position and orientation of the sensor in a global coordinate system e agrid resolution value GR positive real representing the edge length of square cells in which 3D space is subdivided e a fusion threshold value FT positive real representing the minimum distance between two vertices generated by different frames The Fusion threshold is usually kept lower than grid resolution e anupdating threshold value UT positive real representing the maximum number of changes in a mesh before a new list must be generated for visualization The Fusion Procedure produces in output e atime stamp t the same of the input e alist of meshes in which each mesh represents a new portion of mosaic or a modified one and has a name and the information on the number of triangles in that mesh e a list of triangles where each triangle is a triple of points each point represented in a global coordinate system with Cartesian coordinates x y z Department of Computer Science University of Genova WWW disi unige it 20 ARROV Project GRD1 2004 180601 Page 21 of 42 Document ID DISI ARD 012 Deliverable 5 1 1 6 1 Phase 1 Rasterizat
62. ting of different display lists each list of cells 1n the geometric structure has a corresponding display list 1n the graphic structure Each new frame generates one or more new lists both geometric and graphic Such lists contain the new active cells and their corresponding graphical primitives respectively Cells containing portions of surface originated from data with different reliability are distributed among different display lists This 1s done because highly reliable data are likely to survive longer without modifications Old active cells that were modified by processing the new frame B are updated in the geometric structure and each update increases a request value for the relative display list In order to speed up the process of the on line mosaicing a lazy update approach of the display lists has been implemented giving out to the Viewer only the newly generated display lists and those display lists for which the amount of changes exceeds the update threshold UT So meshes received by a Viewer at a given frame can be of two kinds e New mesh a mesh that was generated in the current frame In this case this mesh must be added to the collection held by the Viewer e Modified mesh a mesh that was generated in a previous frame and modified in the current frame In this case this mesh must substitute the mesh having the same name in the collection held by the Viewer An empty mesh 1 e a mesh with zero triangles means that t
63. ula x y tz 4xi yitz 0 We implemented an algorithm which correctly reconstructs a triangle mesh from a range 1mage as input It can be divided into four main steps l Find connections for non vacant entries p Recovery vacant entries 3 Improve connections find feasible semi diagonals 4 Generate the mesh In the following we will go into details of each step showing results and pseudo code of each sub procedure 1 3 1 Step 1 Find connections for non vacant entries Vi For each 2x2 block i in the lattice where v 1s a non vacant entry Figure 3 left the procedure v Vy tries to find feasible edges It first tests independently for horizontal and vertical connectivities basically vi v and vi v3 successively it tests for the descending diagonal vi v4 if it is found the procedure stops otherwise it checks the other diagonal searching for the connection between v3 and v Department of Computer Science University of Genova WWW disi unige 1it ARROV Project GRD1 2004 180601 Page 10 of 42 Document ID DISI ARD 012 Deliverable 5 1 Each time an adjacency 1s found the procedure updates the adjacency vector Test Harizonal adjacency Non vacant entry Adjacent entries Test Vertical adjacency f Test diagonal adjacency Figure 3 2x2 block testing left and the result applied on a input range image right add elements to the 2x2 block ror 1 0 1 md Herght 21 m Wrdth l1
64. ution 1f the settings are correctly set Department of Computer Science University of Genova WWW disi unige it 36 ARROV Project GRD1 2004 180601 Page 37 of 42 Document ID DISI ARD 012 Deliverable 5 1 Settings ee xl L Registration Fe omm C C 9 9 C ree ww Figure 13 for choosing the settins 4 4 ELABORATION MODULES 4 4 1 Pipeline The Pipeline Settings manages the overall elaboration module Each check box can activate or exclude a processing module from the main pipeline Each elaboration module has a dialog for its internal settings Elaboration chain Single Frame Recon Registration Leak Detection Mosaicing Reset Data each frame Path edi Figure 14 Dialog Box for internal settings l Registration The incoming Acoustic Frame is registered with the previous one and roto translated according with the transformation computed by the registration module Department of Computer Science University of Genova WWW disi unige it 37 ARROV Project GRD1 2004 180601 Page 38 of 42 Document ID DISI ARD 012 Deliverable 5 1 2 Single Frame Reconstruction The incoming Acoustic frame 1s meshed using the Single Frame Algorithm 3 Mosaicing the mesh produced by the Single Frame Reconstruction 1s added to the current Mosaic Mesh one or more meshes are sent out to the Visualization module 4 Leak Detection the incoming Acoustic Frame is sent to t
65. we choose arbitrarily view k as the reference one then the unknown rigid transformation G G are respectively G G As customary we will take k 1 These rigid transformations are not independent each other being linked by the composition relationship G s Gigi 2 3 2 We can therefore estimate the alignment G of image V on the reference view defined by the i image V by first registering V onto any view V and then using G to map the result into the space of V G G G 2 3 3 This relationship can be used to compute G when all the matrices G G are known by simply chaining them Gi IT qii j 2 2 3 4 The global registration matrix G will map V into the space of V the reference view As it is well known the combination of pairwise registration does not yield the optimal result For example if G and G are optimal on the sense that they minimize the mean square error distance between the respective sets then G computed with equation 2 3 2 does not necessarily minimizes the mean square error between views V and Small registration errors accumulate so that images near the end of a sequence have a large cumulative error 2 3 1 2 Global transformations adjustment In order to 1mprove the quality of global registration let us suppose we have locally registered all spatially overlapping image pairs n addition to those that are adjacent in the image sequence Especially
66. y parameterized ending up with a system of non linear equations The problem can be cast as a minimization of an objective function min y angle R R R R th t t ii 2 3 6 where angle takes a rotation matrix and returns the angle of rotation around a suitable axis Starting from the global registration obtained by chaining pairwise transformation equation 2 3 4 a solution is found using a Quasi Newton method The estimated transformation G G are influenced by all the pairwise observed transformations and the registration error is distributed over all the estimated transformations In this sense the final registration 1s very close to a well balance graph as defined in 1 Moreover the complexity of the proposed algorithm 1s independent from the number of points involved Because the objective function includes only the matrix components the complexity depends only on the number of overlapping views 2 3 1 3 Dealing with rotations A number of techniques have been developed to represent rotations One of the most convenient 1s the quaternions representation They have a number of mathematical properties that make them particularly well suited to requirements of iterative gradient based search for rotation and translation 4 Rotations are represented by unit quaternions Instead of requiring the quaternion g u v w s to be a unit vector we can enforce the constraint that the rotation matrix 1s o

Object reconstruction and 3D mosaicing Outline

Contents

Download Pdf Manuals

Related Search

Related Contents