Locate touching pixels of two objects

Question

Suppose I have matrix, where each cell of this matrix describes a location (e.g. a bin of a histogram) in a two dimensional space. Lets say, some of these cells contain a '1' and some a '2', indicating where object number 1 and 2 are located, respectively.

I now want to find those cells that describe the "touching points" between the two objects. How do I do that efficiently?

Here is a naive solution:

X = locations of object number 1 (x,y)
Y = locations of object number 2 (x,y)
distances = pdist2(X,Y,'cityblock');

Locations (x,y) and (u,v) touch, iff the respective entry in distances is 1. I believe that should work, however does not seem very clever and efficient.

Does anyone have a better solution? :) Thank you!

Answer 1

Use morphological operations.
Let M be your matrix with zeros (no object) ones and twos indicating the locations of different objects.

M1 = M == 1; % create a logical mask of the first object
M2 = M == 2; % logical mask of second object
dM1 = imdilate( M1, [0 1 0; 1 1 1; 0 1 0] ); % "expand" the mask to the neighboring pixels
[touchesY touchesX] =...
   find( dM1 & M2 ); % locations where the expansion of first object overlap with second one

Answer 2

Code

%%// Label matrix
L = [
    0 0 2 0 0;
    2 2 2 1 1;
    2 2 1 1 0
    0 1 1 1 1]

[X_row,X_col] = find(L==1);
[Y_row,Y_col] = find(L==2);

X = [X_row X_col];
Y = [Y_row Y_col];

%%// You code works till this point to get X and Y

%%// Peform subtractions so that later on could be used to detect 
%%// where Y has any index that touches X

%%// Subtract all Y from all X. This can be done by getting one
%%//of them and in this case Y into the third dimension and then subtracting
%%// from all X using bsxfun. The output would be used to index into Y.
Y_touch = abs(bsxfun(@minus,X,permute(Y,[3 2 1])));

%%// Perform similar subtractions, but this time subtracting all X from Y
%%// by putting X into the third dimension. The idea this time is to index
%%// into X.
X_touch = abs(bsxfun(@minus,Y,permute(X,[3 2 1]))); %%// for X too

%%// Find all touching indices for X, which would be [1 1] from X_touch.
%%// Thus, their row-sum would be 2, which can then detected and using `all`
%%// command. The output from that can be "squeezed" into a 2D matrix using
%%// `squeeze` command and then the touching indices would be any `ones`
%%// columnwise.
ind_X = any(squeeze(all(X_touch==1,2)),1)

%%// Similarly for Y 
ind_Y = any(squeeze(all(Y_touch==1,2)),1)

%%// Get the touching locations for X and Y
touching_loc = [X(ind_X,:) ; Y(ind_Y,:)]

%%// To verify, let us make the touching indices 10
L(sub2ind(size(L),touching_loc(:,1),touching_loc(:,2)))=10

Output

L =
     0     0     2     0     0
     2     2     2     1     1
     2     2     1     1     0
     0     1     1     1     1

L =
     0     0    10     0     0
     2    10    10    10     1
    10    10    10    10     0
     0    10    10     1     1