i L - The Stanford University InfoLab
Contents
1. 100 000 22 Xerox TVFONT PRIMER draft TVFONT i s on the system and can be run by typing TVFONT _ at alll display console At present 23 is next to a camera setup for making fonts The process of mak i ng a new XGP font or altering an old wi be explained in six steps 1 Raster input get a video image or an old font 2 Contour i ng make po ygons 3 Polygon editing delete scale position and alter2. lil 1 zu n al M x tii a i 22222222 ILLA m ee em eS EE 7 r 1 E 111 2 i bs BE UE lt d f ili ve gt 7 eri Py 1222 22 2 t ilii lal t Hi TE ii E n ii i pu shit i LE H tii im 1 jj itia i dtp dus i I ili E ili T vil dH nii shi i t ii uli 1 a i Hit BE nt m O T unt iji iili t uidi T 4 ji Joi m i HHI T ANTI T ME th win iii 2 a m 11 ili i Hit alate 11 TH a li m A o
3. The shape node contains the data necessary for normalizing two polygons so only their shapes remain In particular the row and col of a shape node is the center of mass of the polygon area isthe area perm is the length of perimeter and mxx myy mzz pxy is the polygons inertia tensor frorn which the principle angle of orientation can be computed When given two shapes the centers of mass may be aligned the principle angles may be align and the areas or perimeter of the two may be normalized There are two kinds of shapes polygon shapes and fusion shapes Polygon shapes correspond to a single polygon pointed at by the PGON link The CW CCW and NGON links of a polygon shape are NIL Fusion shapes are temporary nodes belonging to a level as a ring thru CW and CCW Fusion shapes correspond to the summation of two unmated polygons which are pointed to by the NGON and PGON links The expressions relating to the inertia tensor and to fusion summation are given in the section on polygon comparing The datums named perm area pxy mxx mzz contain the left half of a PDP 10 floating number Technical note half of a floating number has 9 bits of precision and should be expanded to full word by using the mirabile dictu instruction in order to avoid an illegal floating zero caused by truncating numbers like 1023 0 in CRE only the product of inertia will ever be negative 2 155
4. vt LEVEL NODE 0 LEVEL RING 90N a TYPE RELDC 4 5 7 T ys EMPTY AVAIL 2 RELOC 3 T es gt 4 5 T 99 6 70 4 7 50 SUMMARY OF LAMINAINERTIA TENSOR EXPRESSIONS RECTANGLE S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS MXX MYY MZZ FXY T T T T BxBxAREA 12 B HEIGHT IN RQWS 12 IN COLUMNS MXX MYY 0 ORIENTED RIGHT TRIANGLE S LAMINA INERTIA TENSOR ABOUT ITS CENTER OF MASS MXX MYY MZZ PXY T T T T 18 B HEIGHT IN ROWS 18 WIDTH IN COLUMNS MXX MYY 36 SUMMATION LAMINA INERTIA TENSORS AREA XCM YCM MXX MYY PXY ANGLE OF PRINCIPLE AXIS PHI PXY MXX MY Y PXY T T T f lt _ AREA1 AREA2 AREAL 1 AR E A 2 x XCM2 AREA AREA1 t AREA2 x YCM2 AREA MXX MXX2 Hy rd ges 1 PXYZ 1 t 1 XCMZxXCMZxAREA2 XCMlxYCMLIXxAREA t XCM2xYCMZxAREA2 t SXATAN 2 Q Sx MYY 2 TRANSLATION OF LAMINA INERTIA TENSOR AWAY FROM CENTER MASS t Y
5. Numeric absolute and relative positioning of the turntable is under the command the details of which are still being developed 35 TELETYPE COMMANDS VIDEO COMMANDS Take a4 bittelevision picture 6 1 television picture S Select camera number default is camera c 5 Set TCLIF default is O Set BCLIP default is 7 5 Shrink node space Calls node storage compactor The two command characters T and S control live video camera input The default camerais camera 1 the Cohu camera on the hand eye table Camera 0 is the Cart Receiver camera 2 is the ierra hand eye camera and camera 3 15 one or the other old brown cameras depending on which coaxisplugged up the brown camera near 123 is the Font Camera and the brown cameranear the turntable is the GCOMED Camera INPUT OUTPUT COMMANDS Input TMP file Television image from disk file e Input file Contour film from disk file 0 Output TMP file Television image to disk file lt lt 0 Output file Contour film to disk file X Output video image to XGP Output Ill file buffer for calcomp plotter Output VIC contour edges to This command requires a list of octal numbers J Contrast enhancement for the sake of appearance Type twenty CRLF s to clear page printer Display help summary of CRE commands IMAGE CONTOURING COMMANDS C Cut at given thresho
6. Although an affront to common sense the counter clockwise direction about the image ring is positive or later in time and the clockwise direction is negative or earlier in time achieved this curio by consistently adhereing to the mathematical convention of counter clockwise as positive and a day came when counter clockwise around a ring of real time events was represented in the same manner as counter clockwise around a polygonal ring of edges All the empty space in the image node is reserved for camera specification data 247 7 FILM NODE FORMAT CCW Ist empty uord OAD 2 6 0 Ist image 3 5 5 7 e Hor d a pis 0 me The film node is unique it is the first node in a CRE output file the SON of film is its first image the DAD of a film is NIL the CCW of a film is a pointer to the 1st empty node however because nodes are compacted for output and then relocated with respect to the film node the final empty node pointer indicates the number of words of data in the CRE file 18 1 8 EMPTY NODE FORMAT Hord 73 ward 3 uer d 4 CCW 0000 ord word 5 ER The list of empty nodes is maintained in the CCW link postion the last empty node contains a zero or NIL link At present all the other words of an empty node are zero FIGURE S
7. t anes tt erases the marks so that for region uith smooth boundar ill follow spiral path ta the center eating up ihe marks it goes like lathe with the tool continually advancing into the work 5 the contiguity routine scans it lays down back amp scratch array which enable t to retrace tts path back to the start H dezd end s reached no more marked it traces back along this path looking marked points to the risht Thrre br nn marked points on the left side while backtracking since this was the right side on the way out and the outaoing can stayed as far ta the right ns pnesiblr If a marked point i found nn the backtrace it is replaced with a pointer to the adiocent path already traced out and then new path is traced as if this a starting point When the boarktrace reaches the original starting point the contiquity scan completed effect of this algorithm 5 to construct a tree of pointers in the scratch array with the starting paint atthe root All points which can be reached via a connected path fram the starting point kill be apart fthistree 28 FI GURE 7 SMOOTHING AND ARC MAKI ku b ee ud TES 95 gt a the I kaw 4 SMOOTHING In CRE the term smoothing refers more to the problem of
8. 5 LEVEL NODE FORMAT CCW level ring j SUN 1 image Ist polygon 3 word type reloc lt 33 0200 Hord 0 uord ALT ncnt 4 ist fusion shape threshold cut level 2 tior c G Every level belongs to an image pointed to by the DAD link the ring of levels of an image is formed in the CW and CCW links the son of a level is its first polygon and that first polygon is the upper left most polygon of the level The ncnt datum of a level contains its threshold cut value which is an integer between 1 and 63 The 1 level is always generated and it contains a single polygon with four sides The 1 levels polygon is called the border polygon the fiction being that every point beyond the edges of the television picture has an intensity value of 2 which is blacker than black The ALT link of a level contains a temporary pointer to that levels ring of fusion shapes during polygon compare time mating 16 6 IMAGE NODE FORMAT H CCH 0 image ring 3 DAD C vom film 15 level 3 2 33 0000 uord 3 p 4 word lt 8 8 Every image belongs to the film pointed to by the DAD link the ring of images of the film is formed in CW and CCW links the son of an image is its first level and that first level is the 1 intensity cut level of the image
9. 5 Teve branch t1 ipe fM eacb rvel 9 1 scanned and the pointsabnve the dhrecsbiotdd marked in array This scatch array isthen scanned for marked paints When ane ts found a contiguity routine is called which visits all marked points ubich can be reached from the start via a connected path The marks are erased by this coutine as tt goes and statistics kept on the region thus generated such as the sums of the x and coordinates of the points and the sum of the squares of the x and coordinates used to compute the center and the eccentricity fl tree node 16 then made up for the region and the can for marked paints continues A special mark ts Jeft ta the scratch array for earch region When this mark is encountered during the the next level it 15 looked up on an association list This establishes th link reninn and the regions which are a subseto fita t t h e previous level iP beteren n nnde snd its sub nades The contiquity scan 15 the most complex program It works by leaving directional pointers the seratch array These are three bit cades denoting one af the crabt paenible nershboring points The contiguity sean is always started at point wbect is the bottom edae of the resion TCU traces along this edge to the riaht by maving from ane marked point ta the next but always keeping an un marked point to ihe de fi
10. DISPLAY BOTH OF ABOVE DISPLAY VIDEO INTENSITY CONTOUR MUNGEO PIXELS NO OP RESET LOGICAL CAMERA POSITION RESET DISPLAY TVFONT COMMAND SUMMARY Fetch f i im node c Fetch first image node from f i B Fetch firstlevolfrom film C Fetch first polyganfrom film IF NODE IS CURRENTLY BEING DISPLAYED THESE COMMANDS AFFECT THAT NODE OTHERWISE THEY AFFECT THE CAMERA VIEWERS POSITION CONTROL MULTIPLIES BY 2 META MULTJPLIES BY 4 MOVE LEFT BY DELTA MOVE RIGHT 5 BY DELTA MOVE UP BY DELTA MOVE DOWN BY DELTA DIVIDE DELTA BY 2 MULTIPLY DELTA BY 2 HESE COMMANDS AFFECT THE CAMERA VIEWERS POSITION INCREASE MAGNIFICATION BY DELTA DECREASE MAGNIFICATION BY OELTA x aN THESE COMMANDS CHANGE NODE BEING DISPLAYED FETCH COUNTER CLOCKWISE NODE IN RING FETCH 5 NODE IN RING FETCH FATHER OF NODE FETCH SON OF NODE FETCH ARC QF POLYGON OR VERTEX3 FETCH POLYGON OF VERTEX EQUIVALENT lt gt EQUIVALENT TO lt gt FLUSH NODE DISPLAY lt gt V THESE COMMANDS AFFECT THE 5 LIST PUSH NODE BEING DISPLAYED ONTO STACK POP NODE OFF STACK AND DISPLAY IT SWAP NODE BEING DISPLAYED WITH TOP OF STACK 47 TVFONT S EXTENDED COMMANDS ARCWIO Set smoothing constant Thisis the max mum d i stance aver tex may from a arc before is spl it into tuo arcs Gee description of sm
11. 4 Polygon 1 0 save and restore polygons 5 Font output make new font and output font fi le Complexity arises in that there is more than oneway do each step there are default arguments and switchs which the user C may al ter there are ways save and restore intermediate resul ts and there are quite a few different display modes and display diagonostics TVFONT command scanner resembles that of and aswell as and CEDMED the command scanner types as tcr i sk when it is in its top most listen loop waiting for s i e command character The command character may be mod i f i ed by ps the META CONTROL keys Which Hi I be abbreviated as ang CONTROL and META CONTROL respect i ve y Many commands in turn require arguments such as numbers or fi le names Finally the X command waits for an extended command name of several characters which i scal ed an extended command This first explanation will present a way of making new font using the fewest commands Raster Input and Contouring I take television picture 2 Display histogram of television picture 3 C24 Cut at intensity level 24 Get the Font Camera looking at a single letter in a font book Use black piece of paper uithasquare cut out amask to isolate the letter The T command will take a television picture The H command wi d
12. K KILL IMAGE POLYGON OR VERTEX SHOW LAST IMAGE al CHARACTER FROM FONT IN FNTSEG MOVE POLYGON TO NEXT IMAGE aT MOVE TO NEW IMAGE en MIDPOINT LINE MUNG ONTO GRID POINT AS SEEN IN cY N NEXT IMAGE aN PREVIOUS IMAGE GN REPEAT NEXT IMAGE UNTIL A CHARACTER IS TYPED HEPEATPREVIDUS IMAGE UNTIL CHARACTER 15 TYPED po 1 2 404 1 84 9 4 3 4 D E e un G D I T Aa T 5 21 3 ra b C d C e E hai l In D 4 0 f U V W X Y 45 COMMAND SUMMARY at cL Q at H 5 aS 85 lt 5 aV GV cH X y GY ay Z 2 BZ OUTPUT CAREYE FILE OUTPUT CRE FILE OUTPUT FONT FILE PLOT OUTPUT FILE MAKE FONT MAKE 1 2 SIZE FONT DISPLAY MATRIX FOR THIS ROTATE IMAGE LEVEL OR POLYGON ANGLE IN RADIANS 5 SMOOTH AND KILL VIDEO INTENSITY CONTOUR REPEAT S FOR EACH IMAGE REPEAT aS FOR EACH IMAGE TAKE A TV PICTURE TAKE A TV PICTURE SETTING CLIP LEVELS AUTOMATICALLY CREATE VERTEX AT CENTER CREATE NEL VERTEX AT CURRENT VERTEX CREATE VERTEX IN NEW IMAGE CENTER IN THE WINDOW CENTER Y POSITION ONLY CENTER X POSITION ONLY MOVE POINT SPECIFIED BY LIGHT PEN TO CENTER XTEND MODE COMMANDS DISPLAY SMOOTHED FORM DISPLAY VIDEO INTENSITY CONTOUR
13. Move camera right Move camera down Move camera up Zoom out shrink displayed image Zoom in expand displayed image AL Reset scrolling window to it initial position and size Halve strength of scrolling delta Double strength of scrolling delta Single step displayed image forwards Single step displayed image backwards film display forwards e Run film display backwards The firstseveral commands allow minute examination of the image by magnification and window posit ioning The command character e allows single stepping thru the film of images or continous display of the film forwards or backwards rM i ia Q p CART DRIVING COMMANDS Drive forwards Drive backwards Turn wheels hard left Turn wheels hard right L Pan camera left eR Pan camera right SPACE Stop the cart RETURN Exit cart command mode 2 01 First and most important is understanding how to stop the cart The teletype halt command is SPACE also any character other than F B L or will stop the cart Cart commands passed first from a teletype to the PDP 10 then to the PDP 6 then over a citizens band 27 045 megahertz radio link to the cart control logic When communication is lacking between entities in the chain of command the lower entity times out and causes the cart to halt The cart control logic times out in a fifth of a second if it does not
14. a pointer to the polygon of each vector is stored in the link named DAD as members of a polygon the vectors form a loop which is always connected so that each vertex has a neighboring vertex in the clockwise andin the counter clockwise directions about the polygon s perimeter these perimeter pointers are stored in the link positions named CW and CCW Vectors never cross arcs cross on occassions but can be fixed The ncnt datum of arcs and vectors contains their length The time line links NTIME and PTIME may point to a corresponding arc or vector in the image previous or subsequent to the current image The zdepth datum contains a positive number indicating distance from the camera s image plane the tdepth computation is not properly implemented as of 1973 13 gt 3 POLYGON NODE FORMAT M ers d C M ee A polugo ring 3 SUN l level lst vector 3 Word tupe 2 18 3g 243 uor c 3 fist polygon within surround 3 ALT ncnt shape lst arc number of s 1 des 2 word PONN 9 nest bro polugon nestsis polygon 3 Hord m 6 NTINE time line FTIHE 3 tvery polygon belongs to a level pointed at by the DAD link the ring of polygons of a level is formed in the CW and CCW links the son of a polygon is its first vector or arc after the polygon has
15. um i 1 2 1 p gt 1 THRESHOLDING Thresholding the first and easiest step consists of two subroutines called THRESH and THRESH converts a 6 bit image into a l bit image with respect to a given threshold cut level between zero for black and sixty three for light All pixels equal to or greater than the cut map into a one all the pixels less than the cut map into zero The resulting 1 bit image is stored in a bit array of 216 rows by 288 columns 1 728 words called the PAC picture accumulator which was named in memory of McCormick s ILLIAC 1IIl After THRESH the contains blobs of bits A blob is defined as rooks move simply connected that is every bit of a blob can be reached by horizontal or vertical moves from any other bit without having to cross a zero bit or having to a diagonal bishop s move Blobs may of course have holes Or equivalently a blob always has one outer perimeter polygon and may have one several or no inner perimeter polygons This blob and hole topology is recoverable from the CRE data structure and is built by the nesting step Next PACXOR copies the PAC into two slightly larger bit arrays named HSEG and VSEG Then the is shifted down one row and exclusive OR ed into the HSEG array and the PAC is shifted right one column and exclusive OR ed into the VSEG array to compute th
16. 28 29 30 31 32 33 34 35 unused CAR WORDO CDR WORDO unused CAROWORDI CDR WORD 1 unused CAROWORD3 WORD3 unused CAR WORD4 CDR WORD4 unused CAR WORDS WORDS unused CAR WORD6 COR WORDG The CAR of a word is the left half The CDR of a word is the right half in the node diagrams rclocation of each word is indicated directly to its right as 0 1 2 or 3 meaning no relocation left only right only and relocate both halves respectively 1 VECTOR amp 2 NODE FORMAT CH vector ring 3 uord DAD SN 1 arc or vector 3 uord ee pelos C E 33 8883 rot col E 0008 09 0000 00 0 ird o ncnt length word lt zdepth 0 Hord NIIHE time ine 3 The format of vectors and arcs is identical Inside CRE the term vector has the connotation of being strictly a horizontal or vertical generated by the cont ouring step whereas an arc is a vector generated by the smoothing step Vectors contain the fundamental geometric datum of an image locus The image locus is stored in the halfword datums named row and cot which contain the row and column of a point in units 1 64 of a pixel A pixel is a picture element Vectors and arcs also contain the photometric datum of edge contrast Vectors always belong to a polygon node
17. 75 0455 The views and conclusions contained in this document are those of the author and should not be interpreted as necessarily representing the official policies either expressed or implied of the Advanced Research Project Agency the United States Government pus INTRODUCTION CRE stands both for Contour Region Edge CRE is a solution to the problern of finding contour edges in a set of television pictures and of linking corresponding edecs from one picture to the next The process is automatic and is intended to run wit hout human intervention Furthermore the process is bottom up there are no significant inputs other than the given television images The output of CRE is a2D contour map data structure which is suitable input to a 3D geometric modeling program The overall design soal for CRE was to build a region edge finding program that could applied to a sequence of television pictures and that would output a sequence of line drawings without having to know anything about the content of the images Furthermore it was desired that the line drawings be structured The six design choices that ueterrained the character of CRE are 1 Dumb visionrather than model driven vision 2 Multi irnase analysis rather t han single image analysis Tot alimage struct ure imposed on dze finding rather than separate edge finder andirnage analyzer 4 Automatic rat her than intera
18. CRE does not raise any new scientific problems nor does it have any really new solutions to the old problems rather CRE is another competent video resion edge finding program with its own set of tricks However it is further my impressionthat the particular tricks for smoothing nesting and comparing polygons in CRE are original as programming t cchniques The intended use of CRE is illustrated by the sequences of turn table pictures on paecs land 2 The figures on page 5 illustrate the quality of contoured images over range of subject matter Finally the application of to typography is illustrated below Gh eitis A out sek OL TRU UP ah HP SR Th TW o RST A Vv aw x whe de Fgh tik lmno poe stovw x ACKNOWLEDGEMENT Tovar assisted me with the development of the type font making program TVFGNT HO FIGURE 3 INTENSITY COPITOURING ON A VARI E T Arcem tut A REGULAE POLYEGHM o gi y GRI D men wiih equol aides COSE ey There s nm omone m _ 9 Un three d mena nma the analog of we mm seges m wiid bougdeg Tawa congruent faces and rongement One macht meuppese 90 mode but im thes sre on Lewis J lero DA T A STRUCTURE BASICS Thetwo generic data structures of are arrays and nodes there are five kinds of arrays and ei
19. a 216 by 288 window and the image will be repacked with undefined pixels set to zero Both the I and the O commands will ask for a filename if an extension is not explicitly given the default extension TMP will be used The 0 command will output the CRE data structure and the c command will input CRE data structure naturally the default extension is The X command will output a video image to the XGP The C command followed by a list of octal number s will output the HSEG and VSEG raw vector contours to the XGP The P command will output the currently displayed 111 buffer the default extension is Finally the J command enhances the contrast of an image for the sake of its appearance on the XGP INTERACTIVE MANUAL MULTI IMAGE PROCESSING Taking or inputing new television images and contouring them using the C command or the Q command will form a film data structure images can be explicitly compared and linked by typing M match command which links the latest image with the immediately previous image The Z command will zero the data structure of all images AUTOMATIC MULTI IMAGE PROCESSING The command is for automatic turn table perception takes 64 pictures from camera 3 whilerotating the turn table outputs a file and exits returning control to the 3D geometric editor The turn table is manually moved small amounts by the four possible Y commands BY and
20. about Z axis product of inertia with respect to the X and Y axes DA T A STRUCTURE THE RINGS TREES LISTS AND ARRAYS CRE inputs animace into an array called TVBUF it makes the node structures some of which are temporary and it out puts a final version of the structure representing a film of images Thetemporary structures are relevant to understanding the process but only the final structure is relevant to using CRE output In summary the important structures are FOUR RINGS 1 Image t ing of the film 2 Level ring of an image ring of i 1 level 4 Vcctor ring of a polygon TWO Thelree of rings 2 The tree of nested polygons TWO LISTS 1 fime line lists 2 nodo list TEMPORARY STRUCTURES 1 Arc rings of polygons 2 Fusion shape rings of levels FIVE ARRAYS TVBUF 216 columns of 6 bit bytes 2 PAC 2 1 columns of 1 bit bytes 21 1089 columns of 1 bit bytes 21 7 285 columns of 1 bit bytes 5 SKY 2 16 rows 289 columns of 18 bit bytes gt CO T Ther ts one film node The film is composed of a ring of images Each image is compo ocd of a ring of lavels Eachlevel is composed of a ring of polygons Each polyson is composed of aring of vectors The ring structures are implemented with the four links nara d DAD SON ana CCW The rings are headless only in the sense that a
21. been smoothed and that first vector has the upper left most locus of any vector of the polygon The ENDO NGON PGON are used to form nested polygon tree Every polygon has non NIL NGON and PGON links the trivial case being that the polygon points at it self twice Every polygon except one the outer border polygon has a non NIL EXO link Every polygon that surrounds one or more other polygons has a non NIL ENDO link The ALT link position of a polygon temporarily points to the first arc of a polygon during smoothing when a polygon has both vectors and arcs The final contents of the ALT link is a pointer to the shape node of the polygon The ncnt datum indicates the number of sides of the polygon The time line of polygons runs thru the NTIME and PTIME links which point either to a nearly exact match of a polygon or to a fusion polygon of a two for one match or to one of the two fission parts of a one for two match find the other fission the time links of the vectors must be scanned We rim 4 NODE FORMAT ee fusionsh pe ring QJ Hor c reloc 38 8838 0000 ci i word tou 8888 productof inertia fusion polygon main polygon 3 wor cd mx x ord 15 t Y axis moment g
22. eight smaller images illustrate the results of setting the arc width tolerance over a range of values Because of the dekinking mentioned earlier the arc width tolerance can be equal to or less than 1 0 pixels and still expect a substantial reduction in the number of vectors it takes to describe a contour polygon A final important smoothing detail is that the arc width tolerance is actually taken as a function of the highest contrast vector found along the arc so that high contrast arcs are smoothed with much smaller arc width tolerances than are low contrast arcs After smoothing the contrast across each arc is computed and the ring of arcs replaces the ring of vectors of the given polygon Polygons that would be expressed as only two arcs are deleted 2 30 Fi 9 FIGURE 9A FIGURE 98 e a A 4 Be NS m ROM pr or e k POLYGON COMPARE AND LINK FIGURE 90 j 5 COMPARING The compare step of CRE connects the polygons and arcs of the current image with corresponding polygons and arcs of the previous image CMPARE solves the problem of correlating features between two similar images and is composed four sub sect ions make shape nodes for polygons compare and connect polygons one to one compare and connect polygons two to one compare and connect
23. for debugg i ng READF NT Convert font which has been read into the font segment into polygonal representat ion displaying each character as read SCALE Scale al images by constant Equivalent to the command B applied to each image SLANT Slant al images by constant Pl ease see command cB for a more complete description SORT Sort i mages f i lm according to ASCI code This i s for conv i enence in looking a fonts sequentially The G command i s recommended for finding specific characters XEROX OUTPUT TV IMAGE TO XGP XSCALE Scale al l images by constant in the X direction Equivalent to the command applied to each image YSCAL E Scale allimages by constant in the Y direction Equivalent to the command applied to each image E 49 F b s TVFONT NODE FORMATS JAN 1973 VERTEX ARC NODE 0 VERTEX RING 1 COL RELOC 3 T ss 7 4 ARC 5 PGON 6 RT SEG LTSEG MACE NODE 8 MAGE RING l SON e TYPE RELOC 3 7 4 7 T 9 4 FILM NODE 8 CORESIZE 1 SON 2 TYPE RELOC B AVAIL 4 BLOCK COUNT 5 T 99 7 E 9 n a SEGMENT NODE 0 SEGMENT RING 1 7T s3 7 2 300903 4 LCOL RCOL 2 LROH RROW POLYGON REG ON NODE 0 POLYGON RING DAD SON TYPE RELOC 2 72 4 NCNT 5 PGON b SUO
24. hear from the POP 6 the PDP 6 times out in less than a minute if it has not heard from the PDP 10 the PDP 6 stops broadcasting cart commands if it detects the death of the PDP 10 the PDP 10 job times out after 5 minutes of not hearing from the teletype and kills the PDP 6 spacewar job Second and of occasional interest is understanding how to make the cart go The command F will make the cart go forwards and the other commands will cause action as mentioned in the table the cart fails to move alt itsswitchs should be check for being in the ON or AUTOMATIC or FAST position all its plugs should be plugged in and its batteries should be checked Recently cart failure had been most often caused by the radio transmitter in the Kludge Bay Check to see that the transmitter is turned on and that the PDP 6 is running By the end of the year 1973 a new cart radio controler will be installed by Hans Moravec and these commands will be updated CART HARDWARE DIAGONOSTIC V Enter diagonostic listen loop RETURN Exit diagonostic listen loop NUMERALS 0 1 2 3 4 5 6 7 send direction relay bits CHARACTERS H A B C D E F G send action relay bits The cart diagonostic listen loop simply takes the low order four bits of a non carriage return ASCII character and broadcasts them to the cart The cart decodes four bit radio command bytes into six relays commands 0 thru 7 set the pan drive or steering direction relay repective to bits 4 2 and 1 co
25. must check for first a turn to the east indicated by a bit in HSEG next for no turn continue south and last for a turn to the west When a turn is encountered MKPGON creates a vector node representing the run of bits between the previous turn and the present turn The trace always ends heading west bound The outline so traced can be either the edge of a blob or a hole the two cases are distinguished by looking at the VIC polygon s uppermost left pixel in the PAC bit array There are two complexities contrast accumulation and dekinking The contrast of a vector is defined as QUOTIENT DIFFERENCE Sum of pixel values on one side of the vector Sum of pixel values on the other side of the vector length of the vector in pixels Since vectors are always either horizontal or vertical and are construed as being on the cracks between pixels the specified summations refer to the pixels immediately to either side of the vector Notice that this definition of constrast will always give a positive contrast for vectors of a blob and negative contrast for the vectors of a hole The terms jaggies kinks and sawtooth all are used to express what seems to be wrong about the lowermost left polygon on page 25 The problem involves doing something to a rectilinear quantized set of segments to make its linear nature more evident CRE jaggies solution in the subroutine MKPGON merely positions the turning locus diagonally off its grid poin
26. polygon s and the mutually closest vertices closer than an epsilon are considered to be mated Actually the potential N M compares is avoided by a window splitting scheme similiar to that used in hidden line elimination algorithms like Warnock s The results of vertex compare and mate are illustrated in figures 9 and 9D the compare execution takes less than a second on images such as the pump blocks and dolls that have appeared in this paper The applications of this compare might include the aiming of a pixel correlation comparator such as Quam s recognition and location of an expected object or the location and extent of an unknown object is this latter application that will be described in my forthcoming thesis 33 Ill USING CRE A PRIMERON RUNNING CRE B TELETYPE COMMANDS C SAIL INTERFACING D LISP INTERFACING PRIMER ON RUNNING CRE Single Image Contouring The Stanford copy of 15 run by typing CRE CRE displays only on a console however if will work without displays when run from a Data Disc console The command scanner is a simple charac ter jump table the command scanner will type an asterisk when it is listening for teletype input Carriage returns following commands are unnecessary but harmless most commands signal their completion by displaying something or by typing a carriage return Some commands require arguments or file names The question mark gt comman
27. t AREAxDXxDX AREAXDXxDY ROTATION OF LAMINA INERTIA TENSOR ABOUT CENTER OF MASS S MXX MYY FAT lt lt PHI SINE PHI SxSxMYY 2 2 S S PXY t CxSx MYY MXX REFERENCES 1 GOLDSTEIN H 1950 Classical Mechanics Addison Wesley Reading Massachusetts 2 KNUTH D E 1968 The Art of Computer Programing Volume 1 Fundamenta gor i thms Chapter 2 Informat ion Structures Addison Wesley Reading Massachusetts 3 KRAKAUER L J 1971 Computer Analysis of Visual Properties of Curved bjects Project MAC Technical Report 82 Massachusetts Institute of Technology Cambridge Massachusetts 02139 4 ZAHN C T 1366 Tr JO Dimensional Pattern Description and Recognition via curvature points SLAC Report 70 Stanford Linear Acceleration Center otanford University Stanford Cail fornia BS 2
28. 9 columns of 18 bit pointers The name SKY came about because the array use to represent the furthest away regions or background which in the case of a robot vehicle is the real sky blue The sky contains vector pointers and would be more efficient on a virtual memory machine that didn t allocate unused pages of its address space Whereas most computers have more memory containers than address space computer graphics and vision might be easier to program in a memory with more address space than physical space i e an almost empty virtual memory The first part of the INTREE routine finds the surrounder of a given polygon by scanning the SKY due east from the uppermost left pixel of the given polygon The SON of a polygon is always its uppermost left vector After INTREE the INSKY routine places pointers to the vertical vectors of the given polygon into the sky array The second part of the INTREE routine checks for and fixes up the case where the new polygon captures a polygon that is already enciaved This only happens when two or more levels of the image have blobs that have holes The next paragraph explains the arcane details of fixing up the tree links of multi level hole polygons and the box following that is a quotation from the appendix of Krakauer thesis 3 describing his nesting aigorit hm z 07s 3 NESTING Let the given polygon be named Poly and let the surrounder of Poly be called Exopoly and assum
29. HOWING RASTER STRUCTURE NORTH grid point R C R C 1 oH 5 E C lt WEST d PIXEL R C SOUTH R 1 C 19 EAST W DATA STRUCTURE IMAGE ARRAYS As mentioned before there are five arrays in CRE TVBUF Television Buffer PAC Picture Accumulator VSEG vertical segments HSEG horizontal segments and SKY background sky blue array The dimensions are FIVE ARRAYS 1 TVBUF 216 888 columns of 6 bit bytes 2 216 0 88 columns of 1 bit bytes 3 VSEG 2160 889 columns of 1 bit bytes 4 HSEG 210 888 columns of 1 bit bytes 5 SKY 21610889 columns of 18 bit bytes Inside CRE the video image size was fixed at 216 rows of 288 columns of 6 bits per pixel My original idea was to write a vision operator that would be applied on a small fixed sized window so have had windows 2 by 2 2 by 3 4 by 9 32 by 36 72 96 and 216 by 288 That is 216 2 2 2 3 3 3 and 288 242x2 2 213x3 Having fixed window size avoids a morass of word packing array allocation and window splicing Having a window size constructed out of powers of 2 and 3 simplifies what word packing is required and allows me to do area and space computations in my head The image arrays of CRE are of course two dimensional with the coordinates in row and columns Row number increases going down image in the negative Y axis direction which is also called the direction south Column numbers increase going right on th
30. STANFORD ARTIFICIAL INTELLIGENCE LABORATORY MEMO AIM 199 STAN CS 73 398 IMAGE CONTOURING AND COMPAR ING BY BRUCE G BAUMGART SUPPORTED BY ADVANCED RESEARCH PROJECTS AGENCY ARPA ORDER NO 2494 PROJECT CODE 3D30 OCTOBER 1973 COMPUTER SCIENCE DEPARTMENT School of Humanities and Sciences STANFORD ARTIFICIAL INTELLIGENCE LABORATORY OCTOBER 1973 MEMO AIM 1 99 COMPUTER SCIENCE DEPARTMENT REPORT NO 598 IMAGE CONTOURING AND COMPARING Bruce G Baumgart ABSTRACT A contour image representation is stated and an algorithm for converting a set of digital television irnages into this representation is explained The algorithm consists of five steps digital image thresholding binary image contouring polygon nesting polygon smoothing and polygon comparing An implementation of the algorithm is the main routine of a program called CHE auxiliary routines provide cart and turn table control TV camera input image display and xerox printer output A serendip application of CRE to type font construction is explained Details about the intended application of CRE tothe perception of physical objects will appear in sequels to this paper CONTENTS Introduction The data structure Il The CRE algorithm Ill Using CRE IV Using TVFONT Post scripts This research was supported in by the Advanced Research Projects Agency of the Office of the Secretary of Defense under Contract DARC 15
31. breaking a manifold polygon into functions arcs rather than to the problem of fitting functions to measured data The smoothing step converts the polygons of vertical and horizontal vectors into polygons of arcs For the present the term arc means linear arc which is a line segment Fancier arcs circular and cubic spline were implemented and thrown out mostly because they were of no use to higher processes such as the polygon compare which would break the fancier arcs back down into linear vectors for computing areas inertia tensors or mere display buffers omoothing is applied to each polygon of a level To start the smoothing a ring of two arcs is formed a bi gon with one arc at the uppermost left and the other at the lowermost right of the given vector polygon Next a recursive make arc operation is is appled to the two initial arcs Since the arc given to MKARC is in a one to one correspondece with a doubly linked list of vectors MKARC checks to see whether each point on the list of vectors is close enough to the approximating arc returns the given arc as good enough when all the sub vectors fall within a given width otherwise MKARC splits the arc in two and places a new arc vertex on the vector vertex that was furthest away from the original arc The two large images in figure 7 illustrate a polygon smoothed with arc width tolerances set at two different widths in order to show one recursion of MKARC The
32. by taking empty nodes from an AVAIL list and entities are killed by returning their node to the AVAIL list there is no garbage collector but there is aspace compactor DATA STRUCTURE LINK AND DATUM NAMES Nodes contain either numerical data or pointers to other nodes such node pointers tauchine addresses are called links The positions within a node where a link is stored are named and are reserved for particular uses In the table below thel link names and 1 3 datum names are introduced The link names will always appear capit alized 1 1 LINK NAMES CW clockwise CCW count er clockwise DAD parent of node free structure descendent of a node down a tree structure ENDO Greek for inside polveon wit hin Greek for out side surrounding polygon Li alternate NGON negative polygon PGON positive polygon NTIME negative in real time into the past PTIME positive in real time into he future 13 DATUM NAMES Eoo ean dat urns type type of node bits reloc rellocation of node bits Fixed point datums row row of image locus col column of locus cnt rst contrast of an doo vector and arc ncnt number count various uses une point datums zdepth 2 depth frorn camera lens center perm length of perimeter area area in pixel unit s motnent of inertia avoitt X axis rayy moment of inertia about Y axis mzz moment of inertia
33. ctive 5 Fixed image window size rather than variable window size 6 Machine language rather than higher level language The design choices are ordered from the more strategic to the more tactical the first t hree choices being research strategies the latter three choices being programming tactics Adopting thesedesign choices lead to image contouring and contour structutes sirnilar to that of Krakauer 3 and Zahn 4 The first design choice does not refer to the issue of how model dependent a finished vision system will be it will be quite model dependent but rather to thr issue Of how one should begin building such a system believe that the best starting point s are at the two apparent extremes of nearly total knowledge of a par ticular visual world or nearly tot al ignorance The first extreme involves synthesis by computer sraphics of a predict cd 2D image followed by comparing the predicted and a perceived image for slight differences which expected but not yet measured The involves analysing perceived images into structures which can be readily for near equality and measured for slight differences followed by the construction of a SD geometric model the perceived world The point is that in both cases are compared and in both cases the 3D model initially or finally contains specific numerical data on the georaetry and physics of the particula
34. d will display a summary of all the other commands Command characters may be modified by the control and meta shift keys such keying will be indicated in this document by prefixing the characters and to indicate control meta both rneta control shift keying respectively The command T will take a four bit television picture from camera number The command will display a histogram of the television picture The command character SPACE will refresh the image you had before the histogram display The command C followed by a list of octal numbers followed by a carriage return will make a contour image and display it Thus the teletype discourse for taking and contouring a single television image should have the following appearance IC R CRE T H C2O 40 60 All the images in this document were made with 3 or 7 equally spaced contours for which cases 80 xQ will automatically specify contour cuts are 20 40 60 or 10 20 30 40 34 PRIMER IMAGE INPUT OUTPUT AND XGP ing After you have an image and its contours you can save one or the other or both on disk files or print one or the other The O command will output a video image file in the new hand eye 200 octal word header format The 4 will input a video image from such a hand eye file if the file is not 216by 288 then the center of the image will be placed coincident with the center of
35. e current arc vector The polygons of arc vectors mated in time are themselves mated in time because after polygon time tine links have been made one polygon is temporarily translated rotated and dilated so as to have the same inertia tensor as its mate that is the locus of the arc vectors of one polygon arc temporarily altered then the correspondins arc vectors are found and their time line linkagesare made The empty node list is maintained CCW link positions the last empty node contains a zero link All nodes are explicitly made from and killed to the empty node list by the subroutines MKNODE and KLNODE The arc ring of a polygon is just like a vector ring except that the pointer to it is storcd in the ALT link of the polygon white the polygon has both a ring of vectors and a ring of ares The fusion of a intensity level runs thru the CW and CCW links of shape nodes is pointed at by the ALT link of the level Fusion shape nodes are the shapes gencrated to represent pairs of polygons unmated in time 10 DATASTRUCTURE TYPE BITS Each nodehas a word reserved for a boolean vector of 36 values or bits The first eighteen bits are called the type bits and are individually named as follows for 0 WESDIT westward vector vectors SOUEIT southward vector only 2 EASBIT eastward vector 3 NORBIT northward vector 4 NFUSE NTIME polygon fusion 5 NFISS NTIME polygon fission
36. e horizontal and vertical border bits of the PAC blobs Notice that this is the very heart of the edge finder of CRE is the mechanism that converts regions into edges TIE is an Mes 6 WD CORN 5 PEE s 5 5 en TR lt 24 e r Fi GURE 6 SAW TOOTH DEKI NKI NG LLUSTRATED t at SAW TOOTHED J N p SMOOTHED et 7 TOOTHED ye 2A DEKI NKED SAW TOOTHED 6 SMOOTHED 2 CONTOURING Contouring converts the bit arrays HSEG and VSEG into vectors and polygons The contouring it self is done by a single subroutine named MKPGON make polygon When MKPGON is called it looks for the upper most left non zero bit in the VSEG array If the VSEG array is empty MKPGON returns a NIL However when the bit is found traces and erases the polygonal outline to which that bit belongs and returns polygon node with a ring of vectors To belabor the details for the sake of later complexities the MKGON trace can go in four directions north and south along vertical columns of bits in the VSEG array or east and west along horizontal rows of the HSEG array The trace starts by heading south until it hits a turn when heading south MKPGON
37. e image in the positive X axis direction which is also called the direction east Video picture elements or pixels are thought of as expressing the intensity of a square cell the cells are numbered from 0 to 215 rows 0 to 287 columns the number of a ceil is the grid locus of its upper left northwest corner the center locus of a cell is at row 1 5 col 1 2 pixel cell is surrounded by four segments the horizontal segments are numbered 0 to 216 rows 0 to 287 columns the number of an HSEG is the grid locus of its left west end point The vertical segments are numbered 0 to 215 rows 0 to 288 columns the number of a VSEG is the grid locus of its upper north end point These conventions are suggested in the diagram at the bottom of page 19 20 l FI GURE 4 WATER PUMP VI DEO AND SMOOTH CONTOURS il ili ii x MES du si i i i qu i gt 4 gt 2 la du Em 29 il 11 E n ue d y wil E a 10 TT 2 d 5 5 T 3 1 2 H n em OF s THE ALGORITHM INTRODUCTION consists of five steps comparing t hresholding contouring nesting smoothing and Thresholding contouring and smoothi
38. e obt ained INTEGER FILM IMAGE LEVEL POLYGON VERTEX FILM O LEVEL SON FILM POLYGON SON LEVEL VERTEX SON POLYGON heusermay note that SAIL will compile three or more instructions for what is known as a 10 halfword operation also if the user converts the CRE nodes and links into LEAP items and associations then an overhead of from ten to one hundred instructions per halfword operation will bc incurred 239 6 LISP INTERFACING It should he possible to embed CRE machine code under a LISP core image however do do this work For the present the CRE Interface to LISP is only realized a disk file transfer data structure A read into LISP binary program space and accessed using the CRE nomensclature 1llink names 13 datum names by means of the S Expression subioutines provided in the file CRE LSP CRE BGB The subroutines work in both the old Stanford LISP 1 6 as welt as the newer UC LISP and Micro Planner The CRE LSP CRE BGB can be loaded eitherby one or the other of the following two LISP statements DSKIN CRE BGB CRE LSP ONCONPUT CRE BGBY CRE LSP is read into LISP binary program space by of the three possible INCRE formats INCRE filename INCRE filename project INCRE filename project programmer Filenames should be six characters or less projects and programmer i
39. e potentially MxN 2 compares is avoided by sorting on the center of mass locations In CRE which is intended for comparing sequences of pictures of natural scenes match for center of mass location is tested first and most strictly followed by match for inertia Pointers between matching polygons are placed in the time link positions of the polygon nodes and the polygons are considered to be mated in time 2395 5 COMPARING Third all unmated polygons of a level are considered two at a time and fusion shape node for each pair is made The potentially N N 2 N fusion shapes are avoided because there is a maximum possible unmated inertia in the other image if there are no unmated polygons in one image then the extra polygons of the first image can be ignored In the event where there are unmated polygons in corresponding levels of the two images the fusion shapes of one are compared with the polygon shapes of the other The fusion fission compare solves the rather nasty problem illustrated in figures 9A and 9B of linking two contour polygons of one image with a single contour polygon in the next image Fourth the vertices of polygons mated in time are compared and mated To start a vertex compare the vertices of one polygon are translated rotated and dilated to get that polygon s lamina inertia tensor coincident with its mate or mates Conceptually each vertex of one polygon is compared with each vertex of the other
40. e that Exopoly surroundsseveral enclaved polygons called endo s which are already in the nested polygon tree Also there are two kinds of temporary lists named the PLIST and the NLIST There is one PLIST which is initially a list of all the ENDO polygons on Exopoly s ENDO ring Each endo in turn has an NLIST which is initially empty The subroutine INTREE re scans the sky array for the polygon due east of the uppermost left vector of each endo polygon on the PLIST Exopoly s ENDO ring On such re scanning on behalf of say an Endol there are four cases 1 No change the scan returns Exopoly which is Endol s original EXO 2 Poly captures Endol the scan returns Poly indicating that endol has been captured by Poly 3 My brothers fate the scan hits an endo2 which is not on the PLIST which means that endo2 s EXO is valid and is the valid EXO of endo 1 4 My fate delayed the scan hits an endo2 which is still on the PLIST which means that endo2 s EXO is not yet valid but when discovered it will also be Endol s EXO so Endol is CONS ed into Endo2 s NLIST When an endo polygon s EXO has been re discovered then all the polygons on that endo s NLIST are also placed into the polygon tree at that place All of this link crunching machinery takes half a page of code and is not frequently executed _ KRAKAUER S NESTING ALGORITHM The mine 11 sarneratedone threshold level at t Ime starting at the
41. ent photometric data by quantum lines The explanation of CRE node structures will be presented in three parts first the several kines of nodes will be briefly exolained second the sub structures such as rings trees and lists willbe described and third the node formats and their contents will be explained di detail Following that willbe ancxplanation of the five at rays CRE The reader is warnedthat this whole sub section on data structure is an elaborate shaggy doe story f naming names and defining things all the action is to be found in the following sub section on the algorit hm DA TASTRUCTURE KINDS OF NODES Thoarecight kinds of CRE nodes Vector Arc Polygon Shape Image Level Film and Empty J Atthe top of the structure is the film node the film node is unique and serves as an OBLIST from which all other node s may be reached The film node embodies the idea of apiece of celluloid film or a length of magnetic video tape A film is a sequence of mages taken by the sarne camera of the same scene with only a small amount of action bet ween images 2 An image node represents the familiar two dimensional idea of a photograph or an oll painting or to be exact a digital video image of 216 rows by 288 columns of nurnbers ranging from 0 for dark to 63 for bright The image is formed by a thin lens and is projected on a flat image plane The idea of an image is so common that it is easy to ovcrlookthe wonder of su
42. fghijkImnopqrstuv 2 This is sample output from the Xerox Graphics Printer lec S n Aoodc2nuVJee lt 3 78 0123456789 lt gt eABCDEFGHIJKLMNOPQRSTUVWXYZIMI abcdefghijkImnopqrstuvwxyz lfl This is sample output from the Xerox Graphics Printer Joe 7 0 0 123456789 lt gt eABCDEFGHIJKLMNOPQRSTUVWXYZNt abcdefghijkImnopqrstuvwxyz lfl This is sample output from the Xerox Graphics Printer x lt gt sv 874 0123456789 lt gt eABCDEFGHIJKLMNOPQRSTUVWXYZIVI abcdefghijkImnopqrstuvwxyz lf This is sample output from the Xerox Graphics P rinter lt gt 7 0123456789 lt gt 2 eABCDEFGHIJKLMNOPQRSTUV WXY ZIMI abcdefghijklmnopqrstuvwxyztlfl 41 USING TVFONT Introduction TVFONT is a version of CRE January 1973 that Has specialized to the task of converting television images into type fonts for tne Xerox Graphics Printer The original idea uas to demons trate the utility of a polygon representation for scaling smoothing and editing typographical glyphs the resulting hack demonstration program was extended and developed by into the program called TVFONT Accordingly the main idea of s to convert video rasters into polygons to edit and scalethe polygons and to convert the poly
43. for 6 NEXCT NTIME polygon exact match polysons only 7 PFUSE PTIME polygon fusion 8 PFISS PTIME polygon fission 9 PEXCT PTIME polygon exact match 10 HOLBIT Hole polygon bit modify 1 1 ARCBIT Arc vector bit 12 SBIT Shape node bit 13 VBIT Vertex node bit 14 PBIT Polygon node bit kind 15 LBIT Level node bit 16 JE node bit 17 FBIT Film node bit The first four bits WESDIT SOUBIT EASDIT and NORBIT apply only to vectors and indic at the direction of the vector next six bits NFUSE NFISS NEXCT PFUSE PFISS are set by the polygon compare routine to indicate the kind of time mating found where and P mean negative time or postive time linkage fusion means that the givcnpolygon another polygon fuse to form the time polygon two into one fission means the given polygon splits one into two and exact means that the given polygon malchs one for one with its time polygon The next two bits HOLBIT and ARCDIT indicate distinguished polygons and vectors respoctively Only one of the last six bits SBIT VBIT PBIT LBIT IBIT and FBIT may be on ina node These bits indicate the node s type 2 DATA STRUCTURE RELOCATION BITS The next eighteen bits are called the reloc bits and indicate whether or not a link is stored in particular position of the node The relocation bits are used to compact the CRE node space for output 18 19 20 2 22 23 24 25 26 27
44. ght kinds of nodes The node structures to be discussed are implemented as seven word fixed sized blocks a fashion usual to graphics and simulation anintroduction to this technology can be found in Knuth 4 The language of implementation is PDP 1 0 machine codo via the FAIL asscrabler the whole nodal structure in CRE represents a sequence in time of video intensity contour rape Such contour maps arc like topographical elevation contour maps in that no two contour lines should ever cross and in that all the contour lines should close Consequently the loops of contours enclose regions and these regions overlap in a nested fashion forrang tree like data structure ihe seneral examples of contoured images on page 5 illustrate a notion that is emphatically not in is that of a schematic line drawing Although the CRE output can viewedasa collection of lines on a display screen people expecting a line drawing rendition of the given television picture will be disappointed A CRE picture is a simple transformation of the photometry geometry and topology of the original video image whet eas the typical line drawing from a human illustrator is a representation of the scene without photometric inforrnation the other hand the work of an artist such as Peter Max or a paint by the numbers grid does resemble CRE output This is not an idle coincidence but rat her a consequence of whether or not the artist is trying to repres
45. gons back into bit rasters This section IV uil available asa TVFONT user manual in another six months i t is presented here to give the uould be user a start and the general reader a sample of the design and extent of TVFONT The figure on page 41 is example of expanding contracting a font without manual touching up The top sample is the original BDR48 from CMU The remainder have been generated TVFONT The on contract ion done converting fonts from bit matrices into polygonal representation multiplying by the appropr i ate constant reconverting back into a bit representat ion The follow i ng paragraph is an example of a font made from television pictures XGP Xerox Graphics Printer Xerox LDX Palo Alto ee 1700 scan line 1700 2200 3 740 000
46. isplay a histogram of the television picture shouing how many points of the image intensity total black and how many point s of the i mage were 77 intehsi ty total white picture of a black glyph whi te background surrounded by a black mask should yield a histogram with two peaks Next the C command fo l owed by octal number fo owed by i age return contours the image at the given octal intensity cut threshold That is al the points of the image above the threshold are inside of a polygon The intensity value of the l owestval ley between the two peaks of the histogram is probably the best cut value and is probably the octal number 24 or 38 The cut command wi display the polygons that are made 4 Polygoh Killing 4 Fetch 1st polygon of 1st image of the fi Im 5 E d Kill a polygon 6 ring around the polygons of an image 7 flush node display Given an i niage of polygons corresponding to one letter undesired ygons can be del eted by using the K command and the node ink di splay commands To start the e wil intensify the first polygon of the image s polygon ring from there the commands will intensify the next polygon of the ring the K command wil I delete the presently intensified polygon and fetch the next po ygon A font corresponds to a f i lm An image corresponds to letter After taking a series of iaages and dele
47. ld levels Q Out at equally spaced conttours three cuts 20 40 60 Q Seven cuts 10 20 30 40 50 GO 70 E Enable all CRE processing D Disable allsteps except contouring M Compare and mate match current image wrth previous W Enter Arc Width Table alter mode M e a 36 F CRE TELETYPE COMMANDS NODE FOLLOWING COMMANDS Fetch film node Flush node display re CW CCW Fetch Ring links lt gt DAD SON Fetch Tree links TYPE RELLOC ENDO EXO Fetch nested polygon tree links lt gt ALT NCNT Fetch alternate shape or arc link c gt NGON PGON Fetch nested polygon tree links v A NTIME PTIME Fetch time line links These 14 commands allow detailed inspection of the CRE data structure by showing the contents of a node Data halfwords of a node are displayed in octal link halfwords are displayed prefixed with a letter indicating the type of node being pointed at a zero link is displayed as NIL The FILM node which is the root of the whole data structure is fetched and displayed by the command From the Film the gt command can be used toget SON FILM whichisalwaysthe first image gt command of an image will get a level and gt of alevel will geta polygon Vectors and polygons intensified when their contents are being displayed The exit commandis which leaves the screen less cluttered WINDOW SCROLLING COMMANDS
48. llthe ringare brothers a pointer to the head of a ring is stored in the DAD link of ach element The DAD of the film node is NIL and NIL is an 18 bit zero Thefinal SON of all vector nodes is also NIL The DAD and SON links form a tree of Fines DATASTRUCTURE THE RINGS TREES LISTS AND ARRAYS Besides the tree of rings there is the tree of nested polygons The nested polygon tree isimplemented with the four links named ENDO NGON and PGON The of a polygon points at its surrounding polygon The ENDO of a polygon points at one of the polygons that may be enclaved within the given polygon and the NGON and PGON links form ring of polygons that have the EXO polygon The time line lists run thruarc and polygon nodes In the simple case the time line links of a polygon point to a corresponding polygon in the image previous NTIME or subsequent of the current polygon the correspondence being that the time polygon iS exactly the sameintensity atnearly the same location orientation and size as the sivcenpbolyzon In the case of polygon fusion the time line link of a polygon points to a time polygon of which the given polygon becomes a part In the case of polygon fission the time line link of a polygon points to only one the pieces into which the given polygon splits The time line links of an arc vector pointto a corresponding arc vector in the image previous or subsequent of th
49. mmands A thru G set the pan drive or steering action relays respective to bits 4 2 and 1 35 385 SAIL INTERF ACING It should be possible to the CRE machine code under a SAIL core image however intend to do this work For the present the CRE interface to SAIL is only realized via disk file transfer of the data structure A CRE file may be read into an integer array in binary mode as illustrated below The first word of a CRE file is the first word of the film node which contains the size of the file in words The film node has address 0 the next node has address 7 and so on in multiples of seven There at e no empty nodes in a file The following SAIL program will read in file named X COMMENT EXAMPLE OF SAIL INPUT OF A CRE FILE BEGIN TEST INTEGER SIZE OPEN 1 DSK 8 3 0 0 0 0 LOOKUP 1 X CRE 0 SIZE WORDIN 1 BEGIN INTEGER ARRAY NODE O SIZE 1 SIZE 1 RELEASE 1 MAIN PROGRAM END END After the NODE array is loaded CRE links and data be accessed by their document names in areasonablenode link notation using macros like the following DEFINE CW Q NODE Q LSH 18 DEFINE CCW Q NODE Q LAND 777777 DEFINE DAD Q NODE Q 1 LSH 18 DEFINE SON Q NODE Q 1 LAND 777777 So that the first vertex of the first polygon of the first level of the first image of the film can b
50. n light scalterins off of surfaces refracting thru a lens and forming acomplex pat tern called a real image 3 Below the image node are the intensity contour levels A contour level is binary image that results from thresholding a gray scaled image So an image is composed of levels and in turn a level is composed of polygons 4 A Polygon node represents the idea of a contour loop which always closes upon it scl f and does not cross it self or any other contour Contour loops are approximated by a ring of vectors hence the term polygon The contour polygons alwayshave atleast three sides and are simply connected 5 Shape nodes contain data about one or two polygons The data in a shape node is not a positive representation of the notion of shape but is rather the parameters of alignment that must be normalized out before shapes can be compared 6 Vector nodes contain the locus of an image vertex however since vectors always belong to a polygon and always have two neighbors their counterclockwise neighbors considered to determine their vector direction 7 Arc nodes are vectors that are rnade by the polygon smoothing routine one arc typically replace several vectors When both arcs and vectors arc being discussed vectors arc strictly horizontal and vertical whereas arcs may point in any direction Empty nodes arc anartifact of the fixed node size dynamic storage allocation mechanisra Entities are made
51. ng perform conversions between two different kinds of images Nesting and contouring compute topological relationships within a given image representation In summary the major operations are MAJOR OPERATION 1 2 3 4 5 THRESHOLDING CONTOURING NESTING SMOOTHING COMPARING OPERAND 6 BIT IMAGE 1 BIT IMAGES VIC IMAGE VIC IMAGE IMAGE amp FILM RESULT 1 BIT IMAGES VIC IMAGE NESTED VIC IMAGE ARC IMAGE FILM Although the natural order of operations is sequential from image thresholding to image comparing in order to keep memory size down the first four steps are applied one intensity level at a time from the darkest cut to the lightest cut only nesting depends on this sequential cut order and comparing is applied to whole images The illustrations on pages 21 and 23 show an initial video image and its final smoothed contour image the illustrations immediately below and on page 24 the corresponding intermediate sawtoothed contour images The illustrated images are each composed of seven intensity levels and took 16 seconds and 13 seconds to compute respectively on a PDP 10 2usec memory The final CRE data structures contained 680 and 293 nodes respectives which comes to 2K and 4 5K words respectively the initial video image requires 10 2K words FIGURE PUMP SAW TOOTHED CONTOURS FIGURE 5 BLOCK SCENE VI DEO AND SMOOTH CONTOURS m vu m
52. nitials should be three characters or less the filename extension CRE is assummed and the usual PPPN defaults occur If the input succeeds INCRE returns a value T if the input fails INCRE returns a value NIL and prints one or the other of these two m ssages CRE FILE NOT FOUND CRE FILE REQUIRES 00000 MORE WORDS OF BINARY PROGRAM SPACE After a sucessful INCRE the film image level polygon arc and vector nodes are referred to by integer s usingthe 11 Link Fetch Subroutines CW nodeXCCW node DAD node SON nodeXENDO nodeXEXO node ALT nodeXNGON node PGON nodeXPTIME node film address is the integer 0 zero So that the expression SETQ V3 CCW CCW SON SON SON SON 0 will retrieve the lower right hand corner of the border polygon of the 1 level of the first image of the film The 13 CRE LSP datutn fetch subroutines are ROW nodeXCOL node nodeXRELOC node CNTRST nodeXNCNT ZDEPTH nodeXPERM nodeX AREA node nodeXMZZ nodeXPXY node 40 This 15 sample output from the Xerox Graphics Printer lee lt gt 080 0 123456789 4 lt gt 2 ABCDEFGHIJKLMN OPORSTUVWXYZIMI abcdefghijklmnopqrstuvwxyzilft This is sample output from the Xerox Graphics Printer lec 5A n Aoogc2nuV dee lt 675 0s9 0123456789 2 eABCDEFGHIJK LMNOPORSTUVWXYZI I abcde
53. oothing al gor thm on page XX BABYKILL Toggle flag which causes baby polygons those consisting of only one pixel to be killed CAMERA Select a different camera number CENTER Center al images It isequi val ent to the command app lied to each image and uses the same contro bi ts DDT Invoke DOT present return with oP AY Enable display DISPLAY Disabledisplay TVFONT spends siignif icant amount of time putting up the display EXIT Ex tto mon i ter Enable display of grid Grid is some multiple of pixel size dependen t on camera f ength It is useful of lining up characters GRIL Disab ledi ay of grid Displag help file HOLE Change a polygon into a hole KILARC Ki arcs vectors This al lows several degrees of smoothi ng to be tried in conjunction uith the ARCHID command 48 TVFONT S EXTENDED COMMANDS KICVIC Kil video intensity contours and replaces them with arcs MUNG Force al i vertices of current polygon or level onto pixel boundaries This has a permanent effect as opposed to cY command which only displays them that ORTHMUNG ORTHMUNG forces vertices which appear to be formright angles onto 1 boundaries This is attempt to counter the rounding effect of dek i nk i ng on sharp corners as are generated by reading a font POLYGON Change hole into a polygon POPJ Leave TTY loop Used
54. r world being looked at FI CURE 2 P INTRODUCTION Thesccond design choice of multi irnage anaylsis rather than single image analysis provides abasis for solving for camera positions and feature depths The third design choice solves rather avoids the problem of integrating an edge finders results into by using a very simple edge finder and by accepting all the edges found the image structure is never lost This design postpones the problem of interpreting photometric dges as physical edges The fourth choice is arcsolution to write an image processor that does not requirescperator assist ance or parameter tuning The fifth choice of the 216 by 288 fixed window sizeis a sin that proved surprisingly expedient it is explained later A variable window version of CRE athalves thirds and other simple fractions of its present window size will be made at sorne future date The final design choice of using machine language was for the sake of implementing node link cat a structures that are proccssed 100 faster than LEAP 10 times faster t han compiled 15 require significantly less memory than similar structures in either LISP or LEAP Furthermore machine code assembles and loads faster than higher level languages machine code can be extensively fixed and altered without recompiling is my impression that
55. t alittle in the direction northeast northwest sout hwcst or sout heast that bisects the turn s right angle The distance of dekink vernier positioning is always less than half a pixel but greater for brighter cuts and less for the darker cuts in order to preserve the nesting of contours The saw toothed and the dekinked versions of a polygon have the same number of vectors am very fond of t his dekinking algorithm because of its incredible efficiency given that you have a north south east west polygon trace routine which handles image coordinates packed row column into one accumulator word then dekinking requires only one more ADD instruction execution per vector s 3 NESTING The nesting problem is to decide whether one contour polygon is within another Although easy in the two polygon case solving the nesting of many polygons with respect to each other becomes n squared expensive in either compute time or in memory space The nesting solution CRE sacrifices memory for the sake of greater speed and requires a 31K array called the SKY CRE s accumulation of a properly nested tree of polygons depends on the order of threshold cutting going from dark to light For each polygon there are two nesting steps first the polygon is placed in the tree of nested polygons by the subroutine INTREE second the polygon is placed in the SKY array by the subroutine named INSKY The SKY array is 216 rows of 28
56. ting undesired polygons a font fi le can be made using Making and Outputing a Font File 8 Center al the images of the f i Im d HA Make font bit rasters 10 0 Output font file The X CENTER command i s an extend mode command and requ i res both hitting X and typing out the word CENTER fo 11 by a carr i age return The will cause bit raster to be made for interior portions of each image of the film if an image node does not have an associate ASCII code then the user wi be requested to supp one The 0 will ask for a font f i lename and wi output a font fi le in the Stanford Format Test i ng a neu Font F i l e I FILE FONT NEWFNT FNT XGP BGB The above monitor command wi print a FILE with a new font The user must specify his PPPN because the default is XGP SYS 44 TVF ONT COMMAND SUMMARY A ASSIGN ASCII CODE TO IMAGE EXPAND CONTRACT BY CONSTANT IN Y DIRECTION 6B EXPAND CONTRACT IN X DIRECTION cB SLANT CHARACTER 1 2 SLANTS 0 45 DEGREE ANGLE C MAKE THRESHOLD CUT MAKE POLYGON IMAGE QUT OF DI TREPRESENTATION OF FONT 0 ENABLE DISABLE DELETION OF BABY POLYGONS DEFAULTIS OFF F LOCATE NEAREST POINT F USE LIGHT PEN G LEVEL OF CORRESPONDING CHARACTER CODE li HISTOGRAM GH BI MODAL CUT TV PICTURE FROM DISK INPUT FILE
57. vertices of connected polygons OON a First the shape nodes of the polygons of an image are computed The shape node contains the center of mass and the lamina inertia tensor of a polygon The lamina inertia tensor of a polygon with N sides is computed by summation over N trapezoids The trapezoid corresponding to each side is formed by dropping perpendiculars up to the top of the image frame each such trapezoid consists of a rectangle ana right triangle since the sides of polygons are directed vectors the areas of the triangles and rectangles canbe arranged to take positive and negative values such that a summation will describe the interior region of the polygon as positive The equations necessary for computing the tensor of a polygon are collected in a table in the postscripts to this paper and were derived by using Goldstein s Classical Mechanics 1 as a reference The meaning of the inertia tensor is that it characterizes each polygon by arectangle of a certain length and width at a particular location and oriention and of further importance such inertia tensors can be added to characterize two or more polygons by a single rectangle It is the lamina inertia tensor rectangles that are actually compared by Second all the shapes of the polygons of one level of the first image are compared with all the shapes of the polygons of the corresponding level of the second image for nearly exact match Th
Download Pdf Manuals
Related Search