Алгоритм нахождения

← →
Pavelius © (2004-04-14 16:42) [0]

Так как этот форум был раньше и по алгоритмам, то вопрос такой.

Существует следующая задача.

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

Помогите пожалуйста с алгоритмами для этой задачи.

← →
Мараканец © (2004-04-14 17:09) [1]

может так получится:
for r = 1 to X do
begin
находить количество точек имеющих преобладающий цвет %)
ну можно собрать все точки и отсортировать и выбрать
преобладающий цвет
и так на каждом новом проходе сверять с преидущим
значением пока не произойдет резкое изменение
преобладающего цветацвета
end;

%)

← →
TButton © (2004-04-14 18:24) [2]

1. спрашиваем у пользователя цвет окружности. например предлагаем тыкнуть по ней.

2. спрашиваем допустимое отклонение. чем четче и однороднее закрашеная окружность тем меньше допуск.

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

3. сканируем строки сверху вниз, ищем первую и последнюю строку в которой есть пикселы принадлежащие окружности.

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

радиус - есть половина от среднего двух чисел
1 = последний столбец - первый
2 = последняя строка - первая

координаты центра
X = (последний столбец - первый)/2 + первый столбец
Y = (последняя строка - первая)/2 + первая строка

← →
Мараканец © (2004-04-14 18:29) [3]

а если края не четкие, т.е. чать пикселов обозночающих край отсутствует???
и круг хоть и обозначен но закрашен с погрешностью.

может стоит написать код? я не думаю что он будет слишком сложным....

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

← →
TButton © (2004-04-14 20:13) [4]

>а если края не четкие, т.е. чать пикселов обозночающих край отсутствует???
>и круг хоть и обозначен но закрашен с погрешностью.

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

но в целом алгоритм, имхо, правильный.

← →
Мараканец © (2004-04-14 20:16) [5]

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

← →
wiz © (2004-04-14 20:43) [6]

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

Ты представляешь свою картинку как функцию яркости от двух координат g(x,y) и задашь теоретическую функцию как:
| A, sqrt(sqr(x-B)+sqr(y-C))<D f(x,y)=| | 0, иначе
итого, у тебя четыре неизвестных (A,B,C,D).

функция ошибки стандартная: S = summ( sqr( f(x,y) - g(x,y) ) );
(сумма по всем x и y);

все эти входные данные подсовываешь какому-нибудь классическому алгоритму:
а) Метод деформируемого многоугольника (Нелдера-Мида)
(этот почти наверняка сработает)

или
б) Метод покоординатного спуска (Хука-Дживса)
(этот тоже наверное сработает, хоть он и проще)

(что-либо более навороченное брать imho не имеет смысла)

← →
Pavelius © (2004-04-15 08:02) [7]

Марканец пришли мне пожалуйста.

wiz, а ты не мог бы еще и алгоритмы описать:
а) Метод деформируемого многоугольника (Нелдера-Мида)
б) Метод покоординатного спуска (Хука-Дживса)

Буду премного благодарен

← →
Мараканец © (2004-04-15 08:05) [8]

я бы тебе прислал, знать бы только куда?

← →
Pavelius © (2004-04-15 08:13) [9]

pshipilin#mail.ru

← →
MBo © (2004-04-15 08:34) [10]

кроме круга, на картинке еще что-то есть?

← →
Pavelius © (2004-04-15 09:04) [11]

Ок, уточню условия задачи.

В указанной области (x,y)-(x1,y1) предположительно есть только одна окружность плюс разного рода шум (плохое качество картинки, полученной со сканера). Окружность может быть частично "размыта": отсутствие части пикселов, неполный край. Нам надо очистить картинку от шума, степень очистки можно менять для улучшения результата. И на получившимся изображении искать что то похожее на окружность, некое подобие ее. В принципе можно еще указать погрешность нахождения.
Ну и можно еще реализовать дополнительно нахождение большего количества окружностей в данной области.

Чтобы Вам было интереснее поработать над этой задачей я решил предоставить финансовое вознаграждение за решенную задачу и предоставления ее в виде программы с исходным кодом. Ну, а сумма будет в пределах от 50 до максимум 100 у.е. естественно от степени реализации

← →
wiz © (2004-04-15 09:05) [12]

2 Pavelius:
набираем в яндексе названия и читаем до полного просветления

← →
Anatoly Podgoretsky © (2004-04-15 09:08) [13]

Почему был? Вот сегодняшняя вырезка из правил

Игры. Построение игр (разработка алгоритмов, написание игр)

http://delphimaster.ru/forums.shtml

← →
Pavelius © (2004-04-15 09:18) [14]

to Anatoly Podgoretsky
просто раньше явно был указан, а сейчас не очень :), хотя я могу ошибаться

to wiz:

Просто задачу надо максимально быстро решить.

to all:
и из-за того что ее надо решить быстро я предоставляю финансовое вознаграждение.

← →
wiz © (2004-04-15 09:22) [15]

2 Pavelius:

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

← →
Morfy (2004-04-15 09:22) [16]

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

← →
wiz © (2004-04-15 09:30) [17]

2 Pavelius:

еще пара вопросов (если серьёзно подходить к задаче)

1. картинка (как и окружность) ч/б или мы работаем в цвете?
2. примерные размеры изображения и примерные размеры окружности
3. ограничения на время выполнения алгоритма (по порядку величины: миллисекунды, секунды, часы (т.е. не важно))

(ну и еще один вопрос не по алгоритму: срочность?)

← →
Pavelius © (2004-04-15 09:53) [18]

to Morfy:
Никакого человека с тыканием на кнопки мыши, только компьютер и наши параметры.

to wiz:

Насчет картинки, ее можете делать сами, просто придерживайтесь следующего: Окружность должна быть больше похожа на окружностью, а не на овал. Радиус гдето от 5 мм до 20 мм. В точках сколько будет не знаю. И еще надо будет несколько видов изображений: с шумом, с неполной окружностью, для того чтобы проверить качество алгоритма

1. Даже если она и в цвете, мы ее приводим в черно-белое изображение и в дальнейшем работаем только Ч/Б
2. Мы может сами указывать, чтобы более универсальный был
3. Ограничения по времени: гдето для размеров области 10 см на 10 см не больше пары секунд.

На реализацию: около недели
Вознаграждение гарантирую !

← →
Anatoly Podgoretsky © (2004-04-15 10:09) [19]

Pavelius © (15.04.04 09:18) [14]
Место для дополнительных пунктов меню освобождали

← →
wiz © (2004-04-15 10:16) [20]

2 Pavelius:

хорошо бы еще знать отношение сигнал/шум на изображении...

если 0.3 и меньше, то без меня... это задачка не на одну неделю

(0.3 это отношение, при котором человек уверенно (и почти мгновенно) устанавливает параметры объекта, 0.1 еще почти без труда различает, 0.03 глаз уже не видит)

← →
wiz © (2004-04-15 10:29) [21]

2 Pavelius:

(в предыдущем post"е я описался... за 0.3 я еще готов побороться)

кстати, тут всплыл еще один вопрос: требуемая точность в поиске размеров/положения???

← →
Pavelius © (2004-04-15 10:42) [22]

to wiz [20]

Шум минимальный

← →
Pavelius © (2004-04-15 10:51) [23]

to wiz [21]

Размер мы как бы изначально знаем, приблизительное расположение тоже. А как насчет ввода коэффициента точности ?

← →
wiz © (2004-04-15 11:15) [24]

2 Pavelius:

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

← →
KA_ © (2004-04-15 11:25) [25]

>Pavelius © (14.04.04 16:42)

Тебе надо сначала избавиться от шума, думаю медианный фильтр здесь будет то что надо.
Дальше надо найти на этой отфильтрованной картинке контур окружности - самым простым пороговым методом.
В итоге получишь последовательность точек - контур, а его надо аппроксимировать до окружности.

Задача достаточно тривиальная, если на картинке только окружность и качество не совсем ужасное.

← →
KA_ © (2004-04-15 11:31) [26]

Пояснения:
1. Медианная филтрация - такое изменение картинки, когда для каждой ее точки рассматривается область вокруг нее, вычисляется среднее значение интенсивности и присваивается этой точке.
Области обычно берут квадратные. Чем больше размер картинки, тем больше сглаживание и меньше шума.
2. Пороговый метод поиска контуров - просматриваются последовательно все пары соседних точек на картинке. Если перепад интенсивности больше некоторого порогового значения, то в этом месте находится граница объекта, т.е. контур

← →
Pavelius © (2004-04-15 11:36) [27]

to wiz
Ничего страшного мне реализация нужна максимум через неделю

to KA_

А помочь в реализации не хотите ?

to ALL

Реализация задачи будет вознаграждена

← →
Pavelius © (2004-04-15 11:38) [28]

На реализацию у меня просто нет времени. Вот я Вас уважаемые и прошу, да к тому же за вознаграждение.

← →
KA_ © (2004-04-15 11:40) [29]

>Pavelius © (15.04.04 11:38) [28]

О! Я не все читал! Здесь и деньги дают :)
За 50 баксов сварганю - пиши в мыло :)

← →
KA_ © (2004-04-15 11:43) [30]

Кстати, есть еще несколько методов поиска площадных объектов на растре.
1. Можно использовать преобразование Хаффа (Hough). Но это достаточно ресурсоемказ задача - работать будет медленно, хотя зависит от конкретных условий распознавания.
2. Если круг маленький (занимает скажем 10% от площади картинки), то пожно применить пирамидальное преобразование растра.

← →
KA_ © (2004-04-15 11:47) [31]

>wiz © (15.04.04 10:16) [20]

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

← →
Pavelius © (2004-04-15 12:47) [32]

to ALL
Если есть еще какие то вопросы по задаче, задавайте

← →
KA_ © (2004-04-15 12:57) [33]

>Pavelius © (15.04.04 12:47) [32]

Большая окружность или нет? Много места она занимает на этом куске 10х10?

to KA_

see to EMail

← →
sergey_shandar (2004-04-15 14:04) [35]

На С++ за вознаграждение можно реализовать алгоритм. В не зависимости от ответа, идея здесь http://www.rsdn.ru/Forum/Message.aspx?mid=607696 и здесь http://www.rsdn.ru/Forum/Message.aspx?mid=607412.

to sergey_shandar
Спасибо за указание в каком направлении надо двигаться

← →
smb (2004-04-15 20:59) [37]

http://smb.hotmail.ru/files/spsearch2.exe
качайте исходник. работает иногда криво, файлы, которые тестировал там же. можно выбрать цвет и расхождение, или как оно там называется, короче цвет+-расхождение. для начала расчета нажать на картинку. радиус будет на заголовке формы.
зы. говорите, что хотите - люблю когда на меня гонят :)

2 Pavelius:

поиск одинокого круга на тестовом изображении. версия нулевая:

http://wad-fox.chat.ru/im_searcher.zip

Для поиска координат круга использованы профильные гистограммы и метод моментов. Для поиска радиуса использовано "эдакое нечто", что я пока сам не могу классифицировать :)

Алгоритм отвратительно работает в случае отрезки части круга, но это можно пофиксить дальнейшими "уточняющими" алгоритмами (чем я займусь, если это будет интересно "заказчику").

to wiz

see to email

Уважаемые мастера, что повашему проще находить: окружность или другие примитивы ?

← →
sergey_shandar (2004-04-17 07:44) [41]

Если примитив хорошо описываеться аналитически и можно решить МНК для него, то все равно. Прямая линия и окружность IMHO легче чем квадрат :-)

Не мастер. :-)

>sergey_shandar (17.04.04 07:44) [41]

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

2 KA_:

профильные диаграммы - довольно тупая весчь: берём некий массив (AxB), усредняем по одной координате и получаем массив 1xB или Ax1. В нём уже довольно легко определить нужное нам (т.к. одномерный случай). Этот способ (конечно) даёт большую ошибку, и всерьез может использоваться только как первая "пристрелка", чтобы более сложные алгоритмы стартовали не с "нуля".

Способ взят на вооружение из некой книги по аппроксимации (названия и автора уже не помню - давно было). Там правда они imho назывались немного по другому (или так как я их обозвал, или "покоординатные гистограммы", в общем - не помню :] )

>wiz © (19.04.04 20:01) [44]

Спасибо. А то я напугался :)

>Этот способ (конечно) даёт большую ошибку

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

2KA_:

в предложеной проге я как раз сглаживаю полученные гистограммы, считаю "средний шум" и вычитаю его...

>wiz © (20.04.04 13:59) [46]

ИМХО, такое сглаживание сильно зависит от зашумленности изображения. Лучше, наверное, использовать преобразование Фурье над полученной гистограммой и отбросить шумы с нее.

Алгоритм нахождения Найти похожие ветки