KR100216520B1

KR100216520B1 - Edge thinning method

Info

Publication number: KR100216520B1
Application number: KR1019960068070A
Authority: KR
Inventors: 도경민; 이쾌희
Original assignee: 이계철; 한국전기통신공사; 정선종; 한국전자통신연구원
Priority date: 1996-12-19
Filing date: 1996-12-19
Publication date: 1999-08-16
Anticipated expiration: 2016-12-19
Also published as: KR19980049369A

Abstract

본 발명은 영상 처리 및 컴퓨터 비전 분야에서 에지를 세선화하는 방법에 관한 것으로서, 최단 거리 추적 방법 또는 최소화 추적 방법을 사용하여 그래디언트 방향 기반 세선화를 수행하는 제1단계와, 세선화 조각을 제거하는 제2단계로 구성된다.The present invention relates to a method for thinning edges in the field of image processing and computer vision, comprising: a first step of performing gradient direction based thinning using a shortest distance tracking method or a minimum tracking method; It consists of a second step.

상기와 같은 본 발명의 에지 세선화 방법을 사용하면 컴퓨터 비전이나 영상 처리 분야에서 대상체의 경계 에지를 추출하는데 효과적인 능력을 제공하며, 빈 공간인 경우 잔가지 성분이 존재하는 경우, 이진 영역의 가장 긴축이 대상체의 에지 방향과 다른 방향으로 나타나는 경우 또는 에지 영상에서 인접한 대상체의 경계가 서로 만나는 경우에 기존의 세선화 방법의 왜곡된 경계 생성의 단점을 극복할 수 있다.Using the edge thinning method of the present invention as described above provides an effective ability to extract the boundary edge of the object in the field of computer vision or image processing, and if there is a twig component in the empty space, When the edges of the object appear in a direction different from that of the object or when the boundaries of adjacent objects meet each other in the edge image, the disadvantage of generating the distorted boundary of the conventional thinning method may be overcome.

그리고, 더욱 많은 에지를 추출하기 위해 낮은 임계값을 사용하여 얻어진, 두꺼운 에지 영역을 가지는 에지 영상을 대상체 원래의 경계를 표현하는 에지로 세선화하여 더욱 많은 양의 정보를 왜곡 없이 제공할 수 있으며, 시각적으로 양질의 영상을 얻을 수 있을 뿐만 아니라 데이터 저장이나 전송시 채널 점유 시간을 줄이고 메모리를 절약할 수 있다.In addition, an edge image having a thick edge region obtained by using a low threshold value to extract more edges may be thinned to an edge representing an object's original boundary, thereby providing a greater amount of information without distortion. Not only can you get a good visual quality, but you also save channel memory and save memory when saving or transferring data.

Description

Edge thinning method

본 발명은 영상 처리 및 컴퓨터 비전 분야에서 에지를 세선화하는 방법에 관한 것으로서, 영상 처리 및 컴퓨터 비전 분야에서 사용하는 물체의 경계를 표현하는 에지는 일반적으로 연산자를 사용하고 임의의 임계값으로 이진화하여 얻어지는데, 이 때, 사용된 임계값에 따라 획득되어지는 에지의 양과 두께가 결정된다.BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for thinning edges in the field of image processing and computer vision, wherein edges representing the boundaries of objects used in the field of image processing and computer vision generally use an operator and binarize to an arbitrary threshold. In this case, the amount and thickness of the edge to be obtained are determined according to the threshold used.

일반적으로 낮은 임계값을 사용하면 많은 에지가 얻어지나 에지가 두꺼워지며, 높은 값의 임계값을 사용하면 두께가 얇게 나타나나 뚜렷한 에지만이 얻어져 영상으로부터 많은 정보를 획득하기 어려운 장단점을 가진다.In general, using low thresholds results in many edges but thicker edges. Using high thresholds results in thinner thicknesses, but only distinct edges are obtained, which makes it difficult to obtain much information from an image.

또한, 밝기가 서서히 변하는 물체의 영상은 그래디언트 크기가, 또렷한 경계를 가지는 부분에 비해 상대적으로 작기 때문에 이러한 물체의 에지는 높은 임계값을 사용하면 나타나지 않는다.In addition, since the image of an object whose brightness changes gradually, the gradient size is relatively small compared to the portion having a clear boundary, the edge of such an object does not appear using a high threshold value.

따라서, 동일한 입력 영상으로부터 보다 많은 양의 정보를 획득하기 위해서는 낮은 값의 임계값을 사용하여 에지 영상을 취득하여야 하는데, 이 경우 에지 영상에서 나타나는 에지는 서로 다른 두께를 가지며 대상체의 경계를 정확하게 표현하지 못한다는 단점이 있다.Therefore, in order to acquire more information from the same input image, an edge image must be acquired using a low threshold value. In this case, edges appearing in the edge image have different thicknesses and do not accurately represent the boundary of the object. There is a drawback to not doing it.

상기 세선화는 이진 영상에서 물체를 이루는 중심 뼈대(Skeleton, Stick figure)로 나타내는 것으로서, 종래의 세선화 방법은 사용하는 방법에 따라 크게 두가지로 분류된다.The thinning is represented by a skeleton (stick figure) forming an object in a binary image, and conventional thinning is classified into two types according to a method used.

첫 번째는 medial-axis 변환을 사용하는 방법이다.The first is to use the medial-axis transformation.

상기 방법은 물체의 중심 뼈대와 물체의 경계 사이의 거리가 동일하게 되는 적어도 두 개 이상의 경계가 존재하는 중심 뼈대를 찾는 방법으로서, 연속 공간(Continuous space)에서는 medial-axis 변환에 의해 물체를 유일하게 표현할 수 있고, 아무런 정보 손실 없이 물체를 복원할 수 있으나, 이산 공간(discrete space)에서는 원래 물체의 형태를 보존할 수 없다는 단점이 있다.The method finds a central skeleton in which at least two boundaries exist in which the distance between the center skeleton of the object and the boundary of the object is the same. In continuous space, the object is uniquely identified by a medial-axis transformation. It can be expressed, and the object can be restored without any information loss, but there is a disadvantage that the original object cannot be preserved in discrete space.

두 번째는 물체의 주변 화소를 제거하는 방법이다.The second method is to remove the surrounding pixels of the object.

상기 방법은 물체의 연결성(connectivity)이 변화시키지 않는 조건하에서, 반복적으로 물체를 구성하는 화소를 경계에서부터 물체 중심 방향으로 하나씩 제거하는 방법으로서, 상기와 같은 대부분의 종래의 세선화 방법은 주로 문자 인식 등과 같은 분야에서의 응용을 위하여 개발되어 이러한 응용에서는 좋은 결과를 보이나, 이진 영역의 형태를 유지하는 방향으로 세선화를 수행하기 때문에 에지 추출 등의 분야에서는 세선화 결과 왜곡된 에지를 생성시키는 문제점이 있다.The above method is a method of repeatedly removing pixels constituting an object one by one from the boundary toward the object center under the condition that the connectivity of the object does not change. Most conventional thinning methods as described above mainly use character recognition. It is developed for application in such fields and shows good results in such applications. However, since thinning is performed in the direction of maintaining the shape of the binary region, the problem of generating distorted edges as a result of thinning is difficult. have.

이하, 도면을 참조하여 종래의 에지 세선화 방법을 설명한다.Hereinafter, a conventional edge thinning method will be described with reference to the drawings.

제1도는 종래의 세선화 방법에 따른 세선화 결과 예시도이다.1 is an exemplary view showing thinning results according to a conventional thinning method.

제1도를 참조하면, B는 에지 영역에 내용이 있는 경우를 나타내고, W는 빈 공간을 나타낸다.Referring to FIG. 1, B represents a case where there is content in the edge region, and W represents an empty space.

(a)와 같이 에지 영역에 빈 공작이 존재하는 경우, 종래의 세선화 방법은 영역의 형태를 유지하도록 세선화를 수행하여 (c)와 같이 애상체의 경계와 다른 왜곡된 예지를 생성한다.When there is an empty work in the edge region as shown in (a), the conventional thinning method performs thinning so as to maintain the shape of the region to generate a distorted edge different from the boundary of the ghost body as shown in (c).

그리고, (b)와 같이 에지 영역에 잔가지 성분이 존재하는 경우, 종래의 세선화 방법은 영역의 형태를 유지하도록 세선화를 수행하여 (d)와 같은 대상체의 경계와 다른 왜곡된 에지를 생성한다.In addition, when the twig component is present in the edge region as shown in (b), the conventional thinning method performs thinning to maintain the shape of the region, thereby creating a distorted edge different from the boundary of the object as shown in (d). .

또한, 에지 영상에서 인접한 대상체의 경계가 서로 만난 경우에는 대상체 원래의 경계와 다른 형태로 대상체의 경계를 왜곡시켜 세선화하는 문제점이 있다.In addition, when the edges of adjacent objects meet each other in the edge image, there is a problem of thinning by distorting the boundary of the object in a form different from the original boundary of the object.

즉, 대상체의 경계의 동일한 화소값을 가지는 화소들이 존재하는 경우, 밝기의 변화가 다른 부분에 비해 상대적으로 적은 경우, 대상체의 경계 부근에 밝기의 분표가 일정하지 않은 경우는 입력 영상에서 일상적으로 빈번하게 발생되므로 에지 영상에서 에지 영역의 빈 공간이나 잔가지 성분 또한 일상적으로 빈번하게 발생된다는 단점이 있다.That is, when there are pixels having the same pixel value at the boundary of the object, when the change in brightness is relatively small compared to other parts, when the fraction of brightness is not constant near the boundary of the object, the input image is frequently used. As a result, the empty space or the twig component of the edge region in the edge image is also frequently generated frequently.

따라서, 본 발명에서는 상기와 같은 단점을 보완하기 위해, 빈 공간이나 잔가지 성분 등에 의해 영향을 받지 않고 여러 두께를 가지는 에지를 대상체 원래의 경계를 표현하는 에지로 추출하는 에지 세선화 방법을 제공하고자 한다.Accordingly, the present invention is to provide an edge thinning method for extracting edges having various thicknesses as the edge representing the original boundary of the object without being affected by the empty space or the twig component. .

제1도는 종래의 세선화 방법에 따른 세선화 결과 예시도이고,1 is an exemplary view of thinning results according to a conventional thinning method,

제2도는 본 발명의 실시예에 따른 처리 단계의 구성도이고,2 is a block diagram of a processing step according to an embodiment of the present invention,

제3도는 본 발명의 실시예에 따른 에지 세선화 방법에서 사용하는 임계값의 설명도이고,3 is an explanatory diagram of a threshold value used in the edge thinning method according to an embodiment of the present invention,

제4도는 본 발명의 실시예에 따른 최단 거리 추적 방법을 사용하여 세선화를 수행하는 흐름도이고,4 is a flowchart for performing thinning using the shortest distance tracking method according to an embodiment of the present invention.

제5도는 본 발명의 실시예에 따른 최소차 추적 방법을 사용하여 세선화를 수행하는 흐름도이고,5 is a flowchart of performing thinning using a minimum difference tracking method according to an embodiment of the present invention.

제6도는 본 발명의 실시예에 따른 세선화 조각 제거 단계 흐름도이다.6 is a flowchart of a thinning fragment removal step according to an embodiment of the present invention.

본 발명에서 제공하는 에지 세선화 방법은 최단 거리 추적 방법 또는 최소 거리 추적 방법을 사용하여 그래디언트 방향 기반 세선화를 수행하는 제1단계와, 세선화 조각을 제거하는 제2단계로 구성된다.The edge thinning method provided by the present invention includes a first step of performing gradient direction based thinning using a shortest distance tracking method or a minimum distance tracking method, and a second step of removing the thinning pieces.

이하, 첨부된 도면을 참조하여 본 발명을 상세히 설명한다.Hereinafter, with reference to the accompanying drawings will be described in detail the present invention.

제2도는 본 발명의 실시예에 따른 처리 단계의 구성도이고, 제3도는 본 발명의 실시예에 따른 에지 세선화 방법에서 사용하는 임계값의 설명도이고, 제4도는 본 발명의 실시예에 따른 최단 거리 추적 방법을 사용하여 세선화를 수행하는 흐름도이고, 제5도는 본 발명의 실시예에 따른 최소차 추적 방법을 사용하여 세선화를 수행하는 흐름도이고, 제6도는 본 발명의 실시예에 따른 세선화 조각 제거 단계 흐름도이다.2 is a schematic diagram of a processing step according to an embodiment of the present invention, and FIG. 3 is an explanatory diagram of a threshold value used in the edge thinning method according to an embodiment of the present invention, and FIG. 4 is a diagram illustrating an embodiment of the present invention. FIG. 5 is a flowchart for performing thinning using the shortest distance tracking method according to the present invention. FIG. 5 is a flowchart for performing thinning using the minimum difference tracking method according to an embodiment of the present invention. According to the thinning fragment removal step flow chart.

제2도를 참조하면, 본 발명의 세선화 방법은 에지 영상을 입력으로 수행된다.Referring to FIG. 2, the thinning method of the present invention is performed by inputting an edge image.

이때, 에지 영상이란, Sobel, Canny 등과 같은 일반적인 그래디언트 연산자를 사용하여 컨벌루션을 취하고, 임의의 임계값으로 이진화하여 얻어진 영상을 의미한다.In this case, the edge image refers to an image obtained by taking convolution using general gradient operators such as Sobel and Canny, and binarizing to an arbitrary threshold.

본 발명의 세선화 방법은 크게 두 단계로 구성된다.The thinning method of the present invention is largely composed of two steps.

첫 번째 세선화 단계에서는 에지 영상의 에지 영역에 대해 그 영역의 위치에 대응하는 원 영상의 그래디언트 방향을 고려하여 세선화(100)를 수행하는 과정이고, 두 번째 단계인 세선화 조각 제거 단계(200)는 세선화 결과로 발생되는 조각을 제거하는 과정이다.In the first thinning step, the thinning step 100 is performed in consideration of the gradient direction of the original image corresponding to the position of the area with respect to the edge area of the edge image. ) Is the process of removing fragments resulting from thinning.

대상체의 경계 부근에서의 밝기값의 불연속이나 잡음 등에 의하여 발명한 세선화 결과 하나의 에지 영역이 둘 이상의 에지로 나타날 수 있는데, 그중 하나는 대상체 원래의 경계를 표현하는 세선화된 에지이고, 나머지는 1∼10정도의 길이를 가지는 잡음들이다. 세선화 조각은 이러한 조각을 나타내며 세선화 조각은 두 번째 단계에서 제거되어 원래 물체의 경계를 표현하는 세선화된 에지 영상을 얻는다.As a result of the thinning invented by the discontinuity or noise of the brightness value near the boundary of the object, one edge region may appear as two or more edges, one of which is a thinned edge representing the original boundary of the object, and the other Noises of length 1-10. Thinning fragments represent these fragments, and the thinning fragments are removed in the second step to obtain thinned edge images that represent the boundaries of the original object.

제3도를 참조하면, 본 발명에서는 최대 방향차(Dd)(31), 기준 길이(Lb)(32),Referring to FIG. 3, in the present invention, the maximum direction difference Dd 31, the reference length Lb 32,

탐색 길이(Ls)(33), 세선화 조각 크기(Af)(34), 유사도 임계값(Sf)(35)의 다The length of the search length (Ls) 33, the thinning piece size (Af) 34, and the similarity threshold (Sf) 35

섯 가지 임계값을 사용한다.Six thresholds are used.

이때, 상기 최대 방향차(31), 기준길이(32), 탐색길이(33)은 세선화 단계에서 사용되고, 나머지(34, 35)는 세선화 조각 제거 단계에서 사용된다.At this time, the maximum direction difference 31, the reference length 32, the search length 33 is used in the thinning step, the remainder 34, 35 is used in the thinning fragment removal step.

현재까지 추적되어 온 화소의 집합을 추적단이라 정의하고 추적단 중 기준 그래디언트 방향은 추적단의 그래디언트 방향의 평균값으로 결정되고, 탐색단은 기준 그래디언트 방향에 존해하는 일정 길이태의 화소의 집합을 의미한다.The set of pixels that have been tracked up to now is defined as a tracking stage, and the reference gradient direction of the tracking stages is determined by the average value of the gradient direction of the tracking stage, and the search stage is a set of pixels having a predetermined length that exists in the reference gradient direction. .

상기 최대 방향차(31)는 기준 그래디언트 방향과 탐색단을 구성하는 각 화소의 그래디언트 방향과의 최대 허용차이를 나타내며, 0∼π의 값을 가지는데 상기 최대 방향차(31)의 값이 클수록 추적단의 길이가 더욱 길어지게 되어 세선화된 영상에서 화소의 총 수가 적어진다.The maximum direction difference 31 indicates a maximum allowable difference between the reference gradient direction and the gradient direction of each pixel constituting the search end, and has a value of 0 to π, and the larger the value of the maximum direction difference 31 is tracked. The length of the stage becomes longer, so that the total number of pixels in the thinned image is reduced.

상기 기준 길이(32)는 기준 추적열의 길이를 나타내는데, 기준 추적열은 추적단의 가장 마지막에 추적된 화소부터 기준 길이만큼 역추적하여 역추적된 화소들로 형성된다. 따라서, 상기 기준길이(32)는 기준 그래디언트 방향을 산출하는데 사용하는 화소의 길이를 의미한다. 현재까지 추적된 화소의 총 개수, 즉 추적단의 길이가 N개일 때 상기 기준길이(32)는 1∼N의 값을 가진다.The reference length 32 represents the length of the reference tracking sequence, and the reference tracking sequence is formed of pixels traced back from the last traced pixel by the reference length. Therefore, the reference length 32 means the length of the pixel used to calculate the reference gradient direction. The reference length 32 has a value of 1 to N when the total number of pixels tracked so far, that is, the length of the tracking stage is N.

상기 탐색 길이(33)는 탐색단의 길이를 나타내며 추적의 진행을 결정할 후보 화소의 수를 의미하며, 현재 추적된 화소에서 기준 그래디언트 방향으로의 탐색 길이(33) 내의 화소들로 탐색단을 구성한다.The search length 33 represents the length of the search end and means the number of candidate pixels to determine the progress of tracking, and constitutes the search end with pixels within the search length 33 in the direction of the reference gradient from the currently tracked pixel. .

상기 탐색 길이(33)는 1 이상의 값을 가지는데 탐색 길이의 값이 너무 크면 추적단의 길이가 길어지므로 세선화된 영상에서의 에지가 왜곡된다.The search length 33 has a value of 1 or more. If the value of the search length is too large, the length of the tracking end becomes long, and thus the edge of the thinned image is distorted.

상기 세선화 조각의 크기(34)는 세선화 조각을 결정하는데 사용되는 임계값이며 세선화 결과 발생되는 에지 성분중, 세선화 조각 크기보다 작은 영역의 에지 성분은 세선화 조각으로 결정되고, 상기 유사도 임계값(35)은 세선화 조각의 제거를 결정하는데 사용되며 0∼1 사이의 값을 가지며 값이 클수록 더욱 많은 에지들이 제거된다.The size 34 of the thinning piece is a threshold used to determine the thinning piece, and among the edge components resulting from thinning, an edge component of a region smaller than the size of the thinning piece is determined as the thinning piece. Threshold 35 is used to determine removal of thinning pieces and has a value between 0 and 1, with larger values removing more edges.

제4도를 참조하면, 본 발명의 두 단계 처리 과정 중, 그래디언트 방향을 이용하여 세선화를 수행하는 첫 번째 단계인 최단 거리 추적 방법에 의한 세선화 단계에서는 먼저, 최대 방향차(Dd), 기준 길이(Lb), 탐색 길이(Ls)의 세가지 임계값이 사용되므로, 상기 값을 결정한다(101).Referring to FIG. 4, in the thinning step by the shortest distance tracking method, which is the first step of performing the thinning using the gradient direction, the maximum direction difference Dd and the reference are performed. Since three threshold values of length Lb and search length Ls are used, the value is determined (101).

그리고, 에지 영상을 탐색하다가 에지 화소를 만나면 추적을 시작(102)하는데, 이때의 에지 화소를 E라 표기한다. 상기 화소 E의 위치에 대응하는 원 영상에서의 그래디언트의 방향, DIR(E)를 구하고, 이 값을 초기 기준 그래디언트 방향(DIRsum)으로 선택한다. 또한, 추적단 그래디언트 방향의 값을 초기 기준 그래디언트 방향으로 할당한다(103). 이때, 초기 기준 그래디언트 방향을 + 추적 방향으로 결정하고, 180도 위상차를 가지는 방향을 - 추적 방향으로 결정한다.When the edge image is encountered while searching for the edge image, tracking is started (102). The edge pixel at this time is denoted as E. The direction of the gradient, DIR (E), in the original image corresponding to the position of the pixel E is obtained, and this value is selected as the initial reference gradient direction (DIRsum). In addition, a value of the tracking end gradient direction is allocated to the initial reference gradient direction (103). At this time, the initial reference gradient direction is determined as the + tracking direction, and a direction having a 180 degree phase difference is determined as the − tracking direction.

먼저, + 추적 방향으로 에지 화소를 추적하는데, 상기 + 추적 방향에 존재하는 탐색 길이내의 화소중, 그래디언트 방향과 기준 그래디언트 방향과의 차가 최대 방향차 이하이고, 에지 화소이며, 추적에 사용되지 않은 화소 중에서 현재 추적된 화소와 가장 가까운 화소로 추적을 진행한다(104 내지 111).First, an edge pixel is tracked in the + tracking direction, wherein a difference between the gradient direction and the reference gradient direction of the pixels within the search length existing in the + tracking direction is equal to or less than the maximum direction difference, and is an edge pixel and is not used for tracking. Tracking is performed to the pixel closest to the currently tracked pixel, from 104 to 111.

상기 추적을 진행하기 위해 먼저, 탐색 기준값 i를 1로 초기화(104)하고, 상기 i 값과 탐색 길이를 비교(105)하여, i 값이 탐색 길이보다 작거나 같은 경우 기준 거리(DIRbase)를 계산(106)한 후, + 추적 방향의 화소(P(i))를 구한다(107).To proceed with the tracking, first, the search reference value i is initialized to 1 (104), and the search value is compared 105 to the value i, and the reference distance DIRbase is calculated when the value of i is less than or equal to the search length. After 106, the pixel P (i) in the + tracking direction is obtained (107).

그리고, 화소 P(i)에서의 그랜디언트 방향(약(P(i)))을 구한 후(108), 상기 DIRbase와 DIR(P(i))의 차(DIFF)를 구하고(109), DIFF와 Dd를 비교(110)하여 DIFF가 Dd보다 작지 않으면, P(i)가 1인 경우 i값을 1증가시킨 후(111), 상기 추적 과정(105 내지 111)을 반복한다.After obtaining the gradient direction (about P (i)) in the pixel P (i) (108), the difference DIFF between the DIRbase and DIR (P (i)) is obtained (109), When DIFF and Dd are compared 110 and DIFF is not smaller than Dd, when P (i) is 1, i value is increased by 1 (111), and the tracking process (105 to 111) is repeated.

이러한 방법을 최단 거리 탐색 방법이라 한다.This method is called the shortest distance search method.

상기와 같은 방법으로 추적을 진행할 화소 P(i)가 결정되면 현재 추적된 화소로부터 화소 P(i) 이내의 탐색 화소의 위치(ROW((P(i)), COL(P(i))를 저장하고 그래디언트 방향을 누적시킨다(112 내지 115).When the pixel P (i) to be tracked is determined as described above, the position ROW ((P (i)), COL (P (i)) of the search pixel within the pixel P (i) is determined from the currently tracked pixel. Store and accumulate gradient directions (112-115).

상기와 같이 추적 정보를 갱신하였으면, 추적을 진행할 화소(P(i))로 이동하여 추적을 계속한다(116).If the tracking information is updated as described above, the tracking information is moved to the pixel P (i) to be tracked to continue tracking (116).

만일, + 추적 방향에 존재하는 탐색 길이내의 화소중, 그래디언트 방향과 기준 그래디언트 방향과의 차가 최대 방향차 이하이고 에지 화소이며 추적에 사용되지 않는 화소가 없는 경우는 + 추적 방향으로의 추적을 종료하고, - 추적 방향으로 에지 화소 추적을 시작한다. 이 때 추적단 그래디언트 방향의 값을 DIR(E)로 할당한다(117).If the difference between the gradient direction and the reference gradient direction is less than or equal to the maximum direction difference and there are no pixels that are edge pixels and are not used for tracking among the pixels in the search length existing in the + tracking direction, the tracking ends in the + tracking direction. ,-Start edge pixel tracking in the tracking direction. At this time, the value of the tracking stage gradient direction is allocated to DIR (E) (117).

- 추적 방향에 존재하는 탐색 길이내의 화소 중, 그래디언트 방향과 기준 그래디언트 방향과의 차가 최대 방향차 이하이고, 에지 화소이며 추적에 사용되지 않은 하소중에서 현재 추적된 화소와 가장 가까운 화소로부터 추적을 진행한다(118 내지 125).In the pixel in the search length present in the tracking direction, the difference between the gradient direction and the reference gradient direction is equal to or less than the maximum direction difference, and the tracking is performed from the pixel closest to the currently tracked pixel during calcination not used for tracking. (118-125).

상기 진행과정의 세부 사항은 상기 + 방향의 추적방향과 동일하고, 방향만 +에서 -로 바뀐다.Details of the process are the same as the tracking direction of the + direction, and only the direction changes from + to-.

이때, 추적을 진행할 화소(P(i))가 결정되면, 현재 추적된 화소로부터 화소 P(i) 이내의 탐색 화소의 위치(ROW(P(i)), COL(P(i))를 저장하고 그래디언 방향을 누적시킨다(126 내지 129). 상기와 같이 추적 정보를 갱신한 후, 추적을 진행할 화소(P(i))로 이동하여 추적을 계속한다(130).In this case, when the pixel P (i) to be tracked is determined, the position ROW (P (i)) and COL (P (i)) of the search pixel within the pixel P (i) are stored from the currently tracked pixel. The gradient direction is accumulated (126 to 129.) After the tracking information is updated as described above, the tracking is continued by moving to the pixel P (i) to be tracked (130).

상기 과정 진행 중에 만일, - 추적 방향에 존재하는 탐색 길이내의 화소 중, 그래디언트 방향과 기준 그래디언트 방향과의 차가 최대 방향차 이하이고, 에지 화소이며 추적에 사용되지 않은 화소가 없는 경우는 화소 E에 대한 모든 추적을 종료하고, + 추적 방향으로의 추적에서 저장된 추적단의 정보와 - 추적 방향으로의 추적에서 저장된 추적단의 정보로부터 총 추적 화소의 중앙 화소를 구하여 추적단의 중심으로 결정한다(131).During the process, if the difference between the gradient direction and the reference gradient direction is less than or equal to the maximum direction difference among the pixels in the search length existing in the tracking direction, and there are no pixels that are edge pixels and are not used for tracking, All tracking ends, and the center pixel of the total tracking pixels is obtained from the information of the tracking stage stored in the + tracking direction and the information of the tracking stage stored in the tracking-tracking direction, and determined as the center of the tracking stage (131). .

상기와 같이 한 에지 성분에 대한 세선화가 종료되면 에지 영상을 탐색하고 에지 영역의 화소를 만나면, 다시 위와 같은 과정을 반복하여 세선화를 수행한다.As described above, when the thinning of the edge component is completed, the edge image is searched and when the pixels of the edge region are met, the above process is repeated to perform the thinning.

제5도를 참조하면, 본 발명의 두 단계 처리 과정 중, 그래디언트 방향을 이용하여 세선화를 수행하는 첫 번째 단계인 최소차 추적 방법에 대한 세선화 단계에서는 최소차 탐색 방법은 먼저, 최대 방향차(Dd), 기준 길이(Lb), 탐색 길이(Ls)의 세가지 임계값이 사용되므로, 상기 값을 결정한다(151).Referring to FIG. 5, in the thinning step for the minimum difference tracking method, which is the first step of performing the thinning using the gradient direction in the two-step process of the present invention, the minimum difference searching method is the first and the maximum direction difference. Since three threshold values (Dd), reference length Lb, and search length Ls are used, the value is determined (151).

그리고, 에지 영상을 탐색하다가 에지 화소를 만나면 추적을 시작(152)하는데, 이때의 에지 하소를 E라 표기한다. 상기 화소 E의 위치에 대응하는 원영상에서의 그래디언트의 방향, DIR(E)를 구하고, 이 값을 초기 기준 그래디언트 방향(DIRsum)으로 선택한다. 또한, 추적단 그래디언트 방향의 값을 초기 기준 그래디언트 방향으로 할당한다(153). 이때, 초기 기준 그래디언트 방향을 + 추적 방향으로 결정하고, 180도 위상차를 가지는 방향을 -추적 방향으로 결정한다.When the edge image is encountered while searching for the edge image, tracking is started (152). The edge calcination at this time is denoted as E. The direction of the gradient, DIR (E), in the original image corresponding to the position of the pixel E is obtained, and this value is selected as the initial reference gradient direction (DIRsum). In addition, a value of the tracking end gradient direction is allocated to the initial reference gradient direction (153). At this time, the initial reference gradient direction is determined as a + tracking direction, and a direction having a 180 degree phase difference is determined as a −tracking direction.

먼저, + 추적 방향으로 에지 화소를 추적하는데, 상기 + 추적 방향에 존재하는 탐색 길이내의 화소중, 그래디언트 방향과 기준 그래디언트 방향과의 차가 최대 방향차 이하이고, 에지 화소이며, 추적에 사용되지 않은 화소 중에서 현재 추적된 화소와 가장 가까운 화소로 추적을 진행한다(154 내지 164).First, an edge pixel is tracked in the + tracking direction, wherein a difference between the gradient direction and the reference gradient direction of the pixels within the search length existing in the + tracking direction is equal to or less than the maximum direction difference, and is an edge pixel and is not used for tracking. Tracking is performed to the pixel closest to the currently tracked pixel, from 154 to 164.

상기 추적을 진행하기 위해 먼저, 탐색 기준값 i를 1로 초기화(154)하고, 최소차 거리(DIFFmin)를 999.0으로 초기화(155)한 후, 상기 i 값과 탐색 길이를 비교(156)하여, i 값이 탐색 길이보다 작거나 같은 경우 기준 거리(DIRbase)를 계산(157)한 후, + 추적 방향의 화소(P(i))를 구한다(158).In order to proceed with the tracking, first, the search reference value i is initialized to 154 (1), the minimum difference distance (DIFFmin) is initialized to 1559.0 (155), and then the value i is compared to the search length (156), i If the value is less than or equal to the search length, the reference distance DIRbase is calculated (157), and then the pixel P (i) in the + tracking direction is obtained (158).

그리고, 화소 P(i)에서의 그래디언트 방향 (DIR(P(i)))를 구한 후(159), 상기 DIRbase와 DIR(P(i))의 차(DIFF)를 구하고(160), DIFF와 Dd를 비교(161)하여 DIFF가 Dd 보다 작은 경우 상기 DIFF와 DIFFmin을 비교하여(162) DIFF가 DIFFmin보다 작으면, n 값에 i 값을 저장시킨 후 DIFFmin에 DIFF 값을 저장하고(163), i 값을 1증가시킨 후(164), 상기 추적 과정(156 내지 164)을 반복한다.After obtaining the gradient direction DIR (P (i)) in the pixel P (i) (159), the difference (DIFF) between the DIRbase and DIR (P (i)) is obtained (160). When the DIFF is smaller than the Dd by comparing the Dd (161), comparing the DIFF and the DIFFmin (162). If the DIFF is smaller than the DIFFmin, the i value is stored in the n value and the DIFF value is stored in the DIFFmin (163). After increasing the value of i by one (164), the tracking process (156 to 164) is repeated.

상기와 같은 방법을 최소차 탐색 방법이라 한다.Such a method is called a minimum difference search method.

상기와 같은 방법으로 추적을 진행할 화소 P(n)이 결정되면 현재 추적된 화소로부터 화소 P(n) 이내의 탐색 화소의 위치(ROW(P(n)), COL(P(n))를 저장하고 그래디언트 방향을 누적시킨다(166 내지 169).When the pixel P (n) to be tracked is determined as described above, the position of the search pixels ROW (P (n)) and COL (P (n)) within the pixel P (n) is stored from the currently tracked pixel. The gradient direction is accumulated (166 to 169).

상기와 같이 추적 정보를 갱신하였으면, 추적을 진행할 화소(P(n))으로 이동하여 추적을 계속한다(170).If the tracking information is updated as described above, the tracking information is moved to the pixel P (n) to be tracked to continue tracking (170).

만일, + 추적 방향에 존재하는 탐색 길이내의 화소중, 그래디언트 방향과 기준 그래디언트 방향과의 차가 최대 방향차 이하이고 에지 화소이며 추적에 사용되지 않은 화소가 없는 경우는 + 추적 방향으로의 추적을 종료하고,If the difference between the gradient direction and the reference gradient direction is less than or equal to the maximum direction difference and no pixels are used for tracking among pixels in the search length existing in the + tracking direction, the tracking ends in the + tracking direction. ,

- 추적 방향으로 에지 화소 추적을 시작한다. 이 때 추적단 그래디언트 방향의 값을 DIR(E)로 할당한다(171).Start edge pixel tracking in the tracking direction. At this time, a value of the tracking end gradient direction is allocated to DIR (E) (171).

- 추적 방향에 존재하는 탐색 길이내의 화소 중, 그래디언트 방향과 기준 그래디어트 방향과의 차가 최대 방향차 이하이고, 에지 화소이며 추적에 사용되지 않은 화소중에서 그래디언트 방향과 기준 그래디언트 방향과의 차가 최소인 화소로부터 추적을 진행한다(172 내지 182).The difference between the gradient direction and the reference gradient direction is less than or equal to the maximum direction difference among the pixels in the search length existing in the tracking direction, and the difference between the gradient direction and the reference gradient direction is the minimum among pixels that are edge pixels and are not used for tracking. Tracking is performed from the pixel (172 to 182).

상기 진행과정의 세부 사항은 상기 + 방향의 추적 방향과 동일하고, 방향만 +에서 - 로 바뀐다.Details of the process are the same as the tracking direction of the + direction, and only the direction changes from + to-.

이때, 추적을 진행할 화소(P(n))가 결정되면, 현재 추적된 화소로부터 화소 P(i) 이내의 탐색 화소의 위치 (ROW(P(n)), COL(P(n))를 저장하고 그래디언트 방향을 누적시킨다(184 내지 187).At this time, when the pixel P (n) to be tracked is determined, the position ROW (P (n)) and COL (P (n)) of the search pixel within the pixel P (i) are stored from the currently tracked pixel. And the gradient direction is accumulated (184 to 187).

상기와 같이 추적 정보를 갱신한 후, 추적을 진행할 화소(P(n))으로 이동하여 추적을 계속한다(188).After the tracking information is updated as described above, the tracking information is moved to the pixel P (n) to be tracked to continue tracking (188).

상기 과정 진행 중에 만일, - 추적 방향에 존재하는 탐색 길이내의 화소중, 그래디언트 방향과 기준 그래디언트 방향과의 차가 최대 방향차 이하이고, 에지 화소이며 추적에 사용되지 않은 화소가 없는 경우는 화소 E에 대한 모든 추적을 종료하고, + 추적 방향으로의 추적에서 저장된 추적단의 정보와 - 추적 방향으로의 추적에서 저장된 추적단의 정보로부터 총 추적 화소의 중앙 화소를 구하여 추적단의 중심으로 결정한다(189).During the process, if the pixel in the search length present in the tracking direction has a difference between the gradient direction and the reference gradient direction less than or equal to the maximum direction difference, and there are no pixels that are edge pixels and are not used for tracking, All tracking ends, and the center pixel of the total tracking pixel is obtained from the information of the tracking end stored in the tracking in the + tracking direction and the information of the tracking end stored in the tracking in the tracking direction (189). .

제6도를 참조하면, 본 발명을 구성하는 두 단계의 처리 과정 중, 세선화 조각을 제거하는 두 번째 단계의 흐름은 먼저, 두 번째 단계에서 사용하는 세선화 조각 크기(Af)와 유사오 임계값(Sf)을 결정하고(102), 본 발명의 첫 번째 단계 처리 결과의 영상을 탐색하여 에지 화소를 만나면(202), 8-이웃 화소 연결성을 가지는 세선화된 영역을 찾는다(203).Referring to FIG. 6, in the two-step process of constructing the present invention, the flow of the second step of removing the thinning pieces is first similar to the thinning piece size Af used in the second step. The value Sf is determined (102), and the image of the first step processing result of the present invention is searched to find an edge pixel (202), and a thinned region having 8-neighbor pixel connectivity is found (203).

세선화 영역의 크기를 추출하고(204), 추출된 세선화 영역의 크기와 세선화 조각 크기를 비교(205)하여, 세선화 영역의 크기가 세선화 조작 크기보다 크면 세선화된 에지 성분으로 결정하여 보존하고, 계속해서 상기 첫 번째 단계 처리 결과 영상에서 에지 화소를 탐색하고(202), 추출된 세선화 영역의 크기가 세선화 조각 크기보다 작으면, 본 발명의 첫 번째 단계 처리 입력 영상인 에지 영상의 위치에서 8-이웃 화소 연결성을 가지는 에지 영역을 찾는다(206).The size of the thinning region is extracted (204), and the size of the extracted thinning region and the size of the thinning fragment are compared (205). If the size of the thinning region is larger than the size of the thinning operation, the thinning edge component is determined. If the extracted thinning area is smaller than the size of the thinning piece, the edge of the first step processing input image of the present invention is searched. An edge region with 8-neighbor pixel connectivity at the location of the image is found (206).

그리고, 발견된 에지 영역의 크기를 추출하여(207), 발견된 에지 영역의 크기와 추출된 세선화 영역의 크기의 비로 세선화 결과 영역과 에지 영역의 유사도를 계산한다(208).Then, the size of the found edge region is extracted (207), and the similarity between the thinning result region and the edge region is calculated by the ratio of the size of the found edge region to the size of the extracted thin region (208).

상기 세선화된 영역의 유사도와 유사도 임계값을 비교하여(209), 세선화된 영역의 유사도가 유사도 임계값보다 작으면 세선화된 영역을 세선화 조각으로 결정하여 세선화 결과 영상에서 제거한다(210).By comparing the similarity and the similarity threshold of the thinned region (209), if the similarity of the thinned region is smaller than the similarity threshold, the thinned region is determined as a thinning fragment and removed from the thinning result image ( 210).

상기와 같은 본 발명의 에지 세선화 방법을 사용하면 컴퓨터 비전이나 영상 처리 분양에서 대상체의 경계 에지를 추출하는데 효과적인 능력을 제공하며, 빈 공간인 경우, 잔가지 성분이 존재하는 경우, 이진 영역의 가장 긴축이 대상체의 에지 방향과 다른 방향으로 나타나는 경우 또는 에지 영상에서 인접한 대상체의 경계가 서로 만나는 경우에 기존의 세선화 방법의 왜곡된 경계 생성의 단점을 극복할 수 있다.Using the edge thinning method of the present invention as described above provides an effective ability to extract the boundary edge of the object in computer vision or image processing distribution, and in the case of the empty space, when the twig component is present, the largest contraction of the binary region When the edges of the object appear in a direction different from that of the object or when the boundaries of adjacent objects meet each other in the edge image, the disadvantage of generating the distorted boundary of the conventional thinning method may be overcome.

본 발명은 영상 처리 및 컴퓨터 비전 분야에 있어서, 에지 영상 획득에서 불가피하게 발생되는 여러 화소의 두께를 가지는 에지를 세선화하여 동일한 입력 영상으로부터 더욱 많은 양의 정확한 정보를 획득할 수 있도록 하는 에지 세선화 방법을 제공하는 것을 목적으로 한다.In the field of image processing and computer vision, an edge thinning is performed to obtain a larger amount of accurate information from the same input image by thinning an edge having a thickness of several pixels inevitably generated in edge image acquisition. It is an object to provide a method.

Claims

An edge thinning method comprising: a first step of performing gradient direction based thinning using a shortest distance tracking method; and a second step of removing thinning pieces.

2. The method of claim 1, wherein the first step includes determining a necessary threshold value; and step 120 of searching for an edge image and starting tracking when an edge pixel is encountered; According to step 130, the initial reference gradient direction is assigned, and then the initial reference gradient direction is assigned to the value of the tracking terminal gradient direction, and the tracking pixel gradient direction value assigned in the step 130 is the edge pixel in the + tracking direction. Step 140 of tracking the shortest distance; and if the pixel to be tracked is determined in step 140, storing the search pixel position within the pixel from the currently tracked pixel and accumulating the gradient direction; In step 160, after the tracking information of the step is updated and moved to the pixel to be tracked, the shortest distance tracking is performed; And stop tracking the shortest distance of the edge pixel in the tracking direction, and if the pixel to be tracked is determined in step 170, the search pixel position within the pixel is stored from the currently tracked pixel. Step 180 of accumulating a gradient direction; and step 190 of moving to a pixel to be tracked after updating the tracking information of step 180 and performing tracking; terminating all the tracking of the pixel; Edge thinning method comprising the step of obtaining the center pixel of the pixel.

3. The edge thinning method of claim 2, wherein the operation 110 determines a maximum direction difference, a reference length, and a search length as necessary threshold values.

3. The edge thinning method of claim 2, wherein the step 130 determines an initial reference gradient direction as a + tracking direction, and determines a direction having a phase difference of 180 degrees from the initial reference gradient direction as a tracking direction. .

The method of claim 2, wherein the step 140 comprises: among pixels in the search length existing in the + tracking direction, a difference between a gradient direction and a reference gradient direction is equal to or less than a maximum direction difference, and is an edge pixel and is not used for tracking. An edge thinning method characterized in that the tracking is performed to the pixel closest to the currently tracked pixel.

The pixel of claim 2, wherein the difference between the gradient direction and the reference gradient direction is equal to or less than the maximum direction difference, and the pixels that are not used for tracking are among pixels within the search length existing in the + tracking direction. Edge thinning method, characterized in that the end of the tracking in the + tracking direction if none.

The pixel processing method of claim 2, wherein the step 170 is a method in which the difference between the gradient direction and the reference gradient direction is equal to or less than the maximum direction difference, and is an edge pixel among pixels within the search length existing in the tracking direction. An edge thinning method characterized in that the tracking is performed to the pixel closest to the currently tracked pixel.

3. The method of claim 2, wherein in step 200, a difference between the gradient direction and the reference gradient direction is less than or equal to the maximum direction difference among the pixels in the search length existing in the -tracking direction, and the pixel that is not used for tracking is If none, end all tracking for the initial edge pixel.

2. The method of claim 1, wherein the second step includes selecting a thinning fragment size and a similarity threshold value, and a thinning area having four-neighbor pixel connectivity when the edge pixel encounters the processing result of the first step. Search for step 202, extract the size of the thinned area of step 202, and if the size of the thinned area of step 203 is smaller than the size of the thinning piece of step 201, A step 204 of searching for an edge region having 4-neighbor pixel connectivity at the position of the edge image as the first step processing input image, a step 205 of extracting the size of the edge region of step 204, and a thinning result And calculating the similarity between the region and the edge region, and removing the thinning region if the similarity level of the 206 stage is less than the similarity threshold.

The edge thinning method of claim 9, wherein the similarity of the step 206 is calculated by a ratio of the size of the edge area found in the first step to the size of the thinning area extracted in the step 204.

An edge thinning method comprising: a first step of performing gradient direction based thinning using a minimum difference tracking method; and a second step of removing thinning pieces.

12. The method of claim 11, wherein the first step comprises: step 110 of determining a necessary threshold value; step 120 of searching for an edge image and starting tracking when an edge pixel is encountered; According to step 130, the initial reference gradient direction is assigned, and then the initial reference gradient direction is assigned to the value of the tracking terminal gradient direction, and the tracking pixel gradient direction value assigned in the step 130 is the edge pixel in the + tracking direction. Step 140 of tracking the minimum difference; and if the pixel to be tracked is determined in step 140, storing the search pixel position within the pixel from the currently tracked pixel and accumulating the gradient direction; In step 160, after the tracking information of the step is updated and moved to the pixel to be tracked, the minimum difference tracking is performed; End of the enemy,-step 170 of tracking the edge pixel minimum difference in the tracking direction; and if the pixel to be tracked is determined in step 170, the position of the search pixel within the pixel is stored from the currently tracked pixel, and the gradient A step 180 of accumulating directions; a step 190 of updating the tracking information of step 180 and moving to a pixel to be tracked; and tracking all of the pixels; Edge thinning method comprising the step of obtaining the center pixel 200.

The edge thinning method of claim 12, wherein the operation 110 determines a maximum direction difference, a reference length, and a search length as required threshold values.

The edge thinning method of claim 12, wherein the operation 130 determines an initial reference gradient direction as a + tracking direction, and determines a direction having a phase difference of 180 degrees from the initial reference gradient direction as a tracking direction. .

13. The method of claim 12, wherein the step 140 comprises: among pixels within the search length existing in the + tracking direction, a difference between a gradient direction and a reference gradient direction is equal to or less than a maximum direction difference, and is an edge pixel and is not used for tracking. An edge thinning method, characterized in that tracking is performed with a pixel having a minimum difference between a gradient direction and a reference gradient direction.

The pixel of claim 12, wherein the difference between the gradient direction and the reference gradient direction is equal to or less than the maximum direction difference, and the pixel that is not used for tracking is selected from the pixels within the search length existing in the + tracking direction. Edge thinning method, characterized in that the end of the tracking in the + tracking direction if none.

The pixel processing method of claim 2, wherein the step 170 is a method in which the difference between the gradient direction and the reference gradient direction is equal to or less than the maximum direction difference, and is an edge pixel among pixels within the search length existing in the tracking direction. An edge thinning method, characterized in that tracking is performed with a pixel having a minimum difference between a gradient direction and a reference gradient direction.

12. The method of claim 11, wherein the second step selects the thinning fragment size and the similarity threshold, and in step 201 and the thinning region having the 4-neighbor pixel connectivity when the edge pixel meets the processing result of the first step. Search for step 202, extract the size of the thinned area of step 202, and if the size of the thinned area of step 203 is smaller than the size of the thinning piece of step 201, A step 204 of searching for an edge region having 4-neighbor pixel connectivity at the position of the edge image which is the first step processing input image, a step 205 of extracting the size of the edge region of step 204, and a thinning result And calculating the similarity between the region and the edge region, and removing the thinning region if the similarity level of the 206 stage is less than the similarity threshold.

20. The edge thinning method of claim 19, wherein the similarity of the step 206 is calculated by a ratio of the size of the edge area found in the first step to the size of the thinning area extracted in the step 204.