Técnicas de contagem de objetos em imagens

Ideia Geral

Contar objetos em uma imagem é uma tarefa fundamental em Processamento de Imagens, nesse artigo iremos discutir algumas técnicas para isso.

Cenário 1

Nesse primeiro cenário vamos explorar uma técnica simples e eficiente para contar objetos usando imagens no formato PBM(Portable Bitmap), que são imagens binárias em que cada pixel só pode ser preto(1) ou branco(0).

Temos uma imagem binária em que os pixels brancos representam o fundo e os pixels pretos representam os objetos. Nosso objetivo é contar quantos objetos distintos existem na imagem. Chamamos esses objetos de ilhas, pois são agrupamentos de pixels pretos conectados entre si.

Solução: Busca em Largura(BFS)

A estratégia utilizada é baseada no algoritmo de busca em largura (BFS - Breadth-First Search). A ideia é simples e elegante:

1. Percorremos toda a matriz da imagem pixel por pixel
2. Quando encontramos um pixel de valor 1, isso significa que descobrimos uma nova ilha
3. A partir desse pixel, exploramos todos os pixels adjacentes conectados, “conquistando” toda a ilha
4. Marcamos os pixels visitados como 0 para evitar contá-los novamente
5. Continuamos o processo até varrer toda a imagem

Estrutura do Código

Funções Auxiliares

O código começa com funções básicas para manipulação de matrizes:

create_matrix: Aloca dinamicamente uma matriz bidimensional para armazenar a imagem.

destroy_matrix: Libera a memória alocada pela matriz.

inside: Verifica se uma coordenada está dentro dos limites da imagem, evitando acessos inválidos à memória.

A Função de Conquista

A função conquista é o coração do algoritmo. Ela recebe as coordenadas de um pixel branco e explora toda a “ilha” conectada a ele:

void conquista (int **matrix, int i, int j, int nrows, int ncols)
{
  Queue *q = create(nrows*ncols+1); 
  enqueue (q, (point){i,j});
  matrix[i][j] = 0; 
  while (!empty(q))
  {
    point p = dequeue (q);
    int x, y;
     for (x = -1; x <= +1; x++)
     {
      for (y = -1; y <= +1; y++)
      {
        int sx = p.x + x;
        int sy = p.y + y;	    
        if (inside(sx, sy, nrows, ncols) && matrix[sx][sy] == 1)
        {
	        enqueue (q, (point){sx,sy});
	        matrix[sx][sy] = 0;
	      }  
      }	
    }  
  }
  destroy (q); 
}

O processo funciona assim:

• Uma fila é criada para armazenar as coordenadas dos pixels a serem explorados
• O pixel inicial é adicionado à fila e marcado como visitado (valor 0)
• Enquanto houver pixels na fila, retiramos um e verificamos seus 8 vizinhos (horizontal, vertical e diagonal)
• Cada vizinho que for 1 é adicionado à fila e marcado como visitado
• Isso garante que toda a ilha conectada seja explorada

Contando as Ilhas

A função count_islands coordena todo o processo:

int count_islands (int **matrix, int nrows, int ncols)
{
  int i, j, sum = 0;	
  for (i = 0; i < nrows; i++)
  {
    for (j = 0; j < ncols; j++)
    {
      if (matrix[i][j] == 1)
      {
	      sum++;
        conquista (matrix, i, j, nrows, ncols);     
      }	      
    }	     
  }
  return sum;
}

Ela percorre cada pixel da matriz. Sempre que encontra um pixel branco, incrementa o contador de ilhas e chama a função conquista para marcar toda aquela ilha como visitada. Ao final, retorna o número total de ilhas encontradas.

O Programa Principal

A função main gerencia a leitura do arquivo PBM:

1. Abre o arquivo de imagem (“parafusos.pbm”)
2. Lê o cabeçalho PBM
3. Carrega os pixels da imagem em uma matriz
4. Chama a função de contagem
5. Exibe o resultado e libera a memória

Complexidade e Eficiência

A complexidade temporal deste algoritmo é O(n × m), onde n e m são as dimensões da imagem. Cada pixel é visitado no máximo uma vez durante a varredura inicial e uma vez durante a exploração das ilhas. A complexidade espacial também é O(n × m) devido ao armazenamento da matriz e da fila.

Resultados

Imagem de cromossomos.

Resultado : Número de ilhas: 5

Imagem de Parafusos.

Resultado : Número de ilhas: 8

Cenário 2: Trabalhando com Imagens Coloridas (PNG)

No cenário anterior, trabalhamos com imagens binárias no formato PBM, que já vinham prontas com pixels pretos e brancos. Porém, no mundo real, lidamos principalmente com imagens coloridas em formatos como PNG, JPEG, etc. Neste cenário, vamos evoluir nossa técnica para processar imagens coloridas e transformá-las em imagens binárias adequadas para contagem.

O Desafio

Quando temos uma imagem colorida, precisamos realizar algumas etapas de pré-processamento antes de aplicar o algoritmo de contagem:

1. Converter a imagem colorida para escala de cinza
2. Aplicar um threshold (limiar) para binarizar a imagem
3. Filtrar ruídos e artefatos indesejados
4. Contar os objetos usando o algoritmo BFS

Conversão para Escala de Cinza

O primeiro passo é transformar uma imagem RGB (Red, Green, Blue) em escala de cinza. Não basta simplesmente fazer a média dos três canais de cor, pois nossos olhos têm sensibilidades diferentes para cada cor. A fórmula padrão utilizada é:

\[\text{Gray} = 0.299 \times R + 0.587 \times G + 0.114 \times B\]

Esses coeficientes refletem a sensibilidade do olho humano, que é mais sensível ao verde, seguido pelo vermelho e por último o azul. No código, isso é implementado durante a leitura da imagem PNG:

for (int x = 0; x < width; x++) {
    png_bytep px = &(row[x * 4]);
    img->data[y][x] = (px[0] * 0.299 + px[1] * 0.587 + px[2] * 0.114);
}

Binarização com Threshold

Após obter a imagem em escala de cinza (valores de 0 a 255), precisamos transformá-la em uma imagem binária (apenas 0 ou 1). Isso é feito através de um threshold (limiar):

int** convert_to_binary(image *img, int threshold) {
    int **binary = (int**)malloc(img->h * sizeof(int*));
    
    for (int y = 0; y < img->h; y++) {
        binary[y] = (int*)malloc(img->w * sizeof(int));
        for (int x = 0; x < img->w; x++) {
            binary[y][x] = (img->data[y][x] >= threshold) ? 1 : 0;
        }
    }
    
    return binary;
}

A lógica é simples: pixels com intensidade maior ou igual ao threshold tornam-se brancos (1), e pixels abaixo do threshold tornam-se pretos (0). No exemplo atual, usamos threshold = 128, que é exatamente o meio da escala (0-255).

Escolhendo o Threshold Ideal

A escolha do threshold é crucial e depende da imagem:

• Threshold muito baixo: Objetos podem se fundir com o fundo
• Threshold muito alto: Partes dos objetos podem ser perdidas
• Threshold 128: Um bom ponto de partida, mas não ideal para todas as imagens

Em cenários futuros, exploraremos métodos automáticos como o algoritmo de Otsu, que calcula o threshold ótimo para cada imagem.

Filtragem por Tamanho

Uma melhoria importante implementada foi a filtragem por tamanho mínimo de ilha. Na prática, após a binarização, pequenos ruídos e artefatos podem aparecer como “ilhas” de poucos pixels. Para eliminar esses falsos positivos, modificamos a função conquista para retornar o tamanho da ilha:

int conquista (int **matrix, int i, int j, int nrows, int ncols)
{
    int tam = 0;
    Queue *q = create(nrows*ncols+1); 
    enqueue (q, (point){i,j});
    matrix[i][j] = 0; 
    
    while (!empty(q))
    {
        point p = dequeue (q);
        int x, y;
        for (x = -1; x <= +1; x++)
        {
            for (y = -1; y <= +1; y++)
            {
                int sx = p.x + x;
                int sy = p.y + y;	    
                if (inside(sx, sy, nrows, ncols) && matrix[sx][sy] == 1)
                {
                    tam++;
                    enqueue (q, (point){sx,sy});
                    matrix[sx][sy] = 0;
                }  
            }	
        }  
    }
    destroy (q); 
    return tam;
}

E na função de contagem, filtramos ilhas pequenas:

int count_islands (int **matrix, int nrows, int ncols)
{
    int i, j, sum = 0;	
    for (i = 0; i < nrows; i++)
    {
        for (j = 0; j < ncols; j++)
        {
            if (matrix[i][j] == 1)
            {
                int tamanho_ilha = conquista(matrix, i, j, nrows, ncols);
                if(tamanho_ilha > 120)  // Filtra ruídos menores que 120 pixels
                    sum++;
            }	      
        }	     
    }
    return sum;
}

O valor de 120 pixels é um exemplo. Na prática, esse threshold de tamanho deve ser ajustado conforme as características da imagem e dos objetos que você deseja contar.

Leitura de Imagens PNG

A biblioteca libpng fornece funções completas para leitura de arquivos PNG. O código cuida de vários detalhes importantes:

• Validação do formato PNG através da assinatura do arquivo
• Conversão automática de diferentes formatos de cor para RGB
• Normalização de profundidade de bits (16 bits → 8 bits)
• Tratamento de transparência
• Conversão de paleta de cores para RGB

Pipeline Completo

O fluxo completo do processamento é:

1. Leitura: Carregar imagem PNG colorida
2. Conversão: RGB → Escala de cinza (aplicando os pesos corretos)
3. Binarização: Escala de cinza → Binário (usando threshold)
4. Contagem: Aplicar BFS com filtro de tamanho mínimo
5. Resultado: Número de objetos detectados

Vantagens e Limitações

Vantagens desta abordagem:

• Funciona com imagens reais em formato PNG
• Filtragem de ruído através do tamanho mínimo
• Código relativamente simples e eficiente

Limitações:

• Threshold fixo pode não funcionar bem para todas as imagens
• Objetos que se tocam ainda são contados como um único objeto
• Iluminação não uniforme pode afetar a binarização
• Requer ajuste manual dos parâmetros (threshold e tamanho mínimo)

Próximos Passos

No próximo cenário, exploraremos técnicas mais avançadas:

• Threshold adaptativo: Métodos como Otsu para calcular automaticamente o melhor threshold
• Separação de objetos: Técnicas para lidar com objetos que se tocam ou sobrepõem
• Morfologia matemática: Operações de erosão e dilatação para melhorar a segmentação

Exemplo de Uso

int main() {
    image *img = read_png("ata.png");
    if (!img) return 1;

    printf("Imagem carregada: %dx%d pixels\n", img->w, img->h);
    
    // Binariza com threshold 128
    int **binary = convert_to_binary(img, 128);

    // Conta objetos maiores que 120 pixels
    printf("Número de ilhas: %d\n", count_islands(binary, img->h, img->w));

    free_binary(binary, img->h);
    free_image(img);
    return 0;
}

Complexidade

A complexidade permanece O(n × m) para a contagem, mas agora temos etapas adicionais:

• Conversão para escala de cinza: O(n × m)
• Binarização: O(n × m)
• Contagem com BFS: O(n × m)

A complexidade total continua sendo O(n × m), pois todas as etapas são lineares no número de pixels.

Resultados

Imagem de exemplo.

Resultado : Número de ilhas: 3