# Picture Completion utilizing Global Optimization

0
0
2658 days ago, 775 views
PowerPoint PPT Presentation

### Presentation Transcript

Slide 1

﻿Picture Completion utilizing Global Optimization Presented by Tingfan Wu

Slide 2

The Image Inpainting Problem

Slide 3

Outline Introduction History of Inpainting Camps – Greedy & Global Opt. Model and Algorithm Markov Random Fields (MRF) & Inpainting Belief Propagation (BP) Priority BP Results Structural Propagation

Slide 4

Method Type Priority Texture Synth. Require User Guidance

Slide 5

Exampled Based Method — Jigsaw Puzzle Patches Not Available

Slide 6

Method Type Priority Texture Synth. Require User Guidance

Slide 7

Ooops Greedy v.s Global Optmization Greedy Method Global Optimization Refine Globally  Cannot do a reversal 

Slide 8

Outline Introduction History of Inpainting Camps – Greedy & Global Opt. Model and Algorithm Markov Random Fields (MRF) & Inpainting Belief Propagation (BP) Priority BP Results Structural Propagation

Slide 9

Random Fields/Belief Network Random Variable (Observation) RF ： Random Variables on Graph Node : Random Var. (Concealed State) Belief : from Neighbors, and Observation Good Project Writer? (High Project review) Smart Student? (High GPA) Good Test Taker? (High test score) Good Employee (No Observation yet) Edge: Dependency

Slide 10

Story about MRF (Bayesian) Belief Network (DAG) Markov Random Fields (Undirected, Loopy) Special Case: 1D - Hidden Markov Model (HMM) Hidden Markov Model (HMM) Office Helper Wizard

Slide 11

Inpainting as MRF enhancement Node : Grid on target locale, covered patches Edge : A hub depends just on its neighbors Optimal naming (shrouded express) that minimizing confuse vitality

Slide 12

MRF Potential Functions Mismatch (Energy) between .. V p (X p ) : Source Image versus New Label V pq (X p , X q ) : Adjacent Labels S um of S quare D istances (SSD) in Overlapping Region

Slide 13

Global Optimizatoin min

Slide 14

Outline Introduction History of Inpainting Camps – Greedy & Global Opt. Model and Algorithm Markov Random Fields (MRF) & Inpainting Belief Propagation (BP) Priority BP Results Structural Propagation

Slide 15

Belief Propagation(1/3) Good Project Writer? (High Project review) Smart Student? (High GPA) Good Test Taker? (High test score) Good Employee (No Observation yet) Undirected and Loopy Propagate forward and in reverse

Slide 16

X q p Belief Propagation(2/3) Message Forwarding Iterative calculation until join O(|Candidate| 2 ) Candidates at Node Q Candidates at Node P Neighbors (P)

Slide 17

Belief Propagation(3/3)

Slide 18

Priority BP too moderate: Huge #candidates ��  Time msg = O(|Candidates| 2 ) Huge #Pairs �� Cannot store pairwise SSDs. Perceptions Non-Informative messages in unfilled locales Solution to a few hubs is self-evident (less hopefuls.)

Slide 19

Human Wisdom Candidates Start from non-vague part And Search for Brown quill + green grass Nobody begin from here

Slide 20

Priority BP Observations unnecessary messages in unfilled areas Solution to a few hubs is self-evident (less competitors.) Solution: Enhanced BP: Easy hubs goes first (need message booking) Keep just exceptionally conceivable applicants (keep up an Active Set)

Slide 21

? ? ? ? ? ? ? ? Need & Pruning Discard Blue Points High Priority prune a considerable measure Low Priority Candidates sorted by relative conviction Pruning may miss adjust mark

Slide 22

#Candidates in the wake of Pruning Active Set (Darker means littler) Histogram of #candidates Similar applicants

Slide 23

A more critical take a gander at Priority BP Priority Calculation Priority : 1/(#significant competitor) Pruning (on the fly ) Discard Low Confidence Candidates Similar patches ��  One agent (by grouping) Result More Confident �� More Pruning Confident hub builds neighbor " s certainty. Cautioning: PBP and Pruning must be utilized together

Slide 24

Outline Introduction History of Inpainting Camps – Greedy & Global Opt. Model and Algorithm Markov Random Fields (MRF) & Inpainting Belief Propagation (BP) Priority BP Results Conclusion Structural Propagation

Slide 25

Results-Inpainting(1/3) Darker pixels ��  higher need Automatically begin from striking parts.

Slide 26

Results-Inpainting(2/3)

Slide 27

Results-Inpainting(3/3) Up to 2minutes/picture (256x170) on P4-2.4G

Slide 28

More : Texture Synthesis Interpolation and additionally extrapolation

Slide 30

Conclusion Priority BP {Confident hub first} + {candidate pruning} Generic – relevant to other MRF issues. Accelerate MRF for Inpainting Global advancement maintain a strategic distance from outwardly inconsistence by eager Priority BP for Inpainting Automatically begin from notable point.

Slide 31

Sometimes … Image contains hard abnormal state structure Hard for PCs Interactive fruition guided by human.

Slide 32

Potential Func. For Structural Propagation User input a rule by human area. Potential Function regard remove between lines Jian Sun et al, SIGGRAPH 2005

Slide 33