UDC 004932:621.396

T.M. VLASOVA, V.G. KALMIKOVS

ALGORITMS UN PROGRAMMA ATTĒLA KONTŪRU ATZĪŠANAI KĀ CIGITĀLO LĪNIJU SEGMENTU SECĪBU

Anotācija: Dotajā darbā digitālā tiešās līnijas segmenta atpazīšanas algoritms bināro attēlu kontūrās un tiek apskatīta algoritma programmatūras realizācija. Šī algoritma izmantošana attēlu apstrādei radīs dabiskāku un ekonomiskāku aprakstu, salīdzinot ar zināmajiem attēlu aprakstīšanas veidiem. Aplūkoto algoritmu un programmatūras realizāciju var izmantot arī kontūru aprakstīšanai, apstrādājot pustoņu un krāsu attēlus.

Atslēgas vārdi: attēls, kontūra, digitālie taisnie segmenti, algoritms, programma.

Anotācija: Šajā robotā ir ieviests algoritms digitālo līniju atpazīšanai bināro attēlu kontūrās, kā arī algoritma programmatūras realizācija. Attēla apstrādes algoritmu izstrādājām tādā apjomā, lai attēla apraksts būtu dabiskāks un ekonomiski līdzvērtīgs attēla kodēšanas metodēm. Piedāvāto algoritmu un programmatūras ieviešanu var iestatīt kontūru kodēšanai, apstrādājot Navtone un krāsu attēlus. Atslēgas vārdi: attēli, kontūra, digitālās taisnes, algoritms, programma.

Kopsavilkums: Šajā rakstā mēs aplūkojam algoritmu digitālo līniju segmentu atpazīšanai bināro attēlu kontūrās un algoritma programmatūras ieviešanu. Šī algoritma izmantošana attēlu apstrādē radīs dabiskāku un ekonomiskāku, salīdzinot ar zināmi veidi attēlu apraksts. Aplūkoto algoritmu un programmatūras realizāciju var izmantot arī kontūru aprakstīšanai pelēktoņu un krāsu attēlu apstrādē. Atslēgas vārdi: attēls, kontūra, digitālo līniju segmenti, algoritms, programma.

1. Ievads

Attēlu kontūru kā līniju segmentu un līkņu loku secību strukturālā analīze ir viens no galvenajiem uzdevumiem attēlu apstrādē, lai tos interpretētu mākslīgā intelekta sistēmās.

Vairumā gadījumu attēlu var uzskatīt par plaknes daļu, kas sadalīta zonās ar nemainīgiem vai mainīgiem parametriem pēc kāda likuma, piemēram, optiskais blīvums, krāsa, faktūra, kas nosaka fonu un attēla objektus. Katras šīs zonas neatņemama īpašība ir tās robeža, tas ir, kontūra ir vienkārši savienota secība, kas sastāv no līniju segmentiem un izliektiem lokiem. Apstrādājot rastra attēlu, objektu kontūras parasti tiek izceltas. Tomēr objektu kontūras, kas attēlotas kā atsevišķu robežpikseļu kopa, nav īpaši piemērotas tālākai apstrādei, jo tās nepietiekami izsaka tā ģeometrisko būtību.

Attēla kontūru atpazīšanu līniju segmentu secības veidā var uzskatīt par vienu no galvenajiem uzdevumiem rastra attēla apstrādes procesā. Kontūras kā taisnu līniju segmentu secības attēlošanas problēmas risināšana ļauj iegūt attēla aprakstu kompaktā formā, kas ir dabiska cilvēka uztverei, nemainīga afīnās transformācijās, ērta, jo īpaši, apstrādei ar neironu tīkliem. Līniju segmenti ir kontūras pamatelementi. Arī līknes loku bieži aizstāj ar tajā ierakstītu lauztu līniju gan aprēķinu pamatos, gan lielā skaitā praktiski pielietojumi.

Zināmas metodes un algoritmi, jo īpaši tie, kas piedāvāti darbā, ļauj iegūt aptuvenu risinājumu, kas nav pieņemams visiem lietojumiem.

Šajā rakstā mēs aplūkojam binārā attēla kontūras atpazīšanu kā ciparu taisnu līniju segmentu secību, nezaudējot informāciju.

2. Kontūra kā ciparu līniju segmentu secība

Šajā sadaļā attēla kontūru strukturālā analīze aplūkota kā digitālo līniju segmentu secība, kas ir sākotnējie dati kontūras segmentēšanai digitālo līkņu lokos un digitālo līniju segmentos.

Aplūkosim tikai bināros attēlus, kuru objektus pilnībā nosaka to ierobežojošās kontūras. Digitālo līkņu lokus, kā arī digitālo līniju segmentus veido, atlasot attēlus, kas satur kontūras, ko veido taisnu līniju segmenti un līkņu loki.

Raksturīgās iezīmes transformācijas laikā tiek zaudēti taisnu līniju segmenti un līkņu loki. Skatot paraugu attēlu ar pietiekamu palielinājumu, bieži vien ir grūti secībā atpazīt atsevišķus līniju segmentus un līkņu lokus.

vertikālās un horizontālās sadaļas. Apstrādes laikā rodas papildu grūtības, jo kontūrlīnijas - matemātiskas līnijas bez biezuma - tiek parādītas monitora ekrānā savienotās pikseļu secībās, tas ir, vizuālās līnijas ar biezumu.

Lai novērstu no tā izrietošās problēmas, attēlu, kas iegūts no oriģināla diskretizācijas rezultātā, uzskatīsim par divdimensiju šūnu kompleksu. Šajā gadījumā

pikseļi ir šī šūnu kompleksa divdimensiju elementi. Papildus pikseļiem ir plaisas un punkti. Kreks ir

pikseļu malas, kas ir viendimensijas elementi. Punkti ir plaisu gala punkti un pikseļu stūra punkti. Punkti ir nulles dimensijas elementi. Tātad

Tātad aplūkojamajā gadījumā objekta kontūra ir savienota slēgta kontūru plaisu secība, kas robežojas starp objekta pikseļiem un fonu. Kontūru var aprakstīt kā veselu punktu koordinātu secību,

ierobežojot kontūras plaisas. Kā parādīts attēlā, attēla plaknes attēlojums kā

šūnu komplekss sniedz daudzas priekšrocības. Jo īpaši reģiona robeža kļūst par plānu līkni ar nulles laukumu.

Uz att. 1 ir parādīts objekta sākotnējās kontūras piemērs, ko veido līknes loks un taisnas līnijas segments, kā arī tā digitālais ekvivalents kā plaisu secība. Punkti, kas pieder pie dažādu virzienu plaisām, ir numurēti. Kā jau darbos, ar b-elementu saprotam viena un tā paša virziena sasaistītu plaisu secību, sākot no kāda punkta un beidzot ar tāda paša vai perpendikulāra virziena plaisu. Uz att. 1 parādīts viens no iespējamiem kontūras nodalījumiem b elementos, kurus veido plaisas starp punktiem: (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). Katru b elementu raksturo šādi parametri: virziens attiecībā pret tā sākuma punktu g (ņemts g = 0 - virzienam uz augšu, 1 - pa labi, 2 - uz leju, 3 - pa kreisi); l - plaisu skaits virzienā g (! = 1,2,...); pēdējās plaisas virziens q attiecībā pret iepriekšējo plaisu g virzienu (q = -1 - pēdējā plaisa ir vērsta pa kreisi attiecībā pret g virzienu, +1 - pa labi, 0 - sakrīt ar g virzienu ). Plaisu skaits l nosacīti tiks saukts par b elementa "garumu". B elementam (0-2) g =0, !=3, q =+1. B elementam (27-0) g =3, =1, q =0.

Digitālo līniju segmentu atlases metode kontūrā izmanto šādu segmentu veidojošo b elementu secības īpašību. Šāda secība ietver b-elementus ar vienādām g, q vērtībām; to garumi ņem vērtības!, +1. Un

garumu b elementu maiņu!, +1 nosaka turpinātā daļa, kas iegūta, dalot veselus skaitļus n = Ax = |x1 - x2| un m = Ay = |y1 - y2\, kur (x1zy1), (x2,y2) ir sākuma koordinātas

un segmenta beigu punkti: vai

Noteiktības labad pieņemam, ka n > m. Kā izriet no formulas (1), l - vesela daļa, dalot n ar m - atbilst ciparu taisnes segmentā l secīgu viena virziena plaisu skaitam. Kopā ar piegulošo perpendikulāro plaisu tie veido garuma b elementu!. k1 secīgi b-elementi ar garumu l un viens garuma b-elements!+1 (vai k1 secīgi b-elementi ar garumu +1 un viens garuma b-elements!) veido K1-elementu ar "garumu" k1 (ar līdzība ar "garuma" b-elementu). B-elements, kura garums atšķiras par 1 no secīgiem b-elementiem, tiks saukts par dotā K1 elementa modificēto b-elementu. Līdzīgi veidojas k2 secīgi K1 elementi ar “garumu” k1 un viens K1 elements “garums” k1 +1 (vai k2 secīgi K1 elementi ar “garumu” k1 +1 un viens K1 elements ar “garumu” k1) K2 – “garuma” elements k1. Tātad

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

tālāk, līdz ir izsmelti turpinātās daļas locekļi. K1 -elements (parasti K-1 -elements), kura garums par 1 atšķiras no secīgiem K1 -elementiem (Kg-1 -elements), mēs sauksim šī K2 modificēto K1 -elementu (Kg-1 -elements) - elements (Kg -elements). Tādējādi katram

taisnes ciparu segments atbilst turpinātajai daļai, kuras elementi nosaka šī segmenta struktūru.

Kontūrā attēlā. 1 var atlasīt šādus digitālo taisnu līniju segmentus: 0-3, 3-9, 910, 10-17, 17-0.

3. Digitālo līniju segmentu izvēle kontūrā

Apstrādājot attēla kontūras, jo īpaši bināros attēlus, plaisu secībā, kas veido kontūru, ir jāizvēlas secības daļas, kas veido līniju segmentus. Šo problēmu var uzskatīt par turpinātās daļas elementu noteikšanas problēmu no kontūras L-elementu secības. Šī problēma ir apgriezta problēmai par taisnas līnijas segmenta struktūras noteikšanu pēc turpinātās daļas locekļu secības, kas iegūta kā segmenta sākuma un beigu koordinātu atšķirību attiecība.

Digitālās līnijas segmentu atlases metode sastāv no sekojošu darbību secīgas veikšanas.

1. B-elementu secības izvēle plaisu secībā. Šī darbība atbilst veselas skaitļa daļas definīcijai! turpinājums (1).

2. Kg-elementu virknes izolācija ar r = 1 b-elementu secībā, un vienam no katra K1-elementa b-elementiem jāsatur 1 plaisa vairāk vai mazāk nekā pārējie. Šī darbība atbilst turpinātās frakcijas (1) k1-tā elementa definīcijai. Pēc tās izpildes r vērtība jāpalielina par 1.

3. Kg-elementu secības izolēšana Kg-1 elementu secībā,

turklāt vienam no katra Kg elementa Kg-1 elementiem ir jāsatur viens K-2 elements vairāk vai mazāk nekā pārējie. Šī darbība atbilst turpinātās daļas (1) k(-tā elementa definīcijai. Pēc tās izpildes r vērtība jāpalielina par 1.

4. 3. punktu atkārto, līdz tas joprojām ir iespējams no secīgiem Kr-elementiem

veido Km-elementu.

5. Robežpunktus nosaka starp diviem blakus esošiem b elementiem, kas nav iekļauti vienā Kg elementā. Šie punkti ir digitālo līniju segmentu beigu punkti, kas veido kontūru.

Apsveriet algoritmu līniju segmentu izvēlei b-elementu secībā

Let [b5 (/5,gs,qs)); s = 0,1,...,t - kontūru veidojošo L-elementu secība; x5, y5 - e-tā b-elementa sākuma koordinātas; [hu, y y); y = ; r = 0,1,...,!; !< £ - множество

kontūru pārtraukuma punkti. Pārtraukuma punkti nosaka līniju segmentu beigu punktus, kas veido ceļu. Atrast pārtraukuma punktus nozīmē noteikt līnijas posmus, kas veido kontūru.

Katru aplūkojamo segmentu raksturo Kg -elements, kā arī ķēde

šāviens. Sākotnējā segmenta atpazīšanas brīdī atbilstošās turpinātās daļas elementi ir vienādi ar 0. Segmentu var uzskatīt par atzītu, ja tiek atpazīti Kr elementa parametri, ieskaitot tā secību r un elementu vērtības atbilstošā turpinātā frakcija.

1. Sākotnējie nosacījumi.

Ir dotas sekvences [b5 (/5, gs, qs)) un (x5, y5).

Jāatrod pārtraukuma punktu koordinātas |x;.,y,).

k0r:= 0, k1r:= 0, k2r:= 0,..., kr:= 0 - turpinātās frakcijas elementu darba vērtības.

Par pirmā segmenta sākumpunktu pieņemsim punktu 5 =0; i = 0; i=0.

2. Paņemiet pirmo b-elementu secībā līdz pirmā taisnes posma sākumam. Tā sākuma punkts ir x5,y. Garums /=/0 ir arī turpinātās daļas pirmā elementa vērtība.

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

3. Pārbaudiet nākamo b elementu, vai tie kopā ar iepriekšējiem veido K0 elementu.

3.1. Ja ((q3 == q3-1) && (q3 == 73-1)&& (4 == /3-1)), tad Kr-elementa turpinājums k0p:= k0p +1; 5:= 5 + 1; un līnijas segmenta turpinājums. Pārejiet uz 3. vienumu.

3.2. Ja ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1)), tad līnijas segmenta beigas. Pārejiet uz 5. vienumu.

3.3. Ja ((&== 93+1) && (%== 73+1)&& ((/3+1== /3+1)1! (/3 - 1 == /3+1))), tad K0 -elementa pabeigšana; Ї = Ї+1.

4. K (-elementa) turpināšanas/pabeigšanas pārbaude.

4.1. Ja (k == 0), tad k ^= k^; cr:= 0; k^1p:= k1+ 1p+1; 5:=5 +1; Km elementa sākums.

Pārejiet uz 3. vienumu.

4.2. Ja ((k IF 0)&&(k == k^)), tad k^1p:= k^1p+1; 5:= 5+1; elementa Ki+1 turpinājums. Pārejiet uz 3. vienumu.

4.3. Ja ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^))), tad Ї := +1; Km elementa beigas.

Pārejiet uz 4. vienumu.

4.4. Ja ((^φ0)&&(|k - k1p|>1)), tad segmenta beigas ir tieša pāreja uz 5. vienumu.

5. Segmenta beigas.

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

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

Pretējā gadījumā L elementu secības beigas. Algoritma beigas.

Faktiski piedāvātais algoritms atrod turpinātās daļas elementus un katram iegūtajam Kt -elementam un pārbauda, ​​vai jaunizveidotā Kt elementa turpinātā daļa ir piemērota jau konstruētajam.

4. Programma digitālās līnijas segmentu atlasei

Kā redzams no algoritma apraksta, tajā ir ievērojams skaits nosacīto lēcienu, kuru izmantošana ir pretrunā ar strukturētās programmēšanas ieteikumiem grūtību dēļ, kas rodas programmu atkļūdošanas laikā. Turklāt parametru skaits Kt iepriekš

nevar noteikt, jo mainīgais t nav iepriekš ierobežots. Ierobežojiet t vērtību

Tas nozīmē iepriekš ierobežot attēla izmēru. Programmatūras ieviešana, it īpaši piedāvātā algoritma atkļūdošana ar triviāliem līdzekļiem, norādīto iemeslu dēļ ir ievērojami sarežģīta. Programmatūras ieviešanas izstrādes un atkļūdošanas grūtības ir iespējams samazināt, ja tiek izmantoti mūsdienīgi objektorientētas programmēšanas rīki.

Piedāvātais algoritms ir realizēts programmas LINESEGM veidā, kas ir daļa no laboratorijas programmatūras pakotnes attēlu apstrādei Visual C++ vidē.

Kā sākotnējo informāciju programma LINESEGM izmanto L-elementu secības, kas veidotas katrai apstrādātā attēla kontūrai.

Programmas rezultāts ir katrai kontūrai konstruētu ciparu taisnu līniju segmentu savienota secība, kas attēlota ar segmentu gala punktu koordinātām.

Kā redzams no algoritma, Kt -elementu konstruēšanas operācijas no Kt-l -elementiem

ir vienādas visām t vērtībām. Ņemiet vērā, ka sākotnējā vērtība t =0 ikreiz, kad algoritms darbojas, palielinās par 1. Speciālā klase CKForLn ietver metodes, kas atbilst algoritma darbībām. Algoritmu realizējošās programmas darbības laikā ar katru t pieaugumu par 1 tiek izveidots jauns objekts, kas satur funkcijas, kas veic algoritma darbības katrai t vērtībai.

Ņemot vērā, ka nulles līmenī K0 -elementi veidojas nevis no K -elementiem, bet gan no L -

elementiem, ir izveidota īpaša CKForLn klases modifikācija Cmini klase, lai realizētu algoritmu nulles līmenī.

Programmas darbības princips ir tāds, ka katrai t vērtībai programma realizē t-tā līmeņa CKForLn klases objektu, kas satur funkcijas, kas nosaka Kt elementa parametrus. Kt elementa sākotnējie parametri jau ir parametri

pabeigts Kt-l -elements, kura parametrus definēja CKForLn t-1 klases objekts

Oho līmenis.

CKForLn klases objekti tiek realizēti, kad rodas nosacījumi, proti: nepieciešamība veidot nākamā līmeņa K elementu, un tiek uzkrāti īpašā dinamiskā masīvā. Nulles līmeņa objekts tiek izveidots uzreiz programmas sākumā.

Objektu ieviešana dinamiskā masīvā, palielinoties t, ļauj neuzlikt ierobežojumus attēla izmēram. Attēla lieluma ierobežojumus nosaka tikai izmantotā datora resursi.

Aprakstot programmas darbību, tiks izmantots pabeigtā Kt jēdziens -

elements. Katrs pabeigtais Kt elements satur kt Kt-l elementus un vienu modificētu Kt-l elementu, kas satur kt-l ±1 Kt-2 elementus, atšķirībā no nepabeigtā Kt elementa, kas nesatur nepilnu Kt elementu.

CKForLn klase ietver šādas metodes.

1. Metode DK(), (define K-element) - definē K-elementu.

Noteikt Kt elementu nozīmē noteikt Kt-1 elementu skaitu, kas veido doto Kt elementu.

2. Metode VK§, (pārbaudi K-elementu) - pārbauda aplūkotā K elementa identitāti ar tāda paša līmeņa K elementu, kas iepriekš noteikts ar DK() metodes funkciju.

3. Metode DEO, (define end of K-element) - lai noteiktu K-elementa beigas, tas ir, definējot Kt-elementu, atrodiet tā modificēto Kt-1-elementu. Līmeņa t-1 metodes funkciju DE() izsauc t līmeņa DK() metodes funkcija.

4. Metode VE(),(pārbaudi K -elementa beigas) - pārbauda aplūkotā K elementa beigu identitāti ar modificēto K elementu, kas iepriekš noteikts ar DE () metodes funkciju.

Cmini klasē ietilpst tās pašas metodes, kas atšķiras no CKForLn klases metodēm ar to, ka Cmini klases metodes darbojas uz L elementiem un nosaka vai pārbauda K0 elementus.

Cmini klases metodes

Cmini klases metodes izmanto kā sākuma datu sekvences no L elementiem, kas konstruētas katrai no apstrādātā attēla kontūrām, sākot no L elementa pašreizējā numura metodes funkcijas izsaukšanas brīdī.

Cmini klases metodes DK() funkcija salīdzina katra nākamā L elementa parametrus ar sākotnējā L elementa parametriem, līdz tie sakrīt. Ja parametri nesakrīt, funkcija DK() pārbauda, ​​vai K0 elements ir pabeigts, un beidzas

strādāt. K0 -elements tiek uzskatīts par pabeigtu, ja tas beidzas ar modificētu L -elementu, kura garums atšķiras no citiem K0 -elementa L -elementiem par 1 (operācija 3.1 segmenta sākumam - t = 0).

Metodes VK() funkcija pārbauda, ​​vai sekojošo k0 L -elementu parametri atbilst K0 -elementa L -elementu parametriem, kas iepriekš definēti ar DK() metodes funkciju.

tāds pats līmenis. Ja pašreizējā K0 elementa parametri sakrīt ar iepriekš

definēts, funkcija VK() ģenerē segmenta turpinājuma zīmi un beidzas (operācija 3.1 segmenta turpinājumam - t > 0).

AT citādi funkcija VK() ģenerē segmenta beigu zīmi un beidzas

Metodes funkcija DE() salīdzina pašreizējā Kci elementa parametrus ar K0 elementa parametriem, ko iepriekš definēja funkcija DK(), lai noteiktu, vai pašreizējais K0 elements ir mainījies. Ja citi parametri ir vienādi, L elementu skaits k0

modificēto K0 elementu, salīdzinot ar iepriekš definēto K0 elementu

funkcijai DK() ir jāatšķiras ar 1 (operācija 3.2, 3.3, lai noteiktu pabeigšanu

sākuma K0 -nozares elements - t = 0). Rezultāts - modificētā K0 elementa parametri

tiek izmantoti Cmini klases VE() metodē.

Metodes funkcija VE() salīdzina pašreizējā K0 elementa parametrus ar modificētā K0 elementa parametriem, ko iepriekš definēja funkcija DE(), lai noteiktu, vai

vai tie sakrīt (operācija 3.2, 3.3 posma turpinājumam - t > 0). Rezultāts - atbilstības vai neatbilstības zīme - tiek izmantots CKForLn klases metodē VK().

CKForLn klases metodes

Metodes kā sākotnējos datus izmanto zemākajam līmenim konstruētos K-elementu parametrus. Tas ir, lai noteiktu Kt elementa parametrus, tiek izmantoti parametri

jau uzbūvēti Kt-l -elementi.

CKForLn klases t līmeņa metodes DK() funkcija, nosakot ^-elementa parametrus, izsauc CKForLn klases t-1 līmeņa funkciju VK(), kas pārbauda, ​​vai Kt-l elements ar tie paši parametri seko jau definētam Kt-l elementam. Ja jā, funkcijas VK() izsaukums tiek atkārtots. Šajā gadījumā tiek skaitīts atkārtojumu skaits, tas ir, tiek noteikts parametrs kt.

Pretējā gadījumā t līmeņa funkcija DK() izsauc t-1 līmeņa funkciju DE(), lai noteiktu modificēto Kt-l elementu un izietu. Darba beigās CKForLn klases t līmeņa funkcija DK() nosaka parametrus un ģenerē pabeigta vai nepabeigta Kt elementa pazīmes (operācija 4.1, 4.2 ar pašreizējo maksimālo vērtību t).

CKForLn klases t līmeņa metodes VK() funkcija pārbauda, ​​vai sekojošo kt Kt -elementu parametri ir tādi paši kā iepriekš definētā Kt elementa parametri.

tāda paša līmeņa metodes DK() funkcija. Ja pašreizējā Kt elementa parametri sakrīt ar

iepriekš definēta funkcija DK() Kt -vienāda līmeņa elements, funkcija VK().

ģenerē segmenta turpinājuma zīmi un pabeidz darbu.

Pretējā gadījumā funkcija VK() ģenerē segmenta beigu zīmi un iziet (operācija 4.1, 4.2 ar pašreizējo vērtību t, kas ir mazāka par maksimālo).

Kt elements Klases CKForLn DE0 līmeņa t metodes funkcija, nosakot Kt elementa parametrus, salīdzina pašreizējā Kt elementa parametrus ar Kt elementa parametriem, kas iepriekš definēti ar funkciju DK() lai noteiktu, vai pašreizējais Kt elements ir mainījies. Ja citi parametri ir vienādi, to kt-1 vērtībām jāatšķiras par 1. Ja šis nosacījums ir izpildīts, funkcija DE() ģenerē mainītā Kt elementa zīmi un

beidzas (operācija 4.3, 4.4 pie pašreizējās maksimālās vērtības t).

CKForLn klases t līmeņa metodes VE() funkcija salīdzina pašreizējā Kt elementa parametrus ar modificētā Kt elementa parametriem, kas iepriekš piešķirti ar funkciju DE(), lai noteiktu, vai to parametru vērtības sakrīt.

Ja pašreizējā Kt elementa parametru vērtības sakrīt ar iepriekšējo

ko nosaka tā paša līmeņa funkcija DK(), funkcija VK() ģenerē zīmi, ka parametru vērtības sakrīt, un beidzas (operācija 4.3, 4.4 ar pašreizējo vērtību t, kas ir mazāka par maksimālo).

Laika diagramma (2. att.) ilustrē programmas LINESEGM darbību, izmantojot taisnes segmenta atpazīšanas piemēru. Attēla apakšējā daļa parāda digitālās līnijas daļu, kas sastāv no viena un tā paša galvenā un palīgvirziena un dažāda garuma L-elementiem.

0. solī tiek izveidots Stіnі klases objekts, kas definē K0 elementa parametrus.

10. solī tiek pabeigta K0 elementa parametru noteikšana un izveidots klases CRORGn objekts 1, kas izmanto iepriekš izveidotā objekta funkcijas, lai noteiktu K1 elementa parametrus. 19. solī tiek pabeigta K1 elementa parametru definēšana un izveidots klases CCROGn objekts 2, kas izmanto iepriekš izveidoto objektu funkcijas, lai noteiktu K2 elementa parametrus. 49. solī tiek pabeigta K2 elementa parametru noteikšana un izveidots klases CRORGn objekts 3, kas izmanto iepriekš izveidoto objektu funkcijas, lai noteiktu K3 elementa parametrus. 79. darbībā

beigu nosacījums. Programmas darbība ir detalizēti aprakstīta pielikumā.

Sadaļā 0-6 divi b elementi veido nepabeigtu K0 elementu. Ir skaidrs, ka b -

3. garuma elements 3-6 pabeidz līnijas posmu, jo 1. garuma b-elements 6-7 nevar būt tā turpinājums. Tādējādi b-elements 6-7 ir ciparu līnijas segmenta sākums.

Uz att. 3 parāda programmas darbības piemēru. Cirtainās bultiņas binārā attēla kontūra ir sadalīta ar kvadrātiem taisnu līniju segmentos. Programmas rezultāts - līniju segmentu secība - tika izmantots, lai izceltu digitālo līkņu lokus. Lieli kvadrāti parāda digitālo līkņu loku robežas.

Programmas darbība ir pārbaudīta uz ievērojama skaita (vairāk nekā 2000) piemēru un tiek izmantota pustoņu attēlu strukturālās analīzes izpētē.

5. Līniju posmu atpazīšanas programmas darbs

Apskatīsim programmas iEBESM darbu uz att. piemēra. 4. Attēla apakšējā daļā redzama daļa no ciparu līnijas, kas sastāv no vienāda galvenā un palīgvirziena un dažāda garuma b-elementiem. Sadaļā 0-6 divi b elementi veido nepilnu K0-

Rīsi. 3. Kontūras strukturālās analīzes programmas darba piemērs - kontūras segmentēšana pa digitālo taisnu līniju segmentiem

elements. Acīmredzot b-elements 3-6, kura garums ir 3, pabeidz līnijas posmu, jo b-elements 6-7 ar garumu 1 nevar būt tā turpinājums. Tādējādi b-elements 6-7 ir ciparu līnijas segmenta sākums.

Programmas darbu taisnes nākamā posma noteikšanai uzsāk nulles līmeņa funkcija OK(), kas nosaka pabeigto K0 -elementu 6-10, kas sastāv no b elementiem.

garumi 1,1,2; k0=2. Šis K0 elements ir K1 elementa sākuma elements. Programma veido pirmā līmeņa objektu un nodod vadību šī objekta funkcijai OK(). 1. līmeņa funkcija OK() izsauc 0. līmeņa VKQ funkciju. Funkcija VKQ salīdzina K0 elementa 6-10 b elementu parametrus ar nākamajiem b elementiem un apstiprina K0 elementa 10-14 esamību,

identisks K0 -elementam 6-10. Turpinot, funkcija VKQ konstatē, ka nākamie b elementi neveido vienu un to pašu K0 elementu, iziet un nodod vadību 1. līmeņa OK() funkcijai. Līmeņa 1 OK() funkcija izsauc 0. līmeņa OE() funkciju. ar b-elementu 6-7, nosaka modificēta K0 elementa 14-19 klātbūtni, kas sastāv no b-elementiem ar garumu 1,1,1,2; k0=3, iziet un nodod vadību uz 1. līmeņa funkciju OK(). Šī funkcija nosaka pabeigta K1 elementa 6-19 klātbūtni, kas sastāv no diviem K0 -

elementi 1,1,2, (k1=2) un viens mainīts 1,1,1,2 (k0=3). Programma veido otrā līmeņa objektu un nodod vadību šī objekta funkcijai OK(). 2. līmeņa funkcija OK() izsauc 1. līmeņa VKQ funkciju, kas savukārt izsauc VKQ funkciju 0. Funkcija VKQ salīdzina K0 elementa b-elementus 6-10 ar sekojošo b

elementiem un apstiprina K0 elementu 19-23, 23-27 esamību, kas ir identiski K0 elementam 6-10, tas ir, tāds pats skaits kā tādi K0 elementi ir ietverti K1 elementā 6-19. Tālāk 0 līmeņa funkcija VKQ atgriež vadību ar 1. līmeņa funkcijas VKQ segmenta turpināšanas zīmi. Funkcija VKQ izsauc 0 līmeņa funkciju VE0, kas nosaka izmainīta K0 esamību -

elements 27-32, identisks K0 elementam 14-19. Tādējādi tiek definēts K1 elements 19-32,

identisks K1 elementam 6-19. Turklāt 1. līmeņa funkcija VKQ nenosaka nākamo K1 elementu, identisku K1 elementam 6-19, jo 0 līmeņa funkcija VE0 nenosaka modificēto K1 elementu, identisku K1 elementam 6-19, sākot no b elementa. 40-41, un atgriež 2. līmeņa funkcijas OK() vadību. 2. līmeņa funkcija OK() izsauc 1. līmeņa funkciju OE(), kas nosaka modificēta K1 elementa 32-49 klātbūtni, kas sastāv no K0 elementi 32-36, 36-40,

40-44, 44-49. Tālāk tiek noteikts K2 elements 6-49, tiek veidots 3.līmeņa objekts, noteikts modificētais K2 elements 49-79. Šie divi K2 elementi veido K3 elementu 6-79. Tas pabeidz segmenta uzbūvi, jo šādi b elementi 79-81 un 81-83 neveido K0 elementu,

identisks K0 elementam 6-10, un 0. līmeņa VKQ funkcija neģenerē turpinājuma karogu

segmentu. B elementu secībā tiek izvēlēts digitālās taisnes 6-79 segments. Programma sāk nākamā segmenta definīciju, sākot ar b-elementu 80-82.

b. atklājumiem

1. Piedāvāts jauns algoritms līniju segmentu atlasei attēla kontūrās un algoritma netriviāla programmatūras realizācija, kas ļauj iegūt precīzu risinājumu problēmai atpazīt attēla kontūras kā līniju segmentu secības.

2. Līniju segmentu atlases algoritma programmatūras realizācija attēla kontūrās veikta, izmantojot mūsdienīgi līdzekļi objektorientētā programmēšana, kas ļāva nenoteikt skaidrus ierobežojumus apstrādātā attēla izmēram, vienlaikus maksimāli izmantojot izmantotā datora resursus.

3. Pamatojoties uz piedāvāto algoritmu un tā programmatūras realizāciju, tika iegūts teorētiskais risinājums un veikti eksperimenti digitālo līkņu loku atpazīšanai un bināro attēlu kontūras segmentēšanai uz digitālo līniju segmenta un digitālo līkņu lokiem.

BIBLIOGRĀFIJA

1. Kovaļevskis V.A. Digitālo taisno segmentu pielietojumi ekonomiskai attēla kodēšanai, 7. starptautiskā semināra darbā DGCI"97, Monpeljē. - Francija, 1997. - 3.-5. decembris - 51.-62. lpp.

2. Kalmikovs V.G. Strukturālā metode digitālo taisnu līniju segmentu aprakstīšanai un atpazīšanai bināro attēlu kontūrās // Piece Intellect. - 2002. - Nr. 4. - C. 450-457.

3. Kalmikovs V.G., Višņevskis V.V. Objektu kontūru analīze bināros attēlos // Matemātiskās mašīnas un sistēmas. - 1997. - Nr.2. - S. 68 - 71.

4. Kalmikovs V.G. Digitālās līknes loks - apzīmējums un stagnācija // Signālu apstrāde un attēlu atpazīšana un attēlu atpazīšana. Visas Ukrainas starptautiskās konferences materiāli. - Kijeva. - 2004. - 11 - 15 Zhovten.

Problēmas formulēšana nosaka tās īstenošanas mērķis un iespējas.

Mērķis. Izstrādāt programmu taisnstūra detaļu klasificēšanai kvalitatīvās un bojātās.

Uzdevuma īstenošanas iespējas nosaka datora iespējas. Dators spēj apstrādāt skaitlisku informāciju algoritmiskā secībā. Lai realizētu datora iespējas, ir nepieciešams simulēt risināmo problēmu.

Modelēšana, izmantojot datoru, nozīmē pāreju no reāla objekta (pasaules) uz tā īpašību kodētu aprakstu, izmantojot datus un darbības ar tiem. Šāda pāreja, kā likums, tiek veikta vairākos posmos:

Abstrakcija- uzdevuma ziņā svarīgāko objekta pazīmju atlase.

Nepieciešams veikt pētījumus, kas ļauj pāriet no modelēšanas objekta uz modelēšanas priekšmetu, izmetot visu lieko atbilstoši uzdevumā izvirzītajam mērķim

Kā taisnstūris atšķiras no citiem četrstūriem?

• Pretējo pušu vienlīdzība.
• Pretējo pušu paralēlisms.
• Diagonāļu vienādība.
• Visi leņķi ir pareizi.

Kāds ir minimālais funkciju skaits, kas nepieciešams, lai unikāli atrisinātu problēmu?

• 2 pretējo malu vienādība + diagonāļu vienādība.
• 2 pretējo malu paralēlisms + diagonāļu vienādība.
• Trīs stūri ir pareizi.

Tātad, pateicoties abstrakcijai, mēs ieguvām verbālās informācijas modeli. Bet tas joprojām ir nesaprotams datoram. Tas saprot matemātisko modeli, kas tiek parādīts kā algoritms un ieviests programmatūrā.

Uzdevuma īstenošanas metodika.

Kvalitatīvas daļas (taisnstūra) vai bojātas daļas (četrstūra) rasējums tiek izveidots no segmentiem (komanda LINE) AutoCAD grafikas sistēmā un eksportēts uz . Programma kntrs.lsp() nolasa līnijas segmentu datus (virsotņu koordinātes) no DXF faila un ieraksta tos teksta failā vrtks.txt apaļā secībā.

Teksta failu vrtks.txt var izveidot manuāli, paņemot virsotņu koordinātas tieši no zīmējuma.

Izstrādātajai programmai rct.lsp jānolasa dati no faila vrtks.txt, tie jāanalizē un failā result.txt jāizvada ieraksts par daļas atbilstību prasībām (taisnstūris vai ne).

Pazīmju formalizēšana

Segmentu (malu vai diagonāļu) garumu vienādība: katra segmenta garumu nosaka kā taisnstūra taisnstūra hipotenūzu (saskaņā ar Pitagora teorēmu), izmantojot segmentu koordinātu atšķirību:

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

Līniju paralēlisms: K2= K1, kur Uz ir taisnes slīpums K=(Y2-Y1)/(X2-X1)

Kā formalizēt jēdzienu "taisns leņķis"? Kā daļu no uzdevuma klātbūtne " pareizā leņķī» var noteikt, pamatojoties uz segmentu perpendikularitāti: K2= -1/K1, kur Uz ir taisnes slīpums. K=(Y-Y0)/(X-X0).

Modeļa parādīšana datorā

Jebkura informācija galu galā tiek parādīta datorā, izmantojot bināros skaitļus (kodus) iekšējā mašīnas modelī. Iepriekš kodēšanu veica programmētājs. Tagad lielākā daļa programmu ir izveidotas algoritmiskās valodās.

Kad mēs skatāmies uz trīsdimensiju ainas divdimensiju attēlu (gleznā, fotogrāfijā, monitora ekrānā), mums šķiet, ka visi objekti, kurus mēs varētu redzēt, ja mēs tieši novērotu vienu un to pašu ainu dzīvē, ir tieši klāt. tur. Tikmēr viss, kas mums faktiski tiek dots divdimensiju attēlā, ir redzams lauks, kas ir tikai daži spilgtuma sadales funkcija vai krāsas divdimensiju plaknē: f(x, y) , kur x un y ir Dekarta koordinātas, kas apraksta attēla plakni.

Turklāt, pietuvojoties datora monitora ekrānam, var redzēt, ka attēls ekrānā patiesībā nav gluds un nepārtraukts, bet gan diskrēta “mozaīka”, kas sastāv no atsevišķiem krāsainiem taisnstūriem, kas sakārtoti regulārā taisnstūra matricā. Šis ir digitālais attēls. No matemātiskā viedokļa digitālais attēls ir divdimensiju matrica Im ar izmēru (DimXDimY), kur x ir vesels skaitlis no 0 līdz DimX–1, kas apraksta elementa numuru matricas rindā, y ir vesels skaitlis no 0 līdz DimY– 1, kas apraksta rindu. matricas numurs, kurā atrodas šis elements. Tajā pašā laikā tiek izsaukts pats digitālā attēla elements (taisnstūra matricas šūna). pikseļu(pikselis, attēla elements). Vienkāršākajā gadījumā katram pikselim Im ir skalāra vesela skaitļa vērtība, kas ir proporcionāla spilgtuma sadalījuma funkcijas vērtībai f(x, y) noteiktā plaknes punktā.

Uz att. 1.1.1. attēlā kreisajā pusē ir attēlots sievietes sejas attēls, kas atveidots kā attēls, bet labajā pusē ir palielināts tās pašas sejas (labās acs) attēla fragments, kur katram attēla elementam ir atbilstošā pikseļu skaitliskā vērtība. Attēla gaismas elementi atbilst b par Lielākas matricas vērtības, tumšās – mazākas vērtības. Digitālais attēls nesatur nekādu citu informāciju.

@Rīss. 1.1.1. Digitālais attēls kā divdimensiju intensitātes matrica

Sākot pētīt mašīnredzi, ir skaidri jāsaprot, ka datorā kā digitāls attēls tiek saglabāts tikai un vienīgi tāda vai cita formāta skaitļu divdimensiju masīvs. Jebkurus citus datus, ko mēs vēlamies iegūt no attēla (formas, līnijas, objekti, izmēri, attēlotā teksta saturs utt. utt.), var iegūt, tikai izmantojot vairākas attēla apstrādes un analīzes procedūras. ka mums vai nu jāprogrammē pašiem, vai jāizmanto gatavas procedūras, kas pieejamas labi zināmās attēlu analīzes programmatūras pakotnēs. Tajā pašā laikā, lai atrisinātu vienkāršas datorredzes problēmas gatavie līdzekļi visticamāk atrodamas attēlu apstrādes procedūru standarta bibliotēkās, sarežģītāku problēmu risināšanai būs jāapvieno noteiktas gatavas procedūras un daudziem gluži "parastiem" uzdevumiem, ko cilvēka "bioloģiskais" redzējums, tas Šķiet, risina viegli un bez piepūles, datormašīnredzei līdz šim joprojām nav risinājumu un joprojām turpina tos meklēt. Galu galā, izmantojot savu dabisko redzi, cilvēks viegli orientējas jebkurā vidē, atpazīst objektus, izvēlas ceļu, brauc ar automašīnu un daudz ko citu. Kāpēc dators, kas saņem attēlu no videokameras, to visu nevarētu izdarīt? Varbūt tā ir cilvēka acs uzbūve?

Patiesībā cilvēka acs, tāpat kā videokamera, veido tikai "redzamo lauku", līdzīgi kā digitālais attēls. Šajā gadījumā optiskā sistēma, kas sastāv no zīlītes un lēcas, projicē divdimensiju attēlu uz tīkleni, kur gaismas jutīgās šūnas ("stieņi" un "konusi") pārvērš iegūto attēlu nervu impulsos. Un tikai pēc tam komplekss saņemtās informācijas apstrādes mehānisms, kas funkcionē attiecīgajā mūsu smadzeņu nodaļā, interpretē šos impulsus kā mums saprotamu redzamās ainas attēlu. Tādējādi cilvēkiem "redzes" funkciju veic ne tikai acs, bet sistēma "acs + smadzenes" ("sensors + dators"). Tieši smadzenēs iebūvētie informācijas apstrādes algoritmi ļauj cilvēkam saprast, ko viņš redz. Šo iebūvēto algoritmu lomu var ilustrēt ar šādu piemēru.

Kad 20. gadsimta vidū oftalmoloģiskie ķirurgi iemācījās veikt acs lēcas operācijas, daudziem cilvēkiem, kuri bija akli no dzimšanas, bija tehniskas spējas skaidri redzēt. Tas ir, pēc šādas operācijas cilvēkam, kurš līdz šim bija akls (gaisma vienkārši netika cauri objektīvam), uz tīklenes sāka veidoties attēls un attiecīgie signāli sāka ienākt smadzenēs tieši tādā pašā veidā kā tas. notiek iekšā veseliem cilvēkiem. Diemžēl šajā gadījumā "redzēt gaismu" nenozīmēja "sākt redzēt". Kā liecina turpmākā vēsture, lielākā daļa "tehniski apgaismotu" pieaugušo pacientu nekad nav spējuši sasniegt ievērojamākus rezultātus redzes laukā par vienkāršu ģeometrisku formu atpazīšanu - un pat tas prasīja no viņiem nopietnas apzinātas pūles. Cilvēku atpazīšana pēc sejas un orientēšanās telpā viņiem palika nepārvarami uzdevumi. Fakts ir tāds, ka iebūvētie "automātiskās" vizuālās analīzes mehānismi, kas cilvēkiem attīstās agrā bērnībā, šiem pacientiem netika savlaicīgi izstrādāti, un viņi atradās datora pozīcijā, kuram ir attēla ievades ierīce, bet viņam nav analīzei nepieciešamās programmatūras.

Lai beidzot pārliecinātos par attēla, kas ir skaitlisku datu divdimensiju masīvs, analīzes uzdevuma sarežģītību, mēs mēģināsim sevi nostādīt datorprogrammas vietā, kas nodarbojas ar abstraktiem skaitļiem. Lai to izdarītu, mentāli mainīsim attēla uztveres modalitāti - pārnesim to no redzes zonas uz taustes. Iedomāsimies divdimensiju intensitātes vērtību masīvu kā šaha laukumu, kura izmērs ir vienāds ar attēla izmēru (DimXDimY), un katras šūnas centrā ir iestrēgusi kolonna, kuras augstums ir proporcionāls atbilstošā attēla pikseļa vērtībai. Citiem vārdiem sakot, uzskatiet divdimensiju attēlu kā sava veida nosacītu trīsdimensiju virsmu. Uz att. 1.1.2. pa kreisi kā attēls ir attēlots sievietes sejas fragments, bet labajā pusē - kā pseido-trīsdimensiju reljefs.

@Rīss. 1.1.2. Digitālais attēls kā pseido-3D reljefs

Tagad iedomājieties, ka jums, neskatoties uz attēlu, jāsajūt tam atbilstošais “reljefs” un jāmēģina noteikt, ko tieši šis “reljefs” attēlo - māju, suni vai cilvēka aci? Kā liecina eksperimenti, vidusmēra cilvēks ar šādu uzdevumu netiek galā. Pat visvienkāršāko ģeometrisko formu atpazīšana šādā "reljefa" attēlojumā būs saistīta ar ievērojamām pūlēm un prasīs apzinātu īpašu prasmju, stratēģijas un palpācijas algoritmu attīstību. Tāda, neskatoties uz šķietamo “digitālā attēla” objekta vienkāršību, ir datora un mašīnredzes uzdevumu patiesā sarežģītība.