Aluna: Ana Beatriz Vicentim Graciano
abvg@ime.usp.br
Orientador: Roberto Marcondes Cesar Junior
Prof. Responsável: Carlos Eduardo Ferreira
No 
semestre de 2001, cursei a disciplina MAC 417 - Visão e Processamento de Imagens - como optativa eletiva do curso de Ciência da Computação. Essa área sempre me interessou, pois tem aplicações relacionadas à biogenética, medicina, interação homem-computador, robótica, automação industrial, edição de vídeo, dentre tantos outros campos de natureza diversa.
Através dessa experiência com a disciplina, surgiu a oportunidade de participar de um projeto de iniciação científica, que poderia também ser aproveitado como projeto de formatura, proposto pelo professor Roberto Marcondes Cesar Jr. Especificamente, o trabalho está ligado à aplicação de Processamento de Imagens em edição de vídeo digital.
As próximas seções tratam desse trabalho e da experiência adquirida através do mesmo. Em particular, a Parte I apresentará toda a descrição técnica do projeto, enquanto a Parte II relatará a experiência pessoal, as dificuldades enfrentadas, os acertos e a importância da formação obtida no IME.
Além disso, as técnicas computacionais existentes [7, Apêndice A] ainda necessitam de aperfeiçoamento, pois, dependendo da complexidade do objeto, nem sempre produzem resultados satisfatórios ou impõem diversas restrições. Muitas vezes, os objetos segmentados apresentam bordas com reentrâncias indesejáveis ou mesmo incoerência espacial entre os recortes obtidos a partir de quadros consecutivos da seqüência de vídeo.
O objetivo principal desta pesquisa é, portanto, propor soluções para o aprimoramento dos resultados obtidos aplicando-se a metodologia de segmentação de objetos em seqüências de vídeo proposta por Franklin C. Flores em sua dissertação de mestrado [7]. Tal metodologia baseia-se em ferramentas de aprendizado computacional e de morfologia matemática, respectivamente. Em particular, a segmentação automática dos objetos é dada através da aplicação do paradigma de Beucher-Meyer, o que permite a detecção exata das bordas dos mesmos.
Nas próximas seções, serão apresentadas as etapas da metodologia supracitada, os problemas encontrados nos resultados, as soluções derivadas a partir deste projeto e os aprimoramentos conseguidos.
Assim como é possível observarmos um objeto em especial ao assistirmos um vídeo, podemos desejar perseguir um ou mais objetos de uma seqüência automaticamente através de algoritmos e recursos computacionais. Então, utilizaríamos esses objetos observados, por exemplo, sobre um fundo diferente de acordo com o interesse.
Para que um objeto seja observado automaticamente ao longo de uma seqüência de quadros, duas etapas devem ser levadas em consideração:
Seja
um subconjunto retangular finito de pontos, ![$K = [0, k]$](img3.gif){kind=small}
um intervalo fechado em 
, e
![$F[E,K] = \{f: E \rightarrow K\}$](img5.gif){kind=small}
. Uma imagem é dada por uma função ![$f \in F[E,K]$](img6.gif){kind=small}
. Um conjunto de pixels de 
é um subconjunto finito do conjunto Imagem 
de .
Para encontrar um conjunto de pixels constituintes de um dado objeto de estudo no quadro, [7] propõe a aplicação de operadores aperture. Tais operadores são construídos através de técnicas de aprendizado computacional, que consistem no estudo de métodos computacionais que permitam o aprendizado de um dado conceito. No caso dos operadores aperture, o conceito fundamental envolvido é a caracterização dos mesmos por funções específicas, que associam uma função a um valor inteiro.
Para que os marcadores sejam impostos sobre os objetos ao longo de toda a seqüência, é necessário que o usuário defina manualmente quais objetos serão perseguidos no primeiro quadro em que aparecem. Essas regiões marcadas manualmente servem para treinar os operadores aperture. Após essa interação, os objetos podem ser detectados nos quadros subseqüentes pelos operadores aperture, que impõem os marcadores adequadamente.
Portanto, para cada quadro da seqüência, é gerada uma imagem contendo marcadores que indicam os objetos de interesse. Essas imagens 
com marcadores possuem o seguinte formato:
e 
são, respectivamente, um majorante e um minorante de 
, ou seja, os pixels que pertencem aos marcadores para os objetos possuem nível de cinza máximo e os restantes possuem nível de cinza mínimo.
A segmentação dos objetos detectados e marcados pelos operadores aperture é realizada quadro-a-quadro através da aplicação do Paradigma de Beucher-Meyer. Tal paradigma permite a detecção exata das bordas dos objetos de interesse através da aplicação do operador watershed em uma imagem com as seguintes características:
A próxima seção descreve detalhadamente o funcionamento do Paradigma de Beucher-Meyer.
Para entendermos o funcionamento do Paradigma de Beucher-Meyer, vamos definir primeiramente o conceito de operador morfológico. Um operador morfológico ([7]) é um operador decomponível em termos de operações e operadores elementares. Para realizarmos tal decomposição, utilizamos a linguagem formal conhecida como linguagem morfológica, cujos operadores são a erosão e a dilatação , e cujas operações são supremo, ínfimo, negação e composição. Um operador morfológico compõe uma frase nessa linguagem.
Sejam e 
![$\in F[E,K]$](img15.gif){kind=small}
, onde ![$E, K, F[E, K]$](img16.gif){kind=small}
foram definidos anteriormente. Seguem, então, as definições matemáticas dos operadores e operações da linguagem morfológica:
, sendo 
o maior elemento de 
, onde
![$\psi _{1}: F[E,K] \rightarrow F[E,K]$](img23.gif){kind=small}
e
![$\psi _{2}: F[E,K] \rightarrow F[E,K]$](img24.gif){kind=small}
são dois operadores.
O Paradigma de Beucher-Meyer busca a segmentação exata das bordas dos objetos de estudo, consistindo na aplicação seqüencial dos seguintes operadores morfológicos:
A sequência de figuras abaixo mostra o efeito da aplicação desses operadores sobre um quadro.
(a) |
(b) |
Essa primeira etapa do paradigma tem o propósito de reforçar as bordas ou contornos do quadro 
em que ocorrerá a segmentação. As bordas da imagem são caracterizadas por transições dos níveis de cinza da mesma, ou seja, descontinuidades da imagem (regiões de mudanças bruscas).
Seja 
o elemento estruturante [8, Cap. 3] igual ao losango ou ao quadrado elementar, o operador gradiente morfológico de pode ser definido como [8]:
Assim, o operador gradiente resulta da subtração entre dois outros operadores morfológicos: dilatação e erosão de .
Logo, o resultado desse operador sobre é uma nova imagem cujas bordas são realçadas.
Nesse passo, eventuais ruídos também podem ser ressaltados pelo operador, o que acarreta supersegmentação do resultado após a aplicação do operador watershed na fase final do paradigma. Para contornar esse problema, realiza-se um procedimento chamado filtragem homotópica, visto a seguir.
Nessa etapa, o objetivo é filtrar o resultado do gradiente para evitar a supersegmentação do resultado final. Assim, deseja-se obter um gradiente filtrado cujos mínimos regionais representem os objetos que se quer segmentar.
Para isso, constrói-se uma imagem contendo somente marcadores para os objetos do frame. Como visto anteriormente, tal imagem é obtida pelo uso dos operadores aperture. 
tem valor igual ao maior nível de cinza para os pixels de que pertencem ao objeto, e igual ao menor nível de cinza para aqueles que não constituam o objeto de interesse.
A filtragem é então realizada através do operador de mudança de homotopia, que realiza uma reconstrução da imagem pela imagem com os marcadores. Tal filtragem é composta de:
).
e , resultando numa imagem 
cujos pixels pertencentes aos marcadores possuem o menor nível de cinza, enquanto os outros possuem o valor do nível de cinza correspondente em .
a partir de , que consiste da erosão infinita de condicionada à imagem .
Com isso, obtemos uma nova imagem 
contendo apenas os mínimos regionais relativos aos objetos marcados.
O último passo do paradigma consiste na aplicação do operador watershed sobre a imagem resultante , obtendo uma nova imagem apenas com as bordas dos objetos segmentados. De posse dessa imagem, é possível realizar a combinação do objeto ou do fundo com uma outra sequência de vídeo.
O operador watershed (ou linha de partição de águas) é uma das ferramentas de segmentação de imagens mais eficientes e utilizadas dentro da morfologia matemática, pois apresenta considerável desempenho em relação às outras abordagens.
A idéia básica do operador watershed pode ser exemplificada através da seguinte analogia. Uma imagem em níveis de cinza pode ser vista como uma superfície cujos pontos têm altitudes relativas aos valores dos pixels. Quanto maior o valor do nível de cinza correspondente, maior a altitude. Como as bordas dos objetos já foram ressaltadas pelo operador gradiente, a superfície seria formada de vales e bacias. Ainda, pode-se imaginar que essa superfície é imersa em água, a partir dos pontos mais baixos. Conforme o nível de água nas bacias e vales aumenta, as águas dessas bacias transbordam e tocam aquelas provenientes de outras bacias. Nesse ponto, são construídas barragens para evitar a união dessas águas, daí o nome de "linha de partição de águas".
Esse processo pode ser representado matematicamente através de operadores morfológicos.
Um mínimo regional de altitude h da função é um conjunto conexo de pontos de 
tal que seus elementos possuem o valor 
.
Seja 
. A seção inferior de no nível é o conjunto definido por
. Computacionalmente, esse conceito pode ser implementado através de um histograma dos níveis de cinza encontrados em , bem como seus valores supremo 
e ínfimo 
. De posse desse resultado, faz-se uma ordenação dos endereços dos pixels de de acordo com seus níveis de cinza, para facilitar o acesso às posições da imagem que possuem valores iguais. Isso permite a "inundação" da superfície a partir dos níveis de cinza mais baixos até os mais altos.
Agora, é necessário definir o conjunto das bacias de captação de água de , dado pelo seguinte conjunto 
obtido através da seguinte recorrência:
O conjunto IZ é conhecido como zona de influência geodésica de 
, que reúne os pixels vizinhos ao conjunto de cuja distância a é menor do que a qualquer outro conjunto. Em termos algorítmicos, essas bacias são encontradas por meio de rótulos dados aos pixels e utilizando-se o vetor ordenado por níveis de cinza contendo os endereços dos pixels correspondentes.
As linhas de partição de águas de são formadas pelo conjunto complementar das bacias de captação de . Nesse caso, o algoritmo marca os pixels que têm possibilidade de receber dois rótulos diferentes, o que indica que as águas de duas bacias distintas se encontraram.
Uma explicação detalhada de implementações eficientes do algoritmo de watershed pode ser encontrada em [8] ou em [4].
A imagem 
resultante do operador watershed sobre o 
ésimo quadro da sequência é binária e possui dimensões iguais às do quadro original. Porém, seria interessante obter uma estrutura que contivesse apenas os pixels representantes do recorte, pois a mesma permitiria maior eficiência ao ser usada em computações posteriores. Além disso, o consumo de memória também seria reduzido consideravelmente.
Para isso, pode-se aplicar a todas as imagens resultantes do paradigma de Beucher-Meyer um algoritmo de extração de contorno, que, dada uma imagem binária, encontra os pixels pertencentes ao contorno dos objetos presentes em e armazena as coordenadas dos mesmos numa estrutrura como vetor, lista ligada ou até mesmo em arquivo. Neste projeto, optou-se por utilizar dois vetores como saída do algoritmo: um para armazenar as coordenadas 
dos pixels pertencentes ao contorno, e outro para as coordenadas 
.
Existem vários algoritmos distintos para a extração de contornos paramétricos de uma imagem. Para este projeto, foi utilizado o algoritmo contour following descrito em [2, Cap. 5]. Tal algoritmo extrai o contorno externo (vide [2]) dos objetos presentes na imagem.
O funcionamento do algoritmo está centralizado no fato de que, numa imagem binária, sabe-se que o fundo é representado por pixels brancos, enquanto os objetos são formados por pixels pretos. Dessa forma, é possível percorrer a imagem em busca de pixels vizinhos a ``pixels pretos'', ou seja, que constituam os contornos.
Na primeira etapa do algoritmo, a imagem é visitada linha a linha em busca de um pixel branco e cujo vizinho à direita é preto. Uma vez encontrado esse pixel inicial, o processo de extração do contorno é iniciado. O que é feito, na verdade, é uma busca pelos pixels que circundam o objeto até encontrar o pixel inicial novamente.
Para circundar o objeto, utiliza-se uma máscara 
com pixels 8-conectados, concêntrica ao pixel corrente pertencente ao contorno. Os pixels dessa máscara são acessados de acordo com a seguinte ordenação: o pixel vizinho à direita do pixel central da máscara tem rótulo 0, e os pixels seguintes, percorridos no sentido anti-horário, possuem rótulos 2, 3, 4, 5, 6, 7.
A partir do pixel pertencente ao contorno atual, analisa-se qual o próximo pixel a ser obtido. Para isso, a máscara é percorrida no sentido anti-horário, novamente em busca de um pixel cujo valor é zero e cujo vizinho correspondente no código da cadeia é preto. O procedimento acaba quando o pixel inicial é revisitado.
O algoritmo de extração de contornos de imagens binárias foi implementado em C, tendo sido um dos projetos avaliados na disciplina MAC 447 - Análise e Reconhecimento de Formas: Teoria e Prática, oferecida pelo IME - USP e ministrada pelo Prof. Dr. Roberto Marcondes Cesar Junior, no período de Agosto a Novembro de 2001.
Para permitir o uso desse algoritmo dentro do ambiente do MATLAB
, o programa foi adaptado para comportar a interface entre funções do software e códigos . Para isso, as modificações necessárias consistem basicamente da criação de uma função chamada mexFunction, que substitui a função main tradicional de , e das seguintes transformações:
. No ambiente MATLAB, os dados são mantidos em vetores e matrizes. Porém, programas em podem utilizar estruturas de dados mais adequadas e eficientes para determinados tipos de aplicação. Devido a esse fator, é necessário o mapeamento dos dados.
Uma vantagem de se usar programas escritos em código dentro do ambiente do MATLAB é o fato do código ser compilado, o que permite maior eficiência durante a execução, pois os comandos são executados diretamente. Já os programas escritos na linguagem para o MATLAB, chamados scripts, são interpretados ao serem executados, levando a um processamento mais lento. Como as imagens tendem a ter tamanhos variados e o algoritmo de extração de contornos deve percorrê-las completamente, é interessante utilizar o recurso dessa interface, para não incrementar consideravelmente o tempo de processamento total da sequência de vídeo.
O fator preponderante na busca da coerência espacial é aproximar os contornos obtidos entre os quadros e 
, o que é feito através do algoritmo de interpolação de contornos. Todos os objetos recortados em cada quadro da sequência têm seus contornos extraídos e interpolados ao contorno do quadro anterior, que é previamente guardado. A interpolação só não é realizada no quadro da sequência, pois apenas um contorno está disponível nesse ponto.
A entrada desse algoritmo são dois contornos, ou vetores no formato obtido do algoritmo de extração de contornos, e o número de pontos que se deseja usar na interpolação. O resultado obtido é um novo contorno a ser submetido à filtragem passa-baixas.
Um exemplo do resultado da interpolação dos contornos pode ser visto abaixo.
(a) |
(b) |
obtido após a interpolação dos contornos. Como o contorno é representado por um sinal unidimensional, a computação adicional é relativamente baixa.
Uma filtragem passa-baixas é caracterizada por atenuar os componentes de alta freqüência de uma função ou imagem, permitindo a passagem de baixas freqüências. No caso de uma imagem, as altas freqüencias são representadas pelas bordas dos objetos pois, matematicamente, elas podem ser consideradas picos ou pontos de inflexão entre regiões. Como os contornos são boas representações das bordas dos objetos, utiliza-se um filtro passa-baixas sobre os mesmos, atenuando o efeito das bordas e conseguindo suavizar reentrâncias nas mesmas, como é possível ver na figura abaixo.
Um dos métodos de filtragem passa-baixas mais utilizado é a filtragem gaussiana. Isso se deve à facilidade computacional de sua aplicação, pois tal filtro pode ser implementado utilizando-se propriedades de derivação da transformada de Fourier (vide [2], [6], [1]). Como a transformada de Fourier é computacionalmente viável e eficiente, tal filtragem foi também a escolhida para a suavização das bordas dos objetos segmentados nos quadros da seqüência.
A suavização gaussiana foi também implementada através de funções dos toolboxes de processamentos de imagens e de sinais do software MATLAB.
Embora a utilização de operadores aperture resulte em marcadores satisfatórios para os objetos de interesse, [7] propôs o estudo de operadores ou técnicas adaptativas para detecção de marcadores como possível campo de continuidade de seu trabalho. Essa extensão permitiria maior flexibilidade na busca de marcadores caso a sequência de imagens apresentasse considerável variação qualitativa entre os quadros como, por exemplo, mudanças de iluminação.
Para abordar esse aspecto adaptativo, foram estudados os seguintes métodos:
Como fonte de apoio para esses tópicos, foram também estudados alguns artigos ( [5], [3]).
De posse dessas ferramentas, será possível analisar e propor uma combinação de características a serem consideradas na busca dos marcadores, na tentativa de reduzir razoavelmente a dependência entre os marcadores e a homogeneidade dos quadros. Esses fatores poderão ser extraídos quadro-a-quadro e atualizados para que se adaptem ao longo da sequência.
No caso da minha iniciação, o problema já estava bem definido, restando propor soluções aos resultados da metodologia desenvolvida anteriormente. Em relação à parte teórica, foi possível encontrar muitas fontes bibliográficas que facilitaram o entendimento do problema e propiciaram o encaminhamento das soluções. Porém, na prática, nem sempre foi fácil atingir os objetivos. Às vezes, um fator não considerado previamente levava à reformulação do método, o que consumia um certo tempo.
Outro fator que dificultou um pouco a implementação do projeto foi o fato de eu não saber programar para o MATLAB. Embora seja uma linguagem relativamente simples e com muito suporte funcional, precisei de um certo tempo para compreendê-la tão bem quanto eu sei utilizar C. A opção pelo MATLAB deve-se à ampla utilização desse software no laboratório de Visão e Processamento de Imagens, o que tornaria o projeto uma ferramenta que todos os que quisessem poderiam usar. Originalmente, a metodologia apresentada havia sido implementada em C, na forma de bibliotecas para o software Khoros, que não é tão conhecido quanto o MATLAB.
Além disso, aprendi também como utilizar programas em C dentro do MATLAB através da interface que este oferece: os arquivos mex. Através deles, pudemos adaptar o algoritmo de extração de contornos, como visto anteriormente. Ainda, aprendi como usar as funções do toolbox de Morfologia Matemática para o MATLAB. Isso facilitou a obtenção dos resultados, mas, ao mesmo tempo, dificultava um pouco quando as coisas não saíam como se esperava. Quando não se sabe como são implementados os algoritmos, é mais complicado descobrir onde podem estar os problemas.
Por fim, como o paradigma e suas soluções consistiam de diversos scripts diferentes, o uso de uma interface gráfica facilitaria a manipulação do processo. Para isso, aprendi a desenvolver também interfaces dentro do MATLAB, o que não foi uma tarefa muito fácil. Precisei me preocupar com questões de compatibilidade entre as versões do MATLAB para Windows e Linux/Unix, manipulação dos callbacks, facilidade de uso da interface, entre outros fatores. Porém, o problema principal que encontrei nessa etapa foi a documentação do MATLAB para interfaces gráficas. Apesar do help ser bem completo, há muita informação e é difícil entender o funcionamento básico das interfaces dele. Com a ajuda de um documento encontrado na internet, foi possível utilizar, finalmente, essa funcionalidade do MATLAB.
Desde então, ele sempre procurou me integrar aos outros membros do grupo de visão computacional do IME, o Creativision, além de mostrar-se disponível para esclarecer dúvidas e problemas, e para auxiliar no que fosse necessário. Ainda, incentivou a participação em seminários da área ou de trabalhos correlatos e apoiou a inscrição em eventos científicos como o SIICUSP, que possibilitou o contato com outros trabalhos de iniciação científica e permitiu uma experiência nova de apresentação do projeto para públicos diversos.
Uma outra experiência interessante foram as reuniões semanais realizadas entre o professor e os outros alunos sob sua orientação. Nesses encontros, podíamos apresentar as dúvidas, discutir o andamento dos projetos e conhecer também os trabalhos de cada um. Isso tudo facilitava a solução de problemas mais práticos, por exemplo, quando se tratava da manipulação de um determinado software.
Apesar do meu projeto ser baseado numa tese produzida no IME, não tive muito contato com o autor Franklin Cesar Flores. Ele se disponibilizou uma vez, mas relativamente no começo do projeto, quando eu ainda não conhecia tão bem a teoria. Nesse encontro, ele me explicou genericamente como o paradigma de Beucher-Meyer era utilizado e também como funcionavam os operadores aperture. Além disso, ele permitiu com que eu tivesse acesso aos scripts e às sequências de vídeo que havia usado na elaboração da tese. Outras dúvidas que surgiram foram esclarecidas por email, mas poucas vezes.
Uma experiência que gostaria de tentar no futuro é a participação num projeto em que houvesse mais pessoas envolvidas, pois acredito que isso contribua para a troca de informações e também para a análise dos problemas e a metodologia que se deve aplicar para atingir os objetivos da pesquisa.
Além da iniciação científica, também tive a oportunidade de participar das seguintes atividades:
A formação oferecida pelo IME foi fundamental para os meus conhecimentos em computação, pois, quando entrei no BCC, eu era apenas uma usuária curiosa de computadores e jamais havia programado.O interesse por matemática e por aplicações de computação em efeitos especiais e medicina foram os fatores que me levaram a optar por um bacharelado em computação. Por isso, tudo o que eu sei hoje se deve ao BCC de uma forma ou outra.
Em relação à formação geral, as seguintes disciplinas foram muito importantes, pois permitiram o contato com algoritmos e conceitos fundamentais de computação, bem como a prática de programação: Princípios de Desenvolvimento de Algoritmos, Estruturas de Dados, Laboratórios de Programação I e II e Conceitos de Linguagens de Programação.
Quanto ao projeto, as seguintes disciplinas foram fundamentais ou auxiliares:
Em relação à continuidade da pesquisa, serão implementadas as técnicas estudadas para a busca automática de marcadores para os objetos ao longo da seqüência, pois esse é um problema clássico mas que ainda comporta inovações.
