--- title: "Recognition of Occluded Objects" authors: - "Bir Bhanu" doi: "" url: "https://ijcai.org/proceedings/1983/264" pdf: "https://ijcai.org/proceedings/1983/0264.pdf" venue: "Proceedings of the Eighth International Joint Conference on Artificial Intelligence" year: 1983 pages: "1136-1137" track: "Vision" keywords: --- # Recognition of Occluded Objects Bir Bhanu *Proceedings of the Eighth International Joint Conference on Artificial Intelligence*, pages 1136-1137. ## Abstract Matching of occluded objects is one of the prime capabilities of any computer vision system. In this paper a hierarchical stochastic labeling technique to do shape matching of 2-D occluded objects is presented. The technique explicitly maximizes a criterion function based on theambiguity and inconsistency of classification. The 2-D shapes are represented by their polygonal approximation. For each of the objects participating in the occlusion, there is a hierarchical process. These processes are executed in parallel and are coordinated in such a way that the same segment of the apparent object, formed as a result of occlusion of two or more actual objects, is not matched to the segments of different actual objects. Results are presented when two or three objects partially occlude. ## Full text ## ABSTRACT Matching of occluded objects is one of the prime capabilities of any computer vision system. In this paper a hierarchical stochastic labeling technique to do shape matching of 2-D occluded objects is presented. The technique explicitly maximizes a criterion function based on the ambiguity and inconsistency of classification. The 2-D shapes are represented by their polygonal approximation. For each of the objects participating in the occlusion, there is a hierarchical process. These processes are executed in parallel and are coordinated in such a way that the same segment of the apparent object, formed as a result of occlusion of two or more actual objects, is not matched to the segments of different actual objects. Results are presented when two or three objects partially occlude. I. INTRODUCTION: The problem of assigning names or labels to a set of units/objects is the key problem in computer vision, image analysis and pattern recognition. Since all the labels are not possible for a given unit, constraints based on contextual information are used to obtain a consistent and unambiguous valid assignment of the units. Local parallel processes are a very efficient way of assigning labels. The features of such algorithms include the propagation of local contextual information in a paradigm of competition and cooperation, locality and speed. In general the task of assigning names to units only on the basis of features of the units is very difficult since any segmentation based on low-level analysis is bound to contain errors and the computed features are noisy. The solution to this problem is to delay any firm commitment until all the contextual information has been used. In this paper we present one such hierarchical stochastic labeling technique to do shape recognition of 2-D occluded objects. The occlusion problem in 2-D is viewed basically a boundary matching problem. The hierarchical nature of the algorithm reduces the computation time and uses results obtained at low levels to speed up and improve the accuracy of results at higher levels. Objects participating in the occlusion may move, rotate, undergo significant changes in the shape and their scale may also change. As compared to the previous studies, the framework presented here provides a mathematical basis for the solution of the occlusion problem. II. PROBLEM FORMULATION: Consider a general case in which M ( > 2) actual objects, called models ## Bir Bhanu ## Ford Aerospace & Communications Corporation ## Newport Beach, CA 92660, USA (Xl, ··· , XM ) occlude one another to form a single apparent object called the object. Fig. 1 shows the block diagram of the algorithm when two models occlude each other. Let a model Xm (m = 1, ··· M) be represented by X m = ( T1 , T2, ··· , TNm), where Nm is the number of segments in the polygonal path representation. Similarly, let 0 .= (o1 ,o2 , ··· ,er.\_1 ) be the polygonal path representation of the object. The object has L-1 segments. We want to match the segments of the models against the segments of the object such that the following two conditions are satisfied. 1) None of the segments of the different models are assigned to the same segment of the object. This is called the occlusion condition. It is necessary for the labeling to be unambiguous. - 2) Those segments of the models which do not match to any of the segments of the object are assigned to the nil class, i.e., no match class. We are trying to identify parts of the models within the object. We designate the object segments as classes, and the model segments as units. Let the nil class be denoted by ~· To each of the units Ti of a model ~. we assign a probability denoted by Pim (k) to belong to class 9k· This is represfnted as a vector Pim = [P\_im ( 1), · · ·, Pim (L)] · The set of all vectors Pim (i = 1, ··· ,N) is called a stochastic labeling of the set of units. The global criterion that measures the consistency and ambiguity of the labeling over the set of units of a model Xm is [1], where and, n denotes the first or second stage of the hierarchy. C1 and C2 comapre the local structures of X m and 0 at the first and second stage. They are defined .as functions of s2xa2 and s3xa3 into [2,1] where, S2 and S3 are two subsets of X~ and xn; defined by, Let Vm be the vector of RP , (P = NmL) equal to (plm' P2m·····~m ). Then the total criterion of consistency and ambiguity for all the M models is, where ~~ is obtained from v~ with the elements corresponding to the nil class set equal to zero for all the units of the model X~ and g(s1,sj) is the inner product of the vectors s i and Sj · Now the occlusion problem can be stated as follows. Problem S1ftement (A): Given an initial labeling v} 0 J, ~ 2 (), ··· , VMr:uJ for the set of M models (X 1 ,x 2 , ··· ,XM) to belong to var~ous+ segme~ts of the object, find the labeling ul, u2, ··· ,uM that corresponds to the local maximum of the criterion (6) which is closest to ~{ O l, ~J Ol, ... ,~J O l subject to the constraints: (a) If Urn = (Plm· P2m· ··· , PNy, 1 m) then P~m is a probability vector for ~ = 1,2, · ·· ,N and m = 1,2, ··· ,M. (b) �(~l' ~ 2 , ... , ~M ) as defined by (7) be equal to zero. Note that the criterion (6) is nonlinear. Constraint (a) involves linear equality and nonnegativity restriction, and constraint (b) is nonlinear. In order to solve this optimization problem we use the gradient projection method and penalty function concept [2]. III. OCCLUSION ALQORITHM: In order to solve the problem (A) we define the penalized objective function as, where <l> ij is a penalty function and {d i j} are penalty constants. The penalty function is taken as the simple quadratic loss function. The problem (A) is equivalent to that of maximizing (8) subject to the constraints (a). It is solved by using the gradient projection method applied to the l i near constraints. The maximization of (8) subject to the constraints (a) is equivalent to maximizing where S(~l'; .. ,;,tm) corresponds to the second term of (8). In general to solve (9) by maximizing with respect to ;,ti the algorithm can be stated as follows: 1. Pick an initial estimate of (;,t1(0 ), v2(UJ, ··. 'VM(U~. This is the initial assignment of probabilities to the units of the models. 2. Pick the penalty. constant {dijl so that it provides a suitable balance between the associated first and second terms of (9). This is done in an automatic manner [1]. 3. Determine the maximum ~m ( n+ l ) (m = 1,2, ··· ,M) 3. of the unconstrained penalized objective function (9) subject to the constraints (al by using the value at the present iteration vm (n)and gradient projection method. 4. Pick new penalty constants {dij } in order to rebalance the magnitude of the penalty terms; replace n by n+1 and return to 3. 5. Under the assumption of the continuity of function F (6) and cons~raint~ (~+~\inherent in (8), the sequence of ma~ma {vm 1 for m = 1, ·.· ,M generated by the above algorithm approaches a constrained maximum of the problem defined in (A). Since we are seeking only local maximum, ill-conditioning problems do not occur [2]. Example ~: Fig. 2 shows two models x1 and x 2 which occlude each other to form an apparent object. The results of labeling of the units of the models are shown in Table 1. Label 19 is the nil class. Note that the assignment of the units of both models are correct. Example .2.: Fig. 3 presents a synthetic example, where three models X1, X2 and X3 occlude one another to form an apparent object. We want to identify each of the models within the apparent object. The problem is a kind of "jig-saw puzzle". Table 2 shows the results of labeling. All the labels of all the units of X1 , X2 and x 3 are correct. Example ~: Fig. 4 shows gray scale 512x512, 8 bits, images of industrial parts which occlude each other to form an occluded object. The images in figs. 4(b) and (c) are reduced by 16 times and the image in fig. 4(a) by 18 times. The reduced images are thresholded and their polygonal approximation is shown in fig. 5 , Only the rotation and scale invariant features are used. Label 25 is the nil class. The results are shown in Table 3. Note that all the key assignments of the units are correct. The units 5,6,7,8 of the Model X 1 are not matched to the segments 9,10,11,12. The reason for this is the presence of ambiguity between segments 5 to 17 of fig. 5(c) and 8 to 16 of fig. 5(a); the number of segments is different as a result of change in scale. IV. CONCLUSIONS: The technique is found to be very effective when applied to synthetic, industrial and biological images. It is able to cope to a certain extent with the common problems of scene analysis such as noisy features, extra and missing segments and a large number of segments [1]. The computation time varies linearly with the number of objects occluding one another and it took about 1 to 10 minutes on a PDP-10.