Алгоритмы *

Многие документы содержат защитные элементы, такие как голограммы, водяные знаки, гильош и т.д. В процессе сканирования таких документов возникает проблема — защитные элементы мешают системам распознавания (OCR). При разработке Smart PassportReader мы провели исследование, направленное на поиск и устранение подобных защитных элементов с изображений документов.

Рассмотрим пример паспорта гражданина РФ, на котором легко увидеть периодический голографический узор.



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

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

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


А если не видели, то это результаты Хинтона и Крижевского по классификации ImageNet-2010 глубокой сверточной сетью

Давайте взглянем на ее правый угол, где алгоритм опознал леопарда с достаточной уверенностью, разместив с большим отрывом на втором и третьем месте ягуара и гепарда.

Это вообще довольно любопытный результат, если задуматься. Потому что… скажем, вы знаете, как отличить одного большого пятнистого котика от другого большого пятнистого котика? Я, например, нет. Наверняка есть какие-то зоологические, достаточно тонкие различия, типа общей стройности/массивности и пропорций тела, но мы же все-таки говорим о компьютерном алгоритме, которые до сих пор допускают какие-то вот такие достаточно глупые с человеческой точки зрения ошибки. Как он это делает, черт возьми? Может, тут что-то связанное с контекстом и фоном (леопарда вероятнее обнаружить на дереве или в кустах, а гепарда в саванне)? В общем, когда я впервые задумался над конкретно этим результатом, мне показалось, что это очень круто и мощно, разумные машины где-то за углом и поджидают нас, да здравствует deep learning и все такое.

Так вот, на самом деле все совершенно не так.

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

Меня настолько заинтересовал вопрос о книгах, что я решил начать новую серию статей на своём сайте catonmat о моих топ-100 книгах о программировании, программном обеспечении, науке, физике, математике и компьютерах. В каждой статье я буду размещать по пять книг, ведь разбивать огромное задачи на маленькие подзадачи — это самый простой способ их решать (GTD — get things done).

Взгляните на мою книжную полку, чтобы убедиться, что я настоящий ботаник:

Вместо введения

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

В комментариях попросили рассказать подробнее о структуре данных, скрывающейся за priority_queue в STL C++. В конце статьи приводится краткий рассказ и ее реализация.

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

Не хотелось бы, чтобы пост воспринимался в ключе холиваров на тему SQL vs. NOSQL И так понятно что везде есть свои плюсы и минусы, в данном случае это просто где-то немного справки, где-то немного примеров из того, с чем приходилось сталкиваться. Примеры на mongo shell и на python.

1. Миграция в на новые версии в mongodb
   
   • До версии 2.6
   • С 2.6 до 3.0 версии
   • Новое в PyMongo
2. Запросы сравнения и логические
3. Полнотекстовый поиск в Mongodb, regexp, индексы и пр.
4. Атомарные операторы (модифицирующие данные )
5. Немного о транзакциях в Mongodb
   
   • Уникальный индекс
   • Двухфазный коммит
6. Агрегационный фреймворк и JOIN-ы в Mongodb
7. Примеры
   
   • Деревья, комментарии в Mongodb
   • Теги, блоги
   • Е-commerce, и сложные фильтры в Mongodb
8. Небольшая песочница на Python

В чем ее измерить? И какую полезную конверсию мы хотим получить от видеоаналитики?

Перевод поста Anneli Mossberg и Olle Isaksson "Modeling Aircraft Flap System Failure Scenarios with SystemModeler".
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

Вы что-нибудь слышали о Boeing 747 Dreamlifter, который прилетел не к тому аэропорту и был вынужден приземляться на слишком короткую взлётно-посадочную полосу? К счастью, эта история имела счастливую развязку, и никто из пассажиров не пострадал. Тем не менее, это весьма опасная ситуация — когда фактическая посадочная дистанция (далее — ФПД) длиннее взлётно-посадочной полосы, и возникать она может не только из-за ошибки пилота, который сбился с верного пути.

Одна из возможных причин такого сценария — неисправность закрылков. Закрылки — шарнирные устройства, расположенные на задних краях крыльев, их угловое положение регулируется для изменения подъёмных свойств самолёта. К примеру, определённое положение закрылков может позволить самолёту лететь на меньшей скорости при наборе высоты, или приземляться под более крутым углом, при этом не увеличивая скорость. Одно из главных их преимуществ состоит в том, что ФПД становится короче. Вот что меня озадачивает: Может ли небольшая неисправность закрылка увеличить ФПД настолько, что взлётно-посадочная полоса окажется слишком короткой?

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

Идея написания первой статьи на Хабр возникла в процессе «собирания камней» для создания серверной системы, основные задачи которой:

• получение заявок от пользователей на некоторые типовые последовательные «тяжелые» вычисления;
• осуществление вычислений;
• выдача информации (по запросу) об оставшемся времени вычислений;
• выдача результатов вычислений по их завершению.

Следует уточнить ряд обстоятельств исследования:

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

Думаю все из нас, кто учился на ИТ-специальностях, в университете изучали конечные автоматы. Для тех, кто не в курсе, это абстрактный автомат способный находиться в конечном количестве состояний, переход из одного состояния в другое происходит при выполнение некоторых условий. Штука интересная, но не совсем понятно когда и как это можно применить для решения реальных задач. О том, как я пришел к решению возникшей задачи на основе конечного автомата, а также о том, как реализовал его на bash, я бы и хотел рассказать. А в качестве бонуса опишу как сохранять его состояние для возможности восстановить работу с прерванной точки.

Сегодня мы публикуем последнюю лекцию курса «Анализ изображений и видео», прочитанного Натальей Васильевой — старшим научным сотрудником HP Labs и руководителем HP Labs Russia. Наталья Сергеевна читала курс, посвящённый анализу изображений, в петербургском Computer Science Center, который создан по совместной инициативе Школы анализа данных Яндекса, JetBrains и CS клуба.



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

1. Введение в курс «Анализ изображений и видео»;
2. Основы пространственной и частотной обработки изображений;
3. Морфологическая обработка изображений;
4. Построение признаков и сравнение изображений: глобальные признаки;
5. Построение признаков и сравнение изображений: локальные признаки;
6. Поиск по подобию. Поиск нечетких дубликатов;
7. Классификация изображений и распознавание объектов;
8. Анализ изображений и видео. Сегментация изображений.

Под катом вы найдете план новой лекции и слайды.

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

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

В прошлом году в Санкт-Петербургском академическом университете открылся бакалавриат (А), готовящий студентов по информатике с дальнейшей специализацией по теоретической информатике, разработке программного обеспечения или биоинформатике.

В этом году в Санкт-Петербургском государственном университете открывается бакалавриат (Ч) по математике и теоретической информатике.

Поскольку я принимал участие в создании обеих этих программ, коллеги настойчиво рекомендуют мне объясниться. (Зовут меня Эдуард Гирш, и я работаю в лаборатории математической логики ПОМИ РАН.)

Суффиксное дерево – мощная структура, позволяющая неожиданно эффективно решать мириады сложных поисковых задач на неструктурированных массивах данных. К сожалению, известные алгоритмы построения суффиксного дерева (главным образом алгоритм, предложенный Эско Укконеном (Esko Ukkonen)) достаточно сложны для понимания и трудоёмки в реализации. Лишь относительно недавно, в 2011 году, стараниями Дэни Бреслауэра (Dany Breslauer) и Джузеппе Италиано (Giuseppe Italiano) был придуман сравнительно несложный метод построения, который фактически является упрощённым вариантом алгоритма Питера Вейнера (Peter Weiner) – человека, придумавшего суффиксные деревья в 1973 году. Если вы не знаете, что такое суффиксное дерево или всегда его боялись, то это ваш шанс изучить его и заодно овладеть относительно простым способом построения.

Перевод статьи Стивена Вольфрама (Stephen Wolfram) "The History and Future of Special Functions".
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

Статья представляет собой запись выступления, сделанного на Wolfram Technology Conference 2005 в Шампейне, штат Иллинойс, как часть мероприятия в честь 60-летия Олега Маричева.

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


История многих понятий и объектов математики прослеживается ещё со времён древнего Вавилона. Ведь ещё 4000 лет назад в Вавилоне была разработана и активно использовалась 60-ричная арифметика с различными сложными операциями.

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

По сути, деление сводилось к сложению и вычитанию обратных величин. А умножение довольно хитрым образом сводилось к сложению и вычитанию квадратов.

Таким образом, практически любые вычисления сводились к работе с таблицами. И, конечно, археологам доводилось находить вавилонские таблички из глины с таблицами обратных величин и квадратов.

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

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

Следующие «куски» были, вероятно, теми, которые включают тригонометрию. Египетский папирус Ринда 1650-го года до н.э. уже содержал некоторые проблемы касательно пирамид, решение которых требовало тригонометрии. Стоит упомянуть, что была найдена вавилонская табличка с таблицей секансов.

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

Одной из важных технологий любой серьезной системы мониторинга сетей является метод обнаружения связей сетевых элементов на 2-м и 3-м уровне модели OSI.



С точки зрения алгоритмов эта задача является одной из самых интересных встреченных нами во время разработки нашей системы.

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

После первой публикации в обсуждении статьи появилась вопросительная ссылка, на которую я хотел бы ответить другой развернутой статьей. Ее автор – под ником «psazhin» – попал просто в точку, приведя пример классической «жесткой» видеоаналитики — как мы помним, разработанной и похороненной Интелом, реинкарнированной рекламным хайтеком. Хотя, промазать здесь сложно, потому что 90% всего рынка видеонаналитики – как капли воды повторяют интеловскую библиотеку Open CV. Ну, раз выбор пал на фирму Синезис, то проведем конкретный анализ её «интеллектуальных» алгоритмов на базе уже выработанной методики.

Мы лишь немного вдумчивей прочитаем то, что написано на рекламном сайте этой фирмы. Берем первую самую главную настройку.

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

Уже по самой масштабности можно приклеить этому направлению понятие «классическое». Тем более что у истоков стояла фирма Intel, а это уже классика. Именно на базе ее библиотеки с открытым кодом Open CV до сих пор делают свои продукты разработчики видеонаблюдения. Гордости ради надо сказать, программисты этого направления – русские и к тому же располагались в России – в нижегородском филиале Intel. Почему располагались? Направление закрыто уже несколько лет, народ разошелся по другим фирмам. Видимо, Intel первым почувствовал бесперспективность своей «классики».

Тем не менее, дело его живет и активно развивается. Только самый ленивый разработчики систем видеонаблюдения не применил Open CV в своих «интеллектуальных» кодах. И эта библиотека после своей смерти творит чудеса! Как заявляют многие продавцы систем видеонаблюдения, вычисляет криминальные моменты, детектирует драки, определяет оставленные и унесенные предметы, находит экстремистов… И пипл хавает. Миллиарды рублей вбухиваются в такие задачи для проектов «Безопасный город», «Безопасность на метрополитене», «Операция антитеррор» и т.д. Но, это больше политика, мы же поговорим о технологиях, почему эта красивая обертка для выставок не может работать на практике.

После прочтения статьи про CGA от SLY_G я необычайно возбудился. Вспомнил юность, IBM PC/XT и игру frogger jr, в которой лягушка должна была пересечь дорогу, избежав колес бешено мчавшихся байков. Затем по бревнам допрыгать до тихой заводи. И так до смерти, которых выдавали 4 штуки. Фраю выдали 666, но я не Макс.
Поплакав о безвозвратно потерянных годах, я решил потерять еще пару дней и сделал ремейк игры под iPad.

Движение воды в речке решил смоделировать по-правильному, через разностную схему.
О численном алгоритме моделирования озерных волн и о том, что получилось, читайте дальше.
Да! забыл сказать.
Тем, кто может продолжить последовательность

T T F S E...

читать будет не особенно интересно.

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

Преобразование Фурье
Для ФБД будем интерпретировать процесс как временной процесс. Существует частотная область, в которой функция — сумма составляющих, имеющих определенную частоту. Функция может быть разложена как .
Составляющая с частотой имеет вид:

, где .

Функция называется преобразованием Фурье.

Приветствую, Хабр! В этой публикации хочу представить свой опыт реализации алгоритма анализа ВСР человека в MATLAB. Теме анализа ВСР уделено достаточно внимания на Хабре. (поиск по слову ЭКГ) однако, как мне показалось, некоторые моменты раскрыты слабо или вовсе не рассматриваются. В данной статье не уделяется много внимание объяснению явления ВСР и теории методов ее анализа. Подразумевается, что читатель подготовлен, а основной упор сделан на использование для целей анализа функций и процедур MATLAB.