I propose we implement the Hough transform for RosettaCode
http://rosettacode.org/wiki/Hough_transform
The version in this message seems to work given an array but
lacks .png IO.
Also, the discovery of "interesting data" is hard-coded to
agree with the test data.
b =. 0 < ,y NB. repair this decision for rosettacode data
Background:
Rosettacode challenges us to write in J the Hough transform of a
picture of a pentagon composed of five black line segments on a white
background given in portable network graphics format.
In multi-dimensional Hough space the axes correspond to parameters
describing a figure. Slope and intercept describe a line, thus the
corresponding Hough space has slope and intercept axes. A point in
Hough space corresponds to a figure in Cartesian space. Conversely, a
Cartesian point lies on all intersecting figures forming a curve in
parameter space. 3D Hough space describes circles if the parameters
are center and radius. To perform the discrete Hough transform make
an accumulator grid having rank of the number parameters of the target
figure. For all interesting points in the picture increase the values
of the accumulator cells to which that point could belong. Co-figure
points combine in the same Hough cell producing a local extreme. Two
parameter figures can be displayed as an image. An edge detector
would select as regions of interest those with high intensity
gradient. This information can also improve algorithmic efficiency.
The challenge demands the
transformation of a picture into Hough space using line detection.
The slope and intercept of near vertical lines can be large. Rather
than applying additional transformations (arctangent works well) to
make these fit a small rectangular space, the usual Hough
representation of a line records in polar coordinates the line's
distance from an origin. A quick sketch reveals an unique vector
perpendicular to the line. In this implementation we choose the
origin at data center. The orthogonal vector has Hough radius in
magnitude up to half the picture's diagonal. Angular range:
$[0,\pi)$. The C program offered by rosettacode on 2010-AUG loops
over parameter space and adds the pixel values of the corresponding
line of the picture. The J implementation instead will loop over the
picture and, for interesting sites only, find the possible
corresponding regions of parameter space. Let $\vec{P}, \vec{I}$
respectively represent the interesting point in the picture and the
intersection with the distance vector.
Scalar product of 2 vectors gives the RosettaCode formula.
The dot product in J code uses homogeneous coordinates for centering,
converts from left handed coordinate system to right handed,
and determines radius for each angle.
data =: (+. |."1)(+. |.)(= +. (=/ 2&*))i.111 NB. dotted & `solid' lines
display =: (' .-+m%*#@' {~ [: <. (* (8.9 % >./@,))) : [:
grid =: 0.5&% + i. % ] NB. example below
length =: +/"1&.:*:
hough =: 4 : 0 NB. centered about picture center
NB. N_radii N_angles hough 2D_data
radii =. (>:length>:$y)*_0.5+grid {. x NB. -/+half diagonal
angle =. 1r1p1*grid {: x NB. angles 0 to pi
b =. 0 < ,y NB. repair this decision for rosettacode data
inter =. b # , y NB. interesting values
coord =. ($y) #: I. b NB. Cartesian coordinates
rhoug =. (coord,.1)+/ .*(1 0,0 _1,:_0.5 0.5*$y)+/ .*1 2 o./angle
phi =. i. {: x
r =. (<:@# - I.&rhoug)radii NB. careless conversion to integer
accum =. zeros =. 0 $~ 0 _1 { x
for_i. i. # inter do.
accum =. accum(+ (i{inter)&((<"1 phi,.~i{r)}))zeros
end.
)
grid 5
0.1 0.3 0.5 0.7 0.9
display 30 hough data NB. radius vertical, angle horizontal
.
. ... .
.. .... ..
... . ...... ...
.... ... ........ .. ....
...-m-.. ........ ...---...
..--.-. . .......... ..-+-...
.....-.. .-........-....-.....
.........--........-- ........
......+.m-..........-+.+......
.......@+--.........-+@+......
......+.m-.........--+.+......
.........-..........-.........
.....-.. .-........-- ........
...-.-. .........- ...-.-...
...-m-.. ........ ..-m-...
.... ... ........ ... ....
... . ...... . ...
.. .... ..
. .. .
.. .
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
