This dissertation is concerned with domain decomposition methods for convex optimization in image processing. In particular, we focus on total variation minimization which is one of the standard techniques in image processing. Domain decomposition methods are suitable for parallel computation since they solve a large-scale problem by dividing it into smaller problems and treating them in parallel. Since total variation is nonlinear, nonsmooth, and nonseparable, it is quite challenging to design an efficient domain decomposition method for total variation minimization.
In this dissertation, two fast iterative substructuring methods for total variation minimization are proposed. We show that the proposed iterative substructuring methods outperform the existing methods both theoretically and numerically. In addition, we present a convergence rate analysis for a nonoverlapping Schwarz method for total variation minimization, and propose its accelerated variant which has superior convergence properties. We present another novel domain decomposition method which can be applied to not only total variation minimization but also more general optimization problems in image processing such as higher models and nonconvex models. Numerical results for all of the proposed domain decomposition methods applied to various problems of image processing such as image denoising, inpainting, deconvolution, and segmentation are provided.
영역분할법은 문제의 정의역을 여러 개의 부영역으로 나누어 각각의 부영역에서 정의된 소문제를 병렬로 해결하는 기법으로, 멀티코어 컴퓨터 자원을 효율적으로 활용하여 빠른 계산을 할 수 있도록 한다. 본 학위논문은 영상 처리에서 사용되는 볼록 최적화 문제에 대한 영역분할법을 다룬다. 영상 처리의 표준 문제인 총변이 최소화 문제의 경우, 부영역 경계에서 해의 불연속을 허용하고, 각 부영역에서의 총변이의 합이 전 영역에서의 총변이와 같지 않다. 그러므로 기존의 타원형 미분방정식에 대하여 개발된 영역분할법을 적용할 수가 없어, 새로운 접근법을 필요로 한다.
본 학위논문에서는 총변이 최소화 문제에 대한 새로운 경계 기반의 영역분할법을 제시하고, 제시한 방법이 기존의 방법보다 이론적, 수치적으로 월등함을 증명한다. 또한 기존의 총변이 최소화 문제에 대한 겹치지 않는 슈바르츠 방법의 수렴 속도를 보이고, 더 빠른 수렴 속도를 갖는 새로운 슈바르츠 방법을 제시한다. 총변이 최소화 문제뿐만 아니라 고차 문제, 볼록하지 않은 문제 등의 더 일반적인 볼록 최적화 문제에 적용할 수 있는 새로운 영역분할법을 소개한다. 본 학위 논문에서 제시한 모든 영역분할법의 영상 잡티 제거, 인페인팅, 디콘볼루션, 분할 등의 다양한 영상 처리 문제에 대한 수치 실험 결과를 제공한다.
