Игры и Люди

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

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

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

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

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

Google+

Разведывательный полет

Видео советую смотреть в разрешении 720p или 1080p

Беспилотная тема выходит из лаборатории на свежий воздух. В результате кооперации с энтузиастами летающих моделей состоялся летный эксперимент — своего рода разведка боем. Он преследовал сразу несколько целей:

  • получение качественного видео, имитирующего взлетно — посадочную полосу (ВПП) с расположенными на ней маркерами. В качестве ВПП была отснята автострада;
  • проход над «ВПП» под различными углами, высотами и имитация захода на посадку;
  • получение данные телеметрии и создание подсистема их визуализации в реальном времени.

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

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

Итак, рассказываю про эксперимент, что и как )

Борт

В качестве беспилотника взяли имеющийся в наличии Phantom 4. Это квадрокоптер, которому автоматическая посадка особо не нужна. Но мы все равно решили полетать на нем, чтобы иметь возможность сделать несколько проходов и обеспечить качество картинки. Фантом управлялся с отдельного пульта, к которому был подключен планшет Samsung/Android.

Когда дело дойдет до автоматической посадки, будем облетывать свое. Например это:

IMAG3305

Иди даже вот это:

IMAG3306

Энтузиасты свое дело знают!

Камера

На Фантоме установлена камера Go Pro с разрешением HD. Камера стабилизирована на карданном подвесе, есть возможность управления углом наклона. Мы выставили около 30° вниз, чтобы лучше было видно дорогу с маркерами.

Видео с камеры идет на экран приложения планшета, и также записывается приложением в формате mp4 целым файлом. Видео также записывается на SD карту которая вставляется в квадрокоптер, на карте я обнаружил несколько MOV файлов с размером около 2 Гб каждый.

Тут возникла первая проблема: частота фреймов Go Pro — 120 кадров в секунду, мои кодеки на Ubuntu неправильно определяли ее (как 30 fps) и соответственно попытка понизить frame rate до 30 кадров в секунду не увенчалась успехом. Потом я нашел другой способ: в видеоредакторе kdenlive использовал фильтр, который понижает скорость воспроизведения в четыре раза. В конечном счете, я просто взял mp4 файл который записался в планшете и работал с ним.

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

Софт

На планшет я установил приложение DJI Go, в котором можно получать изображение с камеры квадрокоптера. Покопавшись в файловой системе,  нашел лог телеметрии. Его формат неизвестен, но есть возможность перекодировки в csv. Для парсинга лога я воспользовался сервисом сайта healthydrones.com.

Были оставлены только данные, которые представляют интерес: координаты в виде широта/долгота, данные компаса, высоты, угол наклона камеры и метки времени. Лог выглядел примерно так:

Лог телеметрии БПЛА

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

Для обработки лога и визуализации полета «по приборам» было написано Qt приложение, которое разбирало лог синхронно с временными метками и отображало информацию на «приборах» кокпита. В качестве таких приборов были применены замечательные виджеты QFlightInstruments.

Индикация организована следующим образом. Данные высоты не калибровались. Они отображаются на отдельном индикаторе и на комбинированном индикаторе авиагоризонта.

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

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

В правом верхнем углу — отметка даты и времени.

На панели есть еще один индикатор, который пока не используется. На него будет выводится посадочная информация — отклонение БПЛА от глиссады. Это позволит оператору вести посадку как в ручном режиме, так и контролировать посадочный автопилот.

ToDo

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

Собственные числа и векторы в поиске закономерностей. Метод главных компонент

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

Что поделаешь, это еще одно напоминание о том, что человеческий глаз — это совершенное средство обработки данных.

В этом примере прямая — это некоторая закономерность, которую нужно найти в потоке данных. Где может пригодиться такой алгоритм? Например, в распознавании маркеров взлетно — посадочной полосы оптической системы посадки БПЛА. Или хотя бы определить направление, в котором дедушка Ляо идет из кабачка домой.

Principal Component Analysis, eigenvalue, eigenvector, собственные числа, собственные векторы, БПЛА, распознавание маркеров ВПП

Следы оставленные дедушкой Ляо по дороге из кабачка домой

Понаблюдаем же за дедушкой Ляо. Хорошо посидев с друзьями своей юности в кабачке, он спешит к домашнему очагу. Как видно из карты перемещений, у дедушки Ляо не очень уверенная походка. Тем не менее, очевидно что он стойко идет к своей цели. Очевидно для нас, потому что мы пользуемся совершенными инструментами — собственными глазами. А что делать компьютеру? Как ему выявить закономерность на основе данных десяти точек?

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

Матрицы линейного преобразования: портим фигуру

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

Для наглядности можно вывести значение этой матрицы на экран:

Матрица определяет фигурку из 12 точек, первая строка — x координаты точек, вторая строка — y координаты. Выглядит фигурка так:

Собственные числа, собственные векторы, линейное преобразование, метод главных компонент, Principal Component Analysis

Фигурка, соответствующая исходной матрице

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

Или сжимать также по горизонтали:

Растягивать по вертикали:

Перекос:

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

Или вообще вместе со сжатием и растяжением еще перекосить ее так, что сразу и не узнаешь:

Воспользуемся последним преобразованием и скособочим нашу фигурку:

Собственные числа, собственные векторы, линейное преобразование, метод главных компонент, Principal Component Analysis

Начальный ромбик — синие квадратики, преобразованный — красные кружки

Матрица линейного преобразования A перевела 12 наших исходных векторов на другие позиции, то есть поменяла их координаты: на то оно и преобразование.

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

Вскрытие собственников

Найдем собственные числа и собственные векторы нашей матрицы преобразования A. На Питоне это делается одной строчкой:

Я придерживаюсь обозначений, которые показаны в примерах модуля numpy Питона: w — это собственное число, v — собственный вектор. Неудобно, что слова vector и value начинаются на одну и ту же букву, и поскольку вектор главнее, собственное число получило наименование w.

Посмотрим что получилось:

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

Первая парочка:

Наступил момент истины. Подвергнем вектор линейному преобразованию:

Так оно и есть: собственный вектор «не чувствует» родную матрицу A и остается таким же, как и был, точнее — умноженным на собственное число.

Проверка второй парочки:

Тоже самое: какого-либо желания трансформироваться не обнаружено напрочь.

Principal Component Analysis (PCA), или  Метод главных компонент в поисках закономерностей

Теперь мы хорошо подготовлены к тому, чтобы переварить идею метода PCA, вынесенного в заголовок. Метод основан на поиске осей максимальных изменений входных данных; эти оси называются компонентами, что и послужило основой для названия метода. Подробное и самое главное — понятное описание метода для химических приложений изложено здесь (вспоминая замечательный журнал Химия и жизнь).

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

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

Итак, начнем с выборки следов дедушки Ляо, которую для солидности будем именовать треком из 10 точек:

Уберем из трека постоянную составляющую и найдем ковариационную матрицу трека:

Сделаем передышку и осмыслим сделанное (физический смысл — основа любого метода). О чем говорит ковариацонная матрица? Одинаковые значения 0.615 говорят о степени связи (корреляции) переменных x[0..9] и y[0..9], которые являются соответствующими координатами трека (простите, в Питоне индексы начинаются с нуля). Элементы главной диагонали 0.717 и 0.617 говорят о корреляции этих переменных с собой же, то есть это практически значения мощности, если переменные интерпретировать как сигналы.

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

Диагональный отрезок под 45°:

Диагональный отрезок под -45°:

Вертикальный отрезок:

Горизонтальный отрезок:

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

Если мы еще раз нырнем в теорию, то обнаружим, что искомые векторы на самом деле являются собственными векторами ковариационной матрицы.

Итак, за работу!

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

Principal Component Analysis, eigenvalue, eigenvector, собственные числа, собственные векторы, БПЛА, распознавание маркеров ВПП

Главные компоненты метода PCA. Справа — трек в новой системе координат (rotated_track)

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

Кажется, подошло время к тому, чтобы сделать кое-какие выводы.

Тайное становится явным

«Человек, у которого только одни часы, точно знает который час. Обладатель двух часов ни в чем не уверен»

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

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

И в конце вишенка на торте. Посчитаем ковариационную матрицу повернутого трека:

Если считать очень-очень маленькие числа (в степени -17) нулями, то ковариационная матрица нового трека

стала диагональной! А это значит, что корреляция, а именно взаимозависимость между координатами x и y исчезла. Более того, малое значение корреляции для координаты y говорит о том, что мы имеем дело с шумом малой мощности. Сказанное влечет за собой важное следствие: теперь мы можем анализировать трек только по одной новой координате x, не обращая внимания на другую: она в силу ортогональности системы не оказывает никакого влияния.

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

Всем большой привет от дедушки Ляо!

Если у вас нет дома: краткий курс бытия от Лао-Цзы

Если у вас нет дома,
Пожары ему не страшны,
И жена не уйдёт к другому,
Если у вас нет жены.

Если у вас нет тёти,
То вам её не потерять,
И если вы не живёте,
То вам и не умирать.

Оркестр гремит басами,
Трубач выдувает медь.
Думайте сами, решайте сами —
Иметь или не иметь.

Помните эту песню? Если кому-либо пришло в голову уместить в несколько строк содержимое трактата «Дао дэ дзин», который написал Лао-Цзы, то это можно было бы сделать именно так. Ведь в самом деле:

Слава и позор подобны страху. Знатность подобна великому несчастью в жизни…. обычные люди приобретают славу со страхом и теряют ее тоже со страхом. Что значит, знатность подобна великому несчастью в жизни? Это значит, что я несчастен, потому что дорожу самим собой и боюсь потерять свой статус

Вся идея трактата пронизана этим — «если вы не живете, то вам и не умирать». Эта фраза может показаться унылой перспективой, если понимать жизнь так, как понимаем ее мы. В представлении Лао-Цзы жизнь — это нечто совершенно другое. Есть Дао — поток событий; можно с ним бороться, можно с ним плыть. Подозреваю, что все мудрецы прошли этап борьбы с потоком и пришли к тому, что проще и приятнее просто плыть по нему.

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

Вот и Лао-Цзы, который вел неприметную жизнь смотрителя плантации лаковых деревьев, не собирался писать никаких книг. Неизвестно, откуда он появился и куда ушел. Известно лишь, что перед своим уходом в никуда, начальник пограничной стражи упросил его изложить свои идеи на бумаге, чтобы оставить их потомкам. К слову, вот были интересные пограничники в те времена! Идет такой странник без определенных занятий, с котомкой за плечами, и Страж Границы заводит с ним разговор, выделяет пишущие инструменты и бумагу (что в то время стоило недешево), и просит написать трактат. Так и появился Дао-дэ-цзин, а про Лао-Цзы после этого больше никто ничего не слышал.

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

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

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

Что происходит после выпадения из процесса Дао?

Когда устранили великое Дао, появились «человеколюбие» и «справедливость». Когда появилось мудрствование, возникло и великое лицемерие. … Когда в государстве царит беспорядок, тогда появляются «верные слуги».

Человеколюбие и справедливость в кавычках — это фарисеи. Знакомая история, правда? А про «верных слуг» вообще в точку, для этого даже в древнюю историю закапываться не надо, достаточно современной…

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

Поскольку глобальному процессу нет смысла противостоять, меняется концепция силы. Она парадоксально расходится с общепринятыми представлениями. Тем не менее, из этих строк вышли самые эффективные «внутренние» стили кунг-фу и само айкидо:

Древко крепкое сломается,
Могущественное войско погибнет.
Мягкое и слабое — спутники жизни,
Твердое и сильное — спутники смерти.

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

Пассивный радиолокатор с нейроподобной ФАР

В пассивном радиолокаторе есть функция определения направления прихода сигнала DOA (Direct of Approach). Знание углового положения источника сигнала и помехи позволяет повысить однозначность определения координат цели на эллипсах равновероятного местоположения. В дополнение к уже рассмотренным адаптивным методам, попробуем реализовать нейроподобный подход к задаче определения DOA.

На вход нейроподобной сети (НПС) будем подавать сигнал с элементов

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

Темная сторона КСА УВД Галактика

Встречаются два программиста — один пишет на Си, другой на Ада. Си-программист говорит: — Я буду бифштекс с луком

Анекдот понятный только для тех программистов, кто в теме )

Отображение воздушной обстановки на экране диспетчера. Какое программное обеспечение скрыто за монитором?

Разработка программного обеспечения для промышленных систем

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

Судовой радиопеленгатор. Пиратская история

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

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

Школьный вечер

Мормон ступал по битому кирпичу. Когда-то здесь было здание — может, коровник, а может сельсовет. Деревня которая осталась позади пребывала в таком же запустении. По крайней мере, не надо беспокоиться за джип, которого уже не видно за пригорком. «За него вообще уже не надо беспокоиться», — поправил себя Мормон. Как и обо всем остальном. Хотя…

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

Адаптивная антенная решетка радиопеленгатора и пассивного радиолокатора

Поскольку пассивный радиолокатор (Passive Coherent Locator) и радиопеленгатор — родственные души, посмотрим как может пригодится адаптация в кольцевой антенной решетке. Что есть главное зло для PCL? Оригинальный сигнал базовой станции. Что есть главное зло для РП? Переотражения от местных предметов, или как любят говорить связисты, многолучевое распространение. И в том и другом случае, антенная решетка,

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

Хорошо что теперь летят не ракеты

Советская СС-20 и американский Першинг. Когда-то они смотрели друг на друга с противоположных континентов, а сейчас стоят рядышком в одном музее

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

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

Графический акселератор в Python

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

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

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