БИНАРИЗАЦИЯ «ФОН - ОБЪЕКТ» ПРЕДОБРАБОТКОЙ ИЗОБРАЖЕНИЯ И НЕЧЕТКИМ АЛГОРИТМОМ K-MEANS
Авторы:
1.
Кубанский государственный технологический университет
Тип:
Статья
Страницы:
с 32
по 39
Статус:
Опубликован
Получено:
05.07.2016
Одобрено:
25.07.2016
Опубликовано:
25.07.2016
Классификаторы:
ВАК 05.12.2013 Системы, сети и устройства телекоммуникаций
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.9
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
ВАК 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
ВАК 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
ВАК 05.13.10 Управление в социальных и экономических системах
ВАК 05.13.18 Математическое моделирование, численные методы и комплексы программ
ВАК 05.13.19 Методы и системы защиты информации, информационная безопасность
УДК 004.9
ГРНТИ 20.01 Общие вопросы информатики
ГРНТИ 28.01 Общие вопросы кибернетики
ГРНТИ 49.01 Общие вопросы связи
ГРНТИ 50.01 Общие вопросы автоматики и вычислительной техники
ГРНТИ 82.01 Общие вопросы организации и управления
Язык материала:
русский
Ключевые слова:
бинаризация 2D-изображений, отделение объекта от фона, нечёткая кластеризация k-means
Аннотация (русский):
Рассмотрен этап бинаризации цветного 2D-изображения на связные области с пикселями объекта и фона в задачах идентификации с детальной оценкой системами компьютерного зрения состояния объектов природного происхождения и их массового количества, с высокой вариабельностью внутри классов, и близости самих классов. Предложен эффективный алгоритм бинаризации на основе кластеризации k -means с евклидовой метрикой, позволяющий устранить ряд сложностей при подборе алгоритмов для программной реализации в системах компьютерного зрения и удовлетворяющий требованиям к скорости и точности. Алгоритм сочетает в себе предобработку изображения с применением вспомогательного «нечёткого» кластера в алгоритме k -means для контроля качества отделения объекта от фона. Предобработка при определённых условиях исключает светлоту L цветовой шкалы CIELab (CIE 1976 Lab) из k -means.
Рассмотрен этап бинаризации цветного 2D-изображения на связные области с пикселями объекта и фона в задачах идентификации с детальной оценкой системами компьютерного зрения состояния объектов природного происхождения и их массового количества, с высокой вариабельностью внутри классов, и близости самих классов. Предложен эффективный алгоритм бинаризации на основе кластеризации k -means с евклидовой метрикой, позволяющий устранить ряд сложностей при подборе алгоритмов для программной реализации в системах компьютерного зрения и удовлетворяющий требованиям к скорости и точности. Алгоритм сочетает в себе предобработку изображения с применением вспомогательного «нечёткого» кластера в алгоритме k -means для контроля качества отделения объекта от фона. Предобработка при определённых условиях исключает светлоту L цветовой шкалы CIELab (CIE 1976 Lab) из k -means.
Ключевые слова:
бинаризация 2D-изображений, отделение объекта от фона, нечёткая кластеризация k-means
бинаризация 2D-изображений, отделение объекта от фона, нечёткая кластеризация k-means
Введение Бинаризация цветного 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. Зиятдинова В. А., Шаззо А. Ю., Усатиков С. В., Погорелова И. И. Оценка качества риса с использованием современных методов анализа цветовых характеристик единичных зерен // Изв. вузов. Пищевая технология. 2015. № 2-3 (344-345). С. 100-104.
3. Остапов Д. С. Предобработка изображений для повышения эффективности бинаризации методом k-средних // Актуальные направления научных исследований 21 века: теория и практика: сб. науч. тр. по матер. Междунар. заоч. науч.-практ. конф. Воронеж: ВГЛТУ, 2015. № 8, ч. 1 (19-1). С. 108-112.
4. Остапов Д. С. Адаптивный алгоритм k-means сегментации изображений объектов природного происхождения // VII науч.-техн. конф. «Техническое зрение в системах управления - 2016» (Москва, 15-17 марта 2016 г.). М.: ИКИ РАН, 2016. С. 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. Белим С. В., Кутлунин П. Е. Выделение контуров на изображениях с помощью алгоритма кластеризации // Компьютерная оптика. 2015. Т. 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. Харинов М. В. База данных оптимальной сегментации. URL: http://oogis.ru/index.php/tekhnologii/21baza-dannykh-optimalnoj-segmentatsii.
