Авторы: С. В. Абламейко, В. В. Краснопрошин, В. А. Образцов
Название: Распознавание образов и анализ изображений: теория и опыт решения практических задач
Источник: Белорусский государственный университет. – Минск
В работе обобщается опыт теоретических и прикладных исследований, проводимых на кафедре информационных систем управления при выполнении различного рода государственных научно-практических (в том числе и между- народных) проектов.
Надо сказать, что это не первая подобная публикация авторов. Сошлемся на статью [1], в которой мы попытались изложить методологические и теоретические ре-
зультаты в области распознавания образов. В настоящей публикации принят несколько иной стиль. Во-первых, мы пытаемся акценты более равномерно расставить
между двумя компонентами: теорией и практикой. А, во-вторых, стараемся избегать
методологических аспектов и оценочных суждений. Надеемся, что полученный вариант послужит в дальнейшем для подготовки более «фундаментальной» публикации.
Несколько слов хочется сказать в качестве исторической ретроспективы. Дело в
том, что два автора данной публикации (В. В. Краснопрошин, В. А. Образцов) всегда
имели непосредственное отношение к кафедре. Вначале это была кафедра автоматизированных систем управления, а с 2008 года – информационных систем управления.
Третий автор (С. В. Абламейко) долгие годы основное отношение имел к академической системе, работая до 2008 года в Объединенном институте проблем информа-
тики НАН Беларуси. При этом он с 1988 года начал по совместительству работать на
кафедре, что продолжается и по сей день. С 2008 года, после перехода в Белгосуниверситет в качестве ректора, основным местом и для него стала кафедра. Кроме того,
надо заметить, что все три автора считают, что они принадлежат к известной школе
академика АН России Ю. И. Журавлева. В итоге мы сочли возможным объединить в
данной публикации основные результаты перечисленных авторов и отнести их все к
кафедре информационных систем управления.
В [1] нами была предложена схема, с помощью которой можно точно определить
роль и соотношение теории и практики, а также указать основные проблемы, возникающие в этих областях. Воспользуемся той же схемой (см. рис. 1), чтобы при опи-
сании результатов не вводить слишком много понятий. Практическая задача всегда
связана с содержательным уровнем данной схемы и представляет собой отношение: вх вых Z ? I ? I . Для задачи распознавания образов с обучением необходимо еще зафик-
сировать содержание и способ представления вх I и вых I . Относительно первого элемента будем предполагать, что вх I представляет собой информацию о некотором
множестве объектов, разбитую на классы (их число конечно). Способ представления
информации для вх I – прецедентный, а для Z известна лишь часть информации (обучающая и контрольная выборки). Что касается второго элемента ( вых I ), то здесь речь
идет только о метках (или индексах) классов.
В практической задаче Z требуется получить решение на формальном уровне в
виде некоторого алгоритма A с тем, чтобы построить модель вычислительного процесса Pr, но требования к результату не строгие. В такой задаче соотношение между вых i
1 и вых i2 на всем множестве вх I устанавливать не требуется. Иными словами, обоснованность решения в процессе исследования и решения задачи Z даже не предполагается
Иначе обстоит дело в теории распознавания образов. Чтобы перейти в эту плоскость, необходимо, как правило, осуществить типизацию вх I и . вых I Второй элемент
здесь остается неизменным в силу своей универсальности. А вот первый отделяется
от конкретной предметной области. Кодирование при этом теряет смысл и, поэтому,
задача рассматривается уже как отношение Z XY ? ? . Алгоритмизацию для такой
задачи осуществить не так уж и сложно. Значительно более сложным является сравнительный анализ алгоритмов или моделей алгоритмов ?, который служит основанием для установления фундаментального свойства математических формализмов –
обоснованности решения. И вот здесь на первый план выходит установление соотношения между вых i
1 и 2 . вых i В рамках эвристических алгоритмов установить такое соотношение даже в некотором локальном смысле, как правило, не удается. И, поэтому, Ю. И. Журавлевым был предложен [2] подход к построению моделей алго-
ритмов ? для решения задачи Z , смысл которого заключается в установлении существования в рамках ? корректных (т. е. точных на заданной контрольной выборке)
алгоритмов. Т.к. теория распознавания имеет явную практическую направленность,
то помимо существования дополнительно требуется еще возможность построения
корректных алгоритмов в явном виде.
В рамках этого подхода вначале исследования проводились для случая задачи Z,
когда пространство
l Y = ? 2 (здесь {0,1} ? 2 = , l – число классов). Это направление
связано в основном с логической корректировкой, т. е. поиском подходящих функций вида l l g 2 2 : ? > ? . К этому направлению можно отнести целый ряд результатов,
которые получены В. В. Краснопрошиным. Для построения g им использовались
операции трехзначной логики [3], т. к. допускались отказы от распознавания. Соотношение между вых i
1 и вых i2 на контрольной (или тестовой – в оригинале) выборке определялось с помощью «штрафов» и минимизировалось их число. В этом случае
проблема сводится к задаче минимизации функции трехзначной логики. Как известно, эта задача для всех конечных логик эквивалентна задаче о покрытиях. В свою
очередь, последняя задача сводится к построению дизъюнктивных нормальных форм
и их различных подмножеств (сокращенных или тупиковых). В результате проведенных исследований им был предложен также конструктивный вариант построения алгоритма, доставляющего решение искомой оптимизационной задачи.
В рамках данного направления достаточно быстро стало понятно, что логические
корректоры не обладают всеми необходимыми свойствами, гарантирующими существование корректных алгоритмов. И поэтому дальнейшие исследования сосредоточились на алгебрах над некорректными (эвристическим) алгоритмами. Смысл алгебр
очень простой. Алгоритм AX Y : , > который плохо поддается корректировке функциями g, заменяется на новый. Для этого вводится более «богатое» по сравнению с Y
пространство Y ? (как правило l Y ? = ? ), но с одним ограничением: должно существовать отображение с :Y ?>Y (называемое обычно решающим правилом), которое явля-
ется непротиворечивым и допускает существование корректных алгоритмов. Отображение BX Y : , > ? которое является частью исходного алгоритма A , называется обычно
распознающим оператором. А далее в пространстве Y ? вводятся уже операторные корректоры fY Y : , ? ? > подходящая суперпозиция которых с наборами распознающих
операторов и образует искомые алгебры. В [2] было показано, что построение корректных алгоритмов может быть осуществлено в рамках линейной алгебры для большинства известных эвристических моделей. Правда, к таким моделям предъявлялись
достаточно серьезные требования – существование операторов B, которые в наборе на
контрольной выборке размерности q образуют базис пространства ( ).q
В этом направлении на кафедре также получен целый ряд интересных результатов. Вначале это было сделано С. И. Кашкевичем [4]. Он предложил линейную алгебру дополнить константными элементами, что позволило существенно снизить
требования к эвристическим моделям распознающих операторов. Вместо базиса в
такой алгебре*)
Несколько интересных результатов были получены В. А. Образцовым [5–7]. В
частности, был доказан критерий существования корректных алгоритмов, на основе
которого удалось упорядочить результаты, полученные в линейной и полиномиальной алгебре распознающих операторов. Предложен вариант тензорной алгебры распознающих операторов, на основе которой построен билинейный
оказалось достаточно построения элементов, число которых не превосходит числа объектов в контрольной выборке. Кроме того, им также впервые для
алгебраической теории был предложен вариант определения устойчивых распознающих операторов, близкий по смыслу к непрерывности функций.
**)
Хочется сказать о той роли, которую сыграл алгебраический подход. Приблизительно два десятилетия до этого приемлемым считался путь развития теории распознавания, при котором: сначала выдвигалось некоторое эвристическое предположение о структуре множества объектов, расположении классов; затем на его базе строилась модель алгоритмов распознавания и достаточным условием ее применимости
(во многом и правильности) полагалась возможность построения оптимальных на
контрольной выборке алгоритмов. Алгебраический подход при тех же предположениях на эвристику дал возможность конструктивного построения не просто оптимальных, но и точных на любой заданной выборке (корректных, если речь идет о
контрольной выборке) алгоритмов. Сама же алгебраическая теория позволила показать, что во всех случаях мы имеем дело лишь с необходимыми условиями правильности алгоритмов. В общем, это вполне естественно, если учитывать индуктивную
природу задачи распознавания [1].
В связи вышеописанным возникает вопрос: если корректность является только
необходимым условием, что же дальше, в каком направлении может развиваться теория распознавания образов? В распознавании образов существует направление, которого алгебраические исследования не коснулись. Это статистический подход, который по построению имеет индуктивный характер, а развиваемые в нем вероятностные модели без труда адаптируются для решения задач распознавания. Как и все вероятностные модели, они являются самодостаточными с позиции выразительной силы языка для построения высказывания об обоснованности результатов. Поэтому
сформулированные выше вопросы относятся в большей степени к детерминистской
ветви теории распознавания.
О направлении развития теории в настоящее время судить сложно. Некоторый вариант ответа на сформулированный вопрос мы попытались выстроить в [7–9]. Предположим, что для решения некоторой задачи Z удалось построить алгоритм 0 A , который ее решает и возможно делает это наилучшим образом (правильно, за меньшее
число шагов и т. п.). Если для решения той же задачи построен новый алгоритм A1 и
показано, что в области X , где определен 0 A , алгоритм A1 дает аналогичные результаты, то правомерность использования последнего не вызывает сомнений. Этот прием
часто используется в вычислительной математике и математическом моделировании в
целом.
Рассмотрим другой случай. Предположим, что имеется два алгоритма 0 0 AX Y : >
и A1 : X1 >Y , которые решают разные задачи, но между областями X0 и X1 можно
установить взаимно-однозначное соответствие 0 1 f : X X > . Тогда вновь возникает
возможность сравнения алгоритмов по аналогии с тем, как это было указано выше.
Своим происхождением, применительно к задачам распознавания, данный вариант во многом обязан медицинской диагностики. В этих задачах часто используются
два способа представления исходной информации о диагнозах: в виде логических
правил (чаще всего с помощью продукций), или в виде прецедентов (примерами объектов с указанием принадлежности к классам). Для решения задачи легко построить
гибридный алгоритм, в котором на логической информации работает метод резолюций ( A0 ), а на прецедентной – алгоритм распознавания ( A1 ). В частном случае, когда
прецедентная информация строится в булевом пространстве, попадаем в ситуацию
сравнимости алгоритмов A0 и 1 A , описанную выше. Так как сравнение осуществляться с классическим алгоритмом резолюций ( A0 ), правильность которого доказана
по канонам математической строгости, то и алгоритм 1 A , который работает также как
и A0 , должен быть обоснован. Но в отличие от 0 A , алгоритм A1 применяется для
прецедентного представления информации.
В описанной схеме нами предложен и исследован целый класс алгоритмов 1 A ,
которые уместно называть алгоритмами индуктивной резолюции. Показано также,
что ограничение, связанное с булевым пространством признаков, является несущественным. Аналогичные результаты легко переносятся на случай любой дискретной
системы признаков, и, с некоторыми ограничениями, на случай непрерывных признаков.
Ряд следующих теоретических результатов получен при решении задачи обработки и распознавании изображений. Получены они либо лично Абламейко С. В.,
либо под его непосредственным руководством [24–26].
Вначале несколько слов о сути теоретических исследований в области обработки
изображений. Обратимся снова к схеме на рис. 1 и заметим, что суперпозицию кодировки (k) и алгоритма A также можно рассматривать как некую универсальную ко-
дировку k? = A? k (в том смысле, что для нее не требуется разработки алгоритма A ).
Справедлив следующий тезис: если для некоторой задачи Z не существует уни-
версальной кодировки k?, для которой Z окажется разрешимой, то для любых k и
A задача будет неразрешимой. Задачи обработки и распознавания изображений
имеют дело со специальными объектами – изображениями. В силу сформулированного выше тезиса на первый план в этих задачах выходит кодировка k, а алгоритмы
1, ... , A An могут быть и зафиксированы. Такой выбор кодировки уже можно рассматривать как процесс предобработки изображений. И именно этот процесс составляет
суть теоретических исследований в области обработки изображений. При этом сам
процесс может быть представлен в виде стандартной суперпозиции некоторых алгоритмов и исследование может быть сведено к изучению свойств элементов этой суперпозиции.
В рамках теоретических исследований предложен способ описания изображения
с помощью векторов ахроматической и хроматической области, позволяющий качественно выделять объекты, характеризуемые как “бесцветные” с точки зрения восприятия. Способ использует квазиполутоновое преобразование, сохраняющее информацию о цвете объектов с ярко выраженной хроматической компонентой и повышающее контраст полутоновых областей.
Предложен подход пиксельного силового поля для решения задач обработки изображений. По сравнению с традиционными методами в рамках этого подхода предлагается простое и эффективное средство для выполнения операций обработки, как
цветных, так и полутоновых изображений. В дальнейшем модель пиксельного силового поля (ПСП) использовалась для решения трудно формализуемых задач утоньшения и сегментации цветных изображений. Определены основные свойства ПСП,
отличные от других скалярных и векторных полей, разработаны варианты их практического применения. Главным преимуществом ПСП является способность выделять
скелетные пиксели на цветных, полутоновых и многоспектральных изображениях.
Разработаны устойчивый к шумам алгоритм выделения скелета на трехмерных
изображениях и алгоритмы вычисления характеристик скелета, необходимые для определения топологических и геометрических особенностей объектов. Характеристика
структур является важным фактором в задачах исследования материалов, мониторинга заболеваний, контроля качества. В связи с тем, что объекты на трехмерных
изображениях отличаются большой вариабельностью форм и структур, выделение
характеристик относится к сложным задачам обработки изображений.
Ниже описаны три типа практических задач , вх вых ZI I ? ? которые в разные годы
и с различным успехом решались на кафедре. Это большой класс задач медицинской
диагностики, задачи дистанционного зондирования и геомониторинга, а также задачи
распознавания и обработки изображений
Медицинская диагностика. Вообще говоря, это задача является классической для распознавания образов. На кафедре исследованиями в направлении автоматизации процессов медицинской диагностики и тактики лечения занимаются уже бо-
лее 30 лет. Можно выделить три этапа этих исследований.
а) (1977 – 1987 гг). В этот период были решены две задачи: дифференциальной
диагностики деструктивных поражений желудка [11], диагностика синдромов множественных врожденных пороков развития у детей [12]. Решение носило в основном
исследовательский характер и осуществлялось стандартными методами. Врачам интересно было понять, возможна ли автоматизация в принципе, а сотрудникам кафедры – можно ли это сделать с помощью моделей и методов распознавания.
Главным препятствием, которое не позволяло полученные решения перевести в плоскость
законченных программных продуктов, было отсутствие подходящих технологий для
существовавших в то время больших ЭВМ. В конце этого периода на кафедре был
разработан программный продукт (пакет программ ПАРУС), но уже начиналась эпоха персональных компьютеров.
б) (1988 – 1994 гг). В указанный период были решены следующие задачи [13]:
диагностика острой хирургической патологии брюшной полости, диагностика острого аппендицита у детей, диагностика и оптимизация лечения при нарушении сердечного ритма, диагностика и выбор лечения при челюстно-лицевых травмах, диагностика острых неврологических заболеваний. Задачи решались в рамках государственной программы совместно с группой высококвалифицированных специалистов
института усовершенствования врачей. Чтобы решить все перечисленные задачи, потребовалось провести систематизацию методологий ввода и обработки информации,
разработать гибридные алгоритмы [14], которые представляли собой синтез алгоритмов резолюции и распознавания. Необходимость такого синтеза была обусловлена
разнородностью информации, а также требованием отделения информации от
средств алгоритмической обработки. По результатам исследований была разработана
программная технология и на ее базе для каждой из перечисленных задач построено
программное решение. Проведенная систематизация и развитие соответствующих
компьютерных технологий позволило не ограничиваться только решением задач диагностики, а перейти к задачам следующего уровня – разработки автоматизированных рабочих мест специалистов-медиков [15]. Но для решения этих задач, как в тот
период, так, пожалуй, и сейчас, не созданы соответствующие законодательные предпосылки.
в) (1995 – 2010 гг). В указанный период были решены две задачи: диагностики и
выбора тактики лечения заболеваний в области ортопедии [16, 17], информационной
поддержки решений в области экстренных хирургических операций [18]. Принципиальное отличие этого этапа заключается в том, что здесь задачи решались уже самостоятельно, а не подгонялись по известную схему. Результатом этого явилась разработка оригинальных методов (метод индуктивной резолюции [8–10]), программной
технологии, базирующейся на отделении данных и знаний от средств обработки, и
средств, а также инструментов ввода, вывода, интерпретации и объяснения результатов.
Для решения первой задачи спроектирована и реализована прикладная система
Орто-Эксперт, которая обеспечивает лечебно-диагностический процесс от обследования пациента до выбора тактики лечения различных патологий (спины, верхних и
нижних конечностей).
Для второй задачи также разработана система, которая обеспечивает полную информационную поддержку при проведении хирургических операций. Основное назначение системы заключается в повышении надежности проведения наиболее массовых хирургических операций путем обеспечения практикующих врачей контекстно
интересной и по возможности новейшей информацией.
Дистанционное зондирование и геомониторинг. В рамках задачи дистанционного зондирования исследовались вопросы компьютерного анализа аэрокосмических данных на основе моделей распознавания образов и определялись условия для
построения соответствующей программной технологии [19, 20]. Была разработана
геоинформационная система, которая включала блоки: предобработки данных аэрокосмического спектрометрирования, распознавания подстилающих поверхностей
Земли, оригинальный редактор электронных карт для построения тематических карт
и др. Задача геомониторинга связана в основном с составлением т. н. тематических
карт [21]
2.3. Распознавание и обработка изображений. Разработана комплексная техно-
логия создания цифровых карт на основе результатов тематического дешифрирова-
ния космических снимков, карт и тематических баз данных. Технология базировалась
на интеграции в единую оболочку двух основных программно-информационных
комплексов, поддерживающих два сложных последовательных этапа: 1) тематиче-
ского дешифрирования снимков с формированием тематических слоев, 2) формиро-
вания тематических карт.
Был разработан метод оперативного совмещения цифровых аэрокосмических
снимков и карт по опорным точкам. Опыт использования существующих на тот момент методов совмещения цифровых снимков (ЦС) и цифровых карт (ЦК) по опорным точкам показал, что их возможности в части повышения оперативности совмещения, его точности и эффективности ограничены. Это касалось возможности ускорения процесса выбора функциональных соотношений (ФС) и необходимого количества опорных точек для обеспечения требуемой точности совмещения ЦС и ЦК. Поскольку анализ и количественная оценка искажений, имеющихся на ЦС, этими методами не производился, то процесс выбора ФС и опорных точек реализовывался методом «проб и ошибок». В результате возникали непроизводительные затраты времени,
снижалась оперативность и точность совмещения. Предложенный метод позволил
автоматизировать процесс и снять существующие ограничения за счет анализа, количественной оценки и моделирования имеющихся на ЦС искажений, и созданной расчетным путем модели опорных точек
Был предложен интерактивный подход выделения объектов на аэрокосмических
изображениях, который сократил время оцифровки (в среднем в 2–3 раза по отношению к ручной) и повысил ее качество в случаях, когда автоматическая сегментация
не давала удовлетворительных результатов. Высокая интерактивность позволила изменять результаты выделения объекта в реальном масштабе времени с помощью
движения курсора мыши. Подход позволял эффективно выделяться как площадные,
так и линейные объекты.
Изложенные ниже выводы не столь бесспорны и непосредственно из описанных выше результатов непосредственно не следуют. Тем не менее, мы сочли возможным их сформулировать, т. к. они являются следствием опыта авторов по решению разнообразных практических задач в области распознавания и имеют в большей степени методологическое значение. Итак, первый вывод: при нынешнем положении дел в теории распознавания образов разработка еще одной модели алгоритмов почти никак не отразится ни на теории, ни на практике. Иначе говоря, настало время качественного осмысления задач распознавания на основе того опыта и чисто технических результатов, которые накоплены за последние десятилетия. Убедиться в этом совсем несложно – достаточно попытаться решить любую практическую задачу. Почти без риска ошибиться можно утверждать, что для всякой модели и любых алгоритмов найдется такая информация, которая вне зависимости от используемой методики приведет к необходимости отказа от алгоритма. И, в связи с этим, второй вывод: решение задачи распознавания – это процесс, конечной целью которого является установление точной аналитической характеризации классов. По всей видимости, такая характеризация с помощью моделей и аппарата теории распознавания образов (как это сегодня понимается) в принципе невозможна. Если, допустим, как-нибудь можно преодолеть индуктивную природу задачи, то все еще останется слишком большое множество различных моделей и решений. А это всегда является признаком не очень хорошей постановки задачи. И, наконец, последний – третий вывод, который, как нам кажется, не требует никаких комментариев: конкретная задача и ее решение всегда важнее любых теоретических построений, а уж тем более – предпочтений, чем бы они ни аргументировались