Сегментация изображений и выделение границ объектов (edge detection) играют важную роль в системах Computer Vision и применяются для задач распознавания сцен и выделения (определения) объектов. По большому счету, это такой же инструмент, как, например, сортировка, предназначенный для решения более высокоуровневых задач. И поэтому понимание устройства данного класса алгоритмов не будет лишним при построении подобных систем с учетом предъявляемых требований (в плане качество/производительность) и специфики поставленных задач.

В данной статье кратко описан алгоритм «Efficient Graph-Based Image Segmentation» авторов Pedro F. Felzenszwalb (MIT) и Daniel P. Huttenlocher (Cornell University), опубликованный в 2004 году. Да, алгоритм относительно старенький, но, несмотря на это, он до сих пор остается весьма популярным, демонстрируя неплохие результаты в плане производительности.

Под катом – большая смесь картинок и текста, не требовательная к текущему уровню знаний тематики. Любопытство приветствуется.

UPD: Заголовок изменен, что бы более соответствовать теме статьи

В статье пойдет речь об использовании convolution matrix (матрицы скручивания или матрицы свертки), с помощью которой можно создавать и накладывать на изображения фильтры, такие как blur, sharpen и многие другие.

Cтатья будет интересна не только веб-программистам, но и всем кто так или иначе занимается программной обработкой изображений, поскольку функции для работы с матрицей скручивания имеются во многих языках (точно известно о php и flash). Так же, статья будет интересна дизайнерам, использующим Adobe Photoshop, поскольку в нем имеется соответствующий фильтр (Filter-Other-Custom).

Примеры будут на языке PHP с использованием библиотеки GD. Теория, практика, примеры (осторожно, много картинок!)

Когда писалась эта статья, хабрапоиск по словосочетанию «Генетический алгоритм» выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить к следующему экспонату ко второй части, где описывается создание на основе ГА бота для программистской игры Robocode. Это, по последним сведениям разведки, еще не встречалось на хабре.

Часть первая. Жизнь и творчество генетического алгоритма.

Начнем издалека. Есть некоторый набор задач, которые требуют решения. Наша цель — найти действия, которые смогут преобразовать Дано (начальные условия задач) в Ответ (целевое состояние).

Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо, нас наебали, все расходимся. Например, при решении квадратного уравнения ответ (значения x1, x2) получаются из начального условия (коэффициентов a, b, c) путем применения формулы, которую мы все учили в школе. А что делать в более печальном случае, когда нужной формулы в учебнике нету? Можно попробовать с помощью мозгового штурма решить одну из задач. Аналитически. Численными методами. Силой отчаянного перебора функций. Через некоторое время послышатся мечтательное студенческое «хоть бы оно само решилось». Ага, тут-то мы и вылезаем из-за занавесок. Итак, цель — написать программу, которая бы находила функцию (программу), получающую на вход исходные данные и возвращающую годные циферки. Сила метапрограммирования, в бой!

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

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

Нам понадобится капелька абстрактного мышления, знание какого-нибудь сбалансированного дерева поиска (например, описанного мною ранее декартова дерева), умение читать простой код на C#, и желание применить полученные знания.

Итак, на повестке сегодняшнего дня — моноиды и их основное применение для кеширования вычислений в деревьях.

Моноид как концепция

Представьте себе множество чего угодно, множество, состоящее из объектов, которыми мы собираемся манипулировать. Назовём его M. На этом множестве мы вводим бинарную операцию, то есть функцию, которая паре элементов множества ставит в соответствие новый элемент. Здесь и далее эту абстрактную операцию мы будем обозначать "⊗", и записывать выражения в инфиксной форме: если a и b — элементы множества, то c = a ⊗ b — тоже какой-то элемент этого множества.

Например, рассмотрим все строки, существующие на свете. И рассмотрим операцию конкатенации строк, традиционно обозначаемую в математике "◦", а в большинстве языков программирования "+": "John" ◦ "Doe" = "JohnDoe". Здесь множество M — строки, а "◦" выступает в качестве операции "⊗".
Или другой пример — функция fst, известная в функциональных языках при манипуляции с кортежами. Из двух своих аргументов она возвращает в качестве результата первый по порядку. Так, fst(5, 2) = 5; fst("foo", "bar") = "foo". Безразлично, на каком множестве рассматривать эту бинарную операцию, так что в вашей воле выбрать любое.

Далее мы на нашу операцию "⊗" накладываем ограничение ассоциативности. Это значит, что от неё требуется следующее: если с помощью "⊗" комбинируют последовательность объектов, то результат должен оставаться одинаковым вне зависимости от порядка применения "⊗". Более строго, для любых трёх объектов a, b и c должно иметь место:
(a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
Легко увидеть, что конкатенация строк ассоциативна: не важно, какое склеивание в последовательности строк выполнять раньше, а какое позже, в итоге все равно получится общая склейка всех строк в последовательности. То же касается и функции fst, ибо:
fst(fst(a, b), c) = a
fst(a, fst(b, c)) = a
Цепочка применений fst к последовательности в любом порядке всё равно выдаст её головной элемент.

И последнее, что мы потребуем: в множестве M по отношению к операции должен существовать нейтральный элемент, или единица операции. Это такой объект, который можно комбинировать с любым элементом множества, и это не изменит последний. Формально выражаясь, если e — нейтральный элемент, то для любого a из множества имеет место:
a ⊗ e = e ⊗ a = a
В примере со строками нейтральным элементом выступает пустая строка "": с какой стороны к какой строке её ни приклеивай, строка не поменяется. А вот fst в этом отношении нам устроит подлянку: нейтральный элемент для неё придумать невозможно. Ведь fst(e, a) = e всегда, и если a ≠ e, то свойство нейтральности мы теряем. Можно, конечно, рассмотреть fst на множестве из одного элемента, но кому такая скука нужна? :)

Каждую такую тройку <M, ⊗, e> мы и будем торжественно называть моноидом. Зафиксируем это знание в коде:

public interface IMonoid<T> {
    T Zero { get; }
    T Append(T a, T b);
}

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

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

По просьбам трудящихся выкладываю описание и доказательство алгоритма Укконена.

Описание задачи

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

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.

Посетителям сайта stackoverflow.com был задан вопрос: «Какие программерские термины вы придумали, так чтобы они стали популярны в ваших кругах (то есть вы слышали, что кто-то их повторяет)?

Ниже — вольный перевод самых популярных ответов.

Существует великое множество файловых систем. Это и файловые системы для носителей информации (FAT*, NTFS, ext* и т.д.), и сетевые файловые системы (NFS, CIFS и т.д.), и виртуальные файловые системы, и великое множество других. А появлялась ли у тебя, %habrauser%, потребность в своей, еще несуществующей файловой системе? О том, как ее сделать для ОС Windows на managed-коде (.net), и пойдет речь.

Предисловие

— Кибердворник дядя Федя силой ровно в три медведя, — сообщил Поль, извлекая из недр кибердворника блок регулировки. — Я тут уже знаю одного Федю. Приятный такой, веснушчатый. Очень, очень асептический молодой человек. Это не твой родственник?

Аркадий и Борис Стругацкие (Полдень. ХХII век).

Статья посвящена вопросу применимости генетических алгоритмов к проблеме идентификации динамической системы.
Обновлено: опубликовано продолжение ТАУ-Дарвинизм: реализация на Ruby

Совсем недавно я понял, отчего многие программисты, использующие PHP, отличаются от программистов «в целом». Основой для моего понимания стали слова Руслана Косолапова: «Это PHP. Понять невозможно, только запомнить». А ведь действительно, это так. Объясню, почему.

Покупая билет на поезд дальнего следования РЖД, можно воспользоваться услугой электронной регистрации. Это когда приходишь на поезд с паспортом и вообще без билета. Оно неоднократно опробовано и прекрасно работает.

У электронной регистрации мне известны три проблемы.
1) [Животрепещущая] Туалеты на вокзалах платные. Но за два часа до отправления и в течение двух часов после прибытия — бесплатно (Вы этого не знали? Упс, вокзальные туалеты теперь постигнет хабраэффект...)
При наличии электронного билета гадить бесплатно вы можете только в комментах, но не на вокзале.

2) [Бюрократическая] Если вы едете в командировку от организации, особенно государственной, то бухгалтерии нужен билет в качестве обоснования, что вы не лось.
Электронный билет — вы электронный лось.

3) [Основная] Подходя к поезду, вы должны знать свой номер вагона! Иначе вам придётся идти к начальнику поезда и искать свою фамилию в списке — а если вы пришли к поезду впритык, то можете этого и не успеть!

И вот к этой-то проблеме я и предлагаю гризманки-решение.

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

Стадия первая. Рождение

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

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

24-ого ноября была раскрыта 0day уязвимость, затрагивающая все наиболее популярные ныне операционные системы семейства Windows, а именно Windows XP, Vista, 7, а также Windows Server 2008. На данный момент под ударом находятся даже системы со всеми установленными обновлениями безопасности, причём как 32-х, так и 64-х битные редакции. Технические детали уже были опубликованы на китайском форуме и привели к предположению, что скоро злоумышленники начнут вовсю использовать уязвимость.

Здравствуй, хабрачитатель.

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

Hg Init: Учебное пособие по Mercurial.

Mercurial — это современная распределенная система контроля версий с открытым кодом. Эта система — заманчивая замена для более ранних систем вроде Subversion. В этом простом учебном пособии в шести частях Джоэль Спольски (Joel Spolsky) рассказывает о ключевых принципах Mercurial.

Если вы использовали Subversion, то Mercurial будет непонятным. Эта часть рассказывает о главных отличиях при работе с Mercurial. Если вы никогда не использовали Subversion, то можете просто пропустить эту часть.

Часть 1. Переобучение для пользователей Subversion

В каком же я был смятении, когда программисты в моей компании решили сменить Subversion на Mercurial!

Для начала, я начал приводить всевозможные тупые причины, по которым нам не надо ничего менять. «Мы должны хранить репозиторий на центральном сервере, так безопаснее», — сказал я. Знаете что? Я был неправ. При работе с Mercurial у каждого разработчика на жестком диске хранится полная копия репозитория. Это, на самом деле, безопаснее. В любом случае, почти в каждой команде, использующей Mercurial, центральный репозиторий тоже существует. И вы можете делать резервное копирование этого репозитория со всей необходимой одержимостью. А еще можете устроить трехступенчатую защиту с Сайлонами, Штурмовиками и прелестными лабрадудлами или что там требует ваш IT-отдел.

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



Служба XMPP позволяют GAE-приложениям отправлять и принимать жаббер-сообщения.
XMPP – открытый протокол обмена мгновенными сообщениями, на основе XML, так же известный как Jabber. Именно он уже используется в Google Talk.

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