LabVIEW

cancel
Showing results for 
Search instead for 
Did you mean: 

Calculating euclidian distance faster

Solved!
Go to solution

Hello,

 

I tried to built a VI that calculates an euclidian distance transform on a binary 2D-Image.

 

The VI looks like this:

 

transform03.png

 

So for every black pixel it calculates the distance to every other pixel and then selects the smallest distance. 

 

And it works just as it should, the following input results in the following output:

 

circle-512.png distanceTransform.png

 

Just as it should. However it is extremely slow. It took about 340 seconds for this 512x512 image. I believe the runtime is O(n^4). I've seen algorithms (in C) doing this in O(n), but I do not know how to implement these in LabVIEW. Is there a simple yet nice way to speed it up?

 

You can find the VI attached. Thanks in advance.

 

0 Kudos
Message 1 of 17
(4,331 Views)
if you have vision toolkit
you can check IMAQ Danielsson and
IMAQ Watershed both work with calculation of euclidean distance
but if you do not have you can do some work to reduce time of calculation
for example there is no difference to calculate i and j pixel with j and i so you need to calculate just one of them it reduce time to half
0 Kudos
Message 2 of 17
(4,322 Views)

First of all, I assume that the real data is much less symmetric, because if you know that you have a filled circle of a give radius, you can do all calculations using trivial geometry. Overall, your code seems convoluted. Can't you combine the sequential inner loops?

 

Yes, just iterating over all data will be slow, because there are so many comparisons, so you simply need to be smarter.

For example if the given pixel is black, no other pixel even needs to be checked and you can terminate the inner loop (you already do that). If it is white, you can go along circles of increasing radius centerend at the current pixel and again terminate the inner loop once you find a black because all other pixels will be further away. There will be additional correlations reducing the calculations even more, for example if you found a distance, the distance from the next pixel has an absolute minimum as the last measured distance -1, so you also don't need to measure any closer pixels.

Message 3 of 17
(4,303 Views)

Sadly I do not have IMAQ installed.

 

@altenbach: You are absolutely right about the inner loops, did not see that. The other tips are also quite nice. 

0 Kudos
Message 4 of 17
(4,290 Views)

You could speed up your code significantly, if you used sgl instead of dbl as datatype for the distance value.

2016-05-22_sgl.PNG

Message 5 of 17
(4,258 Views)

Furthermore, if you used "index and replace array" instead of auto-indexing to updtae the distance buffer, this will also be significantly faster.

 

2016-05-22_auto-index.PNG

 

like this:

2016-05-22_index-replace.PNG

 

 

 

 

Message 6 of 17
(4,247 Views)

@alexderjuengere wrote:

You could speed up your code significantly, if you used sgl instead of dbl as datatype for the distance value.

2016-05-22_sgl.PNG


Just to the right of the right most yellow circule.  That whole less than, selectt combo could be replaced by the Max & Min function.

Message 7 of 17
(4,236 Views)

@joelsa wrote:

 

@altenbach: You are absolutely right about the inner loops, did not see that. The other tips are also quite nice. 


Sorry I was on the road, but here's somewhat cleaned up code using your slow algorithm, just to give you some ideas how to cleanup things. It is still slow for 512x512 (~300s on my laptop when not parallelized).

 

Also remember that you can parallelize the outer loop, giving you a proportional speedup depending on the number of available cores. (Sorry, I only have a dual core laptop, but the speed for 256x256 doubled (from ~19s to 9.5s).

 

Also note that you can use an 8 bit paletted image. You can reverse the colors instead of doing (255-x)

 

(As long as the radius is less that 256, you could also do the entire thing in U8. Only the complex parts should be orange) 

 

 

 

Anyway, this is all pretty pointless, because you need a more intelligent algorithm. Is the size always the same?

I would probably do a lookup table of relative coordinate distances. You should never have to compare more than about one circle per pixel.

 

 

 

 

Download All
Message 8 of 17
(4,225 Views)

Ok, I implemented some of my ideas and got a version that does 512x512 with one big circle in under 3 seconds. (This is really the worst case scenario, for example if there are a couple of smaller circles it is significantly faster.)

 

Maybe I attach it later.... 😄

0 Kudos
Message 9 of 17
(4,205 Views)

Thank you very much for those hints. I'm pretty new to LabVIEW and still impressed what this (rather unknown outside the world of engineering/science) programming language is capable of, especially when used by an experienced programmer. I got the time down to ~150s for the 512x512 image on my Quadcore processor. Merging the inner loops alone brought 60 seconds.

 

@altenbach Sharing your VI would be much appreciated as I understand the correlations you are talking about, but do not have a clue on how to implement those. So if you would share it, I could learn how an experienced programmer would do this. (Looking at other people's code is actually the best method to learn IMHO)

0 Kudos
Message 10 of 17
(4,178 Views)