本篇介紹如何在 OpenCV 中實作 Graph Based Segmentation 圖形分割演算法。

在 R-CNN 中的候選區域是從 Selective Search 得來的，而 Selective Search 又是根據 Graph Based Segmentation 的結果而來，所以我在研究 R-CNN 的同時，也必須先看一下 Graph Based Segmentation 的理論與實做。


在 OpenCV 中已經有包含了 Graph Based Segmentation 的功能，只是它放在 OpenCV contrib 當中，所以通常要自己安裝才會有。以下是 OpenCV 與 contrib 額外模組的安裝方式，以及 Graph Based Segmentation 的範例程式碼。

安裝 OpenCV

這裡我以 Ubuntu Linux 16.04.3 的環境示範自己下載 OpenCV 的原始碼編譯與安裝的步驟。首先更新系統套件庫：

sudo apt-get update
sudo apt-get upgrade

安裝編譯 OpenCV 所需的基本套件：

sudo apt-get -y install libopencv-dev build-essential cmake git libgtk2.0-dev pkg-config python-dev python-numpy libdc1394-22 libdc1394-22-dev libjpeg-dev libpng12-dev libtiff5-dev libjasper-dev libavcodec-dev libavformat-dev libswscale-dev libxine2-dev libgstreamer0.10-dev libgstreamer-plugins-base0.10-dev libv4l-dev libtbb-dev libqt4-dev libfaac-dev libmp3lame-dev libopencore-amrnb-dev libopencore-amrwb-dev libtheora-dev libvorbis-dev libxvidcore-dev x264 v4l-utils unzip qt5-default libvtk6-dev zlib1g-dev libwebp-dev libpng-dev libtiff5-dev libopenexr-dev libgdal-dev libx264-dev yasm libxine2-dev libeigen3-dev python-tk python3-dev python3-tk python3-numpy ant default-jdk doxygen

使用 git 下載最新的 OpenCV 原始碼：

# 下載 OpenCV 原始碼
git clone https://github.com/Itseez/opencv.git
cd opencv/
git pull
cd ..

除了基本的 OpenCV 之外，也要下載 OpenCV contrib 的原始碼：

# 下載 OpenCV contrib 原始碼
git clone https://github.com/Itseez/opencv_contrib.git
cd opencv_contrib/
git pull
cd ..

建立編譯用的目錄：

cd opencv/
mkdir -pv build
cd build

執行 CMake：

cmake -D CMAKE_BUILD_TYPE=RELEASE 
      -D OPENCV_EXTRA_MODULES_PATH=../../opencv_contrib/modules 
      -D CMAKE_INSTALL_PREFIX=/usr/local 
      -D WITH_TBB=ON 
      -D WITH_V4L=ON 
      -D WITH_QT=ON 
      -D WITH_OPENGL=ON 
      -D BUILD_opencv_ximgproc=ON 
      -D BUILD_opencv_python2=ON 
      -D BUILD_opencv_python3=ON 
      -D CUDA_GENERATION=Auto 
      ..

使用 4 核心的 CPU 進行編譯：

make -j4

安裝 OpenCV：

sudo make install
sudo /bin/bash -c 'echo "/usr/local/lib" > /etc/ld.so.conf.d/opencv.conf'
sudo ldconfig

這樣 OpenCV 就安裝完成了。

實作 Graph-Based Image Segmentation

我拿這張小狗的照片作為範例，以 Graph-Based Image Segmentation 演算法對其進行圖像分割。

測試圖檔

Qiita 網頁中有一個以 OpenCV 實做 Graph-Based Image Segmentation 的簡單範例，這個程式會將每個分割結果輸出成個別的圖檔：

import cv2
import numpy as np

# Graph-Based Image Segmentation 分割器
segmentator = cv2.ximgproc.segmentation.createGraphSegmentation(sigma=0.5, k=300, min_size=1000)

# 使用 OpenCV 讀取圖檔
src = cv2.imread('image.jpg')

# 分割圖形
segment = segmentator.processImage(src)

# 將每個分割結果輸出成個別的圖檔
mask = segment.reshape(list(segment.shape) + [1]).repeat(3, axis=2)
masked = np.ma.masked_array(src, fill_value=0)
for i in range(np.max(segment)):
  masked.mask = mask != i
  y, x = np.where(segment == i)
  top, bottom, left, right = min(y), max(y), min(x), max(x)
  dst = masked.filled()[top : bottom + 1, left : right + 1]
  cv2.imwrite('segment_{num}.jpg'.format(num=i), dst)

執行的結果會像這樣，輸出多個分割圖檔：

若要方便觀察執行結果，可以直接開啟視窗顯示圖形，並將分割結果以不同顏色顯示出來：

import cv2
import random
import numpy as np

segmentator = cv2.ximgproc.segmentation.createGraphSegmentation(sigma=0.5, k=300, min_size=5000)
src = cv2.imread('image.jpg')
segment = segmentator.processImage(src)
seg_image = np.zeros(src.shape, np.uint8)

for i in range(np.max(segment)):
  # 將第 i 個分割的座標取出
  y, x = np.where(segment == i)

  # 隨機產生顏色
  color = [random.randint(0, 255), random.randint(0, 255),random.randint(0, 255)]

  # 設定第 i 個分割區的顏色
  for xi, yi in zip(x, y):
    seg_image[yi, xi] = color

# 將原始圖片與分割區顏色合併
result = cv2.addWeighted(src, 0.3, seg_image, 0.7, 0)

# 顯示結果
cv2.imshow("Result", result)
cv2.waitKey(0)
cv2.destroyAllWindows()

這樣就會以顏色來表示分割的結果，看起來比較容易理解：

分割結果

我們也可以使用方框標示出各個分割區的範圍，這種作法在應用於其他演算法時可能會用到：

import cv2
import random
import numpy as np

segmentator = cv2.ximgproc.segmentation.createGraphSegmentation(sigma=0.5, k=300, min_size=5000)
src = cv2.imread('image.jpg')
segment = segmentator.processImage(src)
seg_image = np.zeros(src.shape, np.uint8)

for i in range(np.max(segment)):
  y, x = np.where(segment == i)

  # 計算每分割區域的上下左右邊界
  top, bottom, left, right = min(y), max(y), min(x), max(x)

  # 繪製方框
  cv2.rectangle(src, (left, bottom), (right, top), (0, 255, 0), 1)

cv2.imshow("Result", src)
cv2.waitKey(0)
cv2.destroyAllWindows()

執行的結果會像這樣：

分割結果

在學習 Graph Based Segmentation 的時候，建議可以調整 sigma、k 與 min_size 這些關鍵參數，透過程式的執行結果可以幫助我們了解它們的作用與影響，讓理論與實際更容易結合。

由於本程式主要的目的在於幫助學習 Graph Based Segmentation 演算法，在實作上並沒有考慮執行效能，若在實際應用時，請勿使用此程式碼。

參考資料：Efficient Graph-Based Image Segmentation（PDF）、博客、pyimagesearch、Qiita、OpenCV Answers