Bug introduced in 9.0.0 and fixed in 9.0.1

I want to get a Hough transform of some edged image.

When I compare the same transformation on the same image I got different results.

i = 0; While[i < 10, i++; Print[Radon[imgEdged, Method -> "Hough"] ==
True
True
True
False
True
True
False
False
False
True


Why isn't repeatability provided in result of this function?

Update:

imgEdged =

-
Hi jhilary, welcome to Mathematica.SE! Could you please consider uploading your imgEdged so others can have a full view on your question? – Silvia Dec 29 '12 at 14:31
I cannot test this (Radon is new) but you may try setting e.g. SeedRandom[1] before every use of Radon in case the latter makes use of random numbers without using BlockRandom (which also might be applicable). – Mr.Wizard Dec 29 '12 at 14:42
I find Radon[] is giving consistent results for a set of test images in MMa 8.0 Perhaps your particular image has some particularity. Please post a link to it. – Dr. belisarius Dec 29 '12 at 15:08
I get a different Radon transform every time... !Mathematica graphics – chris Dec 29 '12 at 15:40
I tried post image in question, but they said that not enough reputation i.stack.imgur.com/UeSlT.jpg – jhilary Dec 29 '12 at 15:46

I think I found more hints on what might explain the fact that Hough gives different results each time it is called. But this is too small to fit in a comment.

This is assuming the implementation by Mathematica is as explained in the Wikipedia article for Hough transform. The Hough implementation uses (from the link)

The Hough transform algorithm uses an array, called an accumulator, to detect the existence of a line $y = mx + b$

Then later on it says:

the number of page swaps required for this will be very demanding because the accumulator array is used in a randomly accessed fashion

Notice the word randomly accessed. This is the key.

It seems to work in a fashion similar to Monte Carlo method for numerical integration in the sense only that it uses randomness to do its work for speed vs. quality.

But since using SeedRandom[1] did not resolve the differences between calls as can be seen here:

With[{imgEdged = Image[CellularAutomaton[30, {{1}, 0}, 40], "Bit"]},
Reap[Do[
SeedRandom[1];
im1 = Radon[imgEdged, Method -> "Hough"];
SeedRandom[1];
im2 = Radon[imgEdged, Method -> "Hough"];
Sow[im1 == im2], {i, 100}]]
]


My guess now is that Radon[], or the function that implements the Method->Hough does not use the same random number generator that SeedRandom[] resets (the global one), but its own, in the Kernel, and it forgets to reset its own at random number generator at start of each call? Just a guess, since nothing else seems to make sense ;)

You might also want to look at Randomized Hough transform

-
The link you shared mentions this — Hough generally uses polling and binning, and I presume it uses a random initialization each time. – R. M. Dec 29 '12 at 17:27
Interesting. I still get True always i.stack.imgur.com/a4Y6b.png – Dr. belisarius Dec 29 '12 at 20:18
@NasserM.Abbasi Mma 8.0 on WinXp – Dr. belisarius Dec 30 '12 at 5:45
I'm not convinced on the "random access" point. In computer engineering this simply means that the access pattern is not predictable by memory controller, not literally that the access occurs at a randomly chosen point. Basically it is the antonym of "sequential" in this context, although modern processors can predict some nonsequential access patterns as well. – Oleksandr R. Jan 2 '13 at 20:11

That was a bug which got fixed in Mathematica 9.0.1.

-

Thanks to @Nasser I search about probablistic hough transform. Maybe it used in Mathematica implementation for speeding-up. I found good explanation here: http://www.cvmt.dk/education/teaching/f09/VGIS8/AIP/hough_09gr820.pdf

The Hough transform is not a fast algorithm for ﬁnding inﬁnite lines in images of a certain size. Since additional analysis is required to detect ﬁnite lines, this is even slower. A way to speed up the Hough Transform and ﬁnding ﬁnite lines at the same time is the Progressive Probabilistic Hough Transform (PPHT). The idea of this methood is to transform randomly selected pixels in the edge image into the accumulator. When a bin in the accumulator corresponding to a particular inﬁnite line has got a certain number of votes, the edge image is searched along that line to see if one or more ﬁnite line(s) are present. Then all pixels on that line are removed from the edge image. In this way the algorithm returns ﬁnite lines. If the vote threshold is low the number of pixels to evaluate in the accumulator gets small

And important part:

An issue with this algorithm is, that severel runs may may yield diﬀerent results. This can be the case if many lines share pixels. If two lines cross, the ﬁst line to be detected removes the common pixel (and a band around it) resulting in a gab in the other line. If many lines cross, then many pixels can miss in the last lines, and the votes in the accumulator may not reach the threshold.

So If you want after hough transform get expected lines, I think it's not very useful use hough transform (ImageLines function use Hough transform method inside (or RANSAC, which is randomized too)).

For example OpenCV hough lines provide choice which algorithm used in lines' search.

-