Four dimensional computed tomography (4D CT) image sets contain both tissue motion as well as respiratory induced changes in the CT image characteristics resulting from ventilation. Deformable image registration (DIR) provides a link between the component phase images for extraction of the motion and physiological information. Most current algorithms, such as optical flow, assume incompressibility in their formulation, which is a potential source of error for lung tissue. In this study, we derive two new DIR methods. First, the combined compressible local global (CCLG) formulation accounts for: (1) the compressible nature of the lungs, (2) noise in the images, and (3) the high computational workload required. In order to account for lung compressibility, voxel displacement is modeled by the conservation of mass equation, rather than by the constant voxel intensity assumption employed by optical flow. The effect of noise is reduced by applying a local-global approach to the conservation of mass setting. Finally, the resulting large scale linear systems are solved using a parallelizable, preconditioned conjugate gradient algorithm. The local compressible interpolation (LCI) method is a less computationally intensive variant of the full CCLG method for use in cases where restrictions on computational resources prevent the application of the full CCLG method. The average spatial accuracy of the methods applied to three thoracic CT image sets was determined using large samples of expert-determined landmarks, and found to be 1.59 mm and 1.86 mm for the CCLG and LCI methods, respectively.