BINARIZATION OF "BACKGROUND - OBJECT" BY USING PRETREATMENT OF AN IMAGE AND FUZZY K-MEANS ALGORITHM
Authors:
1.
Kuban State Technological University
Type:
Article
Pages:
from 32
to 39
Status:
Published
Received:
05.07.2016
Accepted:
25.07.2016
Published:
25.07.2016
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.9
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK 004.9
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
binarization of 2D-images, separation of an object from background, fuzzy k-means clusterization
Abstract (English):
The paper considers the stage of binarization of color 2D-image into the connected areas with the pixels of an object and background while identifying the state of the objects of natural origin and their mass quantity with detailed evaluation by means of the systems of computer vision, with high variability inside the classes and their proximity. Binarization algorithm is suggested on the basis of k-means clusterization with Euclid’s metrics, which helps eliminate a number of difficulties while choosing the algorithms for software actualization in the computer vision systems and satisfies the demands for velocity and accuracy. The algorithm combines pretreatment of an image by using additional "fuzzy" cluster in the k -means algorithm for the control of quality of separation of an object from background. The pretreatment under certain conditions excludes the lightness L of color scale CIELab (CIE 1976 Lab) from k -means.
The paper considers the stage of binarization of color 2D-image into the connected areas with the pixels of an object and background while identifying the state of the objects of natural origin and their mass quantity with detailed evaluation by means of the systems of computer vision, with high variability inside the classes and their proximity. Binarization algorithm is suggested on the basis of k-means clusterization with Euclid’s metrics, which helps eliminate a number of difficulties while choosing the algorithms for software actualization in the computer vision systems and satisfies the demands for velocity and accuracy. The algorithm combines pretreatment of an image by using additional "fuzzy" cluster in the k -means algorithm for the control of quality of separation of an object from background. The pretreatment under certain conditions excludes the lightness L of color scale CIELab (CIE 1976 Lab) from k -means.
Keywords:
binarization of 2D-images, separation of an object from background, fuzzy k-means clusterization
binarization of 2D-images, separation of an object from background, fuzzy k-means clusterization
Введение Бинаризация цветного 2D-изображения на связные области с пикселями объекта и фона важна для решения задачи идентификации с детальной оценкой системами компьютерного зрения состояния объектов природного происхождения и их массового количества, с высокой вариабельностью внутри классов, и близости самих классов. Основная сложность подбора алгоритмов решения рассматриваемой задачи - высокая вариабельность характеристик пикселей изображения (что свойственно объектам природного происхождения), внимание к мелким деталям на поверхности каждого объекта, необходимость количественной оценки этих деталей и обеспечение дальнейшего сбора информации о состоянии массового количества объектов, большой объём данных и высокие требования к скорости и точности [1-4]. Наиболее популярным методом бинаризации цветных изображений является алгоритм k-means. В [3] предложен способ предобработки для повышения его эффективности, но он не решает проблемы теней, бликов и прочих пиксельных «выбросов» и «помех». Подходы, основанные на использовании графовых или агломеративных методов, могут дать хороший результат (особенно в том случае, когда учитывается критерий связности), но характеризуются очень низким быстродействием [5-7]. Методы, основанные на выделении границ, использовании порогов, а также метод Оцу неприменимы для работы с цветными изображениями с наличием «помех» [6, 7]. В данной работе предложен алгоритм бинаризации на основе кластеризации k-means с евклидовой метрикой, удовлетворяющий требованиям к скорости и точности, сочетающий предобработку изображения с применением вспомогательного «нечёткого» кластера в алгоритме k-means для контроля качества отделения объекта от фона. Особенностью работы алгоритма является то, что он не использует «тяжёлые» агломеративные или графовые технологии; повышение точности основано на предобработке изображений; контроле качества бинаризации, основанном на «нечетком» кластере в алгоритме k-means. Ни одна из составляющих алгоритма не является вычислительно сложным процессом. Общая схема алгоритма отделения пикселей объекта от фона и предобработка 2D-изображения Общая схема алгоритма показана на рис. 1. Следует отметить, что при кластеризации k-means необходимо применять евклидову метрику: она даёт стабильные средние результаты по сравнению с остальными известными метриками (Манхэттен, Махаланобис и др.). Ряд экспериментов с использованием различных метрик позволил выявить, что евклидова метрика даёт наиболее стабильные и качественные результаты, при использовании других метрик часть объектов сливается с фоном, появляется скопление единичных пикселей, ложные объекты и т. д. а б Рис. 1. Алгоритм отделения пикселей объекта от фона: а - общая схема; б - схема блока контроля качества бинаризации Предобработка при определённых условиях исключает светлоту L цветовой шкалы CIELab (CIE 1976 Lab), далее LAB, из k-means. Помехи, связанные с бликами, тенями и неравномерностью освещения, отражены преимущественно на оси L пространства LAB, и при исключении её влияния результат бинаризации будет более высокого качества. Однако в ряде случаев информация, представленная на изображении, содержится преимущественно в компоненте L: монохромное изображение, однотонное или фото с чёрными объектами на белом фоне, или с белыми на чёрном и т. п. Один из способов оценки информативности каждой оси - расчёт среднеквадратичных отклонений проекций пикселей на эти оси и их сравнение. Информативность компоненты L рассчитывается по формуле (1): , , (1) где σL, σB, σA - среднеквадратичное отклонение пикселей изображения по компонентам L, A и B соответственно; n - число точек-пикселей; - среднее значение характеристики L по всем пикселям; Li - значение компоненты L для i-го пикселя (среднеквадратичное отклонение проекций точек на оси A и B рассчитывается аналогично). В зависимости от значения IL необходимо по-разному выполнять предобработку изображения (рис. 1, а). Параметры a и b подбираются эмпирически для каждого типа изображений: в данном случае a = 100, b = 8 (рассматривался случай с множественным количеством объектов на однородном фоне). Экспериментально установлено, что при IL > a = 100 - класс монохромных изображений; при 100 > IL > b = 8 - класс изображений, в которых компонента L цветового пространства LAB содержит важную информацию, но информация содержится не только в этой компоненте. Как видно из рис. 1, а, при IL > 100 информация об изображении содержится преимущественно в компоненте L, и из этого можно сделать вывод, что выполнять его бинаризацию следует с использованием методов бинаризации однотонных изображений - метода Оцу и т. п. В случае, когда 100 > IL > 8, перед тем как исключать компоненту L цветового пространства LAB, необходимо выполнить дополнительную обработку изображения в цветовом пространстве RGB: - определить среднеарифметические по всем пикселям значения {Cj}, j = 1; 2; 3 цветовых компонент изображения в цветовом пространстве RGB; - выбрать компоненту, среднее значение которой максимально: max{Cj} = C; - получить новые значения Cijꞌ = {Riꞌ, Giꞌ, Biꞌ} компонент RGB каждого i-го пикселя по следующей формуле: (2) Пример результатов после выполнения операции добавления оттенков цвета, исключения компоненты L и бинаризации по k-means показан на рис. 2. Как видно из рис. 2, добавление оттенков цвета даёт положительный эффект при высоких значениях IL. На изображениях, имеющих объекты с цветовыми характеристиками, близкими к фону, предварительная обработка по L может не принести желаемого результата. Индикатором этого может выступать информационная энтропия H, показывающая однородность элементов в множестве: чем энтропия выше, тем множество более однородно. Информационная энтропия изображения рассчитывается по формуле , (3) где pijt - вероятность попадания в заданные диапазоны (Ri, Gj, Bt), на которые разбиты интервалы [0; 255] цветовых RGB-шкал координат пикселей (здесь I = J = T = 255 в интервалах [0; 255] RGB-шкал). а б в г д е Рис. 2. Бинаризация изображения, где 100 > IL > 8: а - исходное изображение; б - результат бинаризации исходного изображения по k-means; в - результат бинаризации с предварительной обработкой по L; г - изображение после предобработки по (2); д - изображение после предобработки по L и (2); е - результат бинаризации по k-means с предобработкой по L и (2) На изображениях с высокой энтропией возможно негативное влияние предварительной обработки, т. к. переход из трёхмерного цветового пространства в двухмерное сопровождается потерей информации, и если на разнородных изображениях (с низкой энтропией) повышение однородности оказывает положительное влияние, то на изображениях с высокой энтропией влияние будет негативным. Пример изображения с высокой энтропией представлен на рис. 3. а б в г Рис. 3. Бинаризация изображения с H > 9,8: а - исходное изображение с высокой энтропией; б - результат бинаризации по k-means; в - результат бинаризации с предобработкой по L; г - результат бинаризации по k-means c «нечётким» кластером Как видно из рис. 3, б, в, для изображений с высокой энтропией предварительная обработка по L оказывает негативное воздействие. Порог для H подбирается эмпирически для каждого типа изображений: в данном случае с = 9,8 (рис. 1, а), т. е. для изображений, энтропия которых больше c, использование предварительной обработки по L будет давать отрицательный результат. Применение вспомогательного «нечёткого» кластера в алгоритме k-means для контроля качества отделения объекта от фона В примере с изображением на рис. 3, а бинаризация выполнена некачественно: часть объектов искажена и потеряна. В подобных случаях необходимо осуществить дополнительный контроль с использованием «нечёткого» кластера в k-means. Как видно из рис. 1, б, предлагаемый алгоритм обеспечивает полностью автоматизированный контроль качества бинаризации. Определение, к какому кластеру «фон - объект» относится рассматриваемый пиксель, осуществляется следующим образом. 1. От каждой i-й точки-пикселя P вычисляются расстояния d1 и d2 до центров кластеров m = 1 и m = 2. 2. Точка P относится к тому кластеру, расстояние до центра которого является наименьшим. Степень принадлежности rm точки P к кластеру m можно вычислить по следующей формуле: . (4) Если rm > 0,5, то рассматриваемая точка P относится к кластеру m. Но это решение надёжно только при p1 или p2, близких к 1: например, если d1 << d2, тогда можно однозначно утверждать, что P относится к кластеру 1. В случае, если d1 и d2 отличаются друг от друга незначительно, такое решение ненадёжно. Выделим такие пиксели в «нечёткий» кластер m = 3: пусть точки, для которых не выполняется условие d1 << d2, составляют множество E. Это множество E состоит из «нечётких» пикселей (рис. 1, б), определяемых из следующего неравенства: , (5) где k - эмпирический коэффициент: k = 0,6. Заметим, что неравенство (5) эквивалентно неравенству max{p1, p2} < k. Проблемные точки результатов бинаризации, представленные на рис. 3, б, в, показаны на рис. 3, г. 3. Рассчитывается количество pE пикселей множества E от всего изображения, %: . (6) Если pE > y, где эмпирический порог y = 3 %, присутствует высокая вероятность некачественной бинаризации, когда надёжно отделить пиксели фона от пикселей объекта этим способом невозможно (в «нечётком» кластере могут быть участки изображения объекта, но это неизвестно). Например, для изображения на рис. 3, а pE = 11,344 %, что говорит о существенных проблемах при бинаризации. Расчёт показателя pE позволяет системе компьютерного зрения определить, насколько качественно была сделана бинаризация, а выделение «нечёткого» кластера позволяет визуально определить причину проблем (неравномерность освещения, тени, блики, искажённый спектр, механические повреждения фоновой поверхности и т. п.). Выделение связных областей с пикселями единичных объектов Этап бинаризации позволяет перейти, с применением алгоритма Хафа, от анализа изображения массового количества объектов к работе по отдельности с изображением единичного объекта - для распознавания, сбора статистики о распределении вероятностей определённых характеристик по поверхности единичных зёрен и т. д. Алгоритм Хафа относится к градиентным методам и может выполнить выделение единичных объектов только в том случае, если они окружены пикселями фона. Однако, если некоторые объекты соприкасаются друг с другом либо налагаются друг на друга, тогда результатом работы алгоритма будет изображение с группой таких касающихся или наложенных объектов (рис. 4). В этом случае алгоритм расценивает их как единый невыпуклый объект. Если же объекты находятся близко друг к другу, но не соприкасаются, тогда с помощью алгоритма Хафа происходит сегментирование исходного 2D-изображения на многоугольники и дальнейшее «разрезание» на изображения единичных объектов (рис. 4). Следует заметить, что применение методов сегментирования сразу ко всему исходному изображению массового количества объектов, для работы по отдельности с изображениями единичных объектов без этапа бинаризации, не оптимально ни по скорости, ни по точности и создает ряд дополнительных трудностей. Представляет интерес сравнение результатов работы предлагаемого алгоритма с подходом, не учитывающим конкретного приложения, - оценкой качества работы метода тестированием на общей базе изображений [8, 9], для которых известна «правильная» сегментация (например, Berkeley Segmentation Dataset and Benchmark - BSD [8] (рис. 5)). а б в Рис. 4. Результат работы алгоритма Хафа: а - определение границ каждого объекта; б - выделение единичного объекта в отдельное изображение; в - выделение группы касающихся объектов а б в г Рис. 5. Бинаризация изображения из базы BSD: а - пример исходного изображения BSD; б - бинаризация BSD; в - результат бинаризации по k-means и (1)-(6); г - контроль качества бинаризации по (4)-(6) Как видно из рис. 5, предлагаемый алгоритм успешно справляется с бинаризацией изображения и выделяет пиксели, бинаризация которых, возможно, была выполнена неправильно. Заключение Предложенный алгоритм бинаризации на основе кластеризации k-means с евклидовой метрикой удовлетворяет требованиям к скорости и точности, сочетает в себе предобработку изображения с применением вспомогательного «нечёткого» кластера в алгоритме k-means для контроля качества отделения объекта от фона. Использование предварительной обработки по компоненте L пространства LAB (когда IL < 8 и H < 9,8) позволяет сделать изображение более однородным и повышает качество его бинаризации по методу k-means, в котором целесообразно применять евклидову метрику. Когда H ≥ 9,8, выполнять предварительную обработку нецелесообразно из-за высокой однородности изображения. Когда IL > 8 и H < 9,8, перед исключением L необходимо добавить оттенок цвета по (2). Данная операция повышает качество бинаризации, контролировать которое позволяет расчёт показателя pE. Если pE > y, где эмпирический порог y = 3 %, тогда присутствует высокая вероятность некачественной бинаризации, когда надёжно отделить пиксели фона от пикселей объекта этим способом невозможно. Применение методов сегментирования сразу ко всему исходному изображению массового количества объектов для работы по отдельности с изображениями единичных объектов, без этапа бинаризации не оптимально ни по скорости, ни по точности и создает ряд дополнительных трудностей. Разработанный алгоритм позволяет устранить ряд сложностей, связанных с бинаризацией разного рода изображений: монохромных, с бликами, тенями и другими выбросами. Алгоритм имеет высокую точность и скорость; он способен функционировать в реальном времени благодаря использованию операций, имеющих низкую вычислительную сложность.
1. Computer Vision Technology for Food Quality Evaluation. Ed. by Da-Wen Sun, Published by Elsevier Academic Press, San Diego, CA, USA, 2011. 600 p.
2. Ziyatdinova V. A., Shazzo A. Yu., Usatikov S. V., Pogorelova I. I. Ocenka kachestva risa s ispol'zovaniem sovremennyh metodov analiza cvetovyh harakteristik edinichnyh zeren // Izv. vuzov. Pischevaya tehnologiya. 2015. № 2-3 (344-345). S. 100-104.
3. Ostapov D. S. Predobrabotka izobrazheniy dlya povysheniya effektivnosti binarizacii metodom k-srednih // Aktual'nye napravleniya nauchnyh issledovaniy 21 veka: teoriya i praktika: sb. nauch. tr. po mater. Mezhdunar. zaoch. nauch.-prakt. konf. Voronezh: VGLTU, 2015. № 8, ch. 1 (19-1). S. 108-112.
4. Ostapov D. S. Adaptivnyy algoritm k-means segmentacii izobrazheniy ob'ektov prirodnogo proishozhdeniya // VII nauch.-tehn. konf. «Tehnicheskoe zrenie v sistemah upravleniya - 2016» (Moskva, 15-17 marta 2016 g.). M.: IKI RAN, 2016. S. 70-71.
5. Kharinov M. V. Reclassification formula that provides to surpass K-means method // arXiv preprint, arXiv:1209.6204, 28 Sep 2012. 10 p. URL: http://arxiv.org/ftp/arxiv/papers/1209/1209.6204.pdf.
6. Stathis P., Kavallieratou E., Papamarkos N. An evaluation technique for binarization algorithms // Journal of Universal Computer Science. 2008. Vol. 14, no. 18. P. 3011-3030.
7. Belim S. V., Kutlunin P. E. Vydelenie konturov na izobrazheniyah s pomosch'yu algoritma klasterizacii // Komp'yuternaya optika. 2015. T. 39, № 1. C. 119-124.
8. Martin D., Fowlkes C. The Berkeley segmentation database and benchmark. Computer Science Department, Berkeley University, 2001. URL: http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/.
9. Harinov M. V. Baza dannyh optimal'noy segmentacii. URL: http://oogis.ru/index.php/tekhnologii/21baza-dannykh-optimalnoj-segmentatsii.
