Sébastien Piérard

Listing all the maximal included rectangles

Shape representation and analysis are crucial tasks for a large variety of applications including video scene interpretation, video surveillance, automatic classification of objects, quality control, etc. We propose a new technique for the representation of binary shapes in two-dimensional discretized spaces (digital images). We represent shapes by the set of all maximal rectangles that can be wedged inside the shape. This representation has already been used successfully for machine learning tasks.

maximal rectangles

A binary shape with two examples of maximal included rectangles.

How to cite this work ?

Object descriptors based on a list of rectangles: method and algorithm (download the PDF file)
M. Van Droogenbroeck and Sébastien Piérard
10th international symposium on mathematical morphology (ISMM)
July 2011 - Intra, Italy


We have proposed a new algorithm (the only existing one to our knowledge) to compute the set of all maximal included rectangles. It is fast and easy to implement. Only 50 lines of C code suffice to compute the set ! The computational complexity is linear in the number of pixels in the image.

The following video is supplementary material related to our paper. It shows the behavior of our algorithm on an example, step by step. A circle is drawn on each visited pixel. The color of this circle is blue for pixels (row,col+width-1) on which a maximal rectangle has been detected. The horizontal red line denotes the downwards limit maxS.

Loading the player ...

Software download

We provide a C++ program (with source files) that computes the set of maximal included rectangles, and granulometries. It runs on Linux (it should be possible to compile it for other operating systems too).

>>>>>> Download ! <<<<<<