#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	DEFAULT_SWEEP_RANGE = 7.

static const l_float32	DEFAULT_SWEEP_DELTA = 1.

static const l_float32	DEFAULT_MINBS_DELTA = 0.01

static const l_int32	DEFAULT_SWEEP_REDUCTION = 4

static const l_int32	DEFAULT_BS_REDUCTION = 2

static const l_float32	MIN_DESKEW_ANGLE = 0.1

static const l_float32	MIN_ALLOWED_CONFIDENCE = 3.0

static const l_int32	MIN_VALID_MAXSCORE = 10000

static const l_float32	MINSCORE_THRESHOLD_CONSTANT = 0.000002

static const l_int32	DEFAULT_BINARY_THRESHOLD = 130

Detailed Description

 Top-level deskew interfaces
     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]	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 205 of file skew.c.

◆ 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.
     (2) This may return a clone.

Definition at line 162 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]	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 285 of file skew.c.

◆ 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 1105 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 1178 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 370 of file skew.c.

◆ 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.

◆ 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 414 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]	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 558 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]	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:
           ~ MIN_VALID_MAXSCORE (minimum allowed maxscore)
           ~ MINSCORE_THRESHOLD_CONSTANT (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 612 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 661 of file skew.c.

Referenced by pixFindSkewSweepAndSearchScore().

Macros

Functions

Variables

Detailed Description

Function Documentation

◆ pixDeskew()

◆ pixDeskewBoth()

◆ pixDeskewGeneral()

◆ pixFindDifferentialSquareSum()

◆ pixFindNormalizedSquareSum()

◆ pixFindSkew()

◆ pixFindSkewAndDeskew()

◆ pixFindSkewSweep()

◆ pixFindSkewSweepAndSearch()

◆ pixFindSkewSweepAndSearchScore()

◆ pixFindSkewSweepAndSearchScorePivot()