![]() |
Leptonica
1.82.0
Image processing and image analysis suite
|
#include <math.h>
#include "allheaders.h"
Go to the source code of this file.
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) |
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.
[in] | pixs | any depth |
[in] | redsearch | for binary search: reduction factor = 1, 2 or 4; use 0 for default |
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.
[in] | pixs | any depth |
[in] | redsearch | for binary search: reduction factor = 1, 2 or 4; use 0 for default |
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().
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 | ||
) |
[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 |
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.
l_ok pixFindDifferentialSquareSum | ( | PIX * | pixs, |
l_float32 * | psum | ||
) |
pixFindDifferentialSquareSum()
[in] | pixs | |
[out] | psum | result |
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().
l_ok pixFindNormalizedSquareSum | ( | PIX * | pixs, |
l_float32 * | phratio, | ||
l_float32 * | pvratio, | ||
l_float32 * | pfract | ||
) |
[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 |
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.
l_ok pixFindSkew | ( | PIX * | pixs, |
l_float32 * | pangle, | ||
l_float32 * | pconf | ||
) |
[in] | pixs | 1 bpp |
[out] | pangle | angle required to deskew, in degrees |
[out] | pconf | confidence value is ratio max/min scores |
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.
[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 |
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.
l_ok pixFindSkewSweep | ( | PIX * | pixs, |
l_float32 * | pangle, | ||
l_int32 | reduction, | ||
l_float32 | sweeprange, | ||
l_float32 | sweepdelta | ||
) |
[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 |
Notes: (1) This examines the 'score' for skew angles with equal intervals. (2) Caller must check the return value for validity of the result.
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 | ||
) |
[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 |
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().
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()
[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 |
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().
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()
[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 |
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().