Сегодня, дорогой Хабр, я расскажу тебе историю о комбинаторной оптимизации.
Издревле (как минимум, с начала прошлого века) математики задавались вопросом, как оптимально разместить некоторое количество пива нужных и полезных предметов в рюкзаке. Была сформулирована задача о ранце и ее подзадачи — тысячи их! — которые заинтересовали информатиков, криптографов и даже лингвистов.

От задачи о ранце отпочковалась задача об упаковке в контейнеры (Bin Packing Problem), одной из разновидностей которых является задача двумерной упаковки (2-Dimensional Bin Packing). Снова отбросив несколько вариаций, мы наконец придем к двумерной упаковке в полуограниченную полосу (2-Dimensional Strip Packing, 2DSP). Чувствуете, сколько интересного уже осталось за кадром? Но мы еще не закончили продираться сквозь классификацию. У 2DSP есть два варианта входных данных: когда набор упаковываемых объектов известен заранее (offline-проблема) и когда данные поступают порциями (online-проблема).

В этой статье рассматриваются алгоритмы решения offline-варианта 2DSP. Под катом немного матчасти и много картинок с цветными квадратиками.

В чем, собственно, проблема?

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

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

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

Тема может показаться «заезженной», но вдруг кому-нибудь пригодится. Как-то копал в сторону Google Speech Recognition и её реализацию в Chrome. И в голову пришла мысль написать простенький скрипт для постинга в твиттер голосом. Распознование конечно не особо — но такие фразы как «уехал за грибами» или «отошёл» — воспринимает вполне адекватно. Дома — ОС Ubuntu -потому для deb-подобных систем — всё будет описано.

Здравствуй, Уважаемый $USERNAME.

Небольшое введение

В данной статье я хотел бы рассказать вам о распознавании голоса, написанном на таком языке программирования как Bash. В качестве OC я выбрал Ubuntu 12.04

Ближе к теме

Распознавание голоса будет осуществляться сервисом Google, который используется в браузере Google Chrome для голосового поиска. Приступим?

^Assorium

На Хабре публиковалось несколько статей с алгоритмами и скриптами для выбора доминирующих цветов на изображении: 1, 2, 3. В комментариях к тем статьям можно найти ссылки ещё на десяток подобных программ и сервисов. Но нет предела совершенству — и почему бы не рассмотреть способ, который кажется самым оптимальным? Речь идёт об использовании кластеризации методом k-средних (k-means).

Активные модели внешнего вида (Active Appearance Models, AAM) — это статистические модели изображений, которые путем разного рода деформаций могут быть подогнаны под реальное изображение. Данный тип моделей в двумерном варианте был предложен Тимом Кутесом и Крисом Тейлором в 1998 году [1]. Первоначально активные модели внешнего вида применялись оценки параметров изображений лиц, но затем они стали активно применяться и в других областях, в частности, в медицине при анализе рентгеновских снимков и изображений, полученных с помощью магнито-резонансной томографии.




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

Об экспериментах с компьютерной голографией писалось неоднократно. [1, 2, 3] Мне эта тема просто любопытна. Я как-то экспериментировал с бит-реверсивной перестановкой (bit-reversal permutation) изображений и случайно обнаружил голографические свойства. Но обо всем по порядку.

Можешь выбрать подходящую к заголовку поста картинку?

Тогда научи робота! Он тоже хочет.

Команда проекта Открытый корпус просит хабралюдей помочь разметить свободно доступный (CC-BY-SA) корпус текстов. Под катом мы расскажем о том, что такое корпус, зачем он нужен, как обстоят дела с корпусами в России и за рубежом, почему так плохо и какой у нас план.

Многие современные алгоритмы компьютерного зрения строятся на основе детектирования и сопоставления особых точек визуальных образов. По этой теме было написано немало статей на хабре(например SURF, SIFT). Но в большинстве работ не уделяется должного вниманию такому важному этапу, как фильтрация ложных соответствий между изображениями. Чаще всего для этих целей применяют RANSAC-метод и на этом останавливаются. Но это не единственный подход для решения данной задачи.
Данная статья посвящена одному из альтернативных способов фильтрации ложных соответствий.

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

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

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

Алгоритм Particle Filter замечателен своей простотой и интуитивной понятностью. Предлагаю собственный вариант его использования в задаче стереоскопического зрения для сопоставления «одной и той же точки» на двух изображениях — с левой и правой камеры. Для реализации (исключительно в целях развлечения) использован Python с библиотеками numpy (матричные вычисления) и pygame (графика и обработка событий мышки). Сам алгоритм Particle Filter без изменений взят из курса Programming a Robotic Car на Udacity. Меня извиняет лишь то, что я честно прослушал весь курс и сделал все домашние работы, включая и реализацию этого алгоритма.

В задаче стереоскопического зрения нужно сопоставлять малые области (например, 8х8 пикселей) на левом и правом кадре. При идеальном расположении камер строго горизонтально, зная разность координаты по оси Х одинаковой области между левым и правым кадром, можно вычислить расстояние до объекта, который изображен в этой области. Понимаю, что звучит запутанно, но на самом деле это легко выводится простейшими геометрическими построениями по правилу подобных треугольников. Например, на видео с недостроенной колокольней, мы видим уходящий вдаль забор с одинаковыми ромбами. Ближний к нам ромб наиболее сильно смещен на правом кадре относительно левого, следующий — чуть меньше и т.д.

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



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

Обнаружение пешеходов используется главным образом в исследованиях, посвященных беспилотным автомобилям. Общая цель обнаружения пешеходов — предотвращение столкновения автомобиля с человеком. На Хабре недавно был топик про «умные машины». Создание подобных систем очень популярное направление исследований (Darpa challenge). Я занимаюсь распознаванием пешеходов для подобного проекта интеллектуальных автомобилей. Очевидно, что проблема обнаружения пешеходов — программная, а предотвращение столкновения — аппаратная. В данной статье я упомяну лишь о программной части, кратко расскажу об одном способе обнаружения людей на изображении и алгоритме классификации.

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

Amazon Glacier

Вкратце — Amazon Glacier — это сервис с очень привлекательной ценой сторейджа, созданный для хранения архивов/бэкапов. Но процесс восстановления архивов довольно сложный и/или дорогой. Впрочем, сервис вполне пригоден для secondary backup.
Подробнее про Glacier уже писали на хабре.

О чём пост

Хочу поделиться Open Source клиентом на Perl для синхронизации локальной директории с сервисом Glacier, также расказать о некоторых ньюансах работы с glacier и описать workflow его работы.

Многие из Вас наверняка читали в далеком 2007-ом, увлекательную статью пользователя ACiD — The Scene — настоящий андеграунд Интернета, и судя по комментариям, некоторые даже посмотрели указанный в статье сериал The Scene в оригинале. Для тех кто не вкурсе, или забыл, немного информации.

Сцена — веб-сериал, созданный Jun Group Entertainment в 2004-2006гг. Первый в своем роде фильме действие которого происходит на экране компьютеров его героев, где мы видим, как они общаются в чате.

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

Недавно я наткнулся на этот сериал на рутрекере, подумав что его перевели с субтитрами или голосом как множество других шоу. Но все оказалось намного интересней: Пользователю под ником ID-Daemon ценой невероятных усилий за полгода, удалось практически вручную отрисовать первую серию. На данный момент полностью русифицировано 12 из 20 серий первого из двух сезонов.

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



Под катом ссылки на раздачи, Рецензия, Саундтрек, а также полная история пользователя ID-Daemon связанная с этим сериалом, которой он сопровождает свои релизы, в попытках популяризовать это не стандартное для обычных людей шоу и получить право публикации сериала в разделе Сериалы. На данный момент шоу расположено в ветке Rutracker.org » Разное » Разное » Видео

Широко известны сайты для решения олимпиадных задач по программированию, такие, как, например, TopCoder и Codeforces, а также сборники математических задач-головоломок, например, Project Euler. За последний год произошёл бум онлайн образования: возникли стартапы Coursera и Udacity, предоставляющие онлайн курсы от топовых университетов США… но для тех, кто хочет изучить биоинформатику, пока ничего нет.

Розалинд — проект, разрабатываемый в Санкт-Петербуге и University of California, San Diego с мая 2012 года, как раз заполняет эту нишу. Это платформа для обучения биоинформатике с помощью решения задач, бесплатная и открытая.

Пару месяцев назад я рассказывал о приближенных результатах в задаче о сворачивании РНК. Напомню требуется свернуть вироидный рибозим NC_003540 организма Chrysanthemum chlorotic mottle viroid, третичная структура которого неизвестна.

И вот оно свершилось — рибозим свернулся ! (В нем образованы все имеющиеся водородные связи)

Смотрим его конечное состояние, а под катом еще его траекторию сворачивания, а также подводим итоги.

Продолжим серию статей «ИИ для чайников». Если в прошлой статье мы попробовали отграничить людей, решающих задачи «оракулов сильного ИИ» от задач «слабого ИИ», и показать решение какого рода задач дает больше, чем лирические «откровения». Одну из таких задач мы назвали «задача двух учителей».

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

Sentiment analysis (по-русски, анализ тональности) — это область компьютерной лингвистики, которая занимается изучением мнений и эмоций в текстовых документах. Недавно на хабре появилась статья про использование машинного обучения для анализа тональности, однако, она была настолько плохо составлена, что я решил написать свою версию. Итак, в этой статье я постараюсь доступно объяснить, что такое анализ тональности, и как реализовать подобную систему для русского языка.