Find a vector placed horizontally or vertically in

问题:

I'm trying to find a vector B in a big matrix A.
B can be in multiple rows and one column of A, or multiple columns and one row of A.

For example:

A = [56  55  53  52  53;
     49  45  44  45  47;
     33  30  31  34  35;
     34  34  27  24  26;
     44  48  45  35  24;
     56  57  57  53  39;
     62  62  62  60  55;
     62  61  61  54  47;
     49  47  42  40  32;
     47  42  44  45  40];

B = [34 27 24];

I need a function that returns the row and col indices i.e. something like:
find(A, B) → 4th row, 2nd to 4th col (for the given example).

How to do this?

回答1:

Benchmark between rahnema1 and m7913d

Horizontal and vertical matches

Benchmarking the solution of rahnema1 and m7913d using timeit for the given example (Small A) and one that is 100^2 larger (Large A), gives the following results:

Method   | Small A    | Large A
--------------------------------
rahnema1 | 4.0416e-05 | 0.0187
m7913d   | 2.5242e-05 | 0.0129

Note that m7913d's solution is ~50% faster.

Horizontal (or vertical) matches only

If you are only interested in horizontal matches, the following results are obtained:

Method   | Small A    | Large A
--------------------------------
rahnema1 | 9.6752e-06 | 0.0115
m7913d   | 5.8634e-06 | 0.0056

In this case, m7913d's solution is even more favorable, being up to ~100% faster.

Complete benchmark code

A=[56  55  53  52  53;
  49  45  44  45  47;
  33  30  31  34  35;
  34  34  27  24  26;
  44  48  45  35  24;
  56  57  57  53  39;
  62  62  62  60  55;
  62  61  61  54  47;
  49  47  42  40  32;
  47  42  44  45  40];
B=[34 27 24];
A_large = repmat(A, 100, 100);

t_m7913d = timeit(@() m7913d(A, B))
t_rahnema = timeit(@() rahnema1(A, B))

t_large_m7913d = timeit(@() m7913d(A_large, B))
t_large_rahnema = timeit(@() rahnema1(A_large, B))

 function [row_h, col_h, row_v, col_v] = m7913d(A, B)
    Ah = true(size(A) - [0 length(B)-1]);
    Av = true(size(A) - [length(B)-1 0]);
    for i=1:length(B)
        Ah= Ah & A(:, i:end-3+i) == B(i);
        Av= Av & A(i:end-3+i, :) == B(i);
    end
    [row_h, col_h] = find(Ah);
    [row_v, col_v] = find(Av);
end

function [row_h, col_h, row_v, col_v] = rahnema1(A, B) 
    n = numel(B);
    C = A == reshape(B,1,1,n);
    mask_h = permute(eye(n),[3 2 1]);
    mask_v = permute(eye(n),[1 3 2]);
    [row_h, col_h]=find(convn(C,mask_h,'valid')==n);
    [row_v, col_v]=find(convn(C,mask_v,'valid')==n);
end

回答2:

We can typecast the matrix to char and use strfind to search the matrix:

%Horizontal search
A_str_h = typecast(A.','char');
B_str = typecast(B,'char');
charsize = numel(B_str)/numel(B);
pos_h = strfind(A_str_h,B_str)-1;
pos_h = pos_h(mod(pos_h,charsize)==0)/charsize+1;
[col_h row_h] = ind2sub(flip(size(A)),pos_h);
idx_h = col_h <= (size(A,2)-numel(B)+1);
row_h = row_h(idx_h);
col_h = col_h(idx_h);

%Vertical search
A_str_v = typecast(A,'char');
B_str = typecast(B,'char');
charsize = numel(B_str)/numel(B);
pos_v = strfind(A_str_v,B_str)-1;
pos_v = pos_v(mod(pos_v,charsize)==0)/charsize+1;
[row_v col_v] = ind2sub(size(A),pos_v);
idx_v = row_v <= (size(A,1)-numel(B)+1);
row_v = row_v(idx_v);
col_v = col_v(idx_v);

Another solution using convn:

n = numel(B);
C = A == reshape(B,1,1,n);
mask_h = permute(eye(n),[3 2 1]);
mask_v = permute(eye(n),[1 3 2]);
[xh yh]=find(convn(C,mask_h,'valid')==n);
[xv yv]=find(convn(C,mask_v,'valid')==n);

[xh yh] represents the starting positions of horizontal matches and [xv yv] represents the starting positions of vertical matches.

Here is the result of testing different methods setting A as a [2750 * 1250] matrix and different sizes for B:

Result shows that CONVN is less efficient than other methods and is not applicable for arrays of large sizes and STRFIND works best for all array sizes.

*Methods are tested in Octave.

回答3:

For a fixed size of B, you can use the following approach:

[row, col] = find(A(:, 1:end-2) == B(1) & ...
                  A(:, 2:end-1) == B(2) & ...
                  A(:, 3:end) == B(3))

This will return row = 4 and col = 2, i.e. the location of B(1) in A.

See Find Array Elements That Meet a Condition for more information.

This can be extended to a variable size vector B using a for loop:

Ah = true(size(A) - [0 length(B)-1]);
for i=1:length(B)
    Ah= Ah & A(:, i:end-length(B)+i) == B(i);
end
[row, col] = find(Ah);

This can be easily extended to find occurrences of B horizontally and vertically as follows:

Ah = true(size(A) - [0 length(B)-1]);
Av = true(size(A) - [length(B)-1 0]);
for i=1:length(B)
    Ah= Ah & A(:, i:end-3+i) == B(i);
    Av= Av & A(i:end-3+i, :) == B(i);
end
[row_h, col_h] = find(Ah);
[row_v, col_v] = find(Av);

Benchmark

Note that nevertheless I'm using a for loop this method is faster than rahnema1's solution, especially if you are only interested in horizontal (or vertical) matches. Have a look at the benchmark for more information.