--- title: "Range Data Understanding Guided by a Junction Dictionary" authors: - "Kokichi Sugihara" - "Yoshiaki Shirai" doi: "" url: "https://ijcai.org/proceedings/1977/168" pdf: "https://ijcai.org/proceedings/1977/0168.pdf" venue: "Proceedings of the Fifth International Joint Conference on Artificial Intelligence" year: 1977 pages: "706--1" track: "Vision" keywords: --- # Range Data Understanding Guided by a Junction Dictionary Kokichi Sugihara, Yoshiaki Shirai *Proceedings of the Fifth International Joint Conference on Artificial Intelligence*, pages 706--1. ## Abstract ## Full text ## Introduction We propose a new approach to representing range data originated with real scenes by a collection of simple planar and/or curved objects. A rough sketch with obvious features is generated in the beginning and it is improved step by step according to the guidance by a junction dictionary. The dictionary predicts new features to be extracted until the perfect description is obtained. The dictionary also suggests how to partition the scene into simple bodies (Sugihara (1977)). Waltz (1972) and others have used similar junction knowledge to interpret a given line drawing. Their works, however, deal with perfect line drawings which are usually difficult to obtain from light intensity data. The present approach, on the other hand, is practical since noisy raw range data can be dealt with. ## Junction Dictionary It is assumed that the objects in the scene are solid bodies bounded by planar surfaces and/or curved surfaces of the second order and that exactly three faces meet at each vertex. Four kinds of labels are used to represent physical meanings of lines: a plus symbol for a convex edge whose both sides are visible, a minus symbol for a concave edge, an arrow for an occluding line and a dotted line with an arrow for an occluded line. Junctions are divided into two classes: the junctions which are possible in a picture of three-dimensional objects (possible junctions) and the others (impossible junctions). The junction dictionary is the directed graph. The nodes consist of the possible junctions and those impossible ones which can be made possible by adding new lines to them. A branch exists from a junction to another if the latter can be obtained by adding a new line to the former. For example, two branches ((a),(b)) and ((a), (c)) exist among the junctions (a), (b) and (c) in Fig.l. Each branch tells us the type and the orientation of the associated new line. Directed paths starting with a junction (which may or may not be possible) and ending with possible junctions suggest where and what types of lines we should search for to improve the present description. If the present description contains the junction (a), the paths (length-one paths) suggest either a convex line in the upper fan-shaped area (b) or a concave line in the opposite area (c). A new line 'must' exist since the junction (a) is impossible. Some junctions are possible only when two or more bodies are put together in the scene. Those junctions are used as cues to partition the scene into several bodies. To enumerate possible junctions .the curved line-segments are replaced by the half lines tangent to the curves at the junctions. ![Image](https://ijcai.org/proceedings/1977/fulltext/168/image_000000_60ecb648e3ae13059d6ed1f5ca9510b39b8a95a1d2fa6595491c041fc4b080ac.png) This convention prevents our dictionary from swelling. ## Dictionary-Guided Scene Analysis Fig.2 shows a light stripe image (from which the range data are calculated by triangulation), Fig.3 shows a rough description generated on the way of scene analysis and Fig.4 gives the final description. The system first extracts contours (strings of range-jump points) and junctions (curvature-maximal points) on them. Starting with those junctions new lines are searched for according to the suggestion by the dictionary. When a new line is found, it is followed until . it terminates (the lines JlJ2 and J3J4 in Fig.3) and new junctions on it are also found (the junction JS). The body is partitioned into simpler ones whenever it is possible. (The concave lines JlJ2 and J3J5J4 and the junctions along them suggest body partitioning.) The line extraction is finished when all junctions have grown possible and no more lines can be found (Fig.4). ## Conclusion Knowledge about the object world is condensed into the dictionary and it is used as a guide for scene analysis. This approach seems prom1s1ng because 1) the guidance by the dictionary assures the efficient and reliable feature extraction system and 2) objects are not limited to a few prototypes. ## Reference s Sugihara, Based on 1977. K.: Dictionary-Guided Scene Analysis Depth Information, PIPS-R-No.l3, ETL, Waltz, D.L.: Generating Semantic Descriptions from Drawings of Scenes with Shadows, AI-TR-271, MIT, 1972.