Scale-ivariant feature transform (SIFT) has defects in computational complexity of its key point descriptor computing stage and in the high dimensionality of the key point feature vectors. To speed up the computation, a SIFT based on compressive sensing algorithm was proposed. By the sparse feature representation methods of compressive sensing theory, the feature vector of SIFT was extracted and the high-dimensional gradient derivative was decreased to low-dimensional sparse feature vector. Accordingly, Euclidean distance was introduced to compute the similarity and dissimilarity between feature vectors used for image registration and Best-Bin-First (BBF) data structure was used to avoid exhaustion. The experimental results show that the proposed algorithm has better performance than the standard SIFT algorithm while registering the affine transformation medical images. Comparing with the current modified SIFT algorithms, the real-time performance of the proposed algorithm is improved obviously.