Информационная технология восстановления изображений, основанная на принципах распознавания образов Чернов Андрей Владимирович

Постановка задачи построения восстанавливающих процедур с использованием P/R-методов

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

B четвертой главе диссертации рассматривается построение простых в реализации? и» быстрых классификаторов, предназначенных для преобразования изображений-признаков в: выходное (восстановленное) изображение;: производится экспериментальное сравнение классификаторов по качеству и вычислительной: сложности. Рассматриваются линейные по параметрам, древовидные (кусочно-линейный и кусочно-постоянный); классификаторы: и: классификатор в виде двухслойной нейронной сети.

Для древовидных классификаторов решается; задача соотнесениям сложности решающей функции: с количеством имеющихся данных (выработки: критерия остановки разбиения) при построении классификаторов (проблема переобучения) на основе теории, восстановления регрессии по эмпирическим; данным, предложенной Вапником [3]. Также рассматриваются множество параметров, влияющих на процесс построения древовидных классификаторов . и конкретный вид решающей \ функции" и различные способы деления перспективных вершин.

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

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

Методы исследований: В диссертационной работе используются методы распознавания образов, цифровой обработки сигналов и изображений; теории вероятностей и статистического анализа, линейной алгебры и математического анализа, методы оптимизации. Научная новизна работы. В диссертации получены следующие новые научные результаты. 1. Разработана общая схема преобразования данных для применения P/R-методов в задачах восстановления и фильтрации изображений. 2. Разработаны методы нахождения вычислительно эффективного семейства признаков, описывающих форму изображения, в т.ч. инвариантных к повороту изображения и линейному преобразованию его яркости. 3. Разработаны быстрые алгоритмы вычисления одномерных и двумерных сверток с конечной импульсной: характеристикой на основе аппроксимации последовательностями, удовлетворяющими линейно-рекуррентным соотношениям. 4. Разработаны алгоритмы параметрической оптимизации семейства признаков в P/R-методах. 5. Разработаны алгоритмы обучения древовидных классификаторов, осуществляющих преобразование признаков в выходное (восстановленное) изображение, способы\ разбиения признакового пространства и правила остановки процесса обучения. 6. Разработана сквозная информационная технология синтеза и применения восстанавливающих процедур с использованием P/R-методов. Практическая ценность работы. Разработанная информационная технология может быть использована для восстановления изображений в системах технического зрения при самых общих предположениях о характере искажений и классе обрабатываемых сигналов. Построенные быстрые алгоритмы восстановления могут быть использованы в цифровых системах оперативного анализа видеоинформации в режиме реального времени (в темпе видеоизмерений). Отдельные алгоритмы, разработанные в рамках технологии, имеют применение, выходящее за рамки восстановления изображений. Алгоритмы формирования и параметрической оптимизации семейства локальных признаков могут применяться в широком классе задач распознавания изображений. Процедуры быстрого вычисления признаков могут использоваться для синтеза цифровых одномерных и двумерных рекурсивных фильтров с конечной импульсной характеристикой. Предложенный в диссертационной работе подход позволяет, с одной стороны, улучшить качество восстановления за счет адаптации к свойствам обрабатываемых сигналов и более полного использования априорных данных, ас другой стороны, совместно с рекурсивными алгоритмами формирования локальных признаков, радикально снизить вычислительную сложность обработки видеоинформации. Реализация результатов работы. Результаты диссертации внедрены в рамках ряда госбюджетных и хоздоговорных научно-исследовательских работ в Институте систем обработки изображений РАН и ЗАО "Самара-Информспутник". Апробация работы. Основные результаты работы докладывались на следующих конференциях: 3-й Всероссийской конференции "Распознавание; образов и анализ изображений: новые информационные технологии" (РОАИ-3-97), г. Нижний Новгород, 1997; 5h Open German-Russian Workshop on Pattern Recognition and Image Understanding, 21-25 сентября 1998г., г.Херршинг, Германия; 4-й Всероссийской конференции "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-4-98), г.Новосибирск, 1998; 5-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-5), Самара, 2000; 6-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-6), Великий Новгород, 2002. Работы по тематике диссертации были поддержаны грантами Российского фонда фундаментальных исследований (проекты № 96-01-00453, № 00-01-00600) Президента РФ № НШ-1007.2003.01 и Американского фонда гражданских исследований и развития (CRDF Project SA-014-02) в рамках российско-американской -программы "Фундаментальные исследования и высшее образование" (BRHE)..

Обеспечение инвариантности к повороту для системы признаков, описывающих форму изображения

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

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

При наличии априорной информации о классе изображений, предъявляемых для классификации (замкнутость семейства относительно локальных трансформаций определенного вида) необходимо при обучении и классификации использовать ограниченный набор признаков (например, не используя оценку угла поворота). Экспериментальные исследования по эффективности предложенных систем признаков приводятся в параграфе 4.8. Выводы и результаты Рассмотрены вопросы формирования признаков в задаче восстановления изображений. 1) Приведены примеры эффективно вычисляемых систем признаков - локальные обобщенные моменты с ядрами из прямоугольного и полиномиального базиса, а также моментные инварианты (параграф 2.1). 2) Получены семейства признаков, описывающих форму изображения на основе аппроксимации полиномом заданного порядка (параграф 2.2). 3) Разработан алгоритм нормализации семейства признаков, описывающих форму, к повороту изображения и линейному преобразованию яркости (пп. 2.2.1 — 2.2.2.). Важным свойством полученной системы признаков является обратимость процедуры нормализации, из которой следует отсутствие межпризнаковых функциональных зависимостей. Использование указанной системы признаков является альтернативой к использованию моментных характеристик (моментов и моментных инвариантов) при наличии априорной информации о замкнутости класса изображений относительно поворота и линейного преобразования яркости. 4) Получены оценки сложности вычисления системы признаков и проведения алгоритма нормализации. Все рассматриваемые в данной главе признаки являются обобщенными моментами (локальными свертками изображения с различными импульсными характеристиками) или эффективно вычисляются на их основе. В главе 3 рассматриваются методы ускорения вычисления локальных сверток с помощью аппроксимации произвольных импульсных характеристик семейством рекурсивных ядер.

Обработка изображений в режиме- "скользящего окна", осуществляемая, , в частности, для формирования» обобщенных моментов, предполагает вычисление цифровой свертки входного сигнала с конечной импульсной? характеристикой: линейных систем с постоянными параметрами (КИХ-фильтров) [20]. При этом "прямое" вычисление свертки для? каждого положения окна взвешенным суммированием отсчетов имеет практический смысл лишь для малых размеров окна, т.е. для? короткой І импульсной характеристики, поскольку объем вычислений; здесь пропорционален числу ненулевых отсчетов последней: Для больших окон (в задачах фильтрации и восстановления сигналов, вычисления признаков, корреляционного обнаружения І объектов и т.д.) прямое вычисление свертки; оказывается чрезмерно трудоемким. В этой связи; представляется целесообразным применение алгоритмов, воплощающих идею рекурсивной реализации: КИХ-фильтров, развитую в работах [24,25,46]. Основная; идея; этих алгоритмов - приближение конечной импульсной? характеристики; семейством; функций специального вида, вычисление свертки с которыми допускает рекурсивную реализацию с помощью разностных схем.

В данной главе рассматривается? задача построения наилучших приближений произвольно заданной" на отрезке конечной импульснойI характеристики линейно-рекуррентным соотношением; (ЛРС) R-того порядка. Как показано в [25], вычислительная сложность нахождения выходного отчета для такой і реализации зависит только от порядка рекуррентности R и не зависит от размеров окна обработки; N. Практически для R«N эту задачу можно рассматривать как задачу минимизации ошибки вычисления выходного сигнала при заданной пользователем вычислительной сложности обработки. Необходимо также заметить, что переход к рекуррентому вычислению выходного сигнала - это единственный. способ радикального снижения і вычислительной сложности по сравнению со сложностью вычисления прямой свертки или ее реализации с помощью дискретных ортогональных преобразований;

В теории построения рекурсивных фильтров; с бесконечной импульсной характеристикой (БИХ-фильтров) [ 15,22] эта задача решается путем приближений z-преобразования исходной импульсной характеристикой дробно-рациональной функцией различными методами [41,47,51]. В данной главе, с одной стороны, эти методы обобщаются для проектирования КИХ-фильтров, ас другой стороны, выполняется обобщение методов проектирования рекурсивных. КИХ-фильтров [24,25,46] специального вида за счет рассмотрения более широкого класса функций, удовлетворяющих ЛРС.

Следует заметить, что результаты, полученные в данной главе, охватывают гораздо более широкий класс задач, чем рекурсивное вычисление признаков в P/R-методах. Все рассмотренные во второй главе признаки эффективно вычисляются на і основе начальных моментов (сверток с многочленами). Полученные оценки; вычислительной сложности для такого частного случая (вычисления двумерных сверток с многочленами) совпадают с оценками: вычислительной сложности, полученными ранее в работах [8,46]. Исключением: является случай подсчета моментов и производных характеристик с нетривиальной функцией окна (импульсная характеристика отлична от "дельта-импульса"). Однако при использовании в качестве признаков других локальных обобщенных моментов (сверток с гауссовским фильтром, LOG-масок [20] и др.) использование результатов данной главы ведет к ускорению расчета признаков при приемлемой погрешности вычислений.

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

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

Заметим, что качество=построения таких классификаторов в большой степени зависит от способа:разбиения признакового пространства на подобласти. Наиболее естественным; было бы применение какого-либо алгоритма автоматической; таксономии г с фиксированным числом кластеров [29]. Существуют работы [11] по адаптивному подбору критерия кластеризации в- зависимости от ошибки аппроксимации? функции решения на кластерах. Однако такие процедуры требуют-существенно большего числа операций на этапах обучения и классификации, чем рассматриваемые древовидные (иерархические) классификаторы.

Поэтому в данной; работе используются древовидные классификаторы, при построении которых используется более простая схема разбиения. Синтез такого классификатора заключается в следующем. В процессе обучения область определения-функции решения; представляющее собой -мерный гиперкуб, последовательно разбивается по осям? и порождает в памяти ЭВМ древовидную структуру (см. "двумерную" иллюстрацию на рисунке 43.). В каждой из областей, полученных в результате разбиения, аппроксимация функции решений в соответствии с выбранным критерием (например, обычным методом наименьших квадратов (4.2) для варианта линейной аппроксимации). Области с малой ошибкой аппроксимации принимаются за терминальные вершины дерева. Те области; в которых ошибка велика, подвергаются; дальнейшему разбиению. Процедура обучения завершается либо при достижении заданной точности аппроксимации, либо при исчерпании ресурсов памяти ЭВМ, отведенной на хранение древовидной структуры вместе с коэффициентами аппроксимации в терминальных вершинах дерева.

Как показали эксперименты, такие классификаторы при небольшой размерности признакового пространства достаточно быстро обучаются; и далее: демонстрируют хорошие результаты распознавания при весьма незначительных вычислительных затратах. Рассмотрим общую рекурсивную схему построения дерева решений; Пусть на некотором этапе построения имеется дерево решений В (в начале построения рассматривается дерево, состоящее из одной корневой вершины). С этим? деревом последовательно проводятся следующие операции. 1) Определение перспективности деления на подобласти конечных вершин. В соответствии с выбранным критерием (во всех нижеописанных методах им служит ошибка аппроксимации), вершины упорядочиваются по степени перспективности; Определяется количество перспективных вершин, подлежащих делению. 2) Деление перспективных вершин. Определяются оси (номера признаков), по которым происходит деление и пороги деления. Перспективные вершины заменяются на поддерево, состоящее из двух новых конечных вершин. 3) Построение аппроксимирующей функции в новых конечных вершинах и вычисление ошибки аппроксимации. 4) Проверка условий завершения процесса. В случае их невыполнения - переход на шаг 1. В памяти ЭВМ для древовидного классификатора в нетерминальных вершинах хранятся значения признака и порога разбиения (если эти параметры определяются адаптивно для каждого нетерминального узла), а для терминальных вершин хранятся элементы, необходимые для получения оценки идеального изображения (коэффициенты аппроксимации для кусочно-линейного классификатора). При применении древовидных классификаторов для каждого пришедшего на классификацию вектора Жщ п2) происходит последовательное сравнение значений признаков с порогами в нетерминальных узлах, находится соответствующая вектору терминальная вершина и вычисляется оценка у(щ,П2). В следующих пунктах рассматриваются различные виды аппроксимации в терминальных вершинах. В общем случае при построении кусочно-линейной аппроксимации используются формулы (4.2)-(4.3) и находится линейная аппроксимация (способом описанным в пункте 4.Ш) в каждой из терминальных вершин построенного древовидного классификатора. При этом погрешность в каждой терминальной вершине древовидного» классификатора считается по формуле (4.8), которая аналогична формуле (4:3), с той лишь разницей, что суммирование ведется лишь по точкам, попавшим в данную терминальную вершину: где А1- количество признаков по которым строится аппроксимация, N(i) - количество точек попавших в /-ую терминальную вершину. Общая суммарная погрешность вычисляется по формуле (4.7). В памяти ЭВМ при таком виде аппроксимации в каждой из терминальных вершин1 хранится полный набор из К вещественных значений а - коэффициентов аппроксимирующей гиперплоскости. При построении древовидных классификаторов существует множество различных параметров, от правильного подбора которых зависит качество аппроксимации и скорость обработки при наличии дополнительных ограничений на вычислительные ресурсы. Перечислим и проклассифицируем эти параметры. 1) Параметры информационной модели восстановления изображений: - число признаков К (размерность признакового пространства); - конкретный вид признаков Ц% = С"о/ »-» / ЛГ-І,/ ) (см- главу 2); - вид аппроксимирующей функции (оператора R (1.4)) - кусочно-линейная, кусочно-постоянная (см. параграф 4.1); - вид функции потерь I - в рамках данной работы принимается показатель среднеквадратичной ошибки (4.1); - допустимая ошибка аппроксимации на обучающей выборке є in. 2) Параметры, описывающие ограничения вычислительной реализации: - максимальный объем памяти, отводимый под хранение параметров классификатора (максимальное количество терминальных узлов при заданном виде аппроксимирующей функции) Ртах;= Ртах(R,K); - максимальная hmax или средняя И глубина, дерева (максимальное или среднее количество операций сравнения с порогом при классификации); - максимальное время,.отводимое на процедуру обучения tmax - определяется через максимальное количество итераций при разбиении признакового пространства. 3) Параметры, описывающие процесс разбиения признакового пространства: - способ разбиения узлов древовидного классификатора (номер признака, по которому происходит разбиение и значение порога разбиения); - количество разбиваемых узлов на каждом шаге итерации;: - параметры остановки процесса разбиения.

Методы повышения устойчивости вычислительного алгоритма кусочно-линейной аппроксимации

Поэтому, задав начальное приближение р0, можно найти оптимальные значения векторов р и а, используя метод градиентного спуска. Отметим, что на каждом шаге итерации производится минимизация сразу и по вектору параметров р, и по коэффициентам линейной аппроксимации а. Проведя минимизацию выражения (4.16), мы получим первое приближение рі: Рік = Рок+ которое будет использовано в качестве р0 на втором шаге, и так далее пока норма разности р - р0 не станет меньше некоторого, наперед заданного, значения. Тогда коэффициенты при Мк(Рок) в (4.16) стремятся к нулю и определяющими являются значение Рк(Р0к) следовательно, значение параметрар является близким к оптимальному.

Итерационный процесс совместной оптимизации по вектору параметров р и коэффициентам аппроксимации а состоит из следующих шагов. 1) Задаются начальные приближения р . 2) Вычисляется система изображений - признаков цк (р0) и juk (р0) 3) Находятся матрицы М и М, вектора си с и решается СЛУ (4.17) относительно Переменных tf и & . 4) Находятся р = Pok+ kfak и проверяется условие завершения процесса (норма разности коэффициентов, полученных на предыдущем и последующем шагах, не превышает наперед заданное є). 5) Если условие завершения не выполняется, происходит переход к шагу 2) с начальными приближениями Рок=Рк Этот же принцип легко обобщается и на случаи зависимости одного или нескольких от векторных параметров цк.= (рр. При этом система уравнений (4.17) решается относительно параметров а и b # = (р# - ро )ак. В случае зависимости нескольких признаков от одного параметра р (неважно, скалярного или векторного) система уравнений (4; 17) относительно переменных яд и; Ъ . получается переопределенной. В самом деле, пусть для простоты изложения и без ограничения общности- К признаков зависят от одного параметра и (М-К) признаков не зависят от параметров. Мы имеем систему из (М+К) линейных уравнений относительно переменных ад и Ь , всего лишь с (М+1) неизвестными..Таким образом необходимо решать систему из (М+К) линейных уравнений с учетом К-Ї ограничений. Более простым способом является использование метода покоординатного спуска. Зафиксировав некоторое р=ро, найдем оптимальные значения вектора весовых коэффициентов: faf} решив систему (4Л7). После чего, используя полученный набор коэффициентов {а, }"+1 найдем popt, взяв производную от функционала (4.16) по (р-ро) и решив GЛУ относительно р; Процесс продолжается до,тех пор пока разница не будут меньше какого-между найденным рот и PQ, , и норма вектора aSn _ я(п !) либо наперед заданного значения. Замечание 1. В задаче распознавания образов на классы из-за недифференцируемости функции; решения для подобной подстройки прибегают к достаточно сложным методам алгебраического замыкания; [12] (если рассматривать.различные алгоритмы распознавания как признаки). В [5] приводится общий подход для методов линейной и монотонной» коррекции, который для задач; восстановления регрессии? фактически представляет собой метод покоординатного спуска поочередного нахождения параметров І признаков (алгоритмов) и корректирующих коэффициентов. В отличие от него, приведенные в параграфе алгоритмы (при указанных допущениях) позволяют проводить минимизацию сразу и по параметрам: признаков, и по коэффициентам коррекции, что существенно повышает сходимость алгоритма. Замечание 2. Приведенные алгоритмы минимизации являются, по сути, градиентными, как и алгоритмы: обратного распространения ошибки обучения нейронных сетей; (см. параграф 4.2). Однако модификация алгоритма параметрической оптимизации для входных нейронов первого слоя в алгоритме back propagation при использовании нейронной сети вместо линейного классификатора выходит за рамки настоящей диссертации. При восстановлении изображений с помощью P/R-методов одним из параметров обработки является размер окна, используемый для вычисления признаков. Заметим, что процедуры, описанные в п.4.6.1, можно выполнить и в случае, когда параметр р принимает упорядоченное множество дискретных значений (например, размер окна для вычисления признаков на изображении). В этом случае роль «производных по параметру» играют их дискретные аналоги - разности в значениях признаков на соседних значениях параметров. Значения (р-ро) на каждом шаге итерации показывают направление и предполагаемую величину изменения дискретного параметра (размера окна). Другим вариантом является использование так называемых гауссовских окон для признаков, вычисляемых с помощью локальных сверток изображения в окне, суть которых состоит в умножении исходной импульсной характеристики h(ni,n2) на двумерную гауссовскую функцию:

Параметр а в этом случае для каждого из признаков находится с помощью методов, описанных в п. 4.6.1.. Если по причине сокращения объема вычислений нежелательно использовать модифицированные признаки, умноженные на функцию гауссовского окна, то можно после предварительного подбора параметра а далее использовать окно обработки D = [-За,За] х [-Зет, За] для исходных признаков.

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

Разработанные в работе алгоритмы легли в основу общей информационной технологии построения восстанавливающих процедуру основанной на итерационном усложнении решающего правила. Основу информационной технологии составляет процедура последовательного наращивания размерности признакового пространства ("Step-Up" метод) [19]. Согласие ей, сначала выбирается единственный признак, обеспечивающий экстремальное значение показателя качества, затем к нему присоединяется еще один, дающий наилучшее качество линейной аппроксимации в паре с уже выбранным признаком, и т.д. до получения набора из К признаков; Идея "Step-up" метода обобщается для случая построения древовидных классификаторов, если рассматривать в качестве процедур наращивания сложности разделение вершин дерева, присоединение очередного признака; непараметрического семейства и присоединение одного признака параметрического семейства с найденным значением параметра.

Похожие диссертации на Информационная технология восстановления изображений, основанная на принципах распознавания образов

Байесовские методы опорных векторов для обучения распознаванию образов с управляемой селективностью отбора признаковТатарчук Александр Игоревич

Методы и алгоритмы беспризнакового распознавания образовСередин Олег Сергеевич

Методы распознавания образов в массивах взаимосвязанных данныхДвоенко Сергей Данилович

Разработка и исследование модели знакового представления данных в задачах распознавания образовГончаров, Александр Владимирович

Метод опорных объектов для обучения распознаванию образов в произвольных метрических пространствахАбрамов, Вадим Игоревич

Логико-комбинаторные задачи дискретного моделирования: системы распознавания образовАсланян, Левон Акопович

Спектрально-аналитические методы обработки данных и распознавания образовКуликова Людмила Ивановна

Методы решения задач распознавания образов комбинированного типаБорисова Ирина Артемовна

Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходеКосовская, Татьяна Матвеевна

Разработка и исследование метода создания и использования хранилищ ключевой информации на основе распознавания биометрических образов Тумоян Евгений Петрович