Replacing Fractional Arithmetic by Integer Arithmetic on Rendering Graphics Primitives

위영철,김하진,Wee, Young-Cheul,Kimn, Ha-Jine Korea Computer Graphics Society 2000 컴퓨터그래픽스학회논문지 Vol.6 No.3

래스터 그래픽스 시스템에서 처리되는 픽슬의 수는 한 프래임 당 100 만 개가 넘을 경우가 많다. 따라서, 그래픽스 프리미티브를 랜더링에서 실수연산을 정수연산으로 대체 함으로써 많은 처리속도 향상이 된다. 본 논문에서는, 스케일링에 의하여 그래픽스 프리미티브 랜더링 알고리즘의 실수연산을 정수연산으로 대체하는 방법을 소개한다. 이 방법은 필터링 된 직선 그리기와 구로세이딩에 적용된다. 또한, 이 방법은 증가적 방법에 근거한 다른 그래픽스 랜더링 알고리즘에도 적용 될 수 있다. 특히, 이 방법은 이미 ASIC 구현이 된 기존의 알고리즘에서 극히 일부분의 단순 수정을 요구하기 때문에 ASIC 구현이 용이하다. The number of pixels being processed in a raster graphics system often exceeds 1 million per frame. Replacing fractional arithmetic by integer arithmetic on rendering graphics primitives will therefore significantly improve the rendering performance. A scaling method that replaces fractional arithmetic by integer arithmetic on rendering graphics primitives is introduced. This method is applied to the filtered edge drawing and Gouraud shading. This method will also be applicable to some of other incremental algorithms for rendering graphics primitives. Because the scaling method requires only simple modifications upon the known algorithms that already have been implemented in ASIC (Application Specific Integrated Circuit), our algorithms can easily be implemented in ASIC. Our method will be useful especially for the low-price systems (e.g., home game machines, personal computers, etc.).

공간예측에 의한 고속 2${\times}$2 프랙탈 영상압축

위영철,Wee Young Cheul 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.11

본 논문은 극소 원자블록(ultra small atomic block)에 공간예측(spatial prediction)을 적용하여 프랙탈(fractal) 영상압축의 압축시간을 획기적으로 향상시키고 화질/압축률을 향상시키는 방법을 제안한다. 본 방법은 치역(range block)의 크기가 아주 작으면 아주 적은 탐색범위 내에서 변환계수(transformation parameter)들의 값을 극히 제한하더라도 유사한 정의역(domain block)을 쉽게 찾을 수 있고 변환계수들이 좋은 상호관계를 유지함을 이용하여 변환계수 예측으로 화질/압축률을 향상시킨다. 특히, 본 방법은 탐색범위를 극히 제한하기 때문에 기존의 프랙탈 압축방법들 보다 압축시간을 획기적으로 향상시킨다. In this paper, we introduce a very fast and efficient fractal coding scheme by using the spatial prediction on ultra-small atomic range blocks. This new approach drastically speeds up the encoding while improving the fidelity and the compression ratio. The affine transformation coefficients between adjacent range blocks induced by this method often have good correlations thereby the compression ratios can further be improved. The proposed method leads to improved rate-distortion performance compared to previously reported pure fractals, and it is faster than other state-of-the-art fractal coding methods.

공간예측에 의한 고속 2×2 프랙탈 영상압축

위영철(Young Cheul Wee) 한국정보과학회 2004 정보과학회논문지 : 시스템 및 이론 Vol.31 No.11·12

본 논문은 극소 원자블록(ultra small atomic block)에 공간예측(spatial prediction)을 적용하여 프랙탈(fractal) 영상압축의 압축시간을 획기적으로 향상시키고 화질/압축률을 향상시키는 방법을 제안한다. 본 방법은 치역(range block)의 크기가 아주 작으면 아주 적은 탐색범위 내에서 변환계수(transformation parameter)들의 값을 극히 제한하더라도 유사한 정의역(domain block)을 쉽게 찾을 수 있고 변환계수들이 좋은 상호관계를 유지함을 이용하여 변환계수 예측으로 화질/압축률을 향상시킨다. 특히, 본 방법은 탐색범위를 극히 제한하기 때문에 기존의 프랙탈 압축방법들 보다 압축시간을 획기적으로 향상시킨다. In this paper, we introduce a very fast and efficient fractal coding scheme by using the spatial prediction on ultra-small atomic range blocks. This new approach drastically speeds up the encoding while improving the fidelity and the compression ratio. The affine transformation coefficients between adjacent range blocks induced by this method often have good correlations thereby the compression ratios can further be improved. The proposed method leads to improved rate-distortion performance compared to previously reported pure fractals, and it is faster than other state-of-the-art fractal coding methods.

Replacing Fractional Arithmetic by Integer Arithmetic on Rendering Graphics Primitives

Young-Cheul Wee(위영철),Ha-Jine Kimn(김하진) 한국컴퓨터그래픽스학회 2000 컴퓨터그래픽스학회논문지 Vol.6 No.3

단조 행렬 탐색을 이용한 양방향 각도제한 근접점 계산방법

위영철(Young-Cheul Wee) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.1·2

이 논문은 행렬 탐색 방법을 이용하여 평면상의 n 개의 점에 대한 모든 L_p, 1≤p≤∞ 거리의 양방향 각도제한 근접 점 문제를 O( n log n) 시간에 계산하는 알고리즘을 고안한다. 이 방법은 최적의 시간 복잡도를 가지며 궤적추적 법을 쓰지 않기 때문에 수치오차가 적으며 구현이 용이하고 실용적이다. Using the Monotone Matrix Searching, we present an asymptotically optimal Ο( n log n) time divide-and-conquer algorithm for solving the symmetric angle restricted nearest neighbor problem for a set of n sites in the plane under any L_p metric, 1≤p≤∞. This algorithm works quite well in practice even for small values of n because the associated constants in its time complexity are fairly low, and because it does not follow a locus-based approach.

L∞(L₁) 디루니 삼각분할의 병렬처리 알고리즘

위영철(Young-Cheul Wee) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.3·4

본 논문은 영역별 근접 그래프 (geographic nearest neighbor graph)와 레인지 트리 (range tree)를 이용하여 평면 위의 n 개의 점에 대한 L∞(L₁) 거리 (metric) 상의 디루니 삼각분할 (Delaunay triangulation)을 구축하는 방법을 소개한다. 이 방법은 L∞(L₁) 거리 상에서 디루니 삼각분할에 있는 각 삼각형의 최소한 한 선분이 영역별 근접 그래프에 포함됨을 이용하여 레인지 트리 방법으로 디루니 삼각분할을 구축한다. 본 방법은 O( n log n)의 순차계산 시간에 L∞(L₁) 디루니 삼각분할을 구축하며, CREW-PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine)에서 Ο( n)의 프로세서로 Ο( log n)의 병렬처리 시간에 L∞(L₁)디루니 삼각분할을 구축한다. 또한, 이 방법은 직선간의 교차점 계산 대신 거리비교를 하기 때문에 수치오차가 적고 구현이 용이하다. Using the geographic nearest neighbor approach, we introduce a new method for constructing the Delaunay triangulation for a set S of n sites in the plane under the L∞(L₁) metric. Although there is no inclusion relationship between the geographic nearest neighbor graph and the Delaunay triangulation, we find that at least one edge of each triangle in the Delaunay triangulation is contained in a geographic nearest neighbor graph. Using this observation and employing the range tree scheme, we present an algorithm that constructs the Delaunay triangulation of S in O( n log n) sequential time. This algorithm can easily be parallelized, and takes Ο( log n) time with Ο( n) processors on a CREW-PRAM (Concurrent Read Exclusive Write Parallel Random Access Machine). Because the operations involved in this algorithm are mainly distance comparisons rather than line intersections, this algorithm is numerically stable and easy to implement.

움직임 벡터 예측 후보들과 적응적인 탐색 패턴을 이용하는 블록 정합 알고리즘

곽성근,위영철,김하진,Kwak, Sung-Keun,Wee, Young-Cheul,Kim, Ha-JIne 한국정보처리학회 2004 정보처리학회논문지B Vol.11 No.3

본 논문에서는 영상의 시공간적인 특성과 움직임 벡터의 중심 지향적 분포 특성을 이용하는 예측 탐색 알고리즘을 제안한다. 제안된 알고리즘을 이린 프레임 블록으로부터 예측된 움직임 벡터, 분할된 탐색 구간에 속하는 후보 벡터와 현재 프레임 블록의 이웃 블록으로 예측된 움직임 벡터 중에서 가장 작은 SAD 값을 갖는 점을 정확한 움직임 벡터를 찾기 위한 초기 탐색점 위치로 결정한다. 그리고 초기 탐색점 위치로 이동하여 움직임 크기에 따라 적응적인 탐색 패턴으로 탐색을 수행판다. 실험 결과 제안된 방식은 FS를 제외한 기존의 대표적인 고속 탐색 방식들에 비해 PSNR 값에 있어서 평균적으로 0.05∼0.34dB 개선되고 영상에 따라 최고 0.75dB 정도 우수한 결과를 나타내었다. In this paper, we propose the prediction search algorithm for block matching using the temporal/spatial correlation of the video sequence and the renter-biased property of motion vectors The proposed algorithm determines the location of a better starting point for the search of an exact motion vector using the point of the smallest SAD(Sum of Absolute Difference) value by the predicted motion vector from the same block of the previous frame and the predictor candidate pint in each search region and the predicted motion vector from the neighbour blocks of the current frame. And the searching process after moving the starting point is processed a adaptive search pattern according to the magnitude of motion vector Simulation results show that PSNR(Peak-to-Signal Noise Ratio) values are improved up to the 0.75dB as depend on the video sequences and improved about 0.05∼0.34dB on an average except the FS (Full Search) algorithm.

십자와 육각패턴을 이용한 고속 블록 정합 동작 예측 기법

박인영,남현우,위영철,김하진,Park, In-Young,Nam, Hyeon-Woo,Wee, Young-Cheul,Kim, Ha-Jine 한국정보처리학회 2003 정보처리학회논문지B Vol.10 No.7

본 논문에서는 십자패턴과 육각패턴을 이용한 고속 블록 정합 동작 예측 기법을 제안한다. 블록 기반 탐색에서 전역 탐색방법이 가장 좋은 동작벡터를 찾지만, 탐색영역 내의 모든 전을 검색하기 때문에 많은 시간을 필요로 하게 된다. 본 방법은 대부분의 동영상에서 동작벡터가 블록의 중심 부근에 집중적으로 분포함을 착안하여 십자패턴으로 중앙을 우선 탐색한 다음 움직임이 큰 동작벡터를 육각패턴을 사용하여 찾는다. 실험결과, 본 방법은 기존의 탐색방법보다 화질과 탐색시간에서 대부분의 경우에 좋은 성능을 보임을 알 수 있다. In this paper, we propose a fast block-matching motion estimation method using the cross pattern and the hexagonal pattern. For the block-matching motion estimation method, full search finds the best motion estimation, but it requires huge search time because it has to check every search point within the search window. The proposed method makes use of the fact that most of motion vectors lie near the center of block. The proposed method first uses the cross pattern to search near the center of block, and then uses the hexagonal pattern to search larger motion vectors. Experimental results show that our method is better than recently proposed search algorithms in terms of mean-square error performance and required search time.

정규화된 분산을 이용한 프랙탈 압축방법

김종구,함도용,위영철,김하진,Kim, Jong-Koo,Hamn, Do-Yong,Wee, Young-Cheul,Kimn, Ha-Jine 한국정보처리학회 2001 정보처리학회논문지 A Vol.8 No.4

프랙탈 코딩은 높은 압축률을 포함한 여러 가지 장점을 가지고 있으나 유사블록 탐색에 긴 시간이 소요되는 문제점을 가지고 있다. 본 논문은 각 블록의 정규화 된 분산 값은 명도(contrast)와 밝기(brightness)에 독립적임을 발견하고, 이를 이용하여 d(key의 수)차원 공간에서 최근접부근탐색(nearest neighbor search)을 하여 효율적인 유사블록을 탐색하는 방법을 제안한다. 본 방법은 각 치역 블록 당 Ο(log N), (N : 정의역블록 수) 시간에 유사 정의역 블록 찾을 수 있음을 보였다. 압축처리 된 이미지는 각 치역 블록 당 Ο(N) 시간이 요구되는 전체탐색의 PSNR (Peak Signal Noise Ratio)과 거의 같은 값을 얻게 되었다. 또한, 본 방법은 에지가 많은 이미지에도 전체탐색과 거의 유사한 PSNR로 압축되는 장점을 가진다. Fractal image coding suffers from the long search time of domain pool although it provides many properties including the high compression ratio. We find that the normalized variance of a block is independent of contrast, brightness. Using this observation, we introduce a self similar block searching method employing the d-dimensional nearest neighbor searching. This method takes Ο(log/N) time for searching the self similar domain blocks for each range block where N is the number of domain blocks. PSNR (Peak Signal Noise Ratio) of this method is similar to that of the full search method that requires Ο(N) time for each range block. Moreover, the image quality of this method is independent of the number of edges in the image.

고속 블록 정합을 위한 납작한 육각패턴 기반 탐색 알고리즘

남현우(Hyeon-Woo Nam),위영철(Young-Cheul Wee),김하진(Ha-Jine KIMN) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅱ

서로 다른 형태와 크기를 가지는 탐색패턴과 움직임 벡터의 분포는 블록 정합 기법에서 탐색 속도와 화질을 좌우하는 중요한 요소이다. 본 논문에서는 납작한 육각패턴을 이용한 새로운 고속 블록 정합 알고리즘을 제안한다. 이 방법은 작은 육각패턴을 이용하여 적은 탐색점으로 움직임이 적은 벡터를 우선 찾은 다음에 움직임이 큰 벡터에 대해서는 납작한 육각패턴을 이용하여 고속으로 움직임 벡터를 찾게 하였다. 실험결과, 제안된 알고리즘은 육각패턴 탐색기법에 비하여 움직임 벡터 예측의 속도에 있어서 약 11~51% 이상의 높은 성능 향상을 보였으며 화질 또한 PSNR 기준으로 약 0.05~0.74dB 의 향상을 보였다.