Oct 11

Что почитать начинающему программисту

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

Будет актуально для linux/windows системных и прикладных разработчиков. Если вы прочитаете и сможете пользоваться этим знанием – 85% процентов вакансий уровня middle (ну и junior) – ваши.

1st programming bookЯ тоже перфекционист. Но даже мне кажутся изрядно раздутыми общедоступные списки книг для начинающих программистов. Причем некоторые книги в этих списках, новичкам, по моему мнению, просто противопоказаны. Ну нельзя подавляющему большинству нормальных людей путь в с++ начинать со Страуструпа. Можно сколько угодно ломать копья, обсуждая фундаментальные труды Кнута, но такое чтиво, особенно если университетский курс вышки подзабыт, быстро вгоняет в уныние, навевая мысли о проф. непригодности. К таким суровым упражнением будет милосерднее подходить спустя пару лет разминки в боевых условиях. Когда по граблям проторены тропы и начинает формироваться опасная иллюзия, что мол который год уже программирую – чем это меня тут еще удивить можно? Computer science?! Не, не слышал.

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

Да, программирование это наука. Да, программирование – это математика (в явном или не очень виде). И всему этому учиться не переучиться. Но не все же сразу. А вот начинать я бы предложил в таком порядке:

Язык C – основа основ:

Язык программирования C - Керниган, Ритчи

Язык программирования C – Брайан Керниган, Деннис Ритчи
(C Programming Language by Brian W. Kernighan, Dennis M. Ritchie )

SQL – ну куда сейчас без баз данных:

SQL - запросы для простых смертных. Хернандес, Вьескас

SQL – запросы для простых смертных. Практическое руководство по манипулированию данными в SQL Майкл Дж. Хернандес, Джон Л. Вьескас
(SQL Queries for Mere Mortals: A Hands-On Guide to Data Manipulation in SQL by John L. Viescas, Michael J. Hernandez)

C++ – противоречивый, не простой и всемогущий 🙂

C++ за 21 день, Либерти

Джон Либерти Освой самостоятельно C++ за 21 день – прекрасная вводная книга в мир ужасных крестов
(Teach Yourself C++ in 21 Days – Jesse Liberty, Bradley L. Jones)

Линуксы – ОС кроме Windows?

Операционная система UNIX Робачевский, Немнюгин, Стесик

Операционная система UNIX Андрей Робачевский, Сергей Немнюгин, Ольга Стесик

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

У. Ричард Стивенс, Стивен А. Раго: “UNIX. Профессиональное программирование”
Рихтер Джеффри “Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows” (не смотря на то, что сейчас миром десктопных приложений правят C# и Java, именно в этих книгах детально изложена информация об особенностях программирования под конкретную ОС)

Функциональное программирование – это уже сильно опционально, для постепенной подготовки организма к просвещению и философскому подходу к программированию. (Они хоть и на английском зато с доходчивыми картинками и объяснениями концепций буквально “на пальцах”).

The Little Schemer - Daniel P. Friedman Matthias Felleisen

The Little Schemer – Daniel P. Friedman Matthias Felleisen

The Seasoned Schemer - Daniel P. Friedman Matthias Felleisen

The Seasoned Schemer – Daniel P. Friedman Matthias Felleisen

Land of Lisp, Conrad Barski

Land of Lisp: Learn to Program in Lisp, One Game at a Time! – Conrad Barski

Jun 28

GPU-оптимизация – прописные истины

[pullquote align=”left|center|right” textalign=”left|center|right” width=”30%”]Ядер много не бывает…[/pullquote]

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

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

Причины по которой GPU эффективны для работы с большими объемами данных, требующих обработки:

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

Пропускная способность памяти (memory bandwidth) – это сколько информации – бит или гигабайт – может может быть передано за единицу времени секунду или процессорный такт.

Одна из задач оптимизации – задействовать по максимуму пропускную способность – увеличить показатели throughput (в идеале она должна быть равна memory bandwidth).

Для улучшения использования пропускной способности:

  • увеличить объем информации – использовать пропускной канал на полную (например каждый поток работает с флоат4)
  • уменьшать латентность – задержку между операциями

Задержка (latency) – промежуток времени между моментами, когда контролер запросил конкретную
ячейку памяти и тем моментом, когда данные стали доступны процессору для выполнения инструкций.
На саму задержку мы никак повлиять не можем – эти ограничения присутствуют на аппаратном уровне.
Именно за счет этой задержки процессор может одновременно обслуживать несколько потоков –
пока поток А запросил выделить ему памяти, поток Б может что-то посчитать, а поток С ждать пока к нему придут запрошенные данные.

Как снизить задержку (latency) если используется синхронизация:

  • уменьшить число потоков в блоке
  • увеличить число групп-блоков

Использование ресурсов GPU на полную – GPU Occupancy

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

Вычислительные мощности GPU – это сотни процессоров жадных до вычислений, при создании программы – ядра (kernel) – на плечи программиста ложиться бремя распределения нагрузки на них. Ошибка может привести к тому, что большая часть этих драгоценных ресурсов может бесцельно простаивать. Сейчас я объясню почему. Начать придется издалека.

Напомню, что варп (warp в терминологии NVidia, wavefront – в терминологии AMD) – набор потоков которые одновременно выполняют одну и туже функцию-кернел на процессоре. Потоки, объединенные программистом в блоки разбиваются на варпы планировщиком потоков (отдельно для каждого мультипроцессора) – пока один варп работает, второй ждет обработки запросов к памяти и т.д. Если какие-то из потоков варпа все еще выполняют вычисления, а другие уже сделали все что могли – имеет место быть неэффективное использование вычислительного ресурса – в народе именуемое простаивание мощностей.

Каждая точка синхронизации, каждое ветвление логики может породить такую ситуацию простоя.  Максимальная дивергенция (ветвление логики исполнения) зависит от размера варпа. Для GPU от NVidia – это 32, для AMD – 64.

Для того чтобы снизить простой мультипроцессора во время выполнения варпа:

  • минимизировать время ожидания барьеров
  • минимизировать расхождение логики выполнения в функции-кернеле

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

ядро запускается с блоками размерностью 64x16, потоки разбиваются по варпам в порядке X, Y, Z - т.е. первые 64 элемента разбиваются на два варпа, потом вторые и т.д.

ядро запускается с блоками размерностью 64×16, потоки разбиваются по варпам в порядке X, Y, Z – т.е. первые 64 элемента разбиваются на два варпа, потом вторые и т.д.

Ядро запускается с блоками размерностью 16x64. В первый варп добавляются первые и вторые 16 элементов, во второй варп - третьи и четвертые и т.д.

Ядро запускается с блоками размерностью 16×64. В первый варп добавляются первые и вторые 16 элементов, во второй варп – третьи и четвертые и т.д.

более подробно про это можно почитать тут:
http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#thread-hierarchy

Как снижать дивергенцию (помните – ветвление – не всегда причина критичной потери производительности)

  • когда у смежных потоков разные пути исполнения – много условий и переходов по ним – искать пути ре-структуризации
  • искать не сбалансированную загрузку потоков и решительно ее удалять (это когда у нас мало того что есть условия, дак еще из-за этих условиях первый поток всегда что-то вычисляет, а пятый в это условие не попадает и простаивает)

Как использовать ресурсы GPU по максимуму

Ресурсы GPU, к сожалению, тоже имеют свои ограничения. И, строго говоря, перед запуском функции-кернела имеет смысл определить лимиты и при распределении нагрузки эти лимиты учесть. Почему это важно?

У видеокарт есть ограничения на общее число потоков, которое может выполнять один мультипроцессор, максимальное число потоков в одном блоке, максимальное число варпов на одном процессоре, ограничения на различные виды памяти и т.п. Всю эту информацию можно запросить как програмно, через соответствующее API так и предварительно с помощью утилит из SDK. (Модули deviceQuery для устройств NVidia, CLInfo – для видеокарт AMD).

Общая практика:

  • число блоков/рабочих групп потоков должно быть кратно количеству потоковых процессоров
  • размер блока/рабочей группы должые быть кратен размеру варпа

При этом следует учитывать что абсолютный минимум – 3-4 варпа/вейфронта крутятся одновременно на каждом процессоре, мудрые гайды советуют исходить из соображения – не меньше семи вейфронатов. При этом – не забывать ограничения по железу!

В голове все эти детали держать быстро надоедает, потому для расчет gpu-occupancy NVidia предложила неожиданный инструмент – эксельный(!) калькулятор набитый макросами. Туда можно ввести информацию по максимальному числу потоков для SM, число регистров и размер общей (shared) памяти доступных на потоковом процессоре, и используемые параметры запуска функций – а он выдает в процентах  эффективность использования ресурсов (и вы рвете на голове волосы осознавая что чтобы задействовать все ядра вам не хватает регистров).

сам кальулятор:
http://developer.download.nvidia.com/compute/cuda/CUDA_Occupancy_calculator.xls

информация по использованию:
http://docs.nvidia.com/cuda/cuda-c-best-practices-guide/#calculating-occupancy

GPU и операции с памятью

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

Проблема обстоит в следующем – каждый запрос возвращает в ответ кусочек данных размером кратный 128 битам. А каждый поток использует лишь четверть его (в случае обычной четырех-байтовой переменной). Когда смежные потоки одновременно работают с данными расположенными последовательно в ячейках памяти – это снижает общее число обращений к памяти. Называется это явление – объединенные операции чтения и записи (coalesced access – good! both read and write) – и при верной организации кода (strided access to contiguous chunk of memory – bad!) может ощутимо улучшить производительность. При организации своего ядра – помните – смежный доступ – в пределах элементов одной строки памяти, работа с элементами столбца – это уже не так эффективно. Хотите больше деталей? мне понравилась вот эта pdf –  или гуглите на предмет “memory coalescing techniques“.

Лидирующие позиции в номинации “узкое место” занимает другая операция с памятью – копирование данных из памяти хоста в гпу. Копирование происходит не абы как, а из специально выделенной драйвером и системой области памяти: при запросе на копирование данных – система сначала копирует туда эти данные, а уже потом заливает их в GPU. Скорость транспортировки данных ограничена пропускной способностью шины PCI Express xN (где N число линий передачи данных) через которые современные видеокарты общаются с хостом.

Однако, лишнее копирование медленной памяти на хосте – это порою неоправданные издержки. Выход – использовать так называемую pinned memory – специальным образом помеченную область памяти, так что операционная система не имеет возможности выполнять с ней какие либо операции (например – выгрузить в свап/переместить по своему усмотрению и т.п.). Передача данных с хоста на видеокарту осуществляется без участия операционной системы – асинхронно, через DMA (direct memory access).

И, на последок, еще немного про память. Разделяемая память на мультипроцессоре обычно организована в виде банков памяти содержащих 32 битные слова – данные. Число банков по доброй традиции варьируется от одного поколения GPU к другому – 16/32 Если каждый поток обращается за данными в отдельный банк – все хорошо. Иначе получается несколько запросов на чтение/запись к одному банку и мы получаем – конфликт (shared memory bank conflict). Такие конфликтные обращения сериализуются и соответственно выполняются последовательно, а не параллельно. Если к одному банку обращаются все потоки – используется “широковещательный” ответ (broadcast) и конфликта нет. Существует несколько способов эффективно бороться с конфликтами доступа, мне понравилось описание основных методик по избавлению от конфликтов доступа к банкам памяти – тут.

Как сделать математические операции еще быстрее? Помнить что:

  • вычисления двойной точности – это высокая нагрузка операции с fp64 >> fp32
  • константы вида 3.13 в коде, по умолчанию, интерпретируется как fp64 если явно не указывать 3.14f
  • для оптимизации математики не лишним будет справиться в гайдах – а нет ли каких флажков у компилятора
  • производители включают в свои SDK функции, которые используют особенности устройств для достижения производительности (часто – в ущерб переносимости)

Для разработчиков CUDA имеет смысл обратить пристальное внимание на концепцию cuda stream,  позволяющих запускать сразу несколько функций-ядер на одному устройстве или совмещать асинхронное копирование данных с хоста на устройство во время выполнения функций. OpenCL, пока, такого функционала не предоставляет 🙁

Утиль для профилирования:

NVifia Visual Profiler
AMD CodeXL (бывший Amd APP Profiler)

Средства для дебугинга:
gDEBugger – http://www.gremedy.com/
CUDA-gdb – https://developer.nvidia.com/cuda-gdb

И отдельно хочу отметить функционал AMD APP KernelAnalyzer – статического анализатора кода (не требует наличия GPU в системе, умеет компилировать/разбирать собранные ядра для различных архитектур GPU от AMD). Сейчас входит в состав очередной системы для разработки все-в-одном – AMD CodeXL.
CUDA-MEMCHECK – анализатор от NVidia, призванный обеспечить функционал одноименного расширения для valgrind в мире CUDA-приложений.
http://multicore.doc.ic.ac.uk/tools/GPUVerify/ – интересная утилитка, анализирует ядра как CUDA так и OpenCL.

P. S. В качестве более пространного руководства по оптимизации, могу порекомендовать гуглить всевозможные best practices guide для OpenCL и CUDA.

Jun 16

Введение в GPU-вычисления – CUDA/OpenCL

Введение в GPU-вычисления

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

В этой заметке собрана информация которая поможет понять общие принципы GPU-программирования.

Введение в архитектуру GPU

Разделяют два вида устройств – то которое управляет общей логикой – host, и то которое умеет быстро выполнить некоторый набор инструкций над большим объемом данных – device.
Архитектура GPU

В роли хоста обычно выступает центральный процессор (CPU – например i5/i7).
В роли вычислительного устройства – видеокарта (GPU – GTX690/HD7970). Видеокарта содержит Compute Units – процессорные ядра. Неразбериху вводят и производители NVidia называет свои Streaming Multiprocessor unit или SMX , а
ATI – SIMD Engine или Vector Processor. В современных игровых видеокартах – их 8-32.
Процессорные ядра могут исполнять несколько потоков за счет того, что в каждом содержится несколько (8-16) потоковых процессоров (Stream Cores или Stream Processor). Для карт NVidia – вычисления производятся непосредственно на потоковых процессорах, но ATI ввели еще один уровень абстракции – каждый потоковый процессор, состоит из processing elementsPE (иногда называемых ALU – arithmetic and logic unit) – и вычисления происходят на них.

Необходимо явно подчеркнуть что конкретная архитектура (число всяческих процессоров) и вычислительные возможности варьируются от модели к модели – что несколько влияет на универсальность и простоту кода для видеокарт от обоих производителей.
Для CUDA-устройств от NVidia это sm10, sm20, sm30 и т.д. Для OpenCL видеокарт от ATI/NVidia определяющее значение имеет версия OpenCL реализованная в драйверах от производителя 1.0, 1.1, 1.2 и поддержка особенностей на уровне железа. Да, вы вполне можете столкнуться с ситуацией когда на уровне железа какие-то функции просто не реализованы (как например локальная память на амд-ешных видеокарт линейки HD4800). Да, вы вполне можете столкнуться с ситуацией когда какие-то функции не реализованы в драйверах (на момент написания – выполнение нескольких ядер на видео-картах от NVidia с помощью OpenCL).

Программирование для GPU

Выполнение программы на GPU

Программы пишутся на расширении языка Си от NVidia/OpenCL и компилируются с помощью специальных компиляторов входящих в SDK. У каждого производителя разумеется свой. Есть два варианта сборки – под целевую платформу – когда явно указывается на каком железе будет исполнятся код или в некоторый промежуточный код, который при запуске на целевом железе будет преобразован драйвером в набор конкретных инструкций для используемой архитектуры (с поправкой на вычислительные возможности железа).

Ядро - kernelВыполняемая на GPU программа называется ядром – kernel – что для CUDA что для OpenCL это и будет тот набор инструкций которые применяются ко всем данным. Функция одна, а данные на которых она выполняется – разные – принцип SIMD.

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

Драйвер CUDA/OpenCL разбивает входные данные на множество частей (потоки выполнения объединенные в блоки) и назначает для выполнения на каждый потоковый процессор. Программист может и должен указывать драйверу как максимально эффективно задействовать существующие вычислительные ресурсы, задавая размеры блоков и число потоков в них. Разумеется, максимально допустимые значения варьируются от устройства к устройству. Хорошая практика – перед выполнением запросить параметры железа, на котором будет выполняться ядро и на их основании вычислить оптимальные размеры блоков.

Схематично, распределение задач на GPU происходит так:

Выполнение программы на GPU

Выполнение программы на GPU

work-item (OpenCL)  или thread (CUDA) – ядро и набор данных, выполняется на Stream Processor (Processing Element в случае ATI устройств).
work group (OpenCL) или thread block (CUDA) выполняется на Multi Processor (SIMD Engine)
Grid (набор блоков такое понятие есть только у НВидиа) = выполняется на целом устройстве – GPU. Для выполнения на GPU все потоки объединяются в варпы (warp – CUDA) или вейффронты (wavefront – OpenCL) – пул потоков, назначенных на выполнение на одном отдельном мультипроцессоре. То есть если число блоков или рабочих групп оказалось больше чем число мултипроцессоров – фактически, в каждый момент времени выполняется группа (или группы) объединенные в варп – все остальные ожидают своей очереди.

Одно ядро может выполняться на нескольких GPU устройствах (как для CUDA так и для OpenCL, как для карточек ATI так и для NVidia).
Одно GPU-устройство может одновременно выполнять несколько ядер (как для CUDA так и для OpenCL, для NVidia – начиная с архитектуры 20 и выше). Ссылки по данным вопросам см. в конце статьи.

Модель памяти OpenCL (в скобках – терминология CUDA)

Модель памяти GPU

Здесь главное запомнить про время доступа к каждому виду памяти. Самый медленный это глобальная память – у современных видекарт ее аж до 6 Гб. Далее по скорости идет разделяемая память (shared – CUDA, local – OpenCL) – общая для всех потоков в блоке (thread block – CUDA, work-group – OpenCL) – однако ее всегда мало – 32-48 Кб для мультипроцессора. Самой быстрой является локальная память за счет использования регистров и кеширования, но надо понимать что все что не уместилось в кеши\регистры – будет хранится в глобальной памяти со всеми вытекающими.

Паттерны параллельного программирования для GPU

1. Map

Map - GPU parallel pattern

Map – GPU parallel pattern

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

Отношение – как один к одному (one-to-one).

out[i]=operator(int[i])

пример – перемножение матриц, оператор инкремента или декремента примененный к каждому элементу матрицы и т.п.

2. Scatter

Scatter - GPU parallel pattern

Scatter – GPU parallel pattern

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

out[Loc[i]] = operator(in[i])

Отношение – как один ко многим (one-to-many).

3. Transpose

Transpose - GPU parallel pattern

Transpose – GPU parallel pattern

Данный паттерн можно рассматривать как частный случай паттерна scatter.
Используется для оптимизации вычислений – перераспределяя элементы в памяти можно достичь значительного повышения производительности.

4. Gather

Gather - GPU parallel pattern

Gather – GPU parallel pattern

Является обратным к паттерну Scatter – для каждого элемента в выходном массиве мы вычисляем индексы элементов из входного массива, которые окажут на него влияние:

out[i] = operator(in[Loc[i]])

Отношение – несколько к одному (many-to-one).

5. Stencil

Stencil - GPU parallel pattern

Stencil – GPU parallel pattern

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

Отношение несколько к одному (several-to-one)

Пример:  фильтр  Гауссиана.

6. Reduce

Reduce -  GPU parallel pattern

Reduce – GPU parallel pattern

Отношение все к одному (All-to-one)

Пример – вычисление суммы или максимума в массиве.

7. Scan/ Sort

При вычислении значения в каждой ячейке выходного массива необходимо учитывать значения каждого элемента входного. Существует две основные реализации – Hillis and Steele и Blelloch.

out[i] = F[i] = operator(F[i-1],in[i])

Отношение все ко всем (all-to-all).

Примеры – сортировка данных.

Полезные ссылки

Архитектура GPU – http://www.ixbt.com/video3/rad.shtml

Введение в CUDA:

http://cgm.computergraphics.ru/issues/issue16/cuda

Введение в OpenCL:

http://www.drdobbs.com/parallel/a-gentle-introduction-to-opencl/231002854

http://opencl.codeplex.com/wikipage?title=OpenCL%20Tutorials%20-%201

http://www.fixstars.com/en/opencl/book/OpenCLProgrammingBook/contents/

Хорошие статьи по основам программирования (отдельный интерес вызывает область применения):
http://www.mql5.com/ru/articles/405
http://www.mql5.com/ru/articles/407

Вебинары по OpenCL:

http://developer.amd.com/resources/heterogeneous-computing/opencl-zone/training-events/opencl-programming-webinar-series/

Курс на Udacity по программированию CUDA:

https://www.udacity.com/course/cs344

Выполнение ядра на нескольких GPU:

http://stackoverflow.com/questions/16478968/running-opencl-kernel-on-multiple-gpus
http://www.linkedin.com/groups/Any-new-ideas-on-using-139581.S.97270720
http://www.codeproject.com/Articles/167315/Part-4-Coordinating-Computations-with-OpenCL-Queue

Причем можно пойти по пути упрощения и задействовать один из специальных планировщиков:
http://www.ida.liu.se/~chrke/skepu/
http://aces.snu.ac.kr/Center_for_Manycore_Programming/SnuCL.html
http://runtime.bordeaux.inria.fr/StarPU/

Выполнение нескольких ядер одновременно на одном GPU:
http://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#conurrent-kernel-execution
http://stackoverflow.com/questions/12344223/cuda-understanding-concurrent-kernel-execution
http://stackoverflow.com/questions/9311015/cuda-concurrent-kernel-execution-with-multiple-kernels-per-stream
Для ATI карт упоминаний такой возможности я не нашел. В стандарте OpenCL есть флаг CL_QUEUE_OUT_OF_ORDER_EXEC_MODE_ENABLE но в настоящее время он поддерживается только для CPU.

Серия постов про паттерны параллельного программирования на сайте интела:
http://software.intel.com/en-us/blogs/2009/05/26/parallel-pattern-1-superscalar-sequences-and-task-graphs
http://software.intel.com/en-us/blogs/2009/06/03/parallel-pattern-2-speculative-selection
http://software.intel.com/en-us/blogs/2009/06/10/parallel-patterns-3-map
http://software.intel.com/en-us/blogs/2009/06/24/parallel-pattern-4-gather
http://software.intel.com/en-us/blogs/2009/07/07/parallel-pattern-5-stencils
http://software.intel.com/en-us/blogs/2009/07/14/parallel-pattern-6-partition
http://software.intel.com/en-us/blogs/2009/07/23/parallel-pattern-7-reduce
http://software.intel.com/en-us/blogs/2009/09/15/parallel-pattern-8-scan
http://software.intel.com/en-us/blogs/2009/12/01/parallel-pattern-9-pack
http://software.intel.com/en-us/blogs/2010/06/09/parallel-pattern-10-scatter

CUDA – grid, threads, blocks- раскладываем все по полочкам

http://stackoverflow.com/questions/2392250/understanding-cuda-grid-dimensions-block-dimensions-and-threads-organization-s
http://llpanorama.wordpress.com/2008/06/11/threads-and-blocks-and-grids-oh-my/

доступные в сети ресурсы по CUDA

http://nvlabs.github.io/moderngpu/
https://developer.nvidia.com/content/gpu-gems-part-i-natural-effects
https://developer.nvidia.com/content/gpu-gems-2
https://developer.nvidia.com/content/gpu-gems-3

UPDATE 28.06.2013

http://my-it-notes.com/2013/06/bases-of-gpu-optimisation/ – основы оптимизации программ для GPU

Враперы для взаимодействия с ОпенСЛ:
JOCL – Java bindings for OpenCL (JOCL)
PyOpenCL – для python
aparapi – полноценная библиотека для жавы

для хаскела
http://hackage.haskell.org/package/accelerate
http://hackage.haskell.org/package/hopencl

Интересные статью по OpenCL – тут.

доступные материалы курсов по параллельным вычислениям:

http://www.slac.stanford.edu/~rolfa/cudacourse/

http://www.cs.nyu.edu/courses/fall10/G22.2945-001/lectures.html

https://computing.llnl.gov/tutorials/parallel_comp/

UPDATE 23.11.2013
http://clcc.sourceforge.net/ – компилятор для OpenCL, удобен для проверки используемых в проекте OpenCL ядер. Поддерживает Windows, Mac. Хотя под Mac – для этих целей можно воспользоваться и “родным”, более продвинутым средством – openclc:

/System/Library/Frameworks/OpenCL.framework/Libraries/openclc -x cl -cl-std=CL1.1 -cl-auto-vectorize-enable -emit-gcl matrix_multiplication.cl

данная команда не только проверит ваш код на соответствие стандарту OpenCL, но, заодно, создаст и заготовки клиентского кода (в данном случае файлы matrix_multiplication.cl.h/matrix_multiplication.cl.cpp) для вызова ядра из пользовательского приложения.
https://github.com/petRUShka/vim-opencl – плагин для Vim’а с поддержкой проверки синтаксиса OpenCL

May 03

Практическое введение в компьютерное зрение

как научить компьютер читать

как научить компьютер читать

Компьютерное зрение?!

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

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

На практике, вот это все разом необходимо далеко не всегда, так как зачастую небольшие упрощения позволяют махом отбросить большую часть сложностей (или добавить еще). Однако, для того чтобы осознанно использовать алгоритмы компьютерного зрения для конкретных практических задач – крайне желательно ориентироваться в плюсах-минусах методов и быть в курсе “state of the art” – последних исследований.

компьютерное зрение - сплав многих наук

компьютерное зрение – сплав многих наук

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

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

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

Компьютерное зрение – практическое введение:

01 – изображение в компьютерном зрении
02 – (пред)обработка изображений
03 – features – локальные особенности – за что зацепиться взгляду
04 – поиск преобразования между особыми точками и немного моделирования
05 – машинное обучение для классификации изображений

Использованные материалы

Видео-лекции

на русском:
Видео-лекции спецкурсов ВМК МГУ “Введение в компьютерное зрение” и “Дополнительные главы компьютерного зрения”, за авторством Антона Конушина (Anton Konushin):
http://www.lektorium.tv/course/?id=22847 – первая часть на лекториуме.
http://www.youtube.com/playlist?list=PLbwKcm5vdiSYTm87ntDsYrksE4OfngSzY – все части на ютубе.
все прекрасно смотрится на удвоенной скорости.
http://moodle.graphicon.ru/course/view.php?id=4 – Вспомогательные материалы по курсам.
http://www.slideshare.net/ktoshik – презенташки к лекциям можно найти там.
UPDATE 23.11.2013
http://habrahabr.ru/company/yandex/blog/203136/– лекции Яндекса по компьютерному зрению
https://sites.google.com/site/cvnnsu/materialy-lekcij – материалы спец-курса “Компьютерное зрение” ННГУ им Н.И. Лобачевского

на английском:
Курс “Введения в компьютерное зрение” университета Флориды от профессора Dr. Mubarak Shahтынц. Ооочень разжевано.
Курс “Цифровая обработка изображений” Харагпурского университета (Индия) – детально и математично разжеваны основные методы низкоуровневой обработки – http://freevideolectures.com/Course/2316/Digital-Image-Processing-IIT-Kharagpur
Нейронные сети –
http://nptel.iitm.ac.in/video.php?subjectId=117105084
Математические основы компьютерного зрения на курсере от Prof. Malikтут.
Видео по использованию OpenCV для конкретных задач – http://www.youtube.com/user/18F4550videos

Литература:
Компьютерное зрение Шапиро, Стокман – основательная, относительно современная и единственная, мне известная, годная книга по данной теме на русском.

Фундаментальные труды, доступные для свободного скачивания:

http://szeliski.org/Book/Computer Vision: Algorithms and Applications – Richard Szeliski, Microsoft Research

http://www.computervisionmodels.com/Computer Vision: Models, Learning, and Inference Simon J.D. Prince

http://programmingcomputervision.com/Programming Computer Vision with Python by Jan Erik Solem

_Официально_, доступных для скачивания не видел, но тоже заслуживают внимания:
Digital Image Processing – Rafael C. Gonzalez Richard E. Woods
Computer Vision: A Modern Approach – Forsyth
Introduction to Machine Learning – Alpaydin

Библиотеки содержащие алгоритмы компьютерного зрения

http://opencv.org/ – первое, что приходит на ум в качестве общедоступного инструментария для погружения в предметную область. Часть алгоритмов перенесена на GPU. С учетом наличия готовых рецептов использования (книги на амазоне\в интернетах – Learning OpenCV, Mastering OpenCV) – идеальна для новичков.
http://www.vlfeat.org/ – алгоритмы компьютерного зрения на чистом C, есть интерфейсы для матлаба.
http://www.simplecv.org/ – библиотека на c/c++ построенная поверх OpenCV, основная цель проекта – предоставить упрощенный интерфейс ко всем алгоритмам. Есть готовое пособие для тех, кто совсем не в теме – “Practical Computer Vision with SimpleCV”.
http://intopii.com/ – большущий фреймворк на c++ для машинного обучения и анализа изображений, есть javacript’овый апи.
ViSP – c++ библиотека с алгоритмами компьютерного зрения (преимущественно в области отслеживания-треккинга и наблюдение)
SHARK – Machine learning library – C++ библиотека алгоритмов машинного обучения, выгодно отличается от альтернатив наличием больше нигде не реализованных алгоритмов
OpenVIDIA : Parallel GPU Computer Vision – алгоритмы компьютерного зрения на GPU (CUDA)
http://scikit-learn.org – методы машинного обучения на питоне
http://cs.unc.edu/~ccwu/siftgpu/ – имплементация алгоритма SIFT на gpu.
MATLAB (toolbox + sample) – наверное, самый простой (и затратный) способ попробовать алгоритмы компьютерного зрения:
http://www.mathworks.com/products/image/
http://www.mathworks.com/products/computer-vision/

Материалы по теме:

http://courses.graphicon.ru/ – учебные материалы (на русском) по курсам Обработки изображений и Компьютерного зрения
презентации по библиотеке OpenCV
Курс лекций по компьютерному зрению от курсеры – https://www.coursera.org/course/computervision (на момент публикации не активен)
Запись выступлений с конференции по компьютерному зрению 2012 года Франция

Материалы англоязычных курсов от ведущих вузов по компьютерному зрению:
CSE/EE486 Computer Vision I
CS395T: Visual Recognition
6.870 Grounding Object Recognition and Scene Understanding
(гуглить по этим названиям и искать полезные крупицы знания)
Washington CSE 576 (Graduate Computer Vision)
Trevor Darrell’s CS 280 Computer Vision class at Berkeley
Antonio Torralba’s 6.869 Advances in Computer Vision class at MIT
Michael Black’s CS 143 Introduction to Computer Vision class at Brown
Kristen Grauman’s CS 378 Computer Vision class at UT Austin
Alyosha Efros’ 15-463 Computational Photography
16-721 Learning-Based Methods in Vision classes at Carnegie Mellon
Pascal Fua’s CS-442 Introduction to Computer Vision class at EPFL

http://visionserver.lems.brown.edu/engn2910x/lectures.php – лекции в pdf формате

http://homepages.inf.ed.ac.uk/rbf/CVonline/ – структурированная и необъятная информация по компьютерному зрению

Библиографии по компьютерному зрению:
http://forums.udacity.com/questions/1033058/free-book-computer-vision-models-learning-and-inference
http://www.compvision.ru/wiki/
http://www.computervisiononline.com/books

http://www.cvpapers.com/rr.html – пространный список библиотек, с реализованными методами компьютерного зрения (computer vision algorithm implementation)
http://www.kernel-machines.org/software – список библиотек с алгоритмами машинного обучения, применимых для задач компьютерного зрения

May 03

01 – изображение в компьютерном зрении

Что такое изображение?

пример ортографической проекции

пример ортографической проекции

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

На практике рассматривают два основных вида преобразований:
Перспективная проекция (perspective projection) – вы сами создавали такие проекции с помощью фотоаппарата (об упрощенной модели перспективной проекции часто рассказывают на примере pinhole camera или камеры обскуры
Ортографическая проекция (orthographic projection) – получается, например, с неуправляемых шпионов-беспилотников

Что влияет на формирование изображения?

Свет – где находится источник(и) света, характеристики света.
Камера – где расположена, куда направлена, параметры
Сцена – динамическая или нет, какие отражающие свойства у поверхностей объектов в сцене и т.п.

Хорошее детальное описание процесса формирования изображения может быть найдено много где, например, если на ютубе поискать по строке “Fundamentals of image formation – Computer Vision-Professor Jitendra Malik” – находятся две 15 минутных лекции с картинками и разжевыванием. Как правило, для практических задач принимаются во внимание только параметры камеры, а все остальное списывается на погрешность измерений.

Как изображение “видит” компьютер?

Здесь есть два принципиально разных подхода – дискретный (конечный) набор данных или функция.

1) Бинарное изображение (представлены только два цвета – черный и белый) можно представить в виде числовой матрицы размером n на m. Единички соответствуют черному, а нолики белому цветам. Для представления изображения в градациях серого подойдет такой же двумерный массив, где каждый элемент будет содержать значение интенсивности – от 0 (совсем черный) до 255 (совсем белый). Для цветного изображения – будет уже три таких массива (для каждого из каналов RGB – свой массив). Разрешение изображения – число строк и столбцов. Видео – последовательность таких изображений (30 фреймов в секунду). Каждый пиксель изображения – представление множества точек пространства.

2) Для обработки вышеописанный подход не подходит так как получается медленно и неэффективно. А потому периодически рождались новые методы.

2.0) Можно думать об изображении как о некоторой функции – это может быть значительно удобней для вычислений. Функцию можно разложить с помощью дискретного преобразования Фурье – ДПФ (англ. – DFT, Discrete Fourier Transform). Ускоренный вариант – быстрое преобразование Фурье (англ. – FFT) можно получить за n*lg(n) операций. Зачем? Кратко – для сжатия, подробно – http://psi-logic.shadanakar.org/fft/fft7.htm. Грубо говоря, на выходе мы получим представление нашего сигнала (то бишь изображения) в виде суммы значения производных разных порядков этой функции в этой точке.

представление изображения в виде функции

представление изображения в виде функции

Как правило, сигнал – наше изображение – задан на некотором отрезке возможных значений. Для его представления используется разложение в косинусах с помощью метода – дискретное косинусное преобразование (DCT). На практике, изображение раскладывается на две базисные функции – двумерные синусоиды с разными углами наклона и фазами. Для ускорения разложения используется их декомпозиция на одномерные ДПФ. Используется, например, при сжатии в JPEG.

Так как частичная сумма ряда Фурье будет отличаться от сигнала на резких границах – возникает погрешность – ringing Gibb’s Phenomenon. С которой с переменным успехом борются по сию пору.

Спектр – изображение отражающее зависимость амплитуды от частоты и от направления синусоиды. Если какую-то часть спектра отсечь и выполнить обратное преобразование – получится изображение “отфильтрованное” по тем или иным характеристикам.

Развитие идеи ДКП – Фильтр Габора. Подобные фильтры позволяют находить края заданной ориентации и частоты. Если их объединить в банк фильтров – набор фильтров разного масштаба и ориентации – то можно получить описание локальной текстуры области изображения (в виде вектора признаков) и использовать для анализа.

2.1) пирамида изображений – Пирамида Гауссианmipmap

пример пирамиды изображения

пример пирамиды изображения

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

2.2) пирамида Лапласиана – вариация Пирамиды Гауссиан На каждом уровне хранится не масштабированная копия, а сигнал (данные изображения) определенной частоты. Эффективнее сжатие, прогрессивная передача данных сначала верхние уровни потом уточняем менее частыми данными

2.3) Ориентированные пирамиды. Получаются если к каждому уровню пирамиды Лапласиана применить ориентированный фильтр – например, фильтр Габора. Хранят информацию о структурах разного масштаба – частоты и ориентацию. Используется для синтеза детектора краев произвольной ориентации (а заодно и для синтеза изображений).

2.4) Вейвлет (wavelet – всплекс) разложение – разложение сигнала по набору масштабированных и смещенных версий одной базовой функции. Может оптимально закодировать сигнал одномерной функции – используется в JPEG2000, эффективен для медицинских изображений высокого разрешения\размытых границ – томограмм.

2.5) Популярные в последнее время – разреженные представления (sparse modeling) сигнала – через словарь – состоящий из фрагментов часто встречающихся в изображениях. Основные методы построения изображения по словарю: basic pursuit, matching pursuit, orthogonal matching pursuit, LARS – Lasso. Можно выбрать либо аналитические методы построения словаря – Curvelets, Countourlets, Surflets, Bandelets, Complex Wavelet Transform, Shearlet, Grouplet, Grouped bandelet. Или построить его с помощью одного из пакетных методов – на основе исходных данных. Наряду с методами строящими словарь на основе всех данных, существуют быстрые методы построения словарей с обучением на лету – после добавление нового элемента данных производится обновление словаря (K-SVD, Image Signature Dictionary). Иерархические словари используются для ускорения разложения.

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

Подробно про сжатие изображений – тут.

Библиотеки для построения словарей и работы со словарями есть в свободном доступе:
Sparse modeling software
sparselab.stanford.edu
от Minh N. Doтут
от Michael Eladтут

May 03

02 – (пред)обработка изображений

Обработка изображений

Основная причина обработки изображения – сделать его “лучше” с точки зрения человека. Или компьютера. Этот вот обтекаемый термин – “лучше” – может означать что угодно – контрастнее, четче, скрыть неугодные родинки на лице неудачной фотографии или выделить все границы на изображении.

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

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

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

Какие на практике бывают разновидности брака:

Мона Лиза - когда не лады со светом

Мона Лиза – когда не лады со светом

Проблема – темное или пересвеченное изображение. Решение – повышение контраста (всего изображения целиком или его части) с помощью линейной коррекцией (или робастной линейной коррекцией). В случае неравномерного освещения, как правило достаточно применения метода single scale retinex (SSR) – принцип расписан на хабре – примеры применения там, конечно, своеобразны. Однако лучших результатов помогают добиться методы нелинейной коррекции – гамма коррекция или логарифмическая, Multi-Scale Retinex. Сравнение всех методов коррекции освещения в статье “A Comparison of the Multiscale Retinex With Other Image Enhancement Techniques”.

Мона Лиза - когда на изображении много шума

Мона Лиза – когда на изображении много шума

Проблема – зашумленное изображение. Шум бывает нескольких видов: соль и перец, белый шум – случайные белые пикселы, гауссов – колебания яркости распределяются по нормальному закону). Cамый легкий способ побороть шум – сделать серию кадров и по ним рассчитать среднее изображение. Обычно же, для борьбы с шумом используется линейная фильтрация (альтернативное название – операция свертка или, на английском, convolution with matrix). На практике, это процесс, когда значение каждого пикселя пересчитывается на основе его окрестности – значений соседних пикселей и специальных коэффициентов-весов (т.е. линейной комбинации). Какая конкретно окрестность и какие конкретно коэффициенты – определяет ядро применяемого фильтра. Ядро – это просто числовая матрица с подобранными коэффициентами. Эти коэффициенты называют степенями влияния или “ценностями”, определяющими вес пикселей из рассматриваемой окрестности. Полезно помнить, что сумма коэффициентов ядра должна быть равна 1, для того чтобы не изменялась средняя яркость/интенсивность. Из линейных фильтров наибольшее распространение получил гауссовский, построенный по принципу “взвешенного усреднения”. Как правило, не понятно насколько сильно зашумлено изображение, потому, на основе экспериментов при использовании гауссовского фильтра выбирают радиус в трое больше сигмы – среднеквадратичного отклонения. Однако есть немало и альтернативных методов фильтрации шума, из которых имеет смысл запомнить медианный фильтр, по сравнению с фильтром Гаусса, он не “размывает” изображение. anisotropic diffusion. Первые фильтры – Превитта, Собеля – сейчас практически не используются.

Мона Лиза - все как в тумане - когда не хватает резкости

Мона Лиза – все как в тумане – когда не хватает резкости

Проблема – нерезкое изображение. Общий принцип усиления границ – размыть изображение, вычесть полученный результат из исходного, тем самым получив сильные границы, а потом полученную разницу добавить к исходному. Основные методы: unsharp masking, Лапласиан/Лапласиан гауссиана – детали подробные тут.

Мона Лиза - нарушенный баланс цветов

Мона Лиза – нарушенный баланс цветов

Проблема – неправильные цвета (хорошо известная фотографам проблема баланса белого). Разделяют на интерактивные методы – серые (белые) карточки (более продвинутые – адаптация “Von Kries”). Или вероятностные – модель серого мира – Grayworld или, как вариант, – растяжение контрастности – autolevels.

Какую информацию можно извлечь из изображения?

Вспоминаем, что понаписано в предыдущей статье – изображение это, всего навсего, такая функция от двух переменных. Раз функция, то, при желании, можно искать ее производные. Вектор из частных производных для каждого пикселя – это градиент этого пикселя или его направление (orientation). Для изображения частные производные можно вычислять через разность текущего и соседнего значений пикселей (смачно разжеванные детали – тут). По градиентам всего изображения можно построить гистограмму ориентированных градиентов – histogram of oriented gradients, которая используется повсеместно.

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

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

Границы могут быть образованы совершенно разными условиями – изменениями цвета/текстуры, разрывами поверхностями – когда нормаль резко меняется, вызванными перепадами освещения и тенями. Иногда рассматривают отдельно различные виды моделей границ – step\roof\spike\ramp. Простейший способ определения границ – вычисление производных функций изображения. На практике же используются стандартный кэни – Gradient of Gaussian (Canny) – подробно и наглядно на русском здесь. Как альтернатива – LoG (Laplacian of Gaussian  Marr-Hildreth).

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

May 03

03 – features – локальные особенности – за что зацепиться взгляду

[pullquote align=”left|top” textalign=”center” width=”30%”]Лучше один раз увидеть…[/pullquote]

Local features – локальные особенности

Изображение, бесспорно, представляет собой самое емкое и лаконичное представление большего объема “нефильтрованной” информации. Нефильтрованной, потому как в большинстве случаев, в рамках определенной задачи, нам вполне достаточно некоей “выжимки” данных: есть на изображении объект интереса или нет, где он расположен, каковы его характеристики. Эпическое описание сцены со всеми подробностями, как правило, не является предметом первой необходимости. Да и второй тоже.

features - особые точки

features – особые точки

Особые точки (в разных источниках – features/characteristic points/local feature points/interest point/локальные особенности) – говоря неформально – “хорошо различимые” фрагменты изображения. Это точки (пиксели) с характерной (особой) окрестностью – т.е. отличающиеся своей окрестностью от всех соседних точек. Классический пример локальной особенности – вершина угла (а не какая-то произвольная точка на прямой или на однородном фоне). Описываются вектором признаков вычисляемых на основе интенсивности/градиентов или других характеристик точек окрестности. Используя особые точки можно  анализировать как изображения целиком так и объекты на них. Хорошие характерные точки позволяют справиться с изменением масштаба, ракурса и перекрытиями сцены или объекта.

Локальные особенности – краеугольный камень во многих высокоуровневых алгоритмах компьютерного зрения: отслеживание (tracking) и распознавание (recognition) объектов, 3d-реконструкция и навигация (SLAM и loop-closure). Используя характерные точки можно вычислить сдвиг (disparity) между двумя изображениями, произвести сегментацию на основе сдвига элементов сцены, рассчитать фундаментальную матрицу для калибровки стерео-пары или проиндексировать изображения для поиска.

Какими должны быть локальные особенности?

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

Основные методы поиска локальных особенностей:

Виды преобразований.

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

Простейшим видом преобразования является параллельный перенос (сдвиг):

пример преобразования параллельный перенос

пример преобразования параллельный перенос

Подобие (перенос, масштаб, поворот):.

пример преобразования подобия

пример преобразования подобия

Афинное (дает хорошее приближение искажений претерпеваемых небольшим плоским фрагментом объекта при изменении радиуса):

пример аффинного преобразования

пример аффинного преобразования

Гомография – одна из простых разновидностей проективного преобразования. Это перспективное преобразование плоскости – преобразование между двумя видами одной и той же плоскости или преобразование между видами полученными с повернутой камеры (при общем центре проекций) – съемка со штатива. По сути – преобразование в однородных координатах.

пример преобразования гомография

пример преобразования гомография

Если распределить модели преобразований по возрастанию сложности то получится:

поворот -> масштаб -> афинное.

Особняком стоит афинное изменение яркости (съемка сцены в разных условиях освещения) которое хоть и не геометрическое, но также часто встречается на практике.

Как найти локальные особенности?

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

Первым детектором особенностей был детектор углов Харриса (Harris corner detector), построенном на основе того нехитрого факта, что в области вокруг угла у градиента изображения 2 основных направления. Обладает частичной инвариантностью к преобразованиям поворота и к изменению освещения, но не к масштабу.

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

В качестве детектора, не чувствительного к масштабу была предложена концепция блобов (Blobe) – каплевидных окрестностей, в центре которых расположена особая точка. Внимание – ужас. Для определения таких окрестностей использовались лапласианы гауссианов (LoG – ЛОГ-фильтром) или разница гауссианов (DoG – DOG-фильтром). Несмотря на зловещее название тут тоже все просто. Изображение, как все помнят, мы представляем в виде функции. Лапласиан – сумма вторых частных производных функции в точке. Гауссиан – это просто гауссова функция – которой обрабатывают изображение. Соответственно лапласиан гауссиана – представление функции-изображения после применения оператора Гаусса, через сумму частных производных (его трехмерный график, при некоторой доле воображения, напоминает мексиканскую шляпку или сомбреро).

Характеристический размер блоба, теоретически, можно найти так: провести свертку размытого Гауссом изображения с помощью оператора Лапласа в нескольких масштабах и выбрать тот масштаб, на котором достигается максимальный отклик лапласиана. Для того чтобы это все работало на больших масштабах – необходима нормализация. Именно так и работали первые многомасштабные детекторы блобов. Одно но – лапласианы дорого считать. Лапласиан гауссиана можно приближенно представить в виде разницы двух гауссиан (с различным масштабом) – по русски это значит что мы “размазываем” исходное изображение с помощью оператора Гаусса (с разными значениями сигмы) и вычитаем одно из другого.

Детекторы углов и блобов можно использовать параллельно. На этой нехитрой идее выросли алгоритма Харис-Лапласа (Harris–Laplace) и Хессиан (Hessian affine region detector).
Общая идея – мы также выделяем углы на изображении, но уже с учетом характеристического размера: ищем точки максимизирующие отклик угла Харриса по изображению и отклик Лаплассиана по масштабу. Отклик – это просто значения функции после применения фильтра.

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

Развитием идеи блобов явились детекторы областей: EBR (edge-based regions), IBR (Intensity-Extrema-Based Region), MSER (Maximally stable external regions). Характерных областей на изображении будет значительно меньше чем блобов, но, с точки зрения семантического описания сцены, они более информативны. К сожалению, на информацию о применении в практических задачах такого подхода я не натыкался.

Как описать локальные особенности? Дескрипторы особых точек (feature descriptor)

После того как особые точки найдены их надо друг с дружкой сравнивать. Для этого необходимо некоторое компактное представление характерных особенностей. Они должны быть:

  • Простыми – представление должно быть быстро вычислимым.
  • Уникальными – разные точки должны иметь разное представление.
  • Локальными – как и сама особая точка ее представление должно зависеть лишь от небольшой окрестности.
  • Инвариантными к максимально большему числу преобразований.

Обычно используется вектор-признаков. И вопрос только в одном – по каким характеристикам вычислять этот дескриптор.

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

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

Тем не менее, в практических задачах уже давно эталоном стал дескриптор SIFTScale-invariant feature transform и его производные – SURF, GLOH и PCA-SIFT. Самый его жирный минус – для использования необходим патент.

Состоит из трех основных компонентов:

  • Детектор на основе разницы гауссиан – DoG – служит для определения положения и характерного масштаба особой точки на изображении.
  • Гистограмма градиентов, используется для определения ориентации особой точки (берется самый сильный градиент).
  • Дескриптор конструируется на основе направлений всех градиентов орестности.

Инвариантен к малому сдвигу и изменениям освещения.

Более компактное представление дескриптора практиковалось в методы PCA-SIFT. Использование цветовой информации нашло свое отражении в дескрипторе RGB-SIFT (3 SIFT для каждого канала) а также C-SIFT, rgSIFT.

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

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

Готовое приложение для сравнения всех детекторов в OpenCV (SIFT, SURF, ORB, FREAK и тд) с гуи и исходниками доступно здесь – https://code.google.com/p/find-object/

Для сравнительно недавнего (2011) сравнения дескрипторов и детекторов особых точек гуглить:
Steffen Gauglitz Tobias Höllerer Matthew Turk
Evaluation of Interest Point Detectors and Feature Descriptors for Visual Tracking

Сравнение дескрипторов:
http://computer-vision-talks.com/2011/08/feature-descriptor-comparison-report/
http://computer-vision-talks.com/2012/08/a-battle-of-three-descriptors-surf-freak-and-brisk/

May 03

05 – машинное обучение для классификации изображений

Машинное обучение – для компьютерного зрения

компьютерное зрение - как научить компьютер думать

компьютерное зрение – как научить компьютер думать

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

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

Машинное обучение это когда компьютеру скормили учебную выборку данных (положительные и отрицательные примеры), а он на их основе научился работать с новыми данными(не входящими в учебную выборку). Конкретный объект можно описать с помощью признаков и характеристик, если проанализировать несколько объектов одного класса – можно выделить их общие признаки, и при изучении нового объекта отталкиваться от нашего представления о базовом классе, для того чтобы понять относится ли новый объект к известному нам классу. Например, мы хотим распознавать на любом изображении человека. Тогда нам нужна учебная выборка содержащая и не содержащая людей. Люди должны быть разные – высокие, толстые, в разных одеждах и позах. При обработке учебной выборки формируется классификатор содержащий описание признаков людей, который, при применении к новому изображению, с некоторой долей вероятности (проценту совпавших признаков) будет распознавать или не распознавать людей.

Сколько всего объектов для распознавания? Примерно это число существительных плюс число объектов, описываемых словосочетаниями, не включая абстрактные, не материальные сущности + .. – … Словом много их. На практике, нам не нужен доскональный анализ каждой букашки на изображении – в силу приземленности, нас интересует сугубо практичная информация, навроде представлен ли на изображении конкретный объект. Или, что несколько более обобщенно – относится ли изображение к заданному классу – содержит ли он объект(ы) определенного типа (пейзаж/таракашку/атомный ледокол). Класс (категория) содержит информацию о том, как мы можем взаимодействовать с объектом (кошку вполне можно погладить за ухом, от тигра надо тикать). С другой стороны то, как мы можем взаимодействовать с объектом – функции объекта – зависят от наблюдателя – в кошке при виде мышки проснется охотник, в женщине – паника.

В идеальном мире разделение по категориям было бы простым – либо объект входит в данную категорию, либо нет: на основе набора свойств общих для всех элементов из категории. Это так называемые жесткие идеальные категории. На практике не все так просто – если кто-то любит лакомиться кактусами, это еще не повод заносить их в класс “еда”. Потому принято использовать так называемые естественные категории (Natural Categories by Rosch). В них каждый класс определяется наилучшими примерами-прототипами и, при сравнении неизвестного класса, можем задать некоторую степень (вероятность) соответствия категории. Нечеткие правила гораздо более гибкие и больше подходят для реальных задач классификации.

В психологии (ну, вы помните про кучу смежных отраслей, да?) используется термин каноническая перспектива (“Когнитивная психология”, Роберт Солсо) – такой эталонный экземпляр класса, по которому для человека проще всего опознать предмет. Скажут вам класс “кошка”, а на ум как-то сам собой приходит какой-нибудь Барсик, с расцарапанной по весне разбойничей мордой. Одна из упрощенных моделей мышления человека – feed-forward architecture – когда нет априорной информации о наблюдаемой сцене (человек без понятия что ему должны показать). При этом не обязательна обратная связь – т.е. никто не уточнит что качан капусты на мяч футбольный смахивает весьма отдаленно, хотя формой схожи. Хороший классификатор должен обеспечивать эквивалентные возможности.

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

Основные методы категоризация изображений:
Knn – метод ближайших соседей
и методы на основе машинного обучения
random forest – случайные леса
SVM – метод опорных векторов
boosting
neural networks – нейронные сети

Внимание – далее все тоже самое только оно расписано чуть более подробно с использованием разнузданной лексики из теории вероятности.

У всех объектов заданного класса есть некоторые схожие признаки. Распределение этих признаков (пусть неизвестное, пусть сложное) – одинаковое для всех всех объектов внутри класса. Имея некоторый конечный набор данных мы сможем оценить вероятностные характеристики – построить правила – некоторую функцию. Функция эта будет получать на вход характеристики важные для ответа на вопрос “Является ли эта штука объектом класса А?” – т.е. это классическая для тервера вероятность чего-то при условии таком-то. Пока, для упрощения, считаем что характеристики вычисляются на основе взаиморасположения особых точек.

Разновидности классификаций:

1) бинарная классификация – рассматриваем 2 класса

2) многоклассовая классификация – классов больше двух

3) регрессия – классов вообще нет, есть различные значения функции (определение возраста, веса)

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

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

Общая схема обучения (Features -> Coding -> Spatial pooling):
Для каждого изображения
– вычисляем признаки изображения (например по-пиксельно)
– разбиваем их на несколько категорий-кластеров (для усиления влияния на непосвященных можно воспользоваться термином “квантование признаков”, в случае неравномерного распределения признаков – в большинстве случае – лучше использовать адаптивное квантование с помощью K-средних)
– определяем область для вычисления (например, с помощью пространственной пирамиды – изображения разбиваем на области, и вычисляем признаки отдельно для каждой области, причем берем несколько уровней разделения – на 4 на 16 и т.п. частей)
– вычисляем признаки – агрегируем (гистограммы, мешок слов)
Используем один из методов категоризации на полученном наборе мешков слов, для формирования классификатора.

Гистограмму для описания распределения признаков можно строить по регулярной сетке или с помощью кластеризации (адаптивно). Используются различные подходы к ее вычислению: гистограммы цветов/градиентов/разреженных визуальных слов/ плотных визуальных слов. Каждый вид признаков можно рассчитывать по всему изображению, а можно по отдельной области. Часто используется пирамида разбиений из трех уровней (1+4+16 гистограммы).

Для сравнения гистограмм используются: пересечение гистограммы (histogram intersection), расстояние Манхэтена, L1 distance, расстояние хи-квадрат и т.п.

составляем лицо медведя на основе визуальных "слов" из словаря

составляем лицо медведя на основе визуальных “слов” из словаря

Один из метод агрегирования – мешок слов. Принимаем часто повторяющийся фрагмент изображения за визуальное слово. В конкретном изображении может встречать ровно один раз, несколько или ни одного раза. На их основе составляем словарь – базовый набор из фрагментов которые часто повторяются в коллекции изображений. Часто используется совместно и разреженная и плотная версия представления слов (Dense words PhowGray PhowColor – попросту говоря с перекрытиями или без). При построении словаря актуальной становится проблема золотой середины – чтобы слов было не слишком много (опять переобучение), но и не слишком мало (когда словами нельзя описать все признаки) – методы решения – использование деревьев словарей, хеширования.

Оценка качества работы классификатора

Эмпирический риск – отражает уровень ошибки тренировки – средняя вероятность ошибки, цель обучения классификатора – минимизация эмпирического риска. Во время тренировки руководствуемся правилом бритвы Окама (в науке это правда называется “Принцип структурной минимизации риска”) – и выбираем наиболее простую модель из тех, что достаточно точно описывают объект-категорию.

Для проверки качества можно использовать метод скользящего контроля (Cross validation)

Различают ошибки первого и второго рода – ошибки классифицированные и пропущенные. Их любят отображать на ROC-кривой – отражающей зависимость чувствительности и ошбки второго рода (ROC – receiver operating characteristic).

Если попробовать схематично описать процесс тренировки то получатся как то так: разделяем доступную нам выборку данных на несколько частей. Поочередно используем одну часть для проверки работы классификатора – контроля, а остальные для тренировки. Каждый вид объекта – прецедент – будет присутствовать минимум один раз в контрольный выборке, однако обучающие выборки будут сильно перекрываться и оценка может быть смещена. Альтернативный вариант – обучить на каждую часть свой классификатор и с помощью кросс-валидации выбрать лучший.

Виды классификаторов
1) Линейный классификатор.
Обладая достаточно развитым абстрактным мышлением можно представить себе множество признаков как набор точек в пространстве. Классификатор при таком представлении будет гиперплоскостью (линейной функцией) разделяющий множество признаков. Нас интересует какая гиперплоскость лучше – какой классификатор лучше подойдет для задачи категоризации объекта по признакам. Сухим языком эта задача формулируется как поиск гиперплоскости, максимизирующую отступ между положительными и отрицательными примерами (можно также учитывать влияние шума – добавив параметр минимизации доли признаков ошибочно отнесенных к “не своей” группе). На этот вопрос можно ответить с помощью метода опорных векторов (SVM – support vector machine).

2) Не-линейные.
Да где вы видели в реальном мире ситуацию, когда применимо линейное разделение? Однако уж больно подкупает кажущаяся простота линейного подхода. И был придуман простой способ избежать ужасов хитровыдуманных функций. Исходное пространство параметров отображается на многомерное пространство признаков (feature space), где обучающаяся выборка будет линейно разделима. (представьте что у вас на листке – двухмерном пространстве – есть набор из взаимнопересекающихся фигур, которые на этом листке никак не разделяются, но если вы перенесете этот же набор в трехмерное пространство все получится). Для упрощения вычислений, вычисляется ядровая функция – kernel trick, если она неотрицательно определена (Mercer’s condition) – тогда мы можем построить нелинейную решающую функцию в исходном пространстве.

Простейший пример ядра это полиномиальное.
1 выбрать признаки для изображения \мешок слов
2 выбрать ядро для этого вектор признака
3 вычслить матрицу значений ядра для каждой пары примеров из обучающей выборки
4 матрицу грузим в библиотеку SVM для получения весов и опорных векторов
5 во время вывода вычислить значения ядра для тест образца и каждого опорного вектора
и взять взвешенную сумму для получения значений решающей функции.

Не существует формулировки для многоклассовой категоризации, приходится комбинировать бинарные:
– один против всех (формируем классификатор отдельно для каждого класса против остальных, применим метод опорных векторов к образцу и назначим класс – для которых он наиболее выделен – достоверное решение)
– один против одного (построим классификатор для каждой пары классов на основе метода опорных векторов, МОВ голосует за классы выбираем класс с наибольшим числом голосов(

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

May 03

04 – поиск преобразования между особыми точками и немного моделирования

Сопоставление изображений

Когда изображения не сопоставляются

Когда изображения не сопоставляются

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

Что же позволяет нам проявлять столь похвальную прозорливость? У Эйфелевой башни есть некоторые характерные особенности которые мы можем безошибочно определить на всех снимках, не взирая на различия в освещении, ракурсе съемки или перекрытия (людьми или постройками). Более того – на основании снимка мы можем примерно прикинуть откуда он был сделан и определить условия съемки. (Нет, это не столько для того чтобы ощутить свое всемогущество – такая возможность пригодится при 3д реконструкции объектов и сцен, или построении панорам).

Если немного отвлечься от сладких грез о Париже и вернуться к нехитрым выкладкам из теории компьютерного зрения получается вот что: на изображении мы можем выделить характерные точки. Если изображений в нашем распоряжении несколько – мы можем попытаться определить – есть ли на них общие особые точки. Если мы найдем некоторое количество общих особых точек – тогда мы сможем полнее описать наблюдаемую сцену – в случае если сменился ракурс обзора. Это поможет определить как переместились особые точки по сравнению с предыдущим кадром (для описания движения объекта или частей объекта) – т.е. сможем оценить изображение уже на более высоком уровне.

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

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

Общий алгоритм поиска преобразования между двумя изображениями на основе особых точек:

  • Находим особые точки
  • Вычисляем дескрипторы особых точек
  • Сопоставляем точки по дескрипторам – получая соответствия точек
  • По этому набору соответствий вычислить модель преобразования (не забывая про ошибки измерения положения точек)

Особая точка на первом изображении потенциально может соответствовать любой из особых точек второго изображения (мы же не можем заранее предсказать как изменилась сцена или сместилась эта точка). Потому, при анализе используются наборы из возможных пар соответствий. Проверять каждую особую точку на соответствие со всеми особыми точками второго изображения – способ конечно надежный но слишком уж ресурсоемкий. Для ускорения анализа сейчас принято составлять гипотезы для набора разных точек в совокупности – MND – mutual neighbor distance и проверять, насколько они согласуются друг с другом. Например, разбивая изображения на отдельные участки – сетку, или отбирая пары случайным образом . Те точки, которые соответствуют модели преобразования называются inliers, те которые нет – выбросы – outliers. Дескрипторы сравниваются как обычно – SSD, SAD, кросс-кореляцией, пересечением гистограмм.

Надо отметить, что потенциально может быть полезно и попиксельное сопоставление (при поиске по шаблону или построении панорам) – однако для практики это скорей экзотика. Полноты описания ради – функции оценки попиксельного сопоставления – SSD, SAD, градиентный спуск, многомасштабное сопоставление.

Моделируя изображения

Для того, чтобы описать объект или целую сцену редко необходима вся информация о цвете и текстуре. В конце-концов, несколькими контурами а ля “палка палка огуречик” можно схематично изобразить и ледовое побоище и утро в сосновом бору. Что позволяет заявлять о том, что львиную долю изображений можно как-то аппроксимировать в виде набора простых (геометрических) моделей (линии, окружности). Простые модели, в свою очередь, можно составлять из набора особых точек. Как это сделать?

Существует целое семейство задач связанных с параметрами модели изображения на основе особых точек – model fitting – “подгонка” модели. Методы решения разделяют на робастные (выбросы не оказывают влияния на результирующую модель) и не робастные (неустойчивые к выбросам – например заданы точки удовлетворяющие модели и надо вычислить параметры этой модели)

1) Неробастные методы

Подгонка прямых линий
При заданном наборе точек, мы ищем прямую наилучшим образом их аппроксимирующую.
Решение – методом наименьших квадратов что упрощенно решается через сингулярное разложение – SVD (singular value decomposition).

В случае обобщенной модели, когда задан набор признаков и необходимо найти ее параметры используется все тот же метод наименьших квадратов, однако он уже называется DLT – Direct Linear Transform (или метод максимального правдоподобия, или минимизация суммы квадратов отклонения. Метод полных квадратов показывает наилучшие результаты. Однако для сложной модели, при использовании этого метода производится оптимизация алгебраической ошибки лишенной физического смысла, меж тем как для каждой модели есть и разумная ошибка, имеющая физический смысл. Методы минимизирующие эту ошибку называется gold standard.

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

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

На практике, такие задачи разбиваются на две части:
выбрать приближение – функцию, а потом итеративно его уточнять (как пример – взвешенный итеративный МНК).

b) RANSACRANdom SAmple Consensus
Параметры модели оцениваются не по всем данным, а по малой части не содержащей выбросы. Заранее неизвестно, какая часть не содержит выбросы – случайно делаем выборки несколько раз и для каждой выборки оцениваем модель и ее качество.

Регулируется несколькими параметрами:
– размер – минимальное количество точек для оценки параметров (например для прямой – две точки)
– количество выборок
– требуемая вероятность что правильная точка будет правильно классифицирована

Хорошо и часто работает на практике. Применяется для сопоставления изображений.
Недостатки:
не всегда удается хорошо оценить параметры по минимальной выборке
– много настраиваемых параметров (если порог не корректен – будут проблемы)
– иногда требуется слишком много итераций
– не срабатывает при очень высокой доле выбросов
– часто есть лучший способ нежели равновероятно выбирать точки

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

В вариации M-SAC для оценки порога используются M-оценки – это дает прирост точности и не влияет на вычислительную сложность.

Альтернатива RANSAC – LMS (Least median squares). Из его минусов – может выбрать неверную гипотезу. Не работает если больше половины точек выбросы. Потому на практике малопригоден.

Еще одна альтернатива RANSAC – схемы голосования (voting scheme). Пространство параметров называется фазовым пространством. Схемы голосования используются для поиска семейства кривых заданных параметрически.

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

Самое известное преобразование – преобразование Хафа (Hough Transform). Эффективно в случае если на изображении мало точек для перебора.

Альтернатива – преобразование Радона (Radon transform). Эффективен если мало возможных конфигураций кривых.

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

Apr 17

Machine Learning – links

Machine learning intro:

http://habrahabr.ru/company/yandex/blog/208034/ – comprehensive lection from Yandex (in russian)
http://ciml.info/ – A Course in Machine Learning by Hal Daumé III
http://alex.smola.org/teaching/cmu2013-10-701/index.html – Intro to Machine Learning ’13, by Carnegie Mellon University
http://alex.smola.org/teaching/berkeley2012/ – Scalable Machine Learning ’12, Berkley
http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=MachineLearning – Machine Learning from Andrew Ng
http://ufldl.stanford.edu/wiki/index.php/UFLDL_Tutorial – brief overview of advanced concepts
solution for above cources – https://github.com/danluu/UFLDL-tutorial
http://cs229.stanford.edu/materials.html – Machine Learning from Stanford
http://machinelearningmastery.com/start-here/ – practical recommendation to apply methods of ML – language, libraries, frameworks

Deep Learning:

http://deeplearning.stanford.edu/tutorial/ – great intro to world of deep learning
http://cvn.ecp.fr/personnel/iasonas/deeplearning.html – another intro
http://timothymasters.info/Deep_learning.html
http://deeplearning.net/tutorial/
http://markus.com/deep-learning-101/
https://developer.nvidia.com/deep-learning – toolset overview from NVidia
https://developer.nvidia.com/deep-learning-courses – cource from NVidia
http://cs.stanford.edu/people/karpathy/convnetjs/ – Javascript library for training Deep Learning models within browser
https://medium.com/@jiefeng/deep-learning-playbook-c5ebe34f8a1a – overview of toolset/libraries
https://jmozah.github.io/links/ – yet another links collection

Few video about deep learning:
http://techtalks.tv/deep_learning_nyu_spring_2014/
https://www.youtube.com/playlist?list=PLnDbcXCpYZ8lCKExMs8k4PtIbani9ESX3 – RE.WORK Deep Learning Summit
https://www.youtube.com/watch?v=PlhFWT7vAEw&list=PLjK8ddCbDMphIMSXn-w1IjyYpHU3DaUYw – Deep learning from Oxford

Udacity cources:

https://www.udacity.com/course/viewer#!/c-ud617/ – Intro to hadoop and reduce
https://www.udacity.com/course/ud359 – Intro to data science
https://www.udacity.com/course/viewer#!/c-ud675/ – Machine learning supervised learning
https://www.udacity.com/course/viewer#!/c-ud741/ – Machine learning – unsupervised learning
https://www.udacity.com/course/viewer#!/c-ud820/ – Reinforcement learning

Artificial Neural Networks:

http://neuralnetworksanddeeplearning.com/
http://www.theprojectspot.com/tutorial-post/introduction-to-artificial-neural-networks-part-1/7/
http://cs231n.stanford.edu/ – Convolutional Neural Networks for Visual Recognition

Older posts «

» Newer posts