Seam Carving -- 基于内容的图像缩放算法

1 背景

我们经常会有缩放图像的需求,然而直接缩放的问题是,如果宽高缩放比例不一致,会导致图像内容发生形变“失真”。

Seam Carving 算法是下面论文中提出的一种图像缩放算法,它的好处是可以尽可能保持图像中“重要区域”的比例,避免由于直接缩放造成的“失真”。

@inproceedings{avidan2007seam,
title={Seam carving for content-aware image resizing},
author={Avidan, Shai and Shamir, Ariel},
booktitle={ACM Transactions on graphics (TOG)},
volume={26},
number={3},
pages={10},
year={2007},
organization={ACM}
}

compare_resizing

上图是几种缩放方法的对比,左侧是 seam carving 结果,中间是直接缩放,右侧是 crop ,可以发现 seam carving 方法很好地保持了原图中大部分“信息”,且看起来画面中的主要物体也没有出现比例“失真”的情况(比如图片底部的岩石,直接缩放比例变化很大,crop 的话直接就没了)。

2 算法原理

基本思想

算法的基本思想非常直观,先考虑下沿着宽的方向进行缩放,缩放实质是删去了若干条纵向的像素“路径”(或者 seam,缝隙),直接缩放删去的路径都是竖直的长条,相当于沿着图像竖直方向做了均匀的降采样。那么我们为什么一定要删去竖直的“路径”呢,如果能保持删去路径后,剩余的图像部分还是“平滑”的,或者说删去的路径是最不重要的,那么不就实现了基于图像内容的缩放了吗?

于是该论文作者提出了可以删去“能量”最少的 seam 来实现图像缩小。

“能量” 如何定义,最容易想到的就是梯度信息:

用像素在水平和竖直方向上的一阶梯度值的之和来表示该像素点的能量,那么一条缝隙的能量就是该缝隙上所有像素点能量之和。

我们需要做的就是每次找到像素能量最小的一条缝隙,然后删去它。

seam with min energy

算法步骤

有了基本思想的铺垫,算法步骤也非常直观了,假设我们要删去 K 条 seam:

  1. 计算每个像素点的能量;
  2. 找到竖直/水平方向上的能量最小的路径,称为 seam;
  3. 移除 seam,得到新图像;
  4. 重复步骤 1 至步骤 3 K 次,得到缩放后的图像,

3 实现细节

More

韩国电影《寄生虫》观后感

韩国电影《寄生虫》,最近挺火,有人说尺度很大,中国肯定引进不了。今天花时间看完了,个人评价是一部好电影,但是给我的感觉又比较奇怪。

先说看完后最违和的一个感受:像影片中这种水平的富人,判断人的能力真有可能会这么差吗?家里突然换了一堆工作人员,就没有想到是诈骗的可能性?

其次,这部电影究竟想表达个啥?看起来像是在讽刺富人、穷人之间的阶级对立,不过这里的富人、穷人形象都不那么正面。我讨厌富人嫌弃穷人身上“味道”的态度,更瞧不起穷人一家坑蒙拐骗式的“寄生”。阶级问题自古以来就存在,想逾越阶级谈何容易,有时候靠几代人的努力都不够,还要靠机会、运气,不过本片中的男主一家,在我看来显然是选错了努力方向。

影片的结尾,看到男主幻想着自己赚了大钱买下豪宅,我还以为这是个励志片=. =

总的来说,有种强行制造冲突的感觉,看得挺爽,但看完回味起来又感觉各种不合理。

用 Python 实现“文档扫描”

“扫描全能王” 是我手机里一直都有的 App,我非常喜欢把一些纸质内容电子化,比如书中看到的喜欢的段落、日常生活中的票据、产品说明书等等。

如下图所示,只需要拍一张照片,App 就会自动识别文档的边缘,并将文档转换为“正视图”。

camscanner_demo.png

实际上这个 App 用到的算法非常简单,核心就是“边缘检测 + 透视变换”,下面我们就用 Python 和 OpenCV 实现一个简单的 Demo。我用 Tkinter 做了个简单的 GUI ,可以支持手动选择文档的角点,代码地址在:

https://github.com/insaneyilin/document_scanner

More

一个简单的 C++ 对象池实现

对象池

前一段时间的工作中,有一项任务是检查线上代码中的动态内存分配与释放,能预先分配的统一预先分配,减少线上运行时动态分配、释放造成的性能开销。对于一些大对象来说,频繁的分配、释放会影响性能,我们可以使用对象池技术(Object Pool)来进行优化。

对象池,说白了就是一个池子,预先分配了一堆对象,原先的 new 改成从池子里取对象,delete 改成把对象放回池子。也就是池子中的对象是可以重复利用的,避免了频繁的分配、释放。

按照上面的简单思路,一个对象池的基本功能应该包括:

  • 构造函数中申请一批对象
  • 析构函数中释放对象
  • 提供获取和回收对象的接口 Get()Recycle()
  • 池子空了的时候支持扩容

实现起来也不难,用一个队列维护所有对象,用的时候从队列中取,回收了 push 回队列即可。不过显式的 回收 操作用起来不是很方便,忘记回收会造成资源浪费。可以考虑利用 C++ 智能指针(smart pointer)自定义删除器(deleter)来实现自动回收。

自定义智能指针的删除器

先看一个例子(这是一个错误使用智能指针的例子,只是为了展示 deleter 做了什么):

int main(int argc, char **argv) {
  Object *obj1 = new Object;

  std::shared_ptr<Object> p1(obj1);
  std::cout << p1.use_count() << std::endl;

  std::shared_ptr<Object> p2(obj1);
  std::cout << p2.use_count() << std::endl;

  return 0;
}

运行结果:

1
1
malloc: *** error for object 0x7f845f400340: pointer being freed was not allocated
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

报错了,提示说释放了一个未分配的指针。这是因为 std::shared_ptr 默认的 deleter 就是 delete,当两个 shared_ptr 实例出作用域时,执行了两次 delete obj1,所以出错。

我们不用默认的 deleter ,试试自己定义一个 deleter 来避免第二次 delete (再强调下,这个例子只是为了展示 deleter ,实际工作中没人会这么写的):

More

高考10年

这两天全国各地陆续发布了高考分数线,我也刚刚过完了这辈子第 28 个年头,转眼间,距离我参加高考已经 10 年了。

我对自己高考总分印象很深,因为不多不少,正好和我中考总分一样。

More

夏虫不可语冰,井蛙不可语海

今天,在百度 AI 开发者大会上,Robin 正式宣布百度和金龙合作的 L4 自动驾驶小巴量产了,一起奋斗了大半年的同事们都很开心,金龙当天的股票还涨停了,大家调侃道怎么没想到早点买金龙的股票。

晚上回到家,打开知乎,刷到这样一个答案,真是哭笑不得😂:

如何看待百度称首款 L4 级别自动驾驶巴士量产下线?

论吹牛,百度说第二,没人敢说第一

这车就是一个简单的循迹行驶,架好差分GPS基站,先用人工开一遍,录一下轨迹,然后一直按着轨迹绕圈圈跑,连感知设备都用不上。

利益相关,匿了

这位答主贴的图的确是厦门金龙研发现场的,看得出来应该是一位“内部人士”。

看完这个回答和评论区内容,先是愤怒,然后是想笑,最后是无奈。

愤怒是因为我所在的组就是做感知的,没有任何证据直接说“连感知设备都用不上”相当于完全不认可我们的工作,更何况这还是一位内部人士(不太可能是 baidu 这边的人,如果是金龙的员工,那就更让人心寒了)。

想笑是由于答主在评论区里还俨然一副专家姿态,“自己百度差分GPS”(敢情还是得用百度😐),“装了感知设备,未必代表就用了”,“你自己想想这照片我怎么拍的,再猜猜我是做什么的”。当时我就想到一句话:

夏虫不可语冰,井蛙不可语海

无奈是评论里竟然还有很多人认同答主,这才是最可悲的。像这位朋友评论说“装几个简单的雷达或者红外绕车子一周,然后if else就差不多了。。。”、“实现广义的L4不难”都让人啼笑皆非。

一件本来很让人高兴的事情,却变了味道。一方面是 baidu 近年来的公众形象问题,另一方面也反映出大众对自动驾驶的认知还远远不够。

像上面这位“内部人士”显然对于自动驾驶是没有多少了解的,甚至可以说“无知”也不为过。但可怕的不是无知,而是面对自己不熟悉的内容的傲慢与偏见。

关于“夏虫不可语冰,井蛙不可语海”,还有一个老笑话:

联合国给几个世界各地的小朋友们出题:“关于其他国家粮食短缺问题,请大家说说自己的看法”。非洲小朋友不知道什么是粮食,美国小朋友不知道什么是其他国家,欧洲小朋友不知道什么是短缺,拉美小朋友不知道什么是请,中国小朋友不知道什么是自己的看法。

很讽刺不过也很现实。人哪有那么容易理解自己没见过的事物呢?从某种意义上来说,我们每个人都是“夏虫”。但是面对无尽的未知,我们不应该抱着傲慢的态度,而应该以开放、谦卑、学习的心态来对待。

以后遇到无法沟通的人或者无脑喷子,想想这句话,也就释怀了。

std::vector<std::shared_ptr<XXX> > 初始化的坑

现在写 C++ 用智能指针基本是习惯了,不过今天遇到一个细节处的错误:

std::vector<std::shared_ptr<A> > a_vec(n, std::make_shared<A>());

本意是初始化了一个元素都是智能指针对象的数组,看起来很美好,实际上这个数组里所有元素都指向了同一个实例。看一下 C++ 文档上的参数说明:

val
Value to fill the container with. Each of the n elements in the container will be initialized to a copy of this value. Member type value_type is the type of the elements in the container, defined in vector as an alias of its first template parameter (T).

vector 所有成员用 val 的拷贝来初始化,智能指针的拷贝嘛,还是指向同一个实例。

正确的初始化方式:

std::vector<std::shared_ptr<A> > a_vec(n);
std::for_each(std::begin(a_vec), std::end(a_vec), [](std::shared_ptr<A> &ptr) {
  ptr = std::make_shared<A>();
});

C++ 更新动态库后强制转换基类指针遇到的坑

这两天被一个 bug 折磨得不轻,发新版本更新了 caffe-output 动态库,结果发现某一 layer 中一个参数读出来是随机数,模型预测结果总是不对。最后一点一点找 diff,发现是发布时打包的 caffe 动态库有错误,新版本 caffe 基类 layer 增加了这个参数作为成员变量,而老版本 caffe 动态库中没有这个成员变量。

直接看下面的例子吧=_=_

More

美签小记

最近公司一些业务要派人去美国分公司出差半个月,虽然没准备派我去,不过作为刚入职半年的壮丁,难免以后要去当苦力,还是让我先去办理一下。

读本科的时候总想着去美帝读书,后来因为各种原因打消了念头,没想到工作没多久竟然要去办理美帝的签证,真是造化弄人。

问了下同事,办理的是 B1/B2 商务签证,大部分人都是一年签证,每年都要去办一次,还有种是十年签证,拿到的人比较少。

按照公司提供的流程准备了材料,提交给中美商会,然后等着去面签就可以了。

面签之前要准备好的材料有:

  • 护照
  • 蓝色面试预约单
  • 预约确认单
  • DS-160 确认页
  • 照片
  • 签证申请费收据
  • 邀请信(公司提供)
  • 在职证明
  • 英文简历

这里说下 DS-160 ,这表格真的够长,同事告诉我说一定要认真填,有些时候 DS-160 填写情况就决定了你这次签证成功与否。还有就是照片要是白色背景、不能戴眼镜。

面签当天,没想到人非常多,我预约的是9点半,最后排队到11点才轮到我。英语口语一直不太好,有点紧张,前一天晚上还找了些面签的对话材料练习了下,我前面的小哥用英文和签证官(一个白人小哥)扯了半天,好像签证官还是不太满意,小哥还来了句“我是英文专业的” Orz 。到我了,我刚想开口用英文说明申请理由,小哥用非常不标准的普通话问我:“你为什么要去美国?”(请自行脑补音调),我愣了一下没说话,他又重新问了一遍,我才反应过来,用中文回答道:“公司派我去的。”完了就让我递给他邀请信和 DS-160 确认页。我还再想等下会问到什么英文问题,结果小哥对我微笑着说:“你通过了,可以走了。”啥?这也太顺利了吧,我很怀疑😂

过两天查了下邮件,真的过了,还是 10 年签。。。总有种今年人品用光了的感觉。。。