Leptonica  1.83.1
Image processing and image analysis suite
edge.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 
61 #ifdef HAVE_CONFIG_H
62 #include <config_auto.h>
63 #endif /* HAVE_CONFIG_H */
64 
65 #include "allheaders.h"
66 
67 /*----------------------------------------------------------------------*
68  * Sobel edge detecting filter *
69  *----------------------------------------------------------------------*/
93 PIX *
95  l_int32 orientflag)
96 {
97 l_int32 w, h, d, i, j, wplt, wpld, gx, gy, vald;
98 l_int32 val1, val2, val3, val4, val5, val6, val7, val8, val9;
99 l_uint32 *datat, *linet, *datad, *lined;
100 PIX *pixt, *pixd;
101 
102  if (!pixs)
103  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
104  pixGetDimensions(pixs, &w, &h, &d);
105  if (d != 8)
106  return (PIX *)ERROR_PTR("pixs not 8 bpp", __func__, NULL);
107  if (orientflag != L_HORIZONTAL_EDGES && orientflag != L_VERTICAL_EDGES &&
108  orientflag != L_ALL_EDGES)
109  return (PIX *)ERROR_PTR("invalid orientflag", __func__, NULL);
110 
111  /* Add 1 pixel (mirrored) to each side of the image. */
112  if ((pixt = pixAddMirroredBorder(pixs, 1, 1, 1, 1)) == NULL)
113  return (PIX *)ERROR_PTR("pixt not made", __func__, NULL);
114 
115  /* Compute filter output at each location. */
116  pixd = pixCreateTemplate(pixs);
117  datat = pixGetData(pixt);
118  wplt = pixGetWpl(pixt);
119  datad = pixGetData(pixd);
120  wpld = pixGetWpl(pixd);
121  for (i = 0; i < h; i++) {
122  linet = datat + i * wplt;
123  lined = datad + i * wpld;
124  for (j = 0; j < w; j++) {
125  if (j == 0) { /* start a new row */
126  val1 = GET_DATA_BYTE(linet, j);
127  val2 = GET_DATA_BYTE(linet + wplt, j);
128  val3 = GET_DATA_BYTE(linet + 2 * wplt, j);
129  val4 = GET_DATA_BYTE(linet, j + 1);
130  val5 = GET_DATA_BYTE(linet + wplt, j + 1);
131  val6 = GET_DATA_BYTE(linet + 2 * wplt, j + 1);
132  val7 = GET_DATA_BYTE(linet, j + 2);
133  val8 = GET_DATA_BYTE(linet + wplt, j + 2);
134  val9 = GET_DATA_BYTE(linet + 2 * wplt, j + 2);
135  } else { /* shift right by 1 pixel; update incrementally */
136  val1 = val4;
137  val2 = val5;
138  val3 = val6;
139  val4 = val7;
140  val5 = val8;
141  val6 = val9;
142  val7 = GET_DATA_BYTE(linet, j + 2);
143  val8 = GET_DATA_BYTE(linet + wplt, j + 2);
144  val9 = GET_DATA_BYTE(linet + 2 * wplt, j + 2);
145  }
146  if (orientflag == L_HORIZONTAL_EDGES)
147  vald = L_ABS(val1 + 2 * val4 + val7
148  - val3 - 2 * val6 - val9) >> 3;
149  else if (orientflag == L_VERTICAL_EDGES)
150  vald = L_ABS(val1 + 2 * val2 + val3 - val7
151  - 2 * val8 - val9) >> 3;
152  else { /* L_ALL_EDGES */
153  gx = L_ABS(val1 + 2 * val2 + val3 - val7
154  - 2 * val8 - val9) >> 3;
155  gy = L_ABS(val1 + 2 * val4 + val7
156  - val3 - 2 * val6 - val9) >> 3;
157  vald = L_MIN(255, gx + gy);
158  }
159  SET_DATA_BYTE(lined, j, vald);
160  }
161  }
162 
163  pixDestroy(&pixt);
164  return pixd;
165 }
166 
167 
168 /*----------------------------------------------------------------------*
169  * Two-sided edge gradient filter *
170  *----------------------------------------------------------------------*/
199 PIX *
201  l_int32 orientflag)
202 {
203 l_int32 w, h, d, i, j, wpls, wpld;
204 l_int32 cval, rval, bval, val, lgrad, rgrad, tgrad, bgrad;
205 l_uint32 *datas, *lines, *datad, *lined;
206 PIX *pixd;
207 
208  if (!pixs)
209  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
210  pixGetDimensions(pixs, &w, &h, &d);
211  if (d != 8)
212  return (PIX *)ERROR_PTR("pixs not 8 bpp", __func__, NULL);
213  if (orientflag != L_HORIZONTAL_EDGES && orientflag != L_VERTICAL_EDGES)
214  return (PIX *)ERROR_PTR("invalid orientflag", __func__, NULL);
215 
216  pixd = pixCreateTemplate(pixs);
217  datas = pixGetData(pixs);
218  wpls = pixGetWpl(pixs);
219  datad = pixGetData(pixd);
220  wpld = pixGetWpl(pixd);
221  if (orientflag == L_VERTICAL_EDGES) {
222  for (i = 0; i < h; i++) {
223  lines = datas + i * wpls;
224  lined = datad + i * wpld;
225  cval = GET_DATA_BYTE(lines, 1);
226  lgrad = cval - GET_DATA_BYTE(lines, 0);
227  for (j = 1; j < w - 1; j++) {
228  rval = GET_DATA_BYTE(lines, j + 1);
229  rgrad = rval - cval;
230  if (lgrad * rgrad > 0) {
231  if (lgrad < 0)
232  val = -L_MAX(lgrad, rgrad);
233  else
234  val = L_MIN(lgrad, rgrad);
235  SET_DATA_BYTE(lined, j, val);
236  }
237  lgrad = rgrad;
238  cval = rval;
239  }
240  }
241  }
242  else { /* L_HORIZONTAL_EDGES) */
243  for (j = 0; j < w; j++) {
244  lines = datas + wpls;
245  cval = GET_DATA_BYTE(lines, j); /* for line 1 */
246  tgrad = cval - GET_DATA_BYTE(datas, j);
247  for (i = 1; i < h - 1; i++) {
248  lines += wpls; /* for line i + 1 */
249  lined = datad + i * wpld;
250  bval = GET_DATA_BYTE(lines, j);
251  bgrad = bval - cval;
252  if (tgrad * bgrad > 0) {
253  if (tgrad < 0)
254  val = -L_MAX(tgrad, bgrad);
255  else
256  val = L_MIN(tgrad, bgrad);
257  SET_DATA_BYTE(lined, j, val);
258  }
259  tgrad = bgrad;
260  cval = bval;
261  }
262  }
263  }
264 
265  return pixd;
266 }
267 
268 
269 /*----------------------------------------------------------------------*
270  * Measurement of edge smoothness *
271  *----------------------------------------------------------------------*/
307 l_ok
309  l_int32 side,
310  l_int32 minjump,
311  l_int32 minreversal,
312  l_float32 *pjpl,
313  l_float32 *pjspl,
314  l_float32 *prpl,
315  const char *debugfile)
316 {
317 l_int32 i, n, val, nval, diff, njumps, jumpsum, nreversal;
318 NUMA *na, *nae;
319 
320  if (pjpl) *pjpl = 0.0;
321  if (pjspl) *pjspl = 0.0;
322  if (prpl) *prpl = 0.0;
323  if (!pjpl && !pjspl && !prpl && !debugfile)
324  return ERROR_INT("no output requested", __func__, 1);
325  if (!pixs || pixGetDepth(pixs) != 1)
326  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
327  if (side != L_FROM_LEFT && side != L_FROM_RIGHT &&
328  side != L_FROM_TOP && side != L_FROM_BOT)
329  return ERROR_INT("invalid side", __func__, 1);
330  if (minjump < 1)
331  return ERROR_INT("invalid minjump; must be >= 1", __func__, 1);
332  if (minreversal < 1)
333  return ERROR_INT("invalid minreversal; must be >= 1", __func__, 1);
334 
335  if ((na = pixGetEdgeProfile(pixs, side, debugfile)) == NULL)
336  return ERROR_INT("edge profile not made", __func__, 1);
337  if ((n = numaGetCount(na)) < 2) {
338  numaDestroy(&na);
339  return 0;
340  }
341 
342  if (pjpl || pjspl) {
343  jumpsum = 0;
344  njumps = 0;
345  numaGetIValue(na, 0, &val);
346  for (i = 1; i < n; i++) {
347  numaGetIValue(na, i, &nval);
348  diff = L_ABS(nval - val);
349  if (diff >= minjump) {
350  njumps++;
351  jumpsum += diff;
352  }
353  val = nval;
354  }
355  if (pjpl)
356  *pjpl = (l_float32)njumps / (l_float32)(n - 1);
357  if (pjspl)
358  *pjspl = (l_float32)jumpsum / (l_float32)(n - 1);
359  }
360 
361  if (prpl) {
362  nae = numaFindExtrema(na, minreversal, NULL);
363  nreversal = numaGetCount(nae) - 1;
364  *prpl = (l_float32)nreversal / (l_float32)(n - 1);
365  numaDestroy(&nae);
366  }
367 
368  numaDestroy(&na);
369  return 0;
370 }
371 
372 
382 NUMA *
384  l_int32 side,
385  const char *debugfile)
386 {
387 l_int32 x, y, w, h, loc, index, ival;
388 l_uint32 val;
389 NUMA *na;
390 PIX *pixt;
391 PIXCMAP *cmap;
392 
393  if (!pixs || pixGetDepth(pixs) != 1)
394  return (NUMA *)ERROR_PTR("pixs undefined or not 1 bpp", __func__, NULL);
395  if (side != L_FROM_LEFT && side != L_FROM_RIGHT &&
396  side != L_FROM_TOP && side != L_FROM_BOT)
397  return (NUMA *)ERROR_PTR("invalid side", __func__, NULL);
398 
399  pixGetDimensions(pixs, &w, &h, NULL);
400  if (side == L_FROM_LEFT || side == L_FROM_RIGHT)
401  na = numaCreate(h);
402  else
403  na = numaCreate(w);
404  if (side == L_FROM_LEFT) {
405  pixGetLastOffPixelInRun(pixs, 0, 0, L_FROM_LEFT, &loc);
406  loc = (loc == w - 1) ? 0 : loc + 1; /* back to the left edge */
407  numaAddNumber(na, loc);
408  for (y = 1; y < h; y++) {
409  pixGetPixel(pixs, loc, y, &val);
410  if (val == 1) {
411  pixGetLastOnPixelInRun(pixs, loc, y, L_FROM_RIGHT, &loc);
412  } else {
413  pixGetLastOffPixelInRun(pixs, loc, y, L_FROM_LEFT, &loc);
414  loc = (loc == w - 1) ? 0 : loc + 1;
415  }
416  numaAddNumber(na, loc);
417  }
418  }
419  else if (side == L_FROM_RIGHT) {
420  pixGetLastOffPixelInRun(pixs, w - 1, 0, L_FROM_RIGHT, &loc);
421  loc = (loc == 0) ? w - 1 : loc - 1; /* back to the right edge */
422  numaAddNumber(na, loc);
423  for (y = 1; y < h; y++) {
424  pixGetPixel(pixs, loc, y, &val);
425  if (val == 1) {
426  pixGetLastOnPixelInRun(pixs, loc, y, L_FROM_LEFT, &loc);
427  } else {
428  pixGetLastOffPixelInRun(pixs, loc, y, L_FROM_RIGHT, &loc);
429  loc = (loc == 0) ? w - 1 : loc - 1;
430  }
431  numaAddNumber(na, loc);
432  }
433  }
434  else if (side == L_FROM_TOP) {
435  pixGetLastOffPixelInRun(pixs, 0, 0, L_FROM_TOP, &loc);
436  loc = (loc == h - 1) ? 0 : loc + 1; /* back to the top edge */
437  numaAddNumber(na, loc);
438  for (x = 1; x < w; x++) {
439  pixGetPixel(pixs, x, loc, &val);
440  if (val == 1) {
441  pixGetLastOnPixelInRun(pixs, x, loc, L_FROM_BOT, &loc);
442  } else {
443  pixGetLastOffPixelInRun(pixs, x, loc, L_FROM_TOP, &loc);
444  loc = (loc == h - 1) ? 0 : loc + 1;
445  }
446  numaAddNumber(na, loc);
447  }
448  }
449  else { /* side == L_FROM_BOT */
450  pixGetLastOffPixelInRun(pixs, 0, h - 1, L_FROM_BOT, &loc);
451  loc = (loc == 0) ? h - 1 : loc - 1; /* back to the bottom edge */
452  numaAddNumber(na, loc);
453  for (x = 1; x < w; x++) {
454  pixGetPixel(pixs, x, loc, &val);
455  if (val == 1) {
456  pixGetLastOnPixelInRun(pixs, x, loc, L_FROM_TOP, &loc);
457  } else {
458  pixGetLastOffPixelInRun(pixs, x, loc, L_FROM_BOT, &loc);
459  loc = (loc == 0) ? h - 1 : loc - 1;
460  }
461  numaAddNumber(na, loc);
462  }
463  }
464 
465  if (debugfile) {
466  pixt = pixConvertTo8(pixs, TRUE);
467  cmap = pixGetColormap(pixt);
468  pixcmapAddColor(cmap, 255, 0, 0);
469  index = pixcmapGetCount(cmap) - 1;
470  if (side == L_FROM_LEFT || side == L_FROM_RIGHT) {
471  for (y = 0; y < h; y++) {
472  numaGetIValue(na, y, &ival);
473  pixSetPixel(pixt, ival, y, index);
474  }
475  } else { /* L_FROM_TOP or L_FROM_BOT */
476  for (x = 0; x < w; x++) {
477  numaGetIValue(na, x, &ival);
478  pixSetPixel(pixt, x, ival, index);
479  }
480  }
481  pixWrite(debugfile, pixt, IFF_PNG);
482  pixDestroy(&pixt);
483  }
484 
485  return na;
486 }
487 
488 
489 /*
490  * \brief pixGetLastOffPixelInRun()
491  *
492  * \param[in] pixs 1 bpp
493  * \param[in] x, y starting location
494  * \param[in] direction L_FROM_LEFT, L_FROM_RIGHT, L_FROM_TOP, L_FROM_BOT
495  * \param[out] ploc location in scan direction coordinate
496  * of last OFF pixel found
497  * \return 0 if OK, 1 on error
498  *
499  * <pre>
500  * Notes:
501  * (1) Search starts from the pixel at (x, y), which is OFF.
502  * (2) It returns the location in the scan direction of the last
503  * pixel in the current run that is OFF.
504  * (3) The interface for these pixel run functions is cleaner when
505  * you ask for the last pixel in the current run, rather than the
506  * first pixel of opposite polarity that is found, because the
507  * current run may go to the edge of the image, in which case
508  * no pixel of opposite polarity is found.
509  * </pre>
510  */
511 l_ok
512 pixGetLastOffPixelInRun(PIX *pixs,
513  l_int32 x,
514  l_int32 y,
515  l_int32 direction,
516  l_int32 *ploc)
517 {
518 l_int32 loc, w, h;
519 l_uint32 val;
520 
521  if (!ploc)
522  return ERROR_INT("&loc not defined", __func__, 1);
523  *ploc = 0;
524  if (!pixs || pixGetDepth(pixs) != 1)
525  return ERROR_INT("pixs undefined or not 1 bpp", __func__, 1);
526  if (direction != L_FROM_LEFT && direction != L_FROM_RIGHT &&
527  direction != L_FROM_TOP && direction != L_FROM_BOT)
528  return ERROR_INT("invalid side", __func__, 1);
529 
530  pixGetDimensions(pixs, &w, &h, NULL);
531  if (direction == L_FROM_LEFT) {
532  for (loc = x; loc < w; loc++) {
533  pixGetPixel(pixs, loc, y, &val);
534  if (val == 1)
535  break;
536  }
537  *ploc = loc - 1;
538  } else if (direction == L_FROM_RIGHT) {
539  for (loc = x; loc >= 0; loc--) {
540  pixGetPixel(pixs, loc, y, &val);
541  if (val == 1)
542  break;
543  }
544  *ploc = loc + 1;
545  }
546  else if (direction == L_FROM_TOP) {
547  for (loc = y; loc < h; loc++) {
548  pixGetPixel(pixs, x, loc, &val);
549  if (val == 1)
550  break;
551  }
552  *ploc = loc - 1;
553  }
554  else if (direction == L_FROM_BOT) {
555  for (loc = y; loc >= 0; loc--) {
556  pixGetPixel(pixs, x, loc, &val);
557  if (val == 1)
558  break;
559  }
560  *ploc = loc + 1;
561  }
562  return 0;
563 }
564 
565 
566 /*
567  * \brief pixGetLastOnPixelInRun()
568  *
569  * \param[in] pixs 1 bpp
570  * \param[in] x, y starting location
571  * \param[in] direction L_FROM_LEFT, L_FROM_RIGHT, L_FROM_TOP, L_FROM_BOT
572  * \param[out] ploc location in scan direction coordinate
573  * of first ON pixel found
574  * \return 0 if OK, 1 on error
575  *
576  * <pre>
577  * Notes:
578  * (1) Search starts from the pixel at (x, y), which is ON.
579  * (2) It returns the location in the scan direction of the last
580  * pixel in the current run that is ON.
581  * </pre>
582  */
583 l_int32
584 pixGetLastOnPixelInRun(PIX *pixs,
585  l_int32 x,
586  l_int32 y,
587  l_int32 direction,
588  l_int32 *ploc)
589 {
590 l_int32 loc, w, h;
591 l_uint32 val;
592 
593  if (!ploc)
594  return ERROR_INT("&loc not defined", __func__, 1);
595  *ploc = 0;
596  if (!pixs || pixGetDepth(pixs) != 1)
597  return ERROR_INT("pixs undefined or not 1 bpp", __func__, 1);
598  if (direction != L_FROM_LEFT && direction != L_FROM_RIGHT &&
599  direction != L_FROM_TOP && direction != L_FROM_BOT)
600  return ERROR_INT("invalid side", __func__, 1);
601 
602  pixGetDimensions(pixs, &w, &h, NULL);
603  if (direction == L_FROM_LEFT) {
604  for (loc = x; loc < w; loc++) {
605  pixGetPixel(pixs, loc, y, &val);
606  if (val == 0)
607  break;
608  }
609  *ploc = loc - 1;
610  } else if (direction == L_FROM_RIGHT) {
611  for (loc = x; loc >= 0; loc--) {
612  pixGetPixel(pixs, loc, y, &val);
613  if (val == 0)
614  break;
615  }
616  *ploc = loc + 1;
617  }
618  else if (direction == L_FROM_TOP) {
619  for (loc = y; loc < h; loc++) {
620  pixGetPixel(pixs, x, loc, &val);
621  if (val == 0)
622  break;
623  }
624  *ploc = loc - 1;
625  }
626  else if (direction == L_FROM_BOT) {
627  for (loc = y; loc >= 0; loc--) {
628  pixGetPixel(pixs, x, loc, &val);
629  if (val == 0)
630  break;
631  }
632  *ploc = loc + 1;
633  }
634  return 0;
635 }
#define GET_DATA_BYTE(pdata, n)
Definition: arrayaccess.h:188
#define SET_DATA_BYTE(pdata, n, val)
Definition: arrayaccess.h:198
l_int32 pixcmapGetCount(const PIXCMAP *cmap)
pixcmapGetCount()
Definition: colormap.c:683
l_ok pixcmapAddColor(PIXCMAP *cmap, l_int32 rval, l_int32 gval, l_int32 bval)
pixcmapAddColor()
Definition: colormap.c:403
PIX * pixTwoSidedEdgeFilter(PIX *pixs, l_int32 orientflag)
pixTwoSidedEdgeFilter()
Definition: edge.c:200
PIX * pixSobelEdgeFilter(PIX *pixs, l_int32 orientflag)
pixSobelEdgeFilter()
Definition: edge.c:94
NUMA * pixGetEdgeProfile(PIX *pixs, l_int32 side, const char *debugfile)
pixGetEdgeProfile()
Definition: edge.c:383
l_ok pixMeasureEdgeSmoothness(PIX *pixs, l_int32 side, l_int32 minjump, l_int32 minreversal, l_float32 *pjpl, l_float32 *pjspl, l_float32 *prpl, const char *debugfile)
pixMeasureEdgeSmoothness()
Definition: edge.c:308
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:460
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:193
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:357
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:630
l_ok numaGetIValue(NUMA *na, l_int32 index, l_int32 *pival)
numaGetIValue()
Definition: numabasic.c:720
NUMA * numaFindExtrema(NUMA *nas, l_float32 delta, NUMA **pnav)
numaFindExtrema()
Definition: numafunc2.c:2483
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 * pixCreateTemplate(const PIX *pixs)
pixCreateTemplate()
Definition: pix1.c:380
l_ok pixSetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 val)
pixSetPixel()
Definition: pix2.c:263
l_ok pixGetPixel(PIX *pix, l_int32 x, l_int32 y, l_uint32 *pval)
pixGetPixel()
Definition: pix2.c:192
PIX * pixAddMirroredBorder(PIX *pixs, l_int32 left, l_int32 right, l_int32 top, l_int32 bot)
pixAddMirroredBorder()
Definition: pix2.c:2100
@ L_FROM_BOT
Definition: pix.h:830
@ L_FROM_LEFT
Definition: pix.h:827
@ L_FROM_RIGHT
Definition: pix.h:828
@ L_FROM_TOP
Definition: pix.h:829
@ L_ALL_EDGES
Definition: pix.h:798
@ L_VERTICAL_EDGES
Definition: pix.h:797
@ L_HORIZONTAL_EDGES
Definition: pix.h:796
PIX * pixConvertTo8(PIX *pixs, l_int32 cmapflag)
pixConvertTo8()
Definition: pixconv.c:3055