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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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



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