Mihai își face periplul în prelucrarea imaginilor și începe să descopere modalități prin care acesta poate detecta contururile obiectelor din pozele analizate. Astfel, el a descoperit conceptul de aplicare a unui kernel asupra unei imagini.

Intro to kernels

Un kernel este o matrice pătratică de ordin impar care se poate aplica peste o matrice generală prin procedeul de convoluție. Convoluția este o operație matematică ce presupune, în acest caz, centrarea kernelului pe fiecare pixel din imagine (pe rând) și calcularea unei sume peste valorile pixelului central și a celor înconjurători, sumă care va înlocui pixelul în imaginea finală.

Spre exemplu, să presupunem că avem kernelul $K$ și matricea $A$:

$\displaystyle K = \begin{bmatrix} 0 & -1 & 0 \\ -1 & 5 & -1 \\ 0 & -1 & 0 \end{bmatrix}$

$\displaystyle A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}$

Elementele matricei $A$, după aplicarea kernelului, vor avea valorile:

$\displaystyle A = \begin{bmatrix} 0 & 5 \\ 10 & 15 \end{bmatrix}$

Ca o formulă generală, putem considera că aplicarea unui kernel produce pixelii conform formulei următoare (în care pixelii din membrul drept folosiți în calcule sunt exclusiv pixeli din vechea matrice, sau $0$ pentru acele poziții în care kernelul este aplicat pe un pixel marginal/colț și iese parțial din matrice):

$\displaystyle A_{new}[i][j] = \sum_{di = -1}^{1} \sum_{dj = -1}^{1} A[i + di][j + dj] \cdot K[1 + di][1 + dj]$

Pentru matricea $A$ dată anterior, rezultatele sunt:

• $A_{new}(0, 0) = 5 \cdot A(0, 0) - A(1, 0) - A(0, 1) - A(-1, 0) - A(0, -1) = 5 \cdot 1 - 3 - 2 - 0 - 0 = 0$
• $A_{new}(1, 0) = 5 \cdot A(1, 0) - A(2, 0) - A(1, 1) - A(0, 0) - A(1, -1) = 5 \cdot 3 - 0 - 4 - 1 = 10$
• $A_{new}(0, 1) = 5 \cdot A(0, 1) - A(1, 1) - A(0, 2) - A(-1, 1) - A(0, 0) = 5 \cdot 2 - 4 - 0 - 0 - 1 = 5$
• $A_{new}(1, 1) = 5 \cdot A(1, 1) - A(2, 1) - A(1, 2) - A(0, 1) - A(1, 0) = 5 \cdot 4 - 0 - 0 - 2 - 3 = 15$

Cerință

Mihai a decis să realizeze un program care să îl ajute să înțeleagă aplicarea unui kernel specific pe o matrice oarecare, însă are o problemă. Mai exact, el nu obține rezultatele așteptate. Ajutați-l! Programul scris de Mihai îl puteți găsi aici sau în dreapta paginii sub „Atașamente”.

Date de intrare

Pe prima linie se află numărul de linii, respectiv coloane ale matricei, precum și o valoare maximă ($maxval$) pe care niciun element din matricea rezultat nu o poate depăși.
Pe următoarele linii se află matricea.

Date de ieșire

Se vor afișa datele primite la intrare (numărul de linii/coloane și valoarea maximă), precum și noile valori ale elementelor din matrice.

Restricții și precizări

• Elementele din rezultat trebuie să se încadreze în intervalul $[0, maxval]$. Dacă se depășește, valoarea se aduce la capătul cel mai apropiat.
• Numărul de linii sau de coloane ale matricei nu va depăși $100$.

Exemplul 1

stdin

2 2 100
1 2
3 4

stdout

2 2 100
0 5
10 15

Exemplul 2

stdin

2 2 10
8 6
-5 1

stdout

2 2 10
10 10
0 4

Explicație

Dacă nu ar fi fost limitată, matricea rezultată ar fi arătat astfel:

$\displaystyle \begin{bmatrix} 39 & 21 \\ -34 & 4 \end{bmatrix}$