Analysis and coding of visual objects: new concepts and new tools

Abstract

Video coding has been under intense scrutiny during the last years. The published international standards rely on low-level vision concepts, thus being first-generation. Recently standardization started in second-generation video coding, supported on mid-level vision concepts such as objects.

This thesis presents new architectures for second-generation video codecs and some of the required analysis and coding tools.

The graph theoretic foundations of image analysis are presented and algorithms for generalized shortest spanning tree problems are proposed. In this light, it is shown that basic versions of several region-oriented segmentation algorithms address the same problem. Globalization of information is studied and shown to confer different properties to these algorithms, and to transform region merging in recursive shortest spanning tree segmentation (RSST). RSST algorithms attempting to minimize global approximation error and using affine region models are shown to be very effective. A knowledge-based segmentation algorithm for mobile videotelephony is proposed.

A new camera movement estimation algorithm is developed which is effective for image stabilization and scene cut detection. A camera movement compensation technique for first-generation codecs is also proposed.

A systematization of partition types and representations is performed with which partition coding tools are overviewed. A fast approximate closed cubic spline algorithm is developed with applications in partition coding.

A codificação de vídeo tem sido intensamente estudada nos últimos anos. As normas internacionais já publicadas baseiam-se em conceitos da visão de baixo nível, sendo portanto de primeira geração. Começou recentemente a normalização de técnicas de codificação de segunda geração, suportada em conceitos da visão de médio nível tais como objectos.

Esta tese apresenta novas arquitecturas para codificadores de vídeo de segunda geração e algumas das correspondentes ferramentas de análise e codificação.

Apresentam-se fundamentos de teoria dos grafos aplicada à análise de imagem e propõem-se algoritmos para generalizações do problema da árvore abrangente mínima. Mostra-se que versões básicas de vários algoritmos de segmentação orientados para a região resolvem o mesmo problema. Estuda-se a globalização de informação e mostra-se que confere propriedades diferentes a esses algoritmos, transformando o algoritmo de fusão de regiões no algoritmo de árvores abrangentes mínimas recursivas (RSST). Mostra-se a eficácia de algoritmos RSST que tentam minimizar o erro global de aproximação e que usam modelos de região afins. Propõe-se um algoritmo baseado em conhecimento prévio para segmentação em vídeo-telefonia móvel.

Desenvolve-se um algoritmo de estimação de movimentos de câmara eficaz na estabilização de imagem e na detecção de mudanças de cena. Propõe-se também uma técnica de compensação de movimentos de câmara para codificadores de primeira-geração.

Sistematizam-se os tipos e as representações de regiões, revendo-se depois técnicas de codificação de partições. Desenvolve-se um algoritmo rápido e aproximado para cálculo de splines cúbicas fechadas.