A frequency domain technique for range data registration

This work introduces an original method for registering pairs of 3D views consisting of range data sets which operates in the frequency domain. The Fourier transform allows the decoupling of the estimate of the rotation parameters from the estimate of the translation parameters, our algorithm exploits this well-known property by suggesting a three-step procedure. The rotation parameters are estimated by the first two steps through convenient representations and projections of the Fourier transforms' magnitudes and the translational displacement is recovered by the third step by means of a standard phase correlation technique after compensating one of the two views for rotation. The performance of the algorithm, which is well-suited for unsupervised registration, is clearly assessed through extensive testing with several objects and shows that good and robust estimates of 3D rigid motion are achievable. Our algorithm can be used as a prealignment tool for more accurate space-domain registration techniques, like the ICP algorithm.     

An accurate and fast point-to-plane registration technique

This paper addresses a registration refinement problem and presents an accurate and fast point-to-(tangent) plane technique. Point-to-plane approach is known to be very accurate for registration refinement of partial 3D surfaces. However, the computation complexity for finding the intersection point on a destination surface from a source control point is hindering the algorithm from real-time applications. We introduce a novel point-to-plane registration technique by combining the high-speed advantage of point-to-projection technique. In order to find the intersection point fast and accurately, we forward-project the source point to the destination surface and reproject the projection point to the normal vector of the source point. We show that iterative projections of the projected destination point to the normal vector converge to the intersection point. By assuming the destination surface to be a monotonic function in a new 2D coordinate system, we show contraction mapping properties of our iterative projection technique. Experimental results for several objects are presented for both pair-wise and multi-view registrations.     

Surface area estimation of digitized 3D objects using quasi-Monte Carlo methods

A novel and efficient quasi-Monte Carlo method for estimating the surface area of digitized 3D objects in the volumetric representation is presented. It operates directly on the original digitized objects without any surface reconstruction procedure. Based on the Cauchy-Crofton formula from integral geometry, the method estimates the surface area of a volumetric object by counting the number of intersection points between the object's boundary surface and a set of uniformly distributed lines generated with low-discrepancy sequences. Using a clustering technique, we also propose an effective algorithm for computing the intersection of a line with the boundary surface of volumetric objects. A number of digitized objects are used to evaluate the performance of the new method for surface area measurement.     

Hidden Octree Node Removal as a Pipeline Process

A processing pipeline solution to the generation and display of octree encoded 3-D objects is described. Particular emphasis is given to an algorithm which removes that part a of linear octree code which describes parts of the object which are invisible from a prescribed viewing position. The scope of the algorithm is restricted to viewing directions which are parallel to the Cartesian axes and to orthogonal projections. The algorithm is specifically designed to operate as a single stage within a pipeline of processes.     

增量式精确多面体可见外壳

提出一种新的增量式计算精确多面体可见外壳的算法IEPVH。首先,在新视图的图像平面,计算旧可见外壳的边被新光椎切割得到的交点。然后,恢复旧可见外壳的边上交点的局部方向信息并同时获得新光椎边上的交点。接着,恢复新光椎边上交点的局部方向信息。最后,新可见外壳的多边形面片通过一次遍历网格的边的过程被识别出来,并为了便于显示而被划分为三角面片。与EPVH等其他算法相比,IEPVH不但能够让用户更多地参与基于图像3维重建的过程,而且具有空间计算复杂度小。实验证明此算法的高效和鲁棒性。IEPVH的特点使其更易于在移动设备中得到应用。     

Constructing a wire-frame from views on arbitrary view planes for objects with conic sections inclined to all view planes

A new and efficient approach to construct a 3D wire-frame of an object from its orthographic projections is described. The input projections can be two or more and can include regular and complete auxiliary views. Each view may contain linear, circular and other conic sections. The output is a 3D wire-frame that is consistent with the input views.The approach can handle auxiliary views containing curved edges. This generality derives from a new technique to construct 3D vertices from the input 2D vertices (as opposed to matching coordinates that is prevalent in current art). 3D vertices are constructed by projecting the 2D vertices in a pair of views on the common line of the two views. The construction of 3D edges also does not require the addition of silhouette and tangential vertices and subsequently splitting edges in the views. The concepts of complete edges and n-tuples are introduced to obviate this need. Entities corresponding to the 3D edge in each view are first identified and the 3D edges are then constructed from the information available with the matching 2D edges. This allows the algorithm to handle conic sections that are not parallel to any of the viewing directions. The localization of effort in constructing 3D edges is the source of efficiency of the construction algorithm as it does not process all potential 3D edges.Working of the algorithm on typical drawings is illustrated.     

二维概念格图形的三维重构研究

介绍了二维概念格图形向三维空间转化和延伸的必要性和现状。通过对传统概念格图形分层定位布局方法的研究与分析,提出并实现了一种新的以具有大量的平行四边形和有向线段为基本特征的概念格在三维空间的自动布局算法,描述了一种基于该算法的二维概念格图形的三维重构机制,有效地解决了节点横向过度扩张的问题并减少了线段交叉,较好地实现了复杂概念格图形的三维可视化,为知识发现和知识处理提供了良好的基础。     

Implementation of two hidden-line algorithms

Two hidden-line elimination programs are described. One removes the hidden lines from vector-type projections of planar-faced 3D objects. This program implements the Loutrel algorithm which has been extended here to solids with multiply-connected faces. The other is applicable to solids bounded by sections of quadric surfaces (i.e. cylinders, cones, spheres, ellipsoids, paraboloids and hyperboloids) and represents an implementation of the Woon algorithm. The latter can be regarded as an extension of the Loutrel algorithm to curved-surface bodies. Both programs generate true, visible-line perspective projections for output on a digital plotter or a vector-type CRT display. The implementation of these algorithms for a variety of computer systems is described.     

A complete and extendable approach to visual recognition

A framework for 3D object recognition is presented. Its flexibility and extensibility are accomplished through a uniform, parallel, and modular recognition architecture. Concurrent and stacked parameter transforms reconstruct a variety of features from the input scene. At each stage, constraint satisfaction networks collect and fuse the evidence obtained through the parameter transforms, ensuring a globally consistent interpretation of the input scene and allowing for the integration of diverse types of information. The final interpretation of the scene is a small consistent subset of the many initial hypotheses about partial features, primitive features, feature assemblies, and 3D objects computed by the various parameter transforms. A complete, integrated, and implemented system that extracts planar surfaces, patches of quadrics of revolution, and planar intersection curves of these surfaces from a depth map viewing 3D objects is described. Experimental results on the recognition behavior of the system are presented     

Inverse Displacement Mapping in the General Case

Inverse Displacement Mapping is a form of displacement mapping which allows the ray tracing of displacement mapped surfaces. The technique performs all calculations in the inverse (parametric) space of the surface thus avoiding the need to explicitly model the complex three dimensional geometry. This produces a compact and general algorithm, Only when the solution, in parametric space, has been determined is it transformed back to 3D space. The algorithm works by projecting the ray into the parametric space of the surface. This ray is then split into a series of segments, each of which can be efficiently handled to calculate the intersection points. The algorithm presented here has been used to ray trace displacement mapped objects from a variety of underlying surface types.     

Physical sketching: Reconstruction and analysis of 3D objects from freehand sketches

When designing a 3D object, designers, engineers and teachers often begin investigating potential design tradeoffs by creating informal sketches. Ideally, these sketches-in combination with a variety of engineering analysis tools-would allow prediction of the object’s physical properties, especially those that affect the critical early design process. We introduce a pen-based system that reconstructs 3D spatial geometry from a single 2D freehand-sketch consisting of straight and curved lines in interactive time. Several optimization-based approaches to this problem have been proposed, but these generally have difficulty converging to an acceptable solution because the dimensionality of the search space is large. The primary contribution of this paper is a new reconstruction algorithm for orthographic projections of 3D wireframes. The algorithm reconstructs the depths of each vertex by exploiting geometric regularities among the graph lines in a reduced solution space, then optimizes a cost function over this space to recover the vertex depths. A second optimization algorithm is used to infer the 3D geometry of curved strokes once the vertex depths have been recovered. The proposed approach can recover the geometry of several objects with approximately 50 curved strokes in near interactive time. We also present an iterative, Tablet-PC-based design system that uses the proposed reconstruction algorithm to recover 3D objects from 2D orthographic sketches. The system allows the reconstructed objects to be subjected to two types of physical analysis, the results of which are superimposed directly on the sketch: a fast, kinematic simulation, and a complete finite-element-based static analysis. The object can quickly be modified in place using the pen-based interface according to the results of the analysis to allow for iterative design work. We demonstrate the system in action on a variety of early-stage design analyses.     

基于直线段提取及其参数化的矩形重构方法研究

文章根据矩形目标边缘二值图的特点,提出一种基于直线段提取及其参数化的矩形目标重构方法,实现矩形目标位姿参数高精度快速求取。该文提出的矩形目标重构方法主要分两步进行:首先从矩形目标边缘图像的二值图中提取出所有直线段,并将直线段参数化;其次由参数化的直线段提取出近似矩形,再由近似矩形重构出精确的目标矩形,并计算其位姿参数。该文提出的算法可应用于机器人装配及目标跟踪中。     

Three-dimensional reconstruction from serial sections in PC-Windows platform by using 3D_Viewer

Three-dimensional (3D) reconstruction from serial sections allows identification of objects of interest in 3D and clarifies the relationship among these objects. 3D_Viewer, developed in our laboratory for this purpose, has four major functions: image alignment, movie frame production, movie viewing, and shift-overlay image generation. Color images captured from serial sections were aligned; then the contours of objects of interest were highlighted in a semi-automatic manner. These 2D images were then automatically stacked at different viewing angles, and their composite images on a projected plane were recorded by an image transform-shift-overlay technique. These composition images are used in the object-rotation movie show. The design considerations of the program and the procedures used for 3D reconstruction from serial sections are described. This program, with a digital image-capture system, a semi-automatic contours highlight method, and an automatic image transform-shift-overlay technique, greatly speeds up the reconstruction process. Since images generated by 3D_Viewer are in a general graphic format, data sharing with others is easy. 3D_Viewer is written in MS Visual Basic 6, obtainable from our laboratory on request.     

Feature-Based Object Recognition and Localization in 3D-Space,Using a Single Video Image

We introduce a robust algorithm to recognize objects in 3D space from one 2D video image and to localize the objects in all six degrees of freedom. Point-like attached features are used in the input image and additional edge information provides grouping. In an initial phase, a 3D model of all objects to be recognized is stored in the computer represented by their features. Combining the location of the detected features in the 2D input scene with the features of the 3D computer model, each single feature gives a subspace as possible solutions of the location parameters to be determined. The points of intersection of the corresponding trajectories are accumulated as possible solutions in a Hough table. The location of the highest peak in the space of hypothetical solutions delivers the desired rotation and translation parameters, even for partially hidden objects. The fully analytical algorithm is adapted to weak perspective (orthographic and scale) as well as to perspective projection. An application to range images leads to the automated feature modeling of the required 3D reference objects.     

Tomographic Reconstruction of 3D Objects Using Marked Point Process Framework

For reconstructing sparse volumes of 3D objects from projection images taken from different viewing directions, several volumetric reconstruction techniques are available. Most popular volume reconstruction methods are algebraic algorithms (e.g. the multiplicative algebraic reconstruction technique, MART). These methods which belong to voxel-oriented class allow volume to be reconstructed by computing each voxel intensity. A new class of tomographic reconstruction methods, called “object-oriented” approach, has recently emerged and was used in the Tomographic Particle Image Velocimetry technique (Tomo-PIV). In this paper, we propose an object-oriented approach, called Iterative Object Detection—Object Volume Reconstruction based on Marked Point Process (IOD-OVRMPP), to reconstruct the volume of 3D objects from projection images of 2D objects. Our approach allows the problem to be solved in a parsimonious way by minimizing an energy function based on a least squares criterion. Each object belonging to 2D or 3D space is identified by its continuous position and a set of features (marks). In order to optimize the population of objects, we use a simulated annealing algorithm which provides a “Maximum A Posteriori” estimation. To test our approach, we apply it to the field of Tomo-PIV where the volume reconstruction process is one of the most important steps in the analysis of volumetric flow. Finally, using synthetic data, we show that the proposed approach is able to reconstruct densely seeded flows.     

3D face reconstruction using images from cameras with varying parameters

In this paper, we present a new technique of 3D face reconstruction from a sequence of images taken with cameras having varying parameters without the need to grid. This method is based on the estimation of the projection matrices of the cameras from a symmetry property which characterizes the face, these projections matrices are used with points matching in each pair of images to determine the 3D points cloud, subsequently, 3D mesh of the face is constructed with 3D Crust algorithm. Lastly, the 2D image is projected on the 3D model to generate the texture mapping. The strong point of the proposed approach is to minimize the constraints of the calibration system: we calibrated the cameras from a symmetry property which characterizes the face, this property gives us the opportunity to know some points of 3D face in a specific well-chosen global reference, to formulate a system of linear and nonlinear equations according to these 3D points, their projection in the image plan and the elements of the projections matrix. Then to solve these equations, we use a genetic algorithm which consists of finding the global optimum without the need of the initial estimation and allows to avoid the local minima of the formulated cost function. Our study is conducted on real data to demonstrate the validity and the performance of the proposed approach in terms of robustness, simplicity, stability and convergence.     

Simulation Studies For The Performance Analysis Of The Reconstruction Of A Line In 3-D From Two Arbitrary Perspective Views Using Two Plane Intersection Method

Objects in nature as well as man made are bound by planar as well as curvilinear surfaces. Hence the reconstruction process of three dimensional objects involves obtaining the geometrical attributes of these planar and curvilinear surfaces, lines, points etc. If a line in 3-D space is viewed from two arbitrary positions, two different images of the same line are obtained. The correspondence between this pair of projections of the line is assumed to be established in this work. The work presented in this paper describes a method of reconstruction of a line in 3-D as an intersection of two planes containing the respective projected line images. The parameters of the line in 3-D space are obtained from the parameters of projected images of the line. Relevant mathematical formulations and analytical solutions for obtaining the parameters of the reconstructed line are given. The effect of noise in the reconstruction and the efficiency of the described reconstruction methodology are studied by simulation studies.     

利用简化9交模型进行三维拓扑分析

针对点、线、面和体等简单空间对象提出新的否定规则，对9交模型进行了简化．利用简化后的9交模型，仅需分析4组相交关系即可得出实际拓扑关系．在此基础上构建了拓扑关系推导表，可进一步分析复合空间对象之间的拓扑关系，并以线与体之间拓扑关系为例讨论了算法实现．与已有的算法相比，该算法能分析更为复杂的空间对象之间的拓扑关系．     

Virtual viewpoints reconstruction via Fourier slice transformation

We propose a new method of calculating the arbitrary viewpoints for auto‐stereoscopic display. The three‐dimensional (3D) object is first virtually reconstructed in 3D spaces by mapping each pixel with a depth according to the depth mapping. We then calculate the Fourier spectrum of the 3D object by the fast Fourier transformation. The arbitrary viewpoints are reconstructed by “slicing” the 3D Fourier spectrum. To repair “black hole” artifacts, the regions in the background are calculated by advanced boundary in‐painting. Experimental results show the effectiveness and accuracy of the proposed algorithm to calculate viewpoints with arbitrary viewing angles. A comparison is also presented, which indicates that the proposed algorithm is more accurate than conventional method, and the advanced boundary in‐painting can save three quarters of time than the conventional in‐painting method.     

Approximation of displacement fields using wavefront region growing

This paper presents a novel approach for the computation of displacement fields along contours which correspond to moving homogeneous regions in an image sequence. Individual frames of the image sequence are treated one at a time by performing segmentation and 2D motion analysis simultaneously. For the first frame, an original segmentation of the image into disjoint regions is assumed to be given in the form of pixel markings and the properties of these regions. The analysis of each new frame consists of (a) finding the new segmentation and (b) a set of displacement vectors that link corresponding points on the original and the new contour. The new region is assumed to overlap with the original region, such that their intersection is not empty. After finding the intersection, wavefront region growing is applied to obtain the new region and to compute a set of tentative displacement vectors. The final approximation is found by using a relaxation-type algorithm which “rotates” the mapping between the original and the new boundary until a correspondence with minimum deformation is found. The proposed algorithm is simple and lends itself to parallel implementation. Various examples are presented to illustrate the approach.