본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

개선된 간단한 경계선 추적자 알고리즘
Improved Simple Boundary Following Algorithm

정철호   (연세대학교 컴퓨터과학과UU0000936  ); 한탁돈   (연세대학교 컴퓨터과학과UU0000936  );
  • 초록

    간단한 경계선 추적자 알고리즘(SBF: Simple Boundary Follower)은 영상의 인식과 표현을 위하여 사용되는 경계선 추적 알고리즘 중에서 널리 사용되는 것이다. SBF는 주로 이진화된 영상에서 물체의 경계선을 추적할 때 매우 간단하면서도 효율적인 성능을 제공한다. 그러나 추적자의 위치와 방향조건에 따라 인너코너(inner corner)와 인너-아우터 코너(inner-outer corner)의 일부 영상을 추적하지 못하는 비일관성(inconsistency)을 가지고 있고, 경계선 이외의 픽셀들에 대한 부가적인 이동연산을 요구한다는 단점이 있다. 이러한 제약성들 중 인너-아우터 코너의 비일관성을 해결하기 위하여 수정된 간단한 경계선 추적자 알고리즘(MSBF: Modified Simple Boundary Follower)이 연구되었지만 여전히 인너코너 추적 비일관성과 부가 연산 필요성에 대한 해결책은 제시되지 않았다. 본 논문에서는 이를 개선하기 위하여 비일관성이 일어나지 않도록 처리하고, 경계선 주위 픽셀에 대한 이동 연산을 줄일 수 있는 개선된 간단한 경계선 추적자 알고리즘(ISBF: Improved Simple Boundary Follower)을 제안하였다. 또한 경계선상의 픽셀들의 배치와 이동 경로 방식에 대해 분류를 함으로써 세 가지 알고리즘의 연산복잡도를 계산하였다. 제안된 알고리즘은 MSBF에 비하여 연산량이 감소하였고, 비일관성의 문제가 없는 것으로 분석되었다.


    The SBF (Simple Boundary Follower) is a boundary-following algorithm, and is used mainly for image recognition and presentation. The SBF is very popular because of its simplicity and efficiency in tracing the boundary of an object from an acquired binary image; however, it does have two drawbacks. First, the SBF cannot consistently process inner or inner-outer corners according to the follower's position and direction. Second, the SBF requires movement operations for the non-boundary pixels that are connected to boundary pixels. The MSBF (Modified Simple Boundary Follower) has a diagonal detour step for preventing inner-outer corner inconsistency, but is still inconsistent with inner-corners and still requires extra movement operations on non-boundary pixels. In this paper, we propose the ISBF (Improved Simple Boundary Follower), which solves the inconsistencies and reduces the extra operations. In addition, we have classified the tour maps by paths from a current boundary pixel to the next boundary pixel and have analyzed SBF, MSBF, and ISBF. We have determined that the ISBF has no inconsistency issues and reduces the overall number of operations.


  • 주제어

    경계선 추적 알고리즘 .   Papert의 터틀 알고리즘 .   간단한 경계선 추적자 .   수정된 간단한 경계선 추적자 .   개선된 간단한 경계선 추적자.  

  • 참고문헌 (7)

    1. S. Marchand-Maillet, Y.M. Sharaiha, Binary Digital Image Processing, pp.173-180, Academic Press, 2000 
    2. M. Das, M.J. Paulik, N.K. Loh, 'A Bivariate Autoregressive Modeling Technique for Analysis and Classification of Planar Shapes,' IEEE Transaction on Pattern Analysis and Machine Intelligence, Vol. 12, No. 1, pp. 97-103, January 1990 
    3. S. Papert, 'Uses of technology to enhance education,' Technical report 298, AI Lab., MIT, 1973 
    4. I. Pitas, Digital Image Processing Algorithms and Applications, pp.275-329, John Wiley & Sons, 2000 
    5. N. Arica, F.T. Yarman-Vural, 'An Overview of Character Recognition Focused on Off-Line Handwriting,' IEEE Transaction on Systems, Man, and Cybernetics-PART C: Applications and Reviews, VOL. 31, NO. 2, pp.216-233, May 2001 
    6. E. Gose, R. Johnsonbaugh, S. Jost, Pattern recognition and Image analysis, pp.338- 346, Prentice Hall, 1996 
    7. R.O. Duda, P.E. Hart, Pattern recognition and scene analysis, John Wiley & Sons, 1973 

 저자의 다른 논문

  • 정철호 (10)

    1. 1999 "통계적 기법에 의한 상용 마이크로프로세서의 성능분석" 정보과학회논문지. Journal of KISS (c) : computing practices. C 5 (4): 516~525    
    2. 2000 "3차원 그래픽을 위한 Geometry 프로세서의 설계" 정보처리논문지 = The transactions of the Korea Information Processing Society 7 (1): 252~265    
    3. 2002 "정보화 사회와 착용형 컴퓨터의 전망" 한국멀티미디어학회지 6 (1): 88~104    
    4. 2003 "포스트 PC 시대의 착용형 컴퓨터 전망" 제어·자동화·시스템공학회지 = ICASE magazine 9 (4): 15~27    
    5. 2003 "작은 룩업테이블을 가지는 새로운 파이프라인 나눗셈기" 電子工學會論文誌. Journal of the Institute of Electronics Engineers of Korea. SD, 반도체 40 (9): 724~733    
    6. 2004 "3차원 그래픽 지오메트리 연산을 위한 벡터 지오메트리 엔진의 설계." 정보과학회논문지. Journal of KIISE. 시스템 및 이론 31 (1): 135~143    
    7. 2015 "WiMedia MAC DRP 프로토콜에서 효율적인 영상 스트리밍 서비스를 위한 Fast MAS 재조정 기법" 한국통신학회논문지 = The Journal of Korean Institute of Communications and Information Sciences 40 (6): 1048~1057    
    8. 2015 "향상된 분산 채널 접근 기법 및 다중사용자 MIMO 기반 무선랜 환경에서 가변 길이 페이로드에 대한 수학적 모델" 한국통신학회논문지 = The Journal of Korean Institute of Communications and Information Sciences 40 (6): 1117~1119    
    9. 2015 "효율적인 영상 스트리밍 서비스를 위한 Cross-layer 영상 정보 공유 방법 및 선택적 재전송 기법" 멀티미디어학회논문지 = Journal of Korea Multimedia Society 18 (7): 853~863    
  • 한탁돈 (32)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기