АВТОМАТИЗИРОВАННОЕ ОПРЕДЕЛЕНИЕ И ОБРЕЗКА НЕОДНОЗНАЧНОГО КОНТУРА ДОКУМЕНТА НА ИЗОБРАЖЕНИИ Российский патент 2019 года по МПК G06K9/62 G06T7/60 

ОБЛАСТЬ ТЕХНИКИ

[0001] Настоящее изобретение относится в целом к обработке изображений, а более конкретно - к системам и способам выявления контуров документов на цифровых изображениях при подготовке к последующей автоматизированной обработке цифровых изображений, включая автоматическую обрезку, оптическое распознавание символов (OCR) или трансформацию (исправление) перспективы.

УРОВЕНЬ ТЕХНИКИ

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[0003] Настоящее изобретение иллюстрируется с помощью примеров, а не способом ограничения, и может быть лучше понято при рассмотрении приведенного ниже описания предпочтительных вариантов реализации в сочетании с чертежами, на которых:

[0004] ФИГ. 1 иллюстрирует пример общего подхода к анализу цифрового изображения для обнаружения контура объекта в соответствии с одним или более вариантами реализации настоящего изобретения.

[0005] ФИГ. 2 представляет высокоуровневую архитектурную схему для вычислительного устройства, например, мобильного устройства, в котором реализован способ анализа и обнаружения контура по настоящему изобретению для получения контура объекта в соответствии с одним или более вариантами реализации настоящего изобретения.

[0006] ФИГ. 3А иллюстрирует пример цифрового изображения, содержащего множество документов, в соответствии с одним или более вариантами реализации настоящего изобретения.

[0007] ФИГ. 3В иллюстрирует пример цифрового изображения, содержащего множество перекрывающихся документов, которые выходят за пределы границ цифрового изображения в соответствии с одним или более вариантами реализации настоящего изобретения.

[0008] ФИГ. 4 иллюстрирует отдельный вариант реализации способа и подсистемы сжатия в соответствии с одним или более вариантами реализации настоящего изобретения.

[0009] ФИГ. 5 иллюстрирует отдельный вариант реализации способа и подсистемы сглаживания в соответствии с одним или более вариантами реализации настоящего изобретения.

[00010] ФИГ. 6 иллюстрирует отдельный вариант реализации способа и подсистемы свертки в соответствии с одним или более вариантами реализации настоящего изобретения.

[00011] ФИГ. 7 иллюстрирует отдельный вариант реализации способа и подсистемы, использующей пороговое значение, в соответствии с одним или более вариантами реализации настоящего изобретения.

[00012] ФИГ. 8 иллюстрирует отдельный вариант реализации способа и подсистемы обнаружения направления границ в соответствии с одним или более вариантами реализации настоящего изобретения.

[00013] ФИГ. 9 иллюстрирует отдельный вариант реализации другого способа и подсистемы обнаружения направления границ в соответствии с одним или более вариантами реализации настоящего изобретения.

[00014] ФИГ. 10 иллюстрирует отдельный вариант реализации другого способа и подсистемы обнаружения направления границ в соответствии с одним или более вариантами реализации настоящего изобретения.

[00015] ФИГ. 11 иллюстрирует отдельный вариант реализации другого способа и подсистемы обнаружения направления границ в соответствии с одним или более вариантами реализации настоящего изобретения.

[00016] ФИГ. 12 иллюстрирует отдельный вариант реализации другого способа и подсистемы обнаружения направления границ в соответствии с одним или более вариантами реализации настоящего изобретения.

[00017] ФИГ. 13 иллюстрирует отдельный вариант реализации способа и подсистемы обнаружения точки схода в соответствии с одним или более вариантами реализации настоящего изобретения.

[00018] ФИГ. 14 иллюстрирует отдельный вариант реализации способа и подсистемы группировки линий в соответствии с одним или более вариантами реализации настоящего изобретения.

[00019] ФИГ. 15 иллюстрирует отдельный вариант реализации способа и подсистемы формирования многоугольника-кандидата в соответствии с одним или более вариантами реализации настоящего изобретения.

[00020] ФИГ. 16 иллюстрирует отдельный вариант реализации другого способа и подсистемы оценки многоугольника-кандидата в соответствии с одним или более вариантами реализации настоящего изобретения.

[00021] ФИГ. 17 иллюстрирует отдельный вариант реализации способа и подсистемы обнаружения направления в соответствии с одним или более вариантами реализации настоящего изобретения.

[00022] ФИГ. 18 иллюстрирует отдельный вариант реализации другого способа и подсистемы обнаружения направления в соответствии с одним или более вариантами реализации настоящего изобретения.

[00023] ФИГ. 19 представляет собой блок-схему примера реализации способа обнаружения контура объекта в соответствии с одним или более вариантами реализации настоящего изобретения.

[00024] ФИГ. 20 иллюстрирует типичное изображение с цифровым кодированием в соответствии с одним или более вариантами реализации настоящего изобретения.

[00025] ФИГ. 21 иллюстрирует один вариант цветовой модели RGB в соответствии с одним или более вариантами реализации настоящего изобретения.

[00026] ФИГ. 22 иллюстрирует другую цветовую модель «Тон-насыщенность-светлота» (HSL) в соответствии с одним или более вариантами реализации настоящего изобретения.

[00027] ФИГ. 23 иллюстрирует формирование серого или бинаризованного изображения из цветного изображения в соответствии с одним или более вариантами реализации настоящего изобретения.

[00028] ФИГ. 24 иллюстрирует дискретный расчет градиента яркости в соответствии с одним или более вариантами реализации настоящего изобретения.

[00029] ФИГ. 25 иллюстрирует градиент, рассчитанный для точки на непрерывной поверхности, в соответствии с одним или более вариантами реализации настоящего изобретения.

[00030] ФИГ. 26 иллюстрирует ряд примеров для градиента яркости в соответствии с одним или более вариантами реализации настоящего изобретения.

[00031] ФИГ. 27 иллюстрирует применение ядра к изображению в соответствии с одним или более вариантами реализации настоящего изобретения.

[00032] ФИГ. 28 иллюстрирует свертку ядра с изображением в соответствии с одним или более вариантами реализации настоящего изобретения.

[00033] ФИГ. 29 иллюстрирует пример ядра и методики обработки изображений на основе ядра в соответствии с одним или более вариантами реализации настоящего изобретения.

[00034] ФИГ. 30А иллюстрирует пример вычислительного устройства в соответствии с одним или более вариантами реализации настоящего изобретения.

[00035] ФИГ. 30В иллюстрирует другой пример вычислительного устройства в соответствии с одним или более вариантами реализации настоящего изобретения.

[00036] ФИГ. 31 иллюстрирует блок-схему иллюстративного вычислительного устройства, работающего в соответствии с примерами осуществления настоящего изобретения.

ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ

[00037] В настоящем изобретении рассматриваются способы и системы, направленные на улучшение определения контуров объектов в цифровых изображениях. Обычно проблемы возникают при попытке распознать контуры объектов, которые неоднозначно представлены на изображении. Контур объекта может быть неоднозначно представлен на изображении, когда объект частично перекрыт, повернут в кадре, скомкан или поврежден оптическим искажением (например, перспективой). Например, может возникнуть проблема при определении контуров изображения, включающего в себя несколько документов с частями, которые перекрываются, не перекрываются, смещены (например, документы, повернутые в разные стороны), выровнены или комбинация вышеуказанного. Традиционные методы определения контуров часто опираются исключительно на отслеживание контура с использованием методов обнаружения границ и могут основываться на типичных геометрических свойствах объектов. Традиционные методы могут плохо работать для определения контуров, которые неоднозначно представлены на изображении.

[00038] Особенности настоящего изобретения исправляют вышеупомянутые и другие недостатки, используя одну или несколько точек схода изображения (vanishing points). Точка схода - это абстрактная точка относительно плоскости изображения, которая может указывать на место схождения параллельных линий. Точка схода может упоминаться как точка схождения или точка направления, на которую часто влияет перспектива устройства захвата изображения. Системы и методы настоящего изобретения решают задачу определения одной или более точек схода для изображения, а затем решают задачу оценки контуров кандидата на основе одной или более точек схода. В одном примере объектом может быть документ, который выходит за пределы изображения, и относительно документа можно определить две или более точки схода. Первая точка схода может быть определена на основе набора горизонтальных линий, обнаруженных на изображении, а вторая точка схода может быть определена на основе набора вертикальных линий, обнаруженных на изображении. Точки схода могут использоваться для создания и оценки одного или более многоугольников-кандидатов, которые представляют контуры одного или нескольких документов на изображении. Затем изображение может быть преобразовано с учетом многоугольника, представляющего конкретный документ. Преобразование может включать кадрирование изображения так, чтобы оставался только конкретный документ или документ изменялся для настройки перспективы.

[00039] Системы и методы настоящего изобретения включают технологию, которая улучшает обнаружение контуров объекта на изображении. В частности, особенности настоящего изобретения могут более точно определять контуры объектов, которые искажены или скрыты. Использование одной или более точек схода может улучшить обнаружение объектов с параллельными линиями, хотя перспективное искажение делает такие линии в изображении непараллельными. Особенности настоящего изобретения могут также уменьшать требования к вычислительным ресурсам (например, вычислительную мощность или память) и могут предоставлять возможность определения контуров объектов на пользовательских устройствах (например, смартфоне, планшете или другом вычислительном устройстве). Например, использование точки схода может уменьшить количество боковых пар (например, верх/низ и правый/левый), а также количество анализируемых многоугольников-кандидатов.

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

[00041] ФИГ. 1 иллюстрирует пример общего подхода к использованию точек схода для определения контура. Подход реализуется на примере цифрового изображения 100, на котором запечатлена стопка документов на столе, расположенном рядом со стеной с обоями, где имеется окно, из которого виден внешний пейзаж. Цифровое изображение 100 может проходить этапы обработки цифровых изображений 110А-С, чтобы определить контур 109 документа 102, который может находиться поверх стопки документов. Могут быть выполнены дополнительные или альтернативные этапы обработки цифрового изображения, которые могут использоваться для распознавания и классификации физических объектов на изображении, включая стол, стопку, оконную раму, другие функции или их комбинацию. Описываемый в настоящем документе способ определения контуров подразумевает различные ограничения и параметры для управления определением контуров с целью установления контуров для конкретных целей.

[00042] Обработка изображений 110А-С является примером, используемым для анализа цифрового изображения 100, и в результате могут быть получены представления изображений 120А-С соответственно. Обработка изображения 110А может включать в себя анализ пикселей цифрового изображения 100 для определения одной или более затравочных точек 104 и может приводить к карте затравочных точек, показанной представлением изображения 120А. Каждая из затравочных точек 104 может быть начальной точкой кандидата и соответствовать одному или более пикселям цифрового изображения 100. Обработка изображения 110А может определить затравочные точки 104, потому что затравочная точка имеет градиент изображения (например, интенсивность цвета или яркости), которая превышает соседние точки. Это более подробно обсуждается ниже по отношению к ФИГ. 5-8.

[00043] Обработка изображения 110В может использовать затравочные точки 104 для определения линий 106 и точек схода 108А и 108В. Как показано на представлении изображения 120В, линии 106 могут включать в себя несколько линий, соответствующих краям и границам физических объектов. Каждая из линий может быть основана на одной или более затравочных точках 104, которые продлены в одном или более направлениях. Каждая из точек схода 108А и 108В может быть определена на основе, по меньшей мере, двух линий 106. Например, точка схода кандидата может быть выбрана на основе пары линий и оценена в зависимости от количества других линий, которые будут соответствовать точке схода кандидата. Может быть выбрана точка схода кандидата, соответствующая большинству линий. Определение и оценка точек схода обсуждаются ниже по отношению к ФИГ. 13.

[00044] Обработка изображения 110С может использовать линии 106 и точки схода 108А и 108В для определения контура 109. Контур 109 может быть выбран из нескольких разных многоугольников-кандидатов, оценивающихся с учетом множества параметров (например, критериев оценки), которые более подробно обсуждаются ниже. Каждая обработка изображения 110А-С может включать в себя множество процессов. Эти процессы могут основываться на формировании и сохранении различных многочисленных типов промежуточных результатов и данных. В различных вариантах реализации способов и систем настоящего изобретения могут использоваться различные типы представления данных и промежуточных результатов. Например, в одном варианте реализации изобретения промежуточный результат может быть представлен двумерной картой с элементами, соответствующими пикселям на цифровом изображении, но в другом варианте реализации он может быть представлен сохраненными данными со ссылками на исходное изображение.

[00045] ФИГ. 2 иллюстрирует блок-схему примера вычислительного устройства 100, которое включает в себя компоненты и модули для выполнения обработки изображения с целью определения контуров объектов в соответствии с одним или несколькими вариантами реализации настоящего изобретения. Вычислительное устройство 100 может включать в себя компонент предобработки изображения 220, компонент определения линии 220, компонент точки схода 230 и контурный многоугольный компонент 240. Вычислительное устройство 100 может быть пользовательским устройством (например, смартфоном, планшетом или другим мобильным устройством) или серверным устройством (например, облачным сервисом) либо их комбинацией. Могут быть включены меньше или больше компонентов без потери общности. Например, два или более компонента или части компонентов могут быть объединены в один компонент или один из компонентов может быть разделен на два или более модулей. В одном варианте реализации изобретения один или несколько модулей могут исполняться различными вычислительными устройствами (например, частично на пользовательском устройстве и частично на серверном устройстве).

[00046] Компонент предобработки изображения 220 может анализировать цифровое изображение и сформировать одну или несколько структур данных, которые представляют и хранят дату цифрового изображения. Компонент предобработки изображения 220 может изменять цифровое изображение для оптимизации последующей цифровой обработки изображения. В одном примере компонент предобработки изображения 220 может включать в себя модуль доступа к изображению 212, модуль регулировки разрешающей способности 214 и модуль сглаживания 216.

[00047] Модуль доступа к изображению 212 может получать доступ к цифровому изображению 251, полученному вычислительным устройством 100. Цифровое изображение 251 может иметь любой формат и приниматься вычислительным устройством 100 по сети или получаться вычислительным устройством 100. К цифровому изображению 251 можно получить доступ в месте, локальном для вычислительного устройства (например, внутреннем хранилище, съемном хранилище, вложенном хранилище) или месте, удаленном от вычислительного устройства (например, по сети). Это изображение может быть впоследствии сохранено в хранилище данных 250.

[00048] Модуль регулировки разрешающей способности 214 может позволить вычислительному устройству 100 изменять количество деталей, предоставленных цифровым изображением 251, путем уменьшения, увеличения или изменения разрешающей способности цифрового изображения 251. Разрешающая способность изображения может быть представлена как размер в пикселях и может включать длину и высоту в пикселях. Модуль регулировки разрешающей способности 214 может изменять длину и/или высоту цифрового изображения, чтобы уменьшить количество деталей, представленных на цифровом изображении 251. Модуль регулировки разрешающей способности 214 может изменять цифровое изображение 251 с сохранением пропорций цифрового изображения 251 или без него. В одном примере модуль регулировки разрешающей способности 214 может изменять цифровое изображение 251, чтобы средняя длина и высота составляли приблизительно 350 пикселей, а соотношение сторон - приблизительно 1.0.

[00049] Модуль сглаживания 216 может изменить цифровое изображение 251, пытаясь получить важные шаблоны в данных и удалить шум или другие визуальные дефекты (артефакты изменения разрешающей способности). Модуль сглаживания 216 может использовать один или более различных способов для сглаживания цифрового изображения 251, и эти методы могут включать в себя линейные или нелинейные преобразования цифрового изображения 251. Модуль сглаживания 216 может изменить цифровое изображение 251 на основе одного или более медианных фильтров либо фильтров Гаусса, как обсуждается ниже по отношению к ФИГ. 5.

[00050] Модуль сглаживания 216 может также или альтернативно выполнять морфологические преобразования для извлечения или размытия частей цифрового изображения 251. Морфологические преобразования могут использоваться для сглаживания цифрового изображения 251 вдоль одной или более направленных линий и включать удаление «пробелов» в цифровом изображении 251. Морфологические преобразования могут включать в себя выбор пикселей и сравнение выбранных пикселей с окружающими их пикселями (например, соседними), а также сохранение выбранных пикселей с наименьшими, наибольшими или промежуточными значениями. Морфологическое преобразование может включать в себя эрозию цифрового изображения, которая уменьшает яркость пикселей, окруженных менее яркими соседними пикселями. Эрозия точки может быть минимумом точек в ее конкретной окрестности. Окрестность обсуждается более подробно ниже и может быть определена конкретным элементом структурирования (например, матрицей). Морфологическое преобразование может включать в себя функции морфологии в градациях серого (например, эрозия в серых тонах), которые выполняются для изображений на уровне серого (например, изображений с серой шкалой), и функции бинаризованной морфологии, которые выполняются для бинаризованных изображений (например, черно-белых изображений).

[00051] Компонент обнаружения линии 220 может позволить вычислительному устройству 100 анализировать цифровое изображение 251 и определять одну или более линий 254. Линии 254 могут представлять края объектов в цифровом изображении 251. Каждая из линий 254 может иметь начальную и конечную точки и включать в себя по меньшей мере одну начальную точку. Линии 254 могут включать прямые участки, изогнутые участки или их комбинацию. В одном примере компонент обнаружения линии 220 может включать в себя модуль градиента изображения 222, модуль обнаружения затравочной точки 224 и модуль прослеживания линии 226.

[00052] Модуль градиента изображения 222 может использоваться для анализа цифрового изображения 251 и определения градиентов изображения цифрового изображения 251. Градиент изображения может быть направленным изменением яркости изображения. Яркость может быть основана на яркости пикселей, и яркость пикселя может быть основана на одном или более значениях пикселя (например, R, G, В), причем чем выше значение, тем ярче пиксель. Градиент функции яркости изображения может быть представлен вектором, возникающим в каждой точке изображения. Вектор может быть двухмерным и иметь компоненты, заданные производными в горизонтальном и вертикальном направлениях. В каждой точке изображения вектор градиента может указывать в направлении наибольшего возможного увеличения яркости, а длина вектора градиента может соответствовать скорости изменения в этом направлении. Градиенты изображения могут храниться в одной или более структурах данных, таких как карта, таблица или сетка, и могут включать в себя ячейки, которые представляют точки в цифровом изображении 251. В одном примере градиенты изображения могут быть сохранены в карте градиента 252 и представлять градиенты во множестве точек (например, всех точек) в цифровом изображении 251.

[00053] Модуль обнаружения затравочной точки 224 может получить доступ к карте градиента 252 и определить набор затравочных точек 253 в цифровом изображении 251. Затравочные точки 253 могут быть пикселями в цифровом изображении 251, которые выбраны, поскольку имеют градиенты яркости (например, изменения яркости) больше, чем окружающие их пиксели. Затравочные точки 253 могут быть определены путем выполнения свертки с использованием ядра немаксимального подавления (non-maximum-suppression, NMS). Это подробно обсуждается по отношению к ФИГ. 6 и может включать в себя доступ к карте градиента 252 для создания одной или более точечных карт, которые представляют соответствующие локальные максимальные модули градиента. Порог может применяться к картам точек для определения точек в цифровом изображении 251, которые содержат наибольшие значения модуля градиента.

[00054] Модуль прослеживания линии 226 может получить доступ к затравочным точкам 253 и может распространять одну или несколько затравочных точек 253 для создания линий 254. Модуль прослеживания линии 226 может сортировать затравочные точки 253 на основе яркости или изменения яркости, а также выбирать затравочную точку, имеющую наибольшее соответствующее значение. Модуль прослеживания линии 226 может анализировать выбранную затравочную точку с учетом карты градиента 252 для определения направления продления затравочной точки. Затравочная точка может быть увеличена в одном или более направлениях. Если затравочная точка продляется только в одном направлении, она может функционировать как начало или конец линии. Если затравочная точка продляется в нескольких направлениях, она может лежать вдоль линии, но не может быть ни начальной, ни конечной точкой линии. Определение направления или направлений для продления затравочной точки обсуждается по отношению к ФИГ. 8-12.

[00055] Линии 254, которые обнаруживаются модулем прослеживания линии 226, могут включать в себя линии, внешние или внутренние по отношению к объекту, или их комбинацию. Линии, внешние по отношению к объекту, могут быть внешними краями объекта, а прямые, внутренние для объекта, могут быть линиями в пределах границ объекта и вдоль содержимого объекта. Например, если объектом является документ, внешние линии могут быть линейными или нелинейными краями документа, а внутренние линии могут быть прослеженными линиями вдоль текстовых строк документа. Как внутренние, так и внешние линии могут использоваться для определения контура объекта, как описано ниже.

[00056] Компонент точки схода 230 может определять одну или несколько точек схода 256 для цифрового изображения 251. Точка схода может упоминаться как точка сведения или точка направления и может быть абстрактной точкой относительно плоскости изображения, которое указывает кажущееся из-за перспективного искажения место соединения параллельных линий. Перспективное искажение может быть деформированием или преобразованием объекта и его окружающей области при получении устройством захвата изображения. Полученный объект может отличаться от того, как будет выглядеть объект с нормальным фокусным расстоянием и с относительным масштабом соседних и отдаленных объектов. Часто перспективное искажение возникает, когда угол обзора вычислительного устройства, получающего изображение, является более широким или узким, чем угол обзора, с которого просматривается изображение. В одном примере компонент точки схода 230 может включать в себя модуль определения пересечения 232, модуль оценки точки 234 и модуль выбора точки 236.

[00057] Модуль определения пересечения 232 может получать доступ к линиям 254 и определять точки пересечения 255, которые соответствуют линиям 254. Точки пересечения 255 могут упоминаться как продленная точка пересечения или гипотетическая точка пересечения, поскольку каждая точка пересечения 255 может указывать, где, по меньшей мере, две отдельные линии пересекались, если бы одна или более линий были продолжены до тех пор, пока линии не пересекались. Точка пересечения может быть абстрактной точкой вдоль плоскости изображения цифрового изображения 251 и может лежать за границей цифрового изображения 251.

[00058] Модуль идентификации пересечения 232 может определить точки пересечения 255 путем выбора одной или более пар линий из линий 254. Как обсуждалось выше, линии 254 могут включать в себя внешние линии, которые соответствуют внешним границам объекта и внутренним линиям, которые соответствуют содержимому в границах объекта (например, текстовые строки внутри документа). Внутренние линии, внешние линии или их комбинация могут использоваться модулем идентификации пересечения 232. Модуль идентификации пересечения 232 может разделять линии 254 на один или более наборов, и пару линий могут быть выбраны из одного или разных наборов. В одном примере линии 254 могут быть разделены на набор практически горизонтальных и набор практически вертикальных, и обе линии пары могут быть выбраны из одного и того же набора. В другом примере линии 254 могут быть разделены на четыре разных множества, которые соответствуют линиям-кандидатам для верхних, нижних, левых и правых границ объектов соответственно. Каждая линия пары может быть выбрана из другого набора линий. Например, первая пара линий может включать в себя линию, выбранную из набора верхних границ кандидата, и линию, выбранную из набора нижних границ кандидата. Аналогично, вторая пара линий может включать в себя линию, выбранную из набора левых границ кандидатов, и линию, выбранную из набора нижних границ кандидатов. В любом примере выбор пары линий из набора линий может быть случайным или основан на данных, связанных с точкой вдоль линии (например, затравочной точкой, начальной точкой, конечной точкой, промежуточной точкой), местоположением, длиной, кривизной линии, другими данными (например, параметром оценки) или их комбинацией.

[00059] Модуль идентификации пересечения 232 может затем продлить одну или более линий выбранной пары, используя экстраполяцию (например, линейную экстраполяцию). Экстраполяция может включать вычисление одной или более касательных линий вдоль линии или на конце линии и оценка точки, где касательные линии пары линий пересекаются одна с другой. Точка может соответствовать одной или более координатам относительно цифрового изображения 251. Одна или более координат могут быть основаны на системе координат, связанной с цифровым изображением 251. Система координат может быть такой же или подобной декартовой системе координат (например, координаты x и у), цилиндрической системой координат, сферической системой координат, другой системой координат или их комбинацией. Модуль определения пересечения 232 может затем добавить координаты в набор, который представляет точки пересечения 255.

[00060] Модуль оценки точки 234 может получать доступ к определенным точкам пересечения 255 и оценивать точки пересечения для определения точки схода. Модуль оценки точки 234 может выбирать несколько точек пересечения из множества точек пересечения 255 и может определять количество линий, которые соответствуют каждой из точек пересечения. Определение того, соответствует ли линия точке пересечения, может состоять в определении того, указывает ли линия на точку пересечения в пределах заданного порога. Предопределенный порог может быть основан на заданном угловом смещении. Угловое смещение может представлять собой угловое расстояние (например, угловое разделение) между продленным вариантом линии и точкой пересечения кандидатов. В одном примере определение углового смещения может заключаться в определении угла между линией и направлением к точке пересечения. В другом примере определение углового смещения может включать в себя определение углового вращения, которое должно быть применено к линии, чтобы сделать ее экстраполяцию пересекающей точку пересечения кандидатов. Экстраполяция может быть такой же или аналогичной описанной выше методике экстраполяции в отношении определения точки пересечения. Предустановленный порог может быть скорректирован для оптимизации обнаружения точек схода, и может быть в качестве примера задано значение меньшее 15°.

[00061] Модуль выбора точки 236 может выбирать точку пересечения в качестве точки схода для цифрового изображения 251 с учетом вывода модуля оценки точки 234. Модуль выбора точки 236 может использовать вышеупомянутую методику оценки для выбора нескольких точек схода для определенного цифрового изображения. В примере, детально показанном ниже на ФИГ. 13, первая точка схода может быть определена на основе набора горизонтальных линий, обнаруженных на изображении, а вторая точка схода может быть определена на основе набора вертикальных линий, обнаруженных на изображении. В одном примере модуль выбора точки 236 может выбирать точку схода, анализируя несколько точек пересечения и сортируя точки пересечения на основе количества соответствующих линий. В другом примере модуль выбора точки 236 может использовать метод итерационного машинного обучения для выбора точки схода 256 на основе одной или нескольких точек пересечения 255.

[00062] Метод итерационного машинного обучения может начинаться с выбора текущего значения точки схода (например, значения по умолчанию или случайно выбранных координат точки пересечения). Затем модуль выбора точки 236 может затем оценить одну или более точек пересечения и сравнить количество линий, связанных с точкой пересечения, с количеством линий, связанных с текущей точкой схода. Модуль выбора точки 236 может затем заменить текущую точку схода точкой пересечения, когда количество линий, соответствующих точке пересечения, превышает число линий, соответствующих текущей точке схода. Модуль выбора точки 236 может продолжать итерацию через разные точки пересечения до тех пор, пока не будет обнаружено условие выхода. Условие выхода может быть основано на общем количестве итераций, количестве итераций с момента последней замены, количестве доступных кандидатов, времени, доступности вычислительных ресурсов, другом условии или их комбинации.

[00063] В одном примере метод итерационного машинного обучения может включать в себя метод случайных выборок (RANSAC). Метод RANSAC может использоваться для оценки точки схода с помощью случайных данных выборки, наблюдаемых в цифровом изображении 251 (например, линий 254, точек пересечения 255). Учитывая набор данных, элементы данных которого содержат как неискаженные измерения, так и аномалии, RANSAC может использовать схему голосования для поиска оптимального результата соответствия. Элементы данных в наборе данных используются для голосования за одну или несколько моделей (например, точек пересечения). Внедрение этой схемы голосования может основываться на предположении, что функции шума не будут последовательно голосовать для какой-либо одной модели (несколько аномалий), и что есть достаточно возможностей для утверждения хорошей модели (несколько отсутствующих данных).

[00064] Метод RANSAC может включать в себя выборку поднабора, содержащего элементы данных, которые произвольно выбираются из входного набора данных (например, точек пересечения 255 или линий 254). Подходящая модель и соответствующие параметры модели вычисляются с использованием элементов этого подмножества образцов. Количество поднаборов образцов является наименьшим достаточным для определения параметров модели. Этот метод может включать проверку того, какие элементы всего набора данных согласуются с моделью, созданной с помощью параметров оцениваемой модели. Элемент данных (например, линия) может рассматриваться как аномалия, если он не соответствует модели согласования (например, точке пересечения), созданной набором параметров оцениваемой модели в пределах некоторого порога для ошибки, который определяет максимальное отклонение, обусловленное эффектом шума. Максимальное отклонение может быть таким же или аналогичным упомянутому выше угловому смещению. Набор показателей, полученных для модели соответствия, называется набором консенсуса. Алгоритм RANSAC может итеративно повторять описанный выше процесс до тех пор, пока полученный консенсус, установленный на определенной итерации, не будет иметь достаточных неискаженных признаков.

[00065] Метод RANSAC может состоять из нескольких этапов, которые включают в себя выбор случайного поднабора линий 254, которые могут упоминаться как гипотетические неискаженные значения. Затем модель может применяться к набору гипотетических неискаженных значений. Затем все остальные данные проверяются на соответствие применяемой модели. Точки, которые соответствуют оцениваемой модели согласно определенной функцией потерь по модели, могут рассматриваться как часть множества консенсуса. Оцениваемая модель может считаться лучше, чем предыдущая, если достаточно много точек классифицированы как часть установленного набора консенсуса (например, больше соответствующих линий, чем в ранее проанализированной модели). Впоследствии текущая модель может быть улучшена путем ее переоценки с использованием всех участников множества консенсуса. Эта процедура повторяется определенное количество раз, каждый раз производя либо модель, которая отклоняется, потому что слишком мало точек является частью набора консенсуса, либо точной модели вместе с соответствующим размером набора консенсуса. В последнем случае точная модель сохраняется, если ее набор консенсуса больше, чем ранее оцененная модель.

[00066] Контурный многоугольный компонент 240 может получать доступ к данным компонента обнаружения линии 220 и компоненту точки схода 230, а также использовать его для определения многоугольника, который лучше всего представляет контуры объекта на цифровом изображении 251. В одном примере контурный многоугольный компонент 240 может включать в себя модуль формирования многоугольника 242 и модуль оценки многоугольника 244.

[00067] Модуль формирования многоугольника 242 может формировать один или несколько многоугольников 257 на основе линий, обнаруженных компонентом обнаружения линии. Каждый из многоугольников 257 может включать в себя множество линий 254 и представлять собой контур кандидата объекта. Множество линий, которые организованы в цепочку линий (например, сторон). В одном примере каждая линия в цепочке может быть выбрана из линий 254 и может быть продлена (например, экстраполирована) таким образом, чтобы линия в цепочке пересекалась с другой линией в цепочке. Это может привести к появлению многоугольника, называемого замкнутым многоугольником. В другом примере по меньшей мере одна линия в цепочке может не быть непосредственно связана с другой линией внутри цепочки, и, следовательно, между сторонами многоугольника может возникнуть зазор. Это может привести к появлению многоугольника, называемого незамкнутым многоугольником (например, открытого многоугольника). Количество линий, включенных в многоугольник, может меняться в зависимости от настраиваемого параметра, который зависит от ожидаемого количества сторон типа целевого объекта. Если тип целевого объекта является документом, количество линий в многоугольнике может быть четыре, и поэтому многоугольник может быть четырехугольным. Если выбраны другие типы целевых объектов, количество линий в многоугольнике может быть больше или меньше четырех. Построение многоугольников более подробно обсуждается ниже на ФИГ. 15.

[00068] Многоугольник 257 может включать в себя одну или более линий, которые выходят за пределы цифрового изображения 251. Это может быть полезным, поскольку цифровое изображение 251 может не включать весь объект, и часть объекта может существовать вне границ цифрового изображения 251. Методы обработки прошлых изображений могут использовать границу изображения как часть многоугольника-кандидата, если существующая альтернатива недоступна. Это может привести к системе обнаружения контуров, которая не сможет создать исправленный многоугольник или не сможет правильно оценить ближайший многоугольник. Включение одной или более линий многоугольника для выхода за пределы границы изображения позволяет многоугольнику более точно представлять фактические контуры объекта, а также оптимизирует оценку, выполняемую модулем оценки многоугольника 244.

[00069] Модуль оценки многоугольника 244 может оценивать множество многоугольников-кандидатов, сформированных компонентом формирования многоугольников 242, и может выбирать многоугольник, который лучше всего представляет контуры объекта в цифровом изображении 251. Модуль оценки многоугольника 244 может оценивать каждый многоугольник на основе одного или более параметров. Параметры могут быть основаны на особенностях многоугольника 257, линий 254, точек схода 256, точек пересечения 255, затравочных точек 253, цифрового изображения 251, других данных или их комбинации. Приведенные ниже примеры параметров могут относиться к точкам схода и размерам многоугольника. Дополнительные параметры и методы оценки обсуждаются на ФИГ. 16.

[00070] Параметры для оценки многоугольника могут быть основаны на одном или более измерениях многоугольника. Размеры многоугольника могут относиться к измерениям сторон, углов, областей, другим измерениям или их комбинациям. Примеры параметров могут включать в себя: длины сторон многоугольника 257, площадь многоугольника 257, отношение сторон многоугольника 257 относительно отношения сторон цифрового изображения 251, отношение длины стороны многоугольника 257 относительно длины соответствующей обнаруженной линии 254, на которой она основана, углы между противоположными сторонами многоугольника-кандидата (верхняя и нижняя стороны или левая и правая стороны), углы внутри четырехугольника, углы схождения соседних сторон, углы наклона сторон относительно оси ориентации (например, оси системы координат), местоположение (например, координаты) углов многоугольника, отношение среднего веса прослеживаемых точек, которые перекрывают сторону многоугольника со средним весом точки, которые перекрывают сегмент за пределами четырехсторонней стороны, цвет области ColorOut (например, 5 пикселей) за пределами прослеживаемой стороны для каждого цветового канала, цвет области ColorIn (например, 5 пикселей) внутри границ четырехугольника прослеживаемой стороны для каждого цветового канала, разница между областями ColorOut и ColorIn.

[00071] Параметры для оценки многоугольника могут также или альтернативно быть основаны на одной или более характеристиках точек схода 256 или положении точек схода относительно многоугольника-кандидата. Как обсуждалось выше, для оценки многоугольника-кандидата можно использовать одну или несколько точек схода. Параметры, связанные с точками схода, могут включать в себя ряд линий, соответствующих точке схода, пропорцию линий относительно всех линий, которые соответствуют или не соответствуют точке схода, направление линии, указывающей на точку схода, расстояние до точки схода, расстояние до ближайшей точки схода и вес ближайшей точки схода. Расстояния могут быть определены по углам от линий, направленных от центров противоположных сторон многоугольника (например, горизонтальных или вертикальных сторон).

[00072] Модуль оценки многоугольника 244 может объединять один или более параметров оценки для многоугольника-кандидата и оценивать их с использованием метода машинного обучения. Комбинация может быть линейной или нелинейной комбинацией, и метод машинного обучения может оценивать модель прогнозирования в виде набора моделей неполного прогнозирования (например, деревьев решений). Метод машинного обучения может использовать бустинг (boosting) поход, который формирует модель прогнозирования поэтапно и может обобщать модели неполного прогнозирования, позволяя оптимизировать произвольную дифференцируемую функцию потерь. В одном примере метод машинного обучения может быть таким или аналогичным методу градиентного бустинга. Градиентный бустинг может объединять слабых «учеников» в одного сильного ученика в итеративном режиме. После оценки одного или более многоугольников-кандидатов Модуль оценки многоугольника 244 может выбрать многоугольник-кандидат с максимальным качеством. Затем модуль оценки многоугольника 244 может указывать, что многоугольник-кандидат представляет контуры цифрового изображения 251 объекта.

[00073] На ФИГ. 3А и 3В представлены примеры цифровых изображений 300 и 306, имеющие документы с неоднозначными контурами. ФИГ. 3А содержит цифровое изображение 300 стопки документов 302. Стопка документов 302 может включать в себя несколько перекрывающихся документов, которые смещены, так что один или более документов могут быть повернуты по сравнению с одним или более другими документами в стопке 302. Документ 304 может располагаться сверху стопки 302 и может перекрывать и скрывать один или более других документов в стопке 302. ФИГ. 3В может включать в себя цифровое изображение 306 с двумя перекрывающимися документами 308А и 308В. Документы 308А и 308В могут лежать на столе, и части обоих документов могут лежать вне границ цифрового изображения 306, в результате чего фрагменты текста на документах оказываются скрыты. Документ 308А может свисать с стола, и документ 308В может быть перевернут (например, повернут приблизительно на 180°). Может быть, что ни один из документов не лежит на столе, и в результате оба документа могут иметь края, которые являются нелинейными (например, изогнутыми). Кроме того, цифровое изображение 306 может быть захвачено устройством захвата изображения под углом, который может создавать перспективное искажение.

[00074] Следует сразу же отметить, что методы настоящего изобретения и системы могут определять фрагменты изображений документов с нелинейными границами, в том числе документы, искаженные при обработке изображения, в связи с искажением перспективы и иными оптическими эффектами, физическим искажением документов из-за скомкания или сгиба, а также документы с искривленными границами в их нормальной физической форме. В примере на ФИГ. 3А содержащий текст документ 304 и базовые документы в стопке документов 302 могут иметь линейные и нелинейные края. Для удобства иллюстрации и ясности описания стопка документов 302 показана с линейными краями, но изображения документов с нелинейными краями легко распознаются процессами распознавания документов, рассмотренными ниже.

[00075] На ФИГ. 4-15 представлены подробные, поэтапные иллюстрации для облегчения понимания примера реализации способа и системы. Функции, обсуждаемые в этом примере, могут быть частью подкомпонента автоматизированной системы распознавания текста, которая пытается определить документы с цифровыми изображениями для создания электронных документов, соответствующих стопке документов.

[00076] ФИГ. 4 иллюстрирует сжатие цифрового изображения 300, которое может уменьшить вычислительные ресурсы, занятые последующей обработкой и хранением. Цифровое изображение 300 может быть сжато, сохраняя соотношение сторон (например, отношение высоты и ширины) на том же значении. Цифровое изображение 300 может быть представлено в виде таблицы или сетки клеток, которые соответствуют значениям пикселей и могут иметь высоту 402 и ширину 404 в пикселях. В этом примере разница между высотой и шириной цифрового изображения 300 составляет 512 пикселей.

[00077] Цифровое изображение 300 может быть сжато для создания одного или более сжатых изображений 410А и 410В, которые могут быть сжаты с использованием различных коэффициентов сжатия. Сжатое изображение 410А может быть сжато с использованием коэффициента сжатия 3/4 (например, 75%) и имеет разницу между шириной и высотой, равной 128 пикселям. Сжатое изображение 410В может быть сжато с использованием коэффициента сжатия 1/2 (например, 50%) и имеет разницу между шириной и высотой, равную 256 пикселям. В описываемом варианте реализации изобретения цифровое изображение 300 сжимается с одним или более коэффициентами сжатия для создания одного или более соответствующих сжатых изображений, где разность между шириной и высотой изображения ниже порогового числа пикселей, например, ниже 300 пикселей. Для сжатия цифрового изображения могут использоваться различные способы. В одном примере сжатие может использовать обнаружение равномерно распределенных строк и колонок пикселей и удаление их из исходного изображения для создания сжатых изображений. В другом примере сжатие может использовать способы сглаживания, сдвига и интерполяции, чтобы уменьшить вероятность того, что желаемые детали будут случайно удалены или изменены во время операции сжатия.

[00078] На ФИГ. 5 показан другой этап обработки в примере процесса обнаружения контура, где версия исходного изображения подвергается одной или более операциям сглаживания. Версия исходного изображения может быть основана на цифровом изображении 300 или на одном сжатом изображении 410A и 410В на ФИГ. 4. Изображение 501 может быть сглажено с использованием любой операции сглаживания цифрового изображения и может содержать медианный фильтр, свертку с гауссовым ядром, другую операцию или их комбинацию. Операция сглаживания может создавать соответствующее сглаженное изображение 510. Горизонтальное градиентное ядро G_x и вертикальное градиентное ядро G_y могут применяться к каждому цветному каналу (например, красный зеленый синий (RGB)) сглаженного изображения. Это может привести к образованию трех пар горизонтально-градиентных и вертикально-градиентных компонентных карт 520A-F.

[00079] Например, ядро горизонтальной компоненты градиента, прошедшее свертку с красным каналом сглаженного изображения 510, может создавать карту горизонтальной компоненты градиента для красного канала 520А. Понятие «G_i(X)» используется для указания на свертку ядра компоненты градиента в направлении i с цветовым каналом X изображения, так и для указания на карту компоненты градиента, создаваемую при свертке. При формировании и сохранении в памяти шести карт компонент градиента 520A-F или, как вариант, при их оперативном формировании модули компонент градиента могут быть определены и использованы для создания «карты градиента» 540. Каждый элемент карты градиента, такой как элемент 542 (например, «i»), включает в себя соответствующий модуль градиента 544 и угол направления 546.

[00080] Математические расчеты 530 иллюстрируют, как вычисляется карта градиента 540. На шаге 1624 сумма абсолютных значений компонентов градиента может быть вычислена для одного или более цветовых каналов и может храниться в переменных R_i, G_i и B_i. Если R_i превышает G_i в соответствии с определением на шаге 1626 и, если R_i превышает В_i в соответствии с определением на шаге 1628, на шаге 1630 рассчитывается градиент для клетки или пикселя i с использованием компонент градиента для красного канала. Если R_i не превышает ни G_i, ни B_i, то на шаге 1632 определяется, является ли B_i больше G_i. Если В_i превышает G_i, то на шаге 1634 на основе компонента градиента синего канала рассчитывается модуль и направление градиента для клетки или пикселя i. В ином случае модуль и угол направления градиента рассчитываются по компонентам градиента зеленого канала на шаге 1636.

[00081] Вычисления, проиллюстрированные на 1624, 1626, 1628, 1630, 1632, 1634 и 1636, могут быть повторены для одного или более пикселей (например, каждой клетки i) в сглаженном изображении 510. В некотором примере свертки переносятся на пикселях изображения, над которыми может быть наложено ядро, и в этом случае карта, созданная сверткой, может иметь меньше колонок и строк, чем исходная карта. В других примерах либо исходное изображение расширяется, поэтому ядра могут быть применены ко всем пикселям изображения, либо используются модифицированные ядра для граничных пикселей. Поэтому, карта градиента 540 может быть картой модулей и направлений градиентов для каждого пикселя (например, элемента 542) сглаженного изображения, при этом градиент для каждого пикселя основан на цветовом канале сглаженного изображения, для которого сумма компонент градиента является максимальной.

[00082] ФИГ. 6 иллюстрирует пример ядра немаксимального подавления (NMS) 601. Ядро NMS 601 содержит три области: (1) центральный пиксель 603; (2) непосредственная окрестность 605; и (3) расширенная окрестность 607. Применение ядра NMS для пикселей подразумевает такое наложение ядра NMS, чтобы область центрального пикселя 603 ядра NMS 601 накладывалась на пиксель, к которому применяется ядро. Применение ядра определяет, передается ли яркость пикселя, к которому применяется ядро, или наоборот, передается ли на карту или изображение значение яркости 0. Если яркость расположенного ниже центрального пикселя выше яркости расположенного ниже пикселя в непосредственной окрестности и если яркость пикселя под областью центрального пикселя выше или равна яркости любого пикселя, лежащего ниже расширенной окрестности, то на образующееся изображение или карту передается значение яркости центрального пикселя. В ином случае на образующееся изображение или карту передается значение 0. Этот процесс принятия решения формально выражен в математическом сравнении 611. При свертке ядра NMS с изображением или картой выбираются пиксели изображения с локальной максимальной яркостью для передачи на образующуюся карту или изображение.

[00083] На ФИГ. 7 показаны этапы в примере определения последовательности контуров для формирования точечной карты с показаниями затравочных пикселей, рассмотренных выше, со ссылкой на карту затравочных точек ФИГ. 1 (например, представление изображения 120А). Карта градиента 702, сформированная в ходе описанного выше процесса, может быть свернута с ядром NMS для создания промежуточной карты точек 704. Ядро NMS может рассматривать компоненту модуля градиента для каждой клетки карты градиента и передавать модули максимальных локальных градиентов с карты градиента на промежуточную карту точек 704. Порог 705 может быть применен к карте промежуточной точки 704 для создания карты точек 706, которая содержит модули с наибольшим значением градиента, при этом другие клетки содержат значение 0 как результат свертки NMS-ядра или установления порога. В некоторых примерах может быть создана отсортированная карта точек 710 и индекс 712, которые содержат ссылки на затравочные пиксели на карте точек 706. Индекс 712 может сортироваться по убыванию модулей градиента, поэтому большая часть перспективных затравочных пикселей обрабатываются с более высоким приоритетом, чем менее перспективные затравочные пиксели. Альтернативные примеры процесса могут использовать отсортированный массив структур данных, содержащих координаты и модуль градиента для одного или более затравочных пикселей, а не сохраняет разреженную карту точек.

[00084] На ФИГ. 8-12 показано, как определить направление для продления точки для создания линии или расширения существующей линии. Определение направления для продления точки может быть основано на ранее сформированной карте точек 706, карте отсортированных точек 710 или других структурах данных, содержащих затравочные точки, которые обсуждались выше. На ФИГ. 8 показана типичная точка 1902 карты точек 710 и множество стрелок, которые представляют собой направления потенциальных дуг. Из заданного затравочного пикселя или точки на карте точек 1902 исходный контур может иметь одно из более возможных направлений, показанных стрелками, например, стрелкой 1904. На шаге 1906 выбора исходного направления границы выбирается конкретное направление для линии, представляющей потенциальный контур, и создается вектор 1908 длинной L, конец которого соответствует затравочному пикселю 1902, а направление совпадает с выбранным направлением. Линия - это сегмент с двумя конечными точками, соответствующими концу и началу построенного вектора. В следующем обсуждении векторы могут альтернативно упоминаться как «сегменты», поскольку, как обсуждается ниже, линия (например, контур, граница) может быть представлена элементами, содержащими векторы или сегменты. Векторы могут быть комплектом векторов «от начала до конца» и могут иметь начальную точку, модуль и угол направления, а сегменты могут иметь начальную и конечную точки (например, координаты).

[00085] На ФИГ. 9 представлен расчет модуля проекции градиента пикселя р вдоль вектора исходного контура r, исходящего из затравочного пикселя или затравочной точки i. Как показано на ФИГ. 9, предполагаемый исходный вектор r 2002 для вектора, совпадающего с затравочным пикселем i 2004, рассматривается в процессе выбора направления для продления точки с целью формирования линии. Пиксель р 2006 расположен вдоль вектора r 2002. Имеется вектор градиента 2008, связанный с пикселем р на карте градиента. Этот вектор градиента имеет угол направления θ_р 2010, который также доступен на карте градиента. Угол 2012, θ_r, является углом направления для вектора r. Угол ψ 2014 является углом между вектором градиента для пикселя р и вектором r 2002. Вектор pr 2016 является проекцией вектора градиента 2008 на вектор r 2002. В показанных конструкциях угол ψ легко рассчитывается на основе углов направлений θ_р и θ_r 2218. Отношение модулей векторов pr и вектора градиента для пикселя р равно косинусу угла ψ 2220. Таким образом, модуль вектора проекции pr вычисляется как произведение косинуса ψ и модуля вектора градиента, исходящего из пикселя р 2222. Как вариант, для расчета модуля вектора проекции pr 2224 может использоваться скалярное произведение вектора градиента 2002 и вектора r. Замена результата 2222 на выражение скалярного произведения дает выражение для определения модуля вектора проекции pr 2226.

[00086] На ФИГ. 10 показано формирование промежуточных вычисленных значений, которые используются для выбора направления продления затравочных пикселей. На ФИГ. 10 показан затравочный пиксель с координатами (х, y) 2102 вместе с кандидатом вектора 2104. Для кандидата вектора границы создаются промежуточные результаты, 2108 и H_(х,y,r) 2110, где r является вектором 2104 и также называется направлением начальной границы, при этом фактически имеется в виду угол направления вектора r. Имеется 10 пикселей, включая затравочный пиксель 2102, которые лежат под вектором 2104, представляющим кандидата начального контура. Значение вычисляется как сумма модулей проекций векторов, связанных с пикселями i₁-i₁₀, разделенная на количество элементов набора пикселей под начальным контуром. H_(х,y,r) является гистограммой 2112, на которой направление градиента пикселей под вектором начального контура представлено в виде бинов гистограммы. Как показано в выражении 2114, количество пикселей, зарегистрированных в каждом бине H_i гистограммы, соответствует количеству пикселей направлений градиента в интервале направлений, представленных бином. Бин 2116 с максимальным значением соответствует общему направлению градиента пикселей под начальным контуром. При правильном направлении начального контура направление вектора 2104 должно быть в общем перпендикулярно направлениям градиента пикселей под вектором 2104.

[00087] На ФИГ. 11 представлена схема управления для определения направления продления затравочного пикселя. На шаге 2202 процесс получает координаты затравочного пикселя. На шаге 2204 происходит инициализация набора кандидатов к пустому набору. Набор кандидатов является набором структур данных кандидатов, каждое из которых включает направление r и значение В for-цикле 2206-2213 шагов рассматривается каждое направление r от 0° до 360°. Следует, опять же, отметить, что r в настоящем описании считается как вектором, так и направлением, где направление представляет собой направление ориентации вектора r. На шаге 2207 для рассматриваемого направления вычисляется гистограмма H_(х,y,r). На шаге 2208 для бина с максимальным значением в Н_(х,y,r) устанавливается индекс j. На шаге 2209 определяется, является ли направление r перпендикулярным углу в диапазоне углов, соответствующих бину с максимальным значением и его ближайшим соседям.

[00088] Если направление r является перпендикулярным углу в этом диапазоне, то на шаге 2210 определяется, превышает ли значение или число пикселей, назначенное бину с максимальным значением, пороговое значение В. Если да, то на шаге 2211 рассчитывается значение для рассматриваемого направления и, на шаге 2212 в набор кандидатов добавляется запись для рассматриваемого направления. В ином случае направление r удаляется из набора направлений кандидатов. После завершения for-цикла 2206-2213 шагов, если количество кандидатов в наборе составляет меньше 0, как определено на шаге 2214, то на шаге 2215 возвращается вектор со значением 0 для указания на то, что предпочтительное направление контура для затравочного пикселя не может быть установлено. В ином случае на шаге 2216 выбирается один кандидат из набора с максимальным значением . Если значение для выбранного кандидата превышает пороговое значение , как определено на шаге 2218, то на шаге 2220 возвращается направление r, содержащееся у выбранного кандидата. В ином случае на шаге 2215 возвращается нулевой вектор, указывающий на невозможность определения направления для затравочного пикселя. Таким образом, выбор исходного направления контура для затравочного пикселя включает выбор направления, согласованного с направлениями векторов градиента для пикселей в окрестности исходного контура, когда имеется консенсус в окрестности с учетом направления градиента.

[00089] На ФИГ. 12 показан выбор конкретного направления для продления линии. Процесс продления линии является таким же или аналогичным процессу выбора начального направления затравочной точки, как описано выше. При этом в процессе продления контура следующий вектор длины L продлевается из конечного пикселя строящейся линии, а не продлевается из затравочной точки в одном или более противоположных направлениях. Как показано на ФИГ. 12 следующий кандидат вектора 2302 продлен из конечного пикселя 2304 формируемого контура. В этом случае в качестве направлений кандидатов рассматриваются только направления с углом 2α 2306. Иными словами, следующий отрезок контура 2302 может быть наклонен относительно направления предыдущего уже существующего отрезка контура 2308 на угол до α. В ином случае процесс выбора направления аналогичен процессу выбора направления для начальных векторов, соответствующих начальному контуру для затравочного пикселя. Сразу же после обнаружения линий процесс обнаружения контура может определять одну или более точек схода.

[00090] На ФИГ. 13 показан процесс идентификации и оценки одного или более кандидатов точек схода 1330А, 1330В на цифровом изображении 300. Точка схода может упоминаться как точка сведения или точка направления и может быть абстрактной точкой относительно плоскости изображения и может указывать кажущееся, из-за перспективного искажения, место соединения параллельных линий. Кандидаты точек схода 1330А и 1330В могут быть определены на основании точек пересечения 1320А и 1320В соответственно. Точки пересечения 1320А и 1320В могут упоминаться как продленная точка пересечения или гипотетическая точка пересечения, поскольку каждая точка пересечения может указывать, где, по меньшей мере, две отдельные линии пересекались, если бы одна или более линий были продолжены до тех пор, пока линии не пересекались. Точка пересечения может быть абстрактной точкой вдоль плоскости изображения цифрового изображения 300 и может лежать за границей цифрового изображения 300. В показанном примере существует два разных набора линий (например, набор горизонтальных линий и набор вертикальных линий), и каждый набор линий может использоваться для определения соответствующего набора точек пересечения и точек схода.

[00091] Точки пересечения 1320А, 1320В могут быть определены путем выбора пар линий из одного или более линейных множеств 1312А, 1312В. Набор линий 1312А может быть основано на выявлении линии 1310A и может представлять собой по существу горизонтальные линии, а набор линий 1312В может быть основано на выявлении линии 1310В и может представлять собой по существу вертикальные линии. В качестве примера линия может быть «по существу горизонтальной», когда она имеет направление ориентации от 0 до 45° или от 135° до 180° от оси ориентации и может быть «по существу вертикальной», когда она имеет направление ориентации между 45 и 135° от оси ориентации. Ориентирующая степень может по умолчанию установить горизонтальную ось цифрового изображения 300 и может обновляться при определении ориентации цифрового изображения.

[00092] Выбор пары линий из соответствующего набора линий может быть случайным или может быть основан на данных, связанных с точкой вдоль линии (например, затравочной точкой, начальной точкой, конечной точкой, промежуточной точкой), линией местоположения, длиной линии, кривизной линии, другими данными или с их комбинацией. После выбора пары линий одна или более линий пары могут быть продлены с помощью экстраполяции (например, линейной экстраполяции). Экстраполяция может содержать вычисление одной или более касательных линий вдоль линии или на конце линии и оценку точки, в которой касательные линии пары линий пересекаются одна с другой. Точка может соответствовать одной или более координатам относительно цифрового изображения 300. Одна или более координат могут быть основаны на системе координат, связанной с цифровым изображением 300. Система координат может быть такой же или подобной декартовой системе координат (например, координаты x и y), цилиндрической системой координат, сферической системой координат, другой системой координат или их комбинацией. Модуль определения пересечения 232 может затем добавить координаты в набор, который представляет точки 1320А и 1320В пересечения соответственно.

[00093] Кандидаты точек схода могут быть выбраны из соответствующих множеств точек пересечения и могут быть оценены для определения того, являются ли они фактическими_точками схода для изображения. Оценка может включать определение количества линий, соответствующих каждой из выбранных точек пересечения. Определение того, соответствует ли линия точке пересечения, может состоять в определении того, указывает ли линия на точку пересечения в пределах заданного порога. В одном примере предопределенный порог может быть основан на заданном угловом смещении.

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

[00095] Методы оценки, рассмотренные выше в отношении ФИГ. 2 могут использоваться для выбора точки схода из нескольких точек пересечения кандидатов. В примере, показанном на ФИГ. 13, первая точка схода может быть определена на основе набора горизонтальных линий, обнаруженных на изображении, а вторая точка схода может быть определена на основе набора вертикальных линий, обнаруженных на изображении. В одном примере выбор каждой точки схода может быть основан на анализе и сортировке нескольких точек пересечения на основе количества соответствующих линий и выбора точки пересечения, соответствующей большинству линий. В другом примере модуль выбора точек 236 может использовать итерационный метод машинного обучения для выбора точки схода, основанной на одной или более точках пересечения 1320, как обсуждалось выше в отношении ФИГ. 2.

[00096] На ФИГ. 14 показаны дополнительные этапы процесса обнаружения контуров, которые разделяют линии цифрового изображения на четыре отдельных множества линий. Линии, полученные путем применения примера процесса определения контура, разделены на первый набор линий 2904, которые ориентированы по существу вертикально, и второй набор линий 2906, которые ориентированы по существу горизонтально. Как обсуждалось выше, линии, имеющие направление ориентации в качестве примера между 45° и 135°, считаются ориентированными по существу вертикально в одном варианте реализации изобретения, тогда как линии с направлениями ориентации в качестве примера от 0° до 45° и в качестве примера от 135° до 180° считаются ориентированными горизонтально. Направление ориентации изогнутых линий можно определить за счет использования многочисленных возможных способов для подбора линии к кривой линии, включая обычно используемые способы линейной регрессии или более простые геометрические способы, например, аппроксимацию кривой с помощью линии, совпадающей с конечными точками кривой или совпадающей с точками рядом с конечными точками кривой линии. После этого направление ориентации для кривой проходит аппроксимацию как направление ориентации для прямой линии, применяемой для кривой.

[00097] Далее, как также показано на ФИГ. 14, контуры 2904, направленные по существу вертикально, разделяются на левые контуры 2908 и правые контуры 2910. Аналогичным образом по большей части по существу горизонтально ориентированные контуры 2906 располагаются в верхних контурах 2912 и нижних контурах 2914. В одном варианте реализации изобретения эти операции не дают строгое разделение, поскольку некоторые из линий могут заканчиваться в обоих разделах. В одном варианте реализации изобретения горизонтальная граница карты по существу вертикально ориентированных наборов линий 2904 разделяется на три вертикальные участка 2916-2918, определенных следующим образом: (1) левый участок 2916 от x=0,0 до 0,4, где x - координата на горизонтальной оси Декартовой системы координат цифрового изображения; (2) центральная область 2917 от x=0,4 до 0,6; и (3) правый участок 2918 от x=0,6 до 1,0. Следует отметить, что координаты x являются относительным координатами относительно ширины цифрового изображения 1,0. Левые линии 2908 являются по существу вертикально ориентированными в карте контуров 2904, содержащимися в левой и центральной вертикальной областях 2916 и 2917. Правые линии 2910 являются по существу вертикально ориентированными линиями, которые и встречаются в центральной 2917 и правой 2918 областях по существу вертикально ориентированной карты линий 2904. В результате этого нестрого разделения, например, небольшой набор контуров 2920 встречается в карте правых линий 2908 и в карте левых линий 2910. Аналогичное разделение вертикальной оси карты по существу горизонтально направленной карты линии 2906 используется для создания верхней 2912 и нижней 2914 карт линий из набора по существу горизонтально направленных линий 2906.

[00098] Следует отметить, что для простоты иллюстрации и наглядности множества линий 2904 и 2906, создаваемые при первом разделении линий, и четыре множества линий 2908, 2910, 2912 и 2914, создаваемые при втором нестрогом разделении, показаны в виде изображений или карт. При этом они могут быть представлены в электронном виде как структуры данных, включающие координаты конечных точек каждой линии и также могут быть представлены множеством других способов. В последующем описании четыре нестрогих разделения 2908, 2910, 2912 и 2914 называются «множествами линии» и, в частности, «множеством левых линий» 2908, «множеством правых линий» 2910, «множеством верхних линий» 2912 и «множеством нижних линий» 2914.

[00099] На следующем этапе четыре множества линии проходят фильтрацию и сортировку по длине контуров или, как вариант, по количеству пикселей, содержащихся в линиях. Верхние n линий каждого набора линий сохраняются для последующей обработки, где n является параметром. В одном из вариантов реализации изобретения n равно 10. Выбор n верхних линий-кандидатов может быть основан на длине, количестве пикселей в пределах линии и иных подобных критериях. В определенных вариантах реализации эти критерии объединяются с дополнительными критериями, включая среднюю величину модуля градиента для пикселей в пределах линии, меру равномерности направления градиента в пределах линии и иные подобные критерии. При альтернативном варианте фильтрации также может использоваться информация о цветах исходного цифрового изображения.

[000100] ФИГ. 15 иллюстрирует формирование потенциальных многоугольников на основе четырех множеств линий, рассмотренных выше. Четыре множества линий представлены четырьмя картами линий 1502-1505. Опять же, наборы линий могут быть представлены структурами данных, картами или любым из многих других типов представлений набора линий. Одна или более линий могут быть изогнутыми линиями, а также прямыми. Гипотеза создается путем выбора одной линии из каждого множества линий с последующим построением многоугольника из выбранных линий. На ФИГ. 15 изогнутые стрелки, например, изогнутая стрелка 1506, указывают на выбор линии из каждого набора линий для создания расположения линий 1508-1511, показанной в левой нижней части на ФИГ. 15. Затем линии, по необходимости, продлеваются для образования многоугольника 1512 с четырьмя вершинами 1514-1517. Прерывистые линии, например, прерывистые линии 1517-1521, представляют собой продление линий для образования многоугольника.

[000101] Эти продления могут быть получены различными методиками продления линий, включая определение наиболее подходящей линии для изогнутых линий с использованием способов линейной регрессии, геометрического продления, при этом изогнутый сегмент продлевается по линии, соединяющей две точки в пределах изогнутого сегмента или иными способами применения линий к кривым. Линейные сегменты продлеваются по прямой в том же направлении, что линейный сегмент с любого одного конца или с обоих концов. Следует отметить, что, несмотря на то, что построенный многоугольник на ФИГ. 15 лежит полностью в границах исходного изображения, продление линий может привести к тому, что многоугольник будет лежать частично за пределами исходного изображения. Например, продление линий двух почти перпендикулярных линий может привести к построению вершины за пределами границы исходного изображения. Многоугольник, в котором часть границ и вершин лежит за пределами границ исходного изображения, является допустимым с учетом описанных ниже ограничений. В целом, методы настоящего изобретения и системы составляют все возможные гипотезы или, иными словами, все возможные сочетания четырех линий, каждый из которых выбирается из другого множества линий, и выполняется оценка многоугольников-кандидатов для выбора лучшего многоугольника-кандидата (например, для контура документа).

[000102] ФИГ. 16 иллюстрирует ряд параметров оценки для выбора многоугольника-кандидата. Как показано на ФИГ. 16, параметры, используемые для оценки многоугольника-кандидата, могут быть основаны на особенностях многоугольников, линий, точек схода, точек пересечения, затравочных точек, цифровых изображений, других данных или их комбинации. Многоугольник-кандидат 3202 представляет собой четырехсторонний многоугольник или четырехугольник со сторонами длиной а 3203, b 3204, с 3205 и d 3206. Многоугольник 3202 имеет две диагонали 3208 и 3209 длиной р и q. Многоугольник имеет четыре угла е 3212, ƒ3213, g3214 и h3215. В дополнение, гипотеза или многоугольник 3202 может быть распрямлен до прямоугольника, имеющего стороны длиной с'3218 и b' 3220, показанные прерывистыми линиями на ФИГ. 16. Прямоугольник из прерывистых линий со сторонами 3222-3225 представляет исходную границу цифрового изображения. Эта исходная граница продлевается в геометрическом представлении, показанном на ФИГ. 16, до прямоугольника, показанного прерывистыми линиями 3226-3229 с высотой Н_е 3230 и шириной W_e 3232. Для этого продления могут применяться параметры Т_H 3234 и T_W 3236, как показано на ФИГ. 16.

[000103] С правой стороны на ФИГ. 16 перечислены шесть различных критериев для оценки гипотезы. Первый критерий 3240 заключается в том, что углы многоугольника расположены в большем прямоугольнике высотой Н_е и шириной W_e, со сторонами 3226-3229. Второй критерий 3242 заключается в том, что многоугольник должен быть выпуклым. В выпуклом многоугольнике все внутренние углы имеют значение менее 180°, при этом отрезок линии, соединяющий любые две произвольно расположенные точки на границах многоугольника, не содержит какие-либо точки за пределами многоугольника. Для каждой стороны многоугольника х рассчитывается показатель качества стороны q_x 3244. Этот показатель принимает одно из трех значений: и 0, в зависимости от отношения , как показано в выражении 3246 на ФИГ. 16. Показатель качества по площади 3248 рассчитывается аналогичным образом, как показано в выражении 3250, из площади многоугольника 3252. Показатель качества по площади qA имеет одно из трех значений и 0 в зависимости от значения коэффициента Показатель качества по углам q_y 3254 рассчитывается для каждого угла у многоугольника в соответствии с выражением 3256. Показатель качества по углам q_y может принимать четыре значения, находящиеся в интервале от 1 до 0, при этом для углов ближе к 90° присваиваются более высокие значения. Показатель качества по соотношению сторон qS 3258 рассчитывается в соответствии с псевдокодом 3260, если известно отношение ширины документа к высоте документа По существу, показатель качества по соотношению сторон qS имеет значение 1, когда отношение ширины к высоте распрямленного многоугольника или прямоугольника приближается к известному отношению ширины документа к его высоте, в ином случае отношение равно 0.

[000104] Точки схода 3262 и 3264 могут также или альтернативно использоваться для оценки многоугольника-кандидата. Свойства точек схода 3262, 3264 или положение точек схода относительно многоугольника-кандидата могут использоваться для определения того, представляет ли многоугольник-кандидат контуры объекта (например, документа). Как обсуждалось выше, для оценки многоугольника-кандидата можно использовать одну или более точек схода 3262, 3264. Параметры, связанные с точками схода, могут включать в себя ряд линий, соответствующих точке схода, пропорцию линий относительно всех линий, которые соответствуют или не соответствуют точке схода, направление линии, указывающей на точку схода, расстояние до точки схода, расстояние до ближайшей точки схода и вес ближайшей точки схода. Расстояния могут быть определены по углам от линий, направленных от центров противоположных сторон многоугольника (например, горизонтальных или вертикальных сторон). Параметры для оценки многоугольника могут быть основаны на одном или более измерениях многоугольника. Размеры многоугольника могут относиться к измерениям сторон, углов, областей, другим измерениям или их комбинациям. Примеры параметров могут включать в себя: длины сторон многоугольника 3202, площадь многоугольника 3202, отношение сторон многоугольника 3203 относительно отношения сторон цифрового изображения, отношение длины стороны многоугольника 3203 относительно длины соответствующей обнаруженной линии, на которой она основана, углы между противоположными сторонами многоугольника-кандидата (верхняя и нижняя стороны или левая и правая стороны), углы внутри четырехугольника, углы схождения соседних сторон, углы наклона сторон относительно оси ориентации (например, оси системы координат), местоположение (например, координаты) углов многоугольника, отношение среднего веса прослеживаемых точек, которые перекрывают сторону многоугольника со средним весом точки, которые перекрывают сегмент за пределами четырехсторонней стороны, цвет области ColorOut (например, 5 пикселей) за границами прослеживаемой стороны для каждого цветового канала, цвет области ColorIn (например, 5 пикселей) внутри границ четырехугольника прослеживаемой стороны для каждого цветового канала, разница между областями ColorOut и ColorIn.

[000105] На ФИГ. 17-18 представлен расчет значения показателя веса стороны с целью построения гипотезы. На ФИГ. 17 показан расчет веса для пикселя, лежащего в пределах или вдоль одной из сторон гипотезы. Двунаправленная стрелка 3302 представляет направление стороны гипотезы, а пунктирная двунаправленная стрелка 3304 представляет направление р, перпендикулярное стороне 3302. Пиксель i 3306 лежит на стороне 3302 гипотезы. Пиксель связан с вектором градиента _i 3308, что было описано в предыдущем разделе. Длина проекции градиента 3308 на вектор р, имеющая направление, равное направлению р, может быть рассчитана как скалярное произведение градиента и р, как показано в выражении 3312 на ФИГ. 17. Угол α 3314 между связанным с пикселем градиентом и направлением р рассчитывается по выражению 3314 и служит как числовое указание на то, насколько близко направление градиента пикселя соответствует направлению р, имеющему значение 0, когда градиент и направление р являются взаимно перпендикулярными, и значение 1, когда градиент и направление р параллельны. Затем значение угла α может быть использовано в выражении 3316 для расчета весового значения, веса_i для заданного пикселя i. Чем ближе связанный с пикселем градиент соответствует направлению, перпендикулярному стороне многоугольника, тем больше вес пикселя.

[000106] На ФИГ. 18 представлен расчет совокупного весового значения, вес_гип для гипотезы. На ФИГ. 18 сторона гипотезы представлена сплошной двунаправленной стрелкой 3402 и пунктирной двунаправленной стрелкой 3404. Стрелка 3402 представляет линию, а пунктирная стрелка 3404 представляет продление линии для создания гипотезы. Стрелка накладывается на ряд пикселей, показанных прерывистыми линиями, например, пиксель 3406 исходного изображения. Количество пикселей, охватываемых частью линий стороны, 3402, равно SF3408 и имеет числовое значение 19 в представленном на ФИГ. 18 примере. Количество пикселей, охватываемых продленной частью стороны, FE 3410 имеет значение 11 в представленном на ФИГ. 18 примере. Отношение q 3412 является отношением SF к SF+FE. Вес стороны, вес_стор 3414 рассчитывается по выражению 3416. Показатель вес_стор имеет значение, основанное на весовых значениях пикселей линии W_i и весовых значениях пикселей, связанных с продлением части стороны W₀. Показатель веса стороны вес_гип для гипотезы представляет собой сумму весов, рассчитанных для сторон 3418. В качестве варианта для получения значений W_i и W₀ может использоваться средний вес пикселя.

[000107] На ФИГ. 19 приведена блок-схема одного иллюстративного примера способа 1900 для создания последовательности определителей для уменьшения ложных запусков в соответствии с одним или более вариантами реализации настоящего изобретения. Способ 1900 и (или) каждая из его отдельных функций, процедур, подпрограмм или операций может выполняться одним или более процессорами компьютерной системы, выполняющей этот способ. В некоторых реализациях способ 1900 может быть реализован в одном потоке обработки. Кроме того, способ 1900 может выполняться, используя два или более потоков обработки, причем каждый поток выполняет одну или более отдельных функций, процедур, подпрограмм или операций способа. В иллюстративном примере потоки обработки, в которых реализован способ 1900, могут быть синхронизированы (например, с использованием семафоров, критических секций и/или других механизмов синхронизации потоков). В качестве альтернативы потоки обработки, реализующие способ 1900, могут выполняться асинхронно по отношению друг к другу.

[000108] Для упрощения объяснения способы в настоящем описании изобретения изображены и описаны в виде последовательности действий. Однако действия в соответствии с настоящим описанием изобретения могут выполняться в различном порядке и (или) одновременно с другими действиями, не представленными и не описанными в настоящем документе. Кроме того, не все действия, приведенные для иллюстрации сущности изобретения, могут оказаться необходимыми для реализации способов в соответствии с настоящим описанием изобретения. Специалистам в данной области техники должно быть понятно, что эти способы могут быть представлены и иным образом - в виде последовательности взаимосвязанных состояний через диаграмму состояний или событий. Кроме того, следует учитывать, что способы настоящего изобретения, представленные в настоящем документе, могут храниться на изделии для упрощения передачи и размещения этих способов на вычислительных устройствах. Термин «изделие» в настоящем документе означает компьютерную программу, доступную посредством любого машиночитаемого устройства или носителя данных. В одном варианте реализации изобретения способ 1900 может выполняться вычислительным устройством 100 на ФИГ. 2.

[000109] Способ 1900 может выполняться устройством обработки вычислительного устройства (например, клиентским устройством или серверным устройством) и может начинаться с шага 1902. На шаге 1902 устройство обработки может обнаруживать набор линий в изображении, содержащем объект. Набор линий в изображении может содержать множество линий, которые расположены вдоль текстовых линий объекта. В одном примере обнаружение набора линий в изображении может содержать вычисление градиента яркости множества точек (например, пикселей) внутри изображения и применение операции утончения границ (edge thinning) к множеству точек для определения набора точек. Операция утончения границ может использовать градиент яркости и может содержать использование операции немаксимального подавления (non-maximum suppression). Обнаружение может также содержать организацию набора точек на основе градиента яркости, при котором набор точек содержит точку с максимальным градиентом яркости. Затем точки могут быть продлены с использованием максимального градиента яркости вдоль границы яркости по меньшей мере в одном направлении для создания отрезка линии, который затем добавляется к набору линий.

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

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

[000112] На шаге 1906 устройство обработки может определять точку схода, основанную на множестве точек пересечения. Определение точки схода может содержать выбор точки пересечения кандидатов из множества точек пересечения и определение ряда линий из множества линий, которые соответствуют точке пересечения кандидатов. Линия может соответствовать (относиться) или быть связанной с точкой пересечения кандидатов, если линия указывает на точку пересечения кандидата в пределах заданного углового смещения. Определение может также содержать замену точки схода кандидатом в точки пересечения, если количество линий, которые соответствуют кандидату в точки пересечения, превышает количество линий, соответствующих текущей точке схода. В одном примере определение точки схода может содержать обнаружение многочисленных точек схода. Первая точка схода может быть основана на множестве по существу горизонтальных линий в изображении, а вторая точка схода может быть основана на множестве по существу вертикальных линий в изображении.

[000113] На шаге 1908 устройство обработки может формировать многоугольник-кандидат на основе множества линий. Формирование многоугольника-кандидата на основе множества линий может включать в себя выбор первой пары линий из первого множества и вторую пару линий из второго множества. Эти одна или более линий первой пары или второй пары продляются, образуя многоугольник-кандидат. В одном из примеров объект содержит документ, а многоугольник-кандидат содержит замкнутый четырехугольник, отражающий контур документа. Замкнутый четырехугольник может выходить за границы изображения.

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

[000115] На шаге 1912 устройство обработки отображает многоугольник-кандидат, представляющий контур объекта. Отображаемая гипотеза контура используется для изменения изображения. Изменение изображения заключается в выполнении по меньшей мере одной из процедур: кадрирование изображения на основании многоугольника-кандидата, поворот изображения на основании многоугольника-кандидата, корректировка перспективы изображения на основании многоугольника-кандидата. После выполнения операций, описанных выше и относящихся к шагу 1912, процедура завершается.

[000116] В другом примере реализации процедура 1900 может также содержать получение изображения от пользовательского устройства, содержащего датчик изображений, и уменьшение разрешения изображения. Уменьшение разрешения изображения подразумевает сохранение соотношения сторон изображения при уменьшении длины и ширины изображения и сглаживании изображения с помощью Гауссова фильтра (Gaussian kernel) или медианного фильтра (median filter).

[000117] ФИГ. 20-29 иллюстрируют методики обработки, структуры и данные, поясняющие приведенное выше описание. На ФИГ. 20 показано типичное изображение с цифровым кодированием. Кодированное изображение содержит двумерный массив пикселей 301. Каждый маленький квадрат, такой как квадрат 303, представляет пиксель, в общем определяемый как наименьшая структурная часть изображения, численно заданная в цифровой кодировке. Каждый пиксель имеет свое расположение, в общем представляемое парой числовых значений, соответствующих перпендикулярным осям x и y 305 и 307 соответственно. Так, например, пиксель 303 имеет координаты x, y (39,0), а пиксель 311 имеет координаты (0,0). В цифровой кодировке пиксель представлен числовыми значениями, указывающими на то, как область изображения, соответствующая пикселю, представляется при печати, отображается на экране компьютера или ином дисплее. Обычно для черно-белых изображений для представления каждого пикселя используется единичное значение в интервале от 0 до 255 с числовым значением, соответствующим уровню серого, с которым отображается этот пиксель. Согласно общепринятому правилу значение «0» соответствует черному цвету, а значение «255» - белому. Для цветных изображений может применяться один из множества различных наборов числовых значений, указывающих на цвет. В одной широко используемой цветовой модели, как показано на ФИГ. 20, каждый пиксель соотнесен с тремя числами, или координатами (r, g, b), задающими яркость красного, зеленого и синего компонентов цветов, отображаемых в соответствующей пикселю области.

[000118] На ФИГ. 21 показан один из вариантов цветовой модели RGB. Тремя координатами первичных цветов (r, g, b) представлен весь спектр цветов, как указано выше со ссылкой на ФИГ. 20. Цветовая модель может считаться соответствующей точкам в пределах единичного куба 401, в котором трехмерное цветовое пространство определяется тремя осями координат: (1) r 403; (2) g 405; и (3) b 407. Таким образом, индивидуальные координаты цвета находятся в диапазоне от 0 до 1 по каждой из трех цветовых осей. Например, чистый синий цвет максимально возможной яркости соответствует точке 409 по оси b с координатами (0,0,1). Белый цвет соответствует точке 411 с координатами (1,1,1), а черный цвет - точке 413, началу системы координат с координатами (0,0,0).

[000119] На ФИГ. 22 показана другая цветовая модель, называемая «Тон-насыщенность-светлота» (HSL). В этой цветовой модели цвета содержатся в трехмерной бипирамидальной призме 500, имеющей шестигранное сечение. Оттенок (h) связан с преобладающей длиной волны излучения света, воспринимаемого наблюдателем. Значение оттенка находится в интервале от 0° до 360°, начиная с красного цвета 502 в точке 0°, проходя через зеленый 504 в точке 120°, синий 506 в точке 240° и заканчивая красным 502 в точке 660°. Насыщенность (s), находящаяся в диапазоне от 0 до 1, обратно пропорциональна количеству белого и черного, смешанных с данной длинной волны, то есть оттенком. Например, чистый красный цвет 502 является полностью насыщенным при насыщенности s=1,0, в то время как розовый цвет имеет насыщенность менее 1,0, но более 0,0, белый цвет 508 является полностью ненасыщенным с s=0,0, черный цвет 511 также является полностью ненасыщенным с s=0,0. Полностью насыщенные цвета находятся на периметре среднего шестигранника, содержащего точки 502, 504 и 506. Шкала оттенков серого проходит от черного 511 до белого 508 вдоль центральной вертикальной оси 512, представляющей полностью ненасыщенные цвета без оттенка, но с различными пропорциями черного и белого. Например, черный 511 содержит 100% черного и не содержит белого, белый 508 содержит 100% белого и не содержит черного, а начало координат 513 содержит 50% черного и 50% белого. Светлота , представленная центральной вертикальной осью 512, указывает на уровень освещенности в интервале от 0 для черного 511, при до 1 для белого 508, при Для произвольного цвета, представленного на ФИГ. 22 точкой 514, оттенок определяется как угол θ 516, между первым вектором из начала координат 513 к точке 502 и вторым вектором из начала координат 513 к точке 521, в которой вертикальная линия 522, проходящая через точку 514, пересекает плоскость 524, содержащую исходную точку 513 и точки 502, 504 и 506. Насыщенность задается отношением расстояния от представляемой точки 514 до вертикальной оси 512 (d') к длине горизонтальной линии, проходящей через точку 521 от начала координат 513 к поверхности бипирамидальной призмы 500 (d). Светлота задается расстоянием по вертикали от представляемой точки 514 до вертикального уровня точки, представляющей черный цвет 511. Координаты конкретного цвета (h, s, ) в цветовой модели HSL могут быть получены на основе координат цвета в цветовой модели RGB (r, g, b) следующим образом:

и

[000120] где значения r, g и b - яркость красного, зеленого и синего, нормализованные в диапазоне [0,1]; С_max - нормализованное значение яркости, равное максимальному из значений r, g и b; С_min - нормализованное значение яркости, равное минимальному из значений r, g и b; Δ определяется как С_max-C_min.

[000121] На ФИГ. 23 показано формирование серого или бинаризованного изображения из цветного изображения. В цветном изображении каждый пиксель обычно связан с тремя значениями: а, b и с 602. В разных цветовых моделях для представления конкретного цвета используются разные значения а, b и с. Серое изображение содержит для каждого пикселя только одно значение яркости 604. Бинаризованное изображение является частным случаем серого изображения, которое имеет только два значения яркости «0» и «1». Обычно серые изображения могут иметь 256 или 65536 разных значений яркости для каждого пикселя, представленного байтом или 16-битным словом соответственно. Таким образом, чтобы преобразовать цветное изображение в серое, три значения а, b и с цветных пикселей необходимо преобразовать в одно значение яркости для серого или бинаризованного изображения. На первом шаге три значения цвета а, b и с, преобразуются в значение светимости L, обычно в интервале [0,0; 1,0] 606. В некоторых цветовых моделях к каждому из цветовых значений 608 применяется определенная функция, и результаты суммируются 610, давая значение светимости. В других цветовых моделях каждое цветовое значение умножается на определенный коэффициент, и полученные результаты суммируются 612, давая значение светимости. В третьих цветовых системах одно из трех цветовых значений является, фактически, значением светимости 614. Наконец, в общем случае к трем цветовым значениям 616 применяется определенная функция, дающая значение светимости. Затем значение светимости округляется до целого 618, позволяя получить значение яркости оттенков серого в требуемом интервале, обычно [0, 255] для серых изображений и (0,1) для бинаризованных изображений.

[000122] На ФИГ. 24 показано дискретное вычисление градиента яркости. На ФИГ. 24 показан небольшой квадратный участок 722 цифрового изображения. Каждая клетка, например, клетка 724, представляет пиксель, а числовое значение в клетке, например, значение «106» в клетке 724, представляет яркость серого цвета. Допустим, пиксель 726 имеет значение яркости «203». Этот пиксель и четыре смежных соседних пикселя показаны на крестообразной схеме 728 справа от участка 722 цифрового изображения. Рассматривая левый 730 и правый 732 соседние пиксели, изменение яркости в направлении x, Δх, можно дискретно вычислить как:

Рассматривая нижний 734 и верхний 736 соседние пиксели, изменение яркости в вертикальном направлении (Δу) можно дискретно вычислить как:

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

Частный дифференциал функции яркости F вдоль оси у в центральном пикселе 726 оценивается по Δу:

Градиент яркости в пикселе 726 можно приближенно вычислить следующим образом:

где i и j - это единичные векторы в направлениях х и у. Величина вектора градиента и угол вектора градиента далее рассчитываются следующим образом:

Направление вектора 740 градиента яркости и угол θ 742 наложены на участок 722 цифрового изображения на ФИГ. 24. Отметим, что вектор градиента указывает в направлении скорейшего увеличения яркости от пикселя 726. Модуль вектора градиента указывает на ожидаемое увеличение яркости на единицу приращения в направлении градиента. Конечно, поскольку градиент всего лишь оценен с помощью дискретных операций, в вычислении, показанном на ФИГ. 24, направление и модуль градиента - это всего лишь приближенные значения.

[000123] На ФИГ. 25 показан градиент, рассчитанный для точки на непрерывной поверхности. На ФИГ. 25 представлена непрерывная поверхность z=F(x,y). Непрерывная поверхность 802 построена в трехмерной декартовой системе координат 804 и имеет форму шляпы. Для отображения непрерывного множества точек с постоянным значением z на поверхности могут быть построены линии, например, контурная линия 806. В конкретной точке 808 на линии, построенной на поверхности, вектор градиента 810, рассчитанный в точке, расположен перпендикулярно к этой линии и указывает в направлении скорейшего роста на поверхности от точки 808. В общем случае вектор градиента яркости направлен перпендикулярно границе яркости, при этом чем больше модуль градиента, тем резче граница, т.е. тем больше разница яркостей пикселей с двух сторон границы.

[000124] На ФИГ. 26 показан ряд примеров для градиента яркости. Каждый пример, такой как пример 902, содержит центральный пиксель, для которого рассчитывается градиент, и четыре смежных пикселя, которые используются для расчета Δх и Δу. Наиболее резкие границы яркости показаны в первой колонке 904. В этих случаях модуль градиента составляет не менее 127,5, а в третьем случае 906 - 180,3. При относительно небольшой разности на границе, показанной в примере 908, значение модуля градиента получается равным всего лишь 3,9. Во всех случаях вектор градиента расположен перпендикулярно очевидному направлению границы яркости, проходящей через центральный пиксель.

[000125] На ФИГ. 27 показано применение ядра преобразования к изображению. На ФИГ. 27 небольшая часть изображения 1002 представлена в виде прямоугольной сетки пикселей. Малое ядро 3×3 k 1004 показано ниже изображения I 1002. Ядро применяется к каждому пикселю изображения. В случае ядра 3×3, такого как ядро k 1004, показанное на ФИГ. 27, для пикселей на границе изображения можно использовать модифицированное ядро. Также изображение можно расширить, скопировав значения яркости для пикселей границы в описанный прямоугольник пикселей, чтобы иметь возможность применять ядро к каждому пикселю исходного изображения. Чтобы применить ядро к пикселю изображения, ядро 1004 при помощи вычислений накладывается на окрестности пикселя 1006, к которому применяется ядро с такими же размерами в пикселях, как у ядра. Применение ядра на окрестностях пикселя, к которому применяется ядро, позволяет получить новое значение для пикселя в преобразованном изображении, полученном применением ядра к пикселям исходного изображения. Для некоторых типов ядер новое значение пикселя, к которому применено ядро, I_n, вычисляется как сумма произведений значения ядра и пикселя, соответствующего значению ядра 1008. В других случаях новое значение пикселя является более сложной функцией окрестности для пикселя и ядра 1010. В некоторых других типах обработки изображений новое значение пикселя формируется функцией, применяемой к окрестностям пикселя без использования ядра 1012.

[000126] На ФИГ. 28 показана свертка ядра с изображением. В общем случае ядро последовательно применяется к каждому пикселю изображения, в некоторых случаях к каждому пикселю изображения, не принадлежащему границе изображения, или, в других случаях, для создания новых значений преобразованного изображения. На ФИГ. 28 ядро 3×3, выделенное штриховкой 1102, последовательно применяется к первой строке пикселей, не принадлежащих границе изображения 1104. Каждое новое значение, созданное в результате применения ядра к пикселю в исходном изображении 1106, переносится в преобразованное изображение 1107. Другими словами, ядро было последовательно применено к исходным окрестностям каждого пикселя в исходном изображении для создания преобразованного изображения. Этот процесс называется «сверткой» и отдаленно связан с математической операцией свертки, которая выполняется путем перемножения Фурье-преобразований изображений, с последующим обратным Фурье-преобразованием произведения.

[000127] На ФИГ. 29 показан пример ядра и методики обработки изображений на основе ядра. В процессе, называемом «медианной фильтрацией», значения яркости в окрестности исходного изображения 1202 отсортируются 1204 по возрастанию, и новым значением 1208 для соответствующей окрестности преобразованного изображения выбирается среднее значение 1206. Гауссово сглаживание и очистка от шумов подразумевают применение гауссова ядра 1210 ко всем окрестностям пикселей 1214 исходного изображения для создания значения центрального пикселя 1216 соответствующей окрестности обработанного изображения. Значения в гауссовом ядре рассчитываются по выражению, например, выражение 1218, для создания дискретного представления гауссовой поверхности над окрестностью, причем поверхность образована вращением кривой нормального распределения вокруг вертикальной оси, совпадающей с центральным пикселем. Горизонтальная и вертикальная компоненты градиента изображения для каждого пикселя могут быть получены применением соответствующих ядер градиента G_x 1220 и G_y 1222. Были указаны только три из множества различных типов методик обработки изображения на основе свертки.

[000128] На ФИГ. 30А-В показаны два различных типа портативных устройств получения изображений. На ФИГ. 30А показана цифровая камера 3002, а на ФИГ. 30В показан смартфон 3004. Цифровая камера содержит объектив и кнопку спуска затвора, нажатие которой пользователем приводит к захвату цифрового изображения, соответствующего отраженному свету, поступающему в объектив цифровой камеры. С задней стороны цифровой камеры имеется видоискатель и жидкокристаллический дисплей-видоискатель, которые пользователь использует при съемке цифровых изображений. С помощью видоискателя пользователь может напрямую просматривать создаваемое объективом камеры изображение, а с помощью жидкокристаллического дисплея-видоискателя - просматривать электронное отображение создаваемого в настоящей момент объективом изображения. Обычно пользователь камеры настраивает фокус камеры с помощью кольца фокусировки, смотря при этом через видоискатель или наблюдая изображение на жидкокристаллическом дисплее для выбора необходимого изображения перед нажатием на кнопку спуска затвора с целью цифрового захвата изображения и сохранения изображения в электронной памяти цифровой камеры.

[000129] На ФИГ. 30В показан типичный смартфон 3004 с лицевой стороны и задней стороны. На задней стороне имеется объектив цифровой камеры и цифровой экспонометр и/или датчик приближения. На лицевой стороне смартфона под управлением приложения может отображаться получаемое изображение аналогично работе жидкокристаллического дисплея видоискателя цифровой камеры, а также сенсорная кнопка спуска затвора, при прикосновении к которой происходит съемка цифрового изображения и сохранение его в памяти смартфона.

[000130] На ФИГ. 31 приведена блок-схема вычислительной системы, работающей в соответствии с одним или более вариантами реализации настоящего изобретения. В различных иллюстративных примерах вычислительная система 3100 может соответствовать вычислительной системе 100 на Фиг.1. Вычислительная система может входить в состав вычислительного центра, поддерживающего виртуализацию. Виртуализация с помощью вычислительного центра заключается в виртуализации физической системы с помощью виртуальных машин для объединения инфраструктуры вычислительного центра и увеличения эффективности работы. Виртуальная машина (ВМ) может быть программной эмуляцией физического вычислительного устройства. Например, работа этой ВМ может осуществляться на основе архитектуры компьютера и функций компьютерного аппаратного обеспечения, связанного с жесткими дисками и другими типами памяти. Такая ВМ эмулирует физическое вычислительное оборудование, но для передачи запросов к жесткому диску или другим типам памяти на соответствующие физические вычислительные аппаратные ресурсы эти запросы управляются виртуальными уровнями вычислительного устройства. В результате такого типа виртуализации несколько ВМ совместно используют физические ресурсы.

[000131] В некоторых вариантах реализации вычислительная система 3100 соединяется (например, с помощью сети, такой как LAN, интрасеть, внешняя сеть или Интернет) с другими вычислительными системами. Вычислительная система 3100 может работать в качестве сервера или клиента в среде «клиент-сервер», или в качестве однорангового вычислительного устройства в одноранговой (или распределенной) сетевой среде. Вычислительная система 3100 может быть представлена персональным компьютером (ПК), портативным компьютером, телеприставкой, карманным персональным компьютером (КПК), мобильным телефоном, веб-устройством, сервером, сетевым маршрутизатором, коммутатором или мостом или любым устройством, имеющим возможность выполнять набор команд (последовательный или иной), определяющих действия, предпринимаемые этим устройством. Кроме того, термин «вычислительная система» или «компьютер» также подразумевает любой набор компьютеров, которые по отдельности или совместно выполняют набор команд (или несколько наборов команд) для выполнения любого одного или более из описанных здесь методов настоящего изобретения.

[000132] В других вариантах вычислительная система 3100 содержит устройство обработки 3102, энергозависимую память 3104 (например, запоминающее устройство с произвольным доступом (ЗУПД или RAM)), энергонезависимую память 3106 (например, постоянное запоминающее устройство (ПЗУ или ROM) или электрически стираемое программируемое запоминающее устройство (ЭСППЗУ или EEPROM)) и устройство хранения информации 3116, обменивающиеся данными с помощью шины 3108.

[000133] Устройство обработки 3102 может иметь один или более процессоров, таких как процессор общего назначения (например, микропроцессор с общин набором команд (CISC), микропроцессор с сокращенным набором команд (RISC), микропроцессор с очень длинными машинными командами (VLIW), микропроцессор, использующий другие типы наборов команд, или микропроцессор, использующий комбинации типов наборов команд) или процессор специального назначения (например, интегральные схемы специального назначения (ASIC), программируемая пользователем вентильная матрица (FPGA), цифровой процессор обработки сигналов (DSP) или сетевой процессор).

[000134] Вычислительная система 3100 может дополнительно содержать устройство сопряжения с сетью 3122. Вычислительная система 3100 может также содержать устройство отображения изображений 3110 (например, жидкокристаллический экран), буквенно-цифровое устройство ввода 3112 (например, клавиатуру), координатное устройство 3114 (например, мышь) и устройство формирования сигнала 3120.

[000135] Устройство хранения данных 3116 может содержать постоянный машиночитаемый носитель данных 3124, на котором хранятся команды 3126, кодирующие один или более описанных способов или процедур, в том числе, инструкции по реализации процедур 1900, и компоненты и модули, показанные на ФИГ. 2.

[000136] Во время выполнения команд 3126 вычислительной системой 3100 они могут также находиться, полностью или частично, в энергозависимой памяти 3104 и (или) в устройстве обработки 3102, таким образом энергозависимая память 3104 и устройство обработки 3102 могут также содержать машиночитаемый носитель информации.

[000137] Несмотря на то, что машиночитаемый носитель данных 3124 показан в иллюстративных примерах как единичный носитель, термин «машиночитаемый носитель информации» подразумевает как единичный носитель, так и несколько таких носителей (например, централизованная или распределенная база данных и (или) связанные кэши и серверы), на которых хранится один или более наборов команд. Термин «машиночитаемый носитель данных» также подразумевает любой носитель, который может хранить или кодировать набор команд для выполнения вычислительным устройством и который обеспечивает выполнение вычислительным устройством любого одного или более способов настоящего изобретения. Термин «машиночитаемый носитель данных» подразумевает, но не ограничивается, в частности, устройства твердотельной памяти, оптические и магнитные носители.

[000138] Описанные в документе способы, компоненты и функции могут быть реализованы дискретными компонентами оборудования, либо они могут быть интегрированы в функции других аппаратных компонентов, таких как ASICS, FPGA, DSP или подобных устройств. Кроме того, способы, компоненты и функции могут быть реализованы с помощью модулей встроенного программного обеспечения или функциональных схем аппаратного обеспечения. Способы, компоненты и функции могут быть также реализованы с помощью любой комбинации аппаратных устройств и программных компонентов, либо исключительно с помощью программного обеспечения.

[000139] Если не указано обратное, термины, такие как «инициирование», «передача», «получение», «анализ» и подобные им, подразумевают действия и процессы, выполняемые или осуществляемые вычислительными системами, преобразующими данные, представленные физическими (электронными) величинами в системных регистрах и запоминающих устройствах вычислительной системы в другие данные, аналогично представленными физическими величинами в системных регистрах, запоминающих устройствах и аналогичных им устройствах вычислительной системы, устройствах передачи или отображения данных. Также, термины «первый», «второй», «третий», «четвертый» и т.д. используются как метки для обозначения различных элементов и не обязательно имеют смысл порядковых номеров в соответствии с их числовым обозначением.

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

[000141] Описанные способы и иллюстративные примеры не связаны с какими-либо конкретными компьютерами или другими устройствами. Для реализации описанных способов могут быть использованы различные системы общего назначения, или могут быть разработаны более специализированные устройства для реализации способов 1900 и (или) отдельных процедур, методов, подпрограмм или операций. Примеры структур разнообразных систем такого рода определяются в порядке, предусмотренном в описании выше.

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

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

1. Способ автоматического детектирования контуров документов, содержащий:

получение изображения, содержащего один или более документов;

детектирование набора линий на изображении;

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

определение одной или более точки схода на основе указанного множества точек пересечения;

генерацию многоугольника-кандидата на основе указанного набора линий;

оценку указанного многоугольника-кандидата на основе ассоциированного с одной или более характеристикой указанной одной или более точки схода одного или более параметра; и

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

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

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

4. Способ по п. 1, отличающийся тем, что определение указанного множества точек пересечения включает в себя:

выбор пары линий из указанного набора линий на изображении;

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

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

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

6. Способ по п. 1, отличающийся тем, что определение указанной точки схода на основе множества точек пересечения включает в себя:

выбор кандидата в точки пересечения из указанного множества точек пересечения;

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

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

7. Способ по п. 1, отличающийся тем, что определение указанного набора линий на изображении включает в себя:

определение первого набора линий, которые практически горизонтальны;

определение второго набора линий, которые практически вертикальны;

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

8. Способ по п. 7, отличающийся тем, что формирование указанного многоугольника-кандидата на основе набора линий включает в себя:

выбор первой пары линий из указанного первого набора линий и второй пары линий из указанного второго набора линий;

продление одной или более линий первой пары линий или второй пары линий для формирования многоугольника-кандидата.

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

длину стороны многоугольника-кандидата;

площадь многоугольника-кандидата;

координату внутреннего угла многоугольника-кандидата;

величину внутреннего угла многоугольника-кандидата;

величину внешнего угла схождения сторон многоугольника-кандидата;

отношение длины стороны многоугольника-кандидата к длине соответствующей линии из обнаруженного множества линий;

соотношение сторон многоугольника-кандидата;

угол наклона стороны многоугольника-кандидата относительно оси изображения;

расстояние до ближайшей точки схода;

количество линий, соответствующих ближайшей точке схода;

направление линии, указывающей на точку схода;

расстояние до точки схода;

расстояние до ближайшей точки схода;

вес ближайшей точки схода;

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

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

11. Способ по п. 1, отличающийся тем, что определение указанного набора линий на изображении включает в себя:

вычисление градиента яркости множества точек на изображении, причем каждая точка содержит пиксель;

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

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

растягивание точки с максимальным градиентом яркости вдоль границы яркости по меньшей мере в одном направлении для формирования сегмента линии; и

добавление указанного сегмента линии к указанному набору линий.

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

13. Способ по п. 1, дополнительно включающий:

получение изображения от пользовательского устройства, содержащего датчик изображений;

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

сглаживание изображения.

14. Система автоматического детектирования контуров документов, включающая следующие компоненты:

запоминающее устройство;

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

получения изображения, содержащего один или более документ;

детектирования набора линий на изображении;

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

определения одной или более точки схода на основе указанного множества точек пересечения;

генерации многоугольника-кандидата на основе указанного набора линий;

оценки указанного многоугольника-кандидата на основе ассоциированного с одной или более характеристикой указанной одной или более точки схода одного или более параметра; и

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

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

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

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

выбора пары линий из указанного набора линий на изображении;

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

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

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

получению изображения, содержащего один или более документ;

детектированию набора линий на изображении;

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

определению одной или более точки схода на основе указанного множества точек пересечения;

генерации многоугольника-кандидата на основе указанного набора линий;

оценке указанного многоугольника-кандидата на основе ассоциированного с одной или более характеристикой указанной одной или более точки схода одного или более параметра; и

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

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

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