UDC 004932:621.396

T.M. VLASOVA, V.G. KALMIKOV

ALGORITMI DHE PROGRAMI PËR NJOHJEN E KONTUREVE TË IMAZHIT SI RADHJE E SEGMENTEVE TË LINJAVE DIGJITALE

Abstrakt: Në veprën e dhënë algoritmi i njohjes së segmentit të linjës direkte dixhitale në konturet e imazheve binare. dheështë konsideruar zbatimi softuerik i algoritmit. Përdorimi i këtij algoritmi për përpunimin e imazheve do të rezultojë në një përshkrim më të natyrshëm dhe ekonomik në krahasim me mënyrat e njohura të përshkrimit të imazheve. Algoritmi i konsideruar dhe zbatimi i softuerit mund të përdoren gjithashtu për përshkrimin e kontureve gjatë përpunimit të imazheve gjysmë-tonike dhe me ngjyra.

Fjalët kyçe: imazh, kontur, segmente të drejta dixhitale, algoritëm, program.

Shënim: Në këtë robot prezantohet një algoritëm për njohjen e linjave dixhitale në konturet e imazheve binare, si dhe një implementim softuerik i algoritmit. Ne zhvilluam algoritmin për përpunimin e imazhit në atë masë që përshkrimi i imazhit do të ishte më i natyrshëm dhe ekonomikisht i barabartë me metodat e kodimit të imazhit. Algoritmi i propozuar dhe zbatimi i softuerit mund të vendosen për kodimin e kontureve gjatë përpunimit të imazheve navtonike dhe me ngjyra. Fjalët kyçe: imazhe, kontur, vija të drejta dixhitale, algoritëm, program.

Abstrakt: Në këtë punim, ne shqyrtojmë një algoritëm për njohjen e segmenteve të linjave dixhitale në konturet e imazheve binare dhe zbatimin e softuerit të algoritmit. Përdorimi i këtij algoritmi në përpunimin e imazhit do të rezultojë në një më të natyrshme dhe më ekonomike në krahasim me mënyra të njohura përshkrimi i imazheve. Algoritmi i konsideruar dhe zbatimi i softuerit mund të përdoren gjithashtu për të përshkruar konturet në përpunimin e imazheve në shkallë gri dhe me ngjyra. Fjalët kyçe: imazh, kontur, segmente të linjave dixhitale, algoritëm, program.

1. Hyrje

Analiza strukturore e kontureve të imazhit si sekuenca të segmenteve të linjës dhe harqeve të kthesave është një nga detyrat kryesore në përpunimin e imazhit për qëllimin e interpretimit të tyre në sistemet e inteligjencës artificiale.

Në shumicën e rasteve, imazhi mund të konsiderohet si një pjesë e aeroplanit, e ndarë në zona me parametra konstante ose të ndryshueshme sipas ndonjë ligji, për shembull, dendësia optike, ngjyra, tekstura, të cilat përcaktojnë sfondin dhe objektet e imazhit. Një veti integrale e secilës prej këtyre zonave është kufiri i saj, domethënë, kontura është një sekuencë e lidhur thjesht e përbërë nga segmente vijash dhe harqe të lakuar. Kur përpunohet një imazh raster, zakonisht theksohen konturet e objekteve. Sidoqoftë, konturet e objekteve, të paraqitura si një grup pikselësh të veçantë, kufitarë, nuk janë shumë të përshtatshëm për përpunim të mëtejshëm, pasi ato nuk shprehin mjaftueshëm thelbin e tij gjeometrik.

Njohja e kontureve të imazhit në formën e një sekuence të segmenteve të linjës mund të konsiderohet si një nga detyrat kryesore në procesin e përpunimit të një imazhi raster. Zgjidhja e problemit të paraqitjes së një konture si një sekuencë e segmenteve të vijës së drejtë bën të mundur marrjen e një përshkrimi të imazhit në një formë kompakte, të natyrshme për perceptimin njerëzor, të pandryshueshme nën transformimet afinike, të përshtatshme, veçanërisht, për përpunimin nga rrjetet nervore. Segmentet e vijave janë elementet bazë të një konture. Harku i një lakore gjithashtu shpesh zëvendësohet nga një vijë e thyer e gdhendur në të, si në bazat e llogaritjes ashtu edhe në në numër të madh aplikime praktike.

Metodat dhe algoritmet e njohura, në veçanti ato të propozuara në punë, bëjnë të mundur marrjen e një zgjidhjeje të përafërt, e cila nuk është e pranueshme për të gjitha aplikimet.

Në këtë punim, ne e konsiderojmë njohjen e konturit të një imazhi binar si një sekuencë segmentesh të vijave të drejta dixhitale pa humbje informacioni.

2. Kontura si një sekuencë segmentesh të linjave dixhitale

Ky seksion e konsideron analizën strukturore të kontureve të imazhit si një sekuencë segmentesh të linjave dixhitale, të cilat janë të dhënat fillestare për segmentimin e konturit në harqe të kthesave dixhitale dhe segmente të linjave dixhitale.

Le të kufizohemi në shqyrtimin e imazheve binare, objektet e të cilave përcaktohen plotësisht nga konturet e tyre kufizuese. Harqet e kthesave dixhitale, si dhe segmentet e linjave dixhitale, formohen nga mostrat e imazheve që përmbajnë konturet e formuara nga segmentet e vijave të drejta dhe harqet e kthesave.

Tiparet karakteristike segmentet e drejtëzave dhe harqet e kthesave humbasin gjatë transformimit. Kur shikoni një imazh të kampionuar me zmadhim të mjaftueshëm, shpesh është e vështirë të njihen segmentet individuale të linjës dhe harqet e kthesave në një sekuencë.

seksione vertikale dhe horizontale. Vështirësi të tjera lindin gjatë përpunimit për shkak të faktit se linjat e konturit - linjat matematikore pa trashësi - shfaqen në ekranin e monitorit në sekuenca të lidhura pikselësh, domethënë linja vizuale me trashësi.

Për të eliminuar problemet që lindin nga kjo, imazhin e marrë nga origjinali si rezultat i diskretimit do ta konsiderojmë si një kompleks qelizash dydimensionale. Në këtë rast

pikselët janë elementë dydimensionale të këtij kompleksi qelizor. Përveç pikselëve, ka të çara dhe pika. Plasaritja është

anët e pikselave që janë elemente njëdimensionale. Pikat janë pikat fundore të çarjeve dhe pikat e qosheve të pikselëve. Pikat janë elemente me dimensione zero. Kështu që

Kështu, në rastin në shqyrtim, kontura e objektit është një sekuencë e mbyllur e lidhur e çarjeve konturore, në kufi midis pikselëve të objektit dhe sfondit. Një kontur mund të përshkruhet si një sekuencë e koordinatave të pikës së plotë,

duke kufizuar çarjet konturore. Siç tregohet në , përfaqësimi i planit të imazhit si

Kompleksi i qelizave ofron shumë përfitime. Në veçanti, kufiri i rajonit bëhet një kurbë e hollë me sipërfaqe zero.

Në fig. 1 tregon një shembull të konturit fillestar të një objekti të formuar nga një hark i një kurbë dhe një segment të drejtë, si dhe ekuivalenti i tij dixhital si një sekuencë çarjesh. Pikat që i përkasin çarjeve të drejtimeve të ndryshme janë të numëruara. Ashtu si në punime, me elementin b nënkuptojmë një sekuencë të lidhur çarjesh të të njëjtit drejtim, duke filluar nga një pikë dhe duke përfunduar me një çarje të të njëjtit drejtim ose pingul. Në fig. 1 tregon një nga ndarjet e mundshme të konturit në elemente b, të cilat formohen nga çarje midis pikave: (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). Çdo b-element karakterizohet nga parametrat e mëposhtëm: drejtimi në lidhje me pikën e tij fillestare g (marrë g = 0 - për drejtimin lart, 1 - djathtas, 2 - poshtë, 3 - majtas); l - numri i çarjeve në drejtimin g (! = 1,2,...); drejtimi i çarjes së fundit q në lidhje me drejtimin g të çarjeve të mëparshme (q = -1 - plasaritja e fundit drejtohet majtas në lidhje me drejtimin g, +1 - djathtas, 0 - përkon me drejtimin g ). Numri i çarjeve l në mënyrë konvencionale do të quhet "gjatësia" e elementit b. Për elementin b (0-2) g =0, !=3, q =+1. Për b-elementin (27-0) g =3, =1, q =0.

Metoda e zgjedhjes së segmenteve të linjave dixhitale në kontur përdor vetinë e mëposhtme të sekuencës së elementeve b që formojnë segmentin. Një sekuencë e tillë përfshin b-elemente me të njëjtat vlera g, q; gjatësitë e tyre marrin vlerat !, +1. Dhe

alternimi i b-elementeve të gjatësive!, +1 përcaktohet nga thyesa e vazhdueshme e përftuar nga pjesëtimi i numrave të plotë n = Ax = |x1 - x2| dhe m = Ay = |y1 - y2\, ku (x1zy1), (x2,y2) janë koordinatat e fillestarit

dhe pikat fundore të segmentit: ose

Për definicion, supozojmë se n > m Siç vijon nga formula (1), l - pjesa e plotë e pjesëtimit n me m - korrespondon në segmentin e drejtëzës dixhitale me numrin e l çarjeve të njëpasnjëshme të të njëjtit drejtim. Së bashku me plasaritjen pingule fqinje formojnë elementin b të gjatësisë!. k1 b-elementë të njëpasnjëshëm me gjatësi l dhe një element b të gjatësisë!+1 (ose k1 b-elementë të njëpasnjëshëm me gjatësi +1 dhe një element b të gjatësisë!) formojnë një element K1 me "gjatësi" k1 (nga analogji me "gjatësinë "b-element). Një element b që ndryshon në gjatësi me 1 nga elementët b të njëpasnjëshëm do të quhet një element b i modifikuar i një elementi K1 të dhënë. Në mënyrë të ngjashme, k2 K1-elemente të njëpasnjëshme të "gjatësisë" k1 dhe një K1-element me "gjatësi" k1 +1 (ose k2 K1-elemente të njëpasnjëshme të "gjatësisë" k1 +1 dhe një K1-element me "gjatësi" k1) formohen. K2- elementi “gjatësi” k1. Kështu që

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

më tej derisa anëtarët e thyesës së vazhdueshme të shteren. K1 -element (përgjithësisht K-1 -element), i cili ndryshon në gjatësi me 1 nga elementët e njëpasnjëshëm K1 (Kg-1 -element), ne do ta quajmë elementin e modifikuar K1 (Kg-1 -element) të këtij K2 - element (Kg -element). Kështu, për secilin

një segment dixhital i një vije të drejtë korrespondon me një fraksion të vazhdueshëm, elementët e të cilit përcaktojnë strukturën e këtij segmenti.

Në konturin në Fig. 1 mund të zgjidhen segmentet e mëposhtme të vijave të drejta dixhitale: 0-3, 3-9, 910, 10-17, 17-0.

3. Përzgjedhja e segmenteve të linjës dixhitale në kontur

Kur përpunoni konturet e imazhit, në veçanti, imazhet binare, në një sekuencë çarjesh që formojnë një kontur, është e nevojshme të zgjidhni pjesë të sekuencës që formojnë segmente vijash. Ky problem mund të konsiderohet si një problem i përcaktimit të elementeve të një fraksioni të vazhdueshëm nga një sekuencë e elementeve L të konturit. Ky problem është i kundërt me problemin e përcaktimit të strukturës së një segmenti të një vije të drejtë nga sekuenca e anëtarëve të një fraksioni të vazhdueshëm, i marrë si raport i ndryshimeve në koordinatat e fillimit dhe fundit të segmentit.

Metoda e zgjedhjes së segmenteve të një linje dixhitale konsiston në kryerjen e njëpasnjëshme të veprimeve të mëposhtme.

1. Përzgjedhja e sekuencës së elementeve b në sekuencën e çarjeve. Ky veprim korrespondon me përkufizimin e një pjese të plotë! gjuajtja e vazhdueshme (1).

2. Izolimi i sekuencës së Kg-elementeve me r = 1 në sekuencën e elementeve b, dhe një nga b-elementet e çdo elementi K1 duhet të përmbajë 1 çarje më shumë ose më pak se të tjerët. Ky veprim korrespondon me përkufizimin e elementit k1 të thyesës së vazhdueshme (1). Pas ekzekutimit të tij, vlera e r duhet të rritet me 1.

3. Izolimi i sekuencës së Kg-elementeve në sekuencën e Kg-1 -elementeve,

për më tepër, një nga elementët Kg-1 të çdo elementi Kg duhet të përmbajë një element K-2 më shumë ose më pak se të tjerët. Ky veprim korrespondon me përcaktimin e elementit k(-të të thyesës së vazhdueshme (1). Pas ekzekutimit të tij, vlera e r duhet të rritet me 1.

4. Paragrafi 3 përsëritet derisa të jetë ende e mundur nga Kr-elemente të njëpasnjëshme

formojnë elementin Km.

5. Pikat kufitare përcaktohen ndërmjet dy elementeve b ngjitur që nuk përfshihen në të njëjtin Kg-element. Këto pika janë pikat fundore të segmenteve të linjës dixhitale që formojnë konturin.

Konsideroni algoritmin për zgjedhjen e segmenteve të linjës në sekuencën e elementeve b

Le të [b5 (/5,gs,qs)); s = 0.1,...,t - sekuenca e elementeve L që formojnë konturin; x5, y5 - koordinatat e fillimit të elementit e-të b; [hu, y y); y = ; r = 0,1,...,!; !< £ - множество

pikat e thyerjes së konturit. Pikat e ndërprerjes përcaktojnë pikat fundore të segmenteve të linjës që formojnë shtegun. Të gjesh pikat e thyerjes do të thotë të përcaktosh segmentet e vijës që formojnë konturin.

Çdo segment në shqyrtim karakterizohet nga një element Kg, si dhe nga një zinxhir

e qëlluar. Në momentin fillestar të njohjes së segmentit, elementët e fraksionit të vazhdueshëm përkatës janë të barabartë me 0. Një segment mund të konsiderohet i njohur nëse njihen parametrat e elementit Kr, duke përfshirë renditjen e tij r dhe vlerat e elementeve të thyesa e vazhdueshme përkatëse.

1. Kushtet fillestare.

Janë dhënë sekuencat [b5 (/5, gs, qs)) dhe (x5, y5).

Është e nevojshme të gjenden koordinatat e pikave të thyerjes |x;.,y,).

k0r:= 0, k1r:= 0, k2r:= 0,..., kr:= 0 - vlerat e punës të elementeve të fraksionit të vazhduar.

Le të marrim si pikënisje të segmentit të parë pikën 5 =0; i =0; i=0.

2. Merrni elementin e parë b në sekuencë nga fillimi i segmentit të parë të drejtë. Pika e tij e fillimit është x5,y. Gjatësia /=/0 është gjithashtu vlera e elementit të parë të thyesës së vazhduar.

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

3. Kontrolloni për elementin b të ardhshëm nëse ata së bashku me të mëparshmit formojnë një element K0.

3.1. Nëse ((q3 == q3-1) && (q3 == 73-1)&& (4 == /3-1)), atëherë vazhdimi i elementit Kr k0p:= k0p +1; 5:= 5 + 1; dhe vazhdimi i segmentit të linjës. Shkoni te pika 3.

3.2. Nëse ((d3 f d3-1) || (d3 f 73-1)11 (|/e - /є-1!>1)), atëherë fundi i segmentit të linjës. Shkoni te pika 5.

3.3. Nëse ((&== 93+1) && (%== 73+1)&& ((/3+1== /3+1)1! (/3 - 1 == /3+1))), pastaj plotësimi i elementit K0; Ї = Ї+1.

4. Kontrollimi i vazhdimësisë/përfundimit të elementit K (-.

4.1. Nëse (k == 0), atëherë k ^= k^; cr:= 0; k^1p:= k1+ 1p+1; 5:=5 +1; fillimi i elementit Km.

Shkoni te pika 3.

4.2. Nëse ((k IF 0)&&(k == k^)), atëherë k^1p:= k^1p+1; 5:= 5+1; vazhdim i elementit Ki+1. Shkoni te pika 3.

4.3. Nëse ((k (Ф 0)&&((k+1== k1p)11(k1-1 == k^))), atëherë Ї := +1; fundi i elementit Km.

Shkoni te pika 4.

4.4. Nëse ((^φ0)&&(|k - k1p|>1)), atëherë fundi i segmentit është një kalim i drejtpërdrejtë në artikullin 5.

5. Fundi i segmentit.

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

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

Përndryshe, fundi i sekuencës së elementeve L. Fundi i algoritmit.

Në fakt, algoritmi i propozuar gjen elementë të fraksionit të vazhdueshëm dhe për çdo element Kt të marrë dhe kontrollon nëse fraksioni i vazhdueshëm i elementit Kt të sapondërtuar është i përshtatshëm për atë të ndërtuar tashmë.

4. Programi për zgjedhjen e segmenteve të një linje dixhitale

Siç shihet nga përshkrimi i algoritmit, ai përmban një numër të konsiderueshëm kërcimesh të kushtëzuara, përdorimi i të cilave bie ndesh me rekomandimet e programimit të strukturuar për shkak të vështirësive që lindin gjatë korrigjimit të programeve. Përveç kësaj, numri i parametrave Kt paraprakisht

nuk mund të përcaktohet, pasi ndryshorja t nuk është e kufizuar paraprakisht. Kufizoni vlerën e t

Kjo nënkupton kufizimin e madhësisë së imazhit paraprakisht. Zbatimi i softuerit, veçanërisht korrigjimi i algoritmit të propozuar me mjete të parëndësishme, për arsyet e treguara, është dukshëm i vështirë. Është e mundur të zvogëlohen vështirësitë e zhvillimit dhe korrigjimit të një zbatimi të softuerit nëse përdoren mjete programimi moderne të orientuara nga objekti.

Algoritmi i propozuar zbatohet në formën e programit LINESEGM, i cili është pjesë e paketës softuerike laboratorike për përpunimin e imazhit në mjedisin Visual C++.

Si informacion fillestar, programi LINESEGM përdor sekuenca të elementeve L të ndërtuara për secilën nga konturet e imazhit të përpunuar.

Rezultati i programit është një sekuencë e lidhur segmentesh të vijave të drejta dixhitale të ndërtuara për çdo kontur, të përfaqësuar nga koordinatat e pikave fundore të segmenteve.

Siç shihet nga algoritmi, operacionet e ndërtimit të Kt -elementeve nga Kt-l -elementet

janë të njëjta për të gjitha vlerat e t. Vini re se vlera fillestare t =0 rritet me 1 sa herë që ekzekutohet algoritmi. Klasa speciale CKForLn përfshin metoda që korrespondojnë me operacionet e algoritmit. Gjatë funksionimit të programit që zbaton algoritmin, me çdo rritje të t me 1, krijohet një objekt i ri që përmban funksione që kryejnë veprimet e algoritmit për çdo vlerë të t.

Duke marrë parasysh që në nivelin zero elementët K0 formohen jo nga elementët K, por nga L -

elemente, një modifikim i veçantë i klasës CKForLn, klasa Cmini, është krijuar për të zbatuar algoritmin në nivelin zero.

Parimi i funksionimit të programit është që për çdo vlerë të t, programi zbaton një objekt të klasës CKForLn të nivelit t-të, i cili përmban funksione që përcaktojnë parametrat e elementit Kt. Parametrat fillestarë të elementit Kt janë parametrat tashmë

kompletuar Kt-l -element parametrat e të cilit janë përcaktuar nga një objekt i klasës CKForLn t-1

Ua nivel.

Objektet e klasës CKForLn zbatohen kur lindin kushtet, përkatësisht: nevoja për të ndërtuar një element K të nivelit tjetër, dhe grumbullohen në një grup të veçantë dinamik. Objekti i nivelit zero krijohet menjëherë në fillim të programit.

Zbatimi i objekteve në një grup dinamik ndërsa t rritet ju lejon të mos vendosni kufizime në madhësinë e imazhit. Kufijtë e madhësisë së imazhit përcaktohen vetëm nga burimet e kompjuterit që përdoret.

Gjatë përshkrimit të funksionimit të programit, do të përdoret koncepti i një Kt të përfunduar -

element. Çdo element Kt i plotësuar përmban elemente kt Kt-l dhe një element Kt-l të modifikuar i cili përmban elemente kt-l ±1 Kt-2, ndryshe nga një element Kt jo i plotë i cili nuk përmban një element Kt jo të plotë.

Klasa CKForLn përfshin metodat e mëposhtme.

1. Metoda DK(), (përcaktoni elementin K) - përcaktoni një element K.

Të përcaktosh një element Kt do të thotë të përcaktosh numrin e elementeve Kt-1 që formojnë një element të caktuar Kt.

2. Metoda VK§, (verifikoni K-elementin) - kontrolloni identitetin e elementit K të konsideruar me elementin K të të njëjtit nivel, të përcaktuar më parë nga funksioni i metodës DK().

3. Metoda DEO, (përcaktoni fundin e elementit K) - për të përcaktuar fundin e elementit K, domethënë kur përcaktoni elementin Kt, gjeni elementin Kt-1 të modifikuar të tij. Funksioni i metodës DE() i nivelit t-1 thirret nga funksioni i metodës DK() i nivelit t.

4. Metoda VE(),(verifikoni fundin e elementit K) - kontrolloni identitetin e fundit të elementit K të konsideruar me elementin K të modifikuar, të përcaktuar më parë me funksionin e metodës DE ().

Klasa Cmini përfshin të njëjtat metoda, të cilat ndryshojnë nga metodat e klasës CKForLn në atë që metodat e klasës Cmini veprojnë në elementet L dhe përcaktojnë ose kontrollojnë elementët K0.

Metodat e klasës Cmini

Metodat e klasës Cmini përdorin si sekuenca fillestare të të dhënave të elementeve L të ndërtuara për secilën nga konturet e imazhit të përpunuar, duke filluar nga numri aktual i elementit L në momentin që thirret funksioni i metodës.

Funksioni i metodës DK() të klasës Cmini krahason parametrat e çdo elementi L të ardhshëm me parametrat e elementit L fillestar derisa ato të përputhen. Nëse parametrat nuk përputhen, funksioni DK() kontrollon nëse elementi K0 është i përfunduar dhe nëse përfundon

puna. Një element K0 konsiderohet i përfunduar nëse përfundon me një element L të modifikuar, gjatësia e të cilit ndryshon nga elementët e tjerë L të elementit K0 me 1 (operacioni 3.1 për fillimin e segmentit - t = 0).

Funksioni i metodës VK() kontrollon nëse parametrat e elementëve k0 L të mëposhtëm përputhen me parametrat e elementeve L të elementit K0 të përcaktuar më parë nga funksioni i metodës DK().

të njëjtin nivel. Nëse parametrat e elementit aktual K0 përputhen me ato të mëparshme

i përcaktuar, funksioni VK() gjeneron një shenjë të vazhdimit të segmentit dhe përfundon (operacioni 3.1 për vazhdimin e segmentit - t > 0).

AT ndryshe funksioni VK() gjeneron një shenjë të fundit të segmentit dhe përfundon

Funksioni i metodës DE() krahason parametrat e elementit aktual Kci me parametrat e elementit K0 të përcaktuar më parë nga funksioni DK() për të përcaktuar nëse elementi aktual K0 ka ndryshuar. Nëse parametrat e tjerë janë të barabartë, numri i elementeve L k0

të elementit K0 të modifikuar në krahasim me elementin K0 të përcaktuar më parë

funksioni DK() duhet të ndryshojë me 1 (operacioni 3.2, 3.3 për të përcaktuar përfundimin

fillestar K0 -elementi i segmentit - t = 0). Rezultati - parametrat e elementit K0 të modifikuar

përdoren në metodën VE() të klasës Cmini.

Funksioni i metodës VE() krahason parametrat e elementit aktual K0 me parametrat e elementit të modifikuar K0 të përcaktuar më parë nga funksioni DE() për të përcaktuar nëse

a përkojnë ato (operacioni 3.2, 3.3 për vazhdimin e segmentit - t > 0). Rezultati - një shenjë e një përputhjeje ose një mospërputhje - përdoret në metodën VK() të klasës CKForLn.

Metodat e klasës CKForLn

Metodat përdorin si të dhëna fillestare parametrat e elementeve K të ndërtuar për nivelin më të ulët. Kjo do të thotë, për të përcaktuar parametrat e elementit Kt, përdoren parametrat

tashmë të ndërtuara Kt-l -elemente.

Funksioni i metodës DK() të nivelit t të klasës CKForLn, gjatë përcaktimit të parametrave të një elementi ^, thërret funksionin VK() të nivelit t-1 të klasës CKForLn, i cili kontrollon nëse një element Kt-l me të njëjtat parametra ndjekin një element tashmë të përcaktuar Kt-l. Nëse po, thirrja e funksionit VK() përsëritet. Në këtë rast, numërohet numri i përsëritjeve, domethënë përcaktohet parametri kt.

Përndryshe, funksioni DK() i nivelit t thërret funksionin DE() të nivelit t-1 për të përcaktuar elementin e modifikuar Kt-l dhe del. Në fund të punës, funksioni DK() i nivelit t të klasës CKForLn përcakton parametrat dhe gjeneron shenja të një elementi Kt të përfunduar ose jo të plotë (operacioni 4.1, 4.2 me vlerën maksimale aktuale t).

Funksioni i metodës VK() të nivelit t të klasës CKForLn kontrollon nëse parametrat e elementëve kt Kt të mëposhtëm janë të njëjtë me parametrat e elementit Kt të përcaktuar më parë

funksioni i metodës DK() të të njëjtit nivel. Nëse parametrat e elementit aktual Kt përputhen me

më parë funksioni i përcaktuar DK() Kt -element i të njëjtit nivel, funksion VK().

gjeneron një shenjë të vazhdimësisë së segmentit dhe përfundon punën.

Përndryshe, funksioni VK() gjeneron një shenjë të fundit të segmentit dhe del (operacioni 4.1,4.2 me vlerën aktuale prej t më pak se maksimumi).

Elementi Kt Funksioni i metodës t nivelit DE0 të klasës CKForLn, kur përcakton parametrat e një elementi Kt, krahason parametrat e elementit aktual Kt me parametrat e elementit Kt të përcaktuar më parë nga funksioni DK() për të përcaktuar nëse elementi aktual Kt ka ndryshuar. Nëse parametrat e tjerë janë të barabartë, vlerat e tyre kt-1 duhet të ndryshojnë me 1. Nëse ky kusht plotësohet, funksioni DE() gjeneron një shenjë të elementit të ndryshuar Kt dhe

përfundon (operacioni 4.3, 4.4 në vlerën maksimale aktuale të t).

Funksioni i metodës VE() të nivelit t të klasës CKForLn krahason parametrat e elementit aktual Kt me parametrat e elementit të modifikuar Kt të alokuar më parë nga funksioni DE () për të përcaktuar nëse vlerat e tyre të parametrave përputhen.

Nëse vlerat e parametrave të elementit aktual Kt përputhen me ato të mëparshme

i përcaktuar nga funksioni DK() i të njëjtit nivel, funksioni VK() gjeneron një shenjë që vlerat e parametrave përputhen dhe përfundon (operacioni 4.3,4.4 me vlerën aktuale prej t më pak se maksimumi).

Diagrami i kohës (Fig. 2) ilustron funksionimin e programit LINESEGM duke përdorur shembullin e njohjes së një segmenti të drejtë. Pjesa e poshtme e figurës tregon një pjesë të linjës dixhitale, e përbërë nga elementë L me të njëjtat drejtime kryesore dhe ndihmëse dhe gjatësi të ndryshme.

Në hapin 0, krijohet një objekt i klasës Stіnі, i cili përcakton parametrat e elementit K0.

Në hapin 10, përfundon përcaktimi i parametrave të elementit K0 dhe krijohet një objekt 1 i klasës CRORGn, i cili përdor funksionet e objektit të krijuar më parë për të përcaktuar parametrat e elementit K1. Në hapin 19, përfundon përcaktimi i parametrave të elementit K1 dhe krijohet një objekt 2 i klasës CCROGn, i cili përdor funksionet e objekteve të krijuara më parë për të përcaktuar parametrat e elementit K2. Në hapin 49, përfundon përcaktimi i parametrave të elementit K2 dhe krijohet një objekt 3 i klasës CKRORGN, i cili përdor funksionet e objekteve të krijuara më parë për të përcaktuar parametrat e elementit K3. Në hapin 79,

kusht përfundimi. Funksionimi i programit përshkruhet në detaje në shtojcë.

Në seksionin 0-6, dy elementë b formojnë një element K0 të papërfunduar. Është e qartë se b -

elementi 3-6 i gjatësisë 3 plotëson segmentin e vijës, pasi elementi b 6-7 i gjatësisë 1 nuk mund të jetë vazhdimësi e tij. Kështu, elementi b 6-7 është fillimi i segmentit të linjës dixhitale.

Në fig. 3 tregon një shembull se si funksionon programi. Kontura e imazhit binar të shigjetës kaçurrelë ndahet me katrorë në segmente të vijës së drejtë. Rezultati i programit - një sekuencë segmentesh vijash - u përdor për të theksuar harqet e kthesave dixhitale. Sheshet e mëdha tregojnë kufijtë e harqeve të kurbës dixhitale.

Funksionimi i programit është testuar në një numër të konsiderueshëm (më shumë se 2000) shembujsh dhe përdoret në studimin e analizës strukturore të imazheve gjysmëtonike.

5. Puna e programit për njohjen e segmenteve të linjës

Le të shqyrtojmë punën e programit iEBESM në shembullin e fig. 4. Pjesa e poshtme e figurës tregon një pjesë të linjës dixhitale, e përbërë nga b-elemente me drejtime kryesore dhe ndihmëse të njëjta dhe gjatësi të ndryshme. Në seksionin 0-6, dy elementë b formojnë një K0- jo të plotë

Oriz. 3. Një shembull i punës së programit për analizën strukturore të konturit - segmentimi i konturit sipas segmenteve të drejtëzave dixhitale.

element. Natyrisht, elementi b 3-6 i gjatësisë 3 plotëson segmentin e vijës, pasi elementi b 6-7 i gjatësisë 1 nuk mund të jetë vazhdimi i tij. Kështu, elementi b 6-7 është fillimi i segmentit të linjës dixhitale.

Puna e programit për përcaktimin e segmentit vijues të vijës së drejtë fillon me funksionin OK () të nivelit zero, i cili përcakton elementin K0 të përfunduar 6-10, të përbërë nga b -elemente.

gjatesite 1,1,2; k0=2. Ky element K0 është elementi fillestar për elementin K1. Programi formon një objekt të nivelit të parë dhe transferon kontrollin në funksionin OK() të këtij objekti. Funksioni OK() i nivelit 1 thërret funksionin VKQ të nivelit 0. Funksioni VKQ krahason parametrat e elementeve b të elementit K0 6-10 me elementët pasues b dhe konfirmon praninë e elementit K0 10-14.

identike me K0 -elementin 6-10. Duke vazhduar, funksioni VKQ zbulon se elementët b të ardhshëm nuk formojnë të njëjtin element K0, del dhe transferon kontrollin në funksionin OK() të nivelit 1. Funksioni OK() i nivelit 1 thërret funksionin e nivelit 0 OE(). me b-elementin 6-7, përcakton praninë e një elementi K0 të modifikuar 14-19, i përbërë nga elemente b me gjatësi 1,1,1,2; k0=3, del dhe transferon kontrollin në funksionin OK() të nivelit 1. Ky funksion përcakton praninë e një elementi të kompletuar K1 6-19, i përbërë nga dy K0 -

elementet 1,1,2, (k1=2) dhe një i ndryshuar 1,1,1,2 (k0=3). Programi formon një objekt të nivelit të dytë dhe transferon kontrollin në funksionin OK() të këtij objekti. Funksioni OK() i nivelit 2 thërret funksionin VKQ të nivelit 1, i cili nga ana tjetër thërret funksionin VKQ të nivelit 0. Funksioni VKQ krahason elementet b të elementit K0 6-10 me b-në vijuese

elemente dhe konfirmon praninë e elementeve K0 19-23, 23-27, identike me elementin K0 6-10, domethënë të njëjtin numër si elementët e tillë K0 përmbahen në elementin K1 6-19. Më pas, funksioni VKQ i nivelit 0 kthen kontrollin me shenjën e vazhdimit të segmentit të funksionit VKQ të nivelit 1. Funksioni VKQ thërret funksionin VE0 të nivelit 0, i cili përcakton praninë e një K0 të ndryshuar -

elementi 27-32, identik me elementin K0 14-19. Kështu, përcaktohet K1-elementi 19-32,

identike me elementin K1 6-19. Më tej, funksioni i nivelit 1 VKQ nuk përcakton elementin tjetër K1, identik me elementin K1 6-19, sepse funksioni i nivelit 0 VE0 nuk përcakton elementin K1 të modifikuar, identik me elementin K1 6-19, duke filluar nga elementi b. 40-41, dhe kthen kontrollin e funksionit OK() të nivelit 2. Funksioni OK() i nivelit 2 thërret funksionin OE() të nivelit 1, i cili përcakton praninë e një elementi K1 të modifikuar 32-49, i përbërë nga Elementet K0 32-36, 36- 40,

40-44, 44-49. Më pas, përcaktohet elementi K2 6-49, formohet objekti i nivelit 3, përcaktohet elementi i modifikuar K2 49-79. Këta dy elementë K2 formojnë elementin K3 6-79. Kjo përfundon ndërtimin e segmentit, pasi elementët b 79-81 dhe 81-83 në vijim nuk formojnë një element K0,

identike me elementin K0 6-10, dhe funksioni i nivelit 0 VKQ nuk gjeneron një flamur vazhdimi

segment. Në sekuencën e elementeve b, zgjidhet një segment i vijës së drejtë dixhitale 6-79. Programi fillon përcaktimin e segmentit tjetër, duke filluar me elementin b 80-82.

b. gjetjet

1. Propozohet një algoritëm i ri për zgjedhjen e segmenteve të linjës në konturet e imazhit dhe një zbatim softuer jo i parëndësishëm i algoritmit, të cilat lejojnë marrjen e një zgjidhjeje të saktë për problemin e njohjes së kontureve të imazhit si sekuenca të segmenteve të linjës.

2. Zbatimi softuerik i algoritmit për zgjedhjen e segmenteve të linjës në konturet e imazhit bëhet duke përdorur mjete moderne programimi i orientuar nga objekti, i cili bëri të mundur që të mos vendoseshin kufizime të qarta në madhësinë e imazhit të përpunuar duke maksimizuar përdorimin e burimeve të kompjuterit të përdorur.

3. Në bazë të algoritmit të propozuar dhe zbatimit të tij softuerik, u mor një zgjidhje teorike dhe u kryen eksperimente për njohjen e harqeve të kthesave dixhitale dhe segmentimin e konturit të imazheve binare në një segment të vijave dixhitale dhe harqeve të kurbave dixhitale.

BIBLIOGRAFI

1. Kovalevsky V.A. Aplikimet e segmenteve të drejta dixhitale në kodimin ekonomik të imazhit, në punimet e seminarit ndërkombëtar të 7-të, DGCI"97, Montpellier. - Francë, 1997. - 3-5 dhjetor - F. 51-62.

2. Kalmykov V.G. Metoda strukturore për përshkrimin dhe njohjen e segmenteve të linjave dixhitale në konturet e imazheve binare // Piece Intellect. - 2002. - Nr 4. - C. 450-457.

3. Kalmykov V.G., Vishnevsky V.V. Analiza e kontureve të objekteve në imazhet binare // Makinat dhe sistemet matematikore. - 1997. - Nr. 2. - S. 68 - 71.

4. Kalmikov V.G. Harku i një kurbë dixhitale - përcaktimi dhe stanjacioni // Përpunimi i sinjalit dhe njohja dhe njohja e imazheve të imazheve. Punimet e Konferencës Ndërkombëtare Gjith-Ukrainase. - Kiev. - 2004. - 11 - 15 Zhovten.

Formulimi i problemit përcaktuar nga qëllimi dhe mundësitë e zbatimit të tij.

Synimi. Zhvilloni një program për klasifikimin e pjesëve drejtkëndore në cilësore dhe të dëmtuara.

Mundësitë për zbatimin e detyrës të përcaktuara nga aftësitë e kompjuterit. Një kompjuter është i aftë të përpunojë informacione numerike në një sekuencë algoritmike. Për të realizuar aftësitë e një kompjuteri, është e nevojshme të simuloni problemin që zgjidhet.

Modelimi duke përdorur një kompjuter nënkupton një kalim nga një objekt (botë) real në një përshkrim të koduar të vetive të tij duke përdorur të dhëna dhe operacione mbi to. Një tranzicion i tillë, si rregull, kryhet në disa faza:

Abstraksioni- përzgjedhja e veçorive më domethënëse të objektit për sa i përket detyrës.

Është e nevojshme të kryhen kërkime që ju lejojnë të kaloni nga objekti i modelimit në subjektin e modelimit, duke hedhur poshtë gjithçka të tepërt në përputhje me qëllimin në detyrë

Si ndryshon një drejtkëndësh nga katërkëndëshat e tjerë?

• Barazia e anëve të kundërta.
• Paralelizmi i anëve të kundërta.
• Barazia e diagonaleve.
• Të gjitha këndet janë të drejta.

Cili është numri minimal i veçorive që nevojiten për të zgjidhur në mënyrë unike problemin?

• Barazia e 2 brinjëve të kundërta + barazia e diagonaleve.
• Paralelizmi i 2 brinjëve të kundërta + barazia e diagonaleve.
• Tre qoshet janë të drejta.

Pra, falë abstraksionit, ne morëm një model informacioni verbal. Por, është ende e pakuptueshme për kompjuterin. Ai kupton modelin matematikor të paraqitur si algoritëm dhe të zbatuar në softuer.

Metodologjia për zbatimin e detyrës.

Një vizatim i një pjese cilësore (drejtkëndëshi) ose një pjese me defekt (katërkëndësh) bëhet nga segmentet (komandë LINE) në sistemin grafik AutoCAD dhe eksportohet në . Programi kntrs.lsp() lexon të dhënat e segmentit të linjës (koordinatat e kulmit) nga një skedar DXF dhe i shkruan ato në një skedar teksti vrtks.txt në rend të rrumbullakët.

Skedari i tekstit vrtks.txt mund të krijohet manualisht duke marrë koordinatat e kulmeve direkt nga vizatimi.

Programi i zhvilluar rct.lsp duhet të lexojë të dhënat nga skedari vrtks.txt, t'i analizojë ato dhe të nxjerrë në skedarin result.txt një regjistrim të përputhshmërisë së pjesës me kërkesat (drejtkëndësh ose jo).

Formalizimi i veçorive

Barazia e gjatësive të segmenteve (anët ose diagonalet): Gjatësia e secilit segment përcaktohet si hipotenuzë e një drejtkëndëshi drejtkëndësh (sipas teoremës së Pitagorës) përmes ndryshimit në koordinatat e segmenteve:

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

Paralelizmi i drejtëzave: K2=K1, ku për tëështë pjerrësia e vijës së drejtë K=(Y2-Y1)/(X2-X1)

Si të zyrtarizohet koncepti i "Këndit të drejtë"? Si pjesë e detyrës, prania e " kënd i drejtë» mund të përcaktohet në bazë të pingulitetit të segmenteve: K2= -1/K1, ku për tëështë pjerrësia e vijës së drejtë. K=(Y-Y0)/(X-X0).

Shfaqja e modelit në kompjuter

Çdo informacion shfaqet përfundimisht në një kompjuter duke përdorur numra (kode) binare në një model të brendshëm makine. Më parë, kodimi bëhej nga një programues. Tani shumica e programeve janë krijuar në gjuhë algoritmike.

Kur shikojmë një imazh dy-dimensional të një skene tredimensionale (në një foto, fotografi, ekran monitori), na duket se të gjitha objektet që mund t'i shihnim nëse e vëzhgonim drejtpërdrejt të njëjtën skenë në jetë janë drejtpërdrejt të pranishme. atje. Ndërkohë, gjithçka që na jepet në të vërtetë në një imazh dydimensional është fushë e dukshme, e cila është vetëm disa funksioni i shpërndarjes së shkëlqimit ose ngjyrat në një plan dydimensional: f(x, y) , ku x dhe y janë koordinata karteziane që përshkruajnë rrafshin e imazhit.

Për më tepër, nëse i afroheni ekranit të një monitori kompjuteri, mund të shihni se imazhi në ekran nuk është në të vërtetë i qetë dhe i vazhdueshëm, por është një "mozaik" diskret i përbërë nga drejtkëndësha individualë me ngjyra të rregulluar në një matricë të rregullt drejtkëndore. Ky është imazhi dixhital. Nga pikëpamja matematikore imazh dixhitalështë një matricë dydimensionale Im me madhësi (DimXDimY), ku x është një numër i plotë nga 0 në DimX– 1, duke përshkruar numrin e elementit në rreshtin e matricës, y është një numër i plotë nga 0 në DimY– 1, duke përshkruar rreshtin numri i matricës në të cilën ndodhet ky element. Në të njëjtën kohë, elementi i vetë imazhit dixhital (një qelizë e një matrice drejtkëndore) quhet piksel(piksel, element foto). Në rastin më të thjeshtë, çdo piksel Im ka një vlerë të plotë skalar në përpjesëtim me vlerën e funksionit të shpërndarjes së shkëlqimit f(x, y) në një pikë të caktuar në aeroplan.

Në fig. Në figurën 1.1.1, ana e majtë tregon një imazh të një fytyre femërore të përkthyer si imazh, ndërsa ana e djathtë tregon një fragment imazhi të zmadhuar të së njëjtës fytyrë (syri i djathtë), ku çdo element i imazhit ka vlerën e tij numerike të pikselit përkatës. Elementet e lehta të figurës korrespondojnë me b rreth Vlerat më të mëdha të matricës, të errëta - vlera më të vogla. Imazhi dixhital nuk përmban asnjë informacion tjetër.

@Rajs. 1.1.1 Imazhi dixhital si një matricë intensiteti dydimensionale

Duke filluar të studioni vizionin e makinës, është e nevojshme të kuptohet qartë se vetëm dhe ekskluzivisht një grup dy-dimensionale numrash të një formati ose një tjetër ruhet në një kompjuter si një imazh dixhital. Çdo e dhënë tjetër që dëshirojmë të nxjerrim nga imazhi (forma, vija, objekte, dimensione, përmbajtja e tekstit të shfaqur, etj., etj.) mund të merret vetëm si rezultat i aplikimit të një numri procedurash të përpunimit dhe analizës së imazhit. që ose duhet të programojmë vetë ose të përdorim procedura të gatshme të disponueshme në paketat e njohura softuerike të analizës së imazhit. Në të njëjtën kohë, për të zgjidhur probleme të thjeshta të vizionit kompjuterik fonde të gatshme ka të ngjarë të gjenden në bibliotekat standarde të procedurave të përpunimit të imazhit, për të zgjidhur probleme më komplekse do të jetë e nevojshme të kombinohen disa procedura të gatshme dhe për shumë detyra mjaft "të zakonshme" që vizioni "biologjik" i një personi, ai do të duket, zgjidh lehtësisht dhe pa mundim, vizioni i makinerive kompjuterike deri më tani nuk ka ende zgjidhje dhe ende vazhdon t'i kërkojë ato. Në fund të fundit, duke përdorur vizionin e tij natyror, një person lundron lehtësisht në çdo mjedis, njeh objekte, zgjedh një rrugë, drejton një makinë dhe shumë, shumë më tepër. Pse një kompjuter që merr një imazh nga një video kamera nuk mund t'i bëjë të gjitha këto? Ndoshta është struktura e syrit të njeriut?

Në fakt, syri i njeriut, si një videokamerë, formon vetëm një "fushë të dukshme", të ngjashme me një imazh dixhital. Në këtë rast, sistemi optik, i përbërë nga bebëza dhe thjerrëza, projekton një imazh dy-dimensional në retinë, ku qelizat fotosensitive ("shufra" dhe "kone") konvertojnë imazhin që rezulton në impulse nervore. Dhe vetëm pas kësaj, një mekanizëm kompleks për përpunimin e informacionit të marrë, që funksionon në departamentin përkatës të trurit tonë, i interpreton këto impulse si një imazh të skenës së dukshme që është e kuptueshme për ne. Kështu, tek njerëzit, funksioni i "vizionit" kryhet jo vetëm nga syri, por nga sistemi "sy + tru" ("sensori + kompjuter"). Janë algoritmet e përpunimit të informacionit të ndërtuara në tru që lejojnë një person të kuptojë atë që sheh. Roli i këtyre algoritmeve të integruara mund të ilustrohet me shembullin e mëposhtëm.

Kur, në mesin e shekullit të 20-të, kirurgët okulistë mësuan të kryenin operacione në thjerrëzat e syrit, shumë njerëz që ishin të verbër që nga lindja kishin aftësinë teknike për të parë qartë. Kjo do të thotë, pas një operacioni të tillë në një person që ishte deri tani i verbër (drita thjesht nuk kalonte përmes thjerrëzave), imazhi në retinë filloi të formohej dhe sinjalet përkatëse filluan të hyjnë në tru në të njëjtën mënyrë si ai. ndodh në njerëz të shëndetshëm. Fatkeqësisht, në këtë rast, "të shohësh dritën" nuk do të thotë "fillo të shohësh". Siç tregoi historia e mëvonshme, shumica e pacientëve të rritur "teknikisht të shkolluar" nuk kanë qenë kurrë në gjendje të arrijnë rezultate më domethënëse në fushën e shikimit sesa njohja e formave të thjeshta gjeometrike - madje kjo kërkonte përpjekje serioze të ndërgjegjshme prej tyre. Njohja e njerëzve nga fytyrat e tyre dhe orientimi në hapësirë ​​mbetën detyra dërrmuese për ta. Fakti është se ato mekanizma të integruar të analizës vizuale "automatike" që zhvillohen tek njerëzit në fëmijërinë e hershme nuk u zhvilluan në kohën e duhur tek këta pacientë dhe ata u gjendën në pozicionin e një kompjuteri që ka një pajisje për futjen e imazhit, por nuk ka softuerin e nevojshëm për analizën e tij.

Për të bindur përfundimisht veten për kompleksitetin e detyrës së analizimit të një imazhi që është një grup dydimensional i të dhënave numerike, ne do të përpiqemi ta vendosim veten në vendin e një programi kompjuterik që merret me numra abstraktë. Për ta bërë këtë, le të ndryshojmë mendërisht modalitetin e perceptimit të imazhit - ne do ta transferojmë atë nga zona vizuale në atë të prekshme. Le të imagjinojmë një grup vlerash dydimensionale të intensitetit si një tabelë shahu, madhësia e së cilës është e barabartë me madhësinë e figurës (DimXDimY), dhe një kolonë është mbërthyer në qendër të çdo qelize, lartësia e së cilës është proporcionale me vlerën e pikselit të imazhit përkatës. Me fjalë të tjera, konsideroni një imazh dy-dimensional si një lloj sipërfaqeje tre-dimensionale të kushtëzuara. Në fig. 1.1.2 në të majtë, një fragment i fytyrës së një femre është paraqitur si imazh, dhe në të djathtë është paraqitur si një reliev pseudo-tre-dimensionale.

@Rajs. 1.1.2. Imazhi dixhital si lehtësim pseudo-3D

Tani imagjinoni që, pa shikuar imazhin, duhet të ndjeni "lehtësimin" që i përgjigjet dhe të përpiqeni të përcaktoni se çfarë saktësisht përshkruan ky "lehtësim" - një shtëpi, një qen apo një sy njeriu? Siç tregojnë eksperimentet, një person mesatar nuk është në gjendje të përballojë një detyrë të tillë. Edhe njohja e formave më të thjeshta gjeometrike në një paraqitje të tillë "reliev" do të shoqërohet me përpjekje të konsiderueshme dhe do të kërkojë zhvillimin e ndërgjegjshëm të një aftësie të veçantë, strategjie dhe algoritmesh palpimi. I tillë, pavarësisht nga thjeshtësia në dukje e objektit "imazhi dixhital", është kompleksiteti i vërtetë i detyrave të kompjuterit dhe vizionit të makinës.