Publications
Detailed Information
Stochastic Graduated Graph Approximation Algorithm for MRF optimization : 확률론적 순차적 그래프 근사를 이용한 MRF 최적화
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor | 이경무 | - |
dc.contributor.author | 세르게이 | - |
dc.date.accessioned | 2017-07-14T03:00:28Z | - |
dc.date.available | 2017-07-14T03:00:28Z | - |
dc.date.issued | 2015-02 | - |
dc.identifier.other | 000000026116 | - |
dc.identifier.uri | https://hdl.handle.net/10371/123161 | - |
dc.description | 학위논문 (석사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2015. 2. 이경무. | - |
dc.description.abstract | Markov random elds have been powerful models in computer vision but tractable
algorithms to obtain exact solution for the corresponding energy functions are lim- ited | - |
dc.description.abstract | approximate solutions, in most cases are provided for efficiency. In this work
graduated optimization technique is applied in a novel way to develop an efficient al- gorithm for solving general multi-label MRF optimization problem called Stochastic Graduated graph approximation (SGGA) algorithm. The algorithm initially min- imizes a simplied function and progressively transforms that function until it is equivalent to the original function. However, it is hard to nd how to generate the sequence of intermediate functions and what parameter to use for making transition from one problem to another. For this we propose a new iterative method of build- ing the sequence of approximations for the original energy function. We exploit a stochastic method to generate intermediate functions, which guides the intermedi- ate solutions to the near-optimal solution for the original problem. The transition from one intermediate problem to another is controlled by the schedule of gradual addition of edges. In each iteration, a deterministic algorithm such as block ICM is applied to minimize intermediate functions and to generate initial solution for the next problem. The proposed algorithm guarantees the convergence of local mini- mum. We test on a synthetic image deconvolution problem and also on the set of experiments with the OpenGM2 benchmark. | - |
dc.description.tableofcontents | Abstract i
Contents iii List of Figures iv List of Tables viii 1 Introduction 2 1.1 Background of research . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Outline of thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Related works 8 2.1 Graduated optimization . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Sequential Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . 11 3 Stochastic graduated graph approximation 13 3.1 Graph approximation by scanlines . . . . . . . . . . . . . . . . . . . 13 3.2 Graph approximation by trees . . . . . . . . . . . . . . . . . . . . . . 18 4 Minimization of intermediate energy functions 20 4.1 Block Iterated conditional modes . . . . . . . . . . . . . . . . . . . . 20 4.1.1 Block Iterated conditional modes: general idea . . . . . . . . 20 4.1.2 Block ICM for graduated graph approximation . . . . . . . . 21 4.2 Dynamic programming . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.1 Dynamic programming: general idea . . . . . . . . . . . . . . 23 4.2.2 The DP algorithm on scanlines for graduated graph approxi- mation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2.3 The DP algorithm on trees . . . . . . . . . . . . . . . . . . . 27 5 Experiments 29 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Image deconvolution . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.3 OpenGM2 benchmark . . . . . . . . . . . . . . . . . . . . . . . . . . 43 6 Conclusion 51 Bibliography 52 59 60 | - |
dc.format | application/pdf | - |
dc.format.extent | 3571108 bytes | - |
dc.format.medium | application/pdf | - |
dc.language.iso | en | - |
dc.publisher | 서울대학교 대학원 | - |
dc.subject | MRF | - |
dc.subject | discrete optimization | - |
dc.subject | graph approximation. | - |
dc.subject.ddc | 621 | - |
dc.title | Stochastic Graduated Graph Approximation Algorithm for MRF optimization | - |
dc.title.alternative | 확률론적 순차적 그래프 근사를 이용한 MRF 최적화 | - |
dc.type | Thesis | - |
dc.contributor.AlternativeAuthor | Sergei Liubich | - |
dc.description.degree | Master | - |
dc.citation.pages | viii, 60 | - |
dc.contributor.affiliation | 공과대학 전기·컴퓨터공학부 | - |
dc.date.awarded | 2015-02 | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.