Functional Implementation of Moments Based Region Descriptors in J
Vector 16:3, page 99
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 99
Abstract¶
For many years, the field of computer vision has been concerned with accurate ways of describing shapes. One manner of describing shapes is to use statistical region based descriptors. Moments invariants are often used for this purpose, and are a well respected method of description. The following article describes the use of functional programming, using the J language, to implement six moment based descriptors for the description of icebergs in blob coloured images.
Introduction¶
The theory of computer vision relies upon the ability to accurately describe objects or phenomena. These descriptions can then be used for pattern matching, or object recognition, for example. Both of these tasks rely on accurately describing the concepts in an image, since any further processing uses these descriptions.
In this article, we will be examining the implementation of a set of region based descriptors, which are derived from moments theory. A moment is a statistical measure of the properties of an object, and different properties can be derived from the moments of an object. This paper will illustrate the implementation of six moments based descriptors, which use the zeroth, first and second order moments.
A discussion of the theoretical basis of moments theory is beyond the scope of this paper, and will not be discussed here. For more information, refer to Prokop and Reeves (1992).
Moments techniques are particularly suited to image analysis because they can be adapted to use an array based approach. Since many data analysis packages have optimised array operations (e.g. IDL), it is convenient and efficient to have techniques that can exploit these array optimisations.
Reading the image¶
Description¶
The first step is to read in the image. The image is input as a text file, where each row is separated by a carriage return and line feed. These files are of variable length, both in the number of rows and the length of each row. Each image is a blob coloured image, produced by the SARTRACKER system (Williams et al, 1998). Images are included in the appendix for further information.
Functions¶
The unprocessed file can be read in using the following monadic functions, taking the file name as the argument:
The input file is a text file, where each row is separated by a carriage return and line feed (ASCII codes 13 and 10, respectively). To perform the moments calculations on the image, it must first be converted to a numerical array, which can be easily achieved using the ". or ‘do’ function. However, this function does not produce the desired result unless the text file is first stripped of the carriage return and line feeds.
Two basic functions were developed to accomplish the task; getl and takel. The getl function takes a copy of the file until the next carriage return character. The takel function then removes the next line from the array, including the carriage return and line feed. The result of this two step process is that we have the first row of the array, free of line feeds and able to be changed from text to numeric data.
The next step is to use these functions repeatedly, in order to strip the end lines from every row of the image. Since we do not know how long each row will be, or how many rows there are, we need to use an approach that will continue reading data until there is no data remaining. When used with the right argument of infinity, the power operator can perform this function. The plan then, is to produce a fork to box the unprocessed text file, and to catenate an empty box to the front of this.
This is implemented as the boxed read (br) function:
In order to move rows from one side of the box to the other, a simple head and tail function were implemented:
These can then be used in a fork which retrieves one line of the text file:
Which can then be used with the ^: _, as described above, to read in the entire text file.
Results¶
The functions to read the file produce large arrays of data. For readability, the images used in the functions have been included in the Appendix. As a consequence, the results of these functions will not be shown here, as they are the basis of the other functions in this paper.
Other functions¶
Description¶
At this stage, it is convenient to describe a few simple utility functions, which are later used to compose more sophisticated functions.
Functions¶
The first of these gives the number of elements in an array:
The next two functions, as the names suggest, give the number of rows and columns, respectively, in an image.
Finally, the numberg function gives the number of icebergs in an image:
Results¶
rows 'test1.txt'
22
rows 'test2.txt'
23
cols 'test1.txt'
16
cols 'test2.txt'
31
nele 'test1.txt'
352
nele 'test2.txt'
713
Calculating the moments¶
Description¶
Moments are a well established statistical measure, used traditionally to show the amount of variance in a statistical sample (Prokop and Reeves, 1992). However, Hu showed that moments theory can equally be applied to images, in order to gain information about the spatial properties of regions within the image (Hu, 1962). The moments for an unoccluded object in a discrete image can he given by:
Where:
\(M\) is the number of columns
\(N\) is the number of rows
\(g\) is the binary image of an object.
Functions¶
To consistently use the array based approach, we first construct an array containing the x and y co-ordinates of the image. This is done by using the i. operator to make an array that contains every integer between 0 and n-1, where n is the number of items in each row. This is determined by dividing the number of elements by the number of rows. Similarly, the y array is calculated by using the i. to make an array from 0 to n-1, where n is the number of rows.
At this point, the image is a one-dimensional array. We can easily translate this into a two-dimensional array by reshaping the array by the number of columns, but it is more convenient for the moment to leave the image as a one-dimensional array. However, to perform the moments calculations, we need to produce a binary image of each iceberg. The way that this has been achieved is to use a fork which produces a binary image for each ID number indicated by taking the nub of the image.
The moments is calculated by producing a fork, where the left component is the x array to the power of p, and the right component is a fork that multiplies y to the power of q by the value of the image at each pixel. The right argument of the top level fork is the name of the image file, and the left argument is a vector containing the order of the vector to be calculated. For example, 0 0 moment 'image.txt' will give the zeroth order moment of the image in the file "image.txt".
The result of this function is a vector, where each element is the moment of an region in the image. The identifier of the region can be obtained by the nub or the image, using the ~. operator. For example, ~.@readfile 'test1.txt' gives the vector 1 2 3 4 5, meaning that any region based statistics will refer to the regions in this order. Similarly, ~.@readfile 'test2.txt' produces 1 4 2 3. All other region descriptors discussed in this paper produce vectors which should be interpreted in a similar manner.
Results¶
Area¶
Description¶
The first region based descriptor to be calculated from the moments is also the simplest. The zeroth order moment gives the area of a region. Therefore, the area can be obtained by:
Functions¶
An examination of this formula shows that this gives a simple count of all pixels in the region. This is implemented by a fork, which binds the vector 0 0 to the moment function, forcing it to take 0 0 as the left argument.
Results¶
Centre of Mass¶
Description¶
The centre of mass (COM) can be described as the point about which all mass is evenly distributed – the centre of th object. The centre of mass (denoted by \(\bar x\) and \(\bar y\)) is obtained through the first order moments, using the following equations:
Functions¶
This can be achieved by formulating a visually complex, yet quite simple fork:
The result of this function is a two-dimensional array, where the first row of the array gives the x location of the COM for each shape, and the second row is the y co-ordinates of the COM for each shape. Thus, each column gives the complete COM for each shape. These can be indexed in the same way as the moments data - via the nub of the image.
Results¶
com 'test1.txt'
7.5 8.2459 5.77273 9.29412 4.97222
10.5 9.43716 8.02273 15.0588 16.7778
com 'test2.txt'
15 14.4735 10.0455 21.3467
11 10.7939 10.6364 12.56
Central moments¶
Description¶
The central moments of an image can be used to calculate more advanced descriptors, and are denoted as \(\mu_{pq}\). The central moments are formed by calculating the centre of mass, then translating the objects such that the centre of mass is coincident with the origin of the image. The moments calculated on this normalised image (using the equation for moments as given above) are known as the central moments (Prokop et al, 1992).
Functions¶
As discussed above, the COM can be used to reposition the object so that the COM is coincident with the origin of the image. In keeping with our array based approach, we can simulate this by altering the x and y arrays, according to the value of the COM.
These altered x and y coordinates can be used to calculate the central moments of an object, by substituting the altered x array for the original x array, and likewise with the y array. Thus:
The central moments are denoted by \(\mu_{pq}\).
Results¶
1 0 mu 'test1.txt'
0 1.65201e_13 1.06581e_14 _1.24345e_14 2.04281e_14
1 0 mu 'test2.txt'
0 _1.7053e_13 _1.95399e_14 _7.10543e_14
Orientation Axis¶
Description¶
The orientation axis gives some sense of direction to the object. The formula below describes \(\phi\), which is the angle between the x axis, and the principal axis, major or minor, which is closest to the x axis.
Functions¶
Implementing \(\phi\) in J requires only slight complexity, using a fork of the form:
Results¶
fi 'test1.txt'
0 _0.118375 0.0137031 _0.0341932 0.531458
fi 'test2.txt'
0 _0.0495822 0.310555 _0.378673
Image ellipse¶
Description¶
The image ellipse describes the ellipse which most closely fits a shape - that is, an ellipse about which all the first order moments are the same as the actual object. The image ellipse is defined in terms of a major and minor axis, which can be calculated using the following formulae:
Where \(\alpha\) is the major radius and \(\beta\) is the minor radius of the ellipse. Obviously, the approximate length and width of the region will be twice the value of the major and minor radii (respectively).
The intensity of the image ellipse is a measure of how well the ellipse fits the object. This is a very simple calculation, and is specified by:
Functions¶
The calculation of the principal axes was implemented using two rather complex forks:
top =:(+:@+:@*:@mu~&1 1 %:@+ 2 0&mu *:@-0 2&mu)
major =: 0 0&mu %:@%~ 2 0&mu +:@+ 0 2&mu + top
minor =: 0 0&mu %:@%~ 2 0&mu +:@+ 0 2&mu - top
The intensity also makes a simple fork, using the major and minor functions:
Results¶
major 'test1.txt'
16.4283 12.045 5.64905 2.63637 4.4969
major 'test2.txt'
23.5421 17.4863 5.19964 6.35354
minor 'test1.txt'
12.7584 9.036 2.6229 2.21923 2.60758
minor 'test2.txt'
18.6486 13.2773 2.83953 4.12198
Conclusion¶
A functional approach to moments based descriptors provides a clear illustration of the simplicity of both the descriptors and the J language. The functions implemented in this paper illustrate how moments theory can be put to practical use in image processing, using blob coloured images. Further work in this area could include functions which would implement pattern matching over a number of images, using the region based descriptors implemented in this paper.
References¶
- Holmes, W.N. "Functional Calculation" (series of articles to be offered for publication) 1996.
- Hu, M.K. "Visual pattern recognition by moments invariants" IRE Transactions on Information Theory IT-8, 179-187, 1962.
- Sonka, M, Hlavac, V., and Boyle, R. Image Processing, Analysis and Machine Vision. London: Chapman & Hall, 1993.
- Williams, R.N., and Crowther, P. "Application of a Technique, based on Local Image Homogeneity, to delineate Spatial Objects in Satellite Images" In Publication, IJRS 1998.
- Prokop, R.J., and Reeves, A.P. "A survey of Moment-Based Techniques for Unoccluded Object Representation and Recognition" CVGIP: Graphical Models and Image Processing vol. 54, no. 5, September 1992.
Appendix A - Images¶
Two images were used to test the functions described in this paper. The preprocessing of the images was completed by the SARTRACKER program (Williams, Rees and Young - see Williams et al 1998). The images depict icebergs in the Southern Oceans surrounding Antarctica, and the original images were synthetic aperture radar images from ERS-1. The images shown here are segmented, and each shade of grey represents a numerical value, depicting a region to which the pixel belongs. There are two regions in these images that do not depict icebergs. These are the border, and the background. Although these are treated in the same manner as icebergs, a cursory examination of the images reveals that they are not icebergs.
Image "test1.txt"¶
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 2 2 2 2 2 3 3 2 2 2 2 2 2 2 1
1 2 2 2 2 3 3 3 2 2 2 2 2 2 2 1
1 2 2 2 3 3 3 3 2 2 2 2 2 2 2 1
1 2 2 2 3 3 3 3 3 2 2 2 2 2 2 1
1 2 2 3 3 3 3 3 3 2 2 2 2 2 2 1
1 2 2 3 3 3 3 3 3 2 2 2 2 2 2 1
1 2 2 2 3 3 3 3 3 2 2 2 2 2 2 1
1 2 2 2 3 3 3 3 2 2 2 2 2 2 2 1
1 2 2 2 2 3 3 3 2 2 2 2 2 2 2 1
1 2 2 2 2 3 3 2 2 2 2 2 2 2 2 1
1 2 2 2 2 3 3 3 2 2 2 4 2 2 2 1
1 2 5 5 5 5 3 4 4 4 4 4 2 2 2 1
1 2 5 5 5 5 5 4 4 4 4 4 2 2 2 1
1 2 5 5 5 5 5 5 4 4 4 4 2 2 2 1
1 2 5 5 5 5 5 5 5 4 4 2 2 2 2 1
1 2 5 5 5 5 5 5 5 5 2 2 2 2 2 1
1 2 2 2 5 5 5 5 5 5 2 2 2 2 2 1
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Image "test2.txt"¶
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 2 2 2 2 2 2 2 4 4 4 4 4 4 4 4 4 3 3 3 3 3 4 4 4 1
1 4 4 4 4 4 2 2 2 2 2 2 2 2 4 4 4 3 3 3 3 3 3 3 3 3 3 3 4 4 1
1 4 4 4 4 4 2 2 2 2 2 2 2 2 2 4 4 3 3 3 3 3 3 3 3 3 3 3 3 4 1
1 4 4 4 4 4 4 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 4 4 1
1 4 4 4 4 4 4 4 2 2 2 4 4 2 2 2 3 3 3 3 3 3 3 3 3 4 3 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 3 3 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
C. Anne Chamley, BappComp