Efficient hybrid search for visual reconstruction problems

Visual reconstruction refers to extracting stable descriptions from visual data ( [1] ; A. Blake and A. Zisserman, Visual Reconstruction, MIT Press, Cambridge, MA, 1987). Visual reconstruction problems are commonly formulated in an optimization framework and normally require the optimization of nonconvex functions especially when discontinuity preserving image/shape recovery is the goal. Example problems include, image restoration, surface reconstruction, shape from shading etc. Most existing deterministic methods fail to reach the global optimum and lack the generality to incorporate reasonably complex interactions between boolean valued line process variables used for representing the presence (absence) of discontinuities. Stochastic methods for solving such problems e.g. the simulated annealing algorithm or variants thereof do achieve a global optimum but are plagued by slow convergence rates. In this paper, we present a new hybrid search algorithm as an efficient solution for achieving the global optimum of the nonconvex function derived from a Markov random field formulation which allows for incorporation of complex interactions between the line process variables to better constraint the line processes. In the hybrid search, for the stochastic part, we develop an informed genetic algorithm (GA) while employing an incomplete Cholesky preconditioned conjugate gradient algorithm ( [23] ; S.H. Lai and B.C. Vemuri, Robust and efficient algorithms for optical flow computation, in: Proceedings of the International Symposium on Computer Vision, Coral Gables, FL, 1995, pp. 455–460) for the deterministic part. Our informed GA consists of a reproduction operator and an informed mutation operator. The informed mutation operator exploits specific domain knowledge in the search and is accomplished by the Gibbs sampler. Our hybrid search algorithm is highly parallelizable and leads to a globally optimal solution. The performance of our algorithm is demonstrated via experimental results on the sparse data surface reconstruction and the image restoration problem.