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.