{"id":846,"date":"2017-06-05T21:26:25","date_gmt":"2017-06-05T19:26:25","guid":{"rendered":"http:\/\/tomaszkacmajor.pl\/?p=846"},"modified":"2020-05-17T15:56:46","modified_gmt":"2020-05-17T13:56:46","slug":"hough-lines-transform-explained","status":"publish","type":"post","link":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/","title":{"rendered":"Hough Lines Transform Explained"},"content":{"rendered":"\n

Hough Lines Transform is the key method used in the previous project<\/a> where lane lines are detected. It is very helpful in many Computer Vision applications. The original form of Hough Transform aimed to identify straight lines<\/strong>. And that’s what I’m going to explain today. Furthermore, this technique was later generalized to detect also other shapes like circles, ellipses etc. [1]<\/a>.<\/p>\n\n\n\n\n\n\n\n

The goal of the method, image preparation<\/h3>\n\n\n\n

To use Hough Lines Transform, processed image should be binary. But we would like to search for the straight lines on an original, color image. Therefore, probably the most common solution is to firstly grayscale the image and then to detect edges. Such mask of edges can be then fetched to the Hough Lines method which should output a set of straight lines found on an image.<\/p>\n\n\n\n

Straight lines representations<\/h3>\n\n\n\n

As we learned from quite early school classes, the straight line can be represented by two parameters. The simplest and most widely used pair of parameters is \"(a, b)\" which correspond to slope and intercept. The line is then described as:<\/p>\n\n\n\n


\"{y = a x + b}\"<\/p>\n\n\n\n

Let’s forget for a while about these parameters. We can also unambiguously describe the line using the pair \"(\rho, \theta)\" in polar system. The first parameter, \"\rho\", is the shortest distance from the origin to the line (approaching the line perpendicularly). The second, \"\theta\", is the angle between x-axis and the distance line. One of the benefits of such representation is that we can describe vertical lines by \"\rho\" and \"\theta\" which is impossible by using only \"(a, b)\" parameters in cartesian system.<\/p>\n\n\n\n

\"Line\"<\/a><\/figure><\/div>\n\n\n\n

For a given line, we can determine specific \"\rho\" and \"\theta\". Then, the following equation is satisfied for each \"x_i\", \"y_i\" point belonging to this line:<\/p>\n\n\n\n

\"\LARGE{\rho = x cos(\theta) + y sin(\theta)}\"<\/p>\n\n\n\n

Mapping from Image space to Hough space<\/h3>\n\n\n\n

Let’s draw a line on an image space again. As we already know, it is represented by some \"\rho\" and \"\theta\". So, we can draw such point in \"(\rho,\theta)\" coordinates which will be later called a Hough space.<\/p>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n

Now, in the image space, we are drawing other lines which are intersecting at one common point. Let’s see what points will be produced in Hough space which are corresponding to these lines.<\/p>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n

It turns out that these points in \"(\rho,\theta)\" space are forming a sinusoid. Drawing infinite number of additional lines intersecting at this one point would result in a continuous sinusoid in Hough space. So, maybe, we can say that a point<\/strong> in image space results in a sinusoid<\/strong> in Hough space? Let’s recall the equation \"\rho = x cos(\theta) + y sin(\theta)$\". Indeed, for fixed \"(x_0, y_0)\" parameters representing point in image space and sliding through all possible values of \"\theta\" in some range, we obtain \"\rho\" values which form a sinusoid.<\/p>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n

To sum up, we observed following relations:<\/p>\n\n\n\n

Image space<\/strong><\/td>Hough space<\/strong><\/td><\/tr>
Straight line<\/td>Point<\/td><\/tr>
Point<\/td>Sinusoid<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

Finding Hough Lines<\/h3>\n\n\n\n

Finally, maybe the most interesting effect. If we draw points which form a line in the image space, we will obtain a bunch of sinusoids in the Hough space. But, magically, they are intersecting at exactly one point!<\/p>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n

It means that, to identify candidates for being a straight line, we should seek for intersections in Hough space. Below, you can see 2 lines and corresponding image in Hough space. Sure enough, there are 2 main intersections highlighted here for convenience. They are representatives (by \"\rho\" and \"\theta\" parameters) of the straight lines.<\/p>\n\n\n\n

\"\"<\/a><\/figure><\/div>\n\n\n\n
from en.wikipedia.org\/wiki\/Hough_transform<\/a><\/div>\n\n\n\n

Hough Lines parameters<\/h4>\n\n\n\n

In real application, for example using OpenCV library, the Hough space of an image is divided into uniform clusters. The grid is defined by parameters which can be called rho resolution<\/em> and theta resolution<\/em>. They often equals 1 pixel and 1 degree respectively. We sweep through all cells in the grid and count how many votes there are for a certain line. If there are more votes than a given threshold, we claim that the straight line has been found and it’s described by \"\rho\" and \"\theta\" parameters from the considered cluster.<\/p>\n\n\n\n

Implementation in Python<\/h3>\n\n\n\n

OK, now we are ready to find Hough Lines in real image using OpenCV and Python. After image loading I perform grayscaling, blurring and edge detection. Then, OpenCV cv2.HoughLines<\/em> function is called to obtain set of detected lines. Next, the results are presented. Note that function cv2.HoughLines<\/em> requires 3 parameters which were discussed before. They were chosen experimentally for the given image example. It’s good to play with these parameters. E.g. if threshold is lower, more lines will be found and vice versa.<\/p>\n\n\n\n

\nimport matplotlib.pyplot as plt\nimport matplotlib.image as mpimg\nimport numpy as np\nimport cv2\n\nimage = mpimg.imread("test_images\/ppnt.jpg")\ngray_image = cv2.cvtColor(image, cv2.COLOR_RGB2GRAY)\nblurred_image = cv2.GaussianBlur(gray_image, (9, 9), 0)\nedges_image = cv2.Canny(blurred_image, 50, 120)\n\nrho_resolution = 1\ntheta_resolution = np.pi\/180\nthreshold = 155\n\nhough_lines = cv2.HoughLines(edges_image, rho_resolution , theta_resolution , threshold)\n\nhough_lines_image = np.zeros_like(image)\ndraw_lines(hough_lines_image, hough_lines)\noriginal_image_with_hough_lines = weighted_img(hough_lines_image,image)\n\nplt.figure(figsize = (30,20))\nplt.subplot(131)\nplt.imshow(image)\nplt.subplot(132)\nplt.imshow(edges_image, cmap='gray')\nplt.subplot(133)\nplt.imshow(original_image_with_hough_lines, cmap='gray')\nplt.show()\n<\/pre><\/pre>\n\n\n\n
Below, there are some helper functions. I attach them for a better understanding of the entire code.<\/p>\n\n\n\n
\ndef draw_lines(img, houghLines, color=[0, 255, 0], thickness=2):\n    for line in houghLines:\n        for rho,theta in line:\n            a = np.cos(theta)\n            b = np.sin(theta)\n            x0 = a*rho\n            y0 = b*rho\n            x1 = int(x0 + 1000*(-b))\n            y1 = int(y0 + 1000*(a))\n            x2 = int(x0 - 1000*(-b))\n            y2 = int(y0 - 1000*(a))\n\n            cv2.line(img,(x1,y1),(x2,y2),color,thickness)   \n\ndef weighted_img(img, initial_img, \u03b1=0.8, \u03b2=1., \u03bb=0.):\n    return cv2.addWeighted(initial_img, \u03b1, img, \u03b2, \u03bb)\n<\/pre><\/pre>\n\n\n\n
Example results<\/h3>\n\n\n\n
Results can be seen below. If there are too much lines in our opinion, or too few of them, we should adjust rho resolution<\/em>, theta resolution<\/em> and threshold<\/em> parameters. But remember also about tuning parameters which are used in blurring and edge detection. Whole pipeline should be revised to fit your needs.<\/p>\n\n\n\n
\"\"<\/a><\/figure><\/div>\n\n\n\n
\"\"<\/a><\/figure><\/div>\n\n\n\n
\"\"<\/a><\/figure><\/div>\n\n\n\n
It’s worth noting that in OpenCV there exists another version of the function to find Hough Lines. It’s named HoughLinesP<\/strong><\/em>. P suffix stands for probabilistic<\/em> here. It has more efficient implementation and the function outputs extremes of detected lines \"(x_0, y_0, x_1, y_1)\" which can be very useful. Below, there is an example of the same image with the straight lines found using HoughLinesP<\/em>.<\/p>\n\n\n\n
\"\"<\/a><\/figure><\/div>\n\n\n\n
References<\/h3>\n\n\n\n

1. Generalized Hough Transform on Wikipedia<\/a>
2. Hough Transform on Wikipedia<\/a>
3. OpenCV 2.4 documentation<\/a> – Hough Lines Transform
4. OpenCV 3.1 documentation<\/a> – Hough Lines Transform<\/p>\n","protected":false},"excerpt":{"rendered":"
Hough Lines Transform is the key method used in the previous project where lane lines are detected. It is very helpful in many Computer Vision applications. The original form of Hough Transform aimed to identify straight lines. And that’s what I’m going to explain today. Furthermore, this technique was later generalized to detect also other […]<\/p>\n","protected":false},"author":1,"featured_media":850,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19],"tags":[8,22,21],"class_list":["post-846","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-self-driving-cars","tag-image-processing","tag-opencv","tag-python"],"blocksy_meta":[],"yoast_head":"\nHough Lines Transform Explained - tomaszkacmajor.pl<\/title>\n<meta name=\"description\" content=\"Explanation of Hough Lines method used for detecting straight lines on an image. Many visualizations along with implementation in Python and real examples.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Hough Lines Transform Explained - tomaszkacmajor.pl\" \/>\n<meta property=\"og:description\" content=\"Explanation of Hough Lines method used for detecting straight lines on an image. Many visualizations along with implementation in Python and real examples.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/\" \/>\n<meta property=\"og:site_name\" content=\"tomaszkacmajor.pl\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/ProggBlogg\/\" \/>\n<meta property=\"article:published_time\" content=\"2017-06-05T19:26:25+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-05-17T13:56:46+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"900\" \/>\n\t<meta property=\"og:image:height\" content=\"561\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"tomasz.kacmajor\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@tkacmajor\" \/>\n<meta name=\"twitter:site\" content=\"@tkacmajor\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"tomasz.kacmajor\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"6 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/\",\"url\":\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/\",\"name\":\"Hough Lines Transform Explained - tomaszkacmajor.pl\",\"isPartOf\":{\"@id\":\"https:\/\/tomaszkacmajor.pl\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg\",\"datePublished\":\"2017-06-05T19:26:25+00:00\",\"dateModified\":\"2020-05-17T13:56:46+00:00\",\"author\":{\"@id\":\"https:\/\/tomaszkacmajor.pl\/#\/schema\/person\/5f40890309a32ae4f63fa6a284215b6c\"},\"description\":\"Explanation of Hough Lines method used for detecting straight lines on an image. Many visualizations along with implementation in Python and real examples.\",\"breadcrumb\":{\"@id\":\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#primaryimage\",\"url\":\"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg\",\"contentUrl\":\"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg\",\"width\":900,\"height\":561},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Strona g\u0142\u00f3wna\",\"item\":\"https:\/\/tomaszkacmajor.pl\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Hough Lines Transform Explained\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/tomaszkacmajor.pl\/#website\",\"url\":\"https:\/\/tomaszkacmajor.pl\/\",\"name\":\"tomaszkacmajor.pl\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/tomaszkacmajor.pl\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Person\",\"@id\":\"https:\/\/tomaszkacmajor.pl\/#\/schema\/person\/5f40890309a32ae4f63fa6a284215b6c\",\"name\":\"tomasz.kacmajor\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/tomaszkacmajor.pl\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/a1fe5c8a80549b9a680c7a6f9ea33a94?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/a1fe5c8a80549b9a680c7a6f9ea33a94?s=96&d=mm&r=g\",\"caption\":\"tomasz.kacmajor\"},\"url\":\"https:\/\/tomaszkacmajor.pl\/index.php\/author\/tomasz-kacmajor\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Hough Lines Transform Explained - tomaszkacmajor.pl","description":"Explanation of Hough Lines method used for detecting straight lines on an image. Many visualizations along with implementation in Python and real examples.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/","og_locale":"en_US","og_type":"article","og_title":"Hough Lines Transform Explained - tomaszkacmajor.pl","og_description":"Explanation of Hough Lines method used for detecting straight lines on an image. Many visualizations along with implementation in Python and real examples.","og_url":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/","og_site_name":"tomaszkacmajor.pl","article_publisher":"https:\/\/www.facebook.com\/ProggBlogg\/","article_published_time":"2017-06-05T19:26:25+00:00","article_modified_time":"2020-05-17T13:56:46+00:00","og_image":[{"width":900,"height":561,"url":"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg","type":"image\/jpeg"}],"author":"tomasz.kacmajor","twitter_card":"summary_large_image","twitter_creator":"@tkacmajor","twitter_site":"@tkacmajor","twitter_misc":{"Written by":"tomasz.kacmajor","Est. reading time":"6 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/","url":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/","name":"Hough Lines Transform Explained - tomaszkacmajor.pl","isPartOf":{"@id":"https:\/\/tomaszkacmajor.pl\/#website"},"primaryImageOfPage":{"@id":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#primaryimage"},"image":{"@id":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#primaryimage"},"thumbnailUrl":"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg","datePublished":"2017-06-05T19:26:25+00:00","dateModified":"2020-05-17T13:56:46+00:00","author":{"@id":"https:\/\/tomaszkacmajor.pl\/#\/schema\/person\/5f40890309a32ae4f63fa6a284215b6c"},"description":"Explanation of Hough Lines method used for detecting straight lines on an image. Many visualizations along with implementation in Python and real examples.","breadcrumb":{"@id":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#primaryimage","url":"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg","contentUrl":"https:\/\/tomaszkacmajor.pl\/wp-content\/uploads\/2017\/06\/Clipboard01-1.jpg","width":900,"height":561},{"@type":"BreadcrumbList","@id":"https:\/\/tomaszkacmajor.pl\/index.php\/2017\/06\/05\/hough-lines-transform-explained\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Strona g\u0142\u00f3wna","item":"https:\/\/tomaszkacmajor.pl\/"},{"@type":"ListItem","position":2,"name":"Hough Lines Transform Explained"}]},{"@type":"WebSite","@id":"https:\/\/tomaszkacmajor.pl\/#website","url":"https:\/\/tomaszkacmajor.pl\/","name":"tomaszkacmajor.pl","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/tomaszkacmajor.pl\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Person","@id":"https:\/\/tomaszkacmajor.pl\/#\/schema\/person\/5f40890309a32ae4f63fa6a284215b6c","name":"tomasz.kacmajor","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/tomaszkacmajor.pl\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/a1fe5c8a80549b9a680c7a6f9ea33a94?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/a1fe5c8a80549b9a680c7a6f9ea33a94?s=96&d=mm&r=g","caption":"tomasz.kacmajor"},"url":"https:\/\/tomaszkacmajor.pl\/index.php\/author\/tomasz-kacmajor\/"}]}},"_links":{"self":[{"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/posts\/846","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/comments?post=846"}],"version-history":[{"count":134,"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/posts\/846\/revisions"}],"predecessor-version":[{"id":1703,"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/posts\/846\/revisions\/1703"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/media\/850"}],"wp:attachment":[{"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/media?parent=846"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/categories?post=846"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tomaszkacmajor.pl\/index.php\/wp-json\/wp\/v2\/tags?post=846"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}