Como: pacotes de pixels em uma imagem para coordenadas de ponto representativas (x, y)

7

Vamos ter uma imagem (em escala de cinza ou até binária), como mostrado na figura a seguir, no lado esquerdo. O objetivo é gerar uma lista de pontos, isto é, coordenadas na forma de (x, y) para cada pacote do pixels escuros na imagem.
Quais são as ferramentas adequadas de processamento de imagem para fazer isso e onde estão disponíveis?

pacotes de pixels para apontar coordenadas


Atualizações:
1) Aqui você pode encontrar mais detalhes sobre o problema. (Observe a variação no tamanho das embalagens)

detalhes

Eu posso sugerir que os pacotes sejam detectados para calcular o limite do casco convexo para cada um e, em seguida, encontre o centróide representativo {veja isso para obter detalhes} .

pacote de pixels no casco convexo ao ponto central


2)
Aqui está o resultado produzido pela aplicação da Distância Transformada (sugerida por "Libor"). Observe minhas anotações na figura. O método não funciona como promissor!

insira a descrição da imagem aqui

3) A
erosão elimina embalagens pequenas!

from __future__ import division
from scipy import zeros, ndimage as dsp
from pylab import subplot,plot,matshow,show

img = zeros((30,30))
img[10:14,10:14] = 1
img[16:17,16:17] = 1
img[19:23,19] = 1
img[19,19:23] = 1

subplot(221)
matshow(img,0)

subplot(222)
y = dsp.binary_erosion(img,[[1,1],[1,1]])
matshow(y,0)

subplot(223)
y = dsp.binary_erosion(img,[[0,1,0],[1,1,1],[0,1,0]])
matshow(y,0)

subplot(224)
y = dsp.binary_erosion(img,[[1,1,1],[1,1,1],[1,1,1]])
matshow(y,0)

show()

insira a descrição da imagem aqui

4)
Bem, aqui está uma implementação em Python (isto é, a linguagem do amor :)) da idéia de rotular (também proposta por "Jean-Yves" abaixo):

subplot(221)
l,n = dsp.label(img)
sl = dsp.find_objects(l)
for s in sl:
    x = (s[1].start+s[1].stop-1)/2
    y = (s[0].start+s[0].stop-1)/2
    plot(x,y,'wo')

e o resultado:

insira a descrição da imagem aqui

Observe que, embora seja feito em Python tão rapidamente devido ao desempenho do Scipy, o procedimento em segundo plano na labelfunção deve ser uma iteração exaustiva. Isso pode ser considerado um trade-off. Por um tempo, continuo ansioso para buscar algoritmos mais eficientes. E observe também que, no código fornecido acima, achei o centro da geometria tão simples, enquanto que para formas complexas ou assimétricas, isso pode causar um viés de posicionamento. Ou seja, é um trabalho em andamento;).

5)
Aqui está um caso complexo (uma imagem real) capturado daqui em que a proposta de rotulagem foi aplicada e você vê os resultados. Observe que foram necessários apenas 0,015 s para todo o procedimento, incluindo rotular e localizar os objetos. Pessoal Scipy , fez um ótimo trabalho, eu acho. Uau! {clique com o botão direito do mouse na imagem, clique em Visualizar imagem para obter resolução total}

insira a descrição da imagem aqui

Desenvolvedor
fonte
Você sabe: 1) Número de embalagens. 2) Max / Min tamanho x de um pacote. 3) Tamanho máximo / mínimo de um pacote.
Spacey
@Mohammad Dado é apenas uma imagem. Portanto, nenhuma das informações necessárias mencionadas está disponível.
Desenvolvedor
Se você puder detectar o número de pacotes, eu usaria isso como o valor de 'k' em um algoritmo genérico de k-means. Ele convergirá para o centro de cada cluster, dado um valor de k. No entanto, não tenho certeza de como você poderá determinar o valor de 'k'. Como você vai determinar isso?
Spacey
Você precisa de precisão sub-pixel para transformação / erosão da distância para detectar o máximo nos pequenos remendos (por exemplo, 2x2). Existem máximos, mas não podem ser detectados, pois você os pula com sua amostragem. No caso de transformação à distância, é possível aumentar a amostra da imagem por fator de dois ou computar a transformação para posições de sub-pixel (0,0, 0,5, 1,0, 1,5 ...). Em caso de erosão, você pode implementá-lo usando morfologia baseada em PDE (iterativa).
Libor
@Developer esta pergunta minha sobre SO pode ser de interesse: stackoverflow.com/questions/4087919/...
Ivo Flipse

Respostas:

4

Apenas uma sugestão ingênua: você conhece a rotulagem de componentes ?

A técnica é encontrar pedaços de pixels "tocantes" e atribuir um rótulo a eles, por exemplo , um número inteiro. Em seguida, você pode interrogar cada fenda separadamente, procurando o pixel que compartilha o mesmo rótulo.

No MATLAB, aqui está a função que faz isso trivialmente: bwlabel

Jean-Yves
fonte
Obrigado pela proposta. Eu já havia abordado dessa maneira e, como você mencionou, atualizei o post com uma implementação em Python . Surgi alguns problemas relacionados ao uso de rotulagem na atualização 4 :
Desenvolvedor
Eu votei nisso uma vez que é outra abordagem para resolver o problema. Obrigado por compartilhar :)
Desenvolvedor
Você poderia esclarecer a atualização 4? Não entendo o que você quer dizer com troca e exaustão.
Jean-Yves
Fazer rotulagem é um trabalho iterativo requer muita computação. No entanto, os caras do Scipy fizeram um excelente trabalho (ou alguns truques!) Para fazê-lo quase imediatamente. Eu coloquei um caso realmente complexo para avaliação e funcionou apenas em 0,015 s. Não é demais? Observe que a segunda parte, ou seja, encontrar o centro dos pacotes detectados ainda é uma questão. Aparentemente, a aplicação de casco convexo para um conjunto tão mssive de pacotes não é recomendada.
Desenvolvedor
Não discordo: a rotulagem de componentes conectados NÃO é expansiva. Ele é executado em tempo linear na maioria das implementações modernas, e alguns até conseguiram executá-lo multithread.
Jean-Yves
3

Você também pode executar uma transformação de distância na imagem e detectar o máximo local (pesquisar pixels com o valor mais alto / mais baixo de todos os pixels no patch de 3x3 pixels - pode ser maior dependendo da distância mínima esperada entre os blobs originais).

Observe que, para detectar recursos com tamanhos de 1 a 3 pixels, é necessário dobrar sua frequência de amostragem (aumentar a imagem de origem ou executar a transformação / erosão da distância com precisão de sub-pixel).

ATUALIZAR:

As abordagens de transformação à distância e erosão pressupõem que os recursos que você está detectando são convexos. Algo com a forma de U, por exemplo, pode disparar no seu detector várias vezes.

Um método mais elaborado para essa segmentação é baseado em conjuntos de níveis e contornos ativos . Começa com uma grande curva fechada, adaptada iterativamente aos seus recursos. Este método foi usado na minha universidade para contar células e detectar cromossomos em imagens de microscópio.

Libor
fonte
Você pode ver o resultado da minha implementação da sua ideia na seção Atualizações: 2 . Parece que não funciona como o esperado :(
Desenvolvedor
OK, eu estendi minha resposta.
Libor
Eu votei nisso uma vez que é outra abordagem para resolver o problema. Obrigado por compartilhar :)
Desenvolvedor
2

Uma opção seria aplicar erosão morfológica repetida à imagem até que ela seja totalmente erodida. Nesse ponto, cada um dos blobs mostrados acima seria reduzido para um único pixel; você pode considerar a localização desses pixels como a lista de pontos que procura.

Jason R
fonte
Alguns pontos: 1) como parar a iteração? 2) pode ser que os pacotes sejam menores. 3) parece muito intensivo em computação, pois é necessária a iteração para todo o conjunto de dados. Observe que a imagem pode ser grande.
Desenvolvedor
Eu rapidamente implementei sua ideia na forma atual, mas ela não funcionou. Elimina embalagens pequenas. Todos os meus comentários anteriores se aplicam.
Desenvolvedor
Não sei o que você quer dizer com "embalagens pequenas". Alguma é mostrada na imagem de exemplo?
Jason R
Bem, como mostrado, os pacotes têm tamanhos e formatos diferentes e, quando apliquei erosão iterativa (Python: Scipy: Spatial: Erosion), os menores (ou mais estreitos) desapareceram. Observe que, no caso real, o pacote na imagem de entrada pode estar no intervalo de um pixel a muito grande.
Desenvolvedor
@ Desenvolvedor Você sabe o número de 'pacotes' com antecedência? Por exemplo, aqui você tem 6. #
Spacey
2

Receio que, seja qual for a maneira que você escolher, não será fácil, porque para atribuir os alvos aos clusters, você precisará passar pela imagem (pelo menos uma vez).

Suponho que obter os pontos seja o problema mais fácil dos dois (você provavelmente já está aplicando alguma forma de limiar, por exemplo).

Para recuperar os clusters nos quais os pontos estão agrupados e fazê-lo rapidamente, você pode criar uma estrutura de quatro árvores que contém "cadeias de pixels conectados" que estão em algum lugar ao redor da área da célula de quatro árvores.

Dessa forma, você pode percorrer a imagem e, depois de encontrar um pixel que é um alvo, "empurre" em sua estrutura de quatro árvores.

Essa operação "push" iniciaria um processo iterativo que retornaria a célula (em outras palavras, a área específica da imagem) onde está o pixel específico. Você poderia então percorrer todas as cadeias de pixels atribuídas a essa célula e tentar para "empurrar" (novamente) o pixel para a cadeia de pixels. Uma cadeia de pixels aceita um novo pixel se tiver pelo menos 1 pixel próximo a qualquer um dos pixels já atribuídos. Se nenhuma cadeia de pixels "aceitar" o novo pixel, crie uma nova cadeia de pixels nesta célula e atribua o novo pixel a ela.

A árvore quádrupla aqui é uma maneira de limitar sua pesquisa pela cadeia de pixels mais próxima e seria necessário se sua imagem fosse grande e os alvos fossem numerosos, para que as operações de push da cadeia de pixels fossem feitas rapidamente. Se você sabe que não está lidando com um grande número de alvos, pode até pular o quad-tree e manter uma simples "lista de cadeias de pixels". Toda vez que você encontrar um "alvo", poderá percorrer as listas e tentar "empurrar" o pixel nelas. Se nenhuma lista "admite" o pixel, crie uma nova lista e atribua o pixel.

Qualquer que seja a maneira que você escolher, no final deste processo, você terá um conjunto de "cadeias de pixels" conectadas (seus clusters) que você poderá passar para outra parte do seu programa que tratará de estimar suas localização. Pode ser um casco convexo, ajuste de modelo (por exemplo, elipsóide ou outro) ou simplesmente a média / mediana das coordenadas x, y.

Eu espero que isso ajude.

A_A
fonte
Eu votei nisso uma vez que é outra abordagem para resolver o problema. Obrigado por compartilhar :)
Desenvolvedor