Question

Pixel 与 Image

一张电脑图片、一幅萤幕画面、一台电子跑马灯，都是由许多小光点组成，一个小光点就是一个“像素”、“画素”。大量的小光点排列整齐，宛如棋盘方格，构成一张“图片”。

小光点够小够密集，或者相对来说，小光点很远很渺小，那麽观看图片时，相邻的小光点将糊在一起，彷彿是柔顺平滑的图片。

电视机与相机经常强调画素与解析度。画素很高，意思是小光点很多；解析度很高，意思是小光点很密，使得图片清晰锐利。

Red, Green, Blue

电脑当中，以整数 0 到 255，代表小光点的亮度。0 是最暗，255 是最亮。256 种数值已经足够细腻，超越人类视觉对于亮度的辨别能力！

一个像素拥有三个数值，代表红光、绿光、蓝光的亮度；简称 RGB，红绿蓝的首字母。

三色光叠合，得到各种颜色。RGB 都是 255，叠合之后就是白光、呈现白色。RGB 都是 0，就是无光、呈现黑色。RGB 都一样，则呈现灰色。RGB 不一样，则呈现各式各样的彩色。

第一张图片是范例图片；第二张图片是保留 R 值（G 值与 B 值设定为 0）；第三张图片是保留 G 值；第四张图片是保留 B 值。右边三张图片的对应像素相加之后，就会形成左图。

举例来说
第二张图片裡面，某一个像素的颜色 (255,   0,   0)
第三张图片裡面，对应的像素的颜色 (  0, 123,   0)
第四张图片裡面，对应的像素的颜色 (  0,   0, 247)
这三张图片相加起来，得到第一张图片裡面，对应的像素的颜色
(255, 0, 0) + (0, 123, 0) + (0, 0, 247) = (255, 123, 247)

熟悉数学的读者，可以把“RGB 值相加”想做是“向量相加”。
但是“RGB 值相加”与“向量相加”，两者背后的原理完全不相干，切莫搞混。

Alpha

有些图片额外增加一个数值，代表透明程度；简称 A，alpha 的首字母。

0 是完全透明、呈现背景底色；255 是完全不透明、呈现图片原色；其馀数值则按比例混合图片颜色与背景底色。

左图所有像素的 A 值都是 255，完全不透明，看不到网页背景的颜色；中图所有像素的 A 值是 127，透明的程度是 50%，看得到一点网页背景的颜色；右图中央 A 值高、外围 A 值低。

举例来说
图片裡面有一个像素的颜色 (255, 123,  10)，透明程度 34
背景裡面对应的像素的颜色 (  0,   0, 255)

按比例混合（加权平均）（线性内插），得到显示的颜色
  (255, 123, 10) * 34/256   +   (0, 0, 255) * 222/256
= (255*34/256, 123*34/256, 10*34/256 + 255*222/256)

由于 RGB 值必须是整数，所以计算结果必须再取 floor/ceil/round。

Image 的资料结构

图片的资料结构，一般是二维阵列，一个元素储存三个数字 RGB，或者储存四个数字 RGBA。

注意到：存取矩阵元素、存取图片像素，行列次序刚好颠倒。套用图片函式库时，要尤其小心。

UVa 706 10267

使用 C/C++处理图片

C 与 C++本身没有处理图片的函式库。

你可以土法炼钢，参考 BMP、JPEG、PNG 的规格书，自己写程式读取图片撷取像素；然后利用 Windows API 、 Linux 视窗介面的工具 、Cocoa，自己写程式把图片像素画在萤幕上。

你也可以拍手炼成，直接使用现成的函式库，例如 OpenCV 、 CImg ，都是不错的选择。

这是我设计的练习题目 。

使用 Qt/C#/Java 处理图片

这些语言处理图片的方式都大同小异。首先建立一个图片物件（Qt 的 QImage、C#的 Image、Java 的 Image 与 ImageIO），然后建立一个视窗，覆写视窗的重绘函式，取其绘图物件（Qt 的 QPaint、C#的 Graphics、Java 的 Graphics），把图片画在视窗当中。

使用 Python 处理图片

Python 本身没有处理图片的函式库，必须另行安装。

知名函式库是 pillow ，容易上手。

使用 HTML 与 JavaScript 处理图片

http://www.w3schools.com/tags/canvas_drawimage.asp

将图片画在网页上，只消几行程式码。首先在 HTML 当中，建立一个<img>以及一个<canvas>。然后在 JavaScript 当中，利用 drawImage() 将<img>的图片画在<canvas>上面。

也可以利用 createElement()，动态建立<img>与<canvas>。图片的部分，也可以利用 Image() 建构子，动态建立<img>。

我们无法直接从<img>得到像素。必须先将<img>的图片画在<canvas>上面，再利用 getImageData() 得到像素。其成员.data 是一条一维阵列，依序存放每个像素的 RGBA 值。

修改好每个像素的数值之后，最后利用 putImageData() 将像素画在<canvas>上面，便大功告成了。

想要宣告像素，可以利用 createImageData()。想要拷贝像素，可以直接拷贝阵列。

学会撷取像素之后，就能做一些简单的实验了，例如颠倒色彩（255 减掉原本的数值）、彩色变灰阶（RGB 相加除以三）、失焦模糊（取邻近像素求平均值）。

甚至可以即时处理影片。影片可以想成是很多张图片组成的。

使用 Photoshop/GIMP 处理图片

Image 的演算法，早已经制作成套装软体。商业软体，例如 Adobe Photoshop ；开源软体，例如 GIMP ；台湾人自制的软体，例如 PhotoCap 与 Ulead PhotoImpact ，都是不错的选择。

只要发挥创意，就能做出各种图片特效。完全不需要学习程式语言与数学，只需要仔细阅读软体使用说明书。

Color（Under Construction!）

Color

一道光包含许多个 波 。人类看见一道光，却只感受到一种 色 。

从光到色的机制尚未釐清。目前只知道：一、人类视觉无法解析每一个波，只能感受混和结果。二、不同的光（不同的波的组合），可以是相同的色。彷彿数学术语“投影”。

波有两个要素：振幅、频率。一道光的成分，可以画成频谱：横轴是频率，纵轴是振幅，一个峰是一个波。

振幅平方，决定 光能 ；频率，决定 色相 。混和数种光能的宏观感受，称作 亮度 ；混和数种色相的宏观感受，称作 彩度 。

这只是简易解释，人类视觉机制并非如此单纯。亮度和彩度会互相干涉，不能分开讨论。

人眼拥有四种感光细胞，可以感知频率和振幅。其中一种无法转换成彩度，属于夜视能力，此处不讨论。

工程师设计实验，制造各种频率、各种振幅的简谐波，请民众辨别亮度和彩度。最后以统计学来估计三种感光细胞的感光程度。感光程度偏高之处，是红绿蓝三色。

理应取得感光细胞进行生物实验，不过至今无人这样做。

Color Space

色彩空间 。人类视觉所能感知的所有颜色，化作数值。

CIE RGB ：模仿人眼机制，以三个波，固定频率（红绿蓝），调整光强，得到一种色，令其数值是光强比例。然而三种单色光，也少于人类所能分辨的色，于是数值有时是负数，模拟那些色，彷彿数学术语“外插”。

工程师假设：三种感光细胞的三个刺激量，决定了色。一个刺激量是每种频率的光强乘以感光程度之后求和（点积）。以实验数据反推感光程度，感光程度有时是负数。虽然这个数学模型完全不符合人眼机制，但是方便设计电路、方便计算。

CIE XYZ ：调整成非负数。

CIE L*a*b* ：数值差距等于颜色差距。

Color Model

色彩模型 。数值与颜色的对应方式，通常只对应到人类视觉所能感知的一部分颜色。数值格式符合人类作业需求。

RGB ：红绿蓝，萤幕。光的三原色。用于电脑萤幕。

CMYK ：青洋红黄黑，颜料的三原色，外加黑色。用于印刷。

HSL 和 HSV ：色相、饱和度、亮度。用于电脑美术。

YUV ：类比视讯。其中 YCbCr 用于 JPEG 压缩。

Color Palette

色盘 。记录一张图片有哪些颜色。

Color Grading

简介

调整像素的数值。

图片的数学运算：Function

新旧图片，新旧像素值的对应关係，是函数。RGB 分开处理，是三个函数。

identical：45°斜线。保持不变。

inverse：翻转 45°斜线，255-x，亮暗颠倒。传统相机的负片，具备此特性。

gamma correction ：模拟人脑依据环境调整亮度。人脑会根据环境亮暗，自动将极亮变暗、极暗变亮。数位相机的硬体，内建此功能。

图片的数学运算：Histogram

RGB 分开处理，得到 RGB 三个直方图。一张图片，像素值（亮度）仅 256 种，分别统计 0 到 255 的出现次数，得到直方图。甚至再除以总次数，得到机率密度函数 PDF。

先前透过函数，订立新旧亮度的对应关係：每种旧亮度，对应每种新亮度。现在透过直方图，订立新旧亮度的对应关係：旧直方图，对应新直方图。

histogram equalization ：调整直方图间距。两两相邻亮度，旧亮度的出现次数相差越多，新亮度相差越多，成正比。预先计算出现次数的前缀和（甚至再除以总次数，得到累积分布函数 CDF），方便计算新亮度。实际应用：在亮者恆亮、暗者恆暗的前提下，让亮暗层次更分明。

histogram matching ：以 CDF 来建立新旧亮度的对应关係。实际应用：一张图片，求出 CDF；自订另一个 CDF，以自由调整新亮度。

histogram comparison ：求出两个直方图的差距，以判断图片相似程度。方法很多。

Image Thresholding

门槛化 。区分像素数值大小，依照大小分别处理。可以进一步制造 黑白化（二值化） 、 单色化 等效果。

binary thresholding ：自订临界值。大于临界值、小于临界值，实施不同处理。

Otsu's thresholding ：穷举临界值，找到最佳临界值。大于临界值为前景，小于临界值为背景，求前景 PDF、背景 PDF，求前景变异数、背景变异数相加最小者。

Color Reduction（Color Quantization）

删减 。减少颜色种类，让图片依然清楚。每个颜色重新设定颜色；把不同的颜色，重新设定成相同的颜色。

令压缩图片的效果更好、传递图片的速度更快。另外，当颜色种类很少，可塑造特殊风格，例如 色调分离 、 色带 等效果。

左图是原图，中图是只有 256 种颜色的图，右图是选中的 256 种颜色。

k-means clustering ：要几种颜色就分几群。形成 Voronoi Diagram，各群中心是新颜色。

median cut ：所有像素置于 RGB 三维空间。反覆分割空间，不断取宽度（或体积）最大的区块，从最宽的那一个维度、从中位数分割。如果原图片要降低为 256 种颜色，就切出 256 个区块。区块内所有像素，新颜色一律是平均值。

Color Dithering

颤化 。减少颜色种类，让图片观感与原先相仿。每个像素依序重新设定颜色；每个像素的先后颜色误差，分摊给邻近的像素。

dithering 是 印刷 和 液晶显示 的重要技术。报纸上的图片就用了 dithering，用少量的单调颜色，调合出原本颜色；在原本像素的周围点上单调颜色，宏观望去宛如原本颜色。

左图是原图，中图是先转灰阶再处理，右图是 RGB 三个值分开处理。新颜色只有两种，要嘛是 255、要嘛是 0。

Floyd-Steinberg dithering ：先后误差的 7/16 传给右、3/16 给左下、5/16 给下、1/16 给右下。所有像素依行列顺序处理，具有递推效果，一传十十传百。

Color Halftoning（Color Stippling）

半色调化 。仅使用基本原色，让图片观感与原先相仿。以墨水点的尺寸、间距、数量，取代像素值。

AM halftoning：墨水点尺寸不同、间距相同。像素值越高越亮，墨水点越小越淡。

FM halftoning：墨水点尺寸相同、间距不同。像素值越高越亮，墨水点越散越淡。

Color Correction

校正 。重新著色，呈现真实颜色，不受色彩模型影响。

校准 。重新著色，呈现真实颜色，不受摄影设备、显示设备影响；同时求出设备的影响力。

平衡 。著重于亮度，为了更加清晰。比方来说，室内用传统灯泡，白纸会泛黄；室内用日光灯，白纸会泛蓝。白纸理当是白色，以白纸为基准，重新调整图片当中每一种颜色，移除灯光造成的影响，还原成理想颜色。亦称“白平衡”。

调色（调光） 。著重于色调，为了改变风格。制片必备绝技，属于美术设计师、调光师的专业。

Color Harmonization

调和 。重新著色，视觉上和谐。

Color to Grayscale

彩色转灰阶 。重新著成灰色，让图片依然清楚。

简易的方式是把每一种颜色的 RGB 值更改为平均亮度：floor((R+G+B)/3)。缺点是无法区分平均亮度相同的颜色。当人生是黑白的时候，可能会看到不一样的景色。

另外还有很多 简易的方式 。至于 高竿的方式 ，是採用其他的色彩模型，例如将 RGB 转换成 CIE L*a*b* 或者 HSV 等等，根据人类擅于感受的亮度及彩度，决定灰色深浅。

Grayscale to Color（Colorization）

灰阶转彩色 。重新著成彩色，让图片依然清楚。

高竿的方法 请读者自行参考。一些古老的电视剧、影剧作品，就是如此重新上色的。又例如医学影像，利用超音波观察腹中胎儿，只能得到密度资讯，不能得到色彩资讯。密度资讯顶多只能转换成灰阶图片，所以我们看到的超音波影像大多是灰色的。我们可以利用灰阶转彩色的演算法，将图片上色，以便清楚地看到胎儿，方便医生诊视。

灰阶转彩色不是电脑专用的技术。在水墨画当中，也有先上墨色、再上彩色的作画技巧。

Image Filtering

简介

调整像素的数值，依据邻近像素的数值。

图片的数学运算：2D Convolution

一张图片，可以表示成 RGB 三个阵列，三个阵列分开处理。教科书则是表示成 RGB 三个函数。

图片具有地域性，邻近像素关係匪浅。邻近像素的平均值、相差值（梯度），各有功效。这些计算，可以统一成加权平均值，又可以统一成点积：对应项相乘，加总。

一种位移量、一次点积，得到一个新像素。穷举各种位移量、一一点积，即摺积，得到新图片。时间複杂度为 O(XYMN)。

【注： 摺积 规定其中一条数列必须头尾颠倒；方便起见，此处不颠倒图片和滤波器。】

超过图片边界时， 有许多种应对方式 ，例如不计算、补零、複制边界数值、线性内插。旁枝末节，不重要。

先算横条，再垂直整合，一如 区域总和 、 区域最小值 的计算手法，时间複杂度降为 O(XY(M+N))，但是需要大量额外空间。

空域循环摺积，就是频域乘法。时间複杂度降为 O(XYlogXY + MNlogMN)。然而滤波器通常很小，不必大费周章、弄巧成拙。

设计滤波器、套用滤波器， 便能制造各种图片特效 。亦得在特定区域之内套用滤波器，而不是整张图片都套用滤波器。

滤波器是线性的。倍率性：一个滤波器（的每个值）乘上倍率，等于新图片（的每个像素）乘上倍率。加法性：两个滤波器相加减，等于两张新图片相加减。想要揉合多张新图片，可以预先揉合滤波器，降低计算量。

新图片像素数值必须介于 0 到 255，须 normalization。

Image Smoothing（Image Blurring）

平滑化 、 雾化 。消灭边缘。失焦模糊。可以进一步制造 动态模糊 、 去噪 、 抗锯齿 、 打马赛克 等效果。

人眼感知到的平滑，就是亮度暨彩度相差很少。相邻像素取平均值，让彼此数值更接近、更平滑。

mean filter：平均值，矩阵所有数值设定为 1/NM。

Gaussian filter ：矩阵是一个二维常态分布。 有高速算法 。

bilateral filter ：当像素数值差距太大，就尽量不列入平均值计算，以保留形状边缘。不是摺积，无法直接转至频域计算， 另有高速算法 。

median filter ：原本数值替换为邻近数值们的中位数，可移除脉衝。不是摺积，无法直接转至频域计算， 另有高速算法 。

Image Edge Detection

边缘侦测 。产生边缘。得到形状边缘。可以进一步制造 边缘强化（锐化） 、 镂空 等效果。

人眼感知到的边缘，就是亮度暨彩度相差很多。相邻像素取差值，差值较大的地方就是边缘。

gradient filter ：X 轴、Y 轴分别一次偏微分。即是梯度。

Sobel filter ：gradient filter 补强中央数值，让边缘更明显。

Laplacian filter ：X 轴、Y 轴分别二次偏微分，然后相加。即是梯度的散度。

Image Template Matching

匹配 。给定图片片段，找到正确位置。概念等同 字串匹配 。

完全相等：穷举所有位移量；针对每一种位移量，对应位置判断相等后求 AND。缺点是像素数值不准有一丁点误差。

平方误差 最小：对应位置相减平方后求和。

相关係数 最大：对应位置相乘后求和（即摺积）。凭感觉瞎搞，但是算得快。图片预先锐化、图片预先保留高频，结果较佳。

Chamfer distance 最小：特色是比对边缘，而且边缘形状不必完全相同。图片与片段，预先求得边缘、二值化（边缘为 1，非边缘为 0）。图片求 distance map。套用相关係数最大的演算法。

图片的数学运算：Mathematical Morphology

图片视作三个函数，以 数学形态学 调整函数形状，例如 dilation 令亮处扩散黏结、erosion 令暗处扩散黏结。亦可先求梯度再处理。

Image Warping（Under Construction!）

简介

调整像素的位置。

图片的数学运算：Geometric Transformation

订立每个像素的新座标，或者只订立每个像素的移动方向，然后移动像素。这麽做可以营造一些图片特效。

一一设定每个像素，实在太累人。我们可以直接运用优美的数学工具，运用 几何变换 ，一口气移动所有像素。 计算几何 与 线性代数 谈过线性的几何变换，例如平移、缩放、旋转、镜射。

正向处理（直接法）：穷举原图片每个像素的座标，一一变换，得到新座标。新座标四捨五入，让像素座标是整数。然而，有些地方密集重叠、有些地方稀疏留白，无法构成图片。这种方式行不通。

逆向处理（试误法）：穷举新图片每个像素的座标，一一逆向变换，得到原座标。实施 二维内插 ，例如 近邻内插（恰为四捨五入） 、 双线性内插 、 sinc 内插 ，求得理想的像素数值。

Image Scaling（Image Resizing）

缩放 。调整图片尺寸。可以进一步制造 Depixelation 的效果。

Image Rotation

旋转 。除了内插，亦得 用 shear 达成图片旋转 ，避免误差。

图片的数学运算：Weighted Average Coordinates

移动像素亦可运用 加权平均座标系统 。钉选几个对应点，就能在原图片与新图片上面订立座标系统，立即完成每个像素的座标对应关係。

三角形内插：

四边形内插：

Image Warping

扭曲 。扭曲外形。可以进一步制造 验证 的效果。

function-based warping：制定一个函数，二维到二维，输入是像素原始位置，输出是像素移动目的地。

feature-based warping ：标记数条对应线段，以线段长度、点线距离，做为内插比重。特色是容易操作。

mesh warping ：手动或者 自动 建立网格，网格顶点是控制点。原图片网格呈整齐等分，新图片网格供用户调整。隐藏原图片暨网格，显示新图片暨网格。对应网格实施 座标内插 。

Image Deformation

形变 。保持架构，扭曲外形。

Image Morphing

变形 。从一个外形变化为另一个外形。可以进一步制造 美化 、变脸、 补帧 的效果。

标记数个对应点，符合五官特徵、四肢关节。

像素位置逐步变化，仅改变形状。warping。

像素数值逐步变化，仅淡入淡出。cross dissolving。

像素位置、像素数值一齐逐步变化，达成变形的效果！morphing = warping + cross dissolving。

变形就是两张图做内插，像素位置、像素数值都要内插。

Image Editing（Under Construction!）

简介

Image Compositing

合成 。两张图片相叠覆盖，成为一张图片。

copy-and-paste：直接覆盖。建议先去背。弄得好是 剪贴艺术 、 拼贴艺术 。

Image Segmentation

分割 。区隔景物，找到边界。

gradient：求梯度、订立临界值。

watershed transform ：区域极小值分别注水。相连水域，推定为相同景物。高速算法是四元树，求每块区域的平均值与变异数。分割过程中，当变异数太高则分割区域。分割结束后，当平均值相近则合併区域。

curvature flow ：手动圈景物，手绘曲线沿曲率方向移动，不断缩小范围，遇到梯度较大处则停止。效果等同前者，特色是会动。 甚至考虑张力和拉力 ，透过 regularization 併入最佳化对象，控制手绘曲线的大小和形状。

GrabCut ：手动圈景物，求 最小割 。像素之间的权重：梯度绝对值倒数。源点（汇点）到像素的权重：前景（背景）像素理想值与实际值的差距的倒数。倒数通常改成高斯分布或者左右翻转的 sigmoid，以避免倒数趋近无限大。

手动划记：一、手动划记前景与背景。前景划记处求 PDF，背景划记处求 PDF。二、图片每个像素，区分前景与背景，根据 PDF 机率大小。然而前景与背景不一定连通。三、图片每个像素，重新区分前景与背景，根据最短路径长度。分别找到每个像素到前景划记处、背景划记处的最短路径，点是像素，边是八方向，边的权重分别是前景 PDF 机率差、背景 PDF 机率差。前景与背景多半会连通。四、于边界两旁，分别撷取前景与背景的像素，做为新的划记。反覆执行演算法，直到边界收敛。

Image Blending

合成 。两张图片相叠揉合，成为一张图片。可以进一步制造 脸部剪接 的效果。

compositing 和 blending 都是合成，但是有点差别。compositing 是聚合，拼凑在一起。blending 是融合，掺杂在一起。运用 blending 得以制做自然美观的 compositing。

alpha blending ：RGB 加权平均。鬼影。

pyramid blending：两图分别求 Laplacian pyramid，每层分别拼接，最后叠合还原。

Poisson blending ：新图梯度，儘量等于底图梯度（或者儘量等于两图梯度较大者）。左右两式相减平方最小，就是左右两式一次微分相等；纵向与横向加总，就是左右两式散度相等。新图梯度与底图梯度的平方误差最小，就是梯度的散度相等，此即微分方程经典公式 Poisson equation。 化做线性方程组求解 ， 亦有频域的高速算法（限矩形区域） 。

Image Matting

去背 。保留主角，去除背景。区隔景物，找到边界。可以进一步制造 替换背景 的效果。

segmentation 与 matting 都是区隔景物，但是有点差别。segmentation 著重大体，matting 著重细部。

有人认为 blending 与 matting 互为反运算。blending 是叠合两张图片，matting 是剥离两张图片。

blue screen matting：主角背后放个蓝幕或蓝牆壁进行拍摄，图片中的蓝色就是背景。俗搁有力，又快又准。摄影棚必备道具。

Bayesian matting：

Poisson matting：求梯度。

Image Inpainting

修补 。填补缺漏像素。可以进一步制造擦拭边缘的效果。

smoothing ：依照行列顺序，逐一填补像素。取得已知的邻近像素，求亮度平均值（平滑化），甚至採用其他的平滑化滤波器。缺点是平滑化所带来的模糊化、边缘偏移、误差累进。

fluid dynamics ：周界往内推进，逐一填补像素。周界像素视作粒子，沿著梯度的垂直方向移动（沿著边缘移动），速度是二阶微分。可表示成偏微分方程 PDE。详细内容是个谜！

fast marching ：周界往内推进，逐一填补像素。填补顺序是自创的最短距离，填补数值是自创的加权平均值。 缺点是边缘破损 。

填补顺序。周界为起点，求周界到内部像素们的最短距离。 label setting algorithm ，像素视作节点。最短路径分两类：由正上/正下/正左/正右走来，距离加一；由上左/上右/下右/下左走来，距离如下图。

填补数值。针对一个已知邻点，其亮度加梯度（取出朝向填补点的分量，求其长度），是填补点理论上的亮度。针对所有已知邻点，个别求出理论上的亮度，再求加权平均值，权重是 这三项相乘 ：

一、修补后的周界的法线（即最短距离的梯度），取出朝向像素的分量，求其长度。二、邻点与填补点，二维直线距离的倒数。三、邻点与填补点，前述最短距离的差的倒数。

Image Completion

补全 。填补大片缺漏像素，重塑景物。可以进一步制造 填充纹理 的效果。

data-driven ：从资料库找到最相像的图片，剪接上去。Image Retrieval 检索，Image Matching 匹配，Image Blending 合成。

Image Retargeting

重新定位。缩小图片长宽，裁剪多馀像素，但是保留景物原本形状。

seam carving ：屡次删除不穿过边缘的路径，路径以纵向或横向跨越图片，使得图片长或宽屡次减一。使用动态规划或大量随机散步，找到一条梯度绝对值总和最小的路径。梯度可换成 Sobel、Canny。

Image Recomposition（Image Reshuffling）

重新合成 。移动景物位置，无缝接轨。

Image Painting（Under Construction!）

简介

Texture Generation

纹理生成 。制造纹理。

noise ：乱数产生纹理，内插产生绵延感。

Texture Synthesis

纹理生成 。延展纹理，由窄变广。

Voronoi diagram ：素材随机取出片段，随机散佈，相邻素材片段的中央地带求加权平均。 程式范例 。

image quilting ：素材随机取出方格，整齐拼接，部分交叠，交叠处误差尽量小。误差可定义为：所有对应像素误差总和、最小割（平面图最小割即最短路径）。

discrete element textures ：

stroke pattern ：

Texture Transfer

纹理转印 。拼接纹理，构成图形，宛如拓印。

image quilting ：纹理与新图片交叠处的误差（最小割），纹理与原图片的匹配误差，两者加权平均值最小。

Image Abstraction

抽象化 。保留图片大致的轮廓、大致的色调。

Image Stylization

风格化 。重新绘制图片，呈现 特殊风格 。已有 彙整书籍 、 彙整文章 。

Hertzmann's Algorithm ：画线。每个像素大致朝著相同方向移动一段距离，沿途不断贴上。调整笔画粗细、下笔间距，可以营造印象派画风。亦得沿梯度的垂直方向移动，遇到边缘就停住，让边缘明显。画笔与像素，颜色差异太大就停住。 算法在此 。

Image Analogy

类比 。撷取两图之间的风格差异，套用至其他图片。

Hertzmann's Algorithm ：

convolutional neural network ：

Image Understanding（Under Construction!）

简介

图片的特殊武器：Pyramid

人眼有著观（失焦、视野广）看（对焦、视野窄）的差别。由观到看、由看到观的过程当中，人脑似乎能够快速撷取图片特点。

一种模拟的方式是：图片分别套用各种宽度的 mean filter。换句话说：图片缩放成各种尺寸，套用相同宽度的 mean filter。

mean pyramid ：图片长宽屡次缩小一半，得到许多张图片，形成金字塔。缩小时，每四个像素合併成一个像素（田变口），取平均值。此步骤即 mean filter，具有模糊化效果，彷彿人眼失焦。

Gaussian pyramid ：缩小时改採 Gaussian filter，消灭边缘。

Laplacian pyramid ：缩小时改採 Laplacian filter，强调边缘。

图片的特殊武器：Blob

针对人类视觉系统的特性，撷取图片引人注目的地方。

Laplacian of Gaussian filter (LoG filter) ：先做 Gaussian filter，再做 Laplacian filter。先去噪，再求边缘，效果更佳。

difference of Gaussian filter (DoG filter) ：LoG filter 的高速近似算法。两个 Gaussian filter，平均值相同、变异数为 0.3 和 1.0，相减之后恰好近似 Laplacian filter。

Laplacian of Gaussians (LoG) ：图片套用各种宽度（变异数）的 LoG filter。针对一种宽度，找到区域极大值，推定为图片重点，重点的半径范围是 LoG filter 的变异数。

difference of Gaussians (DoG) ：LoG 的高速近似算法。改为套用各种宽度的 DoG filter。换句话说，图片缩放成各种尺寸，套用同样宽度的 DoG filter。换句话说，Gaussian pyramid，从中选择尺寸足够大的图片来缩小（因为放大会失真），以得到各种尺寸的图片；宽度最接近的两两图片，直接相减。【尚待确认：直接相减】

图片的特殊武器：椭圆形 Blob

引人注目的地方，莫名其妙是圆形。由于尺寸、形状皆不够精准，所以调整成椭圆形。不过还是很莫名其妙。

automatic scale selection：调整 blob 尺寸。一、找到一个 blob 之后，微调 blob 尺寸。二、计算 blob 裡面（或者周围）所有像素的梯度的长度的平均值。三、平均值依照 blob 尺寸排列，形成一串数列。四、区域极大值所在之处，表示梯度变化最大，推定为正确尺寸。当区域极大值不只一个，推定 blob 不存在。

高速近似算法：一、各种宽度的 blob，改成各种尺寸的图片（实务：边长屡乘 0.7 倍）。二、微调 blob 尺寸，改为尺寸相邻的两张图片的线性内插（实务：微调范围是该图的 0.7 至 1.4 倍，自行设定间距）。三、统计 blob 内部的梯度平均值，改为撷取 blob 中心的 DoG 值。四、简单一句话归纳：长、宽、缩放尺寸，在三维空间中求得 DoG 区域最小值。

affine shape adaptation：调整 blob 形状。取得 blob 内的像素，求得 二次动差矩阵 总和，实施 特徵分解 ，得到椭圆形，设为新 blob。重複上述动作，直至 blob 形状不变。

另类观点：取得 blob 内的像素。一个像素的 X 梯度、Y 梯度，视作一个二维座标点；所有像素的 X 梯度、Y 梯度，视作一群二维座标点。计算 principal component analysis（不必预先减去平均值），得到椭圆形。

Ix(x,y) = I(x,y) - I(x-1,y) = x gradient at (x,y)
Iy(x,y) = I(x,y) - I(x,y-1) = y gradient at (x,y)

P = [ Ix(x,y) Ix(x,y+1) Ix(x,y+2) ... Ix(x+1,y) Ix(x+1,y+1) ... ]
    [ Iy(x,y) Iy(x,y+1) Iy(x,y+2) ... Iy(x+1,y) Iy(x+1,y+1) ... ]

PᵀP = [ ∑IxIx ∑IyIx ] = ∑C(x,y) 
      [ ∑IxIy ∑IyIy ]

C(x,y) = [ IxIx IyIx ] = second monent matrix = structure tensor
         [ IxIy IyIy ]

Image Feature Detection

特徵侦测 。找到图片所含有的特殊结构、边边角角。

Hessian keypoint detection ：侦测顶点、端点、临界点。一、求每个像素的 det(Hessian matrix)。二、由于综合了 X 梯度与 Y 梯度，因此数值偏高者，多半为顶点、端点、临界点。

I(x,y) = R/G/B pixel value at (x,y)
Ix(x,y) = I(x,y) - I(x-1,y) = x gradient at (x,y)
Iy(x,y) = I(x,y) - I(x,y-1) = y gradient at (x,y)
Ixy(x,y) = Ix(x,y) - Ix(x,y-1)
         = [I(x,y) - I(x-1,y)] - [I(x,y-1) - I(x-1,y-1)]
         = y gradient of x gradient at (x,y)

     ∂I          ∂²I    
Ix = ――   Ixy = ―――――   H = [ Ixx Iyx ]   det(H) = Ixx Iyy - Ixy Iyx
     ∂x         ∂x ∂y       [ Ixy Iyy ]          = Ixx Iyy - (Ixy)²

Harris corner detection ：侦测角。一、撷取一块区域，求梯度。二、套用窗函数 Gaussian window，专注于区域中心附近的梯度。三、求得二次动差矩阵总和，实施特徵分解，以两个特徵值的绝对值大小，判断该区域是否有角。两值都足够大，就表示梯度们有两个主要方向，就表示有两条较直的边缘，就表示有角。四、高速算法是改用 det 和 trace 来判断。五、为何不採用 independent component analysis，而是用 principal component analysis？我也不知道。

Canny edge detection ：侦测边缘。一、平滑兼去噪：Gaussian filter。二、求边缘：求得梯度长度、梯度方向。三、找到最明显的边缘：若梯度长度为区域极大值，则保留，否则设为零。区域极大值是依照梯度方向取得前后两个像素，仅三个像素比较梯度长度。四、清除不明显的边缘：设定门槛，梯度长度太短者设为零。五、衔接边缘。

Hough line transform ：侦测直线，甚至侦测线段。一、求边缘：求得梯度长度，设定门槛。二、针对一个像素(x,y)，穷举穿过此像素的直线们，求得原点在直线上的投影点，再换成极座标表示法(r,θ)，一条直线对应一个点，直线们对应一条曲线 r = xcosθ + ysinθ。一个像素得到一条曲线。三、图片每个像素皆换成曲线。曲线们的交点，即是穿过大量像素的直线！四、建立细腻方格纸（离散化），曲线穿过方格，则投票加一，得票多的方格当作交点。

Hough cycle transform ：侦测圆。穷举各种半径。针对一个像素(x,y)，穷举穿过此像素的所有圆；圆穿过像素，则投票加一，得票多的像素就是圆心。

UVa 12599

Image Feature Detection 再进化

例如 corner，只有位移不变、旋转不变。现在还要缩放不变。方法是把 corner 补强为椭圆形 blob。

Harris affine region detector ：图片缩放成各种尺寸，每张图都找 corner。每一个 corner，以自己为中心，尝试找椭圆形 blob。

Hessian affine region detector ：找 corner 改为找 keypoint，其馀相同。

maximally stable extremal regions ：

Kadir-Brady saliency detector ：

Image Feature Description

特徵描述 。将图片独特之处写成数值，以供辨识比对。

histograms of oriented gradients (HOG) ：一个像素进行投票，梯度长度是持票数，梯度角度（无视正反方向，仅 0°到 180°）决定投票箱编号。180°等分成 9 个箱子。一个像素投票给最邻近的两个箱子，与箱子中心的距离（角度差）做为投票比例。

图片分解成大量 16×16 区域，交叠一半。一个区域 256 个像素实施投票，得到 9 个数字，RGB 分开就是 9×3 个数字。一个区域的数字，依序串成一串，当作特徵描述。

scale-invariant feature transform (SIFT) ：一个像素进行投票，梯度长度是持票数，梯度角度决定投票箱编号。360°等分成 8 个箱子。一个像素投票给一个箱子。

实施 Harris affine region detector，得到大量区域。针对一个区域，切成 4×4 宫格，一个宫格所有像素实施投票，得到 8 个数字，所有宫格就是 4×4×8=128 个数字，RGB 分开就是 128×3 个数字。一个区域的数字，依序串成一串，当作特徵描述。

speeded up robust features (SURF)：SIFT 的高速算法。

BRIEF – Binary Robust Independent Elementary Features
BRISK – Binary Robust Invariant Scalable Keypoints
ORB   – Oriented FAST and Rotated BRIEF
FREAK – Fast Retina Keypoint

Image Feature Matching

特徵匹配。两张图片，找到引人注目的地方，找到对应。

KNN Match
Radius Match
Flann Based Matcher
RANSAC

Image Object Detection

物体侦测。判断图片内容是否为预设物体。

Viola-Jones framework ：最初用来侦测人脸。一、已知是何物的图片，穷举位置、范围、窗函数（仿照 Harr 小波，此处使用四种），一种情况当做一个特徵，得到大量特徵。二、因此图片必须尺寸一致、正面照、无留白，如此位置和范围才对的上。三、一个特徵，求区域和，得到一个分数，当作特徵描述。区域和的高速算法是前缀和相减。四、实施 classification，取得关键特徵，捨弃无效特徵。五、不知是何物的图片，穷举位置、区域，全部特徵都通过检验才视为正确。

integral channel features (ChnFtrs) ：Viola-Jones framework 豪华版，最初用来侦测行人。一、像素数值，除了灰阶值以外，还可以是梯度方向的投票数（仿照 HOG，此处使用六个箱子）、梯度长度、LUV 值。二、窗函数，除了原本四种以外，还可以是简单的矩形窗、自订的零散的区域。三、区域和，还可以是 histogram。

Image Object Recognition

物体辨识 。判断图片内容是哪种物体。

Image Saliency Detection

重点侦测。针对人类视觉系统的特性，找到图片引人注目的地方。引人注目的地方，不一定是与众不同的地方。

Image Edge Grouping

边缘整合。针对人类视觉系统的特性，将图片边缘衔接成区域。

Image Texture Description

纹理描述 。将纹理独特之处写成数值，以供辨识比对。

local binary pattern ：八个相邻像素值，分别减去中央像素值，取其正负号，变成 8-bit 二进位数值。旋转视为相同，剩下 36 种数值。图片所有像素都实施此计算，统计每种数值的数量。

Image Shape Description

形状描述 。将形状独特之处写成数值，以供辨识比对。平移旋转后，数值需相同。

principal component analysis：凭感觉乱搞。座标轴不实用，中心则可用。

shape histogram：选定中心，同心圆、放射线。

spherical harmonics decomposition：选定中心，分解成 球谐函数 。

Image Reasoning（Under Construction!）

简介

Image Categorization

归类 。解读图片内容，将大量图片分门别类。

bag-of-words model：列举世上各种物品，编纂百科全书。一张图片，从中找到每种物品的出现次数（或者相似程度），得到一个直方图。所有直方图实施 clustering 建立分类；分群时，以 histogram comparison 得到两两直方图距离。

part-based model：

GIST descriptor：

convolutional neural network ：专门用来分类图片的数学模型。手动分类大量图片，灌入模型，进行训练。之后就能找到某图片的类别，也能找到某类别的图片。

Image Retrieval

检索 。从大量图片当中找到想要的图片。可以进一步制造 归纳 的效果。

Image Parsing

剖析 。建立图片当中每个物品的从属关係。

binary partition tree ：把一张图片裡的物件依照区域分类，储存于二元树之中。

Image to Text（Image Caption）

图片转文字 。可以进一步制造 看图说故事 的效果。

Text to Image

文字转图片。

Video Tracking（Under Construction!）

概论

图片的数学运算：Registration

物体不断移动，物体于每张图片的位置、形状都略有差异。我们可以透过前面章节的 feature detection、feature description，撷取物体的大致范围，但是如何精准得到物体移动轨迹呢？

想像像素们一齐移动，欲求轨迹。像素们一齐实施函数变换，欲求函数。此问题即是 registration ，每个点（像素）另外附带数值（像素值）；点的位置要尽量对齐，点的数值也要尽量相同。

Kanade-Lucas-Tomasi algorithm ：一、假设只有 translation。二、令两张图的平方误差最小。三、泰勒展开式，以零阶与一阶导数，近似原式。四、实施 gradient descent 或者 Euler extrapolation。

图片的特殊武器：Optical Flow

Kanade-Lucas-Tomasi algorithm 的高速近似算法。一、增加了时间维度。二、假设像素们位移之后完全相符，原式与零阶导数完全相等。两者相消后，得到“泰勒展开式一阶导数等于零”的结论，得到一道简洁的线性方程式。

一个像素构成一道线性方程式，所有像素构成一个线性方程组（矩阵恰是二次动差矩阵总和）。求解，即得位移量。

然而，正常情况下，像素们位移之后不可能完全相符。前述假设，逻辑错误，最后得到歪解。凭感觉瞎搞，但是算得快。

“泰勒展开式一阶导数等于零”，整个式子除以时间，就得到像素速度与亮度的关係式。计算学家取了一个文雅的名称叫做“光流”。以光流的角度，重新解释整件事：

假定像素亮度不变、位置会变；欲求像素的移动速度，移动速度表示成向量。三个维度：长、宽、时间。像素位置改变，泰勒展开式取到一阶导数，原式与零阶导数相消：梯度在“像素的移动距离向量”上的点积（投影）等于零。整个式子除以一单位时间：梯度在“像素的移动速度向量”上的点积（投影）等于零。此投影量，理想状态是零，但是通常不是零。我们希望投影量越小越好。

Lucas-Kanade algorithm ：“投影量”越小越好。一、因为是歪解，所以只好用递推法趋近正解。二、递推法，以当前移动速度来移动像素，再求得新的移动速度，直到收敛。三、缩放法，Gaussian pyramid，从最小的图片（最大的范围）开始实施，逐步缩小范围。四、translation 可以推广成 affine transform。请参考 这篇讲义 。

Horn-Schunck algorithm ：“投影量”与“速度向量的长度”越小越好。scalarization。

EpicFlow ：“投影量”与“速度向量的长度”与“边缘匹配的差异”越小越好。scalarization。

Video Stabilization

安定。摄影过程中相机震动摇晃，相机位置不断改变。摄影之后令影片摆正对齐。

Image Template Tracking

范本追踪 。给定图片片段，找到移动轨迹。

Lucas-Kanade algorithm ：

Image Feature Tracking

特徵追踪。给定图片特徵，找到移动轨迹。

Kanade-Lucas-Tomasi algorithm ：

Video Object Tracking（Video Object Matching）

物体追踪。指定图片当中物体，找到移动轨迹。可以进一步达到 複数物体追踪 、 群众计数 的效果。

dense tracking：warping + template matching + template tracking。

sparse tracking：feature detection + feature matching + feature tracking。

online optimization：以 histogram 或 SIFT 的相似程度做为函数，实施 mean shift 或 particle filter。

convolutional neural network：

Video Magnification

放大 。以高速、高解析度的摄影机进行拍摄，观察物体极短时间、极小范围的微小变化。 应用范围很广 。

Image Coding（Under Construction!）

简介

像素数值，视作纯粹的数字、讯号、码。

图片的数学运算：Vector 与 Linear Transformation

一张图片，可以表示成 RGB 三条向量。

像素的运算，想成是函数。若是线性变换，可以写成矩阵。

线性变换有许多优美的性质。例如矩阵加减，等价于新图片加减。例如一连串线性变换，可以简化成一次线性变换；多个矩阵预先相乘（複合），简化成一个矩阵。

Image Representation

表示法。以简略数据，纪录图片，用于特徵描述、辨识。

eigenimage ：图片表示成向量。两两点积，求相关矩阵（实数对称矩阵），得到特徵值（实数）、特徵基底（正规正交矩阵）。

sparse coding ：图片表示成向量。求一套基底，其线性组合涵盖所有向量（图片）。处理一张图片：解 Ax = b，A 的一个直条是一张样式图片，x 是加权平均值，b 是一张完整图片，请最小化 x 的 1-norm。处理多张图片：加总起来，或者把向量推广成矩阵。

图片的数学运算：Fourier Transform

声音处理是一维讯号，影像处理是二维讯号，道理相通。

图片亦有 spatial domain 与 frequency domain 的概念。实施正向的二维 Fourier transform ，空域转频域。实施逆向的二维 Fourier transform，频域转空域。时间複杂度为 O(XYlogXY)。

空域当中，平均值具备平滑效果，声音处理得齆声，影像处理得雾化；差分具备差异效果，声音处理得尖声，影像处理得边缘。

频域当中，低频数值具备主体，声音处理得母音，影像处理得形体；高频数值具备细节，声音处理得爆音，影像处理得特徵。

声音处理，频域符合人类感知；影像处理，空域符合人类感知。因此影像处理不适合採用频域。早期的影像处理教科书，是讯号学者主导，所以才会非常强调频域。

如果不关心图片内涵，只想把图片当作讯号来处理，那麽频域就可发挥功效。

Image Noise

杂讯 。像素值异动、有误差，不是原始数值。简单起见，习惯假设：每个像素独立产生杂讯，不会互相影响。

不同的杂讯，有不同的补救方式。兵来将挡、水来土掩。

salt-and-pepper noise ：各个像素以固定机率丢失。要嘛正常，要嘛变成 0 或 255。数位传输经常出现。破法是 median filter。

Gaussian noise ：相素值添加误差，误差呈 Gaussian distribution，简称 Gaussian error。类比传输经常出现。破法是 mean filter。

clipped noise：感光设备收集过多亮度，数字爆表，仅得 255。好比电玩游戏伤害上限 9999。亮处摄影经常出现。无法破解。

shot noise ：感光设备偶然加收一些亮度。好比公车正要离站，刚好有人陆续赶上车，公车无法立即关门、准时行驶。即是 Poisson error。暗处摄影经常出现。破法是 mean filter。

quantization noise ：像素值捨去小数变成整数，导致误差。我们合理假设，小数部分任何可能性一律均等，呈 uniform distribution。捨去小数，即是减去一个随机数字，即是添加误差，即是 uniform error。数位设备必然出现。不必破解。

Image Denoising

去杂讯、去噪。

Wiener deconvolution ：

Richardson-Lucy deconvolution ：假设位移误差是 Gaussian noise，亮度误差是 Poisson noise。

anisotropic diffusion ：

图片的数学运算：Wavelet

http://www.jjj.de/fxt/fxtbook.pdf

Gabor filter ：

Image Compression

压缩 。主要用途是 图片档案格式 。目标是减少档案容量、避免画面 失真 。

BMP ：无压缩。添加表头。

JPEG ：失真压缩。8x8、RGB2YUV、DCT（KLT if 1-markovian）、quantization、zig-zag、Huffman。

JPEG 2000 ：失真压缩。发展当中。

PNG ：无失真压缩。delta filtering = finite difference、DEFLATE = LZ77 + Huffman、CRC。

GIF ：无失真压缩，只有 256 色，已退流行。LZW。

DjVu ：失真压缩，专门处理文件。黄钟毁弃，瓦釜雷鸣，故不流行。分三层：前景、背景、文字。前景、背景，IW44。文字视作黑白图片，JB2。

Video Compression

压缩 。影像压缩标准的两大阵营是国际标准 HEVC、谷歌 VP9。主要用途是 影片档案格式 。可以进一步制造 串流 、 广播 的功能。

MPEG ：继承 JPEG。在前后帧找到相似区块，增进压缩效果。区分 IPB 三种帧。

Image Transmission

传输。传送图片资讯，儘量不失真。

progressive transmission：设定成不同解析度，分别传输。

Image Watermarking（Image Steganography）

浮水印 。讯息隐藏至图片当中，无法察觉差异。用来判断图片是否被私下改造。

Image Acquisition

撷取 。运用各种器材，获得资讯，将资讯转换成像素数值。诸如数位相机、监视器、扫描器、显微镜、太空望远镜、声纳、超音波摄影、核磁共振摄影等等。详情请洽电机系。

注意到资讯不一定要是光线的频率、光线的强度，也可以是物质密度、声音频率等其他东西。

http://en.wikipedia.org/wiki/Coherent_diffraction_imaging