patternMinor
What is an algorithm to find the largest rectangle of white space in an image?
Viewed 0 times
thewhitespacewhatimagerectanglelargestalgorithmfind
Problem
Take an image, (the Google home page) is a good example.
I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of white space containing only white space.
Do you know any algorithms that would do this?
I want an algorithm to find the largest white rectangle in this image. That is to say, the largest rectangle that would fit in an area of white space containing only white space.
Do you know any algorithms that would do this?
Solution
Subtract $254.9999999$ from all pixel values, so black corresponds to $-254.9999999$ and white to $0.0000001$.
Find the 2D subrectangle with maximum sum. There are standard $O(n^3)$-time algorithms for this problem (e.g., https://stackoverflow.com/q/19064133/781723, https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/). As long as you have no more than 10,000,000 pixels in the image, this will be the solution to your problem (since each white pixel contributes another $0.0000001$ to the sum).
Proof that this finds the optimal solution: only all-white subrectangles have a positive sum (if you have a single non-white pixel, then its contributes a negative value of $-0.9999999$ or lower to the sum, which cannot be outweighed by any number of white pixels); and the larger the all-white subrectangle, the larger its sum.
Find the 2D subrectangle with maximum sum. There are standard $O(n^3)$-time algorithms for this problem (e.g., https://stackoverflow.com/q/19064133/781723, https://www.geeksforgeeks.org/maximum-sum-rectangle-in-a-2d-matrix-dp-27/). As long as you have no more than 10,000,000 pixels in the image, this will be the solution to your problem (since each white pixel contributes another $0.0000001$ to the sum).
Proof that this finds the optimal solution: only all-white subrectangles have a positive sum (if you have a single non-white pixel, then its contributes a negative value of $-0.9999999$ or lower to the sum, which cannot be outweighed by any number of white pixels); and the larger the all-white subrectangle, the larger its sum.
Context
StackExchange Computer Science Q#123464, answer score: 3
Revisions (0)
No revisions yet.