## Multigrid methods enchancement.

Descussing the last adnvances in image processing and computer vision
Creator
Posts: 157
Joined: Tue Dec 16, 2008, 20:52
Location: Hannover, Germany
Contact:

### Multigrid methods enchancement.

We continue our research on fast boundary problems solver. As was described in the article "Accurate Real-Time Disparity Estimation with Variational Method", the multigrids methods are very efficient in that contest. In the same article we have offered a new kind of multigrid cycles - O-cycle, or null-cycle, which was more effective as v- and w-cycles, when solving the Euler-Lagrange equations. Here we applied the same approach to the Poisson problem and compared the efficiency of classical multigrid cycles with the o-cycle.
The test problem was described at this forum in Poisson Equation thread. In two words, we solve 2D Poisson equation L[u(x,y)] = -f(x,y). We use Dirichlet boundary conditions, i.e. u(x,y) = 128 on boundaries. As for function f we initialize it as a positive and a negative knots: f(width/4, height/2) = -128 and f(3*width/4, height/2) = 128. We have an analytical true solution to this problem and can calculate the accuracy of the solution, achieved by our method in meaning of bad pixels percentage. Here we designate a pixel as a bad one if it' grey value differs from the exact solution value more then by 4.
We compare the performance of different cycles in milliseconds. We use the fastest configuration for each cycle to achieve the accuracy less than 1%. The Smart Iterations Distribution (SID) is the method of adopting the number of iterations parameter depending on the multigrid level, described in the article, mentioned above.
Image domain size = 640 x 400. CPU: Intel Q9550 @ 2,83GHzs.
Attachments Last edited by Creator on Thu Oct 15, 2009, 16:19, edited 1 time in total.

Creator
Posts: 157
Joined: Tue Dec 16, 2008, 20:52
Location: Hannover, Germany
Contact:

### Re: Multigrid methods enchancement.

- As we can see, the SID enchants the performance from 10% up to 70% depending on cycle used.
- Using o-cycles gives a very good performance but yields to v-cycle performance.
- O-cycles with SID were used in the article "Accurate Real-Time Disparity Estimation with Variational Method".
Let's continue with non-linear approach!

Creator
Posts: 157
Joined: Tue Dec 16, 2008, 20:52
Location: Hannover, Germany
Contact:

### The cascadic multigrid method for elliptic problems

It looks like cascadic multigrid is very common to O-cycles.
Attachments cascadic multigrid.pdf
The cascadic multigrid method for elliptic problems

Creator
Posts: 157
Joined: Tue Dec 16, 2008, 20:52
Location: Hannover, Germany
Contact:

### Re: Multigrid methods enchancement.

For the non-linear case we took another problem, but still based on Poisson equation: L[u(x,y)] = u(x,y) - f(x,y), where L no is a non-linear operator. Again, we compare the performance of different cycles in milliseconds, using the fastest configuration for each cycle to achieve the accuracy less than 10%.
Attachments 