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

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?

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

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} .

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!

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()

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:

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}

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

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.

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.

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.