Leptonica  1.82.0
Image processing and image analysis suite
skew.c File Reference
#include <math.h>
#include "allheaders.h"

Go to the source code of this file.

Macros

#define DEBUG_PRINT_SCORES   0
 
#define DEBUG_PRINT_SWEEP   0
 
#define DEBUG_PRINT_BINARY   0
 
#define DEBUG_PRINT_ORTH   0
 
#define DEBUG_THRESHOLD   0
 
#define DEBUG_PLOT_SCORES   0 /* requires the gnuplot executable */
 

Functions

PIXpixDeskewBoth (PIX *pixs, l_int32 redsearch)
 
PIXpixDeskew (PIX *pixs, l_int32 redsearch)
 
PIXpixFindSkewAndDeskew (PIX *pixs, l_int32 redsearch, l_float32 *pangle, l_float32 *pconf)
 
PIXpixDeskewGeneral (PIX *pixs, l_int32 redsweep, l_float32 sweeprange, l_float32 sweepdelta, l_int32 redsearch, l_int32 thresh, l_float32 *pangle, l_float32 *pconf)
 
l_ok pixFindSkew (PIX *pixs, l_float32 *pangle, l_float32 *pconf)
 
l_ok pixFindSkewSweep (PIX *pixs, l_float32 *pangle, l_int32 reduction, l_float32 sweeprange, l_float32 sweepdelta)
 
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)
 
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)
 
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)
 
l_int32 pixFindSkewOrthogonalRange (PIX *pixs, l_float32 *pangle, l_float32 *pconf, l_int32 redsweep, l_int32 redsearch, l_float32 sweeprange, l_float32 sweepdelta, l_float32 minbsdelta, l_float32 confprior)
 
l_ok pixFindDifferentialSquareSum (PIX *pixs, l_float32 *psum)
 
l_ok pixFindNormalizedSquareSum (PIX *pixs, l_float32 *phratio, l_float32 *pvratio, l_float32 *pfract)
 

Variables

static const l_float32 DefaultSweepRange = 7.0
 
static const l_float32 DefaultSweepDelta = 1.0
 
static const l_float32 DefaultMinbsDelta = 0.01
 
static const l_int32 DefaultSweepReduction = 4
 
static const l_int32 DefaultBsReduction = 2
 
static const l_float32 MinDeskewAngle = 0.1
 
static const l_float32 MinAllowedConfidence = 3.0
 
static const l_int32 MinValidMaxscore = 10000
 
static const l_float32 MinscoreThreshFactor = 0.000002
 
static const l_int32 DefaultBinaryThreshold = 130
 

Detailed Description

     Top-level deskew interfaces
         PIX       *pixDeskewBoth()
         PIX       *pixDeskew()
         PIX       *pixFindSkewAndDeskew()
         PIX       *pixDeskewGeneral()
     Top-level angle-finding interface
         l_int32    pixFindSkew()
     Basic angle-finding functions
         l_int32    pixFindSkewSweep()
         l_int32    pixFindSkewSweepAndSearch()
         l_int32    pixFindSkewSweepAndSearchScore()
         l_int32    pixFindSkewSweepAndSearchScorePivot()
     Search over arbitrary range of angles in orthogonal directions
         l_int32    pixFindSkewOrthogonalRange()
     Differential square sum function for scoring
         l_int32    pixFindDifferentialSquareSum()
     Measures of variance of row sums
         l_int32    pixFindNormalizedSquareSum()
     ==============================================================
     Page skew detection
     Skew is determined by pixel profiles, which are computed
     as pixel sums along the raster line for each line in the
     image.  By vertically shearing the image by a given angle,
     the sums can be computed quickly along the raster lines
     rather than along lines at that angle.  The score is
     computed from these line sums by taking the square of
     the DIFFERENCE between adjacent line sums, summed over
     all lines.  The skew angle is then found as the angle
     that maximizes the score.  The actual computation for
     any sheared image is done in the function
     pixFindDifferentialSquareSum().
     The search for the angle that maximizes this score is
     most efficiently performed by first sweeping coarsely
     over angles, using a significantly reduced image (say, 4x
     reduction), to find the approximate maximum within a half
     degree or so, and then doing an interval-halving binary
     search at higher resolution to get the skew angle to
     within 1/20 degree or better.
     The differential signal is used (rather than just using
     that variance of line sums) because it rejects the
     background noise due to total number of black pixels,
     and has maximum contributions from the baselines and
     x-height lines of text when the textlines are aligned
     with the raster lines.  It also works well in multicolumn
     pages where the textlines do not line up across columns.
     The method is fast, accurate to within an angle (in radians)
     of approximately the inverse width in pixels of the image,
     and will work on a surprisingly small amount of text data
     (just a couple of text lines).  Consequently, it can
     also be used to find local skew if the skew were to vary
     significantly over the page.  Local skew determination
     is not very important except for locating lines of
     handwritten text that may be mixed with printed text.

Definition in file skew.c.

Function Documentation

◆ pixDeskew()

PIX* pixDeskew ( PIX pixs,
l_int32  redsearch 
)

pixDeskew()

Parameters
[in]pixsany depth
[in]redsearchfor binary search: reduction factor = 1, 2 or 4; use 0 for default
Returns
pixd deskewed pix, or NULL on error
Notes:
     (1) This binarizes if necessary and finds the skew angle.  If the
         angle is large enough and there is sufficient confidence,
         it returns a deskewed image; otherwise, it returns a clone.
     (2) Typical values at 300 ppi for redsearch are 2 and 4.
         At 75 ppi, one should use redsearch = 1.

Definition at line 210 of file skew.c.

◆ pixDeskewBoth()

PIX* pixDeskewBoth ( PIX pixs,
l_int32  redsearch 
)

pixDeskewBoth()

Parameters
[in]pixsany depth
[in]redsearchfor binary search: reduction factor = 1, 2 or 4; use 0 for default
Returns
pixd deskewed pix, or NULL on error
Notes:
     (1) This binarizes if necessary and does both horizontal
         and vertical deskewing, using the default parameters in
         the underlying pixDeskew().  See usage there.
     (2) This may return a clone.

Definition at line 167 of file skew.c.

Referenced by pixDecideIfTable().

◆ pixDeskewGeneral()

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()

Parameters
[in]pixsany depth
[in]redsweepfor linear search: reduction factor = 1, 2 or 4; use 0 for default
[in]sweeprangein degrees in each direction from 0; use 0.0 for default
[in]sweepdeltain degrees; use 0.0 for default
[in]redsearchfor binary search: reduction factor = 1, 2 or 4; use 0 for default;
[in]threshfor binarizing the image; use 0 for default
[out]pangle[optional] angle required to deskew, in degrees; use NULL to skip
[out]pconf[optional] conf value is ratio of max/min scores; use NULL to skip
Returns
pixd deskewed pix, or NULL on error
Notes:
     (1) This binarizes if necessary and finds the skew angle.  If the
         angle is large enough and there is sufficient confidence,
         it returns a deskewed image; otherwise, it returns a clone.

Definition at line 290 of file skew.c.

◆ pixFindDifferentialSquareSum()

l_ok pixFindDifferentialSquareSum ( PIX pixs,
l_float32 *  psum 
)

pixFindDifferentialSquareSum()

Parameters
[in]pixs
[out]psumresult
Returns
0 if OK, 1 on error
Notes:
     (1) At the top and bottom, we skip:
          ~ at least one scanline
          ~ not more than 10% of the image height
          ~ not more than 5% of the image width

Definition at line 1112 of file skew.c.

References pixCountPixelsByRow().

◆ pixFindNormalizedSquareSum()

l_ok pixFindNormalizedSquareSum ( PIX pixs,
l_float32 *  phratio,
l_float32 *  pvratio,
l_float32 *  pfract 
)

pixFindNormalizedSquareSum()

Parameters
[in]pixs
[out]phratio[optional] ratio of normalized horiz square sum to result if the pixel distribution were uniform
[out]pvratio[optional] ratio of normalized vert square sum to result if the pixel distribution were uniform
[out]pfract[optional] ratio of fg pixels to total pixels
Returns
0 if OK, 1 on error or if there are no fg pixels
Notes:
     (1) Let the image have h scanlines and N fg pixels.
         If the pixels were uniformly distributed on scanlines,
         the sum of squares of fg pixels on each scanline would be
         h * (N / h)^2.  However, if the pixels are not uniformly
         distributed (e.g., for text), the sum of squares of fg
         pixels will be larger.  We return in hratio and vratio the
         ratio of these two values.
     (2) If there are no fg pixels, hratio and vratio are returned as 0.0.

Definition at line 1185 of file skew.c.

◆ pixFindSkew()

l_ok pixFindSkew ( PIX pixs,
l_float32 *  pangle,
l_float32 *  pconf 
)

pixFindSkew()

Parameters
[in]pixs1 bpp
[out]pangleangle required to deskew, in degrees
[out]pconfconfidence value is ratio max/min scores
Returns
0 if OK, 1 on error or if angle measurement not valid
Notes:
     (1) This is a simple high-level interface, that uses default
         values of the parameters for reasonable speed and accuracy.
     (2) The angle returned is the negative of the skew angle of
         the image.  It is the angle required for deskew.
         Clockwise rotations are positive angles.

Definition at line 375 of file skew.c.

◆ pixFindSkewAndDeskew()

PIX* pixFindSkewAndDeskew ( PIX pixs,
l_int32  redsearch,
l_float32 *  pangle,
l_float32 *  pconf 
)

pixFindSkewAndDeskew()

Parameters
[in]pixsany depth
[in]redsearchfor binary search: reduction factor = 1, 2 or 4; use 0 for default
[out]pangle[optional] angle required to deskew, in degrees; use NULL to skip
[out]pconf[optional] conf value is ratio of max/min scores; use NULL to skip
Returns
pixd deskewed pix, or NULL on error
Notes:
     (1) This binarizes if necessary and finds the skew angle.  If the
         angle is large enough and there is sufficient confidence,
         it returns a deskewed image; otherwise, it returns a clone.

Definition at line 246 of file skew.c.

◆ pixFindSkewSweep()

l_ok pixFindSkewSweep ( PIX pixs,
l_float32 *  pangle,
l_int32  reduction,
l_float32  sweeprange,
l_float32  sweepdelta 
)

pixFindSkewSweep()

Parameters
[in]pixs1 bpp
[out]pangleangle required to deskew, in degrees
[in]reductionfactor = 1, 2, 4 or 8
[in]sweeprangehalf the full range; assumed about 0; in degrees
[in]sweepdeltaangle increment of sweep; in degrees
Returns
0 if OK, 1 on error or if angle measurement not valid
Notes:
     (1) This examines the 'score' for skew angles with equal intervals.
     (2) Caller must check the return value for validity of the result.

Definition at line 419 of file skew.c.

◆ pixFindSkewSweepAndSearch()

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()

Parameters
[in]pixs1 bpp
[out]pangleangle required to deskew; in degrees
[out]pconfconfidence given by ratio of max/min score
[in]redsweepsweep reduction factor = 1, 2, 4 or 8
[in]redsearchbinary search reduction factor = 1, 2, 4 or 8; and must not exceed redsweep
[in]sweeprangehalf the full range, assumed about 0; in degrees
[in]sweepdeltaangle increment of sweep; in degrees
[in]minbsdeltamin binary search increment angle; in degrees
Returns
0 if OK, 1 on error or if angle measurement not valid
Notes:
     (1) This finds the skew angle, doing first a sweep through a set
         of equal angles, and then doing a binary search until
         convergence.
     (2) Caller must check the return value for validity of the result.
     (3) In computing the differential line sum variance score, we sum
         the result over scanlines, but we always skip:
          ~ at least one scanline
          ~ not more than 10% of the image height
          ~ not more than 5% of the image width
     (4) See also notes in pixFindSkewSweepAndSearchScore()

Definition at line 563 of file skew.c.

References pixFindSkewSweepAndSearchScore().

◆ pixFindSkewSweepAndSearchScore()

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()

Parameters
[in]pixs1 bpp
[out]pangleangle required to deskew; in degrees
[out]pconfconfidence given by ratio of max/min score
[out]pendscore[optional] max score; use NULL to ignore
[in]redsweepsweep reduction factor = 1, 2, 4 or 8
[in]redsearchbinary search reduction factor = 1, 2, 4 or 8; and must not exceed redsweep
[in]sweepcenterangle about which sweep is performed; in degrees
[in]sweeprangehalf the full range, taken about sweepcenter; in degrees
[in]sweepdeltaangle increment of sweep; in degrees
[in]minbsdeltamin binary search increment angle; in degrees
Returns
0 if OK, 1 on error or if angle measurement not valid
Notes:
     (1) This finds the skew angle, doing first a sweep through a set
         of equal angles, and then doing a binary search until convergence.
     (2) There are two built-in constants that determine if the
         returned confidence is nonzero:
           ~ MinValidMaxscore (minimum allowed maxscore)
           ~ MinscoreThreshFactor (determines minimum allowed
                minscore, by multiplying by (height * width^2)
         If either of these conditions is not satisfied, the returned
         confidence value will be zero.  The maxscore is optionally
         returned in this function to allow evaluation of the
         resulting angle by a method that is independent of the
         returned confidence value.
     (3) The larger the confidence value, the greater the probability
         that the proper alignment is given by the angle that maximizes
         variance.  It should be compared to a threshold, which depends
         on the application.  Values between 3.0 and 6.0 are common.
     (4) By default, the shear is about the UL corner.

Definition at line 617 of file skew.c.

References L_SHEAR_ABOUT_CORNER, and pixFindSkewSweepAndSearchScorePivot().

Referenced by pixFindSkewSweepAndSearch().

◆ pixFindSkewSweepAndSearchScorePivot()

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()

Parameters
[in]pixs1 bpp
[out]pangleangle required to deskew; in degrees
[out]pconfconfidence given by ratio of max/min score
[out]pendscore[optional] max score; use NULL to ignore
[in]redsweepsweep reduction factor = 1, 2, 4 or 8
[in]redsearchbinary search reduction factor = 1, 2, 4 or 8; and must not exceed redsweep
[in]sweepcenterangle about which sweep is performed; in degrees
[in]sweeprangehalf the full range, taken about sweepcenter; in degrees
[in]sweepdeltaangle increment of sweep; in degrees
[in]minbsdeltamin binary search increment angle; in degrees
[in]pivotL_SHEAR_ABOUT_CORNER, L_SHEAR_ABOUT_CENTER
Returns
0 if OK, 1 on error or if angle measurement not valid
Notes:
     (1) See notes in pixFindSkewSweepAndSearchScore().
     (2) This allows choice of shear pivoting from either the UL corner
         or the center.  For small angles, the ability to discriminate
         angles is better with shearing from the UL corner.  However,
         for large angles (say, greater than 20 degrees), it is better
         to shear about the center because a shear from the UL corner
         loses too much of the image.

Definition at line 666 of file skew.c.

Referenced by pixFindSkewSweepAndSearchScore().