Algoritmos: correspondência de elipse

Eu tenho muitas imagens como as seguintes (apenas branco e preto):

insira a descrição da imagem aqui

Meu problema final é encontrar elipses bem correspondentes. Infelizmente as imagens reais usadas nem sempre são legais assim. Eles podem ser deformados um pouco, o que torna a elipse mais provável.

Minha ideia é encontrar “break points”. Eu marquei-os na seguinte imagem:

insira a descrição da imagem aqui

Talvez esses pontos possam ajudar a fazer uma correspondência para as elipses. O resultado final deve ser algo assim:

insira a descrição da imagem aqui

Alguém tem uma ideia de qual algoritmo pode ser usado para encontrar esses pontos de quebra? Ou ainda melhor para fazer uma boa combinação de elipse?

Muito obrigado

  1. Amostra dos pontos de circunferência

    Basta digitalizar sua imagem e selecionar todos os pixels pretos com qualquer vizinho branco. Você pode fazer isso recolorindo os pixels pretos restantes em qualquer cor não usada (azul).

    Depois que a imagem inteira é feita, você pode recolorir o interior de volta da cor não usada (azul) para branco.

  2. formar uma lista de pontos de circunferência ordenada por cluster / elipse

    Basta digitalizar sua imagem e encontrar o primeiro pixel preto. Em seguida, use A * para ordenar os pontos de circunferência e armazenar o caminho em alguma matriz ou lista pnt[] e manipulá-lo como matriz circular.

  3. Encontre os “pontos de quebra”

    Eles podem ser detectados por pico no ângulo entre os vizinhos dos pontos encontrados. algo como

     float a0=atan2(pnt[i].y-pnt[i-1].y,pnt[i].x-pnt[i-1].x); float a1=atan2(pnt[i+1].y-pnt[i].y,pnt[i+1].x-pnt[i].x); float da=fabs(a0-a1); if (da>M_PI) da=2.0*M_PI-da; if (da>treshold) pnt[i] is break point; 

    ou use o fato de que no ponto de ruptura o sinal de mudança de delta do ângulo de inclinação:

     float a1=atan2(pnt[i-1].y-pnt[i-2].y,pnt[i-1].x-pnt[i-2].x); float a1=atan2(pnt[i ].y-pnt[i-1].y,pnt[i ].x-pnt[i-1].x); float a2=atan2(pnt[i+1].y-pnt[i ].y,pnt[i+1].x-pnt[i ].x); float da0=a1-a0; if (da0>M_PI) da0=2.0*M_PI-da0; if (da0< -M_PI) da0=2.0*M_PI+da0; float da1=a2-a1; if (da1>M_PI) da1=2.0*M_PI-da1; if (da1< -M_PI) da1=2.0*M_PI+da1; if (da0*da1<0.0) pnt[i] is break point; 
  4. encheckboxr elipses

    então, se nenhum ponto de quebra for encontrado, você poderá ajustar todo o pnt [] como elipse simples. Por exemplo, encontrar checkbox delimitadora. Seu centro é o centro da elipse e seu tamanho lhe dá semi-eixos.

    Se os pontos de quebra forem encontrados, primeiro encontre a checkbox delimitadora de pnt[] inteiro pnt[] para obter limites para semi-eixos e busca de área de posição central. Em seguida, divida o pnt[] para as partes entre os pontos de quebra. Lidar com cada parte como parte separada da elipse e ajuste.

    Depois que todas as partes pnt[] estiverem encheckboxdas verifique se algumas elipses não são as mesmas, por exemplo, se elas estão sobrepostas por outra elipse, elas seriam divididas ... Então, mescle as idênticas (ou média para aumentar a precisão). Em seguida, recolorir todos os pontos pnt[i] para branco, limpe a lista pnt[] e loop # 2 até não mais pixel preto é encontrado.

  5. como encheckboxr a elipse da seleção de pontos?

    1. algebricamente

      use a equação de elipse com pontos conhecidos dispersos "uniformemente" para formar um sistema de equações para calcular parâmetros de elipse ( x0,y0,rx,ry,angle ).

    2. geometricamente

      por exemplo, se você detectar inclinação 0,90,180 ou 270 graus, então você está na intersecção semi-eixo com a circunferência. Então, se você tem dois desses pontos (um para cada semi-eixo), isso é tudo que você precisa para encheckboxr (se for uma elipse alinhada ao eixo).

      Para elipses não alinhadas no eixo, você precisa ter uma parte grande da circunferência disponível. Você pode explorar o fato de que o centro da checkbox delimitadora é também o centro da elipse. Então, se você tem toda a elipse, você também conhece o centro. As intersecções semi-axiais com circunferência podem ser detectadas com maior e menor alteração tangencial. Se você tem centro e dois pontos é tudo que você precisa. Caso você tenha apenas um centro parcial (apenas coordenada x ou y), você pode combinar com mais pontos do eixo (encontrar 3 ou 4) ... ou aproximar as informações ausentes.

      Além disso, o eixo das linhas de metade H, V está cruzando o centro da elipse para que possa ser usado para detectá-la, se não toda a elipse na lista pnt[] .

      ajuste de elipse não alinhado ao eixo

    3. pesquisa de aproximação

      Você pode percorrer "todos" possíveis combinações de parâmetros de elipse dentro dos limites encontrados em # 4 e selecionar aquele que está mais próximo de seus pontos. Isso seria insanamente lento de grosseiro, então use a pesquisa binária como se aproximasse de algo como a minha class approx . Veja também

      • Ajuste de curvas com y pontos em posições x repetidas (arms Galaxy Spiral)

      sobre como é usado para um ajuste semelhante ao seu.

    4. híbrido

      Você pode combinar aproximação geométrica e aproximação. Primeiro calcule o que você pode por abordagem geométrica. E, em seguida, calcule o resto com a pesquisa de aproximação. Você também pode aumentar a precisão dos valores encontrados.

    Em casos raros, quando duas elipses são mescladas sem ponto de interrupção, a elipse ajustada não corresponderá aos seus pontos. Então, se tal caso detectou você tem que subdividir os pontos usados ​​em grupos até que seus ajustes coincidam ...

É isso que tenho em mente com isso:

Visão geral

Você provavelmente precisa de algo assim:

https://en.wikipedia.org/wiki/Circle_Hough_Transform

Seus pontos de borda são simplesmente pixels pretos com pelo menos um branco de 4 vizinhos.

Infelizmente, porém, você diz que suas elipses podem estar “inclinadas”. Elipses genéricas são descritas por equações quadráticas como

 x² + Ay² + Bxy + Cx + Dy + E = 0 

com B² <4A (⇒ A> 0). Isso significa que, comparado ao problema do círculo, você não tem 3 dimensões, mas 5. Isso faz com que a transformação Hough seja consideravelmente mais difícil. Felizmente, seu exemplo sugere que você não precisa de alta resolução.


Veja também: algoritmo para detectar um círculo em uma imagem


EDITAR

A ideia acima para um algoritmo era otimista demais , pelo menos se aplicada de maneira direta. A boa notícia é que parece que dois caras espertos (Yonghong Xie e Qiang Ji) já fizeram a lição de casa para nós:

https://www.ecse.rpi.edu/~cvrl/Publication/pdf/Xie2002.pdf

Não tenho certeza se criaria meu próprio algoritmo. Por que não aproveitar o trabalho que outras equipes fizeram para descobrir toda a curva de ajuste de bitmaps?

INKSCAPE (App Link)

O Inkscape é uma ferramenta de código aberto especializada em edição de charts vetoriais com alguma capacidade de trabalhar com partes rasterizadas (bitmap) também.

Aqui está um link para um ponto de partida para a API do Inkscape:

http://wiki.inkscape.org/wiki/index.php/Script_extensions

Parece que você pode criar scripts no Inkscape ou acessar o Inkscape por meio de scripts externos.

Você também pode fazer algo com zero script, a partir da interface de linha de comando do inkscape:

http://wiki.inkscape.org/wiki/index.php/Frequently_asked_questions#Can_Inkscape_be_used_from_the_command_line.3F

COREL DRAW (App Link)

O Corel Draw é reconhecido como a principal solução do setor para charts vetoriais e possui ótimas ferramentas para converter imagens rasterizadas em imagens vetoriais.

Aqui está um link para a API deles:

https://community.coreldraw.com/sdk/api

Aqui está um link para o processamento de imagens em lote do Corel Draw (solução não-script):

http://howto.corel.com/en/c/Automating_tasks_and_batch-processing_images_in_Corel_PHOTO-PAINT