What is the fastest way to check if a matrix is an element of an 3d array?-CodePudding

I have an 3d binary array M(x,y,z) consisting of only 0s and 1s, then at each timestep I am given an binary matrix A(x,y), then I need to check if A(x,y)=M(x,y,z) for some z, and if not then I add it at the end of M with M(x,y,end 1)=A(x,y). Is there a way to do this which is faster then checking every z until an equality is found?

I tried looping over every z, but then I thought it should be possible to precompute something aout M that allows us to check multiple z with 1 comparison.

CodePudding user response：

Obviously there is no way of doing it without checking all of them.

However if you are trying to find a faster way, we can borrow from the image processing literature where they use "image integrals". Simply compute sum(M,[1,2]) for each z slice and store it in an array. When a new A comes, compute sum(A(:)) and compare to the list. Then only fully compare such indices of z that match in integral with the new matrix.

Depending on the nature of the matrices, you may need to find a different metric that is not the integral, as your application may produce normalized matrices or something like that. Just find a metric that is different enough and easy to compute. Image integrals are really good for natural images.

CodePudding user response：

Premature optimisation being the root of all evil, instead of trying to do anything fancy, I would simply try and use MATLAB's array notation and vectorisation and then later worry about optimisations. I haven't tested, but there's a decent chance that just vectorising things will be pretty reasonable since it makes the memory accesses required uniform. Here's how I'd do it:

>> M = rand(3,4,7) > 0.5;  % Example data
>> A1 = rand(3,4) > 0.5;   % (Probably) not a page of M
>> A2 = M(:,:,3);          % Page 3 of M
>> find(all(A1==M, [1 2])) % Use implicit expansion to compare
ans =
  0x1 empty double column vector
>> find(all(A2==M, [1 2]))
ans =
     3

This uses implicit expansion in the Ax == M piece, and then uses the relatively recent vectorised dimension specifier to all for the "reduction" piece.