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

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

Ниже показан результат обработки реального размытого изображения (не с синтетическим размытием). Исходное изображение было получено камерой Canon 500D с объективом EF 85mm/1.8. Фокусировка была выставлена вручную, чтобы получить размытие. Как видно, текст совершенно не читается, лишь угадывается диалоговое окно Windows 7.



И вот результат обработки:



Практически весь текст читается достаточно хорошо, хотя и появились некоторые характерные искажения.

Под катом подробное описание проблем деконволюции, способов их решения, а также множество примеров и сравнений. Осторожно, много картинок!

Эксклюзивно для Хабра.



(кликабельно)

Компания Intel опубликовала четыре тома документации (2400+ страниц) с описанием архитектуры и полным руководством по программированию графических процессоров Ivy Bridge. Документация относится к наборам микросхем Intel HD Graphics 2500/4000, которые используются с процессорами третьего поколения Intel Core i7/i5/i3.

Все 17 PDF'ов опубликованы на сайте Linux Graphics Drivers from Intel под лицензией Creative Commons.

Документация описывает регистры, инструкции и интерфейсы памяти для программного взаимодействия с компонентами, в том числе графическое ядро (MMIO, медиарегистры, движок рендеринга, растровый движок), конвейер 3D-обработки, мультиформатный транскодер (MFX), регистры VGA, PCI и другие компоненты, а также различные системы: URB, оценка движения на видео, пиксельный интерполятор и исполнительный модуль (execution unit).

Не знаю, как вы, уважаемый читатель, а я всегда поражался контрасту между изяществом базовой идеи, заложенной в концепцию двоичных деревьев поиска, и сложностью реализации сбалансированных двоичных деревьев поиска (красно-черные деревья, АВЛ-деревья, декартовы деревья). Недавно, перелистывая в очередной раз Седжвика [1], нашел описание рандомизированных деревьев поиска (нашлась и оригинальная работа [2]) — настолько простое, что занимает оно всего треть страницы (вставка узлов, еще страница — удаление узлов). Кроме того, при ближайшем рассмотрении обнаружился дополнительный бонус в виде очень красивой реализации операции удаления узлов из дерева поиска. Далее вы найдете описание (с цветными картинками) рандомизированных деревьев поиска, реализация на С++, а также результаты небольшого авторского исследования сбалансированности описываемых деревьев.

Листая страницы хаба «Алгоритмы», наткнулся на топик, посвященный решению задачи локализации точки в многоугольнике: задан многоугольник (замкнутая ломаная линия без самопересечений), требуется определить — находится ли заданная точка A внутри этого многоугольника или нет. В одном из последних комментариев к топику было высказано недоумение, какое отношение такая чисто математическая задача имеет к теории алгоритмов. Имеет-имеет, причем самое непосредственное. Задача локализации является классической задачей вычислительной геометрии (не путать с компьютерной графикой). В качестве разминки предлагается взглянуть на картинку справа, на которой изображен многоугольник типа кривой Пеано (источник [1]), и попытаться ответить на вопрос — красная точка ты видишь суслика? и я не вижу, а он есть! находится внутри или снаружи многоугольника? А ниже мы (исключительно в образовательных целях) рассмотрим простую вариацию данной задачи, когда заданный многоугольник является выпуклым.