Multigrid methods enchancement.

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

Multigrid methods enchancement.

Postby Creator » Wed Oct 14, 2009, 17:07

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
FMG perfomance.jpg
Last edited by Creator on Thu Oct 15, 2009, 16:19, edited 1 time in total.

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

Re: Multigrid methods enchancement.

Postby Creator » Thu Oct 15, 2009, 16:13

    - 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!

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

The cascadic multigrid method for elliptic problems

Postby Creator » Mon Oct 26, 2009, 16:36

It looks like cascadic multigrid is very common to O-cycles.
Attachments
cascadic multigrid.pdf
The cascadic multigrid method for elliptic problems
(213.7 KiB) Downloaded 429 times

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

Re: Multigrid methods enchancement.

Postby Creator » Tue Oct 27, 2009, 19:07

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
FMG NL.jpg


Return to “Image processing”

Who is online

Users browsing this forum: No registered users and 1 guest