Harris Corner Detection

In order to understand Harris Corner Detection, let us consider a grayscale image. Sweep a window w(x,y)(with displacements uin the x-direction and vin the y-direction), Icalculates the variation of intensity w(x,y).


Where:
  • w(x,y)is the window position at (x,y)
  • I(x,y)is the intensity at (x,y)
  • I(x+u,y+v)is the intensity at the moved window(x+u,y+v).

Since we are looking for windows with corners, we are looking for windows with a large variation in intensity. Hence, we have to maximize the equation above, specifically the term:



Using Taylor expansion:



Expanding the equation and cancellingI(x,y)with-I(x,y):



The above equation can be expressed in a matrix form as:



So, our equation is now:


A score is calculated for each window, to determine if it can possibly contain a corner:



Where,

API Syntax

Non-Maximum Suppression:

In non-maximum suppression (NMS) if radius = 1, then the bounding box is 2*r+1 = 3.

In this case, consider a 3x3 neighborhood across the center pixel. If the center pixel is greater than the surrounding pixel, then it is considered a corner. The comparison is made with the surrounding pixels, which are within the radius.

Radius = 1

x-1, y-1 x-1, y x-1, y+1
x, y-1 x, y x, y+1
x+1, y-1 x+1, y x+1, y+1

Threshold:

A threshold=442, 3109 and 566 is used for 3x3, 5x5, and 7x7 filters respectively. This threshold is verified over 40 sets of images. The threshold can be varied, based on the application.

template void xFCornerHarris ( xF::Mat _src, ap_uint<32> points[MAXCORNERS], uint16_t threshold, uint16_t k, uint32_t * nCorners)

Parameter Descriptions

The following table describes the template and the function parameters.

Table 1.xFCornerHarris Function Paramater Descriptions
Parameter Description
MAXCORNERS Maximum number of corners that can be detected by the kernel.
FILTER_SIZE Size of the Sobel filter. 3, 5, and 7 supported.
BLOCK_WIDTH Size of the box filter. 3, 5, and 7 supported.
NMS_RADIUS Radius considered for non-maximum suppression. Values supported are 1 and 2.
TYPE Input pixel type. Only 8-bit, unsigned, 1-channel is supported (XF_8UC1)
ROWS Maximum height of input image (must be a multiple of 8)
COLS Maximum width of input image (must be a multiple of 8)
NPC Number of pixels to be processed per cycle; possible options are XF_NPPC1 and XF_NPPC8 for 1 pixel and 8 pixel operations respectively.
src Input image
points List of corners. The corners are packed in 32-bit format. Lower 16-bits provides the column index and upper 16-bits indicates the row index.
threshold Threshold applied to the corner measure.
k Harris detector parameter
nCorners Output from kernel providing number of corners detected in the input image.

Resource Utilization

The following table summarizes the resource utilization of the harris corner detection in different configurations, generated usingVivado HLS 2017.1version tool for theXilinx Xczu9eg-ffvb1156-1-i-es1FPGA, to process a grayscale HD (1080x1920) image for 1024 corners.

The following table summarizes the resource utilization for Sobel Filter = 3, Box filter=3 and NMS_RADIUS =1

Table 2.Resource Utilization Summary - For Sobel Filter = 3, Box filter=3 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 33 74
DSP48E 13 83
FF 3254 9330
LUT 3522 13222
CLB 731 2568

The following table summarizes the resource utilization for Sobel Filter = 3, Box filter=5 and NMS_RADIUS =1

Table 3.Resource Utilization Summary - Sobel Filter = 3, Box filter=5 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 45 98
DSP48E 13 83
FF 5455 12459
LUT 5675 24594
CLB 1132 4498

The following table summarizes the resource utilization for Sobel Filter = 3, Box filter=7 and NMS_RADIUS =1

Table 4.Resource Utilization Summary - Sobel Filter = 3, Box filter=7 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 57 122
DSP48E 13 83
FF 8783 16593
LUT 9157 39813
CLB 1757 6809

The following table summarizes the resource utilization for Sobel Filter = 5, Box filter=3 and NMS_RADIUS =1

Table 5.Resource Utilization Summary - Sobel Filter = 5, Box filter=3 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 200 MHz
BRAM_18K 35 78
DSP48E 13 83
FF 4656 11659
LUT 4681 17394
CLB 1005 3277
The following table summarizes the resource utilization for Sobel Filter = 5, Box filter=5 and NMS_RADIUS =1
Table 6.Resource Utilization Summary - Sobel Filter = 5, Box filter=5 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 47 102
DSP48E 13 83
FF 6019 14776
LUT 6337 28795
CLB 1353 5102

The following table summarizes the resource utilization for Sobel Filter = 5, Box filter=7 and NMS_RADIUS =1

Table 7.Resource Utilization Summary - Sobel Filter = 5, Box filter=7 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 59 126
DSP48E 13 83
FF 9388 18913
LUT 9414 43070
CLB 1947 7508

The following table summarizes the resource utilization for Sobel Filter = 7, Box filter=3 and NMS_RADIUS =1

Table 8.Resource Utilization Summary - Sobel Filter = 7, Box filter=3 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 37 82
DSP48E 14 91
FF 6002 13880
LUT 6337 25573
CLB 1327 4868

The following table summarizes the resource utilization for Sobel Filter = 7, Box filter=5 and NMS_RADIUS =1

Table 9.Resource Utilization Summary - Sobel Filter = 7, Box filter=5 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 49 106
DSP48E 14 91
FF 7410 17049
LUT 8076 36509
CLB 1627 6518

The following table summarizes the resource utilization for Sobel Filter = 7, Box filter=7 and NMS_RADIUS =1

Table 10.Resource Utilization Summary - Sobel Filter = 7, Box filter=7 and NMS_RADIUS =1
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 61 130
DSP48E 14 91
FF 10714 21137
LUT 11500 51331
CLB 2261 8863

The following table summarizes the resource utilization for Sobel Filter = 3, Box filter=3 and NMS_RADIUS =2

Table 11.Resource Utilization Summary - Sobel Filter = 3, Box filter=3 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 41 90
DSP48E 13 83
FF 5519 10714
LUT 5094 16930
CLB 1076 3127
Resource utilization: For Sobel Filter = 3, Box filter=5 and NMS_RADIUS =2
Table 12.Resource Utilization Summary
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 53 114
DSP48E 13 83
FF 6798 13844
LUT 6866 28286
CLB 1383 4965

The following table summarizes the resource utilization for Sobel Filter = 3, Box filter=7 and NMS_RADIUS =2

Table 13.Resource Utilization Summary - Sobel Filter = 3, Box filter=7 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 65 138
DSP48E 13 83
FF 10137 17977
LUT 10366 43589
CLB 1940 7440

The following table summarizes the resource utilization for Sobel Filter = 5, Box filter=3 and NMS_RADIUS =2

Table 14.Resource Utilization Summary - Sobel Filter = 5, Box filter=3 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 43 94
DSP48E 13 83
FF 5957 12930
LUT 5987 21187
CLB 1244 3922
The following table summarizes the resource utilization for Sobel Filter = 5, Box filter=5 and NMS_RADIUS =2
Table 15.Resource Utilization Summary - Sobel Filter = 5, Box filter=5 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 55 118
DSP48E 13 83
FF 5442 16053
LUT 6561 32377
CLB 1374 5871

The following table summarizes the resource utilization for Sobel Filter = 5, Box filter=7 and NMS_RADIUS =2

Table 16.Resource Utilization Summary - Sobel Filter = 5, Box filter=7 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 67 142
DSP48E 13 83
FF 10673 20190
LUT 10793 46785
CLB 2260 8013

The following table summarizes the resource utilization for Sobel Filter = 7, Box filter=3 and NMS_RADIUS =2

Table 17.Resource Utilization Summary - Sobel Filter = 7, Box filter=3 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 45 98
DSP48E 14 91
FF 7341 15161
LUT 7631 29185
CLB 1557 5425

The following table summarizes the resource utilization for Sobel Filter = 7, Box filter=5 and NMS_RADIUS =2

Table 18.Resource Utilization Summary - Sobel Filter = 7, Box filter=5 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 57 122
DSP48E 14 91
FF 8763 18330
LUT 9368 40116
CLB 1857 7362

The following table summarizes the resource utilization for Sobel Filter = 7, Box filter=7 and NMS_RADIUS =2

Table 19.Resource Utilization Summary - Sobel Filter = 7, Box filter=7 and NMS_RADIUS =2
Name Resource Utilization
1 pixel 8 pixel
300 MHz 150 MHz
BRAM_18K 69 146
DSP48E 14 91
FF 12078 22414
LUT 12831 54652
CLB 2499 9628

Performance Estimate

The following table summarizes a performance estimate of the harris corner detection in different configurations, as generated usingVivado HLS 2017.1tool for Xilinx Xczu9eg-ffvb1156-1-i-es1 FPGA, to process a grayscale HD (1080x1920) image.

Table 20.xFCornerHarris Function Performance Estimate Summary
Operating Mode

Operating Frequency

(MHz)

 Configuration Latency Estimate

Sobel

Box

 NMS Radius Latency(In ms)
1 pixel 300 MHz 3 3 1 7
1 pixel 300 MHz 3 5 1 7.1
1 pixel 300 MHz 3 7 1 7.1
1 pixel 300 MHz 5 3 1 7.2
1 pixel 300 MHz 5 5 1 7.2
1 pixel 300 MHz 5 7 1 7.2
1 pixel 300 MHz 7 3 1 7.22
1 pixel 300 MHz 7 5 1 7.22
1 pixel 300 MHz 7 7 1 7.22
8 pixel 150 MHz 3 3 1 1.7
8 pixel 150 MHz 3 5 1 1.7
8 pixel 150 MHz 3 7 1 1.7
8 pixel 150 MHz 5 3 1 1.71
8 pixel 150 MHz 5 5 1 1.71
8 pixel 150 MHz 5 7 1 1.71
8 pixel 150 MHz 7 3 1 1.8
8 pixel 150 MHz 7 5 1 1.8
8 pixel 150 MHz 7 7 1 1.8
1 pixel 300 MHz 3 3 2 7.1
1 pixel 300 MHz 3 5 2 7.1
1 pixel 300 MHz 3 7 2 7.1
1 pixel 300 MHz 5 3 2 7.21
1 pixel 300 MHz 5 5 2 7.21
1 pixel 300 MHz 5 7 2 7.21
1 pixel 300 MHz 7 3 2 7.22
1 pixel 300 MHz 7 5 2 7.22
1 pixel 300 MHz 7 7 2 7.22
8 pixel 150 MHz 3 3 2 1.8
8 pixel 150 MHz 3 5 2 1.8
8 pixel 150 MHz 3 7 2 1.8
8 pixel 150 MHz 5 3 2 1.81
8 pixel 150 MHz 5 5 2 1.81
8 pixel 150 MHz 5 7 2 1.81
8 pixel 150 MHz 7 3 2 1.9
8 pixel 150 MHz 7 5 2 1.91
8 pixel 150 MHz 7 7 2 1.92

Deviation fromOpenCV

InxfOpenCVthresholding and NMS are included, but inOpenCVthey are not included. InxfOpenCV, all the blocks are implemented in fixed point. Whereas,inOpenCV, all the blocks are implemented in floating point.