hp-Adaptive Image Approximation using Binary Wedge Partitioning Trees

This thesis presents an adaptive lossy compression framework for graph signals defined over metric spaces, with a specific focus on digital image compression. The proposed methodology bridges two distinct mathematical paradigms: Binary Wedge Partitioning (BWP) trees, which perform geometric domain subdivision to capture edge alignment and boundary features, and Peter Binev's theoretical hp-adaptive approximation framework. By combining spatial refinement (h-adaptivity) with local polynomial approximation of increasing complexity (p-adaptivity), the algorithm dynamically decides at each step whether to partition a region or increase the local polynomial degree using a greedy search strategy that guarantees near-best approximation performance.

Questa tesi presenta un framework di compressione lossy adattiva per segnali su grafi definiti su spazi metrici, con una specifica applicazione alla compressione di immagini digitali. La metodologia proposta unisce due paradigmi matematici distinti: gli alberi di Binary Wedge Partitioning (BWP), che effettuano una suddivisione geometrica del dominio per catturare l'allineamento dei bordi e le caratteristiche strutturali, e il framework teorico di approssimazione hp-adattiva introdotto da Peter Binev. Combinando il raffinamento spaziale (h-adattività) con l'approssimazione polinomiale locale a complessità crescente (p-adattività), l'algoritmo decide dinamicamente a ogni passo se partizionare una regione o incrementare il grado del polinomio locale. Questo processo è guidato da una strategia di ricerca greedy che garantisce un'approssimazione ottimale (near-best).