Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

Highlighted

05-22-2016 07:34 AM

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

Hello,

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

The VI looks like this:

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:

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.

Solved! Go to Solution.

05-22-2016 08:07 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

05-22-2016 10:15 AM - edited 05-22-2016 06:08 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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.

05-22-2016 10:44 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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.

05-22-2016 04:23 PM - edited 05-22-2016 04:51 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

05-22-2016 04:44 PM - edited 05-22-2016 04:50 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

like this:

05-22-2016 05:33 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

@alexderjuengere wrote:

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

05-22-2016 06:35 PM - edited 05-23-2016 10:48 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

@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.**

05-22-2016 09:25 PM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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.... 😄

05-23-2016 03:35 AM - edited 05-23-2016 03:37 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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)