H. A fast algorithm for finding crosswalks using figure-ground segmentation

格式：pdf
大小：454.81 KB
文档页数：10

下载文档原格式

应用快速偶极子法与RACA法快速求解导体目标RCS

应用快速偶极子法与RACA法快速求解导体目标RCS胡倩倩;孙玉发【摘要】文章将快速偶极子法(fast dipole method,FDM)结合再压缩自适应交叉近似(recompressed adaptive cross approximation,RACA)算法应用于导体目标雷达散射截面(radar cross section,RCS)的计算.快速偶极子法是在等效偶极子法的基础上,将远场组相互作用的偶极子之间的距离通过泰勒级数展开,实现矩阵向量积的快速计算.为了进一步加快近场组互阻抗元素的填充,采用RACA算法对阻抗矩阵进行进一步压缩.与传统FDM相比,计算时间和内存得到了有效缩减,数值结果证明了该方法的有效性和精确性.%The fast dipole method(FDM)combined with recompressed adaptive cross approximation (RACA)algorithm is used to solve the radar cross section(RCS)for perfect conducting targets.T he FDM,which is based on the equivalent dipole-moment method(EDM),uses a simple Taylor's series to expand the distance between the interacting equivalent dipoles in far-field groups and realizes the fast calculation of matrix vector product.In order to speed up the calculation of mutual impedance ele-ments in the near-field groups,the RACA algorithm is used to further compress the impedance ma-trix.T he computational time and memory consumption of the proposed method are reduced effectively compared with the traditional FDM.Numerical results are presented to demonstrate the efficiency and accuracy of this method.【期刊名称】《合肥工业大学学报（自然科学版）》【年(卷),期】2018(041)002【总页数】4页(P207-210)【关键词】快速偶极子法(FDM);等效偶极子法;再压缩自适应交叉近似(RACA)算法;导体目标;雷达散射截面(RCS)【作者】胡倩倩;孙玉发【作者单位】安徽大学计算智能与信号处理教育部重点实验室,安徽合肥 230601;安徽大学计算智能与信号处理教育部重点实验室,安徽合肥 230601【正文语种】中文【中图分类】TN011矩量法(method of moments,MoM)在雷达散射截面(radar cross section,RCS)的计算、电磁环境的预测问题中有着广泛的应用,但是,随着目标电尺寸的不断增大,计算复杂度和内存需求迅速增加,普通计算机难以负担。

《人工智能-一种现代方法》第四版习题答案

Chapter 2
2.1 Define in your own words the following terms: agent, agent function, agent program, rationality, reflex agent, model-based agent, goal-based agent, utility-based agent, learning agent. The following are just some of the many possible definitions that can be written:
1.11 “surely computers cannot be intelligent-they can do only what their programmers tell them.” Is the latter statement true, and does it imply the former? This depends on your definition of “intelligent” and “tell.” In one sense computers only do what the programmers command them to do, but in another sense what the programmers consciously tells the computer to do often has very little to do with what the computer actually does. Anyone who has written a program with an ornery bug knows this, as does anyone who has written a successful machine learning program. So in one sense Samuel “told” the computer “learn to play checkers better than I do, and then play that way,” but in another sense he told the computer “follow this learning algorithm” and it learned to play. So we’re left in the situation where you may or may not consider learning to play checkers to be s sign of intelligence (or you may think that learning to play in the right way requires intelligence, but not in this way), and you may think the intelligence resides in the programmer or in the computer

A Sequential Algorithm for Generating Random Graphs

A Sequential Algorithm for Generating Random Graphs
Mohsen Bd Amin Saberi1
arXiv:cs/0702124v4 [] 16 Jun 2007
Stanford University {bayati,saberi}@ 2 Yonsei University jehkim@yonsei.ac.kr
(FPRAS) for generating random graphs; this we can do in almost linear time. An FPRAS provides an arbitrary close approximaiton in time that depends only polynomially on the input size and the desired error. (For precise deﬁnitions of this, see Section 2.) Recently, sequential importance sampling (SIS) has been suggested as a more suitable approach for designing fast algorithms for this and other similar problems [18, 13, 35, 6]. Chen et al. [18] used the SIS method to generate bipartite graphs with a given degree sequence. Later Blitzstein and Diaconis [13] used a similar approach to generate general graphs. Almost all existing work on SIS method are justiﬁed only through simulations and for some special cases counter examples have been proposed [11]. However the simplicity of these algorithms and their great performance in several instances, suggest further study of the SIS method is necessary. Our Result. Let d1 , . . . , dn be non-negative integers given for the degree sequence n and let i=1 di = 2m. Our algorithm is as follows: start with an empty graph and sequentially add edges between pairs of non-adjacent vertices. In every step of the procedure, the probability that an edge is added between two distinct ˆj (1 − di dj /4m) where d ˆi and d ˆj denote ˆi d vertices i and j is proportional to d the remaining degrees of vertices i and j . We will show that our algorithm produces an asymptotically uniform sample with running time of O(m dmax ) when maximum degree is of O(m1/4−τ ) and τ is any positive constant. Then we use a simple SIS method to obtain an FPRAS for any ep, δ > 0 with running time O(m dmax ǫ−2 log(1/δ )) for generating graphs with dmax = O(m1/4−τ ). Moreover, we show that for d = O(n1/2−τ ), our algorithm can generate an asymptotically uniform d-regular graph. Our results are improving the bounds of Kim and Vu [34] and Steger and Wormald [45] for regular graphs. Related Work. McKay and Wormald [37, 39] give asymptotic estimates for number of graphs within the range dmax = O(m1/3−τ ). But, the error terms in their estimates are larger than what is needed to apply Jerrum, Valiant and Vazirani’s [25] reduction to achieve asymptotic sampling. Jerrum and Sinclair [26] however, use a random walk on the self-reducibility tree and give an FPRAS for sampling graphs with maximum degree of o(m1/4 ). The running time of their algorithm is O(m3 n2 ǫ−2 log(1/δ )) [44]. A diﬀerent random walk studied by [27, 28, 10] gives an FPRAS for random generation for all degree sequences for bipartite graphs and almost all degree sequences for general graphs. However the running time of these algorithms is at least O(n4 m3 dmax log5 (n2 /ǫ)ǫ−2 log(1/δ )). For the weaker problem of generating asymptotically uniform samples (not an FPRAS) the best algorithm was given by McKay and Wormald’s switching technique on conﬁguration model [38]. Their algorithm works for graphs 2 2 3 2 with d3 max =O(m / i di ) with average running i di ) and dmax = o(m + 2 2 2 4 time of O(m + ( i di ) ). This leads to O(n d ) average running time for dregular graphs with d = o(n1/3 ). Very recently and independently from our work, Blanchet [12] have used McKay’s estimate and SIS technique to obtain an FPRAS with running time O(m2 ) for sampling bipartite graphs with given

移相相关法计算相位差的研究

移相相关法计算相位差的研究刘玉周;赵斌【摘要】为了提高相位式测距仪的测量精度，采用移相相关方法来估计两同频正弦信号的相位差。

首先将每路信号移相2π后和原信号做相关来计算自相关，以减少噪声的影响；其次用少许数据初步估算相位差，并将一路信号移相，使两路信号的相位差移到π/2（或3π/2）附近；然后用较多的采样数据计算两路信号的相位差，将结果再减去移相量得到最终的相位差。

同时分析了频率误差对相位差计算精度的影响，进行了理论分析和仿真实验验证。

结果表明，该方法计算的误差大大减小。

这对提高测距仪的测量精度是有帮助的。

%In order to improve the accuracy of a phase-shift range finder , a phase-difference algorithm based on phase-shift correlation analysis was proposed to estimate the phase-difference between two sinusoidal signals with same frequency .For reducing the influence of noise , the autocorrelation between the original and 2πshifted signal was calculated firstly.Secondly, the phase difference was estimated approximately with a few sampled data and the initial phase of one signal was shifted by Δθto make the phase difference between two signals to be near π/2(or 3π/2).Then, the phase-difference was calculated with whole set of data by correlation method and the final phase difference was obtained by subtracting Δθ.The influence of frequency error was analyzed .Theoretical analysis and simulation shows that the error of this method is greatly reduced .The proposed method can improve the accuracy of a range finder .【期刊名称】《激光技术》【年(卷),期】2014(000)005【总页数】5页(P638-642)【关键词】测量与计量;移相相关法;相位差;频率误差【作者】刘玉周;赵斌【作者单位】华中科技大学机械科学与工程学院仪器系，武汉430074;华中科技大学机械科学与工程学院仪器系，武汉430074【正文语种】中文【中图分类】TH741相位式激光测距在3-D成像［1］、机器人导航［2］、表面检测［3］等领域有着广泛的应用，它通过测量光波往返的相位差来计算时间延迟从而计算待测距离［4-5］。

a星算法预处理路径

a星算法预处理路径A*算法是一种启发式搜索算法，用于在图形空间中找到两个点之间的最短路路径。

除了起点和终点之外，它还需要一个评估函数来评估每个节点到目标节点的距离。

因为这个评估值是启发式的，所以A*算法能够在搜索空间中快速找到最优解。

与其他搜索算法不同的是，A*算法可以在不搜索整个搜索空间的情况下，找到最短路径。

A*算法的核心思想是使用一个评估函数f(n)来评估每个节点n的最小反向代价估计，这个评估函数的值是从起点到当前节点的代价g(n)和从当前节点到目标节点的最小估计代价h(n)之和，即f(n)=g(n)+h(n)。

其中h(n) 是它到目标节点的估计距离，g(n)是从起点到节点n的实际代价。

A*算法的预处理路径是将整个图形空间进行分类，将每个点都归入不同的类别中。

这样做的目的是为了让算法能够更快地搜索到目标节点。

预处理路径的过程一般包括两个步骤：建立地图和预处理路径。

建立地图时需要将地图分为不同的区域，确定每个区域的关系，并将每个区域编号。

这部分需要涵盖一定的算法和数据结构知识，如图形数据结构、二维数组、树、模拟人类思维过程的“分而治之”等。

在将地图分为不同的区域时需要考虑地图是否要求精细化处理，比如是否需要考虑建筑物的复杂形状、地形的起伏等因素。

同时，也要考虑到预处理路径的计算效率，是否需要对地图进行简化处理。

预处理路径是指在搜索之前，通过一些算法来计算出每个点到目标点的距离，这样可以加速搜索过程。

这个过程涉及到的算法有 Dijkstra 算法、BFS 算法、Floyd 算法等。

其中Dijkstra算法是一种确定路径的算法，可以用于单源最短路径问题。

BFS算法是一种广度优先搜索算法，在小型地图上表现很好，但在大型地图上会面临内存瓶颈。

Floyd算法是一种动态规划算法，可以用于求任意两点之间的最短路径，但计算量比较大。

综合考虑，一般使用 A* 算法来计算预处理路径。

在预处理路径时，需要考虑选择合适的启发式算法来评估每个节点的距离，同时需要考虑到搜索空间的大小和节点数量。

A星路径寻找算法的应用

摘
要
A*算法是一种启发式的搜索算法。使用 A*算法能够快速地在游戏地图中得到一条最优路径。本文通过对 A*算法的分析，结合面向对象的思想，用 C#语言实现可重用的 A*类库，并应用于一个小游戏中。
关键词
A*算法；代价；二叉堆；启发函数
I
Abstract
A * algorithm is a heuristic search algorithm. Using the A * algorithm can quickly get the optimal path in the game map. Based on the A* algorithm analysis, combined with object-oriented thinking, an A* reusable class librariy with the C # language is implemented and applied it to a small game.
Key words
A* Algorithm; Cost; Binary Heap; Heuristic Function
II
目
录
1 引言.................................................................................................................................................. 1 2 算法原理.......................................................................................................................................... 1 2.1 算法基本概念.......................................................................................................................1 2.1.1 地图（搜索空间）.....................................................................................................1 2.1.2 A*结点........................................................................................................................ 2 2.1.3 代价............................................................................................................................2 2.2 A* 算法................................................................................................................................. 2 2.2.1 启发函数与估价函数................................................................................................2 2.2.2 Open 表与 Closed 表..................................................................................................2 2.2.3 伪代码........................................................................................................................3 3 算法设计.......................................................................................................................................... 4 3.1 二叉堆（Binary Heap）...................................................................................................... 4 3.1.1 数据存储和方法........................................................................................................4 3.1.2 添加元素....................................................................................................................4 3.1.3 获取堆顶元素............................................................................................................5 3.1.4 删除堆顶元素............................................................................................................5 3.1.5 查找指定元素............................................................................................................7 3.1.6 获取和替换元素........................................................................................................7 3.2 AStarNode 抽象类............................................................................................................... 10 3.2.1 属性..........................................................................................................................10 3.2.2 方法..........................................................................................................................10 3.3 AStar 类................................................................................................................................ 11 3.3.1 属性.......................................................................................................................... 11 3.3.2 方法.......................................................................................................................... 11 3.4 AStarNode2D 类.................................................................................................................. 13 3.4.1 属性..........................................................................................................................14

带有模式选择的改进的方向性菱形搜索算法

ｄｉｅｔｏａａｎｌｏｔｍ．ｅｓｍｕａｉｎｒｓｌｓｓｗｈａｏｓｄａｇｒｔｍａｅｕｅｓａｃｉｔｅｃｅｌｎｅ— ｒｃｉｎｌｄｉｍｏｄａｇｒｈＴｈｉｌｔｏｅｕｔｈｏｔｔｐｒｐｏｅｌｏｉｈｃｎｒｄｃｅｒｈｐｏｎｍｉｎｔｙａｄｒｉ
（ｃｏｌｆＣｍｕｅＳｉｃＳｈｏｏｏｐｔｃｎｅ＆ＴｌｏｍｕｉｔｎＥｇｎｅｉＪａｇｕＵｉｒｔＺｅＹｎｉｎｓ１０３，ｈｎ）ｒｅｅｃｍｎａｉｎｉｒｇ，ｉｕｓｎｖｓｙ，ｈｗａｇＪｇｕ２２１Ｃｉａｅｃｏｅｎｅｉａ
中图分类号：Ｔ９１７Ｎ１．３文献标志码：Ａ文章编号：１０ — ６５２１）１０９ — ３０１３９（０００ — ３３０
ｄｉ１．９９ｉｎ１０ —６５２１．１１８ｏ：０３６ｄ．ｓ．０１３９．０００．ｓ１
朱小龙，罗
摘
星，陈祖爵
（江苏大学计算机科学与通信工程学院，江苏镇江２２１）１０３要：针对Ｈ２４ＡＣ标准的多模式运动估计算法编码模式复杂、算量大的不足，出了一种带有模式选．６／Ｖ计提
择的方向性菱形搜索算法。基于宏块最佳编码模式的统计分析，运动特征的不同进行分类，运动估计的直按将
ＡｂｔａｔＦｒｍｕｔｍｏｅｍｏｉｎｅｔｔｎａｇｒｔｆＨ，６／ｓｒｃ：ｏｌ — ｄｔｓｉｉｌｏｉｉｏｍａｏｈｍｏ２４ＡＶＣｓａｄｒａｈｒｂｅｆｏｌａｅｏｉｇｍｏｅｔｎｔｄｃｄｎｄｃｃ

astar寻路算法原理 -回复

astar寻路算法原理-回复A*寻路算法原理及步骤一、简介A*（A-Star）寻路算法是一种常用的路径规划算法，用于找到两个点之间的最短路径。

它综合了Dijkstra算法和贪心算法的优点，既考虑了每个节点的代价，也考虑了每个节点到目标节点的预估代价。

本文将一步一步详细介绍A*寻路算法的原理和步骤。

二、原理A*算法的核心思想是使用一个估算函数来预测从起始节点到目标节点的代价，并在遍历过程中选择最小代价节点来进行扩展。

该算法综合了代价函数和启发函数的信息，以更快地找到最短路径。

其具体步骤如下：1. 初始化将起始节点添加到一个开放列表(open list)中，开放列表存放待扩展的节点。

同时，创建一个空的闭合列表(closed list)，用于存放已扩展过的节点。

2. 循环操作进入循环操作，直到开放列表为空或找到目标节点。

在每次循环中，选择开放列表中代价最小的节点进行扩展。

3. 节点扩展取开放列表中代价最小的节点，将其从开放列表中删除，并加入到闭合列表中。

然后，获取该节点的相邻节点，计算它们的代价和预估代价，并更新它们的代价值和路径。

4. 判断相邻节点对于每个相邻节点，判断它们是否在开放列表或闭合列表中。

若在闭合列表，则跳过该节点；若在开放列表，比较新路径与旧路径的代价，若新路径更好，则更新代价和路径；否则，不做任何操作。

5. 添加新节点对于不在开放列表中的相邻节点，将它们添加到开放列表中，并计算它们的代价和预估代价。

6. 重复操作重复步骤2至5，直到开放列表为空或找到目标节点。

若开放列表为空，则无法找到路径；若找到目标节点，则回溯路径，回到起始节点。

三、关键要点在上述步骤中，有几个关键要点需要注意：1. 代价函数代价函数用于计算节点到起始节点的实际代价，包括走过的距离、障碍物等影响因素。

根据具体情况，可以自定义代价函数。

2. 启发函数启发函数用于估算节点到目标节点的代价，即预测代价。

常见的启发函数有曼哈顿距离、欧几里得距离等，根据实际情况选择合适的启发函数。

[Archer, 88]

R EFERENCES[Agha et al., 93]G.Agha, P.Wegner and A.Yonezawa (Eds.), “Research Directions in Concurrent Object-Orientated Programming”, MIT Press, 1993.[Alexander and Davis, 91]L.Alexander and A.Davis, “Criteria for Selecting Software Process Models”, In Proceedings of the 15th Annual International Computer Software and Applications Conference (COMPSAC), IEEE Computer Society, 1991.[Alty et al., 94]J.Alty, D.Griffiths, N.Jennings and E.Mamdani, “ADEPT - Advanced Decision Support Environment for Process Tasks: Overview and Architecture”, In Proceedings of the 1994 BCS Expert Systems conference, British Computer Society, 1994.[Alty, 97]J.Alty, (Lutchi Research Centre, Loughborough University), Personal Communication, March 1997.[Archer, 88]S.Archer, “Qualitative Research and Epistemological Problems of the Management Disciplines”, in A.Petigrew (Ed.), “Competitiveness and the Management Process”, Blackwell, 1988.[Bander et al., 88]J.Bander, J.Edwards, C.Jones and D.Hannaford, “Practical Engineering of Knowledge Based Systems”, Information and Software Technology, Vol. 30, No. 5, 1988.[Bass et al., 98]L.Bass, P.Clements and R.Kazman, “Software Architecture in Practice”, Addison Wesley, 1998.[Bates et al., 92]J.Bates, A.Bryan-Loyall and W.Scott-Reilly, “Integrating reactivity, goals, and emotion in a broad agent”, Technical Report CMU-CS-92-142, Carnegie-Mellon University, 1992.[Benech and Desprats, 97]D.Benech and T.Desprats, “A KQML-CORBA based Architecture for Intelligent Agents Communication in Cooperative Service and Network Management”, in Proceedings of IFIP / IEEE International Conference on Management of Multimedia Networks and Services, 1997.[Berson, 92]A.Berson, “Client/Server Architecture”, McGraw-Hill, 1992.[Bochsler, 88]D.Bochsler, “A Project Management Approach to Expert System Applications”, In Proceedings of ISA’88, 1988.[Boland and Hirschheim, 87]R.Boland and R.Hirschheim (Eds.), “Critical Issues in Information Systems Research”Wiley, 1987.[Bonczek et al., 81]R.H.Bonczek, C.W.Holsapple, and A.Whinston, “Foundations of Decision Support Systems”, Academic Press, 1981.[Booch, 94]G.Booch, “Object Orientated Analysis and Design With Applications” (2nd Edition), Addison Wesley, 1994.[Boy, 91]G.Boy, “Intelligent Assistant Systems”, Academic Press, 1991.[Bradshaw, 97]J.Bradshaw (Ed.), “Software Agents”, MIT Press, 1997.[Brooks, 87]F.P.Brooks, “No Silver Bullet: Essence and Accidents of Software Engineering”, IEEE Computer, 20 (4), 1987.[Brooks, 89]R.Brooks, “A Robot that Walks: Emergent Behaviors from a Carefully Evolved Network”, Journal of Neural Computation, Vol.1, No.2, 1989.[Brown et al., 82]J.Brown, R.Burton, and J.deKleer, “Pedagogical, Natural Language and Knowledge Engineering Techniques in SOPHIE”, In D.Sleeman and J.Brown (Eds.), “Intelligent Tutoring Systems”, Academic Press, 1982.[Brownston et al., 85]L.Brownston, R.Farrell and E.Kant, “Programming Expert Systems in OPS5- An Introduction to Rule-Based Programming”, Addison-Wesley, 1985.[Buchanan and Feigenbaum, 78]B.Buchanan and E.Feigenbaum, “DENDRAL and Meta-DENDRAL: Their Applications Dimension”, Artificial Intelligence, 11, 1978.[Buchanan et al., 83]B.Buchanan, D.Barstow, R.Bechtel, J.Bennet, W.Clancey,C.Kulikowski, T.Mitchell andD.Waterman, “Constructing Expert System”, in F.Hayes-Roth, D.Waterman and D.Lenat (Eds.), “Building Expert Systems”, Addison-Wesley, 1983.[Budd, 98]M.Budd (Ed), “Ovum Evaluates: CASE Products”, Ovum, 1998.[Caglayan and Harrison, 97]A.Caglayan and C.Harrison, “Agent Sourcebook”, Wiley, 1997.[Catalyst, 99]“Plan Your Projects Better”, Catalyst Software, 1999.[Cawsey, 98]A.Cawsey, “The Essenance of Artificial Intelligence”, Prentice Hall, 1998.[Clocksin and Mellish, 81]W.F.Clocksin and C.S. Mellish, “Programming in Prolog”, Springer-Verlag, 1981.[Cohen and Levesque, 97]P.Cohen and H.Levesque, “Communicative Actions for Artificial Agents”, in J.Bradshaw (Ed.), “Software Agents”, MIT Press, 1997.[Cooke and McDonald, 86]N.Cooke and J.McDonald, “A Formal Methodology for Acquiring and Representing Expert Knowledge”, In Proceedings of the IEEE, pp. 1422-30, IEEE, 1986.[Coutaz, 87]J.Coutaz, “PAC - An Object Orientated Model for Dialog Design”, in H.Bullinger and B.Shackel (Eds.), “Human Computer Interaction - INTERACT’87”, North-Holland, 1987.[Corkhill, 97]D.Corkhill, “Countdown to Success: Dynamic Objects, GBB and RADARSAT-1”, Communications of the ACM, Vol. 40, No.5, 1997.[Cornford, 96]T.Cornford, “Project Research in Information Systems: A Students Guide”, Macmillan, 1996.[Cox, 94]B.Cox, “Explaining and Understanding Engineering Problems - An Intelligent Tutoring Approach”, International Journal of Engineering Education, Vol.10, No.3, 1994.[Dennett, 91]D.Dennett, “Consciousness Explained”, Penguin Press, 1991.[DTI, 92]Department of Trade and Industry, “KBS: Survey of UK Applications”, Touche Ross and Co., 1992.[Eilon, 79]S.Eilon, “Seven Faces of Research”, In S.Eilon, “Aspects of Management” (2nd Edition), Pergamon Press, 1979.[Engelmore, 93]R.Engelmore (Ed.), “JTEC Panel on Knowledge-based Systems in Japan”, ARPA Technical Report, Advanced Projects Research Agency, 1993.[Englemore and Morgan, 88]R. Englemore, T.Morgan, “Blackboard Systems”, Addison Wesley, 1988.[Fairclough, 96]J.Fairclough (Ed.), “Software Project Management”, in “Software Engineering Guides”, Prentice Hall, 1996[Finin et al., 97]T.Finin, brou, and J.Mayfield, “KQML as an agent communication language”, in J.Bradshaw (Ed.), “Software Agents”, MIT Press, 1997.[Finkelstein et al., 94]A.Finkelstein, J.Kramer andB.Nuseibeh (Eds.), “Software Process Modelling and Technology”, Research Studies Press, 1994.[Fischer, 87]G.Fischer, “A Critic for LISP”, In Proceedings of the 10th International Joint Conference on Artificial Intelligence, Los Altos, USA, Morgan Kaufman, 1987.[Fischer et al., 91]G.Fischer, A.C.Lemke, T.Mastaglio, A.Morch, “The Role of Critiquing in Cooperative Problem Solving”, ACM Transactions on Information Systems, April 1991.[Fodor, 83]J.Fodor, “The Modularity of Mind”, MIT Press, 1983.[Forgy, 82]C.Forgy, “Rete: A Fast Algorithm for the Many Pattern / Many Object Pattern Match Problem”, Artificial Intelligence, No. 19, 1982.[Fowler , 97]M.Fowler, “UML Distilled - Applying the Standard Object Modelling Language”, Addison Wesley, 1997.[Frasson and Gauthier, 86]C.Frasson and G.Gauthier (Eds.), “Intelligent Turoring Systems - Proceedings of the Third International Conference (ITS’96)”, Lecture Notes in Computer Science 1086, Springer, 1996.[Friedman-Hill, 99]E.J.Friedman-Hill, “Jess - The Java Expert System Shell”, User Manual version5.01b1, Sandia National Laboratories, USA, 1999.[Galliers, 92]R.Galliers, “Choosing Appropriate Information Systems Research Methods”, in H.Nissen (Ed), “Information Systems Research: Contemporary Approaches and Emergent Traditions, North-Holland, 1992.[Genesereth and Fikes, 92]M.Genesereth and R.Fikes, “Knowledge Interchange Format Version 3 Reference Manual”, Technical Report 92-1, Logic Group, Stanford University, 1992.[Genesereth and Ketchpel, 94]M.Genesereth and S.Ketchpel, “Software Agents”, Communications of the ACM, Vol. 37, No. 7, 1994.[Giarratano and Riley, 94]J.Giarratano and G.Riley, “Expert Systems - Principles and Programming”, PWS Publishing Company, 1994.[Goal, 95]“The GOAL Project”, ESPRIT 6283 - Generic Object-Oriented Multi-Application Project Management Tool for Large Inter-Organisational Projects, Public Report, 1995.[Gosling and McGilton, 96]J.Gosling and H.McGilton, “The Java Language Environment”, White Paper, Sun Microsystems, May 1996.[Gupta et al., 96]S.Gupta, W.Regli and D.Nau, “Integrating DFM with CAD through Design Critiquing”, Concurrent Engineering, Vol. 2, No. 2, 1996.[Grosz and Davis, 94]B.Grosz and R.Davis (Eds.), “A Report to APRA on Twenty-First Century Intelligent Systems”, American Association for Artificial Intelligence, 1994.[Hall, 97a]C.Hall (Ed.), “Intelligent Software Strategies”, Cutter Information Corp., Summer 1997.[Hall, 97b]C.Hall (Ed.), “Intelligent Software Strategies”, Cutter Information Corp., Fall 1997.[Hampton, 97]“A Buyer Guide to Selecting Project Management Software”, The Hampton Group, 1997.[Hayes-Roth, 83]B.Hayes-Roth, “The Blackboard Architecture - A Generic Framework for Problem Solving?”, Technical Report, HPP-83-30, Stanford University, 1983.[Hebb, 49]D.Hebb, “The Organisation of Behavior”, Wiley, 1949.[Heck and Mitchell, 96]M.Heck and K.Mitchell, “Project Management Solutions”, InfoWorld, Vol. 18, Issue 23, 1996.[Henry, 94]W.Henry, “Software Project Risk Management: A Support Tool”, M.Sc. Thesis, Dublin City University, 1994.[Hodges and Rogers, 97]J.Hodges and S.Rogers, “Cross-Industry Application: 1997 Worldwide Markets and Trends”, Report 13705, International Data Corporation, 1997.[Hughes and Cotterall, 99]B.Hughes and M.Cotterall, “Software Project Management” (2nd Edition), McGraw-Hill, 1999.[Humphrey, 89]W.Humphrey, “Managing the Software Process”, Addison-Wesley, 1989.[Humphrey, 95]W.Humphrey, “A Discipline for Software Engineering”, Addison-Wesley, 1995.[Hunt, 98]J.Hunt, “Tooled up for Java”, SIGS Application Development Advisor, Vol. 2, No. 2, 1988.[Huhns and Sing, 97]M.Huhns and M.Sing, “Conversational Agents”, IEEE Internet Computing, Vol. 1, No. 2, 1997.[Jackson, 90]P.Jackson, “Introduction to Expert Systems” (2nd edition), Addison-Wesley, 1990.[Jeffery and Votta, 99]R.Jeffery and L.Votta, “Guest Editors Special Section Introduction”, IEEE Transactions on Software Engineering, Vol. 25, No. 4, 1999.[Jenkins et al., 87]J.O.Jenkins, R.Verbruggen and M.Bosco, “Integrated Management Process Workbench (IMPW): Intelligent assistance for the Software Project Manager”, In Proceedings of CASE’87 - 1st International Workshop on Computer-Aided Software Engineering, Cambridge, USA, 1987.[Jennings et al., 96a]N.Jennings, J.Corera, resgoiti, E.Mamdani, F.Perriollat, P.Skarek and L.Varga,“Using ARCHON to develop real-world DAI applications for electricity transportation management and particle accelerator control”, IEEE Expert, Vol. 11, No. 6, 1996.[Jennings et al., 96b]N.Jennings, P.Faratin, T.Norman, P.O’Brien, M.Wiegand, C.Voudouris, J.Alty, T.Miah, E.Mamdani, “ADEPT: Managing Business Processes using Intelligent Agents”, In Proceedings of the 1996 BCS Expert Systems conference, BCS, 1996.[Jones, 94]M.Jones, “Project Management Report”, Cambridge Market Intelligence, 1994.[Kamsteeg and Blerman, 89]P.Kamsteeg and D.Blerman, “Differences Between Expert Systems and Domain Components of Intelligent Tutoring Systems”, in J.Cambell and J.Cuena (Eds.),“Perspectives in Artificial Intelligence”, Wiley, 1989.[Kaplan and Maxwell, 94]B.Kaplan, and J.Maxwell, “Qualitative Research Methods for Evaluating Computer Information Systems”, in J.Anderson,C.Aydin and S.Jay (Eds.), “Evaluating Health Care Information Systems: Methods and Applications”, Sage, 1994.[Kawaguchi et al., 91]A.Kawaguchi, H.Motoda and R.Mizoguchi, “Interview Based Knowledge Acquisition Using Dynamic Analysis”, IEE Expert, Vol. 6, No. 5, 1991[Keen, 91]P.Keen, “Relevance and Rigour in Information Systems Research: Improving Quality, Confidence, Cohesion and Impact”, in H.Nissen (Ed), “Information Systems Research: Contemporary Approaches and Emergent Traditions, North-Holland, 1992.[Klein and Methlie, 95]M.Klein and L.B.Methlie, “Knowledge Based Decision Support Systems with Applications in Business” (2nd edition), John Wiley & Sons, 1995.[Lange and Oshima, 97]nge and M.Oshima, “Programming Mobile Agents in Java with the Java Aglet API”, White Paper, IBM Japan, 1997.[Lederberg, 87]J.Lederberg, “How DENDRAL was Conceived and Born”, ACM Symposium on the History of Medical Informatics, National Library of Medicine, 1987.[Leonard, 98]A.Leonard, “Bots - The Origin of New Species”, Penguin, 1998.[Lesnick and Moore, 97]L.Lesnick and R.Moore, “Creating Cool Intelligent Agents for the Net”, IDG Books, 1997.[Luger and Stubblefield, 89]G.F.Luger and W.A.Stubblefield, “Artificial Intelligence and the Design of Expert Systems”, Benjamin-Cummings Publishing, 1989.[Luger and Stubblefield, 98]G.Luger and W.Stubblefield, “Artificial Intelligence - Structures and Strategies for Complex Problem Solving”, Addison Wesley, 1998.[Maes, 97]P.Maes, “Software Agents”, In Proceedings of the Unicom conference on Agents and Intelligent User Interfaces, Unicom, 1997.[Mair, 92]P.Mair, “CASE: A State of the Market Report”, Unicom, 1992.[Mallach, 94]E.Mallach, “Understanding Decision Support Systems and Expert Systems”, Irwin, 1994.[Mayfield et al., 95]J.Mayfield, brou, T.Finin, “Evaluation of KQML as an Agent Communication Language”, in M.Wooldridge, J.Muller, M.Tambe (Eds.), “Intelligent Agents II: Agents Theories, Architectures and Languages”, Lecture Notes in Computer Science 1037, Springer Verlag, 1995.[Microsoft, 97]“Introduction to Microsoft Agent”, White Paper, Microsoft Corporation, August 1997.[Miller, 97]ler, “I Dream of Genie: Microsoft’s new active agent control can grant your wish”, Lecture presented at Microsoft SiteBuilder Conference, 1997.[Minsky, 85]M.Minsky, “The Society of Mind”, Simon and Schuster, 1985.[Montgomery, 88]A.Montgomery, “Gemini - Government Expert Systems”, In Proceedings of the 1988 BCS Expert Systems conference, British Computer Society, 1988.[Moynihan et al., 94]T.Moynihan, J.Power, W.Henry, “A Critiquing System Architecture for Software Risk Management”, In Proceedings of 5th European Software Control and Metrics conference (ESCOM), Italy, May 1994.[Muller et al., 99]J.P.Muller, M.P.Singh and A.S.Rao (Eds.), “Intelligent Agents V: Agents Theories, Architectures and Languages”, LNCS 1555, Springer Verlag, 1999.[Mumford et al., 84]E.Mumford, R.Hirschheim, G.Fitzgerald and A.Wood-Harper (Eds.) “Research Methods in Information Systems”, Proceedings of the IFIP WG 8.2 Colloquium, North-Holland, 1984.[OMG, 96]“CORBA: Architecture and Specification”, Object Management Group, 1996.[O’Connell, 96]F.O’Connell, “How To Run Successful Projects II”, Prentice Hall, 1996.[O’Connor et al., 97a]R.O'Connor, T.Moynihan, T.Renault and belles, “PROMPTER - A Decision Support Tool for Software Project Management”, Technical Report CA-2997, Dublin City University, 1997.[O’Connor et al., 97b]R.O'Connor, T.Renault, C.Floch, T.Moynihan and belles, “Prompter - A Decision Support Tool using Distributed Intelligent Agents”, In Proceedings of 9th International Conference on Artificial Intelligence Applications, England, 1997.[O’Connor, 98]R.O’Connor, “A Multi-Agent Approach to Knowledge Base Implementation”, In Proceedings of the International Postgraduate Research Student Conference, Dublin, Ireland, 1998.[O’Connor and Jenkins, 98]R.O'Connor and J.O.Jenkins, “Supporting Effective Software Project Management and Control by the use of Intelligent Knowledge-based Guidance”, In Proceedings of 9th European Software Control and Metrics conference (ESCOM), pp. 133 - 141, Rome, Italy, 1998.[O'Connor and Moynihan, 98]R.O'Connor and T.Moynihan, “A Multi-Agent Approach to Project Planning”, In Proceedings of 10th International Conference on Artificial Intelligence Applications (EXPERSYS), Virgina, USA, 1998.[O’Connor and Renault, 98]R.O’Connor and T.Renault, “Designing an Internet Enabled Decision Support Tool in the Domain of Software Project Management”, In Proceedings of the International Symposium on Engineering of Intelligent Systems, Spain, 1998.[O’Connor and Jenkins, 99a]R.O'Connor and J.O.Jenkins, “Intelligent Project Guidance”, In Proceedings of 10th European Software Control and Metrics conference (ESCOM), pp. 27 - 36, Herstmonceux, England, 1999.[O’Connor and Jenkins, 99b]R.O'Connor and J.O.Jenkins, “Using Agents for Distributed Software Project Management”, In Proceedings of 8th International Workshops on Enabling Technologies: Infrastructures for Collaborative Enterprises, IEEE Computer Society Press, USA, 1999.[Ould, 90]M.Ould, “Strategies for Software Engineering: The Management of Risk and Quality”, Wiley, 1990.[Orfali et al., 99]R.Orfali, D.Harkey and J.Edwards, “Client/Server Survival Guide”, Wiley, 1999.[Orfali and Harkey, 98]R.Orfali and D.Harkey, “Client/Server Programming with Java and CORBA”, Wiley, 1998.[Orlikowski and Baroudi, 91]W.Orlikowski and J.Baroudi, “Studying Information Technology in Organizations: Research Approaches and Assumptions”, Journal of Information Systems Research Vol. 2, 1991.[P3, 99]“The P3 Project - Handbook and Training Guide”, ESPRIT 22241, 1999.[Polson and Richardson, 88]M.Polson and J.Richardson (Eds.), “Foundations of Intelligent Tutoring Systems”Lawrence Erlbaum Associates Inc., 1988.[Pooley and Stevens, 99]R.Pooley and P.Stevens, “Using UML - Software Eningeering with Objects and Components”, Addison Wesley, 1999.[Power, 94]J.Power, “A Critiquing System Architecture in the Risk Management Domain”, M.Sc. Thesis, Dublin City University, 1994.[Pulford et al., 96]K.Pulford, A.Kuntzmann-Combelles and S.Shirlaw, “A Quantative Approach to Software Management - The AMI Handbook”, Addison Wesley, 1996.[Pressman, 97]R.Pressman, “Software Engineering - A Practitioners Approach”, McGraw Hill, 1997.[Procter and Bouchier, 94]I.Procter and S.Bouchier, “Software Tools for Project Management”, Information Technology Report, Unicom, 1994.[PMI, 96]“A Guide to the Project Management Body of Knowledge”, Project Management Institute, 1996.[Quillian, 68]M.R.Quillian, “Semantic Memory”, In Semantic Information Processing, M.Minsky (Ed.), MIT Press, 1968.[USAF, 88]“Software Risk Abatement”, AFSC/AFLC Pamphlet 800-45, US Department of the Air Force, 1988.[Ringland and Duce, 88]G.A.Ringland and D.A.Duce, “Approaches to Knowledge Representation”, Research Studies Press, 1988.[Rumbaugh et al., 91]J.Rumbaugh, M.Blaha, W.Premerlani, F.Eddy and W.Lorensen, “Object Orientated Modeling and Design”, Prentice Hall, 1991.[Russell et al., 89]D.Russell, T.Burton, D.Jordan, M.Jensen, R.Rogers and J.Cohen, “Creating Instructions with IDE: Tools for Instructional Designers”, Technical Report PS-00076, Xerox Palo Alto Research Center, 1989.[Sanders, 98]M.Sanders (Ed.), “The SPIRE Handbook - Better, Faster, Cheaper Software Development in Small Organisations”, ESPRIT/ESSI project 23873, European Commission, 1998.[Seaman, 99]C.Seaman, “Qualitative Methods in Empirical Studies of Software Engineering”, IEEE Transactions on Software Engineering, Vol. 25, No. 4, 1999.[Selfridge, 59]O.Selfridge, “Pandemonium - A Paradigm for Learning”, Symposium on the Mechanization of Thought, HMSO, London, 1959.[Schach, 97]S.Schach, “Software Engineering with Java”, Irwin, 1997.[Schreiber et al., 93]G.Schreiber, B.Wielinga and B.Brenker (Eds.), “KADS: A Principled Approach to Knowledge Based Systems Development”, Knowledge Based Systems, Vol. 11, Academic Press, 1993.[Shaw and Garlan, 96]M.Shaw and D.Garlan, “Software Architecture - Perspectives on an Emerging Discipline”, Prentice Hall, 1996.[Shen, et al., 97]D.Shen, C.Wu and S.Lee, “EXPIDER: A Channel Routing Expert for VLSI Design”, Journal of Expert Systems with Applications, Vol. 12, No. 2, 1997.[Shoham, 93]Y.Shoham, “Agent-oriented programming”, Artificial Intelligence, Vol. 60, No. 1, 1993.[Silverman, 92]B.Silverman, “Survey of Expert Critiquing Systems: Practical and Theoretical Frontiers”, Communications of the ACM, Vol. 35, No. 4, April 1992.[Smith et al., 94]P.Smith, P.Ross and E.Awad, “A Survey of the Skills and Personality Attributes of the Knowledge Engineer in the UK”, KnowledgeBase, Vol. 8, No. 2, 1994.[Smith, 96]P.Smith, “An Introduction to Knowledge Engineering”, International Thomson Computer Press, 1996.[Sommerville, 95]I.Sommerville, “Software Engineering”, Addison Wesley, 1995.[Srinivas et al., 97]K.Srinivas, V.Jugannathan and R.Karinthi, “Java and Beyond Executable Content”, IEEE Computer, June 1997.[Stone, 97]W.Stone, “Project Management for the Internet”, Mainspring Communications, June 1997.[Straub et al., 94]D.Straub, S.Ang and R.Evaristo, “Normative Standards for IS Research”, Database, Vol. 25, No.1, 1994.[Tierney and Davison, 95]M.Tierney and R.Davison, “Decision Support for the Provision of Services”, Communicate, Vol.2, No.1, June 1995.[Turban, 95]E.Turban, “Decision Support and Expert Systems: Management Support Systems”, Prentice Hall, 1995.[Verbruggen et al., 89]R.Verbruggen, T.Moynihan and G.McCloskey, “RISKMAN1: A Prototype Risk Analysis Tool for Software Development Project Managers”, In Proceedings of CASE’89 - 3rd International Workshop on Computer-Aided Software Engineering, 1989.[Watson, 97]M.Watson, “Intelligent Java Applications”, Morgan Kaufmann, 1997.[Weld, 95]D.Weld (Ed.), “The Role of Intelligent Systems in the National Information Infrastructure”, AI Magazine, Fall 1995.[Wittig et al., 94]T.Wittig, N.Jennings and E.Mamdani, “ARCHON - A Framework for Intelligent Co-operation”, Journal of Intelligent Systems Engineering, Vol. 3, No. 3, 1994.[White, 94]J.White, “Telescript Technology: The foundation for the electronic marketplace”, White paper, General Magic Inc., USA, 1994.[White et al., 97]J.White, C.Helgeson and D.Steedman, “Introduction to the Odyssey API”, White Paper, General Magic Inc., USA, 1997.[Wooldridge and Jennings, 95]M.Wooldridge and N.Jennings, “Intelligent Agents: Theory and Practice”, Knowledge Engineering Review, Vol. 10, No. 2, 1995.[Zuboff, 88]S.Zuboff, “In the Age of Smart Machines - The Future of Work and Power”, Heinemann Professional Publishing, 1988.。

一种新的矩阵平方根的迭代算法

一种新的矩阵平方根的迭代算法杨壮;彭振赟;牟继萍【摘要】For solving the constraint solution of the quadratic matrix equation X 2-A=0,an iterative algorithm is proposed. The convergence theorem of the algorithm for solving the symmetric solution of the quadratic matrix equation X 2-A=0 is proved.Numerical experiments illustrate that the algorithm is effective.%针对求解二次矩阵方程X 2-A=0的约束解问题，提出一种新的迭代算法，并给出该算法在求解二次矩阵方程对称解时的收敛性定理。

数值实验证明了算法的有效性。

【期刊名称】《桂林电子科技大学学报》【年(卷),期】2014(000)001【总页数】5页(P60-64)【关键词】二次矩阵方程;迭代算法;收敛性【作者】杨壮;彭振赟;牟继萍【作者单位】桂林电子科技大学数学与计算科学学院，广西桂林 541004;桂林电子科技大学数学与计算科学学院，广西桂林 541004;桂林电子科技大学数学与计算科学学院，广西桂林 541004【正文语种】中文【中图分类】O241.6矩阵方程X2－A＝0的解称为矩阵A 的平方根。

矩阵平方根在很多方面都有应用，如控制论、广义特征值问题、线性方程组预处理、偏微分方程边界问题。

对于矩阵平方根的存在性及个数的问题，Higham 在文献［1］和Cross等在文献［2］已经作出了详细的阐述。

求解矩阵平方根的方法大致可以分为直接法和迭代法2种。

直接法首先对矩阵A 进行Schur分解，使矩阵A 成为一个上三角矩阵，进而求解上三角矩阵的平方根，最后还原成矩阵A 的平方根。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

A Fast Algorithm for Finding Crosswalks usingFigure-Ground SegmentationJames M.Coughlan and Huiying ShenSmith-Kettlewell Eye Research InstituteSan Francisco,CA94115USA{coughlan,shen}@Abstract.Urban intersections are the most dangerous parts of a blindperson’s travel.Proper alignment is necessary to enter the crosswalk inthe right direction and avoid the danger of straying outside the cross-puter vision is a natural tool for providing such alignmentinformation.However,little work has been done on algorithms forﬁnd-ing crosswalks for the blind,and most of it focuses on fairly clean,simpleimages in which the Hough transform suﬃces for extracting the bordersof the crosswalk stripes.In real-world conditions such as cluttered sceneswith shadows,saturation eﬀects,slightly curved stripes and occlusions,the Hough transform is often unreliable as a pre-processing step.Wedemonstrate a novel,alternative approach forﬁnding zebra(i.e.multi-plely striped)crosswalks that is fast(just a few seconds per image)androbust.The approach is based onﬁgure-ground segmentation,which wecast in a graphical model framework for grouping geometric featuresinto a coherent structure.We show promising experimental results on animage database photographed by an unguided blind pedestrian,demon-strating the feasibility of the approach.21IntroductionUrban intersections are the most dangerous parts of a blind person’s travel. While most blind pedestrians have little diﬃculty walking to intersections using standard orientation and mobility skills,it is very diﬃcult for them to align themselves precisely with the crosswalk.Proper alignment would allow them order to enter the crosswalk in the right direction and avoid the danger of straying outside the crosswalk.Little work has been done on algorithms for detecting zebra crosswalks for the blind and visually impaired[10,4,5,9].This body of work focuses on fairly simple images in which the Hough transform is typically suﬃcient for extracting the borders of the crosswalk stripes.However,in real-world conditions,such as cluttered scenes with shadows,saturation eﬀects,slightly curved stripes and occlusions,the Hough transform is often inadequate as a pre-processing step. Instead of relying on a tool for grouping structures globally such as the Hough transform,we use a moreﬂexible,local grouping process based onﬁgure-ground segmentation(or segregation)using graphical models.Figure-ground segmentation has recently been successfully applied[8,3]to the detection and segmentation of speciﬁc objects or structures of interest from the background.Standard techniques such as deformable templates[12]are poorly suited toﬁnding some targets,such as printed text,stripe patterns, vegetation or buildings,particularly when the targets are regular or texture-like structures with widely varying extent,shape and scale.The cost of making the deformable templateﬂexible enough to handle such variations in structure and size is the need for many parameters to estimate,which imposes a heavy computational burden.In these cases it seems more appropriate to group target features into a common foreground class,rather than seek a detailed correspon-dence between a prototype and the target in the image,as is typically done with deformable template and shape matching techniques.Our graphical model-based approach toﬁgure-ground segmentation empha-sizes the use of the geometric relationships of features extracted from an image as a means of grouping the target features into the foreground.In contrast with related MRF techniques[2]for classifying image pixels into small numbers of categories,our approach seeks to make maximal use of geometric,rather than intensity-based,information.Geometric information is generally more intuitive to understand thanﬁlter-based feature information,and it may also be more appropriate when lighting conditions are highly variable.We formulate our approach in a generalﬁgure-ground segmentation frame-work and apply it to the problem ofﬁnding zebra crosswalks in urban scenes. Our results demonstrate a high success rate of crosswalk detections on typical images taken by an unguided blind photographer.2Graphical Model for Figure-GroundWe tackle theﬁgure-ground segmentation problem using a graphical model that assigns a label ofﬁgure or ground to each element in an image.In our application3 the elements are a sparse set of geometric features created by grouping togethersimpler features in a greedy,bottom-up fashion.The features are designed tooccur commonly on the foreground structure of interest and more rarely in thebackground.For example,in our crosswalk application,simple edges are groupedinto candidate crosswalk stripe fragment features,i.e.edge pairs that are likelyto border fragments of the crosswalk stripes.The true positive features tend tocluster into regular structures(roughly parallel stripes in this case),diﬀerentlyfrom the false positives,which are distributed more randomly.Our approach exploits this characteristic clustering of true positive features,drawing on ideas from work on object-speciﬁcﬁgure-ground segmentation[8],which uses normalized cuts to perform grouping.We use aﬃnity functions tomeasure the compatibilities of pairs of elements as potential foreground candi-dates and construct a graphical model to represent aﬁgure-ground process.Each node in the graph has two possible states,ﬁgure or ground.The graphi-cal model deﬁnes a probability distribution on all possible combinations ofﬁgure-ground labels at each node.We use belief propagation(BP)to estimate themarginal probabilities of these labels at each node;any node with a suﬃcientlyhigh marginal probability of belonging to theﬁgure is designated asﬁgure.2.1The Form of the Graphical ModelWe deﬁne the graphical model for a generalﬁgure-ground segmentation pro-cess as follows.Each of the N features extracted from the image is associatedwith a graph node(vertex)x i,where i ranges from1through N.Each nodex i can be in two possible states,0or1,representing ground andﬁgure,respec-tively.The probability of any labeling of all the nodes is given by the followingexpression:P(x1,...,x N)=1/Z N i=1ψi(x i) <ij>ψij(x i,x j).(Here we adopt the notation commonly used in the graphical model literature[11],in which theword“potential”corresponds to a factor in this expression for probability.Thisis diﬀerent from to the usage in statistical physics,in which potentials mustbe exponentiated to express a factor in the probability,e.g.e−U i where U i is apotential.)This is the expression for a pairwise MRF(graphical model),whereψi(x i)is the unary potential function,ψij(x i,x j)is the binary potential function andZ is the normalization factor.<ij>denotes the set of all pairs of features iand j that are directly connected in the graph.ψi(x i)represents a unary factorreﬂecting the likelihood of feature x i belonging to theﬁgure or ground,inde-pendent of the context of other nearby features.ψij(x i,x j)is the compatibilityfunction between features i and j,which reﬂects how the relationship between two features inﬂuences the probability of assigning them toﬁgure/ground.The unary and binary functions may be chosen by trial and error,as inthe current application,or by maximum likelihood learning.An example of thiskind of learning is in[6],in which compatibilities(binary potentials)learned fromlabeled data are used to construct graphical models for clustering.However,forthe preliminary results we show to demonstrate the feasibility of our approach,we used simple trial and error to choose unary and binary functions.4The general form of our unary and binary functions is as follows.First,ψi(x i) enforces a bias in favor of each node being assigned to the ground:ψi(x i=0)=1 (which we refer to as a“neutral”value for a potential)andψi(x i=1)<1. The magnitude of theﬁgure value for any feature will depend on one or more unary cues,or factors.In order for a node to be set to the foreground,the bi-nary functions must reward compatible pairs of nodes suﬃciently to oﬀset the unary bias.Ground-ground and ground-ﬁgure interactions are set to be neu-tral:ψij(x i=0,x j=0)=ψij(x i=0,x j=1)=ψij(x i=1,x j=0)=1. Figure-ﬁgure interactionsψij(x i=1,x j=1)are set less than1for rela-tively incompatible nodes and greater than1for compatible nodes.The value of ψij(x i=1,x j=1)will be determined by several binary cues,or compatibility factors.3Figure-Ground Process for Finding LinesA standard approach to detecting crosswalk stripes is to use the Hough trans-form toﬁnd the straight-line edges of the stripes,and then to group them into an entire zebra pattern.While this method is sound for analyzing high-quality photographs of suﬃciently well-formed crosswalks,it is inadequate under many real-world conditions because the Hough transform fails to isolate the lines cor-rectly.To illustrate the limitations of the Hough transform,consider Figure1.A straight line is speciﬁed in Hough space as a pair(d,θ):this deﬁnes a line made up of all points(u,v)such that n(θ)·(u,v)=d,where n(θ)=(cosθ,sinθ)is the unit normal vector to the line.In an image containing one straight line,each point of the line will cast votes in Hough space,and collectively the votes will concentrate on the true value of(d,θ).The lines in Figure1are not perfectly straight, however,and so the peak in Hough space corresponding to each line will be smeared.If only one such line were present in the image,this smearing could be tolerated simply by quantizing the Hough space bins coarsely enough.However, the presence of a second nearby line makes it diﬃcult for the Hough transform to resolve the two lines separately,since no choice of Hough bin quantization can group all the votes from one line without also including votes from the other.Fig.1.Two slightly curved lines(black),representing edges of crosswalk stripes(with exaggerated curvature).The straight red dashed line is tangent to both lines,which means that the Hough transform cannot resolve the two black lines separately.The global property of the Hough transform is inappropriate for such situa-tions,which is why we turn to a localﬁgure-ground process instead.5 3.1Local Figure-Ground ProcessOur localﬁgure-ground process is a graphical model with a suitable choice of unary and binary potentials.Given oriented edgelets y i=(E i,d i,θi)where E i is the edge strength,d i=u i cosθi+v i sinθi and(u i,v i)are the pixel coordinates of the point,we can deﬁne the unary potential asψi(x i)=e(αE i+β)x i whereαand βare coeﬃcients that can be learned from training data.With this deﬁntion, note thatψi(x i)always equals1whenever x i=0,and thatψi(x i=1)increases with increasing edge strength(assumingα>0).Similarly,we can deﬁne the binary potential asψij(x i,x j)=e(λC ij+τ)x i x j where C ij=|d i−d j|+sin2(θi−θj) measures how collinear edgelets y i and y j are.Again,note thatψij(x i,x j)always equals1whenever at least one of the states x i,x j is0.Unless the graph has very dense connectivity,with edgelets being connected even at very long separations,the grouping of edgelets may lack long-range coherence.Without such long-range coherence,the graph may group edgelets into lines that are very slowly curving everywhere(e.g.a large circle)rather than justﬁnding lines that are globally roughly straight.However,such dense connectivity creates great computational complexity in running BP to perform inference.The solution we adopt to this problem is to create a much smaller(and thus faster),higher-scale version of the original graph based on composite fea-ture nodes,each composed of many individual features.For our line grouping problem,we propose a greedy procedure to group the edgelets into roughly straight-line segments of varying length.We describe how this framework ap-plies to crosswalk detection in the next section.4Crosswalks and StripeletsWe have devised a bottom-up procedure for grouping edges into composite fea-tures that are characteristic of zebra crosswalks,and which are uncommon else-where in street scenes.The image is converted to grayscale,downsampled(by a factor of4with our current camera)to the size409x307and blurred slightly. We have avoided the use of color since we wish to detect crosswalks of arbitrary color.Since the crosswalk stripes are roughly horizontal under typical viewing con-ditions,our edge detectorﬁnds roughly horizontal edges byﬁnding local min-ima/maxima of a simple y derivative of the image intensity,∂I/∂y.A greedy procedure groups these individual edges into roughly straight line segments(see Figure3(a)).A candidate stripe fragment feature,or“stripelet,”is deﬁned as the com-position of any two line segments(referred to as“upper”and“lower”)with all of the following properties:(1.)The upper and lower segments have polarities consistent with a crosswalk stripe,i.e.∂I/∂y is negative on the upper segment and positive on the lower segment,since the crosswalk stripe is painted a much brighter color than the pavement.(2.)The two segments are roughly parallel6in the image.(3.)The segments have suﬃcient“overlap,”i.e.the x-coordinate range of one segment has signiﬁcant overlap with the x-coordinate range of the other.(4.)The vertical width w of the segment pair(i.e.the y-coordinate of the upper segment minus the y-coordinate of the lower,minimized across x belong-ing to both segments)must be within the range2to70pixels(i.e.spanning the typical range of stripe widths observed in our409x307images).Many stripelets are detected in a typical crosswalk scene(see Figure3(b)).4.1Crosswalk Graphical ModelOnce the stripelets(i.e.nodes)of the graph have been extracted,unary and binary cues are used to evaluate their suitability as“ﬁgure”elements.The unary cue exploits the fact that stripes lower in the image tend to be wider,which is true assuming that the camera is pointed rightside-up so that the stripes lower in the image are closer to the photographer.If we examine the empirical distribution of all stripelets(not just the ones that lie on the cross-walks)extracted from our image dataset,weﬁnd a characteristic relationship between the vertical widths w and vertical coordinates y(i.e.the vertical height of the centroid of the stripelet in the image).Figure2shows a typical scatter-plot of(y,w)values from stripelets extracted from a single crosswalk image.The envelope of points in the lower left portion of the graph,drawn as a red line, corresponds to the distribution of stripelets that lie on the crosswalk.The slope and intercept of the envelope will vary depending on the crosswalk,camera pose and presence of non-crosswalk clutter,but typically few points lie left of the envelope.In general,the closer a point is to the envelope,the more likely it is to correspond to a stripelet lying on the crosswalk.Given a crosswalk image,a line-ﬁtting procedure can be used to estimate the envelope,and thereby provide unary evidence for each stripelet belonging toﬁgure(crosswalk)or ground.Let E denote the distance(in(y,w)space) between a(y,w)point and the envelope,andˆw be the value of w along the envelope corresponding to the vertical coordinate y of the stripelet.Then E/ˆw is a normalized measure of distance from the envelope.Another source of unary evidence is the length of the stripelet:all else being equal,long(i.e.horizontally extended)stripelets are more likely to belong to ﬁgure than to ground.Denoting the lengths of the upper and lower segments of a stripelet by a and b,we choose a measure L that is the square root of the geometric mean of a and b:L=(ab)1/4.We combine these two sources of unary evidence into the unary function as follows:ψi(x i=1)=(1/10)max[1,L(1−E/ˆw)].Longer stripelets that lie close to the envelope will have larger values of unary potential forﬁgure,ψi(x i=1), but note that this value never exceeds1/10,compared to the unary potential for ground,1.One binary cue is applied in two diﬀerent ways to deﬁne the binary poten-tial between two stripelets.This cue is based on the cross ratio test[1](the application of which is inspired by crosswalk detection work of[10,9]),which is7Fig.2.Typical scatterplot of(y,w)values from stripelets extracted from single cross-walk image.Envelope of points,drawn as a red line,corresponds to distribution of stripelets lying on the crosswalk.a quantity deﬁned for four collinear points(in3-D space)that is invariant to perspective projection.Theﬁrst application of the cross ratio test is used to check for evidence that the four line segments corresponding to the two stripelets are approximately par-allel in three-dimensional space,as they should be.The cross ratio is calculated by drawing a“probe”line through the four lines in the image deﬁned by the line segments.If the four lines share a vanishing point(i.e.because they are parallel in3-D),the cross ratio should be the same no matter the choice of probe.In our algorithm,we choose two vertical probes to estimate the cost ratio twice, i.e.values of r1and r2,and the less discrepant these two values,the higher the compatibility factor.In addition,we exploit a geometric property of a zebra crosswalks:the stripe widths are equal to the separation between adjacent stripes(in3-D),and so the cross ratio from any line slicing across adjacent stripes should equal1/4,as pointed out by[9].These two properties of the cross ratio are combined into an overall error measure as follows:R=(|r1−1/4|+|r2−1/4|)/2+2|r1−r2|.This in turn is used to deﬁne the binary potentialψij(x i=1,x j=1)=(10/3)e−10R.4.2Crosswalk Implementation and ResultsSince the line-ﬁtting procedure forﬁnding the envelope is confused by noisy scatterplots,multiple envelope hypotheses can be considered if necessary,each of which gives rise to a separate version of the graph.In our experiments we chose eight diﬀerent envelope hypotheses and ran BP on each corresponding graph. The solution that yielded the highest unary belief at any node was chosen as the ﬁnal solution.For each graph,the graph connectivity was chosen according to three fac-tors describing the relationship between each possible pair of stripelets:distance between the stripe centroids,the cross ratio error measure R,and the“mono-tonicity”requirement that the higher stripe must have less vertical width than the lower stripe(i.e.the slope of the envelope is negative).If the distance is not8too long,the error measure is suﬃciently low and the monotonicity requirement is satisﬁed,then a connection is established between the stripelets.A few sweeps of BP(one sweep is a schedule of asynchronous BP message updating that updates every possible message once)are applied to each graph, and the unary beliefs,i.e.estimates of P(x i=1),are thresholded to decide if each feature belongs to theﬁgure or ground.The eﬀects of pruning out the “ground”states are shown in Figure3and Figure4.We ran our algorithm with the same exact settings and parameter values for all of the following images.The total execution time was a few seconds per image,using unoptimized Python and C++code running on a standard laptop.Note the algorithm’s ability to handle considerable amounts of scene clutter,shadows,saturation,etc.Also note that all photographs were taken by a blind photographer,and no photographs that he took were omitted from our zebra crosswalk dataset.Fig.3.Stages of crosswalk detection.Left to right:(a)Straight line segments(green).(b)Stripelets(pairs of line segments)shown as red quadrilaterals.(c)Nodes in graph-ical model.(d)Figure nodes identiﬁed after BP.5Summary and ConclusionsWe have demonstrated a novel graphical model-basedﬁgure-ground segmenta-tion approach toﬁnding zebra crosswalks in images intended for eventual use by a blind pedestrian.Our approach is fast(a few seconds per image)as well as robust,which is essential for making it feasible as an application for blind pedes-trians.We are currently investigating learning our graphical model parameters from ground truth datasets,as well as the possibility of employing additional cues.We would like to thank Roberto Manduchi for useful feedback.Both authors were supported by the National Institute on Disability and Rehabilitation Re-search grant number H133G030080and the National Eye Institute grant number EY015187-01A2.References1.R.I.Hartley and A.Zisserman.”Multiple View Geometry in Computer Vision”.2000.Cambridge University Press.9Fig.4.Crosswalk detection results for all zebra crosswalk images.2.X.He,R.S.Zemel and M.A.Carreira-Perpinan.“Multiscale Conditional Random Fields for Image Labeling.”CVPR 2004.3.S.Kumar and M.Hebert.“Man-Made Structure Detection in Natural Images using a Causal Multiscale Random Field.”CVPR 2003.4.S.Se.”Zebra-crossing Detection for the Partially Sighted.”CVPR)2000.South Carolina,June 2000.5.S.Se and M.Brady.”Road Feature Detection and Estimation.”Machine Vision and Applications Journal,Volume 14,Number 3,pages 157-165,July 2003.6.N.Shental,A.Zomet,T.Hertz and Y.Weiss.“Pairwise Clustering and Graphical Models.”NIPS 2003.7.J.Shi and J.Malik.”Normalized Cuts and Image Segmentation.”IEEE Transac-tions on Pattern Analysis and Machine Intelligence,22(8),888-905,August 2000.8.S.X.Yu and J.Shi.“Object-Speciﬁc Figure-Ground Segregation.”CVPR 2003.9.M.S.Uddin and T.Shioyama.“Bipolarity-and Projective Invariant-Based Zebra-Crossing Detection for the Visually Impaired.”1st IEEE Workshop on Computer Vision Applications for the Visually Impaired,CVPR 2005.1010.S.Utcke.”Grouping based on Projective Geometry Constraints and Uncertainty.”ICCV’98.Bombay,India.Jan.1998.11.J.S.Yedidia,W.T.Freeman,Y.Weiss.“Bethe Free Energies,Kikuchi Approx-imations,and Belief Propagation Algorithms”.2001.MERL Cambridge Research Technical Report TR2001-16.12. A.L.Yuille,“Deformable Templates for Face Recognition”.Journal of CognitiveNeuroscience.Vol3,Number1.1991.。