XXVI Simpósio Brasileiro de Telecomunicações
Rio de Janeiro, 4 Setembro 2008
Casamento Aproximado de Padrões
Multiescala com Segmentação Flexível e
Treino do Dicionário
Nelson Francisco, Nuno Rodrigues, Sérgio de Faria,
Eduardo da Silva, Vítor Silva and Manuel Reis
© 2005, it - instituto de telecomunicações. Todos os direitos reservados.
DEEC
Univ. Coimbra
O MMP
 O MMP (Multidimensional Multiscale Parser) é um algoritmo genérico de
compressão baseado em recorrência de padrões multiescala;
 Como não se baseia em qualquer pressuposto relativamente às
características da imagem a codificar, o MMP apresenta uma elevada
versatilidade em relação à imagem a comprimir;

Apresenta um desempenho consideravelmente superior ao dos algoritmos
baseados em transformadas na codificação de imagens de texto;
 A vantagem não se mantinha no entanto quando aplicado a imagens
naturais, o que motivou a sua evolução principalmente centrada para este
tipo de imagens.
XXVISimpósio Brasileiro de Telecomunicações
2 | Rio de Janeiro, 4 de Setembro 2008
O MMP
 A imagem é dividida em blocos
de dimensão NxM;
 Para cada bloco Xli, o algoritmo procura o elemento do dicionário Slj
que minimiza o custo Lagrangeano
da representação de Xli por Sli,.
Xl
Sl0
… …
Sli
SlL
J (T )  D( X il , S lj )  R(S lj )
XXVISimpósio Brasileiro de Telecomunicações
3 | Rio de Janeiro, 4 de Setembro 2008
O MMP
 O bloco Xli é então segmentado em 2
sub-blocos, X(l-1)L e X(l-1)R com metade do
tamanho do primeiro;
 O procedimento anterior é aplicado recursivamente a cada um dos sub-blocos
obtidos;
 Se a soma do custo associado aos dois
sub-blocos for inferior ao custo da representação do bloco original, este é
segmentado;
 Caso contrário, o bloco é representado S(l-1)0 … …
por Sli .
XXVISimpósio Brasileiro de Telecomunicações
4 | Rio de Janeiro, 4 de Setembro 2008
S(l-1)i1
S(l-1)i2
O MMP
 As segmentações sucessivas dão origem a uma árvore de segmentação
binária, que corresponde à representação óptima do bloco;
 Os nós segmentados são codificados com a flag 0;
 Os nós terminais são codificados com a flag 1 e são seguidos pelo índice
do dicionário seleccionado para representar o sub-bloco em causa.
0 1 i0 0 1 i1 0 0 i2 i3 1 i4
XXVISimpósio Brasileiro de Telecomunicações
5 | Rio de Janeiro, 4 de Setembro 2008
Actualização do Dicionário
Dicionário Adaptativo
+ Aproximação de padrões multiescala
= Codificação versátil com bom desempenho universal
XXVISimpósio Brasileiro de Telecomunicações
6 | Rio de Janeiro, 4 de Setembro 2008
MMP com esquema preditivo - MMP-I
 Combinação de esquemas de codificação preditivos com o MMP;
 Os modos de predição utilizados são essencialmente os mesmos usados
pelo H.264/AVC;
Mode 0:
Mode 1:
Mode 4:
Directional
Vertical Prediction
Horizontal Prediction
Vertical Down Prediction
Prediction Modes
 Os resíduos gerados são codificado com o MMP;
 A predição gera blocos mais uniformes e com uma distribuição probabilística
que favorece a adaptação do dicionário e o desempenho do algoritmo.
XXVISimpósio Brasileiro de Telecomunicações
7 | Rio de Janeiro, 4 de Setembro 2008
Optimização do dicionário adaptativo – MMP-II

Utiliza novas técnicas para optimização do dicionário:
•
•
•
•
•
Super-actualização do dicionário com transformacões geométricas;
Condicionamento estatístico do codificador aritmético;
Limitação de escalas;
Controlo de redundância;
Equalização de norma.
 Permitiu ganhos de desempenho, aliados à redução da complexidade
computacional do algoritmo, principalmente para imagens suaves.
XXVISimpósio Brasileiro de Telecomunicações
8 | Rio de Janeiro, 4 de Setembro 2008
MMP com Segmentação Flexível – MMP-FP
 Testes experimentais demonstraram que a direcção de segmentação tem
grande influência no desempenho do algoritmo;
 Foi implementado um novo algoritmo com direcção de segmentação
adaptativa, de modo a minimizar o custo Lagrangeano da representação
do bloco.
MMP-II
XXVISimpósio Brasileiro de Telecomunicações
9 | Rio de Janeiro, 4 de Setembro 2008
MMP-FP
Treino do dicionário - Motivação
 O MMP utiliza um dicionário inicial esparso, com blocos uniformes;
 A adaptação do dicionário aumenta seu poder de aproximação com a inserção de padrões mais diversificados;
 Na fase inicial da codificação, são normalmente usadas mais segmentações dos blocos a comprimir;
 Um aumento dos padrões do dicionário inicial permite melhorar o
desempenho do algoritmo, sobretudo para os blocos iniciais.
XXVISimpósio Brasileiro de Telecomunicações
10 | Rio de Janeiro, 4 de Setembro de 2008
Treino do dicionário - Conceito
 Dotar o dicionário inicial com um número mais alargado de padrões, com
probabilidade de utilização elevada;
 A codificação sequencial de várias imagem tenderá a convergir para um
conjunto restrito de blocos;
 Utilização de valores distintos para λ permite gerar os novos padrões
mais distribuídos entre as várias escalas do dicionário.
XXVISimpósio Brasileiro de Telecomunicações
11 | Rio de Janeiro, 4 de Setembro de 2008
Construção do dicionário treinado
 Foram definidos dois conjuntos de imagens de teste de modo a gerar dois
dicionários treinados independentemente;
Grupo I
Grupo II
 Codificação sequencial de cada grupo variando o parâmetro Lagrangeano
λ.
XXVISimpósio Brasileiro de Telecomunicações
12 | Rio de Janeiro, 4 de Setembro de 2008
Construção do dicionário treinado
 Todos os elementos usados na compressão de uma imagem são inseridos no dicionário inicial da imagem seguinte;
 Toda a informação relativa à probabilidade de utilização e condicionamento estatístico de cada um dos blocos é mantida e actualizada na
codificaçao das imagens seguinte;
 O dicionário resultante de cada iteração será composto por todos os
blocos usados na compressão das várias imagens de treino.
XXVISimpósio Brasileiro de Telecomunicações
13 | Rio de Janeiro, 4 de Setembro de 2008
Testes experimentais
 Cada dicionário de treino foi usado para codificar imagens não pertencente ao grupo de teste que lhe deu origem;
 Foram utilizadas duas abordagens na inserção dos blocos de treino no
dicionário inicial:
– Treino
I: Os blocos foram inseridos no contexto original da escala
onde foram criados;
– Treino II: Os blocos foram inseridos num novo contexto especialmente
destinados a receber os blocos provenientes do treino, criado para
cada escala.
XXVISimpósio Brasileiro de Telecomunicações
14 | Rio de Janeiro, 4 de Setembro de 2008
Resultados
Resultados para a Imagem Lena (PSNR)
 A inserção dos elementos no contexto original tende a gerar melhores resultados para taxas de compressão elevadas;
 Para taxas de compressão baixas, o condicionamento estatístico dos elementos provenientes do treino tende a limitar a adaptabilidade do dicionário.
XXVISimpósio Brasileiro de Telecomunicações
15 | Rio de Janeiro, 4 de Setembro de 2008
Resultados
XXVISimpósio Brasileiro de Telecomunicações
16 | Rio de Janeiro, 4 de Setembro de 2008
Resultados
XXVISimpósio Brasileiro de Telecomunicações
17 | Rio de Janeiro, 4 de Setembro de 2008
Resultados
Imagem PP1205
XXVISimpósio Brasileiro de Telecomunicações
18 | Rio de Janeiro, 4 de Setembro de 2008
Resultados
XXVISimpósio Brasileiro de Telecomunicações
19 | Rio de Janeiro, 4 de Setembro de 2008
Conclusões
 O treino do dicionário aliado à segmentação flexível permitiram ganhos
consistentes;
 O aumento de desempenho permitiu ao MMP ultrapassar os algoritmos
baseados em transformadas na codificação de imagens suaves;
 Apesar de ter sido realizado para imagens suaves, o treino do dicionário
não compromete o desempenho do algoritmo para imagens não suaves;
 A versatilidade do MMP aumentou, visto que este passou a superar o
desempenho dos algoritmos baseados em transformadas para todas as
imagens testadas, a praticamente todas as taxas de compressão.
XXVISimpósio Brasileiro de Telecomunicações
20 | Rio de Janeiro, 4 de Setembro 2008
Agradecimentos
O Projecto SCODE (PTDC/EEA-TEL/66462/2006) é financiado pela FCT
”Fundação para a Ciência e Tecnologia”, Portugal.
Casamento Aproximado de Padrões
Multiescala com Segmentação Flexível e
Treino do Dicionário
DEEC
Univ. Coimbra
Nelson Francisco, Nuno Rodrigues, Sérgio de Faria,
Eduardo da Silva, Vítor Silva and Manuel Reis
21 | Rio de Janeiro, 4 de Setembro 2008