findsubmat

Finds one matrix (a sub-matrix) within another.

Description

FINDSUBMAT find one matrix (a sub-matrix) inside another.
IDX = FINDSUBMAT(A,B) looks for and returns the linear index of the
location of matrix B within matrix A. The index IDX corresponds to the location of the first element of matrix B within matrix A. Only works for 2-d matrices or vectors, both of which may contain NaNs or Infs.

[R,C] = FINDSUBMAT(A,B) returns the row and column instead.

I would like to extend to N-D but don't have the time right now. This may be a future enhancement, but I believe the file stands on it's own just fine too.

Email me if bugs are found, thanks.

• MATLAB release: MATLAB 7.4 (R2007a)

[us]

- very nice: help, example, commented and intelligent engine, acknowledgement of input by another user (excellent academic behavior)...
- BUT: unfortunately, it does NOT (yet) handle NANs - nor does it give a warning/error message...
- a workaround could be to replace NANs with a unique value not found in either data set (we did this in FEX:FPAT:id:6070)...
us

[Matt Fig]

Good point us, I will submit an update.

[us]

observing a master carving out an outstanding masterpiece of a master's workmanship...
us

[Siyi Deng]

Matt: your code is well written but I really don't understand why use strfind to serch line by line. Compare it to these codes:

% Sorry I'm not used to use capital a,b;

idx = find(a(1:(ra*(ca-cb+1)-rb+1)) == b(1));
idx = idx(mod(idx-1,ra) <= ra-rb);

idc = bsxfun(@plus,0:ra:ra*(cb-1),(0:rb-1).');
c = 2;
d = b(c) == a(idx+idc(c));
while ~all(d)
    idx = idx(d);
    c = c+1;
    d = b(c) == a(idx+idc(c));
end

for general large matrices It seems that searching line by line usually results in overkill.

[Matt Fig]

Siyi, Your code, as written, will work when there is one submatrix within A. However, it will need to be modified for multiple submatrices. Even without the modification, it is slower to use the approach you suggest. In the following, I made a copy of findsubmat, took out all of the NaN checking and the transposing of A, and put your code in the proper place. Here are some results:

A = round(rand(2000)*1);
B = [1 2;4 5];
A(30:31,60:61) = B; % Only one submatrix.

tic
C = findsubmat(A,B); % Elapsed time is 0.055974 seconds.
toc

tic
C = findsubmat_2(A,B); % Elapsed time is 0.502954 seconds.
toc

Also, this is really the kind of exchange that better takes place through email. Mine is listed in the help for findsubmat.
Feel free to email me about this code.
Thanks.

[Karthik Mahadevan]

 

[Thomas Trötscher]