position estimate can be determined by computing
the locale centroid. Figure 6 depicts a sequence of
intersecting feasible regions resulting in a single
locale for the target location.
FIGURE 6
SUCCESSIVE INTERSECTION OF FEASIBLE
REGIONS TO OBTAIN THE LOCALE
It has been seen that the locale pattern is very
sensitive to small variations in the shape of the
target. It would seem then, that the position decoding
algorithm would be very sensitive to the deviations
of the contour map model of the target from reality,
either due to noise, distortion, or lack of accurate
representation. This problem is alleviated by
recording in the truth map the relative probability,
for each level of the contour map, that the target was
located there. A grey scale representation of this is
depicted in figure 7.
FIGURE 7
USE OF PROBABILTIY DISTRIBUTION
FOR FEASIBILITY REGIONS
The probability used in the truth map might be
exponential with repect to the magnitude of the
difference between the observed pixel value and that
of the contour levels. The truth map then represents a
portion of the probability distribution for the spatial
coordinates of the target given the pixel value.
Successive pixels are appropriately combined by
point-wise product of the probability distributions for
their independent pixels.
It is more practical to store the logarithm of the
probability distribution, that is; the square magnitude
difference between the observed pixel value and the
contour level. In this case, the joining of the
information from successive pixels is achieved by
summing the corresponding log-probabilities. This
results in a straightforward algorithm which
iteratively updates a "truth map" of numbers. After
all the pixels have been processed, the region within
the truth map defined by all those cells with the
highest value is taken to be the locale for the target.
The possibilities for tuning and refining the
algorithm are many fold. The selection of the list of
pixels can be done so that the most useful ones
appear first. For example, symmetrically opposed
pixels can be processed in succession to take
advantage of a symmetric target shape, or pixels
occuring where the image has maximum gradient can
be selected first since these generally contain better
positional information. As the feasible regions are
intersected, and the candidate area of the locale
diminishes in size, processing can be terminated at a
preselected tolerance, thereby avoiding the processing
of unnecessary pixels. Pixels which yield no highly-
likely cells in the truth map can be deemed defective
and eliminated from the analyis. Various probability
measures and pixel weights can be tailored. Occluded
or missing pixels present no obstacle to the
completion of the algorithm.
The algorithm has been implemented with simulated
target images and noise, without elaborate tuning,
and its performance has been extremely robust and
near-optimal. The ease with which good performance
is achieved has been impressive.
9. COMPUTATIONAL
CONSIDERATIONS
The truth table is the primary storage element of the
position decoding algorithm. To economize on space
and associated processing, the truth table is allocated
only about 15 cells on a side, that is; the unit square
representing the area of a pixel is divided into about
225 cells. Since locales tend to be smaller than this
cell size, a method is needed to ensure that at least
one cell is selected by the intersection of feasible
regions. This is accomplished by storing the log-
probability in the truth table and selecting the cell(s)
with the highest probability. Once the truth map has
been evaluated for all the pixels, the process is
reiterated with the resolution of the truth map
increased and centered over the previously selected
cells. At each iteration position decoding provides a
better estimate of the shape and location of the
locale. This process of incrementally increasing the
resolution of the truth map is continued until either
the cell size is less than .001 or the locale is clearly
resolved (extends over about 1/3 of the truth map).
Iterative refinement of the truth map not only saves
storage space, it dramatically reduces the number of
cells which must be evaluated and updated during the
processing. A further reduction is achieved by
processing only those cells which have a sufficiently
high probability value.
Associated with the processing of each cell of the
truth table is an evalutation of the contour map
representing the target. It is important that this
60