So I recently came across this coding question on hackerrank and stackoverflow called Even Tree. The question goes as follows - 

You are given a tree (a simple connected graph with no cycles). You have to remove asmany edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest should contain an even number of vertices.

To accomplish this, you will remove some edges from the tree. Find out the number of removed edges.

So the question requires us to traverse a tree and cutoff edges such that each sub-tree/forest created has even number of nodes. You can also treat this question as a directional graph question wherein you start from a node and remove any edges to come up with subgraphs that contain even number of nodes.

To make it easy to visualize, lets consider a tree -

                                    Fig 1 - Sample tree with all it edges

                            Fig 2 - Tree with edges to be removed marked in blue

Algorithm :-

• Populate the children below each node:- 

This step relies on the way the input is given for the problem(upper nodes being nearer to the root and lower nodes being the leaves. If the input is given out of order, I recommend using a level order traversal and do a bottom-up approach for this step to calculate the children below. The function populateChildren adds the number below each to a map and as we traverse bottom to top, we keep adding the number of children of each node in a node's adjacency list to that node's number of children.

• Traverse each edge and decide if it needs to be removed based on the number of children below each of the vertices connected through that edge:- 

This step iterates through all edges and checks if an edge needs to be removed. There are two cases when an edge can be removed 

- The first case is when the difference between the number of children below the parent node and the child node in the edge is odd AND the number of children below the child is odd. (The difference means that child node of the edge along with its children aggregate to an even number and the parent can get into a different forest of nodes. For example, consider the edge joining nodes 2 and 5. As 5 has odd number of children and difference between the children of parent and node is also odd indicating that the parent can find a different group with its children or its parent or both.)

- The second case is the case when children below both parent and child of an edge have an odd number, it is safe to remove that edge to get forests of even nodes.(For example, consider the edge joining nodes 1 and 3. For node 3, the number of children is three and for node 1, the number of children is nine. So node 1 will be able to connect to the remaining 5 nodes in such a way so as to make a forest of even nodes)

A sample input for this solution is as below :-

 30 29

 2 1

 3 2

 4 3

 5 2

 6 4

 7 4

 8 1

 9 5

 10 4

 11 4

 12 8

 13 2

 14 2

 15 8

 16 10

 17 1

 18 17

 19 18

 20 4

 21 15

 22 20

 23 2

 24 12

 25 21

 26 17

 27 5

 28 27

 29 4

 30 25

In the input, the first line indicates the number of vertices and edges respectively and the following lines indicate the edges connecting the nodes.

Pasting the solution code in Java below :-

1:  import java.util.ArrayList;  
2:  import java.util.HashMap;  
3:  import java.util.Map;  
4:  import java.util.Scanner;  
5:    
6:  class EvenTree {  
7:      private int numVertices = 0;  
8:      private int edges = 0;  
9:      private Map<Integer, Integer> edgeListMap = new HashMap<Integer, Integer>();  
10:      private Map<Integer, ArrayList<Integer>> adjListMap = new HashMap<Integer, ArrayList<Integer>>();  
11:      private Map<Integer, Integer> numChildren = new HashMap<Integer, Integer>();  
12:    
13:      //Method to decide which edges to remove  
14:      private void eliminateEdges() {  
15:          int edgesRemoved = 0;  
16:          for (Map.Entry<Integer, Integer> entry : edgeListMap.entrySet()) {  
17:              if (((this.numChildren.get(entry.getValue()) - this.numChildren  
18:                      .get(entry.getKey())) % 2 != 0 && this.numChildren  
19:                      .get(entry.getKey()) % 2 != 0)  
20:                      || (this.numChildren.get(entry.getValue()) % 2 != 0 && this.numChildren  
21:                              .get(entry.getKey()) % 2 != 0)) {  
22:                  // For printing the edges removed  
23:                  //System.out.println(entry.getKey() + ":" + entry.getValue());  
24:                  ++edgesRemoved;  
25:              }  
26:          }  
27:          System.out.println(edgesRemoved);  
28:      }  
29:    
30:      //Method to populate the number of children below each node  
31:      private void populateChildren() {  
32:          for (int i = numVertices; i > 0; i--) {  
33:              int numChildren = 0;  
34:              ArrayList<Integer> adjList = this.adjListMap.get(new Integer(i));  
35:              if (adjList != null) {  
36:                  for (Integer node : adjList) {  
37:                      if (this.numChildren.containsKey(node)) {  
38:                          numChildren = numChildren + 1  
39:                                  + this.numChildren.get(node);  
40:                      } else  
41:                          ++numChildren;  
42:                  }  
43:              }  
44:              this.numChildren.put(i, numChildren);  
45:          }  
46:      }  
47:    
48:      public static void main(String[] args) {  
49:    
50:          Scanner ob = new Scanner(System.in);  
51:          EvenTree eventree = new EvenTree();  
52:          eventree.numVertices = ob.nextInt();  
53:          if (eventree.numVertices % 2 != 0) {  
54:              System.out.println("Number of vertices are not even. Exiting...");  
55:              return;  
56:          }  
57:          eventree.edges = ob.nextInt();  
58:          int vertex1, vertex2;  
59:          for (int i = 0; i < eventree.edges; i++) {  
60:              vertex1 = ob.nextInt();  
61:              vertex2 = ob.nextInt();  
62:              eventree.edgeListMap.put(vertex1, vertex2);  
63:              if (eventree.adjListMap.containsKey(vertex2)) {  
64:                  ArrayList<Integer> adjListMap = eventree.adjListMap  
65:                          .get(vertex2);  
66:                  adjListMap.add(vertex1);  
67:              } else {  
68:                  ArrayList<Integer> adjList = new ArrayList<Integer>();  
69:                  adjList.add(vertex1);  
70:                  eventree.adjListMap.put(vertex2, adjList);  
71:              }  
72:          }  
73:      //Populate the children map  
74:          eventree.populateChildren();  
75:      //Decide the edges to be removed  
76:          eventree.eliminateEdges();  
77:      }  
78:  }  

The time complexity of this solution is O(V + E).

Imagine digging through a lot of photos everytime you decide to send a photo from your smart phone to a whatsapp contact or to your facebook/twitter account.

There has to be an easier way to filter out photos containing the required content(somebody's face) in the camera roll.
This blog post is about a naive approach to solving this issue of search for your photos.

Algorithm -

1. Take any photo (one input and one to compare with the input)

2. Find the face in the image such that the face has specific features used(no hair but eyes, nose and mouth present) and resize the face to a 100 x 100 image

Note that this step uses LBP cascade classifier to detect faces in the image. Find related information here -

OpenCV Cascade Classifier tutorial

static Mat cropFaceFromImg(InputArray _frame)

{

    Mat testFrame = _frame.getMat();

    std::vector<Rect> faces;

    Mat frame_gray;

    std::vector<Mat> croppedFaces;

    Mat resizedFace;//dst image

    

    cvtColor( testFrame, frame_gray, CV_BGR2GRAY );

    //equalizeHist( frame_gray, frame_gray );

    

    //-- Detect faces

    face_cascade.detectMultiScale( frame_gray, faces, 1.1, 2, 0|CV_HAAR_SCALE_IMAGE, Size(1, 1) );

    

    for( size_t i = 0; i < faces.size(); i++ )

    {

        Mat faceImg;

        Rect rect = Rect( faces[i].x + (faces[i].width/6), faces[i].y , faces[i].width*2/3, faces[i].height ); // ROI rect in srcImg

        frame_gray(rect).copyTo(faceImg);

        Size size(100,100);//the dst image size,e.g.100x100

        

        resize(faceImg,resizedFace,size);//resize image

        croppedFaces.push_back(resizedFace);

        

    }

    //imshow("ResizedFace", resizedFace);

    //waitKey(0);

    return resizedFace;

}

3. Calculate histogram for the image.

The essence of this step is calculating a pixel with its neighboring 8 pixels and assigning a 8 bit binary value for that pixel H(I) based on whether the neighboring pixel is darker or lighter than the pixel at the center.
Related code to calculate histogram bins [From OpenCV src code]

//------------------------------------------------------------------------------

// cv::elbp

//------------------------------------------------------------------------------

template <typename _Tp> static

inline void elbp_(InputArray _src, OutputArray _dst, int radius, int neighbors) {

    //get matrices

    Mat src = _src.getMat();

    // allocate memory for result

    _dst.create(src.rows-2*radius, src.cols-2*radius, CV_32SC1);

    Mat dst = _dst.getMat();

    // zero

    dst.setTo(0);

    for(int n=0; n<neighbors; n++) {

        // sample points

        float x = static_cast<float>(radius * cos(2.0*CV_PI*n/static_cast<float>(neighbors)));

        float y = static_cast<float>(-radius * sin(2.0*CV_PI*n/static_cast<float>(neighbors)));

        // relative indices

        int fx = static_cast<int>(floor(x));

        int fy = static_cast<int>(floor(y));

        int cx = static_cast<int>(ceil(x));

        int cy = static_cast<int>(ceil(y));

        // fractional part

        float ty = y - fy;

        float tx = x - fx;

        // set interpolation weights

        float w1 = (1 - tx) * (1 - ty);

        float w2 =      tx  * (1 - ty);

        float w3 = (1 - tx) *      ty;

        float w4 =      tx  *      ty;

        // iterate through your data

        for(int i=radius; i < src.rows-radius;i++) {

            for(int j=radius;j < src.cols-radius;j++) {

                // calculate interpolated value

                float t = static_cast<float>(w1*src.at<_Tp>(i+fy,j+fx) + w2*src.at<_Tp>(i+fy,j+cx) + w3*src.at<_Tp>(i+cy,j+fx) + w4*src.at<_Tp>(i+cy,j+cx));

                // floating point precision, so check some machine-dependent epsilon

                dst.at<int>(i-radius,j-radius) += ((t > src.at<_Tp>(i,j)) || (std::abs(t-src.at<_Tp>(i,j)) < std::numeric_limits<float>::epsilon())) << n;

            }

        }

    }

}

4. Compare the histogram with the histogram of the input face image.(this is done similar to a type of Face Recognizer in OpenCV called Linear Binary Patterns Histogram)

For this step, OpenCV has four different types of Histogram compare methods.
I use the CV_COMP_CORREL method as it allows for a basic correlation done and its value does not change even if we reverse the compared photo with the input. The formula for the correlation of histogram bins is -


where
  

and N is the total number of historgram bins.
[From Histogram Comparison OpenCV tutorials]
The above formula gives a value of 1 if the images are same and its value is proportional to the similarity of the images.

5. If histogram correlation shows more than 0.6, the image can be considered belonging to the same person.

Pros :-
1. A single step classifier which can be made better as the search queries increase by combining data sets of similar face searches.
2. No face modeling done and hence relies on the simplicity of histogram creation and comparison.
3. Good for mobile platform analysis

Cons:-
1. A naive classifier of 0.6 threshold so chances to get false positives and false negatives are high.
2. No face modeling done so critical features of the face may be neglected due to the basic histogram approach.

Note:- This is still a naive way to filter faces but the algorithm can be made adaptive as with each iteration of searches, we can keep improve the accuracy by combining search results for the same person and filtering out the faces which do not fall into the intersection set.

The github repo(source code) for the above can be found here

Some things are worth looking again at

1. There is always a way. [Location :- Katra, India]

2. Old Spice. [Location :- Martha's Vineyard, MA]

3. And the sun rose. 

4. Yosemite Fire [Somewhere above it]

5. Serene Truckee and Tahoe[South Lake Tahoe, CA]

6. Erupting skies [North Lake Tahoe, CA]

7. Bridge across the bay [San Francisco, CA]

8. Footsteps in the sky. [Mount Diablo, CA]

9. Your Highness [East Yosemite, CA]

" For all of the places we could've been, this is where we chose to be"