Здравствуйте, 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, Вы писали:

...

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

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

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

D>...

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

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

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

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

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

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

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

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

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

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