Поиск объектов на изображениях с помощью графов
Данная работа посвящена проблеме поиска объектов на изображении. Для её решения предлагается использовать метод на основе применения графа, описывающего изображение. Данный граф должен обладать тем свойством, что отдельным объектам на изображении должны соответствовать его подграфы. Тогда задача пои...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2012 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2012
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/57697 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поиск объектов на изображениях с помощью графов / А.В. Агарков // Штучний інтелект. — 2012. — № 4. — С. 105-119. — Бібліогр.: 11 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860268255404359680 |
|---|---|
| author | Агарков, А.В. |
| author_facet | Агарков, А.В. |
| citation_txt | Поиск объектов на изображениях с помощью графов / А.В. Агарков // Штучний інтелект. — 2012. — № 4. — С. 105-119. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Данная работа посвящена проблеме поиска объектов на изображении. Для её решения предлагается использовать метод на основе применения графа, описывающего изображение. Данный граф должен обладать тем свойством, что отдельным объектам на изображении должны соответствовать его подграфы. Тогда задача поиска объекта сводится к выделению соответствующего подграфа. Для описания изображения предлагается использовать граф, построенный на основе использования структурных элементов, выделенных с помощью мультимасштабного представления. Данный граф позволяет отражать структуру как текстурированных, так и нетекстурированных объектов. Для выделения подграфов, соответствующих искомым объектам, используются средства, основанные на построении дополнительного графа-пирамиды. Экспериментальная проверка использования данного графа и средств его обработки для поиска текстурированных и слабо текстурированных объектов показала их высокую эффективность. Сравнение с аналогами показало значительное превосходство предложенных средств при поиске слабо текстурированных объектов.
Дана робота присвячена проблемі пошуку об’єктів на зображенні. Для її вирішення пропонується використовувати метод на основі вживання графа, що описує зображення. Даний граф повинен володіти тією власти- вістю, що окремим об’єктам на зображенні повинні відповідати його підграфи. Тоді задача пошуку об’єкта
зводиться до виділення відповідного підграфа. Для опису зображення пропонується використовувати граф, побудований на основі використання структурних елементів, виділених за допомогою мультимасштабного представлення. Даний граф дозволяє відображати структуру як текстурованих, так і нетекстурованих об’єктів. Для виділення підграфів, відповідних шуканим об’єктам, використовуються засоби, засновані на побудові додаткового графа-піраміди. Експериментальна перевірка використання даного графа і засобів його обробки для пошуку текстурованих і слабо текстурованих об’єктів показала їх високу ефективність. Порівняння з аналогами показало значну перевагу запропонованих засобів при пошуку слабо текстурованих об’єктів.
This work is devoted to object search in images. To solve this problem, the method based on the use of a graph that describes the image is applied. The given graph should have such property that the individual objects in the image must comply with its subgraphs. In such case, the task of object search is limited to allocation of corresponding subgraph. To describe the images, it is suggested to use a graph constructed on the basis of the structural elements, which are identified with the help of multi-scale representation. This graph can reflect the structure of both textured and non-textured objects. To separate subgraphs, which correspond to the desired objects, the tools based on the construction of additional graph pyramid are used. Experimental verification of a given graph, and means of processing to search for textured and weakly textured objects demonstrated their high efficiency. Comparison to analogues showed significant superiority of the proposed means at searching poorly textured objects.
|
| first_indexed | 2025-12-07T19:03:42Z |
| format | Article |
| fulltext |
«Штучний інтелект» 4’2012 105
3А
УДК 004.931, 519.174
А.В. Агарков
Институт проблем искусственного интеллекта
МОН Украины и НАН Украины, г. Донецк
Украина, 83048, г. Донецк, ул. Артема, 118-б
Поиск объектов на изображениях с помощью графов
A.V. Agarkov
Institute of Artificial Intelligence
MES of Ukraine and NAS of Ukraine, c. Donetsk
Ukraine, 83048, c. Donetsk, Artema st., 118-b
Object Searching in Images by Graph Using
A.B. Агарков
Інститут проблем штучного інтелекту
МОН України і НАН України, м. Донецьк
Україна, 83048, м. Донецьк, вул. Артема 118-б
Пошук об’єктів на зображеннях за допомогою графів
Данная работа посвящена проблеме поиска объектов на изображении. Для её решения предлагается
использовать метод на основе применения графа, описывающего изображение. Данный граф должен
обладать тем свойством, что отдельным объектам на изображении должны соответствовать его
подграфы. Тогда задача поиска объекта сводится к выделению соответствующего подграфа. Для
описания изображения предлагается использовать граф, построенный на основе использования
структурных элементов, выделенных с помощью мультимасштабного представления. Данный граф
позволяет отражать структуру как текстурированных, так и нетекстурированных объектов. Для выделения
подграфов, соответствующих искомым объектам, используются средства, основанные на построении
дополнительного графа-пирамиды. Экспериментальная проверка использования данного графа и
средств его обработки для поиска текстурированных и слабо текстурированных объектов показала их
высокую эффективность. Сравнение с аналогами показало значительное превосходство предложенных
средств при поиске слабо текстурированных объектов.
Ключевые слова: поиск объектов, распознавание изображений, сравнение графов.
This work is devoted to object search in images. To solve this problem, the method based on the use of a graph that
describes the image is applied. The given graph should have such property that the individual objects in the image
must comply with its subgraphs. In such case, the task of object search is limited to allocation of corresponding
subgraph. To describe the images, it is suggested to use a graph constructed on the basis of the structural elements,
which are identified with the help of multi-scale representation. This graph can reflect the structure of both textured
and non-textured objects. To separate subgraphs, which correspond to the desired objects, the tools based on the
construction of additional graph pyramid are used. Experimental verification of a given graph, and means of
processing to search for textured and weakly textured objects demonstrated their high efficiency. Comparison to
analogues showed significant superiority of the proposed means at searching poorly textured objects.
Key Words: object search, image recognition, graph comparison.
Дана робота присвячена проблемі пошуку об’єктів на зображенні. Для її вирішення пропонується використо-
вувати метод на основі вживання графа, що описує зображення. Даний граф повинен володіти тією власти-
вістю, що окремим об’єктам на зображенні повинні відповідати його підграфи. Тоді задача пошуку об’єкта
зводиться до виділення відповідного підграфа. Для опису зображення пропонується використовувати граф,
побудований на основі використання структурних елементів, виділених за допомогою мультимасштабного
представлення. Даний граф дозволяє відображати структуру як текстурованих, так і нетекстурованих об’єктів.
Для виділення підграфів, відповідних шуканим об’єктам, використовуються засоби, засновані на побудові
додаткового графа-піраміди. Експериментальна перевірка використання даного графа і засобів його обробки
для пошуку текстурованих і слабо текстурованих об’єктів показала їх високу ефективність. Порівняння з
аналогами показало значну перевагу запропонованих засобів при пошуку слабо текстурованих об’єктів.
Ключові слова: пошук об’єктів, розпізнавання зображень, порівняння графів.
Агарков А.В.
«Искусственный интеллект» 4’2012106
3А
Введение
В последнее время для поиска / распознавания произвольных объектов на
изображениях всё чаще применяются методы, использующие локальные инвариантные
черты (local invariant features) изображений. Данные черты довольно стабильно выде-
ляются на изображениях даже при смене освещения, масштаба и ракурса. Это позволяет
использовать их для описания и поиска / распознавания довольно широкого класса
объектов на изображениях. Каждой характерной черте ставится в соответствие дескрип-
тор, который отражает особенности изображения в её окрестности. При проведении
поиска / распознавания на рассматриваемом изображении выделяются все локальные
инвариантные черты, затем среди них проводится поиск множества тех, которые со-
ответствуют искомому объекту. Для этого вначале для каждой черты модели прово-
дится поиск наиболее вероятных соответствий из черт рассматриваемого изображения
путём сравнения соответствующих дескрипторов. Чтобы отфильтровать ложные соот-
ветствия используется также метод FLANN, который учитывает и соседние черты.
После выделения наиболее вероятных соответствий для отдельных черт модели
проводится поиск соответствия их множеству среди множества черт рассматриваемого
изображения. Наиболее распространенными методами для поиска соответствующего
объекту множества локальных черт в настоящее время являются RANSAC [1] и обоб-
щённое преобразование Хафа.
Данная схема в настоящее время широко и успешно используется с различными
вариациями – применяются различные детекторы локальных черт, различные дескрип-
торы и способы их сравнения [2-4]. Однако следует заметить, что данный метод / схема
может успешно применяться только для поиска / распознавания объекта по имеющемуся
шаблону и искомый объект должен быть достаточно текстурирован (т.е. иметь вну-
треннюю структуру). Это связано с особенностями применяемых дескрипторов и мето-
дов поиска соответствующих множеств черт. Поскольку при поиске соответствующих
подмножеств локальных черт используется их взаимное расположение, то логично для
их описания использовать граф. Вершинам данного графа-описания соответствуют
структурные элементы (локальные черты), а ребра отражают отношения между ними.
Отдельным объектам на изображении соответствуют подграфы графа-описания.
Таким образом, задача поиска определённого объекта сводится к поиску соответствую-
щего подграфа, который осуществляется путем сравнения графа-эталона с графом-
описанием изображения.
Данный подход был использован в работах [5], [6], где в качестве структурных
элементов использовались границы. Использование в качестве структурных элементов
границ приносит определённые трудности, связанные с влиянием изменений яркости
и контрастности на результат их выделения. Гораздо предпочтительней для этого
локальные инвариантные черты, хотя их недостатки, упомянутые выше, несколько
ограничивают область их применения.
В данной работе предлагается усовершенствование данного метода за счёт исполь-
зования новых графов и средств их сравнения. В качестве графа для сравнения исполь-
зуется клика, построенная на основе графа-описания, предложенного в [7-9]. Исполь-
зование данного графа-описания в совокупности со сравнением графов, основанным
на построении дополнительного графа-пирамиды [10], [11], позволяет проводить
поиск / распознавание объектов на изображениях без использования сложных дескрип-
торов. Также предложенное усовершенствование позволяет проводить поиск одинаковых
объектов на различных изображениях без наличия априорной информации о них.
Целью данной работы является проверка эффективности применения графа-
описания и средств его обработки, предложенных в работах [7-11], для решения
задач распознавания зрительных образов. Для этого необходимо:
Поиск объектов на изображениях с помощью графов
«Штучний інтелект» 4’2012 107
3А
1. Разработать алгоритм на основе их применения для поиска текстурированных
и нетекстурированных объектов на изображениях;
2. Провести проверку эффективности работы данного алгоритма, сравнить эффек-
тивность работы данного алгоритма с аналогами.
Граф-описание изображения
Выделение структурных элементов для построения графа-описания описано в
работах [7-9] и является развитием метода выявления структуры изображений, основан-
ного на применении мультимасштабных представлений, получаемых на основе свёрток
с функцией Гаусса и её производными. Данные структурные элементы, называемые
далее инвариантными, так же как и инвариантные локальные черты, выделяются с по-
мощью мультимасштабного представления, построенного с помощью оператора DoG.
Инвариантные структурные элементы (ИСЭ) выделяются на основе использова-
ния экстремумов по направлению во всех плоскостях мультимасштабного представления
рассматриваемого изображения. Следует отметить, что множество локальных инва-
риантных черт является подмножеством множества ИСЭ. Это связано с тем, что
локальные экстремумы, которым соответствуют локальные инвариантные черты, явля-
ются подмножеством экстремумов по направлению, используемых для выделения
инвариантных структурных элементов. И, так же как и локальные черты, ИСЭ харак-
теризуются координатами центра, характерными масштабом и яркостью.
Таким образом, в качестве графа, описывающего изображение , используется
граф ( , )I I IG V E , где IV и IE – множества вершин и рёбер соответственно. Каждой
вершине I
i Iv V взаимно однозначно соответствует структурный элемент, который
характеризуется координатами центра ( ) ( , )I
ir v x y
, характерным масштабом ( )I
iS v ,
характерной яркостью ( )I
iG v , контрастностью ( )I
iDoG v . Параметры, характеризующие
структурный элемент, составляют атрибут соответствующей вершины. Каждое ребро
( , )I I I
ij i j Ie e v v E характеризует взаимное расположение структурных элементов, отве-
чающих вершинам. Атрибутом ребра являются расстояние между центрами соответст-
вующих структурных элементов и отношения их характерных масштабов, яркостей и
контрастностей:
( ) ( ) / ( )I I I
ij i jRS e S v S v ,
( ) ( ) / ( )I I I
ij i jRG e G v G v ,
( ) ( ) / ( )I I I
ij i jRDoG e DoG v DoG v ,
( )* ( )
( )
( )* ( )
I I
j iI
ij I I
j i
G v DoG v
RGDoG e
DoG v G v
.
Для ускорения сравнения изображений целесообразно использовать не все
инвариантные структурные элементы, а только часть. То есть необходимо выбрать
репрезентативные вершины, которые будут участвовать в сравнении графов-опи-
саний и которые образуют репрезентативный граф. Данный граф удобнее всего делать
кликой, чтобы отсутствие каких-либо вершин не влияло на результат поиска соответ-
ствующих подграфов.
Таким образом, алгоритм поиска одинаковых объектов на изображениях имеет вид:
1. Построение графов-описаний сравниваемых изображений.
2. Отбор репрезентативных вершин для построения графов-клик, которые будут
сопоставляться.
Агарков А.В.
«Искусственный интеллект» 4’2012108
3А
3. Построение производного графа.
4. Поиск в производном графе множества максимальных клик
5. Формирование решения из найденных клик.
Если в качестве одного из сравниваемых изображений будет изображение объекта,
то данный алгоритм будет применим для поиска определённого объекта на изображении.
Репрезентативный граф
Чаще всего в качестве репрезентативных вершин достаточно выбрать те, кото-
рым соответствуют ИСЭ, совпадающие с локальными инвариантными чертами. Каждой
репрезентативной вершине R
iv ставится в соответствие множество ИСЭ ( )R
ib v , которые
расположены в окрестности соответствующей ЛИЧ и характеризуют структуру
изображения в данной окрестности.
( ) : ( , ) ( )* , ( , )R R R R
i j I i j i i jb v v V r v v S v k C v v
( , )R
i jC v v – цепь между вершинами R
iv и jv ( , ) , : ( ), ( ) 1R R
i j iC v v v e v b v m e ,
где ( ) 1m e означает, что соседние структурные элементы соответствующие
вершинам, инцидентные ребру e , относятся к одной детали изображения и их центры
являются соседними пикселями ([8]).
Алгоритм для формирования множества ( )R
ib v имеет вид
( )R
ib v // инициализация искомого множества ( )R
ib v пустым множеством
( )R R
i ib v v // добавление в искомое множество вершины R
iv
,
, ,
,
, , ,
( 1; ( ) ; )
{
/ / ( )
/ / ( ) ,
( 1; ( ) ; )
{
/ / ( )
/ / ( , ) ,
R
i
R R
i j i
R R
i j i j
R
i j
R R
i j l i j
R
i j
for j j N b v j
v j аявершинаиз множестваb v
n v множествовершин смежныхсv
for l l N n v l
v l аявершинаиз множестваn v
r v v расстояние между ИСЭ соотв
, , , , ,
, ,
( , ) ( )* ( ( , )) 1 ( )
{
( ) ;
}
}
}
R
i j
R R R R R R
i j i i j i j l i j l i
R R
i i j l
етствующимиv иv
if r v v S v k m e v v v b v
b v v
Выбранные для дальнейшего сравнения вершины соединяются ребрами каждое
с каждым. В качестве атрибута данных рёбер выступает расстояние между соответ-
Поиск объектов на изображениях с помощью графов
«Штучний інтелект» 4’2012 109
3А
ствующими ИСЭ – ( ( , ))i jR e v v . Фактически формируется новый граф-клика из репре-
зентативных вершин, который и используется при дальнейшем сравнении изображений.
Таким образом, при данном сравнении изображений используется только инфор-
мация, предоставляемая графом-описанием, в отличие от других, которые основаны
на использовании сложных дескрипторов.
Сравнение репрезентативных графов
Для поиска соответствующих подграфов у пары графов-описаний проводится
их сравнение, основанное на поиске их изоморфных пересечений. Для данного сравнения
предлагается использовать построение дополнительного графа-пирамиды [10], [11],
поскольку это позволяет достичь линейной зависимости вычислительной сложности
от количества решений, а также даёт возможность ускорения вычислений за счёт
учёта специфики конкретной задачи и возможность распараллеливания вычислений.
Производный граф
Поиск соответствующих подграфов начинается с построения производного графа.
Вершинам данного графа ),( PPP EVG , соответствуют пары вершин сравниваемых графов
),( 111 EVG и ),( 222 EVG , которые потенциально могут соответствовать друг другу –
)()(,,),( 21221121
jiji
P
ji vatrvatrVvVvVvv .
Ребрами в производном графе соединены те вершины, соответствующие вершины
которых также являются смежными, и параметры, характеризующие рёбра, совпадают
или достаточно похожи друг на друга.
)),(()),((,),(,),(),(),,( 22112221112121
kjlikjli
P
klji vveatrvveatrEvveEvveEvvvve .
Набор параметров, составляющих атрибуты вершин и рёбер, и то, как они сопо-
ставляются, зависит от решаемой задачи. В данном случае сравнение графов исполь-
зуется для поиска одинаковых объектов, поэтому предполагается, что значительных
искажений пропорций, отношений яркости и контрастности не происходит. Это по-
зволяет ограничиться тем набором параметров, который указывался ранее – масш-
табом, яркостью и контрастностью.
В рассматриваемом случае сравнения графов-описаний это означает, что
соответствующие им структурные элементы совпадают или достаточно друг на
друга похожи. Следует, однако, учитывать, что при изменении освещения значения,
характеризующие ИСЭ могут меняться, что приводит к росту количества вершин
производного графа.
Для оценки похожести структурных элементов, соответствующих вершинам 1
iv
и 2
lv , используются следующие соотношения:
1 2 1 2( , ) ( ) / ( )i j i jrS v v S v S v ,
1 2 1 2( , ) ( ) / ( )i j i jrG v v G v G v ,
1 2 1 2( , ) ( ) / ( )i j i jrDoG v v DoG v DoG v ,
1 2
1 2
1 2
( )* ( )
( , )
( )* ( )
j i
i j
j i
G v DoG v
rGDoG v v
DoG v G v
.
Агарков А.В.
«Искусственный интеллект» 4’2012110
3А
Вершина 1 2( , )i jv v образовывается только в случае, если удовлетворяется условие
1 2 1 2
1 2 1 2
1/ ( , ) 1/ ( , )
1/ ( , ) 1/ ( , )
i j i j
i j i j
mrS rS v v mrS mrG rG v v mrG
mrDoG rDoG v v mrDoG mrGDoG rGDoG v v mrGDoG
, (1)
где mrS , mrG , mrDoG , mrGDoG – пороги, определяющие максимальное
отношение между соответствующими параметрами атрибутов сравниваемых вершин.
В данном случае это означает, что взаимное расположение на плоскости и в про-
странстве признаков соответствующих структурных элементов совпадает. Сравнение
атрибутов рёбер предназначено для проверки схожести их взаимного пространствен-
ного и параметрического расположения.
Для сравнения их взаимного расположения в плоскости изображений исполь-
зуются следующие соотношения:
1 2 1 2 1 1 2 2( ( , ), ( , ) ) ( ( , )) / ( ( , ))i j l k i l j krR e v v v v R e v v R e v v ,
1 2 1 2 1 2
1( ( , ), ( , ) ) ( ) / ( )i j l k i jrS e v v v v S v R v ,
1 2 1 2 1 2
2 ( ( , ), ( , ) ) ( ) / ( )i j l k l krS e v v v v S v R v ,
1 2 1 2 1 2 1 2 1 2 1 2
1 2( ( , ), ( , ) ) ( ( ( , ), ( , ) ) ( ( , ), ( , ) )) / 2i j l k i j l k i j l krS e v v v v rS e v v v v rS e v v v v ,
1 2 1 2 1 2 1 2 1 2 1 2( ( , ), ( , ) ) ( ( ( , ), ( , ) ) ( ( , ), ( , ) ))i j l k i j l k i j l kdrRS e v v v v abs rR e v v v v rS e v v v v ,
1 2 1 2 1 2 1 2 1 2 1 2
1( ( , ), ( , ) ) ( ( ( , ), ( , ) ) ( ( , ), ( , ) ))i j l k i j l k i j l kdrRR e v v v v abs rR e v v v v rR e v v v v .
При сравнении взаимных яркостей пар ИСЭ используется качественная оценка.
То есть для каждой рассматриваемой пары ИСЭ учитываются только отношения
вида «больше», «меньше», «равно». Как показали проведённые исследования, учёт толь-
ко такого типа отношений позволяет добиться большего качества, чем использование
количественных отношений. Для этого используется следующая функция:
1 1
1 1 1 1
1 1
1, ( ( , ))
( ( , )) 0, ( ( , ))
1, ( ( , ))
i l
i l i l
i l
if thrG rG e v v
RG e v v if thrG rG e v v thrG
if rG e v v thrG
,
где
1 1
1 1
1 1
( ) ( )
( ( , ))
( ) ( )
i l
i l
i l
G v G v
rG e v v
G v G v
, thrG – порог, определяющий разницу в яркостях,
которым можно пренебречь, чтобы яркости считались одинаковыми.
Структурные особенности изображений слабо подвержены влиянию смены осве-
щения, что позволяет отфильтровывать ложные соответствия при значительных вариа-
циях яркости, контрастности и фона. Для того, чтобы учесть структурные особенности
изображений при их сравнении, необходимо сравнить взаимное расположение соседних
ИСЭ для каждой из сравниваемых пар.
Для сравнения структур изображений в окрестности ЛИЧ соответствующим вер-
шинам 1 2 1 2, , ,i j l kv v v v , используется следующий приём, – исходя из условия перехода дан-
ных ЛИЧ друг в друга, рассчитывается преобразование координат 2 1 2 1: ( ), ( )j i k lM v Mr v v Mr v
из одного изображения в другое, используя которое, проводится сравнение расположений
Поиск объектов на изображениях с помощью графов
«Штучний інтелект» 4’2012 111
3А
ИСЭ, соответствующих вершинам из множеств 1 2 1 2( ), ( ), ( ), ( )i j l kb v b v b v b v . Для оценки
похожести структур используется функция
1 1
1 2 1 2
( )
( , ) ( , ( ), )
m
m
v b v
C v v c v b v M
,
где
2 2 2 1
1 2
2 2 2 1
1, ( ) : ( ) ( )
( , ( ), )
0, ( ) : ( ) ( )
n n m
m
n n m
if v b v r v M r v mD
c v b v M
if v b v r v M r v mD
.
Если значения 1 2( , )i jC v v и 1 2( , )l kC v v превышают некий порог mC – 1 2( , )i jC v v mC ,
1 2( , )l kC v v mC , то структуры считаются похожими.
Ребро 1 2 1 2( , ), ( , )i j l ke v v v v образовывается только в случае соблюдения условия
1 2 1 2 1 2 1 2
1 1 2 2 1 2 1 2
( ( , ), ( , ) ) ( ( , ), ( , ) )
( ( , )) ( ( , )) ( , ) ( , )
i j l k i j l k
i l j k i j l k
drRS e v v v v mdrRS drRR e v v v v mdrRR
RG e v v RG e v v C v v mC C v v mC
. (2)
Следует отметить, что в производном графе могут существовать подмножества
вершин, каждая из которых соответствует одной вершине одного графа и различным
вершинам второго. Причём вершины второго графа соответствуют структурным эле-
ментам, сходным по параметрам и расположению. Это приводит к наличию неза-
висимых множеств в производном графе, которое приводит к экспоненциальному ко-
личеству максимальных клик. Чтобы этого избежать, достаточно попарно соединить
ребрами такие вершины, что позволяет исключить из производного графа независимые
множества, обуславливающие экспоненциальное количество максимальных клик.
Построение пирамиды
Пирамида образуется в результате построения, то есть начиная с основного /
исходного графа (нулевого уровня) проводится следующая процедура – граф, соот-
ветствующий одному уровню, разбивается на подграфы, для каждого из которых в
следующем уровне создаётся новая вершина. Эти новые вершины являются дочер-
ними для вершин соответствующих подграфов предыдущего уровня, которые, в
свою очередь, являются родителями для новозаведенных вершин.
Вид пирамиды и, соответственно, то, какие подграфы будут соответствовать
вершинам пирамиды, будет зависеть от правил её построения. Поиск пресечений
графов заключается в следующем – на одном из графов строится пирамида, а затем
на производном графе строится вторая пирамида по образу и подобию первой.
В соответствии с такими правилами построения вершинам второй пирамиды будут
соответствовать пересечения рассматриваемых графов.
Однако в случае графов, описывающих изображения, можно ограничиться по-
строением одной пирамиды. Действительно, если графы 1G и 1G являются кликами,
то их пересечения также являются кликами. Поэтому для их поиска достаточно найти
все максимальные клики в производном графе. Для этого необходимо построить
граф-пирамиду для поиска множества максимальных клик.
Для того чтобы вершинам пирамиды соответствовали клики, необходимо, чтобы
подграфы разбиения являлись кликами, а новые вершины пирамиды соединялись реб-
рами только в том случае, если их объединение также является кликой. Если придержи-
ваться данных правил при построении пирамиды, то каждой её верхушке будет соответ-
Агарков А.В.
«Искусственный интеллект» 4’2012112
3А
ствовать клика. Наиболее подходящей для решения данной задачи является ребёрная
пирамида, у которой в качестве подграфов разбиения выступают пары смежных
вершин. То есть каждой вершине данной пирамиды соответствует ребро с инцидент-
ными ей вершинами.
Существует, однако, несколько дополнительных правил построения такой пира-
миды, которые позволяют избегать повторов и пропусков решений. Более подробно о по-
строении пирамиды для поиска множества максимальных клик можно посмотреть в [11].
Сокращение вычислений
Если графы 1G и 2G являются кликами, то для создания производного графа
может потребоваться значительное время. Это связано с необходимостью создания
большого числа рёбер – 221 )()( VNVNO .
Также два таких графа будут иметь большое количество пересечений, не соот-
ветствующих одинаковым объектам. Это обусловлено высоким количеством струк-
турных элементов, что приводит к большому числу их подмножеств, имеющих
сходное / похожее взаимное расположение. Следует также учесть, что структурные
элементы, относящиеся к одному объекту, находятся недалеко друг от друга. Следует
помнить также, что вычислительная сложность поиска множества клик в графе мето-
дом строительства пирамиды линейна относительно их числа и пропорциональна
кубу среднего количества их вершин.
Вышесказанное позволяет заключить, что для сокращения вычислений необхо-
димо уменьшить количество вершин в отдельных максимальных кликах. Это необхо-
димо сделать, выбросив из рассмотрения рёбра сравниваемых графов, соединяющие
вершины, которые соответствуют далеко расположенным друг от друга структурным
элементам.
Контроль взаимного расположения структурных элементов
Метод построения пирамиды позволяет использовать дополнительные проверки
для контроля свойств промежуточных результатов. Это реализуется с помощью до-
полнительных условий при создании новых вершин и рёбер пирамиды.
При сравнении графов, описывающих изображения, необходимо контролировать
взаимное расположение структурных элементов в каждой паре потенциально со-
ответствующих клик-троек.
Перед построением ребра между вершинами, объединению которых соответст-
вует клика-тройка, проводится проверка. Направление обхода по соответствующим
структурным элементам данной пары троек должно совпадать, иначе новое ребро не
образуется. Это позволяет отфильтровывать зеркально отражённые соответствия.
Также проверяются соотношения между соответствующими расстояниями между
центрами ИСЭ. Данные отношения не должны сильно отличаться, что позволяет
отфильтровывать геометрически искаженные соответствия.
Формирование решения
После построения пирамиды её вершинам, не имеющим дочерних, будут соответ-
ствовать максимальные клики производного графа { }P
iq [11]. Данным кликам отвечают
Поиск объектов на изображениях с помощью графов
«Штучний інтелект» 4’2012 113
3А
пересечения – пары соответствующих подграфов, принадлежащих рассматриваемым
графам-описаниям 1G и 2G . Вообще говоря, данные графы не изоморфны, а гомо-
морфны. Это связано с тем, что в найденных кликах могут быть вершины, соответ-
ствующие одной вершине одного графа и нескольким различным вершинам другого,
что обусловлено их попарной смежностью. Не смотря на это, данным подграфам соответ-
ствуют группы структурных элементов, взаимное расположение которых совпадает с оп-
ределённой точностью.
Вследствие того, что при сравнении графов были исключены рёбра, соединяющие
вершины, которым соответствуют структурные элементы, расположенные далеко
друг от друга, найденные пересечения не являются максимальными. Для того, чтобы
найти максимальные пересечения, необходимо объединить найденные клики производ-
ного графа в подграфы, которым отвечают соответствующие клики графов 1G и 2G .
Это можно сделать рядом способов, каждый из которых лучше подходит к раз-
личным случаям. Если необходимо получить как можно более точно решение – т.е.
чтобы взаимное расположение соответствующих друг другу структурных элементов
полностью совпадало, необходимо провести следующую процедуру. На основе анализа
уже известных пересечений удалить из производного графа вершины, которые не
соответствуют искомым решениям. Затем дополнить производный граф рёбрами,
которые соответствуют далеко удаленным друг от друга парам структурных объектов.
После этого построить новый граф NG , каждой вершине которого отвечает найденная
пара соответствующих подграфов, т.е. одна из максимальных клик производного
графа: ( )N P
i iv v q . Ребрами соединить только те вершины, которым соответствуют
подграфы производного графа, объединение которых является кликой. После чего
производится поиск множества максимальных клик в данном графе NG . Согласно
заданным критериям из найденного множества выделяются те клики, которые соответ-
ствуют искомым решениям.
Однако если учитывать, что вследствие различного рода искажений взаимное
расположение некоторых структурных элементов может меняться, то условие создания
рёбер в графе NG необходимо ослабить. Например, потребовать, чтобы количество
несопряженных пар в объединённом подграфе было не более опредёленного порога.
А после создания всех рёбер графа NG действовать так же, как и в первом случае.
Следует, однако, отметить, что создание новых рёбер и проверка каждой пары
клик в производном графе требует дополнительного времени. Уменьшить временные
затраты позволяет использование того свойства соответствующих графов, что взаимное
расположение их структурных элементов совпадают (или достаточно близко). Это
означает, что координаты структурных элементов рассматриваемой пары изображений
связаны друг с другом опредёленным преобразованием ( )P
iM q . Для двух пар соот-
ветствующих множеств структурных элементов, относящихся к одному объекту,
данное преобразование координат будет с определённой точностью совпадать:
( , ) ( ) ( )N N P P
i j i je v v M q M q .
В данном случае преобразование ( )P
iM q находилось с помощью метода наи-
меньших квадратов из условия отсутствия аффинных искажений, т.е. преобразование
подразумевает только трансляцию, поворот и масштабирование. Сравнение преоб-
разований ( )P
iM q и ( )P
jM q сводится, таким образом, к сопоставлению трансляций
Агарков А.В.
«Искусственный интеллект» 4’2012114
3А
( )t M
, углов поворота ( )M и масштабных коэффициентов ( )c M . Для их сравнения
использовались следующие величины:
( , ) ( ( )) ( ( ))P P P P
i j i jdt q q t M q t M q
,
( , ) ( ( )) ( ( ))P P P P
i j i jd q q M q M q ,
max( ( ( )), ( ( )))
( , )
min( ( ( )), ( ( )))
P P
i jP P
i j P P
i j
c M q c M q
rc q q
c M q c M q
.
Преобразования ( )P
iM q и ( )P
jM q считаются совпадающими, если соблюдается
условие
( , ) ( , ) ( , )P P P P P P
i j i j i jdt q q mdt d q q md rc q q mrc . (3)
Таким образом, каждой найденной максимальной клике производного графа
вычисляется и ставится в соответствие преобразование координат. Если пара таких
клик имеет совпадающее преобразование, то вершины графа NG соединяются ребром.
Для ускорения построения ребер в графе NG данный процесс проводится в не-
сколько этапов – вначале рассматриваются клики, имеющие общие вершины; затем
выделяются связные подграфы в NG ; затем рассматриваются пропущенные пары,
принадлежащие одному связному подграфу. Данный приём позволяет значительно
сократить время, по сравнению с полным перебором всех пар найденных максимальных
клик (всех пар вершин графа NG ).
Если объект на одном изображении довольно значительно искажен по сравнению
со вторым изображением, то преобразования координат будут совпадать только у
максимальных клик производного графа, имеющих общие вершины. В этом случае
целесообразно остановится на этапе выделения связных подграфов и рассматривать
соответствующие им подграфы производного графа как возможные кандидаты решения.
Искомые решения выбираются из найденных кандидатов согласно заданным крите-
риям, зависящим от конкретной задачи.
Эксперимент
Для проверки эффективности использования предложенных графов и средств
их обработки (далее ГиС) были выбраны задачи поиска объекта на изображении и
поиска одинаковых объектов на различных изображениях.
Для проверки работоспособности представленного алгоритма на основе использо-
вания ГиС вначале поиск объекта проводился на искусственно сформированных изо-
бражениях. Данные изображения формировались следующим образом – на произ-
вольное изображение, которое служит фоном, накладывалось изображение объекта,
изменённое в размерах и повёрнутое на произвольный / лучайный угол. Место
расположения изображения объекта на фоне также выбиралось случайным образом.
Были использованы два типа объектов – текстурированные и слабо текстурированные.
В качестве вторых были использованы символы, использующиеся в автомобильных
номерных знаках. На рис. 1 представлены изображения объектов, которые были исполь-
зованы в экспериментах. На рис. 2 представлены изображения, которые применялись
в качестве фона.
Поиск объектов на изображениях с помощью графов
«Штучний інтелект» 4’2012 115
3А
а
b
Рисунок 1 – Изображения объектов – a – текстурированные объекты,
b – слаботекстурированные объекты
Рисунок 2 – Изображения фона
Граф, представляющий изображение объекта, является кликой, вершинам кото-
рой соответствуют ЛИЧ. Граф изображения фон + объект состоит из пересе-
кающихся клик, вершины которых соответствуют ЛИЧ, расположенных друг отно-
сительно друга на расстоянии не больше, чем ( ) ( ) 5I I
i jS v S v . Каждой ЛИЧ общих
графов ставится в соответствие множество ИСЭ, характеризующих структуру в её
окрестности и отстоящих от её центра на расстояние не более чем ( ) 2,5I
iS v .
При построении вершин производного графа учитываются яркость, контраст-
ность и отношения яркости и контрастности.
В условии (1) для образования вершин производного графа были использованы
параметры 2, 1,5, 1, 2, 1, 2mrS mrG mrDoG mrGDoG . В условии (2) для образо-
вания рёбер производного графа – 0, 2, 0, 2, 0,5mdrRS mdrRR mC . В условии (3)
для образования рёбер в графе NG – 1,3, 0,07, 0,05mdt md mrc . Такой набор
параметров позволяет сократить размеры производного графа и, соответственно,
сократить время поиска до 1сек. Было протестировано 1000 изображений, образованных
текстурированными объектами. Доля верно обнаруженных объектов составила 97%.
Агарков А.В.
«Искусственный интеллект» 4’2012116
3А
Этот же набор параметров был использован в задачах поиска объекта на
изображениях реальной видеопоследовательности и поиска одинаковых объектов на
различных изображениях. Поиск одинаковых объектов осуществлялся на искусственно
сформированных изображениях. Для каждой из этих задач также было протести-
ровано по 1000 изображений.
Результаты тестов представлены в табл. 1. Из данной таблицы видно, что эф-
фективность предложенных средств на реальных изображениях не сильно падает по
сравнению с искусственными и остаётся на достаточно высоком уровне. Это показывает,
что результаты тестов на искусственных изображениях позволяют оценивать эффектив-
ность предложенных средств при их использования для реальных изображений.
Таблица 1 – Результаты тестирования на различных задачах
Задача Доля верного обнаружения объекта
Поиск объекта на искусственно
сформированных изображениях
97%
Поиск объекта на изображениях реального
видеоряда
95%
Поиск одинаковых объектов на различных
изображениях без наличия априорной
информации о них
95%
На рис. 3 представлены примеры поиска объекта на искусственном (3a), реаль-
ном (3b) изображениях и поиска одинаковых объектов на различных изображениях (3с).
Также было проведено сравнение предложенных средств с аналогами, предназ-
наченными для поиска объектов на изображениях. В качестве аналогов были исполь-
зованы схемы SIFT+FLANN+RANSAC и SURF+FLANN+RANSAC, которые нашли
широкое применение при решении задач распознавания изображений и поиска объек-
тов. Данные схемы были реализованы с помощью библиотеки OpenCV.
В этом тесте фактор времени (скорости получения результатов) не учитывался,
чтобы получить как можно более высокий результат как для аналогов, так и для
предложенных средств. В условии (1) для образования вершин производного графа
были использованы параметры , 2, 2, 2mrS mrG mrDoG mrGDoG . В условии
(2) для образования рёбер производного графа – 0, 2, 0, 2, 0,5mdrRS mdrRR mC .
В условии (3) для образования рёбер в графе NG – 1,3, 0,07, 0,05mdt md mrc .
Было протестировано 3000 изображений. Результаты тестов применения рас-
сматриваемых схем для решения различных задач представлены в табл. 2. Из данной
таблицы видно, что доля верно найденных / обнаруженных текстурированных объектов
для сравниваемых схем / технологий / механизмов практически не отличается. Для
предложенных средств доля изображений, на которых объект был обнаружен верно,
составила 99,5% для текстурированных объектов и 98,4% – для слабо текстурированных.
Однако для слабо текстурированных объектов контрольные схемы / технологии /
механизмы показывают долю верных обнаружений менее 50%, что говорит об их
неприменимости в подобных случаях.
Также следует отметить, что метод RANSAC невозможно применять для поиска
одинаковых объектов на различных изображениях, поскольку он предназначен для
поиска объекта по известному шаблону. Это отражено в табл. 2 прочерками в со-
ответствующих ячейках.
Поиск объектов на изображениях с помощью графов
«Штучний інтелект» 4’2012 117
3А
a b
с
Рисунок 3 – Примеры поиска объекта – a – на искусственном изображении,
b – на реальном изображении, c – одинаковых объектов на различных изображениях
Выводы
Применение представленных графов (репрезентативный граф и граф-описание)
и средств их обработки позволяет эффективно проводить поиск текстурированных и
слабо текстурированных объектов на изображениях, в отличие от других методов и
алгоритмов, которые специализируются на объектах одного типа. При этом исполь-
зуются только данные, предоставляемые графом-описанием, без использования дополни-
тельных дескрипторов. Это показывает высокую перспективность использования пред-
ложенных средств формирования и обработки описаний изображений с помощью
графов для решения задач распознавания зрительных образов.
Таблица 2 – Результаты сравнительных тестов – доля правильно найденных
объектов в зависимости от типа объекта, задачи и используемых средств
Поиск объекта на искусственно
сформированных изображениях
Поиск одинаковых объектов на
различных изображениях без наличия
априорной информации о них
Текстурирован-
ные объекты
Нетекстуриро-
ванные объекты
Текстурирован-
ные объекты
Нетексту-
рированные объекты
SIFT+FLANN
+RANSAC 99% 44,1% - -
SURF+FLANN
+RANSAC 99% 46,3% - -
ГиС 99,5% 98,4% 99% 97%
Их применение также даёт возможность увеличивать скорость работы за счет
распараллеливания вычислений, которое легко осуществимо вследствие особенностей
структуры используемых алгоритмов.
Агарков А.В.
«Искусственный интеллект» 4’2012118
3А
Дальнейшие исследования в области применения представленных графов и средств
их обработки будут направлены на увеличение скорости вычислений и расширение
круга решаемых задач. Увеличение скорости работы возможно за счет распарал-
леливания вычислений, которое легко осуществимо вследствие особенностей структуры
используемых алгоритмов.
Учет структуры изображения в окрестности структурных элементов, которые
соответствуют репрезентативным вершинам, позволит лучше отфильтровывать ложные
гипотезы при построении производного графа. Это позволит сократить его размеры,
что уменьшит время получения решения. Исследования в этой области также позволит
более оптимально для решаемых задач выбирать вершины для репрезентативного гра-
фа, что позволит добиться стабильно высокой эффективности для всех типов объектов.
Литература
1. Martin A. Fischler. Random Sample Consensus: A Paradigm for Model Fitting with Apphcatlons to
Image Analysis and Automated Cartography / Martin A. Fischler, Robert C. Bolles // Communications
of the ACM. - June 1981. – Vol. 24, № 6. – P. 381-395
2. Krystian Mikolajczyk. A performance evaluation of local descriptors / Krystian Mikolajczyk, Cordelia Schmid //
IEEE Transactions on Pattern Analysis & Machine Intelligence. – 2005. – Vol. 27, № 10. – P. 1615-1630.
3. Yan Ke. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors / Yan Ke, Rahul
Sukthankar // IEEE Computer Society Conference on Computer Vision and Pattern Recognition. –
2004. – V. 2. – P. 506-513.
4. Fred Rothganger. 3D Object Modeling and Recognition Using Local Affine-Invariant Image Descriptors
and Multi-View Spatial Constraints / Fred Rothganger, Svetlana Lazebnik, Cordelia Schmid //
International Journal of Computer Vision archive. – Vol. 66. – P. 231-259.
5. Benoit Huet. Shape retrieval by inexact graph matching / Benoit Huet, Andrew D.J. Cross, Edwin R.
Hancock // International Conference on Multimedia Computing and Systems. – 1999. – Vol. 1. – P. 772-776.
6. Radu Horaud. Stereo Correspondence Through Feature Grouping and Maximal Cliques / Radu Horaud,
Thomas Skordas // IEEE Transactions on pattern analysis and machine intelligence. – 1989. – Vol. 11,
№ 11. – P. 1168-1180
7. Агарков A.В. Iєрархiчне представлення зображень для застосування при вирiшеннi широкого
кола проблем / А.В. Агарков // Оброблення сигналiв i зображень та розпiзнавання образiв :
Восьма всеукраїнська мiжнародна конференцiя. - Київ, 2006. – С. 119-122.
8. Агарков А.В. Структурное описание изображений в виде графа для решения задач
распознавания / А.В. Агарков // Бионика интеллекта. – 2009. – № 1(70). – С. 95-101.
9. Andrej Agarkov. Novel Structural Elements for Image Descriptor / Andrej Agarkov // International
Workshop on Intelligent Information Systems. – Institute of Mathematics and Computer Science. –
September 13 – 14, 2011. – P. 97-100
10. Агарков А.В. Метод сравнения двух графов за полиномиальное время / А.В. Агарков //
Искусственный интеллект. – 2003. – № 4. – С.172-184.
11. Агарков А.В. Поиск множества максимальных клик на основе метода построения дополнительного
графа / А.В. Агарков // Искусственный интеллект. – 2011. – № 3. – С .190-199.
Literatura
1. Martin A. Fischler, Robert C. Bolles, Random Sample Consensus: A Paradigm for Model Fitting with
Apphcatlons to Image Analysis and Automated Cartography // Communications of the ACM, - June
1981. – vol. 24, № 6. - P. 381-395
2. Krystian Mikolajczyk and Cordelia Schmid, A performance evaluation of local descriptors // IEEE
Transactions on Pattern Analysis & Machine Intelligence. - 2005. – Vol. 27, № 10. – P.1615–1630.
3. Yan Ke, Rahul Sukthankar. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors // IEEE
Computer Society Conference on Computer Vision and Pattern Recognition. 2004. Vol.2. – P.506-513.
4. Fred Rothganger, Svetlana Lazebnik, Cordelia Schmid, 3D Object Modeling and Recognition Using
Local Affine-Invariant Image Descriptors and Multi-View Spatial Constraints, International Journal of
Computer Vision archive. Vol. 66. P.231 – 259.
Поиск объектов на изображениях с помощью графов
«Штучний інтелект» 4’2012 119
3А
5. Benoit Huet, Andrew D. J. Cross, Edwin R. Hancock, Shape retrieval by inexact graph matching //
International Conference on Multimedia Computing and Systems. 1999. Vol. 1. P.772-776.
6. Radu Horaud, Thomas Skordas, Stereo Correspondence Through Feature Grouping and Maximal
Cliques // IEEE Transactions on pattern analysis and machine intelligence, november 1989. vol. 11,
№11, P. 1168-1180.
7. Agarkov A.V. Obroblennja sygnaliv i zobrazhen’ ta rozpiznavannja obraziv: Vos’ma vseukrains’ka
mizhnarodna konferencija. Kyiv. 2006. S. 119-122.
8. Agarkov A.V. Bionika intellekta. 2009. №.1(70). S. 95-101.
9. Andrej Agarkov, Novel Structural Elements for Image Descriptor // International Workshop on Intelligent
Information Systems, Institute of Mathematics and Computer Science, - September 13-14, 2011. P. 97-100.
10. Agarkov A.V. Iskusstvennyj intellekt. 2003. № 4. S. 172-184.
11. Agarkov A.V. Iskusstvennyj intellekt. 2011. № 3. S. 190-199.
RESUME
A.V. Agarkov
Objects Searching on Images by Using Graphs
This work is devoted to finding objects in the image. To solve this problem are encouraged
to use a method based on the use of a graph that describes the image. This graph should have the
property that the individual objects in the image must comply with its subgraphs. Then the
problem of finding the object is reduced to an appropriate allocation of the subgraph.
To describe the images suggested to use a graph, constructed on the basis of the struc-
tural elements identified with the help of multi-scale representation. The same multi-scale
representation constructed on the basis of the convolution operator DoG, is used to find local
invariant features in images, which correspond to local extrema. But unlike them, these
structural elements are obtained by analyzing the extrema in the direction in all planes of multi-
scale representation.
This graph can reflect the structure of both textured and non-textured objects. It allows
you to build the skeleton of regions with uniform brightness, without prior segmentation of the
image.
To search for items using a graph-clique, for which the representative vertexes are
elected from of the graph-description. Using this graph instead of graph-descriptions can
reduce search time. Each vertex of the graph is associated with the set of adjacent
structural elements, which characterizes the structure of the image in its vicinity.
Selecting objects in the images is reduced to compared of the corresponding graphs. If
one image is an image of the object, it looks for a particular object. If it’s pictures of various
scenes, it looks for the same objects.
To separate subgraphs corresponding to the desired objects, tools are used, based on
the construction of additional graph pyramid. Pre-complementary graph is constructed on
the basis of the compared graphs. Cliques of the one correspond to the intersection of the
compared graphs. To select the set of maximal cliques algorithm based on the construction
of an additional graph pyramid.
Experimental verification of a given graph, and means of processing to search for textured
and weakly textured objects demonstrated their high efficiency. Comparison with analogues
showed a significant superiority of the proposed means of finding poorly textured objects.
Статья поступила в редакцию 05.06.2012.
|
| id | nasplib_isofts_kiev_ua-123456789-57697 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-12-07T19:03:42Z |
| publishDate | 2012 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Агарков, А.В. 2014-03-13T20:49:48Z 2014-03-13T20:49:48Z 2012 Поиск объектов на изображениях с помощью графов / А.В. Агарков // Штучний інтелект. — 2012. — № 4. — С. 105-119. — Бібліогр.: 11 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/57697 004.931, 519.174 Данная работа посвящена проблеме поиска объектов на изображении. Для её решения предлагается использовать метод на основе применения графа, описывающего изображение. Данный граф должен обладать тем свойством, что отдельным объектам на изображении должны соответствовать его подграфы. Тогда задача поиска объекта сводится к выделению соответствующего подграфа. Для описания изображения предлагается использовать граф, построенный на основе использования структурных элементов, выделенных с помощью мультимасштабного представления. Данный граф позволяет отражать структуру как текстурированных, так и нетекстурированных объектов. Для выделения подграфов, соответствующих искомым объектам, используются средства, основанные на построении дополнительного графа-пирамиды. Экспериментальная проверка использования данного графа и средств его обработки для поиска текстурированных и слабо текстурированных объектов показала их высокую эффективность. Сравнение с аналогами показало значительное превосходство предложенных средств при поиске слабо текстурированных объектов. Дана робота присвячена проблемі пошуку об’єктів на зображенні. Для її вирішення пропонується використовувати метод на основі вживання графа, що описує зображення. Даний граф повинен володіти тією власти- вістю, що окремим об’єктам на зображенні повинні відповідати його підграфи. Тоді задача пошуку об’єкта
 зводиться до виділення відповідного підграфа. Для опису зображення пропонується використовувати граф, побудований на основі використання структурних елементів, виділених за допомогою мультимасштабного представлення. Даний граф дозволяє відображати структуру як текстурованих, так і нетекстурованих об’єктів. Для виділення підграфів, відповідних шуканим об’єктам, використовуються засоби, засновані на побудові додаткового графа-піраміди. Експериментальна перевірка використання даного графа і засобів його обробки для пошуку текстурованих і слабо текстурованих об’єктів показала їх високу ефективність. Порівняння з аналогами показало значну перевагу запропонованих засобів при пошуку слабо текстурованих об’єктів. This work is devoted to object search in images. To solve this problem, the method based on the use of a graph that describes the image is applied. The given graph should have such property that the individual objects in the image must comply with its subgraphs. In such case, the task of object search is limited to allocation of corresponding subgraph. To describe the images, it is suggested to use a graph constructed on the basis of the structural elements, which are identified with the help of multi-scale representation. This graph can reflect the structure of both textured and non-textured objects. To separate subgraphs, which correspond to the desired objects, the tools based on the construction of additional graph pyramid are used. Experimental verification of a given graph, and means of processing to search for textured and weakly textured objects demonstrated their high efficiency. Comparison to analogues showed significant superiority of the proposed means at searching poorly textured objects. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Анализ и синтез коммуникационной информации Поиск объектов на изображениях с помощью графов Пошук об’єктів на зображеннях за допомогою графів Object Searching in Images by Graph Using Article published earlier |
| spellingShingle | Поиск объектов на изображениях с помощью графов Агарков, А.В. Анализ и синтез коммуникационной информации |
| title | Поиск объектов на изображениях с помощью графов |
| title_alt | Пошук об’єктів на зображеннях за допомогою графів Object Searching in Images by Graph Using |
| title_full | Поиск объектов на изображениях с помощью графов |
| title_fullStr | Поиск объектов на изображениях с помощью графов |
| title_full_unstemmed | Поиск объектов на изображениях с помощью графов |
| title_short | Поиск объектов на изображениях с помощью графов |
| title_sort | поиск объектов на изображениях с помощью графов |
| topic | Анализ и синтез коммуникационной информации |
| topic_facet | Анализ и синтез коммуникационной информации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/57697 |
| work_keys_str_mv | AT agarkovav poiskobʺektovnaizobraženiâhspomoŝʹûgrafov AT agarkovav pošukobêktívnazobražennâhzadopomogoûgrafív AT agarkovav objectsearchinginimagesbygraphusing |