GTT: Graph Template Transforms With Applications To Image .
GTT: Graph Template Transforms with Applicationsto Image CodingEduardo Pavez, Hilmi E. Egilmez, Yongzhe Wang and Antonio OrtegaSignal and Image Processing Institute, University of Southern California{pavezcar, hegilmez, yongzhew}@usc.edu, antonio.ortega@sipi.usc.eduAbstract—The Karhunen-Loeve transform (KLT) is knownto be optimal for decorrelating stationary Gaussian processes,and it provides effective transform coding of images. Althoughthe KLT allows efficient representations for such signals, thetransform itself is completely data-driven and computationallycomplex. This paper proposes a new class of transforms calledgraph template transforms (GTTs) that approximate the KLT byexploiting a priori information known about signals representedby a graph-template. In order to construct a GTT (i) a designmatrix leading to a class of transforms is defined, then (ii) aconstrained optimization framework is employed to learn graphsbased on given graph templates structuring a priori knowninformation. Our experimental results show that some instancesof the proposed GTTs can closely achieve the rate-distortionperformance of KLT with significantly less complexity.Index Terms—Graph-based transform, learning graphs, KLT,image coding, video codingI. I NTRODUCTIONTransform coding is an essential component for image/videocompression standards in which the discrete-cosine transform(DCT) is undoubtedly the most popular transform. This ismainly due to practical reasons given that a reasonable energycompaction can be attained with low-complexity implementations. However, the DCT is known to be optimal onlyfor the class of signals characterized by a highly correlatedfirst-order Gaussian Markov model. To support a broaderclass of signals, DCT/DST-based hybrid transforms [1] havebeen proposed and recently adopted in state-of-the-art videocoding standards such as HEVC [2]. This transforms aremore efficient for prediction residual signals, but are notwell adapted to other signals, for example, images includingtextures. As an alternative, the Karhunen-Loeve transform(KLT) provides optimal energy compaction for the data, butit is completely data-driven (i.e., obtained from an empiricalcovariance matrix) and does not have a fast implementation.In general, the empirical covariance is a dense matrix whichrequires signaling of a full matrix for different classes ofimage blocks, introducing a considerable amount of overhead;therefore these transforms may not be competitive in termsof rate-distortion performance. This naturally leads to theproblem of designing a transform that approximates KLT butwith less complexity and overhead.This paper proposes a new class of transforms called graphtemplate transforms (GTTs) that approximates inverse covari-ance matrices under sparsity constraints. For this purpose, firsta set of graph templates are constructed to define the sparsitypattern of the approximate inverse covariance matrices, orequivalently, to define connectivity pattern of a graph thatreveal inter-sample similarities among pixels. Then, a constrained optimization problem is solved to learn a graph byoptimizing the entries of the matrix of interest. Finally, theresulting matrix is used to derive GTTs.In the literature, several estimation methods have beenproposed to construct graphs from data for various applications. Friedman et.al. [3] propose graphical lasso to estimatesparse inverse covariance matrix. More recently in [4] and[5], a sparse combinatorial Laplacian matrix is estimated fromthe data samples by including a smoothness functional. Inthese works, a regularization parameter is used to controlsparsity, and this usually leads to arbitrarily connected graphs.However, in our work, we propose using a graph template toimpose a sparsity pattern, then the empirical inverse covarianceis approximated based on that template. There are severaladvantages of introducing a graph template for image/videocoding applications. Firstly, it can include prior informationabout different classes of block signals. For example, sampleswith high vertical correlation may benefit from a templategraph with less or no horizontal links. Secondly, the parameterestimation is more robust to lack of sufficient data or to noise,given the reduced number of total parameters to estimate.Finally, the number of graph parameters to transmit can bereduced with respect to an arbitrary graph transform or theKLT because the graph template is fixed and known a priori,and can be pre-stored at the decoder side.Recently, graph signal processing [6] has drawn a lot ofinterest for its ability to embed a priori signal informationin a graph. For block-based compression applications, it hasbeen demonstrated that graph-based transforms can providesignificant coding gains for piecewise-smooth images suchas depth maps [7], [8], [9] which exploit sharp boundariesin depth images to create graphs. In this paper, we showthat the proposed GTTs can be also used for natural imagecompression, focusing in particular on texture images, forwhich a piecewise smooth image model would not be suitable.The rest of the paper is organized as follows. Section IIdiscusses some preliminaries. The proposed GTTs and variousdesign methods are presented in Section III. Experimentalresults are described in Section IV. Section V draws some
conclusions.II. P RELIMINARIESA. Karhunen-Loeve transform (KLT)Consider a set of N image blocks formed as column vectorsx1 , x2 , · · · , xN of size K, with empirical covariance matrixS. We assume that these vectors have been chosen from aset of block signals sharing some properties/characteristicsof interest (e.g., they might have a structure such as edgeswith similar orientation). The empirical KLT is given by theeigenvector matrix Φ of S ΦΛΦt . This is the optimaldecorrelating transform for such signals.(a)(b)Fig. 1: Graphs (a) connecting each pixel with its four nearestneighboring pixels (4-connected) and (b) connecting each pixelwith pixels that are 1-hop away (8-connected).B. Graph-based Transform (GBT)Given an undirected graph G (V, E, Q) consisting of acollection of nodes V {1, 2, ., K} connected by a set ofedges E and matrix representation Q, where for i 6 j thelink (i, j) / E if and only if the weight Qij 0. We assumeQ is a symmetric positive semi-definite matrix. Note that ourgraph definition is different from the ones used in recent graphsignal processing literature, where Q is usually restricted tobe a graph Laplacian derived from an adjacency matrix [6].After deciding on a Q matrix, we first perform an orthonormaleigen-decomposition,Q UΛUt .(1)and the associated graph-based transform (GBT) is defined asthe orthonormal matrix U {u1 , ., uK }, with correspondingforward transform given byx̃ Ut x.(2)Note that, if we choose Q S or Q S 1 , then wesimply obtain the KLT basis. This is because any non-singulardiagonalizable matrix and its inverse have the same set ofeigenvectors.III. G RAPH T EMPLATE T RANSFORMSIn this section, we design three different kinds of Q matricesthat provide sparse approximations for the inverse covariancematrix, S 1 . Since the inverse covariance matrix is densein general, we introduce graph templates to set a sparsenonzero pattern for Q that approximates S 1 . We also presenttwo optimization problems where the graph templates imposeconstraints on the optimization. The resulting sparse matrix Qis used to construct the graph template transforms (GTT).A. Matrix TypesThe empirical covariance matrix is modeled as S 1 Q N, where Q is a sparse positive semi-definite matrix and Nan error term. Assuming the link set E is fixed, we considerthree types of matrices:1) Sparse inverse covariance (SIC): Q is a positive semidefinite matrix, where for every i 6 j Qij 0 when(i, j) / E.2) Generalized Laplacian (GL): Q is a GL matrix if it isa SIC matrix with non-positive off-diagonal terms, i.e.,Qij 0 if i 6 j.3) Combinatorial Laplacian (L): Q is a combinatorialLaplacian, if it is a singular generalizedP Laplacian withan all ones eigenvector, i.e., Qii j6 i Qij .Given a fixed edge set E, the SIC, GL and L matrices have adecreasing number of parameters. A sparse inverse covariancewill provide a better approximation for the inverse covariance,but given the arbitrary sign of the off diagonal entries, ituses more overhead. Also it is not straightforward to give aninterpretation as a weighted graph, where the edge weightshave positive and negative values. If the data were to followa Gaussian distribution and N 0, Q is called the precisionmatrix, and Qij 6 0 if and only if the random variables corresponding to nodes i and j are conditionally independent, givenall the other nodes, leading to a Gaussian Markov RandomField (GMRF) process. The generalized Laplacian has a fixedsign pattern, thus reducing the overhead. Furthermore, the offdiagonal elements can be interpreted as the edge similaritiesbetween pixels. The combinatorial Laplacian further reducesthe number of parameters, because its diagonal entries can bedirectly computed. Also, the first eigenvector associated withzero eigenvalue corresponds to DC component which is oftendesirable in image compression applications.B. Template selectionMany image processing applications have adopted thenearest-neighbor image model for natural image compression[10], and texture analysis [11]. In terms of our graph-based notation, this model is equivalent to unweighted 4-connected gridgraph as shown in Fig.1(a) which derives the traditional 2DDCT [12]. Different transforms can be obtained by choosingdifferent graphs like the one shown in Fig.1(b) which allowsdiagonal connections.Assuming the pixels are localized in an uniform grid, weuse three different graph templates (edge sets E), whosecorresponding weights are optimized1) 4-connected graph template (E4 ): Each pixel is connected to its 4 nearest neighbors which corresponds tohorizontal and vertical edges as shown in Fig.1(a).
2) 8-connected graph template (E8 ): This template extendsthe 4-connected graph template by allowing diagonalconnections so that each pixel is connected to its 8nearest neighbors as shown in Fig.1(b).3) 24-connected graph template (E24 ): This template connects each pixel to its 24 closest neighbors. This allowsconnections with farther pixels and in additional diagonal directions. One can show that, if the image blocks have size K K.The 8-connected graph template has E 2( K 1)(2 K 1) edges. Hence the SIC and GL matrices have E Knonzero entries, while the L matrix has E nonzero entries.Thus the parameter complexity of the GTT is O(K), scalinglinearly on the number of pixels per block. This is smallerthan the KLT, which requires K(K 1)/2 parameters to storea symmetric matrix (i.e., fully connected graph template).Different graph templates can be also used to define sparsitypatterns capturing other signal characteristics. Yet, we choosethree basic templates for simplicity. The optimization methodsused to design weights are discussed in the next section.C. Optimization methodTo find a matrix of interest Q, we solve one of the followingconvex optimization problems,(i) Sparse left inverse (SLI):Q arg min kAS IkF(3)A Γ(ii) Gaussian maximum likelihood (GML):Q arg min (log det(A) tr(SA))(4)A Γwhere Γ denotes the constraint set given by a matrix type- graph template pair. For example Γ(GL, E8 ) is the set ofall generalized Laplacians with edge set E8 . Note that theproblem in (3) approximates the inverse covariance matrixby a sparse left inverse (SLI). In (4), the problem abbreviated as GML can be interpreted as a constrained maximumlikelihood (ML) estimation under Gaussian-Markov assumptions. Hence, solving (4) is equivalent to approximating thedata as a GMRF with precision matrix Q. In [3], authorssolve minA Γ log det(A) tr(SA) λkAk1 , with A positivesemidefinite, where the extra term is included to promotesparsity in the solution. Our formulation in (4) is a constrainedversion with λ 0, because the 1 term is not necessary sincewe impose a fixed sparsity pattern. In practice these methodswould produce sparse graphs by zeroing out coefficients belowa certain threshold.IV. R ESULTSIn this section, we evaluate the performance of differentGTT designs by benchmarking against DCT and KLT in termsof rate-distortion (RD) performance. GTTs are investigatedextensively by selecting different (i) optimization methods,(ii) design matrices and (iii) connectivity constraints/patternswhose details are discussed in Section III.In our experiments, we use the USC-SIPI texture dataset11 USC-SIPIImage Dataset: http://sipi.usc.edu/database/(a)(b)Fig. 4: An example of 8-connected graphs designed for woodimage with (a) no rotation and (b) with 30 degree counterclockwise rotation. The darker colors correspond to largerweights.which includes thirteen Brodatz texture images and theirdifferent pre-processed versions. In particular, we choose allthirteen original Brodatz textures and their 30 degree counterclockwise rotated versions so that a total of 26 images areused. For each image, KLT and GTT transforms are designedbased on a covariance matrix generated using 4 4 or 8 8 nonoverlapping image blocks as data samples. Fig.4 illustrates twosample graphs associated to two different GTTs designed forwood image and its rotated version, respectively. As seen inFig.4, the graphs allow us to capture anisotropic behavior inimages by adjusting the edge-weights.The transforms are applied directly on the images and thetransform coefficients are first uniformly quantized and thenencoded using a symbol grouping-based arithmetic entropyencoder called AGP, which uses an amplitude group partitiontechnique to efficiently encode image transform coefficients[13]. The AGP encoder allows us to fairly compare theRD performance of different transforms since AGP can flexibly learn and exploit amplitude distribution of transformcoefficients. For ordering of the quantized coefficients, weemploy zig-zag scanning for DCT coefficients, and descendingand ascending order of eigenvalues are used for KLT andGTT coefficients, respectively. After decoding the quantizedtransform coefficients using AGP decoder, we reconstruct thetexture image and PSNR with respect to the original image iscalculated.The average RD performances of different transforms arepresented in Fig.2 and Table I in terms of PSNR and total bitsspent for encoding quantized transform coefficients per-pixel(BPP). Fig.2 compares GTTs generated based on differentdesign matrix types (L, GL and SIC) with different connectivity constraints against traditional DCT and KLT. Morecomprehensive results are available in Table I where we showpercent bit reductions gained by using GTTs and KLT atdifferent PSNR values (i.e., 28, 32 and 36 dBs) with respect tousing DCT. Note that, positive values in the table means thatbetter RD performance (bit reduction) is achieved comparedto using DCT. According to these results: Encoding performance of GTTs can closely approach thatof KLT with reduced number of parameters. For sparse graph templates, GL matrices lead to a betterperformance, while for dense graph templates (i.e., graphswith 24 or more connected templates) SIC matrices workbetter. The best results shown in Table I are similar for different
TABLE I: Average percentage reduction in bitrate (BPP) with respect to average bitrate obtained with 841.2472.8663.5191.4801.5742.4641.2444 4 block 8 8 block 1.41.600.20.40.6BPP0.811.21.41.6BPPFig. 2: Average PSNR vs. BPP results using GML method with (left) 4 and (right) 8 connected models for 4 4 0.20.40.60.811.2BPPFig. 3: PSNR vs. BPP results for wood image (left) with no rotation and (right) with 30 degree counter-clockwise rotation. block sizes, (i.e., 4 4 and 8 8), so our solutions scalenicely for larger blocks unlike KLT-based solutions.In terms of the optimization procedures, generally GMLmethod is better than SLI method.SLI method does not work well on Laplacian (L) matricesdue to convergence issues during the graph optimization,since L matrices are singular by definition. Therefore,corresponding results are omitted (see N/A in Table I).Moreover, Fig.3 illustrates the RD performance results forthe wood texture image. Note that for the image with norotation, DCT performs better than KLT and GTT, since theimage is mostly smooth and the pixel value discontinuitiesappear vertically. This is a very special case where KLT andGTT cannot produce effective transforms. On the other hand,KLT and GTT significantly outperform DCT for 30 degreerotated version of the same image where the discontinuities
appear diagonally. Note also that the performance of GTTclosely approaches to KLT.V. C ONCLUSIONSIn this paper, we have proposed a new class of transforms,called graph template transforms (GTT), to approximate theempirical KLT with a reduced number of parameters. Byintroducing the notion of graph templates, we add priorknowledge about signal classes. In terms of graph learning, wepropose and compare (i) three types of matrices to characterizethe graph, (ii) three graph templates to constraint connectivityof graphs, and (iii) two optimization methods to optimizeedge weights of a graph based on a given template. Ourexperimental results lead us to the following conclusions: We propose to use Gaussian maximum-likelihood (GML)method since it provides a better optimization for learningedge weights of a graph compared to sparse left inverse(SLI) method in general. For sparse graph templates (e.g., 4 or 8 connected templates), we suggest to optimize generalized Laplacian(GL) matrices using GML method. For dense graph designs, using 24 connected or moredense graph templates, we propose to optimize sparseinverse covariance (SIC) matrices using GML method. As we choose more dense graph templates, sparse inverse covariance (SIC) matrix can closely achieve therate-distortion performance of KLT. However, any transform design procedure should also consider the tradeoff between coding gain and transform signaling/storingoverhead.VI. ACKNOWLEDGEMENTThis work has been supported in part by LG Electronics,Inc. and by an USC Annenberg Graduate Fellowship.R EFERENCES[1] J. Han, A. Saxena, V. Melkote, and K. Rose, “Jointly optimized spatialprediction and block transform for video and image coding,” ImageProcessing, IEEE Transactions on, vol. 21, no. 4, pp. 1874–1884, 2012.[2] G. J. Sullivan, J. Ohm, W.-J. Han, and T. Wiegand, “Overview of thehigh efficiency video coding (HEVC) standard,” Circuits and Systemsfor Video Technology, IEEE Transactions on, vol. 22, no. 12, pp. 1649–1668, 2012.[3] J. Friedman, T. Hastie, and R. Tibshirani, “Sparse inverse covarianceestimation with the graphical lasso,” Biostatistics, vol. 9, no. 3, pp. 432–441, 2008.[4] C. Hu, L. Cheng, J. Sepulcre, G. El Fakhri, Y. M. Lu, and Q. Li, “Agraph theoretical regression model for brain connectivity learning ofalzheimer’s disease,” in Biomedical Imaging (ISBI), 2013 IEEE 10thInternational Symposium on. IEEE, 2013, pp. 616–619.[5] X. Dong, D. Thanou, P. Frossard, and P. Vandergheynst, “Learninggraphs from observations under signal smoothness prior.” [Online].Available: http://arxiv.org/abs/1406.7842[6] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregulardomains,” Signal Processing Magazine, IEEE, vol. 30, no. 3, pp. 83–98,2013.[7] W. Hu, G. Cheung, A. Ortega, and O. Au, “Multi-resolution graphfourier transform for compression of piecewise smooth images,” ImageProcessing, IEEE Transactions on, vol. 24, no. 1, pp. 419–433, 2015.[8] G. Shen, W.-S. Kim, S. K. Narang, A. Ortega, J. Lee, and H. Wey,“Edge-adaptive transforms for efficient depth map coding,” in PictureCoding Symposium (PCS), 2010. IEEE, 2010, pp. 566–569.[9] E. Martinez-Enriquez, E. Diaz-de Maria, and A. Ortega, “Video encoderbased on lifting transforms on graphs,” in Image Processing (ICIP), 201118th IEEE International Conference on, Sept 2011, pp. 3509–3512.[10] A. Sandryhaila and J. Moura, “Nearest-neighbor image model,” in ImageProcessing (ICIP), 2012 19th IEEE International Conference on, Sept2012, pp. 2521–2524.[11] R. C. Dubes and A. K. Jain, “Random field models in image analysis,”Journal of Applied Statistics, vol. 16, no. 2, pp. 131–164, 1989.[12] C. Zhang and D. Florêncio, “Analyzing the optimality of predictivetransform coding using graph-based models,” Signal Processing Letters,IEEE, vol. 20, no. 1, pp. 106–109, 2013.[13] A. Said and W. A. Pearlman, “Low-complexity waveform coding viaalphabet and sample-set partitioning,” in SPIE Visual Communicationsand Image Processing, 1997, pp. 25–37.
graph template transforms (GTTs) that approximate the KLT by exploiting a priori information known about signals represented by a graph-template. In order to construct a GTT (i) a design matrix leading to a class of transforms is
30 minutes. The IV tubing on your unit delivers 15 gtt/mL. What is the correct rate of flow in drops per minute? a. 15 gtt/min b. 20 gtt/min c. 25 gtt/min d. 30 gtt/min 6. An intravenous line has been inserted into a patient. Fluid is being delivered at a rate of 42 mL/h. How much fluid
The totality of these behaviors is the graph schema. Drawing a graph schema . The best way to represent a graph schema is, of course, a graph. This is how the graph schema looks for the classic Tinkerpop graph. Figure 2: Example graph schema shown as a property graph . The graph schema is pretty much a property-graph.
communications, providing clients with the services and capabilities that drive productivity across their organizations. GTT is a Tier 1 IP network, ranked in the top five worldwide, that connects its clients to any location in the world and any application in the cloud. GTT of fers a comprehensive
Oracle Database Spatial and Graph In-memory parallel graph analytics server (PGX) Load graph into memory for analysis . Command-line submission of graph queries Graph visualization tool APIs to update graph store : Graph Store In-Memory Graph Graph Analytics : Oracle Database Application : Shell, Zeppelin : Viz .
and Laplace transforms F(s) Z 0 f(t)e st dt. Laplace transforms are useful in solving initial value problems in differen-tial equations and can be used to relate the input to the output of a linear system. Both transforms provide an introduction to a more general theory of transforms, which are u
a graph database framework. The proposed approach targets two kinds of graph models: - IFC Meta Graph (IMG) based on the IFC EXPRESS schema - IFC Objects Graph (IOG) based on STEP Physical File (SPF) format. Beside the automatic conversation of IFC models into graph database this paper aims to demonstrate the potential of using graph databases .
1.14 About Oracle Graph Server and Client Accessibility 1-57. 2 . Quick Starts for Using Oracle Property Graph. 2.1 Using Sample Data for Graph Analysis 2-1 2.1.1 Importing Data from CSV Files 2-1 2.2 Quick Start: Interactively Analyze Graph Data 2-3 2.2.1 Quick Start: Create and Query a Graph in the Database, Load into Graph Server (PGX) for .
Automotive Finance Luxury Media Retail Sport Tech Move In the Decade of Possibility. Best Global Brands fl flfi Automotive 5 Welcome to Best Global Brands 2020 At a time of deep reflection, the deepest form of relevance is increasingly being driven by an uncompromising approach to fundamental human issues. Businesses that do not yet know, very specifically, which constituents they are .
