LovisMind

第 31 章

换基与图像压缩：好基的三个标准

换基是求解 P = Wc；好基要快、能压缩、最好正交。JPEG 用小块傅里叶基，小波基是它的竞争者；同一个变换在不同基下的矩阵互为相似。

Change of Basis and Image Compression: Three Tests for a Good Basis

A change of basis solves P = Wc; a good basis is fast, sparse, and ideally orthogonal. JPEG uses small Fourier blocks, wavelets compete with it, and one transformation in two bases yields similar matrices.

首发于 2019.09.25中 / EN
系统课程linear-algebrachange-of-basisimage-compressionwavelets
语言
字号
目录
篇内目录

图像就是一个很长的向量

一张 512×512512\times512 的灰度图有 5122=262144512^2=262144 个像素，每个像素取 00 到 255255 之间的整数，也就是 88 位。把像素按行排开，就得到一个 R262144\mathbb R^{262144} 中的向量。彩色图还需要三个通道，长度再乘三。

这就是压缩问题的起点：信息量太大，直接传输会压垮信道。

标准基为什么不好

标准基把每个像素单独看成一个坐标方向。可是自然图像里相邻像素高度相关：衬衫的蓝色区域、黑板的深色区域，相邻值往往只差一点点。

如果一块区域几乎所有像素都相同，标准基仍然要用几百个非零坐标去描述它——每个像素一个。这完全没有利用「相邻值接近」这一结构。

换基的目的，就是找到一组向量，使得少数几个系数就能概括整块图像。

时间轴

时间内容
0:07图像压缩与基变换
1:38基变换要回答的核心问题
3:02像素、无损压缩与信息量
3:28512×512512\times512 图像的数据量
6:52图像相邻像素高度相关
7:59第一个好基：全一向量
11:07JPEG 的基与 8×88\times8 分块
13:46换基、压缩、再换回
14:43有损压缩：丢弃小系数
17:26指纹图像的压缩故事
22:00小波基的构造
24:21用基的系数表示图像
28:46好基的两个要求：计算快、表示稀疏
30:54小波变换的快速算法
31:14小波基不是正交基
35:56矩阵在两组基下的关系
39:52AA 与 BB 相似
43:18变换在新基下的矩阵怎么求
47:08特征向量基使矩阵对角化

好基应该包含什么

最显然应该加入的，是全 11 向量：

(1,1,…,1).(1,1,\dots,1).

一个纯色图像只需要这一个方向加一个系数。它不在标准基里，但这正是换基的自由：基可以自己选。

第二类有用的向量是棋盘向量 (1,−1,1,−1,… )(1,-1,1,-1,\dots)，它描述高频交替；更常见的是半边亮半边暗的向量，例如前一半 11、后一半 −1-1。

这三类向量分别对应：常数（零频）、缓慢变化（低频）、快速交替（高频）。

选基是一个价值数十亿美元的工程决定。电视标准、电影标准、JPEG 标准背后，都是这个线性代数问题的不同答案。

JPEG 怎么做

分块

整张 512×512512\times512 图太大，JPEG 把它切成许多 8×88\times8 的小块，每块 6464 个像素。压缩在 6464 维空间里逐块进行。

第一步：换基（无损）

在每个块里，用傅里叶基（更准确说是离散余弦基）表示这 6464 个像素值：

x=Wc.x=Wc.

输入是 6464 个像素值，输出是 6464 个系数。这一步只是换了一组坐标，没有丢失任何信息。

傅里叶基包含常数向量（直流分量，DC），也包含各种频率的交替向量。

第二步：阈值化（有损）

自然图像的能量集中在低频：常数项和缓变项系数大，高频项系数小。于是设定一个阈值，把绝对值很小的系数直接置零：

c^=threshold(c).\hat c=\text{threshold}(c).

大多数高频系数被丢掉，留下少数几个。

第三步：重建

x^=Wc^.\hat x=W\hat c.

只保留两三个系数时，6464 维的块被压缩到 33 维左右，压缩比约 21:121:1。人眼几乎看不出差别，因为被丢掉的是图像里本来就很微弱的高频细节。

关键点：换基本身无损，压缩发生在阈值化。前者是线性代数，后者是利用「信号在好基下稀疏」这一经验事实。

指纹与视频

  • 指纹：FBI 的指纹库有数千万张卡片，数字化后每张仍是巨大的图像。压缩后建立索引，查询从「一周」缩短到「几分钟」。他们选择的基不是最简单的 Haar 小波，而是更平滑的小波。
  • 视频：相邻帧高度相关，编码时只记录「预测」和「修正量」，压缩修正量，而不是每帧独立压缩。这仍然是利用相关性，只是相关性出现在时间方向。

小波基

傅里叶基的竞争者是小波基。以 R8\mathbb R^8 为例，一组最简单的 Haar 小波基是：

(1,1,1,1,1,1,1,1),(1,1,1,1,−1,−1,−1,−1),(1,1,−1,−1,0,0,0,0),(0,0,0,0,1,1,−1,−1),(1,−1,0,0,0,0,0,0),(0,0,1,−1,0,0,0,0),(0,0,0,0,1,−1,0,0),(0,0,0,0,0,0,1,−1).\begin{aligned} &(1,1,1,1,1,1,1,1),\\ &(1,1,1,1,-1,-1,-1,-1),\\ &(1,1,-1,-1,0,0,0,0),\\ &(0,0,0,0,1,1,-1,-1),\\ &(1,-1,0,0,0,0,0,0),\\ &(0,0,1,-1,0,0,0,0),\\ &(0,0,0,0,1,-1,0,0),\\ &(0,0,0,0,0,0,1,-1). \end{aligned}

它们全部由 1,−1,01,-1,0 组成，乘法只需加减；它们两两正交。长度分别为 8,4,2,2,2,2,2,2\sqrt8,\sqrt4,\sqrt2,\sqrt2,\sqrt2,\sqrt2,\sqrt2,\sqrt2，归一化后就得到一组标准正交基。

与小波基的变换

把 88 个像素值排成向量 PP，小波基作为列组成矩阵 WW，则

P=Wc,c=W−1P.P=Wc,\qquad c=W^{-1}P.

因为 WW 的列正交，归一化后 W−1=WTW^{-1}=W^{\mathsf T}，变换与逆变换都只是矩阵乘法。

好基的三个标准

标准含义为什么重要
快正变换与逆变换都能快速计算图像数量巨大，慢一倍就不可接受
稀疏少数系数就能重建信号这是压缩率的来源
正交W−1=WTW^{-1}=W^{\mathsf T}逆变换和正变换一样快，数值稳定

傅里叶基满足三条：有 FFT，能量集中，且（复数版）正交。小波基同样满足：有快速小波变换，且正交。

最快的「基」其实是不换基——标准基本身不需要任何计算。但它在压缩上表现很差：丢掉 90%90\% 的像素，图像就直接变暗、损坏。速度与稀疏性要同时满足，缺一不可。

换基与相似矩阵

回到线性变换的语言。

设 TT 是 nn 维空间到自身的线性变换。在基 v1,…,vnv_1,\dots,v_n 下，它的矩阵是 AA；在另一组基 w1,…,wnw_1,\dots,w_n 下，矩阵是 BB。则

B=M−1AM,B=M^{-1}AM,

其中 MM 是换基矩阵，其列是新基向量在旧基下的坐标。

这就是「相似」的来源：同一个变换，不同基，矩阵相似。

特征向量基是最好的基

若基向量全部是特征向量，则

T(vi)=λivi.T(v_i)=\lambda_iv_i.

按构造规则，T(vi)T(v_i) 在基下的坐标只在第 ii 个位置非零，值为 λi\lambda_i。所以矩阵是对角矩阵

Λ=diag⁡(λ1,…,λn).\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n).

这就是为什么对角化如此重要：它把变换写成「每个方向独立拉伸」。

对图像压缩而言，特征向量基理论上最优，但求一个 5122512^2 维矩阵的特征向量代价太高。实际做法是选一个「足够好且算得快」的基，例如小波或傅里叶。

常见误区

  1. 以为换基会改变向量。向量本身不变，变的是它的坐标表示。
  2. 把压缩归因于换基。换基是无损的；压缩来自阈值化丢弃小系数。
  3. 只看压缩率，忽略速度。一个压缩率极高但变换极慢的基在工程上不可用。
  4. 以为所有正交基都一样好。正交只保证逆变换方便；稀疏性取决于信号与基的匹配程度。

本讲结论

  • 图像是高维向量，标准基没有利用像素间的相关性。
  • 好基的标准是：变换快、表示稀疏、最好正交。
  • JPEG 在 8×88\times8 块上用傅里叶（余弦）基，换基无损，阈值化有损。
  • 小波基是傅里叶的竞争者，JPEG 2000 采用小波。
  • 换基的矩阵语言是 P=WcP=Wc，c=W−1Pc=W^{-1}P。
  • 同一变换在不同基下的矩阵相似：B=M−1AMB=M^{-1}AM；特征向量基给出对角矩阵。

理解检验

1. 为什么标准基对「整块纯色」的图像效率很低？

参考答案：标准基的一个坐标方向对应单个像素，用标准基表示一块 8×88\times8 纯色图，需要 6464 个非零系数——每个像素一个，尽管它们的值几乎相同。纯色图真正的结构是一条方向上的一个振幅，即全 11 向量；这条方向不在标准基里，所以只能拆成大量坐标来拼。标准基没有利用「相邻像素高度相关」这一事实，因此系数个数无法减少，压缩也就无从谈起。

2. JPEG 的哪一步是无损的，哪一步是有损的？

参考答案：第一步换基 x=Wcx=Wc 是无损的：它只把 6464 个像素值重新表示成 6464 个傅里叶（余弦）系数，信息一一对应，c=W−1xc=W^{-1}x 可以精确还原。第二步阈值化 c^=threshold⁡(c)\hat c=\operatorname{threshold}(c) 是有损的：把绝对值很小的高频系数直接置零，这部分信息永久丢失。第三步重建 x^=Wc^\hat x=W\hat c 对保留下来的系数是精确的，但无法恢复被丢掉的系数。所以压缩发生在阈值化，「换基」本身不压缩。

3. 小波基为什么能同时做到「快」和「正交」？

参考答案：快，是因为 Haar 小波基的每个向量只由 1,−1,01,-1,0 组成，正变换与逆变换只需要加减法，不需要乘法；对长度为 nn 的信号，快速小波变换是 O(n)O(n) 的。正交，是因为这组向量两两内积为零，例如 (1,1,1,1,−1,−1,−1,−1)(1,1,1,1,-1,-1,-1,-1) 与 (1,1,−1,−1,0,0,0,0)(1,1,-1,-1,0,0,0,0) 的内积是 1+1−1−1=01+1-1-1=0；归一化后 W−1=WTW^{-1}=W^{\mathsf T}，逆变换与正变换同样快，且数值稳定。两个性质来自同一组 ±1\pm1 结构，所以能同时满足。

4. 一个基正交但不稀疏，会带来什么问题？

参考答案：正交保证逆变换容易（W−1=WTW^{-1}=W^{\mathsf T}）且数值稳定，但压缩率取决于「信号在这组基下有多少系数是小的」。若不稀疏，说明信号能量分散在很多系数上，阈值化会丢掉真正重要的信息，要么保留大量系数（压缩比低），要么重建误差明显。标准基就是极端例子：它正交，但对自然图像完全不稀疏，丢掉 90%90\% 的像素会让图像变暗、损坏。所以正交只是三个标准之一，不能代替稀疏性。

5. 若 B=M−1AMB=M^{-1}AM，MM 的列在新基下代表什么？

参考答案：MM 的列是新基向量在旧基下的坐标。设旧基为 v1,…,vnv_1,\dots,v_n，新基为 w1,…,wnw_1,\dots,w_n，则第 jj 列是 wjw_j 用旧基表示的系数向量。于是 MM 完成「新坐标 → 旧坐标」的转换：若 xnewx_{\text{new}} 是同一向量在新基下的坐标，则 xold=Mxnewx_{\text{old}}=Mx_{\text{new}}。相似公式 B=M−1AMB=M^{-1}AM 的含义就是：先用 MM 把新坐标翻译成旧坐标，用 AA 作用，再用 M−1M^{-1} 翻译回新坐标。

与前后课程的关系

上一讲说明了矩阵如何由基构造；这一讲把换基应用到压缩，并回到相似矩阵：同一个变换在不同基下的矩阵相似。下一讲是第三次测验复习，把特征值、对称矩阵、正定、相似与 SVD 串成一组典型题型。

An image is a very long vector

A 512×512512\times512 grayscale image has 5122=262144512^2=262144 pixels, each an integer from 00 to 255255, that is, eight bits. Laid out row by row, the image is a vector in R262144\mathbb R^{262144}. A color image needs three channels, tripling the length.

Compression starts here: the information is too large to transmit directly.

Why the standard basis is poor

The standard basis treats each pixel as its own coordinate direction. But natural images are highly correlated locally: across a blue shirt or a dark blackboard, neighboring values differ only slightly.

For a nearly uniform region, the standard basis still needs hundreds of nonzero coordinates, one per pixel. It ignores the very structure that makes compression possible.

Changing basis aims at a different representation in which a few coefficients summarize an entire block.

Timeline

TimeTopic
0:07Image compression and change of basis
1:38The central question of change of basis
3:02Pixels, lossless compression, information
3:28The data in a 512×512512\times512 image
6:52Neighbouring pixels are highly correlated
7:59The first good basis vector: all ones
11:07The JPEG basis and 8 by 8 blocks
13:46Change basis, compress, change back
14:43Lossy compression: discarding small coefficients
17:26The fingerprint compression story
22:00Constructing the wavelet basis
24:21Representing an image by basis coefficients
28:46A good basis must be fast and sparse
30:54The fast wavelet transform
31:14The wavelet basis is not orthonormal
35:56How a matrix relates under two bases
39:52AA and BB are similar
43:18Finding the matrix in the new basis
47:08An eigenvector basis diagonalizes the matrix

What a good basis should contain

The most obviously useful vector is the all-ones vector:

(1,1,…,1).(1,1,\dots,1).

A solid-color image needs only this direction and one coefficient. It is not in the standard basis — and that is exactly the freedom a change of basis gives.

The second useful family is the checkerboard vector (1,−1,1,−1,… )(1,-1,1,-1,\dots), describing rapid alternation. More common in real images is a half-light, half-dark vector, with 11 on one half and −1-1 on the other.

These correspond to constant (zero frequency), slow variation (low frequency), and rapid alternation (high frequency).

Choosing a basis is a billion-dollar engineering decision. Television standards, film standards, and JPEG all rest on different answers to this linear algebra question.

How JPEG works

Blocking

A full 512×512512\times512 image is too large to handle at once, so JPEG splits it into 8×88\times8 blocks of 6464 pixels and compresses each block in a 6464-dimensional space.

Step one: change basis (lossless)

Within a block, the 6464 pixel values are expressed in a Fourier (more precisely, discrete cosine) basis:

x=Wc.x=Wc.

Sixty-four pixels go in, sixty-four coefficients come out. This step only changes coordinates; no information is lost.

The Fourier basis includes the constant vector (the DC component) and vectors that alternate at various frequencies.

Step two: threshold (lossy)

Natural images concentrate energy at low frequencies: the constant and slowly varying coefficients are large, high-frequency coefficients are small. Set a threshold and zero out the small ones:

c^=threshold(c).\hat c=\text{threshold}(c).

Most high-frequency coefficients disappear.

Step three: reconstruct

x^=Wc^.\hat x=W\hat c.

With only two or three coefficients kept, a 6464-dimensional block is reduced to about three numbers — roughly 21:121:1 compression. The eye barely notices, because what was discarded was the faint high-frequency detail.

The key distinction: the change of basis is lossless; compression happens at thresholding. The first is linear algebra; the second exploits the empirical fact that signals are sparse in a good basis.

Fingerprints and video

  • Fingerprints: the FBI's archive held tens of millions of cards, and digitized images were still enormous. Compression made indexing feasible, cutting a query from a week to minutes. The basis chosen was not the simplest Haar wavelet but a smoother one.
  • Video: consecutive frames are highly correlated, so an encoder records a prediction plus a correction and compresses only the correction. The correlation is temporal instead of spatial.

The wavelet basis

The competitor to Fourier is the wavelet basis. In R8\mathbb R^8, one simple Haar wavelet basis is

(1,1,1,1,1,1,1,1),(1,1,1,1,−1,−1,−1,−1),(1,1,−1,−1,0,0,0,0),(0,0,0,0,1,1,−1,−1),(1,−1,0,0,0,0,0,0),(0,0,1,−1,0,0,0,0),(0,0,0,0,1,−1,0,0),(0,0,0,0,0,0,1,−1).\begin{aligned} &(1,1,1,1,1,1,1,1),\\ &(1,1,1,1,-1,-1,-1,-1),\\ &(1,1,-1,-1,0,0,0,0),\\ &(0,0,0,0,1,1,-1,-1),\\ &(1,-1,0,0,0,0,0,0),\\ &(0,0,1,-1,0,0,0,0),\\ &(0,0,0,0,1,-1,0,0),\\ &(0,0,0,0,0,0,1,-1). \end{aligned}

Every entry is 11, −1-1, or 00, so multiplication is just addition and subtraction. The vectors are pairwise orthogonal, with lengths 8,4,2,…,2\sqrt8,\sqrt4,\sqrt2,\dots,\sqrt2; normalizing gives an orthonormal basis.

Transforming with wavelets

Put the eight pixel values in a vector PP and the wavelet basis vectors in the columns of WW. Then

P=Wc,c=W−1P.P=Wc,\qquad c=W^{-1}P.

After normalization the columns are orthonormal, so W−1=WTW^{-1}=W^{\mathsf T}: the forward and inverse transforms are both just matrix multiplications.

Three tests for a good basis

TestMeaningWhy it matters
FastBoth transform and inverse are cheapImage volumes are enormous; twice as slow is unusable
SparseA few coefficients reconstruct the signalThis is where compression comes from
OrthogonalW−1=WTW^{-1}=W^{\mathsf T}The inverse is as fast as the forward transform, and numerically stable

Fourier passes all three: FFT, energy concentration, orthogonality (in the complex version). Wavelets pass as well: a fast wavelet transform and orthogonal columns.

The fastest "basis" is no change at all — the standard basis costs nothing. But it compresses badly: discard 90%90\% of the pixel values and the image darkens and breaks. Speed and sparsity are both required.

Change of basis and similar matrices

Return to linear transformations.

Let TT map an nn-dimensional space to itself. In the basis v1,…,vnv_1,\dots,v_n its matrix is AA; in another basis w1,…,wnw_1,\dots,w_n its matrix is BB. Then

B=M−1AM,B=M^{-1}AM,

where MM is the change-of-basis matrix whose columns are the new basis vectors expressed in the old basis.

This is the origin of similarity: one transformation, two bases, similar matrices.

The eigenvector basis is best

If every basis vector is an eigenvector, then

T(vi)=λivi.T(v_i)=\lambda_iv_i.

By the construction rule, the coordinates of T(vi)T(v_i) are zero except in position ii, where the value is λi\lambda_i. Hence the matrix is diagonal:

Λ=diag⁡(λ1,…,λn).\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n).

This is why diagonalization matters: it writes the transformation as independent stretching along each direction.

For image compression, the eigenvector basis would be optimal in theory, but finding eigenvectors of a 5122512^2-dimensional matrix is far too expensive. Practice chooses a basis that is good enough and fast, such as wavelets or Fourier.

Common mistakes

  1. Thinking a change of basis changes the vector. The vector is unchanged; only its coordinates change.
  2. Attributing compression to the change of basis. The basis change is lossless; compression comes from thresholding small coefficients.
  3. Ignoring speed in favor of compression ratio. A basis with a spectacular ratio but a slow transform is useless in practice.
  4. Assuming all orthogonal bases are equally good. Orthogonality makes inversion convenient; sparsity depends on how well the basis matches the signal.

Takeaways

  • An image is a high-dimensional vector, and the standard basis ignores local correlation.
  • A good basis is fast, sparse, and preferably orthogonal.
  • JPEG uses a Fourier (cosine) basis on 8×88\times8 blocks; the basis change is lossless and thresholding is lossy.
  • Wavelets compete with Fourier and are used in JPEG 2000.
  • The matrix form of a basis change is P=WcP=Wc, c=W−1Pc=W^{-1}P.
  • One transformation in two bases gives similar matrices B=M−1AMB=M^{-1}AM; the eigenvector basis gives a diagonal matrix.

Check your understanding

1. Why is the standard basis inefficient for an image that is a single solid color?

Reference answer: Each coordinate direction of the standard basis corresponds to a single pixel, so representing a solid 8×88\times8 block needs 6464 nonzero coefficients — one per pixel — even though the values are nearly identical. The real structure of a solid block is one amplitude along the all-ones direction; that direction is not in the standard basis, so it must be assembled from many coordinates. The standard basis ignores the strong correlation between neighbouring pixels, so the number of coefficients cannot shrink and compression has nothing to exploit.

2. Which JPEG step is lossless, and which is lossy?

Reference answer: The basis change x=Wcx=Wc is lossless: it merely rewrites the 6464 pixel values as 6464 Fourier (cosine) coefficients, and c=W−1xc=W^{-1}x recovers them exactly. Thresholding c^=threshold⁡(c)\hat c=\operatorname{threshold}(c) is lossy: coefficients with small magnitude are set to zero and that information is gone for good. Reconstruction x^=Wc^\hat x=W\hat c is exact for the retained coefficients, but cannot restore the discarded ones. Compression therefore happens in the thresholding step, not in the basis change.

3. Why can a wavelet basis be both fast and orthogonal?

Reference answer: Fast, because every Haar wavelet vector has entries in {1,−1,0}\{1,-1,0\}, so the forward and inverse transforms need only additions and subtractions — no multiplications — and the fast wavelet transform on a signal of length nn costs O(n)O(n). Orthogonal, because the vectors have pairwise zero inner products; for example (1,1,1,1,−1,−1,−1,−1)(1,1,1,1,-1,-1,-1,-1) and (1,1,−1,−1,0,0,0,0)(1,1,-1,-1,0,0,0,0) have inner product 1+1−1−1=01+1-1-1=0. After normalization W−1=WTW^{-1}=W^{\mathsf T}, so the inverse is as cheap as the forward transform and numerically stable. Both properties come from the same ±1\pm1 structure, which is why they hold together.

4. What goes wrong with a basis that is orthogonal but not sparse?

Reference answer: Orthogonality makes inversion easy (W−1=WTW^{-1}=W^{\mathsf T}) and numerically stable, but compression depends on how many coefficients are small. If the representation is not sparse, the signal's energy is spread over many coefficients: thresholding would discard genuinely important information, forcing you either to keep many coefficients (low compression) or to accept visible reconstruction error. The standard basis is the extreme case — orthogonal, yet completely non-sparse for natural images, so dropping 90%90\% of pixels darkens and damages the picture. Orthogonality is only one of the three criteria and cannot substitute for sparsity.

5. If B=M−1AMB=M^{-1}AM, what do the columns of MM represent in the new basis?

Reference answer: The columns of MM are the coordinates of the new basis vectors expressed in the old basis. If the old basis is v1,…,vnv_1,\dots,v_n and the new one is w1,…,wnw_1,\dots,w_n, column jj holds the coefficients of wjw_j in the old basis. Thus MM converts new coordinates to old ones: if xnewx_{\text{new}} holds the coordinates of a vector in the new basis, then xold=Mxnewx_{\text{old}}=Mx_{\text{new}}. The formula B=M−1AMB=M^{-1}AM says exactly this: translate new coordinates to old with MM, apply AA, and translate back with M−1M^{-1}.

How this connects to the course

The previous lecture showed how bases construct matrices; this one applies basis changes to compression and returns to similarity: one transformation, different bases, similar matrices. The next lecture is the third quiz review, tying eigenvalues, symmetric matrices, positive definiteness, similarity, and SVD into a set of typical problems.

来源