misle.ru страница 1
скачать файл


Учреждение образования

«БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАТИКИ И РАДИОЭЛЕКТРОННИКИ»

Конкурс научных работ студентов Республики Беларусь

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

в задачах цифровой обработки изображений

Автор: Павлёнок Наталья Александровна

Группа 250502 , курс 4

Факультет компьютерных систем и сетей
Научный руководитель: Садыхов Рауф Хосровович

доктор технических наук, профессор

кафедра ЭВМ

Минск 2006



Содержание
Введение 3

1. Линейное преобразование адона 4

2. Дискретное преобразование Радона. 7

3. Нормальное преобразование Радона. 10

4. Связь преобразования Радона с преобразованием Фурье. 11

5. Примеры. 12

6. Преобразование Хафа. 14

7. Локальное веерное преобразование Радона. 16

8. Фигурное контурное преобразование. 18

Заключение 19

Литература 20

Введение
В 1917 году математик И. Радон [1] предложил метод восстановления (реконструкции) многомерных функций по их интегральным характеристикам, т.е. метод решения обратной задачи интегральной геометрии.

Широкое применение нашёл этот метод в компьютерной томографии [2]:

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

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


Общие сведения о преобразовании Радона, его свойства и возможности реализации приведены в [2].

1. Линейное преобразование Радона
Преобразование Радона R (k,b) непрерывной функции f (x,y) вычисляется путём интегрирования (сложения) значений f вдоль наклонной линии, как показано на рисунке 1:


Рисунок 1. Линейное преобразование Радона


Можно записать:


(1)
Или при помощи δ-функции Дирака:




(2)
Необходимо отметить, что преобразование (1) или (k,b)-преобразование обладает некоторыми свойствами, очень важными для работы с изображениями, такими как свойство линейности (3), сдвига (4), масштабирования (5).

Свойство линейности можно сформулировать следующим образом: «Преобразование Радона взвешенной суммы функций равно взвешенной сумме преобразований каждой функции»:

(3)


Свойства (4) и (5) (сдвиг и масштабирование) показывают, как вычисляется (k,b)-преобразование при изменении аргументов интегрируемой функции.
(4)


(5)
Рассмотрим несколько элементарных примеров:


Любую точку можно представить в виде произведения 2-х δ-функций:

(6)

Тогда её преобразование Радона будет иметь вид:




(7)
Пользуясь свойством сдвига, получим:




(8)
Преобразование Радона в этом случае:




(9)
Таким образом, преобразование Радона точки имеет вид прямой (рисунок 2).



Рисунок 2. Преобразование отдельной точки.

Стоит отметить этот вывод, поскольку любая функция может быть представлена в виде взвешенной суммы (интеграла) множества точек.
Соответственно, для прямой линии, заданной уравнением y=kx+b получим:


(10)
Преобразование Радона в этом случае:




(11)

Рисунок 3 . Преобразование прямой линии.

2. Дискретное преобразование Радона.
Для вычисления на ЭВМ необходимо провести дискретизацию. Самый простой способ – линейная выборка значений х и у:


(12)


Тогда преобразование Радона аппроксимируется простым суммированием:

(13)
Поскольку y – целое число, возникает проблема интерполяции значений y:




(14)
Два самых простых подхода – интерполяция ближайшего соседства и линейная интерполяция:


Реализация алгоритма:


  • Переменной х назначаются дискретные значения из рассматриваемого интервала. Затем вычисляется соответствующее значение переменной у.

  • В случае интерполяции ближайшего соседства значение y округляется до ближайшего целого. Вычислительная сложность алгоритма в этом случае будет порядка 0(Т,Н,М). где Т, Н и М количество отсчётов k, x и b соответственно. Также будет иметь место погрешность округления (см. рисунок 4).

  • При линейной интерполяции между двумя соседними отсчётами функции погрешность вычислений будет меньше при той же вычислительной сложности алгоритма (см. рисунок 5).



Рисунок 4. Вычисление преобразования Радона прямой

с интерполяцией ближайшего соседства.




Рисунок 5. Вычисление преобразования Радона прямой

с линейной интерполяцией.


Далее приводятся тексты соответствующих функций для MatLab

//Интерполяция ближайшего соседства

P = tan(-pi*89/180:pi/180:pi*89/180);

R = length(P);

TAU = -N/2:N/2;

T = length(TAU);

result = zeros(T, R);

for th = 1:T

for p = 1:R

for x = -T:T

y = x*P(p) + TAU(th);

yy = T-round(y);

xx = T+x;

if (xx>0) && (xx<=N) && (yy>0) && (yy<=N)

result(th, p) = result(th, p) + IMG(xx, yy);

end


end

end


end
//Линейная интерполяция

TAU = -N/2:N/2;

T = length(TAU);

P = tan(-pi*89/180:pi/180:pi*89/180);

R = length(P);

result = zeros(T, R);

for p = 1:R

for th = 1:T

for x = -T:T

xx = T+x;

y = x*P(p) + TAU(th);

y1 = floor(y);

w = y - y1;

yy1 = T - y1;

yy2 = T - (y1+1);

if (xx>0) && (xx<=N) && (yy2>0) && (yy1<=N)

result(th, p) = result(th, p) + IMG(xx, yy1)*(1-w) + IMG(xx, yy2)*w;

end


end

end


end

3. Нормальное преобразование Радона.
Нормальное уравнение прямой (рисунок 6) имеет вид:

(15)

Рисунок 6. Нормальное уравнение прямой.


Аналогичным образом, преобразование Радона можно вычислить по формуле:
(16)
Простейшие случаи – преобразование точки и прямой линии (17) и (18)


(17)

Рисунок 7. Нормальное преобразование точки


(18)


4. Связь с преобразованием Фурье.
Одномерное преобразование Фурье по переменной s от преобразования Радона функции f даёт двумерное преобразование Фурье функции f.

(19)

Поскольку двумерное преобразование Фурье обратимо, то обратимо и преобразование Радона (20).


(20)

где:



Выражение (20) есть формула обращения преобразования Радона.

К сожалению, преобразование Радона обратимо не для каждой функции.




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

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

Необходимо также отметить, что нормальное преобразование Радона подходит для выявления прямых любой ориентации, что невозможно при линейном преобразовании (прямые, параллельные оси У).


Рассмотрим зашумлённое изображение:



Рисунок 9. Работа с зашумлённым и незашумлённым изображением
Итак, как показано на рис. 9 (нижний ряд), преобразование Радона практически с одинаковой точностью позволяет определить расположение прямых на зашумлённых и незашумлённых изображениях. Это свойство преобразования в значительной степени расширяет область его применения. Например, можно применять преобразование для анализа зашумлённых полутоновых изображений интегральных микросхем [4].


6. Преобразование Хафа.
При анализе монохромного изображения при использовании преобразования Радона, как описано ранее, исходное изображение отображается в некоторое пространство признаков (так для (k,b) – преобразования это пространство параметров прямой k и b, а для нормального – ρ и θ соответственно). Затем по виду результирующего изображения можно судить о наличии на исходном изображении определённых объектов, их формы и т.д. Как отмечалось ранее, при реализации такого преобразования появляются определённые сложности, связанные с необходимостью “подгонять” значения аргументов под рассматриваемые параметры. Такой необходимости не будет, если анализировать не исходное изображение, а результирующее пространство. Каждой точке его можно поставить в соответствие счётчик, и затем, анализируя результаты аналогичного преобразования наращивать счётчики. Таким образом, анализируя счётчик каждой точки результирующего пространства, представляющей собой ни что иное, как представление фигуры интереса (искомой фигуры, кривой и т.д.), можно судить о наличие фигур с задаваемыми параметрами.

Такое преобразование называется преобразованием Хафа. Его идея состоит в выявлении кривых заданных определёнными параметрами:


(21)
Пространство, содержащее результирующее изображение называют фазовым. Его образуют параметры семейства кривых а12,...an, задаваемого формулой (19).

Алгоритм поиска заданных прямых очень прост и состоит лишь в вычислении значений счётчиков фазового пространства, а затем, в поиске наибольших их значений.


Существует несколько модификаций вычисления преобразования Хафа.

  • Случайное преобразование – заключается в анализе случайным образом выбранных точек.

  • Иерархическое преобразование – исходное изображение делиться на небольшие квадраты, анализируется, затем квадраты группируются по 4 в большие квадраты и т.д.

  • «Размытие» фазового пространства – в случае зашумлённых изображений, для увеличения точности наращиваются счётчики не только рассматриваемой точки фазового пространства, но и прилежащие ей счётчики близлежащих кривых.

  • Использование градиента яркости – рассматриваются только кривые перпендикулярные градиенту яркости изображения в данной точке, если оно получено операторами выделения краёв.

Преобразование Хафа может применяться там, где необходимо анализировать формы кривых. Это всевозможные системы распознавания образов, таких как рукописный шрифт, анализ изображений микросхем, аэрокосмических снимков а также системы слежения (рис. 10).



Пусть х – одномерная последовательность, полученная после предварительной обработки видео изображения. Значение n определяет номер кадра. Траектория движения точки p – некоторая кривая.

Если движение точки равномерно, то кривая есть прямая линия, задаваемая уравнением:


(22)
Таким образом, пространственно-временное преобразование, описанное в [5], построенное на основании принципов преобразования Хафа было применено в системе слежения.


7. Локальное веерное преобразование Радона.

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



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

Для выделения центров сетчатых структур может быть использовано веерное преобразование Радона [6].


В данном случае применяется классическое преобразование Радона для двумерного случая, только интеграл берётся не по прямой, а по лучу или по отрезку, как показано на рисунке 12.
.
Рисунок 12. Преобразование Радона (интеграл по прямой),

веерное преобразование Радона (интеграл по лучу)

и локальное веерное преобразование Радона (интеграл по отрезку).
При фиксировании точки (x,y) (центра структуры) и радиуса локальной области в результате преобразования получится функция от одной переменной (угла θ) – радиальная развёртка изображения, имеющая локальные минимумы для направлений, соответствующих ветвям.

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

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

8. Фигурное контурное преобразование (Shape Trace Transform) и обработка изображения лица человека.
Преобразование, описанное в [7], представляется авторами как один из вариантов преобразования Радона. Метод фигурного контурного преобразования применим в задачах распознавания лиц (Face Recognition).
Последовательность действий при работе с изображением лица следующая:


  • В качестве исходного изображения принимается нормализованное и ограниченное изображение лица (пример на рисунке 13).

  • Проводится его нормальное преобразование Радона.

  • В полученном цветном изображении выделяются области наибольшей интенсивности.

  • Области нормализуются и в качестве образца для анализа используются контуры области.



Рисунок 13. Фигурное контурное преобразование.

Образцы, полученные посредством STT, могут сравниваться друг с другом, например, посредством вычисления расстояния Хаусдорффа. В качестве классификатора в [7] предлагается использовать нейронную сеть, на базе квазилинейных модулей Бернулли.


Модификация STT – взвешенное фигурное преобразование, годится для работы с изображениями, повёрнутыми на некоторый угол, с искажающими деталями (мимика, детали внешности – очки, причёски, усы и т.д.)
Заключение
Наиболее широкую область применения, как это отмечалось в самом начале, преобразование Радона нашло в компьютерной томографии. В задачах цифровой обработки изображений наиболее широко применяется преобразование Хафа. В среде MatLab (Image Processing Toolbox) реализованы оба преобразования (в том числе и обратное преобразование Радона) .

В ходе выполнения данной работы, была разработана инструментальная среда, в которой помимо преобразований Хафа и Радона (с различными типами интерполяции), реализованы дискретное веерное и фигурное контурное преобразования. Среда имеет пользовательский интерфейс, позволяющий варьировать параметры преобразований, сравнивать время их вычислений.

Планируется также модуль, реализующий фигурное контурное преобразование, ввести в состав системы обработки лица человека Face Processing, разрабатываемую на кафедре ЭВМ БГУИР.

Литература
[1]. J. Radon.Über die Bestimmung von Funktionen durch ihre Integralwerte längs

gewisser Mannigfaltigkeiten. Berichte Sächsische Akademie der Wissenschaften,

Leipzig, Mathematisch-Physikalische Klasse, 69:262–277, 1917.

[2]. И.С. Грузман. Математические задачи компьютерной томографии.Соросовский образовательный журнал, том 7, №5. 2001.

[3]. P. Toft. The Radon Transdorm: Theory and Implementation.Ph. D. Thesis, Department of Matematical Modelling Section for Digital Signal Processing, Technical University of Danemark, 1996

[4]. Система цифровой обработки изображений слоев интегральных микросхем /Вершок Д.А., Дудкин А.А., Калюта А.Г. и др. // Идентификация образов: Сб. науч. тр.– Минск: Ин-т техн. кибернетики НАН Беларуси.– 2001.– С. 71-87.

[5]. Koichi Sato, J.K. Aggarwal. Temporal spatio-velocity transform and its application to tracking and interaction. Computer and Vision Research Center, Department of Electrical and Computer Engineering,The University of Texas at Austin, Austin, TX 78712, USA

[6]. Дискретное веерное преобразование Радона в задаче выделения центров ветвей сетчатых структур. В.Г. Баранов, А.Г. Храмов. Институт систем обработки изображений РАН Самарский государственный аэрокосмический университет



[7]. A. Kadyrov and M. Petrou, “The Trace Transform and Its Applications,” IEEE Trans. PAMI, Vol. 23(8), pp. 811-828, 2001.


скачать файл


Смотрите также: