Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV Thiago Teixeira Santos Carlos Hitoshi Morimoto 1
Resumo: Os constantes avanços em poder de processamento, capacidade de armazenamento, e largura de banda tornaram possível ao usuário de computadores o acesso, manipulação e edição de imagens e vídeos digitais. Nesse tutorial, vamos descrever alguns algoritmos de visão computacional para a segmentação, indexação e recuperação de vídeo utilizando o OpenCV para que, ao final do tutorial, você seja capaz de desenvolver suas próprias ferramentas de visão computacional para processamento de vídeo. Conhecimentos sobre visão computacional e experiência em programação utilizando a linguagem C++ são desejados para um melhor aproveitamento do conteúdo desse tutorial. Abstract:
Constant advancements in processing power, larger storage capacity and higher bandwidth available at lower cost, have made it possible to everyone to access, edit, and manipulate digital images and video. In this tutorial we present a few computer vision algorithms for video segmentation and indexing based on visual content using OpenCV. By the end of this tutorial, you will be able to develop your own computer vision tools for video processing. Previous knowledge of computer vision and programming experience in C/C++ is required to take full advantage of this tutorial.
1
Introdução
Esse texto foi preparado para servir de material de apoio ao mini-curso oferecido no IV Workshop de Visão Computacional realizado em novembro de 2008 na Universidade Estadual Paulista em Bauru, estado de São Paulo, e é baseado na disssertação de mestrado de Thiago Teixeira Santos [14]. O objetivo desse trabalho é introduzir conceitos sobre segmentação e indexação de vídeo, necessários para que possamos a seguir desenvolver alguns algoritmos simples de processamento de vídeo usando o OpenCV. Alguns desses algoritmos serão descritos em detalhes durante o mini-curso e podem ser encontrados em [14]. 1 Instituto
de Matemática e Estatística, USP {hitoshi,
[email protected]}
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
1.1
Processamento de vídeo digital
Quando assistimos a um programa em vídeo (como TV, cinema, etc), nossos olhos recebem estímulos visuais (imagens) a uma taxa rápida o suficiente para que percebamos objetos em movimento. Cada imagem estática corresponde a um quadro no vídeo. Um vídeo é tipicamente composto por 30 quadros por segundo, ou 1800 quadros por minuto, ou 108 mil quadros por hora. Esse grande volume de dados é um dos motivos que torna essa área de pesquisa tão desafiadora. Com a popularização do vídeo digital (veja http://www.youtube.com por exemplo), novas aplicações que exijam a sua manipulação, busca e navegação, demandam uma nova estrutura para esta mídia. Tradicionalmente em mídias analógicas como fitas de vídeo-cassete, a única forma disponível de navegação é a seqüencial. Com o armazenamento do vídeo em computadores, formas mais sofisticadas de acesso se tornaram possíveis. O Moving Picture Experts Group (MPEG), ao criar o padrão MPEG-4, em 1998, apresentou uma decomposição do conteúdo audiovisual em objetos de mídia que podem ser combinados e reutilizados de formas diferentes em aplicações distintas. Posteriormente, em 2001, o grupo apresentou seu novo padrão MPEG-7, formalmente chamado Multimedia Content Description Interface. O padrão acrescenta mecanismos de anotação para descrever formas, cores, texturas e movimento presentes no vídeo. Mais do que isso, o MPEG-7 permite a estruturação de diversos elementos espaço-temporais em relações de antes/depois, à frente/atrás, acima/abaixo, parte/todo. Para possibilitar novas formas em seu envio, consulta e consumo, o vídeo digital deve estar estruturado. Considere, por exemplo, um sistema de busca em acervos de vídeo digital, como mostrado na Figura 1. A estruturação incrementa a eficiência dos extratores de características pois estes não necessitam mais efetuar processamento quadro-a-quadro. A própria estrutura em si pode conter também características de interesse, para responder questões como: • Quais os segmentos que compõem a primeira cena do filme? • Onde mais se encontra este personagem? • Quais os segmentos filmados neste cenário? Assim, torna-se necessário definir uma unidade para a decomposição do vídeo que leve a uma estrutura útil às várias possíveis aplicações.
2
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
Figura 1. Um sistema para recuperação de conteúdo em vídeo digital.
1.2
Estruturação e tomadas
Além dos quadros, a tomada é outra estrutura importante do vídeo. Uma tomada2 é uma seqüência de quadros que mostra uma ação contínua no tempo e no espaço. Cenas são obtidas pela combinação de várias tomadas e delas obtem-se o vídeo completo, como ilustra a Figura 2. A transição de uma tomada para a seguinte pode ser feita através da simples concatenação de quadros ou da aplicação de efeitos mais complexos de edição, como dissoluções e fades, que sobrepõem segmentos das duas tomadas na forma de uma passagem gradual de uma para a outra, como visto na Figura 3. As tomadas são as estruturas com a mais fina granularidade em relação à unidade de ação, sendo a base para a maioria dos sistemas para segmentação e sumarização de vídeo [11, 8]. De modo similar à decomposição de texto em seções, parágrafos e frases, a divisão de vídeo em tomadas pode ser utilizada para a indexação de vídeo e construção de sumários, promovendo formas eficientes de busca e navegação. Além de navegação e busca, várias outras aplicações podem se beneficiar da estruturação por tomadas. Ferramentas automáticas e semi-automáticas para colorização de vídeos em preto e branco podem associar mapas de cores distintos à tomadas diferentes, agilizando o trabalho dos editores. A restauração de vídeos antigos pode ser auxiliada de forma semelhante, reaproveitando conteúdo e configurações entre tomadas similares [8]. 2 Utilizaremos
“tomada” neste trabalho como tradução do termo “shot”.
RITA • Volume X • Número 1 • 2008
3
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
Figura 2. Estruturação de vídeo, como visto em Lienhart et al. [11].
1.3
Sumarização e indexação
Grandes quantidades de informação, como as disponíveis em vídeo (e em acervos de vídeo) necessitam de técnicas eficientes de navegação e busca. A navegação exige uma exibição sucinta e representativa do conteúdo do material, como os sumários utilizados em livros e revistas. Já a busca se beneficia da construção de índices que referenciem de modo apropriado os elementos desejados. Uma forma de representar segmentos do vídeo é a utilização de um ou mais quadros-chaves. Considere como exemplo a Figura 4. Se desejamos obter um sumário
Figura 3. Uma transição gradual (dissolução) em Airline Safety and Economy (disponível via The Open Video Project [13]).
4
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
visual conciso do vídeo em questão, podemos admitir que há grande redundância entre os quadros da seqüência, de modo que um único deles poderia representar de modo satisfatório todo o conteúdo do segmento para fins de navegação. Devido a sua unidade em termos de tempo e espaço, uma tomada é adequada não só à procura de quadros chaves como também para a construção de mosaicos. Mosaicos gerados por técnicas como strip pasting, a partir dos quadros de uma tomada, podem representar, em uma única imagem, toda a ação contida em um segmento do vídeo. Quadros-chaves e mosaicos podem ser utilizados na criação de índices, através da extração de características de imagem, como cor, textura e forma. Já as tomadas são adequadas para a extração de características envolvendo movimento. Sistemas complexos para problemas de detecção de padrões, como reconhecimento de faces, podem se beneficiar dessas representações sucintas do conteúdo e ter seus desempenhos incrementados, pois podem operar em uma massa menor de dados, como visto anteriormente na Figura 1. 1.4
Organização deste trabalho
A próxima seção descreve algoritmos de segmentação de vídeo, em particular, para a detecção de cortes. A forma de avaliação desses algoritmos é apresentada na Seção 3, e a Seção 4 apresenta características utilizadas para a detecção de cortes entre tomadas de vídeo. A Seção 5 discute como definir o limiar para otimizar a detecção de cortes e a Seção 6 introduz o problema de indexação e recuperação de vídeo a partir de conteúdo visual, e ilustra uma possível aplicação baseada em filtros para detecção de faces. Algoritmos para o processamento de vídeo em OpenCV são descritos na Seção 7. A Seção 8 conclui esse tutorial.
2
Segmentação de Vídeo
O problema de segmentação de vídeo em tomadas (shot boundary detection) é um passo importante para sua estruturação e para a análise de eventos. A passagem de uma tomada para outra representa uma troca de contexto essencial se estamos interessados, por exemplo, na construção de uma imagem panorâmica, no estudo da trajetória de um objeto ou qualquer outra análise dependente de unidade temporal e/ou espacial. Podemos representar um vídeo digital como uma seqüência V = hq1 , q2 , ..., qn i composta por quadros qi , imagens de resolução M × N . Ele é obtido pela monta-
RITA • Volume X • Número 1 • 2008
5
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
Figura 4. Tomada de Airline Safety and Economy.
6
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
gem de várias tomadas em um processo de edição, onde cada par consecutivo de tomadas é separado por uma transição. Pode-se representar uma transição Ti entre duas tomadas consecutivas Si e Si+1 por um par de índices (s, t), s < t, tais que Si = h..., qs−1 , qs i e Si+1 = hqt , qt+1 , ...i, como exibido na Figura 5. A forma mais simples de transição entre duas tomadas consecutivas é o corte, onde t = s + 1, ilustrado na Figura 6. Já as transições graduais ocorrem quando t > s + 1, onde os quadros no intervalo entre s e t são editados, formados por uma composição dos quadros originais das duas tomadas em questão. É o que ocorre entre as tomadas S2 e S3 na Figura 5.
Figura 5. Montagem de um vídeo a partir de quatro tomadas.
Figura 6. Um corte em Challenge at Glen Canyon (disponível via The Open Video Project [13]). Transições graduais obtidas pela manipulação das cores ou da intensidade luminosa dos quadros de duas tomadas sucessivas são chamadas transições cromáticas
RITA • Volume X • Número 1 • 2008
7
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
[7]. Nesta categoria, os efeitos de edição mais largamente utilizados são os fades (diminuição progressiva da luminosidade nos quadros) e as dissoluções (transformação gradual de uma tomada para a seguinte). Além das cromáticas, as transições graduais podem ser espaciais como em wipes, onde uma cena é deslocada espacialmente para a entrada da próxima cena. Dada a complexidade para detecção de transições graduais, nesse tutorial trataremos apenas de cortes. 2.1
Análise do problema
Hanjalic [8] apresenta uma análise do problema de delimitação de tomadas. A base para a resolução do problema reside no fato que quadros em torno de uma transição geralmente apresentam uma mudança significativa em seu conteúdo visual. O processo de detecção consiste no reconhecimento de descontinuidades no fluxo do conteúdo visual da seqüência de vídeo. Toma-se uma característica do conteúdo visual dos quadros que será utilizada como base para o método, junto a uma métrica para mensurar a variação z l (i) = z(qi , qi+l ) dessa característica entre dois quadros qi e qi+l , onde l ≥ 1 é uma distância inter-quadros (um passo). Cada z l (i), 1 ≤ i ≤ n, é comparado por um detector a um limiar K(i), decidindo-se assim se qi consiste ou não em um limite de uma tomada. O Algoritmo 1 a seguir sumariza o processo: Algoritmo 1 (Determinação de descontinuidades) Dada uma seqüência de vídeo V = hq1 , q2 , ..., qn i, encontra uma seqüência de transições T = hT1 , T2 , ..., Tv i em V . D1. [Inicialize.] Atribua i ← 1, T ← hi. D2. [Calcule a variação.] Faça o processamento adequado dos quadros qi e qi+l e calcule z l (i). D3. [Obtenha o limiar.] Calcule K(i). D4. [Excedeu?] Se z l (i) > K(i), adicione a nova transição T = (i, i + l) a T e atribua i ← i + l + 1. Vá para D6. D5. [Incremente i.] Atribua i ← i + 1. D6. [Fim do vídeo?] Se i ≥ n, o algoritmo termina. Caso contrário, volte a D2. A maioria dos algoritmos apresentados pela literatura são variações do Algoritmo 1, sobretudo em relação ao parâmetro l e as funções d(qi , qj ) e K(i). Para o
8
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
sucesso do Algoritmo 1, o par característica/métrica utilizados em z l (i) deve ser tão ¯ o intervalo mínimo de valores tal que zl (i) ∈ R ¯ discriminante quanto possível. Seja R para todo i onde qi e qi+l estão dentro de uma mesma tomada. Analogamente, seja R um intervalo mínimo de valores tal que zl (i) ∈ R para todo i onde qi e qi+l estão em tomadas diferentes. A função zl (i) é tão discriminante quanto menor for a intersecção ¯ como indicado na Figura 7. Uma grande intersecção torna-se fonte de entre R e R, falsos positivos e falsos negativos durante a fase de detecção, degenerando a qualidade da solução.
¯ e a desempenho da detecção [8]. Figura 7. Intervalos R e R 2.2
Fatores extremos
As maiores diferenças no conteúdo visual de quadros em uma mesma tomada são causadas principalmente por movimentações de objetos, movimentação da câmera e mudanças de iluminação. Características e métricas muito sensíveis a esses ¯ (R ¯ se expande). Se z l (i) eventos terão uma grande sobreposição dos intervalos R e R pudesse ser construída sobre características e métricas robustas em relação a esses ¯ seria pequena, mas também tería-se intervalos confatores, não só a interseção R ∩ R sistentes mesmo em vídeos de natureza diferente. Um filme de ação ou um vídeo clip tem níveis maiores de movimentação e alteração de luminosidade do que um drama ou uma entrevista. Dizer que os intervalos são consistentes significa desempenho similar em vídeos diferentes sem a necessidade de ajustes manuais ou qualquer outra intervenção humana [8]. Porém, grandes alterações na luminosidade da tomada ou casos extremos de
RITA • Volume X • Número 1 • 2008
9
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
movimentação de objetos e câmera são situações difíceis mesmo para um par característica/métrica robusto. Tais situações, combinadas às descontinuidades sutis nas transições graduais, requerem o uso de algum conhecimento extra para uma melhoria na desempenho do detector. Várias informações extras podem auxiliar um detector. Conhecimento sobre os padrões assumidos por z l (i) durante um corte ou seu comportamento no decorrer de fades ou dissoluções são dados que podem ser utilizados na etapa de decisão para evitar falsas conclusões. No caso de dissoluções, por exemplo, Yeo e Liu [18] mostraram que, para l suficientemente grande, o gráfico de z l (i) assume a forma de um trapézio durante uma dissolução, o que os autores chamam de “platôs”. Além da análise de descontinuidades, há outras informações que podem auxiliar na detecção e na determinação da natureza de uma transição. Alattar [1] observou que a variância da luminosidade dos quadros assume um padrão parabólico durante uma dissolução. Já Guimarães et al. [6] mostraram que há uma contração nos histogramas de luminosidade durante fades. Há, também, certas informações a priori que podem ser utilizadas sem qualquer análise dos quadros da seqüência de vídeo. Vasconcelos e Lippman [15, 16] embutiram seu detector com informação sobre a duração das tomadas. Imediatamente após o final de uma tomada, uma nova transição tem poucas chances de ocorrer. Contudo, a probabilidade de ocorrência de uma transição vai aumentando conforme o tempo passa. Tal idéia é retomada na abordagem probabilística de Hanjalic [8].
3
Avaliação de desempenho
O sucesso de um delimitador de tomadas é medido pela acurácia com que ele identifica os extremos qs e qt de uma transição. As medidas de cobertura e precisão3 , comumente utilizadas na área de recuperação de informação, são utilizadas como indicadores da qualidade da solução dada por um delimitador contra uma solução ideal anotada por um observador humano. Sua função é mensurar a quantidade de falsos negativos e falsos positivos em uma solução proposta, ou em outras palavras, avaliar a proporção de transições reais perdidas e falsas transições inseridas por engano do detector. Considere Tcorte = {T1 , T2 , ..., Tm } o conjunto de cortes reais existentes em uma seqüência de vídeo V (obtido por um avaliador humano ou através do esquema original de edição). Seja T¯corte = {T¯1 , T¯2 , ..., T¯p } o conjunto de cortes T¯i encontrados pelo 3 Os termos “cobertura” e “precisão” serão utilizados aqui no lugar das palavras inglesas “recall” e “precision”
respectivamente.
10
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
delimitador para V . A cobertura R, utilizado para avaliar a solução em relação a falsos negativos, é definido para cortes como
Rcorte =
|Tcorte ∩ T¯corte | . |Tcorte |
(1)
Para avaliar o número de falsos positivos da solução, utilizamos a precisão P, definida por
Pcorte =
4
|Tcorte ∩ T¯corte | |T¯corte |
(2)
Características e métricas
Como visto na Seção 2.1, utiliza-se uma medida de variação do conteúdo visual entre dois quadros como base para a detecção de transições. Diversas medidas foram propostas na literatura, baseadas em características espaciais (pixels, super-pixels e bordas), características de cor e na estrutura da compressão MPEG. 4.1
Domínio espacial: comparação pixel a pixel
A comparação direta entre os pixels correspondentes de dois quadros qi e qj foi uma das primeiras características exploradas na literatura. Uma das métricas mais simples é dada por zpixel (qi , qj ) =
M N 1 XX | qi [x, y] − qj [x, y] |, M N x=1 y=1
(3)
para quadros em níveis de cinza ou, de forma equivalente, zpixel (qi , qj ) =
1 MN
X
M X N X
| qi [x, y, c] − qj [x, y, c] |
(4)
c∈{R,G,B} x=1 y=1
para quadros coloridos (no caso, no domínio RGB). Infelizmente, tal métrica é incapaz de discernir entre uma pequena mudança em uma grande área dos quadros e uma grande alteração em uma pequena área, o que a torna muito sensível à movimentação de objetos e da câmera [9]. Devido a
RITA • Volume X • Número 1 • 2008
11
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
isso, Nagasaka e Tanaka [12] e Zhang et al. [20] propuseram considerar apenas os pixels onde a alteração de valor fosse considerável: 1 se |p1 − p2 | > kpixel , dpixel (p1 , p2 ) = (5) 0 caso contrário. M N 1 XX dpixel ( qi [x, y], qj [x, y] ), M N x=1 y=1
zpixel (qi , qj ) =
(6)
onde p1 e p2 são valores em níveis de cinza (entre 0 e 255) e kpixel um limiar fixado (a extensão para quadros coloridos decorre de forma análoga). Esta métrica é capaz de filtrar alterações irrelevantes entre pixels mas ainda é muito sensível aos fatores extremos, sobretudo movimentação. 4.2
Domínio espacial: blocos
Buscando utilizar informação local para incrementar a robustez da métrica em situações de movimento, alguns autores substituiram a comparação entre pixels pela comparação de blocos de pixels, que dividem o quadro em regiões retangulares de mesmas dimensões e sem sobreposição entre si. Shahraray propôs a soma ponderada das diferenças entre blocos correspondentes: zbloco (qi , qj ) =
B X
cb dbloco (qi [b], qj [b]),
(7)
b=1
onde dbloco mede a diferença entre dois blocos. Kasturi e Jain [10] assumem cb = 1 para todos os blocos e fazem uso da verossimilhança da seguinte forma: λ( qi [b], qj [b] ) =
[
µ(q [b])−µ(q [b]) σ 2 (qi [b])+σ 2 (qj [b]) + ( i 2 j )2 ]2 2 , σ 2 (qi [b]) · σ 2 (qj [b])
dbloco ( qi [b], qj [b] ) =
1 0
se λ(bu , bv ) > kλ , caso contrário.
(8)
(9)
onde σ 2 (q[b]) e µ(q[b]) são, respectivamente, a variância e a média da intensidade luminosa no bloco q[b]. Comparada a diferença pixel a pixel, esta métrica consegue reduzir o número de falsos positivos devido a sua tolerância a movimentos lentos de câmera e/ou objetos [20]. Contudo, pode gerar falsos negativos quando blocos muito diferentes têm probabilidades com funções de densidade similares, além do fato que
12
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
os cálculos envolvidos nas equações 3.6 e 3.7 tornam muito lenta a computação da medida [20, 17, 5]. Xiong et al. [17] estudaram como uma amostragem baseada em blocos poderia impactar a eficiência da segmentação. Eles argumentam que o tamanho do bloco tem estreita relação com a robustez do método a movimentações: quanto menor o bloco, mais ele se aproxima da comparação entre pixels e torna-se mais sensível a tais eventos. A partir dessa observação, os autores definem os blocos como quadrados de lado 2δ, onde δ é o máximo movimento, em pixels, entre duas imagens. Eles alegam que, na prática, δ = 10 é uma estimativa que leva a bons resultados. Isto garante que, não havendo uma transição abrupta, ao menos um quarto dos pixels de blocos correspondentes são iguais. A similaridade entre os blocos é mensurada através de dbloco (q1 [b], q2 [b]) =
1 0
se | µ(q1 [b]) − µ(q2 [b]) | > kbloco , , caso contrário.
(10)
onde µ(q[b]) é a média da intensidade luminosa no bloco q[b] e kbloco um limiar (a equação 3.8 pode ser vista como generalização da equação 3.3). A diferença é dada por zbloco (qi , qj ) =
1 X db (qib , qjb ) , |Bs |
(11)
b ∈ Bs
sendo Bs uma amostra do conjunto blocos B. Os autores provam que o desempenho da medida degenera muito pouco com a amostragem, podendo Bs ser consideravelmente menor que o conjunto de todos os blocos B. 4.3
Domínio espacial: bordas
Zabih et al. [19] propõem uma métrica baseada nos conceitos de pixel de borda entrante4 e pixel de borda ausente5 . Um pixel de borda entrante entre dois qi e qj é um pixel (x, y) de borda de qj que não possua um correspondente em uma vizinhança de qi (x, y). Similarmente, um pixel de borda ausente é um pixel (x, y) de bordas de qi que não possua um correpondente em uma vizinhança de qj (x, y). Mais formalmente, seja fi a imagem binária obtida pelo detector de bordas de Canny aplicado a qi . Seja também f¯i a imagem binária obtida pela dilatação morfológica de fi por um elemento estruturante (um “diamante” de altura e largura igual a 2r + 1 pixels). Define-se daí a fração de pixels ausentes, ρout , por 4 Do 5 Do
original entering edge pixel. original exiting edge pixel.
RITA • Volume X • Número 1 • 2008
13
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
P
x,y
ρout (qi , qj ) = 1 −
fi (x + δx, y + δy) · f¯j (x, y) P . x,y f (x, y)
(12)
Analogamente, obtem-se a fração de pixels entrantes, ρin , por P ρin (qi , qj ) = 1 −
f¯i (x + δx, y + δy) · fj (x, y) P . x,y f (x + δx, y + δy)
x,y
(13)
Os valores δx e δy são inteiros que representam uma translação que alinhe qi e qj , obtidos por algoritmos de compensação de movimento. A partir daí, tem-se uma nova métrica, a fração de bordas alteradas zρ , dada por zρ (qi , qj ) = max( ρout(qi , qj ), ρin(qi , qj ) ).
(14)
A detecção de transições realizada pelos autores baseia-se nos padrões assumidos por ρin e ρout entre quadros sucessivos ao longo da seqüência de vídeo. Cortes apresentam picos em ρin e ρout . Fades-in apresentam valores crescentes de ρin ao longo do tempo, o mesmo ocorrendo de modo análogo com fades-out e ρout . Dissoluções são marcadas por valores crescentes de ρout e um pico de ρin e ρout na metade da transição, seguida por valores decrescentes de ρin . 4.4
Domínio de cores: histogramas
Uma das características mais utilizadas na literatura é o histograma de intensidade luminosa. O histograma de um quadro qi em níveis de cinza no intervalo [0, L − 1] é um vetor hi [l] = nl onde l é o l-ésimo nível de cinza e nl o número de pixels na imagem que apresentam tal valor. Os elementos hi [l] são comumente chamados bins. Baseando-se nessa característica Nagasaka e Tanaka [12] e Zhang et al. [20] propõem o uso da diferença entre histogramas bin-a-bin
zh (qi , qj ) =
L−1 X
| hi [l] − hj [l] |.
(15)
l=0
Ao tratarem-se de quadros coloridos, há várias alternativas. Uma delas é reduzí-los a quadros em escala cinza. De acordo com o padrão de vídeo NTSC: l = 0, 299 R + 0, 587 G + 0, 114 B
14
(16)
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
. Contudo, há várias formas para a construção de um histograma de cores. Zhang et al., por exemplo, utilizam um código para cada cor obtido tomando-se os dois bits mais significativos das componentes básicas R, G e B. Com esse código c, a variação por histograma pode ser calculada através de
zh (qi , qj ) =
64 X
| hi [c] − hj [c] |.
(17)
c=1
Há opções a diferença bin-a-bin. Nagasaka e Tanaka sugerem o uso do χ2 como medida, revista posteriormente por Gargi et al. [5]: (hi [l]−hj [l])2 l=1 hj [l] 2 PL (hi [l]−h j [l]) l=1 hi [l]
( PL zχ2 (qi , qj ) =
se hj [l] 6= 0, caso contrário.
(18)
Contudo, de acordo com os testes de Zhang et al. e Gargi et al., o χ2 não possui desempenho melhor que a de zh 15, sendo ainda mais sensível às várias formas de movimentação. Por outro lado, Gargi et al. identificam em seus testes um melhor desempenho da medida dada pela intersecção de histogramas, definida por
z∩ (qi , qj ) = 1 −
L X
min(hi [l], hj [l]).
(19)
l=1
Quadros díspares podem ter histogramas similares, o que seria uma possível fonte de falsos negativos6 . Histogramas são mais robustos à movimentação de objetos sobre um fundo constante do que as métricas em domínio espacial, mas permanecem sensíveis à movimentação de câmera.
5
Limiarização e detecção
A forma mais comum de delimitação de tomadas é utilizar o Algoritmo 1 com l = 1 e K(i) = kcorte para todo i. Em outras palavras, calcula-se a variação entre todo quadro qi e seu sucessor imediato qi+1 , obtendo-se assim um sinal (Figura 8) que é posteriormente limiarizado frente a uma constante kcorte , um limiar global para todo o vídeo. 6A
ocorrência de tais eventos é, felizmente, pouco freqüente.
RITA • Volume X • Número 1 • 2008
15
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
Figura 8. Gráfico i × zh (qi , qi+1 ) de um segmento de Airline Safety and Economy. Embora seja uma solução razoável para a detecção de cortes, tal detector não tem um comportamento adequado com relação às transições graduais. A região entre os quadros 4500 e 4525, referente a uma dissolução em Airline Safety and Economy, ilustra a situação: um limiar global sobre o sinal poderia não identificar a transição, de valores menores se comparados aos cortes em 4875, 4935 e 5028, ou ainda declarar como corte cada ponto da transição.
6
Indexação e Recuperação de Vídeo
A busca por conteúdo visual em repositórios de vídeo digital é realizada através de anotações na forma de texto, realizadas manualmente. Porém, não é sempre que essa informação se encontra disponível e, mesmo quando ela existe, em geral ela é incompleta e inexata para uma grande variedade de buscas. Por exemplo, buscas podem ser bem genéricas como “cenas de praia”, ou específicas como “Presidente Lula surfando no Guarujá”. Como as informações visuais podem ser difíceis de serem expressadas em palavras, alguns sistemas propoem o uso de exemplos na forma de imagens ou esboços. Outros sistemas propoem o uso de filtros para a detecção de objetos específicos que permitiriam a construção de perguntas com conteúdo semântico mais elevado. Nesse trabalho, vamos introduzir um sistema de indexação automática de vídeo utilizando faces. Aplicações semelhantes foram sugeridas em [3, 4] A Figura 9 ilustra uma possível interface para um sistema assim. Essa interface é constituída por 3 partes. A primeira parte (P1), presente no canto superior esquerdo, permite a visualização das faces encontradas no vídeo. A segunda parte (P2), no canto superior direito, permite a visualização de um vídeo, e a terceira parte
16
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
(P3), localizada na parte inferior da interface, mostra os quadros-chave que representam todas as tomadas extraídas do vídeo. As tomadas estão organizadas de forma cronológica, sendo possível dessa forma visualizar o vídeo como um todo na forma de um mosaico de quadros-chave. Ao se clicar em um quadro-chave em P3, o vídeo passa a ser exibido em P2 a partir dessa tomada. Ao se clicar em uma face em P1, as tomadas que contem aquela face são realçadas com uma borda em vermelho. Dessa forma é possível visualizar todas as personagens de um vídeo em P1, saber em que tomadas elas aparacem, e facilmente acessar qualquer tomada de interesse.
Figura 9. Interface de um sistema para indexação e recuperação de vídeos baseado em faces
7
Implementação dos Algoritmos usando OpenCV
O OpenCV (Intel Open Source Computer Vision Library) é uma biblioteca de código aberto (open source) desenvolvida pela Intel em C/C++ que implementa várias rotinas populares para o processamento de imagens e algoritmos de visão computa-
RITA • Volume X • Número 1 • 2008
17
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
cional. O código, documentação e instruções para instalação do OpenCV podem ser obtidos em http://sourceforge.net/projects/opencvlibrary. O OpenCV pode ser utilizado para a construção de um sistema para busca e recuperação de vídeo baseado em faces como descrito na seção anterior. Para isso, vamos utilizar o seguinte esqueleto de programa para detectar os cortes e as faces contidas em um arquivo de vídeo: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
int main( int argc, char** argv ) { CvCapture* capture = 0; IplImage *frame[2] = {0,0}; int i = 0; cvNamedWindow("Video Window", 1); if (argc == 2) capture = cvCaptureFromFile ( argv[1] ); else printf("Usage: %s %s\n", argv[0], "video_file_name"); while (cvGrabFrame( capture)) { frame[i%2] = cvRetrieveFrame( capture ); cvShowImage("Video Window", frame[i%2]); if(shotBoundary(frame)) storeCut(i); if (detectFaces(frame[i%2])) storeFaces(frame[i%2], i); i++; } cvReleaseCapture( &capture ); return 0; }
Esse esqueleto está bastante simplificado para facilitar sua leitura e entendimento, e não mostra, por exemplo, itens importantes como os protótipos das funções, include files, e testes de consistência dos ponteiros capture e frame devolvidos pelas funções. O programa recebe o nome de um arquivo de vídeo, que corresponde ao parâmetro argv[1] definido pelo usuário na linha de comando. Caso o número de parâmetros não seja correto, o programa fornece uma mensagem de erro ao usuário. A função cvCaptureFromFile prepara um arquivo de vídeo para ser processado. Ela é bastante similar a função cvCapture, que prepara a captura de vídeo a partir de uma câmera. A função cvGrabFrame captura uma imagem (do arquivo ou câmera), que é acessada pela função cvRetrieveFrame. Essas duas funções permitem que o OpenCV capture imagens rapidamente. A função cvNamedWindow cria
18
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
uma janela de nome “Video Window” e cvShowImage mostra a imagem capturada em frame[i%2] na janela. Todas essas funções para captura e exibição de imagens estão definidas no pacote highgui.h do OpenCV. Você pode usar uma estrutra similar para desenvolver suas próprias ferramentas. Observe que a variável i é utilizada para contar o número de quadros processados até o momento. Quando o quadro é par, ele é armazenado em frame[0] e, quando é ímpar, ele é armazenado em frame[1]. A função shotBoundary recebe esses 2 quadros e verifica se existe um corte entre eles. Em caso afirmativo, o quadro atual é marcado como o início de uma nova tomada e o quadro anterior como o fim da tomada anterior pela função storeCut. Finalmente a função detectFaces verifica se há faces no quadro capturado e, em caso afirmativo, chama a função storeFaces que organiza as faces em cada quadro para que possam ser utilizadas pela interface. Mais detalhes sobre as funções detectFaces e shotBoundary estão disponíveis em http://www.ime.usp.br/˜hitoshi/wvc08. A função detectFaces é baseada no exemplo fornecido como parte da documentação do OpenCV, que detecta faces utilizando filtros de Haar em cascata. Já a função shotBoundary é uma versão muito simplificada do programa desenvolvido na dissertação de mestrado disponível em [14]. As estruturas a serem utilizadas pela interface definiram o que as funções storeCut e storeFaces devem realizar, e não são tratadas nesse tutorial.
8
Conclusão
Nesse trabalho foram descritos alguns algoritmos básicos para segmentação, indexação e busca automática de conteúdo visual em vídeo. Primeiramente foram introduzidos algoritmos para dividir o vídeo em seqüências de quadros com continuidade temporal, conhecidas como tomadas. As tomadas podem ser utilizadas para simplificar o processamento, o acesso, e a visualização do vídeo. A indexação de conteúdo visual, que tipicamente é feita de forma manual, pode ser automatizada com a utilização de filtros, como descrevemos em [2]. Introduzimos uma ferramenta que ilustra o grande potencial de aplicações que integrem a visualização, busca e manipulação de vídeo utilizando apenas um filtro para detecção de faces. Finalmente sugerimos um esqueleto de programa para o processamento de vídeo usando OpenCV. Os algoritmos apresentados aqui são de certa forma simples e serve apenas para introduzir o leitor a essa área que vem se expandindo muito rapidamente. Para conhecer detalhes de algoritmos de segmentação mais complexos para detecção de transições
RITA • Volume X • Número 1 • 2008
19
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
graduais, sugerimos a dissertação de Santos [14].
Agradecimentos Os autores gostariam de agradecer à Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) e à Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) pelos auxílios financeiros concedidos a esse projeto.
Referências [1] Adnan M. Alattar. Detecting and compressing dissolve regions in video sequences with a dvi multimedia image compression algorithm. Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS), 1:13–16, Maio 1993. [2] R.A. Barbosa, F. Silva, T.T. Santos, and C.H. Morimoto. An extensible automatic video browsing tool. In Workshop Teses e Dissertações - Sibgrapi 05, Natal, RN, October 2005. [3] Csaba Czirjek, Noel O’Connor, Sean Marlow, and Noel Murphy. Face detection and clustering for video indexing applications. In Proceedings of the ACIVS 2003 - Advanced Concepts for Intelligent Vision Systems, pages 3–15. IEEE, September 2003. [4] Andrew Fitzgibbon and Andrew Zisserman. On affine invariant clustering and automatic cast listing in movies. In Proc. of 7th the European Conference on Computer Vision, volume 3, pages 304–320. Springer Verlag, 2002. [5] Ullas Gargi, Rangachar Kasturi, and Susan H. Strayer. Performance characterization of video-shot-change detection methods. IEEE Transactions on Circuits and Systems for Video Technology, 10(1):1–13, 2000. [6] Silvio Jamil Ferzoli Guimarães, Michel Couprie, Arnaldo de Albuquerque Araújo, and Neucimar Jerônimo Leite. Video segmantation based on 2d image analysis. Pattern Recognition Letters, 24:947–957, 2003. [7] A Hampapur, T. Weymouth, and R. Jain. Digital video segmentation. In Proceedings of the second ACM international conference on Multimedia, pages 357–364. ACM Press, 1994. [8] Alan Hanjalic. Shot-boundary detection: Unraveled and resolved? IEEE Transactions on Circuits and Systems for Video Technology, 12(2):90–105, fevereiro 2002.
20
RITA • Volume X • Número 1 • 2008
Segmentação, Indexação e Recuperação de Vídeo Utilizando OpenCV
[9] F Idris and S. Panchanathan. Review of image and video indexing techniques. Journal of Visual Communication and Image Representation, 8(2):146–166, June 1997. [10] R. Kasturi and R. Jain. Computer Vision: Principles, chapter Dynamic Vision, pages 469–480. IEEE Computer Society Press, Washington, DC, 1991. [11] Rainer Lienhart, Silvia Pfeiffer, and Wolfgang Effelsberg. Video abstracting. Communications of ACM, 40(12):54–62, 1997. [12] Akio Nagasaka and Yuzuru Tanaka. Automatic video indexing and full-video search for object appearances (abstract). J. Inf. Process., 15(2):316, 1992. [13] The Open Video Project. http://www.open-video.org. [14] Thiago Teixeira Santos. Segmentação automática de tomadas em vídeo. Master’s thesis, Instituto de Matemática e Estatística, Universidade de São Paulo, 2004. [15] Nuno Vasconcelos and Andrew Lippman. A bayesian video modeling framework for shot segmentation and content characterization. In Proceedings of the 1997 Workshop on Content-Based Access of Image and Video Libraries (CBAIVL ’97), page 59. IEEE Computer Society, 1997. [16] Nuno Vasconcelos and Andrew Lippman. Statistical models of video structure for content analyis and characterization. IEEE Transactions on Image Processing, 9(1):3–19, Janeiro 2000. [17] Wei Xiong, John Chung-Mong Lee, and Man-Ching Ip. Net comparison:a fast and effective method for classifying image sequences. In Proc.of SPIE Conference on Storage and Retrieval for Image and Video Databases III, volume 2420, pages 318–328, San Jose, CA, 1995. [18] Boon-Lock Yeo and Bede Liu. Rapid scene analysis on compressed video. IEEE Transactions on Circuits and Systems for Video Technology, 5:533–544, December 1995. [19] Ramin Zabih, Justin Miller, and Kevin Mai. A feature-based algorithm for detecting and classifying scene breaks. Proceedings of ACM Mutlimedia 95, pages 189–200, Novembro 1995. [20] HongJiang Zhang, Atreyi Kankanhalli, and Stephen W. Smoliar. Automatic partitioning of full-motion video. Multimedia Systems, 1(1):10–28, 1993.
RITA • Volume X • Número 1 • 2008
21
