Spatial index를 이용한 웹 어플리케이션 최적화
안녕하세요, 뷰노의 SW최적화 파트장 김상근입니다.
뷰노는 의료영상, 음성인식 그리고 신호처리 분야의 인공지능을 만들고 있습니다. 이 글에서는 의료영상 중 병리학(Pathology) 분야에서 사용하는 병리 뷰어 프로젝트의 소개와 이를 진행하면서 만난 재미있는 문제 및 해결방법에 대해 설명하려고 합니다.
Pathology
병리학은 질병의 본질적 성질을 연구하는 의학의 한 분야로서 세포, 조직, 장기의 표본을 육안이나 현미경 등을 이용하여 검사해, 그것들이 질병에 침범되었을 때에 어떤 변화를 나타나는지에 대하여 연구하는 학문이다. — wikipedia
병리학에서 사용하는 슬라이드에는 현미경으로 보아야 관찰할 수 있을 정도로 굉장히 작은 세포, 근육, 지방 등 여러 조직이 모여있습니다. 이러한 슬라이드를 컴퓨터로 분석하기 위해 슬라이드 스캐너를 이용하면 마이크로미터 수준의 고해상도 이미지로 변환됩니다. 따라서 슬라이드 한 장당 보통 수십억개의 픽셀로 이루어져 있습니다(이미지 한 장의 크기: 100MB ~ 10GB).
Gland
분비선(Gland) 상피에서 발생하는 악성 종양이 가장 흔한 암(선암)의 형태를 띄기 때문에, 일반적으로 분비선의 형태는 여러 선암의 악성 정도를 평가하는데 쓰인다. — GlaS@MICCAI’2015: Gland Segmentation Challenge Contest
Gland는 생체물질을 합성하는 조직으로, 대부분의 장기에 존재하는 중요한 구조입니다. 뷰노의 머신러닝 연구팀에서는 딥러닝을 이용하여 Gland를 찾는 인공지능을 만들었고, SW개발팀에서는 해당 인공지능을 적용하여 HTML5 Canvas에서 슬라이드 이미지를 시각화하고 Gland를 그려주는 웹 어플리케이션을 제작했습니다.
Project requirements
병리 뷰어 프로젝트는 아래의 기능을 필요로 했습니다.
- 고해상도 슬라이드 이미지와 Gland를 시각화
- 이미지 뷰어의 확대/축소/이동이 가능해야함
- Gland의 추가/수정/삭제가 가능해야함
Library
UI 라이브러리는 React를 사용했고, 고해상도 슬라이드 이미지를 보여주기 위해 Openseadragon을 사용했습니다. 슬라이드 이미지의 크기가 굉장히 크기 때문에 원본 이미지를 캔버스에 바로 띄우지 않고, 확대 축소 레벨과 현재 viewport에 해당하는 Tiled 이미지를 서버에서 가져오는 방식으로 구현했습니다.
Problem
Openseadragon의 도움을 받아 슬라이드 이미지를 보여주고, 확대/축소/이동 등의 기능은 잘 동작하도록 구현 했으나, 문제는 인공지능 모델이 찾은 Gland를 이미지 위에 그리는 작업이 사용하기 힘들 정도로 느렸습니다. 원인은 슬라이드 한 장에서 찾은 Gland의 수가 굉장히 많았고, 이를 HTML5 Canvas에 그리는 작업이 굉장히 느렸기 때문입니다.
심지어 위 슬라이드의 크기는 300MB정도의 크기인데, 용량이 큰 슬라이드의 경우 GB단위의 크기를 갖는다는 것이 더 큰 문제입니다. 사용자가 사용할 수 없을 정도로 초기 로딩 속도가 느렸기 때문에, 사용성을 높이기 위한 방법이 필요했습니다.
Approach 1. 이미지 포맷으로 그리기
기존에 인공지능 모델의 Heatmap을 슬라이드 이미지 위에 덧씌우는 기능이 있었기에 Gland들을 이미지 포맷으로 압축하여 그리려는 생각을 해봤습니다. 하지만 사용자가 Gland를 추가/수정/삭제를 할 수 있어야 하는데, 이미지 포맷으로는 기존 Gland의 정보가 날아가기 때문에 사용할 수가 없었습니다.
Approach 2. 현재 화면에 보여지는 부분의 Gland만 그리기
확대한 경우 보여지는 부분에 존재하는 Gland만 그려준다면 그려야 하는 Gland의 숫자가 현저히 줄어들게 됩니다. 하지만 이 방법도 마찬가지로 확대하기 전의 뷰에는 모든 Gland가 존재하기 때문에 문제가 있습니다.
Approach 3. 현재 보여지는 Canvas에서 한 픽셀에 중복된 점 제거
고해상도의 슬라이드 이미지여도 Canvas에 그려지는 이미지의 크기는 작습니다. 하지만 Gland를 구성하는 점들의 좌표는 실제 슬라이드 이미지 원본의 좌표계를 따르기 때문에, Canvas에 그려지는 점들이 화면 한 픽셀에 중복되어 그려지게 됩니다. 따라서 확대/축소 시 한 픽셀에 중복되는 점을 제거하여 그려주면 점의 개수가 꽤 줄어들게 됩니다. (15917 -> 3428 (78% 감소))
Approach 4. 수정이 가능한 확대/축소 레벨보다 높은 경우 그룹화
슬라이드 이미지를 어느정도 확대하지 않으면 Gland를 확인하기가 쉽지 않습니다. 따라서 특정 확대 레벨이 되기 전까지는 이 곳에 Gland가 존재하는지를 알 수 있도록 Gland를 그룹화하여 그려야 하는 Gland의 숫자를 줄여줍니다. 수정할 수 있는 확대 레벨이 되면 이미 화면에 포함되어 있는 Gland의 숫자가 적기 때문에 그룹화를 하지 않고 그려줍니다. (400 -> 154 (62% 감소))
Implementation
위 Approach 2, 3, 4를 전부 적용하여 구현하기에 앞서, 최적화 할 수 있는 부분을 살펴봅니다. Approach 2의 경우 현재 보여지는 부분에 존재하는 Gland를 찾는 부분이 빈번하게 일어나므로, 해당 query를 빠르게 처리할 수 있는 index를 생각할 수 있습니다. 또한 Approach 4의 경우 그룹화를 하기 위해 주변 Gland를 찾는 부분이 빈번하게 일어나므로 이것도 index를 적용하여 query 효율을 높일 수 있어보입니다.
Spatial index
바이너리 트리, 레드블랙 트리 등의 자료구조는 1차원 데이터를 빠르게 저장, 조회하는데 효율적으로 사용 되고 있습니다. 하지만 현재 우리가 접한 문제는 2차원 x, y좌표 상에서 Gland를 효율적으로 저장, 조회해야 하기 때문에 2차원 데이터를 인덱싱할 수 있는 Spatial index인 R-tree, Kd-tree, MVP-tree 등을 고려할 수 있습니다. Spatial index의 가장 큰 장점으로는 효과적인 Similarity query를 쉽게 구현할 수 있다는 점입니다. Similarity query는 크게 Range query와 kNN query로 나눌 수 있습니다. Range query는 query point로부터 특정 range 안에 존재하는 데이터를 조회하는 query이고, kNN query는 query point로부터 가장 가까운 k개의 데이터를 조회하는 query입니다.
Approach 2의 경우 현재 Canvas가 그리고 있는 화면 만큼의 range query를 통해 시간복잡도를 줄일 수 있고, Approach 4의 경우 그룹화를 할 주변 Gland를 조회할 때 kNN query를 통해 시간복잡도를 줄일 수 있으므로 처음 Gland 데이터를 받아올 때 Spatial index를 빌드한 뒤, 이를 이용했습니다.
Algorithm pseudo code
K := 5
AreaThreshold := 80function getGlands(index, canvasBoundingRect, zoom):
glands := index.rangeQuery(canvasBoundingRect) # Approach 2
glands := pruneByZoom(glands, zoom) # Approach 3
glands := merge(index, glands, zoom) # Approach 4
return glandsfunction merge(index, glands, zoom):
results := []
pq := MinPriorityQueue<Gland.area>
pq.push(gland) for gland in glands
while not pq.empty():
gland := pq.pop()
if gland.area > AreaThreshold:
results.push(gland)
continue
neighbors := index.knn(gland, K)
for neighbor in neighbors:
if neighbor.area > AreaThreshold: continue
mergedGland := convexHull(gland, neighbor)
pq.push(mergedGland)
return results
K와 AreaThreshold는 상수이고, 화면의 확대/축소/이동 이벤트가 발생할 때마다 getGlands 함수를 호출하고, 반환되는 Gland 리스트를 화면에 그려주도록 구현했습니다. 그룹화 하는 함수인 merge는 우선 Approach 2, 3을 적용하여 줄어든 Gland를 넓이가 작은 것이 우선순위인 힙 자료구조에 집어넣습니다.
힙이 비어있지 않을 때까지 순회하면서 넓이가 작은 Gland부터 뽑은 뒤 주변 K개 만큼의 다른 Gland를 kNN query로 찾습니다. 만약 그룹화 할 수 있는 주변 Gland가 있다면 convex hull로 그룹화를 해주고, 다시 힙에 넣습니다. 이 과정을 반복하다보면 작은 Gland가 모여있는 곳은 거듭된 그룹화를 하여 하나의 큰 Gland로 합쳐지게 됩니다.
Conclusion
위에서 계속 보여졌던 56064 * 80128크기의 슬라이드 이미지 위에 15,000개의 점으로 구성된 400개의 Gland를 그렸을 때, Gland의 수는 62% 감소하였고 점의 수는 78% 감소했습니다. 확대/축소/이동 시 매번 getGlands 함수를 호출해야 되지만, 해당 함수는 70ms 미만의 시간이 걸리므로 사용이 불가능 했던 기존 방법과는 달리 준수한 성능을 보인다고 할 수 있습니다.
해당 슬라이드의 크기보다 더 큰 슬라이드 일 수록 효율성은 더 커질 것이라고 생각됩니다.
