本文介绍 Divide and Conquer（分而治之） 的一种典型算法，FFT（快速傅里叶变换）。

DFT

DFT：$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi k}{N} n}, k = 0, 1, 2, …, N-1$

• for each k: N complex mults, N-1 complex adds
• $e^{-j \frac{2 \pi k}{N} n}$ 预计算并保存在计算机中
• $O(N^2)$ computations for direct DFT $\Longrightarrow$ $O(N log_2 N)$ for FFT

　本周的 part 是 Divide and Conquer（分而治之）。

Books：数字图像处理（冈萨雷斯）
Codes：https://github.com/Durant35/Courses/tree/master/dip

第2章 数字图像基础

• 取样和量化
• 空间和灰度分辨率
  • 空间分辨率：空间分辨率是图像在单位面积内像素的个数，表示了图像的空间细节分辨能力
  • 灰度分辨率：灰度分辨率指的是在纯黑和纯白之间灰度级别的多少，指的是图像对灰度变化细节的分辨能力

TBD…

　情况是这样的，在之前讲过的回播 .pcap 数据的 Velodyne_player 程序中，需要调用 Winpcap (其实就是 libpcap 的 Win挫版) 的 API 解析 .pcap 数据，再通过 UDP 发送出去。我们的 Velodyne_player 是一个 Win32 的程序，显然调用的就是32位的 Winpcap 库的 API； 后来我们也移植了一个 .pcap 采集程序的 Linux 版本，结果，用该 Linux 版本采集程序采集到的 .pcap 数据却没办法用我们 Win 下的 Velodyne_player 回播。后来发现，我们的 Linux 版本的采集程序用的是64位的 libpcap 库(因为系统是64位的 Ubuntu16.04，默认安装的就是64位的 libpcap 库)，64位和32位的 libpcap，在时间戳上有很关键的区别，下面是开源的 pcap.h 中的声明:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/*
 * Generic per-packet information, as supplied by libpcap.
 *
 * The time stamp can and should be a "struct timeval", regardless of
 * whether your system supports 32-bit tv_sec in "struct timeval",
 * 64-bit tv_sec in "struct timeval", or both if it supports both 32-bit
 * and 64-bit applications.  The on-disk format of savefiles uses 32-bit
 * tv_sec (and tv_usec); this structure is irrelevant to that.  32-bit
 * and 64-bit versions of libpcap, even if they're on the same platform,
 * should supply the appropriate version of "struct timeval", even if
 * that's not what the underlying packet capture mechanism supplies.
 */
struct pcap_pkthdr {
  struct timeval ts;	/* time stamp */
  bpf_u_int32 caplen;	/* length of portion present */
  bpf_u_int32 len;	/* length this packet (off wire) */
};

近几个月的 Windows 高空作业让我发现，dumpbin 这个小工具往往能解决一些关键问题。目前发现并且使用过的这个小家伙的功能有:

• 查看 DLL 动态链接库导入导出信息，解决动态链接库导出和可执行程序引用对接问题、程序缺失库问题
• 查看可执行程序的依赖库信息，解决各种程序运行时报错
• 查看程序、库位数信息，找到库引用位数不匹配等尴尬问题

　下面就来快速学习一下，怎么把这个小家伙用起来。

　　待续…

　　待续…