WRVA2008_ApostilaTutorialReconhecimentoPadroesTempoReal

Reconhecimento de Padres em Tempo Real Utilizando a Biblioteca OpenCVJoo Paulo Silva do Monte Lima1 Daliton da Silva1 Veronica Teichrieb1 Judith Kelner1

Resumo: Reconhecimento de padres em tempo real uma tarefa crucial emvrias reas, tais como Realidade Aumentada, Robtica e Interao Homem Computador. A biblioteca OpenCV uma soluo open source para viso computacional que prov vrias funcionalidades adequadas para esse tipo de aplicao. A implementao do OpenCV contm vrias otimizaes que favorecem uma boa performance. Ela tambm prov funcionalidades simples de usar (out of the box) para interface com o usurio, carregamento de imagens e captura de vdeo. O objetivo deste minicurso mostrar o potencial do OpenCV para reconhecimento de padres com restries de tempo real. Sero apresentadas as principais funes de processamento de imagem presentes no OpenCV que podem ser usadas em sistemas de reconhecimento de padres, em tempo real. Os algoritmos implementados sero explicados, juntamente com informaes sobre como eles podem ser utilizados e sua aplicabilidade a

Grupo de Pesquisa em Realidade Virtual e Multimdia, Centro de Informtica, UFPE, Av. Professor Moraes Rego S/N, Prdio da Positiva, 1 Andar, Cidade Universitria, Recife, Pernambuco, CEP 50670-901 {jpsml, ds2, vt, jk @cin.ufpe.br}

1

Reconhecimento de padres em tempo real utilizando a biblioteca OpenCV

problemas reais. Exemplos de aplicaes tambm sero apresentadas de forma a ilustrar o uso das funcionalidades de viso computacional descritas.

Abstract: Real-time pattern recognition is a crucial task of systems appliedto several fields, such as Augmented Reality, Robotics and Human Computer Interaction. The OpenCV library is an open source solution for computer vision that provides many features suitable for this kind of applications. OpenCV implementation contains many optimizations that favor a good processing performance. It also provides out of the box functionalities for user interface, image loading and video capture. The goal of this tutorial is to show OpenCVs potential for pattern recognition with real-time constraints. A number of image processing functions featured by OpenCV that can be used in real-time pattern recognition systems will be enumerated. The implemented algorithms will be explained, along with information of how they can be utilized and their applicability to real life problems. Example applications will also be presented in order to illustrate the use of the described computer vision features.

2

RITA Volume XXXX Nmero X 20XX


1

Introduo

O OpenCV uma biblioteca open source para processamento de imagens offline e em tempo real. Ela pode ser utilizada em diversas e diferentes reas, como em interao homemmquina (Human-Computer Interaction, HCI), identificao de objetos, segmentao e reconhecimento, reconhecimento de faces, reconhecimento de gestos, rastreamento de movimentos, ego motion, compreenso de movimentos e Structure from Motion (SfM), e robtica mvel. A Tabela 1 apresenta uma descrio mais detalhada das funes suportadas pelo OpenCV. A biblioteca desenvolvida pela Intel, e est em desenvolvimento desde 2001, com a primeira verso liberada em outubro de 2006. Existem verses do OpenCV tanto para o sistema operacional Windows quanto para o Linux.Tabela 1. Principais funes do OpenCV

Fitragem, deteco de bordas, deteco de cantos, interpolao e amostragem, converso de cor, operaes morfolgicas, histogramas, pirmides de imagens. Anlise estrutural Componentes conexos, processamento de contornos, transformao de distncia, momento diverso, casamento de templates, aproximao poligonal, montagem de linha, montagem de elipse, triangularizao de Delaunay Calibrao de cmera Busca, rastreamento e calibrao de padres, calibrao, estimao de matrizes fundamentais, estimao homogrfica, correspondncia estreo. Anlise de movimentos Fluxo ptico, segmentao de movimentos, rastreamento Reconhecimento de objetos. Mtodos-eigen, Hidden Markov Models (HMM) GUI bsica Exibio de vdeo e imagens, tratamento de entrada do teclado e do mouse, barras de rolagens Labeling de imagens Linha, cnica, polgono, texto, desenho de texto O cdigo do OpenCV encontra-se disponvel para download e aberto para modificaes, desde que as clusulas da licena sejam obedecidas. O OpenCV foi escrito em C/C++, e prov suporte para desenvolvedores que utilizam o Microsoft Visual Studio, Eclipse Project e C++ Builder (quando utilizando Windows) e make files (quando utilizando Linux). OpenCV pode ser dividido em quatro mdulos: cv, cvaux, cxcore e highgui. O mdulo cv

Funa Manipulao de imagens IO de vdeo e imagem Manipulao de matrizes e vetores e retinas de lgebra linear Diversas estruturas de dados dinmicas Processamento de imagens bsico

Descrio Alocao, desalocao, cpia, modificao, converso Input e output baseado em arquivo e cmera Produto, soluo, single value decomposition (SVD) Listas, filas, pilhas, rvores, grafos


3


contm as funes padres podendo ser considerado o corao da biblioteca. O mdulo cvaux, como o nome sugere, implementa funes que suportam o uso do OpenCV. O mdulo cxcore responsvel pelas estruturas de dados e operaes de lgebra linear. Por fim, o mdulo highgui prov suporte para funes de GUI, como a exibio de janela contendo imagens capturadas pela webcam, por exemplo. 1.1 Motivao

Reconhecimento de padres em tempo real representa uma importante tarefa de aplicaes em diversas reas, como realidade aumentada, robtica e HCI. OpenCV prov funcionalidades para construo de interfaces com o usurio, leitura de imagens e captura de vdeo, por exemplo. A biblioteca OpenCV uma soluo de cdigo aberto para viso computacional que prov funcionalidades adequadas para aplicaes dos tipos listados anteriormente. A biblioteca foi definida para prover uma interface de programao simples, podendo ser facilmente integrada em outros projetos que j existam. Um importante problema envolvendo o reconhecimento de padres o pesado processamento exigido por esse tipo de tarefa. Por causa disto, o OpenCV contm otimizaes que resultam em bom desempenho para as suas aplicaes. Como o OpenCV implementado pela Intel, ele contm otimizaes especificamente desenvolvidas para os processadores da Intel. A Intel tem realizado investimentos de larga escala no desenvolvimento do OpenCV. Seus pesquisadores se dedicam ao desenvolvimento de novas funcionalidades para o OpenCV, que so incorporadas a biblioteca a cada nova verso distribuda. Como exemplo, pode-se citar a funo cvGoodFeaturesToTrack, baseada no trabalho de Carlo Tomasi [1]. 1.2 Licena

A licena do OpenCV permite a modificao e a livre distribuio do seu cdigo fonte e binrios, desde que certas condies sejam observadas. Entre essas condies, as seguintes so relevantes: - O cdigo fonte e os binrios distribudos devem conter todas as informaes listadas na licena original do OpenCV; - O nome da Intel ou qualquer uma de suas marcas no podem ser utilizados para promover o uso de aplicaes que utilizem OpenCV sem a prvia autorizao. 1.3 Instalao

O OpenCV pode ser instalado atravs de um wizard, disponvel em http://sourceforge.net/projects/opencvlibrary/, ou pode ser adquirido diretamente do CVS. As instrues para o uso do CVS esto disponveis em http://sourceforge.net/cvs/?group_id=22870. Em ambos os casos podem ser copiados o cdigo fonte e os binrios. Na sequncia, a instalao passo a passo do OpenCV descrita. A Figura 1 mostra a tela que aparece na instalao do OpenCV. Clicando no boto Next, a licena de usurio

4



exibida. Para aceitar os termos listados, o usurio deve clicar na opo I accept the agreement e clicar no boto next novamente. As trs telas seguintes do processo de instalao exibem as configuraes de instalao padres. A Figura 1 ilustra a primeira dessas telas. Depois de confirmar todas as opes, o OpenCV copiado para o disco rgido e estar pronto para o uso.

Figura 1. A primeira tela da instalao do OpenCV.

Para recompilar o cdigo do OpenCV utilizando o Microsoft Visual Studio, necessrio abrir o arquivo opencv.sln, localizado dentro da pasta _make. Desta forma todo o ambiente de desenvolvimento configurado para a correta compilao do cdigo. Na sequncia, o usurio clica em Build Solution, do menu Build, como ilustrado na Figura 2. Cada mdulo do OpenCV compilado em duas Iink libraries (.dll e .lib). Elas integram o OpenCV com projetos desenvolvidos pelo usurio.


5


Figura 2. Compilando o cdigo fonte do OpenCV.

1.4

Documentao

O OpenCV possui uma documentao completa, muitos fruns e grupos de discusso, resultando em um suporte eficiente para os usurios da biblioteca. A aplicao de instalao automaticamente copia uma srie de documentos de suporte ao usurio. Dentre estes documentos, o opencvman_old.pdf merece uma ateno especial, este o manual de referncia da biblioteca. Neste documento pode ser encontrada a descrio em detalhes das funes do OpenCV e cdigos de exemplos. O manual tambm explica conceitos gerais referentes ao OpenCV, como a definio de tipos de dados especficos e guias de implementao utilizados e processamento de imagens. O grupo de discusso sobre OpenCV est disponvel em http://tech.groups.yahoo.com/group/OpenCV. A documentao tambm est disponvel na instalao do OpenCV como um arquivo HTML, que uma verso mais simples porm mais freqentemente atualizada do manual. Quando o usurio se registra (o registro no grupo de discusso grtis) ele pode acessar uma extensa base de dados envolvendo questes prticas. O usurio tem a possibilidade de postar suas questes que no podem ser resolvidas utilizando a documentao existente. Existe uma grande chance de que a questo seja resolvida, pois a comunidade do OpenCV possui um grande nmero de membros ativos.

2

Funcionalidades

Este captulo explica um conjunto de funes do OpenCV relativas a vrios passos do pipeline de processamento de imagens. As funes relativas a pr-processamento,

6



segmentao, representao e reconhecimento so inseridas em um contexto e sua utilizao explicada. 2.1 Realce de imagens e seleo de caractersticas

O principal objetivo do realce de imagens processar uma imagem de forma que o resultado seja mais adequado do que a imagem original para um conjunto de aplicaes especficas. Existem basicamente duas abordagens para o realce de imagens: mtodos do domnio espacial e mtodos do domnio de freqncia. O termo domnio espacial se refere ao prprio plano de imagem, e abordagens nesta categoria so baseadas na manipulao direta de pixels de uma imagem. Tcnicas do domnio de freqncia so baseadas em modificar a transformada de Fourier de uma imagem. A biblioteca OpenCV trata somente um subconjunto de tcnicas do domnio espacial. Alm disso, neste captulo algumas funes relacionadas a seleo de caractersticas (por exemplo, arestas e cantos) so apresentadas. Suavizao. Filtros de suavizao so usados para borramento e reduo de rudo. O borramento usado em etapas de pr-processamento, tais como remoo de pequenos detalhes de uma imagem. Alm disso, a reduo de rudo pode ser feita atravs de um borramento usando um filtro linear e atravs de uma filtragem no-linear. Um exemplo de uso do borramento mostrado na Figura 3.

Figura 3. Imagem original (esquerda), um kernel uniforme (centro) e um kernel Gaussiano (direita).

Na biblioteca OpenCV, existe uma funo relativa a filtragem de suavizao chamada cvSmooth, e como a operao de suavizao nada mais que uma convoluo com uma matriz especfica, possvel usar a funo cvFilter2D. Ambas as funes so explicadas abaixo. void cvSmooth( const CvArr* src, CvArr* dst, int smoothtype,int param1, int param2, double param3 ); O argumento src a imagem de origem, dst a imagem de destino, smoothtype o tipo da suavizao que pode ser aplicada (todos os tipos esto listados na Tabela 2).


7

Reconhecimento de padres em tempo real utilizando a biblioteca OpenCV Tabela 2. Tipos de suavizao do OpenCV.

Descrio Somatrio em uma vizinhana de pixels param1param2 CV_BLUR Somatrio em uma vizinhana de pixels param1param2 com subseqente escala por 1/(param1param2) CV_GAUSSIAN Convoluo da imagem com um kernel Gaussiano param1param2 CV_MEDIAN Mediana de uma vizinhana de pixels param1param1 (ou seja, a vizinhana quadrada) CV_BILATERAL Aplicao de um filtro 3x3 bilateral com cor sigma=param1 e espao sigma=param2, como descrito em [2] Quando o smoothtype Gaussiano usado, param3 indica o sigma da Gaussiana (isto , o desvio padro). E se ele for zero, ele calculado a partir do tamanho do kernel, usando a frmula: sigma (n / 2 1) * 0.3 0.8 , onde sigma param1 ou param2, dependendo da orientao do kernel (horizontal ou vertical). Outra funo relacionada com convolues cvFilter2D, que uma funo que convolui qualquer kernel linear com uma imagem, e sua assinatura : void cvFilter2D( const CvArr* src, CvArr* dst, const CvMat* kernel, CvPoint anchor); onde src a imagem de origem, dst a imagem de destino e kernel o kernel de convoluo, uma matriz de ponto flutuante mono-canal. O anchor indica a posio relativa de um ponto filtrado com o kernel, a nica preocupao que o ponto da ncora deve estar dentro do kernel. O valor padro especial (-1,-1) significa que ele est no centro do kernel. Deteco de arestas. As tcnicas de deteco de arestas so inerentemente fceis de implementar e possuem uma complexidade computacional baixa. Como um exemplo de aplicao de deteco de arestas para rastreamento, o RAPiD [3] comumente citado, e pode ser visto na Figura 4. Este captulo apresenta todas as funes relativas a deteco de arestas do OpenCV. Os operadores de Sobel, de Canny e Laplaciano so apresentados.

Tipo de suavizao CV_BLUR_NO_SCALE

8



Figura 4. Alguns pontos so amostrados ao longo das arestas do modelo (esquerda), estes pontos so utilizados para inferir a pose (centro). Ocluses podem ser tratadas de uma forma robusta (direita).

Operador de Sobel. O operador de Sobel realiza uma medida do gradiente espacial 2D de uma imagem e enfatiza regies de alto gradiente espacial que correspondem a arestas. Tipicamente ele usado para encontrar a magnitude absoluta aproximada do gradiente em cada ponto de uma imagem em tons de cinza de entrada. Um exemplo de uso do operador de Sobel ilustrado na Figura 5.

Figura 5. Imagem em tons de cinza (esquerda), imagem do gradiente x de Sobel (centro) e imagem do gradiente y de Sobel (direita).

Pelo menos na teoria, o operador consiste em um par de mscaras de convoluo 3x3 como as mostradas na Figura 6. Uma mscara simplesmente a outra aps sofrer uma rotao de 90.

Figura 6. Mscaras de convoluo de Sobel.

Estas mscaras so designadas para responder maximamente a arestas verticais e horizontais com relao grade de pixels, uma mscara para cada uma das duas orientaes


9


perpendiculares. As mscaras podem ser aplicadas independentemente na imagem de entrada para produzir medidas separadas da componente do gradiente em cada orientao (chamadas Gx e Gy ). Elas podem ser combinadas para encontrar a magnitude absoluta do gradiente em cada ponto e a orientao desse gradiente. A magnitude do gradiente dada por: , embora tipicamente uma magnitude aproximada pode ser computada rapidamente usando:

G

Gx G y

G

Gx

Gy

Na biblioteca OpenCV, o operador de Sobel implementado atravs da funo cvSobel, e sua assinatura : void cvSobel( const CvArr* src, CvArr* dst, int xorder, int yorder, int aperture_size ); O argumento src a imagem de origem, dst a imagem de destino, xorder a ordem da derivada x , yorder a ordem da derivada no eixo y . O parmetro aperture_size o tamanho do kernel de Sobel estendido, ele precisa ser 1, 3, 5 ou 7. Em todos os casos, exceto quando ele 1, um kernel aperture_size x aperture_size ser usado para calcular a derivada. Existe tambm um valor especial para aperture_size CV_SCHARR que corresponde ao filtro 3x3 de Scharr [4]. Operador Laplaciano. O Laplaciano uma medida isotrpica 2D da derivada segunda espacial de uma imagem. O Laplaciano de uma imagem destaca regies de rpida mudana de intensidade e portanto comumente usado para deteco de arestas. O Laplaciano freqentemente aplicado em uma imagem que foi primeiramente suavizada com um filtro Gaussiano aproximado de forma a reduzir sua sensibilidade a rudo, e por isso as duas variantes sero descritas em conjunto neste texto. O operador normalmente toma uma nica imagem em tons de cinza como entrada e produz outra imagem em tons de cinza como sada. O Laplaciano L( x, y ) de uma imagem com valores de intensidade de pixel I ( x, y ) dado por:

L ( x, y )

I x2

2

I y2

2

Este operador pode ser aproximado por um filtro de convoluo. Visto que a imagem de entrada representada por um conjunto de pixels discretos, necessrio encontrar um kernel de convoluo discreta que possa aproximar as derivadas segundas na definio do Laplaciano. Dois kernels pequenos comumente utilizados so mostrados na Figura 7.

10



Figura 7. Duas aproximaes discretas do filtro Laplaciano comumente usadas.

A funo do OpenCV que implementa o Laplaciano de uma imagem cvLaplace, e sua assinatura : void cvLaplace( const CvArr* src, CvArr* dst, int aperture_size ); O argumento src a imagem de entrada, dst a imagem resultante, e aperture_size o mesmo argumento usado no operador de Sobel. Operador de Canny. O operador de Canny foi projetado para ser um detector de arestas timo (de acordo com critrios particulares, isto , existem outros detectores que tambm afirmam ser timos de acordo com critrios ligeiramente diferentes). Ele usa como entrada uma imagem em tons de cinza e produz como sada uma imagem mostrando as posies das descontinuidades de intensidade rastreadas. Um exemplo do operador de Canny a Figura 8. Como pode ser visto nesta figura, as arestas da imagem foram destacadas.

Figura 8. Imagem crua (esquerda), imagem resultante (direita).

O operador de Canny funciona como um processo multi-estgio. Primeiramente, a imagem suavizada usando convoluo Gaussiana. Ento, uma derivada primeira 2D simples aplicada imagem suavizada para destacar regies da imagem com derivadas primeiras espaciais altas. Arestas do origem a picos na imagem da magnitude do gradiente. O algoritmo ento rastreia ao longo do topo desses picos e seta para zero todos os pixels que no esto no topo dos picos, de forma a gerar linhas finas na sada, um processo conhecido


11


como supresso de no-mximos. O processo de rastreamento utiliza uma histerese controlada por dois limiares: T1 e T2 , com T1 > T2 . O processo de rastreamento s pode comear em um ponto de pico maior que T1 . O rastreamento ento continua em ambas as direes a partir desse ponto at que a altura do pico fique abaixo de T2 . Esta histerese ajuda a garantir que arestas com rudo no sejam quebradas em mltiplos fragmentos. O operador de Canny implementado no OpenCV atravs da funo cvCanny e sua assinatura a seguinte: void cvCanny( const CvArr* image, CvArr* edges, double threshold1, double threshold2, int aperture_size ); O argumento image a imagem de entrada, edges a imagem que ir guardar os resultados, threshold1 e threshold2 so os dois limiares usados nesse operador, aperture_size o parmetro de abertura, assim como no operador de Sobel. Deteco de cantos. Uma das abordagens da literatura de viso computacional para extrair certos tipos de caractersticas de uma imagem a deteco de cantos, ou mais genericamente deteco de pontos de interesse. A Figura 9 mostra uma aplicao de realidade aumentada sem marcadores baseada em pontos de interesse [5] que capaz de rastrear, por exemplo, a posio e orientao de um computador usando alguns pontos de interesse. E como pode ser notado na Figura 9 acima e direita, a maioria dos pontos de interesse esto localizados ao redor de cantos. Na Figura 9 abaixo e esquerda, possvel ver que o algoritmo robusto a rotao e translao, uma vez que a posio da placa rastreada corretamente. Alguns usos da deteco de caractersticas incluem deteco de movimento, mosaicos de imagens, colagem de imagens panormicas, modelagem 3D e reconhecimento de objetos.

12



Figura 9. Inicialmente, o aramado casado com o computador (acima, esquerda), oito pontos so rastreados (acima, direita) e finalmente a placa no computador rastreada (abaixo, esquerda e direita).

Na biblioteca OpenCV, existem trs maneiras de detectar pontos de interesse: (1) diretamente calculando autovetores e autovalores, (2) atravs do operador de Harris e (3) usando a funo Good Features to Track. As alternativas (1) e (2) se preocupam em detectar cantos na imagem, e embora a (3) seja baseada na (2), a classe de caractersticas que o algoritmo capaz de tratar abrange mais elementos do que apenas cantos. Autovetores e autovalores. A maioria dos algoritmos de deteco de caractersticas so baseados no clculo de autovalores e autovetores, e esta operao implementada no OpenCV atravs de duas funes, cvCornerEigenValsAndVects e cvCornerMinEigenVal. Ambas as funes so relativas matriz de covariao das derivadas em torno de certo pixel. A matriz de covariao da forma:

C

dI dx dI dx

2

dI dx dI dy

dI dy2

,

dI dy


13


onde I ( x, y ) a intensidade do pixel nas coordenadas ( x, y) . A funo cvCornerEigenValsAndVects calcula tanto os autovalores como os autovetores da matriz de covariao e cvCornerMinEigenVal apenas calcula e guarda os autovalores desta. A assinatura de cvCornerEigenValsAndVects : void cvCornerEigenValsAndVecs( const CvArr* image, CvArr* eigenvv, int block_size, int aperture_size ); O argumento image a imagem de entrada, eigenvv uma imagem que guarda os resultados e precisa ser seis vezes mais larga que image, block_size o tamanho da vizinhana e aperture_size o parmetro de abertura como no operador de Sobel. A assinatura da funo cvCornerMinEigenVal : void cvCornerMinEigenVal ( const CvArr* image, CvArr* eigenval, int block_size, int aperture_size ); Os parmetros desta funo so os mesmos da cvCornerEigenValsAndVecs, com exceo de eigenval, porque esta funo apenas calcula e guarda os menores autovalores associados com os pixels. Isso significa que cada autovalor do mesmo tamanho de image, ao contrrio da funo cvCornerEigenValsAndVecs que seis vezes maior, alm de calcular e guardar tanto os autovalores como os autovetores. Detector de cantos de Harris. O detector de cantos de Harris computa a matriz de momento com mdia local a partir dos gradientes da imagem, e ento combina os autovalores da matriz de momento para computar a fora do canto, da qual valores mximos indicam as posies dos cantos. Esse detector tambm baseado na matriz de covariao. A chave desta equao est em examinar seus autovalores. Quando a matriz possui dois autovalores altos, isto corresponde a duas direes principais diferentes no gradiente da imagem subjacente. Isto calculado rapidamente e eficientemente com uma simples equao para a resposta do canto que guardada para cada pixel da imagem:

R

det(C ) k *(trace(C )) 2 ,

onde k um parmetro ajustvel que determina o quo aresta-fbica a resposta do algoritmo . O resultado da aplicao do algoritmo em uma imagem pode ser visto na Figura 10. Na figura da direita, possvel ver algumas regies brancas, relativas a mximas locais que indicam que uma regio um canto. Deve-se notar que o detector de cantos de Harris capaz de encontrar arestas tambm, como pode ser visto nas regies cinza escuro da Figura 10.

14



Figura 10. Imagens em tons de cinza (esquerda), o resultado da aplicao do detector de cantos de Harris (direita).

A assinatura da funo mostrada abaixo: void cvCornerHarris( const CvArr* image, CvArr* harris_response, int block_size, int aperture_size, double k ); O argumento image a imagem de entrada, harris_response a imagem que guardar o resultado do detector de Harris. O parmetro block_size responsvel pelo tamanho da vizinhana, como discutido para autovetores e autovalores. O aperture_size o mesmo do operador de Sobel. Finalmente, k o parmetro ajustvel. Good Features to Track. O trabalho de Shi e Tomasi [1] em rastreamento de caractersticas implementado no OpenCV atravs da funo cvGoodFeaturesToTrack. Ele fortemente baseado no operador de deteco de cantos de Harris. A idia bsica do algoritmo monitorar a qualidade das caractersticas da imagem durante o rastreamento usando uma medida de dissimilaridade da caracterstica que quantifica a mudana de aparncia de uma determinada caracterstica entre o primeiro quadro e o quadro atual. Abaixo, na Figura 11, as caractersticas encontradas na imagem da esquerda so realadas e mostradas na imagem de direita.


15


Figura 11. O primeiro quadro da sequncia (esquerda), as caractersticas selecionadas de acordo com o critrio estabelecido (direita).

Existem algumas precaues relativas a esta funo. Uma delas a necessidade de se ter duas imagens temporrias de ponto flutuante de 32 bits do mesmo tamanho da imagem de entrada. Em aplicaes onde a memria um recurso escasso, alguns problemas podem aparecer quando essa funo usada. A assinatura da funo mostrada abaixo: void cvGoodFeaturesToTrack( const CvArr* image, CvArr* eig_image, CvArr* temp_image, CvPoint2D32f* corners, int* corner_count, double quality_level, double min_distance, const CvArr* mask, int block_size, int use_harris, double k ); O argumento image a imagem mono-canal de entrada, eig_image e temp_image so imagens temporrias de ponto flutuante de 32 bits do mesmo tamanho da imagem de entrada. O parmetro corners uma estrutura previamente alocada para comportar os cantos detectados, corner_count simplesmente o nmero de cantos detectados. O parmetro quality_level um nmero indicando a qualidade mnima aceitvel dos cantos da imagem, min_distance a distncia euclidiana mnima entre os cantos. O parmetro mask a regio de interesse, se um ponteiro para NULL passado, a imagem inteira usada. O parmetro block_size o mesmo da funo do detector de cantos de Harris. Ao usar esta funo, possvel decidir por usar o detector de cantos de Harris setando use_harris para qualquer valor diferente de zero. Por fim, k o parmetro livre do operador de Harris.

16



2.2

Segmentao

A tarefa de analisar uma imagem de forma a distinguir elementos especficos chamada segmentao. Os sub-captulos a seguir explicam algumas tcnicas usadas para atingir esse objetivo. Limiarizao. Esta tcnica consiste em separar os objetos de interesse do fundo da imagem. Isto comumente feito com imagens em tons de cinza, mas pode tambm ser aplicado a outros formatos, como imagens coloridas. Uma prtica comum quando se quer limiarizar imagens coloridas considerar a soma das componentes de cor para cada pixel. A limiarizao feita estimando intervalos de nvel que determinam os pixels que pertencem ao fundo da imagem e a objetos de interesse. Como pode ser visto na Figura 12 (esquerda), quando existe apenas um objeto para segmentar em uma imagem f ( x, y ) , um limiar T especificado e dois intervalos de nvel so definidos: f ( x, y ) T e f ( x, y) T . Esta operao chamada limiarizao mono-nvel e o resultado uma

imagem binria que distingue os pixels que pertencem a cada intervalo de nvel. Na limiarizao multi-nvel, existem n objetos para segmentar, requerendo o uso de diferentes limiares T1 , , Tn , como mostrado na Figura 12 (direita). O resultado desta operao uma imagem em tons de cinza com n nveis distintos.

Figura 12. Limiarizao mono-nvel (esquerda) e multi-nvel (direita)

A operao de limiarizao pode tambm ser classificada como global ou local. Na limiarizao global, os mesmos limiares Tk so usados para todos os pixels da imagem. Na limiarizao local, os limiares Tk dependem de propriedades locais dos pixels, tais como o nvel mdio de sua vizinhana. A limiarizao global mais adequada a imagens onde os objetos possuem uma iluminao constante. A Figura 13 mostra um exemplo onde um objeto com iluminao constante corretamente segmentado usando limiarizao global, enquanto que os resultados obtidos com a limiarizao local no so satisfatrios. A limiarizao local


17


mais indicada para casos onde a iluminao dos objetos varivel, visto que ela leva em considerao caractersticas locais da imagem. Na Figura 14, a limiarizao local segmenta mais pixels dos objetos do que a limiarizao global, devido natureza varivel da iluminao dos objetos.

Figura 13. Imagem de entrada onde o objeto possui uma iluminao constante (esquerda), resultado da limiarizao global (centro) e resultado da limiarizao local (direita).

Figura 14. Imagem de entrada onde os objetos possuem uma iluminao varivel (esquerda), resultado da limiarizao global (centro) e resultado da limiarizao local (direita).

Muitos algoritmos de processamento de imagens usados em aplicaes de tempo real no manipulam imagens coloridas. Como resultado, a imagem original tem de ser convertida para um formato mais adequado, tal como o binrio. a que a limiarizao entra. Um exemplo de uso da limiarizao no reconhecimento de padres em tempo real aparece no rastreamento de marcadores feito pela biblioteca de realidade aumentada ARToolKit [6]. As imagens coloridas capturadas pela cmera so analisadas de forma a segmentar os pixels escuros relativos a marcadores do fundo da imagem. Uma limiarizao mono-nvel global aplicada imagem de entrada, com o limiar T sendo especificado pelo usurio. Um valor comum para T 150. Considerando um pixel colorido (rp , g p , bp ) da imagem de entrada, se rp

gp

bp

3T , ento o pixel classificado como um pixel de marcador, caso

contrrio classificado como pixel de fundo. A Figura 15 mostra os resultados obtidos pelo ARToolKit ao limiarizar um quadro de entrada.

18



Figura 15. Limiarizao global usada no ARToolKit: imagem colorida de origem (esquerda) e resultado da limiarizao global (direita).

O OpenCV implementa uma limiarizao mono-nvel e oferece tanto uma limiarizao global como uma local para imagens em tons de cinza. A limiarizao global implementada pela funo cvThreshold, que possui a seguinte assinatura: void cvThreshold ( const CvArr* src, CvArr* dst, double threshold, double max_value, int threshold_type ); O argumento src a imagem em tons de cinza a ser limiarizada. O argumento dst onde a imagem binria resultante ser guardada. O limiar global T especificado pelo argumento threshold. O argumento max_value o nvel que ser usado para distinguir os pixels do objeto dos pixels do background. O argumento threshold_type determina qual funo ser usada na operao de limiarizao. Os cinco tipos de limiarizao disponveis e suas respectivas funes so apresentados na Tabela 3, e sua representao visual ilustrada na Figura 16.Tabela 3. Tipos de limiarizao do OpenCV e suas funes.

Tipo de limiarizao CV_THRESH_BINARY

Funo

dst ( x, y )dst ( x, y ) dst ( x, y ) dst ( x, y )

max_value , se src ( x, y ) threshold 0, caso contrrio0, se src ( x, y ) threshold threshold threshold max_value , caso contrrio threshold , se src ( x, y ) src ( x, y ), caso contrrio src ( x, y ), se src ( x, y ) 0, caso contrrio

CV_THRESH_BINARY_INV

CV_THRESH_TRUNC

CV_THRESH_TOZERO


19


CV_THRESH_TOZERO_INV

dst ( x, y )

0, se src ( x, y )

threshold

src ( x, y ), caso contrrio

Figura 16. Representao visual dos tipos de limiarizao do OpenCV.

A limiarizao local implementada pela funo cvAdaptiveThreshold, que tem a seguinte assinatura: void cvAdaptiveThreshold( const CvArr* src, CvArr* dst, double max_value, int adaptive_method, int threshold_type, int block_size, double param1 );

20



Os argumentos src, dst, max_value e threshold_type so os mesmos de cvThreshold. Os nicos tipos de limiarizao local disponveis so CV_THRESH_BINARY e CV_THRESH_BINARY_INV. O limiar T computado para cada pixel da imagem de entrada. O argumento adaptive_method determina como T calculado. Se ele CV_ADAPTIVE_THRESH_MEAN_C, ento T a media da vizinhana de pixels block_size x block_size subtrada por param1. Se ele CV_ADAPTIVE_THRESH_GAUSSIAN_C, ento T a soma ponderada Gaussiana da vizinhana de pixels block_size x block_size subtrada por param1. Isso significa que pixels mais prximos tero uma influncia maior no resultado do que os mais distantes. Deteco de linhas. Para detectar linhas retas em uma imagem, o primeiro passo realizar uma operao de realce de arestas na imagem de entrada. Da, um limiar aplicado ao resultado. A sada binria desta operao pode ser usada para a deteco de linhas. Algumas tcnicas de rastreamento 3D sem marcadores se baseiam na deteco de segmentos de linha na imagem Erro! Fonte de referncia no encontrada.. Um modelo aramado do objeto a ser rastreado projetado na imagem usando uma estimativa de pose da cmera. A projeo e as linhas da imagem so comparadas para calcular a pose atual da cmera. A Figura 17 ilustra o processo.

Figura 17. Linhas detectadas na imagem (esquerda) e pose estimada do carro (direita).

O operador usado para realizar deteco de linhas a transformada de Hough. A idia por trs da transformada de Hough diminuir a complexidade computacional da deteco de linhas usando uma representao de linhas no espao de parmetro ao invs de no plano xy . Considerando um ponto ( xi , yi ) no plano xy , existe uma infinidade de linhas que passam por ele. Essas linhas tm a forma yi

axi parmetros a e b , a equao resultante b

b . Rearranjando a equao em termos dos xi a yi . Isto equivalente a uma linha no

espao de parmetros. Considerando outro ponto ( x j , y j ) , o conjunto de linhas que passa por ele representado no espao de parmetros por b

x ja

y j . A interseco das linhas

no espao de parmetro no ponto (a' , b' ) determina os parmetros da linha que passa por


21


ambos os pontos no ( xi , yi ) e ( x j , y j ) no plano xy . A Figura 18 mostra grficos que ilustram esta idia.

Figura 18. Representao da linha no plano xy (esquerda) e no espao de parmetros (direita).

Na representao usada pelo algoritmo, cada eixo do espao de parmetros subdividido em intervalos de tamanho igual, como mostra a Figura 19, gerando clulas chamadas acumuladores. Cada acumulador (a, b) no espao de parmetros representa uma linha no plano xy . O primeiro passo do algoritmo atribuir zero a todos os acumuladores. Depois, a imagem de entrada escaneada procura de pontos de aresta. Para cada ponto ( xi , yi ) , os parmetros (a, b) de todas as linhas que passam por ele so avaliados usando todos os

xa y . O acumulador correspondente valores permitidos pela subdiviso da equao b para cada par de parmetros incrementado. Depois que todos os pontos de aresta so tratados, os valores nos acumuladores sero o nmero de pontos de aresta contidos na linha correspondente. Um limiar pode ento ser aplicado para selecionar as linhas com o maior nmero de pontos.

22



Figura 19. Acumuladores no espao de parmetros.

O tempo de execuo da transformada de Hough pode ser reduzido sem perda significativa na qualidade dos resultados usando uma abordagem probabilstica [8]. Ao invs de se utilizar todos os pontos de aresta, apenas uma frao aleatria desses pontos considerada. A deteco de linhas feita pela funo do OpenCV cvHoughLines2: CvSeq* cvHoughLines2( CvArr* image, void* line_storage, int method, double rho, double theta, int threshold, double param1, double param2 ); O argumento image a imagem binria de onde as linhas sero adquiridas. O argumento line_storage um recipiente para os dados das linhas detectadas. A variante da transformada de Hough a ser utilizada especificada pelo argumento method. A Tabela 4 apresenta os mtodos da transformada de Hough disponveis. Os argumentos rho e theta so a resoluo da distncia e do ngulo, respectivamente. O argumento threshold determina o nmero mnimo de pontos necessrios para uma linha. Os argumentos param1 e param2 so apenas usados se method CV_HOUGH_PROBABILISTIC ou CV_HOUGH_MULTI_SCALE. Na transformada de Hough probabilstica, param1 o tamanho mnimo da linha e param2 a distncia mxima entre segmentos pertencentes a uma mesma linha que no causa sua unio. Na transformada de Hough multi-escala, param1 o divisor para rho e param2 o divisor para theta.Tabela 4. Mtodos da transformada de Hough do OpenCV.

Mtodo da transformada de Hough CV_HOUGH_STANDARD

Descrio Transformada de Hough clssica. Retorna todas as linhas detectadas. Cada linha


23


representada pela distncia para a origem ( ) e pelo ngulo entre o eixo x e a normal da linha ( ) Transformada de Hough probabilstica. Retorna todos os segmentos de linha detectados. Cada segmento representado pelos seus pontos de incio e fim Variante multi-escala da transformada de Hough clssica. Retorna todas as linhas detectadas da mesma maneira que CV_HOUGH_STANDARD

CV_HOUGH_PROBABILISTIC

CV_HOUGH_MULTI_SCALE

Deteco de contornos. Aps aplicar um operador de realce de imagens para deteco de arestas e limiarizar a imagem resultante, os contornos podem ser extrados a partir da imagem. Para realizar esta tarefa, dois passos precisam ser contemplados: traado de contornos e representao de contornos. No traado de contornos, os contornos existentes so seguidos na imagem. Na representao de contornos, os contornos so descritos de uma forma significativa. A deteco de contornos largamente utilizada em solues de reconhecimento de padres em tempo real. No ARToolKit, os contornos relativos aos marcadores presentes no quadro de entrada precisam ser segmentados para possibilitar o reconhecimento e estimativa de pose [6]. A Figura 20 ilustra a operao.

Figura 20. Deteco de contornos usada no ARToolKit: imagem colorida de entrada (esquerda), arestas realadas (centro) e contornos detectados destacados na imagem (direita).

O OpenCV usa o algoritmo de Suzuki para realizar o traada de contornos [9]. Nesse algoritmo, inicialmente o pixel de contorno mais acima e esquerda encontrado. Da, a vizinhana do primeiro pixel verificada no sentido horrio para encontrar o prximo pixel do contorno. A partir da, a busca por outros pixels feita no sentido anti-horrio e termina quando os primeiros dois pixels do contorno so encontrados novamente. O OpenCV realiza representao de contornos usando dois tipos diferentes de descrio: cdigos de cadeia e representao poligonal.

24



Cdigos de cadeia consistem numa seqncia de nmeros que determinam a vizinhana de um pixel de contorno onde o prximo pixel de contorno se encontra. A Figura 21 mostra os cdigos para cada vizinhana (esquerda) e um exemplo de um contorno representado por um cdigo de cadeia (direita). Pode-se notar que escolher um ponto inicial diferente para o contorno pode gerar diferentes representaes de cdigo de cadeia. Isso pode ser evitado deslocando os nmeros do cdigo de cadeia de forma que resulte no inteiro de magnitude mnima.

Figura 21. Cdigos de cadeia para cada direo de vizinhana (esquerda) e uma representao de cdigo de cadeia de um contorno (direita).

A representao poligonal uma seqncia de vrtices que quando ligados simbolizam a essncia do contorno. A Figura 22 exemplifica esse tipo de representao, na qual existe um compromisso entre a fidelidade do contorno e o overhead de codificao.

Figura 22. Representao poligonal.

O OpenCV prov vrias maneiras de organizar os contornos obtidos a partir de uma imagem. Por exemplo, os contornos podem ser guardados em uma rvore, onde um contorno C1 pai de um contorno C 2 se e somente se C1 contm C 2 . A Figura 23 mostra como contornos aninhados podem ser descritos por uma rvore.


25


Figura 23. Representao hierrquica de contornos do OpenCV.

A funo usada para extrair contornos de uma imagem binria chamada cvFindContours e definida da seguinte forma: int cvFindContours( CvArr* image, CvMemStorage* storage, CvSeq** first_contour, int header_size, int mode, int method, CvPoint offset); O argumento image a imagem binria de onde os contornos sero retornados. O argumento storage um recipiente de dados dos contornos. O argumento first_countour onde um ponteiro para o primeiro contorno detectado estar disponvel aps a chamada da funo. O argumento header_size relativo ao tamanho da estrutura do contorno. O argumento mode determina como os contornos devem ser organizados. A Tabela 5 apresenta os modos de retorno dos contornos disponveis e suas descries. O argumento method especifica a representao de contorno a ser usada. A Tabela 6 descreve os mtodos de representao disponveis. O argumento offset usado para deslocar os pontos retornados de uma quantidade explcita de pixels. A funo retorna o nmero de contornos encontrados na imagem.Tabela 5. Modos de retorno dos contornos do OpenCV.

Modo de retorno CV_RETR_EXTERNAL CV_RETR_LIST CV_RETR_CCOMP CV_RETR_TREE

Descrio Retorna apenas os contornos externos extremos Retorna todos os contornos numa lista Retorna os componentes conexos de uma imagem (ver Rotulao de componentes conexos) Retorna todos os contornos hierarquicamente em uma rvore

26


Reconhecimento de padres em tempo real utilizando a biblioteca OpenCV Tabela 6. Mtodos de representao de contornos do OpenCV.

Mtodo de representao CV_CHAIN_CODE CV_CHAIN_APPROX_NONE

CV_CHAIN_APPROX_SIMPLE

Descrio Representao de cdigo de cadeia Representao poligonal onde todos os pixels de contorno so retornados como vrtices Representao poligonal onde apenas os pontos extremos de segmentos horizontais, verticais e diagonais do contorno so retornados como vrtices Duas variantes da representao poligonal de Teh-Chin [10]. Apenas os pixels de contorno com curvatura alta so retornados como vrtices Representao poligonal onde apenas os pontos extremos de segmentos horizontais de um contorno so retornados como vrtices

CV_CHAIN_APPROX_TC89_L1 e CV_CHAIN_APPROX_TC89_KCOS

CV_LINK_RUNS

Aps extrair os contornos de uma imagem, eles podem ser manipulados de forma a obter informaes tais como rea e aproximao poligonal. A rea do contorno calculada usando a funo cvContourArea, descrita a seguir: double cvContourArea( const CvArr* contour, CvSlice slice); A rea do contorno especificado no argumento contour retornada pela funo. Se apenas uma seco de interesse do contorno tem de ser considerada no clculo, ela pode ser determinada usando o argumento slice. A aproximao poligonal de um contorno obtida usando a funo cvApproxPoly: CvSeq* cvApproxPoly( const void* src_seq, int header_size, CvMemStorage* storage, int method, double parameter, int parameter2); O argumento src_seq o contorno a ser aproximado. Os argumentos header_size e storage tm a mesma finalidade dos de cvFindContours. O nico valor aceito atualmente para o argumento method CV_POLY_APPROX_DP, que corresponde ao algoritmo de aproximao poligonal de Douglas-Peucker [11]. O argumento parameter determina o valor de tolerncia a ser usado no algoritmo. O argumento parameter2 especifica se uma organizao hierrquica deve ser organizada ou se o contorno fechado ou no. O algoritmo baseado na distncia entre um vrtice e um segmento de aresta e em uma tolerncia . Para comear o algoritmo, dois pontos extremos do polgono so conectados. Essa conexo define a primeira aresta a ser usada. Depois, a distncia entre cada vrtice


27


remanescente e essa aresta testada. Se existem distncias maiores que , ento o vrtice com a maior distncia da aresta adicionado simplificao. O processo continua recursivamente para cada aresta do passo atual at que todas as distncias entre os vrtices da linha poligonal original e a simplificao estejam dentro da distncia de tolerncia. A Figura 24 ilustra o passo-a-passo do algoritmo.

Figura 24. Algoritmo de aproximao poligonal de Douglas-Peucker.

Rotulao de componentes conexos. A rotulao de uma imagem binria diz respeito ao ato de atribuir um valor nico para pixels que pertencem a uma mesma regio conexa. Aps limiarizar a imagem de entrada, os pixels vizinhos que pertencem a objetos de interesse so associados com um rtulo. O conhecimento dos componentes conexos de uma imagem bastante til para o processo de reconhecimento automatizado. Essa operao comumente usada em aplicaes de reconhecimento de padres, em tempo real. A rotulao est presente no pipeline da biblioteca ARToolKit [6]. Os componentes conexos de uma imagem limiarizada so

28



rotulados para identificar regies relativas a bordas de marcadores e aos padres internos, como pode ser visto na Figura 25.

Figura 25. Rotulao de componentes conexos usada no ARToolKit: imagem limiarizada (esquerda) e resultados da rotulao (direita).

O princpio do algoritmo de rotulao consiste no escaneamento da imagem binria a partir do pixel localizado mais acima e esquerda procura de pixels de objeto. Para cada pixel de objeto, os seus pixels vizinhos que j foram escaneados so examinados. Existem trs opes para a rotulao de um pixel: - Se no existem pixels de objeto entre os pixels examinados, um novo rtulo criado e atribudo ao pixel atual; - Se existe um e apenas um pixel de objeto entre os pixels examinados, o rtulo deste pixel atribudo ao pixel atual; - Se existem mais de um pixel de objeto entre os pixels examinados, um dos rtulos atribudo ao pixel atual e uma equivalncia entre os diferentes rtulos criada. Quando todos os pixels de objeto so rotulados, os rtulos equivalentes so agrupados em classes de equivalncia, cada uma com um rtulo nico. A imagem ento escaneada novamente para resolver as equivalncias e definir os componentes conexos. No OpenCV, a rotulao realizada usando a funo cvFindContours com CV_RETR_CCOMP setado como o argumento mode. Os componentes conexos so organizados de uma maneira hierrquica. Os contornos externos dos componentes so colocados no primeiro nvel na rvore. Os contornos dos buracos presentes em um componente so colocados no segundo nvel. 2.3 Rastreamento de objetos

A biblioteca OpenCV possui algumas funes para rastreamento de objetos. Este tutorial abordar trs tcnicas possveis de implementao usando estas funes. Casamento de Modelos (Template Matching) usa um modelo (template) simples para examinar a imagem, armazenando os resultados. CamShift um algoritmo adaptativo que tenta encontrar um objeto baseado na retroprojeo do seu histograma. Fluxo ptico (Optical Flow) usa o fluxo de cada pixel para rastrear o objeto. Outras combinaes podem ser realizadas de forma a alcanar resultados diferentes.


29


Casamento de Modelos. Casamento de Modelos uma das formas mais simples de encontrar um objeto em uma imagem. O objetivo desta tcnica examinar todos os pixels de uma imagem e encontrar todas as instncias de um objeto especfico descrito por um modelo. Um cenrio de uso do Casamento de Modelos para reconhecimento de padres em tempo real pode ser encontrado em algumas aplicaes de realidade aumentada sem marcadores, tais como a ilustrada na Figura 26 e descrita em [12]. A diferena entre uma regio da imagem e o modelo de referncia minimizada. Em seguida, os parmetros de uma funo que mapeia o modelo na imagem alvo so calculados, de forma que o rastreamento pode ser realizado.

Figura 26. Rastreamento 3D com casamento de modelos linhas verdes delimitam a imagem do modelo (esquerda) e cena aumentada (direita).

O OpenCV oferece tal funcionalidade atravs da funo cvMatchTemplate: void cvMatchTemplate( const CvArr* image, const CvArr* templ, CvArr* result, int method ); Todos os resultados da comparao so armazenados na varivel result, que pode ser interpretada como uma imagem. A aparncia desta imagem estar diretamente relacionada com o resultado do casamento do modelo com a imagem original: quanto mais prximo o modelo casado, maior o valor do pixel armazenado, que poder ser visualizado na imagem como um pixel claro. O OpenCV suporta diversos mtodos de comparao do modelo com a imagem, conforme a Tabela 7:

30


Reconhecimento de padres em tempo real utilizando a biblioteca OpenCV Tabela 7. Mtodos para Casamento de Modelos

Descrio A diferena quadrada entre o modelo e a CV_TM_SQDIFF imagem CV_TM_SQDIFF_NORMED A diferena quadrada normalizada A correlao cruzada entre modelo e CV_TM_CCORR imagem CV_TM_CCORR_NORMED A correlao cruzada normalizada CV_TM_CCOEFF O coeficiente de correlao CV_TM_CCOEFF_NORMED O coeficiente de correlao normalizado A Figura 27 mostra o exemplo de um modelo, e a Figura 28 ilustra os resultados obtidos pelo casamento deste modelo com uma imagem de entrada.

Mtodo

Figura 27. Modelo utilizado pela tcnica Casamento de Modelos.

Figura 28. Um exemplo de uso do Casamento de Modelos. A imagem original (cima) e o modelo resultante (baixo).


31


CamShift. CamShift remete a Continuous Adaptive Mean Shift, ou seja Deslocamento Mdio Adaptativo Contnuo, sendo um algoritmo iterativo [13]. Ele utiliza o algoritmo de deslocamento mdio, que iterage para encontrar o centro de um objeto dada a imagem da distribuio de probabilidade da sua cor 2D. Ento, o algoritmo calcula o tamanho e a orientao do objeto. O fluxo de funcionamento do algoritmo mostrado na Figura 29.

Figura 29. Fluxo de funcionamento do CamShift.

O algoritmo CamShift descrito, passo a passo, abaixo: 1. 2. 3. Configurar a regio de clculo da distribuio de probabilidade para toda a imagem. Escolher o local inicial da janela de busca do deslocamento mdio 2D. Calcular a distribuio de probabilidade da cor na regio 2D centralizada na janela de busca em uma Region of Interest (ROI) um pouco maior que o tamanho da janela de deslocamento mdio. Executar o algoritmo de deslocamento mdio [13] para encontrar o centro da janela de busca. Armazenar o momento (rea ou tamanho) e a posio do centro. Para o prximo frame de vdeo, centralizar a janela de busca na posio mdia armazenada no Passo 4 e configurar o tamanho da janela para uma funo do momento anterior encontrado. Ir para o Passo 3.

4.

5.

A funo cvCamShift do OpenCV implementa o algoritmo CamShift:

32



int cvCamShift( const CvArr* prob_image, CvRect window, CvTermCriteria criteria, CvConnectedComp* comp, CvBox2D* box); O parmetro prob_image a retroprojeo do histograma do objeto, que pode ser calculada pela funo cvCalcBackProject, como mostrado na Figura 30. O parmetro window a janela de busca inicial que o algoritmo utilizar nas iteraes. O parmetro criteria usado para informar aplicao sobre quando ela deve parar a busca. O usurio pode especificar se o critrio o nmero de iteraes ou um limiar psilon que define a similaridade das janelas. O parmetro comp remete a Componente Conectado, que contm informaes sobre a convergncia da janela de busca. As coordenadas da janela podem ser recuperadas chamando comp->rect e a soma de todos os pixels dentro da janela pode ser obtida pelo campo comp->area. O parmetro box contm o tamanho e a orientao do objeto no final da execuo do algoritmo. A Figura 31 ilustra um exemplo de rastreamento de face usando CamShift.

Figura 30. Exemplo da retroprojeo do histograma.

Figura 31. Exemplo de rastreamento com o CamShift.


33


Fluxo ptico. Fluxo ptico a tcnica que mede a velocidade dos pixels de uma imagem comparando os mesmos com o frame anterior. O deslocamento destes pixels ao longo do tempo pode ser usado para estimar o movimento da cmera em aplicaes como a ilustrada na Figura 32, que rastreia faces em 3D [14].

Figura 32. Fluxo ptico usado para rastreamento 3D.

Existem vrios algoritmos que implementam Fluxo ptico, e o OpenCV oferece quatro deles. Estas implementaes so explicadas na seqncia. Tcnica Lucas & Kanade. A tarefa de medir o fluxo ptico reduzida a um sistema linear aplicando a equao do fluxo ptico a um grupo de pixels adjacentes e assumindo que todos eles tm a mesma velocidade [15]. Esta tcnica rpida o suficiente para ser usada em tempo real porque no processa a imagem toda. A funo do OpenCV que implementa esta tcnica a cvCalcOpticalFlowLK, que usada em um exemplo descrito na Seo 3. void cvCalcOpticalFlowLK( const CvArr* prev, const CvArr* curr, CvSize win_size, CvArr* velx, CvArr* vely ); Os argumentos prev e curr so os dois frames adjacentes temporrios da imagem usados para calcular a velocidade. O parmetro win_size a janela mdia que funcionar como base para toda a imagem. Os parmetros velx e vely so, respectivamente, os componentes horizontal e vertical do fluxo ptico para cada pixel. Eles tm o mesmo tamanho das imagens de entrada. O OpenCV tambm implementa uma abordagem piramidal do algoritmo Lucas & Kanade [16]. O algoritmo de rastreamento piramidal procede da seguinte forma. Primeiramente, o fluxo ptico calculado em um nvel de maior profundidade da pirmide Lm . Ento, o resultado deste clculo propagado at o nvel mais alto para se obter um valor inicial (uma tentativa) para o deslocamento dos pixels. Dado este valor inicial, o fluxo ptico refinado calculado no nvel 0 (a imagem original). A funo cvCalcOpticalFlowPyrLK do OpenCV implementa este algoritmo. void cvCalcOpticalFlowPyrLK( const CvArr* prev, const CvArr*

34



curr, CvArr* prev_pyr, CvArr* curr_pyr, const CvPoint2D32f* prev_features, CvPoint2D32f* curr_features, int count, CvSize win_size, int level, char* status, float* track_error, CvTermCriteria criteria, int flags ); Os argumentos prev_pyr e curr_pyr so buffers usados pelo algoritmo para armazenar as imagens parciais. Os argumentos prev_features e curr_features so os arrays de pontos a serem rastreados. O primeiro buffer contm os pontos e o segundo buffer armazenar as novas posies encontradas. O argumento count define o nmero de pontos a serem rastreados. O parmetro win_size define o tamanho da janela de busca para cada pirmide, e level o nvel piramidal mximo. O parmetro status um array que contm 1 se a caracterstica (feature) foi rastreada com sucesso e o fluxo foi calculado, e 0 em caso contrrio. O argumento track_error um parmetro opcional que contm diferenas entre patches ao redor dos pontos originais e deslocados. O parmetro flags pode ser configurado para salvar algum tempo de processamento, uma vez que possvel assumir que um buffer de uma determinada pirmide j foi calculado. As flags disponveis so listadas na Tabela 8.Tabela 8. Flags do Fluxo ptico Piramidal

Flag CV_LKFLOW_PYR_A_READY CV_LKFLOW_PYR_B_READY CV_LKFLOW_INITIAL_GUESSES

Descrio A pirmide para o primeiro frame prcalculada antes da chamada A pirmide para o segundo frame prcalculada antes da chamada O array curr_features contm as coordenadas iniciais das caractersticas antes da chamada da funo

Tcnica Horn & Schunck. Esta funo encontra o padro do fluxo ptico, assumindo que a velocidade aparente do padro de brilho varia suavemente, praticamente em toda a imagem [17]. A tcnica de Fluxo ptico Horn & Schunck implementada no OpenCV atravs da funo cvCalcOpticalFlowHS: void cvCalcOpticalFlowHS( const CvArr* prev, const CvArr* curr, int use_previous, CvArr* velx, CvArr* vely, double lambda, CvTermCriteria criteria );


35


O parmetro use_previous denota usar ou no o clculo do campo de velocidade prvia. O campo lambda chamado multiplicador Lagrangiano (Lagrangian multiplier). Ele deve ser menor para imagens com rudo e maior para imagens limpas e precisas. Tcnica de Casamento de Blocos (Block Matching). Esta tcnica no utiliza diretamente uma equao de fluxo ptico. Ao invs disso, ela usa uma tcnica que lembra casamento de padres. Ela usa uma caixa definida dentro da primeira imagem e tenta encontrar outra caixa de mesmo tamanho na segunda imagem, que seja similar a primeira. Este algoritmo apresenta um resultado aproximado quando comparado s outras tcnicas. A funo cvCalcOpticalFlowBM no OpenCV implementa esta tcnica: void cvCalcOpticalFlowBM( const CvArr* prev, const CvArr* curr, CvSize block_size, CvSize shift_size, CvSize max_range, int use_previous, CvArr* velx, CvArr* vely ); Os parmetros block_size e shift_size definem as caractersticas do bloco utilizado. O parmetro max_range representa o tamanho dos pixels vizinhos ao redor do bloco que sero examinados. 2.4 Deteco de objetos

A biblioteca OpenCV fornece a funcionalidade de deteco de objetos. Ela usa um classificador, proposto por Paul Viola [18] e Rainer Lienhart [19], que identifica vrios objetos diferentes. O processo inicia selecionando algumas centenas de amostras de vises do objeto desejado, em diversos ngulos e sob diversas condies de iluminao. Este conjunto de imagens chamado de amostras positivas. Ento, outro conjunto de imagens escolhido, contendo imagens arbitrrias no incluindo o objeto desejado. Este conjunto chamado de amostras negativas. Em seguida, ambos os conjuntos so usados para treinar uma cascata de classificadores ditos boosted. A palavra cascata no nome do classificador significa que o classificador resultante consiste de diversos classificadores mais simples que so aplicados subseqentemente a uma ROI, at que em alguma etapa o candidato rejeitado ou todas as etapas so superadas. A palavra boosted significa que os classificadores, a cada etapa da cascata, so complexos por si s e so formados por classificadores bsicos usando uma entre quatro tcnicas de boosting diferentes (voto ponderado). Atualmente, as tcnicas Discrete Adaboost, Real Adaboost, Gentle Adaboost e Logitboost so suportadas [20]. Aps o classificador ser treinado, pode ser usado para detectar o objeto em uma ROI. O classificador projetado de forma a, redimensionando a ROI, detectar objetos de tamanhos diferentes.

36



O OpenCV fornece um projeto completo para deteco de faces, que ser detalhado na Seo 3, implementando o classificador em cascata descrito anteriormente. Este projeto pode ser facilmente adaptado para qualquer objeto, uma vez que um novo conjunto de imagens pode ser usado na etapa de treinamento sem modificar muito o cdigo. A Figura 33 mostra uma aplicao de deteco de objetos [21].

Figura 33. Exemplo de deteco de componentes de uma placa me.

O OpenCV disponibiliza algumas funes importantes que merecem um detalhamento para melhor entendimento do contedo. A funo cvLoad do OpenCV usada para importar o arquivo XML gerado durante a etapa de treinamento: void* cvLoad( const char* filename, CvMemStorage* memstorage, const char* name, const char** real_name); O nico parmetro que precisa ser passado para esta funo quando carregando uma cascata o filename, que deve conter o endereo do arquivo XML. A funo cvHaarDetectObjects retorna uma seqncia de quadrados para cada objeto detectado: CvSeq* cvHaarDetectObjects( const CvArr* image, CvHaarClassifierCascade* cascade, CvMemStorage* storage, double scale_factor, int min_neighbors, int flags, CvSize min_size);


37


O parmetro image representa a imagem onde os objetos devem ser detectados. A sada da funo cvLoad deve ser passada no parmetro cascade. Durante a busca, potenciais retngulos candidatos so armazenados no parmetro storage. O scale_factor o fator de escala aplicado na janela de busca a cada subexame. O parmetro min_neighbors funciona agrupando retngulos vizinhos. A nica flag atualmente suportada pelo parmetro flags CV_HAAR_DO_CANNY_PRUNNING, que usa o detector de arestas Canny para rejeitar algumas regies da imagem que no contm o objeto procurado. min_size define o tamanho mnimo da janela de deteco.

3

Aplicaes de exemplo

A Intel tambm disponibiliza no pacote padro do OpenCV alguns exemplos de cdigo. No subdiretrio samples, localizado no diretrio de instalao, tem cdigos fonte que podem auxiliar um usurio iniciante do OpenCV. Entre estes arquivos, alguns exemplos merecem um detalhamento maior, levando em considerao sua relevncia para deteco de padres e o uso de conceitos apresentados previamente neste tutorial. Estes exemplos sero descritos na seqncia. 3.1 Deteco de quadrados

O exemplo da deteco de quadrados visa encontrar e destacar os quadrados contidos nas imagens carregadas. Para encontrar os quadrados, o exemplo implementa uma funo que retorna uma seqncia contendo os vrtices dos quadrados detectados. Primeiramente, a seqncia que ser usada para guardar o resultado criada, tornando possvel qualquer futura adio de vrtices. Em seguida, alguns filtros so aplicados para destacar arestas, considerando vrios limiares. A cada limiar, a funo cvFindContours separar cada contorno e armazenar os mesmos em um objeto de seqncia. Para cada contorno, a funo cvApproxPoly calcula um polgono aproximado baseado no resultado de cvFindContours. Se algumas condies forem satisfeitas (tais como ter quatro vrtices e um contorno convexo), o polgono detectado um retngulo. A Figura 34 ilustra dois exemplos com os quadrados destacados pelo exemplo.

38



Figura 34. Exemplo de deteco de quadrados.

3.2

Demo do CamShift

Este exemplo mostra como aplicar a cvCamShift para detectar um padro em uma imagem capturada por uma webcam, baseado na informao fornecida por um histograma. O histograma contm a informao da cor de um padro, e este demo usa o mesmo para encontrar uma rea na imagem que casa com os dados do histograma. Para tornar o rastreamento possvel, o usurio precisa fornecer como entrada para a aplicao uma subrea do frame capturado. Esta rea tomada como base para calcular um histograma de matizes, que servir como padro para vasculhar todo o frame procurando por uma combinao correspondente. Um exemplo de histograma pode ser visto na Figura 35. Este histograma funciona como uma identidade da cor.

Figura 35. Histograma de matizes da face detectada na Figura 36.

As funes usadas para criar e calcular o histograma so, respectivamente, cvCreateHist e cvCalcHist. Para encontrar o padro em um frame deve-se calcular a retroprojeo do plano de matizes, usando o histograma. A retroprojeo uma imagem onde cada posio tem uma


39


probabilidade de compor um objeto tal qual o objeto rastreado. Para calcular a imagem equivalente retroprojeo da imagem, baseado em um histograma, o usurio precisa chamar cvCalcBackProjection. O resultado da retroprojeo ilustrado na Figura 36 (direita). Dado o resultado da retroprojeo, o algoritmo CamShift aplicado para retornar a caixa de rastreamento, que conter o retngulo orientado que envolve a rea casada. O algoritmo CamShift implementado pela funo cvCamShift. Um exemplo do CamShift sendo aplicado a uma face pode ser visto na Figura 36 (esquerda). O algoritmo visa buscar a maior rea com vizinhos conectados, tendo uma alta probabilidade de fazer parte da soluo.

Figura 36. CamShift detectando uma face (esquerda) e retroprojeo da imagem (direita).

3.3

O rastreador Kanade Lucas

O Kanade Lucas um rastreador (tracker) de caractersticas (features) popular, implementado utilizando uma abordagem piramidal que usa fluxo ptico para calcular as novas posies das caractersticas selecionadas. Uma caracterstica pode ser explicada como um ponto em uma cena praticamente rgida que pode ser casado com outro ponto no prximo frame, mantendo o valor semntico de estar no mesmo ponto 3D da cena real. Para gerar algumas caractersticas para popular a aplicao e testar o comportamento do rastreador, uma funo chamada cvGoodFeaturesToTrack pode ser usada. Esta funo seleciona os cantos mais fortes na imagem para ser as caractersticas que sero rastreadas pela aplicao. Para refinar a posio dos cantos selecionados, cvFindCornersSubPix pode ser usada adicionalmente funo apropriada. Um resultado desta funo pode ser visto na Figura 37.

40



Figura 37. Um frame mostrando as boas caractersticas para rastrear.

No lao principal, o programa testa se o usurio adicionou manualmente uma nova caracterstica e tambm refina a posio deste ponto para casar com o canto mais prximo na imagem. Isto necessrio porque cantos so mais fceis de rastrear e calcular o fluxo ptico. Para calcular a prxima posio das caractersticas mostradas no ltimo frame, a funo cvCalcOpticalFlowPyrLK usada. Esta funo implementa o rastreador Kanade Lucas e precisa de algumas imagens temporrias para aplicar a abordagem piramidal. Elas atuam como imagens subamostradas que ajudam o algoritmo a rastrear fluxos pticos, com movimentos grandes. O resultado desta funo a nova posio dos pontos fornecidos como parmetros. 3.4 Deteco de faces

O exemplo de deteco de faces usa o classificador Haar para reconhecer um padro de face. O exemplo carrega um classificador Haar pr-treinado e usa o mesmo para detectar os objetos no frame atual. O classificador Haar usado neste exemplo o HaarClassifierCascade, que difere de outros classificadores por usar em cascata mltiplos classificadores Haar. Para carregar o classificador o exemplo usa a funo cvLoad e o resultado definido como sendo do tipo cvHaarClassifierCascade. Este classificador ser usado como parmetro da funo cvHaarDetectObjects. Com esta funo, o usurio pode encontrar todas as regies que casam com os objetos que a cascata foi treinada. Como valor de retorno a funo cvHaarDetectObjects fornece uma seqncia de retngulos contendo os objetos casados. Uma instanciao em tempo de execuo da deteco de faces mostrada na Figura 38.


41


Figura 38. Classificador Haar detectando faces.

4

Consideraes finais

Este tutorial apresentou o OpenCV, composto por uma grande quantidade de funes relacionadas com reconhecimento de padres. Estas funes so bsicas para qualquer projeto de processamento de imagens que visa detectar um padro especfico ou genrico. As funes bsicas do OpenCV para deteco de padres so fceis de usar e seguem uma estrutura padronizada, compartilhando parmetros comuns fornecidos pela biblioteca. Alm da simplicidade do framework, o OpenCV traz uma biblioteca para desenvolvimento de interfaces, que agiliza o perodo de prototipao de um teste ou aplicao usando o OpenCV. Esta biblioteca chamada HighGUI e um exemplo de cdigo mostrado no Apndice, em anexo.

Referncias[1]. J. Shi e C. Tomasi, Good Features to Track, Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Washington DC, EUA, 1994. [2]. C. Tomasi e R. Manduchi. Bilateral Filtering for Gray and Color Images, Proceedings of the International Conference on Computer Vision, Bombay, India, 1998. [3]. C. Harris. Tracking with Rigid Objects. MIT Press, 1992. [4]. H. Scharr. Digitale Bildverarbeitung und Papier: Texturanalyse mittels Pyramiden und Grauwertstatistiken am Beispiel der Papierformation. Diplomarbeit, Fakultt fr Physik und Astronomie, Ruprecht-Karls-Universitt Heidelberg, 1996.

42



[5]. M. Uenohara e T. Kanade. Vision-Based Object Registration for Real-Time Image Overlay. Journal of Cognitive Neuroscience 3, 7186, 1991. [6]. H. Kato e M. Billinghurst. Marker Tracking and HMD Calibration for a Video-Based Augmented Reality Conferencing System, Proceedings of the Workshop on Augmented Reality, San Francisco, EUA, 1999. [7]. D. Koller, K. Daniilidis e H. Nagel. Model-Based Object Tracking in Monocular Image Sequences of Road Traffic Scenes. International Journal of Computer Vision 10, 257281, 1993. [8]. J. Matas, C. Galambos e J. Kittler. Progressive Probabilistic Hough Transform, Proceedings of the British Machine Vision Conference, Southampton, UK, 1998. [9]. S. Suzuki e K. Abe. Topological Structural Analysis of Digital Binary Images by Border Following. Graphical Model and Image Processing 30, 32-46, 1985. [10]. C. The e R. Chin. On the Detection of Dominant Points on Digital Curves. IEEE Transactions on Pattern Analysis and Machine Learning 11, 859-872, 1989. [11]. D. Douglas e T. Peucker. "Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature". The Canadian Cartographer 10, 112-122, 1973. [12]. Lepetit, V., Lagger, P. e Fua, P. Randomized Trees for Real-Time Keypoint Recognition, Conference on Computer Vision and Pattern Recognition, 2005. [13]. Bradski, G. Computer Vision Face Tracking as a Component of a Perceptual User Interface, Workshop on Applications of Computer Vision, 1998. [14]. Basu, S., Essa, I. e Pentland, A. Motion Regularization for Model-Based Head Tracking, International Conference on Pattern Recognition, 1996. [15]. Lucas, B. e Kanade, T. An Iterative Image Registration Technique with an Application to Stereo Vision, International Joint Conference on Artificial Intelligence, 1981. [16]. Bouguet, J.-Y. Pyramidal Implementation of the Lucas Kanade Feature Tracker, parte da documentao do OpenCV. [17]. Horn, B. e Schunck, B. Determining Optical Flow. Artificial Intelligence, 17, 185203, 1981. [18]. Viola, P. e Jones, M. Rapid Object Detection using a Boosted Cascade of Simple Features, Conference on Computer Vision and Pattern Recognition, 2001. [19]. Lienhart, R. e Maydt, J. An Extended Set of Haar-like Features for Rapid Object Detection, International Conference on Image Processing, 2002. [20]. Freund, Y. e Schapire, R. A Short Introduction to Boosting, Journal of Japanese Society for Artificial Intelligence, 14, 771-780, 1999.


43


[21]. Teixeira, J. M., Silva, D., Moura, G., Costa, L. H., Teichrieb, V. e Kelner, J. miva: Constructing a Wearable Platform Prototype, Symposium on Virtual and Augmented Reality, 2007.

ApndiceEste apndice descreve como construir uma interface simples para testar ou prototipar algumas funcionalidades do OpenCV, usando o framework HighGUI. O framework HighGUI disponibilizado com a distribuio padro do OpenCV e visa simplificar tarefas bsicas, tais como criar e manipular janelas, exibir imagens em janelas, criar controles para ajustar parmetros de aplicaes e outras funes para manipular imagens, vdeos e captura de cmera. Funcionalidades como escutar eventos de mouse tambm so gerenciadas pelo framework HighGUI. O trecho de cdigo abaixo mostra o vdeo capturado por uma cmera e implementa uma funo bsica que escuta os eventos do mouse. #include "cv.h" #include "highgui.h" #ifdef _EiC #define WIN32 #endif //escuta os eventos do mouse void on_mouse(int event, int x, int y, int flags, void* param) { //testar todos os eventos possiveis switch(event) { case CV_EVENT_LBUTTONDOWN: break; case CV_EVENT_RBUTTONDOWN: break; case CV_EVENT_MBUTTONDOWN: break; case CV_EVENT_LBUTTONUP: break; case CV_EVENT_RBUTTONUP: break; case CV_EVENT_MBUTTONUP: break; case CV_EVENT_LBUTTONDBLCLK:

44



break; case CV_EVENT_RBUTTONDBLCLK: break; case CV_EVENT_MBUTTONDBLCLK: break; default: //CV_EVENT_MOUSEMOVE } } int main( int argc, char** argv ) { int c = 0; //Objeto capture usado para captura de video CvCapture* capture = 0; //Imagens usadas como buffers na captura de video IplImage *frame, *frame_copy = 0; //Captura da camera padrao capture = cvCaptureFromCAM(-1); //Cria uma janela chamada "result" cvNamedWindow( "result", 1 ); //Configura o callback do mouse como sendo a funcao //descrita antes da main cvSetMouseCallback( "result", on_mouse, 0 ); if( capture ) { //laco de captura for(;;) { if( !cvGrabFrame( capture )) break; frame = cvRetrieveFrame( capture ); if( !frame ) break; if( !frame_copy ) frame_copy = cvCreateImage( cvSize(frame->width,frame->height), IPL_DEPTH_8U, frame->nChannels ); if( frame->origin == IPL_ORIGIN_TL ) cvCopy( frame, frame_copy, 0 ); else


45


cvFlip( frame, frame_copy, 0 ); //Exibe o frame na janela cvShowImage( "result", frame_copy ); //Testa se o usuario pressionou a tecla ESC c = cvWaitKey(10); if( (char)c == 27 ) break; } cvReleaseImage( &frame_copy ); cvReleaseCapture( &capture ); } cvDestroyWindow("result"); return 0; }

46


Documents

WRVA2008_ApostilaTutorialReconhecimentoPadroesTempoReal