Игры и Люди

… одетый только в халат из холщовой ткани, ходил в кабачки и к певичкам. Когда его спрашивали, почему он таков, он каждый раз открывал рот, засовывал туда кулак и не говорил. Император Лян-цзун призвал его и спросил: «Каков принцип Вашего Пути?» Гуйчжэнь ответил: «Одежда тонка — поэтому люблю вино, выпью вина и защищусь от холода, напишу картину — и расплачусь за вино. Кроме этого, ничего не умею». Лян-цзун не нашелся, что сказать…

От игрушек детства мы движемся к другим. Здесь — об этом.

Алхимия игры включает несколько ингредиентов.

Рецептура состоит из Миров, по которым можно путешествовать; не все из них достаточно хорошо населены. Дело — это Игрушка одного из миров.

Объединяя видимые и сокрытые элементы, Алхимия выступает и как самостоятельный Игрок.

Google+

Препарируем Blockchain

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

Поработаем с блоками и связями такой популярной криптовалюты, как BitCoin.

Блоки и связи / Block & Chains

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

Блоки хорошо представлять в виде вагончиков, которые сцепляются друг с другом. Эта аналогия обладает еще одним ценным соответствием: самый первый вагончик, то есть паровозик, не сцеплен спереди ни с кем. Это самый верхний блок в системе, и он будет самым верхним до тех пор, пока кто-нибудь не намайнит следующий блок. Тогда новый блок становится паровозиком во главе состава и к нему подцепляется остальная цепочка.

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

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

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

Block Parsing

Распарсим один из блоков блокчейна. Я взял для примера блок #528340, хэш которого имеет значение

0000000000000000002740c2167e7dcea59e11362587ea9ed348022701f5a73d.

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

Заканчиваем с лирическими отступлениями и приступаем к парсингу. Блок будем брать прямо с сайта по его хэшу:

Если код статуса равен 200, значит на запрос получен ответ с нужными данными в формате JSON, которые преобразуются в словарь с парами ключ — значение (переменная data).

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

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

Теперь все это нужно смешать в одну кучу

и найти значение хэша нашего блока:

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

Полезная нагрузка: транзакции

За повествованием мы забыли про полезное наполнение блока, ради чего все собственно затевалось: про транзацкции, кто кому сколько перечислил. Транзакций в блоке великое множество, они проходят под ключом tx. Gосмотрим только одну из, например самую верхнюю n=0:

Информацию дает строчка json.dumps(data[‘tx’][n]), остальное — красивости для удобочитаемого вывода. В результате увидим:

Видно, что некто перечислил 14.3 BTC кому-то. Именно так: кошельки отправителя и получателя представлены в виде хэшей, и кто это такие — мы не знаем. Собственно это и есть краеугольный камень БитКойна.

Блокчейн хранит абсолютно все транзакции, которые были в системе. По этой причине совершенно четко видно, как появляются монеты и к кому они переходят, и какое общее количество их находится в системе.

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

Google Contacts API и авторизация OAuth2

Когда в адресной книге Google набирается несколько тысяч клиентов, становится тяжеловато ворочать этим объемным списком. Импорт/экспорт в странички Excel становится неудобным; кроме того появляются CRM-подобные приложения, в которых хотелось бы интегрировать самые разные базы данных, в том числе и контакты Google. Значит, пришло время доступиться к нашим контактам через консольные приложения, используя Google Contacts API.

Получение списка контактов

Используя API, мы можем не только получить список контактов, но также и видоизменять и дополнять его. В простейшем случае, первые 150 записей из адресной книги можно вытащить так, вбив это в адресную строку браузера:

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

Регистрируемся в Google

Предполагаю, что у вас уже есть Google-аккаунт, или электронная почта. Логинимся на страничке Гугла и идем по адресу https://console.developers.google.com/cloud-resource-manager , где создаем новый проект. Даем ему произвольное название, например Beerware. Дальше переходим в другое место https://console.developers.google.com/apis/credentials. Жмем кнопочку «Создать учетные данные» и выбираем «Идентификатор клиента OAuth», и дальше отмечаем «Другие типы». Дадим название идентификатору — скажем Beerware Script.

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

Это все, что нужно было сделать в девелоперских панелях Гугла. Если вы нажмете на редактирование идентификатора, то увидите ID клиента и секрет клиента. Запомним эти названия, они понадобятся нам дальше. Чтобы не путаться с обозначениями при подстановке в другие строки, обозначим их CLIENT_ID и CLIENT_SECRET.

Authorization Flow: как проходит авторизация OAuth2

Конечной целью авторизации является получение ACCESS_TOKEN, который необходимо использовать каждый раз когда мы делаем запрос к адресной книге. Теперь нам нужно внимательно пройтись по всем этапам. Самая главная вещь, которая толком не описана в документации Google — какие этапы выполняются только один раз, а какие нужно выполнять периодически. Я буду это подчеркивать.

Каждый этап — это обращение к серверу Google по HTTPS и получение ответа. Детали запроса я распишу позже, сейчас главное — уяснить общую схему.

Получение кода авторизации

Код авторизации сразу ставит в тупик. Зачем он нужен, если уже есть CLIENT_SECRET?  Разница в том, что код авторизации используется только один раз — для получения токенов. Замечу сразу, что если вы попытаетесь получить по одному и тому же коду авторизации токены еще раз, то получите ошибку. Таким образом, код авторизации действителен пока мы еще не получили токены. После их получения он сразу «протухает». Но об этом — дальше.

CLIENT_SECRET, как и CLIENT_ID — постоянные строки, скрытые в нашем приложении вдали от посторонних глаз.

Итак, посылаем на сервер CLIENT_ID, CLIENT_SECRET и получаем код авторизации. Назовем его AUTH_CODE.

Получение токенов

И снова заголовок наводит на размышления. Почему токены во множественном числе, когда вначале говорилось только об ACCESS_TOKEN? На самом деле, помимо этого токена, который используется при работе с адресной книгой, нам дают еще REFRESH_TOKEN. Его роль будет ясна ниже.

Посылаем на сервер CLIENT_ID, CLIENT_SECRET, AUTH_CODE и получаем парочку ACCESS_TOKEN, REFRESH_TOKEN.

Казалось бы, тут можно забыть о REFRESH_TOKEN, поскольку ACCESS_TOKEN  у нас в руках, и дальше еще забыть и про авторизацию и спокойно пользоваться ACCESS_TOKEN во всех запросах. Я так поначалу и делал, только обнаружил что в один прекрасный момент сервер перекрыл мне доступ. В чем дело? А причина была в том, что по задумке Google время жизни ACCESS_TOKEN — всего лишь час, после чего он протухает и работать с ним не получится.

Что теперь, снова получать код авторизации и токены? Нет. Про эти два этапа «получение кода авторизации» и «получение токенов» можно полностью забыть и уже никогда к ним не возвращаться. Самое главное, что у нас есть — это REFRESH_TOKEN. Сохраните его в надежном месте, поскольку теперь кроме него нам ничего не нужно.

Замечу, что эти пройденные этапы мы выполняем лично. Наше приложение Beerware Script о них ничего не знает: ему нужны только токены.

Получение ACCESS_TOKEN по REFRESH_TOKEN

Дальше все становится просто. Когда ACCESS_TOKEN протухает, то есть через час становится не действительным, или просто не дожидаясь этого момента, мы посылаем на сервер CLIENT_ID, CLIENT_SECRET, REFRESH_TOKEN и получаем обновленное значение ACCESS_TOKEN, которое используем для запросов к серверу. Важно знать, что при этом REFRESH_TOKEN не меняется. Поэтому для приложения критично запомнить его, например в файле, при получении в самый первый раз.

Все этапы авторизации из командной строки

Для различных языков есть соответствующие библиотеки OAuth2. Мы же, для ясности изложения, все будем делать ручками из командной строки, формируя запросы с помощью утилиты curl. В конце концов, все эти библиотеки делают тоже самое — формируют url запросы к серверу Google.

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

Запросом response_type=code мы хотим увидеть код авторизации. Он будет переслан по адресу redirect_uri, а поскольку на URI=http://localhost:8080 ни у меня, ни думаю у вас — ничего нет, то естественно браузер даст ошибку. Но это неважно, поскольку искомый код появится в адресной строке браузера и мы возьмем его оттуда, копируя начиная с code= и продолжая до символа #, который присутствует в конце url. Так мы получаем AUTH_CODE.

В середине процедуры вас может пробросить на страницу авторизации, где вы должны подтвердить доступ к адресной книге со стороны проекта Beerware.

Теперь получаем токены. На запрос

сервер выдаст нам долгожданную парочку токенов:

Если мы попробуем получить токены еще раз, с использованным кодом авторизации, нас ожидает ошибка:

Все, код авторизации протух и с ним уже сделать ничего нельзя!

На этом ручная работа закончилась и скрипт Beerware Script может начинать работу. Отдаем ему ACCESS_TOKEN и REFRESH_TOKEN и забываем про авторизацию. Все, что нужно делать скрипту когда ACCESS_TOKEN становится недействительным — это получить его новое значение запросом

Само собой, это будет уже не утилита curl, а https запрос с соответствующей библиотеки нашего приложения Beerware Script.

После запроса мы получим новый ACCESS_TOKEN:

Поработаем с адресной книгой

Теперь самое время посмотреть, как будет выглядеть работа со списком адресов. Как обычно, на этом этапе нам ассистирует Python. Ниже — фрагменты скрипта Beerware Script, которые дают представление об общей идее работы с полученным списком.

Вначале затребуем список:

В комментах видно, в каком месте нужно ловить ошибку авторизации, когда ACCESS_TOKEN устареет. Дальше нужно что-то делать с полученным списком адресов, наверное самое очевидное — это получить номера телефонов.

Делается это в цикле по всей структуре data:

В результате после работы скрипта получим список контактов, где под каждой фамилией будет список телефонов. Тема отдельного рассмотрения — как изменять существующие контакты и заводить новые. Это решается засылкой на сервер соответствующей xml записи. Подробно процедура описана здесь. Думаю, вы и сами отлично справитесь с этой задачей )

Согласованный фильтр 2D: поиск соответствия в изображении

Согласованную фильтрацию можно рассматривать как во временной, так и в частотной области.

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

Еще нагляднее физический смысл проявляет себя в частотной области: согласованный фильтр «доворачивает» спектральные составляющие сигнала ровно настолько, чтобы они складывались синфазным образом, достигая максимального выходного эффекта. Чтобы доворот происходил в направлении компенсации, используется комплексно-сопряженное значение передаточной функции фильтра.

Часто реализацию согласованного фильтра выполняют в частотной области, используя наработанные библиотеки быстрого преобразования Фурье (БПФ).

Вот пожалуй и все, что хотелось бы сказать про согласованный фильтр (СФ). Поехали дальше.

От времени к пространству

Что скажете, если мы займемся фильтрацией пространственных данных? Это немного непривычно, поскольку мы обычно связываем сигнал с изменениями во времени. С другой стороны, когда смотрим на график этого сигнала то видим только рисунок, и ничего более. И фактически работаем с этим рисунком. Только это будет одномерная обработка, где ось времени будет просто абстрактной осью x.

С двумерными изображениями физический смысл ускользает. Как представить этот сигнал изменяющимся во времени, когда он содержит уже две «псевдовременные» оси? Поэтому нам лучше оторваться от привязки ко времени и воспринимать сигнал тем, чем он является — 2D изображением. Что интересно, для многомерных сигналов также существует понятие пространственных частот, и это активно используется при изучении работы объемных антенных решеток.

Маджонг: найти кубик

Чтобы наше повествование не выглядело слишком солидным и серьезным, выберем в качестве входного сигнала изображение россыпи кубиков Маджонг:

Исходная сцена для поиска кубика, соответствующего шаблону

Поставим себе задачу: найти в этой россыпи определенный кубик, например такой:

Шаблон для поиска

Как вы догадались, этот кубик, который я буду использовать в качестве шаблона, просто скопирован из исходной сцены — россыпи. Вот кстати, можно сразу немного поиграть в Маджонг: найдите этот шаблон на сцене!

При этом будем считать, что окружающие кубик куски — это тоже часть шаблона. Не будем обрезать его до идеального, ведь лучшее — враг хорошего )

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

Теперь пришло время дать правильные названия всем действующим лицам и участникам.

Кто есть кто

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

Наша задача: найти этот кубик на сцене с помощью 2D согласованного фильтра, и не только найти, но и сразу определить его местоположение. Структура СФ будет определяться шаблоном для поиска — этим же кубиком, который на этот раз сам по себе.

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

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

Перед фильтрацией необходимо найти пространственные спектры сцены и нашего опорного кубика:

Запускаем интерпретатор Питона (да, это был именно он) и смотрим на результаты.

Результат работы согласованного фильтра 2D

Я добавил в программу небольшой вспомогательный код, чтобы отмечать зеленой рамкой на сцене месторасположение максимального отклика на выходе СФ. На рисунке сцена (сигнал+шум) расположена слева, отклик согласованного фильтра — справа. Белый цвет соответствует максимальному отклику.

Согласованный фильтр 2D, 2D Matched Filter

Результат работы согласованного фильтра 2D для поиска шаблона

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

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

Согласованный фильтр 2D, 2D Matched Filter

Результат работы согласованного фильтра 2D со сценой, содержащей два шаблона

Интересное наблюдение: на картинке отклика СФ наблюдается небольшое светлое пятно, соответствующее определенному совпадению с сигналом шаблона. Я долго не мог понять, что он там нашел, а потом догадался: ведь искомый кубик имеет повторяющуюся структуру, и этой области немного не хватило рисунка, чтобы продолжить следующие шесть точек на юго-восток. Совпадение получилось только наполовину, что дало всплеск на выходе СФ.

Может возникнуть такой вопрос: если помеха отфильтрована, почему на выходе СФ мы не наблюдаем чистый сигнал? Вот такой он, согласованный фильтр: использует всю информацию о сигнале, и на выходе ее уже не остается. Только уровни, которые только и остается что сравнивать. Если бы на выходе мы наблюдали признаки формы сигнала, это означало бы, что СФ не использовал эту информацию в обработке.

Также открою маленький секрет: выход СФ есть не что иное, как двумерная корреляционная функция сцены и шаблона.

Эта статья — аэродром подскока, который мы используем позже, когда начнем распознавать маркеры системы автоматической визуальной посадки беспилотников. Эта игрушка будет посильней Маджонга!

Алгоритм MUSIC: MUltiple SIgnal Classification в оценке спектра

Вот мы наконец и добрались до этого метода. Литературы по этой технике — целая куча, но как обычно смысл ускользает. Само описание MUSIC достаточно простое: это поиск экстремума произведения двух матриц. Однако что происходит внутри этих матриц — с этим нам предстоит разобраться.

Эту тему довольно сложно понять с нуля, не имея относительно прочной опоры

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

АРП DF-2000: что пошло не так с этим радиопеленгатором

Историю современных радиопеленгаторов для аэропортов гражданской авиации можно отсчитывать от момента появления новой версии АРП «Платан» с процессорной обработкой и операционной системой. В то время было принято, что радиоприемные устройства (РПУ) — покупные «Юрки» будут компромиссным решением (за неимением радиоприемника своей разработки). Вначале разрабатываемое цифровое РПУ было частью пеленгационного проекта, но со временем руководство конторы

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

Устойчивость АФАР/AESA радиолокатора F-35 к блокированию T/R модулей

Антенная решетка локатора AN-APG-81 самолета F-35

Бортовые радиолокаторы военных самолетов, предназначеные для поиска и сопровождения целей проходят эволюцию от пассивных фазовых антенных решеток (ПФАР, или PESA — Passive Electronically Scanned Array) к активным фазовым антенным решеткам — АФАР, или AESA: Active Electronically Scanned Array). Базовым элементом и тех и других является приемо-передающий модуль —

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

Блеск и горечь архитектуры OMAP 3530

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

ARM хорош и к тому же быстро развивается, сопроцессор с плавающей точкой NEON с распараллеливанием выполнения (pipeline) уже само собой разумеющийся атрибут. В последнее время обозначилась новая мода —

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

Проект в проекте

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

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

Трансляция видео на два HDMI экрана

Одновременная трасляция видео на два экрана

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

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

Импортозамещение СКРС / VCS методом China Copy

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

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

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