And for the most the ideas in these patents are far from "obvious."

    predicted_mvx = median(left_mvx, top_mvx, topright_mvx)
    predicted_mvy = median(left_mvy, top_mvy, topright_mvy)

These two lines of pseudocode are patented. In reality, they usually are implemented in just about two lines. There's nothing non-obvious about it; if you take 15 minutes and go test the only two possible median prediction methods, this one comes up as the best.

And yet it's patented. And most video coding software patents are just like this one: stupid.

If you want even more ridiculous ones, just go look at motion search patents; they've basically patented everything under the sun.

Patents should be on implementations, not ideas. Algorithms are ideas, not implementations. People didn't do this decades ago; the inventor of Quicksort didn't rush out to patent it. But today, any time anyone comes up with an algorithm, they instantly patent it, because the system is broken.