Модель квазиоптимального машинного зрения

Размещено на http://www.allbest.ru/

Модель квазиоптимального машинного зрения

М.В. Харинов

Санкт-Петербургский институт информатики и автоматизации РАН

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

цифровой зрение квазиоптимальный

В ближайшие годы за рубежом, а также в России, ожидается создание унифицированных программно-алгоритмических решений проблемы выделения объектов на цифровых изображениях, именуемой «проблемой сегментации». Проблема возникает при распознавании цифровых изображений на первоначальной стадии «приведения данных к удобному для распознавания виду» (И.Б. Гуревич, 1985, [1]), «локализации объектов» (Ю.В. Визильтер и др., 2011, [2]), извлечения и упорядочения «глобально-локальной информации» (С.В. Абламейко и др., 2009, [3]), «квазиоптимальной разметки» изображения (П.А. Мельников и др., 2012, [4]). Суть проблемы состоит в недостаточной формализации понятия «объектов», которые «видит» или выделяет на изображении компьютер для последующего анализа признаков и идентификации.

В нашей модели понятия «изображение», «объект» и «кластер сегментов» формально не разграничиваются между собой. Сегментация трактуется как разделение изображения на вложенные изображения и допускается, что изображение, в общем случае, состоит из нескольких сегментов. В результате сегментации рассчитывается квазиоптимальная бинарная иерархия кластеров связных сегментов, которая отражает неоднозначную классификацию пикселей изображения. Тривиальные кластеры, состоящие из одинаковых пикселей, считаются элементарными изображениями, которые полагаются неделимыми. Особенностью модели квазиоптимального машинного зрения является то, что в дополнение к выделению объектов, для них автоматически генерируются инвариантные целочисленные обозначения, которые получаются в алгоритме изотонного преобразования средних по кластерам яркостей пикселей изображения, составляют инвариантные представления квазиоптимальных приближений и не меняются при предусмотренных преобразованиях или искажениях изображения. При этом инвариантные представления визуально воспроизводят квазиоптимальные приближения, задают иерархию последних и конвертируются одно в другое арифметическими преобразованиями значений своих пикселей.

Понятие инвариантного представления сигнала разработано в СПИИРАН для решения проблемы формализации понятия информации, кодированной в цифровом сигнале, и количества бит информации в элементе сигнала (Р.М. Юсупов, 1973 г., [5]). В 2008 г. оно запатентовано в приложении к задачам стеганографии (патенты РФ №№ 2006119273 и 2006119146). В модели квазиоптимального машинного зрения интерпретация цифровой информации развивается в приложении к обратной задаче автоматического выделения объектов на цифровом изображении.

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

, (1)

где , , -- тривиальные компоненты изображения, состоящие из одинаковых пикселей

Преобразование коммутирует с преобразованием :

, (2)

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

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

, (3)

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

, (4)

где -- тривиальная матрица из одинаковых пикселей, например, из одних 0. Таким образом, преобразование цветового изображения одинаково действует на одномерную компоненту в составе серого изображения из трех одинаковых цветовых компонент и монохромного изображения при обнулении остальных.

При заданном алгоритме разделения нетривиального кластера на пару вложенных, инвариантное представление , по существу, является результатом целочисленной «оцифровки» средних яркостей вложенных кластеров. Оно строится посредством кодирования знаков разностей средних яркостей вложенных кластеров в итеративном алгоритме, подобном алгоритму получения двоичного кода числа, в котором для учета при кодировании неделимых тривиальных кластеров используется не двоичное, а троичное значение коэффициентов разложения по степеням 2. При этом по результирующему инвариантному представлению посредством арифметических операций вычисляются предыдущие [6].

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

Если исходное или вложенное изображение является результатом слияния вложенных кластеров, то интегральное квадратичное отклонение значений пикселей этого изображения от среднего значения получается суммированием интегральных квадратичных отклонений для вложенных кластеров и некоторой неотрицательной добавки, характеризующей средний взвешенный разброс квадратов евклидовых попарных расстояний между центрами , кластеров и из и пикселей в цветовом RGB пространстве [7]:

(5)

где -- суммарная квадратичная ошибка для разбиения изображения на кластеров, -- суммарная квадратичная ошибка для разбиения изображения с единственным кластером, , -- число пикселей в рассматриваемом изображении. Если в качестве вложенных кластеров иметь в виду тривиальные кластеры, на которые распадается изображение, то сумма , очевидно, обращается в 0. Если в качестве тривиальных кластеров рассматриваются отдельные пиксели, то в выписанной формуле следует также положить и . Тогда она, с точностью до множителя, совпадает с выражением для дисперсии значений пикселей, которое активно применяется в [8-10] для теоретической и практической разработки методов кластеризации. Таким образом, формула (5) обобщает аналогичную формулу [8-10] на случай тривиальных кластеров из нескольких или многих пикселей.

Для случая пары вложенных кластеров, из (5) получаются выражения для приращений суммарной квадратичной ошибки при трех операциях с кластерами пикселей: операции слияния пары кластеров, операции коррекции кластеров посредством реклассификации подмножества пикселей из одного кластера в другой и операции дробления кластера за счет выделения подмножества пикселей в отдельный кластер [7].

Приращение суммарной квадратичной ошибки при слиянии кластеров и с числом пикселей , выражается через квадрат евклидова расстояния между трехмерными средними яркостями , в виде:

. (6)

Именно выражение (6) служит критерием слияния сегментов изображения в версиях [7, 11] модели сегментации Мамфорда-Шаха [12], и либо с аддитивной добавкой, либо с дополнительным множителем используется в версиях [13, 14] модели. В отличие от модели Мамфорда-Шаха, в нашей модели сегментации минимизация суммарной квадратичной ошибки достигается не только за счет слияния смежных сегментов изображения, а может выполняться также и на множестве всевозможных пар кластеров, как в методе Уорда [15], что существенно улучшает качество приближений, особенно при малом числе кластеров или сегментов изображения.

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

, (7)

где , -- число пикселей в кластерах и .

При коррекции вложенных кластеров множества пикселей в них меняются. Поэтому обе иерархии множеств пикселей вложенных кластеров приходится каждый раз обновлять, обрабатывая кластеры как самостоятельные изображения. Выражение (7) продуктивно тем, что позволяет вывести классический метод K-средних (K-means, [16]) и обобщенный метод "K-meanless" [8], который в нашей версии [7], наряду с операциями с отдельными пикселями, предусматривает операции с наборами пикселей.

Приращение суммарной ошибки при дроблении кластера со средним значением пикселей за счет выделения в новый кластер его пикселей со средним значением описывается формулой:

, (8)

При применении формулы для оптимизации дробления кластеров по критерию важно, что множество кластеров в (8) полагается сформированным, например, по алгоритмам слияния кластеров, использующим (6), и при дроблении учитывается расширенное множество кластеров. Поэтому дробление кластера, полученного итеративным слиянием вложенных кластеров, при обратном увеличении числа кластеров на единицу снижает или, по крайней мере, не увеличивает значение . Особенностью алгоритмов дробления на основе формулы (8) является обновление иерархии кластеров, которое при очередной модификации выполняется для кластера, как для отдельного изображения.

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

, (9)

и оказывается серым, что не является тривиальным свойством, так как оно нарушается, например, при преобразовании одной из исходных цветовых компонент в негатив. Если пиксели инвариантного представления трактовать как автоматически генерируемые обозначения, метки объектов, то совпадение меток согласуется с тем, что пиксели одних и тех же объектов в различных цветовых компонентах должны помечаться одинаковыми обозначениями. Обнаруженное свойство планируется проиллюстрировать в докладе на примере выделения объектов на дистанционном изображении из 15 млн. пикселей.

Таким образом, по сравнению с моделью сегментации Мамфорда-Шаха, в нашей модели комбинированной сегментации/кластеризации число базовых операций с множествами пикселей изображения утроено, что обеспечивает достоверную оптимизацию качества приближений изображения по суммарной квадратичной ошибке или среднеквадратичному отклонению приближения от изображения. Судя по нашему опыту [7,17], система элементарных формул (6)-(8) обеспечивает эффективную разработку и развитие алгоритмов достоверной оптимизации качества приближений изображения, и, что не менее важно, позволяет уточнить интерпретацию классических методов [12, 15, 16], потенциал которых в приложении к цифровым изображениям, по всей видимости, еще далеко не исчерпан.

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

Еще 35-40 лет назад типичной задачей при расчетах на ЭВМ являлось сжатие данных без потерь, которой занималось множество программистов для решения конкретных проблем хранения и передачи информации. В настоящее время, этой задачей продолжает заниматься узкий круг профессионалов, а остальные специалисты пользуются готовыми программами. Вполне вероятно, что автоматическое выделение объектов на цифровых изображениях окажется следующей проблемой, для которой будут найдены общеупотребительные решения, превосходящие известные по установленным критериям качества. В нашем варианте аппроксимации изображения иерархической последовательностью квазиоптималь-ных приближений требуемым критерием является максимальная близость приближений к изображению по суммарной квадратичной ошибке, эффект минимизации которой планируется продемонстрировать в докладе

Литература

Gurevich I., Trusova Yu., Yashina V. The challenges, the problems and the tasks of the decsriptive approach to image analysis // Proc. 11-th. Int. Conf. on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-11-2013). Sept. 23-28 2013. Vol. 1, -- pp. 30-35.

Визильтер Ю.В., Желтов С.Ю. Проблемы технического зрения в современных авиационных системах // Механика, управление и информатика, 2011. .№6, -- С. 11-44.

Абламейко С.В., Недзьведь А.М., Белоцерковский А.М., Руцкая Е.А. Сегментация трехмерных изображений компьютерной томографии на основе глобально-локальной информации // Вестник Белорусского госуниверситета. Сер. 1, Физика. Математика. Информатика, 2009. .№ 1, -- С. 58-64.

Мельников П.А., Копылов А.В. Алгоритм поиска квазиоптимальной разметки для обработки изображений с построчным комбинированием переменных // Известия Тульского государственного университета. Естественные науки, 2012. № 1, -- С. 119-129.

Юсупов Р.М. Теоретические основы прикладной кибернетики. Вып.1. Элементы теории информации. Л.: ВИКА им. А.Ф.Можайского, 1973. -- 110 с.

Харинов М.В. Запоминание и адаптивная обработка информации цифровых изображений / Под ред. Р.М. Юсупова. СПб.: Изд-во С.Петерб. ун-та, 2006. -- 138 с.

Харинов М.В. Обобщение трех подходов к оптимальной сегментации цифрового изображения // Труды СПИИРАН, 2013. Вып. 2(25), -- С. 294-316.

Dvoenko S.D. Meanless k-means as k-meanless clustering with the bi-partial approach // Pattern Recognition and Information Processing (PRIP'2014) / Proc. of the 12th Int. Conf., Minsk, 2014. -- pp. 50-54.

Dvoenko S.D. Clustering of a set of objects// Pattern Recognition and Information Processing (PRIP-2007) / Proc. of the 9th Int. Conf., Minsk, 2007. Vol. 1. -- pp. 93-97.

Двоенко С.Д. Неиерархический дивизимный алгоритм кластеризации // Автоматика и телемеханика, 1999. №4, -- C. 117-124.

Бугаев А.C., Хельвас А.В. Поисковые исследования и разработка методов и средств анализа и автоматического распознавания потоковой информации в глобальных информационных системах. Шифр «Лацкан» // Отчет по НИР. М.: МФТИ, 2001. Том 1, - 140 с.

Mumford D., Shah J. Boundary detection by minimizing functionals, I // Proc. IEEE Comput. Vision Patt. Recogn. Conf., San Francisco, 1985.-- pp. 22-26.

Redding N.J., Crisp D.J., Tang D.H., Newsam G.N. An efficient algorithm for Mumford-Shah segmentation and its application to SAR imagery // Proc. Conf. Digital Image Computing Techniques and Applications (DICTA '99). 1999. -- pp. 35-41.

Koepfler G., Lopez C., Morel J. A Multiscale Algorithm for Image Segmentation by Variational Method // SIAM J. on Numerical Analysis, Vol. 31, № 1, 1994. -- pp. 282-299.

Ward J.H., Jr. Hierarchical grouping to optimize an objective function. // J. Am. Stat. Assoc. 1963. Vol. 58, Issue 301, -- pp. 236-244.

Jain A.K. Data Clustering: 50 Years Beyond K-Means // Pattern Recognition Letters, Vol. 31, No. 8, 2010. -- pp. 651-666.

Kharinov M.V. Image Segmentation Using Optimal and Hierarchical Piecewise-Constant Approximations // Pattern Recogn. Image Anal.: Adv. Math. Theory Appl. 2014. Vol. 24, №.2, -- pp. 409-517.

Размещено на Allbest.ru