Facebook Interview Question Software Engineer / Developers
0of 0 voteshow would you detect mouth in a picture
Country: -
An automatic face morphing algorithm is proposed. The algorithm automatically extracts feature points on the face, and based on these feature points images are partitioned and face morphing is performed. The algorithm has been used to generate morphing between images of faces of different people as well as between different images of the face of an individual. The results of both inter- and intra-personal morphing are subjectively satisfactory.
ref-->/
ccrma.stanford.edu/~jacobliu/368Report/index.html
This can be solved using graphs.
1) each pixel in the image would represent a vertex in a graph with an edge between 2 neighboring pixels. The weight of the edge should be proportional to the darkness of the pixel.
2) identify different connected components (eye, node, mouth) in the image using spanning tree algorithm.
3) the last of the puzzle is to identify which of the connected component is the mouth. each connected component (eye, nose, mouth, etc) would be represented as a vertex in a graph and the edge weight is proportional to their distance from each other. using shortest path, you can identify 2 pair of eyes and the component that is farthest from the eyes is the mouth.
1) "The weight of the edge should be proportional to the darkness of the pixel." you said the VERTEX represents the pixel. So which pixels' darkness did you mean when mentioning edge weight?
2) "an edge between 2 neighboring pixels" based on this you will have no separate islands in the graph; but one single component. So why the spanning tree algorithm?
Your solution doesn't make any sense to me.
@future googler: it is not mentioned that the picture will have a full face. It can be only lips in the picture. I think different approach is needed. One basic property of lips is two points having three different lines touching them. I think if we consider a graph with nodes as pixels. Then each pair would have three lines where lines starting from one point would end in the other. Probably lines have different properties which can be figured out. I this can be one point to be considered. Also, the pair of points could be eyes too. These are just my thoughts.
Note that I don't have a solution/algorithm/design right now.
Is it a human mouth? an open mouth or a closed mouth? Is a mouth guaranteed to be present or not? If so how many mouths can exist in a single picture? Is the picture always in a particular orientation. These are some questions that could be asked as clarification.
- @future googler 2 September 17, 2011