OPKFDD 최소화를 위한 노드의 확장형 결정

정미경,황민,이귀상,김영철,Jung, Mi-Gyoung,Hwang, Min,Lee, Guee-Sang,Kim, Young-Chul 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.3

OPKFDD(Ordered Pseudo-Kronecker Functional Decision Diagram)는 각 노드에서 다양한 확장방법(decomposition)을 취할 수 있는 Ordered-DD(Decision Diagram)의 한 종류로서 각 노드마다 Shannon, positive Davio, 그리고 negative Davio 확장중의 하나를 사용하도록 하며 다른 종류의 DD와 비교해서 작은 수의 노드로 함수를 표현할 수 있다. 그러나 각 노드마다 각기 다른 확장 방법을 선택할 수 있는 특징 때문에 입력 노드에 대한 확장 방법의 결정에 의해서 OPKFDD의 크기가 좌우되며 최소의 노드 수를 갖는 OPKFDD의 구성은 매우 어려운 문제로 알려져 있다. 본 논문에서는 DD 크기의 기준을 노드 수로 하여 기존의 OBDD(Ordered Binary Decision Diagram) 자료구조에서 각 노드의 확장방법을 결정하는 직관적(heuristic)인 방법을 제시하고, 주어진 입력변수 순서에 대해서 각 노드의 확장 방법을 결정하는 알고리즘을 제안하고 실험 결과를 제시한다. OPKFDD (Ordered Pseudo-Kronecker Functional Decision Diagram) is one of ordered-DDs (Decision Diagrams) in which each node can take one of three decomposition types : Shannon, positive Davio and negative Davio decompositions. Whereas OBDD (Ordered Binary Decision Diagram) uses only the Shannon decomposition in each node, OPKFDD uses the three decompositions and generates representations of functions with smaller number of nodes than other DDs. However, this leads to the extreme difficulty of getting an optimal solution for the minimization of OPKFDD. Since an appropriate decomposition type has to be chosen for each node, the size of the representation is decided by the selection of the decomposition type. We propose a heuristic method to generate OPKFDD efficiently from the OBDD of the given function and the algorithm of the decision of decomposition type for a given variable ordering. Experimental results demonstrate the performance of the algorithm.

OPKFDD를 이용한 불리안 함수 표현의 최적화

정미경(Jung Mi Gyoung),이 혁(Lee Hyuck),이귀상(Lee Guee Sang) 한국정보처리학회 1999 정보처리학회논문지 Vol.6 No.3

DD(Decision Diagrams) is an efficient operational data structure for an optimal expression of boolean functions. In a graph-based synthesis using DD, the goal of optimization decreases representation space for boolean functions. This paper represents boolean functions using OPKFDD(Ordered Pseudo-Kronecker Functional Decision Diagrams) for a graph-based synthesis and is based on the number of nodes as the criterion of DD size. For a property of OPKFDD that is able to select one of different decomposition types for each node, OPKFDD is variable in its size by the decomposition types selection of each node and input variable order. This paper proposes a method for generating OPKFDD efficiently from the current BDD(Binary Decision Diagram) Data structures and an algorithm for minimizing one. In the multiple output functions, the relations of each function affect the number of nodes of OPKFDD. Therefore this paper proposes a method to decide the input variable order considering the above cases. Experimental results of comparing with the current representation methods and the reordering methods for deciding input variable order are shown.

Complex term을 이용한 OPKFDD의 입력변수 순서 방법

정미경(Mi Gyoung Jung),김미영(Mi Young kim),이귀상(Guee Sang Lee) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.9

OPKFDD(Ordered Pseudo-Kronecker Functional Decision Diagram)는 각 노드에서 다양한 decomposition을 취할 수 있는 Ordered-DD(Decision Diagram)의 한 종류이다. OBDD(Ordered Binary Decision Diagram)에서 각 노드는 Shannon decomposition만을 이용하는 반면, OPKFDD는 각 노드마다 Shannon, positive Davio, negative Davio decomposition 중의 하나를 사용하도록 하며 많은 경우 매우 적은 수의 노드로 함수를 표현할 수 있다. 그러나 각 노드마다 각기 다른 확장 방법을 선택할 수 있는 특징 때문에 입력 노드에 대한 확장 방법과 입력 변수 순서의 결정에 의해서 OPKFDD의 크기가 좌우되며 이에 대한 최적의 해를 구하는 것은 매우 어려운 문제로 알려져 있다. 본 논문에서는 DD 크기의 기준을 노드 수로 하여 기존의 BDD(Binary Decision Diagram) 자료구조에서 OPKFDD를 효율적으로 유도해내는 방법을 제시하고 complex term을 이용하여 이를 최소화하는 알고리즘을 제시한다. 그리고 입력변수 순서 결정을 위하여 다출력함수의 경우 함수간의 포함관계를 고려한 그룹-sifting과 각 노드의 확장 방법을 제안하고 실험 결과를 제시한다. OPKFDD(Ordered Pseudo-Kronecker Functional Decision Diagrams) is one of ordered-DDs(Decision Diagrams) in which each node can take one of the three decomposition types, Shannon, positive Davio and negative Davio in contrast to the OBDD(Ordered Binary Decision Diagram) which uses only Shannon decomposition in each node. In many cases it has been shown that OPKFDD can represent functions in more compact form than any other DDs, e.g. OBDD(Ordered Binary Decision Diagram). However, this leads to the very difficulty of getting an optimal solution in the minimization of OPKFDD. Since an appropriate decomposition type has to be chosen for each node, the size of the representation is decided by the selection of a decomposition type as well as a variable ordering of the diagram. We propose a method for generating OPKFDD efficiently from BDD(Binary Decision Diagram) of a given function with a group-sifting algorithm for the decision of a good variable ordering of multi-output functions using complex terms. Experimental results demonstrate the performance of the algorithm.

TDS 기법을 이용한 움직임 벡터 추정

김미영,정미경,Kim, Ki-Young,Jung, Mi-Gyoung 한국정보처리학회 2004 정보처리학회논문지B Vol.11 No.3

본 논문은 움직임 벡터를 보다 빠르고 정확하게 추정해나가는 탐색 방법으로 상 좌 우 3 방향을 고려한 TDS(T-Shape Diamond Search) 알고리즘을 제안하였다. 이 방법에서는 실제 움직임 벡터가 탐색 영역의 중심과 상ㆍ하 ㆍ좌 ㆍ우 방향에 집중되어 있는 특성을 이용하여 먼저 탐색 원점을 중심으로 상ㆍ하ㆍ좌ㆍ우 4 방향으로 탐색 점을 배치한 후 블록 정합을 실행한다 이들 중 정합 오차가 가장 삭은 지점을 기준점으로 상 방향으로 탐색 점을 확장하여 정합 오차를 측정해보고 기준점토다 오차가 작으면 계속 상 방향으로 확장해 나가고 그렇지 않으면 기준점을 충심으로 좌우 두 점 중 정합오차가 작은 점을 선택한다. 예측된 방향으로 위의 과정을 반복하며 움직임을 추정한다. 특히 움직임이 십자방향에 집중되는 영상의 경우 접근이 빠르고, 단계적으로 움직임 가능성이 낮은 부분을 탐색 대상에서 제외해 나감으로써 탐색이 비교적 빠르고 정확하게 이루어진다. 이 방법은 기존의 부분 최적 탐색 기법인 NTSS, DS, 그리고 HEXBS 등의 탐색법과 비교할 때 유사한 화질을 유지하면서도 탐색 점수에서는 평균 38%의 개선된 결과를 얻을 수 있었다. 특히 움직임이 적은 영상에서의 탐색 점수는 50%의 향상된 결과를 얻었다. In this paper, we proposed the TDS(T-shape Diamond Search) based on the directions of above, below, left and right points to estimate the motion vector fast and more correctly in this method, we exploit the facts that most motion vectors are enclosed in a circular region with a radius of 2 fixels around search center(0,0). At first, the 4 points in the above, below, left and right around the search center is calculated to decide the point of the MBD(Minimum Block Distortion). And then w. above point of the MBD is checked to calculate the SAD. If the SAD of the above point is less than the previous MBD, this process is repeated. Otherwise, the right and left points of MBD are calculated to decide The points that have the MBD between right point and left point. Above processes are repeated to the predicted direction for motion estimation. Especially, if the motions of image are concentrated in the crossing directions, the points of other directions are omitted. As a result, we can estimate motion vectors fast. Experiments show that the speedup improvement of the proposed algorithm over Diamond Search algorithm(DS) and HEXgon Based Search(HEXBS) can be up to 38∼50% while maintaining similar image Quality.

H.264/AVC에서 효율적인 정화소.부화소 움직임 추정

윤효순,김희숙,정미경,김미영,조영주,김기홍,이귀상,Yoon, Hyo-Sun,Kim, Hye-Suk,Jung, Mi-Gyoung,Kim, Mi-Young,Cho, Young-Joo,Kim, Gi-Hong,Lee, Guee-Sang 한국정보처리학회 2009 정보처리학회논문지B Vol.16 No.2

움직임 추정은 동영상 압축에서 영상 화질과 인코더 속도에 대하여 중요한 역할을 하지만, 많은 수행 시간을 요구한다. H.264/AVC에서 움직임 추정에 소요되는 수행 시간을 줄이면서 화질을 유지하기 위하여 본 논문에서는 정화소와 부화소 움직임 추정 기법을 제안하였다. 본 논문에서는 정화소 움직임 추정을 위하여 계층적인 탐색 기법을 사용하였고, 정확한 움직임 추정을 위하여 블록 크기에 따라 부화소 움직임 추정 패턴을 적응적으로 결정하였다. 제안한 정화소 움직임 추정 탐색 기법은 대칭적 십자가-엑스 탐색 패턴, 다중 사각형 탐색 패턴, 다이아몬드 탐색 패턴들로 이루어져 있다. 이 탐색 패턴들은 블록 움직임이 수직으로 크거나 블록 움직임이 크면서 규칙적인 영상에서 국부적 최소화 문제를 해결하고 움직임 추정에 소요되는 시간을 줄이기 위하여 탐색 영역 내에 탐색 점들을 규칙적, 대칭적으로 배치하였다. 제안한 부화소 움직임 추정 탐색 기법은 부화소 움직임 추정을 위하여 기존의 전역 부화소 탐색 패턴, 중앙 편향적 부화소 탐색 패턴과 제안한 부화소 움직임 탐색패턴들을 사용한다. 그리고 블록의 크기에 따라 3가지의 부화소 탐색 패턴들 중 한 패턴이 부화소 움직임 추정을 위해 적응적으로 결정된다. 블록의 크기에 따라 적응적으로 부화소 탐색 패턴이 결정되므로 보다 정확하게 부화소 움직임 추정을 수행할 수 있다. 제안한 기법을 전역 탐색 기법과 비교하였을 때 약 5.2배의 속도 향상을 가져왔으며, 영상 화질에 있어서 약 0.01 (dB)정도 성능 저하를 보였다. 반면에, 비대칭 다중육각형 탐색 기법과 비교하였을 때 움직임 추정 속도와 화질에 있어서 각각 약 1.2배와 약 0.02 (dB)정도 향상을 보였다. Motion estimation (ME) plays an important role in digital video compression. But it limits the performance of image quality and encoding speed and is computational demanding part of the encoder. To reduce computational time and maintain the image quality, integer pel and fractional pel ME methods are proposed in this paper. The proposed method for integer pel ME uses a hierarchical search strategy. This strategy method consists of symmetrical cross-X pattern, multi square grid pattern, diamond patterns. These search patterns places search points symmetrically and evenly that can cover the overall search area not to fall into the local minimum and to reduce the computational time. The proposed method for fractional pel uses full search pattern, center biased fractional pel search pattern and the proposed search pattern. According to block sizes, the proposed method for fractional pel decides the search pattern adaptively. Experiment results show that the speedup improvement of the proposed method over Unsymmetrical cross Multi Hexagon grid Search (UMHexagonS) and Full Search (FS) can be up to around $1.2{\sim}5.2$ times faster. Compared to image quality of FS, the proposed method shows an average PSNR drop of 0.01 dB while showing an average PSNR gain of 0.02 dB in comparison to that of UMHexagonS.

커널 추출을 이용한 저전력설계

이귀상(Guee-sang Lee),정미경(Mi-gyoung Jung) 대한전자공학회 1999 대한전자공학회 학술대회 Vol.1999 No.6