Embedded implementatie van optical flow voor independent motion segmentation

Departement Industriële Wetenschappen

Master in de industriële wetenschappen: Elektronica-ICT afstudeerrichting ICT

Embedded implementatie van optical flow voor independent motion segmentation

Masterproef voorgedragen tot het behalen van de beroepstitel van industrieel ingenieur.

Academiejaar 2010-2011

Door:

Lorenz Van den Heuvel

Promotor hogeschool:

Ing. Kristof Van Beeck

Promotor bedrijf:

Ing. Kristof Van Beeck

Woord vooraf Dit eindwerk is een onderdeel van de opleiding Industrieel Ingenieur Elektronica - ICT optie ICT aan de Hogeschool Lessius Mechelen - Campus De Nayer. Dit eindwerk is uitgevoerd in opdracht van de Embedded & Applied Vision Engineering groep, EAVISE. Ik wil iedereen bedanken die dit eindwerk mogelijk heeft gemaakt. Ik wil hierbij in het bijzonder mijn promotor Kristof Van Beeck bedanken die mij bijgestaan heeft gedurende dit eindwerk, en Toon Goedem´e van de EAVISE onderzoekscel. Tot slot wil ik mijn ouders nog bedanken die het mogelijk gemaakt hebben dat ik deze opleiding heb kunnen volgen.

Lorenz Van den Heuvel

Nederlands abstract Titel: Embedded implementatie van optical flow voor independent motion segmentation Situering Masterproef: Onderdeel van de onderzoekscel Embedded and Applied Vision Engineering (EAVISE), gevestigd op de Hogeschool Lessius Mechelen - Campus De Nayer. Doel Masterproef: Het doel van dit eindwerk bestaat uit 3 delen: het uitvoeren van een onderzoek naar de huidige stand in zake optical flow technieken, de implementatie van een optical flow techniek op een embedded systeem en tot slot trachten een versnelling van het algoritme te realiseren door een gedeelte van dit algoritme in hardware te implementeren. De eerste doelstelling bestaat erin een grondig onderzoek uit te voeren naar de huidige stand in zake optical flow. Hiermee wordt bedoeld te onderzoeken wat optical flow juist is, welke technieken er bestaan om optical flow te berekenen, en op basis van een vergelijkende studie een optical flow algoritme te kiezen dat we implementeren op een embedded platform. We zijn begonnen met een diepgaande literatuurstudie naar optical flow en zijn op zoek gegaan naar bronnen die optical flow technieken met elkaar vergelijken. Na deze vergelijkende studie uit gevoerd te hebben, hebben we gekozen om het Camus algoritme te implementeren. De tweede doelstelling bestaat erin om het gekozen algoritme te implementeren op een embedded platform, namelijk de Virtex 5 ML507. Een eerste stap daar naartoe was het implementeren van het Camus algoritme in software, geschreven in de programmeertaal C. De derde doelstelling was het versnellen van het Camus algoritme. Hiervoor hebben we een deel van het algoritme, het correlatie criteria, in hardware ge¨ımplementeerd.

I

II

English abstract Title: Embedded implementation of optical flow for independent motion segmentation Thesis Location: Part of the research group Embedded and Applied Vision Engineering (EAVISE), located at the university college Lessius Mechelen - Campus De Nayer. Thesis Goal: The goal of this thesis consists out of three parts: a thorough literature study regarding optical flow, the implementation of an optical flow algorithm on an embedded platform and finally realizing a speed-up by an implementation of part of the algorithm in hardware. The first goal consists out of an in-depth investigation of optical flow. What optical flow is, which techniques there are to calculate optical flow and, based upon a comparison of optical flow techniques, we will chose an algorithm to implement on an embedded platform. We started with a detailed literature study which described optical flow and started looking for papers which compared the different techniques. After this comparison we chose to implement the Camus algorithm on an embedded platform. The second goal was the implementation of the Camus algorithm on an embedded platform. The embedded platform we used was the Xilinx Virtex 5 ML507. A first step was the implementation of the Camus algorithm in software using the C programming language. The third goal was to accomplish a speed-up of the Camus algorithm. Therefore we implemented part of the algorithm, the correlation criteria, in hardware.

III

IV

Short summary Introduction The goal of this thesis was to research optical flow and implement an optical flow algorithm on an embedded platform. Optical flow is a vector representation of the displacement of a pixel between consecutive frames. Optical flow has a lot of applications like motion estimation, object tracking and so on. There are a lot of different techniques available to calculate optical flow. Each technique has its advantages and disadvantages. The main problem is the speed versus accuracy trade-off that exists, optical flow is very computationally expensive. This is the reason why we want to implement an optical flow algorithm on an embedded platform to achieve a speed-up.

The Camus algorithm We started researching the different techniques which exists to determine the optical flow field and came to the conclusion that there are 4 major groups: differential, correlation, phase and energy based techniques. We started looking at the different characteristics of these techniques and compared them based on speed, accuracy and robustness against noise. Based on these characteristics we chose the Camus correlation technique as the ideal algorithm to implement on the embedded platform. The algorithm produces reasonable accurate results, and has a good time complexity. Correlation-based techniques use neighborhoods, which are a collection of connected pixels in a frame. Usually this neighborhood has a square shape. Correlation-based techniques compare neighborhoods from frame 1 with neighborhoods from frame 2 and search for the best match over different displacements of that neighborhood. Camus also uses past frames to find the best match. This way we can reduce the size of the displacement (by looking at the past frames) and achieve a better time complexity.

V

Embedded platform The embedded platform we used in this master thesis is the Xilinx Virtex 5 ML507 Evaluation Platform. This platform consists of a PowerPC440 and a Virtex 5 FPGA. We are capable of combining software, which runs on the PowerPC, with hardware designs. The PowerPC is clocked at 400MHz. The Virtex 5 is also capable of communicating with a host PC using an RS-232 connection. Other features of the Virtex 5 are CompactFlash interface and the external DDR2 SDRAM.

Embedded project The embedded project consist of multiple hardware blocks, a PowerPC and the Processor Local Bus to connect the different components with each other. We have implemented the Camus correlation algorithm in software on the embedded platform and we have implemented part of the algorithm in hardware. The software implementation is written in C. The different C-files are compiled into object files and are then combined in an executable file that can be run on the embedded platform. The process of combining, called linking, is done using a linker script. In this linker script we defined what size the stack, heap and other section have and where they are placed in the memory: either in BlockRAM or in DDR2 SDRAM. Also noted in the linker script is the boot address of the system. The hardware implementation is build up around a Finite State Machine. An FSM is a machine that consists out of a finite number of states, outputs and transition conditions. We have created an FSM with 3 states that calculates the Sum Of Absolute Differences. We created an Intellectual Property (IP) with a number of registers which can be read and written from and to in software using C-functions. The initial problem was that we could not write to a register in hardware, but only read from it, so we had to adapt the original functions, thereby creating 2 kinds of registers. The first ones are both read- and writable in software but only readable in hardware. The latter are only readable in software but read- and writable in hardware. The PowerPC has a separate instruction and data cache, which can be activated independently. Cache is a small and fast memory that is located between the CPU and the main memory. This is used to store data or instructions recently used by the CPU, so the next time the CPU needs them they are immediately available and the CPU doesn’t need to copy them from slower main memory. This delivers an increase in performance of the CPU. These caches are enabled by VI

functions provided by Xilinx. The usage of these caches gave a tremendous boost in performance when enabled in our project. The FGPA is configurable in different ways. We used the Xilinx Microprocessor Debugger to generate an ACE file that can be downloaded to a CompactFlash card. This CompactFlash card is then connected to the FPGA and using the DIP switches we can chose which ACE file has to be loaded into the FPGA. An ACE file consist out of an .elf file and a .bit file. The Executable and Linkable Format is the result of the different C-files when compiled and linked together. The .bit file contains the configuration of the hardware.

Results By implementing a part of the Camus algorithm in hardware, the correlation criteria, we realized a reduction of 3.47 microseconds opposed to the software version without using cache. This reduction is partly undone by the numerous memory transfers we had to do for transferring the data from software to the hardware registers. When we enabled the cache of the PowerPC, the time needed to calculate the correlation criteria reduced to 0.23 microseconds. This is still more than the 0.03 microseconds needed to calculate the correlation criteria in hardware. But the memory transfers needed for the hardware version makes the hardware version slower when the cache is enabled.

Conclusion We have done a thorough research and comparison of optical flow techniques based on accuracy and speed criteria. We have then chosen the ideal algorithm to implement on an embedded platform. This implementation of the chosen Camus algorithm was successful. We were able to calculate the optical flow and used different techniques to achieve a speed-up. We created our own intellectually property and used the available cache of the PowerPC to increase the speed of the algorithm.

VII

VIII

Inhoudsopgave Woord vooraf Nederlands abstract

I

English abstract

III

Short Summary

V

1 Inleiding

1

1.1

Situering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Optical flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Camus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Embedded systeem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.5

Overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

2 Optical Flow

5

2.1

Wat is optical flow ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Toepassingen van optical flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.3

Problemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3 Optical flow berekenen

9

3.1

Aanname . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2

Technieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.3

3.2.1

Differentie technieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.2.2

Correlatie technieken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2.3

Energie gebaseerde technieken . . . . . . . . . . . . . . . . . . . . . . . .

16

3.2.4

Fase gebaseerde technieken . . . . . . . . . . . . . . . . . . . . . . . . . .

18

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

IX

4 Optical flow technieken vergelijken

19

4.1

Co¨effici¨enten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.2

Vergelijken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

4.2.1

Accuraatheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

4.2.2

Snelheid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

4.2.3

Ruis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.3

5 Het Camus algoritme

27

5.1

Inleiding

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

5.2

Camus correlatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

5.3

Camus problemen

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.3.1

Temporele aperture probleem . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.3.2

Temporele aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

5.3.3

Temporele oclussie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

5.4

Parallellisatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

5.5

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

6 Embedded systeem 6.1

37

Inleiding op FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

6.1.1

Logische Blokken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

6.1.2

Input/Output Blokken . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

6.1.3

Interconnecties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

6.2

Virtex-5 Evaluation Platform ML507 bord . . . . . . . . . . . . . . . . . . . . . .

40

6.3

Aansluitingen van de Virtex 5 ML507 . . . . . . . . . . . . . . . . . . . . . . . .

43

6.4

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

7 Embedded project

47

7.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

7.2

Overzicht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

7.3

Software implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

7.3.1

PowerPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

7.3.2

Software linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

7.3.3

C-bestanden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

7.4

Hardware implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

7.5

Configuratie van de FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

7.6

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

8 Resultaten en Conclusie 8.1

61

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . X

61

8.2

Gebruikte resources

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

8.3

Resultaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

62

8.4

Conclusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

Bijlagen

75

A Paper Rome

75

B Embedded systeem overzicht

81

C Afbeeldingen

83

D C-Functies

85

XI

XII

Lijst van afkortingen UCF User Constraint File XPS Xilinx Platform Studio FPGA Field-Programmable Gate Array IOB Input/Output Block CLB Configurable Logic Block LUT Look-up Table ELF Executable and Linkable Format DCM Digital Clock Manager DLL Delay-Locked Loop FAT File Allocation Table PLB Processor Local Bus LED Light Emitting Diode BRAM Block Random-Access Memory UART Universal Asynchronous Receiver/Transmitter DDR2 SDRAM Double Data Rate Synchronous Dynamic Random-Access Memory

XIII

CF CompactFlash VHDL VHSIC hardware description language VHSIC Very High Speed Integrated Circuit FSM Finite-state Machine OFCE Optical Flow Constraint Equation CPU Central Processing Unit ICC Instruction Cache Controller DCC Data Cache Controller IP Intellectual Property XMD Xilinx Microprocessor Debugger PC Personal Computer DMA Direct Memory Access SAD Sum of Absolute Differences SSD Sum of Squared Differences ACE Advanced Configuration Environment DIP Dual in-line Package

XIV

Lijst van figuren 1.1

(a) Dode hoek van een vrachtwagen. (b) Dodehoekcamera.

. . . . . . . . . . . .

2

1.2

Testbeelden van de dodehoekcamera. . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3

Optical flow veld voor Yosemite sequentie. . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Camus correlatie: zoektocht in tijd en ruimte. . . . . . . . . . . . . . . . . . . . .

4

2.1

Optical flow veld voor Yosemite sequentie. . . . . . . . . . . . . . . . . . . . . . .

5

2.2

Verschil tussen motion en optical flow veld. . . . . . . . . . . . . . . . . . . . . .

6

2.3

Schijnbare beweging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4

Aperture probleem [19] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

3.1

Correlatie methode [2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3.2

Energie gebaseerde techniek [25] . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

3.3

Reichardt correlator [25] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.1

Square2 sequentie [4]

21

4.2

Yosemite sequentie met motion veld [4]

. . . . . . . . . . . . . . . . . . . . . . .

21

4.3

Relatieve performantie van elk algoritme voor een complexe sequentie [18] . . . .

23

4.4

Resultaten voor accuraatheid van de hoek en grootte voor een re¨ele sequentie [25]. 24

4.5

2-D performantie diagrammen [16] . . . . . . . . . . . . . . . . . . . . . . . . . .

25

4.6

Invloed van ruis op prestaties [25] . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

5.1

Zoekgebied voor een pixel A. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

5.2

Rigide-body veronderstelling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

5.4

Kwadratische toename van het zoekoppervlak. . . . . . . . . . . . . . . . . . . .

30

5.5

Visualisatie van de verplaatsing van Afbeelding t-1 naar Afbeelding t. . . . . . .

31

5.6

Visualisatie van de verplaatsing van Afbeelding t-2 naar Afbeelding t. . . . . . .

32

5.7

2-dimensionale zoektocht in zowel tijd als oppervlakte. . . . . . . . . . . . . . . .

32

5.8

Temporele aperture probleem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

XV

5.9

Temporele aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

5.10 Temporele occlusie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

5.11 Parallellisatie door middel van de afbeelding op te splitsen in kleinere stukken. .

35

6.1

Architectuur van een FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

6.2

Architectuur van logisch blok . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

6.3

Architectuur van het Input/Output blok . . . . . . . . . . . . . . . . . . . . . . .

39

6.4

Architectuur van de switch box . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

6.5

Virtex-5 Evaluation Platform ML507 bord . . . . . . . . . . . . . . . . . . . . . .

40

6.6

(a)CLB (b) Virtex-5 Slice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

6.7

Virtex-5 Block RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

6.8

Virtex-5 Blokdiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

7.1

High-level blokdiagram van het complete embedded project. . . . . . . . . . . . .

48

7.2

Het complete embedded project zoals voorgesteld in Xilinx Platform Studio (XPS). 49

7.3

PLB bus verbindt de verschillende hardware componenten met elkaar. . . . . . .

49

7.4

Processor Local Bus (PLB) blok diagram. . . . . . . . . . . . . . . . . . . . . . .

50

7.5

Cache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

7.6

PowerPC 440 blok diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

7.7

Van C naar uitvoerbaar bestand. . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

7.8

Het gebruikte linkerscript. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

7.9

Correlatie criteria wordt in hardware ge¨ımplementeerd. . . . . . . . . . . . . . . .

56

7.10 Blokdiagram van de gecre¨eerde correlatie hardware blok. . . . . . . . . . . . . . .

57

7.11 (a)Register is 32 bit groot. (b) Hoe wij het register hebben ingevuld. . . . . . . .

58

7.12 Finite-state machine (FSM) ge¨ımplementeerd in hardware. . . . . . . . . . . . . .

59

8.1

De tijd nodig voor de berekening van het correlatie criteria zonder cache. . . . .

63

8.2

De tijd nodig voor de berekening van het correlatie criteria met cache. . . . . . .

63

8.3

Grafische voorstelling van de gegevens in tabel 8.2 voor de software. . . . . . . .

66

8.4

Grafische voorstelling van de gegevens in tabel 8.2voor de hardware. . . . . . . .

66

8.5

Grafische voorstelling van de gegevens in tabel 8.3. . . . . . . . . . . . . . . . . .

67

XVI

Lijst van tabellen 4.1

Resultaten voor Square2 [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.2

Resultaten voor Yosemite [4] . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

6.1

Specificaties van de Xilinx Virtex 5 ML507 FX70T . . . . . . . . . . . . . . . . .

41

6.2

Configuratie mogelijkheden van een 36Kbit en een 18Kbit RAM

. . . . . . . . .

42

7.1

De adressen van het embedded project (grootte in bytes)

. . . . . . . . . . . . .

50

7.2

Verschillende secties van een programma . . . . . . . . . . . . . . . . . . . . . . .

53

8.1

Gebruikte resources van de FPGA. . . . . . . . . . . . . . . . . . . . . . . . . . .

61

8.2

Resultaten voor Camus uitgevoerd op de FPGA in seconden. . . . . . . . . . . .

64

8.3

Vergelijking van PC versus FPGA in seconden. . . . . . . . . . . . . . . . . . . .

65

XVII

XVIII

Hoofdstuk 1

Inleiding Het doel van dit eindwerk bestaat uit 3 delen: een literatuurstudie naar optical flow technieken, het implementeren van een hieruit gekozen optical flow algoritme in een embedded systeem en het versnellen van dit algoritme d.m.v. een hardware implementatie. Het eerste doel bestaat uit een literatuurstudie in verband met optical flow. Wat optical flow is, welke technieken er zijn om optical flow te berekenen en een vergelijkende studie uit te voeren. Om op basis daarvan een algoritme te kiezen dat het beste resultaat zal opleveren wanneer het ge¨ımplementeerd wordt in een FPGA. Dit laatste is dan de tweede doelstelling, het gekozen algoritme implementeren op een embedded platform. We hebben hiervoor het Xilinx Virtex 5 ML507 gekozen. De laatste doelstelling bestaat er dan in om het gekozen algoritme te versnellen door middel van een gedeeltelijke hardware implementatie. Dit hoofdstuk start met een situering van de masterproef in sectie 1.1 gevolgd door een korte introductie van optical flow in sectie 1.2. Het gekozen Camus algoritme wordt beschreven in sectie 1.3. In sectie 1.4 wordt het platform voorgesteld waarop we het optical flow algoritme implementeren en tot slot wordt er in sectie 1.5 een overzicht van de thesis gegeven.

1.1

Situering

Deze masterproef is een onderdeel van een doctoraat dat wordt uitgevoerd aan de EAVISE onderzoeksgroep. Het doctoraat genaamd ”The active blind spot camera: hard real-time recognition of moving objects from a moving camera”heeft als doel het verminderen van het aantal dodehoek ongevallen met vrachtwagens. Onderzoek toont aan dat er jaarlijks in de Europse Unie meer dan 1300 doden vallen door deze dode hoek ongevallen [1]. In dit doctoraat wordt onderzoek gedaan om automatisch in de dodehoekcamera beelden (figuur 1.1(a) en figuur 1.1(b)) zwakke weggebruikers te detecteren, en dan automatisch een alarm te genereren. Figuur 1.2 geeft een voorbeeld van zo’n dodehoekcamera beelden. Bestaande dode hoek systemen, zoals de verplichte dodehoekspiegel, worden vaak niet of niet correct gebruikt. Actieve systemen, zoals bijvoorbeeld ultrasone detectoren, kunnen geen onder-

2

Inleiding

Figuur 1.1: (a) Dode hoek van een vrachtwagen. (b) Dodehoekcamera bevestigd op een vrachtwagen.

Figuur 1.2: Testbeelden van de dodehoekcamera.

scheid maken tussen statische objecten en zwakke weggebruikers. Zij geven bijvoorbeeld ook een alarm wanneer er een verkeersbord in de dode hoek aanwezig is. Hierdoor kan het systeem vaak als storend worden ervaren en gaat de vrachtwagenbestuurder dit systeem eerder uitschakelen. In deze toepassing bewegen zowel de camera als de te detecteren objecten (de zwakke weggebruikers). Hierdoor hebben we een zeer dynamische achtergrond, en kunnen standaard technieken zoals background substraction niet gebruikt worden. Er is dus nood aan een meer geavanceerde techniek voor het segmenteren en detecteren van de zwakke weggebruikers. Een mogelijke manier is om gebruik te maken van independent motion segmentation, gebaseerd op optical flow. Motion segmentation gaat objecten segmenteren door gebruik te maken van het feit dat deze objecten een beweging vertonen die verschillende is van de beweging van de achtergrond. Om deze beweging te bepalen maken we gebruik van optical flow vectoren. Hiervoor hebben we een real-time optical flow implementatie nodig, dat in deze masterproef wordt uitgewerkt.

1.2

Optical flow

Optical flow geeft de verplaatsing van elke pixel weer tussen 2 opeenvolgende frames door middel van een vector veld. In essentie geeft optical flow de projectie weer van de echte 3D beweging op een 2D afbeeldingsvlak. Een voorbeeld van een optical flow veld is voorgesteld in figuur 1.3. Een inleiding op optical flow

1.3 Camus

3

(a)

(b)

(c)

Figuur 1.3: (a)en(b) zijn 2 frames uit de Yosemite sequentie. (c)Optical flow veld voor (a)en(b) [4]

is gegeven in hoofdstuk 2, gevolgd door een overzicht van de verschillende methodes om optical flow te berekenen in hoofdstuk 3. De bedoeling is de verschillende optical flow technieken met elkaar te vergelijken en op basis van deze vergelijking een geschikt algoritme te kiezen om te implementeren in hardware. Deze vergelijkende studie wordt uitgevoerd in hoofdstuk 4.

1.3

Camus

Het Camus correlatie algoritme is in hoofdstuk 4 gekozen na de verschillende technieken vergeleken te hebben. Het Camus algoritme is een correlatie gebaseerd optical flow algoritme. Dit wil zeggen dat er een window, ook genaamd patch of mask, van een afbeelding op tijdstip t zal vergeleken worden met een window van een afbeelding op tijdstip t − 1. Er wordt dus gekeken naar de waarde van de pixels in een window op 2 verschillende tijdstippen. Men gaat dan opzoek naar het window op tijdstip t − 1 dat het best overeenkomt met het window op tijdstip t. Wat Camus hier aan toevoegd is dat er gezocht kan worden zowel in de ruimte als in de tijd, zoals voorgesteld in figuur 1.4. We gaan dus opzoek naar de beste overeenkomst tussen de windows in de tijd en in de ruimte. In hoofdstuk 5 wordt er dieper ingegaan op het Camus algoritme en wat mogelijke problemen zijn wanneer men dit implementeert in hardware.

1.4

Embedded systeem

Een embedded systeem is een elektronisch systeem dat zowel hardware als een processor bevat. Het is een combinatie van configureerbare logische elementen, zoals een FPGA of CPLD, en een of meer hard- of softcoreprocessoren. Daarnaast heeft het embedded platform ook nog

4

Inleiding

Figuur 1.4: Camus correlatie: zoektocht in tijd en ruimte.

andere periferie zoals DDR2 SDRAM geheugen, CompactFlash slot en een UART connectie om communicatie te voorzien. Een FPGA bevat configureerbare logische componenten, ook wel logische blokken genoemd, en interconnecties die volledig configureerbaar zijn. Door middel van de juiste connecties te maken kunnen we de verschillende logische blokken met elkaar verbinden om zo specifieke taken te laten uitvoeren. Een uitgebreidere uitleg over FPGA’s wordt geven in hoofdstuk 6.

1.5

Overzicht

In hoofdstuk 2 wordt optical flow uitgelegd en verklaard wat mogelijke applicaties zijn. De verschillende technieken om optical flow te berekenen worden besproken in hoofdstuk 3 en de vergelijking van deze verschillende technieken is terug te vinden in hoofdstuk 4. De gekozen Camus correlatie techniek wordt in detail bekeken in hoofdstuk 5. In hoofdstuk 6 is het embedded systeem, de Virtex 5 ML507 besproken, en geven we een korte beschrijving over FPGA’s in het algemeen. In hoofdstuk 7 wordt het totale embedded project besproken: zowel de software als de hardware kant van het ontwerp wordt uitgelegd. Tot slot worden in hoofdstuk 8 de resultaten besproken en een conclusie genomen.

Hoofdstuk 2

Optical Flow In dit hoofdstuk wordt een inleiding op optical flow gegeven. We beginnen met de definitie van optical flow in sectie 2.1 te geven. Verder wordt er in sectie 2.2 uitgelegd welke toepassingen er bestaan. Tot slot wordt in sectie 2.3 besproken welke problemen er kunnen opduiken bij het berekenen van optical flow.

2.1

Wat is optical flow ?

Optical flow geeft de verplaatsing van elke pixel weer tussen 2 opeenvolgende frames door middel van een vector veld. Optical flow cre¨eert dus een 2D vector veld op basis van beweging van pixels tussen 2 frames.

(a)

(b)

(c)

Figuur 2.1: (a)en(b) zijn 2 frames uit de Yosemite sequentie. (c)Optical flow veld voor (a)en(b) [4]

6

Optical Flow

Figuur 2.1(a) en 2.1(b) zijn 2 frames van de Yosemite sequentie. Door middel van optical flow wordt nu een vector veld opgesteld, dat aangeeft waar elke pixel van figuur 2.1(a) naartoe is in figuur 2.1(b). Dit vector veld, het optical flow veld genaamd, wordt voorgesteld in 2.1(c).

(a)

(b)

(c)

Figuur 2.2: In (b)en(c) wordt respectievelijk het motion veld en het optical flow veld voorgesteld voor figuur (a) [21].

Het ultieme doel van optical flow is het benaderen van het echte motion veld. Het motion veld is een exacte voorstelling van een 3D beweging zoals het geprojecteerd is op een camera afbeelding. In ideale gevallen is het optical flow veld gelijk aan het motion veld, maar zoals we kunnen zien in figuur 2.2 is dit niet altijd correct. In figuur 2.2(a) wordt een barbierspaal tegenwijzerzin rond zijn as gedraaid. Deze beweging wordt voorgesteld in het motion veld (figuur 2.2(b)) door middel van vectoren die van links naar rechts wijzen, dit wil zeggen dat de pixels van links naar rechts zijn verplaatst. Het optical flow veld (figuur 2.2(c)) daarentegen geeft aan dat de pixels naar boven zijn verplaatst. De reden dat het optical flow veld en het motion veld niet gelijk zijn is omdat er een verschil is tussen een beweging en een schijnbare beweging. Als een object geen textuur heeft (egaal gekleurd is en een glad oppervlak heeft) zoals de rode bal in figuur 2.3, dan kunnen we geen accuraat optical flow veld opstellen. In figuur 2.3 links beweegt de rode bol rond zijn as. Er is dus een beweging waar te nemen, namelijk een rotatie, maar in het optical flow veld kunnen we deze beweging niet terug vinden. Optical flow kan dus alleen ogenschijnlijke beweging voorstelling, vandaar het verschil tussen het optical flow veld en het motion veld. In figuur 2.3 rechts beweegt de bol niet, maar de belichting verandert. De belichtingsbron beweegt, met als gevolg dat we in het optical flow veld een beweging terugvinden. We nemen aan dat het optical flow veld gelijk is aan het motion veld behalve in speciale gevallen [25].

2.2

Toepassingen van optical flow

Optical flow heeft een breed gamma aan toepassingen in de beeldverwerkende sector namelijk: object herkenning, segmentatie, . . . . Het cre¨eren van het optical flow veld is meestal niet het

2.3 Problemen

7

Figuur 2.3: Schijnbare beweging

eind doel. Optical flow wordt vaak gebruikt om een beweging uit een reeks van beelden te halen. Zoals in [11] waar men door middel van optical flow handbewegingen wil gaan herkennen. In [12] gaat men optical flow technieken gebruiken voor medische doeleinden, namelijk het herkennen van endocardial oppervlakken in 3D-structuren. Ook in deze masterproef is het berekenen van optical flow niet het einddoel, maar willen we gebruik gaan maken van optical flow om zwakke weggebruikers te detecteren in een reeks beelden.

2.3

Problemen

In sectie 2.1 hebben we al aangehaald dat het optical flow veld niet voor elke situatie gelijk is aan het motion veld en hebben we in figuren 2.2 en 2.3 al enkele voorbeelden gegeven waarvoor er problemen kunnen optreden. Een ander vaak voorkomend probleem is het aperture probleem. In figuur 2.4(a) is een vlak met diagonale lijnen te zien door een opening (aperture). In figuur 2.4(b) is dit zelfde vlak verschoven naar links, over 5 pixels. In figuur 2.4(c) is dit zelfde vlak naar boven verschoven over een afstand van 6 pixels. Er is geen verschil op te merken tussen afbeeldingen 2.4 (a), (b) en (c) in de opening, nochtans heeft er in elke foto een andere beweging plaats gevonden, namelijk naar links of naar boven. We kunnen dus geen exacte beweging waarnemen ten gevolge van de opening. Het is dan ook onmogelijk om deze beweging terug te vinden in het optical flow veld, terwijl het motion veld dus wel een beweging bevat. Dit probleem heet het aperture probleem, waarbij wij geen accuraat optical flow veld kunnen opstellen ten gevolge van het feit dat we kijken door een opening (aperture) [25].

(a) Origineel

(b) 5 pixels naar links

(c) 6 pixels omhoog

Figuur 2.4: Aperture probleem [19]

8

Optical Flow

Hoofdstuk 3

Optical flow berekenen Allereerst wordt er in sectie 3.1 de Optical flow constraint equation verklaart. In sectie 3.2 wordt een overzicht gegeven van de verschillende bestaande optical flow technieken en wordt er dieper ingegaan op het technisch aspect van elk type techniek. In sectie 3.3 bevindt zich de conclusie.

3.1

Aanname

De meeste optical flow technieken starten met de aanname dat een pixel dezelfde intensiteitswaarde behoudt bij een beweging voor minstens een korte tijdsperiode. Hiermee wordt bedoeld dat de intensiteitswaarde van een pixel tussen 2 opeenvolgende frames niet verandert. Dit wordt als volgt uitgedrukt: I(x, y, t) = I(x + dx, y + dy, t + dt)

(3.1)

Vergelijking (3.1), geeft weer dat de pixel op plaats (x,y,t) intensiteit I(x, y, t) heeft. Wanneer we de intensiteit bekijken nadat we ze verplaatsen in zowel de x,y richting als in het t-domein krijgen we I(x + dx, y + dy, t + dt). Als we op vergelijking (3.1) de Taylor expansie uitvoeren en de hogere orde termen verwaarlozen, krijgen we de volgende vergelijking: Ix u + Iy v + It = 0

(3.2)

dy Waar (u, v) staat voor de optical flow vectoren ( dx dt , dt ) en Ix u + Iy v + It de afgeleiden van in-

tensiteit op co¨ ordinaat (x,y,t). Deze aanname wordt de optical flow constraint equation (OFCE) genoemd [5, 14, 25].

3.2

Technieken

Er zijn 2 mogelijke manieren om de verschillende technieken te groeperen. De eerste en de meest gebruikte indeling is beschreven door Barron et al.[4].

10

Optical flow berekenen

Hier wordt gekozen om de technieken op te delen in de volgende 4 categorie¨en: 1. Differentie gebaseerde optical flow 2. Correlatie gebaseerde optical flow 3. Energie gebaseerde optical flow 4. Fase gebaseerde optical flow De tweede manier van groeperen, zoals voorgesteld door Lui et al.[16], is om ze op te delen in 2 groepen : gradi¨ent gebaseerde technieken en niet-gradi¨ent gebaseerde technieken. Ongeacht welke manier van groeperen bestaan de algoritmes allemaal uit de volgende 3 stappen:

• De spatiotemporele procedures die worden toegepast op de beelden om features te extraheren. • De manier waarop de beweging wordt geschat aan de hand van de ge¨extraheerde features. • De manier waarop het flowveld wordt aangepast aan de hand van zekerheidsschattingen.

We zullen in de rest van deze masterproef gebruik maken van de Barron et al. indeling [4].

3.2.1

Differentie technieken

Differentie gebaseerde technieken zijn gebaseerd op afgeleiden. Meer specifiek gaat het over parti¨ele afgeleiden van de intensiteit I over x en y en in de tijd t. Differentie technieken zijn op zich nog eens opgesplitst in de volgende categorie¨en: lokale, globale en gecombineerde lokale en globale technieken. Lokale technieken, zoals Lucas & Kanade [17], proberen een lokale energie expressie te maximaliseren. Globale technieken, zoals de Horn–Schunck methode [14], proberen een globale energie expressie te minimaliseren.

Differentie technieken hebben nood aan smoothing. De reden hiervoor is dat de gradi¨ent (de eerste afgeleide) gevoelig is voor ruis. Door middel van een smoothing kunnen we de hoog frequente stukken (ruis) eruit halen. Er is ook nog opsplitsing tussen 1ste orde en 2de orde differentie technieken. Voorbeelden van de 2de orde differentie technieken zijn: Uras et al.[27] en Nagel. Een groot nadeel is dat 2de orde differentie technieken nog gevoeliger zijn voor ruis dan 1ste orde differentie technieken [10, 25].

3.2 Technieken

11

Lokale differentie technieken maken gebruik van vergelijking (3.2) die we kunnen omvormen tot vergelijking (3.3) Ix u + Iy v = −It

(3.3)

Deze vergelijking kunnen we niet oplossen doordat er teveel onbekenden zijn. Maar door gebruik van de ruimtelijke coherentie assumptie krijgen we meer vergelijkingen. De ruimtelijke coherentie assumptie zegt dat we veronderstellen dat buurpixels in een beeld dezelfde snelheid hebben. Dus kunnen we vergelijking (3.3) ook toepassen op zijn buurpunten. Ix1 u + Iy1 v = −It1 Ix2 u + Iy2 v = −It2 Ix(p) u + Iy(p) v = −It(p) .. .

(3.4)

Ixn u + Iyn v = −Itn

Waar n staat voor het aantal buurpixels en waar p de pixels binnen het window voorstellen. Met deze vergelijking zeggen we dus dat de omgeving van de pixel (de neighborhood, het window ) een translatie beweging (u,v) uitvoert. De grootte van dit window is zelf te kiezen. Nu kunnen we deze set van vergelijkingen oplossen met de Least squares (LS) , Total least squares (TLS) of nog recenter de Constrainted total least squares (CTLS) methode [26]. In het voorbeeld hieronder is gebruik gemaakt van de Least squares methode.   u ~u = = (S T S)−1 S T (−T ) v

(3.4)

Waarin S staat voor     S=  

Ix (x1 , y1 )

Iy (x1 , y1 )



      Ix (xN , yN ) Iy (xN , yN ) Ix (x2 , y2 ) .. .

Iy (x2 , y2 ) .. .

(3.5)

en 

It (x1 , y1 )



   T =  

It (x2 , y2 ) .. .

     

(3.6)

It (xN , yN ) Met N de windowgrootte en : Ix =

∂I ∂x

, Iy =

∂I ∂y

, It =

∂I ∂t .

De Lucas & Kanade [17] techniek

wordt berekend op elke pixel en de vergelijkingen die we kunnen opstellen kunnen we uitbreiden door gebruik te maken van buurpixels, zo krijgen we meer vergelijkingen [5, 25].

12

Optical flow berekenen

Globale differentie technieken

zoals de Horn–Schunck methode [14], maken ook gebruik

van de intensiteits constante besproken in 3.1, maar hebben nog nood aan een extra smoothness beperking. Deze auteurs verwachten dat de flow geleidelijk varieert over het beeld. Ze baseren zich hier op het feit dat buurpixels dezelfde snelheden hebben als ze tot hetzelfde object behoren. Dit levert natuurlijk problemen op bij objecten die over elkaar bewegen (occlusie). De methode van Horn-Schunck wordt best opgelost op een iteratieve methode. Allereerst kunnen we deze beperking, de smoothness constraint, weergeven door het kwadraat van de grootte van de gradi¨ent van de flow snelheid te minimaliseren. De gradi¨ent over u en v wordt als volgt gedefinieerd:

(

∂u ∂u 2 ) + ( )2 ∂x ∂y

(3.6)

(

∂v 2 ∂v ) + ( )2 ∂x ∂y

(3.6)

Een andere manier van smoothness van het flowveld is de som van de kwadraten van de Laplacianen van x en y-componenten van de flow. De Laplacianen van u en v zijn als volgt voorgesteld: ∇2 u =

∂2u ∂2u + 2 ∂x2 ∂y

(3.6)

∇2 v =

∂2v ∂2v + ∂x2 ∂y 2

(3.6)

Voor het schatten van de afgeleiden Ix , Iy , It is een kleine filter gebruikt.

1 Ix ≈ (Ii,j+1,k − Ii,j,k + Ii+1,j+1,k − Ii+1,j,k + Ii,j+1,k+1 − Ii,j,k+1 + Ii+1,j+1,k+1 − Ii+1,j,k+1 ) 4 1 Iy ≈ (Ii+1,j,k − Ii,j,k + Ii+1,j+1,k − Ii+1,j,k+1 + Ii + 1, j, k + 1 − Ii,j,k+1 + Ii+1,j+1,k+1 − Ii+1,j,k+1 ) 4 1 It ≈ (Ii,j,k+1 − ii,j,k + Ii+1,j,k+1 − Ii+1,j,k + Ii,j+1,k+1 − Ii,j+1,k + Ii+1,j+1,k+1 − Ii+1,j+1,k ) 4

Merk op dat deze filters driedimensionaal zijn. Om de Laplacianen van u en v te schatten wordt gebruik gemaakt van de volgende benadering: ∇2 u ≈ κ(ui,j,k − ui,j,k )

(3.2)

∇2 v ≈ κ(v i,j,k − vi,j,k )

(3.2)

3.2 Technieken

13

Waar de lokale gemiddelden ui,j,k en v i,j,k verkregen zijn door de volgende matrix voor de verticale en horizontale snelheidscomponenten te gebruiken:   1/12 1/6 1/12    Average =  1/6 0 1/6   1/12 1/6 1/12

(3.2)

Verder is κ gelijk aan 3 wanneer gebruik wordt gemaakt van de kleine filters voor het schatten van de afgeleide. κ wordt gebruikt om alles in proportie te krijgen. Nu moeten de schending van de intensiteit beperking en de smoothness beperking zo klein mogelijk worden gehouden. Of wel moeten de volgende 2 foutmaten worden geminimaliseerd: εi = Ix u + Iy v + It

ε2c = (

(3.2)

∂u ∂v ∂v ∂u 2 ) + ( )2 + ( )2 + ( )2 ∂x ∂y ∂x ∂y

Nu moet bepaald worden hoe deze twee factoren zich tot elkaar verhouden. Door onder andere ruis kan niet verwacht worden dat εi gelijk is aan 0. In de praktijk lijkt de εi ongeveer proportioneel te zijn aan de ruis. Laat daarom α2 de wegingsfactor zijn. De totale fout die nu geminimaliseerd moet worden is: ε2 =

Z Z

(α2 ε2c + ε2i ) dxdy

(3.1)

Voor een goede minimalisatie moeten er geschikte waarden voor de flow snelheid (u, v) worden gevonden. Volgens Horn-Schunk [14] komen we dan, met variatierekenen, tot vergelijkingen 3.2.1 en 3.2.1: Ix2 u + Ix Iy v = α2 ∇2 u − Ix It

(3.1)

Ix Iy u + Iy2 v = α2 ∇2 v − Iy It

(3.1)

Met de benaderingen van de Laplacianen die we behandeld hebben in vergelijkingen 3.2.1 en 3.2.1 krijgen we : (α2 + Ix2 )u + Ix Iy v = (α2 u − Ix It )

(3.1)

Ix Iy u + (α2 + Ix2 )v = (α2 v − Iy It )

(3.1)

Wanneer we nu u en v proberen op te lossen krijgen we : (α2 + Ix2 + Iy2 )u = (α2 + Iy2 )u − Ix Iy v − Ix It )

(3.1)

14

Optical flow berekenen

(α2 + Ix2 + Iy2 )v = −Ix Iy u + (α2 + Ix2 )v − Iy It )

(3.1)

Welke ook kan beschreven worden door : (α2 + Ix2 + Iy2 )(u − u) = −Ix (Ix u + Iy v + It )

(3.1)

(α2 + Ix2 + Iy2 )(v − v) = −Iy (Ix u + Iy v + It )

(3.1)

Wanneer we α2 gelijk aan nul laten zijn dan kunnen we een oplossing verkrijgen voor het minimalisatie probleem. Wanneer de Lagrange multipliers methode wordt toegepast wordt voor het minimaliseren van ε2c terwijl εi = 0 dan krijgen we : Iy ∇2 u = Ix ∇2 v

(3.1)

Ix u + Iy v + It = 0

(3.1)

Wanneer we de Laplaciaan schatten door het verschil in snelheid op een punt en de gemiddelde snelheid van zijn buurpunten dan krijgen we : (Ix2 + Iy2 )(u − u) = −Ix (Ix u + Iy v + It )

(3.1)

(Ix2 + Iy2 )(v − v) = −Iy (Ix u + Iy v + It )

(3.1)

We hebben nu 2 vergelijkingen voor elk punt van het beeld. We kunnen de vergelijkingen oplossen door bijvoorbeeld een Gauss-Jordan eliminatie. Voor een beeld van n × n pixels betekent dit een matrix van 2n × 2n. Daarom is het beter een iteratieve oplossing toe te passen. Met een Gauss - Seidel methode kunnen we een nieuwe schatting van de snelheden (un+1 , v n+1 ) maken op basis van de afgeleiden en gemiddelden van de vorige geschatte snelheden (un , v n ). We krijgen nu : un+1 = un − Ix (Ix un + Iy v n + It )/(α2 + Ix2 + Iy2 )

(3.1)

v n+1 = v n − Iy (Ix un + Iy v n + It )/(α2 + Ix2 + Iy2 )

(3.1)

Sommige punten liggen buiten de figuur en moeten opgevuld worden met waarden die op de rand liggen. De beginwaarden voor u en v zijn 0. In de gebieden waar de gradi¨ent gelijk aan 0 is, wordt de geschatte snelheid het gemiddelde van de buurpunten. Grote uniforme gebieden waar de gradi¨ent dus nul is, worden na voldoende iteraties helemaal opgevuld met schattingen van de flow snelheid [14, 25].

3.2 Technieken

15

Gecombineerde globale en lokale differentie methoden (GLC) [8] proberen de voordelen van de lokale en globale differentie technieken samen te nemen. Globale technieken hebben als nadeel dat ze meer gevoelig zijn voor ruis dan lokale technieken, maar het voordeel is dat ze een fijnere flow veld produceren dan lokale technieken. De Horn-Schunck [14] energie functie voorgesteld in vergelijking 3.2.1: ELK = w> Jρ (∇3 f )w

(3.1)

met

w := (u, v, 1)> , ∇3 f

|∇w|2 := |∇u|2 + |∇v|2 ,

:= (fx , fy , ft )> ,

Jρ (∇3 f ) := Kρ ∗ (∇3 f ∇3 f > )

(3.2) (3.3)

uitgebreid met de energie functie van Lucas & Kanade [17] weergegeven in vergelijking 3.2.1: Z

(w> J0 (∇3 f )w + α|∇w|2 ) dxdy

EHS (w) =

(3.3)

Ω

Levert de energie functie voor de CLG - methode , voorgesteld in vergelijking 3.2.1 : Z ECLG =

(w> Jρ (∇3 f )w + α|∇w|2 ) dxdy

(3.3)

Ω

3.2.2

Correlatie technieken

Correlatie technieken worden ingedeeld bij de niet - gradi¨ent gebaseerde technieken, zoals al eerder werd aangehaald in sectie 3.2, door Lui et al.[16]. Een correlatie techniek is eenvoudig voorgesteld het vergelijken van een window van frame 1 met een window van frame 2. Dit is voorgesteld in figuur 3.1. Er zijn dus 2 frames afgebeeld waarbij het grijsvlak in de figuur het

Figuur 3.1: Correlatie methode [2]

window voorstelt. Deze methode gaat dus rond elke pixel van frame 1 een window leggen. In het volgende frame kijken we waar het window van frame 1 de beste overeenkomsten heeft. De beste overeenkomst wordt dan bepaald door een correlatie criteria.

16

Optical flow berekenen

Er zijn 2 belangrijke parameters bij correlatie algoritmen: 1. de grootte van het window 2. de range : de grootte van de verplaatsing die kan voorkomen

Enkele voorbeelden van een correlatie criteria zijn de SSD (Sum of Squared Differences) en SAD (Sum of Absolute Differences) : SSD - Sum of squared Differences k k X X

d(p1, p2) =

(I1 (x1 + i, y1 + j) − I2 (x2 + i, y2 + j))2

(3.3)

j=−k i=−k

SAD - Sum of Absolute Differences d(p1, p2) =

k k X X

|I1 (x1 + i, y1 + j) − I2 (x2 + i, y2 + j|

(3.3)

j=−k i=−k

met k de grootte van het window. p1 = (x1 , y1 ) is het midden van window in Image1 p2 = (x2 , y2 ) is het midden van window in Image2 Optical flow algoritmes gebaseerd op correlatie technieken zijn gemakkelijk te implementeren en hebben een gunstige tijdscomplexiteit. Het nadeel van deze technieken is dat ze meestal niet zo nauwkeurig zijn. De meest bekende voorbeelden van correlatie technieken zijn die van Anadan, Singh en Camus [25].

3.2.3

Energie gebaseerde technieken

Een beweging kan worden gekarakteriseerd door zijn ori¨entatie in het ruimte-tijd domein. Figuur 3.2 (A) stelt een vlak voor dat van links naar rechts beweegt. Daar voegen we dan ook nog een as voor de tijd bij en dan krijgen we een ruimte-tijd volume 3.2 (B). Als we nu dit volume doorsnijden loodrecht op de y-as dan krijgen we figuur 3.2 (C). De helling die de balk hier maakt is gelijk aan de horizontale snelheid van het vlak in 3.2 (A). Voor dit soort bewegingen in het ruimte-tijd domein kun je een spatiotemporele filter ori¨enteren zodat deze de beweging kan detecteren. Deze filters zijn in te stellen voor bepaalde frequenties. Wanneer een filter een frequentie waarneemt waarvoor hij gevoelig is dan geeft deze filter een hoge output. De output, of ook wel energie, van deze filters kan dan gebruikt worden voor het schatten van het optical flow veld. Doordat de berekende optical flow afhankelijk is van de energie die de filters afgeven, worden technieken gebaseerd op deze filters energiegebaseerde technieken genoemd. Doordat de filters gevoelig zijn voor bepaalde frequenties is frequentie

3.2 Technieken

17

Figuur 3.2: In A beweegt een vlak naar rechts. In B staat hetzelfde vlak afgebeeld maar nu inclusief de tijd. In C staat een doorsnede van het ruimte-tijd volume in B [25].

gebaseerde technieken ook een gebruikte aanduiding. Een voorbeeld van een energiegebaseerde techniek is voorgesteld in de volgende sectie [22, 25]. Reichardt correlator Een eenvoudige instantie van een Reichardt correlator is te zien in figuur 3.3(a) . De input van een visueel systeem kan gezien worden als een intensiteitsignaal dat veranderd als functie van tijd en plaats. De twee input plaatsen A en B corresponderen met twee punten op het retina vlak. Wanneer nu een object van links naar rechts beweegt dan passeert deze eerst punt A en daarna B. Wanneer nu het signaal dat binnenkomt op A met de juiste mate vertraagt wordt dan zal het corresponderen met het signaal dat binnenkomt op B.

(a)

(b)

(c)

Figuur 3.3: Elementaire bewegingsdetector (a) reageert op bewegingen van A naar B. Elementaire bewegingsdetector (b) reageert op bewegingen van B naar A. Van bewegingsdetector 1 en 2 is het mogelijk een Reichardt detector te maken (c). De Reichardt detector reageert met een positieve output op beweging van A naar B en met een negatieve output op beweging van B naar A [25].

Een Reichardt correlator bestaat uit twee elementaire bewegingsdetectoren (figuur 3.3(a) en figuur 3.3(b)). Het ene deel zal over het algemeen reageren op beweging van links naar rechts en het andere deel op beweging in de tegenovergestelde richting. De reactie van de ene elementaire detector wordt van de andere afgetrokken (figuur 3.3(c)). Hierdoor reageert een Reichardt detector met een positieve waarde op beweging naar links en met negatieve waarde op beweging naar rechts. Hoewel het model een adequate bewegingsdetector is, is het geen goede snelheidsmeter. De output van het model is helaas niet lineair met de snelheid van een voorbij bewegende structuur. Onder andere de intensiteit en vorm van de voorbij bewegende patronen hebben in-

18

Optical flow berekenen

vloed op de output. Kortom de output van de correlator geeft een onzuivere schatting van de bewegingssnelheid [25].

3.2.4

Fase gebaseerde technieken

Fase gebaseerde technieken maken gebruik van spatiotemporele filters net zoals energiegebaseerde technieken. De video wordt allereerst omgezet in aantal band-pass kanalen. Dit kan gedaan worden door een bank quadrature filters. De resulterende bandpass beelden kunnen worden gerepresenteerd in termen van amplitude en fase. Het voordeel is dat de fase min of meer stabiel blijft wanneer de intensiteit verandert tussen twee frames. Andere technieken adopteren meestal de intensiteitconstantheid assumptie, zie 3.1, en zijn hierdoor minder stabiel bij intensiteitsveranderingen. Maar als grootste nadeel hebben ze dat ze een zeer slechte tijdscomplexiteit hebben, waardoor ze niet geschikt zijn om real-time te worden gebruikt [22, 24, 25].

3.3

Conclusie

In dit hoofdstuk zijn de verschillende technieken besproken waarmee men optical flow kan berekenen. De verschillende technieken zijn : differentie, correlatie, energie en fase gebaseerd optical flow technieken. Uit dit overzicht is gebleken dat correlatie en differentie gebaseerde technieken het best geschikt zijn om te implementeren. In het volgende hoofdstuk zullen deze technieken worden vergeleken met elkaar op basis van verschillende criteria om zo de beste techniek te selecteren en te implementeren.

Hoofdstuk 4

Optical flow technieken vergelijken In dit hoofdstuk worden de verschillende optical flow technieken met elkaar vergeleken. Dit wordt gedaan aan de hand van resultaten die behaald zijn in vorige studies, namelijk in Barron et al.[4], McCane et al.[18] en Lui et al.[16]. In Barron et al. wordt een vergelijkende studie gemaakt van verschillende optical flow technieken op basis van de parameter EA , die besproken is in vergelijking 4.1. McCane et al. gaat dan verder op deze studie door de gebruikte co¨effici¨ent te bekritiseren en door zijn eigen testen uit te voeren met nog een extra co¨effici¨ent, namelijk de EM , besproken in vergelijking 4.1. Deze twee studies zijn besproken in sectie 4.2.1. Lui et al., in sectie 4.2.2, focused meer op de computationele eisen die een techniek stelt aan de hardware. Eerst wordt er in sectie 4.1 dieper in gegaan op de co¨effici¨enten die gebruikt zullen worden in de studies uitgevoerd door Barron et al., McCane et al. en Lui et al.

4.1

Co¨ effici¨ enten

Optical flow algoritmen hebben elk hun voor- en nadelen. Er kunnen verschillen optreden in accuraatheid, dichtheid (density) en computationele eigenschappen. De co¨effici¨enten die gebruikt worden om de kwaliteiten van een algoritme weer te geven voor een bepaalde beeld zijn EA en EM . We gaan zowel gebruik maken van de hoek als de grootte van de vector in de vergelijkende tests, met als reden dat de EA co¨effici¨ent meermaals bekritiseert is, onder andere door Otte and Nagel [20], omdat het geen correcte weergave geeft bij grote vectoren. Daarom hebben zij gekozen om een andere co¨effici¨ent te introduceren, namelijk de EM . Het verschil in hoek wordt als volgt gedefinieerd : EA = cos−1 (ˆ c.ˆ e)

(4.0)

waar EA de fout van de hoek voorstelt, c is de correcte hoek en e de geschatte hoek. Hetˆteken staat voor vector normalisatie. Om problemen te vermijden die ontstaan tengevolge van kleine flow vectoren wordt een klein getal δ = 1 bij de vectoren c en e opgeteld als een derde co¨ordinaat. Het effect van deze derde co¨ ordinaat heeft meer invloed op kleine dan op grote flow vectoren.

20

Optical flow technieken vergelijken

Dit wil zeggen dat deze toevoeging als effect heeft dat bij een kleine flow de fout kleiner wordt, dus dat een verschil in hoek bij een grote flow erger is dan een verschil in hoek bij een kleine flow. Voor flows met een grootte die kleiner is of gelijk aan de δ, wordt het hoekverschil verlaagd door de derde co¨ordinaat, waar dat het hoekverschil bij grote flows niet wordt aangepast. Dit zorgt ervoor dat een verkeerde hoek in een gebied met grote flow belangrijker is dan in een gebied met kleine flow. De tweede co¨effici¨ent, ge¨ıntroduceerd door Otte and Nagel [20], is de EM , wat staat voor het verschil in grootte van de berekende vector en werkelijke vector. Zoals in vergelijking 4.1 staan c en e weer voor de correcte en de geschatte vector.   kc−ek  if kck ≥ T,    kck EM = kek−T T if kck < T     0 if kck < T

and

kek ≥ T,

and

kek < T,

(4.0)

Ook bij deze parameter moet er rekening gehouden worden met kleine flow, hiervoor introduceert men een drempelwaarde T. Wanneer de werkelijke flow kleiner is dan T dan gaan we er vanuit dat we geen correcte waarde kunnen berekenen voor dat punt [25, 18].

4.2

Vergelijken

In deze sectie gaan we de verschillende optical flow technieken met elkaar vergelijken op basis van accuraatheid, snelheid en weerstand tegen ruis.

4.2.1

Accuraatheid

In deze sectie gaan we de resultaten behaalt in Barron et al.[4] en in McCane et al.[18] bespreken. Zij gaan de optical flow technieken enkel vergelijken op basis van accuraatheid. Het verschil tussen beide studies is dat McCane et al. gebruik maakt van een extra co¨effici¨ent om te vergelijken. Eerst gaan we de resultaten bespreken van de test uitgevoerd door Barron et al. gevolgd door die van McCane et al. Barron et al.[4]

maakt gebruik van een sequentie genaamd Square2 en een sequentie genaamd

Yosemite. In figuur 4.1 is de Square2 sequentie voorgesteld. Dit is een simpele test case, terwijl de Yosemite sequentie voorgesteld in figuur 4.2 een veel moeilijkere opdracht is. Op deze beelden is dan van elke categorie, besproken in hoofdstuk 3.2, minstens 1 techniek toegepast en de resultaten worden dan weergegeven (in tabel 4.1 en tabel 4.2) en besproken. Na deze resultaten bekeken te hebben kunnen we enkele conclusies trekken. Namelijk dat er een duidelijke onderverdeling is tussen algoritmen die een goede accuraatheid, een kleine

4.2 Vergelijken

21

Figuur 4.1: Square2 sequentie[4]

Figuur 4.2: Yosemite sequentie met motion veld [4] Tabel 4.1: Resultaten voor Square2 [4]

Techniek

Gemiddelde fout

Standaard deviatie

densiteit

Horn-Schunck

47.21◦

14.60◦

100 %

Lucas & Kanade (λ2 ≥ 1.0)

0.21◦

0.16

Uras et al. (det(H) > 1.0 )

0.15◦

0.10◦

26.1 %

Nagel

34.57◦

14.38◦

100 %

Anadan (unthresholded)

31.46◦

18.31◦

100 %

Singh (Step 1, n = 2, w = 2)

49.03◦

21.38◦

100 %

Heegher (combined)

6.16◦

4.02◦

29.3 %

Waxman et al. (σf = 1.5)

8.78◦

4.71◦

1.1 %

Fleet and Jepson ( τ = 1.25)

0.07◦

0.02◦

2.2 %

◦

7.9 %

gemiddelde fout, behalen of een goede densiteit hebben. We merken ook op dat er een verschil is tussen de lokale en de globale differentie technieken. Zoals we kunnen zien in tabel 4.1 en tabel 4.2 levert de globale techniek van Horn-Schunck een fijn flow veld op maar ook een grote gemiddelde fout. Terwijl de lokale techniek van Lucas & Kanade goede resultaten oplevert op gebied van de gemiddelde fout, maar geen fijn flow veld produceert. Een tweede vaststelling is dat de 2de orde differentie technieken, van Nagel en van Uras et al., beter resultaten opleveren dan de 1ste orde differentie technieken. Maar deze verbetering is maar gering. Als we dan verder gaan kijken in de tabel komen we de correlatie technieken van Anadan en Singh tegen waarbij we opmerken dat ze grote gemiddelde fouten opleveren, maar een fijn flow veld. De waarden van de

22

Optical flow technieken vergelijken Tabel 4.2: Resultaten voor Yosemite [4]

Techniek

Gemiddelde fout

Standaard deviatie

densiteit

Horn-Schunck

32.43◦

30.28◦

100 %

Lucas & Kanade (λ2 ≥ 1.0)

4.10◦

9.58

◦

35.1 %

Uras et al. (det(H) > 1.0 )

6.73◦

16.01◦

14.7 %

Nagel

11.71◦

10.59◦

100 %

Anadan

15.84◦

13.46◦

100 %

Singh (Step 1, n = 2, w = 2

18.24◦

17.02◦

100 %

Heegher (combined)

11.74◦

19.04◦

44.8 %

Waxman et al. (σf = 2.0)

20.32◦

20.60◦

7.4 %

Fleet and Jepson ( τ = 1.25)

4.95◦

12.39◦

30.6 %

correlatie technieken liggen in dezelfde grootte orde als die van de globale differentie technieken. De energie techniek van Heeger levert grote gemiddelde fouten af en een slecht fijn veld. De fase techniek van Fleet en Jepson daarentegen levert goede resultaten af voor het Square2 beeld, maar niet voor het Yosemite beeld. De reden hiervoor is dat de tuning frequentie moest worden aangepast, met het gevolg dat deze dichter tegen de Nyquist rate ligt. We merken dus op dat de fase gebaseerde techniek van Fleet and Jepson goede resultaten oplevert. Ook de 1ste orde differentie leveren goede prestaties af [4].

McCane et al. [18]

maakt ook zoals Barron et al gebruik van de EA , de hoek fout, maar

maakt ook nog gebruik van een extra co¨effici¨ent om de resultaten te meten. Namelijk de EM , de fout in grootte van de vector, uitgelegd in sectie 4.1, vergelijking 4.1. In figuur 4.3 zien we de resultaten van de test uitgevoerd door McCane et al. In figuur 4.3(a) wordt de resultaten voor EA weergegeven en in figuur 4.3(b) de resultaten voor EM . Op de y-as is het cumulatief percentage voor flows kleiner dan de error weergegeven en op de x-as de grootte van de error (in figuur 4.3(a) in stappen van 18 graden en in figuur 4.3(b) in stappen van 0.2). Dit wil dus zeggen dat, in figuur 4.3(a), het Proesman et al. algoritme 75 procent van zijn flows een hoekfout hebben van 18 graden of minder. De ideale curve is dus diegene die het meest bovenaan gelegen is en voor elke error waarde. H.Top [25] heeft gebruik gemaakt van de techniek die voorgesteld is door McCane et al. om de optical flow technieken te vergelijken. H.Top heeft dan testen uitgevoerd op een re¨ele sequentie en kwam tot de resultaten die weergegeven zijn in figuur 4.4. Deze 2 grafieken laten de accuraatheid in de hoek van de flowvectoren zien en de accuraatheid van de grootte van de flowvectoren. In de bovenste grafiek staat op de verticale as het percentage van juiste schattingen. Op de horizontale as de maximale fout in de hoek van de flowvectoren. Als we bijvoorbeeld naar de maximale hoekfout van 10 graden kijken, in figuur 4.4, dan zien we dat bij de Reichardt correlator 87

4.2 Vergelijken

23

procent van de geschatte flowvectoren een fout van 10 graden of minder hebben. De energie gebaseerde technieken presteren hier het best gevolgd door de correlatie technieken.

(a) Hoek accuraatheid.

(b) Grootte accuraatheid.

Figuur 4.3: Relatieve performantie van elk algoritme voor een complexe sequentie[18] .

4.2.2

Snelheid

Lui et al.[16]

heeft onderzoek gedaan naar zowel de accuraatheid als de snelheid van de opti-

cal flow technieken. Lui et al. heeft deze dan weergegeven in zogenaamde AE-curves (AccuracyEfficiency curves). Waarin de CPU Time, die nodig is om de techniek uit te voeren, op de y-as staat en de hoek fout op de x-as. Figuur 4.5(a) is zo’n AE-curve voor de Yosemite sequentie en figuur 4.5(b) is een AE-curve voor de Diverging Trees sequentie. Ook uit deze grafiek kunnen we veel informatie halen, namelijk het feit dat de 2de orde differentie technieken (Nagel en Uras et al.) betere resultaten opleveren dan 1ste orde differentie technieken, maar dat ze hogere computationele eisen stellen. We zien ook dat de energie - en fasegebaseerde

24

Optical flow technieken vergelijken

Figuur 4.4: Resultaten voor accuraatheid van de hoek en de grootte voor een re¨ele sequentie [25].

technieken de beste resultaten opleveren, maar een zeer slechte tijdscomplexiteit hebben. In sectie 3.2.3 en in 3.2.4 hebben we uitgelegd dat energie- en fasegebaseerde technieken gebruik maken van spatiotemporele filters. Dit zorgt ervoor dat ze zeer rekenintensief zijn. We kunnen ook concluderen dat de techniek die het beste presteert op zowel accuraatheid en snelheid, de Camus correlatie techniek is [3, 4, 6, 10, 13, 15, 16].

4.2.3

Ruis

We kunnen de optical flow technieken ook gaan vergelijken op basis van hun ruisgevoeligheid. In figuur 4.6 zijn de EA en EM weergegeven voor 4 verschillende optical flow technieken wanneer er ruis is toegevoegd aan de sequentie. Deze twee grafieken laten de accuraatheid in de hoek van de flowvectoren zien en de accuraatheid van de grootte van de flowvectoren. In de bovenste grafiek staat op de verticale as het percentage van juiste schattingen. Op de horizontale as de maximale fout in de hoek van de flowvectoren. Opvallend zijn de prestaties van de energie gebaseerde methode en de correlatie gebaseerde methode op de video met ruis. Vooral onder deze omstandigheid presteren deze algoritmen beter dan de anderen. Dit kan er op duiden dat deze algoritmen interessant zijn voor gebruik onder moeilijke omstandigheden. Het lokale differentie gebaseerde algoritme van Lucas & Kanade presteert opvallend slecht op de video met ruis. Hierdoor is het algoritme wellicht een mindere keuze onder moeilijke omstandigheden. Ook de globale techniek van Horn-Schunck levert geen al te beste resultaten af bij toevoeging van ruis [3, 4, 6, 10, 13, 15, 16].

4.3 Conclusie

25

(a) 2-D performantie diagram voor de Yosemite sequentie [16]

(b) 2-D performantie diagram voor de Diverging Trees sequentie [16]

Figuur 4.5: 2-D performantie diagrammen [16]

4.3

Conclusie

De fase- en energiegebaseerde technieken komen in alle tests naar voor als het algoritme dat het beste resultaat oplevert in zowel accuraatheid van de hoek als in grootte. Het nadeel van deze fase- en energiegebaseerde technieken is dat ze computationeel hoge eisen stellen. Dit wil zeggen dat ze veel rekentijd nodig hebben en daarom niet worden gebruikt in real-time toepassingen. De lokale en globale differentie technieken leveren geen totaal oplossing. Namelijk de lokale technieken zijn robuuster tegen ruis, leveren geen te grote fouten af maar hun flow veld is niet fijn. Globale technieken zijn het tegenovergestelde van lokale technieken, ze geven een goed fijn flow veld (100%) maar geven slechtere prestaties bij ruis en grote hoek fouten. Een nadeel bij differentie technieken in het algemeen is dat ze liefst hebben dat de intensiteit niet veranderd. Correlatie technieken zijn beter geschikt om met ruis te werken, omdat ze geen afgeleiden moeten berekenen. Correlatie technieken zijn uit het computationele standpunt gezien lichter dan de

26

Optical flow technieken vergelijken

Figuur 4.6: Invloed van ruis op prestaties [25]

differentie gebaseerde algoritme of natuurlijk de fase- en energie gebaseerde algoritme. Het besluit is dat als we een real-time implementatie willen die robuust is tegen ruis en een goede accuraatheid heeft, we dan een correlatie techniek moeten gebruiken. Op basis van deze eerste vier hoofdstukken hebben we een reflection paper ingediend voor IADIS Computer Graphics, Visualization, Computer Vision and Image Processing (CGVCVIP) conferentie. Deze paper is terug te vinden in de bijlage A. De paper gaf een overzicht van de verschillende optical flow technieken en gaf een vergelijking op basis van verschillende criteria. De reflection paper is geaccepteerd door CGVCVIP en er zal een presentatie worden gegeven tijdens deze conferentie.

Hoofdstuk 5

Het Camus algoritme In dit hoofdstuk wordt er dieper in gegaan op het Camus correlatie algoritme. Dit hoofdstuk begint met sectie 5.1 waarin een uitgebreidere uitleg wordt gegeven over correlatie technieken in het algemeen, gevolgd door een bespreking van het Camus algoritme zelf in sectie 5.2, waarin er wordt uitgelegd hoe het werkt en wat de eigenschappen zijn. Daarna worden er in sectie 5.3 de problemen besproken die eventueel kunnen optreden bij het gebruik van het Camus algoritme. In sectie 5.4 worden de parallellisatie mogelijkheden besproken. Tot slot is er nog een conclusie in sectie 5.5.

5.1

Inleiding

Zoals eerder vermeld, in hoofdstuk 2, is optical flow het weergeven van de verplaatsing van een pixel tussen 2 opeenvolgende frames door middel van een vector. Dit is voorgesteld in figuur 5.1, waar pixel A verplaatst is over een afstand van 2 pixels naar rechts onder in Afbeelding 2 ten opzichte van Afbeelding 1. In deze sectie gaan we nu dieper in op de werkwijze van correlatie gebaseerde technieken om optical flow te berekenen. We beginnen met te veronderstellen dat de maximale verplaatsing van elke pixel gelimiteerd is tot n in elke richting, in figuur 5.1 is deze maximale verplaatsing n gelijk aan 2. Deze waarde van n moet gekozen worden op basis van de verwachte snelheid waarmee de pixels zich zullen verplaatsen in de afbeelding. Omdat we meestal ge¨ınteresseerd zijn in de verplaatsing van rigide-body object, dus niet van individuele pixels, maar van objecten bestaand uit aaneengesloten pixels kunnen we veronderstellen dat elke pixel van zulke rigide-body objecten dezelfde snelheid zal hebben als zijn omgeving. Er wordt dan gebruik gemaakt van een vierkante neighborhood, ook wel window, mask of patch genoemd, met een grootte van v rond de gegeven pixel, hierbij veronderstellen we dat de vectoren voor de pixels gelegen aan de gekozen pixel gelijk aan mekaar zijn, zoals voorgesteld in figuur 5.2. De beweging van een pixel op plaats [x, y] is gedefinieerd als de beweging van het v × v window

28

Het Camus algoritme

(a)

(b)

Figuur 5.1: (a) In Afbeelding 1 is het zoekgebied weergegeven voor pixel A met een maximale verplaatsing n van 2 pixels. (b) De correcte verplaatsing van de pixel van Afbeelding1 naar Afbeelding 2 is weergegeven door de vector AB.

(a)

(b)

Figuur 5.2: (a) In Afbeelding 1 is het window weergegeven voor een pixel A, v=3. (b) De vectoren voor pixels gelegen aan pixel A worden verondersteld gelijk te zijn ten gevolge van de rigide-body veronderstelling.

5.2 Camus correlatie

29

gecentreerd in [x, y] van mogelijk (2n + 1) × (2n + 1) mogelijk verplaatsingen. We bepalen de juiste verplaatsing van het window door middel van simulatie van elke mogelijke verplaatsing van [x, y] en door middel van match strength of correlatie waarde te bepalen voor elke mogelijke verplaatsing. Als dan φ een correlatie functie voorstelt die een waarde teruggeeft die proportioneel is aan de overeenkomst gevonden tussen 2 elementen van het window, dan is de match strength M (x,y;u,w) voor een punt [x, y] en verplaatsing (u, w) berekend door de som te nemen van elke correlatie waarde voor elke pixel in het verplaatste window Pv , dit is weergegeven in vergelijking 5.1 ∀u, w : M (x, y; u, w) =

X

φ(E1(i, j)) − E2(i + u, j + w)), (i, j) ∈ Pv .

(5.0)

Een voorbeeld van zo’n matching functie φ is het verschil in absolute waarde nemen tussen de twee pixel intensiteiten. Dit is voorgesteld in vergelijking 5.1. Een ander voorbeeld is het gebruik maken van het gekwadrateerd verschil van de intensiteitswaarde, voorgesteld in vergelijking 5.1. k k X X

d(p1, p2) =

(I1 (x1 + i, y1 + j) − I2 (x2 + i, y2 + j))2

(5.0)

j=−k i=−k

d(p1, p2) =

k k X X

|I1 (x1 + i, y1 + j) − I2 (x2 + i, y2 + j|

(5.0)

j=−k i=−k

De vuistregel bij deze correlatie functies is dat hoe lager deze waarde is hoe beter de overeenkomst is. De opmerking die we hier moeten bij maken is dat de verplaatsing die we toewijzen aan die pixel [x, y] gekozen is uit (2n + 1) × (2n + 1) mogelijke verplaatsingen waarbij dat we kijken naar de maximum correlatie waarde (dus eigenlijk het minimum verschil tussen de windows). Dit is genaamd een winner-take-all algoritme, omdat er wordt gekeken naar de beste overeenkomst tussen windows en niet op basis van een individuele pixel. Dit wordt dan uitgevoerd voor elke pixel in de afbeelding, onafhankelijk van de andere pixels met enkel een uitzondering voor de n + [v/2] rand van de afbeelding omdat er daar geen pixels meer zijn. Een voordeel van het feit dat dit op elke pixel van de afbeelding wordt uitgevoerd is dat het window voor een pixel grotendeels overlapt met het window van de aanliggende pixel met het gevolg dat het resulterend optical flow veld relatief smooth is. Een ander voordeel is dat er daardoor voor elke pixel een vector gemaakt wordt en dus dat de densiteit van het optical flow veld gelijk is aan 100 procent.

5.2

Camus correlatie

De belangrijkste limitatie van traditionele correlatie technieken is dat tijdscomplexiteit kwadratisch toeneemt met de maximum toegelaten verplaatsing van de pixel, dit is voorgesteld in figuur

30

Het Camus algoritme

Figuur 5.3: Zoekgebied voor een maximale verplaatsing van 1 pixel en van 2 pixels.

5.4. Intu¨ıtief weten we dat als de snelheid toeneemt van het waar te nemen object, dit wil zeggen dat de maximum toegelaten verplaatsing van de pixel toeneemt, de tijd nodig om te zoeken naar de juiste beweging kwadratisch toeneemt, omdat het gebied waarover we moeten zoeken gelijk is aan cirkel gecentreerd op de pixel met een straal gelijk aan de maximum snelheid die we willen detecteren. Dit wordt verduidelijkt door middel van figuur 5.3 waarin het zoekgebied wordt voorgesteld voor een maximale verplaatsing van 1 pixel en voor 2 pixels.

(a) Constante tijdsvertraging, variabele afstand.

(b) Constante afstand, variabele tijdsvertragingen

Figuur 5.4: Als de maximum toegelaten verplaatsing toeneemt dan neemt het zoekoppervlak kwadratisch toe, maar wanneer we gebruik maken constante maximum verplaatsing en variabele tijdsvertragingen is zoeken in de tijd lineair.

In vergelijking 5.2 wordt het verband weergeven tussen snelheid, tijd en afstand. Normaal wordt er bij een correlatie methode gezocht over variabele afstanden om te zoeken naar vari¨erende snelheden en blijft de tijd constant, zoals voorgesteld in vergelijking 5.2. Met het gevolg, zoals we kunnen zien in figuur 5.4(a), dat het te onderzoeken oppervlak kwadratisch toeneemt.

snelheid =

∆af stand ∆tijd

(5.0)

5.2 Camus correlatie

31

∆v =

∆d δt

(5.0)

Wat Camus dan voortelt is in plaats van de afstand aan te passen waarover we zoeken, we het tijdsframe aanpassen, dit is weergegeven in figuur 5.4(b) en in vergelijking 5.2. Dus het zoekgebied in oppervlak, aantal pixel, is nu een constante waarde geworden bijvoorbeeld 1 pixel.

∆v =

δd ∆t

(5.0)

Zoals hiervoor al vermeld is de gekozen verplaatsing gelijk aan de verplaatsing die de kleinste match waarde heeft. In de figuren 5.5 en 5.6 wordt dit verduidelijkt aan de hand van een voorbeeld. Hier wordt er geprobeerd om de optical flow voor een pixel op de plaats (1,1) in de huidige frame, Afbeelding t, te berekenen. In figuur 5.5 is de optimale optical flow voor de pixel op de plaats (1,1) van Afbeelding t − 1 naar Afbeelding t berekend als een pixel verplaatsing van (1,-1). Dit is enkel de tijdelijke lokale metingen, dit is niet noodzakelijk de beste verplaatsing. In figuur 5.6 zijn dezelfde berekeningen uitgevoerd alleen is Afbeelding t − 2 gebruikt als eerste afbeelding. In dit geval is de juiste verplaatsing gelijk aan pixel verplaatsing van (0,1) over 2 frames. Als de maximum tijdsvertraging gelijk is aan S = 2 dan zou dit het einde betekenen voor deze procedure anders moet er verder worden gewerkt tot dat we de t − S naar t hebben berekend. De beste verplaatsingen is gekozen uit alle tijdelijke lokale metingen.

Figuur 5.5: Visualisatie van de verplaatsing van Afbeelding t-1: (1,1) naar t: (2,0). De verplaatsing is hier gelijk aan (1,-1).

In figuur 5.7 is dan een overzicht weergegeven van het principe dat schuil gaat achter het Camus algoritme. De normale 1-dimensionale zoektocht in oppervlakte, de maximale verplaatsing is nu omgezet in een 2-dimensionale zoektocht in zowel de tijd als in oppervlakte.

32

Het Camus algoritme

Figuur 5.6: Visualisatie van de verplaatsing van Afbeelding t-2: (1,1) naar t: (1,2). De verplaatsing is hier gelijk aan (0,1) over 2 frames.

Figuur 5.7: De normale 1-dimensionale zoektocht in oppervlakte is omgezet naar een 2-dimensionale zoektocht in zowel tijd als oppervlakte.

5.3 Camus problemen

5.3

33

Camus problemen

In deze sectie worden de problemen besproken die kunnen optreden wanneer men het Camus algoritme gebruikt om optical flow te berekenen.

5.3.1

Temporele aperture probleem

In sectie 2.3 is het Aperture Probleem al besproken geweest. In deze sectie wordt het temporele aperture probleem besproken. In figuur 5.8 wordt een kromme getransleerd naar rechts onder. We veronderstellen een goede overeenkomst te vinden tussen punt A op tijdstip T en punt B op tijdstip T − 2, maar er wordt nog een tweede goede overeenkomst gevonden. Deze tweede goede overeenkomst is tussen punt A op tijdstip T en punt C op tijdstip T − 1. Globaal gezien is de tweede overeenkomst niet correct, maar de verplaatsing is onafhankelijk berekend op elk tijdstip en deze foutieve beweging heeft een goede overeenkomst. We hebben gezien dat het Aperture Probleem opdook bij het gebruiken van een te kleine opening. Het temporele aperture probleem is dan het gevolg van een te klein tijdsopening. Door middel van een grotere tijdsopening te gebruiken kan dit probleem vermeden worden.

Figuur 5.8: Temporele aperture probleem. De correcte verplaatsing is gelijk aan B → A,maar wanneer de opening(window) in de tijd te klein is kan een verkeerde beweging C → A gedetecteerd worden.

5.3.2

Temporele aliasing

In de vorige sectie hebben we gezegd dat we het temporele aperture probleem konden oplossen door onze tijdsopening groter te maken. Dit zal meestal lukken, maar er zijn uitzonderingen. Stel voor dat pixel A naar pixel B transleert en dan naar pixel C, dit kan het geval zijn wanneer het object een scherpe bocht uitvoert, dit is voorgesteld in figuur 5.9. Het kan bijvoorbeeld zijn dat A → C een betere match oplevert dan B → C en we volgden de regel dat de beste match wint. Dus we zouden verkeerd de A → C als de correcte verplaatsing aanduiden. Een voor de hand liggende keuze is aannemen dat de snelste beweging de beste is. In dit voorbeeld werkt dit, maar er zijn speciale gevallen waarbij dit misloopt. Deze regel van de

34

Het Camus algoritme

snelste beweging is de juiste loopt vooral verkeerd wanneer er gebruik wordt gemaakt van een δt = 20 frames.

Figuur 5.9: Temporele aliasing

5.3.3

Temporele oclussie

Temporele occlusie ontstaat wanneer een object een ander object afschermt in een frame in het verleden, maar niet meer in de huidige frame. Een voorbeeld van temporele occlusie is weergegeven in figuur 5.10. In frame T, van figuur 5.10, is een traag bewegende achtergrond aanwezig en deze achtergrond is niet afgeschermd door een ander object op dit tijdstip, maar als we 5 frames terug in de tijd gaan zien we dat de traag bewegende achtergrond word afgeschermd door een sneller bewegend object. Als we dan de correlatie willen berekenen voor een pixel van de traag bewegende achtergrond in het huidige frame T en in het frame T − 5 dan zullen we een foute waarde terug krijgen ten gevolge van het feit dat de achtergrond wordt afgeschermd door een ander object in het verleden. De correlatie berekenen tussen het huidige frame T en het vorige frame T − 1 voor de snel bewegende voorgrond zal een betere correlatie waarde teruggeven. Met het gevolg dat voor deze pixel de beweging van de snelle voorgrond wordt gegeven in plaats van de juiste beweging van de traag bewegende achtergrond. Dit zorgt ervoor dat snel bewegende objecten op de voorgrond een soort van nasleep krijgen, zodat objecten op de voorgrond groter zullen tonen dan ze in echt zijn.

5.4

Parallellisatie

Het Camus correlatie algoritme wordt uitgevoerd op elke pixel van het beeld, maar onafhankelijk van elkaar. Dit wil zeggen dat we geen informatie moeten hebben van de vorige berekening om

5.5 Conclusie

35

Figuur 5.10: Temporele occlusie

de volgende berekening uit te voeren. Een mogelijkheid om aan parallellisatie te doen is om de figuur op te splitsen in stukken om zo tijdswinst te boeken. Dit is voorgesteld in figuur 5.11. Dit wil zeggen dat we pixel-per-pixel apart kunnen berekenen.

Figuur 5.11: Parallellisatie door middel van de afbeelding op te splitsen in kleinere stukken.

5.5

Conclusie

In dit hoofdstuk is er dieper ingegaan op correlatie gebaseerde optical flow technieken, zodat men een beter inzicht krijgt in de redenen waarom er gekozen is voor het Camus correlatie algoritme. Verder werd er in dit hoofdstuk in detail ingegaan op de werkwijze van het Camus correlatie algoritme en welke problemen er kunnen voorkomen als men dit implementeert. Tot slot is de mogelijkheid tot parallellisatie besproken [9, 10].

36

Het Camus algoritme

Hoofdstuk 6

Embedded systeem Na het uitleggen van de werking van het Camus algoritme wordt er in dit hoofdstuk meer informatie gegeven over het gebruikte embedded platform. Het gebruikte embedded platform is de Xilinx Virtex 5 ML507, voorgesteld in figuur 6.5. Dit hoofdstuk begint met een korte introductie op FPGA’s. Hoe ze werken en gebruikt kunnen worden en hoe hun architectuur eruit ziet, gevolgd door de specificaties van het Xilinx Virtex 5 ML507 bord.

6.1

Inleiding op FPGA

FPGA staat voor Field Programmable Gate Array en is een ge¨ıntegreerde schakeling bestaande uit configureerbare digitale componenten. De gebruiker kan zijn eigen hardware systeem cre¨eren en downloaden naar de FPGA. Deze configureerbare digitale componenten kunnen gezien worden als bouwblokken die verbonden kunnen worden met elkaar om zo digitale systemen te cre¨eren. Een FPGA bestaat uit 3 verschillende bouwstenen: 1. Logische Blokken 2. Input/Output Blokken 3. Programmeerbare Interconnecties Een simpel voorbeeld van de architectuur van een FPGA is voorgesteld in figuur 6.1. De 3 belangrijkste elementen (I/O blokken, Logische blokken, Interconnecties) van figuur 6.1 worden besproken in de volgende secties van dit hoofdstuk.

6.1.1

Logische Blokken

Een FPGA kan gezien worden als een aaneenschakeling van configureerbare logische blokken. Deze logische blokken kunnen door de gebruiker geprogrammeerd worden om eenvoudige logische functies te maken, of meer complexe functies te cre¨eren.

38

Embedded systeem

Figuur 6.1: Architectuur van een FPGA

Elk logisch blok, voorgesteld in figuur 6.2, bestaat uit een look-up table (LUT) en een flip-flop. Een lookup table is een data structuur, zoals een array, in welke we de juiste waarde moeten opzoeken door het corresponderende adres te gebruiken. Door waarden in te vullen op bepaalde adressen kunnen we functies cre¨eren. Een flip-flop kan gebruikt worden om een resultaat te stockeren voor een clock cycle of het resultaat kan rechtstreeks naar buiten gebracht worden. Gebruik makend van deze eenvoudige architectuur kunnen de meeste logische functies gecre¨eerd worden.

Figuur 6.2: Architectuur van logisch blok

6.1.2

Input/Output Blokken

Een FPGA maakt gebruik van zijn input en output pinnen/verbindingen voor interactie te voorzien met de externe wereld. De connectie van interne hardware met de externe hardware is beschreven in de UCF (User Constraint File). De externe componenten zijn verbonden met de pinnen die kunnen opgezocht worden in de hardware handleiding. Een voorbeeld van een Input/Output blok is weergegeven in figuur 6.3. De I1 en I2 zijn ingangen en Out is de uitgang. Ingang 1 en 2 brengen signalen van buiten de FPGA naar binnen. Zoals we ook kunnen zien in de figuur 6.3 zijn er nog enkele andere mogelijkheden zoals het vertragen van de ingangssignalen

6.1 Inleiding op FPGA

39

door middel van een delay en ook de mogelijkheid om de uitgangssignalen te inverteren is aanwezig.

Figuur 6.3: Architectuur van het Input/Output blok

6.1.3

Interconnecties

Een belangrijk element van de FPGA is de interconnectie of ook wel de routing genoemd. Deze routing dient om logische blokken te verbinden tot grotere circuits om aan de vereiste functionaliteit te voldoen. De routing in een FPGA is unsegmented. Dit wil zeggen dat om meerder logische blokken met elkaar te verbinden men moet gebruik maken van een switch box, voorgesteld in figuur 6.4. Door middel van het sluiten van enkele programmeerbare schakelaars in de switch box kan men meerdere logische blokken met mekaar verbinden en langere connecties kunnen gemaakt worden om complexere functies te cre¨eren. Hoe eenvoudiger en hoe korter de verbinding is, hoe beter de performantie is.

Figuur 6.4: Architectuur van de switch box

40

Embedded systeem

6.2

Virtex-5 Evaluation Platform ML507 bord

Het platform dat we gebruiken is het Xilinx Virtex-5 Evaluation Platform ML507 bord. Dit platform wordt voorgesteld in figuur 6.5

Figuur 6.5: Virtex-5 Evaluation Platform ML507 bord

Dit platform bestaat uit high performance FPGA die een PowerPC bevat en andere randapparatuur. Specificaties van dit bord worden weergegeven in tabel 6.1. Hieronder is een overzicht weergegeven van de elementen die we nader gaan bespreken: 1. Logische Blokken 2. Block RAM 3. Digital Clock Manager

6.2 Virtex-5 Evaluation Platform ML507 bord

41

Tabel 6.1: Specificaties van de Xilinx Virtex 5 ML507 FX70T

Logische Blokken

71.680

6 LUTs/Flip Flop

44.800

LUT RAM Kbits

820

36Kbit BRAM Blokken

148

BRAM Kbits

5.328

XtremeDSP DSP48E Slices

128

PowerPC 440 Blocks

1

PCI Express Endpoint Blocks

3

10/100/1000 Ethernet MACS

4

Configureerbare logische blokken De configureerbare logische blokken zijn, zoals eerder vermeld, programmeerbare logica die geconfigureerd/geprogrammeerd kan worden door de gebruiker om zo hardware ontwerpen te maken. Nadat een specifiek ontwerp gemaakt is moet het ge¨ımplementeerd worden op de FPGA. Dit ontwerp wordt gecompileerd en gesynthetiseerd in een bit file. Deze bit file bepaalt welke verbindingen er moeten gemaakt worden om ontwerp te realiseren en is gestockeerd in het RAM geheugen. De CLB is zoals eerder vermeld opgebouwd uit 2 slices, deze 2 slices zijn dan verbonden met elkaar via een switch matrix. In figuur 6.6(a) wordt deze switch matrix voorgesteld. Door middel van deze switch matrix zijn de slices verbonden met de globale routing matrix. Een Virtex 5 configureerbaar logisch blok bestaat uit 2 slices, waarin elke slice vier 6 LUT’s en 4 Flip-Flops heeft. Een slice van de virtex 5 is voorgesteld in figuur 6.6(b). In de slice zitten ook nog grote multiplexers en logische poorten.

(a)

(b)

Figuur 6.6: (a)CLB

(b)Virtex-5 Slice

42

Embedded systeem

Block RAM Elke block RAM is een 36Kbit true dual-port RAM s wat betekent dat er 2 verschillende poorten zijn die elk onafhankelijk van elkaar worden geklokt en gecontroleerd, en beiden hebben toegang tot hetzelfde gedeelde geheugen. In figuur 6.7 is zo’n block RAM voorgesteld en zien we dan ook de 2 individuele poorten met elk dezelfde ingangen : Write Enable, Set/Reset, Data Input, Data Output, Address, Cascade Input, Cascade Output als ook gescheiden Data/parity ingangen en Data/parity uitgangen. De lees en schrijf bewerkingen zijn synchrone bewerkingen. Elke 36Kbit block RAM kan geconfigureerd worden als een 36Kb RAM of 2 onafhankelijke 18Kb RAM ’s. De mogelijke configuratie zijn weergegeven in tabel 6.2. Tabel 6.2: Configuratie mogelijkheden van een 36Kbit en een 18Kbit RAM

32K x 1

16K x 1

16K x 2

8K x 2

8K x 4

4K x 4

4K x 9

2K x 9

2K x 18

1K x 18

1K x 36

Figuur 6.7: Virtex-5 Block RAM

6.3 Aansluitingen van de Virtex 5 ML507

43

Digital Clock Manager De Virtex 5 ML507 heeft ook functionaliteit om aan klok beheersing te doen. Dit wordt mogelijk gemaakt door de Digital Clock Manager (DCM). De functies die worden aangeboden door de Digital Clock Manager worden hieronder weergegeven.

Clock Deskew De DCM bevat een delay-locked loop (DLL) om klok distributie vertraging te elimineren. De DLL bevat vertragingselementen (kleine buffers) en controle logica. Frequency Synthesis

De uitgang CLKDV voorziet de FPGA van een uitgang die een spe-

cifieke deel van de ingangsfrequentie is door middel van delingen en vermenigvuldigen. De gebruiker kan de integer vermenigvuldiger (M) en deling (D) gebruiken om een fractie te cre¨eren van het ingangssignaal. Ook zijn er 2 uitgangen CLK2X en CLK2X180 die werken op de dubbele frequentie. Phase Shifting

De DCM laat toe om aan coarse phase shifting te doen. De uitgangs klok

kan in fase verschoven zijn over 90◦ , 180◦ , 270◦ . DCM voorziet ook de mogelijkheid om aan fine-grained phase shifting te doen, dit is het aanpassen van de fase in stappen van 1/256 van de klok periode.

6.3

Aansluitingen van de Virtex 5 ML507

De Xilinx Virtex 5 heeft groot aantal aansluit mogelijkheden voor randapparatuur. Deze aansluitingen worden voorgesteld in een blok diagram in figuur 6.8. De randapparatuur die we gebruiken worden nu besproken. Voeding en configuratie

Het Xilinx Virtex 5 bord wordt gevoed door 5V. Deze spanning

wordt verlaagd naar 1.0V, 1.8V en andere om zo de randapparatuur te voeden. Voor de configuratie van de Xilinx Virtex 5 zijn er verschillende mogelijkheden. De FPGA kan geconfigureerd worden van een CompactFlash kaart of door middel van USB platform kabel. Om te kiezen welke configuratie moet uitgevoerd worden bij het opstarten van de FPGA moeten we gebruik maken van DIP switches. In hoofdstuk 7.5 wordt nader bekeken hoe wij de FPGA configureerde. System RAM Het Xilinx Virtex 5 ML507 bord bevat een connector om DDR2 SDRAM geheugen aan te sluiten op het bord. Het bord ondersteunt geheugens tot een grootte van 512 MB. Op ons bord was een capaciteit aanwezig van 256MB, dit is nodig om aan beeldverwerking

44

Embedded systeem

te doen. Het interne RAM geheugen is te klein om de beelden op te slaan, daarom moet er extra geheugen voorzien zijn.

CompactFlash Controller

De System ACE CompactFlash controller maakt gebruik van

een FAT16 bestandsysteem en alleen 1 gereserveerd sector is toegelaten. Het FAT16 systeem ondersteunt partities tot een grootte van 2GB. Het xilinx.sys bestand moet aanwezig zijn in de root-directory. Het xilinx.sys bestand wordt gebruikt door de System ACE CompactFlash controller om de project structuur te defini¨eren. Deze structuur is opgebouwd uit een hoofd map die 8 sub-folders bevat. In elk van deze 8 sub folders kan men een .ace bestand opslaan. Deze ace bestanden zullen nader worden verklaard in hoofdstuk 7.5 waarin dat we configuratie van de FPGA bespreken. Andere mappen mogen ook aanwezig zijn op de CompactFlash kaart, maar de root directory mag niet meer dan 16 mappen en/of bestanden bevatten.

Figuur 6.8: Virtex-5 Blokdiagram

6.4 Conclusie Seri¨ ele poorten

45 Op het Xilinx Virtex 5 ML507 bord zijn er 3 seri¨ele poorten. Er zijn 2 PS/2

poorten en een RS-232 poort. De 2 PS/2 poorten worden gebruikt om een toetsenbord en muis aan te sluiten. Deze worden allebei gevoed door de 5V die wordt aangeboden door de voeding. De RS-232 poort wordt gebruikt voor de communicatie van seri¨ele data met een ander apparaat. Wij hebben gebruik gemaakt van deze seri¨ele poort om communicatie te voorzien met de host computer, om zo debug informatie te verkrijgen. Een 9-pin seri¨ele kabel geconnecteerd met een COM poort is nodig om de verbinding op te zetten.

6.4

Conclusie

In dit hoofdstuk hebben we uitgelegd wat een FPGA is en hoe het gebruikt kan worden om krachtige software-hardware ontwerpen te realiseren. Het bord, de Xilinx Virtex 5 ML507, dat we gebruikt hebben om dit eindwerk te kunnen realiseren, is ook in detail besproken [7, 33].

46

Embedded systeem

Hoofdstuk 7

Embedded project 7.1

Inleiding

In dit hoofdstuk wordt een overzicht gegeven van de implementatie van het Camus algoritme op het embedded systeem, namelijk de Virtex 5 ML507. In hoofdstuk 5 is het Camus algoritme uitgelegd gevolgd door een beschrijving van het embedded systeem in hoofdstuk 6. Nu wordt er in meer detail uitgelegd hoe het Camus algoritme ge¨ımplementeerd is en welke software en hardware blokken er gebruikt zijn om dit te realiseren. Eerst wordt er een algemeen overzicht gegeven van het embedded project door middel van een high-level blok diagram gevolgd door een voorstelling van het embedded project aan de hand van de gebruikte Xilinx Platform Studio software, in sectie 7.2. Daarna wordt de software implementatie in sectie 7.3 besproken gevolgd door de hardware implementatie in sectie 7.4. In sectie 7.5 wordt de configuratie van de FPGA besproken en tot slot is er nog een conclusie in sectie 7.6.

7.2

Overzicht

Eerst wordt er een overzicht gegeven van het totaal embedded project aan de hand van een highlevel blok diagram dat weergegeven is in figuur 7.1. Daarna wordt de implementatie beschreven er aan de hand van de gebruikte XPS software en gaan we dieper in op de Processor Local Bus (PLB). Het high-level blok diagram geeft een vereenvoudigd overzicht van totale project aan de hand van blokken. Elk blok stelt een stap voor van het totale proces. In het eerste blok worden de foto’s van de CompactFlash kaart naar het DDR2 SDRAM geheugen gekopieerd. Dit wordt gedaan aan de hand van voorgedefineerde C-functies van Xilinx [28]. Daarna begint het eigenlijke werk van het Camus algoritme. Dit blok is dan weer opgebouwd uit meerdere kleinere blokken. In deze kleinere blokken wordt een vereenvoudigde voorstelling gedaan van de nodige operatie om het Camus algoritme uit te voeren. Dit bestaat er in om windows te cre¨eren, gevolgd door

48

Embedded project

op deze windows een correlatie criteria uit te voeren, zoals bijvoorbeeld de Sum of Absolute Differences. Dit correlatie criteria zal er dan voor zorgen dat de beste overeenkomst wordt gekozen en dat voor deze overeenkomst de bijhorende vectoren zullen gemaakt worden. Tot slot wordt dit eindresultaat weggeschreven naar CompactFlash kaart.

Figuur 7.1: High-level blokdiagram van het complete embedded project.

Na deze voorstelling als een high-level blok diagram gaan we over naar de werkelijke implementatie gebruik makende van XPS. Het totaal embedded project bestaat uit meerdere onderdelen. Een overzicht van de gebruikte onderdelen is weergegeven in figuur 7.2, dit is het totaal embedded project zoals het voorgesteld is door de XPS. We zien in het overzicht dat er een PowerPC aanwezig is en als geheugen elementen zijn er BlockRAM en DDR2 SDRAM aanwezig. Andere hardware blokken zijn de CompactFlash kaart om gegevens extern op te slaan en voor de configuratie van de FPGA, de RS-232 UART om te voorzien in communicatie van het embedded systeem met de host PC. Vervolgens zijn er ook nog andere onderdelen zoals de LED’s, DIP switches en de push buttons. Een belangrijk hardware element is correlatie, dit is de hardware blok die die we zelf hebben ontworpen. Dit correlatie blok is beschreven in sectie 7.4. Al deze hardware blokken zijn verbonden met elkaar via de PLB bus, voorgesteld in figuur 7.3. Elke hardware blok dat verbonden is met deze bus is ofwel een master of slave. Wanneer een hardware blok een master is kan deze lezen en schrijven van en naar de bus op specifieke plaatsen. De adressen van de hardware blokken zijn instelbaar. In tabel 7.1 zijn de adressen weergegeven van de hardware blokken die gebruikt zijn in ons project.

7.2 Overzicht

Figuur 7.2: Het complete embedded project zoals voorgesteld in Xilinx Platform Studio (XPS).

Figuur 7.3: PLB bus verbindt de verschillende hardware componenten met elkaar.

49

50

Embedded project Tabel 7.1: De adressen van het embedded project (grootte in bytes)

Module

Connectie

Basisadres

Eindadres

Grootte

DDR2 SDRAM

PLB

0x00000000

0x0FFFFFF

256M

Push buttons

PLB

0x81400000

0x8140FFF

64K

DIP switches

PLB

0x81420000

0x8142FFF

64K

SysACE CompactFlash

PLB

0x83600000

0x8360FFF

64K

RS-232 UART

PLB

0x84000000

0x8400FFF

64K

Correlatie

PLB

0xC7200000

0xC720FFF

64K

BRAM 1

PLB

0xFFFFE000

0xFFFFFFF

8K

Processor Local Bus Zoals eerder vermeld is, en weergegeven is in figuur 7.2, wordt er gebruik gemaakt van de Processor Local Bus (PLB) om de verschillende blokken met elkaar te verbinden. De PLB bus maakt gebruik van 32 bit adressen en 128 bits voor de data. In figuur 7.5 wordt een blokdiagram voorgesteld van de PLB bus. De PLB bus is in staat om tot 16 master devices te beheren. Belangrijke elementen van de PLB bus zijn het Address path, Write data path, Read data en de Bus Control Unit. De Bus Control Unit zorgt voor de arbitratie en data flow van de PLB bus. De arbitratie van de PLB bus is op twee manieren in te stellen: de eerste methode maakt gebruikt van vaste prioriteiten die worden toegekend aan de randapparatuur en de tweede methode maakt gebruikt van een Round Robin arbitratie. De PLB bus werking en timing is zeer uitgebreid beschreven in [32].

Figuur 7.4: Processor Local Bus (PLB) blok diagram.

7.3 Software implementatie

7.3

51

Software implementatie

In deze sectie bespreken we de PowerPC en hoe de bronbestanden wordt gecompileerd en gelinkt tot een uitvoerbaar bestand dat we kunnen uitvoeren op het embedded platform. Eerst beginnen we met cache operaties van de PowerPC te bespreken, daarna wordt er dieper ingegaan op de compilatie en linking van de bronbestanden en tot slot worden de door ons geschreven Cbestanden kort besproken.

7.3.1

PowerPC

De PowerPC die aanwezig is op de Xilinx ML507 is een PowerPC440 die draait op 400MHz. Figuur 7.6 is een blok diagram van de PowerPC440 met zijn belangrijkste elementen. In deze figuur zien we ook de verbinding van de PowerPC met de eerder besproken 128 bit PLB bus. De manier waarop de PowerPC aan cache beheer doet is ook zichtbaar in deze figuur, namelijk een aparte cache voor data en voor instructies. Door gebruik te maken van deze cache zullen er minder referenties naar het geheugen zijn en dit zal er voor zorgen dat er een versnelling wordt gerealiseerd. Cache is eigenlijk een zeer snel en klein geheugen waarin de laatst gebruikte data en/of instructies worden opgeslagen en bevindt zich tussen de CPU en het geheugen, dit is voorgesteld in figuur 7.5. Het opslaan van de laatst gebruikte instructie of data is in veel gevallen nuttig want deze gegevens worden meestal meerdere malen door de CPU opgevraagd, een voorbeeld hiervan is een for-lus. Door gebruik te maken van cache moet de CPU de gegevens niet van extern geheugen halen maar kan hij ze rechtstreeks terug vinden in het snelle geheugen en wordt er een versnelling gerealiseerd.

Figuur 7.5: Cache

De werking van cache is als volgt: als de CPU data of instructies nodig heeft controleert hij eerst of deze aanwezig zijn in de cache, als deze aanwezig zijn in de cache gebruikt de CPU deze. Deze situatie noemen we een hit. Wanneer de gevraagde gegevens niet in de cache aanwezig zijn noemen we het miss. In deze situatie moet de CPU de gegevens van extern geheugen gaan halen en zal hij deze gegevens in de cache plaatsen om zo de volgende keer als hij deze gegevens nodig heeft hij een hit zal hebben. De PowerPC 440 heeft een Instruction Cache Controller (ICC) een Data Cache Controller (DCC) maken beiden gebruik van 32-byte lines en zijn allebei 64-way set-associative. Een

52

Embedded project

set-asscociative cache is een compromis tussen een volledige associatieve cache en een direct mapped cache. Een direct mapped cache is een cache waarbij elke geheugen blok een vaste plaats heeft. Volledige associatieve cache is het tegenovergestelded van direct mapped cache hierbij kan een geheugen blok op elke plaats worden opgeslagen. Xilinx voorziet de gebruiker van functies waarmee de beide caches kunnen gecontroleerd worden, namelijk:

void XCache EnableDCache ( unsigned int regions ); void XCache DisableDCache ( void ) ; void XCache FlushDCacheLine(unsigned int adr) ; void XCache StoreDCacheLine(unsigned int adr) ; void XCache EnableICache(unsigned int regions ); void XCache DisableICache ( void ) ; Meer informatie omtrent deze functies kan gevonden worden in [29, 30, 31].

Figuur 7.6: PowerPC 440 blok diagram

7.3 Software implementatie

7.3.2

53

Software linking

In deze sectie wordt uitgelegd hoe een uitvoerbaar bestand dat naar de FPGA kan worden gedownload is opgebouwd uit verschillende bron bestanden. De software is geschreven in de programmeertaal C. Deze C bestanden moeten gecompileerd worden voor het embedded systeem. Hierbij moet rekening gehouden worden met geheugen indeling van het embedded systeem. Elk C programma gebruikt meerdere secties. In tabel 7.2 zijn enkele van de belangrijke sectie van het C programma opgesomd, besproken en wordt er een voorbeeld gegeven in C-code. Tabel 7.2: Verschillende secties van een programma

Sectie

Beschrijving

Voorbeeld (in C-code)

.text

Tekst sectie

i += 1;

.data

Data sectie (lezen/schrijven)

int i[4] = 1, 2, 3, 4;

.sdata

Kleine data sectie (lezen/schrijven)

.rodata

Read-Only sectie

const int j = 6;

.bss

Niet-ge¨ınitialiseerde data sectie

int k;

.sbss

Kleine niet-ge¨ınitialiseerde data sectie

Deze C bestanden moeten dus worden omgezet in een uitvoerbaar bestand voor uitvoering in het embedded systeem. In figuur 7.7 is een overzicht weergegeven van welke stappen er nodig zijn om van een C-bronbestand naar een executable bestand te gaan. De eerste stap is dat de Cbronbestanden (.c bestanden) worden gecompileerd tot objecten (.o bestanden). Deze objecten worden dan samengevoegd tot een object door de linker en dan wordt er een uitvoerbaar bestand (.elf bestand) gemaakt. De linker maakt gebruik van een linker script dat aangeeft waar elke sectie van het C-programma, zoals degene voorgesteld in tabel 7.2, moet geplaatst worden in het fysieke geheugen. Door middel van het linker script kan er dus aangegeven worden waar elke sectie moet worden opgeslagen zoals in het externe DDR2 SDRAM geheugen of de interne BlockRAM. Bepaalde secties zoals de .sdata en de .sbss moeten een aangesloten geheugenruimte hebben. De .boot sectie bepaalt waar het programma begint in het geheugen. In figuur 7.8 is een stuk van het gebruikte linkerscript weergegeven.

7.3.3

C-bestanden

In deze sectie wordt het software gedeelte van de implementatie besproken. Het volledige project bestaat uit meerdere C-bestanden die dan worden samengevoegd zoals besproken in sectie 7.3.2. De verschillende C-bestanden die geschreven zijn als volgt: • main.c: Dit is het hoofdprogramma waarin alle andere functies worden opgeroepen

54

Embedded project

Figuur 7.7: Van C naar uitvoerbaar bestand.

• inlees routine.c:

Dit bestand bevat de functie om de foto van de CompactFlash kaart

naar het geheugen te schrijven. • Camus.c: Dit bestand bevat de functies om het Camus algortime te berekenen. • utilities.c:

Dit bestand bevat verschillende functies die nodig zijn voor het Camus.c be-

stand, zoals vullen van de Windows en tekenen van lijnen,... • main.h: Functie en variabele declaraties voor het main.c bestand. • utilities.h: Functie en variabele declaraties voor het utilities.c bestand. • correlatie.h: Functie en variabele declaraties om te kunnen lezen en schrijven van en naar register van het correlatie hardware blok.

De verschillende functies die gebruikt zijn in de C-bestanden zijn weergegeven in bijlage D.

7.3 Software implementatie

Figuur 7.8: Het gebruikte linkerscript.

55

56

7.4

Embedded project

Hardware implementatie

In deze sectie word besproken welke delen er in hardware zijn ge¨ımplementeerd en hoe dit aangepakt is geweest. Om een versnelling te realiseren is er een stuk van het Camus algoritme ge¨ımplementeerd in hardware. Het stuk dat gekozen is geweest om te implementeren is het correlatie criteria, zie figuur 7.1 en figuur 7.9. Het correlatie criteria voert de eigenlijke berekeningen uit die nodig zijn voor het Camus algoritme. Dit is het belangrijkste onderdeel van het Camus algoritme.

Figuur 7.9: Correlatie criteria wordt in hardware ge¨ımplementeerd.

We hebben een nieuwe Intellectual Property (IP) gecre¨eerd en aan het systeem toegevoegd. Deze nieuwe IP is genaamd correlatie en is terug te vinden in figuur 7.2. Deze IP bestaat uit een aantal registers en is verbonden via de PLB bus met de rest van het systeem. Door gebruikt te maken van C-functies kunnen we lezen en schrijven van en naar de registers van het correlatie hardware blok. Deze lees- en schrijf functies zijn hieronder voorgesteld: void CORRELATIE mWriteReg(Xuint32 BaseAddress, unsigned RegOffset, Xuint32 Data); Xuint32 CORRELATIE mReadReg(Xuint32 BaseAddress, unsigned RegOffset) ; Het probleem dat hierbij te voorschijn komt is dat we in het correlatie hardware blok kunnen lezen van het register, maar niet kunnen schrijven naar deze registers. Nu is het gewenst dat de resultaten die berekend worden in deze hardware blok kunnen uitgelezen worden door de software kant van het embedded systeem. Daarom is de functionaliteit van enkele van deze registers aangepast geweest zodat er in hardware naar deze register kan geschreven worden. Nu zijn er twee soorten registers aanwezig in het correlatie blok: de eerste soort registers kunnen

7.4 Hardware implementatie

57

vanuit software gelezen en geschreven worden en in hardware enkel gelezen worden. De tweede soort registers kunnen in software enkel gelezen worden en in hardware gelezen en geschreven worden. Hoe dit uitgevoerd geweest is kan in meer detail gevonden worden in [23].

Figuur 7.10: Blokdiagram van de gecre¨eerde correlatie hardware blok.

In de figuur 7.10 is een blokdiagram weergegeven van het correlatie hardware blok die wij gecre¨eerd hebben. We zien dat dit blok verbonden is met de PLB bus en bestaat uit registers en een berekeningseenheid. Deze registers hebben een grootte van 32 bit. Het hardware blok werkt in 3 stappen: eerst worden de input pixels vanuit de software naar de hardware weggeschreven. Daarna start de berekening, tot slot worden de resultaten terug naar de software gestuurd. Hoe elk van de 3 stappen ge¨ımplementeerd is wordt hieronder besproken.

58

Embedded project

Stap 1: De pixels van het window worden vanuit de software weggeschreven naar de registers van het correlatie hardware blok. Deze pixels kunnen een waarde hebben die gelegen is tussen 0-255 (enkel positief), dit is voor te stellen met 8 bits (28 = 256 waarden). Dus theoretisch gezien zouden we vier pixels in een register kunnen wegschrijven zoals weergegeven is in figuur 7.11(a). De opmerking die we hier moeten maken is dat de berekeningen die we gaan uitvoeren in de berekeningseenheid verwachten dat we gaan werken met signed waarden. Dit wil zeggen dat we ook negatieve getallen kunnen voorstellen en dat er gebruikt wordt gemaakt van de Two’s Complement notatie. Hierdoor kunnen we geen gebruik maken van de 8 bits voorstelling zoals in figuur 7.11(a), omdat we een tekenbit moeten voorzien. Daardoor worden onze pixels nu voorgesteld door 9 bits zoals weergegeven in figuur 7.11(b), met als nadeel dat we per register maar drie pixels kunnen opslaan. Op het einde van stap 1 hebben we 2 windows ingeladen in de registers van het correlatie blok.

Figuur 7.11: (a)Register is 32 bit groot. (b) Hoe wij het register hebben ingevuld.

Stap 2: In stap 2 worden de effectieve berekeningen uitgevoerd. Dit noemen we de berekeningseenheid. De berekeningseenheid zelf is opgebouwd rond een Finite-state Machine (FSM). Een FSM is een eindige toestandsmachine en bestaat uit drie delen namelijk: een eindig aantal states, overgangen tussen die toestanden en acties. Het principe van een FSM is dus dat er een huidige toestand is en een volgende toestand. De volgende toestand wordt dan bepaald op basis van voorwaarden. Er zijn twee soorten FSM namelijk: Moore of Mealy. Moore maakt enkel gebruik van de toestand

7.4 Hardware implementatie

59

om de output te bepalen, Mealy maakt gebruikt van de toestand en de input om de output te bepalen. In figuur 7.12 is weergegeven welke toestanden de ge¨ımplementeerde FSM heeft, welke signalen er nodig zijn om naar de volgende state te gaan en wat de volgende state is. Er zijn drie toestanden en er moet enkel een start bit worden geset om de state machine te starten. Deze start bit is eigenlijk een controle register dat we zelf gecre¨eerd hebben en waar we naartoe schrijven vanuit de software. Zodra de start bit geset is wordt er naar toestand 2 gegaan waar de eigenlijke berekeningen worden uitgevoerd. Vanuit toestand 2 wordt er zonder voorwaarden naar toestand 3 gegaan waarin de berekende waarde wordt weggeschreven naar de registers en wordt er terug naar toestand 1 gegaan.

Figuur 7.12: Finite-state machine (FSM) ge¨ımplementeerd in hardware.

Stap 3: Vanuit de software kunnen we nu de door hardware berekende waarde opnieuw inlezen en verder verwerken.

60

7.5

Embedded project

Configuratie van de FPGA

De configuratie van de FPGA kan op verschillende manieren gebeuren. Een eerste methode is gebruik makend van de JTAG kabel die het bit bestand download naar het bord en gebruik makend van de Xilinx Microprocessor De-bugger omgeving (XMD) kan het software uitvoerbaar bestand gedownload worden naar het bord. De tweede methode maakt gebruik van de PROM die aanwezig zijn op het bord. Door gebruik te maken van Xilinx iMPACT software worden de bit file en het software uitvoerbaar bestand naar de PROM gedownload. Op deze methode kunnen twee configuratie opgeslagen worden en door gebruik te maken van de DIP switches kan er gekozen worden dewelke er zal uitgevoerd worden. De manier waarop wij dit hebben uitgevoerd is gebruik makend van de CompactFlash kaart om de FPGA te configureren door middel van de System ACE CF controller, dit is de derde methode. Het bit bestand en het software uitvoerbaar bestand worden dan door middel van een script genace in de XMD omgeving omgezet in ace formaat dat opgeslagen kan worden op de CF kaart. Op de CF kaart kunnen zo tot 8 .ace bestanden opgeslagen worden. Aan de hand van de DIP switches kan dan gekozen worden welk ace bestand er moet worden ingeladen bij het opstarten van de FPGA. Er moet wel opgemerkt worden dat de CompactFlash kaart moet geformatteerd worden in het FAT16 (File Allocation Table) formaat.

7.6

Conclusie

In dit hoofdstuk hebben we een overzicht gegeven van het totale embedded project. We hebben de software kant besproken en het door ons gecre¨eerde hardware blok. We hebben in detail besproken hoe het hardware blok opgebouwd is, hoe we de register functionaliteit hebben aangepast van dit hardware blok en hoe we de FSM in het hardware blok hebben ge¨ımplementeerd. Er is ook besproken hoe we een uitvoerbaar bestand maakten opgebouwd uit verschillende Cbestanden door gebruikt te maken van het linkerscript. Hoe het cache systeem van de PowerPC werkt is ook in detail besproken.

Hoofdstuk 8

Resultaten en Conclusie 8.1

Inleiding

Dit hoofdstuk begint met een overzicht van de gebruikte resources in sectie 8.2, gevolgd door een bespreking van de verzamelde resultaten in sectie 8.3 en tot slotte nemen we een conclusie in sectie 8.4.

8.2

Gebruikte resources

In deze sectie bespreken we de gebruikte resources van de Xilinx Virtex 5. De implementatie van het Camus algoritme op het embedded platform heeft gebruikt gemaakt van de PowerPC440 die aanwezig is. In tabel 8.1 is een overzicht gegeven van de gebruikte resources. Het totaal aan gebruikte IOB is gelijk aan 36%. De BlockRAM’s zijn gebruikt voor 4%. Tabel 8.1: Gebruikte resources van de FPGA.

FPGA utilisatie

Gebruikt

Beschikbaar

Procent gebruikt

BlockRAM

6

148

4%

PPC440

1

1

100%

IOBs

233

640

36%

Slice Flip Flops

4,803

44,800

10%

DCM

1

12

8%

Slice LUTs

4,443

44,800

9%

→ als logic

4,275

→ als Memory

158

→ als route-thru

54

62

8.3

Resultaten en Conclusie

Resultaten

In tabel 8.2 is een overzicht weergegeven van de resultaten behaald met de FPGA om optical flow te berekenen door gebruik te maken van het Camus algoritme. We vergelijken hier de software versie op FPGA, waarbij het Camus algoritme op de PowerPC in de FPGA wordt uitgevoerd, met de hardware versie op FPGA, waarbij we een gedeelte van het algoritme in hardware laten uitvoeren. Een grafische voorstelling van tabel 8.2 is weergegeven in de figuren 8.3 en 8.4. De gegevens in tabel 8.2 zijn berekend voor een afbeelding met dimensies van 376 × 282 en in grijswaarden. De figuren die gebruikt zijn voor de tests uit te voeren zijn terug te vinden in bijlage C.

We kunnen concluderen dat als we de FPGA software versie zonder cache vergelijken met de hardware versie zonder cache dat de hardware versie sneller is dan de FPGA software versie. Dit is ten gevolge van de hardware implementatie van het correlatie criteria. Het verschil tussen de FPGA software versie zonder cache en de hardware versie zonder cache is beperkt ten gevolge van geheugen transfers. Hiermee bedoelen we dat het transfereren van de gegevens van en naar de registers van het correlatie blok het meeste tijd in beslag neemt. Geheugen transfers nemen in totaal bij de hardware 2.45 microseconden in. De berekeningen zelf, die worden uitgevoerd op de register, in hardware nemen in totaal 0.03 microseconden in. Als we de berekening in de software bekijken komen we uit op 3.5 microseconden. Er is dus een groot verschil tussen de berekeningstijd nodig in software en hardware, maar deze wordt teniet gedaan door de geheugen transfers. We hebben dus een reductie van 3.47 microseconden per berekening gerealiseerd. Deze vergelijking is grafisch voorgesteld in figuur 8.1.

Als we de resultaten vergelijken tussen de FPGA software versie met cache en de hardware versie met cache zien we dat FPGA software versie sneller is dan de hardware versie. Dit is komt doordat de gegevens voor de FPGA software versie terug te vinden zijn in de cache en dat er minder geheugen transfers nodig zijn. Dit kunnen we concluderen ten gevolge van de meting die we hebben uitgevoerd. Zonder cache zijn er 3.5 microseconden nodig om de berekeningen uit te voeren, met cache is dit teruggedrongen tot 0.23 microseconden. Dit is nog altijd meer dan de 0.03 microseconden die we nodig hebben in de hardware versie, maar we hebben 0.66 microseconden nodig om aan de geheugen transfers te doen in hardware en zo bekomen we tragere resultaten. Dus ook hier hebben we een versnelling van 0.20 microseconden gerealiseerd ten opzichte van de FPGA software versie. Een grafische voorstelling is weergegeven in figuur 8.2

In tabel 8.3 zijn de resultaten weergegeven van het Camus algoritme uitgevoerd op de FPGA en op de PC. Een grafische voorstelling van tabel 8.3 is weergegeven in figuur 8.5. De PC is een Intel Core 2 Duo met een CPU geklokt op 2,6 GHz en 2 GB 667 MHz DDR2 SDRAM geheugen.

8.3 Resultaten

63

Figuur 8.1: Vergelijking van de tijd, in microseconden, nodig voor de berekening van het correlatie criteria zonder cache.

Figuur 8.2: Vergelijking van de tijd, in microseconden, nodig voor de berekening van het correlatie criteria met cache.

Het besturingssysteem op deze PC is Mac OS X. We zien aan de hand van deze resultaten dat de FPGA trager is dan de PC. Dit is ten gevolge van het feit dat de PowerPC te veel geheugen transacties moet uitvoeren en dat de PC beschikt over Direct Memory Acces (DMA). De vele geheugen transacties zouden vermijden kunnen worden door een hardware implementatie die zelf de pixels rechtstreeks uit het extern geheugen zou gaan halen. Hierdoor vermijden we de omweg via de processor te moeten gebruiken. Na deze resultaten bekeken te hebben kunnen we ook concluderen dat het idee achter het Camus algoritme, namelijk de zoektocht in 2-dimensies in plaats van in 1-dimensie om zo de tijd te reduceren, inderdaad juist is. We zien dat het langer duurt om een een verplaatsing van 5 pixels te berekenen op 1 frame, dan een verplaatsing van 1 pixel op 5 frames. Door gebruik te maken van de oudere frames kunnen we onze zoektocht in de oppervlakte beperkt houden en zo tijd besparen.

64

Resultaten en Conclusie

Tabel 8.2: Resultaten voor Camus uitgevoerd op de FPGA in seconden. Verplaatsing geeft de maximum verplaatsing van de pixel aan. Frames is het aantal frames dat gebruikt is om met te vergelijken.

Verplaatsing

1

2

3

4

5

Frames

Software

Hardware

Met cache

Zonder cache

Met cache

Zonder cache

1

0.57

7.19

0.74

7.09

2

1.07

13.57

1.39

13.34

3

1.60

20.20

2.07

19.76

4

2.14

26.85

2.72

25.96

5

2.68

33.47

3.38

32.32

1

1.48

18.93

1.88

18.23

2

2.96

37.53

3.73

35.88

3

4.43

56.11

5.57

53.53

4

5.90

74.71

7.41

71.17

5

7.38

93.30

9.25

88.82

1

2.83

36.77

3.64

35.16

2

5.77

77.65

7.24

70.31

3

8.65

116.29

10.84

105.18

4

11.53

154.94

14.44

140.05

5

14.41

193.59

18.04

174.92

1

4.58

59.76

5.99

57.68

2

9.52

127.99

11.93

128.32

3

14.28

191.79

17.87

192.18

4

19.04

255.61

23.81

256.03

5

23.80

319.41

29.75

319.88

1

7.11

92.8

8.91

85.79

2

14.21

191.00

17.78

191.27

3

21.32

286.30

26.65

286.59

4

28.42

381.61

35.51

381.94

5

35.52

476.92

44.38

477.27

8.3 Resultaten

65

Tabel 8.3: Vergelijking van PC versus FPGA uitgedrukt in seconden.Verplaatsing geeft de maximum verplaatsing van de pixel aan. Frames is het aantal frames dat gebruikt is om met te vergelijken.

Verplaatsing

1

2

3

4

5

Frames

FPGA

PC

1

0.57

0.13

2

1.07

0.27

3

1.60

0.38

4

2.14

0.52

5

2.68

0.63

1

1.48

0.36

2

2.96

0.70

3

4.43

0.95

4

5.90

1.28

5

7.38

1.57

1

2.83

0.67

2

5.77

1.23

3

8.65

1.88

4

11.53

2.49

5

14.41

3.25

1

4.58

1.11

2

9.52

2.02

3

14.28

3.05

4

19.04

4.10

5

23.80

4.97

1

7.11

1.47

2

14.21

3.06

3

21.32

4.44

4

28.42

5.87

5

35.53

7.68

66

Resultaten en Conclusie

Figuur 8.3: Grafische voorstelling van de gegevens in tabel 8.2. Op de Y-as is de tijd (in sec) weergegeven en op de X-as het aantal frames. Deze grafiek stelt de gegevens voor de software versie voor.

Figuur 8.4: Grafische voorstelling van de gegevens in tabel 8.2. Op de Y-as is de tijd (in sec) weergegeven en op de X-as het aantal frames. Deze grafiek stelt de gegevens voor de hardware versie voor.

8.4 Conclusie

67

Figuur 8.5: Grafische voorstelling van de gegevens in tabel 8.3. Op de Y-as is de tijd (in sec) weergegeven en op de X-as het aantal frames. Deze grafiek stelt de vergelijking voor tussen de resultaten behaald op de FPGA versus de PC.

8.4

Conclusie

De doelstellingen van deze masterproef waren: het uitvoeren van een grondige literatuurstudie, het implementeren van het Camus algoritme op een embedded platform en het realiseren van een speed-up. We zijn geslaagd in 2 van onze 3 doelen. De literatuurstudie is grondig uitgevoerd geweest. Op basis van deze literaatuurstudie is dan een reflection paper ingediend bij de IADIS Computer Graphics, Visualization, Computer Vision and Image Processing (CGVCVIP) Conferentie en is aanvaard geweest. Op basis van deze literatuurstudie is dan een algoritme gekozen om te implementeren op een embedded platform. Het gekozen algoritme was het Camus algoritme en we waren succesvol bij het implementeren van dit algoritme op de Xilinx Virtex 5. De speed-up doelstelling is daarentegen niet gehaald geweest. We hebben gebruikt gemaakt van verschillende technieken om deze speed-up te realiseren. We hebben een eigen Intellectual property (IP) gecre¨eerd in hardware met een versnelling ten opzichte van de software versie. We hebben ook gebruik gemaakt van de cache die we konden activeren op het embedded platform en hebben hierbij een grootte versnelling opgemerkt. Wat we gerealiseerd hebben in deze thesis is het volgende:

1. Grondige literatuurstudie van optical flow

68

Resultaten en Conclusie 2. Publicatie van een paper 3. Grondige kennis van het Camus algoritme 4. Leren maken van hard- en software ontwerpen op een embedded platform gebruik makende van Xilinx software 5. Grondige kennis van de Xilinx Virtex 5 ML507 6. Implementatie van correlatie criteria in hardware (VHDL) 7. Implementatie van het Camus algoritme in software

Bibliografie [1] Commision of the european communities, european road safety action programme: midterm review. Report of the European Commission, 2006. [2] P.C. Arribas and F.M.H. Macia. FPGA implementation of Santos-Victor optical flow algorithm for real-time image processing: an useful attempt. In Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, JF Lopez, JA Montiel-Nelson, and D. Pavlidis, Eds, volume 5117, pages 23–32. Citeseer. [3] S. Baker, D. Scharstein, JP Lewis, S. Roth, M.J. Black, and R. Szeliski. A database and evaluation methodology for optical flow. In Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, pages 1–8. IEEE, 2007. [4] JL Barron, D.J. Fleet, and SS Beauchemin. Performance of optical flow techniques. International journal of computer vision, 12(1):43–77, 1994. [5] S.S. Beauchemin and J.L. Barron. The computation of optical flow. ACM Computing Surveys (CSUR), 27(3):466, 1995. [6] J.M. Bodily. An Optical Flow Implementation Comparison Study. PhD thesis, Brigham Young University, 2009. [7] S. Brown and J. Rose. Architecture of fpgas and cplds: A tutorial. IEEE Design and Test of Computers, 13(2):42–57, 1996. [8] A. Bruhn, J. Weickert, and C. Schn¨orr. Lucas/Kanade meets Horn/Schunck: Combining local and global optic flow methods. International Journal of Computer Vision, 61(3):211– 231, 2005. [9] T. Camus. Real-time quantized optical flow. In camp, page 126. Published by the IEEE Computer Society, 1995. [10] Theodore Armand Camus. Real-time optical flow. PhD thesis, 1994. [11] R. Cutler and M. Turk. View-based interpretation of real-time optical flow for gesture recognition. In Automatic Face and Gesture Recognition, 1998. Proceedings. Third IEEE International Conference on, pages 416–421. IEEE, 2002.

70

BIBLIOGRAFIE

[12] Q. Duan, E.D. Angelini, S.L. Herz, C.M. Ingrassia, O. Gerard, K.D. Costa, J.W. Holmes, and A.F. Laine. Evaluation of optical flow algorithms for tracking endocardial surfaces on three-dimensional ultrasound data. In SPIE International Symposium, Medical Imaging, volume 5750. Citeseer, 2005. [13] B. Galvin, B. McCane, K. Novins, D. Mason, and S. Mills. Recovering motion fields: An evaluation of eight optical flow algorithms. In British Machine Vision Conference, volume 1, pages 195–204. Citeseer, 1998. [14] B.K.P. Horn and B.G. Schunck. Determining optical flow. Artificial intelligence, 17(13):185–203, 1981. [15] J.J. Little and A. Verri. Analysis of differential and matching methods for optical flow. In Visual Motion, 1989., Proceedings. Workshop on, pages 173–180. IEEE, 2002. [16] H. Liu, T.H. Hong, M. Herman, and R. Chellappa. Accuracy vs. efficiency trade-offs in optical flow algorithms. Computer Vision—ECCV’96, pages 174–183, 1996. [17] B.D. Lucas and T. Kanade. An iterative image registration technique with an application to stereo vision. In International joint conference on artificial intelligence, volume 3, pages 674–679. Citeseer, 1981. [18] B. McCane, K. Novins, D. Crannitch, and B. Galvin. On benchmarking optical flow. Computer Vision and Image Understanding, 84(1):126–143, 2001. [19] Nakayama. The aperture problem in apparent motion. [20] M. Otte and H.H. Nagel. Estimation of optical flow based on higher-order spatiotemporal derivatives in interlaced and non-interlaced image sequences. Artificial Intelligence, 78(12):5–43, 1995. [21] Robyn Owens. Optical flow. Computer Vision IT412 : Department of Computer Science, 1997. [22] E.P. Simoncelli, E.H. Adelson, Massachusetts Institute of Technology. Media Laboratory. Vision, and Modeling Group.

Computing optical flow distributions using spatio-

temporal filters. Citeseer, 1991. [23] Deian Stefan. Adding a custom IP to PowerPC using Xilinx XPS - A very Short tutorial, 1 August 2009. [24] D. Sun, S. Roth, J. Lewis, and M. Black. Learning optical flow. Computer Vision–ECCV 2008, pages 83–97, 2008. [25] H. Top. Optical flow en bewegingillusies. Order, 501:2982.

BIBLIOGRAFIE

71

[26] C.J. Tsai, N.P. Galatsanos, and A.K. Katsaggelos. Optical flow estimation from noisy data using differential techniques. In Acoustics, Speech, and Signal Processing, 1999. ICASSP’99. Proceedings., 1999 IEEE International Conference on, volume 6, pages 3393–3396. IEEE, 2002. [27] S. Uras, F. Girosi, A. Verri, and V. Torre. A computational approach to motion perception. Biological Cybernetics, 60(2):79–87, 1988. [28] Xilinx. FATFile System(FATfs). Xilinx. [29] Xilinx. Virtex-5 FXT PowerPC P440 and MicroBlaze edition Kit Reference Systems. Xilinx, 1.2.1 edition, July 30 2009. [30] Xilinx. Embedded Processor Block in Virtex-5 FPGAs. Xilinx, v1.8 edition, February 24 2010. [31] Xilinx. OS and Libraries Document Collection. Xilinx, April 19 2010. [32] Xilinx. Processor Local Bus (PLB) v4.6. Xilinx, 1.05a edition, September 21 2010. [33] Xilinx. Virtex-5 FPGA User Guide. Xilinx, 5.3 edition, May 17 2010.

72

BIBLIOGRAFIE

Bijlagen

Bijlage A

Paper Rome In dit hoofdstuk van de bijlage bevindt zich de paper die ingediend is voor de IADIS Computer Graphics, Visualization, Computer Vision and Image Processing (CGVCVIP) 2011 Conferentie. Deze paper is aanvaard als een reflection paper en er zal een presentatie worden gegeven tijdens de conferentie.

A COMPARISON OF OPTICAL FLOW TECHNIQUES FOR A BLIND SPOT CAMERA Lorenz Van den Heuvel, Kristof Van Beeck, Toon Goedemé Lessius Mechelen, Association K.U. Leuven Jan De Nayerlaan 5, 2860 Sint-Katelijne-Waver, Belgium [email protected] [email protected] [email protected]

ABSTRACT In this paper we present an overview and comparison of the most important optical flow calculation techniques. Our comparison is based upon three aspects: accuracy, speed and robustness against noise. Based on the results of our comparison, we determine which of the algorithms is best suited for real-time implementation on dedicated hardware. This decision is based on the trade-off that we found between our evaluation aspects. In the future we will use this result to achieve the automatic detection of vulnerable road users using a blind spot camera. KEYWORDS Computer vision, object recognition, optical flow, quantitative comparison.

1. INTRODUCTION The work in this paper is part of an ongoing research project that aims on reducing accidents with trucks caused by the so-called blind spot area (figure 1(a)). Using a blind spot camera, represented in figure 1(b), our goal is the automatic detection of vulnerable road users. Therefore, this research focuses on object recognition under harsh conditions, meaning that the objects of interest, the pedestrians and other road users, as well as the camera are moving and that the time for recognition of these objects is extremely short. The problem that emerges is that simple object recognition techniques, such as background subtraction, need a constant background. We need a more advanced approach for object recognition. The chosen approach is independent motion segmentation based on optical flow. Motion segmentation is the partitioning of an image into regions of the same pixel motion. The goal of this paper is to get an in-depth look at optical flow techniques and to choose the best suited technique for real–time implementation on dedicated hardware such as a Field Programmable Gate Array. We take a close look on which techniques exist, and what their advantages and disadvantages are. Based on these results, we select the optimal optical flow algorithm that suits our application. This decision is based upon the techniques ability to generate optical flow in real–time and its capability for independent motion segmentation. The final goal of this work is to build a real-time demonstrator that can detect pedestrians and other vulnerable road-users using optical flow and independent motion segmentation. In section 2 we give an introduction of optical flow, followed by the comparison of optical flow techniques in section 3. In section 4 we state our conclusion from this study.

Figure 1. (a) Blind spot of a truck. (b) Blind spot camera mounted on truck. (c) And (d) are test frames of the blind spot camera.

2. OPTICAL FLOW The goal of this study is to look at the different techniques that exist to calculate the optical flow. We look for the best technique that is most suitable for real-time implementation in dedicated hardware with respect to the accuracy and speed, and that can be adequately adapted to perform independent motion segmentation. Optical flow is a vector representation of the movement of each pixel in two successive frames. Figure 2(a) and 2(b) are two frames of the Yosemite sequence. Figure 2(c) represents the result of an optical flow algorithm on this sequence. Optical flow techniques can be categorized into 4 groups (Barron et al. (1994)):

Figure 2. (a) And (b) are 2 frames from the Yosemite sequence. (c) Is the optical flow field for (a) and (b).

Differential techniques are based upon partial differentials of the intensity in the spatial and time domain. Differential techniques themselves are then again divided into three groups: local, global and combined techniques. Local techniques, such as Lucas & Kanade (1981), try to maximize a local energy expression while global techniques, like Horn and Schunk (1981), try to minimize a global energy expression. The key assumption that is made when using differential techniques is brightness constancy. This means that the intensity of the pixels from 2 successive frames may not change, represented by equation 1. Where I(x,y,t) is the intensity of a pixel on x,y in the spatial domain and t in the time domain.

I ( x, y, t ) = I ( x + dx, y + dy, t + dt )

(1)

Correlation techniques compare a window from frame 1 with a window from frame 2. A window is a neighborhood of pixels. They search for the best match in correlation between two windows, using a correlation criterion. Examples of such correlation criteria are SSD (Sum of Squared Differences) and SAD (Sum of Absolute Differences). There are two parameters that are important when using correlation techniques: firstly the size of the window and secondly the size of the displacement of the window. Some well-known correlation techniques are introduced by Anadan (1987) and Camus (1997). Energy techniques use velocity-tuned filters. These filters are adjustable for specific frequency ranges. This means that filters respond with a high (energy) output when they perceive frequencies for which they are sensitive. This output is used to calculate the optical flow field. An example of an energy algorithm is Heeger (1988). Phase techniques use band-pass velocity-tuned filters to calculate optical flow. Band-pass filters are used to separate the input image accordingly to scale, speed and orientation. Waxman, Fleet and Jepson (1990) are examples of phase-based techniques.

3. COMPARISON OF OPTICAL FLOW TECHNIQUES The comparison of the optical flow techniques in this section is separated into three parts. Each part presents the performance of the different optical flow techniques based on a specific characteristic: accuracy, speed and robustness against noise. These results are obtained by an in-depth literature study that we performed, and thus summarizes results from several authors (Barron et al (1994), H.Top (2007), Lui et al (1996)) . Table 1. Summary of results from the Yosemite sequence Technique

Average Error

Standard deviation

Density

Horn & Schunck Lucas & Kanade (!2 " 1.0) Uras et al. (det(H) > 1.0 ) Nagel

32.43° 4.10° 6.73° 11.71°

30.28° 9.58° 16.01° 10.59°

100% 35.1% 14.7% 100%

Anadan Singh (Step 2, n = 2, w = 2)

15.84° 13.16°

13.46° 12.07°

100% 100%

Heegher (combined)

11.74°

19.04°

44.8%

Waxman et al. (#f = 2.0) Fleet and Jepson ($ = 1.25)

20.32° 4.95°

20.60° 12.39°

7.4% 30.6%

Differential

Correlation Energy Phase

3.1 Accuracy The accuracy of an optical flow algorithm is measured by the average angular error and the density it produces. The angular error is calculated as stated in equation 2. In table 1 the results are shown of tests conducted by Barron et al. (1994).

LI I EA ! cos <1 (c. e)

(2)

From these results we can conclude some interesting facts. Firstly there is a noticeable difference between global and local differential techniques. Global techniques deliver good density but a large average error, the opposite is true for local techniques. Secondly, correlation-based techniques have an average error that is reasonable while having dense fields. Thirdly, the energy-based techniques deliver poor results both on average error and density. Finally we can determine that the phase-based techniques deliver the best results with respect to the average error and density, therefore these phased-based techniques are the most interesting for accurate optical flow.

3.2 Speed Lui et al. (1996) did research into the speed aspect of optical flow techniques. They displayed the techniques in Accuracy-Efficiency graphs (AE graphs), where they plotted the error in degrees on the x-axis and the efficiency in seconds/frame on the y-axis. Figure 3 represents the different types of optical flow techniques in an AE graph. We see that the phase-based techniques, which delivered outstanding results in the tests

Figure 3. 2-D performance diagram for Diverging Trees sequence.

Figure 4. Influence of noise on the performance.

conducted by Barron et al. (1994), here also deliver good accuracy but have a very bad time-complexity. This means that the time needed to calculate the optical flow is very large. Differential techniques deliver better time results but also have a larger error rate. Correlation techniques deliver the best time-complexity of them all, with accuracy varying accordingly to the size of the window used. From these results we can conclude that the optical flow techniques with the best time-complexity are the correlation-based techniques followed by the differential-based techniques.

3.3 Robustness against noise A very important factor at which we also looked at is the robustness against noise. In many real-life situations variations in light conditions may occur, which result in a change of brightness. Figure 4, from H.Top (2007), represents the performance of the different techniques after introduction of noise. The results reveal that the differential-based techniques are the worst of them all. This results in the usage of brightness constancy as mentioned in section 2. The correlation and energy-based techniques are not affected by noise or the change in brightness because they don’t rely on brightness constancy.

4. CONCLUSIONS After reviewing the result of section 3, we can come to some very interesting conclusions. There is an obvious difference between techniques that deliver good accuracy and those that deliver good timecomplexity. The accuracy declines with increasing speed. It has also the ability of being very robust under different circumstances. Energy and phase-based techniques have very good accuracy, but very bad time complexity. As we are looking for optical flow techniques that could be implemented in real-time, energy and phase-based technique are not suited for our goal. The choice remains between differential and correlation-based techniques. Differential based techniques are less accurate than energy/phase-based techniques but are more accurate than correlation-based techniques. A major drawback is that they are sensitive to noise and brightness variation. They are usually implemented with a pre-smoothing step to resolve the noise factor. Correlation techniques have the advantage that they are more robust in real-life situations, only use integer computation and are not affected by the brightness constancy factor. This makes correlation-based techniques the ideal choice to use for dedicated hardware implementation. We chose specifically for the Camus correlation technique because it has a very good time–complexity, as we have seen in section 3, and acceptable accuracy. In our future work we plan to implement the Camus (1997) correlation technique on an FPGA and build a real-time demonstrator that will detect vulnerable road-users using independent motion segmentation. We built a test set-up with a blind spot camera on a Volvo truck and recorded 8000 frames. Figure 1(c) and (d) are examples of such test frames.

REFERENCES Barron et al., 1994. Performance of optical flow techniques.Int. Jour. of computer vision,Vol. 2,No. 1,pp 43-77, Springer. Fleet, D.J. and Jepson, A.D.,1990. Computation of component image velocity from local phase information, International Journal of Computer Vision, Vol. 5, No.1, pp 77-104 Heeger, D.J., 1988. Optical flow using spatiotemporal filters. Int. Jour. of Computer Vision, Vol. 17, No.4, pp 279-302 Horn, B.K.P. and Schunck, B.G., 1981. Determining optical flow, Artificial intelligence, Vol. 17, No. 1-3,pp 185-203. H.Top., 2007. Optical flow en bewegingillusies. University of Groningen. Faculty of Mathematics & Natural Sciences Lui et al., 1996. Accuracy vs. efficiency trade-offs in optical flow algorithms. Computer Vision-ECCV'96 ,pp 174-183. Lucas, B.D. and Kanade, T., 1981. An iterative image registration technique with an application to stereo vision, International Joint Conference on Artificial Intelligence, Vol. 3, 674-679, Citeseer P.Anadan, 1987. Measuring Visual Motion From Image Sequences, PhD dissertation and COINS Technical Report 8721, University of Massachusetts T. Camus, 1997. Real-time quantized optical flow, J. Real-Time Imaging 3, 71–86.

80

Paper Rome

Bijlage B

Embedded systeem overzicht

Bijlage C

Afbeeldingen Hieronder zijn de figuren weergegeven die wij gebruikt hebben om onze testresultaten te verzamelen.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

84

Afbeeldingen

Bijlage D

C-Functies main.c void ReadImage(char *ImageFileName, Xuint32 address); char *ReadImagePtr(char *ImageFileName, Xuint16 column, Xuint16 row); char *ReadImagePtr2(char *ImageFileName, Xuint16 column, Xuint16 row); char *Camus (char *Image1,char *Image2,char *Image3, char *Images[], int t , int displac); utilities.c void FillWindow(int dimX,int dimY, int disX, int disY, int plaatsX, int plaatsY,char *Image,int *Window); void FillWindow1(int dimX,int dimY, int disX, int disY, int plaatsX, int plaatsY,char *Image,int *Window); void FillWindow2(int dimX,int dimY, int disX, int disY, int plaatsX, int plaatsY,char *Image,int *Window); void DrawLine(int r1, int c1, int r2, int c2); void rasterCircle(int x0, int y0, int radius,char *Image) Camus.c int bereken(int *Window1, int *Window2) correlatie.c void CORRELATIE mWriteSlaveRegn(Xuint32 BaseAddress, unsigned RegOffset, Xuint32 Value) Xuint32 CORRELATIE mReadSlaveRegn(Xuint32 BaseAddress, unsigned RegOffset)

86

C-Functies