UDC 004932:621.396

Т.М. ВЛАСОВА, В.Г. КАЛМИКОВ

АЛГОРИТЪМ И ПРОГРАМА ЗА РАЗПОЗНАВАНЕ НА КОНТУРИ НА ИЗОБРАЖЕНИЕ КАТО ПОСЛЕДОВАТЕЛЬНОСТЬ ОТ СЕГМЕНТИ ОТ ЦИФРОВИ ЛИНИИ

Резюме: В дадената работа алгоритъмът за разпознаване на цифровия директен сегмент в контурите на двоичните изображения и наразглежда се софтуерна реализация на алгоритъма. Използването на този алгоритъм за обработка на изображенията ще доведе до по-естествено и икономично описание в сравнение с известните начини за описание на изображенията. Разгледаният алгоритъм и софтуерната реализация могат да се използват и за описание на контурите при обработка на полутонови и цветни изображения.

Ключови думи: изображение, контур, цифрови прави отсечки, алгоритъм, програма.

Анотация: В този робот е въведен алгоритъм за разпознаване на цифрови линии в контурите на двоични изображения, както и софтуерна реализация на алгоритъма. Разработихме алгоритъма за обработка на изображения до степен, че описанието на изображението ще бъде по-естествено и икономично равно на методите за кодиране на изображението. Предложеният алгоритъм и софтуерна реализация могат да бъдат настроени за кодиране на контури при обработка на навигационни и цветни изображения. Ключови думи: изображения, контур, цифрови прави линии, алгоритъм, програма.

Резюме: В тази статия се разглежда алгоритъм за разпознаване на сегменти от цифрови линии в контурите на двоични изображения и софтуерна реализация на алгоритъма. Използването на този алгоритъм в обработката на изображения ще доведе до по-естествено и икономично в сравнение с известни начиниописание на изображенията. Разгледаният алгоритъм и софтуерна реализация могат да се използват и за описване на контури при обработката на сиви и цветни изображения. Ключови думи: изображение, контур, сегменти от цифрови линии, алгоритъм, програма.

1. Въведение

Структурният анализ на контурите на изображението като последователности от прави сегменти и криви дъги е една от основните задачи при обработката на изображения с цел интерпретирането им в системите с изкуствен интелект.

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

Разпознаването на контурите на изображението под формата на последователност от линейни сегменти може да се счита за една от основните задачи в процеса на обработка на растерно изображение. Решаването на проблема за представяне на контур като последователност от прави сегменти дава възможност да се получи описание на изображението в компактна форма, естествена за човешкото възприятие, инвариантна при афинни трансформации, удобна, по-специално, за обработка от невронни мрежи. Отсечките са основните елементи на контура. Дъгата на крива също често се заменя с прекъсната линия, вписана в нея, както в основите на смятането, така и в в големи количествапрактически приложения.

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

В тази статия разглеждаме разпознаването на контура на двоично изображение като последователност от сегменти от цифрови прави линии без загуба на информация.

2. Контур като последователност от сегменти от цифрови линии

Този раздел разглежда структурния анализ на контурите на изображението като последователност от сегменти от цифрови линии, които са изходни данни за сегментиране на контура в дъги от цифрови криви и сегменти от цифрови линии.

Нека се ограничим до разглеждането на бинарни изображения, чиито обекти са напълно определени от техните ограничаващи контури. Дъгите от цифрови криви, както и сегментите от цифрови линии, се образуват чрез вземане на проби изображения, съдържащи контури, образувани от сегменти от прави линии и дъги от криви.

Характерни чертисегменти от прави линии и дъги от криви се губят по време на трансформацията. Когато гледате образно изображение при достатъчно увеличение, често е трудно да се разпознаят отделни линейни сегменти и дъги от криви в последователност.

вертикални и хоризонтални секции. Допълнителни трудности възникват по време на обработката поради факта, че контурните линии - математически линии без дебелина - се показват на екрана на монитора в свързани последователности от пиксели, тоест визуални линии с дебелина.

За да премахнем проблемите, произтичащи от това, ще разгледаме изображението, получено от оригинала в резултат на дискретизация, като двуизмерен клетъчен комплекс. В такъв случай

пикселите са двуизмерни елементи на този клетъчен комплекс. В допълнение към пикселите има пукнатини и точки. Крекът е

страни на пиксели, които са едномерни елементи. Точките са крайните точки на пукнатините и ъгловите точки на пикселите. Точките са елементи с нулево измерение. Така

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

ограничаване на контурните пукнатини. Както е показано в , представянето на равнината на изображението като

клетъчен комплекс осигурява много предимства. По-специално, границата на региона се превръща в тънка крива с нулева площ.

На фиг. 1 е показан пример за начален контур на обект, образуван от дъга на крива и отсечка от права линия, както и неговия цифров еквивалент като поредица от пукнатини. Точките, принадлежащи на пукнатини с различни посоки, са номерирани. Както в произведенията, под b-елемент разбираме свързана последователност от пукнатини с една и съща посока, започваща от някаква точка и завършваща с пукнатина в същата или перпендикулярна посока. На фиг. 1 е показано едно от възможните разделяния на контура на b-елементи, които се образуват от пукнатини между точките: (0-2), (2-4), (4-6), (6-8), (8 -9), (9 -11), (11-13), (13-15), (15-17), (17-19), (20-21), (21-23), (23-25 ), (25-27 ), (27-0). Всеки b-елемент се характеризира със следните параметри: посока спрямо началната си точка g (взета g = 0 - за посоката нагоре, 1 - надясно, 2 - надолу, 3 - наляво); l - броят на пукнатините в посока g (! = 1,2,...); посоката на последната пукнатина q спрямо посоката g на предишните пукнатини (q = -1 - последната пукнатина е насочена наляво спрямо посоката g, +1 - надясно, 0 - съвпада с посоката g ). Броят на пукнатините l условно ще се нарича "дължина" на b-елемента. За b-елемента (0-2) g =0, !=3, q =+1. За b-елемент (27-0) g =3, =1, q =0.

Методът за избор на сегменти от цифрови линии в контура използва следното свойство на последователността от b-елементи, които образуват сегмента. Такава последователност включва b-елементи със същите стойности на g, q; техните дължини приемат стойностите !, +1. И

редуването на b-елементи с дължини!, +1 се определя от непрекъснатата дроб, получена чрез разделяне на цели числа n = Ax = |x1 - x2| и m = Ay = |y1 - y2\, където (x1zy1), (x2,y2) са координатите на началната

и крайни точки на сегмента: или

За определеност приемаме, че n > m. Както следва от формула (1), l - цялата част от деленето на n на m - съответства в отсечката на цифровата права на броя на l последователни пукнатини от една и съща посока. Заедно със съседната перпендикулярна пукнатина те образуват b-елемента на дължина!. k1 последователни b-елементи с дължина l и един b-елемент с дължина!+1 (или k1 последователни b-елементи с дължина +1 и един b-елемент с дължина!) образуват K1-елемент с "дължина" k1 (от аналогия с "дължина" b-елемент). b-елемент, който се различава по дължина с 1 от последователни b-елементи, ще се нарича модифициран b-елемент на даден K1-елемент. По същия начин, k2 последователни K1-елементи с „дължина“ k1 и един K1-елемент с „дължина“ k1 +1 (или k2 последователни K1-елементи с „дължина“ k1 +1 и един K1-елемент с „дължина“ k1) образуват K2- елементът „дължина“ k1. Така

k + k 2 + k z + ... + kg

по-нататък до изчерпване на членовете на продължителната дроб. K1 -елемент (обикновено K-1 -елемент), който се различава по дължина с 1 от последователни K1 -елементи (Kg-1 -елемент), ще наречем модифицирания K1 -елемент (Kg-1 -елемент) на този K2 - елемент (Kg -елемент). Така на всеки

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

В контура на фиг. 1 могат да бъдат избрани следните сегменти от цифрови прави линии: 0-3, 3-9, 910, 10-17, 17-0.

3. Избор на цифрови линейни сегменти в контура

Когато обработвате контури на изображения, по-специално двоични изображения, в поредица от пукнатини, образуващи контур, е необходимо да изберете части от последователността, които образуват линейни сегменти. Този проблем може да се разглежда като проблем за определяне на елементите на непрекъсната дроб от последователност от L-елементи на контура. Този проблем е обратен на задачата за определяне на структурата на отсечка от права линия от последователността на членовете на непрекъсната дроб, получена като съотношение на разликите в координатите на началото и края на отсечката.

Методът за избор на сегменти от цифрова линия се състои в последователно извършване на следните действия.

1. Избор на последователността на b-елементите в последователността на пукнатините. Това действие съответства на дефиницията на цяла част! продължаващ изстрел (1).

2. Изолиране на последователността от Kg-елементи с r = 1 в последователността на b-елементите, като един от b-елементите на всеки K1-елемент трябва да съдържа 1 пукнатина повече или по-малко от останалите. Това действие съответства на дефиницията на k1 -тия елемент от непрекъснатата дроб (1). След неговото изпълнение стойността на r трябва да се увеличи с 1.

3. Изолиране на последователността от Kg-елементи в последователността на Kg-1-елементи,

освен това, един от Kg-1 елементите на всеки Kg елемент трябва да съдържа един K-2 елемент повече или по-малко от останалите. Това действие съответства на дефиницията на k(-тия елемент от продължителната дроб (1). След неговото изпълнение стойността на r трябва да се увеличи с 1.

4. Параграф 3 се повтаря, докато все още е възможно от последователни Kr-елементи

образуват Km-елемент.

5. Граничните точки се определят между два съседни b-елемента, които не са включени в един и същ Kg-елемент. Тези точки са крайните точки на цифровите линейни сегменти, които образуват контура.

Помислете за алгоритъма за избор на линейни сегменти в последователността от b-елементи

Нека [b5 (/5,gs,qs)); s = 0.1,...,t - последователност от L-елементи, образуващи контура; x5, y5 - координати на началото на e-тия b-елемент; [hu, y y); y = ; r = 0,1,...,!; !< £ - множество

точки на прекъсване на контура. Точките на прекъсване определят крайните точки на линейните сегменти, които образуват пътя. Да се ​​намерят точки на прекъсване означава да се определят отсечките, които образуват контура.

Всеки разглеждан сегмент се характеризира с Kg -елемент, както и с верига

застрелян. В началния момент на разпознаване на сегмента елементите на съответната продължителна дроб са равни на 0. Сегментът може да се счита за разпознат, ако параметрите на Kr-елемента са разпознати, включително неговия ред r и стойностите на елементите на съответната продължена дроб.

1. Изходни условия.

Дадени са последователностите [b5 (/5, gs, qs)) и (x5, y5).

Необходимо е да се намерят координатите на точките на прекъсване |x;.,y,).

k0r:= 0, k1r:= 0, k2r:= 0,..., kr:= 0 - работни стойности на елементите на непрекъснатата дроб.

Да вземем за начална точка на първия сегмент точката 5 =0; i =0; i=0.

2. Вземете първия b-елемент в последователността до началото на първия сегмент от права линия. Неговата начална точка е x5,y. Дължината /=/0 също е стойността на първия елемент от продължителната дроб.

5:=5+1; k1p:=k1p+1.

3. Проверете за следващия b-елемент дали заедно с предишните образуват K0-елемент.

3.1. Ако ((q3 == q3-1) && (q3 == 73-1)&& (4 == /3-1)), тогава продължението на Kr-елемента k0p:= k0p +1; 5:= 5 + 1; и продължението на отсечката. Отидете на точка 3.

3.2. Ако ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1)), тогава краят на отсечката. Отидете на точка 5.

3.3. Ако ((&== 93+1) && (%== 73+1)&& ((/3+1== /3+1)1! (/3 - 1 == /3+1))), след това завършването на K0 -елемента; Ї = Ї+1.

4. Проверка на продължаването/завършването на K (-елемент.

4.1. Ако (k == 0), тогава k ^= k^; cr:= 0; k^1p:= k1+ 1p+1; 5:=5 +1; началото на елемента Km.

Отидете на точка 3.

4.2. Ако ((k IF 0)&&(k == k^)), тогава k^1p:= k^1p+1; 5:= 5+1; продължение на елемента Ki+1. Отидете на точка 3.

4.3. Ако ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^))), то Ї := +1; краят на Km-елемента.

Отидете на точка 4.

4.4. Ако ((^φ0)&&(|k - k1p|>1)), тогава краят на сегмента е директен преход към точка 5.

5. Край на сегмента.

X] = Xs; y \u003d Uz; k1p:= 0, k2p:= 0,., kіp:= 0; k:= 0, k2:= 0,., k:= 0.

Ако (с< S), то s:= s +1; переход к п. 2.

В противен случай краят на последователността от L -елементи. Край на алгоритъма.

Всъщност предложеният алгоритъм намира елементи от продължителната дроб и за всеки получен Kt -елемент и проверява дали продължената част на новопостроения Kt -елемент е подходяща за вече конструирания.

4. Програма за избор на сегменти от цифрова линия

Както се вижда от описанието на алгоритъма, той съдържа значителен брой условни скокове, чието използване противоречи на препоръките на структурното програмиране поради трудностите, които възникват при отстраняване на грешки в програми. В допълнение, броят на параметрите Kt предварително

не може да се определи, тъй като променливата t не е ограничена предварително. Ограничете стойността на t

Това означава предварително ограничаване на размера на изображението. Софтуерната реализация, особено отстраняването на грешки на предложения алгоритъм с тривиални средства, е значително затруднена поради посочените причини. Възможно е да се намалят трудностите при разработването и отстраняването на грешки в софтуерна реализация, ако се използват съвременни инструменти за обектно-ориентирано програмиране.

Предложеният алгоритъм е реализиран под формата на програмата LINESEGM, която е част от лабораторния софтуерен пакет за обработка на изображения в среда Visual C++.

Като начална информация програмата LINESEGM използва последователности от L-елементи, конструирани за всеки от контурите на обработеното изображение.

Резултатът от програмата е свързана последователност от сегменти от цифрови прави линии, изградени за всеки контур, представени от координатите на крайните точки на сегментите.

Както се вижда от алгоритъма, операциите по конструиране на Kt -елементи от Kt-l -елементи

са еднакви за всички стойности на t. Обърнете внимание, че първоначалната стойност t =0 се увеличава с 1 всеки път, когато алгоритъма работи. Специалният клас CKForLn включва методи, съответстващи на операциите на алгоритъма. По време на работата на програмата, която реализира алгоритъма, при всяко увеличение на t с 1 се създава нов обект, съдържащ функции, които изпълняват операциите на алгоритъма за всяка стойност на t.

Като се има предвид, че на нулево ниво K0 -елементите се образуват не от K -елементи, а от L -

елементи, беше създадена специална модификация на класа CKForLn, класа Cmini, за реализиране на алгоритъма на нулево ниво.

Принципът на действие на програмата е, че за всяка стойност на t програмата реализира обект от клас CKForLn от t-то ниво, който съдържа функции, които определят параметрите на елемента Kt. Първоначалните параметри на Kt-елемента са вече параметрите

завършен Kt-l -елемент, чиито параметри са дефинирани от обект от клас CKForLn t-1

Уау ниво.

Обектите от класа CKForLn се реализират при възникване на условия, а именно: необходимостта от изграждане на K-елемент от следващото ниво и се натрупват в специален динамичен масив. Обектът на нулево ниво се създава веднага в началото на програмата.

Внедряването на обекти в динамичен масив с увеличаване на t ви позволява да не налагате ограничения върху размера на изображението. Ограниченията за размера на изображението се определят само от ресурсите на използвания компютър.

Когато се описва работата на програмата, ще се използва концепцията за завършен Kt -

елемент. Всеки завършен Kt елемент съдържа kt Kt-l елементи и един модифициран Kt-l елемент, който съдържа kt-l ±1 Kt-2 елементи, за разлика от непълен Kt елемент, който не съдържа непълен Kt елемент.

Класът CKForLn включва следните методи.

1. Метод DK(), (дефиниране на K-елемент) - дефиниране на K-елемент.

Да се ​​определи Kt -елемент означава да се определи броят Kt-1 -елементи, които образуват даден Kt -елемент.

2. Метод VK§, (проверете K-елемент) - проверява идентичността на разглеждания K-елемент с K-елемента от същото ниво, предварително определен от функцията на метода DK().

3. Метод DEO, (дефиниране на края на K-елемента) - за определяне на края на K-елемента, тоест при дефиниране на Kt-елемента, намиране на неговия модифициран Kt-1-елемент. Функцията на метода DE() на ниво t-1 се извиква от функцията на метода DK() на ниво t.

4. Метод VE(),(проверете края на K -елемента) - проверете идентичността на края на разглеждания K -елемент с модифицирания K -елемент, предварително дефиниран от функцията на метода DE ().

Класът Cmini включва същите методи, които се различават от методите на класа CKForLn по това, че методите на класа Cmini оперират с L елементи и определят или проверяват K0 елементи.

Методи за клас Cmini

Методите на класа Cmini използват като начални последователности от данни от L-елементи, конструирани за всеки от контурите на обработеното изображение, започвайки от текущия номер на L-елемента в момента на извикване на функцията на метода.

Функцията на метода DK() на класа Cmini сравнява параметрите на всеки следващ L -елемент с параметрите на първоначалния L -елемент, докато съвпаднат. Ако параметрите не съвпадат, функцията DK() проверява дали елементът K0 е завършен и завършва

работа. K0 -елемент се счита за завършен, ако завършва с модифициран L -елемент, чиято дължина се различава от другите L -елементи на K0 -елемента с 1 (операция 3.1 за началото на отсечката - t = 0).

Функцията на метода VK() проверява дали параметрите на следните k0 L-елементи съвпадат с параметрите на L-елементите на K0-елемента, предварително дефинирани от функцията на метода DK()

същото ниво. Ако параметрите на текущия K0 елемент съвпадат с предишния

дефинирана, функцията VK() генерира знак за продължаване на сегмента и завършва (операция 3.1 за продължаване на сегмента - t > 0).

IN в противен случайфункцията VK() генерира знак за края на сегмента и завършва

Функцията на метода DE() сравнява параметрите на текущия елемент Kci с параметрите на елемента K0, предварително дефиниран от функцията DK(), за да определи дали текущият елемент K0 се е променил. Ако другите параметри са равни, броят на L -елементите k0

на модифицирания K0 елемент в сравнение с предварително дефинирания K0 елемент

функцията DK() трябва да се различава с 1 (операция 3.2, 3.3 за определяне на завършването

начален K0 -елемент на отсечката - t = 0). Резултат - параметри на модифицирания K0 елемент

се използват в метода VE() на класа Cmini.

Функцията на метода VE() сравнява параметрите на текущия K0 елемент с параметрите на модифицирания K0 елемент, предварително дефиниран от функцията DE(), за да определи дали

съвпадат ли (операция 3.2, 3.3 за продължение на отсечката - t > 0). Резултатът - знак за съвпадение или несъответствие - се използва в метода VK() на класа CKForLn.

Методи на класа CKForLn

Методите използват като изходни данни параметрите на К-елементите, конструирани за най-ниското ниво. Тоест, за да се определят параметрите на елемента Kt, се използват параметрите

вече изградени Kt-l -елементи.

Функцията на метода DK() на ниво t от клас CKForLn, когато определя параметрите на ^-елемент, извиква функцията VK() от ниво t-1 от клас CKForLn, която проверява дали Kt-l елемент с същите параметри следват вече дефиниран Kt-l елемент. Ако да, извикването на функцията VK() се повтаря. В този случай се отчита броят на повторенията, тоест се определя параметърът kt.

В противен случай, функцията DK() на ниво t извиква функцията DE() на ниво t-1, за да определи модифицирания Kt-l елемент и излиза. В края на работата функцията DK() на ниво t от класа CKForLn определя параметрите и генерира знаци за завършен или незавършен Kt елемент (операция 4.1, 4.2 с текущата максимална стойност на t).

Функцията на метода VK() на ниво t на класа CKForLn проверява дали параметрите на следните kt Kt -елементи са същите като параметрите на предварително дефинирания Kt -елемент

функция на метода DK() от същото ниво. Ако параметрите на текущия Kt-елемент съвпадат с

преди това дефинирана функция DK() Kt -елемент от същото ниво, функция VK().

генерира знак за продължението на сегмента и завършва работата.

В противен случай функцията VK() генерира знак за края на сегмента и излиза (операция 4.1,4.2 с текущата стойност t по-малка от максималната).

Kt елемент Функцията на метода DE0 ниво t на класа CKForLn, когато определя параметрите на елемент Kt, сравнява параметрите на текущия Kt елемент с параметрите на елемента Kt, предварително дефиниран от функцията DK(), за да определи дали текущият елемент Kt се е променил. Ако другите параметри са равни, техните kt-1 стойности трябва да се различават с 1. Ако това условие е изпълнено, функцията DE() генерира знак за променения Kt елемент и

приключва (операция 4.3, 4.4 при текущата максимална стойност t).

Функцията на метода VE() на ниво t от класа CKForLn сравнява параметрите на текущия елемент Kt с параметрите на модифицирания елемент Kt, предварително разпределен от функцията DE(), за да определи дали стойностите на техните параметри съвпадат.

Ако стойностите на параметрите на текущия Kt-елемент съвпадат с предишните

дефинирана от функцията DK() на същото ниво, функцията VK() генерира знак, че стойностите на параметрите съвпадат и се прекратява (операция 4.3,4.4 с текущата стойност на t по-малка от максималната).

Времевата диаграма (фиг. 2) илюстрира работата на програмата LINESEGM, използвайки примера за разпознаване на сегмент от права линия. Долната част на фигурата показва част от цифровата линия, състояща се от L-елементи със същите основни и спомагателни посоки и различни дължини.

На стъпка 0 се създава обект от класа Stіnі, който дефинира параметрите на K0 -елемента.

На стъпка 10 определянето на параметрите на елемента K0 завършва и се създава обект 1 от клас CRORGn, който използва функциите на предварително създадения обект за определяне на параметрите на елемента K1. На стъпка 19 дефинирането на параметрите на елемента K1 завършва и се създава обект 2 от клас CCROGn, който използва функциите на предварително създадените обекти за определяне на параметрите на елемента K2. На стъпка 49 определянето на параметрите на елемента K2 завършва и се създава обект 3 от клас CRORGn, който използва функциите на предварително създадените обекти за определяне на параметрите на елемента K3. На стъпка 79,

прекратяващо условие. Работата на програмата е описана подробно в приложението.

В секция 0-6 два b-елемента образуват незавършен K0-елемент. Очевидно е, че b -

елемент 3-6 с дължина 3 завършва линейния сегмент, тъй като b-елемент 6-7 с дължина 1 не може да бъде негово продължение. По този начин b-елементът 6-7 е началото на сегмента на цифровата линия.

На фиг. 3 показва пример за това как работи програмата. Контурът на двоичното изображение на къдравата стрелка е разделен от квадрати на прави сегменти. Резултатът от програмата - последователност от линейни сегменти - беше използван за подчертаване на дъгите на цифровите криви. Големите квадрати показват границите на цифровите дъги на кривата.

Работата на програмата е тествана върху значителен брой (повече от 2000) примери и се използва при изследване на структурния анализ на полутоновите изображения.

5. Работа на програмата за разпознаване на отсечки

Нека разгледаме работата на програмата iEBESM на примера на фиг. 4. Долната част на фигурата показва част от цифровата линия, състояща се от b-елементи с еднакви основни и спомагателни направления и различни дължини. В раздел 0-6 два b-елемента образуват непълен K0-

Ориз. 3. Пример за работата на програмата за структурен анализ на контура - сегментиране на контура по сегменти от цифрови прави линии

елемент. Очевидно b-елемент 3-6 с дължина 3 завършва отсечката, тъй като b-елемент 6-7 с дължина 1 не може да бъде негово продължение. По този начин b-елементът 6-7 е началото на сегмента на цифровата линия.

Работата на програмата за определяне на следващия сегмент от права линия се стартира от функцията OK() на нулево ниво, която определя завършения K0 -елемент 6-10, състоящ се от b-елементи

дължини 1,1,2; k0=2. Този елемент K0 е началният елемент за елемента K1. Програмата формира обект от първо ниво и прехвърля управлението на функцията OK() на този обект. Функцията OK() от ниво 1 извиква функцията VKQ на ниво 0. Функцията VKQ сравнява параметрите на b-елементите на K0-елемент 6-10 с последващите b-елементи и потвърждава наличието на K0-елемент 10-14,

идентичен с K0 -елемент 6-10. Продължавайки, функцията VKQ открива, че следващите b-елементи не образуват същия K0-елемент, излиза и прехвърля управлението на функцията OK() от ниво 1. Функцията на ниво 1 OK() извиква функцията ниво 0 OE(). с b-елемент 6-7, определя наличието на модифициран K0 елемент 14-19, състоящ се от b-елементи с дължини 1,1,1,2; k0=3, излиза и прехвърля управлението към функцията OK() от ниво 1. Тази функция определя наличието на завършен K1 елемент 6-19, състоящ се от две K0 -

елементи 1,1,2, (k1=2) и един променен 1,1,1,2 (k0=3). Програмата формира обект от второ ниво и прехвърля управлението на функцията OK() на този обект. Функцията OK() от ниво 2 извиква VKQ функция на ниво 1, която от своя страна извиква функцията VKQ ниво 0. Функцията VKQ сравнява b-елементите на елемента K0 6-10 със следното b

елементи и потвърждава наличието на K0 елементи 19-23, 23-27, идентични с K0 елемента 6-10, тоест същия брой като такива K0 елементи се съдържат в K1 елемента 6-19. След това функцията VKQ от ниво 0 връща управление със знака за продължаване на сегмента на функцията VKQ от ниво 1. Функцията VKQ извиква функцията VE0 от ниво 0, което определя наличието на променен K0 -

елемент 27-32, идентичен с K0 елемент 14-19. Така K1-елемент 19-32 е дефиниран,

идентичен с K1 елемент 6-19. Освен това функцията VKQ от ниво 1 не определя следващия елемент K1, идентичен с K1 елемент 6-19, тъй като функцията на ниво 0 VE0 не определя модифицирания елемент K1, идентичен с K1 елемент 6-19, започвайки от елемента b 40-41 и връща контрола на функцията OK() от ниво 2. Функцията OK() от ниво 2 извиква функцията OE() от ниво 1, която определя наличието на модифициран K1 елемент 32-49, състоящ се от K0 елементи 32-36, 36- 40,

40-44, 44-49. След това се определя K2 елемент 6-49, формира се обект на ниво 3, модифицираният K2 елемент 49-79 се определя. Тези два елемента K2 образуват K3 елемента 6-79. Това завършва изграждането на сегмента, тъй като следните b-елементи 79-81 и 81-83 не образуват K0 елемент,

идентичен с K0 елемент 6-10, а функцията VKQ ниво 0 не генерира флаг за продължаване

сегмент. В последователността от b-елементи се избира сегмент от цифровата права линия 6-79. Програмата започва дефинирането на следващия сегмент, започвайки с b-елемент 80-82.

б. заключения

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

2. Софтуерната реализация на алгоритъма за избор на линейни сегменти в контурите на изображението е направена с помощта съвременни средстваобектно-ориентирано програмиране, което направи възможно да не се налагат изрични ограничения върху размера на обработеното изображение, като същевременно се максимизира използването на ресурсите на използвания компютър.

3. На базата на предложения алгоритъм и неговата софтуерна реализация е получено теоретично решение и са проведени експерименти по разпознаване на дъги на цифрови криви и сегментиране на контура на двоични изображения върху сегмент от цифрови линии и дъги от цифрови криви.

БИБЛИОГРАФИЯ

1. Ковалевски В.А. Приложения на цифрови прави сегменти за икономично кодиране на изображения, В доклади от 7-ия международен семинар, DGCI"97, Монпелие. - Франция, 1997. - 3-5 декември. - P. 51-62.

2. Калмиков В.Г. Структурен метод за описване и разпознаване на сегменти от цифрови прави линии в контурите на двоични изображения // Piece Intellect. - 2002. - бр. 4. - С. 450-457.

3. Калмиков В.Г., Вишневски В.В. Анализ на контурите на обекта в двоични изображения // Математически машини и системи. - 1997. - No 2. - С. 68 - 71.

4. Калмиков В.Г. Дъгата на цифрова крива - обозначение и стагнация // Обработка на сигнали и разпознаване на изображения и разпознаване на изображения. Материали от Всеукраинската международна конференция. - Киев. - 2004. - 11 - 15 Жовтен.

Формулиране на проблемаобусловена от целта и възможностите за нейното изпълнение.

Цел.Разработете програма за класифициране на правоъгълни части на качествени и дефектни.

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

Моделирането с помощта на компютър предполага преход от реален обект (свят) към кодирано описание на неговите свойства с използване на данни и операции върху тях. Такъв преход, като правило, се извършва на няколко етапа:

Абстракция- избор на най-значимите характеристики на обекта по отношение на задачата.

Необходимо е да се проведе изследване, което ви позволява да преминете от моделиращия обект към обекта на моделиране, като изхвърлите всичко излишно в съответствие с целта в задачата

По какво се различава правоъгълникът от другите четириъгълници?

• Равенство на противоположните страни.
• Паралелизъм на противоположните страни.
• Равенство на диагоналите.
• Всички ъгли са прави.

Какъв е минималният брой функции, необходими за еднозначно решаване на проблема?

• Равенство на 2 противоположни страни + равенство на диагоналите.
• Паралелизъм на 2 противоположни страни + равенство на диагоналите.
• Три ъгъла са прави.

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

Методика за изпълнение на задачата.

Чертеж на качествена част (правоъгълник) или дефектна част (четириъгълник) се прави от сегменти (команда LINE) в графичната система AutoCAD и се експортира в . Програмата kntrs.lsp() чете данни за линейни сегменти (координати на върховете) от DXF файл и ги записва в текстов файл vrtks.txt в кръгов ред.

Текстовият файл vrtks.txt може да бъде създаден ръчно, като се вземат координатите на върховете директно от чертежа.

Разработената програма rct.lsp трябва да прочете данните от файла vrtks.txt, да ги анализира и да изведе във файла result.txt запис за съответствието на частта с изискванията (правоъгълник или не).

Формализиране на характеристиките

Равенство на дължините на отсечки (страни или диагонали): Дължината на всеки сегмент се определя като хипотенуза на правоъгълен правоъгълник (съгласно Питагоровата теорема) чрез разликата в координатите на отсечките:

(setq DX12 (abs (- X1 X2))) (setq DY12 (abs (- Y1 Y2))) (setq DA1 (sqrt (+ (* DX12 DX12) (* DY12 DY12))))

Паралелизъм на линиите: K2=K1, където ДА СЕе наклонът на правата линия K=(Y2-Y1)/(X2-X1)

Как да формализираме концепцията за "прав ъгъл"? Като част от задачата, наличието на " прав ъгъл» може да се определи въз основа на перпендикулярността на сегментите: K2= -1/K1, където ДА СЕе наклонът на правата линия. K=(Y-Y0)/(X-X0).

Показване на модела на компютъра

Всяка информация в крайна сметка се показва в компютър с помощта на двоични числа (кодове) във вътрешен модел на машината. Преди това кодирането се извършваше от програмист. Сега повечето от програмите са създадени на алгоритмични езици.

Когато гледаме двуизмерно изображение на триизмерна сцена (на картина, снимка, екран на монитор), ни се струва, че всички обекти, които бихме могли да видим, ако директно наблюдавахме една и съща сцена в живота, присъстват директно там. Междувременно всичко, което всъщност ни се дава в двуизмерен образ, е видимо поле, което е само малко функция за разпределение на яркосттаили цветовена двуизмерна равнина: е(х, г) , където хИ гса декартови координати, описващи равнината на изображението.

Освен това, ако се приближите до екрана на компютърен монитор, можете да видите, че изображението на екрана всъщност не е гладко и непрекъснато, а е дискретна „мозайка“, състояща се от отделни цветни правоъгълници, подредени в правилна правоъгълна матрица. Това е цифровото изображение. От математическа гледна точка цифрово изображениее двуизмерна матрица Im с размер (DimXDimY), където x е цяло число от 0 до DimX– 1, описващо номера на елемента в реда на матрицата, y е цяло число от 0 до DimY– 1, описващо реда номер на матрицата, в която се намира този елемент. В този случай елементът от самото цифрово изображение (клетка от правоъгълна матрица) се нарича пиксел(пиксел, елемент на картина). В най-простия случай всеки пиксел Im има скаларна целочислена стойност, пропорционална на стойността на функцията за разпределение на яркостта е(х, г) в дадена точка от равнината.

На фиг. На фигура 1.1.1 лявата страна показва изображение на женско лице, изобразено като изображение, а дясната страна показва увеличен фрагмент от изображението на същото лице (дясното око), където всеки елемент от изображението има съответната цифрова стойност на пиксела. Светли елементи на изображението отговарят на b относноПо-големи стойности на матрицата, тъмни – по-малки стойности. Цифровото изображение не съдържа никаква друга информация.

@Ориз. 1.1.1 Цифрово изображение като двуизмерна матрица на интензитета

Започвайки да изучавате машинното зрение, е необходимо ясно да разберете, че само и изключително двуизмерен масив от числа от един или друг формат се съхранява в компютър като цифрово изображение. Всички други данни, които бихме искали да извлечем от изображението (форми, линии, обекти, размери, съдържание на показания текст и т.н. и т.н.), могат да бъдат получени само в резултат на прилагане на редица процедури за обработка и анализ на изображения че трябва или да програмираме сами, или да използваме готови процедури, налични в добре познатите софтуерни пакети за анализ на изображения. В същото време за решаване на прости проблеми на компютърното зрение готови средствавероятно ще се намерят в стандартните библиотеки с процедури за обработка на изображения, за решаване на по-сложни проблеми ще е необходимо да се комбинират определени готови процедури, а за много съвсем „обикновени“ задачи, които „биологичното“ зрение на човек, то изглежда, решава лесно и без усилие, компютърното машинно зрение до все още няма решения и продължава да ги търси. В крайна сметка, използвайки естественото си зрение, човек лесно се ориентира във всяка среда, разпознава обекти, избира път, кара кола и много, много повече. Защо компютър, който получава изображение от видеокамера, не може да направи всичко това? Може би това е структурата на човешкото око?

Всъщност човешкото око, подобно на видеокамера, образува само "видимо поле", подобно на цифровото изображение. В този случай оптичната система, състояща се от зеницата и лещата, проектира двуизмерно изображение върху ретината, където фоточувствителните клетки („пръчици“ и „конуси“) преобразуват полученото изображение в нервни импулси. И едва след това сложен механизъм за обработка на получената информация, функциониращ в съответния отдел на нашия мозък, интерпретира тези импулси като разбираем за нас образ на видимата сцена. Така при хората функцията на "зрението" се изпълнява не само от окото, но и от системата "око + мозък" ("сензор + компютър"). Именно вградените в мозъка алгоритми за обработка на информация позволяват на човек да разбере какво вижда. Ролята на тези вградени алгоритми може да бъде илюстрирана със следния пример.

Когато в средата на 20-ти век офталмологичните хирурзи се научиха да извършват операции на лещата на окото, много хора, които бяха слепи от раждането, имаха техническата способност да виждат ясно. Тоест след такава операция при човек, който до този момент е бил сляп (светлината просто не е минавала през лещата), образът върху ретината започва да се формира и съответните сигнали започват да навлизат в мозъка по абсолютно същия начин, както се случва в здрави хора. За съжаление в този случай „да видиш светлината“ не означаваше „да започнеш да виждаш“. Както показа последвалата история, по-голямата част от „технически просветените“ възрастни пациенти никога не са били в състояние да постигнат по-значими резултати в полето на зрението от разпознаването на прости геометрични форми - и дори това изисква сериозни съзнателни усилия от тях. Разпознаването на хората по лицата и ориентацията в пространството остават непосилни задачи за тях. Факт е, че тези вградени механизми за "автоматичен" визуален анализ, които се развиват при хора в ранна детска възраст, не са развити своевременно при тези пациенти и те се оказват в позицията на компютър, който има устройство за въвеждане на изображение, но не разполага с необходимия софтуер за своя анализ.

За да се убедим окончателно в сложността на задачата да анализираме изображение, което е двуизмерен масив от числови данни, ще се опитаме да се поставим на мястото на компютърна програма, която се занимава с абстрактни числа. За да направим това, нека умствено променим модалността на възприятието на изображението - ще го прехвърлим от визуалната област в тактилната. Нека си представим двуизмерен масив от стойности на интензитета като шахматна дъска, чийто размер е равен на размера на изображението (DimXDimY), а в центъра на всяка клетка е залепена колона, чиято височина е пропорционален на стойността на съответния пиксел на изображението. С други думи, разгледайте двуизмерното изображение като вид условна триизмерна повърхност. На фиг. 1.1.2 вляво като изображение е показан фрагмент от женско лице, а вдясно като псевдотриизмерен релеф.

@Ориз. 1.1.2. Цифрово изображение като псевдо-3D релеф

Сега си представете, че без да гледате изображението, трябва да почувствате съответния „релеф“ и да се опитате да определите какво точно изобразява този „релеф“ - къща, куче или човешко око? Както показват експериментите, обикновеният човек не е в състояние да се справи с такава задача. Дори разпознаването на най-простите геометрични форми в такова "релефно" изображение ще бъде свързано със значителни усилия и ще изисква съзнателно развитие на специално умение, стратегия и алгоритми за палпация. Такава, въпреки очевидната простота на обекта „цифров образ“, е истинската сложност на задачите за компютърно и машинно зрение.