Chapter 20 Accuracy

20.1 Introduction
accurately characterizing performance: important aspect of vision system




20.2 Mensuration Quantizing Error
position on digital grid: has inherent quantizing error due to discreteness
$\hat{f}$: coordinate of line's right endpoint
$\Delta c$: spacing between pixel centers
$\hat{\sigma}_2$: uniform random variable, $0 \leq q \leq 1$
$B=\Delta c(B^*-1/2+q)$
$B^*=Ceiling(B/\Delta c -1/2)$
relationship between the line segment end and the digital grid
=====Fig. 20.1=====




$\beta^*$: digital coordinate of the line's rightmost pixel
natural quantizing model:

\begin{displaymath}
\beta^* = \left \{
\begin{array}{ll}
B^* & {\rm with \ proba...
...
B^*-1 & {\rm with \ probability \ } 1-q
\end{array}\right .
\end{displaymath}

letting $x$ be a random variable where

\begin{displaymath}
x = \left \{
\begin{array}{ll}
1 & {\rm with \ probability \ } q \\
0 & {\rm with \ probability \ } 1-q
\end{array}\right .
\end{displaymath}

restate the quantizing model:

\begin{displaymath}
\beta^* = B^* -1+x
\end{displaymath}

note: $E(x)=q$ and $E(x^2)=q$
the mean of digital coordinate $\beta^*$:

\begin{displaymath}
E(\beta^*)=E(B^*-1+x)=E\left (\frac{B}{\Delta c}+\frac{1}{2}-q-1+x\right )
=\frac{B}{\Delta c}-\frac{1}{2}
\end{displaymath}

thus unbiased estimator $\hat{B}$ for position $\hat{f}$ is $\hat{B}=\Delta c(\beta^*+\frac{1}{2})$
the variance of digital coordinate $\beta^*$:

\begin{displaymath}
V(\beta^*)=E\left \{ \left [
\beta^*-\left ( \frac{B}{\Delt...
...eft (B^*-1+x-\frac{B}{\Delta c}+\frac{1}{2}\right )^2 \right ]
\end{displaymath}


\begin{displaymath}
=E[(x-q)^2]=E(q-2q^2+q^2)=E(q-q^2)=\frac{1}{2}-\frac{1}{3}=\frac{1}{6}
\end{displaymath}

$S^2, \sigma_1^2, \sigma_2^2$: line's left endpoint handled in a similar way




20.3 Automated Position Inspection: False-Alarm and Misdetection Rates
in industrial position inspection: mechanism machines part to specification
inspection: ensures machining or part placement is correct
automated inspector: consists of machine identifying critical object points
$t$: known number for relative position
$x$: actual position
$x$: Gaussian distribution with mean $t$ and standard deviation $\sigma_x$
$t\pm \alpha$: tolerance interval centered around position $t$
$\vert x-t\vert<\alpha$: position is good
$\vert x-t\vert\geq\alpha$: position is bad




actual position $x$: not known
measurement $y$: obtained by observing actual position and measuring it
measurement $y$: noisy and not equal to $x$
$y$ given $x$: Gaussian distribution with mean $x$ and standard deviation $\sigma_y$
$t\pm \beta$: acceptance interval for decision that actual position in tolerance
$\vert y-t\vert<\beta$: inspection system decides the position is good
$\vert y-t\vert\geq \beta$: inspection system decides the position is bad
false alarm: good position falsely called bad
misdetection: bad position missed and incorrectly called good
false-alarm rate is the conditional probability:

\begin{displaymath}
P_F=P(\vert y-t\vert>\beta \ \vert \ \vert x-t\vert<\alpha)
\end{displaymath}

misdetection rate is the conditional probability:

\begin{displaymath}
P_M=P(\vert y-t\vert<\beta \ \vert \ \vert x-t\vert>\alpha)
\end{displaymath}

entire probability model: characterized by five parameters $t,\sigma_x,\sigma_y,\alpha,\beta$
problem: how to compute false-alarm and misdetection probabilities




20.3.1 Analysis
$P(x)$: probability density function for actual position $x$
$P(y\vert x)$: conditional probability density function for $y$ given $x$
with Gaussian distribution assumption:

\begin{displaymath}
P(x)=\frac{1}{\sqrt{2\pi}\sigma_x}e^{-\frac{1}{2}\left ( \frac{x-t}{\sigma_x}
\right )^2}
\end{displaymath}


\begin{displaymath}
P(y\vert x)=\frac{1}{\sqrt{2\pi}\sigma_y}e^{-\frac{1}{2}\left ( \frac{y-x}{\sigma_y}
\right )^2}
\end{displaymath}

conditional probability $P(\vert y-t\vert<\beta\ \vert\ \vert x-t\vert<\alpha)$ closely related to false-alarm probability:

\begin{displaymath}
P(\vert y-t\vert<\beta\ \vert\ \vert x-t\vert<\alpha)=1-P(\vert y-t\vert>\beta\ \vert\ \vert x-t\vert<\alpha)=1-P_F
\end{displaymath}

now

\begin{displaymath}
P(\vert y-t\vert<\beta\ \vert\ \vert x-t\vert<\alpha)=P(-\beta \leq y-t \leq \beta \vert -\alpha \leq
x-t \leq \alpha)
\end{displaymath}


\begin{displaymath}
=\frac{P(-\alpha \leq x-t \leq \alpha, -\beta \leq y-t \leq ...
...+t} P(y\vert x)P(x)dydx}{\int_{x=-\alpha+t}^{\alpha+t} P(x)dx}
\end{displaymath}


\begin{displaymath}
=\frac{\int_{x=-\alpha+t}^{\alpha+t} \int_{y=-\beta+t}^{\bet...
..._x}e^{-\frac{1}{2}\left ( \frac{x-t}{\sigma_x}
\right )^2} dx}
\end{displaymath}

inherent invariance of false-alarm and misdetection probabilities to the scale
$\sigma_x, \sigma_y, \alpha, \beta$
define relative precision $r$ of the measurement:

\begin{displaymath}
r = \frac{\sigma_y}{2\alpha}=\frac{\sigma_y}{2k_\alpha \sigma_y}
=\frac{1}{2 k_\alpha}
\end{displaymath}

=====Garfield 17:67=====




20.3.2 Discussion
when $k_\beta=\frac{\beta}{\sigma_y}$ large: acceptance interval large
$k_\beta$ large: all good positions are accepted
$k_\beta$ large: false-alarm rate small
$k_\beta$ large: bad positions will also be accepted
$k_\beta$ large: high rate of misdetection
$k_\beta$ small: acceptance interval relatively small
$k_\beta$ small: all bad positions expected not to be accepted
$k_\beta$ small: misdetection rate small
$k_\beta$ small: good positions will also not be accepted
$k_\beta$ small: high rate of false alarm
false alarm rate and misdetection rate approximately inverse proportional
three operating curves for a fixed failure rate of 0.05
top operating curve: relative precision of 0.1
middle operating curve: relative precision of 0.065
bottom operating curve: relative precision of 0.05
=====Fig. 20.2=====
three operating curves for a fixed failure rate of 0.01
top operating curve: relative precision of 0.1
middle operating curve: relative precision of 0.075
bottom operating curve: relative precision of 0.05
=====Fig. 20.3=====
fix failure rate and misdetection rate: as relative precision $r$ better,
tolerance interval i.e. st. dev. of measurements smaller
operating curves for smaller values of relative precision below larger ones




fix relative precision and misidentification rate: as failure rate increases
false-alarm rate increases
three operating curves for a fixed relative precision of 0.075
top operating curve: failure rate of 0.02
middle operating curve: failure rate of 0.01
bottom operating curve: failure rate of 0.005
=====Fig. 20.4=====
operating curves for larger failure rates uniformly above smaller ones




for failure rate to increase when relative precision fixed, tolerance interval
must remain the same while st. dev. of actual position increase
if acceptance interval does not change, misidentification rate decreases




20.4 Experimental Protocol
controlled experiments: important component of computer vision
experimental protocol: so experiment can be repeated and evidence verified by
another researcher
experiment protocol states:

protocol: gives experimental design and data analysis plan




The experimental design describes how a suitably random, independent, and representative set of images from the specified population is to be sampled, generated, or acquired.
accuracy criterion: how comparison between true, measured values evaluated
experimental data analysis plan: how hypothesis meets specified requirement
experimental data analysis plan: how observed data analyzed
experimental data analysis plan: detailed enough for another researcher
analysis plan: supported by theoretically developed statistical analysis




20.5 Determining the Repeatability of Vision Sensor Measuring Positions
vision sensors: measure position or location in 1D, 2D, 3D
to determine repeatability of vision sensor: some number of points, times




20.5.1 The Model
: number of points to be measured
$\mu_1,...,\mu_N$: actual but unknown positions of these points
$P(\vert y-t\vert<\beta\ \vert\ \vert x-t\vert<\alpha)$: number of times each point is measured
: each point is -dimensional
$Y_{nm}$: $t\pm \beta$th measurement of the $\sigma_x, \sigma_y, \alpha, \beta$th point
assumption: measurements independent
assumption: difference between actual and measured positions $N(0, r^2 I)$
$r$: standard deviation describing repeatability of vision sensor




20.5.2 Derivation
mean observed positions:

\begin{displaymath}
\hat{\mu}_n = \frac{1}{M} \sum_{m=1}^M Y_{nm}
\end{displaymath}

sum of norms squared of differences between observed positions and mean:

\begin{displaymath}
S^2 = \sum_{n=1}^N \sum_{m=1}^M (Y_{nm}-\hat{\mu}_n)'(Y_{nm}-\hat{\mu}_n)
\end{displaymath}

We need to determine the relationship between $S^2$ and $r^2$.




20.6 Determining the Positional Accuracy of Vision Sensors
vision sensors: may measure position in 1D, 2D, 3D
To determine the accuracy of the vision sensor (after it has been suitably calibrated), an experiment must be performed in which some number of points in known positions are exposed to the sensor, the measured positions are compared with the known positions, and the accuracy is computed in terms of the degree to which the actual and measured positions agree.
positions of points: random and not follow regular pattern
number of points measured large enough: variance of accuracy small




20.6.1 The Model
: number of points to be measured
$\mu_1,...,\mu_N$: actual but unknown positions of these points
$\mu_1^*,...,\mu_N^*$: unknown expected positions of these points
points: independent
points: deviations between actual and nominal position $N(0, \sigma_1^2 I)$
$P(\vert y-t\vert<\beta\ \vert\ \vert x-t\vert<\alpha)$: number of times each point is measured
: each point is -dimensional
$Y_{nm}$: $t\pm \beta$th measurement of $\sigma_x, \sigma_y, \alpha, \beta$th point
assumption: measurements independent
difference between $\mu_n, Y_{nm}$: $N(\mu_n+b_n, r^2 I)$
bias vector $b_n$: $N(0, \sigma_b^2 I)$
positional accuracy of vision sensor: described by $r^2+\sigma_b^2$
The purpose of the experiment is to estimate $r^2+\sigma_b^2$ by using a large enough number of samples so that the unbiased estimate $\hat{\sigma}_2$ of $\hat{r}^2 + \hat{\sigma}_b^2$ is guaranteed to be sufficiently close to $r^2+\sigma_b^2$.




20.6.2 Derivation
sum of norms squared of differences between observed and known positions:

\begin{displaymath}
S^2 = \sum_{n=1}^N (Y_n - \mu_n)'(Y_n - \mu_n)
\end{displaymath}

We need to determine the relationship between $S^2, \sigma_1^2, \sigma_2^2$.




20.7 Performance Assessment of Near-Perfect Machines
machines in recognition and defect inspection: required to be nearly flawless
error rate: fraction of time that machine's judgment incorrect
error rate: contains false detection and misdetection errors
false-detection rate: false-alarm rate: unflawed part judged flawed
misdetection rate: flawed part judged unflawed




20.7.1 Derivation
consider false-alarm errors; misdetection errors similar
: sampling size, total number of parts observed
: number of false-alarm judgements observed to occur in acceptance test
$f_\circ$: machine performance specification of false-alarm fraction
maximum likelihood estimate $\hat{f}$ of $\Delta c$ based on : $\hat{f}=K/N$
$\hat{f} < f_\circ$: machine passes acceptance test
$\hat{f} > f_\circ$: machine fails acceptance test
$\Delta c$: true error rate
$X_n$: random variable taking value 1 for false alarm, 0 otherwise




in maximum-likelihood technique, compute estimate $\hat{f}$ as $\Delta c$ maximizing:

\begin{displaymath}
Prob \left ( \sum_{n=1}^N X_n \ = K \vert f \right ) = \left (
\begin{array}{c}
N \\
K
\end{array} \right ) f^K (1-f)^{N-K}
\end{displaymath}




20.7.2 Balancing the Acceptance Test
If the buyer and seller balance their own self-interests exactly in a middle compromise, the operating point chosen for the acceptance test will be the one for which the false-acceptance rate (which the buyer wants to be small) equals the missed-acceptance rate (which the seller wants to be small).




20.7.3 Lot Assessment
In the usual lot inspection approach, a quality control inspector makes a complete inspection on a randomly chosen small sample from each lot.
reason for not inspecting all of the lot: cost
more than specified number of defective products found: entire lot rejected




20.8 Summary
mensuration quantizing error model: computes variance due to random error
=====Oldie 33:120=====



2002-02-26