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

Так вот кто Ирак бомбит...

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

DonPager
Поясни, пожалуйста, поподробнее, что это за изображение. Дело в том, что у оружейников есть методики, позволяющие посчитать примерное положение центра прицеливания по распределению пробоин на мишени. Твоя задача хоть чем-то напоминает это?

Цитата

Поясни, пожалуйста, поподробнее, что это за изображение. Дело в том, что у оружейников есть методики, позволяющие посчитать примерное положение центра прицеливания по распределению пробоин на мишени. Твоя задача хоть чем-то напоминает это?

Суть такова:
Есть лазерная пушка, она подаёт сигнал на целевой знак,
с него на комп , а на компе уже всё обрабатывается.
Загвоздка в том что луч немного дёргатся и в зависимомти от угла прихода возникают нелинейные искажения рисунка.
Рисунок выглядит примерно так (звиняйте за размер):
http://galileo.spaceports.com/~donpager/cntr.jpg

Привет, DonPager!

А можно сделать так:
1) выбираем 3 точки на окружности (лучше в трех секторах по 120 градусов);
2) строим треугольник
3) описываем вокруг него окружность
4) находим ее центр (пересечением перпендикуляров из середин сторон)

Ну это конечно же логический алгоритм. На самом деле, если имплементирвать его:

1) выбрать 3 точки (A, B, C)
2) найти уравнения 2-х прямых (AB и BC)
3) находим нормаль в серединах сторон
4) находим точку пересечения нормалей - это и есть наш центр.

Вся проблема в выборе этих трех точек. Хотя я не думаю, что это настолько неразрешимая проблема.

А как такой?
1. Разделить исходную картинку линиями по горизонтали и по вертикали (как бы, т.е. логически). предположим по 2-3 линии. В цикле "по вертикали" проверить все точки по горизонтали. Т.к. цвет круга известен, то при его наличии запоминаем эту точку рисунка в массив точек. И так же в этом же цикле нужно эту же "линию" проверить справа. Т.е. найти правую точку круга. Аналогично и по горизонтали.
В результате получим массив точек, принадлежёщих внешнему ободу. Чем больше "линий", тем больше точек.

2. Из каждой точки в каждую другую "провести" линию. Найти точки пересечения кажой такой линии с каждой другой. Занести все точки пересечений в массив точек #2.

3. Найти распределение позиций этих точек (получится что-то вроде нормального распределения), т.е. завести массив координат с количеством точек для конкретной координаты ну и т.д.

4. Самый большой элемент последнего массива - это и есть центр.

PS: чем больше прочерчиваем горизонтальных/вертикальных линий, тем больше точность.

PPS: вычислительная сложность невелика (я не стану здесь писать её, это IMHO и так видно).

А как такой способ ?

1. Отделяем пикселы мишени от "не-мишени" - переводим всё
в черно-белый формат.
2. Ищем "центр тяжести" для пикселов мишени.

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

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

5. Компенсируем искажения растра.
6. Выполняем ещё раз шаги 1 и 2.

Всё.

А картинки по ссылке нет.

Это сообщение отредактировал(а) Crait - 27.4.2003, 21:11

Цитата

Отделяем пикселы мишени от "не-мишени" - переводим всё в черно-белый формат.

я не переводил в ч/б а искал максимальную светимость (т.к. всё красное),
примерно так

Цитата

Разделить исходную картинку линиями по горизонтали и по вертикали (как бы, т.е. логически). предположим по 2-3 линии. В цикле "по вертикали" проверить все точки по горизонтали. Т.к. цвет круга известен, то при его наличии запоминаем эту точку рисунка в массив точек. И так же в этом же цикле нужно эту же "линию" проверить справа. Т.е. найти правую точку круга. Аналогично и по горизонтали

но для картинки 800х600 пикселей поиск идёт на моём 800 атлоне ~ 5сек ,
нет ли алгоритмика побыстрее

Цитата

А картинки по ссылке нет

таковы реалии халявного хостинга
если нужно посмотреть придтся зайти на
http://galileo.spaceports.com/~donpager/
а потом дописать в адресе cntr.jpg

Цитата

на моём 800 атлоне ~ 5сек  ,

точнее 50 сек

Каковы требования по быстродействию ?
И какой центр истинный - обозначенный перекрестьем
или центр окружностей ?

А чего сайт на народе такой-то кровавый ?
Хотя цепочка из черепов мне понравилась

Это сообщение отредактировал(а) Crait - 28.4.2003, 17:18

Пройти в цикле "по горизонтали" одну строчку рисунка занимает 50 секунд? :? Что-то явно неправильно...

Я могу, просто ради интереса, проверить реализуемость этого алгоритма, напишу программку...

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

Цитата(DonPager @ 28.4.2003, 16:15)

Цитата на моём 800 атлоне ~ 5сек  , точнее 50 сек

Используй ScanLine - будет 5 мс.

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

Хотя это сложновато.