What Is Where: Inferring Containment Relations from Videos

1 Introduction andMotivations

For many AI tasks, such as scene understanding in visual perception, task planning in robot autonomy, and symbol grounding in natural language understanding, a key problem is to infer "what is where over time". A person may say "the pizza is in a pizza box, and the pizza box is in a fridge". In such a description, the object locations are described in a qualitative and hierarchical way, in which containers play an important role in quantizing human perceptual space via containment relations. By containers, we refer to any general objects in a scene that can contain other objects, for example, fridge, mug, box, lunch bag, envelop and so on. The containment relations between containers and contained objects, i.e. containees, may change over time by agents.

In this paper, we propose a probabilistic approach to infer containment relations from RGB-D videos. Consider the example shown in Fig. 1. The containers and containees are tracked in a 3D scene and highlighted in colored bounding boxes in the top panel. The inferred containment relations are constructed in the bottom panel, pointing from containees to the corresponding containers, and the numbers on edges denote the frames when the containment relations occur. It is worth noting that the containment relations are time varying, and can be changed by human actions. The presented containment relation inference method is aim to address the following two tasks.

Recovering hidden objects with severe occlusions. Severe occlusions frequently happen in daily scene. Reasoning about containment relations helps to recover objects from tracking failures when objects are partially occluded or even completely unobservable. For instance, as shown in Fig. 1, although we only observe a person taking a pizza from a pizza box at frame 246, we are able to infer that the pizza was contained by the pizza box from frame 1 to 245, during which period the pizza was unobservable. By simple commonsense that a containee shares the same position as its container when the containment relation between them holds, we are able to recover the hidden containee with severe occlusions or even without actually seeing it. This capability provides a potential solution to build a system (e.g. an assistive robot) to answer "what is where over time". For example, a robot can help to localize an object in a room if a person forgets where he or she left it.

Inferring subtle human actions. Because there are selfocclusions or occlusions by other objects in a scene, subtle human actions that involve small and local movements, such as placing a phone in a bag, are difficult to detect. If a change of objects' status (i.e. a containment relation change) is observable, it is natural to reason about that some human actions occurred. The ability of inferring human subtle actions by goals instead of observing and matching detailed action trajectories provides possibilities for a robot to understand the intentions of agents.

Fig. 2 illustrates the framework of the proposed method. Given a RGB-D video captured by a consumer depth camera (Fig. 2(a)), our method first tracks the objects of interest and the human skeletons (Fig. 2(b)). Then at each frame t, the containment relations are represented by a containment graph; in time, containment relation changes are proposed based on human actions. To find the optimal interpretation across the full sequence, a dynamic programming algorithm is adopted to globally optimize both spatial and temporal space, resulting in the optimal sequence of containment graphs (Fig. 2(c)).

This paper makes three major contributions:

1. We propose a probabilistic approach to infer containment relations from videos over time. A dynamic programming algorithm is applied to solve the ambiguities on both containment relations in space and containment relation

changes in time, providing a globally optimized solution.

1. We propose a dynamic graph representation for containment relations over time (shwon in Fig.1). The dynamic graph quantizes 3D scene space and provides a qualitative way for tracking objects with heavy occlusions.
2. We model the containment relation changes in time by assuming that human actions are the only cause to change the containment relations. This constraint in return helps to recover hidden objects and infer time varying containment relations at each frame.

1.1 RelatedWork

Cognitive studies [Hespos and Spelke, 2007] has shown that infants can understand containers and containment relations as early as 3.5 months old. Strickland and Scholl [Strickland and Scholl, 2015] suggest that infants can detect containment before understanding occlusion. Liang et al. [Liang et al., 2015] evaluates human cognition of containing relations for adults through a series of experiments using physical-based simulations. In computer science, the problem of containers has been studied from various perspectives in the fields of AI, robotics and computer vision.

AI. Qualitative Spatial Representation / Reasoning (QSR) has been extensively studied in the AI community. Cohn and Hazarika [Cohn and Hazarika, 2001] provided a survey of key ideas and results in QSR literature. Some typical methods include using ontology [Hudelot et al., 2008; Grenon and Smith, 2004], topology [Gerevini and Renz, 2002; Li, 2007], metric spatial representation [Frank, 1992; Papadias and Sellis, 1994], and other approaches [Hedau et al., 2010; Sokeh et al., 2013; Renz, 2012]. Since 1980s, the AI community began to study containers as a typical example for qualitative reasoningusing symbolic input [Bredeweg and Forbus, 2003; Frank, 1996]. In particular, Collins and Forbus [Collins and Forbus, 1987] used containers to reason about liquid by introducing a new technique, namely molecular collection ontology. A knowledge base for qualitative reasoning about containers was developed by Davis et al. [Davis et al., 2013], which was expressed in a first-order language of time, geometry, objects, histories, and events. However, existing methods for spatial and temporal reasoning in the AI literature are mostly based on logic formulas, which are difficult to apply on processing real sensory inputs. The ability to handle noisy visual signal as inputs by introducing probability to model qualitative spatial relations makes our method different from previous work.

Robotics. Localizing objects using spatial relations has received considerable interests in the robotics community, e.g. [Aydemir et al., 2011; Wong et al., 2013; Feddema et al., 1997; Aksoy et al., 2010; Nitti et al., 2014]. Alper et. al [Aydemir et al., 2011] utilized spatial relations to describe topological relationships between objects. Wong et al. [Wong et al., 2013] studied occluded objects inside containers, and presented a novel generative model for representing container contents by using object co-occurrence information and spatial constraints. Feddema et al. [Feddema et al., 1997] applied two methods to control the surface of liquid in an open container which was moved by a robot. Most of the existing methods can only reason about containment relations in a known structured environment. In contrast, the proposed method aims to address the problem in arbitrary environments, where the number of objects are not fixed and relation changes occur more frequently.

Computer Vision. Two streams of studies are closely related to the present work: object affordance and tracking objects using context information. In recent literature, there is growing interest in understanding scenes and objects by their their affordances and functionalities [Grabner et al., 2011; Gupta et al., 2011; Zhao and Zhu, 2013; Zhu et al., 2015; 2016] and their possible interactions with human poses [Satkin et al., 2012; Koppula et al., 2013; Zhu et al., 2014; Wang et al., 2014a; Wei et al., 2013; Pei et al., 2013]. Using context information has also been extensively explored in human-object interaction and multiobject tracking. For instance, Yang et al. [Yang et al., 2009] proposed to track multiple interacting objects by mining auxiliary objects, and [Wang et al., 2014b] formulated the interacting objects tracking as a network-flow Mixed Integer Program problem. More recently, a multiple objects tracking algorithm [Yoon et al., 2015] was proposed by maintaining spatial relations between objects using a Relative Motion Network. In comparison, our method utilizes the interactions between human and objects as temporal constraints to infer the explicitly modeled containment relations and their changes, resulting a probabilistic approach to recover objects with heavy occlusions.

2 ProblemDefinition

We use ⌦ = ¶Oi ♣i = 1 · · ·N♦ to denote all the objects of interest in a scene, where Oi denotes the ith object. At each frame, we define the following variables:

• ÷ A containment indicator function is denoted by Ct(·) 2 ⌦. If Oj contains Oi directly, then Oj = Ct(Oi ), where Oi is the containee and Oj is the container.
• ÷ A containment relation Rit = hOi ↪Ct(Oi )i is an ordered pair representing the containment relation between Oi and Ct(Oi ). The set of all containment relations at time t is denoted as ⇤t = ¶Rit ♣i = 1↪ · · · ↪N♦.
• ÷ A containment graph is denoted as Gt = (⌦↪ ⇤t), where ⌦ is the set of vertices and ⇤t is the set of directed edges.

To make the inference process tractable, we make the following assumptions about the properties of Gt.

Spatial Assumptions. i) Each object must be contained by one and only one container, except the root node of Gt, i.e., the "room", which does not have its container. ii) There is no loop in Gt, that is, object cannot contain itself. The nested containment relations do not form loops. iii) A person becomes a container when he or she holds an object.

Temporal Assumption. We assume that all containment relation changes ought to be caused by a person, which means a scene does not have external disturbance other than human. In other words, if we know there is no human actions, the containment relations should not change. This temporal assumption couples containment relations in space with containment relation changes over time. Fig. 3 gives an example: a person takes an apple out of a bowl, during which the person breaks the containment relation between the apple and the bowl, and establishes a new containment relation between the apple and the person.

3 ProblemFormulation

The objective of our work is to interpret the observed video as the optimal sequence of containment graphs ¶Gt♦⇤ from a given RGB-D video V[1↪T ] = ¶Vt♣t = 1↪ · · · ↪ T♦.

3.1 Containment Relations in 3D Space

At each frame t, a containee Oi is contained by a container Ct(Oi ) if and only if it satisfies all following relations defined in terms of an energy function Φ with the three components:

• ÷ IN relation defined by the energy term φIN;
• ÷ AFFORD relation defined by the energy term φAFF.
• ÷ ON relation defined by the energy term φON;

IN relation describes containment relations from the top view:

where Γ(Oi ) is the projected area of containee Oi along the gravity axis, and Γ(Oi ) \ Γ(Ct(Oi )) is the overlapped area between containee Oi and its container Ct(Oi ) projected in 2D from the top view.

The bottom right of Fig. 4 shows three examples of IN relation. If a containee is contained by its container, the boundary of the containee should be inside the contour of the container from the top view.

ON relation describes containment relations from the

where Zb(Oi ) is the bottom coordinates of the containee projected to 2D, Zg(Ct(Oi )) = [Zt(Ct(Oi ))↪ Zb(Ct(Oi ))] is the interval of the container's top and bottom coordinates projected to 2D, and D is a distance function which measures how well the bottom of the containee Zb(Oi ) falls into the intervals between the top and the bottom of the container Zg(Ct(Oi )). If a containee is contained by its container, the bottom of the containee has to contact the container, and the containee should be above the container. Three examples of ON relation are illustrated in the top right of Fig. 4.

AFF relation φAFF(Rit ↪ Vt) measures the ability of a container to afford a containment relation with containee at frame Vt, which is a pair-wise term. The containment relation is subject to a set of physical and geometric constraints. For example, a porous basket can neither contain a containee bigger than itself, nor smaller containees like beads. In this paper, we only consider the relative volume between the container and the containee.

Energy of containment relations is defined as:

where λ1 and λ2 are the weights of the energy terms, obtained through cross-validation during the training phrase.

3.2 Containment Relation Changes in Time

The containment relation change between frame t and t + 1 is denoted as ∆Rit . We classify the changes based on human actions into the following four categories, shown in Fig. 5.

Move-in is defined as ∆Rit : hOi ↪Hti ! hOi ↪Ct+1(Oi )i, which describing a containee Oi moves from a person Ht at frame t to another container Ct+1(Oi ) at frame t + 1.

Move-out is the opposite change to move-in, defined as ∆Rit : hOi ↪Ct(Oi )i ! hOi ↪Ht+1i.

No-change implies there is no containment relation change between frame t and t + 1, defined as Ct(Oi ) = Ct+1(Oi ).

Paranormal-change refers to the change that is in conflict with the temporal assumptionthat a person is the only cause that leads to containment relation changes, and thus is ruled out through reasoning. Formally, if the containment relation Rit changes, i.e. Ct(Oi ) 6= Ct+1(Oi ), but no person H is involved, i.e. Ct(Oi ) 6= Ht &Ct+1(Oi ) 6= Ht+1, such changes are defined as paranormal-change.

Energy of containment relation changes is defined as

where !Lj is the template parameter for four types of containment relation changes Lj ↪ j 2 ¶1↪ 2↪ 3↪ 4♦, [t - ✏↪ t + ✏] is the time interval of the sliding windows for temporal feature extractions, and ✓ is the extracted feature vector.

For ✓, we introduce objects context during feature extractions [Wei et al., 2013]. Three kinds of features are considered in a sliding window on the time axis: the human pose F hm , the relative movements between the human hands and the object F rm, and the movements of the object F om. Suppose that the sliding window size is 2✏, the feature vector sequence at time t is Fm = (F hm↪F rm↪F om), m 2 [t-1-✏ t-1+✏]. F hm is the relative distance of all skeletons to three base points (two shoulders and a spine point). F rm is the distance between the human hands and the position of the object. F om is the object position changes during the time interval 2✏. A wavelet transform is then applied to Fm. The coefficients at the low frequency are kept as the interaction feature ✓. The window sizes and sliding steps are both multi-scale.

3.3 Joint Spatial-Temporal Energy

By combining both the energy of containment relations in space at each frame (Eq. 3), and the energy of containment relation changes between adjacent frames (Eq. 4), the optimal containment graph ¶Gt♦⇤ is defined as:

where φ is the data term which models the energy of containment relations in space, is the smooth term that models the containment relation changes in time, and θ is the trade-off parameter between the spatial-temporal cues.

4 Inference by Dynamic Programming

The goal of the inference process is to find the optimal sequence of containment graphs ¶Gt♦⇤ for the input RGB-D video by optimizing the energy function defined in Eq. 5.

The time complexity of searching the entire solution space is O(N (N-1)·T ), where N is the number of objects and T is the video length. It is impractical to brute-force search the entire space.

Fortunately, at each frame, the container of the containee Oi is independent of the container of the containee Oj . By assuming such property that the container of each containee is independent, we can optimize the solution for each object separately. Hence, Eq. 5 can be rewritten in terms of containment relations with respect to each object:

By aggregating ¶Rit ♦⇤ from each object, we can recover the full sequence of containment graphs ¶Gt♦⇤ of the scene. A dynamic programming is adopted to find the optimal solution of Eq. 6 with the time complexity O(N 2 · T).

5 Experiments

5.1 Dataset

We collected a RGB-D video dataset with diverse actions to evaluate the proposed method. Our dataset consists of 1326 video clips in 9 scenes captured by a Kinect sensor, in which 800 clips are used to train our model and the remaining clips are for testing. For each video clip, RGB and depth images, 3D human skeletons as well as point cloud information are used as the input of the proposed method.

Our dataset is unique, compared with traditional ones in the following aspects: i) it focuses on containers and containment relations; ii) it includes partially and completely occluded objects, such as an apple in a bowl (partial occlusion) and a laptop in a backpack (complete occlusion); iii) it includes diverse containment relation changes in different scenarios, such as throwing, picking up, opening lid, zipping zipper and so on.

5.2 Detection of Containment Relation Changes

Consider the case shown in Fig. 6, where a person moves a containee from one container to another, during this process the containee changes directions, scales, and views. Severe occlusions by hands and other objects also occurred. We show the probabilities of three relation changes by detection: move-in, move-out and no-change between two objects highlighted with bounding boxes. At each frame, we compare the category which has the highest probability among three candidate categories with the ground truth (bars at the bottom). The detection of relation changes works well in most cases, but it fails in certain situations: i) when skeletons, the containee and the container are occluded at the same time (frame 54-70), the algorithm cannot distinguish the relation change of move-in or move-out from no-change; ii) some skeletons or the containee are occluded partly (frame 380-390), which causes difficulties in distinguishing move-in from move-out.

We quantitatively compare the results of containment relation changes between our method with two baseline methods, as shown in Fig. 7: (a) recognition by human actions only, and (b) recognition by both human actions and object context. Both of them are trained by multi-class SVM on the same training data. There are obvious confusions between move-in and move-out in (a). By introducing object context, the proposed method improve the accuracy as shown in (b). The proposed method achieves the best performance in (c). The reason is that our method is able to correct some temporal detection errors.

5.3 Inferring Containment Relations

Fig. 8 demonstrates the inference process. Firstly, we track all objects of interest by state-of-the-art RGB-D trackers [Song and Xiao, 2013]. The objects are bounded by boxes with different colors in Fig. 8 (a). Take the object in the green box as an example, we infer the containment relations it involves in.

Fig. 8 (c) shows the probability of containment relations between the object in the green box and its potential container, using the spatial cues only. Each row represents one possible container. The height of the line represents how likely this container contains the object in the green box. Due to severe occlusions, the spatial cues of objects are missing constantly. When the object is occluded, the probability for each possible container is evenly distributed.

Fig. 8 (d) shows the inference result matrix, in which the nth row represents the DP result of each frame given the first n frames of the video. The grey area denotes the states that are not observed up to the nth frame. As more information is given, the DP algorithm gradually corrects results and gets closer to the ground truth. Take 1© for example, the inferred container from frame 53 to 90 does not change to the human hand until the 91st frame. The initial inferred container remains to be the table due to heavy occlusion. But as time goes, the temporal information accumulates and wins against the spatial cues. our method achieves good performance in comparison with the ground truth in Fig. 8 (e).

We also perform quantitative evaluations. For comparison, we transform the tracking results into containment relations as a baseline. Specially, we apply non-maximum suppression at each frame for all candidates, and the bounding box with the highest score is considered as the present position of the object. For each object Oi , its container is the object which is nearest to Oi , and satisfies both ON relation and IN relation.

We divide our dataset into three parts according to the visibility of objects: no occlusion, partial occlusion and complete occlusion. Partial occlusion is the situation that the containee or its container is observed partially, whereas complete occlusion means that the container or its container is occluded completely, such as a laptop is put into a backpack. We quantitatively evaluate the accuracy of containment relations on these situations. The results are shown in Table 1. In the completely occluded situation, both methods perform worse than in the other situations. The proposed method performs better by recovering some relations from complete occlusions. In the situation of no occlusion, there are some false positives because of the observation noise in the detection process. Our method is efficient to eliminate some false positives.

6 Conclusion

Containers and containment relations are ubiquitous in daily scenes and activities. They are useful not only to answer "what is where over time" for various AI tasks, but also for quantizing the perception of functional space, detecting and tracking hidden objects and heavily occluded objects, and reasoning about human subtle actions. The presented method achieves good performance in some challenging scenarios. However, it is still limited in the following aspects: i) IN and ON relation do not describe all containment relations, such as liquid or gas; ii) the objects with large deformation, such as plastic bags, are still difficult to solve.

Acknowledgment. The authors would like to thank the support of a DARPA SIMPLEX project N66001-15-C4035, a MURI project N00014-16-1-2007, and a NSF grant IIS1423305.