1 /*====================================================================*
2 - Copyright (C) 2001 Leptonica. All rights reserved.
3 -
4 - Redistribution and use in source and binary forms, with or without
5 - modification, are permitted provided that the following conditions
6 - are met:
7 - 1. Redistributions of source code must retain the above copyright
8 - notice, this list of conditions and the following disclaimer.
9 - 2. Redistributions in binary form must reproduce the above
10 - copyright notice, this list of conditions and the following
11 - disclaimer in the documentation and/or other materials
12 - provided with the distribution.
13 -
14 - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18 - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23 - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24 - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 *====================================================================*/
26
27 /*!
28 * \file quadtree.c
29 * <pre>
30 *
31 * Top level quadtree linear statistics
32 * l_int32 pixQuadtreeMean()
33 * l_int32 pixQuadtreeVariance()
34 *
35 * Statistics in an arbitrary rectangle
36 * l_int32 pixMeanInRectangle()
37 * l_int32 pixVarianceInRectangle()
38 *
39 * Quadtree regions
40 * BOXAA *boxaaQuadtreeRegions()
41 *
42 * Quadtree access
43 * l_int32 quadtreeGetParent()
44 * l_int32 quadtreeGetChildren()
45 * l_int32 quadtreeMaxLevels()
46 *
47 * Display quadtree
48 * PIX *fpixaDisplayQuadtree()
49 *
50 *
51 * There are many other statistical quantities that can be computed
52 * in a quadtree, such as rank values, and these can be added as
53 * the need arises.
54 *
55 * Similar results that can approximate a single level of the quadtree
56 * can be generated by pixGetAverageTiled(). There we specify the
57 * tile size over which the mean, mean square, and root variance
58 * are generated; the results are saved in a (reduced size) pix.
59 * Because the tile dimensions are integers, it is usually not possible
60 * to obtain tilings that are a power of 2, as required for quadtrees.
61 * </pre>
62 */
63
64 #include <math.h>
65 #include "allheaders.h"
66
67 #ifndef NO_CONSOLE_IO
68 #define DEBUG_BOXES 0
69 #endif /* !NO_CONSOLE_IO */
70
71
72 /*----------------------------------------------------------------------*
73 * Top-level quadtree linear statistics *
74 *----------------------------------------------------------------------*/
75 /*!
76 * \brief pixQuadtreeMean()
77 *
78 * \param[in] pixs 8 bpp, no colormap
79 * \param[in] nlevels in quadtree; max allowed depends on image size
80 * \param[in] *pix_ma input mean accumulator; can be null
81 * \param[out] *pfpixa mean values in quadtree
82 * \return 0 if OK, 1 on error
83 *
84 * <pre>
85 * Notes:
86 * (1) The returned fpixa has %nlevels of fpix, each containing
87 * the mean values at its level. Level 0 has a
88 * single value; level 1 has 4 values; level 2 has 16; etc.
89 * </pre>
90 */
91 l_int32
pixQuadtreeMean(PIX * pixs,l_int32 nlevels,PIX * pix_ma,FPIXA ** pfpixa)92 pixQuadtreeMean(PIX *pixs,
93 l_int32 nlevels,
94 PIX *pix_ma,
95 FPIXA **pfpixa)
96 {
97 l_int32 i, j, w, h, size, n;
98 l_float32 val;
99 BOX *box;
100 BOXA *boxa;
101 BOXAA *baa;
102 FPIX *fpix;
103 PIX *pix_mac;
104
105 PROCNAME("pixQuadtreeMean");
106
107 if (!pfpixa)
108 return ERROR_INT("&fpixa not defined", procName, 1);
109 *pfpixa = NULL;
110 if (!pixs || pixGetDepth(pixs) != 8)
111 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
112 pixGetDimensions(pixs, &w, &h, NULL);
113 if (nlevels > quadtreeMaxLevels(w, h))
114 return ERROR_INT("nlevels too large for image", procName, 1);
115
116 if (!pix_ma)
117 pix_mac = pixBlockconvAccum(pixs);
118 else
119 pix_mac = pixClone(pix_ma);
120 if (!pix_mac)
121 return ERROR_INT("pix_mac not made", procName, 1);
122
123 if ((baa = boxaaQuadtreeRegions(w, h, nlevels)) == NULL) {
124 pixDestroy(&pix_mac);
125 return ERROR_INT("baa not made", procName, 1);
126 }
127
128 *pfpixa = fpixaCreate(nlevels);
129 for (i = 0; i < nlevels; i++) {
130 boxa = boxaaGetBoxa(baa, i, L_CLONE);
131 size = 1 << i;
132 n = boxaGetCount(boxa); /* n == size * size */
133 fpix = fpixCreate(size, size);
134 for (j = 0; j < n; j++) {
135 box = boxaGetBox(boxa, j, L_CLONE);
136 pixMeanInRectangle(pixs, box, pix_mac, &val);
137 fpixSetPixel(fpix, j % size, j / size, val);
138 boxDestroy(&box);
139 }
140 fpixaAddFPix(*pfpixa, fpix, L_INSERT);
141 boxaDestroy(&boxa);
142 }
143
144 pixDestroy(&pix_mac);
145 boxaaDestroy(&baa);
146 return 0;
147 }
148
149
150 /*!
151 * \brief pixQuadtreeVariance()
152 *
153 * \param[in] pixs 8 bpp, no colormap
154 * \param[in] nlevels in quadtree
155 * \param[in] *pix_ma input mean accumulator; can be null
156 * \param[in] *dpix_msa input mean square accumulator; can be null
157 * \param[out] *pfpixa_v [optional] variance values in quadtree
158 * \param[out] *pfpixa_rv [optional] root variance values in quadtree
159 * \return 0 if OK, 1 on error
160 *
161 * <pre>
162 * Notes:
163 * (1) The returned fpixav and fpixarv have %nlevels of fpix,
164 * each containing at the respective levels the variance
165 * and root variance values.
166 * </pre>
167 */
168 l_int32
pixQuadtreeVariance(PIX * pixs,l_int32 nlevels,PIX * pix_ma,DPIX * dpix_msa,FPIXA ** pfpixa_v,FPIXA ** pfpixa_rv)169 pixQuadtreeVariance(PIX *pixs,
170 l_int32 nlevels,
171 PIX *pix_ma,
172 DPIX *dpix_msa,
173 FPIXA **pfpixa_v,
174 FPIXA **pfpixa_rv)
175 {
176 l_int32 i, j, w, h, size, n;
177 l_float32 var, rvar;
178 BOX *box;
179 BOXA *boxa;
180 BOXAA *baa;
181 FPIX *fpixv, *fpixrv;
182 PIX *pix_mac; /* copy of mean accumulator */
183 DPIX *dpix_msac; /* msa clone */
184
185 PROCNAME("pixQuadtreeVariance");
186
187 if (!pfpixa_v && !pfpixa_rv)
188 return ERROR_INT("neither &fpixav nor &fpixarv defined", procName, 1);
189 if (pfpixa_v) *pfpixa_v = NULL;
190 if (pfpixa_rv) *pfpixa_rv = NULL;
191 if (!pixs || pixGetDepth(pixs) != 8)
192 return ERROR_INT("pixs not defined or not 8 bpp", procName, 1);
193 pixGetDimensions(pixs, &w, &h, NULL);
194 if (nlevels > quadtreeMaxLevels(w, h))
195 return ERROR_INT("nlevels too large for image", procName, 1);
196
197 if (!pix_ma)
198 pix_mac = pixBlockconvAccum(pixs);
199 else
200 pix_mac = pixClone(pix_ma);
201 if (!pix_mac)
202 return ERROR_INT("pix_mac not made", procName, 1);
203 if (!dpix_msa)
204 dpix_msac = pixMeanSquareAccum(pixs);
205 else
206 dpix_msac = dpixClone(dpix_msa);
207 if (!dpix_msac) {
208 pixDestroy(&pix_mac);
209 return ERROR_INT("dpix_msac not made", procName, 1);
210 }
211
212 if ((baa = boxaaQuadtreeRegions(w, h, nlevels)) == NULL) {
213 pixDestroy(&pix_mac);
214 dpixDestroy(&dpix_msac);
215 return ERROR_INT("baa not made", procName, 1);
216 }
217
218 if (pfpixa_v) *pfpixa_v = fpixaCreate(nlevels);
219 if (pfpixa_rv) *pfpixa_rv = fpixaCreate(nlevels);
220 for (i = 0; i < nlevels; i++) {
221 boxa = boxaaGetBoxa(baa, i, L_CLONE);
222 size = 1 << i;
223 n = boxaGetCount(boxa); /* n == size * size */
224 if (pfpixa_v) fpixv = fpixCreate(size, size);
225 if (pfpixa_rv) fpixrv = fpixCreate(size, size);
226 for (j = 0; j < n; j++) {
227 box = boxaGetBox(boxa, j, L_CLONE);
228 pixVarianceInRectangle(pixs, box, pix_mac, dpix_msac, &var, &rvar);
229 if (pfpixa_v) fpixSetPixel(fpixv, j % size, j / size, var);
230 if (pfpixa_rv) fpixSetPixel(fpixrv, j % size, j / size, rvar);
231 boxDestroy(&box);
232 }
233 if (pfpixa_v) fpixaAddFPix(*pfpixa_v, fpixv, L_INSERT);
234 if (pfpixa_rv) fpixaAddFPix(*pfpixa_rv, fpixrv, L_INSERT);
235 boxaDestroy(&boxa);
236 }
237
238 pixDestroy(&pix_mac);
239 dpixDestroy(&dpix_msac);
240 boxaaDestroy(&baa);
241 return 0;
242 }
243
244
245 /*----------------------------------------------------------------------*
246 * Statistics in an arbitrary rectangle *
247 *----------------------------------------------------------------------*/
248 /*!
249 * \brief pixMeanInRectangle()
250 *
251 * \param[in] pixs 8 bpp
252 * \param[in] box region to compute mean value
253 * \param[in] pixma mean accumulator
254 * \param[out] pval mean value
255 * \return 0 if OK, 1 on error
256 *
257 * <pre>
258 * Notes:
259 * (1) This function is intended to be used for many rectangles
260 * on the same image. It can find the mean within a
261 * rectangle in O(1), independent of the size of the rectangle.
262 * </pre>
263 */
264 l_int32
pixMeanInRectangle(PIX * pixs,BOX * box,PIX * pixma,l_float32 * pval)265 pixMeanInRectangle(PIX *pixs,
266 BOX *box,
267 PIX *pixma,
268 l_float32 *pval)
269 {
270 l_int32 w, h, bx, by, bw, bh;
271 l_uint32 val00, val01, val10, val11;
272 l_float32 norm;
273 BOX *boxc;
274
275 PROCNAME("pixMeanInRectangle");
276
277 if (!pval)
278 return ERROR_INT("&val not defined", procName, 1);
279 *pval = 0.0;
280 if (!pixs || pixGetDepth(pixs) != 8)
281 return ERROR_INT("pixs not defined", procName, 1);
282 if (!box)
283 return ERROR_INT("box not defined", procName, 1);
284 if (!pixma)
285 return ERROR_INT("pixma not defined", procName, 1);
286
287 /* Clip rectangle to image */
288 pixGetDimensions(pixs, &w, &h, NULL);
289 boxc = boxClipToRectangle(box, w, h);
290 boxGetGeometry(boxc, &bx, &by, &bw, &bh);
291 boxDestroy(&boxc);
292
293 if (bw == 0 || bh == 0)
294 return ERROR_INT("no pixels in box", procName, 1);
295
296 /* Use up to 4 points in the accumulator */
297 norm = 1.0 / ((l_float32)(bw) * bh);
298 if (bx > 0 && by > 0) {
299 pixGetPixel(pixma, bx + bw - 1, by + bh - 1, &val11);
300 pixGetPixel(pixma, bx + bw - 1, by - 1, &val10);
301 pixGetPixel(pixma, bx - 1, by + bh - 1, &val01);
302 pixGetPixel(pixma, bx - 1, by - 1, &val00);
303 *pval = norm * (val11 - val01 + val00 - val10);
304 } else if (by > 0) { /* bx == 0 */
305 pixGetPixel(pixma, bw - 1, by + bh - 1, &val11);
306 pixGetPixel(pixma, bw - 1, by - 1, &val10);
307 *pval = norm * (val11 - val10);
308 } else if (bx > 0) { /* by == 0 */
309 pixGetPixel(pixma, bx + bw - 1, bh - 1, &val11);
310 pixGetPixel(pixma, bx - 1, bh - 1, &val01);
311 *pval = norm * (val11 - val01);
312 } else { /* bx == 0 && by == 0 */
313 pixGetPixel(pixma, bw - 1, bh - 1, &val11);
314 *pval = norm * val11;
315 }
316
317 return 0;
318 }
319
320
321 /*!
322 * \brief pixVarianceInRectangle()
323 *
324 * \param[in] pixs 8 bpp
325 * \param[in] box region to compute variance and/or root variance
326 * \param[in] pix_ma mean accumulator
327 * \param[in] dpix_msa mean square accumulator
328 * \param[out] pvar [optional] variance
329 * \param[out] prvar [optional] root variance
330 * \return 0 if OK, 1 on error
331 *
332 * <pre>
333 * Notes:
334 * (1) This function is intended to be used for many rectangles
335 * on the same image. It can find the variance and/or the
336 * square root of the variance within a rectangle in O(1),
337 * independent of the size of the rectangle.
338 * </pre>
339 */
340 l_int32
pixVarianceInRectangle(PIX * pixs,BOX * box,PIX * pix_ma,DPIX * dpix_msa,l_float32 * pvar,l_float32 * prvar)341 pixVarianceInRectangle(PIX *pixs,
342 BOX *box,
343 PIX *pix_ma,
344 DPIX *dpix_msa,
345 l_float32 *pvar,
346 l_float32 *prvar)
347 {
348 l_int32 w, h, bx, by, bw, bh;
349 l_uint32 val00, val01, val10, val11;
350 l_float64 dval00, dval01, dval10, dval11, mval, msval, var, norm;
351 BOX *boxc;
352
353 PROCNAME("pixVarianceInRectangle");
354
355 if (!pvar && !prvar)
356 return ERROR_INT("neither &var nor &rvar defined", procName, 1);
357 if (pvar) *pvar = 0.0;
358 if (prvar) *prvar = 0.0;
359 if (!pixs || pixGetDepth(pixs) != 8)
360 return ERROR_INT("pixs not defined", procName, 1);
361 if (!box)
362 return ERROR_INT("box not defined", procName, 1);
363 if (!pix_ma)
364 return ERROR_INT("pix_ma not defined", procName, 1);
365 if (!dpix_msa)
366 return ERROR_INT("dpix_msa not defined", procName, 1);
367
368 /* Clip rectangle to image */
369 pixGetDimensions(pixs, &w, &h, NULL);
370 boxc = boxClipToRectangle(box, w, h);
371 boxGetGeometry(boxc, &bx, &by, &bw, &bh);
372 boxDestroy(&boxc);
373
374 if (bw == 0 || bh == 0)
375 return ERROR_INT("no pixels in box", procName, 1);
376
377 /* Use up to 4 points in the accumulators */
378 norm = 1.0 / ((l_float32)(bw) * bh);
379 if (bx > 0 && by > 0) {
380 pixGetPixel(pix_ma, bx + bw - 1, by + bh - 1, &val11);
381 pixGetPixel(pix_ma, bx + bw - 1, by - 1, &val10);
382 pixGetPixel(pix_ma, bx - 1, by + bh - 1, &val01);
383 pixGetPixel(pix_ma, bx - 1, by - 1, &val00);
384 dpixGetPixel(dpix_msa, bx + bw - 1, by + bh - 1, &dval11);
385 dpixGetPixel(dpix_msa, bx + bw - 1, by - 1, &dval10);
386 dpixGetPixel(dpix_msa, bx - 1, by + bh - 1, &dval01);
387 dpixGetPixel(dpix_msa, bx - 1, by - 1, &dval00);
388 mval = norm * (val11 - val01 + val00 - val10);
389 msval = norm * (dval11 - dval01 + dval00 - dval10);
390 var = (msval - mval * mval);
391 if (pvar) *pvar = (l_float32)var;
392 if (prvar) *prvar = (l_float32)(sqrt(var));
393 } else if (by > 0) { /* bx == 0 */
394 pixGetPixel(pix_ma, bw - 1, by + bh - 1, &val11);
395 pixGetPixel(pix_ma, bw - 1, by - 1, &val10);
396 dpixGetPixel(dpix_msa, bw - 1, by + bh - 1, &dval11);
397 dpixGetPixel(dpix_msa, bw - 1, by - 1, &dval10);
398 mval = norm * (val11 - val10);
399 msval = norm * (dval11 - dval10);
400 var = (msval - mval * mval);
401 if (pvar) *pvar = (l_float32)var;
402 if (prvar) *prvar = (l_float32)(sqrt(var));
403 } else if (bx > 0) { /* by == 0 */
404 pixGetPixel(pix_ma, bx + bw - 1, bh - 1, &val11);
405 pixGetPixel(pix_ma, bx - 1, bh - 1, &val01);
406 dpixGetPixel(dpix_msa, bx + bw - 1, bh - 1, &dval11);
407 dpixGetPixel(dpix_msa, bx - 1, bh - 1, &dval01);
408 mval = norm * (val11 - val01);
409 msval = norm * (dval11 - dval01);
410 var = (msval - mval * mval);
411 if (pvar) *pvar = (l_float32)var;
412 if (prvar) *prvar = (l_float32)(sqrt(var));
413 } else { /* bx == 0 && by == 0 */
414 pixGetPixel(pix_ma, bw - 1, bh - 1, &val11);
415 dpixGetPixel(dpix_msa, bw - 1, bh - 1, &dval11);
416 mval = norm * val11;
417 msval = norm * dval11;
418 var = (msval - mval * mval);
419 if (pvar) *pvar = (l_float32)var;
420 if (prvar) *prvar = (l_float32)(sqrt(var));
421 }
422
423 return 0;
424 }
425
426
427 /*----------------------------------------------------------------------*
428 * Quadtree regions *
429 *----------------------------------------------------------------------*/
430 /*!
431 * \brief boxaaQuadtreeRegions()
432 *
433 * \param[in] w, h size of pix that is being quadtree-ized
434 * \param[in] nlevels number of levels in quadtree
435 * \return baa for quadtree regions at each level, or NULL on error
436 *
437 * <pre>
438 * Notes:
439 * (1) The returned boxaa has %nlevels of boxa, each containing
440 * the set of rectangles at that level. The rectangle at
441 * level 0 is the entire region; at level 1 the region is
442 * divided into 4 rectangles, and at level n there are n^4
443 * rectangles.
444 * (2) At each level, the rectangles in the boxa are in "raster"
445 * order, with LR (fast scan) and TB (slow scan).
446 * </pre>
447 */
448 BOXAA *
boxaaQuadtreeRegions(l_int32 w,l_int32 h,l_int32 nlevels)449 boxaaQuadtreeRegions(l_int32 w,
450 l_int32 h,
451 l_int32 nlevels)
452 {
453 l_int32 i, j, k, maxpts, nside, nbox, bw, bh;
454 l_int32 *xstart, *xend, *ystart, *yend;
455 BOX *box;
456 BOXA *boxa;
457 BOXAA *baa;
458
459 PROCNAME("boxaaQuadtreeRegions");
460
461 if (nlevels < 1)
462 return (BOXAA *)ERROR_PTR("nlevels must be >= 1", procName, NULL);
463 if (w < (1 << (nlevels - 1)))
464 return (BOXAA *)ERROR_PTR("w doesn't support nlevels", procName, NULL);
465 if (h < (1 << (nlevels - 1)))
466 return (BOXAA *)ERROR_PTR("h doesn't support nlevels", procName, NULL);
467
468 baa = boxaaCreate(nlevels);
469 maxpts = 1 << (nlevels - 1);
470 xstart = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
471 xend = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
472 ystart = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
473 yend = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
474 for (k = 0; k < nlevels; k++) {
475 nside = 1 << k; /* number of boxes in each direction */
476 for (i = 0; i < nside; i++) {
477 xstart[i] = (w - 1) * i / nside;
478 if (i > 0) xstart[i]++;
479 xend[i] = (w - 1) * (i + 1) / nside;
480 ystart[i] = (h - 1) * i / nside;
481 if (i > 0) ystart[i]++;
482 yend[i] = (h - 1) * (i + 1) / nside;
483 #if DEBUG_BOXES
484 fprintf(stderr,
485 "k = %d, xs[%d] = %d, xe[%d] = %d, ys[%d] = %d, ye[%d] = %d\n",
486 k, i, xstart[i], i, xend[i], i, ystart[i], i, yend[i]);
487 #endif /* DEBUG_BOXES */
488 }
489 nbox = 1 << (2 * k);
490 boxa = boxaCreate(nbox);
491 for (i = 0; i < nside; i++) {
492 bh = yend[i] - ystart[i] + 1;
493 for (j = 0; j < nside; j++) {
494 bw = xend[j] - xstart[j] + 1;
495 box = boxCreate(xstart[j], ystart[i], bw, bh);
496 boxaAddBox(boxa, box, L_INSERT);
497 }
498 }
499 boxaaAddBoxa(baa, boxa, L_INSERT);
500 }
501
502 LEPT_FREE(xstart);
503 LEPT_FREE(xend);
504 LEPT_FREE(ystart);
505 LEPT_FREE(yend);
506 return baa;
507 }
508
509
510 /*----------------------------------------------------------------------*
511 * Quadtree access *
512 *----------------------------------------------------------------------*/
513 /*!
514 * \brief quadtreeGetParent()
515 *
516 * \param[in] fpixa mean, variance or root variance
517 * \param[in] level, x, y of current pixel
518 * \param[out] pval parent pixel value, or 0.0 on error
519 * \return 0 if OK, 1 on error
520 *
521 * <pre>
522 * Notes:
523 * (1) Check return value for error. On error, val is returned as 0.0.
524 * (2) The parent is located at:
525 * level - 1
526 * (x/2, y/2)
527 * </pre>
528 */
529 l_int32
quadtreeGetParent(FPIXA * fpixa,l_int32 level,l_int32 x,l_int32 y,l_float32 * pval)530 quadtreeGetParent(FPIXA *fpixa,
531 l_int32 level,
532 l_int32 x,
533 l_int32 y,
534 l_float32 *pval)
535 {
536 l_int32 n;
537
538 PROCNAME("quadtreeGetParent");
539
540 if (!pval)
541 return ERROR_INT("&val not defined", procName, 1);
542 *pval = 0.0;
543 if (!fpixa)
544 return ERROR_INT("fpixa not defined", procName, 1);
545 n = fpixaGetCount(fpixa);
546 if (level < 1 || level >= n)
547 return ERROR_INT("invalid level", procName, 1);
548
549 if (fpixaGetPixel(fpixa, level - 1, x / 2, y / 2, pval) != 0)
550 return ERROR_INT("invalid coordinates", procName, 1);
551 return 0;
552 }
553
554
555 /*!
556 * \brief quadtreeGetChildren()
557 *
558 * \param[in] fpixa mean, variance or root variance
559 * \param[in] level, x, y of current pixel
560 * \param[out] pval00, pval01,
561 * pval10, pval11 four child pixel values
562 * \return 0 if OK, 1 on error
563 *
564 * <pre>
565 * Notes:
566 * (1) Check return value for error. On error, all return vals are 0.0.
567 * (2) The returned child pixels are located at:
568 * level + 1
569 * (2x, 2y), (2x+1, 2y), (2x, 2y+1), (2x+1, 2y+1)
570 * </pre>
571 */
572 l_int32
quadtreeGetChildren(FPIXA * fpixa,l_int32 level,l_int32 x,l_int32 y,l_float32 * pval00,l_float32 * pval10,l_float32 * pval01,l_float32 * pval11)573 quadtreeGetChildren(FPIXA *fpixa,
574 l_int32 level,
575 l_int32 x,
576 l_int32 y,
577 l_float32 *pval00,
578 l_float32 *pval10,
579 l_float32 *pval01,
580 l_float32 *pval11)
581 {
582 l_int32 n;
583
584 PROCNAME("quadtreeGetChildren");
585
586 if (!pval00 || !pval01 || !pval10 || !pval11)
587 return ERROR_INT("&val* not all defined", procName, 1);
588 *pval00 = *pval10 = *pval01 = *pval11 = 0.0;
589 if (!fpixa)
590 return ERROR_INT("fpixa not defined", procName, 1);
591 n = fpixaGetCount(fpixa);
592 if (level < 0 || level >= n - 1)
593 return ERROR_INT("invalid level", procName, 1);
594
595 if (fpixaGetPixel(fpixa, level + 1, 2 * x, 2 * y, pval00) != 0)
596 return ERROR_INT("invalid coordinates", procName, 1);
597 fpixaGetPixel(fpixa, level + 1, 2 * x + 1, 2 * y, pval10);
598 fpixaGetPixel(fpixa, level + 1, 2 * x, 2 * y + 1, pval01);
599 fpixaGetPixel(fpixa, level + 1, 2 * x + 1, 2 * y + 1, pval11);
600 return 0;
601 }
602
603
604 /*!
605 * \brief quadtreeMaxLevels()
606 *
607 * \param[in] w, h dimensions of image
608 * \return maxlevels maximum number of levels allowed, or -1 on error
609 *
610 * <pre>
611 * Notes:
612 * (1) The criterion for maxlevels is that the subdivision not
613 * go down below the single pixel level. The 1.5 factor
614 * is intended to keep any rectangle from accidentally
615 * having zero dimension due to integer truncation.
616 * </pre>
617 */
618 l_int32
quadtreeMaxLevels(l_int32 w,l_int32 h)619 quadtreeMaxLevels(l_int32 w,
620 l_int32 h)
621 {
622 l_int32 i, minside;
623
624 minside = L_MIN(w, h);
625 for (i = 0; i < 20; i++) { /* 2^10 = one million */
626 if (minside < (1.5 * (1 << i)))
627 return i - 1;
628 }
629
630 return -1; /* fail if the image has over a trillion pixels! */
631 }
632
633
634 /*----------------------------------------------------------------------*
635 * Display quadtree *
636 *----------------------------------------------------------------------*/
637 /*!
638 * \brief fpixaDisplayQuadtree()
639 *
640 * \param[in] fpixa mean, variance or root variance
641 * \param[in] factor replication factor at lowest level
642 * \param[in] fontsize 4, ... 20
643 * \return pixd 8 bpp, mosaic of quadtree images, or NULL on error
644 *
645 * <pre>
646 * Notes:
647 * (1) The mean and root variance fall naturally in the 8 bpp range,
648 * but the variance is typically outside the range. This
649 * function displays 8 bpp pix clipped to 255, so the image
650 * pixels will mostly be 255 (white).
651 * </pre>
652 */
653 PIX *
fpixaDisplayQuadtree(FPIXA * fpixa,l_int32 factor,l_int32 fontsize)654 fpixaDisplayQuadtree(FPIXA *fpixa,
655 l_int32 factor,
656 l_int32 fontsize)
657 {
658 char buf[256];
659 l_int32 nlevels, i, mag, w;
660 L_BMF *bmf;
661 FPIX *fpix;
662 PIX *pixt1, *pixt2, *pixt3, *pixt4, *pixd;
663 PIXA *pixat;
664
665 PROCNAME("fpixaDisplayQuadtree");
666
667 if (!fpixa)
668 return (PIX *)ERROR_PTR("fpixa not defined", procName, NULL);
669
670 if ((nlevels = fpixaGetCount(fpixa)) == 0)
671 return (PIX *)ERROR_PTR("pixas empty", procName, NULL);
672
673 if ((bmf = bmfCreate(NULL, fontsize)) == NULL)
674 L_ERROR("bmf not made; text will not be added", procName);
675 pixat = pixaCreate(nlevels);
676 for (i = 0; i < nlevels; i++) {
677 fpix = fpixaGetFPix(fpixa, i, L_CLONE);
678 pixt1 = fpixConvertToPix(fpix, 8, L_CLIP_TO_ZERO, 0);
679 mag = factor * (1 << (nlevels - i - 1));
680 pixt2 = pixExpandReplicate(pixt1, mag);
681 pixt3 = pixConvertTo32(pixt2);
682 snprintf(buf, sizeof(buf), "Level %d\n", i);
683 pixt4 = pixAddSingleTextblock(pixt3, bmf, buf, 0xff000000,
684 L_ADD_BELOW, NULL);
685 pixaAddPix(pixat, pixt4, L_INSERT);
686 fpixDestroy(&fpix);
687 pixDestroy(&pixt1);
688 pixDestroy(&pixt2);
689 pixDestroy(&pixt3);
690 }
691 w = pixGetWidth(pixt4);
692 pixd = pixaDisplayTiledInRows(pixat, 32, nlevels * (w + 80), 1.0, 0, 30, 2);
693
694 pixaDestroy(&pixat);
695 bmfDestroy(&bmf);
696 return pixd;
697 }
698