Deep-sky image registration is the most important step in deep-sky image applications. Due to the low efficiency of these existing algorithms based on the triangle similarity, and the hardness of applying algorithms based on star description to deep-sky image registration, an improved efficient triangle similarity algorithm is proposed and applied in the deep-sky image registration. Firstly, the proposed method analyzes the single pixel intensity and star size histograms of detected stars, and divides the stars into stable and normal stars. Then, the triangles are constructed for stable star or normal star with its nearest two stable stars respectively. Finally, by introducing the degree of similarity, the improved voting matrix is used in triangle matching. During this step, an adaptive threshold calculation method is also proposed to measure the triangle similarity. Experimental results show that the proposed method greatly enhances the star matching efficiency, reduces the resources requirement and guarantees the high level of matching precision.