Integração de Métodos Baseados em Diferença de Quadros para Sumarização do Conteúdo de Vídeos Carlos A. F. Pimentel Filho, Celso A. Saibel Santos, Thomas A. Buck NUPERC - Universidade Salvador R. Ponciano de Oliveira, 126 41950-275 Salvador – BA – Brasil Tel: (+55)(71) 3330-4640 Fax: (+55)(71) 3330-4630
[email protected], {saibel,thomas}@unifacs.br ABSTRACT This paper focuses on automatic video keyframe extraction. Keyframes are usefull for video summarization and supporting content based video retrieval. The paper analyses some wellknown keyframe extraction methods based on interframe difference against two parameters: keyframes lost and redundancy. As result, this work shows these parameters must be reduced when these methods are put to work together.
Categories and Subject Descriptors H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing – Abstracting methods and Indexing methods.
General Terms Algorithms, Management, Measurement, Experimentation.
Keywords
still-image abstract ou ainda, static storyboard – são uma coleção de quadros extraídos, a partir de um determinado critério, para representar o conteúdo do vídeo. Esse artigo trata exatamente do último caso, isto é, da geração automática de um sumário do vídeo no formado static storyboard ou quadros-chave. Um dos pontos a serem observados nesse processo é que a extração de quadros-chave seja feita de modo que o sumário apresente, ao mesmo tempo, uma baixa redundância entre os quadros capturados e baixa perda de quadros que representem o conteúdo visual do vídeo. De fato, a perda e a redundância possuem forte correlação e o artigo mostra como é possível obter a melhor relação entre essas duas variáveis para alguns métodos de extração de quadros-chave. O artigo mostra também que a integração de métodos de extração de quadroschave produz uma relação perda x redundância superior àquela obtida com a aplicação de cada método individualmente.
Keyframe extraction, video summarization, video indexing.
1. INTRODUÇÃO As necessidades de gerenciamento de grandes repositórios de vídeos têm impulsionado o desenvolvimento de sistemas de recuperação orientados ao conteúdo, CBVR (content based video retrieval) [1]. Embora os resultados a serem apresentados se insiram em um contexto mais amplo de um sistema CBVR com o objetivo de recuperar vídeos a partir das características dos seus quadros (ver Figura 1), este artigo enfoca especificamente o problema da extração automática de quadros-chave para a sumarização do conteúdo visual de um vídeo. A sumarização de vídeo provê uma forma rápida de acesso ao conteúdo de vídeo num sistema de recuperação [2]. De acordo com Pfeiffer [3], o sumário de um vídeo é definido como uma seqüência de imagens estáticas ou em movimento que representa o conteúdo de um vídeo. Essa representação resumida permite que o espectador assimile alguma informação concisa sobre o conteúdo completo do vídeo de forma rápida e simplificada, enquanto a mensagem original é preservada. Existem basicamente duas formas de sumarização de vídeo: Video skim e quadros-chave (ou key frames) [4]. O Video skim – também conhecido como moving-image abstract ou moving story board – é uma sumarização formada por segmentos importantes do vídeo (com seu respectivo canal de áudio), de modo a resumir o conteúdo como um todo. Os trailers de filmes são exemplos típicos desse tipo de sumarização. Os quadros-chave – também conhecidos como key frames, representative frames, r-frames,
Vídeo Oráculo
Vídeo Parsing
Figura 1 – Ambiente de indexação e recuperação de vídeos. O artigo está estruturado da seguinte maneira: A seção 2 discute a questão da extração dos quadros do vídeo e dos métodos empregados para eleger os seus quadros-chave. A seção 3 apresenta uma avaliação das abordagens para extração de quadros e as considerações gerais sobre cada uma das abordagens avaliadas. A seção final apresenta as conclusões e as perspectivas, seguida pelas referências utilizadas no texto.
2. EXTRAÇÃO DE QUADROS-CHAVE O esquema para extração de quadros-chave utilizado neste artigo faz parte de um projeto de pesquisa de escopo mais amplo. O projeto engloba a construção de um ambiente que dispõe de uma série funcionalidades relacionadas à captura e ao processamento dos quadros dos vídeos e também às operações de indexação, busca e navegação de vídeos [5]. O ambiente, ilustrado na Figura 1, foi estruturado em dois módulos principais: vídeo parsing e vídeo oráculo. O primeiro é responsável pelo processamento das informações associadas ao fluxo do vídeo e o segundo, pela indexação, recuperação e navegação do conteúdo. Em sua essência, os métodos baseados em distância entre quadros para detecção automática de cortes de tomada e extração de quadros-chave utilizados neste artigo são, basicamente, os mesmos. A diferença entre eles está nos limiares aplicados e nos canais de cores empregados em cada método. Outra diferença é que, se qi é um quadro no instante i, na detecção de um corte de tomada, calcula-se a distância entre quadros adjacentes qi e qi+1, enquanto que para a extração de quadros-chave, a diferença é calculada entre o último quadro-chave encontrado, qi, e os próximos qi+n quadros candidatos a serem quadros-chave. Estes métodos têm sido utilizados há algum tempo para a detecção de cortes de tomada, uma vez que se espera que fronteiras de tomadas apresentem uma distância entre os quadros qi e qi+1 acima de um certo limiar. Um dos principais problemas do método, nesse caso, é que ele é intolerante à movimentação brusca de objetos e de câmera [7].
2.1 Comparação de quadros pixel-a-pixel A abordagem mais simples e direta para comparação de quadros é o cálculo da distância entre eles, a partir dos valores dos seus pixels que ocupam a mesma posição espacial. Para isso, pode-se utilizar a norma L1 ou L2 (respectivamente, as Eq. 1 e Eq. 2). Embora as equações não explicitem o canal de cor utilizado na comparação, essas equações são válidas para qualquer um deles.
f k , f l = ∑ f k [i, j ] − f l [i, j ]
Eq. 1
i, j
f k , fl
2
=
2
∑ ( f [i, j ] − f [i, j]) k
l
Eq. 2
i, j
Para a seleção de quadros-chave, o mesmo método pode ser empregado. O primeiro quadro do vídeo, q0, é o primeiro quadrochave selecionado. A partir do último quadro-chave selecionado, é calculada a distância para cada um dos quadros seguintes, até que um limiar seja alcançado. Nesse caso, um novo quadro-chave é selecionado. O Algoritmo 1 ilustra o pseudocódigo do método. 1 2 3 4 5 6 7
i = 0; qChave = q[i]; para (i = 1; i limiar) qChave = q[i]; fim se fim para
onde rk é o k-ésimo nível de cinza, nk é o número de pixels na imagem com ocorrência do valor de intensidade k, n é o número total de pixels na imagem e k = 0,1,2,..., L–1 [8]. A seleção de quadros-chave baseada em histograma pode ser implementada de forma simples, com a substituição da função de distância de pixel-a-pixel no Algoritmo 1, pela função de distância de histograma, ilustrada na Eq. 3. Nessa equação, fi e fj denotam, respectivamente, os quadros i e j; pi e pj, os histogramas de probabilidade dos quadros i e j; e zn( fi , fj ), a função de distância entre os dois histogramas. L −1
zn ( f i , f j ) = ∑ pi [l ] − p j [l ]
Eq. 3
l =o
Embora a Eq. 3 tenha sido apresentada em termos de uma imagem monocromática, ela pode ser aplicada no domínio RGB ou qualquer outro domínio espacial de cor. Assim como no método pixel-a-pixel, a diferença por histograma é calculada para cada um dos canais RGB e os canais I e Q no vídeo parsing. O motivo da exclusão do canal Y deve-se uma característica comum nos vídeos jornalísticos: comumente, eles apresentam flashes e efeitos de transição de tomadas com fading, fazendo com que a comparação por histograma gere muitos quadros-chave redundantes. Dado que flashes e fadings estão relacionados ao brilho da imagem, uma solução é eliminar a componente de luminância (canal Y) no cálculo das distâncias [8].
2.3 Seleção de quadros-chave A seleção de quadros-chave depende dos objetivos da aplicação que os utiliza. Para a aplicação de sumarização e suporte à busca orientada ao conteúdo visual proposta em [5], considera-se que captura de quadros-chave deve apresentar, simultaneamente, a menor perda de quadros e a menor redundância, em comparação a uma referência obtida por intervenção humana. Quadros consecutivos são redundantes se possuírem grande similaridade visual, quantificada pela distância calculada entre eles. Quadros perdidos são aqueles que aparecem na referência, mas não foram capturados pelo método. O número de quadros perdidos e redundantes é influenciado pela escolha adequada do valor do limiar de distância considerado. Se o limiar é baixo demais, muitos quadros redundantes são gerados; se ele é alto demais, muitos quadros podem ser perdidos. A Figura 2 apresenta seqüências de quadros-chave que podem ser obtidos a partir de um vídeo de um telejornal, ilustrando o problema.
a)
b)
Algoritmo 1 – Seleção de quadros-chave por distância.
2.2 Comparação de quadros por histograma Outra técnica muito utilizada na detecção de corte de tomadas está baseada na comparação dos histogramas de intensidade luminosa dos quadros. O histograma de uma imagem digital, com níveis de cinza no intervalo [0, L–1], é uma função discreta p(rk) = nk / n,
c) Figura 2 – Quadros-chave extraídos de um telejornal.
A Figura 2(a) ilustra um subconjunto da seleção de quadros-chave do modelo de referência, selecionados manualmente. A Figura 2(b) mostra o resultado de uma seleção automática de quadroschave com alto nível de redundância e baixa taxa de perdas e a Figura 2(c) ilustra o resultado de uma seleção automática com baixa redundância, mas com grande de perda de quadros-chave.
3. AVALIAÇÃO DOS MÉTODOS Quando aplicados aos espaços RGB e YIQ, os dois métodos baseados em diferença entre quadros da seção 2 permitiram derivar quatro abordagens básicas de extração de quadros-chave, de acordo com os canais de cor utilizados. As abordagens básicas avaliadas – referenciadas como (1), (2), (3) e (4) – estão associadas, respectivamente, às comparações pixel-a-pixel e de histogramas no espaço RGB e entre os canais I e Q, no YIQ. Além da aplicação isolada de cada uma das abordagens básicas, o artigo mostra que é possível melhorar a relação perda versus redundância no processo de captura de quadros-chave através da integração dessas abordagens. As três novas abordagens derivadas correspondem à combinação dos métodos baseados nas diferenças pixel-a-pixel e de histogramas de quadros nos canais RGB (combinação de 1 e 2), nos canais I e Q (combinação de 3 e 4) e, finalmente, à combinação de todas as abordagens básicas (de 1 a 4). A combinação de métodos obriga apenas a uma pequena alteração no Algoritmo 1: ao invés de uma medida de distância isolada, são testadas as medidas de todos os métodos, com a operação lógica AND na condição SE da linha 4.
3.1 Critério de avaliação dos métodos O critério considerado para avaliação dos métodos é a relação entre quadros redundantes gerados e quadros perdidos durante o processo de extração de quadros-chave. A avaliação foi baseada na comparação entre os resultados obtidos por cada uma das abordagens e aqueles gerados através da intervenção humana (e, portanto, tidos como ideais). Drew et al. [9] utilizam o mesmo critério, fazendo uma comparação entre sumários construídos manualmente e outros obtidos de forma automática.
Nas Tabelas 1 e 2, Limiar é o valor de limiar aplicado; KF/S, a média de quadros-chave por tomada; Perda e Red, os percentuais médios de perda e redundância na seqüência gerada, respectivamente; TotP e TotR, o total de quadros perdidos e redundantes, respectivamente, e; Tot é o total de quadros-chave capturados.
3.2 Resultados dos experimentos Os experimentos consistiram em definir o melhor limiar de captura para cada abordagem avaliada, aplicando-se o seguinte critério: o melhor limiar é aquele para o qual as curvas de perda e redundância se cruzam no gráfico de desempenho da abordagem. Intuitivamente, fora desse ponto, ou existe excesso de quadroschave (muita redundância) ou ausência destes (muita perda). O cruzamento das curvas determina, então, o melhor limiar para o método de extração de quadros-chave considerado. Como exemplo, considere o método de comparação de quadros pixel-a-pixel no espaço RGB. A Tabela 2 ilustra os resultados obtidos para o método, variando-se o limiar de captura entre 45 e 75. Note que o limiar poderia variar entre 0 (quadros idênticos) e 255 (um quadro todo branco outro completamente preto). Tabela 2 - Desempenho do método pixel-a-pixel RGB Limiar
KF/S
Perda
Red.
TotP
TotR
Tot
45
2,74
8,2%
65,2%
90
763
1596
52,5
1,94
16,4%
33,2%
158
380
1132
60
1,39
26,3%
14,9%
265
173
809
67,5
1,02
39,8%
7,9%
387
87
595
75
0,71
51,7%
3,1%
505
30
413
No método de diferença pixel-a-pixel RGB, a melhor relação perda x redundância ocorre perto de 22%, conforme o Gráfico 1.
Melhor relação perda x redundância
A seqüência de quadros-chave de referência foi obtida por inspeção visual de uma edição do Jornal Nacional, com os intervalos comerciais. A amostra da edição possui 79.432 quadros, com duração de 44 minutos. Por intervenção humana, foram identificados 582 cortes de tomada e 883 quadros-chave, resultando numa média de 1,51 quadro-chave por tomada. As métricas consideradas para a avaliação são os percentuais médios de quadros redundantes gerados e perdidos por tomada, com relação aos quadros das tomadas da seqüência de referência. Assim, uma tomada com 1 quadro-chave na referência e 2 na abordagem automática, tem redundância de 100%. Por outro lado, uma tomada com 4 quadros na referência representada por 3 quadros na seleção automática, indica uma perda de 25%. A Tabela 1 apresenta os valores de referência utilizados. Como estes valores são os esperados em um processo “ideal” de extração automática realizada por inspeção visual humana, não há, naturalmente, nem perda nem redundância. Tabela 1 – Tabela com valores de referência Limiar
KF/S
Perda
Red.
TotP
TotR
Total
não definido
1,51
0%
0%
0
0
883
Gráfico 1 – Perda x Redundância: Método pixel-a-pixel RGB A Tabela 3 mostra os pontos de intercessão entre as curvas de perda e redundância obtidos para as quatro abordagens básicas e suas respectivas combinações. Os valores dessa tabela foram obtidos seguindo a mesma metodologia anterior. Tabela 3 – Melhor resultado para cada método Método de extração de quadros
Resultado
1 - Pixel-a-pixel RGB
22%
2 - Histograma RGB
29%
3 - Pixel-a-pixel IQ
39%
4 - Histograma IQ
25%
5 - Combinação de 1 e 2
17%
6 - Combinação de 3 e 4
18%
7- Combinação de 1, 2, 3 e 4
12%
O método de comparação pixel-a-pixel no espaço RGB, embora bastante simples, foi o que obteve o melhor desempenho individual. Ele tem como vantagem a robustez aos efeitos de transições de tomada com fading [7], evitando a geração de quadros redundantes. Porém, pequenos movimentos de câmera e/ou objetos podem provocar a geração excessiva de quadros redundantes, sendo este o seu ponto fraco. O método baseado em histogramas RGB tem como vantagem uma boa resistência aos efeitos de dissolução e como maior desvantagem, a grande sensibilidade ao fading, capturando quadros em excesso nessas transições. Cenas com flashes também causam problema, já que correspondem a mudanças bruscas de luminosidade (e, portanto, dos histogramas). Além disso, devido a sua resistência a pequenas movimentações de câmera ou objetos, o método pode perder quadros importantes cuja variação da posição dos objetos na cena é relevante. Semelhante ao que ocorre no espaço RGB, a comparação pixel-apixel nos canais I e Q apresenta grande sensibilidade a movimentos de objetos e câmera, além de agravar o problema de redundância de quadros nos efeitos de dissolução. Com isso, o método apresenta o pior desempenho individual. A comparação dos histogramas I e Q também tem desempenho semelhante à sua versão para o espaço RGB, mas sendo um pouco mais resistente a transições com efeito de fading. Em contrapartida, ele é ainda mais sensível ao efeito de dissolução, capturando quadros em excesso nesses casos. A resistência a movimentos de objetos e câmera também causa uma grande perda de quadros chave como acontece no espaço RGB. A combinação dos métodos de histograma e pixel-a-pixel IQ, apresenta resultados melhores que qualquer um dos seus componentes trabalhando isolados. As desvantagens são herdadas dos seus componentes básicos analisados, onde há uma redundância excessiva se existirem efeitos de dissolução. Como ponto forte, pode-se destacar uma maior robustez em cenas onde há grande variação de luminosidade (flashes), bastante comum nos vídeos jornalísticos. A explicação para o fato é que, no caso dos flashes, há variação basicamente no canal de luminância Y, justamente aquele descartado no método. A combinação das abordagens básicas (1 a 4) resultou no melhor desempenho global dentre todos os métodos avaliados. Não há vulnerabilidade em efeito de transição com fading e dissoluções. Também há uma boa captura de quadros-chave em cenas em branco e preto, o que não acontece nos métodos de histograma e pixel-a-pixel IQ. A vulnerabilidade da combinação desses métodos aparece em cenas com flashes, onde a variação de luz causa mudanças bruscas de histograma e em nível de pixel. A combinação de métodos exige a definição de conjunta dos limiares associados a cada método básico. As definições dos limiares foram baseadas em heurística. Inicialmente, foram estabelecidos pisos para cada limiar, com base nas avaliações individuais de cada método. Em seguida, foi feita uma avaliação do desempenho conjunto com esses valores mínimos de limiar. Após a geração do sumário do vídeo, por inspeção visual, buscouse determinar qual dos métodos estava relacionado à geração excessiva de quadros (uma vez que se trabalhava com limiares muito baixos). O método identificado deveria ter o seu limiar aumentado a fim de minimizar o problema. De maneira similar, os
limiares adequados necessitam de ajuste quando o sumário passa a ter problemas de perda excessiva de quadros. Na verdade, a avaliação dos métodos básicos isoladamente permitiu a definição de um intervalo adequado para o ajuste de cada limiar, reduzindo as possíveis configurações a serem avaliadas.
4. CONCLUSÕES E PERSPECTIVAS A redução do conjunto de quadros é importante para a diminuir o custo computacional na extração de características de conteúdo visual, diminuir o custo de armazenamento e o tamanho da base de dados indexada. Isso torna o sistema de busca por similaridade visual [5] mais eficiente e menos redundante. Entretanto, não é possível evitar uma certa perda de informação, que sendo controlada, como mostrado nesse trabalho, pode ficar dentro de um nível aceitável. Na pesquisa específica, esse nível de perda de quadros-chave é tolerável e atente as necessidades da aplicação de recuperação de conteúdo visual de vídeos digitais. Após a definição dos melhores limiares dos quatro métodos em conjunto, uma base com 46 edições do Jornal Nacional, com cerca de 34 horas de vídeo e 3.420.835 quadros foi processada, permitindo a geração de um conjunto de sumários com 42.755 quadros-chave. Estes sumários, usados tanto para a busca tanto baseada em características visuais, representam uma redução na quantidade total de quadros para cerca de 1,25% do total. Como trabalhos futuros, projeta-se adquirir uma base de vídeos maior e com menos ruído, além de estender a avaliação do desempenho da captura de quadros-chave para outras categorias de vídeos (filmes, vídeos educativos e de vigilância).
5. REFERÊNCIAS [1] Seinstra, F. J. et alli. High-Performance Distributed Video Content Analysis with Parallel-Horus. IEEE Multimedia, Oct.-Dec. 2007 Vol. 14, N.4, pp. 64-75. [2] Hanjalic, A.; Zhang, H. An integrated scheme for automated video abstraction based on unsupervised cluster-validity analysis. IEEE Trans. Circuits Systems Video Technol. Vol.9, N.8, 1999. pp. 1280–1289. [3] Pfeiffer, S. et alli. Abstracting Digital Movies Automatically. Journal of Visual Communication and Image Representation, Vol. 7, N.4, 1996. pp. 345–353. [4] Truong, B. T. Search of Structural and Expressive Elements in Film Based on Visual Grammar. Phd Thesis, Dep. Comp. Science, Curtin University of Technology, 2004. [5] Pimentel C. A. Um ambiente para indexação e recuperação de conteúdo de vídeo baseado em características visuais. Dissertação de Mestrado: Universidade Salvador, 2008. [6] Jacobs, C.E.; Finkelstein, A.; Salesin, D.H. Fast multiresolution image querying. Proc. SIGGRAPH, Aug 1995. pp. 277-286. [7] Santos, T. T. Segmentação automática de tomadas em vídeo. Dissertação de Mestrado, USP, 2004. [8] Gonzalez, C. R.; Woods, E. R. Processamento de imagens digitais. São Paulo, SP: Edigard Blücher, 2000. [9] Drew, M.; Au, J. Video Keyframe Production by Efficient Clustering of Compressed Chromaticity Signatures. In Proc. of the ACM Multimedia, USA, Oct. 2000. pp 365–367.
