Em aplicações de CG é interessante ser capaz de converter uma figura representada por um bitmap para uma forma vetorizada. Esta última tem várias vantagens sobre um bitmap, como por exemplo, pode sofrer transformações sem perda de resolução e é mais adequada para o uso em visão computacional (reconhecimento de padrões).
O algoritmo aqui apresentado permite realizar esta conversão de um modo prático e eficiente. Este será descrito em duas etapas:
Resumo do Problema
Vetorização transforma uma figura em uma coleção de vetores que delimitam seus limites. Uma vez que a vetorização parte de uma aproximação grosseira da figura (a partir de uma grade de pixels), só pode gerar um número limitado de vetores, os quais podem ser codificados como inteiros no intervalo [ 0, 7 ]. Esta coleção é também chamada de "código de encadeamento".
Figura 1: Algoritmo original
Primeiramente, o algoritmo gera os limites. Isto é feito em quatro passagens: rastreando o bitmap em uma direção particular (da direita para a esquerda, da esquerda para a direita, de cima para baixo, de baixo para cima). Cada fase adiciona uma camada de pixels à figura, cada vez que passa sobre um limite. A figura abaixo mostra o resultado dos dois primeiros passos:
Figura 2: Geração dos limites (contorno)
Finalmente, o algoritmo encontra um pixel do contorno da figura e começa então o seu laço principal:
repetir
marcar(p)
//
marcar a posição atual
for idelta = 0 to 7 // índice
para os deslocamentos em ordem inversa ao relógio
delta = vetor[idelta] // obtém vetor de
deslocamento
se
borda(p+delta) // achou limite ?
encadeia(delta) //
adiciona à cadeia
p = p +
delta // atualiza posição
enquanto HouverMovimento()
Limitações
O algoritmo não é perfeito. Apresenta dois problemas com bitmaps "finos" ou com bitmaps que possuem "buracos" muito estreitos. A seguir são apresentados estes problemas:
Problema 1: No primeiro exemplo, o algoritmo é aplicado a uma letra "m", pequena e minúscula. O algoritmo começa normalmente no ponto A, então gradualmente se aproxima de um buraco estreito (um pixel de largura) no ponto B. Uma vez que a verificação das direções é feita em sentido anti-horário, ele "cai" no buraco. Porém, continuando ao longo deste e marcando seus pixels no caminho, não percebe que está bloqueando sua saída. Dessa forma, finaliza no ponto C, vetorizando apenas 1/3 do "m".
Figura 3: Um beco sem saída
Problema 2: No segundo exemplo, o algoritmo é aplicado a um número "1", começando no ponto A. Teoricamente, um bom algoritmo deveria subir pela vertical até o ponto B então pegar a "escada" à esquerda até o ponto C e por fim subir até o ponto D. Porém, quando chega no ponto B, decide pegar um atalho e vai diretamente ao ponto D. O motivo é o mesmo: a verificação das direções é realizada em sentido anti-horário. Para linhas finas de 45 graus, não há maneira de saber qual rota escolher (C ou D).
Figura 4: Um "vazamento"
Uma extensão simples solucionará ambos os problemas. O truque é subdividir cada pixel do bitmap em uma grade 4x4 de "pixels menores", como mostra a figura abaixo.
Figura 5: O novo algoritmo
Nessa nova escala, o problema 1 simplesmente desaparece. Em um mundo 4 x 4, não existem buracos estreitos... Porém, o problema 2 ainda persiste mas é facilmente resolvido. Neste ambiente, os movimentos em linha reta sempre terão maior prioridade que os movimentos na diagonal. Estes últimos só devem ser utilizados em último caso. Desta forma, o problema 2 é resolvido simplesmente alterando-se a ordem de verificação das direções.
Poderíamos citar três objeções a este novo método:
Dois Truques Adicionais
Dois truques simples solucionarão a maioria das objeções sugeridas: