В данный момент занялся я векторизацией. Первый шажок сделан. Нахожу массив точек.
Суть алгоритма, в-кратце: перевожу картинку в шкалу серого; пробегаю её по Х, находя переход из светлого в тёмное и наоборот, с учётом порога чувствительности (наилучшие результаты для моих картинок даёт чувствительность в 40 единиц, относительно 127.5); пробегаю точно так же по Y, чтобы найти переходы примерно горизонтальных линий; микширую два массива с учётом заданного (любого) минимально допустимого расстояния между соседними точками, как и в случае с проходами по X и по Y; давлю шумы (средневзвешенный цвет участка вокруг каждый точки близок к белому, чёрному или серому (весь участок размыт)).
Получается не плохо: для картинки размером 640*480, при расстоянии между искомыми точками порядка 5..10 пикселей, получаем приемлемое количество точек (для разных условий - от 100 до 1000 штук).
Теперь начинается самое интересное. Надо из найденного массива точек найти линии и окружности.
У меня уже есть алгоритмы, определяющие по методу наименьших квадратов (МНК) линии, окружности и плоскости. Ясно, что их нужно будет использовать. Весь вопрос: как?
Возьмём, к примеру, линию. Если перебрать массив, скажем, из 500 точек, определяя линии для всех комбинаций из трёх точек, а затем взять и выбрать из них линии с приемлемой ошибкой (которая получается по МНК); потом пройтись по всем точкам, и отнести их к тем линиям, расстояние до которых окажется, опять же, вполне приемлемым; а потом сделать ещё один проход, вычисляя линии по МНК уже с учётом бОльшего количества точек, что, несомненно, даст более точные результаты, - то, вроде бы, всё должно получиться. Однако, количество линий для поиска будет просто офигенным. Так никакой памяти не хватит.
Как-то это сильно круто. Такое чувство складывается, что быстрее мой компьютер сдохнет, чем это всё обсчитается. Нужен другой алгоритм. А пока, за неимением других, более перспективных мыслей, попробую этот.

Наверное, на форуме не найдётся никого, кто решил такую задачу. Можно даже поспорить или попринимать на это ставки.

Чё то хреновый какой то алгоритм, погугли на тему: edge detection, hough transform, canny edge detection, feature detection, computer vision etc
Незачем пробегать по изображению 2 раза, по х, потом по у. Изображение обычно обрабатывается матрицей свертки (обычно 3х3 пиксела), иногда называют ядром свёртки. Для выделения края можно к примеру получить 2 изображения по алгоритму Собела с разными матрицами свёртки, а затем усреднить их (найти среднеквадратичное значение яркости 2х пикселов).  

Нормальный алгоритм. Про всякие мудрёные методы я не слыхал, а потому сел, репу почесал, и за день сваял свой алгоритмик нахождения точек. Работает он как раз таки очень качественно и шустро. Все четыре этапа проходят за время, примерно равное времени перевода изображения в шкалу серого. Куда уж лучше то? Меня устраивает. Так что никаких Собелов мне не надо. Я бы дольше искал эти алгоритмы, потом ещё дольше бы в них разбирался, и хрен знает сколько бы потом переделывал да адаптировал под свои задачи. Полная утопия. К таким выводам я пришёл уже давно, а потому лезу что-то искать, если сам не врубаюсь как это можно сделать.
А алгоритм получился простой, компактный и эффективный. Так что я доволен.
Без прохода по Y в моём алгоритме не обойтись. Я уже про это писал. Для строки (Y=const), в которой расположена горизонтальная линия, перехода цвета не будет вообще, либо точек там найдётся совсем не много. А это не есть гуд.

Институт я закончил уже давно (10 лет назад). Так что курс матана позабыл на 99%.
Если кто в душе математик, и кому интересно, можете вывести формулу для количества комбинаций при переборе множества силы N тремя точками?
А то я вчера целый час мозг напрягал, так и не допёр. Старый стал.
Число комбинаций при N=3 - 3; 4 - 4; 5 - 10; 6 - 20...
Ясно, что это будет сумма ряда.
Если для N=1000 это будут какие-нибудь миллиарды, то тогда моя задумка для поиска линий и окружностей не покатит.

Это сообщение отредактировал(а) ilya_z - 15.8.2007, 06:09

Не надо изобретать велосипед, всё придумано уже до вас. Проще изучить метод и качественно его реализовать, чем тратить время и деньги на то что уже есть.
http://planetmath.org/encyclopedia/HoughTransform.html
http://homepages.inf.ed.ac.uk/rbf/HIPR2/hough.htm

сомневаюсь что перебирать пикселы по Y очень шустро.


 

haugh transform для этого и предназначен, можно даже ваш алгоритм для поиска точек использовать, это не важно.

Я решил не лезть в дебри. Сделаю по-своему. Перебирать все комбинации не буду - это тупиковый вариант: 1) очень много комбинаций; 2) результат будет не предсказуем, т.к. будет обнаружено очень много ложных линий (к линии будут отнесены точки на самом деле принадлежащие другим объектам). Сделаю всё проще, уже есть мысли.
Посмотрел я на алгоритм этого Поджилкина (спасибо за ссылку). Там есть интересные мысли, подумаю как их использовать.
Проблему определения линий способом 1, описанным у Поджилкина (в декартовых координатах, когда линия близка к вертикальной, коэффициент "а" (у=а*х+б) стремится в бесконечность), я решил. Всё это детектируется довольно просто. Возникает при этом, конечно, небольшая погрешность, но мне супер точности и не надо.
Я пишу свою CAD-систему для проведения измерений при помощи контрольно-измерительной машины. До кучи решаю проблему проведения измерений с использованием микроскопа: в обычный микроскоп вставляем веб-камеру, кладём измеряемую деталь, и в проходящем свете осуществляем видеозахват картинки; когда есть изображение, векторизуем его, и, применяя масштабирующий коэффициент, определяемый по калибру, вычисляем истинные размеры детали. Погрешность получается приемлемая: при 10-кратном увеличении размеры порядка 1 мм определяются с погрешностью менее 1%, т.е. погрешность таких измерений составляет 10 микрон. Не плохо.

Процесс потихоньку пошёл. Уже выделяю линии и окружности (из точек методом наименьших квадратов). Если они цельные (нет стыковок с другими объектами), - то проблем нет. Но вот чтобы детектировать стыки линий, а также линий и окружностей, - пока алгоритм не придумал. Уже шарики за ролики начинают заезжать с этой векторизацией.
Но и сделанное уже не плохо работает. В прикреплённой фотке - пример векторизации "на автомате", в один проход.
Складывается впечатление, что стыки объектов за один проход никак не определить. Будем думать дальше.

Присоединённый файл ( Кол-во скачиваний: 25 )
 01.jpg 31,10 Kb