CSCE 221 Culture Assignment 1

« previous | Friday, April 8, 2011 | next »

Habib Talavatifard: Parallel L1-minimization for Surface reconstruction and image enhancement

Building 3D models from a single image and making images clearer (i.e. less pixelated) and more colorful

Problem

Extract a surface $u$ from a set of measurements in a set

• points or averages

Given a bunch of data, create a smooth surface

Solution

Approximate the minimum of norm for $u$'s second derivative.

$L_{p}$ has something to do with $L^{1}$, which has something to do with the mean

$L^{1}$ gives better results

Functions can be used to eliminate noise ("jump" is 0), which makes the problem easier to solve.

• Interior Point (IP; preferred)
• Augmented Lagrangian Method (AL)

Both perform similarly and have their own pros and cons:

• IP is good for more complex parts
• AL converges faster, but takes a while to reach exact value (good for stuff that's easy to calculate)

Answer: Use a combination of both!

Enough 3D, lets go 2D: Upscaling an image

• Bi-cubic splines in GIMP is not as good as this guy's algorithm
• Edge reconstruction, detail enhancement

Can these be performed in parallel?

• Matrix-vector multiplication and dot products
• Domain decomposition (modular and scalable)

We hypothesize that solving in parallel will give same results as sequential solution

• Break image/data into two parts ("domains"), allowing them to overlap just a little (relating the two domains to each other)
• Solve each domain on a separate processor
• Solve over one domain while keeping the other constant; then do the same with the other, and then average the two
• Sometimes jumps will occur between two boundaries, so more overlap will help to smooth transitions

This hypothesis is true! Parallelization speeds up the process "superlinearly" (better than linear)

On 2D images, parallelization requires 3+ iterations over the same data

How could this be implemented on GPUs?