Search

Most 3-D laser scanners are based on 3-D optical triangulation algorithms, where the location of each 3-D point is estimated as the intersection of a camera ray and a plane of light projected by a laser line generator. Since a physical laser-line generator projects a sheet of light of finite thickness, inaccurate measurements and errors result from assuming that the plane of light is infinitesimally thin. We propose a new mathematical formulation for 3-D optical triangulation based on interval arithmetic, where 3-D points are only determined within certain bounds along the camera rays, and multiple measurements are used to tighten these bounds. We propose the line segment cloud as an alternative surface representation to visualize the measurement errors within the proposed framework. We introduce the iterative line segment tightening algorithm to convert line segment clouds into point clouds, as a preprocessing step prior to surface reconstruction. We describe how to construct a low-cost laser-line 3-D scanner, where the camera is fixed with respect to the object and the laser-line generator is mounted on a high-resolution motion platform. We describe a GPU-based implementation where the large number of captured images is processed in real time. Finally, we present some experimental results. [ABSTRACT FROM AUTHOR]

In this paper, we proposed a coverage path (CP) planning approach for a mobile robot moving in a dynamically changing environment. Our family of algorithms begins by finding the first path around the center of interior obstacles/disks of a given target region (TR) through the Graham scan algorithm. The first path is then used as a foundational path to generate a collision free, first order differentiable, and observable CP through a complete set of input and output transformation algorithms which together form the rainbow CP planning approach. The last algorithm of the rainbow CP planning approach finds a sufficient number of observation points on the CP needed to observe the TR. The novelty of our rainbow CP planning approach is that it partitions the TR into different shapes with different properties needed to obtain complete coverage while achieving first order path differentiability. The main technical contributions of the proposed approach is to provide a holistic solution that segments any TR, uses triangulation to determine the line of sights and observation points, and computes the collision-free CP within a quadratic runtime. The proposed method can be readily generalized to address problems of higher dimensions, and it is scalable with respect to the size of TR and the number of robots. Computer simulations are used to illustrate the effectiveness and correctness of the proposed approach. [ABSTRACT FROM AUTHOR]

A novel localization framework is presented based on ultra-wideband (UWB) channel sounding, employing a triangulation method using the geometrical properties of propagation paths, such as time delay of arrival, angle of departure, angle of arrival, and their estimated variances. In order to extract these parameters from the UWB sounding data, an extension to the high-resolution RiMAX algorithm was developed, facilitating the analysis of these frequency-dependent multipath parameters. This framework was then tested by performing indoor measurements with a vector network analyzer and virtual antenna arrays.The estimated means and variances of these geometrical parameters were utilized to generate multiple sample sets of input values for our localization framework. Next to that, we consider the existence of multiple possible target locations, which were subsequently clustered using a Kim–Parks algorithm, resulting in a more robust estimation of each target node. Measurements reveal that our newly proposed technique achieves an average accuracy of 0.26, 0.28, and 0.90 m in line-of-sight (LoS), obstructed-LoS, and non-LoS scenarios, respectively, and this with only one single beacon node. Moreover, utilizing the estimated variances of the multipath parameters proved to enhance the location estimation significantly compared to only utilizing their estimated mean values. [ABSTRACT FROM PUBLISHER]

Node self-localization is a key research topic for wireless sensor networks (WSNs). There are two main algorithms, the triangulation method and the maximum likelihood (ML) estimator, for angle of arrival (AOA) based self-localization. The ML estimator requires a good initialization close to the true location to avoid divergence, while the triangulation method cannot obtain the closed-form solution with high efficiency. In this paper, we develop a set of efficient closed-form AOA based self-localization algorithms using auxiliary variables based methods. First, we formulate the self-localization problem as a linear least squares problem using auxiliary variables. Based on its closed-form solution, a new auxiliary variables based pseudo-linear estimator (AVPLE) is developed. By analyzing its estimation error, we present a bias compensated AVPLE (BCAVPLE) to reduce the estimation error. Then we develop a novel BCAVPLE based weighted instrumental variable (BCAVPLE-WIV) estimator to achieve asymptotically unbiased estimation of locations and orientations of unknown nodes based on prior knowledge of the AOA noise variance. In the case that the AOA noise variance is unknown, a new AVPLE based WIV (AVPLE-WIV) estimator is developed to localize the unknown nodes. Also, we develop an autonomous coordinate rotation (ACR) method to overcome the tangent instability of the proposed algorithms when the orientation of the unknown node is near \pi/2. We also derive the Cramér-Rao lower bound (CRLB) of the ML estimator. Extensive simulations demonstrate that the new algorithms achieve much higher localization accuracy than the triangulation method and avoid local minima and divergence in iterative ML estimators. [ABSTRACT FROM PUBLISHER]

In this paper, we propose a novel interactive projection system (IPS), which enables bare-finger touch interaction on regular planar surfaces (e.g., walls, tables), with only one standard camera and one projector. The challenge of bare-finger touch detection is recovering the touching information just from the 2-D image captured by the camera. In our method, the graphical user interface (GUI) button is projected on the surface and is distorted by the finger when clicking it, and there is a significant positive correlation between the button's distortion and the finger's height to the surface. Therefore, we propose a novel, fast, and robust algorithm, which takes advantage of the button's distortion to detect the touch action. The proposed touch detection algorithm is performed in three stages: 1) region of interest extraction through a homography mapping, by which the computational complexity of the following processing is reduced; 2) the button's distortion detection using a special edge detection algorithm, which greatly reduces the errors due to the influence of the finger's shadows and edges; and 3) touch action judgment by the button's distortion. Several applications (e.g., virtual keyboard, power point viewing), which use the proposed touch detection method based on the buttons, are shown in this paper. An evaluation is performed on the virtual keyboard and the results demonstrate that the proposed approach can detect bare-finger touch in real time with the missed detection rate of 1.00%, false detection rate of 2.08%, and touch detection rate of 96.92% at the typical projected distance. [ABSTRACT FROM AUTHOR]

A new exact algorithm is proposed to compute the 3D geometric moments of a homogeneous shape defined by an unstructured triangulation of its surface. This algorithm relies on the analytical integration of the moments on tetrahedra defined by the surface triangles and a central point and on a set of recurrent relationships between the corresponding integrals, and achieves linear running time complexities with respect to the number of triangles in the surface mesh and with respect to the number of moments that are computed. This effectively reduces the complexity for computing moments up to order N from N^6 to N^3 with respect to the fastest previously proposed exact algorithm. [ABSTRACT FROM AUTHOR]

A new technique to compute the physical optics (PO) integral is presented. The technique consists of a blind code that computes the different contributions (stationary phase points, end points, etc.) numerically. This technique is based on a decomposition of the surface into small triangles and a fast evaluation of each triangle by means of a deformation of the integration path in the complex plane. This algorithm permits a fast and accurate evaluation of the PO integral for smooth large surfaces. The CPU time is almost independent of frequency. [ABSTRACT FROM AUTHOR]

We present an algorithm for distributed sensor localization with noisy distance measurements (DILAND) that extends and makes the DLRE more robust. DLRE is a distributed sensor localization algorithm in ℝm (m ⩾1) introduced in our previouswork (IEEE Trans. Signal Process., vol. 57, no. 5, pp. 2000-2016, May 2009). DILAND operates when: 1) the communication among the sensors is noisy; 2) the communication links in the network may fail with a nonzero probability; and 3) the measurements performed to compute distances among the sensors are corrupted with noise. The sensors (which do not know their locations) lie in the convex hull of at least m+1 anchors (nodes that know their own locations). Under minimal assumptions on the connectivity and triangulation of each sensor in the network, we show that, under the broad random phenomena described above, DILAND converges almost surely (a.s.) to the exact sensor locations. [ABSTRACT FROM AUTHOR]

The article discusses the use of an algorithm for finding minimum cutsets in connected graphs. Topics include designing probabilistic algorithms, using recursion to lower the computational cost of an algorithm, and finding the minimum-sized set of edges required to disconnect a graph. Also discussed is a Delaunay triangulation graph.

A new parameter-free graph-morphology-based segmentation algorithm is proposed to address the problem of partitioning a 3D triangular mesh into disjoint submeshes that correspond to the physical parts of the underlying object. Curvedness, which is a rotation and translation invariant shape descriptor, is computed at every vertex in the input triangulation. Iterative graph dilation and morphological filtering of the outlier curvedness values result in multiple disjoint maximally connected submeshes such that each submesh contains a set of vertices with similarcurvedness values, and vertices in disjoint submeshes have significantly different curvedness values. Experimental evaluations using the triangulations of a number of complex objects demonstrate the robustness and the efficiency of the proposed algorithm and the results prove that it compares well with a number of state-of-the-art mesh segmentation algorithms. [ABSTRACT FROM AUTHOR]

Many existing multiview image/video coding techniques remove inter-viewpoint redundancy by applying disparity compensation in a conventional video coding framework, e.g., H.264/MPEG-4 AVC. HQwever, conventional methodology works ineffectively as it ignores the special characteristics of inter-viewpoint disparity. In this paper, we propose a geometric prediction methodology for accurate disparity vector (DV) prediction, such that we can largely reduce the disparity compensation cost. Based on the new DV predictor, we design a basic framework that can be implemented in most existing multiview image/video coding schemes. We also use state-of-the-art H.264/MPEG-4 AVC as an example to illustrate how the proposed framework can be integrated with conventional video coding algorithms. Our experiments show proposed scheme can effectively tracks disparity and greatly improves coding performance. Compared with H.264/MPEG-4 AVC codec, our scheme outperforms maximally 1.5 dB when encoding some typical multiview image sequences. We also carry out an experiment to evaluate the robustness of our algorithm. The results indicate our method is robust and can be used in practical applications. [ABSTRACT FROM AUTHOR]

This paper describes a method for constructing isosurface triangulations of sampled, volumetric, three-dimensional scalar fields. The resulting meshes consist of triangles that are of consistently high quality, making them well suited for accurate interpolation of scalar and vector-valued quantities, as required for numerous applications in visualization and numerical simulation. The proposed method does not rely on a local construction or adjustment of triangles as is done, for instance, in advancing wavefront or adaptive refinement methods. Instead, a system of dynamic particles optimally samples an implicit function such that the particles' relative positions can produce a topologically correct Delaunay triangulation. Thus, the proposed method relies on a global placement of triangle vertices. The main contributions of the paper are the integration of dynamic particles systems with surface sampling theory and PDE-based methods for controlling the local variability of particle densities, as well as detailing a practical method that accommodates Delaunay sampling requirements to generate sparse sets of points for the production of high-quality tessellations. [ABSTRACT FROM AUTHOR]

We demonstrate the effect of using multiple estimations from independent single wireless motes in order to decrease network topology dependence on location estimation in a wireless sensor network. A method of determining the location of a target by using multiple compact semi-directional antennas is shown to give an independent estimate of location from each sensor mote in a network, each estimate not relying on the data from neighboring motes as in the case of traditional triangulation. We begin by demonstrating a method of using angular diversity through multiple semi-directional antennas in order to ascertain the location of a target. The estimation of both range and angle is demonstrated in the presence of a noisy and/or faded channel. An efficient and fast algorithm on a wireless sensor mote is presented through a Taylor series expansion of the simulated antenna pat- tern. Furthermore, using the results from the location estimation from a single node, location determination in a realistic network is explored through both theory and simulation. The results indicate that our proposed algorithm depends significantly less on the topology (spatial arrangement) of the anchor nodes. While network planning for a variety of topologies of anchor nodes is shown to be necessary when using triangulation, our proposed algorithm is insensitive to the deployments of the anchor nodes. A testbed was created in order to experimentally demonstrate that the predictions are accurate even in triangulation-adverse topologies. The experimental testbed shows that a linear arrangement of closely spaced sensors can reduce the location error to one-fourth of the location error using triangulation. [ABSTRACT FROM AUTHOR]

Locally optimal Delaunay triangulations are constructed to improve previous image approximation schemes. Our construction relies on a local optimization procedure, termed exchange. The efficient implementation of the exchange algorithm is addressed, and its complexity is discussed. The good performance of our improved image approximation is illustrated by numerical comparisons. [ABSTRACT FROM AUTHOR]

In this paper, we present a computational framework for automatic generation of provably correct control laws for planar robots in polygonal environments. Using polygon triangulation and discrete abstractions, we map continuous motion planning and control problems, specified in terms of triangles, to computationally inexpensive problems on finite-state-transition systems. In this framework, discrete planning algorithms in complex environments can be seamlessly linked to automatic generation of feedback control laws for robots with underactuation constraints and control bounds. We focus on fully actuated kinematic robots with velocity bounds and (underactuated) unicycles with forward and turning speed bounds. [ABSTRACT FROM AUTHOR]

Many generic position-estimation algorithms are vulnerable to ambiguity introduced by nonunique landmarks. Also, the available high-dimensional image data is not fully used when these techniques are extended to vision-based localization. This paper presents the landmark matching, triangulation, reconstruction, and comparison (LTRC) global localization algorithm, which is reasonably immune to ambiguous landmark matches. It extracts natural landmarks for the (rough) matching stage before generating the list of possible position estimates through triangulation. Reconstruction and comparison then rank the possible estimates. The LTRC algorithm has been implemented using an interpreted language, onto a robot equipped with a panoramic vision system. Empirical data shows remarkable improvement in accuracy when compared with the established random sample consensus method. LTRC is also robust against inaccurate map data. [ABSTRACT FROM AUTHOR]

Depth from triangulation has traditionally been investigated in a number of independent threads of research, with methods such as stereo, laser scanning, and coded structured light considered separately. In this paper, we propose a common framework called spacetime stereo that unifies and generalizes many of these previous methods. To show the practical utility of the framework, we develop two new algorithms for depth estimation: depth from unstructured illumination change and depth estimation in dynamic scenes. Based on our analysis, we show that methods derived from the spacetime stereo framework can be used to recover depth in situations in which existing methods perform poorly. [ABSTRACT FROM AUTHOR]

This article focuses on a survey of motion-parallax-based 3-D reconstruction algorithms. The task of recovering three-dimensional (3-D) geometry from two-dimensional views of a scene is called 3-D reconstruction. It is an extremely active research area in computer vision. Analysis and interpretation of visual information are at the heart of all computer vision research. The availability of both physiological and psychological cues gives the human visual system the ability to perceive depth. Some examples of these cues include binocular parallax, monocular movement parallax, accommodation, convergence, linear perspective, shades and shadows, and so on.

In this paper, we consider soft decision directed channel estimation for turbo equalization. To take advantage of soft information provided by the decoder, a minimum mean square error linear channel estimator is derived under an uncorrelated channel tap model, and a soft input recursive least squares algorithm is also developed by modifying the cost function of the conventional recursive least squares algorithm. The performance of the proposed channel estimators are analyzed in terms of mean square identification error (MSLE) for stationary channels. Simulation results for both time-invariant and time-varying frequency-selective Rayleigh fading channels are also presented. [ABSTRACT FROM AUTHOR]

A leaky recursive least squares (LRLS) algorithm obtained by a criterion of the ridge regression with the exponential weighting factor was recently proposed by one of the authors. On the other hand, an optimization criterion for improving the method of total least squares (TLS) has been proposed by Chandrasekaran et al. In this work, it is expressed that there is a case where the equation obtained by the criterion of the LRLS algorithm is identical to one obtained by the extended criterion of Chandrasekaran et al. In addition, some implementations of the LRLS filter by using the method for updating the eigendecomposition of rankeone matrix updates, or by using the leaky least mean square (LLMS) algorithm, are introduced to decrease the computational complexity of the LRLS algorithm. Moreover, by means of computer experiments, it is shown that the LRLS and the LLMS algorithms yield more precise estimation parameters than the RLS algorithm when the method of Chandrasekaran et al. is more useful than that of LS and TLS. Besides, it is demonstrated that the LLMS algorithm can be effectively introduced into a noise reduction system for noisy speech signals to support the theoretical results in this work. [ABSTRACT FROM AUTHOR]

Presents a ray-tracing procedure based on a triangular grid approach for predicting the propagation of radio waves in urban environments. Facts on the two-dimensional triangulation of propagation environments; Description of a ray-tracing algorithm; Comparison of simulations for radio wave propagation.

Examines the mechanism of a sensor fusion scheme called triangulation-based fusion (TBF) of sonar data. Discussion on the basic triangulation principle; Complexity in computing the TBF algorithm; Application of the TBF algorithm in robot pose tracking.

Shows that the power and flexibility of the reconfigurable mesh can be exploited to obtain constant-time algorithms for a number of constrained triangulation problems. Refigurable mesh as a powerful architecture augmented by a dynamically reconfigurable bus system; Computer-aided manufacturing and design; Robotics; Very large scale integration design.

Studies the combinatorial and computational constructions for difference triangle sets having small scopes. Combinatorial asymptotics for difference triangle sets; Algorithms for constructing difference triangle sets; Conclusions.

Memoryless online routing (MOR) algorithms are suitable for the applications only using local information to find paths, and Delaunay triangulations (DTs) are the class of geometric graphs widely proposed as network topologies. Motivated by these two facts, this paper reports a variety of new MOR algorithms that work for Delaunay triangulations, thus greatly enriching the family of such algorithms. This paper also evaluates and compares these new algorithms with three existing MOR algorithms. The experimental results shed light on their performance in terms of both Euclidean and link metrics, and also reveal certain properties of Delaunay triangulations. Finally, this paper poses three open problems, with their importance explained. [ABSTRACT FROM AUTHOR]

In the research of computer vision and machine perception, 3D objects are usually represented by 2-manifold triangular meshes \cal M. In this paper, we present practical and efficient algorithms to construct iso-contours, bisectors, and Voronoi diagrams of point sites on \cal M, based on an exact geodesic metric. Compared to euclidean metric spaces, the Voronoi diagrams on \cal M exhibit many special properties that fail all of the existing euclidean Voronoi algorithms. To provide practical algorithms for constructing geodesic-metric-based Voronoi diagrams on \cal M, this paper studies the analytic structure of iso-contours, bisectors, and Voronoi diagrams on \cal M. After a necessary preprocessing of model \cal M, practical algorithms are proposed for quickly obtaining full information about iso--contours, bisectors, and Voronoi diagrams on \cal M. The complexity of the construction algorithms is also analyzed. Finally, three interesting applications—surface sampling and reconstruction, 3D skeleton extraction, and point pattern analysis—are presented that show the potential power of the proposed algorithms in pattern analysis. [ABSTRACT FROM AUTHOR]

The capability to query the topology of spatial regions is fundamental to today's centralized spatial computing systems, like spatial databases and GIS. By contrast, this paper explores decentralized algorithms for computing the topology of spatial regions in wireless sensor networks. The approach generates global topological information about regions, using only the local knowledge of nodes and their immediate network neighbors aggregated up through spatial boundary structures. Using three basic boundary structures (boundary nodes, boundary cycles, and boundary orientation), a family of decentralized algorithms is defined that can respond efficiently to snapshot queries about the topology of spatial regions, including containment and adjacency queries. The communication complexity of the algorithm is O(n) for realistic inputs. Empirical investigation of the performance of the approach, using simulation, also confirms the efficiency, scalability, and robustness of this approach. [ABSTRACT FROM AUTHOR]