Determine if there are 3 consecutive rows and columns in a list of subscripts

I have a 28x2 matrix (see printout below) of subscript values (row, col) and I want to determine if there are 3 consecutive rows and then 3 connective columns coming stemming from a single reference point in the list of subscripts. From the example list below, the answer to this questions would be 'yes'. This is because the 3 consecutive rows are (44,13), (45,13), (46,13), and the 3 consecutive columns are (44,13), (44,14), (44,15). How would I execute this in matlab? I was thinking of using diff(A) to determine changes in subscript values but I am unsure exactly how. Sorry if this is confusing at all, wasn't sure how to explain my problem.

A =

      43    15
      44    13
      44    14
      44    15
      44    16
      45    12
      45    13
      45    14
      45    15
      45    16
      46    12
      46    13
      46    14
      46    15
      46    16
      47    12
      47    13
      47    14
      48    11
      48    12
      48    13
      49    11
      49    12
      49    13
      50    11
      50    12
      50    13

Answer 1

[Matt J]

map=conv2(  accumarray(A,1), ones(3),'same');

any3x3 = any(map(:))>=9

[Andrew Poissant]

Hello, thank you for the quick response. Could you please explain your two lines of code very briefly? The output I am getting for 'any3x3' for the list provided in the question is 0. I am assuming 0 means that no such consecutive rows and columns are present in the list I provided above?

[Matt J]

Whoops. Typo.

   any3x3 = any( round(map(:)) >=9 )

The idea is to convert A to a binary image by doing accumarray(A,1). Then we convolve the image with a matched filter kernel ones(3). If any pixel in the filter output is greater than 9, you know a 3x3 connected region is present.

If you have the image processing toolbox, you could also use bwconncomp.

[Fangjun Jiang]

should be: any3x3 = any(map(:)>=9)

[Andrew Poissant]

Ah, I see. It works now. How would I extract the pairs of rows/cols that satisfy the 3 consecutive row/col condition?

[Matt J]

   [I,J]=find(  map >=9 );

    rows= I+[-1:1];
    cols= J+[-1:1];

[Andrew Poissant]

perfect. Thank you for your help!

[Guillaume]

Hum, the convolution looks for the pattern

[1 1 1
 1 1 1 
 1 1 1]

which as far as I understood is not what was asked for and is a lot more restrictive. E.g, the code fails with:

A = [1 1; 1 2; 1 3; 2 1; 3 1]

And I'm not sure my answer matches what was asked for either. I understood that the 3 consecutive columns and 3 consecutive rows could be completely independent. Rereading the question, I think that the 3 consecutive rows and columns must intersect.

Answer 2

[Guillaume]

One option:

hasconseccols = any(accummarray(A(:, 1), A(:, 2), [], @(v) ~isempty(strfind(sort(diff(v))', [ 1 1]))))
hasconsecrows = any(accummarray(A(:, 2), A(:, 1), [], @(v) ~isempty(strfind(sort(diff(v))', [ 1 1]))))

which basically, regroup together in a vector all the indices corresponding to a row/column respectively, sort that vector, take its diff and search for [1 1] which indicates at least 3 consecutive indices. If the search is not empty you have at least one row/column with 3 consecutive points.

Another option:

B = zeros(max(A));
B(sub2ind(max(A), A(:, 1), A(:, 2))) = 1;
hasconseccols = any(any(conv2(B, [1, 1, 1]) == 3))
hasconsecrows = any(any(conv2(B, [1; 1; 1]) == 3))

which basically fills a matrix with 1 at your given indices, then convolves it with a column or row of three 1. If that result in a 3, you know you have 3 consecutive indices.

[Andrew Poissant]

This looks like what I am looking for! Do you know how I would return the list of subscripts that are part of the 3 consecutive row/col pts?

[Andrew Poissant]

Also where in the code for the first solution you posted did you specify it had to be 3 consecutive rows/cols? I see where you did that in the second solution.

[Guillaume]

With the first option, to get the indices of the columns with 3 consecutive rows, use find instead of any. The index of the 3 consecutive rows in these columns cannot be retrieved easily however. Use find instead of any on the 2nd line to get the indices of the rows with 3 consecutive columns.

The diff of 3 consecutive row/column indices will generate the sequence [1 1]. I use strfind to find that sequence. Despite its name, strfind works for finding sequences of numbers.

With the second option. The locations of the 3s in the result of the convolutions mark the centre of the row/column sequence, so:

B = accumarray(A, 1);  %simpler than my initial 2 lines. From matt's answer
[row, centrecol] = find(conv2(B, [1, 1, 1], 'same') == 3);  %consecutive columns in a row
[centrerow, col] = find(conv2(B, [1; 1; 1], 'same') == 3); %consecutive rows in a column

edit: forgot the == 3 in the find for the convolutions

[Andrew Poissant]

Thank you for the answer. You solutions were very helpful.

[Guillaume]

I think I misunderstood a bit what was asked and that the consecutive rows and column must intersect. If that is the case, then the accumarray option would not work.

You can build on my conv2 solution to get the correct result:

B = accumarray(A, 1);  %simpler than my initial 2 lines. From matt's answer
[row, centrecol] = find(conv2(B, [1, 1, 1], 'same') == 3);  %consecutive columns in a row
[centrerow, col] = find(conv2(B, [1; 1; 1], 'same') == 3); %consecutive rows in a column
colexpanded = (centrecol + [-1, 0, 1])';
rowexpanded = (centrerow + [-1, 0, 1])';
ptsconsecrow = [repelem(row, 3, 1), colexpanded(:)];
ptsconseccol = [rowexpanded(:), repelem(col, 3, 1)];
intersections = intersect(ptsconsecrow, ptsconseccol, 'rows')