Example：
Initialized：
Augmenting path：s→a→b→t，excess capacity：min(4, 3, 5) = 3
f(G) = 3：
Augmenting path：s→a→t，excess capacity：min(1, 5) = 1
f(G) = 4：
Augmenting path：s→c→d→t，excess capacity：min(6, 4, 4) = 4
f(G) = 8：
Final result：
March 7, 2011
[基础算法] 一个Ford-Fulkerson算法的例子
March 3, 2011
[论文笔记] CUDA Cuts: Fast Graph Cuts on the GPU
Paper：V. Vineet, P. J. Narayanan. CUDA cuts: Fast graph cuts on the GPU. In Proc. CVPR Workshop, 2008.
问题概述：Graph cut是一种十分有用和流行的能量优化算法，在计算机视觉领域普遍应用于前背景分割（Image segmentation）、立体视觉（stereo vision）、抠图（Image matting）等。但在获得不错效果的同时，Max-flow / Min-cost问题求解的时间代价却很大。本文作者称其所知最佳的Graph cut实现求解一张640×480的图至少需100毫秒（平均数据会差得多），无法满足实时应用的需求。但事实上，Max-flow求解中经典的Push-relabel算法在流的计算和维护上只与局部相关，具有潜在的可并行性，适于GPU加速。因此，作者实现了push-relabel算法的GPU版。作者称其算法于一张640×480的图平均每秒可以求解150次Graph cut（Nvidia 8800 GTX），也就是约6.7毫秒速，是传统CPU算法约30-40倍速。作者还提供源码的下载，点我。
Definition & Notation：
对于一个图 G = (V, E) ，其中 V 为节点集合，包括源点 s 和终点 t （也可以定义多个端点，其可以优化为双顶点图）、以及其他诸多中间节点集合 V’ ，E 为连接这些节点的边，每条边附有容量 c(u, v) 代表节点 u 通过这条边流向节点 v 所能承受的最大流量，在具体应用中边的容量通常等价于其能量值。Graph cut的目的在于找到图的Min-cut，Cut将 V’ 分割为两个部分，去掉这些边将使舍得图中的任意一个节点只与 s 或 t 相连通（如下图），而Min-cut是所有cut中边的能量值总和最小的一个。 
算法上要直接找Min-cut是十分困难的，通常要将问题转化为与之等价的Max-flow问题（理论推导点我）。Graph cut具体应用的性能关键在于能量函数的定义，用于计算机视觉中的一种常见能量函数定义如下： 
Dp 定义数据能量，Vp, q 定义平滑度能量，N 定义相邻关系，fp 为像素 p 的标签（属于 s 或 t ）。
经典Push-relabel算法：
求解Max-flow有两种经典的算法：Ford-Fulkerson和Push-relabel算法。Ford-Fulkerson算法的大意是在图中不断寻找 s 和 t 之间可用路径，记入总流量，并维护一张残余网络（Residual graph），直到再也找不到可用路径为止，此时的总流量就是Max-flow（具体算法点我）。Ford-Fulkerson算法的串行性很大，因为可用路径的查找是全局性的，这是GPU所不擅长的。
Push-relabel算法，相对的，具有很强的局部性和可并行性，在每一个子操作中指关心节点及其相邻节点。Push-relabel的基本思路是将尽可能多的流量从 s 推向 t ，但是当 t 已经无法再接受更多的流量时，这些流量将会被反推回 s，最终达到平衡（和Ford-Fulkerson算法一样，再也找不到 s 到 t 的可用路径）。算法过程中的“流”称为Preflow（先流），它并不像Ford-Fulkerson算法过程中的流一样总是持续升高直至Max-flow，而是初始预测一个值，在不断趋近于Max-flow，过程中可能出现回流的现象。Preflow对每一个节点满足 e(u) = in(u) – out(u)，且 e(u) ≥ 0。当 e(u) > 0 时，节点 u 溢出（overflowing）。溢出的节点需要将多余的流量Push向其相邻的节点，即Push操作。当一条从 s 到 t 的路径上所有的节点都不溢出时，此路径上的Preflow就变成真正的Flow了。
Push-relabel算法和Ford-Fulkerson算法一样都会维护一张残余网络。对于图中的每一个节点 u，若在残余网络中存在 e(u, v)，则 h(u) ≤ h(v) + 1。Push操作只能在 h(u) ＞ h(v) ，u 节点溢出且 e(u, v) 残留容量时进行；而当 u 节点溢出，且与之相邻所有残留边节点的 h(v) ≥ h(u) 时，只能进行Label操作，增加节点 u 的高度，即 h(u) += 1。在初始化时，h(s) = n，t 及其他所有节点的高度均为 0；从 s 出发的所有边初始化 f(e) = c(e)，其余边 f(e) =0。Push-relabel算法将不断重复Push和Label操作，直至任意操作都无法进行。
（更详细的算法步骤推荐查阅Tutorial，点我）
比较形象点，Push-relabel是泛滥的洪水，奔腾向前，堵了就倒流；Ford-Fulkerson则是很温吞的做法，先找个人探路，回来报告能流多少水就开闸放多少。
Push-relabel算法的GPU版：
存储和线程结构：
Grid拥有和输入图片一样的维度，并被分为若干个Block，每个Block的维度为 B×B。每个线程对应一个节点（像素），即每个Block对应 B×B 个节点、需要访问 (B+2)×(B+2) 个节点的数据。每个节点包含以下数据：溢出量 e(u)，高度 h(u)，活跃状态 flag(u) 以及与其相邻节点间的边的容量。活跃状态共3种：Active，e(u) ＞ 0 且 h(u) = h(v) + 1；Passive，e(u) ＞ 0 且 h(u) ≠ h(v) + 1，这种状态在Relabel后可能变成Active；Inactive，没有溢出且没有相邻残留边，
这些数据存储在全局或设备内存中，被所有线程共享。
（GPU架构及Cuda指南参考NVidia相关手册，点我）
本文作者通过4个Kernel实现GPU版Push-relabel算法：
1) Push Kernel (node u)：
| ■ | 将 h(u) 和 e(u) 从全局内存读入到Block共享内存中（使用共享内存是因为一些数据会被相邻线程共享，这种读入方式相对单独的读入更节省时间）； |
| ■ | 同步线程（使用共享内存都需要做这一步，为了保证所有内存都被完全读入了）； |
| ■ | 将 e(u) 按照Push规则推向相邻节点（不大于边的剩余容量，且 h(u) ≥ h(v) ）； |
| ■ | 将以上Preflow记入一个特殊的全局数组 F。 |
2) Pull Kernel (node u)：
| ■ | 读入 F 中推向 u 的Preflow； |
| ■ | 累加所有新的Preflow，得到最终的溢出值，记入 e(u) 到全局内存。 |
3) Local Relabel Kernal (node u)：
按照经典Push-relabel算法中的Relabel操作，局部地调整节点的高度
| ■ | 将 h(u) 和 flag(u) 从全局内存读入到Block共享内存中； |
| ■ | 同步线程； |
| ■ | 计算 u 相邻 active / passive 节点的最小高度； |
| ■ | 该最小高度+1，作为新高度写入 h(u) 到全局内存。 |
4) Global Relabel Kernal：
从终点 t 开始，按照广度优先策略，遍历所有节点，更新其高度至正确的距离（节点的高度总是其与终点距离的下限）。迭代次数 k 被记录与全局内存中。
| ■ | 如果 k == 1，所有与 t 相邻且有残留边的节点高度被设为 1； |
| ■ | 所有未被设置的节点检查其相邻节点，若其相邻节点的高度为 k，则设置该节点高度为 k+1； |
| ■ | 更新高度值到全局内存。 |
算法总体流程：
a. 计算能量矩阵 → b. Push+Pull Kernel循环 → c. Local Relabel Kernel循环 → d. Global Relabel Kernel循环 → e. 重复b到d至收敛（没有可进行的Push和Relabel操作）
作者还基于GPU实现了Dynamic graph cut，应用于连续细微变化的Graph cut，通过对前一帧的简单修改形成新图，重用其他数据，加速Max-flow的求解。作者的实验数据称GPU实现可以提速70-100倍。不过具体应用具体分析，提速肯定是有的，多少未知，要待我实现过试验过。据说这个印度人提供的代码Bug颇多，虽然不太信，但还是先做了要重新实现的准备。末了，吐个槽，这论文贡献不大，确实只是发Workshop的水平。
December 28, 2010
2010年终盘点
前些日子杭州下了05年来最大的一场雪，青天白日的乱飞积了一地，想起当年姐还小的时候在ZJG堆的龙猫雪人和红晕龙猫雪人，时间过得真快。然后，今年有件可喜的事是收获了一颗大饼，皮糙肉厚耐摔耐磨。
※音乐
陈奕迅今年发的些碟们倒是都听过几遍，「沙龙」和「於心有愧」听着喜欢，还装模作样地K过一回，只是粤语什么的说得太对不起了。
刨到些 いきものがかり 的老专辑，羡慕主唱有力的声音，什么唱起来都觉得励志，「SAKURA」最高。今年新发的单曲，「ありがとう」很温情，「時をかける少女」是某穿越真人片的主题歌，最不喜这种二次元真人版，但歌很是 いきものがかり 的风格。
YUI 今年也好些作品，「to Mother」老实惊艳了一下，第一次见她弹钢琴，比摆弄吉他时果然温柔淑女多了。
断断续续地下完了 吉田拓郎 的一张4CD精选，85年出，也就是他隐退的前夕。最初是去找「夏休み」，反反复复就几句词，曲风应该是民谣吧，耐听的。
追钢炼识了个新乐队 シド ，主唱是个非主流，所幸声音还行，听CD比现场舒服些。
暑假时在图书馆借了 帕格尼尼 的传记，还找了摩西幻想曲来听，这曲子对演奏者技巧的要求很高，是首很厚重的咏叹调。
※动画
今年的动画倒是每季都挑了喜欢的追。剧场什么的国内能看到的也都下着看了。整理了下才发现如果没有VeryCD没有BT我会死掉的，对国外的资源实在太依赖了。
# 残留的钢炼完结了
年番，从去年一直播到今年中。照着漫画的剧情，最后一场架结结实实地打了10集，剧情上果然比上作严谨得多。连带着还有很多好听的OP/ED，丰富了在下的精神文化生活。
# 无头骑士异闻录 | デュラララ!!
「BACANO! 」原班制作人马，一样奔放地剪TV动画像剪电影，不输骨头的流畅动作，我喜欢的非恐怖灵异故事。十分喜欢动画里主角们的聊天系统，不知是仿的哪个软件，恰到好处的排版和头像设计，爱！据说会出续作，想想也会，头都没拿回来，还有故事好讲，「BACANO! 」也是两季的故事。我想看静雄打架！！！
# 交响情人梦Finale | のだめカンタービレ フィナーレ
例行追的。轻松搞笑好看。野田妹什么的最萌了。千秋什么的最好推倒了。我邪恶了。
# 机动战士高达UC | 機動戦士ガンダムUC
独角兽。白白的机体，我觉得不太好看的说。复古的人设，应该是要向老祖致敬什么的。大饼要看的，我就跟着看了。剧情俗套，和几年前看柯南剧场没什么差别，但这是一种感情，高达饭的话应该是这样的。我这样的就是来看打架的。
# 轻音少女 第2季 | けいおん！！
觉得没有第一作好看的说，歌的话需要吐槽一下某OP，难听死了，小日本的口味真奇特，「No Thank you!」什么的好听多了，只混个ED。轻音今年还是Oricon大丰收，这种音乐题材的动画真是有的赚啊。
# 大神与七位伙伴 | オオカミさんと七人の仲間たち
这旁白的声音真是听过一次能记住一辈子，太有特点了。该作的特点是胆小的用弹弓的男主角、傲娇系用猫猫拳套的女主角和腹黑的私生子女二号。其实也普通的说，我就是喜欢人设的画风和旁白的声音= =
# 传说中勇者的传说 | 伝説の勇者の伝説
我以为这片全年龄向的，只是这制作组总是有意无意地腐一下，尤其是最后几集，又是小清新又是暧昧的，受不了。女主角是个我喜欢的类型，拿大剑崇拜团子神的好女人。男主角们不评论，腐者自腐。
# 南家三姐妹 | みつどもえ && 妄想学生会 | 生徒会役員共
这两个放一起，因为都是重口味的四格改编题材。女生KUSO起来真不是盖的啊。我就喜欢看欢乐的片子。顺便同情下两部片子里负责吐槽的男主角们，工作太辛苦了。
# 学园默示录 | 学園黙示録 HIGHSCHOOL OF THE DEAD
这片该是男性向的，又是大胸又是打僵尸的。虽然打架真的蛮好看的，我还是要担心下这片坑挖得太大填不上烂掉。全世界都变僵尸了这种话题，好在日本没有广电某局，不然估计编剧抓破脑袋也写不出一个有利青少年成长的结局。
# 滑头鬼之孙 | ぬらりひょんの孫
我对这片最不满的是这废柴女主角，我要奴良和雪女在一起！重复一千次。
# 只有神知道的世界 | 神のみぞ知るセカイ
这故事很有趣。男主是个玩GALGame玩得出神入化对三次元完全没有兴趣的宅男，号称攻略之神，so某穿粉红色披肩的魔鬼小妞就找上他了。平均3集攻克一个不同类型的三次元女，驱除捕获她们心灵缝隙里的驱魔，用的还是游戏里的攻略思维。真宅男们看着应该更有趣点，我就是去围观PFP的。
# PANTY and STOCKING | パンティ＆ストッキングwithガーターベルト
神作！必须膜拜。乍一看还以为是飞天小女警。GAINAX果然搞怪，就是要吓你一大跳。大尺度啊大尺度。
# 食梦者 | バクマン。
据说是原作者自身经历的改编，描写的是少年漫画家的成长，热血的说。还有“实现梦想前不交往，实现了以后我们结婚”这样的纯爱。青春什么的真是美好啊。
# STAR DRIVER 闪亮的塔科特 | STAR DRIVER 輝きのタクト
好了，BONEZ，我要来吐槽你。你说你出个啥低龄的「Hero Man」我就原谅你了，你还（<ゝω・）綺羅星!★（注意这是个动作！），你还“银河美少年”，你还“飒爽登场”，你想干啥？！我看这片我每回都羞耻感大增，我容易么我，就为着听鱼mm唱歌，为着乃是BONEZ。现在我每回看，都觉得这是个喜剧片，BONEZ乃绝对是故意的。
# 少女妖怪石榴 | おとめ妖怪ざくろ
我很喜欢她们打架时唱的歌，快出OST吧要拿来当铃声。
# 侵略！乌贼娘 | 侵略！イカ娘
巨萌的乌贼娘，不解释！
# 猫屎一号 | Cat shit One
难得日本人能拍出这么好的3D动画，兔子的短腿真是太萌了，还要装正经说“危险”。。快出第二集吧。每个国家的人都用一种动物代替，打起架来还是蛮新颖的，只是我不明白法国人为啥是猪呢。。
※电影
这个有些多，新的旧的还有些清掉了，全的列表是拿不到，挑几个印象深刻的说说。（有些心心念念想看的片子还木有出DVD，国内又不引进的，借东西的小人、长发公主什么的，只有等明年了）
# 驯龙高手 | How To Train Your Dragon
傲娇系小萌龙和技术宅男主角都赞的。几个配角小龙也蛮有趣的。梦工厂这次的龙设很讨巧，线条有些拙，化掉了龙们的戾气，最终BOSS都觉得多凶的说。故事讲得也张弛有度，笑点什么的那是梦工厂的片子里从来不缺的。特别赞一下几个男主角和小萌龙单独相处时对小萌龙表情的控制。另外，小萌龙长得有点像MH里的迅妹，就是尾巴上不长刺。（我坚信这片子会出2）
# 卑鄙的我 | Despicable Me
这是本光明正大地宣称做全世界最大的大盗是天底下最了不起的事情的片子。第一遍看的时候，发现金字塔被偷走的开头很有冲击力。全片最出彩的是那些个明黄色的胶囊小人，很佩服主角可以记住他们每个的名字，DVD里附的3个短篇很好看。
# Mai Mai Miracle | マイマイ新子と千年の魔法
09年的片子。日本乡村风格。片子所谓的魔法只是一个毛头小妞凭空的想象力，因为生活平凡，就在乡间小路上狂奔时想象有个精灵和自己赛跑，想象千年前这土地上曾存在过的繁华的都城，以及都城里一位从京城来还没有朋友的公主。巧的是，来了个东京的转学生，穿和乡下人不一样的粉红洋裙，用24个颜色的彩铅，做客时的礼物是没见过的酒心巧克力（小时候我也吃过这个，好怀念啊）。然后是理所当然地被排斥，理所当然地偏偏和主角交好，理所当然地高潮，理所当然地现实与想象的冲突。好在这种温情的片子总会有个愉快的结尾。魔法什么的，是存在于每个人的心里的。
# 成为约翰·马尔科维奇 | Being John Malkovich
99年的老片。有点恐怖的说。男主角曾是个木偶艺人，偶尔在打工的七楼半公司档案室发现了一个小门，从那个小门可以通向一个名叫马尔科维奇的明星脑内，见其所见感其所感的无比真实的15分钟体验。于是男主角伙同某艳女做起了一门“Being John Malkovich”的生意，并渐渐学会了控制马科尔维奇，就像当初控制木偶一样。他呆在马科尔维奇脑内的时间越来越长，终于抛弃自己的肉体做起了马科尔维奇。结局是出乎意料的犀利，马科尔维奇和那个神秘的通道最初就是作为一群老头老太获得永生的工具而存在的，而主角被诱骗出马科尔维奇的身体，又误闯进其孩子的脑内，最后被幼儿强烈的潜意识吞没。这种永生方式新鲜的说，只是换做你，愿意作为自己死去，还是作为他人永生呢？
# 人类之子 | Children Of Men
这片说的是很久很久以后人类几乎失去了生育能力，这时一个在英国的非法移民非洲女孩成为了最后一个孕妇，被男主角保护着去找某传说中的友善组织。其实第一个逗号结束就是本片剧情的全部亮点了，导演真是会想。还有个亮点是片末一个好长好长的长镜头，豆瓣上这片的评论几乎赞的都是这个。技术的确蛮赞的。最后男主角死得也蛮好的，只可惜那个孩子木有死，不然这片子在豆瓣上就有9分了。不过，我的话，还是觉得谁都别死一起喝庆功酒比较好。
# 傲慢与偏见 | Pride And Prejudice
这片以前就老见猫看，今年我总算把它看了，还买了本原著，王科一版的。看了一遍，暂时还只能理会到爱情那一层，人性啥的没怎么看出来。私以为小说什么的，还是单纯些把故事写好人物写真就够了，什么中心思想什么段落主题都是后人瞎YY的GP，人家作者就是活得腻了YY了个“假如我的人生是这样”或者实现活得不得志发发牢骚。最讨厌某颜色学家。最后，这片好看的。
# 歪小子斯科特对抗全世界 | Scott Pilgrim vs. the World && 海扁王 | Kick-Ass
这两个片子放一起，因为都是打片。爽！爽！爽！前一个宅些，充满了电子游戏的影子。后一个的亮点是大力小萝莉，and我觉得会出续集。
# 深夜食堂
这不是电影，我顺便。09年番。是个充满了人情味的日剧。摘一段每段片头深夜食堂老板的话：
一天结束了 在大家都各自赶回家的时候 我的一天才刚刚开始
菜单只有这些（豚汁定食、酒什么的4样） 其他的只要是你喜欢的我能做的就可以点 这就是我的经营方法
营业时间是从晚上12点到次日早上7点
大家都把它叫做深夜食堂
你问这样还有没有客人会来？ 客人还挺多的
片子的大致故事就这样了，25分钟一集，都是些平凡的小故事，各式各样的人在深夜食堂的小房间里谈论着。很喜欢这种气质的片子。
OP也赞，推荐下。铃木常吉「思ひ出」。
一台本子、一颗大饼。
OVER。
November 16, 2010
奥利奥不能没事乱咬了
冬天开始许久了，都说今年是千年极寒，但是专家说寒不寒的要等到冬天结束才会知道。上海某正保暖改造的旧高楼着了，几个老太老爷从十几楼跳下脚手架上避火，死了五十三重伤了七十，消防队员说喷水其实不能灭火我们喷喷就是为了让群众觉得我们还是在做事情的。方便的咖啡奶茶不敢乱喝了，奥利奥不敢没事乱咬了，雀巢在国外说氢化植物油害人在国内却好好好卖，麦当劳说不关我们的事。然后今天，蜂蜜有害，强生也含二恶烷了。账户里只有虽然四位但1字打头的存款，我每天都不只一次想到，这世界里的至少中国大陆没法活了。移民什么的只有等到爸妈都去了才能考虑，那也是二十三十年后的事情，说不定到那时韩国人都统治世界了。
老妈电话里老问忙吗，我想了想只有回答就这样。不忙吗？忙的，每天实验室待到10点，每周休息0.5天，工作50小时才刚刚够到老板心里认真工作的底线边缘。忙吗？那要看对忙的定义是啥了，一年300天如此，别人的忙在你这里是日常，不忙是太闲了。这世界变化太快了，你如何让一个每天油盐酱醋9点半就打瞌睡的淳朴老妈，理解你12点睡觉叫早10点半了还在街上买炒粉干的行为。
还有十几天MHP3就发布了，可我2G还在下位混，看到轰哥就怕。说起来，这游戏当初第一次玩过就删了，觉得无聊而且丑，后来不知不觉又捡回来了，现在睡觉前每日一怪砍得不亦乐乎。多玩论坛上见到好多人都是这样，总要辗转反侧几次才能发现MH的美。今天在多玩上看到某MH饭的2G回忆录SP，我这个长年潜水的人都忍不住回了贴，剪得赞，BGM配的更是赞，热血，还励志。我总是想，要是这现实世界，有和做猎人一般单纯就好了，哪有那么多花花肠子，不过就是你死我活，还要说什么友谊第一，虚伪！
只要你骨子里有那么一点点热血，绝对会爱上这燃到内牛满面的BGM，虾米地址狂点我！
码完继续看论文。
November 2, 2010
[论文笔记] Multi-view video based multiple objects segmentation using graph cut and spatiotemporal projections
Paper：Qian Zhang, and King Ngi Ngan. Multi-view video based multiple objects segmentation using graph cut and spatiotemporal projections. In Journal of Visual Communication and Image Representation, Pages 453-461, 2010.
问题描述：这篇文章旨在从多视点视频中分割多个前景物体——Interested Objects（IOs），也是一个综合多通道信息的大算法框架，如下图所示。吸引人的地方在于据作者所述，该算法表现出不俗的精确度、效率和鲁棒性。在架构5个摄像头的实验中，处理640*480分辨率的视频能达到30fps的梦幻速度（不知是否包括预处理和离线操作）。并且，题目中的多前景物体分割也很具吸引力，虽然就实验结果来看，作者并没有考虑前景物体的重叠遮挡情况。
- 预处理阶段，做色彩归一化和定标，杂务。
- 离线阶段，生成一些用于在线阶段的辅助信息：Motion field[1]、Disparity field、Occlusion map、Depth map和Combined occlusion map（详细描述见论文），三维重建相关，可参阅其他文献。
- 关键视点初始帧操作：
1） 文章引入一些High-level Feature到Saliency model，如Motion、Depth等。Saliency model（SM）旨在表现人会更关心一幅图像中的那些部分，比如相较于背景更关心前景、更关心运动的物体、更关心图像的中间部分或色彩明艳的部分等。因为人比起机器，更懂得识别场景的语义，所以学人，总是没错的。那么，SM中拥有较高值的块将触发下一步的操作，如下图。
2） 基于Graph cut的多前景物体分割。文章修改了基本的能量方程（事实上，每篇文章都改），在色彩和平滑度的基础上增加了对像素重叠（前景物体边缘是重叠的高发地带，因此联合重叠部分CO比可见部分更有可能是背景）和对比度变化[2]的考虑。另外，对于每一个前景物体，graph cut是分别进行的，在一个Object Rectangle中，用于限制物体的最大区域。and，就文章的实验结果来看，的确比基本的能力方程更有效，如下图。 - 多视点视频前景分割：
1） 根据上一步得到的关键视点初始帧轮廓，可以通过Visibility Constraint得到其他视点的粗略轮廓；
2） 类似的，可以通过Motion Projection来获得后继帧的粗略轮廓；
3） 对于不确定的前景物体边界，再基于像素的activity measure（运动的变化量）应用一次Graph cut来得到精确轮廓线。
首先，文章的实验结果是暂时所见到的诸多segmentation文章中最美好的，虽然只有两个实验用视频，且鉴于以往经验，论文所述的实验结果和conclusion在实际重复其工作时，总会打上些折扣。
其次，私以为，文章存在以下limitation：1）没有考虑前景物体间的遮挡，至少文中并没有说明或证明算法能解决这一问题；2）由于文中算法对除关键视点初始帧以外的其他帧和视点，采取了基于关键视点初始帧轮廓投影的方法，来得到粗略轮廓，也就是说，可能存在由于关键视点初始帧操作崩坏，而带来的集体崩坏现象。那么，我们有理由怀疑文章算法对其他视频的适用性；3）同2）原因，文章算法很可能无法简单地适用于前景物体变化较大的视频，比如突然多了一个人；4）鉴于真实经历，相机定标等杂务，绝不如其在文章中的比例和重要性一样轻巧，并且往往有可能是带来后继问题最多的一部分。
综上所述，虽然文章很美好，拿到实际应用中，总是堪忧的。
[1] L. Itti, P. Baldi, A principled approach to detecting surprising events in video, IEEE Int. Conf. Computer Vision (2005) 631–637.
[2] J. Sun, W.W. Zhang, X.O. Tang, H. Y Shum, Background cut, ECCV (2006).
[论文笔记] Joint 3D-Reconstruction and Background Separation in Multiple Views using Graph Cuts
Paper：B. Goldlcke, M.A. Magnor. Joint 3D-reconstruction and Background Removal Separation in Multiple Views Using Graph Cuts. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition（CVPR ‘03）, page 683–688, 2003.
问题描述：这是篇03年的老文章，老耿给的且瞅着作者长得挺不错（点我点我）——其实前面的才是重点，通读了一下。文章的亮点在于同时处理Depth map estimation和Background seperation问题，当然是Multi-view的，而且是精确定标的（不像09年那位拿硬件捣鼓，这篇文章是基于图像像素算算算出来的）。文章认为，如果已知每个像素的深度，那么只有那些深度小于背景的像素，才有可能属于前景；同时，考虑背景因素可以提高三维重建算法的鲁棒性。
帅气一作的强项是三维重建，因此前背景分割则比较像站在他人肩膀上的那位。作者在文中以及Abstract里反复说文中的优化算法衍生于Kolmogorov等人的Multi-Camera Scene Reconstruction via Graph Cuts，他们做的工作是Generalize，所以文章本身的算法描述部分没什么亮点。它的好看之处在于作者对二维点的三维关系和三维点的二位投影的优美定义和量化。
 | 深度的定义：如果有个面P，所有的摄像头都在P的一边，且朝向P的另一边，那么可以认为在P上的点拥有相同的深度D。这个深度其实是一个离散的、相对的概念。 拓扑结构的定义：Np，指在Pk上与p点相邻的所有，能量函数在这个集合上应当是连续的；Cp，指包括p点的相邻点，用于作为判断图像一致性的标准。 几何结构的定义：<p, l>和<q, l>相交，指p, q来自不同的摄像头，且p是图像上最接近<q, l>在cam j上投影点的点，这种二元关系组成集合打不出来的花体D，其中<p, l>指点p的三维点。(1) <p, l>遮盖<q, l’>，指满足(1)关系，且Id’＜Id（也就是深度小），这种二元关系组成集合打不出的花体J。 |
然后就可以帅气地定义能量方程：
其中，第一项指图像一致性，即通俗点讲，如果p,q是同一点，那么其相邻点集合Cq, Cq应该差不多；
第二项指平滑性，即通俗点讲，如果p, q相邻，且它们的颜色也差不多，那么它们的深度也应该差不多，或者在是否是背景这一点上应该是一致的；
第三项指可视性约束，即通俗点讲，如果cam j看到深度为Id的点p，其为<p, l>的投影，<p, l>投影到cam k上最近为q点，那么q点的深度不可能比p点大；
第四项指背景属性，即通俗点讲，如果一个点是背景，那么必须有和背景一样的深度。
具体的量化见论文。
然后，balabala定义完后，就是Graph Cut上演最小能量优化，略。
算法结果上来讲，比03年同期的分割算法好些，但是速度嘛。。作者当年用1.8GHz的Pentium III Xeon做个初始化要30秒，320*240的图片处理需要约4次迭代290秒，有点慢的说。。不过人家当年可没有GPU加速的Graph Cut可以用，CPU也够呛，所以放到现在实现起来有多少效率也不知道。不过，鉴于大多源自重建算法的图像分割效率都不怎么样，私以为这算法在效率上是没什么看头的。其余，精度尚可，鲁棒性其实论文说什么都是假的，灵活性倒是高——不用添置新硬件，软件什么的改改还是方便的，总能找到能尝试优化的地方——虽然大多时候是有限且低效的。
以上。
November 1, 2010
[论文笔记] Combining Color, Depth, and Motion for Video Segmentation
Paper：J. Leens, S. Piérard, O. Barnich, M. Van Droogenbroeck, and J.-M. Wagner. Combining color, depth, and motion for video segmentation. Proceedings of the 7th International Conference on Computer Vision Systems: Computer Vision Systems（ICVS ‘09）, pages 104–113. Springer, 2009.
问题描述：本文引入TOF摄像头（文中指PMD-camera，TOF-cam的一种），对视频场景做新的解释，并结合传统的彩色分割技术、动态分割技术，做前背景的分割。
传统摄像头提供彩色图像，而PMD-camera提供物体距离、信号强度、信号密度等和物体空间位置相关的场景属性，是一种十分有前景且年轻的技术。不过同时，TOF摄像头也存在一些暂时无法解决的问题，如信号的噪声、受传感器大小限制的分辨率（160*120）、以及估算距离的致信区间、还有定标难等问题。尽管如此，这种新硬件对于交互领域还是非常有趣和有价值的。
文中的方法基于像素做前背景分割，避免对场景内容的假设，也不需要任何3D模型的支持。方法结合背景相减技术（Background subtraction tech.）对获得的区域图（Range map）进行处理，获得更鲁棒和准确的分割结果。比如，当人物的颜色和背景的颜色相近时，基于色彩的传统背景相减技术就可能失效，而基于红外信号反馈的PMD-camera就可能返回可用的结果；而，当人物和背景的材质相近，也就是说对红外信号的吸收相近时，传统背景相减技术就能弥补PMD-camera的失效。
作者简单地将两种摄像头上下捆绑，采用简单地仿射变换来对齐图像，回避了TOF-cam定标难的问题。文中采用的背景相减技术引用了09年O. Barnich等人发表的ViBe - a powerful random technique to estimate the background in video sequences 一文，其最显著的特点在于通过一种随机策略来建立基于样本的背景估计和一种全新的策略在相邻的像素间传播信息和状态。
文中提出传统技术和PMD-camera联合策略还是比较简单易懂的，如上图所示。图中，T&I 指代Transformation and Interpolation，G.R.指代Geodesic Reconstruction（待考证是什么意思）。究其本质，意在让两种方法互补缺点，如下图所示。据文中所言，能达到实时的速度，较之一些结合立体视觉和颜色技术的算法目前所见最多只有9fps的速度，还是很有吸引力的。
Subscribe to:
Posts (Atom)