ado@elsie.UUCP (07/07/87)
A while back I posted an article describing > The problem: given an arbitrary bit map, find a set of filled > rectangles that matches the bitmap while *minimizing the number > of rectangles used*. Several respondents suggested finding papers on quadtrees and Karnaugh maps. Other respondents had different or more specific suggestions; the letters from folks from whom I received permission to publish appear below. ------------------------------------------------------------------------------- From seismo!ihnp4!sask!aupperle Sat May 30 06:56:21 1987 . . . From: seismo!ihnp4!sask!aupperle (Larry Aupperle) . . . In its most general case this problem is NP-complete. By the most general case, I mean covering areas that are allowed to contain "holes", ie multiply connected regions. This was proven by Masek in 1979; the result is not published, so I can't give you the reference. His result is referred to in Garey and Johnson's text "Computers and Intractability: A Guide to the Theory of NP-Completeness". There is a polynomial time algorithm for regions that are vertically convex (ie any vertical line intersecting the region does so in a single line segment). It is described in D.S. Franzblau, D.J. Kleitman, "An algorithm for covering polygons with rectangles", in Information and Control, 63, pp. 164-189 (1984). As far as I know, the problem is open over arbitrary regions without holes. Although I believe the D.S. Franzblau has done some work on approximation algorithms. She is probably your best bet. The above paper should hopefully serve as the pointer you desire. Larry Aupperle. ps. I just realized that I assumed that you want the rectangles to be allowed to overlap ie: ABCDEFGHIJKLMNP uOOOOOOOOOOOOOOO vOOOXXXXXXOOOOOO wOOOXXXXXXXXXXOO xOOOXXXXXXXXXXOO yOOOOOOOXXXXXXOO zOOOOOOOOOOOOOOO The X region could be covered by two overlapping rectangles, ((D to I, v to x) (H to M, w to y). If you don't want overlapping rectangles, your primary references should be "Minimal Rectangular Partitions of Digitized Blobs", L. Ferrari, P.V. Sankar, and J. Sklansky, Computer Vision, Graphics, and Image Processing, 28, pp. 58-71, (1984). or "On two-dimensional data organization", E. Lodi, F. Luccio, C. Mugnai, and L. Pagli, Annales Societatis Mathematicae Polonae Series IV: Fundamenta Informaticae. As you can tell from the titles, the first reference is the image oriented one. ------------------------------------------------------------------------------- From seismo!ihnp4!sask!aupperle Fri Jul 3 01:50:17 1987 . . . From: seismo!ihnp4!sask!aupperle (Larry Aupperle) . . . Another reference you might be interested in, concerning rectangle partitions, is Ohtsuki, T., Minimum dissection of rectilinear regions, in "Proc. 1982 IEEE Sympos. on Circuits and Systems," Rome. pp 1210-1213. I haven't read the above paper. It is referenced in the Franzblau and Kleitman paper. Finally, something I might not have previously mentioned is Anna Lubiw's Phd Thesis. (U of T department of Computer Science tech report 186/86). Chapter three of this thesis describes a basis for a polynomial-time rectangle *cover* algorithm over certain rectilinear polygons. ------------------------------------------------------------------------------- From seismo!hplabs!hpcehfe!avi Wed May 27 15:45:06 1987 . . . From: Avi Naiman <seismo!hplabs!hpcehfe!avi> . . . Are you sure you want to minimize the number of rectangles? Although there are cases where you need fewer, overlapping rectangles to describe a bitmap, than disjoint ones, you must then be able to handle the overlap appropriately. Alternatively, you may want to minimize the sum of the edges of the rectangles. The general problem of decomposing a rectilinear polygon (i.e., a bitmap) into rectangles such that the total perimeter is minimal is NP-hard [Ling82]. If a polygon is without holes, the problem is solvable in polynomial time (O(n**4) for 'n' corners [Ling82]). There are various heuristics for finding a rectangular decomposition within some constant factor of the minimum edge length when there are holes [Ling83]. When there are a relatively small number of holes, the best approach seems to be to eliminate the holes by adding approximately minimum-length edges from the holes to the boundaries. This can be done in O(n**2) time and gives a solution within a factor of 2 of the minimum length for this step [Kou81]. Once the holes have been eliminated, the aforementioned algorithm for rectilinear polygons with no holes can be run. Kou81 Kou, L., G. Markowski and L. Berman, ``A Fast Algo- rithm for Steiner Trees,'' Acta Informatica, Volume 15, 1981. Ling82 Lingas, A., R. Pinter, R. Rivest, and A. Shamir, ``Minimum Edge Length Decompositions of Rectilinear Figures,'' Proceedings of the 12th Annual Allerton Conference on Communication, Control, and Computing, Illinois, 1982. Ling83 Lingas, A., ``Heuristics for Minimum Edge Length Rectangular Partitions of Rectilinear Figures,'' in Theoretical Computer Science, Edited by A. B. Cre- mers and H. P. Kriegel, Springer-Verlag, Berlin, January 1983, pp. 199-219. ------------------------------------------------------------------------------- From seismo!mcvax!hutcs!ado Wed May 27 07:51:47 1987 . . . From: seismo!mcvax!hutcs!ado (Andre Dolenc) . . .Try reading "An Algorithm for covering polygons with rectangles" by D.S.Franzblau and D.J.Kleitman, Information and Control 63,164-189(1984). ------------------------------------------------------------------------------- From cvl!harvard!endor!hughes@gymble.umd.edu Tue May 26 12:36:40 1987 . . . From: cvl!harvard!endor!hughes@gymble.umd.edu (Brian Hughes) . . . This might help: "Direct Spatial Search on Pictorial Databases Using Packed R-trees", by Roussopoulos, N. and Leifker, D., in Proceedings of ACM-SIGMOD 1985 International Conf. on Management of Data (SIGMOD RECORD, V. 14, no. 4, Dec. 1985) published by ACM. The packing algorithm they present seems like it should solve your problem. Since they are trying to represent arbitrary polygons, & you're just interested in rectangles, you could probably ignore some/many of their details. ------------------------------------------------------------------------------- From seismo!rochester!rocksvax!oswego!rocky!dab Sat May 23 23:51:44 1987 . . . you ought to check out: "Optimal Quadtree Construction Algorithms" by Clifford A. Shaffer & Hanan Samet in Computer Vision, Graphics, and Image Processing volume 37, number 3 (March,1987) pages 402-419 It constructs a quadtree identifying just those rectangles that go into a linear quadtree running time proportional to the number of rectangles in the resulting quadtree. Very clever algorithm. luck, Dave Bozak Director, Information Science SUNY College at Oswego Oswego, NY 13126 (315) 341-2367 rochester!rocksvax!oswego!dab ------------------------------------------------------------------------------- From seismo!cbosgd!alice!td Fri May 22 10:42:07 1987 . . . I have a Bell Labs memorandum in front of me titled ``Partitioning Rectangular Polygons into Rectangles'' by D. K. Sharma, dated Feb 1, 1982. It describes an algorithm for partitioning bitmaps (and more general Rectangular Polygons) into rectangles and proves that the result is optimal. I do not know whether this paper was ever published. Looking in the Bell Labs phone book, I find: Dhiraj K Sharma 201 580 8025 This D K Sharma is in a different department than the one listed on the memo, but he's probably the same person. I suggest giving him a call. ------------------------------------------------------------------------------- From seismo!mimsy!aplcen!osiris!phil Fri May 22 20:15:20 1987 . . . From: seismo!mimsy!aplcen!osiris!phil (Philip Kos) . . . Good golly, you're looking for a different version of a program I wrote back in grad school.. mine worked with edges instead of bitmaps, though. I had to write it completely from scratch and make lots of assumptions, like edges will always be either horizontal or vertical... it worked OK though. On a moderately loaded VAX-11/780 running 4.1aBSD it could reduce an image of about 1000 overlapping rectangles (these were masks for nMOS integrated circuits; my program was a plotter filter) into the correct feature outlines in a couple of minutes. The algorithm used went like this (this is from memory, I haven't seen the code for several years, so excuse lapses): - read all the edge line segments one at a time, finding closed rectangles whose four edges were stuck into a single structure; - perform a more-or-less n**2 loop over all the rectangles, where on each iteration you . check to see if the masking rectangle intersects the "rectangle of interest", . (if not) continue . (if so) clip overlapping edges of the "rectangle of interest" based on the area bounded by the masking rectangle - draw the resulting set of intersecting line segments, forming the feature outlines The clipping was the weird part. I had to bend over nearly backward to make sure I didn't clip things twice, or if I had two overlapping edges, that I didn't clip both, leaving a hole in the outline. Because of the complex algorithms I wound up with, and the difficulties I had working minor bugs out of the code, I once almost trashed everything and started over by converting the "continuous" set of edges to a bitmap and follow- ing the edges that way! Great fun. It took me most of a year and three pretty complete rewrites before I got it working satisfactorily. As far as I know, I don't have any copies of the code around, nor listings, and I don't know if you'd be able to get one from the University or not. . . -- "The Moon must wait--we have unfinished business here on Earth." UUCP: ..seismo!elsie!ado ARPA: elsie!ado@seismo.CSS.GOV Elsie and Ado are trademarks of Borden, Inc. and Ampex.