Теоретико-информационный подход к анализу изображений

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

Энтропийные методы анализа изображений

Количество информации, содержащееся в некотором сообщении, в шенноновской теории вводится на основе понятия вероятности:

formula_66

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

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

formula_67

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

В энтропийных методах различием I(H) для разных гипотез часто пренебрегают, что приводит к критерию выбора гипотезы только на основе величины I(D|H) и соответствует методу максимального правдоподобия. Величина I(D|H) зачастую принимает форму энтропии, если данные трактуются как совокупность независимых отсчетов некоторой случайной величины, тогда выбор гипотезы (модели) производится на основе принципа минимума энтропии.

К примеру, если точки изображения рассматриваются как независимые, то вероятность для всего изображения представляется как произведение вероятностей для каждой его точки:

formula_68

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

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

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

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

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

Таким образом, энтропийные методы имеют много общего с байесовскими методами. В них остается нерешенной проблема выбора формы распределения условных вероятностей и лишь частично решена проблема выбора априорных вероятностей гипотез. Энтропийные методы нашли широкое применение в задачах совмещения изображений [55, 105], выявления изменений в серии изображений [106], извлечении признаков [107] и построении контуров [108], реставрации изображений [109], распознавании объектов [110] и т.д.

Теория информации Колмогорова и принцип минимальной длины описания в анализе изображений

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

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

Пусть U – универсальная машина Тьюринга (УМТ). Алгоритмическая сложность строки β определяется как

formula_69

где l(α) – длина (количество символов) программы α . Для упрощения записи формул индекс U будем далее опускать, если он не играет роли. Программа для УМТ выступает в качестве модели источника, породившего данные β .

Обычно строку α удобно представлять в качестве конкатенации двух строк: α = μδ, где μ интерпретируется в качестве собственно программы (модели или регулярной составляющей), а δ – в качестве данных к этой программе (случайной составляющей). Тогда:

formula_70

где K(β | μ) – условная алгоритмическая сложность строки β при данной строке μ.

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

formula_71

Отсюда следует принцип минимальной длины описания [13]: наилучшей моделью является та модель, которая позволяет минимизировать сумму:

  • длины описания модели l(μ);
  • длины описания данных в рамках модели K(β | μ ).

Существует несколько близких теоретико-информационных подходов, опирающихся на алгоритмическую теорию информации:  подход на основе понятия алгоритмической вероятности (АЛВ; Algorithmic Probability, ALP), разработанного Р. Соломоновым в 1964 году [113], принцип минимальной длины сообщения (МДС; Minimum Message Length, MML), предложенный К. Уалласом и Д. Болтоном в 1968 году [114] (более поздние разработки по МДС можно найти, например, в [115, 116]), принцип минимальной длины описания (МДО; Minimum Description Length, MDL), введенный в 1978 году Ж. Риссаненом [117] и несколько пересмотренный им позднее [118], подход, называемый идеальная МДО (Ideal MDL), предложенный М. Ли и П. Витани в 1989 году [119] (см. также [120]), и принцип аппроксимации сложности (ПАС; Complexity Approximation Principle, CAP), введенный в [121]. Перечисленные подходы основываются на одной общей идее и отличаются только в определенных деталях, поэтому далее не будем делать между ними различия и будем пользоваться для их обозначения единым термином – «принцип минимальной длины описания» (МДО).

Результат (1.10) по форме близок результату логарифмирования формулы Байеса, но здесь длина описания модели не вычисляется через произвольно заданную априорную вероятность, а определяется через длину описания комбинаторной системы, порождающей соответствующие данные. Величина  2^{-l(\mu)} , где строка μ ∈ {0,1}* – некоторая программа для УМТ, соответствует априорной вероятности P(μ), только если все множество программ образует код со свойством однозначного декодирования (например, префиксный код). Это требование является естественным, поскольку длина программы может быть произвольной. Для таких кодов выполняется равенство [13]:

formula_72

что соответствует условию нормировки распределения вероятностей.

Однако способ задания комбинаторной системы с соответствующим распределением априорных вероятностей  2^{-l(\mu)} также достаточно произволен. В теоретических исследованиях указывается [122], что длины описания в рамках двух произвольных формализмов U1 и U2 отличаются не более чем на константу, не зависящую от строки β : |K_{U_{1}}(\beta)-K_{U_{2}}(\beta)|\lt C_{U1,U2} . В связи с этим утверждается, что при увеличении объема исходных данных β выбор оптимальной модели не зависит от выбора конкретного формализма.

В области анализа изображений принцип МДО стал активно применяться, начиная с 1990-хх годов, и число примеров его применения расширяется. Приведем ряд примеров.

  • Сегментация (по текстуре или цвету) изображения [123-125].
  • Выделение признаков на изображении [95].
  • Построение структурных элементов изображения [126] и их группирование [127], а также описание формы границ областей [128, 129].
  • Распознавание объектов на изображении [130] и распознавание рукописных символов [131, 132].
  • Оценивание параметров пространственного преобразования между парой изображений одной и той же сцены, снятой с разных ракурсов, по набору опорных точек [133] и собственно сопоставление и совмещение пары изображений (нахождение соответствия между точками изображений) [134].
  • Оценивание поля движения по видеосерии [135-137].

Перспективным признается использование принципа МДО в задаче выявления изменений [138], а также в ряде других задач анализа изображений [139-141].

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