Избегайте этой ловушки, не следует придавать антропоморфные черты Ларри Эллисону.
Брайэн Кантрилл

Похоже, что в Oracle приняли решение окончательно избавиться от трудовых ресурсов, составляющих костяк Sun Microsystems. Массовые увольнения затронули около 2500 сотрудников, работающих над операционной системой Solaris, платформой SPARC и системами хранения данных ZFS Storage Appliance.

Это не рядовая трансформация — оптимизация, а настоящая бойня. По мнению создателя системы динамической отладки Dtrace Брайэна Кантрилла (Bryan Cantrill) на сей раз нанесен непоправимый ущерб, в результате потери 90% производственных кадров подразделения Solaris, включая все руководство.

От Solaris до illumos

В 2009 г. Oracle приобрел испытывающую серьезнейшие трудности на рынке Sun Microsystems за 5.6 млрд. долларов США. Компания теряла позиции на рынке вследствие лавинообразного распространения Linux в качестве серверной ОС, успеха платформы amd64 и невнятной стратегии по взаимоотношениям с сообществом открытого ПО. Solaris стал открытым слишком поздно — лишь в 2005 г., причем открытым не полностью, отдельные элементы ОС, такие как локализация и некоторые драйвера, оставались проприетарными. Затем появился OpenSolaris, однако точкой сбора сообщества он не сумел стать. То ли дело была в лицензии CDDL, то ли проблема была в том, что Sun пыталась манипулировать проектом. Трудно сказать почему именно, но не взлетел.

Kicked butt, had fun, didn't cheat, loved our customers, changed computing forever. Scott McNealy

Эпитафия Скота МакНили как нельзя лучше отражает жизненный путь компании — отлично развлекались, не дурили головы своим заказчикам и навсегда изменили ИТ. Довольно быстро стало очевидно, что Solaris Ораклу попросту не нужен, и развивать его он не намерен. Затем 13 августе 2010 г. случилось одно из самых позорных событий в истории открытого ПО — компания втихую закрыла исходный код OS Solaris. Никаких официальных заявлений на сей счет не последовало.

We will distribute updates to approved CDDL or other open source-licensed code following full releases of our enterprise Solaris operating system. In this manner, new technology innovations will show up in our releases before anywhere else. We will no longer distribute source code for the entirety of the Solaris operating system in real-time while it is developed, on a nightly basis.

Это всего лишь отрывок из внутреннего циркуляра для сотрудников компании, который естественно сразу же просочился в прессу. Тут речь идет о том, что исходный код будут выкладывать только во время релиза новой версии ОС, а обновления будут только бинарными. Но это оказалось неправдой, после выхода Solaris 11 исходный код не выложили.

Для тех, кто владеет английским очень рекомендую посмотреть выступление Брайэна Кантрилла на конференции Usenix. Эпиграф к статье — одна из его цитат, вот еще несколько.

О принципах руководства компании. Оставшись без мудрого руководства манагеров инженеры выдали гору инноваций: ZFS, DTrace, Zones и много других.

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

О закрытии исходного кода OpenSolaris.

Это ОТВРАТИТЕЛЬНАЯ выходка со стороны корпорации. Вот из-за такого поведения мы становимся циничными и подозрительными.

О последствиях закрытия исходников OpenSolaris для нового проекта ОС illumos — полностью открытого форка OpenSolaris.

Мы готовимся к моменту Судного Дня в лицензиях открытого исходного кода, у нас есть такие сценарии, они работают и это здорово.

Вскоре после этого из Oracle ушли все разработчики DTrace, создатели ZFS, команда zones и сетевики. Вся разработка и инновация на этих направлениях далее происходила операционной системе illumos, где осела диаспора программистов из Sun Solaris. Благодаря особенностям открытых лицензий, в том числе CDDL, в рамках которой шла разработка OpenSolaris, Oracle не может претендовать на все последующие улучшения в коде illumos. То есть может, но только в рамках своего же проекта с открытым кодом. Сценарии Судного Дня работают как надо.

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

Факты россыпью

• Главная цель: выдоить патентные отчисления и штрафы у Google за использование Java в ОС Андроид, ставки были крупные — $8 млрд. Не срослось.
• В целом монетизация Java не удалась, Oracle передает NetBeans Apache Foundation, верное решение.
• Также решено не запускать платформу Sun Cloud.
• Из-за бюрократических проволочек вокруг заплаток безопасности для MySQL, появился форк MariaDB, куда перешло значительное число разработчиков и часть сообщества. Их оказалось достаточно для новой компании.

Выводы

Sun Microsystems еще недавно — живая легенда и лучшее, что когда-либо было в Unix. Вот лишь небольшая часть их наследия.

• NFS
• RPC
• ZFS
• DTrace
• Zones
• Fault Management Architecture
• Service Management Facility

Компания Oracle имела все возможности для того, чтобы развивать и поддерживать OpenSolaris, но вместо этого закрыла исходники и с тех пор Solaris уже не имел будущего. Когда тяжба с компанией Google за использования Java в мобильной ОС Андроид закончилась пшиком в Oracle потеряли к активам Sun Microsystems всякий интерес. Вместо этого компания будет продавать ПО на основе собственной операционной системы — Unbreakable Linux.

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

• Oracle Gets It Right: NetBeans Heads To Apache
• Компания Oracle массово сокращает сотрудников команд Solaris и SPARC
• Sun set: Oracle closes down last Sun product lines

Как это работает?

Метазначения и метафункции

template 
struct square {
  static const int value = x * x;
};

struct One;
struct Zero;

template 
struct Not {
  typedef Zero value;
};

template <>
struct Not  {
  typedef One value;
};

Список

template 
struct Cons {
  typedef h head;
  typedef t tail;
};

struct Nil;

// отрицание непустого списка
template 
struct negate {
private: // инкапсулируем промежуточные вычисления
  typedef typename list::head h; // голова
  typedef typename Not::value not_head; // отрицание головы
  typedef typename list::tail t; // хвост
  typedef typename negate::value not_tail; // отрицание хвоста
public:
  // список из отрицаний элементов - это отрицание головы,
  // соединённое с хвостом отрицаний
  typedef Cons value;
};

// отрицание пустого списка
template <>
struct negate  {
  // пустой список - сам себе отрицание
  typedef Nil value;
};

-- список - либо слитые голова и хвост (причём хвост - сам список),
--          либо пустота
data List a = Cons a List | Nil

-- хелперы для получения головы и хвоста
head (Cons x _) = x -- возвращает голову
tail (Cons _ xs) = xs -- возвращает хвост

-- отрицание списка
negate (Cons x xs) = Cons (Not x) (negate xs)
negate Nil = Nil

Функции высшего порядка

-- Преобразованная голова соединяется с преобразованным хвостом
map f (Cons x xs) = Cons (f x) (map f xs)
-- Пустой список преобразовывать не нужно
map f Nil = Nil

// преобразование непустого списка
// f - шаблон с одним аргументом - унарная метафункция
template 

typedef map>>>::value list;
// list эквивалентно Cons>>

Операции именования выражений

using x = Not::value;

template 
using g = Cons;

// рассмотрим только одну из специализаций
template 
struct If  {
  // expr1, expr2 вычислены, а expr1::value и expr2::value - нет
  typedef typename expr1::value value;
}

// If, destroy>::value не разрушит мир

template 
struct If  {
  // expr1, expr2 вычислены
  typedef expr1 value;
};

// If::value>::value разрушит мир

Замыкания

f x = g
  where g xs = Cons x xs

-- использование: (f x) xs или, что полезнее, map (f x) list

// до C++11: функциональный объект, захвативший переменную
struct f {
  f(something& x) : x(x) {}
  something_else operator () (something_else& xs) { // xs - явный аргумент
    return Cons(x, xs);
  }
private:
  something x; // неявный аргумент
};

// C++11 и выше: лямбда-функция, захватившая переменную
something x;
auto f = [x](something_else& xs) { return Cons(x, xs); };

template 
struct f {
  template 
  struct g {
    typedef Cons value;
  };
};

// использование: f::g::value или map::g, list>

Неограниченное число аргументов или синтаксический сахар для списков

typename 
struct list_wrapper {
  // передаём в list_wrapper<...>::call функцию,
  // которой передадут наши аргументы xs
  struct call

typename 
struct negate {
  template 
  struct f {
    typedef list_wrapper::value, ys> value;
  };
  
  typedef typename negate::template call::value;
};

typename <>
struct negate<> {
  typedef list_wrapper<> value;
};

Выход во внешний мир

template 
struct print {
  print () {
    std::cout << "unknown number" << std::endl;
  }
};

template <>
struct print  {
  print () {
    std::cout << "1" << std::endl;
  }
};

template <>
struct print  {
  print () {
    std::cout << "0" << std::endl;
  }
};

// print::value>() выведет "1"

sum, three> // тип - корректно
sum, three>() // значение - компилируется

do_something(sum(), three()) // значения - компилируется
sum(), three()> // нельзя посчитать,
// т.к. нет перехода от значений к типам

sum()), decltype(three())> // C++11; компилируется

typedef sum, three> x;
typedef decltype(one() + two() + three()) x;

auto v = one() + two() + three(); // v выполнится как императивная конструкция
typedef decltype(v) x;

Эзотерический язык, транслирующийся в шаблоны C++

Значения и функции

One;
Zero;

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

// использование: Not(One) или And(One, Zero)

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;
// map_t раскроется в template 

Список

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

Cons(x, xs)'.head; // x
Cons(x, xs)'.tail; // xs
Not(Zero);         // One
Not(Zero)'!;       // One

// отрицание непустого списка:
// список из отрицаний элементов - это отрицание головы,
// соединённое с хвостом отрицаний
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head; // голова
  not_head = Not(h); // отрицание головы
  t = list.tail; // хвост
  not_tail = negate(t); // отрицание хвоста
} // точку с запятой можно опустить!

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

Функции высшего порядка

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head; // голова
  new_head = f(h); // преобразованная голова
  t = list.tail; // хвост
  new_tail = map(f, t); // преобразованный хвост
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

Замыкания

f(val x) = {
  g(val xs) = Cons(x, xs)';
}

// использование: f(x)'.g(list) или map(f(x)'.g, list)

template 
struct f {
  template 
  struct value {               // value!
    typedef Cons value; // value!
  };
};

f (val x) = g(Not(x)) {
  g (val x) = x; // будет заменено на g (x1) = x1
  // т.к. x станет параметром template f и не допустит x как параметр template g
}

Выход во внешний мир

f(val x) = One;
f(Zero) = Zero;

main {
  print::value>(); // почему так?
}

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    // после typedef-ов head, tail расположится следующий блок кода:
    print() {
      impure print(head); // преобразуется в "print();"
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure { // аналогично print(Zero) { impure { ..., но короче
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

Пространства имён

namespace ns1 {
  namespace ns2 {
    f(val x) = x;
  }
}

namespace ns3 {
  using namespace ns1.ns2;
  g(val x) = f(x);
}

Лямбды

f          (val x) =  y(x) { y(x) = g(x); } // было
f = lambda (val x) -> y(x) { y(x) = g(x); } // стало

template  struct f {}; // пусть была метафункция f

using g = f; // нельзя описать эквивалентность шаблона шаблону

// нужно описать эквивалентность выражений, соответствующих типам
template  using g = f; // g - тип, f - тип

Недостатки и возможные пути решения

1. Нет сокрытия локальных переменных.
   Наивно решается вставкой impure { private: } в код или элементарной модификацией языка.
2. При использовании метаполя автоматически подставляется «typename».
   Не знаю, можно ли избавиться от этого автоматически. В качестве варианта решения можно использовать обязательную венгерскую нотацию (скажем, fMap(fCurry(fCons).fApply(vXs), vObj.vYs) — при доступе к метаполю подставится template, typename или ничего, если первым символом имени будет «f», «v» или «n» соответственно).
   
   Второй путь — «динамическая типизация». То есть представление всех сущностей в виде структуры-обёртки с хранящимся типом и значением:
   
   

   // объявляем значение x
   struct x {
     typedef internal::value type; // тип значения x
   };
   
   // объявляем функцию f(x) = x
   struct f {
     typedef internal::function type; // тип функции f
     template 
     struct value {
       typedef typename x::type type; // тип результата функции f
       struct result { // обёртка для того, чтобы избежать value::value
         typedef x value;
       };
     };
   };
   

   
   Транслятор автоматически сгенерирует пространство имён internal со списком типов и метафункциями для работы с ними; за счёт дополнительной обёртки struct result можно будет избавиться от value::value и возвращать безымянные функции из функций. Также из-за того, что любое значение или функция будет выражаться в виде структуры (то есть просто типа, а не типа или шаблона), можно будет задавать синонимы функций (с помощью typedef), отменить обязательное описание типов аргументов функции, устранить ограничения на лямбды и возврат функций из ФВП.
3. Есть ограничения на лямбды: они не могут возвращать функции и быть анонимными.
   Может помочь описанный выше подход.
   
   Также можно вместо value использовать два значения так, чтобы при увеличении глубины вложенности использовалось другое значение. Получится, что вместо value::value будет value1::value2 и никаких попыток переопределения конструктора не будет:
   
   

   template 
   struct f {
     typedef internal::True uses_value1; // использует value1
     template 
     struct value1 {
       typedef internal::False uses_value1; // использует value2
       typedef Cons value2;
     };
   };
   

   
   Вызвать такие метафункции можно будет с помощью отдельной метафункции, которая в зависимости от обязательного метаполя uses_value1 будет выбирать, доступаться до value1 или до value2.
4. Не учитываются вариадические шаблоны и целые числа как параметры шаблонов.
   Для реализации требуется поддержка кроме val дополнительных типов для чисел (int, uint, ...) и массивов ([val], [int], [uint], ...). При использовании метаполей придётся решить описанную выше проблему с указанием template и typename, т.к. для чисел ничего не требуется указывать, а для типов и шаблонов — требуется.

Пример программы

// строим списки:
my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    // печатаем списки:
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

my list is 1, 1, 0,
negated list is 0, 0, 1,
negated list is also 0, 0, 1,

impure {
  #include 
}

One;
Zero;

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

// отрицание непустого списка:
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head;
  not_head = Not(h);
  t = list.tail;
  not_tail = negate(t);
}

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head;
  new_head = f(h);
  t = list.tail;
  new_tail = map(f, t);
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    print() {
      impure print(head);
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure {
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

#include 
struct One;
struct Zero;
template 
struct Not {
  typedef Zero _value;
};
template <>
struct Not {
  typedef One _value;
};
template 
struct And;
template 
struct And {
  typedef x _value;
};
template 
struct And {
  typedef Zero _value;
};
struct Nil;
template 
struct Cons {
  typedef x head;
  typedef y tail;
};
template 
struct negate {
  typedef typename list::head h;
  typedef typename Not  ::_value not_head;
  typedef typename list::tail t;
  typedef typename negate  ::_value not_tail;
  typedef Cons   _value;
};
template <>
struct negate {
  typedef Nil _value;
};
template 

Транслятор

node src/compile <исходник> # запуск

Как это работает?

Метазначения и метафункции

template 
struct square {
  static const int value = x * x;
};

struct One;
struct Zero;

template 
struct Not {
  typedef Zero value;
};

template <>
struct Not  {
  typedef One value;
};

Список

template 
struct Cons {
  typedef h head;
  typedef t tail;
};

struct Nil;

// отрицание непустого списка
template 
struct negate {
private: // инкапсулируем промежуточные вычисления
  typedef typename list::head h; // голова
  typedef typename Not::value not_head; // отрицание головы
  typedef typename list::tail t; // хвост
  typedef typename negate::value not_tail; // отрицание хвоста
public:
  // список из отрицаний элементов - это отрицание головы,
  // соединённое с хвостом отрицаний
  typedef Cons value;
};

// отрицание пустого списка
template <>
struct negate  {
  // пустой список - сам себе отрицание
  typedef Nil value;
};

-- список - либо слитые голова и хвост (причём хвост - сам список),
--          либо пустота
data List a = Cons a List | Nil

-- хелперы для получения головы и хвоста
head (Cons x _) = x -- возвращает голову
tail (Cons _ xs) = xs -- возвращает хвост

-- отрицание списка
negate (Cons x xs) = Cons (Not x) (negate xs)
negate Nil = Nil

Функции высшего порядка

-- Преобразованная голова соединяется с преобразованным хвостом
map f (Cons x xs) = Cons (f x) (map f xs)
-- Пустой список преобразовывать не нужно
map f Nil = Nil

// преобразование непустого списка
// f - шаблон с одним аргументом - унарная метафункция
template 

typedef map>>>::value list;
// list эквивалентно Cons>>

Операции именования выражений

using x = Not::value;

template 
using g = Cons;

// рассмотрим только одну из специализаций
template 
struct If  {
  // expr1, expr2 вычислены, а expr1::value и expr2::value - нет
  typedef typename expr1::value value;
}

// If, destroy>::value не разрушит мир

template 
struct If  {
  // expr1, expr2 вычислены
  typedef expr1 value;
};

// If::value>::value разрушит мир

Замыкания

f x = g
  where g xs = Cons x xs

-- использование: (f x) xs или, что полезнее, map (f x) list

// до C++11: функциональный объект, захвативший переменную
struct f {
  f(something& x) : x(x) {}
  something_else operator () (something_else& xs) { // xs - явный аргумент
    return Cons(x, xs);
  }
private:
  something x; // неявный аргумент
};

// C++11 и выше: лямбда-функция, захватившая переменную
something x;
auto f = [x](something_else& xs) { return Cons(x, xs); };

template 
struct f {
  template 
  struct g {
    typedef Cons value;
  };
};

// использование: f::g::value или map::g, list>

Неограниченное число аргументов или синтаксический сахар для списков

typename 
struct list_wrapper {
  // передаём в list_wrapper<...>::call функцию,
  // которой передадут наши аргументы xs
  struct call

typename 
struct negate {
  template 
  struct f {
    typedef list_wrapper::value, ys> value;
  };
  
  typedef typename negate::template call::value;
};

typename <>
struct negate<> {
  typedef list_wrapper<> value;
};

Выход во внешний мир

template 
struct print {
  print () {
    std::cout << "unknown number" << std::endl;
  }
};

template <>
struct print  {
  print () {
    std::cout << "1" << std::endl;
  }
};

template <>
struct print  {
  print () {
    std::cout << "0" << std::endl;
  }
};

// print::value>() выведет "1"

sum, three> // тип - корректно
sum, three>() // значение - компилируется

do_something(sum(), three()) // значения - компилируется
sum(), three()> // нельзя посчитать,
// т.к. нет перехода от значений к типам

sum()), decltype(three())> // C++11; компилируется

typedef sum, three> x;
typedef decltype(one() + two() + three()) x;

auto v = one() + two() + three(); // v выполнится как императивная конструкция
typedef decltype(v) x;

Эзотерический язык, транслирующийся в шаблоны C++

Значения и функции

One;
Zero;

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

// использование: Not(One) или And(One, Zero)

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;
// map_t раскроется в template 

Список

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

Cons(x, xs)'.head; // x
Cons(x, xs)'.tail; // xs
Not(Zero);         // One
Not(Zero)'!;       // One

// отрицание непустого списка:
// список из отрицаний элементов - это отрицание головы,
// соединённое с хвостом отрицаний
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head; // голова
  not_head = Not(h); // отрицание головы
  t = list.tail; // хвост
  not_tail = negate(t); // отрицание хвоста
} // точку с запятой можно опустить!

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

Функции высшего порядка

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head; // голова
  new_head = f(h); // преобразованная голова
  t = list.tail; // хвост
  new_tail = map(f, t); // преобразованный хвост
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

Замыкания

f(val x) = {
  g(val xs) = Cons(x, xs)';
}

// использование: f(x)'.g(list) или map(f(x)'.g, list)

template 
struct f {
  template 
  struct value {               // value!
    typedef Cons value; // value!
  };
};

f (val x) = g(Not(x)) {
  g (val x) = x; // будет заменено на g (x1) = x1
  // т.к. x станет параметром template f и не допустит x как параметр template g
}

Выход во внешний мир

f(val x) = One;
f(Zero) = Zero;

main {
  print::value>(); // почему так?
}

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    // после typedef-ов head, tail расположится следующий блок кода:
    print() {
      impure print(head); // преобразуется в "print();"
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure { // аналогично print(Zero) { impure { ..., но короче
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

Пространства имён

namespace ns1 {
  namespace ns2 {
    f(val x) = x;
  }
}

namespace ns3 {
  using namespace ns1.ns2;
  g(val x) = f(x);
}

Лямбды

f          (val x) =  y(x) { y(x) = g(x); } // было
f = lambda (val x) -> y(x) { y(x) = g(x); } // стало

template  struct f {}; // пусть была метафункция f

using g = f; // нельзя описать эквивалентность шаблона шаблону

// нужно описать эквивалентность выражений, соответствующих типам
template  using g = f; // g - тип, f - тип

Недостатки и возможные пути решения

1. Нет сокрытия локальных переменных.
   Наивно решается вставкой impure { private: } в код или элементарной модификацией языка.
2. При использовании метаполя автоматически подставляется «typename».
   Не знаю, можно ли избавиться от этого автоматически. В качестве варианта решения можно использовать обязательную венгерскую нотацию (скажем, fMap(fCurry(fCons).fApply(vXs), vObj.vYs) — при доступе к метаполю подставится template, typename или ничего, если первым символом имени будет «f», «v» или «n» соответственно).
   
   Второй путь — «динамическая типизация». То есть представление всех сущностей в виде структуры-обёртки с хранящимся типом и значением:
   
   

   // объявляем значение x
   struct x {
     typedef internal::value type; // тип значения x
   };
   
   // объявляем функцию f(x) = x
   struct f {
     typedef internal::function type; // тип функции f
     template 
     struct value {
       typedef typename x::type type; // тип результата функции f
       struct result { // обёртка для того, чтобы избежать value::value
         typedef x value;
       };
     };
   };
   

   
   Транслятор автоматически сгенерирует пространство имён internal со списком типов и метафункциями для работы с ними; за счёт дополнительной обёртки struct result можно будет избавиться от value::value и возвращать безымянные функции из функций. Также из-за того, что любое значение или функция будет выражаться в виде структуры (то есть просто типа, а не типа или шаблона), можно будет задавать синонимы функций (с помощью typedef), отменить обязательное описание типов аргументов функции, устранить ограничения на лямбды и возврат функций из ФВП.
3. Есть ограничения на лямбды: они не могут возвращать функции и быть анонимными.
   Может помочь описанный выше подход.
   
   Также можно вместо value использовать два значения так, чтобы при увеличении глубины вложенности использовалось другое значение. Получится, что вместо value::value будет value1::value2 и никаких попыток переопределения конструктора не будет:
   
   

   template 
   struct f {
     typedef internal::True uses_value1; // использует value1
     template 
     struct value1 {
       typedef internal::False uses_value1; // использует value2
       typedef Cons value2;
     };
   };
   

   
   Вызвать такие метафункции можно будет с помощью отдельной метафункции, которая в зависимости от обязательного метаполя uses_value1 будет выбирать, доступаться до value1 или до value2.
4. Не учитываются вариадические шаблоны и целые числа как параметры шаблонов.
   Для реализации требуется поддержка кроме val дополнительных типов для чисел (int, uint, ...) и массивов ([val], [int], [uint], ...). При использовании метаполей придётся решить описанную выше проблему с указанием template и typename, т.к. для чисел ничего не требуется указывать, а для типов и шаблонов — требуется.

Пример программы

// строим списки:
my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    // печатаем списки:
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

my list is 1, 1, 0,
negated list is 0, 0, 1,
negated list is also 0, 0, 1,

impure {
  #include 
}

One;
Zero;

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

// отрицание непустого списка:
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head;
  not_head = Not(h);
  t = list.tail;
  not_tail = negate(t);
}

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head;
  new_head = f(h);
  t = list.tail;
  new_tail = map(f, t);
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    print() {
      impure print(head);
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure {
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

#include 
struct One;
struct Zero;
template 
struct Not {
  typedef Zero _value;
};
template <>
struct Not {
  typedef One _value;
};
template 
struct And;
template 
struct And {
  typedef x _value;
};
template 
struct And {
  typedef Zero _value;
};
struct Nil;
template 
struct Cons {
  typedef x head;
  typedef y tail;
};
template 
struct negate {
  typedef typename list::head h;
  typedef typename Not  ::_value not_head;
  typedef typename list::tail t;
  typedef typename negate  ::_value not_tail;
  typedef Cons   _value;
};
template <>
struct negate {
  typedef Nil _value;
};
template 

Транслятор

node src/compile <исходник> # запуск

Как это работает?

Метазначения и метафункции

template 
struct square {
  static const int value = x * x;
};

struct One;
struct Zero;

template 
struct Not {
  typedef Zero value;
};

template <>
struct Not  {
  typedef One value;
};

Список

template 
struct Cons {
  typedef h head;
  typedef t tail;
};

struct Nil;

// отрицание непустого списка
template 
struct negate {
private: // инкапсулируем промежуточные вычисления
  typedef typename list::head h; // голова
  typedef typename Not::value not_head; // отрицание головы
  typedef typename list::tail t; // хвост
  typedef typename negate::value not_tail; // отрицание хвоста
public:
  // список из отрицаний элементов - это отрицание головы,
  // соединённое с хвостом отрицаний
  typedef Cons value;
};

// отрицание пустого списка
template <>
struct negate  {
  // пустой список - сам себе отрицание
  typedef Nil value;
};

-- список - либо слитые голова и хвост (причём хвост - сам список),
--          либо пустота
data List a = Cons a List | Nil

-- хелперы для получения головы и хвоста
head (Cons x _) = x -- возвращает голову
tail (Cons _ xs) = xs -- возвращает хвост

-- отрицание списка
negate (Cons x xs) = Cons (Not x) (negate xs)
negate Nil = Nil

Функции высшего порядка

-- Преобразованная голова соединяется с преобразованным хвостом
map f (Cons x xs) = Cons (f x) (map f xs)
-- Пустой список преобразовывать не нужно
map f Nil = Nil

// преобразование непустого списка
// f - шаблон с одним аргументом - унарная метафункция
template 

typedef map>>>::value list;
// list эквивалентно Cons>>

Операции именования выражений

using x = Not::value;

template 
using g = Cons;

// рассмотрим только одну из специализаций
template 
struct If  {
  // expr1, expr2 вычислены, а expr1::value и expr2::value - нет
  typedef typename expr1::value value;
}

// If, destroy>::value не разрушит мир

template 
struct If  {
  // expr1, expr2 вычислены
  typedef expr1 value;
};

// If::value>::value разрушит мир

Замыкания

f x = g
  where g xs = Cons x xs

-- использование: (f x) xs или, что полезнее, map (f x) list

// до C++11: функциональный объект, захвативший переменную
struct f {
  f(something& x) : x(x) {}
  something_else operator () (something_else& xs) { // xs - явный аргумент
    return Cons(x, xs);
  }
private:
  something x; // неявный аргумент
};

// C++11 и выше: лямбда-функция, захватившая переменную
something x;
auto f = [x](something_else& xs) { return Cons(x, xs); };

template 
struct f {
  template 
  struct g {
    typedef Cons value;
  };
};

// использование: f::g::value или map::g, list>

Неограниченное число аргументов или синтаксический сахар для списков

typename 
struct list_wrapper {
  // передаём в list_wrapper<...>::call функцию,
  // которой передадут наши аргументы xs
  struct call

typename 
struct negate {
  template 
  struct f {
    typedef list_wrapper::value, ys> value;
  };
  
  typedef typename negate::template call::value;
};

typename <>
struct negate<> {
  typedef list_wrapper<> value;
};

Выход во внешний мир

template 
struct print {
  print () {
    std::cout << "unknown number" << std::endl;
  }
};

template <>
struct print  {
  print () {
    std::cout << "1" << std::endl;
  }
};

template <>
struct print  {
  print () {
    std::cout << "0" << std::endl;
  }
};

// print::value>() выведет "1"

sum, three> // тип - корректно
sum, three>() // значение - компилируется

do_something(sum(), three()) // значения - компилируется
sum(), three()> // нельзя посчитать,
// т.к. нет перехода от значений к типам

sum()), decltype(three())> // C++11; компилируется

typedef sum, three> x;
typedef decltype(one() + two() + three()) x;

auto v = one() + two() + three(); // v выполнится как императивная конструкция
typedef decltype(v) x;

Эзотерический язык, транслирующийся в шаблоны C++

Значения и функции

One;
Zero;

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

// использование: Not(One) или And(One, Zero)

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;
// map_t раскроется в template 

Список

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

Cons(x, xs)'.head; // x
Cons(x, xs)'.tail; // xs
Not(Zero);         // One
Not(Zero)'!;       // One

// отрицание непустого списка:
// список из отрицаний элементов - это отрицание головы,
// соединённое с хвостом отрицаний
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head; // голова
  not_head = Not(h); // отрицание головы
  t = list.tail; // хвост
  not_tail = negate(t); // отрицание хвоста
} // точку с запятой можно опустить!

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

Функции высшего порядка

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head; // голова
  new_head = f(h); // преобразованная голова
  t = list.tail; // хвост
  new_tail = map(f, t); // преобразованный хвост
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

Замыкания

f(val x) = {
  g(val xs) = Cons(x, xs)';
}

// использование: f(x)'.g(list) или map(f(x)'.g, list)

template 
struct f {
  template 
  struct value {               // value!
    typedef Cons value; // value!
  };
};

f (val x) = g(Not(x)) {
  g (val x) = x; // будет заменено на g (x1) = x1
  // т.к. x станет параметром template f и не допустит x как параметр template g
}

Выход во внешний мир

f(val x) = One;
f(Zero) = Zero;

main {
  print::value>(); // почему так?
}

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    // после typedef-ов head, tail расположится следующий блок кода:
    print() {
      impure print(head); // преобразуется в "print();"
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure { // аналогично print(Zero) { impure { ..., но короче
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

Пространства имён

namespace ns1 {
  namespace ns2 {
    f(val x) = x;
  }
}

namespace ns3 {
  using namespace ns1.ns2;
  g(val x) = f(x);
}

Лямбды

f          (val x) =  y(x) { y(x) = g(x); } // было
f = lambda (val x) -> y(x) { y(x) = g(x); } // стало

template  struct f {}; // пусть была метафункция f

using g = f; // нельзя описать эквивалентность шаблона шаблону

// нужно описать эквивалентность выражений, соответствующих типам
template  using g = f; // g - тип, f - тип

Недостатки и возможные пути решения

1. Нет сокрытия локальных переменных.
   Наивно решается вставкой impure { private: } в код или элементарной модификацией языка.
2. При использовании метаполя автоматически подставляется «typename».
   Не знаю, можно ли избавиться от этого автоматически. В качестве варианта решения можно использовать обязательную венгерскую нотацию (скажем, fMap(fCurry(fCons).fApply(vXs), vObj.vYs) — при доступе к метаполю подставится template, typename или ничего, если первым символом имени будет «f», «v» или «n» соответственно).
   
   Второй путь — «динамическая типизация». То есть представление всех сущностей в виде структуры-обёртки с хранящимся типом и значением:
   
   

   // объявляем значение x
   struct x {
     typedef internal::value type; // тип значения x
   };
   
   // объявляем функцию f(x) = x
   struct f {
     typedef internal::function type; // тип функции f
     template 
     struct value {
       typedef typename x::type type; // тип результата функции f
       struct result { // обёртка для того, чтобы избежать value::value
         typedef x value;
       };
     };
   };
   

   
   Транслятор автоматически сгенерирует пространство имён internal со списком типов и метафункциями для работы с ними; за счёт дополнительной обёртки struct result можно будет избавиться от value::value и возвращать безымянные функции из функций. Также из-за того, что любое значение или функция будет выражаться в виде структуры (то есть просто типа, а не типа или шаблона), можно будет задавать синонимы функций (с помощью typedef), отменить обязательное описание типов аргументов функции, устранить ограничения на лямбды и возврат функций из ФВП.
3. Есть ограничения на лямбды: они не могут возвращать функции и быть анонимными.
   Может помочь описанный выше подход.
   
   Также можно вместо value использовать два значения так, чтобы при увеличении глубины вложенности использовалось другое значение. Получится, что вместо value::value будет value1::value2 и никаких попыток переопределения конструктора не будет:
   
   

   template 
   struct f {
     typedef internal::True uses_value1; // использует value1
     template 
     struct value1 {
       typedef internal::False uses_value1; // использует value2
       typedef Cons value2;
     };
   };
   

   
   Вызвать такие метафункции можно будет с помощью отдельной метафункции, которая в зависимости от обязательного метаполя uses_value1 будет выбирать, доступаться до value1 или до value2.
4. Не учитываются вариадические шаблоны и целые числа как параметры шаблонов.
   Для реализации требуется поддержка кроме val дополнительных типов для чисел (int, uint, ...) и массивов ([val], [int], [uint], ...). При использовании метаполей придётся решить описанную выше проблему с указанием template и typename, т.к. для чисел ничего не требуется указывать, а для типов и шаблонов — требуется.

Пример программы

// строим списки:
my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    // печатаем списки:
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

my list is 1, 1, 0,
negated list is 0, 0, 1,
negated list is also 0, 0, 1,

impure {
  #include 
}

One;
Zero;

Not (val x) = Zero; // общий случай
Not (Zero) = One; // частный случай

And(val x, val y); // для x,y != One,Zero And не определена
And(val x, One) = x; // One - константа, val x - аргумент
And(val x, Zero) = Zero;

#type number = val;
#type list = val;
#type unary = number -> number;
#type map_t = (unary, list) -> list;

Nil;

Cons(val x, val y) {
  head = x;
  tail = y;
}

// отрицание непустого списка:
negate (list list) = Cons(not_head, not_tail)' {
  h = list.head;
  not_head = Not(h);
  t = list.tail;
  not_tail = negate(t);
}

// пустой список - сам себе отрицание
negate (Nil) = Nil; 

// преобразование непустого списка
map (unary f, list list) = Cons(new_head, new_tail)' {
  h = list.head;
  new_head = f(h);
  t = list.tail;
  new_tail = map(f, t);
}

// преобразование пустого списка
map (unary f, Nil) = Nil;

print(val list) {
  head = list.head;
  tail = list.tail;
  impure {
    print() {
      impure print(head);
      std::cout << ", ";
      impure print(tail);
    }
  }
}

print(Zero) = impure {
  print() {
    std::cout << "0";
  }
}

print(One) = impure {
  print() {
    std::cout << "1";
  }
}

print(Nil) = impure {
  print() {
    std::cout << std::endl;
  }
}

my_list = Cons(One, Cons(One, Cons(Zero, Nil)')')';
negated_list = negate(my_list);
negated_list2 = map(Not, my_list);

impure {
  int main() {
    std::cout << "my list is ";
    impure print(my_list);
    
    std::cout << "negated list is ";
    impure print(negated_list);
    
    std::cout << "negated list is also ";
    impure print(negated_list2);
  }
}

#include 
struct One;
struct Zero;
template 
struct Not {
  typedef Zero _value;
};
template <>
struct Not {
  typedef One _value;
};
template 
struct And;
template 
struct And {
  typedef x _value;
};
template 
struct And {
  typedef Zero _value;
};
struct Nil;
template 
struct Cons {
  typedef x head;
  typedef y tail;
};
template 
struct negate {
  typedef typename list::head h;
  typedef typename Not  ::_value not_head;
  typedef typename list::tail t;
  typedef typename negate  ::_value not_tail;
  typedef Cons   _value;
};
template <>
struct negate {
  typedef Nil _value;
};
template 

Транслятор

node src/compile <исходник> # запуск

О синхронном и асинхронном коде

console.log('1')
console.log('2')
console.log('3')

console.log('1')
setTimeout(function afterTwoSeconds() {
  console.log('2')
}, 2000)
console.log('3')

Постановка задачи

// аргумент url может быть чем-то вроде 'https://api.github.com/users/daspinola/repos'
function request(url) {
  const xhr = new XMLHttpRequest();
  xhr.timeout = 2000;
  xhr.onreadystatechange = function(e) {
    if (xhr.readyState === 4) {
      if (xhr.status === 200) {
       // Код обработки успешного завершения запроса
      } else {
       // Обрабатываем ответ с сообщением об ошибке
      }
    }
  }
  xhr.ontimeout = function () {
    // Ожидание ответа заняло слишком много времени, тут будет код, который обрабатывает подобную ситуацию
  }
  xhr.open('get', url, true)
  xhr.send();
}

Функции обратного вызова

// Вызовем функцию "doThis" с другой функцией в качестве параметра, в данном случае - это функция "andThenThis". Функция "doThis" исполнит код, находящийся в ней, после чего, в нужный момент, вызовет функцию "andThenThis".
doThis(andThenThis)
// Внутри "doThis" обращение к переданной ей функции осуществляется через параметр "callback" , фактически, это просто переменная, которая хранит ссылку на функцию
function andThenThis() {
  console.log('and then this')
}
// Назвать параметр, в котором окажется функция обратного вызова, можно как угодно, "callback" - это просто распространённый вариант
function doThis(callback) {
  console.log('this first')
  
  // Для того, чтобы функция, ссылка на которую хранится в переменной, была вызвана, нужно поместить после имени переменной скобки, '()', иначе ничего не получится
  callback()
}

function request(url, callback) {
  const xhr = new XMLHttpRequest();
  xhr.timeout = 2000;
  xhr.onreadystatechange = function(e) {
    if (xhr.readyState === 4) {
      if (xhr.status === 200) {
       callback(null, xhr.response)
      } else {
       callback(xhr.status, null)
      }
    }
  }
  xhr.ontimeout = function () {
   console.log('Timeout')
  }
  xhr.open('get', url, true)
  xhr.send();
}

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
request(userGet, function handleUsersList(error, users) {
  if (error) throw error
  const list = JSON.parse(users).items
  list.forEach(function(user) {
    request(user.repos_url, function handleReposList(err, repos) {
      if (err) throw err
      //Здесь обработаем список репозиториев
    })
  })
})

• Выполняется запрос для получения репозиториев пользователя (в данном случае я загружаю собственные репозитории);
  
• После завершения запроса вызывается коллбэк handleUsersList;
  
• Если не было ошибок, разбираем ответ сервера c помощью JSON.parse, преобразовываем его, для удобства, в объект;
  
• После этого перебираем список пользователей, так как в нём может быть больше одного элемента, и для каждого из них запрашиваем список репозиториев, используя URL, возвращённый для каждого пользователя после выполнения первого запроса. Подразумевается, что repos_url — это URL для наших следующих запросов, и получили мы его из первого запроса.
  
• Когда запрос, направленный на загрузку данных о репозиториях, завершён, вызывается коллбэк, теперь это handleReposList. Здесь, так же как и при загрузке списка пользователей, можно обработать ошибки или полезные данные, в которых содержится список репозиториев пользователя.
  

try {
  request(userGet, handleUsersList)
} catch (e) {
  console.error('Request boom! ', e)
}
function handleUsersList(error, users) {
  if (error) throw error
  const list = JSON.parse(users).items
  list.forEach(function(user) {
    request(user.repos_url, handleReposList)
  })
}
function handleReposList(err, repos) {
  if (err) throw err
  
  // Здесь обрабатываем список репозиториев
  console.log('My very few repos', repos)
}

Промисы

const myPromise = new Promise(function(resolve, reject) {
  
  // Здесь будет код
  
  if (codeIsFine) {
    resolve('fine')
  } else {
    reject('error')
  }
})
myPromise
  .then(function whenOk(response) {
    console.log(response)
    return response
  })
  .catch(function notOk(err) {
    console.error(err)
  })

• Промис инициализируется с помощью функции, в которой есть вызовы методов resolve и reject;
  
• Асинхронный код помещают внутри функции, созданной с помощью конструктора Promise. Если код будет выполнен успешно, вызывают метод resolve, если нет — reject;
  
• Если функция вызовет resolve, будет исполнен метод .then для объекта Promise, аналогично, если будет вызван reject, будет исполнен метод .catch.
  

• Методы resolve и reject принимают только один параметр, в результате, например, при выполнении команды вида resolve('yey', 'works'), коллбэку .then будет передано лишь 'yey';
  
• Если объединить в цепочку несколько вызовов .then, в конце соответствующих коллбэков следует всегда использовать return, иначе все они будут выполнены одновременно, а это, очевидно, не то, чего вы хотите достичь;
  
• При выполнении команды reject, если следующим в цепочке идёт .then, он будет выполнен (вы можете считать .then выражением, которое выполняется в любом случае);
  
• Если в цепочке из вызовов .then в каком-то из них возникнет ошибка, следующие за ним будут пропущены до тех пор, пока не будет найдено выражение .catch;
  
• У промисов есть три состояния: «pending» — состояние ожидания вызова resolve или reject, а также состояния «resolved» и «rejected», которые соответствуют успешному, с вызовом resolve, и неуспешному, с вызовом reject, завершению работы промиса. Когда промис оказывается в состоянии «resolved» или «rejected», оно уже не может быть изменено.
  

function request(url) {
  return new Promise(function (resolve, reject) {
    const xhr = new XMLHttpRequest();
    xhr.timeout = 2000;
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          resolve(xhr.response)
        } else {
          reject(xhr.status)
        }
      }
    }
    xhr.ontimeout = function () {
      reject('timeout')
    }
    xhr.open('get', url, true)
    xhr.send();
  })
}

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
const myPromise = request(userGet)
console.log('will be pending when logged', myPromise)
myPromise
  .then(function handleUsersList(users) {
    console.log('when resolve is found it comes here with the response, in this case users ', users)
    const list = JSON.parse(users).items
    return Promise.all(list.map(function(user) {
      return request(user.repos_url)
    }))
  })
  .then(function handleReposList(repos) {
    console.log('All users repos in an array', repos)
  })
  .catch(function handleErrors(error) {
    console.log('when a reject is executed it will come here ignoring the then statement ', error)
  })

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
const userRequest = request(userGet)
// Если просто прочитать эту часть программы вслух, можно сразу понять что именно делает код
userRequest
  .then(handleUsersList)
  .then(repoRequest)
  .then(handleReposList)
  .catch(handleErrors)
function handleUsersList(users) {
  return JSON.parse(users).items
}
function repoRequest(users) {
  return Promise.all(users.map(function(user) {
    return request(user.repos_url)
  }))
}
function handleReposList(repos) {
  console.log('All users repos in an array', repos)
}
function handleErrors(error) {
  console.error('Something went wrong ', error)
}

Генераторы

function* foo() {
  yield 1
  const args = yield 2
  console.log(args)
}
var fooIterator = foo()
console.log(fooIterator.next().value) // выведет 1
console.log(fooIterator.next().value) // выведет 2
fooIterator.next('aParam') // приведёт к вызову console.log внутри генератора и к выводу 'aParam'

function request(url) {
  return function(callback) {
    const xhr = new XMLHttpRequest();
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          callback(null, xhr.response)
        } else {
          callback(xhr.status, null)
        }
      }
    }
    xhr.ontimeout = function () {
      console.log('timeout')
    }
    xhr.open('get', url, true)
    xhr.send()
  }
}

function* list() {
  const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
 
  const users = yield request(userGet)
  
  yield
  
  for (let i = 0; i<=users.length; i++) {
    yield request(users[i].repos_url)
  }
}

• Мы ожидаем подготовки первого запроса, возвращая ссылку на функцию и ожидая коллбэка для этого первого запроса (вспомните функцию request, которая она принимает url и возвращает функцию, которая ожидает коллбэк);
  
• Ожидаем готовности списка пользователей, users, для отправки в следующий .next;
  
• Проходимся по полученному массиву users и ожидаем, для каждого из них, .next, возвращая, для каждого, соответствующий коллбэк.
  

try {
  const iterator = list()
  iterator.next().value(function handleUsersList(err, users) {
    if (err) throw err
    const list = JSON.parse(users).items
    
    // Отправляем список пользователей итератору
    iterator.next(list)
    
    list.forEach(function(user) {
      iterator.next().value(function userRepos(error, repos) {
        if (error) throw repos
        // Здесь обрабатываем информацию о репозиториях каждого пользователя
        console.log(user, JSON.parse(repos))
      })
    })
  })  
} catch (e) {
  console.error(e)
}

Async/await

sumTwentyAfterTwoSeconds(10)
  .then(result => console.log('after 2 seconds', result))
async function sumTwentyAfterTwoSeconds(value) {
  const remainder = afterTwoSeconds(20)
  return value + await remainder
}
function afterTwoSeconds(value) {
  return new Promise(resolve => {
    setTimeout(() => { resolve(value) }, 2000);
  });
}

• Имеется асинхронная функция sumTwentyAfterTwoSeconds;
  
• Мы предлагаем коду подождать разрешения промиса afterTwoSeconds, который может завершиться вызовом resolve или reject;
  
• Выполнение кода заканчивается в .then, где завершается операция, отмеченная ключевым словом await, в данном случае — это всего одна операция.
  

function request(url) {
  return new Promise(function(resolve, reject) {
    const xhr = new XMLHttpRequest();
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          resolve(xhr.response)
        } else {
          reject(xhr.status)
        }
      }
    }
    xhr.ontimeout = function () {
      reject('timeout')
    }
    xhr.open('get', url, true)
    xhr.send()
  })
}

async function list() {
  const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
  
  const users = await request(userGet)
  const usersList = JSON.parse(users).items
  
  usersList.forEach(async function (user) {
    const repos = await request(user.repos_url)
    
    handleRepoList(user, repos)
  })
}
function handleRepoList(user, repos) {
  const userRepos = JSON.parse(repos)
  
  // Обрабатываем тут репозитории для каждого пользователя
  console.log(user, userRepos)
}

list()
  .catch(e => console.error(e))

Итоги

О синхронном и асинхронном коде

console.log('1')
console.log('2')
console.log('3')

console.log('1')
setTimeout(function afterTwoSeconds() {
  console.log('2')
}, 2000)
console.log('3')

Постановка задачи

// аргумент url может быть чем-то вроде 'https://api.github.com/users/daspinola/repos'
function request(url) {
  const xhr = new XMLHttpRequest();
  xhr.timeout = 2000;
  xhr.onreadystatechange = function(e) {
    if (xhr.readyState === 4) {
      if (xhr.status === 200) {
       // Код обработки успешного завершения запроса
      } else {
       // Обрабатываем ответ с сообщением об ошибке
      }
    }
  }
  xhr.ontimeout = function () {
    // Ожидание ответа заняло слишком много времени, тут будет код, который обрабатывает подобную ситуацию
  }
  xhr.open('get', url, true)
  xhr.send();
}

Функции обратного вызова

// Вызовем функцию "doThis" с другой функцией в качестве параметра, в данном случае - это функция "andThenThis". Функция "doThis" исполнит код, находящийся в ней, после чего, в нужный момент, вызовет функцию "andThenThis".
doThis(andThenThis)
// Внутри "doThis" обращение к переданной ей функции осуществляется через параметр "callback" , фактически, это просто переменная, которая хранит ссылку на функцию
function andThenThis() {
  console.log('and then this')
}
// Назвать параметр, в котором окажется функция обратного вызова, можно как угодно, "callback" - это просто распространённый вариант
function doThis(callback) {
  console.log('this first')
  
  // Для того, чтобы функция, ссылка на которую хранится в переменной, была вызвана, нужно поместить после имени переменной скобки, '()', иначе ничего не получится
  callback()
}

function request(url, callback) {
  const xhr = new XMLHttpRequest();
  xhr.timeout = 2000;
  xhr.onreadystatechange = function(e) {
    if (xhr.readyState === 4) {
      if (xhr.status === 200) {
       callback(null, xhr.response)
      } else {
       callback(xhr.status, null)
      }
    }
  }
  xhr.ontimeout = function () {
   console.log('Timeout')
  }
  xhr.open('get', url, true)
  xhr.send();
}

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
request(userGet, function handleUsersList(error, users) {
  if (error) throw error
  const list = JSON.parse(users).items
  list.forEach(function(user) {
    request(user.repos_url, function handleReposList(err, repos) {
      if (err) throw err
      //Здесь обработаем список репозиториев
    })
  })
})

• Выполняется запрос для получения репозиториев пользователя (в данном случае я загружаю собственные репозитории);
  
• После завершения запроса вызывается коллбэк handleUsersList;
  
• Если не было ошибок, разбираем ответ сервера c помощью JSON.parse, преобразовываем его, для удобства, в объект;
  
• После этого перебираем список пользователей, так как в нём может быть больше одного элемента, и для каждого из них запрашиваем список репозиториев, используя URL, возвращённый для каждого пользователя после выполнения первого запроса. Подразумевается, что repos_url — это URL для наших следующих запросов, и получили мы его из первого запроса.
  
• Когда запрос, направленный на загрузку данных о репозиториях, завершён, вызывается коллбэк, теперь это handleReposList. Здесь, так же как и при загрузке списка пользователей, можно обработать ошибки или полезные данные, в которых содержится список репозиториев пользователя.
  

try {
  request(userGet, handleUsersList)
} catch (e) {
  console.error('Request boom! ', e)
}
function handleUsersList(error, users) {
  if (error) throw error
  const list = JSON.parse(users).items
  list.forEach(function(user) {
    request(user.repos_url, handleReposList)
  })
}
function handleReposList(err, repos) {
  if (err) throw err
  
  // Здесь обрабатываем список репозиториев
  console.log('My very few repos', repos)
}

Промисы

const myPromise = new Promise(function(resolve, reject) {
  
  // Здесь будет код
  
  if (codeIsFine) {
    resolve('fine')
  } else {
    reject('error')
  }
})
myPromise
  .then(function whenOk(response) {
    console.log(response)
    return response
  })
  .catch(function notOk(err) {
    console.error(err)
  })

• Промис инициализируется с помощью функции, в которой есть вызовы методов resolve и reject;
  
• Асинхронный код помещают внутри функции, созданной с помощью конструктора Promise. Если код будет выполнен успешно, вызывают метод resolve, если нет — reject;
  
• Если функция вызовет resolve, будет исполнен метод .then для объекта Promise, аналогично, если будет вызван reject, будет исполнен метод .catch.
  

• Методы resolve и reject принимают только один параметр, в результате, например, при выполнении команды вида resolve('yey', 'works'), коллбэку .then будет передано лишь 'yey';
  
• Если объединить в цепочку несколько вызовов .then, в конце соответствующих коллбэков следует всегда использовать return, иначе все они будут выполнены одновременно, а это, очевидно, не то, чего вы хотите достичь;
  
• При выполнении команды reject, если следующим в цепочке идёт .then, он будет выполнен (вы можете считать .then выражением, которое выполняется в любом случае);
  
• Если в цепочке из вызовов .then в каком-то из них возникнет ошибка, следующие за ним будут пропущены до тех пор, пока не будет найдено выражение .catch;
  
• У промисов есть три состояния: «pending» — состояние ожидания вызова resolve или reject, а также состояния «resolved» и «rejected», которые соответствуют успешному, с вызовом resolve, и неуспешному, с вызовом reject, завершению работы промиса. Когда промис оказывается в состоянии «resolved» или «rejected», оно уже не может быть изменено.
  

function request(url) {
  return new Promise(function (resolve, reject) {
    const xhr = new XMLHttpRequest();
    xhr.timeout = 2000;
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          resolve(xhr.response)
        } else {
          reject(xhr.status)
        }
      }
    }
    xhr.ontimeout = function () {
      reject('timeout')
    }
    xhr.open('get', url, true)
    xhr.send();
  })
}

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
const myPromise = request(userGet)
console.log('will be pending when logged', myPromise)
myPromise
  .then(function handleUsersList(users) {
    console.log('when resolve is found it comes here with the response, in this case users ', users)
    const list = JSON.parse(users).items
    return Promise.all(list.map(function(user) {
      return request(user.repos_url)
    }))
  })
  .then(function handleReposList(repos) {
    console.log('All users repos in an array', repos)
  })
  .catch(function handleErrors(error) {
    console.log('when a reject is executed it will come here ignoring the then statement ', error)
  })

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
const userRequest = request(userGet)
// Если просто прочитать эту часть программы вслух, можно сразу понять что именно делает код
userRequest
  .then(handleUsersList)
  .then(repoRequest)
  .then(handleReposList)
  .catch(handleErrors)
function handleUsersList(users) {
  return JSON.parse(users).items
}
function repoRequest(users) {
  return Promise.all(users.map(function(user) {
    return request(user.repos_url)
  }))
}
function handleReposList(repos) {
  console.log('All users repos in an array', repos)
}
function handleErrors(error) {
  console.error('Something went wrong ', error)
}

Генераторы

function* foo() {
  yield 1
  const args = yield 2
  console.log(args)
}
var fooIterator = foo()
console.log(fooIterator.next().value) // выведет 1
console.log(fooIterator.next().value) // выведет 2
fooIterator.next('aParam') // приведёт к вызову console.log внутри генератора и к выводу 'aParam'

function request(url) {
  return function(callback) {
    const xhr = new XMLHttpRequest();
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          callback(null, xhr.response)
        } else {
          callback(xhr.status, null)
        }
      }
    }
    xhr.ontimeout = function () {
      console.log('timeout')
    }
    xhr.open('get', url, true)
    xhr.send()
  }
}

function* list() {
  const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
 
  const users = yield request(userGet)
  
  yield
  
  for (let i = 0; i<=users.length; i++) {
    yield request(users[i].repos_url)
  }
}

• Мы ожидаем подготовки первого запроса, возвращая ссылку на функцию и ожидая коллбэка для этого первого запроса (вспомните функцию request, которая она принимает url и возвращает функцию, которая ожидает коллбэк);
  
• Ожидаем готовности списка пользователей, users, для отправки в следующий .next;
  
• Проходимся по полученному массиву users и ожидаем, для каждого из них, .next, возвращая, для каждого, соответствующий коллбэк.
  

try {
  const iterator = list()
  iterator.next().value(function handleUsersList(err, users) {
    if (err) throw err
    const list = JSON.parse(users).items
    
    // Отправляем список пользователей итератору
    iterator.next(list)
    
    list.forEach(function(user) {
      iterator.next().value(function userRepos(error, repos) {
        if (error) throw repos
        // Здесь обрабатываем информацию о репозиториях каждого пользователя
        console.log(user, JSON.parse(repos))
      })
    })
  })  
} catch (e) {
  console.error(e)
}

Async/await

sumTwentyAfterTwoSeconds(10)
  .then(result => console.log('after 2 seconds', result))
async function sumTwentyAfterTwoSeconds(value) {
  const remainder = afterTwoSeconds(20)
  return value + await remainder
}
function afterTwoSeconds(value) {
  return new Promise(resolve => {
    setTimeout(() => { resolve(value) }, 2000);
  });
}

• Имеется асинхронная функция sumTwentyAfterTwoSeconds;
  
• Мы предлагаем коду подождать разрешения промиса afterTwoSeconds, который может завершиться вызовом resolve или reject;
  
• Выполнение кода заканчивается в .then, где завершается операция, отмеченная ключевым словом await, в данном случае — это всего одна операция.
  

function request(url) {
  return new Promise(function(resolve, reject) {
    const xhr = new XMLHttpRequest();
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          resolve(xhr.response)
        } else {
          reject(xhr.status)
        }
      }
    }
    xhr.ontimeout = function () {
      reject('timeout')
    }
    xhr.open('get', url, true)
    xhr.send()
  })
}

async function list() {
  const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
  
  const users = await request(userGet)
  const usersList = JSON.parse(users).items
  
  usersList.forEach(async function (user) {
    const repos = await request(user.repos_url)
    
    handleRepoList(user, repos)
  })
}
function handleRepoList(user, repos) {
  const userRepos = JSON.parse(repos)
  
  // Обрабатываем тут репозитории для каждого пользователя
  console.log(user, userRepos)
}

list()
  .catch(e => console.error(e))

Итоги

О синхронном и асинхронном коде

console.log('1')
console.log('2')
console.log('3')

console.log('1')
setTimeout(function afterTwoSeconds() {
  console.log('2')
}, 2000)
console.log('3')

Постановка задачи

// аргумент url может быть чем-то вроде 'https://api.github.com/users/daspinola/repos'
function request(url) {
  const xhr = new XMLHttpRequest();
  xhr.timeout = 2000;
  xhr.onreadystatechange = function(e) {
    if (xhr.readyState === 4) {
      if (xhr.status === 200) {
       // Код обработки успешного завершения запроса
      } else {
       // Обрабатываем ответ с сообщением об ошибке
      }
    }
  }
  xhr.ontimeout = function () {
    // Ожидание ответа заняло слишком много времени, тут будет код, который обрабатывает подобную ситуацию
  }
  xhr.open('get', url, true)
  xhr.send();
}

Функции обратного вызова

// Вызовем функцию "doThis" с другой функцией в качестве параметра, в данном случае - это функция "andThenThis". Функция "doThis" исполнит код, находящийся в ней, после чего, в нужный момент, вызовет функцию "andThenThis".
doThis(andThenThis)
// Внутри "doThis" обращение к переданной ей функции осуществляется через параметр "callback" , фактически, это просто переменная, которая хранит ссылку на функцию
function andThenThis() {
  console.log('and then this')
}
// Назвать параметр, в котором окажется функция обратного вызова, можно как угодно, "callback" - это просто распространённый вариант
function doThis(callback) {
  console.log('this first')
  
  // Для того, чтобы функция, ссылка на которую хранится в переменной, была вызвана, нужно поместить после имени переменной скобки, '()', иначе ничего не получится
  callback()
}

function request(url, callback) {
  const xhr = new XMLHttpRequest();
  xhr.timeout = 2000;
  xhr.onreadystatechange = function(e) {
    if (xhr.readyState === 4) {
      if (xhr.status === 200) {
       callback(null, xhr.response)
      } else {
       callback(xhr.status, null)
      }
    }
  }
  xhr.ontimeout = function () {
   console.log('Timeout')
  }
  xhr.open('get', url, true)
  xhr.send();
}

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
request(userGet, function handleUsersList(error, users) {
  if (error) throw error
  const list = JSON.parse(users).items
  list.forEach(function(user) {
    request(user.repos_url, function handleReposList(err, repos) {
      if (err) throw err
      //Здесь обработаем список репозиториев
    })
  })
})

• Выполняется запрос для получения репозиториев пользователя (в данном случае я загружаю собственные репозитории);
  
• После завершения запроса вызывается коллбэк handleUsersList;
  
• Если не было ошибок, разбираем ответ сервера c помощью JSON.parse, преобразовываем его, для удобства, в объект;
  
• После этого перебираем список пользователей, так как в нём может быть больше одного элемента, и для каждого из них запрашиваем список репозиториев, используя URL, возвращённый для каждого пользователя после выполнения первого запроса. Подразумевается, что repos_url — это URL для наших следующих запросов, и получили мы его из первого запроса.
  
• Когда запрос, направленный на загрузку данных о репозиториях, завершён, вызывается коллбэк, теперь это handleReposList. Здесь, так же как и при загрузке списка пользователей, можно обработать ошибки или полезные данные, в которых содержится список репозиториев пользователя.
  

try {
  request(userGet, handleUsersList)
} catch (e) {
  console.error('Request boom! ', e)
}
function handleUsersList(error, users) {
  if (error) throw error
  const list = JSON.parse(users).items
  list.forEach(function(user) {
    request(user.repos_url, handleReposList)
  })
}
function handleReposList(err, repos) {
  if (err) throw err
  
  // Здесь обрабатываем список репозиториев
  console.log('My very few repos', repos)
}

Промисы

const myPromise = new Promise(function(resolve, reject) {
  
  // Здесь будет код
  
  if (codeIsFine) {
    resolve('fine')
  } else {
    reject('error')
  }
})
myPromise
  .then(function whenOk(response) {
    console.log(response)
    return response
  })
  .catch(function notOk(err) {
    console.error(err)
  })

• Промис инициализируется с помощью функции, в которой есть вызовы методов resolve и reject;
  
• Асинхронный код помещают внутри функции, созданной с помощью конструктора Promise. Если код будет выполнен успешно, вызывают метод resolve, если нет — reject;
  
• Если функция вызовет resolve, будет исполнен метод .then для объекта Promise, аналогично, если будет вызван reject, будет исполнен метод .catch.
  

• Методы resolve и reject принимают только один параметр, в результате, например, при выполнении команды вида resolve('yey', 'works'), коллбэку .then будет передано лишь 'yey';
  
• Если объединить в цепочку несколько вызовов .then, в конце соответствующих коллбэков следует всегда использовать return, иначе все они будут выполнены одновременно, а это, очевидно, не то, чего вы хотите достичь;
  
• При выполнении команды reject, если следующим в цепочке идёт .then, он будет выполнен (вы можете считать .then выражением, которое выполняется в любом случае);
  
• Если в цепочке из вызовов .then в каком-то из них возникнет ошибка, следующие за ним будут пропущены до тех пор, пока не будет найдено выражение .catch;
  
• У промисов есть три состояния: «pending» — состояние ожидания вызова resolve или reject, а также состояния «resolved» и «rejected», которые соответствуют успешному, с вызовом resolve, и неуспешному, с вызовом reject, завершению работы промиса. Когда промис оказывается в состоянии «resolved» или «rejected», оно уже не может быть изменено.
  

function request(url) {
  return new Promise(function (resolve, reject) {
    const xhr = new XMLHttpRequest();
    xhr.timeout = 2000;
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          resolve(xhr.response)
        } else {
          reject(xhr.status)
        }
      }
    }
    xhr.ontimeout = function () {
      reject('timeout')
    }
    xhr.open('get', url, true)
    xhr.send();
  })
}

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
const myPromise = request(userGet)
console.log('will be pending when logged', myPromise)
myPromise
  .then(function handleUsersList(users) {
    console.log('when resolve is found it comes here with the response, in this case users ', users)
    const list = JSON.parse(users).items
    return Promise.all(list.map(function(user) {
      return request(user.repos_url)
    }))
  })
  .then(function handleReposList(repos) {
    console.log('All users repos in an array', repos)
  })
  .catch(function handleErrors(error) {
    console.log('when a reject is executed it will come here ignoring the then statement ', error)
  })

const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
const userRequest = request(userGet)
// Если просто прочитать эту часть программы вслух, можно сразу понять что именно делает код
userRequest
  .then(handleUsersList)
  .then(repoRequest)
  .then(handleReposList)
  .catch(handleErrors)
function handleUsersList(users) {
  return JSON.parse(users).items
}
function repoRequest(users) {
  return Promise.all(users.map(function(user) {
    return request(user.repos_url)
  }))
}
function handleReposList(repos) {
  console.log('All users repos in an array', repos)
}
function handleErrors(error) {
  console.error('Something went wrong ', error)
}

Генераторы

function* foo() {
  yield 1
  const args = yield 2
  console.log(args)
}
var fooIterator = foo()
console.log(fooIterator.next().value) // выведет 1
console.log(fooIterator.next().value) // выведет 2
fooIterator.next('aParam') // приведёт к вызову console.log внутри генератора и к выводу 'aParam'

function request(url) {
  return function(callback) {
    const xhr = new XMLHttpRequest();
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          callback(null, xhr.response)
        } else {
          callback(xhr.status, null)
        }
      }
    }
    xhr.ontimeout = function () {
      console.log('timeout')
    }
    xhr.open('get', url, true)
    xhr.send()
  }
}

function* list() {
  const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
 
  const users = yield request(userGet)
  
  yield
  
  for (let i = 0; i<=users.length; i++) {
    yield request(users[i].repos_url)
  }
}

• Мы ожидаем подготовки первого запроса, возвращая ссылку на функцию и ожидая коллбэка для этого первого запроса (вспомните функцию request, которая она принимает url и возвращает функцию, которая ожидает коллбэк);
  
• Ожидаем готовности списка пользователей, users, для отправки в следующий .next;
  
• Проходимся по полученному массиву users и ожидаем, для каждого из них, .next, возвращая, для каждого, соответствующий коллбэк.
  

try {
  const iterator = list()
  iterator.next().value(function handleUsersList(err, users) {
    if (err) throw err
    const list = JSON.parse(users).items
    
    // Отправляем список пользователей итератору
    iterator.next(list)
    
    list.forEach(function(user) {
      iterator.next().value(function userRepos(error, repos) {
        if (error) throw repos
        // Здесь обрабатываем информацию о репозиториях каждого пользователя
        console.log(user, JSON.parse(repos))
      })
    })
  })  
} catch (e) {
  console.error(e)
}

Async/await

sumTwentyAfterTwoSeconds(10)
  .then(result => console.log('after 2 seconds', result))
async function sumTwentyAfterTwoSeconds(value) {
  const remainder = afterTwoSeconds(20)
  return value + await remainder
}
function afterTwoSeconds(value) {
  return new Promise(resolve => {
    setTimeout(() => { resolve(value) }, 2000);
  });
}

• Имеется асинхронная функция sumTwentyAfterTwoSeconds;
  
• Мы предлагаем коду подождать разрешения промиса afterTwoSeconds, который может завершиться вызовом resolve или reject;
  
• Выполнение кода заканчивается в .then, где завершается операция, отмеченная ключевым словом await, в данном случае — это всего одна операция.
  

function request(url) {
  return new Promise(function(resolve, reject) {
    const xhr = new XMLHttpRequest();
    xhr.onreadystatechange = function(e) {
      if (xhr.readyState === 4) {
        if (xhr.status === 200) {
          resolve(xhr.response)
        } else {
          reject(xhr.status)
        }
      }
    }
    xhr.ontimeout = function () {
      reject('timeout')
    }
    xhr.open('get', url, true)
    xhr.send()
  })
}

async function list() {
  const userGet = `https://api.github.com/search/users?page=1&q=daspinola&type=Users`
  
  const users = await request(userGet)
  const usersList = JSON.parse(users).items
  
  usersList.forEach(async function (user) {
    const repos = await request(user.repos_url)
    
    handleRepoList(user, repos)
  })
}
function handleRepoList(user, repos) {
  const userRepos = JSON.parse(repos)
  
  // Обрабатываем тут репозитории для каждого пользователя
  console.log(user, userRepos)
}

list()
  .catch(e => console.error(e))

Итоги

Алексей Потапов
Профессор кафедры компьютерной фотоники и видеоинформатики ИТМО. Победитель конкурса грантов для молодых научно-педагогических работников вузов Санкт-Петербурга. Победитель конкурса грантов Президента Российской Федерации для государственной поддержки молодых российских ученых — докторов наук в области «Информационно-телекоммуникационных систем и технологий».

Вот, например, несколько неплохих курсов:
Introduction into Deep Learning
Neural Networks and Deep Learning
Convolutional Neural Networks for Visual Recognition

• Глубокие свёрточные сети для сегментации изображений (Сергей Николенко, ПОМИ РАН)
  
• От клика к прогнозу и обратно: Data Science пайплайны в ОК (Дмитрий Бугайченко, Одноклассники)
  
• Автоматический поиск контактной информации в интернете (Александр Сибиряков, Scrapinghub)
  
• Прикладное машинное обучение в электронной коммерции: сценарии и архитектуры пилотов и боевых проектов (Александр Сербул, 1С-Битрикс)
  
• Deep Learning: Распознавание сцен и достопримечательностей на изображениях (Андрей Бояров, Mail.ru)
  

Алексей Потапов
Профессор кафедры компьютерной фотоники и видеоинформатики ИТМО. Победитель конкурса грантов для молодых научно-педагогических работников вузов Санкт-Петербурга. Победитель конкурса грантов Президента Российской Федерации для государственной поддержки молодых российских ученых — докторов наук в области «Информационно-телекоммуникационных систем и технологий».

Вот, например, несколько неплохих курсов:
Introduction into Deep Learning
Neural Networks and Deep Learning
Convolutional Neural Networks for Visual Recognition

• Глубокие свёрточные сети для сегментации изображений (Сергей Николенко, ПОМИ РАН)
  
• От клика к прогнозу и обратно: Data Science пайплайны в ОК (Дмитрий Бугайченко, Одноклассники)
  
• Автоматический поиск контактной информации в интернете (Александр Сибиряков, Scrapinghub)
  
• Прикладное машинное обучение в электронной коммерции: сценарии и архитектуры пилотов и боевых проектов (Александр Сербул, 1С-Битрикс)
  
• Deep Learning: Распознавание сцен и достопримечательностей на изображениях (Андрей Бояров, Mail.ru)
  

Алексей Потапов
Профессор кафедры компьютерной фотоники и видеоинформатики ИТМО. Победитель конкурса грантов для молодых научно-педагогических работников вузов Санкт-Петербурга. Победитель конкурса грантов Президента Российской Федерации для государственной поддержки молодых российских ученых — докторов наук в области «Информационно-телекоммуникационных систем и технологий».

Вот, например, несколько неплохих курсов:
Introduction into Deep Learning
Neural Networks and Deep Learning
Convolutional Neural Networks for Visual Recognition

• Глубокие свёрточные сети для сегментации изображений (Сергей Николенко, ПОМИ РАН)
  
• От клика к прогнозу и обратно: Data Science пайплайны в ОК (Дмитрий Бугайченко, Одноклассники)
  
• Автоматический поиск контактной информации в интернете (Александр Сибиряков, Scrapinghub)
  
• Прикладное машинное обучение в электронной коммерции: сценарии и архитектуры пилотов и боевых проектов (Александр Сербул, 1С-Битрикс)
  
• Deep Learning: Распознавание сцен и достопримечательностей на изображениях (Андрей Бояров, Mail.ru)
  

Каждый год Министерство образования и науки РФ публикует перечень школьных олимпиад, дающих льготы при поступлении в вузы. С 2015 года в этот список входит и Технокубок — олимпиада по программированию под эгидой Mail.Ru Group.

Поучаствовать в Технокубке могут ученики 8—11-х классов. Олимпиада позволяет ребятам оценить свои силы и пообщаться с профессионалами IT-отрасли, а главное — дает шанс поступить в ведущие профильные вузы России.

В 2017/18 учебном году Технокубок стал олимпиадой II уровня. Каждый вуз определяет льготу самостоятельно — это может быть максимальный балл по информатике или зачисление без вступительных испытаний. Судить о льготах на текущий год можно исходя из прошлогодних привилегий: как правило, эти сведения доступны на сайтах вузов. Также информация есть здесь.

Зарегистрироваться на Технокубок можно до 12 ноября. Заочные отборочные раунды пройдут 17 сентября, 15 октября и 12 ноября. Для того чтобы попасть в финал, достаточно победить в одном из трех отборочных раундов. Для интересующихся — примеры и разборы задач прошлых лет:

Технокубок 2015/16
1-й и 2-й отборочный раунд
Финал

Технокубок 2016/17
1-й отборочный раунд
2-й отборочный раунд
3-й отборочный раунд
Финал

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

Очный финал состоится в марте 2018-го на двух московских площадках: в МГТУ им. Н. Э. Баумана и в МФТИ. Награждение победителей пройдет в офисе Mail.Ru Group.

Каждый год в Технокубке участвует около 3 тысяч школьников из России и стран СНГ. Всего за время существования олимпиады в ней приняли участие более 7 тысяч человек.

Участникам, занявшим первые три места, помимо льгот при поступлении достанутся ценные призы. Кроме того, финалисты, которые попадут в МГТУ им. Н. Э. Баумана и в МФТИ, получат привилегии при поступлении в Технопарк и Технотрек — бесплатные практико-ориентированные образовательные проекты Mail.Ru Group.

В составе оргкомитета олимпиады — председатель совета директоров и сооснователь Mail.Ru Group Дмитрий Гришин. Сопредседатели оргкомитета — ректор МФТИ Н. Н. Кудрявцев и ректор МГТУ им. Н. Э. Баумана А. А. Александров. Председатель жюри — Михаил Мирзаянов, старший преподаватель кафедры математических основ информатики и олимпиадного программирования Саратовского государственного университета, основатель и генеральный директор Codeforces, дважды серебряный призер чемпионата мира по программированию ACM-ICPC.

Зарегистрироваться, узнать подробности и задать вопросы можно на сайте олимпиады и в группе в ВКонтакте. Технокубок-2018 ждет новых героев!

Каждый год Министерство образования и науки РФ публикует перечень школьных олимпиад, дающих льготы при поступлении в вузы. С 2015 года в этот список входит и Технокубок — олимпиада по программированию под эгидой Mail.Ru Group.

Поучаствовать в Технокубке могут ученики 8—11-х классов. Олимпиада позволяет ребятам оценить свои силы и пообщаться с профессионалами IT-отрасли, а главное — дает шанс поступить в ведущие профильные вузы России.

В 2017/18 учебном году Технокубок стал олимпиадой II уровня. Каждый вуз определяет льготу самостоятельно — это может быть максимальный балл по информатике или зачисление без вступительных испытаний. Судить о льготах на текущий год можно исходя из прошлогодних привилегий: как правило, эти сведения доступны на сайтах вузов. Также информация есть здесь.

Зарегистрироваться на Технокубок можно до 12 ноября. Заочные отборочные раунды пройдут 17 сентября, 15 октября и 12 ноября. Для того чтобы попасть в финал, достаточно победить в одном из трех отборочных раундов. Для интересующихся — примеры и разборы задач прошлых лет:

Технокубок 2015/16
1-й и 2-й отборочный раунд
Финал

Технокубок 2016/17
1-й отборочный раунд
2-й отборочный раунд
3-й отборочный раунд
Финал

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

Очный финал состоится в марте 2018-го на двух московских площадках: в МГТУ им. Н. Э. Баумана и в МФТИ. Награждение победителей пройдет в офисе Mail.Ru Group.

Каждый год в Технокубке участвует около 3 тысяч школьников из России и стран СНГ. Всего за время существования олимпиады в ней приняли участие более 7 тысяч человек.

Участникам, занявшим первые три места, помимо льгот при поступлении достанутся ценные призы. Кроме того, финалисты, которые попадут в МГТУ им. Н. Э. Баумана и в МФТИ, получат привилегии при поступлении в Технопарк и Технотрек — бесплатные практико-ориентированные образовательные проекты Mail.Ru Group.

В составе оргкомитета олимпиады — председатель совета директоров и сооснователь Mail.Ru Group Дмитрий Гришин. Сопредседатели оргкомитета — ректор МФТИ Н. Н. Кудрявцев и ректор МГТУ им. Н. Э. Баумана А. А. Александров. Председатель жюри — Михаил Мирзаянов, старший преподаватель кафедры математических основ информатики и олимпиадного программирования Саратовского государственного университета, основатель и генеральный директор Codeforces, дважды серебряный призер чемпионата мира по программированию ACM-ICPC.

Зарегистрироваться, узнать подробности и задать вопросы можно на сайте олимпиады и в группе в ВКонтакте. Технокубок-2018 ждет новых героев!

Каждый год Министерство образования и науки РФ публикует перечень школьных олимпиад, дающих льготы при поступлении в вузы. С 2015 года в этот список входит и Технокубок — олимпиада по программированию под эгидой Mail.Ru Group.

Поучаствовать в Технокубке могут ученики 8—11-х классов. Олимпиада позволяет ребятам оценить свои силы и пообщаться с профессионалами IT-отрасли, а главное — дает шанс поступить в ведущие профильные вузы России.

В 2017/18 учебном году Технокубок стал олимпиадой II уровня. Каждый вуз определяет льготу самостоятельно — это может быть максимальный балл по информатике или зачисление без вступительных испытаний. Судить о льготах на текущий год можно исходя из прошлогодних привилегий: как правило, эти сведения доступны на сайтах вузов. Также информация есть здесь.

Зарегистрироваться на Технокубок можно до 12 ноября. Заочные отборочные раунды пройдут 17 сентября, 15 октября и 12 ноября. Для того чтобы попасть в финал, достаточно победить в одном из трех отборочных раундов. Для интересующихся — примеры и разборы задач прошлых лет:

Технокубок 2015/16
1-й и 2-й отборочный раунд
Финал

Технокубок 2016/17
1-й отборочный раунд
2-й отборочный раунд
3-й отборочный раунд
Финал

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

Очный финал состоится в марте 2018-го на двух московских площадках: в МГТУ им. Н. Э. Баумана и в МФТИ. Награждение победителей пройдет в офисе Mail.Ru Group.

Каждый год в Технокубке участвует около 3 тысяч школьников из России и стран СНГ. Всего за время существования олимпиады в ней приняли участие более 7 тысяч человек.

Участникам, занявшим первые три места, помимо льгот при поступлении достанутся ценные призы. Кроме того, финалисты, которые попадут в МГТУ им. Н. Э. Баумана и в МФТИ, получат привилегии при поступлении в Технопарк и Технотрек — бесплатные практико-ориентированные образовательные проекты Mail.Ru Group.

В составе оргкомитета олимпиады — председатель совета директоров и сооснователь Mail.Ru Group Дмитрий Гришин. Сопредседатели оргкомитета — ректор МФТИ Н. Н. Кудрявцев и ректор МГТУ им. Н. Э. Баумана А. А. Александров. Председатель жюри — Михаил Мирзаянов, старший преподаватель кафедры математических основ информатики и олимпиадного программирования Саратовского государственного университета, основатель и генеральный директор Codeforces, дважды серебряный призер чемпионата мира по программированию ACM-ICPC.

Зарегистрироваться, узнать подробности и задать вопросы можно на сайте олимпиады и в группе в ВКонтакте. Технокубок-2018 ждет новых героев!

Приветствую вас, коллеги. Оказывается, не все компьютерное зрение сегодня делается с использованием нейронных сетей. Хотя многие стартапы и заявляют, что у них дип лернинг везде, спешу вас разочаровать, они просто хотят хайпануть немножечко. Рассмотрим, например, задачу сегментации. В нашем слаке развернулась целая драма. Одна богатая и высокотехнологичная селфи-компания собрала датасет для сегментации селфи с помощью нейросетей (а это непростое и недешевое занятие). А другая, более бедная и не очень развитая решила, что можно подкупить людей, размечающих фотки, и спполучить базу. В общем, страсти в этих ваших Интернетах еще те. Недавно я наткнулся на статью, где без всяких нейросетей на устройстве делают очень даже хорошую сегментацию. Для сегментации от пользователя требуется дать алгоритму несколько подсказок, но с помощью dlib и opencv такие подсказки легко автоматизируются. В качестве бонуса мы так же сгладим вырезанное лицо и перенесем на какого-нибудь рандомного человека, тем самым поймем, как работают маски во всех этих снапчятах и маскарадах. В общем, классика еще жива, и если вы хотите немного окунуться в классическое компьютерное зрение на питоне, то добро пожаловать под кат.

Алгоритм

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

Далее делаем следующие шаги:

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

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

%matplotlib inline
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_style("dark")
plt.rcParams['figure.figsize'] = 16, 12
import pandas as pd
from PIL import Image
from tqdm import tqdm_notebook
from skimage import transform
import itertools as it
from sklearn.neighbors.kde import KernelDensity
import matplotlib.cm as cm
import queue
from skimage import morphology
import dlib
import cv2
from imutils import face_utils
from scipy.spatial import Delaunay

Автоматизируем штрихи

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

img_input = np.array(Image.open('./../data/input2.jpg'))[:500, 400:, :]
print(img_input.shape)
plt.imshow(img_input)

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

# инстанцируем класс для детекции лиц (рамка)
detector = dlib.get_frontal_face_detector()
# инстанцируем класс для детекции ключевых точек
predictor = dlib.shape_predictor('./../data/shape_predictor_68_face_landmarks.dat')

# конвертируем изображение в много оттенков серого
img_gray = cv2.cvtColor(img_input, cv2.COLOR_BGR2GRAY)
# вычисляем список рамок на каждое найденное лицо
rects = detector(img_gray, 0)
# вычисляем ключевые точки
shape = predictor(img_gray, rects[0])
shape = face_utils.shape_to_np(shape)

img_tmp = img_input.copy()
for x, y in shape:
    cv2.circle(img_tmp, (x, y), 1, (0, 0, 255), -1)
plt.imshow(img_tmp)

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

# оригинальная рамка
face_origin = sorted([(t.width()*t.height(), 
                       (t.left(), t.top(), t.width(), t.height())) 
                      for t in rects], 
                     key=lambda t: t[0], reverse=True)[0][1]

# коэффициенты расширения рамки
rescale = (1.3, 2.2, 1.3, 1.3)
# расширение рамки, так чтобы она не вылезла за края
(x, y, w, h) = face_origin
cx = x + w/2
cy = y + h/2
w = min(img_input.shape[1] - x, int(w/2 + rescale[2]*w/2))
h = min(img_input.shape[0] - y, int(h/2 + rescale[3]*h/2))
fx = max(0, int(x + w/2*(1 - rescale[0])))
fy = max(0, int(y + h/2*(1 - rescale[1])))
fw = min(img_input.shape[1] - fx, int(w - w/2*(1 - rescale[0])))
fh = min(img_input.shape[0] - fy, int(h - h/2*(1 - rescale[1])))

face = (fx, fy, fw, fh)

img_tmp = cv2.rectangle(img_input.copy(), (face[0], face[1]), 
                        (face[0] + face[2], face[1] + face[3]),
                        (255, 0, 0), thickness=3, lineType=8, shift=0)
img_tmp = cv2.rectangle(img_tmp, (face_origin[0], face_origin[1]), 
                        (face_origin[0] + face_origin[2], face_origin[1] + face_origin[3]),
                        (0, 255, 0), thickness=3, lineType=8, shift=0)
plt.imshow(img_tmp)

Теперь у нас имеется область, которая точно не относится к лицу — всё, что вне красной рамки. Выберем оттуда некоторое количество случайных точек и будем считать их штрихами фона. Также у нас имеются 62 точки, которые точно расположены на лице. Для упрощения задачи я выберу 5 из них: по одной на уровне глаз на краю лица, по одной на уровне рта на краю лица и одну внизу посередине подбородка. Все точки внутри этого пятиугольника будут принадлежать только лицу. Опять же для простоты будем считать, что лицо вертикально расположено на изображении и потому мы можем отразить полученный пятиугольник по оси $$, тем самым получив восьмиугольник. Все, что внутри восьмиугольника будем считать штрихом объекта.

# выбираем вышеописанные пять точек
points = [shape[0].tolist(), shape[16].tolist()]
for ix in [4, 12, 8]:
    x, y = shape[ix].tolist()
    points.append((x, y))
    points.append((x, points[0][1] + points[0][1] - y))

# я не особо в прототипе запариваюсь над производительностью
# так что вызываю триангуляцию Делоне,
# чтобы использовать ее как тест на то, что точка внутри полигона
# все это можно делать быстрее, т.к. точный тест не нужен
# для прототипа :good-enough: 
hull = Delaunay(points)
xy_fg = []
for x, y in it.product(range(img_input.shape[0]), range(img_input.shape[1])):
    if hull.find_simplex([y, x]) >= 0:
        xy_fg.append((x, y))
print('xy_fg%:', len(xy_fg)/np.prod(img_input.shape))

# вычисляем количество точек для фона
# примерно равно что бы было тому, что на лице
r = face[1]*face[3]/np.prod(img_input.shape[:2])
print(r)
k = 0.1
xy_bg_n = int(k*np.prod(img_input.shape[:2]))
print(xy_bg_n)

# накидываем случайные точки
xy_bg = zip(np.random.uniform(0, img_input.shape[0], size=xy_bg_n).astype(np.int),
            np.random.uniform(0, img_input.shape[1], size=xy_bg_n).astype(np.int))
xy_bg = list(xy_bg)
xy_bg = [(x, y) for (x, y) in xy_bg 
         if y < face[0] or y > face[0] + face[2] or x < face[1] or x > face[1] + face[3]]
print(len(xy_bg)/np.prod(img_input.shape[:2]))

img_tmp = img_input/255
for x, y in xy_fg:
    img_tmp[x, y, :] = img_tmp[x, y, :]*0.5 + np.array([1, 0, 0]) * 0.5

for x, y in xy_bg:
    img_tmp[x, y, :] = img_tmp[x, y, :]*0.5 + np.array([0, 0, 1]) * 0.5

plt.imshow(img_tmp)

Нечеткое разделение фона и объекта

Теперь у нас есть два набора данных: точки объекта $$ и точки фона $$.

points_fg = np.array([img_input[x, y, :] for (x, y) in xy_fg])
points_bg = np.array([img_input[x, y, :] for (x, y) in xy_bg])

Посмотрим на распределение цветов по RGB каналам в каждом из множеств. Первая гистограмма — для объекта, вторая — для фона.

fig, axes = plt.subplots(nrows=2, ncols=1)
sns.distplot(points_fg[:, 0], ax=axes[0], color='r')
sns.distplot(points_fg[:, 1], ax=axes[0], color='g')
sns.distplot(points_fg[:, 2], ax=axes[0], color='b')
sns.distplot(points_bg[:, 0], ax=axes[1], color='r')
sns.distplot(points_bg[:, 1], ax=axes[1], color='g')
sns.distplot(points_bg[:, 2], ax=axes[1], color='b')

Радует, что распределения отличаются. Это значит, что если мы сможем получить функции, оценивающие вероятность принадлежности точки к нужному распределению, то мы получим нечеткие маски. И оказывается такой способ есть — kernel density estimation. Для заданного набора точек, можно построить функцию оценки плотности для новой точки $$ следующим образом (для простоты пример для одномерного распределения):

где:

• $$ — параметр сглаживания
• $$ — некоторое ядро

Мы для простоты будем использовать Гауссово ядро:

Хотя для скорости Гауссово ядро не лучший выбор и если взять ядро Епанечникова, то все будет считаться быстрее. Так же я буду использовать KernelDensity из sklearn, что в итоге выльется в 5 минут скоринга. Авторы этой статьи утверждают, что замена KDE на оптимальную реализацию сокращает расчеты на устройстве до одной секунды.

# инстанцируем классы KDE для объекта и фона
kde_fg = KernelDensity(kernel='gaussian', 
                       bandwidth=1, 
                       algorithm='kd_tree', 
                       leaf_size=100).fit(points_fg)
kde_bg = KernelDensity(kernel='gaussian', 
                       bandwidth=1, 
                       algorithm='kd_tree', 
                       leaf_size=100).fit(points_bg)

# инициализируем и вычисляем маски
score_kde_fg = np.zeros(img_input.shape[:2])
score_kde_bg = np.zeros(img_input.shape[:2])
likelihood_fg = np.zeros(img_input.shape[:2])
coodinates = it.product(range(score_kde_fg.shape[0]), 
                        range(score_kde_fg.shape[1]))
for x, y in tqdm_notebook(coodinates, 
                          total=np.prod(score_kde_fg.shape)):
    score_kde_fg[x, y] = np.exp(kde_fg.score(img_input[x, y, :].reshape(1, -1)))
    score_kde_bg[x, y] = np.exp(kde_bg.score(img_input[x, y, :].reshape(1, -1)))
    n = score_kde_fg[x, y] + score_kde_bg[x, y]
    if n == 0:
        n = 1
    likelihood_fg[x, y] = score_kde_fg[x, y]/n

В итоге у нас есть несколько масок:

• score_kde_fg — оценка вероятности быть точкой объекта $$
• score_kde_bg — оценка вероятности быть точкой объекта $$
• likelihood_fg — нормализированная вероятность быть точкой объекта $$
• 1 - likelihood_fg нормализированная вероятность быть точкой фона $$

Посмотрим на следующие распределения.

Распределение значений score_kde_fg

sns.distplot(score_kde_fg.flatten())
plt.show()

Распределение значений score_kde_bg

sns.distplot(score_kde_bg.flatten())
plt.show()

Распределение значений likelihood_fg:

sns.distplot(likelihood_fg.flatten())
plt.show()

Вселяет надежду то, что на $$ есть два пика, и количество точек, принадлежащих лицу, явно не меньше, чем фоновых точек. Нарисуем полученные маски.

маска score_kde_fg

plt.matshow(score_kde_fg, cmap=cm.bwr)
plt.show()

маска score_kde_bg

plt.matshow(score_kde_bg, cmap=cm.bwr)
plt.show()

plt.matshow(likelihood_fg, cmap=cm.bwr)
plt.show()

маска 1 - likelihood_fg

plt.matshow(1 - likelihood_fg, cmap=cm.bwr)
plt.show()

К сожалению, часть косяка двери получилась частью лица. Хорошо, что косяк далеко от лица. Этим-то свойством мы и воспользуемся в следущей части.

Бинарная маска объекта

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

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

def dijkstra(start_points, w):
    d = np.zeros(w.shape) + np.infty
    v = np.zeros(w.shape, dtype=np.bool)
    q = queue.PriorityQueue()
    for x, y in start_points:
        d[x, y] = 0
        q.put((d[x, y], (x, y)))

    for x, y in it.product(range(w.shape[0]), range(w.shape[1])):
        if np.isinf(d[x, y]):
            q.put((d[x, y], (x, y)))

    while not q.empty():
        _, p = q.get()
        if v[p]:
            continue

        neighbourhood = []
        if p[0] - 1 >= 0:
            neighbourhood.append((p[0] - 1, p[1]))
        if p[0] + 1 <= w.shape[0] - 1:
            neighbourhood.append((p[0] + 1, p[1]))
        if p[1] - 1 >= 0:
            neighbourhood.append((p[0], p[1] - 1))
        if p[1] + 1 < w.shape[1]:
            neighbourhood.append((p[0], p[1] + 1))

        for x, y in neighbourhood:
            # тут вычисляется расстояние
            d_tmp = d[p] + np.abs(w[x, y] - w[p])
            if d[x, y] > d_tmp:
                d[x, y] = d_tmp
                q.put((d[x, y], (x, y)))

        v[p] = True

    return d

# вызываем алгоритм для двух масок
d_fg = dijkstra(xy_fg, likelihood_fg)
d_bg = dijkstra(xy_bg, 1 - likelihood_fg)

новая нечеткая маска объекта

plt.matshow(d_fg, cmap=cm.bwr)
plt.show()

новая нечеткая маска фона

plt.matshow(d_bg, cmap=cm.bwr)
plt.show()

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

margin = 0.0
mask = (d_fg < (d_bg + margin)).astype(np.uint8)

plt.matshow(mask)
plt.show()

Можно отправить себя в космос.

img_fg = img_input/255.0
img_bg = (np.array(Image.open('./../data/background.jpg'))/255.0)[:800, :800, :]

x = int(img_bg.shape[0] - img_fg.shape[0])
y = int(img_bg.shape[1]/2 - img_fg.shape[1]/2)

img_bg_fg = img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :]
mask_3d = np.dstack([mask, mask, mask])
img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :] = mask_3d*img_fg + (1 - mask_3d)*img_bg_fg

plt.imshow(img_bg)

Сглаживание маски

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

Допустим, у нас есть структурный элемент (СЭ) типа "диск" — бинарная маска диска.

• эрозия: прикладываем к каждой точке объекта на оригинальном изображении СЭ так, чтобы совпадал центр СЭ и точка на изображении; если СЭ полностью принадлежит в объекту, то такая точка объекта остается; получается, что удаляются детали, которые меньше чем СЭ, и объект "худеет"; в примере из синего квадрата сделали голубой
• наращивание (dilation): на каждую точку объекта накладывается СЭ, и недостающие точки дорисовываются; таким образом закрашиваются дырки меньшие чем СЭ, а объект в целом "толстеет"; на примере из синего квадрата сделали голубой, углы получились закругленные
• размыкание (opening): сначала эрозия, потом наращивание тем же СЭ
• замыкание (closing): сначала наращивание, потом эрозия тем же СЭ

Мы воспользуемся размыканием, что сначала удалит "волосатость" по краям, а потом вернет первоначальный размер (объект "похудеет" после эрозии).

mask = morphology.opening(mask, morphology.disk(11))
plt.imshow(mask)

После применения такой маски результат станет поприятнее:

img_fg = img_input/255.0
img_bg = (np.array(Image.open('./../data/background.jpg'))/255.0)[:800, :800, :]

x = int(img_bg.shape[0] - img_fg.shape[0])
y = int(img_bg.shape[1]/2 - img_fg.shape[1]/2)

img_bg_fg = img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :]
mask_3d = np.dstack([mask, mask, mask])
img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :] = \
    mask_3d*img_fg + (1 - mask_3d)*img_bg_fg

plt.imshow(img_bg)

Накладываем маску

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

Подопытный экземпляр

img_target = np.array(Image.open('./../data/target.jpg'))
img_target = (transform.rescale(img_target, scale=0.5, mode='constant')*255).astype(np.uint8)
print(img_target.shape)
plt.imshow(img_target)

Найдем на подопытном все 62 колючевые точки лица, напомню, что они будут в том же порядке как и на любом другом лице.

img_gray = cv2.cvtColor(img_target, cv2.COLOR_BGR2GRAY)
rects_target = detector(img_gray, 0)
shape_target = predictor(img_gray, rects_target[0])
shape_target = face_utils.shape_to_np(shape_target)

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

Данное уравнение легко решается с помощью псевдообратной матрицы:

Так и сделаем:

# добавим справа к матрицам колонку единиц,
# иначе будет только масштабирование и поворот, без переноса
X = np.hstack((shape, np.ones(shape.shape[0])[:, np.newaxis]))
Y = np.hstack((shape_target, np.ones(shape_target.shape[0])[:, np.newaxis]))
# учим оператор
A = np.dot(np.dot(np.linalg.inv(np.dot(X.T, X)), X.T), Y)

# выбираем точки лица по искомой маске
X = np.array([(y, x, 1) for (x, y) in 
    it.product(range(mask.shape[0]), 
                   range(mask.shape[1])) if mask[x, y] == 1.0])
# вычисляем новые координаты маски на целевом изображении
Y = np.dot(X, A).astype(np.int)

img_tmp = img_target.copy()
for y, x, _ in Y:
    if x < 0 or x >= img_target.shape[0] or y < 0 or y >= img_target.shape[1]:
        continue
    img_tmp[x, y, :] = np.array([0, 0, 0])

plt.imshow(img_tmp)

img_trans = img_target.copy().astype(np.uint8)
points_face = {}
for ix in range(X.shape[0]):
    y1, x1, _ = X[ix, :]
    y2, x2, _ = Y[ix, :]
    if x2 < 0 or x2 >= img_target.shape[0] or 
       y2 < 0 or y2 >= img_target.shape[1]:
        continue
    points_face[(x2, y2)] = img_input[x1, y1, :]

for (x, y), c in points_face.items():
    img_trans[x, y, :] = c
plt.imshow(img_trans)

Заключение

В качестве домашней работы вы можоте самостоятельно сделать следующие улучшения:

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

Ноутбук с исходниками находится тут. Приятного времяпрепровождения.

Как обычно спс bauchgefuehl за редактуру.

Приветствую вас, коллеги. Оказывается, не все компьютерное зрение сегодня делается с использованием нейронных сетей. Хотя многие стартапы и заявляют, что у них дип лернинг везде, спешу вас разочаровать, они просто хотят хайпануть немножечко. Рассмотрим, например, задачу сегментации. В нашем слаке развернулась целая драма. Одна богатая и высокотехнологичная селфи-компания собрала датасет для сегментации селфи с помощью нейросетей (а это непростое и недешевое занятие). А другая, более бедная и не очень развитая решила, что можно подкупить людей, размечающих фотки, и спполучить базу. В общем, страсти в этих ваших Интернетах еще те. Недавно я наткнулся на статью, где без всяких нейросетей на устройстве делают очень даже хорошую сегментацию. Для сегментации от пользователя требуется дать алгоритму несколько подсказок, но с помощью dlib и opencv такие подсказки легко автоматизируются. В качестве бонуса мы так же сгладим вырезанное лицо и перенесем на какого-нибудь рандомного человека, тем самым поймем, как работают маски во всех этих снапчятах и маскарадах. В общем, классика еще жива, и если вы хотите немного окунуться в классическое компьютерное зрение на питоне, то добро пожаловать под кат.

Алгоритм

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

Далее делаем следующие шаги:

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

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

%matplotlib inline
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_style("dark")
plt.rcParams['figure.figsize'] = 16, 12
import pandas as pd
from PIL import Image
from tqdm import tqdm_notebook
from skimage import transform
import itertools as it
from sklearn.neighbors.kde import KernelDensity
import matplotlib.cm as cm
import queue
from skimage import morphology
import dlib
import cv2
from imutils import face_utils
from scipy.spatial import Delaunay

Автоматизируем штрихи

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

img_input = np.array(Image.open('./../data/input2.jpg'))[:500, 400:, :]
print(img_input.shape)
plt.imshow(img_input)

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

# инстанцируем класс для детекции лиц (рамка)
detector = dlib.get_frontal_face_detector()
# инстанцируем класс для детекции ключевых точек
predictor = dlib.shape_predictor('./../data/shape_predictor_68_face_landmarks.dat')

# конвертируем изображение в много оттенков серого
img_gray = cv2.cvtColor(img_input, cv2.COLOR_BGR2GRAY)
# вычисляем список рамок на каждое найденное лицо
rects = detector(img_gray, 0)
# вычисляем ключевые точки
shape = predictor(img_gray, rects[0])
shape = face_utils.shape_to_np(shape)

img_tmp = img_input.copy()
for x, y in shape:
    cv2.circle(img_tmp, (x, y), 1, (0, 0, 255), -1)
plt.imshow(img_tmp)

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

# оригинальная рамка
face_origin = sorted([(t.width()*t.height(), 
                       (t.left(), t.top(), t.width(), t.height())) 
                      for t in rects], 
                     key=lambda t: t[0], reverse=True)[0][1]

# коэффициенты расширения рамки
rescale = (1.3, 2.2, 1.3, 1.3)
# расширение рамки, так чтобы она не вылезла за края
(x, y, w, h) = face_origin
cx = x + w/2
cy = y + h/2
w = min(img_input.shape[1] - x, int(w/2 + rescale[2]*w/2))
h = min(img_input.shape[0] - y, int(h/2 + rescale[3]*h/2))
fx = max(0, int(x + w/2*(1 - rescale[0])))
fy = max(0, int(y + h/2*(1 - rescale[1])))
fw = min(img_input.shape[1] - fx, int(w - w/2*(1 - rescale[0])))
fh = min(img_input.shape[0] - fy, int(h - h/2*(1 - rescale[1])))

face = (fx, fy, fw, fh)

img_tmp = cv2.rectangle(img_input.copy(), (face[0], face[1]), 
                        (face[0] + face[2], face[1] + face[3]),
                        (255, 0, 0), thickness=3, lineType=8, shift=0)
img_tmp = cv2.rectangle(img_tmp, (face_origin[0], face_origin[1]), 
                        (face_origin[0] + face_origin[2], face_origin[1] + face_origin[3]),
                        (0, 255, 0), thickness=3, lineType=8, shift=0)
plt.imshow(img_tmp)

Теперь у нас имеется область, которая точно не относится к лицу — всё, что вне красной рамки. Выберем оттуда некоторое количество случайных точек и будем считать их штрихами фона. Также у нас имеются 62 точки, которые точно расположены на лице. Для упрощения задачи я выберу 5 из них: по одной на уровне глаз на краю лица, по одной на уровне рта на краю лица и одну внизу посередине подбородка. Все точки внутри этого пятиугольника будут принадлежать только лицу. Опять же для простоты будем считать, что лицо вертикально расположено на изображении и потому мы можем отразить полученный пятиугольник по оси $$, тем самым получив восьмиугольник. Все, что внутри восьмиугольника будем считать штрихом объекта.

# выбираем вышеописанные пять точек
points = [shape[0].tolist(), shape[16].tolist()]
for ix in [4, 12, 8]:
    x, y = shape[ix].tolist()
    points.append((x, y))
    points.append((x, points[0][1] + points[0][1] - y))

# я не особо в прототипе запариваюсь над производительностью
# так что вызываю триангуляцию Делоне,
# чтобы использовать ее как тест на то, что точка внутри полигона
# все это можно делать быстрее, т.к. точный тест не нужен
# для прототипа :good-enough: 
hull = Delaunay(points)
xy_fg = []
for x, y in it.product(range(img_input.shape[0]), range(img_input.shape[1])):
    if hull.find_simplex([y, x]) >= 0:
        xy_fg.append((x, y))
print('xy_fg%:', len(xy_fg)/np.prod(img_input.shape))

# вычисляем количество точек для фона
# примерно равно что бы было тому, что на лице
r = face[1]*face[3]/np.prod(img_input.shape[:2])
print(r)
k = 0.1
xy_bg_n = int(k*np.prod(img_input.shape[:2]))
print(xy_bg_n)

# накидываем случайные точки
xy_bg = zip(np.random.uniform(0, img_input.shape[0], size=xy_bg_n).astype(np.int),
            np.random.uniform(0, img_input.shape[1], size=xy_bg_n).astype(np.int))
xy_bg = list(xy_bg)
xy_bg = [(x, y) for (x, y) in xy_bg 
         if y < face[0] or y > face[0] + face[2] or x < face[1] or x > face[1] + face[3]]
print(len(xy_bg)/np.prod(img_input.shape[:2]))

img_tmp = img_input/255
for x, y in xy_fg:
    img_tmp[x, y, :] = img_tmp[x, y, :]*0.5 + np.array([1, 0, 0]) * 0.5

for x, y in xy_bg:
    img_tmp[x, y, :] = img_tmp[x, y, :]*0.5 + np.array([0, 0, 1]) * 0.5

plt.imshow(img_tmp)

Нечеткое разделение фона и объекта

Теперь у нас есть два набора данных: точки объекта $$ и точки фона $$.

points_fg = np.array([img_input[x, y, :] for (x, y) in xy_fg])
points_bg = np.array([img_input[x, y, :] for (x, y) in xy_bg])

Посмотрим на распределение цветов по RGB каналам в каждом из множеств. Первая гистограмма — для объекта, вторая — для фона.

fig, axes = plt.subplots(nrows=2, ncols=1)
sns.distplot(points_fg[:, 0], ax=axes[0], color='r')
sns.distplot(points_fg[:, 1], ax=axes[0], color='g')
sns.distplot(points_fg[:, 2], ax=axes[0], color='b')
sns.distplot(points_bg[:, 0], ax=axes[1], color='r')
sns.distplot(points_bg[:, 1], ax=axes[1], color='g')
sns.distplot(points_bg[:, 2], ax=axes[1], color='b')

Радует, что распределения отличаются. Это значит, что если мы сможем получить функции, оценивающие вероятность принадлежности точки к нужному распределению, то мы получим нечеткие маски. И оказывается такой способ есть — kernel density estimation. Для заданного набора точек, можно построить функцию оценки плотности для новой точки $$ следующим образом (для простоты пример для одномерного распределения):

где:

• $$ — параметр сглаживания
• $$ — некоторое ядро

Мы для простоты будем использовать Гауссово ядро:

Хотя для скорости Гауссово ядро не лучший выбор и если взять ядро Епанечникова, то все будет считаться быстрее. Так же я буду использовать KernelDensity из sklearn, что в итоге выльется в 5 минут скоринга. Авторы этой статьи утверждают, что замена KDE на оптимальную реализацию сокращает расчеты на устройстве до одной секунды.

# инстанцируем классы KDE для объекта и фона
kde_fg = KernelDensity(kernel='gaussian', 
                       bandwidth=1, 
                       algorithm='kd_tree', 
                       leaf_size=100).fit(points_fg)
kde_bg = KernelDensity(kernel='gaussian', 
                       bandwidth=1, 
                       algorithm='kd_tree', 
                       leaf_size=100).fit(points_bg)

# инициализируем и вычисляем маски
score_kde_fg = np.zeros(img_input.shape[:2])
score_kde_bg = np.zeros(img_input.shape[:2])
likelihood_fg = np.zeros(img_input.shape[:2])
coodinates = it.product(range(score_kde_fg.shape[0]), 
                        range(score_kde_fg.shape[1]))
for x, y in tqdm_notebook(coodinates, 
                          total=np.prod(score_kde_fg.shape)):
    score_kde_fg[x, y] = np.exp(kde_fg.score(img_input[x, y, :].reshape(1, -1)))
    score_kde_bg[x, y] = np.exp(kde_bg.score(img_input[x, y, :].reshape(1, -1)))
    n = score_kde_fg[x, y] + score_kde_bg[x, y]
    if n == 0:
        n = 1
    likelihood_fg[x, y] = score_kde_fg[x, y]/n

В итоге у нас есть несколько масок:

• score_kde_fg — оценка вероятности быть точкой объекта $$
• score_kde_bg — оценка вероятности быть точкой объекта $$
• likelihood_fg — нормализированная вероятность быть точкой объекта $$
• 1 - likelihood_fg нормализированная вероятность быть точкой фона $$

Посмотрим на следующие распределения.

Распределение значений score_kde_fg

sns.distplot(score_kde_fg.flatten())
plt.show()

Распределение значений score_kde_bg

sns.distplot(score_kde_bg.flatten())
plt.show()

Распределение значений likelihood_fg:

sns.distplot(likelihood_fg.flatten())
plt.show()

Вселяет надежду то, что на $$ есть два пика, и количество точек, принадлежащих лицу, явно не меньше, чем фоновых точек. Нарисуем полученные маски.

маска score_kde_fg

plt.matshow(score_kde_fg, cmap=cm.bwr)
plt.show()

маска score_kde_bg

plt.matshow(score_kde_bg, cmap=cm.bwr)
plt.show()

plt.matshow(likelihood_fg, cmap=cm.bwr)
plt.show()

маска 1 - likelihood_fg

plt.matshow(1 - likelihood_fg, cmap=cm.bwr)
plt.show()

К сожалению, часть косяка двери получилась частью лица. Хорошо, что косяк далеко от лица. Этим-то свойством мы и воспользуемся в следущей части.

Бинарная маска объекта

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

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

def dijkstra(start_points, w):
    d = np.zeros(w.shape) + np.infty
    v = np.zeros(w.shape, dtype=np.bool)
    q = queue.PriorityQueue()
    for x, y in start_points:
        d[x, y] = 0
        q.put((d[x, y], (x, y)))

    for x, y in it.product(range(w.shape[0]), range(w.shape[1])):
        if np.isinf(d[x, y]):
            q.put((d[x, y], (x, y)))

    while not q.empty():
        _, p = q.get()
        if v[p]:
            continue

        neighbourhood = []
        if p[0] - 1 >= 0:
            neighbourhood.append((p[0] - 1, p[1]))
        if p[0] + 1 <= w.shape[0] - 1:
            neighbourhood.append((p[0] + 1, p[1]))
        if p[1] - 1 >= 0:
            neighbourhood.append((p[0], p[1] - 1))
        if p[1] + 1 < w.shape[1]:
            neighbourhood.append((p[0], p[1] + 1))

        for x, y in neighbourhood:
            # тут вычисляется расстояние
            d_tmp = d[p] + np.abs(w[x, y] - w[p])
            if d[x, y] > d_tmp:
                d[x, y] = d_tmp
                q.put((d[x, y], (x, y)))

        v[p] = True

    return d

# вызываем алгоритм для двух масок
d_fg = dijkstra(xy_fg, likelihood_fg)
d_bg = dijkstra(xy_bg, 1 - likelihood_fg)

новая нечеткая маска объекта

plt.matshow(d_fg, cmap=cm.bwr)
plt.show()

новая нечеткая маска фона

plt.matshow(d_bg, cmap=cm.bwr)
plt.show()

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

margin = 0.0
mask = (d_fg < (d_bg + margin)).astype(np.uint8)

plt.matshow(mask)
plt.show()

Можно отправить себя в космос.

img_fg = img_input/255.0
img_bg = (np.array(Image.open('./../data/background.jpg'))/255.0)[:800, :800, :]

x = int(img_bg.shape[0] - img_fg.shape[0])
y = int(img_bg.shape[1]/2 - img_fg.shape[1]/2)

img_bg_fg = img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :]
mask_3d = np.dstack([mask, mask, mask])
img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :] = mask_3d*img_fg + (1 - mask_3d)*img_bg_fg

plt.imshow(img_bg)

Сглаживание маски

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

Допустим, у нас есть структурный элемент (СЭ) типа "диск" — бинарная маска диска.

• эрозия: прикладываем к каждой точке объекта на оригинальном изображении СЭ так, чтобы совпадал центр СЭ и точка на изображении; если СЭ полностью принадлежит в объекту, то такая точка объекта остается; получается, что удаляются детали, которые меньше чем СЭ, и объект "худеет"; в примере из синего квадрата сделали голубой
• наращивание (dilation): на каждую точку объекта накладывается СЭ, и недостающие точки дорисовываются; таким образом закрашиваются дырки меньшие чем СЭ, а объект в целом "толстеет"; на примере из синего квадрата сделали голубой, углы получились закругленные
• размыкание (opening): сначала эрозия, потом наращивание тем же СЭ
• замыкание (closing): сначала наращивание, потом эрозия тем же СЭ

Мы воспользуемся размыканием, что сначала удалит "волосатость" по краям, а потом вернет первоначальный размер (объект "похудеет" после эрозии).

mask = morphology.opening(mask, morphology.disk(11))
plt.imshow(mask)

После применения такой маски результат станет поприятнее:

img_fg = img_input/255.0
img_bg = (np.array(Image.open('./../data/background.jpg'))/255.0)[:800, :800, :]

x = int(img_bg.shape[0] - img_fg.shape[0])
y = int(img_bg.shape[1]/2 - img_fg.shape[1]/2)

img_bg_fg = img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :]
mask_3d = np.dstack([mask, mask, mask])
img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :] = \
    mask_3d*img_fg + (1 - mask_3d)*img_bg_fg

plt.imshow(img_bg)

Накладываем маску

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

Подопытный экземпляр

img_target = np.array(Image.open('./../data/target.jpg'))
img_target = (transform.rescale(img_target, scale=0.5, mode='constant')*255).astype(np.uint8)
print(img_target.shape)
plt.imshow(img_target)

Найдем на подопытном все 62 колючевые точки лица, напомню, что они будут в том же порядке как и на любом другом лице.

img_gray = cv2.cvtColor(img_target, cv2.COLOR_BGR2GRAY)
rects_target = detector(img_gray, 0)
shape_target = predictor(img_gray, rects_target[0])
shape_target = face_utils.shape_to_np(shape_target)

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

Данное уравнение легко решается с помощью псевдообратной матрицы:

Так и сделаем:

# добавим справа к матрицам колонку единиц,
# иначе будет только масштабирование и поворот, без переноса
X = np.hstack((shape, np.ones(shape.shape[0])[:, np.newaxis]))
Y = np.hstack((shape_target, np.ones(shape_target.shape[0])[:, np.newaxis]))
# учим оператор
A = np.dot(np.dot(np.linalg.inv(np.dot(X.T, X)), X.T), Y)

# выбираем точки лица по искомой маске
X = np.array([(y, x, 1) for (x, y) in 
    it.product(range(mask.shape[0]), 
                   range(mask.shape[1])) if mask[x, y] == 1.0])
# вычисляем новые координаты маски на целевом изображении
Y = np.dot(X, A).astype(np.int)

img_tmp = img_target.copy()
for y, x, _ in Y:
    if x < 0 or x >= img_target.shape[0] or y < 0 or y >= img_target.shape[1]:
        continue
    img_tmp[x, y, :] = np.array([0, 0, 0])

plt.imshow(img_tmp)

img_trans = img_target.copy().astype(np.uint8)
points_face = {}
for ix in range(X.shape[0]):
    y1, x1, _ = X[ix, :]
    y2, x2, _ = Y[ix, :]
    if x2 < 0 or x2 >= img_target.shape[0] or 
       y2 < 0 or y2 >= img_target.shape[1]:
        continue
    points_face[(x2, y2)] = img_input[x1, y1, :]

for (x, y), c in points_face.items():
    img_trans[x, y, :] = c
plt.imshow(img_trans)

Заключение

В качестве домашней работы вы можоте самостоятельно сделать следующие улучшения:

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

Ноутбук с исходниками находится тут. Приятного времяпрепровождения.

Как обычно спс bauchgefuehl за редактуру.

Приветствую вас, коллеги. Оказывается, не все компьютерное зрение сегодня делается с использованием нейронных сетей. Хотя многие стартапы и заявляют, что у них дип лернинг везде, спешу вас разочаровать, они просто хотят хайпануть немножечко. Рассмотрим, например, задачу сегментации. В нашем слаке развернулась целая драма. Одна богатая и высокотехнологичная селфи-компания собрала датасет для сегментации селфи с помощью нейросетей (а это непростое и недешевое занятие). А другая, более бедная и не очень развитая решила, что можно подкупить людей, размечающих фотки, и спполучить базу. В общем, страсти в этих ваших Интернетах еще те. Недавно я наткнулся на статью, где без всяких нейросетей на устройстве делают очень даже хорошую сегментацию. Для сегментации от пользователя требуется дать алгоритму несколько подсказок, но с помощью dlib и opencv такие подсказки легко автоматизируются. В качестве бонуса мы так же сгладим вырезанное лицо и перенесем на какого-нибудь рандомного человека, тем самым поймем, как работают маски во всех этих снапчятах и маскарадах. В общем, классика еще жива, и если вы хотите немного окунуться в классическое компьютерное зрение на питоне, то добро пожаловать под кат.

Алгоритм

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

Далее делаем следующие шаги:

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

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

%matplotlib inline
import matplotlib
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
sns.set_style("dark")
plt.rcParams['figure.figsize'] = 16, 12
import pandas as pd
from PIL import Image
from tqdm import tqdm_notebook
from skimage import transform
import itertools as it
from sklearn.neighbors.kde import KernelDensity
import matplotlib.cm as cm
import queue
from skimage import morphology
import dlib
import cv2
from imutils import face_utils
from scipy.spatial import Delaunay

Автоматизируем штрихи

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

img_input = np.array(Image.open('./../data/input2.jpg'))[:500, 400:, :]
print(img_input.shape)
plt.imshow(img_input)

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

# инстанцируем класс для детекции лиц (рамка)
detector = dlib.get_frontal_face_detector()
# инстанцируем класс для детекции ключевых точек
predictor = dlib.shape_predictor('./../data/shape_predictor_68_face_landmarks.dat')

# конвертируем изображение в много оттенков серого
img_gray = cv2.cvtColor(img_input, cv2.COLOR_BGR2GRAY)
# вычисляем список рамок на каждое найденное лицо
rects = detector(img_gray, 0)
# вычисляем ключевые точки
shape = predictor(img_gray, rects[0])
shape = face_utils.shape_to_np(shape)

img_tmp = img_input.copy()
for x, y in shape:
    cv2.circle(img_tmp, (x, y), 1, (0, 0, 255), -1)
plt.imshow(img_tmp)

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

# оригинальная рамка
face_origin = sorted([(t.width()*t.height(), 
                       (t.left(), t.top(), t.width(), t.height())) 
                      for t in rects], 
                     key=lambda t: t[0], reverse=True)[0][1]

# коэффициенты расширения рамки
rescale = (1.3, 2.2, 1.3, 1.3)
# расширение рамки, так чтобы она не вылезла за края
(x, y, w, h) = face_origin
cx = x + w/2
cy = y + h/2
w = min(img_input.shape[1] - x, int(w/2 + rescale[2]*w/2))
h = min(img_input.shape[0] - y, int(h/2 + rescale[3]*h/2))
fx = max(0, int(x + w/2*(1 - rescale[0])))
fy = max(0, int(y + h/2*(1 - rescale[1])))
fw = min(img_input.shape[1] - fx, int(w - w/2*(1 - rescale[0])))
fh = min(img_input.shape[0] - fy, int(h - h/2*(1 - rescale[1])))

face = (fx, fy, fw, fh)

img_tmp = cv2.rectangle(img_input.copy(), (face[0], face[1]), 
                        (face[0] + face[2], face[1] + face[3]),
                        (255, 0, 0), thickness=3, lineType=8, shift=0)
img_tmp = cv2.rectangle(img_tmp, (face_origin[0], face_origin[1]), 
                        (face_origin[0] + face_origin[2], face_origin[1] + face_origin[3]),
                        (0, 255, 0), thickness=3, lineType=8, shift=0)
plt.imshow(img_tmp)

Теперь у нас имеется область, которая точно не относится к лицу — всё, что вне красной рамки. Выберем оттуда некоторое количество случайных точек и будем считать их штрихами фона. Также у нас имеются 62 точки, которые точно расположены на лице. Для упрощения задачи я выберу 5 из них: по одной на уровне глаз на краю лица, по одной на уровне рта на краю лица и одну внизу посередине подбородка. Все точки внутри этого пятиугольника будут принадлежать только лицу. Опять же для простоты будем считать, что лицо вертикально расположено на изображении и потому мы можем отразить полученный пятиугольник по оси $$, тем самым получив восьмиугольник. Все, что внутри восьмиугольника будем считать штрихом объекта.

# выбираем вышеописанные пять точек
points = [shape[0].tolist(), shape[16].tolist()]
for ix in [4, 12, 8]:
    x, y = shape[ix].tolist()
    points.append((x, y))
    points.append((x, points[0][1] + points[0][1] - y))

# я не особо в прототипе запариваюсь над производительностью
# так что вызываю триангуляцию Делоне,
# чтобы использовать ее как тест на то, что точка внутри полигона
# все это можно делать быстрее, т.к. точный тест не нужен
# для прототипа :good-enough: 
hull = Delaunay(points)
xy_fg = []
for x, y in it.product(range(img_input.shape[0]), range(img_input.shape[1])):
    if hull.find_simplex([y, x]) >= 0:
        xy_fg.append((x, y))
print('xy_fg%:', len(xy_fg)/np.prod(img_input.shape))

# вычисляем количество точек для фона
# примерно равно что бы было тому, что на лице
r = face[1]*face[3]/np.prod(img_input.shape[:2])
print(r)
k = 0.1
xy_bg_n = int(k*np.prod(img_input.shape[:2]))
print(xy_bg_n)

# накидываем случайные точки
xy_bg = zip(np.random.uniform(0, img_input.shape[0], size=xy_bg_n).astype(np.int),
            np.random.uniform(0, img_input.shape[1], size=xy_bg_n).astype(np.int))
xy_bg = list(xy_bg)
xy_bg = [(x, y) for (x, y) in xy_bg 
         if y < face[0] or y > face[0] + face[2] or x < face[1] or x > face[1] + face[3]]
print(len(xy_bg)/np.prod(img_input.shape[:2]))

img_tmp = img_input/255
for x, y in xy_fg:
    img_tmp[x, y, :] = img_tmp[x, y, :]*0.5 + np.array([1, 0, 0]) * 0.5

for x, y in xy_bg:
    img_tmp[x, y, :] = img_tmp[x, y, :]*0.5 + np.array([0, 0, 1]) * 0.5

plt.imshow(img_tmp)

Нечеткое разделение фона и объекта

Теперь у нас есть два набора данных: точки объекта $$ и точки фона $$.

points_fg = np.array([img_input[x, y, :] for (x, y) in xy_fg])
points_bg = np.array([img_input[x, y, :] for (x, y) in xy_bg])

Посмотрим на распределение цветов по RGB каналам в каждом из множеств. Первая гистограмма — для объекта, вторая — для фона.

fig, axes = plt.subplots(nrows=2, ncols=1)
sns.distplot(points_fg[:, 0], ax=axes[0], color='r')
sns.distplot(points_fg[:, 1], ax=axes[0], color='g')
sns.distplot(points_fg[:, 2], ax=axes[0], color='b')
sns.distplot(points_bg[:, 0], ax=axes[1], color='r')
sns.distplot(points_bg[:, 1], ax=axes[1], color='g')
sns.distplot(points_bg[:, 2], ax=axes[1], color='b')

Радует, что распределения отличаются. Это значит, что если мы сможем получить функции, оценивающие вероятность принадлежности точки к нужному распределению, то мы получим нечеткие маски. И оказывается такой способ есть — kernel density estimation. Для заданного набора точек, можно построить функцию оценки плотности для новой точки $$ следующим образом (для простоты пример для одномерного распределения):

где:

• $$ — параметр сглаживания
• $$ — некоторое ядро

Мы для простоты будем использовать Гауссово ядро:

Хотя для скорости Гауссово ядро не лучший выбор и если взять ядро Епанечникова, то все будет считаться быстрее. Так же я буду использовать KernelDensity из sklearn, что в итоге выльется в 5 минут скоринга. Авторы этой статьи утверждают, что замена KDE на оптимальную реализацию сокращает расчеты на устройстве до одной секунды.

# инстанцируем классы KDE для объекта и фона
kde_fg = KernelDensity(kernel='gaussian', 
                       bandwidth=1, 
                       algorithm='kd_tree', 
                       leaf_size=100).fit(points_fg)
kde_bg = KernelDensity(kernel='gaussian', 
                       bandwidth=1, 
                       algorithm='kd_tree', 
                       leaf_size=100).fit(points_bg)

# инициализируем и вычисляем маски
score_kde_fg = np.zeros(img_input.shape[:2])
score_kde_bg = np.zeros(img_input.shape[:2])
likelihood_fg = np.zeros(img_input.shape[:2])
coodinates = it.product(range(score_kde_fg.shape[0]), 
                        range(score_kde_fg.shape[1]))
for x, y in tqdm_notebook(coodinates, 
                          total=np.prod(score_kde_fg.shape)):
    score_kde_fg[x, y] = np.exp(kde_fg.score(img_input[x, y, :].reshape(1, -1)))
    score_kde_bg[x, y] = np.exp(kde_bg.score(img_input[x, y, :].reshape(1, -1)))
    n = score_kde_fg[x, y] + score_kde_bg[x, y]
    if n == 0:
        n = 1
    likelihood_fg[x, y] = score_kde_fg[x, y]/n

В итоге у нас есть несколько масок:

• score_kde_fg — оценка вероятности быть точкой объекта $$
• score_kde_bg — оценка вероятности быть точкой объекта $$
• likelihood_fg — нормализированная вероятность быть точкой объекта $$
• 1 - likelihood_fg нормализированная вероятность быть точкой фона $$

Посмотрим на следующие распределения.

Распределение значений score_kde_fg

sns.distplot(score_kde_fg.flatten())
plt.show()

Распределение значений score_kde_bg

sns.distplot(score_kde_bg.flatten())
plt.show()

Распределение значений likelihood_fg:

sns.distplot(likelihood_fg.flatten())
plt.show()

Вселяет надежду то, что на $$ есть два пика, и количество точек, принадлежащих лицу, явно не меньше, чем фоновых точек. Нарисуем полученные маски.

маска score_kde_fg

plt.matshow(score_kde_fg, cmap=cm.bwr)
plt.show()

маска score_kde_bg

plt.matshow(score_kde_bg, cmap=cm.bwr)
plt.show()

plt.matshow(likelihood_fg, cmap=cm.bwr)
plt.show()

маска 1 - likelihood_fg

plt.matshow(1 - likelihood_fg, cmap=cm.bwr)
plt.show()

К сожалению, часть косяка двери получилась частью лица. Хорошо, что косяк далеко от лица. Этим-то свойством мы и воспользуемся в следущей части.

Бинарная маска объекта

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

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

def dijkstra(start_points, w):
    d = np.zeros(w.shape) + np.infty
    v = np.zeros(w.shape, dtype=np.bool)
    q = queue.PriorityQueue()
    for x, y in start_points:
        d[x, y] = 0
        q.put((d[x, y], (x, y)))

    for x, y in it.product(range(w.shape[0]), range(w.shape[1])):
        if np.isinf(d[x, y]):
            q.put((d[x, y], (x, y)))

    while not q.empty():
        _, p = q.get()
        if v[p]:
            continue

        neighbourhood = []
        if p[0] - 1 >= 0:
            neighbourhood.append((p[0] - 1, p[1]))
        if p[0] + 1 <= w.shape[0] - 1:
            neighbourhood.append((p[0] + 1, p[1]))
        if p[1] - 1 >= 0:
            neighbourhood.append((p[0], p[1] - 1))
        if p[1] + 1 < w.shape[1]:
            neighbourhood.append((p[0], p[1] + 1))

        for x, y in neighbourhood:
            # тут вычисляется расстояние
            d_tmp = d[p] + np.abs(w[x, y] - w[p])
            if d[x, y] > d_tmp:
                d[x, y] = d_tmp
                q.put((d[x, y], (x, y)))

        v[p] = True

    return d

# вызываем алгоритм для двух масок
d_fg = dijkstra(xy_fg, likelihood_fg)
d_bg = dijkstra(xy_bg, 1 - likelihood_fg)

новая нечеткая маска объекта

plt.matshow(d_fg, cmap=cm.bwr)
plt.show()

новая нечеткая маска фона

plt.matshow(d_bg, cmap=cm.bwr)
plt.show()

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

margin = 0.0
mask = (d_fg < (d_bg + margin)).astype(np.uint8)

plt.matshow(mask)
plt.show()

Можно отправить себя в космос.

img_fg = img_input/255.0
img_bg = (np.array(Image.open('./../data/background.jpg'))/255.0)[:800, :800, :]

x = int(img_bg.shape[0] - img_fg.shape[0])
y = int(img_bg.shape[1]/2 - img_fg.shape[1]/2)

img_bg_fg = img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :]
mask_3d = np.dstack([mask, mask, mask])
img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :] = mask_3d*img_fg + (1 - mask_3d)*img_bg_fg

plt.imshow(img_bg)

Сглаживание маски

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

Допустим, у нас есть структурный элемент (СЭ) типа "диск" — бинарная маска диска.

• эрозия: прикладываем к каждой точке объекта на оригинальном изображении СЭ так, чтобы совпадал центр СЭ и точка на изображении; если СЭ полностью принадлежит в объекту, то такая точка объекта остается; получается, что удаляются детали, которые меньше чем СЭ, и объект "худеет"; в примере из синего квадрата сделали голубой
• наращивание (dilation): на каждую точку объекта накладывается СЭ, и недостающие точки дорисовываются; таким образом закрашиваются дырки меньшие чем СЭ, а объект в целом "толстеет"; на примере из синего квадрата сделали голубой, углы получились закругленные
• размыкание (opening): сначала эрозия, потом наращивание тем же СЭ
• замыкание (closing): сначала наращивание, потом эрозия тем же СЭ

Мы воспользуемся размыканием, что сначала удалит "волосатость" по краям, а потом вернет первоначальный размер (объект "похудеет" после эрозии).

mask = morphology.opening(mask, morphology.disk(11))
plt.imshow(mask)

После применения такой маски результат станет поприятнее:

img_fg = img_input/255.0
img_bg = (np.array(Image.open('./../data/background.jpg'))/255.0)[:800, :800, :]

x = int(img_bg.shape[0] - img_fg.shape[0])
y = int(img_bg.shape[1]/2 - img_fg.shape[1]/2)

img_bg_fg = img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :]
mask_3d = np.dstack([mask, mask, mask])
img_bg[x:(x + img_fg.shape[0]), y:(y + img_fg.shape[1]), :] = \
    mask_3d*img_fg + (1 - mask_3d)*img_bg_fg

plt.imshow(img_bg)

Накладываем маску

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

Подопытный экземпляр

img_target = np.array(Image.open('./../data/target.jpg'))
img_target = (transform.rescale(img_target, scale=0.5, mode='constant')*255).astype(np.uint8)
print(img_target.shape)
plt.imshow(img_target)

Найдем на подопытном все 62 колючевые точки лица, напомню, что они будут в том же порядке как и на любом другом лице.

img_gray = cv2.cvtColor(img_target, cv2.COLOR_BGR2GRAY)
rects_target = detector(img_gray, 0)
shape_target = predictor(img_gray, rects_target[0])
shape_target = face_utils.shape_to_np(shape_target)

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

Данное уравнение легко решается с помощью псевдообратной матрицы:

Так и сделаем:

# добавим справа к матрицам колонку единиц,
# иначе будет только масштабирование и поворот, без переноса
X = np.hstack((shape, np.ones(shape.shape[0])[:, np.newaxis]))
Y = np.hstack((shape_target, np.ones(shape_target.shape[0])[:, np.newaxis]))
# учим оператор
A = np.dot(np.dot(np.linalg.inv(np.dot(X.T, X)), X.T), Y)

# выбираем точки лица по искомой маске
X = np.array([(y, x, 1) for (x, y) in 
    it.product(range(mask.shape[0]), 
                   range(mask.shape[1])) if mask[x, y] == 1.0])
# вычисляем новые координаты маски на целевом изображении
Y = np.dot(X, A).astype(np.int)

img_tmp = img_target.copy()
for y, x, _ in Y:
    if x < 0 or x >= img_target.shape[0] or y < 0 or y >= img_target.shape[1]:
        continue
    img_tmp[x, y, :] = np.array([0, 0, 0])

plt.imshow(img_tmp)

img_trans = img_target.copy().astype(np.uint8)
points_face = {}
for ix in range(X.shape[0]):
    y1, x1, _ = X[ix, :]
    y2, x2, _ = Y[ix, :]
    if x2 < 0 or x2 >= img_target.shape[0] or 
       y2 < 0 or y2 >= img_target.shape[1]:
        continue
    points_face[(x2, y2)] = img_input[x1, y1, :]

for (x, y), c in points_face.items():
    img_trans[x, y, :] = c
plt.imshow(img_trans)

Заключение

В качестве домашней работы вы можоте самостоятельно сделать следующие улучшения:

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

Ноутбук с исходниками находится тут. Приятного времяпрепровождения.

Как обычно спс bauchgefuehl за редактуру.