Need Way to calculate Line-of-Sight through Terrain that is faster than los2

Hello,

My code calculates among other things the Line-of-sight from multiple points in an aircraft orbit to a target on the ground. To do this I enter arrays of coordinates into los2. Everything works accurately but the runtime is just unacceptable. To do one orbit against one target takes about 20 seconds. This code will be used with others to test the suitability of several orbits against several targets. Those 20 seconds add up quickly and I'm looking at a code that takes an hour to run a simple case.

Has anyone experienced this slow of a runtime with los2? Is there an alternative method (and/or function) that would be faster than los2?

Any suggestions are welcome!

[MCM]

I want to clarify that los2 is Matlab function from the Mapping Toolbox. Running thousands of points through los2 is the bottle neck, every other portion of the code runs in fractions of a second.

I need a way to calculate line-of-sight using DTED terrain data that is faster than los2

Answer 1

[Kelly Kearney]

If you profile a simple example, you'll see that nearly all the computation time of los2 is being spent on the cummax subfunction. There is a built-in cummax.m function, but for some reason (probably legacy), the los2-called function calculateLOS.m has it's own local non-builtin version of cummax that's much, much, much slower than the builtin. I opened the calculateLOS.m file (<matlabroot>/toolbox/map/map/private/calculateLOS.m) and commented out the cummax subfunction at the very end; an los2 call speeds up dramatically after that (I haven't double-checked to make sure the results are the same, so you should definitely do that, though).

The Mapping Toolbox, unfortunately, is full of little inefficiencies like this one, which aren't very noticeable when running toy examples but really add up when trying to apply them to complex datasets.

[MCM]

Thank you so much for responding!! I'd love to give this a try but I don't have the calculateLOS.m file. Plus I don't have the permission to edit any files in the "map/private" folder. Instead, I created a new function los2FAST which is just a copy/pasted the original los2.

At first los2FAST threw errors because it was using other functions in map/private folder. So, I just copy/pasted those functions into los2FAST as subfunctions. Now it runs just like los2.

However, when I try to comment out cummax, I get an 'undefined function' error. I think I just need to replace the cummax subfunction in los2FAST with a copy/paste of the built-in cummax. Do you know what file that is in? I can't find it.

Thanks

[Kelly Kearney]

Which version of Matlab are you running? It looks like the cummax builtin was introduced in R2014b, so you'll have to be running a recent version of Matlab to get this working. The los2 function itself has changed quite a bit over the last few releases too; I'm surprised they haven't gotten rid of the slow cummax.m subfunction in all those updates.

Also, I recommend this modified function_handle function when you're trying to create custom functions that need access to private directories. At the beginning of you los2FAST function, add a line like

privatefun = function_handle(fullfile(matlabroot, ...
             'toolbox', 'map', 'map', 'private','privatefun.m');

That way you'll be able to keep the calls to privatefun, and incorporate future updates without having to recopy and repaste code.

[MCM]

Turns out cummax was introduced in R2014b. I was working R2014a which is why I couldn't find it. I updated to the latest version of Matlab 2015a. And surprise, los2 no longer has the cummax subfunction (in fact all the subfunctions are different). In R2015a los2 runs significantly faster ( yeah, happy dance!). Previously, processing 100,000 point pairs took 317 seconds in R2014a. Now in R2015a it takes 92 seconds. I still have to be strategic with my code but huge improvement.

Thank you so much for your post!

[Sean de Wolski]

If you're bored, give the 15b prerelease a try too :)

[Kelly Kearney]

I'm confused... I'm running the 2015b prerelease, and the slow cummax subfunction is still in there (in toolbox/map/map/private/calculateLOS.m, not the main los2.m), so you should be able to get even more speed out of things by commenting that out. On my computer, that brought a 1000-point test from 18.225517 sec to 0.414691.

[MCM]

Yep, you are right. 2015a still has the slow cummax subfunction. I was looking in los2 and not calculateLOS. Made the change you suggested and WOW what a difference. Thanks!!!

Answer 2

[amberly hadden]

Hi-- The one way to speed up such simulation is to define your output matrices or vector before loop. You can use for instance you want displacement from such observation du = zeros(m,n); dh= zeroes(m,n);....so on

tic for i = .... ...... ..... end toc

sorry if I misunderstood your question

[MCM]

Thanks for replying! While a good suggestion in general, your answer doesn't apply because I don't use a loop. I tried looping by calculating line of sight from each orbit point to target one at a time just to see if that was faster. But that was twice as slow (no surprise with Matlab).

What I do is create 4 arrays; oblat,oblon,tgtlat,tgtlon. oblat and oblong have an entry for every orbit point. tgtlat and tgtlon are just the target's lat/lon position repeated. These are my inputs to los2. The output is the array, vis, whose value is 1 if the orbit point has line-of-sight to target and 0 o.w.

This works great for small arrays. But for my purposes, I'm testing 7,000 points at once (aka 7000 x 1 array inputs) and it takes 20+ seconds. (Looping took over 40 seconds)

Answer 3

[Sean de Wolski]

You could consider using the Parallel Computing Toolbox to calculate multiple lines-of-sight at the same time with parfor or parfeval

[MCM]

Great Suggestion! I gave it a try and it did cut down the run time. But not to an acceptable level. I tried running a 28,000 array (a basic example of 1 of 500 I'd need to do) and it took 90 seconds normally and 55 seconds with parallel computing. Good start but still not enough.

The lesson learned here is that los2 is the bottle neck. The function just takes too long to run. Every other part of the code processes 28,000 lines in fractions of a second.

[MCM]

Previously I tried parfor and now I want to see if parfeval gives me any different time savings. Unfortunately, I'm having issues running it. Below is my code for testing.

Lat=32*ones(1,N);
Long=-118*ones(1,N);
tgtlat=34*ones(1,N);
tgtlon=-116*ones(1,N);
alt=20000*0.3048*ones(1,N);
tgtalt=zeros(1,N);
tic
p=parpool(4);
f=parfeva(p,@los2,Topo,RefVec,Lat,Long,tgtlat,tgtlon,alt,tgtalt);
vis=fetchOutputs(f);
delete(p)
parallel2=toc;

When I run this I get an error. What am I doing wrong?

[Sean de Wolski]

You're not using parfeval correctly. What is Topo? That should be the number of outputs. Also, for parallel computing, you could not include the opening and closing of the pool in the computation cost since this is a one time thing that can remain open (no reason to close the pool unless you need to free up resources).

Also, depending on how many times you have to do this, scaling the parallel work up to a cluster or cloud with MDCS or MATLAB Compiler might be an option. How many times do you have to run this?

[MCM]

Good news, I updated to R2015a and los2 now runs about three times faster than when I had R2014a.

I tried using parfor in R2015a to see if I could get even more time savings but it actually ran slower. Process 100,000 point pairs took 90 seconds using los2 and 136 seconds with los2 in a parfor loop.

My guess is that it ran slower because parfor is a loop. Would parfeval run faster since it isn't a loop? If yes, then please tell me how to fix the aforementioned error. If not, let me know so I can ditch the parallel computing idea.

Thanks