Leptonica  1.83.1
Image processing and image analysis suite
skew.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 
98 #ifdef HAVE_CONFIG_H
99 #include <config_auto.h>
100 #endif /* HAVE_CONFIG_H */
101 
102 #include <math.h>
103 #include "allheaders.h"
104 
105  /* Default sweep angle parameters for pixFindSkew() */
106 static const l_float32 DefaultSweepRange = 7.0; /* degrees */
107 static const l_float32 DefaultSweepDelta = 1.0; /* degrees */
108 
109  /* Default final angle difference parameter for binary
110  * search in pixFindSkew(). The expected accuracy is
111  * not better than the inverse image width in pixels,
112  * say, 1/2000 radians, or about 0.03 degrees. */
113 static const l_float32 DefaultMinbsDelta = 0.01; /* degrees */
114 
115  /* Default scale factors for pixFindSkew() */
116 static const l_int32 DefaultSweepReduction = 4; /* sweep part; 4 is good */
117 static const l_int32 DefaultBsReduction = 2; /* binary search part */
118 
119  /* Minimum angle for deskewing in pixDeskew() */
120 static const l_float32 MinDeskewAngle = 0.1; /* degree */
121 
122  /* Minimum allowed confidence (ratio) for deskewing in pixDeskew() */
123 static const l_float32 MinAllowedConfidence = 3.0;
124 
125  /* Minimum allowed maxscore to give nonzero confidence */
126 static const l_int32 MinValidMaxscore = 10000;
127 
128  /* Constant setting threshold for minimum allowed minscore
129  * to give nonzero confidence; multiply this constant by
130  * (height * width^2) */
131 static const l_float32 MinscoreThreshFactor = 0.000002;
132 
133  /* Default binarization threshold value */
134 static const l_int32 DefaultBinaryThreshold = 130;
135 
136 #ifndef NO_CONSOLE_IO
137 #define DEBUG_PRINT_SCORES 0
138 #define DEBUG_PRINT_SWEEP 0
139 #define DEBUG_PRINT_BINARY 0
140 #define DEBUG_PRINT_ORTH 0
141 #define DEBUG_THRESHOLD 0
142 #define DEBUG_PLOT_SCORES 0 /* requires the gnuplot executable */
143 #endif /* ~NO_CONSOLE_IO */
144 
145 
146 
147 /*-----------------------------------------------------------------------*
148  * Top-level deskew interfaces *
149  *-----------------------------------------------------------------------*/
165 PIX *
167  l_int32 redsearch)
168 {
169 PIX *pix1, *pix2, *pix3, *pix4;
170 
171  if (!pixs)
172  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
173  if (redsearch == 0)
174  redsearch = DefaultBsReduction;
175  else if (redsearch != 1 && redsearch != 2 && redsearch != 4)
176  return (PIX *)ERROR_PTR("redsearch not in {1,2,4}", __func__, NULL);
177 
178  pix1 = pixDeskew(pixs, redsearch);
179  pix2 = pixRotate90(pix1, 1);
180  pix3 = pixDeskew(pix2, redsearch);
181  pix4 = pixRotate90(pix3, -1);
182  pixDestroy(&pix1);
183  pixDestroy(&pix2);
184  pixDestroy(&pix3);
185  return pix4;
186 }
187 
188 
206 PIX *
208  l_int32 redsearch)
209 {
210  if (!pixs)
211  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
212  if (redsearch == 0)
213  redsearch = DefaultBsReduction;
214  else if (redsearch != 1 && redsearch != 2 && redsearch != 4)
215  return (PIX *)ERROR_PTR("redsearch not in {1,2,4}", __func__, NULL);
216 
217  return pixDeskewGeneral(pixs, 0, 0.0, 0.0, redsearch, 0, NULL, NULL);
218 }
219 
220 
240 PIX *
242  l_int32 redsearch,
243  l_float32 *pangle,
244  l_float32 *pconf)
245 {
246  if (!pixs)
247  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
248  if (redsearch == 0)
249  redsearch = DefaultBsReduction;
250  else if (redsearch != 1 && redsearch != 2 && redsearch != 4)
251  return (PIX *)ERROR_PTR("redsearch not in {1,2,4}", __func__, NULL);
252 
253  return pixDeskewGeneral(pixs, 0, 0.0, 0.0, redsearch, 0, pangle, pconf);
254 }
255 
256 
282 PIX *
284  l_int32 redsweep,
285  l_float32 sweeprange,
286  l_float32 sweepdelta,
287  l_int32 redsearch,
288  l_int32 thresh,
289  l_float32 *pangle,
290  l_float32 *pconf)
291 {
292 l_int32 ret, depth;
293 l_float32 angle, conf, deg2rad;
294 PIX *pixb, *pixd;
295 
296  if (pangle) *pangle = 0.0;
297  if (pconf) *pconf = 0.0;
298  if (!pixs)
299  return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
300  if (redsweep == 0)
301  redsweep = DefaultSweepReduction;
302  else if (redsweep != 1 && redsweep != 2 && redsweep != 4)
303  return (PIX *)ERROR_PTR("redsweep not in {1,2,4}", __func__, NULL);
304  if (sweeprange == 0.0)
305  sweeprange = DefaultSweepRange;
306  if (sweepdelta == 0.0)
307  sweepdelta = DefaultSweepDelta;
308  if (redsearch == 0)
309  redsearch = DefaultBsReduction;
310  else if (redsearch != 1 && redsearch != 2 && redsearch != 4)
311  return (PIX *)ERROR_PTR("redsearch not in {1,2,4}", __func__, NULL);
312  if (thresh == 0)
313  thresh = DefaultBinaryThreshold;
314 
315  deg2rad = 3.1415926535 / 180.;
316 
317  /* Binarize if necessary */
318  depth = pixGetDepth(pixs);
319  if (depth == 1)
320  pixb = pixClone(pixs);
321  else
322  pixb = pixConvertTo1(pixs, thresh);
323 
324  /* Use the 1 bpp image to find the skew */
325  ret = pixFindSkewSweepAndSearch(pixb, &angle, &conf, redsweep, redsearch,
326  sweeprange, sweepdelta,
327  DefaultMinbsDelta);
328  pixDestroy(&pixb);
329  if (pangle) *pangle = angle;
330  if (pconf) *pconf = conf;
331  if (ret)
332  return pixClone(pixs);
333 
334  if (L_ABS(angle) < MinDeskewAngle || conf < MinAllowedConfidence)
335  return pixClone(pixs);
336 
337  if ((pixd = pixRotate(pixs, deg2rad * angle, L_ROTATE_AREA_MAP,
338  L_BRING_IN_WHITE, 0, 0)) == NULL)
339  return pixClone(pixs);
340  else
341  return pixd;
342 }
343 
344 
345 /*-----------------------------------------------------------------------*
346  * Simple top-level angle-finding interface *
347  *-----------------------------------------------------------------------*/
365 l_ok
367  l_float32 *pangle,
368  l_float32 *pconf)
369 {
370  if (pangle) *pangle = 0.0;
371  if (pconf) *pconf = 0.0;
372  if (!pangle || !pconf)
373  return ERROR_INT("&angle and/or &conf not defined", __func__, 1);
374  if (!pixs)
375  return ERROR_INT("pixs not defined", __func__, 1);
376  if (pixGetDepth(pixs) != 1)
377  return ERROR_INT("pixs not 1 bpp", __func__, 1);
378 
379  return pixFindSkewSweepAndSearch(pixs, pangle, pconf,
380  DefaultSweepReduction,
381  DefaultBsReduction,
382  DefaultSweepRange,
383  DefaultSweepDelta,
384  DefaultMinbsDelta);
385 }
386 
387 
388 /*-----------------------------------------------------------------------*
389  * Basic angle-finding functions *
390  *-----------------------------------------------------------------------*/
407 l_ok
409  l_float32 *pangle,
410  l_int32 reduction,
411  l_float32 sweeprange,
412  l_float32 sweepdelta)
413 {
414 l_int32 ret, bzero, i, nangles;
415 l_float32 deg2rad, theta;
416 l_float32 sum, maxscore, maxangle;
417 NUMA *natheta, *nascore;
418 PIX *pix, *pixt;
419 
420  if (!pangle)
421  return ERROR_INT("&angle not defined", __func__, 1);
422  *pangle = 0.0;
423  if (!pixs)
424  return ERROR_INT("pixs not defined", __func__, 1);
425  if (pixGetDepth(pixs) != 1)
426  return ERROR_INT("pixs not 1 bpp", __func__, 1);
427  if (reduction != 1 && reduction != 2 && reduction != 4 && reduction != 8)
428  return ERROR_INT("reduction must be in {1,2,4,8}", __func__, 1);
429 
430  deg2rad = 3.1415926535 / 180.;
431  ret = 0;
432 
433  /* Generate reduced image, if requested */
434  if (reduction == 1)
435  pix = pixClone(pixs);
436  else if (reduction == 2)
437  pix = pixReduceRankBinaryCascade(pixs, 1, 0, 0, 0);
438  else if (reduction == 4)
439  pix = pixReduceRankBinaryCascade(pixs, 1, 1, 0, 0);
440  else /* reduction == 8 */
441  pix = pixReduceRankBinaryCascade(pixs, 1, 1, 2, 0);
442 
443  pixZero(pix, &bzero);
444  if (bzero) {
445  pixDestroy(&pix);
446  return 1;
447  }
448 
449  nangles = (l_int32)((2. * sweeprange) / sweepdelta + 1);
450  natheta = numaCreate(nangles);
451  nascore = numaCreate(nangles);
452  pixt = pixCreateTemplate(pix);
453 
454  if (!pix || !pixt) {
455  ret = ERROR_INT("pix and pixt not both made", __func__, 1);
456  goto cleanup;
457  }
458  if (!natheta || !nascore) {
459  ret = ERROR_INT("natheta and nascore not both made", __func__, 1);
460  goto cleanup;
461  }
462 
463  for (i = 0; i < nangles; i++) {
464  theta = -sweeprange + i * sweepdelta; /* degrees */
465 
466  /* Shear pix about the UL corner and put the result in pixt */
467  pixVShearCorner(pixt, pix, deg2rad * theta, L_BRING_IN_WHITE);
468 
469  /* Get score */
470  pixFindDifferentialSquareSum(pixt, &sum);
471 
472 #if DEBUG_PRINT_SCORES
473  L_INFO("sum(%7.2f) = %7.0f\n", __func__, theta, sum);
474 #endif /* DEBUG_PRINT_SCORES */
475 
476  /* Save the result in the output arrays */
477  numaAddNumber(nascore, sum);
478  numaAddNumber(natheta, theta);
479  }
480 
481  /* Find the location of the maximum (i.e., the skew angle)
482  * by fitting the largest data point and its two neighbors
483  * to a quadratic, using lagrangian interpolation. */
484  numaFitMax(nascore, &maxscore, natheta, &maxangle);
485  *pangle = maxangle;
486 
487 #if DEBUG_PRINT_SWEEP
488  L_INFO(" From sweep: angle = %7.3f, score = %7.3f\n", __func__,
489  maxangle, maxscore);
490 #endif /* DEBUG_PRINT_SWEEP */
491 
492 #if DEBUG_PLOT_SCORES
493  /* Plot the result -- the scores versus rotation angle --
494  * using gnuplot with GPLOT_LINES (lines connecting data points).
495  * The GPLOT data structure is first created, with the
496  * appropriate data incorporated from the two input NUMAs,
497  * and then the function gplotMakeOutput() uses gnuplot to
498  * generate the output plot. This can be either a .png file
499  * or a .ps file, depending on whether you use GPLOT_PNG
500  * or GPLOT_PS. */
501  {GPLOT *gplot;
502  gplot = gplotCreate("sweep_output", GPLOT_PNG,
503  "Sweep. Variance of difference of ON pixels vs. angle",
504  "angle (deg)", "score");
505  gplotAddPlot(gplot, natheta, nascore, GPLOT_LINES, "plot1");
506  gplotAddPlot(gplot, natheta, nascore, GPLOT_POINTS, "plot2");
507  gplotMakeOutput(gplot);
508  gplotDestroy(&gplot);
509  }
510 #endif /* DEBUG_PLOT_SCORES */
511 
512 cleanup:
513  pixDestroy(&pix);
514  pixDestroy(&pixt);
515  numaDestroy(&nascore);
516  numaDestroy(&natheta);
517  return ret;
518 }
519 
520 
549 l_ok
551  l_float32 *pangle,
552  l_float32 *pconf,
553  l_int32 redsweep,
554  l_int32 redsearch,
555  l_float32 sweeprange,
556  l_float32 sweepdelta,
557  l_float32 minbsdelta)
558 {
559  return pixFindSkewSweepAndSearchScore(pixs, pangle, pconf, NULL,
560  redsweep, redsearch, 0.0, sweeprange,
561  sweepdelta, minbsdelta);
562 }
563 
564 
603 l_ok
605  l_float32 *pangle,
606  l_float32 *pconf,
607  l_float32 *pendscore,
608  l_int32 redsweep,
609  l_int32 redsearch,
610  l_float32 sweepcenter,
611  l_float32 sweeprange,
612  l_float32 sweepdelta,
613  l_float32 minbsdelta)
614 {
615  return pixFindSkewSweepAndSearchScorePivot(pixs, pangle, pconf, pendscore,
616  redsweep, redsearch, 0.0,
617  sweeprange, sweepdelta,
618  minbsdelta,
620 }
621 
622 
652 l_ok
654  l_float32 *pangle,
655  l_float32 *pconf,
656  l_float32 *pendscore,
657  l_int32 redsweep,
658  l_int32 redsearch,
659  l_float32 sweepcenter,
660  l_float32 sweeprange,
661  l_float32 sweepdelta,
662  l_float32 minbsdelta,
663  l_int32 pivot)
664 {
665 l_int32 ret, bzero, i, nangles, n, ratio, maxindex, minloc;
666 l_int32 width, height;
667 l_float32 deg2rad, theta, delta;
668 l_float32 sum, maxscore, maxangle;
669 l_float32 centerangle, leftcenterangle, rightcenterangle;
670 l_float32 lefttemp, righttemp;
671 l_float32 bsearchscore[5];
672 l_float32 minscore, minthresh;
673 l_float32 rangeleft;
674 NUMA *natheta, *nascore;
675 PIX *pixsw, *pixsch, *pixt1, *pixt2;
676 
677  if (pendscore) *pendscore = 0.0;
678  if (pangle) *pangle = 0.0;
679  if (pconf) *pconf = 0.0;
680  if (!pangle || !pconf)
681  return ERROR_INT("&angle and/or &conf not defined", __func__, 1);
682  if (!pixs || pixGetDepth(pixs) != 1)
683  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
684  if (redsweep != 1 && redsweep != 2 && redsweep != 4 && redsweep != 8)
685  return ERROR_INT("redsweep must be in {1,2,4,8}", __func__, 1);
686  if (redsearch != 1 && redsearch != 2 && redsearch != 4 && redsearch != 8)
687  return ERROR_INT("redsearch must be in {1,2,4,8}", __func__, 1);
688  if (redsearch > redsweep)
689  return ERROR_INT("redsearch must not exceed redsweep", __func__, 1);
690  if (pivot != L_SHEAR_ABOUT_CORNER && pivot != L_SHEAR_ABOUT_CENTER)
691  return ERROR_INT("invalid pivot", __func__, 1);
692 
693  deg2rad = 3.1415926535 / 180.;
694  ret = 0;
695 
696  /* Generate reduced image for binary search, if requested */
697  if (redsearch == 1)
698  pixsch = pixClone(pixs);
699  else if (redsearch == 2)
700  pixsch = pixReduceRankBinaryCascade(pixs, 1, 0, 0, 0);
701  else if (redsearch == 4)
702  pixsch = pixReduceRankBinaryCascade(pixs, 1, 1, 0, 0);
703  else /* redsearch == 8 */
704  pixsch = pixReduceRankBinaryCascade(pixs, 1, 1, 2, 0);
705 
706  pixZero(pixsch, &bzero);
707  if (bzero) {
708  pixDestroy(&pixsch);
709  return 1;
710  }
711 
712  /* Generate reduced image for sweep, if requested */
713  ratio = redsweep / redsearch;
714  if (ratio == 1) {
715  pixsw = pixClone(pixsch);
716  } else { /* ratio > 1 */
717  if (ratio == 2)
718  pixsw = pixReduceRankBinaryCascade(pixsch, 1, 0, 0, 0);
719  else if (ratio == 4)
720  pixsw = pixReduceRankBinaryCascade(pixsch, 1, 2, 0, 0);
721  else /* ratio == 8 */
722  pixsw = pixReduceRankBinaryCascade(pixsch, 1, 2, 2, 0);
723  }
724 
725  pixt1 = pixCreateTemplate(pixsw);
726  if (ratio == 1)
727  pixt2 = pixClone(pixt1);
728  else
729  pixt2 = pixCreateTemplate(pixsch);
730 
731  nangles = (l_int32)((2. * sweeprange) / sweepdelta + 1);
732  natheta = numaCreate(nangles);
733  nascore = numaCreate(nangles);
734 
735  if (!pixsch || !pixsw) {
736  ret = ERROR_INT("pixsch and pixsw not both made", __func__, 1);
737  goto cleanup;
738  }
739  if (!pixt1 || !pixt2) {
740  ret = ERROR_INT("pixt1 and pixt2 not both made", __func__, 1);
741  goto cleanup;
742  }
743  if (!natheta || !nascore) {
744  ret = ERROR_INT("natheta and nascore not both made", __func__, 1);
745  goto cleanup;
746  }
747 
748  /* Do sweep */
749  rangeleft = sweepcenter - sweeprange;
750  for (i = 0; i < nangles; i++) {
751  theta = rangeleft + i * sweepdelta; /* degrees */
752 
753  /* Shear pix and put the result in pixt1 */
754  if (pivot == L_SHEAR_ABOUT_CORNER)
755  pixVShearCorner(pixt1, pixsw, deg2rad * theta, L_BRING_IN_WHITE);
756  else
757  pixVShearCenter(pixt1, pixsw, deg2rad * theta, L_BRING_IN_WHITE);
758 
759  /* Get score */
760  pixFindDifferentialSquareSum(pixt1, &sum);
761 
762 #if DEBUG_PRINT_SCORES
763  L_INFO("sum(%7.2f) = %7.0f\n", __func__, theta, sum);
764 #endif /* DEBUG_PRINT_SCORES */
765 
766  /* Save the result in the output arrays */
767  numaAddNumber(nascore, sum);
768  numaAddNumber(natheta, theta);
769  }
770 
771  /* Find the largest of the set (maxscore at maxangle) */
772  numaGetMax(nascore, &maxscore, &maxindex);
773  numaGetFValue(natheta, maxindex, &maxangle);
774 
775 #if DEBUG_PRINT_SWEEP
776  L_INFO(" From sweep: angle = %7.3f, score = %7.3f\n", __func__,
777  maxangle, maxscore);
778 #endif /* DEBUG_PRINT_SWEEP */
779 
780 #if DEBUG_PLOT_SCORES
781  /* Plot the sweep result -- the scores versus rotation angle --
782  * using gnuplot with GPLOT_LINES (lines connecting data points). */
783  {GPLOT *gplot;
784  gplot = gplotCreate("sweep_output", GPLOT_PNG,
785  "Sweep. Variance of difference of ON pixels vs. angle",
786  "angle (deg)", "score");
787  gplotAddPlot(gplot, natheta, nascore, GPLOT_LINES, "plot1");
788  gplotAddPlot(gplot, natheta, nascore, GPLOT_POINTS, "plot2");
789  gplotMakeOutput(gplot);
790  gplotDestroy(&gplot);
791  }
792 #endif /* DEBUG_PLOT_SCORES */
793 
794  /* Check if the max is at the end of the sweep. */
795  n = numaGetCount(natheta);
796  if (maxindex == 0 || maxindex == n - 1) {
797  L_WARNING("max found at sweep edge\n", __func__);
798  goto cleanup;
799  }
800 
801  /* Empty the numas for re-use */
802  numaEmpty(nascore);
803  numaEmpty(natheta);
804 
805  /* Do binary search to find skew angle.
806  * First, set up initial three points. */
807  centerangle = maxangle;
808  if (pivot == L_SHEAR_ABOUT_CORNER) {
809  pixVShearCorner(pixt2, pixsch, deg2rad * centerangle, L_BRING_IN_WHITE);
810  pixFindDifferentialSquareSum(pixt2, &bsearchscore[2]);
811  pixVShearCorner(pixt2, pixsch, deg2rad * (centerangle - sweepdelta),
813  pixFindDifferentialSquareSum(pixt2, &bsearchscore[0]);
814  pixVShearCorner(pixt2, pixsch, deg2rad * (centerangle + sweepdelta),
816  pixFindDifferentialSquareSum(pixt2, &bsearchscore[4]);
817  } else {
818  pixVShearCenter(pixt2, pixsch, deg2rad * centerangle, L_BRING_IN_WHITE);
819  pixFindDifferentialSquareSum(pixt2, &bsearchscore[2]);
820  pixVShearCenter(pixt2, pixsch, deg2rad * (centerangle - sweepdelta),
822  pixFindDifferentialSquareSum(pixt2, &bsearchscore[0]);
823  pixVShearCenter(pixt2, pixsch, deg2rad * (centerangle + sweepdelta),
825  pixFindDifferentialSquareSum(pixt2, &bsearchscore[4]);
826  }
827 
828  numaAddNumber(nascore, bsearchscore[2]);
829  numaAddNumber(natheta, centerangle);
830  numaAddNumber(nascore, bsearchscore[0]);
831  numaAddNumber(natheta, centerangle - sweepdelta);
832  numaAddNumber(nascore, bsearchscore[4]);
833  numaAddNumber(natheta, centerangle + sweepdelta);
834 
835  /* Start the search */
836  delta = 0.5 * sweepdelta;
837  while (delta >= minbsdelta)
838  {
839  /* Get the left intermediate score */
840  leftcenterangle = centerangle - delta;
841  if (pivot == L_SHEAR_ABOUT_CORNER)
842  pixVShearCorner(pixt2, pixsch, deg2rad * leftcenterangle,
844  else
845  pixVShearCenter(pixt2, pixsch, deg2rad * leftcenterangle,
847  pixFindDifferentialSquareSum(pixt2, &bsearchscore[1]);
848  numaAddNumber(nascore, bsearchscore[1]);
849  numaAddNumber(natheta, leftcenterangle);
850 
851  /* Get the right intermediate score */
852  rightcenterangle = centerangle + delta;
853  if (pivot == L_SHEAR_ABOUT_CORNER)
854  pixVShearCorner(pixt2, pixsch, deg2rad * rightcenterangle,
856  else
857  pixVShearCenter(pixt2, pixsch, deg2rad * rightcenterangle,
859  pixFindDifferentialSquareSum(pixt2, &bsearchscore[3]);
860  numaAddNumber(nascore, bsearchscore[3]);
861  numaAddNumber(natheta, rightcenterangle);
862 
863  /* Find the maximum of the five scores and its location.
864  * Note that the maximum must be in the center
865  * three values, not in the end two. */
866  maxscore = bsearchscore[1];
867  maxindex = 1;
868  for (i = 2; i < 4; i++) {
869  if (bsearchscore[i] > maxscore) {
870  maxscore = bsearchscore[i];
871  maxindex = i;
872  }
873  }
874 
875  /* Set up score array to interpolate for the next iteration */
876  lefttemp = bsearchscore[maxindex - 1];
877  righttemp = bsearchscore[maxindex + 1];
878  bsearchscore[2] = maxscore;
879  bsearchscore[0] = lefttemp;
880  bsearchscore[4] = righttemp;
881 
882  /* Get new center angle and delta for next iteration */
883  centerangle = centerangle + delta * (maxindex - 2);
884  delta = 0.5 * delta;
885  }
886  *pangle = centerangle;
887 
888 #if DEBUG_PRINT_SCORES
889  L_INFO(" Binary search score = %7.3f\n", __func__, bsearchscore[2]);
890 #endif /* DEBUG_PRINT_SCORES */
891 
892  if (pendscore) /* save if requested */
893  *pendscore = bsearchscore[2];
894 
895  /* Return the ratio of Max score over Min score
896  * as a confidence value. Don't trust if the Min score
897  * is too small, which can happen if the image is all black
898  * with only a few white pixels interspersed. In that case,
899  * we get a contribution from the top and bottom edges when
900  * vertically sheared, but this contribution becomes zero when
901  * the shear angle is zero. For zero shear angle, the only
902  * contribution will be from the white pixels. We expect that
903  * the signal goes as the product of the (height * width^2),
904  * so we compute a (hopefully) normalized minimum threshold as
905  * a function of these dimensions. */
906  numaGetMin(nascore, &minscore, &minloc);
907  width = pixGetWidth(pixsch);
908  height = pixGetHeight(pixsch);
909  minthresh = MinscoreThreshFactor * width * width * height;
910 
911 #if DEBUG_THRESHOLD
912  L_INFO(" minthresh = %10.2f, minscore = %10.2f\n", __func__,
913  minthresh, minscore);
914  L_INFO(" maxscore = %10.2f\n", __func__, maxscore);
915 #endif /* DEBUG_THRESHOLD */
916 
917  if (minscore > minthresh)
918  *pconf = maxscore / minscore;
919  else
920  *pconf = 0.0;
921 
922  /* Don't trust it if too close to the edge of the sweep
923  * range or if maxscore is small */
924  if ((centerangle > rangeleft + 2 * sweeprange - sweepdelta) ||
925  (centerangle < rangeleft + sweepdelta) ||
926  (maxscore < MinValidMaxscore))
927  *pconf = 0.0;
928 
929 #if DEBUG_PRINT_BINARY
930  lept_stderr("Binary search: angle = %7.3f, score ratio = %6.2f\n",
931  *pangle, *pconf);
932  lept_stderr(" max score = %8.0f\n", maxscore);
933 #endif /* DEBUG_PRINT_BINARY */
934 
935 #if DEBUG_PLOT_SCORES
936  /* Plot the result -- the scores versus rotation angle --
937  * using gnuplot with GPLOT_POINTS. Because the data
938  * points are not ordered by theta (increasing or decreasing),
939  * using GPLOT_LINES would be confusing! */
940  {GPLOT *gplot;
941  gplot = gplotCreate("search_output", GPLOT_PNG,
942  "Binary search. Variance of difference of ON pixels vs. angle",
943  "angle (deg)", "score");
944  gplotAddPlot(gplot, natheta, nascore, GPLOT_POINTS, "plot1");
945  gplotMakeOutput(gplot);
946  gplotDestroy(&gplot);
947  }
948 #endif /* DEBUG_PLOT_SCORES */
949 
950 cleanup:
951  pixDestroy(&pixsw);
952  pixDestroy(&pixsch);
953  pixDestroy(&pixt1);
954  pixDestroy(&pixt2);
955  numaDestroy(&nascore);
956  numaDestroy(&natheta);
957  return ret;
958 }
959 
960 
961 /*---------------------------------------------------------------------*
962  * Search over arbitrary range of angles in orthogonal directions *
963  *---------------------------------------------------------------------*/
964 /*
965  * \brief pixFindSkewOrthogonalRange()
966  *
967  * \param[in] pixs 1 bpp
968  * \param[out] pangle angle required to deskew; in degrees cw
969  * \param[out] pconf confidence given by ratio of max/min score
970  * \param[in] redsweep sweep reduction factor = 1, 2, 4 or 8
971  * \param[in] redsearch binary search reduction factor = 1, 2, 4 or 8;
972  * and must not exceed redsweep
973  * \param[in] sweeprange half the full range in each orthogonal
974  * direction, taken about 0, in degrees
975  * \param[in] sweepdelta angle increment of sweep; in degrees
976  * \param[in] minbsdelta min binary search increment angle; in degrees
977  * \param[in] confprior amount by which confidence of 90 degree rotated
978  * result is reduced when comparing with unrotated
979  * confidence value
980  * \return 0 if OK, 1 on error or if angle measurement not valid
981  *
982  * <pre>
983  * Notes:
984  * (1) This searches for the skew angle, first in the range
985  * [-sweeprange, sweeprange], and then in
986  * [90 - sweeprange, 90 + sweeprange], with angles measured
987  * clockwise. For exploring the full range of possibilities,
988  * suggest using sweeprange = 47.0 degrees, giving some overlap
989  * at 45 and 135 degrees. From these results, and discounting
990  * the the second confidence by %confprior, it selects the
991  * angle for maximal differential variance. If the angle
992  * is larger than pi/4, the angle found after 90 degree rotation
993  * is selected.
994  * (2) The larger the confidence value, the greater the probability
995  * that the proper alignment is given by the angle that maximizes
996  * variance. It should be compared to a threshold, which depends
997  * on the application. Values between 3.0 and 6.0 are common.
998  * (3) Allowing for both portrait and landscape searches is more
999  * difficult, because if the signal from the text lines is weak,
1000  * a signal from vertical rules can be larger!
1001  * The most difficult documents to deskew have some or all of:
1002  * (a) Multiple columns, not aligned
1003  * (b) Black lines along the vertical edges
1004  * (c) Text from two pages, and at different angles
1005  * Rule of thumb for resolution:
1006  * (a) If the margins are clean, you can work at 75 ppi,
1007  * although 100 ppi is safer.
1008  * (b) If there are vertical lines in the margins, do not
1009  * work below 150 ppi. The signal from the text lines must
1010  * exceed that from the margin lines.
1011  * (4) Choosing the %confprior parameter depends on knowing something
1012  * about the source of image. However, we're not using
1013  * real probabilities here, so its use is qualitative.
1014  * If landscape and portrait are equally likely, use
1015  * %confprior = 0.0. If the likelihood of portrait (non-rotated)
1016  * is 100 times higher than that of landscape, we want to reduce
1017  * the chance that we rotate to landscape in a situation where
1018  * the landscape signal is accidentally larger than the
1019  * portrait signal. To do this use a positive value of
1020  * %confprior; say 1.5.
1021  * </pre>
1022  */
1023 l_int32
1024 pixFindSkewOrthogonalRange(PIX *pixs,
1025  l_float32 *pangle,
1026  l_float32 *pconf,
1027  l_int32 redsweep,
1028  l_int32 redsearch,
1029  l_float32 sweeprange,
1030  l_float32 sweepdelta,
1031  l_float32 minbsdelta,
1032  l_float32 confprior)
1033 {
1034 l_float32 angle1, conf1, score1, angle2, conf2, score2;
1035 PIX *pixr;
1036 
1037  if (pangle) *pangle = 0.0;
1038  if (pconf) *pconf = 0.0;
1039  if (!pangle || !pconf)
1040  return ERROR_INT("&angle and/or &conf not defined", __func__, 1);
1041  if (!pixs || pixGetDepth(pixs) != 1)
1042  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
1043 
1044  pixFindSkewSweepAndSearchScorePivot(pixs, &angle1, &conf1, &score1,
1045  redsweep, redsearch, 0.0,
1046  sweeprange, sweepdelta, minbsdelta,
1048  pixr = pixRotateOrth(pixs, 1);
1049  pixFindSkewSweepAndSearchScorePivot(pixr, &angle2, &conf2, &score2,
1050  redsweep, redsearch, 0.0,
1051  sweeprange, sweepdelta, minbsdelta,
1053  pixDestroy(&pixr);
1054 
1055  if (conf1 > conf2 - confprior) {
1056  *pangle = angle1;
1057  *pconf = conf1;
1058  } else {
1059  *pangle = -90.0 + angle2;
1060  *pconf = conf2;
1061  }
1062 
1063 #if DEBUG_PRINT_ORTH
1064  lept_stderr(" About 0: angle1 = %7.3f, conf1 = %7.3f, score1 = %f\n",
1065  angle1, conf1, score1);
1066  lept_stderr(" About 90: angle2 = %7.3f, conf2 = %7.3f, score2 = %f\n",
1067  angle2, conf2, score2);
1068  lept_stderr(" Final: angle = %7.3f, conf = %7.3f\n", *pangle, *pconf);
1069 #endif /* DEBUG_PRINT_ORTH */
1070 
1071  return 0;
1072 }
1073 
1074 
1075 
1076 /*----------------------------------------------------------------*
1077  * Differential square sum function *
1078  *----------------------------------------------------------------*/
1094 l_ok
1096  l_float32 *psum)
1097 {
1098 l_int32 i, n;
1099 l_int32 w, h, skiph, skip, nskip;
1100 l_float32 val1, val2, diff, sum;
1101 NUMA *na;
1102 
1103  if (!psum)
1104  return ERROR_INT("&sum not defined", __func__, 1);
1105  *psum = 0.0;
1106  if (!pixs)
1107  return ERROR_INT("pixs not defined", __func__, 1);
1108 
1109  /* Generate a number array consisting of the sum
1110  * of pixels in each row of pixs */
1111  if ((na = pixCountPixelsByRow(pixs, NULL)) == NULL)
1112  return ERROR_INT("na not made", __func__, 1);
1113 
1114  /* Compute the number of rows at top and bottom to omit.
1115  * We omit these to avoid getting a spurious signal from
1116  * the top and bottom of a (nearly) all black image. */
1117  w = pixGetWidth(pixs);
1118  h = pixGetHeight(pixs);
1119  skiph = (l_int32)(0.05 * w); /* skip for max shear of 0.025 radians */
1120  skip = L_MIN(h / 10, skiph); /* don't remove more than 10% of image */
1121  nskip = L_MAX(skip / 2, 1); /* at top & bot; skip at least one line */
1122 
1123  /* Sum the squares of differential row sums, on the
1124  * allowed rows. Note that nskip must be >= 1. */
1125  n = numaGetCount(na);
1126  sum = 0.0;
1127  for (i = nskip; i < n - nskip; i++) {
1128  numaGetFValue(na, i - 1, &val1);
1129  numaGetFValue(na, i, &val2);
1130  diff = val2 - val1;
1131  sum += diff * diff;
1132  }
1133  numaDestroy(&na);
1134  *psum = sum;
1135  return 0;
1136 }
1137 
1138 
1139 /*----------------------------------------------------------------*
1140  * Normalized square sum *
1141  *----------------------------------------------------------------*/
1165 l_ok
1167  l_float32 *phratio,
1168  l_float32 *pvratio,
1169  l_float32 *pfract)
1170 {
1171 l_int32 i, w, h, empty;
1172 l_float32 sum, sumsq, uniform, val;
1173 NUMA *na;
1174 PIX *pixt;
1175 
1176  if (phratio) *phratio = 0.0;
1177  if (pvratio) *pvratio = 0.0;
1178  if (pfract) *pfract = 0.0;
1179  if (!phratio && !pvratio)
1180  return ERROR_INT("nothing to do", __func__, 1);
1181  if (!pixs || pixGetDepth(pixs) != 1)
1182  return ERROR_INT("pixs not defined or not 1 bpp", __func__, 1);
1183  pixGetDimensions(pixs, &w, &h, NULL);
1184 
1185  empty = 0;
1186  if (phratio) {
1187  na = pixCountPixelsByRow(pixs, NULL);
1188  numaGetSum(na, &sum); /* fg pixels */
1189  if (pfract) *pfract = sum / (l_float32)(w * h);
1190  if (sum != 0.0) {
1191  uniform = sum * sum / h; /* h*(sum / h)^2 */
1192  sumsq = 0.0;
1193  for (i = 0; i < h; i++) {
1194  numaGetFValue(na, i, &val);
1195  sumsq += val * val;
1196  }
1197  *phratio = sumsq / uniform;
1198  } else {
1199  empty = 1;
1200  }
1201  numaDestroy(&na);
1202  }
1203 
1204  if (pvratio) {
1205  if (empty == 1) return 1;
1206  pixt = pixRotateOrth(pixs, 1);
1207  na = pixCountPixelsByRow(pixt, NULL);
1208  numaGetSum(na, &sum);
1209  if (pfract) *pfract = sum / (l_float32)(w * h);
1210  if (sum != 0.0) {
1211  uniform = sum * sum / w;
1212  sumsq = 0.0;
1213  for (i = 0; i < w; i++) {
1214  numaGetFValue(na, i, &val);
1215  sumsq += val * val;
1216  }
1217  *pvratio = sumsq / uniform;
1218  } else {
1219  empty = 1;
1220  }
1221  pixDestroy(&pixt);
1222  numaDestroy(&na);
1223  }
1224 
1225  return empty;
1226 }
PIX * pixReduceRankBinaryCascade(PIX *pixs, l_int32 level1, l_int32 level2, l_int32 level3, l_int32 level4)
pixReduceRankBinaryCascade()
Definition: binreduce.c:150
l_ok gplotAddPlot(GPLOT *gplot, NUMA *nax, NUMA *nay, l_int32 plotstyle, const char *plotlabel)
gplotAddPlot()
Definition: gplot.c:316
l_ok gplotMakeOutput(GPLOT *gplot)
gplotMakeOutput()
Definition: gplot.c:456
GPLOT * gplotCreate(const char *rootname, l_int32 outformat, const char *title, const char *xlabel, const char *ylabel)
gplotCreate()
Definition: gplot.c:187
void gplotDestroy(GPLOT **pgplot)
gplotDestroy()
Definition: gplot.c:253
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:460
l_ok numaGetFValue(NUMA *na, l_int32 index, l_float32 *pval)
numaGetFValue()
Definition: numabasic.c:687
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:193
void numaDestroy(NUMA **pna)
numaDestroy()
Definition: numabasic.c:357
l_ok numaEmpty(NUMA *na)
numaEmpty()
Definition: numabasic.c:438
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:630
l_ok numaGetMin(NUMA *na, l_float32 *pminval, l_int32 *piminloc)
numaGetMin()
Definition: numafunc1.c:444
l_ok numaGetMax(NUMA *na, l_float32 *pmaxval, l_int32 *pimaxloc)
numaGetMax()
Definition: numafunc1.c:485
l_ok numaFitMax(NUMA *na, l_float32 *pmaxval, NUMA *naloc, l_float32 *pmaxloc)
numaFitMax()
Definition: numafunc1.c:2093
l_ok numaGetSum(NUMA *na, l_float32 *psum)
numaGetSum()
Definition: numafunc1.c:525
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
PIX * pixClone(PIX *pixs)
pixClone()
Definition: pix1.c:582
l_ok pixZero(PIX *pix, l_int32 *pempty)
pixZero()
Definition: pix3.c:1777
NUMA * pixCountPixelsByRow(PIX *pix, l_int32 *tab8)
pixCountPixelsByRow()
Definition: pix3.c:2096
@ L_BRING_IN_WHITE
Definition: pix.h:662
@ L_ROTATE_AREA_MAP
Definition: pix.h:655
@ L_SHEAR_ABOUT_CORNER
Definition: pix.h:668
@ L_SHEAR_ABOUT_CENTER
Definition: pix.h:669
PIX * pixConvertTo1(PIX *pixs, l_int32 threshold)
pixConvertTo1()
Definition: pixconv.c:2952
PIX * pixRotate(PIX *pixs, l_float32 angle, l_int32 type, l_int32 incolor, l_int32 width, l_int32 height)
pixRotate()
Definition: rotate.c:101
PIX * pixRotate90(PIX *pixs, l_int32 direction)
pixRotate90()
Definition: rotateorth.c:162
PIX * pixRotateOrth(PIX *pixs, l_int32 quads)
pixRotateOrth()
Definition: rotateorth.c:75
PIX * pixVShearCenter(PIX *pixd, PIX *pixs, l_float32 radang, l_int32 incolor)
pixVShearCenter()
Definition: shear.c:423
PIX * pixVShearCorner(PIX *pixd, PIX *pixs, l_float32 radang, l_int32 incolor)
pixVShearCorner()
Definition: shear.c:365
PIX * pixDeskewBoth(PIX *pixs, l_int32 redsearch)
pixDeskewBoth()
Definition: skew.c:166
l_ok pixFindSkewSweepAndSearchScore(PIX *pixs, l_float32 *pangle, l_float32 *pconf, l_float32 *pendscore, l_int32 redsweep, l_int32 redsearch, l_float32 sweepcenter, l_float32 sweeprange, l_float32 sweepdelta, l_float32 minbsdelta)
pixFindSkewSweepAndSearchScore()
Definition: skew.c:604
l_ok pixFindSkewSweep(PIX *pixs, l_float32 *pangle, l_int32 reduction, l_float32 sweeprange, l_float32 sweepdelta)
pixFindSkewSweep()
Definition: skew.c:408
l_ok pixFindNormalizedSquareSum(PIX *pixs, l_float32 *phratio, l_float32 *pvratio, l_float32 *pfract)
pixFindNormalizedSquareSum()
Definition: skew.c:1166
l_ok pixFindSkewSweepAndSearchScorePivot(PIX *pixs, l_float32 *pangle, l_float32 *pconf, l_float32 *pendscore, l_int32 redsweep, l_int32 redsearch, l_float32 sweepcenter, l_float32 sweeprange, l_float32 sweepdelta, l_float32 minbsdelta, l_int32 pivot)
pixFindSkewSweepAndSearchScorePivot()
Definition: skew.c:653
PIX * pixDeskew(PIX *pixs, l_int32 redsearch)
pixDeskew()
Definition: skew.c:207
PIX * pixFindSkewAndDeskew(PIX *pixs, l_int32 redsearch, l_float32 *pangle, l_float32 *pconf)
pixFindSkewAndDeskew()
Definition: skew.c:241
l_ok pixFindSkew(PIX *pixs, l_float32 *pangle, l_float32 *pconf)
pixFindSkew()
Definition: skew.c:366
l_ok pixFindDifferentialSquareSum(PIX *pixs, l_float32 *psum)
pixFindDifferentialSquareSum()
Definition: skew.c:1095
l_ok pixFindSkewSweepAndSearch(PIX *pixs, l_float32 *pangle, l_float32 *pconf, l_int32 redsweep, l_int32 redsearch, l_float32 sweeprange, l_float32 sweepdelta, l_float32 minbsdelta)
pixFindSkewSweepAndSearch()
Definition: skew.c:550
PIX * pixDeskewGeneral(PIX *pixs, l_int32 redsweep, l_float32 sweeprange, l_float32 sweepdelta, l_int32 redsearch, l_int32 thresh, l_float32 *pangle, l_float32 *pconf)
pixDeskewGeneral()
Definition: skew.c:283
Definition: gplot.h:77
void lept_stderr(const char *fmt,...)
lept_stderr()
Definition: utils1.c:306