| Русский Русский | English English |
   
Главная Архив номеров
12 | 11 | 2019
10.14489/vkit.2016.03.pp.003-010

DOI: 10.14489/vkit.2016.03.pp.003-010

Белим С. В., Кутлунин П. Е.
ВЫЯВЛЕНИЕ ПОВРЕЖДЕННЫХ ПИКСЕЛОВ НА ИЗОБРАЖЕНИИ С ПОМОЩЬЮ АЛГОРИТМА КЛАСТЕРИЗАЦИИ
(c. 3-10)

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

Ключевые слова:  анализ изображений; алгоритм кластеризации; представление изображения в виде дерева; импульсный шум; поиск шума на изображениях.

 

Belim S. V., Kutlunin P. E.
IMPULSE NOISE DETECTION IN IMAGES USING A CLUSTERING ALGORITHM
(pp. 3-10)

Abstract. This article proposes a method for automatic detection of pixels damaged by impulse noise. The pixels of the original image are represented as points of five-dimensional space, which includes three color coordinates and two spatial. Set of the points is matched with a weighted complete graph. Vertices of the graph are the points of five-dimensional space. Euclidian distance between the points is used as weights of the edges. For clustering process a minimum spanning tree is used obtained from the graph. In order to optimize the algorithm a greedy algorithm is used to construct the minimum spanning tree without constructing a complete graph. Leafs of the tree are considered as the noise. These leafs either belongs to large clusters or correspond to clusters with one vertex. A distinctive feature of the one-vertex clusters is their remoteness from the neighboring points. Therefore, leafs are selected as the noise which are connected to the tree with an edge having the length greater than a threshold value. The effectiveness of the method is studied in the computer experiment on real photographic images. The proposed method can automatically detect corrupted pixels with an efficiency of up to 74 % with 10 % noise pollution. The main feature of this method is the low rate of false positives in comparison with other approaches. False positives may be less than 1 % for certain values of the parameters at the correct detection efficiency greater than 50 %.

Keywords: Image analysis; Clustering algorithm; Image representation as a tree; Impulse noise; Noise detection.

Рус

С. В. Белим, П. Е. Кутлунин (Омский государственный университет им. Ф. М. Достоевского) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript  

Eng

S. V. Belim, P. E. Kutlunin (Omsk State University n.a. F. M. Dostoevskiy) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Рус

1. Фисенко В. Т., Фисенко Т. Ю. Компьютерная обработка и распознавание изображений: учеб. пособие. СПб.: Изд-во СПбГУ ИТМО, 2008. 192 с.
2. Методы компьютерной обработки изображений / под ред. В. А. Сойфера. М.: ФИЗМАТЛИТ, 2003. 784 с.
3. Гонсалес Р., Вудс Р. Цифровая обработка изображений: пер. с англ. М.: Техносфера, 2005. 1072 с.
4. Ларионов И. Б. Алгоритм автоматизированного восстановления поврежденных графических файлов // Вестник Омского университета. 2011. № 2. С. 176–177.
5. Ларионов И. Б. Восстановление изображений при помощи многомерных линейных многообразий // Проблемы обработки и защиты информации. Кн. 2. Анализ графической и текстовой информации / под общ. ред. С. В. Белима. Омск: Полиграфический центр КАН, 2010. С. 43 – 57.
6. Ларионов И. Б. Карты Кохонена как способ восстановления мультимедийной информации [Электронный ресурс] // Журнал радиоэлектроники: электрон. журнал. 2010. № 10. 29 c. URL: http://jre.cplire.ru/jre/oct10/ 3/text.html (дата обращения: 10.01.2016).
7. A New Efficient Approach for the Removal of Impulse Noise from Highly Corrupted Images / E. Abreu et al. // IEEE Transactions on Image Processing. 1996. V. 5, № 6. P. 1012 – 1025.
8. A Universal Noise Removal Algorithm with an Impulse Detector / R. Garnett et al. // Transactions on Image Processing. 2005. V. 14, № 11. P. 1747 – 1754. doi: 10.1109/TIP.2005.857261.
9. Сорокин С. В., Щербаков М. А. Реализация SD-ROM фильтра на основе концепции нечеткой логики // Изв. высших учебных заведений. Поволжский регион. Техн. науки. 2007. № 3. С. 56 – 65.
10. Красовский Г. Я., Усс М. Л. Фильтрация изображений, искаженных импульсными помехами точечного и строчного типа, на основе систем итерированных функций // Радiоелектроннi i комп’ютернi системи. 2003. № 2. С. 47 – 55.
11. Белим С. В., Селиверстов С. А., Майоров-Зильбернагель А. О. Использование ассоциативных правил для восстановления зашумленных изображений // Вестник Омского университета. 2013. № 4. С. 197 – 200.
12. Белим С. В., Селиверстов С. А. Использование метода анализа иерархий для выявления импульсного шума в графических объектах // Информационные технологии. 2015. № 4. С. 251 – 258.
13. Chan R., Ho C., Nikolova M. Salt-and-Pepper Noise Removal by Median-Type Noise Detectors and Detail-Preserving Regularization // IEEE Transactions on Image Processing. 2005. V. 14, № 10. P. 1479 – 1485. doi: 10.1109/TIP.2005.852196.
14. Kam H. S., Tan W. H. Noise Detection Fuzzy (NDF) Flter for Removing Salt and Pepper Noise // Visual Informatics: Bridging Research and Practice: Lecture Notes Computer Science. 2009. V. 5857. P. 479 – 486. doi: 10.1007/978-3-642-05036-7_45.
15. Нгок Хоанг Ф., Спицын В. Г. Анализ алгоритмов обнаружения импульсного шума на цифровых изображениях // Изв. Томского политехнического университета. 2011. Т. 318, № 5. С. 70 – 73.
16. Белим С. В., Селиверстов С. А. Алгоритм восстановления поврежденных пикселей на зашумленных изображениях на основе метода анализа иерархий [Электронный ресурс] // Наука и образование: электрон. науч.-техн. изд. 2014. № 11. URL: http://technomag. bmstu.ru/doc/742145.html (дата обращения: 10.01.2016). doi: 10.7463/1114.0742145.
17. Белим С. В., Майоров-Зильбернагель А. О. Восстановление изображений со статическими пропусками на основе метода ассоциативных правил // Вестник компьютерных и информационных технологий. 2014. № 12. С. 18 – 23. doi: 10.14489/vkit.2014.12.pp.018-023.

Eng

1. Fisenko V. T., Fisenko T. Iu. (2008). Computer processing and image recognition: textbook. St. Petersburg: Izdatel'stvo SPbGU ITMO.
2. Soifer V. A. (Ed.). (2003). Methods of computer image processing. Мoscow: FIZMATLIT.
3. Gonsales R., Woods R. (2005). Computer image processing. Moscow: Tekhnosfera.
4. Larionov I. B. (2011). Algorithm for automated repair of damaged image files. Vestnik Omskogo universiteta, (2), pp. 176-177.
5. Belim S. V. (Ed.), Larionov I. B. (2010). Image restoration using multivariate linear manifolds. Problems of processing and data protection. Book 2. Analysis of graphic and text information. Omsk: Poligraficheskii tsentr KAN, pp. 43-57.
6. Larionov I. B. (2010). Kohonen maps as a way to restore multimedia information. Zhurnal radioelektroniki, (10). Available at: http://jre.cplire.ru/jre/oct10/3/text.html (Accessed: 10.01.2016).
7. Abreu E. et al. (1996). A new efficient approach for the removal of impulse noise from highly corrupted images. IEEE Transactions on Image Processing, 5(6), pp. 1012-1025.
8. Garnett R. et al. (2005). A universal noise removal algorithm with an impulse detector. Transactions on Image Processing, 14(11), pp. 1747-1754. doi: 10.1109/TIP.2005.857261.
9. Sorokin S. V., Shcherbakov M. A. (2007). Implementing SD-ROM filter based on fuzzy logic concept. Izvestiia vysshikh uchebnykh zavedenii. Povolzhskii region. Tekhnicheskie nauki, (3), pp. 56-65.
10. Krasovskii G. Ia., Uss M. L. (2003). Filtering images distorted by pulse noises of point and line types based on iterated function systems. Radioelektronni i komp’iuterni sistemi, (2), pp. 47-55.
11. Belim S. V., Seliverstov S. A., Maiorov-Zil'bernagel' A. O. (2013). Using association rules to restore noisy images. Vestnik Omskogo universiteta, (4), pp. 197- 200.
12. Belim S. V., Seliverstov S. A. (2015). Using the method of hierarchy analysis to detect impulse noise in graphic objects. Informatsionnye tekhnologii, (4), pp. 251- 258.
13. Chan R., Ho C., Nikolova M. (2005). Salt-and-pepper noise removal by mediantype noise detectors and detailpreserving regularization. IEEE Transactions on Image Processing, 14(10), pp. 1479-1485. doi: 10.1109/TIP.2005.852196.
14. Kam H. S., Tan W. H. (2009). Noise detection fuzzy (NDF) filter for removing salt and pepper noise. Visual Informatics: Bridging Research and Practice: Lecture Notes Computer Science, V. 5857, pp. 479-486. doi: 10.1007/978-3-642-05036-7_45.
15. Ngok Khoang F., Spitsyn V. G. (2011). Algorithms analysis of detecting impulse noise on digital images. Izvestiia Tomskogo politekhnicheskogo universiteta, 318(5), pp. 70-73.
16. Belim S. V., Seliverstov S. A. (2014). Algorithm of repairing damaged pixels on noisy images based on the analytic hierarchy process. Nauka i obrazovanie, (11). Available at: http://technomag.bmstu.ru/doc/742145.html (Accessed: 10.01.2016). doi: 10.7463/1114.0742145.
17. Belim S. V., Maiorov-Zil'bernagel' A. O. (2014). Image restoration with static gaps on the basis of association rules. Vestnik komp'iuternykh i informatsionnykh tekhnologii, (12), pp. 18-23. doi: 10.14489/vkit.2014.12.pp.018-023.

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа статьи заполните форму:

{jform=1,doi=10.14489/vkit.2016.03.pp.003-010}

.

Eng

This article  is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please fill out the form below:

{jform=2,doi=10.14489/vkit.2016.03.pp.003-010}

 

 

 

 

 

.

.

 

 

 
Поиск
Баннер
Баннер
Баннер
Баннер
Журнал КОНТРОЛЬ. ДИАГНОСТИКА
Rambler's Top100 Яндекс цитирования