Defina árvores quad e explique como imagens podem ser representadas usando-as. Descreva como podemos girar imagens, fazer mudança de escala e transladá-las manipulando a árvore quad correspondente.

Passo 1

O enunciado quer que a gente explique o que é uma árvore quad (quadtree), como ela representa imagens e de que maneira podemos aplicar rotações, escalas e translações diretamente manipulando essa estrutura de árvore. O conteúdo aqui é Estruturas de Dados (árvores recursivas) aplicadas a processamento de imagens.

Passo 2

Definição de quadtree
Uma quadtree é uma árvore em que cada nó corresponde a um bloco quadrado de pixels de uma imagem.
– Se o bloco for “homogêneo” (por exemplo, todos os pixels têm mesma cor ou variam dentro de um limiar), o nó é uma folha que armazena a informação de cor desse bloco.
– Caso contrário, o bloco é subdividido em quatro quadrantes iguais (superior-esquerdo, superior-direito, inferior-esquerdo e inferior-direito) e o nó interno terá exatamente quatro filhos, um para cada sub-bloco, repetindo o processo recursivamente.

Passo 3

Representação de imagens
  1. Começamos pela raiz, que representa toda a imagem (normalmente tamanho 2^k\times2^k).
  2. Testamos homogeneidade: se os pixels são todos “parecidos”, fazemos um nó folha e guardamos a cor média.
  3. Se não, dividimos em quatro e criamos quatro filhos, cada um para um quadrante, repetindo recursão até chegar ao nível de pixel ou homogeneidade.
    Isso gera uma estrutura compacta, pois regiões grandes e uniformes viram folhas em níveis altos, e regiões com muitos detalhes descem até folhas mais profundas.

Passo 4

Rotação de imagem via quadtree
Para girar a imagem em múltiplos de 90\circ basta, em cada nó interno, permutar seus quatro filhos de acordo com o tipo de rotação desejada e aplicar recursivamente nos filhos:
  • Rotação de 90\circ no sentido horário (CW):
    • filho Norte-Oeste passa a ser Norte-Leste
    • Norte-Leste → Sul-Leste
    • Sul-Leste → Sul-Oeste
    • Sul-Oeste → Norte-Oeste
  • Rotação de 180\circ: trocar Norte-Oeste↔Sul-Leste e Norte-Leste↔Sul-Oeste
  • Rotação de 270\circ CW: é a inversa de 90\circ CW
    Folhas não mudam cor, mas mudam sua posição lógica na árvore.

Passo 5

Escalonamento (scaling) pela quadtree
– Ampliação (zoom in): se quisermos dobrar a resolução, podemos expandir cada folha repetindo-a ou subdividindo-a criando filhos com mesma cor, até alcançar a nova granularidade. Em outras palavras, “esticamos” cada nó para ocupar um bloco de quatro nós-filhos idênticos.
– Redução (zoom out): podemos descer a árvore até um nível mais profundo, agrupar quatro nós-filhos e calcular uma cor média para formar uma única folha no nível superior, “colapsando” a estrutura.
É basicamente ajustar até que cada bloco na árvore corresponda ao novo tamanho de pixel desejado.

Passo 6

Translação (shifting) usando quadtree
Para deslocar a imagem em blocos de tamanho potência de 2, podemos:
  1. Criar um novo nó raiz cujo quadrante “de preenchimento” receba uma quadtree vazia (ou cor de fundo) e outro quadrante receba a quadtree original.
  2. Se o deslocamento for maior que o tamanho atual da raiz, repetimos o passo criando níveis acima até acomodar o deslocamento.
    Isso “move” logicamente a imagem dentro de uma área maior. Para deslocamentos pequenos não múltiplos de quadrantes, seria necessário realinhar subdivisões e potencialmente reconstruir partes da árvore, mas o princípio geral é sempre realocar subárvores para outros filhos do nó raiz ou níveis acima.

Resposta

Definimos quadtree como uma árvore recursiva que subdivide uma imagem em quadrantes até encontrar blocos homogêneos, armazenando cor em folhas. Para rodar a imagem, basta permutar os quatro filhos de cada nó segundo a rotação desejada. Para escalar, ampliamos folhas repetindo-as ou reduzimos colapsando subárvores e recalculando cor média. Para transladar, deslocamos a quadtree inteira dentro de uma nova raiz, encaixando-a em quadrantes deslocados e preenchendo o espaço vazio com subárvores “brancas” ou cor de fundo.

Exercícios de Livros Relacionados