Search

The use and scope of LADAR applications continues to expand as the technology matures. This growth is reflected in NIST's experience with research into the applications of LADARs for construction, manufacturing, and autonomous vehicle navigation. However, standard protocols or procedures for calibrating and testing of LADARs have yet to be developed. Because selections of LADAR instruments are generally based on the manufacturer's specifications, the availability of standard test procedures would promote more uniform definitions of these specifications and provide a basis for a more rational decision. Consequently, NIST's Construction Metrology and Automation Group (CMAG) has conducted exploratory experiments to characterize the performance of a LADAR. The experiences gained in these efforts are summarized in this paper. These experiences also pointed to the need for an internal calibration/testing facility at NIST, as well as to the need for the development of uniform specifications and test procedures for LADARs. As a result, NIST convened a workshop on the establishment of a LADAR calibration facility. A discussion of some of the issues relating to the performance evaluation of LADARs and facility requirements is also presented in this paper., Presented at the Performance Metrics for Intelligent Systems (PerMIS '03) Conference held in Gaithersburg, Maryland on 16-18 September 2003. Published in the Proceedings of the Performance Metrics for Intelligent Systems (PerMIS '03) Conference, 2003. Co-sponsored by the Defense Advanced Research Projects Agency (DARPA). The original document contains color images.

Test runs of Army Research Laboratory's (ARL) autonomous vehicle (Experimental Unmanned Vehicle, XUV) were followed by the acquisition of high resolution scans of selected regions of the test course. These scans were used to i) determine terrain features (e.g., heavy vegetation, ditches, etc.) which may hamper the autonomous navigation of the XUV and ii) develop the ability to quantify terrain features such as vegetation or roughness. Those tasks require determination of "ground" or "bare earth," which is a major issue of ongoing research into terrain characterization. Point clouds collected by ground-based LADAR (laser distance and ranging) pose a particular challenge because they are extremely dense in close proximity to the instrument and progressively sparse at larger distances. This work focuses on the National Institute of Standards and Technology's (NIST) procedures for ground determination and the development of gauges for vegetation coverage and slope variability., Presented at the Performance Metrics for Intelligent Systems (PerMIS '03) Conference held in Gaithersburg, Maryland on 16-18 September 2003. Published in the Proceedings of the Performance Metrics for Intelligent Systems (PerMIS '03) Conference, 2003. Co-sponsored by the Defense Advanced Research Projects Agency (DARPA). The original document contains color images.

A computational approach to the task of generating contour-true and drain-consistent cartographic terrain surfaces from given grid-digitized contour lines is proposed and demonstrated for a still somewhat limited class of such contours. This approach is as follows: Consider all grid points located between two adjacent contours, and for each such grid point determine a shortest path towards the lower contour with respect to a grid metric that penalizes proximity to either contour. The pattern of these shortest paths is interpreted as a drain (ridge) pattern or network. This pattern contains the major drain (ridge) lines as implied by the contour information and thus permits the extraction of such features directly from grid-digitized contours. In a further development, the pattern is utilized to construct a grid elevation matrix by prorating elevations along its paths. An alternate drain (ridge) pattern derives naturally from that elevation matrix. This suggests an iterative procedure, alternating between extracting a drain (ridge) pattern from a grid elevation matrix and then generating a new elevation matrix from such a pattern. This procedure will be described and demonstrated. It will be considered as a method for interspersing contour lines of intermediate elevations.

This report concludes the second phase of a three-phase collaborative effort between the U.S. Army Engineer Topographic Laboratories and the National Bureau of Standards. The main objective of this effort is to develop and implement a contour-to-grid algorithm, that is, an algorithm capable of converting digitized contour data into Digital Terrain Elevation Data (DTED). The approach is to create a synthetic terrain surface based on digitized contour information and then to calculate any grid from that surface. Five tasks are to be performed: 1) Edit a digitized contour data set (input); 2) Thin (reduce, sample) the input data; 3) Triangulate the selected points; 4) Generate a smooth synthetic surface; and 5) Generate the desired grid. The first phase, which was completed in December 1985, addressed the first three tasks. The second phase, to which this report refers, elaborates on the previous results and includes work in all five areas. The effort demonstrates the feasibility of performing such tasks for large data sets, such as a Digital Graphic Recorder data tape of roughly 500,000 points.

Contents: Approximations by polynomials Theorems on continuity of rational approximations.

Tucker has formulated the Duality Theorem of Linear Programming in terms of orthogonality properties of a pair of complementary orthogonal linear manifolds with respect to the positive orthant. This theorem is generalized by substituting complementary polar conical sets for complementary orthogonal linear manifolds, and proved under simple stability assumptions. Equivalence to Feuchel's Duality Theorem for conjugate convex functions is established. There are strong parallelisms to work by Kretschmer. (Author)

The Fibonacci search technique for maximizing a unimodal function of one real variable is generalized to the case of a given first evaluation. This technique is then employed to determine the optimal sequential search technique for the maximization of a concave function. (Author)

A matrix calculus is introduced with the intention to develop data structures suitable for a high level algorithmic language for Mathematical Programming. The paper investigates how the special structure of matrices can be described and utilized for efficient computing by saving memory space and avoiding superfluous operations. The power of the calculus is increased by introducing lists, lists of lists, etc. of matrices and by extending ordinary matrix operators to list operators and cumulative operators over lists. Effective algorithms are given which use symbolic manipulations of matrix and list expressions so as to find the forms best suited for computation. These forms are called normal forms. Several completeness results are obtained in the sense that for each expression an equivalent expression in normal form can be found within a specified calculus. (Author)

Transportation polytopes are a special class of polytopes arising as sets of feasible solutions to transportation problems. The same polytopes are formed by all nonnegative matrices with specified row sums and column sums. Such matrices can be considered as generalized doubly stochastic matrices. The combinatorial structure--in particular, the number of vertices--of transportation polytopes is examined. (Author), Prepared in cooperation with Boeing Scientific research Labs., Seattle, Wash. Mathematics Research Lab., Rept. nos. D1-82-0662, Mathematical Note-536.

The frame of a cone C is a minimal set of generators, and the lineality space L of C is the greatest linear subspace contained in C. Algorithms are described for determining the frame and the lineality space of a cone C(S) spanned by a finite set S. These algorithms can be used for determining the vertices, edges, and other faces of low dimension of the convex hull of a finite set H(S). All algorithms are based on the simplex method of linear programming. The problem of finding the lineality space can be successively reduced to problems in spaces of lower dimensions. (Author), Prepared in cooperation with National Bureau of Standards, Washington, D. C.

It is shown that the theory of positive linear independence and the properties of Jordan-equivalent matrices can be utilized effectively in order to obtain an algebraic characterization of a face structure of convex polyhedral cones. (Author), Also available from the authors.

The constrained orthogonal Procrustes problem is the least-squares problem that calls for a rotation matrix that optimally aligns two matrices of the same order. Over past decades, the algorithm of choice for solving this problem has been the Kabsch-Umeyama algorithm, which is effectively no more than the computation of the singular value decomposition of a particular matrix. Its justification, as presented separately by Kabsch and Umeyama, is not totally algebraic since it is based on solving the minimization problem via Lagrange multipliers. In order to provide a more transparent alternative, it is the main purpose of this paper to present a purely algebraic justification of the algorithm through the exclusive use of simple concepts from linear algebra. For the sake of completeness, a proof is also included of the well known and widely used fact that the orientation-preserving rigid motion problem, i.e., the least-squares problem that calls for an orientation-preserving rigid motion that optimally aligns two corresponding sets of points in d-dimensional Euclidean space, reduces to the constrained orthogonal Procrustes problem.