# Introduction daboost learning algorithm, proposed by [1], and adapted by Viola and Jones for object detection [2] [3], is one of the most widely used algorithms in detection. This algorithm, based on Haar-like features (Fig. 2), achieves a high detection rate and we use it widely in face and pedestrian detection [4] [5] [6]. Haar-like feature classifiers trained by Adaboost algorithm are often incapable of finding rotated objects (Fig. 1). Many experts have proposed several solutions to fill this problem; Viola and Jones [2] [3] [4] used rotated positive examples during training, but this approach may give some inaccurate classifier. Another process adopted by several researchers [5] [7] [9] [10] consists of training several classifiers which specialize in certain angle intervals, this approach provides classifiers with appropriate accuracy and efficiency, but it makes the training computationally more expensive. In [7] [8] the image is physically or virtually rotated until the edges of the Haar-Like feature are aligned vertically or horizontally, this approach makes the detection computationally more expensive and also a loss of information when a set of pixels will be outside the region of interest. Fig. 1: Face detection with the latest method [12]; The algorithm is unable to detect a few rotated faces. In [12], we gave a solution allowing, firstly, to define, dynamically, a set of rotated Haar-Like Features by more than 50 angles formally expressed by ????????????ð??"ð??" (?? / ??) such that ?? and ?? are two integers. And secondly, to calculate, approximately, the rotated integral image of these rectangles to preserve the two advantages (speed and simplicity) for which Viola and Jones invented this technique for the first time. This method has shown a disadvantage, a little annoying, which consists of a false alarm rate, which is relatively high. In this paper, we propose a method that calculates the real Integral Image of a rotated rectangle based on the set of pixels, called key-points, forming each of its four segments. Indeed, we determine these points by adapting the algorithm for drawing a segment [13]. We organize this paper as follows: Section II presents some work done in the literature. In section III we will propose our technique concerning the quickly integration of a rotated rectangle. Section IV explores the results obtained by our two experiments carried out for the case of face detection. In section V, we will give a summary of our work, some conclusions, and perspectives. # II. # Related Work The technique of the Integral Image, strongly associated with the famous algorithm of Viola and Jones [2], is a technique that goes back to the year 1984 when Crow [16] introduced it, for the first time, in computer graphics. Its use in computer vision began in 2001 when Viola and Jones used it to calculate the integral of the rectangular filters called HaarLike features, shown in Fig. 2 (a), considered as one of the pillars of their realtime face detection algorithm. Therefore, most researchers have widely used and developed this technique to solve the problems related to the detection of objects, including faces detection [2][7], pedestrian detection [4][6], etc. Let ?? be an image of dimension ?? × ??, ?? (??, ??) is the intensity of the pixel (??, ??) of the image ??. The Integral Image is another image ???? such that for each pixel (??, ??): (see Fig. 2(b)). (1) Therefore, the integration of each axis-aligned (parallel to the axes of the image coordinate system) rectangle ?? = [(??, ??), ??, ?] is calculated only in four references: (see Fig. 2(c)) ????(??) = ????(?? + ??, ?? + ?) ? ????(??, ?? + ?) ? ????(?? + ??, ??) + ????(??, ??)(2) As (??, ??) is the upper left corner of ??, ?? and ? represent, respectively, its width and height. In the rest of this article, this type of rectangle is called a normal rectangle. This technique was then the subject of several improvements, in order to detect rotated objects in an image. Indeed, several works have chosen to feed the original set of HaarLike features, initially proposed by Viola and Jones (Fig. 2 (a)), by others which are rotated by a variety of angles and offering an ease of calculating their integration. In particular, Lienhart et al. [5] who introduced a 45° tilted integral image. Then, Barczak et al. [7] and Du et al. [8] retained the same technique of Viola and Jones to incorporate rotated features by 26.57° and 63.5°. Then Barczak and Mossom [9] tried to generalize this technique for angles having a tangent in the form of a rational number 1/?? or ??/1. Another work is that of Ramirez et al. [10], who introduced the asymmetric Haar Features. Pham et al. [14] have developed a technique called Polygonal integration to divide a polygon into a set of axis-aligned rectangles (normal rectangles), then determine its integration according to those of these rectangles. Doretto et al. [15] gave an extension of formula 1 to compute the integral of a domain ?? ? ? ?? , which consists of a finite unification of axis-aligned rectangles. Formally, a rotated rectangle is defined by a sixelement vector as shown by the following formula: ??(?, ?) = ? ?(? ? , ? ? ) ???? ???? ? ? ? = (?, ? ? , ? ? , ? ? , ? ? , ?) ? ??? × (? * ) 4 × ? * The set of rotated rectangles ? is divided into two categories ??? and ???. These two categories are defined by formulas 4 and 5. ??? = {?? ? ?| (???? ? ???? ???? ???? ? ????) ???? (???? ? ???? ???? ???? ? ????)} (4) ??? = {?? ? ?| (???? > ???? ???? ???? < ????) ???? (???? < ???? ???? ???? > ????)}(5) Knowing that ??, ?? and ?? are other vertices of the rotated rectangle ??, as shown in Fig. 3. # b) The integration of a rotated rectangle The principle of our method consists in dividing the rectangle that encapsulates ?? into five normal rectangles called ??i, as shown in Fig. 4 and 5. The result of the intersection of ?? with the rectangles ??i is the right triangle called ???? . We illustrated this definition in Fig. 5. The following equation gives the identification of these triangles: ???? = ?? ? ???? for ?? ? {1,2,3,4}. Knowing that the integral of a rotated rectangle is: (6) (7) Indeed, we can divide a triangle ?? into several normal rectangles ??i (axis-aligned rectangles) (Fig. 6). The two vertices (????, ????) of each rectangle ??i crossed by the hypotenuse of the triangle ?? are named key points. The set of these key points, ????, are found by applying the Segment Drawing Rule (SDR) [13]. In fact, ???? = ? ? ?? such that: ? = ???1 ? ???2 ? ???3 ? ???4 ?? = ????1 ? ????2 ? ????3 ? ????4 Knowing that ????? and ?????? are, respectively, the set of key points ???? and ???? of the triangle ????. Mathematically speaking, let ð??"ð??": ? ? ???? ?? be a function that determines the vector ???? = (??0, . . , ???? ) of the key points, for each rectangle ?? of ??, therefore: ð??"ð??"(??) = ???? = (??0, . . , ???? ). And ð??"ð??": ???? ?? ? ? a function that computes the Integral Image from a vector of points. In other words, ð??"ð??"(????) = ??(??). Indeed, we define the function I as a function composed of ð??"ð??" and ð??"ð??": ??(??) = ð??"ð??"??ð??"ð??"(??). Therefore, the method proposed in this article, to calculate the Integral Image of a rectangle, is based on three essential tasks: ? Determine the rule for drawing a segment (SDR); ? Determine all the key points (????, ????) of the rectangle ??; ? Calculate the integral image of r according to its key points. # c) Triangle integration The major problem of the computation part of the integral of a right triangle ?? is that each slope of its hypotenuse presents different difficulties. Is very difficult to integrate a line with an irrational slope because at the level of each pixel intersected by the line, the partition model is always different. For our case, the slope of the hypotenuse of the triangle t is rational. Specifically, a line with a rational slope produces a finite number of pixel partition models. Consider, for example, a positive slope ?? of a line ??, when this line crosses a set of pixels, the model of partitions of the pixels is repeated at each ?? pixels intersected by the line ?? [14]. This repetition is the key of our solution proposed in this article. More generally, let ?? = ??/?? (??, ?? ? ?? ?????? ?? ? 0) be a rational slope, the integer vector ???? = (??, ??) / ð??"ð??"???? (| ?? |, | ?? |) represents a 2D interval such as the partition model is periodic. Otherwise, the partition model at any pixel (??, ??) is the same at (??, ??) + ????. To determine the pixels traversed by a line ??, we used the Bresenham algorithm [13], which makes it possible to define the Segment Drawing Rule (SDR). Segment Drawing Rule (SDR): Based on the Bresenham algorithm [13], which allows determining all the pixels forming a segment, we have defined the rule allowing to go through all the pixels forming the hypotenuse of a iangle ?? (Fig. 6 (a)). This rule ???????? is a vector formally defined as follows: ???????? = (??1, ??2, ? , ????) such that ?? represents the number of floors which is equal to ??????(???, ???) and ???? that of pixels for the ????? floor; The authors of [14] have shown that the number of pixels, denoted np, traversed by the hypotenuse of the right triangle ?? for each partition is ???? = | ?? ?| + | ??? |? 1, indeed, we easily deduce that the total number of pixels traversed by the hypotenuse of ?? is: ???? ? ?????1 = ???? ?????? ??0 = ???? ; ? ???? = ??. Therefore, the Integral Image of a triangle ?? will be the sum of those of all rectangles ????, formally: Indeed, the Integral Image of a normal rectangle ????, ????(????), according to formula 2 is: Such as the function ???? represents the Integral Image of a given pixel. Therefore, from equation 8 and 9, we deduce the formula to calculate the Integral Image of a triangle ?? (case of triangle ??1): Knowing that for ??1: ???? = ?? ???? ???? = ??. According to this principle, we deduce the formulas for calculating the integral image of all types of triangles of the rotated rectangle ??: (Fig. 5) # d) Rotated Rectangle Integration In the end and according to equation 7, formula 15 shows the Integral Image of a rotated rectangle. That of the rectangle of the medium ??5 is easily found via the equation 2. Knowing that ?? is the number of floors of the hypotenuses of triangles ??1 and ??2 and ?? that of triangles ??2 and ??4. So, the total number of key points ???? of a rotated rectangle ??, adding the two points ?? and ??, is ?? = 4 (?? + ??) ? 2. In general, the Integral Image of a rotated rectangle ?? is: Such as ???? is the parity corresponding to the pixel ????. Fig. 7 shows the variation of the sign ???? according to the type of the triangle and the key point (+1, for ??, and ?1 for ??) Algorithm 2 illustrates the process proposed to find these points for the two segments [????] and [????] with the direction of the path ?? = ???????????????? ? ????ð??"ð??"???. Indeed, to compute the Integral Image of a rotated rectangle, we need 4 (?? + 1) ? 2 access to the memory, which means that the associated algorithm has a linear complexity O(n). In practice, the worst-case complexity varies between 40 and 74 operations for only 12% of cases. The complexity in the best case varies between 6 and 20 operations for more than 45% of cases, and 23 on average for all cases. ?(?) = ??(?) ? ??(?)) ? ? ??(? 1? ) ??1 0 + ? ??(? 1? ??2 0 ) ? ? ??(? 2? ??1 0 ) + ? ??(? 2? ) ??2 0 + ? ??(? 3? ) ??1 0 ? ? ??(? 3? ??2 0 ) + ? ??(? 4? ??1 0 ) ? ? ??(? 4? ??2 0 )(15)?(?) = ? ? ? * ??(? ? ??1 0 ) /? ? ? {+1, ?1}(16) IV. # Experiences During the learning phase, we adopted the use of two of the most known and most available databases in our field, which are: UMIST Face Database [17] and CMU-PIE Face Database [18]. The base of faces UMIST consists of 564 images -cut and trimmed -of 20 people (mixed race, kind, and appearance) [17]. In this database we represent each person's frontal profile by a multitude of images illustrating a range of poses from different angles; their number is about 19 up to 36 for each person. These images are sampled, in our experience, up to a resolution of 20 × 20. Their number is 6900 images of faces. The CMU-PIE database contains 41,368 images obtained from 68 people. These images were taken in the CMU 3D room using a set of 13 high-quality color cameras synchronized with 21 flashes. The resulting RGB color images are 640 × 486 in size. These images are sampled, in our experiment, up to a resolution of 18 × 20. And for the training of our detector, we used 9996 images of faces. For the test phase, we used the standard MIT + CMU base which contains 117 images with 511 faces. The result of our work is the creation of two detectors UMIST-Detector and PIE-Detector from the process of learning using the two image bases, respectively, UMIST and PIE CMU described above. The learning phase uses more than 300,000 features (or weak classifiers) divided into two types: normal and rotated. The storage of this large number of features took on a large amount of memory. The result of this phase is a detector composed of a group of features selected by the AdaBoost algorithm. For each feature selected, it takes about 3 to 4 hours -sometimes more -calculating time using an HP Notebook PC with a 2.6 GHz frame rate and 4 GB of memory. This slowness of learning was considered a major drawback of the Viola & Jones method. The Viola-Jones detector contains 4297 features distributed over 32 stages, as is presented in the article of its authors [2][3]. The difference in the number of weak classifiers of our detectors and that of Viola and Jones is because we use, at most of the original features, those rotated by different angles. Table I shows the numbers of normal and rotated features selected by AdaBoost for each experiment, compared by the number obtained by Viola and Jones. Indeed, this added value has allowed us to achieve good results. These results clearly show that our detectors have correct detection rates greater than or nearly equal to those reported by Viola-Jones. UMIST-Detector has a detection accuracy of up to 97.8%, and this amounts to the fact that the images of the UMIST database are better pre-processed and standardized at the level of illumination, rotation of faces, different human races, etc. With PIE-Detector the detection rate cannot exceed the 95.9% threshold. To have performance tests comparable to those performed by Viola & Jones and Rowly [2][3] [11], we used the MIT-CMU test database, which consists of 117 images and 511 faces. Viola and Jones used 130 images and 507 faces. A difference that we neglected because most of the images were the same or have undergone some slight modifications. Fig. 8 illustrates these results as a ROC. The results are generally better, especially those obtained by Viola and Jones. Our two detectors have lower false alarm rates than the other methods; 28% for the first experience and 31% for the second. By using a 2.3 GHz core i3 and a 4 GB memory capacity, our detectors can scan an image of 252 × 426 pixels in about 0.9 seconds with a scaling factor of 1.2. what makes them a little bit slow compared to that of Viola and Jones (0.7 seconds to scan an image of 384 × 288), and this is mainly due to the large number of weak classifiers used by our method. The average speed to determine all the key points for each rotated feature does not exceed 62.4 ?s. V. # Conclusion In this work, we have proposed a simple, and effective method to integrate a rectangle rotated by any angle of rotation. The principle of this technique is to find specific pixels (key points) for each segment of the rectangle, then calculate the sum of its pixels according to these points. To find these points, we adopted the Bresenham algorithm for drawing a segment. This technique applied to the Viola and Jones algorithm with rotated HaarLike features added to the core set has proven efficiency and a high detection rate for detecting rotated faces in an image. In fact, we performed two experiments using, for the training phase, two image databases known in the literature, notably UMIST and CMU-PIE, and the MIT-CMU database for the test phase. Our perspective is to apply this technique for real-time detection and also for face and emotion recognition. 2![Fig. 2: (a) Haar-Like basic features, used by Viola-Jones in [2]. (b) Integral Image (c) Calculation of the sum of the rectangle D with the Integral Image.](image-2.png "Fig. 2 :") 3![Fig. 3: Representation of a rotated rectangle. III. Fast Integration of the Rotated Haar-Like a) Rotated Haar-Like features A rotated Haar-Like feature is a rectangle rotated by a given angle. The rotated Haar-like features are based on the normal ones presented in [2]. In a scan window named ?????? -with ???????? as height and ???????? as width -a rotated rectangle is defined by its vertex ?? (????, ????), its rotation angle ?? and its rectangle encapsulating ??[??(???? ? ???? , ????), ?? = ???? + ????, ? = ???? + ???? ] as shown in Fig.3.](image-3.png "Fig. 3 :") 4![Fig. 4: Representation of a rotated rectangle of the category ??? by (a) and (b) and ??? by (c) and (d).](image-4.png "Fig. 4 :") 5![Fig. 5: A rotated rectangle divided into triangles.](image-5.png "Fig. 5 :") 4![?(?) = ? ??(? ? ) + ? × ?(? 5 ) / { ? = +1 ?ð??" ? ? ? ? ? = ?1 ?ð??" ? ? ? ? Global Journal of Computer Science and Technology Volume XX Issue I Version I Journals The Fast Integration of a Rotated Rectangle Applied to the Rotated Haar-like Features for Rotated Objects Detection (3) such that ??(??, ??) is the intensity of the pixel (??, ??) belonging to the rectangle ??. The exploitation of the integral image technique proposed by Viola and Jones [2] leads us to reformulate equation 6 in this form: such that: ??(??5) is the Integral Image of ??5 rectangle calculated according to the equation 2. ????(????) is the integration of the triangle ???? .](image-6.png "4 ?=1") 6![b) gives an example of these values. A floor is a set of ??i pixels aligned either vertically (??ð??"ð??" ?? < 45°) or horizontally (??ð??"ð??" ?? > 45°). The transition from one floor to another is done by moving a pixel to the right for sides [????] and [????] and left for [????] and[????]. A particular case is that of ?? = 45°, the number of pixels for each floor is always equal to 1, and the displacement can be done in both directions.Indeed, the Segment Drawing Rule (SDR) is the result of the function ??: ð?"?ð?"? ? ? ?? which takes in parameter a segment ?? and returns a vector.](image-7.png "Fig. 6 (") 6![Fig. 6: (a) Rule for drawing a segment, (b) Example of values for ?? = 16, ?? = 10. ???????? = (??1, ??2, ? , ????). ?? is the set of segments of a polygon; for our case, we are talking about a rectangle with four segments. Each segment is formally defined as follows: ?? = (???? , ????, ?? ? , ?? ? , ??, ??, ??), such that: ? ???? and ???? are, respectively, the starting point and the arrival point of the segment ??; ? ?? = gcd(|??|, |??|) is the number of partitions or repetitions of ????????; ? (?? ?, ???) = (??, ??) / ??; ? ?? = ??????(??, ??) = ??????(?? ? , ?? ? ) * ?? = ?? * ??: the number of floors composing the hypotenuse of the triangle;](image-8.png "Fig. 6 :") ![??. Therefore, to determine the SDR, algorithm 1 traverses (???? + ??) × ?? pixels.Integral image of a right triangle: As mentioned above, the principle of our method is based on the division of a triangle into k normal rectangles ????. A normal rectangle ???? is defined by the following quadruple: (see Fig.6 (a)) ???? = [????????????????+1] ð??"ð??"???? ??1, such us : ? ??1 is the triangle with the hypotenuse as segment [????], shown in Fig. 5; ? ??: Number of floors; ? ?? = 0,1, ? , ?? ? 1 ;](image-9.png "×") 1![Get SDR ?????ð??"? ? ? ? : ???????ð??" ????? (? ?? ?) ? (? ? , ? ? ) = (?, ?) / gcd(|?|, |?|) ??? (?, ?) = (? ? , ? ? ) ??? ??ð??"??? 2 ? ? = ???(? ? , ? ? ) number of floors ? ? ? = ????? ?ð??" ?????? ?? ??? ? ?? ð??"???? ??ð??"?ð??"?: ??? ð??"?? ??ð??"???? [??] ??? [??] ????????ð??"?????: ?(? ? , ? ? ) = ? ? + 1 ??: ??ð??" ? = 1 ?? ? ? 1 ?? ? = ? ? , ? ? = 0 ????? ? ? 0 ?? ? ? = ? ?? ? ?? ??ð??"???? (?? ?? ??) ??? ? ?????? ??????ð??"?? ???? ? ????????? ? ? ? ????????? ? ??ð??"? ? ? = ? ? 1 ? ? = ? ? + ?: number of rectangles ? ? . (8) ??(? ? ) = ??(? ? ) ? ??(? ?+1 ) ? ??(? ? ) + ??(? ? )](image-10.png "Algorithm 1 /") 1UMISTCMU-PIE VIOLA & JONESNormal410340754297Rotated642443930TOTAL1052784684297Our program was run for 21 days for the firstexperience and 15 days for the second. The firstdetector consists of 10527 features distributed over 53stages, and the second detector contains 8468 featuresspread over 46 stages. ( ) F © 2020 Global JournalsThe Fast Integration of a Rotated Rectangle Applied to the Rotated Haar-like Features for Rotated Objects Detection * A desicion-theoretic generalization of on-line learning and an application to boosting YFreund RSchapire Journal of Computer and System Sciences(JCSS) 55 1 1997 * Robust real-time object detection PViola MJones International Journal of Computer Vision (IJCV) 57 2 2001 * Rapid Object Detection Using a Boosted Cascade of Simple Features PViola MJones IEEE Computer Society Conference on Computer Vision and Pattern Recognition 2001 1 * Detecting pedestrians using patterns of motion and appearance PViola MJones DSnow International Journal of Computer Vision 63 2 July 2005 * An extended set of haar-like features for rapid object detection RLienhart JMaydt International Conference on IEEE 2002 1 * Pedestrian recognition in far-infrared images by combining boosting-based detection and skeleton-based stochastic tracking RMiyamoto HSugano HSaito Advances in Image and Video Technology Berlin Heidelberg Springer 2006 * Toward an Efficient Implementation of a Rotation Invariant Detector using Haar-Like Features AL CBarczak Proceedings of the IEEE/RSJ international conference on Intelligent robots and systems the IEEE/RSJ international conference on Intelligent robots and systemsNouvelle-Zélande, Dunedin 2005 * Rotated Haar-Like Features for Face Detection with In-Plane Rotation SDu NZheng QYou YWu MYuan JWu 12th International Conference Xi'an, China 2006. October 18-20. 2006 * Stream processing for fast and efficient rotated Haarlike features using rotated integral images CHMessom AL CBarczak IJISTA 7 1 2009 * Multi-Pose Face Detection With Asymmetric Haar Features GARamirez OFuentes 2008 WACV Mountain,CO * HARowley SBaluja * Neural networkbased face detection TKanade In IEEE Trans. Pattern Analysis and Machine Intelligence 20 1998 * A new approach to represent rotated haar-like features for objects detection MOualla ASadiq SMbarki Journal of Theoretical & Applied Information Technology (JATIT) 78 10th August 2015 * Algorithm for computer control of a digital plotter JackEBresenham IBM Systems Journal 4 1 1th January 1965 * Fast Polygonal Integration and Its Application in Extending Haar-like Features to Improve Object Detection MTPham YGao VD DHoang TJCham proceeding of the IEEE conference on Computer Vision and Pattern Recognition eeding of the IEEE conference on Computer Vision and Pattern Recognition CVPR * Appearance-based person reidentification in camera networks: Problem overview and current approaches GDoretto TSebastian PTu JRittscher Journal of Ambient Intelligence and Humanized Computing Berlin / Heidelberg Springer 2011 * Summed-area tables for texture mapping FCrow 1984 84 * Characterizing Virtual Eigen signatures for General Purpose Face Recognition DBGraham NMAllinson NATO Advanced Study Institute, Face recognition: from theory to applications 1997 * ASI SERIES F COMPUTER AND SYSTEMS SCIENCES 163 1998 Springer * The CMU Pose, Illumination, and Expression (PIE) Database of Human Faces TSim SBaker MBsat Transactions on Pattern Analysis and Machine Intelligence 2003 25