차량 경로 스케줄링 문제 해결을 위한 개미 군집 최적화 휴리스틱

홍명덕,유영훈,조근식,Hong, Myung-Duk,Yu, Young-Hoon,Jo, Geun-Sik 한국정보처리학회 2010 정보처리학회논문지B Vol.17 No.5

차량 경로 스케줄링 문제(VRSPTW, the Vehicle Routing and Scheduling Problem with Time Window)는 여러 고객의 시간 제약과 요구량을 만족시키면서 최소 이동 비용을 가지는 경로를 구성하는 문제이다. 이 문제는 NP-Hard 문제이기 때문에 해를 산출하는데 시간이 오래 걸린다. 본 연구는 VRSPTW를 빠른 시간 내에 최근사해를 구하기 위한 멀티 비용 함수(Multi Cost Function)를 갖는 개미 군집 최적화(Ant Colony Optimization)을 이용한 휴리스틱을 제안하였다. 멀티 비용 함수는 각 개미가 다음 고객 노드로 이동하기 위해 비용을 평가할 때 거리, 요구량, 각도, 시간제약에 대해 서로 다른 가중치를 반영하여 우수한 초기 경로를 구할 수 있도록 한다. 본 연구의 실험결과에서 제안된 휴리스틱이 Solomon I1 휴리스틱과 기회시간이 반영된 하이브리드 휴리스틱보다 효율적으로 최근사 해를 얻을 수 있음을 보였다. The Vehicle Routing and Scheduling Problem with Time Windows(VRSPTW) is to establish a delivery route of minimum cost satisfying the time constraints and capacity demands of many customers. The VRSPTW takes a long time to generate a solution because this is a NP-hard problem. To generate the nearest optimal solution within a reasonable time, we propose the heuristic by using an ACO(Ant Colony Optimization) with multi-cost functions. The multi-cost functions can generate a feasible initial-route by applying various weight values, such as distance, demand, angle and time window, to the cost factors when each ant evaluates the cost to move to the next customer node. Our experimental results show that our heuristic can generate the nearest optimal solution more efficiently than Solomon I1 heuristic or Hybrid heuristic applied by the opportunity time.

차량 경로 스케줄링 문제 해결을 위한 멀티 비용 함수를 갖는 개미 군집 최적화 기법 기반의 휴리스틱

홍명덕 ( Myung-duk Hong ),유영훈 ( Young-hoon Yu ),조근식 ( Geun-sik Jo ) 한국정보처리학회 2010 한국정보처리학회 학술대회논문집 Vol.17 No.1

본 연구는 차량 경로 스케줄링 문제(VRSPTW, the Vehicle Routing and Scheduling Problem with Time Window)를 해결하기 위하여, 멀티 비용 함수(Multi Cost Function)를 갖는 개미 군집 최적화(Ant Colony Optimization)을 이용한 휴리스틱을 제안하였다. 멀티 비용 함수는 각 개미가 다음 고객 노드로 이동하기 위해 비용을 평가할 때 거리, 요구량, 각도, 시간제약에 대해 서로 다른 가중치를 반영하여 우수한 초기 경로를 구할 수 있도록 한다. 본 연구의 실험결과에서 제안된 휴리스틱이 Solomon I1 휴리스틱과 기회시간이 반영된 하이브리드 휴리스틱보다 효율적으로 최근사 해를 얻을 수 있음을 보였다.

개인화된 뉴스 서비스를 위한 소셜 네트워크 기반의 콘텐츠 추천기법

홍명덕(Myung-Duk Hong),오경진(Kyeong-Jin Oh),가명현(Myung-Hyun Ga),조근식(Geun-Sik Jo) 한국지능정보시스템학회 2013 지능정보연구 Vol.19 No.3

세계에는 수많은 사람들이 살아가고 있고, 사람들의 일상으로부터 매일, 매 시간 단위로 새로운 뉴스가 발생한다. 발생되는 뉴스는 예정된 일과 예상하지 못한 일들을 포함하고 있다. 발생하는 뉴스의 거대한 양과 이를 전달하는 수많은 미디어들로 인해 사람들은 뉴스 콘텐츠를 이용하는데 많은 시간을 소비하게 된다. 하지만 미디어에 시시각각 나타나는 속보와 실시간 이슈의 대부분이 가십 기사로 이루어져 있어 사용자들이 자신의 성향에 맞는 뉴스를 선별하고, 뉴스로부터 정보를 획득하는 것은 쉽지 않은 일이다. 또한 사용자의 관심사가 시간에 따라 변하기 때문에 뉴스 제공에 있어 사용자의 변하는 관심사를 반영하는 것이 요구된다. 본 논문에서는 사용자의 최근 관심사를 기반으로 사용자 선호도에 맞는 뉴스를 제공하기 위한 콘텐츠 기반의 추천 기법 및 시스템을 제안한다. 사용자의 최근 선호도를 파악하기 위하여 소셜 네트워크 서비스인 Facebook 사용자의 정보와 최근 게시글을 이용하여 동적으로 사용자 프로파일을 생성하여 이를 뉴스 서비스에 활용하고, 사용자 선호도에 적합한 뉴스를 추출하기 위해서 뉴스 콘텐츠의 분석을 요구한다. 뉴스 콘텐츠 분석을 위해 미디어에서 제공되는 뉴스의 카테고리를 사용하고, 뉴스 방송원고의 분석 및 주요 키워드 추출을 통해 뉴스 프로파일을 생성한다. 사용자 프로파일과 뉴스 프로파일 간의 유사도 측정을 위해서는 두 프로파일 간 형식의 일치화가 요구되므로 사용자 프로파일을 뉴스 프로파일과 동일한 형태로 생성한다. 사용자가 시스템에 접속하면 시스템은 사용자 프로파일에 명시된 선호도를 기반으로 뉴스 프로파일과의 유사도를 측정하고, 사용자 선호도에 가장 적합한 뉴스들을 제공하게 된다. 또한 사용자에게 제공된 뉴스 프로파일과 다른 뉴스 프로파일들 간에 유사도를 측정하여 유사도가 높은 관련된 뉴스들을 제공하게 된다. 제안한 개인화된 뉴스 서비스의 성능을 평가하기 위해 사용자에게 추천된 뉴스에 대한 사용자 평가와 시스템 예측값의 오차를 기반으로 6Sub-Vectors 벤치마크 알고리즘과 성능 평가를 수행하였고, 실험 결과를 통해 제안한 시스템의 우수성을 입증하였다.

Freebase 기반의 추천 시스템 시각화

홍명덕(Myung-Duk Hong),하인애(Inay Ha),조근식(Geun-Sik Jo) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.10

본 논문에서는 영화 추천을 위해 사용자들이 명시적으로 표시한 신뢰 정보를 이용하여 소셜 네트워크와 유사하게 신뢰 네트워크를 생성하고, 그 사용자들의 연결 정도를 이용하여 추천 시스템에 적용하며, 추천 정보는 시각화 방법을 이용하여 제공하는 방법을 제안한다. 이를 통해 사용자가 명시적으로 신뢰 관계를 표현한 신뢰 네트워크에서 숨겨진 신뢰 관계를 추론한다. 시각화된 추천 정보는 영화, 음악, 인물 등 다양한 토픽에 대한 정보를 구조화된 형태로 제공하는 Freebase를 이용하였으며, 시각화 방법은 다음 3가지와 같다. (1) 사용자가 제공받고자 하는 영화의 수만큼 영화 포스터로 시각화하고, (2) 추천된 영화 중 특정 영화를 선택하면 영화 감독, 주연 배우, 장르 등의 부가적인 정보를 시각화하여 제공한다. 마지막으로 (3) 신뢰 기반의 사용자들 중 임의로 몇 명을 이웃 사용자로 선택하여 추천한다. 본 논문에서는 시각화 방법을 적용함으로써 추천 수 또는 이웃 사용자의 수, 그리고 부가 정보 요청 등 사용자의 의견(요구)을 바탕으로 추천하기 때문에 사용자의 의사결정 능력을 향상시킬 수 있다. 뿐만 아니라 본 논문에서 제안하는 추천 시각화 방법을 통해 동적으로 사용자들의 요구를 반영할 수 있고, Freebase, LinkedMDB, 위키피디아 등 현존하는 LOD의 정보 재사용을 통해 보다 풍부하게 추천 정보를 제공할 수 있다. In this paper, the proposed movie recommender system constructs trust network, which is similar to social network, using user's trust information that users explicitly present. Recommendation on items is performed by using relation degree between users and information of recommended item is provided by a visualization method. We discover the hidden relationships via the constructed trust network. To provide visualized recommendation information, we employ Freebase which is large knowledge base supporting information such as movie, music, and people in structured format. We provide three visualization methods as the followings: i) visualization based on movie posters with the number of movies that user required. ii) visualization on extra information such as director, actor and genre and so on when user selected a movie from recommendation list. iii) visualization based on movie posters that is recommended by neighbors who a user selects from trust network. The proposed system considers user's social relations and provides visualization which can reflect user's requirements. Using the visualization methods, user can reach right decision making on items. Furthermore, the proposed system reflects the user's opinion through recommendation visualization methods and can provide rich information to users through LOD(Linked Open Data) Cloud such as Freebase, LinkedMDB and Wikipedia and so on.

효율적인 상품등록을 위한 워드넷 기반의 오픈마켓 카테고리 검색 시스템

홍명덕(Myung-Duk Hong),김장우(Jang-Woo Kim),조근식(Geun-Sik Jo) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.9

여러 오픈마켓에서 판매자가 동일한 상품을 등록할 시에 각 오픈마켓마다 다른 기준으로 제공되는 카테고리로 인하여 카테고리 선정에 어려움이 발생한다. 본 논문에서는 판매자가 오픈마켓에서 상품 등록 시 다른 오픈마켓에서 기 판매하고 있는 상품의 카테고리와 의미적으로 가장 연관성이 높은 카테고리를 추천하는 방법을 제안한다. 이때 입력받은 카테고리를 의미 분석하는 방법으로 형태소 분석, Wiki 낱말사전, WordNet, Google 번역 서비스를 사용하여 추출된 색인어로 카테고리를 검색한 후, 의미적 연관성 측정을 통하여 가장 의미가 비슷한 카테고리를 추천하는 방법이다. 실험 결과로 색인어 기반의 검색방법 보다 제안하는 의미분석 검색방법이 정확한 검색결과를 보여주어 시스템의 신뢰도를 향상시켰으며, 카테고리를 선택하는데 드는 시간비용을 절감해주는 것을 보인다. Open Market is one of the key factors to accelerate the profit. Usually retailers sell items in several Open Market. One of the challenges for retailers is to assign categories of items with different classification systems. In this research, we propose an item category recommendation method to support appropriate products category registration. Our recommendations are based on semantic relation between existing and any other Open Market categorization. In order to analyze correlations of categories, we use Morpheme analysis, Korean Wiki Dictionary, WordNet and Google Translation API. Our proposed method recommends a category, which is most similar to a guide word by measuring semantic similarity. The experimental results show that, our system improves the system accuracy in term of search category, and retailers can easily select the appropriate categories from our proposed method.

깊이 영상 기반 필터를 적용한 효과적인 호모그래피 추정 방법

주용준,홍명덕,윤의녕,고승현,조근식 한국정보처리학회 2019 정보처리학회논문지. 소프트웨어 및 데이터 공학 Vol.8 No.2

Augmented reality is a technology that makes a virtual object appear as if it exists in reality by composing a virtual object in real time with the image captured by the camera. In order to augment the virtual object on the object existing in reality, the homography of images utilized to estimate the position and orientation of the object. The homography can be estimated by applying the RANSAC algorithm to the feature points of the images. But the homography estimation method using the RANSAC algorithm has a problem that accurate homography can not be estimated when there are many feature points in the background. In this paper, we propose a method to filter feature points of a background when the object is near and the background is relatively far away. First, we classified the depth image into relatively near region and a distant region using the Otsu's method and improve homography estimation performance by filtering feature points on the relatively distant area. As a result of experiment, processing time is shortened 71.7% compared to a conventional homography estimation method, and the number of iterations of the RANSAC algorithm was reduced 69.4%, and Inlier rate was increased 16.9%. 증강현실은 카메라로 촬영하고 있는 영상에 가상의 객체를 실시간으로 합성하여 가상의 객체가 현실에 존재하는 것처럼 보이게 하는 기술이다. 증강현실에서 현실에 존재하는 물체에 가상의 물체를 증강하기 위해서는 현실에 존재하는 물체의 위치와 방향을 정확하게 추정해야 하는데, 이 때 활용되는 기술이 영상의 호모그래피(Homography) 이다. 이러한 호모그래피는 영상의 특징점 좌표에 RANSAC 알고리즘을 적용하여 추정할 수 있는데, RANSAC 알고리즘을 이용한 호모그래피 추정 방식은 호모그래피를 추정하고자하는 물체 이외의 배경에 특징점이 많을 경우 정확한 호모그래피를 추정할 수 없다는 문제점이 존재했다. 본 논문에서는 호모그래피를 추정하고자하는 물체가 가까이에 있고 배경이 상대적으로 멀리 위치해있을 때 영상 각 픽셀의 거리 값을 알 수 있는 깊이 영상을 활용하면 물체와 배경을 쉽게 분리할 수 있다는 점을 이용하여 배경의 특징점을 필터링하는 방법을 제안한다. 이를 위하여 본 논문에서는 흑백조 영상인 깊이 영상을 Otsu 알고리즘을 이용하여 사용자와 거리가 가까운 영역과 거리가 먼 영역으로 이진화하고, RGB 영상에서 추출된 특징점 중에서 거리가 먼 영역에 위치한 특징점을 제거함으로써 특징점을 활용한 호모그래피 추정 결과를 향상시킨다. 이러한 방법을 기존의 호모그래피 추정 방법에 적용한 결과 수행시간이 71.7% 단축되었으며, RANSAC 알고리즘의 반복 횟수가 69.4% 줄어들었고, 참정보 비율이 16.9% 증가하였다.

3차 투영법과 CNN을 이용한 360 비디오 썸네일 생성 방법

장정훈,윤의녕,홍명덕,조근식 한국지능정보시스템학회 2017 한국지능정보시스템학회 학술대회논문집 Vol.2017 No.8

링크드 데이터를 이용한 협업적 비디오 어노테이션 및 브라우징 시스템

이연호,오경진,홍명덕,박승보,조근식 한국지능정보시스템학회 2011 한국지능정보시스템학회 학술대회논문집 Vol.2011 No.5

최근 이러닝과 같은 서비스로 인해 동영상 형태의 멀티미디어 소비가 증가함에 따라 사용자들은 자신이 원하는 멀티미디어를 찾거나 멀티미디어에 등장하는 객체의 정보를 브라우징 하고자 하는 요구사항이 증대되고 있다. 이러한 사용자들의 요구사항을 충족시키기 위해서는 노동집약적인 어노테이션 작업이 불가피하다. 특히 객체 기반 어노테이션에서는 수많은 연구자들이 객체 검출 및 인식, 트래킹 등의 컴퓨터 비전 기술을 적용한 자동 어노테이션을 시도하고 있으나 동영상 내의 다양한 객체를 다루기에 어려움이 있다. 또한 기존 키워드 기반 어노테이션은 객체의 모든 관련 정보를 개별적으로 관리해야 하므로 대용량 데이터 관리와 브라우징에 대한 어려움이 따른다. 이러한 문제를 극복하고자 본 논문에서는 시맨틱 데이터에 접근하기 위해 링크드 데이터를 이용하여 다수의 어노테이션 수행하는 사용자들이 협업적으로 객체에 대한 어노테이션을 하고, 이후 서비스 이용자들이 시맨틱 어노테이션을 통해 효율적인 브라우징을 할 수 있도록 하는 시스템을 제안한다.

C3D 기반의 광학 흐름을 결합한 CCTV에서의 이상 탐지

박슬기(SeulGi Park),홍명덕(MyungDuk Hong),조근식(GeunSik Jo) 한국컴퓨터정보학회 2020 한국컴퓨터정보학회 학술발표논문집 Vol.28 No.1

특징점 배치의 기하학적 유사성을 이용한 GS-RANSAC

송기흔(Kiheun Song),홍명덕(Myung-Duk Hong),조근식(Geun-Sik Jo) 한국정보과학회 2020 정보과학회논문지 Vol.47 No.3

증강 현실은 현실의 대상 위에 증강 객체를 표시하여 정보를 제공하는 것이 목적으로, 증강 객체의 좌표를 정확하게 계산하는 것이 핵심 기능이다. 증강 객체의 좌표를 계산하기 위해서는 두 이미지 간의 호모그래피 추정법을 이용하는데, 여기서 RANSAC(Random Sample Consensus)은 두 이미지에서 추출된 특징점 쌍 중에 적합한 4쌍을 선택하는 기능을 한다. 하지만 기존의 RANSAC의 경우 추출 과정에서 선택한 특징점의 배치가 두 이미지 간에서 기하학적으로 유사한지 보장할 수 없는 문제점이 존재한다. 본 논문에서는 이 문제점을 해결하기 위해 RANSAC에서 선택하는 특징점의 배치를 검사하는 방법을 제안한다. 제안하는 방법은 이미지 위에 특징점의 사각형을 그려서 정점의 순서와 내각의 분포를 각각 검사한다. 실험 결과 제안하는 알고리즘은 기존 RANSAC보다 결함률을 8.55% 줄였으며, 증강 객체를 보다 정확한 위치에 표시하였다. 우리는 제안하는 알고리즘을 통해 증강 현실에서 증강 객체 좌표의 정확도를 개선하였다. Augmented Reality (AR) is intended to generate information by displaying augmented objects on real-world objects. AR is essentially used to calculate the coordinates of augmented objects, for which a homography estimation method involving two images is generally used. In homography estimation, the RANSAC (Random Sample Consensus) algorithm is used to select the four most appropriate pairs of feature points extracted from the two images. However, conventional RANSAC algorithms cannot guarantee the geometric similarity of the inter-image locations of the feature points selected randomly. In order to resolve this conundrum, we propose an algorithm to evaluate the geometric similarity of inter-image locations of feature points. The proposed algorithm draws tetragons of feature points on each image. Then the algorithm determines if the tetragons are similar in the order of vertices and the range of internal angles. The experimental results show that the proposed algorithm decreases the failure rate by 8.55% and displays the augmented objects more accurately compared with conventional RANSAC. We improved the accuracy of augmented object coordinates in AR using our proposed algorithm.