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

For example, let us take two top hat functions of the type described earlier. Let

be the top hat function shown in Fig. ,

and let

be as shown in Fig. , defined by

Another top hat:

is the reflection of this function in the vertical axis,
is the latter shifted to the right by a distance x.
Thus for a given value of x, integrated over all is the area of overlap of these two top hats, as has unit height.
An example is shown for x in the range in Fig.

Fig.14 Convolving two top hats
If we now consider x moving from

, we can see that

for or , there is no overlap;
as x goes from -1 to 0 the area of overlap steadily increases from 0 to 1/2;
as x increases from 0 to 1, the overlap area remains at 1/2;
and finally as x increases from 1 to 2, the overlap area steadily decreases again from 1/2 to 0.
Thus the convolution of f(x) and g(x), f(x)*g(x), in this case has the form shown in Fig. 15,

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 )² + ( x(2) - m )² + ... + ( x(n) - m )² ] / ( 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) = _{(0, 1)} u^a^{- 1}(1 - u)^b-1du.

$Mathematical Exercise$ 1. Show that the B(a, b) is finite for a > 0 and b > 0, using these steps:

Break the integral into two parts, from 0 to 1 / 2 and from 1 / 2 to 1.
If 0 < a < 1, the integral is improper at u = 0, but (1 - u)^b - 1 is bounded on (0, 1 / 2).
If 0 < b < 1, the integral is improper at u = 1, but u^a - 1 is bounded on (1 / 2, 1).

$Mathematical Exercise$ 2. Show that

B(a, b) = B(b, a) for a > 0, b > 0.
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 + b) B(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.

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) = u^a - 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:

0 < a < 1, 0 < b < 1
a = 1, b = 1 (the uniform distribution)
a = 1, 0 < b < 1
0 < a < 1, b = 1
0 < a < 1, b > 1
a > 1, 0 < b < 1
a > 1, b = 1
a = 1, b > 1
a > 1, b > 1. Show that the mode occurs at (a - 1) / (a + b -2)

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

F(x) = x^a for 0 < x < 1.
F ^-1(p) = p^1/a for 0 < p < 1.

$Mathematical Exercise$ 11. For a > 1 and b > 0, show that

F(x) = 1 - (1 - x)^b for 0 < x < 1.
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 F_p denote the binomial distribution function with parameters n and p and let G_k denote the beta distribution function with parameters n - k + 1 and k. Show that

F_p(k - 1) = G_k(1 - p)

Hint: Express G_k(1 - p) as an integral of the beta density, and then integrate by parts.

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

a = 1, b = 1
a = 1, b = 3
a = 3, b = 1
a = 2, b = 4
a = 4, b = 2
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(U^k) = B(a + k, b) / B(a, b).

$Mathematical Exercise$ 15. Suppose that U has the beta distribution with parameters a and b. Show that

E(U) = a / (a + b)
var(U) = ab / [(a + b)² (a + b + 1)]

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:

Nodes of the tree represent a scene to model primitive (e.g. edge, surface) match.
Let Tree have m branches at each node that correspond to model primitives.
Let level of tree represent a model primitive.
The level and node position specify a match pair.
Use a depth first tree search to find a match.
One traversal through tree gives a match list -- a possible match of scene to model features.
Representation called a search or interpretation tree.

Fig. 51 Interpretation tree
How do we perform matching?

At each level of the tree, one of the edges from the scene is matched with each of the m possible edges in the model.
Each node has m children representing taking the match proposed so far together with all possible matches for the current scene edge.
A transformation representing the match so far can be maintained.
Search tree in depth first manner and pruned by rejecting interpretations that fail to satisfy current match.
The search space is large -- possible combinations for n scene primitives.
A lot of computations?

We can reduce the computational overheads by employing some local geometric constraints to prune the tree further.
These are:

Cheap to compute and employ.
applied before the transformation test.

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 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:

Angles between planes.
Area of planes.
Invariants.
Measures of curvature.

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 s².