Андрей

Не понял вопрос
Я прекрасно открывал видео (avi), зажатое как раз H264
В Линукс достаточно собрать ffmpeg с поддержкой libx264

Шумы размытием гауса убираем

В opencv есть как раз пример для поиска прямоугольников — squares.cpp

«Это выполняется с помощью opencv? Не подскажите где можно глянуть как это делается? »
Да, это можно сделать с помощью opencv
Я на IBM DW статью накатал с примерами кода если интересно — стучите ссылку дам в личку

Попробуйте boofcv
boofcv.org
Работает и на Android и в Java SE

Можно еще сделать так — бинаризовать изображение (например по средней яркости) и там где меньше черных точек качество будет выше