Line detection: Difference between revisions

Revision as of 09:32, 19 May 2018

Latest revision as of 17:33, 20 March 2025

(27 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Algorithm}}

{{multiple issues|

In image processing, '''line detection''' is an algorithm that takes a collection of ''n'' [[edge detection|edge points]] and finds all the lines on which these edge points lie.<ref name=":0">{{Cite book|url=https://www.worldcat.org/oclc/491888664|title=Digital image processing and analysis : human and computer vision applications with CVIPtools|last=Umbaugh|first=Scott E.|date=2011|publisher=CRC Press|isbn=9781439802052|edition=2nd|___location=Boca Raton, FL|oclc=491888664}}</ref> The most popular line detectors are the [[Hough transform]] and [[Kernel (image processing)|convolution]] -based techniques.<ref>{{Cite web|url=http://www.mathworks.com/help/images/ref/hough.html|title=Hough transform - MATLAB hough|website=www.mathworks.com|access-date=2018-04-23}}</ref>

{{essay-like|date=April 2018}}

{{orphan|date=April 2018}}

{{refimprove|date=April 2018}}

}}

== Hough transform ==

In image processing, '''line detection''' is an algorithm that takes a collection of n [[edge detection|edge points]] and finds all the lines on which these edge points lie.<ref name=":0">{{Cite book|url=https://www.worldcat.org/oclc/491888664|title=Digital image processing and analysis : human and computer vision applications with CVIPtools|last=Umbaugh|first=Scott E.|date=2011|publisher=CRC Press|isbn=9781439802052|edition=2nd|___location=Boca Raton, FL|oclc=491888664}}</ref> The most popular line detectors are the [[Hough transform]] and [[Kernel (image processing)|convolution]] based techniques.<ref>{{Cite web|url=http://www.mathworks.com/help/images/ref/hough.html|title=Hough transform - MATLAB hough|website=www.mathworks.com|access-date=2018-04-23}}</ref>

The [[Hough transform]]<ref name="CalTechCaltech">{{Cite web|url=http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/HoughTrans_lines_09.pdf|title=Line Detection by Hough transformation|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}</ref> can be used to detect lines and the output is a parametric description of the lines in an image, for example ρ = r cos(θ) + c sin(θ).<ref name=":0" /> If wethere haveis a line in oura row and column based image space, weit can definebe that line bydefined ρ, the distance from the origin to the line along a perpendicular to the line, and θ, the angle of the perpendicular projection from the origin to the line measured in degrees clockwise from the positive row axis. Therefore, a line in the image corresponds to a point in the Hough space.<ref>{{cite web|url=http://vision.stanford.edu/teaching/cs231a_autumn1112/lecture/lecture4_edges_lines_cs231a_marked.pdf |title=Finding lines: from detection to model fitting |first=Fei‐FeiFei-Fei |last=Li |date=10 October 2011 |publisher=Stanford Vision Lab}}</ref> The Hough space for lines has therefore these two dimensions θ and ρ, and a line is represented by a single point corresponding to a unique set of these parameters. The Hough transform can then be implemented by choosing a set of values of ρ and θ to use. For each pixel ({{var|r}}, {{var|c }}) in the image, we compute r cos(θ) + c sin(θ) for each values of θ, and place the result in the appropriate position in the (ρ, θ) array. At the end, the values of (ρ, θ) with the highest values in the array will correspond to strongest lines in the image

== Convolution-based technique ==

The [[Hough transform]]<ref name="CalTech">{{Cite web|url=http://web.ipac.caltech.edu/staff/fmasci/home/astro_refs/HoughTrans_lines_09.pdf|title=Line Detection by Hough transformation|last=|first=|date=|website=|archive-url=|archive-date=|dead-url=|access-date=}}</ref> can be used to detect lines and the output is a parametric description of the lines in an image, for example ρ = r cos(θ) + c sin(θ).<ref name=":0" /> If we have a line in our row and column based image space, we can define that line by ρ, the distance from the origin to the line along a perpendicular to the line, and θ, the angle of the perpendicular projection from the origin to the line measured in degrees clockwise from the positive row axis. Therefore, a line in the image corresponds to a point in the Hough space.<ref>{{cite web|url=http://vision.stanford.edu/teaching/cs231a_autumn1112/lecture/lecture4_edges_lines_cs231a_marked.pdf |title=Finding lines: from detection to model fitting |first=Fei‐Fei |last=Li |date=10 October 2011 |publisher=Stanford Vision Lab}}</ref> The Hough space for lines has therefore these two dimensions θ and ρ, and a line is represented by a single point corresponding to a unique set of these parameters. The Hough transform can then be implemented by choosing a set of values of ρ and θ to use. For each pixel (r, c ) in the image, we compute r cos(θ) + c sin(θ) for each values of θ, and place the result in the appropriate position in the (ρ, θ) array. At the end, the values of (ρ, θ) with the highest values in the array will correspond to strongest lines in the image

In a [[Kernel (image processing)|convolution]] -based technique, the line detector operator consists of a convolution masks tuned to detect the presence of lines of a particular width n and a θ orientation. Here are the four convolution masks to detect horizontal, vertical, oblique (+45 degrees), and oblique (-45−45 degrees) lines in an image.

In a [[Kernel (image processing)|convolution]] based technique, the line detector operator consists of a convolution masks tuned to detect the presence of lines of a particular width n and a θ orientation. Here are the four convolution masks to detect horizontal, vertical, oblique (+45 degrees), and oblique (-45 degrees) lines in an image.

<references group="https://homepages.inf.ed.ac.uk/rbf/HIPR2/linedet.htm" />a) Horizontal mask(R1)

{| class="wikitable"

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

|-

| 2

| 2

| 2

|-

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

|}

(b) Vertical (R3)

{| class="wikitable"

| −1

|<nowiki>-1</nowiki>

| 2

| −1

|<nowiki>-1</nowiki>

|-

| −1

|<nowiki>-1</nowiki>

| 2

| −1

|<nowiki>-1</nowiki>

|-

| −1

|<nowiki>-1</nowiki>

| 2

| −1

|<nowiki>-1</nowiki>

|}

(C) Oblique (+45 degrees)(R2)

{| class="wikitable"

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

| 2

|-

| −1

|<nowiki>-1</nowiki>

| 2

| −1

|<nowiki>-1</nowiki>

|-

| 2

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

|}

(d) Oblique (-45−45 degrees)(R4)

{| class="wikitable"

| 2

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

|-

| −1

|<nowiki>-1</nowiki>

| 2

| −1

|<nowiki>-1</nowiki>

|-

| −1

|<nowiki>-1</nowiki>

| −1

|<nowiki>-1</nowiki>

| 2

|}

<ref name=":1" />

Line 79 ⟶ 76:

|}

As can be seen below, if mask is overlay on the image (horizontal line), multiply the coincident values, and sum all these results, the output will be the (convolved image). For example, (-1−1)(0)+(-1−1)(0)+(-1−1)(0) + (2)(1) +(2)(1)+(2)(1) + (-1−1)(0)+(-1−1)(0)+(-1−1)(0) = 6 pixels on the second row, second column in the (convolved image) starting from the upper left corner of the horizontal lines.<ref name=":0" /> page 82

== Example ==

{| class="wikitable sortable"

|

Line 149 ⟶ 148:

| -

|-

| -1−1

| -1−1

| -1−1

|

|

Line 177 ⟶ 176:

|

|-

| -1−1

| -1−1

| -1−1

|

|

Line 250 ⟶ 249:

The code was used to detect only the vertical lines in an image using Matlab and the result is below. The original image is the one on the top and the result is below it. As can be seen on the picture on the right, only the vertical lines were detected

[[File:Testbuilding.jpg|thumb|Original Image]]

[[File:LineImage.jpg.png|thumb|line detection]]

<syntaxhighlight lang="matlab" line="1">

clear all

clc

% this matlabMATLAB program will only detect vertical lines in an image

building = imread('building.jpg'); % This will upload the image building

tol = 5; % define a tolerance in the angle to account for noise or edge

% that may look vertical but when the angle is computed

% it may not appear to be

[~, angle] = imgradient(building);

out = (angle >= 180 - tol | angle <= -180 + tol);
%this part will filter the linesline

out_filter = bwareaopen(out, 50);

figure, imshow(crazybuilding), title('Original Image');

figure, imshow(out_filter), title('Detected Lines');

</syntaxhighlight>

Line 276:

[[Category:Image processing]]

__FORCETOC__