Fast segment to segment adjacency matrix

Say I have two images A and B of the same size. Say that I also have two bags of segments bag_A and bag_B of 2D segments, from images A and B respectively.

A 2D segment is defined as a set of locations (pixels) on an image, and can be represented with a binary image of the same size as the original image, where a pixel is true if the pixel is inside of the segment, and false if it is outside.

Say I want to see which segments from bag_A overlap with which segments from bag_B and encode the result in an adjacency matrix, so that:

• adjacency_matrix(segment_from_A,segment_from_B) is true if the segments overlap.
• adjacency_matrix(segment_from_A,segment_from_B) is false otherwise.

My question is, what would be an efficient way of quickly computing this adjacency matrix?

Say I define N and M as the % of segments in bag_A and bag_B respectively. Is there a way to compute the adjacency matrix in less than O(N*M) "on average"? (e.g. with a uniform distribution of segments in space and size)? If so, how?

My take so far:

I believe there is a way to do this via hashing, maybe by pre-processing the data to distribute segments into buckets. I think I can define a bucket for every location on each image where two or more segments from that image overlap. Then I could probably just compute the adjacency between the buckets between two images, and from that, I could get the adjacency between bag_A and bag_B somehow "directly". However, I am not sure if this would work (I will probably try it soon), or how to estimate the expecte开发者_C百科d running time for it.

Also, when would it be worth to compute the adjacency via hashing rather than via comparison all possible pairs directly?

Bonus: Implementation specfics

I'm ultimately looking for a solution that would work in or from MATLAB.

First impressions: At the lowest level, I would encode the segment data as bits in integers (or an array of integers), and implement the final comparison as an AND operation to find out if they overlap.

For higher level optimization, to reduce the number of comparisons, I would build quadtrees for the segment bitmaps where a branch present in the quadtree represents that there is a true-bit present anywhere in that quadrant of the bitmap (and so on recursively down to some arbitrary minimum). You could get fancier like encode the number of true bits in each quadtree branch if you want.

Then I'd hash the quadtrees to come up with the buckets. Within a bucket, you can quickly rule out what can't be a match if their quadtrees don't match. Finally, I'd use a low-level AND operation to find the ones that actually overlap.