7

I've worked with OpenCV Stitching for a while. Now I want to do the last step of stitching: crop image. This leads to find the largest inscribed axis-parallel rectangle in general polygon.

I've already googled it and found some answers (How do I crop to largest interior bounding box in OpenCV?). The quality of output image is good despite the program run slowly (it takes 15 sec to crop image quite takes only 47 sec to stitch 36 1600x1200 pictures into 1 panorama) since the used algorithm have bad time complexity (for each point in the contour, it scan all point in same row/column).

Any way to improve this? Thanks.

P/S: I also found this book:

Finding the Largest Area Axis-Parallel Rectangle in a Polygon

Karen Daniels y Victor Milenkovicz Dan Rothx Harvard University,

Division of Applied Sciences,

Center for Research in Computing Technology,

Cambridge, MA 02138.

June 1995

but I didn't have any idea to implement the theory into code :v

Community
  • 1
  • 1
khôi nguyễn
  • 626
  • 6
  • 15
  • I'd like to point to [this](http://stackoverflow.com/a/32682512/5008845) solution in a similar question. – Miki Sep 20 '15 at 17:59

2 Answers2

6

You probably don't want to implement that algorithm; it would take quite a while, and I suspect that you would be disappointed with the performance in spite of the big-O bound.

It sounds as though you're working with a raster anyway, so you could use a linear-time algorithm for finding the largest rectangle of zeros in a binary matrix.

Community
  • 1
  • 1
David Eisenstat
  • 64,237
  • 7
  • 60
  • 120
  • 2
    A possible solution can be found [here](http://stackoverflow.com/a/32682512/5008845). Thanks for the links! – Miki Sep 20 '15 at 18:03
1

Maybe have a look at this largest interior rectancle implementation. It uses the algorithm described in this paper. An example Image is

enter image description here

At the moment I'm implementing the cropping functionality into the stitching package

Lukas Weber
  • 455
  • 6
  • 13