Virtual Image Correlation uncertainty

In order to study the precision of the method, the above set of equation is simplified hereafter. At first we suppose that, close to the solution, $F(\mathbf{X})\simeq f(x_{2})$ (as it is the case for $g$, see Eqs. (1, 2)) thus:

Together with Eq. (13), this allows the separation of variables in Eq. (10):

The current term of the first integral is null if ${\partial\vec{X}^{c}}/{\partial\lambda_{p}}$ is everywhere collinear to $\vec{e}_{s}$, corresponding to a tangential motion which lets the curve unchanged: such case has to be avoided when choosing a curve equation. Thus, at convergence of the Newton scheme, when ${\partial\psi}/{\partial\lambda_{p}}=0$:

At last, if the virtual image borders lie one in the white background and one in the black silhouette: $f(-1)=0$ and $f(1)=1$, an integration by parts gives:

which shows that, at convergence, the mean value of $f$ is $1/2$.

Let $\bar{F}(X)=H(X-X_{0})$, where $H$ is the Heavyside distribution, be the physical luminance of a 1D silhouette (Fig. 3). Supposing ideal sensor (linear and homogenous) and optics, the $i^{\mathrm{th}}$ pixel returns the value $\int_{i-1/2}^{i+1/2}\bar{F}dX$ (blue dots). In 1D, the curve $\mathcal{C}$ is degenerated into a point ($x_{1}$ is meaningless) whose parameterized equation is simply chosen as $X^{c}=\lambda$ and the mapping (Eq. 3) reduces to $X=\lambda+Rx_{2}$. Due to the absence of curvature, expressions $\Psi$ (Eq. 6) and $\psi$ (Eq. 7) are equivalent thus Eq. (21) corresponds to:

if $f(-1)=F(\lambda-R)=0$ and $f(1)=F(\lambda+R)=1$, i.e. if the support of $G$ is wide enough: $\lambda-R<-1$ and $\lambda+R>1$. Because $-0.5<\lambda<0.5$, this leads to impose $R>1.5$. Solving this integral with the analytical expression $F(X)$ of the linear interpolation (thick blue segments in Fig. 3) gives straightforwardly $\lambda=X_{0}$. This shows that the VIC measurement $X^{c}$ corresponds exactly to the prescribed edge location $X_{0}$, whatever $X_{0}$ and $R>1.5$.

The VIC method requires the user-chosen curve $\mathcal{C}$ to be able to fit the contour of interest. Fig. 4 shows that, if the curve matches, f appears as invariant along $x_{1}$ (very similar to g) but shows waviness in the opposite case. However, a more objective indicator is necessary to quantify the quality of the identification. A straightforward idea consists in using $\partial\psi/\partial x_{1}$ as local correlation function but, g being not physical and $R$ being user chosen, this function only brings a qualitative information and does dot distinguish if the curve is inside or outside the contour.

From Eq. (21), we define the signed distance:

This one is defined in the frame $\vec{x}$ and corresponds to $\mu R$ in the pixel frame $\vec{X}$. Fig. 4 shows that $\mu(x_{1})$ represents a local identification of the boundary.

Fig. 5 is related to the well-know impossibility for a B-Spline to depict a circle [12]. When using a 10 points B-Spline, a peak of magnitude $\simeq 0.05$ pixel at wavelength $63$ pixels ($\simeq L/10$ pixel) is visible in the FFT of $R\mu$. It reveals a periodic oscillation of the curve from inside to outside of the exact circle in between the ten (regularly spaced) control points, which would be hard to see on a representation such has Fig. 4. Cases with noisy images lead to an additional noise spectrum whose mean amplitude is close to the estimation of Eq. (32) of $21\times 10^{-3}$ for the B-Spline and $8\times 10^{-3}$ for the circle.

Curve mismatching induces long wave oscillations of $R\mu$ which are revealed by a spectral analysis as long as they are not hidden by image noise. The acceptable precision, i.e. the magnitude of the maximum peak, remains the the user’s decision.

If the VIC has been shown in Sec. 3.2 to be theoretically exact in 1D, things are more complicated in 2D. The pixel grid is used as computational frame in most of image analysis methods, including DIC and some versions of VIC using $\Psi$ [14]. However, many tests showed that computing on a regular discretization of $(x_{1},x_{2})$ (see Fig. 4) provides better precision, as soon as the distance between two corresponding points $(X_{1},X_{2})$ is less than $1/3$ pixel [16].

The values of F, required for Eq. (7) at these non integer values are obtained by interpolation. Another series of tests showed that the simplest and fastest linear interpolation gives equivalent or even better precision than cubic or B-spline interpolation. This is different from DIC, but in accordance with the analytical analysis in Sec. 3.2.

In Sec. 3.2 we showed that $R$ should be greater than 1.5 pixel. In order to set the optimal value of $R$ for 2D images, we proceed to tests on synthetic images of linear edges identified with a line segment (Fig. 6). To address any cases, the angle $\theta$ from $X_{1}$ to the edge is varied from 0 to $\pi/4$, the ordinate of its midpoint is varied of $\Delta X_{02}\in[0,1[$ pixel and the length $L=100$ of the segment is varied of $\Delta L\in[0,1[$ pixel. Ten levels are used for each variation. The mean $m_{d}$ and the standard deviation $\sigma_{d}$ of the distance $\delta(x_{1})$ between identified and exact segments are computed. In average, setting $R=1.5$ gives $m_{d}=-4.09\times 10^{-5}$ and $\sigma_{d}=3.76\times 10^{-4}$ and setting $R=2$ gives $m_{d}=-5.99\times 10^{-5}$, $\sigma_{d}=7.92\times 10^{-4}$.

However Fig. 7 shows that choosing $R=2$ eliminates pathologic cases of small angles (such as shown by Fig. 6). Setting other (especially larger) values for $R$ did not provide any advantage. As a consequence, $R=2$ appears to be the optimal value for the VIC.

In order to get an estimator of the uncertainty associated to the sole effect of discretization, similar line segment tests have been realized, varying the length $L$ over two decades.

Fig. 8 shows that the mean distance $m_{d}$ is weak for all $L$ and that the standard deviation $\sigma_{d}$ is very close to its linear regression $\sigma_{d}= {0.0885}/{L}$ (blue line on Fig. 8). The proposed empirical rule:

corresponds to the red line. The role of the number of curve parameters $N$ in this equation, of two in these tests (ordinate and angle), is supposed to be equivalent to the one it has in Eq. (32).

At ideal, the silhouette is black and the background is white. However, real images may have contrast and luminance deviations. From Sec. 3.2, the average of $F(X)$ over all possible $X_{0}\in[-0.5,0.5]$ is linear: $<F>=({X+1})/{2}$. Thus, for this analytical study, we suppose $f$ to be the continuous linear piecewise function (see Fig. 9):

where $a$ is the amplitude (contrast), $b$ the bias (luminance), $\delta/R$ the location of the researched edge. The origin of the virtual image at $x_{2}=0$ defines the VIC measurement thus $\delta/R$ (in the frame $\vec{x}$) or $\delta$ (in the pixel frame $\vec{X}$) is the measurement error.

Used together with Eq. (20), which is fulfilled at convergence, above expressions give:

As a consequence, the contrast $a$ has no influence on the precision but a luminance variation $b$ induces a bias $\delta$ in the measurement. In a practical point of view, this is easily annulated during computation by a linear correction of the gray levels of F. Similar calculus shows that non linear image corrections should be avoided because they induce a bias. In particular, best results will be obtained with CCD sensors with good linearity.

Inevitable image noise leads to uncertainty in the VIC measurement. We suppose now that each pixel of integer coordinates $(i,j)$ is the sum of an exact value $F_{ij}$ and a gaussian noise $N_{ij}$, spatially uncorrelated, of zero mean and of standard deviation $\sigma(N_{ij})=\sigma_{0}$. With the hypothesis of Sec. 3.1, we show in Annex B that:

From the Newton scheme (Eq. 8), this term is associated to the standard deviation of each shape parameter by:

The average $\sigma_{n}$ of the standard deviation of the distance $\vec{X}^{c}\cdot\vec{e}_{r}$ from the measurement to the noiseless solution is:

From $d\vec{X}^{c}=({\partial\vec{X}^{c}}/{\partial\lambda_{q}})\,d\lambda_{q}$ we deduce:

Gathering previous expressions gives $\sigma_{n}^{2}$. However this complex expression has to be computed in each cases. A simpler approximation is obtained by supposing at first a perfectly contrasted image with $a=1$ and $b=0$. Eq. (25) and Eq. (12) give:

At second we retain only the diagonal terms of this matrix, which corresponds to consider that each shape variable acts on a separate part of the curve. This gives a simple approximation of the VIC standard deviation due to the image noise:

The proportionality between $\sigma_{n}$ and the image noise $\sigma_{0}$ is common with DIC uncertainty analysis [15, 20, 19, 4]. Doubling the image resolution doubles $L$ thus divides $\sigma_{n}$ by $\sqrt{2}$. The uncertainty $\sigma_{n}$ is proportional to $\sqrt{N}$: this weak dependance allows the user to retain complex curve families. This formula erroneously suggest the use of large $R$ but the calculus is valid for the active part of the virtual image thus one may consider $R\leq 2$. The quantification noise, of classical expression $\sigma_{0q}=(2^{nb}\sqrt{12})^{-1}$ where $nb$ is the bit depth, can also be taken into account as an additional image noise.

Fig. 10 shows the uncertainty of the method, according to expressions of $\sigma_{d}$ (Eq. 24) and $\sigma_{n}$ (Eq. 32). It shows in particular that the irreducible uncertainty $\sigma_{d}$, associated to discretization, can only be attained with low image noise $\sigma_{0}$ and large curve support $L/N$. Of course this graph is valid only in absence of curve fitting error.

In table 1 we compare predicted and measured uncertainties on various tests. Cases C₁ to C₄ correspond to numerical tests onto a $401\times 401$ pixels image of a spiral [16]. Cases D₁ to D₃ refer to synthetic images of discs of average radii respectively of 3 (Fig. 4), 10, 100 pixels whose center and radius are randomly varied over 1 pixel, over 100 trials. Cases D${}_{1}^{\prime}$ to D${}_{3}^{\prime}$ are similar, but with an additive gaussian image noise $\sigma_{0}$. All images are in 8 bits. The standard deviation associated to discretization $\sigma_{d}$ is obtain by Eq. (24) and the one associated to image noise $\sigma_{n}$ by Eq. (32). The quantification noise $\sigma_{0q}$ is took into account in $\sigma_{n}$.

One observes that the predicted values of $\mathrm{max}(\sigma_{d},\sigma_{n})$ are in good agreement with measured ones $\sigma$. The sole exception is the case C₁ for which a curve fitting error is present, the 10 control points of the B-Spline being not enough to describe the spiral at this level of precision.

The VIC method has been already successfully compared to Fast Marching Algorithm [17] and Steger’s method [18] in earlier publication [16]. Since this article, new methods also claimed for sub-pixel precision. Among them we retained the work of Trujilo-Pino (TP) [22, 21] which, based on an area estimate, is in some way close to the estimator $\mu$ (Eq. 29). For reference, we retained the well known Active Contours (AC) method [11].

Table 2 shows the results obtained for the circular disc statistical study. With respect to TP method, the VIC (table 1) offers a gain in $\sigma$ which increases with $L/N$. In the realistic case D₃, with $L/N\simeq 200$ pixels per curve parameter, the VIC is approximatively 6 times more precise than the TP method. The AC method gives worse results but still identifies a continuous contour in noisy images, on the contrary of TP method which required to remove aberrants points (farther than 0.5 pixel). Both TP and AC methods, like the majority of the existing contour detection methods, are local ones. On the contrary, the VIC benefits of the regularization associated to the curve $\mathcal{C}$, whose effect on the precision, from Eqs. (24, 32), increases with the curve length.