# Research on O-ring Dimension Measurement Algorithm Based on Cubic Spline Interpolation
## 3 O-Ring Dimension Measurement Algorithm Design
### Sub-Pixel Level Edge Measurement Algorithm Based on Cubic Spline Interpolation
 \tag{12}\]  
where \(x_{j-1}\leq x\leq x_{j}h_{j}=x_{j}-x_{j-1,j}=1,2,\cdots,N+1\). Then, finding the derivative of \(S(x)\) to obtain,  
\[S^{\prime}(x)=-\frac{M_{j-1}}{2h_{j}}(x_{j}-x)^{2}+\frac{M_{j}}{2h_{j}}(x-x_{j -1})^{2}+\frac{y_{j}-y_{j-1}}{h_{j}}-\frac{M_{j}-M_{j-1}}{6}h_{j} \tag{13}\]  
With Equation (12) we can see that the key to finding \(S(x)\) is to determine \(M_{j}=S^{\prime\prime}(x)_{j}=1,2,\cdots,N+1\). Since node \(x_{j}(j=1,2,\cdots,N)\) is continuously differentiable at \(S^{\prime}(x)\), then,  
\[S^{\prime}(x_{j}-0)=S^{\prime}(x_{j}+0),j=1,2,\cdots,N \tag{14}\]  
From Equation (14) we get:  
\[\frac{h_{j}}{6}M_{j-1}+\frac{h_{j}+h_{j+1}}{3}M_{j}+\frac{h_{j+1}}{6}M_{j+1}= \frac{y_{j+1}-y_{j}}{h_{j+1}}-\frac{y_{j}-y_{j-1}}{h_{j}},j=1,2,\cdots,N \tag{15}\]  
Then, the above equation can be reduced to:  
\[\mu_{j}M_{j-1}+2M_{j}+\lambda_{j}M_{j+1}=d_{j},j=1,2,\cdots,N \tag{16}\]  
where \(\mu_{j}=\frac{h_{j}}{h_{j}+h_{j+1}}\lambda_{j}=1-\mu_{j}d_{j}=\frac{6}{h_{j}+ h_{j+1}}(\frac{y_{j+1}-y_{j}}{h_{j+1}}-\frac{y_{j}-y_{j-1}}{h_{j}})\). Equation (16) is a linear system of equations with respect to \(M_{0},M_{1},\cdots,M_{N+1}\). To determine these \(N+2\) unknowns, two additional boundary conditions are required. Since we do not know the values of the first and second order derivatives of \(S(x)\) on boundaries \(x_{0}\) and \(x_{N+1}\), here we choose to use the natural boundary conditions, i.e., \(S^{\prime\prime}(x_{0})=S^{\prime\prime}(x_{N+1})=0\), \(M_{0}=M_{N+1}=0\). Then \(M_{j}\) is written in the form of a matrix:  
\[\left[\begin{array}{Using the above theoretical calculation, the sub-pixel edge point coordinate \(x_{j\max}\) in the direction of the gray gradient is obtained. The coordinates of the point consist of the integer part \(x_{j\max}^{pixel}\) and the fractional part \(x_{j\max}^{subpixel}\), using the following Equation (18) [21].  
\[x_{j\max}=x_{j\max}^{pixel}+x_{j\max}^{subpixel} \tag{18}\]  
where the integer part \(x_{j\max}^{pixel}\) of \(x_{j\max}\) is the pixel-level coordinate of the edge point, and the fractional part \(x_{j\max}^{subpixel}\) of \(x_{j\max}\) is the sub-pixel-level coordinate of the edge point. The coordinates of the corresponding pixel levels \((x,y)\) in the greyscale map can be determined from the integer part of \(x_{j\max}\). According to the direction of the gradient, the calculation formulas of sub-pixel coordinates \((x^{subpixel},y^{subpixel})\) are as follows [22]:  
If the direction of the grey gradient is the 'a' direction the expression is Equation (19):  
\[\left\{ \begin{array}{c}x^{subpixel}=x\\ y^{subpixel}=y+x_{j\max}^{subpixel}\end{array} \right. \tag{19}\]  
If the direction of the grey gradient is the 'b, c' direction the expression is Equation (20):  
\[\left\{ \begin{array}{c}x^{subpixel}=x+x_{j\max}^{subpixel}\cos 45^{\circ} \\ y^{subpixel}=y+x_{j\max}^{subpixel}\sin 45^{\circ}\end{array} \right. \tag{20}\]  
If the direction of the grey gradient is the 'd' direction the expression is Equation (21):  
\[\left\{ \begin{array}{c}x^{subpixel}=x+x_{j\max}^{subpixel}\\ y^{subpixel}=y\end{array} \right. \tag{21}\]  
A flow chart of the whole algorithm is shown in Figure 5.  
As the theoretical part is rather complex, an example of the calculation of the sub-pixel coordinates of an O-ring contour point is presented. Taking the coordinates of a point (136,528) of the O-ring contour point as an example, the grey scale values of the pixels in a \(7\times 7\) rectangular area centered on this point is shown in Figure 6.  
According to the gradient direction formula (Equation (8)), we can calculate that \(E_{a}=25\),\(E_{b}=181\), \(E_{c}=185\), \(E_{d}=186\). Therefore, the gradient direction is direction \(d\). The third spline interpolation is carried out for each point in direction \(d\). The image of the third spline function \(S(x)\), the first order derivative \(S^{\prime}(x)\), and the second order derivative \(S^{\prime\prime}(x)\) are shown in Figure 7. The calculation gives \(x_{j\max}=1.8159\).