Hardware Reference
In-Depth Information
type
tPtrKlassFeld
is array
(natural
range
<>)
of
tKlassPkt;
Zu Beginn der Bearbeitung eines neuen Bildes ist jedes Feldelement mit einer
Konstanten für den Wert »leer« zu beschreiben:
constant
Pkt_leer: tKlassPkt:=(FNr1=>
0
, s1=>
'0'
, FNr2=>
0
,
s2=>
'0'
, Betrag =>
"0...0"
, i=>
0
, j=>
0
);
Bei einem Hardware-Sortierer ist es wichtig, die Anzahl der Blockspeicherzu-
griffe zu minimieren, da diese sequenziell erfolgen. Der in Abb. 5.18 skizzierte
Algorithmus verwendet dazu zwei Register, »RegL« für den aus dem Block-
speicher gelesenen Wert und »RegE« für den in den Blockspeicher einzusor-
tierenden Wert:
signal
RegL, RegE: tPktKlass;
Bei unserem speziellen Bubble-Sort wird für alle einzusortierenden Werte
nacheinander jedes Element im Sortierspeicher gelesen und mit dem einzu-
sortierenden Wert verglichen. Wenn der gelesene Wert kleiner ist, wird er in
das Feldelement davor kopiert. Anderenfalls, wenn er größer ist, wird der ein-
zusortierende Wert in das vorherige Feldelement und der gelesene Wert in das
Register für den einzusortierenden Wert kopiert. Beim ersten Einsortierschritt
für jeden neuen Datensatz hat das Feldelement, das gelesen wird, keinen Vor-
gänger, so dass der Datensatz für den Bildpunkt mit der geringeren Signifikanz
aus der Liste herausfällt.
0
1
2
4
Listenindex
KantensignifikanzdesBildpunktes
...
89 112 123
215
...
1
3
5
7
NummerdesBerechnungsschritts
2
i
4
6
8
Datensatzf¨alltausderListeheraus
RegL
89 112
123
215
RegL
RegERegistermiteinzusortierendemWert
RegistermitgelesenemWert
6
8
RegE
120 120 120
123
...
2 4
Abb. 5.18. Sortieren der klassifizierten Punkte
Jeder Sortierschritt benötigt eine Schreib- und eine Leseoperation, die
nacheinander ausgeführt werden müssen. Das Sortieren dauert folglich min-
destens 2 N
POI
Takte (N
POI
- Anzahl der zu berechnenden »interessanten«
Bildpunkte). Die Filteroperation benötigt für jeden Bildpunkt 25 Schritte. Da
das Sortieren offensichtlich mehr Zeit benötigt, ist es in Abschnitt 5.3.6 nicht
notwendig, während der Suche der beiden betragsmäßig größten Werte schon
mit der nächsten Filteroperation zu beginnen. Wenn die Filterberechnung und
die Klassifizierung nacheinander erfolgen, dauert das insgesamt etwa 40 Tak-
te. Diese Zeit genügt, um den zuvor klassifizierten Punkt in eine Liste mit
bis zu 20 Bildpunkt-Klassifikator-Tupeln einzusortieren. Die Listenlänge ist
