Hoppa till huvudinnehållet
Institutionen för informationsteknologi

Efficient windowed 2D Radon transform

Windowed Radon transform is a popular approach for detecting lines in 2D images. A problem with this approach is the computational cost, in particular for long line lengths. The cost function is something like this: O(m*n*p*q), for an image with m*n pixels, and we are looking for lines of length q, for p angles. Often p=q, and then the cost function then becomes O(m*n*q^2). So, obviously the runtime increases in a quadratic sense with line length, which is unfortunate when we are looking for long line segments.

There is an idea for changing the implementation, which will (if it works) make the runtime linear in q, which obviously will have a great practical impact for our work. If this approach has not been done before, Schlumberger needs to submit a patent application before the exact approach is disclosed to Uppsala, but that can be done very quickly. A part of this project will be to investigate if similarly efficient algorithms already have been implemented.


The improvement is thought to be intuitive to understand, but perhaps a bit tedious to implement. The implementation needs to be done in either C, C++ or C# language, and there needs to be a focus on compute speed/efficiency.

Supervisor: Victor Aarre

Uppdaterad  2010-02-26 15:31:49 av Maya Neytcheva.