发表于 | 分类于

基于DSP的目标跟踪

一、目标

利用VisualDSP++ 5.0、仿真器、EBF-561实验平台实现该算法，初步了解运动目标跟踪算法基本原理，体会并学习如何用该算法实现视频跟踪，并完成模板匹配跟踪部分的程序。

二、实现方案

实验原理

模板匹配就是在一幅大图像中搜寻目标，已知在该图中有要寻找的目标，且该目标与模板有相同的尺寸、方向和图像，通过一定的算法可以在图中找到目标，确定其坐标位置。

设模板T叠放在搜索图S上平移，模板覆盖下的那块搜索图叫做子图，这块子图的左上角像素点为S的坐标，即参考点。

我们可以用下式来衡量T和S的相似程度：

1

展开上式，则有：

2

阅读全文 »

发表于 | 分类于

基于MRF的FCM图像分割

一、目标

利用VisualDSP++ 5.0、仿真器、EBF-561实验平台实现该算法，并通过该聚类算法实现图像的不同区域的聚类结果。

二、实现方案

实验原理

MRF理论提供了建模上下文依赖实体的一种方式，实体包括图像像素和相关特征等。

在MRF中，令F={F1,…..,Fm}是一组定义在集合S上的随机变量，其中Fi代表在标签集L中的一个取值fi，Fi=fi代表取值为fi的事件，（F1=f1,…,Fm=fm）代表联合事件（joint event）。假设f={f1,….fm}，那么刚才叙述的联合事件则可简记为F=f。对于离散的标签集合L，Fi=fi的概率记作P(Fi=fi)，简称P(fi)；联合事件的概率记作P(f)。对于连续的标签集合L，我们可以知道pdf p(Fi=fi)和p(F=f)。

对于一个邻域系统N，如果如下两条性质满足：

  1. P(f) >0 , 对任意的f。（非负性）
  2. P(fi| fs-{i})=P(fi|fNi)。（马尔科夫性）

那么，我们就称F是一个马尔科夫随机场。

上述1.2中，S-{i}是i除i之外的所有点，如果对于图像来讲，i是其中一个像素，那么S-{i}就是除i之外的其他所有像素；fs-{i}代表的是S-{i}中的所有点的标签集合；fNi={fi’|i’∈Ni}表示点i的邻域的点的标签集合。

阅读全文 »

发表于 | 分类于

基于DSP的FCM图像分割

一、目标

利用VisualDSP++ 5.0、仿真器、EBF-561实验平台实现该算法，并通过该聚类算法实现图像的不同区域的聚类结果。

二、实现方案

实验原理

FCM 聚类算法目标函数为

1

如果 p表示每一个样本x_j的维数0，X={x_1,x_2,…x_j,…x_N}是一个p×N矩阵；N表示样本数目，通常表示图像像素数；C表示聚类数目；u_ij⊆U(p×N×C)是矢量x_j隶属于第i类的隶属度函数，满足u_ij∈[0,1]且∑_(i=1)^C▒u_ij =1；聚类中心Z={z_1,z_2,…z_i,…z_c}是 p×C矩阵，u_ij和z_i更新等式分别为：

2

对于每一个模糊隶属度，由m∈(1,∞)控制模糊度的权重指数；

d^2 (x_j,x_i )=∥x_j-z_i∥为相似性测度。

阅读全文 »

发表于 | 分类于

基于DSP的Kmeans图像分割

一、目标

利用VisualDSP++ 5.0、仿真器、EBF-561实验平台实现该算法，并通过该聚类算法实现图像的不同区域的聚类结果。

二、实现方案

实验原理

产生图像不同区域的聚类本质是图像分割，就是把图像分成若干个特定的、具有独特性质的区域过程，它是由图像处理到图像分析的关键步骤。目前的图像分割方法主要分以下几类：基于阀值的分割方法、基于区域的分割方法、基于边缘的分割方法以及基于特定理论的分割方法等。近年来，研究人员不断改进原有的图像分割方法并把其它学科的一些新理论和新方法用于图像分割，提出了不少新的分割方法。

K-means 算法是很典型的基于距离的聚类算法，采用距离作为相似性的评价指标，即认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到的紧凑且独立的簇作为最终目标。

阅读全文 »

发表于 | 分类于

基于MATLAB的顺序前进、顺序后退及遗传算法特征提取比较

一、概念

特征提取

要在低维空间中更好的分类，变换的有效性最好用错误概率来衡量，然而其计算复杂。从计算观点看，用其中的一些判据进行特征提取往往是唯一可行的方法。

特征提取方法包括按欧氏距离度量、按概率距离判据、基于判别熵最小化等方法。

特征选择

特征选择即对原有特征进行删选优化，从原始特种中挑选出一些最有代表性、分类性能最好的特征进行分类。

需要解决的问题：选择的标准、快速寻优算法。

经典特征选择算法：
1）分支定界法：最优搜索
2）次优搜索：单独最优特征组合法、顺序前进法、顺序后退法
3）其他：模拟退火法、Tabu 搜索法、遗传算法

阅读全文 »

发表于 | 分类于

MATLAB验证LDA降维前后k近邻准确率

一、概念

1.最近邻法：对于未知样本x，比较x与N个已知类别的样本之间的欧式距离，并决策x与距离它最近的样本同类。

2.K近邻法：取未知样本x的k个近邻，看这k个近邻中多数属于哪一类，就把x归为哪一类。K取奇数，为了是避免k1=k2的情况。

3.欧式距离公式：
二维的公式 d = sqrt ( (x1 - x2) ^2 + (y1 - y2) ^2)
三维的公式 d = sqrt ( (x1 - x2) ^2 + (y1 - y2) ^2 + (z1 - z2) ^2)
推广到n维空间，欧氏距离的公式 d = qrt( ∑ (xi1 - xi2) ^2 ) i=1,2..n
xi1表示第一个点的第i维坐标,xi2表示第二个点的第i维坐标.

阅读全文 »

发表于 | 分类于

MATLAB验证Fisher线性判别

一、概念

Fisher判别法的基本思想是寻找一个最好的投影方向，在这个方向的直线上，d维样本的投影能分开的最好。问题是如何根据实际情况找到这条最好的、最易于分类的投影线。这就是fisher法所要解决的基本问题。
一维空间的Fisher线性判别函数为：

fisher1

其中，m1和m2是两个样本的均值，S1，S2分别为各类样本的的类内离散度。投影方向w为：

fisher2

在Fisher判决函数中，分子反应了映射后两类中心的距离平方，该值越大，类间可分性越好；分母反应了两类的类内的离散度，其值越小越好；从总体上讲， 的值越大越好，在这种可分性评价标准下，使 达到最大值的 即为最佳投影方向。以上所做的全部工作都是将d维空间的样本集映射成一维样本集，然后，我们只需要再确定一个阈值,将投影点与阈值比较，便可作出决策。本程序中，采用的是:

阈值=(m1-m2)/2

然后再根据决策规则比较投影与阈值大小就可判断属于什么类型。

Fisher线性判别的主要优点是简单，容易实现，且计算量和存储量小。

阅读全文 »

发表于 | 分类于

文献翻译(一) 负载均衡博弈中稳定平衡低效比的更严格约束

Tighter bounds on the inefficiency ratio of stable equilibria in load balancing games

作者信息及概要

作者： Akaki Mamageishvili, Paolo Penna
作者单位： Department of Computer Science, ETH Zurich, Switzerland
刊名： Operations Research Letters, 2016, Vol.44 (5)
来源数据库： Elsevier Journal
DOI： 10.1016/j.orl.2016.07.014
关键词： Nash equilibria; Load balancing games; Potential games; Price of anarchy

概要：在本文中，我们研究了由Asadpour和Saberi（2009年）提出的负载平衡游戏平衡稳定的低效率比。我们证明更严格的上限和下限分别为7/6和4/3。将该问题中最知名的边界（分别为19/18和3/2）进行了改进。相当于得到了如何令 L2的范数可以近似与L∞的范数(最大完工时间)相同的机器调度达到最佳的问题的结果。

关键词：纳什均衡 负载均衡博弈 潜在博弈 无政府状态的价格

原文

阅读全文 »

发表于 | 分类于

纳什均衡中的网络节点极小覆盖问题

一、目标

当雪堆博弈满足r<1/kmax时，网络博弈的纳什均衡中的采用合作策略的节点构成极小节点覆盖。编程验证该结论，网络自定，节点数目不少于10。

二、原理分析

1、雪堆博弈

“雪堆”博弈模型是一种两人对称博弈模型。

在一个风雪交加的夜晚,两人相向而来,被一个雪堆所阻,假设铲除这个雪堆使道路通畅需要的代价为c,如果道路通畅则带给每个人的好处量化为b。如果两人一齐动手铲雪,则他们的收益为R=b-c/2;如果只有一人铲雪,虽然两个人都可以回家,但是背叛者逃避了劳动,它的收益为T=b,而合作者的收益为S=b-c;如果两人都选择不合作,两人都被雪堆挡住而无法回家,他们的收益都为P=0。这里假设收益参数满足下面的条件:T>R>S>P。

2、纳什均衡

纳什均衡是一种策略组合，使得同一时间内每个参与人的策略是对其他参与人策略的最优反应。

假设有n人参与博弈，如果某种情况下无一参与者可以独自行动而增加收益（即为了自身利益的最大化，没有任何单独的一方愿意改变其策略），则此策略组合被称为纳什均衡。所有局中人策略构成一个策略组合。
纳什均衡，从实质上说，是一种非合作博弈状态

阅读全文 »