<h2 id="%E3%81%AF%E3%81%98%E3%82%81%E3%81%AB" data-line="0" class="code-line">
<a class="header-anchor-link" href="#%E3%81%AF%E3%81%98%E3%82%81%E3%81%AB" aria-hidden="true"></a> はじめに</h2>
撮りたい対象が非常に大きい時、一枚の写真では収まりきらないケースというのはよくあります。そのような時に、複数の写真を結合して一枚の写真にしなければ、画像として視認性が低くなってしまいます。この記事では、そのようなケースに対応するための画像結合のためのアルゴリズムを考え、Pythonで実装してみました。提案アルゴリズムは、「入力画像の共通部分を事前情報なしで検出し、自動的に結合する」ことが可能です。
作成したソースコードについてはGitHubにて公開しています。興味のある方は以下のリンクからご覧ください。
<iframe id="zenn-embedded__e9a62a9b836d" src="https://embed.zenn.studio/card#zenn-embedded__e9a62a9b836d" data-content="https%3A%2F%2Fgithub.com%2FC-Naoki%2Fimage-stitcher" frameborder="0" scrolling="no" loading="lazy"></iframe><a href="https://github.com/C-Naoki/image-stitcher" style="display:none" target="_blank" rel="nofollow noopener noreferrer">https://github.com/C-Naoki/image-stitcher</a>
<h2 id="%E5%87%BA%E5%8A%9B%E4%BE%8B" data-line="7" class="code-line">
<a class="header-anchor-link" href="#%E5%87%BA%E5%8A%9B%E4%BE%8B" aria-hidden="true"></a> 出力例</h2>
以下に、アルゴリズムを用いて結合した出力例を示します。初めに、アルゴリズムに入力する画像の例を添付します。具体的には、以下に示す２枚の画像の結合を行います。画像については、<a href="https://www.cs.toronto.edu/~kriz/cifar.html" target="_blank" rel="nofollow noopener noreferrer">CIFAR-10データセット</a>の中から選択しました。
<img src="https://res.cloudinary.com/zenn/image/fetch/s--mk9z9txP--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_1200/https://storage.googleapis.com/zenn-user-upload/deployed-images/9c2e64a9f9d47620b8588ec4.png%3Fsha%3De23629f42192721545cce4e530bd365aec3632d3" loading="lazy" class="md-img">
図中の赤いエリアは、データが存在しない部分を表しています。また、右側の画像は、正解画像に比べて90度回転しています。開発したアルゴリズムは、この回転を加味して画像を結合することが可能です。
<img src="https://res.cloudinary.com/zenn/image/fetch/s--BMYfZQDH--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_1200/https://storage.googleapis.com/zenn-user-upload/deployed-images/2c4d480ef60e85ae71bf9579.png%3Fsha%3D3e9a3f65d1ad4ed7ec8334f23e211dfc1949f4ad" loading="lazy" class="md-img">
続いて、右画像の回転を補正し、左右の向きを揃えた結果が上図の通りです。緑色の枠で囲まれている部分が、アルゴリズムが自動的に検知した共通部分です。また、タイトル中に記載されている角度（上図では270°）が、アルゴリズムが検出した回転すべき最適な角度を意味しています。入力画像は、元データを90°回転させていることから、最適な角度を検出できていることがわかると思います。
<img src="https://res.cloudinary.com/zenn/image/fetch/s--kM-SfHl---/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_1200/https://storage.googleapis.com/zenn-user-upload/deployed-images/e34d58f5a9b32c2c68117b28.png%3Fsha%3D7312597490f0ff23d5a4f64aae68f846062e497c" loading="lazy" class="md-img">
そして、最終的に結合した結果が上図の通りです。アルゴリズムは、入力画像の共通部分を事前情報なしで検出し、自動的に結合することが可能であることが、この例から直感的に理解していただけると思います。
なお、他の実験結果例については、ここでは省略しますが、GitHubの <a href="https://github.com/C-Naoki/image-stitcher/blob/main/notebooks/tutorial.ipynb" target="_blank" rel="nofollow noopener noreferrer">tutorial.ipynb</a> にて公開しているので、興味のある方はそちらをご覧ください。
<h2 id="%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E6%A6%82%E8%A6%81" data-line="24" class="code-line">
<a class="header-anchor-link" href="#%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%AE%E6%A6%82%E8%A6%81" aria-hidden="true"></a> アルゴリズムの概要</h2>
以下では、提案アルゴリズムの概要を説明します。
<h3 id="1.-%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E6%8E%A2%E7%B4%A2" data-line="27" class="code-line">
<a class="header-anchor-link" href="#1.-%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E6%8E%A2%E7%B4%A2" aria-hidden="true"></a> 1. 共通部分探索</h3>
<img src="https://res.cloudinary.com/zenn/image/fetch/s--efAeYIaS--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_1200/https://storage.googleapis.com/zenn-user-upload/deployed-images/c31c9c5bdd3fd874d4ee789d.png%3Fsha%3D185402287d576a85dcf2dcbc4d089b979e1f7252" loading="lazy" class="md-img">
概要図は上記のとおりです。提案アルゴリズムは、<embed-katex><eq class="zenn-katex">h_c</eq></embed-katex>を共通部分の高さ、<embed-katex><eq class="zenn-katex">w_c</eq></embed-katex>を共通部分の幅とし、これらを基準とした全探索を行います。共通部分のサイズが <embed-katex><eq class="zenn-katex">h_c \times w_c</eq></embed-katex>であると仮定すると、共通部分は以下の4箇所にのみ存在することがわかります。
<ol data-line="32" class="code-line">
<li data-line="32" class="code-line">Image1の左上とImage2の右下の重複部分</li>
<li data-line="33" class="code-line">Image1の右上とImage2の左下の重複部分</li>
<li data-line="34" class="code-line">Image1の左下とImage2の右上の重複部分</li>
<li data-line="35" class="code-line">Image1の右下とImage2の左上の重複部分（上図に対応）</li>
</ol>
これらにより、特定の共通部分に対して、4箇所を探索することで、過不足なく共通部分を検索することが可能です。
<div class="code-block-container"><pre class="language-python"><code class="language-python code-line" data-line="39">for hc in range(min_h, max(h1, h2) + 1):
 for wc in range(min_w, max(w1, w2) + 1):
 for ix in range(2):
 for iy in range(2):
</code></pre></div>上記のコードの<code>ix</code>と<code>iy</code>の組み合わせが、上記の4箇所に対応しています。
<h4 id="%E5%B1%80%E6%89%80%E8%A7%A3%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E5%AF%BE%E7%AD%96" data-line="48" class="code-line">
<a class="header-anchor-link" href="#%E5%B1%80%E6%89%80%E8%A7%A3%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E5%AF%BE%E7%AD%96" aria-hidden="true"></a> 局所解に対する対策</h4>
画像結合において、局所解への収束は、品質の低い画像提供を意味します。このような問題を防ぐために、提案アルゴリズムは共通部分の最小値を設定することが可能です。共通部分のサイズをベースとした全探索を用いたことで、このような問題に簡単に対応可能です。
<h4 id="%E7%94%BB%E5%83%8F%E3%81%AE%E5%9B%9E%E8%BB%A2%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E5%AF%BE%E7%AD%96" data-line="52" class="code-line">
<a class="header-anchor-link" href="#%E7%94%BB%E5%83%8F%E3%81%AE%E5%9B%9E%E8%BB%A2%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B%E5%AF%BE%E7%AD%96" aria-hidden="true"></a> 画像の回転に対する対策</h4>
画像の回転に対しては、探索アルゴリズムを適用する前に片方の入力画像 (Image2) を回転させるというシンプルな方法で対処しています。
<div class="code-block-container"><pre class="language-python"><code class="language-python code-line" data-line="56">for angle in [0, 90, 180, 270]:
 # 画像を回転
 _image2 = rotate(image2, angle, resize=True, preserve_range=True).astype(np.uint8)
</code></pre></div><h3 id="2.-%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E3%81%AE%E6%8B%A1%E5%BC%B5" data-line="62" class="code-line">
<a class="header-anchor-link" href="#2.-%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86%E3%81%AE%E6%8B%A1%E5%BC%B5" aria-hidden="true"></a> 2. 共通部分の拡張</h3>
<img src="https://res.cloudinary.com/zenn/image/fetch/s--govzVkOE--/c_limit%2Cf_auto%2Cfl_progressive%2Cq_auto%2Cw_1200/https://storage.googleapis.com/zenn-user-upload/deployed-images/8ee0ec2276a98c6edf1706c1.png%3Fsha%3D23385d89bac2a4947db5d1e7ab4ef417266d3a8a" loading="lazy" class="md-img">
上記で説明したアルゴリズムは、共通部分のサイズが <embed-katex><eq class="zenn-katex">h_c \times w_c</eq></embed-katex>であると仮定しています。しかし、このアルゴリズムは、<embed-katex><eq class="zenn-katex">h_c&lt;\min(h_1, h_2)</eq></embed-katex> かつ <embed-katex><eq class="zenn-katex">w_c&lt;\min(w_1, w_2)</eq></embed-katex> という暗黙の仮定に基づいています。すなわち、任意の入力サイズに対応することはできません。このような問題に対応するために、上図のように、<embed-katex><eq class="zenn-katex">h_c</eq></embed-katex>と<embed-katex><eq class="zenn-katex">w_c</eq></embed-katex>を拡張することで、任意のサイズの入力画像に対して、提案アルゴリズムを適用することが可能になりました。
<h2 id="%E3%81%BE%E3%81%A8%E3%82%81" data-line="67" class="code-line">
<a class="header-anchor-link" href="#%E3%81%BE%E3%81%A8%E3%82%81" aria-hidden="true"></a> まとめ</h2>
本記事では、画像結合のためのアルゴリズムを提案し、Pythonで実装してみました。提案アルゴリズムは、入力画像の共通部分を事前情報なしで検出し、自動的に結合することが可能です。また、提案アルゴリズムは、局所解への収束や画像の回転に対しても対処可能です。最後に、提案アルゴリズムの概要を説明し、その有効性を出力例を基に明らかにしました。
<h3 id="%E8%BF%BD%E8%A8%98" data-line="70" class="code-line">
<a class="header-anchor-link" href="#%E8%BF%BD%E8%A8%98" aria-hidden="true"></a> 追記</h3>
2024/10/01: 200+ GitHub Stars🌟 を頂きました。ありがとうございます！

画像結合のためのアルゴリズムを考えてみた

zenn-archive

python

アルゴリズム

Discussion