stMind

about Tech, Computer vision and Machine learning

Color Coherence Vector in Python

Color Coherence Vector(CCV)は画像全体から生成する大域特徴量の一つです。
同じ大域特徴量の色ヒストグラムは空間的な情報が失われるのに対して、CCVは同色の画素が連結した領域に基いた特徴量になっているので、ヒストグラムには出来ないアピアランスの違いを表現することが可能です。

下の図はCCVの論文から引用したものですが、二つの画像はアピアランスが異なるにもかかわらず、色ヒストグラムは同一となっている例です。

f:id:satojkovic:20140427213913p:plain

特徴量計算の手順
  1. 画像のぼかし処理
    • 8近傍のピクセルの平均値で置き換え
  2. 色空間を削減
    • 64色に減色(RGBで4x4x4の64区間)
  3. 連結領域の抽出
    • 8近傍で連結する同じ色領域をラベリング
  4. CCVの生成
    • ラベリングされた領域のピクセル数がしきい値τよりも大きい場合はcoherent、小さい場合はincoherent
    • coherentなピクセル数をα、incoherentなピクセル数をβとしてペアにしたもののリストがCCV = <(α1, β1), ..., (αn, βn)>
in Python

画素アクセスが多いので、画像サイズによっては処理時間が数秒程度かかります。

#-*- coding: utf-8 -*-

"""
1. Blur the image
   replacing each pixel's value with the average value of the
   8 adjacent pixels
2. Discretize the colorspace into n(64 in paper) distinct colors
3. Classify pixels as either coherent or incoherent
   - Computing a connected components C for each distinct color
     C is a maximal set of pixels with same color
     (count if two pixels are eight closest neighbors)
     (C can be computed in a single pass over the image)
   - Detemine Tau's value(25 in paper)
   - C is coherent if the size of C exceeds a Tau, otherwise C is incoherent
4. Compute the CCV
   alpha is the number of coherent pixels
   beta is the number of incoherent pixels

   CCV = <(alpha_1, beta_1), ..., (alpha_n, beta_n)>
"""


from PIL import Image, ImageFilter
import numpy as np
from itertools import product
from collections import defaultdict


class CCV(object):
    MAX_VALUE_PIXEL = 256
    NUM_BINS_EACH_COLOR = 4
    BIN_WIDTH = MAX_VALUE_PIXEL / NUM_BINS_EACH_COLOR
    TAU = 25

    def __init__(self, image_file):
        self._im_org = Image.open(image_file)
        self._w, self._h = self._im_org.size
        self._discretized_im = np.zeros((self._h, self._w), dtype=int)
        self._labeled_im = np.zeros((self._h, self._w), dtype=int)
        self._label_to_color = defaultdict(list)
        self.ccv_vector = defaultdict(list)

    def extract(self):
        self.__blur()
        self.__discretize_colorspace()
        self.__compute_connected_components()
        self.__gen_ccv_vector()

    def __blur(self):
        self._im = self._im_org.copy()

        for y in xrange(1, self._h-1):
            for x in xrange(1, self._w-1):
                adj_pixels = [self._im_org.getpixel((i, j))
                              for i in xrange(x-1, x+2)
                              for j in xrange(y-1, y+2)]

                # replace pixel value
                self._im.putpixel((x, y),
                                  tuple(
                                      map(int,
                                          np.mean(adj_pixels, 0).tolist()
                                          )
                                  ))

    def __discretize_colorspace(self):
        for y, x in product(*map(range, (self._h, self._w))):
            # idx = red_i + green_i * 4 + blue_i * 16
            idx = self.__getidx(x, y, ch=0) + \
                  self.__getidx(x, y, ch=1) + \
                  self.__getidx(x, y, ch=2)

            # assign an index of discretized colorspace
            self._discretized_im[y][x] = idx

    def __getidx(self, x, y, ch=0):
        idx = self._im.getpixel((x, y))[ch] / self.BIN_WIDTH
        return idx if ch == 0 \
            else idx * (self.NUM_BINS_EACH_COLOR ** ch)

    def __compute_connected_components(self):
        self._current_label = 0
        
        for y, x in product(*map(range, (self._h, self._w))):
            checklist, xylist = self.__get_checklist(x, y)
            current_color = self._discretized_im[y][x]

            if current_color in checklist:
                # assign same label from labeled_im
                idx = checklist.index(current_color)
                cx, cy = xylist[idx][0], xylist[idx][1]
                self._labeled_im[y][x] = self._labeled_im[cy][cx]
            else:
                # assign new label
                self._labeled_im[y][x] = self._current_label
                self._label_to_color[self._current_label] = current_color
                self._current_label += 1
                
    def __get_checklist(self, x, y):
        checklist = []
        xylist = []
        
        if x != 0 and x != self._w-1 and y != 0:
            checklist.append(self._discretized_im[y-1][x-1])
            xylist.append([x-1, y-1])
            checklist.append(self._discretized_im[y-1][x])
            xylist.append([x, y-1])
            checklist.append(self._discretized_im[y-1][x+1])
            xylist.append([x+1, y-1])
            checklist.append(self._discretized_im[y][x-1])
            xylist.append([x-1, y])
        elif x != 0 and y == 0:
            checklist.append(self._discretized_im[y][x-1])
            xylist.append([x-1, y])
        elif x == 0 and y != 0:
            checklist.append(self._discretized_im[y-1][x])
            xylist.append([x, y-1])
            checklist.append(self._discretized_im[y-1][x+1])
            xylist.append([x+1, y-1])
        elif x == self._w-1 and y != 0:
            checklist.append(self._discretized_im[y-1][x-1])
            xylist.append([x-1, y-1])
            checklist.append(self._discretized_im[y-1][x])
            xylist.append([x, y-1])
            checklist.append(self._discretized_im[y][x-1])
            xylist.append([x-1, y])

        return checklist, xylist

    def __gen_ccv_vector(self):
        for label in xrange(self._current_label):
            s = self._labeled_im[np.where(self._labeled_im == label)].size
            color = self._label_to_color[label]
            if s >= self.TAU:
                # coherent
                if self.ccv_vector[color]:
                    self.ccv_vector[color][0] += s
                else:
                    self.ccv_vector[color] = list((s, 0))
            else:
                # incoherent
                if self.ccv_vector[color]:
                    self.ccv_vector[color][1] += s
                else:
                    self.ccv_vector[color] = list((0, s))

    
def main():
    ccv = CCV('snow_leopard.jpg')

    print '=== color coherence vector ==='
    ccv.extract()

    for k, v in sorted(ccv.ccv_vector.items()):
        print k, v

if __name__ == '__main__':
    main()
参考文献