[논문]선형 회귀분석 기반 합산영역테이블 정밀도 향상 기법

정주현; 이성길

doi:10.3745/ktsde.2013.2.11.809

선형 회귀분석 기반 합산영역테이블 정밀도 향상 기법
Linear Regression-Based Precision Enhancement of Summed Area Table 원문보기

정보처리학회논문지. KIPS transactions on software and data engineering. 소프트웨어 및 데이터 공학, v.2 no.11, 2013년, pp.809 - 814

정주현 (성균관대학교 전자전기컴퓨터공학과) , 이성길 (성균관대학교 컴퓨터공학과)

초록
AI-Helper

합산영역테이블은 이미지 픽셀 주변 임의의 사각 영역 내 픽셀 값의 합을 4개 픽셀의 합차로 표현할 수 있는 자료구조이다. 그러나 합산영역테이블은 픽셀의 값을 한쪽 모서리에서 다른 쪽 모서리로 순차 누적하므로, 이미지의 크기가 큰 경우에 부동소수점 방식의 표현 범위를 초과하는 문제가 일어날 수 있다. 이를 해결하기 위해 본 논문은 선형 회귀분석을 이용하여 이미지를 근사하고, 회귀분석식과의 차이만을 누적하여 정밀도 누적 오차를 감소시킬 수 있는 제안한다. 또한, 이미지의 복원 시 회귀분석식의 합을 2중 적분을 이용하여 상수시간에 구할 수 있는 방법을 함께 제안 한다. 이미지의 복원에 대한 실험을 수행하였고, 결과는 제안하는 방식이 일반적인 고정오프셋 방식보다 누적 오차를 감소시킴을 보였다.

Abstract ▼ AI-Helper

Summed area table (SAT) is a data structure in which the sum of pixel values in an arbitrary rectangular area can be represented by the linear combination of four pixel values. Since SAT serially accumulates the pixel values from an image corner to the other corner, a high-resolution image can yield overflow in a floating-point representation. In this paper, we present a new SAT construction technique, which accumulates only the residuals from the linearly-regressed representation of an image and thereby significantly reduces the accumulation errors. Also, we propose a method to find the integral of the linear regression in constant time using double integral. We performed experiments on the image reconstruction, and the results showed that our approach more reduces the accumulation errors than the conventional fixed-offset SAT.

주제어

AI 본문요약
AI-Helper

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

문제 정의

본 논문에서는 이러한 성능저하를 매우 효과적으로 막기 위한 오프셋 적분 방식을 제안하였다. 이를 통해 문제점이었던 회귀분석 오프셋의 합을 적분을 이용하여 상수시간에 구할 수 있으며, 또한 이러한 적분은 추가적인 성능 부하가 매우 적어 일반적인 SAT와 거의 동일한 성능을 낼 수 있다.
본 논문은 SAT의 정밀도를 보다 효과적으로 향상시키기 위해 픽셀별 오프셋을 사용하는 방법을 제안한다. 픽셀별 오프셋은 선형 회귀분석(linear regression)을 이용하여 구하 고, SAT 생성 단계에서 회귀분석식과의 차이(residual)만을 누적함으로써, 일반적인 고정 오프셋 방식보다 누적오차를 줄여, 정밀도를 현격히 향상시킬 수 있다.
본 논문은 선형 회귀분석을 통해 이미지를 채널별로 근사 하고, 회귀분석식과의 오차만을 누적하여 SAT의 정밀도를 향상시키기 위한 방법을 제안하였다. 또한 이미지 복원 시 오프셋을 복원함에 있어 상수시간에 계산 가능한 적분을 사용하여 그 성능을 비약적으로 향상시켜, 성능저하 없이 고정 오프셋 방식을 대체하여 품질을 향상시킬 수 있음을 보였다.
이러한 회귀분석 기반의 오프셋은 고정 오프셋 방식과 달리 각 픽셀 별로 그 값이 변하므로, 이미지 복원 시 각 픽셀에서 회귀분석 된 오프셋을 따로 구하여 전 영역에 걸쳐 모두 더해야 하는 부하가 추가로 발생한다. 이에, 본 논문에서는 이러한 회귀분석 오프셋의 합을 수치적으로 적분하여 이미지의 복원을 상수 시간에 가능하게 하여, 이미지 복원 성능 또한 비약적으로 향상시키는 방법도 함께 제안한다.

제안 방법

SAT의 정밀도를 높이기 위해 본 논문에서는 선형 회귀 분석을 이용하여 각 픽셀의 오프셋을 계산한다. Fig.
그러나, 이러한 방법은 큰 영역에 대하여 무시하지 못할 계산 부하를 동반하므로 본 논문에서는 아래와 같이 선형 회귀식을 x와 y에 대해 2중 적분한 식을 이용하여 간단히 상수 시간에 구할 수 있는 방법을 제안한다.
2 참조). 또한 정밀도 문제에 관련하여 이미지에 고정 오프셋을 적용하여 테이블을 생성할 것을 제시하였다. 이러한 방법을 통해 픽셀 값의 범위를 [0.
이는 사각필터 링을 적용하지 않고, 원본 그대로의 이미지와 비교를 함으로써, 누적 자체의 오차를 보기 위함이다. 보편적인 고정오프셋 방식과 본 논문에서 제안하는 방법이 사용되었다.
본 논문에서 제안하는 SAT는 OpenGL을 이용하여 구현 되었으며, 성능 측정을 위해 Intel Core i7 3770, 16GB RAM, NVIDIA　Geforce GTX680의 사용 환경에서 테스트 되었다. 고정 오프셋을 사용할 경우 모든 픽셀에 같은 오프 셋이 적용되어 복원 시, SAT로부터 복원된 결과에 단 하나의 상수 오프셋을 합하여 빠르게 복원 할 수 있다.
오프셋 보정 방법에 따른 성능 차이를 관찰하기 위해 9×9 사각 필터링에 대한 실험을 실시하였다. 비교를 위해 총 3가지 방법, 고정 오프셋, 선형적인 오프셋(선형) 합산, 오프셋 적분을 이용하였으며, 성능은 초당 렌더링 프레임수를 이용하여 비교되었다(Table 1). 고정 오프셋을 사용할 경우 오프셋 복원을 위해 1개의 고정 값을 합하여 평균을 계산할 수 있으며, 선형적인 오프셋 합산의 경우 회귀분석식을 통해 81번의 오프셋 계산을 통해 합을 구한다.
Harris 등[7]은 CUDA를 이용한 work-efficient parallel scan 알고리즘을 소개하였으며, Nehab 등[8]은 overlapping 알고리즘을 소개 하였다. 수직 방향 계산을 위해 transpose를 이용, 수평 방향으로 계산을 한다. shared memory 사용으로 단순 병렬 알고리즘에 비해 그 성능을 향상시켰다.
오프셋 보정 방법에 따른 성능 차이를 관찰하기 위해 9×9 사각 필터링에 대한 실험을 실시하였다.
정밀도 문제를 해결하기 위해 SAT tile grid를 이용하였다. 이미지를 grid로 나누어 각 grid별로 SAT를 생성하였으며, 필요한 grid 수를 계산하는 방법을 소개하였다.
따라서 본 논문에서 제안하는 방법은 픽셀 그리고 채널 별로 다른 오프셋을 적용하여 정밀도를 더욱 향상한다. 이와 함께 SAT를 이용한 translucency 렌더링, glossy environmental reflection, depth of field 렌더링을 소개하였으며[2-3] 추가 적인 연구를 통해 high-dynamic range environment map을 이용한 image-based lighting 기법을 소개하였다[4].
Shen 등[5]은 soft shadow mapping에 사용할 prefiltering을 위해 SAT를 사용하였다. 정밀도 문제를 해결하기 위해 SAT tile grid를 이용하였다. 이미지를 grid로 나누어 각 grid별로 SAT를 생성하였으며, 필요한 grid 수를 계산하는 방법을 소개하였다.
정밀도 오차를 측정하기 위해 원본 이미지와 SAT를 이용하여 복원한 이미지를 비교하였다(Fig. 4). 이는 사각필터 링을 적용하지 않고, 원본 그대로의 이미지와 비교를 함으로써, 누적 자체의 오차를 보기 위함이다.

데이터처리

x와 y 는 각각 이미지의 x축, y축 좌표이다. 회귀분석 결과는 RGB 채널별로 다를 수 있으므로, RGB 채널별로 별도의 회귀분석을 수행하여, 각 채널별로 별도의 회귀분석 오프셋을 이용한다.

이론/모형

Lena, Baboon, Owl의 3가지 이미지(각 해상도 512×512, 512×512, 1024×1024)가 사용되었으며, 원본 이미지와의 차이는 PSNR, SSIM[10]의 두 대표적 방법을 이용하여 측정되었다.
Recursive doubling 알고리즘은 보편적인 shader 기반 프로그래밍과 GPGPU 방식의 프로그래밍에 공통적으로 적용 가능하며, 본 연구에서는 pixel shader 기반의 프로그래밍 방법을 사용한다. 본 논문에서 제안하는 회귀분석 기반 방법은 SAT의 생성 방법과는 의존성이 없으므로, 최근 방식인 GPU의 shared memory 기반의 보다 효율적인 방법들 [7-8]을 이용하여 성능을 향상시킬 수 있다.
본 논문에서는 SAT를 생성하기 위해 보편적인 recursive doubling 알고리즘을 사용한다[2, 9]. Fig.

성능/효과

Lena, Baboon, Owl의 3가지 이미지(각 해상도 512×512, 512×512, 1024×1024)가 사용되었으며, 원본 이미지와의 차이는 PSNR, SSIM[10]의 두 대표적 방법을 이용하여 측정되었다. PSNR은 세 이미지에 대해 본 논문의 회귀분석 기반 방법이 고정 오프셋 방식에 비해 오차가 현격히 줄였음을 알 수 있다. 해상도가 높은 이미지인 경우 오차가 더 많이 누적되어 상대적으로 낮은 복원품질을 보이나, 그 역시 50 dB 이상이 되어, 만족스런 복원이 가능함을 알 수 있다.
그러나 고정 오프셋 방식은 여전히 이미지의 해상도와 색상 분포에 따라 음수나 양수 방향으로 정밀도가 떨어지게 될 잠재적인 문제점을 안고 있다. 따라서 본 논문에서 제안하는 방법은 픽셀 그리고 채널 별로 다른 오프셋을 적용하여 정밀도를 더욱 향상한다. 이와 함께 SAT를 이용한 translucency 렌더링, glossy environmental reflection, depth of field 렌더링을 소개하였으며[2-3] 추가 적인 연구를 통해 high-dynamic range environment map을 이용한 image-based lighting 기법을 소개하였다[4].
본 논문은 선형 회귀분석을 통해 이미지를 채널별로 근사 하고, 회귀분석식과의 오차만을 누적하여 SAT의 정밀도를 향상시키기 위한 방법을 제안하였다. 또한 이미지 복원 시 오프셋을 복원함에 있어 상수시간에 계산 가능한 적분을 사용하여 그 성능을 비약적으로 향상시켜, 성능저하 없이 고정 오프셋 방식을 대체하여 품질을 향상시킬 수 있음을 보였다.
Recursive doubling 알고리즘은 보편적인 shader 기반 프로그래밍과 GPGPU 방식의 프로그래밍에 공통적으로 적용 가능하며, 본 연구에서는 pixel shader 기반의 프로그래밍 방법을 사용한다. 본 논문에서 제안하는 회귀분석 기반 방법은 SAT의 생성 방법과는 의존성이 없으므로, 최근 방식인 GPU의 shared memory 기반의 보다 효율적인 방법들 [7-8]을 이용하여 성능을 향상시킬 수 있다.
Table 1에서 볼 수 있듯이, 선형적인 오프셋 합산을 이용할 경우, 고정 오프셋 방식에 비해 모든 픽셀(81개)에 대해 회귀분석식을 계산하고 더함으로써 성능이 1/3 정도까지 감소하는 것을 볼 수 있지만, 오프셋 적분을 적용한 방식은 사각 영역의 크기에 관계없이 한 번의 계산을 통해 사각 영역의 오프셋 합을 계산하기에 그 성능은 고정오프셋 방식과 거의 차이가 없음을 알 수 있다. 이러한 실험결과를 통해본 논문에서 제안하는 방법은 고정 오프셋 방식에서 성능 저하 없이 품질을 향상시킬 수 있음을 알 수 있다.
이러한 복원 오차는 이미지의 해상도가 커질수록 그 차이가 커질 것을 예상할 수 있다. 한편, SSIM은 세 이미지 모두 1 에 매우 가까워 복원된 이미지의 구조적 유사도가 매우 높은 것으로 나타나고 있고, 여전히 본 논문의 방법이 고정 오프셋 방식보다 나은 품질을 보임을 알 수 있다.

후속연구

이에 본 저자들은 전역 회귀분석의 단점을 극복하기 위해 국소적 회귀분석을 적용하여 정밀도 오차를 보다 감소시킬 수 있는 방법을 향후 연구에 계획하고 있다. 본 논문에서 제안하는 선형 회귀분석을 넘어, 다중 차수의 회귀 분석이나 이산 자료 보간(Scattered data interpolation)과 같은 방법이 사용될 수 있으리라 예상하며, 이에 대한 연구를 진행할 예정이다.
이에 본 저자들은 전역 회귀분석의 단점을 극복하기 위해 국소적 회귀분석을 적용하여 정밀도 오차를 보다 감소시킬 수 있는 방법을 향후 연구에 계획하고 있다. 본 논문에서 제안하는 선형 회귀분석을 넘어, 다중 차수의 회귀 분석이나 이산 자료 보간(Scattered data interpolation)과 같은 방법이 사용될 수 있으리라 예상하며, 이에 대한 연구를 진행할 예정이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	합산영역테이블은 어떤 자료구조인가?	합산영역테이블(Summed Area Table; 이하 SAT)은 이미지 픽셀 주변 임의의 사각 영역 내 픽셀 값의 합을 영역의 넓이(즉, 샘플링할 픽셀 수)에 관계없이 동일한 수의 픽셀을 사용하여 상수 시간에 구할 수 있는 2차원 테이블형의 자료 구조이다[1]. SAT는 각 성분이 현재 위치와 아래 왼쪽 모서 리(혹은 위 오른쪽 모서리)로 정의된 사각 영역을 이루는 모든 성분의 합을 저장한다.
	본 논문에서 오프셋 보정 방법에 따른 성능 차이를 관찰하기 위해 9x9 사각 필터링에 대한 실험을 진행하였을 때 어떤 방법들을 이용하여 비교하였는가?	오프셋 보정 방법에 따른 성능 차이를 관찰하기 위해 9×9 사각 필터링에 대한 실험을 실시하였다. 비교를 위해 총 3가지 방법, 고정 오프셋, 선형적인 오프셋(선형) 합산, 오프셋 적분을 이용하였으며, 성능은 초당 렌더링 프레임수를 이용하여 비교되었다(Table 1). 고정 오프셋을 사용할 경우 오프셋 복원을 위해 1개의 고정 값을 합하여 평균을 계산할 수 있으며, 선형적인 오프셋 합산의 경우 회귀분석식을 통해 81번의 오프셋 계산을 통해 합을 구한다.
	합산영역테이블은 어떤 문제점이 있는가?	합산영역테이블은 이미지 픽셀 주변 임의의 사각 영역 내 픽셀 값의 합을 4개 픽셀의 합차로 표현할 수 있는 자료구조이다. 그러나 합산영역테이블은 픽셀의 값을 한쪽 모서리에서 다른 쪽 모서리로 순차 누적하므로, 이미지의 크기가 큰 경우에 부동소수점 방식의 표현 범위를 초과하는 문제가 일어날 수 있다. 이를 해결하기 위해 본 논문은 선형 회귀분석을 이용하여 이미지를 근사하고, 회귀분석식과의 차이만을 누적하여 정밀도 누적 오차를 감소시킬 수 있는 제안한다.

참고문헌 (10)

Crow, Franklin C. "Summed-area tables for texture mapping." ACM SIGGRAPH Computer Graphics. Vol.18, No.3, ACM, 1984.
Hensley, Justin, et al. "Fast SummedArea Table Generation and its Applications." Computer Graphics Forum. Vol.24, No.3, Blackwell Publishing, Inc., 2005.

상세보기
Hensley, Justin, et al. "Interactive summed-area table generation for glossy environmental reflections." ACM SIGGRAPH 2005 Sketches. ACM, 2005.
Hensley, Justin, et al. "Fast hdr image-based lighting using summed-area tables." Symposium on Interactive 3D Graphics and Games (Poster). 2007.
Shen, Li, Jieqing Feng, and Baoguang Yang. "Exponential Soft Shadow Mapping." Computer Graphics Forum. Vol.32, No.4, Blackwell Publishing Ltd, 2013.

상세보기
Sengupta, Shubhabrata, Aaron E. Lefohn, and John D. Owens. "A work-efficient step-efficient prefix sum algorithm." Proceedings of the Workshop on Edge Computing Using New Commodity Architectures. 2006.
Harris, Mark, Shubhabrata Sengupta, and John D. Owens. "Parallel prefix sum (scan) with CUDA." GPU gems 3.39 (2007): 851-876.
Nehab, Diego, et al. "GPU-efficient recursive filtering and summed-area tables." ACM Transactions on Graphics (TOG) 30.6 (2011): 176.
Horn, Daniel. "Stream reduction operations for GPGPU applications." Gpu gems 2 (2005): 573-589.
Wang, Zhou, et al. "Image quality assessment: From error visibility to structural similarity." Image Processing, IEEE Transactions on 13.4 (2004): 600-612.

상세보기

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증