Leptonica 1.68
C Image Processing Library

quadtree.c File Reference

Quadtree creation and statistics. More...

#include <math.h>
#include "allheaders.h"

Go to the source code of this file.

Defines

#define DEBUG_BOXES   0

Functions

l_int32 pixQuadtreeMean (PIX *pixs, l_int32 nlevels, PIX *pix_ma, FPIXA **pfpixa)
l_int32 pixQuadtreeVariance (PIX *pixs, l_int32 nlevels, PIX *pix_ma, DPIX *dpix_msa, FPIXA **pfpixa_v, FPIXA **pfpixa_rv)
l_int32 pixMeanInRectangle (PIX *pixs, BOX *box, PIX *pixma, l_float32 *pval)
l_int32 pixVarianceInRectangle (PIX *pixs, BOX *box, PIX *pix_ma, DPIX *dpix_msa, l_float32 *pvar, l_float32 *prvar)
BOXAAboxaaQuadtreeRegions (l_int32 w, l_int32 h, l_int32 nlevels)
l_int32 quadtreeGetParent (FPIXA *fpixa, l_int32 level, l_int32 x, l_int32 y, l_float32 *pval)
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)
l_int32 quadtreeMaxLevels (l_int32 w, l_int32 h)
PIXfpixaDisplayQuadtree (FPIXA *fpixa, l_int32 factor)

Detailed Description

Quadtree creation and statistics.

    Top level quadtree linear statistics
        l_int32   pixQuadtreeMean()
        l_int32   pixQuadtreeVariance()

    Statistics in an arbitrary rectangle
        l_int32   pixMeanInRectangle()
        l_int32   pixVarianceInRectangle()

    Quadtree regions
        BOXAA    *boxaaQuadtreeRegions()

    Quadtree access
        l_int32   quadtreeGetParent()
        l_int32   quadtreeGetChildren()
        l_int32   quadtreeMaxLevels()

    Display quadtree
        PIX      *fpixaDisplayQuadtree()


There are many other statistical quantities that can be computed
in a quadtree, such as rank values, and these can be added as
the need arises.

Similar results that can approximate a single level of the quadtree
can be generated by pixGetAverageTiled().  There we specify the
tile size over which the mean, mean square, and root variance
are generated; the results are saved in a (reduced size) pix.
Because the tile dimensions are integers, it is usually not possible
to obtain tilings that are a power of 2, as required for quadtrees.

Definition in file quadtree.c.


Define Documentation

#define DEBUG_BOXES   0

Definition at line 55 of file quadtree.c.


Function Documentation

l_int32 pixQuadtreeMean ( PIX pixs,
l_int32  nlevels,
PIX pix_ma,
FPIXA **  pfpixa 
)

pixQuadtreeMean()

Input: pixs (8 bpp, no colormap) nlevels (in quadtree; max allowed depends on image size) *pix_ma (input mean accumulator; can be null) *pfpixa (<return> mean values in quadtree) Return: 0 if OK, 1 on error

Notes: (1) The returned fpixa has of fpix, each containing the mean values at its level. Level 0 has a single value; level 1 has 4 values; level 2 has 16; etc.

Definition at line 77 of file quadtree.c.

References boxaaDestroy(), boxaaGetBoxa(), boxaaQuadtreeRegions(), boxaDestroy(), boxaGetBox(), boxaGetCount(), boxDestroy(), ERROR_INT, fpixaAddFPix(), fpixaCreate(), fpixCreate(), fpixSetPixel(), L_CLONE, L_INSERT, nlevels, NULL, pixBlockconvAccum(), pixClone(), pixDestroy(), pixGetDepth(), pixGetDimensions(), pixMeanInRectangle(), PROCNAME, quadtreeMaxLevels(), and size.

Referenced by main().

l_int32 pixQuadtreeVariance ( PIX pixs,
l_int32  nlevels,
PIX pix_ma,
DPIX dpix_msa,
FPIXA **  pfpixa_v,
FPIXA **  pfpixa_rv 
)

pixQuadtreeVariance()

Input: pixs (8 bpp, no colormap) nlevels (in quadtree) *pix_ma (input mean accumulator; can be null) *dpix_msa (input mean square accumulator; can be null) *pfpixa_v (<optional return>=""> variance values in quadtree) *pfpixa_rv (<optional return>=""> root variance values in quadtree) Return: 0 if OK, 1 on error

Notes: (1) The returned fpixav and fpixarv have of fpix, each containing at the respective levels the variance and root variance values.

Definition at line 152 of file quadtree.c.

References boxaaDestroy(), boxaaGetBoxa(), boxaaQuadtreeRegions(), boxaDestroy(), boxaGetBox(), boxaGetCount(), boxDestroy(), dpixClone(), dpixDestroy(), ERROR_INT, fpixaAddFPix(), fpixaCreate(), fpixCreate(), fpixSetPixel(), L_CLONE, L_INSERT, nlevels, NULL, pixBlockconvAccum(), pixClone(), pixDestroy(), pixGetDepth(), pixGetDimensions(), pixMeanSquareAccum(), pixVarianceInRectangle(), PROCNAME, quadtreeMaxLevels(), and size.

Referenced by main().

l_int32 pixMeanInRectangle ( PIX pixs,
BOX box,
PIX pixma,
l_float32 pval 
)

pixMeanInRectangle()

Input: pix (8 bpp) box (region to compute mean value) pixma (mean accumulator) &val (<return> mean value Return: 0 if OK, 1 on error

Notes: (1) This function is intended to be used for many rectangles on the same image. It can find the mean within a rectangle in O(1), independent of the size of the rectangle.

Definition at line 244 of file quadtree.c.

References boxClipToRectangle(), boxDestroy(), boxGetGeometry(), ERROR_INT, NULL, pixGetDepth(), pixGetDimensions(), pixGetPixel(), and PROCNAME.

Referenced by pixQuadtreeMean().

l_int32 pixVarianceInRectangle ( PIX pixs,
BOX box,
PIX pix_ma,
DPIX dpix_msa,
l_float32 pvar,
l_float32 prvar 
)

pixVarianceInRectangle()

Input: pix (8 bpp) box (region to compute variance and/or root variance) pix_ma (mean accumulator) dpix_msa (mean square accumulator) &var (<optional return>=""> variance) &rvar (<optional return>=""> root variance) Return: 0 if OK, 1 on error

Notes: (1) This function is intended to be used for many rectangles on the same image. It can find the variance and/or the square root of the variance within a rectangle in O(1), independent of the size of the rectangle.

Definition at line 321 of file quadtree.c.

References boxClipToRectangle(), boxDestroy(), boxGetGeometry(), dpixGetPixel(), ERROR_INT, NULL, pixGetDepth(), pixGetDimensions(), pixGetPixel(), and PROCNAME.

Referenced by pixQuadtreeVariance().

BOXAA* boxaaQuadtreeRegions ( l_int32  w,
l_int32  h,
l_int32  nlevels 
)

boxaaQuadtreeRegions()

Input: w, h (of pix that is being quadtree-ized) nlevels (in quadtree) Return: baa (for quadtree regions at each level), or null on error

Notes: (1) The returned boxaa has of boxa, each containing the set of rectangles at that level. The rectangle at level 0 is the entire region; at level 1 the region is divided into 4 rectangles, and at level n there are n^4 rectangles. (2) At each level, the rectangles in the boxa are in "raster" order, with LR (fast scan) and TB (slow scan).

Definition at line 430 of file quadtree.c.

References boxaaAddBoxa(), boxaaCreate(), boxaAddBox(), boxaCreate(), boxCreate(), CALLOC, ERROR_PTR, FREE, L_INSERT, nlevels, NULL, and PROCNAME.

Referenced by main(), pixQuadtreeMean(), and pixQuadtreeVariance().

l_int32 quadtreeGetParent ( FPIXA fpixa,
l_int32  level,
l_int32  x,
l_int32  y,
l_float32 pval 
)

quadtreeGetParent()

Input: fpixa (mean, variance or root variance) level, x, y (of current pixel) &val (<return> parent pixel value), or 0.0 on error. Return: 0 if OK, 1 on error

Notes: (1) Check return value for error. On error, val is returned as 0.0. (2) The parent is located at: level - 1 (x/2, y/2)

Definition at line 509 of file quadtree.c.

References ERROR_INT, fpixaGetCount(), fpixaGetPixel(), and PROCNAME.

Referenced by main().

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 
)

quadtreeGetChildren()

Input: fpixa (mean, variance or root variance) level, x, y (of current pixel) &val00, val01, val10, val11 (<return> child pixel values) Return: 0 if OK, 1 on error

Notes: (1) Check return value for error. On error, all return vals are 0.0. (2) The returned child pixels are located at: level + 1 (2x, 2y), (2x+1, 2y), (2x, 2y+1), (2x+1, 2y+1)

Definition at line 549 of file quadtree.c.

References ERROR_INT, fpixaGetCount(), fpixaGetPixel(), and PROCNAME.

Referenced by main().

l_int32 quadtreeMaxLevels ( l_int32  w,
l_int32  h 
)

quadtreeMaxLevels()

Input: w, h (of image) Return: maxlevels (maximum number of levels allowed), or -1 on error

Notes: (1) The criterion for maxlevels is that the subdivision not go down below the single pixel level. The 1.5 factor is intended to keep any rectangle from accidentally having zero dimension due to integer truncation.

Definition at line 593 of file quadtree.c.

References L_MIN.

Referenced by pixQuadtreeMean(), and pixQuadtreeVariance().

PIX* fpixaDisplayQuadtree ( FPIXA fpixa,
l_int32  factor 
)

fpixaDisplayQuadtree()

Input: fpixa (mean, variance or root variance) factor (replication factor at lowest level) Return: pixd (8 bpp, mosaic of quadtree images), or null on error

Notes: (1) The mean and root variance fall naturally in the 8 bpp range, but the variance is typically outside the range. This function displays 8 bpp pix clipped to 255, so the image pixels will mostly be 255 (white).

Definition at line 625 of file quadtree.c.

References bmfCreate(), bmfDestroy(), buf, ERROR_PTR, fpixaGetCount(), fpixaGetFPix(), fpixConvertToPix(), fpixDestroy(), L_ADD_BELOW, L_CLIP_TO_ZERO, L_CLONE, L_INSERT, nlevels, NULL, pixaAddPix(), pixaCreate(), pixAddSingleTextblock(), pixaDestroy(), pixaDisplayTiledInRows(), pixConvertTo32(), pixDestroy(), pixExpandReplicate(), pixGetWidth(), and PROCNAME.

Referenced by main().

 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines