/*************************************************************************
 *     MAC447 - Análise e Reconhecimento de Formas: Teoria e Prática     *
 *                                                                       *
 * Daniel André Vaquero                                                  *
 *                                                                       *
 * Exercício 2 - Rotulação de componentes conexas em imagens binárias    *
 * Prof.: Roberto Marcondes Cesar Junior                                 *
 * BCC / IME - USP                                                       *
 * 2o. semestre / 2003                                                   *
 *************************************************************************/

/* Arquivo: rotulacao.c
 *
 * Este programa recebe como entrada uma imagem binária em formato PBM ASCII
 * e o critério de vizinhança entre os pixels (4-vizinhança e 8-vizinhança)
 * e faz a rotulação das componentes conexas da imagem de acordo com a
 * vizinhança fornecida. É gerada uma imagem de saída em níveis de cinza no
 * formato PGM ASCII, onde cada componente conexa da imagem de entrada aparece
 * com um nível de cinza diferente.
 *
 * Para compilar o programa:
 *
 * gcc rotulacao.c -o rotulacao
 *
 * Para executar:
 *
 * ./rotulacao arquivo_de_entrada arquivo_de_saída vizinhança
 *
 * onde arquivo_de_entrada é o nome do arquivo de entrada contendo uma imagem
 * binária no formato PBM ASCII, arquivo_de_saída é o arquivo onde será gravada
 * a imagem de saída em formato PGM ASCII e vizinhança deve ter como valor
 * 4 ou 8, para que o programa faça a rotulação de acordo com a 4-vizinhança
 * ou 8-vizinhança, respectivamente.
 *
 */

#include <stdio.h>
#include <stdlib.h>

#define PILHA_VAZIA (topo == -1)

/* Estrutura representando a posição de um pixel na imagem */
typedef struct {
  int lin;
  int col;
} posicao;

/* Protótipos */
void libera_memoria();
void erro(char *msg, int error_code);
void le_arquivo_pbm_ascii(char *nome_arq);
void grava_arquivo_pgm_ascii(char *nome_arq, int nivel_max);
void empilha(int i, int j);
posicao desempilha();
void visita(int lin, int col);
void rotula4(int lin, int col);
void rotula8(int lin, int col);

/* Variáveis globais */
short int **imagem = NULL; /* Matriz representando a imagem */
int n_lin, n_col;          /* Número de linhas e colunas da imagem */
posicao *pilha = NULL;     /* Pilha usada no algoritmo de rotulação */
int topo = -1;             /* Topo da pilha */
int tamanho = 256;         /* Tamanho da pilha (dobramos quando necessário) */
int rotulo = 1;            /* Próximo rótulo a ser atribuído a uma c. conexa */
char buf[256];             /* Buffer de caracteres */

/* libera_memoria
 *
 * Libera a memória alocada dinamicamente pelo programa.
 *
 */
void libera_memoria() {

  int i;

  if (imagem != NULL) {
    for (i = 0; i < n_lin + 2; i++) {
      if (imagem[i] != NULL) free(imagem[i]);
      else break;
    }
    free(imagem);
  } 
  
  if (pilha != NULL) free(pilha);

}

/* erro
 *
 * Imprime uma mensagem de erro contida em msg e termina o programa com valor
 * de retorno error_code.
 *
 */
void erro(char *msg, int error_code) {
  fprintf(stderr, "Erro: %s\n", msg);
  libera_memoria();
  exit(error_code);
}

/* le_arquivo_pbm_ascii
 *
 * Lê um arquivo de nome apontado por nome_arq no formato PBM ASCII e o
 * armazena na matriz imagem, colocando uma moldura de zeros em torno da
 * imagem (memória é alocada para a matriz de acordo com o tamanho da imagem).
 *
 */
void le_arquivo_pbm_ascii(char *nome_arq) {

  FILE *arq_pbm;     /* arquivo de entrada */
  int i, j;

  arq_pbm = fopen(nome_arq, "r");
  if (arq_pbm == NULL) {
    sprintf(buf, "não foi possível abrir o arquivo %s para leitura", nome_arq);
    erro(buf, 5);
  }

  if (fgetc(arq_pbm) != 'P' || fgetc(arq_pbm) != '1' || fgetc(arq_pbm) != '\n')
    erro("sintaxe inválida no arquivo de entrada", 2);

  if (fscanf(arq_pbm, "%d %d", &n_col, &n_lin) != 2)
    erro("sintaxe inválida no arquivo de entrada", 2);

  if (n_col < 0 || n_lin < 0)
    erro("número de linhas ou colunas inválido", 2);

  /* Alocação de memória */
  imagem = calloc(n_lin + 2, sizeof(short int *));
  if (imagem == NULL)
    erro("alocação de memória", 3);
  for (i = 0; i < n_lin + 2; i++) {
    imagem[i] = calloc(n_col + 2, sizeof(short int));
    if (imagem[i] == NULL)
      erro("alocação de memória", 3);
  }
  
  /* Leitura da matriz de pixels da imagem */
  for (i = 1; i <= n_lin; i++)
    for (j = 1; j <= n_col; j++) {
      int ret = fscanf(arq_pbm, "%hd", &imagem[i][j]);
      if (ret == 0 || ret == EOF)
	erro("sintaxe inválida no arquivo de entrada", 2);
      if (imagem[i][j] != 0 && imagem[i][j] != 1)
	erro("os pixels devem ter valores 0 ou 1", 2);
    }

  fclose(arq_pbm);
  
}

/* grava_arquivo_pgm_ascii
 *
 * Grava a imagem representada pela matriz imagem no arquivo cujo nome está
 * em nome_arq, em formato PGM ASCII. A imagem possui nivel_max + 1 níveis de
 * cinza.
 *
 */
void grava_arquivo_pgm_ascii(char *nome_arq, int nivel_max) {

  FILE *arq_pgm;             /* arquivo de saída */
  int i, j;

  arq_pgm = fopen(nome_arq, "w");
  if (arq_pgm == NULL) {
    sprintf(buf, "não foi possível abrir o arquivo %s para escrita", nome_arq);
    erro(buf, 5);
  }

  fprintf(arq_pgm, "P2\n%d %d %d\n", n_col, n_lin, nivel_max);
  
  for (i = 1; i <= n_lin; i++) {
    for (j = 1; j <= n_col; j++)
      fprintf(arq_pgm, "%d ", imagem[i][j]);
    fprintf(arq_pgm, "\n");
  }
  
  fclose(arq_pgm);

}

/* empilha
 *
 * Dados dois valores i e j, empilha a posição (i, j) na pilha. Dobra o tamanho
 * da pilha se necessário.
 *
 */
void empilha(int i, int j) {

  posicao *tmp;
  int k;

  /* Dobra o tamanho da pilha se necessário */
  if (topo == tamanho - 1) {
    tamanho *= 2;
    tmp = malloc(tamanho * sizeof(posicao));
    if (tmp == NULL)
      erro("alocação de memória", 3);
    for (k = 0; k <= topo; k++)
      tmp[k] = pilha[k];
    free(pilha);
    pilha = tmp;
  }

  topo++;
  pilha[topo].lin = i;
  pilha[topo].col = j;

}

/* desempilha
 *
 * Desempilha a posição presente no topo da pilha e a devolve. 
 *
 */
posicao desempilha() {

  posicao p;

  p.lin = pilha[topo].lin;
  p.col = pilha[topo].col;
  topo--;

  return p;

}

/* visita
 *
 * Dados uma linha e uma coluna da imagem, verifica se o pixel presente nessa
 * posição pertence à componente conexa que estamos rotulando. Se sim, empilha
 * a posição para processamento posterior.
 *
 */
void visita(int lin, int col) {

  if (imagem[lin][col] == -1)
    empilha(lin, col);

}

/* rotula4
 *
 * Dados uma linha e uma coluna da imagem, se existir um pixel de uma
 * componente conexa ainda não rotulada nesta posição da imagem rotula esta
 * componente de acordo com a 4-vizinhança.
 *
 */
void rotula4(int lin, int col) {

  posicao tmp;
    
  if (imagem[lin][col] == -1) {

    imagem[lin][col] = rotulo;

    /* Verifica os vizinhos */
    visita(lin - 1, col);
    visita(lin, col + 1);
    visita(lin + 1, col);
    visita(lin, col - 1);
    
    /* Rotula os pixels vizinhos até que todos tenham sido processados */
    while (!PILHA_VAZIA) {

      tmp = desempilha();
      imagem[tmp.lin][tmp.col] = rotulo;

      visita(tmp.lin - 1, tmp.col);
      visita(tmp.lin, tmp.col + 1);
      visita(tmp.lin + 1, tmp.col);
      visita(tmp.lin, tmp.col - 1);
      
    }

    rotulo++;

  }

}

/* rotula8
 *
 * Dados uma linha e uma coluna da imagem, se existir um pixel de uma
 * componente conexa ainda não rotulada nesta posição da imagem rotula esta
 * componente de acordo com a 8-vizinhança.
 *
 */
void rotula8(int lin, int col) {

  posicao tmp;
    
  if (imagem[lin][col] == -1) {

    imagem[lin][col] = rotulo;

    /* Verifica os vizinhos */
    visita(lin - 1, col - 1);
    visita(lin, col - 1);
    visita(lin + 1, col - 1);
    visita(lin - 1, col);
    visita(lin + 1, col);
    visita(lin - 1, col + 1);
    visita(lin, col + 1);
    visita(lin + 1, col + 1);

    /* Rotula os pixels vizinhos até que todos tenham sido processados */    
    while (!PILHA_VAZIA) {

      tmp = desempilha();
      imagem[tmp.lin][tmp.col] = rotulo;

      visita(tmp.lin - 1, tmp.col - 1);
      visita(tmp.lin, tmp.col - 1);
      visita(tmp.lin + 1, tmp.col - 1);
      visita(tmp.lin - 1, tmp.col);
      visita(tmp.lin + 1, tmp.col);
      visita(tmp.lin - 1, tmp.col + 1);
      visita(tmp.lin, tmp.col + 1);
      visita(tmp.lin + 1, tmp.col + 1);

    }

    rotulo++;

  }

}

int main(int argc, char *argv[]) {

  int i, j;
  int vizinhanca;    /* Vizinhança a ser usada na rotulação */

  if (argc != 4) {
    sprintf(buf, "uso: %s arq_entrada.pbm arq_saida.pgm vizinhanca", argv[0]);
    erro(buf, 17);
  }

  pilha = malloc(tamanho * sizeof(posicao));
  if (pilha == NULL)
    erro("alocação de memória", 3);
  
  le_arquivo_pbm_ascii(argv[1]);

  /* Faz com que os pixels de valor 1 na imagem recebam o valor -1, assim é
     possível usar a mesma matriz para fazer a rotulação começando com o 
     rótulo 1 */
  for (i = 1; i <= n_lin; i++)
    for (j = 1; j <= n_col; j++)
      imagem[i][j] *= -1;

  vizinhanca = atoi(argv[3]);
  
  if (vizinhanca == 4) {            /* 4-vizinhança */
    for (i = 1; i <= n_lin; i++)
      for (j = 1; j <= n_col; j++)
	rotula4(i, j);
  }
  else if (vizinhanca == 8) {       /* 8-vizinhança */
    for (i = 1; i <= n_lin; i++)
      for (j = 1; j <= n_col; j++)
	rotula8(i, j);
  }
  else
    erro("A vizinhança deve ser 4 ou 8", 42);

  grava_arquivo_pgm_ascii(argv[2], rotulo - 1);
  libera_memoria();

  return 0;

}