A new spatial relation called arrangements has been previously proposed to describe how embedded parts in an image are surrounded by their neighbors. Arrangements can be derived directly from the sequence of Voronoi cells bordering an embedded part of an image. It has been shown that it is possible to compare any two arrangements, caused by the embedding of the same parts, by use of the Diagonal Exchange Operator and the Voronoi Flower diagram. However, the algorithms previously proposed is practical only for very small sets of embedded parts because of both the expensive operation of computing the prerequisite area Voronoi tessellation and the exponential search complexity (in terms of the number of edges in the Voronoi tessellation) required to compute the distance metric. We present a new algorithm for computing arrangements efficiently for complex images containing a large number of embedded parts. Motivated by the new algorithm, we propose the use of arrangements for the indexing and retrieval of complex technical diagrams which may contain many similar parts.
Mark J. Burge,
Wilhelm C. Burger,
"Qualitative spatial relations using arrangements for complex images", Proc. SPIE 2826, Vision Geometry V, (30 September 1996); doi: 10.1117/12.251788; https://doi.org/10.1117/12.251788