Подобие матриц (картинок), критерий подобия Опции

[Punk]

Здравствуйте, далек от математики, не обессудьте.
Озадачился на выходных такой проблемой: Как установить подобие двух маленьких картинок, можно сказать матриц, размером скажем 50 на 50. Подобие хотелось бы оценивать по пятибальной шкале, ну крайний вариант - по трехбальной. Реально ли решить такую задачу простыми математическими методами? Скажем, посчитать для обоих определители и их сравнить. Хотелось бы применить минимальное количество действий, дабы воплотить этот алгоритм на каком-нибудь маааленьком 8битном микроконтроллере. Задача исключительно ради мозгоразминки.
С уважением.

[Guest_TSerg_*]

Например так:

Для каждой картинки размером N*M:
- переводим в оттенки серого;
- находим средний уровень;
- бинаризируем по среднему уровню;
Получаем N*M битовое слово

Поразрядно сравниваем число совпадений K бит в битовых словах двух картинок (т.е. обе единицы или оба нуля - совпадение).
Степень похожести R := K/(N*M)
При необходимости квантуем до 5-бальной системы.

[SSerge]

http://electronix.ru/forum/index.php?showt...mp;#entry548369

[Kluwert]

Скажем, посчитать для обоих определители и их сравнить.

Посчитать определитель - это, по-вашему, операция с минимальным количеством действий?

[Punk]

Посчитать определитель - это, по-вашему, операция с минимальным количеством действий?

я просто предлагаю варианты, уверен есть лучше, но я оних не знаю, вот и спрашиваю.



По поводу бинаризации: А есть способы без нее? Существует ли вообще универсальный метод определения подобия одноразмерных матриц состоящих из любых чисел?

[Major]

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

[alex_os]

Спектр матрицы полностью определяет ее, но считать спектр долго (дорого).

А собственные вектора получаются информации не несут?

[Guest_TSerg_*]

>По поводу бинаризации: А есть способы без нее?

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

[Major]

Собственные вектора никто не предлагал.
Если матрица эрмитова, то сингулярные и собственные числа будут эквивалентны.
Я про то, что ТС изначально выделил слово "матрица", лишь в скобках написав "картинка".
Если это матрица, то возможно у нее есть свойства, и хватит ее следа для решения задачи.

[alex_os]

Собственные вектора никто не предлагал.
Если матрица эрмитова, то сингулярные и собственные числа будут эквивалентны.
Я про то, что ТС изначально выделил слово "матрица", лишь в скобках написав "картинка".
Если это матрица, то возможно у нее есть свойства, и хватит ее следа для решения задачи.

Мне кажется ТС имел ввиду изначально картинки. А под подобием он понимает не http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%...%B8%D1%86%D1%8B
а некоторую меру идентичности картинок.

[Major]

Для каждого изображения вычисляется:
1. Проектор на ось X (сумма всех точек вдоль У при фиксированном Х)
2. Проектор на ось У (сумма всех точек вдоль Х при фиксированном У)
3. На каждый проектор действуем оптимально-согласованным фильтром F
4. Рассчитываем кросс-корреляционный корреляционный коэф-ты для пар F(X1):F(X2) и F(Y1):F(Y2)
5. Имеем пару чисел и возможно пару значений типа "уровень значимости"
6. Вычисляем взвешенную оценку
7. Градуируем оценку (возможно логарифмически) в пятибалльный диапазон.
Алгоритм может быть полностью целочисленным.
Но на 8бит контроллере это будет утомительно, надо хотя бы 16бит-целую арифметику(знаковую) иметь.
Функция F зависит от типов ожидаемых границ на изображениях.
Как хэш-код такой результат использовать нельзя.
Алгоритм сложнее чем предложил TSerg, и если как корреляционный коэф. использовать знаковый Фехнера, то наверное будет подобие с ним.

[Punk]

Мне кажется ТС имел ввиду изначально...

Вообще, изначально, вопрос пришел из идеи сделать стереоскопический сенсор расстояния из двух камерок от сотика, который бы, примерно определял расстояние до любого предмета, находящегося поблизости от него. И эту операцию я планировал сделать при помощи сравнения картинок. Чем больше сходства, тем предмет ближе. Почему именно так? так захотелось=)

Сообщение отредактировал Punk - Mar 21 2013, 09:47

[alex_os]

Вообще, изначально, вопрос пришел из идеи сделать стереоскопический сенсор расстояния из двух камерок от сотика, который бы, примерно определял расстояние до любого предмета, находящегося поблизости от него. И эту операцию я планировал сделать при помощи сравнения картинок. Чем больше сходства, тем предмет ближе. Почему именно так? так захотелось=)

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

[Punk]

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

Да-да Вы правы. А сумма модулей это сумма модулей разностей ? (надеюсь правильно выразился )

[Guest_TSerg_*]

сдвигать картинку с одного сенсора по оси соединяющей сенсоры. И вычислять сумму модулей разностей пикселей картинок. Сдвиг соответствующий минимуму суммы модулей будет как-то соответствовать расстоянию до предмета.

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

Пример: сканирование картинки 100*100 по горизонтали на 100 px.
( по оси абсцисс 0 - полное совпадение картинок, 100 - полное несовпадение)



P.S.
Впрочем и упомянутый мной алгоритм тоже имеет похожий, хотя и меньший ньюанс.

***************************
Вот такой метод должен работать:

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



***
Для большей наглядности метода несколько идеализируем изображение.
Как видно, есть возможность измерения как дальности, так и угловой ориентации.

[Punk]

***************************
Вот такой метод должен работать:

- находим геометрические центры областей со знаком "плюс" и со знаком "минус"

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

Вот это оно? http://en.wikipedia.org/wiki/Geometric_median

Сообщение отредактировал Punk - Mar 22 2013, 02:24

[Guest_TSerg_*]

Сначала уточню по вычитанию битовых изображений pixLeft[] и pixRight[]:

Логически раскрашиваем разностное изображение pixRes[] следующим образом:
(псевдокод аля Паскаль)

Это необходимо делать при частичном перекрытии объектом самого себя, что не исключено.

if (pixLeft[i,j] = 0) and pixRight[i,j] = 0 then pixRes[i,j] := clWhite;
if (pixLeft[i,j] = 1) and pixRight[i,j] = 1 then pixRes[i,j] := clBlack;
if (pixLeft[i,j] > pixRight[i,j]) then pixRes[i,j] := clRed;
if (pixLeft[i,j] < pixRight[i,j]) then pixRes[i,j] := clBlue;

cl* - условные "цвета" пикселей разностного изображения.

Определение центра тяжести или геометрическиго центра, что для битовых одно и то же.

Для "компактных" объектов может подойти примитивный способ:
X := (Xmin + Xmax)/2;
Y := (Ymin + Ymax)/2;

Но лучше, через дискретное интегрирование:
Координаты ц.т. изображений L и R находим как сумму координат поделенную на число точек:

cntL: integer; // число точек "левого" объекта - площадь в пикселях
cntR: integer; // число точек "правого" объекта - площадь в пикселях
crdLX, crdRX: integer; // координаты ц.т. "левого" объекта, pix
crdLY, crdRY: integer; // координаты ц.т. "правого" объекта, pix


for i := 0 to W-1
for j := 0 to H-1 do begin

if (pixRes[i,j] = clRed) or (pixRes[i,j] = clBlack) then begin
crdLX := crdLX + i + 1; crdLY := crdLY + j + 1;
Inc(cntL);
end;

if (pixRes[i,j] = clBlue) or (pixRes[i,j] = clBlack) then begin
crdRX := crdRX + i + 1; crdRY := crdRY + j + 1;
Inc(cntR);
end;

end;

if cnt* > 0 then
crd* := crd* / cnt*; // для приведения ц.т. в масштаб изображения

***
Пример детектирования расстояния
Shift - установленный сдвиг
Calc - вычисленный по алгоритму выше.



P.S.
ТС задал явные ограничения на мощность MCU и свои возможности, потому предлагается легкий алгоритм, как для MCU, так и для него.
Сложность пропорциональна N.

***
Пример графика заданного и найденного сдвигов
Наблюдаем хорошую линейность и точность до 60 pix ( после 60 pix - выход за границы и вычисления некорректны )

[haker_fox]

С уважением.

Добрый день! Почитай о функции корреляции. В книге "Без паники! Цифровая обработка сигналов", этот вопрос очень подробно рассмотрен.

С уважением.

Добрый день! Почитайте о функции корреляции. В книге "Без паники! Цифровая обработка сигналов", этот вопрос очень подробно рассмотрен.

[AndreyVN]

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

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

[Punk]

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

здесь я распозновать ничего не буду ибо мк не вытянет. Сегодня запустил распознавание образов на OMAP3530, он и то на своих 700х МГц подтормаживает, чего уж говорить о 8ми битниках.

Буду пробовать метод предложенный TSerg

[Guest_TSerg_*]

Буду пробовать метод предложенный TSerg

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