ホームページ >ウェブフロントエンド >PS チュートリアル >Photoshop での磁気なげなわの大まかな実装 (Python ベース)
Photoshopを頻繁に使用する人は、人がガイドする切り抜き補助ツールであるMagnetic Lasso機能をよく知っているはずです。このエッジ抽出方法は、R&D 分野では通常このように呼ばれることはなく、Intelligent Scissors または Livewire と呼ばれます。
これは元々、画像セグメンテーション プロジェクトのアルゴリズム評価用の Python フレームワークでしたが、少し面白いと思ったので、それを少し拡張し、PyQt でシェルを追加し、非常に大まかな範囲で磁気投げ縄関数をシミュレートしました。シンプルな理由: 1) 最も基本的なエッジ検索のみが実装されています。パスの冷却、ダイナミック トレーニング、マウスの位置補正はなく、ましてやカーブ クロージング、カットアウト、アルファ マッティングなどはありません。2) 単に書くためだけに、パフォーマンスの仕様は考慮されていません。3) についての理解は非常に浅いです。 Qt を使用していますが、Signal-Slot はまだ作成できません。GUI が適切に作成されているかどうかはわかりません。 4) デバッグは必要ありません。
基本アルゴリズム
関連するアルゴリズムについては詳細な調査は行っていませんが、この種のアプリケーションで最も影響力のあるアルゴリズムは [1] にあると思います。これは主な参考文献でもあります。とこの記事の基本的な考え方 画像を無向グラフとみなし、隣接するピクセル間のローカルコストを計算できるので、最短経路問題に変換します。 次のステップは、ダイクストラに基づいて経路を生成することです。アルゴリズム、抽出する必要があるエッジです。関与する主なアルゴリズムは 2 つあります: 1) 隣接ピクセルのコスト計算、2) 最短パス アルゴリズム。
エッジ検出
隣接ピクセルのコストを計算する最終的な目的はエッジを見つけることなので、本質はエッジ検出です。基本的な考え方は、さまざまな手段でエッジを検出し、検出された強度に基づいて重み付けされた値をコストとして計算することです。最短経路の観点から見ると、エッジが明らかであればあるほど、コスト値は小さくなります。 [1] の提案は、重み付けに 3 つの指標を使用することです: 1) エッジ検出演算子、2) 勾配強度 (Gradient Magnitude)、3) 勾配方向 (Gradient Direction)。この記事の方法は [1] とは少し異なります。遅延のため、OpenCV の Canny オペレーターはラプラシアン ゼロクロッシング オペレーターの代わりに使用されます。式は次のとおりです:
[lleft( p,q right)={{w}_{E}}{{f}_{E}}left( q right)+{{w}_{G}} {{ f}_{G}}左(q右)+{{w}_{D}}{{f}_{D}}左(p,q右)]
キャニーオペレーター
基本的な考え方は、最初に勾配情報に基づいて多数の接続ピクセルを検出し、次に各接続ピクセルの最大の接続部分のみを取得し、周囲をゼロに設定して、初期エッジ (エッジ) を取得することです。このプロセスは非と呼ばれます。 - 最大限の抑制。次に、2 つのしきい値法を使用して、これらの検出された初期エッジを「強い」、「弱い」、「なし」の 3 つのレベルに分割します。名前が示すように、「強い」は間違いなくエッジであり、「なし」は破棄され、「弱い」から「強い」に接続されているエッジが選択されます。エッジが保持されると、このプロセスはヒステリシスしきい値と呼ばれます。このアルゴリズムは非常に古典的なものなので、Google が詳細を明らかにし次第、詳細には触れません。式は次のとおりです。
[{{f}_{E}}left( q right)=left{ begin{matrix}
0;text{ if }qtext{ がエッジ上にある場合} \
1;text{ if }qtext { がエッジ上にない} \
end{matrix} right.]
実際、最大勾配の方向に沿って見つかったパスが基本的にエッジ、この用語。私の理解では、その機能は主に、1) 大きな勾配のある領域での明らかなエッジからの逸脱を回避する、2) 抽出されたエッジの連続性を確保し、ある程度の滑らかさを確保する、というものです。
グラデーションの強さ
は、x方向とy方向のグラデーション値の2乗を平方根に加算したものです。
[{{ I}_{G}}left( q right)=sqrt{{{I}_{x}}left( q right)+{{I}_{y}}left( q right)}]
コストがかかるためが必要な場合は、反転して正規化します:
[{{f}_{G}}left( q right)=1-frac{{{I}_{G}}left( q right)}{max left( {{ I}_{G}} right)}]
グラデーションの方向
この項目は実際にはスムージング項目であり、抽出されたエッジが急激に変化するエッジに比較的高いコストを割り当てます。ノイズの影響。具体的な式は次のとおりです。
[{{f}_{D}}left( p,q right)=frac{2}{3pi }left( arccos left( {{d}_{p}}left( p,q右)右)+arccos左({{d}_{q}}左(p,q右)右)右)]
そのうち、
[{{d}_{p}}左( p,q right)=leftlangle {{d}_{bot }}left( p right),{{l}_{D}}left( p,q right) rightrangle ]
[{{d}_{ q}}left ( p,q right)=leftlangle {{l}_{D}}left( p,q right),{{d}_{bot }}left( q right) rightrangle ]
[{{ l}_{ D}}left( p,q right)=left{ begin{行列}
q-p;text{ if }leftlangle {{d}_{bot }}left( p right),q-p rightrangle ge 0 \
p-q;text{ if }leftlangle {{d}_{bot }}left( p right),q-p rightrangle end{matrix} right.]
({{d}_{bot }}left( p right)) は p の垂直方向です。また、上式の符号の判定は ({{d}_{bot }}left( p right)) ({{l}_{D}}left( p,q right)) の値は π/2 に制限されます。
[{{d}_{bot }}left( p right)=left( {{p}_{y}},-{{p}_{x}} right)]
斜め反対方向コスト補正
2次元画像では通常、隣接するピクセルはユークリッド距離に応じて2つのタイプに分けられます。1) ピクセルの辺の長さを間隔として上下左右に隣接する。 ) ピクセル辺の長さの (sqrt{2}) 倍の間隔で斜めに隣接します。ローカル コストを計算するときは、通常、次の図のように、この距離の差の影響を考慮する必要があります。 5
6 | 6 | 7 |
8 | 9 |
ピクセル位置の影響を考慮しない場合、最小コストを求めるとき、左上隅のコスト=2が最小とみなされます。ただし、ピクセル間隔の影響を考慮すると、左上隅の方向に注目します。線形補間を行うと、中心からの左上隅の単位距離の値が 6-2 になります。 center は (6-left( 6- 2 right)times 1/sqrt{2} =3.17>3) である必要があるため、真上にあるものが最小コストの正しい方向になります。 最短経路検索 磁気投げ縄では、最初に点をクリックしてからマウスを動かすと、マウスと最初にクリックした点の間に自動的に端に近づく線が表示されます。ここでは、最初にクリックされたピクセルをシード ポイントとして定義します。磁気投げ縄は、前のセクションで説明したエッジ関連のコストを考慮しながら、シード ポイントから現在のマウスまでの最短経路を実際に見つけます。下の図に示すように、赤いものはシード ポイントで、マウスを動かすと、エッジに最も近いシード ポイントとマウス座標の間の接続がリアルタイムで表示されます。これが磁気投げ縄の理由でもあります。ライブワイヤーと呼ばれます。 最短経路を実現する方法はたくさんありますが、ここで紹介するのはダイクストラアルゴリズムに基づいた実装です。画像のすべてのピクセルを変換し、各ピクセルからシード ポイントまでの最短パスを取得するダイクストラ アルゴリズム。例として下の図を見てみましょう。コスト行列では、ダイクストラ アルゴリズムを使用して各要素を走査した後、各要素が隣接する要素を指すようになり、任意のピクセルが右上隅などのシードへのパスを見つけることができます。 42 と 39 に対応するピクセルは矢印に従って 0 になります。 アルゴリズムは次のとおりです: 输入: s // 种子点 l(q,r) // 计算局部cost 数据结构: L // 当前待处理的像素 N(q) // 当前像素相邻的像素 e(q) // 标记一个像素是否已经做过相邻像素展开的Bool函数 g(q) // 从s到q的总cost 输出: p // 记录所有路径的map 算法: g(s)←0; L←s; // 将种子点作为第一点初始化 while L≠Ø: // 遍历尚未结束 q←min(L); // 取出最小cost的像素并从待处理像素中移除 e(q)←TRUE; // 将当前像素记录为已经做过相邻像素展开 for each r∈N(q) and not e(r): gtemp←g(q)+l(q,r); // 计算相邻像素的总cost if r∈L and gtemp<g(r): // 找到了更好的路径 r←L; { from list.} // 舍弃较大cost的路径 else if r∉L: g(r)←gtemp; // 记录当前找到的最小路径 p(r)←q; L←r; // 加入待处理以试图寻找更短的路径
すべてのピクセルに対応するシードピクセルへの最短パスが見つかった後、マウスを移動すると直接描画されます。シードへの最短パスで十分です。 Pythonの実装 アルゴリズム部分はOpenCVのCanny関数とSobel関数を直接呼び出しています(勾配を求める)RGBの処理も非常に簡単で、勾配の最大値で直接近似しています。さらに、遅延のため、コスト マップとパス マップは両方とも辞書 (dict) を直接使用しますが、拡張ピクセルの記録ではセット (set) を直接使用します。 QThreadの使い方が分からないのでGUI部分はPythonのスレッドを使用しています。 画像のみインタラクティブエリアとステータスバープロンプトを表示し、抽出したエッジを右クリックします。緑色の線、抽出されるエッジは青色の線です。 コード アルゴリズム部分 from __future__ import division import cv2 import numpy as np SQRT_0_5 = 0.70710678118654757 class Livewire(): """ A simple livewire implementation for verification using 1. Canny edge detector + gradient magnitude + gradient direction 2. Dijkstra algorithm """ def __init__(self, image): self.image = image self.x_lim = image.shape[0] self.y_lim = image.shape[1] # The values in cost matrix ranges from 0~1 self.cost_edges = 1 - cv2.Canny(image, 85, 170)/255.0 self.grad_x, self.grad_y, self.grad_mag = self._get_grad(image) self.cost_grad_mag = 1 - self.grad_mag/np.max(self.grad_mag) # Weight for (Canny edges, gradient magnitude, gradient direction) self.weight = (0.425, 0.425, 0.15) self.n_pixs = self.x_lim * self.y_lim self.n_processed = 0 @classmethod def _get_grad(cls, image): """ Return the gradient magnitude of the image using Sobel operator """ rgb = True if len(image.shape) > 2 else False grad_x = cv2.Sobel(image, cv2.CV_64F, 1, 0, ksize=3) grad_y = cv2.Sobel(image, cv2.CV_64F, 0, 1, ksize=3) if rgb: # A very rough approximation for quick verification... grad_x = np.max(grad_x, axis=2) grad_y = np.max(grad_y, axis=2) grad_mag = np.sqrt(grad_x**2+grad_y**2) grad_x /= grad_mag grad_y /= grad_mag return grad_x, grad_y, grad_mag def _get_neighbors(self, p): """ Return 8 neighbors around the pixel p """ x, y = p x0 = 0 if x == 0 else x - 1 x1 = self.x_lim if x == self.x_lim - 1 else x + 2 y0 = 0 if y == 0 else y - 1 y1 = self.y_lim if y == self.y_lim - 1 else y + 2 return [(x, y) for x in xrange(x0, x1) for y in xrange(y0, y1) if (x, y) != p] def _get_grad_direction_cost(self, p, q): """ Calculate the gradient changes refer to the link direction """ dp = (self.grad_y[p[0]][p[1]], -self.grad_x[p[0]][p[1]]) dq = (self.grad_y[q[0]][q[1]], -self.grad_x[q[0]][q[1]]) l = np.array([q[0]-p[0], q[1]-p[1]], np.float) if 0 not in l: l *= SQRT_0_5 dp_l = np.dot(dp, l) l_dq = np.dot(l, dq) if dp_l < 0: dp_l = -dp_l l_dq = -l_dq # 2/3pi * ... return 0.212206590789 * (np.arccos(dp_l)+np.arccos(l_dq)) def _local_cost(self, p, q): """ 1. Calculate the Canny edges & gradient magnitude cost taking into account Euclidean distance 2. Combine with gradient direction Assumption: p & q are neighbors """ diagnol = q[0] == p[0] or q[1] == p[1] # c0, c1 and c2 are costs from Canny operator, gradient magnitude and gradient direction respectively if diagnol: c0 = self.cost_edges[p[0]][p[1]]-SQRT_0_5*(self.cost_edges[p[0]][p[1]]-self.cost_edges[q[0]][q[1]]) c1 = self.cost_grad_mag[p[0]][p[1]]-SQRT_0_5*(self.cost_grad_mag[p[0]][p[1]]-self.cost_grad_mag[q[0]][q[1]]) c2 = SQRT_0_5 * self._get_grad_direction_cost(p, q) else: c0 = self.cost_edges[q[0]][q[1]] c1 = self.cost_grad_mag[q[0]][q[1]] c2 = self._get_grad_direction_cost(p, q) if np.isnan(c2): c2 = 0.0 w0, w1, w2 = self.weight cost_pq = w0*c0 + w1*c1 + w2*c2 return cost_pq * cost_pq def get_path_matrix(self, seed): """ Get the back tracking matrix of the whole image from the cost matrix """ neighbors = [] # 8 neighbors of the pixel being processed processed = set() # Processed point cost = {seed: 0.0} # Accumulated cost, initialized with seed to itself paths = {} self.n_processed = 0 while cost: # Expand the minimum cost point p = min(cost, key=cost.get) neighbors = self._get_neighbors(p) processed.add(p) # Record accumulated costs and back tracking point for newly expanded points for q in [x for x in neighbors if x not in processed]: temp_cost = cost[p] + self._local_cost(p, q) if q in cost: if temp_cost < cost[q]: cost.pop(q) else: cost[q] = temp_cost processed.add(q) paths[q] = p # Pop traversed points cost.pop(p) self.n_processed += 1 return paths livewire.py livewire.py GUI部分
from __future__ import division import time import cv2 from PyQt4 import QtGui, QtCore from threading import Thread from livewire import Livewire class ImageWin(QtGui.QWidget): def __init__(self): super(ImageWin, self).__init__() self.setupUi() self.active = False self.seed_enabled = True self.seed = None self.path_map = {} self.path = [] def setupUi(self): self.hbox = QtGui.QVBoxLayout(self) # Load and initialize image self.image_path = '' while self.image_path == '': self.image_path = QtGui.QFileDialog.getOpenFileName(self, '', '', '(*.bmp *.jpg *.png)') self.image = QtGui.QPixmap(self.image_path) self.cv2_image = cv2.imread(str(self.image_path)) self.lw = Livewire(self.cv2_image) self.w, self.h = self.image.width(), self.image.height() self.canvas = QtGui.QLabel(self) self.canvas.setMouseTracking(True) self.canvas.setPixmap(self.image) self.status_bar = QtGui.QStatusBar(self) self.status_bar.showMessage('Left click to set a seed') self.hbox.addWidget(self.canvas) self.hbox.addWidget(self.status_bar) self.setLayout(self.hbox) def mousePressEvent(self, event): if self.seed_enabled: pos = event.pos() x, y = pos.x()-self.canvas.x(), pos.y()-self.canvas.y() if x < 0: x = 0 if x >= self.w: x = self.w - 1 if y < 0: y = 0 if y >= self.h: y = self.h - 1 # Get the mouse cursor position p = y, x seed = self.seed # Export bitmap if event.buttons() == QtCore.Qt.MidButton: filepath = QtGui.QFileDialog.getSaveFileName(self, 'Save image audio to', '', '*.bmp\n*.jpg\n*.png') image = self.image.copy() draw = QtGui.QPainter() draw.begin(image) draw.setPen(QtCore.Qt.blue) if self.path_map: while p != seed: draw.drawPoint(p[1], p[0]) for q in self.lw._get_neighbors(p): draw.drawPoint(q[1], q[0]) p = self.path_map[p] if self.path: draw.setPen(QtCore.Qt.green) for p in self.path: draw.drawPoint(p[1], p[0]) for q in self.lw._get_neighbors(p): draw.drawPoint(q[1], q[0]) draw.end() image.save(filepath, quality=100) else: self.seed = p if self.path_map: while p != seed: p = self.path_map[p] self.path.append(p) # Calculate path map if event.buttons() == QtCore.Qt.LeftButton: Thread(target=self._cal_path_matrix).start() Thread(target=self._update_path_map_progress).start() # Finish current task and reset elif event.buttons() == QtCore.Qt.RightButton: self.path_map = {} self.status_bar.showMessage('Left click to set a seed') self.active = False def mouseMoveEvent(self, event): if self.active and event.buttons() == QtCore.Qt.NoButton: pos = event.pos() x, y = pos.x()-self.canvas.x(), pos.y()-self.canvas.y() if x < 0 or x >= self.w or y < 0 or y >= self.h: pass else: # Draw livewire p = y, x path = [] while p != self.seed: p = self.path_map[p] path.append(p) image = self.image.copy() draw = QtGui.QPainter() draw.begin(image) draw.setPen(QtCore.Qt.blue) for p in path: draw.drawPoint(p[1], p[0]) if self.path: draw.setPen(QtCore.Qt.green) for p in self.path: draw.drawPoint(p[1], p[0]) draw.end() self.canvas.setPixmap(image) def _cal_path_matrix(self): self.seed_enabled = False self.active = False self.status_bar.showMessage('Calculating path map...') path_matrix = self.lw.get_path_matrix(self.seed) self.status_bar.showMessage(r'Left: new seed / Right: finish') self.seed_enabled = True self.active = True self.path_map = path_matrix def _update_path_map_progress(self): while not self.seed_enabled: time.sleep(0.1) message = 'Calculating path map... {:.1f}%'.format(self.lw.n_processed/self.lw.n_pixs*100.0) self.status_bar.showMessage(message) self.status_bar.showMessage(r'Left: new seed / Right: finish') gui.py gui.py メイン関数 import sys from PyQt4 import QtGui from gui import ImageWin def main(): app = QtGui.QApplication(sys.argv) window = ImageWin() window.setMouseTracking(True) window.setWindowTitle('Livewire Demo') window.show() window.setFixedSize(window.size()) sys.exit(app.exec_()) if __name__ == '__main__': main() main.py main.py Github (ポータル) にアップロードされました。フォークへようこそ。 効率の向上 このコードのプロトタイプは、C++で開発する前のPythonの評価と検証のみを目的としているため、効率はまったく考慮されておらず、実行速度は基本的に400x400の画像ではまったく許容できません。 ... Python のバージョンに基づいた効率の向上については、慎重に考えたわけではありませんが、明白な場所がいくつかあるようです: 1) 現在の最小コストのピクセル操作を取り出します p = min(cost, key=cost.get ) これを書くのは楽しいですが、少なくとも min ヒープなどを使用する必要があるのは明らかです。処理するピクセルとコストの両方を表すのに dict を使用し、それを Python の heapq と組み合わせる方法を考えるのが面倒だったので、粗雑で問題のない min() を使用しただけだったからです。 2) 勾配方向の計算 三角関数の計算は極力避けるべきです。また、元の記事では値の範囲を>πまで拡張することになっている可能性があるため、実際にはこの項目の重みは小さく、 2 つのピクセルが直接使用されている場合でも、それぞれの勾配方向ベクトルの内積を計算して結果を正規化することもできます。 arccos を使用したい場合でも、ルックアップ テーブルの近似を作成することを検討できます。もちろん、最後に言いたいのは、これは実際には必要ではないと個人的に感じているということです。直接適応スピルネや 3 点平均スムージングとノイズ除去効果さえあれば十分です。 3) 隣接するピクセルの位置を計算します 2 つのピクセルが隣接する場合、その周囲の 8 つの隣接するピクセルも一致します。私の方法は比較的原始的であり、モジュール化せずに直接レートを計算できます。 4) いくつかのデータ構造を置き換えます たとえば、パス マップは本質的に、各ピクセルの最短パス上の前のピクセルを与える行列です。実際、代わりに線形データ構造を使用することを検討できますが、これを行う場合、通常は C/C++ コードになります。 5) numpy 私の印象では、numpy の組み込みメソッドを連続して呼び出すと、全体的な効率が向上するように思えます。実際のアプリケーションでは、C/C++ コードのカテゴリにも分類されます。 6) アルゴリズムレベルでの改善 この領域は深く研究されていません。実際のアプリケーションでは、最初に画像全体を計算する必要はなく、いくつかのブロックを分割することができます。あるいは、マウスの軌跡の方向にのみヒューリスティック検索を実行することを検討してください。さらに、パスを計算するときに、Image Pyramid と同様のアイデアを借用することを検討できます。最初からフル解像度でパスを検索する必要はありません。その後のプロジェクトではこのアルゴリズムを使用していなかったので、興味はありましたが、実際には GIMP などの既製のコードがたくさんありましたが、勉強する気力がありませんでした。それを見てください。 その他の改良点 どれもできていないのですが、簡単に紹介しますと、どれも実用性を考慮した改良点です。 パス冷却 Photoshop と GIMP の磁気投げ縄を使用したことのある人なら誰でも、マウスが画像をクリックしなくても、カットアウトの軌道を修正するために移動中にいくつかのポイントが自動的に生成されることをご存知でしょう。これらのポイントは実際にはポイントです。使用中に新しいシード ポイントを自動的に生成するこの方法は、パス冷却と呼ばれます。このメソッドの基本的な考え方は次のとおりです。マウスが移動するときに、パスが一定期間固定された場合、このパス内のシードから最も遠い点が新しいシードとして設定されます。その背後にはダイナミックな計画のアイデア、ベルマンの最適性が隠されています。名前も非常に鮮やかで、パス冷却です。 インタラクティブダイナミックトレーニング 単純な最短経路検索を使用する場合、見つかったエッジが目的のエッジではないという問題がよく発生します。たとえば、上の図では、緑色の線が前のエッジから抽出されています。段落のエッジ。青いのが現在抽出中のエッジです。左側の図では、ミラーの外側にあるレナの帽子のエッジが抽出したいものですが、ミラー内のレナの帽子のエッジはコストが低いため、実際に抽出された青い線分は次のように右に貼り付けられます。右の写真にあります。したがって、インタラクティブ ダイナミック トレーニングのアイデアは、緑の線分を正しく抽出されたエッジとみなして、その緑の線分をトレーニング データとして使用して、現在のエッジ抽出のコスト関数に補正値を追加することです。 [1] で使用される方法は、前のセグメントのエッジ上の点の勾配強度のヒストグラムをカウントし、勾配の発生頻度に従って現在の画像内のピクセルに重み付けをすることです。例えば、緑の線分の全ピクセルに対応する勾配強度が50~100の場合、50~100を10単位で5つのビンに分割し、各ビンの出現頻度をカウントすることができます。はヒストグラムであり、現在検出されている勾配強度を線形に重み付けします。たとえば、50 ~ 60 の範囲に対応するピクセルが最大 10 個ある場合、10 が最大値とみなされ、現在検出されている勾配強度が 50 ~ 60 のピクセルに係数 1.0 が乗算されます。トレーニング データは 70 ~ 80 の間に 5 があり、コスト重み付け係数は 5/10 = 0.5 となり、現在検出されている勾配強度が 70 ~ 80 のすべてのピクセルに係数 0.5 が乗算されます (100 を超えるピクセルが存在しない場合)。また、学習データなのでコストは0/10=0、重み係数は0なので、より強いエッジが検出されても前のエッジから外れることはありません。これは基本的な考え方ですが、実際の実装はそれほど単純ではありません。エッジのピクセルに加えて、垂直エッジの左右の 2 つのピクセルも考慮する必要があります。これにより、エッジ パターンが保証されます。さらに、マウスがトレーニング エッジから遠ざかるにつれて、検出されたエッジのパターンが異なって見える可能性があるため、トレーニングが逆効果になる可能性があります。したがって、このトレーニングの範囲では、トレーニング エッジの距離も考慮する必要があります。シードポイントからマウスを動かし、最後にスムージングとノイズ除去の処理が必要です。詳細は[1]に記載されていますが、かなり面倒なので省略します。詳細に入ります。 シードポイント位置の修正(カーソルスナップ) このアルゴリズムはシードポイントとマウスの間のエッジに最も近いパスを自動的に見つけることができますが、人間の手がよく震えるため、シードポイントはあまり適切ではない可能性があります端にセットします。したがって、ユーザーがシード ポイントの位置を設定した後、実際のシード ポイントの位置として、その座標を中心とした狭い範囲 (7x7 領域など) 内で最もコストの低いピクセルが自動的に検索されます。このプロセスはカーソル スナップと呼ばれます。 Photoshop (Python ベース) での磁気なげなわの簡単な実装の詳細については、PHP 中国語 Web サイトの関連記事に注目してください。 |