Навеяно недавним постом о построении различных картинок с помощью кривой Гильберта. Будет немного теории и немного картинок.

Немного теории

Компьютерный век породил теорию R-функций — функций с «логическим зарядом», возникшую на стыке дискретного и непрерывного анализов, использующую аппарат булевой алгебры, который органически присущ и ЭВМ. На основе теории R-функций была решена обратная задача аналитической геометрии, появилась возможность строить в виде элементарной функции уравнение границы сложного объекта, и притом такое уравнение, которое обладало бы необходимыми дифференциальными свойствами. В. Л. Рвачев с помощью конструктивного аппарата теории R-функций разработал единый подход к проблеме построения координатных последовательностей для основных вариационных и проекционных методов. К настоящему времени метод R-функций был применен для решения большого числа задач электродинамики, механики деформируемого твердого тела, теории пластин и оболочек, гидродинамики и магнитной гидродинамики, теплофизики и др.

Введение

Многие сталкивались с проблемой того, что нужно быстро записать данные на flash-ку, но подлая железяка маленькое устройство ограничивало нас в скорости. Производители конечно не стоят на месте, но, для увеличения скорости, обязательно нужно покупать N-ю, модельку, а старая просто начинает пылиться на полке.
Задумавшись об этом, я начал размышлять: каким же образом можно ускорить запись, не покупая новый девайс. О том что я придумал, и почему у меня ничего не получилось и будет этот пост.

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

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

Большую популярность эта технология моделирования получила в результате успешного применения и дальнейшего развития в области автоматического распознавания речи. Исследования скрытых моделей Маркова превзошли все конкурирующие подходы, и являются доминирующей парадигмой обработки. Их способность описывать процессы или сигналы успешно изучается в течение длительного времени. Причиной этого, в частности, является и то, что технология построения искусственных нейронных сетей, редко применяется для распознавания речи и аналогичных проблем сегментации. Тем не менее, существует ряд гибридных систем состоящих из комбинации скрытых моделей Маркова и искусственных нейронных сетей, в которых используют преимущества обоих методов моделирования (см. раздел 5.8.2).

Здравствуйте, Хабросообщество!

На хабре есть описание множества интересных структур данных, таких как деревья отрезков, дуча и т.п. Если Вам интересны сложные структуры данных, то добро пожаловать под кат!

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

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

Искусственные нейронные сети применяются в различных областях науки: начиная от систем распознавания речи до распознавания вторичной структуры белка, классификации различных видов рака и генной инженерии. Однако, как они работают и чем они хороши?

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

Как видно по дискуссиям на хабре, несколько десятков хабровчан прослушали курс ml-class.org Стэнфордского университета, который провел обаятельнейший профессор Andrew Ng. Я тоже с удовольствием прослушал этот курс. К сожалению, из лекций выпала очень интересная тема, заявленная в плане: комбинирование обучения с учителем и обучения без учителя. Как оказалось, профессор Ng опубликовал отличный курс по этой теме — Unsupervised Feature Learning and Deep Learning (спонтанное выделение признаков и глубокое обучение). Предлагаю краткий конспект этого курса, без строгого изложения и обилия формул. В оригинале все это есть.

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

Введение

[1]
Фракталом (лат.«fractus» – дроблёный, сломанный, разбитый) называют сложную геометрическую фигуру, обладающую свойством самоподобия, т.е. составленной из нескольких частей, каждая из которых подобна целой фигуре. В более широком смысле под фракталами понимают множества точек в евклидовом пространстве, имеющие промежуточную (дробную) метрическую размерность (размерность Хаусдорфа).
Размерность Хаусдорфа – естественный способ определить размерность множества в метрическом пространстве. Размерность Хаусдорфа согласуется с нашими обычными представлениями о размерности в тех случаях, когда эти обычные представления есть. Например, в трёхмерном евклидовом пространстве хаусдорфова размерность конечного множества равна нулю, размерность гладкой кривой – единице, размерность гладкой поверхности – двум и размерность множества ненулевого объёма – трём.

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

За основу была взята функция smooth в MATLAB.
Данную функцию можно использовать для фильтрации сигналов. В качестве входных параметров определяются массив данных и окно усреднения.
Кому интересно, прошу под кат

В статье "Решение судоку с помощью веб-камеры" большинство решений реализовано очень красиво, за исключением самого решателя. В одном из моих старых проектов «Решатель судоку» была попытка подобрать алгоритм с комплектом эвристик для решения стандартной задачи судоку (поле 9х9). Вариант прямого полного перебора не рассматривался.

Предисловие

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

Программа написана с помощью низкоуровневого языка C++, потому что я действительно хотел понять, как же это все работает изнутри. Если вы тоже хотите начать изучение компьютерного зрения, то для этого пригодиться библиотека OpenCV. На CodeProject вы сможете найти несколько уроков по ней. Изображение с веб-камеры получается с помощью исходного кода Вадима Горбатенко (AviCap CodeProject).

Недавно на хабре в очередной подняли тему алгоритмов сортировки, а именно был хорошо описан метод Timsort.

Он, имея сложность не более O(n log n), ускоряется в случае сортировки частично упорядоченных данных и имеет сложность O(n), если данные изначально отсортированны. Но это не единственный алгоритм с такими заявленными свойствами. Существует еще как минимум два более-менее известных метода с похожей сложностью — это Smoothsort и сортировка Шелла.

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

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

Новости из мира науки: матрицы размера теперь умеют умножать за . Другими словами, доказано, что , где  — экспонента умножения матриц. Доказала это совсем недавно Вирджиния Василевска-Вильямс, улучшив тем самым оценку , полученную Копперсмитом и Виноградом в 1987 году. Я напишу про важность этого алгоритма совсем немножко. Тем, кому интересно узнать побольше, предлагается почитать посты Скотта Ааронсона, Ричарда Липтона и Билла Гасарша.

Итак, многие теоретические верхние оценки на время работы алгоритмов используют экспоненту умножения матриц. В частности, много алгоритмов на графах эксплуатируют данную идею: если A — матрица смежности графа, то  — количество (не обязательно простых!) путей длины k между вершинами i и j. Эта простая идея позволяет за время проверить, есть ли в графе треугольник (3-клика): нужно возвести матрицу смежности в куб (для этого потребуется два умножения матриц) и посмотреть на диагональ. Отметим, что речь здесь именно о теоретических оценках, поскольку продвинутые алгоритмы умножения матриц хоть и обгоняют асимптотически простой кубический алгоритм, но на практике дают ускорение только на огромных размерах матриц.

Ещё несколько примеров:

Хотя метод был разработан и представлен в 2001 году Полом Виолой и Майклом Джонсом [1, 2], он до сих пор на момент написания моего поста является основополагающим для поиска объектов на изображении в реальном времени [2]. По следам топика хабраюзера Indalo о данном методе, я попытался сам написать программу, которая распознает эмоцию на моём лице, но, к сожалению, не увидел на Хабре недостающей теории и описания работы некоторых алгоритмов, кроме указания их названий. Я решил собрать всё воедино, в одном месте. Сразу скажу, что свою программу успешно написал по данным алгоритмам. Как получилось рассказать о них ниже, решать Вам, уважаемые Хабрачитатели!

Октодеревья применяются для решения множества задач связанных с оптимизацией, визуализацией в компьютерной графике, да и не только. К примеру, знаменитый и всеми любимый idSoftware, флагман технологий в области компьютерной графики и всего остального, что относится к компьютерным играм, свой новый и, конечно же, высокотехнологичный движок id Tech 6 реализует с инновационной технологией «Sparse Voxel Octree», в основе которой лежит октодерево. Октодеревья позволяют создавать полностью разрушаемую геометрию моделей, как это сделал когда-то главный программист движка DukeNukem 3D, написав сие творение. Если касаться оптимизации, то эту структуру употребляют в движках моделирования физики, очень облегчает работу камню. Ну, и без трассировки лучей не обойдется, здесь тоже применяют октодеревья.

Под катом много трафика!

Timsort, в отличии от всяких там «пузырьков» и «вставок», штука относительно новая — изобретен был в 2002 году Тимом Петерсом (в честь него и назван). С тех пор он уже стал стандартным алгоритмом сортировки в Python, OpenJDK 7 и Android JDK 1.5. А чтобы понять почему — достаточно взглянуть на вот эту табличку из Википедии.



Среди, на первый взгляд, огромного выбора в таблице есть всего 7 адекватных алгоритмов (со сложностью O(n logn) в среднем и худшем случае), среди которых только 2 могут похвастаться стабильностью и сложностью O(n) в лучшем случае. Один из этих двух — это давно и хорошо всем известная «Сортировка с помощью двоичного дерева». А вот второй как-раз таки Timsort.

Алгоритм построен на той идее, что в реальном мире сортируемый массив данных часто содержат в себе упорядоченные (не важно, по возрастанию или по убыванию) подмассивы. Это и вправду часто так. На таких данных Timsort рвёт в клочья все остальные алгоритмы.