Имеется бинарный (черно-белый) рисунок. Он преобразуется в также бинарный рисунок такого же разрешения. Требуется найти алгоритм для определения насколько второй отличается от первого. Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения. Алгоритм должен давать цифру: "похожесть" либо наоборот "различность" этих образов.
Здравствуйте, Lamot', Вы писали:
L>Имеется бинарный (черно-белый) рисунок. Он преобразуется в также бинарный рисунок такого же разрешения. Требуется найти алгоритм для определения насколько второй отличается от первого. Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения. Алгоритм должен давать цифру: "похожесть" либо наоборот "различность" этих образов.
Если рисунки имеют одинаковый масштаб — то просто наложи один на другой через XOR.
Посчитай количество единичек.
Или тебе нужно проводить какой-то хитрожелтый анализ? Тогда, боюсь, без векторизации не обойдешься.
К>Если рисунки имеют одинаковый масштаб — то просто наложи один на другой через XOR. К>Посчитай количество единичек.
C>Если под "преобразованием" понимается циклический сдвиг на один пиксел, а "рисунок" — это нечто вроде C>101010101 C>010101010 C>101010101 C>... C>... C>101010101
C>то твой алгоритм даст 100% несоответствие. На деле это совсем не так.
Тогда нужно уточнить критерий сравнения.
Любите книгу — источник знаний (с) М.Горький
Re: Требуется подобие для человеческого восприятия
Привет, Lamot'!
L>Имеется бинарный (черно-белый) рисунок. Он преобразуется в также бинарный рисунок такого же разрешения. Требуется найти алгоритм для определения насколько второй отличается от первого. Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения. Алгоритм должен давать цифру: "похожесть" либо наоборот "различность" этих образов.
Человек воспринимает изображение не по пикселам, а в целом. В черно-белом изображении главный фактор — яркость данного места.
Например, если какой-то кусок картинки предполагается серым, а не черным и не белым, то совершенно не важно каким образом эта "серость" задана:
010101 011001
101010 или 100110 или как-то еще.
010101 011001
В обоих случаях равномерно распределенная половина пикселов черная.
Поэтому, задача состоит в том, чтобы в каждый пиксел внести информацию о том, как место вокруг этого пиксела воспринимает человек, какая яркость этого места, а не пиксела. Две картники похожи тогда и только тогда, когда у них схожи все места в смысле восприятия их человеком.
В связи с этим мне кажется разумным применить следующий алгоритм: 1. "Размытие" картинки до 256 (например) градаций серого, путем внесения в каждый пиксел информации о том, что его окружает, как воспринимается окружающее его место в целом. 2. Попиксельное сравнение и подсчет суммы модулей разности значений в пикселах. 3. Критерий определяется из практики. Если сумма, полученная на предыдущем шаге больше, чем alfa*width*height*256, то картинки признаются различными, если нет — схожими.
"Размытие" картинки можно строить, например, следующим образом: каждый пиксел вокруг данного, включая, естественно, саму точку, входит в новое значение с определенным весом.
P.S. Мне настолько понравилась задачка, что я непременно поэкспериментирую с предлагаемым выше алгоритмом (правда когда будет время — может быть ближе к выходным). Если будет что-то интересное — напишу!
Здравствуйте, Apapa, Вы писали:
A>Привет, Lamot'!
L>Имеется бинарный (черно-белый) рисунок. Он преобразуется в также бинарный рисунок такого же разрешения. Требуется найти алгоритм для определения насколько второй отличается от первого. Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения. Алгоритм должен давать цифру: "похожесть" либо наоборот "различность" этих образов.
A>Человек воспринимает изображение не по пикселам, а в целом. В черно-белом изображении главный фактор — яркость данного места.
[] A>Поэтому, задача состоит в том, чтобы в каждый пиксел внести информацию о том, как место вокруг этого пиксела воспринимает человек, какая яркость этого места, а не пиксела. Две картники похожи тогда и только тогда, когда у них схожи все места в смысле восприятия их человеком.
A>В связи с этим мне кажется разумным применить следующий алгоритм: A>1. "Размытие" картинки до 256 (например) градаций серого, путем внесения в каждый пиксел информации о том, что его окружает, как воспринимается окружающее его место в целом. A>2. Попиксельное сравнение и подсчет суммы модулей разности значений в пикселах. A>3. Критерий определяется из практики. Если сумма, полученная на предыдущем шаге больше, чем alfa*width*height*256, то картинки признаются различными, если нет — схожими.
[]
Может бред какой-то, но получилось что-то вроде этого (см. ниже). На самом деле можно поэкспериментировать с алгоритмом "размытия", т.е. сведения в пиксел информации о месте в целом, чтобы обеспечить б'ольшую восприимчивость.
На самом деле, задача состоит из 2 подзадач:
1) растровые искажения (когда изображения совпадают по месту, но есть различные виды blur'а и цветопередачи)
2) векторные искажения (в простейшем виде — сдвиг, затем — масштабирование, повороты, навороты ).
В первом случае — можно копать в сторону wavelet компрессии
во втором, вероятно — фрактальные
О где же вы, Frostbitten'а деянья? ( -_-; ) ... << RSDN@Home 1.0 beta 7a >>
Привет, Кодт!
К>На самом деле, задача состоит из 2 подзадач: К>1) растровые искажения (когда изображения совпадают по месту, но есть различные виды blur'а и цветопередачи) К>2) векторные искажения (в простейшем виде — сдвиг, затем — масштабирование, повороты, навороты ).
Вторая отпадает. По крайней мере я ее сразу отбросил! Было написано:
Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения.
Так что масштабирование, повороты и сдвиги не использовались.
К>В первом случае — можно копать в сторону wavelet компрессии К>во втором, вероятно — фрактальные
Где бы посмотреть?
Здравствуйте, Apapa, Вы писали:
A>Привет, Кодт!
К>На самом деле, задача состоит из 2 подзадач: К>1) растровые искажения (когда изображения совпадают по месту, но есть различные виды blur'а и цветопередачи) К>2) векторные искажения (в простейшем виде — сдвиг, затем — масштабирование, повороты, навороты ). A>Вторая отпадает. По крайней мере я ее сразу отбросил! Было написано: A>
A>Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения.
A>Так что масштабирование, повороты и сдвиги не использовались.
К>В первом случае — можно копать в сторону wavelet компрессии К>во втором, вероятно — фрактальные A>Где бы посмотреть?
Если надо могу выложить кучу доков ... общий размер > 100Mb, но своем хостинге... все сразу выложить не смогу могу почастям.... так что если заинтересовало пишите темы
Здравствуйте, ch00k, Вы писали:
C>А можно узнать, что есть?
1. Вейвлеты — 7 доков (12 Mb)
2. Сегментация >
3 ИНСТИТУТ РАДИОТЕХНИКИ И ЭЛЕКТРОНИКИ РАН В.М. ПОЛЯКОВ "ДИСТАНЦИОННОЕ ЗОНДИРОВАНИЕ ПРИРОДНОЙ СРЕДЫ РАДИОФИЗИЧЕСКИМИ МЕТОДАМИ" — 1 док (2Мb)
4. Что-то по алгоритмам обработки изображений — 4 дока (3.5 Mb)
5. Кое-что по Open GL — 3 дока (1.8 Mb)
6. Кое-что по 3D — ? доков (5 метров) // примечание — разбирался за ненадобностью
7. Исходники KUIM, собственно эти исходники и у них скачать (OpenSource проект) — Библиотека функций ЦОИ (Цифр. Обработки Изобр.) — весьма интересная, реализвана на с, легко портируется на различные платформы (9 метров)
8. Лекции — наиболее интересный материал особенно для начинающих (14 метров)
9. Кое-что по морфологии — (3 метра)
10. Разно-общее — тоже, в принципе, может кое-что заинтересовать и понадобиться — (1.5 метра)
11. Куча pdf-файлов — с кратким описанием тех или иных алгоритмов, толком не разбирался за нехваткой времени (~52 метра)
12. Еще раз разное — то, что не успел отсортировать (~23 метра)
13. Кое-какие дипломные работы выпускников МГУ... (только, что-то мне подсказывает, что это урезанные версии). (3 метра)... Их можно найти на самом сайте МГУ... ссылок не спрашивайте, не помню... не сохранились
14. Сжатие изображений — (0.5 Kb)
15. Сплайны — (0.5 Kb)
16. Фильтры — (1 метр) // примечание: о них лучше читать в лекциях там более подробно
17. Цвет и свет — (1.5 метра)
18. Описание создание различных эффектов — (2.2 метра)
Вейвлеты — 7 доков (12 Mb)
Исходники KUIM,
Лекции — наиболее интересный материал особенно для начинающих (14 метров)
Кое-что по морфологии
Куча pdf-файлов...
Разно-общее
Здравствуйте, Lamot', Вы писали:
L>Имеется бинарный (черно-белый) рисунок. Он преобразуется в также бинарный рисунок такого же разрешения. Требуется найти алгоритм для определения насколько второй отличается от первого. Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения. Алгоритм должен давать цифру: "похожесть" либо наоборот "различность" этих образов.
Я это уже где-то видел. Программы по сравнению отпечатков пальцев (системы поддверждения). В этих системах используется матрица NxN, которая формирует изображение капилярной сетки пальца, вся сложность в том, что картинка каждый раз получается разной, поворот, смещение, пальца, пыль, нечеткое изображение и тд. Наверняка есть по этому вопросу литература.
Здравствуйте, Lamot', Вы писали:
L>Имеется бинарный (черно-белый) рисунок. Он преобразуется в также бинарный рисунок такого же разрешения. Требуется найти алгоритм для определения насколько второй отличается от первого. Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения. Алгоритм должен давать цифру: "похожесть" либо наоборот "различность" этих образов.
Теоретики тебе уже все сказали?
И ты познал духа свово нищету?
Здравствуйте, Lamot', Вы писали:
L>Имеется бинарный (черно-белый) рисунок. Он преобразуется в также бинарный рисунок такого же разрешения. Требуется найти алгоритм для определения насколько второй отличается от первого. Нужно что-то вроде алгоритма сравнения двух растровых несильно (на глаз) отличающихся образов одинакового разрешения. Алгоритм должен давать цифру: "похожесть" либо наоборот "различность" этих образов.
Курить учебник по мат статистике, раздел "нормированный кореллятор Лапласа". Это есть функция, возращающая число от -1.0 до 1.0 : 1.0 для полностью совпадающих изображений, -1 для позитива и негатива. Изображения с >0.7 можно считать похожими, >0.9 очень похожими.
Так как изображения однобитные, то можно очень сильно заоптимизировать.
Приложения
Приложение 1. Определение различия между изображениями.
Приложение 2. Определение яркостей цветов.
Приложение 3. Процедуры вывода изображений.
Приложение 4. Работа с pcx-файлами
Перекуём баги на фичи!
Apapa.gif)
