REPORT ON PERCEPTRON ((Sanitized)AND CONFLEX(Sanitized)) CONCERNING AUTOMATED IMAGE RECOGNITION

• Document Type: CREST
• Collection: NGA Records (Formerly NIMA)
• Document Number (FOIA) /ESDN (CREST): CIA-RDP78B04770A002300030029-4
• Release Decision: RIPPUB
• Original Classification: C
• Document Page Count: 114
• Document Creation Date: December 28, 2016
• Document Release Date: March 30, 2005
• Sequence Number: 29
• Publication Date: April 2, 1963
• Content Type: MF

Approved For Release 2005/091.02,::,J0FrUp04770A0W00030029-4
NIMINtAND
PPM
SUBOCCT
Director, JPXC
Assistant for Plans end Development
Report on PMPCMPTPOP
and
Image Recognition
2 April 1.963
oneerflin Aut
1. Selected neibers of the Plans and Development Staff were present rt
briefinge on the 19th and 22nd of Perch. The following paragraphs contain
abstracts of these briefings, a summary, and retcamendations for future
action.
2. presented a briefine trn O9
to 1200 on 19 March 19b3 mom 38467. In addition to sber
of the AND Staff, there were representatives from PIO, Ta), Air Force, Army
and Navy Detachments, USPPIC, (ER, and Bu Peps. Security level -was unclasei
a. PIRCUTRON is a means of automated recognition based on statisti(T1
separability in cognitive systems
(1) It may be described as a "biological' computer system consist-
of a sensory matrix coupled through ? complex continuously variable
weighting system to a general purpose digital computer, programmed in
a fashion which siwluutes brain mechanisms.
develomental history began in 1958 eild
on the basis of concepts originated by
Extensive research has been performed since that time in the follow
realms:
(a) Implementation and evaluation of the PRACEPTRON concept.
(b) Application of the PERCEPTRON to photo interpretation.
(0) Application of the PLICEPTRON to character re-2ognition.
(4) Preprocessing of photo reconnaissance date.
This develOpment program has been characterised by fundamental inventi
ottani, She process is deliberate, comprehensive and slow. This research
Declass Review by NGA.
Approved For Release 2005/05/02piA_-_REIPZ9p 4770A002300030029-4
25X1
25X1
?
25X1
25X1
t?r----
Excluded lra, ::,113DaiLl
dewnErzlia and
declassifict,Iliz
--- ?..
itmlnrjAL
Approved For Release 2005/05fE rn
uPumwrai504770A002300030029-4
-2-
frame of reference for all development in this field.. There is *pil-
e yet unreadhed stage in the development of the principle which must
ed before the majority of developmental effort can be directed toward
.pplication. The main effort of this program is now being directed toward
eprocessine of the image. The processes of object detection, isolation
and normalisation are being investigated through systems other than PERCEPTRON,
which is used solely for the recognition process.
This briefine was held tripe 1400 to MO, 22 March 1963/
I In addition to metbers of
evelopment Staff,' Iof USNPIC anl of BuwePa 25X1
sent, Security level was unclassified.
a. cox= I is said to be e "conditioned reflex Computer.
(1) It may be described as a "biological" computer eystee consiet-
ing of a sensory matrix, elements of which are systematically activated
in a large number of different combinations, coupled to a special purpose
digital computer programmed in a fashion which simulates brain mechanisms.
(2) Its developuentat history began late in 1960 at ender En 25X1
Air Porte study contract. The prototype COMPLEX I system wus eompleted
cation of pictures ofl 'personnel was presented. Related reeeareh
in ftvembar 1962. Au_mplesssive demonstration of learning and /dentin-
has been performed in the following reales:
(a)
Basic studies of biological response. systems.
CO Application of the COOL= system to character recognition.
(c)
Application of the COMPLEX aystem to photographic image
recognition.
(d) ?renormalisation of photographic reconnaissance data.
This is apparently a derivative of the original TielEMSON develop-
ment. personnel have utilized these principles to design an ingeniouB,
compact system which may have considerable application in the image recognitior
field. Their prenormalisetion syytem is based an slit scanning of a given
image field at a large nuther of different attitudes and the consequent pattern
of signals generated by such scans.
The nuOber and complexity of developments in this field
indicate e Plana and Develegummt Staff must acquire more information
before a cpiete program for developnont can be established. Mmplicatioec
of the Observations made to date are as follows:
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/OLLPIZAFFQ104770A002300030029-4
-3-
a. The type of approach appeers to dhow nueb ze pro-
Of eventual Application to photo reconnaissanee analysis then the pure
di itsl scan systems such as AMATO.
b. effort is a conservative, compre-
hensive, Tundameatal research approach which is likely to be slow in yielding
directly applicable techniques or hardware. It does however, aerve as e pri-
letry reference with a broad base and a large amouot of accomplished investization.
Ry the eame token it is likely to yield valuable results from continued research..
c. The effort is representative of the relatively young research
thoility. There is evidence of competent, highly motivated, dynamic developeeel
being accomplished. It is possible thatr--land other orgamization3 of this 25X1
type end caliber will produce the first practical devices for automated tareiet
recognition and they may outstrip Iin developing mnme special aspects of 25X1
more efficient electronic legic. In this regard it should be pointed out that
hes invest ad a renormalinetion system very similar to the one preeent1L)
eaused by multipleges within a single field.
_771
under study at t was eventually rejected due to the 7:71: appears 25X1
to overcome this limitation, but due to the limited know e icqutred to date,
a full assessment cannot be made.
5. . Immediate attention will be given to resolution of
W! er of different endeavors being pursued in thi
effort should definitely be supported for it
level, amii there is a strong possibility that pars
-
by a raciLity such as Ishould also be supported. flower,25X1
is felt that further investigation is imperative before a decision can be
resdered on the latter aspect ._Zn eeteblishing priority for funding it ia
import:13# to note that thai Iprogram is currently being supported by the.
Air Fores whereas th effort is to be terminated in June because the Navy
ean no longer fund the program.
Approved For Release 2005/05/02 : CIA-RpP7804770A002300030029-4
25X1
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
DESIGN OF A PHOTO INTERPRETATION AUTOMATON*
SUMMARY
(-71./wri
The paper describes a system for automatic recognition of simple and com-
plex objects in aerial photographs. Preliminary results from a general-purpose
computer implementation of critical portions of the system are presented. Hope
for achievement of a practical device is high because the basic pattern recognition
capability required in the system is, to a great extent, based on the present state
of the art.
INTRODUCTION
The extremely large volume of photographic material now being provided by
reconaissance and surveillance systems, coupled with limited, but significant,
successes in designing machinery to recognize patterns has caused serious con-
sideration to be given to the automation of certain portions of the photo interpreta-
tion task. While there is little present likelihood of successfully designing
machines to interpret aerial photographs in a complete sense, there is ample
evidence to support the conjecture that simple objects, and even some complex
objects, in aerial photographs might be isolated arid classified automatically.
25X1
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25X1
Approved For Release 2005/05/02: CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
Even if machinery, produced in the near future, can only perform a preliminary
sorting to rapidly winnow the input volume and to reduce human boredom and
fatigue on simple recognition tasks, the development of such machinery may
well be justified.
The supporting evidence for the conjecture that simple objects can be
identified in aerial photographs is based on work which has shown experimentally
that present pattern-recognition machinery - indeed that which existed several
years ago - can be applied to the recognition of silhouetted, stylized objects
which are militarily interesting. Murray has reported just such a capability
for a simple linear discriminator'. Since the information required to design
more capable recognition machines is readily available, it might seem that
there is no problem of real interest remaining to make a rudimentary photo-
interpretation machine an accomplished fact. This, unfortunately, is not so.
One of the most difficult problems is that which is referred to as the segmentation
problem. The problem of pattern segmentation appears in almost all interesting
pattern recognition problems, and is simply stated as the problem of determi-
ning where the pattern of interest begins and ends (as in speech recognition
problems) or how one defines those precise regions or areas in a photo which
constitute the patterns of interest. The problem exists whenever there is more
than one simple object in the entire field of consideration of the pattern recognizer.
The situation appears almost hopeless when one finds patterns of widely varying
sizes, connected to one another (in fact or by shadow), enclosed within other
patterns, or having only vaguely defined outlines.
See "Perceptron.Applications in Photo Interpretation, " A. E. Murray, Photo-
grammetric Eovea nprin ezing
Appr r-oer rteleateSidagE: d/k-i4DP781304770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
This paper constitutes a report on a system which has been conceived to
solve some of these problems. It is being tested by general-purpose computer
implementation. The system discussed represents one of several possible
approaches to the problem and had its design focused towards the use of presently
known capabilities in pattern recognizers. No special consideration has been
given, at this time, to methods of implementing the device; however, the entire
system can be built in at least one way.
SYSTEM PRINCIPLES
Figure 1 is the basic block diagram for the system. It has evolved from
evaluation of possible approaches suggested by research conducted at
pattern recognition work of others, and techniques successfully used in other
problems.
As is evident from Figure 1, objects of interest have been categorized
in two different ways. First, simple objects, such as buildings, aircraft, ships,
and tanks have been distinguished from complexes, or complex objects. Second,
simple objects have been categorized, according to their length-to-width ratios,
as being either blobs (aircraft, storage tanks, buildings, runways) or ribbons
(roads, rivers, railroad tracks). As shown, the detection of simple objects is
accomplished separately for ribbons and for blobs. In the work reported here
the blob channel - from the input end through the identification of a few complex
objects - is receiving the major attention.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
BLOB ISOLATOR
AND
STANDARD! ZATI ON
BLOB OBJECT
ASSOCIATION
AND
I DENT! Fl CAT! ON
OBJECT
OUTPUT
COMPLEX
OBJ ECT 41--
01!TPUT
INPUT
BLOB
OBJ ECT
DETECTION
V V
V
COMPLEX OBJ ECT
ASSOC! ATI ON
AND IDENTIFICATION
A
A
A
PHOTO
( SCALED)
RI BBON
RI BBON OBJ ECT
RI BBON
OBJECT
DETECTI ON
-to
ASSOCIATION
AND
IDENTIFICATION
CONTINUITY
INTERPOLATOR
010
ON
Figure 1 PHOTO INTERPRETATION SYSTEM BLOCK DIAGRAM
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
The preprocessing which is carried out in the first portion of the system
solves several of the problems inherent in the use of a simple pattern-recognition
device to aid in the photo interpretation problem. Briefly, objects are to be
detected, isolated, and standardized so that they can be presented separately
(not necessarily sequentially) for identification.
The function performed at the object identification level is that of identifying
the blobs which have previously been detected, isolated, and standardized. The
input material to this level or state consists of black-on-white objects. As has
been previously indicated, existing devices are fundamentally capable of ac-
complishing the identification task.
At the complex object level, the location and identification information
available from the simple object-level outputs is combined and appropriately
weighted to identify objects at a higher level of complexity. An illustrative
example is the combination of aircraft (simple objects) near a runway (another
simple object) and a group of buildings (each a simple object) to determine the
existence of an airfield.
In the following sections the basic steps in the preprocessing sequence will
be described in more detail and some illustrations from current computer studies
will be discussed. The most difficult part of the problem, by far, is that of
detection.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25X1 Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
OBJECT DETECTION
A study of sample aerial photography suggests three ways in which images
of objects of interest differ from their backgrounds:
a.) points on objects may differ in intensity from the intensity characteri-
zing the background.
b.) objects may be (perhaps incompletely) outlined by sharp edges, even
though the interior of the image has the same characteristic intensity
as the background.
c.) objects may differ from background only in texture, or two dimensional
frequency, content.
Examples of the first two kinds of objects are shown encircled in Figure 2.
There seem to be many fewer examples of objects which differ from background
solely by texture. This class of objects would be much larger if our definition
of object were broader, including, for example, corn fields. Perhaps the most
useful area in which spatial frequency content can be put into use is that of terrain
classification. Terrain classification, as will be noted again later, can play a
significant role in the final identification of our narrower class of objects.
For detection of objects in classes a) and b) above, we have been proceeding
experimentally to determine the capabilities of simple, two-dimensional numerical
filters, some nonlinear and some linear.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Figure 2 EXAMPLES OF OBJECTS DEFINED BY INTENSITY CONTRAST (0)
AND BY EDGES (LI)
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
For initial experimentations', the object filters for discrimination based on
intensity contrast (class a objects) were designed as shown in Figure 3. Square
apertures ("picture frame" regions) were used to compute intensity information
which was then compared with the intensity of the point at the center of the square,
A, to determine if the central point differed sufficiently in intensity from its back-
ground to qualify as being a point on an object.
A computing method equivalent to the following was used. Each point in the
input photograph was surrounded by a frame one point thick, and of width d
(Figure 3). The mean, m , and standard deviation, cr- , of the intensity of the
points in the frame were then computed.
If
or
A m # max , Ker)
A .= m ? max (1 , Ka-)
(1)
the point was recorded as an object point. Several different frame sizes were
used in order to detect objects of different sizes.
>:c
The experimental work reported was carried out using IBM-704 computer
programs which were prepared to process photographic material. An input
device was constructed to scan and quantize photographic information for
input to the computer through the "real-time" package, and the computer
printer was used to provide pictorial output.
A commercially available facsimile transmitter capable of 50 lines/inch
resolution and a commercially available analog-digital samples and encoder
form the basic input device package. In addition, the necessary isolating and
synchronizing circuitry has been designed, and constructed to permit the
output of the facsimile machine (through the encoder) to be read by the "real-
time input package" on the 704 computer. Quantization and processing com-
puter programs have been written and are in operation. These programs
cause photographs to be sampled every 50th of an inch, quantized in sixteen
intensity levels, and stored on magnetic tape. A relatively crude, interim-
nature, output has been arranged by using combinations of symbols available
in the co rrifaPPrOvietliEW Releatn%2005g15/0Pe: ciArliQUeEE11477(14WOOMO2A-Aof four
different levels of intensity.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
A
.41
Figure 3 FILTER FOR DETECTION ON THE BASIS OF INTENSITY CONTRAST
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
'Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Figure 4 ORIGINAL PHOTOGRAPH
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
POciroved For Release 2005105102 .. CIA-R0978604770A00230004,_
?
?
?
el..
?
.: ?,? ....... ...i"::??
?:- ? ? : ?.:*
::ii? .
?
??*
???
? ??
e
. ?:. -
.. .
???
?? ?
..
?
?
?
"?ii:
..
o
.0-
?11?4
. . :
.....: - :.
Figure 5 FILTERED PHOTO, d = 8
???
??
?
..
s
?
..
---,wed For Release 2005105102 : CIA-RDP7g3047701002300030029-4
Approved For Release 2005/05/02: CIA-RDP78604770A002300030029-4
??
??
??.?
Li- ?
..
Figure 6 FILTERED PHOTO, d = 16
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
"
?:
"..." ?
"
"
. "" ... ?
?
?:::
:.: ::?"
???? ???? ?C
'::* :Iiii ** ? *::*
Figure 7 FILTERED PHOTO, d = 32
..... ..? +
? ::
? ? ?
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
Figures 5, 6, and 7 indicate the results of applying three filters of
the type described above to the photograph shown in Figure 4. The frame
widths were 8, 16, and 32 points, and K of equation (1) was 2. The points
which satisfied the inequalities of (1) were printed as asterisks.
The three figures illustrate that objects of different sizes are detected
best (with least shape distortion) by filters of different size. This is especially
noticeable for the building complex in the lower half of the photograph. In
Figure 6 (d=16), the buildings are reproduced in perfect contrast about as well
as can be expected considering the coarseness of the input information. In
Figure 5, the buildings are broken up into segments, while in Figure 7, they
tend to run together.
The seaplane launching ramp at left center is missing completely from
Figures 5 and 6, while the filter which matches it well in size reproduces it
in Figure 7.
It is important to note that the recognition logic used requires only that an
object be detected by a single filter. Distorted versions which are detected by
other filters will be rejected.
Simultaneously with experimentation in detecting objects using the object-
point-intensity criteria, similar experiments are being carried out to detect
objects by outlining them. There are three steps in this process; (1) object
edges must be "detected", (2) gaps in the outlines of objects must be filled in,
and (3) for compatibility with the first method of object detection in later system
stages processing all detected objects, the outlined objects must have their
interior space filled in to produce silhouettes.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25X1
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
The basic operation in edge detection is, of course, differentiation. The
earliest results were obtained by centering a numerical filter of the shape shown
in Figure 8 about each image point.
c
A
d
Figure 8 BASIC FILTER FOR EDGE DETECTION
The values of intensity, ( d-C )=AX and ( a-b )= uiy were determined
and the sum of their magnitudes was taken as the gradient associated with the
center point, A. A similar filter with nine elements is now being tested with
superior results. This filter has the form shown in Figure 9.
a
b
c
d
e
f
g
h
i
Figure 9 IMPROVED FILTER FOR EDGE DETECTION
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
Now the difference in the x direction is taken to be
AX
# 74' * /a #
k ,/
and the difference in the y direction as
4), ( a sh c A, 1)
(2)
(3)
Thus first differences are being used, as before, but a three-point average of
intensity is used to establish the intensity on either side of the central point.
The magnitude of the gradient associated with point e should, of course, be
Igraci I p-x.t. + y z
(4)
The previous approximation to the true form Mr:67(..g Ay' has been improved
over the simple sum of magnitudes in that we now use
Iyrca1(1 CRP- of I XI (3711an er IAXI Ay')
(5)
If object detection by identification of edges is to be successful, one must
plan on completely outlining objects of interest. In many cases, of course, there
will be gaps in the outlines of objects as derived by edge detection. One procedure
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
currently being evaluated for this gap-filling job is described below. It accounts
for the two factors which are most important in deciding whether to fill in a point
of not; that is, such an action requires both proximity in intensity to the threshold
value and proximity in space to at least one other super-threshold point.
After gradient computation, as described above, the complete image, made
up of points computed by Eq. (5), is thresholded, eliminating low gradient points.
The "influence matrix" shown below is then centered over every point in the
thresholded gradient image (i. e. it is centered over high gradient points),
II
12
13
14
15
16
17
18
19
Figure 10 "INFLUENCE" MATRIX FOR GAP-FILLING
and the numbers IP 1, I3' ---- are added to the values in the prethresholded
form of the gradient image. If any point covered by the influence matrix now
exceeds the previously used threshold, that point is "filled in" as a high gradient
or edge point.
It would, of course, be possible to train a recognition device to identify
outlines of simple objects, but a much simpler system will result if outlined
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
objects can be simply converted to solid objects similar to the silhouettes pro-
duced by the annular filter detectors. This can be accomplished very simply by
forming the logical complement of the thresholded, edge-detected, binary picture
and then operating on the complemented picture with the object isolator programs.
OBJECT ISOLATION
Originally computer routines which traced along the edges of silhouetted
objects were planned for use in object isolation. This technique for isolation,
however, does not solve the problem of how to extract the interior portion of the
traced-out object from the background in any neat fashion. A different technique,
devised by
simultaneously traces through the interior of objects
and records these elements in a frame for separate storage. At this stage, that
is, after isolation, all images of objects are stored in binary form, in separate
frames, and in their original size, orientation, and location within the frame.
OBJECT STANDARDIZATION
Standardization involves simply the translation of the binary image of the
object so that its center of gravity coincides with the center of the frame and
rotation of the image so that one of its principal axes of inertia is vertical.
Recently, the programs being used in feasibility studies have been modified so
as to provide scaling of all objects to the same maximum dimension.
OBJECT RECOGNITION
In the system being discussed, recognition of simple binary images, after
detection, isolation, and standardization, will be accomplished by a linear dis-
crimination device, i. e. by comparing the weighted sum of a set of property
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25X1 Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
values to a threshold. The weights used are determined by exhibiting a sequence
of patterns whose classification is known and adjusting the weights when classi-
fication is incorrect, according to prescribed algorithms, until all patterns in
the sequence are correctly classified. Thus, the device is "adaptive" and "learns.
The properties may be thresholded sums of intensity at randomly selected points
in the preprocessed image, or they may be more "objective" properties, that is
they may be measured values of such determinable features of the pattern or
image as maximum extent, area, or moments about principal axes. Certainly,
use will be made of the size, area, and moment information derived during the
standardization process.
The non-determinable properties mentioned earlier (thresholded sums of
intensity at randomly selected points in the image) have the appeal of being very
simple to derive and of being of demonstrated usefulness in classification problems..
The ability of a system using such properties to generalize over pattern distortion
and small translations has not yet been defin.ed to our satisfaction. A recognition
system using these non-determinable properties has been referred to by Rosenblatt
as a simple perceptron. In our experimental work to date on this particular problem
we have attacked the multiple class recognition problem by performing a set of
dichotomizations. Some data on recognition capability have been gathered for
synthesized patterns of the type to be produced by the preprocessor, but they
are insufficient to make an explicit statement of capability at any reasonable
confidence level.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Figure 11 ORIGINAL PHOTOGRAPH
Figure 12 PROCESSED PHOTOGRAPH AFTER OBJECT
DETECTION AND LOW-PASS FILTERING
1111111'
Figure 13 ISOLATED SILHOUETTES FROM Figure 14 STANDARDIZED FORM OF ISOLATED
PROCESSED PHOTOGRAPH SILHOUETTES
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25X1
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
Two types of information are fairly readily available in the system and have
apparent use in classification but have not yet been used. Thus, we could use
the silhouetted image of an object to mask out all but that object in the original
full gray scale image and then derive one or more object properties available
in the original image. (For example, one might scan the interior of an object,
to derive some measure of its interior complexity). This technique makes
available recognition properties other than those based on shape. The second
possibility is to use terrain classification information for the immediate back-
ground of an object to aid in the classification of that object. Certainly a final
system might find such information useful.
ILLUSTRATIVE RESULTS
The entire sequence of preprocessing operations (including detection by
intensity contrast, but not object detection using edges) is illustrated in Figures
11-14. These results were derived from experiments which use general-purpose
digital computer programs to implement the entire sequence of operations. The
first, Figure 11, shows the original aerial photo. It has been quantized spatially
25X1 and fed into
IBM-704 computer through the facsimile input device. After
processing by the intensity contrast filter, the binary photo of Figure 12 is pro-
duced. (The output is the 704 printer; an asterisk is printed in each 1/50" x 1/50"
cell of the original photo which is a point on an object.) We found that some
additional low pass filtering is very useful in making objects "hang" together, in
filling in imperfections in silhouettes, and in reducing the number of small col-
lections of points which appear but which are really not objects. After this
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25X1 Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
filtering (a simple, low-pass, two-dimensional filter is used) and after eliminating
collections of very few points, the binary photo was subjected to the isolation
programs. This operation produced the frames shown in Figure 13. Each of
these several frames from the silhouetted photo was then subjected to the rotation
and translation. programs and the corresponding frames of Figure 14 produced.
Now recall that standardization processing (1) fixes the center of gravity
of a blob within the frame, (2) rotates it to align a major axis of inertia with the
vertical in the frame, and (3) adjusts scale factor to roughly fill the frame. All
information about how much translation, rotation, and scale change has of course
been preserved for use in the recognition process (size is an input to simple
target recognition, while location and orientation are inputs to target-complex
recognition). Examining Figure 14 we find one odd looking building-shaped blob
which must be explained. Referring back to Figure 13 we can locate the s'ource
of this standardized object, a small collection of points. Mentally treating each
of these points as a square, rotating and enlarging the resulting shape shows that
the standardization routine functioned properly. Scale change information would
prevent recognition as a building.
CONCLUSIONS
In this paper approaches to the preprocessing portions of a photo interpretation
automaton have been discussed. Clearly, some extremely important evaluative
work remains:
1. Detection capability must be quantitatively defined. This first requires
that some plausible criterion or criteria for this capability be defined.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
? ? ?
25X1 Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Design of a Photo Interpretation Automation
2. Recognition capability must be quantitatively defined. Here there
exists a body of evidence that recognition of silhouetted objects is
within the recognition capability of current state-of-the-art systems.
We are currently applying measures similar to probability of detection
and false alarm rate to the definition of recognition capability for a
property-list, linear discriminator type of system.
3. Implementation problems for a prototype system must be solved. Our
IBM-704 work is for feasibility only. We have kept implementation
problems in mind during the current system studies and have carefully
avoided using system elements which are unduly complex. As an
example, more complicated two-dimensional filters for object detection
represent a very real temptation, yet we have exercised restraint
and used only the simplest ones which we felt held any hope.
What has been achieved is a demonstration that a plausible system, combining
current state-of-the-art pattern recognition capability and simple two-dimensional
preprocessing operations, can be stated in specific terms and that it represents
the very real and likely prospect of providing automated aid to photo interpreters.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Illustrations to Accompany Presentation On
INVESTIGATION OF PERCEPTRDN APPLICABILITY
TO
PHOTO-INTERPRETATION
(Project PICS
Washington, D. C.
December 20, 1962
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
2005/05/02 : CIA-RDP78604770 V2300O
Approved For RTIrLTree2905/8EV itTieapalipg770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Figure 2 EDITED VERSION OF FIGURE I
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
App oved For elea e 2 5/0 02 :
APERTURE SIZE
(a)
DP7 B04770A 0230 030 29-4
APERTURE SIZE
( b)
ApprobjliFer1Reletkilitil2005/05AMR: 604PRIDMI3C14/117(AA092090030229-4
1672
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
1673
Figure 1.1. OUTPUT OF GAP FILLER APPLIED TO FIGURE 3(a)
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
?
I
1.1.,?????
1
(
1
P
gyp
;4e
Figure 5 OUTPUT OF ISOLATOR APPLIED TO FIGURE
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
I
14
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
i,
,
,
,
,
, 4
,
,
,,.
4.?.1
t
4 t
Figure 6 OUTPUT OF STANDARDI ZER APPLIED TO FIGURE 5
Approved For Release 2005/05/02 : CIA-RDP78B04770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For &ftr3td2g05A)E5Y02N ACU4'-01/1101ABIB14770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Figure 8 EDITED VERSION OF FIGURE 7
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
APERTURE SIZE
(a)
APERTURE S I ZE
( b)
Figure 9 ANNULAR FILTER OUTPUT FOR TWO APERTURE SIZES
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Figure 10(a) OUTPUT OF KOLMOGROV-SMIRNOV FILTER APPLIED TO FIGURE 8
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
3
1679
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Figure 10( b) OUTPUT OF KOLMOGROV-SMI RNOV FILTER APPLIED TO FIGURE 8
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
1680
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
*or
?
if
1
Figure (0(c) OUTPUT OF KOLMOGROV-SMI RNOV FILTER APPLIED TO FIGURE 8
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
.111. 11... ?
1681
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
t
, rLI?
istF
4
1
7 :
T.1
?????????,.-
,
t 1
*
I ?
;
,
,
171
*kr
,
11H
i
dr" I I 11
????????14* TM
,r
....??????????????? ?????1*.??????? ? ? ?
Figure I I SAMPLE OF OBJECTS USED IN RECOGNITION EXPERIMENTS
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
1682
Approved For Release 2005/05/02: CIA-RDP78604770A002300030029-4
RESULTS OF RECOGNITION EXPERIMENT
Synthesized Objects
Correct Pattern
Classification
Total
Number
Number Correctly
Classified
Number Incorrectly
Classified
Recognition
TU 104
60
60
o
100.0
IL 18
60
60
o
100.0
LA 60
60
60
o
100.0
F 102
60
60
o
100.0
SHIPS
60
59
1
98.3
BLDOS
90
86
4
95.5
TANKS
60
59
1
98.3
Object Total
450
444
6
. 90.7
Other
270
262
8
97.0
Object Detection Probability m. .987
False Alarm Probability m .030
COMPLETE RECOGNITION RESULTS
8
H
E
T A
0
Recognized
N
H
fri
As
tcg
pl .
E-4
0
Correcti
Classification
TU 104
bo
IL 18
60
LA 60
6o
F 102
60
SHIPS
59
1
BEGGS
86
4
TANKS
59
1
OTHER
2
6
262
1
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25 June 1962
PAPER PERCEPTRON
Notions of random connection generalization and learning have
dominated discussions of the perceptron to the point of obscuring its basic
principles of operation. Basically, the concept is simple; the mathematics
describing its operation oftentimes appears complex and obscures the basic
simplicity of the central ideas.
The purpose of this discussion is to explain the perceptron concept
by showing how it works. A simple paper model (attached as a series of
six pages to this discussion) is used as a means of demonstrating its
classification function and illustrating the training process.
The perceptron can be divided into three basic sections - sensory,
discriminatory, and response. Figure 1 shows a diagram of a simple
perceptron. The sensors (or S-units) respond to stimuli from the machine's
environment by producing a unit voltage or not, depending on the level of
stimulus. The sensors, arrayed in an orderly pattern, are connected in a
semi-random fashion to the discriminating layer (or A-units). Several
sensor leads are connected to each A-unit in such a way as to produce a
sum of stimuli from sets of sensor points. The model attached is a simplified
paper representation of perceptrons which respond to light. Naturally, a
perceptron of such small size cannot be expected to perform sophisticated tasks
but two letter discrimination within a limited field is a suitable task for
demonstration purposes.
In the model, S-A unit connections are represented by the clear
squares in each of the ten separate A-unit masks (page two of the model).
Every opening indicates a connection between that A-unit and a sensor point
occupying that position in the sensor group.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
PAPER PERCEPTRON 25 June 1962
-2-
The A-units serve to totalize the voltage input from all the sensors
connected to them and present this sum to a thresholding device. Page one
of the model shows the stimuli the machine is trained to classify. Properly
trained, it should be able to recognize the difference between all "P's" and
all "E's". Each letter is displayed in four positions to demonstrate the
flexibility of the perceptron and its ability to cope with letters which do not
maintain a single position. To see how the A-unit operates, we put the
stimuli page under the A-unit page (page two of the model) so that the number
of the stimulus appears in both the top and bottom pilot windows of the A-unit.
Since the dots on the letters represent S-units stimulated, and the holes in
the A-unit diagram represent S-A connections, it is apparent that a count of
the dots visible through the squares represents the total voltage the A-unit
receives. This total has been computed for each unit and stimulus, and the
result has been entered in the upper matrix on page three of the model. Thus
the matrix contains the sums of the input voltages at each A-unit, before
thresholding, when the various stimuli are shown to the sensors.
The summation voltages are then thresholded to produce a "unit"
voltage if the threshold is exceeded, a "zero" voltage in all other cases. In
the model, 6 = 31 was selected for the threshold. The lower matrix on
sheet two of the model shows the output of each thresholding unit for each
stimulus, In this matrix, each stimulus has its own unique binary number
made up of the thresholded A-unit outputs taken in order. This suggests that
there could be a way of training the perceptron to recognize the difference
between the letters. It is apparent that the larger the number of S-units and
A-units, the more patterns could be assigned a unique binary number and
thus the greater the scope of the perceptron. Indeed, larger perceptrons
have capabilities far beyond those indicated in this simple model,
We train the perceptron to recognize the letters by adjusting "weights"
or voltage multipliers which connect the A-units to the response unit. When-
ever the thresholder of any A-unit puts out a voltage, this voltage is
multiplied by a weight which may give a positive or negative product, depending
on its value. The response unit merely totals all the A-unit voltages and
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
PAPER PERCEPTRON 25 June 1962
thresholds the sum. If the A-unit sum plus the threshold (10 units in the
model) is equal to or greater than zero, the response unit puts out a positive
unit of voltage. Negative sums elicit negative unit voltage outputs
and "zero" sums, of course, give no output.
The machine is trained to distinguish between two letters, by adjust-
ing the weights so that the response unit gives plus values for all letters of
one type and minus values for all letters of the other type. Pages four and five
of the model are a representation of this training process. Page four is a
mask of the thresholded A-unit responses for each stimulus made from the
information in the second matrix of sheet three, Each clear part in both
the left and right hand columns of each stimulus mask indicates the A-unit
which produced a plus "one" output. By placing the mask on page four of the
model so that the stimulus number on the training cycle page appears in the
pilot hole of the proper mask, the weight associated with each A-unit can be
seen opposite the A-unit numbers. By totaling the weights and adding the
threshold just as a physical machine would, the sum ( Z ) which the response
unit receives is obtained. If the sum is of the wrong sign, the weights involved
must be changed. It has been shown that it is best to change the weights so
the sum is as great in the proper direction as it was in the wrong direction,
This change ( d ) is divided among the N weights involved and each is changed
by . These new values are recorded in the second column of the mask and
the new sum is listed opposite 2c, . Starting with the weights all at zero,
the machine is exposed to P1 as the first stimulus in the training sequence to
which it responds correctly. Using the stimulus E1 and the same weights, the
machine misclassifies and must be corrected by adjusting the weights using
the procedure just described until a correct reading is obtained. As the sheet
shows, the machine was exposed to all the stimuli in an orderly fashion until
the perceptron correctly identified all the stimuli, On page five of the model,
only the stimuli incorrectly classified during the training cycle are shown for
the sake of brevity. The final column (labelled Wi) contains the final weights
Page six shows that the perceptron now correctly classifies the eight stimuli.
Now the tasks used for this demonstration are quite elementary.
Extensions to more sophisticated tasks would demand a much larger perceptron,
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
PAPER PERCEPTRON 25 June 1962
-4
which would become unmanageable for paper computation. Thus, this
exercise can only be thought of as an exposition of principles of operation,
LTLH-1/rmm
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
SENSORS
1
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
1ST LAYER
DISCRIMINATION
T THRESHOLD
?CCT
2
?
DISCRIMINATION
WEIGHTS
0, I )
5
6
7
?
?
9
e9
10
?
THRESHOLD
CCT
(0,1)
THRESHOLD
CCT
THRESHOLD
CCT
(0,I)
wi
W3
W5
W9
Figure I PATTERN RECOGNITION CONCEPTS
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
RESPONSE
THRESHOLD
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
INPUT STIMULI
P3
? ? ? ?
?
?
? ? ? ?
?
E1
0 0 0 ?
E1
P2
? ? ? ?
? ?
? ? ? ?
?
?
P2
? ? 0 ?
? ? ?
E2
?
? ?
?
?
?
?
? ?
?
?
?
6
?
? ? ?
?
6
?
is
?
p.
? ?
E3
?
?
?
?
?
? ?
?
?
ELI
?
?
? 0 ? ?
PAGE ONE
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
DI SCRIM! NATI ON UNI TS
A10
PAGE TWO
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
"A" UNIT
NUMBER
MATRI CES
SUMMATION MATRIX
STIMULUS IDENTIFICATION
PI P2 P3 P4 El E2 E3 E4
1 2 5 3 1 3 4 3 2
2 2 I 3 3 4 2 2 2
3 3 3 4 3 2 2 4 3
4 2 3 3 2 3 4 3 2
5 4 It 2 2 It 5 1 1
6 3 5 4 2 It It 3 2
7 5 5 4 3 3 5 14 It
8 4 It I 4 3 4 3 5
9314 It 3 2 14 2 3
10 3 It 3 2 2 2 It I
THRESHOLDED VECTOR MATRIX
2
3
"A" UNIT
NUMBER It
5
8
9
10
STIMULUS IDENTIFICATION
Pi P2 P3 P4 El E2 E3 E14
0 I 0 0 0 1 0 0
0 0 0 0 I 0 0 0
0 0 1 0 0 0 I 0
0 0 0 0 0 1 0 0
11001100
01101100
11100111
1 1 0 1 0 I 0 1
01100100
0 1 0 0 0 0 I 0
0= 31-
PAGE THREE
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
STIMULUS AND
WEIGHTS AFFECTED :
"A" UNIT
NUMBER
THRESHOLD:
TOTAL CHANGE :
ACTIVITY VECTOR MASK
PI(N , 3) P2(N = 7)
1111
2
3
4
5
6
7
8
9
10
'I
CHANGE PER UNIT: E
CORRECTED SUM : Ec
STIMULUS AND
WEIGHTS AFFECTED :
1111 El(N =3)
2lU
3
6 ii
, 5
"A" UNIT 7
NUMBER
8
9
10
E3(N = 3
THRESHOLD :
SUM:
TOTAL CHANGE : 6
CHANGE PER UNIT: 6
CORRECTED SUM :
PAGE FOUR
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 200T5i8t1d216CMZ5078B04770A002300030029-4
P-1.10 E.?
STIMULUS IDENTIFICATION
P2
E3
E4
P1P2
E2
P3
E3
E4
PI
E1
o
o
I
I
I
1
I
-I
-I
-I
-I
-I
2
0
0
-7
-7
-7
-7
-7
-7
-7
-7
-7
-7
-7
3
0
o
o
o
-6
-8
-8
-8
-8
-2
-3
-3
-3
4
o
o
o
o
o
o
o
o
-2
-2
-2
-2
-2
5
0
o
-7
-6
-6
-6
i
I
-1
-1
-1
-1
7
6
0
o
-7
-6
-6
-6
-6
-6
-8
-2
-2
-2
-2.
"A" UNIT
NUMBER
7
o
0
o
I
-7
-1 1
-4
-3
-5
1
o
-12
-4
8
0
0
o
I
i
-3
4
4
2
2
2
-10
-2
9
0
o
o
I
I
I
I
i
-i
5
5
5
5
10
0
o
o
I
-7
-7
-7
-7
-7
-7
-8
-8
-8
10
10
10
10
10
10
10
10
10
10
10
10
10
10
10
-4
12
4
-10
0
8
-12
2
12
-13
-20
-7
8
1
-24
-8
-8
-4
20
7
1
( 1 )
-16
-2
24
6
-4
-1
-24
-12
26
8 J
10
-11
3
-12
-4
II
1
-6
12
-1
-12
11
Ei
P2
E2
P3
PI
P2
E2
P3
P2
E3
E4
P2
1
-e
-I
o
-2
-2
-2
-2
1
-2
-2
-1
-1
-1
-1
2
-7
-12
-12
-12
-12
-12
-12
-12
-12
-12
-12
-12
-12
-12
3
-3
-3
-3
-3
-2
-2
-2
-2
-2
-2
-2
-3
-3
-3
4
-2
-2
-2
-4
-4
-4
-4
-4
-7
-7
-7
-7
-7
-7
5
7
2
3
1
1
1
2
5
2
2
3
3
3
4
6
-2
-7
-6
-8
-7
-7
-7
-4
-7
-6
-5
-5
-5
-4
7
-4
-4
-3
-5
-4
-7
-6
-3
-6
-6
-5
-5
-6
-6
-2
-2
-1
-3
-3
-6
-5
-2
-5
-5
-4
-4
-5
-5
5
5
8
4
5
6
5
8
5
5
6
6
6
6
10
-8
-8
-7
-7
-7
-7
-7
-4
-4
-4
-3
-3
-3
-3
10
10
10
10
10
10
10
10
10
10
10
10
10
10
8
-5
7
-2
3
-2
-10
1 1
0
-6
o
I
-I
4
-16
10
-14
4
-6
It
20
-22
1
12
-1
-2
2
-5
1
-2
1
-3
1
3
-3
( I )
1
(-1)
-I
(1)
Sc
-7
2
-7
2
-3
I
II
-10
I
I
-I
-I
1
PAGE FIVE
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
TRAINED PERCEPTRON RESPONSES
P E
STIMULUS IDENTIFICATION
P3 EI
I -1 _1 _1 _1 -I -1 -i
2 -12 -12 -12 -12 -12 -12 -12 -12
3 -3 -3 -3 -3 -3 -3 -3 -3
4 -7 -7 -7 -7 -7 -7 -7 -7
5 4 4 4 4 4 4 4 4
6 -4 '4 -11. -34 -4 -4 -4 4
"A" UNIT
NUMBER 7 -6 -6 -6 -6 -6 -6 -6 -6
8 -5 -5 -5 -5 -6 -5 -5 -5
9 6 6 6 6 6 6 6 6
10 -3 -3 -3 -3 -3 -3 -3 -a
r 10 10 10 10 10 10 10 10
E 3 1 3 6 -2 -3 -2 -I
PAGE SIX
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
(r,i/La
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
INPUT/OUTPUT EQUIPMENT FOR RESEARCH APPLICATIONS
Reprinted from "Proceedings of the NEC"
1962
Vol. 18 pp. 509-517
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
25X1
Approved For Release 2005/05/02 : CIA-RDP781304770A002300030029-4
CPYRGH
INPUT/OUTPUT EQUIPMENT FOR RESEARCH APPLICATIONS
By: W. S. Holmes and H. M. Maynard
Cornell Aeronautical Laboratory, Inc.
ABSTRACT
The purpose of this paper is to review the
input/output requirements for computers used in
research activities, to establish a cohesive phi-
losophy encompassing foreseeable requirements,
and to illustrate that philosophy with case his-
tories of equipment designed and constructed at
Cornell Aeronautical Laboratory for its own
research purposes. Research problems arising
in the areas of photointerpretation, pattern rec-
ognition, speech analysis and radar signal analy-
sis are described with examples of specific solu-
tions of these problems in terms of input/output
equipment. This paper, in addition, demonstrates
that access to a special input/output system will
permit for the solving of research problems, a
radically different approach which is not ordinar-
ily evident at the outset of an investigation.
INTRODUCTION
Over the past decade, computers have pene-
trated and served almost every facet of scientific
research including research on information proc-
essing systems themselves. Accompanying this
penetration has been an intensified requirement
for input-output systems satisfying special needs
not met by standard available equipment. In the
very recent past, movements towards satisfying
these requirements are in evidence, but the over-
all pattern has not been completely established.
The purpose of this paper is to review the
input-output requirements for computers used in
research activities, to establish a cohesive phi-
losophy encompassing foreseeable requirements,
and to illustrate that philosophy with case his-
tories of equipment designed and constructed at
Cornell Aeronautical Laboratory for its own re-
search purposes. In the course of the discussion,
we will describe research problems areas impos-
ing special requirements and to present specific
approaches to the solution of these problems in
terms of input-output equipment. In many cases,
we have found that access to a special input-
output system permitted a radically different
approach to a research problem and opened re-
search vistas not clearly appreciated before the
revised approach was taken.
In retrospect, it is possible to observe major
trends in the use of computers which have im-
posed progressively more exacting requirements
on input-output facilities for general-purpose
digital computers. These trends are roughly
delineated by Table I. At the outset, computers
were used chiefly in scientific computation.
Characteristically, this imposed minimal demands
on input-output equipment in terms of the quantity
of data to be inserted into the machine. Card and
punched tape inputs were entirely adequate and
printer/plotter output largely satisfied display
requirements.
Use of computers in information systems
such as SAGE, MISSILE MASTER, and NTDS
imposed new requirements and raised two issues
which significantly affected attitudes toward
509
Table I
EVOLUTION OF COMPUTER USE AND INPUT/OUTPUT
REQUIREMENTS
APPLICATION
I/O CHARACTERISTICS
SCIENTIFIC COMPUTATION
INFORMATION PROCESSING SYSTEMS
LIMITED I/O DATA
STEREOTYPED DATA
OFTEN NIGH VOLUME DATA
OFTEN REAL-TIME I/O
INFORMATION PROCESSING RESEARCH
(I) BY SIMULATION
(ARTIFICIAL INPUTS)
(2) BY IMPLEMENTATION
(REAL INPUTS)
(3) BY REAL-TIME EXPERIMENTS
LIMITED I/O DATA
INCREASING AMOUNTS OF I/O DATA
UNUSUAL INPUTS SUCH AS PHOTOS,
SPEECH, ETC. ENCOUNTERED
EXTENSIVE DATA TRANSFER
I/O COORDINATION WITH
COMPUTATION AS WELL AS
EXTERNAL SYSTEMS
PRINCIPLE PROBLEM
MASS DATA REDUCTION
EXTENSIVE INPUT DATA
BUFFER STORAGE REQUIREMENT
input-output systems: (1) the use of computers in
a real-time environment, (2) the need for mas-
sive, sophisticated information processing re-
search to make the system work at all. Issues of
noisy inputs and nonlinear processes forced much
of this research into the general purpose com-
puter. The input-output needs for computers
used in information systems, however, tended to
be stereotyped, special-purpose, and therefore
not of interest in a discussion of research re-
quirements.
At first, research on information systems
problems was confined to analytic studies and
simulation of the problem using artificially gen-
erated inputs. More recently, pattern recogni-
tion research as well as some signal processing
research have entailed problems for which arti-
ficial inputs cannot be readily generated. Thus,
special-purpose input systems for pictorial and
other forms of information have become needed.
Consequently, we see information processing re-
search imposing demands on computer input
systems which cannot be met with conventional
card or perforated tape inputs.
At the same time that research on informa-
tion systems became important, scientists deal-
ing with experimental research problems began
to seek in computers, a way out of the cumber-
some, time-consuming, and costly data reduction
problems which their experimental procedures
were imposing upon them. Requirements for the
processing of large masses of data then prolifer-
ated, and solutions to input-output problems im-
posed by this movement have become imperative.
Generally, the data to be transferred into the
computer are time-varying functions in several
parameters and, by and large, some sort of a
buffer store is required between the experiment
and the computer.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
Since some of the most interesting input-out-
put problems imposed by today's research activi-
ties are entailed in the last two of the areas cited,
information processing research and mass data
reduction, we will concentrate on these areas as
a means to focus this paper.
INFORMATION PROCESSING RESEARCH
The two major areas of information process-
ing research which currently impose the most
significant input-output requirements are shown
in Table II. It is clear from the research topics
Table
INFORMATION PROCESSING RESEARCH
PATTERN RECOGNITION
SHIM PROCESSINO
ALINA-NumERIC CHANACTER RECOGNITION
NANO PRINTED ClikRACTEII RECOGNITION
IIANOBRITTEN CHARACTER RECOGNITION
TWIERAIIINT IDENTIFICATION
m tAv INTERARETATIoN
SPEECH RECOGNITION
tECOONIIION Of BUIIMAIIINE BOUNDS
DECOY OESCRImINATION
AUTO-DOES SOUNDS RESEARCH
COMMUNICATIONS COOING
SPEECH OANOMIOTHCONPRESSION
MOTO BANDWIDTH COMPRESSION
ELECTROCARDIOGRAM INTEMPRETAIION
ELECTROENCEPRALOORAN
INTENPMETATION
DATA AnCESSIND
INTERTEROGIIAMfiNALTSIS
PARTICLE SIEIND AND COUNTING
CELL COuNTIBO
OLTENIA COMITINO
AEROSOL iiimEsTIORTION
GEOLOOICAL muCRO-AS,ANINO
delineated in.these figures that the salient feature
of each problem which imposes an unusual input-
output requirement stems from the fact that the
Input to the system under study cannot be readily
characterized analytically. Research in other
areas such as radar track-while-scan research
could readily proceed through the mechanism of
artifically generated inputs. Confidence in the
validity of these artificial inputs, while not per-
fect, is high enough to justify use of the research
results for most design purposes. On the other
hand, characterizing either an aerial photograph
or the essentials of the spoken word analytically
is virtually impossible except for early explora-
tion studies. Thus, research in these areas uti-
lizing general-purpose computers is dependent
upon input-output equipment suitable for the task.
Further contemplation of the research prob-
lems demanding special input equipment convinces
one that a pictorial input system capable of ac-
cepting monotone, opaque or transparency,
material and transferring to store, four to five bit
quantizations of the gray scale level for a spatial
square matrix of l0 to 107 elements would
satisfy a very large percentage of the problems
involving two-dimensional patterns.
Figure 1 shows the major blocks of a Photo
Input System designed and put in operation at the
Laboratory for use on its research programs.*
The facsimile transmitter is a standard commer-
cial unit designed to accept flat copy 8-3/8" wide.
The scanning rate is 6 lines per second, corre-
sponding to a feed rate of 3.6 inches per minute.
The system is synchronized by incorporating a
pulse generator into the facsimile transmitter.
This consists of an inductive pickup associated
with a 180-tooth gear driven by the mechanical
scanning system at five times the line scanning
speed. The resultant "clock" frequency is thus
*This development was sponsored jointly by Geog-
raphy Branch, Office of Naval Research and Photo-
graphic Management Division, Bureau of Naval
Weapons.
510
5.4 Kc with 900 pulses per line locked to the
scan motion. The clock frequency after shaping
is used as a trigger to control the conversion time
of the analog-to-digital converter. The converter
receives a continuous analog signal from the fac-
simile scanner by way of the photomultiplier,
cathode follower and gamma correction amplifier.
(The latter restores the compression introduced
in photographic reproduction processes.) At each
trigger pulse, the instantaneous analog signal is
converted to a four-bit binary number in 22 micro-
seconds and appears on the four output lines of
the converter. The converter also furnishes an
end-of-conversion pulse 0.5 microsecond after
conversion. This pulse is used after shaping, to
control the "read" time of the computer via the
"MG" line.
The circuitry shown in the block diagram as
the input buffer section accepts the digital infor-
mation from the analog-to-digital converter on
the four lines and modifies the levels correspond-
ing to "0" or "1" to make them compatible with
the computer. The gate associated with each
level changer is under control of the "read select"
line from the computer. The gate is either open,
permitting information transfer, or closed,
clamping the cathode follower to "0" level. The
"read select" line also controls the copy feed
motion via the cathode follower and relay in the
control section.
The photo input system is controlled com-
pletely by the digital computer as if it were a
standard item of peripheral equipment, such as a
tape reader. A computer program developed by
the Laboratory makes use of copy content to con-
trol registration of copy area. A black bar, four
Inches long by one-fourthinch wide, is placed at
the top of the copy 0.4 inch above the desired
first line of the area to be .read. The bar may be
printed as part of the photograph or may be ap-
plied as a strip of black tape. To perform a
reading operation then, the facsimile transmitter
Is energized, starting the scanning system. The
prepared copy is inserted until engaged by the
pinch roller using the roller hand wheel. The
computer program is read into the computer in the
normal manner. When the program step selects
the real-time input, the read select line is ener-
gized, opening the gates in the input buffer and
starting the copy feed motor. The computer pro-
gram starts a search routine looking at the digital
Information presented to the I/O bus. This pro-
gram step continues until the black bar is inter-
cepted. The next step allows the copy to advance
0.4 inch, then initiates a second search routine
to locate the pedestal (black level interval at end
of each scan line). Location of the pedestal starts
a counting routine that counts the number of MQ
pulses received as the scan line advances from
left to right. Upon reaching the desired magnitude
(100 counts per inch), the computer transfers the
digital number presented to the I/O bus into core
storage. Each sample thereafter is transferred
until a total MQ count of 900 is reached. Counting
continues until the desired magnitude is again
reached on the next scan line (without digital num-
ber transfer). Establishment of the count again
starts the digital number transfer to core storage
and the cycle is repeated until a predetermined
total number of MQ pulses has been reached,
terminating the read-in program.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
PULSE
GENERATOR
MECHANICAL
SCANNER
OPTICS
PHOTO-
MULTIPLIER
CATHODE
FOLLOWER
COPY
FEED
MOTOR
CONTROL
SCHMITT
TRIGGER
FACSIMILE
TO
L.
RELAY
CON TOOL
CAT ODE
FOLLOWER
BLOCKING
OSCILLATOR
BLOCKING
OSCILLATOR
CATHODE
FOLLOWER
GAMMA
CONVERSION
TRIGGER
PULSE
--a.
AN
TO
DIGITAL
CONVERTER
END
CONVERSION
PULSE
CORRECTION
Figure I
ANALOG SIGNAL
READ SELECT LINE
INPUT BUF ER
20
LEVEL
CHANGER
GATE
LEVEL
CHANGER
1
CA 111 ODE 1_4_
FOLLOWER
21
GATE
LEVEL
CHANGER
CATHODE
FOLLOWER
22
GATE 1.4-?
LEVEL
CATHODE
FOLLOWER
23
CHANGER H
CATHODE
FOLLOWER
1?i?
OATE 1"4-40
_I PULSE h
IMPL I F I ER
IBI4
704
COMPUTER
REAL-TIME
INPUT
I/O BUS
"M Q" LINE
BLOCK DIAGRAM OF PHOTO INPUT SYSTEM
Thus it may be seen that the recorded area of
copy is controlled vertically by the location of the
black bar and the total magnitude of the MQ count.
Horizontal location is controlled by the MQ count
along the scan line. In the actual program, a
packing routine is used to conserve core storage
by consolidating nine four-bit samples into one
standard thirty-six bit computer word. Flexibility
of this control method should be apparent.
Figure 2 shows the physical arrangement of
the major components. The gamma correction
amplifier appears at the top of the rack. Directly
below is located the modified facsimile trans-
mitter. Below the transmitter is the control and
input buffer circuitry, while the analog-to-digital
converter and associated power supply are located
at the bottom of the rack. Primary power for the
control and input buffer chassis is supplied from
the 704 computer. Figure 3 shows the details of
the pulse generator.
Access to a photo input system enables a re-
search worker to investigate two-dimensional
filtering, processing, and decision making methods
without costly breadboarding of proposed systems.
Photographic inputs are inserted with full usable
gray scale for numerical processing. Figure 4
shows an aerial photograph of which the left half
was read into the computer, and printed out in
four levels of gray scale using different letter
symbols for each gray level. Figure 5 shows a
numerical printout of alpha-numeric pictorial
material which was read into the computer by the
511
photo input system and printed out using each of
the ten numerals and four letters of the alphabet
to represent each of the available 16 levels of
gray.
The nature of processing research which is
accommodated by such a photo input system illus-
trated by Figure 6 which shows an original photo-
graph (6a) and three different types of numerical
operations performed on the photo after read-in
to the computer. From the full gray scale record,
two-dimensional filters were used to produce the
binary image (6b). Although it is not immediately
apparent from the illustration, one of the two
filters was a sophisticated variable, dual thres-
hold filter. The other was a simple low pass
filter. The objects in the (6b) binary image were
then isolated one from the other to make the
separate binary images (6c). A scissors pro-
gram was used to produce this result. Finally
each image was normalized by measuring c.g.'s,
angle between horizontal and major axis of
inertia, rotating each image through that angle,
and re-sizing the images to a common vertical
dimension.
These examples afford only a glimpse of the
research potentialities of such an input system.
Naturally a matching photo output system is a
useful adjunct to the photo input system described.
Speech recognition and bandwidth compression
constitute the remaining major area of research
for which special purpose inputs may be of value.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
Figure 2 EXTERNAL VIEW - PHOTO INPUT SYSTEM
Figure 4 ILLUSTRATION OF DIGITALLY STORED
PHOTOGRAPHIC INFORMATION
512
Figure 3 DETAIL OF PULSE GENERATOR
ggngUgggilgOggTgOggaggOgggOnggrg2ggggnOgggg:gegggilgOggnOgOgg:MgOgg2=PMTov
000m000m00000man00000noonnonoom000poom000noomoononoacoormooem00000m000no. m 301
0.0000000000000000000000000.00000000000000000NOPOPM10.0000000.000000000013000.0000004v.vuou001
.000000.000.000.000000000000000000.00000000000.00006040.000000000000000000.00000000000000000t
gONINIINNNNNUNNUMMMIIIINPINSNNBHNBNUNMINNNMINNgUNOU
o1379999u999e ',leo .000000000000001,.....911762.30.000000000000.4.999011807,152M000000001100(
M4VAMUNngMagggr22221Vg2n4nEWUMNSMUNSINNINWHUNUUNgnNN
One 1162111 11100D000000000000000.001978510.00000000000000000.0.0001.740011000000000000.100000000(
01.102100000000000000000.00000001S,851000000000000000.000(100.0000?741000000000000000000000000(
013711511000000P00000000000000000000197711000.0000M01)00000000000000/75.00000000000001100000000(
0137.1100010000000000000000000000002675.0004000000000000n00000000001277,1000000000000000000000000(
aRMINggN22,3gg=2=4NNgging=====nNgNaMINSI8ggggf
0121,7032210000000000000.0000000012579210000000000000000.000000000026.2000000000000000000000000(
012.0100000000000000000000000n0000147510000000000000.006000.000000161.200000000.00000000000000(
0025,62000000000000000000000000000002570200000000000000000000000000000137.1000000000.000000000000.
002.61000.000000.0000.00000.0025.621000000000000006000000000000010.2000000000.000000000000K
00147010000.00000000000000000000.01.76200000000000000000000000000000157620.0000000000000000000000C
Mai.142M12g=gg=2:41::!!??2=gggg2g=gg=g3g11.1:;:2:MMIN:g2:24:2:?
001255922221111000000000.00000000001367.33333210000000000000000000001311977,171.0200000000000000t
20
11:::::2
:::02
I00
0
0
0
0
00
0
1
00
0
0
0
018=2::1
:24
2
2
20
0
80
0
00
00
0
00
00
0
0000
11011122
tg2
2
0
a02
2
gg0
=
001314.33M2100000000000000000000000011110000000.00.000000000000000000000000000000000000000000.
NggIgg41:42TATMT4NOMgggggggggSaggg8g2gggVnggggggggNg&ININITAIgggggS=1
ggNg4MINgg2g2N23g=ggnN=IgNgSgM:gggg;g:4MgggggNgNogg2gN222220.
Figure 5 NUMERICAL PRINT-OUT OF PHOTOGRAPHIC DATA
pp(ovecl I 01 tiii. -
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
T
Figure 6a ORIGINAL PHOTOGRAPH
ISOLATED SI LHOUETTES FROM PROCESSES PHOTOGRAPH
1689
1688
Figure 6b PROCESSED PHOTOGRAPH AFTER OBJECT
DETECTION AND LOW-PASS FILTERING
STANDARI ZED FON OF I ROUTED SI LHOUETTES
1690
Figure 6c ISOLATED SILHOUETTES FROM PROCESSED Flgure 6d STANDARDIZED FORM OF ISOLATED
SILHOUETTES
PHOTOGRAPH
513
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
Actually the approach one uses for this type of re-
search is as much a matter of preference and
background as necessity of or even advantage.
Laboratories staffed with experimentally oriented
personnel, well versed in filter and active circuit
design, may not observe any advantage in the
flexibility afforded by gener-t; purpose computers.
Nevertheless, we cannot ignore the fact that very
flexible filter programs for general purpose
machines can be prepared and almost any experi-
mental operation which can be performed on a
speech record could be as readily performed
within a general purpose computer.
An input system for speech research purposes
could be limited in performance to cover only the
frequency bands known to be needed for recogni-
tion of spoken words by humans, but to so limit
the system might undesirably inhibit research.
Thus the system described here, in use at the
Cornell Aeronautical Laboratory, covers a
sampling rate up to 27000/ second and employs
much of the same circuitry developed for the
photo input system. In regard to Figure 7 one can
see that the input buffer section is similar except
that the full eleven bit capacity of the A/D con-
verter is used, thus affording 1/2% least count
for the system. The control unit accomplishes the
same functions as in the photo input system with
added circuitry to provide one additional control
line to the computer in the form of an end of record
signal. Both of these features enhance the flexi-
bility of the system by allowing complete control
CLOCK
PULSE
END OF
NEC.
ANALOG
TAPE TRANSPORT
OR
DIRECT DATA
CONTROL
SCHMITT
TRI GGER
BLOCK IMO
ASCII LATOR
CATHODE
FOLLOWER
BLOCK ING
OSC ILL A TOR
BLOCK IRO
OSCILLATOR
CATHODE
FOLLOWER
-J
CONVERSION
TRIGGER
PULSE
by computer program. For example, the com-
puter program can specify the number of bits de-
sired in a particular application to match the accu-
racy of the analog data presented. The end of
record pulse serves the function of segmenting
the data in convenient blocks for subsequent mani-
pulation within the computer.
Performance of this system is intimately
related to the processing program desired for the
data reduction. The converter has a conversion
rate of 44,000 samples/second, but when applied
to an IBM 704 computer using fixed program
logic and no word packing, a resulting read-in
rate of 27,777 samples/second is obtained. Adding
dynamic program logic reduces the input rate to
16,667 samples/second. As a consequence of
finite core storage and inadequate time for trans-
fer to tape during a run, lengths of coherent
records are limited unless word packing is em-
ployed. Packing the 11-bit information in the
36-bit word length in order to extend run length
further reduces the input data rate to approxi-
mately 6,000 samples/second.
One of the first applications of this equipment
was in connection with the investigation of radar
video. Here the objective was to improve experi-
mental measurements by long term integration.
The video signal was recorded on a suitable mag-
netic recorder together with a trigger pulse and
range marker pulses on separate tracks. The
ANALOG
TO
DIGITAL
CON VERTER
ANALOG
SIGNAL
END CONVERSION
PULSE
END OF RECORD LINE
INPUT BUFFER
LEVEL
CHANGER
20
GATE H
CATHODE
FOLLOWER
r TE V EL- -1
L CHAN GERd---"i ECA HOD
T2^
1201.10WERJ
GATE
L
21 I
LEVEL
CATHODE
CHANGER
FOLLOWER
GATE
IBM
7014
COMPUTER
REAL-TIME
INPU I
) I/O BUS
---b.
HA
PULSE
PLIFIER
"M Q" LINE
Figure 7 BLOCK DIAGRAM OF GENERAL PURPOSE ANALOG INPUT
514
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
signal then was played back at reduced speed and
fed to the input of the general purpose input sys-
tem. The trigger pulse served as the end of file
input while the range marker pulses served as
clock pulses.
From the specifications on the system, it is
clearly compatible with speech recognition and
bandwidth compression requirements.
Thus, we see the outlines of approaches to
the solutions to broad areas of information proc-
essing research. This equipment has been found
not only to facilitate the special research for
which it was designed, automatic photointerpreta-
don, and radar information studies, but also to
have a broader application to research problems
of the two generic classes listed at the outset.
MASS DATA REDUCTION
Wind tunnels have provided one of the earliest
forces toward mass data reduction by digital com-
puters. Digital recording systems have been em-
ployed in the Cornell Aeronautical Laboratory's
variable density tunnel since its inception in the
1942-45 era. A large number of parameters are
measured very accurately; equations governing
data reduction are complex; and timely results
for examination in the course of a sequence of
runs is of great economic advantage. Although on
the surface these factors might suggest an on-line
operation with direct electrical connection of the
sensors into the computer, the Cornell Aeronauti-
cal Laboratory found the use of punched card
buffer store to be satisfactory and more economi-
cal. The notion of having experiments funneling
data into the real-time bus of a computer for
processing and display of instant results at the
experimental site has a certain appeal to the show-
man in us, but can rarely be justified. Most
input-output systems for mass data reduction will
incorporate some form of buffer storage.
Choice of buffer stores is part of the input-
output design problem. Experience with strip
chart recorders - the principal buffer store during
the past two decades - predicts that computer
input systems will be required to provide compati-
ble buffer stores over a frequency spectrum of at
least 0 to 5000 cycles per channel, with channel
capacities ranging from two to ten.
Experience at the Cornell Aeronautical Labo-
ratory with research problems ranging from air-
craft control problems to measurement of three-
dimensional radar cross-section profiles, has
demonstrated a clear, high-volume research re-
quirement for a digital buffer store to handle an
information rate of up to ZOO bits per second. The
basic system, using punched perforated tape, is
sufficiently flexible to permit selection of the
number of channels and dynamic range to be em-
ployed. Clearly, given a basic information rate,
trade-off among (1) numbers of channels, (Z)
maximum frequency to be recorded, and (3) dyna-
mic range required, are governed by the relation
hi ?
P- T i P j loge L?
where = information rate in bits per second
n = number of channels
maximum frequency of jth channel
in cycles per second
maximum level of jth channel
required least count of jth channel
L1 =
This relation presumes, of course, a substan-
tially noise-free system. Naturally one is faced
with a compromise in deciding how much flexi-
bility to provide in order to take maximum advan-
tage of this relationship over a broad range of
possible experimental requirements. We would
not want to suggest that the system to be de-
scribed (ANDIT) is an optimum compromise; in
fact, second generation models have tended
toward less flexibility.
ANDIT equipment (Figure 8) affords a buffer
store with an information rate capability of
approximately 200 bits per second. This com-
pares with direct galvanometer recorders (14
bits/second per channel) and electronically-
driven galvanometer recorders (700 bits/second
per channel). Experience with strip chart
recorders would suggest that two additional
buffer stores capabilities, one with information
rates in the region of 1,000 bits/second per
channel, and the other with rates around 50,000
bits/second per channel would have utility for
experimental research investigations. Naturally
if one can accommodate both rates in a single
economical system, that approach would be
superior.
Figure 8 DIGITAL RECORDING EQUIPMENT
515
Arrrtwari Frtr Palaaca 9ringing/(19 ? rha_pno7ARnA77nAnn9lnrinlrin9cLA
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
The ANDIT equipment characterizes an ap-
proach to buffer storage in which analog to digital
conversion occurs prior to making the permanent
record. This feature exhibits the advantage that
channel multiplexing and therefore flexible em-
ployment of the available information rate is
facilitated, but has the disadvantage for higher
information rates that it places a more expensive
piece of equipment at each experiment, thus
raising the cost of mass data reduction to each
experiment.
Another approach, that of using analog buffer
stores, is characterized for precision records by
magnetic tape instrumentation recorders. This
approach has been explored commercially and
instruments are available covering information
rates up to approximately 200,000 bits/second
per channel. These systems are more expensive
than the strip charts which they would replace,
but the added capital investment is more than off-
set by the elimination of costly manual conversion.
When analog buffer stores are used, it is neces-
sary to accompany those stores with a suitable
analog-to-digital conversiqn facility at the general
purpose computer. An example of such a system
roughly compatible with requirements for analog
buffer stores has already been discussed in con-
nection with speech research interests. Clearly
flexible record-playback speeds are desirable to
match the conversion system effectively.
The issue of allowable record length impinges
on both the buffer store and on design of analog-
to-digital converter systems feeding directly into
a main frame. Characteristically, as the infor-
mation rate increases for a buffer store, the
allowable coherent record length decreases. In
the course of conversion, analog-to-digital, for
injection into the computer, a similar limitation
is encountered. Whenever the information rate is
sufficiently great that transfer to tape is not
possible in the course of data breaks, the core
storage of the computer eventually is exceeded
and conversion must be discontinued until transfer
to tape can be effected. Naturally, this operation
produces data discontinuities unless techniques
are employed to ensure coherence from one
record to the next. So far, the Laboratory has
not in its research encountered this problem to
the extent that special techniques needed to be
created.
Analog-to-digital converter systems for use
in mass data reduction do not constitute an un-
usually sophisticated design problem. Converters
with speeds acceptable for this service are avail-
able and can usually be adapted for coupling to the
real-time input bus of a general purpose machine.
The system described under speech recognition
input systems is characteristic of such a device.
High speed printers and x-y plotters are
obviously still effective output systems for re-
search purposes. In this discussion, we are
interested only in new approaches to display of
data which may afford solutions to some of the
more recent research problems being undertaken,
and will not touch on advances in printer speed or
plotter facility per Be.
For example, this Laboratory has constructed
for its research purposes an output system which
516
permits plotting the time-varying results of
computer reduced data on a high-speed photo-
graphic-trace oscillograph, and this kind of a
facility is characteristic of the special-purpose
output systems we are interested in discussing
in this paper.
At present, we have partially completed the
design of a photographic output system for use
in conjunction with the photographic input system
already described. Such a capability is important
if one is attempting to design two-dimensional
spatial filters. Thus, the research worker is
able to assess easily the results of a filtering
operation on a given piece of input material.
We expect, however, that this output system
may have broader application than to studies in
automatic photointerpretation and pattern recog-
nition. For example, it affords the interesting
Opportunity to read-out computed curve plots in
conjunction with a graphical format which was
read into the machine through the photographic
input. Thus, for example, a research worker
could insert a log-log or polar or other graphical
record format into the machine, complete with
titles, ordinates, and perhaps even the symbols
to be used by plotting each of several curves, and
having stored this format on tape, and generated
the curve points with a computational program,
read-out the composite result of both these
processes through the photo output system. He is
thus able to produce a complete graphical picture
of the desired results. Such a picture would be
entirely suitable for reproduction in reports or
slides, and thus would facilitate a more economic
reporting process. The potential for presenting
numerical information in three dimensions, X,
Y and density, should find increased application
to report and documentation efforts. Imaginative
employment of this technique of compositing
graphical data derived from philosophically dif-
ferent sources may very well lead to some
unusual research techniques, unforeseen at
present.
CONCLUSIONS
Evidence points to a well-established require-
ment for pictorial input-output systems for mod-
ern research in pattern recognition, signal proc-
essing, and data reduction. Means for entering
computers with time-varying data up to 20 kc for
speech recognition and related research is an
additional requirement. Such a system may at
the same time serve the purposes for mass reduc-
tion of data gathered by analog buffer stores in
the 1,000 bit/second and above classes. Perfo-
rated-paper-tape buffer-store input systems
afford an economical input medium responsive
to experimental needs which formerly were
handled by ink-pen trace strip charts. This same
perforated tape format can, if designed for suffi-
cient flexibility, invade an area of recording
formerly handled by electronically driven galva-
nometer recorders. The principal merit of the
perforated tape system is low cost equipment at
the experiment site, ease of editing data before
entry to the computer, and a reasonable degree
of facility for injection of the data into the general
purpose computer. Moves toward higher and
higher perforated paper tape recording speeds
may entirely satisfy the needs currently being
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CID'YRG-kT
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
handled by electronically driven galvanometer
strip charts. However, systems (possibly analog
instrumentation recorders) making available
information rates in excess of 60, 000 bits/second
per channel will be required for specialized
experiments unless analog-to-digital conversion
coupled with digital buffer stores of sufficient
information rates can compete economically. If
the latter becomes feasible, compatible format
magnetic tape records would be a desirable
feature.
Photo Input/Output systems offer a potential
for information compositing (curve-on-chart) as
yet unexplored.
ACKNOWLEDGEMENTS
The authors wish to acknowledge the contri-
butions made to this paper by the work of col-
leagues which provided input-output examples.
Cognitive Systems Section personnel, notably
Dr. H. R. Leland, Head, Mr. G. E. Richmond and
Mr. C. W. Swonger, recognized the need for the
photo input-output system herein described and
furnished empetus for its design and construction.
The high speed analog-to-digital input system was
constructed to meet specifications established by
Mr. R.F Schneeberger. The ANDIT equipment
was conceived, designed and first put in opera-
tion by Mr. H. F. Meese for Terrain Avoidance
research. Mr. C. L. Syverson and Mr. T. J.
McDade have extended the use of perforated tape
recorders in the design of special purpose systems
for our Radar Cross-Section Ranges. The infor-
mation compositing notion was suggested and
implemented by Mr. M. B. Cohen who is respon-
sible for operation of the Laboratory's IBM 704
computer services. We also wish to acknowledge
the encouragement and interest of Mr. W. M.
Kaushagen, Head of the Laboratory's Electronics
Division, and of Dr. M. G. Spooner, Assistant
Head of its Computer Research Department, in
encouraging the development of input-output
facilities for research purposes.
517
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
PP
r Roloaco 2005/05/02 ? CIA RDP78B01770A002300030029 1
TWO-DIMENSIONAL SPATIAL FILTERING AND COMPUTERS
W. D. Fryer and G. E. Richmond
Cornell Aeronautical Laboratory, Inc.
Buffalo, New York
ABSTRACT
CPYIGH
Processing of two-dimensional signals has important applications, for example,
in photographic image analysis, but when the weighting function of a two-dimensional
linear filter extends over a large area, e. g., smoothing filters, digital realization
via a two-dimensional convolution is prohibitively time consuming, and analog reali-
zation is extremely difficult. The principal purpose of this paper is to show how a
broad and useful class of two-dimensional filtering operations can have notably
shortened execution time in the digital case, and be put into a particularly convenient
form for electrical filtering. The procedure includes a reduction of dimension from
two to one; transformation of two-sided (weighting function extends into both past and
future) operations into one-sided (physically realizable) operations; and finally, for
the digital case, the transformation of a direct many-term convolution expression into
a compact recursive form ideally suited for digital computation. An important class
of smoothing filters, with weighting functions approximately Gaussian, is derived and
used for illustration. The result is a several-order-of-magnitude reduction in time
for digital two-dimensional filters, and some interesting results applicable to one-
dimensional zero-phase-shift filters.
1. INTRODUCTION
Analog or digital processing of two-dimen-
sional signals has many important applications,
notably in photographic image analysis for mili-
tary or commercial purposes. Much of this type
of isiocessing is special purpose, tailored to the
physically significant details within an image.
But there are certain basic operations (e.g. high
and low-pass filtering) that are extensions of
..or responding one-dimensional operations, and
which have a similar range of usefulness.
Because in two-dimensional processing by
digital means, or by means of electrical filters,
storage and processing time requirements are
much greater than for one dimension, there is
a genuine need for nontrivial methods to allevi-
ate time and storage problems. This need is
greatest when each computed point in the output
image is affected by values from a relatively
large area of the original or input image. Such
'An exception is the optical filter, not
conside7.-ed in this paper.
filters, called area filters, are exemplified by
many smoothing operations; they form the
principal topic of this paper. In contrast to the
area filter is the local filter, in which the va
of an output image point depends only upon a
small neighborhood of the corresponding input
image point.
II. THE DIRECT CONVOLUTION APPROACH
The direct approach to realization of an
arbitrary filter operating on a two-dimensional
input is explicit convolution of the impulse re-
sponse of the filter with the input. In the digital
case this takes the form:
ym,n L
-
where subscripts on y (output) and
(1)
y (input)
give the digitized coordinates of the image point,
and h?? is the discrete two-dimensional impulse
response or weighting function.
In the case of a local filter the number of
terms in this expression is small, and the method
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02
: CIA-RDP78604770A002300030029-4
CPYRGH
is practical and often useful. For example,
Kovasznay and Joseph (Ref. 1) describe an inter-
esting analog equivalent to (1) used for outline
enhancement. David (Ref. 2) reports a digital
application of linear and nonlinear local opera-
tions for noise reduction.
In the case of an area filter, the large
number of terms (121, for example, if / =J=5
required for each output point makes this approach
impractical.
III. THE SIMPLIFICATION STEPS
Equation (1) of the direct method is the
starting point for a number of drastic simplifica-
tions. The goal is a set of one-dimensional
filters, of simple recursive form for digital com-
putation, and of physically realizable form for
analog use. The simplification steps are:
(a) Restriction of the weighting function
or h ( , ft ) to a product form
9, or 1'0, ) 9 ( t, ) ; this special
form allows the two-dimensional prob-
lem to be decomposed into two one-
dimensional problems.
(b) Transformation of the one-dimension
filtering operation, which has an impulse
response extending into both positive and
negative time values, with two filtering
operations of the "physically realizable"
form, in which output depends upon the
"past" (impulse response vanishes for
negative argument).
(c) In the digital case, conversion of the
one-dimensional filter into a recursive
form so that only very few terms appear
In the computation of an output value,
even though the effective memory
extends far into the past.
These items are discussed in the following
four sections.
IV. REDUCTION OF DIMENSIONALITY
The first major simplification of (1) is the
reduction in dimensionality from two to one, by
restricting (with some loss of generality) the
weighting function of two variables to be of
product form
h41= '9, (discrete) or
h (e? e2) - ) 9 )
(continuous)
Then the complete double summation of (1) may be
replaced by two sets of calculations, each only
having a single sum; omitting details, and again
writing only the digital equations, we have:
r
Yrn,n
Here, is an intermediate result, com-
puted from the 8, then regarded as input
variable for final computation of the desired
values. The first computation (2) is (for any
fixed r ) an ordinary one-dimensional filter,
operating on one horizontal!' line of the image;
the parameter r identifies which line. Similarly,
the second computation (3) is, for any fixed fr7 ,
an ordinary one-dimensional filter, operating on
a vertical line2 of the y image; the parameter
rn identifies which vertical line.
(2)
(3)
To illustrate the general effect in terms of
saving computing time, suppose that a 100 x 100
grid of picture intensity values is to be filtered,
and assume that the weighting function of (1)
extends 10 terms in each of the possible directions
( / = J 10 ). With edge effects ignored, the
application of (1) directly would require
21 x 21 = 441 operations (an operation consisting
of a multiplication and addition) for each proces-
sed point, for a total number of 4, 410,000 oper-
ations. The corresponding double application of
one-dimensional filters, according to (2) and (3),
would require 21 + 21 = 42 operations per proces-
sed point, for a total number of 420,000 operations
-- less than 1/10 as many.
zWe arbitrarily identify horizontal lines with
fixed second subscript, varying first subscript,
and vertical lines with contrary conditions, in
analogy with the continuous form tz)
where the first variable normally gives the
abscissa value and the second gives the ordinate
value.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
CPYRGH
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
V. SIMPLIFICATION OF THE
ONE-DIMENSIONAL FILTERS
The following approach towards simplifying
the one-dimensional filters of (2) and (3) gives
results definitely useful in originally one-dimen-
sional filtering problems, as well as in the pres-
ent context as intermediate aids for two-dimen-
sional filtering.
It is convenient to drop the redundant double
subscript, and begin with the generic form (open-
loop, double-sided) form that is implied by (2),
(3) and the preceding discussion:
"in 2 hk Xn-A
y I '1.4(ri x(/- r)ir
(discrete)
(continuous),
(4)
and it is convenient to regard a subscript as a
time value (e.g., y? is the value of y at the
quantized time value n ).
Equation (4) could be used in its existing
form for digital computation. But for the case
where the number of terms is large, there is a
more efficient method most conveniently derived
by orienting our terminology towards the continu-
ous-time situation, so that we can simultaneously
develop a method suited to electrical filtering and
of a form that can be converted to an efficient re-
cursive digital filter.
Write h (r)- h_(r) , where 17,
vanishes for negative time, and h_ vanishes for
positive time. The h?. part could be the im-
pulse response of a realizable filter, assumed to
have rational transfer function 6 (s) with
its poles in the left half plane. The h_ part may
be achieved with a realizable filter by reversing
the time variable, for example, by storing the
input on magnetic tape, then playing the tape
backwards. A reversed-time signal passed
through a realizable filter with transfer function
gives a result that is formally equi-
valent (in the sense of a bilateral Laplace trans-
form) to passing the original forward-time signal
through a filter with transfer function f;(-f ) .
Thus we may speak of filters with poles in the
right half plane, with the understanding that they
refer to a physically realizable filter driven by a
time-reversed version of an input signal.
3
Thus, if the original picture is processed
with filter having transfer function f; (5)
then the original picture is filtered independently
with filter having transfer function F, (- 5 )
(actually accomplished by running the input signal
backwards through a filter with transfer function
F,() ), and the results are added, the result-
ant impulse response will be desired 17, h_
and the total effective transfer function will be
The rational functions f; (j) and 1", )
may be combined into a single multiplicative
expression, of the form
where G, contains all of the poles in the left half
plane and G, contains all of the poles in the
right half plane. Thus, we have a cascade form:
rather than filter the original picture twice and
add results, as in the previous paragraph, one
could filter the original picture with 4, , then
filter that result with G? . In the digital case,
the latter has the advantage of eliminating the
need for duplicate storage space, by means
which, if not obvious, are simple. For analog
filtering the' cascade form is more convenient and
avoids various practical synchronization diffi-
culties.
VI. DIGITAL ONE-SIDED RECURSION FILTERS
An open-loop one-sided digital filter has the
form
Yn hoXn # '41 Yn--, h2xn-2 '" ? ? ?
the expression possibly being infinite in extent.
"Open-loop" refers to the fact that y is expres-
sed only in terms of 's (inputs); "one-sided"
refers to the fact that only present (time n ) and
past values of input are used to determine output.
For example, the one-aided open-loop digital
filter corresponding to an exponential impulse
response (simple RC lag filter) is
Y0 a2,0-2 ? ? . (5)
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
Approved For Release 2005/05/02:
CIA-RDP78604770A002300030029-4
CPYRGH
If, as in this example, the number of terms is
infinite, then digital computation can be perform-
ed only by approximating with a finite number of
terms. But if ce in the expression above is
fairly close to unity, (e.g., 0.99 ), it is possible
that several hundreds of terms would be required
for satisfactory approximation.
A one-sided feedback digital filter equivalent
to (5) has the form
Xn
(6)
where cc is the same one as in (5). This form
is of course particularly suited to digital compu-
tation, since it contains only two terms. "Feed-
back filter" here refers to the fact that output
depends explicitly on prior output, as well as the
y input; this type of filter is also commonly
called a recursive (or recursion) filter.
VII. RECURSION FORMULAS FROM
TRANSFER FUNCTIONS
The general problem of converting a transfer
function (such as our (3) , if additive form
is used, or c, (3) if cascade form is used)
into a digital recursion relationship is easily
solved by means of a method presented at the
1961 NEC (Ref. 3, 4), which is described here
only in necessarily very sketchy form. In the
expression for a transfer function , make
the substitution 2 1/- , clear of extra-
neous 142
fractional forms and normalize numerator
and denominator into the following form:
ao a,i ,4-4.,Z27, ? ? ? i? afrnZm
I 1611 bz Zz ? ? ? .kbrz"
(7)
( Z can be interpreted as the delay operator,
with Laplace transform
6,- sr ).
Then the recursion formula becomes
Yn )111 - I. ? ? ? 17
- ra-r " "hr yn-r ?
The quantity T is a time scaling parameter; in
this application, it relates the time variable of
(8)
4
the Laplace transform to the separation between
adjacent sample values.
To illustrate, we use a transfer function that
will later be used to illustrate another aspect of
the two-dimensional filtering problem;
2
# 35
The impulse response has time constants of the
order of one second in real time. Suppose we
desire that over one of these time constants there
would be 10 picture elements (in a rough sense,
the memory covers ten picture elements, if
memory is taken to be a nominal time constant).
Then T = 0.1. Use of the substitution described
above gives for the final recursion formula:
4100849 (in ZYn-/ #)n-j) # 1.95/y/74? 0.97(96yn_1
VIII. ILLUSTRATIVE EXAMPLE
In many two-dimensional filtering applica-
tions, it is desired to have an impulse response
that is circularly symmetrical. The purpose of
this section is to show how one class of such
impulse responses can be approximately realized
with the multiple application of one-dimensional
filters as described above.
Circular symmetry requires that the filter
impulse response h be a function of
Thus the one-dimensional filter g(t) which is to
be applied in each direction must be chosen such
that
h (t?tz)=
ksezth 9(4.z ) F (t;) =y (t; ) .
A solution of this functional equation is
(9)
(10)
In accordance with the previously prescribed
procedure, we now attempt to find a one-sided,
one-dimensional filter whose impulse response is
f(t) = e-ez > 0
0 t the equation is termed Nth order.
One will then require at least N storage locations in a
digital computer, or at least N delay lines in a recircu-
lating delay-line digital system. It is important to note
that for N> 0 the g(k) sequence will usually not ter-
minate.
The system smoothed-velocity output sequence ?
can be given by
4 = E g(k)x,_k
where
Mk) =the input position to output velocity
weighting sequence or unit-impulse re-
sponse.
(3a)
(3b)
A difference equation for the velocity output could also
be written. One can also combine the difference equa-
tions for position and velocity into a set of difference
equations. For example, the common [2 "a-0" or
"g-h" (g =a and h=0) equations become
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
r.PYRnH
28
ApprovphIEFFAMOg/202Aplib?,114F17BEIgnw300030029-4
= xo,?
ce(OC,, ? Xpn)
(4a)
X.. = 74-1
--(x
? xpn)
(4b)
7'
= +
(4c)
where
T =sampling period and
predicted position at n+1 time index.
The set (4) is second order, as can be seen by writing
them in terms of only one output variable.
Z transform 13] one can characterize a sampled-
data tracker by a multiplicative operation
Y(Z) = G(Z)X(Z) (5)
and
(Z) G(Z)X(Z) (6)
where Z = ei'T is a forward time shift and the trans-
forms for signals are given, for example, by
,v(z) = E (7)
n. 0
kiid for the system, for example, by
6,(Z) E g(n)Z'.
The inversion is given, for example, by
gr(n) =
1
ci(z)zn triZ.
27ri r
(8)
(9)
The indicated contour of integration, F, is the unit-
radius circle in the Z plane.
Ill. PERFORMANCE MEASURES
n. order to assess properly the two attributes of noise
reduction and transient performance, two measures are
introduced; in every case their effects will be considered
si inultaneously.
For noise smoothing, the performance measures will
be, for constant input variance, the variance reduction
ratios
steady-state variance in position output
variance in raw position input
si eadv-state variance in velocity output
K?(0) ? - -
variance in raw position input
The notation K.(0) and Ki(0) is used to coincide with
the definitions of .K.-,r(n) and K(n) the input-normalized
autocorrelat ion sequences of the position and velocity
outputs. K?(0) and K(0) are calculated (for uncor-
related scan-to-scan input noise) from the corresponding
unit-impulse responses g(n) and g(n) by the formulas'
See Appendix I.
K(0) = E g2(n)
July
(10a)
Ki(0) = E g.i2(n). (1(11))
For transient (maneuver-following) performance, the
demerit figures will be [referring to (1)1
and
= E [(unit-increment ramp) ? (position ramp response)] 2
n=0
E [n ? gx(j)(n ? j)
n=0 j=0
12
= E [(velocity of unit-increment ramp)
(velocity ramp response)] 2
n
E ? E Mj)(n ? .
n=0 j=0
Ramp-type test inputs of component position are se-
lected because they are realistic for radar TWS opera-
tion on airplanes (sudden heading changes) and are also
realistic for any sampled-data tracking start-up tran-
sients.
Meanwhile, consider the evaluation of arbitrary
tracking systems on these performance bases. See Fig.
I. Here arbitrary tracking systems are compared. One
seeks to design a system which is "close" to the origin.
However, for Tracker A, as parameter p is increased
so as to decrease Di', .K?(0) increases. Tracker B is
clearly better than Tracker A in Region I; Tracker A
is clearly superior in Region II. The optimum tracker
by definition has a single-parameter locus where the
(12)
TUCKER El
r 3p,
TRACKER A
TPACKER C
NOISE - SMOOTHING DEMERI F. K,(0)
Fig. 1 ?Arbitrary system position performance.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
1962 Benedict and Bordner: Radar Track-While-Scan Smoothing Equations
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
ray from the origin is shortest everywhere. Such a
tracker is illustrated by Tracker C on Fig. 1.
The equations derived in the next section will be
optimal for position and velocity tracking simultane-
ously.
Some concrete examples are now given.
Example 1:
For the a-13 tracker as listed in Section I, if one calcu-
lates the impulse response and thence the performance
measures, he obtains Table I. Some parameter pairs
(a, (3) will be poor compromises. The pairs (a, a2/2 ?a)
were shown analytically to form the optimal locus for
the (a, 0) tracker in position and velocity. This analysis
is performed by 1) assuming K(0) a constant, then
dK = 0; 2) the value of a (or (3) that minimizes D cor-
responding to the constant value of K is found by
equating dD/da to zero; and 3) solving dK =0 and
dD/da=0 for 13 in terms of a. These loci are plotted
on Fig. 2a and 2b.
TABLE I
PERFORMANCE MEASURES FOR THE a-0 TRACKER
Position Output
Velocity Output
Variance
Reduction
Ratio
Transient
Performance
2a2+13(2-3a)
1 202
a [4-0-2a]
(2?a)(1?a)2
T2 a [4? 2a-0]
1 a2(2 ? a) +213(1 ? a)
D2=
?
(X0 [4 2a]
T2 00 [4? 2a ? /3]
Example 2:
A first-order (one pole, two zeros) tracker is given by
xn+i = C( an CiXn C2X7,--1 CSX,,-2. (13)
For the conditions
co + ci c2 c3 = 1 (unit dc gain)
C2 = 3 ? 2c0 ? 2c3 (zero steady-state ramp-following error)
one has the measures
13? 15c0+ 4632? 2c1(8 ? 7co+ co2) 2c12(3 ?co)
K(0)= (14)
1+co
(2 ? ci)2
.W=1+
1 ? co2
(15)
These measures are plotted parametrically on Fig. 3.
This tracker shows up everywhere worse than the opti-
mal (Li = a2/2 ?a) a?(3 tracker.2
2 This judgment will be lessened in magnitude, but not reversed,
if the first-order tracker used present input and present output.
Noise demerit T2K-(0)
(a)
Noise demerit K.(0)
(b)
Fig. 2?(a) Tracker velocity performance.
(b) Tracker position performance.
1.35.1.111171/10 PERFORNAIIER
OF FIRST- ORDER TRACKER
Variance Reduction Ratio K.(0)
Fig. 3?First-order tracker position performance.
Approved For Release 2005/05/02 : CIA-RDP78604770A002300030029-4
2
CPYRGI
fiTy
fi) IRE TRANSACTIONS ON
Approved For Release 2005/05/02
I V. SYNTHESES BY CALCULUS OF VARIATIONS
Suppose now that one wishes to find the optimal set
of tracking equations. That is, it is desired to select
perfectly freely the impulse responses Mn) and g(n)
so as to minimize D,,2 for a given IC(0) and vice versa,
and so as to minimize /3?2 for a given tri-(0) and vice
versa.
Taking the velocity case for an example, one wishes
to minimize
= Ki(0) ADth2 (16)
where X is the Lagrangian multiplier (and the final
single parameter).
Letting r(n) be the optimal unit-increment ramp re-
sponse, one has the double-difference identit
gi(n)= r(n + 1) ? 2r(n) r(n 1). (17)
Then
3
= E [ I r(n + 1) ? 2r(n) r(n
AUTOMATIC cosTnw
: CIA-RDP78B04770A00200030029-4
Note that (22) holds only for n>0 since the fact that
h(n) =0, n