Entry

プログラミングメモ - ラベル番号の対応表作成問題

2010年03月04日

一見簡単そうだけれども,ちと難しい問題を紹介しておきます。ここでは問題だけ。気が向いたら解答例を書くかも。

【問題】
次のような数字の対応を収めた配列の配列があります。なお,配列は '[' と ']' で囲み,その要素はカンマで区切られて書かれているものとします。

[
 [ 1,  3], [ 2,  4], [13, 11], [ 6,  4], [ 3,  8],
 [12, 18], [20, 10], [13, 11], [ 2,  4], [ 8, 16],
 [14, 18], [ 9,  4], [14, 12], [ 8,  3]
]

この対応から,下記の〔ルール〕にしたがって,次のハッシュ(key-value 形のデータ構造)を作ってください。ハッシュは,'<' と '>' で囲み,その要素は {key : value} の形式で書かれているものとします。

<
 { 3 :  1}, { 8 :  1}, {12 :  1}, {14 :  1}, {16 :  1},
 {18 :  1}, { 4 :  2}, { 6 :  2}, { 9 :  2}, {20 : 10},
 {13 : 11}
>

〔ルール〕

  • 配列の要素である番号の組に,順序関係はない(例:[1, 2] == [2, 1])。
  • 2つ以上の番号の組で共通する番号を組み合わせて「グループ」を作ることができる。
    (例:グループを'(' と ')' で囲んで表記すると,[1, 2] と [2, 3] の組から (1, 2, 3) というグループを作ることができる。)
  • 作成するハッシュの値(value)にあたる番号は,グループの中でもっとも小さい番号である。
  • 作成するハッシュのキー(key)にあたる番号は,値に選ばれた番号以外の番号である。

つまるところ,同じグループにあたる番号をひとつの番号に変換する変換表を作成しましょう,という話。例で言うと,(1, 3, 8, 12, 14, 16, 18) は同じグループに所属しているわけだけれども,そのすべての数をもっとも小さい番号である 1 に変換する変換表を作成するわけです。

開発言語は何でもいいけれど,C++ でいうなら,配列に std::vector<std::pair<int, int>> みたいな構造,ハッシュに std::map<int, int> な構造を想定しています。

この手の問題は,実用的と言えないもんが多いんですけれど,ここでの問題は具体的に適用場面があります。どゆ場面で使われるか,ピンとくる向きはくるはず。もったいつけずに言うと,画像処理のラベリング処理に使います。ラベリングを高速に行う方法としては,ルックアップテーブルを使う方法が有名です。このルックアップテーブルを整理するときのアルゴリズムを聞いているわけ。

ネットで紹介されている方法の中には,規模が大きくなると画素をなめてラベル付けする処理(ラベリング処理の本体)以上に,このルックアップテーブルを整理する処理の方が重くなっちゃうものがあります。できるだけ効率的かつ高速にルックアップテーブルの対応表を作成してもらいたい。

あたしゃ〔ルール〕をそのまま処理手順に読み替えて,愚直に作ってみたんですけれど,これは非常に遅かった。それなりのスペックのマシンで動かしても,3000 x 4000 pixel 程度の画像では,3秒近く処理が返ってこないことがありました(※ラベリング処理全体)。

ラベリングは,どんな画像処理の本にも書かれているおなじみの処理ですけれど,メモリアクセスの点からも処理全体のコストからも,非常にコストのかかる処理だったりします。反面,二値画像を扱うためには必須となる技術だったりもする。並列処理も含めて考えると面白いかも。週末のお楽しみにどうざましょ。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN