Обработка изображений: Простая классификация объектов по их форме. Возможно ли?

http://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D1%86%D0%B5%D0%BF%D1%82%D1%80...

> Перцептрон

Нет, не подойдет. Таким распознают индексы на почтовых конвертах.
К тому же, у меня органическое неприятие всяких «приближенных» методов в Pattern recognition.
Сказывается обучение на кафедре ММП ВМиК по профилю «распознавание образов» -
у нас рассматривались лишь приложения _дискретной математики_, с
минимумом эвристик типа «мягких вычислений» и «нейронных сетей».

Пример объекта для определения формы (тут приходится смириться с тем, что коричневые плавки от коричневых волос на голове программа отличить не сможет) - http://php.kirovnet.ru/download/cl-men-ascii.txt
http://php.kirovnet.ru/images/cl-men-ascii.jpg

Контрпример: Чем платье отличается от свитера на изображении? Есть ли чёткое определение, пригодное для использования человеком, сортирующим фотографии? А тут ведь надо, чтобы программа это делала… Да ещё и их формы различала…

«Математическая» постановка задачи примерно следующая:
1. Дано несколько изображений-«образцов».
2. Дан изображение-объект для распознавания.
3. Надо найти коэффициенты «похожести» на каждый из объектов-образцов.

С позиций алгебраического подхода к распознаванию образов,
вначале строятся некоторые функционалы на пространстве изображений -
1) «коэффициент зашумленности» объекта;
2) «коэффициент унылости» цветовой палитры;
...
k) «длина контура» объекта;
и т.д.

Затем проводятся вычисления с использованием данных характеристик объектов в k-мерном пространстве.

> Сказывается обучение на кафедре ММП ВМиК по профилю «распознавание образов»

Эко ты пальцы растопырил. Раз такой крутой «специалист» по распознаванию образов, чего таскаешься по форумам с вопросом о «простой классификации»?

> Чем платье отличается от свитера на изображении?

Тоже думал над этим. В этом случае я предполагаю выполнять сортировку только по платьям. «Раскидывать» изображения по категориям на этапе занесения фоток в Интернет-магазин «вручную», а программа пусть сама проставляет их атрибуты для сравнения и поиска SQL-запросами.

google OpenCV

> Раз такой крутой «специалист» по распознаванию образов, чего

таскаешься по форумам с вопросом о «простой классификации»?

Там крутого ничего нет. Обычная охрана авторского права методов сложных обозначений в кандидатских и докторских.
Смысл этих методов распознавания можно объяснить ребенку «на пальцах».
Вот и спрашиваю здесь — поскольку именно по обработке изображений у меня специализации не было - на кафедре я решал узкие задачи из финансового анализа - распознавания трендов на рынке ценных бумаг, а сейчас надо решить небольшую задачу на фрилансе с минимальными временными затратами.

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

Мне надо не просто решить задачу «абы как», а чтобы код получился простым, алгоритм понятным неспециалисту и числовые коэффициенты, например - при различении фасонов платья - очевидными. Пока в голову приходят только проекции контура объекта на оси X и Y.

Есть такая книга «Вейвлеты в компьютерной графике». Там среди прочего рассказывается про поиск изображений в базах по образцу. Может поможет, хз.

>Таким распознают индексы на почтовых конвертах.

Другие картинки тоже можно, главное грамотно их подготовить

> К тому же, у меня органическое неприятие всяких «приближенных» методов в Pattern recognition.

Сказывается обучение на кафедре ММП ВМиК по профилю «распознавание образов»

Всегда подозревал, что на ВМиК кроме пафоса и понтов ничего не осталось... но не думал что там все настолько плохо...

А по теме могу посоветовать замечательный метод Shape Context - замечательно вычисляет дескрипторы формы, которые потом можно сравнивать хоть Евклидовым расстоянием.

А для выделения форм, я бы все-таки пользовался бы не Собелом а каким-нить другим методом сегментации, теми же графами или банальным k-means.

google: image registration

3. Надо найти коэффициенты «похожести» на каждый из объектов-образцов.

google: mutual information

> Всегда подозревал, что на ВМиК кроме пафоса и понтов ничего

не осталось... но не думал что там все настолько плохо...

У нас никогда там не было ни пафоса, ни «понтов». Может быть, сейчас появились.
А уровень образования уже к 1995-2000 серьезно упал, и заметно отличался
в худшую сторону от мехмата МГУ и МФТИ (физтеха: ФОПФ и т.п.).
А собственно программирования и зарубежного «Computer science»
у нас и не было. Только лишь математика, заметно легче «мехматовской».
+Незначительные вкрапления около-CS спецсеминаров.

теми же графами или банальным k-means.

Графы мне ближе, но там весьма ресурсоемкие алгоритмы их сравнения.
То есть, в конце-концов надо получить именно евклидово пространство.

k-means посмотрю, видимо - какая-то эвристика из англоязычных публикаций.

пользовался бы не Собелом а каким-нить другим методом сегментации

Собель - это не метод сегментации, а всего-лишь фильтрация методом весовой функции с конечным «окном».
Сегментация же - суть алгоритмы на графах.

> google: mutual information

Посмотрел определение здесь: http://en.wikipedia.org/wiki/Mutual_information

По-сути дела, метод разделяющих плоскостей и метод потенциалов из распознавания образов решают похожую задачу - вычисление принадлежности нескольким классам в «признаковом пространстве».

У меня же сейчас задача даже не распознать объект, а для начала сформировать это пространство признаков.
Вот и спрашиваю, например, - по каким формальным признакам отличить фасон платья, или форму свитера, от другой ее (его) формы?

Мне кажется, что у вас даже не получится программно определить какого пола человек на фотке, не говоря уже про фасоны свитеров и платьев, которых любая блондинка легко насчитает штук 100 сразу. Я не представляю как их можно программно различить.

> А собственно программирования и зарубежного «Computer science» у нас и не было.

Заканчивал несколько более скромный ВУЗ, но стремление решать тудноформализуемые задачи исключительно «точными» методами вызывает у меня волну непонимания.

Но ладно из того, что я написал, главное обратите внимание на Shape Context - а сегментация уже вторична.

Я знаю, что Собел сам по себе ничего не сегментирует, но на его основе сделано много методов сегментации: детектор Canny, метод водоразделов, ну и т.п.

Из наименее ресурсоёмкой сегментации, могу посоветовать http://en.wikipedia.org/wiki/Region_growing

> А для выделения форм ...

Под «выделением форм» вы понимате - выделение каким-либо алгоритмом графических примитивов?

банальным k-means.

Прочитал. Метод k-means - это метод кластеризации точек в метрическом
пространстве, к тому же - обладающий существенными недостатками. Что
именно кластеризовать? Пикселы?

У Вас был положительный опыт использования этого метода? На каких входных данных?

> Я не представляю как их можно программно различить.

Пол человека различать не требуется. Это действительно очень трудная
задача, что можно проиллюстрировать морфингом изображения (медленно
преобразовывать мужское лицо в женское). Иллюстрация была в книге
серии «Компьютер обретает разум».

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

Заканчивал несколько более скромный ВУЗ, но стремление решать

тудноформализуемые задачи исключительно «точными» методами вызывает

у меня волну непонимания.

Можете считать это «бзиком» моих научных руководителей - один из
которых, по слухам, участвовал в разработке системы С-300 + создании
других серьезных систем.

Но ладно из того, что я написал, главное обратите внимание на Shape Context

Посмотрю.

детектор Canny

Вбивать матрицу сглаживания для Canny мне было просто лень, я смотрел только статьи по этому методу. Но попытка использовать близкую аналогию (с меньшим окном сглаживания), не дала существенного увеличения качества классификации фотографий в моем случае (я использовал этот фильтр для оценки «зашумленности» объекта - с целью определить текстуру материала одежды). Возможно, допустил какие-то ошибки при программировании - посмотрю Canny еще раз чуть позже.

Из наименее ресурсоёмкой сегментации, могу посоветовать http://en.wikipedia.org/wiki/Region_growing

OK. Гляну.

Спасибо за конкретные советы. Займусь этим до сегодняшнего вечера.

ИМХО, придется вам все-таки какую-то долю «искусственного интеллекта» привлекать, чтобы на основе большой выборки фотографий с одинаковыми фасонами научить программу различать эти фасоны. Кстати, а что, если платье будет не одноцветным, а, скажем, перламутровым/в пятнышко/с рисунком? Распознать область с одной и той же фактурой довольно сложно (если только вы не будете делать все фотографии на однотонном фоне кислотного цвета).

> не говоря уже про фасоны свитеров и платьев

Заказчик прислал вот такую картинку:
http://php.kirovnet.ru/images/cl-compareshape.jpg

> если только вы не будете делать все фотографии на однотонном фоне кислотного цвета

Фон на большей части фоток - белый, манекены - светло-серого цвета, кожа - стандартного.
Так что это не проблема.

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

Можно попробовать (если уж вы научились оконтуривать именно платья) разбивать платье на элементарные фигуры (скажем, прямоугольники и треугольники) и попытаться на основе этого разбиения сделать какую-то классификацию.

Дурацкая, наверное, идея. Но. Платье — симметричное, рассматривать имеет смысл одну половину. Контур можно описать десятком последовательных отрезков, или, что то же самое, десятком высот от середины. А это уже простая одномерная гладкая функция. Дальше можно тупо считать корреляцию, или воспользоваться каким-нибудь преобразованием по вкусу, вроде фурье, лапласа или различных вейвлетов.

Заказчик прислал вот такую картинку:

это как раз задача для mutual information.
которая выдаёт численную величину «похожести» двух изображений.

1. сначала оконтурите используя тот же Sobel или какой-либо
другой алгоритм
2. потом сделайте flood fill, залейте каким-либо цветом
3. совместите (x,y,angle transform) два изображения
путём максимизации normalized mutual information
(я использовал double pass migrad algorithm),
которая и будет мерой «похожести» изображений.

Посчитать площади перекрытия уже дело техники.
Так, на пример, совмещают две томограммы полученные
разными способами (modality).

Если очень необходимо сравнивать именно форму, то неплохо работают Active Shape Model и Active Appearance Model.

++ http://research.microsoft.com/pubs/66721/phd-thesis.pdf

ctive Shape Model и Active Appearance Model.

super!

>возможно ли ... по их форме?

Возможно: Фу К. Структурные методы в распознавании образов.
Там используют синтаксис цепного кодирования контура, двумерные грамматики, ... и в конечном счёте метод сводится к решению задачи линейного программирования.

>разделить фотки

Осилив 7 обязательных книжек по теории распознавания образов, ты сможешь решить эту задачу :)

> Возможно: Фу К. Структурные методы в распознавании образов.

Да, я читал эту книжку, а также некоторые другие (Скрыпника, Вапника и проч.) по распознаванию образов (по К.Фу у меня была написана одноименная курсовая на 4 курсе). Очень хорошие вещи - грамматики для описания изображений. Но применение структурных методов здесь не оправдано, то есть - не стоит тех денег, которые предлагает заказчик.

Нашел (попутно) еще вот такие предложения по поиску «похожих» изображений:

http://stackoverflow.com/questions/75891/algorithm-for-finding-similar-images

для Ъ про перцептрон из вики

Перцептроны имеют ограничения в задачах, связанных с инвариантным представлением образов, то есть независимым от их положения на сенсорном поле и относительно других фигур. Такие задачи возникают, например, если нам требуется построить машину для чтения печатных букв или цифр так, чтобы эта машина могла распознавать их независимо от положения на странице (то есть чтобы на решение машины не оказывали влияния перенос, поворот, растяжение-сжатие символов)[6]; или если нам нужно определить из скольких частей состоит фигура[35]; или находятся ли две фигуры рядом или нет[36]. Минским было доказано, что этот тип задач невозможно полноценно решить с помощью параллельных вычислений, в том числе — перцептрона.

очень интересный и поучительный пост получился.
Чем закончилась история?

>Чем закончилась история?

для меня - ничем. мне юбки классифицировать было не нужно. Я решил порезать объект на куски, и применить аффинные преобразования, для того, что-бы объекты имели одинаковый размер и одинаковый поворот. А уж на это я буду натравливать перцептрон. Просто в моём случае это возможно, а в случае ТС, ИМХО, нет.

Однако, лично я этим для себя занимаюсь, когда делать нечего, потому работа движется очень медленно. Если всё-же получится что-то годное, выложу.

Всем спасибо за литературу.

Очень интересует данная задача. С удовольствием помог бы. Просто касаеться моей научной работы, я как раз ищу область применения своим алгоритмам - есть конкретные наработки.

Контакт - LexRema на gmail.

Что значит «Простая»?

Как вы думаете, возможно ли построить некоторую действительнозначную
функцию (или их набор), позволяющую(-ие) классифицировать объекты на
растровых изображениях по их форме?

Таких функций уйма, например {Фурье, Эллиптические, Зернике} инварианты, чуть осилив матан их создания можно ввести свои, тк ортогональных полиномиальных базисов чуть более чем дофига (можно и вейвлетные идейки использовать, никто не мешает).