设 $$ P={ { x_{k} } = (…,x_{-2},x_{-1},x_{0},x_{1},…):x_{i}\in R} $$ 表示双向无穷实数列集合，按分量自然的定义$P$中的向量加法与数乘，则$V$构成一个无穷维为实线性空间。在实际中我们一般称$P$为离散时间信号空间。 对于信号空间$P$的一个子空间（平方可和子空间）： $$ \begin{equation} l_{2}=\left{ {x_{k}} \in P : \sum_{k=-\infty}^{+\infty}x_{k}^{2} < +\infty \right} \end{equation} $$ 是一个无线维的内积空间，其中的内积是自然定义的，即： $$ \begin{equation} \left( {x_{k}},{y_{k}} \right) = \sum_{k=-\infty}^{+\infty}x_{k}y_{k} \end{equation} $$ 于是两个离散信号${x_{k}}$与${y_{k}}$正交$\Longleftrightarrow \sum_{k=-\infty}^{+\infty}x_{k}y_{k} = 0$ 而在实际中，当所有用户共享整个频率信道，不同用户被分配至不同的时区，并且不同用户的通信信号在时域上没有任何重叠，即若以${x_{k}}$与${y_{k}}$分别表示两个不同用户的通信信号，则$x_{k}y_{k}=0,\forall k$（此时由向量${x_{k}}$与${y_{k}}$生成的子空间不但相交为0，而且还是正交的），因此${x_{k}}$与${y_{k}}$正交。这就是在通信信号中信号正交性起到的关键性作用。

这几天到了申请奖学金的日子，才逐步意识到一个人什么都不懂完全靠厚脸皮也可以混到不错的位置。当然这句话里面并没有暗含说我懂得如何如何多，这点不能误解。其实总结起来就是一句话，论人际交往的重要性。 拿我一个队友来说，确实是什么都不会的渣渣，完全靠厚着脸皮什么都不会，上个学期信誓旦旦说什么坚持到最后总会有回报，实际上这家伙仅仅只是为了学习而学习，脸皮厚到把书抄了一遍甚至完全不思考过也敢说“我特么学完了”，学完考完过后再也不会花一丝心思在知识的拓展和回顾上，第二个学期开学回来之后好像很有成就感的在朋友之间炫耀，你们还会C语言么，我完全记不得了，当然这么做不怪他，毕竟你转专业了，没必要再在你身上浪费时间。 可恨的是，我居然对特别傻逼的好像对他抱有一丝希望似的让他混到了我的数学建模队伍，在队里他没有发挥任何关键性的作用，白天午觉睡一个下午，晚上十二点以后必须睡觉，早上八点才起床。在机房做题的三天，我三天都没有回寝室。对我而言，他就是那种吃不了苦而且也不努力的队友，这种队友在队里面完全就是吃干饭混奖的，任何人都有功力心，只是程度不同罢了，你干了实事，和你共事的人绝对不会有半句怨言，必定会和你分享共同的荣耀。 我做自己的事，我写自己的字，简简单单的喜欢，不需要那么多的评论。这段文字结束后，这段话很快就会被人遗忘，世界还会是原来的模样，不爽的还会继续不爽，懂我的人，嘴角依旧那样上扬，只希望朋友们坚持信仰。 浸着汗水的作品，你们尽数拿去，虚荣到底有什么意义，苦短人生，还有太多正事要我去完成，保持沉默因为懒得同你们争论。谁说人不分三六九等，想要我反驳，请先掂量掂量掂量你自己的身份。作茧自缚，践踏自尊，我坐在观众席笑看，尔等的愚笨。

Created by 欧 长坤 & 郭 瞾阳 & 黄 沐 on 13-9-16. Copyright (c) 2013年 欧 长坤 & 郭 瞾阳 & 黄 沐. All rights reserved. 摘 要 碎片化程度不同的碎纸片，其复原难度各有不同。好的复原筛选算法有效的帮助人们减少复原的时间，提高复原的效率。 针对三个问题中复原碎纸片的难度递进关系，本文同样建立了具备递进关系的三个数学模型，并给出其算法。分别为信号相似性算法、边界积分匹配算法和行距匹配算法。针对复原文件的特性，本文将碎片的复原过程分划为三个独立的代码模块，分别为整行筛选模块、整行拼接模块和各行拼接模块。每个模块适当组合使用三个算法，达到精准筛选与匹配。 在问题一中，由于附件1和附件2所提供的待复原图片数量较少，因此直接采用信号相似性分析，来拼接待复原的图片，拼接结果显示，拼接的匹配率达到100%，无需人工干预。 在问题二中，随着碎片数的增加，为了减小拼接问题的复杂度，先筛选出整行碎片，则将该问题转化为问题一进行研究。而整行筛选的方式，中文碎片和英文碎片的处理方式上有细微差异。对于中文碎片而言，采用了行距分析算法等，半自动化的完成了整块碎片文件的拼接，其间人工干预3次。对于英文碎片而言，实际拼接过程中直接使用信号相似性算法来筛选整行更为有效，匹配率为84.21%，完成整块209张图像碎片拼接只需人工干预33次。 对于更复杂的双面碎片问题三而言，综合运用了三个模块进行全面筛选匹配，将匹配率优化为63.31%，完成整个518张图像碎片的拼接复原需要人工干预95次。 关键词： 一维信号, 相似性分析, 边际积分, 行距提取, OpenCV 限于篇幅，下面谈谈摘要中提到的核心模块和核心算法。 一维信号相似分析模型 文[1]对于测量信号$x(t),y(t)$,使用了Hilbert空间上的内积理论获得了对两个信号的相似性判定的衡量方法。设$x=[\xi_{1},\xi_{2},…]$和$x=[\eta_{1},\eta_{2},…]$为两个离散信号，为使能量误差 $$ \begin{equation} Q=\Vert x-\lambda_{0}y\Vert ^{2}=\sum_{n}(\xi_{n}-\lambda_{0}\eta_{n})^{2} \end{equation} $$ 只需要令$\frac{dQ}{d\lambda_{0}}=0$，得到 $$ \begin{equation} \lambda_{0}=\frac{\sum_{n}\xi_{n}\eta_{n}}{\sum_{n}\eta_{n}^{2}} \end{equation} $$ 此时对应的最小能量误差为 $$ \begin{equation} Q_{min}=\sum_{n}(\xi_{n}-\lambda_{0}\eta_{n})^{2} = \sum_{n}\xi_{n}^{2} - \frac{\sum_{n}\xi_{n}\eta_{n}}{\sum_{n}\eta_{n}^{2}} \end{equation} $$ 而最小相对能量误差为：

自从大一第一个学期末的时候买了iPhone 5，逐步对苹果这个公司有了不同的看法。之前对苹果整个公司的看法，都停留在最初级的道听途说。在为期几个月的iPhone使用中发现，苹果的产品确实做得好。因此第二个学期就开始筹划购买MacBook相关事宜了。 购买MacBook之前一直都很担心是否在Windows上面的我必须的生产工具在Macintosh上是否也有，直到这个学期拿下MacBook后才解除了这个疑惑。Macintosh确实是最先进的操作系统，没有之一。 在Windows上，我的需求不多，早期的时候还未接触编程，因此需求工具不多，也就几个数学类的软件，大学后详细接触了编程，于是需求软件一下子就多了起来。下面我把我所有的需有都罗列在下，以备使用。 Maple（数学三剑客之一） Mathematica（数学三剑客之一） Matlab（数学三剑客之一） Lingo（可惜没有Mac版本） 几何画板（很好终于有了Mac版本） Chrome（全套Google服务不说了） Visual Studio（Windows上必备） Microsoft Office（Windows上必备） Goagent（翻墙必备） QQ（这个就不说了） 有道云笔记（一开始接触的就是有道的云笔记，重要的是它和一些帐号绑定全套服务会方便很多。） 迅雷（不说了） 百度云（百度真的很有钱，） WPS（可惜没有Mac版本，否则就真的能彻底抛弃Windows了） Adobe系列（Photoshop、Aftereffect、Audition、Premier Pro） 有道词典（英语渣也就不说什么了） Xcode（在Mac下取代了Visual Studio，重要的是它是免费的。） iWork（在Mac下取代了Microsoft Office。） Wireshark（抓包什么的还是很有用的。） Evernote（印象笔记，多平台通吃，最近几年挂起来的这阵风是好的，软件多平台通吃，给用户以最大体验。） MPlayerX（自带播放器解码还是不行，必须有一个强大的后盾） VirtualBox（开源的，比VMware好的感觉） MathType（Mac版本的Office没有自带MathType，幸运的是Mathtype有Mac版本）

模版链表 上周抽时间写了个模版链表，写完后发现编译过不了，开始我还以为是Xcode的问题，后来换成windows下发现还是不行，最后才知道，我把模版的具体实现和定义分离到.h和.cpp文件中，导致无法编译。具体原因我们等会儿再谈。 下面是实现的模版链表，由于上周后来参加数学建模就没有再写，排序函数还没写好。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 // // Chain.

概述 整个暑假都在做Tracking，其中最为重要的核心就是均值漂移了，均值漂移算法指的是一个迭代的步骤，即先算出当前点的漂移均值，移动该点到其漂移均值，然后以此为新的起始点，继续移动，知道满足一定条件结束。所以，均值漂移实际上是一种在一种数据的密度分布中寻找局部极值的稳定的方法。如果分布连续，那么处理则变得非常容易，在这种情况下本质上只需要对数据的密度直方图应用爬山算法。更加准确的说，均值漂移是与核密度估计的规则有关的算法。而所谓“核”，实际上是一个如同高斯分布的局部函数。如果在充足的点处拥有足够合适的带权重和尺度的核，数据的分布则可以完全根据这些核来表示。然而又与核密度的估计不同，均值漂移仅仅估计数据分布的梯度。如果变化为0的地方则表示是这个分布的峰值（当然，也有可能是局部的）。当然在附近或其他尺度上还是有可能有峰值的。 定义 给定$d$维空间$R^{d}$中$n$个样本点$x_{i},i=1,2,…,n$，$n$在$x$点的均值漂移向量的基本形式定义为： $$ \begin{equation} M_{h}(x)=\frac{1}{k}\sum_{x_{i}\in S_{k}}\left(x_{i}-x\right) \end{equation} $$ 目标模型 均值漂移采用的是特征值的加权概率分布来描述目标模型，属于模式识别中主要描述目标的模型，不同于自动控制理论中采用的状态方程。 目标模型一共具有$m$个特征值（可以理解为像素的灰度值），于是对于序列$q={q_{n}}$，而$u\in {1,…,m}$有 $$ \begin{equation} q\left(u\right)=C\sum_{i=1}^{n}k\left( \left\Vert \frac{X_{i}-X_{0}}{H} \right\Vert ^{2}\right) \end{equation} $$ 其中，$X_{0}$为窗口中心点向量值（可能为RGB向量或者灰度值），$X_{i}$是窗口内第$i$点向量值。$C$为归一化常数，保障$\sum_{i=1}^{m}q_{i}=1$ ，$H$为核函数的带宽向量。$M$为特征值的个数，对于图像处理可以理解为灰度等级划分的个数，从而特征值$u$为对应的灰度等级。 $\delta$函数为脉冲函数，保证只具有$u$特征值的像素才对概率分布作出贡献。从而$k$函数可以理解为$u$灰度值的一个加权频数。 匹配对象 同样采用的是特征值加权概率分布： $$ \begin{equation} P_{u}(Y)=C_{h} \sum_{i=1}^{n_{k}}k\left( \left\Vert \frac{X_{i}-Y}{H_{h}} \right\Vert ^{2}\right) \delta\left(b(X_{i})-u\right) \end{equation} $$ 其中$i\in [1,…,n_{h}]$，$Y$为匹配对象的中心， $X_{i}$是匹配窗口内第$i$点向量值。 $H_{h}$为匹配窗口的核函数带宽向量，$C_{h}$为匹配窗口特征向量的归一化常数。 匹配相似 匹配对象与目标模型的相似程度，相似函数采用的是Bhattacharyya函数 $$ \begin{equation} \rho\left(p(Y),q\right)=\sum_{u=1}^{m}\sqrt{P_{u}(Y)q_{u}} \end{equation} $$ 匹配过程 均值漂移采用梯度下降法，首先$$\rho(Y)$$在\rho(Y_{0})附近进行泰勒展开，去前两项，得到 $$ \begin{equation} \rho(Y) \approx \rho(Y_{0})+\frac{d\rho}{dp}\left(p(Y)-p(Y_{0})\right) \end{equation} $$ 定义 $$ \begin{equation} \rho_{u}(Y)=\sqrt{p_{u}(Y)q_{u}} \end{equation} $$ 从而 $ \begin{equation} \rho_{u}(Y)=\rho_{u}(Y_{0})+\frac{q_{u}}{ 2 \sqrt{p_{u}(Y_{0})q_{u}} }\left( p_{u}(Y) - p_{u}(Y_{0}) \right) \end{equation} $

今天有人问我这个问题，就抽零碎时间在手机上敲敲我的看法。 数学界从来不缺天才，数学界从来不缺重大的突破。就我大学一年零碎所了解到的（以前高中还是太肤浅，当时只是道听途说），现代社会从事科研的人数比以前多了不知多少倍，所以现代科学（包括数学）的发展和突破的速度超越了以往任何一个时代（即《三体》里大刘所说的“技术爆炸”）。 只不过，相对于无理数、复数、微积分这样受过正常理工科教育的人都能理解的简单知识而言，现代数学的突破是almost everyone看不懂的了。我说的“看不懂”是真的看不懂——即数学圈外的人、甚至数学圈内不是一个方向的研究者，连这个“突破”的成果是啥意思都看不明白，更别提理解这个成果是怎么得到的了。（所以大部分民科也只会在像哥德巴赫猜想这类问题上纠结一样） 所以，圈外人会有一种“科学发展停滞了”的错觉，虽然他们每天用着的手机、电脑等由几十年前的“旧数学成果”奠基的工业产品在日新月异地更新换代。（不要觉得现在的产品有多么先进，只是几十年前的数学家不想去做产品化这种无聊的东西。） “整数与小数之间的映射关系”、“离散和连续的关系”、“拓展数的概念”，都是很初等的东西，距离现代数学差得太远了。所以也就能理解为什么会提出这样的问题。 如果没有做过数学、物理等前沿学科问题的研究，是完全无法想象现代前沿科学是什么样的。其抽象程度、推导的复杂程度、需要的知识储备是大大超出一般圈外人的想象的。 举一些20世纪以后数学重大突破的实例吧： 哥德尔不完全性定理：由Godel证明，它使得人们一直以来寻求“完美的数学公理系统”的希望破灭——你永远不可能找到一个完美的数学公理系统，使得所有的数学命题都可以被证明或证伪。一个著名的例子就是连续统假设（CH）——以前数学家们孜孜以求的连续统假设的答案，是它和现代数学所采用的ZFC公理系统独立，即ZFC+CH不会有矛盾，ZFC+CH也不会有矛盾。 范畴论：一个不同于集合论的、可以作为现代数学基础的理论基石。由Samuel和Saunders创立，另外Lawvere、Alexander等数学家都为之做出了巨大贡献。集合论的基本概念是“元素”，而范畴论不再关心元素，而关心不同对象之间的联系，这更能抓住很多抽象数学机构的本质特征。例如，一个经典的例子是Gelfand representation，交换C*代数构成的范畴和紧Housdorff空间构成的范畴是等价的。范畴论不仅是代数几何等前沿数学分支的理论基础，还为理论计算机和物理的发展提供了强大的范畴论工具。 庞加莱猜想：1961年Smale证明了五维以上的情形，1981年Freedman证明了四维情形，2003年Perelman证明了三维情形，从而彻底解决。三人都因其对庞加莱猜想的贡献各自获得菲尔兹奖。关于它的意义我不想也不愿意用初等语言来描述（其实是我自己也不是很明白），微分几何与现代物理的深刻联系需要许多预备知识才能理解。事实上，现代数学最难且最热门的分支就是几何（包括微分几何、代数几何等），它是与现代物理关系最紧密的数学分支，也是聚集了最多数学天才的分支，最近几十年里这方面的突破性进展数不胜数，只可惜我资质愚钝表示都看不懂。

前段时间做Tracking，了解到Kalman滤波，感觉很不错。wikipedia上内容有点多，整理过后发现只有五个核心公式。 原理 Kalman滤波器不断把协方差递归，估算出最优值，并且保留了上一时刻的协方差（Kalman增益），因此它的运行很快，可以随不同的时刻而改变他的值。 首先，我们要引入一个离散控制过程系统，该系统可以用一个线性随机微分方程来描述： $$ \begin{equation} X(k)=AX(k-1)+BU(k)+W(k) \end{equation} $$ 加上系统的测量值： $$ \begin{equation} Z(k)=HX(k)+V(k) \end{equation} $$ 上面式子中，$X(k)$是$k$时刻的系统状态，$U(k)$是$k$时刻对系统的控制量。$AB$是系统参数，对于多模型系统，他们为矩阵。$Z(k)$是$k$时刻的测量值，$H$是测量系统的参数，对于多测量系统，$H$为矩阵。 $W(k)$和$V(k)$分别表示过程和测量的噪声。他们被假设成高斯白噪声他们的协方差分别为$Q$，$R$（假设不随系统状态变化而变化）。 对于满足上面条件（线性随机微分系统，过程和测量都是高斯白噪声），Kalman滤波器是最优的信息处理器。下面则用其自身和自身的协方差来估计系统的最优化输出。 首先，要利用系统的过程模型，来预测下一状态的系统。假设现在的系统状态是k，根据系统的模型，可以基于系统上一状态而预测出现在状态： $$ \begin{equation} X(k|k-1)=AX(k-1|k-1)+BU(k) \end{equation} $$ 上式中，$X(k|k-1)$是利用上一状态预测的结果，$X(k-1|k-1)$是上一状态最优的结果，$U(k)$为现在状态的控制量，如果没有控制量，它可以为0。 至此，系统结果已经更新，但对于$X(k|k-1)$的协方差还未更新，用$Cov$表示协方差则： $$ \begin{equation} Cov(k|k-1)=ACov(k-1|k-1)A^{T}+Q \end{equation} $$ 上式中，$Cov(k|k-1)$是$X(k|k-1)$对应的协方差，$Cov(k-1|k-1)$是$X(k-1|k-1)$对应的协方差，$A^{T}$表示$A$的转置，$Q$是系统过程的协方差。上面两个式子为对系统的预测。 当有了现在状态的预测结果，我们再收集现在状态的预测值。结合预测值和测量值，我们可以得到现在状态$k$的最优化估计值$X(k|k)$： $$ \begin{equation} X(k|k)=X(k|k-1)+K_{g}(k)(Z(k)-HX(k|k-1)) \end{equation} $$ 其中，$K_{g}$为Kalman增益： $$ \begin{equation} K_{g}=Cov(k|k-1)H^{T}(HCov(k|k-1)H^{T}+R(k))^{-1} \end{equation} $$ 于此，已经得到了k状态下的最优估算值$X(k|k)$。但是为了要另Kalman滤波器不断的运行下去直到系统过程结束，我们还要更新k状态下$X(k|k)$的协方差： $$ \begin{equation} Cov(k|k)=(E-K_{g}H)Cov(k|k-1) \end{equation} $$ 其中，$E$为单位矩阵。当系统进入$k+1$状态时，$Cov(k|k)$就是第二个公式的，因此，可以自回归下去。 应用 Kalman滤波器作为一个很好的预测模型，可以根据现有情况来预测未来情况，在做Tracking中则变得很有用处。对于一个对象$S$的Tracking，$S$的pos在域中漂移，利用Tracking可以使得pos平滑稳定。 在OpenCV中提供了CvKalman结构，但是使用起来仍然需要建立模型，前几天我根据上述原理对整个过程进行了封装： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 // // CvKalmanPoint.

之前一直对内存分配上的“stack”和"heap"理解虽说明白但不是很调理。今天写个文章来整理一下。 简单来将，stack上分配的内存系统自动释放，heap上分配的内存，系统不自动释放，哪怕程序退出，那一块内存还是在哪里。所以stack一般指的是金泰分配的内存，heap上一般是动态分配内存。 由于malloc系统函数的内存就是从堆上分配内存，从堆上分配的内存必须手动释放（free）。否则会出现内存泄露。当出现内存泄露时，系统可分配的内存会随着malloc的进一步使用而越来越少，直至系统崩溃。 下面来比较一下二者的区别。 1 2 3 4 5 char *allocStrFormStack(void) { char str[100]; return str; } 1 2 3 4 5 6 7 char *allocStrFromeHeap(int lenth) { char *str; if (lenth &lt;= 0) return NULL; return (char *)malloc(lenth); } 对于第一个函数，函数返回时str所占用的内存被系统所释放，因此，返回值不可被使用。第二个函数使用malloc在堆上分配了内存，因此函数返回时，该段内存并不会因为函数的出栈而释放该内存，从而返回的地址正确。但是一旦不使用free释放或者不小心将指针所移走将会造成内存泄露。

首先，我们需要创建一个MFC的项目。 创建完成后，我们点击下一步来到如图所示的设置界面，选择单个文档，取消文档/视图结构支持，取消使用 Unicode 库。 点击下一步，选择无数据库支持。再点击下一步，主要框架仅勾选最小化框和系统菜单，并选择使用菜单栏和工具栏，然后直接点击完成。 在右侧我们可以看到解决方案资源管理器中的文件列表。 直接运行程序会发现已经自行生成了很多内容，包括菜单栏等，下面我们删除它。 我们的项目名称为MFCTest，因此在MFCTest.cpp中，函数BOOL CMFCTestApp::InitInstance()的最后三行代码为自动生成的代码： 1 2 3 4 // 唯一的一个窗口已初始化，因此显示它并对其进行更新 pFrame->ShowWindow(SW_SHOW); pFrame->UpdateWindow(); return TRUE; 我们将其改为： 1 2 3 4 5 // 调整窗口大小 m_pMainWnd->SetWindowPos(NULL,0,0,811,632,SWP_NOMOVE); //800*600 m_pMainWnd->ShowWindow(SW_SHOW); m_pMainWnd->UpdateWindow(); return TRUE; 更改后的代码将窗口渲染为811*632的大小，而实际上用于显示的部分仅800*600。 在文件MainFrm.cpp中，找到函数 int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)： 可以发现为了兼容性和创建各种控件已经生成了很多的代码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct) { if (CFrameWndEx::OnCreate(lpCreateStruct) == -1) return -1; BOOL bNameValid; if (!