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