Привет, Хабр! Мы продолжаем нашу традицию и снова выпускаем ежемесячный набор рецензий на научные статьи от членов сообщества Open Data Science из канала #article_essense. Хотите получать их раньше всех — вступайте в сообщество ODS!

Статьи выбираются либо из личного интереса, либо из-за близости к проходящим сейчас соревнованиям. Напоминаем, что описания статей даются без изменений и именно в том виде, в котором авторы запостили их в канал #article_essence. Если вы хотите предложить свою статью или у вас есть какие-то пожелания — просто напишите в комментариях и мы постараемся всё учесть в дальнейшем.

Всем привет, в этом посте я расскажу о том, как мне удалось занять 11 место в конкурсе от компании Мерседес на kaggle, который можно охарактеризовать как лидера по количеству участников и по эпичности shake-up. Здесь можно ознакомиться с моим решением, там же ссылка на github, здесь можно посмотреть презентацию моего решения в Yandex.

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

Начну я с того, что немного расскажу о задаче и о том, почему я взялся ее решать. Должен сказать, что в data science я человек новый. Лет 7 назад я закончил Физический Факультет СПбГУ и с тех пор занимался тем, что получал музыкальное образование. Идея немного размять мозг и вернуться к техническим задачам впервые посетила меня примерно два года назад, на тот момент я уже работал в оркестре Московской Филармонии и учился на 3 курсе в Консерватории. Начал я с того, что вооружившись книгой Страуструпа стал осваивать C++. Далее были конечно же разные онлайн курсы и примерно год назад я стал склоняться к мысли о том, что Data Science — это пожалуй именно то, чем я хотел бы заниматься в IT. Мое “образование” в Data Science — это курс от Яндекса и Вышки на курсере, несколько курсов из специализации МФТИ на курсере и конечно же постоянное саморазвитие в соревнованиях.

Python — красивый и местами загадочный язык. И даже зная его весьма неплохо, рано или поздно находишь для себя нечто такое, что раньше не использовал. Этот пост отражает некоторые детали языка, на которые многие не обращают внимание. Сразу скажу: многие примеры являются непрактичными, но, оттого, не менее интересными. Так же, многие примеры демонстрируют unpythonic стиль, но я и не претендую на новые стандарты — я просто хочу показать, что можно делать вот так.

Приходится ждать загрузки видео >360p по несколько секунд, обрывы на середине просмотра стало уже обыденным делом и это с достаточно широким каналом.



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

Для того чтобы запрос шел мимо cdn серверов ютуба надо заблокировать диапазон ip адресов (в роутере или на компьютере).

173.194.55.0/24 и 206.111.0.0/16

Предыстория

Пару лет назад, в процессе выполнения одного проекта, связанного с выделением и сопровождением движущихся объектов, было просмотрено немало алгоритмов вычитания фона, и в итоге одним из самых интересных оказался тот, о котором дальше и пойдет речь. Основной его недостаток — куча патентов, которыми он защищен. Но одно из несомненных достоинств — наличие библиотеки под Linux, которую разрешено использовать в некоммерческих проектах. На странице с его описанием можно найти эту самую библиотеку, а также demo-программы под Windows и Android, ссылки на патенты (где и можно найти основные описания алгоритма) и прочую интересную информацию.

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

Идея распознавать людей по радужной оболочке появилась в далёком 1987 у доктора Джона Доугмана и была запатентована в 1989. Примерно тогда же появился прототип. На тот момент это была вершина технологии. Пару лет до первой коммерческой цифровой камеры + алгоритм обработки изображения на компьютерах уровня i386/i486. До сих пор я не представляю, как можно получать на таком оборудовании стабильный результат.
Задачка о которой я хочу рассказать появилась на свет где-то в 2006-2009 годах. Процессоры к этому времени несколько ускорились, появились хорошие камеры, патент 1989 года истёк и системы распознавания по глазам теперь получил право делать каждый. Люди, которые решили сделать клон системы захотели использовать современные технологии и улучшить алгоритм. Самое первое, что бросалось в глаза — старый алгоритм сравнения глаз использовал изображение глаза в близком ИК диапазоне. То, что глаза бывают цветными не учитывалось.

Пусть p — нечётное простое число. Довольно широко известно, что p представимо в виде суммы двух квадратов целых чисел p=a²+b² тогда и только тогда, когда p при делении на 4 даёт остаток 1: 5=1²+2², 13=3²+2², 17=1²+4², ...; 3, 7, 11,… непредставимы. Куда менее известно, что a и b можно записать красивой формулой, имеющей непосредственное отношение к одной эллиптической кривой. Об этом результате 1907 года за авторством немца по фамилии Jacobsthal и о связанных вещах мы сегодня и поговорим.

Совсем легко понять, почему 3, 7, 11 и прочие числа, дающие при делении на 4 остаток 3, непредставимы в виде a²+b²: квадрат чётного числа всегда делится на 4, квадрат нечётного числа всегда даёт остаток 1 при делении на 4, сумма двух квадратов при делении на 4 может давать остатки 0, 1 или 2, но никак не 3. Представимость простых чисел вида 4k+1 неочевидна (особенно если заметить, что простота существенна: число 21 хотя и имеет нужный остаток, но суммой двух квадратов не представляется).

Авторский пересказ двух публикаций с демонстрационным фильмом.

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

Предлагаем вашему вниманию первую в этом году подборку с ссылками на полезные ресурсы, интересные материалы и IT-новости

Привет, %username%!
Недавно на хабре была опубликована очень спорная статья под названием «Эксперты призывают готовиться к криптоапокалипсису». Честно говоря, я не согласен с выводами авторов о том, что «голактеко опасносте», все скоро взломают и подорожает гречка. Однако я хочу поговорить не об этом.
В комментариях к той статье я высказал мнение, что кое в чем докладчики правы и переходить на эллиптическую криптографию уже давно пора. Ну в самом деле, кто-нибудь видел в интернете ECDSA сертификат? Хотя стандарту уже без малого 13 лет, мы продолжаем по старинке использовать старый добрый RSA. В общем сказал я это, и как это часто бывает, задумался а так ли необходим переход на «эллиптику»? Да и что это за зверь такой эллиптическая криптография? Какие имеет плюсы, минусы, тонкости. Одним словом, давайте разбираться.

В прошлой статье мы подробно описали алгоритм распознавания номеров (ссылка), который заключается в получении текстового представления на заранее подготовленном изображении, содержащем рамку с номером + небольшие отступы для удобства распознавания. Мы лишь вскользь упомянули, что для выделения областей, где содержатся номера, использовался метод Виолы-Джонса. Данный метод уже описывался на хабре (ссылка, ссылка, ссылка, ссылка). Сегодня мы проиллюстрируем наглядно то, как он работает и коснёмся ранее необсужденных аспектов + в качестве бонуса будет показано, как подготовить вырезанные картинки с номерами на платформе iOS для последующего получения уже текстового представления номера.

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

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

Немного предисловия

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



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

Автоматизация тестирования – место встречи двух дисциплин: разработки и тестирования. Наверное поэтому, я отношу эту практику к сложным, но интересным.

Путем проб и ошибок мы пришли к следующему технологическому стеку:

1. SpecFlow (опционально): DSL
2. NUnit: тестовый фреймворк
3. PageObject + PageElements: UI-абстракиця
4. Контекст тестирования (информация о целевом окружении, пользователях системы)
5. Selenium.WebDriver

Для запуска тестов по расписанию мы используем TFS 2012 и TeamCity.
В статье я опишу, как мы к этому пришли, типовые ошибки и пути их решения.

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

Графический интерфейс – node based: Каждая операция производимая над изображением представляется как узел (node), узлы связны между собой связями образуя дерево (ориентированный граф) решений. Данные идут от узла (node) Read (или ноды генерирующей процедурное изображение (constant color, gradient и т. п.)) к узлу Write поэтапно подвергаясь обработке в каждом узле. Узлы делятся на: Color correct, Image transform, Image read/write/view, Image create, Image filter, Image merge, Image channel editing. Узлы Read и ноды генерирующие процедурные изображения объявляются корневыми (root) узлами, с них начинается исполнение процесса.

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


Архитектура системы

Суть проблемы

Сейчас появляется очень много материала про юнит и нагрузочное тестирования. Все поголовно пишут тесты, код создают исключительно через TDD, используют jmeter/ab. Однако, все тестирование очень тесно связано с тестовыми данными. А их нужно генерировать/писать. Проблема не стоит остро для юнит тестирования — накидал mock, погонял его и забыл. Но как быть с нагрузочным тестированием? Когда мне нужно не 1-2-5-10 объектов, а миллионы?

Большинство (php) разработчиков, которых я встречал, сталкиваясь с задачей нагрузочного тестирования своего кода, создают несколько фикстур руками и насилуют их (ab/jmeter). Полученный результат тестирования не является достоверным, но они об этом не думают. Более продвинутые пишут скрипты для генерации данных, закидывают в БД и после этого уже играются. Похвально, но таких значительно меньше, а сам способ мне не кажется идеальным — другой программист может не разобраться в говнокоде генерилки фикстур (ведь создатель писал это быстро и для утилитарных целей) и рано или поздно все либо пойдут по первому пути, либо начнут писать новую генерилку.

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

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

Фотограмметрия — технология дистанционного зондирования, позволяющая определять геометрические свойства объектов по нескольким фотографическим изображениям с разных ракурсов. Более продвинутая разновидность под названием стереофотограмметрия позволяет построить приближённую 3D-модель объекта.

Раньше фотограмметрия применялась, преимущественно, в геологии, топографии и археологических раскопках. В последнее время её начали применять в киноиндустрии, а сейчас с помощью этой техники создаётся компьютерная игра.

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

Если мы хотим узнать на сколько тот или иной объект объект сместился по отношению к его же положению на предыдущем кадре за то время, которое прошло между фиксацией кадров, то скорее всего в первую очередь мы вспомним про оптический поток (optical flow). Для нахождения оптического потока можно смело воспользоваться готовой протестированной и оптимизированной реализацией одного из алгоритмов, например, из библиотеки OpenCV. При этом, однако, очень невредно разбираться в теории, поэтому я предлагаю всем заинтересованным заглянуть внутрь одного из популярных и хорошо изученных методов. В этой статье нет кода и практических советов, зато есть формулы и некоторое количество математических выводов.

С течением времени изменяются наши представления о способах взаимодействия с компьютером. На смену «классических» клавиатуры и мыши, в нашу жизнь прочно вошли тачпады и сенсорные экраны. Но это не последняя ступень эволюции для средств ввода информации. С появлением устройств дополненной реальности, например таких, как Google Glass, возникает необходимость в интерфейсах способных гармонично вписываться в данную концепцию. Предпосылки к возникновению таких интерфейсов имеются, так, например, появились такие устройства как Intel Creative Camera, Microsoft Kinect или Leap Motion. Основными управляющими элементами в данных устройствах являются руки пользователя. Поэтому, одной из фундаментальных алгоритмических задач, для взаимодействия с подобными устройствами, является детектирование рук и пальцев пользователя и реконструкция их пространственного расположения.
В данной статье речь пойдет о одном из способов решения задачи детектирования ладоней и пальцев.

Все мы слышали о 3D графике (далее просто 3D, не путать со способом отображения — голограммами, 3D-мониторами и т.п.), многие прекрасно знают, что такое 3D и с чем его едят. Но, все же, есть и те, кто смутно себе представляет, что кроется под этой короткой аббревиатурой. Статья рассчитана на тех, кто не имеет представления о компьютерной графике. Также будет немного экскурса в историю компьютерной графики (в следующих планируемых частях).
Почему именно 3D? Как нетрудно догадаться, речь идет о 3 Dimension, или о трех измерениях. И не обязательно при этом, чтобы и отображение было в 3D. Речь идет о способе построения картинки.