Модификация количественной оценки детекторов границ прэтта-яскорского

Решетнеескцие чтения. 2015

for model diagnostic // Expert Systems with Applications. 2012. Vol. 39, № 2. P. 1772-1778.

5. Семенкин Е. С., Шабалов А. А., Ефимов С. Н. Автоматизированное проектирование коллективов интеллектуальных информационных технологий методом генетического программирования // Вестник СибГАУ. 2011. № 3(36). С. 77-81.

6. Семенкин Е. С., Семенкина М. Е. Применение генетического алгоритма с модифицированным оператором равномерной рекомбинации при автоматизированном формировании интеллектуальных информационных технологий // Вестник СибГАУ. 2007. № 3(16). С. 27-33.

7. Semenkin E., Semenkina M. Self-configuring genetic programming algorithm with modified uniform crossover // 2012 IEEE Congress on Evolutionary Computation, CEC. 2012. С. 6256587.

References

1. RapidMiner [Electronic resource]. URL: https:// rapidminer.com/ (accessed: 23.06.2015).

2. Hinton G., Deng L., Yu D., Dahl G., Mohamed A., Jaitly N., Senior A., Vanhoucke V., Nguyen P., Sainath T. and Kingsbury B. Deep Neural Networks for Acoustic Modeling in Speech Recognition // IEEE Signal Processing Magazine, 2012. Vol. 29, no. 6, pp. 82-97.

3. Fayyad U. M., Piatetsky-Shapiro G., Smyth P., and Uthurusamy R. Advances in Knowledge Discovery and Data Mining // The AAAI Press, 1996.

4. Antipov E. A., Pokryshevskaya E. B. Mass appraisal of residential apartments: An application of Random forest for valuation and a CART-based approach for model diagnostic // Expert Systems with Applications. 2012. Vol. 39, no. 20, рр. 1772-1778.

5. Semenkin E. S., Shabalov A. A., Efimov S. N. Automated design of intelligent information technologies with genetic programming method // Vestnik SibGAU. 2011. No. 3(36), рр. 77-81.

6. Semenkin E. S., Semenkina M. E. Application of genetic programming algorithm with modified uniform crossover operator for automated design of intelligent information technologies // Vestnik SibGAU. 2007. No. 3(16). C 27-33.

7. Semenkin E., Semenkina M. Self-configuring genetic programming algorithm with modified uniform crossover // 2012 IEEE Congress on Evolutionary Computation, CEC, 2012. Q 6256587.

© Дресвянский Д. В., 2015

УДК 004.932:94, 001.891.57, 004.413.5, 004.415.5:532

МОДИФИКАЦИЯ КОЛИЧЕСТВЕННОЙ ОЦЕНКИ ДЕТЕКТОРОВ ГРАНИЦ ПРЭТТА-ЯСКОРСКОГО

Д. В. Дубинин1, А. И. Кочегуров2, В. Е. Лаевский3

1Томский государственный университет систем управления и радиоэлектроники Российская Федерация, 634050, г. Томск, просп. Ленина, 40 Национальный исследовательский Томский политехнический университет Российская Федерация, 634050, г. Томск, просп. Ленина 30 Государственный объединённый университет Баден-Вюртемберга, инженерный факультет Германия, 88045, г. Фридрихсхафен, Фалленбрунен, 2 Е-mail: 3geringer@dhbw-ravensburg.de

В результате исследования комплексного метода, предложенного в работе I. Boaventura и A. Gonzaga, были отмечены завышенные значения критерия Прэтта (Pratt's Figure of Merit) при малых отношениях с/ш (PSNR -Peak Signal-to-Noise Ratio). В связи с этим в работе представлены результаты количественной оценки детекторов границ с использованием классического критерия Прэтта, предложений по модификации Яскорского и необходимым обобщением и доработкой обоих подходов с точки зрения интеграции в среду программного комплекса стохастического моделирования «КИМ СП». Аппроксимация эталонных изображений произведена с использованием двумерного точечного потока восстановления, обладающего свойствами стационарности, отсутствием последствий, ординарности. Эффективность предлагаемой метрики приведена для трех алгоритмов оконтуривания (Marr-Hildreth, ISEF и Canny) при различных уровнях аддитивного нормального шума. Приведены оценки ошибок первого и второго рода. Результаты стохастического моделирования показывают эффективность предлагаемого подхода.

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

MODIFICATION PRATT FIGURE OF MERIT

D. V. Dubinin1, A. I. Kochegurov2, V. E. Geringer3

1Tomsk State University of Control Systems and Radioelectronics 40, Lenin Av., Tomsk, 634050, Russian Federation 2National Research Tomsk Polytechnic University 30, Lenin Av., Tomsk, 634050, Russian Federation 3Baden-Wurttemberg Cooperative State University, Faculty of Engineering, Campus FN 2, Fallenbrunnen, Friedrichshafen, D-88045, Germany E-mail: 3geringer@dhbw-ravensburg.de

As a result of the study the complex method is proposed in the paper of I. Boaventura and A. Gonzaga, the conservative values of Pratt Figure of Merit under low PSNR (Peak Signal-to-Noise Ratio) are observed. In this regard, the paper presents the results of the quantitative estimate of the edge detection using classical Pratt criteria, proposals by Yaskorski modification and necessary generalization and follow-up revision of both approaches in terms of integration into the framework of the stochastic modeling bundled software "CS sF". Approximation of the reference images has been performed using the two-dimensional Markoff-Renewal-Process with the properties of stationary state, with no consequences and of ordinariness. The efficiency of the proposed metrics is given to three edging algorithms (Marr-Hildreth, ISEF and Canny) under various levels of the additive normal noise. There the estimations of the type 1 and 2 errors are presented. Results of the stochastic computer simulation show the effectiveness of the proposed approach.

Keywords: stochastic computer simulation, reference image, edge detection, quality metrics, performance evaluation, comparison of algorithms.

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

В данной работе представлены результаты стохастического моделирования оценки качества получения контурного рисунка изображения на основе критерия, предложенного Прэттом [1], его модификации - работы Яскорского [2] и обобщения критерия качества с учётом трёх основных типов ошибок: а) локальных смещений (LE - localization error); б) утолщений (MRE -multiples responses error); в) разрывов (OE - omission error) [3].

Цель работы. В результате исследования комплексного метода, предложенного в [4], были отмечены завышенные значения критерия Прэтта (Pratt's Figure of Merit) при малых отношениях с/ш. Поэтому целью данной работы является получение модификации метрики Прэтта, предложенной Яскорским, при условии обобщения метрикой трёх основных типов ошибок, вносимых операторами поиска и локализации границ, адаптация обобщённой метрики в среде комплекса «КИМ СП» [5], оценка возможности выбора алгоритма детектирования.

Этапы моделирования. Для достижения этой цели были решены следующие задачи: 1) сформировать с помощью комплекса «КИМ СП» эталонные изображения с определёнными морфологическими и статистическими свойствами; 2) ввести шумовую состав-

ляющую с нормальным законом распределения и заданным отношением сигнал/шум (с/ш); 3) провести выделение границ различными контурными детекторами; 4) интегрировать различные модификации критерия Прэтта в среду «КИМ СП»; 5) оценить качество выделения границ.

Математическая формализация задачи. Очень часто для проведения сопоставления полученных результатов используется классическая метрика Прэтта [1]. Её общий вид можно представить в виде

1 ^ 1

FOM =-

max {

[ii, ia }él1 + a-d (if

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

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

1 & 1

FOMle =-

Ii

11 -СЫ + а^0)2'

где СЫ - число точек в реальном контурном изображении, не участвующих в расчёте метрики (величина смещения i-й точки найденного контура по нормали к линии идеального контура превышает размеры анализируемой области (5*5), d > 2).

Проводя учёт утолщений контурного поля, его смазывания, вводим составляющую

Решетнееские чтения. 2015

FOMm

1

II - CNC

Ii

1

,=11+p-b(i)2

где СЫС - число элементов в реальном контурном изображении, не участвующих в расчёте метрики (например, центральная точка элемента 170 алфавита морфологии «А», изображение которого является пересечением вертикальной и горизонтальной линий в центре рабочей области, что не позволяет производить учёт центральной точки); в - масштабный множитель, учитывающий величину штрафа, вызванного утолщением (смазыванием) контурной линии; b(i) -количество смазанных точек идеального контура в -й области.

Таким образом, метрика Прэтта позволяет производить учёт локально смещённых (localization error), смазанных и утолщённых границ (multiples responses error). К недостаткам обоих представлений (2) и (3), необходимо отнести плохую реакцию метрик на пропуски элементов границ контура и длину разрывов (последовательность элементов контура, примыкающих друг к другу). Как следствие - завышенное значение метрик при оценке растрового контурного поля, полученного при малых отношениях с/ш. В работе Яскорского [2] был показан один из возможных путей решения этой проблемы. Используя одно из предложений Яскорского по модификации критерия Прэтта, запишем:

1 f 1 N f1 + X-n(j)2'

FOMoE

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

Проводя обобщение результатов, предлагается объединить три составляющие (2), (3) и (4) на основе мультипликативного критерия качества и представить его в форме

mpfom = fomlE * fomMrE * fomOb ,

где MPFOM - Modification Pratt's Figure of Merit.

Результаты. Предложенная методика была проверена с помощью моделирования в среде «КИМ СП». Используя двумерный точечный поток восстановления, были получены эталонные изображения морфологии «А» [6]. На рис. 1, 2 показаны зависимости показателей качества детектирования границ от отношения сигнал/шум для трех операторов выделения границ.

На рис. 3 представлены результаты качества детектирования теми же операторами выделения границ, проведенные по методике оценки ошибок первого и второго рода [4]. При сравнении результатов, показанных на рис. 1, рис. 2, с результатами, приведенными на рис. 3, следует учитывать, что лучшему детектированию соответствуют большие значения FOMLE, FOMmre, FOMoe и MPFOM и меньшие значения ошибок Pnd и Pfa.

Рис. 1. FOMlE и FOMMrE для эталонных изображений морфологии «Л»

Рис. 2. FOMOE и MPFOM для эталонных изображений морфологии «A»

Рис. 3. Ошибки Рпа (первого) и Ра (второго рода) для эталонных изображений морфологии «А»

Заключение. Полученные результаты численных экспериментов на программно-алгоритмическом комплексе «КИМ СП» показали, что модифицированный показатель качества Прэтта (5) может быть использован для объективной оценки качества алгоритмов поиска и локализации границ. Проведенные исследования позволили выделить области предпочтения каждого из алгоритмов в зависимости от отношения с/ш и типа морфологии.

Библиографические ссылки

1. Abdou I., Pratt W. Quantitative Design and Evaluation of Enhancement/Thresholding Edge Detectors // Proceedings of the IEEE (ISSN 0018-9219). 1979. Vol. 67, № 5. P. 753-763.

2. Яскорский А. В. Критерии оценки качества работы детекторов контуров // Автометрия. 1987. № 3. C. 127-128.

3. Nguyen T. B., Zhou D. Contextual and Non-Contextual Performance Evaluation of Edge Detectors // Pattern Recognition Letters 2. 2000. Vol. 21, № 9. P. 805-816.

4. Boaventura I., Gonzaga A. Method to Evaluate the Performance of Edge Detector // SIBGRAPI 2009, XXIInd Brazilian Symposium on Computer Graphics and Image Processing, Rio de Janeiro, 2009. P. 1-3.

5. Dubinin D., Geringer V., Kochegurov A. Reif Bundled Software for Simulation Modeling // Proceedings of the International Symposium on Signals, Circuits and Systems (ISSCS 2013). Romania, Iasi: ISSCS Press (IEEE Catalog Number: CFP13816-CDR). 2013. P. 1-4.

6. Дубинин Д. В., Кочегуров А. И., Лаевский В. Е. Методика моделирования случайных яркостных полей, аппроксимированных однородными одноуровневыми марковскими цепями // Проблемы информатики. 2011. № 4(12). C. 35-40.

References

1. Abdou I., Pratt W. Quantitative Design and Evaluation of Enhancement/Thresholding Edge Detectors // Proceedings of the IEEE (ISSN 0018-9219), 1979. Vol. 67, no. 5, рp. 753-763.

2. Yaskorsky A. V. Kriterii otsenki kachestva raboty detektorov konturov [Criteria for the performance evaluation of the edge detectors] // Optoelectronics, Instrumentation and Data Processing. 1987. No. 3, рp. 127-128 (In Russ.).

3. Nguyen T. B., Zhou D. Contextual and Non-Contextual Performance Evaluation of Edge Detectors, Pattern Recognition Letters 2, 2000. Vol. 21, no. 9, рp. 805-816.

4. Boaventura I., Gonzaga A. Method to Evaluate the Performance of Edge Detector // SIBGRAPI 2009, XXIInd Brazilian Symposium on Computer Graphics and Image Processing, Rio de Janeiro, 2009, рp. 1-3.

5. Dubinin D., Geringer V., Kochegurov A. Reif Bundled Software for Simulation Modeling // In: Proceedings of the International Symposium on Signals, Circuits and Systems (ISSCS 2013). Romania, Iasi: ISSCS Press (IEEE Catalog Nu; ber: CFP13816-CDR), 2013, pp. 1-4.

6. Dubinin D., Kochegurov A., Laevski V. Metodika modelirovaniya sluchaynykh yarkostnykh poley, approksimirovannykh odnorodnymi odnourovnevymi markovskimi tsepyami [A Particular Method of Generating Stochastic Intensity Fields by two-dimensional Semi-Markov Model] // Journal of Information Sciences, Novosibirsk: "ICM & MG SB RAS" Publisher, 2011. No. 4(12), рp. 35-40 (In Russ.).

© Дубинин Д. В., Кочегуров А. И., Лаевский В. Е., 2015