Designing sparse graph via structure tensor for fast transform in image compression

The graph Fourier transform (GFT)—adaptive to the signal structures of local pixel blocks—has recently been shown to be a good alternative to fixed transforms, e.g., the Discrete Cosine Transform (DCT), for image coding. However, the majority of proposed GFTs assume an underlying 4-connected graph structure with vertical and horizontal edges only. In this work, we propose a design methodology to select more general sparse graph structures and edge weights, on which GFTs are defined for block-based coding. Specifically, we first cluster blocks via the Lloyd-Max algorithm based on their principal gradients, which are eigenvectors of the computed structure tensors. For each cluster a graph template with edges orthogonal to the principal gradient is designed. Finally, optimal edge weights are computed assuming each template is a graph describing the inter-pixel correlation in a Gaussian Markov Random Field (GMRF). Experimental results show that GFTs derived from our graph templates lead to sparser signal representations and fewer encoding bits than DCT for a set of natural test images

È stato recentemente dimostrato che la graph Fourier transform(GFT) è una buona alternativa alle trasformate fisse, ad esempio la Discrete Cosine Transform, per la codifica di immagini. La maggior parte delle GFT proposte, però, considerano una struttura sottostante il grafo che sia 4-connected con solo edge verticali e orizzontali. In questo lavoro, proponiamo una metodologia di modellizzazione per selezionare strutture sparse di grafi generici e pesi degli edge, sui quali le GFT sono definite per codifiche block-based. Nello specifico, prima si esegue un Lloyd-Max clustering basato sui gradienti principali, che rappresentano gli autovettori degli structure tensor. Per ogni cluster viene generato un grafo con edge ortogonali al gradiente principale. Infine vengono calcolati i pesi ottimi degli edge, assumendo per che ogni grafo descriva la correlazione tra i pixel in un Gaussian Markov Random Field (GMRF). Risultati sperimentali dimostrano che i GFT ottenuti dai nostri modelli di grafi portano una rappresentazione del segnale più sparse e meno bit da codificare rispetto al metodo DCT, per un insieme di immagini naturali usate come test.