File: | ccv_bbf.c |
Warning: | line 82, column 9 File position of the stream might be 'indeterminate' after a failed operation. Can cause undefined behavior |
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
| |||
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 == 0) return -1; | |||
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 == 0) return -1; | |||
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 > 0) | |||
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 > 0) | |||
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
| |||
| ||||
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 | } |