This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Search for Publication

Year(s) from:  to 
Keywords (separated by spaces):

Tabu Search: An Efficient Solution to Discrete Optimization

M. Stricker and A. Leonardis
161, 1995


In this paper we show that tabu search, which has so far been used predominantly in operations research, is perfectly suited to solve discrete optimization problems in AI and, in particular, in computer vision. Tabu search is a general heuristic strategy for global optimization. We describe the principles and the implementation of tabu search. To demonstrate the superiority of tabu search over classical methods, we apply it to two computer vision problems: figure-ground segmentation and simultaneous fitting of curves. A comparison of the results with those obtained by mean field annealing and Hopfield-Tank neural networks reveals that tabu search outperforms these methods, both in the ability of getting almost optimal solutions and in the computational efficiency. An additional advantage of tabu search over the classical methods is that it produces elite solutions and that constraints can be enforced without changing the search strategy or the objective function.

Download in postscript format
  author = {M. Stricker and A. Leonardis},
  title = {Tabu Search: An Efficient Solution to Discrete Optimization},
  year = {1995},
  month = {March},
  number = {161},
  keywords = {optimization, segmentation, fitting}