LBP and irregular graph pyramids

LBP and Irregular Graph Pyramids Martin Cerman , Rocio Gonzalez-Diaz , and Walter Kropatsch 1PRIP Group, Vienna University of Technology, 1040 Wien, Austria [email protected], [email protected] 2Applied Mathematics Department, School of Computer Engineering, University of Seville, Seville, Spain [email protected] Abstract. In this paper, a new codification of Local Binary Patterns (LBP) is given using graph pyramids. The LBP code characterizes the topological category (local max, min, slope, saddle) of the gray level landscape around the center region. Given a 2D grayscale image I,our goal is to obtain a simplified image which can be seen as “minimal” representation in terms of topological characterization of I.Forthis,a method is developed based on merging regions and Minimum Contrast Algorithm. Keywords: Localbinarypatterns·Irregular graph pyramid ·Primal and dual graph ·Topological characterization ·Minimum contrast algorithm 1 Introduction Given a grayscale digital image I, the Local Binary Pattern LBP (I)[12,13]is a grayscale digital image used to represent the texture element at each pixel in I. This is currently the most frequently used texture descriptor [18] with outstanding results in applications ranging from segmentation and classification [15], object detection [11] to gender classification [16]. Typically the LBP operator is applied to all 3×3 image windows of the considered texture (region). Then the histogram provides the characteristic features of the texture. After training the feature space with the textures of interest new textures can be classified with very good discrimination. While the LBP code of a 3 ×3 window needs 8 bits for a single code, larger windows need more bits or even a varying number of bits if a multiresolution approach is chosen. The new encoding overcomes this drawback by transferring the code from the pixels to the neighbor relations (edges of the neighborhood M. Cerman—Acknowledges the support of the PRIP Club, the organization of friends and promoters of Pattern Recognition and Image Processing activities, Vienna, Austria. R. Gonzalez-Diaz—Author partially supported by IMUS, Spanish Ministry under grant MTM2012-32706 and ESF ACAT program. c 688 M. Cerman et al. graph). We propose a new equivalent encoding using one bit per edge of the graph. It is known that the LBP encodes the basic topological categories of a digital image’s landscape, e.g. extrema, saddle points, plateaus and slopes. After the contraction of all plateaus, these categories can be identified by simple local detectors except for the saddle points. In a discrete image a saddle can be either an identified pixel or a 2×2 non-well composed configuration. As the first major novelty introduced in this paper, we show a way to handle also such situations. We further propose a repetitive contraction process leading to hierarchy of successively smaller graphs, a graph pyramid, preserving the basic topological categories in a substantially smaller graph structure. The second novelty in this paper is the definition of a minimum contrast representative (MCR) image. It stands for the large class of all possible images that produce the same LBP codes and, consequently, also the same LBP histograms. This may allow to understand the trained classifiers since it defines the equivalence class of images of the trained class. The paper is organized as follows: In Section 2, the topological category of the gray level landscape around a pixel ccharacterized by its LBP code, is defined. Section 3recalls irregular graph pyramids. In Section 4, we introduce the notion of well-composed images and explain how any image can be made wellcomposed by inserting a few dummy regions. The goal of the rest of the sections is to obtain a “minimal” representation of a given image in terms of topological characterization. Our idea is to merge pixels (or regions, in general) that provide redundant information, to create the pyramid. The first step in the process is to remove the asymmetry caused by the sign function (see Eq. (1)). For this, in Section 5, we merge regions with same gray value (plateaus). After merging all plateaus, we define the notion of structurally redundant edges that should be removed to reach our goal. In Section 6, we define the topological category of a region. Section 7is devoted to a particular topological category named singular slope that can be merged without changing the topological category of the rest of the regions. Finally, in Section 8, we adapt Minimum Contrast Algorithm given in [17] to be applied to our pyramid in order to obtain a “minimal” representation of the image. Section 9is devoted to conclusions, experiments and future works. 2 Local Binary Patterns (LBP) The intensity of a pixel p=(x, y), denoted by g(p), is expressed within a given range between a minimum and a maximum, inclusive. Without loss of generality we will work with 8 bits, i.e., we will suppose that the range is [0,255]. The standard LBP code [12] is computed for a (center) pixel as in Eq. (1) where Pis the number of neighbors, Ris the distance between the center pixel and the neighbors (we assume 1 here), cis the center pixel of the operator and pis the local neighbor indexed by p. The basic operator uses the sign function s(x)=1ifx≥0ands(x) = 0 otherwise. LBP and Irregular Graph Pyramids 689 LBPP,R = P−1  p=0 s(g(p)−g(c))2p.(1) In this paper, the 4 neighbors (on its top, bottom, right, left) of each pixel are considered for comparison. That is, follow the 4 pixels along a circle (for example, clockwise). Where the center pixel’s gray value is greater than the neighbor’s gray value, write 0. Otherwise, write 1. Example: 113 240 23 20 25 12 15 30 40 ⇒ 1 0250 1 ⇒0101 ⇒9 The 4-neighbor LBP codification has been used in the past for solving problems in Image Processing and Analysis such as, for example, face detection and recognition [6], or iris extraction [5]. The LBP code characterizes the topological category of the gray level landscape around the center pixel. A pixel is a local maximum if the LBP code is composed just by 0s. A local minimum produces an LBP code only with 1s. Notice however that a local minimum can also be created by a plateau (a region composed by neighboring pixels sharing the same gray value) due to the asymmetry of the sign function s.Itisaslope if there is exactly one transition from 0s to 1s or 1s to 0s in its LBP code. Otherwise, it is a saddle. 3 LBP Codes and Irregular Graph Pyramids Aregion adjacency graph (RAG) encodes the adjacency of regions in a partition. A vertex vis associated to each region r. Vertices of neighboring regions are connected by edges. Classical RAGs do not contain any self-loops or parallel edges. An extended region adjacency graph (eRAG) is a RAG that contains the so-called pseudo edges, which are self-loops and parallel edges used to encode neighborhood relations to a region completely enclosed by one or more other regions [7]. The dual graph of an eRAG Gis denoted by ¯ G(Gis said to be the primal graph of ¯ G). The edges of ¯ Grepresent the boundaries (borders) of the regions encoded by G, and the vertices of ¯ Grepresent points where boundary segments meet. Gand ¯ Gare planar graphs if they represent a 2D decomposition into regions. There is a one-to-one correspondence between the edges of Gand the edges of ¯ G, which induces a one-to-one correspondence between the vertices of Gand the 2D cells (regions) of ¯ G. The dual of ¯ Gis again G. The following operations are equivalent: edge contraction in Gwith edge removal in ¯ G, and edge removal in Gwith edge contraction in ¯ G. Edge removal preserves the topology (i.e., regions are always homeomorphic to disks) [3]. A (dual) irregular graph pyramid [7,8] is a stack of successively reduced planar graphs P={(G0,¯ G0),...,(Gn,¯ Gn)}. Each level (Gk,¯ Gk),0<k≤nis 690 M. Cerman et al. (a) grayscale image (b) well-composed (c) merged plateaus (d) MCR Fig. 1. An 8-bit grayscale image (highlighted grayscale values) is (b) made wellcomposed. (c) Plateaus are merged (for color legend see Fig. 3(c)) and (d) Minimum Contrast Algorithm produces the minimum contrast representative (MCR in Section 8). obtained by first contracting edges in Gk−1(removal in ¯ Gk−1), if the corresponding regions should be merged, and then removing edges in Gk−1(contraction in ¯ Gk−1) to simplify the structure. In this paper, pixels are considered unit-square regions, 4-neighborhood is used for constructing the RAG and each vertex vof the RAG associated to each region ris labeled with the gray value of the region, i.e., g(v):=g(r). 4 Creating Well-Composed Images A 2D image is well-composed [9] if it does not contain the following non-well composed configuration (modulo reflection and 90-degree rotation): a b c d where g(a)<g(b), g(a)<g(c), g(d)<g(b)andg(d)<g(c). (2) Lemma 1. If the image is well-composed, then the topological category provided by LBP4,1is the same as LBP8,1. Proof. Consider the following 3×3block a d x b e h c f i . The topological class of eusing LBP4,1is given by b,d,f,andh.LBP 8,1is additionally given by a,c,x,and i. The topological category of LBP8,1is the same as LBP4,1, if by adding the diagonal 8-neighbors to LBP4,1the number of transitions from 0s to 1s or 1s to 0s does not change. In the following we show that any addition of a diagonal element, which would change the topological class, causes the image to become non-well composed (modulo reflection and 90-degree rotation): –Local minimum (resp. maximum) is defined by g(e)<g(p)(resp.g(e)> g(p)) for p=b, d, f, h.Ifg(e)>g(q)(resp.g(e)<g(q)) for q=a, c, x or i, the image becomes non-well composed. –Slope is defined by either: LBP and Irregular Graph Pyramids 691 (a) input (b) merged plateau (c) removed edges Fig. 2. The plateaus of an image with highlighted values are first merged and then structurally redundant edges are removed. •g(e)>g(b),g(f),g(h)andg(e)<g(d)(resp.g(e)<g(b),g(f),g(h) and g(e)>g(d)). If g(e)<g(c)org(e)<g(i)(resp.g(e)>g(c)or g(e)>g(i)) the image becomes not well-composed. Here, g(a)andg(x) are irrelevant. •g(e)<g(b),g(d)andg(e)>g(f),g(h). If g(e)>g(a)org(e)<g(i)the image becomes not well-composed. Here, g(c)andg(x) are irrelevant. –Saddle (resp. plateaus) is defined by g(e)>g(b),g(h)andg(e)<g(d),g(f) (resp. g(e)=g(b)=g(d)=g(h)). Here g(a), g(c), g(x), and g(i) are irrelevant.  The main problem in a non-well composed configuration like Eq. (2), is that the relation between aand d(resp. band c) cannot be deduced from the relation of 4-adjacent regions. To solve this, we insert a new “dummy” region rin the center of the non-well composed configuration: a b r c d . The new region rwith a new gray value g(r) reflects the relations between a, b, c, d and in a way that the 8-connectivity LBP code can be deduced from the LBP code of the modified configuration. Without loss of generality, suppose that g(a)≤g(d)<g(b)≤g(c). Following cases can occur: 1. g(a)=g(d)<g(b)=g(c)(resp.g(a)<g(d)<g(b)<g(c)). In this case, the vertex vrepresents a saddle. Set g(r)=g(d)+g(b) 2. We have that g(a)= g(d)<g(b)+g(d) 2<g(b)=g(c)(resp.g(a)<g(d)<g(b)+g(d) 2<g(b)<g(c)). Therefore, the LBP code of ris 0101 which is a saddle and all three new vertices have degree 3 and, hence, are well-composed. 2. g(a)=g(d)<g(b)<g(c)(resp.g(a)<g(d)<g(b)=g(c)). Set g(r)=g(d) (resp. g(r)=g(b)). In our process, regions a, r, d (resp. b, r, c) form a plateau. See Fig. 1(a) and 1(b). 5 Merging Plateaus and Removing Edges The first step in our process to obtain a simplified image with the same topological information as the original, is to merge plateaus. This way, by contracting adjacent vertices with same value in the primal graph (i.e., merging neighboring 692 M. Cerman et al. (a) after merging plateaus (b) after removing edges s s c s s s minima maxima doubly-singular slopes singular slopes other slopes saddles (c) vertex colors Fig. 3. Removing structurally redundant edges from the primal graph. regions with same value in the dual), we remove the asymmetry caused by the sign function. See Fig. 2(b). After merging all plateaus, a direction can be associated to each non-self-loop edge between different vertices of the primal graph G: (u, v)∈Ehas direction u→viff g(u)>g(v). Proposition 1. After merging plateaus, G\{self-loops}is a directed graph such that: (a) Gdoes not contain directed cycles. (b) Vertices in ¯ Gdo not increase degrees. Proof. (a) Suppose that Ghas a directed cycle u0→u1→···→un=u0. Then u0>u 1>··· >u n=u0, which is a contradiction. (b) Merging plateaus in G consists of removing edges and merging vertices of degree ≤2in ¯ G. Therefore, vertices in ¯ Ghave degree 3 or 4.  An oriented edge (u, v)∈Eis considered ”structurally redundant” if there exists a dual vertex w∈Vbounded by (u, v) and a directed path p(u, v)fromu to v. Structurally redundant edges can be removed in G(see Fig.2(c) and 3(b)). Finally, the notion of well-composed configurations can be extended to regions in ¯ Gdue to Prop. 1(b). 6 Topological Category of Regions After merging plateaus, in the same way as for pixels, we can define the topological category of a vertex vof Gby considering the edges incident to v. See Fig. 1(c) and 3(a). Following the edges incident to v: –vis a local minimum if it is the head of all the edges incident to it. –vis a local maximum if it is the tail of all the edges incident to it. –vis a doubly-singular slope if it has degree two and it is the tail of one of the edges incident to it and the head of the other. –vis a singular slope if it has degree greater than two and it is the tail (resp. head) of exactly one edge incident to it and the head (resp. tail) of the others. –vis a slope if vis the tail of the first edges incident to it and the head of the others, clockwise or counter-clockwise. –vis a saddle otherwise. LBP and Irregular Graph Pyramids 693 (a) graph -plateaus (b) -redundant edges (c) -singular slopes (d) minimal graph Fig. 4. The primal graph Gis successively reduced by merging plateaus and (doubly)- singular slopes. Merge operations and removal of structurally redundant edges are applied in an alternating fashion. The last image is considered “minimal”. Proposition 2. After removing redundant edges, the topological category of the vertices of Gmay be simplified: singular slopes may change to doubly-singular slopes, and slopes to singular slopes (see Fig. 2(c), 3(b) and 4(b)). Nevertheless, local maxima, minima and saddles are always preserved in the primal graph. Proof. For each structurally redundant edge e=(u, v)∈Ethere exists a monotonic path connecting uto v. Therefore the removal would not disconnect an extremum. And since it is monotonic, the extremum remains extremum. Assume the endpoint vof a structurally redundant edge e=(u, v) is a saddle. The last directed edge q=(vk,v) of the alternative path p(u, v)=(u, x0,...,q) must have the same orientation as (u, v) due to the monotonicity of the path. Since the bounded dual cell wdoes not contain any hole both eand qsucceed each other at the saddle v. Since they both are either below or above the saddle the removal of ewould not change the property of the saddle.  7 Merging Singular Slopes After merging plateaus, a direction is associated to the edges of the primal graph and a topological category to its vertices. Structurally redundant edges are then removed and the topological category of the vertices is updated. Further steps in our process to obtain a simplified image with same topological information as the original, should remove topologically redundant information by merging regions. In general, a region obtained after merging slopes around a local maximum (resp. minimum) is not a local maximum (resp. minimum). Singular slopes make an exception. Merging singular slopes propagates well around local extrema since a local extremum in the surrounding regions often is or becomes a singular slope. However non-well composed configurations (corresponding to saddles in the dual graph) can block propagation. This is why we insert dummy regions in non-well composed configurations. Prop. 3asserts that contracting a singular slope pto a vertex qin the primal graph, does not change the topological category of q. 694 M. Cerman et al. Proposition 3. Consider a vertex pwhich is a singular slope in the primal graph. Let Ebe the set of edges incident to p.Letpbe the head (resp. tail) of exactly one edge e∈Eand it is the tail of the rest. Let qbe the tail (resp. head) of e. Then the vertex obtained after contracting pto q(i.e., after merging the two associated regions in the dual graph) inherits the topological category of the region q, i.e. local max, min, saddle or slope. Proof. After contracting pto q, the edge eis replaced by the set of edges E\ein such a way that qis the tail (resp. head) of all these edges. Since qwas the tail (resp. head) of e, then, the topological category of qdoes not change. There is no inconsistency in the new graph: Let wbe the head (resp. tail) of one edge in E\e. Then g(w)<g(p)<g(q)(resp.g(w)>g(p)>g(q)), therefore g(w)<g(q) (resp. g(w)>g(q)), e.g. no new oriented cycle has been generated.  Conjecture 1. The result of merging all singular slopes does not depend on the order we merge. Observe that no new singular slopes can appear after merging singular slopes, since the topological category of the rest of the vertices remains invariant. But, new structurally redundant edges can appear. Therefore, the removal of structurally redundant edges and merging singular slopes can be repeated until no more reductions are possible. Finally, surviving slopes are merged to saddles. This way, we obtain an irregular graph pyramid. On the top of the pyramid, only local maxima, minima and saddles can appear. Besides, the number of local maxima, minima and saddles of the original and reduced image coincide (see Fig. 4). Note that after merging a singular slope p, no “corner” adjacent regions with same gray values could become adjacent later since it would mean that p would have at least two 0s in its LBP code. Besides, as a result after contracting plateaus, the reconstructed LBP code is defined for regions thus having as many bits as adjacent regions. Moreover, after merging all plateaus, the LBP codes are symmetric, and, the operations “image complement” and “LBP code” for regions are commutative. Finally, observe that after merging all singular slopes, each slope has at least two 1s and two 0s in its LBP code. 8 Reconstruction - Representative Image In [17] and much earlier in [10], the authors leverage an inverse problem approach to show that it is possible to directly reconstruct the image content from Local Binary Patterns. For this aim, ascending and descending monotonic paths are considered. Their algorithm, MCA1assumes a minimum contrast of one between two successive pixels; and reconstructs some of the contrast lost in the LBP process. Fig. 5(b) illustrates MCA: after initializing the result with 0, neighbors which should be higher (red >) are repeatedly incremented until all inequalities 1Minimum Contrast Algorithm. LBP and Irregular Graph Pyramids 695 (a) (b) MCA converts a digital image to a MCR. Fig. 5. (a) A monotonic ascending path with same inequalities than a minimum contrast path. (b) A naive illustration of MCA. are satisfied. This problem of reconstructing images from features is also dealt in [1] in which the image is encoded using LBD (Local Binary Descriptors) codes which are related but different to LBP codes. After merging plateaus and singular slopes and removing structurally redundant edges, our image is decomposed in not-necessarily squared regions. In this section we show that the method explained in [17] can be translated in terms of primal and dual graphs. The key is that LBP categories of the MCR2must be equal to those of original image. For this, longest monotonically increasing (decreasing) paths from local minima (maxima) are computed. Definition 1. Given an image I, a monotonic ascending path is a sequence p1,p 2,...,p nof regions such that: (1) piis adjacent3to pi−1and (2) g(pi−1)< g(pi),for1<i≤n. Whenever g(pi−1)>g(pi),for1<i≤n, the path is called monotonic descending (see Fig. 5(a)). To simulate MCA on our graph after contracting plateaus we initialize all vertices with 0. We then repeat following update operation for every oriented edge (u, v): replace g(v) by the maximum of g(v)andg(u) + 1 until no further change occurs. When starting with maxima we initialize with 255 and repeatedly replace g(u) by the minimum of g(u)andg(v)−1. In Fig. 1(d) a naive example of the application of MCA is given. This process opens a door to what we call representative image.LetIbe an image and LBP (I) its associated image of LBP codes. There is a whole set of images ρ(I) for which the LBP codification is identical. Let LBP −1 min(I)be the image obtained after applying MCA on all monotonic ascending paths, and LBP −1 max(I) be the image obtained from all monotonic descending paths. Then both LBP −1 min(I)andLBP −1 max(I) can be used to represent ρ(I). In particular LBP −1 min(I)∈ρ(I) and it is the smallest LBP −1 min(I)≤Jfor all J∈ρ(I). Analogously, LBP −1 max(I)∈ρ(I) and it is the largest LBP −1 max(I)≥Jfor all J∈ρ(I). Fig. 6shows the original image Iand the two representative images. Notice, how visually different these images from the same LBP class may look. Proposition 4. For any two images I,J ∈ρ(I),I=Jthe property LBP −1 min(I)=LBP −1 min(J)and LBP −1 max(I)=LBP −1 max(J)holds. 2Minimal Contrast Representative. 3In the image we assume 4-adjacency while edges encode adjacency in the graph.