In this paper, we propose two algorithms, namely the extrapolated proximal iterative hard thresholding (EPIHT) algorithm and the EPIHT algorithm with line-search, for solving the $\ell_0$-norm regularized wavelet frame balanced approach for image restoration. Under the theoretical framework of Kurdyka–Łojasiewicz property, we show that the sequences generated by the two algorithms converge to a local minimizer with linear convergence rate. Moreover, extensive numerical experiments on sparse signal reconstruction and wavelet frame based image restoration problems including CT reconstruction, image deblur, demonstrate the improvement of $\ell_0$-norm based regularization models over some prevailing ones, as well as the computational efficiency of the proposed algorithms.