समस्या
एक फ़ोटो एडिटिंग लैब चाहती है कि आप grayscale तस्वीर में किनारों (edges) को उभारें। हर pixel 0 (काला) से 255 (सफ़ेद) तक की चमक है। हर pixel के लिए उसका 3 × 3 पड़ोस देखिए और Sobel kernels से दो भारित योग निकालिए:
Gx = -1 0 1 Gy = -1 -2 -1
-2 0 2 0 0 0
-1 0 1 1 2 1Kernel का केंद्र उस pixel पर रहता है, उसकी ऊपरी पंक्ति ऊपर वाली पंक्ति पर और बायाँ कॉलम बाईं ओर वाले कॉलम पर। हर पड़ोसी को उससे मेल खाते weight से गुणा कीजिए और सबको जोड़कर gx और gy पाइए। अगर कोई पड़ोसी तस्वीर से बाहर पड़ता है, तो उसकी जगह किनारे का सबसे नज़दीकी pixel लीजिए (पंक्ति को 0 … rows − 1 और कॉलम को 0 … cols − 1 की सीमा में clamp कीजिए)। Edge strength है min(255, |gx| + |gy|), इसलिए यह हमेशा 0 से 255 के बीच की पूर्ण संख्या रहती है। हमेशा मूल तस्वीर से पढ़िए, उन pixels से नहीं जिन्हें आप पहले ही बदल चुके हैं।
edge_detection(image) लिखिए।
इनपुट
image: तस्वीर, पंक्तियों की list के रूप में; हर पंक्ति की लंबाई बराबर है।
आउटपुट
उसी आकार का नया grid लौटाइए जिसमें हर मान उस pixel की edge strength हो।
सीमाएँ
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}
};
व्याख्या
हर पड़ोस एकसमान है, इसलिए दोनों योग हर जगह 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}
};
व्याख्या
बीच वाले pixel के लिए दायाँ कॉलम 100 + 200 + 100 = 400 जोड़ता है और बायाँ कॉलम 0, इसलिए gx = 400, gy = 0 और strength 255 पर सीमित हो जाती है। दाएँ कॉलम के pixels को भी 255 मिलता है, क्योंकि उनके गायब दाएँ पड़ोसी किनारे का मान 100 ले लेते हैं। बाएँ कॉलम के pixels दोनों तरफ़ सिर्फ़ 0 देखते हैं, इसलिए वे 0 ही रहते हैं।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
एक helper लिखिए जो r और c को grid के अंदर clamp करके (r, c) वाला pixel लौटाए।
संकेत 2
gx सिर्फ़ पड़ोस के बाएँ और दाएँ कॉलम इस्तेमाल करता है; gy सिर्फ़ ऊपर और नीचे की पंक्तियाँ।
संकेत 3
आउटपुट अलग grid में बनाइए; चलते-चलते इनपुट बदलने से आगे के pixels ग़लत हो जाते हैं।
अपेक्षित जटिलता
समय O(rows × cols), अतिरिक्त स्थान O(rows × cols)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।