Number plate reading using computer vision

J. Barroso (**), A. Rafael (***),  E. L. Dagless (****) e J. Bulas-Cruz (*)

(*) Professor Auxiliar (****)Assistente

Universidade de Trás-os-Montes e Alto Douro, Secção de Engenharias Apt.202, 5001 Vila Real Codex, Portugal

 (***) Professor Associado

Universidade de Aveiro, Departamento de Electrónica e Telecomunicações Apt. , Aveiro, Portugal

(***) Professor of Microeletronics

University of Bristol, Dep. of Elect. & Electronic Eng. University Walk, Queen's Building Bristol BS8 1TR, United Kingdom

Abstract - Vehicle number plate recognition systems are expected to have numerous applications in traffic surveying and monitoring, e.g. finding stolen cars, controlling access to car parks and gathering traffic flow statistics. The Computer Vision Group at the University of Trás-os-Montes e Alto Douro, in collaboration with the Universities of Aveiro and Bristol, has been developing a number plate reading system [3][4][5]. The system builds on the experience gained by the Computer Vision Group at the University of Bristol while developing previous transputer based prototypes [5][6][8][12].

 The main tasks of a number plate recognition system are the location of the number plate area in the image, the segmentation of the characters and their identification. These tasks are strongly inter-related, mainly because the way to check if the number plate has been correctly located is based on the result of the character identification process (it should correspond to a predefined syntax). Algorithmic improvements to previous versions of the system, based on the results of intensive testing, are described in the paper. For the location of the number plate area in the image, a new line-based method has been developed. The method, instead of looking for character like shapes in the image, takes advantage of the "signature" of the number plate area in a horizontal cross-section of the image. The method used for the segmentation of the characters is derived from a technique first proposed by Lu [8]. The identification of the characters uses the OCR engine developed by Barroso et al [3][4], based on the crical points method [10][11].

INTRODUCTION

A growing demand for traffic data concerning traffic flow and automatic vehicle identification, led researchers around the world to adopt advanced electronic and computer vision technologies to monitor and control traffic [1][2][7]. Increasing levels of road traffic ask for real time analysis of the captured images in order to extract important data, in this case the vehicle registration number.

 In a typical situation, a number plate reading system will analyse the images captured by a camera at the road side or at the entrance of a car park. The grabbing system may be triggered by an inductive loop. The system should find and recognise number plate characters in a video frame, in order to decode the number plate. Experience shows that, in order to cope with heavy traffic, the average processing time should be under 1 second per number plate.

 Fig. 1 shows a functional decomposition of the number plate reading system. The controller distributes the tasks to the different modules. The main modules correspond to the main tasks of a number plate recognition system: the location of the number plate area in the image, the segmentation of the characters and their identification. These tasks are strongly inter-related, mainly because the way to check if the number plate has been correctly located is based on the result of the character identification process. If a given set of characters conforms to a predefined syntax it is usually assumed that the number plate has been found and no further search is performed.

 For the location of the number plate area in the image, a new line-based method has been developed. The method, instead of looking for character like shapes in the image, takes advantage of the "signature" of the number plate area in a horizontal cross-section of the image. The method used for the segmentation of the characters is derived from a technique first proposed by Lu [9]. These methods are described in section II.

 The OCR (Optical Character Recognition) engine used to identify the characters is described in Section III. It is based on the critical points method [10][11].

 The syntax checking module is at the moment of a simple nature. It is mainly used to distinguish letters from numbers, in difficult cases (e.g. "B,8" and "O,D"). It will not be further described in this paper.

Fig. 1 - Functional decomposition of the number plate reading system.

 NUMBER PLATE LOCATION AND CHARACTER SEGMENTATION

 In order to locate the number plate area in previous versions of the system [5][6][8][12], a search for character like shapes was conduced. When three or more such shapes were found in similar horizontal positions, the system would look in the neighbourhood for other similar shapes. At a second stage, if the shapes were identified as number plate characters, the system would assume a number plate region had been found.

 In order to improve the performance of the location process, a new technique has been developed. This technique is based on the fact that the lines where the number plate is located in the image have a clear "signature" which makes it usually possible to distinguish them from other lines in the image, or at least to pre-select some positions where to look further. Fig. 2 shows two such lines. The top image shows the positions of the cross sections (the white lines). The "signature" of the number plate can be observed in the bottom cross section. It corresponds to strong grey level variations at somehow "regular" intervals.

 The analysis of the image lines in order to identify which lines "cut" the number plate has been conduced both in the spatial an in the Fourier domain. In the Fourier domain the analysis has proved to be very difficult and so the work continued using spatial information. An algorithm which analyses the maxima and minima of the cross section has been developed. The algorithm searches for a set of continuous maxima and minima that have some predefined characteristics (number, relative distances, amplitude, etc.). These characteristics are dynamically chosen from a set of predefined values, using statistical information.

Fig. 2 - Cross sections of a car image (the "signature" is shown in the bottom image).

 Once an horizontal line that crosses the number plate has been located, this information is used to define an area which should contain the number plate image. This area is shown in Fig. 3, for the image in Fig. 2.

 The following step is to locate the number plate area more accurately. This is achieved by using the vertical and horizontal projections of a binary version of the previous image, as shown in Fig. 3. These projections will normally indicate the precise position of the number plate set of characters. The threshold value is dynamically chosen, based on the value of the grey level maxima and minima.

 In order to segment the characters in the number plate image a method based on a technique first proposed by Lu [9], named peak-to-valley, is used. The method searches for valleys in the vertical projection of the binary image, Fig. 4.

Fig. 3 - Accurate location of the number plate area.

 In order to evaluate the proposed methods, a set of tests has been conduced. Three image databases have been created: D1, of images taken at the entrance of a car park; D2, of images of vehicles travelling on a road under normal weather conditions; and D3, of images of vehicles travelling on a road under bat weather conditions (e.g., fog, rain).

Fig. 4 - Character segmentation.

The results are as follows:

• D1 - 100.0% correct number plate location;
• D1 - 99.5% correct number plate location;
• D3 - 88.5% correct number plate location;

 These results show an improvement in performance when compared with the previous method. The images in D3 are of poor quality and the previous method would normally fail. In images of good quality, the improvement comes mainly from the fact that this method is much faster. Typical execution times (Pentium 120MHz) vary from 5 ms to 100 ms, while the previous method would typically take from 200 ms to 500 ms.

• THE OCR ENGINE

 In previous versions of the system the OCR engine is based in a template matching algorithm. The shapes identified as possible characters in the previous steps of the process are binarized and scaled to match the size of the templates in a database, usually 5x8 or 8x10. Each shape is compared with all the characters in the database by template matching. The five best matches are selected and a syntax checker is used to choose the best candidate for the number plate, according to available formats of the plate which define relevant positions of the numeral and alphabetic characters. This helps solving clashes between similar numeral and alphabetic characters such as "8/B" and "0/O/D".

 The procedure used to generate the character templates, and to transform a character to be recognised in a form which is suitable for the matching process, is described below. The scheme is illustrated in Fig. 5.

 The binary image of the character is scaled to an intermediate array by replicating each pixel in the horizontal and vertical dimensions as many times as the size of the template. In the example of the figure, the character size is 4x5 and the template size is 3x4, which gives an intermediate array of 12x20 cells. A grid of the stored template size is "superimposed" on to the intermediate array. Each element of the template takes a value which is equal to the number of "1" pixels in the intermediate array in the corresponding region. Normalisation is achieved by dividing the value in each cell of the template by the area of each cell in the intermediate array (4x5=20, in the example) and multiplying by a scaling factor (2000 is the value being used).

Fig. 5 - Ilustration of the template generation process.

 The distance between an unknown character and a reference template is given by the Euclidean distance.

If a template matching scheme is used to identify the characters in the number plate, in order to get a high recognition rate it is necessary to use large templates and sometimes more than one template per character. However, processing time increases with the number of templates and with their size.

 The template matching procedure adopted has a high degree of tolerance to variations in the shape of the characters, but at the cost of misclassifying some characters, (e.g. the distance between some "4" characters and the "A" template is very short).

 The OCR engine developed in this work uses a feature matching technique to analyse the characters, and reserves template matching to decide between characters with similar features or just to confirm the classification.

 The critical points technique first proposed by Shchepin and Nepomnyashchii [10][11] to read printed text has been adapted with success. The technique is based on a topological analysis of the character and is characterised by finding the critical points of the boundary, maxima and minima. Once the critical points have been found and smoothed, to remove "false" critical points produced by noise, a number of numerical sequences which lead to the classification of the character is derived.

Fig. 6 - Flowchart of the critical points method.

 The flowchart of the critical points technique (using only the level sequence), is shown in Fig. 6.

A binary image is obtained by thresholding the grey-level image of the character. The contour is extracted and the maxima and minima (both in the X and Y directions) are located. A smoothing procedure is used to remove the maxima and minima produced by noise, thus obtaining the essential critical points. The level sequence is calculated, as explained later, producing a number sequence which hopefully identifies the character as belonging to a class. This class is found by searching the sequence obtained in a database. If no match is found another binary image is produced and the procedure repeated. Two or three threshold levels are tried (N=2 or N=3), before the character is considered as unknown. A training set of approximately 4000 characters, extracted from British number plates, has been used to build the databases for classification. The classification performance has been tested with a set of 1172 characters, extracted from "problem" number plates.

 Preliminary speed tests have been conducted on a IBM-PC 486DX4-100, in order to get an idea of the speed of the critical points technique. The average time to decode a character has been measured, using the training database referred to above.

 The smoothing procedure used to eliminate critical points produced by noise and obtain the essential critical points is based on the heuristics that critical points produced by noise are relatively close together (their coordinates differ by less than a percentage of the total height of the character). Fig. 7 shows an example of the critical points of an "A" character, before and after smoothing.

Fig. 7 - Example of character before (a) and after smoothing (b).

 The Y-type level sequence is a numerical sequence derived from the critical points distribution in the following way. Each point is given a level number, which is the number of critical points with higher co-ordinate. Then a sequence is formed by reading the level numbers of the critical points, beginning from the point with the higher coordinate. An example is shown is Fig. 8, where the Y-type sequence is "043412". The technique is also used for the X axis, producing what the authors call the X-type level sequence.

 It is important to mention that the critical points technique, as implemeted by Barroso et al, classifies a character into a class of characters with identical critical point sequences. Using only the level sequence, this class has between one and six characters. An example is "UVWY34". Tests carried out in a database of 1172 characters gave the results shown in the table of Fig. 9. These results show that 6.4% of the characters have been classified into a class of one character (effectively they have been recognised), 19.9% have been classified into a class of 2 characters, etc.. It is worth noting that there are no characters which have been misclassified or not recognised.

Fig. 8 - Levels of the critical points for the Y-type sequence ("043412").

 Two other features are used to produce smaller classification classes: the white/black points sequence and the metric sequence. Other sequences have been tried, but they were abandoned because of the poor results obtained when using them.

Fig. 9 - Results of the tests for the level sequence.

 The white/black points sequence is derived by classifying every essential critical point into white or black. As every critical point is a local maxima or minima of the object (black) or of the background (white), this can be used to classify it into one of four classes:

• white minimum (wm),
• white maximum (wM),
• black minimum (bm),
• black maximum (bM).

 In the example of Fig. 10, going in the clockwise direction, 1=bM, 3=bm, 2=wM, 6=bm, 4=bM and 5=wm. The white/black sequence is then "black, black, white, white, black, white", which is codified by the number of critical points of the same colour which appear in the sequence, i.e. "2211".

Fig. 10 - Critical points for the Y-type white/black sequence ("2211").

 The results of applying the white/black sequence to the database referred to before are shown in Fig. 11.

Fig. 12 shows the results of using the intersection of the sets obtained using the level sequence and the white/black sequence. In the cases where the white/black sequence is not recognised, instead of using the intersection, the level sequence set is taken as the answer.

Fig. 11 - Results of the tests for the white/black sequence.

Fig. 12 - Results of the tests for the combination (intersection of potential answer sets) of the level sequence and white/black sequence.

 Another way of reducing the size of the classes to which a character belongs consists of using the metric sequence. The metric sequence is used only to help resolve clashes, and never by itself. The idea is simply to characterise the overall shape of the character by taking some measures in relation to some critical points. Fig. 13 illustrates the idea, showing that it can easily help in resolving the ambiguity between the letters "J, L, T".

Fig. 13 - Illustration of the meaning of the metric sequence.

 The results of combining the three sequences mentioned earlier are shown in Fig. 14.

Fig. 14 - Results of the tests for the combination of the three sequences.

 The results which have been presented above are shown graphically in Fig. 15.

 The combination of the critical points technique with the template matching technique used before leads to good results. The idea is simply to perform template matching with the templates which have been identified by the critical points technique as potential candidates. The template matching technique has been used in isolation to classify the character images used in the previous tests. The size of the templates used was 10x14. Fig. 16 shows the results of these tests. The same figure also shows the results of using the critical points technique and the two techniques together. It is worth noting that the combination of the two techniques uniquely identifies a character, while the critical points technique only identifies a character as belonging to a class. The combined technique should be refined in order to take advantage of the reduced number of possibilities of classification for each image letter.

Fig. 15 - Results of the tests (no recognition and misclassification are not shown).

Fig. 16 - Results of the tests which compare the critical points and the template matching techniques, and the combination of both.

 The results of the speed tests, performed in a IBM compatible Pentium 180MHz, are shown in Fig. 17. The time taken to compare a character with the 35 templates in the database is not much larger than the time taken to compare it with the templates selected with the critical points technique. For this reason a different template matching scheme has been tried, where the templates are built by subsampling the images of the characters. The results of the speed tests with this scheme are shown is Fig. 18.

Fig. 17 - Critical points and template matching speed tests.

 Using the second method the classification accuracy does not vary significantly.

Fig. 18 - Critical points and template matching speed tests.

CONCLUSIONS AND FUTURE WORK

A method to locate the number plate area in car images has been described. The method is based in the observation that an horizontal cross section of the car image shows a clear "signature" when the cross section cuts the number plate area. The tests which have been conduced to evaluate the proposed method indicate that the method is both robust and fast, which makes it suitable for real-time implementations.

 A technique to segment the characters in the number plate area of the car image has been developed, based in a technique proposed by Lu [9]. The method is fast, but its robustness strongly depends on the OCR engine. This is so because the segmentation is thought to be good when the recognition module correctly recognises the segmented areas.

 An accurate and fast method to build an OCR engine for number plate reading has been described. It is based in the critical points method and uses template matching to disambiguate between characters which were pre-classified in the same class.

 These three components are essential ingredients to build a number plate reading system and the integration of these components in the previous number plate system is under way.

 Further work will concentrate in improving the controller and the OCR engine. Because we are now able to have enough speed in the various steps of the process, these steps can be repeated to improve the accuracy of the system. The controller has to be improved and the OCR engine should be refined in order to better deal with noise (non-character shapes) and with ambiguous situations, like "D,0" and "B,8".

 Some preliminary tests of a neural network based technique for character classification indicate that "B" and "8" characters can be uniquely classified with good accuracy in around 40% of the cases. Further work along this line is necessary.

 Acknowledgements

 The authors would like to thank the students of Electrical Engineering António Viana, Hugo Fiuza, Argentina Leite, Luís Carvalho, Pedro Antunes e Alberto Vasconcelos for their collaboration in the number plate project.

 REFERENCES

[1]  Ali A T & Dagless E L, “Computer Vision-Aided Road Traffic Monitoring”, Proc. ISATA 24th. Int. Conf. Road Transport Informatics (RTI) & Intelligent Vehicle-Highway Systems (IVHS), Florence, Italy, pp.55-61, May 1991.

[2]Ali A T, Bulas-Cruz J & Dagless E L, “Vision Based Road Traffic Data Collection”, Proc. ISATA 26th International Conference, (ATT & IVHS), Aachen, Germany, Sept. (1993).

[3] Barroso J, “Identificação Automática de Placas de Matrícula Automóveis”, Tese de Mestrado em Engenharia Electrónica e Telecomunicações , Universidade de Aveiro, Dezembro (1995).

[4] Barroso J, Bulas-Cruz J, Rafael A & Dagless L, “Identificação Automática de Placas de Matrícula Automóveis”, Proc. 4.ªas Jornadas Luso-Espanholas de Engenharia Electrotécnica, Porto, Junho (1995).

[5] Bulas-Cruz J, “Image Processing Applications using a Transputer-based System”, PhD Thesis, University of Bristol, UK (1995).

[6] Dagless E L & Ali A T, "Real-Time Vision Aided Traffic Monitoring'', Proc. ACEP '92 Workshop, Borowice, Poland, April (1992).

[7] Inigo R M, "Traffic Monitoring and Control using Machine Vision: A Survey'', IEEE Transaction on Industrial Electronics, Vol. IE-32, No. 3, August (1985), pp.177-185.

[8] Lotufo R A, Morgan A D, Johnson A S and Thomas B T (1990). “A Transputer Based Automatic Number-Plate Recognition System”. Proc. of the 2nd Int. Conf. on Applications of Transputers, University of Southampton, July (1990).

[9] Lu, Y,  “Machine printed character segmenation”, Pattern Recognition, vol. 28, n. 1, pp 67-80, Elsevier Science Ltd, UK, 1995.

[10] Shchepin E V & Nepomnyashchii G M, "Character Recognition via Critical Points'', International Journal of Imaging Systems and Technology, vol.3 (1991), pp. 213-221.

[11] Shchepin E V & Nepomnyashchii G M, "On the Method of Critical Points in Character Recognition'', Proc. 5th International Conference of Computerr Analysis of Images and Patterns, Budapest, Sept. (1993), Lecture Notes in Computer Science, Springer-Verlag, pp. 594-598.

[12] Storer R, Milford D J, Bulas-Cruz J & Dagless E L, "Developing Embedded Applications in an Array of Specialised Transputer Modules'', Proc. WOTUG, Bristol, March (1994).