In this appendix we shall develop programs in POP-11 for generating edge maps, matching templates (from method 1), and finding regions (from method 2).
We first need some way of representing images obtained
from the video digitizer and also the stored templates.
The POP-11 array is the ideal construct for this. An array is a
data-structure containing a
collection of POP-11 items indexed by integers. For example, we can store the
names of the months of the year as an array in which each name is indexed by
the number of that month. The array is first created using the POP-11
procedure newarray, which takes as argument a list containing the
desired upper and lower bounds of the index numbers. Then each array cell is
filled with the name of a month of the year:
vars months;
newarray([1 12]) -> months;
"January" -> months(1);
"February" -> months(2);
[IMAGE ]
"December" -> months(12);
Now to find out the name of the 6th month we write
months(6) =>
** June
There will be a mishap if you try to access an array cell which is outside the declared bounds of the array.
The built-in POP-11 procedure boundslist returns a list containing the
upper and lower bounds for a particular array -- for example,
boundslist(months) =>
** [1 12]
Instead of using arrays to store the names of the months we could have used lists. However, arrays are a very efficient means for accessing data that have to be indexed by number, and for this reason they are preferable when large amounts of data are to be stored, as with the grey-levels of an image.
Cells of the array months are accessed by a single integer argument. Arrays of this type are known as 1-dimensional arrays. However, because an image is essentially a 2-dimensional array of pixels, we shall use 2-dimensional arrays to store the grey-levels: that is, arrays which require two integer arguments to access or update their elements. The first argument is the number of the column and the second argument is the number of the row.
The same POP-11 procedure newarray is used to create 2-dimensional
arrays. The single argument is a list specifying the upper and lower bounds
for each of the two indices. Thus, to make an array for storing an image which
is 64 [IMAGE ] 64 pixels in size we do the following:
vars image;
newarray([1 64 1 64]) -> image;
We could assign grey-levels to this array by inserting them one by one into the array cells using 4096 (64 [IMAGE ] 64) assignment statements
4 -> image(1,1);
4 -> image(2,1);
5 -> image(3,1);
[IMAGE ]
72 -> image(64,64);
but
that would be very laborious, so instead we make a list of the grey-levels
and assign this to a POP-11
variable and then transfer the numbers from this list
into the array using a general procedure fillimage, defined as
follows:
![[IMAGE ]](img15.gif){kind=link}
define fillimage(image, list);
/* to transfer numbers from list into array */
vars x, y, g, xsize, ysize;
boundslist(image) --> [1 ?xsize 1 ?ysize];
/* scan array from top-left to bottom-right
inserting grey-levels from list */
for y from 1 to ysize do
for x from 1 to xsize do
list --> [?g ??list];
g -> image(x,y)
endfor
endfor
enddefine;
The
first argument to fillimage (the array image) is a newly
created image array into which grey-levels are to be inserted, and the second
argument (list) is a list of grey-levels ordered from the top-left
pixel to the bottom-right pixel, moving from left to right and from top to
bottom. For example, a list of the grey-levels shown in figure 8.3
would appear as
[4 4 5 ...
1 4 15 ...
...86 71 72] -> grey_levels;
The procedure fillimage generates the row and column indices for each
image array cell (pixel) in turn using two for loops,
one nested within
the other. The outer for loop iterates over the rows and the inner
for loop iterates over the columns, thereby selecting each pixel in the
current row. The pattern matcher is used to extract grey-levels from the
front of list one at a time and to replace list with the values
remaining (both these operations are achieved by a single use of the pattern
matcher).
First, we shall produce an edge map from a given image. The procedure
findedgels returns an array which is the same size as the image array
given as its argument, with a 1 in those cells for which there is a nearby
edge element in the corresponding point in the image array, and 0 otherwise.
define findedgels(image, thrshld) -> edgemap;
vars x, y, xsize, ysize;
/* find the width and height of the given image */
boundslist(image) --> [1 ?xsize 1 ?ysize];
/* make an edge map of the same size as the
given image and initialize each entry to 0 */
newarray([1 ^xsize 1 ^ysize], 0) -> edgemap;
/* scan each pixel in turn */
for y from 2 to ysize-1 do
for x from 2 to xsize-1 do
/* does sum of differences between horizontally
and vertically adjacent pixels exceed a given
threshold? */
if abs(image(x,y) - image(x-1,y))
+ abs(image(x,y) - image(x,y-1)) > thrshld
then
/* yes so record a 1 in current position */
1 -> edgemap(x,y)
endif
endfor
endfor
enddefine;
We now need to define a procedure for comparing an edge map
derived from a
stored template image with an edge map derived from an input image. First we
define a procedure for performing the comparison at a particular position of
one edge map with respect to the other. The position is specified by the
location of the pixel in the second edge map which lies under the top
left-hand corner of the first edge map. A pair of counters are initialized
to zero.
When all corresponding entries in each edge map have been compared, counter
maxtotal will contain the number of edge elements that should have
been found (i.e., those in the edge map derived from the template), and the
other counter, hittotal, will contain the number of times that an edge
element is found in the corresponding location in both edge maps. The quality
of the match is obtained in numerical form by dividing hittotal by
maxtotal:
define match_at_xy(edgemap1, edgemap2, x, y) -> goodness;
vars xx, yy, xsize, ysize, maxtotal, hittotal;
/* find the size of the edge map from the template */
boundslist(edgemap1) --> [1 ?xsize 1 ?ysize];
0 -> maxtotal; 0 -> hittotal;
/* scan each element of edgemap1 */
for yy from 1 to ysize do
for xx from 1 to xsize do
/* is there an edge element at (xx,yy) in edgemap1 */
if edgemap1(xx,yy) = 1 then
/* increment running total of edges */
1 + maxtotal -> maxtotal;
/* is there a matching edge at
corresponding position of edgemap2 */
if edgemap2(x+xx-1, y+yy-1) = 1 then
/* yes so increment running total of matching edges */
1 + hittotal -> hittotal;
endif
endif
endfor
endfor;
/* compute goodness of match by dividing number of matching
edges by number there would be in an ideal match */
hittotal / maxtotal -> goodness;
enddefine;
The next procedure, match_image, finds an edge map from the stored
template and from the input image and then matches these by sliding one over
the other applying match_at_xy at each position. When the quality of
the match exceeds a threshold value, which is given as an argument to
match_image, the position of that match is printed out:
define match_image(template, image, thrshld);
vars xsize, ysize, xxsize, yysize, x, y, edgemap1, edgemap2;
findedgels(template, 10) -> edgemap1;
findedgels(image, 10) -> edgemap2;
boundslist(template) --> [1 ?xxsize 1 ?yysize];
boundslist(image) --> [1 ?xsize 1 ?ysize];
for y from 1 to ysize-yysize+1 do
for x from 1 to xsize-xxsize+1 do
if match_at_xy(edgemap1, edgemap2, x, y) > thrshld then
[There is a good match at position ^x ^y] =>
endif
endfor
endfor
enddefine;
Using the arrays shown in figures 8.3 and 8.6, and with a threshold value of 0.6, a handful of positions are printed, all in the vicinity of the correct position:
** [There is a good match at position 10 11]
** [There is a good match at position 11 11]
** [There is a good match at position 9 12]
** [There is a good match at position 10 12]
** [There is a good match at position 8 13]
** [There is a good match at position 9 13]
In this case the method seems to work!