UPGMpp: a Software Library for Contextual Object Recognition

UPGMpp: a Software Library for Contextual Object Recognition J.R. Ruiz-Sarmiento, C. Galindo, and J. Gonzalez-Jimenez System Engineering and Automation Dept., University of M´alaga, Campus de Teatinos, 29071, M´alaga, Spain, [email protected], WWW home page: http://mapir.isa.uma.es/ Abstract. Object recognition is a cornerstone task towards the scene understanding problem. Recent works in the field boost their performance by incorporating contextual information to the traditional use of the objects’ geometry and/or appearance. These contextual cues are usually modeled through Conditional Random Fields (CRFs), a particular type of undirected Probabilistic Graphical Model (PGM), and are exploited by means of probabilistic inference methods. In this work we present the Undirected Probabilistic Graphical Models in C++ library (UPGMpp), an open source solution for representing, training, and performing inference over undirected PGMs in general, and CRFs in particular. The UPGMpp library supposes a reliable and comprehensive workbench for recognition systems exploiting contextual information, including a variety of inference methods based on local search,graph cuts, and message passing approaches. This paper illustrates the virtues of the library, i.e. it is efficient, comprehensive, versatile, and easy to use, by presenting a use-case applied to the object recognition problem in home scenes from the challenging NYU2 dataset. Keywords: contextual object recognition, probabilistic graphical models, probabilistic inference, scene understanding 1 Introduction Scene understanding systems aim to provide a valid interpretation of the perceived imagery which can be leveraged by a large variety of innovative technologies, like robotics, assistance to visual impaired, autonomous driving, etc. Object recognition is a key component of these systems, whose results become crucial for a proper understanding of the scene. Modern approaches improve the object recognition performance by incorporating contextual information of the objects, in addition to their usually employed geometry and/or appearance properties [1, 12–16, 20, 23]. This enables the disambiguation of confusing classifications provided by methods only relying on properties of the objects themselves [5]. Let’s suppose, for example, a scene with a brown, cylindrical object. A method relying on geometric/appearance properties could have problems to classify it as a pot or a flowerpot, however, if it is found on a stove, the pot option is more probable. Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. II The Probabilistic Graphical Models (PGMs) framework [7] has been widely used to exploit contextual relations among objects. Concretely, a particular type of PGM, namely Conditional Random Field (CRF), has focused the interest of researchers given its suitability to model this kind of problems. PGMs integrate a compact and powerful graph-based representation of complex probability distributions defined over high-dimensional spaces, and employ probabilistic inference algorithms to efficiently perform queries of interest over it. Of particular concern is the Maximum a Posteriori query (MAP), since it provides the recognition results by computing the most probable category assignations to the scene objects1. The simplest MAP inference method, called exact inference, exhaustively tests all the possible objects’ category assignations, which is an unfeasible approach in many real-world problems. Instead, approximate methods are exploited, which can be roughly classified into three major groups: local search [2], graph cuts [4], and message passing algorithms [9]. Most contextual-based object recognition works rely on an ad-hoc implementations of both the PGMs framework and inference algorithms [1, 12, 20, 23]. This makes it difficult to conduct a fair comparison between state-of-the-art works, even when they report results resorting to the same dataset [15]. There are some publicly available software libraries implementing this framework [11, 18], but they are not suited for the contextual object recognition problem (e.g. they only handle chain-structured models), or their applicability to this issue is limited. This paper presents the Undirected Probabilistic Graphical Models in C++ (UPGMpp) library, a software package for working with undirected PGMs, as is the case of CRFs, and its application to scene object recognition. UPGMpp exhibits a number of features that make it suitable for facing this particular problem: i) it works with discrete random variables, like the ones needed to model the possible objects’ categories (e.g. chair, table, book, etc.), ii) it handles unary and pairwise relations, needed for representing the objects’ features and relationships, and iii) it enables the representation of arbitrary structures, i.e. it can codify any number of scene objects and relations among them. This library implements inference methods from the three major groups mentioned above, including for example Iterated Conditional Modes (graph search), α-βswaps (graph cuts), or Loopy Belief Propagation (message passing). Therefore, UPGMpp provides a good basis for their evaluation and integration into recognition systems exploiting context. From an algorithmic point of view, the library also includes mechanisms to train PGMs and to perform probability queries (carry out marginal inference), as well as functionality for storing/loading PGMs from files through serialization. UPGMpp is designed to be efficient, versatile, extensible, and easy to use through clear and intuitive APIs, and resorts to well known libraries for numerical optimization (libLBFGS [10]), matrix operations (Eigen [6]) and memory handling (Boost [17]). It is entirely open-source, and is publicly available under a GNU General Public License (http://mapir.isa.uma.es/work/upgmpp-library). The library is distributed along with a number of code tutorials, so the user can master and start using it quickly. 1Along this paper we employ the term inference to refer to MAP inference. Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. III microwave wall stove counter oven oven wall cabinet cabinet floor I(y4,y5,x4,x5, θ) y6 y5 y7 y4 y3 y2 y1 U (y5,x5,w) x3 x7 x5 x4 x1 x2 x6 x5 x4 x1 x3 x2 x9 x10 x7 x8 x6 y8 x8 y9 x9 y10 x10 Fig. 1. Left, RGB-D image of a kitchen from the NYU2 dataset including the scene objects marked as x={x1, ..., x10}. Right, CRF structure built from the scene. The blue shape represents the scope of an unary factor, while the red one states the scope of a pairwise factor. Random variables are labeled with the categories assigned by the execution of a probabilistic inference method over the CRF. As an illustrative example of its suitability to the contextual object recognition problem, we describe a use-case of recognizing objects from home scenes within the challenging NYU2 dataset [19]. Performance results regarding the execution time of inference and training methods within UPGMpp are also shown. The next section describes the application of Conditional Random Fields to the scene object recognition issue, in order to provide a theoretical background for a better understanding of the library components. Then, section 3 presents the UPGMpp library, as well as the inference algorithms that it implements. Section 4 illustrates the UPGMpp application to the recognition of objects from scenes within the NYU2 dataset. Finally, section 5 outlines the conclusions and possible future work. 2 Contextual Object Recognition through Conditional Random Fields The object recognition problem can be stated as the assignation of classes (e.g. table, chair, notebook, etc.) to a number of regions observed in imagery from a given scene. Let’s consider the following definitions to address this problem from a probabilistic stance: –Define x={x1, .., xn}as the set of nobjects appearing in the scene, where each xiis characterized through a vector of mfeatures, fxiu= [fxiu1, .., fxium]T, e.g. their size, color, orientation, etc. –Let L={l1, .., lk}be the set of kpossible object classes. –Define y={yi, .., yn}as the set of discrete random variables over L, where each yiassigns a class from Lto its associated object xi. Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. IV Thereby, the object recognition problem, modeled through a Conditional Random Field [7], is such of maximizing the probability distribution P(y|x), i.e., to find the most probable classes’ assignation from Lto the random variables in yaccording to the characterized objects in x. The structure of a CRF is represented by a graph H= (V, E), where Vis a set of nodes associated to random variables, and Estands for a set of edges liking related variables/nodes. Regarding the problem at hand, a node represents a variable from y, and an edge connects two variables which associated objects are contextually related in the scene, i.e. they are placed close to each other. Figure 1-left shows an scene with ten objects, which are represented as nodes in the CRF in figure 1right. We can see how, for example, the stove is related to the cabinet, the wall, and the counter, so their associated nodes are linked. Thereby, the probability distribution P(y|x) can be factorized over this graph structure H, which is expressed for convenience by means of log-linear models [7]: P(y|x,ω,θ) = 1 Z(x,ω,θ)e−(y,x,ω,θ)(1) where Z(·) is known as the partition function, so Pξ(y)P(y|x,ω,θ) = 1, being ξ(y) a possible assignation to the variables in y,ωand θare vectors of weights learned during the CRF training, and (·) is the energy function, defined as: (y,x,ω,θ) = X i∈V U(yi, xi,ω) + X (i,j)∈E I(yi, yj, xi, xj,θ) (2) being U(·) and I(·) the so-called unary and pairwise factors respectively. These factors can be seen as functions encoding small parts of the whole P(y|x) over the nodes and edges of the graph H. Thus, an unary factor gives an intuition about how probable is for a node yito belong to a class from Laccording to the features of the object xi. On the other hand, a pairwise factor speaks about an edge, and states the compatibility of two related variables being assigned a certain pair of classes from L. The scope of these factors is shown in figure 1right. They are defined by means of log-linear models as follows: U(yi, xi,ω) = X l∈L δ(yi=l)ωlfxiu(3) I(yi, yj, xi, xj,θ) = X l1∈L X l2∈L δ(yi=l1)δ(yj=l2)θl1,l2fxixjp(4) where δ(yi=l) is the Kronecker delta function, and fxixjpis the vector of pairwise features characterizing the relationship between the objects xiand xj. The training of a CRF consist of finding the vectors of weights ωand θthat maximize the likelihood function: max ω,θLP(ω,θ:D) = max ω,θY d∈D P(yd|xd) (5) Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. V where Dis the set of all the scenes used for training, compound each one of a set of characterized objects xd, and their respective ground truth classes yd. Solving Eq. 5 requires the computation of the partition function, which is unfeasible in practise. Section 3.1 introduces the approaches implemented in the UPGMpp library to face this issue. Once the CRF is trained, it can handle the execution of inference algorithms to contextually recognize objects. Thus, given a scene, its particular graph structure H= (V, E) is built according to the relations shown by its constituent objects (see figure 1). The (MAP) inference goal is to find the classes assignation ˆ y that maximizes the probability distribution P(y|x) factorized over H, that is: ˆ y=arg max yP(y|x,ω,θ) (6) Again the computation of the partition function Z(·) is needed. However, since given a certain scene its value remains constant, this expression can be simplified by: ˆ y=arg max ye−(y,x,ω,θ)(7) Despite this simplification, to compute an exact solution of such an equation is still unfeasible due to the huge number of possible assignations to be checked (kn), which motivates the use of approximate inference methods. The algorithms implemented in the UPGMpp library for this are described in section 3.2. 3 UPGMpp Library The Undirected Probabilistic Graphical Models in C++ (UPGMpp) library is an open-source software for dealing with undirected PGMs, e.g. Markov Random Fields, or Conditional Random Fields. The library works with discrete random variables and handles local and pairwise relations, i.e. first and second order PGMs. UPGMpp provides tools for: i) defining graph representations, ii) completing a fast training of models, and iii) performing efficient inference queries (both probability and MAP queries). This section presents an overview of the most relevant features of the library and its components (section 3.1), as well as the available inference algorithms (section 3.2). 3.1 Overview The UPGMpp library is divided into three packages (see figure 2): –base. Implements the functionality for building and managing PGM graphs. –training. Permits the definition of training datasets to tune a PGM. –inference. Implements algorithms to perform probability and MAP inference queries over PGMs. Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. VI Fig. 2. Simplified UML class diagram of the main classes within the base (blue), training (yellow) and inference (green) packages within the UPMGpp library. For interpretation of references to color, the reader is referred to the web version of this work. The base package provides an easy way to create and manage graphs representing PGM structures. Instances of nodes from Vcan be created employing the CNode class, as well as edges from Ethrough the CEdge one. The CNodeType and CEdgeType classes permit us the definition of typed nodes and edges. Having the sets of nodes and edges, they can be inserted into an instance of the CGraph class, which represents the graph structure H= (V, E). The factors within nodes (unary) and edges (pairwise) have been implemented through log-linear models (recall equations 3 and 4), although the user can easily define a different way to compute them through a prototype function. The training package provides mechanisms for building datasets employing the CTrainingDataset class, i.e. sets of graphs along with their ground truth categories (see the yellow class and methods in figure 2). Once created and populated, a dataset can be used to train an undirected PGM, i.e. to find the vectors of weights ωand θin equation 5. Recalling that the computation of such an equation is unfeasible in practice, two major approaches are considered in the literature: the definition of tractable alternative objective functions, like the pseudolikelihood, and the use of approximate inference processes (including MAP and marginal inference) [7]. Both approaches have been implemented and are available to the user in the training package. Finally, the inference package implements a number of state-of-the-art inference algorithms for performing both, probability and MAP queries (recall equaDraft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. VII tion 7), although in this work we focus on MAP since it provides the scene object recognition results. To facilitate its use and future expansion, every MAP inference algorithm inherit the same functionality from a base class, CInferenceMAP, and implements the same abstract method for performing inference (see green classes in figure 2). The implemented MAP inference methods are described in section 3.2. UPGMpp resorts to the also open-source project libLBFGS [10] for performing numerical optimization, and the Eigen [6] library for performing fast matrix operations. The Boost library [17] is used to avoid unnecessary re-copy of data across the library methods by means of shared smart pointers. This library is also used for serialization purposes, which adds the possibility of storing/loading graphs from/to files, enabling the long-term life of PGMs beyond execution time. 3.2 MAP inference methods This section briefly describes the theory behind the approximate MAP inference methods implemented in the UPGMpp library. The interested reader can refer to the provided citations for further information. Local search methods. Local search methods are the simplest approaches for approximated MAP inference, and they are widely used due to their easy implementation and acceptable results. In a nutshell, these methods operate over a set of candidate solutions called search states, which define a search space. In object recognition, a search state can be seen as a certain assignation ξ(y) to the variables in y, which have an associated likelihood value, and the search space corresponds to the set of all possible assignations. Thus, starting at a certain state ξc(y), a local search method checks if there is a state among the set of similar states, defined as Sim(ξc(y)), showing a higher likelihood value. If so, the algorithm moves to it as the current search state ξc(y). Thereby, these methods perform small movements while exploring the search space, always increasing the expected likelihood, until a local maximum is reached, i.e. there is not a similar state to the current one with a higher likelihood. Algorithms within this group differ in how they define the similarity function Sim(ξc(y)) for a given state ξc(y). Next, the Iterated Conditional Modes (ICM) local search method and its Greedy variant are described (see [2] for further detail.) Iterated Conditional Modes. ICM operates by giving an initial assignation to the variables in y, and iterating over those variables to maximize the local conditional probability: ˆyi=arg max yi P(yi|yNH(yi), xi,xNH(yi)) (8) where yNH(yi)and xNH(yi)are sub-vectors of the original yand xones that contain the random variables and observations of the neighbor nodes of yiin a certain graph H. Thus, being ξc(·) the current assignation to a set of random Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. VIII variables, the set of similar states is defined as Sim(ξc(y)) = {ξ(y)|ξ(y−i) = ξc(y−i)}. This algorithm ends when convergence is achieved, i.e., an iteration over all the variables is completed without changing the search state, or when a given limit of iterations is reached. Greedy ICM . The greedy variant takes the same initialization and ending criteria, but instead of performing a movement per random variable in y, it first iterates over all the variables, and then applies the movement that yields the maximum likelihood increment. In this case the set of similar states is defined as: Sim(ξc(y)) = {ξ(y)|diff(ξ(y), ξc(y)) = 1}, where diff(ξ(y)−ξc(y)) yields the number of random variables with different assigned classes, i.e. two states are similar if only one random variable in yshows a different assignation. This algorithm requires on average more iterations to converge than the original ICM, but it is more robust against getting stuck in a local maximum. Graph cuts methods. Graph cuts [4] have been extensively used to efficiently face early vision problems that can be formulated as a minimization of an energy function. This approach reduces the MAP inference task to instances of the minimum cut problem. Let’s suppose a binary classification problem (yi={0,1}) with factors codified over a graph H= (V, E). To apply graph cuts, the graph is modified in the following way: a pair of nodes, s(source) and t(sink), are added so Vc={V, s, t}, and two edges linking each node with sand tare included, obtaining the set Ec={E}∪{es→i, ei→t,∀i∈V}. Then, the minimum cut of this new graph Hc={Vc, Ec}is computed, which divides the set of nodes into two sets: the one containing the nodes connected to the source s, called Vs, and the set of nodes Vtlinked to the sink t. Finally, the nodes in Vsare classified as belonging to the class 0, and those in Vtto the class 1. This method can be extended to handle non-binary classification problems, as illustrate the α-β swaps and the α-expansions algorithms [3]. α-βswaps. This algorithm iterates over all the possible class pairs (α,β) in L, and checks if there is a swap among the variables assigned to that classes that increments the expected likelihood. Let Vα={Vi=α, ∀i∈V}be the set of nodes/variables assigned to the class α, and Vβ={Vi=β, ∀i∈V}those assigned to β. Then, graph cuts compute the optimal classes assignation for the graph Hc= (Vc, Ec), where Vc=Vα∪Vβ∪ {s, t}and Ec={eij ∈E|(i= α)∩(j=β)}∪{es→k, ek→t,∀k∈(Vα∪Vβ)}. In this case, a node connected to the source sin the minimum cut is classified as belonging to the class α, and to βotherwise. A change in the assignation of a node in the minimum cut with respect to its previous one produces an α-βswap move. The algorithm ends when no swap moves increasing the likelihood can be performed. α-expansions. This method iterates over the classes αin Lperforming α-expansions, i.e. changing the class assigned to a node from L¯α∈L−αto the class α. Thus, for each class, graph cuts are used to compute the minimum cut of the graph Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015. IX Hc= (Vc, Ec), where in this case Vc={V¯α, s, t}is the set of nodes not assigned to the class αplus the source sand the sink t, and Ec={eij ∈E|(yi6= α)∩(yj6=α)}∪{es→k, ek→t,∀k∈V¯α}. The nodes connected to the source sin the minimum cut produce an α-expansion, i.e. they replace their assigned class by α, while those linked to the sink tkeep their initial class. This process is repeated until no α-expansion can increase the current expected likelihood. Message passing methods. The message passing approach, also called Belief Propagation (BP) or max-product [22], is based on the exchange of statistical information among related nodes. This is performed by passing messages from node yito node yj, denoted as mij(yj), indicating the belief of node yiabout the belonging class of node yj. These messages are computed in the following way: mt ij =U(yi, xi,ω)I(yi, yj, xi, xj,θ)Y yk∈NH(yi)\yj mki(yi) (9) where NH(yi)\yjis the set of neighbors of yiin the graph Hless yj, and tis an iteration counter. Thus, the BP algorithm keeps sending messages between nodes following a certain message scheduling until the graph is calibrated, i.e. the messages exchanged between nodes are the same in two consecutive algorithm iterations. Once calibrated, the belief of each node is computed as: b(yi) = κU(yi, xi,ω)Y yj∈NH(yi) mji (10) being κa normalization component so the beliefs for node yisum to 1. Then, each node yiis assigned to the class with the highest belief value in b(yi). In the case of tree-structured graphs, such a message updating rule yields the optimal maximum. On the other hand, when it is applied to graphs with loops it adopts the name of Loopy Belief Propagation (LBP), and it is able to approximate a solution with a reasonable success. Next, we briefly describe the Tree-Based Reparametrization message passing algorithm (TRP) [21]. Tree-Based Reparametrization. This method pursuits a more global exchange of statistical information, not only between related nodes, aiming to reach a faster calibration even in cases where traditional BP methods fail. For that, a set of trees T={T1, .., Tt}are spanned over the original graph H={V, E}in such a way that every node in Vbelongs to (at least) one tree. Once the set of trees Tis obtained, the algorithm iteratively selects a tree and calibrates it, keeping fixed all the messages from the variables out of the tree. The calibration of a tree can lead to the miscalibration of other trees, so the algorithm has to be repeated until global calibration is reached. Once calibrated, the inference results are obtained in the same way as the original LBP algorithm. The interested reader can refer to [21] for more detail. Draft Version. Final version published in The Third Workshop on Recognition and Action for Scene Understanding (REACTS), 2015.