A C-tree decomposition algorithm for 2D and 3D geometric constraint solving

In this paper, we propose a method which can be used to decompose a 2D or 3D constraint problem into a C-tree. With this decomposition, a geometric constraint problem can be reduced into basic merge patterns, which are the smallest problems we need to solve in order to solve the original problem in certain sense. Based on the C-tree decomposition algorithm, we implemented a software package MMP/Geometer. Experimental results show that MMP/Geometer finds the smallest decomposition for all the testing examples efficiently.     

A topological hierarchy-based approach to toolpath planning for multi-material layered manufacturing

This paper proposes a topological hierarchy-based approach to toolpath planning for multi-material layered manufacturing (MMLM) of heterogeneous prototypes. The approach facilitates control of MMLM and increases the fabrication efficiency of complex objects by generating multi-toolpaths that avoid redundant tool movements and potential collisions. It uses a topological hierarchy-sorting algorithm to group complex multi-material slice contours into families connected by a parent-and-child relationship. Subsequently, a sequential toolpath planning algorithm generates multi-toolpaths for sequential deposition of materials without redundant tool movements. To reduce build time further, a concurrent toolpath planning algorithm generates collision-free multi-toolpaths to control the tools that deposit materials concurrently. It uses parametric polygons to construct tool envelopes for contour families of the same material property to simplify detection of tool collisions. The tightness of polygons can be controlled to suit the processing speed and the optimality of the resulting concurrent toolpaths. The proposed approach has been implemented as an integral part of a multi-material virtual prototyping (MMVP) system that can process complex slice contours for planning, stereoscopic simulation, and validation of multi-toolpaths. It may be adapted for subsequent control of MMLM processes.     

Protein classification by matching and clustering surface graphs

In this paper, we address the problem of comparing and classifying protein surfaces with graph-based methods. Comparison relies on matching surface graphs, extracted from the surfaces by considering concave and convex patches, through a kernelized version of the Softassign graph-matching algorithm. On the other hand, classification is performed by clustering the surface graphs with an EM-like algorithm, also relying on kernelized Softassign, and then calculating the distance of an input surface graph to the closest prototype. We present experiments showing the suitability of kernelized Softassign for both comparing and classifying surface graphs.     

An analysis of BioHashing and its variants

As a result of the growing demand for accurate and reliable personal authentication, biometric recognition, a substitute for or complement to existing authentication technologies, has attracted considerable attention. It has recently been reported that, along with its variants, BioHashing, a new technique that combines biometric features and a tokenized (pseudo-) random number (TRN), has achieved perfect accuracy, having zero equal error rates (EER) for faces, fingerprints and palmprints. There are, however, anomalies in this approach. These are identified in this paper, in which we systematically analyze the details of the approach and conclude that the claim of having achieved a zero EER is based upon an impractical hidden assumption. We simulate the claimants’ experiments and find that it is not possible to achieve their reported performance without the hidden assumption and that, indeed, the results are worse than when using the biometric alone.     

A decision-support system for the design and management of warehousing systems

The issue of material handling involves the design and operative control of warehousing systems (i.e., distribution centres), which allow matching vendors and demands, smoothing with seasonality, consolidating products and arranging distribution activities. Warehousing systems play a crucial role in providing efficiency and customer satisfaction. The warehouse design entails a wide set of decisions, which involve layout constraints and operative issues that seriously affect the performances and the overall logistics costs.     

Boundary-conformed toolpath generation for trimmed free-form surfaces

In this paper, we adopt a 2D reparameterization procedure to regenerate boundary-conformed toolpaths. Three methods for the 2D reparameterization of trimmed boundaries in parametric space are examined and compared. They are the Coons method, the Laplace method, and a newly developed boundary-blending method. These three methods represent three different approaches to 2D surface parameterization, namely, the algebraic interpolation approach, the partial differential equation approach, and a geometric offsetting approach, respectively. Complete algorithms for surface reparameterization and toolpath generation are developed and implemented. The results showed that the Coons method is relatively simple yet might cause anomalies when the complexities of the boundary are high. The Laplace method is robust but takes relatively more computational time and also has the problem of uneven distribution of iso-parametrics. For the newly developed boundary-blending method, both the computational efficiency and parameterization robustness are quite good, in addition, it alleviates the uneven distribution problem appeared in the Laplace results.     

Optimal connection of loops in laminated object manufacturing

There are manufacturing applications where a tool needs to move along a prescribed path performing machining operations. An excellent application of this problem is found in the increasingly popular layered manufacturing (LM) methods, where the laser traces the profile of a layer by moving along the path while the laser turns on. The path is typically described by a sequence of curves. For the entire process, the tool must move along each curve exactly once. For typical paths, significant time may be wasted in the movement between the end point of one curve to the start point of the next one along which the laser is turned off. Normally, this non-cutting motion is a straight-line motion so to minimize the distance. A good process plan would minimize the time wasted on such motion. A maximum linear intersection (MLI) algorithm is proposed to solve this problem. Next, we present a variation of the GA based method to solve it. We compare the performance of these two techniques, both in terms of jumping distance and the computing time requirement, with a view to their application to real-time path planning in LM applications.     

On optimal pairwise linear classifiers for normal distributions: the d-dimensional case

We consider the well-studied pattern recognition problem of designing linear classifiers. When dealing with normally distributed classes, it is well known that the optimal Bayes classifier is linear only when the covariance matrices are equal. This was the only known condition for classifier linearity. In a previous work, we presented the theoretical framework for optimal pairwise linear classifiers for two-dimensional normally distributed random vectors. We derived the necessary and sufficient conditions that the distributions have to satisfy so as to yield the optimal linear classifier as a pair of straight lines.In this paper we extend the previous work to d-dimensional normally distributed random vectors. We provide the necessary and sufficient conditions needed so that the optimal Bayes classifier is a pair of hyperplanes. Various scenarios have been considered including one which resolves the multi-dimensional Minsky’s paradox for the perceptron. We have also provided some three-dimensional examples for all the cases, and tested the classification accuracy of the corresponding pairwise-linear classifier. In all the cases, these linear classifiers achieve very good performance. To demonstrate that the current pairwise-linear philosophy yields superior discriminants on real-life data, we have shown how linear classifiers determined using a maximum-likelihood estimate (MLE) applicable for this approach, yield better accuracy than the discriminants obtained by the traditional Fisher's classifier on a real-life data set. The multi-dimensional generalization of the MLE for these classifiers is currently being investigated.     

Ant colony search algorithms for optimal polygonal approximation of plane curves

This paper presents a new polygonal approximation method using ant colony search algorithm. The problem is represented by a directed graph such that the objective of the original problem becomes to find the shortest closed circuit on the graph under the problem-specific constraints. A number of artificial ants are distributed on the graph and communicate with one another through the pheromone trails which are a form of the long-term memory guiding the future exploration of the graph. The important properties of the proposed method are thoroughly investigated. The performance of the proposed method as compared to those of the genetic-based and the tabu search-based approaches is very promising.     

MODEEP: a motion-based object detection and pose estimation method for airborne FLIR sequences

In this paper, we present a method called MODEEP (Motion-based Object DEtection and Estimation of Pose) to detect independently moving objects (IMOs) in forward-looking infrared (FLIR) image sequences taken from an airborne, moving platform. Ego-motion effects are removed through a robust multi-scale affine image registration process. Thereafter, areas with residual motion indicate potential object activity. These areas are detected, refined and selected using a Bayesian classifier. The resulting regions are clustered into pairs such that each pair represents one object's front and rear end. Using motion and scene knowledge, we estimate object pose and establish a region of interest (ROI) for each pair. Edge elements within each ROI are used to segment the convex cover containing the IMO. We show detailed results on real, complex, cluttered and noisy sequences. Moreover, we outline the integration of our fast and robust system into a comprehensive automatic target recognition (ATR) and action classification system.