Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій
Запропоновано удосконалений метод кусково-лінійної апроксимації контурів об’єктів у зображеннях, який дозволяє застосовувати на всіх етапах комп’ютерної обробки даних паралельні обчислення з використанням векторних операцій. В работе предложен усовершенствованный метод кусочно-линейной аппроксимации...
Gespeichert in:
| Veröffentlicht in: | Кібернетика та комп’ютерні технології |
|---|---|
| Datum: | 2020 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/173154 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій / П.Ю. Сабельніков // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 85-89. — Бібліогр.: 7 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-173154 |
|---|---|
| record_format |
dspace |
| spelling |
Сабельніков, П.Ю. 2020-11-23T19:38:32Z 2020-11-23T19:38:32Z 2020 Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій / П.Ю. Сабельніков // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 85-89. — Бібліогр.: 7 назв. — укр. 2707-4501 DOI:10.34229/2707-451X.20.3.8 https://nasplib.isofts.kiev.ua/handle/123456789/173154 004.932 Запропоновано удосконалений метод кусково-лінійної апроксимації контурів об’єктів у зображеннях, який дозволяє застосовувати на всіх етапах комп’ютерної обробки даних паралельні обчислення з використанням векторних операцій. В работе предложен усовершенствованный метод кусочно-линейной аппроксимации замкнутого контура объекта в изображении многоугольником, вершинами которого являются непосредственно точки этого контура. Критерий аппроксимации: расстояние от каждой точки аппроксимируемого участка контура до аппроксимирующего отрезка не должно превышать погрешность аппроксимации. Метод ориентирован на параллельные вычисления с использованием векторных операций. The paper proposes an improved method for piecewise linear approximation of a closed contour of an object in an image by a polygon, the vertices of which are directly the points of this contour. Approximation criterion: the distance from each point of the approximated section of the contour to the approximating segment should not exceed the approximation error. The method is focused on parallel computing using vector operations. uk Інститут кібернетики ім. В.М. Глушкова НАН України Кібернетика та комп’ютерні технології Комп'ютерні системи: теорія та застосування Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій Аппроксимация контура объекта в изображении с применением векторных операций Approximation of the Contour of an Object in an Image Using Vector Operations Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій |
| spellingShingle |
Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій Сабельніков, П.Ю. Комп'ютерні системи: теорія та застосування |
| title_short |
Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій |
| title_full |
Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій |
| title_fullStr |
Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій |
| title_full_unstemmed |
Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій |
| title_sort |
апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій |
| author |
Сабельніков, П.Ю. |
| author_facet |
Сабельніков, П.Ю. |
| topic |
Комп'ютерні системи: теорія та застосування |
| topic_facet |
Комп'ютерні системи: теорія та застосування |
| publishDate |
2020 |
| language |
Ukrainian |
| container_title |
Кібернетика та комп’ютерні технології |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Аппроксимация контура объекта в изображении с применением векторных операций Approximation of the Contour of an Object in an Image Using Vector Operations |
| description |
Запропоновано удосконалений метод кусково-лінійної апроксимації контурів об’єктів у зображеннях, який дозволяє застосовувати на всіх етапах комп’ютерної обробки даних паралельні обчислення з використанням векторних операцій.
В работе предложен усовершенствованный метод кусочно-линейной аппроксимации замкнутого контура объекта в изображении многоугольником, вершинами которого являются непосредственно точки этого контура. Критерий аппроксимации: расстояние от каждой точки аппроксимируемого участка контура до аппроксимирующего отрезка не должно превышать погрешность аппроксимации. Метод ориентирован на параллельные вычисления с использованием векторных операций.
The paper proposes an improved method for piecewise linear approximation of a closed contour of an object in an image by a polygon, the vertices of which are directly the points of this contour. Approximation criterion: the distance from each point of the approximated section of the contour to the approximating segment should not exceed the approximation error. The method is focused on parallel computing using vector operations.
|
| issn |
2707-4501 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/173154 |
| citation_txt |
Апроксимація контуру об’єкта у зображенні із застосуванням векторних операцій / П.Ю. Сабельніков // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2020. — № 3. — С. 85-89. — Бібліогр.: 7 назв. — укр. |
| work_keys_str_mv |
AT sabelʹníkovpû aproksimacíâkonturuobêktauzobraženníízzastosuvannâmvektornihoperacíi AT sabelʹníkovpû approksimaciâkonturaobʺektavizobraženiisprimeneniemvektornyhoperacii AT sabelʹníkovpû approximationofthecontourofanobjectinanimageusingvectoroperations |
| first_indexed |
2025-11-24T16:10:07Z |
| last_indexed |
2025-11-24T16:10:07Z |
| _version_ |
1850484004766089216 |
| fulltext |
КОМП’ЮТЕРНІ СИСТЕМИ: ТЕОРІЯ ТА ЗАСТОСУВАННЯ
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 85
КІБЕРНЕТИКА
та КОМП'ЮТЕРНІ
ТЕХНОЛОГІЇ
Запропоновано удосконалений метод куско-
во-лінійної апроксимації контурів об’єктів у
зображеннях, який дозволяє застосовувати
на всіх етапах комп’ютерної обробки даних
паралельні обчислення з використанням век-
торних операцій.
Ключові слова: зображення, контур об’єк-
та, кусково-лінійна апроксимація, паралельні
обчислення, векторні операції.
П.Ю. Сабельніков, 2020
УДК 004.932 DOI:10.34229/2707-451X.20.3.8
П.Ю. САБЕЛЬНІКОВ
АПРОКСИМАЦІЯ КОНТУРУ ОБ’ЄКТА
У ЗОБРАЖЕННІ ІЗ ЗАСТОСУВАННЯМ
ВЕКТОРНИХ ОПЕРАЦІЙ
Вступ. Паралельно з розвитком теоретичних основ,
методів та алгоритмічної бази обробки цифрових
зображень йде вдосконалення засобів сприйняття й
оброблення відеоданих. Тобто відбувається взаємний
вплив: з одного боку, техніка надає нові можливості
для адаптації існуючих або розробки нових методів
і алгоритмів для ефективнішого використання апарат-
них засобів, а з іншого − нові інформаційні потреби
предметних областей вказують напрямки та стиму-
люють розвиток технічних засобів.
Одним з напрямків, пов’язаних з ідентифікацією,
аналізом форми об’єктів, їх розміру, орієнтації,
маркування та інших геометричних характеристик,
є контурний аналіз [1, 2].
У літературі описано різні методи апроксимації
контурів прямими лініями. Наприклад, у [3] наведено
відомості про модифікований метод найменших квад-
ратів, а у [4] про метод Форсена. Критерій апрокси-
мації: відстань від кожної точки ділянки контуру, що
апроксимується, до апроксимувального відрізка не
повинна перевищувати похибку апроксимації. У ро-
боті [5] пропонується метод, заснований на обчислен-
ні растра для кожного початкового вузла апроксима-
ції, у межах якого знаходиться апроксимувальна лінія,
доки він не стане порожнім. Обчислення проводять
послідовно для всіх точок контуру, не повертаючись
для аналізу до попередніх точок, тому обчислювальна
складність алгоритму пропорційна кількості точок у
контурі. За похибку апроксимації обрано міжпік-
сельну відстань. Для застосовування довільної похиб-
ки апроксимації за цим методом введено додаткові
умови [6], щоб коректно прийняти рішення про кінце-
ву точку апроксимувального відрізка, що відбивається
на практичній реалізації методу.
Мета роботи – удосконалення методу кусково-
лінійної апроксимації контурів об’єктів у зображен-
нях, що дозволить застосовувати на всіх етапах
обробки паралельні обчислення з використанням
векторних операцій.
https://doi.org/10.34229/2707-451X.20.3.8
П.Ю. САБЕЛЬНІКОВ
86 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3
Удосконалений метод кусково-лінійної апроксимації контуру засновано на відомому
методі [5] з пошуком вузлів апроксимації, які належать контуру. За похибку апроксимації прийма-
ється довільна похибка . При цьому кількість вузлів апроксимації має бути якомога меншою.
Суть методу, що пропонується, полягає у послідовному пошуку можливих напрямків і кінце-
вих точок апроксимувального відрізка прямої лінії, що виходить з чергової початкової точки A0
(рисунок). Операції проводяться над векторами, кількість компонентів яких дорівнює кількості
оброблювальних пристроїв у векторному процесорі.
РИСУНОК. Приклад кусково-лінійної апроксимації
Метод передбачає таку послідовність дій.
1. Довільно вибирається початкова точка A0 першої апроксимувальної лінії.
2. Цикл 1. Початкова точка чергової апроксимувальної лінії A0 приймається за початок коор-
динат. Промінь, що проходить через точки A0 і Az першої групи точок, обирається за вісь x. Az – це
найближча до A0 точка, в порядку обходу контуру, на відстані більш ніж . Тому ( )z z
.
3. Цикл 2. Для чергової групи точок ділянки контуру від Az до Аі у новій системі координат з
використанням векторних операцій обчислюються вектори кутів променів, які виходять з точки A0:
( ,..., )z iV , ( ,..., ), ( ,..., )z i z iV V .
Вхідними даними є вектори координат точок контуру. Перед обчисленням інтегральних векто-
рів екстремумів для груп точок, починаючи з другої, за перші компоненти чергових векторів кутів
променів беруться мінімальні значення від z
і ir та максимальні від z
і ir , де ,i ir r –
компоненти інтегральних векторів, обчислені для попередньої групи.
4. За оригінальним методом обчислюються інтегральні вектори максимумів і мінімумів кутів
променів (метод векторного обчислення надано далі):
( ,..., )z iR r r , { ,..., }
z i
R r r ,
де min( ), max( ),
m m
m j m j
j z j z
r r m z i
.
5. Обчислюється результуючий вектор R:
( ) (( 1) ) (( 1) )R R R V R V R ,
де , – операції порівняння компонентів, які знаходяться в однаковій позиції векторів, <<1 –
операція зсуву компонентів вектора на одну позицію ліворуч. Починаючи від точки A0 першої
апроксимувальної лінії, у змінній k зберігається глобальний номер точки контуру, який відповідає
позиції останньої одиниці праворуч в R, якщо така одиниця існує. Цей номер вказує на ймовірну
позицію найдальшої кінцевої точки, для якої виконується друга умова апроксимації
1 1( )k k kr r
.
АПРОКСИМАЦІЯ КОНТУРУ ОБ’ЄКТА У ЗОБРАЖЕННІ ІЗ ЗАСТОСУВАННЯМ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 87
6. Перевіряється перша умова існування апроксимувальної лінії:
( ) (1,1,...,1)R R .
Якщо так, береться наступна група точок контуру, починаючи з останньої точки попередньої
групи, яка вважається початковою точкою групи Az . Виконуються дії, починаючи з п. 3, як і для
попередньої групи точок.
Якщо ні, номер k відповідає позиції найдальшої кінцевої точки чергової апроксимувальної
лінії. Відповідно, ця точка буде початковою точкою A0 наступної апроксимувальної лінії.
7. Дії повторюються з п. 2 до повернення в точку A0 першого апроксимувального відрізка
прямої лінії.
Для спрощення обчислень, щоб уникнути операцій arcsin, arccos, замість векторів значень
кутів використовуються вектори значень синусів та косинусів цих кутів.
Обчислення інтегральних векторів екстремальних значень послідовності чисел
На етапі 4 використовується запропонований метод паралельного обчислення інтегральних
векторів екстремальних значень послідовності чисел R , R , які обчислюються за допомогою
векторних операцій, що пришвидшує обчислювальний процес. Він полягає у такому.
Нехай вхідний вектор A = (a0, a1, …, an – 1) з кількістю компонентів n заноситься в результую-
чий вектор T. Послідовно, крок за кроком, здійснюється операція вибору екстремальних значень
між компонентами, які знаходяться в однаковій позиції вектора T і цього ж вектора, зсунутого
праворуч на 2i – 1 позицій. Результат записується у вектор T (T = extrem(T,(T>>2i – 1))), де extrem це
min або max, i – номер кроку, що змінюється в діапазоні від 1 до Ceil(log2n), функція Ceil(C) повер-
тає найближче до C ціле число, яке є не меншим C ( C), >>2i – 1 – операція зсуву компонентів
вектора праворуч на 2i – 1 позицій. При зсуві праворуч звільнені позиції заповнюються значеннями
крайніх лівих компонентів цього вектора.
Обґрунтування коректності методу обчислення інтегрального вектора екстремальних
значень послідовності чисел
Перевірка коректності методу здійснюється за рахунок дослідження номерів компонентів век-
тора, значення яких крок за кроком обчислюються в довільній позиції вектора T. Розглянемо варі-
ант обчислення інтегрального вектора мінімальних значень послідовності чисел A = (a0, a1, …, a7).
Після занесення послідовності чисел A у вектор T в позиції tj буде компонент aj. На кожному
наступному кроці, згідно з методом, у цій позиції матимемо мінімальне значення результату попе-
реднього кроку і такого ж результату з позиції, індекс якої на 2i – 1 менший, що відповідає операції зсуву
вектора на 2i – 1 позицій праворуч:
0) tj = aj,
1) tj = min(aj, aj-1),
2) tj = min(min(aj, aj – 1), min(aj – 2, aj – 3)),
3) tj = min(min(min(aj, aj – 1), min(aj – 2, aj – 3)), min(min(aj – 4, aj – 5), min(aj – 6, aj – 7))).
Оскільки операція обчислення екстремуму асоціативна, дужки можна розкрити. За j можна
взяти номер довільного елемента, результатом буде екстремум від значень усіх попередніх елемен-
тів, включаючи цей елемент (елементи з від’ємним індексом дорівнюють a0). Що і потрібно було
довести. Метод може бути реалізований на спеціалізованому векторному процесорі [7], або про-
грамно з використанням векторних команд універсальних процесорів.
Висновки. Запропоновано удосконалений метод кусково-лінійної апроксимації контурів
і метод обчислення інтегральних векторів екстремальних значень послідовності чисел, які реалі-
зуються із застосуванням векторних операцій та надають можливість прискорити розв’язання
задач контурного аналізу, а також інших подібних задач у режимі реального часу. Виграш у швид-
кості обчислень пропорційний кількості даних, які може одночасно обробити векторний процесор.
Наявність розвинутих підсистем із сотнями різноманітних векторних команд у процесорах фірм
Intel та ARM дозволяє на практиці використовувати запропоновані методи обчислень.
П.Ю. САБЕЛЬНІКОВ
88 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2020, № 3
Список літератури
1. Фурман Я.А., Юрьев А.Н., Яншин В.В. Цифровые методы обработки и распознавания бинарных изображений.
Красноярск: Изд-во Красноярск. ун-та, 1992. 248 с. https://www.twirpx.com/file/260742/
2. Фурман Я.А., Кревецкий А.В., Передреев А.К. и др. Введение в контурный анализ; приложения к обработке
изображений и сигналов. Под ред. Я.А. Фурмана. 2-е изд., испр. М.: Физматлит, 2003. 592 с.
https://www.twirpx.com/file/190580/
3. Мельник Э.И. Выделение прямых и дуг окружностей в технических чертежах. Автоматизация обработки и
распознавания изображений. Минск: ИТК АНБ, 1995. С. 147–154.
4. Прэтт У. Цифровая обработка изображений Т. 2. М.: Мир, 1982. 480 с. https://www.twirpx.com/file/73664/
5. Бутаков Е.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. М.: Радио и связь, 1987. 240 с.
http://computersbooks.net/books/photoshop/butakov-ea/1987/files/obrabotkaizobrageniynaevm1987.djv
6. Боюн В.П., Сабельніков П.Ю., Сабельніков Ю.А. Апроксимація замкненого контурного зображення багато-
кутником. Комп’ютерні засоби, мережі та системи. 2013. С. 89−97.
http://dspace.nbuv.gov.ua/handle/123456789/69713
7. Сабельніков П.Ю. Векторний операційний пристрій: пат. України на винахід №120139. Ін-т кібернетики імені
В.М. Глушкова НАН України. МПК G06F 7/00. № a2018 00961; заявл. 02.02.2018; опубл. 10.10.2019. Бюл. № 19. 5 с.
https://base.uipv.org/searchINV/search.php?action=viewdetails&IdClaim=262085
Одержано 14.08.2020
Сабельніков Павло Юрійович,
кандидат технічних наук, старший науковий співробітник
Інституту кібернетики імені В.М. Глушкова НАН України, Київ.
http://www.nas.gov.ua/UA/PersonalSite/Pages/default.aspx?PersonID=0000018440
pavelsabel@gmail.com
УДК 004.932
П.Ю. Сабельников
Аппроксимация контура объекта в изображении с применением векторных операций
Институт кибернетики имени В.М. Глушкова НАН Украины, Киев
Переписка: pavelsabel@gmail.com
Введение. Одним из направлений, связанных с идентификацией, анализом формы объектов, их
размера, ориентации, маркировки и других геометрических характеристик, является контурный анализ.
В литературе описаны различные методы аппроксимации контуров. Предлагаемый метод основан
на известном методе. Его суть заключается в последовательном поиске возможных направлений и ко-
нечных точек аппроксимирующих отрезков прямых линий, принадлежащих контуру. Количество узлов
аппроксимации должно быть как можно меньшим. Вычисления проводят только для очередной точки
контура, не возвращаясь для проверки критерия аппроксимации ко всем предыдущим точкам. Вычисли-
тельная сложность алгоритма пропорциональна количеству точек в контуре.
Цель работы − предложить метод кусочно-линейной аппроксимации контуров объектов в изобра-
жениях, который позволит применять на всех этапах компьютерной обработки параллельные вычисле-
ния с использованием векторных операций.
Результаты. В работе предложен усовершенствованный метод кусочно-линейной аппроксимации
замкнутого контура объекта в изображении многоугольником, вершинами которого являются непосред-
ственно точки этого контура. Критерий аппроксимации: расстояние от каждой точки аппроксимируе-
мого участка контура до аппроксимирующего отрезка не должно превышать погрешность аппроксима-
ции. Метод ориентирован на параллельные вычисления с использованием векторных операций.
Также предложен метод параллельного вычисления интегральных векторов экстремальных значе-
ний последовательности чисел для реализации параллельных вычислений с использованием векторных
операций на всех этапах аппроксимации.
https://www.twirpx.com/file/260742/
https://www.twirpx.com/file/190580/
https://www.twirpx.com/file/73664/
http://computersbooks.net/books/photoshop/butakov-ea/1987/files/obrabotkaizobrageniynaevm1987.djv
http://dspace.nbuv.gov.ua/handle/123456789/69713
https://base.uipv.org/searchINV/search.php?action=viewdetails&IdClaim=262085
mailto:pavelsabel@gmail.com
mailto:pavelsabel@gmail.com
АПРОКСИМАЦІЯ КОНТУРУ ОБ’ЄКТА У ЗОБРАЖЕННІ ІЗ ЗАСТОСУВАННЯМ ...
ISSN 2707-4501. Cybernetics and Computer Technologies. 2020, No.3 89
Выводы. Предложены методы, которые реализуются с применением векторных операций и предо-
ставляют возможность ускорить решение задач контурного анализа, а также других подобных задач
в режиме реального времени. Выигрыш в скорости вычислений пропорционален количеству данных,
которые может одновременно обработать векторный процессор. Наличие развитых подсистем вектор-
ных команд в процессорах компаний Intel и ARM позволяет на практике использовать предложенные
методы вычислений.
Ключевые слова: изображение, контур объекта, кусочно-линейная аппроксимация, параллельные
вычисления, векторные операции.
UDC 004.932
P. Sabelnikov
Approximation of the Contour of an Object in an Image Using Vector Operations
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Correspondence: pavelsabel@gmail.com
Introduction. One of the directions associated with identification, analysis of the shape of objects, their
size, orientation, marking and other geometric characteristics is contour analysis.
Various methods for contour approximation are described in the literature. The proposed method is based
on a well-known method. Its essence lies in the sequential search for possible directions and end points of ap-
proximating straight line segments belonging to the contour. The number of approximation nodes should be as
small as possible. The calculation is carried out only for the next point of the contour, without returning to
check the criterion of approximation to all previous points. The computational complexity of the algorithm is
proportional to the number of points in the contour.
The purpose of the paper to propose a method of piecewise linear approximation of the contours of ob-
jects in images, which will allow to use the parallel computations at all stages of computer processing using
vector operations.
Results. The paper proposes an improved method for piecewise linear approximation of a closed contour
of an object in an image by a polygon, the vertices of which are directly the points of this contour. Approxima-
tion criterion: the distance from each point of the approximated section of the contour to the approximating
segment should not exceed the approximation error. The method is focused on parallel computing using vector
operations.
A method for parallel computation of integral vectors of extreme values of a sequence of numbers for the
implementation of parallel computations using vector operations at all stages of approximation is also pro-
posed.
Conclusions. Methods are proposed that are implemented using vector operations and provide an oppor-
tunity to speed up the solution of contour analysis problems, as well as other similar problems in real time.
The gain in computing speed is proportional to the amount of data that a vector processor can simultaneously
process. The presence of developed subsystems of vector instructions in Intel and ARM processors makes it
possible to use the proposed computation methods in practice.
Keywords: image, object contour, piecewise linear approximation, parallel computations, vector
operations.
mailto:pavelsabel@gmail.com
|