sapiСистемный анализ и прикладная информатика«System analysis and applied information science»2309-49232414-0481Belarusian National Technical University10.21122/2309-4923-2019-4-4-9sapi-406Research ArticleСистемный анализSystem analysisБлочно-сегментный поиск локальных экстремумов изображений на основе анализа яркостей смежных пикселей и областейBlock-segment search of local extrema of images based on analysis of brightnesses of related pixels and areasНгуенА. Т.NguyenA. T.nguyenanhtuanrti@gmail.comЦветковВ. Ю.TsviatkouV. Yu.vtsvet@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиБеларусьBelarusian State University of Informatics and RadioelectronicsBelarus2019301220190449Copyright © Нгуен А.Т., Цветков В.Ю., 20192019Нгуен А.Т., Цветков В.Ю.Nguyen A.T., Tsviatkou V.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://sapi.bntu.by/jour/article/view/406

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

The aim of the work is to develop an algorithm for extracting local extremes of images with low computational complexity and high accuracy. The known algorithms for block search for local extrema have low computational complexity, but only strict maxima and minima are distinguished without errors. The morphological search gives accurate results, highlighting the extreme areas formed by non-severe extremes, however, it has high computational complexity. The paper proposes a block-segment search algorithm for local extremums of images based on an analysis of the brightness of adjacent pixels and regions. The essence of the algorithm is to search for single-pixel local extremes and regions of uniform brightness, comparing the values of their boundary pixels with the values of the corresponding pixels of adjacent regions: the region is a local maximum (minimum) if the values of all its boundary pixels are larger (smaller) or equal to the values of all adjacent pixels. The developed algorithm, as well as the morphological search algorithm, allows detecting all single-pixel local extremes, as well as extreme areas, which exceeds the block search algorithms. At the same time, the developed algorithm in comparison with the morphological search algorithm requires much less time and RAM.

локальные экстремумы изображенийстрогие и нестрогие экстремумыблочно-сегментный поиск локальных экстремумовсегментация изображенийlocal extremums of imagesstrict and non-strict extremesblock-segment search for local extremesimage segmentationReferencesVan Herk, M. A fast algorithm for local minimum and maximum fi on rectangular and octagonal kernels / M. Van Herk // Pattern Recognition Letters. – 1992. – Vol. 13. – P. 517–521.Van Herk, M. A fast algorithm for local minimum and maximum fi on rectangular and octagonal kernels / M. Van Herk // Pattern Recognition Letters. – 1992. – Vol. 13. – P. 517–521.Gil, J. Computing 2-D min, median, and max / J. Gil, M. Werman// IEEE Trans. on PAMI. – 1993. – Vol. 15. – P. 504–507.Gil, J. Computing 2-D min, median, and max / J. Gil, M. Werman// IEEE Trans. on PAMI. – 1993. – Vol. 15. – P. 504–507.Coltuc, D. Fast computation of rank order statistics / D. Coltuc, P. Bolon // Proc. Of EUSIPCO. – 2000. – P. 2425– 2428.Coltuc, D. Fast computation of rank order statistics / D. Coltuc, P. Bolon // Proc. Of EUSIPCO. – 2000. – P. 2425– 2428.Neubeck, A. Efficient non-maximum suppression / A. Neubeck, L. Van Gool// Proc. of ICPR. – 2006. – Vol. 3. – P. 850–855.Neubeck, A. Efficient non-maximum suppression / A. Neubeck, L. Van Gool// Proc. of ICPR. – 2006. – Vol. 3. – P. 850–855.Forstner, W. A fast operator for detection and precise locations of distinct points, corners, and centres of circular features / W. Forstner, E. Gulch // Proc. of Intercommission Conf. on Fast Processing of Photogrammetric Data. – 1987. – P. 281–305.Forstner, W. A fast operator for detection and precise locations of distinct points, corners, and centres of circular features / W. Forstner, E. Gulch // Proc. of Intercommission Conf. on Fast Processing of Photogrammetric Data. – 1987. – P. 281–305.Tuan Q. Pham. Non-maximum Suppression Using fewer than 2 Comparisons per Pixel / Tuan Q. Pham // Advanced Concepts for Intelligent Vision Systems(ACIVS). – 2010. – Vol. 12. – P. 438 –451.Tuan Q. Pham. Non-maximum Suppression Using fewer than 2 Comparisons per Pixel / Tuan Q. Pham // Advanced Concepts for Intelligent Vision Systems(ACIVS). – 2010. – Vol. 12. – P. 438 –451.Bastys, A. Iris Matching by Local Extremum Points of Multiscale Taylor Expansion / A. Bastys, J. Kranauskas, R. Masiulis // Springer-Verlag Berlin Heidelberg, 2009. ICB 2009, LNCS 5558. – P. 1070–1079.Bastys, A. Iris Matching by Local Extremum Points of Multiscale Taylor Expansion / A. Bastys, J. Kranauskas, R. Masiulis // Springer-Verlag Berlin Heidelberg, 2009. ICB 2009, LNCS 5558. – P. 1070–1079.Soille, P. Morphological Image Analysis: Principles and Applications / P. Soille. Springer, 2002. – 391 pSoille, P. Morphological Image Analysis: Principles and Applications / P. Soille. Springer, 2002. – 391 p

The authors declare that there are no conflicts of interest present.