Templates in plain C

Templates in ANSI C – simple and convenient method for emulating c++ like templates in plain c. Sample project, which demonstrate this technics can be found at github.

So, it is our constraints:

  • ANSI C (no templates, inheritance, overloading, default params etc.)
  • set of almost the same user-defined structures (the common difference – is types of internal fields)
  • set of the functions, which operates on user-defined structures and provide a common interface used in the whole app

The most straightforward way to solve such task is just hard coded all necessary routine by hand:

/*		first type - type_int							*/
typedef struct type_int {
	int data;
} type_int;

type_int
make_type_int(int init_val) {
	type_int return_value;
	return_value.data = init_val;
	return return_value;
}

type_int
subtract_type_int (type_int A, type_int B) {
	return make_type_int ( A.data - B.data );
}

/*
 *		and a lot of different functions here
 */

 /*		second type - type_float						*/
typedef struct type_float {
	float data;
} type_float;

/*
 *		etc.
 */

This leads to a huge amount of copy-paste and increase chances of errors, especially in case of a large set of functions and vicious habit of the compiler to use implicit type conversion.
But what is most important – such way a bit annoying and leads to impression of bad “smell” of your own code.
So I decided to google around (all helpful link are located at the end of articles) and find out that indeed – the better way for emulating templates in plain C is exist!

Here is my how-to for generating declaration of structures and implementation of methods operating on them, which can be used further in the whole project.
The main trick here is to refresh the basis of C preprocessor and macros.

Firstly, lets define several helpful macros in file my_types.h:

#define CAT(X,Y) X##_##Y
#define TYPE_NAME(X,Y) CAT(X,Y)

They will be used to generate names of your structures and methods using simple rule – merge two params, using underscore as delimiter.
Using macros above lets create our simple structure in file my_type_templates.h:

typedef struct TYPE_NAME(TYPE, SUB_TYPE) {
	SUB_TYPE data;
} TYPE_NAME(TYPE, SUB_TYPE);

And add declaration and implementation of all necessary functions:

#ifndef INCLUDED_IN_IMPLEMENTATION_FILE

/* if this file is included in any header - just add there definition of interface */
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( SUB_TYPE init_value);

TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(subtract, TYPE_NAME(TYPE, SUB_TYPE) ) ( TYPE_NAME(TYPE, SUB_TYPE) A, TYPE_NAME(TYPE, SUB_TYPE) B);

/*
 *		long list of supported functions
 */

#else

/* if this file is included in implementation file, where defined flag INCLUDED_IN_IMPLEMENTATION_FILE than generate implementaion of functions
 */

/*	add implementain make_* functions 		*/
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( SUB_TYPE init_value ) {
	TYPE_NAME(TYPE, SUB_TYPE) return_value;

	return_value.data = init_value;

	return return_value;
}

/*	add implementain subtract_* functions 		*/
TYPE_NAME(TYPE, SUB_TYPE)
TYPE_NAME(subtract, TYPE_NAME(TYPE, SUB_TYPE) ) ( TYPE_NAME(TYPE, SUB_TYPE) A, TYPE_NAME(TYPE, SUB_TYPE) B) {
	return TYPE_NAME(make, TYPE_NAME(TYPE, SUB_TYPE) ) ( A.data - B.data );
}

#endif

NOTE: you should not use any global ifdefs in file my_type_templates.h, because we have to include it multiple times, for every new custom type. Preprocessor will generate actual struct’s names and appropriate functions for manipulating them.

After that lets specify all types, which should be used in our project in usual header file my_types.h. For every type, which we want to generate – just add define/undef command like this:

#define TYPE type
#define SUB_TYPE int
    #include <my_type_templates.h>
#undef TYPE
#undef SUB_TYPE

and add implementation of all functions to a source file – my_types.c – just define flag showing that it is actual implementation and include header file, containing all defined types:

#define INCLUDED_IN_IMPLEMENTATION_FILE
#include <my_types.h>

In your project you should use my_types.h header as usual – just include it in all dependent sources. We have used ifdef for implementation part of our template, so header doesn’t contain any functions implementation – therefore there is no ambiguity during linking and all necessary function would be compile only once – during compilation of file my_types.c.

So the final files should looks like following:

my_types.h

#ifndef MY_TYPES
#define MY_TYPES

#define CAT(X,Y) X##_##Y
#define TYPE_NAME(X,Y) CAT(X,Y)

#define TYPE type

#define SUB_TYPE int
	#include <my_type_templates.h>
#undef SUB_TYPE

#define SUB_TYPE float
	#include <my_type_templates.h>
#undef SUB_TYPE

#undef TYPE

#endif /* MY_TYPES */

my_types.c

/*
 *		Add all includes necessary for you implementations
 */
#define INCLUDED_IN_IMPLEMENTATION_FILE
#include <my_types.h>

That’s it. Using this trick you will achieve compile-time type-checks, decrease amount of boring hand-coded routine and avoid possible errors using another approach, based on void pointers and multiple run-time casts.

Additional resources:
http://arnold.uthar.net/index.php?n=Work.TemplatesC
http://stackoverflow.com/questions/1489932/c-preprocessor-and-concatenation
http://stackoverflow.com/questions/351733/can-you-write-object-oriented-code-in-c

Что почитать для проф развития программисту

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

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

C++

  1. Язык программирования С++, Страуструп
  2. Эффективное использование C++. 55 верных способов улучшить структуру и код ваших программ, Мейерс Скотт
  3. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов, Мейерс Скотт
  4. C++: Библиотека программиста, Джефф Элджер
  5. Веревка достаточной длины, чтобы… выстрелить себе в ногу. Правила программирования на Си и Си++. Ален Голуб
  6. Стандарты программирования на С++. 101 правило и рекомедакция. Герб Саттер, Андрей Александреску
  7. C++. Практический подход к решению проблем программирования, Мэтью Уилсон
  8. Современное проектирование на С++: Обобщенное программирование и прикладные шаблоны проектирования, Андрей Александреску
  9. Advanced C++ Metaprogramming, Davide Di Gennaro
  10. Introduction to the Boost C++ Libraries, by Robert Demming

Алгоритмы

  1. Algorithms in a Nutshell, George T. Heineman, Gary Pollice, Stanley Selkow
  2. Алгоритмы на C++, Роберт Седжвик
  3. Алгоритмы. Построение и анализ, Томас Кормен
  4. Искусство программирования, Дональд Э. Кнут

Сети

  1. Эффективное программирование TCP-IP, Снейдер Й.
  2. UNIX. Разработка сетевых приложений,  У. Р. Стивенс

Функциональный подход к программированию

  1. Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Peter Norvig
  2. Learn You Some Erlang for Great Good!: A Beginner’s Guide, Fred Hebert
  3. ERLANG Programming, Francesco Cesarini, Simon Thompson
  4. Purely Functional Data Structures, Chris Okasaki
  5. Learn You a Haskell for Great Good!: A Beginner’s Guide, Miran Lipovaca

Проектирование ООП программ

  1. Head First Object-Oriented Analysis and Design, Brett D. McLaughlin, Gary Pollice, Dave West
  2. Head First Design Patterns, Elisabeth Freeman, Eric Freeman, Bert Bates, Kathy Sierra, Elisabeth Robson
  3. Head First Software Development, Dan Pilone, Russ Miles
  4. Domain-Driven Design: Tackling Complexity in the Heart of Software, Eric Evans
  5. An Introduction to Object-Oriented Analysis and Design and Iterative Development, Craig Larman

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

  1. Computer Vision: Models, Learning, and Inference, Simon J. D. Prince
  2. Multiple View Geometry in Computer Vision Richard Hartley, Andrew Zisserman
  3. Computer Vision: A Modern Approach, David A. Forsyth
  4. Компьютерное зрение, Шапиро, Стокман

ОБЩАЯ МЕТОДОЛОГИЯ ПРОГРАММИРОВАНИЯ

  1. Чистый код. Создание, анализ и рефакторинг, Роберт Мартин
  2. Совершенный код, Стив Макконнелл
  3. 97 этюдов для архитекторов программных систем, Нил Форд, Майкл Найгард, Билл де Ора
  4. Защищённый код, Майкл Ховард, Дэвид Леблан
  5. Рефакторинг. Улучшение существующего кода, Мартин Фаулер
  6. Шаблоны корпоративных приложений, Мартин Фаулер
  7. Enterprise Integration Patterns: Designing, Building, and Deploying Messaging Solutions, Bobby Woolf, Gregor Hohpe
  8. How to Design Programs: An Introduction to Programming and Computing, http://htdp.org/, Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi
  9. Structure and Interpretation of Computer Programs (SICP), http://mitpress.mit.edu/sicp, Harold Abelson, Gerald Jay Sussman, Julie Sussman
  10. The Pragmatic Programmer: From Journeyman to Master, Andrew Hunt
  11. Writing Solid Code, Steve Maguire
  12. Hacker’s Delight, Henry S. Warren
  13. The Software Architect’s Profession: An Introduction, Marc Sewel
  14. 19 смертных грехов, угрожающих безопасности программ, Ховард М., Лебланк Д., Виега Д.
  15. Компиляторы: принципы, технологии и инструменты, “книга дракона”, Альфреда В. Ахо, Рави Сети, Джеффри Д. Ульмана,
  16. Паттерны проектирования, Гамма, Хелм, Джонсон, Влиссидес
  17. Test Driven Development: By Example, Kent Beck
  18. Code Craft: The Practice of Writing Excellent Code, Pete Goodliffe
  19. The Art of Multiprocessor Programming, Maurice Herlihy
  20. The Architecture of Open Source Applications, Amy Brown, Greg Wilson

VIM (emacs – 😛)

  1. Practical Vim: Edit Text at the Speed of Thought, Drew Neil
  2. Learning the vi and Vim Editors, Arnold Robbins, Elbert Hannah, Linda Lamb

Project Managment

  1. Искусство войны, Сунь-Цзы
  2. Мифический человеко-месяц, или Как создаются программные системы, Фредерик Брукс
  3. The Psychology of Computer Programming, Gerald M. Weinberg
  4. Extreme Programming Explained, Kent Beck
  5. Agile Software Development: The Cooperative Game, Alistar Cockburn
  6. Peopleware: Productive Projects and Teams, Tom DeMarco
  7. Adaptive Software Development: A Collaborative Approach to Managing Complex Systems, James A. Highsmith
  8. Software Craftsmanship: The New Imperative, Pete McBreen
  9. Dynamics of Software Development, Jim McCarthy
  10. Antipatterns: Managing Software Organizations and People, Colin J. Neill, Philip A. Laplante, Joanna F. DeFranco
  11. AntiPatterns in Project Management, William J. Brown
  12. Beyond Chaos: The Expert Edge in Managing Software Development, Larry L. Constantine
  13. The Manager Pool: Patterns for Radical Leadership (Software Patterns Series), by Don Sherwood Olson
  14. Death March, Edward Yourdon
  15. Leading a Software Development Team: A developer’s guide to successfully leading people, Richard Whitehead
  16. Head First PMP, Jennifer Greene, Andrew Stellman
  17. Agile Software Development, Principles, Patterns, and Practices, Robert C. Martin
  18. Цель. Процесс непрерывного совершенствования, Элияху М. Голдрат, Джефф Кокс
  19. Как пасти котов. Наставление для программистов, руководящих другими программистами, Дж. Ханк Рейнвотер

UX design

  1. A Project Guide to UX Design: For user experience designers in the field or in the making (2nd Edition) (Voices That Matter), Russ Unger, Carolyn Chandler

и, на посошок

Некоторые любопытные обсуждения литературы для проф развития:

http://stackoverflow.com/questions/1711/what-is-the-single-most-influential-book-every-programmer-should-read
http://habrahabr.ru/post/135897/
http://mrelusive.com/books/books.html – список книг для разработчика игр

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

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

Будет актуально для 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

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.

Введение в 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

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

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

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

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

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

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

На практике, вот это все разом необходимо далеко не всегда, так как зачастую небольшие упрощения позволяют махом отбросить большую часть сложностей (или добавить еще). Однако, для того чтобы осознанно использовать алгоритмы компьютерного зрения для конкретных практических задач – крайне желательно ориентироваться в плюсах-минусах методов и быть в курсе “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 – список библиотек с алгоритмами машинного обучения, применимых для задач компьютерного зрения

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тут

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, они не учитывают человеческое восприятие. На данный момент универсальной метрики нет.

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/

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 во время вывода вычислить значения ядра для тест образца и каждого опорного вектора
и взять взвешенную сумму для получения значений решающей функции.

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

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