Marine Radar Image Processing of Compressed Sensing Based on Arbitrary Block Statistical Histogram and Dynamic Dictionary

In compressed sensing (CS), the absolute value of the inner product of signal and atom (or dictionary) is used to select atom (or dictionary); the atoms (or dictionaries) with larger absolute values of inner product are selected to decompose and reconstruct signals. This characteristic usually makes it impossible to distinguish the edges of objects (or targets) in some complex cases, especially when the density of objects is very high. For example: let signal $x_{1} =[{\cdots 00110110\cdots }]^{T}$ , $x_{2} =[{\cdots 001110100\cdots }]^{T}$ ; $\psi _{1} $ , $\psi _{2} $ , $\psi _{3} $ and $\psi _{4} $ denote several sparse basis matrices (i.e., sparse dictionaries); $\psi _{1i} =[{\cdots 00000100\cdots }]^{T}$ , $\psi _{2j} =[{\cdots 00110000\cdots }]^{T}$ , $\psi _{3k} =[{\cdots 00111000\cdots }]^{T}$ , and $\psi _{4l} =[{\cdots 00111110\cdots }]^{T}$ are the sparse bases (i.e., atoms) from these sparse basis matrices (i.e., dictionaries), respectively. For signal $x_{1} $ , $\psi _{4l} $ (or $\psi _{4}$ ) is selected instead of $\psi _{2j} $ (or $\psi _{2}$ ); likewise, for $x_{2} $ , $\psi _{4l} $ (or $\psi _{4}$ ) will be selected instead of $\psi _{3j} $ (or $\psi _{3}$ ) and $\psi _{1i} $ (or $\psi _{1}$ ). This causes the edge of the object to be unrecognizable. Another example is in $l_{p} $ regularization, it is not necessarily the optimal case: the smaller the value of $\| {\Psi _{d}^{-1} x} \|_{0} $ , the better the sparse basis matrix (i.e., dictionary), or the larger the weighing parameter. At present, the inner product is used to process almost all signals in CS. Choosing the dictionary that matches the signal best rather than the dictionary with the maximum inner product value can reconstruct the signal more accurately. In order to overcome the above shortcoming, we propose a fully automatic radar image processing algorithm of CS based on arbitrary block statistical histogram and dynamic dictionary. We use arbitrary block statistical histogram to calculate the non-zero block numbers of different sizes, which can better choose the appropriate sparse base (or dictionary) for the signal. Furthermore, the better measurement vector y can be obtained, and the signal can be reconstructed more accurately than the state-of-the-art methods at the receiving end. To realize the proposed method, we construct objective functions and flow charts for noiseless and noisy signals, respectively. In our method, for noiseless signal, discarding the sub-images that do not contain objects can reduce running time; for noisy signal, according to the theory of wavelet, choosing the appropriate wavelet (i.e., wavelet basis) can usually suppress noise. Our proposed algorithm can overcome the above shortcoming of CS in using the absolute value of the inner product, reduce running time, suppressnoise, and improve the signal-to-noise ratio (SNR). The simulation results show that our method is superior to the state-of-the-art methods.

SECTION I. Introduction

In signal processing, the precondition of applying CS [1] is that the signal is sparse, or the signal can be transformed into sparse signal by some transformation. Because not all images are sparse in nature, when CS is used to process non-sparse signals, sparse transform is needed to transform the signals into sparse signals. The common sparse transforms of signal include discrete cosine transform (DCT), wavelet, curvelet, overcomplete dictionary decomposition, etc. Wavelet basis is the natural sparse basis of signal, and its effect is very good. Generally speaking, with the increase of wavelet decomposition levels in a certain range, the SNR of signal will be improved gradually. Signal decomposition and reconstruction methods are mainly classified into three categories: basis pursuit (BP) [2], [3], greedy method [4]–​[7] and other methods [8]–​[10].

A. Basis Pursuit

At present, much attention is given to underdetermined inverse problems in academic and industry communities because of their many potential applications, such as compressed imaging for radar [11], [12], and other methods [13]–​[17]. CS can reconstruct high-dimensional signal from under-determined equation $$\begin{equation*} y=\Phi x+n\tag{1}\end{equation*}$$ where $y\in C^{M\times 1}$ is the measurement vector; $\Phi \in C^{M\times N}$ , $M < < N$ is a given measurement matrix; x is the estimated signal and $n\in C^{N\times 1}$ represents the noise term. The reconstruction problem can be solved well theoretically using the so-called $l_{0}$ regularization described as $$\begin{equation*} \hat {x}_{l_{0}} =\mathop {\mathrm {argmin}}\limits _{x} \left \{{{\gamma \left \|{ {y-\Phi x} }\right \|_{2}^{2} +\lambda \left \|{ x }\right \|_{0}} }\right \},\tag{2}\end{equation*}$$ in which $\left \|{ x }\right \|_{0} = \vert$ supp($x)\vert$ denotes the $l_{0}$ -norm that counts the number of non-zero components. If the signal x is not sparse, a sparse transformation dictionary $\Psi \in R^{N\times N}_{}$ is needed to transform x into a sparse signal. The $l_{0}$ -norm regularized optimization problem in (2) is an NP problem [18]. As a relaxed method, the $l_{1}$ -norm regularization is the most popular alternative. However, the alternative of $l_{1}$ regularization can only obtain a suboptimal solution [19]. The $l_{p}$ (0 < p < 1) quasi-norm regularization [20], [21] is used which can take advantage of more sparse information, especially in the presence of strong noise interference. When $p\in (1/2, 1]$ , the $l_{p}$ regularization will yields a sparser solution. Hence $l_{1/2}$ regularization is often regarded as a typical case for discussion in $l_{p}$ -norm regularization. Recently the half thresholding algorithms are proposed to solve the non-convex $l_{1/2}$ regularization problem [22], [23]. A CS signal reconstruction using $l_{0}$ norm regularization least mean fourth algorithms is present in [24], which based on stochastic gradient to reduce complexity can effectively mitigate certain impulsive noise. A recovery method of block-structured sparse signal using block-sparse adaptive algorithms via dynamic grouping is proposed in [25], which classify the block signals s[i](n) into three sets; and three corresponding regularization parameters are given to recover the signal respectively. In [26], a multiple sub-wavelet-dictionaries-based adaptively-weighted iterative half thresholding algorithm is proposed (MUSAI-$L_{1/2}$ ); it further exploits the prior knowledge of the estimated signal for sparse recovery based on the strategy of multiple sub-wavelet-dictionaries. It use the fact that the values of $\left \|{ {\Psi _{d} x} }\right \|$ will vary across the dictionary $\Psi _{d}$ , where $\Psi _{d}$ , $d=1,2,3,\cdots$ , denote the wavelet dictionaries of different waveforms. E.g., $\Psi _{1}$ uses ‘db1’ wavelet bases, $\Psi _{2}$ uses ‘db2’, $\Psi _{3}$ uses ‘db3’, $\cdots$ . The optimization strategy¹ is described as $$\begin{equation*} \hat {x}_{d,l_{1/2}} =\mathop {\mathrm {argmin}}\limits _{x} \left \{{{\gamma \left \|{ {\Phi x-y} }\right \|_{2}^{2} +\sum \limits _{d=1}^{D} {\lambda _{d} \left \|{ {\Psi _{d} x} }\right \|_{1/2}^{1/2}}} }\right \},\tag{3}\end{equation*}$$ in which a suitable regularization parameter $\lambda _{d}$ is used to weight the proposed sub-wavelet-dictionary $l_{1/2}$ - regularization, where $$\begin{equation*} \lambda _{d}^{(t+1)} \leftarrow \frac {L_{d}}{\varepsilon +\left \|{ {\Psi _{d} x^{(t)}} }\right \|_{1/2}^{1/2}},\tag{4}\end{equation*}$$ t is the number of iterations for a given x.

A method of CS radar imaging with magnitude sparse representation is proposed in [27], which presents an improved framework to handle the magnitude and phase of the scene separately. In [28], compressed image sensing by jointly leveraging multi-scale heterogeneous priors for the internet of multimedia things is proposed, which proposes an image reconstruction algorithm by jointly leveraging multi-scale (local and global) heterogeneous (statistical and structural) priors of natural images, named jointly leveraging statistical and structural priors for CS image reconstruction (JLSSP-CS). In [29], a method of inexact gradient projection and fast data driven CS is proposed. A method of wavelet tree support detection for CS (magnetic resonance imaging) MRI reconstruction is proposed in [30], in which iterative weighting is applied to parent-child pairs in order to preserve fine details in the reconstructed outputs.

B. Greedy and Other Methods

On the other hand, block sparse signals are studied. The block sparsity signal means non-zero entries of x are distributed in the form of blocks in a signal vector (see Figure 1 in which three kinds of sparsity patterns are depicted: same size block sparsity, arbitrary block sparsity, and arbitrary sparsity).

FIGURE 1.

Diagram of different sparse vectors. Each colored square stands for one non-zero entry. (a) Same size block sparse signal. (b) Arbitrary block sparse signal. (c) Arbitrary sparse signal.

In this paper, we define that it is a special form of arbitrary block sparse signal that the size of non-zero block is 1. In practice, most of the man-made signals conform to the block sparsity pattern, such as cognitive radio [31], [32], neuromagnetic imaging [33], and wideband communication [34].

Therefore, many algorithms [35], [36], [37]–​[40] focus on the block-sparse reconstruction (BSR). Nevertheless, almost all of them have a very strict requirement that the target signal should have the same size blocks. Block sparse signal reconstruction based on block sparse adaptive filtering algorithms are proposed in [41], [42], and good results are achieved under different sparsity. In [43], arbitrary block-sparse signal reconstruction based on incomplete single measurement vector is proposed, which has good performance; they use a fixed dictionary in signal processing.An algorithm of on-chip neural data compression based on CS with sparse sensing matrices is proposed in [44], which aims at measurement matrices to reduce area and total power consumption.

A method of fast super-resolution ultrasound imaging with CS reconstruction method and single plane wave transmission is proposed in [45]. In [46], a method of binary matrices for CS is proposed, it proposes a new performance parameter the minimal column degree d which performs better than the known coherence parameter, namely the maximum correlation between normalized columns; it has good recovery performance. It is also for sensing matrix A in formula $y=Ax$ .

A method of adaptive matrix design for boosting CS is proposed in [47]. The aim of this paper is to make a step further in the field of encoder-side optimization. In formula $y=Ax=A\psi \theta$ , it aims at designing sensing matrix A.

C. Problem and Our Contributions

The absolute value of the inner product of CS is used to select atoms (or dictionaries) or set weighting parameters of regularization terms in almost all the above methods. Atoms (or dictionaries) with larger absolute values are used to decompose and reconstruct signals. When the density of small objects is very high, this makes it difficult to recognize the edges of small targets. For example: let signal $x_{1} =\left [{ {00110110\cdots } }\right]^{T}\,\,x_{2} =\left [{ {00111010\cdots } }\right]^{T}$ ; $\psi _{1}$ , $\psi _{2}$ , $\psi _{3}$ and $\psi _{4}$ are several sparse basis matrices (i.e., sparse dictionaries); $\psi _{1i} =\left [{ {00000100\cdots } }\right]^{T}$ , $\psi _{2j} =\left [{ {00110000\cdots } }\right]^{T}$ , $\psi _{3k} =\left [{ {00111000\cdots } }\right]^{T}$ and $\psi _{4l} =\left [{ {00111110\cdots } }\right]^{T}$ are the sparse bases (i.e., atoms) of these sparse basis matrices (i.e., dictionaries) respectively. For signal $x_{1}$ , $\psi _{4l}$ (or $\psi _{4}$ ) is selected instead of $\psi _{2j}$ (or $\psi _{2}$ ); likewise, for $x_{2}$ , $\psi _{4l}$ (or $\psi _{4}$ ) is selected instead of $\psi _{3j}$ (or $\psi _{3}$ ) and $\psi _{1i}$ (or $\psi _{1}$ ). This causes the edge of the object to be unrecognizable. Another example is in $l_{p}$ regularization, it is not necessarily the optimal case: the smaller the value $\left \|{ {\Psi _{d}^{-1} x} }\right \|_{1/2}^{1/2}$ , the better the sparse basis matrix (i.e., dictionary), or the larger the weighing parameter. Choosing the dictionary that matches the signal best rather than the dictionary with the maximum value can reconstruct the signal more accurately.

In marine radar images, people are more concerned about the size and edge of the object (or target) (e.g., boat, ship, island, etc.) than the magnitude of pixel in object (or target). And maritime radar image usually has binarization characteristics.

In view of the above situations, combing the concepts of arbitrary block sparse signal and multiple sub-wavelet-dictionaries, we propose a fully automatic radar image processing algorithm of CS based on arbitrary block statistical histogram and dynamic dictionary. The main contributions of our work include:

1. We propose a fully automatic radar image processing algorithm of CS based on arbitrary block statistical histogram and dynamic dictionary, which can overcome the above shortcoming of CS in using the absolute value of the inner product.

2. We construct objective functions for noiseless and noisy signals respectively to determine which method will be used to each sub-image.

3. Through the simulation experiments of various radar images under different SNR, we get the optimal binarization threshold which can eliminate the noise interference in establishing arbitrary block statistical histogram.

4. We establish the arbitrary block statistical histogram eliminated noise interference, which can quickly and efficiently recognize the local characteristics of sub-images and choose the appropriate sparse base (or dictionary) for signals.

5. To our knowledge, we first introduce the statistical histogram of arbitrary non-zero blocks into maritime radar images of CS.

6. Through simulation, we prove that Haar wavelet is usually more effective than other wavelets in maritime radar image processing.

The algorithm we proposed can reduce running time, suppress noise and improve the SNR of images than state of the art methods. Simulation results are shown to demonstrate the validity of the method we proposed.

The remainder of the paper is organized as follows. In the next section, several existence works and a reconstruction method. In Section III, mathematical theory of our proposed method is presented. The method we proposed is elaborated in Section IV. Section V is simulation results. Finally, we conclude in Section VI.

SECTION II. Several Existence Works and a Reconstruction Method

A. Several Existence Works

1) MUSAI-$L_{1/2}$ : Multiple Sub-Waveletdictionaries-Based Adaptively-Weighted Iterative Half Thresholding Algorithm for Compressive Imaging

The Multiple MUSAI-$L_{1/2}$ [27] utilizes a suitable regularization parameter $\lambda _{d}$ to weight the proposed sub-wavelet-dictionary $L_{1/2}$ -regularizer; the optimization strategy is described as $$\begin{align*} \mathord {\stackrel {{\lower 3pt\hbox {$\scriptscriptstyle \frown $}}} {x}} _{d,l_{1/2} } =\arg \min \limits _{x} \left \{{ {\gamma \left \|{ {\Phi x-y} }\right \|} }\right._{2}^{2} +\sum \nolimits _{d=1}^{D} {\lambda _{d} } \left.{ {\left \|{ {\psi _{d} x} }\right \|_{1/2}^{1/2} } }\right \}, \\\tag{5}\end{align*}$$ in which $\psi _{d}, d=1,2,\cdots$ , denote sub-wavelet-dictionaries, $\lambda _{d}, d=1,2,\cdots$ , denote the regularization parameters for each $L_{1/2}$ -regularizer of $\left \|{ {\psi _{d} x} }\right \|_{1/2}^{1/2}$ . And the sub-wavelet-dictionaries based $\lambda _{1/2}$ -regularizer RMUSAI(x) can be described as $$\begin{align*} R_{MUSAI} (x)=&\sum \limits _{d=1}^{D} {\lambda _{d}} \!\left \|{ {\psi _{d} x} \!}\right \|_{1/2}^{1/2} \\=&\lambda _{1} \!\left \|{ {\psi _{1} x} \!}\right \|_{1/2}^{1/2} \!+\!\,\lambda _{2} \!\left \|{ {\psi _{2} x} \!}\right \|_{1/2}^{1/2} \!+\!\,\cdots \!+\!\,\lambda _{D} \!\left \|{ {\psi _{D} x} \!}\right \|_{1/2}^{1/2}\qquad \!\!\!\!\!\!\!\!\!\!\!\! \\\tag{6}\end{align*}$$ The MUSAI-$L_{1/2}$ algorithm for solving is $$\begin{equation*} x^{t+1}=\arg \min \gamma \left \|{ {\Phi x-y} }\right \|_{2}^{2} +\sum \nolimits _{d=1}^{D} {\lambda _{d} \left \|{ {\psi _{d} x} }\right \|} _{1/2}^{1/2}.\tag{7}\end{equation*}$$ The detailed steps of the algorithm are as follows:

• Input: the sub-wavelet dictionaries $\left \{{{\psi _{d}} }\right \}_{d=1}^{D}$ , the measurement y, the measurement matrix $\Phi$ ; $L_{d}$ ; $\gamma =1$ ; $\varepsilon >0$ ;

• Initialization: $\text{t}=0$ ; $x^{1}=0$ , $\varepsilon =0.01$ ; $\tau =\frac {1-\varepsilon }{\left \|{ \Phi }\right \|^{2}}$ ; $\lambda _{d}^{1} =1$ ;

• for $t=1,2,3,\cdots$ ;

• $x^{t+1}\leftarrow \arg \min \gamma \left \|{ {\Phi x-y} }\right \|_{2}^{2} +\sum \limits _{d=1}^{D} {\lambda _{d} \left \|{ {\psi _{d} x} }\right \|_{1/2}^{1/2}}$ ;

• compute $\lambda _{d}^{\left ({{t+1} }\right)} \leftarrow \frac {L_{d}}{\varepsilon +\left \|{ {\psi _{d} x^{\left ({t }\right)}} }\right \|_{1/2}^{1/2}}$ ;

• end;

• Output $x^{t}$ ;

The adaptive weighting parameter $\lambda _{d,1/2}$ plays a key role in the optimization progress, which not only weight the contribution of each regularization term, but also control the tradeoff between the fidelity and prior knowledge term. The method usually can obtain the optimal solution when the measured value y is known.

However, according to the characteristics of maritime radar images, local feature may be single. For example, there are only a lot of small targets with very high density in a sub-image. The smaller the value of $\left \|{ {\Psi _{d}^{-1} x} }\right \|_{0}$ , the larger the weighing parameter; it makes the boundary of the object unrecognizable; of course, it may reduce the SNR. Our method first uses statistical histogram of arbitrary non-zero block to judge the local characteristics of the marine image, so as to better select sparse basis dictionary and get an optimal measurement vector y in signal sampling. As long as the signal satisfies the reconstruction condition of phase diagram [48], it usually can be better reconstructed at the receiving end. It also can reduce running time.

2) Arbitrary Block-Sparse Signal Reconstruction Based on Incomplete Single Measurement Vector (BMP)

BMP [44] estimates the sparsity of the signal, and provides the relationship among the step size, sparsity and sizes of the non-zero blocks. And it utilizes the RIP instead of block-RIP to analyze the behavior of BMP. The BMP gives the conditions to ensure the recovery of the signal and can improve the SNR.

But this method uses the absolute value of the inner product to select atoms, it chooses the larger absolute values of inner product to decompose and reconstruct signals. If there are only a lot of small targets with very high density, it also makes the boundary of the object unrecognizable. And multiple sub-dictionaries are not used; this shows that the method has room to further improve the SNR.

Our method does not need to estimate the sparsity. In signal sampling, we use statistical histogram to judge the local characteristics of the signal, so as to select a suitable sparse basis (or dictionary) and get a better measurement value y, which can better reconstruct the signal at the receiving end.

3) Adaptive Matrix Design for Boosting Compressed Sensing

A method of adaptive matrix design for boosting CS is proposed in [47]. The aim of this paper is to make a step further in the field of encoder-side optimization. In formula $y=Ax=A\psi \theta$ , it aims at designing sensing matrix A and proposes two novel methods. The first approach (Nearly Orthogonal CS) is based on a geometric constraint enforcing diversity between compressed measurements. NeO-CS relies on off-line procedures to tune sensing matrix A to signal X. Then the second approach is described: the alignment of the rows of A with directions of x is achieved by looking at the m rows that, among M candidates (with M > m), have the largest energy. They refer to this technique as Maximum-Energy CS (Max-CS). The main advantage of the Maximum-Energy approach is the adaptability of the sensing procedure to each signal instance without any requirement on the knowledge of the statistic of input signal class. In other words, Max-CS is a run-time self-adapting CS encoder.

These methods have obvious advantages when the energy of the sensing end is limited. When we compare these methods, we regard them as a method, namely, Adaptive Matrix Design (AMD); and only compare with the better results of them.

4) Wavelet Tree Support Detection for Compressed Sensing MRI Reconstruction

A method of wavelet tree support detection for CS (magnetic resonance imaging) MRI reconstruction is proposed in [31]. In [31], A priori knowledge of the signal/image support based on its statistical and structural information in the transformed domain improves the quality of CS reconstruction. Hidden Markov tree models the wavelet domain support of magnetic resonance images obtained from under sampled k-space data very well. With the support information, parent-child pairs in the wavelet tree are detected accurately; then iterative weighting is applied to parent-child pairs in order to preserve fine details in the reconstructed outputs. And hence, iterative regularization problems for CS-based magnetic resonance imaging reconstruction are solved with high throughputs.

Because this method is very good and there are similarities between marine radar image and MRI image, so our proposed method compared with it.

B. A Reconstruction Method

In order to process the real-time image sequence, this paper uses Stagewise OMP [48] to reconstruct the signal.

Stagewise OMP doesn’t need to know sparsity k. In MATLAB program, the Stagewise OMP function is described as follows: [theta]=CS_StOMP (y, A, S, Th), where y is the measurement vector, A is the sensing matrix, S is the maximum number of StOMP iterations to perform, Th is the threshold parameter; The default value of S is 10; $Th=t_{s} \cdot \sigma _{s}$ ; $t_{s}$ takes values in the range $t_{s} \in [{2,3}]$ , and the default value is 2.5.

If the signal is not sparse, the reconstructed signal becomes worse. It can be transformed into sparse signal by wavelet transform, and thus satisfy the reconstruction condition of Stagewise OMP.

There are usually the following input and output variables:

Input:

1. The sensing matrix is $A=\varphi \phi, A\in R^{M\times N}$ .

2. y denotes the observation vector, where $y\in R^{M\times 1}$ .

3. The iteration number is S.

4. Ts is the threshold parameter.

Output:

1. The estimated coefficient of signal sparse representation.

2. The residual is $r_{s} =y-A_{s} \hat {\theta }_{s}, r_{s} \in R^{M\times 1}$ .

Let’s assume that: $r_{t}$ denotes the residual, t denotes the number of iteration, $\boldsymbol \varphi$ is the empty set. $J_{0}$ is the new index (serial number) set of ‘large’ coordinates obtained in each iteration. $\boldsymbol \Lambda _{t}$ is the union of all index sets $J_{0}$ after t iterations. $a_{j}$ denotes the j column of A. $A_{t}$ denotes the column set selected from A according to the index set $\boldsymbol \Lambda _{t}$ . $\theta _{t}$ is a column vector of $Lt\times 1$ dimension. Symbol $\cup$ represents union. $\langle, \rangle$ represents the inner product of the vector. And abs represents the modulus (absolute value). The steps of Stagewise OMP reconstruction algorithm are as follows:

Initialization: $r_{0} =y, \boldsymbol \Lambda _{0} =\boldsymbol \varphi, A_{0} =\boldsymbol \varphi, t=1$ .

1. Calculate $u=abs[A^{T}r_{t-1}]$ (i.e., calculate $\left \langle{ {r_{t-1}, a_{j}} }\right \rangle, 1\le j\le N$ ), select the values of u that are greater than the threshold Th. The corresponding column number j of A of these values consist the set $J_{0}$ (i.e. column number set).

2. Let $\boldsymbol \Lambda _{0} =\boldsymbol \Lambda _{t} \cup J_{0}, A_{t} =A_{t-1} \cup a_{j}$ , (for all $j\in J_{0}$ ); if $\Lambda _{t} =\Lambda _{t-1}$ (i.e., no new column is selected), stop iteration and enter step (7);

3. Find the least square solution of equation $y=A_{t} \theta _{t}$ : $\mathord {\stackrel {{ { \frown }}} {\theta }}_{t} =\mathop {\mathrm {argmin}}\limits _{\theta _{t}} \left \|{ {y-A_{t} \theta _{t}} }\right \|=\left ({{A_{t}^{T}A_{t}} }\right)^{-1}A_{t}^{T} y$

4. Update residual $r_{t} =y-A_{t} \mathord {\stackrel {{\lower 3pt\hbox {$\scriptscriptstyle \frown $}}} {\theta }}_{t} =y-A_{t} \left ({{A_{t}^{T} A_{t}} }\right)^{-1}A_{t}^{T} y$ ;

5. t = t +1, if $t\le S$ , return to step (2) and continue iteration. If T > S or residual $r_{t} =0$ , stop iteration and enter step (7);

6. Reconstruct all non-zero terms of $\mathord {\stackrel {{\lower 3pt\hbox {$\scriptscriptstyle \frown $}}} {\theta }}$ at $\Lambda _{t}$ , whose values are $\mathord {\stackrel {{\lower 3pt\hbox {$\scriptscriptstyle \frown $}}} {\theta }}_{t}$ obtained by the last iteration.

SECTION III. Mathematical Theory of Our Proposed Method

In CS, mathematical formula can be expressed as $$\begin{equation*} y=\Phi x+n,\tag{8}\end{equation*}$$ where $y\in C^{M\times 1}$ is the measurement vector; $\Phi \in C^{M\times N}$ , $M < < N_{,}$ is a given measurement matrix; and $n\in C^{N\times 1}$ is the noise term. If the signal is not sparse, a sparse transformation matrix is needed to transform the input signal x into a sparse signal. Assuming that $\psi$ is a sparse basis matrix, the sparse transformation is shown in formula (9). $$\begin{equation*} x=\psi \theta\tag{9}\end{equation*}$$ At present, the inner product is used to choose sparse basis matrices (i.e., dictionaries) for almost all signals; atoms (or dictionaries) with larger absolute value of inner product will be selected to decompose and reconstruct signals. For example $$\begin{align*} \mathrm {if}\quad ~ \mathrm {max}\left \{{|\langle \psi _{i1}^{T}.x\rangle |,|\langle \psi _{i1}^{T}.x\rangle |,\cdots,|\langle \psi _{i1}^{T}.x\rangle |}\right \} = |\langle \psi _{i1}^{T}.x\rangle |, \\\tag{10}\end{align*}$$ $\psi _{ii}$ will be selected to decompose and reconstruct the signal x; in formula (10), $\psi _{i}$ is a sparse matrix, $\psi _{ij}$ is a sparse basis (i.e., atom). The sparse representation of signal x is as follows: $$\begin{equation*} x = \psi. \theta = \sum \limits _{m - 1}^{K}\psi _{im}.\theta _{m}.\tag{11}\end{equation*}$$ The smaller the K value, the better the effect of sparse representation; this is what CS always pursues.

A. Problems

But in some special cases, this causes the edges of the objects to be unrecognizable, especially when the density of objects is very high.

1. For example, let signal $x_{1} =[11011000\cdots]^{T}$ , $x_{2} =\left [{ {11101000\cdots } }\right]^{T}$ , $x_{1}, x_{2} \in R^{N\times 1}$ ; $\psi _{1} \in R^{N\times M}$ , $\psi _{2} \in R^{N\times M}$ , $\cdots$ , $\psi _{6} \in R^{N\times M}$ (M and N are positive integers, usually M = N) are sparse basis matrices (i.e., dictionaries) with the base whose size of non-zero blocks are $1,2,\cdots, 6$ , respectively; $\psi = [10000000\cdots]^{T}$ , $\psi = [11000000\cdots]^{T}$ , $\psi = [11100000\cdots]^{T}$ and $\psi = [10000000\cdots]^{T}$ , $\cdots$ ,$\psi = [11111110\cdots]^{T}$ are the sparse bases (i.e., atoms) from these sparse basis matrices (i.e., dictionaries) respectively. For signal $x_{1}$ , $\psi _{5i}$ (or $\psi _{5}$ ) is selected instead of $\psi _{2j}$ (or $\psi _{2}$ ); likewise, for $x_{2}$ , $\psi _{5m}$ (or $\psi _{5}$ ) is selected instead of $\psi _{1i}$ (or $\psi _{1}$ ) and $\psi _{3k}$ (or $\psi _{3}$ ).

2. Another example is in $l_{p}$ regularization. When there is more than one dictionary for people to choose from,

   if $$\begin{align*} \min \left \{{{\left \|{ {\Psi _{1}^{-1} x} }\right \|_{p}, \left \|{ {\Psi _{2}^{-1} x} }\right \|_{p}, \cdots, \left \|{ {\Psi _{n}^{-1} x} }\right \|_{p}} }\right \}=\left \|{ {\Psi _{j}^{-1} x} }\right \|_{p} \\\tag{12}\end{align*}$$ the dictionary $\Psi _{j}$ will be selected to decompose and reconstruct signal x; but in some special cases, this is not the best choice.

3. The third example is multiple dictionaries in $l_{p}$ regularization. As shown in Formula 13, $$\begin{equation*} \hat {x}=\mathop {\mathrm {argmin}}\limits _{x} \left \{{{\gamma \left \|{ {\Phi x-y} }\right \|_{p}^{p} +\sum \limits _{d=1}^{D} {\lambda _{d} \left \|{ {\Psi _{d}^{-1} x} }\right \|_{p}^{p}}} }\right \}\tag{13}\end{equation*}$$ it is not necessarily the optimal case: the smaller the value of $\left \|{ {\Psi _{d}^{-1} x} }\right \|_{1/2}^{1/2}$ , the larger the weighting parameter. In some special cases, for example, if the local density of small objects is very high, it is usually occur that the most appropriate sparse dictionary cannot have the largest weighting parameter. Choosing the dictionary that matches the signal best rather than the dictionary with the maximum sparsity can reconstruct the signal more accurately.

B. Solution

In order to overcome the above shortcomings, according to the characteristics of maritime radar images, we propose the method of calculating the percentages of different size non-zero blocks and choosing the appropriate sparse base (or dictionary). The percentage of some size non-zero blocks is $$\begin{equation*} p(i)=\frac {N(i)}{\sum \limits _{i=2}^{K_{1} \times K_{2}} {N(i)}},\tag{14}\end{equation*}$$ where N(i), $i=1,2,3,\cdots$ , denote the number of blocks containing i consecutive non-zero elements, $K_{1}$ and $K_{2}$ are the numbers of rows and columns of image pixels, respectively. The corresponding distribution function is as formula (15), $$\begin{equation*} F(c)=F(1\le i\le c)=\frac {\sum \limits _{i=1}^{c} {N(i)} }{\sum \limits _{i=1}^{K_{1} \times K_{2}} {N(i)}}\tag{15}\end{equation*}$$ where c is a constant; c is usually considered as the classification threshold constant for the size of non-zero blocks.

The precondition for the application of our proposed method is that the signal is binary. Although radar image has binarization characteristics, it is usually not binarized image; so the appropriate binarization threshold Th is needed to binarize the image for judgment, and then calculate the percentages (or distribution function) of some size non-zero blocks.

The principle of selecting sparse base (or dictionary) is usually as follows $$\begin{equation*} d\le \left \|{ {\psi _{c}} }\right \|_{0} or d\approx \left \|{ {\psi _{c}} }\right \|_{0},\tag{16}\end{equation*}$$ where d is the size of non-zero block, $\psi _{c}$ is a sparse base (atom) of the sparse dictionary.

SECTION IV. Method Proposed in This Paper

To overcome the shortcoming of CS in using inner product, we proposes an image processing method of CS based on arbitrary block statistical histogram and dynamic dictionary. When the small targets are very dense, our method can avoid erroneously choosing the larger sparse base (or dictionary) and avoid erroneously setting regularization parameters, so as to better identify the edges of the small targets and improve the SNR.

In order to implement our method, several experiments are needed to get the relevant threshold parameters or conclusions.

To select the appropriate sparse base (or dictionary), classification threshold constants are needed to determine which sparse base (or dictionary) is the most appropriate choice. So we use arbitrary block statistical histogram to obtain the statistic numbers of various size non-zero blocks, which can be used to generate the classification threshold constants; but building arbitrary block statistical histograms need binary threshold Th. Through simulation experiments, we get the appropriate binary threshold Th and corresponding SNR, which can eliminate noise interference in establishing arbitrary block statistical histogram. Arbitrary block statistical histogram can also reflects the local characteristics of sub-images, based on which we construct the objective functions for the noiseless and noisy signals respectively.

For different dynamic image sequences, adaptive noise detection method is used to detect whether the signal is a noisy signal or not firstly; and then one of the methods is chosen. The overall flow chart is as follows:

The rest of this chapter is divided into three parts: A. several experiments and results; B. The flow chart and objective function for noiseless signal; C. The flow chart and objective function for noisy signal.

A. Several Experiments and Results

1. In order to better classify and process signals, we define two constants $a_{1}$ and $b_{1}$ as classification thresholds, where $a_{1} < b_{1}$ . The two constants will be given specific values from the following simulation experiments.

   For example, some percentages of non-zero blocks of the images in Figure 3 are shown in Table 1. In Figure 3, (a) denotes the image in the upper left corner, (b) denotes the image in the upper right corner, (c) is the image in the lower left corner, (d) is the image in the lower right corner. Let N(i) denote the number of blocks containing i consecutive non-zero elements, where $i=1,2,3,\cdots$ , $K_{1}$ and $K_{2}$ are the rows and columns of image pixels, respectively, $F(i\le 2)=\frac {N(1) +N(2) }{\sum \limits _{i=1}^{K_{1} \times K_{2}} {N(i)}}$ denotes the percentage of non-zero blocks whose size is not greater than 2, $F(i\le 4)=\frac {N(1) +N(2) +N(3) +N(4) }{\sum \limits _{i=1}^{K_{1} \times K_{2}} {N(i)}}$ denotes the percentage of non-zero blocks whose size is not greater than 4;

   The corresponding percentages of some non-zero blocks of images in Figure 4 are shown in Table 2.

   In order to obtain appropriate classification thresholds, we have done a lot of experiments with various radar images. Then we get the reasonable classification thresholds $a_{1}$ and $b_{1}$ , which are 3% and 6% respectively. The selection principle of classification threshold is that as long as there is an object (e.g., ship, boat or island), the method will strive to detect it.

2. For noise signal, in order to eliminate the interference of noise in arbitrary block statistical histogram which is used to judge the local characteristics of sub-images, we have done a lot of simulation experiments with a large number of various radar images under different SNR and thresholds. In order to get accurate raw data, we do not use threshold de-noising (e.g., adaptive threshold de-noising) in the simulation experiments. Finally, the appropriate threshold Th is obtained. Take Figure (e) of Figure 4 as an example, let F(i<=2)=N(1)+N(2), F(i<=4)=N(1)+N(2)+N(3)+N(4), F(i<=2) represents the number of non-zero blocks with sizes of 1 and 2, similarly, F(i<=4) is the number of non-zero blocks with sizes of 1, 2, 3 and 4. Our simulation results are shown in Table 3. We only show the simulation results when the binarization threshold Th =25, 38 and 50, which is about 10%, 15% and 20% of the maximum pixel value respectively (assuming that the maximum pixel amplitude of the images is 255).

   From Table 3, it can be seen that the interference of noise in statistical histogram can be removed when $Th=50$ and $SNR\ge 13dB$ ; if the threshold is less than 50 and the corresponding SNR is less than 13 dB, it is not applicable for noise signals, because statistical values of non-zero blocks fluctuate considerably. A large number of simulation experiments based on different marine radar images also validate the above conclusions.

3. In order to reduce the running time and better choose different methods according to different local characteristics, an image is divided into several sub-images [49]. Let sub-image $S(i,j)\in R^{N\times N}$ , where N is positive integer, the maximum decomposition level of sub-image is L, the reference table for the relationship between the image size and the maximum decomposition level is shown in Table 4.

TABLE 1 Percentages of Some Non-Zero Blocks

TABLE 2 Percentages of Some Non-Zero Blocks

TABLE 3 Some Non-Zero Blocks Statistics of Several Images Under Different SNR. (a) Binarization threshold Th=25. (b) Binarization threshold Th=38. (c) Binarization threshold Th=50

TABLE 4 Relationship Reference Table of the Image Size and the Maximum Decomposition Level

FIGURE 2.

Overall flow chart of the method proposed in this paper.

FIGURE 3.

Some images without targets.

FIGURE 4.

Some images containing targets.

If the size of the sub-image is too small, there will be block effect, which will make the SNR worse.

1) Effect of Different Wavelets on Radar Images

We simulate different wavelets to find the most suitable wavelet for maritime radar image processing. The simulation results are shown in Figure 5 and Figure 6.

FIGURE 5.

Comparisons of image processing effects with different wavelets.

FIGURE 6.

Comparisons of image processing effects with different wavelets.

In Figure 5, the wavelets used in the first row above from left to right are haar,db1 and db2; the wavelets used in the second row from left to right are db3,db4 and db5; the third row are db6, sym1 and sym2.

In Figure 6, the wavelets used in the first row from left to right are haar,sym3 and bior2.4; the wavelets used in the second row from left to right are bior4.4, coif1 and, coif2; the third row are coif3, coif4 and coif5.

From the comparisons, we can see that Haar wavelet is usually the best among all kinds of wavelets in maritime radar image processing.

B. The Flow Chart and Objective Function for Noiseless Signal

The flow chart of the method we proposed for noiseless signal is shown in Figure 7.

FIGURE 7.

Flow chart of the method proposed in this paper for noiseless image.

Firstly, a frame image S is divided into M rows and M columns, the size of each sub-image is K*K. and each sub-image S(i, j) is binarized respectively, where the threshold of binarization is usually 0; of course, other smaller values can also be set as the binarization threshold according to specific circumstances.

Let $B(i,j)$ denotes the binary matrix of S(i, j), then each $B(i,j)$ is transformed into a column vector $C_{\left ({{i,j} }\right)}$ . In each column vector $C_{\left ({{i,j} }\right)}$ , we define that a single non-zero element (entry) is counted as a block of size 1. Similarly, if several non-zero elements are connected sequentially, as long as they are not separated by zero, these non-zero elements are counted as a block. According to the column vector $C_{\left ({{i,j} }\right)}$ , the statistical histogram of arbitrary block is established for sub-image $S(i,j)$ . In statistical histogram, let N(i) denote the number of non-zero blocks with the size of i, where $i=1,2,3,\cdots$ .

Taking Figure (e) of Figure 4 as an example, divide it into 4 rows and 4 columns. The statistical histogram of each sub-image is shown in Figure 8. Due to the limited space of the paper, each statistical histogram cannot be fully displayed in Figure 9.

FIGURE 8.

Divide an image into several sub-images.

FIGURE 9.

Histograms of sub-images in FIGURE 8.

According to the statistical histogram, better matched sparse bases (or dictionaries) are selected respectively. Then a better measurement vector y is obtained at the sender. Finally, the original image S is reconstructed by using Stagewise OMP at the receiving end. The objective function based on statistical histogram is elaborated in the following paragraph.

Let $\textrm {A=}\left ({{{\begin{array}{*{20}c} 0 &\,\, \ldots &\,\, 0 \\ \vdots &\,\, \ddots & \vdots \\ 0 &\,\, \cdots &\,\, 0 \\ \end{array}}} }\right)_{K\times K}$ . If $\sum \limits _{i=1}^{K\times K} {N(i)} =0$ , the bsub-image $S(i,j)$ is a zero matrix; It is discarded directly at the sender and reconstructed into a zero matrix at the receiving end, i.e. $\textrm {S(i,j)=A=}\left ({{{\begin{array}{*{20}c} 0 &\,\, \ldots &\,\, 0 \\ \vdots &\,\, \ddots &\,\, \vdots \\ 0 &\,\, \cdots &\,\, 0 \\ \end{array}}} }\right)_{K\times K}$ .

If $\sum \limits _{i=1}^{K\times K} {N(i)} \ne 0$ , the percentages of some N(i) which will be used are calculated according to the formula $p(i)=\frac {N(i)}{\sum \limits _{i=1}^{K\times K} {N(i)}},i=1,2,3,4\cdots$ . The distribution function of some blocks whose sizes are in a certain range is $F(i\vert a\le i\le b)=\sum \limits _{i=a}^{i=b} {p(i)}$ . Then $F(i\vert a\le i\le b)$ is compared with classification thresholds to select the appropriate sparse base (or dictionary). The classification thresholds set in this paper are mainly for marine radar images. For noiseless signals, the objective function we constructed is shown in formula (17), as shown at the bottom of this page.

Of course, according to different application objects (or environments), people can adjust the thresholds by themselves.

In formula (17), the set of dynamic dictionary is composed of 4-level wavelet sparse basis matrix (dictionary), 5-level wavelet dictionary, and 6-level wavelet dictionary of Haar. 4-level wavelet sparse basis matrix (dictionary) consists of 1, 2, 3,4-layer of wavelet sparse bases, and other dictionaries are similar to it.

C. The Flow Chart and Objective Function for Noisy Signal

Firstly, threshold de-noising (e.g., adaptive threshold de-noising) is applied to the noisy image S, and the image is divided into several sub-images. Then each sub-image is converted into binary matrix B by using threshold Th=50 (or $0.2A_{m}$ ). $A_{m}$ is the maximum amplitude of the signal. If the maximum amplitude of the signal is 255, the threshold is usually 50; otherwise, the threshold is $0.2A_{m}$ . According to the binary matrix B, the statistical histogram of arbitrary block is established. N(i) denotes the number of non-zero blocks whose size is i, where $i=1,2,3,\cdots$ .

The flow chart of processing noisy signal proposed in this paper is similar to that of noiseless signal. In order to avoid omitting weak signals, when $\sum \limits _{i=1}^{K\times K} {N(i)} =0$ , 3-level wavelet dictionary is used to process the corresponding sub-image. The flow chart of the method proposed in this paper for noisy signal is shown in Figure 10.

FIGURE 10.

Flow chart of the method proposed in this paper for noisy signal.

2) In noisy environments, the objective function we constructed is as follows (18), as shown at the bottom of the next page.

D. Advantages and Limits of Our Method

The method we proposed is a fully automatic method for radar image processing based on statistical histogram of arbitrary blocks and dynamic dictionary, which can overcome the shortcoming of CS in using inner product. The objective functions we constructed can quickly and efficiently recognize the local characteristics of sub-images, so as to better select sparse basis dictionary and get an optimal measurement vector y in signal sampling. As long as the signal satisfies the reconstruction condition of phase diagram [48], it usually can be better reconstructed at the receiving end. It also can reduce running time than other methods. In addition, for noisy signal, our method can eliminate the interference of noise in judging local characteristics by arbitrary blocks statistical histogram.

Our method is only suitable for maritime radar images and other similar images which have binary characteristics; it is usually not suitable for processing natural images.

SECTION V. Simulation Results

In this paper, we select a frame of dynamic image for simulation experiment. Taking Figure 11 as an example, we carry out simulation experiments in noiseless and noisy environments respectively. The image has 512 rows and 512 columns, which is divided into 4 rows and 4 columns. The pixels of each sub-image are $128\times 128$ . The range of pixel values is 0-255.

FIGURE 11.

An ideal maritime radar image.

A. Noiseless

In the noiseless environment, we propose a fully automatic method for recognizing the local features of sub-images based on statistical histogram of arbitrary blocks. According to the statistical histogram, different methods are chosen for different sub-images. A better measurement vector y is obtained at the sender; and a relatively clear image will be obtained at the receiving end. The SNR of the proposed method is usually bigger than state of the art methods of CS in processing radar images. Taking Figure 11 as an example, we carried out a simulation experiment with it. The SNR of each method at different sampling ratio is shown in Figure 12.

FIGURE 12.

SNR curves of each method at different sampling ratio.

As can be seen from Figure 12, the performance of Adaptive Matrix Design method (AMD) is very good when the sampling ratio is less than 0.4, because it adaptively designs the sensing matrix (i.e., measurement matrix) according to the signal. When the sampling rate is equal to or greater than 0.4, the measurement matrix can usually reconstruct the signal well. Under these circumstances, the sparse matrix and the weighted optimization strategy usually play the major role in reconstructing signal. So the method of Wavelet Tree Support Detection is superior to others other method. However, this method also has the shortcoming of using the maximum inner product; when the density of small targets is very high, it usually causes the edges of small targets unrecognizable. Our method overcomes this shortcoming in maritime radar image processing, so our method is superior to the other methods.

Since marine radar images are usually sparse, several of the sub-images S(i, j) are usually zero matrices, which are discarded directly at the sender and recovered into zero matrix at the receiving end. Consequently, for marine radar images, the proposed method commonly takes less time than the other methods. The running time of each method at different sampling ratio is shown in Table 5.

TABLE 5 Running Time of Different Method at Different Sampling Ratio

B. Noise

Our method can eliminate the interference of noise in distinguishing local characteristics by statistical histogram, so that sparse basis (or dictionary) can be selected better according to the local characteristics of the image, and better measurement vector y can be obtained, which provides favorable conditions for obtaining high quality reconstructed signal at the receiving end.

Suppose the maximum pixel value of the image is 255. The interference of noise in statistical histogram can be removed when $Th=50$ and $SNR\ge 13dB$ ; Assuming that the SNR of the signal is 16 dB, the SNR curves of the several methods at different sampling ratio are shown in Figure 13.

FIGURE 13.

SNR curves of reconstructed signal at different sampling ratios.

The curves of Figure 13 are similar to those without noise, so we will not elaborate on them here. When the sampling rate is 0.5 and SNR=16dB, the reconstruction images of several methods is shown in Figure 14. And the SNR curves of reconstructed signals with different input SNR are shown in Figure 15.

FIGURE 14.

Comparison of the methods at SNR=16 dB.

FIGURE 15.

Comparison of the methods at sampling ratio is 0.5.

As can be seen from Figure 14, because our method chooses the appropriate sparse base (or dictionary), the image is much clearer than other methods when the targets are very dense.

As can be seen from Figure 15, threshold de-noising (e.g., adaptive threshold de-noising) is usually effective when the SNR of the signal is low; but when small targets are very dense, the effect of threshold de-noising (e.g., adaptive threshold de-noising) is not obvious when the SNR of signal is high. The running time of each method is shown in Table 6.

TABLE 6 Running Time of Different Methods Under Different Sampling Ratios

Radar image is about 24 frames per minute, so the processing time of each frame is about 2.5 seconds. From the table 6 it can be seen that our method can process real-time radar image. If other methods also use threshold de-noising (adaptive threshold de-noising), the SNR curves are shown in Figure 16.

FIGURE 16.

SNR curves of reconstructed signals with adaptive threshold de-noising.

As can be seen from the above, our method overcomes the shortcoming of CS in using absolute value of inner product for selecting atoms (or dictionaries). Our method not only improves the SNR, but also has less running time, and thus can process dynamic radar image in real time.

SECTION VI. Conclusions

In this paper, according to the characteristics of maritime radar images, we propose a fully automatic radar image processing algorithm of CS based on arbitrary block statistical histogram and dynamic dictionary. The method we proposed can overcome the shortcoming of CS in using the absolute value of the inner product for selecting atoms (or dictionaries) in processing maritime radar images. And the objective functions we construct can quickly and efficiently select optimal sparse basis matrix (i.e., dictionary) to decompose and reconstruct signals. Then the better measurement vector y can be obtained, and the signal can be reconstructed more accurately than state of the art methods at the receiving end. It also can reduce running time, suppress noise and improve SNR. Simulation results show that our method is superior to state of the art methods.