CN104077751B

CN104077751B - High spectrum image reconstructing method based on mixing norm tracing algorithm

Info

Publication number: CN104077751B
Application number: CN201410277310.8A
Authority: CN
Inventors: 尹继豪; 余万科; 姜志国; 曲徽; 朱红梅
Original assignee: Beihang University
Current assignee: Beihang University
Priority date: 2014-06-19
Filing date: 2014-06-19
Publication date: 2016-08-24
Anticipated expiration: 2034-06-19
Also published as: CN104077751A

Abstract

The invention discloses a hyperspectral image reconstruction method based on a mixed-norm tracking algorithm: analyzing the existing compressed sensing reconstruction algorithm in combination with hyperspectral image properties, selecting the corresponding 0-norm algorithm and 1-norm algorithm, and proving the existence of Combining the two hybrid strategies and finding the best hybrid strategy, a hybrid norm pursuit algorithm is obtained, and then the sparsely sampled hyperspectral image is reconstructed, and finally the reconstructed hyperspectral image obtained by sparse inverse transformation is output. The method has four functional modules: a human-computer interaction interface module, a hybrid strategy analysis module, a hyperspectral image reconstruction module, and a reconstructed image output module. Compared with the traditional reconstruction method, the hybrid norm tracking algorithm has obvious improvement in speed and accuracy, which reduces the hardware pressure brought by hyperspectral big data transmission and storage, and improves the anti-interference ability of data transmission.

Description

Hyperspectral Image Reconstruction Method Based on Mixed Norm Pursuit Algorithm

技术领域technical field

本发明涉及一种基于混合范数追踪算法的高光谱图像重构方法，适用于高光谱数据处理系统中，属于高光谱数据处理领域。The invention relates to a hyperspectral image reconstruction method based on a mixed norm tracking algorithm, which is suitable for a hyperspectral data processing system and belongs to the field of hyperspectral data processing.

背景技术Background technique

高光谱遥感是一项近几十年来迅速发展的空天对地观测技术，它图谱合一的性质有重大的研究意义和广泛的应用前景，已经在商业、军事和民间领域得到广泛应用。相比较于常规遥感图像，高光谱图像能够更精细的刻画地物特征，探测到常规遥感中无法探测到的物质，为后期地物分类以及探测提供前提条件。然而，它良好的性质建立在庞大的数据量上，一张高光谱图像的大小往往是常规图像的几百倍，大量的波段数带来了巨大的信息冗余。这为高光谱图像的采集、传输和存储带来不必要的麻烦。Hyperspectral remote sensing is a space-to-earth observation technology that has developed rapidly in recent decades. Its image-spectrum integration has great research significance and broad application prospects. It has been widely used in commercial, military and civil fields. Compared with conventional remote sensing images, hyperspectral images can more finely describe the characteristics of ground features, detect substances that cannot be detected in conventional remote sensing, and provide prerequisites for later classification and detection of ground features. However, its good properties are based on the huge amount of data. The size of a hyperspectral image is often hundreds of times that of a conventional image, and a large number of bands brings huge information redundancy. This brings unnecessary troubles to the collection, transmission and storage of hyperspectral images.

压缩感知是近年来提出的一个寻找欠定系统稀疏解的技术，该技术通过开发信号的稀疏特性在远小于奈奎斯特采样率的条件下，利用随机采样获取信号的离散样本，然后通过非线性重构算法完美重构信号。压缩感知理论一经提出便受到信息论、图像处理、地球科学、光学、微波成像、模式识别、无线通讯等领域的高度关注，并被广泛的应用于电子工程尤其是信号处理中，进行低采样率采样和高精度重构稀疏或可压缩的信号。目前广泛采用的压缩感知重构算法主要有两类：基于0范数的贪婪算法和基于1范数的凸优化算法。基于0范数的贪婪算法包括匹配追踪算法、正交匹配追踪算法、硬阈值迭代算法等，基于1范数的凸优化算法包括基追踪算法、梯度投影算法、内点法、同伦法等。这两类算法各有所长但也均有其不足之处：0范数对应的算法速度快但是精度不高；1范数对应的算法精度高但速度不快。Compressed sensing is a technology proposed in recent years to find the sparse solution of underdetermined systems. This technology uses random sampling to obtain discrete samples of the signal by exploiting the sparse characteristics of the signal at a rate much smaller than the Nyquist sampling rate, and then uses non- The linear reconstruction algorithm perfectly reconstructs the signal. Once the theory of compressed sensing was put forward, it received high attention in the fields of information theory, image processing, earth science, optics, microwave imaging, pattern recognition, wireless communication, etc., and was widely used in electronic engineering, especially in signal processing, for low sampling rate sampling and reconstruct sparse or compressible signals with high accuracy. There are two main types of compressive sensing reconstruction algorithms widely used at present: the greedy algorithm based on 0-norm and the convex optimization algorithm based on 1-norm. Greedy algorithms based on 0 norm include matching pursuit algorithm, orthogonal matching pursuit algorithm, hard threshold iterative algorithm, etc. Convex optimization algorithms based on 1 norm include basis pursuit algorithm, gradient projection algorithm, interior point method, homotopy method, etc. These two types of algorithms have their own strengths but also have their shortcomings: the algorithm corresponding to the 0 norm is fast but the accuracy is not high; the algorithm corresponding to the 1 norm is high in accuracy but not fast.

高光谱图像数据庞大且获取不易，为了减轻硬件传输、存储压力需尽可能低的进行采样和高精度重构；另一方面，低速度的重构算法的缺点会因大数据量而被急剧的放大，造成的时间消耗往往让人无法忍受。因此，需要寻找一种重构精度足够高并且重构速度足够快的算法，满足高光谱图像实时处理的需求。Hyperspectral image data is huge and difficult to obtain. In order to reduce hardware transmission and storage pressure, sampling and high-precision reconstruction should be performed as low as possible; The time consumption caused by zooming in is often unbearable. Therefore, it is necessary to find an algorithm with high enough reconstruction accuracy and fast enough reconstruction speed to meet the needs of real-time processing of hyperspectral images.

发明内容Contents of the invention

本发明旨在提供一种基于混合范数追踪算法的高光谱图像重构方法，具体是一种结合现有0范数算法和1范数算法优点的新型压缩感知重构方法。本方法具有较强的鲁棒性，能够在保证重构精度的情况下快速的重构出原始的高光谱图像，对不同地物环境的高光谱图像均表现出良好的实验效果。The present invention aims to provide a hyperspectral image reconstruction method based on a mixed-norm tracking algorithm, specifically a new compressed sensing reconstruction method that combines the advantages of the existing 0-norm algorithm and 1-norm algorithm. This method has strong robustness, can quickly reconstruct the original hyperspectral image while ensuring the reconstruction accuracy, and shows good experimental results for hyperspectral images of different ground object environments.

本发明所涉及的方法流程具体包括以下四个步骤：1、获得初始信息及相关初始化操作；2、混合策略分析；3、高光谱图像重构；4、重构结果输出。下面对该方法流程各步骤进行详细说明：The method flow involved in the present invention specifically includes the following four steps: 1. Obtaining initial information and related initialization operations; 2. Mixing strategy analysis; 3. Hyperspectral image reconstruction; 4. Outputting reconstruction results. Each step of the method flow is described in detail below:

步骤一获得初始信息及相关初始化操作Step 1 Obtain initial information and related initialization operations

利用人工交互接口模块输入高光谱图像稀疏采样结果和两类算法范例，并设置如公式(1)到(3)所示的算法迭代终止条件，对是否终止算法进行判断。Use the manual interaction interface module to input hyperspectral image sparse sampling results and two types of algorithm examples, and set the algorithm iteration termination conditions shown in formulas (1) to (3) to judge whether to terminate the algorithm.

|norm(x_k-1，0)-norm(x_k，0)|＜ε₀ (1)|norm(x _k-1 ，0)-norm(x _k ，0)|＜ε ₀ (1)

$\frac{| | | | {x x}_{k k} - - {x x}_{k k - - 11} | | | |}{| | | | {x x}_{k k} | | | |} \leq \leq {ϵ ϵ}_{11} - - - - - - ((22))$

$\frac{| | | | f f (({x x}_{k k})) - - f f (({x x}_{k k - - 11})) | | | |}{| | | | f f (({x x}_{k k})) | | | |} \leq \leq {ϵ ϵ}_{22} - - - - - - ((33))$

其中，norm(x，0)代表x中非零元素个数，ε₀，ε₁，ε₂是选定的正常数，x是第k步迭代结果，f是目标函数。Among them, norm(x, 0) represents the number of non-zero elements in x, ε ₀ , ε ₁ , ε ₂ are selected normal numbers, x is the iteration result of step k, and f is the objective function.

步骤二混合策略分析Step 2 Mixed Strategy Analysis

假设原始信号是k稀疏的n维信号，它的稀疏变换结果为x，求解的近似结果为x′。实际上，无论是基于0范数的算法还是基于1范数的算法，它们的迭代过程都是n维空间上逼近目标的一条折线。假定n维空间的基为 Assuming that the original signal is a k-sparse n-dimensional signal, its sparse transformation result is x, and the approximate result of the solution is x′. In fact, whether it is an algorithm based on 0-norm or an algorithm based on 1-norm, their iterative process is a broken line approaching the target in n-dimensional space. Suppose the basis of n-dimensional space is

基于0范数的算法满足下面的约束优化问题：The 0-norm-based algorithm satisfies the following constrained optimization problem:

$\underset{x x}{min min} {| | | | x x | | | |}_{{l l}_{00}},, s the s . . t t . . ΦΨx ΦΨx = = y the y - - - - - - ((44))$

其中，y代表观测值，x是我们需要求解的结果，Φ是观测矩阵Ψ是稀疏矩阵。基于0范数的贪婪算法的每一步都会获得某个结果维度上的近似值，按照下面的步骤进行迭代：Among them, y represents the observed value, x is the result we need to solve, Φ is the observation matrix Ψ is a sparse matrix. Each step of the greedy algorithm based on 0 norm will obtain an approximate value on a certain result dimension, and iterate according to the following steps:

第1步，从原点出发沿坐标轴获取第一个分量的近似值 Step 1, start from the origin and get the approximate value of the first component along the coordinate axis

第2步，从x₁′出发沿坐标轴获取第二个分量的近似值 Step 2, start from x ₁ ′ and get the approximate value of the second component along the coordinate axis

第n步，从x_n-1′出发沿坐标轴获取第n个分量的近似值 In the nth step, starting from x _n-1 ′, get the approximate value of the nth component along the coordinate axis

基于1范数的算法满足下面的凸优化问题：The 1-norm based algorithm satisfies the following convex optimization problem:

$\underset{x x}{min min} {| | | | x x | | | |}_{{l l}_{11}},, s the s . . t t . . ΦΨx ΦΨx = = y the y - - - - - - ((55))$

它可以利用拉格朗日方法写成如下形式：It can be written using the Lagrangian method as follows:

$\underset{x x}{min min} (({| | | | x x | | | |}_{{l l}_{11}} + + τ τ | | | | y the y - - ΦΨx ΦΨx | | | |)) - - - - - - ((66))$

其中，τ代表一个用来平衡信号稀疏度和重构误差的非负常量。凸优化算法的每一步迭代都会使迭代结果离目标更近一些。为了更直接的说明，利用梯度引导的算法作为一个例子，这类算法以下面的步骤进行着迭代过程：Among them, τ represents a non-negative constant used to balance signal sparsity and reconstruction error. Each iteration of the convex optimization algorithm will bring the iteration result closer to the goal. For a more direct illustration, using gradient-guided algorithms as an example, such algorithms perform an iterative process in the following steps:

第1步，从原点出发，沿此时的梯度方向前进α⁰步长 Step 1, starting from the origin, advance along the gradient direction at this time by α ⁰ steps

第2步，从x₁′出发，沿此时的梯度方向前进α¹步长 Step 2, starting from x ₁ ′, advance α ¹ step along the gradient direction at this time

第m步，从x_m-1′出发，沿此时的梯度方向前进α^m-1步长 In the mth step, starting from x _m-1 ′, advance along the gradient direction at this time for α ^m-1 steps

其中，参数αⁱ代表第i步的步长，代表目标函数。Among them, the parameter α ⁱ represents the step size of the i-th step, stands for the objective function.

基于步骤二的分析，将混合范数追踪算法确定为由0范数获得近似的结果，再由1范数算法进行调整得到精确结果的两步迭代过程。混合范数追踪算法有效的结合了0范数的速度和1范数的精度，能够高速准确的重构信号。现在存在的问题有两个：1、是否存在最优的混合策略；2、如何寻找最优混合策略。Based on the analysis of the second step, the mixed-norm tracking algorithm is determined as a two-step iterative process in which an approximate result is obtained by the 0-norm algorithm, and then an accurate result is obtained by adjusting the 1-norm algorithm. The mixed-norm tracking algorithm effectively combines the speed of 0-norm and the precision of 1-norm, and can reconstruct signals quickly and accurately. There are two problems now: 1. Whether there is an optimal mixed strategy; 2. How to find the optimal mixed strategy.

首先分析最优的混合策略是否存在，也就是说交换点t是否存在。定义0范数算法的速度时间函数为v₀(t)，1范数算法的速度时间函数为v₁(t)。为了分析方便，假设两类速度时间函数都足够光滑。Firstly, analyze whether the optimal mixed strategy exists, that is to say, whether the exchange point t exists. Define the speed-time function of the 0-norm algorithm as v ₀ (t), and the speed-time function of the 1-norm algorithm as v ₁ (t). For the convenience of analysis, it is assumed that the two types of velocity-time functions are smooth enough.

如图2所示，将一次迭代的初始点到目标点的距离记做d₁，终止点到目标点的距离记做d₂，将这次迭代所走的路程记做d₁-d₂。那么这两个时间点之间的算法的速度时间函数满足公式(7)。As shown in Figure 2, the distance from the initial point to the target point of an iteration is recorded as d ₁ , the distance from the end point to the target point is recorded as d ₂ , and the distance traveled by this iteration is recorded as d ₁ -d ₂ . The speed-time function of the algorithm between these two time points then satisfies formula (7).

${&Integral; &Integral;}_{{t t}_{11}}^{{t t}_{22}} v v ((t t)) dt dt = = {d d}_{11} - - {d d}_{22} - - - - - - ((77))$

选择时间节点t作为两类算法的交替节点。在节点t之前，由0范数算法获得结果的近似值，之后由1范数算法对近似值进行调整，具体情况如图3所示。由于两类算法的速度不一样，相同时间里0范数算法前进的距离大于1范数算法，所以1范数对应的迭代初始时间应该大于t，记做f(t)。由前进距离相同可知，那么两者满足公式(8)所示的关系。The time node t is selected as the alternate node of the two types of algorithms. Before node t, the approximate value of the result is obtained by the 0-norm algorithm, and then the approximate value is adjusted by the 1-norm algorithm, as shown in Figure 3. Since the speeds of the two algorithms are different, the forward distance of the 0-norm algorithm is greater than that of the 1-norm algorithm at the same time, so the initial iteration time corresponding to the 1-norm should be greater than t, which is recorded as f(t). It can be known from the same advancing distance, then the two satisfy the relationship shown in formula (8).

${&Integral; &Integral;}_{{t t}_{00}}^{t t} {v v}_{00} ((t t)) dt dt = = {&Integral; &Integral;}_{{t t}_{00}}^{f f ((t t))} {v v}_{11} ((t t)) dt dt - - - - - - ((88))$

定义新算法的平均速度为那么它满足公式(9)所示的等式关系。Define the average speed of the new algorithm as Then it satisfies the equational relationship shown in formula (9).

$\overset{&OverBar; &OverBar;}{v v ((t t))} = = \frac{{&Integral; &Integral;}_{{t t}_{00}}^{t t} {v v}_{00} ((t t)) dt dt + + {&Integral; &Integral;}_{f f ((t t))}^{{t t}_{end end}} {v v}_{11} ((t t)) dt dt}{t t - - {t t}_{00} + + {t t}_{end end} - - f f ((t t))} - - - - - - ((99))$

联合公式(8)和公式(9)，可以得到下面的结果：Combining formula (8) and formula (9), the following results can be obtained:

$\overset{&OverBar; &OverBar;}{v v ((t t))} = = \frac{{&Integral; &Integral;}_{{t t}_{00}}^{{t t}_{end end}} {v v}_{11} ((t t)) dt dt}{{t t}_{end end} - - {t t}_{00} - - ((f f ((t t)) - - t t))} - - - - - - ((1010))$

由公式(10)可知，新算法运行的距离为这意味着它能达到和1范数算法相同的精度。随着测试样本的稀疏度增加，0范数算法的迭代时间明显增加，但是1范数算法的时间变化并不明显。例如，当测试样本的稀疏度增加到200的时候，正交匹配追踪算法的CPU运行时间明显增加，但是梯度投影算法的CPU运行时间没有多大改变。两种算法的混合使得新算法对测试样本的CPU运行时间更加稳定。另一方面，大多数1范数算法对迭代的初始点有条件要求，但是0范数算法则很少有要求。利用0范数算法得到的近似值作为1范数算法的迭代初始值往往比随机选择的初始值更符合1范数算法的要求。终上所述，混合范数追踪算法较于原来的0范数算法和1范数算法具有更强的鲁棒性。From formula (10), we can see that the running distance of the new algorithm is This means it can achieve the same accuracy as the 1-norm algorithm. As the sparsity of test samples increases, the iteration time of the 0-norm algorithm increases significantly, but the time change of the 1-norm algorithm is not obvious. For example, when the sparsity of test samples increases to 200, the CPU running time of the orthogonal matching pursuit algorithm increases significantly, but the CPU running time of the gradient projection algorithm does not change much. The mixture of the two algorithms makes the new algorithm more stable to the CPU runtime of the test samples. On the other hand, most 1-norm algorithms have conditional requirements on the initial point of iteration, but 0-norm algorithms rarely do. Using the approximate value obtained by the 0-norm algorithm as the iterative initial value of the 1-norm algorithm is often more in line with the requirements of the 1-norm algorithm than randomly selected initial values. Finally, the mixed-norm tracking algorithm is more robust than the original 0-norm algorithm and 1-norm algorithm.

由于新算法运行已经确定，关系新算法效率的仅仅是算法的时间节点选取。因此问题转化为下面的优化问题：Since the operation of the new algorithm has been determined, the only thing that affects the efficiency of the new algorithm is the selection of the time node of the algorithm. Therefore the problem is transformed into the following optimization problem:

$\underset{t t}{max max} ((f f ((t t)) - - t t))$

$s the s . . t t . . {&Integral; &Integral;}_{{t t}_{00}}^{t t} {v v}_{00} ((t t)) dt dt = = {&Integral; &Integral;}_{{t t}_{00}}^{f f ((t t))} {v v}_{11} ((t t)) dt dt - - - - - - ((1111))$

现在分别来证明公式(11)中的函数f(t)连续和最优混合策略在开区间(t₀，t_end)上存在。Now respectively prove that the function f(t) in formula (11) exists on the open interval (t ₀ , t _end ) on the continuous and optimal mixed strategies.

首先定义函数F(t)： $F (t) = {&Integral;}_{t_{0}}^{t} v_{0} (t) dt = {&Integral;}_{t_{0}}^{f (t)} v_{1} (t) dt$ First define the function F(t): $f (t) = {&Integral;}_{t_{0}}^{t} v_{0} (t) dt = {&Integral;}_{t_{0}}^{f (t)} v_{1} (t) dt$

对于选择开区间(t₀，t_end)中的任意一个点t_c，那么for Choose any point t _c in the open interval (t ₀ , t _end ), then

$| | | | F f ((t t)) - - F f (({t t}_{c c})) | | | | = = | | | | {&Integral; &Integral;}_{{t t}_{c c}}^{t t} {v v}_{00} ((t t)) dt dt | | | | \leq \leq | | | | t t - - {t t}_{c c} | | | | * * \underset{t t}{max max} | | | | {v v}_{00} ((t t)) | | | | - - - - - - ((1212))$

选取当||t-t_c||＜δ时，有||F(t)-F(t_c)||＜ε。也就是说F(t)在t_c点连续，由于t_c点的任意性，F(t)在开区间(t₀，t_end)上连续。select When ||tt _c ||<δ, there is ||F(t)-F(t _c )||<ε. That is to say, F(t) is continuous at t _c point, and due to the arbitrariness of t _c point, F(t) is continuous on the open interval (t ₀ , t _end ).

所以，对于存在一个正常数δ＞0，当||t-t_c||＜δ时So, for There is a constant δ>0, when ||tt _c ||<δ

$| | | | F f ((t t)) - - F f (({t t}_{c c})) | | | | = = | | | | {&Integral; &Integral;}_{f f (({t t}_{c c}))}^{f f ((t t))} {v v}_{11} ((t t)) dt dt | | | | = = | | | | f f ((t t)) - - f f (({t t}_{c c})) | | | | * * | | | | {v v}_{11} ((η η)) | | | | < < ϵ ϵ - - - - - - ((1313))$

$| | | | f f ((t t)) - - f f (({t t}_{c c})) | | | | < < \frac{ϵ ϵ}{| | | | {v v}_{11} ((η η)) | | | |} - - - - - - ((1414))$

公式(13)中，η是一个常数满足η∈[f(t)，f(t_c)]。因此，f(t)在点开区间(t₀，t_end)上任意点t_c处连续，所以f(t)在开区间(t₀，t_end)处连续。In formula (13), η is a constant satisfying η∈[f(t), f(t _c )]. Therefore, f(t) is continuous at any point t _c on the point-open interval (t ₀ , t _end ), so f(t) is continuous at the open interval (t ₀ , t _end ).

对于优化问题(11)，函数f(t)-t在区间(t₀，t_end)上连续。因此，对于任意函数f(t)-t在区间[t₀+ε，t_end-ε]上都存在最大值。现在问题转换成函数f(t)-t在区间[t₀，t_end]上的最大值取值位置不在t₀和t_end处。For the optimization problem (11), the function f(t)-t is continuous on the interval (t ₀ , t _end ). Therefore, for any The function f(t)-t has a maximum value on the interval [t ₀ +ε, t _end -ε]. Now the problem is transformed into that the maximum value of the function f(t)-t on the interval [t ₀ , t _end ] is not at t ₀ and t _end .

由之前的分析知，0范数的速度比1范数快，这意味着存在一点t₀′，在这点之前0范数的速度都会大于1范数。与之对应的，1范数运行时间比0范数长，这意味着在0范数的运行停止时1范数速度仍然在运行。即存在一点t_end′，在该点之后1范数的速度大于0范数速度。那么有：According to the previous analysis, the speed of the 0-norm is faster than the 1-norm, which means that there is a point t ₀ ′, and the speed of the 0-norm is greater than the 1-norm before this point. Correspondingly, the running time of the 1-norm is longer than that of the 0-norm, which means that the 1-norm speed is still running when the operation of the 0-norm stops. That is, there exists a point t _end 'after which the velocity of the 1-norm is greater than the velocity of the 0-norm. Then there are:

$\overset{&OverBar; &OverBar;}{v v (({t t}_{00}^{' '}))} = = \frac{{&Integral; &Integral;}_{{t t}_{00}}^{{t t}_{00}^{' '}} - - {v v}_{00} ((t t)) dt dt + + {&Integral; &Integral;}_{f f (({t t}_{00}^{' '}))}^{{t t}_{end end}} {v v}_{11} ((t t)) dt dt}{(({t t}_{end end} - - {t t}_{00})) - - ((f f (({t t}_{00}^{' '})) - - {t t}_{00}^{' '}))} = = \frac{{&Integral; &Integral;}_{{t t}_{00}}^{{t t}_{end end}} {v v}_{11} ((t t)) dt dt}{(({t t}_{end end} - - {t t}_{00})) - - ((f f (({t t}_{00}^{' '})) - - {t t}_{00}^{' '}))} > > \frac{{&Integral; &Integral;}_{{t t}_{00}}^{{t t}_{end end}} {v v}_{11} ((t t)) dt dt}{{t t}_{end end} - - {t t}_{00}} = = \overset{&OverBar; &OverBar;}{v v (({t t}_{00}))} - - - - - - ((1515))$

$\overset{&OverBar; &OverBar;}{v v (({t t}_{end end}^{' '}))} = = \frac{{&Integral; &Integral;}_{{t t}_{00}}^{{t t}_{end end}^{' '}} - - {v v}_{00} ((t t)) dt dt + + {&Integral; &Integral;}_{f f (({t t}_{end end}^{' '}))}^{{t t}_{end end}} {v v}_{11} ((t t)) dt dt}{(({t t}_{end end} - - {t t}_{00})) - - ((f f (({t t}_{end end}^{' '})) - - {t t}_{end end}^{' '}))} = = \frac{{&Integral; &Integral;}_{{t t}_{00}}^{{t t}_{end end}} {v v}_{11} ((t t)) dt dt}{(({t t}_{end end} - - {t t}_{00})) - - ((f f (({t t}_{end end}^{' '})) - - {t t}_{end end}^{' '}))} > > \frac{{&Integral; &Integral;}_{{t t}_{00}}^{{t t}_{end end}} {v v}_{00} ((t t)) dt dt}{{t t}_{end end} - - {t t}_{00}} = = \overset{&OverBar; &OverBar;}{v v (({t t}_{end end}))} - - - - - - ((1616))$

即函数f(t)-t在区间[t₀，t_end]上的最大值取值位置不在t₀和t_end处。That is, the position of the maximum value of the function f(t)-t on the interval [t ₀ , t _end ] is not at t ₀ and t _end .

根据前面的结论，对最优混合策略的选取进行分析。对公式(11)进行求导，得According to the previous conclusions, the selection of the optimal mixed strategy is analyzed. Taking the derivative of formula (11), we get

[f(t)-t]′＝f′(t)-1＝0 (17)[f(t)-t]'=f'(t)-1=0 (17)

对公式(8)进行分析，有Analyzing formula (8), we have

${[[{&Integral; &Integral;}_{{t t}_{00}}^{t t} {v v}_{00} ((t t)) dt dt]]}^{' '} = = {v v}_{00} ((t t)) - - - - - - ((1818))$

${[[{&Integral; &Integral;}_{{t t}_{00}}^{f f ((t t))} {v v}_{11} ((t t)) dt dt]]}^{' '} = = {v v}_{11} [[f f ((t t))]] {f f}^{' '} ((t t)) = = {v v}_{11} [[f f ((t t))]] - - - - - - ((1919))$

因此，可以得到：Therefore, one can get:

v₀(t)＝v₁[f(t)] (20)v ₀ (t) = v ₁ [f(t)] (20)

所以，效率最高的时刻的必要条件是运行相同路程时速度相同。也就是说，运行相同路程是速度相同的点有很大可能就是最优的混合策略点。Therefore, the necessary condition for the most efficient moment is the same speed when running the same distance. That is to say, the point of running the same distance and the same speed is very likely to be the optimal mixed strategy point.

步骤三重构高光谱图像Step 3 Reconstruct hyperspectral image

通过步骤二的分析，可以整理得到混合范数追踪算法的算法流程。为了方便理解，用梯度引导的算法作为1范数算法的例子：Through the analysis of step 2, the algorithm flow of the mixed norm tracking algorithm can be sorted out. For the convenience of understanding, the gradient-guided algorithm is used as an example of the 1-norm algorithm:

步骤1，利用0范数算法获取待求解信号的第一个分量的近似值 Step 1, use the 0-norm algorithm to obtain the approximate value of the first component of the signal to be solved

步骤2，利用0范数算法获取待求解信号的第二个分量的近似值 Step 2, use the 0-norm algorithm to obtain the approximate value of the second component of the signal to be solved

步骤p，利用0范数算法获取待求解信号的第p个分量的近似值 Step p, using the 0-norm algorithm to obtain the approximate value of the pth component of the signal to be solved

步骤p+1，利用1范数算法沿当前位置的梯度方向获取求解信号的位置 ${x_{p + 1}}^{'} = {x_{p}}^{'} - α^{p + 1} &dtri; f ({x_{p}}^{'});$ Step p+1, use the 1-norm algorithm to obtain the position of the solution signal along the gradient direction of the current position ${x_{p + 1}}^{'} = {x_{p}}^{'} - α^{p + 1} &dtri; f ({x_{p}}^{'});$

步骤q，利用1范数算法沿当前位置梯度方向获取求解信号的位置 $x^{'} = {x_{q}}^{'} = {x_{q - 1}}^{'} - α^{q} &dtri; f ({x_{q - 1}}^{'}) .$ Step q, use the 1-norm algorithm to obtain the position of the solution signal along the gradient direction of the current position $x^{'} = {x_{q}}^{'} = {x_{q - 1}}^{'} - α^{q} &dtri; f ({x_{q - 1}}^{'}) .$

在上面的算法流程中p∈{1，2，…k}，k是原始信号的稀疏度，αⁱ是第i步迭代步进；新算法将会很大概率的达到最优状态，如果利用0范数算法迭代p步花的时间t满足(8)和(20)。In the above algorithm flow, p ∈ {1, 2, ...k}, k is the sparsity of the original signal, α ⁱ is the iterative step of the i-th step; the new algorithm will reach the optimal state with a high probability, if using The time t it takes for the 0-norm algorithm to iterate p steps satisfies (8) and (20).

利用混合范数追踪算法对输入的低采样率高光谱图像数据进行重构，按照输入的终止条件终止迭代步骤，获得需要的稀疏近似解。根据高光谱图像的特点，选择相应的稀疏基，通过混合策略分析模块得到的混合范数重构算法对人机交互接口模块获取的稀疏采样结果进行重构，利用稀疏逆变换得到高光谱图像的重构结果。The mixed-norm tracking algorithm is used to reconstruct the input hyperspectral image data with low sampling rate, and the iterative steps are terminated according to the input termination conditions to obtain the required sparse approximate solution. According to the characteristics of the hyperspectral image, select the corresponding sparse basis, reconstruct the sparse sampling results obtained by the human-computer interaction interface module through the mixed norm reconstruction algorithm obtained by the mixed strategy analysis module, and use the sparse inverse transformation to obtain the hyperspectral image. Refactor the result.

步骤四重构结果输出Step 4 reconstruction result output

通过重构结果输出模块，输出重构完成的高光谱图像。Output the reconstructed hyperspectral image through the reconstruction result output module.

本发明是基于混合范数追踪算法的高光谱图像重构方法，其优点在于：能够在较短的时间内对低采样率的高光谱图像样本进行准确的重构，对于不同背景的地物目标和不同的采样率均能达到良好的重构效果，较原有的算法具有更高的鲁棒性。The present invention is a hyperspectral image reconstruction method based on a hybrid norm tracking algorithm, which has the advantage of being able to accurately reconstruct hyperspectral image samples with a low sampling rate in a relatively short period of time, and for objects with different backgrounds And different sampling rates can achieve good reconstruction effect, and it has higher robustness than the original algorithm.

附图说明Description of drawings

图1所示为基于混合范数追踪算法的高光谱图像重构方法流程图Figure 1 shows the flow chart of hyperspectral image reconstruction method based on mixed norm tracking algorithm

图2三类重构算法比较Figure 2 Comparison of three types of reconstruction algorithms

图3所示为速度的定义Figure 3 shows the definition of speed

图4所示为三类算法的速度时间关系Figure 4 shows the speed-time relationship of the three types of algorithms

图5所示为仿真实验数据Figure 5 shows the simulation experiment data

图6所示为仿真实验结果Figure 6 shows the results of the simulation experiment

具体实施方式detailed description

下面结合附图与仿真实验对该发明的技术方法进行进一步的说明。The technical method of the invention will be further described below in conjunction with the accompanying drawings and simulation experiments.

基于本发明开发了仿真原型系统，该系统包括：人机交互接口模块、混合策略分析模块、高光谱图像重构模块、重构图像输出模块这四个功能模块。Based on the present invention, a simulation prototype system is developed, which includes four functional modules: human-computer interaction interface module, hybrid strategy analysis module, hyperspectral image reconstruction module, and reconstructed image output module.

通过人机交互接口模块获得稀疏采样后的高光谱数据。本实例采用Indiana Pine高光谱数据和Washington D.C.Mall高光谱数据截取的一部分，具体情况如图4所示。其中，Indiana Pine高光谱数据大小为145×145，波长范围为400～2400nm，除去水汽吸收波段和低信噪比波段后，保留220个波段，Washington D.C.Mall高光谱数据截取的一部分，大小为100×100，波长范围为0.4～2.4μm，除去水汽吸收波段和低信噪比波段后，保留191个波段，采样矩阵为Gaussian随机矩阵。The sparsely sampled hyperspectral data is obtained through the human-computer interaction interface module. This example uses Indiana Pine hyperspectral data and a part of Washington D.C.Mall hyperspectral data interception, as shown in Figure 4. Among them, the size of the Indiana Pine hyperspectral data is 145×145, and the wavelength range is 400-2400nm. After removing the water vapor absorption band and the low signal-to-noise ratio band, 220 bands are reserved. A part of the hyperspectral data intercepted by Washington D.C.Mall has a size of 100 ×100, the wavelength range is 0.4-2.4 μm, after removing the water vapor absorption band and the low signal-to-noise ratio band, 191 bands are reserved, and the sampling matrix is a Gaussian random matrix.

对有关迭代终止条件的参数进行初始化处理，设置用来终止算法的参数ε₀，ε₁，ε₂，当算法满足公式(1)(2)(3)时，停止运行。Initialize parameters related to iteration termination conditions, set parameters ε ₀ , ε ₁ , ε ₂ used to terminate the algorithm, and stop running when the algorithm satisfies formula (1)(2)(3).

结合高光谱图像稀疏采样结果，选择合适的0范数算法和1范数算法，分析它们的具体算法流程，寻找它们的最优混合时间节点，获得混合范数追踪算法的算法流程。Combined with the hyperspectral image sparse sampling results, select the appropriate 0-norm algorithm and 1-norm algorithm, analyze their specific algorithm flow, find their optimal mixing time node, and obtain the algorithm flow of the mixed-norm tracking algorithm.

假设原始信号是k稀疏的n维信号，它的稀疏变换结果为x，求解的近似结果为x′。实际上，无论是基于0范数的算法还是基于1范数的算法，它们的迭代过程都是n维空间上逼近目标的一条折线。假定n维空间的基为为了方便解释，以下是由梯度引导的算法作为1范数算法的例子：Assuming that the original signal is a k-sparse n-dimensional signal, its sparse transformation result is x, and the approximate result of the solution is x′. In fact, whether it is an algorithm based on 0-norm or an algorithm based on 1-norm, their iterative process is a broken line approaching the target in n-dimensional space. Suppose the basis of n-dimensional space is For ease of explanation, the following is an example of a gradient-guided algorithm as a 1-norm algorithm:

步骤1：利用0范数算法获取待求解信号的第一个分量的近似值： Step 1: Use the 0-norm algorithm to obtain the approximate value of the first component of the signal to be solved:

步骤2：利用0范数算法获取待求解信号的第二个分量的近似值： Step 2: Use the 0-norm algorithm to obtain the approximate value of the second component of the signal to be solved:

步骤p：利用0范数算法获取待求解信号的第p个分量的近似值： Step p: Use the 0-norm algorithm to obtain the approximate value of the pth component of the signal to be solved:

步骤p+1：利用1范数算法沿当前位置的梯度方向获取求解信号的位置： ${x_{p + 1}}^{'} = {x_{p}}^{'} - α^{p + 1} &dtri; f ({x_{p + 1}}^{'});$ Step p+1: Use the 1-norm algorithm to obtain the position of the solution signal along the gradient direction of the current position: ${x_{p + 1}}^{'} = {x_{p}}^{'} - α^{p + 1} &dtri; f ({x_{p + 1}}^{'});$

步骤q：利用1范数算法沿当前位置梯度方向获取求解信号的位置： $x^{'} = {x_{q}}^{'} = {x_{q - 1}}^{'} - α^{q - 1} &dtri; f ({x_{q - 1}}^{'});$ Step q: Use the 1-norm algorithm to obtain the position of the solution signal along the gradient direction of the current position: $x^{'} = {x_{q}}^{'} = {x_{q - 1}}^{'} - α^{q - 1} &dtri; f ({x_{q - 1}}^{'});$

根据高光谱图像的特点，选择相应的稀疏基，通过混合策略分析模块得到的混合范数重构算法对人机交互接口模块获取的稀疏采样结果进行重构，利用稀疏逆变换得到高光谱图像的重构结果；According to the characteristics of the hyperspectral image, select the corresponding sparse basis, reconstruct the sparse sampling results obtained by the human-computer interaction interface module through the mixed norm reconstruction algorithm obtained by the mixed strategy analysis module, and use the sparse inverse transformation to obtain the hyperspectral image. reconstruction result;

通过重构结果输出模块，输出重构完成的高光谱遥感图像。Through the reconstruction result output module, the reconstructed hyperspectral remote sensing image is output.

本发明方法经过仿真系统的具体实施，实验结果表明能够高速高精度重构出不同采样率下不同背景的地物高光谱图像，具有良好的鲁棒性。The method of the invention is implemented by a simulation system, and the experimental results show that hyperspectral images of ground objects with different backgrounds at different sampling rates can be reconstructed at high speed and high precision, and have good robustness.

Claims

1. A hyperspectral image reconstruction method based on the mixed norm tracking algorithm, and based on the corresponding simulation prototype system, the system has a human-computer interaction interface module, a mixed strategy analysis module, a hyperspectral image reconstruction module, and a reconstructed image The four functional modules of the output module specifically include the following steps:

The first step is to obtain initial data and related initialization operations;

Use the human-computer interaction interface module to obtain hyperspectral image data with a low sampling rate, initialize the algorithm iteration termination conditions, and set related parameters: the original signal is a k-sparse n-dimensional signal, its sparse transformation result is x, and the approximate result of the solution is x′, the basis of n-dimensional space is

The second step is to analyze the reconstruction algorithm based on the 0-norm and the reconstruction algorithm based on the 1-norm, and obtain the corresponding hybrid strategy;

Combined with the characteristics of hyperspectral images, analyze the characteristics of the 0-norm algorithm and the 1-norm algorithm and establish a mixed strategy model, analyze and study the best mixed strategy, and obtain the algorithm flow of the mixed-norm tracking algorithm, and use the gradient-guided algorithm as the 1-norm Algorithm The algorithm flow of the mixed-norm tracking algorithm is obtained as follows:

Step 1, use the 0-norm algorithm to obtain the approximate value ξ _i ′ of the first component of the signal to be solved and the first iteration result

Step 2, use the 0-norm algorithm to obtain the approximate value ξ _j ′ of the second component of the signal to be solved and the second iteration result

Step p, using the 0-norm algorithm to obtain the approximate value ξ _p ′ of the p-th component of the signal to be solved and the iteration result of the p-th step

Step p+1, use the 1-norm algorithm to obtain the position of the solution signal along the gradient direction of the current position

Step q, use the 1-norm algorithm to obtain the position of the solution signal along the gradient direction of the current position

In the above algorithm flow, p∈{1, 2,...k}, k is the sparsity of the original signal, and α ⁱ is the iterative step of the i-th step; the mixed norm tracking algorithm will reach the optimal state with a high probability , if the time t it takes to iterate p steps using the 0-norm algorithm satisfies:

{&Integral; &Integral;}_{{t t}_{00}}^{t t} {v v}_{00} ((t t)) d d t t = = {&Integral; &Integral;}_{{t t}_{00}}^{f f ((t t))} {v v}_{11} ((t t)) d d t t - - - - - - ((11))

v ₀ (t) = v ₁ [f(t)] (2)

Among them, t ₀ is the initial moment of iteration, v ₀ (t) is the speed of the 0-norm algorithm, v ₁ (t) is the speed of the 1-norm algorithm, t is the time spent by the 0-norm algorithm to iterate p steps, f( t) is the time it takes for the 1-norm to walk the 0-norm algorithm for p steps;

The third step is hyperspectral image reconstruction;

According to the characteristics of the hyperspectral image, select the corresponding sparse basis, reconstruct the sparse sampling results obtained by the human-computer interaction interface module through the mixed norm reconstruction algorithm obtained by the mixed strategy analysis module, and use the sparse inverse transformation to obtain the hyperspectral image. reconstruction result;

Step 4: output hyperspectral image reconstruction results through the reconstruction result output module.