Projteto_1_Estrutura_de_Dados

Projeto para a disciplina de Estrutura de dados INE5408

Objetivo

Este projeto consiste na utilização de estruturas lineares, vistas até o momento no curso, e aplicação de conceitos de pilha e/ou fila para o processamento de arquivos XML contendo imagens binárias. A implementação deverá resolver dois problemas (listados a seguir), e os resultados deverão ser formatados em saída padrão de tela de modo que possam ser automaticamente avaliados no VPL.

• Entradas:
  • datasets.zip
• Saídas textuais esperadas:
  • t1-saidas.pdf
• Dica:
  • utilize "avaliar" (e não "executar") para que as entradas sejam automaticamente carregadas

Materiais

• De modo a exemplificar uma entrada para o seu programa, segue o arquivo XML utilizado no primeiro teste:

  • dataset01.xml

• dataset02.xml, dataset03.xml, dataset04.xml, dataset05.xml, dataset06.xml

• dicas sobre leitura e escrita com arquivos em C++

  • http://www.cplusplus.com/doc/tutorial/files/

para a criação e concatenação de palavras/caracteres, sugere-se o uso da classe string:

http://www.cplusplus.com/reference/string/string/

Primeiro problema: validação de arquivo XML

Para esta parte, pede-se exclusivamente a verificação de aninhamento e fechamento das marcações (tags) no arquivo XML (qualquer outra fonte de erro pode ser ignorada). Um identificador (por exemplo: img) constitui uma marcação entre os caracteres < e >, podendo ser de abertura (por exemplo: ) ou de fechamento com uma / antes do identificador (por exemplo: ). Como apresentando em sala de aula, o algoritmo para resolver este problema é baseado em pilha (LIFO):

• Ao encontrar uma marcação de abertura, empilha o identificador
• Ao encontrar uma marcação de fechamento, verifica se o topo da pilha tem o mesmo identificador e desempilha. Aqui duas situações de erro podem ocorrer:
  • Ao consultar o topo, o identificador é diferente (ou seja, uma marcação aberta deveria ter sido fechada antes)
  • Ao consultar o topo, a pilha encontra-se vazia (ou seja, uma marcação é fechada sem que tenha sido aberta antes)
• Ao finalizar a análise (parser) do arquivo, é necessário que a pilha esteja vazia. Caso não esteja, mais uma situação de erro ocorre, ou seja, há marcação sem fechamento

Segundo problema: contagem de componentes conexos em imagens binárias representadas em arquivo XML

Cada XML, contém imagens binárias, com altura e largura, definidas respectivamente pelas marcações e , e sequência dos pixels (com valores binários, de intensidade 0 para preto ou 1 para branco), em modo texto (embora fosse melhor gravar 1 byte a cada 8 bits, optou-se pelo modo texto por simplicidade), na marcação . Para cada uma dessas imagens, pretende-se calcular o número de componentes conexos usando vizinhança-4. Para isso, seguem algumas definições importantes:

• A vizinhança-4 de um pixel na linha x e coluna y, ou seja, na coordenada (x,y), é um conjunto de pixels adjacentes nas coordenadas:

  • (x-1, y)
  • (x+1, y)
  • (x, y-1)
  • (x, y+1)

• Um caminho entre um um pixel p1 e outro pn é em um sequência de pixels distintos <p1,p2,...,pn>, de modo que pi é vizinho-4 de pi+1., sendo i=1,2,...,n-1

• Um pixel p é conexo a um pixel q se existir um caminho de p a q (no contexto deste trabalho, só há interesse em pixels com intensidade 1, ou seja, brancos)

• Um componente conexo é um conjunto maximal (não há outro maior que o contenha) C de pixels, no qual quaisquer dois pixels selecionados deste conjunto C são conexos

• Para a determinação da quantidade de componentes conexos, antes é necessário atribuir um rótulo inteiro e crescente (1, 2, ...) para cada pixel de cada componente conexo. Conforme apresentado em aula, segue o algoritmo de rotulação (labeling) usando uma fila (FIFO):

• Inicializar rótulo com 1

• Criar uma matriz R de zeros com o mesmo tamanho da matriz de entrada E lida

• Varrer a matriz de entrada E

  • Assim que encontrar o primeiro pixel de intensidade 1 ainda não visitado (igual a 0 na mesma coordenada em R)
    • inserir (x,y) na fila
      • na coordenada (x,y) da imagem R, atribuir o rótulo atual
  • Enquanto a fila não estiver vazia
    • (x,y) ← remover da fila *inserir na fila as coordenadas dos quatro vizinhos que estejam dentro do domínio da imagem (não pode ter coordenada negativa ou superar o número de linhas ou de colunas), com intensidade 1 (em E) e ainda não tenha sido visitado (igual a 0 em R)
    • na coordenada de cada vizinho selecionado, na imagem R, atribuir o rótulo atual
  • incrementar o rótulo

O conteúdo final da matriz R corresponde ao resultado da rotulação. A quantidade de componentes conexos, que é a resposta do segundo problema, é igual ao último e maior rótulo atribuído.