問題タブ [max-flow]

研究論文で説明されているように、エネルギー最小化の概念を使用して、特定の画像から髪を抽出しようとしていました。エネルギー関数は、事前確率と YCrCb 色尤度ヒストグラムの両方に依存します。エネルギー関数は次のように定義されます。

data (x)=−∑(log(I(x)|x)+logsel (x)) [事前確率モデル]

Smooth (x) = ∑ (x ≠x )exp(-||(x)−(x)||^2/) [以前の YcrCb カラー モデル]

指定されたグラフにラベルを付ける方法に混乱しています(画像のピクセルはグラフのノードとして扱われます)。次のアプローチを使用してグラフにラベルを付けようとしましたが、結果は期待どおりではありません。

そして、グラフのノード間に重みを追加しながら、次を使用します。

値をより低い整数に変更すると比較的良い結果が得られるため、問題はにあると思いmax_val_weight-sourceますが、それは正しい方法ではありません。

また、eSmooth の値を 0 に変更しても、出力には影響しませんか?

誰かがこの文脈に光を当てることができれば、非常に感謝しています。

グラフの一部のエッジがフロー = 3n (n は非負の整数) でなければならないという最大フローの問題をどのように解決しますか? つまり、特定のエッジが 3 で割り切れるフローを持たなければならないという制約をどのように課すのでしょうか? たとえば、これらのエッジにはフロー 0、3、6、9... があるかもしれませんが、フロー 1、2、4、5 はないかもしれません... 理想的には、このようなグラフで最大フローを計算する方法が欲しいです。また、最大フロー構成の各エッジのフロー。

私は、有向で強く接続されたグラフであるグラフ G を持っています。グラフ内の S と T のすべてのペアを意味する、頂点のすべてのペアの最小カットを見つけるように求められます。これは、O(m ² × n ² ) 時間で実行する必要があります。

私が思いついた最善の方法は、すべての頂点を S と見なし、各 S について他のすべての頂点を T と見なし、それらのそれぞれについてフォード-フルカーソン アルゴリズムを実行し、最小カットを見つけることでした。しかし、私が間違っていなければ、このアルゴリズムは O(m ² × n ² × C) の複雑さを持ちます。

^{このタスクを O(m 2} × n ² ) 時間で行うにはどうすればよいでしょうか? それは可能ですか？

加重有向グラフが与えられた場合、グローバルに最小のカット、つまり、削除された場合にグラフを 2 つの半分に分離し、他のそのようなカットと比較して総加重が最小になるエッジのセットを見つけたいと考えています。

さて、以下は機能しているように見えますが、その推論は間違っていると言われました。しかし、率直に言って、私にはその方法がわかりませんし、彼がどれほど確信を持っていたかもわかりません。

U,Vグローバルな最小カット (つまり、st-cut、 where ) によって分離されたノードのセットを考えてみましょうs in U, t in V。V注: からへ戻るエッジは気にしませんU。

任意u in U, v in Vの m について、uv-cut を よりも小さくすることはできません。それ以外のs-t-cut場合、st-cut は (グローバルに) 最小ではありません。同じ理由で、2 つの頂点間uまたは 2 つの頂点間のカットをV小さくすることはできません。

一方、UV カットを大きくすることはできません。それ以外の場合U->Vは、st カットの一部ではないエッジを含める必要があります。つまり、st カットはまったくカットされません。

したがって、s任意に修正して他のすべての頂点を反復するだけで十分ですx。sが inUの場合、sx-cut が大域的最小値に対応するのxは is inVの場合であり、xs-cut はsis inVおよびxis in の場合ですU。それらが両方とも同じセットの一部である場合、カットは少なくともグローバル最小値と同じくらい大きくなります (ただし、より大きくなる可能性もあります)。

したがって、両方を計算し、これまでに遭遇した最小カットを追跡することで、最終的にグローバル最小値を見つけます。

それは私には理にかなっているように思えました。私が間違っている？もしそうなら、なぜですか？

サイズが Ai の N 個のピース​​があります。サイズ x のピースとサイズ y のピースを結合するコストは abs(xy) です。すべてのピースを結合する最適な方法は何ですか? max-flow アルゴリズムを使用して解決できますか?