Removing data from a structure that is less than a certain threshold

I am running a code to find the positions and trajectories of microparticles. I get a lot of noise as my particle concentration is quite dense. The false positives slow down my code significantly so I want to get rid of them every loop so I have made the following code:

c=1;
while c <= length(AllTraj.Passive)
    if ((length(AllTraj.Passive(c).T) <= 10) && ...
            (max(AllTraj.Passive(c).T) < (i-2)))
        AllTraj.Passive(c) = [];
    else
        c=c+1;
    end
    c
end

AllTraj.Passive represents a struct with my connected particle trajectories each with time (T), X and Y values.

I want to get rid of any particles (rows) which have a trajectory of length 10 or less if they are no longer being tracked in the current frame (i-2 is current frame).

This code seems to run very slowly when I have a lot of particles and when I clear the rows which meet the criteria.

Is there a faster way to remove data that is less than a threshold time?

Thanks

Answer 1

[Jan]

The iterative growing and shrinking of arrays is extremely expensive. Better:

nTraj  = numel(AllTraj.Passive);
remove = false(1, nTraj);
for c = 1:nTraj
    tmp       = AllTraj.Passive(c).T;
    % [EDITED: remove -> remove(c)]
    remove(c) = (numel(tmp) <= 10) && (max(tmp) < (i-2));
end
AllTraj.Passive(remove) = [];

Remember: To create a growing array, e.g.:

x = [];
for k = 1:1e6
    x(k) = rand;
end

Matlab has to reserve sum(1:1e6)*8 bytes in the RAM and copy almost the same amount of memory. This is 4 TeraByte, although the final array has 8 MB only. Of course this is slow.

The solution is a pre-allocation:

x = zeros(1, 1e6);

Or in your case to collect the indices to remove at first and remove them in one step after the loop.

[Manny Kins]

Hi Jan thank you for your time and help. Pre-allocation sounds like a good idea but it may be hard for me to implement as I never know the final size of my arrays. I could over allocate and then chop at the end though! I also use a minimum distance search to add new co-ordinates onto my X and Y arrays so creating a pre-allocated matrix of zeros may not be ideal. I can maybe try making pre-allocated NaN arrays instead?

For the code that you sent, (maybe I am being stupid and not seeing something) but is the

AllTraj.Passive(remove) = [];

part meant to be before the end? If I put it before the end I have the same issue as the one I mentioned to Guillaume in that I get an error saying 'Index exceeds matrix dimensions'. This is because maybe we are removing rows from AllTraj.Passive and hence it is getting smaller and smaller.

[Manny Kins]

Ah sorry I get it now, I can just index the part:

remove = (numel(tmp) <= 10) && (max(tmp) < (i-2));

into

remove(c) = (numel(tmp) <= 10) && (max(tmp) < (i-2));

and then use

AllTraj.Passive(remove) = [];

after. (I think!)

However I am still getting the index exceeds matrix dimensions error

[Guillaume]

I don't know what's happening today. Neither Jan nor I provided a correct answer.

There's a bug in Jan's answer, he forgot to index the remove variable in the loop, it should read:

    remove(c) = numel(tmp) <= 10 && max(tmp) < (i-2);   %index remove!

The actual removal is correct and should be after the loop. remove is a logical array the same size as AllTraj.Passive so there won't be an Index Exceeds matrix dimension error. I would have created remove as:

remove = false(size(AllTraj.Passive)); 

but both way work.

Or you can use arrayfun which avoids the need for preallocation (see comment on my answer)/

[Manny Kins]

Thanks so much for your help! I have made the changes and it works very well! The code has sped up quite a bit too just by getting rid of the false positives (improvement of 50%!)

Answer 2

[Guillaume]

This code seems to run very slowly

The code you've posted either doesn' do anything because the if condition is never true, or errors (if the if condition is ever true). It can't be the code you actually use.

If your loop has a known number of iterations you should be using for not while. That way you can't mess up the iterator variable. Let's see what would happen if your if test was true:

%removed unnecessary brackets from the expression to make it easier to read
%check that the field T has less than 10 elements and that the maximum is less than something.
%i is a terrible variable name by the way.
if length(AllTraj.Passive(c).T) <= 10 && max(AllTraj.Passive(c).T) < (i-2)

The only thing you if the test is true is to replace the structure stored in Passive(c) by an empty array. The code then reaches the else. Since the if was true, the code in the else is not executed and c is not incremented. The code then reaches the end of the while loop.

Since c was not incremented, c is still the same as previous iteration. So, we know that AllTraj.Passive(c) is []. And therefore AllTraj.Passive(c).T is now an error. There is no field T, Passive(c) is not a structure anymore.

A for loop would avoid the bug:

for c = 1:numel(AllTraj.Passive)
    if numel(AllTraj.Passive(c).T) <= 10 && max(AllTraj.Passive(c).T) < (i-2)
        AllTraj.Passive(c) = [];
    end
end

Unfortunately for you, there is no way to make this faster without completely changing the way you store your data originally.

[Manny Kins]

Hi Guillaume, thanks for your reply and help. The main issue I was getting when using for instead of while was the error 'Index exceeds matrix dimensions'. This is because (I think) we are removing rows from AllTraj.Passive and hence it is getting smaller and smaller, whilst the initial number of iterations from numel(AllTraj.Passive) would stay the same. Is there any way around this?

[Guillaume]

Oh, yes of course, I missed the forest for the trees. Removing elements of an array while you iterate an array is never a good idea. The only way to do it reliably is to either work backward (but that creates a lot of reallocation), or create a new array with the non-removed elements.

Simpler is to first have a loop that creates a logical array indicating which elements are to be removed, then removed them all afterwards, as Jan has show (once you remove the bug).

I would code it like this:

toremove = arrayfun(@(elem) numel(elem.T) < = 10 && max(elem.T) < i-2, AllTraj.Passive);
AllTraj.Passive(toremove) = [];