{"id":1435,"date":"2020-08-22T01:25:37","date_gmt":"2020-08-22T01:25:37","guid":{"rendered":"https:\/\/muthu.co\/?p=1435"},"modified":"2020-12-27T13:25:05","modified_gmt":"2020-12-27T13:25:05","slug":"skew-detection-and-correction-of-document-images-using-hough-transform","status":"publish","type":"post","link":"http:\/\/write.muthu.co\/skew-detection-and-correction-of-document-images-using-hough-transform\/","title":{"rendered":"Skew Detection and Correction of Document images using Hough Transform"},"content":{"rendered":"\n<p>In this post I will be talking about how we can use Hough Transform to detect and correct Skewness of a document image. There have been many research papers published around this problem and it keeps getting published even today on various journals mainly because its still largely an unsolved problem. I had previously written about Skew correction using Horizontal Projections <a href=\"https:\/\/muthu.co\/deskewing-scanned-documents-using-horizontal-projections\/\">here<\/a> which used the Horizontal projection of an image to indetify the skew angle, The problem with deskewing using Projections is that it fails in many cases where the text may have too many spaces and when the document has less text. This made me look for a better solution and I came across Hough Transform based skew detection technique which is has a better accuracy.<\/p>\n\n\n\n<p>Hough transform is a feature extraction technique that converts an image from Cartesian to polar coordinates which is how it got &#8220;transform&#8221; in its name. It can be used to detect lines or a set of collinear points on the image. If you are new to Hough Transform I would recommend you take a look at the video below which is one of the best one on the internet on this topic. <\/p>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"How Hough Transform works\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/4zHbI-fFIlI?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>The basic idea is:<\/p>\n\n\n\n<ul><li>Convert the image to grayscale<\/li><li>Apple Canny or Sobel filter<\/li><li>Find Hough lines between 0.1 to 180 degree angle.<\/li><li>Round the angles from line peaks to 2 decimal places.<\/li><li>Find the angle with the highest occurrence.<\/li><li>Rotate the image with that angle<\/li><\/ul>\n\n\n\n<p>Here is a sample image which is skewed.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"657\" height=\"853\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2020\/08\/doc.png\" alt=\"\" class=\"wp-image-1438\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/doc.png 657w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/doc-231x300.png 231w\" sizes=\"(max-width: 657px) 100vw, 657px\" \/><\/figure>\n\n\n\n<p>After finding the Hough Lines<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"851\" height=\"524\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2020\/08\/download-8.png\" alt=\"\" class=\"wp-image-1440\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-8.png 851w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-8-300x185.png 300w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-8-768x473.png 768w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-8-769x474.png 769w\" sizes=\"(max-width: 851px) 100vw, 851px\" \/><\/figure>\n\n\n\n<p>As you can see, we have detected a decent number of lines connecting our words. And all we have to do now is to find the orientation of the lines which connect the words.<\/p>\n\n\n\n<p>The code to generate the Hough lines is as below.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import numpy as np\nfrom skimage.transform import hough_line, hough_line_peaks\nfrom skimage.transform import rotate\nfrom skimage.feature import canny\nfrom skimage.io import imread\nfrom skimage.color import rgb2gray\nimport matplotlib.pyplot as plt\nfrom scipy.stats import mode\n\nimage = rgb2gray(imread(\"samples\/doc.png\"))\n\nedges = canny(image)\n# Classic straight-line Hough transform\ntested_angles = np.deg2rad(np.arange(0.1, 180.0))\nh, theta, d = hough_line(edges, theta=tested_angles)\n\n# Generating figure 1\nfig, axes = plt.subplots(1, 2, figsize=(15, 16))\nax = axes.ravel()\n\nax&#91;0].imshow(image, cmap=\"gray\")\nax&#91;0].set_title('Input image')\nax&#91;0].set_axis_off()\n\nax&#91;1].imshow(edges, cmap=\"gray\")\norigin = np.array((0, image.shape&#91;1]))\n\nfor _, angle, dist in zip(*hough_line_peaks(h, theta, d)):\n    y0, y1 = (dist - origin * np.cos(angle)) \/ np.sin(angle)\n    ax&#91;1].plot(origin, (y0, y1), '-r')\n    \nax&#91;1].set_xlim(origin)\nax&#91;1].set_ylim((edges.shape&#91;0], 0))\nax&#91;1].set_axis_off()\nax&#91;1].set_title('Detected lines')<\/code><\/pre>\n\n\n\n<p>Hough line method also gives us the angle made by the line with the origin as shown below.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"350\" height=\"303\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2020\/08\/untitled-1.png\" alt=\"\" class=\"wp-image-1441\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/untitled-1.png 350w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/untitled-1-300x260.png 300w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><\/figure>\n\n\n\n<p>As you might have guessed by now, we only need to isolate these potentially horizontal lines to get our skew angle. To do that, I am looking at the most commonly occurring angle and will rotate my image. The below method gives the skew angle.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def skew_angle_hough_transform(image):\n    # convert to edges\n    edges = canny(image)\n    # Classic straight-line Hough transform between 0.1 - 180 degrees.\n    tested_angles = np.deg2rad(np.arange(0.1, 180.0))\n    h, theta, d = hough_line(edges, theta=tested_angles)\n    \n    # find line peaks and angles\n    accum, angles, dists = hough_line_peaks(h, theta, d)\n    \n    # round the angles to 2 decimal places and find the most common angle.\n    most_common_angle = mode(np.around(angles, decimals=2))&#91;0]\n    \n    # convert the angle to degree for rotation.\n    skew_angle = np.rad2deg(most_common_angle - np.pi\/2)\n    return skew_angle<\/code><\/pre>\n\n\n\n<p>Here is the final output of Skew correction using Hough Transform. The angle of rotation is identified as: 2.24620502 degree.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"614\" src=\"https:\/\/muthu.co\/wp-content\/uploads\/2020\/08\/download-9-1024x614.png\" alt=\"\" class=\"wp-image-1442\" srcset=\"http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-9-1024x614.png 1024w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-9-300x180.png 300w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-9-768x460.png 768w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-9-769x461.png 769w, http:\/\/write.muthu.co\/wp-content\/uploads\/2020\/08\/download-9.png 1156w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>Another important thing to note here is that, if the angle is greater than 90 degree which was the case in my sample, the image is titled clockwise and if it is its less than 90 degrees, its tilted anti-clockwise. In both cases we need to subtract the identified angle by 90 to get the rotation angle we need. <\/p>\n\n\n\n<p>Here is the full notebook for your reference:<\/p>\n\n\n\n<p><a href=\"https:\/\/jovian.ml\/viewer?url=https:\/\/github.com\/muthuspark\/ml_research\/blob\/master\/Skew%20angle%20detection%20and%20correction%20using%20Hough%20Transform.ipynb\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/jovian.ml\/viewer?url=https:\/\/github.com\/muthuspark\/ml_research\/blob\/master\/Skew%20angle%20detection%20and%20correction%20using%20Hough%20Transform.ipynb<\/a><\/p>\n ","protected":false},"excerpt":{"rendered":"<p>In this post I will be talking about how we can use Hough Transform to detect and correct Skewness of a document image. There have been many research papers published around this problem and it keeps getting published even today on various journals mainly because its still largely an unsolved problem. I had previously written [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":1440,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[38],"tags":[47],"_links":{"self":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1435"}],"collection":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/comments?post=1435"}],"version-history":[{"count":1,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1435\/revisions"}],"predecessor-version":[{"id":1532,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/posts\/1435\/revisions\/1532"}],"wp:featuredmedia":[{"embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media\/1440"}],"wp:attachment":[{"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/media?parent=1435"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/categories?post=1435"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/write.muthu.co\/wp-json\/wp\/v2\/tags?post=1435"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}