Algorithmen zur Bestimmung von Objekteigenschaften in konfigurierbarer Hardware

Kurzfassung

Die Arbeit untersucht die Entwicklung von Algorithmen zur Bestimmung von Objekteigenschaften in konfigurierbarer Hardware. Im Rahmen der Arbeit wurden zwei VHDL-Module entworfen: Ein Modul Labelling zum Cluster Labelling binarisierter Bilddaten und ein Modul Label_Moment zur Bestimmung von Umfang und Momenten bis zur zweiten Ordnung von Clustern in binarisierten Bilddaten.

Die Arbeit wurde in der Einrichtung Optische Informationssysteme (OS) des Deutschen Zentrums für Luft- und Raumfahrt (DLR) erstellt. Die Extraktion von nutzer-relevanten Informationen aus den Daten opto-elektronischer Systeme ist einer der zentralen Aufgabenbereiche der Einrichtung OS. Es werden dazu oft heterogene Systeme eingesetzt, bei denen Teile der Anwendung auf Standard-Prozessoren in Software prozessiert und Teile der Anwendung direkt in konfigurierbarer Hardware (FPGA) verarbeitet werden. Im OS wird ein VHDL-Betriebssystemkonzept zur Entwicklung von heterogener Systemen eingesetzt.

Die im Rahmen der Arbeit entwickelten Module wurden mit Hilfe dieses Konzepts entworfen. Sie stehen beliebigen Anwendung, welche mit Hilfe dieses Betriebssystemkonzepts entwickelt werden, als Bibliotheksmodule zur Verfügung.

Die Masterarbeit stellt die Ergebnisse der Entwicklung der implementierten VHDL-Entwürfe Labelling und Label_Moment dar. Insbesondere wird dabei Bezug auf das VHDL-Betriebssystem des DLR und die Umsetzung der Algorithmen in eine Hardwarebeschreibung genommen.

Danksagung

Ich möchte mich bei Prof. Dr.-Ing. Reinhard Eck als Erstprüfer und Prof. Dr. Rainer Rieckeheer als Zweitprüfer der Masterarbeit bedanken.

Mein besonderer Dank gilt Dr. David Krutz für die unermüdliche Unterstützung und Betreuung der Arbeit im DLR, Berlin-Adlershof. Ich bedanke mich bei den Mitarbeitern der Einrichtung Optische Systeme für ihre vielseitigen Hilfen und Kollegialität.

Inhaltsverzeichnis

  Abbildungsverzeichnis  v

1  Einleitung  1

1.1  Motivation  1

1.2  Aufgabenstellung  3

2  Das FPGA-Bildverarbeitungssystem  5

2.1  OIS-FPGA Karte  5

2.2  VHDL-Betriebsystem  6

2.2.1  Einführung  6

2.2.2  Datenkanäle  8

2.2.3  Strukturcompiler  14

2.2.4  Betriebssystemmodule  15

2.2.5  Bibliotheksmodule  16

3  Cluster Labelling binärer Bilddaten  17

3.1  Hoshen-Kopelman Algorithmus  18

4  Merkmalsextraktion  22

4.1  Formmerkmale  22

4.1.1  Fläche  22

4.1.2  Umfang  23

4.1.3  Rundheit  24

4.1.4  Flächenschwerpunkt  24

4.2  Momentenbasierte Merkmale  25

4.2.1  Definitionen  25

4.2.2  Hu-Momente  27

4.2.3  Momenten-Tensor  28

4.2.4  Aspekte der Umsetzung auf dem FPGA  30

iii

Inhaltsverzeichnis

5  Umsetzung der Algorithmen für das VHDL-Betriebssystem  35

5.1  Cluster Labelling  36

5.1.1  Problem der V-Konstellation  37

5.2  Momentenberechnung  40

5.3  Umfang  42

6  VHDL-Entwurf zum Labeln von Bildclustern  44

6.1  Labelling-Modul  46

6.1.1  PRE LABEL  48

6.1.2  SCHEDULER  50

6.1.3  DELAY  52

6.1.4  POST LABEL  53

7  VHDL-Entwurf zur Extraktion von Momenten  56

8  Test des VHDL-Entwurfs  62

8.1  Testanwendung  63

8.2  Simulation der Testanwendung  64

8.3  Ergebnisse der Testanwendung auf der Zielhardware  68

9  Zusammenfassung und Ausblick  73

  Literaturverzeichnis  75

  Glossar  76

iv

  Abbildungsverzeichnis  

  Bild 1 1 : Straßenkreuzung  2

  Bild 1 2 : Heterogenes Bildverarbeitungssystem  4

  Bild 2 1 : OIS6000x FPGA-Karte (KRUTZ 2006 )  6

  Bild 2 2 : Kommunikation im FPGA-Betriebssystem (KRUTZ 2006 )  8

  Bild 2 3 : Datenkanäle zweier Module  9

  Bild 2 5 : Struktur für SChannel Kommunikation  11

  Bild 2 6 : Struktur für Pipe-Kommunikation  12

  Bild 2 7 : Zustandsgraph für die Pipe-Kommunikation  13

  Bild 2 8 : Struktur einer portierungsunabhängigen HDL-Anwendung  15

  Bild 3 1 : Cluster Labelling Schema (FLEISCHMANN 2004 )  17

  Bild 3 2 : Vierernachbarschaft  19

  Bild 3 3 : Tabelle der Label nach dem Post-Labelling  20

  Bild 3 4 : Tabelle der Label vor dem Pre-Labelling  21

  Bild 4 1 : Verwendete Umfangsdefinition  23

  Bild 4 2 : Umfang eines Clusters mit einem Loch  23

  Bild 4 3 : Haupt- und Nebenachse  29

  Bild 4 4 : Hauptachsen des Trägheitstensors  30

  Bild 5 1 : Schema der HDL-Module  35

  Bild 5 2 : V-Konstellation  38

v

  Abbildungsverzeichnis  

  Bild 6 1 : Struktur der Komponente Labelling  44

  Bild 6 2 : Labelling-Module  46

  Bild 6 3 : VHDL-Code der Entity Labelling  47

  Bild 6 4 : Submodul PRE LABEL  48

  Bild 6 5 : Zeilenpuffer von PRE LABEL  48

  Bild 6 6 : Zustandsgraph für einen Labelkonflikt  49

  Bild 6 7 : Submodul SCHEDULER  50

  Bild 6 8 : Interne Struktur des Moduls Scheduler  51

  Bild 6 9 : Submodul DELAY  52

  Bild 6 10 : Submodul POST LABEL  53

  Bild 6 11 : Zustandsgraph des Post Label Moduls  54

  Bild 7 1 : VHDL-Modul Label Moment  56

  Bild 7 2 : VHDL-Code der Entity Label Moment  56

  Bild 7 3 : Datenwort der Ausgabe des Moduls Label Moment  57

  Bild 7 4 : Label-Tabelle des Moduls Label Moment  58

  Bild 7 5 : Ausschnitt aus dem Zustandsgraphen von Label Moment  59

  Bild 7 6 : Taktdomänen von Label Moment  61

  Bild 8 1 : Entwicklungsphasen  62

  Bild 8 2 : VHDL-Testanwendung  64

  Bild 8 3 : Ergebnisse der Simulation des Moduls Labelling  66

  Bild 8 4 : Ergebnisse der Simulation des Moduls Label Moment  67

  Bild 8 5 : Testanwendung für die Synthese  68

  Bild 8 6 : Eingangsdaten der Testanwendung  70

  Bild 8 7 : Ausgabebild des Moduls Labelling  71

  Bild 8 8 : Ausgabe des Moduls Label Moment  71

  Bild 8 9 : Darstellung der Ergebnisse von Labelling und Label Moment  72

vi

1 Einleitung

1.1 Motivation

Die großen Städte und Metropolregionen in Deutschland stehen vor der Herausforderung eines stetig wachsenden Verkehrsaufkommens. Bei der Lösung der damit verbundenen Probleme geht es nicht nur um die Befriedigung einer gesteigerten Nachfrage, vielmehr werden auch Image und Erfolg einer Stadt in der öffentlichen Wahrnehmung zunehmend von der Qualität der Verkehrserschließung und -abwicklung bestimmt.

Die Stadt Nürnberg als Kern der Metropolregion Nürnberg stellt ein typisches Beispiel für die gegenwärtige Situation in deutschen Großstädten dar. Im Nürnberger Stadtzentrum ist die Leistungsgrenze des Straßensystems bereits erreicht. Die steigenden Verkehrsmengen an den Einfallstraßen zwingen zu einer maßgeblichen Verlagerung auf den ÖPNV ¹ . Hierzu entstehen bis 2010 mehrere S-Bahnstrecken. Innerstädtische Verbesserungen erfolgen u.a. durch den Ausbau des U-Bahn- und Straßen- und Stadtbahnnetzes.

Zielsetzung der allgemeinen Nürnberger Verkehrsplanung ist die Bündelung des motorisierten Individualverkehrs auf dem Hauptverkehrsstraßennetz bei gleichzeitiger Verkehrsberuhigung in den Wohngebieten.

ORINOKO ² ist ein Verbundprojekt im Rahmen des Forschungsprogramms „Verkehrsmanagement 2010“ des Bundesministeriums für Bildung und Forschung, das aktuell in Nürnberg durchgeführt wird. Ziel des Projekts ist ein System zur kurz- und langfristigen Verkehrssteuerung in Ballungsräumen. ORINOKO hat drei Forschungsschwerpunkte.

¹ ÖPNV: Öffentlicher Personennahverkehr

² ORINOKO: Operative Integrierte und Optimierte Korridorsteuerung

1

Einleitung

Der erste Schwerpunkt ist die Erfassung des Verkehrs. Ein Teil der Erfassung erfolgt mittels Floating Car Data (SCHÄFER 2001) von Fahrzeugen des ÖPNV. Ein anderer Bereich der Verkehrsdetektion ist das Sammeln von Daten an signifikanten Kreuzungen mit Hilfe von Induktionsschleifen, Infrarotsensoren und videobasierten Systemen.

Der zweite Schwerpunkt liegt im Aufbau eines Datenverbunds. In ORINOKO sollen möglichst viele Quellen verkehrsrelevanter Daten zusammengeführt und in einer konsolidierten Datenbank für Steuerungs-, Informations- und Qualitätssicherungszwecke bereitgestellt werden.

Der dritte Schwerpunkt liegt auf der Steuerung von Lichtsignalanlagen. Dazu sollen Algorithmen entwickelt werden, die eine situationsabhängige Steuerung der Lichtsignalanlagen anhand der gesammelten Daten erlauben. (JUNG 2005)

Das Institut für Verkehrsforschung im Deutschen Zentrum für Luft- und Raumfahrt (DLR) setzt im Rahmen des Projekts ORINOKO ein System zur automatischen Erkennung von Verkehrsteilnehmern und zur Bewertung der Verkehrssituation von Echtzeit-Bildfolgen digitaler Kameras ein. Bild 1.1 zeigt eine Testszene für das System an der Kreuzung Regensburger Straße/Ben Gurion Ring.

Einleitung

Das DLR-System soll verkehrsrelevante Eigenschaften der Verkehrsteilnehmer bestimmen. Dazu gehören z.B. Typ, Position, Geschwindigkeit und Richtung des jeweiligen Verkehrsteilnehmers. Dieser Ansatz ermöglicht es, sowohl konventionelle Verkehrskenngrößen wie Verkehrsstärken und -dichten, als auch innovative Kenngrößen wie z.B. Geschwindigkeitsverteilungen und Spurwechselverhalten zu erheben. Die gewonnenen Daten können für verkehrsstatistische Zwecke, Verkehrsprognosen, für die mikroskopische Analyse der Verkehrsdynamik oder die Steuerung von Lichtsignalanlagen eingesetzt werden.

Für bestimmte rechenintensive oder echtzeitkritische Bildprozessierungsschritte des DLR-Verkehrserfassungssystems kommen FPGA ³ -basierte Bildverarbeitungskarten

zum Einsatz. Andere Bildverarbeitungsschritte dieses Systems werden mit konventionellen PC ⁴ durchgeführt. Zur Vereinfachung des Entwurfs signal-

verarbeitender Systeme in konfigurierbarer Hardware wird im DLR ein Betriebssystemkonzept (KRUTZ 2006) eingesetzt. Ziel der Masterarbeit ist die Entwicklung von Algorithmen zur Bestimmung von Objekteigenschaften in konfigurierbarer Hardware für dieses Betriebssystemkonzept.

1.2 Aufgabenstellung

Im DLR gibt es eine Vielzahl an Projekten, welche die Entwicklung heterogener Systeme zur Signalverarbeitung beinhalten. Solche Systeme ermöglichen es, zeitkritische oder rechenintensive Verarbeitungsschritte eines Systems von leistungsfähigen, konfigurierbaren Hardwarekomponenten wie FPGA prozessieren zu lassen. Der mögliche Aufbau eines solchen Systems ist in Bild 1.2 dargestellt.

³ FPGA: Field Programmable Gate Array

⁴ PC: Personal Computer

3

Einleitung

In vielen Projekten der Bildverarbeitung ist das Identifizieren von Objekten und die Extraktion bestimmter Merkmale, wie z.B. von Umfang oder Fläche eines Objekts notwendig. Diese Bildprozessierungsschritte sind sehr rechenintensiv bei gleichzeitig geringer Komplexität. Sie sind sehr gut für eine Implementierung in FPGA geeignet.

Im Rahmen der Arbeit sollen zwei Bildverarbeitungsmodule für FPGA entwickelt werden: Ein VHDL ⁵ -Entwurf zum Cluster Labelling binarisierter Bilddaten und ein

weiterer VHDL-Entwurf, welcher zu einem gelabelten Cluster den Umfang und so genannte Momente bis zur zweiten Ordnung extrahiert. Beide Bildverarbeitungskomponenten sollen sich in das im DLR eingesetzte Betriebsystemkonzept für konfigurierbare Hardware eingliedern und als Bibliotheksmodul des Betriebssystems verfügbar sein.

⁵ VHDL: Very High Speed Integrated Circuit Hardware Description Language

4

2 Das FPGA-Bildverarbeitungssystem

Im DLR werden in der Einrichtung Optische Informationssysteme (OS) in verschiedenen Projekten, die sich mit der Echtzeitanalyse von Bilddaten beschäftigen, FPGA-Karten verwendet. Die FPGA-Karten werden vor allem zum Bildeinzug von Kameras und der Echtzeit-Vorverarbeitung der aufgenommenen Bilddaten eingesetzt.

2.1 OIS-FPGA-Karte

Das DLR setzt verschiedene selbstentwickelte, FPGA-basierte Bildverarbeitungskarten ein. Im Rahmen des Projekts ORINOKO werden FPGA-Karten mit dem Namen OIS benutzt. Diese FPGA-Karten sind mit einer PCI ⁶ -Schnittstelle ausgestattet, die den Einsatz der Karten in Standard-PC erlaubt. Die Karten werden in verschiedenen Varianten genutzt. Aktuell werden die Karten OIS4000x mit einem Virtex2-4000 FPGA und die OIS6000x mit einem Virtex2-6000 FPGA des Herstellers Xilinx verwendet. Beide sind mit folgenden Komponenten ausgestattet, wie auch in Bild 2.1 dargestellt: Xilinx Virtex2 FPGA (4000, 6000) zwei CamLink Schnittstellen

PLX-PCI-Controller mit 128Kx32 FIFO als Kommunikationspuffer Ethernet PHY

Erweiterungskarte mit USB-Controller und 14xRS232

256 MB SDRAM zwei 16 MB SDRAM

4 MB Synchronous SRAM

16 LED für Status- und Debuganzeigen

Die Hardwareplattform der OIS-FPGA-Karten wird durch Integration weiterer Schnittstellen, erweiterten Speichers oder anderer FPGA-Bausteine, wie z.B. Virtex2-Pro, an verschiedenste Aufgaben anpasst. (KRUTZ 2006)

⁶ PCI: Peripheral Component Interconnect

5

Das FPGA-Bildverarbeitungssystem

2.2 VHDL-Betriebsystem

2.2.1 Einführung

Im DLR gibt es eine Vielzahl an Projekten aus den verschiedensten Anwendungsbereichen, welche die Entwicklung von heterogenen Systemen zur Signalverarbeitung beinhalten. Alle diese Projekte haben einen vergleichbaren Aufbau: Ein oder mehrere Sensorelemente mit entsprechender analoger Vorverarbeitung und Ansteuerung, einer digitalen Vorverarbeitung, bestehend aus einem oder mehreren FPGA sowie einem oder mehreren Prozessoren in Form eines DSP ⁷ oder im PC zur Endverarbeitung. Die

Heterogenität eines solchen Systems bezieht sich dabei sowohl auf das Vorhandensein von Hardware- und Softwarekomponenten, als auch auf die Verbindung von mechanischen, optischen und elektronischen Elementen sowie die Verknüpfung von analogen und digitalen Komponenten.

⁷ DSP: Digitaler Signalprozessor

6

Das FPGA-Bildverarbeitungssystem

Im Gegensatz zu einer reinen Prozessor- oder Hardwarelösung, kann ein heterogenes System optimal an eine Aufgabe angepasst werden. Prozessoren sind universell einsetzbar und programmierbar. Ihre Einbindung in ein Gesamtsystem ist jedoch sehr komplex, was sich besonders auf den erreichbaren Datendurchsatz eines solchen Systems auswirkt. Reine Hardwaresysteme besitzen diese Beschränkung nicht. Ihr Nachteil liegt in einer umfangreicheren und kostspieligeren Entwicklung. Die Verbindung eines Prozessorsystems mit einer Hardwarelösung kann die Vorteile beider Systeme vereinen.

Vorhandene Entwicklungswerkzeuge (z.B. Matlab ⁸ , Simulink ⁹ ) erlauben die Entwicklung und Beschreibung eines solchen Systems auf algorithmischer Ebene. Einen vollständigen Entwicklungsentwurf von der Algorithmusbeschreibung bis zu den Hardware- und Softwareprogrammen ermöglichen sie jedoch nicht. Derzeit bieten sie keine Möglichkeit Module auf die stark variierenden FPGA-Plattformen zu portieren.

Um den Entwicklungsaufwand und die Entwicklungszyklen für solche heterogenen Systeme zu reduzieren, wurde im DLR ein VHDL-Betriebsystem entwickelt. Es bildet eine Schicht zwischen der Funktionalität der Anwendung und der Implementierung auf der Hardware. Der Entwickler partitioniert die Anwendung in Teilalgorithmen, welche auf den verschiedenen Zielplattformen PC und FPGA ausgeführt werden sollen. Die Teilalgorithmen werden aus vorhandenen Bibliotheksmodulen für Hard- oder Software implementiert oder müssen für die entsprechende Zielplattform erstellt werden. Die hardwarespezifische Implementierung von Datenkanälen, die Ressourcenverwaltung des FPGA sowie die Verdrahtung der externen Logik mit dem FPGA wird vom Betriebssystem durchgeführt. Auf der PC-Seite wird vom Betriebssystem eine API ¹⁰ bereitgestellt, mit der auf die Kommunikations-Schnittstellen des Betriebssystems zugegriffen werden kann (siehe Bild 2.2). Die FPGA-API auf der PC-Seite und die FPGA-Betriebssystemschnittstellen auf der FPGA-Seite kapseln die Anwendung von der jeweiligen Zielplattform.

⁸ Matlab: Software des Herstellers The MathWorks zur Lösung mathematischer Probleme

⁹ Simulink: Software des Herstellers The MathWorks zur Modellierung von Systemen

¹⁰ API: Application Programming Interface

7

Das FPGA-Bildverarbeitungssystem

Das System definiert einheitliche Schnittstellen, die eine Wiederverwendung der Module in neuen Anwendungen und auf verschiedenen Zielplattformen erlauben. Die Schnittstellendefinition ist weiterhin unabhängig von der tatsächlichen Realisierung eines Datenkanals. Das Einbinden eines bestimmten Betriebssystemmoduls definiert z.B., ob Daten via USB ¹¹ , PCI oder Ethernet ¹² kommuniziert werden.

2.2.2 Datenkanäle

Das Betriebssystem sieht für den Transfer von Daten drei Formen der Kommunikation vor:

Channel-Kommunikation: asynchroner Datentransfer SChannel-Kommunikation: synchroner Transfer einzelner Datenworte Pipe-Kommunikation: synchroner Transfer von Datenblöcken

¹¹ USB: Universal Serial Bus

¹² Ethernet: Kabelgebundene Datennetztechnologie für lokale Datennetze

8

Das FPGA-Bildverarbeitungssystem

Die Kommunikationskanäle des Betriebsystems sind unidirektional. Daten werden von einem Modul-Output zu einem Modul-Input übertragen. Für eine bidirektionale Kommunikation zwischen zwei Modulen müssen zwei Kanäle implementiert werden, wie in Bild 2.3 dargestellt.

Kommunikationskanäle innerhalb der Zielplattform PC oder FPGA werden direkt umgesetzt. Man könnte sagen, dass diese Module direkt verdrahtet werden. Soll ein Datenkanal auf eine andere Zielplattform übergehen, d.h. vom PC zum FPGA oder umgekehrt, wird diese Aufgabe vom Betriebssystem übernommen. Datenkanälen wird neben ihrer Datenbreite eine eindeutige Identifikationsnummer (ID) zugewiesen. Die ID dient der Identifizierung der Datenkanäle auf den verschiedenen Zielplattformen. Das VHDL-Betriebssystem etabliert einen Datenkanal zwischen einem Modul-Output und einem Modul-Input gleicher ID. Für die physikalische Umsetzung eines solchen Kanals stehen verschiedene Betriebssystemmodule zur Verfügung. Mit Hilfe der Betriebssystemmodule kann ein Datenkanal zwischen PC und FPGA als USB-, PCI-oder z.B. Ethernet-Verbindung ausgeführt werden. (KRUTZ 2006)

9

Das FPGA-Bildverarbeitungssystem

Channels

Channels sind die einfachste Form eines Datenkanals im VHDL-Betriebssystem. Daten werden asynchron über ein Signal übertragen. Weitere Signale zur Signalflusssteuerung fehlen. Eine VHDL-Beschreibung der Channel Schnittstelle ist gegeben durch:

Channel-Output:

entity CHANNEL_OUTPUT generic(

);

port(

data: out std_logic_vector(WIDTH-1 DOWNTO 0) ); end;

Channel-Input:

entity CHANNEL_INPUT generic(

);

port(

data: in std_logic_vector(WIDTH-1 DOWNTO 0) ); end;

Zur eindeutigen Identifikation des Datenkanals wird mit dem Generic ID eine eindeutige Nummer zugewiesen. Der Generic WIDTH legt die Datenbreite des Datensignals fest. Mit dem Wert des Generic VALUE wird der Dateneingang eines Input-Channels initialisiert. (KRUTZ 2006)

SChannels

SChannels erlauben eine synchrone Kommunikation. Die Zeitdomänen von Sender und Empfänger können sich unterscheiden. Der Transfer von Daten muss an die Zeitdomäne des Empfängers angepasst werden. Die Synchronität der Kommunikation verlangt weiterhin, dass das Protokoll eine vollständige Übertragung der Daten vom Empfänger zum Sender garantiert. Alle Signale der SChannel-Schnittstelle beziehen sich auf den Takt, der mittels clock vom Sender der Daten vorgegeben wird. Mit dem Signal

10