АДАПТИВНОЕ РАСПОЗНАВАНИЕ СИМВОЛОВ. (В. Л. Арлазаров, В.В. Троянкер, Н.В. Котович). ПРОДОЛЖЕНИЕ

КЛАСТЕРИЗАЦИЯ. Необходимость разбиения совокупности объектов на несколько групп нередко возникает в самых разных областях знаний - как, например, классификация различных видов бабочек в биологии или классификация языков Новой Гвинеи в лингвистике. Задачей кластеризации и называется задача расклассификации предъявленных объектов по нескольким группам, причем число групп не обязательно известно. Каждую полученную группу часто называют кластером. Существуют разные математические методы и подходы к решению задачи кластеризации [1].

Одним из методов является метод цепной развертки, кратко опишем его. В этом методе в качестве исходного берется любой объект из предъявленной совокупности , ему приписывается номер 1 и расстояние 0. Затем просматриваются все оставшиеся объекты. Выбирается объект, расстояние от которого до исходного элемента минимально. Ему присваивается номер 2 и расстояние, равное расстоянию до исходного объекта. Затем среди оставшихся ищется объект, расстояние от которого до уже отмеченного множества объектов из двух элементов минимально, и т.д. - всегда на очередном шаге выбирается объект, расстояние от которого до уже пронумерованных объектов ( как расстояние до множества ) минимально, ему приписывается очередной номер и это расстояние. Процедура повторяется пока все объекты не будут пронумерованы. В результате все объекты будут выстроены в некотором порядке, и каждому объекту приписано некоторое число - расстояние до предшествующего множества.

Теперь для того, чтобы разделить исходное множество на несколько кластеров таким образом, чтобы расстояние между любыми объектами, входящими в разные кластеры, было больше заданного расстояния d0, а для любых объектов из одного кластера (p1,p2) можно было найти объекты из того же кластера (обозначим их o[1],o[2],,o[n]) , такие что o[1]=p1, o[n]=p2, и для любого i, i < n расстояние между соседними объектами d(o[i],o[i+1]) не больше d0, достаточно просто просмотреть все приписанные объектам расстояния и пометить те из них, которые больше d0. Пусть это будут номера N1,N2,...,Nk. Тогда к первому кластеру следует отнести все объекты с номерами меньше N1, ко второму все объекты с номерами от N1 до N2 и т.д. После процедуры цепной развертки также легко проводить анализ - при каких значениях порога d0 возникают разные варианты кластеризации, как эти варианты соотносятся между собой и многое другое. Но как легко видеть, данная процедура требует N*(N-1)/2 процедур вычисления расстояния между объектами, если всего имеется N объектов, поэтому бывает необходимо в связи с повышением быстродействия использовать иные приемы. Примером как правило более быстрого варианта кластеризации можно привести модификацию описанного выше метода - кластеризацию с фиксированным порогом. В качестве исходного берется любой символ, ему присваивается принадлежность к первому кластеру. К данному первому кластеру присоединяются все символы, принадлежность которых к какому-либо кластеру еще не установлена, и расстояние от которых до исходного символа меньше порога d0. Затем для каждого из вновь присоединенных символов данная процедура повторяется . После того как к первому кластеру никто не может быть больше отнесен, среди символов, которые остались, берется произвольный символ в качестве затравочного для второго кластера и т.д. пока не будут исчерпаны все символы. В худшем случае и здесь при наличии N символов надо N*(N-1)/2 процедур вычисления расстояния, но в лучшем случае всего N процедур.

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

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

Кратко напомним определение метрики Хаусдорфа. Пусть в некотором пространстве определено расстояние между точками, обозначим его d(x,y). Тогда расстояние от точки x до множества Y d(x,Y) определяется как нижняя грань расстояний d(x,y) для y из Y. Расстояние от множества X до множества Y d1(X,Y) определяется как верхняя грань расстояний d(x,Y) для всех x из X. Расстояние Хаусдорфа между множествами X,Y d(X,Y) определяется как максимум расстояний от X до Y и от Y до X, т.е. d(X,Y)=max(d1(X,Y),d1(Y,X)). Таким образом, разные множества в метрике Хаусдорфа близки, если и только если для любой точки из одного множества в ее малой окрестности содержится хотя бы одна точка другого множества (и то же самое для другого множества).

В случае символов можно рассматривать расстояние между символами как расстояние Хаусдорфа между множествами точек, составляющих разные символы. Но необходимо заметить, что вычисление расстояния Хаусдорфа "в лоб" требует слишком много вычислений даже для проверки того, что это расстояние между символами больше или не больше единицы. Для того чтобы проверить все точки растра, надо проверить каждую точку - черная она или белая, т.е. принадлежит символу или нет, и если принадлежит, надо проверить до восьми ее соседей, т.е. при средней заполненности растров на четверть и при размерах растров m на n может потребоваться до 2*(m*n*3/4+m*n*9/4)=6*m*n элементарных операций.

Поэтому полезно использовать некоторые приемы для оценки расстояния Хаусдорфа. Для эффективного вычисления расстояния между символами используется следующий прием. Для каждого символа помимо собственно изображения создается растр, в котором кроме исходных точек содержатся также точки окрестности ("размазанное" изображение). После чего вычисление расстояния между символами сводится к простому выявлению пикселов одного растра, которые не вошли в "размазанное" изображение другого символа. Таким образом требуется одна операция для одного байта (для восьми пикселов) растра - исключающее "или", или две операции - если надо узнать и количество пикселов, выходящих за рамки единичной (или иной) окрестности. Следовательно надо не больше 2*(m*n*2/8)=m*n/2 элементарных операций.