I have a 2D bitmap with various shapes (each pixel is either 1 or 0).
How can I find the largest axis-aligned rectangle that covers only set pixels?
I have a 2D bitmap with various shapes (each pixel is either 1 or 0).
How can I find the largest axis-aligned rectangle that covers only set pixels?
It can be done in $O(n^3)$ time, for a $n\times n$ bitmap.
Let $A$ denote the image, so $A[i,j]$ is the pixel at coordinates $(i,j)$.
For each pixel $(i,j)$, let $H[i,j]$ denote the height of the column of all-1 pixels below it, i.e., the largest $h$ such that $A[i',j]=1$ for all $i' \in [i,i+h-1]$.
For each pixel $(i,j)$ and each height $h$, let $W[i,j,h]$ denote the width of the rectangle of height $h$ with upper-left corner at $(i,j)$ that has covers only set pixels, i.e., the largest $w$ such that $H[i,j'] \ge h$ for all $j' \in [j,j+w-1]$.
You can compute each element of $H$ in $O(1)$ time using dynamic programming (fill them in from the bottom up). Also, once you have $H$, you can compute each element of $W$ in $O(1)$ time using dynamic programming (fill them in the right to left).
Finally, once you have $W$, it is trivial to find the largest rectangle, by scanning all of its elements.
In other words, if you have a $n\times n$ bitmap, you can fill in $H$ in $O(n^2)$ time and fill in $W$ in $O(n^3)$ time, and then you can find the largest rectangle in $O(n^3)$ time. So, this gives an $O(n^3)$ time algorithm. That is an improvement over Pål GD's algorithm, which takes $O(n^4)$ time.
If the bitmap is rectangular rather than square, you can use the same algorithm. I suggest you transpose it first if it is taller than it is wide; that way you will have fewer values of $h$ to iterate over. In this way, if you have a $m\times n$ bitmap, the running time will be $O(\min(mn^2,m^2n))$.