Здравствуйте, Driver, Вы писали:

D>Здравствуйте, BigObfuscator, Вы писали:

D>...

D>можно подробней о вычислении сигнатуры?

Ну конкретно в данном случае использовалась сигнатура типа такой (псевдокод):

foreach(x)
foreach(y)
  signature += pixel[x,y] - (x^2+y^2);

(центр координат — в центре изображения)

В первом приближении дает неплохой результат. Хотя сейчас я уже перешел к более точным методам.

Добрый день, коллеги.

Есть задачка с распознаванием образов.
Требуется найти соответствие картинок из одного набора — картинкам из другого набора, по признакам похожести.
Примеры двух наборов — на картинке. Там же помечены некторые правильные соответствия. Картинка увеличина, для лучшего восприятия.

Размер картинок — фиксированный (скажем 17x17).
Изначально картинки цветные, но здесь уже отобраны картинки с одинаковыми преобладающими цветами, поэтому показан только канал яркости.
Ориентация и масштаб объектов, изображенных на картинках — примерно совпадает.
Но не точно, возможны сдвижки и небольшие искажения вращения (до 10 граудсов).
Поэтому попиксельное сранивнение "в лоб" дает плохой результат.
Центр масс у всех картинок находтся в центре.
Сейчас сраваниваю в "лоб", попиксельно, но каждый пиксел сравнивается не только со своим пикселом, но и с его
соседями (то есть фактически с 9 пикселами), затем выбирается минимальная разница...
Метод дает относительно хорошую точность, но совершенно не подходит в плане быстродействия.
Характерный размер первого ряда — до сотни элементов.
Второй ряд — представлет собой БД, и там может быть порядка миллиарда картинок.

Интересуют либо хорошие методы предварительного отбора кандидатов на сравнение, либо средства сортировки кандидатов, либо может какие-то сигнатурные методы сравнения...

Спасибо за любые идеи

Здравствуйте, BigObfuscator, Вы писали:

Посмотрите в сторону нейронных сетей. Вот нарыл у себя хорошие статьи:
Название: Статьи по нейронным сетям.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. Но главная фишка в том, чтобы иметь быстрый кэш с уже заблюренными изображениями.

Здравствуйте, BigObfuscator, Вы писали:

BO>Есть задачка с распознаванием образов.

Как вариант — дарбулызуть спектральным анализом — предварительно сделать 2D FFT и отбирать возможные кандидаты в частотно-фазовом домене, после чего проверять более тщательно уже в пространственном домене. Это может сработать быстрее. Но может быть и медленнее — надо все проверять.

Здравствуйте, BigObfuscator, Вы писали:

BO>...

Разбить картинку на четыре части, вычислить центр масс для каждой части, прежде чем сравнивать картинки попиксельно сравнить центры масс для частей, если разница между массами меньше заданной погрешности то сравнивать попиксельно. В базе хранить центры масс частей для каждой картинки. Разбивать можно не только на 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>Спасибо за статьи. Однако как здесь мне может помочь нейронная сеть? У меня нет обучения.

Посмотрите в сторону "Самоорганизующиеся нейронные сети Кохонена".

Здравствуйте, 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) Не хочешь компоненты — разбей изображение на уголовые секторы, ключ -- гистограмма плотности распределения сигнальных точек по секторам.

Здравствуйте, BigObfuscator, Вы писали:

Картинки небольшие.
Уподобим каждую картинку текстовой строке, то есть выложим ее в линию, и закодируем (условно говоря, делать не надо) буквами.
Далее применить алгоритмы схожести текстовых строк.
Идея в том, что сдвиг и ротация приведет к тому, что останутся те же "буквы", только немного сместятся их позиции, и критерий похожести будет большим.

Здравствуйте, Слава, Вы писали:

С>Здравствуйте, 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, пальцев на руках хватит?

Здравствуйте, arabo_xv, Вы писали:

_>Посмотрите в сторону "Самоорганизующиеся нейронные сети Кохонена".

А каков механизм применения всего этого? Сделать классификатор базы, и выделить каие -то классы изображений, что бы потом искать внутри их? Или же все таки применять для непосредственного попарного сравнения?

Здравствуйте, denisko, Вы писали:

D>По поводу твоей проблемы.
D>1) Возьми большое число изображений, найди разумное число главных компонент (штук 8-9) и раскладывай по ним, получишь компактный ключ к базе.

Ок, с главными компонентами поиграюсь.

D>2) Не хочешь компоненты — разбей изображение на уголовые секторы, ключ -- гистограмма плотности распределения сигнальных точек по секторам.

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

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Картинки небольшие.
PD>Уподобим каждую картинку текстовой строке, то есть выложим ее в линию, и закодируем (условно говоря, делать не надо) буквами.
PD>Далее применить алгоритмы схожести текстовых строк.
PD>Идея в том, что сдвиг и ротация приведет к тому, что останутся те же "буквы", только немного сместятся их позиции, и критерий похожести будет большим.

Ой, тут куча подводных камней.
Во-первых, внимательно посмотрите на две кратинки помеченных красными стрелочками. Эти картинки разные, и строковое представление у них будет разное, и буквы будут разные. И это связано не только со сдвигом и вращением, там разные "буквы". А строковые алгоритмы ищут комбинации букв, но не предполагают что и сами буквы могут быть разными.
Во-вторых, строковые алгоритмы на то и строковые, что бы работать со строками, когда мы вытягиваем картинку в строку, мы теряем очень много топологической информации.
В-третьих, если бы строковые алгоритмы действительно имели бы какое-то преимущество, я думаю давно был бы уже аналог этих алгоритмов для изображений.
Этот метод близок к сигнатурным, где ищутся какие-то специфические особенности изображений, key futures, "букв". Но как их найти в данном случае — я не знаю.

Здравствуйте, BigObfuscator, Вы писали:

BO>Требуется найти соответствие картинок из одного набора — картинкам из другого набора, по признакам похожести.

Да, в книгах по вейвлетам в качестве примера их применения практически всегда приводится поиск изображений по базе. Сам я не пробовал, рассматривался такой вариант?

Здравствуйте, Nuzhny, Вы писали:

N>Здравствуйте, BigObfuscator, Вы писали:

BO>>Требуется найти соответствие картинок из одного набора — картинкам из другого набора, по признакам похожести.

N>Да, в книгах по вейвлетам в качестве примера их применения практически всегда приводится поиск изображений по базе. Сам я не пробовал, рассматривался такой вариант?

Пока что рассматриваются все варианты, в том числе и этот. Вопрос в обеспечении точности и производительности.

Здравствуйте, BigObfuscator, Вы писали:

BO>Интересуют либо хорошие методы предварительного отбора кандидатов на сравнение, либо средства сортировки кандидатов, либо может какие-то сигнатурные методы сравнения...

На мой взгляд, надо найти метод, позволяющий быстро отбрасывать то, что точно не подходит. Проблема в том, чтобы он не давал никаких false-negatives. Например, можно построить гистограммы яркостей и посчитать корелляцию (как я понял, яркости уже нормализованы, если нет — то нормализовать). А уже кандидатов отбирать более тщательно и медленно. И, кстати говоря, дискретный Фурье может так же помочь. Он лучше тем, что работает на произвольных размерах, не обязательно степени двойки. Строим DFT для нескольких характерных частот, Зануляем фазы и сравниваем амплитуды. Но вообще, здесь необходим "комплекс мероприятий" с большим количеством херуистики и эмпирики.

Здравствуйте, Nuzhny, Вы писали:

N>Здравствуйте, BigObfuscator, Вы писали:

BO>>Требуется найти соответствие картинок из одного набора — картинкам из другого набора, по признакам похожести.

N>Да, в книгах по вейвлетам в качестве примера их применения практически всегда приводится поиск изображений по базе. Сам я не пробовал, рассматривался такой вариант?

Подумал я о вевлейтах более подробно, и понял что это не лучший вариант. Приведу два момента:
1)Вейвлет представление изображения, в общем случае, имеет большую размерность чем исходное. А это значит, что если мы будем сравнивать вейвлет-спектры, то придется перебирать большее число точек.
2)Можно попытаться делать вейвлет не по всем пространственным точкам, а только в центральной точке (тут он становится похож на фурье). Но тут сразу же возникает проблема. Дело в том, что поскольку объекты имееют одинаковый масштаб, то первый же фильтр Хаара(двумерная матрица 17*17) дает почти всегда нуль. Он не нуль только если объект имеет большую дырку посередине, что весьма специфично. Для обычных же объектов без дырок — он всегда 0

Здравствуйте, McSeem2, Вы писали:

MS>На мой взгляд, надо найти метод, позволяющий быстро отбрасывать то, что точно не подходит. Проблема в том, чтобы он не давал никаких false-negatives. Например, можно построить гистограммы яркостей и посчитать корелляцию (как я понял, яркости уже нормализованы, если нет — то нормализовать).

Яркости не нормализированы. Пока формулировка задачи такова, что искомые объекты имеют одинаковую яркость. Если вдруг окажется что яркости все таки разные — никогда не поздно сделать нормировку.
Насчет гистограмм — в гистограммах идет очень большая потеря информации. Да, я могу просеять базу с помощью гистограмм. Но при этом отсеится процентов 70% (от миллиарада). Останется 300млн кандидатов, что с ними дальше делать? А время на сравнение гистограмм — тоже нужно затратить не малое. Хочется что бы самый первый классификатор отсеивал как можно больше, а для этого он должен содержать как можно больше информации об изображении. И это явно не случай гистограмм. Хотя если можно придумать очень эффективный метод хранения, сортировки и сравнения гистограмм, то как вариант это конечно можно рассматривать.

MS>И, кстати говоря, дискретный Фурье может так же помочь. Он лучше тем, что работает на произвольных размерах, не обязательно степени двойки.

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

Здравствуйте, BigObfuscator, Вы писали:

BO>Здравствуйте, arabo_xv, Вы писали:

_>>Посмотрите в сторону "Самоорганизующиеся нейронные сети Кохонена".

BO>А каков механизм применения всего этого? Сделать классификатор базы, и выделить каие -то классы изображений, что бы потом искать внутри их? Или же все таки применять для непосредственного попарного сравнения?

Обучить сеть на первом наборе. Далее для каждой картинки из БД проводить опознание.

Здравствуйте, BigObfuscator, Вы писали:

BO>Насчет гистограмм — в гистограммах идет очень большая потеря информации. Да, я могу просеять базу с помощью гистограмм. Но при этом отсеится процентов 70% (от миллиарада). Останется 300млн кандидатов, что с ними дальше делать? А время на сравнение гистограмм — тоже нужно затратить не малое. Хочется что бы самый первый классификатор отсеивал как можно больше, а для этого он должен содержать как можно больше информации об изображении. И это явно не случай гистограмм. Хотя если можно придумать очень эффективный метод хранения, сортировки и сравнения гистограмм, то как вариант это конечно можно рассматривать.

BO>Вообще говоря, вейвлеты тоже работают не только на степенях двойки. Степени двойки нужны только для ортогональных наборов функций, с той целью что бы можно было восстановить изображение по вейвлетам. Но поскольку у меня задачи восстановления нет, то я могу использовать произвольные вейвлет-функции.

Ну, именно об этом и речь. Надо сначала отсеять 70%, потом из оставшихся 30 попробовать другие методы. И только на самых последних этапах применять дорогие методы. Главное — отсеять как можно больше неподходящих, но чтобы правильные кандидаты оставались. "no false negatives" — это такая мантра в данной задаче. А вообще, надо прсто очень много экспериментировать. Это классическая инженерная задача, ее не решить одним ударом.

В общем, после анализа предложений , наметился кое-какой прогресс .
Удалось отсортировать базу. Результат такой:

Изображения одного и того же объекта подчеркнуты красным. Как видно, они расположены достаточно близко друг от друга.
Каждой картинке удалось присвоить число, при этом близкие по форме картинки имеют близкие сигнатуры (кстати я раньше думал что это почти невозможно ). Сигнатура инвариантна относительно вращения и масштаба.
Метод оказался на удивление прост и дешев. А вот точность на большой базе наверняка будет хромать.

Тема не закрыта, по прежнему приветствуются предложения

Здравствуйте, BigObfuscator, Вы писали:

...

можно подробней о вычислении сигнатуры?

Здравствуйте, BigObfuscator, Вы писали:

Можно попробывать такой http://en.wikipedia.org/wiki/Viola-Jones_object_detection_framework детектор.

Здравствуйте, BigObfuscator, Вы писали:

Недавно один алгоритм на глаза попался. Описан в этом документе Fast Multiresolution Image Querying
На русском языке описание этого алгоритма есть в книге Вейвлеты в компьютерной графике

Вкратце, там сначала к изображению применяется 2D вейвлет-разложение, затем вычисляется сигнатура из среднего значение цвета и выборки нескольких наибольших коэффициентов разложения.