백과

[1] 인공지능 분야. 그래프의 인접 노드간에 구속이 주어져 있는 경우, 그 구속을 만족시킬 수 있도록 노드에 라벨을 붙이는 방법(구속에 의거하는 검색 참고). 인공지능의 문제해결에서 흔히 쓰인다. 최초로 모든 노드에 대해서 라벨의 후보집합이 주어져 있다. 각 노드에 대해서, 라벨의 후보집합의 안에서부터 인접 노드의 라벨의 후보집합과 모순되는 것을 없앤다. 모든 노드에 대해서 이 처리를 한 후, 다시 새 후보집합에 대해서 같은 처리를 반복한다. 어느 노드에서나 라벨의 후보집합이 갱신될 수 없게 되면 처리를 종료한다.

완화법이 종료되었을 때, 모든 노드의 라벨 집합이 단 하나의 라벨을 지니고 있으면 그것이 답이다. 그렇지 않으면 축차처리에 의해 가능한 라벨부의 조를 모두 구한다. 이와 같이 하여 국소적 구속을 만족하는 해를 구한다. 완화법의 원리는 편미분방정식의 수치해법의 완화법이나, 화상처리의 확률적인 완화법과 같다(완화법 참고). 완화법은 음성이해나 화상이해에 있어서, 추출한 특징(예를 들면 선화)을 모순 없이 해석하는 문제로 응용되어 있다.

[2] 패턴 정보처리 분야. 화상의 반복처리(iterative opration)의 대표적 수법. 화상에서 추출된 특징의 집합을 A={a₁, a₂, ⋯, a_n}, 특징이 가능한 해석을 나타내는 라벨의 집합을 A={λ₁, λ₂, ⋯, λ_m} 라고 했을 때, 이하에 나타내는 반복계산에 의해서, 특징 a_i가 라벨 λ_i를 가지는 확률 P_i(λ_i)를 구하는 방법이다. k회째의 반복에서 확률을 P_i^(k)(λ_l)로 하면, k+1회째의 확률은

로 나타내어진다. d_ij는 특징 a_j가 a_i에 미치는 영향의 강도를 나타내는 계수로서 는 특징 a_i의 라벨 λ_l과 a_j의 라벨 λ_r 사이의 정합성을 나타내는 적합계수로서 -1≦r_ij(λ_l, λ_r)≦1. 초기확률 P_i⁽⁰⁾(λ_l)은 특징 a_i를 가지는 성질에 의거해서 계산된다. 완화법에서는, 각 특징을 가지는 국소적인 성질에 더해, 주위의 특징과의 정합성을 고려해서 라벨부가 행해져, 정합성이 있는 대국적인 해석이 구해진다. 완화법은 평활화(잡음제거 참고), 에지 검출, 선추출, 영역의 형상조합, 입체시나 동화상 해석에 있어서의 특징점의 대응부 등 여러 가지 처리에 이용된다.