Распознавание символов

Оптическое распознавание символов

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

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

История

В 1929 году Густав Таушек (Gustav Tauschek) получил патент на метод оптического распознавания текста в Германии, после чего за ним последовал Гендель (Paul W. Handel), получив патент на свой метод в США в 1933. В 1935 году Таушек также получил патент США на свой метод. Машина Таушека представляла собой механическое устройство, которое использовало шаблоны и фотодетектор.

В 1950 году Дэвид Х. Шепард (David H. Shepard), криптоаналитик из агентства безопасности вооружённых сил Соединённых Штатов, проанализировав задачу преобразования печатных сообщений в машинный язык для обработки компьютером, построил машину, решающую данную задачу. После того как он получил патент США, он сообщил об этом в «Вашингтон Дэйли Ньюз» (27 апреля 1951) и в «Нью-Йорк Таймс» (26 декабря 1953). Затем Шепард основал компанию, разрабатывающую интеллектуальные машины, которая вскоре выпустила первые в мире коммерческие системы оптического распознавания символов.

Первая коммерческая система была установлена на «Ридерс Дайджест» в 1955 году. Вторая система была продана компании «Стандарт Ойл» для чтения кредитных карт для работы с чеками. Другие системы, поставляемые компанией Шепарда, были проданы в конце 1950-х годов, в том числе сканер страниц для национальных воздушных сил США, предназначенный для чтения и передачи по телетайпу машинописных сообщений. IBM позже получила лицензию на использование патентов Шепарда.

Примерно в 1965 году «Ридерс Дайджест» и «Ар-Си-Эй» начали сотрудничество с целью создать машину для чтения документов, использующую оптическое распознавание текста, предназначенную для оцифровки серийных номеров купонов «Ридерс Дайджест», вернувшихся из рекламных объявлений. Для печати на документах барабанным принтером «Ар-Си-Эй» был использован специальный шрифт OCR-A. Машина для чтения документов работала непосредственно с компьютером RCA 301 (одна из первых полупроводниковых ЭВМ). Скорость работы машины была 1500 документов в минуту: она проверяла каждый документ, исключая те, которые она не смогла обработать правильно.

Почтовая служба Соединённых Штатов с 1965 года для сортировки почты использует машины, работающие по принципу оптического распознавания текста, созданные на основе технологий, разработанных исследователем Яковом Рабиновым. В Европе первой организацией, использующей машины с оптическим распознаванием текста, был британский почтамт. Почта Канады использует системы оптического распознавания символов с 1971 года. На первом этапе в центре сортировки системы оптического распознавания символов считывают имя и адрес получателя и печатают на конверте штрих-код. Он наносится специальными чернилами, которые отчётливо видимы в ультрафиолетовом свете. Это делается, чтобы избежать путаницы с полем адреса, заполненным человеком, которое может быть в любом месте на конверте.

В 1974 году Рэй Курцвейл создал компанию «Курцвейл Компьютер Продактс», и начал работать над развитием первой системы оптического распознавания символов, способной распознать текст, напечатанный любым шрифтом. Курцвейл считал, что лучшее применение этой технологии — создание машины чтения для слепых, которая позволила бы слепым людям иметь компьютер, умеющий читать текст вслух. Данное устройство требовало изобретения сразу двух технологий — ПЗС планшетного сканера и синтезатора, преобразующего текст в речь. Конечный продукт был представлен 13 января 1976 во время пресс-конференции, возглавляемой Курцвейлом и руководителями национальной федерации слепых.

В 1978 году компания «Курцвейл Компьютер Продактс» начала продажи коммерческой версии компьютерной программы оптического распознавания символов. Два года спустя Курцвейл продал свою компанию корпорации «Ксерокс», которая была заинтересована в дальнейшей коммерциализации систем распознавания текста. «Курцвейл Компьютер Продактс» стала дочерней компанией «Ксерокс», известной как «Скансофт».

Первой коммерчески успешной программой, распознающей кириллицу, была программа «AutoR» российской компании «ОКРУС». Программа начала распространяться в 1992 году, работала под управлением операционной системы DOS и обеспечивала приемлемое по скорости и качеству распознавание даже на персональных компьютерах IBM PC/XT с процессором Intel 8088 при тактовой частоте 4,77 МГц. В начале 90-х компания Hewlett-Packard поставляла свои сканеры на российский рынок в комплекте с программой «AutoR». Алгоритм «AutoR» был компактный, быстрый и в полной мере «интеллектуальный», то есть по-настоящему шрифтонезависимый. Этот алгоритм разработали и испытали ещё в конце 60-х два молодых биофизика, выпускники МФТИ — Г. М. Зенкин и А. П. Петров. Свой метод распознавания они опубликовали в журнале «Биофизика» в номере 12, вып. 3 за 1967 год. В настоящее время алгоритм Зенкина-Петрова применяется в нескольких прикладных системах, решающих задачу распознавания графических символов. На основе алгоритма компанией Paragon Software Group в 1996 была создана технология PenReader. Г.М Зенкин продолжил работу над технологией PenReader в компании Paragon Software Group. Технология используется в одноимённом продукте компании.

В 1993 году вышла технология распознавания текстов российской компании ABBYY. На её основе создан ряд корпоративных решений и программ для массовых пользователей. В частности, программа для распознавания текстов ABBYY FineReader, приложения для распознавания текстовой информации с мобильных устройств, система потокового ввода документов и данных ABBYY FlexiCapture. Технологии распознавания текстов ABBYY OCR лицензируют международные ИТ-компании, такие как Fujitsu, Panasonic, Xerox, Samsung, EMC и другие.

Текущее состояние технологии оптического распознавания текста

Точное распознавание латинских символов в печатном тексте в настоящее время возможно, только если доступны чёткие изображения, такие, как сканированные печатные документы. Точность при такой постановке задачи превышает 99 %, абсолютная точность может быть достигнута только путём последующего редактирования человеком. Проблемы распознавания рукописного «печатного» и стандартного рукописного текста, а также печатных текстов других форматов (особенно с очень большим числом символов) в настоящее время являются предметом активных исследований.

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

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

Онлайн-системы для распознавания рукописного текста «на лету» в последнее время стали широко известны в качестве коммерческих продуктов. Алгоритмы таких устройств используют тот факт, что порядок, скорость и направление отдельных участков линий ввода известны. Кроме того, пользователь научится использовать только конкретные формы письма. Эти методы не могут быть использованы в программном обеспечении, которое использует сканированные бумажные документы, поэтому проблема распознавания рукописного «печатного» текста по-прежнему остаётся открытой. На изображениях с рукописным «печатным» текстом без артефактов может быть достигнута точность в 80 % — 90 %, но с такой точностью изображение будет преобразовано с десятками ошибок на странице. Такая технология может быть полезна лишь в очень ограниченном числе приложений.

Ещё одной широко исследуемой задачей является распознавание рукописного текста. В данное время достигнутая точность даже ниже, чем для рукописного «печатного» текста. Более высокие показатели могут быть достигнуты только с использованием контекстной и грамматической информации. Например, в ходе распознания искать целые слова в словаре легче, чем пытаться выявить отдельные знаки из текста. Знание грамматики языка может также помочь определить, является ли слово глаголом или существительным. Формы отдельных рукописных символов иногда могут не содержать достаточно информации, чтобы точно (более 98 %) распознать весь рукописный текст.

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

Для калибровки систем распознавания текста создана стандартная база данных MNIST, состоящая из изображений рукописных цифр.

Алгоритмы распознавания объектов

Библиографическое описание:

Цветков А. А., Шорох Д. К., Зубарева М. Г., Юрсков С. В., Шуклин А. В., Хамуш А. Л., Ануфриев И. Б. Алгоритмы распознавания объектов // Технические науки: проблемы и перспективы: материалы IV Междунар. науч. конф. (г. Санкт-Петербург, июль 2016 г.). — СПб.: Свое издательство, 2016. — С. 20-28. — URL https://moluch.ru/conf/tech/archive/166/10825/ (дата обращения: 06.06.2019).



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

Ключевые слова: распознавание образов, обработка изображений, компьютерное зрение, машинное обучение

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

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

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

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

Примитивы Хаара

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

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

Рис. 1. Признаки, используемые для распознавания объектов: а) — пересекающиеся области; б) — непересекающиеся области

Признак для данной области (отклик) на представленное свойство можно вычислить используя выражение (1) :

(1)

Для областей, которые не пересекаются (рис. 1а), и

(2)

Для пересекающихся областей (рис. 1б). Черная и белая области обозначается «Ч» и «Б» соответственно. Пересекающаяся область обозначается ««. Индексом S обозначим сумму яркостей находящихся под областью пикселей изображения, индексом N обозначим количество пикселей, находящихся в этой же области.

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

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

1) в случае непересекающихся областей:

(3)

Для пересекающихся областей:

(4)

2) в случае непересекающихся областей

(5)

Для пересекающихся областей:

(6)

Если смотреть с позиции инвариантности значений свойств касаемо возможных яркостных преобразований изображений, использование формул (5, 6) для вычисления значений откликов является наиболее целесообразным.

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

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

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

В этом разделе описано семейство алгоритмов, в основу которых лег алгоритм AdaBoost (от английских слов «adaptive — адаптивность» и «Boosting — усиление») который был описан в 1996 Yoav Freund и Robert E. Schapire .Данный алгоритм успешно применяли для решения широкого круга задач, связанных с распознаванием на изображении, в том числе для поиска и распознавания лиц. Этот подход до сих пор успешно используется во многих областях и продолжаются как прикладные, так и теоретические исследования алгоритмов AdaBoost.

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

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

‒ Нужно ставить на машину, победившую в четырех предыдущих кругах;

‒ Нужно ставить на машину, на которую максимальное количество ставок;

‒ Фаворитами всегда являются чемпионы предыдущих гонок и т. д.

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

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

Рассмотрим один из первых алгоритмов из этой группы — AdaBoost. На основе этого алгоритма была построена на данный момент наиболее эффективная по качеству распознавания и скорости выполнения пославленной задачи система распознавания объектов на изображении — Viola-Jones ObjectDetector . В числе основных достоинств методов AdaBoost можно отметить:

‒ Высокая скорость работы;

‒ Высокая эффективность (точность);

‒ Простота реализации .

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

. Также у нас есть семейство простых классифицирующих функций. Давайте построим итоговый классификатор в следующем виде:

(7)

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

(8)

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

1. Пусть — обучающая выборка, а ;

2. Для каждого шага .

2.1 Выберем лучший слабый классификатор на распределении :

(9)

2.2 Вычислим коэффициент

(10)

2.3 Запоминаем и обновляем распределение

(11)

3. Составляем сильный классификатор следующим образом:

(12)

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

(13)

где — нормализующий коэффициент, причем

(14)

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

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

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

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

(15)

Отметим тот факт, что при рассмотрениив качестве распределения вероятности надX, что верно так как

(16)

то

(17)

Теперь вычисляем вклад слагаемого функцииклассификации на текущем этапе

(18)

Процесс продолжается до шага M, который задается самостоятельно.

Простые классификаторы

Теперь давайте рассмотрим основу всех методов усиления простых классификаторов — простые классификаторы вида .

Разберем пример: пусть данные, которые подаются на вход — это n-мерные вектора , тогда

(19)

это порог по k-той координате. Несмотря на свою простоту, этот классификатор, усиленный алгоритмом AdaBoost, дает весьма впечатляющие результаты . Система поиска объектов на изображении Viola-Jones находит 95 % всех искомых объектов и с 0.001 % ложных срабатываний.

Основное свойство, которым должен обладать простой классификатор — вероятность ошибки должна быть меньше . То есть нужно, что бы он работал точнее чем орел — решка:

(20)

Механизм AdaBoost

По сути, AdaBoost выполняет две основные задачи:

‒ Отбирает простые классификаторы (простые признаки);

‒ Комбинирует отобранные классификаторы (признаки).

Первая задача решается путем отображения пространства входных векторов в пространство значений простых классификаторов:

(21)

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

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

Во время тренировки алгоритм поэтапно производит отображение и создает гиперплоскость.

Существует интерпретация семейства алгоритмов на основе AdaBoost, которая опирается на понятие граней. Для алгоритма AdaBoost понятие грани определяется так:

(22)

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

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

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

Метод Виолы-Джонса

В классическом методе Виолы — Джонса применяются признаки прямоугольной формы, такие как изображены на рисунке ниже:

Рис. 2. Примитивы Хаара

В дополненном методе Виолы — Джонса, который используется в библиотеках OpenCV, применяются признаки, дополненные следующими примитивами :

Рис. 3. Примитивы Хаара, используемые в расширенном методе

Для вычисления значения признака подобного типа применяется формула(23)

(23)

где X — суммарное значение яркостей точек закрытых светлой частью признака, а Y — суммарное значение яркостей точек закрытых темной частью признака. Примитивы Хаара дают точечное значение перепада яркости по оси X и Y соответственно .

Алгоритм Хафа

В основе алгоритма Хафа лежит метод обнаружения линий на изображении. Использование этого метода дает возможность задавать параметры поиска линий или семейства кривых и находить на изображении множество кривых данного семейства.

Пусть, имеются точки в пространстве

(24)

Семейство кривых задано параметрически:

(25)

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

В теории, этот метод можно применять не только на плоскости, но и в n-мерном пространстве. Но на практике используется, в основном, поиск в 2-х мерном пространстве, так как сложность алгоритма достаточно высока .

Стандартный алгоритм состоит из следующих шагов:

‒ Выбор шага дискретизации;

‒ Заполнение матрицы;

‒ Анализ матрицы;

‒ Выделение кривых.

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

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

Существует несколько модификаций стандартного алгоритма Хафа:

Комбинаторное преобразование Хафа

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

Иерархическое преобразование Хафа;

Другой метод поиска линий на бинарном изображении:

‒ Исходное изображение разбивается регулярной сеткой

‒ Используя преобразование Хафа, в каждом фрагменте обрабатываемого изображения обнаруживаются прямые,

‒ Производится иерархическое слияние

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

Адаптивное преобразование Хафа

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

‒ Выбор матрицы маленького размера;

‒ Размер ячейки матрицы уменьшается с каждой итерации, до тех пор, пока не будет достигнут заданный размер;

‒ Заполнение матрицы происходит стандартным способом;

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

‒ Выделение кривой.

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

Алгоритм сравнения с шаблоном

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

‒ Обрабатываемое изображение накладывается на шаблон;

‒ Изображение перемещается по шаблону в поисках совпадений;

‒ При каждом изменении положения изображения вычисляется метрика, отражающая совпадение. Метрика записывается в итоговую матрицу для каждого положения в виде ;

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

Алгоритм сравнения с шаблоном, но основе метода наименьших квадратов

Пусть R(x, y) — результирующая матрица.

(21)

текущие координаты шаблона.

, где — ширина, а высота шаблона.

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

Сегментация изображения

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

Существуют определенные требования, предъявляемые к обрабатываемым областям:

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

‒ Смежные области должны иметь существенные отличия по характеристикам, относительно которых они считаются однородными;

‒ Границы между сегментами быть достаточно явными.

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

Существуют следующие алгоритмы сегментации:

‒ Пороговая обработка;

‒ Классификация пикселей;

‒ Сегментация цветовых изображений;

‒ Выделение краев.

Пороговая обработка

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

Суть пороговой обработки заключается в разделении объектов изображения на два типа по признаку яркости. При пороговой обработке задается некое значение порога, относительно которого происходит разделение.

Классификации пикселей

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

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

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

Сегментация цветных изображений

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

Область можно описать как связанное подмножество пикселей, заданное в пространстве цветов.

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

Выводы

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

Литература:

  1. Гонсалес Р., Вудс Р. Цифровая обработка изображений. Москва: Техносфера, 2005.
  2. Васильев В. Н. Математические методы и алгоритмическое обеспечение анализа и распознавания изображений в информационно-телекоммуникационных системах / В. Н. Васильев, И. П. Гуров, А. С. Потапов // Всероссийский конкурс обзорно-аналитических статей по приоритетному направлению «Информационно-телекоммуникационные системы», URL: http://www.itc.edu.ru/itkonkurs2008/(дата обращения: 17.06.16).
  3. Работа каскада Хаара . URL: http://habrahabr.ru/company/recognitor/blog/228195/(дата обращения: 15.02.15).
  4. Компьютерная графика и мультимедия — Сетевой журнал. Выпуск № 4(2)/2006 — Усиления простых классификаторов . URL: http://cgm.computergraphics.ru/issues/issue12(дата обращения: 12.06.16).
  5. Работа алгоритма Viola Jones . URL: http://habrahabr.ru/post/134857/http://habrahabr.ru/post/134857/(дата обращения: 01.06.16).
  6. Обучение каскадного классификатора: . URL: http://recog.ru/blog/opencv/85.html (дата обращения: 14.06.16).
  7. Алгоритмы выделения параметрических кривых на основе преобразование Хафа . URL: http://cgm.computergraphics.ru/content/view/107 (дата обращения: 13.06.16).
  8. Метод Виолы-Джонса (Viola-Jones) как основа для распознавания лиц: . URL:http://habrahabr.ru/post/133826/ (дата обращения: 06.06.16).
  9. R. Lienhart, A. Kuranov, V. Pisarevsky. Empirical Analysis of Detection Cascades of Boosted Classifiers for Rapid Object Detection. MRL Technical Report, 2002
  10. Rosset, Zhu and Hastie. Boosting as a Regularized Path to a Maximum Margin Classifier. Journal of Machine Learning Research 5 (2004) 941–973, 2004.
  11. Yoav Freund and Robert E. Schapire. A Short Introduction to Boosting. Journal of Japanese Society for Artificial Intelligence, 14(5):771–780, September, 1999.

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

Пару слов о распознавании образов

Давно хотел написать общую статью, содержащую в себе самые основы Image Recognition, некий гайд по базовым методам, рассказывающий, когда их применять, какие задачи они решают, что возможно сделать вечером на коленке, а о чём лучше и не думать, не имея команды человек в 20.


Какие-то статьи по Optical Recognition я пишу давненько, так что пару раз в месяц мне пишут различные люди с вопросами по этой тематике. Иногда создаётся ощущение, что живёшь с ними в разных мирах. С одной стороны понимаешь, что человек скорее всего профессионал в смежной теме, но в методах оптического распознавания знает очень мало. И самое обидное, что он пытается применить метод из близрасположенной области знаний, который логичен, но в Image Recognition полностью не работает, но не понимает этого и сильно обижается, если ему начать рассказывать что-нибудь с самых основ. А учитывая, что рассказывать с основ — много времени, которого часто нет, становится всё ещё печальнее.
Эта статья задумана для того, чтобы человек, который никогда не занимался методами распознавания изображений, смог в течении 10-15 минут создать у себя в голове некую базовую картину мира, соответствующую тематике, и понять в какую сторону ему копать. Многие методы, которые тут описаны, применимы к радиолокации и аудио-обработке.
Начну с пары принципов, которые мы всегда начинаем рассказывать потенциальному заказчику, или человеку, который хочет начать заниматься Optical Recognition:

  • При решении задачи всегда идти от простейшего. Гораздо проще повесить на персону метку оранжевого цвета, чем следить за человеком, выделяя его каскадами. Гораздо проще взять камеру с большим разрешением, чем разрабатывать сверхразрешающий алгоритм.
  • Строгая постановка задачи в методах оптического распознавания на порядки важнее, чем в задачах системного программирования: одно лишнее слово в ТЗ может добавить 50% работы.
  • В задачах распознавания нет универсальных решений. Нельзя сделать алгоритм, который будет просто «распознавать любую надпись». Табличка на улице и лист текста — это принципиально разные объекты. Наверное, можно сделать общий алгоритм(вот хороший пример от гугла), но это будет требовать огромного труда большой команды и состоять из десятков различных подпрограмм.
  • OpenCV — это библия, в которой есть множество методов, и с помощью которой можно решить 50% от объёма почти любой задачи, но OpenCV — это лишь малая часть того, что в реальности можно сделать. В одном исследовании в выводах было написано: «Задача не решается методами OpenCV, следовательно, она неразрешима». Старайтесь избегать такого, не лениться и трезво оценивать текущую задачу каждый раз с нуля, не используя OpenCV-шаблоны.

Очень сложно давать какой-то универсальный совет, или рассказать как создать какую-то структуру, вокруг которой можно строить решение произвольных задач компьютерного зрения. Цель этой статьи в структуризации того, что можно использовать. Я попробую разбить существующие методы на три группы. Первая группа это предварительная фильтрация и подготовка изображения. Вторая группа это логическая обработка результатов фильтрации. Третья группа это алгоритмы принятия решений на основе логической обработки. Границы между группами очень условные. Для решения задачи далеко не всегда нужно применять методы из всех групп, бывает достаточно двух, а иногда даже одного.
Список приведённых тут методов не полон. Предлагаю в комментариях добавлять критические методы, которые я не написал и приписывать каждому по 2-3 сопроводительных слова.

Часть 1. Фильтрация

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

Бинаризация по порогу, выбор области гистограммы

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


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

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

Классическая фильтрация: Фурье, ФНЧ, ФВЧ

Классические методы фильтрации из радиолокации и обработки сигналов можно с успехом применять во множестве задач Pattern Recognition. Традиционным методом в радиолокации, который почти не используется в изображениях в чистом виде, является преобразование Фурье (конкретнее — БПФ ). Одно из немногих исключение, при которых используется одномерное преобразование Фурье, — компрессия изображений. Для анализа изображений одномерного преобразования обычно не хватает, нужно использовать куда более ресурсоёмкое двумерное преобразование.

Мало кто его в действительности рассчитывает, обычно, куда быстрее и проще использовать свёртку интересующей области с уже готовым фильтром, заточенным на высокие (ФВЧ) или низкие(ФНЧ) частоты. Такой метод, конечно, не позволяет сделать анализ спектра, но в конкретной задаче видеообработки обычно нужен не анализ, а результат.


Самые простые примеры фильтров, реализующих подчёркивание низких частот (фильтр Гаусса) и высоких частот (Фильтр Габора).
Для каждой точки изображения выбирается окно и перемножается с фильтром того же размера. Результатом такой свёртки является новое значение точки. При реализации ФНЧ и ФВЧ получаются изображения такого типа:

Вейвлеты

Но что если использовать для свёртки с сигналом некую произвольную характеристическую функцию? Тогда это будет называться «Вейвлет-преобразование». Это определение вейвлетов не является корректным, но традиционно сложилось, что во многих командах вейвлет-анализом называется поиск произвольного паттерна на изображении при помощи свёртки с моделью этого паттерна. Существует набор классических функций, используемых в вейвлет-анализе. К ним относятся вейвлет Хаара, вейвлет Морле, вейвлет мексиканская шляпа, и.т.д. Примитивы Хаара, про которые было несколько моих прошлых статей (1, 2), относятся к таким функциям для двумерного пространства.


Выше приведено 4 примера классических вейвлетов. 3х-мерный вейвлет Хаара, 2х-мерные вейвлет Мейера, вейвлет Мексиканская Шляпа, вейвлет Добеши. Хорошим примером использования расширеной трактовки вейвлетов является задачка поиска блика в глазу, для которой вейвлетом является сам блик:

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

Корреляция

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

Фильтрации функций

Интересным классом фильтров является фильтрация функций. Это чисто математические фильтры, которые позволяют обнаружить простую математическую функцию на изображении (прямую, параболу, круг). Строится аккумулирующее изображение, в котором для каждой точки исходного изображения отрисовывается множество функций, её порождающих. Наиболее классическим преобразованием является преобразование Хафа для прямых. В этом преобразовании для каждой точки (x;y) отрисовывается множество точек (a;b) прямой y=ax+b, для которых верно равенство. Получаются красивые картинки:

(первый плюсег тому, кто первый найдёт подвох в картинке и таком определении и объяснит его, второй плюсег тому, кто первый скажет что тут изображено)
Преобразование Хафа позволяет находить любые параметризуемые функции. Например окружности. Есть модифицированное преобразование, которое позволяет искать любые фигуры. Это преобразование ужасно любят математики. Но вот при обработке изображений, оно, к сожалению, работает далеко не всегда. Очень медленная скорость работы, очень высокая чувствительность к качеству бинаризации. Даже в идеальных ситуациях я предпочитал обходиться другими методами.
Аналогом преобразования Хафа для прямых является преобразование Радона . Оно вычисляется через БПФ, что даёт выигрыш производительности в ситуации, когда точек очень много. К тому же его возможно применять к не бинаризованному изображению.

Фильтрации контуров

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

  • Оператор Кэнни
  • Оператор Собеля
  • Оператор Лапласа
  • Оператор Прюитт
  • Оператор Робертса

Чаще всего используется именно Кэнни, который хорошо работает и реализация которого есть в OpenCV (Собель там тоже есть, но он хуже ищёт контуры).

Прочие фильтры

Сверху приведены фильтры, модификации которых помогают решить 80-90% задач. Но кроме них есть более редкие фильтры, используемые в локальных задачах. Таких фильтров десятки, я не буду приводить их все. Интересными являются итерационные фильтры (например активная модель внешнего вида), а так же риджлет и курвлет преобразования, являющиеся сплавом классической вейвлет фильтрации и анализом в поле радон-преобразования. Бимлет-преобразование красиво работает на границе вейвлет преобразования и логического анализа, позволяя выделить контуры:

Но эти преобразования весьма специфичны и заточены под редкие задачи.

Часть 2. Логическая обработка результатов фильтрации

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

Морфология

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

Контурный анализ

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

Если честно, то у меня ни разу ни получилось применить контурный анализ в реальных задачах. Уж слишком идеальные условия требуются. То граница не найдётся, то шумов слишком много. Но, если нужно что-то распознавать в идеальных условиях — то контурный анализ замечательный вариант. Очень быстро работает, красивая математика и понятная логика.

Особые точки

Особые точки это уникальные характеристики объекта, которые позволяют сопоставлять объект сам с собой или с похожими классами объектов. Существует несколько десятков способов позволяющих выделить такие точки. Некоторые способы выделяют особые точки в соседних кадрах, некоторые через большой промежуток времени и при смене освещения, некоторые позволяют найти особые точки, которые остаются таковыми даже при поворотах объекта. Начнём с методов, позволяющих найти особые точки, которые не такие стабильные, зато быстро рассчитываются, а потом пойдём по возрастанию сложности:
Первый класс. Особые точки, являющиеся стабильными на протяжении секунд. Такие точки служат для того, чтобы вести объект между соседними кадрами видео, или для сведения изображения с соседних камер. К таким точкам можно отнести локальные максимумы изображения, углы на изображении (лучший из детекторов, пожалуй, детектор Хариса), точки в которых достигается максимумы дисперсии, определённые градиенты и.т.д.
Второй класс. Особые точки, являющиеся стабильными при смене освещения и небольших движениях объекта. Такие точки служат в первую очередь для обучения и последующей классификации типов объектов. Например, классификатор пешехода или классификатор лица — это продукт системы, построенной именно на таких точках. Некоторые из ранее упомянутых вейвлетов могут являются базой для таких точек. Например, примитивы Хаара, поиск бликов, поиск прочих специфических функций. К таким точкам относятся точки, найденные методом гистограмм направленных градиентов (HOG).
Третий класс. Стабильные точки. Мне известно лишь про два метода, которые дают полную стабильность и про их модификации. Это SURF и SIFT. Они позволяют находить особые точки даже при повороте изображения. Расчёт таких точек осуществляется дольше по сравнению с остальными методами, но достаточно ограниченное время. К сожалению эти методы запатентованы. Хотя, в России патентовать алгоритмы низя, так что для внутреннего рынка пользуйтесь.

Часть 3. Обучение

ретья часть рассказа будет посвящена методам, которые не работают непосредственно с изображением, но которые позволяют принимать решения. В основном это различные методы машинного обучения и принятия решений. Недавно Яндыкс выложил на Хабр курс по этой тематике, там очень хорошая подборка. Вот оно есть в текстовой версии. Для серьёзного занятия тематикой настоятельно рекомендую посмотреть именно их. Тут я попробую обозначить несколько основных методов используемых именно в распознавании образов.
В 80% ситуаций суть обучения в задаче распознавания в следующем:
Имеется тестовая выборка, на которой есть несколько классов объектов. Пусть это будет наличие/отсутствие человека на фотографии. Для каждого изображения есть набор признаков, которые были выделены каким-нибудь признаком, будь то Хаар, HOG, SURF или какой-нибудь вейвлет. Алгоритм обучения должен построить такую модель, по которой он сумеет проанализировать новое изображение и принять решение, какой из объектов имеется на изображении.
Как это делается? Каждое из тестовых изображений — это точка в пространстве признаков. Её координаты это вес каждого из признаков на изображении. Пусть нашими признаками будут: «Наличие глаз», «Наличие носа», «Наличие двух рук», «Наличие ушей», и.т.д… Все эти признаки мы выделим существующими у нас детекторами, которые обучены на части тела, похожие на людские. Для человека в таком пространстве будет корректной точка . Для обезьяны точка для лошади . Классификатор обучается по выборке примеров. Но не на всех фотографиях выделились руки, на других нет глаз, а на третьей у обезьяны из-за ошибки классификатора появился человеческий нос. Обучаемый классификатор человека автоматически разбивает пространство признаков таким образом, чтобы сказать: если первый признак лежит в диапазоне 0.5<x<1, второй 0.7<y<1, и.т.д., тогда это человек.
По существу цель классификатора — отрисовать в пространстве признаков области, характеристические для объектов классификации. Вот так будет выглядеть последовательное приближение к ответу для одного из классификаторов (AdaBoost) в двумерном пространстве:


Существует очень много классификаторов. Каждый из них лучше работает в какой-то своей задачке. Задача подбора классификатора к конкретной задаче это во многом искусство. Вот немножко красивых картинок на тему.

Простой случай, одномерное разделение

Разберём на примере самый простой случай классификации, когда пространство признака одномерное, а нам нужно разделить 2 класса. Ситуация встречается чаще, чем может представиться: например, когда нужно отличить два сигнала, или сравнить паттерн с образцом. Пусть у нас есть обучающая выборка. При этом получается изображение, где по оси X будет мера похожести, а по оси Y -количество событий с такой мерой. Когда искомый объект похож на себя — получается левая гауссиана. Когда не похож — правая. Значение X=0.4 разделяет выборки так, что ошибочное решение минимизирует вероятность принятия любого неправильного решения. Именно поиском такого разделителя и является задача классификации.

Маленькая ремарка. Далеко не всегда оптимальным будет тот критерий, который минимизирует ошибку. Следующий график — это график реальной системы распознавания по радужной оболочке. Для такой системы критерий выбирается такой, чтобы минимизировать вероятность ложного пропуска постороннего человека на объект. Такая вероятность называется «ошибка первого рода», «вероятность ложной тревоги», «ложное срабатывание». В англоязычной литературе «False Access Rate «.

Что делать если измерений больше двух?

Алгоритмов много. Даже очень много. Если хотите подробно узнать про каждый из них читайте курс Воронцова, ссылка на который дана выше, и смотрите лекции Яндыкса. Сказать, какой из алгоритмов лучше для какой задачи часто заранее невозможно. Тут я попробую выделить основные, которые в 90% помогут новичку с первой задачей и реализацию которых на вашем языке программирования вы достоверно найдёте в интернете.
k-means (1, 2, 3 ) — один из самых простых алгоритмов обучения. Конечно, он в основном для кластеризации, но и обучить через него тоже можно. Работает в ситуации, когда группы объектов имеют неплохо разнесённый центр масс и не имеют большого пересечения.
AdaBoost (1, 2, 3) АдаБуста — один из самых распространённых классификаторов. Например каскад Хаара построен именно на нём. Обычно используют когда нужна бинарная классификация, но ничего не мешает обучить на большее количество классов.
SVM (1, 2, 3, 4 ) Один из самых мощных классификаторов, имеющий множество реализаций. В принципе, на задачах обучения, с которыми я сталкивался, он работал аналогично адабусте. Считается достаточно быстрым, но его обучение сложнее, чем у Адабусты и требуется выбор правильного ядра.
Ещё есть нейронные сети и регрессия. Но чтобы кратко их классифицировать и показать, чем они отличаются, нужна статья куда больше, чем эта.
________________________________________________
Надеюсь, у меня получилось сделать беглый обзор используемых методов без погружения в математику и описание. Может, кому-то это поможет. Хотя, конечно, статья неполна и нет ни слова ни о работе со стереоизображениями, ни о МНК с фильтром Калмана, ни об адаптивном байесовом подходе.
Если статья понравится, то попробую сделать вторую часть с подборкой примеров того, как решаются существующие задачки ImageRecognition.

И напоследок

Что почитать?
1) Когда-то мне очень понравилась книга «Цифровая обработка изображений» Б. Яне, которая написана просто и понятно, но в то же время приведена почти вся математика. Хороша для того, чтобы ознакомиться с существующими методами.
2) Классикой жанра является Р Гонсалес, Р. Вудс » Цифровая обработка изображений «. Почему-то она мне далась сложнее, чем первая. Сильно меньше математики, зато больше методов и картинок.
3) «Обработка и анализ изображений в задачах машинного зрения» — написана на базе курса, читаемого на одной из кафедр ФизТеха. Очень много методов и их подробного описания. Но на мой взгляд в книге есть два больших минуса: книга сильно ориентирована на пакет софта, который к ней прилагается, в книге слишком часто описание простого метода превращается в математические дебри, из которых сложно вынести структурную схему метода. Зато авторы сделали удобный сайт, где представлено почти всё содержание — wiki.technicalvision.ru
4) Почему-то мне кажется, что хорошая книжка, которая структурирует и увязывает картину мира, возникающую при занятии Image Recognition и Machine Learning — это «Об интеллекте» Джеффа Хокинса. Прямых методов там нет, но есть много мыслей на подумать, откуда прямые методы обработки изображений происходят. Когда вчитываешься, понимаешь, что методы работы человеческого мозга ты уже видел, но в задачах обработки видео.

Для того чтобы распознать двухмерную фигуру при работе с

1. В один из жарких летних дней Петя и его друг Вася решили купить арбуз. Они выбрали самый большой и самый спелый, на их взгляд. После недолгой процедуры взвешивания весы показали w килограмм. Поспешно прибежав домой, изнемогая от жажды, ребята начали делить приобретенную ягоду, однако перед ними встала нелегкая задача. Петя и Вася являются большими поклонниками четных чисел, поэтому хотят поделить арбуз так, чтобы доля каждого весила именно четное число килограмм, при этом не обязательно, чтобы доли были равными по величине. Ребята очень сильно устали и хотят скорее приступить к трапезе, поэтому Вы должны подсказать им, удастся ли поделить арбуз, учитывая их пожелание. Разумеется, каждому должен достаться кусок положительного веса.
Входные данные
В первой и единственной строке входных данных записано целое число w (1 ≤ w ≤ 100) — вес купленного ребятами арбуза.
Выходные данные
Выведите YES, если ребята смогут поделить арбуз на две части, каждая из которых весит четное число килограмм, и NO в противном случае.
Примечание
Например, ребята могут поделить арбуз на две части размерами 2 и 6 килограммов соответственно (другой вариант — две части 4 и 4 килограмма).
2. На клетчатой плоскости заданы координаты K зданий. Требуется построить кольцевую дорогу вокруг зданий минимальной длины в виде прямоугольника, со сторонами, параллельными линиям сетки.
Входные данные
Во входном файле, на первой строке, находится число K( ). На следующих K строках находятся пары чисел и – координаты зданий
( ).
Выходные данные
Выведите в выходной файл координаты левого нижнего и правого верхнего углов прямоугольника.
3. Хакер Иван является сотрудником крупной антивирусной компании. Один из вирусов исследованием, которого он занимается, был специально создан для атаки на программы биржевой торговли.
Для того что бы победить зловред Ване необходимо разработать алгоритм, который бы вычислил минимальное количество операций необходимых для того что бы пара чисел (a, b) стала «k -красивой». Пара чисел (a, b) называется «k-красивой» если хотя бы одно из чисел парны не меньше заданного целого числа k. При этом, операции, проводимые с парой чисел (a, b) могут быть только такие:
1. Пара (a, b) может быть преобразована в (a+b, b);
2. Пара (a, b) может быть преобразована в (a, b+a).
Помогите Ване победить.
Входные данные
Единственная строка входных данных содержит три целых числа a, b и k ( — 1018 ≤ x, y, m ≤ 1018).
Выходные данные
Выведите минимальное количество операций или число -1, если сделать заданную пару «k-красивой» невозможно.
4. Инженер-программист Надежда занимается разработкой компилятора для нового сверх секретного языка программирования. Для того чтобы закончить разработку одного из модулей ей остается решить задачу следующего содержания:
Во входных данных Надя получает строку содержащую в себе цифры и скобки одного вида: ‘(‘ и ‘)’. Наде необходимо написать программу, которая для любых входных данных определяет является ли содержащаяся в них скобочная последовательность правильной, и в случае правильности скобочной последовательности возвращает количество встречающихся в ней скобок, если же последовательность неправильная, то выводится число -1.
Скобочная последовательность называется правильной, если:
1. Пустая строка — правильная скобочная последовательность;
2. Правильная скобочная последовательность, взятая в скобки одного типа — правильная скобочная последовательность;
3. Правильная скобочная последовательность, к которой приписана слева или справа правильная скобочная последовательность — тоже правильная скобочная последовательность.
Помогите Наде в разработке компилятора для нового сверх секретного языка программирования.
Входные данные
Единственная строка конечной длины содержит цифры и скобки, длина строки не больше 1024 символов.
Выходные данные
Выведите количество скобок если скобочная последовательность правильная или число -1 если нет.
5. Маленький Вася научился считать сумму цифр для любого числа. Для любого числа, он считал сумму его цифр, затем тоже самое он делал с полученным в результате числом и так далее. Определите сколько раз Васе необходимо посчитать сумму, чтобы она стала цифрой.
Входные данные
Одна непустая строка с числом (0 Выходные данные
Одна строка, с числом.