Non-rigid image registration is an important preprocessing step in many medical image applications, but it is also a very computation intensive task. In this paper, a fast adaptive bases (FAB) non-rigid image registration with local optimization method is proposed to speed up the free-form deformation with radial basis functions. Our proposed algorithm applies matched area identification in the initialization process and adaptive support size for basis function in the misregistration region identification process. Moreover, higher grid point density for local optimization is used in the identified misregistration regions. With our proposed algorithm, the registration speed is found significantly increased while maintaining the registration accuracy. The overall running time is reduced by preserving the advantage of computing local deformation on disjoint regions instead of trying to solve the problem globally. Performance evaluation of our proposed method was conducted using simulated and clinical brain dataset with standard measures based on root mean square error (RMSE) and normalized mutual information (NMI) similarity measure. Experimental results showed that notable improvement on speed was achieved as compared to the conventional regular and adaptive grid approaches.