Measuring distances between image components

How is this? It first groups the points of each component together and applies Nearest and to find minimal distances in the sense of

$$d(A,B) = \inf_{a \in A} \inf_{b\in B} |a-b|.$$

This extracts the boundary pixels of each component (also of the background component):

im = Import["https://i.stack.imgur.com/U7myR.png"];
comp = SparseArray@With[{
       perimeter = 
        SparseArray[ImageData[MorphologicalPerimeter[im]]],
       comp = MorphologicalComponents[im]},
      Plus[
       Times[UnitStep[-comp], 
        MorphologicalTransform[perimeter, Max]],
       Times[comp + 1, perimeter]
       ]
      ]; // AbsoluteTiming // First
Colorize@comp

0.029138

This groups the boundary points' coordinates according to their components:

comppts = Developer`ToPackedArray /@ KeySort@Association@Reap[
         MapThread[
          Sow[#1, #2] &, 
          {comp["NonzeroPositions"],comp["NonzeroValues"]}],
         _, Rule
         ][[2]]; // AbsoluteTiming // First

0.041497

Now we use Nearest to compute pairwise distances:

n = Length[comppts];
data = ParallelTable[
    With[{nf = Nearest[comppts[i] -> "Distance"]},
     {i, j} -> Min[nf[comppts[j]]]
     ],
    {i, 1, n}, {j, i + 1, n}
    ]; // AbsoluteTiming // First

A = Normal[SparseArray[Join @@ data, {n, n}]];
A += Transpose[A];

MatrixPlot[A]

0.424216

So, everything is done in roughly half a second.

If you are not interested in the background component, you can use

comppts = 
    Association@ComponentMeasurements[im, "PerimeterPositions"]; // 
  AbsoluteTiming // First
n = Length[comppts];
data = ParallelTable[
     With[{nf = Nearest[comppts[i][[1]] -> "Distance"]},
      {i, j} -> Min[nf[comppts[j][[1]]]]],
     {i, 1, n},
     {j, i + 1, n}
     ]; // AbsoluteTiming // First
A = Normal[SparseArray[Join @@ data, {n, n}]];
A += Transpose[A];
MatrixPlot[A]

0.006328

0.384601

not a general answer (it is specific to the maze above or when the pixel distance is very small). Assuming distance to be Euclidean, the code below finds distance between neighbours (ignores any pair that is not a neighbour):

comp = MorphologicalComponents@img // Dilation[#, 1] &;
pairs = DeleteDuplicates[Sort/@ Flatten@Map[Thread, ComponentMeasurements[comp,"Neighbors"]]];
neigh = GroupBy[pairs, Keys -> Values];
cent = <|ComponentMeasurements[comp, "Centroid"]|>;

distance[{p_, q___}] := EuclideanDistance[p, #] & /@ {q};

dist = KeyValueMap[distance@FlattenAt[{Lookup[cent, #1], Lookup[cent, #2]}, {2}] &,neigh];

res = Thread[(pairs /. Rule -> List) -> Flatten@dist];

SparseArray[Join[MapAt[Reverse, res, {All, 1}], res]]//MatrixPlot

Absolute timing: 0.0315194

I am not sure that I would call this "efficient", but I think it does what you are asking: given a set of component masks and a pair of component labels, it should return the minimum distance between the components with the given labels.

Get the image:

maze = Import["https://i.stack.imgur.com/U7myR.png"];

Get an association of labels to component masks, and assemble the pairs of component labels:

compMasks = Association @@ ComponentMeasurements[maze, "Mask"];
compLabels = Keys[compMasks];
labelPairs = Tuples[compLabels, 2];

Define a function meant to take the sparse array mask of two regions as separate arguments and return the minimum Euclidean distance between them:

compDistance[mask1_, mask2_] := Block[
    {m1Back, genDist, m2Im},
    m1Back = ColorNegate[Image[mask1]];
    genDist = DistanceTransform[m1Back];
    m2Im = Image[mask2];
    ImageMeasurements[m2Im genDist, "Min", Masking -> m2Im]
]

Define another function that calls that one to compute distance between labelled components:

labelledDistance[maskAssoc_, {label1_, label2_}] := compDistance[maskAssoc[label1], maskAssoc[label2]]

See the results and timing on the first 10 component pairs:

AbsoluteTiming[{#, labelledDistance[compMasks, #]} & /@ labelPairs[[1 ;; 10]]]

returns:

{0.193874, {{{1, 1}, 0.}, {{1, 2}, 3.}, {{1, 3}, 3.}, {{1, 4}, 3.}, {{1, 5}, 3.}, {{1, 6}, 3.}, {{1, 7}, 23.1948}, {{1, 8}, 63.0714}, {{1, 9}, 103.044}, {{1, 10}, 143.031}}}

To compute the distances for all pairs takes ~4m.

 AbsoluteTiming[{#, labelledDistance[compMasks, #]} & /@ labelPairs;]
 {242.331, Null}