2. Theory

Robust machine vision systems are frequently required to recognize targets of unknown scale, unknown position and unknown rotation. In general, any solution to this difficult problem will require that the input imagery be somehow constrained. In industrial machine vision applications, the camera position can be fixed, there is usually a limited number of variations on the object to recognize, and the lighting conditions can be fixed if the system is enclosed. With systems such as this in place, 2D intensity images can be thresholded to yield images typified by figure 2.

  

Figure 2: A contiguous blob of pixels.

By thresholding an image, we seek to eliminate all information except for the general shape of an observed object. From these thresholded silhouette images, referred to as blobs, one observes the low frequency components of the imaged blob: size, orientation, and low-level shape. By edge processing the image, the high frequency detail of the blob's bounding contour is revealed. Figure 3 shows the result of a thresholded 3x3 optimized Sobel edge operation on the blob image.

  

Figure 3: Edge processed blob.

In Visual Pattern Recognition by Moment Invariants[3], Hu derives a set of seven functions that make use of the central moments of a blob image; their output is independent of any translation, rotation or mirror image of a particular blob, and they can be used in conjunction with both the blob image itself and the edge-processed contour image. All the images in figure 4 accurately produce the same numerical result for each of Hu's seven equations.

  

Figure 4: Original, rotated, mirror image, and rotated-mirrored blob.

Hu's equations are based on the uniqueness theory of moments. For a digital image of size (N,M) the p+qth order moments m_pq are calculated, (for $p, q = [0,1,2,\cdots)$ )

$$m_{pq} = \frac{1}{N M} \sum_{x=1}^N \sum_{y=1}^M f(x,y) x^p y^q$$ (1)

The uniqueness theorem of moments: The infinite sequence of moments m_pq is uniquely determined by the joint function f(x,y); conversely, the function f(x,y) is uniquely determined by an infinite sequence of moments m_pq. Strictly, this is only valid for continuous functions whose value is zero wherever x,y are not finite. In general, gross image shape is represented well by the lower-order moments, and high-order moments only reflect the subtleties of a silhouette or boundary image. Nearly all work with moment invariants, including Hu's, depends only on moments of order zero to three.

The central moments of a digital blob image are inherently translation independent,

$$\mu_{pq} = \frac{1}{N M} \sum_{x=1}^N \sum_{y=1}^M f(x,y) (x-\overline{x})^p (y-\overline{y})^q .$$ (2)

Where $\overline{x} = m_{10}/m_{00}$ and $\overline{y} = m_{01}/m_{00}$. Hu's seven moment functions below utilize the central moments of a digital silhouette or boundary image, but are also rotation independent (equations 3 to 9).

  

$$(\mu_{20} + \mu_{02})$$ M₁ = (3)

$$(\mu_{20} - \mu_{02})^2 + 4 \mu_{11}^2$$ M₂ = (4)

$$(\mu_{30} - 3 \mu_{12})^2 + (3\mu_{21} - \mu_{03})^2$$ M₃ = (5)

$$(\mu_{30} + \mu_{12})^2 + (\mu_{21} + \mu_{03})^2$$ M₄ = (6)

$$(\mu_{30} - 3\mu_{12})(\mu_{30} + \mu_{12})[(\mu_{30} + \mu_{12})^2 - 3(\mu_{21} + \mu_{03})^2]$$ M₅ =

$$+ (3\mu_{21} - \mu_{03})(\mu_{21} + \mu_{03})[3(\mu_{30}+\mu_{12})^2 - (\mu_{21} + \mu_{03})^2]$$ (7)

$$(\mu_{20} - \mu_{02})[(\mu_{30} + \mu_{12})^2 - (\mu_{21} + \mu_{03})^2] + 4\mu_{11}(\mu_{30} + \mu_{12})(\mu_{21} + \mu_{03})$$ M₆ = (8)

$$(3\mu_{21} - \mu_{03})(\mu_{30} + \mu_{12})[(\mu_{30} + \mu_{12})^2 - 3(\mu_{21} + \mu_{03})^2]$$ M₇ =

$$- (\mu_{30} - 3\mu_{12})(\mu_{21} + \mu_{03})[3(\mu_{30} + \mu_{12})^2 - (\mu_{21} + \mu_{03})^2]$$ (9)

M₁ through M₆ are all translation and rotation independent for digital images, but M₇ is actually skew invariant - its sign can be used to detect mirror images.

In a paper by Dudani, Breeding, and McGhee[2], Hu's equations above were expanded to act nearly scale-invariant. Using the radius of gyration of a planar pattern, $r = \sqrt{\mu_{02} + \mu_{20}}$, the equations can be normalized so that they remain unaffected by the size of the blob or edge boundary in the digital image:

$$(\mu_{20} + \mu_{02})^{1/2} B = rB$$ M₁' = (10)

M₂' = M₂/r⁴ (11)

M₃' = M₃/r⁶ (12)

M₄' = M₄/r⁶ (13)

M₅' = M₅/r¹2 (14)

M₆' = M₆/r⁸ (15)

M₇' = M₇/r¹2 (16)

For this paper, M₁' will not be used because it requires that the distance from the camera to the observed object, B, is known.

When designing a classifier, either set of above relations can be packed into a seven-dimensional feature vector $\mathbf{X} = \{M_1, M_2, \ldots, M_7\}$. In this high-dimensional space, groups of feature vectors corresponding to particular silhouette blob or edge boundary images can be easily separated by splitting the space with hyperplanes or other high-dimensional surfaces. In practice, as will be shown in the following section, one may not even need all seven moment invariant functions to design a classifier.