問題
写真編集の研究室から、グレースケール画像のエッジ(輪郭)を強調してほしいと頼まれました。各ピクセルは0(黒)から255(白)までの明るさです。各ピクセルについて周囲の3 × 3近傍を見て、ソーベルカーネルで2つの重み付き和を計算します。
Gx = -1 0 1 Gy = -1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1カーネルの中心をそのピクセルに、上の行を1つ上の行に、左の列を1つ左の列に合わせます。各近傍ピクセルに対応する重みを掛けて足し合わせ、gx と gy を求めます。近傍が画像の外にはみ出す場合は、代わりに境界上の最も近いピクセルを使います(行を 0 … rows − 1、列を 0 … cols − 1 の範囲に収めます)。エッジの強さは min(255, |gx| + |gy|) で、0から255の整数になります。値は必ず元の画像から読み、すでに書き換えたピクセルは使いません。
edge_detection(image) を実装してください。
入力
image: 行のリストとして表した画像。すべての行は同じ長さです。
出力
各値がそのピクセルのエッジの強さである、同じ大きさの新しい格子を返してください。
制約
1 ≤ rows, cols ≤ 50
0 ≤ pixel ≤ 255
例
入力:
image = [
[10, 10, 10],
[10, 10, 10],
[10, 10, 10]
]
期待される出力:
expected = [
[0, 0, 0],
[0, 0, 0],
[0, 0, 0]
]
入力:
std::vector<std::vector<long long>> image = {
{10, 10, 10},
{10, 10, 10},
{10, 10, 10}
};
期待される出力:
std::vector<std::vector<long long>> expected = {
{0, 0, 0},
{0, 0, 0},
{0, 0, 0}
};
入力:
long[][] image = new long[][] {
new long[] {10, 10, 10},
new long[] {10, 10, 10},
new long[] {10, 10, 10}
};
期待される出力:
long[][] expected = new long[][] {
new long[] {0, 0, 0},
new long[] {0, 0, 0},
new long[] {0, 0, 0}
};
解説
どの近傍も平坦なので、2つの和はどこでも0になり、結果はすべて0です。
入力:
image = [
[0, 0, 100],
[0, 0, 100],
[0, 0, 100]
]
期待される出力:
expected = [
[0, 255, 255],
[0, 255, 255],
[0, 255, 255]
]
入力:
std::vector<std::vector<long long>> image = {
{0, 0, 100},
{0, 0, 100},
{0, 0, 100}
};
期待される出力:
std::vector<std::vector<long long>> expected = {
{0, 255, 255},
{0, 255, 255},
{0, 255, 255}
};
入力:
long[][] image = new long[][] {
new long[] {0, 0, 100},
new long[] {0, 0, 100},
new long[] {0, 0, 100}
};
期待される出力:
long[][] expected = new long[][] {
new long[] {0, 255, 255},
new long[] {0, 255, 255},
new long[] {0, 255, 255}
};
解説
中央のピクセルでは、右の列から 100 + 200 + 100 = 400、左の列から0が加わるので、gx = 400、gy = 0 となり、強さは255で頭打ちになります。右の列のピクセルも255になります。画像の外にある右隣が、境界の値100のコピーになるからです。左の列のピクセルは両側とも0しか見えないので、0のままです。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
r と c を格子の範囲内に収めてから (r, c) のピクセルを返す補助関数を書きましょう。
ヒント 2
gx は近傍の左右の列だけを、gy は上下の行だけを使います。
ヒント 3
出力は別の格子に作りましょう。入力を途中で書き換えると、あとのピクセルが正しく計算できません。
目安の計算量
時間 O(rows × cols)、追加メモリ O(rows × cols)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。