A triple-spark guiding strategy to enhance the loser-out tournament-based fireworks algorithm

1.   Introduction

Image blur, such as motion blur, is a common disturbance in real-world photography applications. Therefore, image deblurring is of great importance for further practical vision tasks. Motion blur can be modeled as the covolution of the sharp image and blur kernel, which is typically unknown in real-world scenarios. The image degradation can be modeled as:

where $B$, $L$, and $K$ denote the motion-blurred image, the sharp image, and the blur kernel (point spread function), respectively, and $n$ represents the additive white Gaussian noise with a mean of 0 and a standard deviation of $\sigma$, which is introduced during the image degradation process. The symbol $\otimes$ denotes the convolution operator.

Blind deblurring aims to reconstruct both the blur kernel $K$ and the sharp latent image $L$ from a blurred input image $B$. However, this process is ill-posed because different combinations of $L$ and $K$ can produce identical outputs of $B$. To address this problem, it is essential to incorporate prior knowledge to avoid the local optimal solution.

Researchers have extensively explored the optimization of blur kernels modeled with prior knowledge of images in recent years^[1,2,3]. Li et al. ^[4] utilized a deep network to formulate the image prior as a binary classifier. Levin et al. ^[5] employed hyper-Laplacian priors to model the latent image and derived a simple approximation method to optimize the maximum a posteriori (MAP). In the pursuit of developing an efficient blind deblurring method, various prior terms tailored to enhance image clarity have been integrated within the MAP framework^[6,7,8]. Krishnan et al. ^[9] utilized an L1/L2 regularization scheme to sparsely represent the gradient image, whose main feature is to adapt the L1 norm regularization by using the L2 norm of the image gradient as the weight in the iterative process. However, this approach is not conducive to recovering image details in the early stages of the optimization process. Meanwhile, Xu et al. ^[10] proposed an unnatural L0 norm sparse representation to eliminate detrimental small-amplitude structures, providing a unified framework for both uniform and non-uniform motion deblurring. Liu et al. ^[11] explored that the surface maps of intermediate latent images containing detrimental structures typically have a large surface area, and they introduced an additional surface-perception a prior based on the use of the L0 norm to enforce sparsity on the image gradient, thereby preserving sharp edges and removing unfavorable microstructures from the intermediate latent images.

These methods still fail when dealing with images containing more saturated pixels and large blur kernels. Therefore, recent works concentrate on the image reconstruction with outliers for non-blind deblurring^[12] and blind deblurring tasks^[13,14,15]. Chen et al. ^[16] proposed to remove the outliers by adopting a confidence map and further shrunk the outliers by multiplying with its inverse value^[17]. Zhang et al. ^[18] proposed an intermediate image correction method for saturated pixels to improve the quality of saturated image restoration by screening the intermediate image using Bayesian a posteriori estimation and excluding pixel points that adversely affect the blur kernel estimation. Much progress has been made in blurred image estimation for natural images and in image reconstruction techniques, but there are still several major problems with the current blind deblurring algorithms. First, most current motion blur estimation methods are based on images with a linear blurring process^[19,20,21]. In practice, blurred images are often accompanied by large noise and outlier points, such as saturated pixel points, and linear blur models cannot effectively describe saturated pixel points, leading to their poor performance in processing blurred images with outlier pixels. In particular, blurred images taken in low-light environments will contain large noise and outlier points. Therefore, how to effectively cope with the interference caused by saturated pixels has great practical value.

Recently, deep learning methods based on Bayes theory have also developed^[22,23,24]. Kingma et al. ^[22] proposed the auto-encoding variational Bayesian algorithm, where the encoder maps the input into a distribution within the latent space, and the decoder maps the sample points from the latent space to the input space. Zhang et al. ^[20] and Ren et al. ^[23] constructed blind deblurring networks based on the MAP estimation. However, these deep learning-based methods can easily fail when the data distribution is different from the training data. For this reason, the proposed method focuses on the conventional iterative blind deblurring method.

This work investigates the blind deblurring optimization model for saturated pixels established under the MAP framework. By solving the intermediate image and blur kernel by alternating iterations, the blur kernel will eventually converge to the blur kernel of the observed image. In order to overcome the highly ill-posed problem of blind deblurring, the image regularity and the blur kernel regularity are usually used to constrain the model. Although the dark channel prior (DCP) has achieved excellent results, when dealing with images with larger blur kernels or saturated pixels, the results are often unsatisfactory. Therefore, we utilize the pixel screening strategy ^[18] to further correct the intermediate images with large blur kernels or saturated pixels. By distinguishing whether a pixel conforms to the linear degradation assumption, the proposed method reduces the influence of unfavorable structure to obtain a more accurate blur kernel.

2.   Intermediate corrected blind deblurring model based on the DCP

2.1.   MAP framework

We use the MAP probability estimation to construct a probabilistic modeling framework between a sharp image, a blur kernel, and a blurred image. Given the blurred image, the sharp image and the blur kernel are estimated by maximizing a posterior probability based on the assumption that the sharp image $L$ and the blur kernel $K$ are independent of each other. According to the conditional probability formula, we obtain

Taking the negative logarithms on both sides of the above equation, we derive a new form that is equivalent to the original probability density function:

Assume that $n$ is an additive white Gaussian noise with a mean of 0 and a variance of $\sigma$, and the variable $B$ follows a normal distribution, provided that $L$ and $K$ are known. The solution of $L$ and $K$ is transformed into the following minimization problem:

The first term on the right-hand side is the data fitting term, and the second and third terms are regularization terms, which involve a priori knowledge, including statistical and distribution properties about the sharp image and blur kernel. Blind deblurring is to estimate the blur kernel and then recover the sharp image from the blurred image.

2.2.   Blur kernel prior

The motion blur is usually caused by relative motion between the camera and the subject. This motion causes pixels shifting in a specific direction and distance, thus resulting in image degradation. Assume all values in the blur kernel are greater than or equal to 0, and the sum is 1, that is,

where $\Omega$ is the whole image space.

Since blur kernels are sparse, we constrain the possible blur kernels as follows:

where $\|\cdot\|_p$ denotes the $p$ norm operator. As the $\mathrm{L}_2$ norm constraint focuses more on the smoothness of the blur kernel, this leads to more stable results for kernel estimation. Therefore, we use the $\mathrm{L}_2$ norm to constrain the blur kernel in this paper.

2.3.   Blind deblurring method based on the DCP

The dark channel is a natural metric for distinguishing sharp images from blurry images^[25]. He et al. ^[26] first proposed dark channels for image haze removal. The dark channel of image $L$ can be defined as the minimum value of an image patch as follows:

where $N(i, j)$ is the image patch centered at pixel ${(i, j)}$. Experiments show that the dark channels of sharp images are more sparse. The possible reason is that the image blur is a weighted sum of pixel values within the local neighborhood, thereby increasing the dark channel pixels. Therefore, we use the $L_0$ norm of the dark channel as the image regularization.

The deblurring model based on the DCP is to solve the following problem:

The first term of this formula is a fidelity item that constrains the output of the convolution of the recovered image with the blur kernel to be as similar as possible to the observed result. The $\|\nabla L\|_0$ term is used to preserve large image gradients and $\|\mathrm{D}(L)\|_0$ is used to measure the dark channel sparsity. The blind deconvolution method commonly optimizes $L$ and $K$ alternately during the iterative process. The main purpose of this alternating iterative optimization is to progressively refine the motion blur kernel $K$ and the latent image $L$.

In this work, the following two subproblems are solved by the alternating iteration method:

Specifically, for the $k$-th iterative process, $L$ can be solved using the fast Fourier transform. When $L$ is given, kernel estimation in Eq (2.7) is a least-squares problem. The gradient-based kernel estimation methods have shown superiority ^[11], and the kernel estimation model as follows:

2.4.   Pixel screening strategy for intermediate image correction

Normally, blind image deblurring follows the basic linear blurring assumption Eq (1.1). However, methods based on this assumption do not yield satisfactory results in recovering images with a high number of saturated pixels. When outliers are present, intermediate potential images, estimated using methods with traditional data fidelity items, contain significant artifacts. Even a small number of outliers severely degrade the quality of the estimated blur kernel because these outliers often do not fit the linear model.

An effective way to identify and discard outliers during the iterative process is assigning different weights to the pixels while updating the latent image and the blur kernel. Those pixels categorized as outliers are assigned a weight equal to zero to ensure that they do not affect the subsequent iterations^[18]. We introduce variable $Z$ to determine whether the pixel $(i, j)$ complies with the linearity assumption^[12], and the intermediate correction operator is defined as

According to the Bayes formula, we have

In this work, we assume that the noise $n$ obeys a Gaussian distribution with a mean of 0 and a variance $\sigma^2$. When

the degradation assumption holds, and we obtain

where

When

pixel $(i, j)$ is considered an outlier. The posterior distribution is approximated by a uniform distribution as follows:

where $b$ and $a$ correspond to the maximum and minimum values of the input image, respectively.

Given the intermediate image $L^{k+1}$ and kernel $K^k$, we use $p_0$ to represent the percentage of image pixels that deviate from the linear model. The probability of a pixel conforming to Eq (1.1) can be defined as

and we generally assume that about 0–10 $\%$ of the pixels are deviated. The probability of satisfying the linearity assumption Eq (1.1) for a given intermediate blur kernel and intermediate image is defined as

According to the full probability formula, we obtain

Thus, with the above definitions, the pixel screening operator $P$ is calculated as follows:

During the iterative process, after obtaining the estimated intermediate image, we alternate the estimation of the blurring kernel. Based on the intermediate correction operator, we screen and correct the pixels of intermediate images. For those pixels with a high probability of deviation, which means they have greater disadvantageous impact for blur kernel estimation, they are appropriately corrected. With the corrected intermediate image, we solve the following model to estimate the blur kernel:

where $\circ$ is the matrix dot product operator.

2.5.   Algorithm

As shown in Figure 1, this work is carried out in the framework of multi-scale deblurring, where kernel estimation is carried out from a coarse to a fine scheme with an image pyramid. With the color input image, we first transform it to a grayscale image. We use the image to create a pyramid and resize the blur kernel with a down-sampling operation, thus a set of multi-resolution images is obtained. Starting from the smallest level, the structure of the whole image is restored and we recover the rough blur kernel using the correction operator. As the image and kernel resolution improve, the finer details are gradually restored.

Figure 1.  Kernel estimation from coarse to fine under the multi-scale deblurring framework.

DownLoad: Full-Size Img PowerPoint

3.   Experimental results

In order to verify the effectiveness of this method, we conduct numerical experiments on both synthetic and real-world image datasets to compare the processing effects of the dark channel blind deblurring method before and after the correction improvement. We set the parameters

and $p$ is an adjustable parameter in the range of 0.02 to 0.1. Figure 2 compares the results on the Levin dataset^[5] by adjusting $p$ from 0.02 to 0.16. The results show that the deblurring performance relies on the choice of $p$. The more outliers present, the higher the value of $p$, which will provide better results.

Figure 2.  Peak signal-to-noise ratio (PSNR) comparison on the Levin dataset by adjusting $p$ from 0.02 to 0.16.

DownLoad: Full-Size Img PowerPoint

The experimental hardware configuration is an Intel Core i5-10300 CPU, NVIDlA GeForce GTX 1650 GPU, 16.0 GB RAM, the software configuration operating system is Windows 10 (64-bit). We use the PSNR and structural similarity (SSIM) as our evaluation metrics.

3.1.   Synthetic dataset

We use the Levin dataset ^[5] and Köhler dataset ^[27] to evaluate our method. The Levin dataset is a standard benchmark dataset that consists of 32 blurred images synthesized from 4 original images and 8 different convolution kernels, with each image size of $255\times255$. The Köhler dataset is a standard benchmark dataset that consists of 48 blurred images synthesized from 4 original images and 12 different convolutional kernels, with each image size of $800\times800$. We compare our method with DCP^[25], PMP^[28], LMG^[21], and Sat^[17] to demonstrate the effectiveness of our method.

In Figure 3, the left figure shows the PSNR comparison between the proposed method and state-of-the-art methods, where our method significantly improves the PSNR metric. The right figure shows the error ratio comparison with and without intermediate correction. It can be seen that the proposed method has the smallest error ratio. As shown in Figure 3 and Table 1, experimental results on the Levin dataset demonstrate that the deblurring algorithm proposed in this paper achieves significant performance improvements across a wide range of blur types and degrees. The improved method recovery results obtain higher PSNR and SSIM values, and its ability to reach a 100% success rate faster proves its effectiveness in removing blur of different types and degrees.

Figure 3.  PSNR and error ratio comparison on the Levin dataset.

DownLoad: Full-Size Img PowerPoint

Table 1.  Comparison of averaged SSIM on the Levin dataset.

	LMG[21]	PMP[28]	Sat[17]	DCP[25]	Ours
SSIM	0.4662	0.4753	0.2438	0.4559	0.5268

---

 | Show Table

DownLoad: CSV

Figure 4 shows that our method recovers the image and kernel with less artifacts and higher quality.

Figure 4.  Visual comparison on the Levin dataset. The proposed method obtains the best restoration performance.

DownLoad: Full-Size Img PowerPoint

As shown in Figure 5 and Table 2, experimental results on the Köhler dataset show that our proposed deblurring method achieves significant performance improvement, and the recovery results obtain higher PSNR and SSIM values, demonstrating its effectiveness for image quality improvement. Figure 6 shows that the deblurred image of the proposed method obtains most restoration performance with the least ringing artifacts. The restored kernel of the proposed method is more clean and the image has the best visual quality.

Figure 5.  PSNR comparison on the Köhler dataset.

DownLoad: Full-Size Img PowerPoint

Table 2.  Comparison of averaged SSIM on the Köhler dataset.

	LMG[21]	PMP[28]	Sat[17]	DCP[25]	Ours
SSIM	0.6148	0.6147	0.5351	0.6104	0.6256

---

 | Show Table

DownLoad: CSV

Figure 6.  Visual comparison on the Köhler dataset.

DownLoad: Full-Size Img PowerPoint

3.2.   Real dataset

As shown in Figure 7, we compare the dark channels of intermediate results with and without the intermediate correction. Without the correction strategy, our method reduces to the DCP-based method^[25]. The intermediate results show that our method restores more sharp edges and clear blurry kernels. The final recovered image contains more details that demonstrate that our method improves the deblurring quality for saturated images.

Figure 7.  Visual comparison with and without intermediate correction.

DownLoad: Full-Size Img PowerPoint

Estimating motion kernels from blurred images with saturated pixel regions is challenging in image processing. As shown in Figure 8, we present three blurry images with saturated pixels to demonstrate the performance of our method. The first column shows blurry images, and the second and the third column are the results of the DCP^[25] and ours, respectively. The results show that with the intermediate correction, it not only improves the quality of the recovered images, but also restores more clear blurry trajectories.

Figure 8.  Visual comparison on the real-world dataset.

DownLoad: Full-Size Img PowerPoint

4.   Conclusions

In this work, we introduce a blind deblurring method based on the DCP with an intermediate image correction strategy. In order to remove the disadvantageous effect of outliers, such as saturated pixels, we correct the intermediate image during the deblurring process. By assigning different weights to intermediate images, we improve the kernel estimation performance and thus enhance the final image restoration quality. Experimental results show that our method can significantly improve the accuracy and robustness of blur estimation when dealing with blurred images containing noise and outlier pixels.

Author contributions

Min Xiao: writing—original draft; Jinkang Zhang: writing—original draft; Zijin Zhu: writing—review and editing; Meina Zhang: methodology, supervision. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by the Science Foundation of China University of Petroleum, Beijing (No. 2462023YJRC008), Foundation of National Key Laboratory of Computational Physics (No. 6142A05QN23005), Postdoctoral Fellowship Program of CPSF (Nos. GZC20231997 and 2024M752451), National Natural Science Foundation of China (No. 62372467).

Conflict of interest

The authors have no conflicts to disclose.