Contando Bolhas

O SeedFill (ou FloodFill) é o conhecido algoritmo que nos permite, nos mais comuns editores de imagem (o famoso balde de tinta no Paint, do Windows, ou o Pinta, mais comum no linux), preencher determinada região com uma cor específica. Para isso, o algoritmo verifica se as regiões próximas ao ponto possuem a mesma cor que esse ponto, e se sim elas são preenchidas com a cor especificada.

Desse modo, escolhendo um ponto \$(x,y)\$ como sendo o ponto inicial

Esse algoritmo ilustra o mais simples seedFill, e é o que foi implementado no nosso código .cpp:

O que é importante notarmos é que temos um tipo que não pertence às bibliotecas iostream ou opencv, que é a classe coordenada. Apesar da biblioteca opencv possuir uma classe semelhante (CvPoint), essa às vezes pode confundir por não usar o sistema destrógiro, e é de grande vantagem sabermos implementar nossa classe para um melhor desempenho do código. A classe está mostrada a seguir:

A definimos como struct pois queremos que seus valores sejam públicos, e não precisamos de um acesso seguro, precisamos somente de uma rapidez maior no acesso à classe. A segunda linha contém um construtor default.

No algoritmo do seedFill, passamos como parâmetro o x e o y de início, a cor que desejamos e a imagem a ser preenchida. O primeiro teste que fazemos é para a cor do ponto que passamos como parâmetro, que é feita pela linha de código a seguir:

A seguir adicionamos o ponto à pilha, com a função push(), a qual podemos obter mais informações no CppReference, assim como a função top() e pop(). Iniciamos o loop while() testando se a pilha está ou não vazia. Depois retiramos as informações do primeiro elemento da pilha com a função top(), e retiramos esse primeiro elemento da pilha com a função pop(). A seguir temos 4 if()'s, para que possamos testar os valores dos 4-vizinhos do ponto inicial.

O que é importante notarmos nos if()'s são suas condições. para os vizinhos da esquerda e de cima, os valores de x e y não podem ser 0, caso contrário acessaríamos valores de -1, que não existem na matriz da imagem. Para os vizinhos da direita e de baixo, os valores de x e y têm de ser 2 valores menores que o tamanho da imagem, já que o último elemento da matriz é matriz[linhas-1][colunas-1].

A última linha, mostrada a seguir, ajusta o valor do pixel para a cor desejada, passada como parâmetro. O loop continua até a pilha se esvaziar.

Vamos começar a analisar o código a partir de suas bibliotecas.

Utilizamos a biblioteca iostream, indispensável quando vamos programar em c++ (contém algumas funções essenciais como o cin>> e o cout<<). Também utilizamos a biblioteca opencv.hpp, que se encontra na pasta opencv2 e que será informada ao compilador através do arquivo Makefile. Por último temos a biblioteca stack, que é parte da STL e que nos proporcionará o uso da classe stack (ou pilha). Temos as funções namespace que facilitam a nossa vida para que não precisemos digitar cv:: toda vez que formos utilizar a classe Mat.

Na função main() temos nossa função principal, e seus argumentos serão explicados numa sessão posterior.

Começamos lendo a imagem com a função ìmread(), cuja documentação está disponível online, assim como de outras funções do opencv. Os atributos .rows e .cols da classe Mat retornam a quantidade de linhas e de colunas, respectivamente. Temos o objeto int counter que servirá para rotularmos as bolhas, e o vetor int nBubbles[] será utilizado posteriormente.

Os dois loops for() iniciais servem para varrer as bordas da imagem, e caso achem alguma bolha que toque na borda ela será removida (temos um seedFill com a mesma cor do fundo). Depois fazemos dois loops encadeados, para que possamos varrer todos os elementos da imagem (coluna por coluna de cada linha). Caso o programa encontre alguma bolha (image.at<uchar>(i,j) == 255) ele executará um seedFill com o valor de counter, que é o nosso rótulo. O valor de counter é iniciado em 32 e incrementado de 5 em 5 para podermos visualizar melhor as variações nos tons de cinza. Caso tivéssemos muitas bolhas isso não seria possível.

Por último temos:

Essas linhas de código, respectivamente:

Na segunda parte do código iremos contar a quantidade de bolhas, separando as que não possuem buracos das que possum 1, 2 ou n buracos.

Começaremos realizando um seedFill no fundo da imagem, com o valor de 254. Não rotulamos com 255 pois não conseguiríamos distinguir das bolhas. Desse modo distinguiremos o fundo do restante dos buracos das bolhas. Depois procuraremos bolhas e as rotularemos como 1. Não podemos rotular como 0 pois seria impossível distinguir dos buracos. O rótulo das bolhas é igual ao número de buracos que ela contém+1.

\$\text{nBuracos(i)} = \text{Rotulo(i)} - 1\$

Onde o índice i representa o número da bolha. O próximo loop procurará por pixels de valor 0, ou seja, buracos. Cada vez que ele acha um buraco, ele o preenche com o valor do fundo (254) e preenche a bolha com o rótulo_da_bolha+1 (mesmo que rotulo_da_bolha++).

Por fim, temos um loop para procurar bolhas na imagem. Uma bolha será qualquer região cujo valor seja diferente de 254. Quando encontrarmos uma bolha, usaremos o valor de seu rótulo para aumentar o valor de nBubbles na posição desejada, em que 0 é sem buracos. nBubbles é um vetor que armazena a quantidade de bolhas na imagem. Após utilizarmos seu valor, eliminamos a bolha, fazendo com que sua cor (ou seu rótulo) seja igual à cor de fundo.

A abertura da imagem se dá, no linux, devido à passagem de parâmetros durante a execução do código no terminal. O trecho de código:

Os argumentos da função main() são utilizados quando executamos o código no terminal do linux (tal coisa não acontece no Windows). O primeiro parâmetro diz quantos argumentos foram passados durante a chamada da execução do programa, e o segundo parâmetro, que é o vetor, retorna strings que correspondem ao nome do programa e dos parâmetros passados, respectivamente. A chamada do nosso programa é a seguinte (no terminal, após termos executado o Makefile):

Os valores de argc (argument count) e argv (argument value), são, respectivamente:

As primeiras linhas do código, apresentadas abaixo, fazem a leitura dos argumentos passados como parâmetro e consequente abertura do arquivo de imagem, utilizando a função ìmread(), cuja documentação está disponível juntamente da classe cv::Mat, também disponível nesse link.

O código prevê bolhas com até 3 buracos, mas como podemos fazer para que sejam previstos mais buracos? Basta alterarmos a dimensão do vetor nBubbles[] para a quantidade que desejarmos. Isso pode ser pedido ao usuário ou não.

Caso tenhamos uma quantidade bolhas maior que 252 (não é 255 devido aos rótulos que utilizamos no código) podemos criar uma escala de falsos tons de cinza, utilizando RGB e aumentarmos a quantidade possível de buracos (aumentando o tamanho do rótulo da bolha).

A figura original é mostrada abaixo, juntamente com a saída do programa, logo em seguida.

Verificamos o funcionamento do código através da função cout<<, que irá imprimir na tela o resultado da contagem: