Project Proposal

The goal of this project is to accelerate an classic algorithm in GPU. The analysis model and sampling method will be unchanged, the only changed place is in the core function in the algorithm which is called FindBestMatch.

Anticipated Approach

Implement the Wei-Levoy’s L-shape neighbor matching algorithm[WM00]. This algorithm can be divided into 3 phases: Phase1: initialize the output texture with noise. Phase2: For each unsynthesized pixel in the output texture, make a L-shape neighbor for it, compare this neigh-bor with every neighbor of the pixels in the input texture. Phase3: Pick the best matched pixel in the input texture to the output texture.

We can accelerate it in phase1 and phase2: phase1: we can use a quick noise function in GPU, in-stead of using the CPU initialize method. Although this approach won’t affect the synthesis speed that much. phase2: we can set up a K-D tree of all input pixels’ neighbors in GPU.[ZHWG08], and compared the L-shape neighbors parallel.

Complete both the algorithm and its GPU acceleration method, compare the results.

Target Platforms

Operating System: Microsoft Windows;
Hardware requirement: NVIDIA Graphics card with CUDA supported.

Evaluation Criteria

Suppose I have implemented my approach, and its fully functioning. I will set up a table to compare the synthesis speed of the original CPU implementation and GPU acce-leration which is simple and nature. The synthesis results of the two methods are supposed to be the same, but if there are anything different, I will point out to show the different output texture here and try to explain.

Reference

[WM00] WEI, L.-Y., AND LEVOY, M. 2000. Fast texture synthesis using tree-structured vector quantization. Proceedings of SIGGRAPH 2000 (July), 479–488. ISBN 1-58113-208-5.

[ZHWG08] Kun Zhou , Qiming Hou , Rui Wang , Baining Guo, Real-time KD-tree construc-tion on graphics hardware, ACM SIGGRAPH Asia 2008 papers, December 10-13, 2008, Singapore