内部代E 价in 、t外x 部i,代yj 价、 局x 部i 代价x k
E e x t x i,y j G x i,y j
E x i ,y j i n t E i n tx i ,y j e x t E e x tx i,y j
动态规划算法
3.使用背向搜索策略确定最优边界 对梯度图像中每个像素点都计算累积代价
算法实现过程
动态规划算法
1. 计算椎骨图像梯度：
G x ( x ,y ) H ( x 1 ,y ) H ( x 1 ,y ) G y ( x ,y ) H ( x ,y 1 ) H ( x ,y 1 )
G (x ,y )G x(x ,y ) G y(x ,y )
动态规划算法
2. 定义与计算边界累计代价
2012年林清华等人提出一种新型快速中值滤波算法，主 要应用于医学图像.文中方法利用中值滤波算法对滤波窗 口内其他像素点的排列顺序不作要求的特点，将基于排序
动态规划算法
基本概念 动态规划：在多阶段决策问题中，各个阶段采取的决策
，一般来说是和时间（先后）有关的，决策依赖于当前状 态，又随机引起状态的转移，一个决策序列就是在变化的 状态中产生出来的，故有“动态”的含义，这种解决多阶段 决策最优化的过程为动态规划。
五大常用算法介绍及其 在图像处理中的应用
五大常用算法
1
分治法
2
动态规划算法
3
贪心算法
4
回溯法
5
分支限界法
设计思想：
分治法
将一个难以直接解决的大问题，分割成一些规模较小的 相同问题，以便各个击破，分而治之。
分治策略：
对于一个规模为n的问题，若该问题可以容易地解决则直 接解决，否则将其分解为k个规模较小的子问题，这些子 问题互相独立且与原问题形式相同，递归地解这些子问题，
多阶段决策过程：有一类活动的过程，可将过程分为若 干个互相联系的阶段，在它的每一阶段都要做出决策，从 而使整个过程达到最好的活动效果，这种把一个问题看作 是一个前后关联具有链状结构的多阶段过程，就称为多阶
动态规划算法
基本思想
将过程分成若干个互相联系的阶段，即子问题，将各阶 段按一定的次序排列好之后，对 于某个给定的阶段状态， 先求解子问题，然后从这些子问题的解得到原问题的解， 对于重复出现的子问题，只在第一次遇到的时候对它进行 求解，并把答案保存起来，让以后再次遇到时直接引用答 案。
假设这四人分别为A、B、C、D。很明显，开始两人拿着 手电筒过桥后，手电筒就在桥的另一边了，此时需要已经过 桥的那两人中的一个再把手电筒送回桥这边。送手电筒回来
贪心算法
但其实有更快的办法： AB→2 A←1 CD→8 B←2 ቤተ መጻሕፍቲ ባይዱB→2
一共是2+1+8+2+2=15分钟。这个办法的聪明之处在于让 两个走得最慢的人同时过桥，这样花去的时间只是走得最 慢的那个人花的时间，而走得次慢的那位就不用另花时间 过桥了。可以把所有可能的方案都列举一遍，就会发现这
贪心策略适用的前提：局部最优策略能导致产生全局最优 解。
贪心算法不是对所有问题都能得到整体最优解，选择的贪
贪心算法
例 在漆黑的夜里，四位旅行者来到了一座狭窄而且没有护栏 的桥边。如果不借助手电筒的话，大家是无论如何也不敢过 桥去的。不幸的是，四个人一共只带了一只手电筒，而桥窄 得只够让两个人同时过。如果各自单独过桥的话，四人所需 要的时间分别是1、2、5、8分钟；而如果两人同时过桥，所 需要的时间就是走得比较慢的那个人单独行动时所需的时间。 问题是，如何设计一个方案，让这四人尽快过桥 。
然后将各子问题的解合并得到原问题的解。(分治与递
归)
分治法
分治法在每一层递归上都有三个步骤： 分解：将原问题分解为若干个规模较小，相互独立，与
原问题形式相同的子问题； 解决：若子问题规模较小而容易被解决则直接解，否则
递归地解各个子问题 合并：将各个子问题的解合并为原问题的解。
分治法的一般设计模式：
Divide-and-Conquer(P) 1. if |P|≤n0
分治法
分治法在医学图像处理中的应用
传统的中值滤波算法需要对滤波窗口内的所有像素进 行排序，再依据排序的结果选取中值。常用的排序算法有 很多（插入排序、交换排序、选择排序、归并排序、分配 排序），以快速排序为例，其算法的思想是将大问题分解 为若干个规模较小但结构与大问题相似的问题，递归地解 决这些小问题后，将小问题的解结合为大问题的解。
之后，需要利用背向搜索策略找到最终的 最优“路径”。首先找到最后一列中累积代 价和最小的像素点，该累积代价代表了最 优“路径”上所有点的累积代价和。从该像 素点出发，依次向前追踪最优“路径”上的
动态规划算法
椎骨分割结果
(a)
(b) (c) (d)
(e)
(f)
贪心算法
贪心算法是指在对问题求解时，总是做出在当前看来是最 好的选择。也就是说，不从整体最优上加以考虑，他所做 出的仅是在某种意义上的局部最优解。 贪心法的基本思路：从问题的某一个初始解出发逐步逼近 给定的目标，以尽可能快的地求得更好的解。当达到某算 法中的某一步不能再继续前进时，算法停止。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束 状态
图1 动态规划决策过程示意图
动态规划算法
基于动态规划算法分割椎骨上下边界的方法 基本思想
根据椎骨上下缘灰度与形状信息来寻找椎骨的上下边界， 在梯度图像中，最终的分割结果被定义为具有最小累积代 价和的“路径”，该“路径”由梯度图像中每一列上唯一的点 组成，即从梯度图像最左一列到最右一列计算累计代价， 找出最后一列中累积代价和最小的像素点，利用背向搜索 策略找到最终的最优“路径”，最终处在最优“路径”上的所 有像素点构成了最终分割结果。
适用条件
(1) 最优化子结构：如果问题的最优解所包含的子问题 的解也是最优的，就称该问题具有最优子结构，即满足最
动态规划算法
基本步骤
动态规划所处理的问题是一个多阶段决策问题，一般由 初始状态开始，通过对中间阶段决策的选择，达到结束状 态。这些决策形成了一个决策序列，同时确定了完成整个 过程的一条活动路线(通常是求最优的活动路线)。如图所 示。动态规划的设计都有着一定的模式，一般要经历以下 几个步骤。