HN 日本語サマリー

← 一覧へ戻る
プログラミング

幾何学とCUDAプログラミングでランダムな島を地理位置特定する

Geolocating a random island using geometry and CUDA programming (yassa9.github.io)

500 pointsby yassa981 コメント

要約

この記事は、写真に写ったリゾート地の島を、幾何学とCUDAプログラミングを用いて特定する挑戦について詳述しています。メタデータに頼らず、島の形状と相対的な位置関係から「幾何学的フィンガープリント」を作成し、OpenStreetMapのデータセットに対してGPUを活用した高速なマッチング処理を行うことで、候補地を絞り込み、最終的に島の名前と座標を特定するプロセスが解説されています。

全文翻訳

gralhix004 | 幾何学とCUDA GPUプログラミングによるランダムな島の画像の地理位置特定

2026年8月16日

すべてのコードファイルと最終レポート、およびすべての手順は、こちらでGitHubで表示、クローン、ローカルでの試用が可能です。

この記事は、このチャレンジの解説として書いています。
gralhix 004 Sofia Santos作 | Gralhix

タスク概要:

[画像: main]

これは島にあるリゾートの写真です。

a) リゾートの名前は何ですか?
b) 島の座標は何ですか?
c) 写真が撮影されたとき、カメラはどの主要な方向を向いていましたか?

私の意見では、このチャレンジをgoogle lensで解決するのは楽しい機会を無駄にすることなので、数学とプログラミングで解決することにしました。

  • gralhix004 | 幾何学とCUDA GPUプログラミングによるランダムな島の画像の地理位置特定
    • タスク概要:
    • [a] メタデータ](https://yassa9.github.io/osint/gralhix-004/#a-metadata)
    • [b] フィンガープリントの構築](https://yassa9.github.io/osint/gralhix-004/#b-building-the-fingerprint)
    • [c] 検索](https://yassa9.github.io/osint/gralhix-004/#c-search)
      • [01] 熱帯緯度バウンディングボックス](https://yassa9.github.io/osint/gralhix-004/#01-tropical-latitude-bounding-box)
      • [02] 地域密度フィルター](https://yassa9.github.io/osint/gralhix-004/#02-local-density-filter)
      • [03] クラスタリング](https://yassa9.github.io/osint/gralhix-004/#03-clustering)
      • [04] 三つ組の生成](https://yassa9.github.io/osint/gralhix-004/#04-generating-triplets)
      • [05] マッチング、GPU上で](https://yassa9.github.io/osint/gralhix-004/#05-matching-on-the-gpu)
      • [06] 重複排除](https://yassa9.github.io/osint/gralhix-004/#06-dedup)
      • [07] 開いた長方形](https://yassa9.github.io/osint/gralhix-004/#07-the-open-rectangle)
    • [d] サンゴ礁の形状チェック](https://yassa9.github.io/osint/gralhix-004/#d-coral-cay-shape-check)
      • [1] コンパクトさ、円にどれだけ近いか:](https://yassa9.github.io/osint/gralhix-004/#1-compactness-how-close-to-a-circle-the-shape-is)
      • [2] マイクロ環礁のハローチェック:](https://yassa9.github.io/osint/gralhix-004/#2-micro-cay-halo-check)
    • [e] 楕円形状チェック](https://yassa9.github.io/osint/gralhix-004/#e-oval-shape-check)
    • [f] NDVI植生チェック](https://yassa9.github.io/osint/gralhix-004/#f-ndvi-vegetation-check)
    • [g] 標高と山のチェック](https://yassa9.github.io/osint/gralhix-004/#g-elevation-mountain-check)
    • [h] 最終レポート](https://yassa9.github.io/osint/gralhix-004/#h-final-report)
    • [i] ついに、答えが…](https://yassa9.github.io/osint/gralhix-004/#i-finally-answers)
    • [j] データとライセンス](https://yassa9.github.io/osint/gralhix-004/#j-data-licenses)

もちろん、最初に確認するのはメタデータです。これを私のlinux voidで実行しました。

> exiftool main.png

File Type                       : WEBP (lossless)
MIME Type                       : image/webp
Image Width                     : 736
Image Height                    : 515

予想通り、有用な情報はありませんでした。

b] フィンガープリントの構築

[画像: 01_00]

画像からわかるように、3つの陸地があります。

  • P0: 島そのもの、
  • P1: 右側の島、
  • P2: 左手前の島(山の頂上がある)

この画像の鳥瞰図の正しい透視モデルを作成できませんでした。明らかに画像はドローンで撮影されており、標高を全く推定できません(メタデータにも見つかりませんでした)。

そのため、直感で推定する必要がありました。3つの島間の相対的な距離と、その三角形の角度を知りたかっただけです。

[画像: 01_01]

ピクセル座標を順番に記録し、三角形の幾何学を計算する小さなクリックGUI 01_triangle_gui.py を作成しました。

目視で正確な中心をクリックするのは完璧には正確ではないため、検索時に両方の値の周りに±20%の許容範囲を追加しました。

c] 検索

フィンガープリントが確定したので、次のステップは地球上のすべての実際の陸地をそれと比較することです!

OpenStreetMapの分割された陸地ポリゴンセットをデータセットとして使用しました land-polygons-split-4326。WGS84形式の完全なグローバル海岸線ベクトルで、サイズは882MBです。

直感と非実証的な証拠だけで、ヒューリスティックなフィルターを作成しました。値の調整と数え切れないほどの試行錯誤に何日も(はい、丸一日)費やしました😭、ようやくこの動作するフィルターレシピにたどり着きました。

01] 熱帯緯度バウンディングボックス

$$ -30° \le latitude \le 30° $$

写真の島は熱帯にあるように見えるので、高価な幾何学作業を行う前に、熱帯の外にあるものはすべてすぐに除外することにしました。

この帯域フィルターを通過したのは正確に141,131の陸地ポリゴンです。

02] 地域密度フィルター

$$ N ext{_5km}(p) \le 10 $$

$ N ext{_5km}(p) $ は、点(p)から5km以内にある他の中心点の数を数えます。上限は10です。もし環礁が10個以上の近接した隣接点を持っている場合、それは密集したサンゴ礁地帯、混雑した海岸線、または群島の雑然とした場所にあることになり、写真が示すような小さく孤立した3〜4つの島のグループではありません。

これにより候補は51,576に絞られました。

03] クラスタリング

生き残った各点について、20km以内(画像からの目視によるヒューリスティック)にある他のすべての点を見つけます。近接した隣接点が少なくとも2つ(合計3点)ある場合、それはクラスターです。近くに3つ以上のクラスターがない点は除外されます。それらは全く三角形を形成できません。

tree = cKDTree(f_coords)
neigh = tree.query_ball_point(
                            f_coords, 
                            CLUSTER_RADIUS_KM / 111.0)
clusters = set(tuple(sorted(n)) for n in neigh if len(n) >= 3)

$$ \left|{q : \text{dist}(p,q) \le 20,\text{km}}\right| \ge 3 $$

これにより23,500のクラスターに集約されました。

04] 三つ組の生成

各クラスターについて、その中の3点のすべての組み合わせが候補となる三角形になります。これは $ C(n, 3) $ で、大きなクラスターでは急速に爆発します。例えば、60点のクラスターはそれだけで34,220の三つ組を生成します。そのため、各クラスターはまず60点に制限され、ランダムではなくサイズでサンプリングされます。

$$ \binom{n}{3} = \frac{n(n-1)(n-2)}{6} $$

def stratified_sample(idx_arr, area_arr, cap):
    order = np.argsort(area_arr[idx_arr])
    n_small = cap // 3
    n_large = cap // 3
    n_mid = cap - n_small - n_large
    mid_start = max(0, (len(idx_arr) - n_large - n_mid) // 2)
    keep = np.unique(np.concatenate([
        order[:n_small],
        order[-n_large:],
        order[mid_start:mid_start + n_mid],
    ]))
    return idx_arr[keep]

def gen_cluster_triples(idx_arr):
    local = np.array(list(
                itertools.combinations(range(len(idx_arr)), 3)), 
                dtype=np.int64)
    return idx_arr[local]

サンプリングは、クラスター全体やランダムなカットではなく、小さい島を3分の1、大きい島を3分の1、サイズ分布の中央から3分の1を採取します。

23,500のクラスターから合計80,690,777の三つ組が生成されました!!

05] マッチング、GPU上で

各三つ組に1つのCUDAスレッドを割り当てました。各スレッドは、P0(最小の、リゾートの島)を選ぶために3点を面積でソートし、次に他の2つの回転方向を使用してP1とP2を割り当てます。

long long i = blockIdx.x * (long long)blockDim.x + threadIdx.x;
if (i >= n_triples) return;

int pos[3] = {0, 1, 2};
for (int a1 = 1; a1 < 3; a1++) 
{
    int key = pos[a1];
    double keyval = a[key];
    int j = a1 - 1;
    while (j >= 0 && a[pos[j]] > keyval) 
    {
        pos[j + 1] = pos[j];
        j--;
    }
    pos[j + 1] = key;
}

P1とP2は2Dクロス積から決定されます。どのクラスターに三つ組が含まれていたかによる分岐はなく、符号のみが使用されます。

$$ \text{cross} = x_a y_b - x_b y_a $$

$$ P1 = \begin{cases} a & \text{cross} > 0 \ b & \text{cross} \le 0 \end{cases} $$

P0からa、次にbへの移動を考えます。cross > 0なら左折(反時計回り)です。cross < 0なら右折(時計回り)です。これは、3点がどちらの方向にカーブしているかを判断するために使用されるのと同じ符号のトリックです。

次に、P0での角度と距離の比率です。フィンガープリントステップと同じ公式が、各スレッドによって独立して計算されます。

$$ \theta_0 = \arccos\left(\frac{\vec{d_1} \cdot \vec{d_2}}{|\vec{d_1}||\vec{d_2}|}\right), \qquad r = \frac{|\vec{d_1}|}{|\vec{d_2}|} $$

角度、比率、P0のサイズ、P0とP1の間の分離距離、および両方の辺の長さがすべてフィンガープリントの許容範囲内にある場合、その三つ組は生き残ります。通過したスレッドは、アトミックカウンターを使用して結果を共有出力配列に書き込みます。これにより、同時に終了した2つのスレッドが互いを上書きすることはありません。

if (hit) 
{
    unsigned long long slot = atomicAdd(out_count, 1ULL);
    out_p0[slot] = p0idx;
    out_p1[slot] = p1idx;
    out_p2[slot] = p2idx;
}

カーネルから直接CLIに表示されます。

gpu: NVIDIA GeForce RTX 3050 (sm_86)
vram used: 5169 MB
kernel time: 204.1 ms

8070万の三つ組がそれぞれ1スレッドで並列に入力され、158,784がマスクを通過しました。

06] 重複排除

同じ物理的な三つ組が、複数の重複するクラスターに属していた場合、複数のGPUスレッドによってヒットされる可能性があるため、生のヒットはまず同一性によって集約されます。

seen = set()
uniq = []
for i in range(len(p0_all)):
    key = (p0_all[i], p1_all[i], p2_all[i])
    if key not in seen:
        seen.add(key)
        uniq.append(i)

重複排除後、8,915の一意な三つ組が得られました。

07] 開いた長方形

[画像: 02_00]

生き残った各三つ組には、もう1つのテストがあります。それは、写真が示すように、その隣の空間が実際に開いた水域であるかどうかです。P0→P1のエッジに沿って、P2がない方の側に長方形が構築され、その中に何か他のものがないか陸地データセットに対してチェックされます。

width = np.hypot(x1, y1)
u = np.array([x1, y1]) / width
v = np.array([-u[1], u[0]])

# p2は構築により+v側にあります。
# そのため、チェックは-v側で行われます。
length = 2 * width
corners_local = [
    (0, 0), (x1, y1),
    (x1 - v[0]*length, y1 - v[1]*length),
    (-v[0]*length, -v[1]*length),
]

もし3つの候補となる島以外に、その長方形と交差するものがあれば、候補は除外されます。そこに陸地があるということは、写真が実際に示している、遮るもののない開けた水域ではないことを意味します。

8,915の一意な三つ組が948に絞られました。

そして以下は、948の候補地の地図です。

[画像: 02_01]

d] サンゴ礁の形状チェック

この段階では、リゾートの島であるP0のみに注目し、その形状がサンゴ礁の島に見えるかどうかをチェックします。

1] コンパクトさ、円にどれだけ近いか:

ポルスビー・ポッパー・スコア: $$ PP = \frac{4\pi \cdot \text{面積}}{\text{周囲長}^2} $$

def compactness(row):
    return (4 * np.pi * row.area_km2) / (row.perim_km ** 2 + 1e-12)

[画像: 03_00]

1.0は完全な円です。それより低い値は、よりギザギザした、または細長い輪郭を示します。サンゴ礁の島は、波による堆積のために丸い傾向があるため、0.5未満のものはすべて除外されます。

2] マイクロ環礁のハローチェック:
def micro_cay_count(gdf, sindex, lon, lat):
    dists_km = nearby.geometry.distance(pt) * 111.0
    mask = (dists_km > 0) 
           & (dists_km <= HALO_KM) 
           & (nearby["area_km2"].values < MICRO_KM2)
    return int(mask.sum())

P0から1.5km以内にある0.05 km²未満の陸地断片を数えます(単なるヒューリスティックです)。実際のサンゴ礁システムは、単一の孤立した陸地ではなく、主要な島の周りに小さな砂州を散らばらせています(これを苦労して知りました😭)。そのため、少なくとも1つが必要です。

両方のチェックを通過したのは213/948の候補です。

e] 楕円形状チェック

P0のポリゴン自体に対するもう1つの幾何学的フィルターです。その周りに最小回転矩形を当てはめ、そのボックスからの2つの比率を測定します。

def aspect_and_fill(geom):
    mrr = geom.minimum_rotated_rectangle
    coords = list(mrr.exterior.coords)
    s1 = math.hypot(coords[1][0] - coords[0][0], 
                    coords[1][1] - coords[0][1])
    s2 = math.hypot(coords[2][0] - coords[1][0], 
                    coords[2][1] - coords[1][1])
    long_side, short_side = max(s1, s2), min(s1, s2)
    return long_side / short_side, geom.area / mrr.area

アスペクト比は、そのボックスの長い辺と短い辺の比率です。

$$ \text{aspect} = \frac{\text{長い辺}}{\text{短い辺}} \in \ [1.05,\ 2.2] $$

1.0に近すぎるとほぼ完全な円であり、写真のわずかに細長い形状ではありません。2:1よりも細長すぎる形状は高すぎます。

フィル比は、そのバウンディングボックスのどれだけの割合を形状が実際に埋めているかを示します。これには理論的な根拠があります。どんな楕円でも、その最小面積バウンディング矩形の正確に $ \pi / 4 $ を埋めます。これは、どれだけ引き伸ばされていても同様です。

$$ \frac{\text{楕円の面積}}{\text{ボックスの面積}} = \frac{\pi}{4} \approx 0.785 $$

これは、完全に滑らかな楕円の理論上の上限です。実際のサンゴ礁の島は完璧な楕円ではないため、カットオフは、その天井の安全な割合としてヒューリスティックに設定されています。

$$ \text{FILL_RATIO_MIN} = 0.75 \times \frac{\pi}{4} \approx 0.589 $$

形状は、完全な楕円の充填率の少なくとも75%を維持する必要があります。三日月形、リング状、切れ込みのある海岸線はこれよりはるかに低く、丸みを帯びた固体の島はそうではありません。

137/213の候補が通過しました。

f] NDVI植生チェック

最終的なAPIフェーズに到達しました。これはネットワークバウンドであり、計算バウンドではないため、最後に配置しました。

Earth Search(Element84が運営)に接続します。これは、AWSのオープンデータプログラムでホストされているSentinel-2画像をインデックス化する公開STAC APIであり、無料で使用でき、APIキーは不要です。

https://earth-search.aws.element84.com/v1で確認できます。

次に、P0が実際に植生(ヤシの木など)で覆われているか、裸の砂や岩ではないかを確認します。これは、公開STACカタログからその地点の最も新しい低雲のSentinel-2シーンを取得し、その正確なピクセルで赤と近赤外帯域をサンプリングします。

$$ \text{NDVI} = \frac{\text{NIR} - \text{Red}}{\text{NIR} + \text{Red}} $$

生きた植生は近赤外線で強く反射し、赤色光を吸収するため、健康なヤシの木はNDVIを0以上に押し上げます。裸の砂や開けた水面は0付近または負の値になります。

[画像: 04_00]

この素晴らしいGeoawesome Blogから取得した画像を見ることができます。

閾値は0.6に設定されており、散在する単位ではなく、実際の樹木被覆を必要とするには十分な高さです。

NDVIチェックを66/137が通過しました。

g] 標高と山のチェック

[画像: 05_00]

最終発表前の最後のチェックです。2つの条件があります。

  • P0自体は、小さなサンゴ礁の島として一貫性のある、低くて平坦である必要があります。
  • P2は、カメラが実際に向いていた方向にある、実際の高い地形を持っている必要があります。

「正面」は、P1とP2への方位角の二等分線です。

$$ \theta(P_0, P_i) = $$

$$ \text{atan2}\Big(\sin(\Delta\lambda)\cos\phi_i,\ \cos\phi_0\sin\phi_i - \sin\phi_0\cos\phi_i\cos(\Delta\lambda)\Big) $$

$$ \theta_{\text{front}} = $$

$$ \theta(P_0, P_2) + \frac{\big((\theta(P_0,P_1) - \theta(P_0,P_2) + 180) \bmod 360\big) - 180}{2} $$

これにより、レンズが向けられていた方向である1つの方位角が得られます。そこから、2kmから20kmの半径で、その方位角を中心に±50°のサンプル点の扇形が掃引されます。

$$ (\text{lat}, \text{lon}) = \Big(\text{lat}_0 + \frac{r\cos\theta}{111},\ \ \text{lon}_0 + \frac{r\sin\theta}{111\cos(\text{lat}_0)}\Big) $$

これらの各点は、実際の30m Copernicus DEMタイルに対してサンプリングされます。

Copernicus DEM GLO-30は、EUのCopernicusプログラムによって公開されており、AWS Open Data上の無料の公開クラウド最適化GeoTIFFとしてホストされており、アカウントやキーは不要です。

詳細については、https://registry.opendata.aws/copernicus-dem/を参照してください。

最後に、これら2つの単純なヒューリスティック条件が生存を決定します(ええ、すべてがヒューリスティックになったとわかっています haha)。

$$ \text{elev}(P_0) \le 50\text{m} $$

$$ 100\text{m} \le \max ext{_arc}(\text{elev}) \le 500\text{m} $$

[画像: 05_01]

この抽象的なグラフ画像からわかるように、破線はカメラの前方方位角であり、くさび形は標高チェックのために20kmまで広げられた±50°の検索アークです。

標高チェックを26/66が通過しました。

通過した26の候補はすべて、ブラジル近くの1つを除いて、南アジア、オーストラリア、オセアニアに位置しています!

[画像: 05_02]

h] 最終レポート

最後に、最終段階として、最終候補を目視で確認できるようにします。各生存者には、点ポリゴン検索を介して国名が割り当てられ、次にP0、P1、P2の直接のGoogleマップ衛星リンクが生成されます。

出力はプレーンなHTMLテーブル、インデックス、国名、行ごとに3つのクリック可能な座標ペアです。

[画像: 06_00]

この最終リストを入手しました。目視で確認しましょう。

ここでは一つ一つ見ていきませんが、最初の7つは私には全く違います。

[画像: 06_01]

ミクロネシアという国(初めて知りました)のテーブルの8番目の項目を開くまで 😍:

[画像: 06_03]

そしてP1とP2で確認しました。

[画像: 06_04]

そしてこれが解決策です🥳...

Googleマップで確認できます。

i] ついに、答えが…

a) リゾートの名前は何ですか?

$$ \text{Oan} $$

b) 島の座標は何ですか?

$$7^\circ,21^\prime,48.4^{\prime\prime},\text{N} \qquad 151^\circ,45^\prime,20.7^{\prime\prime},\text{E}$$

$$ \text{または} $$

$$7.363444^\circ,\ 151.755750^\circ$$

c) 写真が撮影されたとき、カメラはどの主要な方向を向いていましたか?

$$ \because\quad \theta = \text{atan2}\Big(\sin(\Delta\lambda)\cos\phi_1,\ \cos\phi_0\sin\phi_1 - \sin\phi_0\cos\phi_1\cos(\Delta\lambda)\Big) $$

$$ P_0 = (7.3633,\ 151.755983), \quad P_1 = (7.386573,\ 151.739534) $$

$$ \therefore\quad \theta = 324.97^\circ \implies \textbf{NW} $$

j] データとライセンス

海岸線ポリゴン:

標高:

  • Copernicus DEM GLO-30。
  • © DLR e.V. 2010-2014 および © Airbus Defence and Space GmbH 2014-2018、COPERNICUSを通じて欧州連合およびESAから提供。無断転載を禁じます。

衛星画像:

  • 2025-2026年の変更されたCopernicus Sentinelデータを含みます。Element 84によるEarth Searchを介して、AWS Open Dataでアクセスしました。

国境:

チャレンジとソース写真:

セクション(h)の衛星スクリーンショットはGoogle Maps / Google Earthからのものです。