How to compute Pairwise L1 Distance matrix on very large images in neighborhood only?
I am working on Deep learning approach for my project. And I need to calculate Distance Matrix on 4D Tensor which will be of size N x 128 x 64 x 64 (Batch Size x Channels x Height x Width). The distance matrix for this type of tensor will of size N x 128 x 4096 x 4096 and it will be impossible to fit this type of tensor in GPU, even on CPU it will require lot of memory. So, I would like to calculate the distance matrix only in some neighborhood pixels (say within radius of 5) and consider this rectangular matrix for further processing in neural network. With this approach my distance matrix will be of size N x 128 x 4096 x 61. It will take less memory in comparison to full distance matrix.

Precisely, I am trying to implement the Convolution Random Walk Networks for Semantic Segmentation. This network needs to calculate the Pairwise L1 Distance for features.

Architecture

Just to add this type of Distance Matrix is usually calculated for image segmentation via spectral clustering.

For Example


X = [[a,b],[c,d]]

L1_dist = [ [0, |a-b|, |a-c|, 0], 
            [|a-b|, 0, 0, |b-d|], 
            [|a-c|, 0, 0, |c-d| ], 
            [0,    |b-d|, |c-d|, 0 ] 
          ]

Final_L1_dist = [ [0, |a-b|, |a-c|], // "a" is near to b and c. Including self element i.e. a 
            [|a-b|, 0, |b-d|], // "b" is near to a and d. 
            [|a-c|, 0, |c-d| ], // "c" is near to a and d. 
            [|b-d|, |c-d|, 0 ] // "d" is near to b and c. 
          ]



I would appreciate, if some one can help me to find an efficient way to compute such a matrix.

Thanks  

As far as I understand, the goal is to apply minus operation to each pixel and its surrounding neighbors. This sounds like convolution to me. 

Consider the following convolution process (assume padding='SAME'):



The 3x3 kernel calculates, for each pixel, the difference between the center pixel and its left one. For other neighbors, consider the following kernels:



Thus the goal can be achieved via the following: 


Repeat each kernel for num_channels times using tf.tile;
Apply each kernel channel-wisely using tf.nn.depthwise_conv2d;
Do tf.abs to get the distance;
Reshape each distance tensor to NxCx(HW)x1 and stack them properly.


For efficient for loop, you may consider using tf.map_fn.
