| File: | ccv_bbf.c |
| Warning: | line 932, column 10 Assigned value is garbage or undefined |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | #include "ccv.h" | |||
| 2 | #include "ccv_internal.h" | |||
| 3 | #include <sys/time.h> | |||
| 4 | #ifdef HAVE_GSL1 | |||
| 5 | #include <gsl/gsl_rng.h> | |||
| 6 | #include <gsl/gsl_randist.h> | |||
| 7 | #endif | |||
| 8 | #ifdef USE_OPENMP | |||
| 9 | #include <omp.h> | |||
| 10 | #endif | |||
| 11 | ||||
| 12 | const ccv_bbf_param_t ccv_bbf_default_params = { | |||
| 13 | .interval = 5, | |||
| 14 | .min_neighbors = 2, | |||
| 15 | .accurate = 1, | |||
| 16 | .flags = 0, | |||
| 17 | .size = { | |||
| 18 | 24, | |||
| 19 | 24, | |||
| 20 | }, | |||
| 21 | }; | |||
| 22 | ||||
| 23 | #define _ccv_width_padding(x)(((x) + 3) & -4) (((x) + 3) & -4) | |||
| 24 | ||||
| 25 | static inline int _ccv_run_bbf_feature(ccv_bbf_feature_t* feature, int* step, unsigned char** u8) | |||
| 26 | { | |||
| 27 | #define pf_at(i) (*(u8[feature->pz[i]] + feature->px[i] + feature->py[i] * step[feature->pz[i]])) | |||
| 28 | #define nf_at(i) (*(u8[feature->nz[i]] + feature->nx[i] + feature->ny[i] * step[feature->nz[i]])) | |||
| 29 | unsigned char pmin = pf_at(0), nmax = nf_at(0); | |||
| 30 | /* check if every point in P > every point in N, and take a shortcut */ | |||
| 31 | if (pmin <= nmax) | |||
| 32 | return 0; | |||
| 33 | int i; | |||
| 34 | for (i = 1; i < feature->size; i++) | |||
| 35 | { | |||
| 36 | if (feature->pz[i] >= 0) | |||
| 37 | { | |||
| 38 | int p = pf_at(i); | |||
| 39 | if (p < pmin) | |||
| 40 | { | |||
| 41 | if (p <= nmax) | |||
| 42 | return 0; | |||
| 43 | pmin = p; | |||
| 44 | } | |||
| 45 | } | |||
| 46 | if (feature->nz[i] >= 0) | |||
| 47 | { | |||
| 48 | int n = nf_at(i); | |||
| 49 | if (n > nmax) | |||
| 50 | { | |||
| 51 | if (pmin <= n) | |||
| 52 | return 0; | |||
| 53 | nmax = n; | |||
| 54 | } | |||
| 55 | } | |||
| 56 | } | |||
| 57 | #undef pf_at | |||
| 58 | #undef nf_at | |||
| 59 | return 1; | |||
| 60 | } | |||
| 61 | ||||
| 62 | static int _ccv_read_bbf_stage_classifier(const char* file, ccv_bbf_stage_classifier_t* classifier) | |||
| 63 | { | |||
| 64 | FILE* r = fopen(file, "r"); | |||
| 65 | if (r == 0) return -1; | |||
| 66 | (void)fscanf(r, "%d", &classifier->count); | |||
| 67 | union { float fl; int i; } fli; | |||
| 68 | (void)fscanf(r, "%d", &fli.i); | |||
| 69 | classifier->threshold = fli.fl; | |||
| 70 | classifier->feature = (ccv_bbf_feature_t*)ccmallocmalloc(classifier->count * sizeof(ccv_bbf_feature_t)); | |||
| 71 | classifier->alpha = (float*)ccmallocmalloc(classifier->count * 2 * sizeof(float)); | |||
| 72 | int i, j; | |||
| 73 | for (i = 0; i < classifier->count; i++) | |||
| 74 | { | |||
| 75 | (void)fscanf(r, "%d", &classifier->feature[i].size); | |||
| 76 | for (j = 0; j < classifier->feature[i].size; j++) | |||
| 77 | { | |||
| 78 | (void)fscanf(r, "%d %d %d", &classifier->feature[i].px[j], &classifier->feature[i].py[j], &classifier->feature[i].pz[j]); | |||
| 79 | (void)fscanf(r, "%d %d %d", &classifier->feature[i].nx[j], &classifier->feature[i].ny[j], &classifier->feature[i].nz[j]); | |||
| 80 | } | |||
| 81 | union { float fl; int i; } flia, flib; | |||
| 82 | (void)fscanf(r, "%d %d", &flia.i, &flib.i); | |||
| 83 | classifier->alpha[i * 2] = flia.fl; | |||
| 84 | classifier->alpha[i * 2 + 1] = flib.fl; | |||
| 85 | } | |||
| 86 | fclose(r); | |||
| 87 | return 0; | |||
| 88 | } | |||
| 89 | ||||
| 90 | #ifdef HAVE_GSL1 | |||
| 91 | ||||
| 92 | static unsigned int _ccv_bbf_time_measure() | |||
| 93 | { | |||
| 94 | struct timeval tv; | |||
| 95 | gettimeofday(&tv, 0); | |||
| 96 | return tv.tv_sec * 1000000 + tv.tv_usec; | |||
| 97 | } | |||
| 98 | ||||
| 99 | #define less_than(a, b, aux) ((a) < (b)) | |||
| 100 | CCV_IMPLEMENT_QSORT(_ccv_sort_32f, float, less_than)void _ccv_sort_32f(float *array, size_t total, int aux) { int isort_thresh = 7; float t; int sp = 0; struct { float *lb; float *ub; } stack[48]; if( total <= 1 ) return; stack[0].lb = array ; stack[0].ub = array + (total - 1); while( sp >= 0 ) { float * left = stack[sp].lb; float* right = stack[sp--].ub; for(;;) { int i, n = (int)(right - left) + 1, m; float* ptr; float* ptr2 ; if( n <= isort_thresh ) { insert_sort: for( ptr = left + 1; ptr <= right; ptr++ ) { for( ptr2 = ptr; ptr2 > left && less_than(ptr2[0],ptr2[-1], aux); ptr2--) (((t)) = ((ptr2[0])), ((ptr2[0])) = ((ptr2[-1])), ((ptr2[-1])) = ((t) )); } break; } else { float* left0; float* left1; float* right0 ; float* right1; float* pivot; float* a; float* b; float* c; int swap_cnt = 0; left0 = left; right0 = right; pivot = left + ( n/2); if( n > 40 ) { int d = n / 8; a = left, b = left + d , c = left + 2*d; left = less_than(*a, *b, aux) ? (less_than( *b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than (*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); a = pivot - d, b = pivot, c = pivot + d; pivot = less_than(*a, *b, aux ) ? (less_than(*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than(*a, *c, aux ) ? a : c)); a = right - 2*d, b = right - d, c = right; right = less_than(*a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than (*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than (*a, *c, aux) ? a : c)); } a = left, b = pivot, c = right; pivot = less_than(*a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than (*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than (*a, *c, aux) ? a : c)); if( pivot != left0 ) { (((t)) = ((*pivot )), ((*pivot)) = ((*left0)), ((*left0)) = ((t))); pivot = left0 ; } left = left1 = left0 + 1; right = right1 = right0; for(;; ) { while( left <= right && !less_than(*pivot, *left , aux) ) { if( !less_than(*left, *pivot, aux) ) { if( left > left1 ) (((t)) = ((*left1)), ((*left1)) = ((*left)), ((*left )) = ((t))); swap_cnt = 1; left1++; } left++; } while( left <= right && !less_than(*right, *pivot, aux) ) { if( !less_than (*pivot, *right, aux) ) { if( right < right1 ) (((t)) = (( *right1)), ((*right1)) = ((*right)), ((*right)) = ((t))); swap_cnt = 1; right1--; } right--; } if( left > right ) break; ((( t)) = ((*left)), ((*left)) = ((*right)), ((*right)) = ((t))); swap_cnt = 1; left++; right--; } if( swap_cnt == 0 ) { left = left0, right = right0; goto insert_sort; } n = ({ typeof ((int )(left1 - left0)) _a = ((int)(left1 - left0)); typeof ((int)( left - left1)) _b = ((int)(left - left1)); (_a < _b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t)) = ((left0[i])), ( (left0[i])) = ((left[i-n])), ((left[i-n])) = ((t))); n = ({ typeof ((int)(right0 - right1)) _a = ((int)(right0 - right1)); typeof ((int)(right1 - right)) _b = ((int)(right1 - right)); (_a < _b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t)) = ((left [i])), ((left[i])) = ((right0[i-n+1])), ((right0[i-n+1])) = ( (t))); n = (int)(left - left1); m = (int)(right1 - right); if ( n > 1 ) { if( m > 1 ) { if( n > m ) { stack[++sp]. lb = left0; stack[sp].ub = left0 + n - 1; left = right0 - m + 1, right = right0; } else { stack[++sp].lb = right0 - m + 1; stack[sp].ub = right0; left = left0, right = left0 + n - 1; } } else left = left0, right = left0 + n - 1; } else if( m > 1 ) left = right0 - m + 1, right = right0; else break; } } } } | |||
| 101 | #undef less_than | |||
| 102 | ||||
| 103 | static void _ccv_bbf_eval_data(ccv_bbf_stage_classifier_t* classifier, unsigned char** posdata, int posnum, unsigned char** negdata, int negnum, ccv_size_t size, float* peval, float* neval) | |||
| 104 | { | |||
| 105 | int i, j; | |||
| 106 | int steps[] = { _ccv_width_padding(size.width)(((size.width) + 3) & -4), | |||
| 107 | _ccv_width_padding(size.width >> 1)(((size.width >> 1) + 3) & -4), | |||
| 108 | _ccv_width_padding(size.width >> 2)(((size.width >> 2) + 3) & -4) }; | |||
| 109 | int isizs0 = steps[0] * size.height; | |||
| 110 | int isizs01 = isizs0 + steps[1] * (size.height >> 1); | |||
| 111 | for (i = 0; i < posnum; i++) | |||
| 112 | { | |||
| 113 | unsigned char* u8[] = { posdata[i], posdata[i] + isizs0, posdata[i] + isizs01 }; | |||
| 114 | float sum = 0; | |||
| 115 | float* alpha = classifier->alpha; | |||
| 116 | ccv_bbf_feature_t* feature = classifier->feature; | |||
| 117 | for (j = 0; j < classifier->count; ++j, alpha += 2, ++feature) | |||
| 118 | sum += alpha[_ccv_run_bbf_feature(feature, steps, u8)]; | |||
| 119 | peval[i] = sum; | |||
| 120 | } | |||
| 121 | for (i = 0; i < negnum; i++) | |||
| 122 | { | |||
| 123 | unsigned char* u8[] = { negdata[i], negdata[i] + isizs0, negdata[i] + isizs01 }; | |||
| 124 | float sum = 0; | |||
| 125 | float* alpha = classifier->alpha; | |||
| 126 | ccv_bbf_feature_t* feature = classifier->feature; | |||
| 127 | for (j = 0; j < classifier->count; ++j, alpha += 2, ++feature) | |||
| 128 | sum += alpha[_ccv_run_bbf_feature(feature, steps, u8)]; | |||
| 129 | neval[i] = sum; | |||
| 130 | } | |||
| 131 | } | |||
| 132 | ||||
| 133 | static int _ccv_prune_positive_data(ccv_bbf_classifier_cascade_t* cascade, unsigned char** posdata, int posnum, ccv_size_t size) | |||
| 134 | { | |||
| 135 | float* peval = (float*)ccmallocmalloc(posnum * sizeof(float)); | |||
| 136 | int i, j, k, rpos = posnum; | |||
| 137 | for (i = 0; i < cascade->count; i++) | |||
| 138 | { | |||
| 139 | _ccv_bbf_eval_data(cascade->stage_classifier + i, posdata, rpos, 0, 0, size, peval, 0); | |||
| 140 | k = 0; | |||
| 141 | for (j = 0; j < rpos; j++) | |||
| 142 | if (peval[j] >= cascade->stage_classifier[i].threshold) | |||
| 143 | { | |||
| 144 | posdata[k] = posdata[j]; | |||
| 145 | ++k; | |||
| 146 | } else { | |||
| 147 | ccfreefree(posdata[j]); | |||
| 148 | } | |||
| 149 | rpos = k; | |||
| 150 | } | |||
| 151 | ccfreefree(peval); | |||
| 152 | return rpos; | |||
| 153 | } | |||
| 154 | ||||
| 155 | static int _ccv_prepare_background_data(ccv_bbf_classifier_cascade_t* cascade, char** bgfiles, int bgnum, unsigned char** negdata, int negnum) | |||
| 156 | { | |||
| 157 | int t, i, j, k, q; | |||
| 158 | int negperbg; | |||
| 159 | int negtotal = 0; | |||
| 160 | int steps[] = { _ccv_width_padding(cascade->size.width)(((cascade->size.width) + 3) & -4), | |||
| 161 | _ccv_width_padding(cascade->size.width >> 1)(((cascade->size.width >> 1) + 3) & -4), | |||
| 162 | _ccv_width_padding(cascade->size.width >> 2)(((cascade->size.width >> 2) + 3) & -4) }; | |||
| 163 | int isizs0 = steps[0] * cascade->size.height; | |||
| 164 | int isizs1 = steps[1] * (cascade->size.height >> 1); | |||
| 165 | int isizs2 = steps[2] * (cascade->size.height >> 2); | |||
| 166 | int* idcheck = (int*)ccmallocmalloc(negnum * sizeof(int)); | |||
| 167 | ||||
| 168 | gsl_rng_env_setup(); | |||
| 169 | ||||
| 170 | gsl_rng* rng = gsl_rng_alloc(gsl_rng_default); | |||
| 171 | gsl_rng_set(rng, (unsigned long int)idcheck); | |||
| 172 | ||||
| 173 | ccv_size_t imgsz = cascade->size; | |||
| 174 | int rneg = negtotal; | |||
| 175 | for (t = 0; negtotal < negnum; t++) | |||
| 176 | { | |||
| 177 | PRINT(CCV_CLI_INFO, "preparing negative data ... 0%%")do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("preparing negative data ... 0%%"); fflush(stdout); } } while (0); | |||
| 178 | for (i = 0; i < bgnum; i++) | |||
| 179 | { | |||
| 180 | negperbg = (t < 2) ? (negnum - negtotal) / (bgnum - i) + 1 : negnum - negtotal; | |||
| 181 | ccv_dense_matrix_t* image = 0; | |||
| 182 | ccv_read(bgfiles[i], &image, CCV_IO_GRAY | CCV_IO_ANY_FILE)ccv_read_impl(bgfiles[i], &image, CCV_IO_GRAY | CCV_IO_ANY_FILE , 0, 0, 0); | |||
| 183 | assert((image->type & CCV_C1) && (image->type & CCV_8U))((void) sizeof (((image->type & CCV_C1) && (image ->type & CCV_8U)) ? 1 : 0), __extension__ ({ if ((image ->type & CCV_C1) && (image->type & CCV_8U )) ; else __assert_fail ("(image->type & CCV_C1) && (image->type & CCV_8U)" , "ccv_bbf.c", 183, __extension__ __PRETTY_FUNCTION__); })); | |||
| 184 | if (image == 0) | |||
| 185 | { | |||
| 186 | PRINT(CCV_CLI_ERROR, "\n%s file corrupted\n", bgfiles[i])do { if ((CCV_CLI_ERROR & ccv_cli_get_output_levels())) { printf("\n%s file corrupted\n", bgfiles[i]); fflush(stdout); } } while (0); | |||
| 187 | continue; | |||
| 188 | } | |||
| 189 | if (t % 2 != 0) | |||
| 190 | ccv_flip(image, 0, 0, CCV_FLIP_X); | |||
| 191 | if (t % 4 >= 2) | |||
| 192 | ccv_flip(image, 0, 0, CCV_FLIP_Y); | |||
| 193 | ccv_bbf_param_t params = { .interval = 3, .min_neighbors = 0, .accurate = 1, .flags = 0, .size = cascade->size }; | |||
| 194 | ccv_array_t* detected = ccv_bbf_detect_objects(image, &cascade, 1, params); | |||
| 195 | memset(idcheck, 0, ccv_min(detected->rnum, negperbg)({ typeof (detected->rnum) _a = (detected->rnum); typeof (negperbg) _b = (negperbg); (_a < _b) ? _a : _b; }) * sizeof(int)); | |||
| 196 | for (j = 0; j < ccv_min(detected->rnum, negperbg)({ typeof (detected->rnum) _a = (detected->rnum); typeof (negperbg) _b = (negperbg); (_a < _b) ? _a : _b; }); j++) | |||
| 197 | { | |||
| 198 | int r = gsl_rng_uniform_int(rng, detected->rnum); | |||
| 199 | int flag = 1; | |||
| 200 | ccv_rect_t* rect = (ccv_rect_t*)ccv_array_get(detected, r)((void*)(((char*)((detected)->data)) + (size_t)(detected)-> rsize * (size_t)(r))); | |||
| 201 | while (flag) { | |||
| 202 | flag = 0; | |||
| 203 | for (k = 0; k < j; k++) | |||
| 204 | if (r == idcheck[k]) | |||
| 205 | { | |||
| 206 | flag = 1; | |||
| 207 | r = gsl_rng_uniform_int(rng, detected->rnum); | |||
| 208 | break; | |||
| 209 | } | |||
| 210 | rect = (ccv_rect_t*)ccv_array_get(detected, r)((void*)(((char*)((detected)->data)) + (size_t)(detected)-> rsize * (size_t)(r))); | |||
| 211 | if ((rect->x < 0) || (rect->y < 0) || (rect->width + rect->x > image->cols) || (rect->height + rect->y > image->rows)) | |||
| 212 | { | |||
| 213 | flag = 1; | |||
| 214 | r = gsl_rng_uniform_int(rng, detected->rnum); | |||
| 215 | } | |||
| 216 | } | |||
| 217 | idcheck[j] = r; | |||
| 218 | ccv_dense_matrix_t* temp = 0; | |||
| 219 | ccv_dense_matrix_t* imgs0 = 0; | |||
| 220 | ccv_dense_matrix_t* imgs1 = 0; | |||
| 221 | ccv_dense_matrix_t* imgs2 = 0; | |||
| 222 | ccv_slice(image, (ccv_matrix_t**)&temp, 0, rect->y, rect->x, rect->height, rect->width); | |||
| 223 | ccv_resample(temp, &imgs0, 0, (double)imgsz.height / (double)temp->rows, (double)imgsz.width / (double)temp->cols, CCV_INTER_AREA); | |||
| 224 | assert(imgs0->step == steps[0])((void) sizeof ((imgs0->step == steps[0]) ? 1 : 0), __extension__ ({ if (imgs0->step == steps[0]) ; else __assert_fail ("imgs0->step == steps[0]" , "ccv_bbf.c", 224, __extension__ __PRETTY_FUNCTION__); })); | |||
| 225 | ccv_matrix_free(temp); | |||
| 226 | ccv_sample_down(imgs0, &imgs1, 0, 0, 0); | |||
| 227 | assert(imgs1->step == steps[1])((void) sizeof ((imgs1->step == steps[1]) ? 1 : 0), __extension__ ({ if (imgs1->step == steps[1]) ; else __assert_fail ("imgs1->step == steps[1]" , "ccv_bbf.c", 227, __extension__ __PRETTY_FUNCTION__); })); | |||
| 228 | ccv_sample_down(imgs1, &imgs2, 0, 0, 0); | |||
| 229 | assert(imgs2->step == steps[2])((void) sizeof ((imgs2->step == steps[2]) ? 1 : 0), __extension__ ({ if (imgs2->step == steps[2]) ; else __assert_fail ("imgs2->step == steps[2]" , "ccv_bbf.c", 229, __extension__ __PRETTY_FUNCTION__); })); | |||
| 230 | ||||
| 231 | negdata[negtotal] = (unsigned char*)ccmallocmalloc(isizs0 + isizs1 + isizs2); | |||
| 232 | unsigned char* u8s0 = negdata[negtotal]; | |||
| 233 | unsigned char* u8s1 = negdata[negtotal] + isizs0; | |||
| 234 | unsigned char* u8s2 = negdata[negtotal] + isizs0 + isizs1; | |||
| 235 | unsigned char* u8[] = { u8s0, u8s1, u8s2 }; | |||
| 236 | memcpy(u8s0, imgs0->data.u8, imgs0->rows * imgs0->step); | |||
| 237 | ccv_matrix_free(imgs0); | |||
| 238 | memcpy(u8s1, imgs1->data.u8, imgs1->rows * imgs1->step); | |||
| 239 | ccv_matrix_free(imgs1); | |||
| 240 | memcpy(u8s2, imgs2->data.u8, imgs2->rows * imgs2->step); | |||
| 241 | ccv_matrix_free(imgs2); | |||
| 242 | ||||
| 243 | flag = 1; | |||
| 244 | ccv_bbf_stage_classifier_t* classifier = cascade->stage_classifier; | |||
| 245 | for (k = 0; k < cascade->count; ++k, ++classifier) | |||
| 246 | { | |||
| 247 | float sum = 0; | |||
| 248 | float* alpha = classifier->alpha; | |||
| 249 | ccv_bbf_feature_t* feature = classifier->feature; | |||
| 250 | for (q = 0; q < classifier->count; ++q, alpha += 2, ++feature) | |||
| 251 | sum += alpha[_ccv_run_bbf_feature(feature, steps, u8)]; | |||
| 252 | if (sum < classifier->threshold) | |||
| 253 | { | |||
| 254 | flag = 0; | |||
| 255 | break; | |||
| 256 | } | |||
| 257 | } | |||
| 258 | if (!flag) | |||
| 259 | ccfreefree(negdata[negtotal]); | |||
| 260 | else { | |||
| 261 | ++negtotal; | |||
| 262 | if (negtotal >= negnum) | |||
| 263 | break; | |||
| 264 | } | |||
| 265 | } | |||
| 266 | ccv_array_free(detected); | |||
| 267 | ccv_matrix_free(image); | |||
| 268 | ccv_drain_cache(); | |||
| 269 | PRINT(CCV_CLI_INFO, "\rpreparing negative data ... %2d%%", 100 * negtotal / negnum)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\rpreparing negative data ... %2d%%", 100 * negtotal / negnum ); fflush(stdout); } } while (0); | |||
| 270 | fflush(0); | |||
| 271 | if (negtotal >= negnum) | |||
| 272 | break; | |||
| 273 | } | |||
| 274 | if (rneg == negtotal) | |||
| 275 | break; | |||
| 276 | rneg = negtotal; | |||
| 277 | PRINT(CCV_CLI_INFO, "\nentering additional round %d\n", t + 1)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\nentering additional round %d\n", t + 1); fflush(stdout); } } while (0); | |||
| 278 | } | |||
| 279 | gsl_rng_free(rng); | |||
| 280 | ccfreefree(idcheck); | |||
| 281 | ccv_drain_cache(); | |||
| 282 | PRINT(CCV_CLI_INFO, "\n")do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\n"); fflush(stdout); } } while (0); | |||
| 283 | return negtotal; | |||
| 284 | } | |||
| 285 | ||||
| 286 | static void _ccv_prepare_positive_data(ccv_dense_matrix_t** posimg, unsigned char** posdata, ccv_size_t size, int posnum) | |||
| 287 | { | |||
| 288 | PRINT(CCV_CLI_INFO, "preparing positive data ... 0%%")do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("preparing positive data ... 0%%"); fflush(stdout); } } while (0); | |||
| 289 | int i; | |||
| 290 | for (i = 0; i < posnum; i++) | |||
| 291 | { | |||
| 292 | ccv_dense_matrix_t* imgs0 = posimg[i]; | |||
| 293 | ccv_dense_matrix_t* imgs1 = 0; | |||
| 294 | ccv_dense_matrix_t* imgs2 = 0; | |||
| 295 | assert((imgs0->type & CCV_C1) && (imgs0->type & CCV_8U) && imgs0->rows == size.height && imgs0->cols == size.width)((void) sizeof (((imgs0->type & CCV_C1) && (imgs0 ->type & CCV_8U) && imgs0->rows == size.height && imgs0->cols == size.width) ? 1 : 0), __extension__ ({ if ((imgs0->type & CCV_C1) && (imgs0->type & CCV_8U) && imgs0->rows == size.height && imgs0->cols == size.width) ; else __assert_fail ("(imgs0->type & CCV_C1) && (imgs0->type & CCV_8U) && imgs0->rows == size.height && imgs0->cols == size.width" , "ccv_bbf.c", 295, __extension__ __PRETTY_FUNCTION__); })); | |||
| 296 | ccv_sample_down(imgs0, &imgs1, 0, 0, 0); | |||
| 297 | ccv_sample_down(imgs1, &imgs2, 0, 0, 0); | |||
| 298 | int isizs0 = imgs0->rows * imgs0->step; | |||
| 299 | int isizs1 = imgs1->rows * imgs1->step; | |||
| 300 | int isizs2 = imgs2->rows * imgs2->step; | |||
| 301 | ||||
| 302 | posdata[i] = (unsigned char*)ccmallocmalloc(isizs0 + isizs1 + isizs2); | |||
| 303 | memcpy(posdata[i], imgs0->data.u8, isizs0); | |||
| 304 | memcpy(posdata[i] + isizs0, imgs1->data.u8, isizs1); | |||
| 305 | memcpy(posdata[i] + isizs0 + isizs1, imgs2->data.u8, isizs2); | |||
| 306 | ||||
| 307 | PRINT(CCV_CLI_INFO, "\rpreparing positive data ... %2d%%", 100 * (i + 1) / posnum)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\rpreparing positive data ... %2d%%", 100 * (i + 1) / posnum ); fflush(stdout); } } while (0); | |||
| 308 | fflush(0); | |||
| 309 | ||||
| 310 | ccv_matrix_free(imgs1); | |||
| 311 | ccv_matrix_free(imgs2); | |||
| 312 | } | |||
| 313 | ccv_drain_cache(); | |||
| 314 | PRINT(CCV_CLI_INFO, "\n")do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\n"); fflush(stdout); } } while (0); | |||
| 315 | } | |||
| 316 | ||||
| 317 | typedef struct { | |||
| 318 | double fitness; | |||
| 319 | int pk, nk; | |||
| 320 | int age; | |||
| 321 | double error; | |||
| 322 | ccv_bbf_feature_t feature; | |||
| 323 | } ccv_bbf_gene_t; | |||
| 324 | ||||
| 325 | static inline void _ccv_bbf_genetic_fitness(ccv_bbf_gene_t* gene) | |||
| 326 | { | |||
| 327 | gene->fitness = (1 - gene->error) * exp(-0.01 * gene->age) * exp((gene->pk + gene->nk) * log(1.015)); | |||
| 328 | } | |||
| 329 | ||||
| 330 | static inline int _ccv_bbf_exist_gene_feature(ccv_bbf_gene_t* gene, int x, int y, int z) | |||
| 331 | { | |||
| 332 | int i; | |||
| 333 | for (i = 0; i < gene->pk; i++) | |||
| 334 | if (z == gene->feature.pz[i] && x == gene->feature.px[i] && y == gene->feature.py[i]) | |||
| 335 | return 1; | |||
| 336 | for (i = 0; i < gene->nk; i++) | |||
| 337 | if (z == gene->feature.nz[i] && x == gene->feature.nx[i] && y == gene->feature.ny[i]) | |||
| 338 | return 1; | |||
| 339 | return 0; | |||
| 340 | } | |||
| 341 | ||||
| 342 | static inline void _ccv_bbf_randomize_gene(gsl_rng* rng, ccv_bbf_gene_t* gene, int* rows, int* cols) | |||
| 343 | { | |||
| 344 | int i; | |||
| 345 | do { | |||
| 346 | gene->pk = gsl_rng_uniform_int(rng, CCV_BBF_POINT_MAX(8) - 1) + 1; | |||
| 347 | gene->nk = gsl_rng_uniform_int(rng, CCV_BBF_POINT_MAX(8) - 1) + 1; | |||
| 348 | } while (gene->pk + gene->nk < CCV_BBF_POINT_MIN(3)); /* a hard restriction of at least 3 points have to be examed */ | |||
| 349 | gene->feature.size = ccv_max(gene->pk, gene->nk)({ typeof (gene->pk) _a = (gene->pk); typeof (gene-> nk) _b = (gene->nk); (_a > _b) ? _a : _b; }); | |||
| 350 | gene->age = 0; | |||
| 351 | for (i = 0; i < CCV_BBF_POINT_MAX(8); i++) | |||
| 352 | { | |||
| 353 | gene->feature.pz[i] = -1; | |||
| 354 | gene->feature.nz[i] = -1; | |||
| 355 | } | |||
| 356 | int x, y, z; | |||
| 357 | for (i = 0; i < gene->pk; i++) | |||
| 358 | { | |||
| 359 | do { | |||
| 360 | z = gsl_rng_uniform_int(rng, 3); | |||
| 361 | x = gsl_rng_uniform_int(rng, cols[z]); | |||
| 362 | y = gsl_rng_uniform_int(rng, rows[z]); | |||
| 363 | } while (_ccv_bbf_exist_gene_feature(gene, x, y, z)); | |||
| 364 | gene->feature.pz[i] = z; | |||
| 365 | gene->feature.px[i] = x; | |||
| 366 | gene->feature.py[i] = y; | |||
| 367 | } | |||
| 368 | for (i = 0; i < gene->nk; i++) | |||
| 369 | { | |||
| 370 | do { | |||
| 371 | z = gsl_rng_uniform_int(rng, 3); | |||
| 372 | x = gsl_rng_uniform_int(rng, cols[z]); | |||
| 373 | y = gsl_rng_uniform_int(rng, rows[z]); | |||
| 374 | } while ( _ccv_bbf_exist_gene_feature(gene, x, y, z)); | |||
| 375 | gene->feature.nz[i] = z; | |||
| 376 | gene->feature.nx[i] = x; | |||
| 377 | gene->feature.ny[i] = y; | |||
| 378 | } | |||
| 379 | } | |||
| 380 | ||||
| 381 | static inline double _ccv_bbf_error_rate(ccv_bbf_feature_t* feature, unsigned char** posdata, int posnum, unsigned char** negdata, int negnum, ccv_size_t size, double* pw, double* nw) | |||
| 382 | { | |||
| 383 | int i; | |||
| 384 | int steps[] = { _ccv_width_padding(size.width)(((size.width) + 3) & -4), | |||
| 385 | _ccv_width_padding(size.width >> 1)(((size.width >> 1) + 3) & -4), | |||
| 386 | _ccv_width_padding(size.width >> 2)(((size.width >> 2) + 3) & -4) }; | |||
| 387 | int isizs0 = steps[0] * size.height; | |||
| 388 | int isizs01 = isizs0 + steps[1] * (size.height >> 1); | |||
| 389 | double error = 0; | |||
| 390 | for (i = 0; i < posnum; i++) | |||
| 391 | { | |||
| 392 | unsigned char* u8[] = { posdata[i], posdata[i] + isizs0, posdata[i] + isizs01 }; | |||
| 393 | if (!_ccv_run_bbf_feature(feature, steps, u8)) | |||
| 394 | error += pw[i]; | |||
| 395 | } | |||
| 396 | for (i = 0; i < negnum; i++) | |||
| 397 | { | |||
| 398 | unsigned char* u8[] = { negdata[i], negdata[i] + isizs0, negdata[i] + isizs01 }; | |||
| 399 | if ( _ccv_run_bbf_feature(feature, steps, u8)) | |||
| 400 | error += nw[i]; | |||
| 401 | } | |||
| 402 | return error; | |||
| 403 | } | |||
| 404 | ||||
| 405 | #define less_than(fit1, fit2, aux) ((fit1).fitness >= (fit2).fitness) | |||
| 406 | static CCV_IMPLEMENT_QSORT(_ccv_bbf_genetic_qsort, ccv_bbf_gene_t, less_than)void _ccv_bbf_genetic_qsort(ccv_bbf_gene_t *array, size_t total , int aux) { int isort_thresh = 7; ccv_bbf_gene_t t; int sp = 0; struct { ccv_bbf_gene_t *lb; ccv_bbf_gene_t *ub; } stack[ 48]; if( total <= 1 ) return; stack[0].lb = array; stack[0 ].ub = array + (total - 1); while( sp >= 0 ) { ccv_bbf_gene_t * left = stack[sp].lb; ccv_bbf_gene_t* right = stack[sp--].ub ; for(;;) { int i, n = (int)(right - left) + 1, m; ccv_bbf_gene_t * ptr; ccv_bbf_gene_t* ptr2; if( n <= isort_thresh ) { insert_sort : for( ptr = left + 1; ptr <= right; ptr++ ) { for( ptr2 = ptr; ptr2 > left && less_than(ptr2[0],ptr2[-1], aux ); ptr2--) (((t)) = ((ptr2[0])), ((ptr2[0])) = ((ptr2[-1])), ( (ptr2[-1])) = ((t))); } break; } else { ccv_bbf_gene_t* left0 ; ccv_bbf_gene_t* left1; ccv_bbf_gene_t* right0; ccv_bbf_gene_t * right1; ccv_bbf_gene_t* pivot; ccv_bbf_gene_t* a; ccv_bbf_gene_t * b; ccv_bbf_gene_t* c; int swap_cnt = 0; left0 = left; right0 = right; pivot = left + (n/2); if( n > 40 ) { int d = n / 8; a = left, b = left + d, c = left + 2*d; left = less_than( *a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than(*a, * c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than( *a, *c, aux) ? a : c)); a = pivot - d, b = pivot, c = pivot + d; pivot = less_than(*a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux ) ? b : (less_than(*a, *c, aux) ? a : c)); a = right - 2*d, b = right - d, c = right; right = less_than(*a, *b, aux) ? (less_than (*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than (*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); } a = left , b = pivot, c = right; pivot = less_than(*a, *b, aux) ? (less_than (*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than (*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); if( pivot != left0 ) { (((t)) = ((*pivot)), ((*pivot)) = ((*left0)), ( (*left0)) = ((t))); pivot = left0; } left = left1 = left0 + 1 ; right = right1 = right0; for(;;) { while( left <= right && !less_than(*pivot, *left, aux) ) { if( !less_than(*left, *pivot , aux) ) { if( left > left1 ) (((t)) = ((*left1)), ((*left1 )) = ((*left)), ((*left)) = ((t))); swap_cnt = 1; left1++; } left ++; } while( left <= right && !less_than(*right, * pivot, aux) ) { if( !less_than(*pivot, *right, aux) ) { if( right < right1 ) (((t)) = ((*right1)), ((*right1)) = ((*right)) , ((*right)) = ((t))); swap_cnt = 1; right1--; } right--; } if ( left > right ) break; (((t)) = ((*left)), ((*left)) = (( *right)), ((*right)) = ((t))); swap_cnt = 1; left++; right--; } if( swap_cnt == 0 ) { left = left0, right = right0; goto insert_sort ; } n = ({ typeof ((int)(left1 - left0)) _a = ((int)(left1 - left0 )); typeof ((int)(left - left1)) _b = ((int)(left - left1)); ( _a < _b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t)) = ((left0[i])), ((left0[i])) = ((left[i-n])), ((left[i-n])) = ((t))); n = ({ typeof ((int)(right0 - right1)) _a = ((int)(right0 - right1)); typeof ((int)(right1 - right)) _b = ((int)(right1 - right)); (_a < _b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t)) = ((left[i])), ((left[i])) = ((right0[i-n+1])), ((right0[i-n+1])) = ((t))); n = (int)(left - left1); m = (int )(right1 - right); if( n > 1 ) { if( m > 1 ) { if( n > m ) { stack[++sp].lb = left0; stack[sp].ub = left0 + n - 1; left = right0 - m + 1, right = right0; } else { stack[++sp].lb = right0 - m + 1; stack[sp].ub = right0; left = left0, right = left0 + n - 1; } } else left = left0, right = left0 + n - 1; } else if ( m > 1 ) left = right0 - m + 1, right = right0; else break ; } } } } | |||
| 407 | #undef less_than | |||
| 408 | ||||
| 409 | static ccv_bbf_feature_t _ccv_bbf_genetic_optimize(unsigned char** posdata, int posnum, unsigned char** negdata, int negnum, int ftnum, ccv_size_t size, double* pw, double* nw) | |||
| 410 | { | |||
| 411 | ccv_bbf_feature_t best; | |||
| 412 | /* seed (random method) */ | |||
| 413 | gsl_rng_env_setup(); | |||
| 414 | gsl_rng* rng = gsl_rng_alloc(gsl_rng_default); | |||
| 415 | union { unsigned long int li; double db; } dbli; | |||
| 416 | dbli.db = pw[0] + nw[0]; | |||
| 417 | gsl_rng_set(rng, dbli.li); | |||
| 418 | int i, j; | |||
| 419 | int pnum = ftnum * 100; | |||
| 420 | assert(pnum > 0)((void) sizeof ((pnum > 0) ? 1 : 0), __extension__ ({ if ( pnum > 0) ; else __assert_fail ("pnum > 0", "ccv_bbf.c" , 420, __extension__ __PRETTY_FUNCTION__); })); | |||
| 421 | ccv_bbf_gene_t* gene = (ccv_bbf_gene_t*)ccmallocmalloc(pnum * sizeof(ccv_bbf_gene_t)); | |||
| 422 | int rows[] = { size.height, size.height >> 1, size.height >> 2 }; | |||
| 423 | int cols[] = { size.width, size.width >> 1, size.width >> 2 }; | |||
| 424 | for (i = 0; i < pnum; i++) | |||
| 425 | _ccv_bbf_randomize_gene(rng, &gene[i], rows, cols); | |||
| 426 | unsigned int timer = _ccv_bbf_time_measure(); | |||
| 427 | #ifdef USE_OPENMP | |||
| 428 | #pragma omp parallel for private(i) schedule(dynamic) | |||
| 429 | #endif | |||
| 430 | for (i = 0; i < pnum; i++) | |||
| 431 | gene[i].error = _ccv_bbf_error_rate(&gene[i].feature, posdata, posnum, negdata, negnum, size, pw, nw); | |||
| 432 | timer = _ccv_bbf_time_measure() - timer; | |||
| 433 | for (i = 0; i < pnum; i++) | |||
| 434 | _ccv_bbf_genetic_fitness(&gene[i]); | |||
| 435 | double best_err = 1; | |||
| 436 | int rnum = ftnum * 39; /* number of randomize */ | |||
| 437 | int mnum = ftnum * 40; /* number of mutation */ | |||
| 438 | int hnum = ftnum * 20; /* number of hybrid */ | |||
| 439 | /* iteration stop crit : best no change in 40 iterations */ | |||
| 440 | int it = 0, t; | |||
| 441 | for (t = 0 ; it < 40; ++it, ++t) | |||
| 442 | { | |||
| 443 | int min_id = 0; | |||
| 444 | double min_err = gene[0].error; | |||
| 445 | for (i = 1; i < pnum; i++) | |||
| 446 | if (gene[i].error < min_err) | |||
| 447 | { | |||
| 448 | min_id = i; | |||
| 449 | min_err = gene[i].error; | |||
| 450 | } | |||
| 451 | min_err = gene[min_id].error = _ccv_bbf_error_rate(&gene[min_id].feature, posdata, posnum, negdata, negnum, size, pw, nw); | |||
| 452 | if (min_err < best_err) | |||
| 453 | { | |||
| 454 | best_err = min_err; | |||
| 455 | memcpy(&best, &gene[min_id].feature, sizeof(best)); | |||
| 456 | PRINT(CCV_CLI_INFO, "best bbf feature with error %f\n|-size: %d\n|-positive point: ", best_err, best.size)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("best bbf feature with error %f\n|-size: %d\n|-positive point: " , best_err, best.size); fflush(stdout); } } while (0); | |||
| 457 | for (i = 0; i < best.size; i++) | |||
| 458 | PRINT(CCV_CLI_INFO, "(%d %d %d), ", best.px[i], best.py[i], best.pz[i])do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("(%d %d %d), ", best.px[i], best.py[i], best.pz[i]); fflush( stdout); } } while (0); | |||
| 459 | PRINT(CCV_CLI_INFO, "\n|-negative point: ")do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\n|-negative point: "); fflush(stdout); } } while (0); | |||
| 460 | for (i = 0; i < best.size; i++) | |||
| 461 | PRINT(CCV_CLI_INFO, "(%d %d %d), ", best.nx[i], best.ny[i], best.nz[i])do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("(%d %d %d), ", best.nx[i], best.ny[i], best.nz[i]); fflush( stdout); } } while (0); | |||
| 462 | PRINT(CCV_CLI_INFO, "\n")do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\n"); fflush(stdout); } } while (0); | |||
| 463 | it = 0; | |||
| 464 | } | |||
| 465 | PRINT(CCV_CLI_INFO, "minimum error achieved in round %d(%d) : %f with %d ms\n", t, it, min_err, timer / 1000)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("minimum error achieved in round %d(%d) : %f with %d ms\n", t , it, min_err, timer / 1000); fflush(stdout); } } while (0); | |||
| 466 | _ccv_bbf_genetic_qsort(gene, pnum, 0); | |||
| 467 | for (i = 0; i < ftnum; i++) | |||
| 468 | ++gene[i].age; | |||
| 469 | for (i = ftnum; i < ftnum + mnum; i++) | |||
| 470 | { | |||
| 471 | int parent = gsl_rng_uniform_int(rng, ftnum); | |||
| 472 | memcpy(gene + i, gene + parent, sizeof(ccv_bbf_gene_t)); | |||
| 473 | /* three mutation strategy : 1. add, 2. remove, 3. refine */ | |||
| 474 | int pnm, pn = gsl_rng_uniform_int(rng, 2); | |||
| 475 | int* pnk[] = { &gene[i].pk, &gene[i].nk }; | |||
| 476 | int* pnx[] = { gene[i].feature.px, gene[i].feature.nx }; | |||
| 477 | int* pny[] = { gene[i].feature.py, gene[i].feature.ny }; | |||
| 478 | int* pnz[] = { gene[i].feature.pz, gene[i].feature.nz }; | |||
| 479 | int x, y, z; | |||
| 480 | int victim, decay = 1; | |||
| 481 | do { | |||
| 482 | switch (gsl_rng_uniform_int(rng, 3)) | |||
| 483 | { | |||
| 484 | case 0: /* add */ | |||
| 485 | if (gene[i].pk == CCV_BBF_POINT_MAX(8) && gene[i].nk == CCV_BBF_POINT_MAX(8)) | |||
| 486 | break; | |||
| 487 | while (*pnk[pn] + 1 > CCV_BBF_POINT_MAX(8)) | |||
| 488 | pn = gsl_rng_uniform_int(rng, 2); | |||
| 489 | do { | |||
| 490 | z = gsl_rng_uniform_int(rng, 3); | |||
| 491 | x = gsl_rng_uniform_int(rng, cols[z]); | |||
| 492 | y = gsl_rng_uniform_int(rng, rows[z]); | |||
| 493 | } while (_ccv_bbf_exist_gene_feature(&gene[i], x, y, z)); | |||
| 494 | pnz[pn][*pnk[pn]] = z; | |||
| 495 | pnx[pn][*pnk[pn]] = x; | |||
| 496 | pny[pn][*pnk[pn]] = y; | |||
| 497 | ++(*pnk[pn]); | |||
| 498 | gene[i].feature.size = ccv_max(gene[i].pk, gene[i].nk)({ typeof (gene[i].pk) _a = (gene[i].pk); typeof (gene[i].nk) _b = (gene[i].nk); (_a > _b) ? _a : _b; }); | |||
| 499 | decay = gene[i].age = 0; | |||
| 500 | break; | |||
| 501 | case 1: /* remove */ | |||
| 502 | if (gene[i].pk + gene[i].nk <= CCV_BBF_POINT_MIN(3)) /* at least 3 points have to be examed */ | |||
| 503 | break; | |||
| 504 | while (*pnk[pn] - 1 <= 0) // || *pnk[pn] + *pnk[!pn] - 1 < CCV_BBF_POINT_MIN) | |||
| 505 | pn = gsl_rng_uniform_int(rng, 2); | |||
| 506 | victim = gsl_rng_uniform_int(rng, *pnk[pn]); | |||
| 507 | for (j = victim; j < *pnk[pn] - 1; j++) | |||
| 508 | { | |||
| 509 | pnz[pn][j] = pnz[pn][j + 1]; | |||
| 510 | pnx[pn][j] = pnx[pn][j + 1]; | |||
| 511 | pny[pn][j] = pny[pn][j + 1]; | |||
| 512 | } | |||
| 513 | pnz[pn][*pnk[pn] - 1] = -1; | |||
| 514 | --(*pnk[pn]); | |||
| 515 | gene[i].feature.size = ccv_max(gene[i].pk, gene[i].nk)({ typeof (gene[i].pk) _a = (gene[i].pk); typeof (gene[i].nk) _b = (gene[i].nk); (_a > _b) ? _a : _b; }); | |||
| 516 | decay = gene[i].age = 0; | |||
| 517 | break; | |||
| 518 | case 2: /* refine */ | |||
| 519 | pnm = gsl_rng_uniform_int(rng, *pnk[pn]); | |||
| 520 | do { | |||
| 521 | z = gsl_rng_uniform_int(rng, 3); | |||
| 522 | x = gsl_rng_uniform_int(rng, cols[z]); | |||
| 523 | y = gsl_rng_uniform_int(rng, rows[z]); | |||
| 524 | } while (_ccv_bbf_exist_gene_feature(&gene[i], x, y, z)); | |||
| 525 | pnz[pn][pnm] = z; | |||
| 526 | pnx[pn][pnm] = x; | |||
| 527 | pny[pn][pnm] = y; | |||
| 528 | decay = gene[i].age = 0; | |||
| 529 | break; | |||
| 530 | } | |||
| 531 | } while (decay); | |||
| 532 | } | |||
| 533 | for (i = ftnum + mnum; i < ftnum + mnum + hnum; i++) | |||
| 534 | { | |||
| 535 | /* hybrid strategy: taking positive points from dad, negative points from mum */ | |||
| 536 | int dad, mum; | |||
| 537 | do { | |||
| 538 | dad = gsl_rng_uniform_int(rng, ftnum); | |||
| 539 | mum = gsl_rng_uniform_int(rng, ftnum); | |||
| 540 | } while (dad == mum || gene[dad].pk + gene[mum].nk < CCV_BBF_POINT_MIN(3)); /* at least 3 points have to be examed */ | |||
| 541 | for (j = 0; j < CCV_BBF_POINT_MAX(8); j++) | |||
| 542 | { | |||
| 543 | gene[i].feature.pz[j] = -1; | |||
| 544 | gene[i].feature.nz[j] = -1; | |||
| 545 | } | |||
| 546 | gene[i].pk = gene[dad].pk; | |||
| 547 | for (j = 0; j < gene[i].pk; j++) | |||
| 548 | { | |||
| 549 | gene[i].feature.pz[j] = gene[dad].feature.pz[j]; | |||
| 550 | gene[i].feature.px[j] = gene[dad].feature.px[j]; | |||
| 551 | gene[i].feature.py[j] = gene[dad].feature.py[j]; | |||
| 552 | } | |||
| 553 | gene[i].nk = gene[mum].nk; | |||
| 554 | for (j = 0; j < gene[i].nk; j++) | |||
| 555 | { | |||
| 556 | gene[i].feature.nz[j] = gene[mum].feature.nz[j]; | |||
| 557 | gene[i].feature.nx[j] = gene[mum].feature.nx[j]; | |||
| 558 | gene[i].feature.ny[j] = gene[mum].feature.ny[j]; | |||
| 559 | } | |||
| 560 | gene[i].feature.size = ccv_max(gene[i].pk, gene[i].nk)({ typeof (gene[i].pk) _a = (gene[i].pk); typeof (gene[i].nk) _b = (gene[i].nk); (_a > _b) ? _a : _b; }); | |||
| 561 | gene[i].age = 0; | |||
| 562 | } | |||
| 563 | for (i = ftnum + mnum + hnum; i < ftnum + mnum + hnum + rnum; i++) | |||
| 564 | _ccv_bbf_randomize_gene(rng, &gene[i], rows, cols); | |||
| 565 | timer = _ccv_bbf_time_measure(); | |||
| 566 | #ifdef USE_OPENMP | |||
| 567 | #pragma omp parallel for private(i) schedule(dynamic) | |||
| 568 | #endif | |||
| 569 | for (i = 0; i < pnum; i++) | |||
| 570 | gene[i].error = _ccv_bbf_error_rate(&gene[i].feature, posdata, posnum, negdata, negnum, size, pw, nw); | |||
| 571 | timer = _ccv_bbf_time_measure() - timer; | |||
| 572 | for (i = 0; i < pnum; i++) | |||
| 573 | _ccv_bbf_genetic_fitness(&gene[i]); | |||
| 574 | } | |||
| 575 | ccfreefree(gene); | |||
| 576 | gsl_rng_free(rng); | |||
| 577 | return best; | |||
| 578 | } | |||
| 579 | ||||
| 580 | #define less_than(fit1, fit2, aux) ((fit1).error < (fit2).error) | |||
| 581 | static CCV_IMPLEMENT_QSORT(_ccv_bbf_best_qsort, ccv_bbf_gene_t, less_than)void _ccv_bbf_best_qsort(ccv_bbf_gene_t *array, size_t total, int aux) { int isort_thresh = 7; ccv_bbf_gene_t t; int sp = 0 ; struct { ccv_bbf_gene_t *lb; ccv_bbf_gene_t *ub; } stack[48 ]; if( total <= 1 ) return; stack[0].lb = array; stack[0]. ub = array + (total - 1); while( sp >= 0 ) { ccv_bbf_gene_t * left = stack[sp].lb; ccv_bbf_gene_t* right = stack[sp--].ub ; for(;;) { int i, n = (int)(right - left) + 1, m; ccv_bbf_gene_t * ptr; ccv_bbf_gene_t* ptr2; if( n <= isort_thresh ) { insert_sort : for( ptr = left + 1; ptr <= right; ptr++ ) { for( ptr2 = ptr; ptr2 > left && less_than(ptr2[0],ptr2[-1], aux ); ptr2--) (((t)) = ((ptr2[0])), ((ptr2[0])) = ((ptr2[-1])), ( (ptr2[-1])) = ((t))); } break; } else { ccv_bbf_gene_t* left0 ; ccv_bbf_gene_t* left1; ccv_bbf_gene_t* right0; ccv_bbf_gene_t * right1; ccv_bbf_gene_t* pivot; ccv_bbf_gene_t* a; ccv_bbf_gene_t * b; ccv_bbf_gene_t* c; int swap_cnt = 0; left0 = left; right0 = right; pivot = left + (n/2); if( n > 40 ) { int d = n / 8; a = left, b = left + d, c = left + 2*d; left = less_than( *a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than(*a, * c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than( *a, *c, aux) ? a : c)); a = pivot - d, b = pivot, c = pivot + d; pivot = less_than(*a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux ) ? b : (less_than(*a, *c, aux) ? a : c)); a = right - 2*d, b = right - d, c = right; right = less_than(*a, *b, aux) ? (less_than (*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than (*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); } a = left , b = pivot, c = right; pivot = less_than(*a, *b, aux) ? (less_than (*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than (*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); if( pivot != left0 ) { (((t)) = ((*pivot)), ((*pivot)) = ((*left0)), ( (*left0)) = ((t))); pivot = left0; } left = left1 = left0 + 1 ; right = right1 = right0; for(;;) { while( left <= right && !less_than(*pivot, *left, aux) ) { if( !less_than(*left, *pivot , aux) ) { if( left > left1 ) (((t)) = ((*left1)), ((*left1 )) = ((*left)), ((*left)) = ((t))); swap_cnt = 1; left1++; } left ++; } while( left <= right && !less_than(*right, * pivot, aux) ) { if( !less_than(*pivot, *right, aux) ) { if( right < right1 ) (((t)) = ((*right1)), ((*right1)) = ((*right)) , ((*right)) = ((t))); swap_cnt = 1; right1--; } right--; } if ( left > right ) break; (((t)) = ((*left)), ((*left)) = (( *right)), ((*right)) = ((t))); swap_cnt = 1; left++; right--; } if( swap_cnt == 0 ) { left = left0, right = right0; goto insert_sort ; } n = ({ typeof ((int)(left1 - left0)) _a = ((int)(left1 - left0 )); typeof ((int)(left - left1)) _b = ((int)(left - left1)); ( _a < _b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t)) = ((left0[i])), ((left0[i])) = ((left[i-n])), ((left[i-n])) = ((t))); n = ({ typeof ((int)(right0 - right1)) _a = ((int)(right0 - right1)); typeof ((int)(right1 - right)) _b = ((int)(right1 - right)); (_a < _b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t)) = ((left[i])), ((left[i])) = ((right0[i-n+1])), ((right0[i-n+1])) = ((t))); n = (int)(left - left1); m = (int )(right1 - right); if( n > 1 ) { if( m > 1 ) { if( n > m ) { stack[++sp].lb = left0; stack[sp].ub = left0 + n - 1; left = right0 - m + 1, right = right0; } else { stack[++sp].lb = right0 - m + 1; stack[sp].ub = right0; left = left0, right = left0 + n - 1; } } else left = left0, right = left0 + n - 1; } else if ( m > 1 ) left = right0 - m + 1, right = right0; else break ; } } } } | |||
| 582 | #undef less_than | |||
| 583 | ||||
| 584 | static ccv_bbf_gene_t _ccv_bbf_best_gene(ccv_bbf_gene_t* gene, int pnum, int point_min, unsigned char** posdata, int posnum, unsigned char** negdata, int negnum, ccv_size_t size, double* pw, double* nw) | |||
| 585 | { | |||
| 586 | int i = 0; | |||
| 587 | unsigned int timer = _ccv_bbf_time_measure(); | |||
| 588 | #ifdef USE_OPENMP | |||
| 589 | #pragma omp parallel for private(i) schedule(dynamic) | |||
| 590 | #endif | |||
| 591 | for (i = 0; i < pnum; i++) | |||
| 592 | gene[i].error = _ccv_bbf_error_rate(&gene[i].feature, posdata, posnum, negdata, negnum, size, pw, nw); | |||
| 593 | timer = _ccv_bbf_time_measure() - timer; | |||
| 594 | _ccv_bbf_best_qsort(gene, pnum, 0); | |||
| 595 | int min_id = 0; | |||
| 596 | double min_err = gene[0].error; | |||
| 597 | for (i = 0; i < pnum; i++) | |||
| 598 | if (gene[i].nk + gene[i].pk >= point_min) | |||
| 599 | { | |||
| 600 | min_id = i; | |||
| 601 | min_err = gene[i].error; | |||
| 602 | break; | |||
| 603 | } | |||
| 604 | PRINT(CCV_CLI_INFO, "local best bbf feature with error %f\n|-size: %d\n|-positive point: ", min_err, gene[min_id].feature.size)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("local best bbf feature with error %f\n|-size: %d\n|-positive point: " , min_err, gene[min_id].feature.size); fflush(stdout); } } while (0); | |||
| 605 | for (i = 0; i < gene[min_id].feature.size; i++) | |||
| 606 | PRINT(CCV_CLI_INFO, "(%d %d %d), ", gene[min_id].feature.px[i], gene[min_id].feature.py[i], gene[min_id].feature.pz[i])do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("(%d %d %d), ", gene[min_id].feature.px[i], gene[min_id].feature .py[i], gene[min_id].feature.pz[i]); fflush(stdout); } } while (0); | |||
| 607 | PRINT(CCV_CLI_INFO, "\n|-negative point: ")do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\n|-negative point: "); fflush(stdout); } } while (0); | |||
| 608 | for (i = 0; i < gene[min_id].feature.size; i++) | |||
| 609 | PRINT(CCV_CLI_INFO, "(%d %d %d), ", gene[min_id].feature.nx[i], gene[min_id].feature.ny[i], gene[min_id].feature.nz[i])do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("(%d %d %d), ", gene[min_id].feature.nx[i], gene[min_id].feature .ny[i], gene[min_id].feature.nz[i]); fflush(stdout); } } while (0); | |||
| 610 | PRINT(CCV_CLI_INFO, "\nthe computation takes %d ms\n", timer / 1000)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("\nthe computation takes %d ms\n", timer / 1000); fflush(stdout ); } } while (0); | |||
| 611 | return gene[min_id]; | |||
| 612 | } | |||
| 613 | ||||
| 614 | static ccv_bbf_feature_t _ccv_bbf_convex_optimize(unsigned char** posdata, int posnum, unsigned char** negdata, int negnum, ccv_bbf_feature_t* best_feature, ccv_size_t size, double* pw, double* nw) | |||
| 615 | { | |||
| 616 | ccv_bbf_gene_t best_gene; | |||
| 617 | /* seed (random method) */ | |||
| 618 | gsl_rng_env_setup(); | |||
| 619 | gsl_rng* rng = gsl_rng_alloc(gsl_rng_default); | |||
| 620 | union { unsigned long int li; double db; } dbli; | |||
| 621 | dbli.db = pw[0] + nw[0]; | |||
| 622 | gsl_rng_set(rng, dbli.li); | |||
| 623 | int i, j, k, q, p, g, t; | |||
| 624 | int rows[] = { size.height, size.height >> 1, size.height >> 2 }; | |||
| 625 | int cols[] = { size.width, size.width >> 1, size.width >> 2 }; | |||
| 626 | int pnum = rows[0] * cols[0] + rows[1] * cols[1] + rows[2] * cols[2]; | |||
| 627 | ccv_bbf_gene_t* gene = (ccv_bbf_gene_t*)ccmallocmalloc((pnum * (CCV_BBF_POINT_MAX(8) * 2 + 1) * 2 + CCV_BBF_POINT_MAX(8) * 2 + 1) * sizeof(ccv_bbf_gene_t)); | |||
| 628 | if (best_feature == 0) | |||
| 629 | { | |||
| 630 | /* bootstrapping the best feature, start from two pixels, one for positive, one for negative | |||
| 631 | * the bootstrapping process go like this: first, it will assign a random pixel as positive | |||
| 632 | * and enumerate every possible pixel as negative, and pick the best one. Then, enumerate every | |||
| 633 | * possible pixel as positive, and pick the best one, until it converges */ | |||
| 634 | memset(&best_gene, 0, sizeof(ccv_bbf_gene_t)); | |||
| 635 | for (i = 0; i < CCV_BBF_POINT_MAX(8); i++) | |||
| 636 | best_gene.feature.pz[i] = best_gene.feature.nz[i] = -1; | |||
| 637 | best_gene.pk = 1; | |||
| 638 | best_gene.nk = 0; | |||
| 639 | best_gene.feature.size = 1; | |||
| 640 | best_gene.feature.pz[0] = gsl_rng_uniform_int(rng, 3); | |||
| 641 | best_gene.feature.px[0] = gsl_rng_uniform_int(rng, cols[best_gene.feature.pz[0]]); | |||
| 642 | best_gene.feature.py[0] = gsl_rng_uniform_int(rng, rows[best_gene.feature.pz[0]]); | |||
| 643 | for (t = 0; ; ++t) | |||
| 644 | { | |||
| 645 | g = 0; | |||
| 646 | if (t % 2 == 0) | |||
| 647 | { | |||
| 648 | for (i = 0; i < 3; i++) | |||
| 649 | for (j = 0; j < cols[i]; j++) | |||
| 650 | for (k = 0; k < rows[i]; k++) | |||
| 651 | if (i != best_gene.feature.pz[0] || j != best_gene.feature.px[0] || k != best_gene.feature.py[0]) | |||
| 652 | { | |||
| 653 | gene[g] = best_gene; | |||
| 654 | gene[g].pk = gene[g].nk = 1; | |||
| 655 | gene[g].feature.nz[0] = i; | |||
| 656 | gene[g].feature.nx[0] = j; | |||
| 657 | gene[g].feature.ny[0] = k; | |||
| 658 | g++; | |||
| 659 | } | |||
| 660 | } else { | |||
| 661 | for (i = 0; i < 3; i++) | |||
| 662 | for (j = 0; j < cols[i]; j++) | |||
| 663 | for (k = 0; k < rows[i]; k++) | |||
| 664 | if (i != best_gene.feature.nz[0] || j != best_gene.feature.nx[0] || k != best_gene.feature.ny[0]) | |||
| 665 | { | |||
| 666 | gene[g] = best_gene; | |||
| 667 | gene[g].pk = gene[g].nk = 1; | |||
| 668 | gene[g].feature.pz[0] = i; | |||
| 669 | gene[g].feature.px[0] = j; | |||
| 670 | gene[g].feature.py[0] = k; | |||
| 671 | g++; | |||
| 672 | } | |||
| 673 | } | |||
| 674 | PRINT(CCV_CLI_INFO, "bootstrapping round : %d\n", t)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("bootstrapping round : %d\n", t); fflush(stdout); } } while ( 0); | |||
| 675 | ccv_bbf_gene_t local_gene = _ccv_bbf_best_gene(gene, g, 2, posdata, posnum, negdata, negnum, size, pw, nw); | |||
| 676 | if (local_gene.error >= best_gene.error - 1e-10) | |||
| 677 | break; | |||
| 678 | best_gene = local_gene; | |||
| 679 | } | |||
| 680 | } else { | |||
| 681 | best_gene.feature = *best_feature; | |||
| 682 | best_gene.pk = best_gene.nk = best_gene.feature.size; | |||
| 683 | for (i = 0; i < CCV_BBF_POINT_MAX(8); i++) | |||
| 684 | if (best_feature->pz[i] == -1) | |||
| 685 | { | |||
| 686 | best_gene.pk = i; | |||
| 687 | break; | |||
| 688 | } | |||
| 689 | for (i = 0; i < CCV_BBF_POINT_MAX(8); i++) | |||
| 690 | if (best_feature->nz[i] == -1) | |||
| 691 | { | |||
| 692 | best_gene.nk = i; | |||
| 693 | break; | |||
| 694 | } | |||
| 695 | } | |||
| 696 | /* after bootstrapping, the float search technique will do the following permutations: | |||
| 697 | * a). add a new point to positive or negative | |||
| 698 | * b). remove a point from positive or negative | |||
| 699 | * c). move an existing point in positive or negative to another position | |||
| 700 | * the three rules applied exhaustively, no heuristic used. */ | |||
| 701 | for (t = 0; ; ++t) | |||
| 702 | { | |||
| 703 | g = 0; | |||
| 704 | for (i = 0; i < 3; i++) | |||
| 705 | for (j = 0; j < cols[i]; j++) | |||
| 706 | for (k = 0; k < rows[i]; k++) | |||
| 707 | if (!_ccv_bbf_exist_gene_feature(&best_gene, j, k, i)) | |||
| 708 | { | |||
| 709 | /* add positive point */ | |||
| 710 | if (best_gene.pk < CCV_BBF_POINT_MAX(8) - 1) | |||
| 711 | { | |||
| 712 | gene[g] = best_gene; | |||
| 713 | gene[g].feature.pz[gene[g].pk] = i; | |||
| 714 | gene[g].feature.px[gene[g].pk] = j; | |||
| 715 | gene[g].feature.py[gene[g].pk] = k; | |||
| 716 | gene[g].pk++; | |||
| 717 | gene[g].feature.size = ccv_max(gene[g].pk, gene[g].nk)({ typeof (gene[g].pk) _a = (gene[g].pk); typeof (gene[g].nk) _b = (gene[g].nk); (_a > _b) ? _a : _b; }); | |||
| 718 | g++; | |||
| 719 | } | |||
| 720 | /* add negative point */ | |||
| 721 | if (best_gene.nk < CCV_BBF_POINT_MAX(8) - 1) | |||
| 722 | { | |||
| 723 | gene[g] = best_gene; | |||
| 724 | gene[g].feature.nz[gene[g].nk] = i; | |||
| 725 | gene[g].feature.nx[gene[g].nk] = j; | |||
| 726 | gene[g].feature.ny[gene[g].nk] = k; | |||
| 727 | gene[g].nk++; | |||
| 728 | gene[g].feature.size = ccv_max(gene[g].pk, gene[g].nk)({ typeof (gene[g].pk) _a = (gene[g].pk); typeof (gene[g].nk) _b = (gene[g].nk); (_a > _b) ? _a : _b; }); | |||
| 729 | g++; | |||
| 730 | } | |||
| 731 | /* refine positive point */ | |||
| 732 | for (q = 0; q < best_gene.pk; q++) | |||
| 733 | { | |||
| 734 | gene[g] = best_gene; | |||
| 735 | gene[g].feature.pz[q] = i; | |||
| 736 | gene[g].feature.px[q] = j; | |||
| 737 | gene[g].feature.py[q] = k; | |||
| 738 | g++; | |||
| 739 | } | |||
| 740 | /* add positive point, remove negative point */ | |||
| 741 | if (best_gene.pk < CCV_BBF_POINT_MAX(8) - 1 && best_gene.nk > 1) | |||
| 742 | { | |||
| 743 | for (q = 0; q < best_gene.nk; q++) | |||
| 744 | { | |||
| 745 | gene[g] = best_gene; | |||
| 746 | gene[g].feature.pz[gene[g].pk] = i; | |||
| 747 | gene[g].feature.px[gene[g].pk] = j; | |||
| 748 | gene[g].feature.py[gene[g].pk] = k; | |||
| 749 | gene[g].pk++; | |||
| 750 | for (p = q; p < best_gene.nk - 1; p++) | |||
| 751 | { | |||
| 752 | gene[g].feature.nz[p] = gene[g].feature.nz[p + 1]; | |||
| 753 | gene[g].feature.nx[p] = gene[g].feature.nx[p + 1]; | |||
| 754 | gene[g].feature.ny[p] = gene[g].feature.ny[p + 1]; | |||
| 755 | } | |||
| 756 | gene[g].feature.nz[gene[g].nk - 1] = -1; | |||
| 757 | gene[g].nk--; | |||
| 758 | gene[g].feature.size = ccv_max(gene[g].pk, gene[g].nk)({ typeof (gene[g].pk) _a = (gene[g].pk); typeof (gene[g].nk) _b = (gene[g].nk); (_a > _b) ? _a : _b; }); | |||
| 759 | g++; | |||
| 760 | } | |||
| 761 | } | |||
| 762 | /* refine negative point */ | |||
| 763 | for (q = 0; q < best_gene.nk; q++) | |||
| 764 | { | |||
| 765 | gene[g] = best_gene; | |||
| 766 | gene[g].feature.nz[q] = i; | |||
| 767 | gene[g].feature.nx[q] = j; | |||
| 768 | gene[g].feature.ny[q] = k; | |||
| 769 | g++; | |||
| 770 | } | |||
| 771 | /* add negative point, remove positive point */ | |||
| 772 | if (best_gene.pk > 1 && best_gene.nk < CCV_BBF_POINT_MAX(8) - 1) | |||
| 773 | { | |||
| 774 | for (q = 0; q < best_gene.pk; q++) | |||
| 775 | { | |||
| 776 | gene[g] = best_gene; | |||
| 777 | gene[g].feature.nz[gene[g].nk] = i; | |||
| 778 | gene[g].feature.nx[gene[g].nk] = j; | |||
| 779 | gene[g].feature.ny[gene[g].nk] = k; | |||
| 780 | gene[g].nk++; | |||
| 781 | for (p = q; p < best_gene.pk - 1; p++) | |||
| 782 | { | |||
| 783 | gene[g].feature.pz[p] = gene[g].feature.pz[p + 1]; | |||
| 784 | gene[g].feature.px[p] = gene[g].feature.px[p + 1]; | |||
| 785 | gene[g].feature.py[p] = gene[g].feature.py[p + 1]; | |||
| 786 | } | |||
| 787 | gene[g].feature.pz[gene[g].pk - 1] = -1; | |||
| 788 | gene[g].pk--; | |||
| 789 | gene[g].feature.size = ccv_max(gene[g].pk, gene[g].nk)({ typeof (gene[g].pk) _a = (gene[g].pk); typeof (gene[g].nk) _b = (gene[g].nk); (_a > _b) ? _a : _b; }); | |||
| 790 | g++; | |||
| 791 | } | |||
| 792 | } | |||
| 793 | } | |||
| 794 | if (best_gene.pk > 1) | |||
| 795 | for (q = 0; q < best_gene.pk; q++) | |||
| 796 | { | |||
| 797 | gene[g] = best_gene; | |||
| 798 | for (i = q; i < best_gene.pk - 1; i++) | |||
| 799 | { | |||
| 800 | gene[g].feature.pz[i] = gene[g].feature.pz[i + 1]; | |||
| 801 | gene[g].feature.px[i] = gene[g].feature.px[i + 1]; | |||
| 802 | gene[g].feature.py[i] = gene[g].feature.py[i + 1]; | |||
| 803 | } | |||
| 804 | gene[g].feature.pz[gene[g].pk - 1] = -1; | |||
| 805 | gene[g].pk--; | |||
| 806 | gene[g].feature.size = ccv_max(gene[g].pk, gene[g].nk)({ typeof (gene[g].pk) _a = (gene[g].pk); typeof (gene[g].nk) _b = (gene[g].nk); (_a > _b) ? _a : _b; }); | |||
| 807 | g++; | |||
| 808 | } | |||
| 809 | if (best_gene.nk > 1) | |||
| 810 | for (q = 0; q < best_gene.nk; q++) | |||
| 811 | { | |||
| 812 | gene[g] = best_gene; | |||
| 813 | for (i = q; i < best_gene.nk - 1; i++) | |||
| 814 | { | |||
| 815 | gene[g].feature.nz[i] = gene[g].feature.nz[i + 1]; | |||
| 816 | gene[g].feature.nx[i] = gene[g].feature.nx[i + 1]; | |||
| 817 | gene[g].feature.ny[i] = gene[g].feature.ny[i + 1]; | |||
| 818 | } | |||
| 819 | gene[g].feature.nz[gene[g].nk - 1] = -1; | |||
| 820 | gene[g].nk--; | |||
| 821 | gene[g].feature.size = ccv_max(gene[g].pk, gene[g].nk)({ typeof (gene[g].pk) _a = (gene[g].pk); typeof (gene[g].nk) _b = (gene[g].nk); (_a > _b) ? _a : _b; }); | |||
| 822 | g++; | |||
| 823 | } | |||
| 824 | gene[g] = best_gene; | |||
| 825 | g++; | |||
| 826 | PRINT(CCV_CLI_INFO, "float search round : %d\n", t)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("float search round : %d\n", t); fflush(stdout); } } while ( 0); | |||
| 827 | ccv_bbf_gene_t local_gene = _ccv_bbf_best_gene(gene, g, CCV_BBF_POINT_MIN(3), posdata, posnum, negdata, negnum, size, pw, nw); | |||
| 828 | if (local_gene.error >= best_gene.error - 1e-10) | |||
| 829 | break; | |||
| 830 | best_gene = local_gene; | |||
| 831 | } | |||
| 832 | ccfreefree(gene); | |||
| 833 | gsl_rng_free(rng); | |||
| 834 | return best_gene.feature; | |||
| 835 | } | |||
| 836 | ||||
| 837 | static int _ccv_write_bbf_stage_classifier(const char* file, ccv_bbf_stage_classifier_t* classifier) | |||
| 838 | { | |||
| 839 | FILE* w = fopen(file, "wb"); | |||
| 840 | if (w == 0) return -1; | |||
| 841 | fprintf(w, "%d\n", classifier->count); | |||
| 842 | union { float fl; int i; } fli; | |||
| 843 | fli.fl = classifier->threshold; | |||
| 844 | fprintf(w, "%d\n", fli.i); | |||
| 845 | int i, j; | |||
| 846 | for (i = 0; i < classifier->count; i++) | |||
| 847 | { | |||
| 848 | fprintf(w, "%d\n", classifier->feature[i].size); | |||
| 849 | for (j = 0; j < classifier->feature[i].size; j++) | |||
| 850 | { | |||
| 851 | fprintf(w, "%d %d %d\n", classifier->feature[i].px[j], classifier->feature[i].py[j], classifier->feature[i].pz[j]); | |||
| 852 | fprintf(w, "%d %d %d\n", classifier->feature[i].nx[j], classifier->feature[i].ny[j], classifier->feature[i].nz[j]); | |||
| 853 | } | |||
| 854 | union { float fl; int i; } flia, flib; | |||
| 855 | flia.fl = classifier->alpha[i * 2]; | |||
| 856 | flib.fl = classifier->alpha[i * 2 + 1]; | |||
| 857 | fprintf(w, "%d %d\n", flia.i, flib.i); | |||
| 858 | } | |||
| 859 | fclose(w); | |||
| 860 | return 0; | |||
| 861 | } | |||
| 862 | ||||
| 863 | static int _ccv_read_background_data(const char* file, unsigned char** negdata, int* negnum, ccv_size_t size) | |||
| 864 | { | |||
| 865 | FILE* r = fopen(file, "rb"); | |||
| 866 | if (r == 0) return -1; | |||
| 867 | (void)fread(negnum, sizeof(int), 1, r); | |||
| 868 | int i; | |||
| 869 | int isizs012 = _ccv_width_padding(size.width)(((size.width) + 3) & -4) * size.height + | |||
| 870 | _ccv_width_padding(size.width >> 1)(((size.width >> 1) + 3) & -4) * (size.height >> 1) + | |||
| 871 | _ccv_width_padding(size.width >> 2)(((size.width >> 2) + 3) & -4) * (size.height >> 2); | |||
| 872 | for (i = 0; i < *negnum; i++) | |||
| 873 | { | |||
| 874 | negdata[i] = (unsigned char*)ccmallocmalloc(isizs012); | |||
| 875 | (void)fread(negdata[i], 1, isizs012, r); | |||
| 876 | } | |||
| 877 | fclose(r); | |||
| 878 | return 0; | |||
| 879 | } | |||
| 880 | ||||
| 881 | static int _ccv_write_background_data(const char* file, unsigned char** negdata, int negnum, ccv_size_t size) | |||
| 882 | { | |||
| 883 | FILE* w = fopen(file, "w"); | |||
| 884 | if (w == 0) return -1; | |||
| 885 | fwrite(&negnum, sizeof(int), 1, w); | |||
| 886 | int i; | |||
| 887 | int isizs012 = _ccv_width_padding(size.width)(((size.width) + 3) & -4) * size.height + | |||
| 888 | _ccv_width_padding(size.width >> 1)(((size.width >> 1) + 3) & -4) * (size.height >> 1) + | |||
| 889 | _ccv_width_padding(size.width >> 2)(((size.width >> 2) + 3) & -4) * (size.height >> 2); | |||
| 890 | for (i = 0; i < negnum; i++) | |||
| 891 | fwrite(negdata[i], 1, isizs012, w); | |||
| 892 | fclose(w); | |||
| 893 | return 0; | |||
| 894 | } | |||
| 895 | ||||
| 896 | static int _ccv_resume_bbf_cascade_training_state(const char* file, int* i, int* k, int* bg, double* pw, double* nw, int posnum, int negnum) | |||
| 897 | { | |||
| 898 | FILE* r = fopen(file, "r"); | |||
| 899 | if (r
| |||
| 900 | (void)fscanf(r, "%d %d %d", i, k, bg); | |||
| 901 | int j; | |||
| 902 | union { double db; int i[2]; } dbi; | |||
| 903 | for (j = 0; j < posnum; j++) | |||
| 904 | { | |||
| 905 | (void)fscanf(r, "%d %d", &dbi.i[0], &dbi.i[1]); | |||
| 906 | pw[j] = dbi.db; | |||
| 907 | } | |||
| 908 | for (j = 0; j < negnum; j++) | |||
| 909 | { | |||
| 910 | (void)fscanf(r, "%d %d", &dbi.i[0], &dbi.i[1]); | |||
| 911 | nw[j] = dbi.db; | |||
| 912 | } | |||
| 913 | fclose(r); | |||
| 914 | return 0; | |||
| 915 | } | |||
| 916 | ||||
| 917 | static int _ccv_save_bbf_cacade_training_state(const char* file, int i, int k, int bg, double* pw, double* nw, int posnum, int negnum) | |||
| 918 | { | |||
| 919 | FILE* w = fopen(file, "w"); | |||
| 920 | if (w
| |||
| 921 | fprintf(w, "%d %d %d\n", i, k, bg); | |||
| 922 | int j; | |||
| 923 | union { double db; int i[2]; } dbi; | |||
| 924 | for (j = 0; j < posnum; ++j) | |||
| 925 | { | |||
| 926 | dbi.db = pw[j]; | |||
| 927 | fprintf(w, "%d %d ", dbi.i[0], dbi.i[1]); | |||
| 928 | } | |||
| 929 | fprintf(w, "\n"); | |||
| 930 | for (j = 0; j < negnum; ++j) | |||
| 931 | { | |||
| 932 | dbi.db = nw[j]; | |||
| ||||
| 933 | fprintf(w, "%d %d ", dbi.i[0], dbi.i[1]); | |||
| 934 | } | |||
| 935 | fprintf(w, "\n"); | |||
| 936 | fclose(w); | |||
| 937 | return 0; | |||
| 938 | } | |||
| 939 | ||||
| 940 | void ccv_bbf_classifier_cascade_new(ccv_dense_matrix_t** posimg, int posnum, char** bgfiles, int bgnum, int negnum, ccv_size_t size, const char* dir, ccv_bbf_new_param_t params) | |||
| 941 | { | |||
| 942 | int i, j, k; | |||
| 943 | /* allocate memory for usage */ | |||
| 944 | ccv_bbf_classifier_cascade_t* cascade = (ccv_bbf_classifier_cascade_t*)ccmallocmalloc(sizeof(ccv_bbf_classifier_cascade_t)); | |||
| 945 | cascade->count = 0; | |||
| 946 | cascade->size = size; | |||
| 947 | cascade->stage_classifier = (ccv_bbf_stage_classifier_t*)ccmallocmalloc(sizeof(ccv_bbf_stage_classifier_t)); | |||
| 948 | unsigned char** posdata = (unsigned char**)ccmallocmalloc(posnum * sizeof(unsigned char*)); | |||
| 949 | unsigned char** negdata = (unsigned char**)ccmallocmalloc(negnum * sizeof(unsigned char*)); | |||
| 950 | double* pw = (double*)ccmallocmalloc(posnum * sizeof(double)); | |||
| 951 | double* nw = (double*)ccmallocmalloc(negnum * sizeof(double)); | |||
| ||||
| 952 | float* peval = (float*)ccmallocmalloc(posnum * sizeof(float)); | |||
| 953 | float* neval = (float*)ccmallocmalloc(negnum * sizeof(float)); | |||
| 954 | double inv_balance_k = 1. / params.balance_k; | |||
| 955 | /* balance factor k, and weighted with 0.01 */ | |||
| 956 | params.balance_k *= 0.01; | |||
| 957 | inv_balance_k *= 0.01; | |||
| 958 | ||||
| 959 | int steps[] = { _ccv_width_padding(cascade->size.width)(((cascade->size.width) + 3) & -4), | |||
| 960 | _ccv_width_padding(cascade->size.width >> 1)(((cascade->size.width >> 1) + 3) & -4), | |||
| 961 | _ccv_width_padding(cascade->size.width >> 2)(((cascade->size.width >> 2) + 3) & -4) }; | |||
| 962 | int isizs0 = steps[0] * cascade->size.height; | |||
| 963 | int isizs01 = isizs0 + steps[1] * (cascade->size.height >> 1); | |||
| 964 | ||||
| 965 | i = 0; | |||
| 966 | k = 0; | |||
| 967 | int bg = 0; | |||
| 968 | int cacheK = 10; | |||
| 969 | /* state resume code */ | |||
| 970 | char buf[1024]; | |||
| 971 | sprintf(buf, "%s/stat.txt", dir); | |||
| 972 | _ccv_resume_bbf_cascade_training_state(buf, &i, &k, &bg, pw, nw, posnum, negnum); | |||
| 973 | if (i
| |||
| 974 | { | |||
| 975 | cascade->count = i; | |||
| 976 | ccfreefree(cascade->stage_classifier); | |||
| 977 | cascade->stage_classifier = (ccv_bbf_stage_classifier_t*)ccmallocmalloc(i * sizeof(ccv_bbf_stage_classifier_t)); | |||
| 978 | for (j = 0; j < i; j++) | |||
| 979 | { | |||
| 980 | sprintf(buf, "%s/stage-%d.txt", dir, j); | |||
| 981 | _ccv_read_bbf_stage_classifier(buf, &cascade->stage_classifier[j]); | |||
| 982 | } | |||
| 983 | } | |||
| 984 | if (k
| |||
| 985 | cacheK = k; | |||
| 986 | int rpos, rneg = 0; | |||
| 987 | if (bg
| |||
| 988 | { | |||
| 989 | sprintf(buf, "%s/negs.txt", dir); | |||
| 990 | _ccv_read_background_data(buf, negdata, &rneg, cascade->size); | |||
| 991 | } | |||
| 992 | ||||
| 993 | for (; i < params.layer; i++) | |||
| 994 | { | |||
| 995 | if (!bg
| |||
| 996 | { | |||
| 997 | rneg = _ccv_prepare_background_data(cascade, bgfiles, bgnum, negdata, negnum); | |||
| 998 | /* save state of background data */ | |||
| 999 | sprintf(buf, "%s/negs.txt", dir); | |||
| 1000 | _ccv_write_background_data(buf, negdata, rneg, cascade->size); | |||
| 1001 | bg = 1; | |||
| 1002 | } | |||
| 1003 | double totalw; | |||
| 1004 | /* save state of cascade : level, weight etc. */ | |||
| 1005 | sprintf(buf, "%s/stat.txt", dir); | |||
| 1006 | _ccv_save_bbf_cacade_training_state(buf, i, k, bg, pw, nw, posnum, negnum); | |||
| 1007 | ccv_bbf_stage_classifier_t classifier; | |||
| 1008 | if (k > 0) | |||
| 1009 | { | |||
| 1010 | /* resume state of classifier */ | |||
| 1011 | sprintf( buf, "%s/stage-%d.txt", dir, i ); | |||
| 1012 | _ccv_read_bbf_stage_classifier(buf, &classifier); | |||
| 1013 | } else { | |||
| 1014 | /* initialize classifier */ | |||
| 1015 | for (j = 0; j < posnum; j++) | |||
| 1016 | pw[j] = params.balance_k; | |||
| 1017 | for (j = 0; j < rneg; j++) | |||
| 1018 | nw[j] = inv_balance_k; | |||
| 1019 | classifier.count = k; | |||
| 1020 | classifier.threshold = 0; | |||
| 1021 | classifier.feature = (ccv_bbf_feature_t*)ccmallocmalloc(cacheK * sizeof(ccv_bbf_feature_t)); | |||
| 1022 | classifier.alpha = (float*)ccmallocmalloc(cacheK * 2 * sizeof(float)); | |||
| 1023 | } | |||
| 1024 | _ccv_prepare_positive_data(posimg, posdata, cascade->size, posnum); | |||
| 1025 | rpos = _ccv_prune_positive_data(cascade, posdata, posnum, cascade->size); | |||
| 1026 | PRINT(CCV_CLI_INFO, "%d postivie data and %d negative data in training\n", rpos, rneg)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("%d postivie data and %d negative data in training\n", rpos, rneg); fflush(stdout); } } while (0); | |||
| 1027 | /* reweight to 1.00 */ | |||
| 1028 | totalw = 0; | |||
| 1029 | for (j = 0; j < rpos; j++) | |||
| 1030 | totalw += pw[j]; | |||
| 1031 | for (j = 0; j < rneg; j++) | |||
| 1032 | totalw += nw[j]; | |||
| 1033 | for (j = 0; j < rpos; j++) | |||
| 1034 | pw[j] = pw[j] / totalw; | |||
| 1035 | for (j = 0; j < rneg; j++) | |||
| 1036 | nw[j] = nw[j] / totalw; | |||
| 1037 | for (; ; k++) | |||
| 1038 | { | |||
| 1039 | /* get overall true-positive, false-positive rate and threshold */ | |||
| 1040 | double tp = 0, fp = 0, etp = 0, efp = 0; | |||
| 1041 | _ccv_bbf_eval_data(&classifier, posdata, rpos, negdata, rneg, cascade->size, peval, neval); | |||
| 1042 | _ccv_sort_32f(peval, rpos, 0); | |||
| 1043 | classifier.threshold = peval[(int)((1. - params.pos_crit) * rpos)] - 1e-6; | |||
| 1044 | for (j = 0; j < rpos; j++) | |||
| 1045 | { | |||
| 1046 | if (peval[j] >= 0) | |||
| 1047 | ++tp; | |||
| 1048 | if (peval[j] >= classifier.threshold) | |||
| 1049 | ++etp; | |||
| 1050 | } | |||
| 1051 | tp /= rpos; etp /= rpos; | |||
| 1052 | for (j = 0; j < rneg; j++) | |||
| 1053 | { | |||
| 1054 | if (neval[j] >= 0) | |||
| 1055 | ++fp; | |||
| 1056 | if (neval[j] >= classifier.threshold) | |||
| 1057 | ++efp; | |||
| 1058 | } | |||
| 1059 | fp /= rneg; efp /= rneg; | |||
| 1060 | PRINT(CCV_CLI_INFO, "stage classifier real TP rate : %f, FP rate : %f\n", tp, fp)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("stage classifier real TP rate : %f, FP rate : %f\n", tp, fp ); fflush(stdout); } } while (0); | |||
| 1061 | PRINT(CCV_CLI_INFO, "stage classifier TP rate : %f, FP rate : %f at threshold : %f\n", etp, efp, classifier.threshold)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("stage classifier TP rate : %f, FP rate : %f at threshold : %f\n" , etp, efp, classifier.threshold); fflush(stdout); } } while ( 0); | |||
| 1062 | if (k > 0) | |||
| 1063 | { | |||
| 1064 | /* save classifier state */ | |||
| 1065 | sprintf(buf, "%s/stage-%d.txt", dir, i); | |||
| 1066 | _ccv_write_bbf_stage_classifier(buf, &classifier); | |||
| 1067 | sprintf(buf, "%s/stat.txt", dir); | |||
| 1068 | _ccv_save_bbf_cacade_training_state(buf, i, k, bg, pw, nw, posnum, negnum); | |||
| 1069 | } | |||
| 1070 | if (etp > params.pos_crit && efp < params.neg_crit) | |||
| 1071 | break; | |||
| 1072 | /* TODO: more post-process is needed in here */ | |||
| 1073 | ||||
| 1074 | /* select the best feature in current distribution through genetic algorithm optimization */ | |||
| 1075 | ccv_bbf_feature_t best; | |||
| 1076 | if (params.optimizer == CCV_BBF_GENETIC_OPT) | |||
| 1077 | { | |||
| 1078 | best = _ccv_bbf_genetic_optimize(posdata, rpos, negdata, rneg, params.feature_number, cascade->size, pw, nw); | |||
| 1079 | } else if (params.optimizer == CCV_BBF_FLOAT_OPT) { | |||
| 1080 | best = _ccv_bbf_convex_optimize(posdata, rpos, negdata, rneg, 0, cascade->size, pw, nw); | |||
| 1081 | } else { | |||
| 1082 | best = _ccv_bbf_genetic_optimize(posdata, rpos, negdata, rneg, params.feature_number, cascade->size, pw, nw); | |||
| 1083 | best = _ccv_bbf_convex_optimize(posdata, rpos, negdata, rneg, &best, cascade->size, pw, nw); | |||
| 1084 | } | |||
| 1085 | double err = _ccv_bbf_error_rate(&best, posdata, rpos, negdata, rneg, cascade->size, pw, nw); | |||
| 1086 | double rw = (1 - err) / err; | |||
| 1087 | totalw = 0; | |||
| 1088 | /* reweight */ | |||
| 1089 | for (j = 0; j < rpos; j++) | |||
| 1090 | { | |||
| 1091 | unsigned char* u8[] = { posdata[j], posdata[j] + isizs0, posdata[j] + isizs01 }; | |||
| 1092 | if (!_ccv_run_bbf_feature(&best, steps, u8)) | |||
| 1093 | pw[j] *= rw; | |||
| 1094 | pw[j] *= params.balance_k; | |||
| 1095 | totalw += pw[j]; | |||
| 1096 | } | |||
| 1097 | for (j = 0; j < rneg; j++) | |||
| 1098 | { | |||
| 1099 | unsigned char* u8[] = { negdata[j], negdata[j] + isizs0, negdata[j] + isizs01 }; | |||
| 1100 | if (_ccv_run_bbf_feature(&best, steps, u8)) | |||
| 1101 | nw[j] *= rw; | |||
| 1102 | nw[j] *= inv_balance_k; | |||
| 1103 | totalw += nw[j]; | |||
| 1104 | } | |||
| 1105 | for (j = 0; j < rpos; j++) | |||
| 1106 | pw[j] = pw[j] / totalw; | |||
| 1107 | for (j = 0; j < rneg; j++) | |||
| 1108 | nw[j] = nw[j] / totalw; | |||
| 1109 | double c = log(rw); | |||
| 1110 | PRINT(CCV_CLI_INFO, "coefficient of feature %d: %f\n", k + 1, c)do { if ((CCV_CLI_INFO & ccv_cli_get_output_levels())) { printf ("coefficient of feature %d: %f\n", k + 1, c); fflush(stdout) ; } } while (0); | |||
| 1111 | classifier.count = k + 1; | |||
| 1112 | /* resizing classifier */ | |||
| 1113 | if (k >= cacheK) | |||
| 1114 | { | |||
| 1115 | ccv_bbf_feature_t* feature = (ccv_bbf_feature_t*)ccmallocmalloc(cacheK * 2 * sizeof(ccv_bbf_feature_t)); | |||
| 1116 | memcpy(feature, classifier.feature, cacheK * sizeof(ccv_bbf_feature_t)); | |||
| 1117 | ccfreefree(classifier.feature); | |||
| 1118 | float* alpha = (float*)ccmallocmalloc(cacheK * 4 * sizeof(float)); | |||
| 1119 | memcpy(alpha, classifier.alpha, cacheK * 2 * sizeof(float)); | |||
| 1120 | ccfreefree(classifier.alpha); | |||
| 1121 | classifier.feature = feature; | |||
| 1122 | classifier.alpha = alpha; | |||
| 1123 | cacheK *= 2; | |||
| 1124 | } | |||
| 1125 | /* setup new feature */ | |||
| 1126 | classifier.feature[k] = best; | |||
| 1127 | classifier.alpha[k * 2] = -c; | |||
| 1128 | classifier.alpha[k * 2 + 1] = c; | |||
| 1129 | } | |||
| 1130 | cascade->count = i + 1; | |||
| 1131 | ccv_bbf_stage_classifier_t* stage_classifier = (ccv_bbf_stage_classifier_t*)ccmallocmalloc(cascade->count * sizeof(ccv_bbf_stage_classifier_t)); | |||
| 1132 | memcpy(stage_classifier, cascade->stage_classifier, i * sizeof(ccv_bbf_stage_classifier_t)); | |||
| 1133 | ccfreefree(cascade->stage_classifier); | |||
| 1134 | stage_classifier[i] = classifier; | |||
| 1135 | cascade->stage_classifier = stage_classifier; | |||
| 1136 | k = 0; | |||
| 1137 | bg = 0; | |||
| 1138 | for (j = 0; j < rpos; j++) | |||
| 1139 | ccfreefree(posdata[j]); | |||
| 1140 | for (j = 0; j < rneg; j++) | |||
| 1141 | ccfreefree(negdata[j]); | |||
| 1142 | } | |||
| 1143 | ||||
| 1144 | ccfreefree(neval); | |||
| 1145 | ccfreefree(peval); | |||
| 1146 | ccfreefree(nw); | |||
| 1147 | ccfreefree(pw); | |||
| 1148 | ccfreefree(negdata); | |||
| 1149 | ccfreefree(posdata); | |||
| 1150 | ccfreefree(cascade); | |||
| 1151 | } | |||
| 1152 | #else | |||
| 1153 | void ccv_bbf_classifier_cascade_new(ccv_dense_matrix_t** posimg, int posnum, char** bgfiles, int bgnum, int negnum, ccv_size_t size, const char* dir, ccv_bbf_new_param_t params) | |||
| 1154 | { | |||
| 1155 | fprintf(stderrstderr, " ccv_bbf_classifier_cascade_new requires libgsl support, please compile ccv with libgsl.\n"); | |||
| 1156 | } | |||
| 1157 | #endif | |||
| 1158 | ||||
| 1159 | static int _ccv_is_equal(const void* _r1, const void* _r2, void* data) | |||
| 1160 | { | |||
| 1161 | const ccv_comp_t* r1 = (const ccv_comp_t*)_r1; | |||
| 1162 | const ccv_comp_t* r2 = (const ccv_comp_t*)_r2; | |||
| 1163 | int distance = (int)(r1->rect.width * 0.25 + 0.5); | |||
| 1164 | ||||
| 1165 | return r2->rect.x <= r1->rect.x + distance && | |||
| 1166 | r2->rect.x >= r1->rect.x - distance && | |||
| 1167 | r2->rect.y <= r1->rect.y + distance && | |||
| 1168 | r2->rect.y >= r1->rect.y - distance && | |||
| 1169 | r2->rect.width <= (int)(r1->rect.width * 1.5 + 0.5) && | |||
| 1170 | (int)(r2->rect.width * 1.5 + 0.5) >= r1->rect.width; | |||
| 1171 | } | |||
| 1172 | ||||
| 1173 | static int _ccv_is_equal_same_class(const void* _r1, const void* _r2, void* data) | |||
| 1174 | { | |||
| 1175 | const ccv_comp_t* r1 = (const ccv_comp_t*)_r1; | |||
| 1176 | const ccv_comp_t* r2 = (const ccv_comp_t*)_r2; | |||
| 1177 | int distance = (int)(r1->rect.width * 0.25 + 0.5); | |||
| 1178 | ||||
| 1179 | return r2->classification.id == r1->classification.id && | |||
| 1180 | r2->rect.x <= r1->rect.x + distance && | |||
| 1181 | r2->rect.x >= r1->rect.x - distance && | |||
| 1182 | r2->rect.y <= r1->rect.y + distance && | |||
| 1183 | r2->rect.y >= r1->rect.y - distance && | |||
| 1184 | r2->rect.width <= (int)(r1->rect.width * 1.5 + 0.5) && | |||
| 1185 | (int)(r2->rect.width * 1.5 + 0.5) >= r1->rect.width; | |||
| 1186 | } | |||
| 1187 | ||||
| 1188 | ccv_array_t* ccv_bbf_detect_objects(ccv_dense_matrix_t* a, ccv_bbf_classifier_cascade_t** _cascade, int count, ccv_bbf_param_t params) | |||
| 1189 | { | |||
| 1190 | int hr = a->rows / params.size.height; | |||
| 1191 | int wr = a->cols / params.size.width; | |||
| 1192 | double scale = pow(2., 1. / (params.interval + 1.)); | |||
| 1193 | int next = params.interval + 1; | |||
| 1194 | int scale_upto = (int)(log((double)ccv_min(hr, wr)({ typeof (hr) _a = (hr); typeof (wr) _b = (wr); (_a < _b) ? _a : _b; })) / log(scale)); | |||
| 1195 | ccv_dense_matrix_t** pyr = (ccv_dense_matrix_t**)alloca((scale_upto + next * 2) * 4 * sizeof(ccv_dense_matrix_t*))__builtin_alloca ((scale_upto + next * 2) * 4 * sizeof(ccv_dense_matrix_t *)); | |||
| 1196 | memset(pyr, 0, (scale_upto + next * 2) * 4 * sizeof(ccv_dense_matrix_t*)); | |||
| 1197 | if (params.size.height != _cascade[0]->size.height || params.size.width != _cascade[0]->size.width) | |||
| 1198 | ccv_resample(a, &pyr[0], 0, (double)(a->rows * _cascade[0]->size.height / params.size.height) / (double)a->rows, (double)(a->cols * _cascade[0]->size.width / params.size.width) / (double)a->cols, CCV_INTER_AREA); | |||
| 1199 | else | |||
| 1200 | pyr[0] = a; | |||
| 1201 | int i, j, k, t, x, y, q; | |||
| 1202 | for (i = 1; i < ccv_min(params.interval + 1, scale_upto + next * 2)({ typeof (params.interval + 1) _a = (params.interval + 1); typeof (scale_upto + next * 2) _b = (scale_upto + next * 2); (_a < _b) ? _a : _b; }); i++) | |||
| 1203 | ccv_resample(pyr[0], &pyr[i * 4], 0, (double)(int)(pyr[0]->rows / pow(scale, i)) / (double)pyr[0]->rows, (double)(int)(pyr[0]->cols / pow(scale, i)) / (double)pyr[0]->cols, CCV_INTER_AREA); | |||
| 1204 | for (i = next; i < scale_upto + next * 2; i++) | |||
| 1205 | ccv_sample_down(pyr[i * 4 - next * 4], &pyr[i * 4], 0, 0, 0); | |||
| 1206 | if (params.accurate) | |||
| 1207 | for (i = next * 2; i < scale_upto + next * 2; i++) | |||
| 1208 | { | |||
| 1209 | ccv_sample_down(pyr[i * 4 - next * 4], &pyr[i * 4 + 1], 0, 1, 0); | |||
| 1210 | ccv_sample_down(pyr[i * 4 - next * 4], &pyr[i * 4 + 2], 0, 0, 1); | |||
| 1211 | ccv_sample_down(pyr[i * 4 - next * 4], &pyr[i * 4 + 3], 0, 1, 1); | |||
| 1212 | } | |||
| 1213 | ccv_array_t* idx_seq; | |||
| 1214 | ccv_array_t* seq = ccv_array_new(sizeof(ccv_comp_t), 64, 0); | |||
| 1215 | ccv_array_t* seq2 = ccv_array_new(sizeof(ccv_comp_t), 64, 0); | |||
| 1216 | ccv_array_t* result_seq = ccv_array_new(sizeof(ccv_comp_t), 64, 0); | |||
| 1217 | /* detect in multi scale */ | |||
| 1218 | for (t = 0; t < count; t++) | |||
| 1219 | { | |||
| 1220 | ccv_bbf_classifier_cascade_t* cascade = _cascade[t]; | |||
| 1221 | float scale_x = (float) params.size.width / (float) cascade->size.width; | |||
| 1222 | float scale_y = (float) params.size.height / (float) cascade->size.height; | |||
| 1223 | ccv_array_clear(seq); | |||
| 1224 | for (i = 0; i < scale_upto; i++) | |||
| 1225 | { | |||
| 1226 | int dx[] = {0, 1, 0, 1}; | |||
| 1227 | int dy[] = {0, 0, 1, 1}; | |||
| 1228 | int i_rows = pyr[i * 4 + next * 8]->rows - (cascade->size.height >> 2); | |||
| 1229 | int steps[] = { pyr[i * 4]->step, pyr[i * 4 + next * 4]->step, pyr[i * 4 + next * 8]->step }; | |||
| 1230 | int i_cols = pyr[i * 4 + next * 8]->cols - (cascade->size.width >> 2); | |||
| 1231 | int paddings[] = { pyr[i * 4]->step * 4 - i_cols * 4, | |||
| 1232 | pyr[i * 4 + next * 4]->step * 2 - i_cols * 2, | |||
| 1233 | pyr[i * 4 + next * 8]->step - i_cols }; | |||
| 1234 | for (q = 0; q < (params.accurate ? 4 : 1); q++) | |||
| 1235 | { | |||
| 1236 | unsigned char* u8[] = { pyr[i * 4]->data.u8 + dx[q] * 2 + dy[q] * pyr[i * 4]->step * 2, pyr[i * 4 + next * 4]->data.u8 + dx[q] + dy[q] * pyr[i * 4 + next * 4]->step, pyr[i * 4 + next * 8 + q]->data.u8 }; | |||
| 1237 | for (y = 0; y < i_rows; y++) | |||
| 1238 | { | |||
| 1239 | for (x = 0; x < i_cols; x++) | |||
| 1240 | { | |||
| 1241 | float sum; | |||
| 1242 | int flag = 1; | |||
| 1243 | ccv_bbf_stage_classifier_t* classifier = cascade->stage_classifier; | |||
| 1244 | for (j = 0; j < cascade->count; ++j, ++classifier) | |||
| 1245 | { | |||
| 1246 | sum = 0; | |||
| 1247 | float* alpha = classifier->alpha; | |||
| 1248 | ccv_bbf_feature_t* feature = classifier->feature; | |||
| 1249 | for (k = 0; k < classifier->count; ++k, alpha += 2, ++feature) | |||
| 1250 | sum += alpha[_ccv_run_bbf_feature(feature, steps, u8)]; | |||
| 1251 | if (sum < classifier->threshold) | |||
| 1252 | { | |||
| 1253 | flag = 0; | |||
| 1254 | break; | |||
| 1255 | } | |||
| 1256 | } | |||
| 1257 | if (flag) | |||
| 1258 | { | |||
| 1259 | ccv_comp_t comp; | |||
| 1260 | comp.rect = ccv_rect((int)((x * 4 + dx[q] * 2) * scale_x + 0.5), (int)((y * 4 + dy[q] * 2) * scale_y + 0.5), (int)(cascade->size.width * scale_x + 0.5), (int)(cascade->size.height * scale_y + 0.5)); | |||
| 1261 | comp.neighbors = 1; | |||
| 1262 | comp.classification.id = t; | |||
| 1263 | comp.classification.confidence = sum; | |||
| 1264 | ccv_array_push(seq, &comp); | |||
| 1265 | } | |||
| 1266 | u8[0] += 4; | |||
| 1267 | u8[1] += 2; | |||
| 1268 | u8[2] += 1; | |||
| 1269 | } | |||
| 1270 | u8[0] += paddings[0]; | |||
| 1271 | u8[1] += paddings[1]; | |||
| 1272 | u8[2] += paddings[2]; | |||
| 1273 | } | |||
| 1274 | } | |||
| 1275 | scale_x *= scale; | |||
| 1276 | scale_y *= scale; | |||
| 1277 | } | |||
| 1278 | ||||
| 1279 | /* the following code from OpenCV's haar feature implementation */ | |||
| 1280 | if(params.min_neighbors == 0) | |||
| 1281 | { | |||
| 1282 | for (i = 0; i < seq->rnum; i++) | |||
| 1283 | { | |||
| 1284 | ccv_comp_t* comp = (ccv_comp_t*)ccv_array_get(seq, i)((void*)(((char*)((seq)->data)) + (size_t)(seq)->rsize * (size_t)(i))); | |||
| 1285 | ccv_array_push(result_seq, comp); | |||
| 1286 | } | |||
| 1287 | } else { | |||
| 1288 | idx_seq = 0; | |||
| 1289 | ccv_array_clear(seq2); | |||
| 1290 | // group retrieved rectangles in order to filter out noise | |||
| 1291 | int ncomp = ccv_array_group(seq, &idx_seq, _ccv_is_equal_same_class, 0); | |||
| 1292 | ccv_comp_t* comps = (ccv_comp_t*)ccmallocmalloc((ncomp + 1) * sizeof(ccv_comp_t)); | |||
| 1293 | memset(comps, 0, (ncomp + 1) * sizeof(ccv_comp_t)); | |||
| 1294 | ||||
| 1295 | // count number of neighbors | |||
| 1296 | for(i = 0; i < seq->rnum; i++) | |||
| 1297 | { | |||
| 1298 | ccv_comp_t r1 = *(ccv_comp_t*)ccv_array_get(seq, i)((void*)(((char*)((seq)->data)) + (size_t)(seq)->rsize * (size_t)(i))); | |||
| 1299 | int idx = *(int*)ccv_array_get(idx_seq, i)((void*)(((char*)((idx_seq)->data)) + (size_t)(idx_seq)-> rsize * (size_t)(i))); | |||
| 1300 | ||||
| 1301 | if (comps[idx].neighbors == 0) | |||
| 1302 | comps[idx].classification.confidence = r1.classification.confidence; | |||
| 1303 | ||||
| 1304 | ++comps[idx].neighbors; | |||
| 1305 | ||||
| 1306 | comps[idx].rect.x += r1.rect.x; | |||
| 1307 | comps[idx].rect.y += r1.rect.y; | |||
| 1308 | comps[idx].rect.width += r1.rect.width; | |||
| 1309 | comps[idx].rect.height += r1.rect.height; | |||
| 1310 | comps[idx].classification.id = r1.classification.id; | |||
| 1311 | comps[idx].classification.confidence = ccv_max(comps[idx].classification.confidence, r1.classification.confidence)({ typeof (comps[idx].classification.confidence) _a = (comps[ idx].classification.confidence); typeof (r1.classification.confidence ) _b = (r1.classification.confidence); (_a > _b) ? _a : _b ; }); | |||
| 1312 | } | |||
| 1313 | ||||
| 1314 | // calculate average bounding box | |||
| 1315 | for(i = 0; i < ncomp; i++) | |||
| 1316 | { | |||
| 1317 | int n = comps[i].neighbors; | |||
| 1318 | if(n >= params.min_neighbors) | |||
| 1319 | { | |||
| 1320 | ccv_comp_t comp; | |||
| 1321 | comp.rect.x = (comps[i].rect.x * 2 + n) / (2 * n); | |||
| 1322 | comp.rect.y = (comps[i].rect.y * 2 + n) / (2 * n); | |||
| 1323 | comp.rect.width = (comps[i].rect.width * 2 + n) / (2 * n); | |||
| 1324 | comp.rect.height = (comps[i].rect.height * 2 + n) / (2 * n); | |||
| 1325 | comp.neighbors = comps[i].neighbors; | |||
| 1326 | comp.classification.id = comps[i].classification.id; | |||
| 1327 | comp.classification.confidence = comps[i].classification.confidence; | |||
| 1328 | ccv_array_push(seq2, &comp); | |||
| 1329 | } | |||
| 1330 | } | |||
| 1331 | ||||
| 1332 | // filter out small face rectangles inside large face rectangles | |||
| 1333 | for(i = 0; i < seq2->rnum; i++) | |||
| 1334 | { | |||
| 1335 | ccv_comp_t r1 = *(ccv_comp_t*)ccv_array_get(seq2, i)((void*)(((char*)((seq2)->data)) + (size_t)(seq2)->rsize * (size_t)(i))); | |||
| 1336 | int flag = 1; | |||
| 1337 | ||||
| 1338 | for(j = 0; j < seq2->rnum; j++) | |||
| 1339 | { | |||
| 1340 | ccv_comp_t r2 = *(ccv_comp_t*)ccv_array_get(seq2, j)((void*)(((char*)((seq2)->data)) + (size_t)(seq2)->rsize * (size_t)(j))); | |||
| 1341 | int distance = (int)(r2.rect.width * 0.25 + 0.5); | |||
| 1342 | ||||
| 1343 | if(i != j && | |||
| 1344 | r1.classification.id == r2.classification.id && | |||
| 1345 | r1.rect.x >= r2.rect.x - distance && | |||
| 1346 | r1.rect.y >= r2.rect.y - distance && | |||
| 1347 | r1.rect.x + r1.rect.width <= r2.rect.x + r2.rect.width + distance && | |||
| 1348 | r1.rect.y + r1.rect.height <= r2.rect.y + r2.rect.height + distance && | |||
| 1349 | (r2.neighbors > ccv_max(3, r1.neighbors)({ typeof (3) _a = (3); typeof (r1.neighbors) _b = (r1.neighbors ); (_a > _b) ? _a : _b; }) || r1.neighbors < 3)) | |||
| 1350 | { | |||
| 1351 | flag = 0; | |||
| 1352 | break; | |||
| 1353 | } | |||
| 1354 | } | |||
| 1355 | ||||
| 1356 | if(flag) | |||
| 1357 | ccv_array_push(result_seq, &r1); | |||
| 1358 | } | |||
| 1359 | ccv_array_free(idx_seq); | |||
| 1360 | ccfreefree(comps); | |||
| 1361 | } | |||
| 1362 | } | |||
| 1363 | ||||
| 1364 | ccv_array_free(seq); | |||
| 1365 | ccv_array_free(seq2); | |||
| 1366 | ||||
| 1367 | ccv_array_t* result_seq2; | |||
| 1368 | /* the following code from OpenCV's haar feature implementation */ | |||
| 1369 | if (params.flags & CCV_BBF_NO_NESTED) | |||
| 1370 | { | |||
| 1371 | result_seq2 = ccv_array_new(sizeof(ccv_comp_t), 64, 0); | |||
| 1372 | idx_seq = 0; | |||
| 1373 | // group retrieved rectangles in order to filter out noise | |||
| 1374 | int ncomp = ccv_array_group(result_seq, &idx_seq, _ccv_is_equal, 0); | |||
| 1375 | ccv_comp_t* comps = (ccv_comp_t*)ccmallocmalloc((ncomp + 1) * sizeof(ccv_comp_t)); | |||
| 1376 | memset(comps, 0, (ncomp + 1) * sizeof(ccv_comp_t)); | |||
| 1377 | ||||
| 1378 | // count number of neighbors | |||
| 1379 | for(i = 0; i < result_seq->rnum; i++) | |||
| 1380 | { | |||
| 1381 | ccv_comp_t r1 = *(ccv_comp_t*)ccv_array_get(result_seq, i)((void*)(((char*)((result_seq)->data)) + (size_t)(result_seq )->rsize * (size_t)(i))); | |||
| 1382 | int idx = *(int*)ccv_array_get(idx_seq, i)((void*)(((char*)((idx_seq)->data)) + (size_t)(idx_seq)-> rsize * (size_t)(i))); | |||
| 1383 | ||||
| 1384 | if (comps[idx].neighbors == 0 || comps[idx].classification.confidence < r1.classification.confidence) | |||
| 1385 | { | |||
| 1386 | comps[idx].classification.confidence = r1.classification.confidence; | |||
| 1387 | comps[idx].neighbors = 1; | |||
| 1388 | comps[idx].rect = r1.rect; | |||
| 1389 | comps[idx].classification.id = r1.classification.id; | |||
| 1390 | } | |||
| 1391 | } | |||
| 1392 | ||||
| 1393 | // calculate average bounding box | |||
| 1394 | for(i = 0; i < ncomp; i++) | |||
| 1395 | if(comps[i].neighbors) | |||
| 1396 | ccv_array_push(result_seq2, &comps[i]); | |||
| 1397 | ||||
| 1398 | ccv_array_free(result_seq); | |||
| 1399 | ccfreefree(comps); | |||
| 1400 | } else { | |||
| 1401 | result_seq2 = result_seq; | |||
| 1402 | } | |||
| 1403 | ||||
| 1404 | for (i = 1; i < scale_upto + next * 2; i++) | |||
| 1405 | ccv_matrix_free(pyr[i * 4]); | |||
| 1406 | if (params.accurate) | |||
| 1407 | for (i = next * 2; i < scale_upto + next * 2; i++) | |||
| 1408 | { | |||
| 1409 | ccv_matrix_free(pyr[i * 4 + 1]); | |||
| 1410 | ccv_matrix_free(pyr[i * 4 + 2]); | |||
| 1411 | ccv_matrix_free(pyr[i * 4 + 3]); | |||
| 1412 | } | |||
| 1413 | if (params.size.height != _cascade[0]->size.height || params.size.width != _cascade[0]->size.width) | |||
| 1414 | ccv_matrix_free(pyr[0]); | |||
| 1415 | ||||
| 1416 | return result_seq2; | |||
| 1417 | } | |||
| 1418 | ||||
| 1419 | ccv_bbf_classifier_cascade_t* ccv_bbf_read_classifier_cascade(const char* directory) | |||
| 1420 | { | |||
| 1421 | char buf[1024]; | |||
| 1422 | sprintf(buf, "%s/cascade.txt", directory); | |||
| 1423 | int s, i; | |||
| 1424 | FILE* r = fopen(buf, "r"); | |||
| 1425 | if (r == 0) | |||
| 1426 | return 0; | |||
| 1427 | ccv_bbf_classifier_cascade_t* cascade = (ccv_bbf_classifier_cascade_t*)ccmallocmalloc(sizeof(ccv_bbf_classifier_cascade_t)); | |||
| 1428 | s = fscanf(r, "%d %d %d", &cascade->count, &cascade->size.width, &cascade->size.height); | |||
| 1429 | assert(s > 0)((void) sizeof ((s > 0) ? 1 : 0), __extension__ ({ if (s > 0) ; else __assert_fail ("s > 0", "ccv_bbf.c", 1429, __extension__ __PRETTY_FUNCTION__); })); | |||
| 1430 | cascade->stage_classifier = (ccv_bbf_stage_classifier_t*)ccmallocmalloc(cascade->count * sizeof(ccv_bbf_stage_classifier_t)); | |||
| 1431 | for (i = 0; i < cascade->count; i++) | |||
| 1432 | { | |||
| 1433 | sprintf(buf, "%s/stage-%d.txt", directory, i); | |||
| 1434 | if (_ccv_read_bbf_stage_classifier(buf, &cascade->stage_classifier[i]) < 0) | |||
| 1435 | { | |||
| 1436 | cascade->count = i; | |||
| 1437 | break; | |||
| 1438 | } | |||
| 1439 | } | |||
| 1440 | fclose(r); | |||
| 1441 | return cascade; | |||
| 1442 | } | |||
| 1443 | ||||
| 1444 | ccv_bbf_classifier_cascade_t* ccv_bbf_classifier_cascade_read_binary(char* s) | |||
| 1445 | { | |||
| 1446 | int i; | |||
| 1447 | ccv_bbf_classifier_cascade_t* cascade = (ccv_bbf_classifier_cascade_t*)ccmallocmalloc(sizeof(ccv_bbf_classifier_cascade_t)); | |||
| 1448 | memcpy(&cascade->count, s, sizeof(cascade->count)); s += sizeof(cascade->count); | |||
| 1449 | memcpy(&cascade->size.width, s, sizeof(cascade->size.width)); s += sizeof(cascade->size.width); | |||
| 1450 | memcpy(&cascade->size.height, s, sizeof(cascade->size.height)); s += sizeof(cascade->size.height); | |||
| 1451 | ccv_bbf_stage_classifier_t* classifier = cascade->stage_classifier = (ccv_bbf_stage_classifier_t*)ccmallocmalloc(cascade->count * sizeof(ccv_bbf_stage_classifier_t)); | |||
| 1452 | for (i = 0; i < cascade->count; i++, classifier++) | |||
| 1453 | { | |||
| 1454 | memcpy(&classifier->count, s, sizeof(classifier->count)); s += sizeof(classifier->count); | |||
| 1455 | memcpy(&classifier->threshold, s, sizeof(classifier->threshold)); s += sizeof(classifier->threshold); | |||
| 1456 | classifier->feature = (ccv_bbf_feature_t*)ccmallocmalloc(classifier->count * sizeof(ccv_bbf_feature_t)); | |||
| 1457 | classifier->alpha = (float*)ccmallocmalloc(classifier->count * 2 * sizeof(float)); | |||
| 1458 | memcpy(classifier->feature, s, classifier->count * sizeof(ccv_bbf_feature_t)); s += classifier->count * sizeof(ccv_bbf_feature_t); | |||
| 1459 | memcpy(classifier->alpha, s, classifier->count * 2 * sizeof(float)); s += classifier->count * 2 * sizeof(float); | |||
| 1460 | } | |||
| 1461 | return cascade; | |||
| 1462 | ||||
| 1463 | } | |||
| 1464 | ||||
| 1465 | int ccv_bbf_classifier_cascade_write_binary(ccv_bbf_classifier_cascade_t* cascade, char* s, int slen) | |||
| 1466 | { | |||
| 1467 | int i; | |||
| 1468 | int len = sizeof(cascade->count) + sizeof(cascade->size.width) + sizeof(cascade->size.height); | |||
| 1469 | ccv_bbf_stage_classifier_t* classifier = cascade->stage_classifier; | |||
| 1470 | for (i = 0; i < cascade->count; i++, classifier++) | |||
| 1471 | len += sizeof(classifier->count) + sizeof(classifier->threshold) + classifier->count * sizeof(ccv_bbf_feature_t) + classifier->count * 2 * sizeof(float); | |||
| 1472 | if (slen >= len) | |||
| 1473 | { | |||
| 1474 | memcpy(s, &cascade->count, sizeof(cascade->count)); s += sizeof(cascade->count); | |||
| 1475 | memcpy(s, &cascade->size.width, sizeof(cascade->size.width)); s += sizeof(cascade->size.width); | |||
| 1476 | memcpy(s, &cascade->size.height, sizeof(cascade->size.height)); s += sizeof(cascade->size.height); | |||
| 1477 | classifier = cascade->stage_classifier; | |||
| 1478 | for (i = 0; i < cascade->count; i++, classifier++) | |||
| 1479 | { | |||
| 1480 | memcpy(s, &classifier->count, sizeof(classifier->count)); s += sizeof(classifier->count); | |||
| 1481 | memcpy(s, &classifier->threshold, sizeof(classifier->threshold)); s += sizeof(classifier->threshold); | |||
| 1482 | memcpy(s, classifier->feature, classifier->count * sizeof(ccv_bbf_feature_t)); s += classifier->count * sizeof(ccv_bbf_feature_t); | |||
| 1483 | memcpy(s, classifier->alpha, classifier->count * 2 * sizeof(float)); s += classifier->count * 2 * sizeof(float); | |||
| 1484 | } | |||
| 1485 | } | |||
| 1486 | return len; | |||
| 1487 | } | |||
| 1488 | ||||
| 1489 | void ccv_bbf_classifier_cascade_free(ccv_bbf_classifier_cascade_t* cascade) | |||
| 1490 | { | |||
| 1491 | int i; | |||
| 1492 | for (i = 0; i < cascade->count; ++i) | |||
| 1493 | { | |||
| 1494 | ccfreefree(cascade->stage_classifier[i].feature); | |||
| 1495 | ccfreefree(cascade->stage_classifier[i].alpha); | |||
| 1496 | } | |||
| 1497 | ccfreefree(cascade->stage_classifier); | |||
| 1498 | ccfreefree(cascade); | |||
| 1499 | } |