샹볼레-폭 알고리즘
Chambolle-Pock algorithm수학에서, 챔볼-폭 알고리즘은 볼록 최적화 문제를 해결하기 위해 사용되는 알고리즘입니다.2011년 안토닌 챔볼레와 토마스[1] 팍에 의해 도입되었으며, 이후 이미지 처리,[2][3][4] 컴퓨터 비전,[5] 신호 [6]처리 등 다양한 분야에서 널리 사용되는 방법이 되었습니다.
Chambolle-Pock 알고리듬은 데이터 충실도 항과 정규화 [1]항으로 구성된 매끄럽지 않은 비용 함수의 최소화와 관련된 볼록 최적화 문제를 효율적으로 해결하기 위해 특별히 설계되었습니다.이는 이미지 재구성,[2] 노이즈[3] 제거 및 [4]인페인팅과 같은 잘못된 이미지 역문제에서 일반적으로 발생하는 일반적인 구성입니다.
이 알고리즘은 기본 변수와 이중 변수를 동시에 업데이트할 수 있는 기본-이중 공식을 기반으로 합니다.Chambolle-Pock 알고리듬은 근위 연산자를 사용하여 이미징 [1]프레임워크에 특정한 총 변동과 같은 매끄럽지 않고 볼록하지 않은 정규화 용어를 효율적으로 처리합니다.
문제명세서
XX{X {Y로 . 내부 곱 과 노름 \= \^부터 {까지함수 는 그 연산자 프록스{\ F가 닫힌 형태의 표현을 가지거나 정확하게 계산될 수 있는 경우 단순하다고 합니다 여기서 프록스 FF[1]는 프록스 F{\text{tauF라고 합니다.
다음과 같은 제한된 기본 [1]문제를 생각해 보십시오.
서K : K:{\mathcal는 유계 선형 이며 : Y [ + : [ + + fty: {\infty}, 단순하고 반수직렬이 단순하며[1] 반수직렬합니다.
최소화 문제는 다음과 같은 이중 대응 문제를[1] 가지고 있습니다.
서F F 및∗({{\displaystyle K^{*}})는 [1]F, F, 및의 맵입니다.
기본 문제와 이중 문제가 적어도 해 ) × { {{\times {\를 갖는다고 가정하면, 이는 다음을 만족한다는[7] 것을 의미합니다.
여기서 ({\ F와∂ ({\G})는 [7]각각 볼록 F F와의 하위 경사입니다.
Chambolle-Pock 알고리즘은 소위 안장점[1] 문제를 해결합니다.
이는 [1]앞에서 언급한 비선형 기본 문제와 이중 문제의 기본-기본 공식입니다.
알고리즘.
챔볼레-폭 알고리듬은 기본 문제와 이중 [2]문제를 동시에 해결하기 위해 주로 그레이디언트와 접근 방식을 사용하여 기본 의 상승과 기본 변수의 하강을 반복적으로 번갈아 수행합니다.또한 매개 변수 \를[1]가진 기본 변수에 대해 과도한 이완 기술이 사용됩니다.
Chambolle-Pock 알고리즘 입력: F , > [, (0 ) × \ display > 0\,\times { x에서 정지 기준을 설정합니다.
을 하는 동안 정지 기준 만족하지 않는 끝이 나다
- 할당을 나타냅니다.예를 들어 "가장 큰 ← 항목"은 가장 큰 값이 항목의 값에 변경되는 것을 의미합니다.
- "return"은 알고리즘을 종료하고 다음 값을 출력합니다.
알고리즘의 수렴을 보장하기 위해서는 L\displaystyle \display\leq과 같은단계 크기 매개변수를 선택하는 것이 좋습니다. 서 L { L \ K 이 간단한 선택은 [1]알고리즘의 수렴을 보장합니다.더욱이, 이러한 가설을 제안된 알고리듬이 1 {\ =}에 대해 O ( N) {\를 기본-벡터 [1]간격에 대한 수렴 속도로 가지며, 네스토프는 알려진 구조화된 볼록 최적화 [8]문제의 클래스에 최적임을 보여주었습니다.
반자동 Arrow-Hurwicz[9] 방법은 Chambolle-Pock [1]알고리듬에서 \ = 의 특정 선택과 일치합니다.
가속
수렴 속도가 이론적으로 [1]빨라지는 특별한 경우가 있습니다.사실, GG가 F F가 균일하게 볼록하다면 G는 Lipschitz 연속 기울기를 가집니다.그런 다음 수렴 속도를 O/ 2으)로 개선하여 Chambolle-Pock 알고리즘에 약간의 변화를 제공할 수 있습니다.이는 방법의 가속 버전으로 이어지며, 이러한 [1]값을 고정하는 대신 반복적으로 \n 및를 선택하는 것으로 구성됩니다.
가 균일 볼록이고, > >의 균일 볼록 상수를 갖는 경우, 수정된 알고리즘은[1]
알고리즘 가속 챔볼레-폭 알고리즘 입력: F 0, > \ _{_{ >0 1 (y ) X ×Y {\_{ _ \y을(를) 설정하고 x 0 {\}= 중지 기준을 합니다.
을 하는 동안 정지 기준 만족하지 않는 끝이 나다
- 할당을 나타냅니다.예를 들어 "가장 큰 ← 항목"은 가장 큰 값이 항목의 값에 변경되는 것을 의미합니다.
- "return"은 알고리즘을 종료하고 다음 값을 출력합니다.
또한 의 표준인이 쉽게 추정되지 않거나 매우 클 수 때 알고리즘의 수렴이 느려집니다.적절한 전제 및 \를선택하고 및 \를통해 유도된 규범의 도입으로 근위 연산자를 수정하면 제안된 전제 조건 알고리듬의 수렴이 [10]보장됩니다.
어플
이 알고리즘의 일반적인 적용은 총 변동에 [3]기반한 이미지 노이즈 제거 프레임워크에 있습니다.과도하고 잠재적으로 잘못된 세부 정보를 포함하는 신호는 이미지의 [3]절대 값 기울기의 적분을 나타내는 높은 총 변동을 나타낸다는 개념으로 작동합니다.이 원리를 준수함으로써 프로세스는 원래 신호와 유사성을 유지하면서 신호의 총 변동을 줄이는 것을 목표로 하며 에지와 같은 중요한 특징을 유지하면서 원하지 않는 세부 사항을 효과적으로 제거합니다.고전적인 2차원 이산 [11]설정에서 X M {\{\}=\을 합니다. 여기서 {\u\{\는 데카르트 N ×에[1]결합된 픽셀 값을 가진 이미지를 나타냅니다.
X의 곱을 다음과 같이 정의합니다X[1]}}
이는 [1]로 표시된 X에 대해 2 을 유도합니다.
따라서, 의 기울기는 표준 유한 차이로 계산됩니다.
이는 Y × ({{mathcal {Y}}={ { {의[1] 요소이며, 여기서
그리고 루딘, 오셔, 파테미가 [12]제안한 ROF 모델의 기본 문제는 다음과[1] 같습니다.
서 Xin{{X}}는 알 수 없는 이고 g X {X는 주어진 노이즈가 많은 데이터입니다. 대신 ∈ \는 정규화와 데이터 [1]피팅 간의 균형을 설명합니다.
ROF 문제의 일차-이중 공식은 다음과 같이[1] 공식화됩니다.
여기서 지시자 기능은 다음과 같이 정의됩니다[1].
볼록 P {Y : ( ) + ( 2 ) ≤ \ Pleft{\ {Ysqrtright)}}^left(p_left(\left)\)^{q1이는에 된 노름에 대해 L L^{\ 유니터리 로 볼 수 [1]
근위 연산자를 쉽게[1] 계산할 수 있기 때문에 명시된 원시-이중 공식과 관련된 함수는 단순합니다.
실행
- Manopt.jl[17] 패키지는 Julia에서 알고리즘을 구현합니다.
- Gabriel Peyré는 MATLAB,[note 1] Julia, R 및 Python에서[18] 알고리즘을 구현합니다.
- 역문제를 위한 파이썬 라이브러리인 오퍼레이터 이산화 라이브러리(ODL)[19]에서,
chambolle_pock_solver메소드를 구현합니다.
참고 항목
메모들
- ^ 이 코드는 기사의 이미지를 얻기 위해 사용되었습니다.
레퍼런스
- ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab Chambolle, Antonin; Pock, Thomas (2011-05-01). "A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging". Journal of Mathematical Imaging and Vision. 40 (1): 120–145. doi:10.1007/s10851-010-0251-1. ISSN 1573-7683. S2CID 207175707.
- ^ a b c Sidky, Emil Y; Jørgensen, Jakob H; Pan, Xiaochuan (2012-05-21). "Convex optimization problem prototyping for image reconstruction in computed tomography with the Chambolle–Pock algorithm". Physics in Medicine and Biology. 57 (10): 3065–3091. arXiv:1111.5632. Bibcode:2012PMB....57.3065S. doi:10.1088/0031-9155/57/10/3065. ISSN 0031-9155. PMC 3370658. PMID 22538474.
- ^ a b c d Fang, Faming; Li, Fang; Zeng, Tieyong (2014-03-13). "Single Image Dehazing and Denoising: A Fast Variational Approach". SIAM Journal on Imaging Sciences. 7 (2): 969–996. doi:10.1137/130919696. ISSN 1936-4954.
- ^ a b Allag, A.; Benammar, A.; Drai, R.; Boutkedjirt, T. (2019-07-01). "Tomographic Image Reconstruction in the Case of Limited Number of X-Ray Projections Using Sinogram Inpainting". Russian Journal of Nondestructive Testing. 55 (7): 542–548. doi:10.1134/S1061830919070027. ISSN 1608-3385. S2CID 203437503.
- ^ Pock, Thomas; Cremers, Daniel; Bischof, Horst; Chambolle, Antonin (2009). "An algorithm for minimizing the Mumford-Shah functional". 2009 IEEE 12th International Conference on Computer Vision: 1133–1140. doi:10.1109/ICCV.2009.5459348. ISBN 978-1-4244-4420-5. S2CID 15991312.
- ^ "A Generic Proximal Algorithm for Convex Optimization—Application to Total Variation Minimization". IEEE Signal Processing Letters. 21 (8): 985–989. 2014. Bibcode:2014ISPL...21..985.. doi:10.1109/LSP.2014.2322123. ISSN 1070-9908. S2CID 8976837.
- ^ a b Ekeland, Ivar; Témam, Roger (1999). Convex Analysis and Variational Problems. Society for Industrial and Applied Mathematics. p. 61. doi:10.1137/1.9781611971088. ISBN 978-0-89871-450-0.
- ^ Nesterov, Yu. (2005-05-01). "Smooth minimization of non-smooth functions". Mathematical Programming. 103 (1): 127–152. doi:10.1007/s10107-004-0552-5. ISSN 1436-4646. S2CID 2391217.
- ^ Uzawa, H. (1958). "Iterative methods for concave programming". In Arrow, K. J.; Hurwicz, L.; Uzawa, H. (eds.). Studies in linear and nonlinear programming. Stanford University Press.
- ^ Pock, Thomas; Chambolle, Antonin (2011-11-06). "Diagonal preconditioning for first order primal-dual algorithms in convex optimization". 2011 International Conference on Computer Vision: 1762–1769. doi:10.1109/ICCV.2011.6126441. ISBN 978-1-4577-1102-2. S2CID 17485166.
- ^ Chambolle, Antonin (2004-01-01). "An Algorithm for Total Variation Minimization and Applications". Journal of Mathematical Imaging and Vision. 20 (1): 89–97. doi:10.1023/B:JMIV.0000011325.36760.1e. ISSN 1573-7683. S2CID 207622122.
- ^ Getreuer, Pascal (2012). "Rudin–Osher–Fatemi Total Variation Denoising using Split Bregman" (PDF).
- ^ Esser, Ernie; Zhang, Xiaoqun; Chan, Tony F. (2010). "A General Framework for a Class of First Order Primal-Dual Algorithms for Convex Optimization in Imaging Science". SIAM Journal on Imaging Sciences. 3 (4): 1015–1046. doi:10.1137/09076934X. ISSN 1936-4954.
- ^ Lions, P. L.; Mercier, B. (1979). "Splitting Algorithms for the Sum of Two Nonlinear Operators". SIAM Journal on Numerical Analysis. 16 (6): 964–979. Bibcode:1979SJNA...16..964L. doi:10.1137/0716071. ISSN 0036-1429. JSTOR 2156649.
- ^ Beck, Amir; Teboulle, Marc (2009). "A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems". SIAM Journal on Imaging Sciences. 2 (1): 183–202. doi:10.1137/080716542. ISSN 1936-4954. S2CID 3072879.
- ^ Nestorov, Yu.E. "A method of solving a convex programming problem with convergence rate ". Dokl. Akad. Nauk SSSR. 269 (3): 543–547.
- ^ "Chambolle-Pock · Manopt.jl". docs.juliahub.com. Retrieved 2023-07-07.
- ^ "Numerical Tours - A Numerical Tour of Data Science". www.numerical-tours.com. Retrieved 2023-07-07.
- ^ "Chambolle-Pock solver — odl 0.6.1.dev0 documentation". odl.readthedocs.io. Retrieved 2023-07-07.
진일보한 내용
- Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press.
- Wright, Stephen (1997). Primal-Dual Interior-Point Methods. Philadelphia, PA: SIAM. ISBN 978-0-89871-382-4.
- Nocedal, Jorge; Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 978-0-387-98793-4.
외부 링크
- EE364b 스탠퍼드 과정 홈페이지