Feature vector: a graph-based feature recognition methodology

Recognition of machining features is a vital link for the effective integration of various modules of computer integrated manufacturing systems (CIMS). Graph-based recognition is the most researched method due to the sound mathematical background of graph theory and a graph's structural similarity with B-Rep computer-aided design modellers’ database. The method, however, is criticized for its high computational requirement of graph matching, its difficulty in building a feature template library, its ability to handle only polyhedral parts and its inability to handle interacting features. The paper reports a new edge classification scheme to extend the graph-based algorithms to handle test parts with curved faces. A unique method of representing a feature, called a feature vector, is developed. The feature vector generation heuristic results in a recognition system with polynomial time complexity for any arbitrary attributed adjacency graph. The feature vector can be generated automatically from B-Rep modellers. This helps in building incrementally a feature library as per the requirements of the specific domain. The proposed system is implemented in VC++ using an ACIS® 3D solid modelling toolkit.     

Recognition of machining features - a hybrid approach

This paper describes a hybrid system which endeavours to recognize machining features automatically from a boundary representation (b-rep)-based solid modeller. The graph-based approach and the volume approach are adopted in consecutive stages in a prototype feature recognition system to combine the positive aspects of both strategies. The graph-based approach is based on feature edge sequence (FES) graph, a new graph structure introduced in this system. The FES graph approach is used to extract primitive features from the three-dimensional solid model; and the volume decomposition approach is incorporated to generate multiple interpretations of the feature sets. In addition, a neural network (NN)-based technique is used to tackle the problem of nonorthogonal and arbitrary features. Using the hybrid system, a workpiece designed in b-rep solid modeller will be interpreted and represented by a set of primitive features attached with significant manufacturing parameters, including multiple interpretations, tool directions and machining sequences, etc. The overall hybrid system is able to transform a pure geometric model into a machining feature-based model which is directly applicable for downstream manufacturing applications.     

Geometrical reasoning based on attributed graph grammar for prismatic parts

Modern manufacturing systems rely on a smooth and quick transformation of the design specification into manufacturing instructions. The shift towards feature-based design and manufacturing supports this effort. One of the weak links in this chain of activities is the conversion of the design features into the manufacturing features. This article presents a method based on graph grammar parsing that converts design geometrical features into manufacturing geometrical features. These features can then be used in process planning activities. The method presented extends the state of the art of syntactic graph-based features recognition by supporting embedding transformations, attribute transfer algorithms, decomposition of overlapping features and removal of empty volumes. In addition, the analysis provided by the graph parsing algorithms implicitly treats the features as solid models without the need to perform complicated geometrical'analysis. The system was implemented for prismatic components such that they can be produced on a triple axis vertical milling machine, and currently contains 20 rules.     

A hybrid method for recognizing interacting machining features

Recognizing interacting features from a design part is a major challenge in the feature recognition problem. It is difficult to solve this problem using a single reasoning approach or artificial intelligence technique. A hybrid method, which is based on feature hints, graph theory and an artificial neural network--ART 2 net--has been proposed to recognize interacting machining features. Through enhancing the concepts of feature hints and graph representation schemes, which were presented in previous work to facilitate the extraction process of interacting features and reduce the searching space of recognition algorithms, a novel set of representations and methodologies to define generic feature hints (F-Loops), the interacting relationships between F-Loops and graph manipulations for F-Loops are developed to deduce potential features with various interacting relationships in a unified way. The obtained potential features are represented as F-Loop Graphs (FLGs), and these FLGs are input into an ART 2 neural network to be classified into different types of features eventually. The advantages of employing the ART 2 network are highlighted through comparing the computational results with another type of neural network, which is commonly utilized in the feature recognition domain. Case studies with complex interacting features show that the developed hybrid method can achieve optimal efficiency by benefiting from the diverse capabilities of the three techniques in the different phases of the recognition approach.     

Feature patterns in recognizing non-interacting and interacting primitive,circular and slanting features using a neural network

Many varied techniques have long been suggested for the recognition of features from solid modellers, and the systems which have incorporated these techniques have achieved a moderate success. However the problem of recognition of the wide variety of features, e.g. interacting and non-interacting primitive, circular and slanting features, that any real life component may have, requires complex systems which are inflexible and hence limited in their use. Here, we present a simple and flexible system in which the features are defined as patterns of edges and vertices to deal with all the above types of features. The system starts by searching a B-rep solid model, using a cross-sectional layer method, for volumes which can be considered to represent features. Once the volumes are detected, their edges and vertices are processed and arranged into feature patterns which are used as input for a neural network to recognize the features. Simple conventions used in this work enable the creation of feature patterns for primitive, circular and slanting features. Learning, generalizing and tolerating incomplete data are some of the neural network's attributes exploited in this work to deal with interacting and non-interacting features.     

Recognition of interacting rotational and prismatic machining features from 3-D mill-turn parts

Current feature recognition methods generally recognize and classify machining features into two classes: rotational features and prismatic features. Based on the different characteristics of geometric shapes and machining methods, rotational features and prismatic features are recognized using different methods. Typically, rotational features are recognized using two-dimensional (2-D) edge and profile patterns. Prismatic features are recognized using 3-D geometric characteristics, for example, patterns in solid models such as 3-D face adjacency relationships. However, the current existing feature recognition methods cannot be applied directly to a class of so-called mill-turn parts where interactions between rotational and prismatic features exist. This paper extends the feature recognition domain to include this class of parts with interacting rotational and prismatic features. A new approach, called the machining volume generation method, is developed. The feature volumes are generated by sweeping boundary faces along a direction determined by the type of machining operation. Different types of machining features can be recognized by generating different forms of machining volumes using various machining operations. The generated machining volumes are then classified using face adjacency relationships of the bounding faces. The algorithms are executed in four steps, classification of faces, determining machining zones, generation of rotational machining volumes and prismatic machining volumes, and classification of features. The algorithms are implemented using the 3-D boundary representation data modelled on the ACIS solid modeller. Example parts are used to demonstrate the developed feature recognition method.     

采用图分解的特征识别算法研究

CAD/CAE模型转换,其关键在于如何将模型分解为最简单元,这些单元往往具有相近的网格划分属性,可以方便估计计算误差和计算时间。基于此提出了基于图分解的特征识别算法,对属性邻接图进行分解,根据分解后的属性邻接图中的连通分量生成体特征。该算法不再局限于特征类型,只要合理控制顶点的可分解性判断就可以得到期望的模型分解结果;同时该算法可以获得体特征,使得可以在特征这一粒度上进行特征删除和替换,以方便地完成模型的简化。     

Compound feature recognition by web grammar parsing

A method is presented to automatically recognize compound features using web grammar parsing on a solid model graph. A compound feature is a class of regional shapes with a variable topology. Examples of compound features are connected features, which contain a variable number of simple features connected together, and intersecting features, which intersect one another creating different shapes from the original simple features conceived. The simple features are regional shapes related to preestablished application processes. A solid object, stored as a boundary representation, is transformed to a web representation (a node-labeled graph) which is the input of a web parsing system for feature recognition. And a compound feature is described as a web grammar. From the web representation of an object shape, the compound feature recognition can be accomplished by parsing the web with the web grammar. The application of a web grammar enables a user to define a compound feature and makes feature recognition a formalized process for subsequent recognition.     

Extracting alternative machining features: An algorithmic approach

Automated recognition of features from CAD models has been attempted for a wide range of application domains. In this article we address the problem of representing and recognizing a complete class of features in alternative interpretation for a given design.We present a methodology for recognizing a class of machinable features and addressing the computational problems posed by the existence of feature-based alternatives. Our approach addresses a class of volumetric features that describe material removal volumes made by operations on three-axis vertical machining centers, including drilling, pocket-milling, slot-milling, face-milling, chamfering, filleting, and blended surfaces.This approach recognizes intersecting features and is complete over all features in our class; i.e., for any given part, the algorithm produces a set containing all features in our class that correspond to possible operations for machining that part. This property is of particular significance in applications where consideration of different manufacturing alternatives is crucial.This approach employs a class of machinable features expressible as MRSEVs (a STEP-based library of machining features). An example of this methodology has been implemented using the ACIS solid modeler and the National Institute's of Health C++ class library.     

Machinable volume extraction for automatic process planning

This paper describes an algorithm to extract machinable volumes that need to be removed from a stock, given a boundary model of the part. 'Machinable' implies that these volumes are extracted and arranged in a hierarchy such that each volume in the list is accessible for machining after its preceding volume has been machined, These volumes can be used to automate process planning and NC too! path generation. The algorithm identifies the cavity volumes in the part with respect to outermost faces in the part and fills them with the appropriate primitive volume to obtain the stock from which the part can be realized. Unlike the decomposition-based approaches reported, this algorithm directly identifies primitive volumes that when combined form the cavity volumes corresponding to the machining features. Primitive volumes enable handling parts with interacting Features and renders redundant the additional processing of machining features required to generate a NC tool path. The primitive machinable volumes arc cuboids, wedges and collars. The algorithm handles both prismatic and cylindrical (turned) components. Results of implementation for prismatic and turned components are provided and the extension of the algorithm to handle preformed stock is discussed.     

Identification of machining features based on available resources of cutting tools

In research on machining feature recognition, the problems of interacting features and availability of cutting tools are considered two major obstacles for developing industrial applications. In this research, a new machining feature recognition approach is developed to address these problems. In this work, a new concept called cutting mode is introduced to associate generic machining surfaces and cutting motions. In the feature recognition process, the machining surfaces of a part are first mapped to cutting modes, and these cutting modes are further mapped to available cutting tools. Among all the created candidate machining processes, heuristic rules are employed to identify the optimal solution that requires the minimum number of setups. When a number of machining surfaces are associated with a cutting tool in the same setup, these surfaces are grouped as a machining feature. Therefore the interacting features are recognised by the different cutting tools to produce these features. A database of available cutting tools is used to avoid the identification of features which cannot be machined in a machine shop. Three mechanical parts with interacting features are selected in the case studies to demonstrate the effectiveness of the developed approach.     

STEP-based automatic system for recognising design and manufacturing features

In the present work, a STEP-based platform-independent system for design and manufacturing feature recognition is developed. A manufacturing feature taxonomy with multiple levels, which is based on the access directions of the feature, is proposed. The system can recognise both design and manufacturing features from the lower level geometry and topology available in the STEP file. The developed system can recognise intersecting features, which is a major shortcoming of previous attempts based on neutral formats. A more complete feature relationship analysis than available in the literature is carried out to find the relationships between all the types of features. Removal volumes and access directions of the features are determined to couple the feature recognition with down line applications. Raw material geometry is also considered while recognising the features. The present system is limited to parts that can be machined on a three-axis machining centre.     

A digraph approach to TQM evaluation of an industry

Different total quality management (TQM) environments may be suggested to an organization for improving the quality of products, customer satisfaction, competitiveness and profitability by TQM experts. This paper identifies factors responsible for the TQM environment. All these factors are interacting with each other by different amounts. An attempt has been made to develop a mathematical model of the TQM environment from these interacting factors using a graph theoretic approach. In the graph theoretic model, a directed graph or digraph is used to represent abstract information of the system using directed edges, which is useful for visual analysis. The matrix model developed from the digraph is useful for computer processing. A permanent value of multinomial developed from the matrix represents the environment uniquely by a single number/index, which is useful for comparison, ranking and optimum selection. The method is quite flexible to accommodate new factors and market dynamics in global business in a bid to go for continuous improvement and breakthrough improvement in the environment, product, process and intellectual property rights (IPR).     

基于图的半监督学习的遮挡边界检测方法

提出了一种基于图的半监督学习检测深度图像中遮挡边界的方法。该方法首先获取已标记的像素点和待检测深度图像中的像素点作为顶点构建连通无向图,其次提取无向图中各像素点的最大深度差特征和八邻域有效深度差之和特征组成特征向量,根据像素点的特征向量计算无向图中顶点之间的相似性并将该相似性作为无向图中对应边的权值,然后根据图的半监督学习思想判断无向图中待检测像素点是否为遮挡边界点,最后可视化遮挡边界点得到深度图像中的遮挡边界。实验结果表明,所提方法尽管只需少量的标记样本,但在准确性上却同已有基于监督学习的方法相当。     

A new directed graph approach for automated setup planning in CAPP

The task of setup planning is to determine the number and sequence of setups and the machining features or operations in each setup. Now there are three main methods for setup planning, i.e., the knowledge-based approach, the graph-based approach and the intelligence algorithm-based approach. In the knowledge-based and graph-based approaches reported in the literature, the main problem is that there is no guarantee that all precedence cycles between setups can be avoided during setup formation. The methods to break precedence cycles between setups are to split one setup into smaller setups. However, the implementation of this method is difficult and complex. In the intelligence algorithm-based approach, the method to handle the precedence constraints is a penalty strategy, which does not reflect the influence of precedence constraints on setup plans explicitly. To deal with the above deficiencies, a new directed graph approach is proposed to describe precedence constraints explicitly, which consists of three parts: (1) a setup precedence graph (SPG) to describe precedence constraints between setups. During the generation of the SPG, the minimal number of tolerance violations is guaranteed preferentially by the vertex clusters algorithm for serial vertices and the minimal number of setups is achieved by using variants of the breadth-first search. Precedence cycles between setups are avoided by checking whether two serial vertex clusters can generate a cycle; (2) operation sequencing to minimise tool changes in a setup; and (3) setup sequencing to generate optimal setup plans, which could be implemented by a topological sort. The new directed graph approach will generate many optimal or near-optimal setup plans and provide more flexibility required by different job shops. An example is illustrated to demonstrate the effect of the proposed approach.     

A general steady state mathematical model for fin-and-tube heat exchanger based on graph theory

Fin-and-tube heat exchangers are widely used in air conditioners, chillers, etc. A lot of factors, including arrangement of refrigerant circuits, configure specification of fins and tubes, and operating conditions, have significant influence on the performance of fin-and-tube heat exchangers. For the purpose of fast design of high performance heat exchangers, a simulator reflecting the influence of these factors is necessary. In this paper, a general steady state mathematic model based on the graph theory is presented. With the help of the directed graph and graph-based traversal methods (Breadth-first search and Depth-first search), this model is capable to describe any flexible refrigerant circuit arrangement, and quantify the refrigerant distribution in the refrigerant circuit and heat conduction through fins. An alternative iteration method is also developed to solve the conservation equations, which can shorten the simulating time effectively. The model is verified with the experimental results, and the maximum error is within ±10.0%. A simulator based on this model has been used for designing practical fin-and-tube heat exchangers.     

Adaptive Bearing Fault Diagnosis based on Wavelet Packet Decomposition and LMD Permutation Entropy

Bearing fault signal is nonlinear and non-stationary,therefore proposed a fault feature extraction method based on wavelet packet decomposition( WPD) and local mean decomposition( LMD) permutation entropy,which is based on the support vector machine( SVM) as the feature vector pattern recognition device.Firstly,the wavelet packet analysis method is used to denoise the original vibration signal,and the frequency band division and signal reconstruction are carried out according to the characteristic frequency. Then the decomposition of the reconstructed signal is decomposed into a number of product functions( PE) by the local mean decomposition( LMD),and the permutation entropy of the PF component which contains the main fault information is calculated to realize the feature quantization of the PF component. Finally,the entropy feature vector input multi-classification SVM,which is used to determine the type of fault and fault degree of bearing.The experimental results show that the recognition rate of rolling bearing fault diagnosis is 95%. Comparing with other methods,the present this method can effectively extract the features of bearing fault and has a higher recognition accuracy.     

Vertex Cover Optimization Using a Novel Graph Decomposition Approach

The minimum vertex cover problem (MVCP) is a well-known combinatorial optimization problem of graph theory. The MVCP is an NP (nondeterministic polynomial) complete problem and it has an exponential growing complexity with respect to the size of a graph. No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale. However, several algorithms are proposed that solve the problem approximately in a short polynomial time scale. Such algorithms are useful for large size graphs, for which exact solution of MVCP is impossible with current computational resources. The MVCP has a wide range of applications in the fields like bioinformatics, biochemistry, circuit design, electrical engineering, data aggregation, networking, internet traffic monitoring, pattern recognition, marketing and franchising etc. This work aims to solve the MVCP approximately by a novel graph decomposition approach. The decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures. A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or paths. In order to reduce complexity of the algorithm a new strategy is also proposed. The reduction strategy can be used for any algorithm solving MVCP. Based on the graph decomposition and the reduction strategy, two algorithms are formulated to approximately solve the MVCP. These algorithms are tested using well known standard benchmark graphs. The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.