Поиск видеоданных в сети

Быть может, это и верно, что любой объект является единственным в своем роде, но жизнь была бы невозможна, если бы мы относились к этой мысли слишком серьезно.

Э. Хант. "Искусственный интеллект"

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

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

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

Электронные архивы изображений

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

Особое положение среди последних занимают виртуальные художественные и исторические галереи и музеи.

Вот лишь некоторые сетевые адреса таких архивов.

Web-музей картин из Лувра (www.oir.ucf.edu/wm).

Коллекция работ советских художников-авангардистов эпохи хрущевской оттепели "Другое искусство" (www.stria.ca/Brochetain).

Коммерческий электронный архив изображений, относящихся ко всем сферам истории и деятельности человека (www.photodisc.com).

Коллекция торговых знаков (wwwqbic.almaden.ibm.com/cgi-bin/tmdemo).

Департамент США по патентам и торговым знакам (The U.S. Patent and Trademark Office - USPTO) имеет электронный архив торговых знаков в цифровом виде. В этих архивах, помимо изображения торговых знаков, приводятся сведения о владельце торгового знака, дате ввода в архив и соответствующие коды продукции. Разработана опытная демонстрационная система для просмотра и поиска торговых знаков из базы данных, включающей в себя 1000 знаков из еженедельника "Trademark Weekly Text File" (www.optipat.com), выпускаемого USPTO.

Коллекция почтовых марок, выпущенных в США до 1995 года (wwwqbic.almaden.ibm.com/cgi-bin/stamps/-demo).

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

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

Распознавание изображений и анализ сцен

Несмотря на разнообразие новых задач, их объединяет то, что все они относятся к одной и той же области исследований - машинному зрению (computer vision). Чтобы дать полную картину, мы рассмотрим основные понятия в этой области и далее перейдем к конкретным техническим решениям.

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

Исследования в данной области были в центре внимания как в СССР, так и в США в период развертывания программы СОИ (Стратегическая Оборонная Инициатива).

Фундамент машинного зрения составляют следующие три основные парадигмы:

обработка изображений, распознавание образов и анализ сцен:

Каждый из этих разделов имеет свою специфику:

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

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

Основная задача распознавания (или классификации) образов состоит в отнесении входных объектов (в нашем случае, изображений) к одному из нескольких классов по измеренным характеристикам (признакам) входных объектов.

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

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

Однако анализ определенной сцены может быть затруднен тем, что образец и искомое изображение были получены при различных условиях съемки: они могли быть сняты с различных точек обзора, при разных ориентациях объектов сцены или условиях освещения. В подобных случаях воспринимаемые формы объекта на изображениях будут различными. Выполнение запроса еще более усложнится, если учитывать эффекты отбрасывания теней и отражения света от поверхностей или загораживания одних объектов другими.

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

Поиск изображений в удаленной базе данных

Теперь перейдем к рассмотрению систем, предназначенных для выполнения запросов указанного вида. Несмотря на ряд различий, они функционируют примерно по следующей схеме (см. рис. 2).

Рис. 2. Поиск изображений по их содержанию: путешествие в Сети.

Система ZOMAX

Система ZOMAX (http://target.wins.uva.nl:5345/zomax/HTML/ intr.html), разработанная на языке Java, предназначена для обработки изображений и поиска видеоданных в сети WWW. В этой системе сегментация изображений базируется исключительно на переходах по изменениям отражательных свойств материала поверхностей с учетом изменений их ориентации в наблюдаемой сцене, условий освещенности, затененности и зеркального отражения света от некоторых поверхностей в сцене.

В систему включена база данных из 500 оцифрованных цветных снимков самого различного содержания (предметы домашнего обихода, инструменты, художественные изделия и т. д.) с 8 битами на каждый цвет. На любом из этих снимков, используемых в качестве графического запроса (исходного изображения), запечатлен отдельный объект на белом фоне. Из совокупности уже отснятых объектов случайным образом выбрано около 100 в качестве тестового множества. Затем каждый из объектов тестового множества снят в новой произвольной позиции и ориентации относительно камеры (с изменением расстояния до камеры). В результате изменен масштаб на полученном снимке объекта.

Оценка эффективности выбранного набора признаков дается по критериям инвариантности к геометрическим преобразованиям, различаемости объектов и быстродействии по распознаванию.

ZOMAX состоит из трех подсистем: PICTOSEGMENT - для сегментации цветных изображений, PICTOSEEK (http://zomax.wins.uva.nl:5345/ret_user/) - для поиска изображения по запросу по фотометрическим и геометрическим признакам, и PICTOVISION - для выполнения всех основных операций по обработке изображений.

Проект QBIC

На протяжении ряда лет в корпорации IBM ведутся исследования в рамках проекта QBIC (wwwqbic.almaden.ibm.com) эффективности управления, организации и навигации по онлайновым коллекциям изображений. В результате создана система QBIC ( Query By Image Content - запрос по содержанию изображений), позволяющая выполнять запросы к базам изображений по их содержанию. Это содержание дается в терминах процентных соотношений цветов, местоположения фрагментов различных цветов на изображении, его текстуры и т. д.

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

Система QBIC содержит механизмы индексирования изображений, механизм предварительной обработки запросов из сети WWW и поисковую машину на платформах Linux, Windows 95/NT, OS/2.

Возможны следующие способы поиска изображений:

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

Запрос по ключевым словам. В указанном поле надо ввести ключевые слова для поиска, пользуясь такими описаниями, как "машина", "дом" или "дорога". Изображения при их выводе будут упорядочены по формуле 1: Nq/Nm, где Nq и Nm, соответственно, общее число ключевых слов и число ключевых слов, соответствующих выводимому набору изображений.

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

Если же использовать ключевые слова для поиска, то система QBIC выдаст набор изображений, упорядоченных по степени их близости к заданному запросу (по правилу: чем больше совпадений по ключевым словам, тем лучше).

Комбинированный запрос. Этот вид запроса позволяет совместно использовать ключевые слова и специализированные признаки изображения.

VIR Image Engine

Компания Virage (Сан Матео, США) известна своими разработками в области поиска и обработки мультимедийных данных, таких как изображения и видео. Одна из ее технологий, известная под названием VIR-технологии (visual information retrieval), лицензирована многими ведущими компаниями (Oracle, Sybase, Objectivity и др.), занятыми в сфере разработки СУБД, информационного поиска в Интернете, автоматического составления каталогов цифровых изображений и видео. Технологии этой компании используются также в системах идентификации личности по портрету, скажем, при регистрации в социальных службах, получении водительских прав и управлении доступом в защищенные системы.

Стоит также упомянуть, что весной прошлого года Virage была выбрана корпорацией Intel в качестве одного из шести эксклюзивных производителей ПО для демонстрации возможностей процессора Pentium II.

Одна из систем, разработанных компанией Virage, VIR Image Engine (см. www.virage.com), предназначена для анализа и сравнения цифровых изображений. В настоящее время она адаптирована для многих типов промышленных баз данных.

Поиск зрительной информации с помощью системы VIR Image Engine основан на таких характеристиках изображения, как насыщенность, цвет, тон. При поиске производится оценка и доминирующего цвета, и его вариации на изображении.

В ходе своей работы система VIR Image Engine устанавливает относительное расположение участков изображения различных цветов и оценивает значения ряда текстурных признаков в пределах отобранных эталонных областей. Система также вычисляет характеристики контуров различных форм для описания структуры объекта на изображении.

В демонстрационной версии этой системы предусмотрена возможность присвоения весов (в пределах от 1 до 10) значениям отдельных признаков изображения.

Система VIR Image Engine может быть интегрирована с инструментальным набором Image Read/Write для обеспечения преобразования изображений из одного формата в другое. В целом, преобразование может выполняться практически для всех форматов, принятых в промышленности, включая форматы BMP (Windows, OS/2), JPEG, GIF, MAC, TIFF, PCX и ряд других.

Что можно найти на сайте PhotoDisc

PhotoDisc, одна из компаний, занимающихся записью и распространением коллекций изображений на компакт-дисках, успешно реализовала VIR-технологию на своем Web-сайте (www.photodisc.com) в целях рекламы продукции и приема заказа на нее. В настоящее время ее электронный архив, доступный посетителям сайта, насчитывает 60000 снимков и изображений самого различного содержания (религия, сельское хозяйство, природные явления и т. п.).

Имеется возможность скачать все снимки, имеющиеся на сайте (в формате comp) в онлайновом режиме, но для незарегистрированных пользователей они снабжаются дополнительной меткой (водяными знаками). В этом формате представлены изображения низкого разрешения (72 точки на дюйм) с объемом от 40K до 150K. Для описания изображений предусмотрен список ключевых слов, снабженных гиперссылками на соответствующие изображения коллекции. Можно вести поиск изображений на естественном (английском) языке по ключевым словам и понятиям (concepts) c использованием булевых связок, а также в терминах их визуальных характеристик (например, текстурных свойств поверхности или признаков ее формы), ранжированных по степени важности. Возможен поиск даже по неполному ключевому слову.

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

Java Sketch Engine

В настоящее время в Лейденском университете (Голландия) и университете Карнеги-Меллон (США) совместно разрабатывается проект Java Sketch Engine, цель которого - создание интерфейсов для запросов, задаваемых в виде изображений. Пока созданы две системы, одна из которых производит поиск и сравнение изображений по их эскизным (sketch) вариантам, другая сравнивает их по пиктограммам объектов. Переход к эскизу данного цветного изображения значительно сокращает объем передаваемых видеоданных (примерно в 100 раз). Подобный переход основан на допущении о том, что эскизы, выполненные людьми, имеют большое сходство с картами границ (edge maps), полученных в результате компьютерной обработки исходных изображений.

В рамках проекта Java Sketch Engine пользователь отправляет созданный им эскиз со своего браузера на сервер Лейденского университета для сравнения с картами границ из базы данных. Сравнение проводится на основе сходства формы эскиза с изображениями из базы данных, среди которых отбирается наиболее похожий на полученный эскиз. Процесс сравнения изображений выполняется на нескольких уровнях: сначала сравниваются их уменьшенные копии или копии с низким разрешением, и затем этот процесс последовательно уточняется в результате перехода к копиям с более высоким разрешением. Пользователю передается окончательный набор изображений, выделенный из базы данных. С работой Java Sketch Engine можно ознакомиться по адресу (www.wi.leidenuniv.nl/home/lim/javasketch.htm), используя браузер Netscape 3.0 или 4.0.

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

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

С автором можно связаться по адресу:

tdadashev@hotmail.com