TODO List based 算法、任务分解、分治法
就是围绕一个TODO list，不断取出并处理其中的work item。处理work item的时候，一般先做一些工作，然后可能会产生新的子work item追加到todo list，类似一个大任务分解成若干小任务。

class ToList {
public:
    void append(WorkItem wi);
    WorkItem fetch();
}


注意这个todo list最自然的就是一个队列，实际上只要是支持添加(push)和取出(pop)的容器都可以，queue, stack, priority_queue, random_queue都行，取决于这些子任务之间是否独立，是否有顺序上的要求。

经典例子：

1快排

todo list中的work item定义为对数组的一段[a, b]进行快排
一开始todo list只有一个任务: 快排整个数组[0, A.size() - 1]，每个快排任务的处理是：
1）以第一个元素为轴进行partition
2）添加两个子快排任务到工作列表
int partition(vector<int> &A, int l, int r) {
	int i = l;
	for (int j = l + 1; j <= r; ++j)
		if (A[j] < A[l]) swap(A[++i], A[j]);
	swap(A[l], A[i]);
	return i;
}
void quick_sort(vector<int> &A) {
	if (A.empty()) return;
	queue<pair<int, int>> q;
	for (q.push(make_pair(0, A.size() - 1)); !q.empty(); q.pop()) {
		int l = q.front().first, r = q.front().second;	
		int p = partition(A, l, r);
		if (p - 1 > l) q.push(make_pair(l, p - 1));
		if (p + 1 < r) q.push(make_pair(p + 1, r));
	}
}




2bfs

任务定义：以s为起点进行遍历
任务处理：先打印s的数据。 然后针对s的每个邻居，（如果没被访问过），产生一个新bfs任务追加到todo list。


3进一步，todo list里的任务可以是多种任务，而且之间可以满足一定顺序，通过选用不同的容器。
经典的后序遍历问题，可以用todo list 任务列表算法很自然的表达：

def postorderTraversal(self, root):
    result, todo_list = [], [(root, 1)]
    if root is None: return result
    while len(todo_list) > 0:
        node, taskType  = todo_list.pop()
        if taskType == 1: # 1 for traverse job
            todo_list.append((node, 0)) # 0 for basic print job
            if node.right is not None: todo_list.append((node.right, 1))
            if node.left is not None: todo_list.append((node.left, 1))
        else: result.append(node.val)
    return result



定义2种类型的task, 

1) print task：打印该节点值
2) traverse task：遍历以该节点为根的树
对于第一种task的处理就是直接打印，对于第二种task，产生生成三个子task, 1个print task, 2个 traverse task，并注意task加入顺序，根, 右， 左
一开始工作列表里只有一个任务：后序遍历以root为跟的树，然后不断衍生子任务。。。
4 merge Sort

def mergeSort(A):
	todo_list, aux = [(0, len(A) - 1, 0)], [0] * len(A)
	while len(todo_list) > 0:
		l, r, type = todo_list.pop()
		if type == 0: # mergeSort task: compound task
			if l < r: 
				todo_list.append((l, r, 1)) # merge task
				todo_list.append((l, l + (r - l) / 2, 0)) # sort task
				todo_list.append((l + (r - l) / 2 + 1, r, 0)) # sort task
		else: # merge task: simple task
			i, j, k = l, l + (r - l) / 2 + 1, l
			while i <= l + (r - 1) / 2 and j <= r:
				if A[i] < A[j]: 
					aux[k] = A[i]
					i += 1
				else:
					aux[k] = A[j]
					j += 1
				k += 1
			while i <= l:
				aux[k] = A[i]
				k, i = k + 1, i + 1
			while j <= r:
				aux[k] = A[j]
				k, j = k + 1, j + 1
			for k in xrange(l, r + 1):
				A[k] = aux[k]

5全排列:
两种task：1）全排任务。2）swap 任务

def permute(A):
    todoList = [(0, 0, len(A) - 1)]
    while len(todoList) > 0:
        taskType, l, r = todoList.pop()
        if taskType == 0 and l == r: print A
        elif taskType == 0:
            for i in xrange(r, l - 1, -1):
                todoList.append((1, l, i))
                todoList.append((0, l + 1, r))
                todoList.append((1, l, i))
        else: 
            A[l], A[r] = A[r], A[l]




总结：
2种任务，终端任务和复合任务，终端任务是可以直接做的任务，复合任务是由一系列其他任务序列组成。在快排和BFS的例子中，并没有定义终端任务，因为终端任务处在任务序列前面（或者顺序无关）可以先做，不用放到todo list。而后序遍历和merge sort的例子中，终端任务不能先做，所以先压到箱底。

来源：Proceedings of the Fourth Annual IEEE International Conference on Pervasive Computing and Communications (PERCOM’06)2006

标题：An Adaptive Multi-Constraint Partitioning Algorithm for Offloading in Pervasive Systems 密码: 3gy2

作者：Shumao Ou, Kun Yang and Antonio Liotta {smou, kunyang, aliotta}@essex.ac.uk

单位：University of Essex, Department of Electronic Systems Engineering, UK （埃塞克斯大学，电子工程系，英国）


问题提出：

任务分解是普适系统中采用一种机制，在资源严重受限的移动设备中，通过合并一个普适服务/应用的部分类代码并发送到到附近的一些资源丰富的代理上来完成服务。一个普适服务的应用在分解之前需要被划分。这样划分算法在一个高性能的分解系统中就显得至关重要。

解决办法：

本文提出了一个动态(K+1)划分算法来将一个给定的应用划分成1个不可分解的部分和K个可分解的部分。而且，这些划分满足多种限制条件（应用用户提出的或者是移动设备资源受限）。划分算法用一个动态的多消耗图来模型化一个应用的组成类的资源消耗，包括CPU、内存、数据传输，并用重边轻点算法（HELVM）（即边的权重和定点的权重两方面综合考虑）来粗化多消耗图。最后开发一个实现该算法的任务分解工具来评估我们的算法。实验结果表明我们的算法在效率和资源消耗方面都具有很好的性能表现。



拓展研究：

在任务分解系统中，远程执行及远程交流将不可避免的增加类和应用执行失败的风险，这就需要一个重要而高效的错误容忍机制。另外，安全和信任机制也可以考虑应用到其中。同时，进一步减少K+1划分算法的计算和传输的复杂度.。




存在的不足：（只是现阶段的个人的一些观点，有待验证）

1.应用的组成类是在执行之前进行的划分，然后执行时进行任务的分解。如果事先无法获得应用的所有类，那么就无法划分。能做到边执行边划分？
考虑博弈或马尔可夫。。。

2.按整个类进行划分，对于某些特定的应用还是显得太粗糙，而对另一些应用又显得太细化，可以根据应用的不同类型动态选择划分的粒度。按方法级别，类级别，还是按照模块进行划分。

	

CT技术是CT诊断的基础，帮助医务工作者充分掌握CT技术是我们的责任和义务！
CT原理5
Material Decomposition Algrithm 
物质分解算法简介
1
一篇100页的SCI
这篇SCI是由美国梅奥诊所发表在《医疗物理学》  影响因子为3.177分。
这是一篇科普性的AAPM 任务组291号报告：《多能CT原理及应用》，内容长达100多页，对于充分理解多能CT的原理及应用有帮助，特此分享给大家，今天重点给大家介绍物质分解的算法，也就是如何把混合物的CT图像按照其化学组成分解为元素图像，如下图[1]。
2
1973年最初的想法
CT发明者Hounsfield先生早在1973年就发现一个重要的现象：即化学成分和密度不同的物质在一种X线能量下可以表现为相同的CT值，也就是原子序数Z高但密度低的物质与原子序数Z低但密度高的物质可能通过单一的CT值是无法鉴别的。
基于这一重要的发现，Hounsfield提出了通过两种不同能量的X线(E1、E2)分别成像，以进一步鉴别原子序数不同的等密度物质，如下图[1]。
后来的研究者又对上图中的输出结果(线性衰减系数，μ)做了优化处理：即除以物质密度，μm=μ/ρ,成为质量衰减系数，亦称质量吸收系数，是指每平方厘米每克厚的吸收物质(g/cm²)，所减少的x线强度的百分数，也即每克质量物质对x射线衰减的程度，单位是cm²/g。这样使得该系数只决定于物质的原子序数Z，而与密度无关了，例如，水、冰、水蒸气三种物质虽然密度不同，但是原子序数(Z=7.43)完全相同，所以它们的质量衰减系数是相同的。
3
1976年最初的数学公式
在CT发明者Hounsfield先生提出通过两种能量的X线进行CT成像以鉴别不同化学组成的等密度物质后的第3年，也就是1976年，Alvarez先生首次将这种想法精确地通过数学表达了出来，也就是CT的能量选择性重建，如下图：
也就是通过数学分解的方式，把总的线性衰减系数进一步分解为两部分：光电效应衰减+康普顿衰减
具体公式，如下图[1]。
The function 1/E3 approximates the energy dependence of the photoelectric interaction and fKN(E) gives the energy dependence of the total cross-section for Compton scattering.
然后每一种物质对于一个特定的光电效应衰减系数(α1)和康普顿衰减系数(α2)，这样，每一种物质都可以通过(α1，α2)这样的系数组合进行表达，通过这种方式可以实现对CT值相同的不同物质的准确区分，这是首次通过数学公式精确表达了双能CT的物质分解算法。
4
物质分解算法1
由于双能量物质分解算法的发明者Alvarez的公式对两种能量成像在时间、空间上的匹配具有严格的要求，也就是对设备的要求非常高，要求CT设备能够在相同的时间和方向上同时采集两种能量的衰减数据。
所以早期的物质分解算法并没有按照Alvarez的公式直接对衰减系数进行分解，而是先重建出高、低两种kV的图像，然后利用以下公式计算出不同能级图像的CT值，如下图[1]。
并同样基于两种kV图像的CT值散点图(如下图)中的斜率来分解和区分不同的物质。
5
物质分解算法2
由于上述分解算法是基于图像数据的，因此实际上基于两个假设：(1)CT值测量都是准确的，不会受到噪声干扰；(2)图像不会受到X线硬化伪影的影响。这两个假设都是与实际情况不符的，所以后来又诞生了新的不再使用图像数据进行分解的算法。
该方法是通过对Alvarez公式的数学转化，将线性衰减系数的物理效应分解方式转化成了基物质对(A物质衰减+B物质衰减=总衰减)分解的方式，如下图[1]。
通过高低kV切换的方式获得两种能量的原始数据，然后通过上述公式分解出水基图、碘基图，然后通过这两种基本图像再进一步处理出其他能谱图像，如下图[1]。
6
物质分解算法3
上诉方法是基于几乎同时、几乎同向采集的两种能量的数据实现了投影数据域的分解算法，物质分解的准确性得到了提升，但是实际上也是基于一个假设：假设所有的物质都是由水和碘这两种基本物质混合而成的，例如钙，也是由二者组成的，如下图：
这种假设有时候与实际情况也是不符的，所以基于这两种基物质图获得的单能级图像，其CT值的测量对于碘物质和水物质是准确的，而对于其他物质可能是不准确的[1]。所以后来又诞生了新的投影数据域分解算法，如下图[1]。
这种算法实际上正是1976年Alvarez提出的公式，也就是基于双层探测器在同一时间、同一方向对同一束X线中的高、低能量光子同时进行分离采集，然后基于获得的高、低两种能量的数据通过上述公式求解出康普顿数据和光电效应数据以进一步获得多种能谱图像，同时高低能量两组数据直接求和按照常规CT重建方式也可以获得常规CT图像，如下图[1]。
重点回顾
X线与物质作用后会发生衰减，这是CT成像的基础，通过对这种X线衰减系数的分解可以提高X线对物质的识别能力，目前已经实现了多种不同的分解算法。
注意事项！
✔ 早在1973年Hounsfield就提出通过两种不同能量的X线分别成像，可以进一步鉴别原子序数不同的等密度物质。
✔ 早在1976年，Alvarez就已经通过数学公式表达了物质分解的方式，也就是把总的线性衰减系数分解为光电效应衰减和康普顿衰减两部分。
✔ 具体实践中，Alvarez的数学公式的实现经历了图像数据域物质分解、转化形式的基物质对投影数据域物质分解、直接基于康普顿及光电效应的投影数据域物质分解。
[1].McCollough CH, Boedeker K, Cody D, et al. Principles and Applications of Multi-energy CT Report of AAPM Task Group 291 [published online ahead of print, 2020 Mar 25]. Med Phys. 2020;10.1002/mp.14157. doi:10.1002/mp.14157
扫码关注或加入公众号交流群
如果对您有帮助，请帮忙点下右下角“在看”，非常感谢您的支持！

    

                    

                    

                    
                    
                    
感谢阅读腾讯 AI Lab 微信号第40篇文章，ECCV大会正在德国举办，我们每天深度解读一篇入选论文，今天是第4篇。

ECCV 2018（European Conference on Computer Vision，计算机视觉欧洲大会）与CVPR、ICCV共称为计算机视觉领域三大顶级学术会议，从今天到14日正在德国慕尼黑举办。

腾讯AI Lab 是第二次参加，入选了19篇文章，位居国内企业前列。会议期间，我们选取4篇入选论文做深度解读，主题依次为图像到图像转换方法SCAN、视频再定位、单帧RGB生成三维网络模型和跨年龄人脸识别算法。

在这篇由腾讯 AI Lab 独立完成的论文中，作者提出了一种正交深度特征分解算法OE-CNNs，能显著提高跨年龄人脸识别精度，以下为论文详细解读。

该研究的目的是通过研发新的深度学习模型以提高跨年龄人脸识别的精度。本文提出了一种正交深度特征分解算法OE-CNNs，通过把深度特征正交分解为年龄分量和身份分量，从而将年龄分量和身份分量有效分离开，从而达到减少年龄差异、提高跨年龄人脸识别精度的目标。本文在多个跨年龄人脸识别的国际评测基准（FG-NET, Morph Album 2, CACD-VS）中都取得了国际领先的性能，显著提高了跨年龄人脸识别的精度。此外，研究者还建立了一个新的跨年龄人脸数据库CAF以帮助促进跨年龄人脸识别研究。
 
跨年龄人脸识别是人脸识别领域中的一个极具挑战性的国际性难题。众所周知，同一个人的不同年龄阶段的图片会有非常大的差异，这些差异会严重影响到跨年龄人脸识别的精度。迄今为止，深度学习已经被广泛运用到人脸识别，并且取得了非常好的性能。但是，对于跨年龄人脸识别，问题，由于同一个人在不同年龄阶段下的多张人脸之间存在着非常显著的差异，这严重影响到现有的深度人脸识别模型的性能。为了克服这个巨大的年龄差异，本文研发了一种新的深度学习算法，该算法把深度特征按照模长方向和角度方向（这两个方向是彼此正交的）分别分解为年龄成分和身份成分，如下图所示。
其中，年龄成分被分解成一维径向分量，而身份成分则分解为高维角度分量。这两种分量最后通过多任务学习的方式同时训练，最终的损失函数是二者损失的算术叠加：
其中身份成分的损失函数
而年龄成分的损失函数
基于这种新的分解模型研究人员可以把人脸的年龄分量和身份分量有效分离开，并基于身份分量来做跨年龄人脸识别从而有效提高跨年龄人脸识别的精度。

为了进一步提高跨年龄人脸识别性能，本文还采集了一个面向跨年龄人脸识别的的新型人脸数据库CAF。研究人员通过在网上搜集名人在不同年龄段拍的照片，以保证这些训练图片有足够大的年龄差异。本文的搜集的人名来源于公共的信息库，比如IMDB, Forbes Celebrity, Wikipedia等。本文使用CAF数据库有4,668个不同的人和这些人的313,000张图片。这个数据库的样例和统计分布如下图所示。
实验结果
在上表的FG-NET跨年龄人脸识别任务中，AI Lab的新算法OE-CNNs取得了高达53.26%的第一识别率，比第二名的38.21%足足高了超过15%的识别率。
在上表的Morph Album 2识别任务中，AI Lab的算法也稳定地高于其它所有的人脸算法。
在上表的对比实验中，能明显看出增加了AI Lab新建立的CAF人脸数据做训练后，对于上表中的所有人脸算法，它们的识别率都能显著获得提升，这证明了CAF对于跨年龄人脸识别研究的帮助和价值。