Обработка изображений / Контурный анализ Опции

[Decker]

Cтатья описывает теоретические основы контурного анализа и аспекты его практического применения для распознавания изображений.

Первая часть статьи содержит основные определения и теоремы контурного анализа. Я постарался выделить главные моменты, которые позволяют достаточно быстро понять суть контурного анализа, и начать его применение на практике. Также, я добавил кое-что от себя. В основном это касается некоторых аспектов теории, которые недостаточно ясно изложены в теоретических трудах, а также вопросы оптимизации алгоритмов контурного анализа. Этому посвящена вторая часть статьи. Там же приводятся результаты работы алгоритмов, описаны проблемы и недостатки данного метода.








Основы контурного анализа



Зачем нужен контурный анализ (КА)


КА позволяет описывать, хранить, сравнивать и производить поиск объектов, представленных в виде своих внешних очертаний – контуров.



Предполагается, что контур содержит всю необходимую информацию о форме объекта. Внутренние точки объекта во внимание не принимаются. Это ограничивает область применимости алгоритмов КА, но рассмотрение только контуров позволяет перейти от двумерного пространства изображения – к пространству контуров, и тем самым снизить вычислительную и алгоритмическую сложность.



КА позволяют эффективно решать основные проблемы распознавания образов – перенос, поворот и изменение масштаба изображения объекта. Методы КА инвариантны к этим преобразованиям.




Основные понятия


Сначала определим, что такое контур объекта. Контур – это граница объекта, совокупность точек (пикселов), отделяющих объект от фона.



В системах компьютерного зрения используется несколько способов кодирования контура – наиболее известны код Фримена, двумерное кодирование, полигональное кодирование. Но все эти способы кодирования не используются в КА.



Вместо этого, в КА контур кодируется последовательностью, состоящей из комплексных чисел. На контуре фиксируется точка, которая называется начальной точкой. Затем, контур обходится (допустим – по часовой стрелке), и каждый вектор смещения записывается комплексным числом a+ib. Где a – смещение точки по оси X, а b – смещение по оси Y. Смещение берется относительно предыдущей точки.





В силу физической природы трехмерных объектов, их контуры всегда замкнуты и не могут иметь самопересечения. Это позволяет однозначно определить путь обхода контура (с точностью до направления – по или против часовой стрелки). Последний вектор контура всегда приводит к начальной точке.



Каждый вектор контура будем называть элементарным вектором (ЭВ). А саму последовательность комплекснозначных чисел – вектор-контуром (ВК).

Вектор-контуры будем обозначать большими греческими буквами, а их элементарные вектора – малыми греческими буквами.

Таким образом, вектор-контур Г длины k можно обозначить как:







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



В принципе, комплексное кодирование близко к двумерному кодированию, где контур определяется как совокупность ЭВ, представленных своими двумерными координатами. Но разница в том, что операция скалярного произведения для векторов и для комплексных чисел – различны. Именно это обстоятельство и дает преимущество методам КА.




Свойства контуров

1. Сумма ЭВ замкнутого контура равна нулю. Это тривиально – поскольку элементарные векторы приводят в начальную точку, значит их сумма равна нуль-вектору.
2. Контур-вектор не зависит от параллельного переноса исходного изображения. Поскольку контур кодируется относительно начальной точки, то этот способ кодирования инвариантен сдвигу исходного контура.
3. Поворот изображения на определенный угол равносилен повороту каждого ЭВ контура на тот же угол.
4. Изменение начальной точки ведет к циклическому сдвигу ВК. Поскольку ЭВ кодируются относительно предыдущей точки, то понятно, что при изменении начальной точки последовательность ЭВ будет та же самая, но первым ЭВ будет тот, который начинается в начальной точке.
5. Изменение масштаба исходного изображения можно рассматривать как умножение каждого ЭВ контура на масштабный коэффициент.

Скалярное произведение контуров


Скалярным произведением контуров Г и N называется такое комплексное число:







Где k – размерность ВК, Оі_n — n-й элементарный вектор контура Г, ОЅ_n — n-й ЭВ контура N. (Оі_n, ОЅ_n) — скалярное произведение комплексных чисел, вычисляемое как:







Обратим внимание на то, что в КА допускается скалярное произведение только ВК одинаковой размерности. То есть число элементарных векторов в контурах должно совпадать.



Скалярное произведение обычных векторов и скалярное произведение комплексных чисел – отличаются. Если бы мы перемножали ЭВ как простые вектора, то их скалярное произведение выглядело бы так:







Сравните эту формулу с формулой (2) и вы заметите, что:

• Результатом скалярного произведения векторов является действительное число. А результатом произведения комплексных чисел – комплексное число.
• Действительная часть скалярного произведения комплексных чисел совпадает со скалярным произведением соответствующих векторов. То есть комплексное произведение включает в себя векторное скалярное произведение.

А теперь давайте вспомним линейную алгебру. А точнее – физический смысл и свойства скалярного произведения. В линейной алгебре скалярное произведение равно произведению длин векторов на косинус угла между ними. Это значит, что два перпендикулярных вектора всегда будут иметь нулевое скалярное произведение, коллинеарные же вектора – напротив, будут давать максимальное значение скалярного произведения.



Эти свойства произведения позволяют использовать его как определенную меру близости векторов. Чем оно больше – тем меньше угол между векторами, тем «ближе» они друг к другу. Для перпендикулярных векторов – оно опускается до нуля, и далее становится отрицательным для векторов, направленных в разные стороны. Оказывается, скалярное произведение (1) также обладает похожими свойствами.



Введем еще одно понятие – нормированное скалярное произведение (НСП):







Где |Г| и |N| — нормы(длины) контуров, вычисляемые как:







НСП в пространстве комплексных чисел, также является комплексным числом.

При этом, единица – это максимально возможное значение модуля НСП (это следует из неравенства Коши-Буняковского: |ab|≤|a||b|), и она достигается только если







где Ој – произвольное комплексное число.



Что это значит на практике? Вспомним физический смысл умножения комплексных чисел. При умножении комплексных чисел, их модули(длины) перемножаются, а аргументы(углы) – складываются. Значит контур ОјN это тот же контур N, но повернутый и промасштабированный. Масштаб и поворот определяется комплексным числом Ој.



Итак, модуль НСП достигает максимального значение – единицы, только если контур Г является тем же контуром N, но повернутым на некоторый угол и промасштабированный на определенный коэффициент.



Для примера, рассмотрим скалярное умножение контура самого на себя, но повернутого на определенный угол.

Так, если посчитать НСП вектора самого на себя, то мы получим НСП=1, если повернуть контур на 90 градусов, мы получим НСП=0+i, поворот на 180 градусов даст НСП=-1. При этом, действительная часть НСП будет нам давать косинус угла между контурами, а модуль НСП всегда будет равна единице.







Аналогично, если мы умножим ВК на некоторый действительный коэффициент (промасштабируем), то мы также получим НСП=1 (это несложно увидеть из формулы (4)).



Итак, модуль нормированного скалярного произведения контуров даст единицу только в том случае, если эти два контура равны с точностью до поворота и масштаба. В противном случае, модуль НСП будет строго меньше единицы.



Это центральный вывод КА. Фактически, модуль НСП является инвариантом по переносу, вращению и масштабированию контуров. Если есть два одинаковых контура, то их НСП всегда даст единицу, не зависимо от того, где контуры находятся, каков их угол поворота и масштаб. Аналогично, если контуры различны, то их НСП будет строго меньше единицы, и также независимо от места, вращения и масштаба.



Модуль дает меру сходства контуров, а аргумент НСП (равный atan(b/a)) – дает нам угол поворота контуров относительно друг друга.




Корреляционные функции контуров


В предыдущей главе мы установили, что НСП является чрезвычайно полезной формулой для поиска похожих между собой контуров. К сожалению, есть одно обстоятельство не позволяющее использовать его напрямую. И это обстоятельство – выбор начальной точки.



Дело том, что равенство (6) достигается только если начальные точки контуров – совпадают. Если же контуры одинаковы, но отсчет ЭВ начинается с другой начальной точки, то модуль НСП таких контуров не будет равен единице.



Введем понятие взаимокорреляционной функции (ВКФ) двух контуров:







Где N^(m) — контур, полученный из N путем циклического сдвига его ЭВ на m элементов.

Для примера, если N=(n1, n2, n3, n4), то N⁽¹⁾=(n2, n3, n4, n1), N⁽²⁾=(n3, n4, n1, n2) и так далее.



Что показывает взаимокорреляционная функция? Значения этой функции показывают насколько похожи контуры Г и N, если сдвинуть начальную точку N на m позиций.



ВКФ определена на всем множестве целых чисел, но поскольку циклический сдвиг на k приводит нас к исходному контуру, то ВКФ является периодической, с периодом k. Поэтому нас будет интересовать значения этой функции только в пределах от 0 до k-1.



Найдем величину, имеющую максимальный модуль среди значений ВКФ:







Из определений НСП и ВКФ, понятно, что П„_max является мерой похожести двух контуров, инвариантной переносу, масштабированию, вращению и сдвигу начальной точки.



При этом, модуль |П„_max| показывает степень похожести контуров, и достигает единицы для одинаковых контуров, а аргумент arg(П„_max) дает угол поворота одного контура, относительно другого.



Введем еще одно понятие – автокорреляционной функции (АКФ). Автокорреляционная функция является ВКФ для которой N=Г. По сути – это скалярное произведение контура самого на себя при различных сдвигах начальной точки:







Рассмотрим некоторые свойства АКФ:

1. АКФ не зависит от выбора начальной точки контура. Действительно, посмотрим на определение скалярного произведения (1). Как видим, изменение начальной точки приведет просто к изменению порядка суммируемых элементов и не приведет изменению суммы. Этот вывод не столь очевиден, но если вдуматься в смысл АКФ, то он ясен.
2. Модуль АКФ симметричен относительно центрального отсчета k/2. Поскольку АКФ является суммой попарных произведений ЭВ контура, то каждая пара встретится два раза на интервале от 0 до k.
   
   Пусть, например, N=(n1, n2, n3, n4), распишем значения АКФ для разных m:
   
   
   
   АКФ(0)=(n1,n1)+(n2,n2)+(n3,n3)+(n4,n4)
   
   АКФ(1)=(n1,n2)+(n2,n3)+(n3,n4)+(n4,n1)
   
   АКФ(2)=(n1,n3)+(n2,n4)+(n3,n1)+(n4,n2)
   
   АКФ(3)=(n1,n4)+(n2,n1)+(n3,n2)+(n4,n3)
   
   АКФ(4)=(n1,n1)+(n2,n2)+(n3,n3)+(n4,n4)
   
   
   
   Заметим, что слагаемые в АКФ(1) те же самые, что и в АКФ(3), с точностью до перестановки множителей. А вспомнив, что для комплексных чисел (a, =(b, a)*, получаем что АКФ(1)=АКФ(3)*, где * — знак сопряженного комплексного числа.
   
   А поскольку |a*|=|a|, то получается что модули АКФ(1) и АКФ(3) – совпадают.
   
   Аналогично, совпадают модули АКФ(0) и АКФ(4).
   
   Далее мы везде будем под АКФ понимать только часть функции на интервале от 0 до k/2, поскольку остальная часть функции – симметрична первой части.
3. Если контур имеет какую-либо симметрию относительно поворота, то аналогичную симметрию имеет его АКФ. Для примера, приведем графики АКФ для некоторых контуров:
   
   
   
   
   
   На рисунках, модуль АКФ изображен синим цветом (АКФ изображена только для интервала от 0 до k/2).
   
   
   
   Как видим, все контуры, кроме последнего имеют симметрию к повороту, что приводит к симметрии АКФ. Последний же контур такой симметрии не имеет, и график его АКФ – не симметричен.
4. АКФ контура в определенном смысле можно считать характеристикой формы контура. Так, формы, близкие к кругу имеют равномерные значения модуля АКФ (см рисунок для круга). Сильно вытянутые в одном направлении формы – имеют провал в центральной части АКФ (см рисунок прямоугольника). Формы, переходящие в самих себя при повороте, имеют максимум АКФ в соответствующем месте (см. АКФ квадрата).
5. Нормированная АКФ не зависит от масштаба, положения, вращения и выбора начальной точки контура. Это следует из пункта 1-го и из свойств НСП.
   
   Ниже приведено видео, демонстрирующее этот факт:

На этом, мы заканчиваем теоретическую часть КА. В этой главе я привел только основные понятия и теоретические выкладки, которые я буду непосредственно применять при распознавании изображений во второй главе. При этом, я опустил целые разделы, касающиеся КА, например, преобразования Фурье. Если у вас есть желание более подробно разобраться в теории КА, читайте [1].




Практическое применение контурного анализа





Общий алгоритм распознавания


Итак, мы будем решать задачу распознавания образов на изображении.

Общая последовательность действия при распознавании выглядит так:

1. Предварительная обработка изображения — сглаживание, фильтрация помех, повышение контраста.
2. Бинаризация изображения и выделение контуров объектов.
3. Начальная фильтрация контуров по периметру, площади, коэффициенту формы, фрактальности и так далее.
4. Приведение контуров к единой длине, сглаживание.
5. Перебор всех найденных контуров, поиск шаблона, максимально похожего на данный контур.

Пункты 1 и 3 мы рассматривать не будем, они специфичны для прикладной области, и имеют малое отношение к КА.

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




Оценка производительности алгоритмов в КА


Сразу сделаем оценку быстродействия алгоритмов, основанных на КА.

Пусть изображение уже бинаризировано и на нем выделены контуры.

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

Для этого, возьмем изображение размером n*n пикселов. Затем покроем его равномерной сеткой с шагом s. Суммарная длина всех линий сетки составит







Получается, что переход от плоского двумерного изображения к контурам не уменьшает размерность задачи. Мы по-прежнему работаем в сложности О(n²).



Однако здесь можно сделать несколько замечаний:

1. Приведенная оценка является экстремальной. В реальном изображении далеко не все контуры имеют минимальный размер, и они не покрывают всю площадь изображения. Следовательно, число контуров и их суммарный периметр может быть значительно меньше 2n²/s. В идеальном случае – если изображение содержит один объект, без помех, то КА будет работать только с одним контуром, и число его пикселов составит уже не квадратичную, а линейную зависимость от n. В случае же работы с изображением, как с двумерным массивом пикселов (например, применяя каскадные фильтры Хаара) — мы всегда работаем со всеми пикселами изображения, независимо от того, сколько объектов на нем изображено.
2. Поскольку изображение в виде контуров уже имеет естественную сегментацию — разбито на контуры, то можно осуществлять фильтрацию частей изображения по простым признакам. Среди них – площадь контура, периметр, отношение квадрата периметра к площади (коэффициент формы). Таким образом, есть достаточно простой и эффективный механизм предварительной фильтрации частей изображения.
3. Базовые алгоритмы двумерных методов, как правило, не инвариантны к масштабу(SURF, SIFT) или вращению(Хаар). Поэтому, фактически, они работают в трехмерном пространстве, где еще одно измерение появляется из-за необходимости перебирать масштабы или углы поворота. Поскольку методы КА инвариантны к масштабу и вращению, то здесь такой проблемы не существует (исключение – неинвариантность к начальной точке, но ниже мы рассмотрим эффективные методы борьбы с этой сложностью).
4. КА позволяет обрабатывать изображение в прогрессивном режиме. Это значит, что мы можем отсортировать контуры по каком-либо признаку (например, по площади или по градиенту границ, или по яркости и т.п.). А затем обработать первый контур, и выдать результат. Остальные же контуры обрабатывать в фоновом режиме. Это значит что первый результат (а во многих прикладных задачах именно он и нужен) может быть получен за O(n), что является отличной оценкой для алгоритмов распознавания изображений.
5. Поскольку контуры независимы друг от друга, то алгоритмы распознавания легко распараллеливаются. Кроме того, алгоритмы очень просты и могут выполняться на графических процессорах.
6. Все вышеприведенные размышления касаются только обработки контуров. Разумеется, этап получения самих контуров никуда не исчезает, и он требует как минимум O(n²). Однако, на практике, этот этап занимает не более 10-20% от общего времени обработки.

Совокупность этих факторов существенно снижает константу вычислительной сложности, и при современном развитии компьютерной техники, КА вполне может использоваться как алгоритм реального времени.



Разберемся в причинах сложности О(n²). Сам контур, по сути, является одномерным объектом. Это вектор комплекснозначных чисел. Однако число контуров растет пропорционально квадрату размера изображения. Отсюда и возникает сложность O(n²). Из этого можно сделать вывод о том, что самым эффективным способом увеличения производительности является уменьшение числа контуров предварительной фильтрацией.



Теперь оценим сложность обработки отдельно взятого контура.

В предыдущей главе мы выяснили, что для сравнения контуров нужно найти максимум ВКФ (формулы 7, 8). Оценим сложность вычисления. Скалярное произведение требует O(k) операций, где k – длина контура. А для вычисления ВКФ нужно произвести k вычислений скалярных произведений. Значит, ВКФ требует вычислений порядка O(k²). Кроме того, учитывая, что сравнение идет не с одним шаблоном, а с множеством шаблонов, то полное время поиска шаблона для контура можно оценить как







Где k – длина контура, а t – число шаблонных контуров.

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

Итого, сложность идентификации всех контуров изображения составляет







Где – n – линейный размер изображения, k – длина контура, t – число шаблонов

Сложность идентификации первого контура (в прогрессивном режиме):








Дескриптор контура


Как было показано в предыдущей главе, сложность вычисления ВКФ составляет O(k²). Не смотря на то, что k – константа (процесс приведения контуров к единой длине мы рассмотрим далее), все равно, вычисление ВКФ — трудоемкий процесс. При k=30 на вычисление ВКФ требуется 900 операций умножения комплексных чисел. А при наличии t=1000 шаблонов, поиск шаблона для контура требует около миллиона умножений комплексных чисел.

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

Поэтому мы введем более эффективный способ поиска и сравнения шаблонов.



Для быстрого поиска шаблонов необходимо ввести некий дескриптор, характеризующий форму контура. При этом, близкие между собой контуры должны иметь близкие дескрипторы. Это избавило бы нас от процедуры вычисления ВКФ контура с каждым шаблоном. Достаточно было бы сравнить только дескрипторы, и если они будут близки – только в таком случае – вычислять ВКФ. Само же сравнение дескрипторов должно быть быстрым. В идеале — дескриптором должно быть одно число.



К сожалению, в литературе, я не нашел явного описания подходящих дескрипторов, описывающих форму контура. Тем не менее, такой дескриптор существует.



А первой главе мы подробно рассматривали свойства автокорреляционной функции. Там же мы отмечали, что АКФ инвариантно к переносу, вращению, масштабированию и выбору начальной точки. И кроме того, АКФ является функцией одного контура, а не двух, как ВКФ.



Исходя из этого, АКФ можно выбрать в качестве дескриптора, описывающего форму контура. Близкие контуры всегда будут иметь близкие значения АКФ.



Сравнение двух АКФ имеет сложность O(k), что уже значительно лучше чем O(k²) для ВКФ. Кроме того, как мы помним, АКФ из-за симметрии, определено только на интервале от 0 до k/2, что еще в два раза уменьшает время вычислений.



Если база шаблонов хранит их АКФ, то поиск шаблона для контура, путем сравнения АКФ, составит O(kt). Это уже хорошая оценка. Но и ее нам бы хотелось улучшить.




Свертка АКФ


АКФ представляет собой вектор с k/2 значениями. Если мы вычисляем некую меру различий двух АКФ, нам нужно перебрать все k/2 значений. В принципе, если порог различий фиксирован, то мы можем на каждом шагу вычислять текущую меру различий, и как только она превысит порог – прерывать сравнение АКФ. Таким образом мы ускорим сравнение АКФ.



Однако тут есть две сложности – во-первых, вычисление меры на каждом шагу затратно по времени, во-вторых, если различие происходит в середине, или только в последних компонентах значении АКФ, то эффективность данного алгоритма падает, и он вырождается в полное сравнение.



Для более эффективного решения проблемы сравнения АКФ, изменим способ представления АКФ. Вместо хранения самой АКФ, будем хранить вейвлетную свертку модулей значений АКФ. При этом первый компонент свертки будет соответствовать наиболее крупномасштабному вейвлету, а последующие компоненты – будут уточнять значения функции во все более мелких масштабах.



Вейвлетная свертка позволит нам упорядочить значения АКФ в масштабном порядке. Первым будет идти компонент, отвечающий наиболее крупномасштабным особенностям АКФ, а дальнейшие компоненты будут уточнять все более мелкие особенности АКФ.



Вейвлетная свертка нам дает преимущества при сравнении АКФ. Сравнивая первые компоненты свертки мы получаем сравнение АКФ в наиболее грубом приближении. Если эти компоненты существенно отличаются, дальнейшие сравнения можно не делать, потому что АКФ гарантированно отличаются. Далее, мы сравниваем вторые компоненты свертки, если они существенно отличаются – также прерываем сравнение и так далее.



Кроме того, мы можем не сравнивать все k/2 компонент свертки. Поскольку сравнение носит оценочный, приближенный характер, нам достаточно сравнить первые 4-5 значений свертки АКФ. А затем, при их близости, сразу переходить к вычислению ВКФ.



Отметим следующее:

1. Сравнение АКФ, в общем случае, не избавляет нас от необходимости вычисления ВКФ. Только ВКФ дает точную оценку близости контуров. АКФ же, в общем случае, может совпадать для различных контуров. Но, при этом, предварительный отбор шаблонов по АКФ существенно сужает число кандидатов на сравнение по ВКФ.
2. В ряде случаев, сравнения АКФ может быть достаточно для идентификации контуров. Если на изображении ищутся маркеры с простой геометрической формой, и вероятность ошибочных распознаваний не существенна, то можно опустить процесс сравнения ВКФ, ограничившись только сравнением сверток АКФ. Такой алгоритм дает наибольшую производительность системы.
3. Первый компонент свертки АКФ дает нам хороший дескриптор для упорядочивания базы шаблонов. Действительно, если для данного контура подходят только шаблоны, у которых первый компонент свертки приблизительно равен первому компоненту свертки контура, то имеет смысл упорядочить шаблоны в базе по первому компоненту свертки. Это сразу на порядок уменьшает число шаблонов-кандидатов на сравнение. Для больших баз шаблонов это может дать хороший прирост производительности.

Теперь остановимся на выборе конкретных вейвлетов для свертки.

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



Однако, учитывая то, что свертка нам нужна для сравнения, и то, что АКФ часто является симметричной функцией (см рисунки в первой главе), то не все вейвлеты одинаково хорошо подходят для наших целей.



Основным критерием к выбору вейвлета является его дискриминирующие свойства.

Для примера, рассмотрим широко распространенные вейвлеты Хаара и Уолша:





Также, посмотрим на АКФ контура квадрата:







Обратим внимание, что из-за симметричности АКФ относительно центральной линии, первый компонент вейвлета Хаара даст нулевое значение.

Второй компонент вейвлета Хаара, также даст нулевое значение, из-за симметричности половинок АКФ относительно своих середин.

Кроме того, если мы посмотрим на примеры АКФ, приведенные в первой главе, окажется что первый компонент вейвлета Хаара дает нуль для всех АКФ, кроме последней (контур буквы А). Второй компонент Хаара также даст нуль для контуров круга и квадрата.

Одинаковые значения первых компонент говорит о плохих дискриминирующих свойствах вейвлетов Хаара для свертки АКФ.



Теперь рассмотрим вейвлеты Уолша. Первый компонент свертки, по сути, является суммой всех компонент АКФ. Обратим внимание на то, что эта сумма различна для всех примеров АКФ, приведенных в первой главе. Это значит, что дискриминирующие свойства вейвлета Уолша для симметричных АКФ лучше, чем вейвлета Хаара.



Первые четыре компонента свертки Уолша обозначены красными столбцами на рисунках АКФ в первой главе.



Ниже приведена гистограмма частоты встречаемости первого компонента свертки Уолша для базы шаблонов контуров латинских букв (всего в базе 3463 шаблона).







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



Пусть, для примера, первый компонент контура изображения равен 25 (одно из наиболее часто встречаемых значений в базе шаблонов). Если мы примем пороговую разность сверток Lmax=4, значит, нам подойдут шаблоны в интервале от 21 до 29. Из графика видно, что в этом интервале находится около 1000 шаблонов. Это составляет 1000/3463=29% от всех шаблонов. Значит, в наихудшем случае, сравнение по первому компоненту свертки отфильтрует более 70% неподходящих шаблонов.



В целом, оптимальный выбор вейвлетов определяется характерными формами распознаваемых объектов. Например, если объекты симметричны, лучше выбирать несимметричные базовые функции вейвлетов.




Эквализация контуров


Как уже было отмечено в первой главе, методы КА подразумевают одинаковую длину контуров. В реальном же изображении контуры имеют произвольную длину.



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



В книге [1] описан способ эквализации, дающий на выходе контур, состоящий из заданного числа одинаковых по длине отрезков. Однако этот метод довольно сложен (не будем забывать, что нам нужно будет проводить эквализацию всех контуров изображения, которых в общем случае О(n²)).



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



Итак, сначала мы фиксируем длину ВК, которую мы будем использовать в нашей системе распознавания. Обозначим ее k.



Затем, для каждого исходного контура Г создаем вектор-контур N длиной k. Далее возможно два варианта – либо исходный контур имеет большее число ЭВ чем k, либо меньшее число чем k.



Если исходный контур больше необходимого, то перебираем все его ЭВ, и считаем элементы N как сумму всех ЭВ, следующим образом (C#):



Complex[] newPoint = new Complex[newCount];

for (int i = 0; i < Count; i++)
newPoint[i * newCount / Count] += this[i];



Этот алгоритм достаточно грубый, особенно для длин немногим больших k, однако он вполне применим на практике.



Если же исходный контур меньше k, то производим интерполяцию, и считаем примерно так:



Complex[] newPoint = new Complex[newCount];

for (int i = 0; i < newCount; i++)
{
double index = 1d * i * Count / newCount;
int j = (int)index;
double k = index - j;
newPoint[i] = this[j] * (1 - k) + this[j + 1] * k;
}



Возникает вопрос, каким именно нужно выбрать значение k, какое значение оптимально? Ответ на этот вопрос полностью определяется спецификой прикладной области. С одной стороны, большая длина k означает большие затраты на вычисления. С другой стороны – малые значения k несут меньше информации, и точность распознавания снижается, а распознавание шума – увеличивается.



Ниже приведен график основных показателей системы распознавания, в зависимости от выбранной длины ВК:







Этот график строился для системы распознавания латинских букв, на основании тестов ICDAR.



Как видим, при больших значениях (от 80 и выше) длины контура, параметры системы стабилизируются и мало меняются (кроме времени обработки, которое, естественно, увеличивается).



При малых значениях k (менее 30) — резко повышается число шумовых распознаваний (распознавание как символов шума или других несимвольных элементов изображения, noise recognition), снижается число верных распознаваний (successful recognized), и увеличивается число ложных распознаваний (fail recognitions).



Таким образом, значение k=30 является оптимальным для данной системы распознаваний.



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




Недостатки КА


КА имеет две группы факторов отрицательно влияющих на результаты распознавания.



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



На рисунке справа показано бинаризированное изображение. Небольшие «мостики» между изображением цифры и окружающим фоном делают контур цифры нераспознаваемым методами КА.







Такие случаи очень тяжелы для КА. Ведь КА имеет смысл, только в том случае, когда контур объекта определен однозначно правильно во всех своих точках.



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



На картинке справа – бинаризированное изображение. Видно, что блик фотографии, идущий горизонтальной чертой, делает буквы неразличимыми для КА.







Таким образом, КА имеет слабую устойчивость к помехам, не допускает пересечения или частичной видимости объекта.




Результаты тестирования метода


Несмотря на недостатки, методы КА привлекательны своей простотой и быстродействием. При наличии четко выраженного объекта на контрастном фоне и отсутствии помех КА хорошо справляется с распознаванием.



Тестирование методов КА на тестах ICDAR дает результат 48% распознанных символов. Это неплохой результат, учитывая, что этот тест очень непрост, и содержит большое число плохочитаемых изображений букв. При этом, КА обработал 249 изображений различного размера (от 400x400 до 1280x960) за 30 секунд.



Помимо распознавания статических изображений, быстродействие КА позволяет обрабатывать видео в режиме реального времени. Ниже приведен ролик, демонстрирующий возможности КА








Литература


[<a name="b1">1] Введение в контурный анализ. Под ред. Я.А. Фурмана, 2003.

[2] Learning OpenCV. Gary Bradski, Adrian Kaehle, 2008.
Original source: habrahabr.ru (comments).

Читать дальше