Алгоритмы *

Представляю вашему вниманию заключительную статью из трилогии «Восстановление расфокусированных и смазанных изображений». Первые две вызвали заметный интерес — область, действительно, интересная. В этой части я рассмотрю семейство методов, которые дают лучшее качество, по сравнении со стандартным Винеровским фильтром — это методы, основанные на Total Variaton prior.
Также по традиции я выложил новую версию SmartDeblur (вместе с исходниками в open-source) в которой реализовал этот метод. Итоговое качество получилось на уровне коммерческих аналогов типа Topaz InFocus. Вот пример обработки реального изображения с очень большим размытием:

Алгоритм Particle Filter замечателен своей простотой и интуитивной понятностью. Предлагаю собственный вариант его использования в задаче стереоскопического зрения для сопоставления «одной и той же точки» на двух изображениях — с левой и правой камеры. Для реализации (исключительно в целях развлечения) использован Python с библиотеками numpy (матричные вычисления) и pygame (графика и обработка событий мышки). Сам алгоритм Particle Filter без изменений взят из курса Programming a Robotic Car на Udacity. Меня извиняет лишь то, что я честно прослушал весь курс и сделал все домашние работы, включая и реализацию этого алгоритма.

В задаче стереоскопического зрения нужно сопоставлять малые области (например, 8х8 пикселей) на левом и правом кадре. При идеальном расположении камер строго горизонтально, зная разность координаты по оси Х одинаковой области между левым и правым кадром, можно вычислить расстояние до объекта, который изображен в этой области. Понимаю, что звучит запутанно, но на самом деле это легко выводится простейшими геометрическими построениями по правилу подобных треугольников. Например, на видео с недостроенной колокольней, мы видим уходящий вдаль забор с одинаковыми ромбами. Ближний к нам ромб наиболее сильно смещен на правом кадре относительно левого, следующий — чуть меньше и т.д.

Стандартная схема решения такой задачи довольно тяжелая в вычислительном плане. Нужно откалибровать погрешности взаимного расположения камер так, чтобы гарантировать, что горизонтальная линия с координатой Y на левом кадре точно соответствует горизонтали с той же координатой на правом кадре. Затем сопоставить каждой точке (или области ) вдоль горизонтальной линии на левом кадре наилучшую точку на правом кадре (это решается, например, методом динамического программирования, имеющем квадратическую сложность). Тогда у нас будут вычислены смещения по Ох для каждой точки вдоль рассматриваемой горизонтали. И повторить процедуру для каждой горизонтальной линии. Немного сложновато, и уж совсем не похоже на то, как это работает в мозге (мы ведь знаем это, правда?)



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

Прочитав пост http://toster.ru/2410/, я написал функцию, которая определяет из строки слов их части речи. Определение, конечно не 100%, но можно легко дорабатывать.

Функция возвращает массив значений групп:

• 1. прилагательное
• 2. причастие
• 3. глагол
• 4. существительное
• 5. наречие
• 6. числительное
• 7. союз
• 8. предлог

Пример вызова функции:

print_r(chastrechiRUS('В небе летит красивый сверкающий самолёт'));

Результат работы функции (массив):

Array ( [0] => 8 [1] => 4 [2] => 3 [3] => 1 [4] => 2 [5] => 4 )

Как сообщает Брюс Шнаер в своём блоге Национальный институт стандартов и технологий США (National Institute of Standards and Technology, NIST) собирается в скором времени представить новый хеш-алгоритм, который будет называться SHA-3.

За право бороться в финале на звание нового SHA-3 NIST выбрало 5 финалистов: BLAKE, Grøstl, JH, Keccak, и Skein. Последний является детищем самого Брюса Шнаера.

В предыдущей публикации был рассмотрен алгоритм решения задачи коммивояжёра на плоскости рекурсивным полным перебором. Результат получился любопытным, но итоговый маршрут содержал очевидные неоптимальные участки. В предлагаемой заметке рассмотрен улучшенный алгоритм, который я назвал «рекурсивным жадным алгоритмом». Признаюсь сразу, итоговый маршрут в сравнении с рекурсивным полным перебором получается лучше, в среднем, на 8%.

В связи с дельной критикой хабрахабровцев, я кардинально переделал пост. Надеюсь, такой вариант будет оценен более положительно.

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

В этом посте я хочу поделиться полученным опытом и рассказать о технологии распознавания рукописного текста.

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

История вопроса

Заказчик разрабатывает динамические музыкальные фонтанные комплексы, которые управляются через dmx контроллеры по сценарию. Редактор сценариев он сделал самостоятельно. Но на практике создавать сценарии оказалось неудобным, потому что для того, чтобы видеть как получается нужно иметь целиком построенный и запущенный фонтан. Кроме того, если вдруг дизайнеру хореографу захотелось добавить дополнительные сопла для фонтана — то этого сделать уже практически невозможно. Поэтому заказчик захотел обзавестись модулем для моделирования фонтанов, чтобы хореограф мог без настоящего фонтана разрабатывать сценарии. В целом у меня вышло что-то в таком духе: вот видео того что было смоделировано Hawaii50.wmv, а вот то, что вышло в реале после конструирования фонтана: H5OClip.wmv

Месяц назад несколько раз на Хабре проскакивали статьи о замечательном ресурсе Coursera, где можно пройти курсы обучения по различным направлениям. Среди прочего меня очень заинтересовал курс «Алгоритмы» (часть 1), на который я подписался и начал его изучать. Сейчас курс приближается к завершению, а я решил написать небольшой отчет по первой части курса (надеюсь меня хватит и на описание второй части курса по его завершению), чтобы уважаемый %username% мог определить стоит ли записываться на следующую итерацию курса или нет.

Когда на хабре был опубликован пост о том, что компания Stripe проводит конкурс Capture the Flag, я незамедлительно зарегистрировался как участник.

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

Уровни с 0-го по 6-й не представляли особого труда — стандартные SQL- и JavaScript-инъекции, загрузка на сервер PHP-скрипта вместо картинки и т.п.

А вот 7-й уровень заставить меня поломать голову…

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

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

Предлагаю ознакомиться с принципом работы алгоритма Диффи – Хеллмана в замечательном видео от Art of the Problem в моем переводе.

Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.

Фильтр размытия по гауссу (широко известный “gaussian blur” в фотошопе) достаточно часто применяется сам по себе или как часть других алгоритмов обработки изображений. Далее будет описан метод, позволяющий получать размытие со скоростью, не зависящей от радиуса размытия, используя фильтры с бесконечной импульсной характеристикой.

На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.

Признавайтесь, кто в детстве часами напролёт просиживал за игрой в «Денди» или «Сегу»? А кто по мере прохождения игры записывал пароли на бумажку или в специально заведённую тетрадку? Если это вы, и раз уж вы читаете этот сайт, то у вас наверняка хоть раз возникал вопрос: «а как же это работает?»

Я постараюсь объяснить принципы работы классических механизмов генерации паролей на примерах из игр моего детства. Заранее прошу меня извинить за то, что все примеры будут с платформы NES (да, та, которая «Денди»), хотя тематика только ею не ограничивается. Так уж получилось, что не нашёл в себе достаточно мотивации, чтобы провести немного больше исследований и написать немного больше текста.

«Что позволило остаться GIF, это — циклическое проигрывание анимации, которое добавил Netscape. Если бы Netscape не добавил поддержку GIF в свой браузер, GIF умер бы в 1998»

— Александр Тревор (Alexander Trevor),
руководитель команды по созданию GIF в CompuServe

Формат GIF в июне этого года отпраздновал свое 25-летие, и является сегодня самым старым графическим форматом, который распространен в интернете. Посвящая выходные просмотру смешных анимированных гифок понимаешь, что некоторые из них были бы в разы лучше со звуком. Все текущие решения для циклической анимации со звуком (например: coub.com, gifsound.com) предлагают отказаться от GIF, но это — не выход. И я решил пожертвовать просмотром гифок на выходных для решения этой крайне важной проблемы.

Первая в интернете гифка со звуком по ссылке. Надо нажать на синюю кнопку, а потом на гифке. Плеер должен работать во всех современных браузерах (тестировался в последнем Firefox и Chrome).

Гифок под катом не будет, а будет процесс создания расширения для стандарта, написания конвертера и плеера.

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

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

Однако обе эти формулировки при ближайшем рассмотрении оказываются частными случаями первоначальной формулировки.
Формулировка 1 подразумевает, что входным узлом может быть любой узел, а выходным — один из ближайших к нему. Что требует полного перебора всех ближайших узлов к произвольно выбранному узлу.
Формулировка 2 подразумевает, что входной узел задан, а выходным узлом может быть любой. Что требует полного перебора всех выходных узлов с последующим выбором кратчайшего пути из всех кратчайших.
Поэтому мы остановимся на первоначальной формулировке, и будем решать задачу в общем виде.

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

Когда мы рассуждаем о сильном искусственном интеллекте, то мы понимаем, что это не изолированный вопрос, не вещь в себе, а вопрос ответ на который подразумевает объяснение всех явлений, которые связаны с мышлением человека. То есть, ответив на вопрос о природе интеллекта, мы неизбежно должны будем ответить на такие вопросы как:

• Что есть информация?
• Как мозг представляет знания?
• Что такое язык?
• Какова роль языка в мышлении?
• Как совершаются поступки?
• Как осуществляется планирование?
• Какова природа фантазий и воспоминаний?
• Что такое мотивация?
• Какова природа эмоций?
• Откуда берется многообразие эмоциональных оценок?
• Что есть смысл?
• Как рождается мысль и какова ее природа?
• Что такое внимание?
• Что есть любовь?
• Что есть гармония и красота?

В прошлых статьях я затрагивал тему простых рейтингов. В комментариях меня попросили расписать тему рейтингов, которые выдают для каждого пользователя свои.

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