ПРИМЕНЕНИЕ СИГНАЛЬНЫХ МИКРОПРОЦЕССОРОВ В ЗАДАЧАХ РЕКОНСТРУКЦИИ ИСКАЖЕННЫХ ИЗОБРАЖЕНИЙ
ОБРАБОТКА СИГНАЛОВ И ИЗОБРАЖЕНИЙ
УДК 004.932:621.397.3:517.983.5
К. А. КИРЬЯНОВ, В. С. СИЗИКОВ
ПРИМЕНЕНИЕ СИГНАЛЬНЫХ МИКРОПРОЦЕССОРОВ В ЗАДАЧАХ РЕКОНСТРУКЦИИ ИСКАЖЕННЫХ ИЗОБРАЖЕНИЙ
Исследуются особенности инструментальной реализации алгоритмов реконструкции искаженных (смазанных, дефокусированных или/и зашумленных) изображений. Рассмотрены прямая задача — моделирование искажения или получение реального искаженного изображения и более сложная и важная для практики обратная задача — реконструкция (восстановление) изображения.
Ключевые слова: искажение изображения, прямая и обратная задачи, сигнальные микропроцессоры, программируемая логическая интегральная схема.
Описание реализуемых алгоритмов. Известная задача реконструкции (восстановле-
ния, реставрации) искаженных (смазанных, дефокусированных или/и зашумленных) изобра-
жений ([1—7] и др.) может быть практически решена не только на универсальных ЭВМ (или
персональных компьютерах), но и на спецпроцессорах ([8—11] и др.). Использование спец-
процессоров ведет, во-первых, к уменьшению габаритов обрабатывающих устройств, а во-
вторых, позволяет превратить недостаточно совершенный прибор наблюдения (фотоаппарат,
телескоп, микроскоп и т.д.) в более совершенный путем подключения к нему спецпроцессора
с заложенным в него алгоритмом обработки.
В работе рассматривается задача инструментальной реализации алгоритмов реконст-
рукции искаженных изображений с помощью сигнальных микропроцессоров и программи-
руемых логических интегральных схем (ПЛИС) [8—11].
Однако прежде чем вести речь о технической реализации алгоритмов, необходимо ска-
зать несколько слов о самих алгоритмах. Основные соотношения и уравнения, описывающие
эти задачи в непрерывном виде, следующие [2—7]:
∞
∫ h(x − ξ) wy (ξ) dξ = g y (x) + δg ,
(1)
−∞
∞∞
∫ ∫ h(x − ξ, y − η) w(ξ, η) dξ dη = g(x, y) + δg ,
(2)
−∞ −∞
где h — функция рассеяния точки (ФРТ), в большинстве случаев пространственно-
инвариантная (или разностная), w и g — распределение интенсивности по неискаженному и
искаженному изображению соответственно, δg — помеха. В соотношении (1) ось x направле-
на вдоль смаза, а y играет роль параметра.
Интегральное уравнение (ИУ) (1), точнее набор одномерных интегральных уравнений,
обычно используется в задаче смазывания, а (2) — в задаче дефокусировки изображения [4, 6, 7].
Для решения интегральных уравнений (1) и (2) наиболее подходит метод регуляризации Ти-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
Применение сигнальных микропроцессоров в задачах реконструкции искаженных изображений 21
хонова [2—7, 12]. Так как для инструментальной реализации интерес представляют числен-
ные методы, в настоящей работе им и уделено внимание. При численной реализации метода
регуляризации Тихонова для решения обратной задачи обычно используются метод преобра-
зования Фурье (ПФ) и метод квадратур [2, 3, 5—7]. Используются также методы итераций,
например, метод итеративной регуляризации Фридмана [2, 7, 12].
Метод квадратур эффективен при решении набора одномерных ИУ (1) [6, 12, 13], каж-
дое из которых можно записать в операторной форме:
Aw = g + δg ,
(3)
где A — интегральный оператор. Для нахождения функции w необходимо построить такой
оператор A−1 , который давал бы устойчивое приближение к w. Непрерывным уравнениям (1)
можно поставить в соответствие дискретные выражения типа (3). Тогда (3) преобразуется в
систему линейных алгебраических уравнений (СЛАУ), где A — матрица, связанная с ФРТ.
Однако задача решения уравнений (1)—(3) является некорректной [2, 3, 5—7, 12].
В методе регуляризации Тихонова вместо (3) решается уравнение
(αE + AT A) wα = AT g ,
(4)
где α > 0 — параметр регуляризации, E — единичный оператор (единичная матрица). Матри-
ца αE + AT A является квадратной, симметричной и положительно-определенной, СЛАУ (4) имеет решение и численно устойчива [2, 3, 12, 14]. В результате получаем решение в виде:
wα = (αE + AT A)−1 AT g .
(5)
Способы выбора α изложены, например, в [2, 3, 5—7, 12].
Метод регуляризации Тихонова с использованием преобразования Фурье применим для
решения уравнений типа свертки. Рассмотрим частный случай ИУ Фредгольма I рода —
уравнение типа свертки одномерное (1) и двумерное (2). Если ИУ вида (1) при его численном
решении методом квадратур требует размещения в компьютерной памяти матрицы СЛАУ, то
для решения одномерного уравнения типа свертки возможно применять метод ПФ, опери-
рующий лишь с векторами, и это требует меньшего объема памяти и времени решения. Осо-
бенно важен вопрос о памяти и времени при аппаратной реализации метода, в еще большей
степени — для двумерного уравнения (2).
Задача смазывания сводится к решению одномерного ИУ Фредгольма I рода типа сверт-
ки (1) относительно wy (ξ) при каждом фиксированном значении y, играющем роль парамет-
ра. В уравнении (1) ФРТ выражается формулой [2, 3, 6]:
h(x)
=
⎧ ⎨ ⎩
1∆ 0,
,
− ∆ ≤ x ≤ 0, иначе.
(6)
Решение уравнения (1) методом ПФ с регуляризацией Тихонова имеет вид [2, 3, 5—7, 12]:
∫wα y (ξ)
=
1 2π
∞
Wα y (ω) e−i ωξ
−∞
dω,
(7)
где
Wαy (ω)
=
|
H (−ω)Gy (ω) H (ω) |2 + αω2 p
,
(8)
∞∞
∫ ∫H (ω) = h(x) eiωxdx , Gy (ω) = g y (x) eiωxdx , −∞ −∞
где p ≥ 0 — порядок регуляризации.
(9)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
22 К. А. Кирьянов, В. С. Сизиков
Особенности технической реализации изложенных алгоритмов. Решать задачи, опи-
сываемые уравнениями (1) и (2), на универсальных ЭВМ или ПК возможно в рамках системы
MatLab. Однако такой способ не всегда оптимален по затрачиваемому на решение времени.
Существуют ситуации, когда на выполнение задачи отводится очень мало времени и
нужно выполнить обработку изображения в режиме реального времени. Такие ситуации воз-
никают, когда, например, необходимо распознать самолет, нарушитель территориальных
границ, и восстановить опознавательные знаки на нем. При этом самолет может лететь на-
столько быстро, что получаемое изображение смазывается. У оператора очень мало времени,
чтобы распознать характеристики самолета и принять решение. Задача намного усложняется,
если помимо смазывания изображения самолет находится не в фокусе, а поскольку процесс
быстротекущий, то устройства автофокусировки отработать не успевают ни на одном из по-
лученных кадров.
Очевидно, что для решения таких задач требуемая производительность должна быть
выше, чем у современных ПЭВМ. Одним из важнейших требований к техническим средствам
является обеспечение режима обработки сигналов в реальном времени (со скоростью их по-
ступления) при приемлемых стоимостных и массогабаритных характеристиках системы. Так,
некоторые технические задачи цифровой обработки изображений требуют быстродействия аппаратных средств порядка 109—1010 операций в секунду для обеспечения обработки в ре-
альном времени.
Другой особенностью подобных задач является необходимость обработки больших
объемов (от 1 МБ и более) сложноструктурированных многомерных данных, что вносит до-
полнительные трудности в организацию вычислений и требования к правильному распреде-
лению памяти в ходе решения задачи.
Особенности при реализации на цифровом сигнальном процессоре. Как уже сказано,
существуют два метода решения интегрального уравнения (1), описывающего задачу смазы-
вания:
1) общий случай — решение методом квадратур с регуляризацией Тихонова;
2) частный случай, характерный для уравнений типа свертки — метод ПФ с регуляриза-
цией Тихонова.
Несколько слов о первом методе. Для восстановления изображения нужно знать
искажающее воздействие (ФРТ) h(x, ξ) в общем случае, когда ФРТ не является пространст-
венно-инвариантной (разностной), или h(x − ξ) в случае, когда ФРТ является пространствен-
но-инвариантной. При замене в уравнении (1) интеграла конечной суммой получаем СЛАУ
(3), где по ФРТ можно найти матрицу A как матричный оператор искажающего воздействия,
согласно соотношению
⎡ h(c, a)
h(c, a + hξ ) ... h(c,b) ⎤
h(x, ξ)
→
A
=
⎢⎢h(c ⎢ ⎢
+ hx ...
, a)
h(c + hx , a + hξ ) ...
... ...
h(c
+ hx ...
,
b)
⎥ ⎥ ⎥ ⎥
,
⎣⎢ h(d, a)
h(d, a + hξ ) ... h(d ,b) ⎦⎥
(10)
где hx и hξ — шаги дискретизации по x и по ξ соответственно. Затем эта матрица транспони-
руется и вычисляется матрица αE + AT A , из которой с помощью метода Гаусса—Жордана
[13, 14] получаем обратную, которая хранится в памяти устройства до завершения восстанов-
ления изображения, после чего находится решение, согласно (5). Также решение уравнения
(4) можно получить с помощью метода LU-разложения или методом квадратных корней
Краута—Холецкого [12].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
Применение сигнальных микропроцессоров в задачах реконструкции искаженных изображений 23
Для решения по методу ПФ с регуляризацией Тихонова, как и в предыдущем случае, требуется знать искажающее воздействие и, как уже говорилось, этот метод может быть применен только для пространственно-инвариантной ФРТ. Важно правильно и грамотно распределять память сигнальных микропроцессоров. Для этих целей обычно применяется алгоритм быстрого преобразования Фурье (БПФ) [10, 15, 16]. При использовании БПФ не только сокращается время выполнения всей процедуры (за счет исключения повторяющихся операций), но и происходит экономия памяти.
Для вычисления обычного дискретного ПФ нужны 4 массива: два для действительной и мнимой частей исходного процесса (оригинала изображения) и два — для вычисленного фурье-образа (фурье-спектра изображения). При использовании БПФ можно обойтись двумя массивами, потому что процесс вычисления БПФ итерационный. Число отсчетов N должно
быть целой степенью числа 2, тогда количество итераций будет равно log2 N , а выполнение
самой процедуры возможно с использованием той же области памяти, в которой находились исходные данные. Таким образом, для решения по этому методу с использованием алгоритма БПФ вычисляется фурье-спектр исходного процесса (каждой строки изображения), затем ФРТ, которая в большинстве случаев короче самого изображения и которую нужно дополнить до N нулями, после чего поточечно вычисляется соотношение (8), называемое регуляризованным спектром. И, наконец, от полученного массива, длина которого тоже является целой степенью числа 2, вычисляется обратное ПФ, при котором также используется алгоритм БПФ.
При восстановлении дефокусированных изображений, описываемых уравнением (2), нельзя применить метод квадратур (кубатур) из-за необходимости обращения трехмерной матрицы, что практически невозможно из-за требуемого чрезвычайно большого объема памяти для решения такой задачи. Если нет аберраций линзы и объектив не является широкоугольным, то можно считать ФРТ пространственно-инвариантной. Таким образом, задача описывается двумерным уравнением типа свертки (2), которое можно решать с помощью ПФ. Здесь решение находится также с применением алгоритма двумерного БПФ и данную задачу иначе решить крайне сложно, так как используются двумерные массивы, а у специализированных процессоров довольно мал объем оперативной памяти, в который нужно уложиться.
При решении ИУ методом ПФ для уменьшения эффекта Гиббса можно использовать размытие краев [6, 7] (рис. 1). Для случая, когда ФРТ не является пространственноинвариантной, решение ИУ (2) можно осуществить итерационными методами, такими как метод итеративной регуляризации Фридмана, метод Ландвебера и др. [2, 12].
h(x, y) (ФРТ)
∆
g(x, y)
g(x, y) с размытыми
границами
h(x, y) (ФРТ)
∆
∆∆
Рис. 1
Из всей номенклатуры предложенной элементной базы фирмы Texas Instruments (TI) [16] наиболее подходящими для решения перечисленных задач являются микропроцессоры семейства TMS320C64++, устройства с фиксированной запятой, разработанные специально для математической обработки изображений. Из их числа самыми подходящими являются процессоры C6455 и C6457. Структурная схема такого устройства отображена на рис. 2.
Ядро процессора состоит из восьми вычислительных узлов, двух файлов регистров общего назначения, двух шин данных. Каждый из файлов регистров (A и B) содержит по тридцать два 32-разрядных регистра. Действия можно выполнять с 8-, 16-, 32-, 40- и
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
24 К. А. Кирьянов, В. С. Сизиков
64-разрядными данными. При разрядности данных более 32 бит они сохраняются в парах регистров. Восемь функциональных вычислительных узлов (M1, L1, D1, S1, M2, L2, D2, и S2) способны выполнять по одной инструкции за каждый машинный такт (M — умножители, S и L выполняют арифметико-логические и сдвиговые операции, D обеспечивают обмен данными между памятью и регистровым файлом). При операции комплексного умножения используются четыре 16-разрядных операнда (по два действительных и два мнимых), получаемый результат — 32 бита действительная часть и такая же мнимая. Также возможно выполнять комплексные умножения с округлением, в результате чего 32-разрядный результат содержит действительную и мнимую части, на каждую из которых отводится по 16 разрядов (см. рис. 2). В некоторых случаях это весьма удобно для вычисления ПФ.
32 бита Re yα
32 бита Im yα
Считывание команд Декодирование команд
Регистры состояния Буфер команд
Внутрисхемная эмуляция
L2 S2 M2 D2
L1 S1 M1 D1
16 бит Re yα
16 бит Im yα
Регистровый файл В
Регистровый файл А
Рис. 2
Реализация всех алгоритмов для процессоров TI выполняется на языке C++ в специальной среде Code Composer v.4.0, поставляемой с отладочным модулем. Несколько реже применяются микропроцессоры другой фирмы, Analog Devices [17], для работы с которыми производителем поставляется программная среда VisualDSP++, программы выполняются тоже на С++. При этом программы, разработанные в среде MatLab, требуют выполнения двойной компиляции, что не является оптимальным по быстродействию и распределению памяти.
Особенности реализации метода на основе ПЛИС. Производительность даже специализированного процессора всегда меньше, чем производительность специализированного аппаратного блока, например, реализованного на основе программируемой логической интегральной схемы. Подход состоит в том, что для того или иного вида обработки изображений на базе ПЛИС реализуется конечный автомат, способный выполнять только одну функцию. При этом достигается максимально возможная производительность, которая определяется используемой разработчиком и производителем ПЛИС технологией изготовления (ALTERA, XILINX), но гибкость решения присутствует лишь в той мере, в которой ее предусмотрел разработчик.
Для реконструкции изображений при решении задачи методом квадратур необходимо
правильно сформировать матрицу A, произвести ее транспонирование AT , получить уравнение Тихонова (4), перемножив при этом транспонированную матрицу на исходную и на правую часть уравнения g, и решить уравнение Тихонова, которое может быть решено методом Гаусса—Жордана; схема такого устройства предложена в работе [8]. Сложность состоит только в том, что размерность матрицы нельзя сделать выше определенной величины, которая закладывается при разработке. Структурная схема такого устройства приведена на рис. 3 (здесь K — коммутатор).
Точно так же можно получить решение и для метода регуляризации Тихонова с ПФ для данной задачи — с помощью многоканальной систолической матрицы, систолического процессора БПФ, особенности реализации которых описаны в работе [8]. Производители FPGA
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
Применение сигнальных микропроцессоров в задачах реконструкции искаженных изображений 25
XILINX поставляют готовые программные конфигурации ПЛИС с реализацией различных
видов ПФ. Структурная схема таких устройств для решения задачи (1) приведена на рис. 4
(здесь ОБФП — обратное быстрое преобразование Фурье).
w(ξ) Прямая задача gy(x) Обратная задача
× gy(x) w(ξ)
Прямая задача
K
h(x, ξ)
A
K
Обратная задача
AT×A+αE
Обращение
матрицы
Рис. 3
gy(x) h(x)
БПФ Gy(ω)
БПФ
Н(–ω) Н(ω)
Н(–ω)Gy(ω) |Н(ω)|2+αω2p
|Н(ω)|2 ×
wy(ξ) ОБПФ
Рис. 4
На практике подход к разработке перечисленных устройств выбирается в зависимости от сложности алгоритма обработки и требований по временным параметрам. Довольно часто выбирают комбинированный подход, при котором используются как ПЛИС с реализованными функциями, требующими наибольшего быстродействия и не требующими большой гибкости, так и цифровой сигнальный процессор для реализации той части, где он будет справляться с алгоритмом по быстродействию, но где нужен более гибкий подход к решению.
Выводы. В работе используются в виде инструментальной реализации следующие приемы обработки изображений: „усечение“, „размытие краев“ и „поворот“ при использовании известных методов решения интегральных уравнений — преобразования Фурье или квадратур с регуляризацией Тихонова [6, 7]. Прием усечения используется для того, чтобы избежать так называемых „граничных условий“ [4]. Прием размытия краев используется для уменьшения эффекта Гиббса (эффекта ложных волн на изображении). Прием поворот используется для решения задачи смазывания при произвольном угле.
Указанные методы восстановления изображений могут применяться в таких областях, как томография (возникновение смазывания из-за случайных движений пациента во время обследования), восстановление старых фотографий, обнаружение самолетов-нарушителей территориальных границ и т.п. При этом необходима реализация методик на современной элементной базе, специализированной для обработки сигналов и адаптированной для быстрых алгоритмов.
Работа выполнена при поддержке РФФИ (грант № 09-08-00034а).
СПИСОК ЛИТЕРАТУРЫ
1. Бейтс Р., Мак-Доннелл М. Восстановление и реконструкция изображений. М.: Мир, 1989. 336 с.
2. Бакушинский А. Б., Гончарский А. В. Некорректные задачи. Численные методы и приложения. М.: Изд-во МГУ, 1989. 199 с.
3. Сизиков В. С. Математические методы обработки результатов измерений. СПб: Политехника, 2001. 240 с.
4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2006. 1072 с.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
26 К. А. Кирьянов, В. С. Сизиков
5. Воскобойников Ю. Е. Комбинированный нелинейный алгоритм восстановления контрастных изображений при неточно заданной аппаратной функции // Автометрия. 2007. Т. 43, № 6. С. 3—18.
6. Сизиков В. С., Римских М. В., Мирджамолов Р. К. Реконструкция смазанных и зашумленных изображений без использования граничных условий // Оптич. журн. 2009. Т. 76, № 5. С. 38—46.
7. Сизиков В. С. Прием „усечение—размытие—поворот“ в восстановлении искаженных изображений // Оптич. журн. 2011. Т. 78, № 5. С. 18—26.
8. Кухарев Г. А., Тропченко А. Ю., Шмерко В. П. Систолические процессоры для обработки сигналов. Минск: Беларусь, 1988. 127 с.
9. Кухарев Г. А., Тропченко А. Ю. Систолический процессор для обращения матриц // Изв. вузов. Приборостроение. 1990. Т. 33, № 11. С. 23—27.
10. Тропченко А. Ю. Аппаратные средства для цифровой обработки сигналов. СПб: Изд-во СПбГУ ИТМО, 2005. 138 с.
11. Кирьянов К. А. Инструментальная реализация алгоритмов реконструкции искаженных изображений // Тp. 20-й Междунар. конф. „GraphiCon—2010“. СПб: Изд-во СПбГУ ИТМО, 2010. С. 188—191.
12. Верлань А. Ф., Сизиков В. С. Интегральные уравнения: методы, алгоритмы, программы. Киев: Наук. думка, 1986. 544 с.
13. Поршнев С. В. Вычислительная математика. Курс лекций. СПб: БХВ-Петербург, 2004. 304 с.
14. Киреев В. И., Пантелеев А. В. Численные методы в примерах и задачах. М.: Высш. школа, 2006. 480 с.
15. Рабинер Л., Гоулд В. Теория и применение цифровой обработки сигналов. М.: Мир, 1978. 848 с.
16. Texas Instruments. Digital Signal Processors & ARM Microprocessors [Electronic resource]: .
17. Analog Devices. Embedded processing and DSP [Electronic resource]: .
Константин Александрович Кирьянов Валерий Сергеевич Сизиков
Сведения об авторах — аспирант; Санкт-Петербургский государственный университет
информационных технологий, механики и оптики, кафедра измерительных технологий и компьютерной томографии; E-mail: kiryancon@front.ru — д-р техн. наук, профессор; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра измерительных технологий и компьютерной томографии; E-mail: sizikov2000@mail.ru
Рекомендована кафедрой измерительных технологий и компьютерной томографии
Поступила в редакцию 01.03.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
УДК 004.932:621.397.3:517.983.5
К. А. КИРЬЯНОВ, В. С. СИЗИКОВ
ПРИМЕНЕНИЕ СИГНАЛЬНЫХ МИКРОПРОЦЕССОРОВ В ЗАДАЧАХ РЕКОНСТРУКЦИИ ИСКАЖЕННЫХ ИЗОБРАЖЕНИЙ
Исследуются особенности инструментальной реализации алгоритмов реконструкции искаженных (смазанных, дефокусированных или/и зашумленных) изображений. Рассмотрены прямая задача — моделирование искажения или получение реального искаженного изображения и более сложная и важная для практики обратная задача — реконструкция (восстановление) изображения.
Ключевые слова: искажение изображения, прямая и обратная задачи, сигнальные микропроцессоры, программируемая логическая интегральная схема.
Описание реализуемых алгоритмов. Известная задача реконструкции (восстановле-
ния, реставрации) искаженных (смазанных, дефокусированных или/и зашумленных) изобра-
жений ([1—7] и др.) может быть практически решена не только на универсальных ЭВМ (или
персональных компьютерах), но и на спецпроцессорах ([8—11] и др.). Использование спец-
процессоров ведет, во-первых, к уменьшению габаритов обрабатывающих устройств, а во-
вторых, позволяет превратить недостаточно совершенный прибор наблюдения (фотоаппарат,
телескоп, микроскоп и т.д.) в более совершенный путем подключения к нему спецпроцессора
с заложенным в него алгоритмом обработки.
В работе рассматривается задача инструментальной реализации алгоритмов реконст-
рукции искаженных изображений с помощью сигнальных микропроцессоров и программи-
руемых логических интегральных схем (ПЛИС) [8—11].
Однако прежде чем вести речь о технической реализации алгоритмов, необходимо ска-
зать несколько слов о самих алгоритмах. Основные соотношения и уравнения, описывающие
эти задачи в непрерывном виде, следующие [2—7]:
∞
∫ h(x − ξ) wy (ξ) dξ = g y (x) + δg ,
(1)
−∞
∞∞
∫ ∫ h(x − ξ, y − η) w(ξ, η) dξ dη = g(x, y) + δg ,
(2)
−∞ −∞
где h — функция рассеяния точки (ФРТ), в большинстве случаев пространственно-
инвариантная (или разностная), w и g — распределение интенсивности по неискаженному и
искаженному изображению соответственно, δg — помеха. В соотношении (1) ось x направле-
на вдоль смаза, а y играет роль параметра.
Интегральное уравнение (ИУ) (1), точнее набор одномерных интегральных уравнений,
обычно используется в задаче смазывания, а (2) — в задаче дефокусировки изображения [4, 6, 7].
Для решения интегральных уравнений (1) и (2) наиболее подходит метод регуляризации Ти-
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
Применение сигнальных микропроцессоров в задачах реконструкции искаженных изображений 21
хонова [2—7, 12]. Так как для инструментальной реализации интерес представляют числен-
ные методы, в настоящей работе им и уделено внимание. При численной реализации метода
регуляризации Тихонова для решения обратной задачи обычно используются метод преобра-
зования Фурье (ПФ) и метод квадратур [2, 3, 5—7]. Используются также методы итераций,
например, метод итеративной регуляризации Фридмана [2, 7, 12].
Метод квадратур эффективен при решении набора одномерных ИУ (1) [6, 12, 13], каж-
дое из которых можно записать в операторной форме:
Aw = g + δg ,
(3)
где A — интегральный оператор. Для нахождения функции w необходимо построить такой
оператор A−1 , который давал бы устойчивое приближение к w. Непрерывным уравнениям (1)
можно поставить в соответствие дискретные выражения типа (3). Тогда (3) преобразуется в
систему линейных алгебраических уравнений (СЛАУ), где A — матрица, связанная с ФРТ.
Однако задача решения уравнений (1)—(3) является некорректной [2, 3, 5—7, 12].
В методе регуляризации Тихонова вместо (3) решается уравнение
(αE + AT A) wα = AT g ,
(4)
где α > 0 — параметр регуляризации, E — единичный оператор (единичная матрица). Матри-
ца αE + AT A является квадратной, симметричной и положительно-определенной, СЛАУ (4) имеет решение и численно устойчива [2, 3, 12, 14]. В результате получаем решение в виде:
wα = (αE + AT A)−1 AT g .
(5)
Способы выбора α изложены, например, в [2, 3, 5—7, 12].
Метод регуляризации Тихонова с использованием преобразования Фурье применим для
решения уравнений типа свертки. Рассмотрим частный случай ИУ Фредгольма I рода —
уравнение типа свертки одномерное (1) и двумерное (2). Если ИУ вида (1) при его численном
решении методом квадратур требует размещения в компьютерной памяти матрицы СЛАУ, то
для решения одномерного уравнения типа свертки возможно применять метод ПФ, опери-
рующий лишь с векторами, и это требует меньшего объема памяти и времени решения. Осо-
бенно важен вопрос о памяти и времени при аппаратной реализации метода, в еще большей
степени — для двумерного уравнения (2).
Задача смазывания сводится к решению одномерного ИУ Фредгольма I рода типа сверт-
ки (1) относительно wy (ξ) при каждом фиксированном значении y, играющем роль парамет-
ра. В уравнении (1) ФРТ выражается формулой [2, 3, 6]:
h(x)
=
⎧ ⎨ ⎩
1∆ 0,
,
− ∆ ≤ x ≤ 0, иначе.
(6)
Решение уравнения (1) методом ПФ с регуляризацией Тихонова имеет вид [2, 3, 5—7, 12]:
∫wα y (ξ)
=
1 2π
∞
Wα y (ω) e−i ωξ
−∞
dω,
(7)
где
Wαy (ω)
=
|
H (−ω)Gy (ω) H (ω) |2 + αω2 p
,
(8)
∞∞
∫ ∫H (ω) = h(x) eiωxdx , Gy (ω) = g y (x) eiωxdx , −∞ −∞
где p ≥ 0 — порядок регуляризации.
(9)
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
22 К. А. Кирьянов, В. С. Сизиков
Особенности технической реализации изложенных алгоритмов. Решать задачи, опи-
сываемые уравнениями (1) и (2), на универсальных ЭВМ или ПК возможно в рамках системы
MatLab. Однако такой способ не всегда оптимален по затрачиваемому на решение времени.
Существуют ситуации, когда на выполнение задачи отводится очень мало времени и
нужно выполнить обработку изображения в режиме реального времени. Такие ситуации воз-
никают, когда, например, необходимо распознать самолет, нарушитель территориальных
границ, и восстановить опознавательные знаки на нем. При этом самолет может лететь на-
столько быстро, что получаемое изображение смазывается. У оператора очень мало времени,
чтобы распознать характеристики самолета и принять решение. Задача намного усложняется,
если помимо смазывания изображения самолет находится не в фокусе, а поскольку процесс
быстротекущий, то устройства автофокусировки отработать не успевают ни на одном из по-
лученных кадров.
Очевидно, что для решения таких задач требуемая производительность должна быть
выше, чем у современных ПЭВМ. Одним из важнейших требований к техническим средствам
является обеспечение режима обработки сигналов в реальном времени (со скоростью их по-
ступления) при приемлемых стоимостных и массогабаритных характеристиках системы. Так,
некоторые технические задачи цифровой обработки изображений требуют быстродействия аппаратных средств порядка 109—1010 операций в секунду для обеспечения обработки в ре-
альном времени.
Другой особенностью подобных задач является необходимость обработки больших
объемов (от 1 МБ и более) сложноструктурированных многомерных данных, что вносит до-
полнительные трудности в организацию вычислений и требования к правильному распреде-
лению памяти в ходе решения задачи.
Особенности при реализации на цифровом сигнальном процессоре. Как уже сказано,
существуют два метода решения интегрального уравнения (1), описывающего задачу смазы-
вания:
1) общий случай — решение методом квадратур с регуляризацией Тихонова;
2) частный случай, характерный для уравнений типа свертки — метод ПФ с регуляриза-
цией Тихонова.
Несколько слов о первом методе. Для восстановления изображения нужно знать
искажающее воздействие (ФРТ) h(x, ξ) в общем случае, когда ФРТ не является пространст-
венно-инвариантной (разностной), или h(x − ξ) в случае, когда ФРТ является пространствен-
но-инвариантной. При замене в уравнении (1) интеграла конечной суммой получаем СЛАУ
(3), где по ФРТ можно найти матрицу A как матричный оператор искажающего воздействия,
согласно соотношению
⎡ h(c, a)
h(c, a + hξ ) ... h(c,b) ⎤
h(x, ξ)
→
A
=
⎢⎢h(c ⎢ ⎢
+ hx ...
, a)
h(c + hx , a + hξ ) ...
... ...
h(c
+ hx ...
,
b)
⎥ ⎥ ⎥ ⎥
,
⎣⎢ h(d, a)
h(d, a + hξ ) ... h(d ,b) ⎦⎥
(10)
где hx и hξ — шаги дискретизации по x и по ξ соответственно. Затем эта матрица транспони-
руется и вычисляется матрица αE + AT A , из которой с помощью метода Гаусса—Жордана
[13, 14] получаем обратную, которая хранится в памяти устройства до завершения восстанов-
ления изображения, после чего находится решение, согласно (5). Также решение уравнения
(4) можно получить с помощью метода LU-разложения или методом квадратных корней
Краута—Холецкого [12].
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
Применение сигнальных микропроцессоров в задачах реконструкции искаженных изображений 23
Для решения по методу ПФ с регуляризацией Тихонова, как и в предыдущем случае, требуется знать искажающее воздействие и, как уже говорилось, этот метод может быть применен только для пространственно-инвариантной ФРТ. Важно правильно и грамотно распределять память сигнальных микропроцессоров. Для этих целей обычно применяется алгоритм быстрого преобразования Фурье (БПФ) [10, 15, 16]. При использовании БПФ не только сокращается время выполнения всей процедуры (за счет исключения повторяющихся операций), но и происходит экономия памяти.
Для вычисления обычного дискретного ПФ нужны 4 массива: два для действительной и мнимой частей исходного процесса (оригинала изображения) и два — для вычисленного фурье-образа (фурье-спектра изображения). При использовании БПФ можно обойтись двумя массивами, потому что процесс вычисления БПФ итерационный. Число отсчетов N должно
быть целой степенью числа 2, тогда количество итераций будет равно log2 N , а выполнение
самой процедуры возможно с использованием той же области памяти, в которой находились исходные данные. Таким образом, для решения по этому методу с использованием алгоритма БПФ вычисляется фурье-спектр исходного процесса (каждой строки изображения), затем ФРТ, которая в большинстве случаев короче самого изображения и которую нужно дополнить до N нулями, после чего поточечно вычисляется соотношение (8), называемое регуляризованным спектром. И, наконец, от полученного массива, длина которого тоже является целой степенью числа 2, вычисляется обратное ПФ, при котором также используется алгоритм БПФ.
При восстановлении дефокусированных изображений, описываемых уравнением (2), нельзя применить метод квадратур (кубатур) из-за необходимости обращения трехмерной матрицы, что практически невозможно из-за требуемого чрезвычайно большого объема памяти для решения такой задачи. Если нет аберраций линзы и объектив не является широкоугольным, то можно считать ФРТ пространственно-инвариантной. Таким образом, задача описывается двумерным уравнением типа свертки (2), которое можно решать с помощью ПФ. Здесь решение находится также с применением алгоритма двумерного БПФ и данную задачу иначе решить крайне сложно, так как используются двумерные массивы, а у специализированных процессоров довольно мал объем оперативной памяти, в который нужно уложиться.
При решении ИУ методом ПФ для уменьшения эффекта Гиббса можно использовать размытие краев [6, 7] (рис. 1). Для случая, когда ФРТ не является пространственноинвариантной, решение ИУ (2) можно осуществить итерационными методами, такими как метод итеративной регуляризации Фридмана, метод Ландвебера и др. [2, 12].
h(x, y) (ФРТ)
∆
g(x, y)
g(x, y) с размытыми
границами
h(x, y) (ФРТ)
∆
∆∆
Рис. 1
Из всей номенклатуры предложенной элементной базы фирмы Texas Instruments (TI) [16] наиболее подходящими для решения перечисленных задач являются микропроцессоры семейства TMS320C64++, устройства с фиксированной запятой, разработанные специально для математической обработки изображений. Из их числа самыми подходящими являются процессоры C6455 и C6457. Структурная схема такого устройства отображена на рис. 2.
Ядро процессора состоит из восьми вычислительных узлов, двух файлов регистров общего назначения, двух шин данных. Каждый из файлов регистров (A и B) содержит по тридцать два 32-разрядных регистра. Действия можно выполнять с 8-, 16-, 32-, 40- и
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
24 К. А. Кирьянов, В. С. Сизиков
64-разрядными данными. При разрядности данных более 32 бит они сохраняются в парах регистров. Восемь функциональных вычислительных узлов (M1, L1, D1, S1, M2, L2, D2, и S2) способны выполнять по одной инструкции за каждый машинный такт (M — умножители, S и L выполняют арифметико-логические и сдвиговые операции, D обеспечивают обмен данными между памятью и регистровым файлом). При операции комплексного умножения используются четыре 16-разрядных операнда (по два действительных и два мнимых), получаемый результат — 32 бита действительная часть и такая же мнимая. Также возможно выполнять комплексные умножения с округлением, в результате чего 32-разрядный результат содержит действительную и мнимую части, на каждую из которых отводится по 16 разрядов (см. рис. 2). В некоторых случаях это весьма удобно для вычисления ПФ.
32 бита Re yα
32 бита Im yα
Считывание команд Декодирование команд
Регистры состояния Буфер команд
Внутрисхемная эмуляция
L2 S2 M2 D2
L1 S1 M1 D1
16 бит Re yα
16 бит Im yα
Регистровый файл В
Регистровый файл А
Рис. 2
Реализация всех алгоритмов для процессоров TI выполняется на языке C++ в специальной среде Code Composer v.4.0, поставляемой с отладочным модулем. Несколько реже применяются микропроцессоры другой фирмы, Analog Devices [17], для работы с которыми производителем поставляется программная среда VisualDSP++, программы выполняются тоже на С++. При этом программы, разработанные в среде MatLab, требуют выполнения двойной компиляции, что не является оптимальным по быстродействию и распределению памяти.
Особенности реализации метода на основе ПЛИС. Производительность даже специализированного процессора всегда меньше, чем производительность специализированного аппаратного блока, например, реализованного на основе программируемой логической интегральной схемы. Подход состоит в том, что для того или иного вида обработки изображений на базе ПЛИС реализуется конечный автомат, способный выполнять только одну функцию. При этом достигается максимально возможная производительность, которая определяется используемой разработчиком и производителем ПЛИС технологией изготовления (ALTERA, XILINX), но гибкость решения присутствует лишь в той мере, в которой ее предусмотрел разработчик.
Для реконструкции изображений при решении задачи методом квадратур необходимо
правильно сформировать матрицу A, произвести ее транспонирование AT , получить уравнение Тихонова (4), перемножив при этом транспонированную матрицу на исходную и на правую часть уравнения g, и решить уравнение Тихонова, которое может быть решено методом Гаусса—Жордана; схема такого устройства предложена в работе [8]. Сложность состоит только в том, что размерность матрицы нельзя сделать выше определенной величины, которая закладывается при разработке. Структурная схема такого устройства приведена на рис. 3 (здесь K — коммутатор).
Точно так же можно получить решение и для метода регуляризации Тихонова с ПФ для данной задачи — с помощью многоканальной систолической матрицы, систолического процессора БПФ, особенности реализации которых описаны в работе [8]. Производители FPGA
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
Применение сигнальных микропроцессоров в задачах реконструкции искаженных изображений 25
XILINX поставляют готовые программные конфигурации ПЛИС с реализацией различных
видов ПФ. Структурная схема таких устройств для решения задачи (1) приведена на рис. 4
(здесь ОБФП — обратное быстрое преобразование Фурье).
w(ξ) Прямая задача gy(x) Обратная задача
× gy(x) w(ξ)
Прямая задача
K
h(x, ξ)
A
K
Обратная задача
AT×A+αE
Обращение
матрицы
Рис. 3
gy(x) h(x)
БПФ Gy(ω)
БПФ
Н(–ω) Н(ω)
Н(–ω)Gy(ω) |Н(ω)|2+αω2p
|Н(ω)|2 ×
wy(ξ) ОБПФ
Рис. 4
На практике подход к разработке перечисленных устройств выбирается в зависимости от сложности алгоритма обработки и требований по временным параметрам. Довольно часто выбирают комбинированный подход, при котором используются как ПЛИС с реализованными функциями, требующими наибольшего быстродействия и не требующими большой гибкости, так и цифровой сигнальный процессор для реализации той части, где он будет справляться с алгоритмом по быстродействию, но где нужен более гибкий подход к решению.
Выводы. В работе используются в виде инструментальной реализации следующие приемы обработки изображений: „усечение“, „размытие краев“ и „поворот“ при использовании известных методов решения интегральных уравнений — преобразования Фурье или квадратур с регуляризацией Тихонова [6, 7]. Прием усечения используется для того, чтобы избежать так называемых „граничных условий“ [4]. Прием размытия краев используется для уменьшения эффекта Гиббса (эффекта ложных волн на изображении). Прием поворот используется для решения задачи смазывания при произвольном угле.
Указанные методы восстановления изображений могут применяться в таких областях, как томография (возникновение смазывания из-за случайных движений пациента во время обследования), восстановление старых фотографий, обнаружение самолетов-нарушителей территориальных границ и т.п. При этом необходима реализация методик на современной элементной базе, специализированной для обработки сигналов и адаптированной для быстрых алгоритмов.
Работа выполнена при поддержке РФФИ (грант № 09-08-00034а).
СПИСОК ЛИТЕРАТУРЫ
1. Бейтс Р., Мак-Доннелл М. Восстановление и реконструкция изображений. М.: Мир, 1989. 336 с.
2. Бакушинский А. Б., Гончарский А. В. Некорректные задачи. Численные методы и приложения. М.: Изд-во МГУ, 1989. 199 с.
3. Сизиков В. С. Математические методы обработки результатов измерений. СПб: Политехника, 2001. 240 с.
4. Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2006. 1072 с.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7
26 К. А. Кирьянов, В. С. Сизиков
5. Воскобойников Ю. Е. Комбинированный нелинейный алгоритм восстановления контрастных изображений при неточно заданной аппаратной функции // Автометрия. 2007. Т. 43, № 6. С. 3—18.
6. Сизиков В. С., Римских М. В., Мирджамолов Р. К. Реконструкция смазанных и зашумленных изображений без использования граничных условий // Оптич. журн. 2009. Т. 76, № 5. С. 38—46.
7. Сизиков В. С. Прием „усечение—размытие—поворот“ в восстановлении искаженных изображений // Оптич. журн. 2011. Т. 78, № 5. С. 18—26.
8. Кухарев Г. А., Тропченко А. Ю., Шмерко В. П. Систолические процессоры для обработки сигналов. Минск: Беларусь, 1988. 127 с.
9. Кухарев Г. А., Тропченко А. Ю. Систолический процессор для обращения матриц // Изв. вузов. Приборостроение. 1990. Т. 33, № 11. С. 23—27.
10. Тропченко А. Ю. Аппаратные средства для цифровой обработки сигналов. СПб: Изд-во СПбГУ ИТМО, 2005. 138 с.
11. Кирьянов К. А. Инструментальная реализация алгоритмов реконструкции искаженных изображений // Тp. 20-й Междунар. конф. „GraphiCon—2010“. СПб: Изд-во СПбГУ ИТМО, 2010. С. 188—191.
12. Верлань А. Ф., Сизиков В. С. Интегральные уравнения: методы, алгоритмы, программы. Киев: Наук. думка, 1986. 544 с.
13. Поршнев С. В. Вычислительная математика. Курс лекций. СПб: БХВ-Петербург, 2004. 304 с.
14. Киреев В. И., Пантелеев А. В. Численные методы в примерах и задачах. М.: Высш. школа, 2006. 480 с.
15. Рабинер Л., Гоулд В. Теория и применение цифровой обработки сигналов. М.: Мир, 1978. 848 с.
16. Texas Instruments. Digital Signal Processors & ARM Microprocessors [Electronic resource]: .
17. Analog Devices. Embedded processing and DSP [Electronic resource]: .
Константин Александрович Кирьянов Валерий Сергеевич Сизиков
Сведения об авторах — аспирант; Санкт-Петербургский государственный университет
информационных технологий, механики и оптики, кафедра измерительных технологий и компьютерной томографии; E-mail: kiryancon@front.ru — д-р техн. наук, профессор; Санкт-Петербургский государственный университет информационных технологий, механики и оптики, кафедра измерительных технологий и компьютерной томографии; E-mail: sizikov2000@mail.ru
Рекомендована кафедрой измерительных технологий и компьютерной томографии
Поступила в редакцию 01.03.11 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2011. Т. 54, № 7