Rotation Invariant Histogram Of Gradients Via DFT

I have successfully used HoG for a number of object recognition tasks. In fact I have found it to be a ridiculously good image descriptor particularly for rigid bodies. It can easily differentiate between various objects given very few training samples and is much faster than any of the existing object detection algorithms. While I know the current trend among researchers is toward CNNs, I also feel that CNNs are quite computationally expensive and require extensive training as opposed to HoGs which can be easily implemented on embedded devices.

One of the major problems with HoG though is that HoG is not rotation invariant. The naïve way of solving this problem is by shifting the histogram bins one by one then measuring the distance between bins. Naturally, this is a very expensive process on a large scale. The time complexity of this would be O(n^2). Naturally it would be more convenient to find something that performs the same task in a faster manner.

The task of shifting the histogram bin by bin smelled awfully like correlation – in fact it is correlation. One of the cool properties of correlation is that it has a nice mathematical property:

Let F(x) be the Fourier transform of x.

\star is the correlation operator.

a\star b = F^{-1}(F(x)^{*}F(x))

So lets try it.

I generated a random histogram:

import matplotlib
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline 
arr = np.random.rand(20)
plt.plot(arr)
plt.show()

g1

Next I wrote a shift function:

def shift_array(array,quantity):
     shifted_array = [0.0]*len(array)
     i = 0
     while i < len(array):
         shifted_array[i-quantity] = array[i]
          i+=1
     return shifted_array
arr_shifted = shift_array(arr,3)
plt.plot(arr_shifted)
plt.show()

g2

Now lets try the trick:

arr1 = np.fft.rfft(arr)
arr2 = np.fft.rfft(arr_shifted)
output = np.fft.irfft(np.conj(arr1)*arr2)
plt.plot(output)
plt.show()

g3

Lets try on arr_shifted:

arr_shifted2 = shift_array(arr,9)
arr1 = np.fft.rfft(arr)
arr2 = np.fft.rfft(arr_shifted2)
output2 = np.fft.irfft(np.conj(arr1)*arr2)
plt.plot(output2)
plt.show()

g4

Notice the peak shifted! This could well tell us how much shift there is. Lets check to see:

print(20-np.argmax(output2))
print(20-np.argmax(output))

This gives us peaks at  9 and 3. Exactly the amount we shifted!

But how about comparison? While we can determine the angle of best fit, how do we know whether its actually a fit? Lets take a look:

arr_diff = np.random.rand(20)
arr1 = np.fft.rfft(arr)
arr2 = np.fft.rfft(arr_diff)
output2 = np.fft.irfft(np.conj(arr1)*arr2)
plt.plot(output2)
plt.show()

g5

Notice how there is no clear peak. One could use simple mean and stdev to show that there is no strong peak. This would in effect give us an estimate for how strongly correlated the values are.

Expanding Vocabulary Capabilities of µspeech

In order to take into account the varying complexities of vocabulary used we looked at offline algorithms for skewness. Now I propose a simpler method. Skewness requires a very large number of multiplications and divisions to be performed. This makes it unsuitable for quick calculations on an AVR as the AVR architecture used by an arduino does not contain a multiply instruction, so multiplication is implemented by software not hardware. In order to speed the process up, I came up with another simple yet effective (but not reliable) measure of skewness.

We treat every utterance (syllable) as a probability distribution of individual phonemes. To test the order of which phoneme comes first we record the number of phonemes per unit time. So every 16 cycles we sample the number of phonemes, and from that one keeps a catalog of statistical features

Skewness can be looked at graphically:

Figure 1. Skewness of a unimodal distribution

As one can see the mode of a negatively skewed distribution is to the right of the center of the distribution. Thus the mode – median is positive. This would be opposite for a positively skewed graph. So µSpeech uses this property to determine the order of a sound in an utterance.

Regarding µSpeech 4.1.2+

Dear Users of µSpeech library,
With the release of the 4.2.alpha library I have been reciveing a lot of mail as to how the debug µSpeech program does not work. I sincerely, apologize for this inconvenience as I have very little time on hand to address the issues associated with 4.1.2+ and 4.2.alpha. I realized that I had made the error of not flagging 4.1.2 as a pre-release: I have fixed this now. I also realized that the documentation that I have on youtube is back dated I will be addressing this as soon as possible.

If anyone has the time and is willing to look into why debug_uspeech is giving trouble, please feel free to create a pull request on github. Due to the fact that I am currently going through my school finals, I am unable to devote the time required to address this issue. Please revert back to µSpeech 4.1.1.

Sincere Apologies,

Arjo Chakravarty

 

P.S. If you wish to play with 4.2.alpha then there is a copy of the original debug uSpeech here: https://gist.github.com/arjo129/9c73ec533b2b1a6f91b4/

Wiring two Arduino’s to do your bidding (using I2C)

Ok, so making rovers with one Arduino is so overdone. What if you had two rovers that worked together to solve problems. Or even turn. This can be fairly challenging. In order to achieve communication between to Arduino’s, one can use the two wire interface, known as I2C. I2C is a method of communicating between the Arduino’s. One can connect 100 Arduino’s all on the same line to make a super-duino, but for now lets keep it down just to two.

Many peripherals can be attached to your Arduio (µC) via this protocol. One Arduino acts as the all powerful overlord (a.k.a master).

Schematic of generic I2C circuit (courtesy wikipedia)

Lets put this in context of two Arduino’s. Here’s how you wire them:

Schematic for your Arduino’s, squiggly lines correspond to resistors (courtesy instructables).

So one Arduino will be the master and one the slave. It’s up to you which one you decide will do what – however the master is programmed separate from the slave. So you will need two programs: one for master, and one for slave.

Now for the code. The actual I2C protocol is fairly complex, however the folks at Arduino have simplified the process significantly. They do this through the use of a library. A library stores extra code which may be useful in order to simplify your life. The library it is stored in is known as Wire, so at the top of both the programs attach:

#include <Wire.h>

Now lets deal with the commands that can be sent: left, right, stop and reverse. We can use something known as preprocessor directives to handle these commands. Again at the top of both the master and slave copy and paste the following:

#define LEFT 0
#define RIGHT 1
#define STOP 2
#define REVERSE 3

Now we will have to deal with the slave differently. Because I2C supports multiple devices, each slave device has its own address (a number that identifies it anywhere between 1-127). So in the void setup() function the following needs to be placed:

void setup(){
  ... //some of your code
   Wire.begin(6); 
}

You have declared your slave as having the address 6. This is kind of like the IP address of a computer, or the URL which points you to this website. Next you have to create a function which responds when the master comes around to command the slave.

void setup(){
  ... //some of your code
   Wire.begin(6);
   Wire.onReceive(followCommand); 
}

We have not yet defined followCommand, the function that will follow the master’s orders, but we shall implement it now (full code for slave listed):

#include <Wire.h>
#define LEFT 0
#define RIGHT 1
#define STOP 2
#define REVERSE 3

void followCommand(int command){
   //what your robot will do
   if(command == LEFT){
     //Write code for turning your robot left
   }
   if(command == RIGHT){
     //Write code for turning your robot right
   }
   //You get the idea...
}
void setup(){
   //some of your code
   Wire.begin(6);
   Wire.onReceive(followCommand); 
}
void loop(){
}

We have now implemented a slave, but we need to implement a master. This is easier. The master has no address so the setup would look like this:

void setup(){
  //Your code...
  Wire.begin();
}

To send a signal the following commands can be used:

  Wire.beginTransmission(6); // transmit to device #6
  Wire.send(LEFT);              // sends LEFT Change to whatever
  Wire.endTransmission();

So the master program would look something like this:

#include <Wire.h>
#define LEFT 0
#define RIGHT 1
#define STOP 2
#define REVERSE 3

void setup(){
   //some of your code
   Wire.begin(); 
}
void loop(){
  //Some code
  //Suddenly you want to transmit a message to make the slave turn left
  Wire.beginTransmission(6); // transmit to device #6
  Wire.send(LEFT);              // sends LEFT Change to whatever
  Wire.endTransmission();
  //Some more code
}

Upload the master program to the master Arduino and the slave program to the slave Arduino and you are ready to go!

Creative Coding Quick Reference Sheet

In this page we shall begin to program our robot. To understand how to program we first need to know how a computer works. A computer understands nothing. It is up to the programmer to tell it what to do. At the heart of the computer is a CPU. The CPU translates a piece of machine code into a series of mathematical operations it performs on its inputs. When we program, we program in a structured language such as C++ or Java which is then translated by a program known as the compiler into machine code. The machine code is interpreted by a CPU and translated into the mathematical operations. Java is a little special in this aspect as when you compile a piece of Java it gets converted to Java byte code. The program/application file gets interpreted when a user runs the application through a program known as the Java Virtual Machine. The Java VM translates byte-code to machine code on the fly.

Key components of a programming language

Programming languages are the way we instruct our computers. In this club we will use JAVA and C++. For our purposes, Java is used by the processing application on our desktop and the mobile phone and C++ is used by the Arduino micro-controller. The two languages have their similarities in terms of the way we express ourselves. Most other programming languages follow a similar pattern. Click on the tables to enlarge them.

Screen Shot 2014-03-06 at 7.54.49 PM

Screen Shot 2014-03-06 at 7.55.42 PM

The semicolon (;) and other grammar

In both Java and C++ one must put a semicolon at the end of every statement made. Its basically like a full stop. Both languages also ignore spaces.

Functions

Computers are stupid, so apart from the table above the computer understands nothing else. Thus there is no such thing as special words that mean something. What programmers have done is created their own words known as functions.

In C++(arduino) a function looks like this:

void left(){
     \\tell your robot how to turn left
}

One would invoke the function:

    left();

A function can take an input and give an output:

    int add1(x){
       return x+1;
    }

One can call this by

add1(1);

To handle output one would create a variable to store the data returned.

int val = add1(1); //val will equal 1+1 = 2

Easy.

Now how do you use these? Well, generally the Arduino and Processing environment come with what is known as a library. The libraries provide a list of functions to make life easier (otherwise you would have to write a whole operating system, or tell the arduino how to turn on a pin which is fairly nasty compared to digitalWrite(9,HIGH);

Where to go from here

http://processing.org/learning/objects/

http://processing.org/learning/pixels/

http://arduino.cc/en/Tutorial/AnalogReadSerial

http://arduino.cc/en/Tutorial/DigitalReadSerial

Using skewness to perform syllable recognition – Part I (Theory)

Currently the syllable class contains an accumulator for various letters. If these letters exist it corresponds to a special syllable. I however think that this is fairly limited because “fish” and “shift” will be interpreted as the same word. Yet, µSpeech should be capable of better: we are able to tell when an individual letter has been said. For instance the occurrence of “f” in fish should occur more at the beginning, where as the occurrence of “f” in “shift” should occur at the end.

For solving this problem I have been considering two methods: The skewness and a method based on pure calculus. Today I will explore Skewness.

Skewness – The theory

Skewness is a measure of how something leans to one side. Its statistical definition is:

\frac{\mu_3}{\sigma^3}

Where \mu_3 is the 3rd moment of the mean i.e E[(x-\mu)^3].

Now going back to High school mathematics:

E[(x-\mu)^3] = E[x^3 - 3x^2\mu + 3x\mu^2 - \mu^3] = E[x^3] - 3\mu E[x^2] + 3\mu^2 E[x] - \mu^3

Given that \mu = E[x]:

E[(x-\mu)^3] = E[x^3] - 3\mu (E[x^2] - \mu^2) - \mu^3

Since \sigma^2 = E[x^2]-\mu^2:

E[(x-\mu)^3] = E[x^3] - 3\mu \sigma^2 - \mu^3

This results in the necessity for the algorithm to compute 3 variables: E[x^3], \mu, \sigma^2

Making the algorithm online

Now given that µSpeech has stringent memory requirements it seems imperative that we devise the algorithm so that the following can be done:

  • Data is not kept in an array.
  • Computation is minimal.

Thus keeping these in mind it seems necessary to look at ways of computing the three variables online. To start with lets tackle the simplest algorithm, the one for µ.

Given that \mu = E[x] = \sum n_i p_i = \sum \frac{x_i}{n}, one can write an algorithm as such:

\mu_i = \mu_{i-1} + \frac{x_i - \mu_{i-1}}{i}

This can be extended to E[x^3]:

E[x^3]_i = E[x^3]_{i-1} +\frac{x^3_i-E[x^3]_{i-1}}{i}

The third value which we need to compute \sigma^2.

\sigma^2 = E[x^2]-E[x]^2

So we need to find E[x^2]:

E[x^2]_i = E[x^2]_{i-1} +\frac{x^2_i-E[x^2]_{i-1}}{i}

Part 2 coming soon.

The “Lazy” Keyword

Javascript sharp has learnt to procrastinate. The lazy keyword is a new keyword introduced into JS#. It enables lazy loading (i.e the determination of the variable is procrastinated). This means that the variable will only be computed when the value is used. An example would probably be easier to understand.
var auto n = 9+3
document do write n .

Would compile to :
var n = 9+3
document.write(n);

Where as using lazy instead of var would look like this:
lazy n = 9+3
document do write n .

this would translate to:

document.write(9+3);

Currently the lazy keyword is buggy and would only support the following syntax lazy [variable name] = [javascript expression]