Jump to content

    

Подобие матриц (картинок)

Здравствуйте, далек от математики, не обессудьте.

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

С уважением.

Share this post


Link to post
Share on other sites
Guest TSerg

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

 

Для каждой картинки размером N*M:

- переводим в оттенки серого;

- находим средний уровень;

- бинаризируем по среднему уровню;

Получаем N*M битовое слово

 

Поразрядно сравниваем число совпадений K бит в битовых словах двух картинок (т.е. обе единицы или оба нуля - совпадение).

Степень похожести R := K/(N*M)

При необходимости квантуем до 5-бальной системы.

 

 

Share this post


Link to post
Share on other sites
Скажем, посчитать для обоих определители и их сравнить.

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

Share this post


Link to post
Share on other sites
Посчитать определитель - это, по-вашему, операция с минимальным количеством действий?

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

 

 

 

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

Share this post


Link to post
Share on other sites

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

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

Если картинки плохо обусловлены (мало перепадов яркости), то наверное придется хранить практически весь спектр.

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

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

 

Share this post


Link to post
Share on other sites
Спектр матрицы полностью определяет ее, но считать спектр долго (дорого).

 

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

 

Share this post


Link to post
Share on other sites
Guest TSerg

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

 

Так это копеечная операция - сравнение с порогом и присваивание очередному биту 1 или 0.

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

 

 

Share this post


Link to post
Share on other sites

Собственные вектора никто не предлагал.

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

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

Если это матрица, то возможно у нее есть свойства, и хватит ее следа для решения задачи.

Share this post


Link to post
Share on other sites
Собственные вектора никто не предлагал.

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

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

Если это матрица, то возможно у нее есть свойства, и хватит ее следа для решения задачи.

 

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

а некоторую меру идентичности картинок.

 

 

Share this post


Link to post
Share on other sites

Для каждого изображения вычисляется:

1. Проектор на ось X (сумма всех точек вдоль У при фиксированном Х)

2. Проектор на ось У (сумма всех точек вдоль Х при фиксированном У)

3. На каждый проектор действуем оптимально-согласованным фильтром F

4. Рассчитываем кросс-корреляционный корреляционный коэф-ты для пар F(X1):F(X2) и F(Y1):F(Y2)

5. Имеем пару чисел и возможно пару значений типа "уровень значимости"

6. Вычисляем взвешенную оценку

7. Градуируем оценку (возможно логарифмически) в пятибалльный диапазон.

Алгоритм может быть полностью целочисленным.

Но на 8бит контроллере это будет утомительно, надо хотя бы 16бит-целую арифметику(знаковую) иметь.

Функция F зависит от типов ожидаемых границ на изображениях.

Как хэш-код такой результат использовать нельзя.

Алгоритм сложнее чем предложил TSerg, и если как корреляционный коэф. использовать знаковый Фехнера, то наверное будет подобие с ним.

Share this post


Link to post
Share on other sites
Мне кажется ТС имел ввиду изначально...

 

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

Edited by Punk

Share this post


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

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

Share this post


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

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

Share this post


Link to post
Share on other sites
Guest TSerg
сдвигать картинку с одного сенсора по оси соединяющей сенсоры. И вычислять сумму модулей разностей пикселей картинок. Сдвиг соответствующий минимуму суммы модулей будет как-то соответствовать расстоянию до предмета.

 

Возможны неоднозначности при наличии однородного фона и предмета.

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

 

Пример: сканирование картинки 100*100 по горизонтали на 100 px.

( по оси абсцисс 0 - полное совпадение картинок, 100 - полное несовпадение)

 

a192d323d138t.jpg

 

P.S.

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

 

***************************

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

 

- перевод в шкалу серого;

- бинаризация;

- вычитание изображений ( получим матрицу с элементами -1; 0; +1 )

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

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

 

775616003e1bt.jpg

 

***

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

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

 

f56194b4aea2t.jpg

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this