Radon Transform


Wow, it’s been a rough couple of weeks: I had to hand in my graphics project, study for a statistics test, fighting off my allergies (I hate spring) and then I had to study for my finals. At least I have my degree now.

Finally!  

Anyways, I promised I’d write about the radon transformation I used to convert from the extracted images to a numerical format suitable for input into our neural network. This technique is extremely effective and is already used in industry for just such purposes.  We tested it on demo day with very minimal data and it worked remarkably well.

Before I get knee deep in the technical aspects of the system, I need to mention this: due to the preprocessing done on the motion detected, there is no need for a complicated AI system; the radon transformation and the recursive feature extractor together remove a lot of noise and problems that may have been present otherwise. The radon transform especially helps as we have built in scaling so this does not have to be taken into account later on. Also from the results of the transformation, objects similar in shape have extremely similar radon transformations so the training time of the neural network was reduced as was the amount of hidden neurons necessary.

In the final demo we used a neural network with 408 inputs and only 4 hidden neurons, scary isn’t it.😛

Introduction:

Now back to the nitty gritty: the radon transform. If you Google the “radon transform” you’ll probably get the Wikipedia page with a scary looking equation.  I also got a fright the first time I saw this but after some research it’s really simple.

The basic idea of the radon transform (or my modified version thereof) is simple: if you look at your 2D image in the XY plane, you simply flatten the image onto the X axis (figure1), then divide the X axis into several beams and you work out the amount of pixels within each beam. Your output will be the pixel contributions of the object to each beam.  Then you’d rotate the object and flatten it once again. Doing this for multiple angles will give you a very good representation of the objects shape.

 

rfig1.jpg
Figure 1

The most basic (and unfortunately most commonly used technique) for image classification is to simple get the centroid of the object and then trace the outline of the object giving you a silhouette. Now this doesn’t sound so bad does it? Well, it is firstly it doesn’t handle broken up images well (not without major preprocessing or modification) and it also loses a lot of detail and can provide false matches. In figure1 below we have the radon transform of a solid circle and a hollow circle, a standard outline trace would provide the exact shape result for these obviously different shapes while as you can see the radon transform (in one projection) provides completely different results.  Again this pre-processing will take the strain of the neural network (or other AI technique we’ll use for classification).

 

 

rfig2.jpg
Figure 2

Okay now for the technical details: as you remember we flatten the image according to some projection. Figure2 shows some of these projections. Now if you look at figure 2 you might notice that the now flattened image’s top border can be seen as a graph of some function, so the amount of pixels in a beam is the approximate area under the graph between the left and right end points of the beam.

Now that picture is misleading as you might think that that it is a square object that we’ve rotated and flattened, but it is in fact a single pixel. The algorithm works on a per pixel basis. Instead of actually flattening the object, we simply work out the equation of the graph for a single rotated pixel and then use that to run through all the pixels in the object, work out the left most and right most and then add them to their respective beams.  

Now some of you are screaming that if we just rotate the pixels it will be wrong as we aren’t rotating the entire object but that is taken into account later on.

Now how do we calculate the area under the graph for each pixel and how do we figure out what beam to add it to since a beam will have lots and lots of pixels in it? Also the beam widths will differ per object.

 

rfig3.jpg
Figure 3

What we do is simply divide the beams into lots of sub-beams, so that multiple sub-beams pass through each pixel. Then for each pixel we work out the left most sub-beam and the right most sub-beam that passes through the pixel. This then becomes the domain for the equation of the graph we have earlier and we loop through each sub-beam, calculate the pixels contribution to it(the area under the graph) and then add it to the sub-beam total. This is shown in figure 3. What you also notice from figure 3 is that there is a small degree of approximation to reduce the calculations required for the area, but remember that we’re talking about fractions of a pixel here so the total error in approximation can easily be ignored.

Now for each projection we run through each pixel and add it to the appropriate sub-beam. Once this is complete we sum the sub-beams up into the initial amount of beams and then we divide each beam by the scaling factor. The scaling factor is simply the total pixels over the beam width; this reduces the total area for the beams to 1. So every object gets reduces to an n-beam representation where the sum of all beams is equal to 1.

Okay, my explanation is very basic and I’m sure mathematicians would point out various mistakes and so on , but I’m trying to make this easy to understand and to follow, it is not meant as a 100% mathematically accurate explanation, obviously if you wish to implement something like this, you wouldn’t only use my guide here as a reference. I’ve also left out some details but they should become apparent from the below explanations.

I’m struggling to find a good way to structure this guide so I’m just going to run through the algorithm simply just to finish off. 

Preparation:

The first steps we need to take before we can process the object is to get the total number of pixels, work out the centroid and the approximate radius of the object. Using the radius we work out the amount of beams and sub-beams we need for the transformation. Remember that we want several sub-beams to pass through each pixel.

Projection:

Now we run each of our projection functions to calculate the sub-beams totals. I’ll run through the basic procedure for a  projection:Work out the center of the pixel on the new axis (this where the rotation of the object comes into play)Work out the left most and right most sub-beams that pass through the pixel.For each sub-beam add the pixel’s contribution to it.

Note: For some equations there is an incline to the graph and so this needs to be calculated too, and processed separately. I.e. Work out the left most and right most sub-beams for the increasing incline and the decreasing incline and then using that work out out all the section separately.

Combine Sub-beams:

Now once all the sub-beams have been calculated, we work out the scaling factor which is: beamWidth /numPixels. We then sum all the sub-beams into beams (per projection) and multiply each one by the scaling factor. And that’s it. We have our complete numerical representation of our image.

Note: I used only 8 projections as I had very limited CPU time left at this stage of the project and had to limit the amount of processing that needs to be done, obviously more projections will be better but then again too many would be worse. A fine balance needs to be found, I personally think that 8 projections are more than sufficient for my needs. Again GPGPU programming would be so useful here!

C++ Source Code: https://github.com/BobbyAnguelov/RadonTransformer

22 thoughts on “Radon Transform

  1. I found your site by googling radon transform. I am interested in it for a “line finding” application. I was also interested in the neural net references. I did some work off and on with neural nets, mostly the CMAC. The similarity between the Radon Transform and the line activated neurons in the optical area of the brain immediately struck me when I looked at the Radon Transform. I tried it on some example images in MatLab and it looks at least interesting. I also had the same reaction to the spooky looking equation that I found online. Because I do a lot of numerical programming, I usually find that these things boil down to something a lot more tractable than these arcane looking mathematics.

  2. hello Bobby Anguelov
    Thanks a lot
    your blog is very informative for me
    i am also working on image reconstruction using fan beam.
    i have one problem can you help me.
    i have imageJ plugin for radon transform but i am not able to understand some points in it.
    do you have documentation for that plugin or some notes for that
    please send it to me at my mail
    i shall be very thankful to you for this
    thanks again

  3. I didn’t use imagej, my radon transformation is based off of a research paper wherein they used it for accurate signature verification.

    My c++ source code is available here, perhaps reading through that might help, as i tend to overcomment everything…

  4. thank for your source code. i have downloaded it but i don’t know how to use it. Can you explain what is Vector and how i convert my image to Vector ? thanks again

  5. Bobby,

    Thanks for your explanation of the RT; nice to have visited! If I ever need your source code I’ll be sure you are acknowledged.

  6. Thanks for the explication but I would like to get more information that you had recolect from internet about Radon Transformation, I’m not expert in this theme, I would like to receive some help from you. I also see the equations of wikipedia and I get scared😦, I hope we can get contact, Have a nice day bro

  7. thanks. this is a great post. i have downloaded your source code to use it for a shape matching algorithm. i know you have written this a while back but i was hoping you could help me out with a couple of things-
    1) how do you calculate projection (or contribution) from each pixel for any given angle? (i.e calculation of left/right corner of pixel, length of inclination and contribution). is it possible
    to come up with a generic function which takes point and angle and calculates it’s contribution? (i am trying to do this for many more angles)
    2) is there a reason to use 51 beams?

    thanks,
    tj

  8. i will willingly make a donation if i end up using your code. but first i will need to understand how to calculate contribution for different angles.

  9. dear friend i m the student of BSCS and doing the project on odject detection and identificatiion……. i need ur help plz……i need hough and radon transformation in my project….i visited your site i found here radon transforamtion.h file ut cant found its CPP file…..can u plz send me that file on my id :luqmansky@gmail.com…….i will be so thankfull to u if sent it…and also if u hav hough transfomation.cpp file than plz also send it on id…or tell me the link from where i can easily download it….
    i reaallly appriciate ur work it was excellent…
    with regards
    Luqman

  10. hi,

    i’ve got the same problem as luqman. I need to track vehicles and calculate their speed. I also read some scientific papers for solution.
    luqman i will send hough transform code to ur id.
    i’ll try it out. thank you so much for this. this is very helpful.

    thanks,
    larun

  11. Hi, how do we feed: vector object before executing the transformation?
    Where is the pixel value and how can i copies my char pixels value from my image intp vector object?thanks for your help
    Benoit

  12. Hello bobby , i was wondering if you could help me , i have a project to be completed in two month in which i have to calculate the speed of vehicles using openCV( camera based) and display it a google map , using google api , eg, if speed is belo 30km on a certain road, it will be painted red , i’m really desperate , i’m trying to learn C++ to do this

  13. Hi, bro.

    I downloaded your Radon code. Thanks for sharing. When I used this one, I got one problem and could not solve it until now. If I have one image as 1.jpg, then I think if I use it as transform(projection), it should work. Where I defined IplImage *projection = 0, projection= cvLoadImage(“1.jpg”,0). Can you tell me where am I wrong? Thanks for your help in advance.

  14. Hi, bro.

    I downloaded your Radon code. Thanks for sharing. When I used this one, I got one problem and could not solve it until now. If I have one image as 1.jpg, then I think if I use it as transform(projection), it should work. Where I defined IplImage *projection = 0, projection= cvLoadImage(“1.jpg”,0). Can you tell me where am I wrong? Thanks for your help in advance.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s