Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v3(3-4)/kozlov-95-118.pdf Дата изменения: Fri May 8 19:11:56 2009 Дата индексирования: Mon Oct 1 23:35:37 2012 Кодировка: Windows-1251

О распознавании аффинно разных дискретных изображений
В.Н. Козлов

Введение
Под изображением в этой работе понимается конечное множество точек на плоскости. Такое представление может показаться достаточно абстрактным, отвлеченным от того, что на практике понимается под изображением. К нему, однако, приводит рассмотрение широкого класса реальных изображений: газетных фотографий, картинок на экране телевизора и т.п. - все это изображения, составленные из точек, то есть представляющие собой совокупности точек на плоскости. Проецируемое на сетчатку глаза изображение порождает конфигурацию рецепторов, находящихся в возбужденном состоянии, то есть, в конечном счете, тоже точечное изображение. Применительно к изображениям говорят о зрительных образах. Определения образа нет, и конкретный образ задается, как правило, перечислением примеров изображений, в него входящих. Если исходить из этого, то образ - это совокупность изображений, объединяемых в одну группу, причем по трудноформализуемым критериям. В словесном выражении эти критерии чаще всего звучат так: изображения группы "похожи они "одной формы "одного типа "одинаково устроены"и т.п. Наиболее наглядный и вследствие этого часто рассматриваемый случай - образы букв и цифр, поэтому будем вести рассуждения на их примере. Возьмем, для конкретности, образ цифры два. Во множество изображений, объединяемых под общим названием "двойка входят очень разные изображения. Это может быть и кривая линия на листе бумаги, и гигантская фигура на рекламном щите, и значок из стандартного шрифта на экране компьютера, и пр. Вопрос в том, как конкретизировать, на чем основывается интуитивно очевидное сходство в форме этих изображений? Можно положить, в качестве первого шага, что нагляднее и очевиднее всего "одинаковость формы"для двух изображений имеет место, если их можно просто наложить друг на друга, и они при этом в точности совпадут. Наложить, очевидно, движениями, то есть, в этом случае, параллельными переносами, поворотами

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

Рис. 1-4. Конечно, такое определение будет недостаточным хотя бы потому, что в эту группу не попадут изображения, отличающиеся от двойки на рис. 1 размерами. Поэтому на следующем шаге добавим изменение масштаба, и, тем самым, будем рассматривать преобразования подобия (рис. 2). Наконец, добавление возможности растягивать и сжимать изображение (рисунки 3 и 4) по любому направлению приводит к аффинным преобразованиям в целом. Этими преобразованиями из рисунка 1 порождается уже довольно широкий класс изображений, они, очевидно, отличаются друг от друга довольно значительно. Ранее [1, 2, 3] для описания класса изображений, переводимых друг в друга в точности аффинными преобразованиями, был предложен код и описаны некоторые его свойства. Разумеется, класс изображений, отличающихся друг от друга произвольными аффинными преобразованиями - еще далеко не то, что содержательно понимается под образом. Достаточно обратить внимание на то, что если на рис. 1 какую-либо из точек несколько сдвинуть, оставляя остальные 96


точки неподвижными, то такую фигуру уже никакими аффинными преобразованиями не сделать совпадающей с исходной. А ведь именно своеобразная "инвариантность"по отношению к локальным изменениям формы должна иметь место, если ориентироваться на интуитивные, содержательные представления о том, что есть образ. В этой работе делается попытка сделать очередной шаг в приближении к понятию зрительного образа на основе следующих соображений. Пусть дaно изображение цифры два. Обозначим его через A. Положим, что каждая из точек изображения A - центр круга радиуса r (рис. 5). Отметим в каждом круге по точке (кружочки на рис. 5). В совокупности они тоже составляют точечное изображение (центр кружочка - точка), обозначим его через B . Изображение B смещениями и поворотами можно вынести за пределы изображения A и рассматривать отдельно (рис. 6). Ясно, что в общем случае оно отлично от изображения A в том смысле, что никакими переносами и поворотами нельзя совместить все точки рисунка 6 с точками рисунка 5. Вместе с тем из "происхождения"рисунка 6 следует, что параллельными переносами и поворотами можно его так расположить на рисунке 5, что каждая точка изображения B будет отстоять от соответствующей точки изображения A на расстояние, не большее r. Назовем такое взаиморасположение для A и B искомым. Тогда именно это обстоятельство - возможность искомым образом расположить изображения A и B - и может служить проявлением критерия "одинаковости формы который мы здесь и рассматриваем.

Рис. 5-6. 97


Если рисунок 6 дан "сам по себе без указания на его "происхождение то априори неизвестно, можно ли A и B расположить искомым образом. Поскольку множество возможных взаиморасположений рисунков 5 и 6, очевидно, континуально по мощности, то эту задачу нельзя решить перебором. Поэтому в первую очередь нужно ответить на вопрос о том, можно ли и как решить эту задачу конечными средствами, то есть использованием некоторой конечной процедуры. Под конечной процедурой понимается здесь решение задачи геометрическим построением или сведением к решению некоторой системы уравнений. Вопрос, связанный с определением искомого положения, можно усилить: каков минимальный возможный радиус r, при котором еще можно так расположить изображения A и B , что их соответствующие точки взаимоудалены на расстояние, не большее r, и какими средствами (конечными) осуществить такое их расположение? Именно этот вопрос и то, что с ним связано, рассматриваются в этой работе. Ясно, что решение этой задачи может быть положено в основу процедур распознавания изображений. Двойку на рис. 6 расположить на изображении другой цифры так, чтобы соответствующие точки находились на расстоянии, не большем того же r, очевидно, уже не удастся, и на этом можно основывать их различение.

Рис. 7-8. Везде выше соответствие между точками изображений A и B предполагалось взаимнооднозначным, то есть изображения A и B предполагались состоящими 98


из одинакового числа точек. Это действительно основной, базовый случай, и именно он рассматривается далее. Однако, нетрудно видеть, что решение для этого случая позволит сделать потом естественные его расширения: когда группа точек изображения B сопоставляется одной точке изображения A (рис. 7), и когда сопоставляются друг другу группы точек изображений A и B (рис. 8). Выше в качестве основного иллюстрирующего примера были выбраны изображения цифр. Однако возможности расширения, представленные рисунками 7 и 8, видны на них недостаточно отчетливо. Суть в том, что количество точек в кругах (оно может быть разным и для изображения A, и для изображения B ) есть как бы плотность "краски плотность изображения в этом месте. Это открывает дорогу к рассмотрению полутоновых изображений, а это, в свою очередь, важно при распознавании, например, фотографий. Наконец, рассмотрение трех полутоновых монохроматических (в основных цветах) изображений эквивалентно рассмотрению цветного изображения. Это, в перспективе, дает возможность выхода в рамках такого подхода и на распознавание цветных изображений.

1 Преобразования параллельного переноса и симметрии изображений
Содержательно задачу этого параграфа можно описать следующим образом. Пусть даны два изображения A и B , и каким-либо образом точки из A и B взаимнооднозначно сопоставлены друг другу. Этим определена взаимоудаленность для каждой пары соответствующих друг другу точек из A и B - она есть длина отрезка, концами которого являются эти точки. Можно считать характеристикой данного взаиморасположения изображений A и B величину наибольшего из этих отрезков и называть ее взаимоудаленностью точек в A и B . Будем теперь двигать A и B (параллельными переносами) всеми возможными способами. Можно ли этим так расположить изображения относительно друг друга, чтобы взаимоудаленность точек в A и B была бы наименьшей? Ясно, что это нельзя сделать простым перебором, поскольку разных положений для A и B при параллельных переносах бесконечное множество. Можно ли найти нужное взаиморасположение конечной процедурой? Итак, изображением называем конечное (непустое) множество точек на плоскости. Пусть изображение A состоит из n (n 1) точек. Перенумеруем некоторым образом точки из A, точку с номером i будем обозначать ? через ai (i = 1, . . . , n). Через A обозначим множество всех изображений, 99


которые получаются из A параллельными переносами. При этом если ? A A, то полагаем, что на нем сохраняется нумерация точек, порожденная A, то есть через ai на A обозначена точка, в которую при соответствующем параллельном переносе переходит точка ai из A. Изображения A и A ? из A называем эквивалентными. Любая часть точек ai1 , . . . , aik (k n) из A может также рассматриваться как изображение. Его называем частью изображения A. Пусть изображения A и B состоят из точек a1 , . . . , an и b1 , . . . , bn соответственно. Будем рассматривать все возможные биекции на множествах точек изображений A и B . Зафиксируем какую-либо из них и обозначим ее через . Без ограничения общности можем полагать, что ею точке ai ставится в соответствие точка bi (i = 1, . . . , n). Точки ai и bi называем соответствующими, отрезки (ai aj ) и (bi bj ), i, j = 1, . . . , n, i = j тоже называем соответствующими. Введем в рассмотрение изображение C , которое будем называть характеристическим, и которое получается следующим образом. Фиксируем произвольную точку O на плоскости. Параллельным переносом отрезка (ai bi ) совмещаем точку ai с точкой O. Точку, в которую переходит при этом bi , обозначаем через ci . Точку ci называем порожденной точками ai и bi , а точки ai и bi соответствующими точке ci . Изображение C , полагаем, состоит из точки O и точек ci (i = 1, . . . , n). Точку O называем центром изображения C , а часть, составленную из точек c1 , . . . , cn - его ядром. При таком определении несколько точек bi1 , . . . , bik могут при параллельном переносе перейти в одну. Такую точку называем кратной и сохраняем приписанные ей номера, то есть обозначаем ее через ci1 , . . . , cik . Изображение с кратными точками называем особым. Тем самым, следовательно, C может быть особым изображением. Взяв вместо центра O иную точку O на плоскости, описанной процедурой получим характеристическое изображение C из точки O и точек ci (i = 1, . . . , n). Очевидно, что C и C эквивалентны. Точки ci из C и ci из C , порожденные одной и той же парой точек ai и bi , называем соответствующими. Класс изображений, получаемых таким образом при всех возможных центрах на плоскости, обозначим через (B - A). Все изображения из (B -A) переводимы друг в друга параллельными переносами. Поменяв ролями A и B , можно определить (A - B ). Изображения из (B - A) и (A - B ) переводимы друг в друга параллельными переносами и преобразованиями симметрии. По A и любому C (B -A) построим изображение, которое обозначим через A+(B -A). Берем отрезок (Oci ) из изображения C и параллельным переносом совмещаем точку O с точкой ai . Точка, в которую при этом переходит ci , обозначаем через bi . Нетрудно видеть, что изображение из 100


точек bi (i = 1, . . . , n), возникающее таким образом, есть изображение B . Пусть r (A, B ) - длина наибольшего из отрезков Oci (i = 1, . . . , n) в изображении C , то есть то, что выше было названо взаимоудаленностью точек в A и B . Очевидно, что эта величина не зависит от конкретного C (B - A). Ясно, что и r (A, B ) = r (B , A), где r (B , A) определяется по произвольному C (A - B ). Отметим, что если на C рассматривать круг с центром в точке O и радиуса r (A, B ), то все точки изображения C будут находиться внутри круга или на окружности. ? Рассмотрим бинарное отношение P на декартовом произведении A Ч ? : полагаем, что пары (A1 , B1 ) и (A2 , B2 ) из A Ч B находятся в отношении ?? B P , если (A1 , B1 ) как целое переводится параллельным переносом в пару ?? (A2 , B2 ). По отношению P множество A Ч B разбивается на множество P классов эквивалентности, и, очевидно, P имеет мощность континуума. Содержательно каждый класс P из P задает один вариант взаиморасположения изображений A и B с точностью до параллельных переносов пары (A, B ) как целого на плоскости. Из этого следует, что всеми парами (A, B ) из P задается одно и то же, с точностью до параллельных переносов, характеристическое изображение, то есть класс попарно эквивалентных ? ? изображений. Этот класс обозначим через C . Очевидно, что C совпадает с классом (B - A), порожденным любой парой (A, B ) из P . ? Разным классам P1 и P2 из P соответствуют разные классы C1 и ? C2 характеристических изображений. Действительно, рассмотрим такие две пары изображений из P1 и P2 соответственно, у которых первые элементы совпадают, то есть (A, B ) и (A, B ). Это интерпретируется как фиксированное изображение A и сдвинутые по отношению друг к другу параллельным переносом изображения B и B . Последнее означает, что все отрезки (ai , bi ) разнятся с отрезками (ai , bi ) (i = 1, . . . , n) по длине или углу наклона, и, следовательно, параллельными переносами не совмещаются. ? ? Но тогда, соответственно, и C1 с C2 не совпадают. Множество классов характеристических изображений обозначим через C . Каждому классу из P соответствует, как показано, один и только один класс из C . Все изображения из одного класса C характеристических изображений имеют одну и ту же величину r (A, B ), которая, тем самым, есть и характеристика соответствующего класса P из P . Пусть на классе P0 из P достигается минимум величины r (A, B ). Если такой класс P0 существует, то назовем его главным. Итак, изображения внутри каждого класса в C попарно эквивалентны, изображения из разных классов - не эквивалентны. Каждое такое изображение состоит из центра O и точек ci , . . . , cn ядра.

Лемма 1 Ядра всех характеристических изображений из всех классов
101


в C эквивалентны.

Рис. 9. класса в P . Зафиксируем некоторую точку изображения A, пусть это будет точка ai (рис. 9). Рассмотрим характеристическое изображение C пары (A, B ). Без ограничения общности можем полагать, что центр O характеристического изображения совпадает с точкой ai . Тогда точка ci ядра совпадает с точкой bi . Определяем остальные точки cj (j = 1, . . . , n, j = i) ядра. Отрезок (Oci ) получается параллельным переносом отрезка (aj , bj ) с совмещением точки aj с точкой O, то есть с точкой ai . В параллелограмме ai aj bj cj сторона (cj bj ) может рассматриваться как полученная параллельным переносом отрезка (ai aj ). Рассмотрим треугольник ci cj bj . Он определен однозначно: сторона (ci bj ) есть отрезок (bi bj ) из изображения B , сторона (cj bj ) получается параллельным переносом отрезка (ai aj ) из изображения A с совмещением точки aj с точкой bj . Тем самым отрезок (cj bj ) (j = 1, . . . , n, j = i) определен однозначно, а значит определены и все точки ядра. Нетрудно видеть, что в построении треугольника ci cj bj никак не сказывается конкретное взаиморасположение изображений A и B , что и доказывает лемму. Замечание. В треугольнике ci cj bj угол, противолежащий стороне (ci cj ), обозначим через ij и будем называть углом между соответствующими отрезками (ai aj ) и (bi bj ). Угол этот будем считать положительным, если для совмещения со стороной (cj bj ) сторону (ci bj ) нужно повернуть на ij по часовой стрелке, и отрицательным в противном случае. Длина отрезка (ci cj ) может быть вычислена, поскольку соответствующие отрезки и угол между ними при заданных A и B известны. Тем самым все попарные расстояния между точками ядра можно считать известными. Поскольку характеристические изображения из разных классов в C не эквивалентны, то, следовательно, при совмещении параллельными 102

Доказательство. Рассмотрим какую-либо пару (A, B ) из какого-либо


переносами точек их ядер у них не совпадут именно центры. Таким образом, содержательно различие между не эквивалентными характеристическими изображениями состоит в различии положения центра относительно точек ядра. Можно ли утверждать, что и произвольно взятая в качестве центра точка вместе с точками ядра есть в совокупности некоторое характеристическое изображение? Пусть характеристическое изображение C состоит из центра O и точек c1 , . . . , cn ядра. Изображение из точек c1 , . . . , cn и произвольной точки Ox обозначим через Cx .

Лемма 2 Изображение Cx является характеристическим. Доказательство. Достаточно показать, что существует такая пара из
A Ч B , для которой изображение Cx является характеристическим.

Рис. 10. На рис. 10 точки ai и aj принадлежат изображению A, точки bi и bj - изображению B . Строим точки bi и bj , принадлежащие изображению (A + Cx ): точку bi получаем параллельным переносом отрезка (Ox ci ) с совмещением точки Ox с точкой ai , и точку bj - параллельным переносом отрезка (Ox cj ) с совмещением точки Ox с точкой aj . Рассмотрим треугольники bi ai bi и Oci Ox . Стороны (ai bi ) и (ci O), (ai bi ) и (ci Ox ) у них равны и параллельны, углы bi ai bi и Oai Ox равны. Отсюда сторона (bi bi ) равна и параллельна стороне (OOx ). Из аналогичного рассмотрения для треугольников bj aj bj и Ocj Ox получаем, что и (bj bj ) равна и параллельна (OOx ). Таким образом, (bi bi ) равна и параллельна (bj bj ) (i = j, i, j = 1, . . . , n), и, 103


следовательно, изображение из точек bi (i = 1, . . . , n) может быть получено параллельным переносом изображения B . Лемма доказана.

Теорема 1 В P существует и единственен главный класс.
характеристическое изображение Cx , которое принадлежит ровно одному классу в C . Поскольку классам в C взаимнооднозначно соответствуют классы в P , то, тем самым, содержательно Cx определяет ровно один вариант взаиморасположения изображений A и B . Взаимоудаленность точек изображений A и B определяется длиной наибольшего из отрезков (Ox ci ) (i = 1, . . . , n), то есть радиусом окружности с центром в Ox , вмещающей в себя все точки ядра. Ясно, что существует единственная наименьшая по радиусу такая окружность, ее центр и радиус определяются однозначно. Назовем эту окружность ключевой, соответствующий класс из P есть, очевидно, то, что выше было названо главным классом. Теорема доказана. Содержательно теорема 1 означает, что существует единственный вариант взаиморасположения изображений A и B (назовем его тоже главным), при котором взаимоудаленность их точек минимальна. При заданных изображениях A и B главное их взаиморасположение геометрически строится следующим образом. Выбираем произвольную точку O на плоскости в качестве центра, и параллельными переносами отрезков ai bi (i = 1, . . . , n), с совмещением точки ai с точкой O, строим характеристическое изображение. Этим определяется совокупность точек ci (i = 1, . . . , n) ядра. Строим ключевую окружность, ее центр Ox вместе с ядром образуют характеристическое изображение Cx . Далее строим A + Cx , что дает изображение B , эквивалентное B . Взаиморасположение A и B - главное. Рассмотрим в качестве иллюстрации примеры, в которых изображение A состоит из точек a1 , a2 , a3 , изображение B - из точек b1 , b2 , b3 , треугольники a1 a2 a3 и b1 b2 b3 подобны и стороны их параллельны. Пример 1. Этот случай можно назвать вырожденным, треугольники a1 a2 a3 и b1 b2 b3 в нем равны (рис. 11), точки ядра c1 , c2 , c3 слиты в одну. Пример 2. В этом примере треугольник c1 c2 c3 тупоугольный (рис. 12), поэтому центр Ox располагается на середине наибольшей стороны треугольника. На ключевой окружности находятся две точки ядра, одна точка ядра внутри круга. Пример 3. В этом случае треугольник c1 c2 c3 остроугольный (рис. 13(а)), центр Ox ключевой окружности - центр описанной окружности треугольника c1 c2 c3 . На ключевой окружности - три точки ядра. На рис. 13(б) построено главное взаиморасположение изображений A и B . 104

Доказательство. Произвольная точка Ox вместе с точками ядра дает


Радиус ключевой окружности может быть определен не только геометрическим построением, но и вычислением. В соответствии с замечанием к лемме 1 все попарные расстояния между точками ядра можно считать известными. Далее вычисления разбиваются на два случая, иллюстрируемых примерами 2 и 3 выше. Первый случай. На ключевой окружности находятся две точки, ci1 и ci2 , причем отрезок (ci1 ci2 ) - диаметр окружности, а все остальные точки ядра находятся внутри круга. Необходимым и достаточным условием этого является то, что отрезок (ci1 ci2 ) - наибольший по длине, и треугольники ci1 ci2 ci (i = 1, . . . , n, i = i1 , i2 ) - тупоугольные (включая случай, когда ci лежит на отрезке (ci1 ci2 )). При известных попарных расстояниях между точками ядра это условие проверяется несложно.

105


Рис. 11,12,13(a),13(б). Сюда же отнесем и в некотором смысле пограничный случай, когда на ключевой окружности, помимо точек ci1 и ci2 , есть еще и другие точки ядра. В этом случае они должны с точками ci1 и ci2 образовывать прямоугольный треугольник. Второй случай. Положим, что первый случай уже исключен. Это значит 106


что на ключевой окружности лежат три и больше точек, причем никакая пара из них не образует диаметр окружности. В этом случае ключевая окружность является описанной окружностью треугольника из точек, лежащих на окружности, и этот треугольник - остроугольный. Для нахождения радиуса ключевой окружности надо перебрать все остроугольные треугольники с вершинами в точках ядра и определить треугольник с наибольшей по радиусу описанной окружностью. Она и будет ключевой, все остальные точки ядра будут содержаться внутри круга (или, в крайнем случае, на самой окружности, когда остроугольных треугольников с наибольшим радиусом описанной окружности несколько). Предшествующее описание относилось к случаю, когда биекцией точки a1 , . . . , an изображения A сопоставлялись точкам b1 , . . . , bn изображения B . Обозначим через r (A, B ) = min{r (A, B )}, где минимум берется на множестве всех величин r (A, B ), полученных при всех возможных биекциях на множествах точек изображений A и B . ^ Обозначим через B изображение, полученное из B преобразованием симметрии, и через r (A, B ) - величину, определяемую как r (A, B ) = ^ r (A, B ). Наконец, через r(A, B ) обозначим r(A, B ) = min(r (A, B ), r (A, B )). Содержательно r(A, B ) определяет наименьшую взаимоудаленность точек изображений A и B при всех возможных параллельных переносах и преобразованиях симметрии изображений и при всех возможных вариантах сопоставлений их точек друг другу.


107


2 Изометрические преобразования изображений
Содержательно задача для этого параграфа повторяет задачу для параграфа предшествующего, но с добавлением возможности поворачивать изображения относительно друг друга. Таким образом, для двух изображений нужно параллельными переносами, преобразованиями симметрии и поворотами, то есть изометрическими преобразованиями, так расположить их, чтобы взаимоудаленность их точек была бы наименьшей. ~ Через A обозначим множество всех изображений, получаемых из изображения A параллельными переносами и поворотами. Углы поворота считаем положительными при вращении против часовой стрелки, и отрицательными ~ - в противном случае. При этом для A A полагаем, что сохраняется нумерация точек, порожденная изображением A, то есть через ai обозначена та точка на A , в которую переходит точка ai (i = 1, . . . , n) при соответствующем ~ вращении и переносе изображения A. Изображения A и A из A называем эквивалентными по переносу и повороту (далее, для краткости, просто эквивалентными), точки ai и ai (i = 1, . . . , n) - тоже эквивалентными. Части изображений A и A , состоящие из эквивалентных точек, называем эквивалентными. Рассматриваем биекцию , которая точкам a1 , . . . , an изображения A ставит в соответствие точки b1 , . . . , bn изображения B . Для изображений ~ ~ A A и B B точки ai и bi (i = 1, . . . , n) называем соответствующими. Части изображений A и B , состоящие из соответствующих точек, называем соответствующими. Угол между соответствующими отрезками (ai aj ) из 0 A и (bi bj ) из B обозначаем через ij (i, j = 1, . . . , n, i = j ). ~~ Рассматриваем декартово произведение AЧB . Без ограничения общности 0 0 можно полагать, что среди углов ij (i, j = 1, . . . , n, i = j ) есть угол uv , равный нулю. Далее через будем обозначать угол uv , если uv 0, и угол (2 + uv ), если uv < 0. Отсюда 0 < 2 . Угол будем называть углом между изображениями A и B . ~ ~ На множестве A Ч B рассматриваем бинарное отношение P : пары (A1 B1 ) и (A2 B2 ) находятся в отношении P , если углы между соответствующими 2 1 отрезками у них одинаковы, то есть ij = ij при всех i, j = 1, . . . , n, i = ~ ~ j . Это отношение порождает разбиение множества A Ч B на классы эквивалентности. Каждому классу соответствует свое значение угла между изображениями A и B , поэтому класс обозначим через P , множество классов - через {P }0<2 . Пусть Q и Q - ядра характеристических изображений произвольных пар (A , B ) и (A , B ) из P , ci и cj - точки из Q , ci и cj - соответствующие точки из Q (i, j = 1, . . . , n, i = j ). Длины отрезков (ci cj ) и (ci cj ) 108


определяются только длинами соответствующих отрезков (ai aj ), (bi bj ) и (ai aj ), (bi bj ) и углом между ними, и потому одинаковы. Множество ядер всех характеристических изображений всех пар (A, B ) из P обозначим через Q . Из сказанного следует, что все изображения из Q переводятся друг в друга преобразованиями параллельного переноса и поворота. Поэтому можно говорить об общей для всех ядер из Q величине радиуса ключевой окружности, обозначим ее через R . Через P обозначим подкласс класса P , состоящий из всех таких пар, у которых центр характеристического изображения совпадает с центром ключевой окружности. Величина R есть функция от . Минимальное значение R (0 min min < 2 ) обозначим через R . Угол 0 такой, что R0 = R назовем искомым. Взаиморасположение A и B в парах (A, B ) из P0 тоже назовем искомым. Содержательно искомое взаиморасположение A и B означает, что их точки взаимоудалены на минимальное расстояние, какого можно добиться параллельными переносами и поворотами изображений A и B . Мы используем далее эквивалентное прежнему, но более наглядное и удобное представление о множестве классов {P }0<2 и об искомом ~ взаиморасположении. Зафиксируем какое-либо изображение из A, пусть, для определенности, это будет исходное изображение A. Из каждого класса P возьмем ту пару (A, B ), у которой первый элемент совпадает с A. Если проделывать это последовательно для всех от 0 до 2 , то наглядно это можно представить как неподвижное изображение A и последовательно поворачивающееся относительно A изображение B , причем в каждый момент взаиморасположение A и B - главное. Точки, из которых состоит B , обозначим через b , . . . , b . Для пары 1 n (A, B ) строится характеристическое изображение, состоящее из точек c , . . . , c ядра и центра O, совпадающего с центром ключевой окружности. 1 n Точка O фиксирована и центры всех ключевых окружностей (при разных ) совпадают с точкой O. При таком представлении величина R и изображение из точек c , . . . , c - функции от угла . Вопрос в том, при 1 n каких углах поворота величина R наименьшая? Рассмотрим сначала для примера частный случай, в котором поставленная задача решается просто. Пусть изображения A и B таковы, что они переводимы друг в друга преобразованием подобия. Положим для конкретности, что B получено из A увеличением или уменьшением в размерах с коэффициентом k и поворотом на угол . При повороте B на произвольный угол попарные расстояния между точками c и c ядра (i, j = 1, . . . , n, i = j ) i j вычисляются по формуле (c c )2 = (ai aj )2 + (bi bj )2 - 2(ai aj )(bi bj ) cos( + ij ). Поскольку (bi bj ) = k (ai aj ), то (c c )2 = (ai aj )2 (1 + k 2 - 2k cos( + )). ij Это значит, что при вращении изображения B ядро характеристического изображения пары (A, B ) меняется, оставаясь подобным самому себе (и, 109


заметим, изображениям A и B ). Наименьшими все попарные расстояния между точками ядра, а следовательно и радиус ключевой окружности, будут при ( + ) = 0. Таким образом, искомое взаиморасположение для A и B характеризуется тем, что все соответствующие отрезки на этих изображениях (то есть (ai aj ) и (bi bj ), i, j = 1, . . . , n, i = j ) параллельны друг другу. В рассмотренном примере ядро, меняясь в размерах, остается подобным себе, и потому на ключевой окружности при всех углах поворота находятся одни и те же точки (то есть те точки, которые выше были названы соответствующими). В общем случае точки ядра меняют расположение относительно друг друга, и потому при разных на ключевой окружности могут оказываться разные точки. Итак, имеем изображения A из точек a1 , . . . , an , B из точек b , . . . , b 1 n и C из точек c , . . . , c ; R - радиус ключевой окружности для C . Пусть 1 n изображение Ai есть часть A из точек ai1 , . . . , aik , Bi есть часть B из точек b , . . . , b , Ci есть часть C из точек c , . . . , c (1 k n). i1 ik i1 ik Изображение Ci называем порожденным изображениями Ai и Bi , а сами изображения Ai и Bi называем соответствующими Ci . Через ri обозначим радиус ключевой окружности изображения Ci . Изображение Ci назовем монотонным в точке , если существует такое > 0, что в промежутке от - до + радиус ri либо монотонно возрастает, либо монотонно убывает. В противном случае Ci называем немонотонным в точке . Значения углов , в которых Ci немонотонно, называем критическими для Ci , взаиморасположения соответствующих Ci изображений Bi и Ai при критических углах тоже называем критическими. Пусть угол 0 - искомый. Тогда ядро C - немонотонное изображение в точке 0 , следовательно, угол 0 для C - критический. Идея дальнейших построений состоит в выделении на C особых частей, минимальных по количеству точек, для которых 0 - тоже критический угол. Эти особые части назовем ключевыми изображениями и определим следующим образом. Пусть для Ci - части изображения C - выполняется условие: угол 0 для Ci - критический, и ri = R0 . Пусть для Cj - любой части изображения Ci - это условие не выполняется. Тогда Ci называем ключевым изображением, а соответствующие Ci изображения Ai и Bi тоже называем ключевыми. Из последнего определения следует, что искомый угол может находиться только среди критических углов ключевых изображений. Все возможные ключевые изображения разобьем на три класса: 1) из двух точек, 2) из трех точек, 3) из четырех и более точек. Рассмотрим последовательно эти три случая. 110


Первый случай. Ключевые изображения состоят из двух точек: c0 , c0 i1 i2 из C0 , ai1 , ai2 из A и b0 , b0 из B0 . В этом случае отрезок (c0 c0 ) i1 i2 i1 i2 должен быть диаметром ключевой окружности, и (c0 c0 )2 = (ai1 ai2 )2 + i1 i2 (b0 b0 )2 -2(ai1 ai2 )(b0 b0 ) cos(i1 i2 +0 ). Отсюда следует, что критические i1 i2 i1 i2 углы для рассматриваемых ключевых изображений определяются необходимым 0 условием: | cos(i1 i2 + )| = 1. Это значит, что соответствующие отрезки 0 0 (ai1 ai2 ) и (bi1 bi2 ) должны быть параллельными, то есть угол между ними равен нулю или . Ясно, что 0 определяется равенством угла между соответствующими отрезками нулю. При этом R0 равен половине модуля разности длин отрезков (ai1 ai2 ) и (bi1 bi2 ). Обозначим через U1 множество значений угла , при которых углы между соответствующими отрезками (ai aj ) и (bi bj ) (i, j = 1, . . . , n, i = j ) равны нулю. Второй случай. Ключевые изображения состоят из трех точек: c0 , c0 , i1 i2 c0 из C , ai1 , ai2 , ai3 из A и b0 , b0 , b0 из B0 . Положим сначала, что i3 i1 i2 i3 никакие две из точек c0 (j = 1, 2, 3) не сливаются в одну, то есть c0 c0 c0 ij i1 i2 i3 - остроугольный треугольник (рис. 14). Длины отрезков (ai1 b0 ), (ai2 b0 ), (ai3 b0 ) одинаковы и равны R0 . i1 i2 i3 Отрезки будем полагать направленными с направлением от точек aij к b0 или наоборот. Пусть, для определенности, отрезки направлены от ij aij к b0 (j = 1, 2, 3). Рассмотрим направленные прямые L1 , L2 , L3 , на ij которых лежат эти отрезки, с направлениями для всех трех прямых, совпадающими с направлениями отрезков или противоположными им. Пусть, для определенности, направления прямых Lj совпадают с направлениями отрезков (aij b0 ) (j = 1, 2, 3), лежащих на них. ij

Лемма 3 Для того, чтобы взаиморасположение изображений из точек
ai1 , ai2 , ai3 и b0 , b0 , b0 было критическим, необходимо, чтобы прямые i1 i2 i3 L1 , L2 , L3 пересекались в одной точке.

Доказательство. Заметим сначала, что в треугольнике c1 c2 c3 длины iii

его сторон являются непрерывными функциями от угла . В точке 0 треугольник c0 c0 c0 по условию остроугольный, поэтому существует i1 i2 i3 окрестность точки 0 такая, что при углах из этой окрестности он остается остроугольным.

111


Рис. 14-15.

Рис. 16(а),(б). Прямая Lj (j = 1, 2, 3), если смотреть по ее направлению, делит плоскость на правую и левую полуплоскости. Пусть O - произвольная точка в правой полуплоскости (рис. 15). Правая часть перпендикуляра к отрезку (O b0 ) в точке b0 находится вне круга радиуса R0 с центром ij ij в точке aij , для левой части перпендикуляра участок, примыкающий к b0 , находится внутри круга. Поэтому существует угол > 0 такой, ij что поворот вправо точки b0 с центром вращения в O на угол, не ij больший , удаляет точку b0 от aij , а поворот влево на такой же ij угол - приближает. Аналогично для любого центра вращения O в левой полуплоскости поворот вправо приближает точку b0 , поворот влево ij удаляет ее от aij . Предположим, что L1 , L2 , L3 не пересекаются в одной точке. Тогда они образуют треугольник, все внутренние точки которого являются точками их правых полуплоскостей (рис. 16(а)), или левых полуплоскостей 112


(рис. 16(б)). В любом из этих случаев вращение B0 с центром вращения в любой из внутренних точек этого треугольника в одну сторону удаляет одновременно все точки b0 от соответствующих точек aij (j = 1, 2, 3), в ij другую - одновременно приближает их к ним. Длины отрезков (aij b0 ) ij (j = 1, 2, 3) и углы между ними при таком вращении являются непрерывными функциями от угла (в некоторой окрестности точки 0 ). Следовательно, изображение из точек c0 , c0 , c0 монотонно в точке 0 - пришли к i1 i2 i3 противоречию. Лемма доказана. Пересекающиеся в одной точке прямые L1 , L2 , L3 назовем трехосником, сами прямые - осями, точку OL пересечения - центром трехосника. На каждой оси часть ее от центра в направлении оси называем положительной полуосью, оставшуюся часть - отрицательной полуосью. Все возможные варианты расположения точек ai1 , ai2 , ai3 и b0 , b0 , i1 i2 b0 на трехоснике можно представить четырьмя классами. i3 1. Класс S1 : отрезки (a0 b0 ) (j = 1, 2, 3) все одновременно лежат в ij ij положительных полуосях (рис. 17(а)), или все одновременно - в отрицательных полуосях (рис. 17(б)). 2. Класс S2 : один из отрезков (aij b0 ) (j = 1, 2, 3) лежит в положительной ij полуоси, два других - в отрицательных полуосях (рис. 18(а)), или наоборот, один отрезок лежит в отрицательной полуоси, два других - в положительной (рис. 18(б)). Классами S1 и S2 исчерпываются такие варианты размещения точек на осях, когда каждый из отрезков (aij bij0 ) (j = 1, 2, 3) целиком лежит либо в положительной полуоси, либо в отрицательных. 3. Класс S3 : для всех трех отрезков (aij b0 ) (j = 1, 2, 3) центр трехосника ij 0 расположен между точками aij и bij (рис. 19). 4. Класс S4 : у одного или двух отрезков из (aij b0 ) (j = 1, 2, 3) центр ij трехосника лежит на отрезке, остальные целиком лежат в отрицательной или положительной полуосях (два примера на рис. 20).

113


Рис. 17-20. Классы S1 и S2 представляют варианты искомого взаиморасположения: нетрудно видеть, что вращение B0 относительно центра трехосника в любую сторону (на угол, не превышающий некоторый ) удаляет точки b0 от соответствующих точек aij (j = 1, 2, 3). В S3 взаиморасположение ij 114


точек критическое, но не искомое: вращение B0 относительно центра трехосника в любую сторону приближает соответствующие точки друг к другу. В классе S4 только часть взаиморасположений искомые. Итак, искомое взаиморасположение находится среди взаиморасположений изображений из точек ai1 , ai2 , ai3 и b0 , b0 , b0 , представленных классами i1 i2 i3 S1 - S4 . Следующий вопрос: как найти эти взаиморасположения при конкретных изображениях A и B ? Условимся о следующих обозначениях. Отрезки (aij b0 ) (j = 1, 2, 3) ij будем представлять величиной R, где |R| = R0 , причем будем считать R положительным, если направление отрезка совпадает с направлением оси, на которой он лежит, и отрицательным в противном случае. Отрезки (OL ai1 ), (OL ai2 ), (OL ai3 ) считаем направленными от OL к aij (j = 1, 2, 3), и представляем их величинами x, y , z соответственно. Длину отрезка (OL ai1 ) полагаем равной |x|, x полагаем положительным, если направление (OL ai1 ) совпадает с направлением оси L1 , и отрицательным в противном случае. Аналогично полагаем и для y и z . Углы (положительные, меньшие , в сумме составляющие 2 ) между осями L1 и L2 , L1 и L3 , L2 и L3 обозначим через , , соответственно. На рис. 21 для двух примеров показаны соответствующие обозначения. Ясно, что задание конкретных значений для x, y , z , , , , R определяет конкретное взаиморасположение точек ai1 , ai2 , ai3 и bi1 , bi2 , bi3 , а значит и конкретное значение угла между изображениями A и B .

bi2 , bi3 , представленные в классах S1 , S2 , S3 , S4 , находятся среди решений следующей системы уравнений: (ai1 ai2 )2 (bi1 bi2 )2 (ai1 bi3 )2 (bi bi )2 132 (ai2 ai3 ) (bi bi )2 23 ++ = = = = = = x2 + y 2 - 2xy cos (x + R)2 + (y + R)2 - 2(x + R)(y + R) cos x2 + z 2 - 2xz cos (x + R)2 + (z + R)2 - 2(x + R)(z + R) cos y 2 + z 2 - 2y z cos (y + R)2 + (z + R)2 - 2(y + R)(z + R) cos = 2

Лемма 4 Все варианты взаиморасположения точек ai1 , ai2 , ai3 и bi1 ,

115


Рис. 21. системы уравнений для каждого из вариантов, представленных классами S1 - S4 . Рассмотрим произвольную тройку точек a из A и тройку соответствующих ~ ~ из B . Для изображений a и ~ при определении для них искомого точек b ~b взаиморасположения возможны только первый и второй случаи. Если имеет место первый случай, то определяемое им значение угла между изображениями A и B находится среди углов из множества U1 . Во втором случае искомый угол находится среди набора u углов, определяемых ~ решениями системы уравнений из леммы 4. Обозначим через U2 объединение множеств u, полученных для всех возможных троек точек из A и соответствующих ~ троек точек из B . Везде выше предполагалось, что точки c0 , c0 , c0 - разные. Рассмотрим i1 i2 i3 теперь вырожденный случай, когда две из этих точек, для определенности c0 и c0 , сливаются в одну (рис. 22). Поскольку длина отрезка (c0 c0 ) i2 i3 i2 i3 в этом случае равна нулю, то необходимым условием для этого является равенство по длине отрезков (ai2 ai3 ) и (bi2 bi3 ) и равенство нулю угла i2 i3 . Отсюда следует, что определяемые необходимым условием для всех возможных вырожденных случаев углы между изображениями A и B находятся среди углов множества U1 .

Доказательство. Проводится непосредственной проверкой: написанием

Рис. 22. 116


Рис. 23. На рисунке 23 представлены примеры, относящиеся к вырожденному случаю и выполнению для него необходимого условия: на (а) - искомое взаиморасположение, на (б) - не искомое. Третий случай. Ключевые изображения состоят из четырех и более точек. Рассмотрим четыре из них: c0 , c0 , c0 , c0 . Полагаем, что никакие i1 i2 i3 i4 две из них не сливаются в одну. Из теоремы Птолемея следует, что для того, чтобы точки c0 , c0 , c0 , c0 находились на одной окружности, i1 i2 i3 i4 необходимо и достаточно, чтобы выполнялось одно из трех равенств:

+(c0 c0 )(c0 c0 ) + (c0 c0 )(c0 c0 ) + (c0 c0 )(c0 c0 ) = 0. i1 i2 i3 i4 i1 i3 i4 i2 i1 i4 i2 i3
Величина каждого из отрезков в этих уравнениях есть функция от угла между изображениями A и B . Следовательно, задача нахождения возможных критических углов для этого случая сводится к решению этих уравнений, неизвестным в которых является угол . Такие уравнения составляем для всех четверок точек ai1 , ai2 , ai3 , ai4 из A и соответствующих четверок точек bi1 , bi2 , bi3 , bi4 из B . Множество углов , являющихся решениями получаемых уравнений, обозначим через U3 . Обозначим через U объединение множеств U1 , U2 , U3 .

Теорема 2 Искомый угол 0 находится среди углов множества U . Доказательство. Следует из того, что, по построению, U включает все


возможные критические углы для всех возможных ключевых изображений. Итак, пусть определен угол 0 , следовательно, найдено значение R0 = min min R . Обозначим через R (A, B ) min R , где минимум берется на множестве
min величин R , полученных при всех возможных биекциях на множествах точек изображений A и B . ^ Обозначим через B изображение, полученное из B преобразованием ^ симметрии, и пусть R (A, B ) = R (A, B ).

117


Наконец, через R(A, B ) обозначим min(R (A, B ), R (A, B )). Величина R(A, B ) определяет наименьшую взаимоудаленность точек изображений A и B при всех возможных сопоставлениях этих точек друг другу и при всех возможных изометрических преобразованиях этих изображений. Нетрудно видеть, что алгоритм нахождения R(A, B ), если прямо следовать описанному выше, в значительной мере переборный, и потому довольно трудоемок. Это происходит из того, что цель настоящей работы состояла, в первую очередь, в доказательстве существования конечной процедуры нахождения R(A, B ). Задача нахождения на основе этой процедуры эффективного при использовании на практике алгоритма - следующая по очередности задача. Возможности к ее решению есть и здесь будет обозначен только один момент, с этим связанный. Наиболее чревато трудоемкостью то обстоятельство, что нужно рассматривать все биекции между точками изображений A и B , и для каждой находить искомый угол 0 . Таких биекций n!, где n - количество точек в изображениях A и B . Воспользуемся, однако, тем, что конкретное взаиморасположение любых двух частей a ~ ~ изображений A и B определяет и некоторый угол между самими иb изображениями A и B . Рассмотрим все возможные части a2 из двух ~ точек изображения A и все варианты сопоставления им частей ~2 из двух b ~2 ) будет 2(C 2 )2 . Обозначим через точек изображения B . Таких пар (a2 , b ~ n ~1 множество критических углов для этих пар. Аналогично рассмотрим U 3 пары (a3 , ~3 ) частей изображений A и B из трех точек, их будет 6(Cn )2 . ~b ~ ~ Множество их критических углов обозначим через U2 . Наконец, через U3 обозначим множество критических углов пар (a4 , ~4 ) частей из четырех ~b 4 точек изображений A и B , таких пар будет 24(Cn )2 . Искомый угол будет ~ ~ ~ находиться среди углов объединения U1 U2 U3 . При такой процедуре от перебора n! биекций мы избавлены. Автор глубоко благодарен Ю.И. Журавлеву и В.Б. Кудрявцеву за внимание к работе. Работа поддерживалась грантом РФФИ 98-01-00652.

Список литературы
[1] Козлов В.Н. Математическое моделирование зрительного восприятия // Математические вопросы кибернетики. Вып. 6. М. Наука. 1996. C. 321-338. [2] Козлов В.Н. О кодировании дискретных фигур // Дискретная математика. 1996. T. 8. N 6. C. 57-61. [3] Kozlov V.N. Image Coding and Recognition and Some Problems of Stereovision // Pattern Recognition and Image Analysis. 1997. V. 7. N 4. P. 448-466.

118