Graph-based method for face identification from a single 2D linedrawing

The faces in a 2D fine drawing of an object provide important information for the reconstruction of its 3D geometry. In this paper, a graph-based optimization method is proposed for identifying the faces is a line drawing. The face identification is formulated as a maximum weight clique problem. This formulation is proven to be equivalent to the formulation proposed by Shpitalni and Upson (1996). The advantage of our formulation is that it enables one to develop a much faster algorithm to find the faces in a drawing. The significant improvement in speed is derived from two algorithms provided: the depth-first graph search for quickly generating possible faces from a drawing; and the maximum weight clique finding for obtaining the optimal face configurations of the drawing. The experimental results shown that our algorithm generates the same results of face identification as Shpitalni and Lipson's method, but is much faster when dealing with objects of more than 20 faces     

Identifying faces in a 2D line drawing representing a manifold object

A straightforward way to illustrate a 3D model is to use a line drawing. Faces in a 2D line drawing provide important information for reconstructing its 3D geometry. Manifold objects belong to a class of common solids and most solid systems are based on manifold geometry. In this paper, a new method is proposed for finding faces from single 2D line drawings representing manifolds. The face identification is formulated based on a property of manifolds: each edge of a manifold is shared exactly by two faces. The two main steps in our method are (1) searching for cycles from a line drawing and (2) searching for faces from the cycles. In order to speed up the face identification procedure, a number of properties, most of which relate to planar manifold geometry in line drawings, are presented to identify most of the cycles that are or are not real faces in a drawing, thus reducing the number of unknown cycles in the second searching. Schemes to deal with manifolds with curved faces and manifolds each represented by two or more disjoint graphs are also proposed. The experimental results show that our method can handle manifolds previous methods can handle, as well as those they cannot.     

Identification of faces in a 2D line drawing projection of awireframe object

An important key to reconstructing a three-dimensional object depicted by a two-dimensional line drawing projection is face identification. Identification of edge circuits in a 2D projection corresponding to actual faces of a 3D object becomes complex when the projected object is in wireframe representation. This representation is commonly encountered in drawings made during the conceptual design stage of mechanical parts. When nonmanifold objects are considered, the situation becomes even more complex. This paper discusses the principles underlying face identification and presents an algorithm capable of performing this identification. Face-edge-vertex relationships applicable to nonmanifold objects are also proposed. Examples from a working implementation are given     

Plane-based optimization for 3D object reconstruction from single line drawings

In previous optimization-based methods of 3D planar-faced object reconstruction from single 2D line drawings, the missing depths of the vertices of a line drawing (and other parameters in some methods) are used as the variables of the objective functions. A 3D object with planar faces is derived by finding values for these variables that minimize the objective functions. These methods work well for simple objects with a small number N of variables. As N grows, however, it is very difficult for them to find expected objects. This is because with the nonlinear objective functions in a space of large dimension N, the search for optimal solutions can easily get trapped into local minima. In this paper, we use the parameters of the planes that pass through the planar faces of an object as the variables of the objective function. This leads to a set of linear constraints on the planes of the object, resulting in a much lower dimensional nullspace where optimization is easier to achieve. We prove that the dimension of this nullspace is exactly equal to the minimum number of vertex depths which define the 3D object. Since a practical line drawing is usually not an exact projection of a 3D object, we expand the nullspace to a larger space based on the singular value decomposition of the projection matrix of the line drawing. In this space, robust 3D reconstruction can be achieved. Compared with two most related methods, our method not only can reconstruct more complex 3D objects from 2D line drawings, but also is computationally more efficient.     

Decomposition of complex line drawings with hidden lines for 3D planar-faced manifold object reconstruction

Three-dimensional object reconstruction from a single 2D line drawing is an important problem in computer vision. Many methods have been presented to solve this problem, but they usually fail when the geometric structure of a 3D object becomes complex. In this paper, a novel approach based on a divide-and-conquer strategy is proposed to handle the 3D reconstruction of a planar-faced complex manifold object from its 2D line drawing with hidden lines visible. The approach consists of four steps: 1) identifying the internal faces of the line drawing, 2) decomposing the line drawing into multiple simpler ones based on the internal faces, 3) reconstructing the 3D shapes from these simpler line drawings, and 4) merging the 3D shapes into one complete object represented by the original line drawing. A number of examples are provided to show that our approach can handle 3D reconstruction of more complex objects than previous methods.     

A new algorithm for finding faces in wireframes

The problem of identifying the topology implied by wireframe drawings of polyhedral objects requires the identification of face loops, loops of edges which correspond to a face in the object the drawing portrays.In this paper, we survey the advantages and limitations of known approaches, and present and discuss test results which illustrate the successes and failures of a currently popular approach based on Dijkstra’s Algorithm. We conclude that the root cause of many failure cases is that the underlying algorithm assumes that the cost of traversing an edge is fixed.We propose a new polynomial-order algorithm for finding faces in wireframes. This algorithm could be adapted to any graph-theoretical least-cost circuit problem where the cost of traversing an edge is not fixed but context-dependent.     

3D reconstruction of complex curved objects from line drawings

An active research topic in computer vision and graphics is developing algorithms that can reconstruct the 3D surface of curved objects from line drawings. There are a number of algorithms have been dedicated to solve this problem, but they can't solve this problem when the geometric structure of a curved object becomes complex. This paper proposes a novel approach to reconstructing a complex curved 3D object from single 2D line drawings. Our approach has three steps:(1) decomposing a complex line drawing into several simpler line drawings and transforming them into polyhedron;(2) reconstructing the 3D wireframe of curved object from these simpler line drawings and generating the curved faces;(3) combining the 3D objects into the complete objects. A number of examples are given to demonstrate the ability of our approach to successfully perform reconstruction of curved objects which are more complex than previous methods.     

3D reconstruction of polyhedral objects from single parallel projections using cubic corner

This paper presents a direct method to recover the geometry of the 3D polyhedron depicted in a single parallel projection. It uses two sets of information, the list of faces in the object, obtained automatically from the drawing, and a user-identified cubic corner, to compute for the coordinates of the vertices in the drawing and thus establish the 3D geometry of the whole polyhedron. The algorithm exploits the topological structure of the polyhedron, implicit in the connectivities between the faces, resulting in a complexity that is linear in the number of faces. The method is extended to objects with no cubic corners as well. The algorithm works well for recovering objects from accurate line drawings, producing accurate 3D objects. A simple extension to the algorithm allows it to handle inaccurate drawings such as sketches, and produce 3D objects that are consistent with our human perception of the drawings.     

Inserting an Edge into a Planar Graph

Computing a crossing minimum drawing of a given planar graph G augmented by an additional edge e where all crossings involve e, has been a long standing open problem in graph drawing. Alternatively, the problem can be stated as finding a combinatorial embedding of a planar graph G where the given edge e can be inserted with the minimum number of crossings. Many problems concerned with the optimization over the set of all combinatorial embeddings of a planar graph turned out to be NP-hard. Surprisingly, we found a conceptually simple linear time algorithm based on SPQR-trees, that is able to find a solution with the minimum number of crossings.     

A shape-from-shading method of polyhedral objects using prior information

We propose a new method for recovering the 3D shape of a polyhedral object from its single 2D image using the shading information contained in the image and the prior information on the object. In a strict sense, we cannot recover the shape of a polyhedron from an incorrect line drawing, even if it is practically almost correct. In order to overcome this problem, we propose a flexible face positioning method that can permit inconsistencies in the recovered shape that arise from vertex-position errors contained in incorrect line drawings. Also, we propose to use prior information about the horizontality and verticality of special faces and the convex and concave properties of the edges in order to attain good solutions and present a method of formulating such prior information as physical constraints. The shape-from-shading method is formulated as a minimization problem of a nonlinear cost function with the nonlinear constraints and its solution is searched by a global optimization algorithm. In the experiments with a synthetic image and three kinds of real images, shapes that are similar to those of the actual objects were recovered in all cases. As a result, the proposed method has proven to be effective in the shape recovery of simple-shape polyhedral objects.     

基于EM迭代的曲线提取算法

从工程图纸中追踪曲线并进行数字化是一项极有意义的工程。本文设计了一种基于EM算法思想的曲线追踪提取算法。该算法主要通过两个步骤来实现。首先在E步骤,利用两个先验点预测出下一个目标点。预测的方法采用切线导向搜索法。然后在M步骤,对目标点的坐标进行优化调整,将搜索到的黑游程正中间的点作为最终目标点。文中将该算法应用于工程图纸的曲线数据提取,实验表明,本算法能够实现曲线数据的连续自动提取,并且不受交叉点和其它噪声点的影响,同时优化了搜索过程,极大提高了曲线数据提取的效率。     

基于改进的NRLCC编码的立体线图匹配算法

线图匹配在计算机视觉领域有着广泛的应用。该文研究基于改进的NRLCC编码以及面之间的关系进行立体线图的匹配。首先利用图同构检测目标线图与模型线图的面的排列关系是否一致;然后获取面的NRLCC编码和ENRLCC编码,分别得到面的顶点的凹凸性信息和组成面的曲线段的凹凸性信息。最后,利用以上几组信息,进行线图的匹配。试验结果表明,该方法可以对具有曲线边缘的工业物体进行准确的识别。     

工程三视图的三维恢复

本文在总结边界表示法（ＢＲ）的结构式立体几何表示法（ＣＳＧＲ）重建三维图形的基础上，提出了一种基于两者结合的三维重建方法。采用ＢＲ方法，把工程图纸的二维矢量化信息作为原始数据，逐步恢复三维点，三维边，面及ＣＳＧＲ意义下的基元体。采用ＣＳＧＲ方法，组合基元体，最终生成复合体，重建三维图形。算法以多面体为研究对象，在ＷＩＮＤＯＷ５３．０环境下实现。     

A methodology to find the elementary landscape decomposition of combinatorial optimization problems

A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function f is an eigenfunction of the Laplacian that describes the neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes.     

Clump splitting via bottleneck detection and shape classification

Under-segmentation of an image with multiple objects is a common problem in image segmentation algorithms. This paper presents a novel approach for splitting clumps formed by multiple objects due to under-segmentation. The proposed algorithm includes three steps: (1) decide whether to split a candidate connected component by application-specific shape classification; (2) find a pair of points for clump splitting and (3) join the pair of selected points. In the first step, a shape classifier is applied to determine whether a connected component should be split. In the second step, a pair of points for splitting is detected using a bottleneck rule, under the assumption that the desired objects have roughly a convex shape. In the third step, the selected splitting points from step two are joined by finding the optimal splitting line between them, based on minimizing an image energy. The shape classifier is built offline via various shape features and a support vector machine. Steps two and three are application-independent. The performance of this method is evaluated using images from various applications. Experimental results show that the proposed approach outperforms the state-of-the-art algorithms for the clump splitting problem.     

A hybrid evolutionary approach for heterogeneous multiprocessor scheduling

This article investigates the assignment of tasks with interdependencies in a heterogeneous multiprocessor environment; specific to this problem, task execution time varies depending on the nature of the tasks as well as with the processing element assigned. The solution to this heterogeneous multiprocessor scheduling problem involves the optimization of complete task assignments and processing order between the assigned processors to arrive at a minimum makespan, subject to a precedence constraint. To solve an NP-hard combinatorial optimization problem, as is typified by this problem, this paper presents a hybrid evolutionary algorithm that incorporates two local search heuristics, which exploit the intrinsic structure of the solution, as well as through the use of specialized genetic operators to promote exploration of the search space. The effectiveness and contribution of the proposed features are subsequently validated on a set of benchmark problems characterized by different degrees of communication times, task, and processor heterogeneities. Preliminary results from simulations demonstrate the effectiveness of the proposed algorithm in finding useful schedule sets based on the set of new benchmark problems.     

A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) provides an excellent algorithmic framework for solving multi-objective optimization problems. It decomposes a target problem into a set of scalar sub-problems and optimizes them simultaneously. Due to its simplicity and outstanding performance, MOEA/D has been widely studied and applied. However, for solving the multi-objective vehicle routing problem with time windows (MO-VRPTW), MOEA/D faces a difficulty that many sub-problems have duplicated best solutions. It is well-known that MO-VRPTW is a challenging problem and has very few Pareto optimal solutions. To address this problem, a novel selection operator is designed in this work to enhance the original MOEA/D for dealing with MO-VRPTW. Moreover, three local search methods are introduced into the enhanced algorithm. Experimental results indicate that the proposed algorithm can obtain highly competitive results on Solomon׳s benchmark problems. Especially for instances with long time windows, the proposed algorithm can obtain more diverse set of non-dominated solutions than the other algorithms. The effectiveness of the proposed selection operator is also demonstrated by further analysis.     

Inheritable genetic algorithm for biobjective 0/1 combinatorial optimization problems and its applications.

In this paper, we formulate a special type of multiobjective optimization problems, named biobjective 0/1 combinatorial optimization problem BOCOP, and propose an inheritable genetic algorithm IGA with orthogonal array crossover (OAX) to efficiently find a complete set of nondominated solutions to BOCOP. BOCOP with n binary variables has two incommensurable and often competing objectives: minimizing the sum r of values of all binary variables and optimizing the system performance. BOCOP is NP-hard having a finite number C(n, r) of feasible solutions for a limited number r. The merits of IGA are threefold as follows: 1) OAX with the systematic reasoning ability based on orthogonal experimental design can efficiently explore the search space of C(n, r); 2) IGA can efficiently search the space of C(n, r+/-1) by inheriting a good solution in the space of C(n, r); and 3) The single-objective IGA can economically obtain a complete set of high-quality nondominated solutions in a single run. Two applications of BOCOP are used to illustrate the effectiveness of the proposed algorithm: polygonal approximation problem (PAP) and the problem of editing a minimum reference set for nearest neighbor classification (MRSP). It is shown empirically that IGA is efficient in finding complete sets of nondominated solutions to PAP and MRSP, compared with some existing methods.     

A hybrid particle swarm optimization algorithm for the vehicle routing problem

This paper introduces a new hybrid algorithmic nature inspired approach based on particle swarm optimization, for successfully solving one of the most popular supply chain management problems, the vehicle routing problem. The vehicle routing problem is considered one of the most well studied problems in operations research. The proposed algorithm for the solution of the vehicle routing problem, the hybrid particle swarm optimization (HybPSO), combines a particle swarm optimization (PSO) algorithm, the multiple phase neighborhood search–greedy randomized adaptive search procedure (MPNS–GRASP) algorithm, the expanding neighborhood search (ENS) strategy and a path relinking (PR) strategy. The algorithm is suitable for solving very large-scale vehicle routing problems as well as other, more difficult combinatorial optimization problems, within short computational time. It is tested on a set of benchmark instances and produced very satisfactory results. The algorithm is ranked in the fifth place among the 39 most known and effective algorithms in the literature and in the first place among all nature inspired methods that have ever been used for this set of instances.     

基于耦合相关度的空间数据查询结果自动分类方法

由于空间数据库通常蕴含海量数据,因此一个普通的空间查询很可能会导致多查询结果问题。为了解决上述问题,提出了一种空间查询结果自动分类方法。在离线阶段,根据空间对象之间的位置相近度和语义相关度来评估空间对象之间的耦合关系,在此基础上利用概率密度评估方法对空间对象进行聚类,每个聚类代表一种类型的用户需求;在在线查询处理阶段,对于一个给定的空间查询,在查询结果集上利用改进的C4.5决策树算法动态生成一棵查询结果分类树,用户可通过检查分类树分支的标签来逐步定位到其感兴趣的空间对象。实验结果表明,提出的空间对象聚类方法能够有效地体现空间对象在语义和位置上的相近性,查询结果分类方法具有较好的分类效果和较低的搜索代价。