Введение Бинаризация цветного 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 8 и H < 9,8, перед исключением L необходимо добавить оттенок цвета по (2). Данная операция повышает качество бинаризации, контролировать которое позволяет расчёт показателя pE. Если pE > y, где эмпирический порог y = 3 %, тогда присутствует высокая вероятность некачественной бинаризации, когда надёжно отделить пиксели фона от пикселей объекта этим способом невозможно. Применение методов сегментирования сразу ко всему исходному изображению массового количества объектов для работы по отдельности с изображениями единичных объектов, без этапа бинаризации не оптимально ни по скорости, ни по точности и создает ряд дополнительных трудностей. Разработанный алгоритм позволяет устранить ряд сложностей, связанных с бинаризацией разного рода изображений: монохромных, с бликами, тенями и другими выбросами. Алгоритм имеет высокую точность и скорость; он способен функционировать в реальном времени благодаря использованию операций, имеющих низкую вычислительную сложность.