Mercurial > hgrepos > Python2 > PyMuPDF

comparison mupdf-source/thirdparty/leptonica/src/quadtree.c @ 2:b50eed0cc0ef upstream

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ADD: MuPDF v1.26.7: the MuPDF source as downloaded by a default build of PyMuPDF 1.26.4. The directory name has changed: no version number in the expanded directory now.
author Franz Glasner <fzglas.hg@dom66.de>
date Mon, 15 Sep 2025 11:43:07 +0200
parents
children
comparison
equal deleted inserted replaced
1:1d09e1dec1d9 2:b50eed0cc0ef
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 #ifdef HAVE_CONFIG_H
65 #include <config_auto.h>
66 #endif /* HAVE_CONFIG_H */
67
68 #include <math.h>
69 #include "allheaders.h"
70
71 #ifndef NO_CONSOLE_IO
72 #define DEBUG_BOXES 0
73 #endif /* !NO_CONSOLE_IO */
74
75
76 /*----------------------------------------------------------------------*
77 * Top-level quadtree linear statistics *
78 *----------------------------------------------------------------------*/
79 /*!
80 * \brief pixQuadtreeMean()
81 *
82 * \param[in] pixs 8 bpp, no colormap
83 * \param[in] nlevels in quadtree; max allowed depends on image size
84 * \param[in] pix_ma input mean accumulator; can be null
85 * \param[out] pfpixa mean values in quadtree
86 * \return 0 if OK, 1 on error
87 *
88 * <pre>
89 * Notes:
90 * (1) The returned fpixa has %nlevels of fpix, each containing
91 * the mean values at its level. Level 0 has a
92 * single value; level 1 has 4 values; level 2 has 16; etc.
93 * </pre>
94 */
95 l_ok
96 pixQuadtreeMean(PIX *pixs,
97 l_int32 nlevels,
98 PIX *pix_ma,
99 FPIXA **pfpixa)
100 {
101 l_int32 i, j, w, h, size, n;
102 l_float32 val;
103 BOX *box;
104 BOXA *boxa;
105 BOXAA *baa;
106 FPIX *fpix;
107 PIX *pix_mac;
108
109 if (!pfpixa)
110 return ERROR_INT("&fpixa not defined", __func__, 1);
111 *pfpixa = NULL;
112 if (!pixs || pixGetDepth(pixs) != 8)
113 return ERROR_INT("pixs not defined or not 8 bpp", __func__, 1);
114 pixGetDimensions(pixs, &w, &h, NULL);
115 if (nlevels > quadtreeMaxLevels(w, h))
116 return ERROR_INT("nlevels too large for image", __func__, 1);
117
118 if (!pix_ma)
119 pix_mac = pixBlockconvAccum(pixs);
120 else
121 pix_mac = pixClone(pix_ma);
122 if (!pix_mac)
123 return ERROR_INT("pix_mac not made", __func__, 1);
124
125 if ((baa = boxaaQuadtreeRegions(w, h, nlevels)) == NULL) {
126 pixDestroy(&pix_mac);
127 return ERROR_INT("baa not made", __func__, 1);
128 }
129
130 *pfpixa = fpixaCreate(nlevels);
131 for (i = 0; i < nlevels; i++) {
132 boxa = boxaaGetBoxa(baa, i, L_CLONE);
133 size = 1 << i;
134 n = boxaGetCount(boxa); /* n == size * size */
135 fpix = fpixCreate(size, size);
136 for (j = 0; j < n; j++) {
137 box = boxaGetBox(boxa, j, L_CLONE);
138 pixMeanInRectangle(pixs, box, pix_mac, &val);
139 fpixSetPixel(fpix, j % size, j / size, val);
140 boxDestroy(&box);
141 }
142 fpixaAddFPix(*pfpixa, fpix, L_INSERT);
143 boxaDestroy(&boxa);
144 }
145
146 pixDestroy(&pix_mac);
147 boxaaDestroy(&baa);
148 return 0;
149 }
150
151
152 /*!
153 * \brief pixQuadtreeVariance()
154 *
155 * \param[in] pixs 8 bpp, no colormap
156 * \param[in] nlevels in quadtree
157 * \param[in] pix_ma input mean accumulator; can be null
158 * \param[in] dpix_msa input mean square accumulator; can be null
159 * \param[out] pfpixa_v [optional] variance values in quadtree
160 * \param[out] pfpixa_rv [optional] root variance values in quadtree
161 * \return 0 if OK, 1 on error
162 *
163 * <pre>
164 * Notes:
165 * (1) The returned fpixav and fpixarv have %nlevels of fpix,
166 * each containing at the respective levels the variance
167 * and root variance values.
168 * </pre>
169 */
170 l_ok
171 pixQuadtreeVariance(PIX *pixs,
172 l_int32 nlevels,
173 PIX *pix_ma,
174 DPIX *dpix_msa,
175 FPIXA **pfpixa_v,
176 FPIXA **pfpixa_rv)
177 {
178 l_int32 i, j, w, h, size, n;
179 l_float32 var, rvar;
180 BOX *box;
181 BOXA *boxa;
182 BOXAA *baa;
183 FPIX *fpixv = NULL, *fpixrv = NULL;
184 PIX *pix_mac; /* copy of mean accumulator */
185 DPIX *dpix_msac; /* msa clone */
186
187 if (!pfpixa_v && !pfpixa_rv)
188 return ERROR_INT("neither &fpixav nor &fpixarv defined", __func__, 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", __func__, 1);
193 pixGetDimensions(pixs, &w, &h, NULL);
194 if (nlevels > quadtreeMaxLevels(w, h))
195 return ERROR_INT("nlevels too large for image", __func__, 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", __func__, 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", __func__, 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", __func__, 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_ok
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 if (!pval)
276 return ERROR_INT("&val not defined", __func__, 1);
277 *pval = 0.0;
278 if (!pixs || pixGetDepth(pixs) != 8)
279 return ERROR_INT("pixs not defined", __func__, 1);
280 if (!box)
281 return ERROR_INT("box not defined", __func__, 1);
282 if (!pixma)
283 return ERROR_INT("pixma not defined", __func__, 1);
284
285 /* Clip rectangle to image */
286 pixGetDimensions(pixs, &w, &h, NULL);
287 boxc = boxClipToRectangle(box, w, h);
288 boxGetGeometry(boxc, &bx, &by, &bw, &bh);
289 boxDestroy(&boxc);
290
291 if (bw == 0 || bh == 0)
292 return ERROR_INT("no pixels in box", __func__, 1);
293
294 /* Use up to 4 points in the accumulator */
295 norm = 1.0f / ((l_float32)(bw) * bh);
296 if (bx > 0 && by > 0) {
297 pixGetPixel(pixma, bx + bw - 1, by + bh - 1, &val11);
298 pixGetPixel(pixma, bx + bw - 1, by - 1, &val10);
299 pixGetPixel(pixma, bx - 1, by + bh - 1, &val01);
300 pixGetPixel(pixma, bx - 1, by - 1, &val00);
301 *pval = norm * (val11 - val01 + val00 - val10);
302 } else if (by > 0) { /* bx == 0 */
303 pixGetPixel(pixma, bw - 1, by + bh - 1, &val11);
304 pixGetPixel(pixma, bw - 1, by - 1, &val10);
305 *pval = norm * (val11 - val10);
306 } else if (bx > 0) { /* by == 0 */
307 pixGetPixel(pixma, bx + bw - 1, bh - 1, &val11);
308 pixGetPixel(pixma, bx - 1, bh - 1, &val01);
309 *pval = norm * (val11 - val01);
310 } else { /* bx == 0 && by == 0 */
311 pixGetPixel(pixma, bw - 1, bh - 1, &val11);
312 *pval = norm * val11;
313 }
314
315 return 0;
316 }
317
318
319 /*!
320 * \brief pixVarianceInRectangle()
321 *
322 * \param[in] pixs 8 bpp
323 * \param[in] box region to compute variance and/or root variance
324 * \param[in] pix_ma mean accumulator
325 * \param[in] dpix_msa mean square accumulator
326 * \param[out] pvar [optional] variance
327 * \param[out] prvar [optional] root variance
328 * \return 0 if OK, 1 on error
329 *
330 * <pre>
331 * Notes:
332 * (1) This function is intended to be used for many rectangles
333 * on the same image. It can find the variance and/or the
334 * square root of the variance within a rectangle in O(1),
335 * independent of the size of the rectangle.
336 * </pre>
337 */
338 l_ok
339 pixVarianceInRectangle(PIX *pixs,
340 BOX *box,
341 PIX *pix_ma,
342 DPIX *dpix_msa,
343 l_float32 *pvar,
344 l_float32 *prvar)
345 {
346 l_int32 w, h, bx, by, bw, bh;
347 l_uint32 val00, val01, val10, val11;
348 l_float64 dval00, dval01, dval10, dval11, mval, msval, var, norm;
349 BOX *boxc;
350
351 if (!pvar && !prvar)
352 return ERROR_INT("neither &var nor &rvar defined", __func__, 1);
353 if (pvar) *pvar = 0.0;
354 if (prvar) *prvar = 0.0;
355 if (!pixs || pixGetDepth(pixs) != 8)
356 return ERROR_INT("pixs not defined", __func__, 1);
357 if (!box)
358 return ERROR_INT("box not defined", __func__, 1);
359 if (!pix_ma)
360 return ERROR_INT("pix_ma not defined", __func__, 1);
361 if (!dpix_msa)
362 return ERROR_INT("dpix_msa not defined", __func__, 1);
363
364 /* Clip rectangle to image */
365 pixGetDimensions(pixs, &w, &h, NULL);
366 boxc = boxClipToRectangle(box, w, h);
367 boxGetGeometry(boxc, &bx, &by, &bw, &bh);
368 boxDestroy(&boxc);
369
370 if (bw == 0 || bh == 0)
371 return ERROR_INT("no pixels in box", __func__, 1);
372
373 /* Use up to 4 points in the accumulators */
374 norm = 1.0 / ((l_float32)(bw) * bh);
375 if (bx > 0 && by > 0) {
376 pixGetPixel(pix_ma, bx + bw - 1, by + bh - 1, &val11);
377 pixGetPixel(pix_ma, bx + bw - 1, by - 1, &val10);
378 pixGetPixel(pix_ma, bx - 1, by + bh - 1, &val01);
379 pixGetPixel(pix_ma, bx - 1, by - 1, &val00);
380 dpixGetPixel(dpix_msa, bx + bw - 1, by + bh - 1, &dval11);
381 dpixGetPixel(dpix_msa, bx + bw - 1, by - 1, &dval10);
382 dpixGetPixel(dpix_msa, bx - 1, by + bh - 1, &dval01);
383 dpixGetPixel(dpix_msa, bx - 1, by - 1, &dval00);
384 mval = norm * (val11 - val01 + val00 - val10);
385 msval = norm * (dval11 - dval01 + dval00 - dval10);
386 var = (msval - mval * mval);
387 if (pvar) *pvar = (l_float32)var;
388 if (prvar) *prvar = (l_float32)(sqrt(var));
389 } else if (by > 0) { /* bx == 0 */
390 pixGetPixel(pix_ma, bw - 1, by + bh - 1, &val11);
391 pixGetPixel(pix_ma, bw - 1, by - 1, &val10);
392 dpixGetPixel(dpix_msa, bw - 1, by + bh - 1, &dval11);
393 dpixGetPixel(dpix_msa, bw - 1, by - 1, &dval10);
394 mval = norm * (val11 - val10);
395 msval = norm * (dval11 - dval10);
396 var = (msval - mval * mval);
397 if (pvar) *pvar = (l_float32)var;
398 if (prvar) *prvar = (l_float32)(sqrt(var));
399 } else if (bx > 0) { /* by == 0 */
400 pixGetPixel(pix_ma, bx + bw - 1, bh - 1, &val11);
401 pixGetPixel(pix_ma, bx - 1, bh - 1, &val01);
402 dpixGetPixel(dpix_msa, bx + bw - 1, bh - 1, &dval11);
403 dpixGetPixel(dpix_msa, bx - 1, bh - 1, &dval01);
404 mval = norm * (val11 - val01);
405 msval = norm * (dval11 - dval01);
406 var = (msval - mval * mval);
407 if (pvar) *pvar = (l_float32)var;
408 if (prvar) *prvar = (l_float32)(sqrt(var));
409 } else { /* bx == 0 && by == 0 */
410 pixGetPixel(pix_ma, bw - 1, bh - 1, &val11);
411 dpixGetPixel(dpix_msa, bw - 1, bh - 1, &dval11);
412 mval = norm * val11;
413 msval = norm * dval11;
414 var = (msval - mval * mval);
415 if (pvar) *pvar = (l_float32)var;
416 if (prvar) *prvar = (l_float32)(sqrt(var));
417 }
418
419 return 0;
420 }
421
422
423 /*----------------------------------------------------------------------*
424 * Quadtree regions *
425 *----------------------------------------------------------------------*/
426 /*!
427 * \brief boxaaQuadtreeRegions()
428 *
429 * \param[in] w, h size of pix that is being quadtree-ized
430 * \param[in] nlevels number of levels in quadtree
431 * \return baa for quadtree regions at each level, or NULL on error
432 *
433 * <pre>
434 * Notes:
435 * (1) The returned boxaa has %nlevels of boxa, each containing
436 * the set of rectangles at that level. The rectangle at
437 * level 0 is the entire region; at level 1 the region is
438 * divided into 4 rectangles, and at level n there are n^4
439 * rectangles.
440 * (2) At each level, the rectangles in the boxa are in "raster"
441 * order, with LR (fast scan) and TB (slow scan).
442 * </pre>
443 */
444 BOXAA *
445 boxaaQuadtreeRegions(l_int32 w,
446 l_int32 h,
447 l_int32 nlevels)
448 {
449 l_int32 i, j, k, maxpts, nside, nbox, bw, bh;
450 l_int32 *xstart, *xend, *ystart, *yend;
451 BOX *box;
452 BOXA *boxa;
453 BOXAA *baa;
454
455 if (nlevels < 1)
456 return (BOXAA *)ERROR_PTR("nlevels must be >= 1", __func__, NULL);
457 if (w < (1 << (nlevels - 1)))
458 return (BOXAA *)ERROR_PTR("w doesn't support nlevels", __func__, NULL);
459 if (h < (1 << (nlevels - 1)))
460 return (BOXAA *)ERROR_PTR("h doesn't support nlevels", __func__, NULL);
461
462 baa = boxaaCreate(nlevels);
463 maxpts = 1 << (nlevels - 1);
464 xstart = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
465 xend = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
466 ystart = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
467 yend = (l_int32 *)LEPT_CALLOC(maxpts, sizeof(l_int32));
468 for (k = 0; k < nlevels; k++) {
469 nside = 1 << k; /* number of boxes in each direction */
470 for (i = 0; i < nside; i++) {
471 xstart[i] = (w - 1) * i / nside;
472 if (i > 0) xstart[i]++;
473 xend[i] = (w - 1) * (i + 1) / nside;
474 ystart[i] = (h - 1) * i / nside;
475 if (i > 0) ystart[i]++;
476 yend[i] = (h - 1) * (i + 1) / nside;
477 #if DEBUG_BOXES
478 lept_stderr(
479 "k = %d, xs[%d] = %d, xe[%d] = %d, ys[%d] = %d, ye[%d] = %d\n",
480 k, i, xstart[i], i, xend[i], i, ystart[i], i, yend[i]);
481 #endif /* DEBUG_BOXES */
482 }
483 nbox = 1 << (2 * k);
484 boxa = boxaCreate(nbox);
485 for (i = 0; i < nside; i++) {
486 bh = yend[i] - ystart[i] + 1;
487 for (j = 0; j < nside; j++) {
488 bw = xend[j] - xstart[j] + 1;
489 box = boxCreate(xstart[j], ystart[i], bw, bh);
490 boxaAddBox(boxa, box, L_INSERT);
491 }
492 }
493 boxaaAddBoxa(baa, boxa, L_INSERT);
494 }
495
496 LEPT_FREE(xstart);
497 LEPT_FREE(xend);
498 LEPT_FREE(ystart);
499 LEPT_FREE(yend);
500 return baa;
501 }
502
503
504 /*----------------------------------------------------------------------*
505 * Quadtree access *
506 *----------------------------------------------------------------------*/
507 /*!
508 * \brief quadtreeGetParent()
509 *
510 * \param[in] fpixa mean, variance or root variance
511 * \param[in] level, x, y of current pixel
512 * \param[out] pval parent pixel value, or 0.0 on error
513 * \return 0 if OK, 1 on error
514 *
515 * <pre>
516 * Notes:
517 * (1) Check return value for error. On error, val is returned as 0.0.
518 * (2) The parent is located at:
519 * level - 1
520 * (x/2, y/2)
521 * </pre>
522 */
523 l_ok
524 quadtreeGetParent(FPIXA *fpixa,
525 l_int32 level,
526 l_int32 x,
527 l_int32 y,
528 l_float32 *pval)
529 {
530 l_int32 n;
531
532 if (!pval)
533 return ERROR_INT("&val not defined", __func__, 1);
534 *pval = 0.0;
535 if (!fpixa)
536 return ERROR_INT("fpixa not defined", __func__, 1);
537 n = fpixaGetCount(fpixa);
538 if (level < 1 || level >= n)
539 return ERROR_INT("invalid level", __func__, 1);
540
541 if (fpixaGetPixel(fpixa, level - 1, x / 2, y / 2, pval) != 0)
542 return ERROR_INT("invalid coordinates", __func__, 1);
543 return 0;
544 }
545
546
547 /*!
548 * \brief quadtreeGetChildren()
549 *
550 * \param[in] fpixa mean, variance or root variance
551 * \param[in] level, x, y of current pixel
552 * \param[out] pval00, pval01,
553 * pval10, pval11 four child pixel values
554 * \return 0 if OK, 1 on error
555 *
556 * <pre>
557 * Notes:
558 * (1) Check return value for error. On error, all return vals are 0.0.
559 * (2) The returned child pixels are located at:
560 * level + 1
561 * (2x, 2y), (2x+1, 2y), (2x, 2y+1), (2x+1, 2y+1)
562 * </pre>
563 */
564 l_ok
565 quadtreeGetChildren(FPIXA *fpixa,
566 l_int32 level,
567 l_int32 x,
568 l_int32 y,
569 l_float32 *pval00,
570 l_float32 *pval10,
571 l_float32 *pval01,
572 l_float32 *pval11)
573 {
574 l_int32 n;
575
576 if (!pval00 || !pval01 || !pval10 || !pval11)
577 return ERROR_INT("&val* not all defined", __func__, 1);
578 *pval00 = *pval10 = *pval01 = *pval11 = 0.0;
579 if (!fpixa)
580 return ERROR_INT("fpixa not defined", __func__, 1);
581 n = fpixaGetCount(fpixa);
582 if (level < 0 || level >= n - 1)
583 return ERROR_INT("invalid level", __func__, 1);
584
585 if (fpixaGetPixel(fpixa, level + 1, 2 * x, 2 * y, pval00) != 0)
586 return ERROR_INT("invalid coordinates", __func__, 1);
587 fpixaGetPixel(fpixa, level + 1, 2 * x + 1, 2 * y, pval10);
588 fpixaGetPixel(fpixa, level + 1, 2 * x, 2 * y + 1, pval01);
589 fpixaGetPixel(fpixa, level + 1, 2 * x + 1, 2 * y + 1, pval11);
590 return 0;
591 }
592
593
594 /*!
595 * \brief quadtreeMaxLevels()
596 *
597 * \param[in] w, h dimensions of image
598 * \return maxlevels maximum number of levels allowed, or -1 on error
599 *
600 * <pre>
601 * Notes:
602 * (1) The criterion for maxlevels is that the subdivision not
603 * go down below the single pixel level. The 1.5 factor
604 * is intended to keep any rectangle from accidentally
605 * having zero dimension due to integer truncation.
606 * </pre>
607 */
608 l_int32
609 quadtreeMaxLevels(l_int32 w,
610 l_int32 h)
611 {
612 l_int32 i, minside;
613
614 minside = L_MIN(w, h);
615 for (i = 0; i < 20; i++) { /* 2^10 = one million */
616 if (minside < (1.5 * (1 << i)))
617 return i - 1;
618 }
619
620 return -1; /* fail if the image has over a trillion pixels! */
621 }
622
623
624 /*----------------------------------------------------------------------*
625 * Display quadtree *
626 *----------------------------------------------------------------------*/
627 /*!
628 * \brief fpixaDisplayQuadtree()
629 *
630 * \param[in] fpixa mean, variance or root variance
631 * \param[in] factor replication factor at lowest level
632 * \param[in] fontsize 4, ... 20
633 * \return pixd 8 bpp, mosaic of quadtree images, or NULL on error
634 *
635 * <pre>
636 * Notes:
637 * (1) The mean and root variance fall naturally in the 8 bpp range,
638 * but the variance is typically outside the range. This
639 * function displays 8 bpp pix clipped to 255, so the image
640 * pixels will mostly be 255 (white).
641 * </pre>
642 */
643 PIX *
644 fpixaDisplayQuadtree(FPIXA *fpixa,
645 l_int32 factor,
646 l_int32 fontsize)
647 {
648 char buf[256];
649 l_int32 nlevels, i, mag, w;
650 L_BMF *bmf;
651 FPIX *fpix;
652 PIX *pixt1, *pixt2, *pixt3, *pixt4 = NULL, *pixd;
653 PIXA *pixat;
654
655 if (!fpixa)
656 return (PIX *)ERROR_PTR("fpixa not defined", __func__, NULL);
657
658 if ((nlevels = fpixaGetCount(fpixa)) == 0)
659 return (PIX *)ERROR_PTR("pixas empty", __func__, NULL);
660
661 if ((bmf = bmfCreate(NULL, fontsize)) == NULL)
662 L_ERROR("bmf not made; text will not be added", __func__);
663 pixat = pixaCreate(nlevels);
664 for (i = 0; i < nlevels; i++) {
665 fpix = fpixaGetFPix(fpixa, i, L_CLONE);
666 pixt1 = fpixConvertToPix(fpix, 8, L_CLIP_TO_ZERO, 0);
667 mag = factor * (1 << (nlevels - i - 1));
668 pixt2 = pixExpandReplicate(pixt1, mag);
669 pixt3 = pixConvertTo32(pixt2);
670 snprintf(buf, sizeof(buf), "Level %d\n", i);
671 pixt4 = pixAddSingleTextblock(pixt3, bmf, buf, 0xff000000,
672 L_ADD_BELOW, NULL);
673 pixaAddPix(pixat, pixt4, L_INSERT);
674 fpixDestroy(&fpix);
675 pixDestroy(&pixt1);
676 pixDestroy(&pixt2);
677 pixDestroy(&pixt3);
678 }
679 w = pixGetWidth(pixt4);
680 pixd = pixaDisplayTiledInRows(pixat, 32, nlevels * (w + 80), 1.0, 0, 30, 2);
681
682 pixaDestroy(&pixat);
683 bmfDestroy(&bmf);
684 return pixd;
685 }