F #, algoritmo de marcação para componentes de imagem conectados

A busca e marcação de componentes conectados em imagens binárias é um dos algoritmos básicos para análise e processamento de imagens. Em particular, esse algoritmo pode ser usado em visão de máquina para pesquisar e contar estruturas comuns na imagem, com suas análises subsequentes.

Na estrutura deste artigo, dois algoritmos para marcar componentes conectados serão considerados, sua implementação na linguagem de programação F # é mostrada. E também, uma análise comparativa dos algoritmos, a busca por pontos fracos. O material fonte para a implementação dos algoritmos foi retirado do livro “ Computer Vision” (autores L. Shapiro, J. Stockman. Tradução do inglês por A. A. Boguslavsky editado por S. M. Sokolov) .

Introdução

Um componente conectado com um valor de v é um conjunto de C desses pixels que têm um valor de ve cada par desses pixels é conectado com um valor de v

Parece obscuro, então vamos apenas ver a imagem. Assumimos que os pixels de primeiro plano da imagem binária estão marcados como 1 e os pixels de fundo estão marcados como 0 .

Depois de processar a imagem com o algoritmo de marcação dos componentes conectados, obtemos a seguinte imagem. Aqui, em vez de pixels, são formados componentes conectados, que diferem entre si em número. Neste exemplo, foram encontrados 5 componentes e será possível trabalhar com eles como em entidades separadas.

Figura 1: Componentes conectados rotulados

$$

$$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 2 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 2 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 \\ 3 & 3 & 3 & 3 & 0 & 4 & 0 & 2 \\ 0 & 0 & 0 & 3 & 0 & 4 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 0 & 0 & 2 \\ 5 & 5 & 0 & 3 & 0 & 2 & 2 & 2 \end{matrix}$$

Dois algoritmos que podem ser usados ​​para resolver esse problema serão considerados abaixo.

Algoritmo de rotulagem recursiva

Começaremos analisando o algoritmo baseado em recursão como o mais óbvio. O princípio de operação de um algoritmo será o seguinte:

atribua um rótulo, que marcaremos os componentes relacionados, o valor inicial.

1. Classificamos todos os pontos da tabela, começando com a coordenada 0x0 (canto superior esquerdo). Depois de processar o próximo ponto, aumente o rótulo em um
2. Se o pixel na coordenada atual for 1 , digitalizaremos todos os quatro vizinhos deste ponto (superior, inferior, direita, esquerda)
3. Se o ponto vizinho também for 1 , a função se chamará recursivamente para processar o vizinho até atingir o limite da matriz ou ponto 0
4. Durante o processamento recursivo do vizinho, é necessário verificar se o ponto ainda não foi processado e está marcado com o marcador atual.

Assim, classificando todos os pontos da matriz e invocando um algoritmo recursivo para cada um deles, no final da pesquisa, obtemos uma tabela totalmente marcada. Como é verificado se um determinado ponto já foi marcado, cada ponto será processado apenas uma vez. A profundidade da recursão dependerá apenas do número de vizinhos conectados ao ponto atual. Esse algoritmo é adequado para imagens que não possuem um preenchimento de imagem grande. Ou seja, imagens nas quais existem linhas finas e curtas e todo o resto é uma imagem de fundo que não é processada. Além disso, a velocidade de um algoritmo desse tipo pode ser maior que o algoritmo linha por linha (discutiremos mais adiante neste artigo).

Como as imagens binárias bidimensionais são matrizes bidimensionais, ao escrever o algoritmo, operarei com os conceitos de matrizes, sobre os quais fiz um artigo separado, que você pode ler aqui.Programação

funcional usando o exemplo de trabalho com matrizes da teoria da álgebra

linear.Considere e analise em detalhes a função F # que implementa algoritmo de rotulagem recursiva para componentes de imagem binária conectados

let recMarkingOfConnectedComponents matrix =

        let copy = Matrix.clone matrix

        let (|Value|Zero|Out|) (x, y) = 
            if x < 0 || y < 0
                || x > (copy.values.[0, *].Length - 1)
                || y > (copy.values.[*, 0].Length - 1) then
                Out
            else
                let row = copy.values.[y, *]
                match row.[x] with
                    | 0 -> Zero
                    | v -> Value(v)

        let rec markBits x y value =
            match (x, y) with
            | Value(v) ->
                if value > v then
                    copy.values.[y, x] <- value
                    markBits (x + 1) y value
                    markBits (x - 1) y value
                    markBits x (y + 1) value
                    markBits x (y - 1) value
            | Zero | Out -> ()

        let mutable value = 2
        copy.values
        |> Array2D.iteri (fun y x v -> if v = 1 then
                                            markBits x y value
                                            value <- value + 1)

        copy 

Declaramos a função recMarkingOfConnectedComponents , que utiliza uma matriz bidimensional de matriz, compactada em um registro do tipo Matrix. A função não alterará a matriz original; primeiro, crie uma cópia da mesma, que será processada pelo algoritmo e retornada.

let copy = Matrix.clone matrix

Para simplificar as verificações dos índices dos pontos solicitados fora da matriz, crie um modelo ativo que retorne um dos três valores.

Fora - o índice solicitado foi além da matriz bidimensional
Zero - o ponto contém um pixel de segundo plano (igual a zero)
Valor - o índice solicitado está dentro da matriz

Este modelo simplifica a verificação das coordenadas do ponto de imagem no próximo quadro de recursão:

let (|Value|Zero|Out|) (x, y) = 
    if x < 0 || y < 0
        || x > (copy.values.[0, *].Length - 1)
        || y > (copy.values.[*, 0].Length - 1) then
        Out
    else
        let row = copy.values.[y, *]
        match row.[x] with
            | 0 -> Zero
            | v -> Value(v)

A função MarkBits é declarada recursiva e serve para processar o pixel atual e todos os seus vizinhos (superior, inferior, esquerdo, direito):

let rec markBits x y value =
    match (x, y) with
    | Value(v) ->
        if value > v then
            copy.values.[y, x] <- value
            markBits (x + 1) y value
            markBits (x - 1) y value
            markBits x (y + 1) value
            markBits x (y - 1) value
    | Zero | Out -> ()

A função aceita os seguintes parâmetros como entrada:

x - número da linha
y -
valor do número da coluna - valor atual do rótulo para marcar o pixel

Usando a construção match / with e o modelo ativo (acima), as coordenadas do pixel são verificadas para que não ultrapassem o tamanho bidimensional array. Se o ponto estiver dentro de uma matriz bidimensional, fazemos uma verificação preliminar para não processar o ponto que já foi processado.

if value > v then

Caso contrário, ocorrerá uma recursão infinita e o algoritmo não funcionará.

Em seguida, marque o ponto com o valor atual do marcador:

copy.values.[y, x] <- value

E processamos todos os seus vizinhos, chamando recursivamente a mesma função:

markBits (x + 1) y value
markBits (x - 1) y value
markBits x (y + 1) value
markBits x (y - 1) value

Depois de implementarmos o algoritmo, ele deve ser usado. Considere o código em mais detalhes.

let mutable value = 2
copy.values
|> Array2D.iteri (fun y x v -> if v = 1 then
                                    markBits x y value
                                    value <- value + 1) 

Antes de processar a imagem, defina o valor inicial do rótulo, que marcará os grupos de pixels conectados.

let mutable value = 2

O fato é que os pixels frontais na imagem binária já estão definidos como 1 ; portanto, se o valor inicial do rótulo também for 1 , o algoritmo não funcionará. Portanto, o valor inicial do rótulo deve ser maior que 1 . Existe outra maneira de resolver o problema. Antes de iniciar o algoritmo, marque todos os pixels definidos como 1 com um valor inicial de -1 . Então podemos definir o valor como 1 . Você pode fazer isso sozinho, se quiser.A

próxima construção, usando a função Array2D.iteri , itera sobre todos os pontos da matriz e, durante a pesquisa, você encontra um ponto definido como 1, isso significa que não é processado e, para isso, é necessário chamar a função recursiva markBits com o valor atual da etiqueta. Todos os pixels definidos como 0 são ignorados pelo algoritmo.

Após o processamento recursivo do ponto, podemos assumir que todo o grupo conectado ao qual esse ponto pertence é garantido para ser marcado e você pode aumentar o valor do rótulo em 1 para aplicá-lo ao próximo ponto conectado.

Considere um exemplo da aplicação de um algoritmo desse tipo.

let a = array2D [[1;1;0;1;1;1;0;1]
                 [1;1;0;1;0;1;0;1]
                 [1;1;1;1;0;0;0;1]
                 [0;0;0;0;0;0;0;1]
                 [1;1;1;1;0;1;0;1]
                 [0;0;0;1;0;1;0;1]
                 [1;1;0;1;0;0;0;1]
                 [1;1;0;1;0;1;1;1]]
let A = Matrix.ofArray2D a

let t = System.Diagnostics.Stopwatch.StartNew()
let R = Algorithms.recMarkingOfConnectedComponents A
t.Stop()

printfn "origin =\n %A" A.values
printfn "rec markers =\n %A" R.values
printfn "elapsed recurcive = %O" t.Elapsed 

origin =
 [[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]

rec markers =
 [[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]

elapsed recurcive = 00:00:00.0037342

As vantagens de um algoritmo recursivo incluem sua simplicidade na escrita e no entendimento. É excelente para imagens binárias contendo um fundo grande e intercaladas com pequenos grupos de pixels (por exemplo, linhas, pequenos pontos etc.). Nesse caso, a velocidade de processamento da imagem pode ser alta, pois o algoritmo processa toda a imagem em uma única passagem.

As desvantagens também são óbvias - isso é recursão. Se a imagem consistir em pontos grandes ou for completamente inundada, a velocidade de processamento diminuirá drasticamente (por ordens de magnitude) e existe o risco de o programa travar devido à falta de espaço livre na pilha.

Infelizmente, o princípio da recursão da cauda não pode ser aplicado neste algoritmo, porque a recursão da cauda tem dois requisitos:

1. Cada quadro de recursão deve executar cálculos e adicionar o resultado ao acumulador, que será transmitido pela pilha.
2. Não deve haver mais de uma chamada de função recursiva em um quadro de recursão.

No nosso caso, a recursão não realiza nenhum cálculo final, que pode ser passado para o próximo quadro de recursão, mas modifica simplesmente uma matriz bidimensional. Em princípio, isso pode ser contornado simplesmente retornando um número único, o que por si só não significa nada. Também fazemos quatro chamadas recursivamente, pois precisamos processar todos os quatro vizinhos do ponto.

Algoritmo clássico para marcar componentes conectados com base na estrutura de dados para combinar pesquisas

O algoritmo também tem outro nome, "Algoritmo de marcação progressiva", e aqui tentaremos analisá-lo.

. . . , , .

A definição acima é ainda mais confusa, portanto, tentaremos lidar com o princípio do algoritmo de uma maneira diferente e começar de longe.

Primeiro, trataremos da definição de uma vizinhança com quatro e oito conexões do ponto atual. Veja as figuras abaixo para entender o que é e qual a diferença.

Figura 2: O componente de quatro conexões
\ begin {matrix} Figura 2: O componente de oito conexões \ begin {matrix} A primeira imagem mostra um componente com quatro conexões $$\begin{matrix} & 1 & \\ 2 & * & 3 \\ & 4 & \end{matrix}$$


$$\begin{matrix} 1 & 2 & 3 \\ 4 & * & 5 \\ 6 & 7 & 8 \end{matrix}$$
pontos, isto é, isso significa que o algoritmo processa 4 vizinhos do ponto atual (esquerda, direita, superior e inferior). Assim, o componente de oito pontos conectado de um ponto significa que ele tem 8 vizinhos. Neste artigo, trabalharemos com quatro componentes conectados.

Agora você precisa descobrir o que é uma estrutura de dados para combinar a pesquisa , construída em alguns conjuntos?

Por exemplo, suponha que tenhamos dois conjuntos

$$

$$(1, 2, 3, 4, 8) (5, 6, 7)$$

Esses conjuntos são organizados na forma das seguintes árvores:





Observe que no primeiro conjunto, os nós 3 são raiz e, no segundo, nós 6.

Agora, consideramos a estrutura de dados para uma união de pesquisa, que contém esses dois conjuntos, e também organiza sua estrutura em árvore. .

Figura 4: Estrutura de dados para união de pesquisa
\ begin {matrix} matriz Observe atentamente a tabela acima e tente encontrar um relacionamento com as árvores definidas acima. A tabela deve ser visualizada em colunas verticais. É visto,que o número 3 na primeira linha corresponde ao número 0 $$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 0 & 3 & 7 & 7 & 0 & 3 \end{matrix}$$

na segunda linha. E na primeira árvore, o número 3 é a raiz do primeiro conjunto. Por analogia, você pode descobrir que o número 7 da primeira linha corresponde ao número 0 da segunda linha. O número 7 também é a raiz da árvore do segundo conjunto.

Assim, concluímos que os números da linha superior são os nós filhos dos conjuntos, e os números correspondentes da linha inferior são os nós pais. Guiado por esta regra, você pode restaurar facilmente as duas árvores da tabela acima.

Analisamos esses detalhes para que, mais tarde, seja mais fácil entender como o algoritmo de marcação progressiva funciona.. Por enquanto, vamos nos concentrar no fato de que uma série de números da primeira linha é sempre de 1 a um determinado número máximo. De fato, o número máximo da primeira linha é o valor máximo das etiquetas com as quais os componentes conectados encontrados serão marcados . E conjuntos individuais são transições entre rótulos formados como resultado da primeira passagem (consideraremos mais detalhadamente mais adiante).

Antes de prosseguir, considere o pseudocódigo de algumas funções que serão usadas pelo algoritmo.

Denotamos a tabela que representa a estrutura de dados da pesquisa de junção como PARENT . A próxima função é chamada find e usará o rótulo atual X como parâmetrose uma matriz de pais . Este procedimento rastreia os ponteiros pai até a raiz da árvore e localiza o rótulo do nó raiz da árvore à qual X pertence .

 ̆   ̆  .
X —  
PARENT — , ̆    -

procedure find(X, PARENT);
{
j := X;
while PARENT[j] <> 0
    j := PARENT[j]; return(j);
}

Considere como essa função pode ser implementada no F #

let rec find x =
    let index = Array.tryFindIndex ((=)x) parents.[0, *]
    match index with
    | Some(i) -> 
        match parents.[1, i] with
        | p when p <> 0 -> find p
        | _ -> x
    | None -> x 

Aqui nós declaramos uma função recursiva do achado , que leva o rótulo atual do X . A matriz PARRENT não é passada aqui, pois já a temos no espaço de nomes global e a função já a vê e pode trabalhar com ela.

Primeiro, a função tenta encontrar o índice do rótulo na linha superior (já que você precisa encontrar o pai, localizado na linha inferior).

let index = Array.tryFindIndex ((=)x) parents.[0, *]

Se a pesquisa for bem-sucedida, obtemos o pai e comparamos com 0 . Se o pai não for igual a 0 , esse nó também terá um pai e a função se chamará recursivamente até que o pai seja igual a 0 . Isso significa que encontramos o nó raiz do conjunto.

match index with
    | Some(i) -> 
        match parents.[1, i] with
        | p when p <> 0 -> find p
        | _ -> x
    | None -> x 

A próxima função que precisamos é chamada de união . São necessários dois rótulos X e Y , além de uma matriz de PAI . Esta estrutura modifica (se necessário) PAI subconjunto de fus contendo uma etiqueta de X , com o conjunto que compreende etiqueta Y . O procedimento procura os nós raiz dos dois rótulos e, se não corresponderem, o nó de um dos rótulos é designado como o nó pai do segundo rótulo. Portanto, há uma união de dois conjuntos.

   .
X — ,   .
Y — ,   .
PARENT — , ̆    -.

procedure union(X, Y, PARENT);
{
j := X;
k := Y;
while PARENT[j] <> 0
    j := PARENT[j];
while PARENT[k]] <> 0
    k := PARENT[k];

if j <> k then PARENT[k] := j;
} 

A implementação de F # se parece com isso

let union x y =
    let j = find x
    let k = find y
    if j <> k then parents.[1, k-1] <- j 

Observe que a função find que já implementamos já é usada aqui .

O algoritmo também requer duas funções adicionais, chamadas de vizinhos e rótulos . A função vizinhos retorna o conjunto de pontos vizinhos para a esquerda e para cima (já que, no nosso caso, o algoritmo funciona em um componente conectado a quatro) a partir do pixel fornecido, e a função labels retorna o conjunto de etiquetas que já foram atribuídas ao conjunto de pixels fornecido pela função vizinha . No nosso caso, não implementaremos essas duas funções, mas faremos apenas uma que combine as duas funções e retorne os rótulos encontrados.

let neighbors_labels x y =
    match (x, y) with
    | (0, 0) -> []
    | (0, _) -> [step1.[0, y-1]]
    | (_, 0) -> [step1.[x-1, 0]]
    | _ -> [step1.[x, y-1]; step1.[x-1, y]]
    |> List.filter ((<>)0) 

Olhando para o futuro, direi imediatamente que a matriz step1 que usa a função já existe no espaço global e contém o resultado do processamento do algoritmo na primeira passagem. Quero prestar atenção especial ao filtro adicional.

|> List.filter ((<>)0)

Ele corta todos os resultados que são 0 . Ou seja, se o rótulo contiver 0 , estaremos lidando com um ponto na imagem de plano de fundo que não precisa ser processado. Essa é uma nuance muito importante que não é mencionada no livro, da qual tiramos exemplos, mas, no entanto, o algoritmo não funcionará sem essa verificação.

Gradualmente, passo a passo, nos aproximamos da própria essência do algoritmo. Vamos olhar novamente para a imagem que precisaremos processar.

Figura 5: Imagem binária original
\ begin {matrix} $$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \end{matrix}$$

Antes do processamento, crie uma matriz vazia step1 , na qual o resultado da primeira passagem será salvo.

Figura 6: Matriz etapa1 para armazenar os principais resultados do processamento
$$\begin{matrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$

Considere as primeiras etapas do processamento de dados primário (apenas as três primeiras linhas da imagem binária original).

Antes de darmos uma olhada passo a passo no algoritmo, vejamos o pseudo-código que explica o princípio geral de operação.

     .
B —   .
LB —   .

procedure classical_with_union-find(B, LB);
{
“  .” initialize();
“  1 ̆  L     .”
for L := 0 to MaxRow
{
“     L  ”
for P := 0 to MaxCol
    LB[L,P] := 0;
“  L.”
for P := 0 to MaxCol
    if B[L,P] == 1 then
    {
        A := prior_neighbors(L,P);
        if isempty(A)
        then {M := label; label := label + 1;};
        else M := min(labels(A));
        LB[L,P] := M;
        for X in labels(A) and X <> M
           union(M, X, PARENT);
    }
}
“  2 ,    1,     .”
for L := 0 to MaxRow
    for P := 0 to MaxCol
        if B[L, P] == 1
        then LB[L,P] := find(LB[L,P], PARENT);
};
      LB ( step1)     ( ).

Figura 7: Etapa 1. Ponto (0,0), rótulo = 1
$$\begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
Figura 8: Etapa 2. Ponto (1,0), label = 1
$$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
Figura 9: Etapa 2. Ponto (2.0), label = 1
$$\begin{matrix} 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
Figura 10: Etapa 4. Ponto (3.0), label = 2
$$\begin{matrix} 1 & 1 & 0 & 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix}$$
Figura 11: Última etapa, resultado final da primeira passagem
$$\begin{matrix} 1 & 1 & 0 & 2 & 2 & 2 & 0 & 3 \\ 1 & 1 & 0 & 2 & 0 & 2 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 7 & 7 & 3 \end{matrix}$$
Observe que, como resultado do processamento inicial da imagem original, obtivemos dois conjuntos

$$

$$(1,2) - (3,7)$$

Visualmente, isso pode ser visto como o contato das marcas 1 e 2 (coordenadas dos pontos (1,3) e (2,3) ) e das marcas 3 e 7 (coordenadas dos pontos (7,7) e (7,6) ). Do ponto de vista da estrutura de dados para união de pesquisa, esse resultado é obtido.

Figura 12: Estrutura de dados computada para agregação de pesquisa
$$\begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 3 \end{matrix}$$
Depois de finalmente processar a imagem usando a estrutura de dados obtida, obtemos o seguinte resultado.

Figura 13: Resultado final
$$\begin{matrix} 1 & 1 & 0 & 1 & 1 & 1 & 0 & 3 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 & 3 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 3 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 3 \\ 4 & 4 & 4 & 4 & 0 & 5 & 0 & 3 \\ 0 & 0 & 0 & 4 & 0 & 5 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 0 & 0 & 3 \\ 6 & 6 & 0 & 4 & 0 & 3 & 3 & 3 \end{matrix}$$
Agora, todos os componentes conectados, temos etiquetas exclusivas e podem ser usados ​​em algoritmos subsequentes para processamento.

A implementação do código F # é a seguinte

let markingOfConnectedComponents matrix =

    // up to 10 markers
    let parents = Array2D.init 2 10 (fun x y -> if x = 0 then y+1 else 0)

    // create a zero initialized copy
    let step1 = (Matrix.cloneO matrix).values

    let rec find x =
        let index = Array.tryFindIndex ((=)x) parents.[0, *]
        match index with
        | Some(i) -> 
            match parents.[1, i] with
            | p when p <> 0 -> find p
            | _ -> x
        | None -> x

    let union x y =
        let j = find x
        let k = find y
        if j <> k then parents.[1, k-1] <- j

    // returns up and left neighbors of pixel
    let neighbors_labels x y =
        match (x, y) with
        | (0, 0) -> []
        | (0, _) -> [step1.[0, y-1]]
        | (_, 0) -> [step1.[x-1, 0]]
        | _ -> [step1.[x, y-1]; step1.[x-1, y]]
        |> List.filter ((<>)0)

    let mutable label = 0
    matrix.values
    |> Array2D.iteri (fun x y v ->
                        if v = 1 then
                            let n = neighbors_labels x y
                            let m = if n.IsEmpty then
                                        label <- label + 1
                                        label
                                    else
                                        n |> List.min
                            n |> List.iter (fun v -> if v <> m then union m v)
                            step1.[x, y] <- m)

    let step2 = matrix.values
                |> Array2D.mapi (fun x y v ->
                        if v = 1 then step1.[x, y] <- find step1.[x, y]
                        step1.[x, y])

    { values = step2 } 

Uma explicação linha a linha do código não faz mais sentido, pois tudo foi descrito acima. Aqui você pode simplesmente mapear o código F # para o pseudo-código para deixar claro como ele funciona.

Algoritmos de Benchmarking

Vamos comparar a velocidade de processamento de dados com os dois algoritmos (recursivo e em linha).

let a = array2D [[1;1;0;1;1;1;0;1]
                 [1;1;0;1;0;1;0;1]
                 [1;1;1;1;0;0;0;1]
                 [0;0;0;0;0;0;0;1]
                 [1;1;1;1;0;1;0;1]
                 [0;0;0;1;0;1;0;1]
                 [1;1;0;1;0;0;0;1]
                 [1;1;0;1;0;1;1;1]]
let A = Matrix.ofArray2D a

let t1 = System.Diagnostics.Stopwatch.StartNew()
let R1 = Algorithms.markingOfConnectedComponents A
t1.Stop()

let t2 = System.Diagnostics.Stopwatch.StartNew()
let R2 = Algorithms.recMarkingOfConnectedComponents A
t2.Stop()

printfn "origin =\n %A" A.values
printfn "markers =\n %A" R1.values
printfn "rec markers =\n %A" R2.values

printfn "elapsed lines = %O" t1.Elapsed
printfn "elapsed recurcive = %O" t2.Elapsed 

origin =
 [[1; 1; 0; 1; 1; 1; 0; 1]
 [1; 1; 0; 1; 0; 1; 0; 1]
 [1; 1; 1; 1; 0; 0; 0; 1]
 [0; 0; 0; 0; 0; 0; 0; 1]
 [1; 1; 1; 1; 0; 1; 0; 1]
 [0; 0; 0; 1; 0; 1; 0; 1]
 [1; 1; 0; 1; 0; 0; 0; 1]
 [1; 1; 0; 1; 0; 1; 1; 1]]
markers =
 [[1; 1; 0; 1; 1; 1; 0; 3]
 [1; 1; 0; 1; 0; 1; 0; 3]
 [1; 1; 1; 1; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]
rec markers =
 [[2; 2; 0; 2; 2; 2; 0; 3]
 [2; 2; 0; 2; 0; 2; 0; 3]
 [2; 2; 2; 2; 0; 0; 0; 3]
 [0; 0; 0; 0; 0; 0; 0; 3]
 [4; 4; 4; 4; 0; 5; 0; 3]
 [0; 0; 0; 4; 0; 5; 0; 3]
 [6; 6; 0; 4; 0; 0; 0; 3]
 [6; 6; 0; 4; 0; 3; 3; 3]]
elapsed lines = 00:00:00.0081837
elapsed recurcive = 00:00:00.0038338

Como você pode ver, neste exemplo, a velocidade do algoritmo recursivo excede significativamente a velocidade do algoritmo linha a linha. Mas tudo muda assim que começarmos a processar uma imagem preenchida com cores sólidas e, para maior clareza, também aumentaremos o tamanho para 100x100 pixels.

let a = Array2D.create 100 100 1
let A = Matrix.ofArray2D a

let t1 = System.Diagnostics.Stopwatch.StartNew()
let R1 = Algorithms.markingOfConnectedComponents A
t1.Stop()
printfn "elapsed lines = %O" t1.Elapsed

let t2 = System.Diagnostics.Stopwatch.StartNew()
let R2 = Algorithms.recMarkingOfConnectedComponents A
t2.Stop()
printfn "elapsed recurcive = %O" t2.Elapsed 

elapsed lines = 00:00:00.0131790
elapsed recurcive = 00:00:00.2632489

Como você pode ver, o algoritmo recursivo já é 25 vezes mais lento que o linear. Vamos aumentar o tamanho da imagem para 200x200 pixels.

elapsed lines = 00:00:00.0269896
elapsed recurcive = 00:00:06.1033132

A diferença já é muitas centenas de vezes. Observo que já em um tamanho de 300x300 pixels, o algoritmo recursivo causa um estouro de pilha e o programa trava.

Sumário

Na estrutura deste artigo, um dos algoritmos básicos para marcar componentes conectados para o processamento de imagens binárias foi examinado usando a linguagem funcional F # como exemplo. Aqui foram dados exemplos da implementação de algoritmos recursivos e clássicos, seu princípio de operação foi explicado e uma análise comparativa foi realizada usando exemplos específicos.

O código fonte discutido aqui também pode ser visualizado no
github MatrixAlgorithms.Espero

que este artigo seja interessante para os interessados ​​em F # e algoritmos de processamento de imagem em particular.