F2010E013
An Algorithm for Road Sign Recognition using Levenshtein Distance
Image recognition systems in automobile field should be not only inexpensive to spread over the world but also robust. A robust system should maintain the recognition ratio even though a part of an image captured from in-vehicle camera is hidden by tree. A proposed recognition algorithm enables to achieve maintaining the recognition ration on an inexpensive chip. To make its circuit simple and to increase the operation speed, the proposed algorithm adopts a template matching using Levenshtein distance. In general, Levenshtein distance is applied to judge the similarity of DNA sequence in a bioinformatics field and spell checker. To use template matching for digital pictures, the pictures are converted into character lines consisted of three types of characters (r: red, b: blue, and space: the others), as shown in Fig.1. The character lines are compared with templates. In order to maintain the recognition ratio, the proposed algorithm is also provided with two recognition stages. The primary stage judges whether a road sign is circular or not, and its color, too. The secondary stage decides type of the sign in detail. In judging shape of the sign, the primary stage obtains its center and calculates an error. Suppose that the center of the sign is denoted as (a, b). Each pixel of an outer edge for a sign is (Xi, Yi). The attached equation is defined as an error function using the least squares method and the value of this function is judged the sign shape. The image data covered by tree or bended are lost information for the road sign. Fig. 2 shows the relation between the size of the lost information and its recognition ratio. Its result shows 20% improvement compared with not only an original algorithm but also a general pattern matching algorithm. It is necessary for this proposed algorithm to recognize the road traffic sign in real time. This algorithm consists of only integer-operations and can be mounted on an FPGA. A software simulation using Pentium4 2.8 GHz processor　takes 42.3 ms. The algorithm is implemented on Xilinx Spartan-3 using Bach-C at 49.8 MHz and achieved 17.0 ms execution time. The proposed algorithm shows the improvement of recognition ratios and can be executed on an inexpensive device at low power.
This abstract is supplemented by a PDF, which can be viewed here.
Session: Intelligent Traffic Systems