  % -*- Mode:TeX -*-
 \def\thetitle{Pattern Recognition and Tracking by Texture-Locked Loops}
 \def\theabstract{An important class of spatial patterns displaying
long-range correlations can be recognized in a natural way by {\sl
local} algorithms, provided suitable provisions are made for massive
iteration.  Here we discuss how ``neural networks'' in the form of
cellular automata can be used for this kind of recognition task.}

 \documentstyle{article}
 \twocolumn
 \setlength{\textwidth}{480pt}
 \setlength{\textheight}{600pt}
 \setlength{\oddsidemargin}{-16pt}
 \setlength{\topmargin}{-16pt}

 \input{title}
 \begin{document}
 \maketitle 
 \sloppy

 \def\by{$\times$}
 \def\single{0.35\textwidth}
 \def\double{0.68\textwidth}

\section{Introduction}

We shall introduce a pattern-recognition method that is applicable to a
limited but pervasive class of patterns---typically, natural landscape
features such as rivers, coastlines, urban agglomerations, etc., as they
may appear on a satellite photograph; fingerprints and other biological
constructs; and in general textures and structures whose long-range
spatial correlations are ultimately explainable in terms of the repeated action
of simple local mechanisms.  This method, which can be thought of as a
generalization of the well-known {\sl phase-locked loop}, is insensitive
to large amounts of noise; it can take best advantage of the peculiar
trade-offs in computational resources offered by fine-grained parallel
processors (such as Cellular Automata Machines, the Connection Machine,
and the Massively Parallel Processor); finally, by its very nature this
method is a to certain extent ``aware'' of its capabilities and its
limitations.

\medskip

An aerial photograph of a river and a close-up of a human face both
display remarkable spatial correlations {\sl over a wide range of
scales}.  However, the correlations displayed by a face (or a tank, or a
piece of text) are of a much deeper nature than those displayed by a
river (or a bank of clouds, or a fingerprint).  A face is the surface
product of many levels of transformational grammars, while the
characteristic shape of a river course is produced by the indefinite
repetition of relatively simple physical interactions---which, moreover,
are to a good approximation {\sl local} and {\sl uniform}.

A computer program for ``faceness'' (that is, one capable of generating
a wide and a fairly representative selection of faces) and one for
``riverness'' may well require comparable amounts of computation
(number of machine cycles) to produce an individual item (face or
river).  However, while in the case of ``faces'' one can anticipate the
need for a program that will make a single pass through a large, complex
algorithm, in the case of ``rivers'' one can plausibly expect the
desired result from a large number of passes through a simple, local
algorithm---the natural processes mentioned above can be
viewed as an existence proof for such an algorithm.

Our method is geared at recognizing patterns of the kind that can be
generated in the latter way, i.e., by massive iteration of simple,
local, and uniform transformations.  Though such patterns do not exhaust
the class of recognition tasks the human or robotic eye may be faced
with, nonetheless they are very pervasive---since they reflect
ubiquitous physical constraints that influence the make-up of natural
objects (cf.\ \cite{vichniac}).  In particular, patterns of this kind
play an overwhelming role during the first stages of analysis of visual
information (front-end processing)---where the largest amounts of data
must be handled, and thus computation efficiency and amenability to
parallel processing are at a premium.

\medskip

Section \ref{pll} briefly recalls the concept of `phase-locked loop'.
Section \ref{tll} uses an imaginary but plausible scenario to
illustrates the concept of `texture-locked loop' as applied to a
recognition task of realistic interest.  Section \ref{anneal} presents
in detail a working example of texture-locked loop for a less ambitious
recognition task.  Finally, Section \ref{disc} briefly attempts to
relates texture-locked loops to the relevant
mathematical and technological contexts.

\section{Phase-locked loops}\label{pll}

As we shall see, in the texture-locked loop method a pattern {\sl
generation} mechanism is turned into a pattern {\sl recognition}
mechanism by the introduction of negative feedback.  This technique for
dealing with an inverse problem is well illustrated by the familiar {\sl
phase-locked loop}\cite{viterbi}.  Some intelligence is encoded in the phase or
frequency of a sine-wave carrier (e.g., FM broadcasting), transmitted
through a noisy channel, and eventually received as a weak signal
swamped by noise.  In attempting to recover the intelligence from the
message (signal plus noise), the general {\sl shape} of the carrier
(i.e., the fact that it is a sine wave) and its approximate frequency
are known in advance: only the phase is unknown.  Instead of burdening
our recognition circuit with the task of reconstructing the wave shape
from the message, we provide it with a Voltage-Controlled Oscillator
capable of synthesizing a clean sine wave in the desired frequency
range; all we ask of the phase-locked loop is to fine-tune the VCO so as
to dynamically lock its phase onto that of the carrier buried in the
message.  To this end, the synthetic signal is convolved with the
message through a suitably-shaped time window encompassing several
cycles, and the result is used to ``pull'' the VCO's frequency.  The
amount of pull that is necessary to maximize the correlation between the
synthetic signal and the message is, in first approximation,
proportional to the sought-for phase.

Intuitively speaking, the phase-locked loop has deliberately been made
so single-minded that it cannot help seeing a clean sine wave in {\sl
every} message.  All the message can do is gently encourage the circuit
to adjust the parameters of this Platonic ideal to those of the current
reality.  Too strong a coercion, and the loop will snap out of lock
rather than further compromise on its principles.  (By the way, it is
possible to provide the circuit with a {\sc lock/no-lock} indicator, to
tell us whether the loop is currently locked onto a target or is
aimlessly wandering in search of a match.) 

It is this single-mindedness that gives the phase-locked loop its power.
When {\sl strong}, {\sl localized} clues are not available, the framework provided by a very
specific working hypothesis about the nature of the target signal allows
one to make the most of a large number of {\sl weak}, {\sl distributed} clues.

\section{Texture-locked loops}\label{tll}

For definiteness, let us restrict our attention to two-dimensional
cellular automata with two states per cell (`0' and `1').  Suppose we
had managed to engineer a cellular-automaton rule producing the
following kind of behavior:
 \begin{itemize}
  \item We start with a random initial configuration containing, say,
50\% of `1's.  Macroscopically, this yields a uniformly gray picture.
  \item As we run the rule, from this gray picture there start
condensing at random places a number of thin branched filaments.
These filaments are continually wiggling, breaking up, and reconnecting themselves
in new ways, perhaps like scum on an agitated water surface.
  \item New thin filaments are continually created, but competition
between ``evaporation'' and ``surface tension'' dictates that they
should either wither away or attach themselves to thicker filaments and
slowly be absorbed by them.
  \item As filaments grow in thickness by the above accretion mechanism, their
shapes becomes less wiggly and their movements more stately.
  \item After a long time, the cellular-automaton configuration will
have evolved into a river-like pattern, with main branches,
tributaries, subtributaries, etc.  At the different levels of this
hierarchy, the statistical parameters for radius of curvature, spacing
of branches, angle of graft, etc.\ will be roughly
comparable to those of a real river system.
  \item This river pattern will keep shifting and readjusting
itself, describing a random walk through the space of possible
river-like patterns.
 \end{itemize}
   In other words, we postulate a cellular-automaton rule that
embodies the concept of `riverness'---in the sense that its set of
attractors (for long-term, macroscopic behavior) coincides with the set
of plausible river systems.  Left to itself, this cellular automaton
will {\sl always} generate rivers, {\sl only} rivers, and, in an ergodic
sense, {\sl all} possible rivers.  Given what we know about the
capabilities of cellular automata and the nature of the task, the above
scenario is not preposterous.

\medskip

Now we take an actual aerial picture of a large area which may
contain rivers (and may also contain other features such as houses,
cultivated plots, etc.).  The picture's details may be obscured by
substantial amounts of noise (such as emulsion grain, diffraction,
atmospheric turbulence), so that what at a distance is clearly perceived
by our eyes as a river will be represented in the picture by statistical
correlations between randomly scattered patches rather than by a sharp,
continuous line.

Finally, we introduce some local, weak, nonlinear coupling between the
dynamics of the original cellular automaton and this picture.  For
instance, one may imagine that the cellular automaton has been superposed
to the picture, and that the natural probability of a thread condensing at any
particular spot (cf.\ point 2 above) is slightly enhanced if the
underlying portion of the picture is darker than average, and 
correspondingly depressed if less than average.

\medskip

Let us initialize the cellular automaton to a random state and observe
its evolution under these conditions.  It is clear that the space of
all possible rivers will now be sampled with a bias that favors rivers
similar to those in the picture: in their wanderings, the synthetic rivers
will spend proportionally more time hovering about the real rivers than
about ground features that poorly correlate with a river shape.
Supposing that recognizable rivers are indeed present in the picture,
if we take a time-exposure of the cellular automaton we will see
a river pattern that is very sharp in those places where the presence of a river
is unmistakeable, and perhaps a bit smeared in those areas where several variant
courses are compatible with the photographic data.

If no rivers are present in the picture, the result will depend on the
level of ``thermal agitation'' in the cellular automaton, the strength
of the coupling between the cellular automaton and the picture, and the
length of the time-exposure.  In ideal circumstances, the synthetic
rivers will freely roam about the whole area, yielding a uniformly gray
time-exposure (an indication of {\sc no-lock}).  But clearly the
parameters of the texture-locked loop can be adjusted over a wide
range---from ``quick and dirty'' recognition, where the system will
early on latch onto anything that is vaguely reminiscent of a river, to
``slow and fussy,'' where the shifting rivers will ultimately settle on
a steady pattern only if all the cues provided by the picture meet
stringent acceptance criteria.

\medskip

One may even envisage a real-time, airborne recognizer which will seek
rivers and track them as they slowly drift under the camera's eye.  In
this case, as in ordinary phase-locked loops, the parameters of the
texture-locked loop may be differently optimized for the seeking stage
and the tracking stage.

\section{A concrete example}\label{anneal}

Though the above scenario is plausible, we don't expect that the task of
engineering a satisfactory cellular-automaton rule for `riverness' will
be a trivial one.\footnote
    {In a related field, namely the modeling of fluid
dynamics, a main task is to develop cellular-automaton rules
for the Navier-Stokes equation; though a rule directly based on
physical principles (e.g., conservation of energy and momentum) and
yielding macroscopic behavior similar to that of the Navier-Stokes
equation was discussed over a decade ago, hydrodynamicists
and computer scientists are still hard at work perfecting the technique
in order to improve accuracy and efficiency\cite{fhp,super}.}
    On the other hand, our main concern here is not ``For a particular
class of patterns, to devise a cellular-automaton rule generating that
class (i.e., having that class as a family of attractors),'' but ``Given
a rule that happens to {\sl generate} a certain class of patterns, to
turn this rule into a {\sl recognizer} for the same class by application
of suitable feedback.''

\medskip

The cellular-automaton rule we'll be using in the present example is a
simple annealing rule based on majority vote in the presence of moderate
noise.  Let us start with a cellular automaton which counts the number
$n$ of `1's in the 3\by3 window surrounding each cell.  If $n\geq5$, the
new state $y$ of the cell will be `1'; if $n\leq4$, the new state will be `0'
(``simple majority''---cf.\ \cite{book}, p.~41). In other words,
the response of the system is given by the following table
 \begin{equation}
  \begin{array}{cccccccccccc}
 n & & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
 y & & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 
  \end{array}
 \end{equation}

\figw{fig.quench}{\single}{Simple majority (``quenching''): Evolution of
a random initial configuration (a), after 10 (b) and 100 (c) steps. No significant
changes occur after the first few steps.}

  From a random initial
configuration containing equal amounts of `0's and `1's, in a very few steps this rule yields a stable pattern
of microscopic domains (``quenching''), as in Figure \ref{fig.quench}.  To
achieve gradual ``annealing'' this rule is modified as follows:
if the majority is marginal ($n=4$ or 5), the response is `0' or `1' at
random with equal probabilities. This is equivalent to adding some random $\pm1$ jitter
either to the count or to the threshold.\footnote
    {A separate bit-plane of the cellular automaton, governed by an
appropriate shuffling rule, provides an adequate source of ``thermal
agitation'' for the present purposes (cf.\ \cite{book}, Chapters 8 and
15).  Using an approach suggested by G. Vichniac, substantially the
same kind of annealing can be achieved without making recourse to an
external thermal reservoir (\cite{book}, p.~41).}
    The corresponding table is
 \begin{equation}
  \begin{array}{cccccccccccc}
 n & & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\
 y & & 0 & 0 & 0 & 0 & ? & ? & 1 & 1 & 1 & 1 
  \end{array}\quad,
 \end{equation}
 where `?' represents the outcome of a coin toss.

The class of patterns generated by this rule is illustrated by the
sequence of Figure \ref{fig.anneal}.  In a few steps, the initial
randomness separates out into fine-grained domains of of `1's and
`0's, much as before; however, now the domains keep growing and
coalescing indefinitely.  The boundaries between domains display
{\sl surface tension}---tending to ``fill bays'' and ``erode capes'' at
a rate proportional to the local radius of curvature (cf.\ Figure
\ref{fig.bays-and-capes}).

\figw{fig.anneal}{\double}{Noisy majority (``annealing''): Evolution
of a random initial configuration after 4, 16, 64, 256, 1024, and 4096 steps.}

\figw{fig.bays-and-capes}{\single}{Annealing: Superposition of two successive
stages of evolution (128 and 256 steps) clearly displays the ``surface
tension'' effect, which leads to the filling of bays and erosion of capes.}

The patterns generated by this rule may well describe the shape and distribution
of vegetation patches in an areas of precarious ecological equilibrium---such
as where grassland merges with desert---or water/land boundaries
in wetlands.

\medskip

\figw{fig.target}{\single}{The ``message'' pattern (a), transmitted through
a very noisy channels, yields a received ``signal'' (b) in which the original
pattern is barely discernible.}

Let us consider now a typical pattern generated by the annealing rule (Figure \ref{fig.target}a),
and imagine taking an aerial photograph of it, represented by Figure \ref{fig.target}b;\footnote
    {In reality, we have XOR'ed the picture's bit pattern with $\approx 7/16$ of random noise, to simulate
emulsion grain and other sources of noise, and then run it
through a few steps of a diffusion rule (\cite{book}, p.~156), to simulate
diffraction and scattering in the optical path.}
    in this picture, the original pattern is barely discernible.
Our aim is to exploit the annealing rule itself to reconstruct the ``message''
\ref{fig.target}a from the noisy ``signal'' \ref{fig.target}b.

For this purpose, we shall couple the annealing rule to the signal
as follows: we superpose the bit-plane on which the
annealing rule is operating (i.e., the system of Figure \ref{fig.anneal})
to the bit-plane containing the signal, and at every site of the
cellular automaton we cast into the urn not only the votes from the nine
neighbor-cells  but also a vote from
the underlying picture-cell, so that we have ten votes to count.
The new table is the following
 \begin{equation}
  \begin{array}{ccccccccccccc}
 n+s & & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
   y & & 0 & 0 & 0 & 0 & ? & ? & ? & 1 & 1 & 1 & 1
  \end{array}\quad,
 \end{equation}
 where $s$ denotes the vote cast by the signal.  Thus, dark areas in the
signal provide a slight bias in favor of the growth of dark areas in the
annealing system, and similarly for light areas.

\figw{fig.bias}{\double}{Texture-locked loop: When the annealing rule is
coupled with a signal containing a plausible annealed pattern deeply 
buried in noise, the evolution (sampled at 4, 16, 64, 256, 1024, and 4096 steps)
is biased in favor of patterns similar to the original message.}

If we run the biased rule from a random initial configuration, as in
Figure \ref{fig.bias}, the early evolution of black and white domains
will be qualitatively very close to that obtained with
the unbiased annealing rule. However, almost invariably the evolving
pattern will converge to one that is very close to the original message.

The first three frames of Figure \ref{fig.trials} show the final
patterns extracted from the signal of Figure \ref{fig.target}b by the
biased-annealing rule on three trials. Each trial started with a fresh
random configurations in the annealing system's bit-plane,
but used the same target signal (i.e., that of Figure \ref{fig.target}a);
For comparison, the reconstructed pattern (dark gray) is shown
superposed to the original message (light gray). The last
frame shows the average of the three patterns; further averaging
would of course give a sharper reconstruction of the message as it
can be inferred from the received signal by this particular
pattern-recognizing device.

\figw{fig.trials}{\single}{Three separate texture-locked loop runs (a,b,c)
biased by the same noisy signal, and their average (d).}

\medskip

All of the above experiments were performed on {\sc cam}-6---an
inexpensive, high-performance cellular automata machine\cite{book}.  Of
the four available bit-planes (of size 256\by256), one was used for the
annealing system, one for the signal-pattern, and one for the thermal
reservoir. The longest runs (4096 steps) took approximately one minute.

\section{Discussion and conclusions}\label{disc}

The texture-locked approach to image-processing achieves robustness and
conceptual simplicity at a price---namely, a large amount of
computation---and would be an impractical method if one had
only general-purpose computers available.  The ``novelty'' of neural networks is
that extraordinarily large amounts of computation can be performed at
vanishing cost, provided only that the computation in question is of a
kind that can be naturally performed in parallel by {\sl simple, regular
networks}, which can be ``bought by the pound,'' so to speak.  In a
typical cellular automata machine architecture the
amount of useful processing increases at the same rate as the amount of
memory---in a sense, such an architecture allows one to construct in
arbitrarily large amounts {\sl synthetic} matter obeying man-given
laws---subject only to general constraints (uniformity, locality, etc.)
analogous to those of {\sl physical} matter.

What can one do with such synthetic matter?  Before trying to explicitly
design and build complex objects out of it, one should just try to
let it attain equilibrium, either as an isolated system or under the
influence of externally applied ``fields'' (the coupling of an annealing
system with a photographic image is an example of such an external
influence). The statistical mechanics of ``amorphous'' systems is a burgeoning field
filled with beautiful discoveries, for indeed these equilibria can
spontaneously yield patterns of amazing complexity, and {\sl some} of
these patterns may be just the kind that we are interested in for
certain applications.

\medskip

In a sense, neural networks provide a lot of new answers, and cheaply;
the issue is to find problems to which these answers can naturally be
applied. We cannot expect to find in neural networks the answer to {\sl all}
problems, or even {\sl most} problems. One will have to scour
the scientific arena for problems whose solution can be arrived
at by quasi-physical relaxation of quasi-physical materials.
We believe that the texture-locked loop idea is an example of a good match
between a well-recognized problem and the computing capabilities 
of neural networks.

 \begin{thebibliography}{99}
 \bibitem{fhp} Frisch, U., B. Hasslacher, and Y. Pomeau, ``Lattice-Gas
Automata for the Navier-Stokes Equation,'' {\sl Phys.\ Rev.\ Lett.\
\bf56} (1986), 1505--1508.
 \bibitem{super} Margolus, N., T. Toffoli, and G. Vichniac, ``Cellular
Automata Supercomputers for Fluid Dynamics Modeling,'' {\sl Phys.\ Rev.\ Lett. \bf 56} (1986), 1694--1696.
 \bibitem{book} Toffoli, Tommaso, and Norman Margolus, {\sl Cellular Automata Machines---A new
environment for modeling}, MIT Press (1987).
 \bibitem{vichniac} Vichniac, G\'erard, ``Simulating Physics with Cellular Automata,'' {\sl Physica \bf10D}
(1984), 96--115.
 \bibitem{viterbi} Viterbi. A. J., {\sl Principles of Coherent Communication}, McGraw-Hill (1966).

 \end{thebibliography}


\end{document}







