A non-rigid registration algorithm for application to whole-body emission images of the same patient is presented. Rigid registration is generally insufficient to properly register whole-body images, a certain amount of deformation needs to be applied to obtain a good correspondence. This deformation should not change the size or shape of lesions, bones and the general anatomy. In our approach, non-rigid registration is accomplished by a discrete numerical approach based on the maximisation of mutual information, and regularised by a weighted least squares deformation constraint. Maximisation of mutual information I is accomplished by a preconditioned iterative gradient ascend algorithm using an analytically exact expression for the gradient of I with respect to individual pixel displacements. Anatomy is taken in account by parameterising the constraint according to a simple thresholding segmentation so as to allow large deformations in air, small in soft tissue and no deformation in bone or lesion tissue. A pyramidal multi-resolution approach is used to speed up the registration process. The performance of the method was evaluated by registering deformed phantom images, initial tests on 2D whole-body clinical images also show promising results.