Помогите найти алгоритм поиска изображения по маске с учетом изменения яркости и поворота

http://autex.spb.ru/wavelet/articles.htm

Здесь одной ссылкой не обойтись. Такая задача не столько программистская (если ее понимать так глобально, как поставлен вопрос ), сколько научная. Есть в одной докторской диссертации очень оригинальное решение подобной проблемы. На пальцах выглядит так.
Имеем дело с задачей классификации, т.е. отнесения заданного изображения к одному из известных в классе из N. Чтобы нам не усложнял жизнь такой параметр, как яркость, можно эту яркость отнормировать к самой яркой точке. Эта процедура, естественно, делается для всех экземпляров класса и для заданного изображения.
Теперь что делать с поворотом. Мысль такая. Выбирается полярная система координат. Все пикселы изображения упорядочиваются. Т.е. пикселы выстраиваем в ряд. Здесь важно разумно упорядочить. Если в декартовой системе координат упорядочить можно, например, двигаясь из левого верхнего угла картинки в правый нижний, как бы по строкам. То и в полярной системе надо упорядочить по тому же принципу, но в полярных координатах - по углу и расстоянию.
Затем очень важно! Берем первые конечные разности этого ряда, т.е. вычисляем новый ряд по правилу Y(i) = X(i+1) - X(i). Это избавляет от постоянной составляющей и улучшает свойства стационарности.
А от полученного ряда берем (в простом случае) преобразование Фурье.
Оказывается, теперь в частотной области становится не важен угол поворота изображения!
Надеюсь, понятно, что до процедуры сравнения вот эти шаги надо проделать не только для исходной картинки, но для всех экземпляров класса (всех изображений). В принципе, это и будут эталоны, которые надо хранить в базе и поиск наиболее похожего делать по ним.
Вместо преобразования Фурье можно взять преобразование по любому другому базису, который нравится. Вейвлеты, скажем, очень помогут, если изображения зашумлены или расфокусированы.
Да! Собственно поиск наиболее похожего можно делать по разным критериям, зависящим от выбранной метрики: Евклидовой (самая простая), Махаланобиса (работает устойчивее в шумах) и т.д.
Надеюсь, удовлетворил?
Спрашивай, если что.

Dlya Serega.
Pereril kuchu informacii i dumayu, chto wavelet naibolee podhodit dlya moey zadachi, no tam ne vsyo tak ponyatno kak hotelos-bi. Konkretno: po tvoey ssilke vzya stat'yu "Алгоритм распознавания изображений с использованием вейвлет-преобразования.Плекин В.Я., Малышев http://autex.spb.ru/dspa/dspa2000/part2.htm#21.

Esli ti eto ispol'zoval ili razbiraeshsya v walvet'ah ob'asni kak eto mojno primenit' na praktike

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

Mozhet vozmozhno viyasnit' u nego? ochen' uzh nado...

боюсь теперь уже нет, 5 дней назад ушел в отпуск, на 3 недели

Bomzh
Скажи, что конкретно тебе непонятно в той статье.

V (1): j - stepen' razresheniya 0..J. Otkuda ih vzyat'?
V (6): r0 - koefficient rasfokusirovki
V (5): G - kontur izobrazheniya, kak on schitaetsya?

j - это масштабный коэффициент. В вейвет-анализе является аналогом частоты Фурье-анализа. 0...J - количество уровней разложения, включая аппроксимацию и т.н. "детали". J выбирается в зависимости от того, насколько подробно тебя интересуют эти "детали", т.е. высокочастотные составляющие вейвлет-спектра. Если ты действительно перерыл кучу информации, то найдешь методики, по которым можно определить, сколько уровней разложения надо.
Вообще говоря, все зависит от конкретной решаемой задачи. Я пока не понял, почему тебя заинтересовала именно эта статья. Т.к. следующие 2 переменные, которые тебе непонятны, связаны именно с предметной областью - радиолокацией. РЛС строишь?
В радиолокации борются именно с такими эффектами, как расфокусировка,  искажение контура, поэтому и пропускают сигнал через систему специальных фильтров.
А если, к примеру, такой случай. Берем 2 фотографии - твою и мою - в качестве эталонов. Если на вход нашего решающего устройства подать любой из этих же эталонов, то все будет прекрасно работать. Если же подать на вход мою фотографию хорошо сфокусированную и вообще качественно сделанную, но я на ней буду корчить обезьянью рожицу, то тут никакие фильтры уже не помогут. Решающее устройство будет ошибаться.
Если тебе РЛС не надо, то ищи совпадения с эталонами прямо в пространстве вейвлет-образов.
Разложение по вейвлет-базису дает некоторую матрицу, вот и сравнивай матрицу М1 исходной картинки с матрицами эталонов Мэ.
Можно искать по минимуму

Dm = [(X1-Xэ)'*inv(S)*(X1-Xэ)], где X1, Xэ - векторы средних для матриц М1 и Мэ, S - обобщенная ковариационная матрица, inv - операция обращения матриц.

Это т.н. растсояние Махаланобиса. Можно и другие метрики выбрать. Подробности, анпример, в книге "Прикладная статистика" в 3-х т. под ред. Айвазяна.

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

Zadacha sleduyushaya: est' izobrazhenie.Videlyayu pryamougol'nuy oblast'(fragment) i neobhodimo nayti maksimal'no shozhuyu oblast' na drugoy chasti izobrazheniya. Eto vsyo.

To Bomzh: Пожалуйста пользуйтесь транслитом - когда пишите сообщение - у Вас есть там ссылка для автоматического перевода на русский, написание "на молдавском" языке очень утомляет и раздражает, у нас довольно много участников без русской клавиатуры и все прекрасно пользуются этой услугой.

На самом деле, не особо сложно написать такую программу.
Принцип таков:
Создаем матрицу из структур.
Каждая структура содержит описание пикселя.
(это наш кусок)
Создаем еще одну такую матрицу (такого же размера) и заполняем её начиная с первого пикселя (допустим, верхний левый угол)
Затем попиксельно перемещаем вторую матрицу и сравниваем с исходной (тобишь сравниваем цвет.)
Так находим схожую картинку, но с заданным коэффициентом схожести.
Как найти катинку с плавающим коэффициентом? Тож не так сложно, при сравнение вычисляем среднюю схожесть(берется из суммы всех точек) на каждом участке передвижения и записывается(записываем коэффициент и смещение по х,у).
Далее делаем как и в первом случае, токо каждый раз сравнивая с текущим мах коэфф. схожести и если коэфф. прохода больше, то переписываем смещение и коэфф.
Вобщем, если не понятно, могу доходчивей объяснить.

Уже пробовал
for (int y = 0; y < pdy; y++) {
    for (int x = 0; x < pdx; x++) {
int Diff = (int)(*pP++) - (int)(*pS++);
Sum += Diff * Diff;
}
}
if (Sum > MaxSum)
....
Но работает плохо.
Например выделить один глаз на фотке и найти другой - уже не работает...

С глазами хуже, потому как там с одинаковостью цвета совсем плохо...вообще, оно должно работать хоть как-то.

Хоть както работает, но ООчень плохо, а ето не устраивает...

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

Маричный способ распозначания изображений называется "поис по маске". Метод плох так как не имеет алгоритма исскуственного интеллекта. Речь идёт не о том, чтобы написать программу распозначания изображений такими довольно трудоёмкими методами нейросетевое или какой либо другой способ имеющий сложные математические методы. Речь идёт о создании программы которая может например распозначать графические примитивы типа многоугольников и окружностей, но так чтобы алгорит мог учитывать связь между этими примитивами.
Область применения такой программы достаточно большая на пример:
1)распознавание элементов цифровых схем, где примитивами является вентили
2)распознавание и сравнение различных частей двух мерного графика
и т.д.
Кого это интересует звоните : 8-903-250-11-26 Сергей

Стандартный подход к таким задачам - поиск макисмума ковариации двух изображений

Нельзя ли подробней рассказать о нормализации яркости точки?

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

Нда, при предложенном рецепте (среднее=0) у меня фантазии не хватает представить изображение, у которого отдельные пикселы или даже фрагменты будут с яркостью меньше нуля  Картинку-то хочется не просто обрабатывать методами статистики, а еще и смотреть на нее 

Я для изображений реального мира (более-менее сложных сцен или объектов, т.е. не касаясь случая распознавания черных букв на белом фоне) и возможного наличия шумов обычно делаю так:
1. яркость точек на изображении лежит в диапазоне [x,y], x>=0, y<=255.
2. "обрезаю" наиболее яркие и наименее яркие точки (по 1-2% от всего объема точек на изображении) - заменяю их яркости величинами x1>x, y1<y.
3. полученный интервал яркостей [x1,y1] растягиваю на [0,255] и пересчитываю картинку.
Фактически, п.2 можно делать в самом конце, уже при пересчете яркости изображения: заменяя точки с исходной яркостью <=x1 на точки с яркостью 0, а с исходной яркостью >=y1 - на яркость 255.

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

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

Вообще-то операция линейного сдвига - обратима. 

Это так хинт.

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

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

Но, опыт показывает, что существует множество методов где приминяется центрирование. Широкий класс метода главных компонет. Метод зависимых компонет. Некоторын супорт машины. Многие задачи распознавания использующие построение базисов, которые ВСЕГДА содержат нолевой элемент, да и классические методы нормализации освещения часто используют нормализацию среднего и дисперсии.

Вообщем если хотите подискутировать, я за. Как не как сотрудник кафедры обработки изображений. Хотя и младший ;)

Например тут приминяется http://www.cs.umd.edu/~swjoo/reports/739Q_report.pdf

Это сообщение отредактировал(а) esperant0 - 24.10.2006, 17:41

esperant0

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

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

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

3) Ещё для роботов-спамщиков форумских такая программулина очень актуально-полезна.  

Это первая мысль возникшая, когда я открыл эту тему.
Сорри за оффтоп.

Это сообщение отредактировал(а) мухр - 2.11.2006, 09:25

Имеется отсканированное черно-белое изображение на котором изображен план города (кварталы в виде многоугольников) 
+ "мусор"(хаотично разбросанные не нужные линии,текст, которые могут пересекать кварталы или даже могут быть вписаны в кварталы). 
Нужно создать программу, которая бы убирала "мусор" , а именно:
1. Перенос всех многоугольников на компонент Image(или на любой другой контейнер для хранения изображений).
2. Запомнить координаты вершин всех многоугольников, для дальнейшего их редактирования (чтобы можно было потом перемещать точки(вершины) любого многоугольника).

Основная проблема состоит в том что - как определить что это многоугольник а не муссор?
Думаю создать матрицу M изображения размером (Picture.Height X Picture.Width). Если встетился черный пиксел то M[i][j]:=1, если белый то M[i][j]:=0, а как дальше из неё убрать "мусор"(не нужные m[i][j]=1) я не знаю.

Если кто знает ка это сделать подскажите как?