Engineering presentation
goodworkneeded
20150815142537notes.pdf
FPGA Workshop, OIST 1
Implementing Image Processing Implementing Image Processing Algorithms on FPGAsAlgorithms on FPGAs
Donald Bailey School of Engineering and Advanced Technology
Massey University, Palmerston North, New Zealand
[email protected] http://sprg.massey.ac.nz
FPGA Workshop, OIST 2
Workshop AimsWorkshop Aims • Demonstrate that FPGAs and image processing are
a natural fit • Introduce development tools
– VHDL, Quartus II • Develop basic interfaces to camera and display • Provide hands on experience in implementing basic
image processing operations – Colour, histograms, basic filters, object tracking
• Provide solid foundation for implementing more advanced designs
FPGA Workshop, OIST 3
TimetableTimetable Tuesday 21 Wednesday 22
9:00 1: Image Processing and FPGAs 5: FPGA Based Design and Algorithm Implementation9:30
10:00 10:30 Break Break 11:00 2: Introduction to VHDL 6: Histogram Processing 11:30 Lab: Using Quartus
VHDL display driver Lab: Histogram display, histogram
equalisation12:00 12:30 Lunch Lunch 1:00 1:30 3: Image Capture 7: Colour 2:00 Lab: Camera interface, Bayer filtering
Auto-exposure Lab: Colour detection
Colour tracking2:30 3:00 Break Break 3:30 4: Image Filters, convolution, morphology 8: Frequency domain processing 4:00 Lab: Sobel filter
CORDIC arithmetic Lab: FFT
4:30
FPGA Workshop, OIST 4
Session 1:Session 1: Image ProcessingImage Processing
and and FPGAsFPGAs
FPGA Workshop, OIST 5
Image Processing and Image Processing and FPGAsFPGAs
• Objectives: – Present basic definitions – Outline issues of embedded image processing on a
conventional platform – Show how image processing is inherently parallel
• Particularly low level pre-processing operations
– Describe basic architecture of FPGAs – Overview of the design flow for programming FPGAs
FPGA Workshop, OIST 6
ImagesImages • A spatial representation of an object or scene
– Photograph (a pictorial record formed by a sensor) – Map (a representation of physical or cultural features)
• More formally: – A continuous function of 2 or more variables defined on
some bounded region of space • Digital image
– An image in a form suitable for processing by computer
– Basically an array of numbers Pixel
FPGA Workshop, OIST 7
Digital Image ProcessingDigital Image Processing • Subjecting an image to a series of mathematical
operations in order to obtain a desired result Digital Image
An array of numbers (or vectors for colour)
Desired result
Enhanced image Measurement Classification Grading Description
A sequence of image processing operations
Operation
Operation
Operation
Image Processing Algorithm
FPGA Workshop, OIST 8
for i=1 to rows for j=1 to columns diff = a[i,j]–b[i,j] if diff < 0 c[i,j] = 0
else c[i,j] = diff
Image Processing AlgorithmsImage Processing Algorithms
Operation level algorithm – Programme sequence
implementing the image processing operation
Application level algorithm – Sequence of image processing operations
greyscale opening
subtract original
threshold
FPGA Workshop, OIST 9
Image RepresentationsImage Representations • Low level
– Array of pixels • Intermediate level: image
– Regions – Chain codes – Linear approximation of edges
• Intermediate level: feature – Sets of features – Labels
• High level – Description of object or scene
6 corners Hole area = 760 pixels
Hexagonal ¼ inch nut
Increasing abstraction
D ecreasing
volum e
Increasing value
FPGA Workshop, OIST 10
Operation PyramidOperation Pyramid
Low level
High level
Intermediate level
Pixels
Features
Objects
Image representations
Preprocessing
Segmentation
Classification
Recognition
Operations
Regions
FPGA Workshop, OIST 11
Typical Processing StepsTypical Processing Steps • Preprocessing: Image to image transformation
– Enhance relevant information – Suppress irrelevant information
• Segmentation: Image to region transformation – Detects objects or regions in an image which have a
common property • Classification: Region to feature to label transformation
– Identification of parts of objects – Data no longer image based
• Recognition: Label to description transformation
FPGA Workshop, OIST 12
Real Time Image ProcessingReal Time Image Processing • Real-time systems
– Response must occur within specified time to avoid failure • Machine vision, robot vision, video transmission
• Hard real time – Complete system fails if response is not produced in time
• Grading: decision must be made before activation point • Image capture and display subsystems
• Soft real time – Performance deteriorates if response time not met
• Video transmission
• Not necessarily the same as high performance
FPGA Workshop, OIST 13
• More pixels and higher frame rates means more computation required to process an image – VGA resolution video
• 640 x 480 x 60 frames per second = 18.5 million pixels per second
– HDTV (1080p) • 1920 x 1080 x 50 frames per second = 104 million pixels per second
– Ultra high definition TV • 7680 x 4320 x 60 frames per second
= 2 billion pixels per second
• Image processing requires many operations per pixel!
Processor Power RequiredProcessor Power Required
FPGA Workshop, OIST 14
Embedded VisionEmbedded Vision • Vision embedded within a product or component • Constraints on embedded systems
– Small size – Light weight – Low power
• Smart cameras – Intelligent surveillance – Robot vision – Machine vision – Industrial inspection – Using vision for control
FPGA Workshop, OIST 15
Traditional ComputingTraditional Computing • Basic architecture:
– Fetch instruction / Decode / Execute instruction – Serial processing
• All of the work done by the ALU • Rest of CPU designed to feed ALU as fast as possible
• So much to do, so little time to do it! – With serial processors, time is often the critical resource
• Because can only do one thing to one pixel at a time
– Some problems don’t “fit” serial processors
FPGA Workshop, OIST 16
Von Neumann BottleneckVon Neumann Bottleneck • Serial processing is memory oriented
– Most variables are in memory – A significant proportion of the time is spent accessing
memory • Reading operands • Writing intermediate results
– Memory uses a single monolithic address space • Consequences
– Data passes between the ALU and memory many times during a complex calculation
– Memory bandwidth ultimately limits the algorithm speed
FPGA Workshop, OIST 17
Solution: Parallel ProcessingSolution: Parallel Processing • Dedicated hardware for critical parts
– Hardware is parallel – Uses local registers for intermediate results
• Do more things at once – Parallel processing – Each processor has its own local memory
• Parallel processing is not new – Almost as old as image processing itself
• Image processing has often been a driver for parallel computing
– Only recently have FPGAs had sufficient resources to make them a practical platform
FPGA Workshop, OIST 18
Temporal ParallelismTemporal Parallelism • Algorithms usually consist of a sequence of separate
operations – Use a separate processor for each operation
– Leads to a pipelined architecture at the operation level • Limitations
– Less suited to iterative algorithms – Bandwidth in passing data between operations
Processor 1 Operation 1
Processor 2 Operation 2
Processor 3 Operation 3
FPGA Workshop, OIST 19
Spatial ParallelismSpatial Parallelism • Many operations perform the same function
independently on a large number of pixels – Split the image over a number of separate processors
– Can lead to a single instruction multiple data (SIMD) type architecture
– Most efficient when communication between processors is minimised • When operations only require data from a local region
Row Column Block
FPGA Workshop, OIST 20
Logical ParallelismLogical Parallelism • Functional block reuse in an algorithm
– Example: compare and swap for a bubble sort (rank filter)
<
Min Max
FPGA Workshop, OIST 21
Stream ProcessingStream Processing • Image is scanned to produce a
sequential stream of pixels – Converts spatial parallelism into
temporal parallelism – Each pixel is processed sequentially
• Removes need for parallel data access
• Fits with a pipelined architecture – Data is streamed between operations in a pipeline – Fine grained pipelining with an operation
0 1 2 3 … M 0 1 2 3 … M 0 1 2 3 … M 0 1 2 3 … M 0 1 2 3 … M 0 1 2 3 … M
0 1 2 3 4 5 6 7
… N
0 1 2 3 4 5 6 7 … M Column
R ow
Row 0 Row 1 Row 2 Row 3 … Row N
Time
FPGA Workshop, OIST 22
Parallelism SummaryParallelism Summary • Image processing algorithms have parallelism at a
wide range of granularities – Pipelining operations in the algorithm
• Temporal parallelism – Unrolling the outer loop through
the pixels of an image • Spatial parallelism
– Unrolling the inner loops • Logical parallelism
• All of these can be exploited in a hardware based implementation – FPGAs are just programmable hardware
for { XXXX
}
XXXX XXXX XXXX
FPGA Workshop, OIST 23
Basic FPGA ArchitectureBasic FPGA Architecture
I/O block
I/O block
I/O block
I/O block
I/O block
I/O block
I/O block
I/O block
I/O block
I/O block
Configuration control
Clock control
Programmable logic blocks
Programmable interconnects
FPGA Workshop, OIST 24
Logic CellLogic Cell • Smallest unit of logic on an FPGA • Based on a lookup table
– Output is an arbitrary function of its inputs • Early devices had 3 or 4 inputs • Modern devices have 5 or 6 inputs
– Used to implement logic, adders, counters, multiplexers, etc
– More complex functions require multiple LUTs
• Output also has a flip-flop – Used to build registers, finite state machines, etc
FPGA Workshop, OIST 25
Logic BlockLogic Block • Several logic cells combined together
– Typically 4-10 logic cells – Share common control signals (clock, clock enable)
• Outputs directly available to other inputs – Reduces propagation delay for deeper logic
• Additional dedicated logic – Reduces propagation delay for more complex logic
functions • Some FPGAs allow logic cells or logic blocks to be
used as RAM or shift registers
FPGA Workshop, OIST 26
Dedicated LogicDedicated Logic • Carry chains
– A full adder requires 2 outputs • Sum and carry
– Separate carry hardware allows 1 LUT per bit added • Multiplexer controls
– Combines outputs of multiple LUTs for wider functions – Enables wide multiplexers and more complex logic
functions to be built more efficiently • DSP blocks
– Hardware multiplier or multiply and accumulate • Reduces logic required and propagation delay for DSP applications
FPGA Workshop, OIST 27
Fabric RAMFabric RAM • Adapts structure of LUTs to enable them to be used
as small memories – 16×1 or 32×1 memory (depending on FPGA) – Adjacent blocks combine to make a dual-port memory – True dual-port
• Both ports can be used for read and write – Simple dual-port
• One port is read only and one write only – Used for banks of registers or coefficient memory
• Only one access per port per clock cycle
• Some FPGAs also allow LUTs to be configured as short shift registers
FPGA Workshop, OIST 28
Other Memory ResourcesOther Memory Resources • Dual port block RAM
– Larger blocks • 512 bits – 576 Kbits depending on family
– Flexible word width • Eg 36 Kbit block can be configured from 32K×1 to 512×72
– Each block is independent • Local memories • Potentially wide bandwidth
– Used for FIFO buffers, data caching, large lookup tables • External RAM
– Used for larger blocks (frame buffers, etc)
FPGA Workshop, OIST 29
InterconnectInterconnect • Flexibly connects the logic resources • Based on a grid structure
– Crossbar switches enable connection between horizontal and vertical routing lines
– Often a segmented structure is used • Not every routing line is switched at every junction • Reduces propagation delay
• Some FPGAs have busses as well – Requires tri-state drivers – Only one source may drive the line at a time
FPGA Workshop, OIST 30
Input and OutputInput and Output • Connects FPGA to
external devices • Basic interface
– LVTTL and LVCMOS • Advanced signalling
– Double data rate (DDR) • Data transferred on rising and falling edges of the clock
– Differential signalling (LVDS) • Uses two differential I/O bits to improve noise immunity
– High speed communication signals include parallel-to-serial and serial-to-parallel conversion • Serialisation and deserialisation (SERDES) logic
FPGA Workshop, OIST 31
ClockingClocking • FPGAs are synchronous devices • Each register, memory, I/O controlled by a clock
– Each block can be controlled by only one clock – A clock domain is all of the logic controlled by a clock
• FPGAs use a dedicated clock network – Minimises the skew between parts of a design – Manages the large fan-out required
• Special clock control blocks – Delay locked loops
• Synchronise clocks with external sources and minimise skew – Phase locked loops:
• Synthesise different clock frequencies from a reference clock
FPGA Workshop, OIST 32
FPGA ConfigurationFPGA Configuration • FPGA contents controlled internally by SRAM cells
– Allows infinite reprogrammability – Configuration is volatile
• Must be reloaded on power on • Commonly loaded from a small ROM • Some FGPAs enable encryption and
compression of configuration file – Configuration specifies
• LUT function • Register controls • Interconnect • I/O configuration • Memory contents
ROM
SRAM FPGA
Configuration file
FPGA Workshop, OIST 33
FPGAsFPGAs for Image Processingfor Image Processing • FPGAs are programmable hardware
– Each logic block is independent hardware – Parallel algorithm implemented on parallel hardware
• Able to exploit parallelism inherent in images – Separate hardware built for each operation
• Coarse grained pipelining – Partition image over several parallel function blocks
• Spatial parallelism / SIMD type parallelism – Stream processing can feed image data serially through a
single function block – Duplicated logic from unrolling inner loops
• Functional parallelism
FPGA Workshop, OIST 34
FPGAsFPGAs for Embedded Visionfor Embedded Vision • Parallelism enables a lower clock speed
– Often by 2 or 3 orders of magnitude – Slower clock enables a lower power design
• If whole algorithm can be implemented on an FPGA – Small form factor
• Only 1 or 2 chips (plus power supplies)
– Enables vision to be embedded into a design • Smart sensors and cameras • Integrated applications
FPGA Workshop, OIST 35
Benefits of Benefits of FPGAsFPGAs • FPGAs if used correctly can give
– Significant acceleration of the processing – Improvements in both latency and throughput
• While achieving – Lower clock speed – Lower power
• Enabling – Embedded vision – Smart cameras – Efficient real-time processing
FPGA Workshop, OIST 36
Limitations of Limitations of FPGAsFPGAs • FPGAs are hard to programme
– FPGA based design is hardware design not software – Image processing normally thought of as software
• Large code base of image processing software • Algorithms have to be redeveloped for efficient hardware
implementation
• Parallel hardware requires a hardware mindset – Parallel programming is difficult
• Concurrency, synchronisation, contention, bandwidth • FPGAs are fine grained parallelism
– Results in an explosion in design space complexity
FPGA Workshop, OIST 37
Programming Programming FPGAsFPGAs
• Representation – Basically parallel languages describing hardware – Range of styles and levels of abstractions
• Structural – describes connections between blocks • Concurrent – describes in terms of assignments to registers • Behavioural – describes behaviour in terms of events and
responses
– Compiles to enable a simulation
Behavioural and functional simulation
Design
Representation
FPGA Workshop, OIST 38
Programming Programming FPGAsFPGAs
• Synthesis – Converts logical representation to a device or gate level net-
list • Constraints control aspects of the synthesis
– Optimising for speed or area, type of resets, etc
Synthesis constraints
Behavioural and functional simulation
Gate level simulation
Design
Representation
Synthesis
FPGA Workshop, OIST 39
Programming Programming FPGAsFPGAs
• Mapping – maps the logic onto the resources • Place and route – associates these with particular logic
blocks, I/Os etc on the FPGA
Synthesis constraints
Implementation constraints
Behavioural and functional simulation
Timing simulation
Gate level simulation
Design
Representation
Map Place & route
Synthesis
FPGA Workshop, OIST 40
Programming Programming FPGAsFPGAs
Synthesis constraints
Implementation constraints
Behavioural and functional simulation
Timing simulation
Gate level simulation
In system verification
Design
Representation
Map Place & route
Generate configuration file
Synthesis
Implementation
FPGA Workshop, OIST 41
Session 2:Session 2: VHDLVHDL
FPGA Workshop, OIST 42
VHDLVHDL • Objectives:
– Introduce basic structure and syntax of VHDL • Different programming styles and where they are used
– Develop a basic display driver
• Laboratory objectives – Familiarise with Quartus II tools
• Creating project • Design entry • Timing • Compilation • Implementation
FPGA Workshop, OIST 43
• Main standards: – VHDL, Verilog
• Hierarchical structural languages – Design can be broken into a series of hierarchical blocks
• Main purposes – Documentation – Modelling and verification – Simulation – Synthesis was added later
• Only a subset of the language is synthesisable
Hardware Description LanguagesHardware Description Languages
FPGA Workshop, OIST 44
Hierarchical DesignHierarchical Design • VHDL enables a hierarchical design
– Design can be built in terms of component blocks – Top level contains all inputs and outputs for a design
• Each component is defined by an entity – Entity specifies the interface to the component
• Inputs and outputs • Constant parameters
– Architecture contains the component implementation • An entity may have multiple architectures for different implementations
FPGA Workshop, OIST 45
VHDL EntitiesVHDL Entities • Each component is defined by an entity
– The entity specifies the interface to the component • The view from the outside (black box representation)
– Example we will use is an adder / subtracter
add / subtract
n
n n
a
b
control
q
FPGA Workshop, OIST 46
VHDL EntitiesVHDL Entities • Each component is defined by an entity
– The entity specifies the interface to the component – Implementation is in the corresponding architecture
• An entity may have multiple architectures for different implementations library IEEE; use IEEE.std_logic_1164.all; use IEEE.numeric_std.all;
entity add_sub is generic (n : positive := 4); port (a, b : in signed (n-1 downto 0);
control : in std_logic; q : out signed (n-1 downto 0));
end entity add_sub;
architecture implement of add_sub is … end architecture implement;
Implementation
External libraries
generics provide parameterisation ports define input and output connections
FPGA Workshop, OIST 47
VHDL TypesVHDL Types • Built in types:
• boolean, integer, real, bit, character, string, time, file
– Subtypes: • positive, natural
• Hardware types (in std_logic_1164 library) • std_logic
– Signal on a wire: '0', '1', 'U', '-', 'Z', 'L', 'H', 'X', 'W' • std_logic_vector
– An array or bundle of wires: "00100110", x"26"
• Numeric types (in numeric_std library) • signed, unsigned
FPGA Workshop, OIST 48
Structural Coding StyleStructural Coding Style • Builds a component in terms of other components
– Design is built as a hierarchy of components
n
n
n
a
control
q
b
sumb a
q
diffb a
q
muxb a
q sel
s
d
add:
sub:
sel:
FPGA Workshop, OIST 49
Structural Coding StyleStructural Coding Style • Builds a component in terms of other components
– Design is built as a hierarchy of components architecture structural of add_sub is
component sum generic (n : positive); port (a,b : in signed (n-1 downto 0);
q : out signed (n-1 downto 0)); end component; component diff … end component; component mux … end component;
signal s, d : signed (n-1 downto 0); begin
add: sum generic map(n=> ) port map( a=> , b=> , q=> );
sub: diff generic map(n=> ) port map( a=> , b=> , q=> );
sel: mux generic map(n=> ) port map( a=> , b=> , sel=> , q=> );
end architecture structural;
Definition of constituent components
Local connection signals
add: sum generic map(n=>n) port map( a=>a, b=>b, q=>s );
sub: diff generic map(n=>n) port map( a=>a, b=>b, q=>d );
sel: mux generic map(n=>n) port map( a=>s, b=>d, sel=>control, q=>q );
end architecture structural;
Instantiating components
Explicit port mapping
FPGA Workshop, OIST 50
Concurrent Coding StyleConcurrent Coding Style • Focus is on concurrent signal assignments
– Models the operation of the component in terms of the data flow through the logic
– Whenever a variable on RHS changes, the statement is evaluated and immediately assigned to LHS • Order of assignments is not important – they are in parallel architecture concurrent of add_sub is
signal s, d : signed (n-1 downto 0); begin
s <= a + b; d <= a – b;
mux: for i = 0 to n-1 generate
q(i) <= (control and s(i)) or (not control and d(i)); end generate mux;
end architecture concurrent;
Local connections
generate loop
Concurrent assignments
FPGA Workshop, OIST 51
Concurrent AssignmentsConcurrent Assignments • Straight signal assignment
• Conditional assignment – Builds a multiplexer – Priority coded if have a sequence of conditions
• Selected assignment
sum <= a + b;
q <= a + b when control = '1' else a – b;
with control select q <= a + b when '1',
a – b when '0', (others => 'X') when others;
FPGA Workshop, OIST 52
Behavioural Coding StyleBehavioural Coding Style • Describes the behaviour of a system
– How it responds to events • Implemented as one or more process statements
– Process triggered when signals in sensitivity list change architecture behavioural of add_sub is begin
process variable result : signed (n-1 downto 0 );
begin if control = '1' then
result := a + b; else
result := a – b; end if; q <= result;
end process; end architecture behavioural;
Local process variables
Sensitivity list
Conditional statement
Signal assignments within a process are parallel and are assigned at the end
(a, b, control)
FPGA Workshop, OIST 53
Behavioural Coding StyleBehavioural Coding Style • Statements in a process are sequential
– Variable assignments take place immediately in order of execution
– However, all signal assignments take place concurrently at the end of the process • Before they change, all signals retain the old values • They receive the last value assigned to them
• Both signals and variables can be registers or connections depending on context – Registers are changed in synchronisation with a clock
FPGA Workshop, OIST 54
• Assigned within a process controlled by a clock
281.384 Donald Bailey 54
Registers in VHDLRegisters in VHDL
entity counter is port( clock, reset : in std_logic;
count : out unsigned (3 downto 0)); end entity counter;
architecture ctr of counter is begin
process (clock, reset) variable i_count : unsigned (3 downto 0);
begin if reset = '1' then
i_count := (others => '0'); elsif rising_edge( clock ) then
i_count := i_count + 1; end if; count <= i_count;
end process; end architecture ctr;
Interface definition
Internal counter variable
Asynchronous reset
Synchronous counting
Connect count to the output
FPGA Workshop, OIST 55
VHDLVHDL • Different programming styles can be mixed within
a design – All statements within the architecture are parallel
• Strongly typed language – Types must match exactly – Necessary to specifically perform any type casting
• This is partly what makes VHDL verbose
– Can define own types, including • records, arrays, enumerated types • functions, procedures
FPGA Workshop, OIST 56
Control LogicControl Logic • A lot of control is implemented using finite state
machines – State provides context for
• Selecting register inputs (multiplexing)
• Enabling the clock on registers
– Enables control logic to be separated from computation logic
FPGA Workshop, OIST 57281.384 Donald Bailey 57
Finite State Machines in VHDLFinite State Machines in VHDL entity state_machine is
port( A : in std_logic; Q : out std_logic);
end entity state_machine;
architecture fsm of state_machine is type states is (S1, S2, S3); signal state : states := S1;
begin process (clock) begin
if rising_edge( clock ) then case state is
when S1 => if A = '1' then state <= S2; end if;
when S2 => state <= S3; when S3 => if A = '0' then state <= S1;
end if; end case;
end if; end process; q <= '1' when state = S2 else '0';
end architecture fsm;
State transitions
Output logic
Definitions
FPGA Workshop, OIST 58
DE0DE0
FPGA Workshop, OIST 59
DE0DE0
FPGA Workshop, OIST 60
Video TimingVideo Timing
Horizontal Sync
Vertical Blanking
Visible region
Horizontal Blanking
Vertical Sync
FPGA Workshop, OIST 61
VGA TimingVGA Timing • Image sent to the display in a raster format
– Sync signals indicate start and end of each row
• Timing for 640×480 @ 60 Hz refresh Active Front porch Sync Back porch Total Clock
Horizontal 640 16 96 48 800 pixels 25.175 MHz Vertical 480 10 2 33 525 lines 31.5 kHz
FPGA Workshop, OIST 62
VGA TimingVGA Timing • Timing controlled by counters
– X and Y counters give pixel location currently displayed – Testing for equality is more efficient than ≥ – Use tests to set and reset latches
FPGA Workshop, OIST 63
VGA OutputVGA Output • Analogue video signal output
– Use x and y counters to control which pixel to output – High speed D/A converters required on RGB channels
• Can be provided by an external DAC chip
• Sync signals – Sent directly to the display – 3.3V TTL signal output levels are suitable – Polarity depends on video mode
FPGA Workshop, OIST 64
Laboratory:Laboratory: Using Quartus IIUsing Quartus II
VHDL display driverVHDL display driver
Laboratory: Using Quartus II, VHDL Display Driver
The aim of this laboratory is to familiarise you with Altera’s Quartus II development environment. In this laboratory, you will develop a basic VHDL display driver, and use it to display a simple test pattern.
1: Setting up the project Start Quartus II. In this you see the four main panels: the project navigator, tasks, messages, and file panel on the right (where document and information files are displayed).
Create a new project. From the File menu, select New Project Wizard… (File » New Project Wizard…). This steps you through setting up the project.
First select an appropriate working directory. Ensure that there are no spaces in the path name or filename (i.e. DO NOT put the project on the desktop or in My Documents folders). Then select the project name. It automatically uses the project name as the top-level entity, although this can be changed later if desired.
If necessary, click Yes to create the directory.
Click Next. Copy the file VGA.vhd into the project working directory. Then click Add All to add the file into your project.
Click Next to advance to page 3, where you select the following device:/
Finally, Click Next to get to the end (keep the defaults) or Finish to complete the setup.
2: Enter the top level of the design The next step is to create the top level design file. In the Project Navigator, select the Files tab, and double-click VGA.vhd. Within this, we have already defined the top level entity, which defines the FPGA inputs and outputs used by the design.
50 Mhz Clock
clk_50
VGA Sync signals
Pixel value displayed
vga_hs vga_vs
vga_r vga_g vga_b
This declares that it will use the logic definitions and the numeric functions (signed and unsigned arithmetic) from the IEEE library. The entity VGA has the following interface:
• one input: the 50 MHz clock from the board • three 4 bit outputs: the RGB colour to be displayed • two 1 bit logic outputs: the horizontal and vertical sync signals
The architecture here is currently empty (apart from some comments). The next step is to populate this with the driver and test pattern generator. The pixel clock for standard VGA is 25 MHz, so the 50 MHz from the board will need to be divided down. Within the top level we will have two main components:
• The VGA driver itself which provides the sync signals for the display, two counters to indicate which pixel we are currently at, and blanking signals which indicate when we are in the blanking periods.
• A pattern generator which will determine which colour is displayed for each pixel on the display.
clk x y
hb vb hs vs
x y r g b
VGA Driver
Pattern Generator
–2:
clk_50
To display
The first thing to do is declare the components within the top module. Edit VGA.vhd to first declare the internal signals (lines 12-17) and then wire everything up (lines 20-41), as shown on the following page.
• The first block (lines 21-26) uses the behavioural coding style. clk_50 is in the sensitivity list so the process executes whenever clk_50 changes. On the rising edge of clk_50 we toggle clk_25 signal, which effectively divides it by 2. This is the clock signal passed on to the VGA driver.
• The second block (lines 29-32) uses the structural coding style to instantiate the VGA driver and pattern generator sub-blocks from the work library (these are files within the project). We will create these files shortly.
• The next block (lines 35-41) uses the concurrent dataflow coding style. The AND gates implementing the blanking are represented using conditional signal assignments (the when statements).
Check the syntax of your file with Processing » Analyze Current File (or click the toolbar icon). If you have any errors, correct the offending lines and recheck the file.
3: Enter remaining components If you have not done so already, copy the file VGA_Driver.vhd to your working directory. Then, within the Project Navigator, right-click on Files and select Add/Remove Files in Project…
Within the Settings dialog, click the … button, and select the file VGA_Driver.vhd. Then click Add to actually add the file to the project. It should then appear in the file list within the dialog.
Finally click OK, to add the file to the project. Open the file to explore its contents:
Basically, the VGA driver consists of two counters, xx and yy, one for the x direction and one for the y. We need to use internal signals, because to count, and to determine the positions of sync and blanking, we need to read the current values. We cannot read from output ports, so we use internal signals, and connect these to the output ports using signal assignments.
A process statement, controlled by the clock makes the counters and output control signals synchronous. Based on each counter, tests are used to set or reset the corresponding sync and blanking signals at the appropriate times.
Finally, we will create the pattern generator. File » New… and select VHDL File to create a new VHDL file. Enter the VHDL code on the following page. This simply wires the pixel counters to the RGB outputs to create a coloured test pattern by using the position to directly control the colour.
Check the syntax of each file (Processing » Analyze Current File or ) after you have entered it, and eliminate any errors as you go.
If you Start Analysis and Synthesis ( ) you should have no errors, and an estimate of the resource requirements is provided:
A schematic representation of the design can be viewed in the netlist viewer: Tools » Netlist Viewers » RTL Viewer. Double-click on the VGA driver to go down a level and explore the implementation.
Once you have explored your design, you can close the RTL viewer.
4: Setting up design constraints The next step is to assign pin numbers to the input an output pins. To do this, it is necessary to open the pin planner: Assignments » Pin Planner ( ). This will list the pins and show the corresponding pin location on the pinout for the FPGA. In the Location field in the bottom panel, enter the pin assignments:
These pin numbers correspond to the FPGA pins that these particular peripherals are connected to, and can be found in the DE0 User Manual. Close the Pin Planner after entering in the pins.
Next it is necessary to set up some of the pin options within the project. First we need to tell Quartus what to do with all of the pins which are not used by a design. Select Assignments » Device ( ) and click the Device and Pin Options button. Select Unused Pins and set to As input tri-stated in the dropdown menu.
Then set the Dual-Purpose Pins as Use as regular I/O. This will require double-clicking each entry and selecting the option from the drop-down menu.
Click OK to make the changes and close the settings box.
Next compile your design: Processing » Start Compilation ( ). This will give a number of critical warnings relating to timing requirements not being met. That is because we have not yet specified any timing constraints.
Having done the fitting we can now set these up with Tools » TimeQuest Timing Analyzer ( ). Within the TimeQuest Tasks panel, double-click Create Timing Netlist to initialise the timing netlist for the project:
Then Constraints » Create Clock… to set up the clk_50 clock. Set the Clock name to clk_50, the Period to 20 ns, and the Targets to clk_50 and click Run. Repeat for clk_25, setting the Period to 40 ns.
Next Constraints » Set False Path… to inform TimeQuest that any signals from clk_25 will not be latched by clk_50: Set From to clk_25 and To to clk_50 and press Run.
Next, in the Console panel, enter the command derive_clock_uncertainty to set up the uncertainties associated with clock jitter.
Double click Update Timing Netlist in the Tasks panel to actually derive the uncertainty values.
Finally, at the bottom of the Tasks panel, double click Write SDC File… to save the constraints.
Change the SDC file name to VGA.sdc, uncheck the Expand checkbox and click OK.
You can now close the TimeQuest window and return to the main Quartus II window. Here, recompile your design by clicking on the toolbar button. The design should compile without any timing errors. The flow summary panel summarises the resources used by the design
5: Downloading your design to the FPGA The final stage is to download your configuration file to the FPGA board. First ensure that your DE0 board is connected to your computer using the programming cable, and the VGA outputis connected to a VGA monitor. Check that the RUN – PROG switch on the board is in the RUN position (the other position programmes the configuration ROM on the DE0), and switch the DE0 on.
Open the programmer by double clicking Program Device in the Tasks panel, or by clicking the programmer toolbar button ( ).
This will open the programmer.
If “No Hardware” appears in the top panel, ensure that the DE0 is switched on and connected to the computer. Click the Hardware Setup… button, and select the USB Blaster [USB-0] from the drop down menu, and then Close to return to the programmer.
Click the Start button to send the file to the FPGA. On the DE0, the LOAD LED should light up while the configuration is downloading, and when loading is complete, the design will automatically begin executing, and the test pattern will appear on the VGA display.
6: Further work If you have further time, experiment by creating different test patterns within the pattern generator. The simplest way of doing this is to add a new architecture (with a different name) into pat_gen.vhd, and change the instantiation in VGA.vhd. For example:
7: Summary In this laboratory we have:
• Set up a project within Quartus II • Entered our design for a basic VGA driver and test pattern using VHDL • Viewed our design using the RTL viewer • Used the Pin Planner to specify the input and output pins • Set up pin options for unused pins • Used TimeQuest to set the timing constraints for our design • Compiled our design • Downloaded the design onto the FPGA for testing
FPGA Workshop, OIST 65
Session 3:Session 3: Image CaptureImage Capture
FPGA Workshop, OIST 66
Image CaptureImage Capture • Objectives:
– Describe interface of D5M camera module – Discuss I2C control – Introduce Bayer pattern interpolation
• Laboratory objectives – Implement a simple image capture and display system – Implement Bayer pattern demosaicing – Implement a simple automatic gain control on the camera
FPGA Workshop, OIST 67
D5M CameraD5M Camera • 5 MPixel colour sensor
• 2592×1944
– Bayer pattern readout • Individual pixels have a
red, green or blue filter • Twice as many green
as other colour pixels
– Programmable window • Only part of image needs to be read out • Allows resolution to be traded off for frame rate • Enables electronic pan and scroll
FPGA Workshop, OIST 68
D5M InterfaceD5M Interface
CMOS Image Sensor
MCLK
PIXCLK FVAL LVAL DATA
SCL SDA
Master clock
Pixel data and framing
I2C camera control
FPGA Workshop, OIST 69
Displaying an ImageDisplaying an Image • Cannot just output from camera to VGA display
– Different resolution • Can programme the D5M window to give 640x480 VGA output
– Different clock rates – Different blanking intervals
• Require a buffer buffer to smooth timing – Camera and display are set up as line synchronous
Camera Camera control
FIFO Line buffer
Display
FPGA Workshop, OIST 70
II22C ProtocolC Protocol – Host provides the clock signal – Start bit pulls data low while clock is high – First byte always address and direction (read or write) – Each byte is acknowledged by receiver
FPGA Workshop, OIST 71
II22C CommunicationsC Communications • Send command
– Sends I2C device address with Write direction – Sends register address to be programmed – Sends one or more data values
• Register address usually auto-increments
• Receive command – Sends I2C device address with Write direction – Sends register address to be read – Sends I2C device address with Read direction – Receives one or more data values
• Register address usually auto-increments – Terminate transfer by not acknowledging last byte
FPGA Workshop, OIST 72
Bayer Pattern ProcessingBayer Pattern Processing
• Single chip cameras use a colour filter array – Each pixel is filtered with only one colour – Most common pattern is the Bayer pattern
• Forming a full colour image requires interpolating missing values in each channel – Called demosaicing
FPGA Workshop, OIST 73
Bayer DemosaicingBayer Demosaicing • Nearest neighbour
– Simplest (2×2 window) – Multiplexer selects required pixel
FPGA Workshop, OIST 74
Bayer Pattern DemosaicingBayer Pattern Demosaicing • Bilinear interpolation
– Requires 3×3 window – Optimise resources by reusing calculations
FPGA Workshop, OIST 75
Automatic Gain ControlAutomatic Gain Control • Detect highlights
– Threshold incoming pixel stream • Adjust gain incrementally
– If too many bright pixels, reduce camera gain – If bright pixels are too dark, increase camera gain
• Program camera gain using I2C Black White
Highlights Too bright decrement
gain
Too dark increment
gain
No change
FPGA Workshop, OIST 76
Laboratory:Laboratory: Interfacing to D5M cameraInterfacing to D5M camera Bayer pattern interpolationBayer pattern interpolation
Laboratory: Basic Image Capture and Display
The aim of this laboratory is to develop a basic image capture and display. The D5M digital camera is controlled from the FPGA via an I2C interface, and simple Bayer pattern interpolation is used to generate the corresponding colour image.
1: Basic top level design A block diagram of what we will initially construct is shown here:
Camera
I C control
2
Memory buffer
VGA timing
Camera timing
Sync generator
PLL
Display
50 MHz clock
48.825 MHz 25.2 MHz
The VGA display displays a 640×480 image at 60 frames per second. Including blanking, the total frame size is 800×525, which requires a pixel clock of 25.2 MHz (800×525×60). Although the camera has 5 megapixels, we will operate it in windowed mode, where we will read out a 640×480 window. The timing requirements of the camera are different – to read out one row of the image will take 1550 clock cycles.
In our design, to minimize the latency, we will run the camera and display line synchronous. That is the camera will produce exactly one line of data in the time that it takes to display the line. This requires running the camera at 25.2×1550/800 = 48.825 MHz. We will use one of the phase-locked loops (PLL) on the FPGA to synthesise the two clock frequencies from the on-board 50 MHz clock.
The memory buffer is used to transfer pixel data between the two clock domains, allowing them to run at different clock speeds. This is basically a FIFO with the input in the camera clock domain, and the output in the display clock domain. In addition, a synchronisation signal is passed between the clock domains to reset the VGA display appropriately so that line 0 from the camera appears on the first line of the display.
Rather than spending a lot of time setting up the project, we will start with an initial pre-built project and add features from there. Copy the files for this laboratory into a new directory, and double-click the top.qpf file. This will open the project.
2: Setting up the PLL On the board, we only have a 50 MHz clock available. From this we will generate the 25.2 MHz and 48.825 MHz clocks. Within Quartus, select Tools » MegaWizard Plug-In Manager….
• Select Create a new custom megafunction variation • Expand the I/O tab and select ALTPLL • In the output file, add pll
• Click Next > to continue • Change the frequency of inclk0 to 50 MHz, and Next > to continue
• Click Next > to continue • Uncheck Create an ‘areset’ input and Create a ‘locked’ output.
• Click Next > four more times until you get to the c0 output clock • Select Enter output clock frequency as 25.2 MHz
• Click Next > to move to c1 clock output. • Select Use this clock • Select Enter output clock frequency as 48.825 MHz
• Finally, click on the Finish to get to the summary, and Finish again to create the PLL file.
This process will have added the pll.qip file to the project. This contains the link to the PLL entity which configures the PLL to produce the desired output frequencies.
Within top.vhd, we see the instantiation of the PLL:
First we declare a signal corresponding to the 25 MHz clock. We will use the return clock from the camera as our 48 MHz system clock. Rather than assigning it to another signal, we simply use an alias for this. The alias just uses another name (clock_48) for the signal (cam_pixclk) coming from the camera.
In the instantiation of the PLL, the inclk0 PLL input is mapped to the 50 MHz board clock, c0 to our clock_25 (which we will use for the display domain) and c1 directly to the clock input pin on the camera.
3: Configuring the camera The camera is configured by programming registers within the camera using the I2C protocol. By default, the camera captures a 2592×1944. We need to programme appropriate registers to read out a 640×480 window from the centre of the image. We also need to modify the timing slightly to make it consistent with the VGA display. Each register within the camera is 16 bits wide (the registers are documented in the D5M Hardware Specification) so requires two 8-bit I2C transfers to set.
Within the library, we have an I2C setup module that programmes an I2C device from a table of initialisation data. For this we can use a VHDL constant array.
We then pass this data to the I2C setup block as a generic (since it is a constant parameter).
Since the camera I2C runs at a frequency of 400 kHz, we also need to specify the clock frequency, so that the clock can be divided down appropriately.
I2C uses a 2-wire protocol. One wire is the clock, cam_i2c_scl, which passes from the FPGA to the device. The other is the data wire, cam_i2c_sda, which is bidirectional. This bi-directionality must be managed at the top level, and requires the setup module to have 3 data connections:
• Input data from the camera to the controller, sda_in • Output data from the FPGA controller to the camera, sda_out • Output enable (tri-state control), sda_zo, which determines whether the data is input or output.
Line 69 above controls the tri-stating of the output signal as appropriate.
4: Camera interface Coming from the camera is the pixel data (12 bits per pixel) along with two control signals: line valid and frame valid. The line valid signal differentiates between valid pixel data and horizontal blanking. The frame valid signal differentiates between valid lines and vertical blanking. The timing of these is shown below (from the camera datasheet), with all of the signals (pixel data and synchronisation signals) switching on the rising edge of the clock.
The camera interface block is responsible for registering the input signals from the camera. The following declares the synchronised signals coming from the camera interface.
pixel_sync is a record (declared in the DE_Lib.globals package) containing the line and frame valid signals, as well as two counters indicating where we are in the pixel stream.
It is important for the camera interface block to work with the pixel clock from the camera, since the timing is relative to this, not the clock signal sent to the camera.
Examine the provided camera_interface.vhd file. It consists of two process statements:
• The first, triggered on the falling edge of pixel_clock, samples the incoming data signals while they are stable (they could be changing on the rising edge).
• The second, triggered on the rising edge, aligns all data on the rising edge for the rest of our design. It also provides pixel counters so we know where we are in the stream.
5: Cross domain synchronisation The camera and display are running at quite different clock speeds. However, we have configured them to run line synchronously, that is the time taken for one line of pixel data (including blanking) is identical for both the camera and display. This means that we do not need to save the complete image, but only need to buffer one line of data, and we can display the data as it comes from the camera.
The buffer between the two clock domains is a synchronous dual-port memory, with one port in each clock domain. The pixels from the camera are written into the memory, and the pixels are read and sent to the display (or processing in later labs). A signal is also sent between the domains at the start of each frame to synchronise the VGA display to the camera (vga_reset), so that the first row from the camera corresponds to the top row on the display.
Examine camera_buffer.vhd, and see how it operates. Note that the memory is just declared as an array of values. The synthesis tools will infer that this is dual port memory from the way in which we use it.
There are four processes within camera_buffer: • The first is controlled by the camera clock, and writes pixels into the memory buffer using the pixel
counter as the address. It also detects row 0 for synchronisation. • The second process, controlled by the display clock, reads pixels from the memory buffer, again
using the pixel counter as the address. • The third process is a synchroniser chain to transfer a signal from the camera clock domain into the
display clock domain. This is necessary because these clocks are different frequencies, and there is a danger of metastability if the signal in the camera domain changes within the setup-hold window of the display clock.
• The final process generates a reset pulse if the display is not already synchronised with the camera.
6: VGA controller The final step is to generate the VGA timing and synchronisation pulses. For this we will use a slightly more sophisticated version of what we developed in the last lab. We separate the timing from the sync pulse generation because later we will add image processing operations in between, and we need to account for their latency.
We simply map the 4 most significant bits of the raw pixels from the camera to the red, green, and blue channels of the display to show the greyscale version of the raw image.
Compile your design (Processing » Start Compilation, or ). With the FPGA switched off, carefully plug the camera into the 40 pin GPIO0 connector (this is the inner of the two connectors), facing outwards. Once seated, turn on the FPGA again and programme it with your design. You should see the image from the camera on the VGA monitor. The regular pattern of dot is from the Bayer colour filter array.
7: Bayer pattern demosaicing Within the camera, each pixel has associated with it a colour filter, so that it only captures one of the red, green or blue components. To recover a full colour image, it is necessary to interpolate the missing values for each colour plane. We will use simple bilinear interpolation to give the colour values.
Add the bayer.vhd file to your project. Edit top.vhd, to add the following signal declarations:
Next, we need to instantiate the Bayer interpolation filter, and link it into the processing chain:
Compile the design, and download it onto the FPGA.
Open the file bayer.vhd. The entity has 5 ports: the pixel clock, the input pixel stream and its corresponding timing signals, and the output stream with its timing signals. The output stream is 3 times wider, consisting of the RGB components concatenated together.
Within the architecture, we declare a window, and functions which calculate the averages of 2 and 4 numbers (as required by the filters).
G B G B R G R G G B G B R G R G
We first instantiate a 3×3 make_window component. This gives us the pixels within a 3×3 neighbourhood as required to interpolate the missing pixels. Row buffers are used to cache 2 whole lines of pixels, enabling the whole system to operate on streamed data. The EDGE_MODE generic specifies what to do when the window extends past the edge of the image. In this case we duplicate with a period of 2 pixels (to preserve the Bayer pattern).
The latency of the Bayer filter consists of the following delays:
• It takes 1 clock cycle for the input pixels to be loaded into the edge of the window (this includes the time taken to read the pixels from the row buffers).
• The output pixel corresponds to the centre of the window, which is offset 1 row, and 1 pixels from the start of the window. This means that the latency (time from when a pixel comes into the window to the corresponding output position) is 1 row and 1 clock cycle.
• The interpolation calculations from the window pixels are registered on the output, adding a further clock cycle delay.
• Adding these gives the total latency of the filter as 1 row + 3 pixels. Our output timing signals need to be delayed by this amount, which is achieved through the sync_delay component.
The actual interpolation takes place in the process statement. Since the location of each colour component depends on which clock cycle we are in, the least significant bits of the x and y addresses are combined to give the context. For each context, we average the appropriate pixels together to give the output. The case statement is effectively multiplexing the outputs for the different offset combinations. Note no attempt has been made here to optimise the logic required.
8: Automatic gain control The exposure in the previous design was fixed. The last step we will take is to modify the design to automatically adjust the gain within the camera (via I2C) depending on the light level. This analyses the pixel stream from the camera, looks at the brightest pixels in the image. If there are too many bright pixels, the gain for the next frame is reduced. If the bright pixels are not bright enough, the gain is increased. The camera gain varies between 1 and 128 using a combination of both analogue and digital gain (while high gain will allow us to operate in lower light levels, the resulting images will be quite noisy).
First add the following signal declarations.
Then modify the I2C controller to include the connection from the auto-exposure module. Replace the i2c_setup instantiation with i2c_multi_port as shown here.
Finally instantiate the auto-exposure block itself. This monitors the pixel stream from the camera, and interfaces with the I2C controller to adjust the appropriate camera settings. Generics parameters specify the minimum and maximum levels for the highlights within the image. EXP_N defines what we mean by highlights; here the image is too bright if 1023 pixels are above EXP_MAX, and too dark if fewer than 1023 pixels are below EXP_MIN. Having a dead band reduces flicker as a result of continually changing the exposure.
The last two lines display the current gain on the seven segment displays.
Compile the design and download onto the FPGA. Test the automatic gain control by changing holding various objects in front of the camera, and seeing the exposure change on the display. Switch 9 (the leftmost switch) turns automatic gain control on and off. Since the exposure is only incrementing or decrementing one step per frame, it can take about 2 seconds to change from minimum to maximum.
If the exposure adjustment is continually changing and flickering (for example because of the statistics of the image, or as a result of lighting), then increase the dead band by reducing EXP_MIN.
9: Summary In this laboratory we have:
• Configured a PLL using the Megafunction Wizard • Configured the digital camera using I2C • Received a video stream from the camera • Transferred the data between clock domains using a dual-port memory • Synchronised the VGA display with the camera • Interpolated the Bayer pattern to give a full colour image • Monitored the pixel stream to implement automatic gain control
FPGA Workshop, OIST 77
Session 4:Session 4: Image FiltersImage Filters
Convolution and MorphologyConvolution and Morphology
FPGA Workshop, OIST 78
FiltersFilters • Objectives:
– Derive mechanisms for efficient filtering • Row buffers • Priming and flushing issues
– Outline filter structures for linear and morphological filters – Describe separability and optimisation issues – Illustrate with a Sobel filter
• Introduce CORDIC for Cartesian to polar conversion
• Laboratory objectives – Implement a Sobel filter
• Detect edges and edge orientation image
FPGA Workshop, OIST 79
Local Image FiltersLocal Image Filters • Each output pixel is some function of pixels within a
small local window
Input image Output image
Filter function
FPGA Workshop, OIST 80
Implementation IssuesImplementation Issues • Software approach
– Have entire image stored in a frame buffer (an array) – Loop through for each output pixel – Retrieve input pixels within window in input image – Apply the filter function
• Problems for hardware implementation – Multiple pixels must be read for each window position – Each pixel is read multiple times – Memory bandwidth constraints prevail – Requires some caching arrangement
FPGA Workshop, OIST 81
Window registers
Caching to Reduce BandwidthCaching to Reduce Bandwidth • Filters use multiple pixels
– Stream processing has significant overlap between windows
• Reuse data by shifting it – Only need to load new pixels
• Use row buffers to cache incoming stream – Unrolls inner loop which
accesses pixels – Only need to load one pixel
for each window position
New pixels
Row buffer
Row buffer
Input stream
N ew
pi xe
ls
From row buffer
FPGA Workshop, OIST 82
• Feed image through the window (streaming) – Row buffers can be implemented using
• Shift register • Circular memory (dual-port)
Filter CachingFilter Caching
Dual-port memory
A dd
re ss
D at
a
Shift register Window
Filter function
Input stream
Output stream
Shift register
Row buffers
RAM
Address counter
RAM
FPGA Workshop, OIST 83
Row BufferingRow Buffering • Cache data using row buffers
– A W×W window requires W-1 row buffers • Two basic configurations
– Parallel with window – Series with window pixels
FPGA Workshop, OIST 84
Filter LatencyFilter Latency • Need to load whole window before output starts
– For a W×W window, requires loading W-1 rows • Latency from a pixel input to corresponding output
pixel is produced – Half window height: (W-1)/2 rows +
Half window width: (W-1)/2 columns + Latency of filter function
• Further complicated if input stream has horizontal and vertical blanking – Invalid data during blanking intervals – Also issues of managing image borders
FPGA Workshop, OIST 85
Border PixelsBorder Pixels • Problem around the borders of the image
– Window extends past edge of the image – What pixel values should be used as inputs?
FPGA Workshop, OIST 86
• Just wrap the input stream (ignore the problem) • Truncate the output image (make it smaller) • Modify the filter function • Constant extension
– Often 0, but can be any value • Periodic extension (eg FFT) • Duplicate border pixels
– Nearest neighbour extrapolation • Mirror border pixels
– With or without duplication of the border
Border Pixel Management OptionsBorder Pixel Management Options
FPGA Workshop, OIST 87
Filter Priming and FlushingFilter Priming and Flushing • Example: edge duplication with 3x3
window – Priming: loading of duplicated rows
0 and N and columns 0 and M – Flushing: ignoring invalid outputs
0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 1 …
0 1 2 3 4 5 6 7
… N
0 1 2 3 4 5 6 7 … M Column
R ow
Row 0 (duplicate) Row 0 Row 1 Row 2 …Row 3
X X X X X X X X X X X X X X X X X X 0 1 2 3 … M X X 0 1 2 3 … M X X 0 1 2 3 … M X X 0 … Row 0 Row 1 Row 2 …
Input stream
Output stream
M 0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 1 2 3 … M M 0 0 … Row N-1 Row N Row 0 (duplicate) …Row 0
M X X 0 1 2 3 … M X X 0 1 2 3 … M X X 0 1 2 3 … M X X X X X X X X X X X X X X X X X X 0 Row NRow N-2 Row N-1
Row N (duplicate)
Next frame
Latency
FPGA Workshop, OIST 88
Two Dimensional PrimingTwo Dimensional Priming
●
Output image
First output pixel Row priming
Column priming
Latency
Flushing
FPGA Workshop, OIST 89
Filter PrimingFilter Priming • Only load each pixel once
– Hold pixels at start of row to enable loading multiple times – Recirculate pixels at end or row for flushing – Recirculate first and last rows from first row buffer
Duplicating border pixels
FPGA Workshop, OIST 90
Linear Filter StructureLinear Filter Structure • Output is a weighted sum of input pixels
FPGA Workshop, OIST 91
Pipelined StructurePipelined Structure • Apply transpose structure to rows
– Automatically makes filter structure pipelined
FPGA Workshop, OIST 92
Reducing the ComputationReducing the Computation • Multiplication by powers of 2 is trivial • Exploiting symmetry
– Many filters are symmetric – Can perform add before the multiplication
• Separable filters – Filter decomposes to two 1D filters – Column filter replaces delays
with row buffers
[ , ] [ ] [ ]x yw i j w i w j=
FPGA Workshop, OIST 93
Morphological FiltersMorphological Filters • Erosion
– Output 1 if all inputs are 1 logical AND within window – Object shrinks and background expands
• Dilation – Output 0 if all inputs are 0 logical OR of flipped window – Object expands and background shrinks
• Opening – Erosion followed by dilation
• Closing – Dilation followed by erosion
, [ , ] [ , ]erosion i jQ x y I S I x i y j∈= = + +∧S�
, [ , ] [ , ]dilation i jQ x y I S I x i y j∈= ⊕ = − −∨S
( )I S I S S= ⊕� �
( )I S I S S• = ⊕ �
FPGA Workshop, OIST 94
Erosion and DilationErosion and Dilation • Duality enables one circuit to be used for both
– Dilation is erosion of the complement (with a flipped window)
FPGA Workshop, OIST 95
Filter DecompositionsFilter Decompositions • Decomposes large filters into a
combination of simpler smaller filters • Sequential decomposition
– Dilation is associative • Dilation • Erosion
• Parallel decomposition – Combines parallel filters
• Dilation • Erosion
– Simplify by making composite filters rectangular
( ) ( )1 2 1 2I S S I S S⊕ ⊕ = ⊕ ⊕ ( ) ( )1 2 1 2I S S I S S= ⊕� � �
( ) ( ) ( )1 2 1 2I S S I S I S⊕ ∨ = ⊕ ∨ ⊕ ( ) ( ) ( )1 2 1 2I S S I S I S∨ = ∧� � �
FPGA Workshop, OIST 96
3x3 Erosion Filter3x3 Erosion Filter • Effectively removes isolated pixels
– Also removes 1 pixel layer from edges • Separable
– 1x3 row and 3x1 column filters • Erosion
– Output 1 if all inputs are 1 logical AND
1x3 filter Row buffer
Row buffer
3x1 filter
Input stream Output
stream
FPGA Workshop, OIST 97
Sobel FilterSobel Filter • Combines horizontal and vertical edge filters
– Constituent filters are separable • Sobel output
– Simplified approximation
2 2H V+
H V+
FPGA Workshop, OIST 98
CORDICCORDIC • Method for calculating trigonometric functions
– Based on incremental rotations
– Rearranging
– Trick is choosing factors to be powers of 2: • Multiplications then become shifts
1
1
cos sin sin cos
k k k k
k k k k
x x y y
θ θ θ θ
+
+
− =
1
2 1
1 21 2 11 2
k k k
kk k k
x x y y
− +
−− +
− =
+
tan 2 kkθ −=
1
1
1 tan cos
tan 1 k k k
k k k k
x x y y
θ θ
θ +
+
− =
( , )k kx y
1 1( , )k kx y+ +
kθ
FPGA Workshop, OIST 99
CORDICCORDIC • Rotate by an arbitrary angle through a series of
rotations – Where dk is direction of rotation
– Result rotates the input vector by • Problem is scale factor at front
– By choosing to always rotate, , this will be constant regardless of angle rotated
– Uncompensated • Gives a gain of approximately 1.64676
1
2 2 1
1 21 2 11 2
k k kk
kk k kkk
x xd y ydd
− +
−− +
− =
+ 1
1
0 tan 2
K k
k k dθ
− − −
=
= ∑
{ 1,1}kd ∈ −
FPGA Workshop, OIST 100
CORDIC Operation ModesCORDIC Operation Modes • Rotation mode
– Starts with desired rotation angle in z – Chooses dk = sign(zk) to converge the angle to zero – Result is to rotate the vector by that angle – Can be used to calculate sine and cosine of an angle
• Vectoring mode – Aligns the vector with the x axis – Chooses dk = -sign(yk) to converge y to zero – Result is magnitude and angle of the vector – Can be used to calculate arctangent
• Each iteration gives 1 bit of the result
FPGA Workshop, OIST 101
CORDIC ImplementationCORDIC Implementation • Direct implementation builds
separate hardware for each iteration – Each iteration gives 1 bit of the
result – Scaled magnitude is not a
problem for edge detection • If necessary may be
pipelined for speed
FPGA Workshop, OIST 102
Laboratory:Laboratory: Streamed Sobel filterStreamed Sobel filter
Laboratory: Sobel Filter and CORDIC Arithmetic
The aim of this laboratory is to implement a Sobel filter and use CORDIC arithmetic to obtain the edge orientation map.
This laboratory will make use of the colour image capture and display developed in the previous session. A clean set of files has been provided (in case you did not get the last laboratory completed). Copy the files into a new directory to work on this laboratory.
1: Top level design for the Sobel filter A block diagram of the key part of the top level design is
Memory buffer
VGA timing
Sync generator
Display
Bayer filter to grey
Sobel filter
We use a 2x2 average filter to convert the raw image into a greyscale image (lines 114-118 in top.vhd). This greyscale image is then passed to the Sobel filter (lines 120-124) which produces the image for the display. The Sobel filter is actually produces 3 outputs. Initially it will provide the linear filtered horizontal and vertical derivative images, along with a delayed input image for comparison. Switches sw(1) and sw(0) are used to multiplex these onto the display (lines 126-128). Later we will produce the edge strength and edge orientation maps.
2: Horizontal and vertical edge filters From the lecture, we can factorise each of the edge filters making up the Sobel filter, enabling us to process with a 1×3 window followed by a 3×1 window. We can share the 1×3 window with the two parallel filters.
1
1 2
1
-1 0 1 1 1 1
-1 0 1
1 3 window
×
1 3 filters× 3 1 filters× Outputs
×2
vf(0)
hf(0)
vf(1)
hf(1)
vf(2)
hf(2)
First we instantiate the make_window entity to build the vertical window. We will handle the image borders by duplicating boundary pixels.
The next step is to perform the actual vertical filtering. The vertical filter uses vertical differentiation, and the horizontal filter uses vertical averaging, as illustrated above. The separate horizontal filters then produce the filtered outputs. The signal declarations define an array of registers
with the first process performing the actual filtering:
Variables are used for intermediate signals. Since they are used immediately, they do not retain their values, and consist of just wires. Four bits are added to width of the intermediate variables. This allows three extra bits (including sign bit) for the filters since the Sobel calculations are not normalised, and one extra bit to allow for the growth in magnitude as a result of the CORDIC rotation.
With the two output images, the three LSBs are dropped, effectively scaling the filter output by dividing by 8. An offset is added to adjust zero to mid-grey, with darker values representing negative gradient, and lighter values representing positive gradient.
The filter has a latency of 1 row and 3 pixels, made up of
• 1 row and 1 pixel for forming the 1×3 window at the start • Combinatorial logic is used for the 1×3 filter calculations, so this takes no clock cycles • The 3×1 filters have 2 pixels latency, including the output register. Although there are 3 registers,
with 3 clock cycles delay, the output corresponds to the centre of the window, after 2 clock cycles.
Build the code and download it to the FPGA to see the effects of the filters:
• sw(1) switches between unfiltered and filtered outputs • sw(0) switches between the horizontal and vertical edge filters.
3: Combining the outputs The final stage is to combine the outputs. We will use CORDIC arithmetic to do this. The algorithm is essentially iterative, although we will unroll it and build separate hardware for each iteration, taking only a single clock cycle.
First, adjust the latency on line 32 to delay the output by an extra clock cycle:
Then comment out lines 57-59, which provide the individual filter outputs, and uncomment lines 87-98 which connect the outputs to the output of the CORDIC block.
Within the second process, we are using CORDIC arithmetic to perform an arctangent of the x and y gradient vector components to get the edge strength and edge orientation.
• The declarations on lines 62 and 63 are arrays of intermediate variables for holding the x, y and angle components at each iteration.
• The tan table on line 64 contains arctangents of successive negative powers of 2, scaled so that 360° = 4096. These will be used later for calculating the arctangent
We are using vectoring mode, which selects the rotation direction at each iteration to adjust the y component to 0. This leaves us with the vector magnitude in the x component, and the vector angle.
• The initial (0th) iteration (lines 67-75) performs an optional rotation by 180 degrees if the x component is negative.
• The initial angle has 4 added to automatically perform rounding (we will truncate the 3 LSB from the angle).
• Subsequent iterations (the loop in lines 76-86) select the rotation direction based on the sign of the y component.
• The remaining lines (87-98) register the outputs.
Compile your design, and download it onto the board. Use sw(0) to select either the orientation or edge strength, and sw(1) to toggle between the original and filtered image.
4: Further work Some possibilities:
• Switch the Bayer filter back to a colour image, and instantiate 3 Sobel filters, one for each colour channel. Hint – you can use a for … generate loop to create multiple copies of the Sobel filter.
• One problem with the orientation image is that it is very noisy (the angle of a low magnitude number is strongly dependent on noise). We can colour code the edge strength by treating the angle as a hue. Add an operation in the processing chain between the Sobel filter and display to perform an HSV to RGB conversion. The conversion is shown on the following page:
o Use the edge strength as the value, V. o Set the saturation, S, to 1, to give fully saturated colours for the edges. o In the CORDIC algorithm, adjust the angle scale to have 360° correspond to 3074 rather
than 4096 (to divide the hue into 6 sectors). The edge orientation is then set as the hue, H.
• Implement another filter (create a new vhdl file).
5: Summary In this laboratory we have:
• Implemented linear gradient filters, using separable filter design techniques • Used CORDIC to determine the magnitude and angle of the edge vector
FPGA Workshop, OIST 103
Session 5:Session 5: FPGA Based Design and FPGA Based Design and Algorithm ImplementationAlgorithm Implementation
FPGA Workshop, OIST 104
Architecture Selection
System Implementation
Problem Specification
Design ProcessDesign Process
Algorithm Development
Defines the problem Determines engineering and functional constraints
Determines sequence of image processing operations
Selects configuration for implementation
Maps the algorithm onto the architecture
FPGA Workshop, OIST 105
Problem SpecificationProblem Specification • Same for FPGA and software based systems
– Translate often vague problem description into an engineering specification useful for design
• Requirements analysis – System functionality – Performance (processing rate, success rate) – Operating environment
• Lighting and optics • Interfacing with support hardware and machinery
– System behaviour in exceptional circumstances – Maintenance issues
• Tradeoff between speed, accuracy and cost
FPGA Workshop, OIST 106
Problem SpecificationProblem Specification • Define the desired result of image processing
– Inputs and outputs • Requires comprehensive knowledge of problem
– Allows valid assumptions to be made • Selection of features to measure
– Selection of set of test images for development • Representative of the imaging task performed
– Appropriate lighting is essential • Much of an image processing problem can be simplified by using
appropriate lighting
FPGA Workshop, OIST 107
Algorithm DevelopmentAlgorithm Development • Heuristic development process
– Trial and error (and experience) – Relies on human vision to evaluate operations
• Requires – System with large number of imaging operations – Interactive system to experiment with alternatives
• FPGA development issues: – Algorithm cannot be developed directly on the FPGA
• FPGAs have no operating system • Place and route times for FPGAs are not interactive
– Requires a separate development environment
FPGA Workshop, OIST 108
Typical Algorithm StructureTypical Algorithm Structure • Preprocessing
– Enhance required information – Suppress irrelevant information
• Extract the required results – Transform data from pixel values to more descriptive symbolic form – Segmentation
• Detect regions which have a common property – Classification
• Identification of parts of objects • Data no longer image based (but may contain position)
– Measurement / update models to reflect input image
• Post-processing – Convert extracted information into the required form
FPGA Workshop, OIST 109
Algorithm DevelopmentAlgorithm Development • Not all software algorithms map well to hardware
– Individual operations need to be architecturally compatible – Algorithm must be developed with computational
architecture in mind • Simulation on development platform limited
– Parallel architecture must be simulated on a serial computer • Relatively slow, especially for clock accurate simulation
– Evaluating effectiveness on a continuous, noisy, real-time video stream is difficult
FPGA Workshop, OIST 110
Development ProcedureDevelopment Procedure • Algorithm developed and tested as software first
– Standard software development techniques used – Enables algorithm to be tested and verified
• Algorithm is then modified to match architecture – Selection of alternative operations where necessary – Algorithm retested
• Algorithm is then mapped to hardware – Matching of algorithm steps to available resources – May require further changes
• Introduction of operation specific caching
FPGA Workshop, OIST 111
Architecture SelectionArchitecture Selection • System level architecture
– Peripheral devices and memory • Computational architecture
– How the computation is actually performed – Split between hardware and software execution
• Design issues – Computational architecture is fixed for a serial processor – For FPGAs, must develop architecture as well as algorithm
- nothing is provided – Must select configuration and computational mode
• Hosted / standalone, streaming / random access
FPGA Workshop, OIST 112
System ArchitectureSystem Architecture
FPGA Workshop, OIST 113
Integrated ConfigurationIntegrated Configuration • FPGA is part of CPU
– Key instructions accelerated within host processor – Data passed through shared registers
• With modern FPGAs, CPU is usually soft processor within the FPGA – FPGA implements custom instructions
• Limitations – Limited data may be passed with each instruction – Limited time to perform the processing
• Usually too fine-grained for image processing
FPGA Workshop, OIST 114
FPGA CoprocessorFPGA Coprocessor • FPGA accelerates particular types of operations
– Like a floating point co-processor • FPGA operates relatively independently of host
processor – Still controlled by instructions from host processor – Used to accelerate time critical or computationally dense
sections of an algorithm • Too tightly coupled for many image processing tasks
FPGA Workshop, OIST 115
Hosted ConfigurationHosted Configuration • FPGA multi-processor with conventional computer
• Host system – Configures FPGA – Stores image in shared memory – Signals to FPGA to begin processing – Results returned in shared memory or FPGA registers
Shared memory FPGA
Host computer system
FPGA Workshop, OIST 116
Hosted ConfigurationHosted Configuration • Computationally intensive tasks are compiled to
hardware – Parallelism of FPGA is exploited – Low-level image processing operations
• Software is used for tasks that cannot be performed efficiently in hardware – Serially bound tasks – Data dependent control – High-level image processing operations
• Primarily used for algorithm acceleration and high performance computing
FPGA Workshop, OIST 117
Hosted ConfigurationHosted Configuration • Host computer usually responsible for
– Image capture and display – User interaction – System communication
• Host operating system is augmented to enable – FPGA reconfiguration – Task scheduling – Debugging
• Key terms – Reconfigurable computing
FPGA Workshop, OIST 118
Standalone ConfigurationStandalone Configuration • All processing is performed
on the FPGA – Image capture – Image processing – Image display – User interaction
• No operating system – Tuning, calibration, user interaction, debugging are more
complex • Configuration usually from flash memory • Primarily used for embedded vision applications
FPGA Workshop, OIST 119
Computational ArchitectureComputational Architecture • Simply porting software generally does not work
– Software is usually optimised for processing on a serial computer – Generally memory bound
• Always reading and writing to memory
• Important to obtain a good match between the architecture and the algorithm – Poor match limits acceleration available
• Makes inefficient use of available resources
• Considerations – Form of parallelism being exploited – Memory architecture – Hardware and software mix
FPGA Workshop, OIST 120
Algorithm TransformationAlgorithm Transformation • Algorithm analysis
– Determines the data flow within algorithm • Both within and between operations
– Software dominated by memory accesses • Computational architecture design
– Exploit the available parallelism – Aim to perform as much processing on
FPGA before writing data to memory • Replace memory storage of variables with registers
• Map algorithm onto architecture
Image processing algorithm
Identify algorithm
architecture
Design hardware
architecture
Hardware implementation
Software
Hardware
FPGA Workshop, OIST 121
Pipelined ProcessingPipelined Processing
• Limited bandwidth between operations – Image is transferred using frame buffer (memory) – Each operation has a latency of one image
• Outer loop of many operations is a raster scan
– Implement using stream processing
Processor 1 Operation 1
Processor 2 Operation 2
Processor 3 Operation 3
Image Image
for {
Operation 1
}
for {
Operation 2
}
for {
Operation 3
}
FPGA Workshop, OIST 122
Pipelined Stream ProcessingPipelined Stream Processing • Serialises the parallelism in a way
that efficiently supports pipelining – Ideal close to image capture or display
• Pixel stream is already serialised
Processor 1 Operation 1
Processor 2 Operation 2
Processor 3 Operation 3
Pixel Pixel
for { Operation 1 Operation 2 Operation 3
}
– Separate processors for each operation – Data passed directly to next processor
rather than via memory • Reduces memory overhead and latency
0 1 2 3 4 5 6 7
… N
0 1 2 3 4 5 6 7 … M Column
R ow
FPGA Workshop, OIST 123
Stream ProcessingStream Processing • Fixed clock rate
– Usually one clock cycle per pixel – Limits the memory bandwidth available
• Acceleration gained through pipelining – Use low level pipelining to meet timing constraints
• Suited to low level image processing operations – Point operations and local filters
• Local operations will require caching – Caching will provide data from previous rows for filters and
other operations
FPGA Workshop, OIST 124
Random Access ProcessingRandom Access Processing • Relaxes hard timing constraint
– Data accessed directly from a frame buffer
• No explicit data access requirements – Pixels can be accessed randomly, as needed – May use several clock cycles per pixel accessed
• Can vary from pixel to pixel
Processor Frame buffer
FPGA Workshop, OIST 125
Random Access ProcessingRandom Access Processing • Most similar to software process
– Easiest to map the software algorithm to • Goal is to reduce the combinatorial delay
– Tries to maximise clock speed to maximise throughput – Use low-level pipelining to minimise clock period
• Acceleration gained by identifying parallel branches – Usually gives less acceleration than stream processing
FPGA Workshop, OIST 126
Loop UnrollingLoop Unrolling • Replace innermost loops with multiple copies of
hardware – Allows longer pipelines to be built
• Innermost loop is parallel in many image processing algorithms – Often only a loop because of serial processing – May enable whole loop to be implemented in parallel
• Functional parallelism
for { for {
XXXX }
}
for { XXXX XXXX XXXX
}
FPGA Workshop, OIST 127
Strip MiningStrip Mining • Replace outermost loops with multiple copies of
hardware – Copies work on different sets of data in parallel – Partition the image or other data over the processors
for { for {
XXXX }
}
for { XXXX
} for {XXXX } for {XXXX } for {XXXX } for {XXXX }
FPGA Workshop, OIST 128
Image partitioningImage partitioning • Distributes different parts of image to different
processors – Requires multiple copies of hardware
Stream input
Stream output
Local memory
Local memory
Local memoryBlock
process
Block process
Block process
FPGA Workshop, OIST 129
Strip Rolling & MultiplexingStrip Rolling & Multiplexing • Strip mining results in separate processor for each
partition – Sometimes only one processor is active in any clock cycle – A single processor can be shared among partitions
• Data is multiplexed based on processor index
Processor Data
Processor Data
Processor Data
Processor Data
Processor Data
Data
Data
Processor Data
Data
Data
Memory
FPGA Workshop, OIST 130
Algorithm RearrangementAlgorithm Rearrangement • Rearrange order of operations to simplify processing
complexity
• Exploit factorisation or separability – Simplifies computational complexity
• Reduce data volume through coding – Run length coding for example
• Enables complete runs to be processed as a single unit
Grayscale morphological
filter Threshold
Binary morphological
filter Threshold≡
FPGA Workshop, OIST 131
Operation SubstitutionOperation Substitution • Replace one or more operations with functionally
similar operations – Gain computational efficiency – Will change the results – Usually the image processing algorithm may be adapted to
compensate
Sobel filter output Colour space conversion
2 2H V+
H V+
.299 .587 .114
-.147 -.289 .436
.615 -.515 -.100
.25 .5 .25
.25 -.5 .25
.5 0 -.5
True output
Approximation RGB to YUV Simplification
FPGA Workshop, OIST 132
Software Based ProcessingSoftware Based Processing • Can be used for higher level image processing
– Large amounts of complex code • Largely sequential in nature
– Called occasionally • Once or twice per frame or less frequently
• Better for handling communication protocols than a purely hardware based approach – Interpreting application protocols is largely sequential
• Hard or soft processor cores can be augmented – User instructions that “call” hardware acceleration blocks
FPGA Workshop, OIST 133
Hardware / Software PartitioningHardware / Software Partitioning • Hardware tasks
– Those that can exploit parallelism – Slow when implemented in software
• Software tasks – Those that are called infrequently or are inherently serial – Inefficient use of resources when implemented in hardware
• Not an either / or selection – Spectrum of mix between hardware and software – Skill is finding the optimum mix for an application
FPGA Workshop, OIST 134
Hardware / Software SpectrumHardware / Software Spectrum Hosted Stand-alone
Hardware / Software mix
C P
U F
P G
A
Software only
Custom instructions
Task partitioning
Hardware only
Custom processor
Custom instructions
partitioning
CPU may be separate or built on the FPGA
FPGA Workshop, OIST 135
System ImplementationSystem Implementation • Differs significantly from software based design • Tasks:
– Map imaging operations onto hardware resources • May require modifying the algorithm • Make full use of available parallelism
– Develop device drivers for peripherals • Provided by OS in software based systems
• Important consideration: – This is hardware design, NOT software design
• Even though languages look like software • Efficient design requires a hardware mindset
FPGA Workshop, OIST 136
Implementation IssuesImplementation Issues • Operations are often expressed in parallel
– Eg filters apply an operation to a local neighbourhood
• BUT algorithms are generally represented serially – Optimised for implementation on serial processors – Parallelising serial algorithms is non-trivial
• Not all software algorithms map well to hardware – Limited memory access under real-time constraints
• Particularly so with streaming mode – Hardware has no program counter, stack, etc
• Recursive algorithms must be redesigned – Must redesign algorithm and/or add caching
• Remap operation rather than translate the algorithm
FPGA Workshop, OIST 137
Implementation ConstraintsImplementation Constraints • Real-time implementation imposes constraints
– Timing constraints • Throughput • Latency
– Memory bandwidth • Memory can only be accessed once per clock cycle • Requires data caching
– Resource constraints • Contention of shared resources between parallel sections • Logic block and other resource limits of FPGA
FPGA Workshop, OIST 138
Algorithm MappingAlgorithm Mapping • Best to develop the algorithm in software first
– FPGAs are not ideal for algorithm development • Long compile, place and route times • Simulation times slow for image processing
• Mapping process – Don’t necessarily map the software algorithm
• Unless it was developed with hardware in mind • Most software is optimised for serial implementation
– Map what the software is doing • Not necessarily the same image processing operations • But performs much the same function • Must redesign algorithm for the architecture • May need to design operation specific caching
FPGA Workshop, OIST 139
Design FlowDesign Flow
Develop working algorithm in software
Map algorithm to hardware
Implement on FPGA
Algorithm Tuning
Define problem
Debug / Test
Simulation test bench
Hardware test
Matlab C++
VHDL
Important to implement a working algorithm
Mapping may require changes to the algorithm
Verifies that hardware algorithm behaves identically to software
Again check that the hardware implementation behaves identically
FPGA Workshop, OIST 140
System DebuggingSystem Debugging • Important to debug the algorithm as much as
possible in software before mapping to FPGA – Not always possible with real-time video processing – Algorithm may be modified during mapping process
• Standalone configuration would require video output even if application doesn’t require it – Enable the developer to see algorithm operation
FPGA Workshop, OIST 141
• Conventional approach is through a test bench – Designed to exercise all components of a design
• Does not actually check if the underlying algorithm actually works • Test bench only validates the implementation of the algorithm • Test bench can load input and processed images from file
141
Simulation Test BenchSimulation Test Bench
281.384 Donald Bailey
Operation under test
Stimulus generator
Response checker
Data file
Test bench
FPGA Workshop, OIST 142
Operation Testing on FPGAOperation Testing on FPGA • Structure
has two parts • Communication with host
– Loads test images into frame buffer – Retrieves results
• Stream interface – Streams image from frame buffer to operation
• Simulates image capture and any preprocessing stages
– Stores output stream back into frame buffer • Host can then compare results with software
implementation
FPGA Workshop, OIST 143
System DebuggingSystem Debugging • Control may be required to
– Freeze the input image • To enable closer examination of what is happening for a particular
input
– View the image after any of the operations, not just the output
– Step through the algorithm one operation at a time • For streaming mode there is not necessarily a frame buffer • Output for display must be generated on the fly
– Show non-image information on the display • Eg detected objects
• All requires extra resources and development!
FPGA Workshop, OIST 144
System TuningSystem Tuning • Many algorithms require tuning
– Setting threshold levels and other parameters • Hosted configuration
– Host system provides user interface – Can write control parameters to registers on FPGA
• Standalone configuration – Must build user interface using the FPGA – May require a separate application for tuning
• Tune the algorithm, and store parameters in flash • Reconfigure the FPGA for the application • Load configuration parameters from flash
FPGA Workshop, OIST 145
Algorithm TuningAlgorithm Tuning • Requires a mechanism for dynamically changing
algorithm parameters – Standard approach is through a set of addressable registers – Can also be used for monitoring algorithm status – Interface often through low speed serial interface
FPGA Workshop, OIST 146
Actual application RGB
to YUV conversion
Colour thresholding
Morphological filter
Bounding Box
Control
Thresholds
Example ApplicationExample Application
Frame buffer
VGA
Box overlay
generator
Histogram accumulation
U-V histogram
accumulation
Histogram display
generator
Additional resources for tuning and debugging
FPGA Workshop, OIST 147
SummarySummary • Design process
– Problem specification – Algorithm development – Architecture selection – System implementation – Design entry
• Necessary to transform to a parallel algorithm – Makes stages architecturally compatible
• Reduces memory access through pipelining and caching – Exploits parallelism within the algorithm
• Important to design for debugging and tuning
Architecture Selection
Algorithm Development
System Implementation
Problem Specification
FPGA Workshop, OIST 148
Session 6:Session 6: Histogram ProcessingHistogram Processing
FPGA Workshop, OIST 149
HistogramsHistograms • Objectives:
– Outline basic flow of histogram processing – Describe histograms accumulation issues – Present an efficient technique for histogram equalisation
• Laboratory objectives – Display histograms of each colour channel of an image – Apply histogram equalisation to a greyscale image
FPGA Workshop, OIST 150
Uses of HistogramsUses of Histograms • Data extraction
– From image statistics • Exposure control • Contrast enhancement
– Histogram equalisation • Threshold selection
– Find valleys between peaks corresponding to object and background regions
• Object classification – Histogram similarity
FPGA Workshop, OIST 151
Building the HistogramBuilding the Histogram • Reset accumulators at start
of each frame • Accumulate the pixel count
for each pixel value – Array of counters or registers
(expensive) • Addressed or indexed by the
incoming pixel value
– RAM • Read / Modify / Write cycle • Dual port (requires a late write)
FPGA Workshop, OIST 152
Building the HistogramBuilding the Histogram • If late write not available
– Cannot meet setup time, or are using synchronous pipelined memory • Must delay write to next clock cycle
– Wrong value read if it is currently being updated • Cache previous pixel
value and count • Use cached count if
current pixel value same as previous
FPGA Workshop, OIST 153
Histogram EqualisationHistogram Equalisation • Enhances contrast
– Monotonic transformation – Makes each pixel value
equally likely
– Expands peaks – Compresses valleys
– Mapping is a scaled cumulative histogram
FPGA Workshop, OIST 154
Calculating the MappingCalculating the Mapping • Cumulate histogram, scale by number of pixels
• Division is expensive (in both delay and resources) – Number of pixels is constant
• Calculate inverse offline and use a multiplication – Use powers of 2
• Only take histogram of centre of image
Address counter
sum
index
+
H istogram m
em ory
÷
scale
LU T
m em
ory
Cumulative histogram
Normalisation
FPGA Workshop, OIST 155
Histogram EqualisationHistogram Equalisation • Cumulative histogram is monotonic
– Avoid division by using repeated subtraction if (sum <= 0) if (sum > 0) sum += hist[index]; hist[index] = 0; lut[index] = map; index++;
sum -= scale; map++;
FPGA Workshop, OIST 156
TimingTiming • Four phases or processes
– Clearing the histogram accumulators – Building the histogram – Process histogram to get mapping LUT – Apply the LUT to the image
• State machine to control timing – Multiplexers to switch histogram memory – Handled by high-level language approaches
Streamed image data Blanking Streamed image data Clear Build histogram Process Clear Build histogram Process
Time
FPGA Workshop, OIST 157
Applying the TransformationApplying the Transformation • Construction requires data from whole image • Modes:
– Frame buffering • Holds image while gathering
data
– Use histogram from previous frame • Assumes image changes slowly • Requires no frame memory
FPGA Workshop, OIST 158
Laboratory:Laboratory: Histogram DisplayHistogram Display
Histogram EqualisationHistogram Equalisation
Laboratory: Histogram Display and Equalisation
The aim of this laboratory is to implement basic histogram processing.
This laboratory will make use of the colour image capture and display developed in an earlier session. Copy the files into a new directory to work on this laboratory.
1: Histogram Accumulation As we saw in the lecture, histogram based processing is divided into four phases. Two of these require read access to the histogram (histogram accumulation, and histogram processing), and two require write access (clearing the histogram, and histogram accumulation). This complicates the design of our system because it is necessary to coordinate access between these various phases.
We use a finite state machine to coordinate access in the design presented here. For histogram display, we will have three states:
• Accumulation of the histogram from the incoming image. • Transfer of the accumulated histogram to a display histogram. This is necessary because we will be
displaying the histogram as an overlay for the next frame, so we need somewhere to display the histogram from while we are accumulating the histogram for the next frame. During the transfer, we will also clear the histogram accumulators for the next image.
• Idle, waiting for the start of the next frame.
Note, the transition from the ACCUMULATE to TRANSFER states must wait until both the input stream, and the display stream are both in the blanking period. The transition goes via INIT_TRANSFER to initialise the signals required for the transfer.
For our colour image, we will accumulate data from the raw image (before Bayer pattern demosaicing). This has the advantage that each raw pixel has only one colour, and a single histogram memory can be used for the colour image (rather than 3 separate histogram memories, one for each colour channel).
Incrementing a histogram bin requires two memory accesses, one to read and one to write the incremented bin. Since this must be performed every clock cycle, a dual-port memory is required. Because of the complexity of integrating the accesses between the different phases, we will separate the processes for reading from the histogram bin, and writing the accumulated result back.
The first step in the accumulator read process (shown on the next page) is to determine the read address (lines 60-76):
• When accumulating, the top two address bits comes from the least significant bits of the y and x address. This is used to determine which phase of the Bayer pattern we are in, hence which histogram the pixel value is accumulated into. The actual pixel value selects the bin.
• In the INIT_TRANSFER state, we initialise the address to 0 for the histogram transfer. • In the TRANSFER state, we systematically step through reading successive bins.
The actual reading of the histogram bin is performed in lines 78-84. Incrementing a bin takes two clock cycles (one to read the value, and the other to write the result). If two successive pixels have the same pixel value, the result from the first pixel is not written to the memory before it is read for the second pixel. Therefore, in this case we simply increment the previous count, rather than reading it from memory.
Lines 85 and 86 ensure that the read is followed in the following clock cycle by a write.
The write process is a little simpler:
• In the ACCUMULATE state, the incremented data is written to the histogram memory. • Otherwise, in the TRANSFER state, the histogram accumulator just read is cleared, and the data
written to the display histogram. • While doing the transfer, we also find the maximum count so that we can scale the histogram
appropriately for the display.
2: Histogram display The “simplest” thing to do with a histogram is display it. Since the width of the display (640) is too narrow for 3 full histograms, we will reduce the histograms for display to 128 bins. For this reason, although each pixel has 12 bits, we will use only 128 bins (7 bits) for each histogram during accumulation. The display is divided into 5 parts, of which histograms will be displayed in 3.
The display process is the final process within the entity:
Within this process we will start at the bottom. This is because we are using internal variables, and we want to use registered values, rather than intermediate values.
• Lines 144-151 determines the histogram scaling. To have the histogram approximately 256 pixels high, we divide the maximum count by 256 to get the count associated with each display row (step). Multiplying this by 479 gives the level corresponding to the top row of the screen. (This makes the bottom row 0, so will always be turned on, enabling the width of the histogram to be seen.)
• At the end of each display row (lines 148-149) the threshold level is adjusted for the next row. • Lines 136-142 read the histogram count for the bin corresponding to the current column during the
display streaming. Bits 8 and 9 are used to select the appropriate histogram, with bits 6 downto 0 selecting the bin.
0 128
256
384
512
640
• Lines 127-134 compare the bin count with the threshold level corresponding to the current row. If the count exceeds the threshold, the output is set with the appropriate colour (1 bit for each of RGB).
Edit top.vhd and make the following changes:
• In the declaration section, declare the 3 bit signal for the histogram display output:
• Next, instantiate the histogram display (lines 120-123). We connect the input to the raw pixel stream before Bayer filtering (raw_pix and raw_s), and produce the output in synchronisation with the display stream (disp_s). In the generic map, we set the histogram to 18 bits (sufficient to count to 218=262144), and the number of bins to 128, *4 for the four phases of the raw Bayer image.
• Finally, use the histogram display output to overlay the histogram on lines 127-132.
Compile the design, and download onto to the FPGA and observe the histograms. You should clearly see the histograms shift as the automatic gain control adjusts the camera gain. Observe the effects of different coloured objects on the histograms.
In the display, the histograms are semi-transparent. For example, the red histogram only affects the red component. Modify the display code (lines127-132) to make them opaque (for example when displaying the red histogram, the blue and green channels are set to 0).
3: Histogram Equalisation The last part of the design is to apply histogram equalisation to the image. Initially we will work on a greyscale image (histogram equalisation is only defined for greyscale images).
Building the histogram is much the same as in the previous example, with the exception that we build a single histogram rather than three.
Instead of transferring the histogram, we will calculate the equalisation mapping. Calculating the mapping follows the division by repeated subtraction described in the lecture. The complicating factor is getting the pipeline timing correct with reading the value from histogram memory (which needs to be done in advance because it takes a whole clock cycle).
The actual mapping is trivial, simply looking up the input pixel in the mapping lookup table. The control signal used to select whether the signal is mapped or passed through.
Edit top.vhd and make the following changes to implement histogram equalisation within the processing chain.
• First change the size of the bayer pixel to 12 bits to represent greyscale rather than colour. • Then declare the signals for the output of the equalisation: eq_p and eq_s.
• We will reuse the Bayer to grey conversion to get the greyscale image for equalisation. Edit the instantiation of the Bayer interpolation filter to the bayer_grey version, and adjust the parameters accordingly.
• Instantiate the histogram equalisation we have just developed. In the code here, we are building a full histogram of the 12-bit input image (4096 bins). In performing the equalisation, we are transferring the result to an 8-bit output image.
• Modify the display to use the timing and equalised pixel outputs.
Compile your design and download it onto the FPGA. Use sw(0) to switch the histogram equalisation on and off.
4: Further work Some possibilities:
• Switch the Bayer filter back to a colour image, and instantiate 3 histogram equalisation modules, one for each colour channel. Hint – you can use a for … generate loop to create multiple copies of the histogram equalisation.
• Modify the histogram display routine to add the histogram display (with 256 bins) to the output of the greyscale histogram equalisation.
• Modify the histogram equalisation to give some other output target histogram shape. (The easiest way to do this is to replace the SCALE constant by a signal that changes with each step. The SCALE gives the target number of pixels for each output bin.)
5: Summary In this laboratory we have:
• Accumulated and displayed histograms associated with a colour image. • Obtained the histogram of a greyscale image and used it to perform histogram equalisation on the
input image.
FPGA Workshop, OIST 159
Session 7:Session 7: ColourColour
FPGA Workshop, OIST 160
ObjectivesObjectives • Objectives
– Explain why RGB is generally unsuited for colour detection – Simple conversion to more suitable spaces – Develop rectangular region detection in 3D colour space
• Laboratory objectives – Implement a simple colour thresholding algorithm – Introduce algorithm tuning issues
FPGA Workshop, OIST 161
Colour DetectionColour Detection • Detect pixels belonging to a set of colours
– Label based on colour – Point operation
– Input • RGB pixel value
– Output • Colour label for each pixel
Input stream
Output stream
Function block
FPGA Workshop, OIST 162
Colour ThresholdingColour Thresholding • Computationally simple approach
– Assign pixels within a box in RGB space to a particular label
– Separate thresholds for R, G, and B • Problem:
– Strong correlation between R, G, and B – All 3 depend strongly on illumination
• Illumination level scales all R,G,B • Movement is generally diagonally • Requires large boxes for each colour detected
– Poor colour discrimination
R
B
G
FPGA Workshop, OIST 163
YUV Colour DetectionYUV Colour Detection
• Change colour space – Reduces correlation between channels
• Eg YUV
– Problem: transformation is expensive because of all the multiplications • YUV based on human perception – not necessary here
0.299 0.587 0.114 0.169 0.331 0.500 0.500 0.419 0.081
Y R U G V B
= − −
− −
FPGA Workshop, OIST 164
V ′
U′
YUV Colour DetectionYUV Colour Detection • Solution – use powers of 2
• Simple Implementation
– Shifts come for free in hardware
1 1 1 4 2 4 1 1 1 4 2 4 1 1 2 20
Y R U G V B
′ ′ = −
′ −
V ′
U ′
Y′
–
+ –
+ Y’
U’
V’
G
R B
÷2
÷2
÷2
÷2
FPGA Workshop, OIST 165
Colour ThresholdingColour Thresholding • Threshold each component independently
– One set of comparisons per colour class
min max
min max
min max
U U U V V V Y Y Y
′< < ′< < ′< <
U′
V ′
FPGA Workshop, OIST 166
Colour ThresholdingColour Thresholding • Lookup table approach
– Represent mapping as LUT – Separate LUT for Y,U and V – One bitplane per colour class 0
1
Vmin Vmax
0
1
Umin Umax
0
1
Ymin Ymax 3 2 1 0Bit
Out
Y’
U’
V’
Y LUT
U LUT
V LUT
FPGA Workshop, OIST 167
Bounding BoxBounding Box • Determines leftmost, rightmost, topmost and
bottommost pixels associated with an object – Position – Size – Aspect ratio
• Works on labelled image – Input pixels are labelled
individually, not as a group • Thresholding • Colour segmentation
– A separate bounding box produced for each label
FPGA Workshop, OIST 168
Streamed ImplementationStreamed Implementation • Resetting: Set init flipflop to 1 • First pixel: If init is 1
– Write forced to xmin, xmax and ymin – Resets init to 0
• Otherwise: Write if box boundary is affected
FPGA Workshop, OIST 169
Multiple ObjectsMultiple Objects • Have an array of structures
– Index by pixel label (object id) – Share update logic – Implement using dual-port RAM
• RAM addressing is effectively acting as a multiplexer
FPGA Workshop, OIST 170
Advantages and LimitationsAdvantages and Limitations • Advantages
– Simplicity – Low processing costs
• Disadvantages – Does not require connectivity of points with the label
• Bounding box may include multiple objects with same label
– Measurements are sensitive to noise – Isolated noise points can make data meaningless
• Requires filtering to remove noise first
FPGA Workshop, OIST 171
Object TrackingObject Tracking • Simple tracking
– Detect target within field of view – Move sensor readout window to centre target within the
image • Issues:
– Improve tracking performance by predicting position in next frame • Kalman filter for example
– Repositioning window flushes image capture pipeline – Ideally, should all be implemented on images streamed
from camera to minimise latency
FPGA Workshop, OIST 172
Laboratory:Laboratory: Colour DetectionColour Detection
and Trackingand Tracking
Laboratory: Colour Detection and Tracking
The aim of this laboratory is to perform colour thresholding (after a colour space conversion), and group the detected pixels with a bounding box. Finally, the bounding box will be used to control the digital camera, adjusting the position of the readout window to keep the target object in the centre of the field of view. The block diagram shows the dataflow for the final design at the end of the laboratory.
Memory buffer
I C controller
2
Bayer filter
Erosion filter
RGB to YUV
YUV to RGB
Colour threshold
Display
Colour tuning
Bounding box
This laboratory will make use of the colour image capture and display developed in an earlier session. Copy the files into a new directory to work on this laboratory.
1: Colour space conversion While we could detect colours directly in RGB colour space, as the brightness changes, this will have a strong effect on all three colour channels. To improve this, we can convert the image into a different colour space which separates the luminance component from the chrominance components. This allows us to allow a broad range on the luminance (to account for changes in brightness) while having tighter selection on the colour components.
Therefore we will convert the image into a variation of YUV colour space, using a conversion matrix which consists of powers of 2 to simplify calculation.
The forward conversion is given by
1 1 1 4 2 4 1 1 1 4 2 4 1 1 2 20
Y R U G V B
= − −
, with the reverse as 1 1 1 1 1 0 1 1 1
R Y G U B V
= − −
In the Y component, twice the weight is given to G since in the Bayer sensor, there are twice as many green pixels as other components. The U component gives a colour difference between magenta and green, while the V gives a colour difference between orange and blue.
To view the difference components, we will use the switch inputs to turn on and off the different colour components , with sw(2) switching the Y, sw(1) switching the U and sw(0) switching the V. Note, when Y is switched off, mid grey will be used, rather than black otherwise the colours will not be seen correctly. However, to see the results on an RGB monitor it is necessary to use the reverse conversion.
The colour space conversions are developed as different architectures within the colour_space entity (see colour_space.vhd). Each conversion has a latency of 1 clock cycle. The values r, g, and b are defined from the concatenated input as aliases to make the code more readable, and functions are defined for the sums and differences. Otherwise, it implements the conversion as in the lecture:
The conversions have already been instantiated within top.vhd to save time. (Additional logic has also been added for displaying detected pixels and displaying the box. These will be used later; don’t worry about them for now.) Compile your design onto the FPGA and experiment with the switches to see the representation of different colours within YUV colour space.
2: Threshold setting The next task in detecting a colour is thresholding the colour components to select the combination that corresponds to the desired colour. There are two aspect to this:
• setting the thresholds (colour tuning), and • determining whether each pixel is within the selected range.
We will use key(2) to control whether we are tuning or not. For tuning, we will analyse the statistics of a 32×32 patch within the centre of the image. The average colour of the pixels within this patch will be used as the target colour, and the thresholds will be offset a fixed amount from that target.
When we are not tuning, we will detect pixels within the tuned thresholds and highlight these in red on the display.
Edit top.vhd to instantiate the colour thresholding component:
This operates on the YUV pixels and works in parallel with the YUV to RGB conversion block. Thresholding has a latency of 1 clock cycle, as does YUV to RGB conversion, therefore the detected pixel stream will be in synch with the displayed RGB pixels.
Compile the design and download it onto the FPGA. Tune colours by pressing push-button key(2) and holding the target colour within the marked square. When you release key(2), the thresholds will be set, and the detected pixels will display. With movement, the automatic gain changes the brightness within the image. The simplest way of handling this is to switch off the automatic gain control (recall that this is controlled by sw(9)). If too many other colours are being detected, you may want to tighten the thresholds. These are set by additional generics of colour_threshold. Set these to narrower values (by adding these to the instantiation above), and recompile to test the design.
3: Bounding box In the previous exercise, each pixel was labelled as belonging to an object or the background on the basis of its colour. Each pixel was considered independently of all the others. The next step is to consider all the detected pixels as belonging to an object region, and to determine the position of the object within the image.
For this we will use the bounding box. It assumes that all detected pixels belong to the target object, and finds the top-most, bottom-most, left-most and right- most pixels within the object. These define a box which bounds the object, determining the object’s position and extent.
The implementation in bounding_box.vhd follows the approach from the lecture.
Like with histogram processing, the bounding box is not completed until the end of the frame. We cannot display the box with the data, because the image was streamed directly from the camera and has not been saved in a frame buffer. Therefore we will display the detected box on the following frame. If the target object is moving, then this will not coincide with the location in the new frame, but does give an indication, and is fine with a static target.
Box_display consists purely of combinatorial logic, so will take no clock cycles.
Instantiate the bounding box within top.vhd. First declare the bounding box structure:
Finally, instantiate our bounding box construction and display components after the threshold:
Compile the design, and download it onto the FPGA to test.
4: Morphological filtering While the bounding box is very simple to calculate, there are three main limitations:
• It does not require that the detected pixels to be connected in any way. All of the pixels detected are considered to belong to a single object. If there are multiple objects within the image, the bounding box will consider them all to part of a single object.
• Any noise pixels on the boundary of the object will cause the boundary to jitter. The bounding box is sensitive to correctly detecting the pixels on the edge of the object.
• It is very sensitive to isolated noise pixels. These pixels, misclassified as object pixels, will cause the bounding box to extend to include them. Since these are unrelated to the target object, they completely distort the bounding box, reducing the usefulness of the data obtained.
Modifying the algorithm to solve the first problem is non-trivial. It requires using connected component labelling, which is beyond the scope of this laboratory. Instead, we will assume only a single target, and use a filter to solve the other two problems. A 5×5 morphological erosion filter will shrink the image by 2 pixels from all sides, and eliminate and noise points smaller than 5×5 pixels. An erosion filter with a square window is separable, so we can efficiently perform the 2-dimensional filtering with a row filter followed by a column filter.
The filter will add latency to the image stream (2 rows and 5 pixels), so it is necessary to also delay the colour pixel stream by the same amount. This will be accomplished through the image_delay component. Note that when we are tuning, we use the detected output to display the tuning box. This will get eliminated by the filter, so we need to add the box back in manually.
Edit top.vhd and add the following declarations:
Next, instantiate the morphological filter and image delay components. Make the other changes as highlighted below to determine the bounding box of the filtered stream:
• The bounding box on line 171 operates on the filtered pixel stream. • Line 174 redraws the tuning box when key(2) is pressed. • The overlay takes the combined bounding box / tuning box for display. • The timing of the display is of the filtered pixel stream. • The filtered detected pixel, and delayed RGB image are shown on the display.
Compile the design, and download it to the FPGA. Check that the bounding box now behaves adequately.
5: Tracking The last step is to use the bounding box position to adjust the location of the camera readout window. This is achieved by writing the new window position to the appropriate register within the camera.
As a result of the way the camera operates, the change in window position is not instantaneous. When the command is sent, the camera has already started exposing the next frame. Therefore, whenever we change the start row, the frame after the following frame is invalid. This causes two problems:
• the data received from the camera for that frame is invalid, and • there is a timing bubble (the timing of the camera is reset).
This timing bubble causes a problem because the camera and display get out of synchronisation. Our logic therefore resets the VGA timing generator to resynchronise, however the monitor goes blank for about a second until it synchronises with the new timing. To solve this problem, rather than have the camera free- running, we provide a periodic trigger signal to the camera to initiate capture. This will reduce the bubble allowing us to perform vertical tracking. We have already instantiated a regular trigger within top.vhd (camera_trigger on lines 99-101), however we need to set the camera into trigger mode. Do this by uncommenting line 45 of the camera initialisation data:
Add the declarations of i2c_trk_req (line 51), i2c_trk_cmp (line 53), wpos_x and wpos_y (line 55). Also change the size of i2c_ack:
Next, edit the definition of i2c_multi_port to add the additional port for tracking commands. We add an additional port (N_PORT has been increased to 2), and additional entries have been added to req and ports to link in the new I2C tracking control signals via this additional port.
Finally, instantiate the tracker logic.
The HOLD_OFF generic causes the tracker to delay 3 frames (1/20 second) after making an adjustment before making another adjustment. We have also connected the enable for the tracker to sw(3). This will allow us to turn tracking on and off.
Compile your design, turn sw(3) off, and tune it for a target colour, and move the target within the field of view. Switch sw(3) on, and see what happens. The display might blank for the first 2 or 3 movements, but after that, it should track vertically without resetting the monitor. The flickering is a result of the bad frames that appear after adjusting the vertical position of the window. (Remember that the image is not being stored anywhere – we are operating directly on the streamed data from the camera.) Press key(0) if you need to reset the system to start again.
6: Further work One possibility:
• Comment out the display of the current camera gain, and program the seven segment display with the current position (wpos_x and wpos_y). With only 2 displays for each, use bits (10 downto 7) and (6 downto 3).
7: Summary In this laboratory we have:
• Use colour space conversion to transform and RGB to a simplified YUV colour space, and back. • Performed thresholding within YUV colour space to detect a target colour. • Used a bounding box to group colour pixels into a target object. • Filtered noise using a morphological erosion filter. • Maintained timing between parallel paths within a pipelined system by introducing appropriate delay. • Implemented target tracking to keep the target object in the centre of the field of view.
FPGA Workshop, OIST 173
Session 8:Session 8: Frequency Domain ProcessingFrequency Domain Processing
FPGA Workshop, OIST 174
Objectives • Objectives
– Look at how information is represented in the frequency domain
– Introduce FFT • Radix 2, Radix 4, Radix 22
– Complex multiplication resources – Application of FFT to filtering
• Laboratory objectives – Implement 2D FFT
FPGA Workshop, OIST 175
Fourier TransformFourier Transform • Decomposes an image in terms of spatial frequency
• Basis functions are periodic – Implies image is periodic in both space and frequency – Real images have conjugate symmetric Fourier transforms
• Fast Fourier transform – An efficient implementation of the discrete Fourier transform
2 ( )( , ) ( , ) j xu yv x y
F u v f x y e π− +=∑∑
FPGA Workshop, OIST 176
• A periodic pattern will have distinct peaks in the frequency domain – Position of peaks gives spatial
frequency – Amplitude of peaks gives
amplitude of corresponding spatial sinusoid
– Phase gives position within the image
– Shape of peaks gives information on the shape and size of pattern
Information in Frequency DomainInformation in Frequency Domain
Computation RequiredComputation Required • For an N×N image:
– Each of the N2 frequencies is a weighted sum of N2 pixels – Requires N4 multiplications (for N=256 => 4.3×109)
• Separability:
– Perform transform on rows then on columns – Requires 2N N-point transforms (2N3) (for N=256 => 3.5×107)
• Factorisability: gives fast transform – Each N-point transform requires N log2N operations – Image requires 2N2log2N operations (for N=256 => 1×106)
FPGA Workshop, OIST 177
2 ( )( , ) ( , ) j xu yv x y
F u v f x y e π− += ∑∑
2 2( , ) ( , ) j xu j yv y x
F u v f x y e eπ π− −
=
∑ ∑
FPGA Workshop, OIST 178
RadixRadix--2 Decimation in Time FFT2 Decimation in Time FFT • Splits input into odd
and even samples – Takes FT of each half
and combines results – Applied recursively
gives FFT • Inputs are in bit
reversed order
FPGA Workshop, OIST 179
RadixRadix--2 Decimation in Frequency FFT2 Decimation in Frequency FFT • Calculates even and
odd frequency components separately – Combines inputs and
takes FT of each half – Applied recursively gives
FFT • Frequency outputs are
in bit reversed order
FPGA Workshop, OIST 180
Complex MultiplicationComplex Multiplication • All multiplications are by
complex twiddle factors
– Requires 4 real multiplications – Reduce to 3 with factorisation – Lifting makes it reversible even with truncation
Factorised
Conventional
Lifting
2 / 2 2cos sinj NN N NW e j π π π−= = −
FPGA Workshop, OIST 181
RadixRadix--4 Decimation in Frequency Butterfly4 Decimation in Frequency Butterfly
• Reduces number of multiplies • Decimates by factor of 4
– Uses 4-point FT as “butterflies”
1 1 1 1 1 1 1 1 1 1 1 1
j j
j j
− − =
− − − −
F f
FPGA Workshop, OIST 182
• Butterflies operate in place on data in memory • First data is streamed in • Then streamed through
a butterfly for each level – Output after last level
• With pipeline delays, the multiplication can be shifted out of radix-4 butterfly
FFT ImplementationFFT Implementation
FPGA Workshop, OIST 183
Pipelined RadixPipelined Radix--2222 ButterflyButterfly • Streamed input and streamed output
– Splits radix-4 into two radix-2 butterflies – Each stage has pipeline delay memory
Address bits
FPGA Workshop, OIST 184
Two Dimensional FFTTwo Dimensional FFT • FFT is separable
– Apply 1D FFT to rows then columns • Multiple rows/columns can be transformed in parallel
– Building parallel hardware blocks • With real data, symmetry can be exploited
– Row FFTs are conjugate symmetric • Two row FFTs can be performed at once by a single FFT unit
– 2D output is conjugate symmetric • Half of column FFTs do not need to be calculated explicitly
– Reduces computation by a factor of 4
FPGA Workshop, OIST 185
Frequency Domain FilteringFrequency Domain Filtering • Linear convolution filters become a product in
frequency domain – Filter function is just weighting frequency components – Linear filter can be thought of in terms of its frequency
response • Most images are dominated by low frequencies
– Low pass filtering will improve signal to noise ratio – High frequencies (edges, fine detail) will be attenuated
• Boosting high frequencies will enhance edges – Will also tend to amplify noise
[ , ] [ , ] [ , ]Q u v W u v I u v=
FPGA Workshop, OIST 186
Wiener FilterWiener Filter • Optimal filter in least squares sense
– Minimises errors resulting from • Attenuation of signal by filter • Noise within the image
• Need to know signal and noise frequency content
– Gain is approximately 1 for frequencies where signal is much larger than noise are
– Frequencies where noise dominates are attenuated • Effective for both random and pattern noise
2
2 2
[ , ] [ , ]
[ , ] [ , ] F u v
W u v F u v N u v
= +
FPGA Workshop, OIST 187
Laboratory:Laboratory: Fast Fourier TransformFast Fourier Transform
Laboratory: Pipelined FFT
The aim of this laboratory is to take and display the Fourier transform of an image. Since the FFT requires the size to be a power of 2, and to enable the image to be displayed and transformed we will restrict the processing to 256 pixels. We will use the radix-22 FFT because each stage requires only a radix-2 butterfly, and a complex multiplier is only required after every second stage.
This laboratory will make use of the image capture and display developed in an earlier session. Copy the files into a new directory to work on this laboratory.
1: Basic butterfly The FFT is built on a butterfly. A radix-2 butterfly effectively divides the image in half, and performs both a sum and a difference between the two halves. When working on streamed data, as the image is streamed in, the first half is saved into a buffer. Then when the second half is streamed in, the butterfly is used to add it and subtract it to the first half. While the sum is streamed out, the difference is recirculated back into the buffer for reading out when the sum is finished. While the difference is reading out, for continuous operation, the next row can be streamed in.
Buffer
Butter!y
Compile the project, within Quartus, and download the design to the FPGA. The design processes the first 256 pixels of each row, displaying the sum and difference on the right side of the display. Experiment, with the camera focussed on some text (for example a business card).
Edit fft.vhd, and change N_BUFF on line 59 to 64 or 32. This will control the length of the buffer. Recompile the design and observe the effects.
2: 1-D FFT The FFT consists of a series of butterflies, with buffer lengths decreasing by powers of 2. After each butterfly, the values are multiplied by a corresponding twiddle factor. In a radix-22 FFT, the butterflies are divided into pairs, with the twiddle factors for the first butterfly being 1 or –j (which is trivial), and a complex multiply is required only after the second butterfly in a pair. The addition and subtraction of each butterfly increases the word length by 1. After the complex multiply, the words are rounded back to their original length. Four such pairs are required for a 256 point FFT.
To implement the FFT, first change the DELAY on line 28 to119. This changes the delay to align the FFT correctly on the display.
Next, comment out the butterfly section on line 58 to 62. Select these 5 lines and Edit » Comment Selection (or the toolbar button). Uncomment the FFT section, from lines 64 to 97 (select those lines and Edit » Uncomment Selection or the toolbar button). This performs the 256 element FFT, then uses CORDIC to determine the magnitude of the result, followed by a logarithm to compress the dynamic range to enable the display to be seen clearly.
Compile the design and download to the FPGA to see the FFT of the first 256 pixels in each line.
The output is hard to interpret because the frequencies appear in bit-reversed order. Much of the next process buffers the FFT log magnitude output and displays it in natural order. Change the output on line 96 from log_mag to br. This will display instead the image in natural order.
Compile this design, an experiment by placing different patterns in the left part of the image to see their Fourier transforms.
3: 2-D FFT To perform a 2-D FFT, we next need to perform an FFT down the columns of the row FFTs. For the size of image we are using, this would be a 256×256 FFT, which requires saving the row FFT data in external memory. Unfortunately, on the DE0, the external memory is DRAM, which is more complex to interface to. It is not just a matter of providing an address and getting the data. DRAM uses a paged structure, and each page (or row) must be opened before access (whether read or write) and then closed before moving to another row. Fortunately the DRAM also uses a banked structure, with the memory divided into 4 banks. One row in each bank can be open simultaneously, enabling the row opening and closing to be pipelined with careful memory mapping.
Streamed 1D-FFT
Camera Display Streamed 1D-FFT
Row FFT Column FFT
Memory Memory
A single FFT block can be used to transform both of the rows as they are streamed in, and of the columns during the remaining frame period. This will necessitate displaying the Fourier transform with the following frame.
The first stage is the streamed row FFT, which performs the transform directly on the data streamed from the camera. For a 256×256 FFT, there are 256 complex frequency values produced. However, since the input
image is real, the output will be conjugate symmetric, requiring only 2 real and 127 complex values to be saved. This is a total of 256 real values which are streamed to the memory by row. The column FFT requires those values to be streamed in by column, There are 129 FFTs required, each of which requires 256 samples (512 real values). However, accessing these by column is more difficult when using DRAM memory.
Working with 16 bits per fixed point real number (minimum for satisfactory results), each row would take 256 16-bit words in memory. While this fits exactly into a single row of DRAM, reading down the column would incur significant overhead, opening and closing each DRAM row for two words.
A better arrangement is to distribute each image row across 4 banks within DRAM (64 words in each). This would give time to open each bank, to enable a continuous stream to be formed, maximising the bandwidth. To avoid the problem of the column scan being in the same bank for successive reads, every 4 rows should be offset by a bank to allow activation and precharge commands to be interleaved. The Write memory map would therefore be:
128 values per row
Column addressRow addressBank
256 rows
0
r0 c0c1c2c3c4c5c6r1r2r3r4r5r6r7
Since all 4 banks can be open simultaneously, it is straight forward to do the bit reversing of the data column address as the samples are written.
128 bit reversed values
Column addressRow addressBank
256 rows
0
r 0
c 0
c 0
c 1
c 1
c 2
c 2
c 3
c 3
c 4
c 4
c 5
c 5
c 6
c 6
r 1
r 2
r 3
r 4
r 5
r 6
r 7
This is also convenient because only every second sample needs to be saved (the other samples are the complex conjugates), enabling 2 writes per pair of samples. DC and Nyquist frequency (the two real values) can be saved together since they are available from the FFT in the same clock cycle. The most convenient memory mode would therefore be bursts of 2 samples in successive addresses.
For reading back, the rows and columns are reversed, so are swapped. Only 128 columns need to be read, but each column has 256 rows. Since each entry has 2 words (for the complex number), the least significant bit remains:
256 values per column
Column addressRow addressBank
128 columns
0
r0c0c1c2c3c4c5c6 r1r2r3r4r5r6r7
The 2 reads per sample will therefore either require buffering, or running the FFT at half speed.
When writing the results back to the second transpose buffer, converting from bit-reversed rows to natural rows would require successive accesses to be in different rows of the DRAM, which is not worth doing. The rows can be read out for display in bit reversed order, without any problem. However, when reading out for display, we also need to read out the negative frequencies (not saved). Since these are complex conjugates from the row transform, the Fourier transform of those columns would be in the reverse order. Therefore two rows must be read out for each row on the display. Readout would be simplified if both rows were in the same DRAM rows. This is achieved by using the most significant bit of the row number to negate the address of the remaining bits:
256 bit-reversed values
Column addressRow addressBank
128 columns
1
r 0
-r 0
c 0
c 1
c 2
c 3
c 4
c 5
c 6
r 1
-r 1
r 2
-r 4
-r 2
r 3
-r 5
-r 3
r 4
-r 4
r 5
-r 5
r 6
-r 6
r 7
r 7
When reading out, the negative frequencies are read first, then the positive frequencies. Note that since the column FFT of both the DC and Nyquist frequencies were done together, they will require additional processing when reading out for the display at the end.
Reading out for display will take 512 clock cycles to read out the 256 complex values. Since these are displayed at 1 per clock cycle, the data will need to start loading earlier to achieve the display rate.
4: Further work Some possibilities (challenging):
• Implement the DRAM controller to display the 2-D FFT on the fly. • Implement frequency domain filtering by multiplying the frequency domain image by the filter
frequency response, and performing an inverse FFT. (The single FFT block can be used for both with appropriate buffering).
5: Summary In this laboratory we have:
• Examined the basic butterfly operation used by the FFT. • Implemented a 1-D FFT. • Outlined the design and memory management scheme for a 2-D FFT.
Supplement: Programming the ROM
Up until now, we have been programming the FPGA directly from the computer. The DE0 also contains a flash memory which can be used to provide an initial configuration on power-up. By downloading the configuration into this, we can create a stand-alone system.
The direct configuration is via a .sof file. We need to get Quartus II to produce a .pof file for programming the flash. Assignments » Device will show the FPGA device. Click on the Device and Pin Options… button and select the Configuration category. Perform the following selections:
Then click OK twice to return to Quartus.
Rebuild the project. This will create two output programming files: <Project>.sof for programming directly, and <Project>.pof which is used for programming the configuration flash, where <Project> is the name of your project file.
Switch the Run – Prog switch on the DE0 to the Prog position to set up for programming the flash. Open the programmer, and change the mode from JTAG to Active Serial Programming. At the prompt, click Yes to clear the current device list. Click Add Device… select EPCS4 to select the configuration EPROM, and click OK.
Select the first line (with the file <none>) in the file pane, click Change File… and select the <Project>.pof file for downloading. Finally tick the Program/Configure checkbox to enable the device to be programmed.
Next click the Start button to download the configuration file. If successful, this will load the configuration into the serial flash device in the board.
The final steps are:
• Power the DE0 down • Change the Run – Prog switch back to the Run position • Power on the board again.
This time, the FPGA should automatically load the configuration from the flash memory.
