UNISEB COC - CENTRO UNIVERSITÁRIO TRABALHO DE CONCLUSÃO DE CURSO BACHARELADO ENGENHARIA DE COMPUTAÇÃO SISTEMA DE RECONHECIMENTO DE PLACAS DE VEÍCULOS Rômulo Estevan Fernandes Orientador: Prof. Me. Paulo César de Carvalho Dias RIBEIRÃO PRETO – SP 2011 RÔMULO ESTEVAN FERNANDES SISTEMA DE RECONHECIMENTO DE PLACAS DE VEÍCULOS Trabalho de conclusão de curso apresentado ao UNISEB COC – Centro Universitário de Ribeirão Preto, como parte dos requisitos para obtenção do grau de Bacharel em Engenharia de Computação. Prof. Me. Paulo César de Carvalho Dias Orientador Prof. Dr. Lúcio André de Castro Jorge Membro da banca examinadora Prof. Dr. Roberto Rodrigues Pereira Júnior Membro da banca examinadora RIBEIRÃO PRETO – SP 2011 xvii xvii TRABALHO DE CONCLUSÃO DE CURSO Aluno: Rômulo Estevan Fernandes Código: 6055514 Curso: Engenharia de Computação Semestre/Ano: 10º/2011 Tema: Sistema de Reconhecimento de Placas de Veículos Objetivo Pretendido: Desenvolver um sistema capaz de localizar em uma foto a placa de um automóvel, identificar e depois reconhecer os caracteres dessa placa, mostrando na tela o resultado final para o usuário. _____/_____/________ __________________________________ Prof. Me. Paulo César de Carvalho Dias Professor Orientador _____/_____/________ __________________________________ Rômulo Estevan Fernandes Aluno _____/_____/________ __________________________________ Prof. Me. Paulo César de Carvalho Dias Coordenador do Curso _____/_____/________ __________________________________ Prof. Me. Reginaldo Arthus Vice-Reitor xvii FORMULÁRIO DE AVALIAÇÃO DO TCC Tema do Trabalho: Sistema de Reconhecimento de Placas de Veículos Data da apresentação: _____/_____/________ Horário: ____________ Local: _________________________________ Banca Examinadora 1) Professor Orientador: _________________________________________________ 2) Professor Examinador 1: ______________________________________________ 3) Professor Examinador 2: ______________________________________________ xvii Folha de Pontuação Fatores de Avaliação Pontuação (0.0 a 2.0) 1. Atualidade e relevância do tema proposto. 2. Linguagem técnica utilizada em relação ao tema e aos objetivos, e competência linguística. 3. Aspectos metodológicos e formais da editoração do trabalho escrito - sequencia lógica e coerência interna. 4. Aspectos metodológicos e formais da editoração do trabalho escrito - sequencia lógica e coerência interna. 5. Revisão Bibliográfica realizada em relação ao tema pesquisado. 6. Apresentação oral – segurança e coerência em relação ao trabalho escrito. Média:____________ (___________________________________________________) Assinaturas dos membros da Comissão Julgadora: 1) _____/_____/________ _______________________________________________ 2) _____/_____/________ _______________________________________________ 3) _____/_____/________ _______________________________________________ xvii Dedicatória Dedico este trabalho ao meu orientador, aos professores que lecionam no curso de Engenharia de Computação, aos meus pais, minha avó materna e paterna, aos meus primos, ao meu tio e minha tia, a todos meus amigos de infância e também aos amigos que tenho hoje. xvii AGRADECIMENTOS Em primeiro lugar agradeço a Deus por me ajudar a superar todos os desafios que encontrei durante a execução desse trabalho. A todos os colegas que estavam comigo durante esses longos anos de estudo, onde aprendemos juntos, independentemente do defeito de cada um. Aos meus pais que ajudaram, tiveram paciência, e me compreenderam nos momentos difíceis que passei durante esses cinco anos de graduação. Ao UNISEB COC – Centro Universitário, a todos os funcionários e professores que seja de forma indireta ou direta contribuíram para meu desenvolvimento na vida acadêmica. Agradeço principalmente aos professores que lecionam no curso de Engenharia de Computação que ensinaram as disciplinas mais complicadas da minha vida, com tranquilidade e paciência. Ao meu orientador Prof. Me. Paulo César de Carvalho Dias pela disposição em contribuir com esse trabalho. xvii RESUMO Este trabalho envolve basicamente três áreas da computação: visão computacional, inteligência artificial e processamento digital de imagens. A visão computacional envolve a aquisição de imagens e técnicas processamento digital de imagens. A inteligência artificial se propõe basicamente em resolver problemas “imitando” a capacidade humana. O processamento digital de imagens é toda e qualquer forma de processamento dos dados onde são envolvidas imagens e também partes de um vídeo. A rede neural é utilizada através de um modelo matemático, baseado nos neurônios humanos. Há vários modelos de redes neurais, como por exemplo, Perceptron e Multilayer Perceptron. O objetivo deste trabalho é automatizar o processo de reconhecimento de placas que a partir de uma imagem frontal ou traseira seja capaz de localizar, segmentar e reconhecer caracteres. As imagens originais passam por vários estágios: aquisição, pré-processamento, segmentação e reconhecimento dos caracteres. O protótipo para reconhecer caracteres foi desenvolvido na ferramenta MATLAB. Antes de realizar a localização da placa, as imagens podem passar por um pré-processamento para ficar em condições ideais. Na etapa de localização da placa foi utilizada detecção de bordas, projeção vertical e horizontal. Depois de localizar a placa a mesma é segmentada. Os caracteres podem ser reconhecidos em vários tipos de imagens e também em textos. Para reconhecer os caracteres é utilizada correlação que compara a imagem de cada caractere encontrado pelo protótipo com cada caractere do conjunto de letras e números, o caractere com maior correlação será o eleito. O algoritmo de localização apresentou 66% de eficiência. O algoritmo de reconhecimento acertou 36% dos caracteres da placa. Os resultados obtidos com o trabalho podem ser considerados satisfatórios para uma primeira abordagem ao problema, mas ainda não pode ser utilizado como produto final. Palavras-chave: Visão Computacional, Inteligência Artificial, Rede Neural, Processamento Digital de Imagens, Detecção de Bordas, Algoritmo de Localização, Algoritmo de Reconhecimento dos caracteres. xvii ABSTRACT This work basically involves three areas of the computation: computational vision, artificial intelligence and digital processing of images. The computational vision involves the acquisition of images and techniques digital processing of images. Artificial intelligence if considers basically in deciding problems “imitating” the capacity human being. The digital processing of images is all and any form of processing of the data where they are involved images and also parts of a video. The neural net is used through a mathematical model, based in the human neurons. It has some models of neural nets, as for example, Perceptron and Multi-layer Perceptron. The objective of this work is to automatize the process of recognition of plates that from an image frontal or back is capable to locate, to segment and to recognize characters. The original images pass for some periods of training: acquisition, daily pay-processing, segmentation and recognition of the characters. The archetype to recognize characters was developed in tool MATLAB. Before carrying through the localization of the plate, the images can pass for a daily payprocessing to be in ideal conditions. In the stage of localization of the plate detention of edges was used, vertical and horizontal projection. After locating the plate the same one is segmented. The characters also can be recognized in some types of images and in texts. To recognize the characters correlation is used that compares the image of each character found for the archetype with each character of the set of letters and numbers, the character with bigger correlation will be the elect one. The localization algorithm presented 66% of efficiency. The recognition algorithm made right 36% of the characters of the plate. The results gotten with the work can be considered satisfactory for a first boarding to the problem, but not yet it can be used as end item. Keywords: Computer Vision, Artificial Intelligence, Neural Network, Digital Image Processing, Edge Detection, Algorithm of Localization, Algorithm of Recognition of the characters. xvii SUMÁRIO Introdução ......................................................................................................................... 1 1. Visão Computacional .................................................................................................... 5 1.2. Aquisição e tipos de Imagens ............................................................................. 7 1.2.1. Aquisição de imagens ................................................................................. 7 1.2.2. Imagens em tons de cinza ........................................................................... 8 1.2.3. Imagens Binárias ......................................................................................... 9 1.2.4. Imagens RGB ............................................................................................ 10 1.3. Técnicas de segmentação ................................................................................. 11 1.3.1. Filtros detectores de borda ........................................................................ 15 1.3.2. Técnicas de segmentação aplicadas à detecção de placas......................... 22 1.3.3. Transformada de Hough............................................................................ 23 2. Inteligência Artificial .................................................................................................. 25 2.1. Neurônios ......................................................................................................... 26 2.2. Redes Neurais Artificiais e tipos de redes ........................................................ 28 2.1.1. Redes Neurais Artificiais .......................................................................... 28 2.1.2. Tipos de Redes .......................................................................................... 29 2.3. Aprendizado ..................................................................................................... 32 2.3.1. Aprendizado Supervisionado e Não Supervisionado ................................ 32 3. Materiais e Métodos.................................................................................................... 35 3.1. Localização .......................................................................................................... 35 3.2. Segmentação ........................................................................................................ 37 3.3. Caracteres ............................................................................................................. 39 3.3.1. Reconhecimento ........................................................................................ 39 3.4. Protótipo ............................................................................................................... 41 3.4.1. Apresentação ............................................................................................. 41 3.4.2. Funcionamento .......................................................................................... 42 4. Resultados e Discussões ............................................................................................. 45 5. Conclusão.................................................................................................................... 48 5.1. Considerações Finais ............................................................................................ 48 5.2. Trabalhos Futuros................................................................................................. 49 Referências Bibliográficas .............................................................................................. 50 xvii APÊNDICE A – COMPARAÇÃO ENTRE PLACAS ORIGINAIS E PLACAS RECONHECIDAS PELO PROTÓTIPO........................................................................ 53 xvii LISTA DE ABREVIATURAS E SIGLAS IPVA: Imposto sobre a Propriedade de Veículos Automotores CNH: Carteira Nacional de Habilitação PDI: Processamento Digital de Imagem MATLAB: Matrix Laboratory RGB: Sistema de cores formado por Vermelho (Red), Verde (Green) e Azul (Blue) CCD: Charge Coupled Device CMOS: Complementary Metal Oxide Semiconductor IA: Inteligência Artificial RNAs: Redes Neurais Artificiais MLP: Multi-Layer Perceptron OCR: Optical Character Recognition xvii LISTA DE SÍMBOLOS mm: milímetros nm: nanômetro Gx: borda horizontal Gy: borda vertical GR: operador de Roberts GP: operador de Prewitt GS: operador de Sobel xvii LISTA DE QUADROS Quadro 1: Máscara para detectar pontos na imagem ...................................................... 11 Quadro 2: Máscara para detectar linhas horizontais na imagem .................................... 12 Quadro 3: Máscara para detectar linhas oblíquas 45º positivo na imagem .................... 13 Quadro 4: Máscara para detectar linhas oblíquas 45º negativo na imagem ................... 14 Quadro 5: Máscara para detectar linhas verticais na imagem ........................................ 14 Quadro 6: Máscara horizontal do filtro de Roberts (esquerda). Máscara vertical do filtro de Roberts (direita) ......................................................................................................... 16 Quadro 7: Máscara horizontal do filtro de Prewitt (esquerda). Máscara vertical do filtro de Prewitt (direta) ........................................................................................................... 17 Quadro 8: Máscara horizontal do filtro de Sobel (esquerda). Máscara vertical do filtro Sobel (direita) .................................................................................................................. 18 Quadro 9: Máscaras do filtro Passa-Baixa ...................................................................... 20 Quadro 10: Máscaras do filtro Passa-Alta ...................................................................... 21 Quadro 11: Matriz de confusão. ..................................................................................... 45 xvii LISTA DE FIGURAS Figura 1: Placa de Veículo (CONTRAN, 2007). .............................................................. 2 Figura 1.1: Etapas necessárias para o processamento de imagens digitais (BASTOS, 2010) ................................................................................................................................. 6 Figura 1.2: Imagem em tons de cinza. .............................................................................. 8 Figura 1.3: Histograma da imagem em tons de cinza. ...................................................... 9 Figura 1.4: Imagem binária com limiar 0,525. ................................................................. 9 Figura 1.5: Imagem com a componente R (a). Imagem com a componente G (b). Imagem com a componente B (c). Imagem em RGB (d) ............................................... 10 Figura 1.6: Detecção de pontos na imagem. ................................................................... 12 Figura 1.7: Detecção das linhas horizontais. .................................................................. 13 Figura 1.8: Detecção de linhas oblíquas 45º positivo. .................................................... 13 Figura 1.9: Detecção de linhas oblíquas 45º negativo. ................................................... 14 Figura 1.10: Detecção de linhas verticais. ...................................................................... 15 Figura 1.11: Filtro de Canny. .......................................................................................... 16 Figura 1.12: Filtro de Roberts: Detecção de bordas horizontais (a). Detecção de bordas verticais (b) ..................................................................................................................... 16 Figura 1.13: Filtro de Roberts. ........................................................................................ 17 Figura 1.14: Filtro de Prewitt: Detecção de bordas horizontais (a). Detecção de verticais (b) .................................................................................................................................... 17 Figura 1.15: Filtro de Prewitt. ........................................................................................ 18 Figura 1.16: Filtro de Sobel: Detecção de bordas horizontais (a). Detecção de bordas verticais (b) ..................................................................................................................... 19 Figura 1.17: Filtro de Sobel. ........................................................................................... 19 Figura 1.18: Filtro Passa-Baixa com máscara 3x3 (a). Passa-Baixa com máscara 5x5 (b) ........................................................................................................................................ 20 Figura 1.19: Filtro Passa-Alta com máscara 3x3 (a). Filtro Passa-Alta com máscara 5x5 (b) .................................................................................................................................... 22 Figura 2.1: Etapas para criação de um sistema de inteligência artificial. ....................... 25 xvii Figura 2.2: Neurônio Biológico (BRAGA; LUDERMIR; CARVALHO, 2000) ........... 26 Figura 2.3: Neurônio Artificial (SABBATINI, 1995) .................................................... 28 Figura 2.4: Arquitetura de uma Rede Neural (KUNZLE, 2010) .................................... 29 Figura 2.5: Problema Linearmente Separável (a). Problema Não Linearmente Separável (b) .................................................................................................................................... 30 Figura 2.6: Rede Neural Perceptron. .............................................................................. 31 Figura 2.7: Rede Neural Multi-Layer Perceptron (BRAGA; LUDERMIR; CARVALHO, 2000) ....................................................................................................... 31 Figura 2.8: Aprendizado supervisionado (BRAGA; LUDERMIR; CARVALHO, 2000) ........................................................................................................................................ 33 Figura 2.9: Aprendizado não supervisionado (BRAGA; LUDERMIR; CARVALHO, 2000) ............................................................................................................................... 34 Figura 3.1: Imagem Original do Veículo. ....................................................................... 35 Figura 3.2: Gráfico da projeção vertical. ........................................................................ 36 Figura 3.3: Projeção vertical. .......................................................................................... 36 Figura 3.4: Gráfico da projeção horizontal. .................................................................... 36 Figura 3.5: Projeção horizontal. ...................................................................................... 37 Figura 3.6: Placa isolada. ................................................................................................ 37 Figura 3.7: Placa Binária. ............................................................................................... 37 Figura 3.8: Placa eliminada de ruídos. ............................................................................ 38 Figura 3.9: Caracteres selecionados................................................................................ 38 Figura 3.10: Caracteres separados. ................................................................................. 38 Figura 3.11: Conjunto de caracteres utilizado no reconhecimento. ................................ 39 Figura 3.12: Tela Principal. ............................................................................................ 41 Figura 3.13: Placa localizada. ......................................................................................... 42 Figura 3.14: Caracteres isolados da placa do veículo. .................................................... 43 Figura 3.15: Caracteres reconhecidos pelo Protótipo. .................................................... 43 Figura 3.16: Tela de resultados. ...................................................................................... 44 Figura 4.1: Porcentagem de acertos e erros (letras). ....................................................... 46 xvii Figura 4.2: Porcentagem de acertos e erros (números). .................................................. 47 xvii Introdução No Brasil, 370 mil veículos são roubados ao ano, deste número estima-se que 37 mil veículos sejam clonados. Os veículos clonados usam placa, chassi e documentos copiados de outro carro. Assim, pode circular sem chamar a atenção da polícia e até ser negociado (RIBEIRO, 2009). Vários veículos estão irregulares no Brasil por vários motivos, seja por falta de manutenção, por falta de pagamento de multas, licenciamento, IPVA, documentos ou ainda por irregularidade na CNH. A fiscalização de veículos é realizada pelos órgãos públicos através de servidores públicos treinados para tanto. A placa é o principal meio de identificação utilizado pelos agentes de fiscalização. Através desta, agentes de trânsito, policiais dos estados e da federação podem verificar as irregularidades dos veículos e também dos motoristas, aplicando multas e também, se for necessário, realizando a apreensão do veículo. A identificação de veículos através das placas também é utilizada por empresas privadas e por pessoas para os mais diversos fins. Um exemplo são os pedágios de rodovias sob concessão onde há uma cabine automatizada que identifica o veículo através de um sensor instalado no para-brisa do veículo. As cabines automatizadas são chamadas de SEM PARAR/VIA FÁCIL1. Quando é detectada a passagem do veículo em um dessas cabines o valor do pedágio é debitado automaticamente na conta do usuário cadastrado pela empresa concessionária. Quando o sensor de identificação do veículo falha a cancela da cabine não abre, o que exige que um fiscal do pedágio peça ao usuário algumas informações sobre veículo. Para estas empresas a verificação da placa também é importante. Para todas as aplicações acima, a adoção de um sistema automático de reconhecimento de placas pode ser benéfico. _____________________________________________________________ 1 Disponível em http://velocidademaxima.wordpress.com/2010/02/06/como-funciona-o-sistema-de-pedagiosem-parar/. Acesso em: 01 de maio de 2010. 1 Tais sistemas de reconhecimento podem ser utilizados não só para fiscalização pelas autoridades de trânsito, mas também em outras aplicações, como estacionamentos de grande porte, condomínios residenciais, shoppings, supermercados, concessionárias de rodovias e qualquer outro setor que possa utilizar esse sistema. Há diversos fatores que dificultam o processo automático de identificação: a placa pode estar em posições distintas (considere, por exemplo, o caso de um automóvel e de um caminhão), os caracteres podem ser de difícil visualização e os ângulos no qual a placa está posicionada podem prejudicar a identificação. Também pode haver a influência de diversos fatores ambientais que dificultam a identificação, tais como: neblina, chuva, sol, entre outros tantos possíveis. De acordo com o CONTRAN (2007) veículos (particulares, aluguel, oficial, experiência, aprendizagem e fabricante) são identificados em todo o Brasil através das placas dianteiras e traseiras. As placas e caracteres possuem as seguintes dimensões respectivamente: • altura de 130 mm e comprimento de 400 mm; • altura de 63 mm e espessura do traço de 10 mm. A figura 1 ilustra o modelo de placas de veículo aceito pelo CONTRAN em todo território brasileiro. Figura 1: Placa de Veículo (CONTRAN, 2007). Neste trabalho serão estudadas as técnicas necessárias para a construção de um sistema de reconhecimento de placas. Posteriormente será construído um sistema protótipo que realizará o reconhecimento de placas de veículos através de imagens que serão inseridas no software. No decorrer do desenvolvimento, ele poderá realizar outras 2 funções como, por exemplo, consultar em uma base de dados se o IPVA e licenciamento do veículo estão atrasados. O reconhecimento de placas de veículos é uma aplicação de reconhecimento de padrões, área que trata de diferentes problemas de ciência e engenharia. Padrão pode ser definido como sendo uma entidade, uma imagem de impressão digital é um exemplo de padrão. O reconhecimento pode ser realizado de duas formas: supervisionado (aprende com intervenção humana), não supervisionado (aprende com base em alguns padrões já conhecido). As aplicações na área de reconhecimento de padrões incluem: mineração de dados, biometria entre outras. Em um sistema de reconhecimento de padrões há três etapas fundamentais: aquisição de dados e pré-processamento, representação dos dados e tomada de decisões. (ANIL; ROBERT; JIANCHANG, 1999). Segundo De Sá (2000) reconhecimento de padrões é a ciência que estuda a classificação e descrição de objetos. Assim um projeto de reconhecimento de padrões envolve: • Extração de características; • Seleção das características; • Construção de um classificador. O reconhecimento de placas de veículos pode ser realizado de várias formas, mas neste trabalho serão explicadas duas formas: na primeira o usuário insere a imagem do veículo no software, através de uma ferramenta de seleção, ele seleciona a placa do veículo e ao clicar duplo do mouse na placa, o software mostra ao usuário quais são as letras e números da placa do veículo. Já na segunda o usuário insere a imagem do veículo no software, automaticamente localiza e seleciona a placa, extrai as características e reconhece cada caractere, e finalmente mostra ao usuário somente as letras e números. Este trabalho tem como objetivo automatizar o processo de reconhecimento de placas a partir de uma imagem inserida no protótipo do software. O processo envolve basicamente localizar a placa de um veículo na cena de uma imagem isolando a região que contém os caracteres da placa. 3 A ferramenta MATLAB permite simular e testar o pré-processamento, localização, identificação e reconhecimento dos caracteres da placa do veículo. O sistema de localização e identificação de placas de veículos funciona da seguinte forma: o usuário insere uma imagem do veículo no software, essa imagem passará por vários tratamentos, se necessário, utilizando técnicas de PDI. Essa imagem é convertida em tons de cinza, depois binarizada para facilitar a identificação. Depois de inserir a imagem o usuário clica em um botão e automaticamente o software selecionará na imagem a placa do veículo. Internamente o sistema utiliza a técnica de segmentação, aonde ocorre à separação dos caracteres da placa criando sete recortes, um para cada caractere. Depois da segmentação o sistema separa caractere por caractere. A parte final é o reconhecimento de caracteres que visa classificar cada um dos caracteres da placa. O Capítulo 1 aborda o conceito de Visão Computacional, a forma de adquirir imagens bem como seus tipos (tons de cinza, binária e RGB) e as várias técnicas de segmentação, como por exemplo, detector de bordas. O Capítulo 2 aborda os conceitos de Inteligência Artificial e Redes Neurais. Apresenta e explica os tipos de redes e algoritmos de aprendizagem (supervisionado e não supervisionado). No Capítulo 3 são apresentadas as etapas de localização e segmentação da placa do veículo, também será mostrado de que forma foi feito o reconhecimento dos caracteres, bem como o funcionamento completo do protótipo. No Capítulo 4 são apresentados os resultados e discussões obtidos neste trabalho. No Capítulo 5 são apresentas as conclusões finais do trabalho e sugestões para a realização de trabalhos futuros. 4 1. Visão Computacional Segundo Facon (2002), a visão computacional é um subcampo da inteligência artificial e se preocupa em desenvolver uma compreensão dos princípios que dão sustentação a aptidão visual em sistemas biológicos e artificiais, e em proporcionar uma máquina com algumas capacidades do sistema visual humano. Tais capacidades incluem habilidades para descrever uma cena baseada em dados fornecidos por sensores de imagens, e produzir entendimento da função, objetivo, e intenção dos objetos reconhecidos. Há dois desafios em visão computacional: • Os dispositivos da área de computação deveriam ser capazes de simular experiências físicas, como a distorção dos objetos contidos na imagem para resolver problemas e comparar as imagens armazenadas na memória com a imagem; • Os computadores deveriam interagir fisicamente e sentir o mundo ao seu redor. Não há modo de capturar e armazenar na memória um modelo que refletem todos os detalhes do mundo real. A visão computacional envolve várias áreas da computação entre elas estão: processamento de imagens, reconhecimento de padrões, computação gráfica e inteligência artificial. O objetivo principal da visão computacional é determinar as características de um objeto que está inserido na imagem. De acordo com Vieira (2010) processamento de imagens significa modificar as informações contidas nessa imagem sob vários aspectos, de modo que o resultado seja uma imagem ou uma informação extraída dela. A imagem é considerada digital quando as coordenadas x, y e o valor da amplitude são finitos e possui quantidades discretas. Essa imagem é constituída de uma quantidade finita de elementos, cada um possui seu valor apropriado. Há várias etapas fundamentais para o processamento de imagens digitais. A figura 1.1 mostra as etapas que devem ser aplicadas em uma imagem (domínio do problema) para produzir um resultado satisfatório. 5 Figura 1.1: Etapas necessárias para o processamento de imagens digitais (BASTOS, 2010) Primeiramente, deve-se deve se pensar em um domínio de problema para situação a ser resolvida e também o que se deseja obter como resultado final. A aquisição de imagens é uma etapa do processamento digital de imagens que consiste em adquirir uma imagem digital, seja através de câmerass digitais ou de qualquer outro dispositivo que tenha saída digital e consiga fazer a captura da cena que está em exibição. A próxima etapa é o pré-processamento pré processamento da imagem digital que consiste em melhorar ar a imagem o máximo possível, através do aumento do contraste e redução de ruídos. O próximo é a segmentação que divide a imagem em partes ou objetos. Ao terminar a segmentação da imagem é obtido como saída dados em forma de pixels. A etapa de representação representação e descrição extrai as características de acordo com a região de interesse. No reconhecimento de caracteres qualquer concavidade é muito importante para se diferenciar entre as partes do alfabeto. A etapa final é o reconhecimento e interpretação. O reconhecimento reconhecimento é o processo no qual o software consegue reconhecer uma letra ou número baseado em informações inseridas pelo usuário. Já a interpretação ocorre quando se consegue atribuir significados, por exemplo, aos caracteres que já foram reconhecidos pelo software. Em reconhecimento de padrões é gerada descrições de imagens, relacionando essas descrições a modelos que caracterizam classes de imagens. O reconhecimento de padrões tem como objetivo fazer a classificação de padrões (objetos). Há dois métodos de aprendizagem utilizados no reconhecimento de padrões: aprendizado supervisionado (tem intervenção humana) e aprendizado não supervisionado (não tem intervenção humana, o computador computador já sabe o que fazer). O 6 reconhecimento supervisionado é baseado em conjunto de padrões que já passou por uma classificação, sendo dividido em dois tipos: • Estatística: pode ser chamado também de decisão teórica, é baseado na caracterização dos padrões estatísticos; • Sintática: pode ser chamado também de estrutural, é baseado nas características estruturais dos padrões; A imagem é pré-processada, por exemplo, para eliminar ruídos e borrados. Em seguida a imagem passa por uma segmentação, aonde ocorre à separação da região de interesse da imagem, essas regiões devem ser homogêneas. Toda imagem a ser analisada deve possuir um padrão, por exemplo, no reconhecimento de placas de veículos, as letras e números têm um padrão brasileiro de altura, largura, comprimento e quantidade de caracteres. Isso deve ser considerado antes de aplicar os algoritmos de inteligência artificial. Entre esses algoritmos estão: k-means, k-nearest neighbor, redes Bayseanas e redes neurais artificiais. No reconhecimento de padrões geralmente a entrada é uma imagem e a saída é uma descrição dos conteúdos da imagem. Há muitas áreas de aplicação em reconhecimento de padrões: 1.2 • Reconhecimento de caracteres; • Reconhecimento facial; • Reconhecimento de biométrico, entre outros. Aquisição e tipos de Imagens 1.2.1 Aquisição de imagens A câmera CCD foi desenvolvida em 1970 nos laboratórios Bell por W. Boyle e G. Smith (RÉ, 2005). Segundo Filho (1998) a câmera forma a imagem através da lente que direciona os raios no sensor da câmera, chamada de lente convergente. O sinal de saída do CCD é 7 linear sobre uma faixa de intensidade muito maior comparado a câmera de tubo. O CCD tem menor distorção geométrica, e sua eficiência quântica pode chegar a 80%. Os detectores CCD caracterizam-se por possuírem alta sensibilidade e baixo ruído. A alta sensibilidade do CCD não ocorre somente em luz visível, mas também em raios ultravioletas e infravermelhos. 1.2.2 Imagens em tons de cinza As imagens em tons de cinza possuem uma escala de 0 a 255, onde 0 representa a cor preta, possui baixa intensidade, e 255 representa a cor branca, possui alta intensidade, os valores entre essas intensidades são considerados tons de cinza. Intensidades de tons de cinza também podem ser representadas em escala de 0 a 1. A figura 1.2 mostra uma imagem em tons de cinza. Figura 1.2: Imagem em tons de cinza. Através da imagem em tons de cinza é gerado um histograma. O histograma dessa imagem é uma função H(k) que representa o número de vezes que cada nível de cinza aparece na imagem, sendo considerada uma função de probabilidades. Depois de obtido o histograma da imagem de tons de cinza pode ser que seja necessário realizar a equalização, mas não é uma regra. A equalização de histograma pode ser utilizada para aumentar todo o contraste da imagem, distribuindo de uma maneira coerente os níveis de tons cinza. A figura 1.3 mostra o histograma de uma imagem em tons de cinza. 8 Figura 1.3: Histograma da imagem em tons de cinza. 1.2.3 Imagens Binárias As imagens binárias são geralmente representadas pelo valor 0 como preto e 1 como branco, mas esses valores podem ser invertidos. Na área de PDI imagens binárias podem ser utilizadas como máscaras, operações de segmentação e limiar. O limiar pode ser aplicado nas imagens binárias para definir a intensidade de 0 e 1. A figura 1.4 mostra uma imagem binária com limiar de 0,525. Figura 1.4: Imagem binária com limiar 0,525. 9 1.2.4 Imagens RGB As imagens RGB são formadas por três componentes: R (vermelho, do inglês Red), G (verde, do inglês Green), B (azul, do inglês Blue). Os componentes da imagem RGB podem possuir 5 ou 8 bits cada um, então uma imagem RGB armazena imagens de 16 ou 24 bits respectivamente. Além disso, há também imagens RGB formadas por 32 bits. Toda imagem é formado por uma matriz de dados. As imagens RGB possuem três matrizes que podem ser divididas em três imagens separadas da imagem original, ou seja, uma imagem formada por R, outra por G, e por B. Essas três componentes são utilizadas de base para a formação de novas cores. Imagens RGB são usadas em dispositivos de entrada, por exemplo: câmeras de vídeo e câmeras digitais, scanners, entre outros. E também são usadas como dispositivos de saída, por exemplo, televisores a cores, celulares, impressoras, computadores, entre outros. A figura 1.5 mostra as componentes R, G, B e RGB. (a) (b) (c) (d) Figura 1.5: Imagem com a componente R (a). Imagem com a componente G (b). Imagem com a componente B (c). Imagem em RGB (d) 10 1.3 Técnicas de segmentação Segundo Da Fonseca (2010) a segmentação de imagens consiste em dividir a imagem em regiões. Existem objetos de interesse em uma imagem que podem isolar pixels que não fazem parte dos objetos. A segmentação de imagens é considerada como um estágio prévio de processamento para o reconhecimento. A segmentação possui relação com a análise de imagens e não com o processamento de imagens. Há várias técnicas de segmentação para a separação de objetos de interesse na imagem, como segmentação baseada em bordas e orientada a regiões. A segmentação orientada a regiões divide a imagem em regiões, analisando a descontinuidade dos níveis de cinza que formam contornos no objeto de interesse, sendo muito utilizados na segmentação e no reconhecimento do objeto. Para se aplicar todas as técnicas de segmentação, a imagem de entrada deve estar em tons de cinza. Há várias técnicas de segmentação de imagens baseadas em bordas e também em linhas. Os tipos de detecções são mostrados abaixo. • Detecção de pontos: a segmentação dos pontos do objeto ocorre de forma particular, tendo em vista que esses pontos possuem informações e não podem ser “destruídos”. Essa técnica é utilizada para eliminar os ruídos, evitando falsas detecções na imagem. O quadro 1 mostra a máscara 3x3 utilizada para detectar pontos na imagem. Quadro 1: Máscara para detectar pontos na imagem -1 -1 -1 -1 8 -1 -1 -1 -1 A figura 1.6 ilustra como deve ficar a imagem depois da aplicação da máscara representada no quadro 1. 11 Figura 1.6: Detecção de pontos na imagem. A Convolução aplicada a imagens realiza operações locais de filtragem. Segundo Dos Santos (1998) uma máscara multiplica cada pixel e seus vizinhos, a região de pixels da imagem deve ser do tamanho da máscara, os resultados são somados e o valor obtido é armazenado na posição equivalente a imagem resultante. Este processo percorre toda a imagem original. Há uma técnica denominada operador de detecção de linhas, baseado em convolução. O conjunto de convolução detecta as linhas com uma determinada largura presente na imagem. A detecção de linhas é divida em quatro tipos: • Detecção de linhas horizontais: detecta a presença de linhas horizontais na imagem. A matriz é composta de valores presentes no eixo x. O quadro 2 mostra a máscara 3x3 utilizada para detectar linhas horizontais na imagem. Quadro 2: Máscara para detectar linhas horizontais na imagem -1 -1 -1 2 2 2 -1 -1 -1 A figura 1.7 ilustra como deve ficar a imagem depois da aplicação da máscara representada no quadro 2. 12 Figura 1.7: Detecção das linhas horizontais. • Detecção de linhas oblíquas (+45º): detecta a presença de linhas que formam um ângulo de 45º positivo na imagem. O quadro 3 mostra a máscara 3x3 utilizada para detectar linhas oblíquas em 45º positivo. Quadro 3: Máscara para detectar linhas oblíquas 45º positivo na imagem -1 -1 2 -1 2 -1 2 -1 -1 A figura 1.8 ilustra como deve ficar a imagem depois da aplicação da máscara representada no quadro 3. Figura 1.8: Detecção de linhas oblíquas 45º positivo. • Detecção de linhas oblíquas (-45º): detecta a presença de linhas que formam um ângulo de 45º negativo na imagem. O quadro 4 mostra a máscara 3x3 utilizada para detectar linhas oblíquas em 45º negativo. 13 Quadro 4: Máscara para detectar linhas oblíquas 45º negativo na imagem 2 -1 -1 -1 2 -1 -1 -1 2 A figura 1.9 ilustra como deve ficar a imagem depois da aplicação da máscara representada no quadro 4. Figura 1.9: Detecção de linhas oblíquas 45º negativo. • Detecção de linhas verticais: detecta a presença de linhas verticais na imagem. A matriz é composta de valores presentes no eixo y. O quadro 5 mostra a máscara 3x3 utilizada para detectar linhas verticais. Quadro 5: Máscara para detectar linhas verticais na imagem -1 2 -1 -1 2 -1 -1 2 -1 A figura 1.10 ilustra como deve ficar a imagem depois da aplicação da máscara representada no quadro 5. 14 Figura 1.10: Detecção de linhas verticais. 1.3.1. Filtros detectores de borda O filtro de detecção de bordas de Canny foi desenvolvido por John F. Canny em 1986. Esse filtro é utilizado principalmente em detecção de contornos de objetos da imagem. Para o algoritmo de detecção de bordas de Canny foi definido um conjunto de metas: • Taxa de erro: detecta o maior número possível de bordas da imagem; • Localização: as bordas marcadas devem ser tão próximas possíveis da borda da imagem original; • Número de resposta: os ruídos da imagem não marcam bordas falsas. Segundo Seara (1998) o algoritmo de Canny é desenvolvido em seis etapas da seguinte forma: • Fazer a leitura da imagem que será processada; • Criar máscara de Gauss 1-D para ser convolucionada com a imagem original; • Criar máscara de Gauss (primeira derivada) 1-D na direções x e y que serão denominadas Gx e Gy respectivamente; • A imagem original é convolucionada com G percorrendo linhas (x) e colunas (y) da imagem original; • A direção x e y da imagem original são convolucionadas com Gx e Gy respectivamente; • Os resultados das componentes x e y são combinados. 15 A figura 1.11 mostra o filtro de Canny aplicado na imagem. Figura 1.11: Filtro de Canny. O filtro de Roberts é um operador gradiente que realiza a detecção de bordas contidas na imagem. Esse operador é formado por uma matriz 2x2, nos eixos x e y. O quadro 6 mostra as máscaras horizontais e verticais do filtro de Roberts. Quadro 6: Máscara horizontal do filtro de Roberts (esquerda). Máscara vertical do filtro de Roberts (direita) 1 0 0 1 0 -1 -1 0 A figura 1.12 mostra a máscara horizontal e vertical do filtro de Roberts aplicado na imagem. (a) (b) Figura 1.12: Filtro de Roberts: Detecção de bordas horizontais (a). Detecção de bordas verticais (b) A Equação abaixo faz a junção das bordas horizontais e verticais, obtendo o operador de Roberts. 16 GR = Gx 2 + Gy 2 (1) Ao aplicar a Equação (1), é obtida imagem mostrada na figura 1.13. Figura 1.13: Filtro de Roberts. O filtro de Prewitt é um operador gradiente que faz a detecção de bordas. A matriz de montagem possui algumas alterações em seus valores em relação ao operador de Sobel. O quadro 7 mostra as máscaras horizontais e verticais do filtro de Prewitt. Quadro 7: Máscara horizontal do filtro de Prewitt (esquerda). Máscara vertical do filtro de Prewitt (direta) -1 -1 -1 -1 0 1 0 0 0 -1 0 1 1 1 1 -1 0 1 A figura 1.14 mostra a máscara horizontal e vertical do filtro de Prewitt aplicado na imagem. (a) (b) Figura 1.14: Filtro de Prewitt: Detecção de bordas horizontais (a). Detecção de verticais (b) 17 A Equação abaixo faz a junção das bordas horizontais e verticais, obtendo o operador de Prewitt. GP = Gx 2 + Gy 2 (2) Ao aplicar a Equação (2), é obtida a imagem mostrada na figura 1.15. Figura 1.15: Filtro de Prewitt. O filtro de Sobel é um operador gradiente que utiliza máscaras horizontais e verticais, é muito utilizado em técnicas de PDI. Esse filtro tem a função de detectar bordas nas imagens, sendo muito sensível a ruídos em comparação ao filtro de Roberts. O quadro 8 mostra as máscaras horizontais e verticais do filtro de Sobel. Quadro 8: Máscara horizontal do filtro de Sobel (esquerda). Máscara vertical do filtro Sobel (direita) -1 -2 -1 -1 0 1 0 0 0 -2 0 2 1 2 1 -1 0 1 A figura 1.16 mostra a máscara horizontal e vertical do filtro de Sobel aplicado na imagem. 18 (a) (b) Figura 1.16: Filtro de Sobel: Detecção de bordas horizontais (a). Detecção de bordas verticais (b) A Equação abaixo faz a junção das bordas horizontais e verticais, obtendo o operador de Sobel. GS = Gx 2 + Gy 2 (3) Ao aplicar a Equação (3), é obtida a imagem mostrada na figura 1.17. Figura 1.17: Filtro de Sobel. A filtragem espacial é uma operação local, na qual os pixels da imagem original são alterados em função dos níveis de cinza. Esta filtragem permite destacar na imagem detalhes, chamado de passa-alta, ou ainda destacar padrões, chamado passa-baixa. O filtro passa-baixa é obtido através de um determinado pixel, calculando a média de seus vizinhos. Em baixas freqüências, o filtro passa-baixa ameniza os detalhes da imagem e diminui os tons de cinza. O quadro 9 mostra as duas máscaras do filtro Passa-Baixa. 19 Quadro 9: Máscaras do filtro Passa-Baixa 1/9* 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . *1/25 A figura 1.18 (a) mostra o Filtro Passa-Baixa aplicada na imagem utilizando a máscara 3x3. Já a figura 1.18 (b) mostra o Filtro Passa-Baixa aplicada na imagem utilizando a máscara 5x5. (a) (b) Figura 1.18: Filtro Passa-Baixa com máscara 3x3 (a). Passa-Baixa com máscara 5x5 (b) O filtro passa-alta é utilizado subtraindo a imagem com o filtro passa-baixa juntamente com a imagem original que não foi processada ou passou por técnica de convolução. Em altas frequências, o filtro passa-alta passa por uma rápida mudança na quantidade de pixels. No filtro passa-alta o histograma da imagem ficará estreito e os níveis de cinza estarão em zero. O quadro 10 mostra as duas máscaras do filtro PassaAlta. 20 Quadro 10: Máscaras do filtro Passa-Alta 1/9 * -1 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 24 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 *1/25 A figura 1.19 (a) mostra o Filtro Passa-Alta aplicada na imagem utilizando a máscara 3x3. Já a figura 1.19 (b) mostra o Filtro Passa-Alta aplicada na imagem utilizando a máscara 5x5. 21 (a) (b) Figura 1.19: Filtro Passa-Alta com máscara 3x3 (a). Filtro Passa-Alta com máscara 5x5 (b) 1.3.2. Técnicas de segmentação aplicadas à detecção de placas Quando um documento ou imagem é digitalizado, por exemplo, através de um scanner antigo é fácil perceber o problema de inclinação na imagem, mas atualmente scanners mais sofisticados e modernos corrigem a inclinação logo na aquisição dos documentos ou imagens. A projeção vertical e horizontal é aplicada para corrigir a inclinação de objetos contidos na imagem. A construção de histogramas de projeção vertical e horizontal é utilizada para detectar as linhas e removê-las. A projeção vertical da imagem é composta de um gráfico que possui um valor global mapeada no eixo y, o vetor característico é formado pela somatória das colunas 22 da matriz. Quando se aplica o filtro para a detecção de bordas verticais, são destacadas na imagem somente as bordas verticais, ao aplicar uma transformada na imagem é localizada a região de interesse. A projeção horizontal da imagem é composta de um gráfico que possui o valor global mapeada no eixo x, o vetor característico é formado pela somatória das linhas da matriz. 1.3.3. Transformada de Hough Em análise de imagens frequentemente surgem os problemas de detecção de bordas, aonde podem ocorrer pontos com ausência de pixels por isso não é viável extrair as características do objeto, deste conceito surge à transformada de Hough. A transformada de Hough é um método proposto por Paul Hough em 1962 que consiste em detectar formas nas imagens (círculos, linhas e elipse). O principio principal é definir como será o mapeamento entre o espaço da imagem que contém as formas a serem detectadas e o espaço de parâmetros de acordo com as características do objeto que estão sendo procurados na imagem. O procedimento mais simples e conhecido da transformada de Hough é a detecção de linhas retas que é descrita pela equação da reta. A Equação (3) mostra como calcular a equação da reta: y = ax + b (3) Onde: y = variável x = variável a = coeficiente angular b = coeficiente linear Segundo Martinsky (2007) a placa retangular pode ser girada e inclinada devido ao posicionamento do veículo em relação à câmera. Se a inclinação da placa dificultar o reconhecimento, é importante implementar mecanismos capazes de detectar e corrigir. 23 Neste trabalho a transformada de Hough pode ser usada para calcular o ângulo de inclinação da placa do veículo. 24 2. Inteligência Artificial O surgimento da inteligência artificial ocorreu após a Segunda Guerra Mundial, com base no artigo Computing Machinery and Intelligence, de Alan Turing2. Os pioneiros Allen Newell e Herbert Simon fundaram o primeiro laboratório de inteligência artificial na Universidade Carnegie Mellon na década de 50. Marvin Minsky, Herbert Simon, John McCarthy, Warren McCulloch, Walter Pitts e Allen Newell foram os principais responsáveis no desenvolvimento da inteligência artificial. A inteligência artificial estuda a criação de sistemas computacionais que sejam capazes de imitar a capacidade do ser humano em realizar tarefas, seja simples ou complexa. Um bom exemplo de IA são os robôs industriais e domésticos. Há várias áreas relacionadas à inteligência artificial, entre elas estão: Filosofia; Engenharias; Ciência da Computação; Lógica; Biologia; Psicologia; Processamento de Linguagem Natural; Aprendizado de Máquina e Redes Neurais; Robótica. A figura 2.1 mostra as etapas necessárias para o desenvolvimento de um sistema de inteligência artificial. Figura 2.1: Etapas para criação de um sistema de inteligência artificial. _____________________ 2 Disponível em http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%2021.Computing_machinery_and_intelligence.turing/2-0%20and%2021.Computing_machinery_and_intelligence.turing-alan.mind-59.1950.062303001.pdf/. Acesso em 10 de abril de 2011. 25 2.1. Neurônios Os neurônios possuem uma fina membrana celular, que são responsáveis pelo funcionamento do sistema nervoso. Eles têm a função de receber e transmitir os estímulos que chegam e partem do cérebro. O ser humano possui em seu cérebro 1011 neurônios (BRAGA, LUDERMIR; CARVALHO, 2000). De modo geral, os neurônios transmitem as informações através de impulsos elétricos. Os sinais são propagados como ondas através do axônio, e a sinapse converte esses sinais em sinais químicos. Os neurônios biológicos são formados basicamente por um corpo celular, dendritos e axônio. De acordo com Braga, Ludermir e Carvalho (2000) o corpo do neurônio mede milésimos de milímetro e os dendritos possuem milímetros de comprimento. Os dendritos são responsáveis por receber os sinais. O axônio realiza a transmissão das informações. A figura 2.2 mostra mais detalhes de sua formação. Figura 2.2: Neurônio Biológico (BRAGA; LUDERMIR; CARVALHO, 2000) Segundo Sabbatini (1995) nos modelos de redes neurais artificiais mais simples, os neurodos (elementos de processamento) recebem influência das entradas vindas do exterior ou dos elementos da rede, já as conexões equivalem à sinapse biológica. Os neurônios artificiais tentam “imitar” ou simular todas as funcionalidades dos neurônios biológicos, mas é difícil comparar o funcionamento desses neurônios, pois cada um tem o seu modo de responder aos estímulos do ambiente. Os neurônios artificiais possuem entradas (dendritos), pesos, neurodo (corpo celular), saída (axônio) e ligação entre neurônios (sinapse). As entradas (e1, e2, e3, e4,...,en) possuem pesos (ω1, ω2, ω3, ω4,...,ωn), os valores de entrada podem ser discretos 26 {-1, 0, 1} ou contínuos [-1, 1]. Os neurônios processam os sinais de entrada e transforma em sinal de saída. O sinal de saída depende da interconexão dos neurônios para se propagar. A equação (4) mostra como calcular o resultado da saída da rede neural artificial: n v= ∑ ei * ωi - σ (4) i=0 Onde: v: net e: entrada da rede ω: peso σ: limiar do neurônio A equação (5) mostra como atualizar os pesos da rede neural artificial. ωnovo = ωvelho + η * e * (d - y) (5) Onde: η: taxa de aprendizado d: saída desejada y: saída da RNA A figura 2.3 mostra um exemplo de neurônio artificial. 27 Figura 2.3: Neurônio Artificial (SABBATINI, 1995) 2.2. Redes Neurais Artificiais e tipos de redes 2.1.1. Redes Neurais Artificiais De acordo com Braga, Ludermir e Carvalho (2000) há alguns pesquisadores fundamentais na área de redes neurais artificiais: McCulloch-Pitts (publicaram artigos sobre o assunto em 1943); Donald Hebb (publicou artigos sobre o assunto em 1949); Rosemblatt (publicou artigo sobre o assunto em 1958). Esses pesquisadores aplicaram o modelo de rede de auto-organização e o modelo Perceptron com aprendizado supervisionado. As redes neurais artificiais são apresentadas através de um modelo matemático com base nos neurônios dos seres humanos, e utilizando técnicas através do computador conseguem adquirir conhecimento e experiência somente com o treinamento. A RNA possui unidades de processamento, que são geralmente conectadas através de canais de comunicação, denominada de sinapse, que são associados a pesos. As unidades de processamento utilizam operações sobre os valores locais. A cada interação das unidades de processamento a rede neural se torna mais inteligente. Antigamente as redes neurais eram simuladas através de circuitos analógicos. Hoje em dia as redes neurais são simuladas através de softwares e também são utilizadas nos hardwares para aumentar a velocidade de processamento dos equipamentos. 28 A RNA possui vários algoritmos para realizar o treinamento de sistemas que serão capazes de cumprir várias tarefas. A figura 2.4 mostra as camadas de uma rede neural artificial, de forma genérica. Figura 2.4: Arquitetura de uma Rede Neural (KUNZLE, 2010) • Camada de Entrada (Input Layer): camada onde as informações ou dados são inseridos na rede; • Camada Intermediária (Middle Layer): camada onde são realizados os cálculos necessários para o treinamento da rede; • Camada de Saída (Output Layer): camada onde são mostrados os resultados. 2.1.2. Tipos de Redes Há vários modelos de Redes Neurais Artificiais, o funcionamento dessas redes é muito semelhante, o que altera é o número de camadas que cada uma apresenta. As Redes podem solucionar dois tipos de problemas: • Linearmente separáveis: De acordo com Braga, Ludermir e Carvalho (2000) problemas linearmente separáveis são problemas em que a solução pode ser obtida dividindo o espaço de entrada em duas regiões, separado por uma reta, como mostra a figura 2.5 (a). 29 • Não linearmente separáveis: são problemas aonde não é possível dividir duas regiões utilizando uma reta, como mostra a figura 2.5 (b). (a) (b) Figura 2.5: Problema Linearmente Separável (a). Problema Não Linearmente Separável (b) Há vários modelos de Redes Neurais Artificiais, a seguir serão apresentados detalhes de dois modelos muito importantes. • Perceptron: a rede Perceptron é o modelo mais antigo de rede neural. Desenvolvido pelo pesquisador Frank Rosenblat no ano de 1958, segue o modelo de neurônio biológico de McCulloch-Pitts (BRAGA; LUDERMIR; CARVALHO, 2000). Este tipo de rede neural é formado por uma camada. A arquitetura do modelo Perceptron é composta de uma camada de entrada e uma camada de saída. As camadas de entrada são ligadas diretamente a um único nó de saída, passando pelos pesos da rede, como mostra a figura 2.6. 30 Figura 2.6: Rede Neural Perceptron. O Perceptron só pode ser treinado para resolver problemas que são linearmente separáveis. • Multi-Layer Perceptron: é uma evolução do Perceptron de uma camada. É uma rede neural formada por duas ou mais camadas, cada camada é ligada a outra. A arquitetura do modelo Multi-Layer Perceptron é formada por camada de entrada, camada intermediária e camada de saída, como mostra a figura 2.7. Figura 2.7: Rede Neural Multi-Layer Perceptron (BRAGA; LUDERMIR; CARVALHO, 2000) O Multi-Layer Perceptron com camada intermediária consegue resolver problemas que não são linearmente separáveis. Segundo Braga, Ludermir 31 e Carvalho (2000) na teoria, as redes que possuem duas ou mais camadas podem resolver problemas linearmente separáveis ou não. Essa rede neural utiliza o aprendizado supervisionado e também o algoritmo chamado de backpropagation para o treinamento da rede. O algoritmo backpropagation utiliza correção de erros para ajustar os pesos e aprendizado supervisionado. O treinamento da rede é dividido em duas fases: forward (através de uma entrada define qual será o valor de saída); backward (através da saída desejada e o valor de saída conseguida pela rede é feita a atualização dos pesos). De acordo com Braga, Ludermir e Carvalho (2000) o algoritmo backpropagation possui vários problemas que impede a sua expansão. O problema mais grave apresenta lentidão para superfícies complexas. O Perceptron e o Multi-Layer Perceptron possuem várias aplicações, entre elas estão: inteligência artificial, reconhecimento facial, reconhecimento de caracteres, entre outros. 2.3 Aprendizado As redes neurais são capazes de aprender e diminuir o erro na saída, e assim melhorar o desempenho. Para a rede conseguir realizar tarefas e solucionar problemas é preciso treiná-las, para isso existem vários algoritmos de aprendizado, a única diferença entre esses algoritmos é forma com que os pesos da rede neural são alterados. De acordo com Braga, Ludermir e Carvalho (2000) algoritmos de aprendizagem é um conjunto de regras para solucionar problemas de aprendizagem. 2.3.1 Aprendizado Supervisionado e Não Supervisionado O aprendizado supervisionado é considerado um paradigma de aprendizado. Este aprendizado ocorre quando o ser humano mostra a resposta desejada a rede de acordo com os valores que foram inseridos como entrada. 32 De acordo com Braga, Ludermir e Carvalho (2000) o objetivo do aprendizado supervisionado é ajustar os parâmetros da rede neural artificial para encontrar ligações entre entradas e saídas. Há duas formas de implementação do aprendizado supervisionado: • Off-line: as respostas obtidas com o treinamento da rede não mudam até que um novo treinamento seja realizado; • On-line: os dados são alterados em tempo real obrigando a rede a passar a todo o momento por uma adaptação. A figura 2.8 mostra o funcionamento do aprendizado supervisionado, basicamente à rede compara a resposta desejada (saída desejada) com a resposta calculada (saída calculada), a cada iteração os pesos são ajustados com o objetivo de minimizar o erro. O professor (supervisor) tem a função de informar a rede entradas e saídas desejadas. Figura 2.8: Aprendizado supervisionado (BRAGA; LUDERMIR; CARVALHO, 2000) A aprendizagem por Correção de Erros3 é um método para implementação do aprendizado supervisionado. A rede Perceptron é um modelo de RNA que utiliza o aprendizado supervisionado. O aprendizado não supervisionado é considerado um paradigma de aprendizado. Este aprendizado não tem interferência dos seres humanos nos resultados da rede. 33 Segundo Braga, Ludermir e Carvalho (2000) o aprendizado não supervisionado é semelhante ao supervisionado e ao aprendizado dos seres humanos, um exemplo são os estágios iniciais da visão e audição que utilizam o aprendizado não supervisionado. A figura 2.9 mostra o funcionamento do aprendizado não supervisionado. No aprendizado não supervisionado a rede tem a disposição os padrões de entrada. Figura 2.9: Aprendizado não supervisionado (BRAGA; LUDERMIR; CARVALHO, 2000) A rede tenta encontrar esses padrões nos dados de entrada e assim criar classes de forma automática. Há vários métodos de aprendizagem para implementação do aprendizado não supervisionado: Competitivo4, Hebbiano5, entre outros. A rede feedforward é um modelo de RNA que utiliza o aprendizado não supervisionado. ____________________ 3 Disponível em http://www.lncc.br/~labinfo/tutorialRN/frm1_aprendizado.htm#aprendizadoCompetitivo/. Acesso em 20 de abril de 2011. 4 Disponível em http://www.lncc.br/~labinfo/tutorialRN/frm1_aprendizado.htm#aprendizadoHebbiano/. Acesso em 20 de abril de 2011. 5 Disponível em http://www.lncc.br/~labinfo/tutorialRN/frm1_aprendizado.htm#aprendizadoCorrecaoErro/. Acesso em 20 de abril de 2011. 34 3. Materiais e Métodos 3.1. Localização A localização é a principal etapa para o reconhecimento da placa do veículo, pois se for mal realizada todo trabalho depois disso será prejudicado. A etapa de localização é realizada depois do pré-processamento da imagem. O pré-processamento consiste em um tratamento para melhorar a qualidade da imagem, é utilizado detecção de bordas mais especificamente filtro de Sobel para facilitar a localização. Para conseguir bons resultados na localização da placa é essencial que a imagem do veículo tenha o tamanho 640x240 pixels. No trabalho é utilizada uma base de dados formada por 100 imagens do CBPF (Centro Brasileiro de Pesquisas Físicas)6. A figura 3.1 mostra um exemplo da imagem original do veículo contida nesta base. Figura 3.1: Imagem Original do Veículo. Durante a etapa de localização foi utilizado duas técnicas para conseguir obter a placa do veiculo: • A projeção vertical realiza a somatória das colunas da matriz e através de um gráfico pode-se visualizar o pico mais alto que representa a banda onde provavelmente encontra-se a placa do veículo. A figura 3.2 mostra graficamente a possível região candidata a presença da placa. ________________ 6 Disponível em http://www.cbpf.br/cat/pdsi/lpr/lpr.html. Acesso em 1 de agosto de 2011. 35 Figura 3.2: Gráfico da projeção vertical. Já a figura 3.3 mostra o resultado depois da aplicação da projeção vertical na imagem do veículo. Figura 3.3: Projeção vertical. • A projeção horizontal realiza a somatória das linhas da matriz e através de um gráfico pode-se visualizar os picos mais altos que representa a banda onde provavelmente encontra-se a placa do veículo. A figura 3.4 mostra graficamente a possível localização da placa. Figura 3.4: Gráfico da projeção horizontal. 36 Já figura 3.5 mostra o resultado da aplicação da projeção horizontal na imagem do veículo. Figura 3.5: Projeção horizontal. A partir da projeção horizontal, percorre-se a imagem a procura de um retângulo do tamanho da placa, depois é reajustado o tamanho da placa para 500x100 pixels e isolada da imagem, como mostra a figura 3.6. Figura 3.6: Placa isolada. É importante isolar a placa da imagem original, pois a próxima etapa de segmentação será mais simples de implementar e conseguir resultados mais satisfatórios após a segmentação. 3.2. Segmentação A etapa de segmentação é necessária para eliminar o máximo possível de ruídos contidos na placa e assim facilitar o reconhecimento dos caracteres. Primeiramente a placa é convertida para imagem binária (imagem formada por 0 e 1), como mostra a figura 3.7. Figura 3.7: Placa Binária. Depois através de morfologia, utilizando o comando bwareaopen do MATLAB é possível remover em uma imagem binária objetos que possuem um determinado valor de pixels (p) gerando uma nova imagem binária, como é mostrado abaixo. imagem_binaria = bwareaopen (img_bin, p) 37 A figura 3.8 mostra a placa depois de aplicar o comando bwareaopen. Figura 3.8: Placa eliminada de ruídos. Os caracteres da placa do veículo são selecionados para posteriormente serem reconhecidos. A placa do veículo contém sete caracteres, sendo três letras e quatro números, se for não respeitada esta regra não é considerada placa. Para buscar regiões de interesse foi utilizada a função chamada regionprops. Abaixo é mostrado parte do código desenvolvido no MATLAB para selecionar os caracteres da placa do veículo. [L Ne] = bwlabel (imgn); propied = regionprops (L,'BoundingBox'); hold off for n = 1:size (propied,1) rectangle ('Position',propied(n).BoundingBox, 'EdgeColor','b','LineWidth',2) end hold off A figura 3.9 mostra os caracteres selecionados pelo protótipo. Figura 3.9: Caracteres selecionados. Ao selecionar os caracteres, os mesmos são separados da placa do veiculo da seguinte forma: cada posição do caractere é colocada em um componente do MATLAB chamado de axes. A figura 3.10 mostra os caracteres separados da placa. Figura 3.10: Caracteres separados. 38 3.3. Caracteres 3.3.1. Reconhecimento A etapa de reconhecimento é muito importante, pois é a partir disso que será possível fazer várias consultas com relação ao veículo e proprietário. O reconhecimento é realizado utilizando um conjunto de caracteres, como mostra a figura 3.11. Figura 3.11: Conjunto de caracteres utilizado no reconhecimento. Neste trabalho é utilizada correlação para reconhecer os caracteres da placa do veículo, da seguinte forma: - Correlação: compara a imagem de cada caractere (letras e números binários) encontrado pelo protótipo com cada caractere do conjunto mostrado na figura 3.11, o caractere selecionado será o de maior correlação. No MATLAB o coeficiente de correlação é calculado utilizando a equação (6). r = corr2 (A,B) (6) Onde: A e B = matrizes ou vetores do mesmo tamanho. O corr2 é calculado através da equação (7): (7) Onde: 39 = média dos elementos da matriz A = média dos elementos da matriz B As equações (6) e (7) foram obtidas no help do MATLAB. Para a forma citada acima é necessário utilizar um OCR. O OCR é essencial em toda aplicação de reconhecimento de caracteres e tem a função de realizar a conversão da imagem do caractere em texto mostrando o resultado final ao usuário. Nesta etapa foi constatado que alguns números podem ser trocados por letras, por isso mesmo com a utilização do OCR foi necessário realizar um pequeno tratamento, da seguinte forma: • Q, D e O confundem-se com o número 0; • B e D confundem-se com o número 8; • S confunde-se com o número 5; • Z confunde-se com o número 2; • C e G confundem-se com o número 6; • T e I confundem-se com o número 1; Depois de realizar o tratamento mostrado acima, o protótipo conseguiu reconhecer mais caracteres. 40 3.4. Protótipo 3.4.1. Apresentação O protótipo realiza o reconhecimento dos caracteres de placa dos veículos, foi desenvolvido na ferramenta MATLAB e pode ser utilizado através de uma interface muito intuitiva e de fácil aprendizagem. Todo processo realizado para o reconhecimento dos caracteres foram feitos em um notebook Pentium Dual-Core com 1 GB de memória RAM. Esse protótipo é compatível com vários formatos de imagens (JPEG, BMP, entre outras) e para obter melhores resultados foi necessário definir um padrão de imagem, no caso deste trabalho foi escolhido o tamanho 640x240 pixels. Além de realizar o reconhecimento dos caracteres, o protótipo aplica vários tipos de filtros nas imagens e faz conversões para tons de cinza, binário e negativo. E também conta o total de imagens abertas, número de placas, número de não placas e a porcentagem de caracteres certos e errados. A figura 3.12 mostra a tela principal do protótipo. Figura 3.12: Tela Principal. 41 3.4.2. Funcionamento O funcionamento é muito simples, basta escolher a pasta onde se encontra as imagens e abri-las, a partir disso o protótipo realiza todas as etapas para o reconhecimento e mostra os caracteres encontrados ao usuário de forma totalmente automática. A seguir será mostrado passo a passo o funcionamento do protótipo. • Primeiramente, o protótipo localiza a região candidata a presença da placa na imagem da projeção horizontal, como mostra a figura 3.13. Figura 3.13: Placa localizada. • A partir da figura 3.13 é gerada a imagem dos caracteres isolados da placa, como mostra a figura 3.14. 42 Figura 3.14: Caracteres isolados da placa do veículo. • Depois de isolar os caracteres da placa, é realizada a comparação de cada caractere com a base de dados através de correlação. Os caracteres reconhecidos são mostrados em forma de texto, como mostra a figura 3.15. Figura 3.15: Caracteres reconhecidos pelo Protótipo. • Ao terminar o reconhecimento de todas as imagens, abrirá automaticamente uma tela, ao clicar no botão “Gerar” será exibido ao usuário o total de imagens, à quantidade de placas localizadas e não 43 localizadas, todos os caracteres reconhecidos, bem como a porcentagem de placas, não placas, acertos e erros de caracteres. A figura 3.16 mostra a tela de resultados. Figura 3.16: Tela de resultados. 44 4. Resultados e Discussões A proposta de localizar a placa do veículo e reconhecer os caracteres da mesma foi cumprida, mas ainda ocorrem alguns erros de localização e reconhecimento. Para mostrar os resultados obtidos neste trabalho será utilizada matriz de confusão, quadros e gráficos. A matriz de confusão faz parte da área de inteligência artificial sendo utilizada através de aprendizado supervisionado. Neste tipo de matriz as linhas representam a classe Real, já as colunas representam a classe Previsto. O quadro 11 mostra o formato da matriz de confusão, aonde placa é classificada como p e não placa é classificada como np. Quadro 11: Matriz de confusão. Real Previsto P np P 42 33 Np 1 24 Para gerar o quadro acima foi utilizada uma planilha com placas originais e uma planilha com as placas reconhecidas pelo protótipo, é feita a comparação entre as duas planilhas e se tiver sete caracteres é considerado placa, senão não é placa. O quadro 11 pode ser interpretado da seguinte forma: • Na primeira linha, das 75 placas reais o protótipo localizou 42 como sendo placa e 33 como sendo não placa; • Na segunda linha, das 25 não placas reais o protótipo localizou 1 como sendo placa e 24 como sendo não placa. A porcentagem de acertos de placas localizadas foi de 66% e de erros foi de 34%. 45 Depois de mostrar a porcentagem de placas localizadas pelo protótipo, é fundamental mostrar quais placas foram reconhecidas (ver Apêndice A). A porcentagem de acertos no reconhecimento das placas foi de 36%, já de erros foi de 64%. Com esses dados é possível dizer que a quantidade de acertos foi menor que a de erros, isso mostra que em algumas placas ocorreu erro ao reconhecer caracteres. O índice de acertos pode ser melhorado utilizando redes neurais. A condição de erro ou acerto definido pelo protótipo é feita comparando a planilha de caracteres originais com a planilha de caracteres reconhecidos pelo protótipo se forem exatamente iguais, ou seja, letras e números iguais nas sete posições são considerados acertos, senão são erros. Depois de analisar as 100 imagens com relação à localização e reconhecimento das placas, serão mostradas nas figuras 4.1 e 4.2 a porcentagem de acertos e erros de cada letra e número respectivamente. Figura 4.1: Porcentagem de acertos e erros (letras). Na figura 4.1 é possível observar que as letras M, Q e V obtiveram 100% de erro, já J, W, Y e Z obtiveram 100% de acerto e as demais letras apresentaram variações de acerto e erro, pois o OCR implementado apresentou dificuldades ao reconhecer algumas letras. 46 Figura 4.2: Porcentagem de acertos e erros (números). Na figura 4.2 é possível perceber que o número 6 obteve 100% de erro, isso aconteceu porque em algumas placas ele foi trocado por 4 e em outras por 5. Já os demais números apresentaram variações de acertos e erros. 47 5. Conclusão 5.1. Considerações Finais Neste trabalho, o objetivo proposto foi localizar placas dos veículos e reconhecer caracteres de forma totalmente automática. Antes da localização da placa foi necessário realizar um pré-processamento na imagem, como a imagem procurada foi um retângulo foi necessário aplicar um detector de bordas, neste caso Sobel para destacar as bordas da imagem e assim facilitar a localização da placa. A localização da placa é o ponto principal deste trabalho, pois se essa etapa não for cumprida corretamente pode prejudicar as etapas seguintes. Os métodos de projeção vertical e horizontal apresentaram resultados aceitáveis ao localizar a placa do veículo. Ao selecionar a placa na imagem original foi possível isolá-la e binarizá-la (imagem passou a ser preto e branco). Aplicou-se morfologia para eliminar objetos que não tinha interesse em realizar o reconhecimento. Para reconhecer os caracteres está sendo utilizada correlação, mas somente com rede neural talvez seja possível obter um maior número de caracteres reconhecidos corretamente. Algumas letras são bem semelhantes aos números (como foi citado no item 3.3.1) por isso foi necessário um tratamento para evitar o reconhecimento de caracteres errados, mas mesmo assim alguns caracteres não são reconhecidos corretamente pelo protótipo. O algoritmo de localização (projeção vertical e horizontal) mostrou-se muito eficiente, pois teve um índice de acerto de 66%. Já o algoritmo de reconhecimento não possui muita eficiência, pois acertou menos da metade dos caracteres da placa. Os resultados obtidos com o trabalho podem ser considerados bons, mas ainda não pode ser utilizado como um produto final é necessário alguns ajustes. As letras e números possuem variações de acertos e erros, ou seja, o protótipo está instável. Se for comparado acertos de letras e números é possível observar que as letras apresentam alto índice de acerto no reconhecimento. 48 De modo geral, todas as etapas que envolvem o reconhecimento dos caracteres são difíceis, pois uma etapa depende totalmente da outra. O objetivo citado no início deste trabalho foi cumprido de forma satisfatória, apesar dos resultados esperados não foi de alta qualidade. 5.2. Trabalhos Futuros Para trabalhos futuros o sistema de reconhecimento de placas de veículos pode ser implementado em uma linguagem de programação para deixar o sistema mais estável, aprimorar o reconhecimento dos caracteres e também fazer a comunicação com um banco de dados para realizar várias consultas, como: multas, IPVA vencido e se o veículo é roubado. Esse protótipo também pode ser adaptado e implementado em dispositivos móveis (celulares, tablets e etc). E através da câmera pode ser feito o reconhecimento da placa do veículo e assim realizar consultas via internet. 49 Referências Bibliográficas ANIL, K. J.; ROBERT, P.W. D.; JIANCHANG M. Statistical Pattern Recognition: A 1999. Review, Disponível em: <http://www.cse.msu.edu/~cse802/Papers/JainDuinMao_StatisticalPatternRecognition.p df>. Acesso 15 de maio de 2010. BASTOS, V. P.; DUARTE, Prof. G. D.; CARUSO, Prof. P. D. M. Processamento de Imagens, 2010. Disponível em <http://paginas.ucpel.tche.br/~vbastos/pi.htm>. Acesso em: 23 de junho de 2010. BRAGA, A. de P.; LUDERMIR, T. B.; CARVALHO, A. C. P. de L. F. Redes Neurais Artificiais: Teoria e Aplicações. 1. ed. Rio de Janeiro: LTC, 2000. CONTRAN. Resolução 231, 2007. Disponível em http://www.denatran.gov.br/download/Resolucoes/RESOLUCAO_231.pdf>. < Acesso em: 25 de agosto de 2011. DA FONSECA, M. S. Segmentação de Imagem: Segmentação Limiar em Tons de Cinza, 2010. Disponível em <http://www.ic.uff.br/~aconci/limiarizacao.htm>. Acesso em: 05 de agosto de 2010. DE SÁ, J. P. M. Reconhecimento de Padrões, 2000. Disponível em <http://paginas.fe.up.pt/~jmsa/recpad/index.htm>. Acesso em: 20 de abril de 2010. DOS SANTOS, Cleiton Almeida. Convolução, 1998. Disponível em <http://www.inf.ufsc.br/~visao/1998/cleiton/convolucao.html>. Acesso em: 20 de agosto de 2011. 50 FACON, J. Princípios básicos da visão por computador e do processamento de imagens. Pontificia Universidade Católica do Paraná. Curso e Mestrado em Informática Aplicada, 2002. FILHO, K. de S. O. Como funciona uma câmera CCD?, 1998. Disponível em <http://astro.if.ufrgs.br/med/imagens/node14.htm> Acesso em: 21 de maio de 2010. KUNZLE, P. Vehicle Control with Neural Networks, 2010. Disponível em <http://www.gamedev.net/reference/articles/article1988.asp>. Acesso em: 25 de outubro de 2010. MARTINSKY, O. Algorithmic and Mathematical Principles of Automatic Number Plate Recognition Systems - Brno University of Technology. BRNO University of Technology. Faculty of Information Technology. Department of Intelligent Systems, 2007. RÉ, P. O ABC das câmeras CCD, 2005. Disponível em <http://www.astrosurf.com/re/abc_camaras_ccd_pre.pdf>. Acesso em: 21 de maio de 2010. RIBEIRO, F. Golpe contra o cidadão: Clonagem de carros assusta. Diário do Nordeste, Fortaleza, 16 de novembro de 2009. Disponível em <http://diariodonordeste.globo.com/materia.asp?codigo=692266>. Acesso em: 22 de abril de 2010. SABBATINI, Prof. Dr. R. M. E. Consultoria: Revista Informédica, 1995. Disponível em <http://www.informaticamedica.org.br/informed/cons006.htm>. Acesso em: 26 de outubro de 2010. 51 SEARA, Daniela Marta. Algoritmo para detecção de bordas, 1998. Disponível em < http://www.inf.ufsc.br/~visao/1998/seara/index.html>. Acesso em: 20 de agosto de 2011. VIEIRA, Prof. Dr. M. A. da C. SEL-0339 Introdução à Visão Computacional – Aula 3: Processamento Espacial, 2010. Disponível em <http://iris.sel.eesc.usp.br/sel339/Aula_3.pdf>. Acesso em: 26 de maio de 2010. 52 APÊNDICE A – COMPARAÇÃO ENTRE PLACAS ORIGINAIS E PLACAS RECONHECIDAS PELO PROTÓTIPO. Placa Original Placa Reconhecida LOH8516 LOH8514 LID5816 LAO5914 LNZ7675 LNZ7475 LOF2025 LAY2576 LAY2575 LOA2563 LOA2553 GOL0197 LNU2885 LNU2885 LKI6549 LKI4542 KRJ3113 KRJ3113 KRD7080 KRD7366 KRD2355 LNJ8753 LNJ9753 KUF2376 LNP1417 LNP1417 DUR7778 DUR7778 LNF5873 LNF5873 LNR3839 53 LIN2148 KMV8068 LNO3968 LKO3249 LNP7221 KOE0313 KRA1369 KMN0857 KHN0957 LND3416 LND3435 LNZ3777 LNZ3777 LNG6631 LNG5531 KNI0508 KMU0087 LCK1312 KSL0273 LOE2022 LOF2029 LCS8217 LQS9217 LBD2319 LQD2312 CSE9780 CSE7801 LAG5887 LBU5699 LBU5422 LBL9606 LLL240K 54 LAK8614 AAK0124 LNI2993 LNA2991 LOE0836 LOE0834 KPC7603 KQH7731 KDH7731 AAY5127 AAY5177 LOA7993 LOA7273 KND8865 LNR0491 KNP9837 KNP9837 KMG0982 LAV5233 KQQ0310 LOA1784 LBD9538 KMG6921 KHG4221 LBO1230 LBO4230 KOD7347 KTS1316 LCN7724 ABY9198 ABY9198 GZA2477 GZA2477 55 LAR7207 LAR7207 KMO7265 CTB1569 CTB1859 LOF3405 LOF3405 LIK3988 LSK3988 KOC1299 LMN0916 III0111 LCD7645 LCD7445 LNP5569 LBL9709 LCA7450 LNZ4292 LNZ4222 JLW9464 JLW2444 56