Автоматика и телемеханика, № 12, 2014
Анализ данных
( 2014 г. А.М. МИХАЙЛОВ, канд. техн. наук (alxmikh@gmail.com) (Институт проблем управления им. В.А. Трапезникова РАН, Москва)
ИНДЕКСНЫЙ ПОДХОД К РАСПОЗНАВАНИЮ ОБРАЗОВ И ВИДЕОКЛИПОВ
Рассматривается колонковый классификатор как метод распознавания и кластеризации образов, основанный на понятии обратных образов. Этот подход заменяет операции сравнения неизвестных образов с образами-прототипами операциями пересечения обратных образов. Выполнение этих операций требует значительно меньшего объема вычислений, чем использование операций сравнения. Возможная аналогия с хешированием состоит в том, что признаки распознаваемого образа являются адресами, играющими роль аргумента хеш-функции, которые определяют имя класса образа без поисковых операций, как при хешировании. В качестве примера практической реализации описанного метода решается задача распознавания динамически изменяющихся образов, представленных видеоклипами.
1. Введение
Предложенный в настоящей статье колонковый классификатор (нейронный кортекс) - это многомерная индексная система для распознавания и кластеризации образов. Такая система относится к методам потоковой кластеризации, которые постоянно накапливают информацию, сохраняя без изменения ранее полученные данные. Примерами алгоритмов потоковой кластеризации являются STREAM [1], BIRCH [2], COBWEB [3], Vantage Point Trees (VP- деревья (выгодных точек)) [4] и др. Такие алгоритмы используют либо разбиение пространства поиска на подмножества для локального поиска (STREAM, BIRCH), либо различные древовидные структуры (COBWEB, COVER TREE, VP-деревья). При этом вычислительная сложность варьируется от O(N) до O(logN), где N - число точек (образов) в многомерном пространстве.
Колонковый классификатор был впервые предложен в [5-7]. Такой классификатор не использует разбиений и древовидных структур. При наличии достаточной оперативной памяти его вычислительная сложность не увеличивается с ростом числа образов. Это обстоятельство можно объяснить следующей аналогией. Действительно, время считывания из оперативной памяти по заданному адресу не зависит от того, имеется ли в наличии 1 Мбайт или 1 Гбайт памяти. Однако предложенный в [5-7] классификатор является не методом потоковой кластеризации, а методом распознавания.
Далее в статье рассматриваются: математическая постановка задачи и требования к колонковому классификатору, решающему задачу потоковой кла-
6* 139
стеризации, метод обратных образов, лежащий в основе колонкового классификатора, быстродействие метода и используемая им оперативная память. В статье также рассматриваются вопросы применения колонкового классификатора для распознавания динамически изменяющихся сцен, снимаемых веб-камерами.
2. Постановка задачи
Решаемая задача относится к классу задач потоковой (последовательной) кластеризации [8], а именно: каждый новый вектор x либо относится к одному из существующих кластеров, либо используется как начальная точка нового кластера в зависимости от расстояния между x и ближайшим к этому вектору кластером. Отличие рассматриваемого подхода к решению задачи другими поисковыми методами, упомянутыми в разделе 1, состоит в том, что предлагаемый метод позволяет уменьшать время поиска ближайшего соседа за счет увеличения объема оперативной памяти, а именно: быстродействие алгоритма ограничено только размером используемой памяти (при заданной аппаратной базе).
Математически задача ставится как традиционная задача поиска ближайшего соседа. Пусть дан N-мерный вектор x, набор N-мерных векторов P и порог расстояния S. Требуется найти ближайший к x вектор p € P, такой что
(1) Dp (p, x) = min max | pn — xn|,
pe{p} n=1,2,...,N
где max |pn — xn| - расстояние Чебышева между векторами p и x.
n=1,2,...,N
Разрабатываемый метод должен относиться к методам потоковой кластеризации. Последнее означает, что сначала множество P, состоящее из N-мерных векторов, пусто. По мере поступления новых данных происходит формирование новых кластеров следующим образом: если max |pn — xn| > S,
n=1,2,...,N
то включить вектор x в набор векторов P. В противном случае вектор x относится к кластеру, представляемому вектором p.
Широко используемый, но затратный в вычислительном отношении метод линейной минимизации (1) состоит в сравнении неизвестного вектора x со всеми векторами-прототипами из набора P или с векторами, представляющими категории или кластеры векторов-прототипов. Для методов линейного поиска вычислительная сложность (время поиска) характеризуется величиной порядка O(N ■ P), где N - размерность пространства и P - число образов-прототипов. Другие эффективные методы решения этой задачи связаны с использованием различных древовидных структур. В качестве примера можно привести метод Cover Tree (покрывающее дерево) [9]. Такое дерево можно рассматривать как иерархию уровней с корневой точкой на верхнем уровне. При этом нижний уровень дерева содержит все точки метрического пространства. Номер каждого уровня уменьшается на единицу по мере спуска. Колонковый классификатор (нейронный кортекс) основан на использовании обратных образов.
3. Обратные образы
Обратные образы строятся в соответствии со следующим утверждением. Заметим, что образом с именем п автор называет множество элементов Сп = = {с}. В случае К-мерных векторов, Сп = (в\, с2,..., ск)п.
Утверждение. Для каждого набора См = {сп,п ^ N} из N конечных образов существует набор обратных образов, в котором каждый обратный образ с - множество имен образов, содержащих общий для них элемент с.
Набор образов-прототипов обозначается См, а обратный набор - N0. Обратный набор N0 называется кортексом.
Пример. Для набора множеств г = {а,с}, у = {Ь,с,й}, и = {а,Ь}, х = = {а, й}, V = {й} набор обратных множеств имеет вид а = {г,и,х}, Ь = = {у,и,й}, с = {у,г}, й = {у,х}. Действительно, обратное множество а содержит имена г, и и х, поскольку элемент а принадлежит множествам г, и и х. Обратное множество Ь содержит имена у, и, так как элемент Ь принадлежит множествам у, и и х, и т.д.
Можно показать, что существует взаимно однозначное преобразование набора См в набор N0. Доказательство основано на представлении исходных образов и обратных образов с помощью матрицы, вертикальное измерение которой представляет имена п образов, а горизонтальное измерение - имена с элементов. В результате каждая колонка матрицы содержит имена образов, содержащих общий для них элемент. Доказательство использует то обстоятельство, что обратные образы могут быть получены из исходных образов путем транспонирования строк и столбцов этой матрицы. Однако матричное представление не используется для преобразования набора исходных образов См в набор обратных образов N0, содержащих имена исходных, так как такой подход связан с большими вычислительными затратами при больших наборах данных. В структурном отношении каждое обратное множество N0 представлено списком или колонкой, в которой имена образов лежат друг на друге без зазоров. Был разработан алгоритм, который преобразует См в колонки, содержащие имена исходных множеств. Этот алгоритм относится к классу потоковых алгоритмов, память которых постепенно обновляется с сохранением предыдущего содержания в процессе классификации постоянно поступающих образов. Такой алгоритм основан на следующей теореме.
Теорема. Пусть задан набор См = {Сп,п ^ N} из N конечных образов и некоторый образ (Ш = Ь + Т), имя х которого неизвестно. Тогда х = п тогда и только тогда, когда выполнены два условия:
(2) п = р| {п}с,
(3) |Сх| = |Сп|.
Т.е., во-первых, неизвестное имя можно найти только среди имен, находящихся в колонках, адреса которых равны значениям элементов образа Сх, и, во-вторых, длина (число элементов) образа с именем п равна длине идентифицируемого образа.
4. Основной алгоритм колонкового классификатора
Алгоритм колонкового классификатора - это некоторый способ нахождения пересечения (2). Можно построить различные алгоритмы, но все они будут являться теми или иными способами нахождения пересечения (2). Эффективным способом нахождения (3) служит гистограмма имен. Так как элементы (признаки) образа служат адресами колонок, то образ {с} выделяет некоторое подмножество колонок. Гистограмма Н(п), п € N имен образов, находящихся в колонках с адресами {с}, показывает, сколько раз каждое из имен встречается в выделенных колонках. Очевидно, что если
П мс
n =
VceCx
то тогда и только тогда пик гистограммы расположен над именем искомого образа
H (n) = max H (k).
кем
При этом его высота равна длине образа
H (n) = |СЛ|.
Отметим, что существуют схемы, позволяющие значительно сократить объем памяти, выделяемый на гистограмму, и время ее вычисления. Однако оставляем их за рамками данной статьи. Таким образом, алгоритм колонкового классификатора состоит в следующем.
1. Построить гистограмму имен, находящихся в колонках с адресами, равными значениям элементов неизвестного образа Cx.
2. Найти максимум H(n) этой гистограммы.
3. Если разность |H(n) — |Cx|| > S, где S - заданный порог расстояния, то входной образ заносится в колонковую память, т.е. создается новое имя, равное N + 1, а его |Cx| копий помещаются в колонки с адресами Cx.
4. В противном случае, т.е. если величина максимума близка к длине (размеру) входного образа |H(n) — |Cx|| ^ S, имя входного образа равно значению абсциссы, т.е. положению n найденного максимума на горизонтальной оси гистограммы.
В рассматриваемом далее Приложении будет использоваться иерархия колонковых классификаторов Nc ^ Мм ^ Lm ^ и др. Использование иерархии колонок целесообразно при решении задач анализа сцен с многочисленными объектами, при распознавании объектов с динамически изменяющейся формой и т.д. При этом образы первого уровня (например, локальные признаки контуров) активизируют колонки первого уровня, пересечения которых идентифицируют имена локальных признаков. Далее, найденные имена П1,П2,---,пк используются в качестве элементов образов второго уровня, активизирующих колонки второго уровня Мм, пересечения которых идентифицируют об
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.