Paeth-transform arrays
J - 77 char

Taking an approach that looks different from FUZxxl's answer but is actually very similar.

1!:2&amp;4":2({.,|.@{.,@(256|$-0(0{[/:+`-/|@-])"1@|:(-#:1 2 3)|.!.0$)}.)0".1!:1]3


Some comments on the interesting bits.


1!:2&amp;4": (...) 0".1!:1]3 - If J wasn't terrible about I/O and parsing, this could be refactored as to use &amp;.".&amp;.stdin'', to save 3 chars. But it is so we can't. Rest in peace, precious characters.
2 ({.,|.@{.,@( ... stuff using $ ... )}.) - This disassembles the input and reassembles the output. We use $ both as a reference to the input in stuff using $, and as an operation we need to perform on the input before running the stuff on it.
0( blah )"1@|: - Yes, that's a dyadic Transpose: we regroup the three rotation results as the innermost array axis, so that the Paeth logic can apply on each set separately with "1.
0{[/:+`-/|@-] - The Paeth logic: sort a,b,c by the magnitudes of (p minus each of a,b,c), and take the first.