СПОСОБ ФИКСАЦИИ ИЗОБРАЖЕНИЯ ОБЪЕКТА Российский патент 1994 года по МПК G06K9/52 

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

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

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

В качестве другого аналога предлагаемого способа может быть рассмотрен метод аппроксимации изображения объекта (на плоскости) многоугольником [2]. Метод заключается в следующем: устанавливают границы контура изображения, которые распознаются как сегменты и представляются в виде прямолинейных отрезков, затем выделяют координаты точек их пересечения (вершин). Аналог обладает недостатком, заключающимся в отсутствии возможности использования результата для обоснованной характеристики положения контура или взаиморасположения контуров.

За прототип предлагаемого способа принимается способ аппроксимации плоских изображений объектов, по которому в изображении объекта (закодированному, например, в виде серий) множеству оттенков серого цвета условно сопоставляются два цвета: черный и белый, т.е. изображение превращается в двухградационное [3]. Далее по известным правилам выделяют контурные точки, ограничивающие область изображения объекта. Область должна быть связной, т.е. любые две ее точки могут соединяться непрерывной (соединяющей соседние элементы) кривой, не выходящей за пределы области. При проверке на связность и ограниченность, например, при простой картине изображения достаточно убедиться в замкнутости границы* (* - представляемой в виде простой замкнутой ломаной, соединяющей соседние элементы изображения (контура)), окружающей все точки области. Индекс связности (многосвязность) в прототипе не рассматривается.

Представление контуров изображений в способе-прототипе осуществляется по результатам их аппроксимации стандартными геометрическими фигурами: прямоугольником, кругом, эллипсом, ромбом, равнобедренным треугольником и т.д. Аппроксимация осуществляется путем переноса стандартной фигуры из канонического положения до совмещения ее ц.т. с ц.т. контура изображения. Координаты ц.т. (х_о, у_o) рассчитываются по формулам X_o= X_i/r ; Y_o= Y_i/r ; где x_i, y_i - координаты i-й точки контура; r - число точек контура. Для вытянутых стандартных фигур также осуществляется поворот системы координат до совмещения главных осей тяжести аппроксимируемой и аппроксимирующих фигур (контуров). Далее для определения размеров стандартной фигуры, обеспечивающих близость ее контура к контуру изображения, проводится сопоставление положений ц. т. в правой, левой, нижней и верхней полуплоскостях контуров. Выбор контура наилучшей аппроксимации (из множества контуров) осуществляется по достижении наименьшей суммы квадратов расстояний от точек контура изображения до аппроксимирующего контура.

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

Целью изобретения является унификация представления контуров изображения объектов и уменьшение зависимости положения центра контура и погрешностей представления от положения точек контура изображения объекта.

Цель достигается при осуществлении способа фиксации изображения объекта, в котором выделяют контур, ограничивающий связную плоскую область изображения объекта, используют в качестве стандартного контура изображение окружности выбранного радиуса R, центр которой совмещают с центром контура изображения объекта, за центр контура принимают точку середины отрезка, соединяющего две наиболее разнесенные вершины выпуклой фигуры контура изображения объекта, если при возможных соединениях концов этого отрезка с другими вершинами выпуклой фигуры контура изображения объекта не образуется остроугольный треугольник или в остальных случаях, за центр контура изображения объекта принимают точку пересечения перпендикуляров к серединам сторон одного из остроугольных треугольников, имеющих в качестве вершин вершины выпуклой фигуры контура и такого, что описанная вокруг него окружность имеет наименьший радиус среди описанных вокруг остроугольных треугольников окружностей, ограничивающих область, содержащую все точки контура изображения объекта, находят область погрешностей фиксации как пересечение кругов с радиусом R и центрами, расположенными в вершинах фигуры, гомотетичной к выпуклой фигуре контура изображения объекта, с коэффициентом преобразования -1 и центром преобразования, совпадающим с центром контура, при его совмещении с центром окружности R, причем R берут не менее значения, обеспечивающего включение в круг с радиусом R всех точек контура объекта.

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

Под событием фиксации (Третьяков В. В. Погрешности и статистическая оценка фиксации круговой зоны освещения/Светотехника, 1991, N 2) понимается событие, при котором все рассматриваемые точки находятся внутри круга. Для множества вершин контура фиксацию удобнее представлять как событие V iP{ (x_i--x_o)²+(y_i-y_o)² ≅ R²} , где i = 1(1)n - дискретная переменная, обозначающая номер вершины выпуклой части контура изображения объекта, имеющей координаты (x_i, y_i); R - радиус фиксирующей окружности; n - число вершин выпуклой части контура изображения объекта. Для общности рассмотрения считается, что n может принимать значения n = 1(1) ∞. При таком определении область фиксации можно представить в виде окружности, внутри которой в произвольном положении, получаемом при параллельном переносе фиксируемой фигуры, находится точка (n = 1) или отрезок с двумя точками на концах (n = 2), или треугольник (n = 3), или фигура выпуклого n-треугольника (n ≥ 4), или фигура, ограниченная непрерывным выпуклым контуром (n = ∞).

При фиксации произвольного контура целесообразно рассматривать только его выпуклую часть (многоугольник называется выпуклым, если он целиком лежит по одну сторону от любой прямой, содержащей одну из его сторон - см. Рывкин А.А., Рывкин А.З., Хренов Л.С. Справочник по математике. - М.: Высш. шк., 1987, с. 112), так как касаться фиксирующей окружности могут только (и то не всегда) вершины выпуклой части контура (в силу выпуклости окружности). Для нахождения выпуклой части контура нужно при его последовательном обходе проверять условие выпуклости и спрямлять отрезками невыпуклые дискретизированные или непрерывные участки контура.

При фиксации выпуклой части контура изображения объекта возможны три основных варианта, к которым сводятся все остальные. В первом варианте окружность, построенная на отрезке, соединяющем наиболее разнесенные точки А и В выпуклого контура ACBD (фиг. 1), ограничивает область, содержащую все точки выпуклого контура. В этом случае при соединении концов отрезка АВ = 2R_κν с другими вершинами выпуклого контура не образуется остроугольный треугольник. Окружность, построенная на АВ = 2 R_κν , с центром в середине отрезка является окружностью полной фиксации, т.е. фиксируемая фигура не имеет возможности смещения, а погрешность фиксации, определяемая вектором смещения центра фиксации фиксируемого контура относительно центра фиксирующей неподвижной окружности, равна нулю. Учитывая, что положение полной фиксации обеспечивает возможность точного измерения положения контура, естественно считать центром контура в этом варианте середину отрезка АВ.

Во втором варианте (фиг. 2) в выпуклом контуре ACBD имеются вершины, лежащие вне области, ограничиваемой окружностью, построенной из середины отрезка, соединяющего наиболее разнесенные вершины выпуклого контура, с радиусом R_κν = AB/2. При этом существует возможность построения окружности (R₂), проходящей через вершины А, В и одну из других вершин выпуклого контура, причем такую (в данном случае С), что построенная окружность является наименьшей из окружностей, описывающих остроугольные треугольники (на А, В и каких-либо других вершинах) и содержащих все точки выпуклого контура. В данном варианте центр этой окружности, являющейся по определению окружностью полной фиксации, определяет положение центра выпуклого контура, который находится на пересечении перпендикуляров к серединам сторон остроугольного треугольника (АС и АВ треугольника АСВ).

В третьем варианте (фиг. 3) так же, как во втором, в выпуклом контуре имеются вершины, лежащие вне области, ограничиваемой окружностью, построенной на отрезке, соединяющем наиболее разнесенные вершины, как на диаметре (АВ). Кроме того, ни одна из окружностей, проходящих через А, В и третью вершину контура, не ограничивает область, содержащую все точки контура. В таком случае выделяется сторона или диагональ выпуклого контура, меньшая АВ, но наибольшая среди других сторон или диагоналей. Далее поиск окружности минимального радиуса повторяют на выделенном отрезке. Как следует из фиг. 3, таким отрезком является диагональ CD, а треугольник ACD имеет описанную окружность минимального радиуса, обеспечивающую включение в область, ограниченную ею, всех вершин выпуклого контура. Тогда точка пересечения перпендикуляров к серединам сторон CD, AD, AC является центром выпуклого контура ACBD.

При фиксации контуров в виде правильных n-угольников (n ≥ 3) или неправильных выпуклых, но описываемых окружностью, при поиске центра контура действуют по аналогичным правилам. При наличии нескольких одинаковых диагоналей или сторон делается произвольный выбор.

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

Из-за нечеткости контура или наличия шумов, искажающих контур, с целью иметь некоторый запас по размерам полезно проводить фиксацию (представление) контуров окружностями, имеющими радиус больший, чем радиус окружности полной фиксации. Возникающая при этом область погрешностей фиксации имеет, как показано в статье В.В. Третьякова: "Погрешности и статистическая оценка фиксации круговой зоны освещения". Светотехника, 1991, N 2, полный текст работ деп. в Информэлектро (9-ЭТ 91 и 10-ЭТ 91 от 11.1.91 г.), общее уравнение границы. Там же приведены данные и обоснование по полученной фигуре области погрешностей, сопровождающей фиксацию окружности и отрезка (n = 2), в виде, как показано на фиг. 4 (заштрихованная фигура с двумя изломами границы). При касании окружностью полной фиксации трех вершин контура начальная фигура области погрешностей имеет границу с тремя изломами. Под "начальной" понимается фигура области погрешностей, которая возникает первой при увеличении радиуса фиксирующей окружности от его значения, соответствующего радиусу полной фиксации: фигура с двумя изломами, с тремя изломами или с i изломами. Последняя фигура возникает в тех случаях, когда окружность полной фиксации проходит через i вершин выпуклого контура (i ≅ n). Если в формировании области погрешностей на начальном этапе участвует i вершин (обычно две или три), то при увеличении радиуса R появляется возможность касания фиксирующей окружности более чем i (двумя или тремя) вершинами. Количество изломов границы в фигуре погрешностей за счет этого увеличивается. При некотором увеличении R область погрешностей становится фигурой с n точками изломов, после чего при увеличении R количество изломов границы не изменяется. Картины деформирования области погрешностей фиксации при увеличении R для начальных двухвершинной и трехвершинной фиксации показаны соответственно на фиг. 4-7 и 8-10.

При построении областей погрешностей фиксации (представления) используются вершины выпуклой части контура изображения объекта в виде аппроксимирующего n-угольника или выпуклой фигуры с непрерывными границами, функция дискретизации (выделения вершин) которых определяется в процессе работы. Для дискретизированного контура изображения объекта находится фигура вершин, гомотетичная к исходной, с коэффициентом преобразования -1 и центром преобразования, совпадающим с центром контура. Фигуры таких контуров показаны на фиг. 4-7 и 8-10 пунктирными линиями. Область погрешностей фиксации находится как пересечение кругов с центрами в вершинах фигуры, гомотетичной к исходному контуру. Правомерность такого построения доказывается следующим образом.

В отношении вершин n-угольника выпуклой части контура изображения объекта очевидно (фиг. 7), что способ построения позволяет геометрически найти расстояние между вершиной и окружностью по линии центр фиксации - вершина n-угольника (при совпадении центров фиксации и контура в направлении, заданном углом ϕ). Далее, рассматривая возможные смещения n-угольника при параллельном переносе, нетрудно доказать равенство допустимых смещений в различных направлениях для одной из вершин n-угольника (P или F) и центра контура (заштрихованные области с вершинами углов, совпадающими с вершинами n-угольника, и соответствующие участки области погрешностей, фиг. 7). Из равенства смещений вершины и центра контура следует правомерность приемов и операций построения области погрешностей при фиксации.

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

Из результатов рассмотрения также следует, что при реализации изобретения применяемая совокупность приемов и операций вместе с последовательностью их проведения позволяет унифицировать представление (фиксацию) изображений объектов в виде положения центра, габаритного радиуса R и области погрешностей представления (фиксации). Получаемые параметры позволяют иметь единственное и варьируемое в интересах пользователя (X_o, Y_o, R) представление (фиксацию) для произвольного выпуклого контура, ограничивающего связную область изображения объекта на плоскости.

Предлагаемый способ фиксации изображения объекта может осуществляться с помощью общеизвестных технических средств. Пусть реализация способа проходит в условиях, указанных на с. 3 для односвязной области изображения (при связности с большим индексом выделяются точки внешнего контура как соседние с точками изображения, имеющими максимальные абсолютные значения одной или двух координат). Прием, заключающийся в выделении контурных точек изображения, описан в указанной выше книге Е.А. Бутакова и др. на с. 27. При реализации приема, точки, соседние с оцениваемой точкой b_j, находящиеся в рецепторном поле, алгоритмически анализируют на принадлежность к изображению. Анализ осуществляется путем последовательной выборки двухградационного сигнала (см. с. 2) в элементах поля, имеющих координаты
,
где Δ х, Δ у - интервалы дискретизации поля по осям х и у. По результатам проверки bj считают контурной точкой, если хотя бы одна точка из соседних не принадлежит изображению.

Полученное путем перебора всех точек изображения множество контурных точек упорядочивают, образуя список типа Л2 по принципу соседних точек (см. Кушниренко А. Г., Лебедев Г.В. Программирование для математиков. - М.: Наука, 1988, с. 101). Одновременно убеждаются в замкнутости границы, т.е. в наличии соседства последнего и первого элементов списка. Далее осуществляют поиск точек выпуклой части контура объекта. С этой целью при последовательном обходе контура для каждых двух соседних точек находят уравнение прямой (см. Бронштейн И. Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов. - М.: Наука, 1986, с. 199). В соответствии с условием выпуклости (см. с. 5) отбраковывают точки невыпуклой части контура, а точки выпуклой заносят в виде координат в упорядоченный список В_в. В полученном списке перебором пар точек осуществляют поиск наиболее разнесенных с номерами κ и ν и находят предполагаемый центр контура (х_о, у_о) с координатами, вычисляемыми в виде полусумм координат наиболее разнесенных точек. Находят R _κν по соотношению R_κν= . Проверяют принадлежность элементов списка В_в области в виде ограниченного круга с R _κν по условию
∀ kP {(X_к-X_o)²+ (Y_к-Y_o)²≅ R ,
(1) где к - номер элемента списка. При принадлежности всех элементов списка кругу с радиусом R _κν точку с координатами X_o= , Y_o= принимают за центр контура. Выбирают радиус фиксирующей окружности из условия R ≥ R _κν . Окружность рисуют из найденного центра контура, например, на экране дисплея, используя известные программы Graphic BASIC или AutoCAD (см., например, Пярнпуу А.А. Программирование на современных алгоритмических языках. - M.: Наука, 1990). На экран дисплея также выводятся элементы списка В_в. Далее на основе указанных программ находят гомотетию от выпуклого контура. Для этого каждому элементу списка В_всопоставляют элемент (х^г, у^г) списка В_в^г, вычисляемый по соотношениям
х^г = 2х_о - х_к; у^г = 2у_о - у_к. (2)
Используя полученные элементы списка В_в^г как координаты центров кругов радиуса R, на экране дисплея находят область погрешностей представления (фиксации) контура изображения объекта контуром окружности радиуса R. Область находится как пересечение кругов радиуса R. При необходимости поиск области погрешностей может осуществляться аналитическим путем перебора элементов рецепторного поля и выделения из них элементов, удовлетворяющих известному условию пересечения областей.

Если неравенство (1) не выполняется, то для точек, лежащих вне области круга с R, находят радиусы и координаты центров окружностей (х_оп = 0, у_оп*, R_оп), проходящих через две исходные точки (например, (x _κ , y _κ ), (x _ν , y _ν )) и одну из выделенных точек (х_m*, y_m*). Значения определяют по соотношениям, полученным после преобразования системы координат
Y*о

После вычислений (3) по известным соотношениям для поворота системы координат (см. Бронштейн И.Н. и др., с. 196) определяют положения найденных центров кругов в исходной системе координат. Далее для каждого из полученных кругов проверяется принадлежность всех элементов списка В_в^г области круга. Среди кругов, обеспечивающих включение всех элементов В_в^г, выбирается наименьший. Центр этого круга является центром круга изображения объекта, а радиус - радиусом окружности полной фиксации изображения объекта.

Если такой круг не найден, то, перебирая пары элементов списка В_в^г, находят такую пару, что расстояние между ними меньше 2R _κν , но больше, чем для остальных пар. Для найденной пары точек поиск центра контура и радиуса окружности полной фиксации повторяют как для случая, когда не все элементы списка В_в^г принадлежат кругу с радиусомR _κν .

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

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

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

Изобретение относится к технике обработки изображений и может применятся в технологических процессах, при автоматизации проектирования, для анализа ландшафтных рисунков, в робототехнике, прикладном телевидении. Целью изобретения являются унификация представления контуров изображения объектов и уменьшение зависимости положения центра контура и погрешностей представления контура от положения точек контура изображения объекта. Это достигается за счет представления контура окружностью с определением по предложенным правилам положения центра фиксации контура и погрешностей представления в зависимости от радиуса фиксирующей окружности и положения точек контура. 10 ил.

СПОСОБ ФИКСАЦИИ ИЗОБРАЖЕНИЯ ОБЪЕКТА, в котором выделяют контур, ограничивающий связную плоскую область изображения объекта, используют в качестве стандартного контура изображения окружности выбранного радиуса R, центр которой совмещают с центром контура изображения объекта, отличающийся тем, что за центр контура изображения объекта принимают середину отрезка, соединяющего две наиболее разнесенные вершины выпуклой фигуры контура изображения объекта, если при возможных соединениях концов этого отрезка с другими вершинами выпуклой фигуры контура изображения объекта не образуется остроугольный треугольник, а в остальных случаях за центр контура изображения объекта принимают точку пересечения перпендикуляров к серединам сторон одного из остроугольных треугольников, имеющих в качестве вершин вершины выпуклой фигуры контура, и такого, что описанная вокруг него окружность имеет наименьший радиус среди описанных вокруг остроугольных треугольников окружностей, ограничивающих область, содержащую все точки контура изображения объекта, находят область погрешностей фиксации как пересечение окружностей с радиусом R и центрами, расположенными в вершинах фигуры, гомотетичной к выпуклой фигуре контура изображения объекта, с коэффициентом преобразования -1 и центром преобразования, совпадающим с центром контура при его совмещении с центром окружности радиуса R, причем R берут не менее наименьшего значения, обеспечивающего включение в круг с радиусом R всех точек контура объекта.