Использование множественных представлений видеоинформации в системах автоматического анализа изображений
УДК 004.932, 004.855
ИСПОЛЬЗОВАНИЕ МНОЖЕСТВЕННЫХ ПРЕДСТАВЛЕНИЙ ВИДЕОИНФОРМАЦИИ В СИСТЕМАХ АВТОМАТИЧЕСКОГО АНАЛИЗА ИЗОБРАЖЕНИЙ
© 2012 г. А. С. Потапов, доктор техн. наук
Cанкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, Санкт-Петербург
E-mail: pas.aicv@gmail.com
Проведен анализ необходимости одновременного использования многих представлений информации в системах обработки и анализа изображений. Исследовано различие между критериями Колмогоровской сложности и алгоритмической вероятности при решении задач индукции и принятия решений. Показано, что принятие оптимальных решений (например, в задачах распознавания или прогнозирования) требует использования многих представлений информации, в рамках которых конструируются альтернативные описания изображений. Выведен критерий репрезентационной алгоритмической вероятности для определения оптимального набора представлений по заданной выборке изображений.
Ключевые слова: анализ изображений, представление информации, теория информации, алгоритмическая сложность.
Коды OCIS: 150.1135
Поступила в редакцию 29.05.2012
Введение
Понятие представления является центральным для области обработки изображений. В явном виде это понятие введено Д. Марром. Под представлением он понимал формальную систему, содержащую алгоритмы, позволяющие получить описание объектов заданного класса [1]. Несмотря на такое четкое определение, до недавнего времени понятие представления оставалось не полностью формализованным. Как результат, возникала проблема оценки качества представлений, обоснования выбора того или иного представления, их оптимизация.
Проблема оценки качества представлений была теоретически решена в рамках принципа репрезентационной минимальной длины описания (РМДО) [2]. Данный принцип является расширением на случай массовых проблем (проблем, требующих нахождения единого алгоритма решения всех задач некоторого класса) принципа минимальной длины описания (МДО), дающего общее решение индивидуальных задач индуктивного вывода. Принцип РМДО дает общее теоретическое решение оценки качества представлений и выбора наилучшей модели в рамках используемого представления, однако при условии, что мо-
жет использоваться только одно представление данных.
Хорошо известно [3], что принятие промежуточных решений (в частности, в задачах распознавания изображений) делает невозможным принятие оптимального конечного решения. Например, выбор наиболее вероятной гипотезы при асимметричной матрице потерь может не согласовываться с принятием решения, минимизирующего математическое ожидание потерь. Если пропуск цели несет более значительные потери, чем ложная тревога, то мы предпочтем чаще ошибаться, поднимая ложную тревогу, нежели минимизировать число ошибок (правильность распознавания того, является ли объект целью).
В этой связи задачей индуктивного вывода можно считать не выбор одной лучшей гипотезы о содержании данных, но назначение вероятностей многим гипотезам, чтобы на основе этих вероятностей далее проводился анализ или принимались решения, которые минимизируют риски, исходя из прагматического критерия конечной задачи. Такое понимание задачи индукции (в частности, построения описаний изображений) достаточно распространено. Однако принцип РМДО показывает, что выбор наилучшего представления также сво-
16 “Оптический журнал”, 79, 11, 2012
дится к задаче индукции, в связи с чем возникает вопрос, насколько оправданно выбирать одно лучшее представление, или необходимо использовать многие представления, но учитывать их с разными весами. В данной работе дается теоретическое решение этой проблемы.
Принцип РМДО
Пусть имеется строка исходных данных
f, в качестве которых здесь рассматривается
изображение, и необходимо определить наи-
лучшую модель источника этих данных. Если
никакой другой информации не дано, то уни-
версальное решение такой задачи индукции
заключается в том, что множество моделей
определяется как множество алгоритмов (за-
данных, например, в форме программ p для
универсальной машины Тьюринга (УМТ) U,
порождающих f: U(p) = f, а лучшей считается
модель с наименьшей длиной [4]. Длина такой
наикратчайшей программы называется алго-
ритмической (Колмогоровской) сложностью
строки f
K(f)
=
min
p
éël(
p)
|
U(
p)
=
f
ùû
.
Разделение программы p на регулярную
и случайную составляющие приводит к прин-
ципу минимальной длины описания. Нас
здесь, однако, структура программы p интере-
совать не будет. Важнее то, что задачи анализа
изображений являются массовыми проблема-
ми, то есть для разных изображений некоторой
предметной области необходимо независимо
одним и тем же алгоритмом осуществлять ана-
лиз. При этом в разных изображениях содер-
жится взаимная информация, поэтому верно
неравенство K(f1f2 … fn)
ИСПОЛЬЗОВАНИЕ МНОЖЕСТВЕННЫХ ПРЕДСТАВЛЕНИЙ ВИДЕОИНФОРМАЦИИ В СИСТЕМАХ АВТОМАТИЧЕСКОГО АНАЛИЗА ИЗОБРАЖЕНИЙ
© 2012 г. А. С. Потапов, доктор техн. наук
Cанкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, Санкт-Петербург
E-mail: pas.aicv@gmail.com
Проведен анализ необходимости одновременного использования многих представлений информации в системах обработки и анализа изображений. Исследовано различие между критериями Колмогоровской сложности и алгоритмической вероятности при решении задач индукции и принятия решений. Показано, что принятие оптимальных решений (например, в задачах распознавания или прогнозирования) требует использования многих представлений информации, в рамках которых конструируются альтернативные описания изображений. Выведен критерий репрезентационной алгоритмической вероятности для определения оптимального набора представлений по заданной выборке изображений.
Ключевые слова: анализ изображений, представление информации, теория информации, алгоритмическая сложность.
Коды OCIS: 150.1135
Поступила в редакцию 29.05.2012
Введение
Понятие представления является центральным для области обработки изображений. В явном виде это понятие введено Д. Марром. Под представлением он понимал формальную систему, содержащую алгоритмы, позволяющие получить описание объектов заданного класса [1]. Несмотря на такое четкое определение, до недавнего времени понятие представления оставалось не полностью формализованным. Как результат, возникала проблема оценки качества представлений, обоснования выбора того или иного представления, их оптимизация.
Проблема оценки качества представлений была теоретически решена в рамках принципа репрезентационной минимальной длины описания (РМДО) [2]. Данный принцип является расширением на случай массовых проблем (проблем, требующих нахождения единого алгоритма решения всех задач некоторого класса) принципа минимальной длины описания (МДО), дающего общее решение индивидуальных задач индуктивного вывода. Принцип РМДО дает общее теоретическое решение оценки качества представлений и выбора наилучшей модели в рамках используемого представления, однако при условии, что мо-
жет использоваться только одно представление данных.
Хорошо известно [3], что принятие промежуточных решений (в частности, в задачах распознавания изображений) делает невозможным принятие оптимального конечного решения. Например, выбор наиболее вероятной гипотезы при асимметричной матрице потерь может не согласовываться с принятием решения, минимизирующего математическое ожидание потерь. Если пропуск цели несет более значительные потери, чем ложная тревога, то мы предпочтем чаще ошибаться, поднимая ложную тревогу, нежели минимизировать число ошибок (правильность распознавания того, является ли объект целью).
В этой связи задачей индуктивного вывода можно считать не выбор одной лучшей гипотезы о содержании данных, но назначение вероятностей многим гипотезам, чтобы на основе этих вероятностей далее проводился анализ или принимались решения, которые минимизируют риски, исходя из прагматического критерия конечной задачи. Такое понимание задачи индукции (в частности, построения описаний изображений) достаточно распространено. Однако принцип РМДО показывает, что выбор наилучшего представления также сво-
16 “Оптический журнал”, 79, 11, 2012
дится к задаче индукции, в связи с чем возникает вопрос, насколько оправданно выбирать одно лучшее представление, или необходимо использовать многие представления, но учитывать их с разными весами. В данной работе дается теоретическое решение этой проблемы.
Принцип РМДО
Пусть имеется строка исходных данных
f, в качестве которых здесь рассматривается
изображение, и необходимо определить наи-
лучшую модель источника этих данных. Если
никакой другой информации не дано, то уни-
версальное решение такой задачи индукции
заключается в том, что множество моделей
определяется как множество алгоритмов (за-
данных, например, в форме программ p для
универсальной машины Тьюринга (УМТ) U,
порождающих f: U(p) = f, а лучшей считается
модель с наименьшей длиной [4]. Длина такой
наикратчайшей программы называется алго-
ритмической (Колмогоровской) сложностью
строки f
K(f)
=
min
p
éël(
p)
|
U(
p)
=
f
ùû
.
Разделение программы p на регулярную
и случайную составляющие приводит к прин-
ципу минимальной длины описания. Нас
здесь, однако, структура программы p интере-
совать не будет. Важнее то, что задачи анализа
изображений являются массовыми проблема-
ми, то есть для разных изображений некоторой
предметной области необходимо независимо
одним и тем же алгоритмом осуществлять ана-
лиз. При этом в разных изображениях содер-
жится взаимная информация, поэтому верно
неравенство K(f1f2 … fn)