Содержание к диссертации
Введение
Глава 1. Анализ современного состояния проблемы разработки и контроля качества ПСОАИ 16
1.1. Общая характеристика ПС ОАИ 16
1.1.1. Назначение и область применения ПС ОАИ 16
1.1.2. Особенности математического обеспечения, используемого при разработке ПСОАИ 18
1.2. Особенности процесса разработки и контроля качества ПС ОАИ 22
1.3. Общие подходы к разработке и контролю качества программных средств 26
1.3.1. Обеспечение качества процессов контсруирования ПС 28
1.3.2. Контроль качества ПС 31
1.4. Постановка задачи повышения эффективности процессов разработки и контроля качества ПС ОАИ 37
Выводы по главе 1 39
Глава 2. Методы и средства разработки ПС ОАИ 40
2.1. Модель ЖЦ ПС ОАИ 40
2.2. Методы и средства организации ЖЦ ПС ОАИ 43
2.2.1. Метод и средства формализации спецификаций ПС ОАИ 43
2.2.2. Методы и средства архитектурного проектирования и реализации ПСОАИ 47
2.3. Метод формализованного описания спецификаций ПМ ОАИ 51
2.4. Метод поиска источника ошибки, выявленной в ПМ, реализующем эвристический алгоритм анализа изображений 56
Выводы по главе 2 62
Глава 3. Методы и средства контроля качества ПС ОАИ 63
3.1. Способ верификации программ, содержащих подпрограммы, массивы и особые операторы 63
3.1.1. Обобщение метода Флойда 63
3.1.1.1. Верификация ПМ, содержащих подпрограммы 63
3.1.1.2. Верификация ПМ, содержащих массивы 68
3.1.1.3. Верификация ПМ, содержащих особые операторы 69
3.1.2. Обобщение метода Хоара 72
3.1.2.1. Верификация ПМ, содержащих подпрограммы 72
3.1.2.2. Верификация ПМ, содержащих массивы 74
3.1.2.3. Верификация ПМ, содержащих особые операторы 74
3.2. Практические рекомендации по организации процесса верификации ПСОАИ 75
3.2.1. Построение спецификций ПМ ОАИ 76
3.2.2. Формирование индуктивных утверждений Флойда 79
3.2.3. Верификация ПМ ОАИ с помощью метода Хоара 83
3.2.4. Доказательство завершаемости ПМ ОАИ 84
3.2.5. Уточнение спецификаций ПМ ОАИ 86
3.3. Верификация ПМ ОАИ, реализующих эвристические алгоритмы 87
3.4. Способ тестирования завершаемости циклических структур ПС ОАИ 89
Выводы по главе 3 92
Глава 4. Разработка и обеспечение качества ПО ОЭСИ объектов подвижного состава железнодорожного транспорта 93
4.1. Общее описание ОЭСИ объектов подвижного состава железнодорожного транспорта ARSCIS 93
4.2. Унифицированная система формализованных спецификаций ПМ ОАИ для системы ARSCIS 96
4.3. Объектно-ориентированная архитектура ПО ARSCIS 102
4.3.1. Статическая модель ПО ARSCIS 104
4.3.2. Динамическая модель ПО ARSCIS 109
4.3.3. Анализ планируемое ПО ARSCIS 112
4.4. Обеспечение качества ПО ARSCIS 116
4.5. Оценка качества ПО ARSCIS 123
Выводы по главе 4 133
Глава 5. Оценка эффективности предложенных методов и средств разработки и контроля качества ПС ОАИ 135
5.1. Описание проектов, в ходе которых оценивалась эффективность предложенных методов и средств разработки и контроля качества ПС ОАИ 135
5.2. Преимущества использования метода формализованного описания спецификаций ПМ ОАИ 138
5.3. Преимущества использования метода поиска источника ошибки в ПМ,
реализующем эвристический алгоритм 141
5.4. Оценка эффективности методов контроля качества ПС ОАИ 144
5.5. Перспективы развития методов разработки и контроля качества ПС ОАИ 147
Выводы по главе 5 147
Заключение 149
Список литературы
- Особенности математического обеспечения, используемого при разработке ПСОАИ
- Метод и средства формализации спецификаций ПС ОАИ
- Верификация ПМ, содержащих массивы
- Унифицированная система формализованных спецификаций ПМ ОАИ для системы ARSCIS
Введение к работе
В настоящее время одним из перспективных направлений развития информационных технологий в таких областях человеческой деятельности, как промышленное производство, транспортные перевозки, медицина, охранное наблюдение и т.п. является создание средств информационной поддержки в составе автоматизированных систем контроля и управления. Указанные системы включают в себя как телекоммуникации, так и подсистемы сбора, обработки и анализа данных. При этом в качестве входного потока информации (или его части) широко используются изображения, т.е. данные, полученные с помощью приборного наблюдения (в основном, сканирования и фотографирования в различных диапазонах частот) соответствующих объектов или сцен.
Благодаря появлению в последние годы достаточно мощных и доступных средств вычислительной техники в большинстве приложений стало возможно выполнять обработку и анализ входных изображений на базе ПЭВМ при помощи специально создаваемых программных средств (ПС). Основными этапами представления, обработки и анализа информативных сигналов, которые в совокупности или в отдельных сочетаниях могут выполняться ПС обработки и анализа изображений (ОАИ), являются следующие: фильтрация, сегментация, классификация изображения и его фрагментов, распознавание графических образов. Методы и алгоритмы, которые могут быть использованы при разработке математического обеспечения указанных этапов, широко представлены в научно-технической литературе.
Наиболее важная особенность задач обработки и анализа изображений заключается в том, что большинство из них являются плохо формализуемыми. Сказывается отсутствие адекватных математических моделей наблюдаемых реальных ситуаций или объектов, на базе которых можно было бы вести расчеты и получать количественные и качественные выводы, а также разрабатывать соответствующее программное обеспечение (ПО). В то же время практически любой человек в реальной жизни постоянно и успешно решает такие задачи и может выступать экспертом как при подготовке обучающего и тестового материала, так и при оценке эффективности алгоритмов, реализуемых ПС ОАИ.
Указанная особенность, накладывая ограничения в рамках общей проблемы синтеза и оптимизации алгоритмов обработки и анализа изображений, обуславливает также возникновение ряда вопросов и задач, решение которых необходимо для
7 организации эффективных процессов разработки, обеспечения и контроля качества ПС ОАИ, реализующих такие алгоритмы. Так при разработке и автоматизации контроля качества ПС ОАИ, оперирующих трудно формализуемыми понятиями, требует решения задача адекватного описания спецификаций. Широкое использование эвристических алгоритмов при создании ПС ОАИ затрудняет выполнение процессов контроля качества таких ПС, в первую очередь, тестирования и отладки. Кроме того, наличие в коде ПС ОАИ большого количества массивов, циклов и операторов, которые могут не завершиться и привести к исключительной ситуации или аварийному сбою (особые операторы), обуславливает необходимость использования специализированных способов и методик верификации, тестирования и отладки ПС.
Исследование теоретических и практических аспектов разработки и контроля качества ПС отражено в трудах В.Н.Агафонова, А.П.Ершова, С.С.Лаврова, В.В.Липаева, В.А.Непомнящего, С.А. Орлова, Р.Андерсона, Б.Боэма, Г.Буча, Э.Дейкстры, Г.Майерса, Р.Флойда, Ч.Хоара и др. Однако применение предложенных в этих трудах методов разработки и контроля качества ПО на практике при создании ПС ОАИ сталкивается со значительными трудностями. Как правило, с учетом указанных особенностей известные методы не гарантируют высокую эффективность процессов разработки высококачественных ПС ОАИ по таким критериям, как трудоемкость тестирования и отладки, достигнутые значения показателей корректности и надежности ПС (степени верификации, тестового покрытия, наработки на отказ). В конечном итоге это приводит к увеличению сроков разработки информационных систем с функциями обработки и анализа изображений и не позволяет обеспечить требуемые показатели качества ПО таких систем.
Таким образом, рассматриваемая в работе проблема повышения эффективности процессов разработки и контроля качества ПС ОАИ является весьма актуальной и обусловлена непригодностью или низкой эффективностью известных методов и средств разработки и контроля качества ПО с учетом специфики решаемых, плохо формализуемых задач и используемых алгоритмов обработки и анализа изображений.
Целью диссертационной работы является совершенствование известных и создание специализированных методов и средств, позволяющих повысить эффективность процессов разработки и контроля качества ПС ОАИ с учетом специфических особенностей решаемых, плохо формализуемых задач и
8 используемого алгоритмического обеспечения различных этапов обработки и анализа изображений.
Для достижения указанной цели в работе поставлены следующие основные задачи:
адаптировать известные и создать специализированные методы и средства разработки и контроля качества ПО, применяемые на этапах подготовки спецификаций, программной реализации, верификации, тестирования и отладки ПС ОАИ, учитывающие специфические особенности области приложения и позволяющие повысить эффективность процессов разработки и контроля качества ПС ОАИ;
апробировать и продемонстрировать применение предложенных методов и инструментальных средств в процессе разработки ПО системы технического зрения, на примере оптоэлектронной системы идентификации (ОЭСИ) объектов подвижного состава железнодорожного транспорта (ЖТ);
оценить влияние предложенных методов и средств на эффективность процессов разработки и контроля качества ПС ОАИ по критериям: трудоемкости тестирования и отладки, достигнутым значениям показателей корректности и надежности ПС (степени верификации, тестового покрытия, наработки на отказ).
Для решения поставленных задач использованы теоретические основы технологии разработки ПО, методы проектирования и анализа алгоритмов, теория верификации, тестирования и отладки программ, математический аппарат технологии обработки и анализа изображений, теория планирования в реальном времени и анализа последовательности событий, а также методы планирования научного эксперимента и обработки результатов экспериментальных исследований.
Научная новизна результатов работы состоит в следующем: 1. Предложен метод формализованного описания спецификаций алгоритмов и программных модулей (ПМ) ОАИ, включающий способ описания трудно формализуемых понятий при помощи формируемого экспертом массива "прецедентов", т.е. соответствующих пар вида "входная информация - выходная информация". Метод позволяет сформировать единые требования для этапов разработки и программной реализации алгоритмов решения плохо формализуемых задач обработки и анализа изображений при создании ПС ОАИ, а также существенно снизить трудоемкость фазы тестирования таких ПС за счет автоматизации процедур контроля качества.
Предложен метод поиска источника ошибки, выявленной на этапе тестирования в ПМ, реализующем эвристический алгоритм анализа изображений, основанный на "многоязыковой" реализации алгоритма, характерной при разработке ПС ОАИ, и сравнительном анализе результатов исполнения основной и вспомогательной программных реализаций алгоритма. Применение предложенного метода позволяет сделать процесс отладки таких ПМ более управляемым и сократить трудоемкость процедур отладки.
На основе классических методов Флойда и Хоара предложен способ верификации программ, позволяющий обосновывать корректность ПМ, содержащих подпрограммы, массивы и особые операторы, и соответственно повышать степень корректности ПС (степень верификации и тестового покрытия).
Предложен способ тестирования завершаемости циклических структур обработки массивов видеоданных и списков возможных решений, учитывающий специфику циклов ПМ ОАИ, позволяющий повысить качество создаваемых ПС ОАИ за счет увеличения степени надежности.
Практическая ценность работы заключается в следующем:
Синтезирована модель жизненного цикла (ЖЦ) ПС ОАИ, учитывающая особенности подобных программных средств. Даны практические рекомендации по выбору и применению методов и средств выполнения основных фаз жизненного цикла ПС ОАИ: подготовки спецификаций, программной реализации, верификации, тестирования и отладки.
Предложена методика обоснования конструктивной правильности ПМ, реализующего эвристический алгоритм.
Сформированы унифицированные системы формализованных спецификаций для основных ПМ ОЭСИ транспортных средств (ТС) и оптико-электронной системы контроля (ОЭСК) качества поверхности листового металлопроката, которые могут быть широко использованы при разработке алгоритмического и программного обеспечения подобных систем технического зрения.
Применение предложенных в работе методов и средств разработки и контроля качества ПС ОАИ детально продемонстрировано на примере проекта по созданию ПО ОЭСИ объектов подвижного состава ЖТ - ARSCIS. Даны практические рекомендации по формированию спецификаций качества и комплексной стратегии контроля качества, оценке сложности и достигнутого уровня качества созданного
10 ПС и ему подобных. Разработан набор тестовых классов, упрощающих процесс тестирования ПО ОЭСИ ТС.
Разработана открытая объектно-ориентированная архитектура (графическая модель, представленная средствами языка моделирования UML) ПО ОЭСИ объектов подвижного состава ЖТ. Архитектура обеспечивает возможности: подключения обновленных и дополнительных алгоритмов и оборудования без модификации и перекомпиляции всего ПС; адаптивной настройки алгоритмической и аппаратной подсистем в ходе функционирования ПС; сбора исторической информации, позволяющей повысить эффективность принятия решений в задачах обработки и анализа последовательности изображений. Архитектура может быть широко использована при разработке ПО систем контроля с функциями обработки и анализа изображений различного назначения.
Предложенные в работе методы и средства разработки и контроля качества ПС ОАИ используются в научно-производственной компании "Малленом" (г. Череповец) в качестве базовых при организации процесса разработки ПО ОЭСК различного назначения, что подтверждается актами о внедрении. При непосредственном участии автора на базе этой компании были созданы и внедрены следующие системы: ОЭСИ движущихся автотранспортных средств -ReCar (разработка выполнялась по заказу мэрии г. Череповца); ОЭСИ объектов подвижного состава ЖТ - ARSCIS (разработка выполнялась по заказу администрации ст. Череповец СЖД); оптоэлектронный дефектоскоп листового металлопроката (разработка выполнялась по заказу ОАО "Северсталь"). Указанные системы в 2005 г. удостоены дипломов I и II степеней Правительств г. Санкт-Петербурга и Вологодской области по итогам открытых конкурсов на лучшие инновационные научно-технические разработки и проекты.
Результаты исследований используются в учебном процессе ИМИТ СПбГПУ в рамках дисциплины "Обеспечение качества программных продуктов", в соответствующих разделах дисциплин "Технология разработки ПО" и "Компьютерная графика" для специальности 230105 - Программное обеспечение вычислительной техники и автоматизированных систем.
Основные положения диссертации докладывались и обсуждались на 13 научно-технических конференциях, выставках и конкурсах, по материалам диссертации опубликованы 17 печатных работ.
В структурном отношении работа состоит из введения, пяти глав, заключения, списка литературы и приложений.
В первой главе дается общая характеристика ПС ОАИ, как средств информационной поддержки в составе автоматизированных систем контроля и управления. Дана общая характеристика математического и программного обеспечения ПС ОАИ, применяемых в промышленном производстве, медицине, на транспорте и в охранной деятельности. Выявлены характерные особенности предметной области и ПС ОАИ, обуславливающие недостаточную эффективность процессов разработки и контроля качества подобных ПС. Среди указанных особенностей основными являются: существование трудно формализуемых спецификаций ПМ ОАИ; использование эвристических алгоритмов на этапах анализа данных; широкое применение разнообразных циклических структур, подпрограмм, особых операторов и массивов. Проведен анализ существующих систем и моделей обеспечения качества ПС, который показал, что такие системы и модели носят, в основном, организационный характер и применимы лишь на уровне менеджмента качества ПО. А применение конкретных методов разработки и контроля качества на практике при создании ПС ОАИ сталкивается со значительными трудностями, обусловленными специфическими особенностями области приложений. Обоснована актуальность проблемы повышения эффективности процесса разработки и контроля качества ПС ОАИ. Определена цель диссертационной работы, заключающаяся в совершенствовании известных и создании специализированных методов и средств, позволяющих повысить эффективность процессов разработки и контроля качества ПС ОАИ с учетом специфических особенностей решаемых, плохо формализуемых задач и используемого алгоритмического обеспечения различных этапов обработки и анализа изображений.
Во второй главе синтезирована модель ЖЦ ПС ОАИ, выбраны методы и средства, используемые на соответствующих фазах ЖЦ ПС ОАИ, учитывающие особенности разработки ПС ОАИ и гарантирующие высокое качество конструирования ПС ОАИ. На базе языков UML и OCL предложен принцип объединения фаз формализации спецификации требований и проектирования архитектуры ПС ОАИ, позволяющий ускорить процесс конструирования и сократить число дефектов, связанных с переходом "спецификация -» формальная спецификация -» архитектура". Предложен метод формализованного описания спецификаций алгоритмов обработки и анализа изображений, включающий способ описания трудно формализуемых понятий при
12 помощи формируемого экспертом массива прецедентов. Предложенный метод позволяет создавать системы формализованных спецификаций для широкого спектра ПС ОАИ и, соответственно, сократить дефекты неполноты, противоречивости и неоднозначности требований, а также автоматизировать процедуры контроля качества ПМ ОАИ. Процесс формирования экспертом массива прецедентов автоматизирован с помощью специализированного программного инструментария, позволяющего генерировать тестовые наборы значительной мощности. Предложен метод поиска источника ошибки в ПМ ОАИ, реализующих эвристические алгоритмы обработки и анализа изображений, учитывающий специфику ЖЦ ПС ОАИ и основанный на "многоязыковой" реализации алгоритмов и сравнительном анализе результатов их исполнения. Метод поиска источника ошибки позволяет сократить трудоемкость процесса отладки ПС ОАИ, реализующих эвристические алгоритмы анализа изображений.
В третьей главе на базе классических методов Флойда и Хоара предложен способ верификации программ, позволяющий обосновывать корректность ПМ (в том числе большинства ПМ ОАИ), содержащих подпрограммы, массивы и особые операторы и, соответственно, повышать степень корректности ПС (степени верификации и тестового покрытия). Сформированы практические рекомендации, учитывающие специфику реализации ПС ОАИ и повышающие эффективность механизма аналитической верификации ПМ ОАИ. Предложенные правила и рекомендации позволяют формировать корректные и непротиворечивые спецификации ПМ ОАИ; формировать необходимые и достаточные индуктивные утверждения Флойда и тройки Хоара для основных типов операторов, используемых в рамках ПС ОАИ; выбирать наиболее подходящие фундированные множества и ограничивающие функции для доказательства завершаемости ПМ ОАИ. Предложена методика подтверждения конструктивной правильности {(р)Р0{у/)к ПМ ОАИ, реализующих
эвристический алгоритм. Методика основана на декомпозиции исходного эвристического алгоритма в виде комбинации точных алгоритмов с четко формализуемыми спецификациями Ф{(р,у/) и позволяет использовать методы верификации для доказательства правильности построения и завершаемости ПМ ОАИ вида Р3. Предложен способ тестирования завершаемости циклических структур
обработки массивов видеоданных и списков возможных решений, учитывающий
13 специфику циклов ПМ ОАИ, позволяющий повысить качество создаваемых ПС ОАИ за счет увеличения степени надежности.
В четвёртой главе дано общее описание ОЭСИ объектов подвижного состава ЖТ -ARSCIS. Отмечено, что ARSCIS обладает всеми характерными чертами и отличительными особенностями информационной системы, создаваемой на базе технологии обработки и анализа изображений, базовую основу ПО которой составляет ПС ОАИ, выполняющее процесс идентификации железнодорожных вагонов, цистерн, платформ и т.п. путем распознавания их уникального регистрационного номера (РН). На основе предложенного в работе метода формализованного описания спецификаций построена унифицированная система формализованных спецификаций основных этапов процесса оптоэлектронной идентификации ТС. Созданная система формализованных спецификаций использована в процессе разработки ПО ARSCIS, что позволило сократить дефекты неполноты, неоднозначности и противоречивости требований, разработать эффективные алгоритмы и ПС ОАИ, используемые в процессе идентификации. В целях автоматизации процесса контроля качества ПО ARSCIS на базе предложенной системы спецификаций разработан ПМ, автоматизирующий процесс формирования массивов прецедентов значительной мощности. Разработана открытая объектно-ориентированная архитектура (графическая модель, представленная средствами языка моделирования UML) ПО ОЭСИ объектов подвижного состава ЖТ. Архитектура обеспечивает возможности подключения обновленных и дополнительных алгоритмов и оборудования без модификации и перекомпиляции всего ПС; адаптивной настройки алгоритмической и аппаратной подсистем в ходе функционирования ПС; сбора исторической информации, позволяющей повысить эффективность принятия решений в задачах обработки и анализа последовательности изображений. Архитектура может быть широко использована при разработке ПО систем контроля с функциями обработки и анализа изображений различного назначения. В соответствии с предложенными методами и средствами разработки и обеспечения качества ПС ОАИ создано ПО системы ARSCIS. Указаны стандарты, подходы и средства, применяемые в процессе построения ПО ARSCIS, позволившие достичь высокого качества процессов конструирования ПО. Оценена сложность полученного ПО ARSCIS. Выбраны процедуры контроля качества, позволившие обнаружить ряд критических ошибок и повысить качество ПМ ARSCIS. Реализован набор тестовых классов, автоматизирующих процесс тестирования ПО ОЭСИ ТС. С помощью теории
14 анализа последовательности событий и на основе результатов тестирования производительности подтверждено соответствие функционирования ПО ARSCIS режиму реального времени. Оценён достигнутый уровень качества ПО ARSCIS. Приведены результаты экспериментальных исследований, подтверждающие высокий достигнутый уровень качественных и количественных показателей качества ПО ARSCIS, соответствующий уровню, заданному в спецификации.
В пятой главе предложены методики оценки влияния разработанных методов и средств на эффективность процессов конструирования и контроля качества ПМ ОАИ, позволившие проверить и в итоге подтвердить преимущества предложенных методов и средств. Приведены результаты экспериментальных исследований по оценке влияния предложенных методов и средств на эффективность процессов разработки и контроля качества ПС ОАИ на примере проекта по разработке ОЭСИ ARSCIS. Результаты эксперимента позволяют сделать вывод о повышении эффективности процессов разработки и контроля качества ПС ОАИ по критериям трудоемкости тестирования и отладки, показателю корректности (степени верификации и покрытия тестами) и показателю надежности (наработка на отказ и коэффициент готовности). Приведены также результаты успешного применения предложенных решений в процессе разработки и контроля качества таких ПС ОАИ, как: ПО автоматизированной системы распознавания государственных регистрационных знаков автомашин и ПО ОЭСК качества листового металлопроката, подтверждающие их преимущества.
В приложениях представлены:
Краткое описание классических методов аналитической верификации программ и схема получения расширенной спецификации.
Классификация базовых характеристик качества ПС в соответствии со стандартом ISO 9126.
Пример поиска источника ошибки, выявленной в ПМ ОЭСИ ЖТ, реализующем эвристический алгоритм.
Примеры верификации ПМ ОЭСИ ЖТ с помощью предложенного способа доказательства корректности программ, базирующегося на методах Флойда и Хоара.
Пример верификации ПМ ОЭСИ ЖТ, реализующего эвристический алгоритм.
Пример тестирования завершаемости циклических структур, используемых в ПМ ОАИ.
Блок-схема алгоритма функционирования алгоритмической подсистемы ОЭСИ ТС.
Статическая модель ПО ARSCIS.
Динамическая модель ПО ARSCIS.
Алгоритмы определения планируемости смеси задач ПС в соответствии с теориями планирования в реальном времени и анализа последовательности событий.
Исходные данные, используемые в процессе оценки сложности проекта ARSCIS.
Диаграмма классов, используемых для тестирования ПО ОЭСИ ТС в соответствии со структурными критериями.
Схема нисходящего интеграционного тестирования ПМ ARSCIS.
Фрагмент спецификации требований к ПО ОЭСИ объектов подвижного состава ЖТ.
Определение требования на пропускную способность ПО ОЭСИ объектов подвижного состава ЖТ.
16.Показатели практичности, сопровождаемости и мобильности ПО ARSCIS.
Акты о внедрении предложенных методов разработки и контроля качества в производственный и учебный процессы.
Дипломы Правительств г. Санкт-Петербурга и Вологодской области за разработку оптико-электронных систем контроля.
На защиту выносятся следующие положения:
Метод формализованного описания спецификаций алгоритмов и ПМ ОАИ, оперирующих трудно формализуемыми понятиями, и унифицированная система формализованных спецификаций основных этапов функционирования ПО ОЭСИ ТС, созданная на базе предложенного метода.
Метод поиска источника ошибки в ПМ ОЭСК, реализующих эвристические алгоритмы обработки и анализа изображений.
Способ верификации программ, позволяющий обосновывать корректность ПМ, содержащих подпрограммы, массивы и особые операторы.
Способ тестирования завершаемости циклических структур, содержащихся в ПС ОАИ.
Открытая объектно-ориентированная архитектура (графическая модель, представленная средствами языка моделирования UML) ПО ОЭСИ объектов подвижного состава ЖТ.
Особенности математического обеспечения, используемого при разработке ПСОАИ
В настоящее время одним из перспективных направлений развития современной техники в таких областях человеческой деятельности, как промышленное производство, транспортные перевозки, медицина, охранное наблюдение и т.п. является создание средств информационной поддержки в составе автоматизированных систем контроля и управления. Указанные системы включают в себя как телекоммуникации, так и подсистемы сбора, обработки и анализа данных. При этом в качестве входного потока информации (или его части) широко используются изображения, т.е. данные, полученные с помощью приборного наблюдения (в основном, сканирования и фотографирования в различных диапазонах частот), соответствующих объектов или сцен. Примеры изображений, используемых в указанных системах и содержащих графические образы различных объектов контроля, представлены на рис. 1.1.
Как правило, изображения формируются с помощью оптических регистраторов (видеокамеры) и специализированных датчиков (тепловизоры, радиолокаторы, томографы, УЗИ аппараты) [16,44].
Благодаря появлению в последние годы достаточно мощных и доступных средств вычислительной техники в большинстве приложений стало возможно выполнять обработку и анализ входных изображений на базе ПЭВМ при помощи специально создаваемых ПС ОАИ. В качестве ПЭВМ в большинстве современных ПС ОАИ используются IBM-совместимые компьютеры под управлением операционной системы семейства Windows [50,63].
Как указано выше, ПС ОАИ используются в качестве средств информационной поддержки в составе автоматизированных систем контроля и управления процессами в различных областях хозяйственной деятельности человека. К примеру, в промышленном производстве ПС ОАИ используются для получения различных статистических характеристик выпускаемых изделий, что позволяет оперативно получать информацию о текущем состоянии технологического процесса для эффективного решения задач управления. В качестве примера можно привести ПО автоматизированной системы контроля качества поверхности листового металлопроката [95]. В области здравоохранения и медицины ПС ОАИ используются в составе систем диагностики и профилактики широкого спектра заболеваний по изображениям, получаемым с помощью средств томографических и ультразвуковых исследований [54,78].
Все более востребованной становится технология обработки и анализа изображений при организации процесса контроля на транспорте и в охранной деятельности. К примеру, на транспорте ПС ОАИ используются для решения задач, связанных с оперативным контролем передвижения наземных ТС [92]. К таким задачам относятся: слежение за прохождением ТС через контрольно-пропускные пункты (посты ДПС, проходные предприятий, стоянки, весовые и погрузочно-разгрузочные терминалы, посты списывания и т.п.), решение задач контроля доступа в системах безопасности разного уровня, при диагностике противоправных действий и раскрытии преступлений, совершаемых при помощи ТС. При организации охранного наблюдения ПС ОАИ обеспечивают выявление и классификацию движущихся объектов (люди, машины, животные) в области контроля, а также позволяют осуществить анализ их движения, выявление оставленных предметов, идентификации людей и т.п. В этом случае ПС видеоконтроль приобретает особую значимость в рамках совершенствования антитеррористической деятельности в нашей стране и во всем мире.
Входной информацией большинства типовых ПС ОАИ является изображение рабочей сцены, возникающей в области контроля. Как правило, входное изображение в памяти ПЭВМ представляется в виде матрицы Мт1Я, где п,т - число сірок и столбцов матрицы (рис. 1.2). Элементами матрицы (точки изображения) являются целые числа, принадлежащие диапазону [0,N], то есть V/,y (l / п), (1 j m): Му е[0;ЛП, где ЛГ = 2 -1 - число уровней яркости.
В основе математического обеспечения ПС ОАИ используется технология обработки и анализа изображений, теория распознавания образов совместно с методами принятия решений. Задача разработки математического обеспечения обработки и анализа изображений заключается в синтезе эффективных вычислительных алгоритмов и процедур для различных этапов обработки данных, среди которых основными являются следующие: - предобработка входного изображения, включающая процедуры фильтрации и восстановления изображений и выполняемая в целях улучшения качества изображения; - препарирование изображения в целях выделения отдельных элементов изображения (краев объектов, однородных областей, текстур и т.п.); - сегментация изображения в целях выделения и описания примитивами отдельных объектов на обрабатываемом изображении; - классификация выделенных элементов изображения и распознавание графических образов представленных на изображении объектов. В ПС ОАИ указанные этапы осуществляются в определенном объеме на том или ином уровне (применительно ко всему изображению или к его предварительно выделенным отдельным областям).
Метод и средства формализации спецификаций ПС ОАИ
Процессы проектирования, реализации и тестирования ПС ОАИ осуществляются на основе спецификации требований. В практике программирования принято составлять спецификации в виде набора требований, выраженных с помощью естественного языка. Как правило, такие спецификации содержат дефекты противоречивости, неполноты и неоднозначности требований, оказывающие негативное влияние на качество конструирования ПС уже на начальных стадиях ЖЦ ПО.
Преобразование спецификации требований к формальному виду - формализация спецификации, позволяет устранить перечисленные проблемы, автоматизировать процедуры контроля качества, ускорить процесс разработки и повысить общее качество ПО. В общем случае, формальная спецификация имеет вид Ф{(р, у/), где р -предусловие ПМ (входной предикат), характеризующее области значений входных переменных программы, у/ - постусловие ПМ (выходной предикат), определяющее области значений выходных переменных и их взаимосвязь с входными переменными.
Формализация требований осуществляется с помощью языков формальных спецификаций (в дальнейшем языки спецификаций). Языки спецификаций базируются на одном из методов описания семантики: табличный, алгебраический (операционная, денотационная семантика), логический (аксиоматическая семантика) и графический методы [1]. К современным и многофункциональным языкам спецификаций, базирующимся на указанных методах описания семантики, относятся такие языки, как: MSC, RSL, SDL, UML, VDM, Z [59,68].
В общем случае, каждый из языков спецификаций обладает определенными преимуществами и уникальными особенностями, обуславливающими их успешное применение в целях формализации требований к программным системам определенного класса. Однако, только лишь язык UML является стандартом де-факто в области конструирования ПС и обеспечивает эффективное построение архитектурных концепций на базе графического подхода, доступного для понимания широкого круга пользователей. С другой стороны, для формализации спецификации требований к ПМ может быть использован язык объектных ограничений OCL (object constraint language) [31,51], поддерживаемый UML нотацией. Эффективность применения языка OCL для формализации требований к ПС ОАИ обусловлена поддержкой логического метода описания семантики, необходимого для построения системы формальных спецификаций ПМ ОАИ; доступностью широкому кругу разработчиков, не обладающих серьезной подготовкой в области математической логики; возможностью формализации инвариантов, пред- и постусловий.
Следовательно, использование связки языков UML и OCL позволяет объединить этапы формализации и проектирования ПС ОАИ в единый процесс. Это обеспечит полную и точную формализацию требований спецификации и архитектурных решений, а также ускорит процесс конструирования ПС ОАИ. Предложенный принцип объединения позволит исключить промежуточный язык спецификаций и поэтому сократить число дефектов, связанных с переходами вида "спецификация - формальная спецификация -» архитектура". Использование связки языков UML и OCL для формализации и проектирования позволит осуществить более качественное и эффективное построение архитектурных моделей ПС ОАИ, инкапсулирующих формальные спецификации алгоритмов обработки и анализа изображений необходимых для последующей автоматизации механизма контроля качества ПС ОАИ.
Предложенный принцип объединения этапов формализации и архитектурного проектирования приводит к соответствующему изменению части модели ЖЦ ПС ОАИ, представленной на рис.2.2.
Как демонстрирует представленная схема ЖЦ ПС ОАИ, особенностью конструирования является построение спецификаций ПМ на основе спецификаций двух типов: спецификации алгоритмов и спецификации интерфейсной части методов и классов, которые реализуют заданные алгоритмы. Данная особенность построения спецификаций ПС ОАИ объясняется тем, что, как правило, формализацией требований и проектированием архитектуры занимаются роли системного аналитика и программиста, а за разработку и формализацию алгоритмического обеспечения отвечает роль математика. Таким образом, спецификация ПС ОАИ формируется на основе объединения спецификации классов и спецификации алгоритмов.
Реализация ПС ОАИ осуществляется в соответствии с предложенными на языке UML архитектурными моделями, на основе синтезированной OCL спецификации и описания алгоритмов, представленных псевдокодом или блок-схемами.
В качестве примера построения формальной спецификации ПС ОАИ рассмотрен фильтр Робертса, применяемый для выделения границ и последующей локализации объектов контроля. Спецификация интерфейсной части метода, реализующего фильтр Робертса в стандарте языка C++, задается сигнатурой вида:
Верификация ПМ, содержащих массивы
Массив представляет собой составной тип данных, используемый в языках программирования и объединяющий наборы данных одного типа. Доступ к элементам массива осуществляется по индексу или указателю. Например, если М одномерный массив, то эквивалентные операции доступа (в стандарте "C++") по индексу и указателю имеют вид МЩ = (М + Ї), где / - смещение внутри массива. Массивы широко используются в ПС ОАИ для хранения видеоизображений, исторической информации и результатов вычислений, осуществляемых в рамках технологии обработки и анализа изображений. Особенность представления видеоизображений в ПЭВМ заключается в том, что кадр представляет собой линейную последовательность байт- одномерный массив размером пхт элементов, где п - число столбцов, т - число строк кадра. Для доступа к элементу, расположенному в /-ой строке и у-ом столбце кадра, используются инструкции вида M[i п + у] = (М + /и + у). Одной из разновидностей динамических массивов, используемых в ПС ОАИ, являются вектора (например, вектора из библиотеки STL языка C++). Доступ к элементам вектора может осуществляться как по индексу (vector [і] ), так и по итератору (vector int :: iterator, iterator).
Большинство ошибок в ПМ (в том числе ПМ ОАИ), использующих массивы или вектора, связано с выходом индексов, указателей или итераторов за пределы областей памяти, выделенных массивам. Поэтому в процессе доказательства частичной корректности {(р}Р{у/) программ, содержащих массивы, важно проверить принадлежность значений, принимаемых индексами (указателями или итераторами) действительным областям памяти13. Например, при работе с изображением размерностью пхт, необходимо доказать истинность утверждений вида 0 [i-n + j] n-m-l, М рМ М + п-т-1 (для линейного массива), (0 / т-1)л(0 у л-1) (для двумерного массива), vector, begin () iterator vector.end ()-1 (для вектора), где рМ - указатель на кадр, vector - имя объекта типа вектор, iterator - указатель на элемент вектора. Способ верификации программ, основывающийся на методе Флойда и позволяющий производить доказательство частичной корректности {ср}Р{у/} программ, содержащих массивы, включает следующие дополнения к этапам метода Флойда:
Дополнение ко второму этапу метода Флойда. Каждому оператору, в котором содержится обращение к элементам массива (оператор с доступом к элементам массива), 1т ставится в соответствие утверждение Кк(х) (рис.3.4), задающее принадлежность индексов массиву, где л: - вектор индексов или указателей.
Дополнение к четвёртому этапу метода Флойда. Исходное множество условий верификации Флойда дополняется условиями верификации для операторов с доступом к элементам массива вида Is(v) л Ra.(v) = KL (Ta,(v)), где а - часть базового пути a:S -» С из точки S до оператора lm .
Дополнение к пятому этапу метода Флойда. Для доказательства корректности доступа к элементам массива (отсутствие выхода индексов за границы массива) необходимо доказать истинность условий Is(v)ARa,(v)= К,т(Та,(у)). Если все указанные условия истинны и начальное состояние памяти сги удовлетворяет предусловию # (сг„) = / программы Р, то это гарантирует корректность операций доступа к элементам массива.
В формализованном виде свойство завершаемости программы Р можно описать следующим образом. Пусть с = (сг,/) - конфигурация программы Р, где а -состояние памяти, a leL - метка, указывающая на следующий оператор подлежащий выполнению. Вычислением программы Р называется конечная или бесконечная последовательность конфигураций я = с0,...,с„,.... Пусть val(x) - состояние памяти в последней конфигурации, если я конечно и в сп находится метка завершающего оператора. Если я бесконечно, то va/(;r) = со, где со обозначает неопределенное состояние. Функция значения M[P](cr) = val(n(P,cr)) определяет соотношение между переменными в начальной и завершающей конфигурациях. Пусть вычисление программы Р состоит из п конфигураций, тогда программа Р завершается при начальном состоянии о-,,, если М[Р](ап) = ап со и программа Р не завершается (зацикливается) если М[Р]( ти) = со.
В [43] отмечены две причины, влияющие на свойство завершаемости программы Р: исполнение бесконечного числа итераций в некоторой циклической структуре (зацикливание) и исполнение инструкции, в которой осуществляется обращение к частично определенной функции со значением аргумента вне его области определения (что эквивалентно описанным в первой главе особым операторам).
Как правило, к особым операторам относятся операторы присваивания или ветвления, в которых осуществляется вычисление выражения, задающего частично определенную функцию. ПС ОАИ достаточно активно используют подобные операторы. В качестве примера можно привести оператор присваивания, правая часть которого представляет собой выражение, с помощью которого осуществляется линейное контрастирование изображения. Подобная инструкция на языке "C++" записывается в следующем виде: BYTE vai = 255-( pbuf-min)/(max-min), где min,max - минимальная и максимальная яркость точек данного изображения, pbuf - указатель на изображение. Функция, задаваемая данным выражением, имеет разрыв в точке min = max (в случае однотонного изображения), а область определения функции, задаваемой данным выражением, описывается предикатом cp(phuf, min, max): ( pbuf, min, max є [0;255]) л (min max), где pbuf - яркость точки изображения. Попытка выполнить особый оператор с аргументами, соответствующими точке разрыва, приведет к его не завершению и появлению ошибки времени выполнения (деление на ноль) и затем, либо к аварийному сбою, либо к вызову механизма обработки исключений.
Унифицированная система формализованных спецификаций ПМ ОАИ для системы ARSCIS
Унифицированная система формализованных спецификаций ПМ ОЭСИ ТС, на основе которой разработано алгоритмическое обеспечение, программно реализованы ПМ ОАИ в составе ПО ARSCIS и автоматизированы процедуры контроля их качества, имеет вид: 1) Видеозахват и предобработка. р\ s(r,t) = p-S(r-r0)-S(t0) у/: Mnxm=Fnped(s(},t)): (и,/и 0) л (VA/tf (0 і #1) л (О S./ їй) MtJ є[0;255]), s(r,t) - аналоговый видеосигнал в виде функции яркости, р = \\s{r,t)drdt нормирующий множитель, г = (x,y,z),r0 = (x0,y0,z0),S(r) = S(x)-S(y)-S(z), М„хт -двумерный массив размерности пхт (кадр) значение каждого элемента которого (интенсивность яркости точек) принадлежит интервалу [0;2 -1], в случае полутоновых изображений / = 8. Алгоритмы первого этапа представлены функцией Fnpei), которая включает процедуры оцифровки и улучшения качества изображения.
Оцифровка сигнала проходит в два этапа: дискретизация - умножение непрерывного сигнала на пространственную дискретизирующую функцию к=со /-00 f(x,y)= S(x-k-Ax,y-l-Ay), где Ах,Ау - величины дискретизации, и 4=-00 /=-00 квантование - преобразование непрерывного диапазона яркостей [0,S] к последовательности дискретных величин iS", расположенных на равных интервалах AS. Задача видеозахвата и предобработки в полной мере формализуема. 2) Обнаружение движущегося ТС. р: М = Мпхт y,f: b = Fo6ll(M):be{t,f} е: Ье=Еобн(М): bee{t,f} \М, be = t w = y/ оууе: b = be, М: М = \ [NULL, Ъе = /, М - входное изображение; F0(jH - алгоритм обнаружения ТС; b - признак присутствия графического образа ТС на изображении; Еобн - процедура принятия экспертом решения о наличии графического образа ТС на данном изображении; Ъе - терм, формируемый экспертом, характеризующий присутствие изображения ТС на данном кадре; t,f - истина, ложь. Постусловие этапа обнаружения движущегося ТС является трудно формализуемым ввиду отсутствия формального описания кадра, содержащего изображение ТС. Задача эксперта при подготовке массива прецедентов состоит в выявлении графического образа ТС на изображении и сопоставлении с данным кадром терма b3, принимающего значение истина при наличии ТС и значение ложь при отсутствии графического образа ТС на изображении. Решение алгоритма обнаружения должно совпадать с экспертной оценкой для кадра b = be, и в случае отсутствия графического образа ТС на изображении на выходе алгоритма должен быть признак "NULL", иначе на выходе алгоритма должно изображение идентичное входному. kMK - максимальное число областей локализации; FWK - алгоритм локализации областей РН; Vo6:l - список областей локализации; v(xx,yx,x2,y2) - элемент из Кой7, содержащий координаты локализованной области; wx,w2 - ограничения на ширину области; hx,h2 - ограничения на высоту области; Елок - процедура выделения экспертом всех областей в кадре, содержащих изображения отдельных РН ТС; V"Cn -список областей, формируемый экспертом, каждый элемент которого содержит изображение отдельного РН ТС; сюк - порог соотношения площадей, задаваемый экспертом; 5 = ( - ,+1)-( 2- ,+1) - площадь локализованной области. Предикат Р задаёт геометрическую принадлежность области локализации к области кадра и ограничения на допустимые размеры области, а Рх характеризует геометрическую принадлежность соответствующих областей и соотношения их площадей. Постусловие этапа локализации РН ТС трудно формализуемо, так как нет математического описания области, содержащей изображение РН. Задачей эксперта при подготовке массива прецедентов является формирование экспертного списка V n путём выделения на заданном кадре минимальных по площади областей, каждая из которых должна содержать изображение отдельного РН. При этом алгоритм локализации должен формировать такой список областей Уойл, чтобы изображение любого элемента из Уобл включало в себя изображение отдельного элемента из списка областей V 6l, выделенных экспертом, и его площадь не превышала площади экспертно выделенной области более чем в слок раз.
4) Классификация областей по степени схожести с РН ТС. р: М Мтт, Vo6.4:VveVoa, P(v) у,: P.[1 K ]: V/(l / rJ) (Р,[/]Є[0,1])А(3!У/ЄКОЙ!: РК[І] = FKiacc(M,Vi)) е- 5e[l..f„6l] = :tracc(M,Fofi,), ре: (0 ре 1)A(V/(1 / Fofl7) Be\i]e{t,f}) = fyse: Уобл,Рк: Уі(\ і \Уоб1\) (й(И=/оР,И ()лад = /«Р,И А), Pk[] - массив степеней схожести изображения области локализации с изображением РН ТС; FKWCC - алгоритм классификации областей локализации; Екюсс - процедура ранжирования экспертом изображений областей локализации по степени схожести с изображением РН ТС и отсечения шумовых кандидатов; Ве[] - массив булевых переменных, формируемый экспертом, однозначно сопоставляемый со списком областей локализации. Если значение некоторого элемента массива Ве[] истина, то область, с которой однозначно сопоставлен данный признак, содержит изображение РН ТС, в противном случае, область не содержит графический образ РН ТС. Экспертный порог ре служит для разделения классов областей, содержащих и не содержащих изображения РН. Постусловие этапа классификации является трудно формализуемым, так нет формального описания области, содержащей изображение РН ТС. На этапе классификации эксперт анализирует изображения областей локализации и сопоставляет с каждой областью соответствующий признак из Ве[]. В свою очередь, алгоритму классификации необходимо сформировать такой массив степеней схожести Рк[] для списка Уобч, что для каждой области, помеченной соответствующим экспертным признаком из Ве[] со значением истина, степень схожести не должна быть ниже заданного порога ре. Предполагается, что степень схожести тем больше, чем выше точность локализации РН. Процесс построения массива прецедентов для этапа классификации в значительной мере может быть автоматизирован за счёт использования информации, полученной на этапе локализации.
Похожие диссертации на Методы разработки и контроля качества программных средств обработки и анализа изображений
