一个月前写的，还是贴出来了。

———————————————————–

How to do research — The thesis

2006-11-04

你的论文将会占用你研究生阶段绝大部分的时间。你需要投入大量大量的时间来作研究，甚至是去选择topic，而不是实际的写作。

硕士论文可以说是博士论文的联系，没有好好准备，是很难做好PhD-level的研究的。硕士论文主要是以文字的方式表明你的没mastery：你已经完全明白你自己领域的研究状况，并且你已经可以在那个层次上做些研究。这并不要求你能扩展the state of the art, 也不要求硕士论文能发表。

Choosing a topic is one of the most difficult and important parts of thesis work. A good thesis topic will simutaneously express a personal vision and participate in a conversation with the literature.

The hardest part is figuring out how to cut your problem down to a solvable size while keeping it big enough to be interesting. You will find you need to continually narrow your topic. Choosing a topic is gradual process, not a discrete event, and will continue up to the moment you declare the thesis finished. Acutally solving the problem is often easy in comparison to figuring out what exactly it is.

An ideal thesis topic has a sort of telescoping organization. It has a central portion you are pretty sure you can finish and that you and your advisor agree will meet the degree requirements. It should have various extensions that are successively riskier and that will make the thesis more exciting if they pan out. Not every topic will fit this criterion, but it’s worth trying for.

Choosing a Master’s topic can be harder than choosing the PhD topic, because it has to be done before you know very much and before you’re built much self-confidence.

One parameter of PhD topic choice is whether to continue working in the same subfield as your Master’s, perhaps extending or building on that work, or to switch to another subfield. Staying in the same field simplifies things and probably will take one to two years off the total time to graduation, especially if a PhD-sized topic becomes obvious during the course of the Master’s work. But it may leave you "typecast" as someone who does shape-from -shading or circuit analysis; changing fields gives you breadth.

Once you’ve got a thesis topic, even when it’s a bit vague, you should be able to answer the question "what’s the thesis of your thesis?" what are you trying to show? You should have one-sentence, one-paragraph, and five-minute answers. If you don’t know where you are going, people won’t take you seriously, and, worse, you’ll end up wandering around in circles.

There is a number ways you can waste a lot of time during the thesis. Some activities to avoid (unless they are central to the thesis): language design, user-interface or graphics hacking, inventing new formalisms, overoptimizing code, tool building, bureaucracy. Any work that is not central to your thesis should be minimized.

http://www.cs.indiana.edu/mit.research.how.to/section3.11.html

—————-

这篇太长了，讲了太多的都很有价值的东西，感觉一下子都无法变成自己的意识。

不过，看完后至少改变我对thesis topic的看法。整篇文章都在讲thesis topic很重要（当然从上一篇文章已经知道最主要的决定是如何选老板），因为这个毕竟最终要占据你博士阶段大部分的时间。以前觉得选topic就想去超市买菜一样，虽然不会那么轻率，但是也不是很值得那么重视。文章里指出，选择topic是一个逐渐的过程，而不是一个离散的时间。你会不停的narrow你的研究方向，突然有一天你会说that’s it, 然后你完成了你的thesis。毕竟发现你要研究的问题要比解决它困难的多。

看完这篇文章后，更让我觉得我当时换专业是对的。如果当时申请时还是申请machine learning or pattern recognition方面的，我真的可能会早毕业一两年，但是我这么做给了我breadth。我能明显感觉到我比我们lab的其它的同学更了解一些用在machine learning的一些基本方法或算法，还有一些其它理论知识。当时换了新的方向后，要学很多的新的东西，这样进展会慢许多。不过我相信最终都是有回报的。

现在我看来，可以将Visual Hull作为我master thesis的方向，我可以在2年的时间内完成它，在这两年内再逐渐找到自己的方向，然后把自己博士阶段的精力放到那个方向上面。

文章最后还讲了一些thesis avoidance, 举了一些会浪费时间的例子。自己的时间很宝贵，我很想在博士阶段做出很有成就感的东西，但并不意味着我想晚一些毕业。我需要好好安排我的时间，一些对研究不重要的事情就不要做，集中精力做最重要的事情。这也是我最近为什么不再看Qt的原因。

做完一个homework，紧接着就开始做final project了。现在只有一周的时间来做final project了，但是final project里有很多的geometry computation, 自己以前也没有做过，所以做起来好慢。本来花了两天的时间到网上找了Computer Vision Library, VxL，看起来功能很多，还专门有一个geometry computation的package，花了些时间熟悉了一下。后来advisor给我讲了一些基本的处理流程，觉得也不太复杂，自己可以搞定geometry computation这块。但当自己开始去写得时候却又发现，事情还是不那么简单。自己每写一个函数，都又像做几何题一样，自己先算两遍，没有问题了再去code，这样就花了好多时间，写得好慢，还不清楚能不能在deadline之前搞定。

今天写程序要求两个平面的交线方程，叉乘一下两个normal就得到了直线的方向，但在求那个点的时候卡住了。自己写一个求点的程序，发现要check好多情况，程序好繁。实在忍受不了了，就google search一下居然有这么cool的求交线上任意点的方法，看来自己是在是太fool了。

The intersection of two planes

Written by Paul Bourke
February 2000

The intersection of two planes (if they are not parallel) is a line.

Define the two planes with normals N as

N₁ . p = d₁

N₂ . p = d₂

The equation of the line can be written as

p = c₁ N₁ + c₂ N₂ + u N₁ * N₂

Where "*" is the cross product, "." is the dot product, and u is the parameter of the line.

Taking the dot product of the above with each normal gives two equations with unknowns c₁ and c₂.

N₁ . p = d₁ = c₁ N₁ . N₁ + c₂ N₁ . N₂

N₂ . p = d₂ = c₁ N₁ . N₂ + c₂ N₂ . N₂

Solving for c₁ and c₂

c₁ = ( d₁ N₂ . N₂ – d₂ N₁ . N₂ ) / determinant

c₂ = ( d₂ N₁ . N₁ – d₁ N₁ . N₂) / determinant

determinant = ( N₁ . N₁ ) ( N₂ . N₂ ) – ( N₁ . N₂ )²

Note that a test should first be performed to check that the planes aren’t parallel or coincident (also parallel), this is most easily achieved by checking that the cross product of the two normals isn’t zero. The planes are parallel if

N₁ * N₂ = 0

Finally, 第2个homework终于做完了。虽然做了将近2个星期，但是觉得还是有很多收获的，比算法考试考好的感觉好多了（主要是两次算法考试考得比较差, :-)）。第2个homework主要是实现两个流行的Image Editing的方法，一个是Poisson Image Editing, 一个是Drag and Drop Pasting. 其中第2个算法是对第1个算法的改进。效果图如下。谢谢Sophie提供这么好的UD图片，呵呵。（本例里Drap and Drop Pasting的效果还是不是很好，主要是我只对当前K下算了最优路径，然后用break语句把程序break了，呵呵，只想看看结果。尽管如此，效果也比Poisson Image Editing 要好很多。)

Drag and Drop Pasting

Poisson Image Editing

Dijkstra Alogrithm:

Input:  Graph G, vertices S (start), T (terminate)
Declare:  H (initially empty heap)
1: For all vertices v
2:    if v == S then v.cost := 0
3:    else v.cost := infinity
3:    Insert v into H
4: Repeat
5:    M := ExtractMin(H)
6:    For each vertex A attached to M
7:       w := cost of edge from M to A
8:       if (M.cost + w < A.cost)
9:          DecreaseKey(A,M.cost + w)
10:         A.backlink := M
11: Until M = T
12: Output T.cost
13: Output vertices on chain of backlinks from T to S

Dijkstra’s algorithm sets the cost of each vertex (except the starting vertex) to infinity and puts all the vertices onto a heap. You then extract the cheapest vertex from the heap — call it M — and examine each vertex A adjacent to M. If the cost of M plus the cost of the edge joining M to A is cheaper than the current cost of A (that is, if there’s a cheap path to A through M), you create a link from A to M and decrease A’s key to represent the new cost. You continue extracting successive nodes until you reach T, the target vertex. The value of T is the cost of the shortest path. The links from T back to the starting vertex indicate the shortest path. 

As you can see in Figure 1, the DecreaseKey() on line 9 is the most time-consuming operation of the inner loop. Since Dijkstra’s algorithm is important in network routing and other applications, it would be nice to find a heap implementation that makes this operation as fast as possible. This is the primary motivation for the Fibonacci heap.

 —- By John Boyer

Running Time: (http://en.wikipedia.org/wiki/Dijkstra’s_algorithm)

The simplest implementation of the Dijkstra’s algorithm stores vertices of set Q in an ordinary linked list or array, and operation Extract-Min(Q) is simply a linear search through all vertices in Q. In this case, the running time is O(V^2).

For sparse graphs, that is, graphs with much less than V^2 edges, Dijkstra’s algorithm can be implemented more efficiently by storing the graph in form of adjaceny lists and using a binary heap or Fibonacci heap as a priority queue to implement the Extract-Min function. With a binary heap, the algorithm requires O((E+V)logV) time, and the Fibonacci heap improves this to O(E+VlogV).

IDR_MENU1 MENU
BEGIN
 POPUP ""
    BEGIN
  MENUITEM "Poisson Image Editing",       ID_DSTVIEW_POISSON
  MENUITEM "Drag and Drop Pasting",       ID_DSTVIEW_DDPASTING
 END
END

void CDstView::OnContextMenu(CWnd* /*pWnd*/, CPoint point)
{
      CMenu   popupmenu;  
      popupmenu.LoadMenu(IDR_MENU1);  
      CMenu*   popup=popupmenu.GetSubMenu(0);  
      popup->TrackPopupMenu(TPM_LEFTALIGN,point.x,point.y,this);  

}

// declare memory dc

CDC MemDC;
CBitmap MemBitmap;

// create bitmap object so that there is some space for the memory dc to draw
MemDC.CreateCompatibleDC(pDC/*NULL*/);
MemBitmap.CreateCompatibleBitmap(pDC,nWidth,nHeight);
CBitmap *pOldBit=MemDC.SelectObject(&MemBitmap);

// erase the background of the bitmap object,

// if so, you don’t need to re-define the OnEraseBkg(), I think
MemDC.FillSolidRect(0,0,nWidth,nHeight,RGB(255,255,255));

// drawing

…

// copy data from memory to screen
pDC->BitBlt(0,0,nWidth,nHeight,&MemDC,0,0,SRCCOPY);

// delete memory dc
MemBitmap.DeleteObject();
MemDC.DeleteDC();