For an application in image processing -- using R for statistical purposes -- I
need to solve the following task:
Given n (e.g. n = 100 or 200) points in the unit square, more or less randomly
distributed. Find a rectangle of maximal area within the square that does not
contain any of these points in its interior.
If a, b are height and width of the rectangel, other constraints may have to be
imposed such as a, b <= 0.5 and/or 0.5 <= a/b <= 2.0 . The rectangle is
allowed to touch the border of the square.
For each new image the points will be identified by the application, like all
stars of a certain brightness on an astronomical picture. So the task will have
to be performed several times.
I assume this problem is computationally hard. I would like to find a solution
that is reasonably fast for n = 100..200 points. Exhaustive search along the
x, y coordinates of the points will not be fast enough.
I doubt there is easy way to solve this. At least it is not obvious to me.
PS: see also http://yetanothermathprogrammingconsultant.blogspot.com/2010/03/looks-difficult-to-me-2.html
I guess the solution rectangle has to be aligned with the unit square?
ReplyDeleteThis problem reminds me of this one paper of applied topology: "Homological Sensor" networks. In that paper, the dropped sensors on some area. The sensors had a given range, thus defining a neighborhood graph. From this graph, you can construct a higher-dimensional simplicial complex and compute its homology groups. This way, they could detect holes in the area, not covered by points.
You could interprete your points as sensors and play a little with the range. Of course, the holes found by this method are purely topological, independent of size and shape. It might still be fun to try.
Link to paper:
http://www.math.uiuc.edu/~ghrist/preprints/noticesdraft.pdf
There is already some software available, to compute the homology:
http://chomp.rutgers.edu/
In any case, you can learn some new trick :-)
Well, I would agree that it isn't easy if you are starting from scratch, but this sort of task is fairly straightforward with standard image processing packages.
ReplyDeleteSay you have a binary image with your n points as black pixels on a white background. Modify that image by going through each point and blacking out the entire row and entire column of each point. You now have an image with a bunch of lines. These black lines outline a bunch of white rectangles, which are your candidate rectangles.
Now you can run a standard blob-finding routine to get a list of the rectangles, which you can easily sort by area or apply constraints as you wish.
I know Intel IPP and Matlab have blob-finding built into their image processing toolboxes. I am not familiar with R . . . you may need to implement your own blob finding routine . . . one place you might look for help is openCV's open source implementation (C++). http://opencv.willowgarage.com/wiki/cvBlobsLib#Algorithm
I have actually once solved a similar problem (same but with largest circle) with genetic programing. it works very well.
ReplyDeleteHmm, on further review, please disregard my comment. ;)
ReplyDeleteThe main disadvantage I see with genetic programming is that it is often not clear how good the solutions are. It finds better and better solutions, but how far we are from a global optimum is often just a guess. But it is well known that for some difficult problems it can do extremely well.
ReplyDeleteDo the sides of the rectangle have to be parallel with the sides of the unit square? If not this problem is really hard.
ReplyDeleteOtherwise I'd go for a largest circle first, then find a large box.
Some references are in http://en.wikipedia.org/wiki/Largest_empty_rectangle.
ReplyDelete