CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS

CURSO DE ENGENHARIA ELÉTRICA

MÉTODOS DE PROCESSAMENTO DE

IMAGENS PARA VISÃO COMPUTACIONAL NO

CUBO DE RUBIK

DANIEL LETO NEIVA COSTA

Orientador: Giovani Guimarães Rodrigues

Centro Federal de Educação Tecnológica de Minas Gerais

Coorientador: Túlio Charles de Oliveira Carvalho

Centro Federal de Educação Tecnológica de Minas Gerais

BELO HORIZONTE

DEZEMBRO DE 2015

DANIEL LETO NEIVA COSTA

MÉTODOS DE PROCESSAMENTO DE IMAGENS PARA

VISÃO COMPUTACIONAL NO CUBO DE RUBIK

Trabalho de Conclusão de Curso apresentado ao Cursode Engenharia Elétrica do Centro Federal de EducaçãoTecnológica de Minas Gerais, como requisito parcial para aobtenção do título de Bacharel em Engenharia Elétrica.

Orientador: Giovani Guimarães RodriguesCentro Federal de Educação Tecnológica deMinas Gerais

Coorientador: Túlio Charles de Oliveira CarvalhoCentro Federal de Educação Tecnológica deMinas Gerais

CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DE MINAS GERAIS

CURSO DE ENGENHARIA ELÉTRICA

BELO HORIZONTE

DEZEMBRO DE 2015

ii

Esta folha deverá ser substituída pela có-pia digitalizada da folha de aprovação for-necida pelo DEE

iii

Agradecimentos

São muitas as pessoas e entidades que contribuíram para que este trabalho, bem como

todo o processo de minha graduação fossem finalizados.

Agradeço ao Centro Federal de Educação Tecnológica de Minas Gerais, pela minha

educação acadêmica. Explicitamente, ao Governo Federal, por prover ensino público

superior de qualidade.

Agradeço ao meu orientador, Prof. Dr. Giovani Guimarães, pela paciência e dedicação,

assim como a compreensão em momentos difíceis.

Agradeço aos meus co-orientadores, Prof. Dr. Túlio Charles e Prof. Joel Augusto, pela ajuda

na conclusão deste trabalho.

Agradeço ao Conselho Nacional de Desenvolvimento Científico e Tecnológico pelo fomento

financeiro à minha mobilidade acadêmica no Canadá, a qual acrescentou muito na minha

formação.

A special thanks to the University of Guelph, who welcomed me with arms wide open and

contributed to my academic formation. Also, thank you Professor Bob Dony, PhD, Professor

Michele Oliver, PhD, and Greg Scott, for mentoring me and supporting me in my experience

through academic research.

Agradeço à minha mãe, Silene, mulher de aço, que mesmo em tempos difíceis nunca

desistiu nem transpareceu fraqueza, muitas vezes apoiando seus filhos em contraste a si

mesma.

Agradeço à minha tia, Patrícia, por me ensinar a perdoar e por me mostrar que a humildade

e o altruísmo são reais.

Agradeço ao meu irmão, Rafael, por ser sempre um companheiro leal e me fazer rir a todo

momento.

Agradeço à minha namorada, Laís, por ser sempre um suporte emocional e minha compa-

nheira, sempre me provando que o amor existe.

Agradeço à minha família, por ser sempre presente.

Agradeço aos meus amigos do Brasil, por fazerem dos últimos 6 anos os melhores da minha

vida. Aos meus amigos de Guelph, por fazer da minha estadia uma lembrança eterna e boa.

iv

E a todos que não estão aqui explícitos, saibam que recordo-me bem de todas as pessoas

boas que partilharam minha vida acadêmica.

v

“Sometimes, in order to see the light, you have

to risk the dark.” (Dr Iris Hineman, Minority

Report)

vi

Resumo

O propósito deste trabalho é analisar técnicas de processamento de imagens em eletrônica

digital. O método envolve estudo de formatos gráficos eficientes em tamanho e facilidade de

processamento, além de técnicas de segmentação fotográfica, com análises de histograma.

O foco do trabalho é a imagem de um Cubo de Rubik.

Outrossim, é apresentada neste trabalho uma descrição de codificação e manipulação de

imagens digitais, além de uma revisão sobre seus algoritmos de processamento, utilizando

segmentação por k-médias e características SURF.

A avaliação técnica do problema é feita considerando uma implementação em um sistema de

baixo custo, utilizando-se do ambiente MATLAB para realizar uma simulação da execução

da solução. Também são estudadas técnicas de processamento de imagens utilizando

segmentação por k-médias e comparação de características SURF para identificação do

Cubo. Os resultados das simulações da prática real também estão inclusos neste trabalho.

Palavras-chave: Processamento de imagens. Cubo de Rubik. Visão Computacional. Algo-

ritmos de segmentação. Reconhecimento de cores. Características SURF.

vii

Abstract

The main purpose of this essay is to analyze image processing techniques in digital systems.

The method contains a study of efficient graphic formats in size and complexity of processing,

besides photographic segmentation techniques, with histogram analysis. The essence of

this work is the Computer Vision of a Rubik’s Cube.

Nonetheless, a codification and manipulation of digital images revision is present, besides a

review about processing algorithms using k-means and SURF features.

The technical evaluation of the problem is done considering the implementation in a low cost

system, using MATLAB environment to perform a simulation of the execution of the solution.

Also, image processing techniques are studied with the help of kmeans segmentation and

SURF features matching for the Cube identification. The simulation results are also included.

Keywords: Image Processing. Rubik’s Cube. Computer Vision. Segmentation algorithms.

Color recognition. SURF Features.

viii

Lista de Figuras

Figura 1.1 – Cubo de Rubik 3x3. Fonte: (RUBIKS.COM, 2015) . . . . . . . . . . . . . 2

Figura 2.1 – Extração do Cubo de Rubik de uma fotografia digital. Fonte: (KASPRZAK;

SZYNKIEWICZ; CZAJKA, 2006) . . . . . . . . . . . . . . . . . . . . . . 6

Figura 2.2 – Processo de localização e detecção do Cubo de Rubik por Redes Neurais

Convolucionais. Fonte: (HACK; SHUTZBERG, 2015) . . . . . . . . . . . 7

Figura 2.3 – Processo de detecção do Cubo com foco em sua geometria. Fonte:

(KASPRZAK; SZYNKIEWICZ; CZAJKA, 2006) . . . . . . . . . . . . . . 7

Figura 3.1 – Representação matricial de uma imagem digital. Fonte: (GONZALEZ;

WOODS, 2002, p.55) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Figura 3.2 – Quantização de uma imagem digital em diferentes resoluções. Fonte:

(GONZALEZ; WOODS, 2002, p.55) . . . . . . . . . . . . . . . . . . . . 11

Figura 3.3 – Uma fotografia e sua transformada de Fourier Bidimensional. Fonte:

(PRATT, 2007, p.197) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

Figura 3.4 – Representação em diagrama de Venn do Modelo Aditivo Tricromático

RGB. Fonte: (KOSCHAN; ABIDI, 2008, p.28) . . . . . . . . . . . . . . . 13

Figura 3.5 – Representação do Modelo Subtrativo de Cores CMYK. Fonte: (KOS-

CHAN; ABIDI, 2008, p.28) . . . . . . . . . . . . . . . . . . . . . . . . . 13

Figura 3.6 – Representação matricial para o modelo RGB. Fonte: (JÄHNE, 2005) . . 15

Figura 3.7 – Cubo de cores na base RGB sobreposta à XYZ. Fonte: (HOFFMANN,

2007b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

Figura 3.8 – Seção transversal do cubo RGB no plano XYZ (Diagrama de ferradura).

Fonte: (HOFFMANN, 2007b) . . . . . . . . . . . . . . . . . . . . . . . . 16

Figura 3.9 – Representação em cores do Espaço de Cores CIE 1931. Fonte: (HOFF-

MANN, 2007b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Figura 3.10–Representação em cores do Espaço de Cores CIE LAB. Fonte: (HOFF-

MANN, 2007a) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Figura 3.11–Histograma RGB de uma imagem digital . . . . . . . . . . . . . . . . . 20

Figura 3.12–Histograma em escala de cinza de uma imagem digital . . . . . . . . . . 20

Figura 4.1 – Janela 3x3 pixels que representa um filtro discreto bidimensional (JÄHNE,

2005) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Figura 4.2 – À esquerda, a imagem original. À direita, com um filtro passa-baixas no

domínio da frequência. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

Figura 4.3 – Respostas em frequência do filtro passa-baixas HD e seu filtro inverso

HR (PRATT, 2007). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Figura 4.4 – Modelo de filtragem inversa. . . . . . . . . . . . . . . . . . . . . . . . . 25

ix

Figura 4.5 – Respostas típicas do Filtro Bidimensional de Wiener para o eixo x (PRATT,

2007). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

Figura 4.6 – À esquerda, a imagem original. À direita, a imagem corrompida com ruído

gaussiano. Abaixo, a reconstrução utilizando-se um Filtro Bidimensional

de Wiener . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Figura 4.7 – Correção de iluminação em uma fotografia ao pôr do Sol. À esquerda, a

imagem sem tratamento. À direita, a imagem com correção de iluminação. 28

Figura 4.8 – À esquerda, o histograma de uma fotografia. À direita, o mesmo histo-

grama equalizado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

Figura 4.9 – Imagem digital e sua versão com histograma equalizado. . . . . . . . . 29

Figura 4.10–Detecção de Pontos de Interesse para Características SURF (MATHWORKS,

2015b) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Figura 4.11–Histograma espacial do gradiente da imagem (SIFT)(VEDALDI, 2013) . 31

Figura 4.12–Classificação de dados para k=3. Fonte: (PRATT, 2007) . . . . . . . . . 32

Figura 5.1 – Benchmarking do algoritmo SURF sem pré-processamento. . . . . . . . 36

Figura 5.2 – Comparação com fundo fora de foco, imagem sem pré-processamento. . 36

Figura 5.3 – Comparação mal sucedida, imagem sem pré-processamento. . . . . . . 36

Figura 5.4 – Extração sem pré-processamento, comparação errônea com outliers . . 37

Figura 5.5 – Tratamento das imagens no primeiro caso. . . . . . . . . . . . . . . . . 38

Figura 5.6 – Tratamento das imagens no segundo caso. . . . . . . . . . . . . . . . . 38

Figura 5.7 – Tratamento das imagens no terceiro caso. . . . . . . . . . . . . . . . . . 38

Figura 5.8 – Tratamento das imagens no quarto caso. . . . . . . . . . . . . . . . . . 39

Figura 5.9 – Benchmarking com pré-processamento. . . . . . . . . . . . . . . . . . . 39

Figura 5.10–Comparação com fundo fora de foco utilizando pré-processamento. . . . 40

Figura 5.11–Comparação do terceiro caso utilizando pré-processamento. . . . . . . 40

Figura 5.12–Último caso utilizando-se pré-processamento. . . . . . . . . . . . . . . . 40

Figura 5.13–Resultados para isolação utilizando classificação estatística pelas k-médias 42

Figura 5.14–Resultados para distorção gaussiana de 2 pixels . . . . . . . . . . . . . 42

Figura 5.15–Resultados para distorção gaussiana de 4 pixels . . . . . . . . . . . . . 43

Figura 5.16–Resultados para 20% de ruído gaussiano . . . . . . . . . . . . . . . . . 44

Figura 5.17–Resultados para 50% de ruído gaussiano . . . . . . . . . . . . . . . . . 45

Figura 5.18–Resultados para 20% de ruído gaussiano . . . . . . . . . . . . . . . . . 45

Figura 5.19–Localização do Cubo sem pré-processamento . . . . . . . . . . . . . . 46

Figura 5.20–Localização do Cubo sem pré-processamento . . . . . . . . . . . . . . 47

Figura 5.21–Resultados para uma imagem real do cubo . . . . . . . . . . . . . . . . 47

x

Lista de Abreviaturas e Siglas

ABNT Associação Brasileira de Normas Técnicas

API Algoritmo de processamento de imagens

CIE Comission Internationale de l’Eclairage

CIELAB Espaço de Cores L∗a∗b∗

CIEXYZ Espaço de Cores XY Z

CMOS Complementary Metal Oxide Semi-conductor

CMYK Padrão de cores Cyan, Magenta, Yellow

FCM C-médias Fuzzy

FFT Transformada Rápida de Fourier

HOG Histograma de Gradientes Orientados

RGB Padrão de cores Red, Green, Blue

RNC Rede Neural Convolucional

SIFT Scale Invariant Feature Transform

SURF Speeded-up Robust Features

SVH Sistema Visual Humano

ULA Unidade Lógico-Aritmética

VC Visão Computacional

xi

Sumário

1 – Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 O Cubo de Rubik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Objetivos do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Apresentação do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 – Um estudo geral sobre o problema . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1 Principais aplicações do tema . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Identificando o cubo em uma imagem . . . . . . . . . . . . . . . . . . . . . 6

2.3 Identificando características do Cubo . . . . . . . . . . . . . . . . . . . . . 8

2.4 Termos comuns neste trabalho . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.5 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 – Codificação e Manipulação de Imagens Digitais . . . . . . . . . . . . . . . . . 10

3.1 A representação matricial de imagens digitais . . . . . . . . . . . . . . . . . 10

3.2 Os Modelos de Cores Aditivos e Subtrativos . . . . . . . . . . . . . . . . . 12

3.3 Os Espaços de Cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.3.1 O Espaço RGB (Red-Green-Blue) . . . . . . . . . . . . . . . . . . . 14

3.3.2 O Espaço CIE-XYZ . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.3.3 O Espaço CIE-LAB . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.4 Os histogramas de imagens . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.5 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 – Algoritmos Básicos para Processamento de Imagens Digitais . . . . . . . . 22

4.1 A aquisição de imagens digitais . . . . . . . . . . . . . . . . . . . . . . . . 22

4.1.1 Os problemas comuns a câmeras digitais . . . . . . . . . . . . . . . 22

4.2 Os filtros espaciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4.2.1 Os filtros discretos bidimensionais . . . . . . . . . . . . . . . . . . . 23

4.2.2 O Filtro Bidimensional de Wiener . . . . . . . . . . . . . . . . . . . 24

4.3 A extração de características . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.3.1 O uso de pré-processamento para extração de características . . . 27

4.3.1.1 A melhoria de contraste . . . . . . . . . . . . . . . . . . . 28

4.3.1.2 Alisamento por filtragem . . . . . . . . . . . . . . . . . . . 29

4.3.2 As Características SURF . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3.3 A luminosidade e o ambiente controlado . . . . . . . . . . . . . . . 31

4.4 A classificação estatística das cores pelo método das k-médias . . . . . . . 32

4.5 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

xii

5 – Resultados Aplicados ao Cubo de Rubik . . . . . . . . . . . . . . . . . . . . . 34

5.1 A localização do Cubo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.1.1 O roteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.1.2 A extração sem pré-processamento . . . . . . . . . . . . . . . . . . 35

5.1.3 A extração com pré-processamento . . . . . . . . . . . . . . . . . . 37

5.1.3.1 A comparação entre as imagens sem e com pré-processamento 37

5.1.3.2 Os resultados com pré-processamento . . . . . . . . . . . 38

5.2 A classificação do Cubo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2.1 O caso ideal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2.2 Distorção gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2.3 Adição de ruído . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.2.4 Distorção gaussiana e adição de ruído . . . . . . . . . . . . . . . . 44

5.3 Uma simulação em ambiente real . . . . . . . . . . . . . . . . . . . . . . . 46

5.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6 – Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.1 Conclusões sobre o Cubo de Rubik e Visão Computacional . . . . . . . . . 49

6.2 Conclusões sobre os resultados . . . . . . . . . . . . . . . . . . . . . . . . 50

6.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

xiii

Capítulo 1

Introdução

Visão computacional é um assunto cada vez mais discutido em ambientes de engenharia

nos dias atuais. Foi descoberta como um novo campo da inteligência artificial, centrada em

estudos teóricos de processamento visual de imagens (POGGIO; TORRE; KOCH, 1989).

Seus principais objetivos são: 1) compreender melhor e mais aprofundado o sistema de

visão humana (SVH); e 2) construir e interpretar automaticamente cenas visuais através de

um computador.

O objetivo deste trabalho acadêmico de graduação é entender e aplicar o conceito de visão

computacional a um problema em específico, que são a identificação e a localização do

objeto em uma imagem digital.

1.1 O Cubo de Rubik

Um dos passatempos mais tradicionais de todos os tempos é sem dúvida o Cubo de Rubik1

(RUBIKS.COM, 2015). Criado por Ernõ Rubik em 1974(RUBIKS.COM, 2015), o quebra-

cabeças consiste em uma construção plástica giratória de 3 eixos na horizontal e na vertical,

podendo ser estendida indefinidamente, a custo de aumentar a dificuldade de resolução. A

Figura apresenta uma versão de três lados do cubo mágico.

Inicialmente, as faces são pintadas de cores distintas, então embaralhadas, compondo a

situação inicial do cubo. Então o jogador deve rodar os eixos até que todas as faces tenham

a mesma cor. Não fica difícil, portanto, verificar que existem vários algoritmos de resolução

do problema. A resolução do Cubo em si, não obstante, foge ao escopo deste trabalho.

É natural que haja, portanto, uma necessidade de abordagem computacional para implemen-

tar partes do problema, tanto para criação de softwares que auxiliem no desenvolvimento

de funções cognitivo motoras - por exemplo, melhorar competências, identificar lacunas de

1também conhecido como cubo mágico

1

Figura 1.1 – Cubo de Rubik 3x3. Fonte: (RUBIKS.COM, 2015)

performance e melhorar currículo educacional em crianças (YAGER; LOK; KLIG, 2011) -

para indivíduos que têm interesse no cubo, tanto para uso em testes de desempenho em

sistemas robóticos com visão computacional (HU et al., 2011). Neste último, há um interesse

especial, dado o nível de precisão requerido para a resolução do problema - rotação das

faces, segurança para evitar a quebra do cubo por rotações indevidas, processamento de

imagens coloridas em tempo real -. Isso faz com que softwares deste tipo sejam amplamente

utilizados para testar a performance de robôs existentes no mercado.

Como em qualquer problema de Engenharia, os algoritmos de visão computacional devem

ser adaptados de acordo com a demanda do problema. Em outras palavras, variam de

acordo com a robustez necessária para resolvê-lo, o que leva a uma série de axiomas:

precisão do projeto, eliminação de ruído, velocidade necessária, custo do projeto. Fica fácil

entender, portanto, que não se pode priorizar todos os elementos sem perder em algum, e é

por isso que algoritmos de visão computacional são cada vez mais estudados na atualidade.

O Cubo de Rubik é um objeto de estudo comum para o problema, e está emergindo cada

vez mais como uma tarefa comum para visão computacional. Explica isso o fato de ter

características de cor muito bem definidas, bem como suas bordas e propriedades geomé-

tricas (HACK; SHUTZBERG, 2015). Além disto, concentra uma gama de características

da imagem muito bem definidas, servindo constantemente como teste de performance em

sistemas de visão computacional.

Especificamente, o Cubo de Rubik tem as características fundamentais para uma compara-

ção eficiente entre diversas técnicas de VC, uma vez que engloba aspectos de diferentes

concentrações dentro do tema Visão Computacional. Desta maneira, utilizando-se dos

2

estudos já realizados na área, pode-se avaliar quais são as melhores alternativas para a

construção de sistema robótico para resolver o passatempo.

1.2 Objetivos do trabalho

Os principais objetivos deste trabalho são estudar as técnicas de visão computacional,

simulando de maneira prática a solução. A sua implementação depende de uma avaliação

sistemática de quão complexo é o problema, de modo que a solução tenha um custo-

benefício de performance. Podem ser inclusas, dentre outras: 1) o que é mais importante,

velocidade, ou qualidade? 2) qual é o sistema utilizado para a execução do algoritmo? 3) o

sistema deve rodar com o mínimo possível de recursos?

Realizadas as simulações e analisados os resultados, este estudo servirá de base para

futuras análises e implementações de processamento de imagens aplicado ao Cubo de

Rubik, extensível para imagens de maneira geral.

A metodologia deste trabalho é bem clara, seguindo o conceito epistemológico científico,

confiando em dados concretos do sistema, partindo do pressuposto de que os mesmos são

verdadeiros.

Em primeira instância, é realizada uma leitura geral sobre estudos já realizados com esta

aplicação específica, juntamente com o apoio de livros didáticos sobre processamento

de imagens. Então é realizada uma análise sistemática dos métodos de processamento

existentes, avaliando qual o melhor meio para se resolver o problema.

Com o parecer teórico em mãos, é feita uma implementação simulada em ambiente MATLAB,

utilizando ferramentas do software, mais especificamente, dos seus toolbox de VIsão

Computacional, Processamento de Imagens e Redes Neurais. Os resultados são então

analisados, levando-se em conta tempo de execução e qualidade dos resultados.

1.3 Apresentação do trabalho

Este trabalho é dividido em 6 capítulos. Esta introdução, apresentada no capítulo 1, dá uma

visão geral sobre a natureza do trabalho, juntamente com as motivações para se estudar

técnicas de processamento de imagens para visão computacional aplicados à resolução do

Cubo de Rubik.

O capítulo 2 traz uma revisão bibliográfica dos métodos de visão computacional e reco-

nhecimento de padrões em imagens digitais, classificação e segmentação estatísticas já

pesquisados e implementados. Não somente, uma revisão de compressão e processa-

3

mento de imagens também é apresentada, de modo a verificar as melhores alternativas

para implementação dos algoritmos.

Uma avaliação sistemática de métodos de codificação de imagens digitais é ilustrada no

capítulo 3.

Os modelos e técnicas de processamento avaliados no capítulo 2 são mostrados de uma

maneira mais aprofundada no capítulo 4, de modo a preparar a implementação do sistema

em ambiente MATLAB de maneira direcionada. Buscas por algoritmos já implementados

são também realizadas e apresentadas no mesmo capítulo. Os modelos de cor utilizados

também são discutidos.

A implementação do sistema obtido é apresentada no capítulo 5. Este se dedica, em sua

maior parte, a testar a eficiência dos algoritmos implementados para o problema específico.

Finalmente, os resultados das técnicas utilizadas são apresentados, juntamente com as

suas respectivas análises.

As conclusões obtidas do estudo, juntamente com sugestões de trabalhos futuros, são

descritas no último capítulo deste trabalho - capítulo 6.

4

Capítulo 2

Um estudo geral sobre o problema

Métodos de visão computacional aplicados ao Cubo de Rubik são muito estudados em

ambiente acadêmico nos dias atuais, por motivos que vão desde extração de características

no domínio da frequência até métodos de reconhecimento automático do cubo. Dentro dos

objetivos deste trabalho, é necessário segmentar imagens de acordo com as cores do cubo,

além de identificá-lo automaticamente por uma câmera instalada no robô.

2.1 Principais aplicações do tema

Como já citado na seção 1, existe um interesse grande no estudo de visão computacional

aplicada ao Cubo Mágico. Este campo está crescendo cada vez mais, uma vez que as

suas características geométricas são muito bem definidas, formando, portanto, bordas na

imagem. Desta maneira, uma segmentação eficiente conseguirá determinar com precisão

os pontos de extração (HACK; SHUTZBERG, 2015). Não obstante, o fato do passatempo ter

uma organização fractal - um objeto maior constituído de conjuntos de menores do mesmo

formato, faces e facetas - também facilita em processos de erosão e dilatação de imagens,

facilitando uma eventual identificação em três dimensões do objeto. A Figura 2.1 representa

a extração do puzzle da imagem digital.

Junto com as suas características geométricas, suas características também são muito

bem definidas no domínio da frequência. Justifica isso o fato de que cada faceta - menor

elemento de uma face do cubo - apresenta apenas um elemento de cor, levando a uma

interpretação constante por área, o que também facilita a análise por superpixels, obtendo

uma resposta muito rápida.

As aplicações, portanto, são inúmeras: dentro de um mesmo problema, podem-se identificar

diversos estudos de visão computacional dentro do mesmo tema, fazendo-se valer diferentes

interpretações. Isto facilita a comparação entre duas ou mais técnicas quanto a custo e

performance.

5

Figura 2.1 – Extração do Cubo de Rubik de uma fotografia digital. Fonte: (KASPRZAK;SZYNKIEWICZ; CZAJKA, 2006)

2.2 Identificando o cubo em uma imagem

O processo de identificar o objeto dentro de uma imagem pode ser complicado, dependendo

da abordagem. Muitas formas de identificação do cubo foram e estão sendo estudadas

em ambiente acadêmico. Os métodos para conseguir isto podem variar de acordo com a

robustez necessária para o problema. São citadas neste trabalho três abordagens diferentes:

1) Classificação estatística por vista única utilizando redes neurais convolucionais (RNC); 2)

Reconstrução em tempo real por vista única em 3D; 3) Reconstrução por múltiplas vistas

em tecnologia embarcada utilizando c-médias fuzzy.

O primeiro método estudado foi da Universidade de Stanford, Califórnia, e confia em três

técnicas básicas de processamento de imagens: 1) Detecção de bordas; 2) Detecção de

superpixels; 3) Transformada de Hough; tudo isto analisando uma imagem frontal que

contém três faces do Cubo, explicando, pois, o termo “vista única”. O interesse desta seção

é apenas identificar o Cubo, sua posição e tamanho na imagem. O tratamento, portanto,

consiste em 6 passos básicos (HACK; SHUTZBERG, 2015):

1. Aplicar uma rede neural convolucional em uma imagem RAW para encontrar seu

tamanho e coordenadas;

2. Separar a região da original

3. Aplicar um grupo de três RNC’s independentes às três faces do cubo

4. Aplicar K-médias e filtros gaussianos

5. Extrair superpixels da imagens utilizando o algoritmo Simple Linear Iterative Clustering

6. Extrair os centróides dos superpixels detectados, que serão equivalentes a cada

quadrado da face do cubo.

A Figura 2.2 ilustra o processo de extração por Redes Neurais Convolucionais.

O segundo método proposto descreve um algoritmo para identificação do Cubo também a

6

Figura 2.2 – Processo de localização e detecção do Cubo de Rubik por Redes NeuraisConvolucionais. Fonte: (HACK; SHUTZBERG, 2015)

partir de uma única vista, contendo três de suas faces. A sua vantagem é principalmente a

velocidade do algoritmo, de modo que normalmente a reconstrução 3D de um objeto em

visão computacional normalmente requer extração de características em diversas vistas e

ângulos (KASPRZAK; SZYNKIEWICZ; CZAJKA, 2006), enquanto este leva vantagem das

características geométricas do cubo. Por este motivo, o problema é frequentemente utilizado

para testes de performance. A Figura 2.3 exemplifica um modelo que leva em consideração

a geometria do Cubo.

Figura 2.3 – Processo de detecção do Cubo com foco em sua geometria. Fonte: (KASPR-ZAK; SZYNKIEWICZ; CZAJKA, 2006)

A técnica baseia-se na premissa de que os níveis de branco presentes na imagem devem

ser balanceados, ou seja, os tons de cinza se diferenciam somente pelo seu componente

7

Y de intensidade1, seus níveis U e V são centralizados. A partir da conversão de RGB

para YUV, uma normalização nas cores é realizada baseando-se na intensidade de cada

pixel (KASPRZAK; SZYNKIEWICZ; CZAJKA, 2006). Desta maneira, uma interpretação em

2D será realizada no Cubo. Considerando isto, uma classificação de pixels é realizada de

acordo com a cor. O autor não dá informação clara sobre o fundo da imagem ser controlado

ou não.

A imagem filtrada por cores então passa por uma detecção de células baseada em mo-

mentos geométricos, sendo cada uma destas um pequeno quadrado na face do Cubo.

Os momentos, segundo o autor, foram definidos experimentalmente (KASPRZAK; SZYN-

KIEWICZ; CZAJKA, 2006, p.4). Então as imagens são erodidas e dilatadas de modo a

planificar na tela a face do Cubo. Os resultados são satisfatórios. As faces distorcidas então

passam por uma computação de 4 vértices para cada contorno, as bordas são aproximadas,

as vizinhanças das células, definidas, e a informação direcional.

O último método baseia-se no reconhecimento de cada face do cubo em separado, utilizando

tecnologia embarcada, aplicada na plataforma ARM9 (HU et al., 2011). A segmentação de

imagens utilizado baseia-se em clustering por c-médias fuzzy (FCM). Este autor não levou

em consideração a lógica geométrica na qual o Cubo se enquadra para prever a situação

das outras faces, sendo necessária a captura de todas as outras seis faces.

2.3 Identificando características do Cubo

Uma vez identificado e extraído o cubo da imagem, o processo de identificar os clusters

é relativamente simples. Considerando que as cores diferem-se apenas em seus fatores

cromáticos para níveis constantes de iluminação (MATHWORKS, 2015a), é possível fazer

uma segmentação baseada em cores. Enquanto a abordagem no espaço YUV (KASPRZAK;

SZYNKIEWICZ; CZAJKA, 2006) é interessante, o espaço de cores LAB também é utilizado

pela CIE.

Neste exemplo, a segmentação é feita utilizando o método estatístico das k-médias, e o

número de clusters é definido de acordo com o número de segmentos necessário. No caso

do Cubo Mágico, seis faces, portanto, seis níveis de cores diferentes. Este método é simples

e eficiente para o problema, uma vez que o número de clusters é conhecido previamente à

resolução do problema, requisito indispensável para o algoritmo utilizado.

1considerando o espaço de cores YUV

8

2.4 Termos comuns neste trabalho

Afim de facilitar a leitura deste texto, termos comuns em processamentos de imagens, além

de termos que são amplamente utilizados neste trabalho, são nesta seção descritos.

1. Erosão e dilatação: técnica de processamento de imagens que consiste em erodir ou

ampliar partes da imagem, para destacar determinada característica.

2. Faces: cada face lateral do Cubo de Rubik.

3. Facetas: menor elemento de uma face.

4. Frequência espacial : taxa de variação de intensidade e fase de pixels por área.

5. Gama de cores: amplitude visível de cores do referido dispositivo.

6. Segmentação: separação de partes da imagem de acordo com características especí-

ficas.

7. Superpixel : vários pixels em vizinhança com outros de intensidade igual ou seme-

lhante. Técnica muito utilizada em visão computacional.

2.5 Considerações finais

O Cubo de Rubik, portanto, dadas as suas características geométricas bem definidas, é um

bom objeto para se fazer detecção utilizando visão computacional. Além disto, suas regiões

de cores são adequadamente delimitadas, facilitando uma análise a olho da qualidade do

processamento.

9

Capítulo 3

Codificação e Manipulação de Imagens

Digitais

É usual que um estudo sobre visão computacional seja acompanhado de um estudo

sobre técnicas de processamento de imagens, uma vez que existem diversos métodos

de se abordar o problema de acordo com sua complexidade computacional. Este capítulo

apresenta uma revisão sobre os conceitos aplicados para a resolução do Cubo Mágico.

3.1 A representação matricial de imagens digitais

Para imagens digitais, a representação mais comum para imagens do tipo bitmap - mapas

de bits, imagens não-vetoriais1, onde cada ponto representa a menor unidade da imagem,

o pixel - é a forma matricial. A área da unidade varia de acordo com o tipo de tela utilizado2.

Neste formato, o ponto superior esquerdo da matriz representa a coordenada [0,0], e as

coordenadas crescem para baixo e para a direita. Cada par [x,y] representa a posição de

cada pixel. O valor f(x,y) fornece a intensidade do pixel na respectiva coordenada. Para 256

tons de cinza, o valor 255 quer dizer branco completo, ou seja, total presença de luz, e 0

representa preto completo, ou seja, total ausência de luz. A Figura 3.1 ilustra esta situação.

Como dito, a quantização de uma imagem também é um fator importante. O par de valores

máximos de coordenadas [x,y] é tido como a resolução da imagem digital. Quanto mais

pontos na matriz, mais próxima a quantização da imagem é da imagem real, pois menor é a

área do pixel - considerado de tamanho fixo para um tamanho específico de tela-. A Figura

3.2 exemplifica uma fotografia digital para os valores de resolução (área) de 1024x1024,

512x512, 256x256, 128x128, 64x64 e 32x32 pixels, respectivamente. Pode-se notar que,

quanto maior a resolução, mais precisa é a representação, ou seja, mais nítida a imagem

1alguns métodos de representação de imagens digitais são baseados em gradientes vetoriais, então ospixels são representados por variações e não pontos isolados

2o seu tamanho fixo e a resolução máxima aceita são os fatores determinantes

10

Figura 3.1 – Representação matricial de uma imagem digital. Fonte: (GONZALEZ; WOODS,2002, p.55)

se torna.

Figura 3.2 – Quantização de uma imagem digital em diferentes resoluções. Fonte: (GONZA-LEZ; WOODS, 2002, p.55)

Tratando-se cada ponto da matriz como a intensidade do sinal em cada ponto, define-se

por domínio espacial (GONZALEZ; WOODS, 2002) as características de intensidade e

posição de cada pixel na imagem. Analisar-se a variação em vizinhança, e aplicar-se

uma transformada bidimensional de Fourier, obtém-se a representação da frequência da

imagem, similarmente a processamentos de sinais unidimensionais. Portanto, define-se

como frequência de amostragem a quantidade de pontos por área da imagem. Pode-se dizer

11

que, comparadas imagens de mesmo tamanho em área, a última imagem é subamostrada. A

Figura 3.3 ilustra o domínio da frequência para uma imagem em tons de cinza, com o centro

da imagem sendo o ganho unitário. Nota-se que os elementos centrais da Transformada

são de maior intensidade - branco -, ou seja, de menor frequência. Quanto mais afastados,

menor a frequência. Infere-se, portanto, que a Figura 3.3 possui muitos elementos de baixa

frequência.

Figura 3.3 – Uma fotografia e sua transformada de Fourier Bidimensional. Fonte: (PRATT,2007, p.197)

Os conceitos discutidos nesta seção aplicam-se também a imagens coloridas. No entanto,

neste último caso o valor de intensidade de pixel se dá pela sobreposição aditiva ou

subtrativa de intensidades diferentes de cores. Um estudo um pouco mais detalhado sobre

o tema encontra-se na seção 3.3.

3.2 Os Modelos de Cores Aditivos e Subtrativos

O problema de visão computacional do Cubo de Rubik requer processamento em cores,

considerando a maneira com que a informação é representada. Para isto, representa-se o

padrão de cores de modo quantitativo. Atualmente, são utilizados os modelos aditivo, como

por exemplo Red Green Blue - RGB, no acrônimo em inglês -, que fazem a sobreposição de

cores primárias, e os modelos subtrativos, e.g CIE LAB, que assumem uma base na cor

branca e filtram-na de acordo com o resultado requerido.

Os modelos aditivos consistem em assumir que existe um número finito de cores primárias,

e as mesmas são superpostas de maneira a reproduzir outras cores distintas, sendo branco

a superposição de todas as cores em intensidade máxima, e preto a ausência total de

cor. Estes modelos são muito utilizados em displays digitais, uma vez que basta apenas

12

emitir ondas de luz de diferentes comprimentos de onda para obter o resultado desejado.

Esta também é a maneira com a qual o olho humano interpreta cores (KOSCHAN; ABIDI,

2008). A Figura 3.4 descreve um exemplo do modelo aditivo. Nota-se, na mesma, que a

superposição dos padrões vermelho, azul, e verde resultam em branco.

Figura 3.4 – Representação em diagrama de Venn do Modelo Aditivo Tricromático RGB.Fonte: (KOSCHAN; ABIDI, 2008, p.28)

Por outro lado, os modelos subtrativos assumem como zero o valor de cor branca, que é

então filtrada em diferentes frequências, de modo a produzir o resultado requerido. Quando

todos os filtros estão operando em corte total, a cor preta é obtida. A Figura 3.5 representa o

modelo subtrativo CMYK - acrônimo do inglês para ciano, magenta e amarelo -, amplamente

utilizado em impressoras coloridas. Observa-se, em contraste ao modelo aditivo, que a

superposição de todos os elementos resulta em preto.

Figura 3.5 – Representação do Modelo Subtrativo de Cores CMYK. Fonte: (KOSCHAN;ABIDI, 2008, p.28)

3.3 Os Espaços de Cores

Diferentemente de grandezas físicas como temperatura ou pressão, cores são fenômenos

percebidos e relativos - a sua percepção não é propriamente física -, variando de acordo

com a visão humana - a quantidade de células na retina, por exemplo, diverge de indivíduo

13

para indivíduo (JÄHNE, 2005). Isso faz com que medidas de cor sejam relativas, complexas

de mensurar, portanto. A percepção de cores desvia de acordo com o número de cones

presentes no SVH individual. Em termos de computação, outrossim, esta interpretação

varia com o modelo da unidade de processamento gráfico.

Mais especificamente, os receptores cromáticos humanos dividem-se em três, fazendo com

que imagens coloridas sejam fisiologicamente medidas com um número extremamente

pequeno de sensores (KOSCHAN; ABIDI, 2008). Portanto, a análise de cores dentro de um

espectro de dados faz-se ineficaz. Esta seção discute tratamentos de espaços de cores

para VC, estando fora do escopo estruturas destinadas a impressões gráficas em material

(modelos não-aditivos).

3.3.1 O Espaço RGB (Red-Green-Blue)

O espaço de cores Vermelho, Verde e Azul, como o próprio nome diz, representa imagens

cromáticas utilizando-se da superposição em tons das cores primárias (modelo aditivo).

O resultado disso, em representação matricial, é uma matriz tridimensional onde os dois

primeiros índices indicam a posição do pixel, e o terceiro índice indica qual a intensidade da

cor utilizada no elemento em questão.

A Lei de Grassmann para a mistura de cores, pois, pode ser escrita em formato de soma de

vetores, num espaço vetorial não ortonormal (KOSCHAN; ABIDI, 2008, p.37):

M = R ·R+G ·G+B ·B (3.1)

sendo R, G, B escalares indicando a intensidade de vermelho, verde e azul puros, res-

pectivamente. Em representação matricial, para este modelo, cada pixel se dará pela

superposição de intensidade de cada cor primária, tal como na Figura 3.6.

A representação RGB, portanto, baseia-se na quantidade adicionada de cada cor primária

num espaço vetorial. O primeiro vetor da base indica vermelho puro, o segundo, verde puro,

e o terceiro, azul puro. A combinação linear dos parâmetros R, G e B então resultará na cor

misturada M. Por exemplo, sobrepondo-se as cores do espaço RGB o SVH interpretará a

cor resultante - por exemplo, o valor {255,0,255} em uma representação de 16 bits indica

um pixel na cor roxo puro -.

Este é o padrão mais utilizado para displays LCD’s no mercado, pela seu custo e proximidade

ao SVH. No entanto, a aplicação do problema exige um padrão diferente pelos seguintes

motivos:

• Complexidade e custo computacional - operações matemáticas utilizando-se matrizes

14

Figura 3.6 – Representação matricial para o modelo RGB. Fonte: (JÄHNE, 2005)

podem ser o gargalo de velocidade do problema. Para matrizes tridimensionais, é

ainda pior, uma vez que exige mais operações, aumentando em potência de N (número

de operações) a complexidade do problema (JÄHNE, 2005, p. 68)

• Proximidade ao Sistema Visual Humano - apesar de o modelo RGB identificar-se com

as células responsáveis por cada cor primária, um modelo bidimensional baseado em

cromaticidade e luminosidade (tal como os padrões CIE-YUV e CIE-LAB) aproxima-se

mais da interpretação dada pelo cérebro à visão (HOFFMANN, 2007a).

Este trabalho simula uma implementação a ser realizada em um sistema de baixo custo,

isto é, poder de processamento limitado. Isso faz com que o software seja o mais otimizado

possível, e um processamento bidimensional não-negativo, como o espaço CIE-LAB,

descrito na seção 3.3.3 é vantajoso nesta situação. Além disto, o escopo da classificação

do problema envolve apenas valores de crominância da imagem - elementos responsáveis

pelas cores -, fazendo-se dispensáveis os níveis de luminância - valores de brilho, ou limite

espectral de intensidade da cor -, o que não pode ser alcançado utilizando-se o modelo

RGB. Todavia, o último deve ser suficientemente grande a fazer todas as cores perceptíveis.

3.3.2 O Espaço CIE-XYZ

O primeiro fator a se pensar numa conversão entre modelos de espaços de cores é como

se relacionam. Em 1931, a Comission Internationale de l’Eclairage, órgão responsável

pela normatização internacional de cores, define como diagrama de cromacidade uma

intersecção de planos de iluminação constante - planos com a mesma intensidade de brilho

- com tonalidades representadas no plano, sendo estas seções transversais do cubo RGB -

espaço vetorial não ortonormal - rotacionado e transladado com seus vértices na origem,

tal como na Figura 3.7. Por conseguinte, o meio é vantajoso porque não apresenta valores

negativos - o custo computacional associado é menor se os dados forem inteiros sem sinal.

15

Figura 3.7 – Cubo de cores na base RGB sobreposta à XYZ. Fonte: (HOFFMANN, 2007b)

O resultado, descrito na Figura 3.8, foi nomeado Espaço de Cores CIE-XYZ. Esta indica um

plano com limites espectrais para os valores de cor, que equivalem à percepção de brilho

- iluminância - constante (HOFFMANN, 2007b). Foi definido em comissão, portanto, que

o ponto branco - valor máximo de intensidade de cor, branco - se encontrasse no ponto

x = y = z = 1/3, ao mesmo tempo que todas as cores perceptíveis a olho nu fossem

cobertas (HOFFMANN, 2007b), o que explica a interseção descrita.

A seção transversal descrita na Figura 3.8 é chamada de diagrama de ferradura, e apresenta

um plano de iluminância constante, apresentando um gama de cores - espaço de croma-

ticidade visível pelo dispositivo - bidimensional. Desta maneira, apenas duas dimensões

precisam ser analisadas para tirar informações sobre as cores, independente da quantidade

de luz por elas refletida. A mesma será responsável, contudo, pela área da seção: quanto

maior o valor de iluminância, maior será o gama de cores avaliado.

Figura 3.8 – Seção transversal do cubo RGB no plano XYZ (Diagrama de ferradura). Fonte:(HOFFMANN, 2007b)

Em outra análise, definir apenas duas variáveis para interpretação computacional significa

uma melhora significativa em performance para o sistema. Estas são definidas como matiz

e saturação(KOSCHAN; ABIDI, 2008, p.41), que são respectivamente as abscissas e

16

ordenadas do plano de cromaticidade. Fazendo-se a equivalência entre cores no RGB,

tem-se o resultado na Figura 3.9. Este gráfico relaciona as cores entre o mesmo e o espaço

XYZ.

A área sob as curvas da Figura 3.9, ponderadas de acordo com a potência espectral de

cada uma (JÄHNE, 2005), portanto, fornece uma equivalência direta entre os valores de

cores primários e o espaço XYZ.

Figura 3.9 – Representação em cores do Espaço de Cores CIE 1931. Fonte: (HOFFMANN,2007b)

Desta maneira, fica evidente que a transformação entre os espaços RGB para XYZ é apenas

de rotação e translação, sendo, portanto, uma transformação linear.

A transformação é do tipo:

xyz

XY Z

= Cxr

RGB

RGB

(3.2)

Sendo X,Cxr, R o vetor de coordenadas no espaço XYZ, a matriz de transformação linear

e as coordenadas no espaço RGB, respectivamente.

Portanto, da Figura 3.9, temos que a matriz de transformação de coordenadas será:

Cxr =

0.49000 0.31000 0.20000

0.17697 0.81240 0.01063

0.00000 0.01000 0.99000

(3.3)

Tratando-se de um espaço vetorial linear, a transformação inversa se dá pela multiplicação

17

de ambos os lados pela matriz inversa Crx, sendo a mesma:

Crx =

2.36461 −0.89654 −0.46807−0.51517 1.42641 0.08876

0.00520 −0.01441 1.00920

(3.4)

Os valores de X e Z não contribuem para a iluminância, sendo Y o único fator responsável

pela mesma (HOFFMANN, 2007b). Dessarte, as coordenadas X e Z são responsáveis pela

cromaticidade do objeto, representando as cores em duas dimensões. Estes também são

usualmente utilizados de forma normalizada, tal que x+ y + z = 1.

3.3.3 O Espaço CIE-LAB

Outro espaço de cores é o CIE-LAB, também bidimensional e independente de dispositivo.

É vantajoso por simular de maneira mais eficiente o gama de cores humano - espaço de

crominâncias percebidas pelo SVH -, ampliando de maneira significativa a cromaticidade

para luminâncias de valor mais elevado.

Um exemplo de diagrama de ferradura num plano de iluminância constante é representado

na Figura 3.10.

Figura 3.10 – Representação em cores do Espaço de Cores CIE LAB. Fonte: (HOFFMANN,2007a)

18

Considerando este diagrama de cromaticidade, um método computacionalmente eficiente

para medição de um sistema de cores é o espaço L*a*b* em raizes cúbicas(KOSCHAN;

ABIDI, 2008, p.71). As coordenadas de cores serão:

L∗ =

116(

YYo

) 13 − 16, Y

Yo> 0, 008856

903, 3(

YYo

), 0 ≤ Y

Yo≤ 0, 008856

(3.5)

a∗ = 500

[f

(X

Xo

)− f

(Y

Yo

)](3.6)

b∗ = 200

[f

(X

Xo

)− f

(Z

Zo

)](3.7)

onde a iluminância L∗ é:

L∗ =

w13 , w > 0, 008856

7, 787w + 0, 1379, 0 ≤ w ≤ 0, 008856(3.8)

E a transformação inversa:

Y1 =L∗ + 16

116(3.9)

X1 =a∗

500+ Y1 (3.10)

Z1 =−b∗

200+ Y1 (3.11)

Sendo Xo, Yo e Zo os valores normalizados do espaço CIE-XYZ, em referência ao ponto

branco. Caso algum valor seja menor que 0 ou maior que 1, é considerado que o ponto está

fora do gama de cores visualizado.

3.4 Os histogramas de imagens

Histogramas bidimensionais têm como propósito expressar graficamente a distribuição

de um grupo de dados univariável (ENGINEERING. . . , 2015). Desta maneira, podem ser

aplicados a uma imagem considerando-se o eixo x como sendo o valor da intensidade da

cor e o eixo y como o número de ocorrências do mesmo na imagem.

19

A Figura 3.11 descreve o histograma de uma imagem com padrão de cores RGB. Uma vez

que, de acordo com a seção 3.3 é inferido que imagens neste modelo são formadas a partir

da superposição de cores primárias, é possível observar que o histograma deve ter três

distribuições diferentes. Cada uma delas está representada na própria cor.

Figura 3.11 – Histograma RGB de uma imagem digital

O caso para imagens em tons de cinza é um pouco menos complexo. A Figura 3.12 descreve

uma imagem descolorida e seu histograma, representativo apenas dos tons de cinza da

mesma.

Figura 3.12 – Histograma em escala de cinza de uma imagem digital

Existe um processo para equilibrar ocorrências das cores em imagens monocromáticas,

chamado de equalização de histogramas. Este processo consiste em manter o gráfico o

mais constante possível, e é descrito mais detalhadamente no capítulo 4.

3.5 Considerações Finais

A representação matricial de imagens digitais no domínio espacial é uma tecnologia muito

útil pois descreve informações visuais passíveis de interpretação humana. Quanto mais

amostradas, melhor a qualidade, mas maior o tamanho, e vice-versa. A Transformada

Bidimensional de Fourier informa características de variação da imagem, descrevendo

informações na frequência. Os modelos de cores RGB possuem excelência na informação

20

de cores, independente da luminosidade, todavia são tridimensionais. Um contorno a

este problema pode ser a utilização de modelos bidimensionais, tais como o CIE-LAB,

desconsiderando-se informações de iluminância. Os histogramas são ferramentas eficientes

para retirar informações de distribuições de energia em uma imagem.

21

Capítulo 4

Algoritmos Básicos para

Processamento de Imagens Digitais

É inerente a problemas de Engenharia uma implementação simulada para determinar

características de projeto detalhado. Este capítulo trata o código trabalhado em ambiente

MATLAB para fins de testes gerais de programação, otimização e estimação de recursos

necessários para implementação em tecnologia embarcada.

4.1 A aquisição de imagens digitais

A aquisição de imagens digitais é normalmente realizada através de câmeras, ou gerada

a partir de outros tipos de mídias digitais - softwares de desenho, processamento digital

de imagens, dentre outros -. Neste processo, vários fatores interferem da captura ao

armazenamento. Para o escopo deste trabalho são considerados luminosidade, ruído e

distorção.

4.1.1 Os problemas comuns a câmeras digitais

O dispositivo que faz a interface do mundo em cores analógico com o mundo em cores

digital é a câmera. Por este motivo, está sujeita imperfeições na representação da cena real

de aquisição de dados, sendo os mais comuns sujeira nas lentes e/ou ruído de aquisição.

Para testar a influência disto é tratado um caso ideal (que é simulado por uma imagem do

cubo tratada em ambiente Photoshop), e o restante, dividido em três categorias: 1) Adição

de ruído (simula os ruídos de aquisição do componente CMOS da câmera digital, assumida

distribuição normal); 2) Adição de distorção gaussiana (“embaçamento” das lentes); 3)

Ambos. Todos os três casos foram simulados utilizando as ferramentas gaussian blur e add

noise do mesmo software.

22

4.2 Os filtros espaciais

O simples processamento puntual de cada pixel não considera informações sobre a

vizinhança, sendo que, muitas vezes, a visão do todo é importante para a percepção

do objeto (JÄHNE, 2005). Por este motivo, uma análise espacial é de bom uso para

analisar-se o comportamento em regiões da imagem. Para isto, operadores de vizinhança,

mais especificamente filtros discretos bidimensionais, são utilizados em processamento de

imagens.

4.2.1 Os filtros discretos bidimensionais

Operações de vizinhança podem ocorrer tanto no domínio espacial quanto no domínio

da frequência. No primeiro, é especificada uma janela - máscara bidimensional - (JÄHNE,

2005) que fará uma convolução com uma imagem, sendo transladada ao longo da imagem,

como na Figura 4.1, para um filtro 3x3. A máscara é convoluída ponto a ponto ao longo da

imagem, portanto5.

Figura 4.1 – Janela 3x3 pixels que representa um filtro discreto bidimensional (JÄHNE,2005)

No caso de filtros no domínio da frequência, são especificados os mesmos parâmetros

de filtros discretos, tais como atenuação, banda de passagem e ganho, dentre outros. Um

estudo aprofundado sobre filtros bidimensionais corre do escopo deste trabalho, e pode ser

visitado com mais detalhes nas bibliografias (JÄHNE, 2005), (POGGIO; TORRE; KOCH,

1989), (KOSCHAN; ABIDI, 2008), (PRATT, 2007) e (GONZALEZ; WOODS, 2002).

É reconhecido na seção 3.1 que os elementos de intensidade de um sinal bidimensional são

descritos através de diferentes energias dentro de um espaço, sendo, portanto, pertencentes

ao domínio espacial. Pode-se portanto dizer que grandes variações de energia do sinal de

determinado nível de quantização para outro caracterizam um elemento de altas frequências,

e pequenas alterações indicam baixas frequências. A Figura 4.2 descreve os resultados para

uma filtragem bidimensional passa-baixas. Este problema ocorre quando as imagens estão,

23

por exemplo, fora de foco. Fica evidente que, uma vez filtrada, a fotografia cria dificuldades

de percepções de bordas.

Figura 4.2 – À esquerda, a imagem original. À direita, com um filtro passa-baixas no domínioda frequência.

4.2.2 O Filtro Bidimensional de Wiener

Até o momento foram discutidos problemas comuns a aquisição de imagens, como na seção

4.1. Levando-se em consideração que o desfoco comporta-se como um filtro passa-baixas,

é natural que se pense em filtragem inversa. Define-se, em duas dimensões (PRATT, 2007),

a filtragem inversa na frequência:

HR(ωx, ωy) =1

HD(ωx, ωy)(4.1)

considerando-se HR o filtro inverso de HD.

A bibliografia (PRATT, 2007, p. 359) desenvolve matematicamente a análise, passando por:

1. Espectro da imagem reconstruída

2. Transformada inversa de Fourier

A Figura 4.3 mostra o produto do ganho para a variação unidimensional 1, e nota-se que o

filtro inverso HR - estimado minimizando-se o erro quadrático - visa compensar os ganhos

do filtro direto HD - desconhecido - nas respectivas frequências, mantendo um produto

constante unitário.

Um questionamento que surge nesta análise é a influência eventual de ruídos - elementos

comuns na aquisição de imagens - no projeto do filtro inverso. Não é surpreendente o fato

de que filtragem inversa apresenta desempenho inadequado em meios práticos, dado que

ignora este tipo de entrada (PRATT, 2007).

1separando-se as frequências vertical e horizontal. Isto é possível porque a Transformada de Fourier é umoperador linear

24

Figura 4.3 – Respostas em frequência do filtro passa-baixas HD e seu filtro inverso HR

(PRATT, 2007).

A Figura 4.4 ilustra o modelo de filtragem inversa considerando-se ruído. Sendo x(t) o

sinal de entrada, h(t) o filtro inverso, s(t) o sinal de saída obtido, e e(t) o erro, deseja-se

minimizar o último.

Figura 4.4 – Modelo de filtragem inversa.

Uma solução usual para este tipo de problema é criar um filtro de restauração, sendo o

exemplo abordado o Filtro Bidimensional de Wiener. O mesmo assume um conhecimento

estatístico do campo de ruídos (PRATT, 2007). Para os fins deste trabalho, o modelo de

ruído será considerado gaussiano, em outras palavras, tem distribuição normal.

Assume-se, portanto, que tanto a imagem observada Fo quanto a imagem ideal Fi são

campos bidimensionais estocásticos contínuos com a média espacial centrada em zero. A

resposta ao impulso do Filtro Bidimensional de Wiener é, então, obtida como a minimização

do erro quadrático de restauração ε (PRATT, 2007):

ε = E{[Fo(x, y)− Fi(x, y)]

2}

(4.2)

25

O desenvolvimento matemático é realizado na bibliografia (PRATT, 2007, p. 360), de maneira

que a expressão geral para o Filtro Bidimensional de Wiener com ruído aditivo seja do tipo:

HR(ωx, ωy) =H∗

D(ωx, ωy)WFi(ωx, ωy)

|HD(ωx, ωy)|2WFi(ωx, ωy) +WN(ωx, ωy)

(4.3)

, onde WN é o modelo do ruído na frequência - constante, caso gaussiano -, e WFia

transformada de Fourier da imagem observada.

As respostas típicas em frequência de acordo com as considerações realizadas estão

descritas para o eixo x na Figura 4.5. Considerando o ruído como uma distribuição normal,

tem-se sua transformada WN como uma constante. O modelo do filtro HD é estimado com

ruído aditivo. O resultado para a resposta ao impulso do Filtro de Wiener é descrito por HR.

Figura 4.5 – Respostas típicas do Filtro Bidimensional de Wiener para o eixo x (PRATT,2007).

Aplicando-se ruído gaussiano em uma imagem, e então reconstruindo-se a imagem utili-

zando a ferramenta para cada camada de cor - RGB - tem-se os resultados na Figura 4.6. A

primeira imagem é a original. A imagem da direita representa a imagem corrompida com

ruído gaussiano, o que ocasiona certa granulação. A fotografia mais abaixo representa a

imagem reconstruída, diferindo-se pouco da primeira.

26

Figura 4.6 – À esquerda, a imagem original. À direita, a imagem corrompida com ruídogaussiano. Abaixo, a reconstrução utilizando-se um Filtro Bidimensional deWiener

4.3 A extração de características

Em problemas de classificação e reconhecimento de padrões, uma ferramenta fundamental

é a extração de características. Muito frequentemente, o tamanho do grupo de dados é um

gargalo de processamento (TSAI, 2008), e este problema não se simplifica em VC. Por este

motivo, as características - valores derivados do grupo inicial de dados, informativos e não

redundantes - facilitam o aprendizado subsequente, bem como os passos de generalização.

Isto também pode levar a melhores interpretações humanas.

Especificamente, características em imagens digitais nada mais são que operações em

vizinhanças para executar a tarefa de analisar o comportamento dos pixels por janelas,

extraindo informações relativas sobre a região.

4.3.1 O uso de pré-processamento para extração de características

(TSAI, 2008) propôs uma estratégia para facilitar a extração de características de imagens

digitais, bem como ter certeza de que as mesmas são altamente representativas dentro

da imagem: pré-processamento. Outrossim, estes dados também são garantidamente não

baseados em ruídos e/ou entradas espúrias.

27

O processo de pré-processamento proposto na bibliografia baseia-se em dois principais

passos: 1) melhoria de contraste no domínio do espaço; 2) alisamento por filtragem na

frequência no domínio da frequência (TSAI, 2008).

4.3.1.1 A melhoria de contraste

A melhoria de contraste descrita em (TSAI, 2008) propõe uma maximização de alcance dinâ-

mico - trecho entre o valor mais escuro e o mais claro da imagem, desconsiderando ruídos.

Isto pode ser alcançado através de escalas em amplitude na imagem - majoritariamente

correção de luminosidades e equalização de histogramas.

Algumas imagens possuem características mais exacerbadas graças a diferenças de luz

causadas por iluminação unidirecional. Isto pode intensificar os pontos de interesse em

torno de uma região que não necessariamente reflete a mais forte. Portanto, compensando-

se em amplitude as luminosidades tem-se a garantia de uma extração mais uniforme (TSAI,

2008). A Figura 4.7 ilustra o procedimento para uma fotografia tirada ao pôr do Sol. Uma

vez que a iluminação é mais forte do lado esquerdo, algumas evidências de bordas podem

tornar-se menos intensas do lado sombreado. Isto pode fazer com que o histograma de

gradientes orientados da região deixe de detectar um ponto de interesse.

Figura 4.7 – Correção de iluminação em uma fotografia ao pôr do Sol. À esquerda, a imagemsem tratamento. À direita, a imagem com correção de iluminação.

Outro elemento usual para a melhoria de contraste é a equalização de histograma - como

descrito na seção 3.4 - (TSAI, 2008). De maneira a deixar o mesmo o mais uniforme

possível, as intensidades da imagem digital são ajustadas de maneira a garantir distribuições

aproximadamente iguais. A Figura 4.8 demonstra um histograma e sua versão equalizada.

Naturalmente, no caso monocromático, isto faz com que os pontos mais escuros da imagem

se tornem mais claros, e vice-versa. A Figura 4.9 demonstra a diferença de contrastes entre

uma imagem e sua versão com histograma equalizado. Nota-se que as bordas ficaram mais

evidentes, o que indica um aumento de contraste na imagem.

28

Figura 4.8 – À esquerda, o histograma de uma fotografia. À direita, o mesmo histogramaequalizado.

Figura 4.9 – Imagem digital e sua versão com histograma equalizado.

4.3.1.2 Alisamento por filtragem

Como discutido na seção 4.2, um filtro passa-baixas executa um "alisamento"da imagem,

reduzindo a magnitude dos elementos de altas frequências.

4.3.2 As Características SURF

Um algoritmo de extração de imagens muito popular em reconhecimento de objetos são as

características SURF (TSAI, 2008). Sigla para Speeded-up Robust Features, este método

é computacionalmente eficiente, dentre outros, para reconhecimento de objetos em uma

cena (BAY; TUYTELAARS; Van Gool, 2006).

Seu funcionamento baseia-se em três passos principais (BAY; TUYTELAARS; Van Gool,

2006): 1) seleção de pontos de interesse no objeto; 2) localização de suas vizinhanças; e 3)

seleção e comparação de pontos de interesse na imagem analisada.

A seleção de pontos de interesse ocorre em coordenadas distintas da imagem. Estes

29

pontos podem ser junções em T - formações similares à letra -, bolhas - regiões onde

uma propriedade é constante ou aproximadamente constante -, ou quinas - aproximações

similares a um degrau no domínio espacial -. A parte mais importante deste detector é sua

repetibilidade, ou seja, é capaz de encontrar os mesmos padrões em diferentes condições

de visibilidade, como rotações, escalas em amplitude, diferentes luminosidades, dentre

outros. A Figura 4.10 ilustra este passo: os pontos de interesse foram circulados em verde.

Figura 4.10 – Detecção de Pontos de Interesse para Características SURF (MATHWORKS,2015b)

Localização - armazenamento de informações sobre as localidades - de todas as vizinhanças

dos pontos de interesse em um descriptor, vetor de características onde os pontos são mais

intensos. O mesmo deve ser distintivo - único em sua região -, robusto a ruído, erros de

detecção e deformações na imagem.

O mesmo é realizado para as imagens a serem comparadas, então os descriptors são

relacionados, localizando o objeto no novo quadro. Normalmente este passo baseia-se em

distâncias de Malahanobis (TSAI, 2008) - por correlação - ou Euclideanas - invariantes a

escala. Naturalmente, o tamanho do vetor de características tem um impacto direto no custo

computacional da operação, fazendo-se necessário que o tamanho do vetor seja o menor

possível.

A grande vantagem deste algoritmo - além de sua robustez e eficiência - é a sua invariância

em rotações e escalas. O detector, por este motivo, também o é. Um método muito usado

para tal, dada a sua estabilidade e repetibilidade, é a matriz Hessiana (BAY; TUYTELAARS;

Van Gool, 2006), que baseia-se na localização da curvatura de uma função de várias

variáveis - através das taxas de variação unidimensionais; similar à matriz Jacobiana. Para

uma imagem de duas dimensões, a matriz Hessiana é convoluída com a derivada de

segunda ordem da função gaussiana (BAY; TUYTELAARS; Van Gool, 2006), tornando a

30

detecção robusta a ruído. Uma vez que uma curvatura é detectada, ela também é invariante

a rotações. Aplicando-se a filtros espaciais, localmente a matriz definida H para o ponto x e

variância σ será do tipo:

H(x, σ) =

[Lxx(x, σ) Lxy(x, σ)

Lyx(x, σ) Lyy(x, σ)

](4.4)

onde Lxx(x, σ) é a convolução da segunda derivada da função gaussiana com a imagem

I no ponto x. O raciocínio é análogo para o restante das variáveis. Mais detalhes sobre o

assunto podem ser encontrados em (BAY; TUYTELAARS; Van Gool, 2006).

Para fins práticos, o descriptor mais apelativo para fins práticos é o SIFT - scale invariant

feature transform - (BAY; TUYTELAARS; Van Gool, 2006). O mesmo baseia-se na compu-

tação de um histograma de gradientes orientados - descriptor que conta as orientações

dos gradientes - em torno dos pontos de interesse do detector, armazenando os resultados

em um vetor de 128 dimensões. Isto ocorre dada a natureza do algoritmo utilizar um histo-

grama espacial de gradientes para descrever o comportamento de uma região, quantizada

em oito silos de coordenadas 4-dimensionais, pesadas por uma função Gaussiana, como

descrito na Figura 4.11. O funcionamento completo e detalhado do algoritmo SIFT pode ser

encontrado em (VEDALDI, 2013).

Figura 4.11 – Histograma espacial do gradiente da imagem (SIFT)(VEDALDI, 2013)

4.3.3 A luminosidade e o ambiente controlado

Como discutido na seção 3.3, luminância e crominância são independentes uma vez

considerados os espaços de cores bidimensionais. A complexidade do problema permite

uma análise em qualquer plano de luminância constante, desde que as cores no mesmo

tenham valores melhor definidos de modo a evitar classificações incorretas.

Utilizando-se o espaço de cores CIE-LAB, por motivos discutidos na seção 3.3, a luminância

L pode ser desconsiderada na classificação, dado que apenas os valores de cores do cubo

31

são utilizados para a sua resolução, uma vez a imagem do cubo separada do fundo, ou

seja, extraindo apenas as características necessárias.

4.4 A classificação estatística das cores pelo método das k-

médias

Como qualquer conjunto de dados, os pontos dentro de uma matriz de cores podem ser

classificados em n agrupamentos, sendo cada um destes um outro set de dados menor, com

características semelhantes (features). Estas podem indicar diversos pontos específicos

dentro de uma imagem - olhos e boca em uma fotografia, por exemplo -, e existem pesquisas

específicas dentro do assunto visão computacional dedicadas exclusivamente a extração

de características no domínio da frequência ou do tempo.

O algoritmo das k-médias consiste em receber como entrada os dados e dividí-los em

um número k de agrupamentos, sendo k pré-definido - o número de cores das facetas,

neste caso -. A Figura 4.12 representa a separação linear de dados classificados por

clustering para k = 3. O requisito é também a principal desvantagem entre os métodos de

segmentação, pois o mesmo deve ser conhecido previamente. No escopo deste trabalho,

isto não é um problema, pois k é o número de faces presentes no cubo, uma vez que cada

uma possui apenas uma cor. A classificação dará-se, portanto, com k = 6.

Figura 4.12 – Classificação de dados para k=3. Fonte: (PRATT, 2007)

Uma vez escolhido o número de fatias da imagem, o algoritmo k-means escolherá 6 médias

centrais de cada cluster, especificando portanto a origem do nome. Sendo x o ponto

32

analisado, e µi a média local, temos que a classificação S será dada por:

S = argmins

k=6∑i=i

∑x∈Si

||x− µi||2 (4.5)

Desta maneira, os pontos x são valores das cores nas imagens, e os centróides µi serão

as representações de cada uma das k cores. Portanto, quanto mais próximo o valor de cor

ao centróide, mais precisa será a classificação.

Considerando que o problema é estocástico por ser baseado em pixels sem controle

de ruídos externos (PRATT, 2007), o algoritmo de LLoyd prevê a otimização centrando

os clusters por mínimos quadrados, e atualiza os valores de acordo com a necessidade

do estimador, parando quando a aproximação é suficiente boa (heurística). O estudo

aprofundado deste algoritmo foge ao escopo deste trabalho, e as k-médias serão tratadas

como um bloco fechado ao longo deste.

4.5 Considerações Finais

Técnicas de processamento digital de imagens são abordadas neste trabalho, de maneira a

utilizar filtros restauradores - especificamente, o Filtro de Wiener - para tratar uma imagem

em caso de ruído. A extração de características é realizada utilizando-se o método SURF, e

são comparados resultados com e sem pré-processamento. Ademais, as cores do cubo

são classificadas utilizando-se k-médias no espaço CIE-LAB para luminância constante, e

comparadas adicionando-se ruído e simulando desfoco.

33

Capítulo 5

Resultados Aplicados ao Cubo de Rubik

Este capítulo trata da aplicação das ferramentas descritas no capítulo 4 dedicadas a imagens

matriciais, como ilustradas no capítulo 3.

Doravante, a análise dos resultados será realizada em duas etapas: 1) o tratamento da

imagem enquanto localização do Cubo em uma fotografia digital; e 2) a caracterização de

cada cor utilizando o algoritmo das k-médias.

5.1 A localização do Cubo

A abordagem utilizada para a localização do Cubo em uma imagem baseia-se em extração

e comparação de características SURF, utilizando o software Matlab. Este foi utilizado

dada a sua facilidade de implementação, contendo toolboxes de alto nível para Visão

Computacional e Processamento de Imagens.

5.1.1 O roteiro

Os principais comandos utilizados são:

1. extractfeatures() - encontra os pontos de interesse e armazena em um descriptor.

2. histeq() - equaliza o histograma da imagem.

3. matchfeatures() - compara características em duas imagens diferentes.

4. rgb2gray() - converte uma imagem RGB em 255 tonz de cinza.

5. wiener2() - aplica um Filtro de Wiener Bidimensional na imagem.

(TSAI, 2008) observa que o processo pode ser melhorado utilizando-se pré-processamento,

o que faz com que as características se destaquem mais, e fiquem mais simples ao algoritmo

de serem comparadas. A abordagem da rotina Matlab segue o roteiro:

1. Conversão da imagem de RGB para 255 tons de cinza.

34

2. Aplicação de um Filtro Bidimensional de Wiener para remoção de ruído.

3. Extração das características SURF da imagem do Cubo.

4. Extração das características SURF da fotografia.

5. Comparação utilizando matchfeatures().

Um grupo de dados contendo 25 imagens JPG foi testado, todavia apenas os resultados

mais significativos estão disponíveis neste trabalho, por questões de coesão. Entretanto,

dois tipos de testes foram realizados. Extração com imagens sem tratamento, e extração

com as mesmas fotografias com pré-processamento.

O pré-processamento utilizado consiste de correção de iluminação, via rotina Matlab -

equilibrio de intensidades de cinza - e equalização de histogramas utilizando-se o comando

histeq.

Os resultados são mostrados em Figuras, nas quais ao lado esquerdo encontra-se o objeto

procurado, e ao oposto, a imagem na qual o objeto é buscado. As linhas amarelas conectam

as características SURF encontradas no objeto às suas respectivas na imagem buscada.

Os casos nas quais estas características são errôneamente comparadas são chamados de

outliers.

5.1.2 A extração sem pré-processamento

Em primeiro lugar, a extração de características SURF é realizada sem pré-processamento

da imagem.

O caso mostrado na Figura 5.1 funciona como um benchmarking da aplicação, explicitando

a correlação entre a mesma imagem. Pode-se assumir que as características foram com-

paradas com sucesso, observando-se a quantidade de pares bem sucedidos. No entanto,

alguns pares formaram outliers, como nas facetas brancas, onde pontos similares são

errôneamente ligados.

A Figura 5.2 ilustra o caso em que apenas as características disponíveis em pontos com

foco perfeito na imagem foram comparados com sucesso. É possível inferir que isso possa

ser um problema na localização do cubo caso haja um desfoque na aquisição.

O terceiro caso exacerba o fato de que não houve comparação bem sucedida entre

características - não foi encontrada nenhuma região similar entre as duas representações,

não tendo, portanto, nenhuma linha amarela -, como descrito na Figura 5.3. Isto pode ser

explicado levando-se em consideração que a imagem utilizada como base resulta de um

desenho, e isso infere bordas bem definidas - fotografias possuem, por exemplo, desfoques

e diferenças naturais de iluminação -. Na imagem a ser localizada, mesmo com o Cubo

destacado, equilíbrios de luz, bem como reflexos e bordas não muito definidas podem

35

Figura 5.1 – Benchmarking do algoritmo SURF sem pré-processamento.

Figura 5.2 – Comparação com fundo fora de foco, imagem sem pré-processamento.

atrapalhar a comparação.

Figura 5.3 – Comparação mal sucedida, imagem sem pré-processamento.

A Figura 5.4 representa o último caso. Observando-se este resultado, é curioso notar que

formaram-se apenas outliers nos pares: as características das bordas do Cubo foram

36

comparadas com as bordas dos dedos. Justifica isto o fato de que as interfaces entre o

objeto e o fundo são similares neste caso. O Cubo em si não foi identificado, e para esta

situação o mesmo estava rotacionado.

Figura 5.4 – Extração sem pré-processamento, comparação errônea com outliers

5.1.3 A extração com pré-processamento

O mesmo grupo de dados foi analisado aplicando-se pré-processamento nas imagens,

como recomendado por (TSAI, 2008). Uma filtragem de Wiener foi aplicada, bem como

equalização de histograma e correção de iluminação.

5.1.3.1 A comparação entre as imagens sem e com pré-processamento

As imagens sem e com pré-processamento são dispostas nesta seção para fins de compa-

ração do leitor entre o antes e o depois das operações.

A Figura 5.5 mostra as operações realizadas no primeiro caso. Avaliando-se a primeira

Figura, vêem-se bordas bem definidas, bem como uma iluminação bem distribuída, no

caso anterior. Após efetuadas as correções de iluminação e equalização de histograma, a

imagem tornou-se um pouco menos definida, entretanto seus tons de cinza foram melhor

distribuídos.

O caso mostrado na Figura 5.6 mostra, na imagem da esquerda, uma imagem com tons de

cinza menos definidos. Após o tratamento, o contraste foi melhorado, bem como as bordas

ficaram melhor definidas mesmo no fundo desfocado.

A terceira Figura, 5.7, apresentou após o pré-processamento uma melhor definição de

bordas, e o contraste melhorado. Os tons de cinza de maior energia ficaram mais brancos.

O último caso é ilustrado pela Figura 5.8. O fundo da imagem foi melhor destacado, o

contraste melhorou e as bordas ficaram melhor definidas.

37

Figura 5.5 – Tratamento das imagens no primeiro caso.

Figura 5.6 – Tratamento das imagens no segundo caso.

Figura 5.7 – Tratamento das imagens no terceiro caso.

5.1.3.2 Os resultados com pré-processamento

O benchmarking utilizado neste caso, descrito na Figura 5.9, teve seus resultados um pouco

melhorados, no que se refere a quantidade de outliers. No entanto, uma quantidade bem

38

Figura 5.8 – Tratamento das imagens no quarto caso.

menor de características foi comparada de maneira bem sucedida. Também foi possível

notar que houve um caso em uma faceta branca no qual duas características do objeto

encontraram-se com a mesma na imagem. Em outras palavras, houve uma comparação

errônea. Justifica isto o fato de que o vértice da faceta branca do objeto é muito parecido

com a quina encontrada na imagem.

Figura 5.9 – Benchmarking com pré-processamento.

O segundo caso, ilustrado pela Figura 5.11, teve seus resultados piorados. Na análise

realizada na seção 5.1.2, mais características foram comparadas de maneira bem sucedida.

Portanto, nesta situação, o pré-processamento não foi de boa utilidade.

A Figura 5.11 representa uma melhoria em relação à imagem sem pré-processamento.

A seção 5.1.2 indicou um resultado sem sucesso, entretanto, neste caso, as operações

realizadas melhoraram o mesmo.

39

Figura 5.10 – Comparação com fundo fora de foco utilizando pré-processamento.

Figura 5.11 – Comparação do terceiro caso utilizando pré-processamento.

O último caso, mostrado na Figura 5.12 teve seus outliers removidos, mas não aumentou-

se o número de comparações bem sucedidas. Enquanto na seção 5.1.2 apenas pontos

incorretos foram identificados, nesta situação os mesmos foram removidos.

Figura 5.12 – Último caso utilizando-se pré-processamento.

40

5.2 A classificação do Cubo

5.2.1 O caso ideal

A implementação é baseada no espaço de cores CIE-LAB, por ser bidimensional, portanto,

de fácil processamento. A entrada é uma imagem comprimida em JPG, representada

originalmente em espaço RGB. O comando applycform() serve para realizar uma trans-

formação de espaço de cores independente de dispositivo (MATHWORKS, 2015b), e o

comando makecform() cria um tipo de transformação. Estas instruções podem ser usadas

para resolver o problema. Uma vez obtida a imagem em CIE-LAB, a clusterização pode

ser realizada utilizando-se o método das k-médias para k = 6. O resultado será um cubo

classificado com diferentes tons de cinza, o que facilita o processamento, e está descrito

na Figura 5.13b. A imagem original tem a localização dos pixels classificados marcada,

extraindo cada valor de cor da imagem, e plotando-se em Figuras diferentes, descritas na

5.13. A imagem original do cubo, na Figura 5.13a, foi reproduzida para fins de comodidade

do leitor.

Aplicando-se a função kmeans() do MATLAB a um grupo de dados bidimensional - no caso,

o cubo já separado do fundo -, utilizando-se 6 clusters centralizados nas equivalências de

cores RGB, tem-se o resultado descrito na Figura 5.13. Da esquerda para a direita, de

cima para baixo, tem-se a imagem original do Cubo, o resultado para classificação - cada

tom de cinza indica uma classe diferente -, e o restante das Figuras indica exemplos de

classificação de cores, com as mesmas extraídas da Figura.

O resultado, como apresentado, é bastante satisfatório, mas com duas limitações:

1. O algoritmo confunde tons com equivalências de cores semelhantes, ou seja, para

curvas de equivalência sobrepostas, a classificação pode ser feita incorretamente.

Um exemplo disto é a confusão de tons primários com a cor branca, que são muito

próximos na ferradura do CIE-LAB (vide seção 3.3.3, Figura 3.10).

2. Como a compressão JPG não aceita fundos transparentes, um fundo vazio quer dizer

fundo branco, que também foi confundido durante a classificação.

5.2.2 Distorção gaussiana

A fim de simular um “embaçamento” das lentes de uma câmera, utilizou-se o filtro gaussian

blur do Photoshop, que nada mais é que um filtro passa-baixas que, como no capítulo 3,

amacia as bordas da imagem. Isso faz com que o Cubo perca suas características bem

definidas, premissa para o estudo deste trabalho. A Figura 5.14 apresenta uma distorção

gaussiana com 2 pixels de raio. Nota-se que: 1) houve uma confusão do algoritmo, que

escolheu uma das classes como sendo as bordas das facetas; e 2) a classificação entre

41

(a) Imagem original(b) Resultado para a classifi-

cação do cubo(c) Valores de vermelho isola-

dos

(d) Valores de laranja isolados (e) Valores de branco isolados

Figura 5.13 – Resultados para isolação utilizando classificação estatística pelas k-médias

verde e branco foi feita incorretamente, dada a proximidade dos tons no espaço de cores

CIE-LAB.

(a) Imagem original(b) Resultado para a classifi-

cação do cubo(c) Classificação incorreta de

bordas

(d) Classificação incorreta en-tre verde e branco

Figura 5.14 – Resultados para distorção gaussiana de 2 pixels

42

Como pode-se verificar, o alisamento das bordas é um problema sério na classificação

por k-médias. Filtrando-se a imagem em baixas frequências, os valores de crominância da

imagem podem ser afetados, fazendo com que as classes geradas pela rotina MATLAB

não sejam uma cor, mas sim uma classificação incorreta, tais como na Figura 5.14c. Uma

classificação incorreta entre cores também pode acontecer, como é o caso da Figura 5.14d.

Aumentando-se o efeito de distorção para 4 pixels de raio, analisando-se um cenário pior,

tem-se os resultados descritos na Figura 5.15. Nesta Figura, os tons próximos, como

alaranjado e vermelho, foram confundidos. A classe incorreta que contempla as bordas das

facetas ficou ainda maior.

(a) Imagem original(b) Resultado para a classifi-

cação do cubo(c) Classificação incorreta en-

tre vermelho e laranja

(d) Erro de classificação embordas

Figura 5.15 – Resultados para distorção gaussiana de 4 pixels

É possível verificar que os efeitos de classificação incorreta foram intensificados em relação

a distorções menores e a casos ideais, como na Figura 5.13. O efeito de classificar as

bordas como uma cor foi ainda mais intenso, pois além de criar uma classe indesejada,

também classificou errôneamente facetas de mesma cor, como nas Figuras 5.15c e 5.15d.

5.2.3 Adição de ruído

Outro efeito comum a câmeras digitais é a sensibilidade do dispositivo CMOS capturar

pixels indesejados à imagem. O fenômeno de ruído é simulado em ambiente Photoshop

utilizando-se a ferramenta add noise. Utilizando-se 20% de magnitude de ruído nos primeiros

testes, percebe-se a disposição dos resultados na Figura 5.16. A classe de azul obteve

uma ambiguidade, na qual foi confundida com a cor branca, dada a sua proximidade no

43

espaço CIE-LAB. O mesmo aconteceu no reverso. Explica isto o fato de os centróides serem

colocados muito próximos quando há ruído na imagem.

(a) Imagem original(b) Resultado para a classifi-

cação do cubo(c) Classificação ambígua de

branco

(d) Classificação ambígua deazul

(e) Classificação para facetasvermelhas e laranjas

Figura 5.16 – Resultados para 20% de ruído gaussiano

Uma vez que o ruído gaussiano possui densidade espectral constante, ou seja, possui

elementos de todas as cores ponderadamente iguais, um erro de interpretação pode ser

gerado, confundindo-se branco - que possui elementos de todas as cores - e azul - que é

muito próximo ao verde no gama de cores analisado.

Da mesma maneira que na seção 5.2.2, aumentando-se a magnitude do erro introduzido

para testar a robustez da rotina, temos os resultados na Figura 5.17 para 50 % de magnitude

de ruído. Nota-se uma piora, em que os tons de laranja e vermelho, branco e azul, e verde

e branco são confundidos, pela mesma razão.

Nota-se a classificação quase inexistente neste caso, tal como na Figura 5.17b. A segmen-

tação neste caso é percebida apenas como pequenas aglomerações próximas a cores

semelhantes. As Figuras 5.17c, 5.17d e 5.17e mostram exemplos de cores classificadas

desta maneira.

5.2.4 Distorção gaussiana e adição de ruído

Uma simulação mais próxima possível do real é onde ambos os casos anteriores são

ocorrentes: considerando-se a lente manchada e o sensor CMOS operando com ruído.

44

(a) Imagem original(b) Resultado para a classifi-

cação do cubo(c) Classificação incorreta en-

tre branco e azul

(d) Classificação ambígua deazul

(e) Classificação ambígua deazul

Figura 5.17 – Resultados para 50% de ruído gaussiano

Corrompendo-se a imagem com 2 pixels de raio de distorção gaussiana e 20 % em

magnitude de ruído branco, temos os resultados apresentados na Figura 5.18.

(a) Imagem original(b) Resultado para a classifi-

cação do cubo(c) Classificação incorreta en-

tre laranja e vermelho

(d) Classificação incorreta en-tre verde e amarelo

(e) Classificação de azul ebranco

Figura 5.18 – Resultados para 20% de ruído gaussiano

45

Analisando-se a Figura pode-se notar que o algoritmo funciona parcialmente. Enquanto as

Figuras 5.16e, 5.18d e 5.18e mostram certa classificação ambígua de cores de crominâncias

próximas, o problema pode ser resolvido aplicando um filtro de reconstrução.

5.3 Uma simulação em ambiente real

Após realizadas as simulações modelando-se duas características de imperfeições reais,

os mesmos algoritmos são aplicados a uma foto real capturada do cubo.

A localização do Cubo utilizando pré-processamento de contraste é descrita na Figura 5.19.

Nota-se que apenas uma característica foi identificada, entretanto não é um outlier. Explica

isto o fato do vértice da faceta branca ter sido identificado com outro na imagem buscada.

Figura 5.19 – Localização do Cubo sem pré-processamento

A Figura 5.20 mostra os resultados utilizando-se equalização de histograma e correção de

iluminação. Nota-se que mais características foram comparadas com sucesso, no entanto

houve formação de outliers na faceta branca do Cubo. Isto é explicado pelo fato das

características serem muito parecidas.

Os resultados para a classificação utilizando k-médias são descritos na Figura 5.21.

Analisando-se a classificação na Figura 5.21b, nota-se uma classificação pouco incorreta

de bordas. Este problema é gerado pelo fato do método das k-médias exigir um número de

clusters prévio ao processamento. No entanto, os centróides do algoritmo são colocados

inicialmente sem referência. A Figura 5.21c mostra o resultado desta classificação incorreta.

O problema pode ser solucionado colocando-se referências iniciais para os centróides,

evitando-se assim a criação incorreta de clusters.

46

Figura 5.20 – Localização do Cubo sem pré-processamento

(a) Imagem original(b) Resultado para a classifi-

cação do cubo(c) Classificação incorreta de

bordas

(d) Classificação da cor la-ranja (e) Classificação da cor azul

Figura 5.21 – Resultados para uma imagem real do cubo

5.4 Considerações Finais

Pode-se afirmar acerca da localização do Cubo que:

1. Mesmo a comparação de duas imagens semelhantes pode ocasionar comparações

errôneas.

2. A comparação é limitada quando existe desfoque na imagem.

47

3. As bordas bem definidas podem resultar em comparações incorretas caso existam

em ambas as imagens.

4. O pré-processamento de constraste pode ser útil na remoção de outliers, bem como

em explorar novas características SURF que não seriam detectadas previamente.

Em relação aos resultados de classificações do Cubo, infere-se:

1. Imagens bem construídas do Cubo levam a uma melhor classificação.

2. Desfoque gaussiano pode ser um problema, uma vez que reconhece incorretamente

as bordas das facetas, dado o seu alisamento.

3. Ruído é prejudicial, uma vez que o algoritmo tenta classificar pontos que são foras da

curva.

48

Capítulo 6

Conclusões

Muito se pode concluir com os dados analisados neste trabalho de conclusão de curso. As

suas principais realizações dividem-se em duas grandes áreas: 1) Análises em cores do

Cubo, e 2) Uso de características SURF e k-médias para aplicação em processamento de

imagens.

6.1 Conclusões sobre o Cubo de Rubik e Visão Computacio-

nal

Visão Computacional do Cubo é uma boa análise de benchmarking: suas características

bem definidas, tais como forma geométrica, cores e bordas favoráveis, fazem do quebra-

cabeças um foco para análise de performance de um sistema de VC já construído. Uma vez

que existem muitos estudos nesta área acerca do tema, comparar o tempo de processa-

mento e custo computacional pode ser uma tarefa relativamente simples.

Processamentos em cores têm como gargalo operações em matrizes: o maior tempo

gasto nas simulações foi na classificação de cores da imagem. A natureza matricial

da mesma em sistemas digitais faz com que operações de tratamento e segmentação

utilizem frequentemente cálculos em matrizes de ordens muito elevadas, sendo estes

processamentos computacionais lentos.

O Cubo é um bom objeto de estudo para análise de bordas: o caráter de facetas de

cores diferentes adjacentes leva a altas frequências espaciais, o que, consequentemente,

caracteriza bordas bem definidas. Isto pode ser útil em diversos estudos na área de visão

computacional, tais como detecção de face, dentre outros.

Cores semelhantes são um problema de classificação: nas simulações realizadas, pode-

se observar que algumas facetas de cores semelhantes foram classificadas de maneira

incorreta. Uma sugestão para melhorar-se a precisão da segmentação é o uso de filtros

49

auto-recursivos para análise da classificação, e/ou centróides melhor posicionados para

evitar mínimos locais heurísticos.

A compactação da imagem deve ser escolhida com cuidado: percebe-se a partir das

simulações realizadas que as cores brancas podem ser confundidas com o fundo da

imagem, caso o mesmo seja branco. Compactações que aceitam regulação de opacidade -

transparência - podem ser uma boa solução para o problema.

As características de iluminância podem ser desconsideradas em alguns casos: especifi-

camente, a resolução do Cubo de Rubik envolve apenas os valores perceptíveis de cor -

cromaticidade - da imagem. Por este motivo, casos semelhantes podem ser tratados de

maneira similar a este trabalho.

Ruído e distorção são um problema sério: Na implementação simulada são verificados

diferentes casos nos quais a imagem é corrompida propositalmente com ruídos e distorções,

o que leva a classificações errôneas.

6.2 Conclusões sobre os resultados

A utilização de pré-processamento descrita na seção 4.3.1.1 levou a uma melhora signifi-

cativa dos resultados. Contudo, deve ser utilizada com cautela, uma vez que pode reduzir

muito o número de comparações bem-sucedidas.

O uso de Filtros Bidimensionais de Wiener pode auxiliar na recuperação de eventuais ruídos

e desfoques tanto nas imagens para localização quanto para classificação.

Características SURF são um método robusto e eficaz para o problema de localização

do Cubo, entretanto possuem limitações, como por exemplo a geração de comparações

errôneas e a falta de características comparadas.

O método das k-médias pode ser utilizado para uma implementação simples e rápida para

este problema, desde que processadas em um espaço exclusivo de crominância.

6.3 Considerações Finais

A proposta de processamento de imagens do Cubo é atendida. Consideram-se possíveis

trabalhos futuros:

1. Implementação dos algoritmos utilizados em linguagem python, utilizando-se o pacote

OpenCV, para a construção efetiva de um robô resolvedor do Cubo.

2. Estudo de melhoria de extração de características para uma localização mais eficiente.

3. Métodos de eliminação do problema de ruídos na classificação.

50

4. Utilização de Redes Neurais Convolucionais para o processamento da localização.

51

Referências

BAY, H.; TUYTELAARS, T.; Van Gool, L. Surf: Speeded up robust features. Lecture notesin computer science, v. 3951, p. 14, 2006. ISSN 03029743. Disponível em: <http://www.springerlink.com/index/e580h2k58434p02k.pdf>. Acesso em: 06 de junho de 2015. Citado3 vezes nas páginas 29, 30 e 31.

ENGINEERING Statistics Handbook - Histogram. 2015.Http://www.itl.nist.gov/div898/handbook/eda/section3/histogra.htm. Acesso em: 26de novembro de 2015. Citado na página 19.

GONZALEZ, R. C.; WOODS, R. E. Digital Image Processing. 2. ed. New Jersey, NJ:Prentice Hall, 2002. Citado 3 vezes nas páginas ix, 11 e 23.

HACK, J.; SHUTZBERG, K. Rubiks Cube Localization, Face Detection, and InteractiveSolving. Stanford, CA: University of Stanford, 2015. Disponível em: <http://cs231n.stanford.edu/reports/jaykevin_final.pdf>. Acesso em: 20 de maio de 2015. Citado 5 vezes naspáginas ix, 2, 5, 6 e 7.

HOFFMANN, G. CIELab Color Space. Emden, Germany: [s.n.], 2007. Disponível em:<http://docs-hoffmann.de/cielab03022003.pdf>. Acesso em: 04 de junho de 2015. Citado 3vezes nas páginas ix, 15 e 18.

HOFFMANN, G. CIEXYZ Color Space. Emden, Germany: [s.n.], 2007. Disponível em:<http://docs-hoffmann.de/ciexyz29082000.pdf>. Acesso em: 06 de junho de 2015. Citado 4vezes nas páginas ix, 16, 17 e 18.

HU, X. et al. Design of an embedded vision system for the rubik’s cube robot. Proceedingof the IEEE, 2011. Citado 2 vezes nas páginas 2 e 8.

JÄHNE, B. Digital Image Processing. 6. ed. Holanda: Springer, 2005. Citado 5 vezes naspáginas ix, 14, 15, 17 e 23.

KASPRZAK, W.; SZYNKIEWICZ, W.; CZAJKA, L. Rubik’s Cube Reconstruction fromSingle View for Service Robots. Home page of Wlodzimierz Kasprzak, 2006. Disponívelem: <http://www.ia.pw.edu.pl/wkasprza/PAP/ICCVG06.pdf>. Acesso em: 20 de maio de2015. Citado 4 vezes nas páginas ix, 6, 7 e 8.

KOSCHAN, A.; ABIDI, M. Digital Color Image Processing. 1. ed. New Jersey, NJ: Wiley-Interscience, 2008. Citado 6 vezes nas páginas ix, 13, 14, 16, 19 e 23.

MATHWORKS. Image Processing Toolbox Documentation. Natick, MA,2015. Disponível em: <http://www.mathworks.com/help/images/examples/color-based-segmentation-using-k-means-clustering.html>. Acesso em: 31 de maiode 2015. Citado na página 8.

MATHWORKS. Image Processing Toolbox User’s Guide. Natick, MA, 2015. 712 p. Acessoem: 20 de abril de 2015. Citado 3 vezes nas páginas x, 30 e 41.

52

POGGIO, T.; TORRE, V.; KOCH, C. Image Understanding. 1. ed. Norwood, NJ: AblexPublishing Corporation, 1989. Citado 2 vezes nas páginas 1 e 23.

PRATT, W. K. Digital Image Processing. 4. ed. Los Altos, California: Wiley-Interscience,2007. Citado 9 vezes nas páginas ix, x, 12, 23, 24, 25, 26, 32 e 33.

RUBIKS.COM. The History of the Rubik’s Cube. 2015. Disponível em: <https://www.rubiks.com/about/the-history-of-the-rubiks-cube>. Acesso em: 20 de abril de 2015. Citado 3 vezesnas páginas ix, 1 e 2.

TSAI, C. Accentuating Features by Decimation, Contrast Enhancement, Filtering. 2008.Disponível em: <http://people.csail.mit.edu/halordain/2D%20Imaging/Chris%20Tsai%20-%20Preprocessing%20for%20Features.pdf>. Acesso em: 06 de junho de 2015. Citado 6vezes nas páginas 27, 28, 29, 30, 34 e 37.

VEDALDI, A. Scale Invariant Feature Transform. 2013. Disponível em: <http://www.vlfeat.org/api/sift.html>. Acesso em: 06 de junho de 2015. Citado 2 vezes nas páginas x e 31.

YAGER, P.; LOK, J.; KLIG, J. Advances in simulation for pediatric critical care and emer-gency medicine. 2011. Disponível em: <http://journals.lww.com/co-pediatrics/Abstract/2011/06000/Advances_in_simulation_for_pediatric_critical_care.7.aspx>. Acesso em: 13 desetembro de 2015. Citado na página 2.

53