Иван Симочкин (ivansim) wrote,
Иван Симочкин
ivansim

Categories:

CS50. Обработка картинки BMP

В Гарвардском курсе основ программирования CS50, который я сейчас изучаю, было задание – на месте преступления осталась улика, фото, на котором запечатлен злоумышленник. К сожалению, изображение было испорчено, надо его восстановить с помощью программы на языке Си. Вот этот файл:



Ну что ж, приступим к расследованию. Первое, что приходит в голову, убрать с картинки все красные точки. Самый простой способ, это найти их и заменить на белые.

Так и поступим. В формате BMP каждый пиксель кодируется тремя байтами RGB (красный, зеленый, синий), где каждый цвет может приобретать значения от 0 (нулевая яркость) до 255 (максимальная яркость). Если поковырять исходный файл, в нем обнаруживается большое количество точек ff0000 (255-0-0), т.е. чистый красный цвет максимальной яркости. Написал программку (см. файл 1), которая меняет все точки ff0000 на ffffff.

Запускаем... Так-так-так, что-то начинает проясняться....



Но как-то уж совсем бедно, еле уловимые очертания. Как же улучшить результат?
А вот как. Когда мы заменили все красные точки белыми, мы потеряли очень много исходной информации изображения. И хоть ее и неоткуда восстановить в точности (эти пикселы были затерты красным безвозвратно), но есть вот какое соображение.

Пикселы имеют очень маленький размер, и соседние точки на изображении как правило не сильно отличаются друг от друга по цвету. Что если не заменять красный на белый, а копировать в этих местах предыдущий пиксель. Ну-ка, попробуем (прога 2)...



Ну, вот, уже значительно лучше! Правда в некоторых местах появились артефакты, где дублирование предыдущего пиксела оказалось не в кайф (края прически, белая ленточка на груди и т.п.)

Можно ли эти артефакты минимизировать? А что если не просто копировать предыдущий пиксель, а взять соседний слева и соседний снизу, смешать их цвета, сделать среднее арифметическое и вот этот цвет и вставить на место потерянного?

Сказано – сделано. Вот третья версия, красные точки заменяются на усредненное значение соседей слева и снизу. Артефактов стало значительно меньше. (Забегу наперед, я сделал еще и четвертый вариант, где микшировались целых три соседа - слева, снизу и сверху - но это принесло уже совсем мелкие улучшения)



Ну что ж, процессом чистки испорченных точек мы выжали всё, что могли. Но изображение остается каким-то бледным и почему-то неестественно голубоватым. Явно "уехал" какой-то из цветов. Но какой, и куда? И как исправить?

И вот тут начинается исследовательская работа. Я написал еще одну небольшую программку, которая проходит весь файл от начала до конца и подсчитывает для каждого из трех цветов частоту яркостей. Т.е. сколько в этом изображении точек с яркостью 0, сколько с 1 ... и так до 255. Мы получим своего рода "цветовую карту", вдруг она нам что-то сможет подсказать?



Вот оно как всё интересно, Михалыч! Сразу видно, что зеленый и синий цвет у нас идут ровненько, занимая диапазон с 232 до 255, а красный расползся. Причем, если внимательно присмотреться, то он именно разъехался – можно догадаться, что 205-я позиция должна быть на 232-й, 236-я на 246-й, 244-я на 250-й. Если б эту колонку равномерно "приплюснуть", она бы пришла в соответствие с зеленой и синей.

Нам нужно равномерно перегнать яркости красного цвета так, чтобы 205-я стала 232-й, но чтобы 255-я осталась на своем месте. И все промежуточные также равномерно ужались. Явно это какая-то линейная зависимость – a*x + b = y. Осталось только подобрать коэффициенты. А ну-ка, вспомним математику.

Набросаем систему уравнений:
205*a + b = 232
255*a + b = 255

Решаем, находим a и b, получаем формулу для ужимания красного цвета
y = 0.46*x + 138

Пишем еще одну маленькую программку-модификатор. Прогоняем и смотрим результат – пока только "карту цветов".



Вах! Формула сработала с филигранной точностью! Вот что значит школьный курс математики :-) Пора бы заценить что ж у нас получилось:



Ну вот, все наши старания привели просто к тому, что фотка стала черно-белой :-) Теперь уже задним умом становится ясно (см. последнюю карту цветов), что все значения в тройках RGB должны быть просто одинаковыми для каждого отдельного пиксела - т.е. просто передавать оттенки серого. А значит вместо наших лихих формул и "ужатий", красный цвет можно было вообще снести полностью, и пробить в него значения из полей G и B.

Но все равно не жалко потраченного времени, исследование было увлекательным. Да и откуда ж сразу было догадаться, как надо было сделать, пока мы все внутренности не изучили.

Ну что, остался последний штрих. Контрастность. Как видно из карты цветов, все точки на фотке лежат в узком диапазоне от 232 до 255. Почему бы теперь их не растянуть аккуратно на весь диапазон яркостей – от 0 до 255?

Пишем последнюю программку... Запускаем... И опа!



Вот он, злоумышленник! Мы его вычислили! :-)

ЗЫ. Кому интересен курс программирования Гарвардского университета CS50 – присоединяйтесь. Бесплатно! На украинском языке – http://courses.prometheus.org.ua/courses/Prometheus/CS50/2016_T1/
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 8 comments