How to become an author

Vladimir Yuzhikov @YUVladimir

Пользователь

ProfileArticles6PostsNewsComments354

sic Mar 13 2013 at 19:04

Построение системы оптического распознавания структурной информации на примере Imago OCR

19 min

37K

Open source*Algorithms*Image processing*

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

Читать дальше →

+64

antisies Mar 12 2013 at 16:32

Распознавание пола в изображениях и видео

8 min

52K

Algorithms*Image processing*

В данной статье представлен алгоритм распознавания пола, обладающий точностью 93.1% [1]. Статья не требует каких-либо предварительных знаний в области обработки изображений или машинного обучения. После прочтения статьи читатель будет в состоянии выполнить рассмотренный алгоритм самостоятельно.

Читать дальше →

+90

Airstrike Feb 24 2013 at 18:59

Попытка перевода и озвучки видео в домашних условиях

4 min

139K

Working with video*

Каждый уважающий себя советский мальчишка должен был: знать, где найти карбид; быть влюблен в Алису Селезневу; хотеть стать космонавтом. Я в этом плане не исключение и, так сказать, полностью соответствовал. Со временем многое изменилось, но интерес к космосу остался. С января 2004 года я в течение полутора лет практически ежедневно заходил на специальную страничку НАСА и смотрел, что нового произошло с марсоходами. Так что документальный фильм «Смерть марсохода» (Death of a Mars Rover) был изначально обречен на ошеломительный успех среди меня.

К сожалению, единственная из существующих до недавнего времени озвучек этого фильма была… как бы это сказать… «не на твердую пятерку». Мне-то, в принципе, все равно — я могу и на английском посмотреть — но за ~~державу~~ других зрителей было обидно. Поэтому я решил самостоятельно перевести и озвучить этот интереснейший фильм с помощью подручных средств. Внести, так сказать, посильный вклад в дело распространения знаний среди населения. Думал, управлюсь быстро — всего-то 45 минут освоить! Но процесс занял гораздо больше времени — многословное, на грани логореи, описание подробностей читайте под катом.

"

Читать дальше →

+154

silvansky Mar 1 2013 at 09:05

19 команд ffmpeg для любых нужд

3 min

583K

Working with video*Sound

Tutorial

Translation

От переводчика:
Многие знают, что ffmpeg — это сила, но не все знают, какая именно. Он многогранен и безграничен, а его man объёмен и местами малопонятен, лишь немногие постигли дао профессиональной работы с ним. И тем не менее, этот инструмент может быть полезен почти всем, кто хоть иногда работает с видео и звуком, даже на бытовом уровне. О некоторых полезных консольных командах ffmpeg и пойдёт речь в статье. В некоторых местах я взял на себя смелость вставить ссылки на поясняющие статьи.

ffmpeg — это кроссплатформенная open-source библиотека для обработки видео- и аудиофайлов. Я собрал 19 полезных и удивительных команд, покрывающих почти все нужды: конвертация видео, извлечение звуковой дорожки, конвертирование для iPod или PSP, и многое другое.

1. Получение информации о видеофайле

ffmpeg -i video.avi

2. Превратить набор картинок в видео

ffmpeg -f image2 -i image%d.jpg video.mpg

Эта команда преобразует все картинки из текущей директории (названные image1.jpg, image2.jpg и т.д.) в видеофайл video.mpg

(примечание переводчика: мне больше нравится такой формат:

ffmpeg -r 12 -y -i "image_%010d.png" output.mpg

здесь задаётся frame rate (12) для видео, формат «image_%010d.png» означает, что картинки будут искаться в виде image_0000000001.png, image_0000000002.png и тд, то есть, в формате printf)

Читать дальше →

+206

khdavid Feb 19 2013 at 17:25

Фильтр Калмана

10 min

456K

Algorithms*Mathematics*

Tutorial

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

Читать дальше →

+168

Coderik Feb 17 2013 at 23:17

Вычисление оптического потока методом Лукаса-Канаде. Теория

7 min

58K

Algorithms*Image processing*

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

Если мы хотим узнать на сколько тот или иной объект объект сместился по отношению к его же положению на предыдущем кадре за то время, которое прошло между фиксацией кадров, то скорее всего в первую очередь мы вспомним про оптический поток (optical flow). Для нахождения оптического потока можно смело воспользоваться готовой протестированной и оптимизированной реализацией одного из алгоритмов, например, из библиотеки OpenCV. При этом, однако, очень невредно разбираться в теории, поэтому я предлагаю всем заинтересованным заглянуть внутрь одного из популярных и хорошо изученных методов. В этой статье нет кода и практических советов, зато есть формулы и некоторое количество математических выводов.

Читать дальше →

+107

sergiienko Jan 23 2013 at 10:17

Регулярные выражения изнутри

5 min

125K

Programming*Regular expressions*

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

Команда grep операционной системы Unix или аналогичные команды для поиска цепочек, которые можно встретить в Web-броузерах или системах форматирования текста. В таких системах РВ используются для описания шаблонов, которые пользователь ищет в файле. Различные поисковые системы преобразуют РВ либо в детерминированный конечный автомат (ДКА), либо недетерминированный конечный автомат (НКА) и применяют этот автомат к файлу, в котором производится поиск.
Генераторы лексических анализаторов. Лексические анализаторы являются компонентом компилятора, они разбивают исходную программу на логические единицы (лексемы), которые могут состоять из одного или нескольких символов и имеют определенный смысл. Генератор лексических анализаторов получает формальные описания лексем, являющиеся по существу РВ, и создает ДКА, который распознает, какая из лексем появляется на его входе.
РВ в языках программирования.

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

Читать дальше →

+61

masai Feb 10 2013 at 15:51

Вейвлет-сжатие «на пальцах»

10 min

180K

Image processing*

Tutorial

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

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

Читать дальше →

+167

alizar Feb 8 2013 at 06:58

Головоломка Mercator для знатоков географии

1 min

72K

Vector graphics*

В этот пятничный день компания Google выпустила географический паззл Mercator в качестве примера использования Google Maps API. Нужно положить кусочки суши в соответствующие места на карте, учитывая развёртку сферы на плоскость — проекцию Меркатора. Как известно, в такой проекции масштаб на карте не является постоянным, а увеличивается от экватора к полюсам как обратный косинус широты. Соответствующим образом пересчитываются SVG для каждого элемента паззла.

+77

tomshinsky Feb 4 2013 at 14:15

Идеальное письмо инвестору

2 min

35K

Translation

Перевод статьи Дэвида Коэна: культовая личность, основатель и директор TechStars (одного из лучших американских стартап-акселераторов), венчурный инвестор. Рассказывает о самом «правильном» письме, которое он когда-либо получал от стартапера, ищущего совет и деньги. На злобу дня российским стартаперам.

Как вы догадываетесь, я получаю кучу писем. При прошлой проверке их было более 500 в день и из них – 50 от людей, которых я не знаю. Они часто просят совета или хотят, чтобы я обратил внимание на их стартап с целью инвестирования. И это нормально, я стараюсь отвечать на все. Но однажды я получил очень отличное письмо. Оно не звучало как “холодный звонок”, оно было тщательно продуманным и очень релевантным. И вот его содержание:

Читать дальше →

+31

vtenity Feb 5 2013 at 11:57

Видео лекций всего курса первой Школы разработки интерфейсов Яндекса

2 min

179K

Яндекс corporate blogWebsite development*

Tutorial

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

За долгое время работы в Яндексе нам удалось систематизировать все наши знания и огромный опыт в создании фронтенда веб-сервисов. Результатом этого осмысления и длительной работы стала первая Школа разработки интерфейсов, занятие которой шли в московском офисе Яндекса. Вся практическая часть обучения проходила в реальных проектах Яндекса. Теоретическая же состояла из лекций, которые читали ведущие разработчики интерфейсов Яндекса: Сергей veged Бережной, Михаил mishanga Трошев, Алексей doochik Андросов, Михаил azproduction Давыдов и другие.

Выпускники первой Школы разработки интерфейсов Яндекса

Выпускники первой Школы разработки интерфейсов Яндекса

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

Читать дальше →

+146

Sirion Jan 25 2013 at 09:10

Ломаем спички, или Алиса в стране математических ошибок

5 min

77K

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

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

Я довольно быстро доказал, что вероятность этого события равна нулю. Гордый собой, я запостил решение и ответ, ожидая плюсика в карму. Оказалось, однако, что авторский ответ совсем другой: 1 — 1/e. Забегая вперёд, скажу, что этот ответ неверен.

Неправильные авторские решения — довольно частое явление в интернет-головоломках. И я ни за что не стал бы писать этот пост, если бы автором задачи, а также её неверного решения, не был британский логик и алгебраист Чарльз Л. Доджсон, более известный под псевдонимом Льюис Кэрролл.

Скандалы, интриги, расследования

+207

Majestic12 Jan 15 2013 at 17:52

Пускаем пыль в глаза или как получить больше заказов на разработку

6 min

64K

Website development*

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

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

Читать дальше →

+85

lipskiy Jan 13 2013 at 20:00

Светодиодная лента в качестве освещения комнаты

15 min

1.3M

Изначально для основного освещения одной из комнат, где шёл капитальный ремонт, планировалась обычная люстра. Но недавно мне на глаза попалась суперяркая светодиодная лента Ultra 5000 со светодиодами smd 5630 торговой марки Arlight. Решение было принято быстро, окончательно и бесповоротно — хочу такую ленту в качестве основного света в комнате.

О реализации светодиодного периметра освещения далее

+410

apangin Jan 14 2013 at 09:08

Откуда растут ноги у hashCode

2 min

90K

Опять на собеседованиях по Java спрашивают про hashCode и equals? А кто из собеседующих сам ответит на вопрос, как вычисляется Object.hashCode() и System.identityHashCode()? Насколько дорог вызов этих методов? Как их можно ускорить в HotSpot JVM? Держу пари, едва ли кто даст правильный ответ. Разве что, кто прочитает эту статью.

Читать дальше →

+89

yruslan Feb 1 2011 at 11:27

Что нужно знать про арифметику с плавающей запятой

14 min

1M

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

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

Читать дальше →

+238

Andre_487 Jan 10 2013 at 23:15

Простая программа на ассемблере x86: Решето Эратосфена

9 min

131K

Tutorial

Вступительное слово

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

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

До ее написания я сформулировал такие требования к будущей программе:

Моя программа не должна быть программой под DOS. Слишком много примеров ориентировано на нее в связи с простым API. Моя программа обязательно должна была запускаться на современных ОС.
Программа должна использовать кучу – получать в свое распоряжение динамически распределяемую память.
Чтобы не быть слишком сложной, программа должна работать с целыми беззнаковыми числами без использования переносов.

Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал nasm.

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

Итак, посмотрим, что получилось.

Читать дальше →

+33

aamuvirkku Jan 8 2013 at 12:11

Что сложного может быть в вычислении гипотенузы?

2 min

48K

Programming*Algorithms*

Tutorial

Translation

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

На первый взгляд это может показаться тривиальной задачей, не так ли? Если сторонами треугольника являются x и y, то, формально, формулой для вычисления гипотенузы будет:

sqrt(x*x + y*y)

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

Читать дальше →

+112

amarao Feb 18 2011 at 23:03

TOP'ай сюда

5 min

184K

Configuring Linux*

Обзор практически всех *top утилит под linux (atop, iotop, htop, foobartop и т.д.).

top

Все мы знаем top — самую простую и самую распространённую утилиту из этого списка. Показывает примерно то же, что утилита vmstat, плюс рейтинг процессов по потреблению памяти или процессора. Совсем ничего не знает про загрузку сети или дисков. Позволяет минимальный набор операций с процессом: renice, kill (в смысле отправки сигнала, убийство — частный случай). По имени top суффикс "-top" получили и все остальные подобные утилиты в этом обзоре.

atop

Atop имеет два режима работы — сбор статистики и наблюдение за системой в реальном времени. В режиме сбора статистики atop запускается как демон и раз в N времени (обычно 10 мин) скидывает состояние в двоичный журнал. Потом по этому журналу atop'ом же (ключ -r и имя лог-файла) можно бегать вперёд-назад кнопками T и t, наблюдая показания atop'а с усреднением за 10 минут в любой интересный момент времени.

В отличие от top отлично знает про существование блочных устройств и сетевых интерфейса, способен показывать их загрузку в процентах (на 10G, правда, процентов не получается, но хотя бы показывается количество мегабит).

Незаменимое средство для поиска источников лагов на сервере, так как сохраняет не только статистику загрузки системы, но и показатели каждого процесса — то есть «долистав» до нужного момента времени можно увидеть, кто этот счастливый момент с LA > 30 создал. И что именно было причиной — IO программ, своп (нехватка памяти), процесор или что-то ещё. Помимо большего количества информации ещё способен двумя цветами подсказывать, какие параметры выходят за разумные пределы.

Читать дальше →

+377

Sammarize May 10 2010 at 09:44

Алгоритмы поиска старшего бита

3 min

40K

Здесь я хочу рассказать и обсудить несколько алгоритмов для нахождения старшего единичного бита числа.

На всякий случай, поясню: старшим битом называется единичный бит числа, отвечающий за самую большую степень двойки. Иными словами, это самая большая степень двойки, не превосходящая числа. Чтобы избежать многих случаев, будем здесь считать, что мы имеем дело с натуральным числом в пределах от 1 до 2^31 — 1 включительно. Кроме того, чтобы не слишком углубляться в теорию вероятности, будем считать, что число, в котором требуется определить старший бит, с одинаковой вероятностью будет любым из возможных чисел.

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

int bit1(int x) {
   int t = 1 << 30;
   while (x < t) t >>= 1;
   return t;
}

Читать дальше →

+37

1 2 ...

12

13 14 ...