Algoritmos de detecção de contorno de imagem

O artigo apresenta os quatro algoritmos de detecção de loop mais comuns.

Os dois primeiros, ou seja, o algoritmo para rastrear quadrados e rastrear os arredores de Moore, são fáceis de implementar e, portanto, são frequentemente usados ​​para determinar o contorno de um determinado padrão. Infelizmente, ambos os algoritmos têm várias fraquezas, o que torna impossível detectar o contorno de uma grande classe de padrões devido ao seu tipo especial de adjacência.

Esses algoritmos ignoram todos os "buracos" no padrão. Por exemplo, se tivermos um padrão semelhante ao mostrado na Figura 1 , o circuito detectado pelos algoritmos será semelhante ao mostrado na Figura 2 (o contorno é indicado por pixels azuis). Em algumas áreas de aplicação, isso é bastante aceitável, mas em outras, por exemplo, no reconhecimento de caracteres, é necessária a detecção das partes internas de um padrão para encontrar todos os espaços que distinguem um caractere específico. (A Figura 3 mostra o contorno “completo” do padrão.)



Portanto, para obter um contorno completo, primeiro é necessário usar o algoritmo de “busca de furo” que determina os furos em um determinado padrão e, em seguida, aplicar o algoritmo de detecção de contorno a cada furo.

O que é conectividade?

Em imagens digitais com valores binários, um pixel pode ter um dos seguintes valores: 1 - quando faz parte do padrão, ou 0 - quando faz parte do plano de fundo, ou seja, sem gradação de cinza. (Vamos supor que pixels com o valor 1 sejam pretos e com o valor 0 sejam brancos).

Para identificar objetos em um padrão digital, precisamos encontrar grupos de pixels pretos que estão "conectados" entre si. Em outras palavras, os objetos em um determinado padrão digital são os componentes conectados desse padrão.

No caso geral, um componente conectado é um conjunto de pixels pretos P , de modo que, para cada par de pixels pi e _pj em P, haja uma sequência de pixels pi, ..., _{pj, de} modo que:

a) todos os pixels na sequência estão no conjunto P , ou seja, são pretos e

b) a cada 2 pixels na sequência um ao lado do outro são "vizinhos".

Uma questão importante surge: quando podemos dizer que 2 pixels são “vizinhos”? Como usamos pixels quadrados, a resposta à pergunta anterior não é trivial pelo seguinte motivo: no mosaico quadrado, os pixels têm uma aresta ou um vértice comum ou nada em comum. Cada pixel tem 8 pixels em comum; esses pixels compõem o "bairro Moore" desse pixel. Devemos considerar os pixels "vizinhos" tendo apenas um vértice comum? Ou para ser considerado "vizinho", dois pixels devem ter uma borda comum?

Portanto, existem dois tipos de conectividade, a saber: conexão 4 e conexão 8.

4 conexões

Quando podemos dizer que um determinado conjunto de pixels pretos está conectado 4? Primeiro, você precisa definir o conceito de 4 vizinhos (também chamado de vizinho direto ):

Definição de 4 vizinhos : Um pixel Q é um 4 vizinho de um determinado pixel P se Q e P tiverem uma aresta comum. Os 4 vizinhos do pixel P (designados como P2, P4, P6 e P8 ) são mostrados na Figura 2 abaixo.


Definição de um componente conectado a 4 : o conjunto de pixels pretos P é um componente conectado a 4 se, para cada par de pixels p _i e p _j em P, houver uma sequência de pixels p _i , ..., p _j tal que:

a) todos os pixels na sequência estão no conjunto P , ou seja, são pretos e

b) a cada dois pixels adjacentes na sequência são 4 vizinhos

Exemplos de 4 padrões conectados

Os diagramas abaixo mostram exemplos de 4 padrões conectados:

8 conexões

Quando posso dizer que um determinado conjunto de pixels pretos está 8 conectado ? Primeiro, precisamos definir o conceito de 8 vizinhos (também chamado de vizinho indireto ):

Definição de 8 vizinhos : Um pixel Q é um 8 vizinhos (ou apenas um vizinho ) de um determinado pixel P se Q e P tiverem uma aresta ou vértice comum. Os 8 vizinhos de um determinado pixel P formam o bairro Moore desse pixel.

Definição de um componente conectado a 8 : o conjunto de pixels pretos P é um componente conectado a 8 (ou apenas um componente conectado ) se, para cada par de pixels p _i e p _j em P, houver uma sequência de pixels p _i , ..., p _j tal que :

a) todos os pixels na sequência estão no conjunto P , ou seja, são pretos e

b) a cada dois pixels adjacentes nessa sequência são 8 vizinhos

Nota : todos os padrões de 4 conexões são 8, ou seja, Os padrões com 4 conexões são um subconjunto dos muitos padrões com 8 conexões. Por outro lado, um padrão conectado a 8 pode não estar conectado a 4.

Exemplo de padrão com 8 links

O diagrama abaixo mostra um padrão que está 8 conectado, mas não 4:

Um exemplo de um padrão não conectado a 8:

O diagrama abaixo mostra um exemplo de um padrão que não está conectado 8, ou seja, composto por mais de um componente conectado (o diagrama mostra três componentes conectados):

Algoritmo de traço quadrado

Idéia

A idéia por trás do algoritmo de rastreamento quadrado é muito simples; isso pode ser atribuído ao fato de o algoritmo ter sido uma das primeiras tentativas de detectar o contorno de um padrão binário.

Para entender como funciona, você precisa de um pouco de imaginação ...

Suponha que tenhamos um padrão digital, por exemplo, um grupo de pixels pretos em um fundo de pixels brancos, ou seja, na grade; encontre o pixel preto e declare-o como nosso pixel " inicial ". (Encontrar o pixel " inicial " pode ser implementado de várias maneiras; começaremos do canto inferior esquerdo da grade, digitalizaremos cada coluna de pixels de baixo para cima, da coluna da esquerda para a direita, até encontrarmos um pixel preto. Nós o declararemos " inicial " ".)

Agora imagine que você é uma joaninha no pixel inicial , como mostra a Figura 1 abaixo. Para obter o esboço de um padrão, faça o seguinte:

, , ,

, , ,

.

Os pixels pretos que você circulou serão o contorno do padrão.


Um aspecto importante do algoritmo de traço quadrado é o "senso de direção". As curvas à esquerda e à direita são realizadas em relação à localização atual, que depende de como você chegou ao pixel atual. Portanto, para fazer os movimentos certos, você precisa acompanhar sua direção.

Algoritmo

A seguir, é apresentada uma descrição formal do algoritmo de rastreamento quadrado:

Entrada: mosaico quadrado, T , contendo o componente P conectado de células pretas.

Saída: linha B (b ₁ , b ₂ , ..., b _k ) de pixels da borda, ou seja, contorno.

Iniciar

• Defina B como um conjunto vazio.
• Digitalize as células T de baixo para cima e da esquerda para a direita até encontrar um pixel preto s de P.
• Inserir s em B.
• Torne o pixel atual p o pixel inicial s .
• Vire à esquerda, ou seja, vá para o pixel vizinho à esquerda de p .
• Atualizar p , ou seja, torna-se o pixel atual.
• Enquanto p não for igual a s , execute
  
  Se o pixel atual p for preto
  
  • insira p em B e vire à esquerda (vá para o pixel vizinho à esquerda de p ).
  • Atualizar p , ou seja, torna-se o pixel atual.
  
  caso contrário
  
  • vire à direita (vá para o próximo pixel à direita de p ).
  • Atualizar p , ou seja, torna-se o pixel atual.
  
  Fim do ciclo de "tchau"

O fim

Nota: os conceitos de "esquerda" e "direita" devem ser considerados não com relação à página ou ao leitor, mas com relação à direção de entrada no pixel "atual" durante a digitalização.

Demonstração

A seguir, é apresentada uma demonstração animada de como o algoritmo de rastreamento quadrado detecta o contorno de um padrão. Não esqueça que a joaninha se move em pixels; observe como sua direção muda ao virar à esquerda e à direita. As curvas à esquerda e à direita são realizadas em relação à direção atual em um pixel, ou seja, orientação joaninha.

Análise

Acontece que os recursos do algoritmo de rastreamento quadrado são muito limitados. Ele é incapaz de detectar os contornos de uma grande família de padrões que frequentemente surgem em aplicações do mundo real.

Isso se deve principalmente ao fato de as rotações esquerda e direita não levarem em consideração os pixels localizados “ao longo
diagonais "do pixel atual.

Vamos examinar os diferentes padrões com conectividade diferente e ver por que o algoritmo de rastreamento quadrado falha. Além disso, estudaremos maneiras de melhorar os recursos do algoritmo e fazê-lo funcionar mesmo com padrões que possuem um tipo especial de conectividade.

Critério de parada

Uma das fraquezas do algoritmo é a escolha do critério de parada. Em outras palavras, quando um algoritmo para de executar?

Na descrição original do algoritmo de rastreamento quadrado, a condição de conclusão é atingir o pixel inicial pela segunda vez. Acontece que, se o algoritmo depende de tal critério, não será capaz de detectar os contornos de uma grande família de padrões.

A seguir, uma demonstração animada explicando como o algoritmo não consegue detectar o contorno exato do padrão devido à seleção de um critério de parada incorreto:


Como você pode ver, melhorar o critério de parada pode ser um bom começo para melhorar o desempenho geral do algoritmo. Existem duas alternativas eficazes para um critério de desligamento existente:

a) Pare apenas visitando o pixel inicial n vezes, em que n é pelo menos 2, OU

b) Pare depois de pressionar o pixel inicial pela segunda vez, exatamente como o atingimos inicialmente.

Este critério foi proposto por Jacob Eliosoff , então o chamaremos de critério para interromper Jacob .

A alteração do critério de parada no caso geral melhora a eficácia do algoritmo de rastreio quadrado, mas não supera outros pontos fracos que possui no caso de padrões com tipos especiais de conectividade.

O algoritmo de rastreamento quadrado não consegue detectar o contorno de uma família de padrões com uma conectividade 8 que NÃO possui uma conectividade 4.

A seguir, é apresentada uma demonstração animada de como o algoritmo de rastreamento quadrado (com o critério de parada de Jacob) falha ao detectar o contorno correto de um padrão com conectividade 8 sem conectividade 4:

Esse algoritmo é completamente inútil?

Se você ler a análise acima, provavelmente acha que o algoritmo de rastreamento quadrado falha ao detectar os contornos da maioria dos padrões. Mas acontece. que existe uma família especial de padrões em que o caminho é totalmente detectado pelo algoritmo de rastreamento quadrado.

Seja P o conjunto de pixels pretos com conectividade 4 na grade. Deixe os pixels brancos da grade, ou seja, os pixels de fundo W também têm uma conectividade de 4. Acontece que nessas condições do padrão e de seu fundo, pode-se provar que o algoritmo de traço quadrado (com o critério de parada de Jacob) sempre lidará com êxito com a determinação do contorno.

Abaixo está a prova de que, no caso em que o padrão e os pixels de fundo estão conectados, o algoritmo de traço quadrado determinará corretamente o contorno ao usar o critério de parada de Jacob.

Prova
Dado : o padrão P é tal que todos os pixels do padrão (ou seja, preto) e os pixels de fundo (ou seja, branco) W têm uma conectividade de 4.

Primeira observação

Como o conjunto de pixels brancos W tem uma conectividade 4, isso significa que não pode haver " buracos " no padrão (em termos informais, " buracos " queremos dizer grupos de pixels brancos completamente cercados por pixels pretos do padrão).

A presença de qualquer " buraco " no padrão levará à separação do grupo de pixels brancos dos pixels brancos restantes; no entanto, muitos pixels brancos perdem a conectividade 4.

A Figura 2 e a Figura 3 abaixo mostram dois tipos de " orifícios " que podem ocorrer em um padrão com conectividade 4:



Segunda observação

Quaisquer dois pixels pretos de um padrão DEVEM ter um lado comum.

Suponha que dois pixels pretos tenham apenas um vértice comum. Então, para satisfazer a propriedade da conexão 4 do padrão, deve haver um caminho conectando esses dois pixels para que cada dois pixels adjacentes nesse caminho tenham uma conectividade 4. Mas isso nos dará um padrão semelhante à Figura 3 . Em outras palavras, isso resultará na separação de pixels brancos. A Figura 4 abaixo mostra um padrão típico que satisfaz a suposição de que os pixels no padrão e no plano de fundo estão conectados em 4, ou seja, não tem " buracos " e a cada dois pixels pretos tem um lado comum:


É útil representar esses padrões da seguinte maneira:

Primeiro, consideramos os pixels de limite, ou seja, contorno do padrão. Então, se considerarmos que cada pixel de limite possui 4 arestas de comprimento unitário, veremos que algumas dessas arestas são comuns aos pixels brancos vizinhos. Vamos chamar essas arestas de arestas de fronteira .

Essas arestas de limite podem ser consideradas como arestas de um polígono. Na foto
5 abaixo, essa ideia é demonstrada pelo exemplo de um polígono correspondente ao padrão da Figura 4 acima:


Se considerarmos todas as “configurações” possíveis de pixels de contorno que podem ocorrer em tais padrões, veremos que existem dois casos simples, mostrados na Figura 6 e na Figura 7 abaixo.

Os pixels de limite podem ser múltiplos desses casos ou de outros arranjos, ou seja, as voltas e reviravoltas desses dois casos. As nervuras de limite estão marcadas em azul como E1, E2, E3 e E4 .


Terceira observação

No caso dos dois casos acima, não importa qual seja o pixel inicial que escolhemos, e em qualquer direção em que ele caia , o algoritmo de rastreamento quadrado nunca "voltará" (retrocesso) , nunca "passará" pela borda do limite duas vezes ( somente se não rastrear a borda uma segunda vez) e nunca errar a borda da borda . Confira!

Dois conceitos precisam ser esclarecidos aqui:

a) o algoritmo “volta” quando, antes de rastrear toda a borda, volta a visitar um pixel já visitado, e

b) para cada nervura limite, há duas maneiras de "passar por ela" , a saber, "interna" e "externa" (onde "interna" refere-se ao movimento para dentro do polígono correspondente e "externa" - para fora do polígono).

Além disso, quando o algoritmo passa "para dentro" através de uma das bordas do limite, ele passa "para fora" pela próxima borda do limite, ou seja, o algoritmo de rastreamento quadrado não deve ser capaz de passar por duas arestas consecutivas da mesma maneira.

Última observação

Cada padrão possui um número par de arestas de limite .

Se você observar o polígono da Figura 5 , poderá ver que:

se queremos começar do vértice S marcado no diagrama e seguir as arestas do limite até chegarmos a S novamente, notamos que no processo cruzamos um número par de arestas do limite. Podemos considerar cada aresta de fronteira como um "passo" em uma direção separada. Então, para cada "passo" à direita, deve haver um "passo" correspondente à esquerda, se quisermos retornar à posição inicial. O mesmo se aplica aos "degraus" verticais. Portanto, as "etapas" devem ter pares correspondentes, e isso explica por que cada um desses padrões terá um número par de arestas de limite.

Portanto, quando o algoritmo para rastrear quadrados entra pela borda do limite inicial (do pixel inicial) uma segunda vez, ele o faz na mesma direção da primeira vez.

A razão para isso é que, como existem duas maneiras de atravessar a borda do limite, e o algoritmo se move alternadamente para dentro e para fora, e há um número par de bordas do limite, o algoritmo passará pela borda do limite inicial pela segunda vez da mesma maneira que em primeiro.

Conclusão

No caso de um padrão e fundo de 4 conexões, o algoritmo de rastreamento quadrado detectará toda a borda, ou seja, contorno, padrão e deixará de funcionar após um único traço, ou seja, Ele não o rastreará novamente, porque quando atingir a borda do limite inicial pela segunda vez, entrará na mesma maneira que na primeira vez. Consequentemente, o algoritmo de rastreio quadrado com o critério de parada de Jacob determinará corretamente o contador de qualquer padrão, desde que o padrão e o plano de fundo estejam conectados 4.

Rastreando os arredores de Moore

Idéia

A idéia por trás do rastreamento Moore-Neighbour é simples; mas antes de explicá-lo, precisamos explicar um conceito importante: o bairro Moore de um pixel.

O bairro de Moore

A vizinhança de Moore de um pixel P é um conjunto de 8 pixels com um vértice ou aresta comum com esse pixel. Esses pixels, nomeadamente P1, P2, P3, P4, P5, P6, P7 e P8 , são mostrados na Figura 1 .

O bairro de Moore (também chamado de 8 vizinhos ou vizinhos indiretos ) é um conceito importante frequentemente referido na literatura.


Agora, estamos prontos para nos familiarizar com a ideia subjacente aos vestígios dos arredores de Moore.

Que haja um padrão digital, ou seja, um grupo de pixels pretos, em um fundo de pixels brancos, ou seja, na grade; encontre o pixel preto e declare-o o pixel " inicial ". (Existem várias maneiras de encontrar o pixel " inicial ", mas, como antes, começaremos do canto inferior esquerdo e digitalizaremos todas as colunas de pixels em ordem, até encontrarmos o primeiro pixel preto, que declararemos " inicial ".)

Agora, novamente, imagine que você é uma joaninha no pixel inicial , como mostra a Figura 2 abaixo. Sem perda de generalização, detectaremos o contorno movendo-se no padrão no sentido horário. (Não importa em que direção escolhemos, o principal é usá-lo constantemente no algoritmo).

A idéia geral é a seguinte: toda vez que entramos no pixel preto P , voltamos, isto é, ao pixel branco em que estávamos antes. Em seguida , contornamos o pixel P no sentido horário, visitando todos os pixels nas proximidades de Moore, até chegarmos ao pixel preto. O algoritmo termina quando o pixel inicial atinge o pixel inicial uma segunda vez.

Os pixels pretos que o algoritmo visitou serão o contorno do padrão.

Algoritmo

A seguir, é apresentada uma descrição formal do algoritmo de rastreamento de vizinhança de Moore:

Entrada: mosaico quadrado T contendo um componente P conectado de células pretas.

Saída: linha B (b ₁ , b ₂ , ..., b _k ) de pixels de limite, ou seja, contorno.

Denote por M (a) a vizinhança de Moore do pixel a .

Seja p o pixel atual da borda.

Seja c o pixel atual em consideração, ou seja, c está em M (p) .

Iniciar

• Defina B como um conjunto vazio.
• De baixo para cima e da esquerda para a direita, digitalize as células T até encontrarmos um pixel preto s de P.
• Inserir s em B.
• Definimos o ponto s como o ponto limite atual p , ou seja, p = s
• Vamos voltar, ou seja, vamos para o pixel do qual viemos s .
• Seja c o próximo pixel no sentido horário em M (p) .
• Enquanto c não for igual a s , execute
  
  
  • se c é preto
    
    • Inserir c em B
    • estabelecemos p = c
    • voltar (mover o pixel atual c para o pixel a partir do qual chegamos a p )
    
    caso contrário
    
    • mova o pixel atual c para o próximo pixel no sentido horário em M (p)
    
    Fim do ciclo de adeus

O fim

Demonstração

A seguir, uma demonstração animada de como o rastreamento de vizinhança de Moore realiza a detecção de contornos de padrão. (Decidimos traçar o contorno no sentido horário.)

Análise

A principal fraqueza em rastrear os arredores de Moore reside na escolha de critérios de parada.

Na descrição original do algoritmo para rastrear os arredores de Moore, o critério de parada é atingir o pixel inicial pela segunda vez. Semelhante ao algoritmo de rastreamento quadrado, verifica-se que o rastreamento dos arredores de Moore usando esse critério não pode detectar os contornos de uma grande família de padrões.

A seguir, uma demonstração animada explicando por que o algoritmo não consegue encontrar o contorno exato do padrão devido à seleção de um critério de parada incorreto:


Como você pode ver, melhorar o critério de parada pode ser um bom começo para melhorar o desempenho geral do rastreamento. Existem duas alternativas efetivas para o critério de desligamento, semelhante ao critério de desligamento de Jacob.

O uso do critério Jacob melhora significativamente a eficácia do rastreamento dos arredores de Moore, tornando-o o melhor algoritmo para determinar o contorno de qualquer padrão, independentemente de sua conectividade.

A razão para isso é principalmente porque o algoritmo verifica toda a vizinhança de Moore do pixel de limite para procurar o próximo pixel de limite. Ao contrário do algoritmo de traço quadrado, que gira apenas para a esquerda e para a direita e perde os pixels "na diagonal", o traçado da vizinhança de Moore sempre será capaz de detectar o limite externo de qualquer componente conectado. A razão é a seguinte: para qualquer padrão de 8 conexões (ou simplesmente conectado ), o próximo pixel de borda fica dentro do bairro Moore do atual pixel de borda. Como o rastreamento de vizinhança de Moore verifica cada um dos pixels na vizinhança de Moore do pixel de limite atual, ele deve detectar o próximo pixel de limite.

Quando o rastreio da vizinhança de Mura atinge o pixel inicial uma segunda vez da mesma maneira que ela fez na primeira vez, isso significa que um contorno externo completo do padrão foi detectado e, se o algoritmo não for parado, ele detectará novamente o mesmo contorno.

Varredura radial

O algoritmo de varredura radial é um algoritmo de detecção de contorno discutido em alguns livros. Apesar do nome complexo, a ideia subjacente é muito simples. De fato, verifica-se que o algoritmo de varredura radial é idêntico ao traço do entorno de Moore. Alguém pode perguntar: "Por que o mencionamos?"

O rastreamento dos arredores de Moore procura nas proximidades de Moore o pixel de limite atual em uma determinada direção (escolhemos a direção no sentido horário) até encontrar um pixel preto. Ela então declara esse pixel como o limite atual e continua.

O algoritmo de varredura radial faz o mesmo. Por outro lado, fornece uma maneira interessante de encontrar o próximo pixel preto na vizinhança de Moore de um determinado pixel de limite.

O método é baseado na seguinte ideia:

toda vez que encontrarmos um novo pixel de limite, torne-o o pixel atual P e desenhe um segmento de linha imaginário conectando P ao pixel de limite anterior . Em seguida, giramos o segmento em relação a P no sentido horário até encontrar um pixel preto na vizinhança de Moore do pixel P. A rotação da linha é idêntica à verificação de cada pixel nas proximidades de Moore P.

Criamos uma demonstração animada de como o algoritmo de varredura radial funciona e como ele parece rastrear os arredores de Moore.


E quando o algoritmo de varredura radial para?

Vamos explicar o comportamento do algoritmo usando os seguintes critérios de parada ...

Critério de parada 1

Deixe o algoritmo de varredura radial completo quando visitar o pixel inicial pela segunda vez.

Abaixo está uma demonstração animada, da qual fica claro por que o critério de quebra será alterado corretamente.


Também vale a pena mencionar que, ao usar esse critério de parada nos dois algoritmos, a eficácia do algoritmo de varredura radial é idêntica à localização dos arredores de Moore.

No algoritmo de rastreamento quadrado e no rastreamento de vizinhança de Moore, descobrimos que o uso do critério de parada de Jacob melhora significativamente o desempenho de ambos os algoritmos.

O critério de parada de Jacob exige que o algoritmo pare de executar quando visita o pixel inicial pela segunda vez na mesma direção da primeira vez.

Infelizmente, não podemos usar o critério de parada de Jacob no algoritmo de varredura radial. O motivo é que o algoritmo de varredura radial não define o conceitoA "direção" na qual ele atinge o pixel de limite . Em outras palavras, não está clara a “direção” na qual o algoritmo caiu no pixel de limite (e sua definição é não trivial).

Portanto, precisamos propor outro critério de parada, que não depende da direção de atingir um pixel específico, o que pode melhorar a eficácia do algoritmo de varredura radial ...

Critério de parada 2

Suponha que cada vez que o algoritmo detecte um novo pixel de limite P _i , ele seja inserido em uma série de pixels de limite: P ₁ , P ₂ , P ₃ , ..., P _i ; e declarado como o pixel da borda atual. ( P ₁ consideraremos o pixel inicial ). Isso significa que conhecemos o pixel da borda anterior P _{i-1 de} cada pixel da borda atual P _i . (Quanto ao pixel inicial , assumiremos que P ₀é um pixel imaginário que não é equivalente a nenhum dos pixels na grade que enfrenta o pixel inicial na linha de pixels de limite).

Dadas as premissas acima, podemos determinar o critério de parada da seguinte forma:

O algoritmo termina a execução quando:

a) a corrente de pixel limite P _i já anteriormente se reuniu como um pixel P _j (onde j <i ) na série de pixels de contorno, e

b) P _{i- 1} = P _j-1 .

Em outras palavras, o algoritmo conclui a execução quando visita o pixel limite P no segundovezes se o pixel de limite antes de P (na linha de pixels de limite) pela segunda vez for o mesmo pixel que era antes de P quando P foi visitado pela primeira vez.

Se a condição do critério de parada for atendida e o algoritmo não for desligado, o algoritmo de varredura radial continuará a detectar o mesmo limite pela segunda vez.

O desempenho do algoritmo de varredura radial com esse critério de parada é semelhante ao desempenho de rastrear a vizinhança de Moore com o critério de parada de Jacob.

Algoritmo de Theo Pavlidis

Idéia

Este algoritmo é um dos mais recentes algoritmos de detecção de loop propostos por Theo Pavlidis . Ele o citou em seu livro de 1982, Algoritmos para processamento de gráficos e imagens (capítulo 7, seção 5). Não é tão simples como o algoritmo para rastrear quadrados ou rastrear os arredores de Moore, mas não é tão complicado (isso é característico da maioria dos algoritmos de detecção de contorno).

Não explicaremos esse algoritmo da mesma maneira que foi feito em seu livro. Nossa abordagem é mais fácil de entender e fornece uma idéia da ideia geral subjacente ao algoritmo.

Sem perda de generalização, decidimos dar a volta no loop no sentido horário para corresponder à ordem de todos os outros algoritmos apresentados no artigo. Por outro lado, Pavlidis escolheu a direção no sentido anti-horário. Isso não afetará o desempenho do algoritmo. A única diferença é a direção relativa dos movimentos que faremos quando contornarmos o contorno.

Agora, vamos à ideia ...

Digamos que temos um padrão digital, ou seja, um grupo de pixels pretos em um fundo de pixels brancos, ou seja, na grade; encontre o pixel preto e declare-o o pixel " inicial ". Você pode procurar o pixel " inicial " de várias maneiras, por exemplo, conforme descrito acima.

Para encontrar a inicialpixels para usar esse método é opcional. Em vez disso, escolheremos um pixel inicial que satisfaça as seguintes restrições impostas pelo algoritmo Pavlidis para a seleção de um pixel inicial:

Uma limitação importante da direção na qual inserimos o pixel inicial

Na verdade, você pode escolher QUALQUER pixel de borda preta como o pixel inicial sob esta condição: se você estiver inicialmente nele, o pixel vizinho esquerdo NÃO é preto. Em outras palavras, você precisa inserir o pixel inicial em uma direção em que o pixel vizinho esquerdo seja branco (a "esquerda" aqui é obtida em relação à direção em que inserimos o pixel inicial ).

Agora imagine que você é uma joaninha em pépixel inicial , como mostra a Figura 1 abaixo. Durante a execução do algoritmo, estaremos interessados ​​em apenas três pixels à sua frente, ou seja, P1, P2 e P3 mostrados na Figura 1 . (Designaremos P2 como o pixel à sua frente , P1 é o pixel à esquerda de P2 e P3 é o pixel à direita de P2 ).


Como no algoritmo de traço quadrado, a coisa mais importante no algoritmo Pavlidis é o "senso de direção". As curvas à esquerda e à direita são relativas à posição atual, que depende de como você inseriu o pixel atual. Portanto, para fazer os movimentos certos, é importante acompanhar sua orientação atual. Mas não importa como você esteja localizado, os pixels P1, P2 e P3 são determinados conforme descrito acima.

Com essas informações, estamos prontos para explicar o algoritmo ...

Cada vez que você está no pixel de limite atual (que é o primeiro pixel inicial ), fazemos o seguinte:

Primeiro , verifique o pixel P1 . Se P1 for preto, declare P1o pixel de limite atual e dê um passo à frente e, em seguida, dê um passo à esquerda para estar em P1 (a ordem dos movimentos é muito importante).

Na Figura 2 a seguir ilustra este processo. O caminho para chegar ao P1 é mostrado em azul.


E somente se P1 for branco, procederemos à verificação de P2 ...

Se P2 for preto, declarar P2 o pixel de limite atual e avançar um passo para estar em P2 . Este caso é mostrado na Figura 3 abaixo. O caminho que você precisa seguir no P2 é mostrado em azul.


Somente se P1 e P2 forem brancos, verifique P3 ...

Se P3 for preto, declare P3 o pixel atual da borda e mova um passo para a direita e depois um passo para a esquerda , como mostra a Figura 4 abaixo.


Isso é tudo! Três regras simples para três casos simples. Como você pode ver, é importante acompanhar sua direção ao fazer curvas, porque todos os movimentos são feitos em relação à orientação atual. Mas parece que esquecemos alguma coisa? E se todos os três pixels estiverem brancos à nossa frente? Em seguida, giramos (em pé no atual limite do pixel) 90 graus no sentido horário para ver um novo conjunto de três pixels à nossa frente. Em seguida, fazemos a mesma verificação para esses novos pixels. Você ainda pode ter uma pergunta: e se todos esses três pixels forem brancos ?! Então, novamente, giramos 90 graus no sentido horário, permanecendo no mesmo pixel. Antes de verificar a vizinhança inteira do pixel de Moore, você pode girar três vezes (cada vez 90 graus no sentido horário).

Se girarmos três vezes sem encontrar pixels pretos, isso significa que estamos em um pixel isolado , não conectado a nenhum outro pixel preto. É por isso que o algoritmo permite que você gire três vezes e, em seguida, conclui sua execução.

Outro aspecto: quando o algoritmo completa a execução?

O algoritmo termina em dois casos:

a) como mencionado acima. o algoritmo permite que você gire três vezes (90 graus no sentido horário cada vez), depois de concluir a execução e declarar o pixel isolado OU

b) quando o pixel de limite atual é o pixel inicial , o algoritmo conclui a execução “declarando” que detectou o contorno do padrão.

Algoritmo

A seguir, é apresentada uma descrição formal do algoritmo Pavlidis:

Entrada: mosaico quadrado T contendo um componente P conectado de células pretas.

Saída: linha B (b ₁ , b ₂ , ..., b _k ) de pixels de limite, ou seja, contorno.

Definições:

• Denuncie por p o pixel do limite atual, ou seja, o pixel em que estamos.
• Defina P1, P2 e P3 da seguinte maneira: (veja também a Figura 1 acima)
• P2 é o pixel à sua frente, adjacente àquele em que você está, ou seja, com pixel p .
• P1 — , P2 .
• P3 — , P2 .
• «» .

Iniciar

• B .
• T , s P (. , )
• s B .
• p s .
• :
  P1
  
  • P1 B
  • p=P1
  • ,
  
  P2
  
  • P2 B
  • p=P2
  • (. 3)
  
  P3
  
  • P3 B
  • p=P3
  • , (. 4)
  
  90 , p
  
  • encerrar o programa e declarar p um pixel isolado
  
  caso contrário
  
  • gire 90 graus no sentido horário, de pé no pixel atual p
  
  Até agora p = s (finalize o loop de repetição)

O fim

Demonstração

A seguir, é apresentada uma demonstração animada de como o algoritmo Pavlidis detecta o contorno de um determinado padrão. Não esqueça que andamos em pixels; observe como a orientação muda ao virar para a esquerda ou direita. Para explicar o algoritmo com o máximo de detalhes possível, incluímos todos os casos possíveis.

Análise

Se você acha que o algoritmo Pavlidis é ideal para detectar contornos de padrões, deve mudar de idéia ...

Esse algoritmo é realmente um pouco mais complicado do que, por exemplo, rastrear os arredores de Moore, nos quais não há casos especiais que exijam processamento separado, mas não será capaz de determinar os contornos de um grande número. uma família de padrões que possui um certo tipo de conectividade.

O algoritmo funciona muito bem em padrões de 4 conexões. Seu problema ocorre ao rastrear alguns padrões conectados a 8 que não estão conectados a 4. A seguir, é apresentada uma demonstração animada de como o algoritmo Pavlidis falha ao detectar o contorno correto de um padrão de 8 conexões (e não de 4) - ele pula a maior parte da borda.


Existem duas maneiras simples de modificar um algoritmo para melhorar significativamente seu desempenho.

a) Substitua o critério de parada

Em vez de concluir o algoritmo ao visitar o pixel inicial pela segunda vez, você pode finalizá-lo quando visitar o pixel inicial pela terceira ou quarta vez. Isso melhorará o desempenho geral do algoritmo.

OU

b) Chegue à origem do problema, ou seja, antes de selecionar o pixel

inicial.Há uma limitação importante em relação à direção na qual a entrada no pixel inicial é realizada. Essencialmente, você precisa inserir o pixel inicial para que, quando você fique sobre ele, o pixel à sua esquerda seja branco. A razão para introduzir essa restrição é esta: como sempre olhamos para os três pixels à nossa frente emem uma determinada ordem , em alguns padrões, pularemos o pixel de limite diretamente à esquerda do pixel inicial.

Corremos o risco de perder não apenas o pixel vizinho esquerdo do pixel inicial, mas também o pixel diretamente abaixo dele (como demonstrado na análise). Além disso, em alguns padrões, um pixel correspondente ao pixel R na Figura 5 abaixo será ignorado . Portanto, assumimos que o pixel inicial precisa ser atingido em uma direção em que os pixels correspondentes aos pixels L, W e R mostrados na Figura 5 abaixo sejam brancos.


Nesse caso, padrões como o mostrado na demonstração serão detectados corretamente e a eficácia do algoritmo Pavlidis melhorará significativamente. Por outro lado, encontrar um pixel inicial que atenda a esses requisitos pode ser desafiador e, em muitos casos, será impossível encontrá-lo. Nesse caso, você deve usar uma maneira alternativa de melhorar o algoritmo Pavlidis, ou seja, a conclusão do algoritmo depois de visitar o ponto de partida pela terceira vez.