Hough transform

Hough transform is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Implement the Hough transform.

The transform maps each point in the target image, $(\rho ,\theta )$, to the average color of the pixels on the corresponding line of the source image (in $(x,y)$-space, where the line corresponds to points of the form $x\cos \theta +y\sin \theta =\rho$). 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 target space actually uses polar coordinates, but is conventionally plotted on rectangular coordinates for display.

A test image (.png) is located here.

Tcl

Library: Tk

If using PNG images,

Works with: Tk version 8.6

or

Library: TkImg

<lang tcl>package require Tk if {[catch {

   package require Tk 8.6; # Just for PNG format handler

}] == 1} then {catch {

   package require Img

}}

1. If neither Tk8.6 nor Img, then only GIF and PPM images can be loaded

set PI 3.1415927 proc HoughTransform {src trg} {

   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 #000000 -to 0 0 719 [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(th)+y*sin(th)=r 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} { incr totalPix 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 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} { incr totalPix 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 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 #000000 } lappend row $col } $trg put [list $row] -to 0 $rho update; # Strictly not necessary, but provides a measure of progress.

   }

}

1. Demonstration code

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] update HoughTransform srcImg targetImg puts Done</lang>