Desenvolvimento de Algoritmo
para "Tracking" de Veículos
Trabalho de conclusão de curso apresentado à Escola Politécnica da Universidade de São Paulo
Departamento de Engenharia de Sistemas Eletrônicos
Autor:
Orientador:
Gabriel Ramires de Britto
Prof. Livre-Docente Hae Yong Kim
Ano: 2011

Sumário

1 - Introdução
    1.1 - Resumo
    1.2 - Objetivos
2 - Metodologia
    2.1 - Recursos Utilizados
    2.2 - Diagrama de Blocos
    2.3 - Descrição do Algoritmo
3 - Etapas do Algoritmo
    3.1 - Obtenção da Imagem de Fundo
    3.2 - Subtração de Fundo
    3.3 - "Warp"
    3.4 - "Template Matching"
    3.5 - Fluxo Óptico
    3.6 - Lista Ligada e "Tracking"
4 - Resultados do Algoritmo
    4.1 - Vídeo de Entrada
    4.2 - Imagem de Fundo
    4.3 - Vídeo Intermediário: "Warp"
    4.4 - Vídeo Intermediário: Subtração de Fundo + "Warp"
    4.5 - Vídeo Intermediário: "Template Matching"
    4.6 - Vídeo de Saída
5 - Conclusões
6 - Códigos Fonte
7 - Informações para Contato


1 - Introdução

1.1 - Resumo

Este trabalho consiste em desenvolver um algoritmo para realizar “tracking” de veículos. A palavra “tracking” é um jargão em processamento de imagens que designa o ato de identificar a trajetória de um objeto numa seqüência de imagens. Dado um arquivo de vídeo que mostra um fluxo de veículos, este trabalho pretende identificar a trajetória de cada veículo, simultaneamente, gerando um relatório no final do processo com informações sobre cada trajetória. Entre essas informações estão posição e velocidade de cada veículo quadro a quadro do vídeo. Uma das possíveis aplicações que podem surgir a partir deste tipo de algoritmo é a monitoração do tráfego de veículos por “software”. Outra possível aplicação é a detecção de infrações de trânsito automaticamente.


1.2 - Objetivos

O objetivo deste projeto é, dado um arquivo de vídeo que contenha um fluxo de veículos, gerar um relatório na forma de um arquivo de texto que descreva, quadro a quadro, a trajetória de cada veículo. Neste relatório devem constar a posição e velocidade de cada veículo em cada quadro do vídeo. A figura abaixo representa o relatório descrito.


2 - Metodologia

O sistema proposto neste projeto recebe como entrada um vídeo contendo um fluxo de veículos. Esse vídeo é processado e cada veículo tem sua trajetória acompanhada pelo sistema. A saída do sistema é um relatório contendo informações relevantes sobre a trajetória de cada veículo identificado.

Os vídeos utilizados devem possuir algumas características para que o algoritmo funcione:

(a) O campo de visão deve ser abrangente, possibilitando a visualização dos veículos por um percurso relativamente longo;
(b) O ângulo de visão deve ser de tal forma que, para um tráfego intenso, não deve haver sobreposição total entre os veículos;
(c) Se possível, o vídeo não deve conter obstáculos entre o ângulo de visão e os veículos, dificultando a identificação dos mesmos pelo “software”.

A figura abaixo, obtida a partir de um vídeo fornecido pelo professor Hae Yong Kim, orientador deste projeto, representa um quadro de um vídeo que atende às condições descritas anteriormente.


2.1 - Recursos Utilizados

Este projeto utiliza a linguagem de programação C++. As técnicas de processamento de imagens são aplicadas com o auxílio das bibliotecas OpenCV e Proeikon, sendo a última desenvolvida pelo professor Hae Yong Kim, orientador deste projeto. Os vídeos utilizados para realização dos testes foram fornecidos pelo professor Hae Yong Kim.


2.2 - Diagrama de Blocos

2.3 - Descrição do Algoritmo

Nos próximos parágrafos está uma breve descrição do funcionamento do algoritmo do Diagrama de Blocos.

A primeira etapa no desenvolvimento do algoritmo é a Obtenção da Imagem de Fundo a partir de um trecho do vídeo analisado. Com a imagem de fundo gerada, o programa principal, delimitado pela linha tracejada do Diagrama de Blocos, pode iniciar.

A etapa de Subtração de Fundo permite obter uma imagem que contém apenas os veículos, sem os elementos estáticos da cena. Esta imagem é então submetida ao processo “Warp”, para remover distorções de perspectiva na imagem, deixando-a mais adequada para passar pelo processo de “Template Matching”.

O processo de “Template Matching” encontra as posições em que os “templates” disponíveis melhor se sobrepõem à imagem. Ao término deste processo, as posições dos veículos presentes no quadro são conhecidas. O quadro original é também submetido ao processo de “Warp”. A imagem resultante é analisada a procura de “cantos”. Os “cantos” encontrados no quadro atual são equivalentes a cantos do quadro anterior do vídeo, o que permite estimar a velocidade de cada "canto".

Combinando o resultado do “Template Matching” com as velocidades dos “cantos” encontrados, é possível estimar a velocidade e a próxima posição de cada veículo. Esses valores são guardados para serem consultados no próximo quadro. O programa deve decidir se cada veículo encontrado no quadro atual já estava em quadros anteriores do vídeo. Isso é feito comparando-se a posição atual do veículo encontrado com todas as próximas posições calculadas no quadro anterior para todos os veículos. Caso não haja um veículo cuja próxima posição, calculada anteriormente, seja próxima da posição atual, o veículo encontrado no quadro atual é um novo veículo.

As informações sobre cada veículo e suas respectivas trajetórias são armazenadas numa lista ligada, que é preenchida no decorrer do processamento. Quando não há mais quadros para processar, a lista ligada é percorrida e as informações contidas nela são registradas num arquivo de texto.

Este é apenas um breve resumo do funcionamento do algoritmo. Detalhes sobre cada etapa são apresentados nos respectivos "links".


3 - Etapas do Algoritmo

As etapas principais do algoritmo, mostradas no Diagrama de Blocos, estão descritas nas páginas indicadas nos "links" abaixo.


3.1 - Obtenção da Imagem de Fundo

A obtenção da imagem de fundo é o processo que analisa um trecho especificado do vídeo e gera uma imagem que contém apenas os elementos estáticos da cena, sem os veículos. O processo está descrito nesta página.


3.2 - Subtração de Fundo

Tendo a imagem de fundo adequada, é possível realizar a etapa conhecida como Subtração de Fundo, que consiste em remover dos quadros do vídeo as regiões que não são de interesse. Neste projeto, as regiões de interesse são os veículos em movimento. O processo está descrito nesta página.


3.3 - "Warp"

Devido ao ângulo de captura da câmera, o vídeo obtido apresenta distorções de perspectiva, que devem ser corrigidas antes de se analisar as trajetórias dos veículos. O processo está descrito nesta página.


3.4 - "Template Matching"

Para localizar cada veículo em cada quadro do vídeo, é preciso conhecer o formato aproximado desses veículos. Para cada tipo característico de veículo (motocicleta, carro, van, ...) é associada uma imagem ("template") previamente selecionada que aproxima o seu formato. Com essas imagens em mãos, é possível determinar as posições dos veículos do quadro. O processo está descrito nesta página.


3.5 - Fluxo Óptico

Para acompanhar a trajetória de um veículo é preciso encontrar sua posição no quadro anterior baseando-se em sua posição no quadro atual. Mas antes de se fazer isso para um veículo, é preciso fazer para um único píxel. A técnica que permite isso é conhecida como Fluxo Óptico, e está descrita nesta página.


3.6 - Lista Ligada e "Tracking"

Sabendo as posições e dos veículos em cada quadro do vídeo (resultado do processo de "Template Matching"), é possível associar as posições no quadro atual com as posições no quadro anterior, determinando assim as trajetórias quadro a quadro de cada veículo. O processo está descrito nesta página.


4 - Resultados do Algoritmo

A seguir estão os resultados obtidos para um vídeo fornecido pelo professor Hae Yong Kim, orientador deste projeto.


4.1 - Vídeo de Entrada

Este é o vídeo de entrada utilizado. A resolução do vídeo original é 720 x 480.


4.2 - Imagem de Fundo

Estas são as imagens de fundo obtidas para alguns trechos do vídeo de entrada.

Imagem de Fundo para os quadros de 0 a 999 Imagem de Fundo para os quadros de 4000 a 4999 Imagem de Fundo para os quadros de 10000 a 10999

A imagem de fundo obtida entre os quadros 10000 e 11000 é a que melhor aproxima o fundo dos quadros do vídeo. Essa foi a imagem utilizada para a Subtração de Fundo.


4.3 - Vídeo Intermediário: "Warp"

Este é o resultado do processo de "Warp" aplicado sobre o vídeo de entrada.


4.4 - Vídeo Intermediário: Subtração de Fundo + "Warp"

Este é o resultado do processo de "Warp" aplicado sobre a Subtração de Fundo.


4.5 - Vídeo Intermediário: "Template Matching"

Estas imagens foram utilizadas como "templates" para o processo de "Template Matching".


Este é o resultado do processo de "Template Matching" aplicado sobre a Subtração de Fundo.


4.6 - Vídeo de Saída

Este é o resultado final do algoritmo.


5 - Conclusões

Os resultados obtidos demonstram as principais limitações do algoritmo desenvolvido:

(1) - Necessidade de um pré-processamento para se obter uma "Imagem de Fundo".

(2) - Dificuldade de individualizar os veículos quando o tráfego é muito intenso, pois se a distância entre os veículos é muito pequena o processo de "Template Matching" falha.

(3) - Veículos muito grandes, como caminhões, que ocupam boa parte da tela, são interpretados pelo algoritmo como vários veículos menores.

(4) - O processamento demandado pelo algoritmo é muito elevado para que se considere aplicações em tempo real.

Apesar das limitações, o algoritmo funciona bem para os trechos do vídeo com tráfego menos intenso. Mesmo não sendo suficiente para criar uma aplicação totalmente funcional, este projeto serve como ponto de partida para futuros projetos em processamento de vídeo e controle de tráfego.


6 - Códigos Fonte

Os códigos fonte, o vídeo e os arquivos de texto necessários para reproduzir os resultados deste projeto podem ser obtidos no "link" abaixo.

tracking_de_veiculos.zip


7 - Informações para Contato

Para entrar em contato com o autor deste projeto, envie um e-mail para:  gabriel.ramires@yahoo.com