# FAST CORNER DETECTOR (fast)

## Introduction

The files needed for this section are here (as zip file). A PDF copy of this text is here.

## Aside: Corner Detectors

| dxxI dxyI | det = (dxxI * dyyI) - (dxyI * dyxI)

| dyxI dyyI | trace = dxxI + dyyI

## Iterators

An example duplicating a simple range with a stride is

iter whilerange(lo : int, hi : int, stride = 1) {

/* Check validity of range. */

if (((hi < lo) && (0 < stride)) || ((lo < hi) && (stride < 0)) ||

for i in whilerange(1, 5) do writeln(i);

for i in whilerange(-1, -5, -1) do writeln(i);

for i in whilerange(1, 10, 2) do writeln(i);

for i in whilerange(1, 5, -1) do writeln(i);

(no output, iterator not executed)

for i in whilerange(-1, -5, 1) do writeln(i);

(no output, iterator not executed)

for i in whilerange(1, 5, 0) do writeln(i);

(no output, iterator not executed)

This example is found in ex_iterator.chpl. Compile and run it with

## Custom Iterators (fast_v1, test_fast_v1)

### Class methods this() and these() (ex_class.chpl)

var circle = new circumference(radius);

The method call on the instance circle is to this(), which we would define inside the class as

proc this(center_x : int, center_y : int) : int { ... }

iter these() { yield pt1; yield pt2; ... }

for (x, y) in new circumerence(radius, center_x, center_y, closed) { ... }

var circle = new circumference(radius);

for (x, y) in circle(center_x, center_y, closed) { ... }

for (x, y) in circle(center_x2, center_y2) { ... }

For the stand-alone mode we will need to implement a constructor and these().

var Lquad : domain(1); /* range for 1st quadrant points */

var quad : [Lquad] 2 * int; /* the points, as an (x,y) tuple */

var quadcnt : int; /* number of points in quad (incl.) */

/* closed is an optional argument. */

proc circumference(radius : int, xc : int, yc : int, closed = true) {

proc set_radius(radius : int) {

/* Second quadrant. quadcnt-1 to not duplicate first point. */

/* Third quadrant. Start at one to not duplicate point. */

var mid = 0; /* start of second half of quadrant */

Lquad = 0..2*r; /* slightly oversize the array */

/* The actual routine sets up the quadrant automatically for

x = nearbyint(sqrt(r**2 - y**2)) : int;

y = nearbyint(sqrt(r**2 - x**2)) : int;

proc circumference(radius : int) {

/* closed is an optional argument */

proc this(xc : int, yc : int, closed = false) {

return circum_iter(xc, yc, closed);

iter circum_iter(xc : int, yc : int, closed : bool) {

/* Same as the 'these' function above, except it uses the arguments

for (x, y) in circle.circum_iter(xc, yc) { ... }

### FAST Corner Detector (fast_v1.chpl, test_fast_v1.chpl)

You can adjust the analysis parameters on the command line:

--outname=<file> greyscale copy with corners marked in red

--space=[LAB|YUV] which greyscale plane to use, L or Y

--radius=# radius of the detector

--minlen=# minimum count of consecutive MORE or LESS pixels

--maxlen=# maximum count of consecutive MORE or LESS pixels

--thr=# greyscale difference to label as MORE or LESS

To run the program on the test image do

bin/fast_v1 --inname=owl.png --outname=owl_corners.png

bin/fast_v1 --inname=colors.png --outname=color_corners.png

chpl --main-module test_fast_v1 -o bin/test_fast_v1 test_fast_v1.chpl

## Corner Suppression (fast_v2, test_fast_v2)

### Generic Classes and Records

You can make a generic class or record in three ways. First, you can create a type member

var data : [Lalloc] eltType; /* our payload */

/* This allows array-like access to the data, ie. instance(index).

It returns an element at the index ind with the type of our

proc this(ind : int) : eltType {

/* This will store an element of the generic type in the array. */

proc append(const in val : eltType) {

var data : [1..initalloc] eltType;

var next : listnode(val.type) = nil;

param INIT_ALLOC = 2; /* values for demo */

var Lalloc : domain(rank=1) = 1..INIT_ALLOC;

var Ldata : domain(rank=1) = 1..0;

proc append(const in val : eltType) {

/* Slice the expansion to trim negative values. */

if (Ldata.high == Lalloc.high) {

Lalloc = Lalloc.expand(GROW_ALLOC)[1..];

/* For demo to show we're re-allocating. */

writeln("grew array to ", Lalloc);

/* Now there's room for the new element. */

proc this(ind : int) : eltType {

for d in data[Ldata] do yield d;

var corners = new chunkarray(corner);

details.xc = 100; details.yc = 50; details.len = 10;

details.xc = 150; details.yc = 75; details.len = 13;

details.xc = 125; details.yc = 100; details.len = 12;

before we can show how to access the data

writeln("corners data in " , corners().domain, " size ",

> corners data in {1..3} size 3

writeln("corner #2 ", corners(2));

> corner #2 (xc = 150, yc = 75, len = 13)

writeln("corner at " c.xc, ", ", c.yc, " len ", c.len);

The full example is in ex_genclass.chpl. Compile and run it with

### Generic Procedures

proc castto(type t, val : real) {

writeln(castto(int(32), 314.159));

writeln(castto(uint(8), 314.159));

proc filltuple(param cnt: int, x) {

for param i in 1..cnt do result(i) = x;

var ex1 = filltuple(4, 2.178);

> (2.178, 2.178, 2.178, 2.178)

writeln(typeToString(ex1.type));

proc filltuple(param cnt : int, x : ?t) {

for param i in 1..cnt do result(i) = x;

compilerError("Values must be of integral type.");

proc isIntegralType(type t) param

return isIntType(t) || isUintType(t);

proc suppress_corners(rawcnr : chunkarray(corner)) : chunkarray(corner) {

You can query details about the generic type. If we had written

proc suppress_corners(rawcnr : chunkarray(?t)) : chunkarray(t) {

inline proc &=(ref lhs : int(?w), rhs : int(w)) {

inline proc &=(ref lhs : uint(?w), rhs : uint(w)) {

inline proc &=(ref lhs, rhs) {

proc HeapSort(Data : [?Dom] ?elType, doublecheck=false, param reverse=false)

inline proc +(x : _tuple, y : x(1).type) where isHomogeneousTuple(x) {

proc fillRandom(arr : [], seed : int(64) = SeedGenerator.currentTime)

where (arr.eltType == real || arr.eltType == imag || arr.eltType == complex) {

### Implementation (fast_v2, test_fast_v2)

Now the details of the implementation, which is found in fast_v2.chpl. Compile it with

proc find_corners(img : clrimage, spec : fastspec) : chunkarray(corner) {

const circle = new circumference(spec.radius);

const Ainside = img.area.expand(-spec.radius, -spec.radius);

var corners = new chunkarray(corner);

if (is_corner_w_details(img, x, y, spec, circle, details)) {

var retval = suppress_corners(corners);

proc suppress_corners(rawcnr : chunkarray(corner)) : chunkarray(corner) {

var suppcnr = new chunkarray(corner); /* corners to keep */

var parent : [rawcnr.Ldata] int; /* heap with parent node */

proc <(c1 : corner, c2 : corner) {

if (c1.xc == c2.xc) then return c1.yc < c2.yc;

proc <=(c1 : corner, c2 : corner) {

if (c1.xc == c2.xc) then return c1.yc <= c2.yc;

/* suppsep is the config constant defining separation of corners. */

for c2 in rawcnr.Ldata[c1+1..] {

if ((rawcnr(c1).xc + suppsep) < rawcnr(c2).xc) then break;

if (abs(rawcnr(c1).yc - rawcnr(c2).yc) <= suppsep) {

/* set_parent builds the heap. */

set_parent(rawcnr, c2, c1, parent);

if (parent(c1) < 0) then suppcnr.append(rawcnr(c1));

## Wrap-Up

## Exercises

1. Create a “spot” detector that covers the circumference and its interior. This can be used to implement a SUSAN corner detector (see http://citeseer.ist.psu.edu/viewdocs/summary?doi=10.1.1.24.2763 for the original paper describing the detector and its implementation). How does the SUSAN compare with the FAST?

2. Using a square kernel for a Gaussian low-pass filter leads to some distortion of the underlying circular symmetry. Write a “spot” convolver that takes a circular kernel.

## Files

The programs and image for this section can be found here. A zip file is here.

A PDF version of this text is here.