Pre Processing- A necessity

Eye Detection Algorithm 

There is a quite innovative eye center detection algorithm which works on a principle that, for all points lying on a circle, the normal from each point on the circle passes through  the center of the circle.
First we need to define a term, i.e. Gradient vector, so here it goes.

Gradient vector: It is a vector which is normal to the curve the pixel lies on. Therefore for a point on a circle[we don't know the circle yet], if we somehow approximate[even badly], the boundaries of the circle as slight edges[done by some algo], then the gradient vector of the pixel[lying on the circle] would  be in direction perpendicular to edge[the curve the pixel lies on.] and thus would most likely be close to the normal of the point[on the circle], which would mean that it passes through the center.

Now, the main algorithm goes something like this:

 First gradients are found at each pixel in the region where the eye lies[rectangle can be generated by some heuristic]. Therefore, if no edge passes through that pixel, then the pixel's gradient is zero.

now randomly choose a center. For that center, for every other pixel, compute the normalized distance vector from the center to that pixel. Now, take the dot product of this distance vector with the gradient of the pixel in question. Do this in  iterative manner for all pixels for this center and keep adding all the values. Repeat this whole process for different center positions. Whichever center in your search space gives this highest cumulative value, is most likely the circle center.
/*Give the link of the paper which introduced this thing*/

Histogram Equilization 

Trivial technqiue don't fully exploit the capability of histogram equilization. They are usually used to smoothen the image of any drastic lighting variations across the image. However a paper discovered a awesome way to apply it to an image. So here it goes:

Divide the image vertically in 2 regions, symmetric about the nose. Now apply histogram equilization on both the regions separately in the following manner.

For the left eye region, make the image go from dark to lighter as we move from the left eye towards the nose.

Similarly for the right eye region, make the image go from dark to lighter as we move from the right toward the nose.

Also apply it on the whole face, starting from darker at the sides and becoming lighter as we move towards the center[nose]

EigenFaces

The PCA approach to face recognition, popularly known as EigenFaces happened courtesy a couple of MIT students, who decided to use hard core mathematics to derive one of the first algorithm for Face Recognition. The original paper can be found here. In principal, this Algorithm performs a linear transformation, converting a point[a face] in high dimension image space  to a point[face] in lower dimension subspace[ eigenspace].

It is one of the earliest approach in face recognition and is a fairly accurate algorithm. The one major plus point of using eigenFaces approach is that it is extremely fast, a quality desirable in real life applications. However, it does suffers from luminance variation and pose variation. It is also not suited to handle cases of partial occlusion.


Enlisting all the data structures before the algorithm ensures clarity throughout the tutorial. If you have any confusion later on in the algorithm, you can simply cross check the dimensions of the formula.

faces: n x d
       matrix in which each row is a linear array of pixels of a facial image
eigenVectors: n x n
       each row corresponds to a eigenVector of size n. They are all mutually orthogonal
eigenValues: 1 x n
       each entry is the eigenValue of the corresponding eigenVector. 
eigenPCA: k x n
       top k eigenVectors are decided based on their eigenValues and stored in eigenPCA matrix.  
eigenFaces: k x d
       affect of each eigenVector on each face in the faces matrix is stored in the eigenFaces matrix
weights:  n x k
       affect of each eigenFace on each face in the face matrix is stored in the weights matrix
affect: 1 x k
       affect of each eigenFace on the test image is stored in the affect matrix

Before stating the algorithm, it is worth mentioning that eyes, nose and eyebrows carry the bulk of the information required for identification and therefore should be in the image to give any sort of respectable accuracy. Diving head first into the algorithm, we process it in several modular steps.

1. Input-    read the training images via any imaging library and convert the training images from RGB to gray scale format. Convert each image into a pixel array and store it as a row in the faces matrix.
Various imaging libraries which can be used for this purpose are PIL, openCV etc.
                                                                                                                                                                

2. Adjusting-  calculate a mean face by taking the average of all the rows in the faces matrix. Then
subtract from each row(facial image) the mean face. We call the resultant matrix adjustedFaces.

                    adjustedFaces = faces - meanFace
                                                                                                                                                                

3. Covariance-  calculate the covariance matrix as square of adjustedFaces. If adjustedFace_tr is the transpose of the adjustedFace matrix. This is a symmetric square matrix.
         
                    covariance = adjustedFace * adjustedFace_tr
                                                                                                                                                                

4. EigenValues- calculate the eigenVectors along with their corresponding eigenValues from the covariance matrix. EigenVectors thus obtained are mutually orthogonal. Again, it is better to use a function for this step. if working with matlab, use the eig() function.

                  eigenValues,eigenVectors =linalg.eigh(covariance)

                                                                                                                                                                

5. PCA-  sort the eigenVectors in descending order according to their eigenValues. We select the top k eigenVectors and store them in a matrix eigenPCA. PCA is used to ensure that we discard the most insignificant of features. However keeping it too low a number often means a high dependency is placed on only a few features. Generally about 3/4 of the number of total EigenVectors should do the trick

                  k = ceil.(len(eigenVectors) * 0.75)
                  eigenPCA = sortedEigenVectors[:k]
Hereafter whenever  we talk about eigenVectors, we mean the ones in eigenPCA
                                                                                                                                                                

6. EigenFaces-  calculate affect of each eigenVector on each face.
             
                  EigenFaces = eigenPCA x adjustedFaces_tr
                                                                                                                                                                

7. weights- We calculate affect of each eigenFace on each face. Each row of weights matrix stores the weight of all EigenFaces for one face image. Therefore in each column, we get the weight of one eigenFace on all the faces. let EigenFaces_tr be the transpose of EigenFaces

                   weights = adjustedFaces x EigenFaces_tr

Each row of weights matrix corresponds to the feature vector for one input training image.
                                                                                                                                                                


8. Testimage- Take input the test image. Preprocess as mentioned in step 1. Store it in a vector Testimage. Calculate affect of each eigenFace on the Testimage and store it in affect vector.

                    affect = Testimage x eigenFace_tr

affect vector is the corresponding feature vector of the test image.
                                                                                                                                                                

 9.a Model- Use the rows of weight matrix(read feature vectors) to fit and train a model to help in Face Recognition later on. The model can be any machine Learning one like RBF Neural Networks, SVM. At a later stage, we input a test image's feature vector affect to the model and expect it to output if it belongs to the same person or not. 

9.b Matching- calculate distance of test image feature vector from feature vectors stored in weights matrix. Distance can be euclidean, Mahalanobis, etc. Classify image as belonging to the same person or not based on whether the distance calculated is within the threshold(a experimental value:default=1)
                                                                                                                                                                

*Algorithm ends

However the algorithm mentioned above is a classic implementation mentioned in the research paper which first introduces this technique. It is not the most efficient and accurate technique for applying Eigenfaces.
Many variants have come up which significantly outperfom the classic implementation.

In my experience, The classic implementation gives a success rate of 50-60% while an efficient implementation yielded 75% accuracy performance. Note that these are informal measures, but were performed rigorously.

side note: if you have read papers that quote >90% accuracy for any 2D face recognition algorithm, ignore their results. They are bullshit and are taken in extremely constrained environment not at all related to any real life scenario.

Alternative Implementation:

I. We can implement a different matching technique altogether once we have the eigenFaces in step 6.In this alternate version, the sequence of steps [beginning from 7] look like:

6. Let the eigenface vectors represent a logical subspace. Then this subspace is shown by the eigenFaces matrix. We project the test image in this subspace.

                                    meanEF = numpy.mean(eigenFaces,axis=0)
                                    ProjectedTestImage = (TestImage - meanEF)*eigenFaces.transpose()
_________________________________________________________________________________
                                   
7. After that, we reverse project the test image from the eigenspace to the image space. This is achieved by reversing the above steps. i.e.
           
                                    NewTestImage = (ProjectedTestImage * eigenFaces )+ meanEF
_________________________________________________________________________________
8. As a distance metric, we compare the distance between the test image and the new test image. If this distance is above a threshold distance, we classify the testImage as belonging to  a different person.

                                    dist = numpy.linelg.norm(NewTestImage - TestImage)
                                    if dist < threshold:
                                         samePerson=true
                                    else:
                                         samePerson=false
________________________________________________________________________________

II Another alternative is to perform a non linear mapping from image space to eigenspace instead of the linear mapping we currently employ. It means we change the style in which we compute the covariance matrix. We don't do a simple dot product anymore. We make use of kernels. Yes, these are the same kernels you read about in Support Vector Machines. For those who do not know about them, might consider reading /*[link]this*/ first. For our purpose, we may use either:

polynomial kernel     K = (x . y)**d   where d>0
gaussian kernel         K = e**((|x-y|**2)/2*sigma *sigma)   where sigma ->standard deviation
sigmoid kernel         K = /* Insert formula here*/

Data set:
For implementation purposes, for optimal accuracy, it is advisable to have approximately 15. images per person in your dataset . Research shows that after top 10 eigenvectors, the eigenvalues grow stagnant. A value less than 15.would mean not exploiting the eigenfaces fully while more than 15 would increase processing uselessly. Also try to ensure that in all the images of a person, the faces captured vary in expression. Basically the more varied the training data, the better result expectancy is there.

The value of k[number of eigenvectors to consider] should be chosen carefully. Ideally it should be 10 or 12. Intuitively it makes great sense as you have a dataset of 15 images of each person of which you select the top 10[which are most similar to the test image] for verification purposes. For explanation of how we zeroed in on the number 10, refer here.


Preprocessing:
To have any amount of satisfactory accuracy[i.e >70%], eigenfaces require a lot of pre-processing. The eyes and nose need to be at the same position in every image. Images should be straight[apply rotation for correction to obtain straight images]. It has been found that mouth does not contribute any significant features, therefore can be cropped out. Also apply histogram equalization to account for variable illumination across the image.
Research has shown that slightly blurred image perform better than perfect images. Therefore you may also consider applying a Gaussian filter[or any other] to blur the images slightly.

Further Reading:
A few of the famous blog posts on eigenfaces, worth reading are:

• bytefish [quality post useful when actually implementing eigenfaces]
• scholaropedia [For those comfortable with formal notations]
• article [For those who like simplified and informal theory]

Libraries:
Many libraries come with integrated Eigenfaces modules, for the ease of those who couldn't be less bothered about coding intricacies.

OpenCV in particular has a great implementation, whose details, both conceptual and coding vise can be found here. Although installing it is cumbersome, I definitely recommend downloading openCV, for prototyping EigenFaces as well as other algorithm to first check if they fit the solution requirements for the problem concerned.


To look into other face recognition algorithms, read my earlier post, here.

Software Defined Networking

One things many articles on SDN have in common is, the fact that they are littered with technical terms It is often simpler to glance through these terms, to ease the understanding of the concepts elucidated to in further text.

control plane: It is a logical plane where the execution decisions are taken at a higher level, like taking routing decisions. i.e. it is the brain of the network

data plane: It is the logical plane where actual execution is done at the lower lever, like forwarding packets based on forwarding table. i.e. where the actual function is carried out, is implemented.

mininet: It is a simulator for SDN networks. It is an upgrade over NetSim where we could simulate simple networks via GUI help. In mininet, we have openFlow and SDN support. Simulation environment is set up by writing code and not via GUI.

POX: It is a python framework for configuring a controller. In it every network entity, i.e. 'web server, router, switch' is an component. We create components to introduce entities in our network to be simulated.

OpenFlow: it is a very popular protocol used to communicate between a controlling server and a OpenFlow enabled switch. Using API of OpenFlow, we communicate between server which runs control plane and the actual switches which implement data plane. It is also used to communicate between switches.

dpctl: it is a utility by which we can control the flow aspects for a single switch. It is used for debugging and experimenting with the flow table of the switch. It comes along with openFlow.

note- Incidentally, there is a quick start guide wherein in a virtual box, you import a ovsk format virtual disk which has pre-installed mininet with pox. For more information, look here


Historically, the Data Plane and Control Plane are usually implemented within a single physical device, whether it be a router/ switch or any other layer 3 device. This meant that all network devices literally came in a box, with all their functionality built on a single physical machine. If someone had to change/tweak some functionality, he had to manually configure the specific machine.
However, in the modern era, it would certainly be advantageous if we could implement a little something called separation of concerns. This is achieved by physically separating the Data and Control planes.
This leads to a situation where the control plane controls several devices via a controller, and each device just implements the data plane.

This thinking is exactly what gave rise to the concept of Software Defined Networking, a move to design networks which are dynamic, flexible, more secure and can be controlled centrally. Notionally although this is a fairly new term, in essence its principal have already been applied via various previous protocols.
Even now many people are not sure exactly what SDN entails , including yours truly, but it understanding its functionality separately and combining the pieces bottom up would surely give us a decent idea.

a introductory link, which illucidate the manner in which SDN are used, as well as its underlying benifits is this.


However using a single controller is unfeasible with large number of hosts. Hence we come up with multiple controllers, each connected to separate set of hosts, but behaving as one big logical controller.

Face Feature Exctraction

Eigenfaces - Eigenfaces or PCA approach is nothing more than the mathematical eigenvectors of the face, applied on the dataset images(training). Each eigenface is a point in high dimensional image space converted into point in eigen subspace. They are  mutually orthogonal vectors. A blog post dedicated to Eigenfaces can be found here. suffer from- luminance and pose variations.


Gabor Wavelets - They are a family of sinosudol waves which work very similar to how our visual cortex perceives images. It works on the principal of kernel convolution, where the kernels are the Gabor Filters[ differing in lambda,theta,phase,etc. ]
strength- They are tailor made to handle cases of partial occlusion and are also pose invariant.
However Gabor Wavelets have a better model, log-Gabor, which is quite the new thing in feature extraction methods available nowadays.

Local Binary Patterns - This technique involves playing with histograms. It is the next big thing after Gabor. They preserve spatial information and locality. Each pixel is threshold ed with its nearest pixels[no. depends on radius of neighbourhood considered]. A bit vector is obtained, which is labelled and stored in a histogram. All the histograms of windows are then concatened to form a feature vector.


Harr Classifiers - They are cascade classifier used for face detection. They are general purpose classifiers which can to trained to detect faces, or even eyes, ears and noses separately.

Artificial Bee Colony

It is another technique taken from nature, albeit not as simple as the others. This one is modeled around the behavior observed in bees while gathering food/honey from flower patches.

For the algorithm to work efficiently, it relies on a balance between exploration and exploitation.
exploration : expanding the search space to look for new food sources.
exploitation : eating the resources gathered till now.

There are two kinds of bees :
   scouts - they explore the area, going in random directions locally in reach of new flower patches.
   foragers - the bees which exploit the food sources.

When a scout finds a new food patch, it dances to attract new bees to that patch. The other unemployed bees see the dance of the scout bees and decide the flower patch they want to visit.

Taking a look at the algorithm extracted from this pattern:

Scout discovers a point whose value according to objective function is pretty high.It defines it as an abstract flower patch, symbolically centered around the point.
forager bees wander locally in the area defined abstractly as a flower patch.If they find a point in the search area whose value according to objective function is higher that the point discovered by the scout initailly, this forager bee becomes a new scout.

If no forager bee finds such a point , then the flower patch is deemed exhausted.

Algorithm tricks 1

TWO POINTER ALGORITHM

used to find elements of a array which sum up to some desired value.

Suppose you have 2 arrays A and B and you need to find if there exists some i and j in A  and B respectively such that A[i] + B[j] = val, where val is some value given to you.

We make use of 2 pointers p1 and p2. Firstly, sort the 2 arrays using a suitable sort algorithm. This takes O(n log n) time each.

Initially p1 points at index 0 of array A and pointer p2 points at index n-1 of array B. Now we run the following inside a while loop

1.calculate  A[p1]+B[p2]

2.If this value is greater than val then we do p2--.

3.If this value is smaller than val then we do p1++.

4.Else if this value is equal to val then  p1 and p2 point to the elements of the two arrays whose sum is equal to val and we can break the loop.

5.Exit condition of the loop is specified as when either p1 reaches end of array A or p2 reaches start of array B. If either of the above happens then we have exhausted our search space.

note that we have put the following restriction on p1 and p2. p1 can only move down an array , thus we can only increment it. p2 can only move up an array, i.e we can only decrement its value.

The above technique can be applied to the spoj problem - love story

Firefly Algorithm FA

Firefly Algorithm belongs to a broader set of nature inspired algorithms, namely evolutionary algorithms. In this case,  the behavior of fireflies is our source of inspiration. This particular algorithm is credited to Xin she yang, who has also worked with various other evolutionary algorithms.

FA is a meta-heuristic algorithm, and although it doesn't give us the optimal solution, it does give a solution which is close enough approximation to the optimal solution.

It is suitable for those situations where the information is unkown or is only partially known. Even though it is still a relatively new algorithm, it is already showing to be a favorable choice to handle NP hard problems

The basic principle on which this algorithm runs is that all fireflies glow, and that the glow of a firefly is a measure of its attractiveness. Thus a firefly which perceives a more brightly glowing firefly nearby will be attracted towards it.

To get started on the algorithm, we first need to go through some terminology

1 A Population set X, where each member is characterized by its position.
2 An Objective Function f(x) to measure the glow at position x_{i .}

The concepts involved are :

 1. Attractiveness
 Let us take a firefly at location i and examine how it perceives a firefly at location j. Now the  attractiveness(brightness of light) emitted by firefly i at its own location is  obtained by the value of objective  function at i, that is I_i=f(i).
 Also the firefly j also emits light, whose value at location j is given by I_j=f(j). Now its perceived brightness at  location i is somewhat dampened by the absorbing nature of the medium in which the light travels (gamma).  The exact formula is ,
    Io* e^(-gamma*d2)    [ note - a faster variant would be to use the formuls  Io/(1 +gamma*d²) ]
 where,
                I_o = I_j
                d  = Euclidean distance between i and j
 Now if this perceived brightness is more than I_i   that means that for i, j appears more attractive and hence it should move towards it.


2. Movement
   When we decide that firefly j is brighter than firefly i, then we move firefly i. The formula for calculating the new position of firefly i is given by
                        insert formula
 where
   the first term is the initial position
   the second term is the direct move towards the brighter firefly j
   the third move is the random step in any direction.


The pseudo code of basic  FA is :

   pop=random_populate(n); //  initialize a random population X  of size n and store in pop
   f(x);                                     // define a objective function f (x)
                                   
   while(t<max_iterations)    //loop counter to keep an upper limit on number of iterations
   for i = 1....n
        for j = 1...n                         // double loop for each pair of fireflies
           if ( effect of light source at location j i.e f (pop.j) at location i  >  f (pop.i)   )  //  if firefly j is                       brighter than firefly i
              move(pop.i);                      //  move toward firefly j
       
         end for j;
    end for i;
    t++;
    //rank the fireflies according to the objective function and find the current best
    end while;

keeping value of gamma as 0 means that the medium does not absorb any light, and that intensity due to firefly x at location i is same as that observed at j. for any i and j.Similarly keeping value of gamma as a very large number means that the medium is very dense. In that case the FA reduces to a random search in the search space.

keep value of alpha as a small fraction of  the scale of dimension values we are dealing with(for a particular dimension), ideally 0.1 of the scale of the dimension.This helps in controlling the randomness a little while also not totally neglecting its contribution to the movement of the fireflies.


In practice it has been found out that firefly algorithm is generally superior to Genetic Algorithms(GA) or Particle Swarm Optimization algorithm(PSO).In fact, FA can find the global optima as well as all the local optima simultaneously in a very effective manner.Hence it is a multi-modal optimization algorithm.

It is possible to improve the solution quality by reducing the randomness gradually(in the movement step). We could vary the randomization parameter(alpha) so that it decreases gradually as the optima are approaching(as the number of iterations increases).

 It is still a young algorithm, and more and more areas of its application are still coming up.For example, it can be used to tune parameters of a Neural Network, SVM and so forth. It is developing to be an exciting field of research.