Edge Finding, Segmentation Of Edges And Recognition Of Complex Objects
Proceedings of the Fourth International Joint Conference on Artificial Intelligence. Visual Information Processing. Pages 674-680.
© 1975 International Joint Conferences on Artificial Intelligence
Abstract
This paper describes an approach to the recognition of real-world objects such as books or a telephone on a desk. The system consists of (1) edge finding process which extracts edges of curved objects from light intensity data, (2) segmentation of the edges into straight lines or elliptic cur ves, (3) recognition of objects by mat ching the lines to the models, and (4) simple supervisor. The modu le (1), ( 2 ) and (3) interact with each othe r thr o ugh a simple supervisor so that the system can locate given objects quickly. First, most reliable edges are found and segmented, and then recognition i s attempted using segmented lines. If recogniti on is not successful, less reliable edges are searched for, and recognition is retried. An example of l oc ating a lamp, a book stand and a telephone is sho wn.
- Winston, P. The IHT robot. Machine Intelli- gence I (1972).
- Shirai, Y. A Context Sensitive Line Finder for Recognition of Polyhedra. Artificial Intelligence 4 (2) (1973).
- Falk, G. Tnter~retati on of Imperfect Line Data as a Three-Dimensional Scene . Artificial Intelligence 3 (2) (1972).
- Perkins, W. and Binford, '!'. A Corner F'inrl e r for Visual Feedback. Computer Graphics and Image Processing 2 (3/4) (1971).
- Grape, G. Model Based (Inte rmediate-Level) Computer Vision. Artifici al Intelligen~e Project Memo No. 201 , Stanford Universi.Ly, Stanford, Calif. (1970).
- Agin, G. and Binford, T. Computer Description of Curved Objects, Proc. 3rd In ter n . . Taint Conf. on Artificial Intelligence (August, 1973) 0 IJCAI
- Nevatia, R. and Binford, T. Structured Description of Complex Objects. ibid.
- Oshima, M. and Shirai, Y. Representation of Curved Objects Using Three-Dimensional Information. Second USA-Japan Computer Conf . Proc. (August, 1975).
- Garvey, T. and Tenenbaum, J. On the Automatic Generation of Programs for Locating Office Scenes. Proc. 2nd Intern. Joint Conf. on Pattern Recognition. (August, 1974).
- Preparata, F. and Kay, S. An Approach to Artificial Nonsymbolic Cognition. Information Science 4 (3) (1972).
- Yakimovsky, Y. and Feldman, J. A Semantic Based Decision Theory Re gion Analyzer. Proc. 3rd Intern. Joint Conf. on Artificial Intelligence. (August, 197 3) .
- Prewitt, J. Obje ct Enhancement and Ex- traction. Picture Processing and Psycho- pictorics, Academic Press, New York (1970).
- Rosenfeld, A., Thurston, M. and Lee, Y. Edge and Curve Dete ction: Futher Expe rimen ts. IEEE Trans. on Computers, C-20 (5) (1971).
- Shirai, Y. A Step toward Context Sensitive Recognition of Irregular Objects. Computer Graphics and Image Processing 2 (3/4) (1973).
- Tsuji, S. and Fujiwara, R. Linguisti c Segmentation of Scenes into Regions. Proc. 2nd Joint Conf. on Pattern Recognition . (August, 1974).
- Hueckel, M. An Operator Which Locates Edges in Digitized Pictures. J. ACM 18 (1) (1971).
- Pavlidis, T. and Horowitz, S. L. Segmentation of Plane Curves. IEEE Trans. on Computers, C-23 (8) (1974).
- Braess, D. D. Chebyshev Approximation by Spline Functions with Free Knots. Numer. Math. 17, (1971), 357-366. -- 19 .
- Honma, H. and Kasuya, N. Dimensional Analysis Method of Least Squares and Experimental Formula. Lectures on Applied Mathematics 5, Corona Publishing Co ., Tokyo (1969) (in Japa- nese).
- Tamura, K. Maximal Isomorphic Subgraphs between Two Graphs. Bul. Electrotech. Lab., 37 (9) (1973) (in Japanese).
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1. INTRODUCTION
This paper describes an approach to the rec ognition of real-world objects such as books·or a telephone on a desk. Scene analysis could be divided into two modules : (1) extraction of featur es and (2) recognition of objects based on the features. It is often pointed out that the two modules should not be simply connected serially, but should interact with each other t.o achieve reliable recognition (1].
The author made an attempt to recognize polyhedra by those two modules i.e. a line finder and a line proposer (2]. There have been many works on model-driven recognition of polyhedra (3, 4,5]. However, it is not easy to make these two modules capable of recognizing curved objects. The difficult problem is to determine what features are useful for recognition and how to interprete the extracted features.
There have been some works on description of curved objects using range data (6,7,8]. Garvey and ~enenbaum [9] made an experiment for locating objects in office scenes using range and color data. The work presented here uses only light intensity data, because it can easily be obtained and stored, which makes it practical to approximate unknown scenes at first.
Features of objects to be extracted for rec ognition depend on the objects. For outdoor scenes, regions of uniform color might be good clues for recognition of the sky, fields, lakes and so on (10,11]. For example, a large blue region at an upper part of a scene might be the sky. For office scenes composed of known objects (9], color and range of the each point in the scene might be enough to locate the table top or the door candidates.
On the other hand, recognition of every day objects on the desk using only light intensity data requires more complex features. There is less constraint on the configuration of objects on the desk than those in the outdoor scenes. Light intensity of a point in the unknown desk scene alone can not suggest any meaningful facts. It might be necessary to look at the change of light intensity and the relation with other parts of the scene.
There have been many works on feature ex traction of complex scenes [12,13], but few wurf: s have recognized the scenes, using these features. While, many papers assuming picture primitives, have dealt with the symbolic primitives to recog nize complex objects. There have been few works on recognition of complex objects using raw light intensity data.
The author has proposed local features and global features of curved objects for analysis of real-world scenes [14]. The local features r epre sent the types of light intensity change and the global ones are the connected local features of the same type. If the curved object has uniform surfaces, the global features correspond to the edges of the plane or curved surfaces.
Tsuji [15] made a linguistic approach to segmentation of curved object scenes into regions using picture primitives similar to the local features described above. It consists of hier archical modules, each of which compresses the input data to finally obtain the plane and curved regions. The problem with the method is that it must completely analyze the whole scene before it extracts some useful facts· about a scene.
This paper is a further extension of (14] and describes a total system. The system consists of (1) edge finding, (2) segmentation of the edges into straight lines or elliptic curves, ( 3) rec ognition of objects by matching the lines to the models, or by using the raw data if necessary, and (4) top level supervising. The module (1), (2) and (3) are controlled by a simple supervisor to interact with each other so that depending on the situation, the system can locate ~iven ob.jects quickly or analyze the whole scene. The module (1) and (2) are easily controlled by a set of global parameters such as reliability level, minimum curvature, spatial resolution, etc. They are applicable to various objects. The modul e (3) which has at present less generality is descr ibed briefly in thi s paper.
2. EDGE FINDING
2.1. Edge point detection
An edge of an object surface is defined here as a series of smoothly connected edge points . Many operators for edge point extraction have been proposed [12,13,16]. The two operators (two dimensional and one-dimensional) described here are designed to detect edge points of planes and smoothly curved surfaces. The operators extract discontinuity of both the light intensity and its gradient. If the direction of the edge is unknown, two-dimensional operator is used to compute the direction of the gradient, otherwise a one dimensional operator detects the edge point quickly.
The former operator makes use of the gradient computed by a conventional method ( 1l1]. One of three regions shown in Fig. 1 is used to get the gradient at the center element. The gradient value D and the direction a for mode 1 are defined by light intensity of the neighboring points I(i) as follows.
. The gradient for mode 2 or mode 3 is similarly ·~ef1ne~. The operator for edge finding at (x 0 ,y 0 ) ~s def:ned by its gradient D(x0 ,y 0 ), a(x 0 ,y 0 ) and :ts ?e1ghbors. Let (xi,yi) denote a point which is 1 po1nts away from (xo,YoJ in the direction a(x Yol .. simi~arly. (x_i,y-i) represents a point in°~he oppos1te d1rect1on. An edge point is defined using the following conditions.
(Cl) means that the light intensity at an edge must change. (C2) means that the neighbor of an edge in direction a must have a different light intensity change from that at the edge. Usually if (C2) holds for both i 1 >o and i 2<0, then the edge corre sponds to the boundary between two planes. If only ?ne side of the edge (i<O or i>O) satisfies (C2), 1t corresponds to an edge of a curved surface. Edge points extracted by (Cl) and (C2) are sometimes broad along an edge of a surface. In checking (C2), even if some i1 is found at one side of the edge, (xo,Yol is considered as a transient point if for some i2 at the other side,
Thus edge points must satisfy (Cl) and (C2), and must not satisfy (C3).
The edge point is classified into three categories: (1) type B which satisfies (C2) for both il>O.and i2<0, (2) type L which satisfies (C2) for on Y 1>0, and (3) type R which satisfies (C2) for only i<O. Fig. 2 shows an example of the edge point extracted by this operator.
The one-dimensional operator is used if the direction of the edge is predicted. It assumes that the direction of the gradient a at the neighboring points is perpendicular to the predicted edge direction. This operator detects an edge point using an intensity profile of the picture elements on the line centered at the point in the direction a, and classifies it into the three categories in the similar way described above.
2.2. Edge finding program
Fig. 3 shows a simplified flow of the edge finding program. The program has two main tasks: l) find an edge kernel above a given reliability level, and 2) track along the edge starting from
the kernel.
The edge kernel is a set of edge poi-nts of the same cateogry which have similar gradient di rections. A kernel finder first detects an edge point using the two-dimensional oeprator described above, and detects other edge points along the estimated direction of the edge which is perpen dicular to the gradient direction of the first point. If enough edge points are found, the edge kernel is classified into three categories (B, L and R) based on the types of the edge points. The reliability level corresponds to the threshold of the gradient (Dt) in (Cl) for the edge point detector .
A reference map is used to speed up the kernel finding. The original picture is divided into rectangular regions (e.g. 6x6 picture elements) and the map contains an approximate gradient value of the each region. The kernel finder searches for an edge point in the regions corresponding to the points in the map with larger values than a given reliability value. After an edge kernel is searched for in the candidate region, the corre sponding point in the reference map is updated in order to give an accurate value or to avoid the repetition in the later search.
The kernel thus found is extended in both directions by tracking the edge. The purpose of the tracking is to obtain a smoothly curved edge which consists of the edge points of the same type. Intuitively the smooth curve means that it is con tinuous and the tangent direction does not change abruptly. The type and the current parameters of the edge such as the position Xc, direction Be and gradient value De are initially given by the kernel finder. The current parameters are updated as the tracking goes on. The main steps of the tracking at one cycle are
- Predict the position of the edge point using Xc and Be.
- Find a proper edge point.
- Update Xc' Be and De, and go to l.
The prediction of the edge point Pn at n-th cycle is based on the current edge position Xn and the direction Bg as shown in Fig . 4. The distance ~ between xg and pn is one of the parameters of the edge finder which determines the minimum curvature of the edge tracker. When a proper edge point En is found, XH+l is advanced on the line passing through xg and En, and Bg+l is updated as shown in Fig . 4. If the predicted position of the edge is regarded as being on the other edge already found, or on t~e other end of the same edge, the tracking terminates. For this check, a binary map of the edges is used. When the edge point En is found, the map is updated at the point corresponding to En-m(m depends on i described above) and its two neighbors in the direction perpendicular to Bn-m.
In step 2, the one-dimensional operator is used to find an edge point of the same type near the predicted position. The direction of the gradient of the edge point is assumed here to be perpendicular to the current direction of the edge. If the gradient value of the detected edge point is close to De, it is determined as an extension of the edge. If no such points are found, a back up routine determines whether or not to stop tracking as follows.
- If step 2 is the first attempt of the edge point finding, a different gradient direction is proposed to find a proper edge point again, and go to step 2.
- If an edge point is found in the previous cycle, then insert a simulated edge point at the predicted position and go to step 3.
- Otherwise, stop tracking.
The purpose of the back up is to avoid the effects of a small texture of an object, various kinds of noise and digitization of directions.
When the tracking in both directions termi nates, each end of the edge is checked to connect to the other edges already found. If the tracking stopped at the other edge of the same type and the both edge can be connected smoothly , they are merged.
rig. 5 shows an example of the edge finding. Usually, edge finding is repeated over the picture, each time changing the reliability to a lower level. The tracking of a less reliable ed~e can be blocked by more reliable edges which cross to it.
3. SEGMENTATION OF EDGES
Each edge obtained by the edge finder is rep resented by a set of smoothly connected points. The segmentation of edges is to describe them by several parameters useful for recognition.
There have been many works on the mathemati cal approximation of curves by polygonal lines [17), piecewise polynomial functions or spline functions [18). They defined an error norm and attempted to find an optimal solution. However, these are not easily applied to the description of the complex scenes.
In this paper, straight lines and elliptic curves are used to describe the edge curves. The segmentation of the each edge is divided into two parts: (l) segment the edge into lines and curves, and ( 2) approximate each segment by a straight line or an elliptic curve.
Fig. 6(a) illustrates the purpose of the first part, i.e. to divide the edge AF into five segments (AB, BC, ... ,EF). The method is a heuristic one wh ich m11.kes use of the curvature of the edge as described in [2 ] (i.e. the curvature of an edge point P is defined as the angle o between PR and PQ, where Q and R are on the edge and constant number {~) of points away from P). Thus, the curvature of AF is defined on the interval between A' and F' as in Fig. 6(b) which is rnd points inside of AF. The main steps of the method are
- Find the candidates of the knots of the edge.
- Classify temporary segments into straight lines or curves.
- Merge segments if possible, and determine the positions of the knots.
First, to locate the knots where the direction of the edge changes abruptly, the regions are found which have large curvatures. The candidate regions of the knots are illustrated in Fig. 6(b) as inter vals [Lf,Ri). The interval is defined with the curvature o(P) as follows. Let Omax denote the maximum of lo(P) I in [Lf,Ril, then the interval satisfies the following conditions.
where h(x) is a linear function of x(h(x)<x).
The inte rvals may contain either real knots or curved segments. If the interval is short, it is regarded as a real knot. region, otherwise a curved segment. New knots are inserted at the ends of curved segments. Now the temporary segments are
defined as the intervals between the knot candidate regions (i.e. [A' ,Ll), [Rl,L2), [R2,L3), [L3,R3J and [R3,F'l in Fig. 6(b)).
The next step classifies the temporary segments (excluding the curved intervals found in step 1) into straight lines or curves using the constant (lnd) of the curvature, sum of o's (S0 ) and the total number (N) of points in the segment. If the segment PQ is assumed to be an arc as in Fig.7. the maximum distance d between the line PQ and the arc, and the fan angle a are approximated as follows.
Based on this arc assumption, the classification algorithm is: if N~2m; then the segment is unde fined; if d>du, then curve; if a<at, then !ine; if N<m/2 and d~di (di<du), then line; otherwise curve.
The third step tries to merge undefined and curved segments. If sums of the curvatures S01 ar,d S02 of the adjacent segments and that of the knots are all similar, then the segments are merged into one segment. This procedure is repeated until no more merge is applied. Small segments of a smooth curve created in the step l because of the effect of noise or digitization, might be merged here. The position of each knot is determined now accu rately as the border of the adjacent segments.
The second part of the segmentation fits a straight line or curve to a set of edge points (Xi, Yi) (i=l,2, ... ,n) in each segment. Conventional methods of least squares assume that only Yi is accompanied with error. But the position of each edge point has error of both Xi and Yi· The Deming's method [19] is employed to find the para meters of the curve which minimize the sum of square of the distance from the curve to each point.
Let the equation of the curve with m para meters be denoted by f(x,y; al,a2·····aml = 0, then the method, starting from the approximated para meters, estimates better parameters iteratively until they converges within a given error ratio. The initial parameters are given by an appropriate number of edge points which are sampled from. the segment. If the segment is classified into a curved line, an elliptic curve is at first tried to be fi. t ted to it. The parameters are the center po s~tion, major and minor axes and rotation. If the parameters do not converge in the iteration, the number of the parameters is decreased. Fig. 8 shows an example of the results of the segmentation
and curve fitting.
4. RECONGNITION
A strategy of recognizing an object in a scene depends on how much information is already known. If a desk area is known, the fastest way to locate a telephone is to search in the left front part of the area, and if a dial of the telephone is found, recognition of the receiver is easy. The best way to analyze the whole scene is to start from the most obvious object first, and proceed to the next obvious object making use of the previous facts. To locate a given object, however, the best way might be to try to find it first. If it fails, the other object milht be tried which could help t o
locate the given object .
We have been taking multiple approaches to
recognition of objects. One is matching models of objects described by the graphs to a scene [14]. Now a scene is described by the equations and types of the edges. Models of an object are two-di mensional and represent its views from typical di rections. Because a scene is represented by straight lines and elliptic curves, usually a few models are enough for an object. However, this method can not discriminate shapes which are sensi tive to rotation, such as a circle from an ellipse. Each model is described by the edges and their relations. F'or analysis of a scene of multiple obj ects occluding one another, matching of subgraphs is required. An algorithm which extracts maximal common subgraphs between two colored graphs has been developed [20]. Scenes of simple objects such as blocks, cylinders and spheres are recognized by the graph matching technique. The method can easily add new models of objects by declaring their descriptions. There are, however, many difficulties in recognition of complex objects, e.g. description of models and efficient matching procedure. The graph matching could be used as a part of rec ognition procedure.
Another approach is a procedural one, i.e. to provide with a procedure for recognition of each object. For recognition of a telephone, for ex ample, the procedure is first to search for the dial, and then to find the contour of the telephone around the dial. The candidates of the dial is easily found by examining the equations of the curved edges. The telephone contour is searched for in a . certain region around each dial candidates using a map of the edges. Serially connected lines or curves which surround the dial are identified as the contour. If enough proof is obtained, the rec ognition is successful. If proof is not sufficient or many candidates of a telephone are found, fnrther i nvestir;ation is required which might ask more edges or check the inside of the dial. Sometimes the investi~ation requires a facility for zooming-up a scene although this feedback loop has not at present been implemented.
A simplified organization of the present syste;n is s hown in Fig. 9. Given a set of ob,ject names, the supervi sor asks the edge finder to get edges. [f enough number of edge points or edges are found , then the edges are segmented. Otherwise, the supervisor changes parameters of edge finding and more edges are searched for. The recognition con sists of subroutines for t he given objects. If not all the objects are recognized successfully, the supervi sor asks the edge finder again to col lect more edges.
Fig. 10 shows an e xample of locating a lamp, a book stand and a telephone. Recognition of a telephone is as described above. To locate a lamp, a lamp shade is searched for first as edges of a bright strip region of an allowable dimension, and then the trunk is searched for by finding a pair of parallel vertical edges whose directions are oppo site . A book stand is located by f inding a set of vertical lines c lustered in a certain region. The computing time for locating the three obj ects using a picture (6 bit l evel, 256x256 points) stored in the disk i s about 4 minutes . More than half of the time is spent for finding edges .
On the other hand, in order to recognize as many objects in a scene as possible, the edge finder is given parameters of low reliability level to get many edges. Even if recogniti on of some ob,jects is not successful, edge finding can not be retried in this case . An experiment is made for the same scene as in Fig. 10 in this manner. ThE:
upper bound of edge number (70) is determined by the storage limitation of the computer. Although the same objects are successfully located, the computing time for finding edges is more than twice of the above example (Fig. 10). This shows that in order to locate given objects, the system organization in Fig. 9 is efficient.
CONCLUSIONS
An approach to the r ecop;nit.ion of r eal-wor· Jd objects using light intensity data has been de scribed. The recognition is mainly based on the edges of curved objects. The edge is a set of smoothly connected edge point s where light inten sity or its gradient changes abruptly. The edges are segmented into straight lines or elliptic curves so that they are easily matched to the models of objects. Recogniti on of complex objects with a simple matching procedure has been suc cessful.
The method proposed in this paper would be applicable to recognition of every day objects which are identified by the edges of straight lines or ellptic curves. Further research is required to check on doubtful objects by zooming up the regions of interest in the scene. The other objective to be studied is an efficient way of making many models of complex objects.
@inproceedings{ijcai1975p107,
title = {Edge Finding, Segmentation Of Edges And Recognition Of Complex Objects},
author = {Shirai, Yoshiaki},
booktitle = {Proceedings of the Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-75}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Patrick Winston and Carl Hewitt},
pages = {674--680},
year = {1975},
note = {Visual Information Processing},
url = {https://ijcai.org/proceedings/1975/107},
}
TY - CPAPER TI - Edge Finding, Segmentation Of Edges And Recognition Of Complex Objects AU - Shirai, Yoshiaki T2 - Proceedings of the Fourth International Joint Conference on Artificial Intelligence, IJCAI-75 PB - International Joint Conferences on Artificial Intelligence PY - 1975 SP - 674 EP - 680 UR - https://ijcai.org/proceedings/1975/107 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: