Портал | Содержание | О нас | Авторам | Новости | Первая десятка | Дискуссионный клуб | Чат Научный форум --> Первая десятка "Русского переплета" Темы дня:

Президенту Путину о создании Института Истории Русского Народа. |Нас посетило 40 млн. человек | Чем занимались русские 4000 лет назад?

| Кому давать гранты или сколько в России молодых ученых?

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

Часть 1. Математические модели

В. А. СОЙФЕР

Самарский государственный аэрокосмический университет

ВВЕДЕНИЕ

Недаром говорят: "Лучше один раз увидеть, чем сто раз услышать". Исследования подтверждают, что информационная пропускная способность органов зрения значительно выше, чем у других каналов передачи информации, доступных человеку. В теории информации доказано, что, подбрасывая монету и наблюдая результат, мы всякий раз получаем одну двоичную единицу (бит) информации. Каждая буква в тексте несет примерно четыре бита информации. Изображение участка поверхности Земли, полученное из космоса, содержит примерно 10 миллионов бит информации! Переработать такое количество информации под силу только самому современному компьютеру. Чтобы научить машину обрабатывать изображения, требуется иметь мощный комплекс технических средств, математический аппарат, алгоритмы и большое количество программ.

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

1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ОПТИЧЕСКИХ ИЗОБРАЖЕНИЙ

1.1. Функция яркости

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

Рассмотрим объект, освещенный источником света (рис. 1). На некотором расстоянии от объекта распределение энергии источника светового излучения, отраженного объектом, по пространственным координатам x, y и по длинам волн l описывается функцией с(x, y, l). Эта функция является неотрицательной; ее максимальное значение в изображающих системах ограничено предельной величиной светочувствительности регистрирующих сред,

0 # с(x, y, l) # A,

где A - максимальная яркость изображения.

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

- Lx # x # Lx , - Ly # y # Ly .

Человеческое зрение и видеодатчики обладают спектральной чувствительностью, описываемой функцией u(l). Например, как известно, человеческий глаз обладает чувствительностью к свету в диапазоне волн от lmin = 0,35 мкм до lmax = 0,78 мкм. При этом функция спектральной чувствительности достигает своего максимума приблизительно в середине этого диапазона и спадает к его краям.

Каждый видеодатчик обладает индивидуальной характеристикой спектральной чувствительности, обусловленной физикой прибора. Имеются видеодатчики ультрафиолетового и инфракрасного диапазонов, которые широко используются, например, при проведении спектрозональных съемок Земли из космоса.

Как в случае наблюдения объекта человеком, так и в случае использования видеодатчика наблюдаемое изображение является результатом усреднения функции с(x, y, l) по диапазону длин волн с весовой функцией u(l) и описывается выражением

Функцию f(x, y) в дальнейшем будем называть изображением. Таким образом, изображение - это ограниченная функция двух пространственных переменных, заданная на ограниченной прямоугольной области.

1.2. Двумерные линейные системы

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

С математической точки зрения под системой будем понимать правило L, ставящее в соответствие входной функции f выходную функцию g. Различают одномерные 1D и двумерные 2D системы. Одномерные системы преобразуют функции одной переменной:

g(x) = L[f(x)].

Соответственно двумерные системы преобразуют функции двух переменных:

g(x, y) = L[f(x, y)].

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

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

L[a1 f1(x, y) + a2 f2(x, y)] = a1L[f(x, y)] + a2L[f2(x, y)].

Принцип суперпозиций можно выразить в более общем виде, рассматривая произвольное число M входных воздействий:

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

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

Согласно выражению (9) дельта-функция может рассматриваться как бесконечно узкая колоколообразная функция (рис. 2).

Можно также ввести дельта-функцию, расположенную не в начале координат, а в произвольной точке с координатами (u, u), по формуле

Дельта-функция обладает следующими важными свойствами:

1) Свойство нормировки:

Физически это означает, что, хотя плотность яркости точечного источника бесконечна, энергия его ограничена и равна единице.

2) Фильтрующее свойство

где f(x, y) - произвольная функция двух переменных. Интегралы в (11) и (12) берутся по бесконечно большой пространственной области D. Доказательства свойств 1) и 2) выполняются с помощью подстановки в (11) и (12) выражения (9) и раскрытия предела.

Рассмотрим 2D-линейную систему, на вход которой подан сигнал в виде дельта-функции. Реакция системы на дельта-функцию будет различной для различных систем, называется импульсным откликом и служит характеристикой 2D-системы. Систему называют пространственно-инвариантной, если ее импульсный отклик зависит от разности координат входной (x, y) и выходной (x, h) плоскостей. Для оптической системы, показанной на рис. 3, это означает, что при перемещении точечного источника во входной (предметной) области изображение этого предмета в плоскости наблюдения будет также изменять положение, но сохранять форму.

Для пространственно-инвариантных систем импульсный отклик описывается функцией

h(x - u, y - u) ╞ h(x, h),

где x = x - u, h = y - Яu,

h(x, h) ╞ L[d(x, y)].

Используя функцию импульсного отклика, можно записать уравнение, связывающее изображения на входе и выходе 2D-линейной оптической системы. Для этого представим входной сигнал f(x, y) в виде (12) и подадим его на вход 2D-системы с характеристикой h(x, h). Выходной сигнал запишем в виде

Поскольку операция L линейна и операция интегрирования в фигурных скобках (15) также линейна, их можно поменять местами и записать

Учитывая, что по определению

L{d(x - x, y - h)} ╞ h(x - x, y - h),

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

Уравнение (16) называется интегралом свертки. Из этого уравнения следует, что, зная импульсный отклик оптической системы h(x, h), можно рассчитать выходное изображение по входному.

Процесс свертки иллюстрирует рис. 4. На рис. 4а и 4б изображены функция f(x, y) на входе и импульсный отклик. На рис. 4а показан импульсный отклик при обращении координат, а на рис. 4г - со сдвигом на величину х, у. На рис. 4д заштрихована область, в которой произведение f(x, h) h(x - x, y - h), входящее в подынтегральное выражение (16), не равно нулю. Интегрирование по этой области дает величину g(х, у) для заданных значений координат х, у. Таким образом, функция g(х, у) на выходе может быть найдена сканированием входной функции скользящим "окном" - обращенным импульсным откликом, и интегрированием по области, в которой эти функции перекрываются.

1.3. Средства ввода изображений

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

Ввод изображений в память компьютера осуществляется с помощью видеодатчиков. Видеодатчик переводит оптическое распределение яркости изображения в электрические сигналы и далее в цифровые коды. Поскольку изображение является функцией двух пространственных переменных, а электрический сигнал является функцией одной переменной - времени, то для преобразования используется развертка. Например, при использовании телевизионной камеры изображение считывается по строкам: строка за строкой. При этом в пределах каждой строки зависимость яркости от пространственной координаты x преобразуется в пропорциональную зависимость амплитуды электрического сигнала от времени t. Переход от конца предыдущей строки к началу следующей осуществляется практически мгновенно. Широкое применение в качестве видеодатчиков находят также матрицы фотодиодов и матрицы приборов с зарядовой связью. При использовании матричных видеодатчиков изображение как бы наблюдается сквозь экран с множеством прозрачных ячеек. Число таких ячеек для современных видеодатчиков весьма велико и составляет величину 1024 i 1024 и более (см. рис. 5).

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

2. ДИСКРЕТНЫЕ ПРЕДСТАВЛЕНИЯ ИЗОБРАЖЕНИЙ

2.1. Дискретизация изображений

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

Введем понятие шага дискретизации T1 по пространственной переменной х и Т2 по переменной у. Например, можно представить, что в точках, удаленных друг от друга на расстояние Т1 по оси х, расположены точечные видеодатчики. Если такие видеодатчики установить по всей прямоугольной области, то изображение окажется заданным на двумерной решетке:

Для сокращения записи обозначим

f (n1T1 , n2T2) ╞ f (n1 , n2).

Функция f(n1 , n2) является функцией двух дискретных переменных и называется двумерной последовательностью. То есть дискретизация изображения по пространственным переменным переводит его в таблицу выборочных значений. Размерность таблицы (число строк и столбцов) определяется геометрическими размерами исходной прямоугольной области и выбором шага дискретизации по формуле

где [ " ] обозначает целую часть числа.

Если область определения непрерывного изображения - квадрат Lx = Ly = L и шаг дискретизации выбран одинаковым по осям х и у (Т1 = Т2 = Т ), то

Mx = My = M

и размерность таблицы составляет М 2.

Элемент таблицы, полученной путем дискретизации изображения, называют пиксел. Рассмотрим пиксел f (n1 , n2). Это число принимает непрерывные значения.

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

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

В практических задачах обработки изображений величина K варьируется в широких пределах от К = 2 ("бинарные" (черно-белые) изображения) до K = 210 и более (практически непрерывные значения яркости). Наиболее часто выбираются К = 28, при этом пиксел изображения кодируется одним байтом информации. Из всего вышеуказанного делаем вывод, что пикселы, хранящиеся в памяти компьютера, представляют собой результат дискретизации исходного непрерывного изображения по аргументам и по уровням. Ясно, что шаги дискретизации Т1 ,Т2 и D должны выбираться достаточно малыми, для того чтобы погрешность дискретизации была незначительна и цифровое представление сохраняло основную информацию об изображении.

При этом следует помнить, что чем меньше шаг дискретизации и квантования, тем больший объем данных об изображении должен быть записан в память компьютера. Рассмотрим в качестве иллюстрации этого утверждения изображение на слайде размером 50 i 50 мм, которое вводится в память с помощью цифрового измерителя оптической плотности (микроденситометра). Если при вводе линейное разрешение микроденситометра (шаг дискретизации по пространственным переменным) составляет 100 мкм, то в память записывается двумерный массив пикселов размерности М 2 = 500 i 500 = 25 i 104. Если же шаг уменьшить до 25 мкм, то размеры массива возрастут в 16 раз и составят М 2 = 2000 i 2000 = = 4 i 106. Используя квантование по 256 уровням, то есть кодируя найденный пиксел байтом, получаем, что в первом случае для записи необходим объем 0,25 мегабайт памяти, а во втором случае - 4 мегабайта.

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

2.2. 2D-последовательности

Рассмотрим несколько практически важных 2D-последовательностей, имеющих аналитическое выражение.

1) Цифровой единичный импульс

Нетрудно заметить, что эта последовательность подобна дельта-функции (8). Произвольная последовательность F(n1 , n2) может быть представлена в виде

(сравним с формулой (12)).

2) Цифровой единичный скачок

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

3) Экспоненциальная последовательность

4) Комплексная экспонента

exp(n1 , n2) = exp[i(w1n1 + w2n2)],

где w1 , w2 имеют смысл пространственных частот.

2.3. 2D-системы

С математической точки зрения, 2D-система - это правило, которое ставит в соответствие 2D-входной последовательности f (n1 , n2) 2D-выходную последовательность g(n1 , n2).

Напомним, что мы рассматриваем линейные пространственно-инвариантные системы. Подавая на вход системы функцию u0(n1 , n2), на выходе получаем функцию h(n1 , n2), которая называется импульсной реакцией системы.

Импульсная реакция позволяет записать связь между входной и выходной двумерными последовательностями системы в виде

(сравним с (16)).

Формула 2D-свертки имеет большую вычислительную сложность. Для иллюстрации рассмотрим

Пример. Дана система с импульсной реакцией

Входная последовательность имеет вид

Необходимо рассчитать последовательность g(n1 , n2) на выходе этой системы.

Используя формулу (28), получим

Выполняя суммирование, получим

Сложность вычисления 2D-сверток даже в простых случаях дает представление о вычислительных трудностях, с которыми приходится сталкиваться при работе с 2D-системами.

Из рассмотренного выше примера видно, что, если входной сигнал (или импульсная реакция) имеет ограниченную протяженность, бесконечная сумма (28) в выражении двумерной свертки переходит в конечную:

Из формулы (29) видно, что для вычисления одного пиксела на выходе 2D-системы следует выполнить © M 2 арифметических операций.

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

ЛИТЕРАТУРА

1. Прэтт У. Цифровая обработка изображений. В двух книгах. М.: Мир, 1982.

* * *

Виктор Александрович Сойфер, профессор, ректор Самарского государственного аэрокосмического университета, специалист в области обработки изображений и компьютерной оптики. Им опубликовано 310 научных работ, в том числе 3 монографии, 50 работ опубликовано в зарубежных изданиях.

В.А. Сойфер является лауреатом Государственной премии России в области науки и техники 1992 года за разработку лазерных технологий и их внедрение при создании новой авиационно-космической техники, в 1993 году награжден первой премией Германского общества содействия прикладной информатике за лучшую научную работу в области обработки изображений и распознавания образов. Член международного оптического общества SPIE.