Author Archives: fli10

程序写的好慢

1 Reply

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

The intersection of two planes

1 Reply

今天写程序要求两个平面的交线方程，叉乘一下两个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

N1 . p = d1

N2 . p = d2

The equation of the line can be written as

p = c1 N1 + c2 N2 + u N1 * N2

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 c1 and c2.

N1 . p = d1 = c1 N1 . N1 + c2 N1 . N2

N2 . p = d2 = c1 N1 . N2 + c2 N2 . N2

Solving for c1 and c2

c1 = ( d1 N2 . N2 – d2 N1 . N2 ) / determinant

c2 = ( d2 N1 . N1 – d1 N1 . N2) / determinant

determinant = ( N1 . N1 ) ( N2 . N2 ) – ( N1 . N2 )2

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

N1 * N2 = 0

Photography的homework终于做完了

2 Replies

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

过去的六个小时

Leave a reply
吃完晚饭到现在，一直在debug一个问题。就是在用cvFindContours()的时候找的边缘不正确。我的这段代码是从以前的代码中copy过来的，应该没有问题。但是我的程序里有两部分用到这段代码，一处contours找的正确，一处找的不对，而且出错的结果让人想不到是哪里出了问题。因为代码是一样的，按理说是不应该错呀。就这样6个小时过去了，郁闷个半死，最后才发现是第2处读入的图像不在是二值图像了，虽然我保存时是二值图像。多亏有了Adobe photoshop，我可以查图像里每个象素的RGB值，这才发现了问题。
 
最后的结论是：把二值图像使用JPG格式保存时，由于JPG是有损压缩编码，虽然视觉上看不出什么问题，但是保存后的图像已经不再试二值图像了，最终导致cvFindContours()没能找对边缘。对策就是把图像保存成BMP格式。至此，终于迈出了第一步。

Implementing Dijkstra using (Fibonacci) Heap

6 Replies

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).

Sparse matrix solver

3 Replies
为写Photography的作业，要用到sparse matrix solver。原以为OpenCV中有这个solver，毕竟里面定义了CvSparseMat这个结构，还有cvSolver()等函数，我还真的相信了。花了些时间把OpenCV里的Matrix运算的看了一遍，然后也写好了代码，结果cvSolver()一直报错，很认真地检查code，改了不少matrix运算的策略还是不行。上yahoo 的group搜了一把，才发现opencv里的CvSparseMat就是个噱头，只是用来存数据的，只有histogram这个函数能用sparse matrix，其他函数都不能用。我晕。。。
 
想着IPP应该有sparse matrix solver的，想着自己对IPP还比较熟，OpenCV不行还有IPP。结果down下来也没有，这样就只有MKL这唯一的希望了。不过真地不想用Intel的这些库，虽然效率高，但是用起来真地不太方便，而且把数据从opencv的格式导成MKL/IPP的格式也挺麻烦，我就放弃了。最后还是选用了TAUCS这个库，现在用起来还不错，它可以同时解多个方程，如果Ax=b中A不变。这样我就可以对3个通道同时求解了，cool。

Add popup menu for right click

2 Replies
It is said that popup menu is one of the great creatures by Microsoft. And it is easy to add the popup menu in your MFC application. In fact, there are only 2 steps you need to do:
1. Create the menu resource for the popup menu, like this:
IDR_MENU1 MENU
BEGIN
 POPUP ""
    BEGIN
  MENUITEM "Poisson Image Editing",       ID_DSTVIEW_POISSON
  MENUITEM "Drag and Drop Pasting",       ID_DSTVIEW_DDPASTING
 END
END
2. Overwrite the message handler for WM_CONTEXMENU, then it is done.
 
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);  
}

google黑板报

Leave a reply

Double buffer drawing

Leave a reply
写了一个程序要在现有的图片上画任意形状的曲线选择一个区域，直接用pDC->SetPixelV()画时图片不闪，但是画的曲线一直在闪，可能是我在MouseMove()里用了Invalidate()的缘故。后来在OnDraw()里用了双缓存，这个问题就解决了。
// 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();

在画曲线时用MouseMove()时会把一些点丢掉，可能是没有来的及响应吧。这时我用Bresenham把相邻两个点Rasterize了一下。可以search了一下 LineBresenham，就可以找到相应的code。

Using 2 views for a single document

Leave a reply
In order to use more than 1 views for a singel document, one should add another document template. If adding this snippet code to InitInstance() directly, one would encounter a dialog to select different documents although you only have one type of document. Commonly, there are 2 methods to avoid this dialog: first is to declaim different resource ID for the second document template, and blabla…; second is to add the second doucment template to other place other than the InitInstance(). See:
BOOL CPhotograph2App::OnDstTemplate()
{
 pDstTemplate = new CMultiDocTemplate(IDR_Photograph2TYPE,
  RUNTIME_CLASS(CPhotograph2Doc),
  RUNTIME_CLASS(CChildFrame), // custom MDI child frame
  RUNTIME_CLASS(CDstView));
  
 if (!pDstTemplate)
    return FALSE;
 AddDocTemplate(pDstTemplate);          
  
 ASSERT_VALID(pDstTemplate); 
 return TRUE;
}
 
Then you can create the view when necessary. Remember to InitialUpdateFrame after CreateNewFrame.
// CMainFrame message handlers
BOOL CMainFrame::OnDstWindow()
{
   CMDIChildWnd* pActiveChild = MDIGetActive();
   CDocument* pDocument;
  
   if (pActiveChild == NULL ||
      (pDocument = pActiveChild->GetActiveDocument()) == NULL) {
      TRACE0("Warning: No active document for WindowNew command.\n");
      AfxMessageBox(AFX_IDP_COMMAND_FAILURE);
      return FALSE;     // command failed
   }
  
 CPhotograph2App*  pApp = (CPhotograph2App*)AfxGetApp();  
 ASSERT_POINTER(pApp, CPhotograph2App);
   //CDocTemplate* pTemplate = pDocument->GetDocTemplate();
   CMultiDocTemplate* pDstTemplate = pApp->GetDstTemplate();     
 
 ASSERT_VALID(pDstTemplate); 
 CFrameWnd* pFrame = pDstTemplate->CreateNewFrame(pDocument, pActiveChild);
  
   if (pFrame == NULL)   {  
    TRACE0("Warning: failed to create new frame.\n");   
    return FALSE;     // command failed
   }
 
   pDstTemplate->InitialUpdateFrame(pFrame, pDocument);
}