Доброго времени суток!

Помогите найти алгоритм, помогающий решить следующую задачу.
Мы получаем множество точек на плоскости, которое приблизительно напоминает очертаниями прямоугольник. Задача заключается в том, чтобы вписать в эти очертания прямоугольник и определить его стороны. При этом он может быть как угодно повернут относительно осей координат и могут быть различные выступающие части — помехи, которые нужно игнорировать. По этому я думал, по началу, что нужно описывать прямоугольник, но мне кажется, что лучше именно вписывать его, тогда эти аппендиксы будут автоматических проигнорированы. Нашел два алгоритма:
http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/bounding_rotated_ellipses/bounding_rotated_ellipses.html#bounding-rotated-ellipses
и
http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/bounding_rects_circles/bounding_rects_circles.html#bounding-rects-circles
очень похоже, но они описывают прямоугольник вокруг объекта.
Может быть Вы сталкивались с какими то подобными заданиями?

Здравствуйте, alekos, Вы писали:

A>Доброго времени суток!

A>Помогите найти алгоритм, помогающий решить следующую задачу.
A>Мы получаем множество точек на плоскости, которое приблизительно напоминает очертаниями прямоугольник. Задача заключается в том, чтобы вписать в эти очертания прямоугольник и определить его стороны. При этом он может быть как угодно повернут относительно осей координат и могут быть различные выступающие части — помехи, которые нужно игнорировать. По этому я думал, по началу, что нужно описывать прямоугольник, но мне кажется, что лучше именно вписывать его, тогда эти аппендиксы будут автоматических проигнорированы. Нашел два алгоритма:
A>http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/bounding_rotated_ellipses/bounding_rotated_ellipses.html#bounding-rotated-ellipses
A>и
A>http://docs.opencv.org/doc/tutorials/imgproc/shapedescriptors/bounding_rects_circles/bounding_rects_circles.html#bounding-rects-circles
A>очень похоже, но они описывают прямоугольник вокруг объекта.
A>Может быть Вы сталкивались с какими то подобными заданиями?

Мое личное видение решение задачи, не претендующее на полноту или однозначность.
1. Вычисляем центр прямоугольника по среднему координат.
2. Определяем области наиболее удаленные от центра, разбивая их на четыре части. Это можно сделать следующим образом:
— вычисляем среднее удаление от центра Ra;
— сортируем все точки по расстоянию от центра;
— отбрасываем точки, расстояние от центра до которых меньше Ra, тем самым ограничиваем выборку только точками, близкими к краям прямоугольника;
3. Полученные четыре области пересчитываем в четыре средних точки, которые будут первым приближением краев прямоугольника C[4].
Если высокая точность не нужна, на этом можно закончить.
4. Статистически пересчитываем линии краев прямоугольников, учитывая распределение точек относительно сторон прямоугольника по C[4].
5. Пересчитываем C[4] по результатам п.4.
Пп. 4-5 только для повышения точности, особенно если известно статистическое распределение точек.

Здравствуйте, alekos, Вы писали:


A>Мы получаем множество точек на плоскости, которое приблизительно напоминает очертаниями прямоугольник.
A>но мне кажется, что лучше именно вписывать его,
То есть прямоугольник у тебя незакрашенный, и точки из множества (разумеется кроме выбросов) задают его границу, а не заполняют более-менее плотно изнутри? Тогда используй преобразование Хафа.
Если же точек достаточно много, а выбросы единичны, то иногда вообще можно обойтись вычислением центра тяжести, эксцентриситета и угла поворота на основе статистических моментов. А уж потом, полученного приближение уточнять, если это вдруг оказывается нужным.

Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, alekos, Вы писали:


A>>Мы получаем множество точек на плоскости, которое приблизительно напоминает очертаниями прямоугольник.
A>>но мне кажется, что лучше именно вписывать его,
W>То есть прямоугольник у тебя незакрашенный, и точки из множества (разумеется кроме выбросов) задают его границу, а не заполняют более-менее плотно изнутри? Тогда используй преобразование Хафа.
W>Если же точек достаточно много, а выбросы единичны, то иногда вообще можно обойтись вычислением центра тяжести, эксцентриситета и угла поворота на основе статистических моментов. А уж потом, полученного приближение уточнять, если это вдруг оказывается нужным.

Прямоугольник внутри полностью заполнен точками.
Наверное будет проще описать задачу немного по другому. По конвейеру идет коробка, которая может быть повернута как угодно. Множество датчиков, которые она пересекает, формирует массив тех самых точек. Проблема в том, что у коробки могут торчать различные куски пленки и пр. которые нужно отсечь и образмерить коробку.

Здравствуйте, alekos, Вы писали:


A>Прямоугольник внутри полностью заполнен точками.
A>Наверное будет проще описать задачу немного по другому. По конвейеру идет коробка, которая может быть повернута как угодно. Множество датчиков, которые она пересекает, формирует массив тех самых точек. Проблема в том, что у коробки могут торчать различные куски пленки и пр. которые нужно отсечь и образмерить коробку.

Каков приблизительно объем массива?

Можно считать моменты и строить эллипс на основе этих моментов. Таким образом получите ориентацию прямоугольника. Зная ориентацию можно легко найти границы

Здравствуйте, vit_as, Вы писали:

_>Здравствуйте, alekos, Вы писали:


A>>Прямоугольник внутри полностью заполнен точками.
A>>Наверное будет проще описать задачу немного по другому. По конвейеру идет коробка, которая может быть повернута как угодно. Множество датчиков, которые она пересекает, формирует массив тех самых точек. Проблема в том, что у коробки могут торчать различные куски пленки и пр. которые нужно отсечь и образмерить коробку.

_>Каков приблизительно объем массива?

_>Можно считать моменты и строить эллипс на основе этих моментов. Таким образом получите ориентацию прямоугольника. Зная ориентацию можно легко найти границы

Объем приблизительно 1200х800 точек.
Прямоугольник мы впишем. А вот как в этом случае отсечь лишние аппендиксы?

Здравствуйте, alekos, Вы писали:


A>Объем приблизительно 1200х800 точек.
Это бинарное или полутоновое изображение? Информация в точке только вида 0 и 1 или есть данные о яркости?
Можно ли увидеть пример такого изображения?
A>Прямоугольник мы впишем. А вот как в этом случае отсечь лишние аппендиксы?
Фильтрация изображения, морфологические операции типа открытия, закрытия могут откинуть часть шума, чем упростят задачу