Hausdorff distance measure is very important in CAD/CAE/CAM related applications. This manuscript presents an efficient framework and two complementary subalgorithms to directly compute the exact Hausdorff distance for general 3D point sets. The first algorithm of Nonoverlap Hausdorff Distance (NOHD) combines branch-and-bound with early breaking to cut down the Octree traversal time in case of spatial nonoverlap. The second algorithm of Overlap Hausdorff Distance (OHD) integrates a point culling strategy and nearest neighbor search to reduce the number of points traversed in case of spatial overlap. The two complementary subalgorithms can achieve a highly efficient and balanced result. Both NOHD and OHD compute the exact Hausdorff distance directly for arbitrary 3D point sets. We conduct a number of experiments on benchmark models and CAD application models, and compare the proposed approach with other state-of-the-art algorithms. The results demonstrate the effectiveness of our method.
Distance measure is the fundamental step for many applications in science and engineering areas [15, 41, 68]. Hausdorff distance can quantify the similarity between two arbitrary point sets without the necessity to establish the one-to-one correspondence between them. In most engineering applications, the number of point sets obtained by 3D model is not identical, and it is difficult to establish a one-to-one correspondence between them. Therefore, Hausdorff distance is suitable for measuring similarity between 3D models in engineering practice.
Hausdorff distance has drawn particular attention from scholars in many science and engineering fields, such as CAE/CAD/CAM [40, 68], pattern recognition [52, 63], similarity measure [16, 30, 32, 48], shape matching [5, 70], mesh model simplification , reconstruction of curved and surfaces [11, 12, 18, 35], and penetration depth [66, 73].
It is a hard task to improve the efficiency of the algorithm while ensuring the accuracy in calculating the Hausdorff distance. Generally speaking, the similarity measure for 3D models based on Hausdorff distance faces at least three problems: (1) Most of the previous algorithms of similarity measure based on Hausdorff distance have a strong disciplinary background, and are short of generalization; (2) Since the Hausdorff distance measure is computationally intensive, it is restricted to applications for large scale data; (3) Furthermore, in some applications, computing exact Hausdorff distance needs additional cost (for example, 3D point sets are pre-processed and rasterized into voxel models), which worsen efficiency of some state-of-the-art algorithms.
To the best of our knowledge, it is difficult to cover above limitations in one single processing algorithm. For an example, the state-of-the-art algorithm of 2015 (EARLYBREAK)  can achieve the high efficiency in processing the medical images (considered as voxel data), while it is low efficiency in calculating spatial objects of highly overlapping.
How to find a new approach to cover above problems as much as possible and achieve an efficient and balanced result is becoming a challenge. In this manuscript, based on whether the pair of point sets are nonoverlaped or overlaped, an efficient computation framework is presented with two complementary subalgorithms, Nonoverlap Hausdorff Distance (NOHD) and Overlapped Hausdorff Distance (OHD).
• The NOHD algorithm builds an Octree for input point sets, and uses the principle of branch-and-bound and early breaking to prune the branches of Octree efficiently, which can reduce the number of nodes that have to be traversed.
• However, the efficiency is poor when applying the NOHD algorithm to two point sets of seriously overlapped. Therefore, we propose the OHD algorithm to solve this problem. The OHD algorithm builds adaptive Octree, and also designs point culling strategy which can reduce the traversed points. Both NOHD and OHD compute the exact Hausdorff distance directly for arbitrary 3D point sets. Under the subalgorithms of NOHD and OHD, we present a new Hausdorff distance computing procedure, which can choose the complementary subalgorithms to compute the Hausdorff distance with different spatial relationship of the pair of point sets.
The remainder of this manuscript is organized as follows. In Section 2, we briefly review the related work. Section 3 describes the problem and challenge for computing Hausdorff distance. In Section 4, we present two novel subalgorithms, the NOHD algorithm and the OHD algorithm. In Section 5 we construct an integrated framework of computing the Hausdorff distance. Section 6 conducts experiments with analysis. Finally, the conclusions and future work are discussed in Section 7.
2.1Curves and surfaces
The problem of efficient calculation of the Hausdorff distance has become a hot topic in this field, has influenced the progress in CAD/CAE/CAM.
Alt et al.  presented an algorithm for Hausdorff distance computation based on a characterization of the possible points where the distance can be attained. Chen et al.  presented an algorithm for computing the Hausdorff distance between two B-Spline curves, which improves the reference  by using a pruning technique to reduce computation time.
Bai et al.  presented an algorithm for computing an approximate Hausdorff distance between planar free-form curves by approximating the input curves with polylines and then computing the Hausdorff distance between the line segments. Kim et al.  presented a compact representation for the Bounding Volume Hierarchy (BVH) of Non-uniform rational Basis spline (NURBS) surfaces using Coons patches, which could be used to construct a BVH-based algorithm for computing the Hausdorff distance between NURBS surfaces.
Kim et al.  developed a real-time algorithm for the precise Hausdorff distance between planar freeform curves using hardware depth buffer.
Recently, Krishnamurthy et al. [28, 38, 39] developed a GPU algorithm that computes the Hausdorff distance between NURBS surfaces. Interactive speeds are obtained by performing GPU traversal of a bounding-box hierarchy and selectively culling pairs of bounding boxes that could not contribute to the Hausdorff distance.
The Hausdorff distance computation for large polygonal meshes has been a very difficult task to implement for real-time application.
Atallah  provided an algorithm for computing the Hausdorff distance for a special case of point sets, namely non-intersecting, convex polygons. The algorithm has the complexity of where m and n are the vertex counts. Alt et al.  presented a method based on the Voronoi diagram which requires running time. Barton et al.  presented an deterministic algorithm for computing the precise (up to floating point) Hausdorff distance between polygonal meshes.
Due to the complexity of exactly computing the Hausdorff distance, the approximate algorithms have been proposed as practically solutions [8, 22, 26, 47]. Llanas  proposed two approximate algorithms based on random covering for non-convex polytopes. Guthe et al.  proposed an approximate algorithm for calculating the Hausdorff distance between mesh surfaces. This algorithm makes use of the specific characteristics of meshes to avoid sampling all points in the compared surfaces. These regions are then further subdivided and regions that cannot attain the Hausdorff distance are purged away.
Tang et al.  implemented an approximate algorithm that is based on BVH that is preprocessed in advance (before real-time computation). Their implementation is very fast in practice, running at interactive speed for complicated dynamics scene.
Above algorithms are based on the specific characteristics of meshes and thereby lacks generality. Some general methods are proposed. Given two nonempty point-sets with and points respectively, a brute-force algorithm to compute the Hausdorff distance requires time.
Alt et al.  presented a method based on the Voronoi diagram which requires running time. For , Alt et al.  proposed a randomized algorithm with expected time. Papadias et al.  proposed an algorithm for finding aggregate nearest neighbors (ANN) in databases.
Nutanong et al.  extended the algorithm proposed in  to avoid the iteration of all points in . The aggregate nearest neighbor was executed simultaneously in both directions, where two R-Trees (one for each point set) were used at the same time.
Taha et al. proposed the randomization and the early breaking optimization in reference  to achieve efficient, almost linear, calculation. This optimization avoid scanning all voxel pairs by identifying and skipping unnecessary rounds.
The purpose of this study is to explore a general method to compute the exact Hausdorff distance for CAD/CAE/CAM applications and to ensure the efficiency.
The Hausdorff distance  is the maximum deviation between two models, measuring how far two point sets are from each other . Given two nonempty point sets and , the Hausdorff distance between and is defined as .
denotes the Hausdorff distance in . and are the one-sided value from to and from to , respectively.
The Hausdorff distance is often used in engineering and science for pattern recognition, shape matching and error controlling. If is a small value, and are partially matched; If is equal to zero, then and are matched exactly.
3.2NAIVEHDD and one-side BREAK algorithm
The basic computing method of the Hausdorff distance is described as Algorithm 1.
The outer loop of the NAIVEHDD algorithm traverses all points in , while the inner loop traverses all points in . The time complexity of NAIVEHDD algorithm is .
|Algorithm 1. NAIVENDD algorithm|
| Input: Two finite point sets , Output: Directed Hausdorff distance |
Taha et al.  pointed out that it is not necessary for inner loop (4 7 lines) of the NAIVEHDD algorithm to traverse all points in , and proposed an early break strategy in Algorithm 2. In the inner loop of Algorithm 2, when a distance is found that is below the current cmax, continuing to traverse the remaining points in makes no contribution to update cmax. Therefore, the breaking of the inner loop at that time will reduce the cost of traversing . In the best case when the inner loop meets the breaking condition at the first execution and then break, the ideal time complexity of the EARLYBREAK algorithm is .
The original algorithm published in  missed one line and had been corrected in a note.
|Algorithm 2. EARLYBREAK algorithm|
| Input: Two finite point sets , Output: Directed Hausdorff distance |
3.3Challenge and analysis
In Algorithm 2, the event of meeting the condition that is over cmax is denoted as , . The event of meeting the condition that is less than cmax is denoted as e, . the breaking condition for the inner loop (6 12 lines) is that event occurs.
Assuming that the inner loop has been implemented for times before the loop terminates, then the probability density function of can be expressed as:
The expectation of (the number of execution of the inner loop) is equal to the expectation of ,
According to Eq. (5), the number of tries in the inner loop is inverse proportion to . Meanwhile, Taha et al.  pointed out that depends on and the distribution of all the pair of distances between and , rather than directly on the number of .
The larger is, the larger cmax is, and the larger is. The average probability of the breaking condition can be expressed as:
Where represents the probability distribution function of all the distances between and , and is a constant representing the relationship between cmax and the final Hausdorff distance.
It should be noticed that the smaller is, the larger is, leading to a decreased efficiency of the EARLYBREAK algorithm. In the worst case, when the between and is equal to zero, the inner loop will traverse all the points in , and the time complexity of the EARLYBREAK algorithm is equal to that of NAIVEHDD algorithm.
In order to overcome the deficiency in overlap situation, Taha and Hanbury  proposed a strategy to exclude the intersection point set between and . As shown in Fig. 1, for given grid sets (brown box in Fig. 1(a)) and (blue box in Fig. 1(b)), (green box in Fig. 1(c)) is first calculated. Then the grid set is computed as . At last, the is used to calculate the Hausdorff distance in EARLYBREAK algorithm as .
According to the property of Hausdorff distance, . Obviously, the time complexity of is significantly better than that of . Therefore, the EARLYBREAK algorithm has achieved outstanding results in calculating the Hausdorff distance of medical images.
There are still some problems for EARLYBREAK algorithm . Firstly, the execution number of the inner loop was reduced by early breaking and random initialization, but the execution number of the outer loop was not reduced. Secondly, when the similarity between and is high (e.g., the Hausdorff distance is small), the strategy of early breaking fails to reduce the time complexity. Thirdly, the EARLYBREAK algorithm is inherently and naturally suitable for voxel model and medical image, not for general 3D model, such as 3D point cloud in CAD/CAE/CAM. Finally, if we simply apply the EARLYBREAK algorithm for general 3D models, the original 3D model have to be preprocessed and rasterized into voxel model, which is the approximation for the original 3D models. Therefore, the final result will be approximate one, not exact one.
This manuscript tries to address the above problems as much as possible, and present a new approach to directly and efficiently calculate the Hausdorff distance for general 3D model with an exact result.
4.The proposed two subalgorithms
Firstly, due to the fact that the two subalgorithms are based on Octree, a set of definitions related to lower bound and upper bound are provided. In the case of spatial nonoverlap, a subalgorithm named NOHD was proposed. Then, we analyzed the complexity for computing the Hausdorff distance in the case of spatial overlap and proposed the OHD algorithm.
4.1The definition of bound and the description of overlap
The Hausdorff distance between and can be actually obtained by calculating the Hausdorff distance between and Octree (constructed from ). The principles of branch-and-bound  have be adopted in our NOHD and the OHD algorithms to reduce the number of nodes to be traversed. Therefore, before presenting the NOHD and OHD algorithms, the related definitions are given as follows.
Definition 1. Lower bound of point to node. Given a singleton set and a node in an Octree, a lower bound of the Hausdorff distance from to the elements confined by is defined as Eq. (8),
As shown in Fig. 2(a), the lb() of Hausdorff distance between point and node can be obtained by calculating the minimum possible distance between point and the nearest object (vertexes, edges, surfaces) of node .
Definition 2. Lower bound of point set to node. Given a point set and a node in an Octree, a lower bound of the Hausdorff distance from to the elements confined by is defined as Eq. (9),
As shown in Fig. 2(b), the LB() of Hausdorff distance between the point set to node can be obtained by calculating the minimum value of the lower bound between all points in the point set and node .
Definition 3. Upper bound of point to node. Given a singleton set and a node in an Octree, a upper bound of the Hausdorff distance from to the elements confined by is defined as Eq. (10),
As shown in Fig. 2(c), the ub() of the Hausdorff distance between point and node can be obtained by calculating the maximum possible distance between point and the farthest object (vertex) in node .
Definition 4. Upper bound of point set to node. Given a point set and a node in an Octree, a upper bound of the Hausdorff distance from to the elements confined by is defined as Eq. (11),
As shown in Fig. 2(d), the of Hausdorff distance from the point set to node can be obtained by calculating the minimum value of the upper bound from all points in the point set to node .
According to the analysis in Section 3, when the value of Hausdorff distance between and is relatively small as two objects overlap, the previous algorithms (including state-of-the-art EARLYBREAK in the reference ) cannot efficiently reduce the time complexity. However, the small value of Hausdorff distance occurs in many engineering applications. Therefore, before presenting our algorithms, the overlap is described.
Given an object in 3D space, the range for bounding box BB is described as follows:
Similarly, given an object in 3D space, the range for bounding box BB is described as follows:
In context of this manuscript, the description of overlapping between BB and BB can be written as follows.
As shown in Fig. 3(a), when , it is denoted as . It means there is nonoverlapping relationship between and .
As shown in Fig. 3(b), when && && , it is denoted as . It means there is overlapping relationship between and .
4.2The first subalgorithm: NOHD
4.2.1The basic idea of NOHD and the definition of priority queue
In order to reduce the outer loop number of traversal of , the NOHD algorithm is proposed.
Firstly, the calculation of Hausdorff distance from to is converted into calculating the Hausdorff distance from Octree (constructed from ) to . The lower bound of the Hausdorff distance from any node in Octree to is denoted as LB(), and the upper bound of the Hausdorff distance is denoted as UB(). By traversing all the nodes in Octree and updating LB(), the final LB() is the Hausdorff distance between and at end of NOHD algorithm.
Secondly, NOHD algorithm defines a new concept of entry of Decreasing Priority Queue (DPQ) to enhanced the principles of branch-and-bound, and therefore to reduce the number of nodes of Octree to be traversed. In the context of Hausdorff distance calculation, the definition for entry of DPQ is given as follows.
Definition 5. . Attributes of each Entry(, MinUB) are described as follows: (i) Node node in an Octree for , which could be an object node or a non-object node (index node); (ii) Distance MinUB the minimum value of the upper bound between all points in the point set to node , that is, the UB().
The DPQ which arranges Entries(, MinUB) in decreasing order according to the key value of MinUB.
4.2.2NOHD algorithm description
|Algorithm 3. NOHD algorithm|
| Input: Two finite point sets , Output: Directed Hausdorff distance |
The NOHD algorithm is described in Algorithm 3. The initialization involves the following steps: (i) To create an Octree Octree for point set ; (ii) To create a priority queue DPQ; (iii) to insert the root of Octree with an initial MinUB of into DPQ. (iv) To initialize MaxLB to 0.
After the initialization, DPQ contains a single entry with the root of Octree as the associated node. For each iteration of the while loop (5 24 lines), the head Entry(, MinUB) is removed from DPQ. There are two cases depending on whether is an object or not.
• In case 1, if is not a point object, the children of (8 17 lines) are processed.
• In case 2, if is a point object (19 22 lines), the minimum distance from point to point set is obtained by calling Algorithm 5, and is compared with MaxLB. After comparison, the greater one is the final Hausdorff distance.
In processing of node , two culling procedures are performed.
The first culling is based on whether MinUB is greater than MaxLB or not, the following steps are processed respectively:
• If MinUBMaxLB, all child nodes in node should be traversed (9 15 lines);
• If MinUBMaxLB, node cannot generate a distance greater than the current MaxLB, and it is pruned away.
In the second culling, CubeToPoints (Algorithm 4) is called, and a breaking flag of child node is returned.
• If the flag is “false”, the child node cannot generate a distance that contributes to the final Hausdorff distance, and it is pruned away.
• If the flag is “true”, the child node may generate a distance that contributes to the final Hausdorff distance, and then it is inserted into DPQ.
The pseudocode of CubeToPoints is described as Algorithm 4, into which three parameters are input: child nodes , points set , and the currently greatest lower bound MaxLB.
The Algorithm 4, firstly initializes the flag, the UB(, ) and LB(), and then computes the upper and lower bounds between all points in and child node . For a given point of , the upper bound of to child node is calculated. If the ub(, ) is below MaxLB, then the minimum upper bound from all points in to child node must be below MaxLB. Thus, child node cannot generate a distance over MaxLB, and then the Flag is assigned as “false”, and the whole for loop breaks. When the flag of Algorithm 4 is returned as “false”, the node will be pruned away by Algorithm 3.
|Algorithm 4. CubeToPoints(C, B, Max LB)|
| Input: Child Node , Point set , MaxLBOutput:UB(), LB(), Flag|
The pseudocode of PointToPoints is shown as Algorithm 5, which takes three parameters: point of node , points set , and the greatest lower bound MaxLB.
Algorithm 5 calculates the minimum distance from point to . For a given of , the distance of to of child node is calculated. And if is less than MaxLB, the minimum distance between point and must be less than MaxLB. Since it is impossible to generate a distance over the current lower bound MaxLB between point and , the whole for loop ends.
The combination of Algorithms 4 and 5 can efficiently reduce the time complexity of calculating the distance from to .
|Algorithm 5. PointToPoints(x, B, MaxLB)|
| Input: Point , Point set , MaxLBOutput:cmin|
4.3Difficulties for computing hausdorff distance in overlap situation
In NOHD algorithm, the Hausdorff distance between and is calculated with , as shown in Fig. 4.
In processing Octree, the NOHD algorithm traverse the child node of current node and insert it into DPQ when the UB(, ) is over MaxLB. Once a UB(, ) below MaxLB occurs, the traverse on child node of current node will end and the pruning strategy will be executed. For example, if LB(, 55) is the latest MaxLB, the nodes 2 and 7 are pruned away because UB(, 2) and UB(, 7) are less than LB(, 55). Therefore, MaxLB is constantly updated and the nodes of no-contribution are also pruned away constantly, and finally the Hausdorff distance is obtained.
Figure 5 shows a situation, in which and are highly overlapping in 3D space. According to analysis in previous Sections, there is no efficient solutions (including the EARLYBREAK algorithm in reference  and NOHD algorithm in this manuscript) in this situation for two reasons.
• Firstly, along with the increment of Octree depth, the lower bound from to most nodes of Octree is zero (e.g., LB(, 5)). Therefore, MaxLB (with zero as the minimum distance) cannot be updated because the upper bound of to most nodes in Octree is over MaxLB, and the pruning strategy cannot be executed in Algorithms 3 and 4.
• Secondly, when and are highly similar (e.g., small , the strategy of early breaking in Algorithm 5 will fail in most cases.
Based on the above analysis, both the EARLYBREAK algorithm and NOHD algorithm cannot efficiently reduce the time complexity in overlap situation. Therefore, we proposed the second subalgorithm, the OHD algorithm, to deal with this situation.
4.4The second subalgorithm: OHD
The OHD algorithm computes the Hausdorff distance between and Octree (constructed from ), while NOHD algorithm calculates the Hausdorff distance from Octree (constructed from ) to .
Since the lower bound of the Hausdorff distance between any point in and any node in Octree is , the distance between and the nearest node in Octree is Minlb, where .
By constantly traveling and updating Minlb, the maximum Minlb is found (e.g., ). In this way, the ) can be found without traversing all points in in OHD algorithm, as shown in Algorithm 6.
|Algorithm 6. OHD algorithm|
| Input: Two point set , Output: Directed Hausdorff distance |
The key steps of Algorithm 6 is organized as follows.
• Firstly, the Approximate Hausdorff Distance (AHD) between and is Initialized.
• Secondly, an Octree for is built with the given resolution (AHD).
• Thirdly, a strategy of point culling is applied, where any point in will be culled if it has no contribution to the final Hausdorff distance.
• Finally, the distance between the candidate point and the nearest point in Octree is calculated as Minlb, which is used to update current Maxlb if it is greater than the Maxlb. The final Hausdorff distance is the Maxlb at end of the loop.
4.4.1Initialization of Approximate Hausdorff Distance (AHD)
In typical approximate algorithm , the initial value of AHD is zero at the time when the outer loop is started. With the gradual execution of outer loop, AHD will monotonically increase and reach the value near to final Hausdorff distance after limited times of the loop.
Therefore, the initialization of AHD can be quickly implemented after limited number of loops, which is set as in OHD algorithm. According our experiment research, this manuscript gives the recommendation as follows: the 1/100.
4.4.2Point culling to reduce number of out iterations for exact algorithm
A strategy of point culling is proposed to reduce number of out iterations, that is, to reduce the point number of to be traversed in outer loop.
An Octree Octree with the given resolution (AHD) is built as shown in Fig. 6, where the cube legends represent leaf nodes of Octree, and the red point legends represent and the black point legends represent .
The points of can be divided into two classes: the leaf-node points and the non-leaf-node points.
• The leaf-node points (such as: ) are spatially located inside the leaf node of Octree, and the temporary Hausdorff distance generated by these points cannot be over AHD and can be safely culled away.
• The non-leaf-node points (such as: ) are not located in the leaf node of Octree, and the temporary Hausdorff distance generated by these points may be over AHD. Therefore, only these points are remained to be further processed by the OHD algorithm.
Therefore, our strategy in OHD algorithm is to cull these leaf-node points.
4.4.3The branch-and-bound and the nearest neighbors distance
The lower bound of the Hausdorff distance between any point in and any node in Octree is , so the distance between and the nearest node in Octree is . By constantly traveling and updating of Minlb, the maximum Minlb is found (e.g., ).
In order to efficiently reduce number of inner iterations, that is, to avoid traversing all of nodes in Octree in inner loop, the OHD algorithm enhances the existing branch-and-bound approach with a new concept of entry of Ascending Priority Queue (APQ). In context of this manuscript, the definition for entry of APQ is given as follows.
Definition 6. Entry(N, Minlb). Attributes of each Entry(, Minlb) are described as follows: (i) Node node in an Octree for , which could be an object or a non-object(index node); (ii) Distance Minlb the lower bound of point of to node , that is, lb().
Where, the APQ arranges Entries(, Minlb) in ascending order according to the key value Minlb.
The NNDist algorithm is shown as Algorithm 7. The initialization (1 3 lines) consists of the following steps: (i) initialize Minlb to ; (ii) create a priority queue APQ; (iii) insert the root of Octree with an initial Minlb of 0 into APQ.
After the initialization, APQ contains a single entry with the root of Octree as the associated node. For each iteration of the while loop (4 25 lines), the head Entry(, lb(, is dequeued from APQ. There are two cases depending on whether is an object or not.
Case 1: If is not a point object (7 15 lines), two culling procedures are performed.
– The first culling is based on whether lb(, ) from to is less than Minlb or not: if lb(, Minlb, node cannot generate a distance less than the current Minlb, and thus should be pruned away; if lb(, Minlb, all child nodes in node should be traversed (813 lines).
– The second culling is based on whether lb(, ) from to child node is over Minlb or not: if lb(, Minlb, child node cannot generate a distance less than the current Minlb, and it should be pruned away; if lb(, Minlb, child node may be generate a distance less than the current Minlb, and node is inserted into APQ.
Case 2: If is a point object (17 23 lines), all points of current node will be processed.
– First, the distance from to points confined by is computed.
– Second, if is below Maxlb, the cannot contribute to the final Hausdorff distance, the APQ is cleared.
– Third, after comparing with Minlb, the smaller one is Minlb.
|Algorithm 7.NNDist(a, Octree)|
| Input: Two finite point set , MaxlbOutput:Minlb|
5.An efficient framework based on spatial relationship
Based on spatial relationships of and , an efficient framework was proposed, as illustrated in Algorithm 8. Given the degree of overlap between a pair of point sets, the Algorithm 8 choose suitable subalgorithm to compute Hausdorff distance in a way of high efficiency and balance.
As shown in Fig. 7, the Hausdorff distance between and is continuously changing from nonoverlapping to fully overlapping.
|Algorithm 8. The pseudocode of the proposed framework|
| Input: Two finite point set , Output: Hausdorff distance |
When , the NOHD algorithm can efficiently reduce the Octree traversal cost by the strategies of branch-and-bound and early breaking, so the efficiency of the NOHD algorithm is higher than the EARLYBREAK algorithm. Therefore, in our algorithm framework, the NOHD algorithm was employed to compute the Hausdorff distance in this situation.
When ( and is overlapping as described in Section 4), two algorithms will be called respectively based on the degree of overlap in our algorithm framework. We describe the degree of overlap with , where 0 1:
• is 0 when and are just contact;
• is 1 when and are fully overlapping.
We also introduce a threshold , which is recommended as 0.33 based on experiments in this manuscript. There are two cases based on the value of threshold in our algorithm framework.
• When 1, the OHD algorithm excludes a large number of points in that have made no contribution to the final Hausdorff distance. So the efficiency of the OHD algorithm is higher than the EARLYBREAK algorithm. Therefore, the OHD algorithm was employed to compute the Hausdorff distance in this situation.
• When 0 , only a few points can be excluded by the OHD algorithm, so the efficiency of the OHD algorithm is lower than the EARLYBREAK algorithm. Therefore, the EARLYBREAK algorithm was employed to compute the Hausdorff distance in this situation.
Besides the adaptively and balance, the proposed algorithm can calculate the Hausdorff distance efficiently for general 3D model with an exact result. Under the background, any new and efficient algorithm in future can be easy integrated into the framework, just as the EARLYBREAK algorithm.
A number of experiments are conducted to verify the efficiency and effectiveness of the proposed algorithm, which is implemented using on Windows 7/Inter(R) core(TM) i7-4470 (3.4 GHz)/8.00 GB of memory with C.
We used the code from the PCL-1.6.0 (http://www. pointclouds.org/)  for building Octree. To evaluate the performance of the proposed algorithm, it was tested with three different types of data, namely random 3D Gaussians, point cloud models and CAD/CAE models generated from CAD software.
• In the first experiment (Section 6.1), 3D point sets were generated based on random Gaussians and were used to test the effectiveness of the early breaking strategy for Octree in the NOHD algorithm.
• In the second experiment (Section 6.2), 3D point sets were generated based on random Gaussians and were used to test the effectiveness of the point culling strategy in the OHD algorithm.
• In the third experiment (Section 6.3), 3D point sets were used to test the effect of depth on the efficiency of the NOHD algorithm and the effect of coefficient on the efficiency of OHD algorithm.
• In the fourth experiment (Section 6.4), 3D models generated from CAD software were used to compare the proposed algorithm with the EARLYBREAK algorithm under Motion.
• In the last experiment (Section 6.5), several examples from typical fields (such as point cloud models and CAD/CAE models) are tested among the NAIVEHDD algorithm, the INC algorithm, the EARLYBREAK algorithm and the proposed algorithm.
6.1Test for early breaking in the NOHD algorithm
In order to verify the idea of NOHD early breaking strategy in general, random Gaussians data were used for testing. 300 pairs of nonoverlapping random Gaussian point clouds were generated. The number of points in each pair varies from 3 thousands to 0.3 million. The effectiveness of our early breaking strategy in the NOHD algorithm was tested with different number of points in and .
In order to verify the effectiveness of NOHD early breaking strategy, we denoted the algorithm that had removed the early breaking strategy from the NOHD algorithm as the NOHD algorithm.
As shown in Table 1, the fourth column and fifth column report the average of 10 computation results for the NOHD algorithm and the NOHD algorithm, individually. The average time cost increased along with the increase in the number of and . However, compared with the NOHD algorithm, the NOHD algorithm can efficiently reduce the average time cost by the early breaking strategy.
|Pairs||Set size||Execution time (sec)|
|(1)||3 K||3 K||0.03589||0.02247|
|(2)||15 K||10 K||0.14427||0.09993|
|(3)||23 K||27 K||0.33513||0.23967|
|(4)||43 K||41 K||0.45207||0.3058|
|(5)||49 K||64 K||0.65733||0.3232|
|(6)||64 K||78 K||0.96393||0.48947|
|(7)||77 K||51 K||0.58567||0.42353|
|(8)||86 K||35 K||0.65933||0.58753|
|(9)||105 K||113 K||1.07733||0.74767|
|(10)||123 K||31 K||1.14933||0.74567|
|(11)||131 K||93 K||1.1878||0.70933|
|(12)||145 K||110 K||1.2986||0.8624|
|(13)||169 K||160 K||1.5378||0.99287|
|(14)||210 K||220 K||2.07807||1.34207|
|(15)||231 K||239 K||2.2312||1.38447|
6.2Test for point culling in OHD algorithm
In order to verify the validity of the point culling strategy in the OHD algorithm, the same data sets as Section 6.1 are used. We denoted the algorithm that had removed the point culling strategy from the OHD algorithm as the OHD algorithm.
|Pairs||Set size||Execution time (sec)|
|(1)||4 K||4 K||1.577||0.56087|
|(2)||6 K||12 K||3.1044||1.67333|
|(3)||8 K||4 K||2.617||0.92533|
|(4)||12 K||16 K||5.385||2.11597|
|(5)||21 K||15 K||8.6174||2.04287|
|(6)||29 K||24 K||12.07487||5.299|
|(7)||29 K||17 K||10.78667||3.97227|
|(8)||37 K||22 K||15.1934||3.6774|
|(9)||39 K||32 K||17.3132||6.28933|
|(10)||40 K||34 K||15.83447||5.7202|
|(11)||40 K||28 K||16.64947||5.48007|
|(12)||41 K||35 K||20.3706||9.5222|
|(13)||44 K||26 K||16.0276||4.86627|
|(14)||46 K||47 K||20.1598||7.574|
|(15)||51 K||39 K||20.69647||7.33847|
As shown in Table 2, the fourth column and fifth column report the average of 10 computation results for the OHD algorithm and the OHD algorithm, individually. The OHD algorithm did not adopt the point culling strategy and Algorithm 7 should be called for each points in , while the OHD algorithm used the point culling strategy to exclude the points with no contribution to the final Hausdorff distance and Algorithm 7 is called for only part of points in . Therefore, compared with the OHD algorithm, the OHD algorithm can efficiently reduce the time cost with the point culling strategy.
6.3Analysis of some important parameters
To further analyze various characteristics of the method, we discussed the effect of depth on the efficiency of the NOHD algorithm and the effect of coefficient on the efficiency of OHD algorithm.
In context of this manuscript, in the case of spatial nonoverlap, the calculation of Hausdorff distance from to is converted into calculating the Hausdorff distance from Octree to .
We need to set the depth of Octree before constructing the Octree from . In general, the time cost of constructing an Octree is proportional to the depth of Octree. We selected three pairs of random Gaussian point clouds to test the effect of depth on the efficiency of the NOHD algorithm. The relationship between the depth and the average execution time from 10 trials is shown in Fig. 8. The efficiency of NOHD algorithm is improved with the increasing of the value of depth, and the high efficiency is obtained when depth is increased to five or six. Moreover, with a bigger value of depth, the efficiency is decreased.
According to the experimental research, this manu- script recommended the depth of six.
When and were highly overlapping, the calculation of Hausdorff distance from to is converted into calculating the Hausdorff distance between and Octree.
The Octree is built with the given resolution (AHD). In context of this manuscript, the greater the value of AHD is, the more efficiency of the point culling within OHD algorithm is. Thus, the coefficient directly effects the value of AHD, and indirectly effects the efficiency of computing the Hausdorff distance by OHD algorithm. We selected three pairs of random Gaussian point clouds to test the effect of coefficient on the efficiency of the OHD algorithm. The relationship between the coefficient and the average execution time from 10 trials is shown in Fig. 9. The efficiency of OHD algorithm is improved with the decreasing of , and the high efficiency is obtained when is set as 1/80. Moreover, with a smaller value of , the efficiency is decreased as a result of that the AHD is much less than the Hausdorff distance.
According to our experimental research, this manu- script gives the recommendation as follows: the 1/100.
6.4Hausdorff distance under motion
An important variation of the Hausdorff distance problem is to find the distance when there is a relative movement between two models, such as penetration [66, 73]. This problem is known as geometric matching under the Hausdorff distance metric. In this section, we computed the Hausdorff distance between a fixed model and a moving model to fully illustrate the efficiency of the proposed algorithm.
Two models and with same shape and same size are shown in Fig. 10(a). As demonstrated in Fig. 10(b), with the decrease in the Hausdorff distance, the average time cost gradually increased. When and were highly overlapping, the time cost reached the peak value. With the increase in the Hausdorff distance, the time cost gradually decreased.
When two models were nonoverlapping, the average time cost of the NOHD algorithm was significantly better than that of the EARLYBREAK algorithm. When the degree of overlap fell into the range of 0 0.33, the EARLYBREAK algorithm was integrated into our algorithm framework. When the degree of overlap fell into the range of 0.33 1, the time cost of the OHD algorithm was significantly better than that of the EARLYBREAK algorithm.
As shown in Fig. 11, although two models are tested with different shape and size, the proposed algorithm achieved the same result as above.
6.5Point cloud models and CAD/CAE/CAM models
In order to further evaluate its performance, the proposed approach was applied to several examples from different fields (such as point cloud models and CAD/ CAE/CAM models) for experimental comparison.
Three pairs of point cloud models and three pairs of CAD/CAE/CAM models were tested in this section as shown in Fig. 12. The step of calculating the Hausdorff distance between the models was as follows: (1) Models and were converted point sets and ; (2) the Hausdorff distance was calculated by Eqs (1)–(3).
|Index||Execution time (sec)|
The time costs in calculating the Hausdorff distance through the NAIVEHDD algorithm, the incremental Hausdorff distance calculation algorithm (INC) , the EARLYBREAK algorithm , and the proposed algorithm were shown in Table 3 (The units of time is second).
According to the comparison of experiments, the time cost executed by the proposed algorithm in calculating the Hausdorff distance is significantly less than that executed by the NAIVEHDD algorithm, and is distinctly less than that executed by the EARLYBREAK algorithm.
The proposed algorithm is composed of the NOHD, the OHD and the EARLYBREAK algorithm. The NOHD algorithm combines branch-and-bound with early breaking to cut down the Octree traversal time in case of spatial nonoverlap. The OHD algorithm integrates a point culling strategy and nearest neighbor search to reduce the number of points traversed in case of spatial overlap.
Therefore, the high efficiency of the NOHD algorithm and the OHD algorithm in the proposed efficient framework was confirmed once again.
7.Conclusion and future work
An efficient framework with two complementary subalgorithms is presented with theory analysis. The experiments also demonstrate that the proposed approach, as a whole, outperforms the state-of-the art algorithms [54, 65]. The main contributions are summarized as follows:
(1) Besides individual algorithms, an efficient framework is presented, which automatically chooses the suitable subalgorithms to compute the Hausdorff distance in different spatial relationship between a pair of point sets. In this way, the long-standing limitation of computing Hausdorff distance can be relaxed.
(2) In NOHD algorithm, we present a strategy synthesizing branch-and-bound and early breaking, and efficiently reduce cost of the Octree traversal. In OHD algorithm, we construct a strategy combining point culling and nearest neighbor searching, and efficiently reduces the cost of points traverse. And different from the state-of-the art algorithm [54, 65], the proposed algorithms can directly calculate a pair of the 3D point sets without transforming them into voxel model.
(3) The experiments demonstrate that the proposed approach, as a whole, outperforms the state-of-the art algorithms .
(4) The proposed framework can easily integrate other algorithms. Therefore, any subalgorithm with a high efficiency can be added into this framework in the future.
Since distance measurement is fundamental operation in applications of science, engineering and industry [15, 21, 43, 50, 53, 56, 64, 71, 74, 75, 76], we will explore following directions but no limited in future work:
(1) The qualitative evaluation of model similarity, such as similarity assessments for 3D CAD/ CAE model retrieval [10, 17], focused on the qualitative aspects of the models, e.g., topological result and geometric profile. On the other hand, in the field of data exchange [29, 37, 42, 51, 57, 58, 67, 69] and collaborative design [19, 20, 33, 44, 45, 49], the quantitative comparison of the similarity between source and target of feature-based CAD models is the latest development . So the proposed method can be adopted in this area to improve the computing efficiency of quantitative comparisons between large scale models in engineering applications of CAD/CAE/CAM in the future. For example, the proposed algorithms can enhance the computing efficiency of quantitative comparisons in Feature-based Data Exchange in CAD/CAE/CAM when calculating the fitness in optimization computation .
(2) This work is also related with design automation because the exact Hausdorff distance will be automatically computed. Design automation is considered as a particularly challenging issue in Computer-Aided Engineering systems, such as A MICROCAD system for interactive design of connections in steel buildings engineering [1, 2], object-oriented model-based presentation for integrated design of steel buildings structures [3, 4], and so on.
(3) The multi-core CPUs and many-core GPUs are nice choices for high-performance, low-power and cost-sensitive industrial applications. And they are also available on common PC platforms. Therefore, from view of practice, we should try improve our algorithm with multi-core/many-core acceleration platforms for industrial applications [14, 27, 77, 78].
This work is supported by the National Science Foundation of China (Grant No. 61472289) and Open Project Program of State Key Laboratory of Digital Manufacturing Equipment and Technology at HUST (Grant No. DMETKF2017016).
Adeli H, Fiedorek J. A MICROCAD system for design of steel connections-applications. Comput & Struct. 1986; 24(3): 361-374.
Adeli H, Fiedorek J. A MICROCAD system for design of steel connections-program structure and graphic algorithms. Comput & Struct. 1986; 24(2): 281-294.
Adeli H, Kao WM. Object-oriented blackboard models for integrated design of steel structures. Comput & Struct. 1996; 61(3): 545-561.
Adeli H, Yu G. An integrated computing environment for solution of complex engineering problems using the object-oriented programming paradigm and a blackboard architecture. Comput & Struct. 1995; 54(2): 255-265.
Alt H, Behrends B, Blömer J. Approximate matching of polygonal shapes. Ann Math Artif Intel. 1995; 13(3-4): 251-265.
Alt H, Braß P, Godau M, Knauer C, Wenk C. Computing the Hausdorff distance of geometric patterns and shapes. Discret Comput Geom. 2003; 65-76.
Alt H, Scharf L. Computing the Hausdorff distance between curved objects. Int J Comput Geom Ap. 2008; 18(4): 307-320.
Aspert N, Santa Cruz D, Ebrahimi T. MESH: Measuring errors between surfaces using the Hausdorff distance. ICME. 2002; 705-708.
Atallah MJ. A linear time algorithm for the Hausdorff distance between convex polygons. Inform Process Lett. 1983; 17(4): 207-209.
Bai J, Gao S, Tang W, Liu Y, Guo S. Design reuse oriented partial retrieval of CAD models. Comput Aided Design. 2010; 42(12): 1069-1084.
Bai YB, Yong JH, Liu CY, Liu XM, Meng, Y. Polyline approach for approximating Hausdorff distance between planar free-form curves. Comput Aided Design. 2011; 43(6): 687-698.
Bartoň M. Solving polynomial systems using no-root elimination blending schemes. Comput Aided Design. 2011; 43(12): 1870-1878.
Bartoň M, Hanniel I, Elber G, Kim MS. Precise Hausdorff distance computation between polygonal meshes. Comput Aided Geom D. 2010; 27(8): 580-591.
Belloch JA, Gonzalez A, Martinez-Zaldivar FJ, Vidal AM. Multichannel massive audio processing for a generalized crosstalk cancellation and equalization application using GPUs. Integr Comput-Aid E. 2013; 20(2): 169-182.
Bi ZM, Wang L. Advances in 3D data acquisition and processing for industrial applications. Robot Cim-Int Manuf. 2010; 26(5): 403-413.
Cardone A, Gupta SK, Deshmukh A, Karnik M. Machining feature-based similarity assessment algorithms for prismatic machined parts. Comput Aided Design. 2006; 38(9): 954-972.
Chen X, Gao S, Guo S, Bai J. A flexible assembly retrieval approach for model reuse. Comput Aided Design. 2012; 44(6): 554-574.
Chen XD, Ma W, Xu G, Paul JC. Computing the Hausdorff distance between two B-spline curves. Comput Aided Design. 2010; 42(12): 1197-1206.
Cheng Y, He F, Cai X, Zhang D. A group Undo/Redo method in 3D collaborative modeling systems with performance evalua-tion. J Netw Comput Appl. 2013; 36(6): 1512-1522.
Cheng Y, He F, Wu Y, Zhang D. Meta-operation Conflict Resolution for Human-Human Interaction in Collaborative Feature-Based CAD systems. Cluster Comput. 2016; 19(1): 237-253.
Cheng HC, Lo CH, Chu CH, Kim YS. Shape similarity measurement for 3D mechanical part using D2 shape distribution and negative feature decomposition. Comput Ind. 2011; 62(3): 269-280.
Cignoni P, Rocchini C, Scopigno R. Metro: measuring error on simplified surfaces. Comput Graph Forum. 1998; 17(2): 167-174.
Dubuisson MP, Jain AK. A modified Hausdorff distance for object matching. Pattern Recognition. 12th IAPR International Conference. 1994; 1: 566-568.
Fukunaga K, Narendra PM. A branch and bound algorithm for computing k-nearest neighbors. Ieee T Comput. 1975; 100(7): 750-753.
Guo B, Lam KM, Lin KH, Siu WC. Human face recognition based on spatially weighted Hausdorff distance. Pattern Recogn Lett. 2003; 24(1): 499-507.
Guthe M, Borodin P, Klein R. Fast and accurate Hausdorff distance calculation between meshes. International Conferences in Central Europe on Computer Graphics and Visualization. 2005; 41-48.
Guthier B, Kopf S, Wichtlhuber M, Effelsberg W. Parallel implementation of a real-time high dynamic range video system. Integr Comput-Aid E. 2014; 21(2): 189-202.
Hanniel I, Krishnamurthy A, McMains S. Computing the Hausdorff distance between NURBS surfaces using numerical iteration on the GPU. Graph Models. 2012; 74(4): 255-264.
Hoffmann C, Shapiro V, Srinivasan V. Geometric interoperability via queries. Comput Aided Design. 2014; 46: 148-159.
Huttenlocher DP, Kedem K, Kleinberg JM. On dynamic Voronoi diagrams and the minimum Hausdorff distance for point sets under Euclidean motion in the plane. The eighth annual symposium on Computational geometry. 1992; 110-119.
Huttenlocher DP, Klanderman GA, Rucklidge WJ. Comparing images using the Hausdorff distance. Ieee T Pattern Anal. 1993; 15(9): 850-863.
Hwang CM, Yang MS, Hung WL, Lee M. A similarity measure of intuitionistic fuzzy sets based on the Sugeno integral with its application to pattern recognition. Inform Sciences. 2012; 189: 93-109.
Jing S, He F, Han S, Cai X, Liu H. A method for topological entity correspondence in a replicated collaborative CAD system. Comput Ind. 2009; 60(7): 467-475.
Kim YJ, Oh YT, Yoon SH, Kim MS, Elber G. Coons BVH for freeform geometric models. Acm T Graphic. 2011; 30(6): 169.
Kim YJ, Oh YT, Yoon SH, Kim MS, Elber G. Efficient Hausdorff distance computation for freeform geometric models in close proximity. Comput Aided Design. 2013; 45(2): 270-276.
Kim YJ, Oh YT, Yoon SH, Kim MS, Elber G. Precise Hausdorff distance computation for planar freeform curves using biarcs and depth buffer. Visual Comput. 2010; 26(6-8): 1007-1016.
Kim J, Pratt MJ, Iyer RG, Sriram RD. Standardized data exchange of CAD models with design intent. Comput Aided Design. 2008; 40(7): 760-777.
Krishnamurthy A, McMains S, Halle K. Accelerating geometric queries using the GPU. SIAM/ACM Joint Conference on Geometric and Physical Modeling. 2009; 199-210.
Krishnamurthy A, McMains S, Hanniel I. GPU-accelerated Hausdorff distance computation between dynamic deformable NURBS surfaces. Comput Aided Design. 2011; 43(11): 1370-1379.
Lertchuwongsa N, Gouiffès M, Zavidovique B. Enhancing a disparity map by color segmentation. Integr Comput-Aid E. 2012; 19(4): 381-397.
Lertchuwongsa N, Gouiffès M, Zavidovique B. Mixed color/level lines and their stereo-matching with a modified Hausdorff distance. Integr Comput-Aid E. 2011; 18(2): 107-124.
Li J Kim BC, Han S. Parametric exchange of round shapes between a mechanical CAD system and a ship CAD system. Comput Aided Design. 2012; 44(2): 154-161.
Li K, He F, Chen X. Real time object tracking via compressive feature selection. Front Comput Sci. 2016; 10(4): 689-701.
Li WD, Lu WF, Fuh JYH, Wong YS. Collaborative computer-aided design research and development status. Computer-Aided Design. 2005; 37(9): 931-940.
Li X, He F, Cai X, Zhang D, Chen Y. A method for topological entity matching in the integration of heterogeneous CAD systems. Integr Comput-Aid E. 2013; 20(1): 15-30.
Lin KH, Lam KM, Siu WC. Spatially eigen-weighted Hausdorff distances for human face recognition. Pattern Recogn. 2003; 36(8): 1827-1834.
Llanas B. Efficient computation of the Hausdorff distance between polytopes by exterior random covering. Comput Optim Appl. 2005; 30(2): 161-194.
Lockett H, Guenov M. Similarity measures for mid-surface quality evaluation. Comput Aided Design. 2008; 40(3): 368-380.
Lv X, He F, Cai W, Cheng Y. A string-wise CRDT algorithm for smart and large-scale collaborative editing systems. Adv Eng Inform. DOI: 10.1016/j.aei.2016.10.005.
Mohan P, Haghighi P, Vemulapalli P, Kalish N, Shah JJ, Davidson JK. Toward automatic tolerancing of mechanical assemblies: Assembly analyses. J Comput Inf Sci Eng. 2014; 14(4): 041009.
Mun D, Han S, Kim J, Oh Y. A set of standard modeling commands for the history-based parametric approach. Comput Aided Design. 2003; 35(13): 1171-1179.
Ni B, He F, Pan Y, Yuan Z. Using shapes correlation for active contour segmentation of uterine fibroid ultrasound images in computer-aided therapy. Appl Math Ser B. 2016; 31(1): 37-52.
Ni B, He F, Yuan Z. Segmentation of uterine fibroid ultrasound images using a dynamic statistical shape model in HIFU therapy. Comput Med Imag Grap. 2015; 46: 302-314.
Nutanong S, Jacox EH, Samet H. An incremental Hausdorff distance calculation algorithm. Proceedings of the VLDB Endowment. 2011; 4(8): 506-517.
Papadias D, Tao Y, Mouratidis K, Hui CK. Aggregate nearest neighbor queries in spatial databases. Acm T Database Syst. 2005; 30(2): 529-576.
Primerano R, Wilkie D, Regli WC. A case study in system-level physics-based simulation of a biomimetic robot. Ieee T Autom Sci Eng. 2011; 8(3): 664-671.
Qi J, Shapiro V. Geometric interoperability with epsilon solidity. J Comput Inf Sci Eng. 2006; refvol6(3): 213-220.
Rappoport A. An architecture for universal CAD data exchange. Proceedings of the eighth ACM symposium on Solid modeling and applications. 2003; 266-269.
Rucklidge W. Efficient visual recognition using the Hausdorff distance. Lect Notes Comput Sc. 1996; 1173.
Rusu RB, Cousins S. 3d is here: Point cloud library (pcl). IEEE International Conference on Robotics and Automation. 2011; 1-4.
Sangineto E. Pose and expression independent facial landmark localization using dense-SURF and the Hausdorff distance. Ieee T Pattern Anal. 2013; 35(3): 624-638.
Sim DG, Kwon OK, Park RH. Object matching algorithms using robust Hausdorff distance measures. Ieee T Image Process. 1999; 8(3): 425-429.
Sudha N. Robust Hausdorff distance measure for face recognition. Pattern Recogn. 2007; 40(2): 431-442.
Sun J, He F, Chen Y, Chen X. A multiple template approach for robust tracking of fast motion target. Appl Math Ser B. 2016; 31(2): 177-197.
Taha AA, Hanbury A. An efficient algorithm for calculating the exact Hausdorff distance. Ieee T Pattern Anal. 2015; 37(11): 2153-2163.
Tang M, Lee M, Kim YJ. Interactive Hausdorff distance computation for general polygonal models. Acm T Graphic. 2009; 28(3): 1-9.
Tessier S, Wang Y. Ontology-based feature mapping and verification between CAD systems. Adv Eng Inform. 2013; 27(1): 76-92.
Wu Y, He F, Han S. Collaborative CAD synchronization based on a symmetric and consistent modeling procedure. Symmetry. 2017; 9(4): 59.
Wu Y, He F, Zhang D, Li X. Service-oriented feature-based data exchange for cloud-based design and manufacturing. Ieee T Serv Comput. DOI: 10.1109/TSC.2015.2501981.
Yu H, He F, Pan Y, Chen X. An efficient similarity-based level set model for medical image segmentation. J Adv Mech Des Syst Manuf. 2016; 10(8): JAMDSM0100.
Zeng Y, HorváTh I. Fundamentals of next generation CAD/E systems. Comput Aided Design. 2012; 44(10): 875-878.
Zhang DJ, He FZ, Han SH, Li XX. Quantitative optimization of interoperability during feature-based data exchange. Integr Comput-Aid E. 2016; 23(1): 31-51.
Zhang L, Kim YJ, Varadhan G, Manocha D. Generalized penetration depth computation. Comput Aided Design. 2007; 39(8): 625-638.
Yan X, He F, Chen Y, Yuan Z. An efficient improved particle swarm optimization based on prey behavior of fish schooling. J Adv Mech Des Syst Manuf. 2015; 9(4): JAMDSM0048.
Yan X, He F, Hou N. A novel hardware/software partitioning method based on position disturbed particle swarm optimization with invasive weed optimization. J Comput Sci Tech. 2017; 32(2): 340-355.
Yan X, He F, Hou N, Ai H. An efficient particle swarm optimization for large scale hardware/software co-design system. Int J Coop Inf Syst. DOI: S0218843017410015.
Zhou Y, He F, Qiu Y. Dynamic strategy based parallel ant colony optimization on GPUs for TSPs. Sci China Inform Sci. 2017; 60: 068102.
Zhou Y, He F, Qiu Y. Optimization of parallel iterated local search algorithms on graphics processing unit. J Supercomput. 2016; 72(6): 2394-2416.