# Blur Kernel Estimation by Structure Sparse Prior
## 3 Method
### Structure Sparse Prior  
A classic method for the blind deconvolution problem of Equation (1) is to solve the following objective function:  
\[\{\hat{x},\hat{k}\}=\underset{x,k}{argmin}\;||y-k*x||_{2}^{2}+\eta\rho(x)+ \gamma g(k), \tag{5}\]  
where \(\rho(x),g(k)\) is the regularization term on \(x,k\), respectively, typically an \(l_{2}\) norm penalty. With the sparsity prior as regularization, we can derive the following formulation:  
\[\{\hat{x},\hat{k},\hat{\alpha}\}=\underset{x,k,\alpha}{argmin}\;\left\{ \begin{array}{l}||y-k*x||_{2}^{2}+\eta||x-D\alpha||_{2}^{2}\\ +\gamma g(k)+\beta\phi(\alpha),\end{array}\right\} \tag{6}\]  
where \(\phi(\alpha)\) is the regularization term on \(\alpha\), typically an \(l_{1}\) norm penalty, and \(\eta\), \(\gamma\), and \(\beta\) are the weight coefficients of different terms, respectively.  
Considering the sparsity regularization and _Locality-constrained Linear Coding_ (LLC) constraint, the proposed method exploits the structure relationships among pixels. LLC is a new coding scheme that considers the correlation between codes and ensures similar descriptors have similar codes, keeping the inherent nature of the image [25]. LLC uses the following criteria:  
\[\underset{\alpha}{min}\sum_{i=1}^{N}||x_{i}-D\alpha_{i}||^{2}+\lambda||d_{i} \odot\alpha_{i}||^{2}, \tag{7}\]  
\[s.t.1^{T}\alpha_{i}=1,\forall i\]  
where \(D=[D_{1},D_{2},\ldots,D_{n}]\) and \(\odot\) denotes the element-wise multiplication. \(d_{i}=exp(dist(x_{i},D)/\sigma)\) and \(dist(x_{i},D_{j})\) refers to the Euclidean distance between \(x_{i}\) and \(D_{j}\),  
By introducing the sparsity regularization and the locality constraint, the objective function can be obtained as follows:  
\[\underset{x,k,\alpha}{min}\;||y-k*x||_{2}^{2}+\eta||x-D\alpha||_{2}^{2}+ \lambda_{1}||k||_{1}+\lambda_{2}||d\odot\alpha||_{2}^{2}, \tag{8}\]  
Figure 4: Sparse representation.  
where \(d=[d_{1},d_{2},\ldots,d_{n}]\), \(D=[D_{1},D_{2},\ldots,D_{n}]\), and \(\odot\) denotes the element-wise multiplication. \(d_{i}=exp(dist(x_{i},D)/\sigma)\), \(dist(x_{i},D)=[dist(x_{i},D_{1}),dist(x_{i},D_{2}),\ldots,dist(x_{i},D_{n})]^{T}\), and \(dist(x_{i},D_{j})\) refers to the Euclidean distance between \(x_{i}\) and \(D_{j}\).  
We explain each term of the proposed objective function in Equation (8) in detail as follows.  
* The first term in the objective function is a conventional constraint, which measures the likelihood between the recovered image and the blurred image.
* The second term means the recovered image is sparse representation.
* The third term represents the \(l_{1}\)-norm regularization on \(k\) to enforce sparsity.
* The last term, \(||d\odot\alpha||_{2}^{2}\), is the locality constraint, which ensures each descriptor is represented by multiple bases and regularizes the \(x\) and \(\alpha\) at the same time.  
The main purpose of the objective function in Equation (8) is to estimate the blur kernel. After the blur kernel is estimated, the final image can be recovered by a non-blind deconvolution algorithm (see next section for details). The proposed method combines LLC in the sparse regularization framework to keep the structure relationships among neighbor pixels in the blurred image during the blind deconvolution process. By taking the inherent attribute of the sharp image into consideration, the proposed method can get a more accurate kernel estimation.