1/*M///////////////////////////////////////////////////////////////////////////////////////
2//
3//  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4//
5//  By downloading, copying, installing or using the software you agree to this license.
6//  If you do not agree to this license, do not download, install,
7//  copy or use the software.
8//
9//
10//                        Intel License Agreement
11//                For Open Source Computer Vision Library
12//
13// Copyright (C) 2000, Intel Corporation, all rights reserved.
14// Third party copyrights are property of their respective owners.
15//
16// Redistribution and use in source and binary forms, with or without modification,
17// are permitted provided that the following conditions are met:
18//
19//   * Redistribution's of source code must retain the above copyright notice,
20//     this list of conditions and the following disclaimer.
21//
22//   * Redistribution's in binary form must reproduce the above copyright notice,
23//     this list of conditions and the following disclaimer in the documentation
24//     and/or other materials provided with the distribution.
25//
26//   * The name of Intel Corporation may not be used to endorse or promote products
27//     derived from this software without specific prior written permission.
28//
29// This software is provided by the copyright holders and contributors "as is" and
30// any express or implied warranties, including, but not limited to, the implied
31// warranties of merchantability and fitness for a particular purpose are disclaimed.
32// In no event shall the Intel Corporation or contributors be liable for any direct,
33// indirect, incidental, special, exemplary, or consequential damages
34// (including, but not limited to, procurement of substitute goods or services;
35// loss of use, data, or profits; or business interruption) however caused
36// and on any theory of liability, whether in contract, strict liability,
37// or tort (including negligence or otherwise) arising in any way out of
38// the use of this software, even if advised of the possibility of such damage.
39//
40//M*/
41
42/* Haar features calculation */
43
44#include "_cv.h"
45#include <stdio.h>
46
47/* these settings affect the quality of detection: change with care */
48#define CV_ADJUST_FEATURES 1
49#define CV_ADJUST_WEIGHTS  1
50
51typedef int sumtype;
52typedef double sqsumtype;
53
54typedef struct MyCvHidHaarFeature
55	{
56		struct
57		{
58			sumtype *p0, *p1, *p2, *p3;
59			int weight;
60		}
61		rect[CV_HAAR_FEATURE_MAX];
62	}
63	MyCvHidHaarFeature;
64
65
66typedef struct MyCvHidHaarTreeNode
67	{
68		MyCvHidHaarFeature feature;
69		int threshold;
70		int left;
71		int right;
72	}
73	MyCvHidHaarTreeNode;
74
75
76typedef struct MyCvHidHaarClassifier
77	{
78		int count;
79		//CvHaarFeature* orig_feature;
80		MyCvHidHaarTreeNode* node;
81		float* alpha;
82	}
83	MyCvHidHaarClassifier;
84
85
86typedef struct MyCvHidHaarStageClassifier
87	{
88		int  count;
89		float threshold;
90		MyCvHidHaarClassifier* classifier;
91		int two_rects;
92
93		struct MyCvHidHaarStageClassifier* next;
94		struct MyCvHidHaarStageClassifier* child;
95		struct MyCvHidHaarStageClassifier* parent;
96	}
97	MyCvHidHaarStageClassifier;
98
99
100struct MyCvHidHaarClassifierCascade
101{
102    int  count;
103    int  is_stump_based;
104    int  has_tilted_features;
105    int  is_tree;
106    double inv_window_area;
107    CvMat sum, sqsum, tilted;
108    MyCvHidHaarStageClassifier* stage_classifier;
109    sqsumtype *pq0, *pq1, *pq2, *pq3;
110    sumtype *p0, *p1, *p2, *p3;
111
112    void** ipp_stages;
113};
114
115
116const int icv_object_win_border = 1;
117const float icv_stage_threshold_bias = 0.0001f;
118
119static int myis_equal( const void* _r1, const void* _r2, void* )
120{
121    const CvRect* r1 = (const CvRect*)_r1;
122    const CvRect* r2 = (const CvRect*)_r2;
123    int distance = cvRound(r1->width*0.2);
124
125    return r2->x <= r1->x + distance &&
126	r2->x >= r1->x - distance &&
127	r2->y <= r1->y + distance &&
128	r2->y >= r1->y - distance &&
129	r2->width <= cvRound( r1->width * 1.2 ) &&
130	cvRound( r2->width * 1.2 ) >= r1->width;
131}
132
133static void
134myicvReleaseHidHaarClassifierCascade( MyCvHidHaarClassifierCascade** _cascade )
135{
136    if( _cascade && *_cascade )
137    {
138        /*CvHidHaarClassifierCascade* cascade = *_cascade;
139		 if( cascade->ipp_stages && icvHaarClassifierFree_32f_p )
140		 {
141		 int i;
142		 for( i = 0; i < cascade->count; i++ )
143		 {
144		 if( cascade->ipp_stages[i] )
145		 icvHaarClassifierFree_32f_p( cascade->ipp_stages[i] );
146		 }
147		 }
148		 cvFree( &cascade->ipp_stages );*/
149        cvFree( _cascade );
150    }
151}
152
153/* create more efficient internal representation of haar classifier cascade */
154static MyCvHidHaarClassifierCascade*
155myicvCreateHidHaarClassifierCascade( CvHaarClassifierCascade* cascade )
156{
157    CvRect* ipp_features = 0;
158    float *ipp_weights = 0, *ipp_thresholds = 0, *ipp_val1 = 0, *ipp_val2 = 0;
159    int* ipp_counts = 0;
160
161    MyCvHidHaarClassifierCascade* out = 0;
162
163    CV_FUNCNAME( "icvCreateHidHaarClassifierCascade" );
164
165    __BEGIN__;
166
167    int i, j, k, l;
168    int datasize;
169    int total_classifiers = 0;
170    int total_nodes = 0;
171    char errorstr[100];
172    MyCvHidHaarClassifier* haar_classifier_ptr;
173    MyCvHidHaarTreeNode* haar_node_ptr;
174    CvSize orig_window_size;
175    int has_tilted_features = 0;
176    int max_count = 0;
177
178    if( !CV_IS_HAAR_CLASSIFIER(cascade) )
179        CV_ERROR( !cascade ? CV_StsNullPtr : CV_StsBadArg, "Invalid classifier pointer" );
180
181    if( cascade->hid_cascade )
182        CV_ERROR( CV_StsError, "hid_cascade has been already created" );
183
184    if( !cascade->stage_classifier )
185        CV_ERROR( CV_StsNullPtr, "" );
186
187    if( cascade->count <= 0 )
188        CV_ERROR( CV_StsOutOfRange, "Negative number of cascade stages" );
189
190    orig_window_size = cascade->orig_window_size;
191
192    /* check input structure correctness and calculate total memory size needed for
193	 internal representation of the classifier cascade */
194    for( i = 0; i < cascade->count; i++ )
195    {
196        CvHaarStageClassifier* stage_classifier = cascade->stage_classifier + i;
197
198        if( !stage_classifier->classifier ||
199		   stage_classifier->count <= 0 )
200        {
201            sprintf( errorstr, "header of the stage classifier #%d is invalid "
202					"(has null pointers or non-positive classfier count)", i );
203            CV_ERROR( CV_StsError, errorstr );
204        }
205
206        max_count = MAX( max_count, stage_classifier->count );
207        total_classifiers += stage_classifier->count;
208
209        for( j = 0; j < stage_classifier->count; j++ )
210        {
211            CvHaarClassifier* classifier = stage_classifier->classifier + j;
212
213            total_nodes += classifier->count;
214            for( l = 0; l < classifier->count; l++ )
215            {
216                for( k = 0; k < CV_HAAR_FEATURE_MAX; k++ )
217                {
218                    if( classifier->haar_feature[l].rect[k].r.width )
219                    {
220                        CvRect r = classifier->haar_feature[l].rect[k].r;
221                        int tilted = classifier->haar_feature[l].tilted;
222                        has_tilted_features |= tilted != 0;
223                        if( r.width < 0 || r.height < 0 || r.y < 0 ||
224						   r.x + r.width > orig_window_size.width
225						   ||
226						   (!tilted &&
227                            (r.x < 0 || r.y + r.height > orig_window_size.height))
228						   ||
229						   (tilted && (r.x - r.height < 0 ||
230									   r.y + r.width + r.height > orig_window_size.height)))
231                        {
232                            sprintf( errorstr, "rectangle #%d of the classifier #%d of "
233									"the stage classifier #%d is not inside "
234									"the reference (original) cascade window", k, j, i );
235                            CV_ERROR( CV_StsNullPtr, errorstr );
236                        }
237                    }
238                }
239            }
240        }
241    }
242
243    // this is an upper boundary for the whole hidden cascade size
244    datasize = sizeof(MyCvHidHaarClassifierCascade) +
245	sizeof(MyCvHidHaarStageClassifier)*cascade->count +
246	sizeof(MyCvHidHaarClassifier) * total_classifiers +
247	sizeof(MyCvHidHaarTreeNode) * total_nodes +
248	sizeof(void*)*(total_nodes + total_classifiers);
249
250    CV_CALL( out = (MyCvHidHaarClassifierCascade*)cvAlloc( datasize ));
251    memset( out, 0, sizeof(*out) );
252
253    /* init header */
254    out->count = cascade->count;
255    out->stage_classifier = (MyCvHidHaarStageClassifier*)(out + 1);
256    haar_classifier_ptr = (MyCvHidHaarClassifier*)(out->stage_classifier + cascade->count);
257    haar_node_ptr = (MyCvHidHaarTreeNode*)(haar_classifier_ptr + total_classifiers);
258
259    out->is_stump_based = 1;
260    out->has_tilted_features = has_tilted_features;
261    out->is_tree = 0;
262
263    /* initialize internal representation */
264    for( i = 0; i < cascade->count; i++ )
265    {
266        CvHaarStageClassifier* stage_classifier = cascade->stage_classifier + i;
267        MyCvHidHaarStageClassifier* hid_stage_classifier = out->stage_classifier + i;
268
269        hid_stage_classifier->count = stage_classifier->count;
270        hid_stage_classifier->threshold = stage_classifier->threshold - icv_stage_threshold_bias;
271        hid_stage_classifier->classifier = haar_classifier_ptr;
272        hid_stage_classifier->two_rects = 1;
273        haar_classifier_ptr += stage_classifier->count;
274
275        hid_stage_classifier->parent = (stage_classifier->parent == -1)
276		? NULL : out->stage_classifier + stage_classifier->parent;
277        hid_stage_classifier->next = (stage_classifier->next == -1)
278		? NULL : out->stage_classifier + stage_classifier->next;
279        hid_stage_classifier->child = (stage_classifier->child == -1)
280		? NULL : out->stage_classifier + stage_classifier->child;
281
282        out->is_tree |= hid_stage_classifier->next != NULL;
283
284        for( j = 0; j < stage_classifier->count; j++ )
285        {
286            CvHaarClassifier* classifier = stage_classifier->classifier + j;
287            MyCvHidHaarClassifier* hid_classifier = hid_stage_classifier->classifier + j;
288            int node_count = classifier->count;
289            float* alpha_ptr = (float*)(haar_node_ptr + node_count);
290
291            hid_classifier->count = node_count;
292            hid_classifier->node = haar_node_ptr;
293            hid_classifier->alpha = alpha_ptr;
294
295            for( l = 0; l < node_count; l++ )
296            {
297                MyCvHidHaarTreeNode* node = hid_classifier->node + l;
298                CvHaarFeature* feature = classifier->haar_feature + l;
299                memset( node, -1, sizeof(*node) );
300                node->threshold = (int)((classifier->threshold[l]) * 65536.0);
301                node->left = classifier->left[l];
302                node->right = classifier->right[l];
303
304                if( fabs(feature->rect[2].weight) < DBL_EPSILON ||
305				   feature->rect[2].r.width == 0 ||
306				   feature->rect[2].r.height == 0 )
307                    memset( &(node->feature.rect[2]), 0, sizeof(node->feature.rect[2]) );
308                else
309                    hid_stage_classifier->two_rects = 0;
310            }
311
312            memcpy( alpha_ptr, classifier->alpha, (node_count+1)*sizeof(alpha_ptr[0]));
313            haar_node_ptr =
314			(MyCvHidHaarTreeNode*)cvAlignPtr(alpha_ptr+node_count+1, sizeof(void*));
315
316            out->is_stump_based &= node_count == 1;
317        }
318    }
319
320    /*{
321	 int can_use_ipp = icvHaarClassifierInitAlloc_32f_p != 0 &&
322	 icvHaarClassifierFree_32f_p != 0 &&
323	 icvApplyHaarClassifier_32f_C1R_p != 0 &&
324	 icvRectStdDev_32f_C1R_p != 0 &&
325	 !out->has_tilted_features && !out->is_tree && out->is_stump_based;
326
327	 if( can_use_ipp )
328	 {
329	 int ipp_datasize = cascade->count*sizeof(out->ipp_stages[0]);
330	 float ipp_weight_scale=(float)(1./((orig_window_size.width-icv_object_win_border*2)*
331	 (orig_window_size.height-icv_object_win_border*2)));
332
333	 CV_CALL( out->ipp_stages = (void**)cvAlloc( ipp_datasize ));
334	 memset( out->ipp_stages, 0, ipp_datasize );
335
336	 CV_CALL( ipp_features = (CvRect*)cvAlloc( max_count*3*sizeof(ipp_features[0]) ));
337	 CV_CALL( ipp_weights = (float*)cvAlloc( max_count*3*sizeof(ipp_weights[0]) ));
338	 CV_CALL( ipp_thresholds = (float*)cvAlloc( max_count*sizeof(ipp_thresholds[0]) ));
339	 CV_CALL( ipp_val1 = (float*)cvAlloc( max_count*sizeof(ipp_val1[0]) ));
340	 CV_CALL( ipp_val2 = (float*)cvAlloc( max_count*sizeof(ipp_val2[0]) ));
341	 CV_CALL( ipp_counts = (int*)cvAlloc( max_count*sizeof(ipp_counts[0]) ));
342
343	 for( i = 0; i < cascade->count; i++ )
344	 {
345	 CvHaarStageClassifier* stage_classifier = cascade->stage_classifier + i;
346	 for( j = 0, k = 0; j < stage_classifier->count; j++ )
347	 {
348	 CvHaarClassifier* classifier = stage_classifier->classifier + j;
349	 int rect_count = 2 + (classifier->haar_feature->rect[2].r.width != 0);
350
351	 ipp_thresholds[j] = classifier->threshold[0];
352	 ipp_val1[j] = classifier->alpha[0];
353	 ipp_val2[j] = classifier->alpha[1];
354	 ipp_counts[j] = rect_count;
355
356	 for( l = 0; l < rect_count; l++, k++ )
357	 {
358	 ipp_features[k] = classifier->haar_feature->rect[l].r;
359	 //ipp_features[k].y = orig_window_size.height - ipp_features[k].y - ipp_features[k].height;
360	 ipp_weights[k] = classifier->haar_feature->rect[l].weight*ipp_weight_scale;
361	 }
362	 }
363
364	 if( icvHaarClassifierInitAlloc_32f_p( &out->ipp_stages[i],
365	 ipp_features, ipp_weights, ipp_thresholds,
366	 ipp_val1, ipp_val2, ipp_counts, stage_classifier->count ) < 0 )
367	 break;
368	 }
369
370	 if( i < cascade->count )
371	 {
372	 for( j = 0; j < i; j++ )
373	 if( icvHaarClassifierFree_32f_p && out->ipp_stages[i] )
374	 icvHaarClassifierFree_32f_p( out->ipp_stages[i] );
375	 cvFree( &out->ipp_stages );
376	 }
377	 }
378	 }*/
379
380    cascade->hid_cascade = (CvHidHaarClassifierCascade*)out;
381    assert( (char*)haar_node_ptr - (char*)out <= datasize );
382
383    __END__;
384
385    if( cvGetErrStatus() < 0 )
386        myicvReleaseHidHaarClassifierCascade( &out );
387
388    cvFree( &ipp_features );
389    cvFree( &ipp_weights );
390    cvFree( &ipp_thresholds );
391    cvFree( &ipp_val1 );
392    cvFree( &ipp_val2 );
393    cvFree( &ipp_counts );
394
395    return out;
396}
397
398#define calc_sum(rect,offset) \
399((rect).p0[offset] - (rect).p1[offset] - (rect).p2[offset] + (rect).p3[offset])
400
401
402CV_INLINE
403double myicvEvalHidHaarClassifier( MyCvHidHaarClassifier* classifier,
404								double variance_norm_factor,
405								size_t p_offset )
406{
407    int idx = 0;
408    do
409    {
410        MyCvHidHaarTreeNode* node = classifier->node + idx;
411        double t = node->threshold * variance_norm_factor;
412
413        double sum = calc_sum(node->feature.rect[0],p_offset) * node->feature.rect[0].weight;
414        sum += calc_sum(node->feature.rect[1],p_offset) * node->feature.rect[1].weight;
415
416        if( node->feature.rect[2].p0 )
417            sum += calc_sum(node->feature.rect[2],p_offset) * node->feature.rect[2].weight;
418
419        idx = sum < t ? node->left : node->right;
420    }
421    while( idx > 0 );
422    return classifier->alpha[-idx];
423}
424
425/*********************** Special integer sqrt **************************/
426
427int
428isqrt(int x)
429{
430	/*
431	 *	Logically, these are unsigned. We need the sign bit to test
432	 *	whether (op - res - one) underflowed.
433	 */
434
435	register int op, res, one;
436
437	op = x;
438	res = 0;
439
440	/* "one" starts at the highest power of four <= than the argument. */
441
442	one = 1 << 30;	/* second-to-top bit set */
443	while (one > op) one >>= 2;
444
445		while (one != 0) {
446			if (op >= res + one) {
447				op = op - (res + one);
448				res = res +  2 * one;
449			}
450			res /= 2;
451			one /= 4;
452		}
453	return(res);
454}
455
456#define NEXT(n, i)  (((n) + (i)/(n)) >> 1)
457
458unsigned int isqrt1(int number) {
459	unsigned int n  = 1;
460	unsigned int n1 = NEXT(n, (unsigned int)number);
461
462	while(abs((int)(n1 - n)) > 1) {
463		n  = n1;
464		n1 = NEXT(n, number);
465	}
466	while((n1*n1) > number) {
467		n1 -= 1;
468	}
469	return n1;
470}
471/***********************************************************************/
472
473CV_IMPL int
474mycvRunHaarClassifierCascade( CvHaarClassifierCascade* _cascade,
475						   CvPoint pt, int start_stage )
476{
477    int result = -1;
478    CV_FUNCNAME("mycvRunHaarClassifierCascade");
479
480    __BEGIN__;
481
482    int p_offset, pq_offset;
483	int pq0, pq1, pq2, pq3;
484    int i, j;
485    double mean;
486	int variance_norm_factor;
487    MyCvHidHaarClassifierCascade* cascade;
488
489    if( !CV_IS_HAAR_CLASSIFIER(_cascade) )
490        CV_ERROR( !_cascade ? CV_StsNullPtr : CV_StsBadArg, "Invalid cascade pointer" );
491
492    cascade = (MyCvHidHaarClassifierCascade*)_cascade->hid_cascade;
493    if( !cascade )
494        CV_ERROR( CV_StsNullPtr, "Hidden cascade has not been created.\n"
495				 "Use cvSetImagesForHaarClassifierCascade" );
496
497    if( pt.x < 0 || pt.y < 0 ||
498	   pt.x + _cascade->real_window_size.width >= cascade->sum.width-2 ||
499	   pt.y + _cascade->real_window_size.height >= cascade->sum.height-2 )
500        EXIT;
501
502    p_offset = pt.y * (cascade->sum.step/sizeof(sumtype)) + pt.x;
503    pq_offset = pt.y * (cascade->sqsum.step/sizeof(sqsumtype)) + pt.x;
504    mean = calc_sum(*cascade,p_offset) * cascade->inv_window_area;
505	pq0 = cascade->pq0[pq_offset];
506	pq1 = cascade->pq1[pq_offset];
507	pq2 = cascade->pq2[pq_offset];
508	pq3 = cascade->pq3[pq_offset];
509    variance_norm_factor = pq0 - pq1 - pq2 + pq3;
510    variance_norm_factor = variance_norm_factor * cascade->inv_window_area - mean * mean;
511    if( variance_norm_factor >= 0. )
512        variance_norm_factor = sqrt(variance_norm_factor);
513    else
514        variance_norm_factor = 1.;
515
516//    if( cascade->is_tree )
517//    {
518//        MyCvHidHaarStageClassifier* ptr;
519//        assert( start_stage == 0 );
520//
521//        result = 1;
522//        ptr = cascade->stage_classifier;
523//
524//        while( ptr )
525//        {
526//            double stage_sum = 0;
527//
528//            for( j = 0; j < ptr->count; j++ )
529//            {
530//                stage_sum += myicvEvalHidHaarClassifier( ptr->classifier + j,
531//													  variance_norm_factor, p_offset );
532//            }
533//
534//            if( stage_sum >= ptr->threshold )
535//            {
536//                ptr = ptr->child;
537//            }
538//            else
539//            {
540//                while( ptr && ptr->next == NULL ) ptr = ptr->parent;
541//                if( ptr == NULL )
542//                {
543//                    result = 0;
544//                    EXIT;
545//                }
546//                ptr = ptr->next;
547//            }
548//        }
549//    }
550//    else if( cascade->is_stump_based )
551    {
552        for( i = start_stage; i < cascade->count; i++ )
553        {
554            double stage_sum = 0;
555
556            if( cascade->stage_classifier[i].two_rects )
557            {
558                for( j = 0; j < cascade->stage_classifier[i].count; j++ )
559                {
560                    MyCvHidHaarClassifier* classifier = cascade->stage_classifier[i].classifier + j;
561                    MyCvHidHaarTreeNode* node = classifier->node;
562                    int t = node->threshold * variance_norm_factor;
563                    int sum = calc_sum(node->feature.rect[0],p_offset) * node->feature.rect[0].weight;
564                    sum += calc_sum(node->feature.rect[1],p_offset) * node->feature.rect[1].weight;
565                    stage_sum += classifier->alpha[sum >= t];
566                }
567            }
568            else
569            {
570                for( j = 0; j < cascade->stage_classifier[i].count; j++ )
571                {
572                    MyCvHidHaarClassifier* classifier = cascade->stage_classifier[i].classifier + j;
573                    MyCvHidHaarTreeNode* node = classifier->node;
574                    int t = node->threshold * variance_norm_factor;
575                    int sum = calc_sum(node->feature.rect[0],p_offset) * node->feature.rect[0].weight;
576                    sum += calc_sum(node->feature.rect[1],p_offset) * node->feature.rect[1].weight;
577                    if( node->feature.rect[2].p0 )
578                        sum += calc_sum(node->feature.rect[2],p_offset) * node->feature.rect[2].weight;
579
580                    stage_sum += classifier->alpha[sum >= t];
581                }
582            }
583
584            if( stage_sum < cascade->stage_classifier[i].threshold )
585            {
586                result = -i;
587                EXIT;
588            }
589        }
590    }
591//    else
592//    {
593//        for( i = start_stage; i < cascade->count; i++ )
594//        {
595//            double stage_sum = 0;
596//
597//            for( j = 0; j < cascade->stage_classifier[i].count; j++ )
598//            {
599//                stage_sum += myicvEvalHidHaarClassifier(
600//													  cascade->stage_classifier[i].classifier + j,
601//													  variance_norm_factor, p_offset );
602//            }
603//
604//            if( stage_sum < cascade->stage_classifier[i].threshold )
605//            {
606//                result = -i;
607//                EXIT;
608//            }
609//        }
610//    }
611
612    result = 1;
613
614    __END__;
615
616    return result;
617}
618
619#define sum_elem_ptr(sum,row,col)  \
620((sumtype*)CV_MAT_ELEM_PTR_FAST((sum),(row),(col),sizeof(sumtype)))
621
622#define sqsum_elem_ptr(sqsum,row,col)  \
623((sqsumtype*)CV_MAT_ELEM_PTR_FAST((sqsum),(row),(col),sizeof(sqsumtype)))
624
625
626CV_IMPL void
627mycvSetImagesForHaarClassifierCascade( CvHaarClassifierCascade* _cascade,
628									const CvArr* _sum,
629									const CvArr* _sqsum,
630									const CvArr* _tilted_sum,
631									double scale )
632{
633    CV_FUNCNAME("cvSetImagesForHaarClassifierCascade");
634
635    __BEGIN__;
636
637    CvMat sum_stub, *sum = (CvMat*)_sum;
638    CvMat sqsum_stub, *sqsum = (CvMat*)_sqsum;
639    CvMat tilted_stub, *tilted = (CvMat*)_tilted_sum;
640    MyCvHidHaarClassifierCascade* cascade;
641    int coi0 = 0, coi1 = 0;
642    int i;
643    CvRect equ_rect;
644    double weight_scale;
645
646    if( !CV_IS_HAAR_CLASSIFIER(_cascade) )
647        CV_ERROR( !_cascade ? CV_StsNullPtr : CV_StsBadArg, "Invalid classifier pointer" );
648
649    if( scale <= 0 )
650        CV_ERROR( CV_StsOutOfRange, "Scale must be positive" );
651
652    CV_CALL( sum = cvGetMat( sum, &sum_stub, &coi0 ));
653    CV_CALL( sqsum = cvGetMat( sqsum, &sqsum_stub, &coi1 ));
654
655    if( coi0 || coi1 )
656        CV_ERROR( CV_BadCOI, "COI is not supported" );
657
658    if( !CV_ARE_SIZES_EQ( sum, sqsum ))
659        CV_ERROR( CV_StsUnmatchedSizes, "All integral images must have the same size" );
660
661    if( CV_MAT_TYPE(sqsum->type) != CV_64FC1 ||
662	   CV_MAT_TYPE(sum->type) != CV_32SC1 )
663        CV_ERROR( CV_StsUnsupportedFormat,
664				 "Only (32s, 64f, 32s) combination of (sum,sqsum,tilted_sum) formats is allowed" );
665
666    if( !_cascade->hid_cascade )
667        CV_CALL( myicvCreateHidHaarClassifierCascade(_cascade) );
668
669    cascade = (MyCvHidHaarClassifierCascade*)_cascade->hid_cascade;
670
671    if( cascade->has_tilted_features )
672    {
673        CV_CALL( tilted = cvGetMat( tilted, &tilted_stub, &coi1 ));
674
675        if( CV_MAT_TYPE(tilted->type) != CV_32SC1 )
676            CV_ERROR( CV_StsUnsupportedFormat,
677					 "Only (32s, 64f, 32s) combination of (sum,sqsum,tilted_sum) formats is allowed" );
678
679        if( sum->step != tilted->step )
680            CV_ERROR( CV_StsUnmatchedSizes,
681					 "Sum and tilted_sum must have the same stride (step, widthStep)" );
682
683        if( !CV_ARE_SIZES_EQ( sum, tilted ))
684            CV_ERROR( CV_StsUnmatchedSizes, "All integral images must have the same size" );
685        cascade->tilted = *tilted;
686    }
687
688    _cascade->scale = scale;
689    _cascade->real_window_size.width = cvRound( _cascade->orig_window_size.width * scale );
690    _cascade->real_window_size.height = cvRound( _cascade->orig_window_size.height * scale );
691
692    cascade->sum = *sum;
693    cascade->sqsum = *sqsum;
694
695    equ_rect.x = equ_rect.y = cvRound(scale);
696    equ_rect.width = cvRound((_cascade->orig_window_size.width-2)*scale);
697    equ_rect.height = cvRound((_cascade->orig_window_size.height-2)*scale);
698    weight_scale = 1./(equ_rect.width*equ_rect.height);
699    cascade->inv_window_area = weight_scale;
700
701    cascade->p0 = sum_elem_ptr(*sum, equ_rect.y, equ_rect.x);
702    cascade->p1 = sum_elem_ptr(*sum, equ_rect.y, equ_rect.x + equ_rect.width );
703    cascade->p2 = sum_elem_ptr(*sum, equ_rect.y + equ_rect.height, equ_rect.x );
704    cascade->p3 = sum_elem_ptr(*sum, equ_rect.y + equ_rect.height,
705							   equ_rect.x + equ_rect.width );
706
707    cascade->pq0 = sqsum_elem_ptr(*sqsum, equ_rect.y, equ_rect.x);
708    cascade->pq1 = sqsum_elem_ptr(*sqsum, equ_rect.y, equ_rect.x + equ_rect.width );
709    cascade->pq2 = sqsum_elem_ptr(*sqsum, equ_rect.y + equ_rect.height, equ_rect.x );
710    cascade->pq3 = sqsum_elem_ptr(*sqsum, equ_rect.y + equ_rect.height,
711								  equ_rect.x + equ_rect.width );
712
713    /* init pointers in haar features according to real window size and
714	 given image pointers */
715    {
716#ifdef _OPENMP
717		int max_threads = cvGetNumThreads();
718#pragma omp parallel for num_threads(max_threads) schedule(dynamic)
719#endif // _OPENMP
720		for( i = 0; i < _cascade->count; i++ )
721		{
722			int j, k, l;
723			for( j = 0; j < cascade->stage_classifier[i].count; j++ )
724			{
725				for( l = 0; l < cascade->stage_classifier[i].classifier[j].count; l++ )
726				{
727					CvHaarFeature* feature =
728                    &_cascade->stage_classifier[i].classifier[j].haar_feature[l];
729					/* CvHidHaarClassifier* classifier =
730					 cascade->stage_classifier[i].classifier + j; */
731					MyCvHidHaarFeature* hidfeature =
732                    &cascade->stage_classifier[i].classifier[j].node[l].feature;
733					double sum0 = 0, area0 = 0;
734					CvRect r[3];
735#if CV_ADJUST_FEATURES
736					int base_w = -1, base_h = -1;
737					int new_base_w = 0, new_base_h = 0;
738					int kx, ky;
739					int flagx = 0, flagy = 0;
740					int x0 = 0, y0 = 0;
741#endif
742					int nr;
743
744					/* align blocks */
745					for( k = 0; k < CV_HAAR_FEATURE_MAX; k++ )
746					{
747						if( !hidfeature->rect[k].p0 )
748							break;
749#if CV_ADJUST_FEATURES
750						r[k] = feature->rect[k].r;
751						base_w = (int)CV_IMIN( (unsigned)base_w, (unsigned)(r[k].width-1) );
752						base_w = (int)CV_IMIN( (unsigned)base_w, (unsigned)(r[k].x - r[0].x-1) );
753						base_h = (int)CV_IMIN( (unsigned)base_h, (unsigned)(r[k].height-1) );
754						base_h = (int)CV_IMIN( (unsigned)base_h, (unsigned)(r[k].y - r[0].y-1) );
755#endif
756					}
757
758					nr = k;
759
760#if CV_ADJUST_FEATURES
761					base_w += 1;
762					base_h += 1;
763					kx = r[0].width / base_w;
764					ky = r[0].height / base_h;
765
766					if( kx <= 0 )
767					{
768						flagx = 1;
769						new_base_w = cvRound( r[0].width * scale ) / kx;
770						x0 = cvRound( r[0].x * scale );
771					}
772
773					if( ky <= 0 )
774					{
775						flagy = 1;
776						new_base_h = cvRound( r[0].height * scale ) / ky;
777						y0 = cvRound( r[0].y * scale );
778					}
779#endif
780
781					float tmpweight[3] = {0};
782
783					for( k = 0; k < nr; k++ )
784					{
785						CvRect tr;
786						double correction_ratio;
787
788#if CV_ADJUST_FEATURES
789						if( flagx )
790						{
791							tr.x = (r[k].x - r[0].x) * new_base_w / base_w + x0;
792							tr.width = r[k].width * new_base_w / base_w;
793						}
794						else
795#endif
796						{
797							tr.x = cvRound( r[k].x * scale );
798							tr.width = cvRound( r[k].width * scale );
799						}
800
801#if CV_ADJUST_FEATURES
802						if( flagy )
803						{
804							tr.y = (r[k].y - r[0].y) * new_base_h / base_h + y0;
805							tr.height = r[k].height * new_base_h / base_h;
806						}
807						else
808#endif
809						{
810							tr.y = cvRound( r[k].y * scale );
811							tr.height = cvRound( r[k].height * scale );
812						}
813
814#if CV_ADJUST_WEIGHTS
815						{
816							// RAINER START
817							const float orig_feature_size =  (float)(feature->rect[k].r.width)*feature->rect[k].r.height;
818							const float orig_norm_size = (float)(_cascade->orig_window_size.width)*(_cascade->orig_window_size.height);
819							const float feature_size = float(tr.width*tr.height);
820							//const float normSize    = float(equ_rect.width*equ_rect.height);
821							float target_ratio = orig_feature_size / orig_norm_size;
822							//float isRatio = featureSize / normSize;
823							//correctionRatio = targetRatio / isRatio / normSize;
824							correction_ratio = target_ratio / feature_size;
825							// RAINER END
826						}
827#else
828						correction_ratio = weight_scale * (!feature->tilted ? 1 : 0.5);
829#endif
830
831						if( !feature->tilted )
832						{
833							hidfeature->rect[k].p0 = sum_elem_ptr(*sum, tr.y, tr.x);
834							hidfeature->rect[k].p1 = sum_elem_ptr(*sum, tr.y, tr.x + tr.width);
835							hidfeature->rect[k].p2 = sum_elem_ptr(*sum, tr.y + tr.height, tr.x);
836							hidfeature->rect[k].p3 = sum_elem_ptr(*sum, tr.y + tr.height, tr.x + tr.width);
837						}
838						else
839						{
840							hidfeature->rect[k].p2 = sum_elem_ptr(*tilted, tr.y + tr.width, tr.x + tr.width);
841							hidfeature->rect[k].p3 = sum_elem_ptr(*tilted, tr.y + tr.width + tr.height,
842																  tr.x + tr.width - tr.height);
843							hidfeature->rect[k].p0 = sum_elem_ptr(*tilted, tr.y, tr.x);
844							hidfeature->rect[k].p1 = sum_elem_ptr(*tilted, tr.y + tr.height, tr.x - tr.height);
845						}
846
847//						hidfeature->rect[k].weight = (float)(feature->rect[k].weight * correction_ratio);
848						tmpweight[k] = (float)(feature->rect[k].weight * correction_ratio);
849
850						if( k == 0 )
851							area0 = tr.width * tr.height;
852						else
853//							sum0 += hidfeature->rect[k].weight * tr.width * tr.height;
854							sum0 += tmpweight[k] * tr.width * tr.height;
855					}
856
857					tmpweight[0] = (float)(-sum0/area0);
858
859					for(int ii = 0; ii < nr; hidfeature->rect[ii].weight = (int)(tmpweight[ii] * 65536.0), ii++);
860				} /* l */
861			} /* j */
862		}
863    }
864
865    __END__;
866}
867
868CvMat *temp = 0, *sum = 0, *sqsum = 0;
869double tickFreqTimes1000 = ((double)cvGetTickFrequency()*1000.);
870
871CV_IMPL CvSeq*
872mycvHaarDetectObjects( const CvArr* _img,
873					CvHaarClassifierCascade* cascade,
874					CvMemStorage* storage, double scale_factor,
875					int min_neighbors, int flags, CvSize min_size )
876{
877    int split_stage = 2;
878
879    CvMat stub, *img = (CvMat*)_img;
880    CvMat  *tilted = 0, *norm_img = 0, *sumcanny = 0, *img_small = 0;
881    CvSeq* result_seq = 0;
882    CvMemStorage* temp_storage = 0;
883    CvAvgComp* comps = 0;
884    CvSeq* seq_thread[CV_MAX_THREADS] = {0};
885    int i, max_threads = 0;
886	double t1;
887
888    CV_FUNCNAME( "cvHaarDetectObjects" );
889
890    __BEGIN__;
891
892	double t = (double)cvGetTickCount();
893
894    CvSeq *seq = 0, *seq2 = 0, *idx_seq = 0, *big_seq = 0;
895    CvAvgComp result_comp = {{0,0,0,0},0};
896    double factor;
897    int npass = 2, coi;
898    bool do_canny_pruning = (flags & CV_HAAR_DO_CANNY_PRUNING) != 0;
899    bool find_biggest_object = (flags & CV_HAAR_FIND_BIGGEST_OBJECT) != 0;
900    bool rough_search = (flags & CV_HAAR_DO_ROUGH_SEARCH) != 0;
901
902    if( !CV_IS_HAAR_CLASSIFIER(cascade) )
903        CV_ERROR( !cascade ? CV_StsNullPtr : CV_StsBadArg, "Invalid classifier cascade" );
904
905    if( !storage )
906        CV_ERROR( CV_StsNullPtr, "Null storage pointer" );
907
908    CV_CALL( img = cvGetMat( img, &stub, &coi ));
909    if( coi )
910        CV_ERROR( CV_BadCOI, "COI is not supported" );
911
912    if( CV_MAT_DEPTH(img->type) != CV_8U )
913        CV_ERROR( CV_StsUnsupportedFormat, "Only 8-bit images are supported" );
914
915    if( scale_factor <= 1 )
916        CV_ERROR( CV_StsOutOfRange, "scale factor must be > 1" );
917
918    if( find_biggest_object )
919        flags &= ~CV_HAAR_SCALE_IMAGE;
920
921	if(!temp) {
922		CV_CALL( temp = cvCreateMat( img->rows, img->cols, CV_8UC1 ));
923	}
924	if(!sum) {
925		CV_CALL( sum = cvCreateMat( img->rows + 1, img->cols + 1, CV_32SC1 ));
926	}
927	if(!sqsum) {
928		CV_CALL( sqsum = cvCreateMat( img->rows + 1, img->cols + 1, CV_64FC1 ));
929	}
930    CV_CALL( temp_storage = cvCreateChildMemStorage( storage ));
931
932    if( !cascade->hid_cascade )
933        CV_CALL( myicvCreateHidHaarClassifierCascade(cascade) );
934
935    if( ((MyCvHidHaarClassifierCascade*)cascade->hid_cascade)->has_tilted_features )
936        tilted = cvCreateMat( img->rows + 1, img->cols + 1, CV_32SC1 );
937
938    seq = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvRect), temp_storage );
939    seq2 = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvAvgComp), temp_storage );
940    result_seq = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvAvgComp), storage );
941
942    max_threads = cvGetNumThreads();
943    if( max_threads > 1 )
944        for( i = 0; i < max_threads; i++ )
945        {
946            CvMemStorage* temp_storage_thread;
947            CV_CALL( temp_storage_thread = cvCreateMemStorage(0));
948            CV_CALL( seq_thread[i] = cvCreateSeq( 0, sizeof(CvSeq),
949												 sizeof(CvRect), temp_storage_thread ));
950        }
951    else
952        seq_thread[0] = seq;
953
954    if( CV_MAT_CN(img->type) > 1 )
955    {
956        cvCvtColor( img, temp, CV_BGR2GRAY );
957        img = temp;
958    }
959
960    if( flags & CV_HAAR_FIND_BIGGEST_OBJECT )
961        flags &= ~(CV_HAAR_SCALE_IMAGE|CV_HAAR_DO_CANNY_PRUNING);
962
963//    if( flags & CV_HAAR_SCALE_IMAGE )
964//    {
965//        CvSize win_size0 = cascade->orig_window_size;
966//        /*int use_ipp = cascade->hid_cascade->ipp_stages != 0 &&
967//		 icvApplyHaarClassifier_32f_C1R_p != 0;
968//
969//		 if( use_ipp )
970//		 CV_CALL( norm_img = cvCreateMat( img->rows, img->cols, CV_32FC1 ));*/
971//        CV_CALL( img_small = cvCreateMat( img->rows + 1, img->cols + 1, CV_8UC1 ));
972//
973//        for( factor = 1; ; factor *= scale_factor )
974//        {
975//            int strip_count, strip_size;
976//            int ystep = factor > 2. ? 1 : 2;
977//            CvSize win_size = { cvRound(win_size0.width*factor),
978//			cvRound(win_size0.height*factor) };
979//            CvSize sz = { cvRound( img->cols/factor ), cvRound( img->rows/factor ) };
980//            CvSize sz1 = { sz.width - win_size0.width, sz.height - win_size0.height };
981//            /*CvRect equ_rect = { icv_object_win_border, icv_object_win_border,
982//			 win_size0.width - icv_object_win_border*2,
983//			 win_size0.height - icv_object_win_border*2 };*/
984//            CvMat img1, sum1, sqsum1, norm1, tilted1, mask1;
985//            CvMat* _tilted = 0;
986//
987//            if( sz1.width <= 0 || sz1.height <= 0 )
988//                break;
989//            if( win_size.width < min_size.width || win_size.height < min_size.height )
990//                continue;
991//
992//            img1 = cvMat( sz.height, sz.width, CV_8UC1, img_small->data.ptr );
993//            sum1 = cvMat( sz.height+1, sz.width+1, CV_32SC1, sum->data.ptr );
994//            sqsum1 = cvMat( sz.height+1, sz.width+1, CV_64FC1, sqsum->data.ptr );
995//            if( tilted )
996//            {
997//                tilted1 = cvMat( sz.height+1, sz.width+1, CV_32SC1, tilted->data.ptr );
998//                _tilted = &tilted1;
999//            }
1000//            norm1 = cvMat( sz1.height, sz1.width, CV_32FC1, norm_img ? norm_img->data.ptr : 0 );
1001//            mask1 = cvMat( sz1.height, sz1.width, CV_8UC1, temp->data.ptr );
1002//
1003//            cvResize( img, &img1, CV_INTER_LINEAR );
1004//            cvIntegral( &img1, &sum1, &sqsum1, _tilted );
1005//
1006//            if( max_threads > 1 )
1007//            {
1008//                strip_count = MAX(MIN(sz1.height/ystep, max_threads*3), 1);
1009//                strip_size = (sz1.height + strip_count - 1)/strip_count;
1010//                strip_size = (strip_size / ystep)*ystep;
1011//            }
1012//            else
1013//            {
1014//                strip_count = 1;
1015//                strip_size = sz1.height;
1016//            }
1017//
1018//            //if( !use_ipp )
1019//			cvSetImagesForHaarClassifierCascade( cascade, &sum1, &sqsum1, 0, 1. );
1020//            /*else
1021//			 {
1022//			 for( i = 0; i <= sz.height; i++ )
1023//			 {
1024//			 const int* isum = (int*)(sum1.data.ptr + sum1.step*i);
1025//			 float* fsum = (float*)isum;
1026//			 const int FLT_DELTA = -(1 << 24);
1027//			 int j;
1028//			 for( j = 0; j <= sz.width; j++ )
1029//			 fsum[j] = (float)(isum[j] + FLT_DELTA);
1030//			 }
1031//			 }*/
1032//
1033//#ifdef _OPENMP
1034//#pragma omp parallel for num_threads(max_threads) schedule(dynamic)
1035//#endif
1036//            for( i = 0; i < strip_count; i++ )
1037//            {
1038//                int thread_id = cvGetThreadNum();
1039//                int positive = 0;
1040//                int y1 = i*strip_size, y2 = (i+1)*strip_size/* - ystep + 1*/;
1041//                CvSize ssz;
1042//                int x, y;
1043//                if( i == strip_count - 1 || y2 > sz1.height )
1044//                    y2 = sz1.height;
1045//                ssz = cvSize(sz1.width, y2 - y1);
1046//
1047//                /*if( use_ipp )
1048//				 {
1049//				 icvRectStdDev_32f_C1R_p(
1050//				 (float*)(sum1.data.ptr + y1*sum1.step), sum1.step,
1051//				 (double*)(sqsum1.data.ptr + y1*sqsum1.step), sqsum1.step,
1052//				 (float*)(norm1.data.ptr + y1*norm1.step), norm1.step, ssz, equ_rect );
1053//
1054//				 positive = (ssz.width/ystep)*((ssz.height + ystep-1)/ystep);
1055//				 memset( mask1.data.ptr + y1*mask1.step, ystep == 1, mask1.height*mask1.step);
1056//
1057//				 if( ystep > 1 )
1058//				 {
1059//				 for( y = y1, positive = 0; y < y2; y += ystep )
1060//				 for( x = 0; x < ssz.width; x += ystep )
1061//				 mask1.data.ptr[mask1.step*y + x] = (uchar)1;
1062//				 }
1063//
1064//				 for( int j = 0; j < cascade->count; j++ )
1065//				 {
1066//				 if( icvApplyHaarClassifier_32f_C1R_p(
1067//				 (float*)(sum1.data.ptr + y1*sum1.step), sum1.step,
1068//				 (float*)(norm1.data.ptr + y1*norm1.step), norm1.step,
1069//				 mask1.data.ptr + y1*mask1.step, mask1.step, ssz, &positive,
1070//				 cascade->hid_cascade->stage_classifier[j].threshold,
1071//				 cascade->hid_cascade->ipp_stages[j]) < 0 )
1072//				 {
1073//				 positive = 0;
1074//				 break;
1075//				 }
1076//				 if( positive <= 0 )
1077//				 break;
1078//				 }
1079//				 }
1080//				 else*/
1081//                {
1082//                    for( y = y1, positive = 0; y < y2; y += ystep )
1083//                        for( x = 0; x < ssz.width; x += ystep )
1084//                        {
1085//                            mask1.data.ptr[mask1.step*y + x] =
1086//							mycvRunHaarClassifierCascade( cascade, cvPoint(x,y), 0 ) > 0;
1087//                            positive += mask1.data.ptr[mask1.step*y + x];
1088//                        }
1089//                }
1090//
1091//                if( positive > 0 )
1092//                {
1093//                    for( y = y1; y < y2; y += ystep )
1094//                        for( x = 0; x < ssz.width; x += ystep )
1095//                            if( mask1.data.ptr[mask1.step*y + x] != 0 )
1096//                            {
1097//                                CvRect obj_rect = { cvRound(x*factor), cvRound(y*factor),
1098//								win_size.width, win_size.height };
1099//                                cvSeqPush( seq_thread[thread_id], &obj_rect );
1100//                            }
1101//                }
1102//            }
1103//
1104//            // gather the results
1105//            if( max_threads > 1 )
1106//                for( i = 0; i < max_threads; i++ )
1107//                {
1108//                    CvSeq* s = seq_thread[i];
1109//                    int j, total = s->total;
1110//                    CvSeqBlock* b = s->first;
1111//                    for( j = 0; j < total; j += b->count, b = b->next )
1112//                        cvSeqPushMulti( seq, b->data, b->count );
1113//                }
1114//        }
1115//    }
1116//    else
1117	t1 = (double)cvGetTickCount();
1118//	printf( "init time = %gms\n", (t1 - t)/tickFreqTimes1000);
1119	t = t1;
1120
1121    {
1122        int n_factors = 0;
1123        CvRect scan_roi_rect = {0,0,0,0};
1124        bool is_found = false, scan_roi = false;
1125
1126        cvIntegral( img, sum, sqsum, tilted );
1127
1128//        if( do_canny_pruning )
1129//        {
1130//            sumcanny = cvCreateMat( img->rows + 1, img->cols + 1, CV_32SC1 );
1131//            cvCanny( img, temp, 0, 50, 3 );
1132//            cvIntegral( temp, sumcanny );
1133//        }
1134
1135        if( (unsigned)split_stage >= (unsigned)cascade->count ||
1136		   ((MyCvHidHaarClassifierCascade*)cascade->hid_cascade)->is_tree )
1137        {
1138            split_stage = cascade->count;
1139            npass = 1;
1140        }
1141
1142        for( n_factors = 0, factor = 1;
1143			factor*cascade->orig_window_size.width < img->cols - 10 &&
1144			factor*cascade->orig_window_size.height < img->rows - 10;
1145			n_factors++, factor *= scale_factor )
1146            ;
1147
1148        if( find_biggest_object )
1149        {
1150            scale_factor = 1./scale_factor;
1151            factor *= scale_factor;
1152            big_seq = cvCreateSeq( 0, sizeof(CvSeq), sizeof(CvRect), temp_storage );
1153        }
1154        else
1155            factor = 1;
1156
1157        for( ; n_factors-- > 0 && !is_found; factor *= scale_factor )
1158        {
1159            const double ystep = MAX( 2, factor );
1160            CvSize win_size = { cvRound( cascade->orig_window_size.width * factor ),
1161			cvRound( cascade->orig_window_size.height * factor )};
1162            CvRect equ_rect = { 0, 0, 0, 0 };
1163            int *p0 = 0, *p1 = 0, *p2 = 0, *p3 = 0;
1164            int *pq0 = 0, *pq1 = 0, *pq2 = 0, *pq3 = 0;
1165            int pass, stage_offset = 0;
1166            int start_x = 0, start_y = 0;
1167            int end_x = cvRound((img->cols - win_size.width) / ystep);
1168            int end_y = cvRound((img->rows - win_size.height) / ystep);
1169
1170            if( win_size.width < min_size.width || win_size.height < min_size.height )
1171            {
1172                if( find_biggest_object )
1173                    break;
1174                continue;
1175            }
1176
1177            mycvSetImagesForHaarClassifierCascade( cascade, sum, sqsum, tilted, factor );
1178            cvZero( temp );
1179
1180//            if( do_canny_pruning )
1181//            {
1182//                equ_rect.x = cvRound(win_size.width*0.15);
1183//                equ_rect.y = cvRound(win_size.height*0.15);
1184//                equ_rect.width = cvRound(win_size.width*0.7);
1185//                equ_rect.height = cvRound(win_size.height*0.7);
1186//
1187//                p0 = (int*)(sumcanny->data.ptr + equ_rect.y*sumcanny->step) + equ_rect.x;
1188//                p1 = (int*)(sumcanny->data.ptr + equ_rect.y*sumcanny->step)
1189//				+ equ_rect.x + equ_rect.width;
1190//                p2 = (int*)(sumcanny->data.ptr + (equ_rect.y + equ_rect.height)*sumcanny->step) + equ_rect.x;
1191//                p3 = (int*)(sumcanny->data.ptr + (equ_rect.y + equ_rect.height)*sumcanny->step)
1192//				+ equ_rect.x + equ_rect.width;
1193//
1194//                pq0 = (int*)(sum->data.ptr + equ_rect.y*sum->step) + equ_rect.x;
1195//                pq1 = (int*)(sum->data.ptr + equ_rect.y*sum->step)
1196//				+ equ_rect.x + equ_rect.width;
1197//                pq2 = (int*)(sum->data.ptr + (equ_rect.y + equ_rect.height)*sum->step) + equ_rect.x;
1198//                pq3 = (int*)(sum->data.ptr + (equ_rect.y + equ_rect.height)*sum->step)
1199//				+ equ_rect.x + equ_rect.width;
1200//            }
1201
1202            if( scan_roi )
1203            {
1204                //adjust start_height and stop_height
1205                start_y = cvRound(scan_roi_rect.y / ystep);
1206                end_y = cvRound((scan_roi_rect.y + scan_roi_rect.height - win_size.height) / ystep);
1207
1208                start_x = cvRound(scan_roi_rect.x / ystep);
1209                end_x = cvRound((scan_roi_rect.x + scan_roi_rect.width - win_size.width) / ystep);
1210            }
1211
1212            ((MyCvHidHaarClassifierCascade*)cascade->hid_cascade)->count = split_stage;
1213
1214            for( pass = 0; pass < npass; pass++ )
1215            {
1216#ifdef _OPENMP
1217#pragma omp parallel for num_threads(max_threads) schedule(dynamic)
1218#endif
1219                for( int _iy = start_y; _iy < end_y; _iy++ )
1220                {
1221                    int thread_id = cvGetThreadNum();
1222                    int iy = cvRound(_iy*ystep);
1223                    int _ix, _xstep = 1;
1224                    uchar* mask_row = temp->data.ptr + temp->step * iy;
1225
1226                    for( _ix = start_x; _ix < end_x; _ix += _xstep )
1227                    {
1228                        int ix = cvRound(_ix*ystep); // it really should be ystep
1229
1230                        if( pass == 0 )
1231                        {
1232                            int result;
1233                            _xstep = 2;
1234
1235//                            if( do_canny_pruning )
1236//                            {
1237//                                int offset;
1238//                                int s, sq;
1239//
1240//                                offset = iy*(sum->step/sizeof(p0[0])) + ix;
1241//                                s = p0[offset] - p1[offset] - p2[offset] + p3[offset];
1242//                                sq = pq0[offset] - pq1[offset] - pq2[offset] + pq3[offset];
1243//                                if( s < 100 || sq < 20 )
1244//                                    continue;
1245//                            }
1246
1247                            result = mycvRunHaarClassifierCascade( cascade, cvPoint(ix,iy), 0 );
1248                            if( result > 0 )
1249                            {
1250                                if( pass < npass - 1 )
1251                                    mask_row[ix] = 1;
1252                                else
1253                                {
1254                                    CvRect rect = cvRect(ix,iy,win_size.width,win_size.height);
1255                                    cvSeqPush( seq_thread[thread_id], &rect );
1256                                }
1257                            }
1258                            if( result < 0 )
1259                                _xstep = 1;
1260                        }
1261                        else if( mask_row[ix] )
1262                        {
1263                            int result = mycvRunHaarClassifierCascade( cascade, cvPoint(ix,iy),
1264																	stage_offset );
1265                            if( result > 0 )
1266                            {
1267                                if( pass == npass - 1 )
1268                                {
1269                                    CvRect rect = cvRect(ix,iy,win_size.width,win_size.height);
1270                                    cvSeqPush( seq_thread[thread_id], &rect );
1271                                }
1272                            }
1273                            else
1274                                mask_row[ix] = 0;
1275                        }
1276                    }
1277                }
1278                stage_offset = ((MyCvHidHaarClassifierCascade*)cascade->hid_cascade)->count;
1279                ((MyCvHidHaarClassifierCascade*)cascade->hid_cascade)->count = cascade->count;
1280            }
1281
1282            // gather the results
1283            if( max_threads > 1 )
1284	            for( i = 0; i < max_threads; i++ )
1285	            {
1286		            CvSeq* s = seq_thread[i];
1287                    int j, total = s->total;
1288                    CvSeqBlock* b = s->first;
1289                    for( j = 0; j < total; j += b->count, b = b->next )
1290                        cvSeqPushMulti( seq, b->data, b->count );
1291	            }
1292
1293            if( find_biggest_object )
1294            {
1295                CvSeq* bseq = min_neighbors > 0 ? big_seq : seq;
1296
1297                if( min_neighbors > 0 && !scan_roi )
1298                {
1299                    // group retrieved rectangles in order to filter out noise
1300                    int ncomp = cvSeqPartition( seq, 0, &idx_seq, myis_equal, 0 );
1301                    CV_CALL( comps = (CvAvgComp*)cvAlloc( (ncomp+1)*sizeof(comps[0])));
1302                    memset( comps, 0, (ncomp+1)*sizeof(comps[0]));
1303
1304#if VERY_ROUGH_SEARCH
1305                    if( rough_search )
1306                    {
1307                        for( i = 0; i < seq->total; i++ )
1308                        {
1309                            CvRect r1 = *(CvRect*)cvGetSeqElem( seq, i );
1310                            int idx = *(int*)cvGetSeqElem( idx_seq, i );
1311                            assert( (unsigned)idx < (unsigned)ncomp );
1312
1313                            comps[idx].neighbors++;
1314                            comps[idx].rect.x += r1.x;
1315                            comps[idx].rect.y += r1.y;
1316                            comps[idx].rect.width += r1.width;
1317                            comps[idx].rect.height += r1.height;
1318                        }
1319
1320                        // calculate average bounding box
1321                        for( i = 0; i < ncomp; i++ )
1322                        {
1323                            int n = comps[i].neighbors;
1324                            if( n >= min_neighbors )
1325                            {
1326                                CvAvgComp comp;
1327                                comp.rect.x = (comps[i].rect.x*2 + n)/(2*n);
1328                                comp.rect.y = (comps[i].rect.y*2 + n)/(2*n);
1329                                comp.rect.width = (comps[i].rect.width*2 + n)/(2*n);
1330                                comp.rect.height = (comps[i].rect.height*2 + n)/(2*n);
1331                                comp.neighbors = n;
1332                                cvSeqPush( bseq, &comp );
1333                            }
1334                        }
1335                    }
1336                    else
1337#endif
1338                    {
1339                        for( i = 0 ; i <= ncomp; i++ )
1340                            comps[i].rect.x = comps[i].rect.y = INT_MAX;
1341
1342                        // count number of neighbors
1343                        for( i = 0; i < seq->total; i++ )
1344                        {
1345                            CvRect r1 = *(CvRect*)cvGetSeqElem( seq, i );
1346                            int idx = *(int*)cvGetSeqElem( idx_seq, i );
1347                            assert( (unsigned)idx < (unsigned)ncomp );
1348
1349                            comps[idx].neighbors++;
1350
1351                            // rect.width and rect.height will store coordinate of right-bottom corner
1352                            comps[idx].rect.x = MIN(comps[idx].rect.x, r1.x);
1353                            comps[idx].rect.y = MIN(comps[idx].rect.y, r1.y);
1354                            comps[idx].rect.width = MAX(comps[idx].rect.width, r1.x+r1.width-1);
1355                            comps[idx].rect.height = MAX(comps[idx].rect.height, r1.y+r1.height-1);
1356                        }
1357
1358                        // calculate enclosing box
1359                        for( i = 0; i < ncomp; i++ )
1360                        {
1361                            int n = comps[i].neighbors;
1362                            if( n >= min_neighbors )
1363                            {
1364                                CvAvgComp comp;
1365                                int t;
1366                                double min_scale = rough_search ? 0.6 : 0.4;
1367                                comp.rect.x = comps[i].rect.x;
1368                                comp.rect.y = comps[i].rect.y;
1369                                comp.rect.width = comps[i].rect.width - comps[i].rect.x + 1;
1370                                comp.rect.height = comps[i].rect.height - comps[i].rect.y + 1;
1371
1372                                // update min_size
1373                                t = cvRound( comp.rect.width*min_scale );
1374                                min_size.width = MAX( min_size.width, t );
1375
1376                                t = cvRound( comp.rect.height*min_scale );
1377                                min_size.height = MAX( min_size.height, t );
1378
1379                                //expand the box by 20% because we could miss some neighbours
1380                                //see 'is_equal' function
1381#if 1
1382                                int offset = cvRound(comp.rect.width * 0.2);
1383                                int right = MIN( img->cols-1, comp.rect.x+comp.rect.width-1 + offset );
1384                                int bottom = MIN( img->rows-1, comp.rect.y+comp.rect.height-1 + offset);
1385                                comp.rect.x = MAX( comp.rect.x - offset, 0 );
1386                                comp.rect.y = MAX( comp.rect.y - offset, 0 );
1387                                comp.rect.width = right - comp.rect.x + 1;
1388                                comp.rect.height = bottom - comp.rect.y + 1;
1389#endif
1390
1391                                comp.neighbors = n;
1392                                cvSeqPush( bseq, &comp );
1393                            }
1394                        }
1395                    }
1396
1397                    cvFree( &comps );
1398                }
1399
1400                // extract the biggest rect
1401                if( bseq->total > 0 )
1402                {
1403                    int max_area = 0;
1404                    for( i = 0; i < bseq->total; i++ )
1405                    {
1406                        CvAvgComp* comp = (CvAvgComp*)cvGetSeqElem( bseq, i );
1407                        int area = comp->rect.width * comp->rect.height;
1408                        if( max_area < area )
1409                        {
1410                            max_area = area;
1411                            result_comp.rect = comp->rect;
1412                            result_comp.neighbors = bseq == seq ? 1 : comp->neighbors;
1413                        }
1414                    }
1415
1416                    //Prepare information for further scanning inside the biggest rectangle
1417
1418#if VERY_ROUGH_SEARCH
1419                    // change scan ranges to roi in case of required
1420                    if( !rough_search && !scan_roi )
1421                    {
1422                        scan_roi = true;
1423                        scan_roi_rect = result_comp.rect;
1424                        cvClearSeq(bseq);
1425                    }
1426                    else if( rough_search )
1427                        is_found = true;
1428#else
1429                    if( !scan_roi )
1430                    {
1431                        scan_roi = true;
1432                        scan_roi_rect = result_comp.rect;
1433                        cvClearSeq(bseq);
1434                    }
1435#endif
1436                }
1437            }
1438        }
1439    }
1440
1441//	t1 = (double)cvGetTickCount();
1442//	printf( "factors time = %gms\n", (t1 - t)/tickFreqTimes1000);
1443//	t = t1;
1444
1445    if( min_neighbors == 0 && !find_biggest_object )
1446    {
1447        for( i = 0; i < seq->total; i++ )
1448        {
1449            CvRect* rect = (CvRect*)cvGetSeqElem( seq, i );
1450            CvAvgComp comp;
1451            comp.rect = *rect;
1452            comp.neighbors = 1;
1453            cvSeqPush( result_seq, &comp );
1454        }
1455    }
1456
1457    if( min_neighbors != 0
1458#if VERY_ROUGH_SEARCH
1459	   && (!find_biggest_object || !rough_search)
1460#endif
1461	   )
1462    {
1463        // group retrieved rectangles in order to filter out noise
1464        int ncomp = cvSeqPartition( seq, 0, &idx_seq, myis_equal, 0 );
1465        CV_CALL( comps = (CvAvgComp*)cvAlloc( (ncomp+1)*sizeof(comps[0])));
1466        memset( comps, 0, (ncomp+1)*sizeof(comps[0]));
1467
1468        // count number of neighbors
1469        for( i = 0; i < seq->total; i++ )
1470        {
1471            CvRect r1 = *(CvRect*)cvGetSeqElem( seq, i );
1472            int idx = *(int*)cvGetSeqElem( idx_seq, i );
1473            assert( (unsigned)idx < (unsigned)ncomp );
1474
1475            comps[idx].neighbors++;
1476
1477            comps[idx].rect.x += r1.x;
1478            comps[idx].rect.y += r1.y;
1479            comps[idx].rect.width += r1.width;
1480            comps[idx].rect.height += r1.height;
1481        }
1482
1483        // calculate average bounding box
1484        for( i = 0; i < ncomp; i++ )
1485        {
1486            int n = comps[i].neighbors;
1487            if( n >= min_neighbors )
1488            {
1489                CvAvgComp comp;
1490                comp.rect.x = (comps[i].rect.x*2 + n)/(2*n);
1491                comp.rect.y = (comps[i].rect.y*2 + n)/(2*n);
1492                comp.rect.width = (comps[i].rect.width*2 + n)/(2*n);
1493                comp.rect.height = (comps[i].rect.height*2 + n)/(2*n);
1494                comp.neighbors = comps[i].neighbors;
1495
1496                cvSeqPush( seq2, &comp );
1497            }
1498        }
1499
1500        if( !find_biggest_object )
1501        {
1502            // filter out small face rectangles inside large face rectangles
1503            for( i = 0; i < seq2->total; i++ )
1504            {
1505                CvAvgComp r1 = *(CvAvgComp*)cvGetSeqElem( seq2, i );
1506                int j, flag = 1;
1507
1508                for( j = 0; j < seq2->total; j++ )
1509                {
1510                    CvAvgComp r2 = *(CvAvgComp*)cvGetSeqElem( seq2, j );
1511                    int distance = cvRound( r2.rect.width * 0.2 );
1512
1513                    if( i != j &&
1514					   r1.rect.x >= r2.rect.x - distance &&
1515					   r1.rect.y >= r2.rect.y - distance &&
1516					   r1.rect.x + r1.rect.width <= r2.rect.x + r2.rect.width + distance &&
1517					   r1.rect.y + r1.rect.height <= r2.rect.y + r2.rect.height + distance &&
1518					   (r2.neighbors > MAX( 3, r1.neighbors ) || r1.neighbors < 3) )
1519                    {
1520                        flag = 0;
1521                        break;
1522                    }
1523                }
1524
1525                if( flag )
1526                    cvSeqPush( result_seq, &r1 );
1527            }
1528        }
1529        else
1530        {
1531            int max_area = 0;
1532            for( i = 0; i < seq2->total; i++ )
1533            {
1534                CvAvgComp* comp = (CvAvgComp*)cvGetSeqElem( seq2, i );
1535                int area = comp->rect.width * comp->rect.height;
1536                if( max_area < area )
1537                {
1538                    max_area = area;
1539                    result_comp = *comp;
1540                }
1541            }
1542        }
1543    }
1544
1545	t1 = (double)cvGetTickCount();
1546//	printf( "results eval time = %gms\n", (t1 - t)/tickFreqTimes1000);
1547	t = t1;
1548
1549    if( find_biggest_object && result_comp.rect.width > 0 )
1550        cvSeqPush( result_seq, &result_comp );
1551
1552    __END__;
1553
1554    if( max_threads > 1 )
1555	    for( i = 0; i < max_threads; i++ )
1556	    {
1557		    if( seq_thread[i] )
1558                cvReleaseMemStorage( &seq_thread[i]->storage );
1559	    }
1560
1561    cvReleaseMemStorage( &temp_storage );
1562    cvReleaseMat( &sum );
1563    cvReleaseMat( &sqsum );
1564    cvReleaseMat( &tilted );
1565    cvReleaseMat( &temp );
1566    cvReleaseMat( &sumcanny );
1567    cvReleaseMat( &norm_img );
1568    cvReleaseMat( &img_small );
1569    cvFree( &comps );
1570
1571    return result_seq;
1572}
1573