Two-Channel Filter Banks on Joint Time-Vertex Graphs with Oversampled Graph Laplacian Matrix

Probleemstelling

Conventionele methoden voor het verwerken van signaal op grafen (Graph Signal Processing - GSP), zoals kritisch bemonsterde graf-filterbanken, stuiten op beperkingen wanneer ze worden toegepast op gezamenlijke tijd-vertex signalen (bijvoorbeeld video's of dynamische netwerken).

• Beperking van bestaande methoden: Om een filterbank toe te passen, moeten niet-bipartiete grafen vaak worden opgesplitst in bipartiete subgrafieken. Deze opdeling vereist dat de oorspronkelijke graf wordt gescheiden in subsets van knopen en randen, wat betekent dat niet alle ruimtelijke en temporele randen in één enkele transformatiestap volledig worden benut.
• Verlies van structuur: Deze fragmentatie leidt tot een minder efficiënte representatie van de complexe ruimtelijk-temporele relaties en kan de kwaliteit van reconstructie en ruisreductie beïnvloeden.
• Doel: Er is behoefte aan een raamwerk dat de volledige structuur van de oorspronkelijke graf behoudt, redundante (oversampled) representaties mogelijk maakt voor robuustheid, en een eenzijdige transformatie toestaat zonder het opsplitsen van de graf in losse subgrafieken.

Methodologie

De auteurs introduceren een nieuw raamwerk gebaseerd op een gezamenlijke tijd-vertex oversamplede graf-Laplaciaan-matrix. De kern van de methode omvat de volgende stappen:

1. Oversamplede Laplaciaan:

   • In plaats van de graf te splitsen, wordt de graf uitgebreid door extra knopen en randen toe te voegen. Dit creëert een "oversamplede" versie van zowel de ruimtelijke (vertex) als de temporele domeinen.
   • Voor het temporele domein (vaak gemodelleerd als een ringgraf) wordt een strategie ontwikkeld om een bipartiete structuur te creëren, zelfs bij oneven aantallen tijdstippen, door knopen te dupliceren.
   • De gezamenlijke Laplaciaan ($\tilde{L}_J$) wordt gedefinieerd als de Kroneckersom van de oversamplede temporele Laplaciaan ($\tilde{L}_T$) en de oversamplede vertex-Laplaciaan ($\tilde{L}_G$):
     $$\tilde{L}_J = \tilde{L}_T \otimes I_{N_1} + I_{T_1} \otimes \tilde{L}_G$$
   • Dit behoudt de scheidbaarheid van het spectrum, maar introduceert redundantie.

2. Twee-kanaals Filterbank Ontwerp:

   • Er wordt een twee-kanaals oversamplede graf-filterbank ontworpen die werkt op deze uitgebreide structuur.
   • De analyse- en synthesefilters worden gedefinieerd in het spectrale domein van de oversamplede Laplacianen.
   • Perfecte Reconstructie: De filters voldoen aan spectrale voorwaarden (quadrature mirror filters) die perfecte reconstructie garanderen op bipartiete grafen, zelfs in de gezamenlijke tijd-vertex ruimte.

3. Efficiënte Uitbreiding via K-Coloring:

   • Om de oversamplede bipartiete structuur te realiseren voor willekeurige grafen, wordt een K-coloring strategie gebruikt.
   • Tijd-domein: Een ringgraf wordt gekleurd (3-kleuren voor oneven ringen) en vervolgens uitgebreid tot een bipartiete structuur door duplicatie van knopen.
   • Vertex-domein: Bestaande K-coloring methoden (zoals Harary-algoritme) worden gebruikt om de graf te partitioneren en te dupliceren.
   • Gezamenlijke uitbreiding: De tensorproduct van de uitgebreide tijd- en vertex-grafen vormt de uiteindelijke gezamenlijke graf. Deze methode behoudt alle oorspronkelijke connectiviteitsrelaties (randen) en zorgt voor een consistente spectrale representatie.

Belangrijkste Bijdragen

• Gezamenlijke Oversamplede Laplaciaan: Introductie van een operator die oversampling uit het vertex-domein uitbreidt naar het temporele domein, waardoor de oorspronkelijke grafstructuur volledig behouden blijft terwijl redundantie wordt ingevoerd.
• Twee-kanaals Filterbank: Ontwerp van een filterbank die voldoet aan de voorwaarden voor perfecte reconstructie op bipartiete grafen en oversampling implementeert in zowel tijd als ruimte via een K-coloring strategie.
• Unificatie van Ruimte en Tijd: Een raamwerk dat signaalverwerking en beeld/video-ruisreductie verenigt door beelden te modelleren als grafen en tijd als een extra dimensie, waarbij alle ruimtelijk-temporele relaties in één stap worden verwerkt.

Resultaten

De auteurs hebben hun methode uitgebreid getest op drie gebieden:

1. Reconstructie van Epidemie-simulaties:

   • Toepassing op het Minnesota Road Network met SEIRS-epidemie-modellen.
   • De oversamplede filterbank presteerde significant beter dan kritisch bemonsterde methoden, Graph-QMF en GraphBior, met een veel lagere gemiddelde kwadratische fout (MSE) bij reconstructie.

2. Ruisreductie van Grafsignalen:

   • Getest op het Yale Coat of Arms (geometrische structuur) en het Minnesota Road Network (complexe topologie) met toegevoegde Gaussische ruis.
   • De oversamplede methode behaalde consistent de hoogste Signaal-Ruisverhouding (SNR) over alle ruisniveaus, wat wijst op superieure robuustheid en fideliteit.

3. Beeld- en Videoruisreductie:

   • Beeld: Toepassing op handgeschreven cijfers (0-6 en 1-7) met interpolatie tussen frames. De oversamplede methode onderdrukte ruis effectiever terwijl randen en details beter behouden bleven.
   • Video: Toepassing op een "walking" video-sequentie. De oversamplede filterbank leverde een SNR van 25.85 dB op, vergeleken met 24.55 dB voor de kritisch bemonsterde versie.
   • Trade-off: De methode introduceert een hogere rekenkosten (tijd) door de redundantie, maar de verbetering in kwaliteit rechtvaardigt dit voor toepassingen waar precisie cruciaal is.

Betekenis en Impact

Dit werk is significant omdat het een fundamentele beperking van bestaande graf-filterbanken oplost: de noodzaak om grafen te fragmenteren om filterbank-operaties uit te voeren.

• Behoud van Structuur: Door alle randen in één enkele transformatiestap te behouden, wordt de fysieke en structurele coherentie van de data (zoals beweging in video's of interacties in netwerken) beter vastgehouden.
• Robuustheid: De ingevoerde redundantie (oversampling) maakt het systeem robuuster tegen ruis en verbetert de reconstructie-kwaliteit aanzienlijk.
• Toepassingsbereik: Het raamwerk opent de deur voor geavanceerde toepassingen in beeldherstel, video-analyse, en het modelleren van complexe dynamische systemen (zoals epidemieën of verkeersstromen) waarbij zowel ruimtelijke als temporele afhankelijkheden cruciaal zijn.

Kortom, de paper biedt een theoretisch onderbouwd en empirisch bewezen raamwerk dat de grenzen van grafgebaseerde signaalverwerking voor tijdsafhankelijke data verlegt.