Hledání úseček a kružnic s využitím Houghovy transformace při zpracování obrazu v LabView

Jaroslav Vlach

Při zpracování obrazové informace se používá množství metod, jejichž základy byly po­loženy již koncem 50. let minulého století a jejichž rozvoj nastal zejména v posledních 25 letech. V tomto článku jsou uvedeny některé metody a postupy zpracování obrazu se­jmutého kamerou. Pro příklad je uvedena realizace těchto algoritmů s použitím nástrojů programového prostředí LabView. Článek volně navazuje na [10].

There are a lot of methods used for image processing. Their grounds were found in the end of 50th years and have been developed particularly in the last 25 years. In this ar­ticle, some methods for processing of images taken by camera are explained. As exam­ple, implementation of these algorithms with using of LabView tool is described. The article follows freely [10].

1. Úvod

Při zpracování obrazové informace v prů­myslu se nejčastěji pracuje s dvourozměrnou projekcí obrazu snímané reality a jeho in­terpretací v podobě obrazové funkce f(x, y). Každý prvek o souřadnici (x, y) nese informa­ci o jednom diskrétním prvku obrazu – pixe­lu (z angl. picture element). S určitou mírou zjednodušení budou v dalším popisu uvažo­vány scény nasnímané jasovou interpretací, takže každý prvek obrazu je popsán funkč­ní hodnotou obrazové funkce f(x, y) ve tva­ru celého čísla, které vyjadřuje velikost jasu. Množinu funkčních hodnot obrazové funkce lze pak vyjádřit dvourozměrným polem – ma­ticí, s níž lze dále pracovat pomocí matema­tických funkcí pro práci s maticemi.

Při zpracování obrazu se pracuje s funk­cemi a nástroji umožňujícími s dostatečnou přesností a rychlostí vykonat potřebné opera­ce s obrazovou funkcí f(x, y). Základní ope­race jsou např. prahování, hledání hran, fil­trace nebo vyhlazení. Cílem práce je použít takovou operaci, s jejíž pomocí je dosaženo požadované nebo hledané vlastnosti obrazu.

Často se při práci s obrazem pracuje jen v ur­čité vybrané oblasti obrazu, ve specifikovaném okolí zvoleného bodu (např. 4-okolí, 8-okolí, okolí 3 × 3 apod.) nebo s ohraničenou oblastí zájmu – ROI (z angl. Region Of Interest).

2. Segmentace

Segmentace je jedním z nejdůležitějších kroků analýzy obrazu. Jde o postup, kterým se v obraze vybere určitá část chápaná jako objekt. Obraz se tedy rozdělí do částí, které korespondují s konkrétními objekty v obraze. Informaci o rozdělení obrazu do jednotlivých segmentů využívají algoritmy zpracování ob­razu, které se snaží porozumět obsahu obrazu.

Pro segmentaci obrazu existuje mnoho segmentačních algoritmů. Nejpou­žívanější (a nejnázornější) jsou me­tody založené na prahování (angl. threshold). Příkladem je prahová­ní podle úrovně jasu, které patří k nejjednodušším a také nejstar­ším segmentačním metodám. Pra­hování je funkce, která transfor­muje vstupní obraz f na výstupní binární obraz g podle rozhodova­cího vztahu:

g(i, j) = 1 pro f(i, j) ≥ T

g(i, j) = 0 pro f(i, j) < T (1)

kde T je prahová hodnota (práh).

Jestliže g(i, j) = 1, bod (i, j) je obrazovým prvkem objektu, a jestliže g(i, j) = 0, obrazo­vým prvkem je pozadí.

Kromě metod prahování lze pro segmen­taci obrazu dále využívat metody založené na detekci významných hran v obraze (angl. edge-based). Lokální hrany jsou detekovány pomocí hranových detektorů na základě roz­dílu hodnot jasu sousedních bodů (pixelů). Hranový detektor je algoritmus, který vyhle­dává množinu hran (bodů, pixelů) v obraze.

Dalšími metodami jsou metody založe­né na hledání oblastí v obraze (angl. region-based). Jestliže lze identifikovat hrany, měly by tyto teoreticky ohraničovat oblasti. Kontu­ry oblastí však mohou být porušené, nemusí ohraničovat celou oblast. Není také zaručeno, že hranice oblastí nalezené metodou detekce hran budou stejné jako ty nalezené metodou hledání oblasti. Pro složitější úlohy segmen­tace lze použít další metody založené na sta­tistické analýze obrazových dat, tzv. znalost­ní metody (angl. knowledge-based), a další.

V reálných obrazech je často třeba praco­vat s liniemi, které jsou přerušeny (z důvodu šumu, po prahování nebo detekci hran apod.). V těchto případech je třeba použít metody, které si umějí poradit s chybějícími pixely.

Jednou z používaných metod pro hledání jednoduchých útvarů, jako je úsečka, elipsa či kružnice, je Houghova transformace. Prin­cip metody publikoval P. V. C. Hough v roce 1959 a patentoval ji v roce 1962; v roce 1972 zobecněnou metodu publikovali R. O. Duda a P. E. Hart [3]. Významné použití této trans­formace je při analýze textu, kdy lze s její po­mocí nalézt řádek textu v obraze.

Úlohu pro Houghovu transformaci je mož­né formulovat jako hledání takové podmnoži­ny bodů v obraze, která co nejvíce odpovídá části přímky – úsečce. Přímka s vyznačený­mi body A, B a C je znázorněna na obr. 1a. Každý bod na přímce je popsán dvěma sou­řadnicemi, např. A = (x 1 , y 1 ). Rovnice přím­ky se vyjádří v polárních sou­řadnicích:

r = x cos φ + y sin φ (2)

kde

r je délka normály od přímky k počátku souřadnic,

φ úhel mezi normálou a osou x.

Je patrné, že pro bod A přejde z rovnice (2) na tvar:

r = x 1 cos φ + y 1 sin φ (3)

Podobné vztahy je možné vyjádřit i pro další body B a C na přímce. Poté, po zobra­zení křivek popisujících jednotlivé body A, B a C v souřadné soustavě (φ, r) se zjistí, že se protínají v jednom bodě o souřadnicích (φ´, r´), jak je znázorněno na obr. 1b.

Obvykle se Houghova transformace im­plementuje tak, že obraz se diskretizuje v ras­tru M × N. Každý prvek tohoto prostoru bude pak tvořen dvojicí souřadnic (φ i , r j ), kde i = 1, 2… M a j = 1, 2… N. Algoritmus Houg­hovy transformace pro hledání linie v obraze lze popsat např. takto:

vstupem je binární obraz f, zajímají nás hodnoty obrazové funkce f(x k , y k ) = 1, kte­rých je celkem K, vytvoříme pole A o velikosti M × N (budeme mu říkat akumulátor) a na počátku je vynu­lujeme: A(φ i , r j ) = 0 pro všechna i = 1, 2… M a j = 1, 2… N (zvolíme vhodné dělení, např. φ i = i Π/M, r j = j(r max - r min )/N ), nastavíme počítadlo j = 1, nastavíme počítadlo i = 1, pro každý pixel (x k , y k ), kde k = 1, 2... K, jehož hodnota jasu f(x k , y k ) = 1, vypočte­me hodnotu: r j = x k cos φ i + y k sin φ i , inkrementujeme hodnotu v akumulátoru: A´(φ i , r j ) = A(φ i , r j ) + 1, opakujeme pro všechna další i = 2... M od kroku 5, opakujeme pro všechna další j = 2… N od kroku 4, nyní, po průchodu celým obrazem jsou v akumulátoru A(φ i , r j ) hodnoty n ij , kte­ré určují počet nalezených bodů ležících na přímce dané parametry (φ i , r j ), největší hodnota n ij (tj. maximum všech hodnot) určuje parametry (φ i , r j ) přímky, na které se nachází nejvíce bodů v obraze.

Obdobný postup lze modifikovat pro hle­dání parametrů hranic objektů, které je mož­né popsat analytickou rovnicí. Příkladem je hledání kružnice popsané rovnicí:

(x – a)2 + (y – b)2 = R 2 (4)

Každý bod na kružnici o poloměru R a se středem v bodě (a, b) lze popsat podle obr. 2 souřadnicemi:

x = a + R cos φ

y = b + R sin φ (5)

Bude-li se v obraze hledat bod ležící na kružnici s daným poloměrem R, vypočí­tá se tedy jeho souřadnice a zjistí se hodnoty parametrů a a b podle vztahu:

a = x – R cos φ

b = y – R sin φ (6)

Všechny body se stejnou hodnotou para­metrů a a b budou pak ležet na dané kružnici.

Mějme nyní obraz diskretizován v rast­ru M × N, každý prvek tohoto prostoru bude tvořen dvojicí souřadnic (x i , y j ), kde i = 1, 2… M a j = 1, 2… N. Algoritmus Houghovy transformace pro hledání kružnice v obraze lze popsat např. takto:

vstupem je binární obraz f, zajímají nás hodnoty obrazové funkce f(x k , y k ) = 1, kte­rých je celkem K, zvolíme hodnotu R poloměru hledané kružnice, vytvoříme pole A o velikosti M × N (bu­deme mu říkat akumulátor) a na počátku je vynulujeme: A(x i , y j ) = 0 pro všechna i = 1, 2… M a j = 1, 2… N, nastavíme počítadlo j = 1, nastavíme počítadlo i = 1, nastavíme φ m = 0, pro každý pixel (x k , y k ), kde k = 1, 2… K, jehož hodnota jasu f(x k , y k ) = 1, vypočte­me hodnoty a a b: a = x k – R cos φ m , b = y k – R sin φm, jestliže bude logický výraz (a > 0) & (a < M) & (b > 0) & (b < N) = 1, inkrementu­jeme hodnotu v akumulátoru: A´(a, b) = A(a, b) + 1, opakujeme pro všechna φ m do hodnoty 2ω od kroku 7, opakujeme pro všechna další i = 2… M od kroku 6, opakujeme pro všechna další j = 2… N od kroku 5, nyní, po průchodu celým obrazem jsou v akumulátoru A(x i , y j ) hodnoty n ij , které určují počet nalezených kružnic se středem v bodě (x i , y j ) o poloměru R, největší hodnota n ij (tj. maximum všech hodnot) je středem hledané kružnice v ob­raze.

Lze tušit, že pro dosažení vysoké míry úspěšnosti bude zřejmě záležet na vhodné úpravě vstupního obrazu (resp. vstupní ob­razové funkce f), která v již uvedených al­goritmech není řešena. Významným krokem je prahování (viz vztah (1)) a dalším hledání hran v obraze. Nejčastějšími metodami pro detekci hran jsou:

metody založené na hledání maxim prv­ních derivací pomocí operátorů (Robert­sův, Prewittové, Sobelův), významným ná­strojem pro aplikaci těchto metod je kon­voluce,

metody založené na hledání průchodu dru­hých derivací nulou, angl. zero-crossing – ZC, příkladem je Marrův-Hildrethové ope­rátor a Cannyho hranový detektor,

metody založené na lokální aproximaci ob­razové funkce parametrickým modelem, např. polynomem dvou proměnných (Ha­ralick).

V roce 1980 zveřejnil David Marr spo­lečně s Ellen Hildrethovou [6] teorii popisu­jící matematický model detekce skokových hran při neurofyziologickém měření na sít­nici oka. Základem teorie je hledání polohy hrany v obraze v místě průchodu druhé deri­vace obrazové funkce nulou. První derivace obrazové funkce má v místě hrany své lokální maximum, druhá derivace v místě hrany pro­tíná nulovou hodnotu (odtud zero-crossing).

Významné místo mezi moderními meto­dami hledání hran v obraze zaujímá Canny­ho hranový detektor, který publikoval John Canny v roce 1986 [1]. Není bez zajímavos­ti, že tato práce vznikla na stejném pracovišti jako Marrova teorie. Základní myšlenkou je představa, že skokovou hranu lze hledat filt­rem (hledání nejlepší impulzní funkce filtru).

Detektor je optimální pro skokové hrany, když jsou splněna tři kritéria:

detekční kritérium – významné hrany ne­smí být přehlédnuty a na jednu hranu by neměly být vícenásobné odezvy,

lokalizační kritérium – rozdíl mezi skuteč­nou a nalezenou polohou hrany má být mi­nimální,

požadavek jedné odezvy – detektor nesmí reagovat na jednu hranu v obraze vícená­sobně pro zašuměné a nehladké hrany.

Principem Cannyho hranového detektoru je syntéza z odezev detektoru v různých mě­řítkách. Algoritmus lze potom popsat např. v bodech:

najdi přibližné směry gradientu, pro každý pixel najdi derivaci ve směru gradientu pomocí „optimální“ masky spo­jující vyhlazení a derivaci, najdi lokální maxima těchto derivací, hranové body získej prahováním s hysterezí, proveď syntézu hran získaných pro různě velká vyhlazení (málokdy se používá).

Řešení konkrétní úlohy zpracování obrazu je možné obvykle rozdělit do tří základních kroků (viz obr. 3): vstupní obraz je podroben předzpracování (např. diskretizace, prahování), následně segmentaci (hledání oblastí a objek­tů v obraze) a nakonec vlastnímu rozpozná­vání obrazu. Pro každou část lze použít ně­kolik metod, algoritmů a konkrétních předem vytvořených postupů v daném programovém prostředí. Vždy je však třeba počítat s tím, že každá úloha může mít své specifické vlastnos­ti, které vedou k množství změn, úprav a do­ladění konkrétních postupů a algoritmů. Jinak se bude přistupovat k úloze počítání objektů v obraze, jinak k úloze posuzování shody tva­ru se vzorem (angl. pattern matching), jinak k úloze měření rozměru snímaného objektu v jednom směru, jinak k úloze měření ve více směrech a jinak k úloze posuzování povrcho­vých či podpovrchových vlastností objektu v obraze. Ukazuje se také, že velmi důležitou problematikou je optimální nasvícení scény.

3. Ukázky řešení v prostředí LabView

Nyní pro názornost uveďme příklad řeše­ní některých úloh v programovém prostředí LabView. Pro zájemce je zde odkaz na pub­likaci [9] seznamující se základy programo­vání v tomto prostředí.

V první úloze se bude ve vstupním obraze hledat úsečka. Program realizuje algoritmus Houghovy transformace pro hledání linie. Pro jednoduchost se bude vstupní obraz (jde o še­dotónový obraz s osmibitovým rozlišením, kde hodnota 0 odpovídá černé a hodnota 255 bílé barvě pixelu) upravovat pouze prahováním, což nemusí vždy vést k dobrému výsledku. Na obr. 4a je vstupní obraz a na obr. 4b ob­raz po prahování s prahovou hodnotou T = 35. Na obr. 4c je znázorněno promítnutí akumulá­toru A(φ i , r j ) do roviny (φ, r). Poznamenejme, že oproti obr. 1d se počátek souřadného sys­tému nachází vlevo nahoře (osa φ je zde oto­čena o 180°). Na obr. 4d je znázorněn obraz po prahování s vloženou úsečkou nalezenou za použití Houghovy transformace.

Řešení v prostředí LabView je graficky velmi podobné jednotlivým krokům z obr. 3. Zde bude předpokládáno, že vstupní obraz je již diskretizován do šedotónové podoby. Dále byla pro názornost použita segmentace praho­váním podle předpisu podle vztahu (1). Vlast­ní rozpoznávání v uváděném případě realizuje algoritmus Houghovy transformace (obr. 5).

V další úloze je úkolem ve vstupním obra­ze nalézt kružnici daného poloměru. V tomto případě je realizován algoritmus Houghovy transformace pro hledání kružnice. Opět se bude pracovat se vstupním obrazem s osmibi­tovým šedotónovým rozlišením, který se bude segmentovat prahováním. Na obr. 6a je uve­den vstupní obraz, na obr. 6b obraz po praho­vání s prahovou hodnotou T = 35 a na obr. 6c je obraz s vloženou nalezenou kružnicí (se zvolenou hodnotou R = 29).

Při realizaci v prostředí LabView bude opět předpokládáno, že vstupní obraz je již diskretizován do šedotónové podoby a rovněž se bude segmentovat prahováním. Vlastní roz­poznávání v uváděném případě realizuje al­goritmus Houghovy transformace pro hledá­ní kružnice o poloměru R (obr. 7).

4. Závěr

Hlavním cílem článku bylo seznámit čte­náře s použitím Houghovy transformace v praxi a s její realizací v prostředí LabView. V přiloženém seznamu odkazů lze získat dal­ší informace a podněty k práci.

Literatura:

[1] CANNY, J.: A Computational Approach to Edge Detection. In: IEEE Trans. Pattern Analysis and Machine Intelligence, 1986, s. 679–698. Dostupné na < >.

[2] DOBEŠ, M.: Zpracování obrazu a algoritmy v C#. BEN Praha, 2008, ISBN 978-80-7300-233-6.

[3] DUDA, R. O. – HART, P. E.: Use of the Hough Transformation to Detect Lines and Curves in Pictures. In: Comm. ACM, January, 1972, Vol. 15, s. 1–15. Dostupné na < >.

[4] HLAVÁČ, V. – ŠONKA, M.: Počítačové vidě­ní. GRADA, Praha, 1992.

[5] HLAVÁČ, V. – SEDLÁČEK, M.: Zpracování signálů a obrazu. Skripta FEL ČVUT, Praha, 2007, ISBN 978-80-01-03110-0.

[6] MARR, D. – HILDRETH, E.: Theory of Edge Detection. Proceedings of the Royal Society of London. Series B, Biological Sciences, Feb. 29, 1980, Vol. 207, No. 1167, s. 187–217. Dostupné na < >.

[7] SONKA, M. – HLAVAC, V. – BOYLE, R.: Image Processing, Analysis, and Machine Vision. Thomson Learning, Toronto 2008. Dostupné na < > (odkaz na části staršího vydání).

[8] VLACH, J.: Začínáme s LabView. Sdělovací technika, 4/2008, s. 20–21, ISSN 0035-9942.

[9] VLACH, J. a kol.: Začínáme s LabView. BEN Praha, 2008, ISBN 978-80-7300-245-9.

[10] VLACH, J.: Základy zpracování obrazu v pro-středí LabView. Automatizace, 52, č. 1, s. 40–41, ISSN 0005-125X.

Webové odkazy:

National Instruments – odkaz <

Ing. Jaroslav Vlach

Obr. 1. K výkladu Houghovy transformace pro hledání úsečky

Obr. 2. K výkladu Houghovy transformace pro hledání kružnice

Obr. 3. Základní kroky zpracování obrazu

Obr. 4. Příklad Houghovy transformace pro hle­dání linie: a) původní vstupní obraz, b) vstupní obraz po prahování (T = 35), c) promítnutí akumulátoru A(φ i j ) do , r roviny (φ, r), d) obraz po prahování s vloženou nalezenou úsečkou

Obr. 5. Algoritmus Houghovy transformace pro hledání úsečky v prostředí LabView

Obr. 6. Příklad Houghovy transformace pro hledání kružnice: a) původní vstupní obraz, b) obraz po prahování (T = 35), c) obraz po pra­hování s vloženou nalezenou kružnicí (R = 29)

Obr. 7. Algoritmus Houghovy transformace pro hledání kružnice o poloměru R