СПОСОБ РЕДАКТИРОВАНИЯ СТАТИЧЕСКИХ ЦИФРОВЫХ КОМБИНИРОВАННЫХ ИЗОБРАЖЕНИЙ, ВКЛЮЧАЮЩИХ В СЕБЯ ИЗОБРАЖЕНИЯ НЕСКОЛЬКИХ ОБЪЕКТОВ
METHOD OF EDITING STATIC DIGITAL COMPOSITE IMAGES, INCLUDING IMAGES OF SEVERAL OBJECTS

Изобретение относится к способам обработки изображений, а более конкретно к способам редактирования статических цифровых комбинированных изображений, включающих в себя изображения нескольких объектов.
В последние годы приобретают все большую популярность многофункциональные устройства (МФУ). В таких устройствах сканер и принтер формируют единую связанную систему с множеством выполняемых задач и функций. Одним из примеров такой функциональности является автоматическое извлечение изображения объекта из сканированного изображения, то есть операция кадрирования, и его выравнивание. Более сложной, но не менее востребованной функцией является автоматическая обработка комбинированного изображения, включающего в себя изображения нескольких объектов.
Известны многочисленные разработки способов и устройств, призванных решать задачи, связанные с автоматической обработкой комбинированных изображений. В частности, известен способ, описанный в докладе Michael Guerzhoy and Hui Zhou. Segmentation of Rectangular Objects Lying on an Unknown Background in a Small Preview Scan Image. In Proc. of the Canadian Conference on Computer and Robot Vision, 2008 (CRV 2008) [1]. В докладе раскрывается способ сегментации прямоугольных объектов, располагающихся на слаботекстурированном фоне априорно неизвестного цвета. При этом используется метод приблизительного оценивания цвета фона, набор эвристических подходов для обнаружения сторон прямоугольных объектов и процедуры генерирования предварительных гипотез присутствия прямоугольных объектов на изображении с последующим выбором наиболее правдоподобных. Авторы доклада [1] утверждают, что описанное решение способно обнаруживать перекрывающиеся и смежные объекты, такие как фотографии, чеки или визитные карточки на изображении предварительного просмотра, обладающего очень малыми размерами. Тем не менее, применение описанного решения ограничено предположением о значительном цветовом различии между искомыми объектами и фоном.
Способ, описанный в работе С.Herley. Recursive method to detect and segment multiple rectangular objects in scanned images. IEEE Trans. Image Proc., 2003 [2], основан на идентификации и сегментации прямоугольных объектов, которые могут содержать различного рода искажения, как, например, неровные границы, сглаженные углы и т.п. Авторы работы [2] рассматривают построение одномерной проекции в качестве эффективного и устойчивого инструмента для сегментации. Причем авторы работы [2] исходят из предположения, что каждый объект представляет собой сплошную, связную область, и цель работы заключается в разделении этих объектов одного от другого на основании одномерных проекций. На практике объект зачастую может очень слабо отличаться от фона, вследствие чего использование описанного подхода приведет к тому, что объект будет восприниматься как множество разделенных в пространстве сегментов.
Способ, описанный в патенте США №7483589 [3], предусматривает автоматическое кадрирование нескольких документов, присутствующих на изображении, с последующим изменением их положения на изображении и выравниванием. В качестве возможного применения способа упоминается процедура копирования чеков, в результате которого на копии чеки выглядят выровненными и упорядоченными. Для автоматической сегментации изображений объектов используется пороговая обработка исходного изображения с последующим применением морфологических операций. Таким образом, результат сегментации зависит от связности элементов каждого из объектов. Если связность элементов будет нарушена, это приведет к искажению результатов сегментации.
Способ, описанный в патенте США №7542608 [4], предусматривает автоматическое кадрирование объектов на изображении и включает в себя следующие этапы: этап обнаружения контурных линий объектов, этап разделения изображений и этап объединения изображений. Для разделения изображений на область фона и множество областей переднего плана используется алгоритм нахождения связных компонент. Для объединения областей переднего плана вычисляется расстояние между ними, при этом, если расстояние меньше предопределенного значения, то производят объединение областей. Кроме того, производят объединение меньшей области с большей и при этом выполняют проверку целесообразности такого объединения, основанную на проверке размеров получающегося ограничивающего прямоугольника. Объединение считается нецелесообразным, если ширина и длина получаемого объекта превышает заданные значения. Такое условие ограничивает применение описанного способа, поскольку предполагает разделение объектов, чьи размеры приблизительно известны. Данное решение по своим признакам является наиболее близким к заявляемому изобретению и рассматривается в качестве прототипа.
Существует много проблем, с которыми приходится сталкиваться при разработке полностью автоматических методов сегментации нескольких объектов, присутствующих на одном изображении. Одна из наиболее сложных задач - это обнаружение на изображении светлых или белых объектов, которые при обработке могут быть фрагментированы на части. Второй значительной проблемой является разделение близко расположенных и перекрывающихся объектов. Обычно пользователям рекомендуют не располагать объекты слишком близко друг к другу при сканировании.
С учетом выявленных проблем заявляемое изобретение направлено на создание способа редактирования комбинированных изображений, сочетающего в себе как автоматические процедуры разделения и извлечения изображений объектов, так и возможность редактирования результатов пользователем.
Техническим результатом является предоставление пользователю пользовательского графического интерфейса, который обеспечивает возможность полуавтоматического редактирования цифровых комбинированных изображений, содержащих изображения нескольких объектов.
Заявлен способ редактирования статических цифровых комбинированных изображений, включающих в себя изображения нескольких объектов, посредством вычислительной системы, реализующей графический интерфейс пользователя и включающей в себя дисплей, память, интерфейсное устройство, состоящий из следующих этапов:
- определяют автоматически на комбинированном изображении координаты вершин прямоугольников, ограничивающих изображения объектов;
- визуализируют на дисплее ограничивающие прямоугольники, нанесенные на комбинированное изображение в соответствии с автоматически определенными координатами;
- выбирают с помощью интерфейса пользователя на комбинированном изображении объект в ответ на указание соответствующего ему ограничивающего прямоугольника;
- разделяют выбранное изображение объекта, как минимум, на два изображения объектов в ответ на предопределенные действия с помощью интерфейса пользователя;
- объединяют выбранное изображение объекта с другим изображением объекта в ответ на предопределенные действия с помощью интерфейса пользователя;
- обновляют координаты вершин ограничивающих прямоугольников, описывающих изображения объектов на комбинированном изображении;
- выполняют извлечение изображений объектов в соответствии с координатами вершин описывающих их ограничивающих прямоугольников.
Заявляемому изобретению присущи следующие усовершенствования, отличающие его от существующих решений в этой области:
- предлагается графический интерфейс пользователя в сочетании с автоматическим методом определения координат вершин ограничивающих прямоугольников; способ включает в себя преимущества автоматического метода извлечения изображений объектов, обеспечивающего скорость и минимум необходимых действий со стороны пользователя, а также гибкость ручной коррекции результатов автоматической обработки; наряду с этим предлагаются полуавтоматические решения для разделения изображения объекта на части или объединения нескольких изображений объектов в одно; известные способы предполагают ограниченные возможности редактирования, не включающие в себя полуавтоматические операции;
- для выявления наиболее значимых связных областей комбинированного изображения выполняется классификация областей; в зависимости от результатов классификации устанавливаются приоритеты автоматического анализа, позволяя улучшить качество сегментации;
- за счет обнаружения разделяющих участков фона комбинированного изображения появляется возможность исключить объединение даже близкорасположенных прямоугольных объектов.
Далее существо заявляемого изобретения поясняется с привлечением графических материалов.
Фиг.1 - пример графического интерфейса пользователя, реализующий заявленный способ редактирования статических цифровых комбинированных изображений, включающих в себя изображения нескольких объектов.
Фиг.2 - пример графического интерфейса пользователя, реализующий действие по выбору объекта, описанного ограничивающим прямоугольником.
Фиг.3 - иллюстрация действий для изменения размера и угла наклона ограничивающей рамки.
Фиг.4 - иллюстрация полуавтоматических действий для разделения одного объекта и объединения нескольких объектов.
Фиг.5 - иллюстрация системы для редактирования статических цифровых комбинированных изображений, включающих в себя изображения нескольких объектов.
Фиг.6 - блок-схема, иллюстрирующая принцип осуществления операций разделения и объединения объектов с помощью графического интерфейса пользователя.
Фиг.7 - блок-схема, иллюстрирующая принцип автоматического определения координат вершин ограничивающих прямоугольников.
Фиг.8 - блок-схема, иллюстрирующая принцип конвертирования исходного изображения в бинарное изображение.
Фиг.9 - блок-схема, иллюстрирующая принцип классификации связных областей на бинарном изображении.
Фиг.10 - пример, иллюстрирующий результаты классификации.
Фиг.11 - блок-схема, иллюстрирующая принцип объединения связных областей в группы.
Фиг.12 - пример, иллюстрирующий итерации объединения областей в группу.
В соответствии с заявленным вариантом осуществления настоящего изобретения предлагается способ редактирования статических цифровых комбинированных изображений, включающих в себя изображения нескольких объектов. Редактирование осуществляется посредством вычислительной системы, реализующей графический интерфейс пользователя (Фиг.1) и включающей в себя дисплей, память, интерфейсное устройство. Примерами такой системы являются все типы компьютеров, включая мобильные устройства, а также многофункциональные принтеры с сенсорным экраном. Графический интерфейс 101 пользователя, предназначенный для редактирования комбинированных изображений, включает в рассматриваемом варианте следующие ключевые элементы: окно 102 предварительного просмотра комбинированного изображения, содержащее изображения 104 объектов; визуализированные ограничивающие прямоугольники 103, определенные автоматически и после их ручного редактирования пользователем; интерфейсное устройство 106 пользователя, посредством которого осуществляются действия по редактированию ограничивающих прямоугольников; панель 105 параметров; панель 107 предварительного просмотра извлеченных объектов из комбинированного изображения, в соответствии с описывающими их ограничивающими прямоугольниками.
Ограничивающие прямоугольники определяют собой фрагмент исходного комбинированного изображения, который в результате редактирования будет извлечен из изображения и выровнен. Для корректировки возможных ошибок автоматического вычисления вершин ограничивающего прямоугольника и реализации предпочтений пользователя в графическом интерфейсе пользователя предусмотрены операции по редактированию ограничивающих прямоугольников путем изменения их размера, угла наклона и положения на исходном комбинированном изображении.
Фиг.2 иллюстрирует действие для выбора объекта, описываемого ограничивающей рамкой, в окне 201 предварительного просмотра комбинированного изображения. Объект выбирают посредством указания соответствующего ему ограничивающего прямоугольника с помощью курсора 203, управляемого интерфейсным устройством пользователя. Затем визуализация указанного ограничивающего прямоугольника изменяется, демонстрируя готовность системы приступить к его редактированию. Отличительной чертой редактируемого ограничивающего прямоугольника 202 является наличие на нем трансформирующих меток 204, манипулируя с которыми посредством интерфейсного устройства пользователь может осуществлять необходимые редактирующие действия. Повторное указание объекта приводит к отмене его выбора.
В качестве неограничивающего примера можно указать, что для осуществления интерфейсного устройства пользователя могут быть использованы устройства: «мышь», «сенсорный экран» и другие устройства, позволяющие пользователю взаимодействовать с компьютерной системой. В этом случае осуществление действия указания с помощью устройства «мышь» может быть выполнено путем нажатия и отпускания кнопки мыши (clicking).
На Фиг.3 проиллюстрированы способы пользовательского редактирования ограничивающего прямоугольника. Изменение ограничивающего прямоугольника 301 может быть осуществлено путем взаимодействия интерфейсного устройства пользователя, управляющего курсором 310, и специальных меток. Эти метки чаще всего располагаются на вершинах 304 ограничивающего прямоугольника и на середине 303 его сторон. Метки должны быть легко различимы в окне предварительного просмотра. В неограничивающем варианте заявленного изобретения метки используют для осуществления двух типов действий пользовательского редактирования ограничивающего прямоугольника: изменение размера и изменение угла наклона. В предпочтительном осуществлении заявленного изобретения активация одного из указанных действий зависит от расстояния между выбранной меткой и курсором интерфейсного устройства. Если курсор находится вплотную к метке и дистанция между ними не превышает предустановленного расстояния, то активируется режим изменения размера ограничивающего прямоугольника, обозначаемый курсором в виде стрелок 304, 306, 309, указывающих направления 305, 307, 309 допустимого перемещения метки и соответствующего ему изменения размера ограничивающего прямоугольника. В неограничивающем варианте осуществления заявленного изобретения для меток, расположенных на вершинах ограничивающего прямоугольника, допустимо пропорциональное изменение размера ограничивающего прямоугольника (стрелка 304), в результате которого перемещение метки приводит к одинаковому в процентном отношении изменению сторон (стрелка 305). Для меток, расположенных на середине сторон ограничивающего прямоугольника, допустимо изменение только в одном направлении (см. стрелки 306, 307). При расстоянии между ближайшей меткой и курсором, превышающем предустановленное расстояние, активируется режим изменения угла наклона ограничивающего прямоугольника (стрелка 309). В качестве центра поворота по умолчанию используется левая верхняя вершина 308 ограничивающего прямоугольника, обозначенная отличным от других образом. По желанию пользователя местоположение центра поворота может быть изменено посредством интерфейсного устройства пользователя. В других вариантах осуществления заявленного способа действия пользователя для редактирования ограничивающих прямоугольников реализуются другими способами, например путем использования ключевых кнопок на клавиатуре, как например стрелки, пробел, ввод и т.п.
Для упрощения редактирования ограничивающих прямоугольников предлагаются две полуавтоматические процедуры (Фиг.4): операция разделения участка комбинированного изображения, описанного выбранным ограничивающим прямоугольником, на составляющие его объекты и операция объединения выбранных объектов в один. На Фиг.4 (вид 4.1 и вид 4.2) приведен пример ограничивающего прямоугольника, описывающего участок комбинированного изображения, содержащий два изображения объектов, и действия пользователя по их разделению. Операция разделения изображения, описываемого выбранным ограничивающим прямоугольником 401, вызывается в ответ на действие «перетаскивание»/«перемещение» с помощью интерфейсного устройства пользователя (вид 4.1). Действие начинается на внутренней части ограничивающего прямоугольника и заканчивается на свободном участке изображения, незанятом другими объектами, описываемыми ограничивающими прямоугольниками. На иллюстрации курсор 402 черного цвета соответствует позиции курсора в начале действия «перетаскивания», курсор 403 серого цвета соответствует предполагаемой конечной позиции этого действия. После завершения перетаскивания (вид 4.2) инициируется автоматическая операция разделения участка изображения, описанного выбранным ограничивающим прямоугольником. Результат автоматического разделения проиллюстрирован на Фиг.4 (вид 4.2), где для каждого изображения объекта автоматически определен собственный ограничивающий прямоугольник. Если в ходе этой операции не удалось автоматически произвести разделение, тогда первоначальный ограничивающий прямоугольник остается без изменения. Тем не менее, пользователь может продолжить редактирование вручную, путем использования указанных выше действий.
На Фиг.4 (вид 3 и вид 4) проиллюстрирован пример объединения двух изображений объектов в один. Операция объединения изображений вызывается в ответ на действие «перетаскивание» с помощью интерфейсного устройства пользователя (вид 4.3). Действие начинается на внутренней части ограничивающего прямоугольника первого объекта и заканчивается на внутренней части ограничивающего прямоугольника второго объекта. На иллюстрации курсор 406 черного цвета соответствует позиции курсора в начале действия перетаскивание, курсор 495 серого цвета соответствует предполагаемой конечной позиции 407. Результирующий ограничивающий прямоугольник 408, изображенный на Фиг.4 (вид 4.4), описывает оба выбранных объекта.
Фиг.5 схематично иллюстрирует вычислительную систему, реализующую графический интерфейс пользователя. Вычислительная система для редактирования статических цифровых комбинированных изображений включает в себя: устройство 502 для ввода исходного комбинированного изображения, интерфейсное устройство 503 пользователя, дисплей 504, процессор 505, память 506. Передача данных между модулями системы осуществляется посредством шины 501 передачи данных. Проиллюстрированы только те признаки, которые упомянуты в описании. Однако следует понимать, что вычислительная система может иметь дополнительные признаки, которые не были проиллюстрированы. Вычислительная система может быть, например, персональным компьютером, мобильным телефоном, телевизором, многофункциональным печатающим устройством или быть любым другим электронным устройством, которое использует графический интерфейс пользователя.
Основные этапы взаимодействия пользователя и вычислительной системы для редактирования цифровых комбинированных изображений, содержащих несколько изображений объектов, схематически проиллюстрированы на Фиг.6. Способ начинает выполняться после ввода цифрового комбинированного изображения на шаге 601 посредством использования устройства 502. На шаге 602 выполняется автоматическое определение координат вершин ограничивающих прямоугольников для каждого изображения объекта, находящегося на комбинированном изображении. Шаг 602 осуществляется путем использования процессора 505 в соответствии с инструкциями, хранящимися в памяти 506. Вычисленные ограничивающие прямоугольники визуализируются на шаге 603 с помощью графического интерфейса пользователя, проиллюстрированного на Фиг.1, в виде рамок, расположенных в окне предварительного просмотра комбинированного изображения посредством дисплея 504. Если входное комбинированное изображение не содержит объектов и в результате выполнения шага 602 не было найдено ограничивающих прямоугольников, тогда шаг 603 ничего не изменит в графическом интерфейсе пользователя, что, однако, не мешает пользователю продолжить редактирование. После шага 603 вычислительная система готова к выполнению операций в ответ на действия пользователя. На шаге 604, проиллюстрированном на Фиг.2, осуществляется выбор объекта на комбинированном изображении в ответ на указание соответствующего этому объекту ограничивающего прямоугольника. Указание осуществляется путем использования интерфейсного устройства 503 пользователя, управляющего перемещением курсора 203 в окне графического интерфейса 201. Отображение ограничивающей рамки 202 выбранного объекта изменяется, демонстрируя готовность к редактированию. Если имеет место изменение положений трансформирующих меток в соответствии с примером, проиллюстрированным на Фиг.3, тогда на шаге 605 выполняется соответствующее им изменение координат вершин ограничивающего прямоугольника. Полуавтоматические процедуры для корректировки ограничивающих прямоугольников проиллюстрированы на Фиг.4. Изображение объекта, описанного выбранным ограничивающим прямоугольником 401, автоматически разделяют на шаге 606. Разделение осуществляется в ответ на действие «перетаскивание» с помощью интерфейсного устройства пользователя, начинающееся на выбранном изображении объекта и заканчивающееся на незанятом другими объектами участке комбинированного изображения (402 и 403). В случае, если действие «перетаскивание» заканчивается внутри ограничивающего прямоугольника другого объекта (см. 405), тогда на шаге 607 изображения объектов объединяются в одно изображение 408. Если были произведены действия, приводящие к изменению координат ограничивающих прямоугольников, тогда на шаге 608 осуществляется обновление их координат и соответствующие изменения визуализации на графическом интерфейсе пользователя. Указанные выше процедуры могут быть произведены столько раз, сколько это необходимо, до тех пор пока процесс редактирования не будет завершен. Момент завершения редактирования может быть определен, например, нажатием соответствующей кнопки на графическом интерфейсе пользователя. После этого на шаге 609 выполняется извлечение объектов из комбинированного изображения и выравнивание данных объектов соответственно их ограничивающим прямоугольникам. Выравнивание означает задание ориентации, при которой стороны прямоугольного объекта на изображении параллельны строкам и столбцам.
Основные шаги процедуры автоматического определения координат вершин ограничивающих прямоугольников, описывающих изображения объектов на комбинированном изображении, схематически проиллюстрированы на Фиг.7. На шаге 701 размер исходного комбинированного изображения изменяется (масштабируется) для соответствия предопределенному разрешению цифрового изображения. В неограничивающем примере заявленного способа предопределенное разрешение равняется 75 точкам на дюйм (dpi). Подобное уменьшение изображения позволяет уменьшить количество времени, потраченное вычислительной системой на выполнение описанных в заявленном способе процедур. Масштабированное изображение конвертируют в бинарное на шаге 702, в котором каждая точка соответствует переднему плану изображения или его фону. На шаге 703 определяют связные области переднего плана изображении и фона путем маркирования скоплений примыкающих друг к другу точек изображения. В результате выполнения этого шага элементы одной связной области будут обладать одинаковой меткой. Последующая классификация этих областей на шаге 704 предназначена для выявления наиболее значимых связных областей комбинированного изображения. В зависимости от результатов классификации далее устанавливаются приоритеты автоматического анализа на шаге 705, определяя последовательность и логику объединения связных областей в группы. Для результирующих групп связных областей выполняют вычисление координат вершин ограничивающих их прямоугольников на шаге 706.
Более подробная иллюстрация процедуры конвертации комбинированного изображения в бинарное (шаг 702) представлена на Фиг.8. Действие процедуры начинается с применения гамма-коррекции исходного цветного изображения на шаге 801 с последующим преобразованием в полутоновое изображение на шаге 802. Гамма-коррекция позволяет подчеркнуть слабоокрашенные области изображения. Последующие шаги 803 и 804 оперируют с одинаковым полутоновым изображением. На шаге 803 осуществляется детектирование контурных линий изображения, например, с помощью сравнения с предустановленным порогом результата фильтра Собеля. На шаге 804 осуществляется преобразование полутонового изображения в бинарное посредством его сравнения с предустановленным порогом. Результирующие бинарные изображения обоих шагов (803 и 804) объединяются на шаге 805 путем выполнения логической операцией ИЛИ между соответствующими пикселями объединяемых изображений. Такое объединение позволяет получить устойчивые признаки для последующего определения связных областей. Обнаружение контурных линий необходимо для светлых объектов, которые могли бы быть потеряны при пороговой обработке по яркости. Пороговая обработка по яркости позволяет получить сплошные области, препятствуя раздроблению на части изображений с текстурой. Последующие два шага применяются для уменьшения шумов на объединенном бинарном изображении. На шаге 806 осуществляется удаление одиночных точек и небольших связных областей, чья площадь меньше предустановленной минимальной величины. Для предпочтительного, но неограничивающего варианта осуществления заявленного способа минимальная площадь равняется восьмидесяти точкам для изображения с разрешением 75 точек на дюйм, что приблизительно соответствует пятну с диаметром 0.12 дюйма. Следующий шаг 807 предназначен для предотвращения ошибок сегментации вследствие появления протяженных узких областей вдоль границы изображения, примыкающих к краю изображения. Такой эффект часто встречается у сканированных изображений из-за неполного примыкания крышки сканера по краям. На шаге 807 выполняется обнаружение таких областей и их удаление из последующей обработки.
Фиг.9 схематически иллюстрирует основные шаги, выполняемые для классификации связных областей (шаг 704). Всего предполагается четыре категории связных областей: связные области переднего плана прямоугольной формы; связные области переднего плана в форме отрезков прямых линий; участки фона, расположенные между связными областями прямоугольной формы; неклассифицированные связные области переднего плана. Первый шаг классификации (шаг 901) включает в себя обнаружение отрезков прямых линий для каждой из сторон связной области переднего плана и оценку параметров этих линий, если они найдены. В неограничивающем варианте осуществления заявленного способа обнаружение отрезков прямых линий содержит следующие шаги: вычисляют горизонтальный ограничивающий прямоугольник для анализируемой связной области; каждой точке ограничивающего прямоугольника ставится в соответствие расстояние до ближайшей точки связанной области, при этом ближайшие точки связной области определяются строго вдоль горизонтального или вертикального направления (вдоль строки или столбца); вычисляют производные для векторов расстояний; выбирают горизонтальные участки для векторов производных, определяют соответствующее им значение производной; если суммарная протяженность участков с похожими значениями производной превышает предустановленное значение, тогда соответствующую сторону связной области обозначают как отрезок прямой линии и вычисляют параметры этой прямой. Необходимо отметить, что в других вариантах осуществления заявленного способа обнаружение прямых линий выполняют, например, с помощью преобразования Хафа и другими методами, позволяющими обнаруживать прямые линии на растровых бинарных изображениях.
Если взаимное расположение обнаруженных отрезков прямых линий исключает его соответствие прямоугольнику, в этом случае анализируемую связную область переднего плана обозначают как неклассифицированную область на шаге 902. В предпочтительном, но неограничивающем варианте осуществления заявленного способа взаимное расположение обнаруженных отрезков прямых линий соответствует прямоугольнику, если для разных сторон связанной области обнаружены, как минимум, два отрезка прямых линий, при этом угол пересечения пересекающихся линий близок к прямому углу (90°), а углы скоса для линий, расположенных на противолежащих сторонах связанной области, близки друг к другу в смысле евклидова расстояния. Связная область, для которой одна из сторон намного длиннее и длина меньшей стороны не превышает предустановленного значения, помечается как объект в виде отрезка прямой линии (шаг 904), иначе помечается как объект прямоугольной формы (шаг 903). В предпочтительном варианте осуществления заявленного способа указанное предустановленное значение равняется 10 точкам для разрешения изображения 75 точек на дюйм, что приблизительно соответствует длине в 0.13 дюйма. Дальнейшие шаги, иллюстрированные на Фиг.9, предназначены для вычисления координат вершин ограничивающего прямоугольника, описывающего анализируемую связанную область прямоугольной формы. Для области прямоугольной формы, ограниченной четырьмя отрезками прямых линий координаты ограничивающего прямоугольника вычисляются как точки пересечения этих линий (шаг 905), иначе оценивается угол скоса обнаруженных линий по сторонам области. Если разброс значений углов скоса меньше предустановленного значения, тогда координаты вершин ограничивающего прямоугольника измеряются путем построения профилей ортогональный проекций в направлении усредненного значения скоса (шаг 906). Иначе определяется сектор возможных углов скоса, и координаты вершин ограничивающего прямоугольника оцениваются в результате вычисления минимального профиля ортогональных проекций (шаг 907). Различный подход к вычислению координат ограничивающих прямоугольников позволяет уменьшить вычислительные расходы.
Для предотвращения объединения близкорасположенных областей выбираются наиболее достоверные объекты прямоугольной формы, при анализе которых были обнаружены отрезки прямых линий для каждой из сторон, если расстояние между такими областями не превышает порогового значения, тогда участок фона между ними помечается как разделяющий участок фона (шаг 908). В дальнейшем автоматическом анализе этот участок фона не может находиться на участке изображения, описанного ограничивающим прямоугольником.
Фиг.10 иллюстрирует основные результаты классификации: объекты в виде отрезков прямых линий (1001, 1002), объекты прямоугольной формы (1004, 1005), неклассифицированные объекты (1003) и разделяющий участок фона (1006) между близко расположенными прямоугольными объектами.
Более подробно процедура последовательного объединения связных областей переднего плана в группы (шаг 705) проиллюстрирована на Фиг.11. Процедура начинается с шага 1101, на котором выполняется проверка всех областей прямоугольной формы в порядке уменьшения площади для обнаружения их пересечения с ограничивающими прямоугольниками других областей. Если такое пересечение обнаружено, тогда эти области объединяются в группу, затем выполняется пересчет координат вершин их совокупного ограничивающего прямоугольника на шаге 1102. Пересчет координат включает в себя следующие этапы:
- проверяют пересечение совокупного ограничивающего прямоугольника с разделяющим участком фона, если такое пересечение обнаружено, тогда объединение областей в группу отменяется и в дальнейшем комбинация этих областей в составе одной группы не рассматривается;
- выполняют расчет координат вершин их совокупного ограничивающего прямоугольника по аналогии с шагами 906 или 907, при этом результирующая объединенная группа областей в дальнейшем анализе рассматривается как принадлежащая к категории областей прямоугольной формы.
Шаги 1101 и 1102 выполняются до тех пор, пока все области прямоугольной формы не будут проверены (как это указано на шаге 1101), включая новую проверку полученных на шаге 1102 групп областей. На шаге 1103 осуществляется поиск связных областей, отнесенных ранее к категории отрезков прямых линий. Здесь же выполняется проверка ряда условий, определяющих принадлежность этих областей к прямоугольным объектам. Условия включают в себя следующие этапы:
- выбирают связную область, классифицированную как отрезок прямой линий;
- вычисляют расстояние анализируемой связной области до ближайшего объекта прямоугольной формы;
- если вычисленное расстояние не превышает предопределенного допустимого значения, тогда вычисляют модуль разницы углов скоса между этими объектами;
- если модуль разницы углов скоса меньше предустановленного порогового значения, тогда считают, что связная область в виде отрезка прямой линии принадлежит к найденному ближайшему прямоугольному объекту, и заканчивают поиск;
- иначе исключают из поиска прямоугольные области, для которых условия не были выполнены и повторяют указанные выше этапы до тех пор, пока расстояние до ближайших прямоугольных объектов не превысит предопределенного допустимого значения.
В качестве неограничивающего примера осуществления заявленного способа предопределенное допустимое значение расстояния между областями равняется 1.5 дюйма, пороговое значение разницы между углами скоса областей равняется 1.15 градуса.
Если в результате выполнения шага 1103 были найдены связная область в виде отрезка прямой линии и прямоугольный объект, к которому она принадлежит, тогда на шаге 1104 эти области объединяются в группу. Здесь же осуществляется пересчет координат вершин их совокупного ограничивающего прямоугольника, при этом проверяется его пересечение с ограничивающими прямоугольниками других областей и с разделяющими участками фона по аналогии с шагами 1101, 1102.
На шаге 1105 осуществляется поиск близко расположенных групп областей и связных областей, в том числе отнесенных к категории неклассифицированных. В возможном варианте реализации этого шага расстояние между близко расположенными областями не должно превышать 0.33 дюйма. Если такие области обнаружены, тогда они объединяются в группы на шаге 1106, где также выполняется расчет координат вершин их совокупных ограничивающих прямоугольников, проверка пересечения с ограничивающими прямоугольниками других областей и с разделяющими участками фона. Если после выполнения указанных шагов остаются связные области (шаг 1108), неклассифицированные как объекты прямоугольной формы, и при этом обладающие площадью, превышающей пороговое значение, тогда для таких областей на шаге 1109 выполняется вычисление ограничивающего прямоугольника путем определения минимального профиля ортогональных проекций. В неограничивающем варианте осуществления заявленного способа площадь указанных областей должна превышать один квадратной дюйм, иначе область считается несущественной и расчет ограничивающего прямоугольника для нее не производится.
Фиг.12 иллюстрирует итерации объединения связных областей на бинарном изображении. Объединение областей в группу начинается с области 1201 и продолжается до тех пор, пока все области с пересекающимися ограничивающими прямоугольниками не будут объединены в одну группу.
Описанные выше операции относятся к автоматической процедуре вычисления ограничивающих прямоугольников без вмешательства пользователя, осуществляемой на шаге 602. Тем не менее, как это уже упоминалось выше, пользователь при необходимости может внести изменения в результаты, полученные автоматически. Поясним действие шага 606, выполняющего разделение участка комбинированного изображения на составляющие его объекты в ответ на соответствующие действия пользователя (на Фиг.4, вид 4.1, вид 4.2). Шаг осуществляется посредством выполнения следующих этапов:
- выбирают связные области, расположенные на участке бинарного изображения, в пределах выбранного ограничивающего прямоугольника;
- если количество выбранных связных областей равняется одному, считают разделение невозможным и выполняют выход из процедуры;
- если связных областей две, тогда вычисляют координаты вершин ограничивающих прямоугольников без учета их возможного пересечения и выполняют выход из процедуры;
- иначе определяют количество выбранных связных областей, отнесенных к категории объектов прямоугольной формы;
- если их количество больше двух, тогда вычисляют координаты вершин ограничивающих прямоугольников без учета их возможного пересечения и выполняют выход из процедуры;
- иначе выполняют процедуру последовательного объединения выбранных связных областей в группы в соответствии с шагом 705, проиллюстрированным на Фиг.9, при этом указанную процедуру останавливают за одну итерацию до момента объединения связных областей в одну группу. Для результирующих связных областей и полученных групп вычисляют координаты вершин ограничивающих прямоугольников без учета их возможного пересечения и выполняют выход из процедуры.
В случае если в ходе выполнения процедуры, осуществляющей шаг 606, разделение оказалось невозможным, тогда исходный ограничивающий прямоугольник остается без изменения, в случае успешного разделения как минимум на два объекта, он заменяется на совокупность полученных ограничивающих прямоугольников.
Предпочтительным вариантом осуществления заявленного способа является его реализация в многофункциональных печатающих устройствах или сканирующих устройств, поддерживающих графический интерфейс пользователя, или в их программном обеспечении. Примером практического применения способа является сканирование нескольких объектов, расположенных на рабочей поверхности сканера. Объектами могут быть, например, фотографии, листочки из блокнота, визитные карточки, чеки и так далее.