Quad-Tree
Definição
"
È utilizada para a codificação de imagem
"
Parte do suposto que uma imagem pode ser
dividida em 4 quadrantes, sendo que cada
quadrante possa ser subdividido em mais 4
quadrantes e assim sucessivamente
Tem como idéia principal o armazenamento de
uma decomposição recursiva do espaço
"
Para a obtenção de uma QuadTree
"
"
O algoritmo verifica se a imagem possui uma só
cor, em caso positivo, é criado apenas um nodo
Caso contrário, a imagem é subdividida em 4
quadrantes, se em algum deles houver mais de
uma cor na imagem, este quadrante é subdividido
em 4 quadrantes, e assim recursivamente até que
em todos os quadrantes aja apenas uma cor
Estrutura dos nodos de uma
Quad-Tree
Há dois tipos de nodos
"
"
Nodo interno : possui 4 ponteiros para as
subdivisões. Este nodo não armazena nenhuma
informação a respeito da imagem
Nodo externo : nodo que se encarrega de
armazenar informações sobre a cor da imagem
Quadrantes
"
São denominados por :
NO : Noroeste
NE : Nordeste
SO : Sudoeste
SE : Sudeste
Criação
Inserção
Inserção é dada em 2
momentos
"
"
Na criação da quad-tree : já explicado anteriormente
Na alteração da imagem : quando queremos incluir
novos nodos que reflitam as alterações feitas na imagem
original
Inserção e Alteração
Imagem
inicial
QuadTree
inicial
Imagem
alterada
QuadTree
Final
Pesquisa : por cor
"
"
"
A pesquisa por cor varre toda a QuadTree
gerada, tentado localizar uma cor específica
Realização de operações de troca de cores
em imagens
Uso prático na medicina, onde em
determinadas radiografias, células
defeituosas são mostradas em cinza, que
seria a sua cor natural, porém para visualizálas melhor pode-se trocar a sua cor para
preto.
Deleção
Deleção
"
A exclusão de um nodo ocorrerá quando um
determinado nodo interno tem todos os seus os
seus descendentes de uma mesma cor.
"
Quando isso ocorre, pode-se excluir todos os
nodos descendentes e armazenar a cor no ancestral
correspondente
Caminhamentos
"
Assim como outras estruturas de dados como
árvore binárias, árvores AVL, a quad-tree
também possui algumas formas de
caminhamento, tais como
Tipos de caminhamentos
"
Caminhamento em Z
"
Caminhamento Antihorário
Aplicações
"
- 3D Studio MAX 3 (um dos mais populares
softwares para animação e renderização de
imagens 3D): É utilizado aqui a quadtree para
se fazer o controle da profundidade de cor
para sombras RayTrace.
"
Corrigir deformações de cores nas fotos.
Como por exemplo, quando se tira uma foto e
a pessoa está com os olhos avermelhados,
podendo isso ser corrigido utilizando a
quadtree.
Compactação de imagens.
"