Hough transform: Difference between revisions
→{{header|Tcl}}: remove unnecessary debugging bits |
Convert to a task |
||
Line 1: | Line 1: | ||
{{ |
{{task}} |
||
Implement the [[wp:Hough transform|Hough transform]]. |
Implement the [[wp:Hough transform|Hough transform]], which is used as part of feature extraction with digital images. It is a tool that makes it far easier to identify straight lines in the source image, whatever their orientation. |
||
The transform maps each point in the target image, <math>(\rho,\theta)</math>, to the average color of the pixels on the corresponding line of the source image (in <math>(x,y)</math>-space, where the line corresponds to points of the form <math>x\cos\theta + y\sin\theta = \rho</math>). The idea is that where there is a straight line in the original image, it corresponds to a bright (or dark, depending on the color of the background field) spot; by applying a suitable filter to the results of the transform, it is possible to extract the locations of the lines in the original image. |
The transform maps each point in the target image, <math>(\rho,\theta)</math>, to the average color of the pixels on the corresponding line of the source image (in <math>(x,y)</math>-space, where the line corresponds to points of the form <math>x\cos\theta + y\sin\theta = \rho</math>). The idea is that where there is a straight line in the original image, it corresponds to a bright (or dark, depending on the color of the background field) spot; by applying a suitable filter to the results of the transform, it is possible to extract the locations of the lines in the original image. |
||
[[Image:Pentagon.png|thumb|Sample PNG image to use for the Hough transform.]] |
|||
The target space actually uses polar coordinates, but is conventionally plotted on rectangular coordinates for display. |
|||
The target space actually uses polar coordinates, but is conventionally plotted on rectangular coordinates for display. There's no specification of exactly how to map polar coordinates to a flat surface for display, but a convenient method is to use one axis for <math>\theta</math> and the other for <math>\rho</math>, with the center of the source image being the origin. |
|||
There is also a spherical Hough transform, which is more suited to identifying planes in 3D data. |
|||
A test image (.png) is located [[:Image:Pentagon.png|here]]. |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
{{libheader|Tk}} |
{{libheader|Tk}} |
||
If using PNG images, |
|||
⚫ | |||
⚫ | |||
<lang tcl>package require Tk |
<lang tcl>package require Tk |
||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
set PI 3.1415927 |
set PI 3.1415927 |
||
Line 45: | Line 37: | ||
set totalPix 0 |
set totalPix 0 |
||
# Sum the colors of the line with equation x*cos( |
# Sum the colors of the line with equation x*cos(θ) + y*sin(θ) = ρ |
||
if {$theta<45 || ($theta>135 && $theta<225) || $theta>315} { |
if {$theta<45 || ($theta>135 && $theta<225) || $theta>315} { |
||
# For these half-quadrants, it's better to iterate by 'y' |
# For these half-quadrants, it's better to iterate by 'y' |
||
Line 82: | Line 74: | ||
if {$totalPix > 0} { |
if {$totalPix > 0} { |
||
set totalPix [expr {double($totalPix)}] |
set totalPix [expr {double($totalPix)}] |
||
set col [format #%02x%02x%02x \ |
set col [format "#%02x%02x%02x" \ |
||
[expr {round($totalRed/$totalPix)}] \ |
[expr {round($totalRed/$totalPix)}] \ |
||
[expr {round($totalGreen/$totalPix)}] \ |
[expr {round($totalGreen/$totalPix)}] \ |
||
Line 93: | Line 85: | ||
$trg put [list $row] -to 0 $rho |
$trg put [list $row] -to 0 $rho |
||
} |
} |
||
}</lang> |
|||
} |
|||
⚫ | |||
Takes the name of the image to apply the transform to as an argument. If using PNG images, |
|||
⚫ | |||
⚫ | |||
<lang tcl># Demonstration code |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
set f [lindex $argv 0] |
set f [lindex $argv 0] |
||
image create photo srcImg -file $f |
image create photo srcImg -file $f |
Revision as of 13:57, 22 January 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Implement the Hough transform, which is used as part of feature extraction with digital images. It is a tool that makes it far easier to identify straight lines in the source image, whatever their orientation.
The transform maps each point in the target image, , to the average color of the pixels on the corresponding line of the source image (in -space, where the line corresponds to points of the form ). The idea is that where there is a straight line in the original image, it corresponds to a bright (or dark, depending on the color of the background field) spot; by applying a suitable filter to the results of the transform, it is possible to extract the locations of the lines in the original image.
![](http://static.miraheze.org/rosettacodewiki/thumb/c/c6/Pentagon.png/300px-Pentagon.png)
The target space actually uses polar coordinates, but is conventionally plotted on rectangular coordinates for display. There's no specification of exactly how to map polar coordinates to a flat surface for display, but a convenient method is to use one axis for and the other for , with the center of the source image being the origin.
There is also a spherical Hough transform, which is more suited to identifying planes in 3D data.
Tcl
<lang tcl>package require Tk
set PI 3.1415927 proc HoughTransform {src trg {fieldColor "#000000"}} {
global PI
set w [image width $src] set h [image height $src] set targetH [expr {int(hypot($w, $h)/2)}]
# Configure the target buffer $trg configure -width 360 -height $targetH $trg put $fieldColor -to 0 0 359 [expr {$targetH-1}]
# Iterate over the target's space of pixels. for {set rho 0} {$rho < $targetH} {incr rho} {
set row {} for {set theta 0} {$theta < 720} {incr theta} { set cos [expr {cos($theta/180.0*$PI)}] set sin [expr {sin($theta/180.0*$PI)}] set totalRed 0 set totalGreen 0 set totalBlue 0 set totalPix 0
# Sum the colors of the line with equation x*cos(θ) + y*sin(θ) = ρ if {$theta<45 || ($theta>135 && $theta<225) || $theta>315} { # For these half-quadrants, it's better to iterate by 'y' for {set y 0} {$y<$h} {incr y} { set x [expr { $w/2 + ($rho - ($h/2-$y)*$sin)/$cos }] if {$x < 0 || $x >= $w} continue set x [expr {round($x)}] if {$x == $w} continue incr totalPix lassign [$src get $x $y] r g b incr totalRed $r incr totalGreen $g incr totalBlue $b } } else { # For the other half-quadrants, it's better to iterate by 'x' for {set x 0} {$x<$w} {incr x} { set y [expr { $h/2 - ($rho - ($x-$w/2)*$cos)/$sin }] if {$y < 0 || $y >= $h} continue set y [expr {round($y)}] if {$y == $h} continue incr totalPix lassign [$src get $x $y] r g b incr totalRed $r incr totalGreen $g incr totalBlue $b } }
# Convert the summed colors back into a pixel for insertion into # the target buffer. if {$totalPix > 0} { set totalPix [expr {double($totalPix)}] set col [format "#%02x%02x%02x" \ [expr {round($totalRed/$totalPix)}] \ [expr {round($totalGreen/$totalPix)}] \ [expr {round($totalBlue/$totalPix)}]] } else { set col $fieldColor } lappend row $col } $trg put [list $row] -to 0 $rho
}
}</lang>
Demonstration Code
Takes the name of the image to apply the transform to as an argument. If using PNG images,
or
<lang tcl># Demonstration code if {[catch {
package require Tk 8.6; # Just for PNG format handler
}] == 1} then {catch {
package require Img
}}
- If neither Tk8.6 nor Img, then only GIF and PPM images can be loaded
set f [lindex $argv 0] image create photo srcImg -file $f image create photo targetImg pack [labelframe .l1 -text Source] [labelframe .l2 -text Target] pack [label .l1.i -image srcImg] pack [label .l2.i -image targetImg]
- Postpone until after we've drawn ourselves
after idle HoughTransform srcImg targetImg</lang>