birmaga.ru
добавить свой файл

1 2 3

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


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

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

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

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


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

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


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


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

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

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

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

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

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


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

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


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




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

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



а) б) в)
Рис. 1.2 2. Построение скелета и выделение примитивов
а) исходное изображение; б) его скелет; в) сегментированное изображение


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


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


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


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

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


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



следующая страница >>