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

Resumo Técnico: Bancos de Filtros em Grafos de Tempo e Vértice com Matriz Laplaciana Sobreamostrada

1. Problema e Motivação

O processamento de sinais em grafos (GSP) tem evoluído rapidamente para lidar com dados estruturados em redes complexas. No entanto, muitos dados reais (como vídeos, comportamentos em redes sociais e dinâmicas de epidemias) evoluem tanto no tempo quanto no espaço (vértices), exigindo uma abordagem de sinais conjuntos tempo-vértice.

As limitações principais abordadas neste trabalho são:

• Subamostragem Crítica: Os bancos de filtros de grafos convencionais exigem que o grafo seja decomposto em subgrafos bipartidos. Para grafos não bipartidos arbitrários, isso implica particionar o grafo original, descartando arestas em cada estágio de transformação. Isso impede a exploração completa de todas as conexões temporais e espaciais em uma única etapa.
• Perda de Informação Estrutural: A decomposição em subgrafos bipartidos para subamostragem crítica pode levar a uma perda de informações estruturais e de bordas originais, prejudicando a representação multirresolução e a reconstrução perfeita.
• Necessidade de Redundância: Métodos existentes muitas vezes não conseguem balancear a eficiência computacional com a robustez necessária para tarefas como remoção de ruído em imagens e vídeos complexos.

2. Metodologia Proposta

Os autores propõem um novo framework unificado baseado em uma Matriz Laplaciana de Grafo Sobreamostrada Conjunta (Joint Time-Vertex Oversampled Graph Laplacian Matrix). A metodologia segue os seguintes passos:

• Definição do Operador Laplaciano Sobreamostrado:

  • Estende o conceito de sobreamostragem do domínio dos vértices para o domínio temporal.
  • Constrói um grafo bipartido estendido ($\tilde{G}$) e um grafo temporal estendido ($\tilde{T}$) adicionando nós auxiliares e arestas, preservando todas as arestas originais do grafo conjunto.
  • Define a matriz Laplaciana conjunta sobreamostrada ($\tilde{L}_J$) como a soma de Kronecker das matrizes Laplacianas normalizadas dos grafos estendidos: $\tilde{L}_J = \tilde{L}_T \otimes I_{N_1} + I_{T_1} \otimes \tilde{L}_G$.

• Estratégia de K-Cores para Extensão Bipartida:

  • Para lidar com grafos não bipartidos, utiliza-se uma estratégia de coloração de grafos (K-coloring).
  • Domínio Temporal: Modela-se o tempo como um grafo de anel. Se o número de amostras temporais for ímpar (não bipartido), aplica-se uma extensão baseada em 3 cores, duplicando nós para criar uma estrutura bipartida sobreamostrada que preserva a conectividade temporal.
  • Domínio Espacial (Vértices): Aplica-se o mesmo princípio de coloração K-cores ao grafo espacial.
  • Combinação Conjunta: O produto tensorial das extensões bipartidas temporais e espaciais garante que o grafo conjunto resultante seja bipartido, permitindo a aplicação de bancos de filtros sem descartar arestas.

• Projeto do Banco de Filtros de Dois Canais:

  • Desenvolve-se um banco de filtros de dois canais (baixa e alta frequência) operando no domínio conjunto tempo-vértice.
  • O sistema utiliza filtros de análise e síntese no domínio espectral (baseados nos autovalores do Laplaciano estendido).
  • Garante-se a Reconstrução Perfeita (Perfect Reconstruction) satisfazendo condições espectrais específicas nos domínios temporal e de vértice simultaneamente.
  • A abordagem é redundante (sobreamostrada), o que permite representações multirresolução mais ricas e estáveis.

3. Principais Contribuições

1. Novo Operador Laplaciano: Introdução da Matriz Laplaciana de Grafo Sobreamostrada Conjunta, que estende a sobreamostragem para o domínio temporal, preservando a estrutura original do grafo conjunto.
2. Banco de Filtros Redundante: Projeto de um banco de filtros de dois canais que realiza a sobreamostragem simultânea nos domínios de tempo e vértice, utilizando uma estratégia de K-coloração para garantir a estrutura bipartida necessária.
3. Aplicação em Tarefas de Processamento: Validação do framework em decomposição, reconstrução e, principalmente, remoção de ruído (denoising) de sinais de grafos, imagens estáticas e vídeos dinâmicos.
4. Preservação de Arestas: Diferente dos métodos críticos, a proposta mantém todas as arestas originais em uma única etapa de transformação, melhorando a fidelidade estrutural.

4. Resultados Experimentais

Os autores realizaram extensos experimentos comparando o método proposto com bancos de filtros de amostragem crítica, Graph-QMF e GraphBior.

• Reconstrução de Sinais de Grafos (Simulação de Epidemia):

  • Utilizando a rede rodoviária de Minnesota e um modelo SEIRS de propagação de epidemias.
  • O método sobreamostrado apresentou erros quadráticos médios (MSE) significativamente menores na reconstrução do sinal em comparação com os métodos críticos e existentes.

• Remoção de Ruído em Sinais de Grafos:

  • Testado em dados sintéticos (Brasão de Yale) e reais (Rede Rodoviária de Minnesota).
  • O método sobreamostrado alcançou consistentemente a maior Relação Sinal-Ruído (SNR) em todos os níveis de ruído, demonstrando maior robustez e fidelidade devido à redundância introduzida.

• Denoising de Imagens e Vídeos:

  • Imagens Estáticas: Testado em sequências de dígitos manuscritos (0-6 e 1-7). O método sobreamostrado preservou melhor as bordas e detalhes finos, superando a amostragem crítica em SNR.
  • Vídeos Dinâmicos: Testado em uma sequência de caminhada (75 quadros). O método alcançou 25.85 dB de SNR, superando a amostragem crítica (24.55 dB) e o sinal ruidoso (22.43 dB).
  • Custo Computacional: Houve um aumento no tempo de execução (de 0.79s para 1.07s no teste de vídeo), mas o ganho de desempenho justifica o custo para escalas moderadas.

5. Significado e Conclusão

Este trabalho representa um avanço significativo na interseção entre o Processamento de Sinais em Grafos (GSP) e o processamento de imagens/vídeos. Ao introduzir a sobreamostragem conjunta tempo-vértice, os autores superam a limitação fundamental da necessidade de decomposição em subgrafos bipartidos que descarta informações.

A principal implicação é que é possível realizar transformadas multirresolução e filtragem em grafos complexos e dinâmicos sem perder a conectividade original, resultando em uma representação mais rica e em uma reconstrução mais precisa. O framework proposto oferece uma base sólida para futuras aplicações em aprendizado de máquina em grafos, restauração de vídeo e análise de dados temporais em redes complexas, demonstrando que a redundância controlada é uma ferramenta poderosa para melhorar a qualidade do sinal em vez de ser apenas um custo computacional.