Shape Factor


The special shape feature is the shape factor which is computed using a combination of the area and boundary length features and is defined by equation (8).

If the shape is circular the shape factor has a maximum value of and is less than for noncircular or more elongated shapes.
Geometric Moments
The order geometric moments of a -dimensional binary object (object pixel = 1, background pixel = 0 ) are defined by equation (9).

These moments are not scale, translation or rotation invariant. To make them scale invariant they can be normalised by dividing by the total number of pixels in :

The order normalised geometric moments of a -dimensional binary object are defined by equation (11)

The centre of mass or centroid is computed from the first order normalised moments and :
.

Computing the Image Gradient


Gradient: (Continuous analysis.) Given f(x,y), the gradient of f(x,y) is equation844
The gradient is a vector; it points in the direction of steepest descent. Two useful measures are the magnitude and direction of the gradient: eqnarray855
There are many, many different methods for estimating the gradient in digital images.

Convolution


Several important optical effects can be described in terms of convolutions.
Let us examine the concepts using 1D continuous functions.
The convolution of two functions f(x) and g(x), written f(x)*g(x), is defined by the integral equation318
For example, let us take two top hat functions of the type described earlier. Let tex2html_wrap_inline3166 be the top hat function shown in Fig. , equation322 and let tex2html_wrap_inline3170 be as shown in Fig. , defined by equation330

Another top hat: tex2html_wrap_inline3170


Fig.14 Convolving two top hats
If we now consider x moving from tex2html_wrap_inline3196 to tex2html_wrap_inline3198, we can see that

Convolution of two top hats
Mathematically the convolution is expressed by: equation349

CENTROIDS


You are looking for the CENTRE OF GRAVITY of an irregular polygon. Also known as the CENTROID. Suppose you cut the polygon out of cardboard or sheet metal. This is the point at which it will balance. My search for "center of gravity" NEAR formula on Alta Vista led me to:
This yielded the following description: Subject 2.02: How can the centroid of a polygon be computed?
The centroid (a.k.a. the center of mass, or center of gravity) of a polygon can be computed as the weighted sum of the centroids of a partition of the polygon into triangles. The centroid of a triangle is simply the average of its three vertices, i.e., it has coordinates (x1 + x2 + x3)/3 and (y1 + y2 + y3)/3. This suggests first triangulating the polygon, then forming a sum of the centroids of each triangle, weighted by the area of each triangle, the whole sum normalized by the total polygon area. This indeed works, but there is a simpler method: the triangulation need not be a partition, but rather can use positively and negatively oriented triangles (with positive and negative areas), as is used when computing the area of a polygon. This leads to a very simple algorithm for computing the centroid, based on a sum of triangle centroids weighted with their signed area. The triangles can be taken to be those formed by one fixed vertex v0 of the polygon, and the two endpoints of consecutive edges of the polygon: (v1,v2), (v2,v3), etc. The area of a triangle with vertices a, b, c is half of this expression: (b[X] - a[X]) * (c[Y] - a[Y]) - (c[X] - a[X]) * (b[Y] - a[Y]); Code available at ftp://grendel.csc.smith.edu/pub/code/centroid.c (3K). Reference: [Gems IV] pp.3-6; also includes code.
 
My understanding of the "very simple algorithm" procedure as described is:
1. Select any vertex and use it as a vertex for the n-2 triangles that are produced when this vertex is connected to each of the other vertexes.
2. Calculate the coordinates of the centroid for each of the triangles produced using this formula: XC = (X(1) + X(2) + X(3))/3 YC = (Y(1) + Y(2) + Y(3))/3 3. Calculate the area of each triangle produced using this formula: [(X(2) - (X(1)) * (Y(3) - Y(1)] - [(X(3) - X(1)) * (Y(2) - Y(1))]/2 (areas may negative! ... for reasons I don't want to go into)
4. Calculate the area of the whole polygon . 5. Calculate the fraction of the total area that each triangle contributes. 6. Calculate the product of each ordinate from #2 and the result of #5. 7. Sum the results from #6. This will yield the coordinates of the centroid of the whole.
Consider now an irregular pentagon with vertexes of coordinates: A(0,0);B(6,13);C(15,11);D(16,6);E(14,2)
 
Take the first vertex as the common one for all the triangles, of which there are three: I: A(0,0);B(6,13);C(15,11) II: A(0,0);C(15,11);D(16,6) III: A(0,0);D(16,6);E(14,2)
Triangle I has centroid coordinates XC1=(0+6+15)/3 and YC1 = (0+13+11)/3 ie (7,8) Triangle I has area = {[(6-0) * (11-0)] - [(15 - 0) * (13-0)]}/2 ie {[6 * 11] - [15 * 13]}/2 = -64.5
Triangle II has centroid coordinates XC2=((0+15+16)/3 and YC2=(0+11+6)/3 ie: (31/3,17/3) Triangle II has area = {[(15-0)*(6-0)] - [(16-0)*(11-0)]}/2 ie:{[15*6]-[16*11]}/2 = -43
Triangle III has centroid coordinates XC3=((0+16+14)/3 and YC3=(0+6+2)/3 ie: (10,8/3) Triangle III has area = {[(16-0)*(2-0)] - [(14-0)*(6-0)]}/2 ie:{[16*2]-[14*6]}/2 = -26
Total area of triangles = -64.5 + -43 + -26 = -133.5
So: the fraction of the total area for each of the three triangles is: Triangle I: -64.5/-133.5 Triangle II: -43/-133.5 Triangle III: -26/-133.5
The centroid of the polygon has Xcoordinate: 7*-64.5/-133.5 + 31/3*-43/-133.5 + 10*-26/-133.5= 8.6579 .... and Y coordinate: 8*-64.5/-133.5 + 17/3*-43/-133.5 + 8/3*-26/-133.5 = 6.2097
This is the procedure as I understand it from the description.

Mean and Variance

Consider one feature x. Suppose that we have n examples of patterns that all belong to the same class. Let the different values for the feature x be x(1), x(2), ..., x(n).

There are two important statistics that we can use to characterize this collection of examples -- the mean m and the variance v *. The mean is the arithmetic average or the center of mass:
m = [ x(1) + x(2) + ... + x(n) ] / n .

In general, if the data fall in one cluster, we expect the mean to be more or less in the center of that cluster. That is, the mean represents a typical value. The variance is a measure of the size of the cluster -- how much departure there is from the typical value. It is defined as the arithmetic average of the square of the deviations from the mean. To be more precise, the conventional definition is
v = [ ( x(1) - m )2 + ( x(2) - m )2 + ... + ( x(n) - m )2 ] / ( n - 1 ) .

Clearly, m has the same dimensions as x, but v has those dimensions squared. The square root of the variance is the RMS value or standard deviation, s, and it has the same dimensions as x:
s = sqrt(v) .

Where the mean measures the location of the center of the cluster, the standard deviation measures its "radius". It can be shown that if x has a Gaussian distribution, 68% of the examples will be within one standard deviation of the mean, and 95% will be within 2 standard deviations.

The Beta Distribution


In this section, we will study a two-parameter family of distributions that has special importance in probability and statistics.

The Beta Function


The beta function B(a, b) is defined for a > 0 and b > 0 by

B(a, b) = integral(0, 1) ua - 1(1 - u)b-1 du.

Mathematical Exercise 1. Show that the B(a, b) is finite for a > 0 and b > 0, using these steps:
  1. Break the integral into two parts, from 0 to 1 / 2 and from 1 / 2 to 1. 
  2. If 0 < a < 1, the integral is improper at u = 0, but (1 - u)b - 1 is bounded on (0, 1 / 2). 
  3. If 0 < b < 1, the integral is improper at u = 1, but ua - 1 is bounded on (1 / 2, 1).

Mathematical Exercise 2. Show that
  1. B(a, b) = B(b, a) for a > 0, b > 0.
  2. B(a, 1) = 1 / a.

Mathematical Exercise 3. Show that the beta function can be written in terms of the gamma function as follows:

B(a, b) = gam(a) gam(b) / gam(a + b).

Hint: Express gam(a + bB(a, b) as a double integral with respect to x and y where x > 0 and 0 < y < 1. Use the transformation w = xy, z = x - xy and the change of variables theorem for multiple integrals. The transformation maps the (x, y) region one-to-one and onto the region z > 0, w > 0; the Jacobian of the inverse transformation has magnitude 1 / (z + w). Show that the transformed integral is gam(a) gam(b).
Mathematical Exercise 4. Show that if j and k are positive integers, then

B(j, k) = (j - 1)!(k - 1)! / (j + k -1)!

Mathematical Exercise 5. Show that B(a + 1, b) = [a / (a + b)] B(a, b).
Mathematical Exercise 6. Show that B(1/2, 1/2) = .
A graph of B(a, b) on the square 0 < a < 10, 0 < b < 10 is shown below.

Graph of the beta function

The Beta Density


Mathematical Exercise 7. Show that f given below is a probability density function for any a > 0 and b > 0:

f(u) = ua - 1 (1 - u)b - 1 / B(a, b), 0 < u < 1

The distribution with the density in Exercise is called the beta distribution with parameters a and b. The beta distribution is useful for modeling random probabilities and proportions, particularly in the context of Bayesian analysis. The distribution has two parameters and yet a rich variety of shapes:
Mathematical Exercise 8. Sketch the graph of the beta density function. Note the qualitative differences in the shape of the density for the following parameter ranges:
  1. 0 < a < 1, 0 < b < 1
  2. a = 1, b = 1 (the uniform distribution)
  3. a = 1, 0 < b < 1
  4. 0 < a < 1, b = 1
  5. 0 < a < 1, b > 1
  6. a > 1, 0 < b < 1
  7. a > 1, b = 1
  8. a = 1, b > 1
  9. a > 1, b > 1. Show that the mode occurs at (a - 1) / (a + b -2)

Simulation Exercise 9. In the random variable experiment, select the beta distribution. Set the parameters to values in each of the ranges of Exercise 1. In each case, note the shape of the beta density function. In each case, run the simulation 1000 times with an update frequency of 10. Note the apparent convergence of the empirical density function to the true density function.

Distribution Function


In some special cases, the beta distribution function and quantile function can be computed in closed form.
Mathematical Exercise 10. For a > 0 and b = 1, show that
  1. F(x) = xa for 0 < x < 1.
  2. F -1(p) = p1/a for 0 < p < 1.

Mathematical Exercise 11. For a > 1 and b > 0, show that
  1. F(x) = 1 - (1 - x)b for 0 < x < 1.
  2. F -1(p) = 1 - (1 - p)1/b for 0 < p < 1.

In general, there is an interesting relationship between the distribution functions of the beta distribution and the binomial distribution.
Mathematical Exercise 12. Fix n. Let Fp denote the binomial distribution function with parameters n and p and let Gk denote the beta distribution function with parameters n - k + 1 and k. Show that

Fp(k - 1) = Gk(1 - p)

Hint: Express Gk(1 - p) as an integral of the beta density, and then integrate by parts.
Simulation Exercise 13. In the quantile applet, select the beta distribution. Vary the parameters and note the shape of the density function and the distribution function. In each of the following cases, find the median, the first and third quartiles, and the interquartile range. Sketch the boxplot
  1. a = 1, b = 1
  2. a = 1, b = 3
  3. a = 3, b = 1
  4. a = 2, b = 4
  5. a = 4, b = 2
  6. a = 4, b = 4

Moments


The moments of the beta distribution are easy to express in terms of the beta function.
Mathematical Exercise 14. Suppose that U has the beta distribution with parameters a and b. Show that

E(Uk) = B(a + k, b) / B(a, b).

Mathematical Exercise 15. Suppose that U has the beta distribution with parameters a and b. Show that
  1. E(U) = a / (a + b)
  2. var(U) = ab / [(a + b)2 (a + b + 1)]

Simulation Exercise 16. In the simulation of the random variable experiment, select the beta distribution. Set the parameters to values in each of the ranges of Exercise 1. In each case, note the size and location of the mean/standard deviation bar. In each case, run the simulation 1000 times with an update frequency of 10. Note the apparent convergence of the sample moments to the distribution moments..

Transformations


Mathematical Exercise 17. Suppose that X has the gamma distribution with parameters a and r, that Y has the gamma distribution with parameters b and r, and that X and Y are independent. Show that U = X / (X + Y) has the beta distribution with parameters a and b.
Mathematical Exercise 18. Suppose that U has the beta distribution with parameters a and b. Show that 1 - U has the beta distribution with parameters b and a.
Mathematical Exercise 19. Suppose that X has the F distribution with m degrees of freedom in the numerator and n degrees of freedom in the denominator. Show that

U = (m / n)X / [1 + (m / n)X]

has the beta distribution with parameters a = m / 2 and b = n / 2.

Tree Search Methods


Basic approach:

 
Fig. 51 Interpretation tree
How do we perform matching?

We can reduce the computational overheads by employing some local geometric constraints to prune the tree further.
These are:
For Edges we could employ:
Distance Constraint
-- The length of the sensed edge must be less than or equal to the length of the model edge under consideration.
Angle Constraint
-- The angle between two adjacent sensed edges must agree with that between the two corresponding matched model edges.
Direction Constraint
-- Let tex2html_wrap_inline3774 represent the range of vectors from any point on sensed edge a to any point on sensed edge b. In an interpretation which respectively pairs sensed edges a and b with model edges i and j, this range of vectors must be compatible with the range of vectors produced by i and j.

For Surface we could employ:

Variance and standard deviation (1 of 2)


The variance is a measure of how spread out a distribution is. It is computed as the average squared deviation of each number from its mean. For example, for the numbers 1, 2, and 3 the mean is 2 and the variance is: . The formula (in summation notation) for the variance in a population is where m is the mean and N is the number of scores.
When the variance is computed in a sample, the statistic (where M is the mean of the sample) can be used. S is a biased estimate of s, however. is an unbiased estimate of s2.