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.

공간예측에 의한 고속 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.

공간예측에 의한 고속 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.

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.).

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

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

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

무손실 이미지 압축을 위한 컨텐스트 기반 예측 알고리즘

최정렬(Jeong Ryeol Choi),위영철(Young Cheul Wee) 한국정보과학회 2008 한국정보과학회 학술발표논문집 Vol.35 No.2

본 논문은 무손실 이미지 압축(lossless image compression)을 위한 컨텍스트(context)를 기반으로 하는 새로운 예측 알고리즘 CBSP(context-based statistical prediction)을 제안한다. 무손실 이미지 압축에서 JPEG-LS는 다른 표준 압축 알고리즘에 비해 가장 좋은 압축 성능을 보인다. JPEG-LS는 미디언 에지 디텍터(median edge detector, MED)를 기반으로 하는 LOCO-I 의 예측 방법을 사용하고 있다. 실험 결과 CBSP가 LOCO-I의 예측 알고리즘보다 평균 10% 이상의 엔트로피(entropy) 향상을 보인다.

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

박인영,남현우,위영철,김하진,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.

단위 다이아몬드와 납작한 육각패턴을 이용한 고속 블록 정합 알고리즘

남현우(Hyeon-Woo Nam),위영철(Young-Cheul Wee),김하진(Ha-Jine Kimn) 한국정보과학회 2004 정보과학회 컴퓨팅의 실제 논문지 Vol.10 No.1

서로 다른 형태와 크기를 가지는 탐색패턴과 움직임 벡터의 분포는 블록 정합 알고리즘에서 탐색 속도와 화질을 좌우하는 중요한 요소이다. 본 논문에서는 단위 다이아몬드패턴과 납작한 육각패턴을 이용한 새로운 고속 블록 정합 알고리즘을 제안한다. 이 알고리즘은 단위 다이아몬드패턴을 이용하여 적은 탐색점으로 움직임이 적은 벡터를 우선 찾은 다음에 움직임이 큰 벡터에 대해서는 납작한 육각패턴을 이용하여 고속으로 움직임 벡터를 찾게 하였다. 실험결과, 제안된 알고리즘은 육각패턴 탐색 알고리즘에 비하여 움직임 벡터 예측의 속도에 있어서 약 11~51%의 높은 성능 향상을 보였으며 화질 또한 PSNR 기준으로 약 0.05~0.74dB의 향상을 보였다. In the block matching algorithm, search patterns of different shapes or sizes and the distribution of motion vectors have a large impact on both the searching speed and the image quality. In this paper, we propose a new fast block matching algorithm using the unit-diamond search pattern and the flat-hexagon search pattern. Our algorithm first finds the motion vectors that are close to the center of search window using the unit-diamond search pattern, and then fastly finds the other motion vectors that are not close to the center of search window using the flat-hexagon search pattern. Through experiments, compared with the hexagon-based search algorithm(HEXBS), the proposed unit-diamond and flat-hexagonal pattern search algorithm(UDFHS) improves as high as 11~51% in terms of average number of search point per motion vector estimation and improves about 0.05~0.74dB in terms of PSNR(Peak Signal to Noise Ratio).