画像処理におけるアルゴリズム

ここでは各画像処理におけるアルゴリズムを簡単に解説する。

2値化

指定画像を白と黒の2階調の画像に変換する処理であり、本研究で作成した2値化処理は単一手動閾値方式、P-タイル法、また、誤差分散法およびその拡張型である Floyd&Steinberg 型誤差分散、Jarvice,Judice&Ninke 型誤差分散の5つである。次にそれぞれのアルゴリズムについて解説する。

明るさ調整

画像内の全画素に対して、指定された値だけ増分して出力画素値とする処理で、次の式で表される。（bv:明るさの増分値）

デジタル画像においては 256 階調しか扱うことができないため、bv の値は -255～255 の範囲となる。
このアルゴリズムでは単純に入力画像の画素値を増分するだけなので、例えば極端に明るさを上げると真っ白な画像となってしまう。これを回避して綺麗に明るさを調整するには後述するガンマ補正を行う必要がある。

色成分の抽出

入力されたフルカラー画像のR値（赤）またはG値（緑）、B値（青）の画像をグレイスケール画像として出力する。他に特に述べるべき事はない。

色反転

一般にネガポジ反転と呼ばれる処理で、全ての画素に対して反転処理を行う。式にすると次のようになる。

このときフルカラー画像はRGBそれぞれに対してこの処理を行う必要がある。
また、上式を使わず、各画素に対してNOTをとっても同じ結果が得られる。

コントラスト調整

コントラスト調整処理とは、色の明暗の差異を変化させる処理で、これを上げると明暗のはっきりした画像となり、下げると色の明暗がなくなり中間色が多く現れる。
これは下図に示すように、入力画素濃度値に対する出力濃度値のグラフの傾きを変化させる処理を行えばよい。

このため、コントラスト調整を行うときのパラメータ（コントラストの強さ）は -127～127 の値をとることとなり、-127 を指定した場合はこの傾きが極限まで小さくなって出力画像はほぼ中間濃度(127)のみの画像となり、また 127 を指定した場合は閾値を 127 としたときの2値化処理と同様の結果を得ることができる。
この処理は上の図に示した情報を濃度変換テーブルとしてあらかじめ作成しておくことで、高速に行うことができる。

切り出し

入力画像内における指定領域の部分だけを出力画像とする処理のことである（下図）。

ガンマ補正

画像を表示する場合、表示するディスプレイやシステムによって発色特性にばらつきが生じる。この特性を数値であらわしたものがガンマ値であり、ガンマ補正とは、元画像の明るさが変わらないようにコンピュータの側であらかじめ画像を補正しておき、これをディスプレイに表示することをいう。その計算式は次のようになる。

ただし、画像においては各色情報は 0～255 の値を取るのでこの式は次のように変形される。

この式を用いてガンマ値を変更したのときの入力画素値に対する出力画素値の関係は下の図のようになる。

実際の処理ではコントラスト調整のときと同様、この図の情報を濃度変換テーブルとして作成しておくことで高速に処理を行うことができるようになっている。

グレイスケール化

フルカラー画像から256階調グレイスケール画像へ変換する処理である。
もっとも単純なグレイスケール化処理は次の式に示すような RGB 値の平均を取る方法である。

ただし、この式を用いて処理を行うと青色であった部分が妙に明るく感じたり、緑色だった部分が暗く感じる画像となってしまう。これは人間の視覚における色に対する感度特性が、一般的に緑色の輝度には敏感に反応し、青色の輝度にはあまり反応しないという傾向があるためである。これを考慮すると次の式となる。(Y:出力輝度)

この計算式は NTSC 系加重平均法と呼ばれ、日本やアメリカで使われているガンマ値2.2のテレビ放送の規格 NTSC で使われている。
ただし、この NTSC 系加重平均の式をそのまま用いると浮動小数点演算を行う必要があり、処理が極端に遅くなってしまう。そこで本研究ではそれぞれの計数に 1024 を掛けて整数値に変換してから処理を行っている。これを式に表すと次のようになる。

この式では出力値を 1024 で割っているが、実際のプログラムでは 10 ビット右シフトする事で処理の高速化を図っている。

増色

本研究では2値画像→グレイスケール／フルカラー、またはグレイスケール→フルカラー画像へ変換する処理を増色処理と呼ぶ。
この処理では単純に各画素に対する情報量を増やすだけであるので、出力された画像をただ見ただけでは何も変化は見られない。

画像枠付加

入力画像の上下左右に指定量の黒枠を付加する。
今回作成したライブラリでは初期状態で出力画像が黒色で塗りつぶされていることが分かっているので、下の図に示すように入力画像を出力画像内の中心へ転送するようにして処理を行っている。

鏡像反転

入力画像を鏡に映したように上下または左右に反転処理を行う。
下図にその処理例を示す。この図において灰色の部分が処理対象領域とする。

ノイズ除去

この画像処理ではメディアンフィルタによるノイズ除去処理のみをサポートする。
このメディアンフィルタとは、処理対象画素とその近傍8点の画素（3×3領域）の濃度を調べ、その濃度値を小さい順に並べたときの中央値（メディアン）を出力画素とする処理である。
入力画像が下の図のようになっているとき、最初、灰色で示した濃度10の位置を中心とする3×3の領域の濃度を調べる。その濃度値を小さい順に並べると次のようになる。

今回の研究においては 9画素の濃度値を小さい順に並べる処理にバブルソートアルゴリズムを採用した。ここで必要な情報は 9個の値のうちの中央の値のみであり、バブルソートを用いれば下の図に示すように最高でも 5回の走査でこの値を求めることができるので高速に処理を完了することができる。この図において灰色の枠

はソート処理が完了した値であることを示している。開発当初は標準関数で提供されているクイックソート(qsort)を使用していたが、バブルソートの場合と比べると圧倒的に処理速度が遅かった。これはクイックソートの場合総ての内容のソートを行い、また、再起関数によるオーバーヘッドが発生するためだと考えられる。

輪郭抽出

本研究において輪郭抽出処理としては、Sobel , Roberts , Prewitt が選択可能である。
画像において輪郭とは画像の濃度値が急激に変化する部分であるため、これを取り出すには微分演算が有効である。ただし、デジタル画像においてはデータが一定間隔にとびとびに並んでいるため、本当の意味での微分処理を行うことができない。そのため隣接画素同士の差をとる演算（差分）で微分を近似する。
1次微分において、( x,y ) を処理対象画素として、その画素値は f(x,y) で得られるとすると、X 方向の微分値 fx 、Y 方向の微分値 fy は次の式で求めることができる。

この微分値 fx , fy から次の式よりその点における輪郭の強さを算出できる。

この式は距離の計算を簡略化したものであり、斜めの輪郭が強く現れるという性質を持つが、計算速度は速くなる。
微分値の計算のための隣接画素同士の演算を表現する係数の組を微分オペレータと呼び、今回作成した1次微分による輪郭抽出である Sobel および Roberts の微分オペレータでは次の表のようになる。

1次微分による微分オペレータ

	Roberts	Sobel
fx （X方向微分値）	0 0 0 0 1 0 0 0 -1	-1 0 1 -2 0 2 -1 0 1
fy （Y方向微分値）	0 0 0 0 0 1 0 -1 0	-1 -2 -1 0 0 0 1 2 1

もう一つの Prewitt とはテンプレートマッチングと呼ばれる手法の一つであり、輪郭抽出処理で言うテンプレートマッチングとは、輪郭をあらわす標準パターンをいくつか作成しておき、画像の一部分と比較して最も似たものを選んでいく方法である。
Prewittによるテンプレートマッチングでは下図に示す 8種類のマスクを用意し、入力画素とその近傍 8点の画素にこのマスクの値を乗じて和をとることで一致度合いを計算し比較を行う。この計算を8つのマスクごとに行い、その中で最大の値を示すマスクの向きがエッジの方向、その計算値がそのままエッジの強さとなる。

マスクパターン	1 1 1 1 -2 1 -1 -1 -1	1 1 1 1 -2 -1 1 -1 -1	1 1 -1 1 -2 -1 1 1 -1	1 -1 -1 1 -2 -1 1 1 1	-1 -1 -1 1 -2 1 1 1 1	-1 -1 1 -1 -2 1 1 1 1	-1 1 1 -1 -2 1 -1 1 1	1 1 1 -1 -2 1 -1 -1 1
対応するエッジ

Prewittテンプレートマッチングに用いるマスク

輪郭追跡

輪郭抽出において、処理対象画像が2値画像の場合は、輪郭線をたどるようにして輪郭を抽出する事ができる。この輪郭抽出方法をここでは輪郭追跡処理と呼ぶことにする。このイメージ図を下図に示す。この図において丸点が追跡を開始する点で、矢印に向かって次々と輪郭点を追跡していくことで最終的にその画像の輪郭線を抽出できる。

輪郭追跡の流れ

画像内を左上から右下に向かって走査し、輪郭追跡の開始点を決定する
この追跡開始点を現在の追跡点とし、その追跡点を中心とした 8近傍を図の 1 の所から順に反時計回りで調べる
2. での 1 から 4 の調査点において画素が存在しない場合は孤立点であるので 1. に戻る
一番最初に現れた画素を新たな追跡点として、その追跡点を中心とした 8近傍を反時計回りで調べる。（調査する順番は後述する）
4. の操作を繰り返していくと1本の輪郭線を得ることが出来る。
追跡開始点と追跡点が同じ座標になったら追跡処理を終了し、別の輪郭線を求めるため、1. へもどる。

このとき 4. の項目にある調査する点の順番は前回の追跡点との位置関係によって決定される。この調査の順番を間違えると最悪の場合無限ループとなってしまうので注意が必要である。

左の図のような順番で画像内の輪郭を追跡中で丸のある点の周りを調査するときを考えると、現在の追跡点の周りを調査するときは反時計回りで行うので、

であらわされる点は調査済みであり、必ず有効画素ではないことが分かる。よって下の図のように前の追跡点が右上にある場合は右上、上は調査済みの点であるのでこの場所を最後に調査する順番、つまりこのような順

で調査すればよいことが分かる。

このようにして前回の追跡点の位置と調査の順番をまとめたものを下図に示す。（この図では前回の追跡点が「前回の中心点」と書いてある方向を向くように配置され、現在の調査点が丸印で表されている。）

拡大縮小

今回作成した拡大縮小処理では、拡大時には線形補間を行うかどうか、縮小時にはサンプリングを行うか縮小元領域の平均値を用いるかどうかを指定することができ、また、縦横それぞれに拡大率を指定することができる。このため、下の図に示すように縦方向の拡大縮小を行ってから横方向の拡大縮小処理を行う。

補間を行わない場合の拡大処理は出力する座標から入力画像内の座標を計算し（逆計算）、1画素ずつ転送を行う。この方法は単純であるため処理を高速に行うことができるが、拡大率を上げていくとエッジの目立った見苦しい画像となってしまう。

次に線形補間を用いた拡大処理であるが、まず線形補間について解説を行う。
線形補間とは点と点の間を直線で近似する補間方式で下の図のようになる。ある直線上に点 P1 と P2 があるとしてその間を補間する場合、その間の値を D とすると次の式で表される。

ここで d は D が P1 から P2 の間でどの位置にあるのかを割合であらわしたもので、P1 の位置なら d=0 、P2 の位置なら d=1 、P1 と P2 の中点なら d=0.5 となる。

ただし、この計算式では d の値が 0.0～1.0 という浮動小数点となって処理が極端に遅くなってしまうので、2点間の間隔を 1024 分割して、0～1023 の値を扱うようにすると次の式に変形することができる。

線形補間を用いた拡大処理にはこの式を用いるが、出力座標における入力画像内の座標値は 1024 倍の分解能が必要になる。よって、この座標値を求めるには次の式を用いる。

ここでInLenとOutLenは入出力データの個数（画像データにおいては幅または高さ）である。

ただし、この式で求められる入力画像内の座標は実際の座標の 1024 倍となっているので、先の図における d の部分を取り出し、また入力画像内の正しい座標に変換する必要がある。この求めるには次の式を用いる。ここで InPos は前の式で求められた入力画像内の座標（ 1024 倍されたもの）、RealInPos が正しい入力画像内の座標とする。

次に縮小処理であるが、まずサンプリングを行う方法を解説する。この方法は単純に値を間引くだけであり、たとえば次の数値が並んでいた場合

となるだけである。この出力座標から入力座標を計算する式は次のようになる。

縮小処理のもう一つの方法として、縮小元領域の平均値を求める方法があり、そのアルゴリズムを解説する。
今回作成した拡大縮小処理では縦横別々に処理を行うので処理対象データは1次元データとなるため、ここでは画像データを1次元配列データとして考える。例えば元データを 1/3 倍に縮小したときは下の図のようになる。

この方法を実装するするにはまず、縮小元となる領域を求める必要がある。そのためにはこの図において 1' のデータを求めるには 1' と 2' のデータの縮小元の位置を求める。この場合 1' の縮小元の位置は 1、2 'の縮小元の位置は 4 となり、よって 1' の縮小元領域は 1,2,3 であることが分かり、これより 1' の値は (1+2+3)/3 で求めることができる。

任意角回転

画像データY軸が下を向いた座標軸であるので、角度 θ 回転させるとき、出力座標 ( x2, y2 ) から入力座標 ( x1, y1 ) を求める計算式は次のようになる。（ここでは入出力画像は同じ大きさとし、その中心座標を cx, cy とする）

ただし、このままこの計算式を用いると三角関数や浮動小数の計算となってしまうので、とても処理が遅くなってしまう。だが三角関数は角度 θ しか必要ないのであらかじめ計算しておけばよく、また、浮動小数もこの部分のみであるので、グレイスケール化のときと同様にこの値に 1024 を乗ずる事でこの問題を解決できる。そのように変更した計算式を次に示す。

この計算において、1024 での除算部分があるが、ここは10ビット右シフトで代用できる。

これで回転処理を実装することができるが、この計算式も複雑な座標計算となってしまい、若干であるが処理が遅くなってしまう。そこで本研究ではこの計算を簡略化し、出力画像のある画素に対する入力画像内の位置を加算 2回のみで求める方法を採用した。ここでその解説を行う。
下に示す図がそのアルゴリズムで、最初から回転の角度に応じた形で入力画像内を横断するように処理する事で、結果的に出力される画像は回転された画像となる。

このとき入力画像内の走査を開始する点 ( Sx, Sy ) は次の式で求められる。このとき scx, scy は入力画像の中心座標、dcx,dcyは出力画像の中心座標とする。

この式を用いれば、例えば先の図のように入力画像全体が出力画像に収まるようにする事も出力画像の中心点を次のように計算するだけで実現できる（ sw, sh :入力画像の幅高さ）。

また、入力画像内を走査するときのXループのXYの増分 ( xdx, xdy ) 、およびYループのXYの増分 ( ydx, ydy ) は次の式で求めることができる。

この回転アルゴリズムを採用することで、素直に座標計算したときと比較して約 2 割程度高速に処理を行うことができるようになった。

本研究で開発した回転処理はこれに加えて線形補完を掛けることができる。拡大縮小処理のところで1次元補間の解説を行ったが、ここで用いるのは2次元補間である。その概念図を下図に示す。

この図において C0, C1, C2, C3 は入力画像の濃度値、求めたい濃度値を D とするとこの値は次の式で表される。

ただし、1次元補間のときと同様に、この式では浮動小数点計算が入ってしまうので、処理が低速となってしまう。そのため、この回転処理では下の図に示すように各2点間の距離を 256 分割して 0～255 の値とすることで式を簡単化した。その式を次に示す。

セピア調化

セピアとはイカ墨から作られる黒茶色の絵の具のことで、画像をセピア調にするということは、これで描かれたように見せるということである。
この処理には画像の輝度を用いる。輝度はそのままグレイスケール画像であるのでこの処理の対象はグレイスケールとなる。
セピア調にするには、この輝度に対して適当なパラメータを乗ずることで実現することができる。本研究では RGB 各色成分に対して次の式に示す処理を行った。

ぼかし

ぼかしとは画像をにじませる処理であり、今回作成したものは下の図で灰色に示す領域（指定画素の近傍8点）の色の平均を取るだけである。


	前回の追跡点