А давайте увеличим этот снимок ещё в 1000 раз…

Смотрели с женой шестую серию сериала «Элементарно» (хороший, кстати), там главный герой, Шерлок на экране компьютера увеличивал изображение подозреваемого и оно из зернистого и нечёткого в доли секунды улучшилось настолько, что стало возможным разглядеть надпись на рубашке подозреваемого.

Сейчас будет много текста и рассуждений, напрягитесь.

Жена спросила правда ли такое возможно, на что я ответил «конечно нет», но сам вспомнил свой давний умственный эксперимент.

Вот смотрите, берём, например, российский автомобильный номер. На первой, четвёртой и пятой позиции там одна из двенадцати букв (это те буквы, которые в нашем алфавите совпадают по написанию с латинскими, только они используются у нас в номерах), на остальных — цифры. Между прочим, это номер моей группы (968), в которой я учился в Университете и факультет (ВМК).

Мысленно откроем этот файл в редакторе и уменьшим раз в пять, так чтобы он стал нечитаемым, пусть не полностью, а в большинстве деталей. Уменьшаем каким-то известным алгоритмом, это же графический редактор. Собственно такое преобразование — это функция, которая преобразует одно изображение (набор точек и информацию о цвете каждой из них) в другое, что-то вроде: image = F(IMAGE) (переводим большую картинку в маленькую).

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

А, впрочем, зачем нам уменьшать мысленно, давайте я это в редакторе просто сделаю:

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

Или вы думаете, что и так, без труда разбираете что там написано? Если так, то это заблуждение. На нём — В960НУ, а не В968МК, как на первом. Вот, посмотрите, разница между этими двумя уменьшенными номерами:

Нет ничего невозможного в том, чтобы «развернуть» функцию уменьшения изображения — придумать F’(IMAGE), которая бы давала обратный результат, только с одним «но». Думаю, достаточно очевидно, что функция уменьшения теряет часть информации, то есть обязательно найдутся минимум два изображения, которые дадут одинаковые уменьшенные картинки: image = F(IMAGE₁) и image = F(IMAGE₂).

Таким образом обратная функция вернёт нам не одно изображение, а набор изображений, из который наша F могла сделать уменьшенное изображение. Это было бы проблемой, если бы мы не знали на что мы смотрим. Однако, в данном случае нам дан контекст — это российский автомобильный номер.

К чему я веду. Наш номер написан вполне определённым шрифтом, у нас есть всего 10 или 12 вариантов правильного написания каждого знака, в зависимости от позиции. Если наша обратная функция дала нам множество возможных изображений, из них надо отобрать лишь те, которые дают на каждой позиции допустимый вариант. Возможно таких изображений останется всего ничего, а то и вообще одно.

Посмотрите ещё раз на разницу между уменьшенными изображениями номеров В960НУ и В968МК, на этот раз я увеличу изображение ещё в три раза:

Даже такие слаборазличающиеся номера достаточно заметно разнятся после уменьшения, что даёт надежду, что потери информации при уменьшении не столь значительны, чтобы потерять её вовсе.

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

Собственно, те же рассуждения применимы и к алгоритмам другого рода — вроде тех, которым защищают приватную информацию, например, пикселиризации или смазыванию, если, конечно, нам известно информацию какого характера автор хотел скрыть. Отличный пример есть в блоге Леонида Каганова — четыре смазанные надписи, в которых нам известны все характеристики шрифта и используемый набор символов.