›› 2016, Vol. 31 ›› Issue (3): 450-462.doi: 10.1007/s11390-016-1639-1

Special Issue: Computer Graphics and Multimedia

• Special Section of CVM 2016 • Previous Articles     Next Articles

Improving Shape from Shading with Interactive Tabu Search

Jing Wu, Paul L. Rosin, Xianfang Sun, and Ralph R. Martin   

  1. School of Computer Science and Informatics, Cardiff University, Cardiff, CF24 3AA, U.K.
  • Received:2015-11-27 Revised:2016-03-09 Online:2016-05-05 Published:2016-05-05
  • Supported by:

    This work was supported by the Engineering and Physical Sciences Research Council (EPSRC) of UK.

Optimisation based shape from shading (SFS) is sensitive to initialization: errors in initialization are a significant cause of poor overall shape reconstruction. In this paper, we present a method to help overcome this problem by means of user interaction. There are two key elements in our method. Firstly, we extend SFS to consider a set of initializations, rather than to use a single one. Secondly, we efficiently explore this initialization space using a heuristic search method, tabu search, guided by user evaluation of the reconstruction quality. Reconstruction results on both synthetic and real images demonstrate the effectiveness of our method in providing more desirable shape reconstructions.

[1] Horn B K P, Brooks M J. The variational approach to shape from shading. Computer Vision, Graphics, and Image Processing, 1986, 33(2): 174-208.

[2] Ramachandran V S. Perceiving shape from shading. Scientific American, 1988, 259(2): 76-83.

[3] Belhumeur P N, Kriegman D J, Yuille A L. The basrelief ambiguity. International Journal of Computer Vision, 2001, 35: 1040-1046.

[4] Worthington P L, Hancock E R. New constraints on data-closeness and needle map consistency for shape-fromshading. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21(12): 1250-1267.

[5] Huang R, Smith W A P. Structure-preserving regularisation constraints for shape-from-shading. In Proc. the 13th International Conference on Computer Analysis of Images and Patterns, Sept. 2009, pp.865-872.

[6] Durou J D, Falconeb M, Sagonab M. Numerical methods for shape-from-shading: A new survey with benchmarks. Computer Vision and Image Understanding, 2008, 109(1): 22-43.

[7] Zhang R, Tsai P S, Cryer J E, Shah M. Shape from shading: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1999, 21(8): 690-706.

[8] Zeng G, Matsushita Y, Quan L, Shum H Y. Interactive shape from shading. In Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition, June 2005, pp.343-350.

[9] Meyer A, Briceno H M, Bouakaz S. User-guided shape from shading to reconstruct fine details from a single photograph. In Proc. the 8th Asian Conference on Computer Vision, Nov. 2007, pp.738-747.

[10] Wu T P, Sun J, Tang C K, Shum H Y. Interactive normal reconstruction from a single image. ACM Transactions on Graphics, 2008, 27(5): Article No. 119.

[11] Governi L, Furferi R, Puggelli L, Volpe Y. Improving surface reconstruction in shape from shading using easy-to-set boundary conditions. International Journal of Computational Vision and Robotics, 2013, 3(3): 225-247.

[12] Saito H, Usami K. Shape from shading using genetic algorithm. In Proc. IECON, Nov. 1993, pp.1620-1625.

[13] Crouzil A, Descombes X, Durou J D. A multiresolution approach for shape from shading coupling deterministic and stochastic optimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(11): 1416-1421.

[14] Sinclair M. Comparison of the performance of modern heuristics for combinatorial optimization on real data. Computers & Operations Research, 1993, 20(7): 687-695.

[15] Huang R, SmithWA P. Shape-from-shading under complex natural illumination. In Proc. the 18th IEEE International Conference on Image Processing, Sept. 2011, pp.13-16.

[16] Meyer F. Topographic distance and watershed lines. Signal Processing, 1994, 38(1): 113-125.

[17] Frankot R T, Chellappa R. A method for enforcing integrability in shape from shading algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10(4): 439-451.

[18] Basri R, Jacobs D W. Lambertian reflectance and linear subspaces. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(2): 218-233.

[19] Tomasi C, Manduchi R. Bilateral filtering for gray and color images. In Proc. IEEE International Conference on Computer Vision, Jan. 1998, pp.839-846.

[20] Xu L, Lu C, Xu Y, Jia J. Image smoothing via L0 gradient minimization. ACM Transactions on Graphics, 2011, 30(6): Article No. 174.

[21] Glover F. Tabu search — Part 1. ORSA Journal on Computing, 1989, 1(3): 190-206.

[22] Glover F. Tabu search — Part 2. ORSA Journal on Computing, 1990, 2(1): 4-32.

[23] Daniel P, Durou J D. From deterministic to stochastic methods for shape from shading. In Proc. the 4th Asian Conference on Computer Vision, Jan. 2000, pp.187-192.

[24] Falcone M, Sagona M. An algorithm for the global solution of the shape-from-shading model. In Proc. the 9th International Conference on Image Analysis and Processing, Sept. 1997, pp.596-603.

[25] Tsai P S, Shah M. Shape from shading using linear approximation. Image and Vision Computing, 1994, 12(8): 487-498.
No related articles found!
Full text



[1] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[2] Chen Shihua;. On the Structure of (Weak) Inverses of an (Weakly) Invertible Finite Automaton[J]. , 1986, 1(3): 92 -100 .
[3] Gao Qingshi; Zhang Xiang; Yang Shufan; Chen Shuqing;. Vector Computer 757[J]. , 1986, 1(3): 1 -14 .
[4] Chen Zhaoxiong; Gao Qingshi;. A Substitution Based Model for the Implementation of PROLOG——The Design and Implementation of LPROLOG[J]. , 1986, 1(4): 17 -26 .
[5] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[6] Min Yinghua; Han Zhide;. A Built-in Test Pattern Generator[J]. , 1986, 1(4): 62 -74 .
[7] Tang Tonggao; Zhao Zhaokeng;. Stack Method in Program Semantics[J]. , 1987, 2(1): 51 -63 .
[8] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[9] Zhang Bo; Zhang Ling;. Statistical Heuristic Search[J]. , 1987, 2(1): 1 -11 .
[10] Zhu Hong;. Some Mathematical Properties of the Functional Programming Language FP[J]. , 1987, 2(3): 202 -216 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved