Algoritmo para Rastreamento
Óptico baseado em Padrões com
Características Projetivas
Invariantes
Manuel Loaiza
Marcelo Gattass
Alberto Raposo
Sumario



Introdução.
Motivação.
Descrição do algoritmo.








Características Projetivas Invariantes.
Quad Tree.
Técnicas Auxiliares.
Etapas do algoritmo.
O algoritmo.
Exemplo da aplicação.
Vantagens e desvantagens do algoritmo.
Conclusões e trabalhos futuros.
Introdução




Sistemas de rastreamento óptico tem como
objetivo identificar e rastrear objetos específicos
contidos numa imagem.
Os objetos de rastreamento podem ser
marcadores individuais ou grupais (padrões).
No caso de padrões grupais é preciso identificar
os marcadores que pertencem a um
determinado padrão.
A identificação dos padrões deve ser rápida e
individual.
Motivação



Como podemos criar e
definir padrões?.
Como agrupar os
marcadores individuais
que pertencem a um
determinado padrão?.
Como podemos criar um
identificador único para
padrões com um mesmo
formato?.
Motivação

Como resposta a estas perguntas é que
surgiu a proposta do nosso algoritmo
que basicamente:


Utilizará características projetivas
invariantes para definir e identificar
padrões para o sistema de rastreamento.
Utilizará uma QuadTree para definir uma
relação de vizinhança entre marcadores
individuais que possam ser parte de um
determinado padrão.
Descrição do Algoritmo


Nosso algoritmo se baseia na utilização das
seguintes técnicas:
 Características Projetivas Invariantes.
 Quad Tree.
 Métodos Auxiliares (Area envolvente,
predição).
Ele se divide em duas etapas:
 Treinamento.
 Execução.
Características Projetivas Invariantes


As características projetivas invariantes são
características que continuam constantes
quando fazemos uma projeção 3D para 2D.
Exemplos destas características projetivas
invariantes são:



Colinearidade.
Cross ratio.
Coplanaridade.
Características Projetivas Invariantes



Já (Meer et al, 1998) exploraram estas
características invariantes para comparação de
pontos característicos em fotos áreas.
Definiram a teoria dos “P2 – Invariant”, que se
estendia para formatos coplanarares.
Já (Suk et al 2000) expandiu as propriedades
de invariância a projeção para ser também
invariância a permutação na ordem dos pontos
que conformam o padrão.
Características Projetivas Invariantes

No caso dos padrões coplanares (Suk et al
2000) enuncia uma restrição, para padrões com
“n” pontos coplanares, com n >=5, pelo
menos (n-1) pontos devem ser bem
identificados durante o rastreamento do padrão.
Características Projetivas Invariantes

Invariantes a projeção e permutação?
A
B
C
D
Cross ratio (A,B,C,D)
E
A
D
| AC | / | BC |
| AD | / | BD |
B C
A B
C
C
D
B
A D
(Meer et al, 1998) definiram
com o “P2 -Invariant” e (Suk
et al 2000) expandiu para
ser invariante a projeção e
permutação.
Quad tree


A geração do Quad Tree é feita sobre as posições 2D dos
marcadores reconhecidos na imagem.
Se espera que marcadores que pertencem a um mesmo
padrão fiquem em quadrantes vizinhos.
Quad tree


Cada vez que percorremos a arvore podemos
verificar se o ramo (quadrante) tem pelo menos n =
4 (ou 5) folhas (marcadores).
Caso tenham n > 4 ou 5 folhas, as combinações C 4n
ou C 5n .
Técnicas Auxiliares


Algumas técnicas auxiliares que
foram testados são:
 Teste de colinearidade e
convex hull para descaratr
padrões que não
correspondem ao formato.
 Definição de uma área
envolvente a cada padrão.
O motivo da aplicação destas
técnicas e encontrar falsos
padrões que podem ate ser
considerados bons.
Etapas do Algoritmo

Treinamento:



Nesta etapa são definidos nossos futuros
padrões de marcadores, e capturando algumas
amostra dos mesmos é definido um identificador
único para cada padrão.
Padrões com o mesmo formato ganham
identificadores totalmente diferentes.
Tal como foi definido a característica projetiva
invariante é também invariante a permutações
na ordem dos marcadores que a compõem.
Etapas do Algoritmo

Execusão:


Nesta etapa é onde se realiza o rastreamento
em tempo real dos padrões previamente
treinados.
Algumas incosistencias podem se apresentar no
teste como falsos padrões, mas as tecnicas
auxilares propostas tentam funcionar como
filtros para os falsos padrões.
O Algoritmo

Fluxo dos processos:




Processar imagem e obter posição 2D de
nossos marcadores.
Gerar a quad tree cada frame analisado.
Inicialmente percorrer a quad tree procurando
padrões colineares.
Para cada padrão colinear calcular o valor de
sua característica projetiva invariante e
comparar com os padrões previamente
treinados.
O Algoritmo

Fluxo dos processos:




Caso ter uma comparação valida extrair esses
marcadores (folhas) da quadtree.
Percorrer a quadtree procurando padrões
coplanares.
Para cada padrão coplanar calcular o valor de
sua característica projetiva invariante e
comparar com os padrões previamente
treinados.
Caso ter uma comparação valida extrair esses
marcadores (folhas) da quadtree.
Exemplo da Aplicação

Na imagem temos 2 padrões do tipo colinear e
2 tipo coplanar.
Table 1. Projective invariant values for each pattern.
Exemplos da Aplicação

Valores dos identificadores são intervalos.
Pattern
Type Minimum
Value
Maximum
Value
1st-Pattern
I
[ 2.048 ]
[ 2.085 ]
2nd-Patern
I
[ 2.368 ]
[ 2.460 ]
3rd-Pattern
II
[ 0.06 , 0.06 ] [ 0.14 , 0.13 ]
4th-Pattern
II
[ 0.16 , 0.16 ] [ 0.23 , 0.24 ]
Table 1. Projective invariant values for each pattern.
Exemplos da Aplicação

Padrões Colineares.
Quadrant
Left – Up
Left – Down
Right – Up
Right – Down
Nº Markers
4
5
0
9
Nº Candidates for Pattern I
C 44 = 1
C 45 = 5
0
(C 46 =) 15 + (C 49 =) 126 = 141
Total:
18
147
Quadrant
Candidates
Pattern I
Collinearity
Test
Projective Pattern ID
Inv. Match
Unmatched
Markers
Left – Up
1
1
1
1st-Pattern
0
Left – Down
5
0
0
0
5
Right – Up
0
0
0
0
0
Right – Down
141
0+1=1
1
2nd-Patern
5
Total:
147
2
2
2 (recognized)
10
Table 1. Projective invariant values for each pattern.
Exemplos da Aplicação

Padrões Coplanares.
Quadrant
Nº Markers Nº Candidates
for Pattern II
Left – Up
0
0
Left – Down 5
C 55 = 1
Right – Up
0
0
Right – Down 5
C 55 = 1
Total:
10
2
Quadrant
Candidates
Pattern II
Convex Test Projective
Inv. Match
Pattern ID
Unmatched
Markers
Left – Up
0
0
0
4th-Pattern
0
Left – Down
1
1
1
0
0
Right – Up
0
0
0
0
0
Right – Down
1
1
1
3rd-Pattern
0
Total:
2
2
2
2 (recognized)
0
Vantagens e desvantagens do algoritmo.



Vantagens
 É flexível a ruído.
 Faz o reconhecimento dos padrões só com
informação 2D.
Desvantagens

Sensível a oclusão.

Muita liberdade na geração de candidatos por
combinação dos marcadores pode criar falsos
padrões bons.
Comentário

Extensão para padrões não coplanares ?.
Conclusões e Trabalhos Futuros




O algoritmo foi proposto como uma ferramenta de
apoio no processo de definição e reconhecimento de
padrões.
Ele procura ser uma ferramenta que consiga identificar
os padrões só com informação 2D.
Ele poder ser uma ferramenta de apoio a
correspondência feita com a geometria epipolar.
Como trabalhos futuros é testar nosso algoritmo em
ambientes “markerless” onde pontos característicos da
cena como cantos, arestas naturalmente algumas vezes
pode ter um tipo de agrupação colinear ou coplanar.
Referencias






Meer, P., Lenz, R., Ramakrishna, S.: Correspondence of Coplanar
Features Through p2 Invariant Representations. In: Applications of
Invariance in Computer Vision, pp. 473– 492. Springer, Heidelberg
(1993).
Meer, P., Lenz, R., Ramakrishna, S.: Efficient Invariant
Representations. International Journal of Computer Vision 26, 137–152
(1998).
Santos, P., Stork, A., Buaes, A., Jorge, J.: PTrack: Introducing a Novel
Iterative Geometric Pose Estimation for a Marker-based Single Camera
Tracking System. In: Proceedings of IEEE Virtual Reality, pp. 143–150.
IEEE Press, California, USA (2006).
Suk, T., Flusser, J.: Point-based projective invariants. Pattern.
Recognition (33), 251–261 (2000).
Tsonis, V.S., Chandrinos, K.V., Trahanias, P.E.: Landmark-based
navigation using projective invariants. In: Proc. of International
Conference Intelligent Robots and Systems, pp. 342–347 (1998).
Van Liere, R., Mulder, J.D.: Optical Tracking Using Projective Invariant
Marker Pattern Properties. In: Proc. of IEEE Virtual Reality, pp. 191–
198. IEEE Press, Los Angeles (2003).