The algorithm of automatic recognition of geophysical processes analog records with the use of dynamic programming method

РОССИЙСКИЙ ЖУРНАЛ НАУК О ЗЕМЛЕ, ТОМ 2, N 2, Апрель 2000

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

А. А. Бурцев, М. Н. Жижин

Институт физики Земли РАН

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

1. Постановка задачи, основные определения, предварительные преобразования изображения

1.1. Постановка задачи

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

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

©2000 Российский журнал наук о Земле. Статья N RJE00037.

Онлайновая версия этой статьи опубликована 15 декабря 2000. URL: http://eos.wdcb.ru/rjes/v03/RJE00037/RJE00037.htm

вать этот след в виде временного ряда, описывающего зависимость амплитуды отклонения от времени.

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

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

2. Кроме полезной информации на изображении присутствует "шум", который может быть трех типов:

• загрязнение;

• вспомогательные линии, цифры и пометы интерпретатора;

• пересечение с соседними фрагментами записи.

В связи с этим возникает проблема ассоциации областей (или их частей), относящихся к одной траектории.

3. Склеивание реконструированных участков траектории в местах разрывов и восстановление пропущенных фрагментов.

Рис. 1. Алгоритм реконструкции следа самописца по его изображению.

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

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

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

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

4. По завершении реконструкции требуется пересчет полученной траектории в физические единицы измерения.

1.2. Схема алгоритма

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

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

Рис. 2. Построение скелета и выделение примитивов.

а) исходное изображение; б) его скелет; в) сегментированное изображение.

Рис. 3. Регуляризация и атрибуция примитивов, а) до регуляризации; б) после регуляризации.

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

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

3. Регуляризация и атрибуция примитивов

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

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

Рис. 4. Реконструкция следа самописца, а) исходный набор сегментов; б) выбранные сегменты.

кальных весов их склейки. Пример нахождения такого пути представлен на рис. 4. Локальные веса склейки определяются на основе расстояния между рассматриваемыми сегментами и взаимном расположении их концевых участков.

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

1.3. Предварительная обработка изображения

Исходный материал существует в виде изображений на бумаге или микрофильмов. Для ввода этих изображений с бумажного носителя используется планшетный сканер. В случае микрофильмов может использоваться либо проекционный сканер, либо цифровой фотоаппарат с большой разрешающей способностью. Результаты сканирования могут сохраняться в виде изображения (например, в графическом формате TIFF, см. [Борн, 1995]) как двухцветного (черно-белого), так и содержащего оттенки серого или цветного. Если исходное изображение не является двухцветным, то оно приводится к нему путем порогового преобразования. В резуль-

Рис. 5. Построение результирующей кривой, а) выбранные сегменты; б) результирующая кривая.

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

Рассмотрим подробнее способ перевода изображения к двухцветному представлению. Если изображение цветное, каждая точка может быть задана тройкой чисел (R,G,B), определяющей, каким образом данный цвет получается из трех основных цветов: красного (R), зеленого (G) и синего (В). Каждая из этих величин принимает целые значения и находится в пределах от 0 до 255.

С учетом интенсивности цветное изображение преобразуется в оттенки серого по следующей формуле:

С = round

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

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

Теперь, когда изображение приведено к двухцветному представлению, осталось определить: какой из этих двух цветов соответствует сигналу, а какой -фону. Для этого вычисляем процент площади, покрываемой каждым из этих цветов, и фоновым объявляем цвет, получивший больший процент (более 50%). Данные о занимаемой площади могут быть получены как путем анализа самого изображения (в том числе методом Монте-Карло [Бахвалов, 1975; Бахвалов и др., 1987]), так и его гистограммы.

2. Применение математической морфологии для построения скелета изображения

2.1. Основы математической морфологии

Математическая морфология (mathematical morphology) - это теория, изучающая методы выделения структурной информации на изображении для ее использования в машинном зрении (computer vision). Изображения в ней рассматриваются как функции на целочисленной решетке. В связи с этим математическую морфологию можно рассматривать как формальный язык с элементарными операторами и опе-

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

Определение 2.1-1. Множество L называем частично упорядоченным, если на нем введена операция отношения < такая, что для любых а, Ь, с £ L выполнены три свойства:

1) рефлективность: а < а

2) антисимметричность: если а < Ь, то — b < —а

3) транзитивность: если а < b и b < с, то а < с.

Определение 2.1-2. Полной решеткой (complete lattice) называем частично упорядоченное множество, любое непустое подмножество которого имеет точную верхнюю и нижнюю грани.

Определение 2.1-3. Математическая морфология - это теория, изучающая распределение операторов между полными решетками в терминах некоторого семейства простых операторов: расширение (dilation), размывание (erosion), анти-расширение (anti-dilation), анти-размывание (anti-erosion). Эти операторы называют элементарными операторами математической морфологии.

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

Операторы в НИММ организуются иерархически, основываясь на их распределении в терминах элементарных операторов. Таким образом, мы определяем, в порядке возрастания сложности, следующие семейства операторов и операций: основные операторы и операции, операторы первого, второго и третьего уровня. Здесь будут определены операторы, необходимые для решаемой задачи. Описание других можно найти в работах по математической морфологии [Вапоп and Barrera, 1991; Konstantimdes and Rasure, 1994].

С алгебраической точки зрения элементарные операторы являются отображениями между полными решетками со следующими свойствами:

Определение 2.1-4. Пусть L\ и L2 - полные ре-

шетки, хСЬь Оператор ф называется

• расширением из L\ в ¿2, если ф{Ух) = Уф

• размыванием из L\ в ¿2, если ф{/\х) = ^Ф

• анти-расширением из L\ в ¿2, если ф{Ух) = ^Ф

• анти-размыванием из L\ в L2, если ф(/\х) = VV'(x), где А и V означают соответственно пересечение и объединение в теоретико-множественном смысле.

Пусть Z - множество целых чисел, /={ —1,0,1} х {-1,0,1}CZ2, Е = ([0, ш] х [0, п]) П Z2, К = [0,A:]nZ,

где к,т,п > 0. Обозначим КЕ - множество функций из Е в К. Далее, если не указано противное, мы полагаем что /, д, Д, /2 - функции из КЕ . Эти функции представляют изображение с оттенками серого и бинарное, если К = {0,1}.

Основные операторы и операции

Пересечение и объединение двух функций определяется соответственно следующими формулами:

Операторы дополнения и разности определим соответственно как

Пусть B<Zl, h - вектор из Z2. Тогда обозначим В + h = {х + h : х £ В} ,

В4 = {-х : х Е В}

0 если t = 0 или {i > 0 и i + п < 0} t+n = <{ t + п если t>0n0<.t + n<k к если i > 0 ж i + n > i ,

0 если t<kw.t — п< 0 t—и = <{ t — п если t<kn0<t — п<к

к если {t<knt — п>к} или t = к .

+

Рис. 6. Применение оператора расширения.

а) исходное изображение; б) результат применения

расширения.

ôg{f) £ КЕ (соответственно £g(f) G КЕ), определенная для любого х G Е и задаваемая как

Sg{f){x) = тах{/{у)+д{х -у) : у £ (В* + х)ПЕ}

£д(/)(х) = тт{/(у)-д(у-х) : у £ (В + х) П Е) ,

причем тах(0) = О,тт(0) = к.

Далее мы будем использовать частный случай этого определения - когда функция д постоянна и равна нулю. При этом расширение и размывание зависят только от структурного элемента В и называются соответственно расширением и размыванием / по В. Формулы для них перепишутся в виде:

Вс = {х Е I : х <£ В) .

Определение 2.1-5. Структурным элементом называем любое подмножество В С /• Множество I называем элементарным квадратом. В дальнейшем мы будем задавать структурные элементы в виде матрицы размера 3x3, где единицы соответствуют присутствию данного элемента в В, а ноль - его отсутствию.

Введем две бинарные операции из К х Z в К, определенные для всех 4 £ А', п<Е Z :

SB (/) (х) = max {f(y) : у е {В* + х)пЕ}

ев

На рисунках (рис. 6, рис. 7) показано изображение до и после применения расширения и размывания при использовании в качестве структурного элемента квадрат I = { — 1,0, 1} х { — 1,0, 1}.

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

+

Определение 2.1-6. Пусть д - функция, отображающая структурный элемент В в Z,^E КЕ - функция из Е в К. Тогда расширением (соответственно размыванием) функции f по д называется функция

Рис. 7. Применение оператора размывания.

а) исходное изображение; б) результат применения

размывания.

Определение 2.1-11. Операторы

са,в = г ~ АА в и тА в = г V АА

в

Рис. 8. Применение операторов открытия и замыкания.

а) результат открытия; б) исходное изображение; в) результат замыкания.

назовем соответственно операторами уменьшения и увеличения толщины по паре структурных элементов (А,В).

Операторы второго уровня

Эти операторы строятся с использованием конечного числа основных операторов. Введем следующие обозначения:

Л

п > 0 п_[гвК£в, п> 0 в ~ \ г, п = 0 в ~ \ г, п = 0

п-кратное расширение и п-кратное размывание,

Определение 2.1-7. Оператор г из КЕ в КЕ, заданный для любого /, такой что

»'

назовем единичным оператором.

Операторы первого уровня

Эти операторы строятся с использование только одного основного оператора каждого типа. Определим некоторые из них

Определение 2.1-8. Операторы

¿в =~ ¿В" и еав =~ ев

назовем соответственно анти-расширением и антиразмыванием по В.

Определение 2.1-9. Операторы

7в = &в£в и (рв =

А а,в — £а Л 8ав1 и ца, в — ¿а V

Л,п _ СП ^п ,п _ ^п СП

1в - дВ£В <Рв - £ВдВ

п-кратное открытие и п-кратное замыкание по В.

Пусть а и ¡3 - две конечные последовательности, состоящие из п структурных элементов, причем А{ С В{. Тогда

=

п-кратное уменьшение толщины по паре (а,/3). Операторы третьего уровня

Эти операторы строятся рекурсивно, используя изначально неопределенное число основных операторов. Далее мы используем лишь один из этих операторов.

Определение 2.1-12. Пусть а и ¡3 - две бесконечные последовательности структурных элементов А{ и В{, причем А{ С 58-. Тогда оператором построения скелета путем уменьшения толщины по паре (а,/3) назовем композицию

назовем соответственно открытием и замыканием по В.

Используя в качестве структурного элемента квадрат I = { — 1,0, 1} х { — 1,0, 1}, изобразим результат применения к изображению (рис. 86) оператора открытия (рис. 8а) или замыкания (рис. 8в).

Определение 2.1-10. Пусть А и В - структурные элементы, и А С В. Тогда операторы

Для примера рассмотрим следующую последовательность структурных элементов:

0 0 0 А! = | О 1 0 1 1 1

В{ =

назовем соответственно порождающим сверху и порождающим снизу.

Остальные структурные элементы строим так: последующий получаются из предыдущего его поворотом по часовой стрелке на 45 градусов. Таким образом

Ао =

Аз =

Вс2 =

В1 =

Л, |_8 — ¿¿, 5„с_,_я — 5?, Л .

+8

Скелет изображения, построенного с помощью оператора, определяемого формулой (24) и использующего последовательности структурных элементов (25) и (26) изображен на рис. 9.

Рис. 10. Применение операции замыкания, а) исходное изображение; б) результат замыкания.

2.2. Замыкание информационных областей

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

Замыкание представляет собой совокупность двух последовательно примененных операций (вначале расширение, затем размывание) и определяется по формуле (17). Для построения замыкания, в качестве структурного элемента В мы используем элементарный квадрат I = { — 1,0,1} х { — 1,0,1}. Отметим два очевидных свойства:

Утверждение 2.2-1. При замыкании происходит объединение информационных "островков" на изображении, расстояние между которыми меньше размера структурного элемента.

Утверждение 2.2-2. При замыкании фоновые "дырки" на изображении, которые меньше, чем структурный элемент, закрываются.

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

Рис. 9. Применение оператора построения скелета, а) исходное изображение; б) построенный скелет изображения.

2.3. Построение скелета информационных областей на фотоизображении

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

—

где используется следующие последовательности структурных элементов:

¿1,1 =

А1 я =

¿1,5 =

А 1,7 =

0 0 0

0 0 0

0 1 1

0 0 0

1 0 0

1 0 0

1 1 0

0 0 0

0 0 0

0 0 1

0 0 1

0 0 0

¿1,2 =

А1 4 =

¿1,6 =

¿1 8 =

Ао 1 =

А? я =

Ао 5 =

а 2,7 =

В1

Вс5

ВС7

1 О О

1 0 0 | , А2,4 ООО

1 1

о о о |, А2,6

ООО ООО

о о 1 | , А2,8 О 0 1

ООО

1 1 1

1 0 0 \ 1 0 0 1,5! 10 0/

А

1,8+8

= А,

а

2,8+8

= а2

5г+8 - 5г- .

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

Алгоритм 3.1-1. Переход от двухуровневого изображения к трехмерному представлению. Алгоритм состоит из прямого и обратного прохода по изображению:

Прямой проход: Отождествляя изображение с матрицей размера М х N, мы индуктивно просматриваем матрицу (изображение), начиная с ее верхнего левого угла и заканчивая правым нижним, изменяя значения ненулевых элементов по формуле:

= тш(аг'_1

з>'

-1+1

>¿-1

где г' = 1..М — 2, ] = 1..Ж-2,

,->0.

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

= тщ{тт(а,+1)„(1,)]+1) + 1!

где I = 1..М-2, ] = 1..Ж-2,

,->0.

2.4. Сегментация методом удаление узлов самопересечений

Определение 2.4-1. Ближайшей окрестностью точки называем множество точек Ьт п таких, что тах(|г — т\,\] — п\) = 1.

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

3. Построение скелета больших изображений методом преобразования расстояний

3.1. Переход от двухуровневого изображения к трехмерному представлению

Исходные данные - это двухуровневое изображение, где 0 соответствует фону, а 1 - сигналу. Мы

Если = 0, то для такого элемента значение по формулам (32), (33) не вычисляется.

Нетрудно видеть, что после этих преобразований изображение будет иметь искомый вид.

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

3.2. Построение предварительного скелета за одну итерацию

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

Введем общее определение точек хребта:

Определение 3.2-1. Точками хребта будем называть те точки целочисленной решетки, в которых

а

а

хотя бы одна из частных производных (по х или у) меняет знак, и точка является локальным максимумом по этому направлению.

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

Определение 3.2-2. Точка ф 0 на изображении является точкой хребта, если она является локальным, причем выполнено хотя бы одно из следующих четырех условий:

1) сцл > а%,]-1 и а%,] > а%,]+1)

2) = 0,1^-1,0,1^ > ai¡j-2 и > ai¡j+l,

3) > ai-l¡j и > ai+l¡j,

4) = ai-l¡j,ai¡j > ai-2,j и > ai+l¡j.

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

Совокупность всех точек хребта образует предварительный скелет изображения. Точки хребта ищутся за один просмотр изображения в соответствии с определением 2.3-2. После этого изображение преобразуется к трехуровневому виду: 0 - фон,

1 - информационные области, кроме точек хребта,

2 - точки хребта.

3.3. Коррекция построенного скелета и выделение примитивов

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

На первом шаге удаляем угловые точки.

Определение 3.3-1. Точку ai¡j = 2 (точка хребта) на изображении называем угловой точкой, если выполнено хотя бы одно из следующих четырех условий:

1) а%+1,] = а%,]+1 = 2,

2) а%-1,] = а%,]+1 = 2,

3) яг'+1= а%,]-1 = 2,

4) = а%,]-1 = 2.

Угловые точки ищутся и удаляются индуктивно за один просмотр изображения в соответствии с определением 3.3-1.

На втором шаге пытаемся соединить небольшие разрывы.

Определение 3.3-2. Ближайшей окрестностью точки а^^ называем множество точек Ьт п таких, что тах(|г — т|, — гг|) = 1.

Определение 3.3-3. Точка Ьт п касается точки ai¡j, если она лежит в ближайшей окрестности точки аг-^

Определение 3.3-4. Точку ai¡j = 1 (точка информационной области, но не хребта) на изображении называем точкой восстановимого разрыва, если выполнено два условия:

1) в ее ближайшей окрестности присутствуют ровно две точки хребта;

2) эти две точки не касаются друг друга.

Точки восстановимого разрыва ищутся и удаляются индуктивно за один просмотр изображения в соответствии с определением 3.3-4.

На третьем шаге мы удаляем узловые точки.

Определение 3.3-5. Точку ai¡j = 2 (точка хребта) на изображении называем узловой точкой, если в ее ближайшей окрестности лежит не менее трех точек.

Узловые точки ищутся и удаляются индуктивно за один просмотр изображения в соответствии с определением 3.3-5.

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

3.4. Регуляризация и атрибуция примитивов

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

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

¡{1) =

где ^ = 0..Ж — i] n - число точек в сегменте.

Для этого мы просматриваем изображение, извлекаем связанные (по определению касания 3.3-3) участки скелета, образующие сегменты, и преобразуем их к виду (34). При этом /(0) соответствует начальной точке сегмента, а /(N — 1) - конечной.

На втором этапе мы сглаживаем ж(^), компенсируя ее колебания не превышающие вариации 1. Т.е. значения функции ж(^) на участке, где разница между максимумом и минимумом не превышают 1, устанавливаем равными ее округленному среднему значению на этом участке.

На третьем этапе мы ищем точки, в которых производная от функции меняет знак, и разбиваем сегмент на части в этих точках. Производная вычисляется по методу разделенных разностей ([Бахвалов, 1975; Бахвалов и др., 1987]) по следующей формуле:

^ = х{1 + 1)-х{1) .

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

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

3.5. Преимущества и недостатки рассмотренного метода

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

Основным недостатком техники математической морфологии по сравнению с методом преобразования расстояний является скорость. Операторы математической морфологии "снимают шкурку" с информационных областей, уменьшая их толщину по всем или только по выбранным направлениям в зависимости от используемого набора структурных элементов. Это приводит к весьма аккуратному (при правильном выборе структурных элементов) скелету, однако требует многократного просмотра изображения: не менее 1/2 от минимальной ширины наиболее широкой области. С учетом того, что для нахождения скелета обычно используется последовательность структурных элементов, это число возрастает в несколько раз. Например, в случае использования последовательности элементов заданной формулами (25) и (26) для изображения с шириной областей в 10 точек (что очень немного), изображение придется просматривать около 20 раз. Для построения достаточно качественного скелета (аналогичного тому, что строится математической морфологией) методу преобразования расстояний требуется лишь трехкратный просмотр изображения, причем независимо от размеров информационных областей на нем.

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

лет, что делает их сравнимыми по этому показателю.

Оба метода могут применяться к многоуровневым изображениям в оттенках серого.

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

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

4. Реконструкция следа самописца методом динамического программирования с последующим сглаживанием сплайнами

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

4.1. Вычисление локальных весов склейки сегментов

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

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

Запишем сказанное выше в виде формул. Пусть имеются два сегмента А = |а1,...,ат}, В =

{&!,...,&„} и две точки р, д, где щ, д Е К2. Рассмотрим, как вычисляются для них значения весовой функции.

Пусть нужно вычислить вес склейки сегментов А и В. Он равен минимальному из четырех весов склейки концов сегментов. Для определенности рассмотрим начало сегмента А и начало сегмента В (остальные три вычисляются аналогично).

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

/? =

arctan

7Г

2'

arctan

7Г

2'

Уa i Уа0

УЬ! - УЬ0

Xbi -f- %bo

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

7 =

arctan

7Г

2'

У Ь0 У ар

ХЪр % а о

ХЪ0 -/- % а

s =

mm

8 е [о, i]

...................... -к

N

А/

/

/ \ в

/

г

Рис. 11. Углы при вычислении склейки сегментов.

всеми точками сегмента и граничнои точкой.

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

arctan

7Г

2'

Уак

Уак

X

(.1 Ф хак-1

ajc + i / лак-

иначе.

Найдем средний угол отклонения касательных в начальных точках сегментов от прямой, соединяющей эти точки, и нормируем его, т.ч. максимальное значение равно 1:

Искомое расстояние D(A, В) вычисляется по следующей формуле:

D

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

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

min

2

Искомое расстояние D(A,p) будет вычисляться по формуле:

D

Расстояние между граничными точками р и qD(p, q) будет вычисляться по формуле:

D

4.2. Отбор примитивов, образующих оптимальный путь

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

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

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

Рассмотрим теперь, как вычисляется расстояние зависящей только от этих двух примитивов. Исходя между сегментом А и граничной точкой р. Для из этого, можно считать, что сумма весовых функ-

Oi

а о

Хак + 1 X

и>к-1

i

Рис. 12. Поиск оптимального пути в графе.

зующих оптимальный путь, будет минимальна:

^ЦД-, A'+i)->-min ,

i

где А ~~ г'ьш сегмент в последовательности примитивов определяющих след, a id(A, A+i) ~~ значение весовой функции.

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

В начале кратко поясним суть алгоритма (рис. 12).

Изначально все вершины, кроме начальной, полагаем открытыми. На каждом шаге ищем открытую вершину с номером к, выбранный путь до которой имеет минимальную (среди других вершин) длину Sfc, и полагаем ее закрытой. Рассмотрим открытые вершины с номерами г и путями s8, в которые входит ребро веса w^i из вершины к. Тогда, если Sk + Wki < Si, то полагаем s8 = Sk + w^i, т.е. вершине г соответствует новый оптимальный путь. Алгоритм завершается, как только выбранная вершина, имеющая минимальный путь, будет соответствовать конечной точке.

Теперь рассмотрим этот алгоритм более подробно. Пусть граф содержит Ж + 1 вершину. Каждому ребру (i,j) приписан вес, задаваемый как cost(i,j). Начальную вершину исключаем из рассмотрения, и остается N вершин. Введем три вектора размера N, называемые chain, flags, costs:

• chain[i] - содержит номер вершины, предшествующей вершине с номером г, в наилучшем (в данный момент) пути из начальной точки в г-ую вершину

• costs[i] - содержит стоимость (т.е. сумму весов) наилучшего (в данный момент) пути из начальной точки в г-ую вершину

• flags[i] - показывает, можем ли мы делать шаг из данной вершины

Алгоритм 4.2-1. Отбор примитивов, образующих оптимальный путь. Алгоритм состоит из трех этапов:

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

FOR (каждая вершина г) DO chain[i]="He определена" flags[i]= "открыта"

costs[i]=cost

ENDFOR

2. Прямой проход (поиск оптимального пути) WHILE (существует открытая вершина) DO

к = arg(min(costs[i] : fIags[г]== "открыта" )) flags[fc]= "закрыта" IF (&==конечная вершина) завершить цикл

ENDIF

FOR (каждая вершина j, такая что существует ребро (k,j)) DO

IF

costs[j] = costs[fc] + cost (к, j) chain [j] = к ENDIF ENDFOR ENDWHILE

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

к= "конечная вершина" path= "пустой"

WHILE (chaiп[/г] - определена) DO к=chainffc]

вставить к в начало path ENDWHILE

Сформулируем и докажем несколько утверждений, на которых основывается алгоритм.

Утверждение 4.2-1. Алгоритм требует не более N2/2 вычислений весов между вершинами (функция cost(i, j)). Тем самым не требуется хранить матрицу весов. Число арифметических операций порядка N2. Доказательство: очевидно из структуры алгоритма 4.2-1, поскольку после каждого шага число откры-

тых вершин уменьшается на 1.П

Определение 4.2-2. Будем называть сумму весов ребер, образующих путь до вершины, весом пути до этой вершины.

Определение 4.2-3. Путь до вершины назовем минимальным, если он имеет наименьший вес среди всех ведущих в нее путей.

Определение 4.2-4. Открытую вершину, выбранный путь до которой в данный момент обладаем наименьшим весом (среди путей в этот же момент ведущих к другим вершинам), назовем оптимальной стартовой вершиной.

Определение 4.2-5. Шагом алгоритма из выбранной вершины будем называть последовательность действий, заданных циклом FOR в части 2, алгоритма 4.2-1.

Утверждение 4.2-6. Путь до оптимальной стартовой вершины является минимальным. Доказательство: очевидно, в силу определения оптимальной стартовой вершины: прохождение пути через любую из оставшихся вершин, приведет лишь к увеличению веса пути до стартовой вершины.

Следствие 4.2-6-1. Шаг из оптимальной стартовой вершины может быть произведен лишь однажды, поэтому сразу после этого такую вершину можно положить закрытой и далее не рассматривать. Доказательство: очевидно, в силу минимальности пути до нее.П

Следствие 4.2-6-2. Полученный в результате алгоритма 4.2-1 путь в графе является минимальным. Доказательство: В силу утверждения 4.2-6, путь до каждой из вершин, определяющих по завершению алгоритма путь в графе, является минимальным. Поэтому до конечной точки будет также минимальным.

Следствие 4.2-6-2 доказывает, что представленный выше алгоритм 4.2-1 выбора примитивов, образующих оптимальный путь, действительно минимизирует сумму локальных весов склейки сегментов.

4.3. Интерполяция кубическими сплайнами

Напомним определение кубического интерполяционного сплайна и выпишем формулы для его построения (более подробно об этом и других способах интерполяции сплайнами см. [Бахвалов, 1975; Бахвалов и др., 1987]).

Определение 4.3-1. Пусть заданы Ж+1 точка: хо, ..., xn(N > 2). Кубическим интерполяционным сплайном S(x) функции / по этим точкам называется кусочно-полиномиальная функция третьей степени, обладающая непрерывными производными второго порядка в точках xo,...,Xjy такая, что S(xi) = f(xi),i = 0..N.

Введем обозначение

Mi = S"

Тогда при х G [xi-i, Xi]

S"(x) = Mi_1-

1

Mi

X X ^_

Дважды интегрируя это равенство, константы находим из условий:

1. S(xi) = f(xi),i = 0..N,

2. S(x) - дважды непрерывно дифференцируема на [хо, ждг].

В результате имеем при х £ [ж8-_1, ж8-], hi = ж8- — ж8_ 1, г = 1..N

/ _ \3 ( _ . \3

I X о X I I X X о_1 I

Pi(x) = S(x) = M,--1V ,, ; +Miy 1J '

6 hi

/(n.il-Mi.j-i

6 hi

f(xi) - Mi

6 / hi h: \ X X i — \

6

hi

Надо найти вектор М = (Мо, • • •, М^). В силу второго условия

Pi (xi) — Pi+1(Xi) .

Отсюда, полагая Мо = Мдг = 0, г = 1..N — 1 получаем систему из Ы — 1 уравнения: с Ж —1 неизвестным:

hi hi + hi.и h,

— M8-_i + + Mi + -

6 3 6

+1

M.-+1 =

f

h

i+1

hi

В матричном виде (50) можно записать СМ* = с1, где С - трехдиагональная матрица размера Ж—1 х N — 1, М* = {М\, ..., Мдг_ 1), с1 - вектор-столбец высоты N — 1. Данная система решается методом прогонки за 8Ж арифметических операций.

Выпишем основные формулы для решения уравнений с трехдиагоальной матрицей методом прогонки. Пусть имеется система уравнений:

ацх 1 + ai2x2 = b i

а2\Х\ + а2 2X2 + а2зхз = &2

аз2Х2 + а33ж2 + а34ж3 = Ь3

a-NN-lXN-l + a^NXN = bN

Выражая из к-ого уравнения х& получаем:

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

Хк =

В к — акк+гХк+1

Ак

к = 1..Ж- 1 к = N ,

где

¿1 = а.\, 51 = Ьх

, акк-1

Ак — Окк--;-ак-1к

Ак-1

Вк = Ьк--;-Ви-1 •

Ак —

Для решения системы сначала вычисляем значения Ак и В к, начиная с 1, затем находим х^, начиная с последнего. Первое требует ЗЖ арифметических операций, второе - 5Ж.

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

4.4. Построение результирующей кривой по точкам отобранных примитивов

Окончательный вариант кривой строится в три этапа:

1. Отбираем точки, которые будут использоваться как узловые при интерполяции на следующем шаге. Они выбираются из отобран-

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

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

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

По полученным в результате интерполяции узлам мы можем восстановить значения амплитуды в ка-

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

Пользователь

Открыть файл с изображением сейсмограммы Геометрически преобразовать изображение

Установить привязку к физическим единицам

Установить временные метки

Установить амплитудную привязку

Сохранить результат оцифровки

Рис. 15. Работа пользователя с программой.

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

5. Программная реализация алгоритма на основе объектно-ориентированного подхода

5.1. Внутренняя структура: классы и их взаимодействие

Взаимодействие наиболее важных классов представлено на иМЬ-диаграммах (см. [Фаулер, Скотт, 1999]) взаимодействия классов (рис. 13 и 14). Здесь

классы интерфейса (СШшАрр, СМашРгате, ССЫЫ-Ргате, CWfdView, САА^сШос) выполняют все необходимые операции для обеспечения взаимосвязи пользователя и программы с целью эффективной и удобной работы.

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

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

Класс CImageSkeleton содержит описание скелета в виде набора примитивов и методы приведения последних к регулярному виду.

lEQWaveform digitizer 2.1 Ь2 - [СЛМои документы\620521 PULCPIph tif]  Jnlxl

Ф File View Commands Modes Window Help JffJxJ

esihihi«M ФН i a i \т«4~\тшмт м i *i

У\ Л ; Л-л Л /-V х-- ___

г I A

Рис. 16. Скелет изображения.

Класс CImageTrace отвечает за построение искомой траектории, на основе данных из класса С Image Skeleton.

Класс CUnitedTrace позволяет работать одновременно с несколькими независимыми фрагментами траектории (объектами класса CImageTrace). Он также осуществляет запись результатов в нужном формате.

Классы CBaseline, CTimeMarks и CAmplitude-Marks, содержат информацию и методы соответственно для определения базовой линии, временных меток и амплитудной привязки.

5.2. Пользовательский интерфейс

Пользовательский интерфейс ориентирован на использование в операционной системе MS Windows 95/98/NT. Допустима одновременная работа с несколькими документами. Управление программой осуществляется командами меню или панели инструментов. Работу пользователя с программой можно кратко представить на рис. 15.

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

По завершении предварительного этапа дается ко-

манда на построение скелета всего изображения. Результат представлен на рис. 16.

Затем по построенному скелету восстанавливаем искомую траекторию (изображение самого скелета можно отключить, как это сделано на рис. 17). Пользователь указывает сначала начальную точку, затем конечную. Искомая траектория на указанном участке восстанавливается по построенному на предыдущем этапе скелету. Якорь при этом перемещается к конечной точке, чтобы служить началом следующего участка траектории (рис. 17).

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

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

6. Примеры применения алгоритма и выводы

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

IBM Waveform digitize! 2.1 Ь2 - [СЛМои документы\Б20521 PULCHph tif] Г

ф- File View Commands Modes Window Help - |fl| x|

Л Лл Г1

hi I hi

I I I A

Рис. 17. Реконструкция траектории и установка меток для приведения результата оцифровки к физическим единицам измерения.

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

Эффективность алгоритма зависит в первую очередь от качества исходного изображения: он более эффективен на изображении с четко определенными областями полезного сигнала и малым количе-

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

Рис. 18. Оцифровка магнитограммы.

а) фрагмент магнитограммы (Екатеринбург 11 апреля 1997 г.); б) результат его оцифровки.

Рис. 19. Оцифровка сейсмограммы.

а) фрагмент сейсмограммы (Пулково, 10 марта 1912 г.); б) результат его оцифровки.

терфейсных задач является С++, на котором этот алгоритм и был реализован.

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

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

Литература

Бахвалов Н. С., Численные методы, Наука, Москва, 1975.

Бахвалов Н. С., Жидков, Кобельков Г. М., Численные методы, Наука, Москва, 1987.

Борн Г., Форматы данных, Торгово-издательское бюро BHV, Киев, 1995.

Минул М., Математическое программирование, теория и алгоритмы, Наука, Москва, 1990.

Фаулер М, Скотт К., UML в кратком изложении, Мир, Москва, 1999.

Banon G. J. F., and Ваггега J., Minimal representation for translation invariant set mapping by mathematical morphology, SIAM Journal of Applied Mathematics, 51, (6), 1782-1798, December 1991.

Bellman R.E., Dynamic programming, Princeton University Press, Princeton, NJ, 1957.

Konstantinides K., and Rasure J. R., The Khoros Software Development Environment for Image and Signal Processing, IEEE Transaction on image processing, 3, (3), 243252, May 1994.

John L. Spouge, Speeding up dynamic programming algorithms for finding optimal lattice path, SIAM Journal of Applied Mathematics, 49, (5), 1552-1566, October 1989.

Paul L. Rosin, Geoff A.W. West, Salience distance transforms, Graphical Models and Image Processing, 57, (6), 483-521, 1995.