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 s ≤ wh.
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 ht and contains rt rows of segments. The first rt0 rows of segments in the top region have height yt; the remaining rows (if any) in the top region have height yt + 1. The first ct0 columns in the top region have width xt; any remaining columns in the top region have width xt + 1. Similarly, the first rb0 rows in the bottom region have height yb, and the remaining rows in the bottom region have height yb + 1, while the first cb0 columns in the bottom region have width xb and the remaining columns in the bottom region have width xb + 1.
The steps of the algorithm are the following: First, r is computed. If h > (s – 1)w then r = s. Otherwise, r is the unique positive integer that satisfies (r – 1)rw < hs ≤ (r+1)rw. Some of the other parameters are computed as follows:
If rt < r, so that there is a bottom region, then the remaining parameters are computed as follows:
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. Please contact Don Hart of the California Institute of Technology at (818) 393- 3425. Refer to NPO-30479.
This Brief includes a Technical Support Package (TSP).
Partitioning a Gridded Rectangle Into Smaller Reactangles
(reference NPO30479) is currently available for download from the TSP library.
Don't have an account? Sign up here.