Prioritní fronta Meyerova algoritmu

Autor: handy
Přidáno: 2010-01-16 09:40:10

Lineárně spojovaný seznam s polem ukazatelů na diskrétní hodnoty

V popisu Meyerova algoritmu pro Watershed segmentaci je zmiňována nutnost vkládat hodnoty do prioritní fronty. Pojmem prioritní fronta se rozumí taková struktura, která umožňuje vkládání hodnoty na takovou pozici, aby posloupnost hodnot ve frontě zůstala seřazena, a vyjímání prvního prvku fronty.

Z výše uvedeného popisu je zřejmá výhodnost implementace nějaké z dynamických datových struktur, protože počet prvků ve frontě je velmi proměnný. Dále je, vzhledem k nutnosti udržovat data seřazená, vhodnější využít spojovaného seznamu spíš, než upravovat klasickou strukturu fronty. Data je třeba vyjímat pouze ze začátku fronty, a tedy postačí pouze lineárně spojovaný seznam.

Zde však opět nastává problém se seřazeností. Pro vložení na korektní pozici je třeba od prvního prvku seznamu procházet postupně prvky až k pozici, na který má být vkládaný prvek zařazen. Toto vyhledávání je však vzhledem k obrovskému množství hodnot, jež jsou během segmentace zpracovávány, zbytečně náročné a způsobuje výrazný nárůst složitosti.

Právě zde je uplatněno jednoduché vylepšení využívající faktu, že hodnoty vkládané do seznamu náleží konečné množině. Klasicky se při segmentaci obrazu jedná o jasové celočíselné hodnoty v intervalu <0,255>. Pokud bychom tedy vytvořili pole ukazatelů směrující na místa v lineárním spojovaném seznamu, na která náleží jednotlivé hodnoty z intervalu, bylo by možno vynechat celý postup vyhledávání pozice pro zařazení a hodnotu vložit přímo na místo určené konkrétním ukazatelem. Pochopitelně takový postup předpokládá nutnost udržovat pole ukazatelů aktuální, ale toho lze dosáhnout mnohem jednodušeji, než vyhledávání v seznamu.

Celá myšlenka je zjednodušeně vysvětlena na přiloženém obrázku, kde je znázorněn takto upravený seznam pro celé hodnoty z itervalu <1,5>. Jednotlivé ukazatele jsou nastaveny na místa v seznamu, na kterých, při zařazené příslušné hodnoty, bude zachována seřazenost seznamu. Pokud je nejnižší hodnota přítomná v seznamu vyšší, než nejnižší přípustná hodnota, jsou ukazatele na hodnoty.

Pro snadnější pochopení přikládám ještě kód v C++ s jednoduchou implementací takového seznamu.



Přidat komentář

Jméno:
Text:
Opsat:
Zpět