Шаблон кластеризации на основе моделирования шума в волновом пространстве просмотров: 1490
Шаблон кластеризации на основе моделирования шума в волновом пространстве.
Точечный шаблон кластеризации составляет одно из основных направлений в кластерном анализе. Мерта и Старк [1998] описывают эффективный подход к объектам или функции обнаружения в точечном шаблоне с помощью моделирования шума. В данной работе появляются два преимущества, а именно: (1) многомасштабный подход к волновым преобразованиям очень эффективен для вычислений, (2) прямая обработка шума и помех, что приводит к улучшению кластерного обнаружения. При таком подходе моделирование шума основано на пуассоновском процессе, и применяется непирамидальное (или резервное) волновое преобразование.
С учётом плоского точечного шаблона, 2-D изображение создаётся следующим образом:
• подготовка набора (х, у, 1), когда точка координат (х, у) имеет единичное значение;
• проектирование на плоскость с помощью регулярной дискретной сетки (изображения) и передачу точечной доли пикселям изображения посредством функции интерполяции, используемой волновыми преобразованиями, относят к ажурному алгоритму с кубическим B-сплайном.
•ажурный алгоритм затем используют для результирующего изображения.
Значимые структуры извлекаются на каждом уровне волнового разложения, в зависимости от модели шума для исходного изображения (х, у, 1).
Подробное описание непирамидального (или резервного) волнового преобразования можно найти у Шенса [1992]. Резюме "ажурного" волнового преобразования представлено ниже:
Шаг 1. Инициализировать i до 0 , начиная с изображения сi(k), т.е. с0(k), которое является входным изображением. Индекс k пробегает все пиксели изображения.
Шаг 2. Для увеличения i и после этого проводят дискретные свёртывания изображения с фильтром h с получением ci−1(k). Расстояние между центральным и соседними пикселями равно 2i−1. Следует отметить, что фильтр h основан на кубическом B-сплайне (фильтр 5×5).
Шаг 3. Для получения дискретного волнового преобразования: wi(k) = ci−1(k) − ci(k).
Шаг 4. Чтобы вернуться к шагу 2, если i меньше желаемого количества уровней разрешения (примем р за количество уровней разрешения).
В результате получается множество,
W = {w0, w1, ..., wp, cp}
представляющее собой волновое преобразование изображения, где cp обозначает остаточную величину. Таким образом, следующее добавочное разложение может быть применено к входному изображению, c0(k):
p
c0(k)= cp + . wi(k).
i=1
Рис. 1,20 показывает множество точечного шаблона, который является моделируемым гауссовским кластером с 300 и 259 точками, и шумовой фон Пуассона с 300 точками. На рис. 1.21 представлены соответствующие волновые преобразования. Волновые шкалы 1-6 показаны в последовательности слева направо, начиная с верхнего левого угла.
Изображения и наборы точечных шаблонов обычно содержат шум. Таким образом, волновые коэффициенты слишком шумные. В большинстве случаев, необходимо знать, если волновой коэффициент получают из сигнала (т. е. он является значимым), или из шума [Мерта и Старк, 1998] развивается статистический критерий значимости для решения этой проблемы. Он определяет, что
P = P rob(|wj | < τ ),
где τ обозначает порог обнаружения, определяемый для каждой шкалы. С учётом оценки порога s, если P < s, значение волнового коэффициента не может продлеваться из-за шума и значимый волновой коэффициент может быть обнаружен.
Кратномасштабная опора может быть получена путём обнаружения значимых коэффициенты на каждом уровне масштаба. Кратномасштабная опора определяется следующим образом [Старк и др., 1995].:
Краткий обзор распознавания волновой теории
Пример точечного шаблона [Мерта и Старк, 1998].
M (j, x, y)=
. 1 если wj (x, y) является значимым,
0 если wj (x, y) не имеет существенного значения.
Алгоритм для создания кратномасштабной опоры представлен ниже:
Шаг 1. Чтобы вычислить волновое преобразование изображения;
Шаг 2. Чтобы оценить стандартное отклонение шума в каждом масштабе и после этого вывести статистически значимые коэффициенты на каждом уровне масштаба;
Шаг 3. Чтобы логически измерить каждую шкалу, что может привести к кратномасштабной опоре;
Шаг 4. Для коррекции, с использованием априорного знания, если это необходимо.
Рис. 1,21 волновое преобразование точечного шаблона с масштабами 1-6 [Мерта и Старк, 1998].
Для того чтобы визуализировать кратномасштабную опору, мы можем создать изображение S, определяемое при помощи
p
S(x, y)= . 2j M (j, x, y). (1.6)
j=1
Рис. 1,22 связан с изображением кратномасштабной опоры 5-ого масштаба изображения на рис. 1.21.
Рис. 1,22 Изображение кратномасштабной опоры на 5-м уровне масштаба волнового изображения точечного шаблона, показанного на рис. 1,20
[Мерта и Старк, 1998].
[Мерта и Старк, 1998] используют этот метод для решения трёх примеров: (1) совершенное восстановление гауссовых кластеров, (2) диффузный прямоугольник кластера, и (3) диффузный прямоугольник и размытый гауссов кластер. Результаты показывают, что вычислительная сложность O (1).
1.2.5 Анализ документов с помощью волн.
Обработка документов является одной из самых активных отраслей в области распознавания изображений. Документы содержат знания. Именно они являются посредниками передачи знаний. В самом деле, если привести несколько примеров, множество знаний приобретается из таких документов, как технические отчёты, правительственные файлы, газеты, книги, газеты, журналы, письма, банковские чеки. Приобретение знаний из таких документов информационной системы может включать в себя большой объём ремесленной обработки. Эта ремесленная обработка занимает много времени и может серьёзно ограничить применение информационных систем. Фактически это является узкой специализацией информационных систем. Таким образом автоматическое получение знаний из документов стало важной темой. Начиная с 1960-х гг проводились многие исследования по обработке документов [Тан и соавт., 1994]. В последнее время в данном исследовании была использована волновая теория [Лян и др., 1999; Тан и др., 1995a; Тан и др., 1996a; Тан и др., 1997a; Тан и др., 1997c].
В этой книге у нас есть глава, дающая подробное представление по основам волновой обработки документов. В данном подразделе ниже представлено ещё одно достижение:
1. Анализ форм и документов по определению опорных линий с 2-D волновым преобразованием.
Основные характеристики формы проанализированы в [Тан и др., 1997a]:
• В целом форма состоит из прямых линий, в основном ориентированных в горизонтальном и вертикальном направлениях. Эти линии называют опорными линиями.
•Опорные линии печатаются заранее, чтобы побудить пользователей заполнить форму.
•Информация, которая должна быть введена в компьютер и обработана, - это, как правило, заполненные данные.
• Для того чтобы указать заполняемую позицию, могут использоваться опорные линии, и вводимая информация обычно появляется либо выше этих опорных линий, либо ниже их, либо рядом с ними. Таким образом, опорные линии должны быть обнаружены в форме обработки, потом на их основе мы можем найти полезную информацию из формы, а затем ввести её в компьютер.
В [Тан и соавт., 1997а], представлен новый метод волновых преобразований. В этом методе двумерные кратномасштабного анализа (MRA), разложение волнового алгоритма и конечные ортонормированные всплески используются для преобразования изображения документа на несколько вспомогательных изображений. На основе этих вспомогательных изображений, опорных линий можно извлечь комплексно-справочный документ и получить сведения о геометрической структуре документов, представляющих исторический интерес. В частности, такой подход представляется более эффективным при обработке форм документов с мульти-уровнем серого фона.
Изображение документа может быть преобразовано в четыре подгруппы изображений, применяя алгоритм Мэллета, а именно: (1) вспомогательное изображение LL, (2) вспомогательное изображение LH, (3) вспомогательное изображение HL и (4) вспомогательное изображения HH. Для нас представляют интерес вспомогательные изображения LH и HL. Вспомогательное изображение LH достигается с помощью фильтра, который допускает низкочастотные компоненты для достижения с помощью продольного горизонтального направления, а также более высокие частоты в вертикальном направлении. То есть, эффект "усиления" по вертикали и эффект "сглаживания" по горизонтали. Как результат, во вспомогательном изображении LH остаются только горизонтальные линии. Положение вспомогательного изображения HL является противоположным положению изображения LH. Таким образом, горизонтальное направление фильтра открывается наиболее высокими частотами и вертикальным направлением для низкочастотных компонент. То есть, эффект "усиления" по горизонтали и эффект "сглаживания" по вертикали. Таким образом, во вспомогательном изображении HL остаются только вертикальные линии.
2. Кратномасштабное представление Адамара и его применение в анализе изображений документов.
Новую группу волновых преобразований называют кратномасштабными.
Представление Адамара (MHR) разработано Ляном и соавторами [1999] для анализа документа изображения.
Кратномасштабное представление Адамара (MHR) является двоичным 2-D волновым представлением, которое использует два коэффициента Адамара [1, 1, 1, 1] и [1, -1, -1, +1], как показано на рис. 1.23. Эти коэффициенты ещё не приведены в соответствие с соблюдением нормы LL [Мэллет, 1989c].
Это двумерное волновое представление получается путём применения одномерных фильтров h(·) и g(·) к двумерному изображению как в горизонтальном направлении, так и в вертикальном. Это представление включает в себя четыре канала, а именно: низкопроходный L, горизонтальный H, вертикальныйV и диагональный D, на каждом уровне преобразования. Эти каналы могут быть определены следующими итерационными формулами:
Lu,v,j+1 = Hu,v,j+1 = Vu,v,j+1 = Du,v,j+1 = ¸ ¸
Lu,v,j h(x − 2u)h(y − 2v),
x y
¸ ¸
Lu,v,j h(x − 2u)g(y − 2v),
x y
¸ ¸
Lu,v,j g(x − 2u)h(y − 2v),
x y
¸ ¸
Lu,v,j g(x − 2u)g(y − 2v),
x y
где x и u являются горизонтальными координатами, y и v являются вертикальными. Обратите внимание, что когда j= 0, то Lu,v,j обозначает исходное изображение.
Канал L(j+1) получают путём свёртки Lj с двумерным фильтром h(x)h(y), показанным на рис. 1.24. Канал H(j+1)(V(j+1) получен путём свёртки Lj Lj с двумерным фильтром h(x)g(y)(h(y)g(x)).
a)
b)
Рис. 1,23. Основные функции кратномасштабного представления Адамара (MHR): (а) низкочастотного фильтра h (-) , (б) высокочастотного фильтра g (-) [Лян и др., 1999].
Поскольку форма h(x)g(y)(h(y)g(x)) похожа на горизонтальный (вертикальный) штрих, этот 2-D фильтр служит в качестве детектора горизонтальных (вертикальных) штрихов на Lj , которые могут быть графически представлены на рис. 1.25.
Канал D(j+1) получается путём свёртки Lj с 2-D фильтром g(x)g(y). Графически он отображён на рис 1.26.
В работе [Лян и др., 1999], кратномасштабное представление Адамара (MHR) применяется для анализа изображений в документах, включающего следующие процессы:
• поиск полутоновых изображений,
• сегментация изображений в документах в текстовые блоки и
• определение шкалы символов для каждого текстового блока.
Преобразованные значения вертикальных штрихов символов очень положительны в некоторых каналах V, в то время как горизонтальные штрихи символов дают сильную реакцию в каналах H. Диагональные штрихи символов, с другой стороны, дают реакцию в обоих каналах H и V. Фотографии в газетах, как правило, проецируются в полутонах, где тон фотографий произведён малыми точками блоков с различной плотностью.
Рис. 1,24. L Каналы L двумерных фильтров h(·)g(·) [Лян и соавт., 1999].
Рис. 1,25. Каналы H и V двухмерных фильтров h(·)g(·) [Лян и соавт., 1999].
В то время как символы демонстрируют свои сильные стороны в каналах H и V, полутоновое изображение реагирует как значимый регулярный шаблон в канале D. Эта модель производится, когда полутоновые изображения фильтруются с помощью (g(x)g(y)).
В работе [Лян и соавт., 1999], кратномасштабное представление Адамара (MHR) используется для обработки фрагмента китайской газеты, как показано на рис. 1.27.
Рис. 1,26. Канал D двумерных фильтров h(·)g(·) [Лян и соавт., 1999].
Рис. 1,27. Фрагмент китайской газеты [Лян и соавт., 1999].
Он содержит китайские иероглифы трёх различных размеров. Кратномасштабное представление Адамара, изложенное в [Лян и соавт., 1999], снимает с исходного изображения три текстовых блока с разными масштабами, представленных на рис. 1,28. Кратномасштабное представление Адамара с рис. 1,27 показано на рис. 1,29 , где масштаб j = 1.
Подробное описание можно найти в работе [Лян и соавт., 1999].
Рис. 1.28. Три текстовых блока с различным масштабом [Лян и соавт., 1999].
1.2.1 Анализ и выявление волновых особенностей.
Значительным применением волновой теории является анализ сингулярностей. Многие методы, основанные на волновой теории, были разработаны, чтобы анализировать свойства сингулярностей и отличать их от различных сигналов/изображений; некоторые примеры можно найти в [Чен и др., 1995; Чен и Ян, 1995; Чжуан и Куо, 1996; Ден и Лиенгар, 1996; IEEE, 1993; Лоу и др., 1996; SPIE, 1994; Тан и др., 1997c; Тан и др., 1998d; Тьюн и др., 1997; Чень и Боулз, 1997а; Ян, 1993]. Кромка является одним из классов сингулярностей, которые обычно появляются и в одномерных сигналах, и в двумерных изображениях. Предметом волновых преобразований является замечательный математический инструмент для анализа сингулярностей, включая края, и в дальнейшем, для эффективного их обнаружения. Значительные исследования, связанные с этой научной темой, были сделаны Мэллетом и Хван Чжун и опубликованы в специальном выпуске IEEE "О волновых преобразованиях и анализе кратномасштабных сигналов" (цит. по "Информационной теории" [Мэллет и Хван, 1992]) и по "Анализу шаблонов и искусственному интеллекту" [Мэллет и Чжун, 1992]).
Углы - это особый тип кромки, которые являются очень привлекательной характеристикой многих приложений в распознавании шаблонов и компьютерном видении.
Рис. 1,29. Кратномасштабное представление Адамара с рис. 1,27 в масштабе j=1 [Лян и соавт., 1999].
В [Чен и соавт.,1995] представлен новый сложноуровневый алгоритм обнаружения угла, основанный на волновых преобразованиях. Волновое преобразование используется потому, что масштабное развитие его величин и направлений может употребляться для характеристики локализованных сигналов, таких как кромки, и в том числе углы. Большинство обычных угловых детекторов обнаруживают углы, основываясь на информации обнаружения кромки. Однако эти детекторы кромки плохо функционируют в углах, при этом, напротив, усиливая свою всеобщую производительность. Чтобы справиться с этим недочётом, [Чен и соавт., 1995] прежде всего предлагают новый детектор кромки на основе соотношений между масштабами модулей волновых преобразований. Этот детектор кромки может правильно определить кромки на угловых расположениях, что делает обнаружение возможного угла точным. Чтобы уменьшить количество точек, необходимое для обработки, он применяет неминимальное сжатие схемы к краю изображения и извлекает минимальное изображение. На основании дисперсии ориентации эти неугловые точки кромки устраняются. Для того чтобы найти угловые точки, он предлагает новый индикатор угла на основе масштаба инвариантного свойства угловой ориентации. При исследовании углового индикатора угловые точки могут быть точно расположены, как показывают эксперименты с алгоритмом. Кроме того, поскольку волновое преобразование по своей сути обладает эффектом сглаживания, этот алгоритм вдобавок нечувствителен к шумовому загрязнению.
1. Определение кромки с местным максимальным модулем волнового преобразования.
Важное исследование, связанное с этой научной темой, проведено Мэллетом, Хваном и Чжуном [Мэллет и Хван, 1992; Мэллет и Чжун, 1992]. Многие значительные вклады в науку хранятся в их документах. Они доказали, что максимумы модулей волнового преобразования могут обнаружить местоположение нерегулярных структур. Кроме того, предоставляются числовые процессы для вычисления их Липшиц-экспонентов. Это также численно доказывает, что одно- и двумерные сигналы могут быть восстановлены, с сильной относительностью, из локальных максимумов их модулей волнового преобразования. Алгоритм обнаружения кромки с местными максимальным модулем волнового преобразования представлен ниже:
Алгоритм 1.1 С учётом входного цифрового сигнала
{f (k, l)|k = 0, 1, ··· ,K; l = 0, 1, ··· , L}
Шаг 1. Для расчёта модуля его волнового преобразования,
{Msf (k, l)|k = 0, 1, ··· ,K; l = 0, 1, ··· , L}
также как и кодов
{CodeAsf (k, l)|k = 0, 1, ··· ,K; l = 0, 1, ··· , L}
по градиентным направлениям;
Шаг 2, чтобы достичь порога T > 0, принимая k = 0, 1, ··· ,K; l = 0, 1, ··· , L, если
(1) |Msf (k, l)|≥ T ,
(2) |Msf (k, l)| достигает своего локального максимума по градиентному направлению, представленному CodeAsf (k, l),
тогда (k, l) является краевым пикселем.
2. Обнаружение пошаговой структуры кромки масштабонезависимым алгоритмом и волновым преобразованием MASW.
Локальные максимумы модулей волнового преобразования могут обеспечить достаточно информации для анализа сингулярностей и могут обнаружить все сингулярности. Тем не менее, они не могут распознавать различные структуры сингулярностей [Мэллет и Хван, 1992; Мэллет и Чжун, 1992].
В [Тан и соавт., 1998c] доказывается важное свойство, а именно то, что модуль волнового преобразования в каждой точке кромочной ступени является ненулевой константой, которая не зависит как от градиентного направления, так и от масштаба волнового преобразования. Таким образом, разработан новый алгоритм, называющийся масштабонезависимым алгоритмом.
Загружено переводчиком: Ушакова Юлия Сергеевна Биржа переводов 01
Язык оригинала: английский