Paper Review of Approximate Image-Based Tree-Modeling using Particle Flows

The paper "Apprximate Image-Based Tree-Modeling using Particle Flows" by Boris Neubert, Thomas Franken, and Oliver Deussen from the University of Konstanz proposes an algorithm for synthesizing 3D tree models taking information from a few digital photographs. The authors believe this algorithm is an improvement over other algorithms for at least two reasons.  First, their algorithm requires fewer photographs with looser alignment.  Second, their algorithm produces results much quicker than previous algorithms, i.e. in a matter of seconds instead of hours.

The algorithm follows several steps to produce a realist 3D tree model based on photographs.  The algorithm is as follows:

In order to continue, the algorithm needs an approximation of the density of the tree based on the photographs.  The opacity values from the alpha matting are used as the input to an optimization function.  The output of the process is a coarse voxel grid with an approximation of the tree density for each voxel.  These densities will determine the likelihood of a tree particle starting in each voxel.

A directional field is then generated.  This field is used to determine how tree particles accelerate based on their position.  The field at each point is a combination of the tangent at the nearest point on the tree branch and the direction to the nearest tree branch.  This combination will produce a tree skeleton with branches which both follow the tree-branch sketch produced previously and head towards the main tree trunk.  The weights for the tangent and normal is is determined by calculating the distance from each point to the nearest point on the tree-branch skeleton.  The authors point out that the function used to weight these two values changes the appearance of the tree.

Tree particles are simulated to produce a tree skeleton.  Particles are generated based on the tree density grid. Particles are simulated based on their mass and acceleration.  The force applied to each particle at each time step is a combination of the directional field and the positions of any other particles which are close.  When two particles are within a certain distance they are combined into one particle with larger mass.  The paths the particles take define a tree skeleton.

To make the tree skeleton appear like a tree, the algorithm follows several more steps.  First, the skeleton is given width so that branches which are closer to the base are wider and those further away are thinner.  Second, leaves are added using previously established algorithms.  Lastly, the tree is textured with the appearance of bark.

The results of the algorithm are convincing and the low generation time is very impressive.  However, since the algorithm only tries to approximate the tree skeleton, an application which requires a highly-accurate skeleton structure may not find this algorithm accurate enough.

In my own attempt to reproduce parts of this algorithm, several issues became apparent.   

First, each branch has two tangents vectors which point in opposite directions.  When implementing the directional field, I could not always determine which tangent to use.  Clearly we want the tangent which will lead a tree particle to the trunk, but without additional information, the algorithm does not know which tangent to use.

Second, the algorithm was very sensitive to changes in the weighting of the tangent and normals in the directional field step.  If they were weighted incorrectly, tree particles frequently would get stuck because the normal and tangent vectors would cancel each other out.  Also, sometimes a tree particle would move away from the main trunk as it followed the normal vectors which pulled it away from the ground.  

In terms of future work, the authors point out that the best results come when users draw the branch outline manually.  A solid algorithm for doing this automatically would certainly assist the algorithm. In addition, it seems that there might be a use for an algorithm which can reproduce a tree with just one photograph instead of several.  Also, it would seem useful if the algorithm could align the photographs in 3D space without the help of the user.

"Approximate Image-Based Tree-Modeling using Particle Flows" is an excellent paper of producing 3D tree models from only a few photographs in a very small amount of time.  Aside from a few issues I had in terms of the weighting function, the algorithm seems effective and useful if an approximate tree is good enough.

The full paper in PDF format can be found here: http://graphics.uni-konstanz.de/~neubert/2007_SIG/2007AIBTM.pdf 

The authors' website focusing on this paper (including a video overview) can be found here: http://graphics.uni-konstanz.de/~neubert/2007_SIG/index.htm