Tartalomfüggő átméretezés

A "telér vágás" (seam carving, liquid resize) algoritmus úgy próbálja egy digitális kép egyik dimenzióját változtatni, hogy a "fontos" dolgok minél kevésbé torzuljanak. Ehhez keres egy olyan (mondjuk alulról felfelé haladó) vágást, ami valamilyen mérőszám mellett "legrövidebb.

Feladat

Írjunk programot, ami a "seam carving" algoritmust használva a) egy; b) x pixellel csökkenti egy kép szélességét.

Bemenet

A bemenet egy PGM formátumban megadott szürkeárnyalatos kép. A PGM kép formátuma így néz ki:

P2

# CREATOR: GIMP PNM Filter Version 1.1

1428 968

255

78

80

77

79

82

80

...

A P2 a "flat" / "lapos" PGM (Portable Gray Map) kódja. Azt jelenti, hogy a pixelek színe ASCII karakterekkel van kódolva, vagyis egyszerű szövegszerkesztővel is olvasható.
A "# CREATOR: GIMP PNM Filter Version 1.1" a létrehozó program által beszúrt megjegyzés, nincs képi információ benne.
Az 1428 968 a kép mérete pixelben.
A 255 a szürke árnyalatok maximális megengedett száma.
Ezután a kép pixeleinek kódja következik, a kép szerint sorfolytonosan, balról jobbra. A pixel értékeket "whitespace" választja el, tehát lehet egy sorban több pixel is, vagy akár minden pixel után következhet új sor.

A PGM pontosabb specifikációja itt: http://netpbm.sourceforge.net/doc/pgm.html