Finding a largest rectangle inside a digital object and rectangularization

摘要

A combinatorial algorithm to find a largest rectangle (LR) inside the inner isothetic cover which tightly inscribes a given digital object without holes is presented here which runs in O(k.n/g+(n/g)log⁡(n/g)) time, where n, g, and k being the number of pixels on the contour of the digital object, grid size, and the number of convex regions, respectively. Certain combinatorial rules are formulated to obtain an LR. An LR divides the object in several parts. The object can be rectangularized by recursive generation of a set of LRs and it generates LR-Graph which is useful for shape analysis.