Skip to main content

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

See other formats


jipmll^ 



■r*\ 



\ 




MASSACHUSETTS INSTITUTE Of 
PftOJKT MAC 



Artificial Intelligence Project 
Yjtai©%Me»^ J^>. 101. 



Keaortadua WW-M-320 
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