1202629909 縦がNピクセル、横がMピクセルサイズで、1ピクセルが白か黒のみで構成される2値画像で作れるパターンは2のMN乗になると思いますが、図のように同じパターンが平行移動したパターンは同じパターンとみなすとき、全部で何パターンあるかということは、MとNを使って一般式に表すことはできるのでしょうか?

また一般式に表せない場合はどのような方法でカウントしていけばいいのでしょうか?

回答の条件
  • 1人3回まで
  • 登録:2008/02/10 16:51:51
  • 終了:2008/02/11 12:13:34

ベストアンサー

id:Hiroshi0514 No.1

Hiroshi0514回答回数8ベストアンサー獲得回数12008/02/10 18:49:14

ポイント50pt

カウントする方法を。

質問の画像中にある平行移動をしている白のパターンを「図形」と呼びます。

「図形」の「外接四角形」の縦横を(n,m)とおきます。(画像のは(3,2)になります)

このとき「外接四角形の縦横が(n,m)になるような図形の個数」をn,mを用いてあらわせれば、あとはN≧n,M≧mの(n,m)に関して数え上げればよいわけです。


「外接四角形の縦横が(n,m)になるような図形の個数」は以下のように求めます。


まず、

n=1のとき、図形は横長の四角形になりM個あります。

m=1のとき、図形は縦長の四角形になりN個あります。


つぎに、n≧2かつm≧2のときを考えます。

このとき外接四角形の4隅が図形に含まれるかどうかで場合わけして考えます。

  1. 隅がすべて図形に含まれない場合
  2. 1つの隅だけが図形に含まれる場合
  3. 2つの隅が図形に含まれる場合
  4. 3つの隅が図形に含まれる場合
  5. 4つの隅がすべて図形に含まれる場合

  • 隅がすべて図形に含まれない場合

必ず各辺の四隅以外の部分に、最低1ヶ所は図形に含まれる部分があります。(ない場合、その図形の外接四角形は一回り小さくなってしまいます)

それ以外の部分は自由です。よって

(2^(m-2)-1)(2^(m-2)-1)(2^(n-2)-1)(2^(n-2)-1)*2^((m-2)(n-2))

となります。

(以下略)


このように考え、最後に

Σ[N≧n≧2,M≧m≧2](上述の場合分けの和)+M+N

を計算すればOKです。

その他の回答(3件)

id:Hiroshi0514 No.1

Hiroshi0514回答回数8ベストアンサー獲得回数12008/02/10 18:49:14ここでベストアンサー

ポイント50pt

カウントする方法を。

質問の画像中にある平行移動をしている白のパターンを「図形」と呼びます。

「図形」の「外接四角形」の縦横を(n,m)とおきます。(画像のは(3,2)になります)

このとき「外接四角形の縦横が(n,m)になるような図形の個数」をn,mを用いてあらわせれば、あとはN≧n,M≧mの(n,m)に関して数え上げればよいわけです。


「外接四角形の縦横が(n,m)になるような図形の個数」は以下のように求めます。


まず、

n=1のとき、図形は横長の四角形になりM個あります。

m=1のとき、図形は縦長の四角形になりN個あります。


つぎに、n≧2かつm≧2のときを考えます。

このとき外接四角形の4隅が図形に含まれるかどうかで場合わけして考えます。

  1. 隅がすべて図形に含まれない場合
  2. 1つの隅だけが図形に含まれる場合
  3. 2つの隅が図形に含まれる場合
  4. 3つの隅が図形に含まれる場合
  5. 4つの隅がすべて図形に含まれる場合

  • 隅がすべて図形に含まれない場合

必ず各辺の四隅以外の部分に、最低1ヶ所は図形に含まれる部分があります。(ない場合、その図形の外接四角形は一回り小さくなってしまいます)

それ以外の部分は自由です。よって

(2^(m-2)-1)(2^(m-2)-1)(2^(n-2)-1)(2^(n-2)-1)*2^((m-2)(n-2))

となります。

(以下略)


このように考え、最後に

Σ[N≧n≧2,M≧m≧2](上述の場合分けの和)+M+N

を計算すればOKです。

id:yoneto164 No.2

ヨネちゃん回答回数813ベストアンサー獲得回数942008/02/10 18:49:49

ポイント19pt

一般的な数式では表せないと思いますが、

例えばm=4,n=4であったとすれば、

2mn-(12(m-1)(n-1))-(32(m-2)(n-2))-(60(m-3)(n-3))

というふうに同じパターンを引いていけば可能だと思います。

当然かも知れませんがnとmの値が分かっていれば数式にすることは可能でしょう。

id:totsuan No.3

totsuan回答回数331ベストアンサー獲得回数582008/02/11 09:30:25

ポイント35pt

http://q.hatena.ne.jp/1202629909

URLはダミーです。

他の回答者の方々がもっときちんとした回答をしていらっしゃるかもしれませんが。

例えば、4x4配列において以下の2値画像が同じパターンであるとした場合、:

1100 0110 0010 0001

0100 0010 1100 0110

1111 1111 0100 0010

0010 0001 1111 1111

これらは左端の図を基本として、

それぞれ全体をX方向1、Y方向に1、X方向1+Y方向に1移動させたものです。

(※はみ出した分は逆端に配置してます)

この場合、左端の図の一番左上の1を基準に考えると、移動可能な場所は4x4=16となります。

ただし、全てが同じパターンの場合(真っ黒と真っ白の2通り)は対象外となりますので、

なので、パターン数は、【{2^(4x4)-2}/4x4】+2 通りになります。

これを一般化すると、全体のパターン数は【{2^(MxN)-2}/MxN】+2 通りとなります。

・・・と思われましたが、平行移動によって元と同じパターンになる場合があり、

それを単純計算で求めるのは極めて難しいように思います。

(例)

0101   全体を                   0101

1010   X(Y)方向に2移動! または    1010

0101 → X方向に1+Y方向に1移動!  → 0101 (元と同じ・・・) 

1010                          1010


もし、逆端配置パターンを同一と認めないということになると、

私が例示した上の4つの2値画像はいずれも違うもの、と認識される事になります。

その場合は、まずMxNピクセル内における白ピクセルの広がりに着目します。

例えば、質問者が提示されている画像の場合、

X方向への広がりが2、Y方向への広がりを3と捉えます。

これを一般化すると、

MxNピクセル内における(例えば)白ピクセルの広がりがX方向にX、Y方向にY存在するパターン数については、まず(X-2)(Y-2)ピクセル中の任意の配列を計算すると、2^(X-2)(Y-2) 通りで表されますが、これ自体はあまり難しくありません。下の2値画像で言うところの0に相当する部分を計算しただけです。

← X →

111111111 ↑

100000001 Y

111111111 ↓

むしろ「1」の部分について、白ピクセルがどこに点在するかについて計算できなければいけませんので。ちなみに、「1」の部分に白ピクセルが1つしか無い場合は、絶対に”白ピクセルの広がりがX方向にX、Y方向にY存在する”ことを示す事は出来ませんので、必ず白ピクセルは2箇所以上存在し、かつある数(=X+Y-1)未満の場合は特定の領域(四隅あるいは4辺それぞれ)にいくつか存在しなければいけません。

2+ 4x(X-2)(Y-2)+2x{(X-2)+(Y-2)+(2X+2Y-8)}+4x(2X+2Y-8) + ・・・

2箇所の場合は両対角、3箇所の場合は四隅のうち最低一つ以上、4箇所以上の場合は四隅を押さえなければ各縁に最低1箇所以上、といった具合に場合分けをして計算をしていきます。 X+Y-1箇所以上ある場合(※仮にT箇所)はどのような配置であれ、必ず”白ピクセルの広がりがX方向にX、Y方向にY存在する”パターンになりますので、組み合わせの計算式:(2X+2Y-4)C(T)で求める事が出来ます。後は合計した結果とそのパターン全体がMxNピクセル中でどのくらい平行移動できるか(=(M-X+1)(N-Y+1) パターン)を算出して掛け合わせればよいと思います。ただし、この時点ではXおよびYがそれぞれ一つの定数である場合の結果ですので、X=1 to M, Y=1 to Nまでそれぞれ変化させて(つまりMxN通り)、それぞれを合計すると、求めるパターン数になると思います。

ひたすら文章だけ見づらいのに加えて、これで間違っているようでしたら非常にゴメンナサイ。

               

id:MarriageTheorem No.4

MarriageTheorem回答回数12ベストアンサー獲得回数02008/02/11 11:58:42

ポイント15pt

他の方も指摘済みかもしれませんが、例えば

■□■■

■□□■

■■□■

■■■■

と、それを二マス左にずらした

■■■□

□■■□

□■■■

■■■■

を「同じパターン」とみなすかどうかで答えが変わってきます。

同じパターンとみなさない考え方ですと、例えば

■■■■

■□□■

■□□■

■■■■

■■■■

□□■■

□□■■

■■■■

は、一つめのパターンを「白マスの塊」と捉えれば二つめと同じパターンになるでしょうが、逆に一つめのパターンを「黒マスで描いた四角」と捉える場合には二つめと違うパターンということになるでしょう。

というわけで、まずは「同じパターン」であることをどう判定するのかきちんと定めることが必要かと思います。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません