Earticle

생성트리와 같은 문제를 해결하는데 필요한 정보가 네트워크상의 프로세서에 분산되어 있는 상황에서 그들 정보를 교환하면서 그 문제를 해결하는 알고리즘을 분산알고리즘(Distributed Algorithm)이라고 한다. 생성트리와 강결합요소가 이미 구성되어 있는 비동기식 네트워크상에서 네트워크 형상이 변할 경우, 이로 인해 구성되어 있던 생성트리와 강결합요소를 갱신해야 해는 경우가 발생한다. 본 논문에서는 이러한 경우 생성트리와 강결합요소를 효율적으로 갱신하는 메시지 복잡도 O(n'log n'+ (n'+s+t)), 이상시간복잡도 O(n'log n')의 분산 알고리즘을 제안한다. 여기서 n'는 토폴로지 변화후의 네트워크의 프로세서수, s는 추가 링크수를 나타낸다. 또 t는 삭제 링크를 포함하는 강결합요소에 포함되어 있는 전체 링크수를 나타낸다.

Considers the problem to update the spanning tree and strongly-connected components in response to topology change of the network. This paper proposes a distributed algorithm that solves such a problem after several processors and links are added and deleted. Its message complexity and its ideal-time complexity are O(n'log n'+ (n'+s+t)) and O(n'logn') respectively where n'is the number of processors in the network after the topology change, s is the number of added links, and t is the total number of links in the strongly connected component (of the network before the topology change) including the deleted links.

This paper proposes a novel method of connected component labeling and extraction that segments and removes dirt and interphase cells from the chromosome images. This technique was tested with a standard clinical database of human karyotype and excellent segmentation results were achieved. The process involves identifying the various connected components in the input image and assigning labels to create a Label Matrix using the Color Map for these connected components. The connected components or objects that have fewer than the predefined amount of pixels are removed from the image that produces another image where the chromosome except the dirt, stain and interphase cells are uniquely identified and removed. The segmented image is subtracted from the original image, leaving behind only the chromosomes with no dirt, stain and interphase cells, facilitating accurate karyotyping procedures. This technique is extremely helpful when the unwanted object to be segmented and removed shares common intensity levels with the desired information where traditional threshold based procedure will fail to accomplish precise segmentation results.

Most of the image retrieval systems published and implemented have focused on basic features like color, shape and texture of an image with little or no consideration of the included text region of the image. In this work, we have developed an image retrieval system that works on finding similar composite images containing graphical shapes as well as text from a database of thousands of images. By proposing a novel method for text localization, extraction followed by detection, we have demonstrated how this method outperforms commercial OCR tools. The significant feature of this work is its handling the requirements of invariance to font size, design, text region orientation and its ability to give accurate result even in the presence of complex background and graphical elements. The methodology has been tested for English text but is capable to handle any other language.

Finding and obtaining information eciently from the Web is one of the important ele- ments in realizing Smart Home environment. Users expect to nd most relevant information within the shortest possible time. In this paper, we investigate the similarity of Web pages within Strongly Connected Components (SCCs). SCCs are overlapping groups of Web pages that may imply a relationship between the Web pages of the same component. Therefore, we seek to trace the similarity of these groups of Web pages using Cosine Similarity. Our experiment performed on Malaysian Web pages indicates that Web pages within same SCC carry a common topic or theme. This nding proves that we may locate Web pages with similar topic using the hyperlinks structure, without performing expensive analysis on the contents of the Web pages.

In ubiquitous computing environments, many applications are devised to provide autonomous services. To make services autonomous, each service has to inevitably recognize the deployed devices or objects in ubiquitous computing environments. In order to provide an autonomous service based on vision system, we address an efficient character segmentation algorithm by means of introducing the locally adaptive binarization and the object labeling by Connected Components Analysis (CCA). The proposed binarization technique carries out the grayscale-to-binary image conversion with block-based processing to reflect the local variation of images. The object labeling by CCA algorithm is applied to the binarized image with the morphological operation in order to improve the object connectivity. Experimental results show that the proposed algorithm can segment each object reasonably even with atypical or erratic form. Therefore, the proposed algorithm can be useful for development of various applications in ubiquitous computing environments.

고해상도 위성영상에 내재된 도로 영역의 추출에 있어서 이진화, 잡음 제거, 색처리 등의 전처리 작업에 의해서 추출된 도로 후보 영역에 대한 도로 영역 식별 작업은 가장 중요한 과정이다. 따라서 본 논문에서는 전처리 작업에 의해서 추출된 도로 후보 영역에 대해서 대뇌 시각영역에서 발견되는 신경 세포(Neuron cell)의 방향-선택적 인지 기능을 계산 모델화한 공간필터(Orientation-selective spatial filter)를 적용하여 도로 영역을 식별하는 새로운 방법을 제안한다. 제안하는 방법은 전처리 결과 고립된 연결 성분으로 라벨링 된 각각의 도로후보 영역에 대해서 신경 세포형 방향 필터를 적용한 후, 강한 방향 성분이 인지된 영역을 도로 영역으로 식별한다. 제안한 방법의 성능 평가를 위해서는 위성영상으로부터 추출된 도로 후보 영역에 대해서 도로, 비도로 부류의 혼동 행렬(Confusion matrix)을 이용한 식별 정확 및 오류율을 측정하여 보인다. 실험 결과, 본 논문에서 제안한 방향 선택적 필터 기반의 방법은 추출된 도로 후보 영역에 대해서 92% 이상의 도로 식별 정확성을 보였다.

Road identification is the important task for extracting a road region from the high-resolution satellite images, when the road candidates is extracted by the pre-processing tasks using a binarization, noise removal, and color processing. Therefore, we propose a noble approach for identifying a road using the orientation-selective spatial filters, which is motivated by a computational model of neuron cells found in the primary visual cortex. In our approach, after the neuron cell typed spatial filters is applied to the isolated connected-labeling road candidate regions, proposed method identifies the region of perceiving the strong orientation feature with the real road region. To evaluate the effectiveness of the proposed method, the accuracy&error ratio in the confusion matrix was measured from road candidates including road and non-road class. As a result, the proposed method shows the more than 92% accuracy.

In this paper, we introduce the definition of sequentially g-connected components and sequentially locally g-connected by using sequentially g-closed sets. Moreover, we investigate some characterization of sequentially g-connected components and sequentially locally g-connected.

One of the intriguing and fundamental algorithmic graph problems is the computation of the strongly connected components of a directed graph G. In this paper we first introduce a simple procedure for determining the location of the nonzero elements occurring in $B^{-1}$ without fully inverting B, where EB\;{\equiv}\;(b_{ij)\;and\;B^T$ are diagonally dominant matrices with $b_{ii}\;>\;0$ for all i and $b_{ij}\;{\leq}\;0$, for $i\;{\neq}\;j$, and then, as an application, show that all of the strongly connected components of a directed graph G can be recognized by the location of the nonzero elements occurring in the matrix $C(G)\;=\;(D\;-\;A(G))^{-1}$. Here A(G) is an adjacency matrix of G and D is an arbitrary scalar matrix such that (D - A(G)) becomes a diagonally dominant matrix.

We give a generating function for the number of graphs with given numerical properties and prescribed weighted number of connected components. As an application, we give a generating function for the number of q-partite graphs of given order, size and number of connected components.

Recognition of grapheme is a very important process in the recognition within 'Hangul(Korean written language)' letters using phoneme recognition. It is because the success or failure in the recognition of phoneme greatly affects the recognition of letters. For this reason, it is reported that separation of phonemes is the biggest difficulty in the phoneme recognition study. The current study separates and suggests the new phonemes that used the connective elements that are helpful for dividing phonemes, recommends the features for recognition of such suggested phonemes, databases this, and carried out a set of experiments of recognizing phonemes using the suggested features. The current study used 350 letters in the experiment of phoneme separation and recognition. In this particular kind of letters, there were 1,125 phonemes suggested. In the phoneme separation experiment, the phonemes were divided in the rate of 100%, and the phoneme recognition experiment showed the recognition rate of 98% in recognizing only 14 phonemes into different ones.

본 논문에서는 회전체(surface of revolution)의 isophote를 계산하는 효율적이고 안정성 있는 알고리즘을 제시한다. 회전체는 곡면의 특성 상 곡면이 원의 집합으로 이루어지며 하나의 원 위에 있는 점들에 대한 법선 벡터의 집합은 하나의 원뿔(cone)을 이룬다. 원뿔을 이루는 법선 벡터의 특성과 회전체의 대칭성을 이용하여 곡선과 직선의 교점 계산만으로 isophote에 속한 모든 구성요소(connected component)를 발견하는 방법을 제시한다. 또한 회전체 곡면 상의 isophote를 매개변수 곡선으로 표현함으로써 곡선을 쉽게 추적하는 방법을 제시한다.

This paper presents an efficient and robust algorithm to compute the isophote of a surface of revolution. A surface of revolution can be decomposed to a set of cross-sectional circles. The surface normals along each cross-sectional circle form a cone. Using the characteristics of the normal vectors and the symmetric property of the surface of revolution, we propose a method to find the connected components of an isophote, which requires intersecting a planar curve(and its reflection) with two rays. Moreover, we propose a closed-form representation of an isophote as a parametric curve.

기존의 영상 라벨러는 이중 스캔 연결 성분 라벨링 방식이 주로 사용되어 왔다. 그러나, 이중 스캔 연결 성분 라벨링 방식은 별도의 라벨 병합 구간 때문에 실시간 처리와 다채널 처리가 어렵다. 최근 단일 스캔 연결 성분 라벨링 방법들이 제안되었지만, 이들 역시 스캔 횟수는 줄일 수 있으나 별도의 라벨 병합 구간을 제거하지는 못하였다. 본 논문에서는 별도의 라벨 병합 구간을 갖지 않는 단일 스캔 연결 성분 라벨러 구조를 제안한다. 제안하는 구조는 라인 스캔과 동시에 라벨 병합이 이루어지기 때문에 고속 동작하고, 예상 가능한 프레임 처리율을 가지며, 다채널 처리가 가능하다. 제안하는 라벨러 구조는 FPGA로 설계되었고 동작이 검증되었으며, 성능 실험을 통해 고속 동작과 다채널 영상 처리에 적합함을 확인하였다.

배관시스템은 다양한 산업 분야에서 이용되는 중요한 설비이며 생활 및 안전과 관련된 영역에서 사용되고 있다. 배관시스템은 건축물 및 시설의 주요 구조부에 고정되어 있으나 외부 하중을 지지하지 않으며 주어진 고유기능을 수행하는 비구조요소이다. 지진하중으로 인한 배관시스템은 두 지지점 사이의 서로 다른 거동으로 발생하는 위상차로 인한 상대 변위의 영향을 받으며 변위 지배적인 반복거동 때문에 손상이 발생할 가능성이 있다. 배관시스템에서 피팅과 조인트는 지진하중에 취약한 대표적인 요소이다. 배관시스템의 피팅과 조인트에 대한 내진성능과 한계상태를 평가하고자 한다면 상대변위를 모사하기 위한 높은 스트로크를 가지는 엑츄에이터가 필요하나 실험을 수행할 수 있는 설비가 많지 않아 어려움이 있다. 따라서 피팅과 조인트로 연결된 배관시스템의 내진성능과 한계상태를 평가하기 위해서는 요소 단위의 실험이 필요하다. 이 연구에서는 수직배관시스템에서 지진하중에 취약한 요소인 피팅과 조인트를 포함하는 엘보 시험체에 대하여 내진성능을 평가하는 방법을 제시하였다. 엘보 시험체는 90° 배관 엘보의 양단에 직관부를 유동식 그루브 조인트를 이용하여 연결하였다. 엘보 시험체에 대하여 변형각에 기반을 둔 주기하중 프로토콜을 이용하여 내진성능을 평가하였다. 평가된 내진성능에 대한 여유도를 확인하기 위하여 일정한 진폭에 대한 주기하중을 적용하여 한계상태를 평가하였다.

Piping systems are crucial facilities used in various industries, particularly in areas related to daily life and safety. Piping systems are fixed to the main structures of buildings and facilities but do not support external loads and serve as non-structural elements performing specific functions. Piping systems are affected by relative displacements owing to phase differences arising from different behaviors between two support points under seismic loads; this can cause damage owing to the displacement-dominant cyclic behavior. Fittings and joints in piping systems are representative elements that are vulnerable to seismic loads. To evaluate the seismic performance and limit states of fittings and joints in piping systems, a high-stroke actuator is required to simulate relative displacements. However, this is challenging because only few facilities can conduct these experiments. Therefore, element-level experiments are required to evaluate the seismic performance and limit states of piping systems connected by fittings and joints. This study proposed a method to evaluate the seismic performance of an elbow specimen that includes fittings and joints that are vulnerable to seismic loads in vertical piping systems. The elbow specimen was created by connecting straight pipes to both ends of a 90° pipe elbow using flexible groove joints. The seismic performance of the elbow specimen was evaluated using a cyclic loading protocol based on deformation angles. To determine the margin of the evaluated seismic performance, the limit states were assessed by applying cyclic loading with a constant amplitude.

거대한 웹 컨텐츠 안에는 수많은 링크들로 인한 순환들이 존재하게 된다. 그 순환들은 강하게 뭉쳐있는 실타래 처럼, 강하게 결합한 순환들의 덩어리 형태로 존재하게 된다. 웹 컨텐츠는 흔히 방향그래프로 표현되는데, 즉 웹 컨텐츠에서 나타나는 수많은 링크둘을 방향그래프에서 강결합요소를 이용하면 모든 순환을 효율적으로 발견할 수 있다. 본 논문에서는 강결합요소를 이용하여 거대한 그래프에서 보다 효율적으로 모든 순환을 찾아낼 수 있는 방법을 제시하였다.

본 연구에서는 한글 문자 인식을 수행하였다. 한글 인식을 수행하되 고딕 인쇄체 문자를 대상으로 하였고, 자소 단위 인식을 통한 인식을 수행하되 기존 한글 문자 인식 연구에서 사용하는 자음과 모음 단위의 자소가 아닌 연결성분을 이용하여 인식하는 새로운 자소를 이용하였다. 새로운 자소들은 끝점, 2선 모임점, 3선 모임점, 4선 모임점의 특징을 추출하고 특징에 의해 자소를 인식하는 데이터베이스를 구성하여 자소를 인식하게 하였다. 또한 연결 성분을 반영한 새로운 자소로 고딕 인쇄체 문자를 인식하므로 추출된 자소를 6가지로 분류하였고, 6가지 자소에 의해 구성되는 92가지 문자 구조를 제안하고 이에 따른 문자를 데이터베이스를 구축하였고, 자소의 무게 중심을 이용한 분포를 이용하여 제안된 구조를 통하여 데이터베이스를 이용한 문자인식을 수행하였다.