НАУКА и ОБРАЗОВАНИЕ

Ю. И. Журавлев, акад. РАН, К. В. Рудаков, чл.-корр. РАН, С. И. Гуров, канд. физ.-мат. наук, Е. В. Дюкова, доктор физ.-мат. наук, Г. П. Кутуков, канд. техн. наук, Вычислительный центр РАН; С. Н. Матюнин, канд. техн. наук, СПП РАН, Л. М. Местецкий, доктор техн. наук, Тверской ГУ

Состояние и перспективы развития исследований в области обработки и распознавания видеоинформации (аналитический обзор)

По материалам НИОКР, выполненных в Вычислительном центре (ВЦ) РАН за 1995—97 гг., рассматриваются основные направления исследований в области обработки и распознавания изображений; анализируются недостатки существующих методов обработки и пути их преодоления на основе применения новой технологии (алгебраического подхода) синтеза и оптимизации алгоритмов.

Введение

В настоящее время одним из перспективных направлений развития современной техники является создание средств информационной поддержки в составе автоматизированных систем контроля, разведки и управления.

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

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

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

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

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

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

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

Итак, в целом ситуация на сегодня может быть охарактеризована следующим образом: активно и успешно создаются и внедряются средства доставки и измерительные приборы; доступны средства вычислительной техники достаточной производительности; имеется существенный теоретический задел; на практике применяются традиционные методы обработки, анализа и распознавания видеоданных. Причем сказанное относится как к работам, проводимым в России, так и к известным зарубежным аналогам.

Основные направления исследований и перспективы их развития в области обработки и распознавания видеоинформации

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

1. Первое направление составили работы, авторы которых исходили из того факта, что человек в реальной жизни постоянно и успешно решает чрезвычайно трудные с теоретической точки зрения задачи обработки информации (классический пример — распознавание зрительных образов). Из этого делался вывод о том, что процесс решения на ЭВМ плохо формализованных задач должен моделировать основные аспекты процесса мышления. Именно такое моделирование и составляло основную цель исследований. На этом пути были получены многие интересные теоретические и даже экспериментальные результаты.

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

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

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

Во-первых, выкристаллизовывались общие черты постановок задач, относящихся к внешне самым различным прикладным областям. В частности, становилось ясно, что в качестве замены адекватной математической модели чаще всего приходится использовать массивы прецедентов, т. е. пар вида "входная информация — выходная информация".

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

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

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

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

Предпосылкой для перехода ко второму этапу 3-го направления в значительной степени явилось наличие групп ученых, накопивших опыт решения прикладных задач и использовавших для разных задач близкие по структуре алгоритмы (при этом типы алгоритмов у различных научных групп часто были разными). Суть второго этапа можно определить переходом от принципа "прикладная задача => алгоритм" к принципу "семейство алгоритмов => прикладная задача". Иными словами, произошло оформление параметрических семейств алгоритмов, имеющих весьма универсальный характер и широкие сферы потенциальных приложений. Решение практических задач в этой ситуации свелось к "настройке параметров", т. е. к решению проблемы выбора значений параметров, выделяющих из семейства оптимальный для конкретной задачи алгоритм.

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

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

Исходным пунктом развития алгебраического подхода послужила идея о том, что помимо использования эвристических семейств алгоритмов в качестве фиксированных областей, в рамках которых следует искать решения, имеется альтернативный путь: из имеющихся семейств можно определенным образом выбирать некоторые алгоритмы и, используя подходящие операции над алгоритмами (корректирующие операции), целенаправленно строить оптимальные алгоритмы для конкретных задач. Следует отметить, что сама по себе идея совместного использования наборов алгоритмов при решении отдельных задач широко распространена и активно применяется различными группами исследователей. Эта идея была использована в исходных работах [1] и [2], в которых в качестве корректирующих операций применялись некоторые операции над действительными матрицами, а в качестве исходных семейств алгоритмов рассматривались алгоритмы, основанные на принципе разделения, и алгоритмы вычисления оценок.

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

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

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

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

·        каждый элементарный акт вычислений производится не с изображением в целом, но лишь с некоторой его частью (окном);

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

В настоящее время все указанные выше особенности процедур и механизма обработки (на ЭВМ) изображений реализо­ваны в математической модели, разработанной в ВЦ РАН и успешно апробированной на контрольных примерах и реальных задачах.

Заключение

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

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

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

В случае обработки изображений для применения упомянутой методики исходной оказывается проблема формирования прецедентов. Ими могут быть фрагменты (сегменты) изображения, обработанные "вручную", т. е. оператором по традиционной методике. Таким образом, возникает новая технология автоматизации обработки: вместо подбора алгоритма или последовательности алгоритмов оператор показывает на фрагментах изображения желаемый вид результата, а далее автоматически формируется алгоритм, который и применяется к изображению в целом или к серии изображений. Фактически описанная технология является реализацией идеи обучения алгоритмов обработки изображений. Ее основное достоинство — возможность реализации диалога с оператором на естественном для задач обработки языке — языке показа, что обеспечивает резкое снижение требований к квалификации операторов и делает возможным решение массовых задач обработки и распознавания изображений.

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

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

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

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

В частности, при обработке изображений такими задачами могут быть:

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

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

в) обнаружение и локализация на изображениях интересующих (искомых) областей, объектов или ситуаций;

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

Список литературы

1. Журавлев Ю. И. Корректные алгебры над множеством некорректных (эвристических) алгоритмов. // Кибернетика. 1977. № 4. С. 14-21; 1977. № 6. С. 21-27; 1978. № 2. С. 35-43.

2. Журавлев Ю. И. Об алгебраическом подходе к решению задач распознавания или классификации. // Проблемы кибернетики. Вып. 33. М.: Наука, 1978. С. 5-68.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 4, 1998

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

Ключевые слова:

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