Оптический поток (Optical flow) – технология, использующаяся в различных областях computer vision для определения сдвигов, сегментации, выделения объектов, компрессии видео. Однако если мы захотим его по-быстрому реализовать в своем проекте, прочитав про него на википедии или где-нибудь еще, то, скорее всего, очень быстро наткнемся на то, что он работает очень плохо и сбоит при определении сдвигов уже порядка 1-2 пикселей (по крайней мере так было у меня). Тогда обратимся к готовым реализациям, например, в OpenCV. Там он реализован различными методами и совершенно непонятно, чем аббревиатура PyrLK лучше или хуже обозначения Farneback или чего-нибудь в этом роде, да и придется поразбираться со смыслом параметров, которых в некоторых реализациях очень много. Причем, что интересно, эти алгоритмы как-то работают, в отличие от того, что мы написали сами. В чем же секрет?

Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

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

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

Библиотека libcds имеет свою точку зрения на многие известные структуры данных. Отчасти это объясняется целевой областью – lock-free структуры данных довольно минималистичны по набору предоставляемых методов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому интересно – добро пожаловать под кат

Построение lock-free структур данных зиждется на двух китах – атомарных операциях и способах упорядочения доступа к памяти. В этой статье речь пойдет об атомарности и атомарных примитивах.

Анонс. Спасибо за теплый прием Начал! Вижу, что тема lock-free интересна хабрасообществу, это меня радует. Я планировал построить цикл по академическому принципу, плавно переходя от основ к алгоритмам, попутно иллюстрируя текст кодом из libcds. Но часть читателей требует зрелищ не мешкая показать, как пользоваться библиотекой, особо не рассусоливая. Я согласен, в этом есть свой резон. В конечном счете, и мне не так интересно, что там внутри boost, — опишите, как его применять! Поэтому свой эпический цикл я разделю на три части: Основы, Внутри и Извне. Каждая статья эпопеи будет относится к одной из частей. В Основах будет рассказываться о низкоуровневых вещах, вплоть до строения современных процессоров; это часть для почемучек вроде меня. Внутри будет освещать интересные алгоритмы и подходы в мире lock-free, — это скорее теория о том, как реализовать lock-free структуру данных, libcds будет неисчерпаемым источником C++ кода. В Извне будут статьи о практике применения libcds, — программные решения, советы и FAQ. Извне будет питаться вашими вопросами/замечаниями/предложениями, дорогие хабражители.

А пока я судорожно готовлю начало Извне, — первая часть Основ. Статья во многом не о C++ (хотя и о нем тоже) и даже не о lock-free (хотя без atomic lock-free алгоритмы неработоспособны), а о реализации атомарных примитивов в современных процессорах и о базовых проблемах, возникающих при использовании таких примитивов.
Атомарность — это первый круг ада низкий уровень из двух.

Продолжение.
Предыдущие части: 1-3, 4-6, 7-9

10. Нормализация баз данных

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

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

Аннотация

Около года назад мы опубликовали в блоге цикл статей о разработке плагинов для Visual Studio на языке C#. Сейчас мы переработали эти материалы, добавили новые разделы и предлагаем вашему вниманию новый вариант руководства.

Доброго времени суток уважаемые хабражители. Буквально только что увидел потрясающий проект на GitHub от FredrikNoren.

Ungit:

• Чистый и интуитивно понятный интерфейс для Git (что есть невероятно круто для освоения Git)
• Работает на любой платформе с установленными Node.js и самим Git
• Веб-ориентированный. Возможность запускать его в облаке.
• GitHub

Необходим Node.js версии 0.10 или выше и npm версии 1.3.1 или выше

Установка

npm install -g ungit

Я думаю, что после просмотра видео, моего более тщательного описания не потребуется. Спасибо всем за внимание.

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

Итак, идея

Всё началось с того, что в один прекрасный день я решил жениться! Заявление, подготовка к празднику, все дела. Но вот задача: сделать оригинальные приглашения на свадьбу. Подписывать куски картона не хотелось. Душа просила хардкорного хэндмэйда, далёкого от традиционных свадебных шаблонов. И вот на моё “и вообще, можно электронные девайсы сделать” невеста сказала: “Круто! Давай!”

Оригинальный pdf (на английском)
Переведённый pdf (на русском)

    На написание данного текста меня сподвигло ощущение незнания многими принципов работы, использования (или даже незнание о существовании) параллельной защиты от импульсных перенапряжений в сети, в том числе и вызванных разрядами молний
    Импульсные помехи в сети довольно распространены, они могут возникать во время грозы, при включении/выключении мощных нагрузок (поскольку сеть это RLC цепь, то в ней при этом возникают колебания, вызывающие выбросы напряжения) и многие другие факторы. В слаботочных, в том числе цифровых цепях, это еще более актуально, поскольку коммутационные помехи достаточно хорошо проникают через источники питания (больше всего защищенными являются Обратноходовые преобразователи — в них энергия трансформатора передается на нагрузку, когда первичная обмотка отключена от сети).
    В Европе уже давно де-факто практически обязательна установка модулей защиты от импульсных перенапряжений (далее буду, для простоты, называть грозозащитой или УЗИП), хотя сети у них получше наших, а грозовых областей меньше.
    Особо актуальна стало применение УЗИП последние 20 лет, когда ученые стали разрабатывать все больше вариантов полевых MOSFET транзисторов, которые очень боятся превышения обратного напряжения. А такие транзисторы используются практически во всех импульсных источниках питания до 1 кВА, в качестве ключей на первичной (сетевой) стороне.
    Другой аспект применения УЗИП — обеспечение ограничения напряжения между нейтральным и земляным проводником. Перенапряжение на нейтральном проводнике в сети может возникать, например, при переключении Автомата ввода резерва с разделенной нейтралью. Во время переключения, нейтальный проводник окажется «в воздухе» и на нем может быть что угодно.

WinDbg — позволяет отлаживать 32/64 битные приложения пользовательского уровня, драйвера, может быть использован для анализа аварийных дампов памяти, WinDbg поддерживает автоматическую загрузку отладочных символов, имеется встроенный скриптовый язык для автоматизации процесса отладки, скачать отладчик можно тут.

Введение

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

Матчасть

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

A( x1;y1 )
B( x2;y2 )
C( x3;y3 )

расстояния между точками находятся по теореме Пифагора

a^2 = b^2 + c^2 — 2*b*c*cos(ALPHA)
cos(ALPHA) = (b^+c^-a^) / 2*b*c

Зная косинус, величину угла легко можно вычислить.

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

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

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

Если, допустим, у нас есть несколько анализируемых каркасов, например, «8» и «6». И результат алгоритма распознавания: «8»-80%, «6» — 90%, то решение принимается в пользу той фигуры, в каркасе которой присутствует больше контрольных точек, т.е в пользу восьмерки.

Процент сходства набора точек с точками в каркасе высчитывается просто: суммируются все точки, которые сошлись с теми же точками в каркасе и находится отношение. Допустим, если в каркасе N контрольных точек, а у нас сошлось M, то процент сходства — M / N * 100

Скрытые модели/цепи Маркова одни из подходов к представлению данных. Мне очень понравилось как обобщается множество таких подходов в этой статье.

В продолжение же моей предыдущей статьи описания скрытых моделей Маркова, задамся вопросом: откуда взять хорошую модель? Ответ достаточно стандартен, взять неплохую модель и сделать из нее хорошую.

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

PEB — структура процесса в windows, заполняется загрузчиком на этапе создания процесса, которая содержит информацию о окружении, загруженных модулях (LDR_DATA), базовой информации по текущему модулю и другие критичные данные необходимые для функционирования процесса. Многие системные api windows, получающие информацию о модулях (библиотеках) в процессе, вызывают ReadProcessMemory для считывания информации из PEB нужного процесса.

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

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

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

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

Моему сыну, как и многим мальчишкам, нравятся автомобили. Причём чем они больше и необычнее — тем больше нравятся. Когда мы идём по улице, а мимо проезжает эвакуатор или снегоуборочная машина, он неизменно дёргает меня за руку, указывает на заинтересовавший его объект и говорит: «Папа, б-р-р!». Говорит он так потому, что ему один год и вышеуказанные два слова составляют 40% его словарного запаса. Тем ни менее, в общем мысль понятна — обратить внимание на автомобиль. Давайте подумаем, каким образом ребёнок в возрасте 8-10 лет сказал бы своему сверстнику то же самое. Что-то вроде «Ух ты, смотри какая крутая тачка!», да? Мысль та же, но обратите внимание — уже шесть слов вместо двух. И, наконец, представьте, каким образом то же самое скажет человек лет в тридцать: «Эй, смотри, да это же Ferrari California 2008-го года выпуска с двигателем V8 мощностью в 454 лошадиных силы и 7-ми скоростной коробкой-автоматом! Она до сотни разгоняется за 3.9 секунды!». Да, здесь уже больше деталей, но, если вы не автомеханик или фанат Ferrari — они вам скорее всего не нужны и не важны. Основная же мысль — всё та же, что и в «Ух ты, смотри какая крутая тачка!» или «Папа, б-р-р!». Но выражена она уже в 30 слов.

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

Уважаемые Хабрапользователи!

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

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

Наверняка вы хоть раз видели химические источники света — светящиеся палочки, которые начинают работать после «переламывания». Внутри — стеклянная капсула, которая при этом ломается, и начинается какая-то мистическая химическая реакция. Мне всегда было интересно разобраться, как это работает.

Энергия связи молекул, освобождающаяся во время химической реакции — может выделится в виде тепла (к чему мы все привыкли), а в редких случаях может — в виде излучения кванта света. Излучение света во время химической реакции называется хемилюминесценцией. Существуют 2 наиболее распространенных реакции с хемилюминесценцией: окисление Люминола и окисление TCPO в присутствии органических красителей.

Отличие в том, что Люминол светится сам, а TCPO — передает энергию молекулам органического красителя (вроде Родамина), и таким образом можно управлять цветом свечения выбирая краситель. Про TCPO (включая его синтез) можно посмотреть на YouTube (использование синтез), а вариант с Люминолом — под катом.

Уже не является секретом тот факт, что полные исходные тексты известного банковского вредоносного ПО Carberp утекли в паблик. Около 5GB исходных текстов оказались в поле зрения фактически любого желающего. Архив включает в себя:

• Исходный текст буткита, km драйверов и всего что работает в km.
• Билдер дропперов.
• Плагины.
• Веб-инжекты.
• LPE эксплойты.
• Огромное количество другой полной и необходимой информации, чтобы начать свой собственный проект по разработке вредоносного кода.

Как и в случае с Zeus, история началась с того, что архив с текстами был выставлен на продажу на нескольких подпольных форумах. Ниже представлен пост с объявлением с одного из форумов. Первоначально информация о том, что исходные тексты Carberp были выставлены на продажу была опубликована Trusteer 18-го июня, т. е. около недели назад. При этом указывалось, что цена архива составляет $50,000. Но позже на одном из форумов появилась информация, что тексты продаются по очень низкой цене, всего лишь $5,000. Архив включает в себя тексты вредоносного кода и купленные сторонние наработки с 2008 г.