A Linear Algorithm for the Hyper-Wiener Number of Chemical Trees

Visual Computer manuscript No.(will be inserted by the editor)Convex Contouring of Volumetric Data Tao Ju1,Scott Schaefer1,Joe Warren1Department of Computer Science,Rice UniversityThe date of receipt and acceptance will be inserted by the editorAbstract In this paper we present a fast,table-driven isosurface extraction technique on volumetric data.Un-like Marching Cubes or other cell-based algorithms,the proposed polygonization generates convex negative space inside individual cells,enabling fast collision detection on the triangulated isosurface.In our implementation, we are able to perform over2million point classifica-tions per second.The algorithm is driven by an auto-matically constructed look-up table that stores compact decision trees by sign configurations.The decision trees determine triangulations dynamically by values at cell ing the same technique,we can perform fast, crack-free multi-resolution contouring on nested grids of volumetric data.The method can also be extended to ex-tract isosurfaces on arbitrary convex,space-filling poly-hedra.Keyword:contour,polygonization,implicit modeling 1IntroductionRecent advances in hardware technology of3D scanning and sensoring has brought about the generation of large-scale volumetric data such as MRI scans,CT scans and geological images.A common approach to visualize these volume datasets is to represent the data as implicit func-tions and construct polygonal approximations of isosur-faces,i.e.locus of points with some given function value. This process is often referred to as contouring.The con-toured surface partitions the whole volume into negative space(locus of points with lower function values)and positive space(locus of points with higher function val-ues).In many interactive applications,such as computer gaming and real-world simulations,navigation is con-fined to the negative space,therefore fast operations for checking the side of the main subject(e.g.the navigator) with respect to the contoured surface becomes critical.These operations are often referred to as collision detec-tions.Traditionally,contouring algorithms consider the data volume in uniform cubical cells and polygonize isosur-faces in each non-empty cell,i.e.,cells that are inter-sected by the isosurface.By doing so,the entire nega-tive space is decomposed into sub-spaces within individ-ual cells.Assuming that the negative space models free space,checking whether a point lies inside the free space can be greatly accelerated if the negative sub-space is convex within the enclosing cell.Note that this point-classification is the fundamental operation for computing collision detection with other convex objects.For exam-ple,an edge lies in the free space if for each cell it passes through,both endpoints of the line segment within that cell lie in the cell’s negative space(figure1left).This observation is not true if the negative space within the cell is non-convex(figure1right).Fig.1Edge classification in a signed square with two dif-ferent contours.The dashed lines indicate the contours,the gray areas represent negative space,and the dark gray lineis the edge to be checked.The most widely used cell-based algorithm is the March-ing Cubes(MC)algorithm introduced by Lorensen and Cline[7].MC generates triangles on isosurfaces within each cell based on a pre-computed table of positive/negative patterns(referred to as sign configurations hereafter)2Tao Ju etal.Fig.2Triangulations from theof cell corners.MC became popular for its fast polygo-nization and easy implementation due to its table-drivenmechanism.However,for some sign configurations,MCdoes not produce polygonizations that are consistentin topology with neighboring cells,and thus result insurface discontinuities[4].This drawback has sparkledextensive research on dis-ambiguation solutions[1],[4],[5],[10]and strategies to generate topologically correctpolygonizations[9].Although these solutions generatetopologically consistent isosurfaces,the resulting nega-tive space inside each cell is sometimes disconnected,andthus not convex.In this paper,we propose a fast table-driven cell-basedcontouring method that generate topologically consis-tent contours,while preserving convexity of the nega-tive space within each cell.The algorithm depends on acomposite look-up table that associates each sign con-figuration with a compact decision tree for dynamic tri-angulation of isosurface patches.The reason for the useof a decision tree is that the actual triangulation de-pends not only on the signs,but also on the magnitudeof corner values.The decision trees are pre-computed toensure a minimal number of tests in determining eachtriangulation.This technique can be extended without difficulty tomulti-resolution contouring.In most multi-resolutionapproaches,direct application of the cell-based contour-ing algorithm to a grid of non-uniform cells can resultin surface cracks,i.e.discontinuity between iso-surfacesgenerated from neighboring cells at different resolutions.Various multi-resolution frameworks have been proposedfor contouring on non-uniform grids[3],[8],[11],[12],[14],yet they involve special crack-patching strategies.Bloomenthal[2]proposes an adaptive contouring methodwhich requires run-time face tracing to maintain con-sistent contours for neighboring cells.We show that byconstructing look-up tables for transition cells using theabove algorithms,the same table-driven contouring methodcan be applied to non-uniform data to generate crack-free isosurfaces.The remainder of this paper is organized as follows.Afterreviewing the table-driven Marching Cubes algrorithm,we present the convex contouring algorithm on uniformgrids.Then we explain the automatic construction oflook-up tables in more detail.Next we extend the pro-posed technique to non-uniform grids to produce crack-free contour surfaces.We conclude by discussing otherpossible extensions and applications.2Marching Cubes and Look-up TablesMarching Cubes is a popular algorithm for extractinga polygonal contour from volumetric data sampled ona uniform3D grid.For each cell on the grid,the edgesintersected with the iso-surface are detected from signsat cell corners.The algorithm then forms triangles byconnecting intersections on those edges(referred to asedge intersections hereafter).To speed up the process,ituses a look-up table that establishes triangulations foreach sign configuration.Since there are8corners in acell,the look-up table contains256entries,four of whichare shown infigure2.Using the look-up table,the Marching Cubes algorithmcontours a cell in two steps:1.Look up the triangulation in the table by the signconfiguration,2.For each triangle,compute the exact location of eachvertex(edge intersection)from values at the cell cor-ners by linear interpolation.The Marching Cubes algorithm is fast because it uses ta-ble look-up to build polygonal contours.Unfortunately,the contoured surface generated by the original look-uptable in[7]may contain holes,since the triangular con-tour within each cell is not always consistent with thatof the neighboring cells(figure3).Although this problem wasfixed in later work,it re-veals another drawback of manually created tables.Theentries in the Marching Cubes’look-up table are con-structed by identifying15topologically distinct sign con-figurations and triangulating each case by hand.The lackof automation makes it susceptible to errors and diffi-cult to adapt to other polyhedrons.As we shall see,thelook-up tables used in convex contouring are constructedalgorithmically based on the topology and geometry ofgiven polyhedrons,and therefore minimizes possible er-rors.Convex3Fig.3Two the Marching Cubes topology.3Convex Contouring Using Look-up Tables The goal of convex contouring is to extract polygonal contours that enclose convex negative spaces within each cell.In this section,we will introduce the concept of con-vex contours and describe the proposed polygonization technique based on a pre-computed look-up table.Ex-amples of convex contouring will be presented together with performance comparison with the Marching Cubes algorithm.3.1Convex contourAssuming that the underlying implicit function is trilin-ear inside each cell,the convex hull of the negative space in a cell is the convex hull of all negative cell corners and edge intersections.The convex contour is the part of this convex hull that lies interior to the cell.In 2D,for exam-ple,the convex contour consists of interior line segments connecting edge intersections (i.e.,dashed lines in fig-ure 1left).In 3D,the convex contour consists of interior triangles whose vertices are edge intersections (figure 4left).Together with the triangles that fill the negative regions on cell faces (figure 4right),they constitute the convex hull of the negative space inside thecell.Fig.4Convex contour on the convex hull of the negative space.Note that the convex contour in a cell is outlined by linear convex contours on the faces of the cell (high-lighted in figure 4).Since the linear convex contour in a2D square is uniquely determined given the signs at the 4corners (allowing movement of the edge intersections along the edges),the polygonal convex contours from neighboring 3D cells always share the same linear con-tour on the common face.Hence convex contours always form topologically consistent isosurfaces.In figure 5,we show the convex contours for the same cells from figure 2.In comparison,we observe that the convex contour always encloses a connected,convex neg-ative space within the cell,whereas the contour from the Marching Cubes algorithm does not.Note that a convex contour is sometimes composed of multiple connected components,as shown in the rightmost cell of figure 5.Each of these connected piece of the contour is called a patch ,which may contain multiple holes (such as the center left cell in figure 5).Each hole on the patch is surrounded by a ring of linear convex contours that can be detected by the signs at the corners.Hence a look-up table for patch boundaries can be constructed automat-ically for each sign configuration.3.2Triangulation and Decision treesUnfortunately,although the boundary of the patches on the convex contour is unique for each sign configuration,the actual polygonization is not.In fact,different scalar values at cell corners,which determine the location of edge intersections,may modify the shape of the convex hull and result in different triangulation of the convex contour.As illustrated in figure 6,two cells that share the same sign configuration,but with different scalars at cell corners,result in different triangulated convexcontours.Fig.6Triangulation in cells with different scalar values at corners.Edge intersections are indicted by gray dots.To determine the correct triangulation based on the lo-cation of edge intersections,one could apply a full-scale convex-hull algorithm to compute the convex hull of the negative space.However,such algorithms are too gen-eral for our purposes,since we want only the part of this convex hull that lies interior to the cell.Instead,we can take advantage of the fact that the topology of the boundary is known for each patch on the convex contour.In fact,we can construct a set S of all possible triangu-lations for each patch.For example,figure 6shows the4Tao Ju etal.Fig.5Convex contours in cells withonly two possible triangulations for the convex contour ofthat sign configuration,since the contour contains a sin-gle4-sided patch.According to Euler’s polygon divisionproblem[6],there are(2n−4)!(n−1)!(n−2)!ways to triangulate an−sided patch into n−2triangles.In fact,this size ofS can be further reduced if we realize that the verticesof these triangles are restricted tofixed cell edges,hencesome triangulations will never appear on the convex hullof negative space.We will discuss this process in detailwhen we describe how the look-up table is constructed.Now we can think of the triangulation problem as thefollowing:given the exact locations of the edge inter-sections,choose an appropriate triangulation from S sothat the triangles satisfy the convex hull property(i.e.,all edge intersections and negative corners lie on one sideof the triangle).Hence we need a fast method to differ-entiate the correct triangulation from others by lookingat the edge intersections.Assuming that triangles on theconvex contour face inside the convex hull of the nega-tive space,we can do this by the following4-point test:given four distinct edge intersections V1,V2,V3,V4,if V4lies on the front-facing side of the triangle(V1,V2,V3),then the inverted triangle(V1,V3,V2)does not belongto the convex contour(figure7left).Similarly,triangles(V1,V2,V4),(V2,V3,V4)and(V3,V1,V4)do not satisfythe convex hull property.Otherwise,by symmetry,weclaim that triangles(V1,V2,V3),(V1,V4,V2),(V2,V4,V3)and(V1,V3,V4)do not lie on the convex contour(figure7right).Note that if all vertices lie on the same plane,either choice can be made.V1V2V3V4V1V2V3V4Fig.7Four-point test with vertices V1,V2,V3,V4.Each4-point test on the edge intersections rules outthose from the set S of all possible triangulations thatcontain any of the four back-facing triangles.Since anytwo triangulations differ at least in the triangles sharedby one of the boundary edge,the correct triangulationcan be distinguished from every other triangulation in Sthrough appropriate4-point tests.For best performance,a decision tree can be built to distinguish each triangula-tion through a minimal set of tests.An example of sucha decision tree is shown infigure8for a5-sided patch.At each node,the remaining triangulations are shownand the4-point test is represented by indices of the fourvertices(the order is shown at the top left corner).If thefourth vertex lies on the front-facing side of the triangleformed by thefirst three vertices(in order),we take theleft branch.Otherwise,we follow the right branch.Theprocess stops at a leaf node,where a single triangulationisleft.2,4,5,13,4,5,12,3,4,52,3,5,11,2,3,412345Fig.8A decision tree using4-point test for5-sided patches.Since the construction of decision trees is based on theoriginal set S,they can be pre-computed and optimizedfor every patch in each sign configuration.As we shallsee,the maximum depth of all these decision trees is5and the average tree depth is1.88.In other words,thecorrect triangulation of the convex contour in a cubic cellcan be determined by performing a maximum of5point-face trials on the edge intersections,and on average nomore than2trials.3.3The look-up tableThe look-up table contains256entries,one for each signconfiguration of a cubic cell.In each entry,the look-uptable stores the decision trees computed for each patchConvex Contouring of Volumetric Data5 Fig.9Two screen shots of a real-time navigation application using a convexly contoured terrain.by traversing the nodes in the decision trees in pre-order. Each non-leaf node contains a4-point test,and each leaf node stores a triangulation.The edge intersections in4-point tests and triangulations are represented by indices of the edges on which they lie.Two example entries in this table are shown in table1,with their correspond-ing sign configurations and edge indexing drawn on the right.3.4Contouring by table look-upsIn comparison with the Marching Cubes algorithm,con-vex contouring extracts the polygonal contour in a cell in two steps:1.Look up the decision trees(one for each patch)in thetable by the signs at the cell corners,2.For each decision tree,perform4-point tests on spec-ified edge intersections until arriving at a single tri-angulation.Fig.10Convex contouring on volumetric data.Infigure10,two sets of volumetric data generated by scan-conversion of polygonal models are contoured us-ing the new method.Observe that the edges on the sur-face are manifold and the contour is crack-less.Since the negative space inside each non-empty cell is convex, collision detection can be localized into cells and there-fore become independent of the grid size.Figure9shows two screen shots of a real-time navigation program in which the movement of the viewer is confined within the negative space.The terrain is an iso-surface constructed using convex contouring on a256cubic grid.On a con-sumer level PC machine(dual1.5GHz processors with 2.5G memory),we achieved over2million point classifi-cations per second.As we mentioned before,the average number of tests used to determine triangulation for each patch is less than2.Hence we can perform convex contouring on vol-umetric data with speed comparable to the Marching Cubes algorithm.In table2,the performance of con-vex contouring is compared with that of the Marching Cubes for contouring the terrain infigure9on differ-ent grid sizes.We also compared the average number of triangles generated in each cell in both methods.Notice that convex contouring generates on average only about 2%more triangles than the Marching Cubes algorithm. These extra triangles are needed to preserve the convex-ity of the negative space.Grid Size Marching Cubes Convex Contouring 1283125ms141ms2563781ms907ms51232109ms2437msAvg.Triangles 3.181 3.257Table2Comparison of total contouring time and average number of triangles per cell in convex contouring and the Marching Cubes.6Tao Ju et al.Index Table Entry Cell Configuration171{1,9,12,7}→4-point test{{1,9,7},{9,12,7}}→Triangulation{{1,9,12},{1,12,7}}123456789101112125{1,3,6,12}→4-point test in parent node{1,12,10,2}→4-point test in left child{{1,3,12},{1,12,2},{3,6,12},{12,10,2}}{{1,3,12},{1,12,10},{1,10,2},{3,6,12}}{1,12,10,2}→4-point test in right child{{1,3,6},{1,6,12},{1,12,2},{12,10,2}}{{1,3,6},{1,6,12},{1,12,10},{1,10,2}}123456789101112Table1Two example entries in the look-up table.Each entry is a list of triangulations(each stored as a list of triangles) and4-point tests(each stored by the indices of the vertices)traversed from the decision tree in pre-roder.4Automatic Construction of Look-up TablesIn this section,we will review the table construction pro-cess in more detail.For a given sign configuration,we first detect the patch boundaries as a group of rings of linear contours.Then,for each patch,we construct the set of all possible triangulations that could take place on the convex hull of the negative space.Finally,an opti-mal decision tree is built for every patch detected on the contour.The look-up table can be found on the web at /jutao/research/contour tables/.4.1Detection of patch boundariesA patch on the convex contour in a cubic cell is bounded by linear convex contours on cell faces.These linear con-tours form single or multiple rings that surround the ”holes”of the patch.Since the linear convex contours are unique on each cell face for a given sign configura-tion,a single ring can be constructed using the following tracing strategy:starting from a cell edge that exhibits a sign change(where an edge intersection is expected) and facing the positive end,look for the next edge with a sign change by turning counter-clockwise on the face boundary.Repeat the search process until it returns to the starting edge,when a closed ring is formed(seefigure 11).Notice that face-tracing produces oriented linear convex contours on each cell face.Each linear contour on the cell face is directed so that the negative region on that face lies to its left when looking from outside.There-fore the triangles on the convex contour of the cell that share these linear contours will face towards the nega-tive space.The orientation of the rings are importantfor linear contours already built,and dashed arrows indicate the tracing route.determining the set of possible triangulations that share the same patch boundary.Similar tracing techniques have been described by nu-merous authors in[2],[9],[13],in which convexity of the negative region on each cell face is preserved.These algo-rithms construct a single ring for each patch boundary. However,the problem remains on how to group multiple rings to form the boundary of a multiple-genus patch (such as the center left cell infigure5).Although such patches arise in only4cases among256sign configura-tions,they may appear much more often in other non-cubic cells(such as transition cells in multi-resolution grids,see Section6).We need to be able to identify these cases automatically from the sign configuration and group the rings appropriately.By definition,a patch is a continuous piece on the con-vex hull of negative space.Hence it also projects onto a continuous piece of regions on the cell faces.These regions are positive areas that surround positive cor-Convex Contouring of Volumetric Data7ners connected by cell edges.Therefore the boundary of each patch on the convex contour isolates a group of positive corners that are inter-connected by cell edges. The previous face-tracing algorithm could be modified so that rings constructed around a same edge-connected component of positive corners are grouped to form the boundary of a single patch.This rule is demonstrated in figure12.In the top left cell,two rings of linear contours form the boundary of two patches,due to the presence of two isolated positive corners.In the top right cell,where there is only one edge-connected component of positive corners,the two rings are grouped to form the bound-ary of a single cylinder-like patch.The connectivity of the positive corners in these two cells are illustrated at the bottom offigure12.In contrast,face-tracing without ring-grouping would give the same result in both cells, thus violating the convex hull property in the secondcell.Fig.lighted)to form boundaries of patches.Positive corners are colored gray.Bottom:Connectivity graph of positive corners 4.2Pre-triangulation of Convex ContourThe set of possible triangulations for a patch with an oriented boundary topology can be enumerated by re-cursive algorithms.However,this often results in redun-dant triangulations that never appear on the convex con-tour.For example,the genus-2patch in the center left cell infigure5can be triangulated in only one way on the convex hull of the negative space,regardless of the magnitudes of scalar values at the corners.In contrast, brute-force enumeration would return21possible trian-gulations for an arbitrary genus-2patch with two trian-gular holes.The key observation is that,the patches on the convex contour are not arbitrary patches,their ver-tices(edge intersections)are restricted tofixed edges on the cell.These spacial restrictions limit the number of possible triangulations that could occur on the convex contour.For fast polygonization at run-time,we hope to pre-triangulate each patch as much as possible during table construction,based only on the sign configuration. By the convex hull property,the half-space on the front-facing side of a triangle on the convex contour must con-tain(or partially contain)every other cell edge that ex-hibits a sign change.Note that the three vertices of the triangle can move only along threefixed cell edges,this half-space is always contained in the union of the half-spaces formed when the three vertices are at the ends of their cell edges.Hence we have a way to identify triangles that will not appear on the convex contour:given three cell edges(C1,C2),(C3,C4)and(C5,C6)(C i are cell cor-ners),construct border triangles,i.e.,triangles formed by one end of each edge in order(such as(C1,C3,C5)).If there is an edge on the cell exhibiting a sign change that lies completely to the back of all non-degenerate border triangles,any triangle whose vertices belong to these three edges(in order)will not lie on the convex con-tour.This idea is illustrated infigure13.The highlighted cell edge on the left exhibits a sign change,and lies to the back of all the border triangles constructed from the three dashed edges(E1,E2,E3).Hence the dashed trian-gle formed by intersections on those edges never appears on the convex contour.In contrast,the highlighted cell edge on the right lies partially to the front of at least one of the border triangles formed by the edges(E1,E2,E3), hence the dashed triangle may exist in the triangulation of the convex contour.E1E2E3E1E2E3Fig.13Identifying triangles that do not lie on the convex contour.By eliminating triangulations that contain these ineli-gible triangles,we can trim down the space of possible triangulations.For example,the number of remaining triangulations for thefirst three cells infigure5are re-spectively4,1and4.4.3Construction of decision treesEven after pre-triangulation,some patches still have many potential triangulations on the convex hull of the nega-tive space.To speed up the polygonization at run-time,8Tao Ju et al.we can pre-compute a set of4-point tests on the vertices of the patch(edge intersections)to distinguish between the remaining triangulations.These tests can be orga-nized in a decision tree structure,introduced in the last section.Different sets of tests result in differently shaped decision trees.To obtain optimal performance,we imple-ment a search algorithm that looks for the optimal set of tests that produces a decision tree with the small-est depth.Since each of the two outcomes of a single test eliminates a non-intersecting subset of the remain-ing triangulations,the minimal depth of the correspond-ing decision tree is lower bounded by log2N,where N is the total number of triangulations.For example,the depth of an optimized decision tree for a patch of length 4,5and6are1,3and5respectively.Further computa-tion reveals that the maximum length of a patch(which can not be pre-triangulated)in a cubic cell is6;hence any patch can be triangulated within5point-face trials on thefly by walking down the pre-computed decision tree.On average,however,it only takes1.88tests to de-termine the triangulation of a patch,due to infrequent occurrence of large patches and the reduced triangula-tion space as a result of pre-triangulation.5Multi-resolution Convex ContouringIn volume visualization,the number of polygons gener-ated by uniform contouring easily exceeds the capacity of modern hardware.For real-time applications,it is often advantageous to display the geometry at different lev-els of detail depending on the distance from the viewer. This technique has the advantage that it speeds up the rendering process without sacrificing much visual accu-racy.By using a view-dependent approach,the grid is contoured at different resolutions depending on the dis-tance from the navigator.In particular,we can create a series of nested bounding boxes centered at the viewer, with the grid resolution decreasing by a factor of2.A2D example of this multi-resolution framework is shown infigure14left,in which a circle is contoured using cell grid at two different resolutions.When the coarse cells at the top meet thefine cells at the bottom,the con-tour in the coarse cells need to be consistent with the contour from the neighboringfine cells on the common edges.We call these coarse cells transition cells,which are adjacent to cells at afiner resolution.A2D transition cell thus hasfive corners andfive edges,as shown in the middle offigure14.By connecting edge intersections on each cell edge,the transition cells can be contoured in a way similar to a regular4-corner cell,yielding consistent contours with the adjacentfine cells.Some of the con-toured example are shown infigure14right.Notice that the convexity of the negative region is still preserved in each transition cell.In3D,a transition cell between two resolutions is either adjacent to twofine cells on an edge,or adjacent to four fine cells on a face(seefigure15left).These two types of cells can be regarded as convex polyhedrons with9 corners(figure15center)and13corners(figure15right) respectively.Since the previous discussion on regular cells applies to any convex polyhedron,we can also build look-up ta-bles and perform convex contouring on these transition cells.In this way,crack-free surfaces can be contoured on nested grids within the same framework as uniform contouring.5.1Convex contours in transition cellsAs in a regular cell,the convex contour inside a tran-sition cell is outlined by the linear contours on the cell faces.Since the linear convex contour is unique on each face for a given sign configuration,the boundary of patches on the convex contour can be pre-computed using the proposed face-tracing algorithm.At the top offigure16, the oriented boundaries of patches in different transition cells are detected and drawn as dashed arrows.Since con-vex contours from neighboring cells in a multi-resolution grid always share the same linear contour on the com-mon face as their boundaries,topological consistency is preserved everywhere on the contouredsurface.Fig.16Patch boundaries(top)and triangulation(bottom) in three transition cells.By pre-computing optimal decision trees for each patch, the triangulation can be determined by applying succes-sive4-point tests on the edge intersections.At the bot-tom offigure16,patches detected from the cells on the top are triangulated on the convex hull of the negative space.However,due to the presence of four co-planar faces on a13-corner cell,this convex hull could degener-ate onto a plane(figure17left).To determine the correct triangulation of the convex contour on the degenerate convex hull,we introduce an outward perturbation to。

Machine Vision and Applications (2000) 12: 16–22机器视觉与应用（2000）12:16-22Machine Vision and Applications©Springer-Verlag 2000机器视觉与应用©施普林格出版社2000Andrea Fusiello1, Emanuele Trucco2, Alessandro Verri31 Dipartimento Scientifico e Tecnologico, Universita d i Verona, Ca’ Vignal 2, Strada Le Grazie, 37134 Verona, Italy; e-mail: fusiello@sci.univr.it `2 Heriot-Watt University, Department of Computing and Electrical Engineering, Edinburgh, UK3 INFM, Dipartimento di Informatica e Scienze dell’Informazione, Univ ersita di Genova, Genova, ItalyReceived: 25 February 1999 / Accepted: 2 March 2000收稿日期：1999年2月25日/接受日期：2000年3月2日Abstract. We present a linear rectification algorithm for general, unconstrained stereo rigs. The algorithm takes the two perspective projection matrices of the original cameras,and computes a pair of rectifying projection matrices. It is compact (22-line MATLAB code) and easily reproducible.We report tests proving the correct behavior of our method,as well as the negligible decrease of the accuracy of 3D reconstruction performed from the rectified images directly.摘要：我们在本篇文章中阐述一个用于通用的不加约束的立体视觉设备的线性修正算法。

Student’s Name:Student’s ID No.:College Name:The study of QuaternionsAbstractFinding the definition of quaternions, operations of quaternions, and properties of quaternions. To discuss the problem if the set of quaternions together with the operations of quaternions is a vector space over the real number field. To discuss the problem if the set of quaternions together with the operations of quaternions is a field.IntroductionSearch the definition of quaternions, and discuss some properties of them. Then discuss the applications used by quaternions.Main ResultsAnswers of Q11.1The definition of quaternion:Quaternion is the most simple hyper-complex number. The complex is composed of a real plus the elements of I, including i^2=-1. Similarly,quaternion is composed of real number plus three elements I, J, K, and they have the following relationship: i^2=j^2=k^2=ijk=-1, $four each number is a linear combination of 1, I, J and K, that is quaternion it can be expressed as a+bi+cj+dk, where a, B, C, D is a real number.]1[1.2Operations of quaternion1)Quaternion addition:p+qWith complex numbers, vectors and matrices, the sum of two quaternion need to combine different elements together.The addition follows the commutative and associative laws of real and complex number.2) Quaternion multiplication:pqBetween two to quaternion in the number of non-commutative product usually is Glassman (Hermann Grassmann) is called the product, the product above has been briefly introduced, complete type it is:Because of quaternion multiplication can not be changed , pq is not equal to qp. Glassman product used in the description of many other algebraic function. The vector product is part of qp:3)Quaternion dot product: p · qThe dot product is called the Euclidean inner product, quaternion dot productis equivalent to a four-dimensional vector dot product. The dot product value is the corresponding element numerical value of each element in the p and q . This is between quaternion can change the product number, and returns a scalar.The dot product can use Glassman product form:This product is useful for the elements of isolated from quaternion . For example, i can come out from p extraction:4)Quaternion outer product: Outer(p,q)The Euclidean outer product is not commonly used; However, because the outerproduct and the product form of the Glassmaninner product similarity, they are always to be mentioned:5) Quaternion even product: Even(p,q)Quaternion even product is not commonly used, but it will be mentioned, because of its similar with odd product. It is a pure symmetric product; therefore, it is completely interchangeable.6) Quaternion cross product: p × q Quaternion cross product also known as odd product. It is equivalent to the cross product of vectors , and only return one vector value:7) Quaternion transposition:1-pQuaternion transposition’s definition is by 11=-p p . The same way to constructcomplex inverse structure:A quaternion itself dot multiplication is a scalar. quaternion divided by a scalar is equivalent to the scalar multiplication on the countdown, but to make every element of the quaternion is divided by a divisor.8) Quaternion division: pp1-Quaternion’s unchangeable property lead to the difference of qp1-and pq1-. This means that unless the p is a scalar, otherwise you cannot use the q/p.9) Quaternion Scalar Department:Scalar(p)10) Quaternion vector department:Vector(p)11) Quaternion Modulus: |p|12)Quaternion signal number:Sgn(p)13)Quaternion argument:Argu(p)1.3 Properties of quaternionQuaternion is shaped like a number of ai+bj+ck+d, a, b,c,d is a real number.Answers of Q22. There are two ways to the matrix representation of quaternion.]2[Just as complex numbers can be represented as matrices, so can quaternions. There are at least two ways of representing quaternions as matrices in such a way that quaternion addition and multiplication correspond to matrix addition and matrix multiplication. One is to use 2 × 2 complex matrices, and the other is to use 4 × 4 real matrices. In each case, the representation given is one of a family of linearly related representations. In the terminology ofabstract algebra, these are injective homomorphisms from H to the matrix rings M(2, C) and M(4, R), respectively.Using 2 × 2 complex matrices, the quaternion a + bi + cj + dk can be represented asThis representation has the following properties:∙Constraining any two of b, c and d to zero produces a representation of complex numbers. For example, setting c = d = 0 produces a diagonal complex matrix representation of complex numbers, and setting b = d = 0 produces a real matrix representation.∙The norm of a quaternion (the square root of the product with its conjugate, as with complex numbers) is the square root of the determinant of the corresponding matrix.[20]∙The conjugate of a quaternion corresponds to the conjugate transpose of the matrix.∙By restriction this representation yields a isomorphism between the subgroup of unit quaternions and their image SU(2). Topologically, the unit quaternions are the 3-sphere, so the underlying space of SU(2) is also a 3-sphere.The group SU(2) is important for describing spin in quantum mechanics; see Pauli matrices.Using 4 × 4 real matrices, that same quaternion can be written asIn this representation, the conjugate of a quaternion corresponds to the transpose of the matrix. The fourth power of the norm of a quaternion is the determinant of the corresponding matrix. As with the 2 × 2 complex representation above, complex numbers can again be produced by constraining the coefficients suitably; for example, as block diagonal matrices with two 2 × 2 blocks by setting c = d = 0.Answers of Q3Because the vector part of a quaternion is a vector in R3, the geometry of R3 is reflected in the algebraic structure of the quaternions. Many operations on vectors can be defined in terms of quaternions, and this makes it possible to apply quaternion techniques wherever spatial vectors arise. For instance, this is true in electrodynamics and 3D computer graphics.For the remainder of this section, i, j, and k will denote both imaginary[18] basis vectors of H and a basis for R3. Notice that replacing i by −i, j by −j, and k by −k sends a vector to its additive inverse, so the additive inverse of a vector is the same as its conjugate as a quaternion. For this reason, conjugation is sometimes called the spatial inverse.]3[Choose two imaginary quaternions p = b1i + c1j + d1k and q = b2i + c2j + d2k. Their dot product isThis is equal to the scalar parts of pq∗, qp∗, p∗q, and q∗p. (Note that the vector parts of these four products are different.) It also has the formulasThe cross product of p and q relative to the orientation determined by the ordered basis i, j, and k is(Recall that the orientation is necessary to determine the sign.) This is equal to the vector part of the product pq (as quaternions), as well as the vector part of −q∗p∗. It also has the formulaIn general, let p and q be quaternions (possibly non-imaginary), and writewhere p s and q s are the scalar parts, and and are the vector parts of p and q. Then we have the formulaThis shows that the noncommutativity of quaternion multiplication comes from the multiplication of pure imaginary quaternions. It also shows that two quaternions commute if and only if their vector parts are collinear.For further elaboration on modeling three-dimensional vectors using quaternions, see quaternions and spatial rotation. A possible visualisation was introduced by Andrew J. Hanson.Answers of Q41）Application of quaternions in the attitude of a rigid body simulation With symmetric gyroscope as an example, discusses the existing application and the quaternions in the attitude of a rigid body simulation problem in. That attitude with quaternions description has a solution quickly, won't appear singular advantages, but implied quaternions equation constraint is differential forms, which lead to a strict limit on the simulation time step, which limits its application in a certain extent. Finally discusses the implementation of attitude description uniqueness problem with quaternions, and put forward the concept of "standard" quaternions.]4[2）Application of unit quaternions in aerial photo-grammetry solution Research on unit quaternions method in aerial application of aerial triangulation in each step of the algorithm, and the stability and applicability is evaluated.The first describes the method of unit quaternions tectonic rotation matrix based on relative orientation, establishing model and based on the number of units quaternions settlement method for the model is constructed based on the beam method; regional network unit quaternions rientation and bundle block adjustment test, and with the traditional Euler angle to construct the rotation matrix based schemes are compared. The test results show that, in the relative orientation test, if take P-H algorithm, which requires only minimal control points to ensure that all test data can obtain the correct solution. While in the bundle adjustment method, method of unit quaternions than the traditional method based onthe number of stability is poor, the number of image scale and control points are more sensitive, causing part of the test data can not be correct convergence.]5[Conclusion and AcknowledgementThrough the research of learning, I learned the basic concepts of quaternions and some operational properties. At the same time also learned about the quaternions in many different areas of application.References[2]See Hazewinkel et al. (2004), p. 12.[3]Conway, John Horton; Smith, Derek Alan (2003). On quaternions and octonions: their geometry, arithmetic, and symmetry. p. 9. ISBN 1-56881-134-9.[4]Girard, P. R. The quaternion group and modern physics (1984) Eur. J. Phys. vol 5,。