做过全景拼接的人都知道，像是左边这样的拼接结果，一般的处理方式就是截取一个内接矩形，然而这样就丢失了很大一块内容。PS CS5(将在4月中旬发布）给出了一个先进而简单的解决方案：content aware filling，可以根据图像内容自动进行纹理填充。背后原理不明，是基于PatchMatch的么？
据说GIMP若干年前就有这样的纹理合成的插件了了。名字是Resynthesizer。不知道那个算法更牛逼些。这里甚至有好事者做的两者的效果对比，我把图贴到下面，懒人就不用点进去看了。
这里看官方报道和视频。
在往下读之前，先记住这幅图片！
以下排名非常分先后。
二：能查表就查表，能不用<math.h>就不用。
三：float转int是很慢的，如果编译器不用ftol2_sse或者ftol2_pentium优化的话。
参考：一个扩平台的，快速的float到int转换方法。http://mega-nerd.com/FPcast/ 阅读全文…
Submissions/Acceptances By Topic
Submissions/Acceptances By Year
恭喜陈同学有个poster啊。牛逼啊。
Seeing Machines拿到了最大订单，将Driver State Sensor (DSS)卖给挖掘业巨头Navajo Coal Company。DSS是利用眼部追踪技术制造的司机驾驶状态监视装置。特点是不需要标定。
DSS官方介绍
DSS Capabilities
The DSS-IVS (in vehicle system) measures the eyelid opening of the driver, and based on this data derives the drowsiness state. No sensors need to be worn by the driver; a remote sensor on the dashboard observes the face of the driver and measures eyelid closure. There is also no calibration procedure required for new drivers. This means any driver can get behind the wheel without any time consuming calibration, annoying sensor attachment process, or any special knowledge about the system.
老规矩，还是来自国内的触角科技的帖子，必转。
英国Augmatic公司基于增强现实技术，开发了一套面向学校的创新教具LearnAR。里面涵盖了生物、几何、物理甚至英语等学科，让学生以全新的体验并寓教于乐的学习知识。
当增强现实用于学校教学，除了提供一种全新的展示方式，其实更有意义的是带来一种全新的交互方式。考虑到由于硬件条件限制，或者由于一些危险因素不宜于在课堂上进行的实验，都完全可以通过增强现实的方式自然逼真模拟。触角科技的物理化学实验演示也是向这个应用方向努力的有益探索。
最后说两句：总的来说，这个演示视频比较无聊。。我还是觉得我的光学实验的想法比较有趣（请允许我自恋一下，哈哈），基于marker的增强现实简直是为虚拟光学实验量身定制的啊。
搬家了，暂无网线，转帖一枚。
I dislike animated sorting algorithm visualisations – there’s too much of an air of hocus-pocus about them. Something impressive and complicated happens on screen, but more often than not the audience is left mystified. I think their creators must also know that they have precious little explanatory value, because the better ones are sexed up with play-by-play doodles, added, one feels, as an apologetic afterthought by some particularly dorky sportscaster. Nevertheless I’ve been unable to find a single attempt to visualise a sorting algorithm statically (if you know of any, please drop me a line).
So, presented below are the results of a pleasant evening with some nice Scotch and the third volume of Knuth. First, here’s a taster – a static visualisation of heapsort:
I think these simple static visualisations are much clearer than most animated attempts – and they have the added benefit of also being, to my not entirely unbiased eye, rather beautiful. You will find more visualisations, source code, and a tediously long explanation of why I bothered, after the jump.
Before I go on, though, bear with me while I press home my point about animation with a particularly heinous example of the genre. I found the following specimen on the Wikipedia page for Bubblesort:
Now, it is my measured opinion that this animation has all the explanatory power of a glob of porridge flung against a wall. To see why I say this, try to find rough answers to the following set of simple questions with reference to it:
If you thought that was harder than it needed to be, blame animation. First, while humans are great at estimating distances in space, they are pretty bad at estimating distances in time. This is why you had to watch the animation two or three times to answer the first question. When we translate time to a geometric length, as is done in any scientific diagram with a time dimension, this estimation process becomes easy. Second, many questions about sorting algorithms require us to actively compare the sorting state at two or more different time points. Since we don’t have perfect memories, this is very, very hard in all but the simplest cases. This leaves us with a strangely one-dimensional view into an animation – we can see what’s on screen at any given moment, but we have to strain to answer simple questions about, say, rates of change. Which is why the final question is hard to answer accurately.
It turns out that it is pretty easy to find a static, two-dimensional encoding for the sorting process. The specific technique used here only works when the sorting algorithm is in-place, i.e. does not use any storage external to the array itself. Some of the algorithms below have been slightly modified from their standard forms to make sure they have this property. The magnitude of a number is indicated by shading – higher numbers are darker, and lower numbers are lighter. We begin on the left hand side with the numbers in a random order, and the sorting progression plays out until we reach the right hand side with a sorted sequence. Time, in this particular case, is measured by the number of “swaps” performed. This means that all swaps are equidistant on the diagram, and that only a single swap occurs at any point in time. When I refer to “time” when talking about these diagrams, I am therefore not referring to clock time.
Now, I should be clear at the outset that I haven’t tried to pack these diagrams with as much information as possible. For example, I don’t include tick marks for time units, nor do I explicitly mark algorithm details like pivot points for the Quicksort visualisation, or the heap for Heapsort. Instead, I’ve simply tried to produce images that give a clear sense of the “flow” over time of the algorithms, while simultaneously not being an eyesore. I might produce some scaled-up annotated versions of the diagrams for some future post.
So, lets start with a static visualisation of bubblesort. Notice that, even without any labelling, we can “read off” the answers to all the questions posed above pretty trivially:
Other features of the algorithm are also clearer – for instance, the famous “rabbits” and “turtles” are clearly identifiable. In the diagram the “rabbits” are the dark lines sweeping down to their positions rapidly, and the turtles are the lighter lines that gradually curve towards the top right of the image.
Now, lets return to the heapsort image at the top of this article. First, a quick (and superficial) refresher on the algorithm itself:
Looking at the visualisation, we can see Step 1 clearly – it is the portion of the diagram before the point where the largest element in the array is slotted into place. After that, we can see a repeated pattern – the heap is re-established and the greatest element is moved to below the heap again and again util the array is sorted.
We can immediately make some quite sophisticated observations. For example, we can see that although initially establishing the heap is costly, re-establishing it after the greatest element is removed requires an approximately constant amount of time throughout the sorting process – meaning that the time required is relatively independent of the number of items still in the heap. This is an interesting property that is not immediately obvious from an analysis of the algorithm itself.
Right – enough prattling! Here is a selection of other visualised algorithms for your viewing pleasure:
This whole thing started partly as an excuse to get familiar with the Cairo graphics library. It produces beautiful, clean images, and appears to be both portable and well designed. It also comes with a set of Python bindings that are maintained as part of the project itself – a big plus in my books. Firefox 3 will use Cairo as its standard rendering back end, which will instantly make it one of the most widely used vector graphics libraries out there.
The examples on this page were generated using a command somewhat like the following:
./visualise.py -l 6 -x 700 -y 300 -n 15
Update 9/8/09: A newer version of the code is now available on github. You can check it out like so:
git clone git://github.com/cortesi/sortvis.git
佩戴一个便携式的摄像头，录音仪，gps来记录身边发生的一切已经不是个新鲜玩意了。但是如何有效的挖掘，浏览，总结这海量的数据，却是个新鲜可挖掘的课题。
SenseCamera是微软研发的这种设备，有摄像头，光学传感器，红外传感器，加速仪等等。目前研究者致力于如何有效的组织采集到的影像等数据，来帮助记忆有困难的人来了解过去究竟发生了什么，从而不用像memento（记忆碎片）里那个可怜的家伙一样把自己全身刺满纹身了。
下面是相关研究的介绍引文，没时间翻了。
To find the best memory cues for Mr. Reznick’s experiences, the researchers — Anind K. Dey, a computer science professor at Carnegie Mellon University, and Matthew Lee, a graduate student — considered the types of images that had proved the most effective in previous SenseCam studies.
They soon realized that the capriciousness of memory made answers elusive. For one subject, a donkey in the background of a barnyard photo brought back a flood of recollections. For another, an otherwise unremarkable landscape reminded the subject of a snowfall that had not been expected.
Still, the researchers came up with some broad rules for identifying and retrieving images likely to serve as memory triggers. For a people-based experience like a family reunion, the system selects photographs in which faces are clearly discernible; for a location-based experience like a visit to a museum, it uses geographical positions provided by GPS and accelerometer data to judge what images might be most salient — for example, when a subject might be hovering at one spot, like in front of a painting.
Research groups elsewhere are experimenting with other techniques to summarize and make use of SenseCam data. Alan Smeaton and colleagues at Dublin City University in Ireland are comparing images to categorize them by activity — shopping, for example — so the system can put together a visual summary of the day. At the University of Toronto, a group led by Ronald M. Baecker is investigating the usefulness of complementing SenseCam images with an audio narrative created by a loved one.
Once the system selects some photos from the hundreds taken, the caregiver winnows down the candidates, adding cues like audio from the voice recorder, verbal narration and brief text captions. The final product is a multimedia slide show on a tablet computer that allows the patient to dig deeper into highlighted parts of some images by tapping on the screen. The first tap plays audio, the second shows captions.
“The design is intended to give the patient the ability to engage actively with the experience instead of simply flipping through some pictures,” said Mr. Lee, the graduate student. Testing the system with the Reznicks and two other couples, he and Dr. Dey found that it helped patients recall events more vividly and with greater confidence than when they simply went through all of the images.
Other SenseCam studies — also financed by Microsoft — have produced encouraging results, but plans to market the device as a memory aid have not been announced.
不了解大尺寸多点触摸屏，不好评价，但是看上去很美。来自Perceptive Pixel。
据称该公司的触摸屏是由光纤定位的，因而可以应用于任意尺寸的屏幕。而电容屏在大尺寸上就不行啦。
据称，大尺寸多点触摸屏一个几乎不可克服的缺点是在多人同时操作时，不能判断手指来自那个人。
据称电视节目中最早出现的多点触摸大屏幕（出现在CNN）就是该公司做的。
公司主页。
媒体报道。
最近搞了一下android开发，牵扯到一些log pow exp的运算需要优化，考虑到并不需要精确的数值结果，就尝试用一些近似解法代替c库函数，个人目前还没有能力设计这些近似算法，在网上搜集一些资源，跟大家共享一下，兼做笔记备忘。
log2的近似算法：http://www.musicdsp.org/showone.php?id=91
适用于IEEE 32-bit floating 型，误差在0.1左右。
/ Fast logarithm (2-based) approximation
// by Jon Watte
#include <assert.h>
int floorOfLn2( float f ) {
assert( f > 0. );
assert( sizeof(f) == sizeof(int) );
assert( sizeof(f) == 4 );
return (((*(int *)&f)&0x7f800000)>>23)-0x7f;
}
float approxLn2( float f ) {
assert( f > 0. );
assert( sizeof(f) == sizeof(int) );
assert( sizeof(f) == 4 );
int i = (*(int *)&f);
return (((i&0x7f800000)>>23)-0x7f)+(i&0x007fffff)/(float)0×800000;
}
pow, exp的查表近似算法：http://www.hxa.name/articles/content/fast-pow-adjustable_hxa7241_2007.html
适用于IEEE 32-bit floating 型，可以通过控制查找表的大小来控制精度。相对误差在0.01%~0.02%之间的情形下，查找表大小仅为8KB。
In C (89) (and assuming 32 bit integers), the core is:
const float _2p23 = 8388608.0f;
/**
* Initialize powFast lookup table.
*
* @pTable length must be 2 ^ precision
* @precision number of mantissa bits used, >= 0 and <= 18
*/
void powFastSetTable
(
unsigned int* const pTable,
const unsigned int precision
)
{
/* step along table elements and x-axis positions */
float zeroToOne = 1.0f / ((float)(1 << precision) * 2.0f); /* A */
int i; /* B */
for( i = 0; i < (1 << precision); ++i ) /* C */
{
/* make y-axis value for table element */
const float f = ((float)pow( 2.0f, zeroToOne ) - 1.0f) * _2p23;
pTable[i] = (unsigned int)( f < _2p23 ? f : (_2p23 - 1.0f) );
zeroToOne += 1.0f / (float)(1 << precision);
} /* D */
}
/**
* Get pow (fast!).
*
* @val power to raise radix to
* @ilog2 one over log, to required radix, of two
* @pTable length must be 2 ^ precision
* @precision number of mantissa bits used, >= 0 and <= 18
*/
float powFastLookup
(
const float val,
const float ilog2,
unsigned int* const pTable,
const unsigned int precision
)
{
/* build float bits */
const int i = (int)( (val * (_2p23 * ilog2)) + (127.0f * _2p23) );
/* replace mantissa with lookup */
const int it = (i & 0xFF800000) | pTable[(i & 0x7FFFFF) >> /* E */
(23 - precision)]; /* F */
/* convert bits to float */
return *(const float*)( &it );
}Setting the ilog2 parameter:
pow( 2, val), ilog2 = 1 / log2(2) = 1pow( e, val), ilog2 = 1 / log(2) = 1.44269504088896pow(10, val), ilog2 = 1 / log10(2) = 3.32192809488736pow( r, val), ilog2 = log(r) / log(2) = log(r) * 1.44269504088896These two functions can easily be put in a small class/module that manages the storage and wraps calls for different radixes.
pow, ln近似算法：http://www.hxa.name/articles/content/fast-pow-adjustable_hxa7241_2007.html
适用于IEEE 64-bit double 型。
double pow(double a, double b) {
int tmp = (*(1 + (int *) &a));
int tmp2 = (int)(b * (tmp - 1072632447) + 1072632447);
double p = 0.0;
*(1 + (int * ) &p) = tmp2;
return p;
}
最后附送一坨位运算技巧：http://graphics.stanford.edu/~seander/bithacks.html
最新评论