220420_유명조달기업
영상 감시 시스템을 위한 에이전트 기반의 자동화된 카메라 배치
상태바
영상 감시 시스템을 위한 에이전트 기반의 자동화된 카메라 배치
  • CCTV뉴스
  • 승인 2010.07.29 00:00
  • 댓글 0
이 기사를 공유합니다

유비쿼터스(Ubiquitous)는 1993년 마크 와이저(Mark Weiser)에 의해 발표된 이후에 많은 형태의 기술과 문화적 키워드로써 모습을 달리하여 소개되었으며, 정보화 시대 이후 급속도로 성장한 IT기술로 시공간의 제약을 초월하여 사용자에게 네트워킹 서비스를 지원해줄 수 있는 유비쿼터스 시대가 도래 하였다.

지능형 영상감시 시스템은 카메라를 통해 사람과 객체들을 모니터링하고 위험 상황에 대해 즉각적으로 대응하는 대표적인 유비쿼터스 시스템으로, 시뮬레이션을 통하여 시스템 엔지니어로 하여금 효과적인 유비쿼터스 시스템을 구축할 수 있는 방법에 대한 연구가 선행되어야 한다. 지금까지 지능형 영상 감시 시스템은 주로 효과적인 객체 인식이나 다중 카메라에서의 객체 추적 알고리즘에 대한 연구가 주였지만, 앞으로의 지능형 영상감시 시스템은 단일 카메라의 기능 개발이 아닌 지능공간에서의 다수의 카메라가 유기적으로 협업된 형태의 시스템으로 제한된 비용에서 효과적으로 객체 인식 및 추적이 이루어질 수 있도록 최적의 카메라 배치에 대한 연구가 필요하다.

본 고에서는 효율적인 카메라 배치를 위해 카메라의 FOV(Field Of View)를 기반으로 감시 영역의 커버리지를 계산하였으며, 가상 에이전트들의 이동패턴을 모델링하여 공간 중요도(Space Priority)를 계산하였다. 또한, 최소의 비용으로 공간을 커버할 수 있는 카메라 배치 알고리즘을 구현하고 실제 건물을 모델링하고 가상의 카메라들의 성능과 비용을 입력하여 시뮬레이션하였다. 

공간과 에이전트 모델링

카메라의 위치와 방향에 대한 최적의 배치를 계산하기 위해, 우선 공간을 모델링하고 사람들이 이동하는 경로를 추출한 후, 사람들의 유동량을 계산해야 한다. 그림 1은 이러한 카메라 배치를 위한 시뮬레이션 순서이다. 우선 모델링된 지형정보와 에이전트 데이터를 입력하고, 공간 중요도를 계산하여, 최적의 카메라 배치 위치를 판단한다.



공간 모델링
본 고에서는 시뮬레이션에 사용하는 공간을 2차원 맵으로 모델링하였으며, 보행자의 이동 경로와 유동량을 계산하기 위해 가상의 에이전트를 모델링하였다. 공간은 그림 2와 같이 3가지 레이어로 구성하였다.


지형 레이어는 공간에서 사람이 이동 가능한 영역과 이동이 불가능한 영역으로 구분하였으며, 이진 배열 형태로써 경로탐색 알고리즘에 적용하였다. 영역 레이어는 특정 영역을 원의 형태로 구성하여 속성정보와 함께 저장된 레이어이다.

영역 레이어의 속성은 위치, 범위, 유동량, 이동확률로 구성된다. 유동량은 영역을 통과하는 사람의 이동량이며, 이동확률은 한 영역에서 다른 영역으로 이동할 확률이다. 공간 중요도 레이어는 지형 레이어와 영역 레이어로부터 생성되고, 경로탐색으로 계산된 공간 중요도를 통해 업데이트된다.

에이전트 모델링

1. 에이전트의 경로 탐색 알고리즘
에이전트는 공간에서 이동 가능한 모든 경로를 생성하며, 이를 통해 이동 가능한 영역과 빈번도가 높은 이동 경로를 추출한다. 한 지점에서 다른 지점으로 이동하더라도 사람의 감성, 사전지식, 주변 환경 등 다양한 요인에 따라 경로선택의 우선순위가 달라지기 때문에 여러 가지 경로가 나타난다.

그림 3에서 보는 바와 같이, 최단거리를 우선순위로 하는 경로탐색 알고리즘으로 구한 경로는 사람의 경로선택과 다르게 나타나는데, 이것은 에이전트가 모든 지형을 학습하고, 시야와 방향전환 등을 고려하지 않았기 때문이다.



본 고에서는 이러한 에이전트의 이동경로와 사람의 이동경로에 대한 차이를 줄이기 위하여, 경로탐색 알고리즘으로 추출한 경로에서 주변의 가용 경로를 예측하여 다양한 경로들을 생성하였다. 에이전트는 알고리즘 1을 이용하여 모든 목적지에서 이동 가능한 모든 영역을 검사하는 방법으로 경로탐색 시뮬레이션을 수행한다.

<알고리즘 1> 에이전트 경로탐색 알고리즘
1. 선택되지 않은 목적지가 존재하지 않는다면 시뮬레이션을 끝내고, 그렇지 않다면 현재 위치에서의 확률분포에 근거하여 목적지를 선택한다.
2. 목적지까지의 경로를 경로탐색 알고리즘을 통해 탐색한다.
3. 탐색된 알고리즘상의 경로에서 영역 속성정보에 따라 경로확장 알고리즘을 사용하여 경로를 확장한다.
4. 구한 모든 확장 경로 상에 존재하는 이동 가능한 지역의 공간 중요도를 영역 확률분포에 따라 공간 중요도 레이어에 업데이트한다.
5. 목적지를 현재 위치로 변경하고 1번으로 돌아간다.

 2. 에이전트의 경로 확장 알고리즘
A* 알고리즘은 휴리스틱 탐색(Heuristic Search)과 그래프 탐색(Graph Search) 알고리즘을 기반으로 최단경로와 최소비용으로 경로를 탐색한다. 본 연구에서 시뮬레이션에 적용한 A* 알고리즘은 다음과 같다.

 <알고리즘 2> A* 알고리즘
1. 시작노드 A를 리스트 OPEN에 넣는다. A를 최초의 탐색트리 T에 저장한다.
2. 빈 리스트 CLOSED를 정의한다.
3. OPEN이 비어 있는지 확인해보고 비어있다면 탐색 실패를 반환한다.
4. OPEN에서 첫 번째 노드를 선택하여 An으로 정하고 CLOSED에 넣는다.
5. An이 목표 노드이면 A에서 An까지의 경로를 추적하여 반환한다.
6. 노드 An에 연결된 모든 노드들을 탐색 트리 T에 저장한다.
7. 연결된 모든 노드들을 OPEN에 넣는다.
8. 휴리스틱과 기타 요소값에 따라 OPEN 내용을 재정렬한다.
9. 단계 3으로 되돌아간다.

 본 고에서는 A* 알고리즘을 이용하여 2차원 그리드 기반 맵의 방향을  8가지로 구분하고 휴리스틱 평가함수를 다음과 같이 정의함으로써, 에이전트 경로탐색에 A* 알고리즘을 사용하였다. 

 
     (1)

g는 시작 노드에서 현재 노드까지의 이동 비용의 합이며 h는 현재 노드에서 도착 노드까지의 장애물을 제외한 이동비용의 합이다. 따라서 g와 h의합인 f가 A* 알고리즘에서 경로탐색의 우선순위를 정하는 최종 기준이 된다. 이때 사용한 이동 비용은 상하 좌우 방향은 1, 대각선 방향은 1.4의 비용으로 정하였으며, 노드간의 이동 비용은 맨하탄 기법(Manhattan Method)으로 계산하였다.

A* 알고리즘을 통해 생성한 이동 경로와 사람의 이동 경로는 차이가 발생하기 때문에 이러한 차이를 줄이기 위해, A* 알고리즘으로 추출한 경로 주변의 이동 가능한 공간 중 사람이 이동할 수 있는 영역을 추론하여 공간 중요도 레이어에 중요도를 재계산하였다. 경로 확장 알고리즘의 추론 과정은 다음과 같다.

<알고리즘 3> 에이전트 경로 확장 알고리즘
1. 영역 속성정보에 따른 출발지점, 도착지점의 영역범위 r1, r2를 구한다.
2. 출발지점의 영역범위 r1의 크기에 따라 확장 출발지점 개수 n을 구하고, 영역 범위 내에 n개의 확장 출발지점 위치를 정한다.
3. 도착지점의 영역범위 r2의 크기에 따라 확장 출발지점 개수 m을 구하고, 영역 범위 내에 m개의 확장 출발지점 위치를 정한다.
4. 출발지점을 포함한 확장 출발지점 n+1개, 도착지점을 포함한 확장 도착지점 m+1개에 대해 A* 알고리즘을 적용하여 (n+1)*(m+1)개의 추가 경로를 탐색한다.
5. 각 경로들의 선에 의해 둘러싸인 그리드들을 검색하여 확장영역으로 추가한다.
6. 추가된 모든 경로에 대한 Grid와 5번에 구한 그리드들을 확장영역으로 리턴한다. 

카메라 배치

지금까지, 지형정보를 모델링하고 가상의 에이전트들을 통해 경로를 추출하고 공간 중요도를 계산하였다. 이러한 값으로 FOV가 커버하는 경로비율과 경로확률을 계산하여 카메라 배치를 결정한다.

 1. 카메라의 FOV 모델링
시뮬레이터에서 사용할 카메라의 FOV는 그림 4에서 보는 바와 같이, 카메라의 위치를 기준으로 인식거리와 가용각도로 이루어진 삼각형의 구조를 가진다.
카메라의 위치는 2차원 그리드 맵에서 (x, y)의 정수좌표이고 0˚~360˚의 각도를 갖는다. 즉, 카메라의 FOV는 카메라의 위치 (Cx, Cy), 위치 각도 Φ, 인식거리 d, FOV 각도 a의 구성요소를 갖는다.



카메라 FOV를 구하기 위하여 식 2와 같이 카메라 위치를 원점으로 이동시킨 새 좌표에 대입시킨다. 

   
        (2)

x축을 기준으로 대칭된 삼각형으로 변환하게 되면 다음과 같은 식을 얻을 수 있다.
     
     (3)
    
      (4)

따라서 위의 식으로부터 아래와 같은 식을 계산할 수 있다. 

     
            (5) 

    
       (6) 

    
       (7)

(5),(6),(7)의 식은 카메라의 인식거리와 FOV 각도에 대한 식으로 (2),(3),(4)의 값들을 대입하면 아래 (8),(9),(10)과 같이 변환할 수 있으며, 시뮬레이션에서는 아래의 식과 일치하는 영역을 카메라의 시야 한계로 정한다. 

    
      (8) 

  
       (9) 
 
  
        (10)

FOV를 그리드에 기반 한 영역 소거 방법으로 모델링하여 실제 FOV 내의 오브젝트 인식률을 추정하거나 장애물에 대한 시야간섭을 고려할 수 없다. 따라서 오브젝트에 대한 인식률 계산을 위해, FOV 영역 내에 장애물이나 벽과 같은 보행불가 영역은 FOV 내에서 차지하는 비율에 따라 중요도를 다르게 할당함으로써 시야간섭을 고려하였다.

FOV 내의 영역에 대한 이동 가능한 영역의 공간 중요도는 식 11과 같다. 

     
            (11)

WalkableGridRatio는 보행 가능 공간의 비율로써 전체 지형 레이어 상에서 FOV 내에 있는 비율을 계산하여 공간 중요도를 재계산한다. A* 알고리즘으로 추출한 경로에 해당하는 그리드는 FOV 내에 해당 경로를 포함하는 정도에 따라 공간 중요도가 결정된다. 영역 레이어의 속성정보에 저장된 해당 경로의 확률에 따라 경로의 중요도를 계산하여 경로확률(Path Probability)를 정하고, 경로 상에 나타나는 모든 그리드의 수를 경로비율(Path Ratio)라고 할 때, 지형 레이어 전체의 경로비율에서 FOV가 커버하는 경로비율과 경로확률로 공간 중요도를 결정한다. A* 알고리즘으로 추출한 경로의 공간 중요도 계산식은 식 12와 같다. 

      
        (12)

확장경로에 대해서는 A* 알고리즘으로 추출한 경로와 같은 방법으로 계산하고 파생된 확장경로의 수에 따라 경로확률을 나누어 계산하며 계산식은 식 13과 같다. 

     
            (13)

벽과 장애물의 경우 공간 구분으로 장애물의 그리드 하나가 FOV를 얼마나 차지하는지를 파악하는 것은 어렵기 때문에, 벽과 장애물의 경우는 FOV 내의 이동 불가능한 영역인 이동불가지형(Unwalkable Grid)의 비율을 계산하여 공간 중요도를 감소시켰다. 계산식은 식 14와 같다. 

   
          (14)


배치 위치 선택
카메라의 배치 위치를 선택하기 위해 그리디 알고리즘을 이용하였다. 시뮬레이션 공간 모델의 영역 속성에서 공간 중요도와 에이전트의 경로탐색 알고리즘으로부터 얻은 경로 정보를 바탕으로 공간 중요도 레이어를 추출한다. 카메라의 배치에 대한 위치 선택은 공간 중요도 레이어를 통해 배치위치를 선택하게 되며, 공간 모델의 모든 좌표 점들을 비교하여 카메라 FOV를 통해 공간 중요도가 가장 높은 위치를 정한다. 최적의 위치는 각 좌표 점을 기준으로 적합도(Suitability)를 계산하여 찾아내며, 적합도는 카메라의 비용과 성능에 따라 다르기 때문에, 모든 좌표 점과 카메라 타입에 따른 적합도 계산식은 아래 식 15와 같다. 

   
         (15)

적합도는 해당 그리드 좌표에서 모든 방향에 대해 FOV 내에 공간 중요도가 최대인 위치 각도를 계산한 후, 그 위치 각도에서 얻은 공간 중요도를 카메라 비용으로 나누어 계산한다.    가장 높은 적합도를 갖는 그리드의 순서대로 카메라 위치가 결정되고, 적합도 맵은 재구성 된다.

공간 중요도 레이어에 설치된 카메라들의 FOV를 통해 공간 모두가 커버된다면 카메라 배치는 종료되지만, 공간 중요도를 충족하는 것만으로 최적의 카메라 배치라고 할 수 없기 때문에 본 고에서는 카메라의 최적 배치를 위해 배치 한계비용을 고려하였다. 배치 한계비용은 한계비용을 초과하지 않는 최대의 카메라 개수이며, 알고리즘은 아래와 같다.

<알고리즘 4> 카메라 배치 알고리즘
1. 그리디 알고리즘에 의한 모든 공간 맵에서 카메라 FOV에 의한 커버리지와 비용을 고려한 적합도 맵을 구한다.
2. 적합도 맵에서 가장 높은 공간 중요도의 그리드 좌표를 선택한다.
3. 카메라를 배치하고 배치 리스트에 업데이트한다.
4. 배치 개수가 임계값 이상이면 배치를 종료한다.
5. 배치된 카메라 위치 주변의 적합도 맵을 초기화 한다.
6. 2번으로 돌아간다.

시뮬레이션

시뮬레이션 환경
카메라의 최적화된 배치를 위해 건물의 1 층 내부를 모델링하고 시뮬레이션하였다. 공간내의 이동하는 사람들의 수와 이동경로를 추출하기 위해서, 4층에 카메라를 설치하였다. 설치된 카메라를 통해 24시간 동안 모니터링을 하여 시뮬레이션을 위한 확률모델로 사용하였다. 

  
  

시뮬레이션 툴은 Visual C++ 6.0로 개발하였으며, CPU 2GHz와 1G RAM의 PC 2대를 이용하여 시뮬레이션 하였다. 그림 6에서 보는 바와 같이 영역과 공간 데이터 입력을 위한 인터페이스를 구현하고, 경로탐색과 배치위치선택 알고리즘을 적용하여 시뮬레이션하였으며, 시뮬레이션을 완료하는데 소요된 시간은 약 6시간이었다.
 


시뮬레이션 데이터
시뮬레이션에 사용된 데이터는 건물의 2차원 도면을 이용하여 모델링하였으며, 지형 레이어로 전달하는 과정을 거쳐 시뮬레이션하였다. 모델링된 도면은 그림 7과 같다.


모니터링을 통해 얻은 데이터를 바탕으로 공간의 각 영역을 설정하고 에이전트들의 이동 목적지를 정하여 공간 중요도를 위한 영역 레이어의 속성정보를 입력하였다. 입력한 건물의 20개의 영역은 표 1과 같다.



건물의 구조에 따라 좌표와 범위를 정하였으며, 유동량에 따라 가중치를 정하였다. 영역 간의 이동 확률은 표 2와 같이 모니터링한 사람의 이동 횟수를 백분율로 변환하여 영역 속성정보에 적용하였다.

공간 중요도
공간 중요도 계산을 위해 표 1과 표 2의 데이터를 경로탐색 알고리즘에 사용하였다.

우선 각 목적지간의 최소 경로를 탐색하여 경로를 배열화하고, 경로확장탐색 알고리즘을 적용하여 기존 경로에서 확장 가능성이 있는 영역을 함께 고려하여 공간 중요도를 계산하였다. 경로탐색 알고리즘의 적용결과는 그림 8과 같다.






마지막으로 영역 레이어의 속성정보와 공간 중요도 레이어를 이용하여 공간 중요도를 배열의 형태로 계산하였다. 그림 9는 공간 중요도의 일부를 보이고 있다. 공간 중요도 배열은 카메라 배치 위치를 결정하기 위한 입력 값으로 사용된다.


카메라 배치위치 결정
카메라의 성능에 따라 카메라 배치가 달라질 수 있기 때문에 카메라의 종류를 세 가지로 나누어 시뮬레이션 하였다. 시뮬레이션에 사용된 카메라 성능은 아래 표 3과 같다. 카메라 B는 카메라 A보다 시야거리가 1.5배 길지만, 시야각은 0.75배 작다. 카메라 C는 시야거리가 카메라 A보다 2배 길지만 비용은 2.5배 크다.


그리디 알고리즘기반의 배치 알고리즘을 이용하여, 세 가지 카메라에 대한 적합도를 계산하였다. 카메라 적합도 그래프는 그림 10과 같다. 

  
  

적합도 그래프의 x와 y축은 모델링된 2차원 공간의 좌표이다. 적합도의 값이 높은 순서대로 카메라를 배치하여 최적의 카메라 배치에 대한 조건이 만족할 때까지 배치를 반복한다. 그림 11은 이러한 방법으로 20개의 카메라를 배치를 할 때 공간 중요도 커버리지의 변화를 보이고 있다.


그림 11-(가)와 (나)에서 보는 바와 같이, 카메라 C의 경우, 단위 개수당 공간 중요도 커버리지가 초기 배치에는 가장 높지만, 비용 당 공간 중요도 커버리지는 카메라 배치 개수가 증가할수록 낮아졌다. 이것은 건물의 내부에는 벽과 같은 영역이 존재하기 때문에 카메라의 시야거리가 길고, 시야각이 넓어도 불필요하기 때문이다. 또한 그림 11-(다)에서 보는 바와 같이, 적합도가 높은 순서대로 카메라가 배치되므로, 공간 중요도 커버리지 비율은 처음에는 높은 증가율을 보였지만, 점차 증가율이 낮아지는 것을 확인할 수 있었다. 예를 들어, 카메라 C는 15대 이후의 공간 중요도 커버리지는 단위 개수당 0.08% 이하였다.

시뮬레이션의 종료 조건으로 카메라 배치 한계비용을 500, 1000, 12000, 1500으로 정하여 세 가지 카메라에 대해 각각 시뮬레이션 하였다. 한계비용 내에서 카메라 A, 카메라 B, 카메라 C의 최대의 배치 개수를 구하고, 그 배치 개수에서 최대 공간 중요도 커버리지의 최대값을 계산하여 그 중 가장 높은 공간 중요도 커버리지를 나타낸 카메라를 선택하였다. 시뮬레이션을 통해 구한 최적의 카메라 개수와 커버리지에 대한 결과는 그림 12와 같다.



그림 12에서 보는 바와 같이, 한계 비용이 500, 1200, 1500일 때 카메라 A가 공간 중요도 커버리지가 가장 높았으며, 한계비용이 1000일 때 카메라 C가 가장 높았다. 이러한 최적의 카메라 개수와 커버리지에 대해 카메라 배치에 대한 시뮬레이션 결과는 그림 13과 같다. 

 

그림 13에서 삼각형은 카메라의 FOV이며, 삼각형내의 선은 카메라의 방향이다. 삼각형의 두 변과 삼각형 내에 직선이 만나는 점이 카메라의 위치이다.

카메라의 배치는 사람이 이동할 가능성이 높고 여러 경로들이 중첩되지 않는 홀 지역보다는 좁은 통로가 공간 중요도가 높게 집중되었다. 또한, 카메라 형태에 따라 우선으로 배치되는 위치가 달랐다. 넓은 홀을 2~3대 만으로 커버할 수 있는 카메라 C의 경우 카메라 A와 카메라 B와 달리 좁은 통로보다는 경로들이 분산되어 있지만 거의 모든 경로들이 통과하는 위치인 홀에 우선으로 카메라들이 배치되는 것을 알 수 있었다.

결론

본 고는 효과적인 영상 감시 시스템 구축을 위하여 에이전트를 기반으로 최적의 카메라 배치에 대해 시뮬레이션하였다.

A* 알고리즘기반으로 사람의 이동을 추론하여 에이전트를 모델링하고 구현하였다.

또한 A* 알고리즘으로 추출한 경로 주변의 이동 가능한 공간 중 사람이 이동할 수 있는 영역을 추론하였으며, 공간 중요도 레이어에 중요도를 재계산하여 경로확장 알고리즘을 구현하였다. 실제 공간에 대한 공간의 구조와 사람의 유동량을 측정하여 확률 모델로 이용하였으며, 카메라의 성능과 비용을 시뮬레이션의 변수로 하여 최적의 카메라 배치 위치를 결정하였다.

향후의 연구로는 도시단위의 공간에서 다양한 성능의 카메라들을 조합하여 설치하는 경우에 효율적인 카메라 배치가 가능하도록 최적화하는 것이다.

<본 고는 지식경제부 "지식경제 프론티어 기술개발사업"의 '유비쿼터스 컴퓨팅 및 네트워크 원천 기반 기술 개발 사업'의 일환으로 추진된 연구 결과물이다>





남윤영 박사
(young022@gmail.com)
아주대학교 유비쿼터스컨버전스연구소 /연구교수 




댓글삭제
삭제한 댓글은 다시 복구할 수 없습니다.
그래도 삭제하시겠습니까?
댓글 0
0 / 400
댓글쓰기
계정을 선택하시면 로그인·계정인증을 통해
댓글을 남기실 수 있습니다.