Есть задачка с распознаванием образов.
Требуется найти соответствие картинок из одного набора — картинкам из другого набора, по признакам похожести.
Примеры двух наборов — на картинке. Там же помечены некторые правильные соответствия. Картинка увеличина, для лучшего восприятия.
Размер картинок — фиксированный (скажем 17x17).
Изначально картинки цветные, но здесь уже отобраны картинки с одинаковыми преобладающими цветами, поэтому показан только канал яркости.
Ориентация и масштаб объектов, изображенных на картинках — примерно совпадает.
Но не точно, возможны сдвижки и небольшие искажения вращения (до 10 граудсов).
Поэтому попиксельное сранивнение "в лоб" дает плохой результат.
Центр масс у всех картинок находтся в центре.
Сейчас сраваниваю в "лоб", попиксельно, но каждый пиксел сравнивается не только со своим пикселом, но и с его
соседями (то есть фактически с 9 пикселами), затем выбирается минимальная разница...
Метод дает относительно хорошую точность, но совершенно не подходит в плане быстродействия.
Характерный размер первого ряда — до сотни элементов.
Второй ряд — представлет собой БД, и там может быть порядка миллиарда картинок.
Интересуют либо хорошие методы предварительного отбора кандидатов на сравнение, либо средства сортировки кандидатов, либо может какие-то сигнатурные методы сравнения...
Посмотрите в сторону нейронных сетей. Вот нарыл у себя хорошие статьи:
Название: Статьи по нейронным сетям.rar
Размер: 287.90 кб
Доступен до: 2010-09-19 01:52:02
Ссылка для скачивания файла: здесь
Здравствуйте, xobotik, Вы писали:
X>Здравствуйте, BigObfuscator, Вы писали:
X>Посмотрите в сторону нейронных сетей. Вот нарыл у себя хорошие статьи: X>Название: Статьи по нейронным сетям.rar X>Размер: 287.90 кб X>Доступен до: 2010-09-19 01:52:02 X>Ссылка для скачивания файла: здесь
Спасибо за статьи. Однако как здесь мне может помочь нейронная сеть? У меня нет обучения.
У меня есть база картинок, и набор единарозово предъявляемых изображений, которые нужно найти в базе.
А даже если НС и как-то обучить сравнивать изображения, я не думаю, что этот алгоритм мне даст более быстрое сравнение, чем алгоритм написанный вручную.
Здравствуйте, xobotik, Вы писали:
X>Здравствуйте, BigObfuscator, Вы писали:
X>Посмотрите в сторону нейронных сетей. Вот нарыл у себя хорошие статьи: X>Название: Статьи по нейронным сетям.rar X>Размер: 287.90 кб X>Доступен до: 2010-09-19 01:52:02 X>Ссылка для скачивания файла: здесь
ССылки на статьи не дам и подробно объяснить алгоритм не смогу (у нас алгоритмы пишут математики) но мы как раз занимаемся сравниванием изображений.
Сначала ищутся "Corellation points" — характерные "сильные" точки на картинке, которые всегда можно точно идентифицировать и по горизонтали и по вертикали. Потом по ним определяется трансформация между картинками (если в обоих изображениях нашлось достаточно corellation points. Трансформация — это сдвиг, зум и поворот. Потом по зтим результатам трансформируем одну из картинок и вычитаем одну из другой, анализируем результат в зависимости от допустимых изменения яркости и нассыщенности.
Здравствуйте, BigObfuscator, Вы писали:
BO>Интересуют либо хорошие методы предварительного отбора кандидатов на сравнение, либо средства сортировки кандидатов, либо может какие-то сигнатурные методы сравнения...
BO>Спасибо за любые идеи
Как вариант — сделать предварительно Gaussian Blur, после чего считать корелляцию. Сигму конечно же надо подбирать экспериментально. А уже кандидатов проверять более строго. Blur делается довольно быстро, методом БИХ-фильтров, но есть и еще быстрее, типа stack blur. Но главная фишка в том, чтобы иметь быстрый кэш с уже заблюренными изображениями.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, BigObfuscator, Вы писали:
BO>Есть задачка с распознаванием образов.
Как вариант — дарбулызуть спектральным анализом — предварительно сделать 2D FFT и отбирать возможные кандидаты в частотно-фазовом домене, после чего проверять более тщательно уже в пространственном домене. Это может сработать быстрее. Но может быть и медленнее — надо все проверять.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Разбить картинку на четыре части, вычислить центр масс для каждой части, прежде чем сравнивать картинки попиксельно сравнить центры масс для частей, если разница между массами меньше заданной погрешности то сравнивать попиксельно. В базе хранить центры масс частей для каждой картинки. Разбивать можно не только на 4 части, может и пополам хватит.
Здравствуйте, BigObfuscator, Вы писали:
BO>Требуется найти соответствие картинок из одного набора — картинкам из другого набора, по признакам похожести.
Можно попробовать найти всевозможные моменты, можно так называемые Hu invariants и по ним уже сравнивать. Будет гораздо быстрей. Если моменты примерно совпадут, то уточнять твоим методом.
Здравствуйте, Слава, Вы писали:
С>Сначала ищутся "Corellation points" — характерные "сильные" точки на картинке, которые всегда можно точно идентифицировать и по горизонтали и по вертикали. Потом по ним определяется трансформация между картинками (если в обоих изображениях нашлось достаточно corellation points. Трансформация — это сдвиг, зум и поворот. Потом по зтим результатам трансформируем одну из картинок и вычитаем одну из другой, анализируем результат в зависимости от допустимых изменения яркости и нассыщенности.
Приведенные картинки — это уже результат выделения ключевых точек. Изображения уже повернуты и промасштабированы.
Вот в том то и вопрос, что если их просто тупо "вычесть", то получается плохой результат. Картинки маленькие, сдвиг в один пиксел сразу дает огромную разницу при вычитании.
Здравствуйте, McSeem2, Вы писали:
MS>Как вариант — сделать предварительно Gaussian Blur, после чего считать корелляцию. Сигму конечно же надо подбирать экспериментально. А уже кандидатов проверять более строго. Blur делается довольно быстро, методом БИХ-фильтров, но есть и еще быстрее, типа stack blur. Но главная фишка в том, чтобы иметь быстрый кэш с уже заблюренными изображениями.
Да, заблюрить я всегда успею Время на сам блюр не критично, поскольку его можно делать заранее.
Но! Не хотелось бы блюрить. Блюр — это всегда потеря информации. Да и все равно придется все со всем попиксельно сравнивать.
Здравствуйте, McSeem2, Вы писали:
MS>Здравствуйте, BigObfuscator, Вы писали:
BO>>Есть задачка с распознаванием образов.
MS>Как вариант — дарбулызуть спектральным анализом — предварительно сделать 2D FFT и отбирать возможные кандидаты в частотно-фазовом домене, после чего проверять более тщательно уже в пространственном домене. Это может сработать быстрее. Но может быть и медленнее — надо все проверять.
Да, как вариант может быть. Но тут возможно возникнет две проблемы:
1)Из-за того, что изображения маленькие FFT просто может давать плохие, неустойчивые результаты.
2)Возникнет та же проблема что и в пространственном изображении — сдвиг спектра на одну позицию — и сравнение спектров будет малокоррелированным. И как сравнивать такие спектры — непонятно.
Здравствуйте, Driver, Вы писали:
D>Здравствуйте, BigObfuscator, Вы писали:
BO>>...
D>Разбить картинку на четыре части, вычислить центр масс для каждой части, прежде чем сравнивать картинки попиксельно сравнить центры масс для частей, если разница между массами меньше заданной погрешности то сравнивать попиксельно. В базе хранить центры масс частей для каждой картинки. Разбивать можно не только на 4 части, может и пополам хватит.
Здравствуйте, Nuzhny, Вы писали:
N>Здравствуйте, BigObfuscator, Вы писали:
BO>>Требуется найти соответствие картинок из одного набора — картинкам из другого набора, по признакам похожести.
N>Можно попробовать найти всевозможные моменты, можно так называемые Hu invariants и по ним уже сравнивать. Будет гораздо быстрей. Если моменты примерно совпадут, то уточнять твоим методом.
С инвариантами уже игрался, это дает плохой результат. Пальцем в небо можно сказать.
Здравствуйте, BigObfuscator, Вы писали:
BO>Здравствуйте, xobotik, Вы писали:
X>>Здравствуйте, BigObfuscator, Вы писали:
X>>Посмотрите в сторону нейронных сетей. Вот нарыл у себя хорошие статьи: X>>Название: Статьи по нейронным сетям.rar X>>Размер: 287.90 кб X>>Доступен до: 2010-09-19 01:52:02 X>>Ссылка для скачивания файла: здесь
BO>Спасибо за статьи. Однако как здесь мне может помочь нейронная сеть? У меня нет обучения.
Можно и без обучения обойтись. BO>У меня есть база картинок, и набор единарозово предъявляемых изображений, которые нужно найти в базе.
По поводу твоей проблемы.
1) Возьми большое число изображений, найди разумное число главных компонент (штук 8-9) и раскладывай по ним, получишь компактный ключ к базе.
2) Не хочешь компоненты — разбей изображение на уголовые секторы, ключ -- гистограмма плотности распределения сигнальных точек по секторам.
Картинки небольшие.
Уподобим каждую картинку текстовой строке, то есть выложим ее в линию, и закодируем (условно говоря, делать не надо) буквами.
Далее применить алгоритмы схожести текстовых строк.
Идея в том, что сдвиг и ротация приведет к тому, что останутся те же "буквы", только немного сместятся их позиции, и критерий похожести будет большим.
Здравствуйте, Слава, Вы писали:
С>Здравствуйте, xobotik, Вы писали:
X>>Здравствуйте, BigObfuscator, Вы писали:
X>>Посмотрите в сторону нейронных сетей. Вот нарыл у себя хорошие статьи: X>>Название: Статьи по нейронным сетям.rar X>>Размер: 287.90 кб X>>Доступен до: 2010-09-19 01:52:02 X>>Ссылка для скачивания файла: здесь
С>ССылки на статьи не дам и подробно объяснить алгоритм не смогу (у нас алгоритмы пишут математики) но мы как раз занимаемся сравниванием изображений. С>Сначала ищутся "Corellation points" — характерные "сильные" точки на картинке, которые всегда можно точно идентифицировать и по горизонтали и по вертикали. Потом по ним определяется трансформация между картинками (если в обоих изображениях нашлось достаточно corellation points. Трансформация — это сдвиг, зум и поворот. Потом по зтим результатам трансформируем одну из картинок и вычитаем одну из другой, анализируем результат в зависимости от допустимых изменения яркости и нассыщенности.
Если я правильно понял и ты работаешь с Галичем, то скажи ему, что пока этот джентельмен занимается сифтовским онанизмом, мы с китайцами уже сделали проективно инвариантный поиск, скоро начнем гонять.
З.ы. Если не работаешь, то не говори
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, BigObfuscator, Вы писали:
PD>Картинки небольшие. PD>Уподобим каждую картинку текстовой строке, то есть выложим ее в линию, и закодируем (условно говоря, делать не надо) буквами. PD>Далее применить алгоритмы схожести текстовых строк. PD>Идея в том, что сдвиг и ротация приведет к тому, что останутся те же "буквы", только немного сместятся их позиции, и критерий похожести будет большим.
Какие именно алгоритмы?. Если использовать расстояние левенштейна, то на сравнение пары символов придется потратить примерно 10^5 операций, на выбор из базы в 1.5 * 10^9 придется сделать 10^14 операций, имхо жесть.
Здравствуйте, denisko, Вы писали:
PD>>Идея в том, что сдвиг и ротация приведет к тому, что останутся те же "буквы", только немного сместятся их позиции, и критерий похожести будет большим. D>Какие именно алгоритмы?. Если использовать расстояние левенштейна, то на сравнение пары символов придется потратить примерно 10^5 операций, на выбор из базы в 1.5 * 10^9 придется сделать 10^14 операций, имхо жесть.
Я имел в виду функции "нечеткого сравнения строк", которых в Интернете немало. Пусть их точность относительна, а корректность алгоритма даже под сомнением. Но если они быстро отсеят 90% , то к остатку можно применить другие средства.
20.08.2010 17:23, denisko пишет: > > Если я правильно понял и ты работаешь с Галичем, то скажи ему, что пока > этот джентельмен занимается сифтовским онанизмом, мы с китайцами уже > сделали проективно инвариантный поиск, скоро начнем гонять.
Интересно, если считать оставшихся специалистов в конкретных областях
распознавания образов в ExUSSR, пальцев на руках хватит?
