L_∞(L₁) 동적 디루니 삼각분할 방법

위영철,김하진,서상구,Wee, Youngcheul,Kimn, Hajine,Seo, Sangku 한국컴퓨터그래픽스학회 2000 컴퓨터그래픽스학회논문지 Vol.6 No.4

본 논문은 평면 위의 n 개의 점에 대한 $L_{\infty}(L_1)$ 거리의 동적 디루니 삼각분할을 구축하는 방법을 소개한다. 이 방법은 $L_{\infty}(L_1)$ 거리 상에서 사분면 근접 그래프가 디루니 삼각분할에 포함되고 디루니 삼각분할에 있는 각 삼각형의 최소한 한 선분이 사분면 근접 그래프에 포함됨을 발견하고 이를 이용하여 레인지 트리 방법으로 동적 디루니 삼각분할을 구축한다. 본 방법은 $L_1(L_{\infty})$ 거리의 디루니 삼각분할에서 삽입과 삭제를 한 점 당 $O(log^2n)$ amortized 시간과 O(log n)의 expected 시간에 처리한다. We introduce a new method for constructing a dynamic Delaunay triangulation for a set S of n sites in the plane under the $L_{\infty}(L_1)$ metric. We find that the quadrant neighbor graph is contained in the Delaunay triangluation and that at least one edge of each triangle in the Delaunay triangulation is contained in the quadrant neighbor graph. By using these observations and employing a range tree scheme, we present a method that dynamically maintains the $L_{\infty}(L_1)$ Delaunay triangulation under insertions and deletions in $O(log^2n)$ amortized time and O(log n) expected time.

L<SUB>∞</SUB>(L<SUB>1</SUB>) 동적 디루니 삼각분할 방법

위영철(Youngcheul Wee),김하진(Hajine Kimn),서상구(Sangku Seo) 한국컴퓨터그래픽스학회 2000 컴퓨터그래픽스학회논문지 Vol.6 No.4

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

위영철(Youngcheul Wee),김하진(Hajin Kimn) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.2Ⅰ

이 논문은 행렬탐색 방법을 이용하여 평면상의 n 개의 점에 대한 L_p, 1≤p≤∞ 거리의 양방향 각도제한 근접 점 문제를 θ(n log n) 시간에 계산하는 알고리즘을 고안한다. 이 방법은 최적의 시간 복잡도를 가지며 궤적추적 법을 쓰지 않기 때문에 구현이 용이하고 실용적이다.

블록 기반 영상 압축을 위한 부호화 결함 감소

위영철(Youngcheul Wee) 大韓電子工學會 2011 電子工學會論文誌-CI (Computer and Information) Vol.48 No.1

본 논문에서는 블록 이산 코사인 변환 (block discrete cosine transformation, BDCT) 부호화 영상에서 발생하는 구획화 결함 (blocking artifact)과 링잉 결함 (ringing artifact)을 제거하기 위하여 양방향 필터 (bilateral filter)를 이용한 새로운 후처리방법을 제안하였다. 양방향 필터에서 파라미터 선택은 필터링 결과에 큰 영향을 주는 중요한 문제로 본 논문에서는 양방향 필터의 파라미터를 효과적으로 선택하는 방법을 제시하였다. 실험 결과는 제안된 방법이 부호화 결함을 효과적으로 개선함을 PSNR, MSDS, SSIM의 수치로 보였다. In this paper, we propose a new post-processing technique that removes blocking and ringing artifacts in Block discrete cosine transformation (BDCT)-coded images using bilateral filtering. The selection of filter parameters is a key issue in the application of a bilateral filter because it significantly affects the result. An efficient method of selecting the bilateral filter parameters is presented. The experimental results show that the proposed approach alleviates the artifacts efficiently in terms of PSNR, MSDS, and SSIM.

디루니 삼각분할의 병렬처리 알고리즘

위영철(Youngcheul Wee),황시영(Seeyoung Hwang) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.2Ⅰ

본 논문은 영역별 근접 그래프 (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 Programmable Random Access Machine)에서 O(n)의 프로세서로 O(log n)의 병렬처리 시간에 L∞(L ₁) 디루니 삼각분할을 구축한다. 또한, 이 방법은 직선간의 교차점 계산 대신 거리비교를 하기 때문에 수치오차가 적고 구현이 용이하다.

고속 블록정합을 위한 수정된 다이아몬드 지역탐색 알고리즘

곽성근(Sung-Keun Kwak),위영철(Youngcheul Wee),김하진(Ha-Jine Kimn) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1A

본 논문에서는 현재 프레임 블록의 인접 블록으로부터 예측된 움직임 정보를 구하여, 이를 탐색 원점으로 하여 한 방향으로 진행하는 수정된 다이아몬드 지역 레이더 패턴으로 블록정합을 수행하는 수정된 다이아몬드 지역탐색 알고리즘을 제안한다. 실험 결과 제안된 방식은 기존의 방식들에 비해 PSNR 값에 있어서 평균적으로 0.02~0.37[dB] 개선되고 속도면에서 우수한 결과를 나타내었다. 또한 기존의 다이아몬드 지역탐색 알고리즘보다 탐색 속도면에서 14~24%의 성능향상을 보이면서 화질면에서는 거의 근접하게 나타났다. 제안된 방식은 정량적인 결과뿐만 아니라 부호화후 복호화한 영상의 화질에 있어서도 다른 고속 탐색 알고리즘보다 월등히 우수한 화질을 제공한다.

이전 프레임의 움직임 정보와 탐색 구간별 예측 후보점을 이용하는 블록 정합

곽성근(Sung-Keun Kwak),위영철(Youngcheul Wee),김하진(Ha-Jine Kimn) 한국정보과학회 2004 정보과학회 컴퓨팅의 실제 논문지 Vol.10 No.3

동영상의 현재 블록의 움직임 벡터와 이전 블록의 움직임 벡터는 시간적 상관성을 갖고 있다. 본 논문에서는 영상의 시간적인 특성과 움직임 벡터의 가운데 중심 분포 특성을 이용하는 예측 탐색 알고리즘을 제안한다. 제안된 알고리즘은 이전 프레임 블록으로부터 예측된 움직임 벡터와 분할된 탐색 구간에 속하는 후보 벡터 중에서 가장 작은 SAD 값을 갖는 점을 정확한 움직임 벡터를 찾기 위한 초기 탐색점 위치로 결정한다. 실험 결과 제안된 방식은 FS를 제외한 기존의 대표적인 고속 탐색 방식들에 비해 PSNR 값에 있어서 평균적으로 0.19~0.46dB 개선되고 영상에 따라 최고 1.06dB 정도 우수한 결과를 나타내었다. There is the temporal correlation of the video sequence between the motion vector of current block and the motion vector of previous block. In this paper, we propose the prediction search algorithm for block matching using the temporal correlation of the video sequence and the center-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 point on each search region. Simulation results show that PSNR(Peak-to-Signal Noise Ratio) values are improved up to the 1.06dB as depend on the video sequences and improved about 0.19~0.46dB on an average except the full search(FS) algorithm.

휴대장치를 위한 고속복원의 프로그램 코드 압축기법

김용관(Yongkwan Kim),위영철(Youngcheul Wee) 한국정보과학회 2010 정보과학회논문지 : 소프트웨어 및 응용 Vol.37 No.11

대부분의 휴대기기는 보조 기억장치로 NAND flash 메모리를 사용하고 있다. 또한, firmware의 크기를 줄이고 NAND flash로부터 주기억장치로 로딩하는 시간을 줄이기 위해서 압축된 코드를 NAND flash에 저장한다. 특히, 압축된 코드는 매우 빠르게 해제가 되어야 demand paging이 적용 가능하게 된다. 본 논문에서는 이를 위하여 새로운 사전식 압축 알고리즘을 제안한다. 이 압축방식은 기존의 LZ형식과는 다르게 현재 압축하고자 하는 명령어(instruction)가 참조된 명령어와 같지 않을 경우, 프로그램 코드의 명령어의 특성을 이용하여 두 명령어의 배타 논리합(exclusive or) 값을 저장하는 방식이다. 또한, 압축 해제 속도를 빠르게 하기 위해서, 비트 단위의 연산을 최소화한 압축형식을 제공한다. 실험결과 zlib과 비교해서 최대 5배의 압축해제 속도와 4%의 압축률 향상이 있었으며, 이와 같이 매우 빠른 압축해제 속도에 따라 부팅(booting) 시간이 10~20% 단축되었다. Most mobile devices use a NAND flash memory as their secondary memory. A compressed code of the firmware is stored in the NAND flash memory of mobile devices in order to reduce the size and the loading time of the firmware from the NAND flash memory to a main memory. In order to use a demand paging properly, a compressed code should be decompressed very quickly. The thesis introduces a new dictionary based compression algorithm for the fast decompression. The introduced compression algorithm uses a different method with the current LZ method by storing the “exclusive or” value of the two instructions when the instruction for compression is not equal to the referenced instruction. Therefore, the thesis introduces a new compression format that minimizes the bit operation in order to improve the speed of decompression. The experimental results show that the decoding time is reduced up to 5 times and the compression ratio is improved up to 4% compared to the zlib. Moreover, the proposed compression method with the fast decoding time leads to 10-20% speed up of booting time compared to the booting time of the uncompressed method.

휴대장치에서 압축된 프로그램 코드 갱신을 위한 새로운 압축기법

김태화(Taehwa Kim),위영철(Youngcheul Wee) 한국정보과학회 2011 정보과학회논문지 : 소프트웨어 및 응용 Vol.38 No.2

본 논문은 압축된 프로그램 코드를 무선으로 갱신(CFOTA: Compressed Firmware Over The Air) 하는데 사용되는 새로운 압축기법을 소개한다. CFOTA에서 갱신에 사용되는 차이정보(delta)는 송신비용을 줄이기 위하여 크기가 작아야 하고, 빠른 갱신 및 시스템의 성능을 위하여 복원 및 압축 속도가 빨라야 한다. 일반적으로 차이정보의 크기는 비 압축 프로그램 코드 간에서 보다 비트단위로 코딩 된 압축 프로그램 코드 간에서 아주 크게 된다. 따라서, 대부분의 CFOTA 방법은 차이정보를 비 압축 프로그램 코드기준으로 만든다. 갱신 과정은, 먼저 구 버전 압축 프로그램 코드를 압축해제 하고, 차이정보를 가지고 갱신한 다음, 갱신된 새 버전을 재 압축한다. 이 방법은 차이정보의 크기는 증가시키지 않으나 압축해제와 재압축에 따라 갱신시간이 대폭 증가하게 된다. 본 논문에서는 차이정보를 압축된 프로그램 코드 간에서 구하여 압축해제 및 재 압축을 하지 않는 방법에서 차이정보의 크기가 늘어나는 것을 대폭 완화하는 방법을 제안한다. 실험결과 zlib 대비 차이정보가 20배 이상 줄어들고 갱신속도가 약 6배 향상되었다. This paper presents a new code compression method for the wireless update of compressed firmware so called Compressed Firmware Over The Air (CFOTA) on the hand held devices. CFOTA requires a small delta that minimizes the amount of update data and an efficient compressed method that provides fast encoding and decoding to achieve fast extracting and updating. The delta between bitwise coded compressed versions of firmware is normally much larger than that between uncompressed versions of firmware. Consequently, most of CFOTA methods make a delta for uncompressed versions. The update process first decompress compressed old versions, and then update uncompressed old versions and finally recompress new versions. This method does not increase the size of delta, however, it increases the update time significantly due to decoding and encoding are involved additionally. Our new code compression method that significantly decreases the delta size between compressed programs by which decompression and recompression are avoided. Experimental results show that the delta size is decreased by about 20 times and the update time is reduced about 6 times compared to zlib.

이전 프레임의 시공간 모션 정보에 의한 예측 탐색 알고리즘

곽성근(Sung-Keun Kwak),위영철(Youngcheul Wee),김하진(Ha-Jine Kimn) 한국컴퓨터그래픽스학회 2003 컴퓨터그래픽스학회논문지 Vol.9 No.3