Пишу, по большей части, про историю, свою жизнь и немного про программирование.

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

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

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

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

968 ВМК (5.17КиБ)

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

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

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

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

Уменьшенный номер (4.90КиБ)

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

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

Разница (4.81КиБ)

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

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

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

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

Разница (16.67КиБ)

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

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

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

23 комментария
twitter.com/Sparklss 2013

#disclaimer: личное оценочное мнение о художественных пристрастиях на грани офтопа и КО#

Ну, если никакащуй Elementary «хороший», то от нормального британского Sherlock должно просто порвать на сотни маленьких оргазмов :)

Евгений Степанищев (bolknote.ru) 2013

Комментарий для https://twitter.com/Sparklss:

Нормальный британский «Шерлок» великолепен. А пока готовится (надеюсь) новый сезон, я смотрю хороший «Элементарно». :)

twitter.com/Sparklss 2013

Если жанр/направление Elementary интересует, то осмелюсь обратить внимание на недавние The Fall (типа серьезный, с Джиллиан Андерсон, только начался), Motive (нестандартная идея, остальное обычное), Case Histories (просто хороший британский), Hannibal (эстетически-психоделическое guilty pleasure).

Евгений Степанищев (bolknote.ru) 2013

Комментарий для http://twitter.com/Sparklss:

Спасибо! Досмотрю, буду знакомиться :)

egorinsk 2013

Если интересно, заблюренный текст можно восстановить, на хабре была статья про алгоритм: http://habrahabr.ru/post/136853/

Евгений Степанищев (bolknote.ru) 2013

Комментарий для egorinsk:

О, да, я внимательно слежу за статьями этого автора. Я даже пытался восстановить (безуспешно) неудачно сфотографированный текст на нескольких десятках фото. Мы списывались с автором и я передал ему свои образцы, результат нулевой.

Там совершенно другой алгоритм. Он базируется только на характере искажения (например, смазывание в определённую сторону) без учёта того что должно получиться (например, текст на русском,
шрифт Arial, 15 кегль).

Конечно, для текста он редко пригоден, к сожалению.

При этом я считаю, что автор молодец и статьи крайне интересны.

Дмитрий Радищев (dibr.livejournal.com) 2013

Комментарий для Евгения Степанищева:

Если наша обратная функция дала нам множество возможных изображений, из них надо отобрать лишь те, которые дают на каждой позиции допустимый вариант

«Наша обратная функция» даст нам абсолютно нереальное количество «возможных изображений». Чисто математически — если мы усреднили два пикселя в один, и получили пиксель со значением яркости 128 (из 256 возможных) — «возможных изображений» из двух пикселей будет 256 штук (от (0,255) до (255,0)). Точнее, вдвое больше, за счёт целочисленного округления :-) 10^100 вариантов при этом набирается ну о-очень легко.

Поэтому подходить надо наоборот. Мы заранее знаем, какого вида изображение мы восстанавливаем — например, это «номер автомобиля». Исходя из этого у нас уже есть намного более реальное количество «возможных исходных изображений» (всего менее миллиарда для примера номера машины — это сильно меньше, чем 10^100), и нам примерно (а в некоторых случаях и точно) известен алгоритм размытия. Перебираем все варианты исходного изображения, для каждого — подбираем параметры размытия (координату, угол, масштаб, степень размытия, пару-тройку параметров, определяющих форму размытия) по наилучшему совпадению с нашей исходной размытой фоткой, затем выбираем то изображение, которое после размытия оказалось ближе всего к нашей размытой фотке. Характеристика достоверности — насколько хуже ближайшая конкурирующая картинка совпадает с размытой фоткой чем картинка-победитель.
Если использовать не весь номер, а повторять процедуру итеративно для каждой цифробуквы в номере — распознаваемость несколько ухудшится, зато вычислительные мощности понадобятся уже вполне реальные. Если в этом алгоритме ещё как-то синхронизировать подбор параметров размытия для каждого из знаков — надёжность увеличится, скорость возрастёт.

Ну, и «оквадрачивание» в ФШ — намного более деструктивная операция, чем плавное размытие, потому что она убивает высокие пространственные частоты полностью, в то время как плавное размытие просто уменьшает их амплитуду. Соответственно, при расшифровке «мутных фоток» при росте мути будет плавно падать достоверность, при расшифровке «квадратиков» — в какой-то момент алгоритм «сломается».

Евгений Степанищев (bolknote.ru) 2013

Комментарий для dibr.livejournal.com:

Я ждал, что ты прокомментируешь и рад твоему дополнению, спасибо! :)

Ну, и «оквадрачивание» в ФШ — намного более деструктивная операция, чем плавное размытие, потому что она убивает высокие пространственные частоты полностью, в то время как плавное размытие просто уменьшает их амплитуду. Соответственно, при расшифровке «мутных фоток» при росте мути будет плавно падать достоверность, при расшифровке «квадратиков» — в какой-то момент алгоритм «сломается».

Надеюсь, у меня будет время попробовать что получится. Если ты имеешь ввиду, под моментом, когда алгоритм «сломается» размер пикселя в пикселеризации, то я ни в коем случае не утверждаю, что это будет всегда работать, конечно.

Vlad528 2013

в уменьшенном номере отлично различаются ВСЕ знаки, стоит чуть отодвинуться от монитора.

Vlad528 2013

ну кроме RUS

Евгений Степанищев (bolknote.ru) 2013

Комментарий для Vlad528:

Т. е. вам видно, что там не В968МК, а В960НУ? Уменьшенная буква «м» выглядит ровно так же, как «н» для невооружённого глаза.

Евгений Степанищев (bolknote.ru) 2013

Комментарий для Vlad528:

А букву «у» в этой загогулине я не различаю как не стараюсь.

zg (zg.livejournal.com) 2013

Комментарий для Евгения Степанищева:

Нормальный британский «Шерлок»

какая-то скучная унылая нудятина, не? с трудом две серии осилил. или даже не осилил, не помню.

что касается распознавания номеров, весьма денежная, а поэтому закрытая тема.

Евгений Степанищев (bolknote.ru) 2013

Комментарий для zg.livejournal.com:

какая-то скучная унылая нудятина, не? с трудом две серии осилил. или даже не осилил, не помню.

Не, отличный сериал. На 5+.

zg (zg.livejournal.com) 2013

Комментарий для Евгения Степанищева:

ничего отличного, жалко потраченного времени.

rembish.org 2013

К сожалению, Elementary скатился в попсятину где-то от середины сезона. Поэтому я понимаю негодование комментирующих.

Евгений Степанищев (bolknote.ru) 2013

Комментарий для rembish.org:

Комментирующие говорят о сериале «Шерлок».

Кирилл 2013

Частенько имеется видеозапись, а из видео можно добыть много интересного: http://habrahabr.ru/post/173791/

Евгений Степанищев (bolknote.ru) 2013

Комментарий для Кирилл:

Насчёт частенько не согласен. Иногда имеется, да. А опыты с восстановлением кадров из видеозаписи давно ведутся, несколько лет, непонятно только почему в прототипах так всё впечатляет, а ни одного продукта на рынке нет. :(

Евгений Степанищев (bolknote.ru) 2013

Комментарий для Кирилл:

Если это действительно надёжно работает (как заявлено в статье), думаю, это скоро во всех смартфонах будет.

griffonn 2013

Не по теме — в РСС не видно картинок (через Фидли, по крайней мере).

Евгений Степанищев (bolknote.ru) 2013

Комментарий для griffonn:

Значит глючит ваш Фидли. С картинками в РСС всё в порядке.