CSE557 Final Project

Composite Head

by Colin Zheng, Nilesh Dalvi

Introduction to the Problem

Take a photograph and try to render it using smaller images of distinct objects . Renaissance painter Giuseppe Arcimboldo was famous for such compositions. The “Composite Head” is that faces and human features are painted, not in flesh, but with rendered clumps of assorted vegetables, fruits and other materials. 

This is a non-trivial NPR problem......


Detailed steps of our approach is as follows:

  • Automatic Face Segmentation
    We modified an existing implementation of mean-shift algorithm to perform image segmentation to get a new image with fewer colors[1]. 
  • Polygon Extraction 
    We performed connected component analysis on the segmented image and detected the contour of each component. The outline of each components were extracted as polygon.   
  • Smoothing and Down-sampling
    We smoothed out the outline of each component by averaging it out with neighbors. Down-sampled the above curves by approximating it with polygons of smaller order (using flatness estimates). 
  • Direction Curve Conversion
    Direction Curve has the nice property of translation and rotation invariance, so it's suitable to work here. We converted the polygons into direction curves[2].
  • Sprite Database Setting up
    For the sprites database (consisting of fruits and vegetables), we assumed the image of each sprites has background with constant color. So we extracted sprite out of its background, extracted polygon out of it. Did smoothing and down-sampling as above. We converted all the sprites into the format of direction curves. They would be compared to the face components.
  • Curve Matching
    For each face components, we did curve matching with all the direction curves in the database, in order to find the largest partial match. First matching vertex and rotation angle of the sprite curve were recorded for bitmap composition.
  • Bitmap Composition
    With the starting vertex and the rotation angle, it was easy to place the sprite bitmap onto the face component. More efforts were added to ensure it was filled inside the component, and that part had not been filled before.

Fig 1. System Architecture Overview


  • Limitation of Segmentation Algorithm
    It's always hard to have a good segmentation algorithm that reflects semantics. We gradually realize that "Composite Head" might need a better segmentation which is not based on color cues. So sometimes, human interaction is necessary in order to convey some semantics. 
  • Curve Matching
    The direction curve matching has great advantages, such as solving rotation and translation easily. But our algorithm still has flaws like: if the face component is too large, the outline will be perfectly matched with sprites while it will leave the center untouched. This "hole effect" can be solved with hole detection and filling.
  • Bitmap Composition
    We allow sprites overlapping while filling face components, but the order to fill the components has great effects on the final visual result. We paid little attention on that, but in the later version, we'll use the depth in Z-Buffer to control the composite order. Ideas like depth is proportional to size of the partial match will be applied for better effect.


Original Image Segmented Image
Extracted Polygons Smoothed & Down-sampled Polygons
Composite Hand
Guess who is he/she???


[1]. Dorin Comaniciu, Peter Meer, Robust Analysis of Feature Spaces: Color Image Segmentation, CVPR97, USA.
[2]. S. Umeyama, "Least-squares estimation of transformation parameters between two point patterns," IEEE Trans. Pattern Anal. Machine Intelligence, PAMI-13, 4, pp. 376-380, 1991