概要

積分画像を用いた画像矩形領域の輝度値の和の計算方法について、計算のために必要な4画素の読み出しを高速に行うキヤノンの特許がある。
昔読んで感動したのだが最近ふと思い出して探したら見つかったので解説する。
リンク: JP5963566B2 "パターン識別装置", キヤノン株式会社

内容

積分画像とは

画像の中の画像軸に平行な任意の矩形領域の輝度値の和を高速に計算する方法。

計算に用いるのが積分画像で、この画像の各ピクセルは自分よりも左上に位置する元画像のピクセル値の和を保持する。

(図は[1] より)

元画像におけるDの領域の輝度値の和を求めたいとする。積分画像を使えば、これは4点の画素値から計算できる。積分画像における点$1, 2, 3, 4$の輝度値$i(1), i(2), i(3), i(4)$を使って$i(4) - i(2) - i(3) + i(1)$である。領域A+B+C+D($i(4)$)からA+B($i(2)$), A+C($i(3)$)を引いて、引きすぎたA($i(1)$)を足している。

Haar-like特徴で色々な矩形領域の輝度値の和を計算するので、この方法で高速化できた。局所特徴のHoG(Historam of Gradient)特徴ではこれが拡張されて矩形領域のヒストグラムを積分画像ライクに計算するIntegral Histogram[2] などが提案された。

JP5963566B2 ... 4画素読み出しの並列化

積分画像を使って和の計算は高速化される。これ以上の高速化のためには、4つの画素値へのメモリアクセスがボトルネックになる可能性がある(らしい)。高速化の一案として、同じ積分画像を4つ保持し、左上、右上、左下、右下で異なるメモリを参照すればそれぞれのアクセスを並列に実行することができる。しかし、このためにはメモリが４倍必要になる。

特許JP5963566B2はこの課題を解決するもので、メモリの総量を増やすことなく、メモリアクセスを並列化できる。具体的には、ある法則にしたがって画像領域を複数の記憶領域に振り分ける。

特許的には、以下の文言がこの特許を特徴付けている。

"複数の処理対象領域が所定の次元の入力データの各次元方向毎に定められた間隔で配置され、各処理対象領域から所定のパターンを識別するパターン識別装置において、所定の次元のデータの入力手段と、
前記入力手段によって得られた入力データを保持するため次元毎に割り当てられた個数の積で構成される複数の記憶手段と、
...
前記各次元方向について定められた間隔と対応する前記記憶手段の個数との組の内、少なくとも１組が互いに素の関係にあることを特徴とする。"

提案手法

"次に累積画像情報をメモリに分配する方法と並列読み出しの原理について説明する。〜"以降に記載されているのが提案手法によるメモリの分配方法。

メモリ分配の方法を説明すると、ある数$P1, P2$を定めて、座標値$(x, y)$を$P1, P2$で割った際の剰余によってピクセル値を分配(インターリーブ)していく。矩形領域の幅・高さ(ストライド)はそれぞれ$P1, P2$と互いに素な数で設定する。これだけである。これだけでメモリ総量一定のまま分配できて、4点のメモリアクセスは互いに異なるメモリを参照し、並列化される。

輝度値が分配される先のメモリを$M_{p_1, p_2}$で表すと、以下のようになる。
$$
p1 = x ％ P1
$$

$$
p2 = y ％ p2
$$

ただし％は剰余を表す。

これは、ある数$x_1$に対し$P$と互いに素などんな数$S$を足してもその数$x_2=x_1+S$の$P$による剰余($x_2 ％P$)は元の数の$P$による剰余($x_1％P$)と一致しないという性質を利用している。簡単な数学的性質と思うが自分にはこれ以上うまく説明できない。

例えば$P=5, S=4$とする。$x_1 = 1, 2, 3, 4, 5, ... $に対し $x_2 = x_1 + S = 5, 6, 7, 8, 9...$であり、剰余はそれぞれ$x_1％5 = 1, 2, 3, 4, 0$と$x_2％5 = 0, 1, 2, 3, 4, ...$であり、両者はずっと一致しない。

互いに素である、というのが重要で、いろんな設定の仕方があること、また行方向または列方向、または両方に対して分配を設定しても良いことが本文"また、ここではストライドS1=4、メモリの個数〜"以降に書かれている。

剰余のようなシンプルな概念を使って並列化という目的を達成しているのが素晴らしいと思う。この考え方、他に活用できないかと最近思案している。

参考文献

[1] Viola, Paul, and Michael Jones. "Rapid object detection using a boosted cascade of simple features." CVPR (1) 1.511-518 (2001): 3.
[2] Porikli, Fatih. "Integral histogram: A fast way to extract histograms in cartesian spaces." 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05). Vol. 1. IEEE, 2005.