# Skew detection and correction using Fourier transform

I was trying to implement skew correction method for scanned documents using the method described in this paper.

The algorithm steps:

1- Threshold the image .

2- Find the fourier transform.

3- Divide the frequency space into 4 quadrants .

4- Calculate the angle of each quadrant.

5- if detected angle >= 45 then final angle = 90 - 45 else final angle = - detected angle

It's easy to implement the first 3 steps, now I can't figure out how to detect the angle from each quadrant as this step is the most important step I also tried to read another similar resource but I can't figure it out yet .

I'm using C# with Emgu on windows 7

sample code done so far:

private static Bitmap Matrix2Bitmap(Matrix<float> matrix)
{
CvInvoke.cvNormalize(matrix, matrix, 0.0, 255.0, Emgu.CV.CvEnum.NORM_TYPE.CV_MINMAX, IntPtr.Zero);

Image<Gray, float> image = new Image<Gray, float>(matrix.Size);
matrix.CopyTo(image);

return image.ToBitmap();
}

// Real part is magnitude, imaginary is phase.
// Here we compute log(sqrt(Re^2 + Im^2) + 1) to get the magnitude and
// rescale it so everything is visible
private static Matrix<float> GetDftMagnitude(Matrix<float> fftData)
{
//The Real part of the Fourier Transform
Matrix<float> outReal = new Matrix<float>(fftData.Size);
//The imaginary part of the Fourier Transform
Matrix<float> outIm = new Matrix<float>(fftData.Size);
CvInvoke.cvSplit(fftData, outReal, outIm, IntPtr.Zero, IntPtr.Zero);

CvInvoke.cvPow(outReal, outReal, 2.0);
CvInvoke.cvPow(outIm, outIm, 2.0);

CvInvoke.cvPow(outReal, outReal, 0.5);

CvInvoke.cvAddS(outReal, new MCvScalar(1.0), outReal, IntPtr.Zero); // 1 + Mag
CvInvoke.cvLog(outReal, outReal); // log(1 + Mag)

return outReal;
}

public static Bitmap DFT(Bitmap bmp)
{
Image<Gray, float> image = new Image<Gray, float>(bmp);

// Transform 1 channel grayscale image into 2 channel image
IntPtr complexImage = CvInvoke.cvCreateImage(image.Size, Emgu.CV.CvEnum.IPL_DEPTH.IPL_DEPTH_32F, 2);
CvInvoke.cvSetImageCOI(complexImage, 1); // Select the channel to copy into
CvInvoke.cvCopy(image, complexImage, IntPtr.Zero);
CvInvoke.cvSetImageCOI(complexImage, 0); // Select all channels

// This will hold the DFT data
Matrix<float> forwardDft = new Matrix<float>(image.Rows, image.Cols, 2);
CvInvoke.cvDFT(complexImage, forwardDft, Emgu.CV.CvEnum.CV_DXT.CV_DXT_FORWARD, 0);

CvInvoke.cvReleaseImage(ref complexImage);

// We'll display the magnitude
Matrix<float> forwardDftMagnitude = GetDftMagnitude(forwardDft);

// Now compute the inverse to see if we can get back the original

return Matrix2Bitmap(forwardDftMagnitude);

}
public static Bitmap IDFT(Matrix<float> forwardDft)
{
Matrix<float> reverseDft = new Matrix<float>(forwardDft.Rows, forwardDft.Cols, 2);
CvInvoke.cvDFT(forwardDft, reverseDft, Emgu.CV.CvEnum.CV_DXT.CV_DXT_INV_SCALE, 0);
Matrix<float> reverseDftMagnitude = GetDftMagnitude(reverseDft);
return Matrix2Bitmap(reverseDftMagnitude);
}
// We have to switch quadrants so that the origin is at the image center
private static void SwitchQuadrants(ref Matrix<float> matrix)
{
int cx = matrix.Cols / 2;
int cy = matrix.Rows / 2;

Matrix<float> q0 = matrix.GetSubRect(new Rectangle(0, 0, cx, cy));
Matrix<float> q1 = matrix.GetSubRect(new Rectangle(cx, 0, cx, cy));
Matrix<float> q2 = matrix.GetSubRect(new Rectangle(0, cy, cx, cy));
Matrix<float> q3 = matrix.GetSubRect(new Rectangle(cx, cy, cx, cy));
Matrix<float> tmp = new Matrix<float>(q0.Size);

q0.CopyTo(tmp);
q3.CopyTo(q0);
tmp.CopyTo(q3);
q1.CopyTo(tmp);
q2.CopyTo(q1);
tmp.CopyTo(q2);
}


Sample Image:

Fourier transform output: