Computation of the Minimum One-sided Hausdorff Distance between Plane Curves under a Similarity Transformation and Relevant Applications in Roundness Error Evaluation

I. INTRODUCTION

Early Hausdorff distance computation is mainly applied to pattern recognition and image processing, including the recognition of faces, fingerprints, characters, handwriting, and licence plates. However, there has been little investigation into the computation of the Hausdorff distance relative to non-point sets. In the conventional method, continuous geometric objects are discretised into point sets, based on which the approximate Hausdorff distance between continuous geometric objects can be indirectly obtained by computing the Hausdorff distance between point sets. More recently the computation of the Hausdorff distance between continuous geometric objects has been studied owing to potential demands in geometric modelling, computational geometry, computer graphics, and other fields. In 2008, Alt et al. ${}^{[1]}$ from Germany demonstrated four cases of the one-sided Hausdorff distance between two C ${}^1$ continuous plane curves. Specifically, the Hausdorff distance may present at two endpoints of two curves, with one of the two-points being the end-point of one curve, double perpendicular foot points, or the intersection point of the midline of one curve and another curve. Furthermore, they provided nonlinear constraint simultaneous equations corresponding to the four cases. The Hausdorff distance between plane curves was computed with the aid of a standard algebraic equations solver. In the same year, Elber et al. ${}^{[2]}$ from Israel generalised these four cases of the one-sided Hausdorff distance between two $C^1$ continuous plane curves to space curves/ curved surfaces. They obtained the corresponding Hausdorff distance using a self-designed algebraic equations solver. In 2010, Chen et al. ${}^{[3]}$ tackled the lack of research in finding the root of nonlinear simultaneous equations in previous studies [1-2].

They explored the geometric clipping method for calculating the Hausdorff distance between two B-spline curves. As per their algorithm, sufficient conditions allowing the Hausdorff distance to appear at the end of a curve were provided. The curve segmentation technique and rolling circle clipping method were adopted to transform the Hausdorff distance computation between two curves into that of the minimum or maximum distance between points and curves, thus improving the stability and computational efficiency of the algorithm. In the same year, Kim et al. ${}^{[4]}$ proposed a real-time algorithm to accurately calculate the Hausdorff distance between two plane free-form curves. Firstly, G ${}^1$ continuous double circular arcs were employed to approximate the free-form curves under given tolerances. The arcs were subsequently subjected to distance mapping and saved to a graphics hardware depth buffer. Finally, most of the redundant arc segments were trimmed to improve the computational efficiency related to the Hausdorff distance. In 2011, Bai et al. ${}^{[5]}$ proposed a polyline method to obtain the Hausdorff distance between plane curves. Based on the algorithm, continuous free-form curves were approximated with polylines under a given measurement. An incremental algorithm was subsequently utilised to compute the one-sided Hausdorff distance between line segments and polylines. Since two clipping strategies are used in this method, the ineffective line segments in the final Hausdorff distance computation are clipped which significantly improves the computational efficiency.

In terms of the computation of the minimum Hausdorff distance between geometric objects under a certain transformation, Huttenlocher ${}^{[6]}$ proposed an algorithm to compute the minimum Hausdorff distance for one- and two-dimensional point sets. The one-dimensional algorithm of the minimum Hausdorff distance between point sets was applied to the comparison computation of planar polygons under an affine transformation by using the affine arc length to represent planar polygons. The two-dimensional algorithm was used to compare digital images. Additionally, the Hausdorff distance definition was extended to enable it to be used for the comparison between partial sets. In further studies, Huttenlocher ${}^{[7]}$ improved the minimum Hausdorff distance algorithm under a translation transformation between point sets and line segment sets by using a Voronoi diagram. According to two given polygons, Alt ${}^{[8]}$ proposed that the Hausdorff distance between two polygons can be minimised by the rigid transformation of one of the polygons, and therefore the approximate matching between polygons can be realised. Chew et al. ${}^{[9]}$ investigated the computational complexity of the minimum Hausdorff distance algorithm between geometric objects under a rigid transformation for planar line segments that are composed of point sets and polygon sets that are composed of point sets. Hur et al. ${}^{[10]}$ adopted the conic section represented by a quadratic rational Bezier curve to perform the best uniform approximation (BUA) for the convolution curve of two plane curves. The objective was to minimise the Hausdorff distance between the conic section and the convolution curve. Because the weight factor of the rational Bezier curve was the only optimisation variable in the approximation curve in the model, the study revealed that there were two characteristic points on the approximation curve, and both the distance between them and the convolution curve were the Hausdorff distance, and the derivative signs of the two distances with respect to the weight factor were opposite. This constituted the necessary and sufficient conditions for minimising the Hausdorff distance between two curves. An iterative algorithm was also formulated for computing the BUA based on the necessary and sufficient conditions.

To ensure equal precision and computational efficiency, Gu et al. ${}^{[11]}$ proposed a rough and accurate staged matching method between plane curves under an affine transformation. Liang et al. ${}^{[12]}$ designed a matching method between plane curves using their projection along any direction based on a weak perspective projection model. Gruen et al. ${}^{[13]}$ established a similarity transformation model consisting of seven parameters between curved surfaces as per the least squares principle. In addition, they considered the matching method between curved surfaces and applied it to the automatic mosaic of 3D point cloud data. Rodriguez et al. ${}^{[14]}$ analysed the similarity computation between 3D curves through the string edit distance method. Yamany et al. ${}^{[15]}$ formulated a surface registration method based on a genetic algorithm. Cao et al. ${}^{[16]}$ transformed the Hausdorff distance computation between plane curves into that of the minimum distance from points to curves. This method eliminated the drawback of traditional methods, whereby different nonlinear simultaneous equations had to be solved separately under four Hausdorff distance cases between plane curves. Moreover, they constructed an algorithm to compute the one-sided Hausdorff distance between C2 continuous curves via two steps, namely rough and accurate computations. Based on a previous study ${}^{[16]}$, Cao et al. ${}^{[17]}$ established a programming model for the minimum one-sided Hausdorff distance between plane curves under a rigid transformation and developed relevant solutions. Furthermore, they applied the model to line profile error evaluation.

As suggested in relevant studies, the computation of the Hausdorff distance between continuous curves and curved surfaces has attracted the attention of researchers in geometric modelling, computational geometry, computer graphics, and other fields in recent years. However, it also prevents the wider application of the Hausdorff distance in engineering. There are several issues in relevant research work. 1) A few studies have been conducted on the computation of the Hausdorff distance between free-form curves and curved surfaces. In most cases, the Hausdorff distance was obtained by solving simultaneous algebraic equations. Since the solution of these algebraic equations was either regarded as a black box or obtained by a standard solver, the solutions with a reference value and geometric significance cannot be fully provided. 2) Due to the complexity of concrete curves and curved surfaces in engineering, research on the computation of the Hausdorff distance between continuous curves or curved surfaces and the minimum Hausdorff distance under a certain transformation is still in its infancy. At the same time the lack of relevant solution methods significantly hinders its extensive application in the engineering field.

In this study, a mathematical programming model for computing the minimum one-sided Hausdorff distance between plane curves under a similarity transformation was constructed based on a previous study ${}^{[17]}$ by supplementing the scale transformation parameters of approximation objects. A solution strategy composed of two-stage (rough and accurate) computation was proposed for this model. Moreover, a local iterative accurate algorithm for computing the minimum one-sided Hausdorff distance for continuous curves was also constructed. On that basis, a roundness error evaluation programming model, based on the minimum one-sided Hausdorff distance, was established and then verified numerically.

II. COMPUTATION OF THE MINIMUM ONE-SIDED HAUSDORFF DISTANCE BETWEEN PLANE CURVES UNDER A SIMILARITY TRANSFORMATION

2.1 Mathematical Programming Model

It can be inferred from the definition of the one-sided Hausdorff distance that the computation of $h(A,B)$ involves the shortest distance from a point a on Curve A to Curve B. As per geometric error evaluation theory and curve/curved surface approximation theory, this shortest distance is generally called an error. When Curve B is allowed to undergo a similarity transformation, its position and scale are transformed. The change in the parameter of the point on Curve B corresponding to the shortest distance from a point on Curve A to Curve B is termed parameter transformation. When the shortest distance from Point $a$ to the transformed Curve B is also transformed, it is termed error transformation. Therefore, the computation of $h(A,B)$ under a similarity transformation incorporates position, scale, parameter, and error transformations.

The representation of Curve B under a similarity transformation is subsequently discussed. The similarity transformation of the given plane curve B includes three motions; namely translation, rotation, and scaling. The following homogeneous coordinates can be used to represent the translation matrix, rotation matrix, and scaling matrix, respectively, including

where, $t_x,t_y$ represents the translation coordinates along the X and Y axes; $\theta$ represents the rotation angle; $s_x,s_y$ represents the scaling rations in the X and Y directions; To maintain the shape of the graph unchanged before and after scaling, equal scaling would be adopted in the following discussion, namely $s_x=s_y=s$. These parameters $t_x,t_y,\theta ,s$ are collectively called the similarity transformation parameter X.

After the above three motions, the expression of Curve B can be obtained as:

where, X, Y denotes the coordinates of Curve B in Frame $\{o,ij\}$; they are all functions of the curve parameter b.

From the perspective of the BUA of curves or curved surfaces, the one-sided Hausdorff distance between two geometric objects is the maximum deviation of the approximation object from the approximation target. Minimising the maximum deviation under some transformation is the optimisation objective of the BUA. The process of minimising the maximum deviation is characterised by saddle points and can therefore be explored by saddle point programming. Under a similarity transformation, if the scale and position parameters of the approximation object are taken as optimisation variables and the one-sided Hausdorff distance from the approximation object to the approximation target is minimised as the optimisation objective, the definition of the minimum one-sided Hausdorff distance can be expressed as the following mathematical programming form:

The first line in Equation (3) represents the objective function of the optimisation model and h is the characteristic parameter. The second line represents the optimisation model constraint function; namely that the characteristic parameter h shall be the one-sided Hausdorff distance between two curves under a certain set of transformation parameters $\mathbf{x}\cdot d(\mathbf{A}(a),\mathbf{B}(b,\mathbf{x}))=\Vert \mathbf{A}(a)-\mathbf{B}(b,\mathbf{x})\Vert$ represents the Euclidean distance between Point a on Curve A and Point b on Curve B under the transformation parameter X.

The constraint function in the above model is the one-sided Hausdorff distance between two curves under the transformation parameter $\mathbf{X}$. According to the definition of the one-sided Hausdorff distance between continuous curves in a previous study[16], it can be found that a pair of points satisfying the one-sided Hausdorff distance is the point pair satisfying the maximisation of the minimum distance and it also has the saddle point characteristics. Moreover, a saddle point programming model for the Hausdorff distance computation between two curves can be established if the curve parameters $a$ and $b$ of two curves are taken as optimisation variables and the minimum distance from a point on one curve to the other is taken as the optimisation objective. In other words, the computation of the minimum one-sided Hausdorff distance is an optimisation in Type min max min $f$. To simplify the optimisation process, Curve A would be discretised to complete the computation of the shortest distance from each discrete point on Curve A to Curve B. On that basis, the following mathematical programming model can be constructed to obtain the solution to the minimum one-sided Hausdorff distance:

Following the discretisation of Curve A, the programming model given by Equation (3) can be expressed as:

where, $d_i(\mathbf{A}(a_i),\mathbf{B}(b_i,\mathbf{x}))$ represents the shortest distance from the discrete point $a_i$ on Curve A to the transformed curve $B(b,\mathbf{x})$, as presented in Figure 1. This can be computed according to the shortest distance algorithm from the point to the curve in a previous study ${}^{[16]}$; $b_i=b_i(a_i)$ represents the curve parameter corresponding to the minimum normal distance mapping point of the discrete point $a_i$ on Curve $B(b,\mathbf{x})$; i represents the discrete point serial numbers, and m represents the total number of discrete points on Curve A. $\mathbf{x}=(t_x,t_y,\theta ,s)$ represents a similarity transformation parameter, and $\mathbf{y}=(h,\mathbf{x})=(h,t_x,t_y,\theta ,s)$ represents the optimisation variables of the saddle point programming model.

It can be revealed from Equations (2) and (3) that the optimisation model constraint function given in Equation (4) is not a linear combination of optimisation variables, but a nonlinear optimisation which needs to be linearised.

2.2 Linearisation Solution to the Mathematical Programming Model

It can be seen from the above optimisation model that the nonlinear part of the optimisation variable is included in the shortest distance $d_i$. If the shortest distance in Equation (4) is regarded as a function of the transformation parameter X, it can be expressed as follows:

If the transformation parameter $t_x,t_y,\theta ,s$ is regarded as a first-order small quantity, it is called a small error. After $g(\mathbf{x})$ in Equation (5) is subject to Taylor's expansion at the zero point ${\mathbf{x}}_0=(t_{x0},t_{y0},{\theta }_0,s_0{)}^{\mathrm{T}}$ of transformation parameters and their second-order and higher-order small quantities are omitted, the following expression can be obtained:

In the equation,

where, $g({\mathbf{x}}_0)$ represents the shortest distance from a point $a_i$ on Curve A to Curve B before a similarity transformation; $\mathrm{\Delta }{t}_x,\mathrm{\Delta }{t}_y,\mathrm{\Delta }\theta$, and $\mathrm{\Delta }s$ represent the first-order increment of the transformation parameter $t_x,t_y,\theta ,s$; $X_i,Y_i$ represents the coordinates of the point on Curve B; $N_{Xi},N_{Yi}$ represents the coordinates of the unit normal vector at a point on Curve B; $B_x^{\prime },B_y^{\prime },B_{\theta }^{\prime },B_s^{\prime }$ represents the first-order partial derivatives of Equation (2) for the transformation parameter $t_x,t_y,\theta ,s$.

After Equations (6) - (11) are substituted into Equation (4), the following linear programming model for computing the minimum one-sided Hausdorff distance between plane curves can be obtained:

where, h represents the characteristic parameter, that is, the one-sided Hausdorff distance from curve A to curve B; ${\delta }_i=g({\mathbf{x}}_0)$; and m represents the number of discrete points on the actual curve.

The above optimisation model has the variable $h\ge 0$. However, $\mathrm{\Delta }\theta ,\mathrm{\Delta }{t}_x,\mathrm{\Delta }{t}_y,\mathrm{\Delta }s$ are all free variables without non-negative requirements. To achieve the solutions by the simplex linear programming method, it can be arranged that ${\mathbf{X}}_0=(\mathrm{\Delta }\theta ,\mathrm{\Delta }{t}_x,\mathrm{\Delta }{t}_y,\mathrm{\Delta }s{)}^{\mathrm{T}}={\mathbf{X}}_1-{\mathbf{X}}_2$ and . Then, the slack variable ( $X_3\ge 0$ ) is introduced and the inequality constraint is transformed into an equality constraint, finally an initial basic feasible solution can be obtained. Hence, the above linear programming problem can be expressed in the following standard form:

where, $\mathbf{C}=(1,0,\dots ,0{)}^{\mathrm{T}}$, $\mathbf{X}=(h,{\mathbf{X}}_1^{\mathrm{T}},{\mathbf{X}}_2^{\mathrm{T}},{\mathbf{X}}_3^{\mathrm{T}}{)}^{\mathrm{T}}$ represents a dimensional column vector of $(m+9)$, $\mathbf{A}=({\mathbf{I}}_0,{\mathbf{A}}_0,-{\mathbf{A}}_0,-\mathbf{I})$ represents a matrix of $m\times (m+9)$, and I represents an m-order unit matrix; $\mathbf{b}=({\delta }_1,\dots ,{\delta }_m{)}^{\mathrm{T}}$, ${\mathbf{I}}_0=(1,\dots ,1{)}^{\mathrm{T}}$, and $X_3$ represent m-dimensional column vectors, and $X_0,X_1,X_2$ represents a 4-dimensional column vector; The upper corner mark T represents the matrix transposition.

After the above model is solved by the simplex linear programming method, the characteristic parameter h and the similarity transformation parameter $\mathrm{\Delta }\theta ,\mathrm{\Delta }{t}_x,\mathrm{\Delta }{t}_y,\mathrm{\Delta }s$ of Curve B can be obtained. The value of the characteristic parameter can be considered as the minimum one-sided Hausdorff distance from curve A to curve B.

To reduce any error caused by the linear geometric model, curve B can be rotated, translated, and scaled, using the computation result of $\mathrm{\Delta }\theta ,\mathrm{\Delta }{t}_x,\mathrm{\Delta }{t}_y,\mathrm{\Delta }s$. The transformed curve can be regarded as a new curve and the above process can be repeated until the absolute value of the transformation parameters obtained from the computation of Equation (12) is less than the given precision.

Under the similarity transformation, one of the two curves (e.g., Curve B) can usually be translated, rotated, and scaled, so there are four degrees of freedom in Curve B. Therefore, when $h(A,B)$ reaches its minimum, the equidistant line of Curve B has at least 5 points of tangency to Curve A, as shown in Figure 2. Under this condition, due to the continuous changes in the Curve B scale parameter s, when $h(A,B)$ reaches the minimum, both the symmetric equidistant curves $B_o$ and $B_i$ of Curve B have points of tangency to Curve A. In other words, Curve A is bidirectionally enclosed by the inner and outer equidistant lines of Curve B and the maximum and minimum normal errors of Curve A relative to Curve B are equal in value and opposite in sign. The distribution ratio of the tangency points for the inner and outer equidistant curves $B_o$ and $B_i$ to Curve A can be 1:4 (4:1) or 2:3 (3:2).

2.3 Precise Iterative Model

The mathematical programming model in the previous section can be utilised to compute the minimum one-sided Hausdorff distance from discretised curve A to curve B. When the curve is originally provided in the form of discrete points, for example, when the curve is a data point obtained by measurement or the computational precision is not high, this method can meet the relevant requirements. However, when Curves A and B are presented as continuous curves, in order to obtain the precise minimum one-sided Hausdorff distance between both curves, it is necessary to conduct local iterative optimisations based on the previous section. Finally, the precise minimum one-sided Hausdorff distance from curve A to curve B can be obtained.

The approximate solution which satisfies the optimal condition can be obtained via the algorithm in the previous section. There are 5 characteristic points on discretised Curve A which are optimally arranged with the inner and outer equidistant lines of Curve B. It is necessary to construct a local iterative optimisation model, so that the parameters of Curves A and B, corresponding to 5 equivalent characteristic points, can meet the requirements of the one-sided Hausdorff distance.

As the local optimisation model contains 4 similarity transformation parameters and 10 curve parameters corresponding to 5 characteristic points, with a total of 14 optimisation variables, it can be considered a complex nonlinear problem. If these parameters can be solved together iteratively, the solution process is prone to oscillation, which may induce convergence failure in the computation. To reduce the computational difficulty and ensure computational stability, the precise iterative model is iteratively solved using two steps (similarity transformation parameters and curve parameters).

2.3.1 Similarity Transformation Parameter Iterative Solution

There are 5 initial points ${\mathbf{P}}_i(i=1,\dots ,5)$ on Curve A and the mapping points ${\mathbf{Q}}_i(i=1,\dots ,5)$ with the shortest distance of ${\mathbf{P}}_i$ on Curve B can be obtained by the algorithm of the shortest distance from points to curves. After the position of Point ${\mathbf{P}}_i$ is fixed, the distance between corresponding $\Vert {\mathbf{P}}_i{\mathbf{Q}}_i\Vert$ can be equalised by changing the position, direction, and scale of Curve B. Therefore, the conditional expression can be provided:

where, the position of Point $Q_i$ is related to the similarity transformation parameter of Curve B and its curve parameter b. Since Point $Q_i$ is the normal mapping point with the shortest distance of $P_i$ on Curve B, its curve parameter is not independent, so $b=b(a)$. Hence, Equation (14) can be expressed as:

After Equation (15) is subject to Taylor's expansion near the initial point and the small quantity above the second order is omitted, the following expression can be obtained: