Посоветуйте знающие люди с чего начать, теория, алгоритмы.

alex_kа линия какая?
если кривая - может ли быть замкнутой?
что за поверхность, что еще на поверхности.

и что должно быть на выходе алгоритма?

Нее обычная прямая 2D линия (прямоугольник), с наклоном к одной из осей координат., будет использоваться для калибровки дивайса, На выходе должны быть координаты центра этого прямоугольника. Просто раньше никогда не сталкивался с таким классом задач, поэтому и спрашиваю с чего начинать

maytonВ векторной графике это называется трассировкой. Может поискать по этому ключевому слову?

посоветуй книгу какую нибудь ? ну или ссылку, в поиске, в основном, находит трассировку в различных пакетах: Adobe, Corel и пр

1) Что поступает на вход? Растровая картинка? Цветная? В каком виде? Есть ли на картинке другие фигуры? Картинка зашумлена?


Матрица, элементы который типа byte или long - это будет поверхность, на которой есть некая линия, естественно картинка зашумлена, но это вообщем то не проблема, уже есть фильтры которые убирают некоторые шумы.


2) В каком виде надо получить результирующие координаты? Четыре точки на плоскости? Или центр прямоугольника и угол разворота? Какие требования к времени работы алгоритма (обычно алгоритмы такого класса любят работать о-очень долго).

по времени ничего не скажу, если картинку векторизовать (что предлагалось сделать трассировкой) то это скорее всего будет граф (из которого и нужно будет получить координаты линии). Самый конечный результат это вектор середины прямоугольника - линии, т.н. best fit line - но это уже вторая задача (ее я решу, не проблема).

Есть ли готовые алгоритмы трассировки ? AlgoLab Raster to Vector Conversion Toolkit - не предлогать, нужны исходники алгоритма.

mayton
3.Могут ли линии распадаться на цепочку отдельных точек.


нет, но края линии, плавно переходят в фон, по сути это даже и не линия, а проекция впадины


4. Известен ли размер прямоугольника в пикселях.

глубина, ширина.


5.Точность определения положения центра прямоугольника (~0.5 пикселя? ~0.1 пикселя?)

~ 1 пиксел


6.Время, затраченное на поиск центра прямоугольника.

неважно. центр это 2 задача, будут точные координаты прямоугольника, центр посчитать уже будет не сложно.


Ситуацию, думаю, могла бы сильно прояснить картинка с этим прямоугольником вместе с ответом на последние три вопроса.

В зависимости от ответа на вопросы можно было бы посоветовать автору, как достичь конечного результата с наименьшими затратами.

Если к программе нет каких-то особых требований (например, при наличии сильной зашумленности определять координаты центра с точностью долей пикселя), то задача несложная. В противном случае небольшая задача может превратиться в большую задачу.

хм, ну вы наверное догадывайтесь что запостить рисуночек не получится :) - это не чертеж, наличие большого количества шума.

Меня интересуют чисто теоритические аспекты вопроса и существующие практические реализации, к примеру векторизация (что мне удалось накопать):
1. AutoTrace - http://autotrace.sourceforge.net/index.html - неподходить, в силу определенных специфических особенностей картинки (векторзованный рисунок получается в виде большого множества маленьких векторов).
2. http://www.ocrai.narod.ru/vectory.html (волновой алгоритм для нахождения скелета растрового изображения) - интересный подход, только я не знаком с волновыми алгоритмами, где можно почитать о них еще ?

Другие способы:

3. Cross Corellaton - http://astronomy.swin.edu.au/~pbourke/analysis/correlate/ неподходит, из-за того что образец может быть повернут.

могу еще добавить что фон сильно не однородный, есть идея первоночально отфильтровать картинку Собелем (Sobel), (посмотреть можно тут: http://www.jasonokane.com/tu/351cos/sobel/ )

Vlad17Для меня как раз непонятно, что мешает вырезать из изображения только
прямоугольник с небольшой полоской изображения вокруг контура.


Шумы, картинка даже не векторизуется. Кстати, я все больше склоняюсь к идее волнового алгоритма, сейчас занимаюсь реализацией этого алгоритма, посмотрим что получится. Если получится опубликую результат.

Petro123 Ggg_oldОпубликуйте все-же картинку. Есть очень хороший алгоритм выделения линий на сильно зашумленных изображениях.
если есть алгоритм, то и опубликуй. Или это коммерческое "есть...".

да да опубликуй ну или хотя бы расскажи на чем он основан, как работает ?

Vlad17
Теперь стало совсем непонятно, что мешает автору привести картинку.

Примерно вот так, та область посередине и будет искомой ( не совсем конечно прямоугольник :).

mayton2 Void666

Не совсем понятно. Мы видим много толстых линий. Ты мог бы отметить каким-то ярким цветом (зеленым напр) границы прямоугольника?

ммм, вообщем эти линии паралельны, это пример а не точный имидж, но суть он отражает, скажем так дедектить нужно толстую черную линию.

Ggg_old2Void666:
Да нет, никакой не коммерческий. Если бы вы полазили по инету по сайтам посвященным распознаванию образов и около того, то вы бы наткнулись на этот алгоритм. Называется он Hough Transform. (пишу название по памяти).
Ваша картинка - как раз для этого алгоритма.

Дайте потом хоть знать - получилось ли.
alekcey[gav-gav]ukr[dot]net

ндаа, задача явно выходит из рамок "частного случая", кому интересно, о преобразовании Хафа можно почитать тут:

Преобразование Хафа
Тут на английском
Реализация для окружности

для себя, все таки, я думаю что у меня частный случай, поэтому надо еще подумать...

Ggg_old2Void666:
Да нет, никакой не коммерческий. Если бы вы полазили по инету по сайтам посвященным распознаванию образов и около того, то вы бы наткнулись на этот алгоритм. Называется он Hough Transform. (пишу название по памяти).
Ваша картинка - как раз для этого алгоритма.

Дайте потом хоть знать - получилось ли.
alekcey[gav-gav]ukr[dot]net

Получилось, и весьма неполохо :)
Реализаций туева куча, но только одна из мною расмотренных оказалась самой эффективной (при наличии шумов).