Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 341Image Completion Image Completion using Global using Global OptimizationOptimizationPresented by Tingfan WuPresented by Tingfan Wu2 The Image Inpainting PrThe Image Inpainting Problemoblem3 OutlineOutlineIntroductionIntroductionHistory of InpaintingHistory of InpaintingCamps – Greedy & Global Opt.Camps – Greedy & Global Opt.Model and AlgorithmModel and AlgorithmMarkov Random Fields (MRF) & InpaintingMarkov Random Fields (MRF) & InpaintingBelief Propagation (BP)Belief Propagation (BP)Priority BPPriority BPResultsResultsStructural PropagationStructural Propagation4 Method TypeMethod TypeInpaintingBertalmio et al. SIGGRAPH 2000StatisticalExample BasedTexture Synth./PatchGreedyCriminisi et al. 2003Global OptimizationPriority BP[This paper]Structural Propagation[Sun et. al, SIGGRAPH 05]PDEBertalmio et al. 2001PriorityTexture Synth.Need User Guidance5 Exampled Based MethodExampled Based Method—Jigsaw Puzzle—Jigsaw PuzzlePatchesNot Available6 Method TypeMethod TypeInpaintingBertalmio et al. SIGGRAPH 2000StatisticalExample BasedTexture Synth./PatchGreedyCriminisi et al. 2003Global OptimizationPriority BP[This paper]Structural Propagation[Sun et. al, SIGGRAPH 05]PDEBertalmio et al. 2001PriorityTexture Synth.Need User Guidance7 Greedy v.s Global OptmizGreedy v.s Global OptmizationationGreedy Method Cannot go back Global OptimizationOoopsRefine Globally 8 OutlineOutlineIntroductionIntroductionHistory of InpaintingHistory of InpaintingCamps – Greedy & Global Opt.Camps – Greedy & Global Opt.Model and AlgorithmModel and AlgorithmMarkov Random Fields (MRF) & InpaintingMarkov Random Fields (MRF) & InpaintingBelief Propagation (BP)Belief Propagation (BP)Priority BPPriority BPResultsResultsStructural PropagationStructural Propagation9 Random Fields / Belief Random Fields / Belief NetworkNetworkGood Project Writer?(High Project grade)Good Test Taker?(High test score)Smart Student?(High GPA)Good Employee(No Observation yet)Edge: DependencyRFRF：：Random Variables on GraphRandom Variables on GraphNode : Random Var. (Hidden State) Node : Random Var. (Hidden State) Belief : from Neighbors, and Observation Belief : from Neighbors, and Observation Random Variable(Observation)10 Story about MRFStory about MRF(Bayesian) Belief Network (DAG)(Bayesian) Belief Network (DAG)Markov Random Fields (Undirected, Markov Random Fields (Undirected, Loopy) Loopy) Special Case:Special Case:1D - Hidden Markov Model (HMM)1D - Hidden Markov Model (HMM)Office Helper WizardHidden Markov Model (HMM)Hidden Markov Model (HMM)11 Inpainting as MRF optimInpainting as MRF optimizationizationNode : Grid on target region, overlapped patchesNode : Grid on target region, overlapped patchesEdge : A Edge : A nodenode depends only on its depends only on its neighborsneighborsOptimal labeling (hidden state) that minimizing Optimal labeling (hidden state) that minimizing mismatch energymismatch energy12 MRF Potential FunctionsMRF Potential FunctionsMismatch (Energy) between ..Mismatch (Energy) between ..VVp p (X(Xp p ) : Source Image vs. New Label) : Source Image vs. New LabelVVpqpq(X(Xpp, X, Xqq) : Adjacent Labels) : Adjacent LabelsSSum of um of SSquare quare DDistances (SSD) in Overlapping Reistances (SSD) in Overlapping Regiongion13 Global OptimizatoinGlobal Optimizatoinmin14 OutlineOutlineIntroductionIntroductionHistory of InpaintingHistory of InpaintingCamps – Greedy & Global Opt.Camps – Greedy & Global Opt.Model and AlgorithmModel and AlgorithmMarkov Random Fields (MRF) & InpaintingMarkov Random Fields (MRF) & InpaintingBelief Propagation (BP)Belief Propagation (BP)Priority BPPriority BPResultsResultsStructural PropagationStructural Propagation15 Belief Propagation(1/3)Belief Propagation(1/3)•Undirected and Loopy•Propagate forward and backwardGood Project Writer?(High Project grade)Good Test Taker?(High test score)Smart Student?(High GPA)Good Employee(No Observation yet)16 Belief Propagation(2/3)Belief Propagation(2/3)Message ForwardingMessage ForwardingIterative algorithm until convergeIterative algorithm until convergeXqXpCandidates at Node QCandidates at Node PNeighbors (P)O(|Candidate|2)17 Belief Propagation(3/3)Belief Propagation(3/3)18 Priority BPPriority BPBP too slow: BP too slow: Huge #candidates Huge #candidates  Time Timemsgmsg = O(|Candidat = O(|Candidates|es|22) ) Huge #Pairs Huge #Pairs Cannot cache pairwise SSDs.Cannot cache pairwise SSDs.ObservationsObservationsNon-Informative messages in unfilled regionNon-Informative messages in unfilled regions s Solution to some nodes is obvious (fewer canSolution to some nodes is obvious (fewer candidates.)didates.)19 Human WisdomHuman WisdomNobody start from hereStart from non-ambiguous partAndSearch forBrown feather+green grassCandidates20 Priority BPPriority BPObservationsObservationsneedless messages in unfilled regions needless messages in unfilled regions Solution to some nodes is obvious (fewer Solution to some nodes is obvious (fewer candidates.)candidates.)Solution: Enhanced BP:Solution: Enhanced BP:Easy nodes goes first (priority message Easy nodes goes first (priority message scheduling)scheduling)Keep only highly possible candidates Keep only highly possible candidates (maintain a Active Set)(maintain a Active Set)21 Priority & PruningPriority & Pruning????????High Priorityprune a lotPruning may miss correct labelLow PriorityCandidates sorted by relative beliefDiscard Blue Points22 #Candidates after #Candidates after PruningPruningActive Set (Darker means smaller)Histogram of #candidates Similar candidates23 A closer look at Priority A closer look at Priority BPBPPriority CalculationPriority CalculationPriority : 1/(#significant candidate)Priority : 1/(#significant candidate)Pruning (on the fly )Pruning (on the fly )Discard Low Confidence CandidatesDiscard Low Confidence CandidatesSimilar patches Similar patches  One representative (by One representative (by clustering)clustering)ResultResultMore Confident More Confident More Pruning More Pruning Confident node