# Full text of "mit :: ai :: aim :: AIM-101"

## See other formats

```jipmll^

■r*\

\

MASSACHUSETTS INSTITUTE Of
PftOJKT MAC

Artificial Intelligence Project

1, 1966

r-\

JSmSSSmmmSti

Richard Greenblatt and Jac Holloway

Described by Donald A« Sordillo

SIDES 21 produce© a graph conaistiag of the locations of lines vhich
comprise the a idea of either a geomet ric solid ** » plane figuire* Hie
representation la in floating point «od** Sit**ai&l -#ie subsequent processing.
The input is a picture intensity-function.

r^

Introduction

Let us define a table as a black area, delimited by a white border.
Consider a white opaque object (in this instance a cube) resting on the
table. The whole of the table is considered to be in the f ield-of-view
of the vidisector. Sides 21 will "find" the cube, in that a representa-
tion of the location of each of the edges visible to the vidisector will
be stored in the computer.

The following terms will be used only as defined below:
Edge A physical entity: that part of a cube formed by the meeting
of two and only two sides.

Vertex That part of a cube formed by the intersection of two or

more edges. To the program, the number of edges at a vertex
is dependent upon the angle at which the cube is placed with
respect to the vidisector. [It is assumed that this angle
is kept constant during the execution of the program.]

Line That area demarcated by successive positions of the acceptance
box (q.v.). This has no physical existence and thus differs
from an edge. A line will have a representation which is a
function of the program's past history in looking at an edge.

-2-

Box

A plane figure comprised of three rectangles with ratios

as indicated in Figure 1.

h

1

h

Figure 1.

The innermost rectangle is termed the acceptance box ; the

outer two rectangles are collectively termed the looking

box . The dimension indicated by i is the major axis,

When tracking, the noisier (i.e. less sharply defined) the

edge is, the wider the box must be to successfully track it.

The length and width of the box are functions of the current

length of the line and the iteration number of the box.

-3-

Operation
The program has, as initial conditions, the coordinates of a

starting point. For now, assume that this point is sufficiently near

the cube so that an edge will be within the area swept over.

The program forms boxes on the periphery of an imaginary circle

about the starting point by using the algorithm

Y._ X._

i i-1 K > i i-i K

The parameter, K, (whose current value is 5) determines the number of
boxes about a point. If necessary, slightly more than 360° will be
traversed before the program stops trying to find an edge.

The box tracks and searches by constructing perpendiculars to the

length of the box as in Figure 2. As the line extends across the width,

it searches for the maximum gradient. This is determined by taking

successive differences of the form: log V. - log V. , •

& l ° i-i

[Where V. and V. - are the inputs from the vidisector - integers between
and 256, which are inversely proportional to the intensity of the light

-4-

seen. The program uses only the logs of the V. f s for computation.]

Figure 2

For each sweep, the greatest difference observed is stored; and, at the
end of the sweep, this number is compared with a parameter (the current
value of which is equivalent to 3 vidisector units.) If the number is
less than this parameter, the program thinks that no gradient was found.
The program does not differentiate between this condition and one in
which the gradient was outside of the acceptance box. The relative loca-
tion of the maximum gradient with respect to the box is also known to
the program; and this information is subsequently used to steer the box.
The parameter is set low so that the box does not go berserk when servoe-
ing under noisy conditions. Yet, since the program decides which points
to accept and to reject, the function that tries to extend the line is
not affected by a point with no gradient (or one outside the box) for
these points are never even considered.

-5-

The "looking' 1 section steers the box as a function of where the
general trend of the maximum gradient appears to go. If the line is
within the acceptance box as well, the program considers that the correct
location of the line has been found, and thus will track further.

In the case of a noisy edge, the box is widened as a function of how
far the maximal gradient goes astray. If, on a given try a certain per-
centage of points on the edge fall within the acceptance box, the program
computes any steering necessary, servoes onto the intended line and extends
itself a certain percentage of the box T s length. 90% of the points must be
inside the acceptance box before the box will extend. To compensate for
the case where the box is near the end of the line and the first 89%
of the point may be in and the remaining 11% out, a running total is kept
so that the box will advance, but not as much as usual. As the length of
the line increases, the points further out count more for steering. The
box is, in theory, free to rotate and is not constrained by the axis;
however, the servoeing mechanism is overdamped and the program will not
let the box rotate too far without looking for a corner.

-6-

Within the program is a function that has available to it the current
length of the line of interest. If the line cannot be extended, this
function decides what to do. E.g. it may increase the dimensions of the
box and try again. [When this is done, the percentage of increase of
length is larger than the percentage of increase of width. This has the
effects of 1) counteracting vidisector noise; and 2) speeding up the pro-
gram.] When just starting to look for a line, and loose tolerances are
desired, a negative line length is given to this function. This results
in a larger box.

Thus, when tracking a line, it uses a small box (close tolerances)
whcih requires few vidisector points and, consequently, runs fast. When
noise is encountered a wider box is called into use, which allows for more
latitude in tracking, at a sacrifice of speed.

All parameters can be set as a function of how long the line is at
the present time. Thus when the line is long, the direction that the line
is going is known fairly accurately and not much angular deviation is toler-
ated. If the apparent line goes off in another direction, it is most

-7-

likely a different line. If the line is short and there is a considerable
amount of deviation, it tracks the deviating line on the assumption that
it did not know the real direction. If an attempt is made to extend a
line and it fails, other attempts are made up to a certain maximum, desig-
nated by a parameter.

When the box cannot be extended any further along the line, that
point is recorded as a vertex and the radiation from that vertex of another
sharp gradient change is sought.

To find a new edge, trial boxes are drawn in a circle about the ver-
tex. Hopefully one of these boxes finds an edge. This done, the program
goes through two iterations of using very large scans and wide acceptance
factors to attempt to get onto the edge. (This prevents the occurrence
of a large error in the assumed direction.) Lines that emanate from the
same vertex are stored as a circular list structure. As the vertex is
traversed, the ring is built up so that it eventually has entries for all
of the end points that belong to the vertex. There is an implicit link
between the end points, so vertices are connected to one another by this

-8-

data structure.

The program continues in this fashion until the terminating condition
is reached, viz.it finds a line which it had previously found. This con-
dition is detected by a routine which makes periodic tests on the line
being tracked, after it exceeds a certain length. The cross-product of
the line being tracked and a line previously found is formed and normal-
ized. This gives a number, proportional to sin 0, which is compared with
a threshold. If they are not parallel, the lines are ordered so that the
two ends with the closest x value are together. Then the cross-products
of vectors 1 and 2 are computed. [See Figure 3.] If 1 and 2 are parallel,
they are different lines.

Figure 3,

-9-

If the lines appear to be different, checking is continued until
the end of the line. Before the line is accepted, the entire line is
retested. [The vidisector is so slow it is worth spending the time on
the chance that the line will be deleted*]

When the terminating condition is met, the program jumps back one
vertex and starts checking for additional lines emanating from it. If,
after a sweep of slightly more than 360° about the vertex, no lines are
found, it considers that vertex completely checked out. If the initial
scan runs into an edge at a place between vertices, there is no problem
of finding a half-line since the box searches with wide tolerances until
it finds a corner and the line it first tracked is ignored—to be found
later on.

The current operation of the program is such that there are tolerances
in %LEAV which say that the line must be extended at least n tries or it
is rejected.

The routine will accept as different two abutting lines (within a
certain tolerance) but will reject two lines that overlap. If a line is

-10-

not found after sweeping around the initial point, it gives up. An
inspection of LTBL will reveal this situation.

The lines are represented (in floating point) by two ordered pairs
of numbers, and are stored in LTBL — four register per line. Each pair
represents the x and y coordinate of an end of the line.

After the program has "found" a cube, further processing is avail-
able on the lines stored in LTBL, as noted below.
%FLUSH This routine has as its arguments n lines stored in LTBL.

If it finds three lines that are parallel it eliminates the
middle line. Thus, in the case of a cube, one would expect
the three inner lines of the cube to be deleted and the peri-
meter of the projection to remain. The lines are also ordered
by this routine as a function of their coordinates — the effect
being the storage of the perimeter of the figure by consecu-
tive sides.

-11-

SuTiimary

In Figure 4, assume the program is given point X, and begins a
circular scan, picking up the edge at position b_. It will then track,
with very large acceptance factors, until it reaches either vertex B_
or vertex B_\ When it is at one of these vertices, it will sweep out
in a circle, until it picks up a line. It will then trace this line to
a new vertex. When this is done, it pushes down the information one
level and starts out from the new vertex. When it is satisfied that
it has tracked around once, it. advances one level on its list and searches
again. Finally all nine lines are found and stored.

-12-

Normal Usage

The following is a description of how the entire package would operate.
Those persons interested in using special subsections for particular appli-
cations are urged to consult either of the authors for details since the
first derivative of the program is not yet zero.

The program is called by: PUSHJ P, NSIDE. It will first make a
rought vertical scan with the vidisector, taking gradients and finding
an average value for the scene. It then makes horizontal scans until
it finds something that exceeds the gradient threshold. When a vertex
is found, %LEAV is called. This tries to trace all lines leaving the
point. To do this, %LEAV calls LINEX. This routine will try to advance
the box one position each time it is called. [The actual displacement
of the box is a function of the past history of the line.] If the box is
able to be advanced, the next instruction is skipped. LINEX calls the
length and width functions which determine the dimensions of the box.

-13-

When all the lines are found, %FLUSH is called to order them and delete
inner lines. Finally C0RNS is called to find the vertices.

If fewer than four sides are found, the program tries again by
resuming the horizontal scan from where it left off.

This scheme, attempting to input an arbitrary graph instead of a
simple periphery, has the advantage that if a corner is badly defined,
by either poor lighting or physical wear, and the program fails to see
the other edges leaving it, there is a high probability of getting the
corner since it will be approached from the other sides.

A weakness is that the program does not consider the probability
of other edges radiating from a point unless the edge it was on has
terminated.

For a description of C0RNS, see Artificial Intelligence Memo,
by Robert South (M.I.T.: October 1965)

CS-TR Scanning Project

Document Control Form Date : JJ»/ tL i /*&

Report# Ai rr\ ^ lo)

Each of the following should be identified by a checkmark:
Originating Department:

£^ Artificial Intellegence Laboratory (Al)

□ Laboratory for Computer Science (LCS)

Document Type:

□ Technical Report (TR) j>?( Technical Memo (TM)

□ Other:

Document Information Number of pages. Witt-tm*^ )

Not to include DOD forms, printer intstructions, etc... original pages only.

Originals are: Intended to be printed as :

^ Single-sided or □ Single-sided or

□ Double-sided l£k Double-sided

Print type:

jS>V Typewriter Q Offset Press [_] Laser Print
□ InkJet Printer □ Unknown □ Other:

Check each if included with document:

□ DOD Form □ Funding Agent Form □ Cover Page

□ Spine □ Printers Notes □ Photo negatives

□ Other:

Page Data:

Blank Pagescbypesenumber):

Photographs/Tonal Material (byp^num^:.

vJtner (iioteoescnption/paoe number).

Description : Page Number:

iJFoTct>N5 _____

Scanning Agent Signoff:

Date Received: 1^1 1^1*15 Date Scanned: ' I A3 1*1 C Date Returned: / /^/f*

Scanning Agent Signature: h^tJLjLtjl fv ><^ryK,

_ ^~ v , Rev 8/84 DS/LCS Document Control Form cstrfomvvsd

09&

Scanning Agent Identification Target

Scanning of this document was supported in part by
the Corporation for National Research Initiatives,
using funds from the Advanced Research Projects
Agency of the United states Government under
Grant: MDA972-92-J1029.

The scanning agent for this project was the
Document Services department of the M.I.T
Libraries. Technical support for this project was
also provided by the M.I.T. Laboratory for
Computer Sciences.

M.IX Libraries
Document Services

darptrgt.wpw Rev. 9/94

``` 