【Перевод】GRAIL-распознавание рукописного ввода

искусственный интеллект GitHub алгоритм Twitter

Обновление Твиттера Жуан Ифэна рекомендует иностранный язык, если вам скучно, просто переведите его (инструменты), а новый английский приветствует исправления.Оригинальная ссылка

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

汤姆·艾利斯在20世纪60年代使用RAND平板电脑与屏幕上的图像进行交互
Выше Том Эллис в 1960-х годах использовал планшет RAND для взаимодействия с изображениями на экране.

Причина и следствие

В этой статье мы вернемся к вкладу Габриэля Гронера в проект «Святой Грааль». Гронер изобрел очень умную программу, которая распознавала буквы, цифры, знаки препинания и геометрические фигуры отпечатков ладоней. Программа способна правильно идентифицировать 90% символов, нарисованных пользователем с первого раза. Гронер задокументировал свой метод в служебной записке Рэнда 1966 года для распознавания рукописного текста в реальном времени. В этом посте я представлю простой распознаватель Groner, который распознает только прописные и прописные буквы.

исходный код демоgithub, добро пожаловать на обмен.

Введите текст

Знакомство с планшетом RAND

Люди взаимодействуют со Святым Граалем с помощью планшета RAND, чувствительного к давлению переключателя, установленного на кончике пера. Все входные данные преобразуются в точки в системе координат плоскости xy. Положение стилуса записывается как пара координат (x,y) каждые четыре миллисекунды.

Ниже мы моделируем артборд: двигая указатель и нажимая мышь, это имитирует действие нажатия стилуса на поверхность планшета. Не отпуская мышь, подведите указатель к поверхности планшета, чтобы сделать отметку. Отпустите кнопку мыши, когда метка вас удовлетворит. Попробуйте почувствовать работу на планшете, нарисовав несколько цифр (2, 3, 6) и букв (C, M, S).

Сглаживание

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

Эта схема сглаживает данные путем усреднения вновь поступивших точек данных с ранее сглаженными точками данных, тем самым уменьшая шум из-за дискретного характера положения пера, измеряемого планшетом. То есть ((x1-x)*n,(y1-y)*n)

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

平滑处理

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

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

Smoothing Factor: 0.43  滑动系数
XSi = 0.43XSi-1 + 0.57XRi 
YSi = 0.43YSi-1 + 0.57YRi 
XRi,YRi = coordinates of ith raw point  画板中的原始点
XSi,YSi = coordinates of ith smoothed point 平滑之后的点 

【Изображение 3】

Истончение

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

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

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

细化

Thinning Size = 0.30 细化系数
|XSi - XTj-1| >= 0.30 绝对值大于系数的保留
|YSi - YTj-1| >= 0.30

Кривизна

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

曲率-4方向

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

if |XTj - XTj-1| >= |YTj - YTj-1|
right if XTj - XTj-1 >= 0
left if XTj - XTj-1 < 0 

if |XTj - XTj-1| < |YTj - YTj-1|
up if YTj - YTj-1 >= 0
down if YTj - YTj-1 < 0

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

冗余曲率

Углы

Хотя кривизну каждого штриха можно использовать для предположений о намерениях пользователя, некоторые символы нельзя отличить друг от друга, используя только информацию о направлении. Например, при рисовании «5» и «S» оба направления будут давать один и тот же сегмент направления. Гронер решил разрешить эти неясности наличием или отсутствием углов. Например, цифра «5» обычно рисуется с одним или двумя углами слева от символа, а буква «S» обычно рисуется без углов.

Обнаружение углов реализовано относительно просто. Мы назначаем каждой входной точке кардинальное направление, и Гронер также назначает каждой точке 16 возможных направлений. Углы обнаруживаются, когда перо перемещает два сегмента в одном направлении, изменяя направление не менее чем на 90°.

Нарисуйте несколько цифр, букв и основных фигур на плите ниже, чтобы увидеть алгоритм обнаружения углов в действии. Распознаватель отметит угол розовым крестиком. Вы можете использовать ползунок на правой стороне планшета для проверки пороговых значений, отличных от 90°. Потратьте некоторое время на рисование символов, где углы являются отличительной чертой (5, s, C, G, квадрат и круг), затем медленно отрегулируйте ползунок.

Corners

Элементы размера и положения Элементы размера и положения

Каждая отметка на планшете упакована как описание штриха. Описания штрихов — это представления существенных особенностей записи. Это описание позволяет нам легко ответить на вопрос: «Нарисовал ли пользователь этот символ в левом верхнем углу, а затем перестал рисовать в правом нижнем углу?» «Если ответ на этот вопрос утвердительный, то велика вероятность, что пользователь нарисовал 2 или Z. «Поднял ли пользователь перо с поверхности рядом с тем местом, где он начал рисовать? Если это так, пользователь может нарисовать закрытую черту, например, O или 8. В описаниях штрихов также фиксируются простые характеристики штрихов, такие как ширина, высота и соотношение сторон. Эти признаки позволяют нам ответить на вопрос: «Можете ли вы описать этот символ как толстый или тонкий?» Ответ на этот вопрос может помочь нам отличить 7 от 1.

По мере рисования штриха его крайние значения X (по горизонтали) и Y (по вертикали) постоянно обновляются. Когда перо поднимается, чтобы указать, что штрих завершен, схема анализа использует эти крайние значения для расчета высоты и ширины символа в долях дюймов, его соотношения сторон (отношения высоты к ширине) и его центра относительно Происхождение. Он делит прямоугольную область, определяемую символическими экстремумами, на сетку 4×4. Затем начальная (перо вниз) и конечная (перо вверх) точки и угловые позиции, каждая из которых закодирована так, чтобы лежать в одной из этих 16 областей, позиционируют их относительно символа.

Нарисуйте несколько букв и цифр на виртуальном планшете ниже. Место начала рисования отмечено синим кружком, а место окончания рисования отмечено синим квадратом.

Size and Position Features

Распознавание персонажей

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

Распознаватель сначала генерирует список потенциальных символов на основе первых четырех основных направлений штриха. Штрихи, которые нельзя нарисовать напрямую или без этих первых четырех направлений, немедленно игнорируются. Иногда первые четыре направления дают достаточно информации для точной идентификации персонажей. Например, штрих, который идет вниз, вправо, а затем останавливается, может быть немедленно распознан как буква L. Обычно первые четыре направления не приводят к немедленному узнаванию, и у нас остается список потенциальных персонажей. Например, начальная поездка может быть 0, 2 или 3.

0.2.3

Мы можем устранить эти неясности, проверив другие аспекты описания инсульта. Например, черта может быть идентифицирована как 2, если она заканчивается в правом нижнем углу символа; цифра 3 идентифицирована в нижнем левом углу символа; и 0 идентифицирована, так как начальная и конечная позиции близки. относительно друг друга в верхней части символа. На практике процесс принятия решения реализуется путем написания большого каскада операторов ЕСЛИ. Никакой «магии» в этом процессе нет. И деревья решений нужно улучшать и модифицировать, чтобы встречать новые и неожиданные способы написания определенных символов.

Распознаватель, который я предлагаю в этой статье, способен распознавать заглавные буквы и цифры, нарисованные одним штрихом. Другими словами, каждый символ должен быть нарисован одним мазком. Оригинальный распознаватель Groner может распознавать многострочные символы, позволяя пользователям вводить текст так, как они привыкли. Целью Гронера является сохранение существующих привычек пользователей, чтобы пользователям не приходилось приспосабливаться к их стилю письма. На самом деле, Алан Кей утверждает, что одним из основных мотивов создания системы было избавление от необходимости учить печатать. Поскольку моя цель была гораздо менее амбициозной — объяснить основной подход, использованный Гронером, — я решил реализовать более простой распознаватель однотактных вариантов. Распознавание нескольких штрихов не намного сложнее, чем распознавание одиночных штрихов, но немного сложнее. Если вы заинтересованы в том, чтобы сделать это самостоятельно, в оригинальной записке Гронера четко изложен этот подход.

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

所有字符

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

333

识别器
Распознаватель опыта - Оригинал, или поставьте лайк, если кто-то меня увидит, я скопирую его в эту статью позже Скорее всего, мой распознаватель не сможет обнаружить. Если это произойдет, вы не должны винить подход Гронера. В служебной записке ясно, что при первом использовании пользователем своего распознавателя вероятность успеха составляет 90%. Мое дерево решений является моим собственным, и оно ориентировано на мой собственный стиль каллиграфии. Тем не менее, мое преимущество использования Grona заключается в том, что я могу постоянно вести программу непрерывного улучшения! Если вас раздражает неправильный логотип, разместите его скриншот на странице релизов проекта на GITHUB.

Эпилог

Почему людей в 2016 году (эта статья была написана в 2016 году) волнуют алгоритмы распознавания рукописного текста прошлого века? Прошло пять лет с тех пор, как меморандум Гронера был опубликован, и Святой Грааль исчез из основного программирования и канона сообщества HCI, так зачем тратить время на перечитывание оригинальной книги Гронера, не говоря уже об этой статье?

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

Перевод из книги Джека Шедлера, Берлин, 2016 г.