Transcript PPT

Image Processing in
SIGGRAPH 06
Speaker: Qianqian Hu
Date: March 31, 2006
Outlines




Fast Median and Bilateral Filtering

Ben Weiss (Shell & Slate Software)
Hybrid Images

Aude Oliva (Massachusetts Institute of Technology, Department of
Brain and Cognitive Sciences), Antonio Torralba (Massachusetts
Institute of Technology, Computer Science and Artificial Intelligence
Laboratory), Philippe G. Schyns (University of Glasgow)
Image Deformation Using Moving Least Squares

Scott Schaefer (Texas A&M University), Travis McPhail, Joe Warren
(Rice University)
Appearance-Space Texture Synthesis

Sylvain Lefebvre, Hugues Hoppe (Microsoft Research)
Image Deformation using
Moving Least Squares
Scott Schaefer
Travis McPhail
Texas A&M University Rice University
Joe Warren
Rice Univeristy
Example

Previous Work

Grid-based techniques:



Transformation-based technique:


Bivariate cubic splines[Sederberg and Parry, 1986, Lee et al,
1995]
Shepard’s interpolant[Beier and Neely, 1992]
Radial Basis Function[Bookstein, 1989]
Triangulation-based technique[Igarashi et al, 2005]
Overview of SIG’05
Characters of the
Deformation Function

Given a set of handles p, and corresponding
new positions q. The deformation function f
satisfies



Interpolation: f(pi)=qi
Smoothness: smooth deformations
Identity: q=p  f(v) = v
Moving Least Squares

Given a point v in the image, the best
affine transformation lv(x) minimizes
where
DF: f(v)= lv(v)
Affine Transformation
lv(x)=xM +T,


M :a linear transformation matrix (rotation and
scaling)
T :a translation
Best affine transformation
where
Least Squares Problem
where
Affine Deformations

Solution for matrix M

Solution for deformation function
Result
Non-uniform scaling and shear
Similarity Deformations



Constraints: uniform scaling, i.e,
Define
, where
Least squares problem
where
Similarity Deformations

Solution for matrix M

Solution for deformation function
where
Result
uniform scaling
Rigid Deformations


Constraint: no uniform scaling, i.e.,
Theoretical base
Rigid Deformations

Solution for matrix M

Solution for deformation function
where
, and Ai is as in similarity deformations.
Example

Examples for Rigid MLS
Examples for Rigid MLS
Deformation with Line
Segments

Least squares problem
Affine Lines


Line segments
in matrix form
Least squares problem
are expressed
Solution

The deformation function
and
Similarity Lines

The deformation function
Rigid Lines

The deformation function
where
Examples for Rigid Lines
Implementation


Every pixel is replaced by a grid
Every resulting pixel is calculated using bilinear
interpolation
Contributions

A simple closed-form solution




Handles:



a linear system (2X2) at each point
No use of linear solver
Simple, and realtime
points,
line segments.
As-rigid-as possible
Shortcoming

Lack of topological information
Future Work



Adding topological information
Generalizing to 3D to deform surfaces
Handles can be any curves
Fast Median and Bilateral
Filtering
Ben Weiss
Shell & Slate Software Corp.
Example
Contributions

Improving Runtime from O(r) to O(logr)



Scalable to arbitrary radius
Realtime
Fitting for any bit-depth
Related Work

A variety of O(r) algorithms
Huang, T.S., 1981. Two-Dimensional Signal Processing II: Transforms and
Median Filters.
No good performance for large filtering kernels.

A tree-based O(log2r) algorithm
Gil, J. and Werman, M., 1993. Computing 2-D Min, Median, and Max Filters.
Ill-suited for deep-pipelined, vector-capable modern processors.

A parallel algorithm with time
complexity of O(log4r)
Ranka, S., and Sahni, S., 1989. Efficient Serial and Parallel Algorithms
for Median Filtering.
even worser than linear for r<55.
Median Filtering

A pixel value is replaced by the median
of its neighbours. [Tukey, 1977]
Advantages



Reducing image noise
Preserving edges
Basic algorithm of many imageprocessing techniques


Rank-order filtering
Morphological processing
slowness!!!
Basic O(r) Algorithm

Consider a r-radius median filter to an
8-bit image.
Histogram and Mean Value


Use a 256-element histogram
Mean value = the index v* such that

v*
v0
H (v)dv  2r 2  2r  1
Integral =2r2+2r+1
Huang’s O(r) Algorithm
Fundamental idea

If multiple columns are processed at
once, the aforementioned redundant
calculations become sequential.
Distributive Histograms

For disjoint image regions A and B:
Adapted Huang’s
Algorithm
Three Tiers and Beyond
O(logr) Algorithm
Higher-Depth Median
Filtering


16-bit and HDR(High dynamic range) images
Histogram exponentially with bit-depth
The Ordinal Transform
cardinal values
consecutive ordinal values
Comparison(1)
Comparison(2)

For 8-bit data


50 times faster than Photoshop
For 16-bit data

20 times as fast as Photoshop
MedianDemo
Bilateral Filtering

A normalized convolution[Tomasi, 1998]


Spatial distance
Relative difference in intensity
Linear-Intensity Bilateral

A box spatial and triangular intensity
filter
Logarithmic-Intensity
Bilateral

Durand, F. and Dorsey, J. 2002. Fast Bilateral Filtering
for the Display of High Dynamic Range Images.
SIG’02
Example
Comparison
BilateralDemo