Bereichswachstum

Für das Wachstum müssen Startpunkte gesetzt werden. Diese werden auch als ,,Saatpunkte``   s<sub>i</sub> oder ,,Keimpunkte`` bezeichnet. Von diesen Saatpunkten aus wächst das Gebiet in alle Raumrichtungen bzgl. der 6'er Nachbarschaft weiter. Dafür wird ein Grauwertintervall t=[t₁,t₂] vorgegeben. Das Bereichswachstum setzt sich dann nur in Gebieten fort, deren Grauwerte g im Intervall t liegen. Eine Vorstellung davon sollen die Skizzen in Abbildung und Abbildung auf Seite geben. Dabei ist s der Saatpunkt und n die Anzahl der Ebenen des 3D-Rechners.

 

 

In Abbildung wird gezeigt, wie das Wachstum fortschreitet, wenn ,,Trennwände'' eine geradlinige Ausbreitung verhindern. Trennwände sind Bereiche, deren Grauwerte nicht im Grauwertintervall t liegen. An solchen Trennwänden stopt das Bereichswachstum. Das geflutete Gebiet schlängelt sich dann um die Trennwände herum.

Als Bedingung für das Wachstum wird das Segmentationskriterium   eingeführt. Im folgenden wird nun eine iterative Formel entwickelt, mit der für jeden Smart-Pixel dessen Zugehörigkeit zum segmentierten Gebiet in einer Variablen $\sigma$(steht für [S]ignum) festgehalten werden kann.

Mit dem Segmentationskriterium wird festgelegt, wann ein SPPE $\pi\in\mathbf{\Pi}$ in das wachsende Gebiet $S \subseteq \mathbf{\Pi}$ (S steht für [S]egment) aufgenommen wird. Das ist dann der Fall, wenn einer seiner Nachbarn $\pi_{\nu}$ aus der 6'er Nachbarschaft schon in S aufgenommen wurde, und der Grauwert $g(\pi)$ im Schwellwertintervall liegt, also

$$\pi_{\nu} \in S \wedge g(\pi)\in t \Rightarrow \pi\in S$$ (3.1)

An einer ,,Trennwand'' mit Grauwerten, die außerhalb des vorgegebenen Intervalls t=[t₁,t₂] liegen, endet das Wachstum. Eine iterative Formel für das Wachstum erhält man mit der Ausgangsmenge S₀ und einer Iterationsvorschrift für S_i. Die Menge S₀ ist gerade die Menge der Saatpunkte $\{s_i\}$.

  $$\begin{gather} S_0 = \{ s_i \} \\ S_{i+1} = S_i \cup \{ \pi_{\nu} \in \mathbf... ..._{\nu} \in N_6(\pi) \wedge \pi \in S_i \wedge g(\pi_{\nu}) \in t\} \end{gather}$$
Betrachtet man das Wachstum aus der Sicht eines bereits in S aufgenommenen SPPE $\pi$, dann werden in seiner 6'er Nachbarschaft die SPPE aufgenommen, deren Grauwerte im Intervall t=[t₁,t₂] liegen. Für die noch folgende Darstellung von S_i mit $\sigma_i$ wird S_i+1 aus Sicht des SPPE $\pi$ umgeformt zu

$$S_{i+1} = S_i \cup \{ \pi\in\mathbf{\Pi}: \pi_{\nu}\in N_6(\pi) \wedge \pi_{\nu}\in S_i \wedge g(\pi)\in t \}$$ (3.2)

und wenn man S_i in die Mengenklammer hineinzieht

$$S_{i+1} = \{ \pi\in\mathbf{\Pi}: \pi \in S_i \vee ( \pi_{\nu}\in N_6(\pi) \wedge \pi_{\nu}\in S_i \wedge g(\pi)\in t ) \}$$ (3.3)

Saatpunkte, die in einer ,,Trennwand`` plaziert wurden, müssen noch aussortiert werden. Dafür wird $\pi\in S_i$erweitert zu $\pi\in S_i \wedge g(\pi)\in t$, so daß schließlich gilt:

$$S_{i+1} = \{ \pi\in\mathbf{\Pi}: ( \pi \in S_i \wedge g(\pi)... ...}\in N_6(\pi) \wedge \pi_{\nu}\in S_i \wedge g(\pi)\in t ) \}$$ (3.4)

Im Abschnitt zur Schwellwertbildung wurde die Binarisierung $\beta(g)$eingeführt, mit der hier $g(\pi)\in t$ geprüft wird. Statt nun jedes Element der Menge S_i explizit zu bestimmen, definiert man für das SPPE $\pi$ eine Funktion ${\sigma}(\pi)$ ($\sigma$ steht für [S]ignum). Mit ${\sigma}(\pi)$ wird die Zugehörigkeit von $\pi$zum Gebiet S_i im Schritt i iterativ feststellt:
$$\begin{align}{\sigma}_i(\pi) & = \begin{cases} 1: \pi\in S_i\\ 0: \text{sonst} \end{cases}\end{align}$$

Unter Verwendung von ${\sigma}(\pi)$ und $\beta(g)$ kann man S_i+1 umformulieren als:

 

$$\hspace{-1cm} {\sigma}_{i+1}(\pi) ( {\sigma}_i(\pi) \wedge \beta(g(\pi)) ) \vee \notag$$ = (3.5)

$$( {\sigma}_i(\pi_N) \vee {\sigma}_i(\pi_E) \vee {\sigma}_i(\pi_W)... ..._S) \vee {\sigma}_i(\pi_P) \vee {\sigma}_i(\pi_F)) \wedge \beta(g(\pi))) \notag$$ (3.6)

$$( {\sigma}_i(\pi) \vee {\sigma}_i(\pi_N) \vee {\sigma}_i(\pi_E) \... ...a}_i(\pi_S) \vee {\sigma}_i(\pi_P) \vee {\sigma}_i(\pi_F)) \wedge \beta(g(\pi))$$ = (3.7)

Das sieht kompliziert aus, heißt aber nur, daß mit ${\sigma}_i(\pi_{\nu})$ die Werte ${\sigma}_i(\pi)$ der benachbarten SPPE $\pi_{\nu}$ aus der 6'er Nachbarschaft per intra- bzw. interplanarer Kommunikation angefordert werden, und anschließend mit ${\sigma}_i(\pi)$ und $\beta(g(\pi))$ verknüpft werden.

Die Anfangsbedingung für ${\sigma}_i(\pi)$ wird von S₀ aus () abgeleitet. Es gilt $\forall \pi\in\Pi$
 $$\begin{align} {\sigma}_0(\pi) = \begin{cases} 1: \pi\in S_0\\ 0: \text{sonst} \end{cases}\end{align}$$
Mit S₀ wurde die Menge aller Saatpunkte bezeichnet. Das Setzen der Saatpunkte kann über den Vergleich jedes SPPE mit den Saatpunkten durchgeführt werden. Dafür sind in jedem SPPE die Saatpunkte bereitzustellen. Um festzustellen, ob $\pi=s_i$ gilt, werden die Koordinatenwerte von $\pi$ mit denen von s_i verglichen. Bei Übereinstimmung setzt man $\sigma_0(\pi)=1$. Für die Vergleiche der Koordinatenwerte braucht man den Befehl EQ mit

$$x\ \text{\bf EQ}\ y = \begin{cases} 1: & x=y \\ 0: & \text{sonst} \end{cases}$$ (3.8)

Bei mehreren Saatpunkten liegen die Koordinatenwerte als Array vor. Der Einfachheit halber wird nur 1 Saatpunkt betrachtet. Das kommt auch der Vorstellung entgegen, daß in einer späteren Realisierung von einem Benutzer die Saatpunkte interaktiv durch ,,Anklicken'' gesetzt werden. Unmittelbar nach dem Setzen des neuen Saatpunktes soll das dadurch geflutete Gebiet sichtbar sein. Das entspricht dem Fluten mit jeweils nur 1 Saatpunkt.

Die Koordinatenwerte des Saatpunktes werden jedem SPPE in den Registern SX, SY und SZ bereitgestellt. In X,Y und Z stehen die SPPE-Koordinaten. Für $\sigma_o(\pi)$ und ${\sigma}_i(\pi)$ wird das Register SI verwendet. Als Hilfsregister dient H. Alle Register enthalten ausschließlich Integer-Werte. Die Anfangsbedingung wird dann hergestellt durch

$$\begin{aligned} (1) \quad & & SI & \leftarrow X\ \text{\bf EQ... ...) \quad & & SI & \leftarrow SI\ \text{\bf AND}\ H \end{aligned}$$ (3.9)

Als Kommunikationsbefehl wurde im Abschnitt der SEND-Befehl vorgestellt. Die Beschaffung der Nachbarwerte ${\sigma}_i(\pi_{\nu})$ in () erfolgt deshalb durch Zusenden. Das Register SI wurde für ${\sigma}_i(\pi)$ verwendet. Für die Variable ${\sigma}_{i+1}(\pi)$ wird noch das Register SI1 eingeführt. Das Programm zur Iterationsgleichung () ist in () zu sehen.

$$\begin{aligned} (1) \quad & & IN & \leftarrow 0 \\ (2) \q... ...\quad & & SI1 & \leftarrow SI1\ \text{\bf AND}\ B \end{aligned}$$ (3.10)

In Zeile (1) wird das Empfangsregister initialisiert. Das ist einmal zu Beginn der Iteration notwendig, weil wegen der Randbedingung aus Abschnitt einige der SPPE keine Werte in diesem Register empfangen, und sonst undefinierte Werte enthalten können. Mit (5),(7),(9),(11),(13) und (15) werden die Nachbarwerte ${\sigma}_i(\pi_{\nu})$ im Register IN angefordert. Durch die OR-Verknüpfungen der Werte in (6),(8),(10),(12),(14) und (16) wird das SPPE $\pi$ nur dann ins Gebiet S_i aufgenommen, falls einer seiner Nachbarn oder $\pi$ selbst schon dazugehört. In (2)-(4) wird der Test $g(\pi)\in t$ mit der Binarisierung $\beta(g(\pi))$ von () durchgeführt. Die Zeile stammen von (). Das Ergebnis steht im Register B und zeigt an, ob das SPPE $\pi$ in einer Trennwand liegt oder nicht. Mit der UND-Verknüpfung in (17) wird das Wachstum an Trennwänden aufgehalten.

Durch das Bereichswachstum werden zusammenhängende Gebiete,   d.h. Segmente,   gebildet. Im folgenden wird eine Zustandsbeschreibung sowohl des noch wachsenden Gebietes als auch des segmentierten Gebietes gegeben. Dazu werden folgende Definitionen eingeführt.

Definition 6   Eine Folge $(\pi_1,\dots,\pi_n)$ von SPPE $\pi_i\in S$ mit $S\subseteq\Pi$ heißt Weg (oder Pfad) in S, wenn aufeinanderfolgende SPPE bzgl. der 6'er Nachbarschaft benachbart sind. Die Folge $(\pi_1)$ ist auch ein Weg. Es gilt

$$(\pi_1,\dots,\pi_n) \text{ ist Weg in } S \Leftrightarrow_{df... ...in\mathbb{N} : 1\le i<n \Rightarrow \pi_i\in N_6(\pi_{i+1}))$$ (3.11)

 

Definition 7   Zwei SPPE $\pi_1, \pi_2\in S$ heißen bzgl. S verbunden, falls es einen Weg $(\pi_1,\dots,\pi_n)$ von $\pi_1$ nach $\pi_2$ in $S\subseteq\Pi$ gibt, d.h.

$$\pi_1, \pi_2\in S \text{ verbunden } \Leftrightarrow_{df} \exists \text{Weg }(\pi_1,\dots,\pi_2) \text{ in } S$$ (3.12)

 

Definition 8   Die Menge $S\subseteq\Pi$ heißt zusammenhängendes Gebiet oder Segment, falls 2 beliebige SPPE $\pi_1, \pi_2\in S$ miteinander verbunden sind.  

Für ein segmentiertes bzw. geflutetes Gebiet S gilt dann, daß alle SPPE $\pi\in S$ einen Grauwert $g(\pi)$ haben, der innerhalb des Intervalls t=[t₁,t₂] liegt, d.h. $g(\pi)\in t$.