Universidade Federal do Rio de Janeiro

Escola Politécnica

Departamento de Eletrônica e de Computação

Processamento Digital de Imagens aplicado ao Auxílio à Programação do Sistema de Controle de Avarias (SCAV) da

Marinha do Brasil (MB)

Autor:

_________________________________________________ Fábio Pereira Azevedo Teixeira

Orientador:

_________________________________________________ Heraldo Luis Silveira de Almeida, D.Sc.

Examinador:

_________________________________________________ Flávio Luis de Mello, D.Sc.

Examinador:

_________________________________________________ Aloysio de Castro Pinto Pedroza, Dr.

DEL

Agosto de 2014

ii

UNIVERSIDADE FEDERAL DO RIO DE JANEIRO

Escola Politécnica – Departamento de Eletrônica e de Computação

Centro de Tecnologia, bloco H, sala H-217, Cidade Universitária

Rio de Janeiro – RJ CEP 21949-900

Este exemplar é de propriedade da Universidade Federal do Rio de Janeiro, que

poderá incluí-lo em base de dados, armazenar em computador, microfilmar ou adotar

qualquer forma de arquivamento.

É permitida a menção, reprodução parcial ou integral e a transmissão entre

bibliotecas deste trabalho, sem modificação de seu texto, em qualquer meio que esteja

ou venha a ser fixado, para pesquisa acadêmica, comentários e citações, desde que sem

finalidade comercial e que seja feita a referência bibliográfica completa.

Os conceitos expressos neste trabalho são de responsabilidade do(s) autor(es) e

do(s) orientador(es).

iii

DEDICATÓRIA

Dedico este trabalho ao meu filho(a) ainda não nascido(a) e a todas as pessoas

que contribuíram para sua confecção e que me ajudaram a concluir o curso de

Engenharia Eletrônica e Computação, entre elas em especial, aos meus pais Mônica e

Paulo, e à minha namorada Analice.

iv

AGRADECIMENTO

Agradeço a todos aqueles que contribuíram de forma direta ou indireta para a

minha formação nesta Universidade e à confecção desse trabalho.

Ao professor Heraldo Luis Silveira de Almeida por sua confiança e orientação

segura no decorrer desse projeto.

Ao Instituto de Pesquisas da Marinha - Grupo de Sistemas Digitais pela

oportunidade de contribuir no aprimoramento do processo de desenvolvimento do

Sistema de Controle de Avarias dos Meios Navais da Marinha do Brasil.

Por fim, ao povo brasileiro que contribuiu de forma significativa à minha

formação e estada nesta Universidade. Este projeto é uma pequena forma de retribuir o

investimento e confiança em mim depositados.

v

RESUMO

Este Trabalho de Conclusão de Curso documenta o desenvolvimento de um

Software de Auxílio à Programação dos Sistemas de Controle de Avarias da Marinha do

Brasil. Introduz algumas técnicas inovadoras de processamento de imagens e é capaz de

automatizar tarefas repetitivas e laboriosas relativas ao traçado de objetos visuais em

tela, antes atribuídas a um programador. O software desenvolvido reduz o tempo

despendido pelo profissional alocado para a realização dessa atividade do projeto, em

mais de 90 por cento.

Palavras-Chave: desenvolvimento de software, redução de tempo de atividade

de projeto, automatização de tarefas, processamento de imagens, segmentação

de imagem, thresholding, cobertura de polígono retilíneo com número mínimo

de retângulos, traço de caminho sobre perímetro fechado, ajuste de polígono a

um perímetro fechado.

vi

ABSTRACT

This final paper documents the development of a Programming Aid Software for

the Brazilian Navy's Damage Control System. It presents some innovative image

processing techniques and is capable of automating repetitive and laborious tasks, that

are related to the layout of visual objects over the System's main interface. The

proposed software reduces the amount of time spent by the programmer in that activity,

by over 90 percent.

Key-Words: software development, project activity time reduction, task

automation, image processing, image segmentation, thresholding, covering of

rectilinear polygon with minimum amount of rectangles, path tracing over

closed perimeter, polygon fit over closed perimeter.

vii

SIGLAS

BCB – Borland C++ Builder

BD – Banco de Dados

HDTV – High-definition Television (Formato de Vídeo de Televisores, de Alta

Definição)

IDE – Integrated Development Environment (Ambiente de Desenvolvimento Integrado)

IHM – Interface Homem-Máquina

MB – Marinha do Brasil

PhAB – Photon Application Builder (IDE do QNX)

QNX – Sistema Operacional, "UNIX like", de tempo real da empresa QNX Software

Systems

RTOS – Real Time Operating System (Sistema Operacional de Tempo Real)

RGB – Modelo de representação de cores (Red, Green, Blue)

SCAV – Sistema de Controle de Avarias

SGBD – Sistema Gerenciador de Bancos de Dados

SO – Sistema Operacional

UFRJ – Universidade Federal do Rio de Janeiro

viii

Sumário

1 Introdução 1

1.1 - Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 - Delimitação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.3 - Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.4 - Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.5 - Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.6 - Descrição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Panorama do Sistema 5

2.1 - Sistema de Controle de Avarias . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 - Sistema Operacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 - Desenvolvimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.4 - Requisitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Engenharia Reversa 14

3.1 - Arquivo Fonte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

3.2 - Imagens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.3 - Polígonos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4 - Retângulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

ix

4 Processamento de Imagem 20

4.1 - Segmentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2 - Escala de Cinza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4.3 - Thresholding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4.4 - Método de Otsu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.5 - Conclusões sobre Segmentação . . . . . . . . . . . . . . . . . . . . . . . . . 25

5 Processamento dos Compartimentos 26

5.1 - Considerações Iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

5.2 - Área Interna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

5.3 - Retângulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

5.4 - Perímetro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.5 - Caminho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.6 - Polígonos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6 Software 54

7 Conclusões 60

Bibliografia 61

x

Lista de Figuras

2.3.1 – Compartimento de um navio, no SCAV, no ambiente PhAB. 7

2.3.2 – Compartimento marcado com a avaria Incêndio. 7

2.3.3 – Polígono mapeado no compartimento em tempo de projeto, no PhAB. 8

2.3.4 – Polígonos mapeados, em conflito quanto à resposta a eventos do mouse. 9

2.3.5 – Proa de um navio mapeada em um polígono. 10

2.3.6 – Retângulos mapeados em um compartimentos simples. 11

2.3.7 – Retângulos mapeados em um dos compartimentos mais complexos. 11

3.1.1 – Trecho exemplo da natureza “mista” do arquivo fonte (*.wgtw). 14

3.2.1 – Imagens de teste utilizadas (cada cor preenche um pixel). 16

3.2.2 – Codificação de linha de uma imagem, com pixels de preenchimento. 17

3.3.1 – Parte do código fonte da descrição de um objeto polígono. 18

4.1.1 – Exemplo descaracterizado da planta baixa de um navio. 20

4.1.2 – Exemplo dos traços em gradiente de cor. 20

4.4.1 – Imagem exemplo do Método de Otsu, e seu histograma. 23

5.1.1 – Exemplos de regiões fechadas da imagem que não configuram compartimentos.

26

5.1.2 – Esboço de interface para o software. 27

5.2.1 – Exemplo de execução do algoritmo Scanline Flooding sobre um compartimento real.

28

5.3.1 – Retângulos sem otimização. 30

5.3.2 – Preenchimento por retângulos com otimização. 31

5.3.3 – Preenchimento por retângulos com erro permitido. 32

5.3.4 – O sentido de preenchimento que produz os melhores resultados pode variar de acordo com cada valor de erro permitido.

33

5.3.5 – Exemplo de erro permitido grande demais. 34

5.4.1 – Processo de Extração de Fronteira. 35

xi

5.4.2 – Perímetro da área interna ao compartimento, em vermelho. 36

5.4.3 – Remoção de rota sem saída. 37

5.4.4 – Matrizes de detecção de "cúspides". 38

5.4.5 – Resultado anterior da redução de rota sem saída, corrigido. 38

5.4.6 – Exemplo de compartimento com furo. 39

5.4.7 – Exemplo de compartimento com outro inscrito, muito próximo à antepara.

40

5.5.1 – Exemplo do objetivo do cálculo de caminho por sobre um perímetro externo

41

5.5.2 – Ordem de busca por pontos vizinhos. 42

5.5.3 – Exemplos de traçados válidos e inválidos. 43

5.5.4 – Trecho de perímetro, exemplo do algoritmo melhorado. 44

5.5.5 – Máquina de estados de tomada de decisão para escolha do caminho sobre o perímetro.

45

5.5.6 – Exemplo do conceito de uma concavidade degenerada. 46

5.5.7 – Primeiro passo de inserção de perímetro interno. 47

5.5.8 – Segundo passo de inserção de perímetro interno. 47

5.6.1 – Exemplo do traçado de linha pelo algoritmo ingênuo. 49

5.6.2 – Reta de exemplo do algoritmo de Bresenham no segundo octante. 50

5.6.3 – Pequena reta de exemplo, no segundo octante, e o passo a passo da execução do algoritmo.

51

5.6.4 – Exemplo de execução do algoritmo de ajuste de polígonos. 52

5.6.5 – O compartimento de exemplo com um furo, possui 58 pontos de perímetro.

53

6.1 – Janela de abertura de projeto, no SAP CAV. 54

6.2 – Trechos de exemplo de arquivos de saída do software. 55

6.3 – Janela de carga de imagens do sistema. 56

6.4 – Janela da vista geral e demais reparos do navio, carregadas. 57

6.5 – Compartimentos filtrados e um deles selecionado. 57

xii

6.6 – Arrastando ícone do compartimento para sua posição correta. 58

6.7 – Compartimento calculado. 58

xiii

Lista de Tabelas

4.4.1 – Resultados parciais do algoritmo de Otsu . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.4.2 – Comparação de resultados entre formas de cálculo . . . . . . . . . . . . . . . . . . 25

1

Capítulo 1

Introdução

1.1 – Tema

Os temas do trabalho são o estudo e a subseqüente aplicação de técnicas de

processamento digital de imagens, voltados ao auxílio à programação.

A hipótese inicial é de que seja possível desenvolver um software capaz de

executar todas as etapas necessárias à delimitação e programação em arquivo fonte dos

atributos de um compartimento fechado em uma planta baixa do SCAV, de forma quase

automática, necessitando apenas de um ponto de partida dentro do compartimento em

questão, fornecido pelo usuário.

1.2 – Delimitação

Apesar das técnicas de processamento alvo serem aplicáveis em quaisquer

imagens de plantas baixas similares (que possuam regiões fechadas e diferença de

luminância suficiente entre as regiões de fundo e de fronteira), o projeto está voltado

somente para imagens de plantas baixas dos SCAV da MB.

1.3 – Justificativa

Durante a fase de desenvolvimento do SCAV de um novo navio, todos os

compartimentos na planta baixa deste devem ter seus perímetros internos mapeados em

polígonos e suas áreas internas mapeadas em retângulos, na forma mais simples e

acurada possível, para que a interface visual de acompanhamento de avarias possa

funcionar como projetada. No entanto, a execução manual dessa tarefa demanda cerca

de 176 horas de trabalho de um programador especializado, para um navio de médio

porte.

2

Ao ser familiarizado com o problema, o aluno propôs aos seus superiores que

seria possível desenvolver um software capaz de agilizar a execução desta parte do

projeto de cada SCAV, utilizando processamento digital de imagens para analisar a

planta baixa do navio e realizar automaticamente o mapeamento e preenchimento dos

compartimentos, necessitando apenas de um ponto de origem dentro de cada um deles, a

serem fornecidos pelo programador do SCAV.

Atingindo-se todos os objetivos propostos, obter-se-á um software inteiramente

operacional, estimado ser capaz de realizar em menos de 8 horas de trabalho do mesmo

programador, a mesma tarefa. Uma redução de mais de 95% nas horas trabalhadas e de

aproximadamente um mês no cronograma do projeto.

1.4 – Objetivos

O objetivo final é desenvolver um aplicativo, de interface gráfica intuitiva e

amigável, que seja capaz de analisar um arquivo de código fonte do SCAV e, junto com

o banco de dados do mesmo sistema, fornecer visualmente ao usuário todos os

compartimentos cadastrados do navio. Uma vez listados, os compartimentos estarão

prontos para serem posicionados sobre a planta baixa. A partir deste posicionamento, o

software aplicará, de forma automática, técnicas de processamento de imagens sobre a

planta e escreverá sobre o arquivo fonte original todo código fonte necessário para

descrever os compartimentos.

1.5 – Metodologia

Para alcançar o objetivo supracitado, o software deverá ser capaz de

disponibilizar uma listagem dos compartimentos do navio em questão, para a

determinação da posição de cada um na planta baixa. Para tanto, será necessário

consultar o Banco de Dados (BD) do projeto SCAV do navio, e dele obter as descrições

e códigos de cada compartimento cadastrado. Este BD foi criado utilizando-se o

Sistema Gerenciador de Bancos de Dados (SGBD) "SQLite" [1] (embarcado na

aplicação). Será utilizada, por comodidade de integração, a própria biblioteca em

C/C++, disponível no site deste SGBD.

3

Em seguida, a imagem da planta baixa deverá, se possível, ser lida diretamente

do arquivo fonte do SCAV onde também está armazenada (evitando a necessidade de

mais um arquivo fonte de dados, nesse caso, um arquivo de imagem), e no qual os

códigos que descrevem os polígonos e retângulos que representam o perímetro e a área

interna dos compartimentos, respectivamente, serão escritos posteriormente. Faz-se

necessário, portanto, o estudo da formatação desse arquivo fonte, que é gerado

automaticamente por uma IDE no Sistema Operacional (SO) QNX [2], para determinar

as representações dos parâmetros de imagens, polígonos e retângulos.

Com a imagem da planta carregada em memória, seja a partir do arquivo fonte

do SCAV ou de um arquivo de imagem externo, é preciso classificar seu conteúdo em

duas entidades: fundo e fronteiras. A imagem original é colorida e deseja-se então uma

bicolor, em preto e branco por exemplo. Portanto, o primeiro passo é convertê-la para

uma escala de cinza, baseada na luminância de cada cor. Os pesos dados às

componentes RGB para esse cálculo variam de acordo com a modelagem da percepção

humana de cada uma das cores primárias. Arbitrar-se-á então o uso do mesmo modelo

de luminância do sistema HDTV.

Feito isso, as cores do fundo e das fronteiras ainda não são sólidas (ainda há um

gradiente de cinza). É necessário portanto processar novamente a imagem para

convertê-la em preto e branco.

O próximo passo será oferecer ao usuário, através de interface visual amigável,

uma maneira de posicionar um token representativo de cada compartimento, dentro do

mesmo, sobre a planta baixa carregada, para servir de ponto de partida para os

algoritmos seguintes.

Com um ponto de origem do compartimento e cores de fundo e de fronteira

sólidas, aplica-se o algoritmo que determinará a área interna do compartimento, que

depois será preenchida pelo menor número possível e/ou aceitável de retângulos por

outra sub-rotina.

O perímetro deste compartimento pode ser obtido a partir de sua área interna já

calculada. Ele será então processado de forma a obter-se o polígono mais simples que

circunscreva a área interna calculada.

Por fim, os polígonos e retângulos encontrados serão inseridos no arquivo de

código fonte mencionado anteriormente, finalizando o processo e deixando dito arquivo

pronto para ser compilado novamente no SO QNX, sem a "percepção" da IDE deste de

que os objetos não foram criados manualmente.

4

1.6 – Descrição

O Capítulo 2 tratará do histórico por trás do projeto, as dificuldades relacionadas

à programação do SCAV e os requisitos da solução desejada.

O Capítulo 3 seguirá elaborando a leitura do arquivo fonte do SCAV gerado

durante a programação na IDE do SO QNX, portanto, do esforço de engenharia reversa

para determinar o formato de armazenamento de imagens, de polígonos e de retângulos

no arquivo.

O Capítulo 4 apresentará os algoritmos utilizados no processamento de cores da

imagem. Nele estão contidos a conversão de uma imagem em cores para uma em escala

de cinza (valores de luminância, tendo como base as definições do sistema HDTV) e a

implementação de um filtro de limiar de luminância (Thresholding) utilizando o Método

de Otsu, para converter a imagem em preto e branco.

O Capítulo 5 discorrerá sobre as técnicas de processamento aplicadas na

determinação da área interna ao compartimento, no preenchimento eficiente desta por

retângulos, no cálculo do perímetro dela e na obtenção a partir deste do polígono mais

simples que circunscreve exatamente o compartimento. Para isso são aplicados,

respectivamente, o algoritmo de preenchimento Flood Fill em sua forma clássica, uma

sub-rotina própria para o preenchimento por retângulos, um Flood Fill modificado

juntamente com uma segunda sub-rotina própria para o determinar o perímetro do

compartimento, e por fim, para a obtenção do polígono uma terceira sub-rotina própria

que se utiliza do algoritmo de linhas de Bresenham.

No Capítulo 6 serão apresentados os resultados obtidos.

Por fim, o Capítulo 7 tecerá as conclusões.

5

Capítulo 2

Panorama do Sistema

2.1 – Sistema de Controle de Avarias

Objeto de interesse deste projeto, o SCAV é um sistema complexo, composto de

computadores, sensores, atuadores e software especializado.

O Sistema monitora remotamente diversos sensores, dos tipos fumaça,

temperatura, alagamento, fechamento de portas estanques, disparo de borrifo de água,

disparo de ampolas de CO2 e outros, distribuídos por diversas áreas e compartimentos.

Com a coleta dessas informações, o SCAV permite o acompanhamento visual de

quaisquer avarias vigentes, através de uma representação virtual da planta baixa do

navio, em qualquer um de seus diversos consoles.

Somam-se às suas capacidades a inserção de avarias não sensoriadas, tais como

avarias estruturais, a habilidade de calcular a melhor rota de evacuação de feridos em

incêndios levando em consideração a disponibilidade de acesso a compartimentos e

corredores. Além disso, está apto a sugerir a abertura e/ou fechamento de portas

estanques e o acionamento de determinados ventiladores e/ou extratores visando

otimizar a remoção de fumaça, e é capaz de propor manobras de esgotamento e/ou

alagamento de tanques ou porões baseado no cálculo de reserva de flutuabilidade do

navio, de forma a garantir sua estabilidade em caso de alagamentos por dano no casco.

O Sistema foi desenvolvido pelo Grupo de Sistema Digitais do Instituto de

Pesquisas da Marinha do Brasil.

2.2 – Sistema Operacional

O software do SCAV foi implementado sobre o sistema operacional QNX®

Neutrino®, um RTOS [3] (SO de tempo real) “UNIX like". Ser de "tempo real" implica

em ser capaz de garantir o processamento de threads de alta prioridade sem atraso,

mesmo com o SO sob alta carga de processamento.

6

O QNX possui um micro-kernel, e sua arquitetura propõe a execução de todos

os drivers, aplicações e até do sistema de arquivos, da segurança de um espaço de

usuário protegido em memória, fora do kernel. Então, no caso de falha de virtualmente

qualquer componente de software, este pode ser reinicializado automaticamente, sem

afetar outros, ou o próprio kernel.

Segundo o fabricante, nenhum outro RTOS comercial oferece esse grau de

proteção [4] e este tem sido usado desde a década de 1980 em aplicações de

desempenho crítico, de instrumentos médicos a centrais de atendimento do serviço de

emergência Norte-Americano 911, e até em sistemas de controle de tráfego aéreo.

O software do SCAV foi desenvolvido utilizando-se um dos ambientes de

desenvolvimento padrão do QNX, o Photon Application Builder (PhAB), uma IDE

gráfica orientada a objetos e direcionada a eventos, que utiliza as linguagens C e C++.

2.3 – Desenvolvimento

Tendo em vista que o desenvolvimento do SCAV já apresenta elevado grau de

maturidade, com um framework estável e testado em campo, cabe aos programadores

dos sistemas destinados às novas plataformas desenvolver interfaces personalizadas e

orientadas às particularidades de cada uma delas.

Como exposto anteriormente, compartimentos da planta supervisionada (fig.

2.3.1) podem ser selecionados e ter atribuídas uma ou mais avarias (fig. 2.3.2). Para

tanto, basta o operador posicionar o mouse sobre um dos compartimentos, acessar um

menu com um clique do mouse e escolher as avarias pertinentes.

A implementação dessa importante funcionalidade do sistema depende da

capacidade do software de, baseado na posição do mouse no momento do clique,

determinar qual compartimento foi selecionado, e por conseguinte, a área da imagem

que deve ser preenchida com a cor associada à avaria escolhida.

O que torna isso possível é o mapeamento, em tempo de projeto, da área

ocupada por cada compartimento relacionado na planta baixa. Esta é, porém, uma das

atividades mais dispendiosas durante o desenvolvimento de cada novo SCAV, que deve

ser executada para cada uma das múltiplas plataformas que o possuem.

7

Figura 2.3.1 – Compartimento de um navio, no SCAV, no ambiente PhAB.

Fonte: Próprio.

Figura 2.3.2 – Compartimento marcado com a avaria Incêndio.

Fonte: Próprio.

8

Do ponto de vista da programação, para se obter tal efeito com as ferramentas

disponíveis ao PhAB e ainda com a menor complexidade algorítmica e menores

overheads de processamento e memória possíveis, foi tomada a decisão de não alterar

as cores do compartimento selecionado dentro do objeto 'imagem' da planta baixa, e

sim, mapear seus compartimentos com objetos do tipo polígono, dispostos por sobre a

planta.

Em uma condição normal, esses polígonos são definidos como transparentes,

não sendo exibidos. Em condição de avaria, suas propriedades de cor são definidas de

acordo com a avaria selecionada, vermelho para incêndio, azul para alagamento, cinza

para fumaça, etc.

Como objetos, cada polígono possui um nome único que o identifica, e que deve

ser indexado pelo programador, o que posteriormente permitirá o preenchimento de

informações pertinentes ao compartimento, através de consultas a um banco de dados.

Cada polígono precisa ser construído à mão, ponto a ponto, de forma a melhor

preencher as centenas de compartimentos da planta (fig. 2.3.3). Quão melhor cada

polígono respeitar as fronteiras de seu compartimento, melhor será sua apresentação em

tela.

Figura 2.3.3 – Polígono mapeado no compartimento em tempo de projeto, no PhAB.

Fonte: Próprio.

9

Em um primeiro momento, seria necessário "apenas" desenhar tais polígonos

para permitir a implementação da interface desejada, no entanto, apesar de os objetos

desse tipo poderem responder a eventos de clique do mouse, sua região de resposta não

é a área interna ao polígono, e sim todo o interior do menor retângulo que o

circunscreve.

Segue então, que usar esses objetos como interface com o operador seria

impraticável em determinadas situações, como tentar selecionar um compartimento cujo

polígono esteja "atrás" de outro.

Na figura 2.3.4, por exemplo, tentar selecionar o polígono 2 seria impossível se

o polígono 1 estivesse "à sua frente" (ordem de exibição na janela). Repare na área de

resposta a eventos do mouse de "1", indicada pelo retângulo branco de traço fino que o

circunscreve.

Nesse caso, tomar o cuidado de posicionar 2 "à frente" de 1 resolveria o

problema, mas para casos de um compartimento côncavo e outro ao seu lado que

preencha essa concavidade, ou para o caso da proa do navio (fig. 2.3.5) que sendo quase

triangular responderia a cliques fora de seu interior, não há solução se usados objetos do

tipo polígono para a detecção desses eventos.

Figura 2.3.4 – Polígonos mapeados, em conflito quanto à resposta a eventos do mouse.

Fonte: Próprio.

10

Figura 2.3.5 – Proa de um navio mapeada em um polígono.

Fonte: Próprio.

A decisão de projeto que permitiu contornar este problema se resume a mapear

novamente os compartimentos, mas desta vez com objetos do tipo retângulo, que são

definidos como transparentes e que serão os responsáveis pela detecção de eventos de

mouse sobre suas regiões.

Assim como os polígonos, os retângulos devem ser criados de forma a melhor

preencher seus compartimentos; mas como as geometrias destes variam ao longo do

navio, muitas vezes acompanhando o contorno do casco, uma cobertura adequada

poderá demandar desde apenas um retângulo no melhor caso, até dezenas nos piores

casos (fig. 2.3.6 e 2.3.7).

Isto posto, como esses objetos serão sempre transparentes, não é necessário que

preencham perfeitamente o compartimento, isto é, para manter a um mínimo o total

necessário, é permitido ao programador traçá-los sobrepondo-se uns aos outros, às

paredes do compartimento, e "errar" pequenas áreas (de alguns pixels) nas bordas, que

de outra forma precisariam de vários pequenos retângulos para serem preenchidas.

11

Figura 2.3.6 – Retângulos mapeados em um compartimentos simples.

Fonte: Próprio.

Figura 2.3.7 – Retângulos mapeados em um dos compartimentos mais complexos.

Fonte: Próprio.

12

Um navio de médio porte possui pouco mais de 300 compartimentos, cada um

com seu polígono e seus retângulos, mas o programador do SCAV precisa mapear duas

vezes esse número, pois o sistema possui dois modos de exibição, uma visão geral dos

compartimentos e uma visão ampliada de cada um dos "reparos", sub-divisões do navio

de responsabilidade de um dos grupos de combate a avarias.

O subseqüente grande volume de trabalho, meticuloso e de alto teor empírico

que essas soluções demandam, onera de tal forma um programador do SCAV que

mesmo estando acostumado ao ambiente PhAB e à tarefa, ele despende várias semanas

para sua conclusão.

Apesar da automatização dessas tarefas ser um problema de difícil realização,

em princípio, este aluno propôs ser capaz de desenvolver um software que o fizesse,

visando possibilitar um melhor aproveitamento do tempo do programador antes

designado a esta tarefa.

2.4 – Requisitos Com o objetivo de eximir o programador da grande parte laboriosa do

desenvolvimento do SCAV e, consequentemente, proporcionar uma redução maciça no

tempo necessário à criação e manutenção de suas novas versões, o software

implementado deve possuir uma interface gráfica intuitiva e amigável, almejando uma

curva de aprendizagem o mais acentuada possível.

Ele deve ser capaz de analisar um arquivo de código fonte do SCAV em busca

de polígonos e retângulos já declarados e, se possível, da própria imagem da planta

baixa do navio, e juntamente com algum conteúdo do banco de dados do sistema,

fornecê-los ao programador, agora usuário, com uma listagem de todos os

compartimentos cadastrados do navio.

Se representados em tela através de marcadores individuais, os compartimentos

estarão prontos para serem posicionados sobre suas respectivas regiões da planta baixa.

Essa é a única ação do programador realmente indispensável, pois é o que associa o

significado físico de um determinado compartimento, sua posição no navio e suas

características listadas no banco de dados, a uma região fechada da planta baixa virtual.

13

A partir deste posicionamento o software deverá aplicar, de forma automática e

transparente, técnicas de processamento de imagens sobre a planta, de forma a mapear

as regiões e criar os objetos responsáveis pela interface visual.

Por fim, tendo identificado e processado todos os compartimentos, o software

deverá escrever sobre o arquivo fonte original ou uma cópia deste, todo código

necessário para descrever os objetos calculados, de forma a transparecer ao ambiente

PhAB, no QNX, que foi este que os descreveu.

14

Capítulo 3

Engenharia Reversa

3.1 – Arquivo Fonte

Dada a experiência anterior deste aluno com a IDE para Windows, Borland C++

Builder (BCB) e a forma como ela armazena a formatação de janelas e componentes

visuais em arquivos de texto simples (extensão ".dfm"), imaginou-se bastante provável

a existência de um arquivo similar, também gerado automaticamente, em projetos no

ambiente PhAB, no SO QNX.

Depois de copiar os arquivos gerados na criação de um projeto de teste para o

SO Windows e passar algum tempo escrutinando-os com uma ferramenta de edição de

texto voltada para programação (Notepad++), descobriu-se que, de fato, o PhAB

armazena a formatação de janelas e objetos visuais de forma similar ao BCB, em um

arquivo com o mesmo nome da janela no programa e extensão “.wgtw”. Este arquivo,

no entanto, é um arquivo "misto", que além de conter texto, possui também valores

binários armazenados diretamente em algumas propriedades de objetos (fig. 3.1.1), duas

das quais essenciais à realização deste projeto.

Figura 3.1.1 – Trecho exemplo da natureza “mista” do arquivo fonte (*.wgtw). Fonte: Próprio.

15

O passo seguinte foi descobrir como identificar o início e o fim da descrição de

cada objeto no arquivo. Por inspeção, concluiu-se que todos os objetos visuais que

foram gerados têm como propriedade inicial sua classe, como pode-se observar na fig.

3.1.1, o que poderia ser um identificador válido se todas fossem começadas por "Pt". De

fato, isso se provou verdade para todas as classes dos objetos visuais utilizados nas telas

do SCAV.

A próxima propriedade notável dos objetos é o "Nível de Aninhamento", que

cresce à medida em que estes são postos em contêineres. A janela principal tem nível 1,

todos os objetos pertencentes a ela têm nível 2, se um destes puder possuir outros como

por exemplo uma entidade grupo de objetos, então todos dentro dele terão nível 3 e

assim sucessivamente.

Segue o nome do objeto que, estranhamente, pode ser o mesmo em vários deles,

se igual à sua classe. Por isso, deve ser tomado o cuidado de sempre buscar o próximo

objeto depois de se ler o nome do atual, para evitar erros de acesso.

Outras propriedades de interesse são a posição do objeto dentro do seu contêiner

e suas dimensões, sinalizadas pelos identificadores "pos" e "dim" respectivamente, cuja

ordem de escrita no código fonte não é estrita. O parâmetro "pos" são as coordenadas do

canto superior esquerdo do objeto. Os valores desses campos são números inteiros

armazenados em formato texto.

Nos polígonos, sua propriedade "points" armazena sequencialmente as posições

de seus vértices. Nas imagens, a propriedade "pixmap" contém, além de outros dados, o

mapeamento de todos seus pixels em formato RGB. Ambas têm seus valores

armazenados em formato binário.

No mais, as outras propriedades dos objetos, apesar de importantes para a

correta exibição em tela e funcionamento do sistema, não são relevantes para o

processamento dos compartimentos (ex: cor dos objetos).

16

3.2 – Imagens

Todas as propriedades dessa classe podem ser lidas diretamente como texto,

salvo o "pixmap", que contém a listagem seqüencial de cada um dos pixels que formam

a figura, com os coeficientes das três cores primárias descritos em binário. Na tentativa

de decifrar a codificação utilizada, foram criadas e inseridas em projetos de teste no

PhAB algumas imagens de baixa complexidade (fig. 3.2.1). Elas foram projetadas com

cores distintas e padrões simples, de forma a produzir um mínimo de código fonte, no

qual fosse possível reconhecer a disposição das cores e as posições dos pixels nas

imagens, por inspeção visual do código.

Figura 3.2.1 – Imagens de teste utilizadas (cada cor preenche um pixel). Fonte: Próprio.

Os resultados obtidos foram, a princípio, desanimadores. Imaginou-se que a

análise do código gerado para um projeto contendo apenas a imagem de teste 1 seria

suficiente para se inferir a codificação utilizada pelo objeto. Entretanto, para uma

imagem de apenas 9 pixels foram escritos 133 bytes de dados em sua propriedade

"pixmap", muito mais do que os 27 necessários para mapear a imagem colorida, se

usado o formato de 3 bytes por pixel.

17

Foi preciso comparar os dados gerados para os objetos das quatro imagens da

fig. 3.2.1, até que fosse possível compreender o básico necessário da formatação desse

arquivo, que permitisse a leitura da imagem por software. As words são armazenadas no

formato big-endian e têm tamanho variável, possuindo dois ou três bytes. A word

composta pelos bytes 13 e 14, armazena a largura da imagem e aquela composta pelos

bytes 15 e 16, sua altura. Os dados de cor dos pixels só começam, de fato, a partir do

byte 56, com as cores sendo armazenadas na forma BGR (uma word de 3 bytes por cor,

em formato big-endian). O propósito dos outros bytes anteriores a esses permanece

desconhecido.

A última característica, e considerada por este aluno como a mais excêntrica da

formatação da imagem, é o fato de todas as linhas terem o número de pixels sendo

necessariamente um múltiplo inteiro de oito, e se assim não o forem, serem preenchidas

com bytes "aleatórios" (de bytes NULL até trechos anteriores do arquivo fonte,

aparentemente ainda em memória) até que satisfaçam esse padrão. A fig. 3.2.2

demonstra a codificação da imagem de teste 3.

Figura 3.2.2 – Codificação de linha de uma imagem, com pixels de preenchimento. Fonte: Próprio.

Com essas particularidades do formato conhecidas, um objetivo secundário mas

ainda assim importante do software, ser capaz de ler a imagem da planta baixa do navio

diretamente do código fonte do SCAV, se tornou passível de implementação.

18

3.3 – Polígonos

De forma similar às imagens, os polígonos possuem apenas uma propriedade,

points, cujo conteúdo é armazenado em formato binário (fig. 3.3.1). Ela é dividida em

duas linhas, a primeira armazena em texto o número inteiro positivo de vértices (pontos)

do polígono e a segunda contém words de 2 bytes armazenadas em formato big-endian

e em pares, com cada par representando as coordenadas de cada um dos pontos.

No entanto, onde é definida a origem do sistema de coordenadas desses pontos?

Uma primeira hipótese seria o canto superior esquerdo da janela principal, com todos os

objetos se orientando a partir desse ponto, mas ela se provou falha. O ponto de origem

correto é o ponto "pos" do contêiner do polígono, do objeto com o "nível de

aninhamento" imediatamente superior. Esse ponto é o mesmo que serve de referência

para as coordenadas posição "pos" do polígono.

Ainda nessa questão, os objetos desse tipo possuem um segundo parâmetro

"pos", sempre cadastrado depois de "points", que foi caracterizado por testes como

sendo um deslocamento aplicado aos pontos de todos os vértices. Pela análise dos

objetos desse tipo criados usando o PhAB, não foi possível concluir o que motiva o

preenchimento dos valores encontrados nesse campo. Assim, essa propriedade foi

aproveitada para o armazenamento do ponto de origem do compartimento, definido pelo

operador, que será visto com maiores detalhes mais a diante.

Figura 3.3.1 – Parte do código fonte da descrição de um objeto polígono. Fonte: Próprio.

19

Como dito anteriormente os polígonos, assim como todos os objetos declarados,

possuem nomes. Para propósito de associação aos retângulos que ocupam os mesmos

compartimentos, os nomes dos polígonos possuem uma numeração seqüencial singular,

e serão referência para a nomenclatura dos retângulos. Tais nomes são gerados no

momento em que os compartimentos são efetivamente posicionados em tela.

3.4 – Retângulos

Por último, mas não menos importante, os retângulos. Estes são simplórios em

suas propriedades, não tendo valores armazenados em formato binário, codificados ou

não. Suas propriedades notáveis são sua posição na tela e suas dimensões, que serão

calculadas automaticamente pelo algoritmo de otimização de preenchimento utilizado.

Como são necessários para prover resposta a eventos de clique do mouse para os

compartimentos, os retângulos devem possuir uma associação biunívoca com o

polígono que os representa em tela. Essa ligação se dá pela nomenclatura de todos os

retângulos com o mesmo número dado ao polígono de seu compartimento, acrescido de

uma letra, em ordem alfabética, gerando então um nome singular (ex. 01a). Na

eventualidade do algoritmo preencher um compartimento com mais de 26 retângulos, os

nomes dos retângulos consecutivos passam a possuir duas letras.

20

Capítulo 4

Processamento de Imagem

4.1 – Segmentação As plantas baixas dos navios são imagens coloridas, editadas por um

profissional durante sua criação e na qual não são projetadas para serem "comportadas",

de forma a permitir a execução direta do algoritmo de cálculo dos compartimentos que

se pretende usar.

Todas as imagens têm fundo preto e fronteiras de compartimentos (anteparas)

em cores claras e distintas, azul claro, cinza e amarelo, para navios com três grupos de

"reparos", por exemplo (fig. 4.1.1).

Figura 4.1.1 – Exemplo descaracterizado da planta baixa de um navio. Fonte: Próprio

Além disso, como conseqüência das ferramentas de edição utilizadas, essas

anteparas não são traçadas apenas com cores sólidas, mas possuem também gradientes

de sua cor ao fundo preto, quando em traços de curvas e de diagonais (fig. 4.1.2).

Figura 4.1.2 – Exemplo dos traços em gradiente de cor. Fonte: Próprio

21

A tomada de decisão do algoritmo de processamento de compartimentos sobre

que tons de cor deveriam ser considerados fundo e quais seriam anteparas, seria

dificultada por esses gradientes. Soma-se a isso o fato de que, para a visão humana, a

percepção de intensidade luminosa varia consoante à cor, portanto, um limiar de

luminância escolhido por um programador como adequado para uma cor, talvez não o

seja para outra.

4.2 – Escala de Cinza Como exposto, todas as anteparas devem ser apreciadas de uma mesma forma

pelo algoritmo que processa os compartimentos, independentemente de suas cores.

Assim, evidentemente, o primeiro passo deve ser converter a imagem em uma outra

com apenas tons de cinza. A abordagem originalmente vista como menos complexa

seria derivar da imagem original uma nova, composta pela luminância relativa (às vezes

referida apenas como luminância) de seus pixels.

Para isso foram testados dois padrões de caracterização de luminância, definidos

nas Recomendações 601 e 709 da International Telecommunication Union -

Radiocommunications sector (ITU-R). Em ambos, luminância relativa é definida como

a soma ponderada das componentes RBG, baseada nas características de percepção de

cor da visão humana, apesar de não o fazerem com os mesmos coeficientes.

O primeiro, e mais antigo deles, define a codificação de sinais analógicos de

vídeo em formato digital de baixa definição (para os padrões de hoje), tendo sido

aproveitado inclusive na definição do padrão de vídeo MPEG. Já o segundo, foi criado

especificamente para a padronizar o formato de alta definição HDTV.

Como o cálculo da luminância nas duas determinações se distingue apenas nos

coeficientes que ponderam cada componente de cor, não há como saber a princípio qual

deles teria o melhor desempenho. Em um primeiro momento, optou-se de forma

empírica pela utilização do padrão definido na Rec. 601, visto que os resultados obtidos

com este foram os que produziram menos artefatos e falhas nos contornos dos

compartimentos da imagem final, quando processada com o próximo algoritmo. Mais

adiante, no entanto, uma outra solução foi encontrada.

22

Então, com a imagem livre de ambigüidades introduzidas pelas informações de

cor, é preciso reduzi-la de tons de cinza a puramente monocromática, preta e branca,

para então atingir-se a almejada separação entre entidades fundo e fronteira (anteparas

dos compartimentos).

4.3 – Thresholding No campo de processamento de imagens, converter uma imagem em escala de

cinza para uma em preto-e-branco é uma necessidade usual, e comum a diversas

disciplinas. O objetivo é segmentar a imagem original em uma nova, binária, e sempre

com a menor perda de informação possível.

Dada a diversidade de aplicações, cada área que demanda esse tipo de

processamento acaba por apresentar uma ou mais particularidades, como análise de

imagens com sombras ou variações de iluminação, reflexos, ruído, etc. Para satisfazer

essas demandas específicas, várias abordagens ao problema foram desenvolvidas ao

longo dos anos, culminando hoje em uma miríade de algoritmos.

Demonstrando bem a ordem de grandeza dessa quantidade, Sezgin et. al. [7]

analisam e categorizam apenas 40 deles em seu estudo. Além disso, agruparam os

algoritmos em seis categorias distintas, a partir das características da imagem que são

exploradas durante o processamento.

Dentre as abordagens existentes, as mais básicas analisam o histograma de cores

da imagem e selecionam, de alguma forma, dentre os tons de cinza existentes, um único

limiar (threshold) que defina todos os outros tons mais escuros como sendo pixels

pretos e todos os mais claros como brancos, ou o contrário. Essa metodologia simples,

no entanto, falha em situações um pouco mais complexas, como em imagens que

possuam variações de iluminação.

Afortunadamente, as plantas baixas deste projeto são uniformes o suficiente para

não precisarem de um algoritmo mais robusto, que implemente threshold adaptativo por

exemplo. Ainda assim, mesmo na classe de algoritmos simples, não há um que seja

simultaneamente mais simples e de desempenho superior. Tendo seu uso amplamente

sugerido e pela grande quantidade de fontes detalhadas sobre sua implementação e

funcionamento, este aluno escolheu como algoritmo de thresholding, o Método de Otsu.

23

4.4 – Método de Otsu Batizado em homenagem a Nobuyuki Otsu [8][9], que publicou a técnica em

1979 em seu artigo "A Threshold Selection Method from Gray-Level Histograms"

(Método de Seleção de Limiar a partir de Histogramas em Escala de Cinza), parte das

seguintes premissas: a imagem, e por conseqüência seu histograma, são bimodais, ou

seja, compostos de duas entidades, aqui denominadas plano de fundo e plano de face; a

imagem possui iluminação uniforme, garantindo que quaisquer variações de luminância

representem diferenças entre as entidades; e por fim, para o algoritmo não há qualquer

noção de distribuição espacial de objetos na imagem.

Pressupondo o cumprimento dessas diretrizes, o primeiro passo do método é

gerar um histograma de todas as cores (tons de cinza) da imagem. Em seguida,

percorre-se sequencialmente todos os valores possíveis de threshold, calculando a cada

iteração os seguintes parâmetros: o coeficiente peso de cada classe, que é a razão entre a

quantidade de pixels pertencentes àquela classe e o total de pixels na imagem; o valor

médio dos pixels de cada classe; a variância entorno desse valor, novamente por classe;

e por fim a Within-Class Variance (Variância Intra-classe) definida como a soma das

variâncias, ponderadas por seus respectivos pesos.

O objetivo final é encontrar o valor de limiar que produza a menor variância

intra-classe, o que representa, para o método, a distribuição ótima entre os planos de

fundo e de face, dadas as restrições.

Tomando como exemplo uma imagem de tamanho 6x6 pixels e com 6 tons

diferentes de cinza, e seu histograma (fig. 4.4.1):

Figura 4.4.1 – Imagem exemplo do Método de Otsu, e seu histograma. Fonte: "Otsu Thresholding - The Lab Book Pages" [10].

24

E executando o algoritmo, obtemos os seguintes resultados parciais, para cada

um dos limiares possíveis:

Threshold T=0 T=1 T=2 T=3 T=4 T=5

Peso, Fundo Wfu = 0 Wfu = 0.222 Wfu = 0.4167 Wfu = 0.4722 Wfu = 0.6389 Wfu = 0.8889

Média, Fundo Mfu = 0 Mfu = 0 Mfu = 0.4667 Mfu = 0.6471 Mfu = 1.2609 Mfu = 2.0313

Variância, Fundo Σ²fu = 0 σ²fu = 0 σ²fu = 0.2489 σ²fu = 0.4637 σ²fu = 1.4102 σ²fu = 2.5303

Peso, Face Wfa = 1 Wfa = 0.7778 Wfa = 0.5833 Wfa = 0.5278 Wfa = 0.3611 Wfa = 0.1111

Média, Face Mfa = 2.3611 Mfa = 3.0357 Mfa = 3.7143 Mfa = 3.8947 Mfa = 4.3077 Mfa = 5.000

Variância, Face σ²fa = 3.1196 σ²fa = 1.9639 σ²fa = 0.7755 Σ²fa = 0.5152 σ²fa = 0.2130 σ²fa = 0

Variância Intra-Classe σ²W = 3.1196 σ²W = 1.5268 σ²W = 0.5561 σ²W = 0.4909 σ²W = 0.9779 σ²W = 2.2491

Tabela 4.4.1 – Resultados parciais do algoritmo de Otsu. Fonte: "Otsu Thresholding - The Lab Book Pages" [10].

Na prática, essa forma de cálculo é intensa computacionalmente e, consoante ao

tamanho da imagem, pode vir a ser muito demorada.

Como uma alternativa mais eficiente, Otsu sugere o cálculo da Between Class

Variance (Variância Entre Classes), que se comporta de forma oposta à variância intra-

classe, no tocante em que o limiar que produzir a menor da segunda, produzirá a maior

da primeira.

Variância Intra-Classe σ²W = Wfu σ²fu + Wfa σ²fa

Variância Entre Classes σ²B = σ² - σ²W

σ²B = Wfu (Mfu - M)² + Wfa (Mfa - M)² (onde M = Wfu Mfu + Wfa Mfa)

σ²B = Wfu Wfa (Mfu - Mfa)²

Como fica evidente, para determinar a variância entre classes não é necessário o

cálculo das variâncias individuais dos planos fundo e de face, apenas seus valores

médios e pesos, o que reduz o processamento total a cada iteração, e é a razão desta ser

a forma de realização mais indicada para aplicações práticas.

25

Para a mesma imagem de exemplo acima, ao compararmos os resultados

parciais das duas formas, podemos ver a característica antagônica dos resultados:

Threshold T=0 T=1 T=2 T=3 T=4 T=5

Variância Intra-Classe σ²W = 3.1196 σ²W = 1.5268 Σ²W = 0.5561 σ²W = 0.4909 σ²W = 0.9779 σ²W = 2.2491

Variância Entre Classes σ²B = 0 σ²B = 1.5928 Σ²B = 2.5635 Σ²B = 2.6287 σ²B = 2.1417 σ²B = 0.8705

Tabela 4.4.2 – Comparação de resultados entre formas de cálculo. Fonte: "Otsu Thresholding - The Lab Book Pages" [10].

4.5 – Conclusões sobre Segmentação Apesar de a metodologia de segmentação delineada até aqui ter sido

integralmente implementada e ter alcançado seu objetivo com desempenho satisfatório,

descobriu-se empiricamente que a abordagem conservadora de levar em consideração a

variação de intensidade luminosa percebida consoante à cor, da fisiologia humana, não

é estritamente necessária para essa aplicação.

Dada a natureza da imagem de planta-baixa alvo, com grandes áreas de plano de

fundo em preto e estreitos anteparos em cores, é possível usar uma outra abordagem que

demonstrou produzir melhores resultados, virtualmente eliminando o problema de

"compartimentos abertos", que será detalhado mais adiante.

Ela consiste em executar o thresholding sobre cada coeficiente do modelo RGB

separadamente, produzindo três segmentações distintas, uma por camada de cor

primária, em preto e vermelho (R), preto e verde (G), e preto e azul (B). Entretanto,

como as camadas são visualizadas simultaneamente, acaba-se construindo um fac-

símile da imagem original, como se segmentada em oito entidades diferentes: preto,

branco, vermelho, verde, azul, amarelo, ciano e magenta.

Pode-se então derivar desta, a imagem bi-modal desejada, bastando para isso

interpretar como pixels do plano de fundo apenas os de cor preta, que foram

considerados como tal em cada uma das três etapas de segmentação. Aqueles que

possuírem qualquer outra cor farão parte do plano de face, sendo transformados em

pixels brancos.

26

Capítulo 5

Processamento dos Compartimentos

5.1 – Considerações Iniciais

Este capítulo trata do âmago do software proposto, os procedimentos necessários

para processar as áreas da planta baixa já segmentada, e gerar as estruturas que as

representarão como compartimentos para a sub-rotina de Interface Homem-Máquina

(IHM) do SCAV.

Quando do início desse projeto, foi sugerido que essa etapa de determinação de

compartimentos pudesse ser automatizada, fazendo-se uma busca exaustiva na imagem

por regiões fechadas. Essa, no entanto, é uma propriedade necessária mas não suficiente

para a caracterização de um compartimento. Exemplos de áreas que não configuram

compartimentos são regiões hachuradas internas a tanques de armazenamento e demais

elementos "artísticos" da planta, como estes apresentados na fig. 5.1.1: o canhão de

proa, a lancha tática e heliponto de Veículos Aéreos Não Tripulados (VANT) à popa, a

estrutura da antena do radar principal, entre outros.

Figura 5.1.1 – Exemplos de regiões fechadas da imagem que não configuram compartimentos.

Fonte: Próprio

27

Ademais, dado que não existe uma forma computacional de relacionar o nome

e/ou a descrição de um compartimento à área física ocupada por ele, essa etapa ainda

recairia sobre o programador do SCAV.

Decidiu-se então por realizar todos os passos de processamento depois de um

compartimento ter sido identificado como tal. Assim, deve ser oferecida ao usuário uma

lista, passível de filtragem, contendo os nomes e códigos de todos os compartimentos

existentes no navio. Além disso, ainda serão dispostos marcadores visuais individuais

de compartimentos por sobre a imagem da planta e, de modo bastante intuitivo, bastará

arrastar cada um deles para dentro de seu respectivo compartimento para dar início ao

processamento necessário. A fig. 5.1.2 oferece um esboço da interface proposta.

Figura 5.1.2 – Esboço de interface para o software.

Fonte: Próprio

28

5.2 – Área Interna

O primeiro passo de todo o processamento de compartimentos é, partindo do

ponto definido pelo usuário como interno a um deles, determinar toda a área ocupada

por este. Para isso foi usado o algoritmo de preenchimento mais comum das ferramentas

de edição de imagem, Flood Fill [11] (Preenchimento por Inundação), também

conhecido como Bucket Fill (Preenchimento por Balde).

A implementação clássica desse método consiste em, partindo de um pixel

original, alterar a cor deste e repetir recursivamente a chamada da função para cada um

de seus quatro "vizinhos", os dois verticais e os dois horizontais, se as cores deles forem

iguais à cor do original. No entanto, além de não ser a forma de implementação mais

eficiente, se for tentado um preenchimento de uma grande região sólida, dados os

tamanhos de imagens manipulados atualmente, a quantidade de chamadas da função na

pilha pode ser grande o suficiente para causar um stack overflow (transbordo/estouro de

pilha).

No software foi utilizada uma implementação em forma de pilha explícita desse

algoritmo, utilizando um objeto para sua manipulação, mitigando assim o problema de

estouro por excesso de chamadas recursivas. Além disso, o algoritmo foi escrito na

forma de Scanline Flooding (algo como "inundação por linhas") onde uma linha

horizontal é tratada por vez, evitando acessos repetidos a um mesmo pixel e assim

tornando o processo mais eficiente.

Figura 5.2.1 – Exemplo de execução do algoritmo Scanline Flooding sobre um compartimento real. Ponto

incial em verde, área mapeada em ciano. Em preto, as anteparas do compartimento. As coordenadas da

área interna estão salvas em memória para uso das próximas sub-rotinas.

Fonte: Próprio

29

Foi tomado o cuidado de armazenar as coordenadas de todos os pixels

processados em uma estrutura externa à função, de modo que essa lista que representa a

área interna ao compartimento possa ser passada às funções seguintes. De posse de toda

a região ocupada pelo compartimento, é possível começar a traçar uma estratégia para

seu preenchimento com retângulos.

5.3 – Retângulos

Recapitulando, o preenchimento do compartimento com objetos do tipo

retângulo se faz necessário devido à forma como o ambiente de desenvolvimento PhAB

responde a eventos de clique de mouse sobre um objeto do tipo polígono. Se estes

eventos ocorressem somente no interior do polígono traçado, esses objetos poderiam ser

usados para a interface com aquele periférico. No entanto, a área sensível aos eventos é

o menor retângulo que circunscreve o polígono, dando origem a problemas de

precedência no caso de polígonos com concavidades preenchidas por protuberâncias de

outros vizinhos, ou seja, dentro da planta baixa de um navio, praticamente qualquer

compartimento não retangular.

Para evitar as dificuldades de implementação e o overhead de processamento ao

calcular dinamicamente se o ponto do clique na tela pertence ao interior do polígono

cujo evento foi executado, a equipe de desenvolvimento do SCAV decidiu por

preencher o compartimento com retângulos invisíveis e associar a eles os eventos de

mouse, efetivamente trocando processamento por tempo de desenvolvimento e memória

em tempo de execução do programa.

Esse processo é referido como problema de cobertura de um polígono retilíneo

com o menor número de retângulos, com sobreposição permitida. A literatura [12]

define esse problema como NP-hard [13], o que normalmente implica em ser possível

encontrar soluções muito boas, mas encontrar a melhor possível seria muito

dispendioso. As abordagens encontradas para sua solução foram consideradas

excessivamente complexas, e este aluno optou por desenvolver uma própria.

30

Sem ter como determinar quão grande seria a quantidade possível de retângulos

em tela sem comprometer o desempenho do sistema, este aluno partiu da solução mais

simples possível, para cada pixel de área do compartimento, inserir um retângulo de

área 1x1 que o ocupasse. Quando a IDE "morreu" ao tentar carregar um arquivo de teste

com apenas um punhado de compartimentos preenchidos, a necessidade de otimização

passou de óbvia a obrigatória.

Com isso em mente, a próxima abordagem imaginada foi uma espécie de

integração discreta dos compartimentos, preenchendo-os com retângulos degenerados

em segmentos de reta. Como os compartimentos, em geral, possuem alturas e

comprimentos diferentes, quantidades distintas de retângulos verticais ou horizontais

serão necessárias para preenchê-los, dada a direção de integração.

Além disso, se um compartimento possui um ou mais "furos" como por exemplo

um tanque ou outro compartimento completamente inscrito naquele, os retângulos não

podem sobrepô-lo, precisando ser traçados das anteparas do compartimento até as do

furo, em ambos os lados. Portanto deve-se usar a orientação que os tiver gerado em

menor número. A fig. 5.3.1 demonstra os conceitos deste parágrafo e do anterior.

Figura 5.3.1 – Retângulos sem otimização. O gradiente de azul para amarelo denota a direção do

preenchimento. O compartimento da esquerda é de número 1 e o da direita 2.

Fonte: Próprio

Como próximo passo de otimização, se dois retângulos com dimensões iguais

estiverem lado a lado, vertical ou horizontalmente, pode-se substituí-los por apenas um

que ocupe ambas as suas áreas (fig. 5.3.2). Se implementada como uma verificação

exaustiva, o primeiro retângulo será repetidamente expandido e pode-se perceber que

essa pequena alteração produzirá uma solução ótima para compartimentos retangulares

paralelos ao eixo horizontal, preenchendo-os com um retângulo apenas.

31

Figura 5.3.2 – Preenchimento por retângulos com otimização.

Fonte: Próprio

É valido notar que o pior caso de aproximação dos retângulos seriam

compartimentos com arestas em ângulos de 45° com a horizontal, para os quais esse

método é capaz de reduzir a distribuição original. Portanto, quão mais acentuada a

inclinação das anteparas dos compartimentos em relação à horizontal, mais retângulos

serão necessários para seu preenchimento.

Uma concessão já usada pelos programadores do SCAV é a inspiração para o

próximo nível de otimização, permitir um erro de aproximação. Como os retângulos são

invisíveis, pode-se permitir que um retângulo aproxime o preenchimento da área de seu

vizinho, errando por um determinado número de pixels.

A existência desse erro pode levar a dois resultados: espaços não preenchidos

dentro do compartimento, se o vizinho for maior que o retângulo em questão, ou em

uma pequena sobreposição da antepara, se ele for menor. Nenhum dos dois não causará

problemas, dado que o erro em questão seja pequeno. No último, dificilmente um

operador vai clicar em uma antepara de alguns pixels de espessura propositadamente,

principalmente porque o sistema não prevê uma resposta a isso, e se o fizer acabará

apenas selecionando um dos compartimentos, e imaginar que o tivesse feito. E no

primeiro caso, como esses espaços vazios só existirão próximos às anteparas, a chance

de serem alvo do operador é igualmente pequena. A figura 5.3.3 demonstra

aproximações com erros sucessivamente maiores.

32

Figura 5.3.3 – Preenchimento por retângulos com erro permitido. As regiões vermelhas representam as

partes de retângulos se sobrepondo às anteparas.

Fonte: Próprio

33

Uma conseqüência notável da otimização, seja com ou sem permissão de erros,

é o fato que não necessariamente a orientação de integração que produzia antes o menor

número de retângulos, vertical ou horizontal, será aquela que o fará após a redução por

aproximação, como demonstra a fig. 5.3.4. De fato, não é sequer possível afirmar que

para qualquer compartimento as aproximações em um mesmo sentido mas em direções

opostas, horizontal e pela esquerda ou pela direita por exemplo, produzirão uma mesma

quantidade final de retângulos. Logo, para determinar o melhor resultado, é necessário

executar o processo inteiro quatro vezes, uma para cada sentido e direção possíveis.

Figura 5.3.4 – O sentido de preenchimento que produz os melhores resultados pode variar de acordo com

cada valor de erro permitido.

Fonte: Próprio

Claramente, quão maior o erro permitido menor será o número de retângulos

necessários por compartimento. Entretanto, se o erro for grande demais, há o risco de se

deixar uma região considerável do compartimento sem preenchimento ou pior, partes de

um retângulo podem ultrapassar anteparas e se sobreporem a um compartimento

vizinho. A fig. 5.3.5 demonstra execuções do algoritmo em um mesmo compartimento,

com crescentes valores de erro permitido.

34

Figura 5.3.5 – Exemplo de erro permitido grande demais. As regiões vermelhas representam as partes de

retângulos se sobrepondo às anteparas, as verdes, se sobrepondo a outro compartimento.

Fonte: Próprio

Pode-se perceber que permitir um erro de aproximação de 3 pixels seria algo

imprudente, já que obviamente existem geometrias de compartimentos a bordo que

levariam a sobreposição de compartimentos vizinhos. Talvez um erro de 2 pixels não

causasse o mesmo problema, no entanto, não há garantias disso já que existem anteparas

com traços de 1 pixel de espessura. Portanto, apesar de implicar em um total maior de

retângulos, optou-se pelo valor conservador de erro de 1 pixel, que permite no pior caso

a sobreposição de anteparas mas não de partes de compartimentos vizinhos.

Essa metodologia simples se provou bastante eficiente para a maioria dos

compartimentos que, em geral, são regiões retangulares com protuberâncias

retangulares e ângulos retos, levando a uma redução expressiva no total de objetos

necessários. Com isso concluem-se os passos do preenchimento por retângulos.

Uma melhoria futura capaz de reduzir ainda mais o número de objetos seria

executar o algoritmo múltiplas vezes para cada compartimento, com níveis de erro

incrementais a partir de 1 pixel, até que o número de retângulos se reduza a um, ou até

que um deles ultrapasse uma antepara e se sobreponha a parte de um compartimento

vizinho. Note que para um determinado valor de erro, mesmo que uma aproximação em

dada direção e sentido ultrapasse uma antepara, não é possível afirmar que as outras três

o façam.

35

Dessa forma, cada compartimento teria erro de aproximação próprio, e seria

possível garantir que erros pequenos de 2 pixels não causariam problemas e que, em

determinadas situações, mesmo um erro grande de 5 ou 6 pixels também não o faria.

Dada a dinâmica do algoritmo, talvez fosse possível obter resultados melhores

se as integrações e otimizações nas direções vertical e horizontal fossem executadas em

uma mesma iteração. Mas como não há forma de determinar a precedência entre elas,

seriam precisas execuções repetidas, por tentativa e erro. Além disso, considerando o

desempenho já alcançado e a outra melhoria proposta, espera-se que qualquer ganho

obtido com essa idéia seria apenas marginal.

5.4 – Perímetro

Com a etapa de geração dos retângulos concluída, é preciso determinar o

perímetro da área interna ao compartimento, como o primeiro passo para a geração do

polígono de preenchimento.

A seguir, partindo da área já encontrada e armazenada em memória, aplica-se

um Processamento Morfológico de Imagem [14] simples, a Extração de Fronteira, com

um Elemento Estruturante em cruz. O processo é ilustrado na fig. 5.4.1.

Efetivamente, o algoritmo testa todos os pixels da área calculada e procura

aqueles que não estão cercados por seus quatro adjacentes, a cima, a baixo, à esquerda e

à direita. Se ao menos um desses não existir, esse é considerado um ponto de fronteira.

Figura 5.4.1 – Processo de Extração de Fronteira. Começando no canto superior esquerdo, pode-se ver a

área calculada de uma região de exemplo em ciano e o Elemento Estruturante em cruz, em amarelo. Os

quadros evoluem da esquerda para a direita e as linhas de cima para baixo, terminando no canto inferior

direito. Em azul, pixels vizinhos àquele testado.

Fonte: Próprio

36

Como a área do compartimento é contígua, não granular, então qualquer ponto

que não estiver cercado por outros quatro pontos deve ser parte do perímetro, externo se

o compartimento não possuir furos, senão, do interno. A fig. 5.4.2 demonstra o

resultado do processo sobre um compartimento real de um navio.

Figura 5.4.2 – Perímetro da área interna ao compartimento, em vermelho. Área interna já calculada, em

ciano e fronteiras em preto.

Fonte: Próprio

Para a grande maioria dos compartimentos, isso seria o suficiente para traçar um

perímetro satisfatório, como ilustrado acima. Entretanto, em certos casos, algumas

anomalias não tratadas devidamente trariam ineficiências ao processo de cálculo de

polígonos, enquanto outras certamente o levariam à falha. Todas devem então ser

identificadas e corrigidas.

Essa rotina de correção foi implementada na forma de uma busca seqüencial

exaustiva, através da lista de pontos do perímetro, sempre retornando ao início assim

que um erro é corrigido. Claramente este não é o método mais eficiente de iterar pela

lista, mas garante que se uma nova discrepância for gerada ao corrigir uma antiga, ela

não será ignorada.

O primeiro passo é descobrir quantos e quais são os vizinhos do ponto atual no

laço de repetição, nas oito direções possíveis. De imediato já é possível determinar se o

ponto está "solto", ou seja, se não possui vizinho algum. Essa primeira anomalia parece

bastante improvável, senão impossível, de ser gerada durante o processamento

morfológico, mas é plausível como resultado de algum ajuste posterior. Esses pontos

devem ser eliminados.

37

Outros que devem ser tratados da mesma forma são os pontos que possuírem

apenas um outro adjacente, ou seja, pontas de rotas sem saída. Essas devem ser

removidas pois causariam problemas ao algoritmo posterior que traça um caminho

fechado por sobre o perímetro, antes de ajustar o polígono. Para isso, basta incluir à

remoção de pontos aqueles que tenham apenas um outro contíguo, já que a repetição

exaustiva tratará de remover o caminho inteiro, ponto a ponto. A fig. 5.4.3 demonstra

esse processo.

Figura 5.4.3 – Remoção de rota sem saída. Perímetro, em vermelho, pontos com apenas um vizinho, em

verde.

Fonte: Próprio

Infelizmente, a forma de solucionar esse problema não resolve outro. O pixel

restante da reta, no último quadro acima, está deslocado em relação ao que claramente

poderia ser um único segmento de reta, dando origem a dois deles. Para cada instância

similar a essa em um compartimento seriam criados 5 vértices de polígono, ao invés de

apenas 2. Esta será, portanto, a próxima correção realizada.

38

Para retificar esses "cúspides", procura-se na lista de pontos aqueles que

satisfaçam determinadas matrizes de gabarito (fig. 5.4.4). Se for encontrado um pixel de

perímetro cujos dois pontos laterais sejam anteparas, com apenas ambas diagonais

superiores pertencentes ao perímetro mas não seu ponto adjacente superior, que deve

pertencer à área interna do compartimento. A natureza dos três pontos inferiores não

importa. Satisfeitas essas condições, foi de fato encontrado um cúspide e para corrigi-lo,

o ponto analisado deve ser deslocado para esse espaço adjacente superior antes

desocupado. Como essas estruturas podem ocorrer em qualquer uma das quatro

orientações, deve-se testar todas elas para cada pixel.

Figura 5.4.4 – Matrizes de detecção de "cúspides". À esquerda todas elas nas 4 orientações possíveis. Em

vermelho, pontos da lista do perímetro; pontos de anteparas, em preto; ponto da área interna do

compartimento, em ciano e o ponto atual na iteração da lista, em verde. À direita, correções efetuadas.

Fonte: Próprio

Se aplicado ao resultado anterior, essa correção produz a reta única desejada,

como demonstra a fig. 5.4.5.

Figura 5.4.5 – Resultado anterior da redução de rota sem saída, corrigido.

Fonte: Próprio

39

Antes de prosseguir com a última anomalia, é oportuno demonstrar como são

interpretados compartimentos que estejam contidos em outros.

Se na área do compartimento houver um "furo", ou seja, se existe um traço

fechado de antepara que delimita outro compartimento totalmente inscrito naquele e

sem contato com sua fronteira externa, então durante o processamento morfológico

também será computado o perímetro desse furo, como exemplifica a fig. 5.4.6. Esses

perímetros internos são tão importantes ao cálculo polígono quanto o perímetro externo,

pois determinam o não preenchimento dos furos quando o polígono for feito visível.

Um compartimento pode possuir inúmeros furos.

Figura 5.4.6 – Exemplo de compartimento com furo.

Fonte: Próprio

Segue então a última situação anômala identificada, empiricamente, e ocorre

mesmo com todas as correções anteriores sendo executadas. Se o compartimento

contiver outro inscrito, e se qualquer parte das anteparas desse estiver localizada a uma

distância de apenas um pixel da antepara externa, então os pontos de perímetro

encontrados nesse intervalo serão comuns a ambos, ao externo e ao interno.

Assim como no caso da remoção de rotas sem saída, pontos pertencentes ao

traçado de dois perímetros também são um problema para o algoritmo que encontra

caminhos fechados, pois implicariam em serem percorridos mais de uma vez. Seguindo

a mesma premissa do traçado manual dos polígonos, é preferível errar por não

preencher esses caminhos de um pixel de largura, do que errar sobrepondo o polígono a

outros compartimentos internos.

40

A solução, como nos outros casos, é retirar esses pontos da lista de polígonos, o

que efetivamente transforma o compartimento com furos em um compartimento com

concavidades, como pode ser visto na fig. 5.4.7. Para identificá-los, basta procurar por

pixels que possuam anteparas em ambos seus pontos adjacentes acima e abaixo, ou, em

ambos à esquerda e à direita.

Na prática, esse algoritmo vai encontrar o primeiro ponto do intervalo, removê-

lo, e assim que o fizer, o resto do caminho passa a ser reconhecido como uma rota sem

saída. Todos os pontos ao longo da rota serão retirados pela outra rotina, salvo o último

que terá mais de um vizinho. Este será removido, como o primeiro, por essa regra.

Figura 5.4.7 – Exemplo de compartimento com outro inscrito, muito próximo à antepara. Os quadros

evoluem da esquerda para direita: primeiro área interna do compartimento é calculada, área em ciano;

depois o perímetro extraído dessa área, em vermelho; os pixels comuns a dois caminhos de perímetros

que devem ser removidos, em verde; e a área do compartimento efetivamente apreciada, em ciano.

Fonte: Próprio

Com essas rotinas de ajuste implementadas, todos os compartimentos de teste e

de plantas reais que foram utilizados, tiveram uma aproximação do perímetro

satisfatoriamente calculada.

41

5.5 – Caminho

Feitos todos os ajustes necessários à lista de pontos do perímetro, ela é passada

adiante para a supracitada rotina de cálculo de caminho. Ela é indispensável, visto que

apesar de correta como um conjunto de pontos, a lista de perímetros ainda não se

encontra ordenada em uma forma relevante para o método de ajuste de polígonos. Os

pontos estão ordenados, basicamente, da mesma forma como foram lidos da matriz

imagem, em uma sucessão de linhas, aninhadas em uma sucessão de colunas. Cabe

então a esta sub-rotina ordená-los sequencialmente, seguindo um caminho fechado, de

forma que todos pontos consecutivos sejam vizinhos.

O primeiro caminho calculado deverá ser sempre o perímetro externo, e também

será o único se o compartimento não possuir furos. Para isso, basta partir de um ponto

sabidamente pertencente a esse caminho, como por exemplo um com ambos valores

mínimos ou máximos de coordenadas. Foi escolhida a primeira alternativa e dado que o

sistema de coordenadas da imagem tem sua origem no canto superior esquerdo,

crescente para a direita e para baixo, o algoritmo sempre partirá do ponto mais acima

dos pontos mais à esquerda existentes na lista.

A seguir, é preciso escolher o sentido de iteração por sobre o caminho. Este

poderia ser horário ou anti-horário. Sem qualquer restrição por parte da IDE que

impedisse qualquer uma das opções, foi arbitrado que o traçado do caminho seguiria no

sentido horário. A fig. 5.5.1 demonstra o objetivo do cálculo de caminho.

Figura 5.5.1 – Exemplo do objetivo do cálculo de caminho por sobre um perímetro externo. Nota-se que o

ponto de partida, em verde, não é o ponto mais acima na imagem, mas ainda é o mais acima daqueles

mais à esquerda.

Fonte: Próprio

42

É possível que existam segmentos diferentes de um mesmo perímetro ou de

perímetros diferentes, dispostos lado a lado e seguindo em direções opostas, sobre um

mapa de pontos. Para alcançar o objetivo de percorrer o caminho correto sobre tal mapa

foi necessário um árduo amadurecimento evolutivo do processo e, para a construção de

um algoritmo tido como ótimo para a tarefa, foram consideradas e testadas duas

premissas.

A primeira premissa do método é buscar o próximo pixel, em sucessão horária,

em todas as oito direções possíveis de progressão, a partir do pixel atual de iteração,

como ilustra a fig. 5.5.2. A busca tem início orientada para o ponto adjacente superior

direito do pixel inicial, visto que sabidamente não há pontos mais à esquerda ou

diretamente acima dele, dada a escolha de sua posição.

Figura 5.5.2 – Ordem de busca por pontos vizinhos.

Fonte: Próprio

Sempre que o ponto testado existir na lista do perímetro, ele é incluído na lista

ordenada, depois removido da lista não-ordenada e a variável de iteração assume suas as

coordenadas, efetivamente "andando" para o pixel vizinho. Se o ponto na direção

testada não existir, testa-se o da direção seguinte. Se todas as oito forem analisadas e

não for encontrado um ponto em nenhuma delas, um erro inesperado ocorreu, e para

evitar um loop infinito o algoritmo descarta esse ponto e tenta prosseguir do último

ponto já incluído na lista ordenada.

43

O algoritmo termina quando a variável de iteração alcança as coordenadas do

ponto inicial, o que indica que o caminho foi percorrido por completo, ou se todos os

pontos da lista ordenada forem removidos, o que seria o resultado de uma falha

inesperada e quaisquer pontos restantes na lista não-ordenada seriam descartados.

Essa primeira implementação seria capaz de ordenar os pontos da Fig. 5.5.1 da

forma desejada, entretanto todos os perímetros internos de compartimentos com furos

seriam descartados. Além disso, ela seria incapaz de ordenar corretamente

compartimentos com traçados que possuam segmentos adjacentes, gerando resultados

falhos no mínimo, e retornando uma lista vazia no pior caso. A fig. 5.5.3 ilustra essas

situações.

Figura 5.5.3 – Exemplos de traçados válidos e inválidos. À esquerda, o exemplo anterior, é traçado

corretamente pelo algoritmo. Ao centro, compartimento com exemplo de segmentos adjacentes que

causariam problemas ao algoritmo, em azul. À direita, perímetro interno descartado quando do término do

algoritmo, em azul.

Fonte: Próprio

Partindo desse algoritmo como base, analisando seus resultados sobre os

perímetros de compartimentos de vários formatos e, então, isolando as diversas

disposições de pontos que geravam erros, foi possível aprimorar o método à sua versão

final e garantir os resultados desejados, apenas incluindo uma segunda premissa.

Curiosamente, essa segunda premissa para conseguir percorrer um caminho

fechado com precisão, mantendo um determinado sentido, é sempre tentar seguir no

sentido contrário assim que um ponto vizinho for encontrado. Mais especificamente, no

caso da progressão em sentido horário, sempre que um ponto for encontrado em uma

determinada direção, o próximo ponto deverá ser procurado na direção perpendicular

àquela, no sentido anti-horário.

44

Então, se o algoritmo testar a direção para cima por exemplo, e encontrar um

ponto, o próximo deverá ser procurado à esquerda. Se o caminho seguir de fato para

cima, tal ponto não será encontrado à esquerda, nem à cima e esquerda, e dada a

primeira premissa, o algoritmo seguirá buscando até testar todas as direções possíveis.

A fig. 5.5.4 demonstra a busca de pontos e o traçado final de um trecho de perímetro no

qual o método falharia se utilizasse a primeira premissa apenas.

Visando garantir a conformidade da primeira premissa com a segunda, é

razoável alterar a direção inicial de busca para a esquerda.

Figura 5.5.4 – Trecho de perímetro, exemplo do algoritmo melhorado. Partindo do ponto em verde claro,

pretende-se chegar no ponto em ciano. As setas azuis são as primeiras direções testadas a partir de um

ponto, as verdes as segundas, laranjas são as terceiras e amarelas as quartas. As setas em preto são as

direções efetivamente seguidas, o trajeto correto.

Fonte: Próprio

O método pode ser descrito por completo pela máquina de estados da fig. 5.5.5.

Suas transições estão condicionadas à existência ou não de um ponto naquela direção.

45

Figura 5.5.5 – Máquina de estados de tomada de decisão para escolha do caminho sobre o perímetro.

Fonte: Próprio

Oferecendo uma analogia gráfica ao processo, seria como tentar seguir o

contorno interno de uma sala, com os olhos vendados. Como não é possível enxergar o

caminho adiante, para percorrê-lo no sentido horário e sempre junto às paredes, basta

seguir com a mão esquerda perpendicular à direção do movimento, tateando a parede.

Se em um determinado passo a parede "deixar de existir" será sabido que houve uma

curva à esquerda e que é necessário acompanhá-la nessa direção.

Agora, ao algoritmo resta apenas ser capaz de contemplar os perímetros internos

aos compartimentos mas, em primeiro lugar, é preciso saber como permitir um furo

dentro de um polígono. Na verdade, isso não é possível. A IDE PhAB não permite

retirar parte do interior de um polígono, ou desenhar outro por cima deste de forma a

marcar aquela região como vazia ou algo parecido. Para isso, será implementada a

mesma estratégia usada pelos programadores do SCAV quando realizando o processo

inserindo vértices individuais.

A abordagem consiste em ligar o perímetro externo ao interno por um único

caminho, cujos pontos serão percorridos duas vezes. Com isso cria-se, efetivamente,

uma concavidade degenerada (fig. 5.5.6), com seu interior fazendo parte do exterior do

compartimento mas com largura zero em sua "entrada". É importante salientar que os

caminhos internos devem ser mapeados no sentido contrário àquele do perímetro

externo, para garantir os resultados desejados.

46

Figura 5.5.6 – Exemplo do conceito de uma concavidade degenerada. Ponto de início da lista em verde,

área interna em ciano, pontos de perímetro em vermelho e pontos percorridos duas vezes em amarelo.

Fonte: Próprio

Portanto, o método de caminho deve ser alterado de forma a não mais terminar

quando encontrar o ponto inicial do perímetro externo, e sim continuar buscando

possíveis perímetros internos e os armazenando em listas independentes. Para que estes

sejam calculados no sentido correto, contrário ao externo, basta reverter as direções da

máquina de estados. A busca terminará quando não existirem mais pontos na lista não-

ordenada.

O próximo passo é inserir os pontos do(s) perímetro(s) interno(s) na lista do

externo. Essa sub-rotina começa procurando os dois pontos, um do perímetro interno e

um do externo, que sejam os mais próximos na direção vertical ou na horizontal (fig.

5.5.7). Desses dois, aquele que pertencer ao perímetro interno deve passar a ser o início

deste, portanto, sua lista precisa ser ajustada para prosseguir de acordo. Aquele do

perímetro externo determina onde todos os pontos devem ser inseridos nessa lista,

depois dele.

47

Figura 5.5.7 – Primeiro passo de inserção de perímetro interno. À esquerda, ambos os perímetros

exatamente como foram calculados. Em vermelho o perímetro externo, em azul o interno, os pontos

iniciais de ambas as listas em verde claro e a área interna do compartimento em ciano. À direita, o novo

ponto de início da lista interna e em verde escuro o ponto da lista externa depois do qual todos serão

inseridos.

Fonte: Próprio

É preciso agora preencher a distância entre os dois perímetros, incluindo na lista

todos os pontos no espaço entre esses dois pontos encontrados, formando um caminho

do externo para o interno. Depois são incluídos todos os pontos do perímetro interno. E

finalmente, todos os pontos que ligam as duas listas são inseridos novamente, formando

o caminho fechado. A figura 5.5.8 ilustra esses passos.

Figura 5.5.8 – Segundo passo de inserção de perímetro interno. À esquerda, pontos de ligação entre as

duas listas inseridos. Em vermelho o perímetro externo, em azul o interno, os pontos iniciais de ambas as

listas em verde claro e a área interna do compartimento em ciano. À direita, os pontos internos foram

incluídos na lista externa, em vermelho, e em amarelo os pontos que são percorridos duas vezes. Obteve-

se a concavidade degenerada desejada.

Fonte: Próprio

48

Ao término de sua inserção, o perímetro interno deixa de existir, já que todos

seus pontos passaram a fazer parte do externo. Se houver outra ou mais listas de pontos

que contornam um furo, basta executar o mesmo processo novamente até que por fim

restará uma única lista, com todos os pontos necessários para traçar corretamente o

polígono desse compartimento.

5.6 – Polígonos

Dada a lista de pontos ordenados produzida pelo algoritmo de caminhos, cabe a

esta sub-rotina construir um polígono que melhor os represente. Para isso, seus vértices

devem, obrigatoriamente, pertencer à lista de perímetro. Também é imperativo que as

arestas definidas se sobreponham a todos os pontos contidos entre os vértices, mas não

necessariamente somente a esses.

Apesar deste aluno ter encontrado uma publicação com um algoritmo que lidava

com um problema semelhante, esta foi considerada excessivamente complexa para este

problema, além de muito liberal na determinação do polígono. Este aluno então optou

por desenvolver sua própria abordagem.

Teoricamente, seria possível considerar cada ponto da lista de perímetro como

um vértice e assim construir um polígono extremamente grande porém ainda válido. No

entanto, com todos compartimentos possuindo ao menos algumas centenas de pontos de

perímetro e alguns se aproximando de um milhar deles, previu-se de ao menos uma

perda de performance para uma tela com polígonos gerados dessa forma, até uma falha

da IDE, como no caso dos retângulos. Assim como naquele, otimizações se fazem

necessárias.

Em primeiro lugar, para ser capaz de reduzir o número de vértices do polígono,

o método precisa ser capaz de determinar quais pontos representam um segmento que

ligue dois outros pontos quaisquer sobre um espaço bidimensional de coordenadas

discretas, no qual existem os pixels de uma imagem.

49

É perfeitamente plausível tratar esse espaço como contínuo, traçar uma reta com

suas extremidades nos centros dos pixels inicial e final, e então iterar ao longo do

segmento, determinando quais centros de coordenadas discretas mais se aproximam

dessa reta. Exemplificado na figura 5.6.1, esse é conhecido como o Algoritmo Ingênuo

de Desenho de Linha [15].

Figura 5.6.1 – Exemplo do traçado de linha pelo algoritmo ingênuo. As linhas em verde representam

distâncias menores da reta a um centro de "ponto", enquanto em vermelho, as distâncias maiores. Em

azul, os pontos que aproximam a reta no espaço discreto.

Fonte: Próprio

Entretanto, já existe há algum tempo um método muito mais eficiente.

O Algoritmo de Linhas de Bresenham [16][17][18], desenvolvido por Jack Elton

Bresenham em 1962 enquanto trabalhava na IBM, é capaz de resolver esse mesmo

problema, utilizando apenas estruturas de tomada de decisão, deslocamentos de bits e

aritmética simples com números inteiros, eliminando as custosas multiplicações e

divisões em ponto flutuante.

Desenvolvido em uma época em que os computadores tinham poder de

processamento extremamente limitado, o algoritmo fez parte do início da computação

gráfica. Apesar de menos favorecido atualmente frente às linhas mais suaves e

esteticamente agradáveis do algoritmo de Xiaolin Wu [19], fruto de seu uso de

antialiasing, pela sua simplicidade o algoritmo de Bresenham pode facilmente ser

encontrado em firmwares e hardwares de plotters e de placas gráficas modernas.

50

A idéia do método de Bresenham é de fácil compreensão. Por simplicidade o

algoritmo será demonstrado com uma reta situada no segundo octante de um sistema de

coordenadas cartesiano (fig. 5.6.2), mas com algumas poucas generalizações o

algoritmo torna-se capaz de traçar retas em qualquer octante. O sistema de coordenadas

é centrado no ponto (x0,y0) e é traçada uma reta deste até outro ponto (x1,y1), com

comprimento 'w' no eixo horizontal e altura 'h' no eixo vertical.

Figura 5.6.2 – Reta de exemplo do algoritmo de Bresenham no segundo octante.

Fonte: Próprio

Como em toda equação que define uma reta "y = a*x + b", o coeficiente angular

"a = h / w" determina de quanto 'y' é acrescido em função de um incremento em 'x'. O

que permitiu ao método de Bresenham sua eficiência, foi a concepção de que não é

preciso calcular, de fato, a divisão "h / w".

O algoritmo procede da seguinte forma: existe uma variável 'n' que armazena o

numerador da fração que define 'a', e é inicializada com metade do comprimento 'w',

pois assim como no algoritmo ingênuo, parte-se do centro do pixel. A cada iteração a

coordenada 'x' é incrementada de 1 unidade e 'n', de 'h' unidades. Sempre que a fração

"n / w" for maior ou igual a 1, ou seja, sempre que o numerador não for menor que 'w', é

subtraído dele o valor de 'w', efetivamente simplificando a fração, e 'y' é incrementado

de 1. O algoritmo termina quando atingir a coordenada 'x' do ponto final. Segue abaixo

o cálculo passo a passo de uma pequena reta de demonstração, na fig. 5.6.3.

51

Figura 5.6.3 – Pequena reta de exemplo, no segundo octante, e o passo a passo da execução do algoritmo.

Fonte: Próprio

De posse desse método eficiente de traço de retas, o algoritmo está apto a

prosseguir ao cálculo do polígono. Assim como ao problema de otimização dos

retângulos, este aluno tentou abordar este da forma mais direta e simples possível.

Como um polígono é definido por um conjunto de segmentos de retas unidos

dois a dois por suas extremidades em vértices e formando um caminho fechado, segue

que quão maiores suas arestas mais pontos cobrirão, sendo necessários menos vértices e

resultando em um polígono mais simples.

Mas o grande problema é conseguir encontrar as maiores arestas possíveis, de

forma eficiente, desconhecendo a geometria do polígono alvo. A primeira abordagem

implementada foi um método de busca exaustiva, favorecendo uma implementação

funcional a uma eficiente, inicialmente.

52

O método começa armazenando o ponto inicial da lista como primeiro vértice.

Partindo deste, o comprimento mínimo possível para uma reta (em pontos) seria 1, o

próprio ponto seguinte ao inicial. Obviamente, em um polígono plano, uma única aresta

não é capaz de conter todos os pontos do perímetro. Então o tamanho máximo possível

dessa reta seria metade do comprimento total do perímetro, considerando um polígono

degenerado em duas retas.

Tenta-se traçar uma aresta do ponto inicial até o ponto máximo. Aqueles que

compõem essa reta, obtidos pelo traçado com o algoritmo de Bresenham, são

comparados com todos os pontos contidos na lista entre o inicial e o máximo. Se ao

menos um ponto da lista não estiver contido na reta, esta não é uma aresta válida.

Nesse caso, sem enveredar para uma análise mais aprofundada da quantidade de

correlação entre pontos de reta e lista, sabe-se apenas que a maior aresta possível

partindo do vértice inicial tem tamanho menor que esse máximo calculado. Este é então

diminuído de uma unidade e o processo se repete até que o comprimento máximo seja

reduzido a um ponto, ou até ser localizada uma aresta válida.

Prosseguindo desta forma, assim que uma for encontrada, tem-se certeza de que

é a máxima possível dado seu ponto inicial. O algoritmo armazena como um novo

vértice esse segundo ponto que define a aresta, o toma como novo ponto de partida e

recomeça a busca por uma nova aresta. O processo todo se repete até percorrer a lista de

perímetro por completo (fig. 5.6.4).

Figura 5.6.4 – Exemplo de execução do algoritmo de ajuste de polígonos. Progredindo de cima para

baixo, da esquerda para a direita, em azul os pontos do perímetro. Em laranja, as retas sendo testadas; em

vermelho, pontos que não produzem arestas válidas; em verde, pontos que o fazem; em amarelo, arestas

válidas; e em preto, os vértices encontrados.

Fonte: Próprio

53

Esse processo pôde ser aprimorado quando da percepção de que se o

compartimento possuir concavidades ou furos, metade de seu perímetro é um valor

bastante super-estimado para o comprimento máximo de uma aresta, levando o

algoritmo a executar muitas iterações desnecessárias. Como é sabido, geometricamente,

que qualquer segmento reto do polígono deve, obrigatoriamente, estar contido no menor

retângulo que o circunscreve, um limite superior mais adequado para o comprimento

das arestas seria a diagonal desse retângulo.

Figura 5.6.5 – O compartimento de exemplo com um furo, possui 58 pontos de perímetro. À esquerda, em

vermelho, o ponto no comprimento máximo previamente calculado, 29 pontos. À direita, em vermelho, o

ponto no comprimento máximo com base no método aprimorado, 13 pontos. Em amarelo, os 16 pontos

"economizados", e em verde, o retângulo que circunscreve o perímetro.

Fonte: Próprio

Na esperança de tornar o processo mais eficiente, foi testada uma

implementação inspirada no método de busca binária, visando alcançar uma

complexidade de execução semelhante. Entretanto, quando posta à prova em perímetros

de compartimentos de teste, descobriu-se uma falha inerente a esse processo, que

impossibilitou seu uso. Como as coordenadas espaciais são discretas e os pontos das

retas de Bresenham são aproximações, essa abordagem com busca binária só

funcionaria corretamente em perímetros compostos apenas por arestas paralelas aos

eixos ortogonais ou às bissetrizes de seus quadrantes. Esse, obviamente, não é o caso

com compartimentos da planta de um navio.

Pelo mesmo motivo, não é possível fazer uma busca progressiva a partir do

ponto inicial, pois pode-se encontrar uma aresta válida que não seja a máxima.

54

Capítulo 6

Software

O último passo do projeto foi desenvolver uma interface gráfica amigável para o

programa, que permitisse ao programador do SCAV utilizar esses processos e sub-

rotinas de forma eficiente e transparente. O software foi estruturado de forma

minimalista, se atendo ao princípio de quão mais simples, melhor.

Quando da sua inicialização, a janela de abertura de projeto permite a escolha da

pasta de trabalho do projeto, e dentro dessa são sugeridos dois arquivos de entrada de

dados, se presentes (fig. 6.1).

O primeiro é o arquivo de código fonte da tela de avarias, gerado na IDE PhAB,

"base.wgtw", de onde serão lidas as imagens das plantas baixas a serem processadas;

que contém os retângulos e polígonos possivelmente já cadastrados; e onde serão

inseridos os objetos desses mesmos tipos, calculados para outros compartimentos.

O segundo é o arquivo do banco de dados do projeto, "scm.dat", no padrão do

SGBD SQLite, que contém os nomes e descrições de todos os compartimentos passíveis

de serem cadastrados.

Se não existirem arquivos com esses nomes, os primeiros encontrados que

possuírem as extensões corretas serão sugeridos. É possível escolher arquivos diferentes

dos indicados, se desejado, mas a existência dos dois é obrigatória.

Figura 6.1 – Janela de abertura de projeto, no SAP CAV.

Fonte: Próprio

55

Parte dos dados de saída do programa são inseridos no próprio arquivo de

código fonte "base.wgtw", especificamente as declarações dos polígonos e retângulos,

com todos seus atributos. Além de editar esse, são criados mais três arquivos com

código fonte na linguagem C ANSI (fig. 6.2).

O mais importante deles, denominado "carrega_id_comp.h", contém o

armazenamento em uma lista dos códigos de local dos compartimentos do navio. A

indexação da lista garante a crucial associação entre seus dados e os objetos de tipo

polígono, atributo que efetivamente transforma um objeto na tela em um compartimento

do navio.

Os outros dois arquivos contém o carregamento de listas com todos os nomes

dos polígonos e dos retângulos, permitindo o acesso de forma seqüencial, em tempo de

execução. Os arquivos são o "comp_cor.h" e o "comp_call.h", respectivamente. A lista

de polígonos está indexada na mesma ordem da lista no arquivo "carrega_id_comp.h".

Como cada compartimento possui um ou mais retângulos associados, a nomenclatura

desses começa com o nome do polígono do compartimento, acrescido de uma ou mais

letras e em ordem alfabética, para tornar cada nome único.

Figura 6.2 – Trechos de exemplo de arquivos de saída do software.

Fonte: Próprio

56

Para tornar mais eficientes o acompanhamento, combate e reparos de avarias a

bordo, praticamente todos os navios da MB são sub-divididos em duas ou mais regiões,

chamadas de Reparos, de responsabilidade de diferentes equipes.

O SCAV, além de exibir a planta completa com essas regiões delimitadas,

permite também a visualização individual e aumentada de cada uma delas. Ademais, o

sistema possui uma funcionalidade de visão noturna, na qual as cores de objetos e

imagens são alteradas de modo a reduzir o brilho total emitido pelas telas do sistema.

Assim, à noite, a iluminação gerada por um console no passadiço de um navio não

aumentaria o risco de detecção deste por outros navios.

Considerando isso, sabe-se então que a quantidade de imagens no código fonte

vindo do QNX será duas vezes o número de reparos existentes, mais duas, as imagens

da planta completa em ambos os modos de iluminação. O software busca no banco de

dados a quantidade de reparos desse navio, acrescenta um, e carrega todos os nomes de

imagens válidas encontradas, solicitando a escolha do operador de quais serão utilizadas

(fig. 6.3).

Figura 6.3 – Janela de carga de imagens do sistema.

Fonte: Próprio

Assim que as imagens desejadas são selecionadas e carregadas, são abertas as

principais janelas do programa, as interfaces de posicionamento dos compartimentos. À

direita são exibidos um campo de busca e uma lista com todos os compartimentos

pertinentes àquele reparo, ou todos, na janela da Vista Geral (fig. 6.4). A lista é filtrada

automaticamente quando preenchido o campo de busca. Pelo nível de sigilo das

informações do projeto, os nomes dos compartimentos nas áreas abaixo foram

mascarados.

57

Figura 6.4 – Janela da vista geral e demais reparos do navio, carregadas.

Fonte: Próprio

Cada ícone de mira desenhado sobre a imagem representa um compartimento no

banco de dados. Sempre que um compartimento for selecionado na lista, um marcador

indicará qual é o seu ícone sobre a tela (fig. 6.5).

Figura 6.5 – Compartimentos filtrados e um deles selecionado.

Fonte: Próprio

58

Sempre que o cursor do mouse for passado sobre um ícone, ou enquanto este for

arrastado, será exibida uma etiqueta com o nome de seu compartimento (fig. 6.6). Para

associar um compartimento a uma região fechada da imagem e gerar seu polígono e

seus retângulos, basta arrastar seu ícone para dentro dela (fig. 6.7).

Figura 6.6 – Arrastando ícone do compartimento para sua posição correta.

Fonte: Próprio

Figura 6.7 – Compartimento calculado.

Fonte: Próprio

59

Assim, resta ao usuário apenas posicionar as centenas de marcadores de

compartimentos em suas respectivas regiões por cima da planta da vista geral do navio e

dos diversos reparos, e não mais desenhar cada objeto de cada compartimento.

60

Capítulo 7

Conclusões

Sucesso. As formatações de arquivo, métodos e algoritmos, analisados e

implementados nos capítulos anteriores, alcançaram seus objetivos de projeto e juntos

formam o núcleo do Software de Auxílio ao Programador proposto.

Este por sua vez, apesar de minimalista e de não ter seguido rigorosamente

métricas de engenharia de software em seu desenvolvimento, foi muito bem aceito pela

equipe de programadores do SCAV. Em aplicações reais, um desses programadores

precisou de dois dias, em média, para realizar todo o mapeamento de uma nova janela

de controle de avarias, um dia além do proposto, mas ainda assim apenas uma fração do

tempo original de um mês.

Com base nessa redução no tempo de desenvolvimento, já foi cogitada pela

gerência dos projetos a possibilidade de implementação em vários novos navios, quando

antes não seria possível, dadas as limitações de tempo e pessoal.

Os desafios enfrentados durante a realização desse projeto proporcionaram a

este aluno um melhor entendimento de algumas técnicas de processamento de imagens,

bem como um apreço maior pela necessidade de iniciativa na implementação de

soluções não convencionais para problemas tidos como dificuldades intrínsecas de um

projeto.

Pretende-se dar continuidade ao desenvolvimento do software, visando torná-lo

mais robusto e acrescentando quaisquer funcionalidades que possam reduzir ainda mais

o tempo despendido em programação, por projeto.

61

Bibliografia

[1] “SQLite Home Page”, http://www.sqlite.org/, 2014, (Acesso em 16 Janeiro 2014). [2] “QNX Neutrino RTOS”, http://www.qnx.com/products/neutrino-rtos/neutrino-

rtos.html#overview, 2014, (Acesso em 16 Janeiro 2014). [3] “QNX Neutrino RTOS”, http://www.qnx.com/products/neutrino-rtos/neutrino-

rtos.html#technology-realtime, 2014, (Acesso em 16 Janeiro 2014). [4] “QNX Neutrino RTOS”, http://www.qnx.com/products/neutrino-rtos/neutrino-

rtos.html#benefits, 2014, (Acesso em 16 Janeiro 2014). [5] “BT.601 : Studio encoding parameters of digital television for standard 4:3 and wide

screen 16:9 aspect ratios”, http://www.itu.int/rec/R-REC-BT.601/en, 2014, (Acesso em 12 Fevereiro 2014).

[6] “BT.709 : Parameter values for the HDTV standards for production and

international programme exchange”, http://www.itu.int/rec/R-REC-BT.709/en, 2014, (Acesso em 12 Fevereiro 2014).

[7] SEZGIN, SANKUR, “Survey over image thresholding techniques and quantitative

performance evaluation”, Journal of Electronic Imaging 13(1), pp. 146-165, 2004. [8] NOBUYUKI OTSU, “A threshold selection method from gray-level histograms”,

IEEE Trans. Sys., Man., Cyber. 9(1), pp. 62–66, 1979. [9] “Otsu's method - Wikipedia, the free encyclopedia”,

http://en.wikipedia.org/wiki/Otsu's_method, 2014, (Acesso em 5 Março 2014). [10] “Otsu Thresholding - The Lab Book Pages”,

http://www.labbookpages.co.uk/software/imgProc/otsuThreshold.html, 2014, (Acesso em 5 Março 2014).

[11] “Flood Fill - Wikipedia, the free encyclopedia”,

http://en.wikipedia.org/wiki/Flood_fill, 2014, (Acesso em 8 Março 2014). [12] FRANZBLAU, D., KLEITMAN, D., “An Algorithm for Covering Polygons

with Rectangles”, Information and Control 63, pp. 164–189, 1984. [13] “NP-hard - Wikipedia, the free encyclopedia”, http://en.wikipedia.org/wiki/NP-

hard, 2014, (Acesso em 5 Junho 2014). [14] “ELEN 4304/5365 - Digital Image Processing”, http://ee.lamar.edu/gleb/dip/10-

2%20-%20Morphological%20Image%20Processing.pdf, 2014, (Acesso em 10 Junho 2014).

62

[15] “Line drawing algorithm - Wikipedia, the free encyclopedia”, http://en.wikipedia.org/wiki/Line_drawing_algorithm, 2014, (Acesso em 15 Junho 2014).

[16] BRESENHAM, J. E., “Algorithm for computer control of a digital plotter”, IBM

Systems Journal 4(1), pp. 25–30, 1965. [17] “Bresenham's line algorithm - Wikipedia, the free encyclopedia”,

http://en.wikipedia.org/wiki/Bresenham's_line_algorithm, 2014, (Acesso em 28 Junho 2014).

[18] “The Bresenham Line-Drawing Algorithm”,

http://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html, 2014, (Acesso em 28 Junho 2014).

[19] “Xiaolin Wu's line algorithm - Wikipedia, the free encyclopedia”,

http://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm, 2014, (Acesso em 29 Junho 2014).