File: | ccv_bbf.c |
Warning: | line 1229, column 20 Dereference of null pointer |
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 == 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
| ||||
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 | } |