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

Введение

Глава 1. Сущность и особенности задач обработки числовых квазипериодических последовательностей

1.1. Современное состояние проблемы обработки числовых последовательностей

1.2. Задача обнаружения

1.3. Задача совместного обнаружения и различения

1.4. Задача распознавания кодовых слов

1.5. Выводы

Глава 2. Апостериорное обнаружение одинаковых фрагментов

Введение

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

2.2. Обнаружение как задача проверки гипотез о среднем

2.3. Функция правдоподобия и целевая функция

2.4. Алгоритм обнаружения

2.5. Мощность множества проверяемых гипотез

2.6. Временная и емкостная сложность алгоритма

2.7. Численное моделирование

2.8. Выводы

Глава 3. Апостериорное совместное обнаружение и различение фрагментов

Введение

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

3.2. Совместное обнаружение и различение как задача проверки гипотез о среднем

3.3. Функция правдоподобия и целевая функция

3.4. Алгоритм совместного обнаружения и различения

3.5. Временная и емкостная сложность алгоритма

3.6. Численное моделирование

3.7. Выводы

Глава 4. Распознавание кодовых слов, скрытых в числовых квазипериодических последовательностях

Введение

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

4.2. Распознавание кодовых слов как задача проверки гипотез о среднем

4.3. Функция правдоподобия и целевая функция

4.4. Алгоритм распознавания

4.5. Временная и емкостная сложность алгоритма

4.6. Численное моделирование

4.7. Выводы 109 Заключение 112 Приложение 1. Распознавание штриховых кодов «чередование 2 из 5» 113 Приложение 2. Акт о внедрении результатов диссертационной работы 124 Литература

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

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

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

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

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

Для достижения цели выполняются следующие этапы:

• анализ подходов к решению проблемы обработки числовых квазипериодических последовательностей;

• исследование ключевых задач помехоустойчивой апостериорной обработки числовых квазипериодических последовательностей, а именно — задач: 1) обнаружения подпоследовательностей-фрагментов, 2) совместного обнаружения и различения подпоследовательностей-фрагментов, 3) распознавания кодовых слов, скрытых в квазипериодических последовательностях;

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

• анализ временной и емкостной сложности алгоритмов обработки;

• численное моделирование.

Методы исследований опираются на аппарат теории вероятностей, математической статистики, исследования операций, а так же на математическое моделирование.

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

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

1) обнаружения одинаковых подпоследовательностей-фрагментов;

2) совместного обнаружения и различения подпоследовательностей-фрагментов;

3) распознавания кодовых слов, скрытых в числовых квазипериодических последовательностях.

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

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

Результаты диссертационной работы были использованы в Конструкторско-Технологическом Институте Научного Приборостроения СО РАН при научно-исследовательской разработке системы распознавания штриховых кодов.

Связь с государственными программами. Работа выполнена в рамках проектов № 97-01-00866, № 00-01-00795, № 01-01-06282-МАС, № 02-01-06491-MAC, поддержанных РФФИ.

Апробация работы. Основные результаты работы докладывались на Всероссийских конференциях «Математические методы распознавания образов» (ММРО-8-1997, ММРО-9-1999, ММРО-10-2001), Сибирском конгрессе по прикладной и индустриальной математике (ИНПРИМ-4-2000) и международной конференции «Распознавание образов и анализ изображений» (РОАИ-5-2000).

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

Публикации. По теме диссертации опубликовано 13 работ.

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

Структура и объем работы. Диссертационная работа изложена на 136 страницах и состоит из введения, четырех глав, заключения и двух приложений. Основной текст занимает 112 страниц. Иллюстративный материал включает 18 рисунков. Список литературы состоит из 195 наименований.

4.7. Выводы

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

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

Показано, что для корректной постановки задачи задаваемые параметры должны быть увязаны между собой. Эта связь зафиксирована в леммах 2.2.1-2.2.3, 4.2.1 и утверждении 2.2.1. Для построения вычислительного алгоритма задача распознавания кодовых слов была проинтерпретирована как специфическая задача проверки совокупности простых гипотез о среднем случайного гауссовского вектора (п. 4.2). Заметим, что данная задача проверки гипотез обладает теми же специфическими особенностями, что и ее аналоги, рассмотренные в предыдущих главах. Основную проблему при организации процесса вычислений представляет экспоненциальный рост мощности множества проверяемых гипотез с увеличением длины обрабатываемой последовательности, кроме того, мощность этого множества линейно зависит от числа кодовых слов в словаре. Результаты параграфов 4.4. и 4.5 показывают, каким образом эта проблема может быть решена за полиномиальное время.

Поскольку априорное распределение на множестве проверяемых гипотез не определено, для построения вычислительного алгоритма, так же как и в предыдущих главах, был использован критерий максимального правдоподобия. Показано (лемма 4.3.1), что сущность алгоритма распознавания кодовых слов состоит в вычислении минимума вспомогательной целевой функции и определении аргументов, доставляющих этот минимум. Структуру алгоритма минимизации раскрывает лемма 4.4.1. Показано, что алгоритм минимизации распадается на два этапа. Первый этап — условное обнаружение и разбиение подпоследовательностей, второй — распознавание. При этом второй этап реализуется путем простого перебора и не представляет вычислительных проблем. Ядром же алгоритма является первый этап, состоящий в решении задачи поиска экстремума сепарабельной целевой функции с ограничениями в виде линейных неравенств. Рекуррентные формулы для ее решения следуют из теорем 4.4.1, 4.4.2, леммы 4.4.2 и следствий 4.4.1-4.4.6. Фактически, в перечисленных утверждениях решена более общая дискретная экстремальная задача (обобщение касается лишь системы неравенств-ограничений и не затрагивает вида целевой функции). Как отмечалось в главе 1, существуют два возможных подхода к построению алгоритма распознавания: разработка многопроходового алгоритма последовательного перебора по допустимым значениям числа подпоследовательностей и разработка однопроходового. Реализация первого подхода зафиксирована в теореме 4.4.1 и следствиях 4.4.2, 4.4.3, второго — в теореме 4.4.2 и следствии 4.4.5. Анализ временной и емкостной сложности, проведенный в параграфе 4.5 (следствия 4.5.1-4.5.4), устанавливает, что задача распознавания кодовых слов полиномиально разрешима, при полиномиальных затратах по памяти. Кроме того, показано, что построенный однопроходовый алгоритм дает существенный выигрыш по временным и емкостным затратам по сравнению с многопроходовым алгоритмом последовательного перебора по допустимым значениям числа фрагментов. Результаты численного моделирования, свидетельствующие о высокой помехоустойчивости предложенного алгоритма, завершают исследование поставленной задачи распознавания кодовых слов.

Заключение

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

1) обнаружения неизвестного числа одинаковых подпоследовательностей-фрагментов в квазипериодической последовательности;

2) совместного обнаружения и различения неизвестного числа подпоследовательностей-фрагментов в квазипериодической последовательности;

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

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

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

Совокупность предложенных алгоритмов по существу является базой для решения разнообразных прикладных задач в которых предполагается наличие квазипериодической структуры сигналов. Созданная алгоритмическая база легла в основу системы распознавания штриховых кодов «чередование 2 из 5» (см. приложения 1 и 2).

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

1. Клигене Н. Исследование точности оценки максимального правдоподобия момента изменения параметров уравнения авторегрессии // Статистические проблемы управления. — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1975. — Вып. 12. — С. 42-70.

2. Клигене Н. Точное распределение оценки максимального правдоподобия момента изменения параметров авторегрессии // Статистические проблемы управления. — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1978. — Вып. 31. — С. 9-28.

3. Липейка А. Определение моментов изменения свойств авторегрессионной последовательности // Статистические проблемы управления. — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1977. — Вып. 24. — С. 27-71.

4. Телькснис Л. Определение изменения свойств случайных процессов при неполных априорных данных // Статистические проблемы управления. — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1975. — Вып. 12. — С. 9-26.

5. Телькснис Л. Определение наиболее вероятных изменений свойств многомерных динамических систем с неизвестными параметрами // Статистические проблемы управления. — Вильнюс: Ин-т математики и кибернетики АН ЛитССР, 1977. — Вып. 24. — С. 9-26.

6. Телькснис Л. О применении оптимального байесова алгоритма обучения при определении момента времени изменения свойств случайных сигналов // Автоматика и телемеханика. — 1969.-№ 6. ■— С. 52-58.

7. Лумельский В.Я. Один алгоритм обнаружения момента времени изменения свойств случайного процесса // Автоматика и телемеханика. — 1972. — № 10. — С. 67-73.

8. Монтвилас А. Обработка результатов наблюдений при определении изменения свойств случайных сигналов // Статистические проблемы управления. — Вильнюс: Ин-т математики и кибернетики АН ЛитССР. — 1973. — Вып. 7. — С. 41-53.

9. Box G.E.P., Tiao G.C. A change in level of a nonstationary time series // Biometrika. — 1965. —N 1-2, —P. 181-192.

10. Chernoff H., Zacks S. Estimating the current mean of a normal distribution which is subjected to a change in time // Ann. Math. Statist. — 1964. — Vol. 35, N 3. — P. 999-1018.

11. Hawkins D.M. Testing a sequence of observations for a shift in location // J. Am. Stat. Assoc. — 1977,—Vol. 72,N357. — P. 180-186.

12. Дарховский B.C., Бродский Б.Е. Апостериорное обнаружение момента «разладки» случайной последовательности // Теория вероятностей и ее применения. — 1980. — Т. XXV, вып. 3. — С. 476-489.

13. Hinkley D.V., Hinkley Е.А. Inference about the change point in a sequence of binomial variables // Biometrika. — 1970. — Vol. 57, N 3. — P. 477-488.

14. Hinkley D.V. Inference about the intersection in two-phase regression // Biometrika. — 1969. — Vol. 56, N 3. — P. 495-504.

15. Hinkley D.V. Inference about the change-point in a sequence of a random variables // Biometrika. — 1970, —Vol. 57, N 1. — P. 1-17.

16. Hinkley D.V. Time-ordered classification // Biometrika. — 1972. — Vol. 52, N 2. — P. 509-523.17.