Partitioning a Gridded Rectangle Into Smaller Rectangles

NASA Tech Briefs, Jul 2004

A relatively simple algorithm yields nearly square, nearly equally sized segments.

NASA's Jet Propulsion Laboratory, Pasadena, California

A relatively simple algorithm, devised for use in an image-data-compression application, partitions a rectangular pixelated image (or any other rectangle on which a regular rectangular grid has already been superimposed) into a specified number of smaller rectangles, hereafter denoted segments. The algorithm has the following properties:

* No floating-point operations are needed.

* The segments tend to be nearly square (in the sense that their widths and heights in pixel units tend to be nearly equal).

* The segments tend to have nearly equal areas.

* The algorithm yields valid results (no zero-width or zero-height segments) as long as the specified number of segments, s, does not exceed the number of pixels (equivalently, the number of grid cells).

The inputs to the algorithm are the positive integer s plus the positive integers h and w, denoting the height and width, respectively, of the rectangle in pixel units. The limit on s for a valid result is given by 5

The output of the algorithm is characterized by, and can be described completely in terms of, several parameters that are illustrated by the example shown in the figure. The segments are arranged in r rows. A top region of the rectangle contains segments arranged in c columns. A possible bottom region contains segments arranged in c 1 columns. The top region has height h^sub t^ and contains r^sub t^ rows of segments. The first r^sub t0^ rows of segments in the top region have height y^sub t^; the remaining rows (if any) in the top region have height y^sub t^ 1. The first c^sub t0^ columns in the top region have width x^sub t^; any remaining columns in the top region have width x^sub t^ 1. Similarly, the first r^sub b0^ rows in the bottom region have height y^sub b^, and the remaining rows in the bottom region have height y^sub b^ 1, while the first c^sub b0^ columns in the bottom region have width x^sub b^ and the remaining columns in the bottom region have width x^sub b^ 1.

It has been verified by straightforward algebraic analysis of these equations that the algorithm has the properties mentioned in the first paragraph.

This work was done by Matthew Klimesh and Aaron Kiely of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.

This software is available for commercial licensing. Phase contact Don Hart of the California Institute of Technology at (818) 393-3425. Refer to NPO-30479.