informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-879Research ArticleОБРАБОТКА СИГНАЛОВ, ИЗОБРАЖЕНИЙ, РЕЧИ, ТЕКСТА И РАСПОЗНАВАНИЕ ОБРАЗОВSIGNAL, IMAGE, SPEECH, TEXT PROCESSING AND PATTERN RECOGNITIONСегментный поиск локальных экстремумов изображений на основе анализа яркостей смежных однородных областейSegment search for local extremums of images based on the analysis of brightness of adjacent homogeneous areasЦветковВ. Ю.TsviatkouV. Yu.

доктор технических наук, доцент, заведующий кафедрой инфокоммуникационных технологий

Dr. Sci. (Eng.), Assoc. Prof., Head of the Department of Infocommunication Technologies

vtsvet@bsuir.byНгуенАнь ТуанNguyenAnh Tuan

аспирант кафедры инфокоммуникационных технологий

Postgraduate Student of Department of Infocommunication Technologies

nguyenanhtuanrti@gmail.comБелорусский государственный университет информатикиBelarusian State University of Informatics and Radioelectronics2019260820191632336Copyright © Цветков В.Ю., Нгуен А., 20192019Цветков В.Ю., Нгуен А.Tsviatkou V.Y., Nguyen A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/879

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

The problem of finding local extrema on halftone images is considered. Well-known block-search algorithms provide high speed, but they extract only strict (single-pixel) extremes, skipping extreme areas formed by non-strict extremes. Morphological search algorithms provide the selection of non-strict extremes, but have a high computational complexity. A mathematical model and an algorithm based on the brightness analysis of adjacent homogeneous regions are proposed to isolate strict and non-strict local extremes of images with low computational complexity. Their differences from well-known models are: consideration of homogeneous areas, which are formed by non-strict extremes and are local maxima or minima in relation to adjacent areas; elimination of iterative processing of non-extreme pixels; assigning the numbers to local extremes during their search. These differences allowed to increase the accuracy of local extremum extraction in comparison with block search and to reduce the computational complexity in comparison with morphological search. 

сегментный поисклокальные экстремумыстрогие экстремумынестрогие экстремумылокальные максимумылокальные минимумыsegmentsearchlocal extremesstrict extremesnon-strict extremeslocal maximalocal minimaReferencesLindeberg T. Scale selection properties of generalized scale-space interest point detectors. Journal of Mathematical Imaging and Vision, 2013, vol. 46, no. 2, pp. 177–210.Lindeberg, T. Scale Selection Properties of Generalized Scale-Space Interest Point Detectors / T. Lindeberg, Tony // Journal of Mathematical Imaging and Vision. – 2013. – Vol. 46, Iss. 2. – P. 177–210.Lindeberg T. Image matching using generalized scale-space interest points. Journal of Mathematical Imaging and Vision, 2015, vol. 52, no. 1, pp. 3–36.Lindeberg, T. Image matching using generalized scale-space interest points / T. Lindeberg // Journal of Mathematical Imaging and Vision. – 2015. – Vol. 52. –No. 1. – P. 3–36.Lowe D. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 2004, vol. 60, pp. 91–110.Lowe, D. Distinctive image features from scale-invariant keypoints / D. Lowe // IJCV. – 2004. – Vol. 60. – P. 91–110.Bay H., Ess A., Tuytelaars T., Van Gool L. SURF: Speeded Up Robust Features. Computer Vision and Image Understanding, 2008, vol. 110, no. 3, pp. 346–359.Herbert Bay. SURF: Speeded Up Robust Features / Herbert Bay, Andreas Ess, TinneTuytelaars, Luc Van Gool // Computer Vision and Image Understanding (CVIU). – 2008. – Vol. 110. –No. 3. – P. 346–359.Mikolajczyk K., Schmid C. Scale and affine invariant interest point detectors. International Journal of Computer Vision, 2004, vol. 60, pp. 63–86.Mikolajczyk, K. Scale and affine invariant interest point detectors / K. Mikolajczyk, C. Schmid// IJCV. – 2004. – Vol. 60. – P. 63–86.Rosenfeld A., Kak A. Digital Picture Processing. Academic Press, 1976, 457 p.Rosenfeld, A. Digital Picture Processing / A. Rosenfeld, A. Kak. Academic Press, 1976.Kitchen L., Rosenfeld A. Gray-level corner detection. Pattern Recognition Letters, 1982, vol. 1, pp. 92–102.Kitchen, L. Gray-level corner detection / L. Kitchen, A. Rosenfeld // Pattern Recognition Letters. – 1982. – Vol. 1. – P. 92–102.Harris C., Stephens M. A combined corner and edge detector. Proceedings of the 4th Alvey Vision Conference, Manchester, 31 August – 2 September 1988. Manchester, 1988, pp. 147–151.Harris, C. A combined corner and edge detector / C. Harris, M. Stephens // Proc. of the Fourth Alvey Vision Conference. – 1988. – P. 147–151.Bretzner L., Lindeberg T. Feature tracking with automatic selection of spatial scales. Computer Vision and Image Understanding, 1998, vol.71, no. 3, pp. 385–392.Lindeberg, T. Feature Tracking with Automatic Selection of Spatial Scales / L. Bretzner, T. Lindeberg // Computer Vision and Image Understanding. – 1998. –Vol.71. –No. 3. – P.385–392.Lindeberg T. Scale-space. Encyclopedia of Computer Science and Engineering, 2008, vol. 4, pp. 2495–2504.Lindeberg, T. Scale-space. In Wah, Benjamin (ed.). Encyclopedia of Computer Science and Engineering / T. Lindeberg // John Wiley and Sons. – 2008. – P.2495–2504.Lindeberg T. Detecting salient blob-like image structures and their scales with a scale-space primal sketch: a method for focus-of-attention. International Journal of Computer Vision, 1993, vol. 11, no. 3, pp. 283–318.Lindeberg, T. Detecting Salient Blob-Like Image Structures and Their Scales with a Scale-Space Primal Sketch: A Method for Focus-of-Attention / T. Lindeberg // International Journal of Computer Vision. – 1993. –Vol.11 –No. 3. – P.283–318.Lindeberg T. Scale-Space Theory in Computer Vision. Springer, 1994, 423 p.Lindeberg, T. Scale-Space Theory in Computer Vision / T. Lindeberg. Springer, 1994.Matas J., Chum O., Urban M., Pajdla T. Robust wide baseline stereo from maximally stable extremal regions. Proceedings of the 13th British Machine Vision Conference, Bristol, UK, 2–5 September 2002. Bristol, 2002, pp. 384–396.Matas, J. Robust wide baseline stereo from maximally stable extremal regions / J. Matas, O. Chum, M. Urban, and T. Pajdla // Proc. of British Machine Vision Conference. – 2002. – P.384–396.Haralick R. M., Shapiro L. G. Image segmentation techniques. Computing Vision, Graphics and Image Processing, 1985, vol. 29, no. 1, pp. 100–132.Van Herk, M. A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels / M. Van Herk// Pattern Recognition Letters. – 1992. – Vol. 13. – P. 517–521.Karu K., Jain A. K., Bolle R. M. Is there any texture in the image? Pattern Recognition, 1996, vol. 29, no. 9, pp. 1437–1446.Gil, J. Computing 2-D min, median, and max / J. Gil, M. Werman// IEEE Trans. on PAMI. – 1993. – Vol. 15. – P. 504–507.Van Herk M. A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels. Pattern Recognition Letters, 1992, vol. 13, pp. 517–521.Coltuc, D. Fast computation of rank order statistics / D. Coltuc, P. Bolon,// Proc. Of EUSIPCO. – 2000. – P. 2425–2428.Gil J., Werman M. Computing 2-D min, median, and max. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993, vol. 15, pp. 504–507.Neubeck, A. Efficient non-maximum suppression / A. Neubeck, L. Van Gool// Proc. of ICPR. – 2006. – Vol. 3. – P. 850–855.Coltuc D., Bolon P. Fast computation of rank order statistics. Proceedings of the 10th European Signal Processing Conference, Tampere, Finland, 4–8 September 2000. Tampere, 2000, pp. 2425–2428.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.Neubeck A., Van Gool L. Efficient non-maximum suppression. Proceedings of the 18th International Conference on Pattern Recognition, Hong Kong, 20–24 August 2006. Hong Kong, 2006, vol. 3, pp. 850–855.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.Forstner W., Gulch E. A fast operator for detection and precise locations of distinct points, corners, and centres of circular features. Proceedings of Intercommission Conference on Fast Processing of Photogrammetric Data, Interlaken, Switzerland, 2–4 June 1987. Interlaken, 1987, pp. 281–305.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.Pham T. Q. Non-maximum suppression using fewer than 2 comparisons per pixel. Proceedings of Advanced Concepts for Intelligent Vision Systems, Sydney, Australia, 13–16 December 2010. Sydney, 2010, vol. 12, pp. 438–451.Soille, P. Morphological Image Analysis: Principles and Applications / P. Soille. Springer, 2002.Bastys A., Kranauskas J., Masiulis R. Iris matching by local extremum points of multiscale taylor expansion. Proceedings of the 3rd International Conference "Advances in Biometrics". Springer-Verlag, Berlin, Heidelberg, 2009, pp. 1070–1079.Gonzales, R.C. Digital image processing / R.C. Gonzales, R.E. Woods.Boston, MA Addison-Wesley, 2001. – 823 p.Soille P. Morphological Image Analysis: Principles and Applications. Springer, 2002, 391 p.Soille P. Morphological Image Analysis: Principles and Applications. Springer, 2002, 391 p.Gonzales R. C., Woods R. E. Digital image processing. Boston, Addison-Wesley, 2001, 823 p.Gonzales R. C., Woods R. E. Digital image processing. Boston, Addison-Wesley, 2001, 823 p.

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