약 가시성 다각형에서 최소 링크를 가진 최단 경비원 경로를 구하는 알고리즘

류상률,Ryu, Sang-Ryul 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5

2차원 평면상에 n개의 꼭지점을 가지며 서로 약 가시적인 2개의 체인으로 구성된 다각형을 약 가시적 다각형이라 한다. 본 논문에서는 약 가시적 다각형의 내부를 감시하는 최소 링크를 가진 경비원 경로들 중에서 최소 길이를 가지는 경비원 경로를 $O(n^2)$ 시간에 구하는 알고리즘을 제시한다. A weakly visible polygon is an n-gon in the plane and consists of two mutually weakly visible chains. In this paper, we present an $O(n^2)$ time algorithm that finds a shortest watchman route among the routes with minimum links where a watchman patrols the inside of weakly visible polygons.

특성 다각형에서 최소링크의 경비원 경로를 구하는 알고리즘

류상률,Ryu, Sang-Ryul 한국정보처리학회 2002 정보처리학회논문지 A Vol.9 No.4

다각형의 내부를 경로를 따라 이동하면서 감시하는 경비원 경로는 길이 또는 링크의 최소화 등으로 구분할 수 있다. 최소링크의 경비원 경로(watchman route with minimum route)는 경로 진행에서 발생하는 방향 전환의 횟수가 최소인 경비원 경로이다. 본 논문에서는 특성 다각형인 약 가시 다각형(weakly visible polygon)에서 최소링크의 경비원 경로를 구하는 $O(N^2)$시간 알고리즘을 제시한다. The watchman routes which an watchman patrols the interior of polygon moving along the route are classified to minimum length or minimum links. The watchman route with minimum links has minimum changes of direction in process. In this paper, we present an algorithm with $O(N^2)$ time for finding the watchman route with minimum links in the weakly visible polygons which have specific property.

단조 다각형에서 최단 경비원 경로를 구하는 알고리즘

류상률(Sang-Ryul Ryu),서대화(Dae-Hwa Seo),김승호(Sung-Ho Kim) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.3

다각형 내부의 최단 경비원 경로(shortest watchman route)는 경로 상에서 다각형 내부의 점들을 모두 볼 수 있는 최단 경로이다. 본 논문에서는 2차원 평면상에서 임의의 선분 l에 단조적이며 n개의 꼭 지점을 가진 2개의 체인(chain)으로 구성되는 단조 다각형(monotone polygon)의 최단 경비원 경로를 구하는 O(n) 시간과 O(n) 공간 복잡도의 알고리즘을 제시한다. The shortest watchman route in a polygon is the shortest route such that each point in the interior of the polygon is visible from at least one point along the route. In this paper, we present an O(n) time and O(n) space algorithm that find the shortest watchman route in a monotone polygon, which consists of n vertices and is a union of two chains with respect to l in the plane.

모바일 컴퓨팅 환경기반의 u-Campus 구성원 중심의 취업 서비스 모델

류상률(Ryu, Sang-Ryul),김혁진(Kim, Hyeock-Jin),이세열(Lee, Se-Yul) 한국산학기술학회 2008 한국산학기술학회논문지 Vol.9 No.5

최근 대학의 교육 환경은 교육 여건과 IT 인프라의 발전을 기반으로 많은 변화를 가져오고 있다. 특히 대학의 경쟁력 제고와 대학 이미지 개선을 목표로 중장기 발전계획을 도모하고 있다. 이를 실현하기 위한 단계적인 과정으로 유비쿼터스 캠퍼스를 구축하고 있으며, 교육 서비스의 확대와 IT 기술의 발전을 기반으로 다양한 서비스를 위한 콘텐츠 시스템을 구축하고 있다. 현재 구축되고 있는 서비스 환경은 실수요자들 위한 효율적인 서비스가 제공되지 못하고 있으며, 신기술의 도입이나 연구개발을 통한 테스트베드의 성격이나 원활한 서비스 운영에만 집중되어 있다. 또한 급변하는 대한 환경에서 새롭게 요구되고 있는 교육 콘텐츠 서비스에 대한 구성원 중심의 최적화된 모델을 구현하는데 한계가 있다. 본 논문에서는 대학 구성원 중심의 효율적인 유비쿼더스 캠퍼스 취업 서비스 모델을 제시한다. 제시한 모텔을 기반으로 유비쿼터스 캠퍼스 구축의 핵심요소인 구성원 중심의 U-리쿠르트, 캠퍼스 안내 모바일 서비스 등을 통하여 구성원이 실질적으로 필요로 하는 콘텐츠를 제공하는 유비쿼터스 캠퍼스 서비스 모델을 구성할 수 있다. Recently, the university environment has been changed faster than before. It has based on university environment and IT infrastructure. Especially, most of local university has devised development plan such as improving the image and competitive power of campus. Digital , Electronic and Mobile Campus has increased the importance as people realize that the use of technology can improve the learning process. U-Campus of latest IT Technology need a service environment of which the practical use is possible through IT analysis of the members. For example u-campus setup of mobile offers the convenience to the members. We expected thing to use much, even though actual condition investigation about IT environment of the user is insufficient. The inconvenience of mobile could not be activated to the service for proactive use. The importance became the result about u-campus service setup of a company and university center. This service environment cannot offer specific information of center members for which the service implements. In this paper, we studied about members centralized u-campus model through u-recruit, campus information mobile service on university.

약 가시성 다각형에서 최소 링크를 가진 최단 경비원 경로를 구하는 알고리즘

류상률(Sang-Ryul Ryu) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5·6

2차원 평면상에 n개의 꼭지점을 가지며 서로 약 가시적인 2개의 체인으로 구성된 다각형을 약 가시적 다각형이라 한다. 본 논문에서는 약 가시적 다각형의 내부를 감시하는 최소 링크를 가진 경비원 경로들 중에서 최소 길이를 가지는 경비원 경로를 O(n2) 시간에 구하는 알고리즘을 제시한다. A weakly visible polygon is an n-gon in the plane and consists of two mutually weakly visible chains. In this paper, we present an O(n2) time algorithm that finds a shortest watchman route among the routes with minimum links where a watchman patrols the inside of weakly visible polygons.

단조 다각형에서 최단 경비원 경로를 구하는 최적 알고리즘

류상률(Sang-Ryul Ryu),김승호(Sung-Ho Kim) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

경비원 경로(shortest watchman route) 문제는 계산 기하학(computational geometry)의 가시성(visibility) 분야에서 중요하게 다루고 있는 문제이다. 다각형에서 최단 경비원 경로는 경로상에서 다각형 내부의 점들을 모두 볼 수 있는 최단 경로이다. n개의 절점으로 구성된 단순(simple) 다각형의 경우에는 다각형 내부의 한 점 s가 경비원 경로의 출발점으로 주어졌을 때 최단 경비원 경로에 근사한 경비원 경로를 구하는 O(n⁴) 시간 복잡도의 알고리즘이 제시되어 있다. 임의의 선분 l에 단조적인 2개의 체인(chain)으로 구성될 수 있는 다각형을 단조(monotone) 다각형이라 한다. 본 논문에서는 n개의 절점으로 구성된 단조 다각형의 최단 경비원 경로를 구하는 O(n) 시간 복잡도와 O(n) 공간 복잡도를 가진 최적(optimal) 알고리즘을 제시한다.

단조 다각형에서 최소 개수의 링크를 가진 최단 경비원 경로를 구하는 선형 알고리즘

류상률(Sang-Ryul Ryu) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.11

n개의 꼭지점을 가진 단조(monotone) 다각형은 2차원 평면상의 임의의 선분에 단조 적인 2개의 체인으로 구성된다. 단조 다각형의 내부를 경로 상에서 모두 감시할 수 있는 최소 링크를 가진 경비원 경로(watchman route with minimum links)는 최소 개수의 선분으로 구성된 경로로서 하나 이상 존재할 수 있다. 본 논문에서는 단조 다각형의 최소 링크를 가진 경비원 경로들 중에서 최단 경비원 경로를 구하는 O(n) 시간의 알고리즘을 제시한다. A monotone polygon consists of n vertices and is a union of two monotone chains with respect to some line segment in the plane. A watchman route with minimum-links is a polygonal path such that each point in the interior of the polygon can be visible from at least one point along the route. There may be more than one watchman route with minimum links for given monotone polygon. In this paper, we present an algorithm with O(n) time that finds a shortest watchman route among the watchman routes with minimum links in a monotone polygon.

Quadtree를 사용한 색상 - 공간 특징과 객체 MBR의 질감 정보를 이용한 영상 검색

최창규(Chang-Gyu Choi),류상률(Sang-Ryul Ryu),김승호(Sung-Ho Kim) 한국정보과학회 2002 정보과학회 컴퓨팅의 실제 논문지 Vol.8 No.6

본 논문은 이미지에서 Quadtree를 이용한 색상-공간 특징 추출과 이미지 내에 포함되어 있는 객체의 MBR(Minimum Boundary Rectangle)을 구하여 질감 정보를 추출하는 방법을 제안한다. 제안된 방법은 각 이미지로부터 DC 이미지를 만들고 색상 좌표계를 변환한 후, Quadtree를 이용하여 영역을 분할한다. 영역의 분할 기준은 제안된 조건에 의하여 이루어지며, 각 분할된 영역으로부터 대표 색상을 추출한다. 그리고, 이미지 분할(segmentation)을 통하여 각 이미지의 객체, 객체를 포함한 배경, 또는 일부 배경의 MBR을 구하고, 제안된 알고리즘에 의하여 검색된 MBR의 웨이블릿 계수(wavelet coefficients)를 계산한다. 이 계수들이 MBR의 질감 정보가 되며, 추출된 색상-공간 정보와 질감 정보를 이용하여 제안된 유사도 계산 방법을 통하여 결과를 나타내게 된다. 제안된 방법은 원 이미지(original image)에 비해 특징 정보의 저장 공간을 53% 감소시켰으며, 성능은 유사하게 나타났다. 그리고, 질감 정보를 추가함으로써, 색상-공간 특징의 단점인 객체 정보의 손실을 보완하였고, 질의 이미지의 객체를 포함한 검색 결과를 보였다. In this paper, we present am image retrieval method based on color-spatial features using quadtree and texture information extracted from object MBRs in an image. The proposed method consists of creating a DC image from an original image, changing a color coordinate system, and decomposing regions using quadtree. As such, conditions are present to decompose the DC image, then the system extracts representative colors from each region. And, image segmentation is used to search for object MBRs, including object themselves, object included in the background, or certain background region, then the wavelet coefficients are calculated to provide texture information. Experiments were conducted using the proposed similarity method based on color-spatial and texture features. Our method was able to reduce the amount of feature vector storage by about 53%, but was similar to the original image as regards precision and recall. Furthermore, to make up for the deficiency in using only color-spatial features, texture information was added and the results showed images that included objects from the query images.

정확한 오브젝트 영역 추출을 위한 대칭성을 이용한 그림자 제거 방법

이정원(Jung Won Lee),류상률(Sang Ryul Ryu),장용석(Yong Seok Chang),김승호(Sung Ho Kim) 한국HCI학회 2005 한국HCI학회 학술대회 Vol.2005 No.1

Design of NePID using Anomaly Traffic Analysis and Fuzzy Cognitive Maps

김혁진(Kim, Hyeock-Jin),류상률(Ryu, Sang-Ryul),이세열(Lee, Se-Yul) 한국산학기술학회 2009 한국산학기술학회논문지 Vol.10 No.4

IT 시스템 기반의 네트워크 환경의 급속한 발전은 지속적인 연구방향의 중요한 이슈의 결과이다. 침입시도 탐지는 관심분야의 하나인 것이다. 최근에 다양한 기술을 기반으로 하는 침입시도탐지들이 제안되고 있으나 이러한 기술은 여러 형태의 침입시도의 패턴 중에 한가지 형태 및 시스템에 적용이 가능한 것이다. 또한 새로운 형태 침입시도를 탐지하지 못하고 있다. 그러므로 새로운 형태를 인식하는 침입탐지 관련 기술이 요구되어 지고 있다. 본 연구에서는 퍼지인식도와 비정상 트래픽 분석을 이용한 네트워크 기반의 침입탐지기법(NePID)을 제안한다. 이 제안은 패킷 분석을 통하여 서비스거부공격과 유사한 침입시도를 탐지하는 것이다. 서비스거부공격은 침입시도의 형태를 나타내며 대표적인 공격으로는 syn flooding 공격이 있다. 제안한 기법은 syn flooding을 탐지하기 위하여 패킷정보를 수집 및 분석한다. 또한 퍼지인식도와 비정상 트래픽 분석을 적용하여 판단모듈의 분석 결과를 토대로 기존의 서비스 거부 공격의 탐지 툴과의 비교분석을 하였으며 실험데이터로는 MIT Lincoln 연구실의 IDS 평가데이터 (KDD’99)를 이용하였다. 시뮬레이션 결과 최대평균 positive rate는 97.094% 탐지율과 negative rate는 2.936%을 얻었으며 이 결과치는 KDD’99 의 우승자인 Bernhard의 결과치와 유사한 수준의 값을 나타내었다. The rapid growth of network based IT systems has resulted in continuous research of security issues. Probe intrusion detection is an area of increasing concerns in the Internet community. Recently, a number of probe intrusion detection schemes have been proposed based on various technologies. However, the techniques, which have been applied in many systems, are useful only for the existing patterns of probe intrusion. They can not detect new patterns of probe intrusion. Therefore, it is necessary to develop a new Probe Intrusion Detection technology that can find new patterns of probe intrusion. In this paper, we proposed a new network based probe intrusion detector(NePID) using anomaly traffic analysis and fuzzy cognitive maps that can detect intrusion by the denial of services attack detection method utilizing the packet analyses. The probe intrusion detection using fuzzy cognitive maps capture and analyze the packet information to detect syn flooding attack. Using the result of the analysis of decision module, which adopts the fuzzy cognitive maps, the decision module measures the degree of risk of denial of service attack and trains the response module to deal with attacks. For the performance evaluation, the "IDS Evaluation Data Set" created by MIT was used. From the simulation we obtained the max-average true positive rate of 97.094% and the max-average false negative rate of 2.936%. The true positive error rate of the NePID is similar to that of Bernhard's true positive error rate.