#include <math.h>
#include "allheaders.h"

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
PIX *	pixDeskewBoth (PIX *pixs, l_int32 redsearch)

PIX *	pixDeskew (PIX *pixs, l_int32 redsearch)

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

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)

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.01f

static const l_int32	DefaultSweepReduction = 4

static const l_int32	DefaultBsReduction = 2

static const l_float32	MinDeskewAngle = 0.1f

static const l_float32	MinAllowedConfidence = 3.0

static const l_int32	MinValidMaxscore = 10000

static const l_float32	MinscoreThreshFactor = 0.000002f

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.

Macro Definition Documentation

◆ DEBUG_PLOT_SCORES

#define DEBUG_PLOT_SCORES 0 /* requires the gnuplot executable */

Definition at line 142 of file skew.c.

◆ DEBUG_PRINT_BINARY

#define DEBUG_PRINT_BINARY 0

Definition at line 139 of file skew.c.

◆ DEBUG_PRINT_ORTH

#define DEBUG_PRINT_ORTH 0

Definition at line 140 of file skew.c.

◆ DEBUG_PRINT_SCORES

#define DEBUG_PRINT_SCORES 0

Definition at line 137 of file skew.c.

◆ DEBUG_PRINT_SWEEP

#define DEBUG_PRINT_SWEEP 0

Definition at line 138 of file skew.c.

◆ DEBUG_THRESHOLD

#define DEBUG_THRESHOLD 0

Definition at line 141 of file skew.c.

Function Documentation

◆ pixDeskew()

PIX * pixDeskew	(	PIX *	pixs,
		l_int32	redsearch )

pixDeskew()

Parameters

[in]	pixs	any depth
[in]	redsearch	for 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 207 of file skew.c.

References pixDeskewGeneral().

Referenced by pixDeskewBoth().

◆ pixDeskewBoth()

PIX * pixDeskewBoth	(	PIX *	pixs,
		l_int32	redsearch )

pixDeskewBoth()

Parameters

[in]	pixs	any depth
[in]	redsearch	for 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.

Definition at line 166 of file skew.c.

References pixDeskew().

◆ 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]	pixs	any depth
[in]	redsweep	for linear search: reduction factor = 1, 2 or 4; use 0 for default
[in]	sweeprange	in degrees in each direction from 0; use 0.0 for default
[in]	sweepdelta	in degrees; use 0.0 for default
[in]	redsearch	for binary search: reduction factor = 1, 2 or 4; use 0 for default;
[in]	thresh	for 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 283 of file skew.c.

References L_BRING_IN_WHITE, L_ROTATE_AREA_MAP, and pixFindSkewSweepAndSearch().

Referenced by pixDeskew(), and pixFindSkewAndDeskew().

◆ pixFindDifferentialSquareSum()

l_ok pixFindDifferentialSquareSum	(	PIX *	pixs,
		l_float32 *	psum )

pixFindDifferentialSquareSum()

Parameters

[in]	pixs
[out]	psum	result

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 1095 of file skew.c.

Referenced by pixFindSkewSweep(), and pixFindSkewSweepAndSearchScorePivot().

◆ 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 1166 of file skew.c.

◆ pixFindSkew()

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

pixFindSkew()

Parameters

[in]	pixs	1 bpp
[out]	pangle	angle required to deskew, in degrees
[out]	pconf	confidence 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 366 of file skew.c.

References pixFindSkewSweepAndSearch().

◆ pixFindSkewAndDeskew()

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

pixFindSkewAndDeskew()

Parameters

[in]	pixs	any depth
[in]	redsearch	for 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 241 of file skew.c.

References pixDeskewGeneral().

◆ pixFindSkewOrthogonalRange()

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 )

Definition at line 1024 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]	pixs	1 bpp
[out]	pangle	angle required to deskew, in degrees
[in]	reduction	factor = 1, 2, 4 or 8
[in]	sweeprange	half the full range; assumed about 0; in degrees
[in]	sweepdelta	angle 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 408 of file skew.c.

References L_BRING_IN_WHITE, and pixFindDifferentialSquareSum().

◆ 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]	pixs	1 bpp
[out]	pangle	angle required to deskew; in degrees
[out]	pconf	confidence given by ratio of max/min score
[in]	redsweep	sweep reduction factor = 1, 2, 4 or 8
[in]	redsearch	binary search reduction factor = 1, 2, 4 or 8; and must not exceed redsweep
[in]	sweeprange	half the full range, assumed about 0; in degrees
[in]	sweepdelta	angle increment of sweep; in degrees
[in]	minbsdelta	min 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 550 of file skew.c.

References pixFindSkewSweepAndSearchScore().

Referenced by pixDeskewGeneral(), and pixFindSkew().

◆ 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]	pixs	1 bpp
[out]	pangle	angle required to deskew; in degrees
[out]	pconf	confidence given by ratio of max/min score
[out]	pendscore	[optional] max score; use NULL to ignore
[in]	redsweep	sweep reduction factor = 1, 2, 4 or 8
[in]	redsearch	binary search reduction factor = 1, 2, 4 or 8; and must not exceed redsweep
[in]	sweepcenter	angle about which sweep is performed; in degrees
[in]	sweeprange	half the full range, taken about sweepcenter; in degrees
[in]	sweepdelta	angle increment of sweep; in degrees
[in]	minbsdelta	min 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 604 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]	pixs	1 bpp
[out]	pangle	angle required to deskew; in degrees
[out]	pconf	confidence given by ratio of max/min score
[out]	pendscore	[optional] max score; use NULL to ignore
[in]	redsweep	sweep reduction factor = 1, 2, 4 or 8
[in]	redsearch	binary search reduction factor = 1, 2, 4 or 8; and must not exceed redsweep
[in]	sweepcenter	angle about which sweep is performed; in degrees
[in]	sweeprange	half the full range, taken about sweepcenter; in degrees
[in]	sweepdelta	angle increment of sweep; in degrees
[in]	minbsdelta	min binary search increment angle; in degrees
[in]	pivot	L_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 653 of file skew.c.

References L_BRING_IN_WHITE, L_SHEAR_ABOUT_CENTER, L_SHEAR_ABOUT_CORNER, and pixFindDifferentialSquareSum().

Referenced by pixFindSkewSweepAndSearchScore().

Variable Documentation

◆ DefaultBinaryThreshold

const l_int32 DefaultBinaryThreshold = 130

static

Definition at line 134 of file skew.c.

◆ DefaultBsReduction

const l_int32 DefaultBsReduction = 2

static

Definition at line 117 of file skew.c.

◆ DefaultMinbsDelta

const l_float32 DefaultMinbsDelta = 0.01f

static

Definition at line 113 of file skew.c.

◆ DefaultSweepDelta

const l_float32 DefaultSweepDelta = 1.0

static

Definition at line 107 of file skew.c.

◆ DefaultSweepRange

const l_float32 DefaultSweepRange = 7.0

static

Definition at line 106 of file skew.c.

◆ DefaultSweepReduction

const l_int32 DefaultSweepReduction = 4

static

Definition at line 116 of file skew.c.

◆ MinAllowedConfidence

const l_float32 MinAllowedConfidence = 3.0

static

Definition at line 123 of file skew.c.

◆ MinDeskewAngle

const l_float32 MinDeskewAngle = 0.1f

static

Definition at line 120 of file skew.c.

◆ MinscoreThreshFactor

const l_float32 MinscoreThreshFactor = 0.000002f

static

Definition at line 131 of file skew.c.

◆ MinValidMaxscore

const l_int32 MinValidMaxscore = 10000

static

Definition at line 126 of file skew.c.

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ DEBUG_PLOT_SCORES

◆ DEBUG_PRINT_BINARY

◆ DEBUG_PRINT_ORTH

◆ DEBUG_PRINT_SCORES

◆ DEBUG_PRINT_SWEEP

◆ DEBUG_THRESHOLD

Function Documentation

◆ pixDeskew()

◆ pixDeskewBoth()

◆ pixDeskewGeneral()

◆ pixFindDifferentialSquareSum()

◆ pixFindNormalizedSquareSum()

◆ pixFindSkew()

◆ pixFindSkewAndDeskew()

◆ pixFindSkewOrthogonalRange()

◆ pixFindSkewSweep()

◆ pixFindSkewSweepAndSearch()

◆ pixFindSkewSweepAndSearchScore()

◆ pixFindSkewSweepAndSearchScorePivot()

Variable Documentation

◆ DefaultBinaryThreshold

◆ DefaultBsReduction

◆ DefaultMinbsDelta

◆ DefaultSweepDelta

◆ DefaultSweepRange

◆ DefaultSweepReduction

◆ MinAllowedConfidence

◆ MinDeskewAngle

◆ MinscoreThreshFactor

◆ MinValidMaxscore