SYMMETRY RECOGNITION IN GRAY-LEVEL IMAGES BASED ON AN INTEGRAL TRANSFORM

Abstract

A method for symmetry recognition in 2D gray-level images based on a special integral transform is considered.

Full Text

Введение Изучение симметрии изображений является в настоящее время одним из активно развиваемых направлений теоретической информатики. Работы в этой области активно стимулируются, в частности, тем, что группы симметрий изображений не зависят от их размеров, поворотов, яркости, плотности и центрирования, являясь тем самым сильными дескрипторами изображенных объектов [1-3]. В настоящей работе рассматривается задача распознавания группы симметрий изображения с точностью до изоморфизма. Для ее решения предлагается новое двумерное интегральное преобразование, являющееся непрерывным по первой переменной и дискретным по второй. Идея его построения основана [3] на рассмотрении Фурье-образа изображения в полярной системе координат, что позволяет трансформировать вращения в сдвиги и находить инварианты изображения относительно преобразований симметрии. Отметим, что вводимое преобразование до некоторой степени аналогично так называемому преобразованию Фурье-Меллина [4], инвариантному относительно как сдвигов и вращений, так и масштабирования. Заметим, что последнее важно для эффективного решения задач совмещения изображений [5], однако избыточно при распознавании симметрии, а использование преобразованием Фурье-Меллина полярнологарифмической системы координат приводит к значительным вычислительным сложностям. В частности, основанный на нем метод [6] распоз навания симметрии требует априорного знания координат центра симметрии. Предлагаемый в работе подход свободен от указанных недостатков. Простота аналитического выражения рассматриваемого преобразования позволяет в непрерывном случае сформулировать его свойства в окончательной форме. На их основе устанавливается ряд следствий, позволяющих эффективно распознавать группу симметрий. Работа выполнена при поддержке РФФИ, проекты № 11-07-00591 и №13-07-00327. Группа симметрий изображения Будем считать, что на действительной плоскости М2 введена декартова система координат хОу. Под изображением (точнее, под плоским непрерывным полутоновым финитным изображением) будем понимать неотрицательную действительную ограниченную функцию определенную всюду на R2, но отличную от нуля только внутри некоторой области / с!2 конечного диаметра. Чтобы ввести понятие группы симметрий, рассмотрим следующие элементарные преобразования изображений: 1) сдвиг Та на вектор а = (х0,у0): та\Л = f(x-x0,y-y0)’ 2) вращение Ra на угол а вокруг начала координат O: Ra[f] = f(x cos а — у sin et, х sin а + у cos а) ; 3) отражение M относительно оси Ох: Mif] = f(?,-v)· Рассматривая их композиции, получаем более сложные преобразования. В частности, нам понадобится преобразование ML отражения относительно прямой L, проходящей через точку а = (ж0,у0) и наклоненной к оси Ох на угол а. Как нетрудно показать, Мт = ТК МТ . L а ία —а «Инфокоммуникационные технологии» Том 11, № 2, 2013 Мнухин В.Б. 5 Определение 1. Будем говорить, что изображение / обладает отражательной симметрией относительно прямой L (или симметрично относительно L), если ML[f(x,y)\ = f(x,y) для всех (х, у) Є К2. При этом L называется осью симметрии. Чтобы ввести понятие вращательной симметрии, рассмотрим преобразование R вращения на угол а. вокруг точки а : Д. TRT . а а —а Определение 2. Будем говорить, что изображение / обладает вращательной симметрией бесконечного порядка в точке й, если R [f] = f для всех а. Если же найдется угол ß, (0 < ß < 2π), такой, что RßJf\ = f, но RJf] * f для всех меньших углов а, О < а < ß, то в точке а изображение имеет вращательную симметрию порядка к = 2тт / β, где, как нетрудно заметить, число к > 1 является целым. Точка а называется центром вращательной симметрии. Всевозможные композиции элементарных преобразований сдвигов Т , вращений Ra и отражения M образуют бесконечную группу перемещений Г, являющуюся подгруппой группы всех аффинных преобразований плоскости [7]. Таким образом, Г естественно действует на множестве изображений. Определение 3. Группой симметрий изображения / называется его стабилизатор т в группе перемещений. Другими словами, это множество всех тех перемещений плоскости, которые не изменяют данное изображение. Рис. 1. Примеры изображений с небольшими группами симметрий Классы изоморфизма групп симметрий финитных изображений хорошо известны [7]. Это либо а) конечные циклические группы Zk порядка к >1, порождаемые вращением вокруг точки a на угол 2π / к, (случай к = 1 соответствует отсутствию нетривиальных симметрий), либо б) конечные диэдральные группы Dk порядка 2к >2, порождаемые отражением относительно некоторой прямой и вращением порядка к с центром на даннной прямой, либо в) бесконечная ортогональная группа 0(2), являющейся группой симметрий окружности. Заметим, что обычно считается, что диэдраль-ная группа Dk имеет порядок 2к > 4. Нам будет удобно рассматривать также группу D1 порядка 2, порождаемую единственным отражением, отличая ее от группы Z , порождаемой вращением на 180°. Несмотря на изоморфизм — Z2, соответствующие этим группам симметрии различны (см. рис. 1). В данной работе рассматривается проблема распознавания симметрии плоского финитного изображения, заключающаяся в нахождении его группы симметрий с точностью до изоморфизма. Распознавание симметрии непрерывных изображений Введем интегральное преобразование, играющее ключевую роль в нашем подходе к проблеме распознавания симметрии. Оно основано на двумерном преобразовании Фурье, определяемом [8] следующим образом: il/] = F(u,v) = 00 00 = J* J* І(хіУ)ехР{~ 27гг(а;и + yv)}dxdy, —00 —оо где сходимость немедленно вытекает из наложенных на функцию f{x,y) ограничений. Фу-рье-образ F(u,v) определен на плоскости uOv, называемой частотной областью. Введем в ней полярную систему координат τΟφ с тем же самым началом O и с полярной осью φ = 0 , совпадающей с положительной полуосью Ох. Рассмотрим Фурье-образ F(u,v) в этой системе, полагая Ф(г,<^) = F(r cos φ, г sin φ). Наложим на функцию / еще одно ограничение. Поскольку реальные изображения являются гладкими, условимся считать f(x,y) бесконечно дифференцируемой в каждой точке по любому направлению. Тогда для всякого фиксированного полярного угла φ0 Є [0,7Г] модуль функции «Инфокоммуникационные технологии» Том 11, № 2, 2013 6 Мнухин В.Б. ф(г,φϋ) быстро убывает с ростом радиуса г, что гарантирует корректность определения следующего преобразования: н\{\ = Щщп) = Ф(г, ψ)\ ехр{—i(wr + 2 ηφ)}άτάφ, +00 If о о где непрерывная переменная w принимает всевозможные действительные значения, а дискретная переменная п пробегает множество всех целых чисел Z. Таким образом, H(w,n) можно считать комбинацией некоторого одномерного преобразования Фурье (по переменной w) и коэффициентов ряда Фурье (по переменной п ). Функцию H(w,n) условимся называть ^-образом изображения f при его ^-преобразовании т . Ее можно рассматривать как бесконечную (в обе стороны) последовательность функций Я[/] : ...,Я(®,-1),Я(ш,0),Я(ш,1),... Рассмотрим свойства преобразования H[f ]. Прежде всего отметим, что поскольку оно зависит только от энергетического спектра изображения, ^-преобразование не является ни обратимым, ни линейным. Покажем, как меняется H-образ изображения при его сдвигах и вращениях. Утверждение 1. Преобразование H[f\ инвариантно относительно сдвигов. При вращении изображения / на угол а вокруг произвольной точки его H-образ умножается на фазовый мно- 2 та житель е : Тем самым модуль H-образа изображения инвариантен как относительно сдвигов, так и относительно вращений. Рассмотрим отражения ML изображения относительно некоторой прямой L. Утверждение 2. Если прямая L образует с осью Ох угол а, а H-образ исходного изображения / равен , то H[MJ] = e4inaH(w-n). Таким образом, получаем следующий тест на отражательную симметрию изображения. Следствие 1. Если изображение f симметрично относительно некоторой прямой, образующей с осью Ox угол а, то для H-образа этого изображения выполняется тождество H(w,n) = е H (w,—п). В частности, если для некоторых значений переменных wan справедливо неравенство H(w,n) ^ H(w,—n) то изображение не обладает отражательной симметрией. Аналогичный результат о вращательной симметрии изображения имеет следующий вид. Утверждение 3. Если изображение / имеет бесконечную группу симметрий 0(2) , то H(w,ń) = 0 для всех 0. Если же группа симметрий Г(/) конечна и содержит вращение порядка к, то H(w, п) = 0 для всех п ^ 0 mod h(k), к, если к нечетно, к / 2, если к четно. где h(k) Другими словами, периодическое появление в последовательности т нулевых функций указывает на вращательную симметрию изображения, причем «ширина нулевого интервала» связана с порядком симметрии. Рис. 2. Вид H-преобразования изображения с вращательной симметрией Из предыдущих результатов вытекает тест на диэдральность группы симметрий изображения. Следствие 2. Если изображение / имеет диэд-ральную группу симметрий порядка 2к, то H(w, п) = е maH(w, —та), та ξ 0 mod h(k), О, иначе где а является углом наклона произвольной оси отражения данного изображения к Ох. Корректность данного утверждения следует из того, что разность углов наклона двух различных осей отражения всегда кратна π / к.) «Инфокоммуникационные технологии» Том 11, № 2, 2013 Мнухин В.Б. 7 Распознавание симметрии цифровых изображений Реализация предложенного метода распознавания симметрии для практически значимого случая цифровых изображений имеет ряд особенностей. Обсудим их подробнее, предполагая для простоты изложения, что размер изображения нечетен. Для фиксированного положительного нечетного целого N = 2М + 1 > 3 рассмотрим в дискретной плоскости Z2 квадрат S = [—Μ,Μ] X [—М,М] С Z2. Произвольную неотрицательную ограниченную функцию /(ж, у) : 5 —» К. дискретных аргументов X и у назовем цифровым изображением размера N X N. Под его диаметром будем понимать наименьшее целое d = 2δ + 1 > 0 такое, что f(x,y) ЕЕ О всюду вне некоторого квадрата )[л| N—HX) + 0, что позволяет использовать результаты предыдущего раздела в дискретном случае при выполнении условий N ^ 0 и d <С N. Кроме того, в то время как в непрерывном случае началом полярной системы координат в частотной области может быть только (0, 0), в дискретном случае в этом качестве можно использовать также точку, «диаметрально противоположную» (0, 0) на торе T. Соответственно возникают два варианта дискретного H-преобразования, которые естественно назвать низкочастотным H_[f] и высокочастотным W- Свойства этих преобразований дополняют друг друга, и их можно использовать для распознавания симметрии совместно. Для построения H[f] рассмотрим в частотной области T «полукруг» max{| і - *Д| у - у„|} < δ, (зд) є S. c = e г : + „* < Μ2,« > о} Рассмотрим в облкти 5 двумерное даскрет- и определИМ отображение РТ^С как ное прео6разование Фурье (ДПФ): ρ^φ) = ^ Где ^ g Я“.«) = 'У '/(а,у)ехр (x,y)eS Его частотная область uOv представляет собой дискретный тор T, получающийся из квадрата S отождествлением противолежащих сторон. Заметим, что частотную область непрерывного преобразования Фурье можно считать сферой (после добавления бесконечно удаленной точки). Различная топология этих областей приводит к отличиям в свойствах непрерывного и дискретного преобразований Фурье. В частности, доказательства утверждений предыдущего раздела существенно опираются на то, что непрерывное преобразование Фурье коммутирует с вращениями, FR = RaF. Для цифровых изображений даже корректное определение вращения явлется нетривиальной задачей, допускающей различные решения. Обычно вращение вводится как ^J/] = /([X]modiV,[y]modJV) > где X = х cos а —у sin a, Y = х sin а + у cos а, а [X] и [У] означают ближайшие целые к X и Y соответственно. Условимся называть диска ретным вращением. Как нетрудно заметить, ДПФ уже не коммутирует с 5ft . Вместе с тем можно показать, что для цифровых изображений фиксированного диаметра d < оо имеет место сходимость 2т. Л —— (ux + vy) • u = г + Μ -cos / ' πφ » V г ■ Μ . -sin r γ πφ N 2 я \ / 2 [N Для ДПФ F[f] = F{u,v) построим Ф(г, φ) = F (P(r, 9?)), где (г, φ) Є T, и определим низкочастотное H-преобразование следующим образом: H[f] = H{w,n) = 1 N2 Σ |ф(г’^) (r,tp)eT exp 2πϊ N (rw + φη) Смещая начало координат, аналогично можем определить m . На рис. 3 показана визуализация модулей H-преобразований последнего из изображений рис. 1. Их характерная симметричность указывает на отражательную симметрию исходного изображения. Рис. 3. Модули H-преобразований изображения с группой симметрий D2 «Инфокоммуникационные технологии» Том 11, № 2, 2013 8 Мнухин В.Б. Заметим, что наиболее естественное определение функции Ф с помощью отображения P не свободно от недостатков. Действительно, P не является, вообще говоря, ни инъективным, ни сюръективным, что связано с принципиальной невозможностью вполне адекватного определения полярной системы координат на дискретной плоскости [9]. На практике лучшие результаты дает использование функции Φ'(τ,φ) = аФ(г, φ) + (1 - а)Ф(г,<^), где 0 < а < 1, а Ф определяется следующим образом: рассмотрим отображение Q-.C^T такое, что Q(u, V) = (г, φ), где φ = N arg(,z) / π г 2 I z , z = u + iv, (В некотором причем arg (2) Є —π / 2,π / 2 смысле Q подобно обратному к Р.) Теперь если (г, φ) = Q(u, υ) для (и, ν) Є С , то положим ф(г,<£>) = F{u,v)\ в противном случае Ф (г,<р) = 0. Выбор значения коэффициента а зависит от специфики решаемой задачи; в данной работе полагалось а = 0,5. Рассматривая применимость результатов предыдущего раздела к цифровым изображениям, следует учитывать, что даже абсолютно симметричный относительно некоторой оси отражательной симметрии объект может потерять эту симметричность при поворотах изображения. Поэтому анализ ^-преобразований, превращающихся для цифровых изображений в (N X N) -матрицы, следует проводить статистическими методами. Несмотря на то что приведенные выше результаты дают только необходимые условия наличия симметрий изображений, они позволили корректно распознать группы симметрий в сделанных тестовых примерах. Выводы Предложен метод распознавания групп симметрии плоских финитных изображений, основанный на рассмотрении симметрий в частотной области. Вводится интегральное преобразование, позволяющее получить эффективно вычислимые инварианты изображений.