Leptonica  1.82.0
Image processing and image analysis suite
rank.c
Go to the documentation of this file.
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 
121 #ifdef HAVE_CONFIG_H
122 #include <config_auto.h>
123 #endif /* HAVE_CONFIG_H */
124 
125 #include "allheaders.h"
126 
127 /*----------------------------------------------------------------------*
128  * Rank order filter *
129  *----------------------------------------------------------------------*/
150 PIX *
152  l_int32 wf,
153  l_int32 hf,
154  l_float32 rank)
155 {
156 l_int32 d;
157 
158  PROCNAME("pixRankFilter");
159 
160  if (!pixs)
161  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
162  if (pixGetColormap(pixs) != NULL)
163  return (PIX *)ERROR_PTR("pixs has colormap", procName, NULL);
164  d = pixGetDepth(pixs);
165  if (d != 8 && d != 32)
166  return (PIX *)ERROR_PTR("pixs not 8 or 32 bpp", procName, NULL);
167  if (wf < 1 || hf < 1)
168  return (PIX *)ERROR_PTR("wf < 1 || hf < 1", procName, NULL);
169  if (rank < 0.0 || rank > 1.0)
170  return (PIX *)ERROR_PTR("rank must be in [0.0, 1.0]", procName, NULL);
171  if (wf == 1 && hf == 1) /* no-op */
172  return pixCopy(NULL, pixs);
173 
174  if (d == 8)
175  return pixRankFilterGray(pixs, wf, hf, rank);
176  else /* d == 32 */
177  return pixRankFilterRGB(pixs, wf, hf, rank);
178 }
179 
180 
202 PIX *
204  l_int32 wf,
205  l_int32 hf,
206  l_float32 rank)
207 {
208 PIX *pixr, *pixg, *pixb, *pixrf, *pixgf, *pixbf, *pixd;
209 
210  PROCNAME("pixRankFilterRGB");
211 
212  if (!pixs)
213  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
214  if (pixGetDepth(pixs) != 32)
215  return (PIX *)ERROR_PTR("pixs not 32 bpp", procName, NULL);
216  if (wf < 1 || hf < 1)
217  return (PIX *)ERROR_PTR("wf < 1 || hf < 1", procName, NULL);
218  if (rank < 0.0 || rank > 1.0)
219  return (PIX *)ERROR_PTR("rank must be in [0.0, 1.0]", procName, NULL);
220  if (wf == 1 && hf == 1) /* no-op */
221  return pixCopy(NULL, pixs);
222 
223  pixr = pixGetRGBComponent(pixs, COLOR_RED);
224  pixg = pixGetRGBComponent(pixs, COLOR_GREEN);
225  pixb = pixGetRGBComponent(pixs, COLOR_BLUE);
226 
227  pixrf = pixRankFilterGray(pixr, wf, hf, rank);
228  pixgf = pixRankFilterGray(pixg, wf, hf, rank);
229  pixbf = pixRankFilterGray(pixb, wf, hf, rank);
230 
231  pixd = pixCreateRGBImage(pixrf, pixgf, pixbf);
232  pixDestroy(&pixr);
233  pixDestroy(&pixg);
234  pixDestroy(&pixb);
235  pixDestroy(&pixrf);
236  pixDestroy(&pixgf);
237  pixDestroy(&pixbf);
238  return pixd;
239 }
240 
241 
270 PIX *
272  l_int32 wf,
273  l_int32 hf,
274  l_float32 rank)
275 {
276 l_int32 w, h, d, i, j, k, m, n, rankloc, wplt, wpld, val, sum;
277 l_int32 *histo, *histo16;
278 l_uint32 *datat, *linet, *datad, *lined;
279 PIX *pixt, *pixd;
280 
281  PROCNAME("pixRankFilterGray");
282 
283  if (!pixs)
284  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
285  if (pixGetColormap(pixs) != NULL)
286  return (PIX *)ERROR_PTR("pixs has colormap", procName, NULL);
287  pixGetDimensions(pixs, &w, &h, &d);
288  if (d != 8)
289  return (PIX *)ERROR_PTR("pixs not 8 bpp", procName, NULL);
290  if (wf < 1 || hf < 1)
291  return (PIX *)ERROR_PTR("wf < 1 || hf < 1", procName, NULL);
292  if (rank < 0.0 || rank > 1.0)
293  return (PIX *)ERROR_PTR("rank must be in [0.0, 1.0]", procName, NULL);
294  if (wf == 1 && hf == 1) /* no-op */
295  return pixCopy(NULL, pixs);
296 
297  /* For rank = 0.0, this is a grayscale erosion, and for rank = 1.0,
298  * a dilation. Grayscale morphology operations are implemented
299  * for filters of odd dimension, so we dispatch to grayscale
300  * morphology if both wf and hf are odd. Otherwise, we
301  * slightly adjust the rank (to get the correct behavior) and
302  * use the slower rank filter here. */
303  if (wf % 2 && hf % 2) {
304  if (rank == 0.0)
305  return pixErodeGray(pixs, wf, hf);
306  else if (rank == 1.0)
307  return pixDilateGray(pixs, wf, hf);
308  }
309  if (rank == 0.0) rank = 0.0001;
310  if (rank == 1.0) rank = 0.9999;
311 
312  /* Add wf/2 to each side, and hf/2 to top and bottom of the
313  * image, mirroring for accuracy and to avoid special-casing
314  * the boundary. */
315  if ((pixt = pixAddMirroredBorder(pixs, wf / 2, wf / 2, hf / 2, hf / 2))
316  == NULL)
317  return (PIX *)ERROR_PTR("pixt not made", procName, NULL);
318 
319  /* Set up the two histogram arrays. */
320  histo = (l_int32 *)LEPT_CALLOC(256, sizeof(l_int32));
321  histo16 = (l_int32 *)LEPT_CALLOC(16, sizeof(l_int32));
322  rankloc = (l_int32)(rank * wf * hf);
323 
324  /* Place the filter center at (0, 0). This is just a
325  * convenient location, because it allows us to perform
326  * the rank filter over x:(0 ... w - 1) and y:(0 ... h - 1). */
327  pixd = pixCreateTemplate(pixs);
328  datat = pixGetData(pixt);
329  wplt = pixGetWpl(pixt);
330  datad = pixGetData(pixd);
331  wpld = pixGetWpl(pixd);
332 
333  /* If hf > wf, it's more efficient to use row-major scanning.
334  * Otherwise, traverse the image in use column-major order. */
335  if (hf > wf) {
336  for (j = 0; j < w; j++) { /* row-major */
337  /* Start each column with clean histogram arrays. */
338  for (n = 0; n < 256; n++)
339  histo[n] = 0;
340  for (n = 0; n < 16; n++)
341  histo16[n] = 0;
342 
343  for (i = 0; i < h; i++) { /* fast scan on columns */
344  /* Update the histos for the new location */
345  lined = datad + i * wpld;
346  if (i == 0) { /* do full histo */
347  for (k = 0; k < hf; k++) {
348  linet = datat + (i + k) * wplt;
349  for (m = 0; m < wf; m++) {
350  val = GET_DATA_BYTE(linet, j + m);
351  histo[val]++;
352  histo16[val >> 4]++;
353  }
354  }
355  } else { /* incremental update */
356  linet = datat + (i - 1) * wplt;
357  for (m = 0; m < wf; m++) { /* remove top line */
358  val = GET_DATA_BYTE(linet, j + m);
359  histo[val]--;
360  histo16[val >> 4]--;
361  }
362  linet = datat + (i + hf - 1) * wplt;
363  for (m = 0; m < wf; m++) { /* add bottom line */
364  val = GET_DATA_BYTE(linet, j + m);
365  histo[val]++;
366  histo16[val >> 4]++;
367  }
368  }
369 
370  /* Find the rank value */
371  sum = 0;
372  for (n = 0; n < 16; n++) { /* search over coarse histo */
373  sum += histo16[n];
374  if (sum > rankloc) {
375  sum -= histo16[n];
376  break;
377  }
378  }
379  if (n == 16) { /* avoid accessing out of bounds */
380  L_WARNING("n = 16; reducing\n", procName);
381  n = 15;
382  sum -= histo16[n];
383  }
384  k = 16 * n; /* starting value in fine histo */
385  for (m = 0; m < 16; m++) {
386  sum += histo[k];
387  if (sum > rankloc) {
388  SET_DATA_BYTE(lined, j, k);
389  break;
390  }
391  k++;
392  }
393  }
394  }
395  } else { /* wf >= hf */
396  for (i = 0; i < h; i++) { /* column-major */
397  /* Start each row with clean histogram arrays. */
398  for (n = 0; n < 256; n++)
399  histo[n] = 0;
400  for (n = 0; n < 16; n++)
401  histo16[n] = 0;
402  lined = datad + i * wpld;
403  for (j = 0; j < w; j++) { /* fast scan on rows */
404  /* Update the histos for the new location */
405  if (j == 0) { /* do full histo */
406  for (k = 0; k < hf; k++) {
407  linet = datat + (i + k) * wplt;
408  for (m = 0; m < wf; m++) {
409  val = GET_DATA_BYTE(linet, j + m);
410  histo[val]++;
411  histo16[val >> 4]++;
412  }
413  }
414  } else { /* incremental update at left and right sides */
415  for (k = 0; k < hf; k++) {
416  linet = datat + (i + k) * wplt;
417  val = GET_DATA_BYTE(linet, j - 1);
418  histo[val]--;
419  histo16[val >> 4]--;
420  val = GET_DATA_BYTE(linet, j + wf - 1);
421  histo[val]++;
422  histo16[val >> 4]++;
423  }
424  }
425 
426  /* Find the rank value */
427  sum = 0;
428  for (n = 0; n < 16; n++) { /* search over coarse histo */
429  sum += histo16[n];
430  if (sum > rankloc) {
431  sum -= histo16[n];
432  break;
433  }
434  }
435  if (n == 16) { /* avoid accessing out of bounds */
436  L_WARNING("n = 16; reducing\n", procName);
437  n = 15;
438  sum -= histo16[n];
439  }
440  k = 16 * n; /* starting value in fine histo */
441  for (m = 0; m < 16; m++) {
442  sum += histo[k];
443  if (sum > rankloc) {
444  SET_DATA_BYTE(lined, j, k);
445  break;
446  }
447  k++;
448  }
449  }
450  }
451  }
452 
453  pixDestroy(&pixt);
454  LEPT_FREE(histo);
455  LEPT_FREE(histo16);
456  return pixd;
457 }
458 
459 
460 /*----------------------------------------------------------------------*
461  * Median filter *
462  *----------------------------------------------------------------------*/
470 PIX *
472  l_int32 wf,
473  l_int32 hf)
474 {
475  PROCNAME("pixMedianFilter");
476 
477  if (!pixs)
478  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
479  return pixRankFilter(pixs, wf, hf, 0.5);
480 }
481 
482 
483 /*----------------------------------------------------------------------*
484  * Rank filter (accelerated with downscaling) *
485  *----------------------------------------------------------------------*/
505 PIX *
507  l_int32 wf,
508  l_int32 hf,
509  l_float32 rank,
510  l_float32 scalefactor)
511 {
512 l_int32 w, h, d, wfs, hfs;
513 PIX *pix1, *pix2, *pixd;
514 
515  PROCNAME("pixRankFilterWithScaling");
516 
517  if (!pixs)
518  return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
519  if (pixGetColormap(pixs) != NULL)
520  return (PIX *)ERROR_PTR("pixs has colormap", procName, NULL);
521  d = pixGetDepth(pixs);
522  if (d != 8 && d != 32)
523  return (PIX *)ERROR_PTR("pixs not 8 or 32 bpp", procName, NULL);
524  if (wf < 1 || hf < 1)
525  return (PIX *)ERROR_PTR("wf < 1 || hf < 1", procName, NULL);
526  if (rank < 0.0 || rank > 1.0)
527  return (PIX *)ERROR_PTR("rank must be in [0.0, 1.0]", procName, NULL);
528  if (wf == 1 && hf == 1) /* no-op */
529  return pixCopy(NULL, pixs);
530  if (scalefactor < 0.2 || scalefactor > 0.7) {
531  L_ERROR("invalid scale factor; no scaling used\n", procName);
532  return pixRankFilter(pixs, wf, hf, rank);
533  }
534 
535  pix1 = pixScaleAreaMap(pixs, scalefactor, scalefactor);
536  wfs = L_MAX(1, (l_int32)(scalefactor * wf + 0.5));
537  hfs = L_MAX(1, (l_int32)(scalefactor * hf + 0.5));
538  pix2 = pixRankFilter(pix1, wfs, hfs, rank);
539  pixGetDimensions(pixs, &w, &h, NULL);
540  pixd = pixScaleToSize(pix2, w, h);
541  pixDestroy(&pix1);
542  pixDestroy(&pix2);
543  return pixd;
544 }
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
PIX * pixDilateGray(PIX *pixs, l_int32 hsize, l_int32 vsize)
pixDilateGray()
Definition: graymorph.c:278
PIX * pixErodeGray(PIX *pixs, l_int32 hsize, l_int32 vsize)
pixErodeGray()
Definition: graymorph.c:162
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
void pixDestroy(PIX **ppix)
pixDestroy()
Definition: pix1.c:621
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
PIX * pixCopy(PIX *pixd, const PIX *pixs)
pixCopy()
Definition: pix1.c:705
PIX * pixCreateTemplate(const PIX *pixs)
pixCreateTemplate()
Definition: pix1.c:383
PIX * pixGetRGBComponent(PIX *pixs, l_int32 comp)
pixGetRGBComponent()
Definition: pix2.c:2479
PIX * pixCreateRGBImage(PIX *pixr, PIX *pixg, PIX *pixb)
pixCreateRGBImage()
Definition: pix2.c:2423
PIX * pixAddMirroredBorder(PIX *pixs, l_int32 left, l_int32 right, l_int32 top, l_int32 bot)
pixAddMirroredBorder()
Definition: pix2.c:2101
@ COLOR_BLUE
Definition: pix.h:206
@ COLOR_RED
Definition: pix.h:204
@ COLOR_GREEN
Definition: pix.h:205
PIX * pixRankFilterGray(PIX *pixs, l_int32 wf, l_int32 hf, l_float32 rank)
pixRankFilterGray()
Definition: rank.c:271
PIX * pixMedianFilter(PIX *pixs, l_int32 wf, l_int32 hf)
pixMedianFilter()
Definition: rank.c:471
PIX * pixRankFilterRGB(PIX *pixs, l_int32 wf, l_int32 hf, l_float32 rank)
pixRankFilterRGB()
Definition: rank.c:203
PIX * pixRankFilterWithScaling(PIX *pixs, l_int32 wf, l_int32 hf, l_float32 rank, l_float32 scalefactor)
pixRankFilterWithScaling()
Definition: rank.c:506
PIX * pixRankFilter(PIX *pixs, l_int32 wf, l_int32 hf, l_float32 rank)
pixRankFilter()
Definition: rank.c:151
PIX * pixScaleAreaMap(PIX *pix, l_float32 scalex, l_float32 scaley)
pixScaleAreaMap()
Definition: scale1.c:1914
PIX * pixScaleToSize(PIX *pixs, l_int32 wd, l_int32 hd)
pixScaleToSize()
Definition: scale1.c:323
Definition: pix.h:139