Имеется панорама, составленная из множества кадров: "cканер" ходит по двум координатам, для каждой снимается кадр, потом они сшиваются и т.п. Проблема в том, что ориентация камеры не может быть абсолютно точно выставлена вдоль направления сканера, между ними всегда есть некоторый ненулевой угол. Это приводит к тому, что в совмещенном изображении соседние кадры по X имеют регулярное смещение в несколько пикселов по Y. Сюда еще накладываются ошибки, связанные с позиционированием, вибрацией... , в общем, панорама всегда имеет "зубчатые края".
Задача заключается в том, чтобы найти в ней прямоугольник стандартной ориентации максимального размера. Сейчас это сделано тупым перебором краевых линий, и каждый раз когда я смотрю на код и эффективность его работы меня охватывает уныние.
Есть мысли на тему того, как эту задачу можно решить поумнее?

miksoft, площади.

mayton,
Нет, image stitching или matching - это собственно составление панорамы из фрагментов.
Сабж можно рассматривать как автономную задачу, даже не связанную с изображениями.

mayton,
Я плохо знаю задачи этого класса, с какой-нибудь геометрией...
Регион (как многоугольник) и вписанный в него прямоугольник - вроде достаточно для постановки.

mayton,
OK. Красным обозначена область, зеленым - то, что в ней нужно найти (ну, примерно)

maytonВозможен ли вариант когда есть много решений? Вероятно, да.

maytonВсегда ли стороны красной области параллельны осям? Сторона - это всегда ломаная линия из праллельных оси фрагментов.

mayton,
Я не вижу тут особой разницы, можно и так, и так. Все координаты целочисленные.

mayton,
Не ошибся, монотонность в каких-то фрагментах может нарушаться. Хотя как нулевое приближение, наверное, подойдет. Но я даже тут не вижу хорошего алгоритма.

mayton,
Существует, конечно, обычная задача поиска условного экстремума. Только это уже "-1" приближение, без учета ломаных границ, непонятно даже как к ней перейти.

tchingiz,
Красненькие прямоугольники - это отдельные кадры, они не поворачиваются.

tchingiz, не руками :)
И совмещение делается по схеме parallel-shift.