Leptonica 1.68
C Image Processing Library

Rank order filters (generalization of min/median/max filters) More...
Go to the source code of this file.
Functions  
PIX *  pixRankFilter (PIX *pixs, l_int32 wf, l_int32 hf, l_float32 rank) 
PIX *  pixRankFilterRGB (PIX *pixs, l_int32 wf, l_int32 hf, l_float32 rank) 
PIX *  pixRankFilterGray (PIX *pixs, l_int32 wf, l_int32 hf, l_float32 rank) 
PIX *  pixMedianFilter (PIX *pixs, l_int32 wf, l_int32 hf) 
Rank order filters (generalization of min/median/max filters)
Rank filter (gray and rgb) PIX *pixRankFilter() PIX *pixRankFilterRGB() PIX *pixRankFilterGray() Median filter PIX *pixMedianFilter() What is a brick rank filter? A brick rank order filter evaluates, for every pixel in the image, a rectangular set of n = wf x hf pixels in its neighborhood (where the pixel in question is at the "center" of the rectangle and is included in the evaluation). It determines the value of the neighboring pixel that is the rth smallest in the set, where r is some integer between 1 and n. The input rank parameter is a fraction between 0.0 and 1.0, where 0.0 represents the smallest value (r = 1) and 1.0 represents the largest value (r = n). A median filter is a rank filter where rank = 0.5. It is important to note that grayscale erosion is equivalent to rank = 0.0, and grayscale dilation is equivalent to rank = 1.0. These are much easier to calculate than the general rank value, thanks to the van Herk/GilWerman algorithm: http://www.leptonica.com/grayscalemorphology.html so you should use pixErodeGray() and pixDilateGray() for rank 0.0 and 1.0, rsp. See notes below in the function header. How is a rank filter implemented efficiently on an image? Sorting will not work. The best sort algorithms are O(n*logn), where n is the number of values to be sorted (the area of the filter). For large filters this is an impractically large number. Selection of the rank value is O(n). (To understand why it's not O(n*logn), see Numerical Recipes in C, 2nd edition, 1992, p. 355ff). This also still far too much computation for large filters. Suppose we get clever. We really only need to do an incremental selection or sorting, because, for example, moving the filter down by one pixel causes one filter width of pixels to be added and another to be removed. Can we do this incrementally in an efficient way? Unfortunately, no. The sorted values will be in an array. Even if the filter width is 1, we can expect to have to move O(n) pixels, because insertion and deletion can happen anywhere in the array. By comparison, heapsort is excellent for incremental sorting, where the cost for insertion or deletion is O(logn), because the array itself doesn't need to be sorted into strictly increasing order. However, heapsort only gives the max (or min) value, not the general rank value. This leaves histograms. Represented as an array. The problem with an array of 256 bins is that, in general, a significant fraction of the entire histogram must be summed to find the rank value bin. Suppose the filter size is 5x5. You spend most of your time adding zeroes. Ouch! Represented as a linked list. This would overcome the summingoveremptybin problem, but you lose random access for insertions and deletions. No way. Two histogram solution. Maintain two histograms with bin sizes of 1 and 16. Proceed from coarse to fine. First locate the coarse bin for the given rank, of which there are only 16. Then, in the 256 entry (fine) histogram, you need look at a maximum of 16 bins. For each output pixel, the average number of bins summed over, both in the coarse and fine histograms, is thus 16. If someone has a better method, please let me know!
Definition in file rank.c.
Input: pixs (8 or 32 bpp; no colormap) wf, hf (width and height of filter; each is >= 1) rank (in [0.0 ... 1.0]) Return: pixd (of rank values), or null on error
Notes: (1) This defines, for each pixel in pixs, a neighborhood of pixels given by a rectangle "centered" on the pixel. This set of wf*hf pixels has a distribution of values. For each component, if the values are sorted in increasing order, we choose the component such that rank*(wf*hf1) pixels have a lower or equal value and (1rank)*(wf*hf1) pixels have an equal or greater value. (2) See notes in pixRankFilterGray() for further details.
Definition at line 122 of file rank.c.
References ERROR_PTR, NULL, pixCopy(), pixGetColormap(), pixGetDepth(), pixRankFilterGray(), pixRankFilterRGB(), and PROCNAME.
Referenced by main(), and pixMedianFilter().
Input: pixs (32 bpp) wf, hf (width and height of filter; each is >= 1) rank (in [0.0 ... 1.0]) Return: pixd (of rank values), or null on error
Notes: (1) This defines, for each pixel in pixs, a neighborhood of pixels given by a rectangle "centered" on the pixel. This set of wf*hf pixels has a distribution of values. For each component, if the values are sorted in increasing order, we choose the component such that rank*(wf*hf1) pixels have a lower or equal value and (1rank)*(wf*hf1) pixels have an equal or greater value. (2) Apply gray rank filtering to each component independently. (3) See notes in pixRankFilterGray() for further details.
Definition at line 172 of file rank.c.
References COLOR_BLUE, COLOR_GREEN, COLOR_RED, ERROR_PTR, NULL, pixCopy(), pixCreateRGBImage(), pixDestroy(), pixGetDepth(), pixGetRGBComponent(), pixRankFilterGray(), and PROCNAME.
Referenced by pixRankFilter().
Input: pixs (8 bpp; no colormap) wf, hf (width and height of filter; each is >= 1) rank (in [0.0 ... 1.0]) Return: pixd (of rank values), or null on error
Notes: (1) This defines, for each pixel in pixs, a neighborhood of pixels given by a rectangle "centered" on the pixel. This set of wf*hf pixels has a distribution of values, and if they are sorted in increasing order, we choose the pixel such that rank*(wf*hf1) pixels have a lower or equal value and (1rank)*(wf*hf1) pixels have an equal or greater value. (2) By this definition, the rank = 0.0 pixel has the lowest value, and the rank = 1.0 pixel has the highest value. (3) We add mirrored boundary pixels to avoid boundary effects, and put the filter center at (0, 0). (4) This dispatches to grayscale erosion or dilation if the filter dimensions are odd and the rank is 0.0 or 1.0, rsp. (5) Returns a copy if both wf and hf are 1. (6) Uses rowmajor or columnmajor incremental updates to the histograms depending on whether hf > wf or hv <= wf, rsp.
Definition at line 238 of file rank.c.
References CALLOC, ERROR_PTR, FREE, GET_DATA_BYTE, NULL, pixAddMirroredBorder(), pixCopy(), pixCreateTemplate(), pixDestroy(), pixDilateGray(), pixErodeGray(), pixGetColormap(), pixGetData(), pixGetDimensions(), pixGetWpl(), PROCNAME, and SET_DATA_BYTE.
Referenced by main(), pixRankFilter(), and pixRankFilterRGB().