当前位置:文档之家› HITS算法的二部图实现

HITS算法的二部图实现

HITS算法的二部图实现
HITS算法的二部图实现

package extrcting;

import java.io.*;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.HashSet;

import java.util.Iterator;

public class HITS

{

//public ArrayList facet ;

public HashMap> graphFacet;//没有必要采用hashset,因为反正都得遍历

public HashMap> graphEmo;

public HashMap authScore; //每个节点的中心度

public HashMap centerScore; //每个节点的权威度

public HashMap edgeGraph; //边得信息,暂时没用上

public HashMap wordLex; // 词表,记录词语出现的次数

public HashSet Lexicon;

public HashMap facetScoreA;

public HashMap facetScoreC;

public HashMap emoScoreA;

public HashMap emoScoreC;

public final String data="20110317";

public Integer nounCount=0;

public Integer emoCount=0;

public Integer nounCountEmo=0;

public Integer emoCountEmo=0;

public int rowNumber;//所有行

public int rowNumberEmo=0;;//所有含有情感词的行

public HITS() throws IOException //构造函数

{

BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("Lexicon.txt")));

String words="";

rowNumber=0;

Lexicon = new HashSet(5000);

authScore= new HashMap(10000); //每个节点的中心度

centerScore = new HashMap (10000);

graphFacet = new HashMap>();

graphEmo = new HashMap>();

wordLex = new HashMap();

facetScoreA = new HashMap(5000);

facetScoreC = new HashMap(5000);

emoScoreA = new HashMap(5000);

emoScoreC = new HashMap(5000);

while((words=reader.readLine())!=null)

{

Lexicon.add(words+"/n");

}

extract();

// doHITS();

// finalScore();

// double averageNoun = nounCount/(double)rowNumber;

// double averageEmo = emoCount/(double)rowNumber;

// double averageNounEmo = nounCountEmo/(double)rowNumberEmo; // double averageEmoEmo = emoCountEmo/(double)rowNumberEmo; // System.out.println("名词个数"+nounCount);

// System.out.println("情感词个数"+emoCount);

// System.out.println("平均名词个数"+averageNoun);

// System.out.println("平均情感词个数"+averageEmo);

// System.out.println("所有行数"+rowNumber);

// System.out.println("有情感的行数"+rowNumberEmo);

// System.out.println("情感句平均名词个数"+averageNounEmo);

// System.out.println("情感句平均情感词个数"+averageEmoEmo);

}

public void doHITS() throws IOException

{

int iterOver=0; //代表迭代结束

final int iterTime = 1000; //迭代次数

int count =0; //计数,迭代次数

// File log = new File("E:\\HITSlog");//日志主要是查看盐的相关信息的// if(log.exists())

// {

// log.delete();

// }

// log.createNewFile();

// FileWriter write = new FileWriter(log);

// BufferedWriter bw = new BufferedWriter(write);

int codeNumber = authScore.size();

//while(iterOver!=1)

while(iterOver!=1&&count

{

double authMax=.0;

double centerMax=.0;//新的归一化算法

double authSum =.0;

double centerSum =.0;//用于归一化

HashMap authScoreLast= new HashMap(authScore);

//做实验表明,必须new,不new存的是地址

HashMap centerScoreLast = new HashMap(centerScore);

System.out.println("第"+count+"迭代"+"节点数"+codeNumber+"个");

Iterator iteratorFacet =graphFacet.keySet().iterator();//对属性部分遍历

while(iteratorFacet.hasNext())

{

String sFacet ="";

sFacet = (String) iteratorFacet.next();

ArrayList iterEmoArray = new ArrayList(graphFacet.get(sFacet));

Double authScoreArray=.0;

Double centerScoreArray =.0;

for(int i=0;i

/*

* 每个点的中心度是各个点的权威度之和

* 每个点的权威度是各个点的中心度之和

*/

{

// if(sFacet.equals("盐/n"))

// {

// bw.write(iterEmoArray.get(i));

// bw.newLine();

// bw.flush();

// }

authScoreArray = authScoreArray +

centerScoreLast.get(iterEmoArray.get(i));

authSum = authSum + centerScoreLast.get(iterEmoArray.get(i));

centerScoreArray = centerScoreArray + authScoreLast.get(iterEmoArray.get(i));

centerSum = centerSum + authScoreLast.get(iterEmoArray.get(i));

}

authScore.put(sFacet, authScoreArray);

centerScore.put(sFacet, centerScoreArray);

if(authScoreArray>authMax)//新归一化

{

authMax = authScoreArray;

}

if(centerScoreArray>centerMax)

{

centerMax = centerScoreArray;

}

}

Iterator iteratorEmo =graphEmo.keySet().iterator();//对情感部分遍历

while(iteratorEmo.hasNext())

{

String sEmo ="";

sEmo = (String) iteratorEmo.next();

ArrayList iterFacetArray = new ArrayList(graphEmo.get(sEmo));

Double authScoreArray=.0;

Double centerScoreArray =.0;

for(int i=0;i

/*

* 每个点的中心度是各个点的权威度之和

* 每个点的权威度是各个点的中心度之和

*/

{

authScoreArray = authScoreArray + centerScoreLast.get(iterFacetArray.get(i));

authSum = authSum + centerScoreLast.get(iterFacetArray.get(i));

centerScoreArray = centerScoreArray + authScoreLast.get(iterFacetArray.get(i));

authScoreLast.get(iterFacetArray.get(i));

}

authScore.put(sEmo, authScoreArray);

centerScore.put(sEmo, centerScoreArray);

if(authScoreArray>authMax)//新归一化

{

authMax = authScoreArray;

}

if(centerScoreArray>centerMax)

{

centerMax = centerScoreArray;

}

}

/*

* 归一化机制

*/

Iterator iteratorAuthNorm = authScore.keySet().iterator();

while(iteratorAuthNorm.hasNext())

{

String itFacet= (String)iteratorAuthNorm.next();

// Double authScoreNorm = authScore.get(itFacet)/authSum;

Double authScoreNorm = authScore.get(itFacet)/authMax; //新归一化

authScore.put(itFacet, authScoreNorm);

}

Iterator iteratorCenterNorm = centerScore.keySet().iterator();

while(iteratorCenterNorm.hasNext())

{

String itEmo = (String)iteratorCenterNorm.next();

// Double centerScoreNorm = centerScore.get(itEmo)/centerSum;

Double centerScoreNorm = centerScore.get(itEmo)/centerMax;//新归一化

centerScore.put(itEmo, centerScoreNorm);

}

/*

* 归一化机制

*/

Iterator iteratorAuth = authScore.keySet().iterator();//遍历中心度

int countJudge=0;

while(iteratorAuth.hasNext())

{

String word="";

word = (String)iteratorAuth.next();

if(((authScore.get(word)-authScoreLast.get(word)<0.00001)&&

(authScore.get(word)-authScoreLast.get(word)>-0.00001))

&&((centerScore.get(word)-centerScoreLast.get(word)<0.00001)&&

centerScore.get(word)-centerScoreLast.get(word)>-0.00001))

{

countJudge++;

}

}

//System.out.println(authScore);

//System.out.println(authScoreLast);

//System.out.println("查看迭代终止的另一个条件countjudge"+countJudge);

if(countJudge==authScore.size())

{

iterOver=1;

}

count++;

}

/*

* 迭代结束后的赋值阶段,最终得分阶段

*/

System.out.println(graphFacet);

System.out.println(graphEmo);

}

public void finalScore()

{

Iterator iteFacet = graphFacet.keySet().iterator();//把得分乘以出现的次数

while(iteFacet.hasNext())

{

String facet="";

facet = (String)iteFacet.next();

double scoreFA=.0;

double scoreFC=.0;

double timeF = Math.log10(wordLex.get(facet));

scoreFA = authScore.get(facet)*timeF;

facetScoreA.put(facet, scoreFA);

scoreFC = centerScore.get(facet)*timeF;

facetScoreC.put(facet, scoreFC);

}

Iterator iteEmo = graphEmo.keySet().iterator();

while(iteEmo.hasNext())

{

String emo ="";

emo =(String)iteEmo.next();

double scoreEA=.0;

double scoreEC=.0;

double timeE= Math.log10(wordLex.get(emo));

scoreEA = authScore.get(emo)*timeE;

emoScoreA.put(emo, scoreEA);

scoreEC = authScore.get(emo)*timeE;

emoScoreC.put(emo, scoreEC);

}

}

public void extract() throws IOException

{

System.out.println("开始抽取");

String inputDataPath = "E:\\日本地震_2\\corpus_sum_split\\sum_split"+data;

// String inputDataPath = "E:\\日本地震_2\\corpus_sum_split\\sum_splitSum";

File inputFile = new File(inputDataPath);

FileReader read = new FileReader(inputFile);

BufferedReader re = new BufferedReader(read);

String row ="";

while((row= re.readLine())!=null)

{

int emoSig=0;

int emoEmoCountRow=0;

int emoNounCountRow=0;

System.out.println("处理第"+rowNumber+"行");

//System.out.println(row);

ArrayList[] sentenceInfo = new ArrayList[50];

//一句话的信息,每一个Arraylist为子句的信息,就是用,分格出来的字句

for(int i=0;i<50;i++)

{

sentenceInfo[i]= new ArrayList();

}

int count=0;

int continueNoun=0;//记录名词后面是否有其他词,如果有的话,就不考虑“的”的问题了。

String[] words = new String[100];

words = row.split(" ");

for(int i=0; i

/*

*for循环的作用是遍历每一个词,加入到句子信息中

*/

{

if(words[i].indexOf("/nl")!=-1||words[i].indexOf("/nr")!=-1

||words[i].indexOf("/nrf")!=-1||words[i].indexOf("/nrj")!=-1

||words[i].indexOf("/nr1")!=-1||words[i].indexOf("/nr2")!=-1

||words[i].indexOf("/nsf")!=-1||words[i].indexOf("/ns")!=-1

||words[i].indexOf("/nt")!=-1||words[i].indexOf("/nz")!=-1

||words[i].indexOf("/n")!=-1)

/*

* ng不要,是两次神马的

*/

{

if(words[i]!=null)

//System.out.println(words[i]);

{

if(words[i].substring(0,

words[i].indexOf("/")).matches("[\u4e00-\u9fa5]+")

||words[i].substring(0,

words[i].indexOf("/")).matches("[a-zA-Z]+")

||words[i].substring(0,

words[i].indexOf("/")).matches("[0-9]+"))

{

// if(rowNumber>11183)

// {

// System.out.println(words[i]);

// System.out.println(row);

// System.out.println(count);

// System.out.println(sentenceInfo[count]);

// }

if(!words[i].equals("人/n")&&!words[i].equals("月/n")

&&!words[i].equals("町/n")&&!words[i].equals("原文/n")

&&!words[i].equals("时候/n")&&!words[i].equals("时/ng")

&&!words[i].equals("事情/n")&&!words[i].equals("事/n")

&&!words[i].equals("东西/n")&&!words[i].equals("心/n")

&&!words[i].equals("钱/n")&&!words[i].equals("国/n"))

sentenceInfo[count].add(words[i]);

continueNoun=1;

//统计信息

if(Lexicon.contains(words[i]))

{

emoCount++;

emoEmoCountRow++;

emoSig=1;

}else

{

nounCount++;

emoNounCountRow++;

}

}

}

}

else if(words[i].indexOf("/wd")!=-1||words[i].indexOf("/wj")!=-1

||words[i].indexOf("/ww")!=-1||words[i].indexOf("/wt")!=-1)

/*

* 如果遇到逗号,句号,叹号等能段位子句的符号,进入下一子句即下一个编号的arraylist开始写

* 如果上一句为空,解决了堆积符号的问题

* 这样处理“。。。”被忽略,不过“。。。”还有的情感很复杂,可以不考虑。

* /

*/

{

if(sentenceInfo[count]!=null)

{

if(sentenceInfo[count].size()>1)// 有一个无法组成搭配,默认继续写

{

count++;

}

}

}

else if(words[i].indexOf("/ude1")!=-1&&continueNoun==1)

/*

* 把之前读入的名词删除,因为该名词是

*/

{

// int delteN = sentenceInfo[count].size()-1;

// System.out.println(sentenceInfo[count]);

// System.out.println(delteN);

// if((sentenceInfo[count].get(delteN)).substring((sentenceInfo[count]

// .get(delteN)).indexOf("/")).length()>3)

// //识别出/n,/n的话就需要看是不是情感词,情感词就留下

// {

// sentenceInfo[count].remove(delteN);

// }else

// {

// if(!Lexicon.contains(sentenceInfo[count].get(delteN)))//如果不在情感词典,就删除

// {

// sentenceInfo[count].remove(delteN);

// }

// }

}

else

{

continueNoun=0;

}

}//for循环结束

//统计含有情感词下,名词与情感词的分布

if(emoSig==1)

{

nounCountEmo=nounCountEmo + emoNounCountRow;

emoCountEmo=emoCountEmo+emoEmoCountRow;

rowNumberEmo++;

}

ArrayList facetCandi = new ArrayList();

ArrayList emoCandi = new ArrayList();

//int sigClear=1; //负责记录有没有保留上一句没有搭配的情感词

for(int i=0; i

/*

* 遍历每一个子句

* 所完成的功能,加入二部图中

* 在子句内部的,加入

* 在子句内找不到搭配的,向上找

* 子句内有多个搭配的,排列组合

* */

{

for(int jArray=0;jArray

{

if(emoCandi.size()>0&&facetCandi.size()==0);

//当只有情感词的时候,把情感词带入下一个子句,通过观察,这样比较可行,或者只在每个子句做也可以的。

else//如果都有,则把搭配输出,输出后将数组清空

{

for(int iFacet =0;iFacet

{

for(int jEmo =0; jEmo

{

co_occur(facetCandi.get(iFacet),emoCandi.get(jEmo));

}

}

emoCandi.clear();

facetCandi.clear();

}

String wordInArray ="";

wordInArray = sentenceInfo[i].get(jArray);

if(Lexicon.contains(wordInArray))//是情感词,加入情感词候选,不是加入侧面的候选

{

//System.out.println("添加情感词"+wordInArray);

emoCandi.add(wordInArray);

}else

{

//System.out.println("添加属性候选"+wordInArray);

facetCandi.add(wordInArray);

}

}

}

rowNumber++;

}

}

public void co_occur(String facetCandi , String emoCandi)

/*

* 函数的参数为候选的属性,和候选的情感(对日本地震有效的情感词,或者说主要的情感词)

* 本函数相当于初始化,对graphFacet; graphEmo;edgeGraph;进行赋初值的计算

*/

{

//System.out.println( facetCandi+"与"+emoCandi+"共现");

if(graphFacet.containsKey(facetCandi))

{

if(graphFacet.get(facetCandi).indexOf(emoCandi)==-1)

{

graphFacet.get(facetCandi).add(emoCandi);//如果存在的话,就把emo加入新的set中

//不重复赋值

}

Integer cFacet =0;

cFacet = wordLex.get(facetCandi);

cFacet++;

wordLex.put(facetCandi, cFacet);

//Integer iEdge = -10000; //负责记录边得关系,边+1

//String edge = facetCandi+"-"+emoCandi;

//iEdge = edgeGraph.get(edge) ;

//iEdge++;

//edgeGraph.put(edge, iEdge);

}else//不存在的话,完成赋初值,包括初始的中心度和权威度

{

ArrayList setFacet = new ArrayList();

setFacet.add(emoCandi);

graphFacet.put(facetCandi, setFacet);

authScore.put(facetCandi, 1.0);

centerScore.put(facetCandi, 1.0);

wordLex.put(facetCandi, 1);

//String edge = facetCandi+"-"+emoCandi;

//edgeGraph.put(edge, 1);

}

if(graphEmo.containsKey(emoCandi))

{

if(graphEmo.get(emoCandi).indexOf(facetCandi)==-1)

{

graphEmo.get(emoCandi).add(facetCandi); //对grapgEmo赋值}

Integer cEmo =0;

cEmo = wordLex.get(emoCandi);

cEmo++;

wordLex.put(emoCandi, cEmo);

}else //不存在的话,完成赋初值,包括初始的中心度和权威度

{

ArrayList setEmo = new ArrayList();

setEmo.add(facetCandi);

graphEmo.put(emoCandi, setEmo);

authScore.put(emoCandi, 1.0);

centerScore.put(emoCandi, 1.0);

wordLex.put(emoCandi, 1);

}

}

}

图的算法实现课程设计

数据结构与算法 课程设计报告 课程设计题目:图的算法实现专业班级:信息与计算科学1001班姓名:学号: 设计室号:理学院机房 设计时间: 2011-12-26 批阅时间:指导教师:成绩:

图的算法实现 目录 一.设计内容 二.功能设计流程 三.详细设计 四.调试 五.总结 六.参考文献 七.附录源代码

一、设计内容: 1.实验内容 图的算法实现 (1)将图的信息建立文件; (2)从文件读入图的信息,建立邻接矩阵和邻接表; (3)实现Prim、Kruskal、Dijkstra序算法。 2.实现的任务:从文件中读入图的信息,建立图的邻接矩阵和邻接表,实现Prim、Kruskal、Dijkstra 3.本系统涉及的知识点 Prim、Kruskal、Dijkstra、邻接矩阵和邻接表存储。 4.功能要求 1.不同的功能使用不同的函数实现(模块化),对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2.对系统进行功能模块分析、画出总流程图和各模块流程图。 3.用户接口要求使用方便、简洁明了、美观大方、格式统一。 4.通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5.所有程序需调试通过。 二、功能设计流程: 图的算法 实现 邻接矩阵邻接表 Prim算法Kruskal算法Dijkstra算法

开始 辅助数组初始 输出生成树的边并计算其权值 新顶点并入U 集后重新选择最小边:遍历点,若g.edges[k][j]!=0 && g.edges[k][j]

算法分析与设计总结

第一章算法概述 1.算法:解决问题的一种方法或过程;由若干条指令组成的有穷指令。 2.算法的性质: 1)输入:有零个或多个输入 2)输出:有至少一个输出 3)确定性:每条指令是清晰的、无歧义的 4)有限性:每条指令的执行次数和时间都是有限的 3.算法与程序的区别 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有限性 4.算法复杂性分析 1)算法的复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复 杂性,需要空间资源的量称为空间复杂性 2)三种时间复杂性:最坏情况、最好情况、平均情况 3)可操作性最好且最有实际价值的是最坏情况下的时间复杂性 第二章递归与分支策略 1.递归概念:直接或间接调用自身的算法 2.递归函数:用函数自身给出定义的函数 3.递归要素:边界条件、递归方程 4.递归的应用 ?汉诺塔问题 void Hanuo(int n,int a,int b,int c) { if(n==1) return; Hanuo(n-1,a,c,b); move(a,b) Hanuo(n-1,c,b,a); } ?全排列问题 void Perm(Type list[],int k,int m) { //产生list[k,m]的所有排列 if(k == m) { for(int i = 0;I <= m;i++) cout<

基于matlab的图像去雾算法详细讲解与实现-附matlab实现源代码

本文主要介绍基于Retinex理论的雾霭天气图像增强及其实现。并通过编写两个程序来实现图像的去雾功能。 1 Rentinex理论 Retinex(视网膜“Retina”和大脑皮层“Cortex”的缩写)理论是一种建立在科学实验和科学分析基础上的基于人类视觉系统(Human Visual System)的图像增强理论。该算法的基本原理模型最早是由Edwin Land(埃德温?兰德)于1971年提出的一种被称为的色彩的理论,并在颜色恒常性的基础上提出的一种图像增强方法。Retinex 理论的基本内容是物体的颜色是由物体对长波(红)、中波(绿)和短波(蓝)光线的反射能力决定的,而不是由反射光强度的绝对值决定的;物体的色彩不受光照非均性的影响,具有一致性,即Retinex理论是以色感一致性(颜色恒常性)为基础的。 根据Edwin Land提出的理论,一幅给定的图像S(x,y)分解成两幅不同的图像:反射物体图像R(x,y)和入射光图像L(x,y),其原理示意图如图8.3-1所示。 图-1 Retinex理论示意图 对于观察图像S中的每个点(x,y),用公式可以表示为: S(x,y)=R(x,y)×L(x,y) (1.3.1)实际上,Retinex理论就是通过图像S来得到物体的反射性质R,也就是去除了入射光L的性质从而得到物体原本该有的样子。 2 基于Retinex理论的图像增强的基本步骤 步骤一: 利用取对数的方法将照射光分量和反射光分量分离,即: S'(x, y)=r(x, y)+l(x, y)=log(R(x, y))+log(L(x, y)); 步骤二:用高斯模板对原图像做卷积,即相当于对原图像做低通滤波,得到低通滤波后的图像D(x,y),F(x, y)表示高斯滤波函数: D(x, y)=S(x, y) *F(x, y); 步骤三:在对数域中,用原图像减去低通滤波后的图像,得到高频增强的图像G (x, y): G(x,y)=S'(x, y)-log(D(x, y)) ;

算法分析与设计

专业: 班级: 学号: 姓名: 日期: 2014年 11月 10日

48476Λn n 111+++=。 2、q(n ,m)=q(n ,n),m>=n 。 最大加数n1实际上不能大于n ,因此,q(1,m)=1。 3、q(n ,n)=1+q(n ,n-1)。 正整数n 的划分由n1=n 的划分和n1<=n-1的划分组成。 4、q(n ,m)= q(n ,m-1)+q(n-m ,m),n>m>1。 正整数n 的最大加数n1不大于m 的划分由n1=m 的划分和n1<=m-1的划分组成。 (2)、算法描述 public class 张萌 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub System.out .println(q (2,2)); } public static int q(int n,int m) { if ((n<1)||(m<1)) return 0; if ((n==1)||(m==1)) return 1; if (n

哈密顿图判定问题的多项式时间算法

哈密顿图判定问题的多项式时间算法 姜新文等** (410073,国防科技大学计算机学院,长沙) Abstract: 本文给出一个称为 问题的定义及其多项式时间判定算法。已经证明包括哈密顿图判定问题在内的众多 完全问题可以多项式归结到 问题。 问题的多项式时间判定算法就是 完全问题的多项式判定算法。本文结果暗示 。本文涉及的内容属于简单的图论问题算法设计的入门性范畴,被计算机、数学和信息安全等类专业本科以上知识背景覆盖。相关专业本科甚至专科以上学生通过适当求教算法设计、计算复杂性、图论、运筹学和密码算法相关教师和权威可以阅读本文。 Key words: Algorithm, problem, problem, complete problem 1 问题引入及若干定义 哈密顿图判定问题是 完全问题。为了求解该问题,我们需要对问题进行转化。为缩短证明长度,以分段确认,分割围歼,综合众多意见,我们提出 问题,并将注意力集中在 问题多项式时间判定上。 算法是一堆动作的有序集合。为一个问题设计算法是容易的,将一些动作凑在一起即可。设计算法的困难性和严肃性在于,你的算法是否实现了你的计算目标?于是需要证明。而如何证明常常让人无从着手。 问题是一个人工构造的问题,它的特别的结构特性,使我们容易找到时间复杂性为关于问题规模的多项式函数算法并证明其正确性。该问题的定义已经可以在很多文章中查到。为了本文的完整性,我们首先转述对 问题的定义。 定义1称 , , , , 是加标多级图(labeled multistage graph),如果满足以下条件: 1. 为顶点集合, ∪ ∪ ∪?∪ , ∩ ?,0 , , 。如果 ∈ ,0 ,称 所在级为 级,也称 是 级的顶点。 称为 的级。 2. 为边的集合, 中的边均为有向边,它用三元组? , , ?表示。如果? , , ?∈ ,1 ,则 ∈ , ∈ 。称? , , ?为 的第l级的边。 3. 和 都只包含唯一顶点。称 中的唯一顶点为源点,记为 ,称 中的唯一顶点为汇点,记为 。 4. 对每个顶点 ∈ ,都有一个边集 ( )作为标记, ( )? 。称 ( )为 的边集。 例如,图1所示的两个图,都是加标多级图。各个顶点的边集的一组可能的取值定义如下。对左边的图, (1) , (2) , (3) , , , , (4) , , , (5) , , , (6) , , , , (7) , (8) , , , , ( ) , , , , 。对右边的图, (1) ?, (2) ?, (3) ?, (4) , , , (5) , , , (6) , , , (7) (7 ) , , , , (8) , , , , ( ) ?。 定义2设 , , , , 是一个加标多级图, ? ? (1 , )是 中一**Please visit https://www.doczj.com/doc/9917479277.html,/u/1423845304 for revision information

图像拼接算法及实现.doc

图像拼接算法及实现(一) 来源:中国论文下载中心 [ 09-06-03 16:36:00 ] 作者:陈挺编辑:studa090420 论文关键词:图像拼接图像配准图像融合全景图 论文摘要:图像拼接(image mosaic)技术是将一组相互间重叠部分的图像序列进行空间匹配对准,经重采样合成后形成一幅包含各图像序列信息的宽视角场景的、完整的、高清晰的新图像的技术。图像拼接在摄影测量学、计算机视觉、遥感图像处理、医学图像分析、计算机图形学等领域有着广泛的应用价值。一般来说,图像拼接的过程由图像获取,图像配准,图像合成三步骤组成,其中图像配准是整个图像拼接的基础。本文研究了两种图像配准算法:基于特征和基于变换域的图像配准算法。在基于特征的配准算法的基础上,提出一种稳健的基于特征点的配准算法。首先改进Harris角点检测算法,有效提高所提取特征点的速度和精度。然后利用相似测度NCC(normalized cross correlation——归一化互相关),通过用双向最大相关系数匹配的方法提取出初始特征点对,用随机采样法RANSAC(Random Sample Consensus)剔除伪特征点对,实现特征点对的精确匹配。最后用正确的特征点匹配对实现图像的配准。本文提出的算法适应性较强,在重复性纹理、旋转角度比较大等较难自动匹配场合下仍可以准确实现图像配准。 Abstract:Image mosaic is a technology that carries on the spatial matching to a series of image which are overlapped with each other, and finally builds a seamless and high quality image which has high resolution and big eyeshot. Image mosaic has widely applications in the fields of photogrammetry, computer vision, remote sensing image processing, medical image analysis, computer graphic and so on. 。In general, the process of image mosaic by the image acquisition, image registration, image synthesis of three steps, one of image registration are the basis of the entire image mosaic. In this paper, two image registration algorithm: Based on the characteristics and transform domain-based image registration algorithm. In feature-based registration algorithm based on a robust feature-based registration algorithm points. First of all, to improve the Harris corner detection algorithm, effectively improve the extraction of feature points of the speed and accuracy. And the use of a similar measure of NCC (normalized cross correlation - Normalized cross-correlation), through the largest correlation coefficient with two-way matching to extract the feature points out the initial right, using random sampling method RANSAC (Random Sample Consensus) excluding pseudo-feature points right, feature points on the implementation of the exact match. Finally with the correct feature point matching for image registration implementation. In this paper, the algorithm adapted, in the repetitive texture, such as relatively large rotation more difficult to automatically match occasions can still achieve an accurate image registration. Key words: image mosaic, image registration, image fusion, panorama 第一章绪论

算法分析与设计

第一章 什么是算法 算法是解决一个计算问题的一系列计算步骤有序、合理的排列。对一个具体问题(有确定的输入数据)依次执行一个正确的算法中的各操作步骤,最终将得到该问题的解(正确的输出数据)。 算法的三个要素 1).数据: 运算序列中作为运算对象和结果的数据. 2).运算: 运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移: 运算序列中的控制和转移. 算法分类 从解法上:数值型算法:算法中的基本运算为算术运算;非数值型算法:算法中的基本运算为逻辑运算. 从处理方式上:串行算法:串行计算机上执行的算法;并行算法:并行计算机上执行的算法 算法的五个重要的特性 (1) 有穷性:在有穷步之后结束。 (2) 确定性:无二义性。 (3) 可行性:可通过基本运算有限次执行来实现。 (4) 有输入 表示存在数据处理 (5) 有输出 伪代码 程序设计语言(PDL ),也称为结构化英语或者伪代码,它是一种混合语言,它采用一种语言(例如英语)的词汇同时采用类似另外一种语言(例如,结构化程序语言)的语法。 特点:1)使用一些固定关键词的语法结构表达了结构化构造、数据描述、模块的特征; 2)以自然语言的自由语法描述了处理过程;3)数据声明应该既包括简单的也包括复杂的数据结构;4)使用支持各种模式的接口描述的子程序定义或者调用技术。 求两个n 阶方阵的相加C=A+B 的算法如下,分析其时间复杂度。 #define MAX 20 ∑∑∑∑-=-=-=-=====102101010*11n i n i n i n j n n n n n n n n )O()1O(1O(11i i j i j ==∑∑==))O(N )21O()O()O(21N 1=+=∑=∑==)(N N i i N i i 赋值,比较,算术运算,逻辑运算,读写单个变量(常量)只需1单位时间 2). 执行条件语句 if c then S1 else S2 的时间为TC +max(TS1,TS2). 3). 选择语句 case A of a1: s1;a2: s2;...; am: sm 需要的时间为 max (TS1,TS2 ,..., TSm ). 4). 访问数组的单个分量或纪录的单个域需要一个单位时间. 5). 执行for 循环语句的时间=执行循环体时间*循环次数. 6). while c do s (repeat s until c)语句时间=(Tc+Ts)*循环次数. 7). 用goto 从循环体内跳到循环体末或循环后面的语句时,不需额外时间 8). 过程或函数调用语句:对非递归调用,根据调用层次由里向外用规则1-7进行分析; 对递归调用,可建立关于T(n)的递归方程,求解该方程得到T(n).

图的算法实现

数据结构课程设计报告 设计题目:图的算法实现 班级: 学号: 姓名:

数据结构课程设计报告内容 一.课程设计题目 图的算法实现 【基本要求】 (1)建立一文件,将图的信息存在此文件中; (2)从此文件读入图的信息,建立邻接矩阵和邻接表; (3)实现Prim、Kruskal、Dijkstra和拓扑排序算法。 二.算法设计思想 (1)图的存储结构: 邻接矩阵:用两个数组分别存储数据元素(顶点)的信息和数据元素之间的关系(边或弧)的信息。 邻接表:对图中的每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。每个结点由3个域组成,其中邻接点域指示与顶点Vi邻接的点在图中的位置,链域指示下一条边或弧的结点;数据域存储和边或弧相关的信息。每个链表上附设一个表头结点。在表头结点中,除了设有链域指向链表中第一个结点之外,还设有存储顶点Vi的名或其他相关信息的数据域。 (2)prim算法 是一种求图的最小生成树的算法。 假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V)、TE={}开始。重复执行下列操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条权值最小的边(u0,v0)并入集合TE中,同时v0并入U,直到V=U为止。此时,TE中必有n-1条边,T=(V,TE)为G 的最小生成树。Prim算法的核心:始终保持TE中的边集构成一棵生成树。 (3)Kruskal算法 Kruskal算法是另一种求最小生成树的算法 他的基本思想是以边为主导地位,始终选择当前可用(所选的边不

能构成回路)的最小权植边。所以Kruskal算法的第一步是给所有的边按照从小到大的顺序排序。 具体实现过程如下: <1> 设一个有n个顶点的连通网络为G(V,E),最初先构造一个只有n个顶点,没有边的非连通图T={V,空},图中每个顶点自成一格连通分量。 <2> 在E中选择一条具有最小权植的边时,若该边的两个顶点落在不同的连通分量上,则将此边加入到T中;否则,即这条边的两个顶点落到同一连通分量上,则将此边舍去(此后永不选用这条边),重新选择一条权植最小的边。 <3> 如此重复下去,直到所有顶点在同一连通分量上为止。 (4)Dijkstar算法 Dijkstra算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时,需要指定起点s(即从顶点s 开始计算)。 此外,引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度),而U则是记录还未求出最短路径的顶点(以及该顶点到起点s的距离)。 初始时,S中只有起点s;U中是除s之外的顶点,并且U中顶点的路径是”起点s到该顶点的路径”。然后,从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。然后,再从U中找出路径最短的顶点,并将其加入到S中;接着,更新U中的顶点和顶点对应的路径。…重复该操作,直到遍历完所有顶点。 操作步骤 <1>初始时,S只包含起点s;U包含除s外的其他顶点,且U中顶点的距离为”起点s到该顶点的距离”[例如,U中顶点v的距离为(s,v)的长

基本的图算法

3. 要求对于邻接矩阵和邻接链表给出从G 到T G 的算法,并计算其复杂度。 对于邻接矩阵问题十分简单,直接求矩阵的转置即可,意味着把行换成列,把列换成行,对每行操作为O(|V|),需要对|V|行操作,时间复杂度为O (|V|^2)。 对于邻接链表,很明显要遍历链表的所有结点来看:如果对于u 结点其指向的结点中有v,则在新的链表中,创建一条从v 的链表指向u 的路径,因此需要遍历所有的链表元素,因此时间复杂度为O (|V|+|E|)。 3. 给出一个多图(多图为包含重复边和自循环边的图)去除冗余边的复杂度为O(V+E)的算法。 遍历邻接链表的所有结点,对于结点u ,如果其链表中还有u ,则去除所有的u ;如果还有重复的v ,则去除除了第一个v 以外的v 结点(这里的标记方法有很多种,可以用个数组)。这样的复杂度应该在O(V+E)。 4. 求解平方图的问题 算法如下:遍历G 的邻接矩阵,对于结点u ,如果存在u 到v 的路径,则在G^2的邻接矩阵u 中加入v,然后再遍历v 结点的链表,如果存在v 到w ,则将w 也加入到G^2的邻接矩阵u 中。 时间复杂度:这样,再遍历u 的时候,如果遍历到了u →v 这条边,那就在看v 的链表,而v 的链表里最多有|V|个结点,因此总的复杂度为O (|V|+|V|·|E|)。 6. 邻接矩阵求通用汇点(入度为|V|-1但是出度为0)的算法 算法如下:从(1,1)开始扫描邻接矩阵,如果(i,j )是0,则下一个扫描(i,j+1);如果(i ,j )是1,则下一个扫描(i+1,j ),当i 或者j 任一方到达|V|时停止。 这样,在最坏的情况下,扫描一行加一列或者一列加一行的结点,一共有2*|V|-1时间复杂度,因此为O(V)。 7. 关联矩阵,说明BB^T 每个元素是什么意思。 其中bij = -1 (如果边j 从结点i 发出) 1(如果边j 进入i 结点) 0(其他) 此处需要分类讨论:要明白B^T 中i 行相当于B 中第i 列。 ①BB^T 对角线上的元素,T B B (i ,i ) = ∑=| E |1 j 2 bij ,这样如果存在一条由i 发出或者进 入i 的边,都会在T B B (i ,i )中加一(因为就算是-1平方之后也是1),因此T B B (i ,i )就是代表由多少条边从i 发出或者进入。 ②BB^T 非对角线元素,T B B (i ,j ) = ∑=| |1 k E jk ik b b ,由公式或者读者自己画矩阵图可以 得出,如果k 边从i 发出从j 进入,或者反过来,bik*bjk 就等于-1,否则就为0。原因是i,j

算法分析与设计习题集整理

算法分析与设计习题集整理 第一章算法引论 一、填空题: 1、算法运行所需要的计算机资源的量,称为算法复杂性,主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征:输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣:时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为: O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法:自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求:正确性 和 可读性。 8、计算下面算法的时间复杂度记为: O(n 2) 。 for (i =1;i

新旧图幅编号

我国基本比例尺地形图分幅与编号的计算方法 韩丽蓉 (青海大学水电系,青海西宁 810016) 摘要:通过实例探讨了我国基本比例尺地形图分幅与编号的计算方法,此方法可以帮助使用者快速地由某点的经纬度值计算出高斯投影带带号和某比例尺地形图的图幅编号,在测绘工作中具有一定的实用性。 关键词:分幅;编号;六度带;中央子午线经度 中图分类号:K 99 文献标识码:B 文章编号:1006-8996(2006)06-0079-04 1 高斯分带投影 1.1 基本概念 在地理坐标中,经度是以经过英国格林威治天文台的子午面作为起算点(零度),自西向东逆时针至180°为东经,自东向西顺时针从0°至180°为西经,东、西经180°经线是重合的。地图投影是把不可展的 地球椭球体面上的经纬网,按照一定的数学法则转绘到平面上[1,2]。我国的8种国家基本比例尺地形图 (1:1000000~1:5000)中,除了1:1000000万地形图采用国际通用的正轴等角割圆锥投影外,其余7种国家基本比例尺地形图统一采用高斯投影。 高斯投影中限制长度变形的最有效方法是按一定经差将地球椭球面划分成若干投影带,通常投影分为六度带和三度带。分带时既要控制长度变形使其不大于测图误差,又要使带数不致过多以减少换带计算工作。我国1:500000~1:25000的比例尺地形图多采用六度带高斯投影,1:10000~1:5000的地形图采用三度带高斯投影。我国基本比例尺地形图的分幅与编号需要用到某地所在的1:1000000 地形图(经差6° )的中央子午线经度,故需计算该六度带的带号及中央子午线经度。1.2 投影带带号和中央子午线经度的计算方法 1.2.1 六度带 从格林威治零度经线起,每隔经差6°分为一个投影带,自西向东逆时针分带,全球依次编号为1,2, 3,……60,每带中间的子午线称为中央子午线[1,2]。 东半球从经度0°逆时针回算到东、西经180°,投影带号为1~30。假如知道东半球某地区的平均大地经度L 东,则其投影带带号M 东和中央子午线经度L 6东的计算公式为: M 东=[L 东Π6](取整数商)+1(有余数时);L 6东=(6M 东-3)° (东经)西半球投影带从东、西经180°逆时针回算到0°,投影带号为31~60,假如知道西半球某地区的平均大地经度L 西,则其投影带带号M 西和中央子午线经度L 6西的计算公式为: M 西=[(360°-L 西)Π6](取整数商)+1(有余数时)=[(180°-L 西)Π6](取整数商)+1(有余数时)+30;L 6西={360°-(6M 西-3)°}(西经) 1.2.2 三度带 自东经115°子午线起,每隔经差3°自西向东分带,依次编号为1,2,3,……120[1,2] 。 东半球有60个投影带,编号为1~60,假如知道东半球某地区的平均大地经度L 东,其投影带带号N 东和中央子午线经度L 3东的计算公式为: 收稿日期:2006-07-10 作者简介:韩丽蓉(1967—),女,撒拉族,青海循化人,副教授,硕士。第24卷 第6期2006年12月 青海大学学报(自然科学版)Journal of Qinghai University (Nature Science ) Vol 124No 16Dec 12006

图的最短路径算法的实现

数据结构课程设计报告 图的最短路径算法的实现 班级:计算机112班 姓名:李志龙 指导教师:郑剑 成绩:_______________ 信息工程学院 2013 年1 月11 日

目录 一、题目描述 -------------------------------------------------------------------- 1 1.1题目内容-------------------------------------------------------------------- 1 2.2题目要求-------------------------------------------------------------------- 1 二、设计概要 -------------------------------------------------------------------- 2 2.1程序的主要功能----------------------------------------------------------- 2 2.2数据结构-------------------------------------------------------------------- 2 2.3算法分析-------------------------------------------------------------------- 2 三、设计图示 -------------------------------------------------------------------- 4 四、详细设计 -------------------------------------------------------------------- 5 五、调试分析 -------------------------------------------------------------------- 8 六、运行结果 -------------------------------------------------------------------- 9 七、心得体会 ------------------------------------------------------------------- 11参考资料 ------------------------------------------------------------------------ 12

图的两种存储结构及基本算法

一、图的邻接矩阵存储 1.存储表示 #define vexnum 10 typedef struct{ vextype vexs[vexnum]; int arcs[vexnum][vexnum]; }mgraph; 2.建立无向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;ivexs[i]); for(i=0;iarcs[i][j]=0; for(k=0;karcs[i][j]=1; g->arcs[j][i]=1;} } 3.建立有向图的邻接矩阵算法 void creat(mgraph *g, int e){ for(i=0;ivexs[i]);

for(i=0;iarcs[i][j]=0; for(k=0;karcs[i][j]=w; } } 二、图的邻接表存储 1.邻接表存储表示 #define vexnum 10 typedef struct arcnode{ int adjvex; struct arcnode *nextarc; }Arcnode; typedef struct vnode{ vextype data; Arcnode *firstarc; }Vnode; typedef struct{ Vnode vertices[vexnum]; int vexnum,arcnum;

算法分析与设计-课程设计报告

XXXX大学 算法设计与分析课程设计报告 院(系): 年级: 姓名: 专业:计算机科学与技术 研究方向:互联网与网络技术 指导教师: XXXX 大学

目录 题目1 电梯调度 (1) 1.1 题目描述 (1) 1.2 算法文字描述 (1) 1.3 算法程序流程 (4) 1.4 算法的程序实现代码 (10) 题目2 切割木材 (12) 2.1题目描述 (12) 2.2算法文字描述 (12) 2.3算法程序流程 (13) 2.4算法的程序实现代码 (18) 题目3 设计题 (20) 3.1题目描述 (20) 3.2 输入要求 (20) 3.3输出要求 (20) 3.4样例输入 (20) 3.5样例输出 (20) 3.6测试样例输入 (21) 3.7测试样例输出 (21) 3.8算法实现的文字描述 (21) 3.9算法程序流程 (22) 3.10算法的程序实现代码 (23) 算法分析与设计课程总结 (26) 参考文献 (27)

题目1电梯调度 1.1 题目描述 一栋高达31层的写字楼只有一部电梯,其中电梯每走一层需花费4秒,并且在每一层楼停靠的时间为10秒,乘客上下一楼需要20秒,在此求解最后一位乘客到达目的楼层的最短时间以及具体的停靠计划。例如:此刻电梯停靠需求为4 5 10(有三位乘客,他们分别想去4楼、5楼和10楼),如果在每一层楼都停靠则三位乘客到达办公室所需要的时间为3*4=12秒、4*4+10=26秒、4*9+2*10=56秒,则最后一位乘客到达办公室的时间为56秒,相应的停靠计划为4 5 10均停靠。对于此测试用例电梯停靠计划方案:4 10,这样到第4楼的乘客所需时间为3*4=12秒,到第5楼的乘客所需时间为3*4+20=32秒,到第10楼的乘客所需时间为9*4+10=46秒,即最后到达目的楼层的顾客所需时间为46秒。 输入要求: 输入的第1行为整数n f1 f2 … fn,其中n表示有n层楼需要停靠,n=0表示没有更多的测试用例,程序终止运行。f1 f2 … fn表示需要停靠的楼层(n<=30,2<=f1

基本数字(精选)图像处理算法的matlab实现

基本数字图像处理算法的matlab实现 1.数字图像处理的简单介绍 所谓数字图像就是把传统图像的画面分割成为像素的小的离散点,各像素的灰度值也是用离散值来表示的。 数字图像处理是通过计算机对图像进行去除噪声、增强、复原、分割、提取特征等处理的方法和技术。 2.图像的显示与运算 2.1图像的显示 Matlab显示语句 imshow(I,[lowhigh])%图像正常显示 I为要显示的图像矩阵。,[lowhigh]为指定显示灰度图像的灰度范围。高于high的像素被显示成白色;低于low的像素被显示成黑色;介于high和low之间的像素被按比例拉伸后显示为各种等级的灰色。 subplot(m,n,p) 打开一个有m行n列图像位置的窗口,并将焦点位于第p个位置上。 2.2图像的运算 灰度化将彩色图像转化成为灰度图像的过程成为图像的灰度化处理。彩色图像中的每个像素的颜色有R、G、B三个分量决定,而每个分量有255中值可取,这样一个像素点可以有1600多万(255*255*255)的颜色的变化范围。而灰度图像是R、G、B三个分量相同的一种特殊的彩色图像,其一个像素点的变化范围为255种,所以在数字图像处理种一般先将各种格式的图像转变成灰度图像以使后续的图像的计算量变得少一些。灰度图像的描述与彩色图像一样仍然反映了整幅图像的整体和局部的色度和亮度等级的分布和特征。图像的灰度化处理可用两种方法来实现。

第一种方法使求出每个像素点的R、G、B三个分量的平均值,然后将这个平均值赋予给这个像素的三个分量。 第二种方法是根据YUV的颜色空间中,Y的分量的物理意义是点的亮度,由该值反映亮度等级,根据RGB和YUV颜色空间的变化关系可建立亮度Y与R、G、B三个颜色分量的对应:Y=0.3R+0.59G+0.11B,以这个亮度值表达图像的灰度值。 灰度是灰度级的函数,它表示图象中具有每种灰度级的象素的个数,反映图象中每种灰度出现的频率。 图像增强的目标是改进图片的质量,例如增加对比度,去掉模糊和噪声,修正几何畸变等;图像复原是在假定已知模糊或噪声的模型时,试图估计原图像的一种技术。 Matlab图像格式转换语句 rgb2gray(I) %从RGB图创建灰度图 imhist(I) %画灰度直方图 图像的线性变换 D B=f(D A)=f A*D A+f B Matlab源代码: I1=imread('F:\图片2.jpg'); subplot(2,2,1);imshow(I1);title('原图'); I2=rgb2gray(I1); %灰度化图像 subplot(2,2,2);imshow(I2);title('灰度化后图'); [M,N]=size(I2); subplot(2,2,3) [counts,x]=imhist(I2,60); %画灰度直方图 counts=counts/M/N; stem(x,counts);title('灰度直方图'); g=zeros(M,N);%图像增强

算法分析与设计

《算法分析与设计》2020年03月考试考前练习题 一、简答题 附:参考答案 1. 何谓P、NP、NPC问题。 解答: P(Polynomial问题):也即是多项式复杂程度的问题。 NP就是Non-deterministic Polynomial的问题,也即是多项式复杂程度的非确定性问题。 NPC(NP Complete)问题,这种问题只有把解域里面的所有可能都穷举了之后才能得出答案,这样的问题是NP里面最难的问题,这种问题就是NPC问题。 2. 动态规划算法的基本思想是什么?它和分治法有什么区别和联系? 解答: 动态规划算法的基本思想为:该方法的思路也是将待求解的大问题分成规模较小的子问题,但所得的各子问题之间有重复子问题,为了避免子问题的重复计算,可依自底向上的方式计算最优值,并根据子问题的最优值合并得到更大问题的最优值,进而可构造出所求问题的最优解。 分治法也是将待求解的大问题分成若干个规模较小的相同子问题,即该问题具有最优子结构性质。规模缩小到一定的程度就可以容易地解决。所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题;利用该问题分解出的子问题的解可以合并为该问题的解。 3. 贪心算法和动态规划算法都要求问题具有共同的性质是? 解答: 最优子结构性质。 4. 为什么用分治法设计的算法一般有递归调用? 解答: 子问题的规模还很大时,必须继续使用分治法,反复分治,必然要用到递归。 5. 简述分治法所能解决的问题一般应具有的特征。 解答: 1)该问题的规模缩小到一定的程度就可以容易地解决; 2)该问题具有最优子结构性质; 3)利用该问题分解出的子问题的解可以合并为该问题的解; 4)该问题所分解出的各个子问题是相互独立的。 6. 在回溯法中,为了避免无效的搜索,通常采用哪两种剪枝策略? 解答: 约束剪枝,限界剪枝。 7. 给定如下二分搜索算法,请分析算法的复杂性。 int BinarySearch(Type a[], const Type& x, int l, int r){ while (r >= l){ int m = (l+r)/2; if (x == a[m]) return m; if (x < a[m]) r = m-1; else l = m+1; }

相关主题
相关文档 最新文档