티스토리 뷰
Boundary Extraction / 경계 표출
Boundaries are linked edges that characterize the shape of an object.
They are useful in computation of geometry features such as size or orientation.
경계선은 물체 형태의 특징이 되는 가장자리 들로 연결이 되어 있다.
그것들은 크기와 방향과 같이 기하학적으로 특징이 되는 것들을 계산하는데 있어서 유용한 것이다.
Connectivity / 연결성
Conceptually, boundaries can be found by tracing the connected edges.
On a rectangular grid a pixel is said to be four or eight connected when it has the same properties as one of its nearest four or eight neighbors, respectively (Fig. 9.14).
There are difficulties associated with these definitions of connectivity, as shown in Fig. 9.14c.
Under four-connectivity, segments 1,2,3, and 4 would be classified as disjoint, although they are perceived to form a connected ring.
Under eight-connectivity these segments are connected, but the inside hole (for example, pixel B)is also eight-connected to the outside (for instance, pixel C).
Such problems can be avoided by considering eight-connectivity for object and four-connectivity for background.
An alternative is to use triangular or hexagonal grids, where three-or six-connectedness can be defined.
However, there are other practical difficulties that arise in working with nonrectangular grids.
개념적으로, 경게선은 연결된 가장자리들을 추적함으로써 찾을수 있다.
직각 그리드에서 픽셀이란 같은 속성을 가진 각각 4개 또는 8개의 이웃한 점들을 연결한 것을 말한다.
9.14의 그림에서 볼수 있듯이 이러한 연결성의 개념을 관련하는 것은 어려움이 있다.
이웃한 4개의 점을 토대로 연결성을 고려할때는 시각적으로는 주변의 4점을 하나의 링처럼 인지되지만 각각 독립적인 4개의 점으로 해체되어 불류된다.
이웃한 8개의 점을 토대로 보면 4점의 연결성에서 바라볼때에 분리된 것들이 연결이 되어보지만
이것 또한 내부 구멍의 일부 한점을 바라보면 바깥쪽에 어느 한 점에서 연결성을 가지게 된다.
이러한 문제점은 네 점의 연결성을 바탕으로하고 여덞 점의 연결성을 물제로써 고려하면 피할수 있는 문제들이다.
또한 다른 대안으로는 삼각그리드나 육각그리드로 생각을 해보면 해결이 가능하다.
그러나 N각그리드에서도 또다른 실질적인 문제점이 발생할 수 있다.
Contour Following / 윤곽선 추적
As the name suggests, contour-following algorithms trace boundaries by ordering successive edge points.
A simple algorithm for tracing closed boundaries in binary images is shown in Fig. 9.15.
This algorithm can yield a coarse contour, with some of the boundary pixels appearing twice.
Refinements based on eight-connectivity tests for edge pixels can improve the contour trace [2].
Given this trace a smooth curve, such as a spline, through the nodes can be used to represent the contour.
Note that this algorithm will always trace a boundary, open or closed, as a closed contour.
This method can be extended to gray-level images by searching for edges in the 45° to 135° direction from the direction of the gradient to move from the inside to the outside of the boundary, and vice-versa [19].
A modified version of this contour-following method is called the crack-following algorithm[25].
In that algorithm each pixel is viewed as having a square-shaped boundary, and the object boundary is traced by following the edge-pixel boundaries.
이름 그대로 윤곽선 추적 알고리즘은 연속적인 가장자리 점을 따라감으로써 경계를 추적한다.
바이너리 이미지에서 근접한 경계를 추적하기 위한 이런 단순한 알고리즘은 9.15에서 보여진다.
이 알고리즘은 중복되는 몇몇의 경계 픽셀로 거친 윤곽을 산출해낼수 있다.
(예를 들어 동일한 선상에서 대략적으로라도 비슷한 방향으로 진행하는 두 점이 있다면 그 두 점을 하나의 윤곽이라고 봐도 무방하다고 본다.)
앞서 언급했던 8개의 점을 토대로 한 연결성 테스트를 기반으로 한다면 윤곽 검출이 좀 더 개선될수 있다.
만약 어떤 Spline같은 커브가 주어진다면 그것을 통해 윤곽을 표현하는데 있어서 노드들을 사용할수 있을것이다.(?)
이 알고리즘에서는 항상 가까운 윤곽으로써 개경계,폐경계 추적을 할것이다.
이 방법론은 경계 안에서 밖으로 또는 밖에서 안으로 이동하기 위해 미분방향으로 부터 45도에서 135도 사이의 가장자리를 찾음으로써 그레이 레벨 이미지에서도 확장될 수 있다.
이미 완화된 버전의 윤곽 추적으로 crack-following algorithm이라고 불리는 방법이 있다.
이 알고리즘에서 각각의 픽셀은 사격형 모양의 경계를 가지고 그 물체의 경계는 가장자리 픽셀의 경계를 따라 추적된다.
Edge Linking and Heuristic Graph Searching[18-21] / 가장자리 연결과 휴리스틱 그래프 탐색
A boundary can also be viewed as a path through a graph formed by linking the edge elements together.
Linkage rules give the procedure for connecting the edge elements.
Suppose a graph with node locations xk, k=1,2,... Is formed from node A to node B.
Also, suppose we are given an evaluation function ¢(xk), which gives the value of the path from A to B constrained to go through the node xk.
In heuristic search algorithms, we examine the successors of the start node and select the node that maximizes ¢(·).
The selected node now becomes the new start node and the process is repeated until we reach B.
The sequence of selected nodes then constitutes the boundary path.
The speed of the algorithm depends on the chosen ¢(·) [20,21].
Note that such an algorithm need not give the globally optimum path.
경계는 또한 가장자리 요소들을 연결함으로써 형성되는 그래프를 통해 경로로 나태낼수 있다.
결합 규칙은 가장자리 요소들을 연결하기 위한 순서로 주어진다.
그래프에서 노드 A로부터 노드 B를 연결하기 위한 X가 있다고 가정해보자.
또한 노드 X를 통해 가기 위한 A로부터 B까지의 제한적인 경로의 가치를 평가하는 함수를 Pi(X)라 하자.
휴리스틱 탐색 알고리즘에서 성공적인 시작 노드를 모색하고 Pi(X)가 최대가 되는 노드를 선택한다.
그렇게 선택된 다음 노드는 또 새로운 노드가 되고 이 과정은 B에 도달할때 까지 계속 반복된다.
이와같이 선택된 노드들의 순서가 경계 경로로 여겨진다.
이 알고리즘의 속도는 선택된 평가함수에 의존한다.
이런 알고리즘은 전세계적인 최고의 경로를 줄 필요는 없다.
Example 9.2 Heuristic search algorithms[19]
Consider a 3 × 5 array of edges whose gradient magnitudes lg and tangential contour
directions e are shown in Fig. 9.16a.
The contour directions are at 90° to the gradient directions. A pixel X is considered to be linked to Y if the latter is one of the three
eight-connected neighbors(Y, K, or h in Fig. 9.16b) in front of the contour direction
and if le(x)-e(y)1<90°. This yields the graph of Fig. 9.16c.
As an example, suppose ¢(xk) is the sum of edge gradient magnitudes along the
path from A to xk. At A, the successor nodes are D, C, and G, with ¢(D) =12,
(C) =6, and ¢(G) =8. Therefore, node D is selected, and C and G are discarded.
FTom here on nodes E, F, and B provide the remaining path. Therefore, the boundary
path is ADEFB. On the other hand, note that path ACD EFB is the path of maximum
cumulative gradient.