Содержание к диссертации
Введение
1. Методы и алгоритмы выделения контуров на изображениях 14
1.1. Обзор алгоритмов выделения контуров 14
1.2. Показатели качества контурных детекторов 45
1.3. Сравнение систем с несколькими показателями качества 48
1.4. Постановка задач исследования 51
1.5. Выводы 52
2. Формирование одноуровневых марковских полей 53
2.1. Теория выбранного класса мозаичных изображений 53
2.2. Получение алфавита мозаик 54
2.3. Получение описания условных вероятностей 55
2.4. Методика моделирования мозаичных полей 56
2.5. Динамика марковского поля 58
2.6. Обсуждение результатов моделирования 62
2.7 Выводы 63
3. Разработка критериев оценки качества алгоритмов оконтуривания 64
3.1. Показатели качества выделения контурного рисунка изображения 65
3.2. Оценка схожести контурного вектора с растровым изображением 67
3.3. Оценка толщины контура 74
3.4. Оценка средней длины разрывов контурного рисунка 81
3.5. Оценка сложности алгоритмов получения контурного рисунка 87
3.6. Оценка смещения контурного рисунка 96
3.7. Обобщённый количественный критерий оценки качества алгоритмов оконтуривания 98
3.8. Методика расчёта доверительных интервалов полученных значений количественного критерия оценки качества алгоритмов оконтуривания 99
3.9. Выводы 101
4. Программный комплекс для исследования алгоритмов оконтуривания объектов в изображениях 102
4.1. Краткое описание программного комплекса системы тестирования алгоритмов оконтуривания областей в изображениях 102
4.2. План эксперимента по тестированию алгоритмов оконтуривания. Функции частей программного комплекса 106
4.3. Обсуждение результатов эксперимента по оценке эффективности алгоритмов оконтуривания, рекомендации по их использованию 113
4.4. Обсуждение направлений возможных исследований алгоритмов оконтуривания на разработанном программном комплексе 119
4.5. Выводы 121
5. Применение разработанных методов и алгоритмов при моделировании аэрокосмических изображений местности и в задачах дефектоскопии полимерных и металлических конструкций 122
5.1. Анализ применения разработанных алгоритмов при синтезе аэрокосмических изображений 122
5.2. Принципы работы систем телевизионной бестраншейной диагностики трубопроводов 135
5.3. Результаты применения разработанных алгоритмов в задачах дефектоскопии полимерных и металлических конструкций 139
5.4. Выводы 151
Заключение 154
Список литературы 156
- Сравнение систем с несколькими показателями качества
- Получение описания условных вероятностей
- Оценка схожести контурного вектора с растровым изображением
- План эксперимента по тестированию алгоритмов оконтуривания. Функции частей программного комплекса
Введение к работе
Актуальность работы и состояние вопроса
В настоящее время большой круг научно - технических задач связан с представлением информации в виде изображений. Изображения являются одновременно результатом и объектом исследований в космонавтике, геологии, картографии, биологии, медицине, навигации, дефектоскопии и во многих других областях человеческой деятельности.
Алгоритмы оконтуривания границ объектов на любых разновидностях двумерных сигналов являются необходимым инструментом для решения различных прикладных задач, связанных с их редактированием, анализом, синтезом, восстановлением или сжатием. Хотя в настоящий момент уже разработано большое число таких алгоритмов, возникают вопросы выбора и оптимизации, подбора параметров и адаптации алгоритмов к определённой предметной области. Возникают вопросы, связанные с субъективной и объективной оценкой качества выбранного алгоритма с целью получения удовлетворительного конечного результата. Существующие в настоящее время подходы к решению указанных задач проводятся с привлечением специалистов определённой предметной области. Полученные оценки, результаты и рекомендации зачастую носят субъективный характер и не могут быть использованы для решения задач в других предметных областях. Избежать этого можно с помощью введения показателей качества работы существующих алгоритмов обработки двумерных сигналов.
Важными факторами, влияющими на точность и помехоустойчивость оптических систем, являются статистические характеристики используемых изображений. Они, в свою очередь, зависят от статистических свойств местности, характеристик датчиков и регистрирующих систем. Поэтому при проектировании соответствующих комплексов, формировании базы данных изображений и т. д., необходимо учитывать ряд факторов, характеризующих местность и условия её наблюдения, использовать те алгоритмы обработки сигнала, которые в данной ситуации дают наилучшие результаты. Сложность этих процессов такова, что их исследование аналитическими методами, позволяющими наиболее глубоко проникнуть в физику явлений, доступны лишь специалистам высокой квалификации, очень трудоёмки и не всегда могут быть доведены до конца. Экспериментальные исследования слишком дороги, ограничены в возможности проведения факторного анализа и в конечном итоге основаны на субъективных оценках. Компьютерное моделирование является разумной альтернативой натурному эксперименту, имеет ряд преимуществ: позволяет проводить быструю проверку гипотез, упрощать выкладки, осуществлять детальный анализ полученных результатов, по сравнению с другими методами, позволяет рассматривать гораздо большее число альтернатив, улучшать качество предмета исследования и точнее прогнозировать последствия. Проведение факторного анализа, повтора экспериментов, при использовании цифрового моделирования не вызывает больших затруднений. В данной работе рассмотрены вопросы оценки качества получения контурных рисунков изображений на основе сравнения трёх различных алгоритмов оконтуривания. Для анализа используются двумерные сигналы, полученные при помощи двумерного одноуровневого марковского поля, подверженного воздействию аддитивной шумовой составляющей с нормальным законом распределения. Описана методика проведения подобных исследований (тестирований). Выполнена оценка качества работы контурных детекторов с использованием объективных метрик, проведено визуальное сравнение и анализ полученных результатов.
Объект исследования:
Системы мониторинга земной поверхности и навигации, в которых наблюдение ведётся в оптическом диапазоне.
Геоинформационные системы, предназначенные для проведения картографирования.
Оптические системы по выделению контекстуальной информации.
v Системы измерения параметров повреждений и деформаций полимерных и металлических конструкций при их эксплуатации.
Предмет исследования:
Исследование возможности использования марковских полей для решения задачи тестирования алгоритмов оконтуривания.
Определение устойчивости марковского поля в алгоритме генерации мозаики с расширенным набором контурных элементов.
Эффективность выделения контурного рисунка при обработке изображения различными видами контурных детекторов.
v Влияние аддитивного гауссовского шума на эффективность выделения контурного рисунка.
* Определение границ применимости различных видов контурных детекторов и квазиоптимальных
значений их параметров.
Цель работы
Создание комплекса программ, позволяющего проводить сравнительный анализ алгоритмов оконтуривания объектов в изображениях, аппроксимированных марковскими полями, в присутствии аддитивного нормального шума. Разработка критериев оценки качества оконтуривания и рекомендаций по выбору алгоритмов оконтуривания для конкретных приложений.
Для достижения сформулированной цели были поставлены следующие задачи:
Создать комплекс программ, позволяющий:
формировать одноуровневое марковское поле с определёнными морфологическими и статистическими свойствами,
формировать растровое изображение на основе векторного описания марковского поля и введения шумовой составляющей с нормальным законом распределения и заданным отношением сигнал/шум (с/ш),
тестировать алгоритмы оконтуривания, вычислять обобщённый критерий качества,
проводить анализ данных, формировать статистику получаемых результатов, проверять и подготавливать данные для дальнейшей обработки и визуализации.
Методы исследования
Решение задач исследования проводилось с применением теории случайных процессов, методов математической статистики, теории матричного исчисления, теории погрешностей, методов имитационного моделирования, а также методов планирования численных экспериментов. Разработка ПО и исследование предлагаемых алгоритмов выполнялись с использованием пакетов Khoros 2.2/2001, Borland C++ Builder, Delphi 7.0, Mathcad, библиотеки языка FORTRAN, систем управления версиями на основе CVS 2.1, ECLIPSE 3.4 и анализа кодов Together 6.0.
Научная новизна:
впервые предложена цифровая имитация изображений для решения задач оконтуривания на основе марковского поля;
получен новый алгоритм моделирования мозаичных случайных полей, позволяющий контролировать их морфологические, вероятностные и корреляционные свойства, структура контурного рисунка которых имеет не только горизонтальные и вертикальные, но и диагональные составляющие элементы;
создан комплекс программ для формирования имитационных двумерных сигналов- изображений. В основе моделирования используются алгоритмы построения случайных одномерных марковских полей с различной морфологией и вероятностными и свойствами генерируемого поля. Осуществлён
принципиально новый подход к решению подобного рода исследовательской проблемы, позволяющий вносить вероятностный фактор в процесс исследования, а также проводить факторный анализ эксперимента;
* впервые предложены критерии оценки качества оконтуривания, учитывающие толщину контурного
рисунка, величины схожести и средней длины разрывов.
Практическая значимость работы:
В рамках решения задачи моделирования марковского поля исследована методика использования полного алфавита, состоящего из 248 возможных элементов. Проверена возможность формирования мозаичного поля и получения векторного описания контурного рисунка для типов мозаик известных ранее (работы А.Г. Буймова). На основе полного алфавита получены новые типы контурного рисунка, построение которых было принципиально невозможно при использовании ограниченного алфавита.
В целях исследования динамики марковских полей, моделируемых на основе полного алфавита, состоящего из 248 возможных элементов, проведено исследование вопросов устойчивости управляющего пальмовского поля для отдельных реализаций.
Предлагаемая автором методика тестирования алгоритмов оконтуривания на основе векторного описания марковского поля позволят проводить объективную оценку качества полученного результата. Получена уникальная возможность проводить факторный анализ с целью выявления закономерностей детектирования конкретных формирующих элементов.
Определена совокупность показателей качества детектирования; введён обобщённый критерий качества.
Показано влияние аддитивной гауссовской помехи и морфологии поля на качество оконтуривания.
Выработаны рекомендации по применению различных видов контурных детекторов и их квазиоптимальных параметров.
Модули комплекса программ применены для тестирования оборудования, используемого для измерений параметров повреждений и деформаций полимерных и металлических конструкций при их эксплуатации. Внедрение подтверждено соответствующими актами.
Модули комплекса программ применены для настройки и доводки комплексов программного обеспечения оборудования дефектоскопии. Внедрение подтверждено соответствующими актами.
Модули комплекса программ использовались в целях имитации аэрокосмических изображений земной поверхности для проведения статистических исследований корреляционно- экстремальных систем (КЭС).
Модули комплекса программ использовались в системе имитационного моделирования аэрокосмических снимков (СИМАКС).
Достоверность и обоснованность результатов
Полученные в диссертационной работе теоретические результаты и формулируемые на их основе выводы обеспечиваются строгостью математических выкладок, базирующихся на аппарате теории случайных процессов, методов математической статистики, системного анализа, теории матричного исчисления, теории объектно- ориентированного анализа и объектно- ориентированного программирования, теории погрешностей, а также методов планирования численных экспериментов. Справедливость выводов относительно эффективности предложенной системы подтверждена статистическим моделированием, обработкой реальных изображений, рядом успешных внедрений в производство.
На защиту выносятся следующие научные положения:
разработанный алгоритм генерации одноуровневых марковских полей на основе расширенного набора контурных элементов является устойчивым и позволяет получать структуру контурного рисунка не только с горизонтальными/вертикальными, но и с диагональными составляющими;
использование одноуровневых марковских полей для получения двумерных растровых изображений позволяет устранить субъективность оценки эффективности работы контурных детекторов;
разработанная система тестирования позволяет проводить факторный анализ с целью выявления закономерностей детектирования конкретных формирующих элементов;
двумерные марковские поля позволяют имитировать структуру квазиреальных геофизических полей земли;
векторное представление контурного рисунка позволяет существенно (на порядок) повысить скорость вычисления оценки качества контурного детектора.
Апробация работы
Результаты диссертационной работы докладывались на шести международных [3, 4, 6, 7, 9, 10] и двух [2, 8] всероссийских научно- технических конференциях. Метод построения марковских полей был использован для создания комплексов программного обеспечения оборудования дефектоскопии полимерных и металлических конструкций при их эксплуатации. Ряд материалов диссертации был задействован для реализации комплекса СИМАКС, а также для проведения статистических исследований КЭС.
Личный вклад:
Постановка задач исследования и разработка концепции программного комплекса для проведения сравнительного анализа алгоритмов оконтуривания объектов в изображениях.
Разработана методология тестирования алгоритмов оконтуривания изображений с использованием одноуровневых марковских полей.
Расширена методика построения одноуровневого марковского поля, изложенная в работах Буймова А.Г., Ильина СП., Сейфера В.А.; предложен обобщённый подход к построению марковского поля; разработан, отлажен и протестирован универсальный алгоритм построения одноуровневого марковского поля. Проведена проверка динамики всех полученных разновидностей морфологии (мозаики «А, С, D, F»). Накоплен необходимый объем тестового материала.
Сформулирована совокупность критериев качества получения контурного рисунка. Представлен обобщённый критерий качества. Проведены исследования эффективности критерия, получены рекомендации по его использованию.
Разработано и реализовано алгоритмическое и программное обеспечение комплекса для проведения сравнительного анализа алгоритмов оконтуривания.
Получены, обработаны, проанализированы результаты применения программного комплекса при решении задач измерений параметров повреждений и деформаций полимерных и металлических конструкций. Даны рекомендации по использованию алгоритмов оконтуривания и выбора их квазиоптимальных входных параметров.
Публикации.
По материалам диссертации опубликовано 13 работ: 2 статьи в журнале, рекомендованном ВАК, 8 публикаций в сборниках материалов международных и всероссийских конференций, 3 отчёта по НИР.
Объем и структура диссертации
Диссертационная работа состоит из введения, пяти глав, заключения, изложенных на 171 машинописных страницах, содержит 71 рисунок и 15 таблиц, а также включает список литературы из 134 наименований и ряд приложений (блок-схем, структурных схем, четырёх актов внедрения).
Сравнение систем с несколькими показателями качества
Как упомянул сам автор, этот метод является не чем иным, как разновидностью метода оценки, описанного в работе [61]. Palmer [63] представил метод оценивания системы в целом, на основе которой производилось детектирование границ построчно. Мерой эффективности вычислялась нелинейная комбинация констант, используемых в процессе вычисления контуров границ. Cho [64] использовал подход, позволяющий производить самонастройку алгоритма детектирования, исходя из апостериорных промежуточных результатов. Самонастройка производилась по типу получаемых граней. Все эти методы позволяют оценивать форму граней, вероятность обнаружения истинных границ, вычислять её локальные интенсивности или производят сравнение с искусственными эталонными изображениями, полученными на основе векторных операций. Принципиальное ограничение этих методов заключается в том, что они не позволяют измерить величины рассогласования местоположения граней и их качественные характеристики.
В связи с этим, они не отображают качество граней для любой решаемой задачи. По этой причине, в современных алгоритмах оконтуривания обрабатываемое изображение на первом этапе сглаживают перед проведением процесса поиска границ объектов. Тем самым устраняются возможные выбросы, шумовые всплески, которые имеют негативное влияние на последующие этапы детектирования границ. С другой стороны, необходимо понимать, что процессы сглаживания приводят к неправильной локализации самих границ, и их применение в некоторых задачах просто недопустимо. 1.3. Сравнение систем с несколькими показателями качества Любая техническая система S имеет какие-то характеристики, которые можно изменять, управляя набором параметров системы х = (х1,х2,х3,...хп). Её можно характеризовать совокупностью показателей качества системы к = (ki,k2,k3,...km). Показатель качества системы — числовая характеристика, которая связана с ее качеством строго монотонной зависимостью: чем больше (меньше) к,, тем лучше система при прочих равных условиях. В каноническом виде с уменьшением значения показателя качества система становится лучше.
Показатели качества системы зависят от параметров системы. Функции Fx,F2,...,Fm называют целевыми функциями. Изменение значения одного параметра системы может привести к изменению многих показателей качества. Если »7 = 1, то система характеризуется единственным показателем качества. В этом случае решается задача скалярного синтеза. Если техническая система характеризуется не одним, а двумя и более показателями качества, то для выбора лучшего решения необходимо решить задачу векторного синтеза. Задача векторного синтеза сводится к тому, чтобы из множества допустимых систем выбрать такую систему, которая обладает наилучшим значением вектора k. При этом предполагается, что понятие наилучший вектор к сформулировано математически. То есть, выбран соответствующий критерий предпочтения. При скалярном синтезе единственный показатель качества к позволяет всегда сравнивать разные системы. Например: если k(S") k(S ), то система 5" лучше системы S . если k(S") k(S ), то система S" хуже системы S . если k(S") = k(S ), то система 5" эквивалентна системе S . При векторном синтезе в ряде случаев это сделать нельзя. Особенность векторного синтеза заключена в том, что две системы могут быть несравнимы. Например, при т = 2 : если k(S ) = (2;15), k(S") = (2;Щ, то система 5" лучше системы 5". если k(S ) = (2;Щ, fc(S") = (4;10), то система 5" хуже системы S . если k(S ) = (2; 15), (5") = (4; 10), то система 5" несравнима с системой 5".
Системы 5" и S" сравнимы по вектору качества k=k(S), если выполняется одно из трех условий [65]: либо k(S") k(S ), либо k(S") k(S ), либо k(S№) = k(S ). Если ни одно условие не выполняется, то системы 5" и S" несравнимы по вектору к . Если выполняется векторное неравенство k(S") k(S ), то есть kt(S") k S ) для всех г = 1,т,в том числе хотя бы для одного значения номера / неравенство выполняется строго (то есть к, (" ) к, (5")), то система S" безусловно лучше системы S . Если же не выполняется ни одно из трех условий, указанных выше, то для сравнения систем необходимо ввести дополнительный (условный) критерий предпочтения. Существуют различные методы, основанные на применении условного критерия предпочтения. Наибольшее практическое применение получили: методы, основанные на введении результирующего показателя качества; минимаксный метод, перевод всех показателей качества кроме одного в разряд ограничений, метод последовательных уступок, комбинированные методы, основанные на комбинации нескольких условных критериев предпочтения. Если удается ввести единый результирующий показатель качества кр,
Получение описания условных вероятностей
При построении контуров используются условные вероятности P(fgh/abcde), полученные из формулы полной вероятности [71] Полученные значения P(fgh/abcde) являются элементами стохастической матрицы условных вероятностей Р размерностью 32x8. 2.4. Методика моделирования мозаичных полей Построение контурного рисунка начинается с создания опорных исходящих литер в первой строке и в первом столбце изображения. Левый верхний угол изображения считается началом отсчёта. Значение вектора {abode) для этого элемента не определено, а следовательно, выбор литеры при его построении производится случайным образом с учётом финальных вероятностей. Под значениями предельных или финальных вероятностей будем понимать значения а = а{,а2,ос3 ...,ап , получаемые из векторно-матричного уравнения (XinyY[in\ = cc,y На рис. 2.3 выделены серым цветом опорные задающие элементы, начало отсчёта обозначено крестом, стрелками обозначена координатная система. Генерация первой строки и первого столбца проводится по методике [69] с учётом изотропности появления любого возможного контурного элемента. Вероятности появления контурных лучей ра, рь, рс, Pd, Ре или вероятности их отсутствия qa, qb, qc, qd, Я.е вычисляются по формулам: После создания первой опорной строки и первого опорного столбца, производится построчное (слева на право, сверху вниз) прохождение узлов сопряжения контурных элементов.
Исходя из задающего, априорно известного бинарного вектора (abode), определяется результирующий вектор 57 (fgh). Эта процедура производится с учётом условий, накладываемых стохастической матрицей условных вероятностей. Заключающим этапом является занесение бинарной величины «Z», значение которой определено полным бинарным вектором (abcdefgh), в растр генерируемой мозаики. Рис. 2.4 поясняет геометрию проводимой генерации. Последующие итерации повторяются по приведенной выше схеме с учётом сдвига прямоугольного фрагмента в окрестности исследуемой области на одну точку в необходимом направлении. Преимуществом предлагаемого алгоритма является возможность моделирования мозаичного изображения с расширенным типом контурного рисунка. Эта возможность была достигнута за счёт ввода дополнительных элементов алфавита (рис. 2.1). Расширение базового алфавита позволило получать диагональные составляющие контурного поля, что является существенным достоинством предлагаемого алгоритма по сравнению с алгоритмами, приведёнными в работах [69,71].
Работоспособность алгоритма была проверена путем моделирования мозаик, полученных в работах [69, 70, 71]. Морфология контуров задавалась исключением одного или нескольких типов контурных элементов в соответствии с методикой, предложенной в работе [69]. Тип А является простейшей прямоугольной решеткой, построенной на основе элементов {0, 170, 34, 136}, рис. 2.5. Тип С образуется непересекающимися прямоугольниками разных размеров на основе элементов {0, 34, 136, 42, 138, 162, 168}. Тип D представляет собой многосвязные замкнутые области на основе элементов {0, 34, 136, 0, 40 130, 160}. Мозаика F получена на основе элементов {0, 17, 68}. В процессе реализации вышеописанной методики, использовались следующие источники [72-79]. В Приложении А приведена блок-схема алгоритма формирования марковского поля. 2.5. Динамика марковского поля Кратко рассмотрим математический аппарат дискретных марковских цепей [67, 69, 70, 80, 81]. В дальнейшем будем рассматривать простые, регулярные, однородные марковские цепи с дискретным временем. Отметим, что основным уравнением для дискретной марковской цепи является уравнение, с помощью которого определяется состояние системы на любом её к- м шаге. Это уравнение имеет вид: П [п] = Р п - П[и] , где Р „ - вектор начальных вероятностей, описывающий состояние системы на первом шаге, П[и]- матрица совокупности переходных вероятностей, элементами которой являются вероятности перехода из і- го в j- тое состояние за один шаг процесса. Это рекуррентное соотношение, позволяющее вычислить вероятность состояний марковского случайного процесса на любом шаге при наличии информации о предшествующих состояниях, известно под названием Колмогорова- Чепмена.
Оценка схожести контурного вектора с растровым изображением
Рассмотрим понятие величины схожести описания контурного рисунка с априорно известным, основополагающим описанием марковского поля построенного с учетом заданного типа морфологии мозаики и алфавита поля. Для начала введём ряд понятий позволяющих более детально подойти к восприятию понятия оценки схожести изображения. В результате проведения пороговой обработки контурного аппарата: SV(x,y) = \, g{x,y) T О, g(x,y) T где Т = f(x, у) — адаптивная величина порогового значения, SV{x, у) — растровое бинарное изображение, получается растровое бинарное описание контурного рисунка изображения. Двумерный массив значений SV{x, у) зависит от ряда исходных, входных параметров Р и от адаптивного порога Т = f(x, у). В дальнейшем будем производить запись SV(x, у) в виде SV{x,y,P) и понимать под этим трёхмерный массив. Изменение значений по Р позволяет производить адресацию значений бинарного изображения SV(x, у), исходя из совокупности исходных параметров Р =(G2,а ,...,/) оператора оконтуривания, использованных для его получения. Для проведения сопоставления описания границ контурного рисунка SV(x, у) с априорно известным описанием марковского поля v(j, і), кратко рассмотрим механизмы получения двумерного массива v(j, і) и введём понятия «совокупности исходных контурных векторов». Как известно в информатике, в частности в программировании, под понятием вектора понимается одномерный массив значений.
Причём, использование многомерного массива можно рассматривать как частный случай одномерного. На основании вышесказанного, для описания априорно известного, основополагающего марковского поля (координат точек задающих контуров), введём понятие исходной совокупности контурных векторов v(y, і). Понимая при этом v(y, Ї) — как двумерный массив значений, где размерность / - описывает количество точек отдельно взятого контурного вектора, а размерность j — индекс конкретного контурного вектора совокупности. Проводя адресацию значений массива С = v(y, і), для определённых /, и j, получаем структуру G . В этой структуре находится описание координат отдельно взятой точки контурного вектора и ряд других параметров необходимых в последующем для обработки. Длины JV. — отдельно взятых контурных векторов имеют различное количество составляющих точек а, следовательно, и различную длину. Поэтому, проводя реализацию оценки схожести, я отказался от жёстко заданных двумерных массивов значений v(y, і). Двумерный массив был заменён одномерным динамическим массивом размерностью М (количество контурных векторов), элементами которого являются связанные списки значений структуры G . Каждый список имеет различную длину Nj и включает в себя описание последовательности точек отдельно взятого у-то контурного вектора рис. 3.1. Рассмотрим математическое представление описания исходной совокупности контурных векторов v(y, /). Под записью v(y, i).X будем понимать значения координат по оси х отдельно взятой /-ой точки в у—том контурном векторе. Аналогично, v(y, і). Y означает значения координат по оси у отдельно взятой /-ой точки в у -ом контурном векторе.
Величина схожести совокупности контурных векторов определяется в процессе адресации координат точек всех контурных векторов в структуре данных v(y, і) и проверкой наличия контура в массиве значений 8У(х ,у ,Р), при фиксированном P = Тем самым, производится объективное сопоставление описания границ получаемого в процессе выделения контурного рисунка SV(x, y)L0 с априорно известным, основополагающим описанием марковского поля. Результат рассчитывается исходя из соотношения: где: F - величина схожести при фиксированном значении совокупности параметров Р исследуемого оператора оконтуривания, SV{xji,yji,P) — растровое бинарное изображение контуров, полученное в результате проведения пороговой обработки контурного аппарата g(x,y), v(j,i)— структура данных содержащая исходную совокупность контурных векторов, у-индекс контурного вектора совокупности, і — индекс точки в у -том контурном векторе, N — длина у—го контурного вектора, М — количество контурных векторов, Р = ( G2, а ,...,у)- совокупность параметров оператора оконтуривания.
План эксперимента по тестированию алгоритмов оконтуривания. Функции частей программного комплекса
Существует ряд причин, побуждающих заниматься анализом эффективности использования объема оперативной памяти и времени выполнения, необходимого для успешного решения поставленной задачи. Следует избегать разработки программного обеспечения, которое не отвечает требованиям функциональной эффективности, т.е. степени соответствия алгоритма потребностям пользователя.
Поэтому, лучше заранее произвести оценку необходимого объема памяти и процессорного времени, требуемого алгоритму в процессе обработки данных. Создать условия для объективного сравнения алгоритмов с целью выбора более эффективного алгоритма из альтернативных с учётом перспектив и особенностей применения разрабатываемого программного обеспечения. Найти ту количественную, объективную, обобщённую оценку результатов выполнения алгоритмов. Центральной задачей теории сложности вычислений является создание эффективных алгоритмов и их анализ [92, 111]. При этом под эффективностью алгоритмов принято понимать сопоставление порядков сложности временной эффективности 0(/(Р)), пространственной эффективности @(f(P)j и интеллектуальной сложности Q.(f(P)\ анализируемого алгоритма. Пространственная эффективность измеряется количеством памяти, требуемой для выполнения программы. Если совокупность сопоставляемых программ реализуют идентичные функции, то та программа, которая использует меньший объем памяти, характеризуется большей пространственной эффективностью. Отметим, в последнее время оперативная память персональных компьютеров значительно дешевеет. Поэтому, вопрос пространственной эффективности в настоящее время не является доминирующим и будет упущен в этой работе.
При анализе интеллектуальной сложности алгоритма, — исследуется понятность алгоритмов и сложность их разработки. В нашем случае, проводя сопоставление уже существующих алгоритмов оконтуривания, анализ этапа разработки проводится, не будет. Поэтому, третью компоненту — «интеллектуальную сложность» упустим из рассмотрения. Основной компонентой в нашем случае является составляющая временной эффективности, которая определяется временем необходимым для её выполнения или количеством элементарных операций необходимых для завершения вычислений. Наличие исходных текстов операторов оконтуривания позволило производить расчёт временной эффективности, рассчитывая количество элементарных операций отдельно взятого оператора оконтуривания. Как правило, алгоритмы включает в себя различные операции, которые могут требовать разного времени для своего выполнения. При перемножении двух матриц, мы выполняем операции сложения и умножения вещественных чисел. Время, необходимое для перемножения двух вещественных чисел в общем случае много больше, чем время, затрачиваемое на их сложение. Если это допустимо, пренебрегают временем сложения, считая, что операция сложения производится мгновенно. Время, затрачиваемое алгоритмом на решение задачи, равняется числу выполняемых операций умножения.
В этом случае говорят о мультипликативной сложности алгоритма. В ряде других случаев, можно считать, что время, затрачиваемое на выполнение сложения двух чисел, примерно такое же, что и время, затрачиваемое на их умножение. А для определения сложности алгоритма подсчитывают общее количество операций сложения и умножения. Оценивая сложность алгоритма, говорят о полной арифметической сложности. Если рассмотреть случаи, когда подсчитываются только операции сложения, пренебрегая операциями умножения, то говорят об аддитивной сложности алгоритма. Рассматривая алгоритмы получения контурного рисунка, отметим, что помимо набора умножения, сложения, вычитания, деления в этих алгоритмах используется ряд других функций. В этом случае проведение вычисления аддитивной или мультипликативной сложности алгоритмов не принесут объективных результатов сравнения. Мной предлагается несколько иной подход к вычислению полной арифметической сложности Кплс. Был обобщён ряд операций: количество операций сложения; количество операций вычитания; количество операций умножения; количество операций деления; количество операций вычисления корня; количество операций вычисления арктангенса; количество операций вычисления остатка целочисленного деления. В ходе их анализа, были получены весовые коэффициенты сложности. Под коэффициентом сложности будем в дальнейшем понимать, во сколько раз операция сложения выполняется быстрее, чем оцениваемая операция. Весовые коэффициенты были получены опытным путём, на основании расчёта времени затраченного на вычисление. При нахождении весовых коэффициентов сложности использовался весь интервал возможных значений области определения арифметической операции или вызываемой функции с учётом предметной области решаемой задачи. Для получения коэффициентов использовался компилятор языка Pascal. Получение оценок проводилось под операционной системой Windows NT. Опции компилятора по управлению оптимизацией были использованы по умолчанию.
