Performance is a very important factor when it comes to tracking objects. To gain interactive or even real-time update rates it's necessary to soften the above stated assumptions in the most harmless way (see accuracy below). In the following you could read and work on possibly good ways to speed up the whole process.
Mathematical optimization of the function space
Using optimization algorithms like adaptive random search or Particle Filters are as far as known by the authors a very safe way to prevent the system form simulating all possible configurations without loosing accuracy.
Naturally the optimization will be harder if the degrees of freedom increases. But as it has been shown by Deutscher et. al. that it is possible to optimize high dimensional functions with so called annealed particle filtering. This seems to be very easy archivable when using images. Just take a lower resolution and you will get a smoothed out function. Nontheless it need to be discussed about possible errors and accuracy of such an aproach.
"Little changes" assumption
If we assume only little changes between two captured frames we could dramatically reduce the search space of possible real world configurations.
Using specialized hardware to generate hypothesis
Simulating possible captured datasets on specialized hardware is definitely a very good thing to do. Especially for images this easily done by using modern graphic cards.
- Deutscher, J. and Blake, A. and Reid, I., 'Articulated body motion capture by annealed particle filtering}, IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'00), Vol. 2, issn 1063-6919, year 2000, pages 126-133