Punk 0 19 марта, 2013 Опубликовано 19 марта, 2013 · Жалоба Здравствуйте, далек от математики, не обессудьте. Озадачился на выходных такой проблемой: Как установить подобие двух маленьких картинок, можно сказать матриц, размером скажем 50 на 50. Подобие хотелось бы оценивать по пятибальной шкале, ну крайний вариант - по трехбальной. Реально ли решить такую задачу простыми математическими методами? Скажем, посчитать для обоих определители и их сравнить. Хотелось бы применить минимальное количество действий, дабы воплотить этот алгоритм на каком-нибудь маааленьком 8битном микроконтроллере. Задача исключительно ради мозгоразминки. С уважением. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Гость TSerg 19 марта, 2013 Опубликовано 19 марта, 2013 · Жалоба Например так: Для каждой картинки размером N*M: - переводим в оттенки серого; - находим средний уровень; - бинаризируем по среднему уровню; Получаем N*M битовое слово Поразрядно сравниваем число совпадений K бит в битовых словах двух картинок (т.е. обе единицы или оба нуля - совпадение). Степень похожести R := K/(N*M) При необходимости квантуем до 5-бальной системы. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
SSerge 4 19 марта, 2013 Опубликовано 19 марта, 2013 · Жалоба http://electronix.ru/forum/index.php?showt...mp;#entry548369 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Kluwer 0 20 марта, 2013 Опубликовано 20 марта, 2013 · Жалоба Скажем, посчитать для обоих определители и их сравнить. Посчитать определитель - это, по-вашему, операция с минимальным количеством действий? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Punk 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Посчитать определитель - это, по-вашему, операция с минимальным количеством действий? я просто предлагаю варианты, уверен есть лучше, но я оних не знаю, вот и спрашиваю. По поводу бинаризации: А есть способы без нее? Существует ли вообще универсальный метод определения подобия одноразмерных матриц состоящих из любых чисел? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Major 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Если можно вычислять, то вычисляете спектр матрицы (сингулярные числа). После этого выделяете области кучности и отбрасываете лишнее по малости. Если картинки плохо обусловлены (мало перепадов яркости), то наверное придется хранить практически весь спектр. Спектр матрицы полностью определяет ее, но считать спектр долго (дорого). Если у вас есть доп. инфо о картинках (например процесс их генерации), то можно попробовать поискать другие параметры. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alex_os 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Спектр матрицы полностью определяет ее, но считать спектр долго (дорого). А собственные вектора получаются информации не несут? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Гость TSerg 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба >По поводу бинаризации: А есть способы без нее? Так это копеечная операция - сравнение с порогом и присваивание очередному биту 1 или 0. Делается как раз для того, чтобы в дальнейшем свести вычисление отклонения к такой же простейшей операции, как подсчет числа лог. 1 и 0 в двух длинных числах. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Major 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Собственные вектора никто не предлагал. Если матрица эрмитова, то сингулярные и собственные числа будут эквивалентны. Я про то, что ТС изначально выделил слово "матрица", лишь в скобках написав "картинка". Если это матрица, то возможно у нее есть свойства, и хватит ее следа для решения задачи. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alex_os 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Собственные вектора никто не предлагал. Если матрица эрмитова, то сингулярные и собственные числа будут эквивалентны. Я про то, что ТС изначально выделил слово "матрица", лишь в скобках написав "картинка". Если это матрица, то возможно у нее есть свойства, и хватит ее следа для решения задачи. Мне кажется ТС имел ввиду изначально картинки. А под подобием он понимает не http://ru.wikipedia.org/wiki/%D0%9F%D0%BE%...%B8%D1%86%D1%8B а некоторую меру идентичности картинок. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Major 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Для каждого изображения вычисляется: 1. Проектор на ось X (сумма всех точек вдоль У при фиксированном Х) 2. Проектор на ось У (сумма всех точек вдоль Х при фиксированном У) 3. На каждый проектор действуем оптимально-согласованным фильтром F 4. Рассчитываем кросс-корреляционный корреляционный коэф-ты для пар F(X1):F(X2) и F(Y1):F(Y2) 5. Имеем пару чисел и возможно пару значений типа "уровень значимости" 6. Вычисляем взвешенную оценку 7. Градуируем оценку (возможно логарифмически) в пятибалльный диапазон. Алгоритм может быть полностью целочисленным. Но на 8бит контроллере это будет утомительно, надо хотя бы 16бит-целую арифметику(знаковую) иметь. Функция F зависит от типов ожидаемых границ на изображениях. Как хэш-код такой результат использовать нельзя. Алгоритм сложнее чем предложил TSerg, и если как корреляционный коэф. использовать знаковый Фехнера, то наверное будет подобие с ним. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Punk 0 21 марта, 2013 Опубликовано 21 марта, 2013 (изменено) · Жалоба Мне кажется ТС имел ввиду изначально... Вообще, изначально, вопрос пришел из идеи сделать стереоскопический сенсор расстояния из двух камерок от сотика, который бы, примерно определял расстояние до любого предмета, находящегося поблизости от него. И эту операцию я планировал сделать при помощи сравнения картинок. Чем больше сходства, тем предмет ближе. Почему именно так? так захотелось=) Изменено 21 марта, 2013 пользователем Punk Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alex_os 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Вообще, изначально, вопрос пришел из идеи сделать стереоскопический сенсор расстояния из двух камерок от сотика, который бы, примерно определял расстояние до любого предмета, находящегося поблизости от него. И эту операцию я планировал сделать при помощи сравнения картинок. Чем больше сходства, тем предмет ближе. Почему именно так? так захотелось=) Наверное чем меньше сходство тем ближе? Тогда такой вариант, сдвигать картинку с одного сенсора по оси соединяющей сенсоры. И вычислять сумму модулей разностей пикселей картинок. Сдвиг соответствующий минимуму суммы модулей будет как-то соответствовать расстоянию до предмета. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Punk 0 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба Наверное чем меньше сходство тем ближе? Тогда такой вариант, сдвигать картинку с одного сенсора по оси соединяющей сенсоры. И вычислять сумму модулей разностей пикселей картинок. Сдвиг соответствующий минимуму суммы модулей будет как-то соответствовать расстоянию до предмета. Да-да Вы правы. А сумма модулей это сумма модулей разностей ? (надеюсь правильно выразился :rolleyes: ) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Гость TSerg 21 марта, 2013 Опубликовано 21 марта, 2013 · Жалоба сдвигать картинку с одного сенсора по оси соединяющей сенсоры. И вычислять сумму модулей разностей пикселей картинок. Сдвиг соответствующий минимуму суммы модулей будет как-то соответствовать расстоянию до предмета. Возможны неоднозначности при наличии однородного фона и предмета. Кроме того, в зависимости от пестроты будет наблюдаться значительная нелинейность. Пример: сканирование картинки 100*100 по горизонтали на 100 px. ( по оси абсцисс 0 - полное совпадение картинок, 100 - полное несовпадение) P.S. Впрочем и упомянутый мной алгоритм тоже имеет похожий, хотя и меньший ньюанс. *************************** Вот такой метод должен работать: - перевод в шкалу серого; - бинаризация; - вычитание изображений ( получим матрицу с элементами -1; 0; +1 ) - находим геометрические центры областей со знаком "плюс" и со знаком "минус" - дистанция между геом. центрами будет соответствовать параллаксу, а значит и расстоянию. *** Для большей наглядности метода несколько идеализируем изображение. Как видно, есть возможность измерения как дальности, так и угловой ориентации. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться