Monthly Archives: November 2006


吃完晚饭到现在,一直在debug一个问题。就是在用cvFindContours()的时候找的边缘不正确。我的这段代码是从以前的代码中copy过来的,应该没有问题。但是我的程序里有两部分用到这段代码,一处contours找的正确,一处找的不对,而且出错的结果让人想不到是哪里出了问题。因为代码是一样的,按理说是不应该错呀。就这样6个小时过去了,郁闷个半死,最后才发现是第2处读入的图像不在是二值图像了,虽然我保存时是二值图像。多亏有了Adobe photoshop,我可以查图像里每个象素的RGB值,这才发现了问题。

Implementing Dijkstra using (Fibonacci) Heap

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: (’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

为写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

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:
  MENUITEM "Poisson Image Editing",       ID_DSTVIEW_POISSON
  MENUITEM "Drag and Drop Pasting",       ID_DSTVIEW_DDPASTING
2. Overwrite the message handler for WM_CONTEXMENU, then it is done.
void CDstView::OnContextMenu(CWnd* /*pWnd*/, CPoint point)
      CMenu   popupmenu;  
      CMenu*   popup=popupmenu.GetSubMenu(0);  


Double buffer drawing

// declare memory dc
CBitmap MemBitmap;
// create bitmap object so that there is some space for the memory dc to draw
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

// drawing

// copy data from memory to screen

// delete memory dc

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

Using 2 views for a single document

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(CChildFrame), // custom MDI child frame
 if (!pDstTemplate)
    return FALSE;
 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");
      return FALSE;     // command failed
 CPhotograph2App*  pApp = (CPhotograph2App*)AfxGetApp();  
 ASSERT_POINTER(pApp, CPhotograph2App);
   //CDocTemplate* pTemplate = pDocument->GetDocTemplate();
   CMultiDocTemplate* pDstTemplate = pApp->GetDstTemplate();     
 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);