Rectangular partition for n-dimensional images with arbitrarily shaped rectilinear objects

Abstract

Partitioning two- or multidimensional polygons into rectangular and rectilinear components is a fundamental problem in computational geometry. Rectangular and rectilinear decomposition have multiple applications in various fields of arts as well as sciences, especially when dissecting information into smaller chunks for efficient analysis, manipulation, identification, storage, and retrieval is essential. This article presents three simple yet elegant solutions for splitting geometric shapes (particularly non-diagonal ones) into non-overlapping and rectangular sub-objects. Experimental results suggest that each proposed method can successfully divide n-dimensional rectilinear shapes, including those with holes, into rectangular components containing no background elements. The proposed methods underwent testing on a dataset of 13 binary images, each with 1 … 4 dimensions, and the most extensive image contained 4096 elements. The test session consisted of 5 runs where starting points for decomposition were randomized where applicable. In the worst case, two of the three methods could complete the task in under 40 ms, while this value for the third method was around 11 s. The success rate for all the algorithms was 100 %.

Keywords

• Computational geometry
• Computer vision
• Image analysis
• Image processing
• Polygon partition problem