Contents 1 Introduction
In this paper, we propose a method of automatic hardware implementation of a particular decision rule. This paper focuses mainly on high speed decisions (approximately 5 to 10ns per decision) which can be useful for hi-resolution image segmentation or pattern recognition tasks in very large image databases. Our work is designed in order to be easily integrated in a System-On-Chip, which can perform the full process: acquisition, feature extraction and classification. This paper focuses on the last part of this process. Our method is based on the well known Adaboost algorithm, which decision consists in a simple summation of signed numbers [1], [2]. The limited number of operations to be performed allows us to choose the fastest implementation, a fully parallel one. Moreover, the regular structure of the function can be automatically generated using a hardware description language such as VHDL, and thus can be implemented efficiently in FPGA. Many implementations of particular classifiers have been proposed, mainly based on neural networks [3], [4], [5]. However, the implementation of a classifier is not often optimum in terms of silicon area and performances, because of the general structure of the chosen algorithm. Moreover Adaboost is a powerful machine learning method that can be applied directly, without any modification to generate a classifier implementable in hardware, and a complexity/performance trade-off is natural in the framework: Adaboost learning constructs a set of classifier with increasing complexity gradually and better performance (lower crossvalidated error). In order to follow real-time processing and cost constraint, we have to minimise the test error while minimising the hardware implementation cost and maximise the decision speed. The maximum speed will be obtained using a full parallel implementation. The cost has been estimated considering FPGA as the hardware target. The advantage of these components is mainly their reconfigurability [6] [7]. Using reconfigurable architecture, it is possible to integrate the constant values in the design of the decision function, optimising the number of cells used. We consider here the slice as the main elementary structure of the FPGA and the unit of , One component can contain a few thousand of these blocks. In the first part of this paper, we present the principle of the proposed method, reviewing the Adaboost algorithm and defining a family of weak classifiers suitable to hardware implementation, based on the general concept of hyperrectangle. We describe how it is possible to estimate the full parallel hardware implementation cost in terms of slices. In the second part, we present the algorithm allowing finding a hyperrectangle minimizing the classification error and allowing finding a good trade-off between performance and hardware implementation cost which we estimated. In the third part, results obtained on real databases coming from UCI repository are presented.
