--- title: "Finding Picture Edges through Collinearity of Feature Points" authors: - "Frank O'Gorman" - "M. B. Clowes" doi: "" url: "https://ijcai.org/proceedings/1973/68" pdf: "https://ijcai.org/proceedings/1973/0068.pdf" venue: "Proceedings of the Third International Joint Conference on Artificial Intelligence" year: 1973 pages: "543-554" track: "Computer Vision" keywords: --- # Finding Picture Edges through Collinearity of Feature Points Frank O'Gorman, M. B. Clowes *Proceedings of the Third International Joint Conference on Artificial Intelligence*, pages 543-554. ## Abstract The recovery o f straight ~icture edges from digitisations of scenes containing ~oly hedra ( ' line finding ' ) is central to the functioning of scene analysis ~rograms . While recognising that recovery ~ro~erly involves a com~utational mobilisation of a great deal of knowledge - su~ported context , there remain some basic issues of re~resent ation whi ch govern th e way in which the primary data - grey lev~ls - are addressed . Th e ~a~er describes a ~arametric re~resenta tion of straight ~icture edges and its ~ro cedural de ~ loyment in the recovery of edges from digitisations of scenes whose contents are essentially ~olyhedra with strong visible shadows. ## Full text ## FINDING PICTURE EDGES THROUGH COLLINEARITY OF FEATURE POINTS ![Image](https://ijcai.org/proceedings/1973/fulltext/68/image_000000_1a5456145c149cdefc9f2a5b31fb7393b20756f65f3bb1e12185795c34ec258b.png) F . 0 1Gorman and M. B. Clowes Laboratory of Ex~erimental Psychology University of Sussex Brighton, Sussex , Engl and reformulate a~~roaches to scene analysis as integrated or 'heterarchical' (as e~~osed to 'hierarchical ' ~ass- oriented schemes) there remains a clear reQuirement for ~rocedures which are ca~able - with or without context - of recovering three- dimensionally significant entities in the ~rimary picture data . One recent attem~t to mobilise context to assist a line finder is described by Shiraia · After an initial · ~ass ' to recover an outer contour of the grou~ (or grou~s) of objects visible in the scene , the l ine finder is directed to significant locations e . g . con­ cavities , in this contour as the origin of a search for further edges . Heuristics of various sorts e . g . ' look for an edge ~aralle l to one a l ready found ' are used to furthe r constrain the direction of the search. The search itself ~roceeds from the immediate vicinity of that location . Ins~ection of ty~ical scenes suggests that at many such locations on an edge , the evidence may be meagre although elsewhere a l ong its length the evidence is much stronger . Thus a search initiated by a ~rogram such as Shirai ' s may fail because it has a very myo~ic way of addressing the ~icture s~ace to find edges . This ~a~er is concerned ~rimarily with a study of an alternative to this local search strategy , by ex~loiting the col linearit y of the feature ~oints making u~ a straight ~icture edge as an addressing mechanism . The ex~loitation of this ~ro~erty to find straight l ines is not in itself original . Both Duda and Hart 4 and Griffith 6 describe a parameterisation of feature-~oint data which is of assistance in recovering straight l ines. Indeed our own work derives directly from that of Duda and Hart . These earlier workers however leave many ~roblems unresolved (e . g . Duda and Hart ~ . 13 col . 2) not least of which is the nature of the methods by which the parameterised data is to be concatenated into lines . The study which we have carried out provides a fresh ~erspective from which to view the ' myo~ia ' of l ine finders and gives at the same time a more detailed picture of the difficul ties that remain. ## 2 . ## The Line Finding Process ## 2 . 1. The Data . The data with which we have worked derive f r om ~ositive photogra~hs of scenes l tt by a single l ight source . Our ~rimary concern is with scenes involving the ~u~~et figure which is ~ainted a uniform matt grey , although we have done some work on matt white ~oly­ hedral blocks . The ~hotograph is digitised by a flying spot scanne~ with a linear +we are grateful to Dr . J . R.Parks of the Nat ­ ional Physical Laboratory for making this scanner aval~abie to us . ## Abstract The recovery of straight ~icture edges from digitisations of scenes containing ~oly­ hedra ( ' line finding ' ) is central to the functioning of scene analysis ~rograms . While recognising that recovery ~ro~erly involves a com~utational mobilisation of a great deal of knowledge- su~ported context , there remain some basic issues of re~resent­ ation which govern the way in which the primary data - grey lev~ls - are addressed . The ~a~er describes a ~arametric re~resenta­ tion of straight ~icture edges and its ~rocedural de~loyment in the recovery of edges from digitisations of scenes whose contents are essentially ~olyhedra with strong visible shadows . l. ## Scene Analysis Contem~orary thinking in scene analysis is focussed ~rimarily u~on efforts to de~loy higher level knowledge , e.g . of su~~ort , lighting and scene com~osition~ to achieve an ·integrated ' inter~retation of ~ictures in the form of grey scal e data from TV cameras or com~arable ~icture digitisers . The need to involve such knowledge has become ~rogress­ ively more a~~arent as line and region finders:LO , 5 · 2 , :1. have demonstrated that a ~ass- oriented a~proach to the recovery of edges and surfaces is only ~artially success­ ful. Our own studies are focussed ~rimarily u~on this same endeavour : a crucial feature of our research is the formulation of a task in which there is a rich but ho~efully tractable range of knowledge which could be mobilised in such an integ~ated analysis. The task had its origins in · ~art in the dictum we attribute to Guzman 7 ' if you recognize a foot you know where (in the ~icture) to look for a leg ·.··.· ' The scenes we are working on are ~olyhedral in content but ~olyhedra constrained to form a ~up~et figure (Fig.l ) In so doing we ho~e to bring to bear. just that sense of context which Guzman evokes , in order to assist the ~races­ sing of some picture or scene fragment . Contem~orary ~rograms e . g . Falk 5 do just this but wi thin the restriction that context can only be mobilised to hel~ in identifying the elements of a single body (of which Falk has 9 distinct models) exce~t for the contextual inferences ~rovided by the reQuir­ ement that bodies be sim~ly su~~orted . Winston ' s account :1. 2 of Fin:i.n · s work goes beyond Falk in ~recisely the direction we have adumbrated although it is unclear what range of architectures is being contem~lated beyond the ·arch ' he describes . Notwithstanding these attem~ts to response to reflected light quantised into 64 grey l eve ls . I n practice the range is about 40 grey levels . Inspection of the digitisations reveals that over perceptually uniform regions of the picture the variation in grey level be tween adjacent picture points ( ·noise ·) increases approximately linearly with average grey level to an extent (about 4 units peak- peak at a grey level of 40) which becomes a nuisance in computing the bright­ ness differential within the bright areas of the picture . We have not attempted to identify the source of this ·noise · nor the extent to which it originates in the photo­ multiplier system or in the photographic process . ## 2 . 2 . Mappingthe data into r , a space . As indicated in Section I we wish to use the 'global' collinearity of feature points as a major factor in recovering straight picture edges rather than their contiguity . Following Duda and Hart 4 we capture this property by using a variant of the so- called Hough transformation . A straight picture edge is treated as line in the picture plane , parameterized by a the orientation of , and r the length of the normal f r om the origin to the l ine . The equation of the line is then A line is thus completely specified (except for its extent - an important consideration in the present task) by a (r , a) pair . A point (x , y) in the picture plane may be thought of as the common point of intersect ­ ion of a family of lines , each membe r of this fami ly having an orientation a in the range (0,180°) and a value of r determined by (1) . A point therefore corresponds to a family of (r , a) pairs . A set of collinear points in the two- dimensional space of the picture has a se t of line families with a common (r , a) member . The basic principle of the technique described by Duda and Hart 4 and related methods such as the so- calledHough trans­ formation is to accumulate evidence for such common members by mapping picture points into (r , a) space . The p icture edges of interest are associated with local changes in picture brightness (feature points) and thus the points which form these edges are (x,y) locations in the picture where thegradient G of the picture brightness significantly exceeds the value s of G associated with locations in uniform areas of the picture . We can compute G at the location (m, n) by obtaining a measure of the gradient in the x and y directions (DXmn 'DYmn) as estimated from a 3 x 3 grid centered on (m , n) : The magnitude of G takes the form ![Image](https://ijcai.org/proceedings/1973/fulltext/68/image_000001_ee418df51a066ca50b375d69109dd3fdab0790f1a2b15d080b7369dc6500177a.png) Where ![Image](https://ijcai.org/proceedings/1973/fulltext/68/image_000002_111f921b1d7d032b58de993e748dd6417c028c3681abeab1f0c24a75b5dc3908.png) The term Smn is a scale factor which reduces the magnitude of G for brighter picture points to combat the noise (described earlier) encountered in bright areas of the picture . In the pictures we have studied well over 75% of the picture locat ions give effec­ tively zero values for G as can be seen by imposing a threshold wh ich eliminates these points . The result displayed two- dimensionauy (Fig . 2) contains most of the picture edges of interest . It is only the values of G for these locations that are used in the recovery of picture edges . The threshold is a fixed one which can be regarded as a constant in , the picture- taking and picture- digitising process . For each picture location so identified we could compute the family of r , a pairs it determines and begi n to accumulate evidence by incrementing the appropriate counters in a t wo dimensional array , where each count e r will record the number of locations giving rise to a value of r , a lying within the range appropr­ iate to that counter , a range Dr , Da which is determined by the quantisation we impose on the r , a space . We departfrom this me thod of accumulating evidence (the method described by Duda and Hart 4 ) in two important respects. Firstly by making use of local evidence to determine uniquely the value of a . This local evidence can be derived from the ratio DX;j) which gives the direction in which the graaient lies . Since the gradient should be perpendicular to the picture edge a is given by There is of course a risk that this estimation will be imprecise especially for example at junctions between contiguous p icture edges , but much of the uncertainty arises for picture points where the value of G is low, which we have already excluded from consideration by thresholding G. That these local estimates are consistent and reasonably reliable may be j udged from Fig. 2 , which displays the direction of G at each of the points whe re G exceeds threshold . If a , x and y are all known then r is determined, it can however be computed in two ways g iven that a is going to bequantised . That is , r can be computed either directly from the value of a given by (6) or after that value has been quantised . The two alternatives give the r,a counters differing geome trical fields of view: we shall not pursue this po int of detail here save to say that wB have adopted the second approach , namely we quantise a before comput­ ing r . The quantisation steps used are Da=l0° and Dr=3 picture rows (columns) . The second point of departure r e lative w the method of Duda and Hart4 is to increment the counter by the magnitude of G rather than by 'one for each contributing picture location. Our motivation in so doing is to ensure that we readily find st r ong picture edges (at the risk to be sure of masking weak ones) and to ensure that those counters for which a is accurately computed from the local evidence (because G is large) are emphasised . The resulting histogram H(r,a) for the digitisation of Fig . l is given in Fig . 3 . The origin of coordinates is in the centre of the picture (Row 133 , Column 1 29 of Fig . 2) , it i s t h is point from which r is measured . I n the purely algebraic interpretation of the trans­ formation a ranges between 0° and 180°; the method of computing a from the local evidence yields values which range between 0° and 360° since we wish to distinguish which side of the pictur e edge is the darker . Thus for a given orientation of the picture edge there are two possible values of a corresponding to one or other side being the darker . We have labelled the a axis of the histogram according to the convention for displaying a used in Fig . 2 as wel l as in the more conventional wa~ so that it is possible to pick out correspon­ dences between peaks in the histogram with bands of picture points in Fig . 2 . When one does this e . g . for the bin r = 72 , a = 180° (identifier ' I ' ) corresponding to the shadow of the puppet ' s shoulders , we immediately grasp the fact that the bin in no sense represents the lines we see in Fig . 2 . For t h is bin contains both these picture edges although they a r e not joined , because their constitutent picture locations have the same r , a values associated with them: they are collinear . The quantisation also has its effect too in dividing a singl e edge between adjacent histogram bins ; for example the points forming the lowe r edge of the leg shadow in Fig. 2 do not all have the same orientation and are therefore allocated to different histogram bins . Elsewhere in the picture parallel edges which are close toge­ ther have been allocated to the same bin . The latter two defects can be exposed more readily if we consider the locations contri­ buting to each histogram bin . For convenienE let us restrict attention to only those bins of Fig . 3 whose magnitude exceeds 5 . We can now assign an identifier , chosen again from the character set of the l~ne printer , to each bin and display in the t wo- dimensional format of Fig . 2 the locations which belong to each of these major bins . The result (Fig . 4) illustrates the points we have been making only too well . At the same time the lists of cont ributing points for each bin, referred to hereafter as the cont ributing points list(cp~, provides a basis for surmounting the first 1 two problems posed by the (r , a) transformati~ The data structure we r efe r to as the histo­ g ram H(r , a) contains for each bin a list (the c pl) of the (x, y) locations contributing to that bin as well as the summed magnitude H of the contributions of those locations . ## 2 . 3 . Recovering straight lines from the r , a histogram . The recovery of bounded straight lines from the histogram centres upon a process - at this stage full of crude rather ad hoc devices - of recovering sub- sets of the locations contributing to the histogram : subsets which correspond as closely as possi­ ble with the lines we would sketch in on Fig . l . The starting point for the search is a cpl from a major bin. The method is ite r a ­ tive : search for a new line a l ways begins with the largest bin remaining in the histo­ gram, and search terminates when no bin exceeds the arbitrary value of 5 . These subsets which we shall call putative line lists (pll) , are recovered in a series of steps . 2 . 3 . 1 . Recovery of putative line lists . The cpl of the largest bin in the histogram is taken as a basis for forming a pll. A list of the points in the cpl is made , ordeffd on either x value (for a<45° or <:~,>135°) or y value ( 45° < a< 135°) . This list is now scanned from one end wi th a view to finding other cpl ' s containing points which contribute to the edge . For each point in the list we compute G, a for those neighbours of the point which are not already in the list . By neigh­ bours of a point we mean the eight locat ions which immediately bound the point . For each ot those neighbours having a G above threshold and a value of a not more than 10° different from that of the initial c pl , the cpl contai­ ning each such neighbour is merged into the list and the scan is resumed . During this s·can gaps in the list are tested for . A gap occurs when the next po int on the list has an x value (if the list is ordered on x) or y valu e (if the list is order~d on y) which differs from thatof the current point by more than some constant which at present is set at l unit . I f a gap is found then the points in the l ist beyond the gap are assumed to be from a different , collinear , edge , and a re discarded . Since this scan adds c pl's to the list the beginning of the list may have been ex­ tended, and it is possible that this extension contains gaps . It is therefore necessary to scan the list again in the r everse direction looking for a gap . As before , points (if any) beyond the first gap found are discarded . The points remaining in the list after these two scans are the required pll. They are r emoved from the appropriate cpl's of the histogram and the value of H for each cpl decremented accordingly . Recovery of pll ' s then continues with the cpl from the new largest bin in the histogram as a basis . The recovery process is terminated when there a r e no bins left with magnitude greater than 5 . The set of pll's extracted from t he digitisation of Fig . l and the histogram of Fig . 3 is illustrated in Fig . 5 , again using a unique (new) identifier for each pll · 2 . 3 . 2 . Converting putative line lists into lines . The ordered list of points emerging from the procedure described above is subjected to two tests to determine its acceptability . It s · strength' is assessed by summing the values of G for the points contained in the list . If their summed value is l ess than 2, the pll is rejected . The next step is to fit a line to the point s of the pll using a least squares approximation with each point we i ghted by its G value . The quantisat ion on r sometimes causes points ~rom adj a c ent paralle l edges to ~all into the same b i n . The algorithm ~or recovering pl l ' s cannot at present handle this situation and produces a single pll ~or the edges . Such pl l ' s can be detected ~rom the large spr ead o~ po int s about the ~itted line . The measure used ~or this is the variance o~ the pe r pendicular distances o~ the points ~rom the l ine . Whereas [:: G is d t . t pll use o reJec a pll , the va l ue o~ the variance computed is not , since the pll and t he line ~itted a re structurally signi~icant objects which other programs can be expected to make use o~ . The accepted pll ' s now have to be assigned end points . The technique involved ~irst reorde rs the points o~ the pll in the direction o~ the line ~itted to them , i . e . orde rs them according to their perpendicular distance ~rom a normal to the line . The extremum points o~ this list are not usually very good c and idates as end point s ; the lism tend to have tails with ext r emum po int s some distance o~~ the ~itted line . The method adopted i s to scan the list noting on which side o~ this line the points lie , until the ~irst cross- over is n oted . This cross- over po int approximates to the intersection o~ the line with a boundary around the set o~ poi nts, and is taken as the endpoint . The procedu re is r epeated at the other end o~ the list . The l ine segments superimposed on the pll ' s in Fig. 5 we r e obtained ~rom those pll ' s by the above method . Fig. 6 i s a plot o~ the same lines produced using the GROATS graphical system 8 ; ~or ease o~ inspection lines whose variance exc eeds 10 units are shown dotted . Results ~or other pictures of t his same type , using the same parameter se t tings , are illus­ trated in F ig. 7 . 2 . 3 . 3 . Program details . The prog ram woo implemented in Algol 68R 3 on an ICL 1 90 6A, and uses 35- 45K of core memory . The proce ss ing time depends on the complexity of the pictureq and varies f rom about 30 seconds for simple b l ocks scenes to about 90 seconds for the more complicated puppet p ictures . ## Results Pe r haps the most obvious question to ask of this line finde r i s 'does it work?' Unfortunat ely such a Question can only be answe red r e lative to the success or fai lure achieved in using the line data fo r some recognition or interpretation task . At the time.no such evaluation has been a ttempted ; t he 1nterpretation routines simply do not exist . Howeve r, we c an adopt the requiremenffi that some reported scene analysis system would appear to impose u pon its line finder , and assess performanc e on that basis . A good c andidate is Shirai ' s programi:!. since the con t ext free phase of line finding is rather well defined in that progr am, be i ng aimed at the recovery of the s cene contour . That is the set of ·outer · edges of the object or g roup of ove rlapp ing objects visible in the s c ene . The pictures vre are wor king with , unlike those used by Shirai , contain substan­ tial areas of visible shadow which can be regar ded as augmenting this contour , for exampl e the lines in Fig . 6 numbered 1 , 36 , 19 , 1 6 , 1 7 , 9 , 24 .··..·· I gnoring internal contours . (e . g . 27 , 22 , 20 in l<'ig. 6) we can form a s1mple numerical measure o~ success by c omparing the number of picture edges in the outer contour estimated by eye for the data with the numb e r of these edges appearing as ' lines in the output data . I n Table 1 these c ount s are listed for f ive scenes . | Scene No . | Number of contour picture edges in s c ene .• | Numbe r of corre s - ponding l ines in output . | |----------------------|-------------------------------------------------|---------------------------------------------------| | 211 21 2 214 217 225 | 25 24 28 25 29 | 17 14 19 23 17 | ## Table 1 . The results suggest - relative to Shirai who apparently never fails to recover the c omplete outline - a r ather disappo i nting performance . There is however a major di~ference between the data ~or the two line finders namely that Shirai was working with matt white blocks on a black velvet support plane whe reas we are work ing with matt grey pol yhedra (the puppet) on a matt white support plane . Moreover the optical quality espec­ ially focus of some of our photographs is much i nfe rior to that o~ Shirai (our scenes ext end over a greater spat i a l extent) . Thus our worst cases 212 , 225, s~~er ~rom very badly de~ocussed shadows whe r e many outline picture edges are missed . A more ~ragmentary analysis o~ pe r formaxe can be given by looking at some well- defined mistakes . Speci~ically a number of picture edges are missed due to design de~ects o~ the algo~ i~hm which are potentiall y easily rect1~1ed . We can identify three main causes for missing (or mis- positioning) a picture edge . - (a ) Edges whi ch are short and/or lacking in cont rast . The vast bulk of missed edges fall into this category . For example the edge comple ting the top of the puppe t ' s head in Fig . l (the miss ing line j oining the junction of 1 6 and 17 with the junction of 9 and 24 in Fig . 6) . rhis is clearly visible i n the differentiated data (F ig. 2) its magnitude however is too low for the histogram bin ( r = +57 , a = 130° ) to excee~ critical t hreshol d for line ~inding , so that 1t never appears in the cpl · s for this data (Fig. 4) . - (b) A similar case of considerable interest because of its potential value in any 3-D interpre t a tion of the data, occurs as part of 'TEE junction· formed by the occlusion of the trunk shadow by the nearer · arm ' in Fig . l . Two o~ the edges - l i nes 13 and 18 in Fig . 6 - a re r ecovered; the third is cle arly v isible in the differentiation Fig . 2 and at ~irst sight it seems odd that it doe ~ not get picked up as part o~ 18. The reason is that these, the two collinear pieces o~ the 1 TEE ', are o~ opposed contrast as close inspection o~ Fig.2 shows . (u = 'X','Y' ~or line 18; but u = 1 F 1 , 1 G 1 for the missing edge) , this interesting ~ragment is thus ·on its own ' and ~ails to exceed the H = 5 threshold . This case, and there are quite a lot more , points t o an intrinsic de~ect in distinguishing between (u) and (u 2:180°) i n recovering edges : but to discard the distinction in accumulating H (r , u) would undoubtedly degrade the quality o~ the histo­ g ram data . What seems more relevant is to modi~y the criterion for merging cpl's to ~orm pll's so that the permitted variation in u becomes u new u orig :t. 10° or u new The e~~ect o~ such a change in the restriction on ·acceptable u · would be to accommodate a particular way in which an edge stops ·.·.··· because it has reversed its contrast . (c) Yet another edge in Fig.l which appears quite clearly in the di~~erentiated picture (Fig.2) is the lower (supported) edge o~ the puppet ' s l eg . (The missing line between 25 and 35 in Fig.6). Here the problem is not immediately one o~ low contra~ although it is very weak , as close inspection of G and u (Fig .8) shows, ~or there are su~~icient points to secur e a value o~ H exceeding the criterial value o~ 5 as is evidenced by the presence o~ at least one substantial cpl (identi~ier 1 8 1 ) in Fig.9. The listing o~ pll's in Fig.9 provides an explanation ~or this loss: some 15 out o~ the 53 members o~ cpl '8 ' in Fig.9 are · stolen · by other pll's during the merger o~ cpl ·s. Typically the pll which eventually eme r ges as line 25 in Fig. 6 acquir~s some o~ them, (they contribute a small error i n positioning o~ the ~itted line 25) and does so at an early stage . The residual cpl is then progressiveJ;y dismembered (starting at the 'hip joint·) into small sub- critical pll's ( 'D', '9', '8 ', '7' , etc . in Fig.9) which r emain small precisely because the requirement ~or strict picture adjacency cannot be met . Eventually the original cpl is eroded until its histogram magnitude is less than 5 at which point it drops out altogether . This is why the sizeable group of 1 8 1 s 1 in Fig . 9 near the ~eet neve r appear as pll ' s . A major part o~ this problem can be traced to the myopic nature o~ the line­ ~ollowing criteria, more generally perhaps to the ~ormulation o~ the task o~ assessing the continuity o~ a picture edge, as a serial search o~ sequentially ordered points . This would in ~act have been success~l ~or this picture edge had the search commenced ~rom the other end o~ the cpl i. e . the '8's' near the ~eet in Fig.9. But a deeper issue is at stake here in deciding just how appropriate a connectivity search is when a set o~ contribu­ ting points is available . We r eturn to this topic in the next section . The use o~ the connectedness criterion is not helped more­ over by the 'capture ' o~ picture locations by mergers with strong neighbouring edges (in this case the edge represented by line 25 in Fig. 6) , a process whi ch punches additional holes into the already straggly string o~ l ocations . A much more dramatic case o~ this 'poaching' can be seen ~or scene 214 (Fig . ?) where the low con~idence l ine 22 has captured the larger part o~ the picture edge marked by line 8 with the result that two picture edges are e~~ectively missed . The problem here stems ~rom the pass- oriented character o~ the algorithm, line 22 being apparently a big peak in H(r,u) is ~armed early on and acquires through merger with a picture-adjacent cpl a substantial subset o~ the c pl which properly belongs to line 8 . When the peak in H(r,u) ~or line 8 is eventually considered, the points which 'right~lly' belong to it have been removed. The remedy here seems to lie - like the contrast reversal probl em - in modi~ing the criteria ~or gap acceptance. Specifically it would seem possible to extend adjacency tests to include relevant pll's already ~armed (e . g . the pll ~or line 22 in scene 214) although the decision mechanism to resolve 'disputed ' data is unclear at this stage. It might be su~ficient to return ambiguous analyses or to ~lag pll ' s with a 'disputed ' marker . 4. ## Discussion. The account in the previous section gives a partial· analysis o~ per~ormance and weakness o~ the a l gorithm. It is by no means exhaustive Perhaps the best way to assess the technique is not solely· in terms o~ lines recovered and missed . Rather it is t ·o see how its method o~ addressing the picture data di~~ers ~rom that o~ other techniques. Duda and Hart 4 discuss the efficiency o~ parameter~ isation methods of this general type by contrasting it with a me thod based upon ~itting lines to all possible pairs o~ ~eature points . This, as inspection o~ Fig.2 suggests, is quite prohibitive and can hardly be considered as a serious candidate . Rather the c omparison should be with line ~ollowers such as that described by Horn 9 · In the so-called 1 Bin~ord-Horn line ~inder· , ~eature points derived ~rom an edge- marker due to Bin~ord are ~armed into lists on the basis o~ proximity and agreement o~ attributes such as the direction (u) and magnitude (G) of the intensity step . The crucial characteristic o~ the procedure is that it ~allows or tracks along ~eature points because it is using picture adjacency as the method o~ add r essing possible new members o~ the list. In the method we have described, the addressing scheme is in e~fect inverted since it is proximity in (r , u) space which is used to ~orm the contributing points lists rather than proximity in (x , y) space . 0~ course we then have to add the spatial proximity requi~ ment which in its current ~orm is a simple adjacency test (Section 2) corresponding to the test on u and G applied a~ter spatial proximity in the Bin~ord-Horn approach . At this point our process becomes a line ~ollowe~ · but with the di~~erence that the points it addresses belong to lists o~ locations o~ the same (r , u) . It is clear that the adjacency criterion we have adopted makes it a very crude edge- fol lower . There are basically two things one is trying to do with the cpl in its simple form or its form as augmented by other cpl·s merged due to proximity in (r,u) space or (x,y) space . The first is to find the end points of edges . At present we do this by examining the list. However most interesting picture edges end in junctions. Thus the fact that an edge terminates usually if not always implies that another edge is 'pointing · at that termination point . Thus many ·gaps ' perhaps a majority could be marked not f rom a consideration of the edge cpl per se but from a cons ide ration of ·neighbouring ' (in some sense) cpl ' s . I n Horn's paper he describes a phase which we have not yet studied called ·concocting vertices· . This phase follows on f rom the formation of bounded lines to represent recovered edges : the proposal sketched informally above would in the context of the Binford-Horn line finder amount to a merge of two processes (line fitting and vertex concoction) which are at present sequential . The procedures for carrying this out in the r,u parameterisation have not been detailed as yet . The second objective in processing a significant cpl is to ascertain whether the picture locations which lie in the ·mark' as against the ' space ' be tween gaps , satisfy some criterion of 'edge- ness · realised in the present program by strict sequentially­ addressable picture contiguity . Perhaps less search-dominated criterion would be simply to assess the spatial density of points on the cpl in the putative ·mark ' between gaps . Again we have not pursued this notion to the point of programming it . The crucial question is that of deciding how much work should be done on attempting to remedy some of these defects - perhaps along the l ines suggested - as against accepting the existing performance and leaving other routines to remedy these omissions and error~ Our current preference and intention lies almost wholely in the latter direction. ## Acknowledgements We are grateful to Alan Mackworth and John Francis for discussions and especially for suggesting the use of locally-comput ed values of a in forming the histogram and to John Francis who i mplemented an early version of that suggestion . We are grateful to both Alan Mackworth and Stuart Sutherland for comments on the dr aft of this paper. The research is part of a project supported by the Science Research Council . ## References 1. Barrow , H. G. and Popplestone , R. J . ( 1 971) . Relational Descriptions in Picture processing . Machine Int elligence , § , 377- 396 . 2. Brice , C . R. and Fennema , C. L . (l970) . Scene Analysis Using Regions , Artificial I ntelligence , l , 3 , 205-226 . 3. Currie , I.F., Bond , S . G., and Morison , J . D. (1971 ) . Algol 68 -R in Algol 68 Imple mentat - ion, J .E . L . P eck (Ed) pp . 2l-34 , No rth Holland . 4. Duda , R. O., and Hart P . E . ( 1 972) . Use of the Hough Transformation to De tect Lines and Curves in Pictures . Communications of the A. C.M. 12, l , 11-1 5 . 5. Falk , G. (1972) . Interpretation of impe~t line data as a three-dimensional sce ne . Artif icial Intelligence, } , 2 . 101-144 . 6. Griffith , A. K. (1970) . Computer Recog- nition of Prismatic Solids , Ph . D. the sis , Project MAC , MIT . 7. Guzman, A. (1971 ) . Analysis of Curved Line Drawings Using Context and Global Info r ma- tion , Machine Intelligence , £. 325-376 . 8. Hopgood , F . R.A. (1969) . GROATS, A Graphic Output System for Atlas using the SC4020 , Proceedings 8th UAIDE Conferenc e , San Diego . 9. Horn, B. K. P . (1971 ) . The Binford-Horn Line Finder . Vi sion Flash 16 . Artificial Intelligence Laboratory, MIT . 10. Roberts , L.G. (1965) . Machine Perception of Three -dimensional Solids in Optic al and Electro-o tical Information Processin , Tippett et al Eds pp .l59-l97 , Cambridge , MIT Pres s . 11. Sh irai , Y. ( 1 972) . A H e terarchi~al Prog ram for Recognition of Polyhedra . Memo No . 263 . Artific ial I ntelligence Laboratory , MIT . 12. Winston , P . H. (1972) . The MIT Robot , Machine Intelligence , 1 , 43l-463 .