[논문]기울기 기반 빠른 정상점 탐색에 대한 연구

안정호

초록
AI-Helper

본 논문에서는 기울기 기반 빠른 정상점 탐색 방법론을 제시하고 시뮬레이션 결과를 제시한다. 제안하는 방법론은 유한 구간에서 단봉 그래프를 가지는 함수의 정상점(최대치)을 최대한 적은 수의 함수값을 참조하여 찾는 문제에 대한 솔루션으로, 대표적인 적용분야로는 자동초점이 있다. 우리는 정상점 탐색을 위해 주기적 탐색, 기울기 기반 탐색, 상세 탐색과 같이 세가지 탐색 전략을 통해 정상점을 찾는다. 노이즈가 첨가된 가우시안 함수를 발생시켜 시뮬레이션 한 결과 대략 8번탐색 횟수와 1.04의 오차를 보임을 알 수 있었다.

Abstract ▼ AI-Helper

In this paper we propose a new fast peak searching method using the gradient and present simulation results. The proposed method is a solution to the problem that finds the peak(maximum) of the unimodal function on a finite interval with minimum searching steps. Its main application is the auto-focu...

In this paper we propose a new fast peak searching method using the gradient and present simulation results. The proposed method is a solution to the problem that finds the peak(maximum) of the unimodal function on a finite interval with minimum searching steps. Its main application is the auto-focus in the mobile phone. We propose the three steps to find the peak; periodic search, gradient-based search and detail search. In simulation we generated the Gaussian functions with white noise and have the result of about 8 searching steps and 1.04 errors on average.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 기울기를 이용한 빠른 정상점탐색 방법론을 제안하였다. 제안하는 방법론은 주기적 탐색, 기울기 탐색, 상세탐색 등 세 가지 탐색과정을 포함한다.
SOM과 같은 신경망(Neural Network)[1]을 이용한 방식, 차 방정식 (Difference equation)[2]을 이용한 방식, 힐 클라이밍(Hill climbing)[3,8] 방식, 규칙성(Rule based method)[6]을 이용한 방식, 황금분할 (Golden section) 방식, 이중 분할[9] 방식 등과저 조도(Low illumination)에 강인한 방식 등 과거 10년 이상 빠른 정상점 탐색을 위한 다양한 방법론들이 개발되어 왔다. 본 논문에서는 기울기에 기반한 새로운 정상점 추정 방식을 제안한다. 본 논문의 1.
본 논문의 궁극적인 목표는 최소의 관측(참조)으로 함수 f의 최대치가 발생하는 지점 x = m₀를 찾거나 m₀와 가깝게 결정한다. 많은 응용분야에서 최고점은 안정적(stable)이기 때문에 m₀와 그 이웃점들 사이의 함수값은 큰 차이가 없다.
이러한 문제들은 특히 최대치나 최소치를 찾는 최적화(Optimization) 문제로 귀결되는 경우가 많다. 우리는 본 논문에서 단봉함수의 모드(mode)를 빠르게 추정하는 방법론을 제안함으로써, 최대우도 추정(Maximum Likelihood Estimation)과 같은 통계적 추정이나 디지털 카메라나 핸드폰 카메라에서 제공되는 자동초점(AF: Autofocus)기술과 같은 문제의 해결 방법론을 제공하고자 한다.
우리는 주어진 단봉 함수의 모드(mode)를 최소의 참조를 통해 (가장 가깝게) 찾아내는 것을 목적으로 하는 알고리즘을 제안하였다. 우리는 시뮬레이션을 통해 제안한 알고리즘의 성능을 정확성과 신속성 면에서 입증하였다.
이 구간의 길이를 정상점 위치를 추정함으로써 더 줄이는 것이 두 번째 단계인 기울기 기반 탐색 단계에서의 목표이다.

제안 방법

본 논문에서는 기울기에 기반한 새로운 정상점 추정 방식을 제안한다. 본 논문의 1.1 절에서는 정상점 탐색 문제를 정의하고 제약조건을 기술하였고, 2절에서 제안 하는 정상점 탐색 알고리즘을 주기적 탐색, 기울기 탐색, 상세 탐색 등 세 가지로 나누어 기술하였다. 3절에서는 제안한 알고리즘의 시뮬레이션 결과를 분석하였으며 4절에서는 결론과 앞으로의 연구 진행 방향을 제시하였다.
본 논문에서는 기울기를 이용한 빠른 정상점탐색 방법론을 제안하였다. 제안하는 방법론은 주기적 탐색, 기울기 탐색, 상세탐색 등 세 가지 탐색과정을 포함한다. 주기적 탐색을 통해 국소 최대값을 피하면서 노이즈에 강인하게 모드를 포함하는 구간을 추정할 수 있었고 이렇게 추정 된 구간은 기울기 기반 탐색을 통해 더 작은 구간으로 추정되었다.
주기적 탐색과 기울기 탐색 이후 상세 탐색을 통해 모드를 추정한다. 우리는 상세 탐색에서 정확한 모드를 구하기 위해 탐색횟수를 늘리는 정책(strategy)을 사용하지 않았다.
주기적 탐색을 위하여 피봇값 1, 13, 25, 38, 50의 순으로 함수값을 조사하여 실질적으로 함수값이 감소하는 지점을 찾는 과정을 2.1절의 절차에 따라 수행하였다. 노이즈에 강인하게 기울기의 실질적 감소를 측정하기 위해 x > y에 대하여 다음과 같을 때 함수값 f(x)가 f(y)이 실질적으로 크다고 설정하였다.
주기적 탐색과 기울기기반 탐색을 통해 얻어진 구간 ID를 [S′ , E′] 라 할 때, 이 구간이 충분히 작다는 가정 하에 많은 참조(탐색)를 통해 모드를 결정할 수 있다. 하지만 탐색횟수가 증가하는 것은 바람직하지 않기 때문에 모드와 충분히 가까운 점을 추정하는 방식으로 상세탐색을 수행한다.

대상 데이터

시뮬레이션을 위해 상수 μ는 1과 N사이에서 랜덤으로 발생시켰고 A는 500, σ는 10으로 고정시켰다.

성능/효과

시뮬레이션을 통해 제안한 방법론은 속도와 정확도 면에서 모두 훌륭한 결과를 보임을 보일 수 있었다. 구간의 길이가 모바일 핸드폰의 스텝 수 50에 대해 평균 7.1번의 탐색을 수행하여 1.04 정도의 정확도를 보였다. 탐색횟수가 데이터에 의존적이지 않고, 스텝 수 N과 피봇횟수 n에 대한 함수로결정되는 것은 제안한 방법론의 큰 장점이라 할 수 있다.
이후 상세탐색을 통해 확률적으로 모드를 추정할 수 있었다. 시뮬레이션을 통해 제안한 방법론은 속도와 정확도 면에서 모두 훌륭한 결과를 보임을 보일 수 있었다. 구간의 길이가 모바일 핸드폰의 스텝 수 50에 대해 평균 7.
이러한 고려없이 단순히 두 함수 값만을 비교할 경우 노이즈에 의해 잘못된 결과가 많이 발생함을 실험적으로 확인할 수 있었다. 실험결과 주기적 탐색에서 구한 구간의 99.93%가 정상점을 포함함을 확인할 수 있었다. 여기서 실패하는 0.
우리는 주어진 단봉 함수의 모드(mode)를 최소의 참조를 통해 (가장 가깝게) 찾아내는 것을 목적으로 하는 알고리즘을 제안하였다. 우리는 시뮬레이션을 통해 제안한 알고리즘의 성능을 정확성과 신속성 면에서 입증하였다.
성공률은 탐색을 통해 생성된 구간이 실제 모드값을 포함하는 비율을 보여준다. 우리는 주기적 탐색을 통해 평균 3.88번의 탐색(함수값 참조)으로 구간의 길이를 40.78%(=20.39/50)로 줄일 수 있 었다. 추가로 기울기 탐색을 수행함으로써 4.
이러한 고려없이 단순히 두 함수 값만을 비교할 경우 노이즈에 의해 잘못된 결과가 많이 발생함을 실험적으로 확인할 수 있었다. 실험결과 주기적 탐색에서 구한 구간의 99.
39/50)로 줄일 수 있 었다. 추가로 기울기 탐색을 수행함으로써 4.14번의 탐색으로 구간의 길이를 25.34%(=12.67/50)로 줄일 수 있었다.

질의응답

핵심어	질문	논문에서 추출한 답변
	제약조건이 없을 때 단봉함수의 모드는 어떻게 찾는가?	제약조건이 없을 시 단봉함수의 모드를 찾는 문제는 간단하다. 정의역의 함수값을 모두 조사하고 그 중 최대값을 발생시키는 정의역의 값, 즉 모드를 찾아내면 된다. 하지만 이런 전 검사(full search) 방법론은 시간이나 프로세서와 같은 리소스(resource)가 제한적인 상황에는 맞지 않는다
	노이즈를 포함하는 단봉 함수의 탐색은 어떤 위험이 있는가?	노이즈를 포함하는 단봉 함수의 탐색은 국소 최대값(Local minimum)을 찾을 위험이 있다. 우리는 이러한 위험을 최소화시키기 위해 주기적 탐색을 통해 주어진 구간을 탐색하여 부분 구간을 추출한다.
	과거에 개발된 정상점 탐색을 위한 방법에는 무엇이 있는가?	이러한 이유로 실시간 탐색에 적합한 정상점 (또는 모드) 추정을 위한 탐색방법들이 개발되어왔다[5]. SOM과 같은 신경망(Neural Network)[1]을 이용한 방식, 차 방정식 (Difference equation)[2]을 이용한 방식, 힐 클라이밍(Hill climbing)[3,8] 방식, 규칙성(Rule based method)[6]을 이용한 방식, 황금분할 (Golden section) 방식, 이중 분할[9] 방식 등과저 조도(Low illumination)에 강인한 방식 등 과거 10년 이상 빠른 정상점 탐색을 위한 다양한 방법론들이 개발되어 왔다. 본 논문에서는 기울기에 기반한 새로운 정상점 추정 방식을 제안한다.

참고문헌 (9)

C.Y. Chen, R.-C. Hwang, "An Embedded Lens Contr oller for Passive Auto-Focusing Camera Device Ba sed on SOM Neural Network", TENCON 2006, IEEE Region 10 Conference, pp. 1-4, Nov. 2006.
C.-M. Chen, C.-M. Hong, and H.-C. Chung, "Efficient Auto-Focus Algorithm Utilizing Discrete Difference Equation Prediction Model for Digital Still Cameras", IEEE Transactions on Consumer Electronics, Vol.52(4), pp. 1135-1143, 2006.

상세보기
K.-S. Choi, J.-S. Lee, and S.-J. Ko, "New Aotofocus ing Technique Using the Frequency Selective Weighted Median Filter for Video Cameras", IEEE Transactions on Consumer Electronics, Vol. 45(3), pp. 820-827, 1999.

상세보기
M. Gamadia, N. Kehtarnavaz, K. R.-Hoffman, "Low-Light AutoFocus Enhancement for Digital and Cell-Phone Camera Image Pipelines", IEEE Transcations on Consumer Electronics, Vol. 53(2), pp. 249-257, 2007.

상세보기
M. Gamadia and N. Kehtarnavaz, "A Real-time Continuous Automatic Focus Algorithm for Digital Cameras", IEEE Southwest Symposium on Image Analysis and Interpretation, pp. 163-167, 2006.
N. Kehtanrnavaz, H.-J. Oh, "Development and real-time implementation of a rule-based auto-focus algorithm", Real-Time Imaging, Vol. 9, pp. 197-203, June 2003.

상세보기
W. H. P. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, "Numerical Recipes in Fortran, second edition", Cambridge University Press, pp. 390-395, 1992.
J. He, R. Zhou, and Z. Hong, "Modified Fast Climbing Search Auto-Focus Algorithm with Adaptive Step Size Searching Technique for Digital Camera", IEEE Transactions on Consumer Electronics, Vol. 49(2), pp. 257-262, 2003.

상세보기
안정호, "두 점의 관계를 이용한 정상점 검색 알고리즘에 관한 연구", 한국디지털콘텐츠학회 학술대회 논문집, pp. 273-275, Dec. 2009.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

기울기 기반 빠른 정상점 탐색에 대한 연구
A Simulation Study on the Fast Gradient-based Peak Searching Method 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

기울기 기반 빠른 정상점 탐색에 대한 연구 A Simulation Study on the Fast Gradient-based Peak Searching Method 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

대상 데이터

성능/효과

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

안정호 (11)

관련 콘텐츠

원문 보기

원문 URL 링크

연관된 기능

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

기울기 기반 빠른 정상점 탐색에 대한 연구
A Simulation Study on the Fast Gradient-based Peak Searching Method 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper