이미지 시퀀스 데이터베이스에서의 유사성 기반 서브시퀀스 검색

김인범,박상현,Kim, In-Bum,Park, Sang-Hyun 한국정보처리학회 2003 정보처리학회논문지D Vol.10 No.3

본 논문은 다차원 타임 워핑 거리 함수를 이용하여 유사한 이미지 서브시퀀스를 신속하게 검색할 수 있는 색인 방법을 제안한다. 타임 워핑 거리는 시퀀스들의 길이가 다르거나 샘플링 비율이 다른 많은 응용에서 Lp 거리보다 더욱 적합하다. 우리가 제안한 색인 방법은 디스크 기반의 접미어 트리를 색인 구조체로 채택하고, 유사하지 않은 서브시퀀스를 잘못된 누락 없이 잘 여과하기 위해 하한 거리 함수를 사용한다. 이 방법은 특정 차원의 상대적 가중치를 손쉽게 부여하기 위해 정규화를 적용하고 색인 트리를 압축하기 위해 이산화 과정을 수행한다. 메디컬 이미지와 합성 이미지 시퀀스를 대상으로 한 실험은 본 논문에서 제안한 방법이 naive한 방법보다 우수한 성능을 보이고 대용량의 이미지 시퀸스 데이터베이스로의 확장이 용이함을 입증한다. This paper proposes an indexing technique for fast retrieval of similar image subsequences using the multi-dimensional time warping distance. The time warping distance is a more suitable similarity measure than Lp distance in many applications where sequences may be of different lengths and/or different sampling rates. Our indexing scheme employs a disk-based suffix tree as an index structure and uses a lower-bound distance function to filter out dissimilar subsequences without false dismissals. It applies the normaliration for an easier control of relative weighting of feature dimensions and the discretization to compress the index tree. Experiments on medical and synthetic image sequences verify that the proposed method significantly outperforms the naive method and scales well in a large volume of image sequence databases.

EGOSST를 이용한 이동 경로의 가중치를 반영한 효과적 연결

김인범,Kim, In-Bum 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.5

In this paper, a mechanism connecting all weighted migration routes with minimum cost with EGOSST is proposed. Weighted migration routes may be converted to weighted input edges considered as not only traces but also traffics or trip frequencies of moving object on communication lines, roads or railroads. Proposed mechanism can be used in more wide and practical area than mechanisms considering only moving object traces. In our experiments, edge number, maximum weight for input edges, and detail level for grid are used as input parameters. The mechanism made connection cost decrease average 1.07% and 0.43% comparing with the method using weight minimum spanning tree and weight steiner minimum tree respectively. When grid detail level is 0.1 and 0.001, while each execution time for a connecting solution increases average 97.02% and 2843.87% comparing with the method using weight minimum spanning tree, connecting cost decreases 0.86% and 1.13% respectively. This shows that by adjusting grid detail level, proposed mechanism might be well applied to the applications where designer must grant priority to reducing connecting cost or shortening execution time as well as that it can provide good solutions of connecting migration routes with weights. 본 논문에서는 EGOSST를 이용하여 가중치를 갖는 이동 경로들을 최소 비용으로 모두 연결하는 방법을 제안한다. 이동 경로는 가중치 선분으로 변환될 수 있는데, 이것은 통신선, 도로 및 철도망에서의 동적 궤적뿐 만 아니라, 가중치인 이동 량이나 통행 빈도를 포함한다. 제안되는 방법은 단순한 위치 정보만을 고려하여 처리하는 방법에 비해 더 광범위하고 유용한 분야에 응용이 가능할 것이다. 입력 선분의 수, 각 선분 가중치의 최대 크기, 그리고 그리드 정밀도를 입력 인자로 설정한 실험에서, 본 논문에서 제안된 방법은 가중치 최소 신장 트리를 이용한 방법과 비교할 때, 연결 비용은 평균 1.07%, 가중치 스타이너 최소 트리 방법에 비해서는 평균 0.43% 감소하였다. 또한 그리드 정밀도를 0.1과 0.001로 했을 경우, 가중치 최소 신장 트리 방법에 비해 실행 시간이 각각 평균 97.02%, 2843.87% 증가했으나, 연결 비용은 각각 평균 0.86%, 1.13% 감소되었다. 이는 제안된 방법이 가중치를 반영한 이동 경로의 효과적 연결 뿐 아니라, 그리드 정밀도를 조절하여 생성 시간과 비용 절감 율을 응용 분야에 맞추어 사용될 수 있음을 보인다.

최소 신장 트리를 이용한 센서 네트워크의 효과적인 구성

김인범,Kim, In-Bum 한국컴퓨터산업학회 2009 컴퓨터産業敎育學會論文誌 Vol.10 No.3

본 논문은 센서 네트워크를 구성하는 센서노드와 베이스 스테이션들을 제한 길이 간선 최소 신장 트리를 이용하여 신속하고 효과적으로 연결하는 방법을 제안한다. 이 방법은 센서 네트워크에서 라우팅 등에 활용될 수 있는 연결 트리를 신속하게 구축한다. 2000개 입력 노드 대상의 실험에서, 제안된 방법은 단순 최소 신장 트리 방법과 비교하여 네트워크 길이의 증가 없이 네트워크 구축 시간을 94.7% 단축하였다. 이것은 제안된 방법이 센서 네트워크를 신속히 구축해야 하는 응용 등에 잘 적용될 수 있음을 보인다. This paper proposes a mechanism for prompt and efficient construction of sensor network connecting sensor nodes and base stations using limited length edges minimum spanning tree. This mechanism can rapidly build a connecting tree which may be used in routing of sensor network. In an experiment for 2000 input terminal nodes, this mechanism can curtail 94.7% construction time comparing with the method by naive minimum spanning tree without tree length overheads. This shows the proposed mechanism can apply well to the application of swift construction of a sensor network.

GOSST 문제 해결을 위한 지그재그 스타이너 포인트 배치 방법을 이용한 휴리스틱의 제안

김인범,김재각,Kim, In-Bum,Kim, Chae-Kak 한국정보처리학회 2007 정보처리학회논문지 A Vol.14 No.5

본 논문에서 GOSST(Grade of Services Steiner Minimum Tree) 문제에 대한 개선된 휴리스틱을 제안한다. GOSST 문제는 스타이너 포인트 문제의 한 변형으로 G-Condition을 만족하는 최소비용의 네트워크 구성을 찾는 문제이며, NP-Hard 혹은 NP-Complete 문제로 알려져 있다. 이 문제에 대한 이전의 연구에서 우리는 거리 우선 최소 신장 트리 생성방법과 직접 스타이너 포인트 배치 방법을 결합한 휴리스틱을 제안했었다. 본 논문에서는 스타이너 포인트 배치 방법으로 지그재그 스타이너 포인트 배치방법을 새롭게 제안한다. 이 방법과 거리우선 최소 신장 트리 생성 방법을 결합한 거리 지그재그 GOSST 휴리스틱은 컨트롤인 G-MST에 비해 31.5%의 네트워크 구축 비용의 절감을 얻었고 이전의 가장 좋은 GOSST 휴리스틱인 거리 직접 GOSST 휴리스틱에 비해 2.2%의 비용 개선을 보였다. We propose more enhanced heuristic for the GOSST(Grade of Services Steiner Minimum Tree) problem in this paper. GOSST problem is a variation of Steiner Tree problem and to find a network topology satisfying the G-Condition with minimum network construction cost. GOSST problem is known as one of NP-Hard or NP-Complete problems. In previous our research, we proposed a heuristic employing Direct Steiner Point Locating strategy with Distance Preferring MST building strategy. In this paper, we propose new Steiner point locating strategy, Zigzag Steiner point Locating strategy. Through the results of out experiments, we can assert this strategy is better than our previous works. The Distance Zigzag GOSST method which hires the Distance Preferring MST building strategy and Zigzag Steiner point Locating strategy defrays the least network construction cost and brings 31.5% cost saving by comparison to G-MST, the experimental control and 2.2% enhancement by comparison to the Distance Direct GOSST method, the best GOSST method in our previous research.

근사 최소 스타이너 트리를 이용한 효율적인 클러스터 센서 네트워크의 구성

김인범,Kim, In-Bum 한국정보처리학회 2010 정보처리학회논문지 A Vol.17 No.2

클러스터 센서 네트워크는 여러 개의 중심 노드 주위에 다른 입력 노드들이 밀집된 분포를 보이는 센서 네트워크이다. 최소 스타이너 트리는 스타이너 포인트들을 도입하여 모든 입력 노드들을 최소 비용으로 연결하는 트리이다. 본 논문에서는 센서 노드와 베이스 스테이션의 연결인 간선들을, 클러스터 내에서와 클러스터 사이에서 각각 생성하고, 이를 이용하여 근사 최소 스타이너 트리를 반복적으로 생성하여, 단축된 길이의 클러스터 센서 네트워크를 구성하는 방법을 제안한다. 실행 시간 복잡도가 O($N^2$)인 제안된 방법으로 생성된 클러스터 센서 네트워크들은, 본 논문의 실험에서 유클리드 최소 신장 트리 방법의 네트워크들과 비교하여 생성 시간이 1170.5% 증가하였으나 최소치보다 0.1% 증가된 길이의 네트워크는 20.3%의 증가된 시간에 생성이 가능했다. 이 클러스터 센서 네트워크의 평균 길이는 유클리드 최소 신장 트리 방법과 비교하여 최대 3.7%, 평균 1.9% 감소되었다. Cluster sensor network is a sensor network where input nodes crowd densely around some nuclei. Steiner minimum tree is a tree connecting all input nodes with introducing some additional nodes called Steiner points. This paper proposes a mechanism for efficient construction of a cluster sensor network connecting all sensor nodes and base stations using connections between nodes in each belonged cluster and between every cluster, and using repetitive constructions of approximate Steiner minimum trees. In experiments, while taking 1170.5% percentages more time to build cluster sensor network than the method of Euclidian minimum spanning tree, the proposed mechanism whose time complexity is O($N^2$) could spend only 20.3 percentages more time for building 0.1% added length network in comparison with the method of Euclidian minimum spanning tree. The mechanism could curtail the built trees' average length by maximum 3.7 percentages and by average 1.9 percentages, compared with the average length of trees built by Euclidian minimum spanning tree method.

선분상의 포탈을 이용한 근사 선분 최소 신장 트리의 생성

김인범,김수인,Kim, In-Bum,Kim, Soo-In 한국정보처리학회 2009 정보처리학회논문지 A Vol.16 No.6

본 논문에서는 입력 선분들 상에 위치하며, 이들을 일정한 길이로 분할하는 가상 노드 포탈을 이용하여 입력 선분들을 모두 연결하는 근사 선분 최소 신장 트리를 빠른 시간 내에 찾는 방법을 제안한다. 이 근사 선분 최소 신장 트리는 통신선, 도로 및 철도망의 연결 등에 활용될 수 있다. 3000개의 입력 선분에 대해 제안된 방법으로 생성된 근사 트리는, 포탈 간격이 0.3인 경우에 최적 선분 최소 신장 트리와 비교하여 1.8% 의 길이가 증가한 반면에 트리 생성 시간은 29.74%의 감소를 보였고, 0.75의 경우 2.96%의 길이의 증가와 39.96%의 트리 생성 시간의 절감을 보였다. 이는 약간의 길이 증가를 허용하면서 짧은 시간 내에 선분 연결 트리를 생성해야 하는 응용에 잘 적용될 수 있음을 보인다. 또한 제안 된 방법은 포탈 간격, 포탈 포기 비율 등을 외부 인자로서 조절하여, 목적에 따른 트리 길이 또는 트리 생성 시간에 중점을 둔 근사 선분 최소 신장 트리 생성이 가능함을 보인다. In this paper, a mechanism that produces an approximation edges minimum spanning tree swiftly using virtual nodes called portals dividing given edges into same distance sub-edges. The approximation edges minimum spanning tree can be used in many useful areas as connecting communication lines, road networks and railroad systems. For 3000 random input edges, when portal distance is 0.3, tree building time decreased 29.74% while the length of the produced tree increased 1.8% comparing with optimal edge minimum spanning tree in our experiment. When portal distance is 0.75, tree building time decreased 39.96% while the tree length increased 2.96%. The result shows this mechanism might be well applied to the applications that may allow a little length overhead, but should produce an edge connecting tree in short time. And the proposed mechanism can produce an approximation edge minimum spanning tree focusing on tree length or on building time to meet user requests by adjusting portal distance or portal discard ratio as parameter.

GOSST 문제에 대한 전역적 배치와 지역적 배치 휴리스틱의 개선을 위한 G-Node와 단절에 관한 연구

김인범,김재각,Kim, In-Bum,Kim, Chae-Kak 한국통신학회 2007 韓國通信學會論文誌 Vol.32 No.9b

GOSST 문제에 대한 이전 휴리스틱의 성능 개선을 위한 새로운 제안이 본 논문에서 제시된다. 이 문제는 다양한 등급의 서비스를 제공할 수 있는 통신 네트워크의 설계 등에 적용될 수 있다. GOSST 문제는 G-Condition을 만족하는 최소 구축비용의 네트워크를 찾는 것으로 NP-HARD 문제에 포함된다. 우리는 이전의 연구에서 이 문제와 관련된 두개의 휴리스틱을 발표하였다. 본 연구에서는 스타이너 트리 생성 시 이용되는 G-Node와 제거되는 에지의 선택 방법을 제안하고, 이를 기존의 휴리스틱에 접목한 새로운 휴리스틱을 구현한다. 실험 결과는 이 휴리스틱이 이전 것에 비해 우수함을 나타내는데, 새 지역적 배치 휴리스틱은 17%, 새 전역적 배치 휴리스틱은 14%의 네트워크 구축비용 절감비율의 증가를 보였다. This paper is on the enhancement of our heuristics for GOSST problem that could apply to the design of communication networks offering graduated services. This problem hewn as one of NP-Hard problems finds a network topology meeting the G-Condition with minimum construction cost. In our prior research, we proposed two heuristics. We suggest methods of selecting G-Node and disconnections for Global or Local locating heuristic in this research. The ameliorated Local locating heuristic retrenches 17% more network construction cost saving ratio and the reformed Global locating heuristic does 14% more than our primitives.

효과적인 위치 기반 이동 노드 밀집도 계산방법

김인범(In-bum Kim),서춘원(Choon-weon Seo) 한국통신학회 2015 韓國通信學會論文誌 Vol.40 No.11

Analog Dimming을 이용한 Single-stage LED 구동 회로

김인범(In-Bum Kim),박규민(Kyu-Min Park),한상규(Sang-Kyoo Han),홍성수(Sung-Soo Hong),김현정(Hyun-Jung Kim),이상훈(Sang-Hoon Lee),이효범(Hyo-Bum Lee),이광일(Kwang-Il Lee),노정욱(Chung-Wook Roh) 전력전자학회 2008 전력전자학술대회 논문집 Vol.- No.-

현재 폭넓은 시장을 형성하고 있는 LED는 전 세계적으로 이슈화 되고 있는 친환경 조명기기로 각광받고 있으며, 향후 조명 산업의 50% 이상 시장 점유율을 차지할 것으로 예상된다. 본 논문에서는 Analog Dimming을 이용하여 Single-stage LED 구동 회로를 제안한다. 제안된 회로는 기존 방식과 달리 DC/DC단이 없으므로 가격 경쟁력 및 높은 전력 변환 효율을 확보할 수 있고, 고조파 규제 만족을 위한 역률 보정 기능이 있으며 휘도를 선형적으로 제어할 수 있는 Analog Dimming 기능을 가지고 있다. 최종적으로 제안된 Single-stage LED 구동 회로의 동작 및 Analog Dimming 제어 기법을 소개하고, 시뮬레이션 및 40W급 시작품을 제작, 동작 실험을 통하여 그 타당성을 검증한다.

검도수련생의 도장 선택 요인 차이 분석

김인범(In-Bum Kim),전찬수(Chan-Soo Jun) 대한검도학회 2006 대한검도학회지 Vol.22 No.1

이 연구는 효율적인 검도장 경영을 위한 검도 수련자의 도장 선택요인 차이를 규명하는데 그 목적이 있다. 본 연구의 목적을 달성하기 위하여 한 국사회인 검도대회에 참가한 선수 512(85.3%)명을 편의표본추출방법(Convenience Sampling Method)을 이용하여 연구대상으로 선정하였다. 자료 수집을 위한 측정도구는 설문지로 요인분석을 이용하여 타당도 검증을 하였으며, Cronbach’s α 값은 .650~.889로 나타나 신뢰할 만한 설문지로 판단되어 사용하였다. 자료 분석을 위한 통계기법으로는 SPSS 12.0 통계프로그램을 이용하여 기술통계분석, 요인분석, 독립 t 검증, 일원변량분석을 실시하였다. 이와 같은 연구 절차에 따라 자료를 분석한 결과 인구통계학적 특성에 따른 검도장 선택 시 요인의 중요도 차이에서는 수련 장소에 따라 시설이 도장 선택에 차이가 있는 것으로 나타났으나 성별, 연령, 검도 단급에서는 유의한 차이가 나타나지 않았다. The purpose of this study was to examine the difference in selective factors of Kumdo academy for efficient management. 512 Kumdo players were drawn convenience sampling method from the participants of the 13th Korea Recreational Kumdo Competition. The research method used in this study was questionnaire. Cronbach’s alpha revealed the high internal consistency of the questionnaire (.650 ~ .889) and the factor analysis supported the content validity. To analyze the data, SPSS v12.0 program was used for descriptive statistics, factor analysis, independent t-test and one-way ANOVA. The results were as follows: According to demographic variables, there was a difference in facilities; however there were no differences in gender, age, and level(DAN) in the difference in selective factors of Kumdo academy.