Topology, Geometry and Algebraic

Topology space: video

Real Analysis: book(Zejian Jiang)

Globle differencial geometry: book, TsingHua webpage

n-Manifold:  Direct concept, wiki, video

Advertisements

CSE595 Final Project: Ricci Flow

Discrete Ricci Flow Algorithm

Results

Reference

CSE590 Final Project: Animating Pictures with Stochastic Motion Textures

Abstract

Algorithm

Results

Project Write-up: report

Video animation:

Reference

Criminisi, A., Perez, P., and Toyama, K. 2003. Object removal by Exemplar-based Inpainting. IEEE Computer
Vision and Pattern Recognition.
Criminisi, A., Reid, I. D., and Zisserman, A. 2000. Single view metrology. International Journal of Computer
Vision 40, 2, 123-148.
Jason, L. M. 2005. Real-time synthesis and rendering of ocean water. ATI Research Technical Report.
Jiahe, Xi. Homepage. http://sites.google.com/site/jiahexi2/
Sooraj, Bhat. Object removal by Exemplar-based Inpainting. Project webpage: http://www.cc.gatech.edu/~sooraj/inpainting/
Tessendorf, J. 2001. Simulating ocean water. Siggraph course notes.
Yu-Ting, W. Digital Visual Effects. Project webpage: http://graphics.im.ntu.edu.tw/~kevincosner/courses/vfx/final_project/webpage/index.html
Yung-Yu, C., Dan, B. G., Brian, C., David, H. S., and Richard, S. 2005. Animating pictures with stochastic
motion textures. ACM Transaction on Graphics (TOG) – Proceedings of ACM SIGGRAPH 2005, Volume
24 Issue 3, July 2005.

CSE595 HW3: Cut Graph

Abstract

Goal: Transfer 3D mesh into 2D disc.

Kernel: Compute homology group basis (loops {α_i, β_i}).

Method: Cut through the loops on 3D mesh.

Cut Graph Algorithm

Input: a closed triangle mesh.

File type: .m / .obj

Mesh condition: Closed

Mesh data structure: Halfedge

1. Compute a spanning tree of all faces T_f.

.                                                       *

.                                                                 triangle mesh and dual mesh

I. Concept. We denote triangle mesh as M, and dual mesh as M*. The dual mesh M* has a node for every face and it has an edge between two nodes if the corresponding faces share an edge.

.                                                                     

II. Illustration: Set a fire on lawn. We cover the mesh M with lawn, and set a fire at an arbitrary face of it. Gradually, the fire will spread through all the faces of the mesh M. Computing the spanning tree of all faces, we find all necessary and non-redundant daul edges e*∈T_f to connecting all faces of M. It is obvious that connecting all faces of M by e* will generate a plane disc.

Note: There are two algorithm commonly used to compute (minimum) spanning tree, Prim’s algorithm and Kruskal’s algorithm. We choose Kruskal’s algorithm here, since it can generate an face list during the process. In this section, we used std::queue and std::list data structures to record the nodes union and spanning tree separately.

2. Cut graph = {e | e∉T_f}.

Cut graph {e|e∉T_f} denotes the useless edges to connect all faces in M. So we can cut through all edges belong to cut graph without destroy the plane disc.

.                                            

Note : Cut graph is composed by edges of M, other than dual edges of M*.  As the above figure, we set a fire at the yellow node of M*, and then compute a spanning tree as the green dual edges. The blue dual edges in M* present the useless dual mesh to connecting all faces. From the definition of “dual mesh”, each dual edge of M* corresponds to an unique edge in M. Thus, we mark the black edges in M as cut graph.

3. Compute a spanning tree of cut graph T_g.

In order to generate loops in cut graph, we process the step 3, 4 and 5 continually.

4. {e_1, e_2,…, e_2g} = cut graph – T_g.

{e_1, e_2,…, e_2g} present the remaining edges in cut graph after eliminate the spanning tree of cut graph.

5. e_k ∪ T_g has a unique loop r_k.

Note: For each e_k, we compute two paths in the spanning tree of cut graph which start from the two nodes of e_k separately. Then, we eliminate the overlapping edges of these two paths.

Output: a set of loops {r_1, r_2,…, r_2g}.

Results

.      .                                   

.          Input triangle mesh file: eight.m                            Output triangle mesh with loops file: eight.uv.m

Reference

Prof. David Gu’s tutor: webpage.

MIT Adjacency Data Structure.

Robust Face Recognition via Sparse Representation

Publicaions:

Robust Face Recognition via Sparse Representation

Personal Websie: http://yima.csl.illinois.edu/ EEMath–EECS Math–EECS

Microsoft Blog:http://blog.sina.com.cn/s/blog_4caedc7a0100kxps.html

Google Speach:http://research.microsoft.com/apps/video/default.aspx?id=103787

Students:

John Wright: http://www.jnwright.org/publications.html

Allen Yang: http://www.eecs.berkeley.edu/~yang/

Arvind Ganesh: https://netfiles.uiuc.edu/abalasu2/www/home.html

CSE590 HW4: Automatic Colorization

Baseline Implementation

Algorithm:

1. We choose the best matched face from over 3000 faces trainset. Based on the analysis conclusion, we use gist+SSD image descriptor.

2. We simply average the a&b channels of the best matched face, and copy them into the test face.

Image descriptor:

Slightly, tiny image + SSD is better than gist + SSD image descriptor.

※Some result image are totally black. It is not the algorithm’s bad; it due to the undersize of SSD error.

.        test face        best match train face           result face           best match train face       result face

.                                                         tiny images + SSD                                               gist + SSD

 7365           7365        

 2213           699         

 20023        227         

 2195            1248      

 2144            2311       

 20366         3071      

 5092            13911     

 11453           18320   

9   26679          3980     

10  4194             7546     

.

Enhancement Implementation

1. Average 16 Siblings

The results of ‘best match’ method look like somewhat dull in coloring (e.g. test face No. 7), and present an improper  skin color (e.g. test face No. 34). In order to improve these 2 fault, we implement the ‘Average 16 Siblings’ Algorithm.

7            

1. We extend the ‘similar train face set’ from 1 best matched face to 16 best matched faces, i.e. 16 siblings (16 sibling train faces). Based on the analysis conclusion, we use gist+SSD image descriptor.

2. We simply average the a&b channels of all the siblings, and copy them into the test face.

The results displayed at the bottom of this chapter (16-sibling-based result), and look like much better than all the results of baseline methods.

2. Optimization based Colorization

Just averaging the colors may not work very well when members of the sibling set have widely varying colors. So, that will require a slightly smarter algorithm: ‘Optimizaation based Colorization’, which idea comes from Anat Levin et. ‘Colorization Using Optimization’.

1. Test face preparation: 86×86 gray scale image -> copy to be 86×86×3 gray scales image.

2. Scribbled face preparation: every sibling image.

3. Compute each sibling’s Optimization Colorization Image (Reference: Authors’ code). This step successfully avoid blur edges for the optimization method.

4. We simply average the a&b channels of all the colorized siblings, and copy them into the test face.

3. Hierarchy Sibling + Optimization

The results of ‘Optimization based Colorization’ appeared satisfatory, however, we can improve it even better. How many sibling image should we included in the ‘similar train face set’? ’80 million tiny images’ set 16 siblings for each test face, but it generates deflection of color when the sibling set is oversized. (e.g. test face No.1: Since No.7365 train face is the exact colorization of No.1, ‘Best Match Method’ results in better colorization than ‘Optimization Method’.)

In order to prevent this oversize problem, we raise the ‘Hierarchy Sibling + Optimization’ algorithm. After computing SSD array for each test image, we decide the size of sibling set accroding to the smallest part of SSD array: relative small SSD lead to small size of sibling set.

Set an threshold lies the crux of pinciple, and some experiments might be helpful.

.        test face                 16-sibling-based result    optimization method

1                                    

16 sibling train faces

7365  21024  19027  17623

835     21885  18696  938    

3058  8029   28059  4894

8434  28114   23446  8704

.        test face              16-sibling-based result face   optimaization method

2                                   

16 sibling train faces

699     12134  15182  18037 

6598   585      13677  21622

24471  18757  7006   25359 

15710  1129    27490  2193    

.

Interesting Discuss

1. Skin Color Match. Before implementing above algorithms, we are a little worried about the mismatching of the skin color for people from different area, since the choice of image similarity measure is totally based on shape. It is interesting and wonderful to find the skin color matched very well. (e.g. test face No.22, No. 32, No.65)

22                     

32                   

65                    

2. Stain Robust. The Enhacement Algorithm is robust to stains on the image. (e.g. test face No.56)

56                    

3. Futher work. Although above algorithms implement a somewhat satisfied result and highly automation procession, there are still some places can be improved.

1. The results fail to be in full color, and somewhat loss details. (e.g. test face No.94: face looks pale and  lacking color variation.)

94                    

2. For most of the result, the skin color is converged to the ‘mean skin color’ in the trainset. Some kind of modification of the skin color, such as using another color image from the same people, will do help to this improvement.

.

Reference

1. CSE590 HW4 webpage

2. Paper: 80 million tiny images

3. Paper: Colorization using Optimization

4. Matlab code: RGB2Lab, Lab2RGB

5. Matlab code: Compute gist image descriptor

.

PS..

1. In the 3rd reference, ‘Readme.txt’  has an error:

.                                      example = double(example)/255;

It should be:

.                                      example = double(example/255);

2. I need a ‘quick upload tool’ built in wordpress. It’s a disaster to up load so many pictures one by one!

3. Or, I need a mouse to ‘touch’ other than ‘press’. It do healthy to my wrist.

.

Colerization Result

.          test face            tiny+SSD         gist+SSD                 general average           optimaization method

1                         

2                        

3                        

4                        

5                        

6                        

7                         

8                        

9                        

10                      

11                       

12                      

13                      

14                      

15                      

16                        

17                      

18                      

19                       

20                     

21                         

22                       

23                      

24                     

25                     

26                     

27                      

28                     

29                      

30                      

31                      

32                      

33                     

34                     

35                     

36                     

37                      

38                      

39                     

40                      

41                       

42                      

43                      

44                      

45                      

46                      

47                      

48                        

49                      

50                      

51                      

52                      

53                      

54                      

55                      

56                    

57                      

58                     

59                      

60                      

61                      

62                      

63                      

64                      

65                      

66                      

67                      

68                      

69                      

70                      

71                         

72                       

73                       

74                       

75                       

76                       

77                       

78                       

79                       

80                      

81                      

82                       

83                      

84                      

85                       

86                      

87                      

88                      

89                       

90                      

91                       

92                      

93                      

94                      

95                      

96                      

97                      

98                      

99                      

100                    

CSE 528 Project: Overcoat: An Implicit Canvas for 3D Painting

Programming (Qt Creator)

Project file: D:\Assignment\CS\CG\Project\Code\OverCoat\OverCoat.pro

Headers files

.    mainwindow.h

.        PaintArea *area;

.        QScrollArea *scrollArea;♥

.        bool isSaved;   //if file is saved

.        QString curFile;  //save file path♥

.    paintarea.h

.        Class PaintArea:QWidget    //Implement paint related func

.            QImage image;    //canvas

.            QRgb backColor;    //backcolor♥

.            QPoint lastPoint,endPoint;    //mouse pointer coordinate♥

.            bool modified;   //if image is changed♥

.    donewdialog.h

.        QColor backColor;    //backcolor

.    modelview.h

.        Class ModelView::ModelView() //Import 3D model

.            QGLAbstractScene *m_scene; //Scence

Sources files

.    main.cpp

.    mainwindow.cpp

.       —————————————–new, open, save file——————————————–

.        void doNew();    //new file

.        void doOpen();   //open file

.        bool doFileSave();   //save file

.        bool doFileSaveAs();   //save as file

.        bool maybeSave();   //if save file

.        bool saveFile(QString fileName);   //implement file save

.        void MainWindow::on_action_N_triggered();    //new file menu: initial canvas

.        void MainWindow::on_action_O_triggered()  //open file menu

.        void MainWindow::on_action_S_triggered()  //save file menu

.        void MainWindow::on_action_A_triggered()  //save file as menu

.        void MainWindow::on_action_X_triggered()   //exit menu

.        void closeEvent(QCloseEvent *);    //exit menu: close X button

——————————————–load 3D model——————————————

.        void MainWindow::on_actionImport_3D_Model_triggered(); //import 3D model

.    paintarea.cpp

.        ————————————-setup canvas———————————————

.        PaintArea::PaintArea();    //Construct func: initial canvas size, backcolor

.        void PaintArea::paintEvent(QPaintEvent *);    //redraw

.        ————————————-mouse event———————————————

.        void mousePressEvent(QMouseEvent *);    //mouse press down event: get start coordinate

.        void mouseMoveEvent(QMouseEvent *);   //mouse move event: get current coordinate, paint

.        void mouseReleaseEvent(QMouseEvent *);   //mouse release event: get end coordinate, paint

.        void paint(QImage& theImage);   //paint process: paint from start coordinate to end coordinate

.        ————————————–new file—————————————————-

.        void PaintArea::setImageSize(int width, int height);    //set image size

.        void setImageColor(QColor color);    //set image color

.        ————————————–save file—————————————————–

.        bool isModified() const { return modified; }    //judge if image is changed

.        bool saveImage(const QString &fileName, const char *fileFormat);    //save image

.        bool openImage(const QString &fileName);    //open image

.    donewdialog.cpp

.        int getWidth();    //get canvas width

.        int getHeight();    //get canvas height

.        QColor getBackColor();    //get canvas backcolor

.    modelview.cpp

.        ModelView(QWidget *parent = 0): QGLView(parent); //construct func

.        ~ModelView(); //destruct func

.        void ModelView::initializeGL(QGLPainter *painter); //load scene from source file & store

.        void ModelView::paintGL(QGLPainter *painter); //paint model

Forms files

.   mainwindow.ui: software main window, Photoshop style

.   donewdialog.ui: setup new file

Reference

1. Qt paint software: draw widget, paint line, new file, change canvas, save file, close software, (print, pen style, color panel)

2. Import 3D model into Qt:

.        1) git: git download 20111027.exe->Git Bash, git Wiki, install git tutor (Chi), git user group(A&A)

.        2) Qt/3D installation: Qt/3DQt/3D (Chi), Qt/3D (Eng)

.              a. Obtaining Qt/3D sources

.

. get Home path

.new a direction

.open the direction

.clone Qt/3D from git repository

.

.               b. Obtaining and build Qt sources for Qt/3D!!!

.        3) 3D data import: NeHe, Qt/3D importobj file, 3Ds file, read & redraw.

3. Isosurface (Marching Cube): Vedio1, Vedio2Wiki, Project (Qt + OpenGL code)

.        1) Install Boost C++ Library: Download boostpro_1.47.0 Installer.exe for windows (or compile step by step)

.        2) Add INCLUDEPATH of boost in Qt: Servant of the Lord’s post

.            open “Qt_MARCHING_CUBES.pro” -> right-hand button -> open with -> .pro File Editer

.            INCLUDEPATH += “c:/Programfiles/boost/boost_1_47”

3. Final Vedio: Disney’s Ptex technology, Ptex

4. Qt BOLG: Dou Zi

5. Interesting OpenGL Vedio: Interactive Game

Paper Reading List

1. Painterly rendering for animation

2. NPR (Non-photorealistic rendering)

2011.11.12

1. opengl install

2.