arrays - find largest rectangle not (necessary) aligned with image boundary in binary matrix -

i using this solution find rectangles aligned image border in binary matrix. suppose want find rectangle not aligned image border, , don't know orientation; fastest way find it?

for sake of example, let's rectangle containing 1's. example:

1 1 1 1 0 0 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 

then algorithm described in solution described above find rectangle of size 6 (3x2). find bigger rectangle tilted; can see rectanble of @ least size 10 or more...

i working in c/c++ algorithm description in language or pseudo-code me lot.

some more details:

• there can more 1 rectangle in image: need biggest only
• the rectangle not beautiful rectangle in image (i adapted example above little bit)
• i work on large images (1280x1024) i'm looking fastest solution (a brute-force o(n³) algorithm slow)
• (optional) if solution can parallellized, plus (then can boost more using gpu, simd, ...)

i have partial answer question, , few thoughts on complexity or speed propose.

brute force

the first idea see use fact problem discrete implement rotation around center of image , repeat algorithm use in order find axis aligned solution.

this has downside of checking whole lot of candidate rotations. however, check can done in parallel since indepedant of 1 another. still slow, although implementing (shouldn't hard) , provide more definite answer question speed once parallelized.

note work-space being discrete matrix, there finite number of rotation browse through.

other approach

the second solution see is:

1. to cut down base matrix to separate connected components [1] (corresponding value set you're interested in).
2. for each 1 of smaller matrices -- note may overlapping depending on distribution -- find minimum oriented bounding box value set you're interested in.
3. still each 1 of those, rotate matrix minimum oriented bounding box axis-aligned.
4. launch algorithm have find maximum axis-aligned rectangle containing values value set.
5. the solution found algorithm the largest rectangle obtained connected components.

this second solution give approximation of soluiton, believe might prove worth trying.

for reference

the solutions have found problem of maximum/largest empty rectangle axis-aligned. have seen many unanswered questions corresponding oriented version of problem on 2d continuous space.

edit:

[1] since want separate connected component, if there degree of overlap, should in following example:

0 1 0 0 0 1 0 1 0 0 0 1 

should divided into:

0 0 0 0 0 0 0 1 0 0 0 1 

and

0 1 0 0 0 1 0 0 0 0 0 0 

note kept original dimensions of matrix. did because i'm guessing post has importance , rectangle expanding further away boundaries not found solution (i.e. can't assume there 0 values beyond border).

edit #2:

the choice of whether or not keep matrix dimensions debatable since not directly influence algorithm.

however, worth noting if matrices corresponding connected components not overlap on non-zero values, may choose store matrices "in-place".

you need consider fact if wish return output coordinates of rectangle, creating matrix different dimensions each connected component, force store coordinates of newly created matrix in original 1 (actually, 1 point, instance up-left one, should enough).