УСТРОЙСТВО, СПОСОБ И СИСТЕМА ДЛЯ РЕКОНСТРУКЦИИ 3D-МОДЕЛИ ОБЪЕКТА
DEVICE, METHOD  AND SYSTEM FOR RECONSTRUCTING 3D-MODEL OF OBJECT

Область техники, к которой относится изобретение
Данное изобретение, в общем, относится к области обработки изображений, и, в частности, оно ориентировано на устройство, способ и систему для 3D-реконструкции объекта из изображений, генерируемых посредством сканирования объекта на 360 градусов.
Уровень техники
3D-реконструкция является процессом вычисления математического представления трехмерной поверхности объекта из двумерных проекций объекта, получаемых с разных точек просмотра. Реконструированная 3D-модель объекта может быть сохранена, обработана и отображена в цифровом виде и физически воссоздана с использованием устройств 3D-печати. Процесс 3D-реконструкции широко используют в различных сферах деятельности, таких как развлечения (кинофильмы, анимация, компьютерные игры и т.д.), дизайн интерьеров, архитектура, промышленный дизайн, технология прототипирования.
Существуют разные подходы к 3D-реконструкции, которые основаны на различных оптических системах, используемых для захвата изображений. Обычно оптическая система может быть выполнена либо в виде специализированной камеры глубины (например, активного датчика глубины или стереокамеры), либо в виде традиционной монокулярной камеры.
Специализированная камера глубины может захватывать карты глубины (либо непосредственно в случае активного датчика глубины, либо после обработки пары скорректированных стереоизображений в случае стереокамеры) объекта или среды в реальном времени. Каждый пиксель в картах глубины соответствует дискретному измерению расстояния, получаемому посредством камеры из 3D-точки в среде. Например, документ US 8587583 B2 описывает подход, в котором местоположение камеры оценивают с использованием захваченной карты глубины, причем все карты глубины непрерывно объединяют во внутренней памяти обрабатывающего устройства с использованием оцененного местоположения камеры. Этот подход имеет два недостатка: во-первых, он требует дорогостоящего аппаратного обеспечения для реализации датчика глубины, используемого для захвата карт глубины, и, во-вторых, алгоритм обработки является вычислительно сложным и требует мощного графического процессора для обработки данных в реальном времени.
В подходах на основе монокулярной камеры может быть использован способ 3D-реконструкции на основе силуэта. В этом способе изображения, захваченные посредством камеры, используются для извлечения силуэтов, которые затем образуют объемную структуру, вместе с их пересечениями. Такой способ описан в документе US 8270704 B2 и имеет в качестве результата полигональную сетку с цветной текстурой. Недостатком этого способа является его вычислительная сложность в отношении объемного объединения и извлечения силуэтов, что ограничивает его реализацию на мобильных устройствах. Другой недостаток состоит в том, что этот способ не может восстанавливать вогнутости, которые не видны на изображениях силуэтов.
Другим классом способов, использующих аппаратное обеспечение на основе монокулярной камеры, является процесс 3D-реконструкции на основе определения структуры по движению, в котором характерные точки извлекают и сопровождают для последовательных захваченных изображений. Характерные траектории в зависимости от времени используют затем для реконструкции их 3D-местоположений и перемещения камеры. Такой подход описан в документе US 8532367 B2. Недостатком этого подхода является то, что он обычно реконструирует облако 3D-точек или полигональную сетку без текстуры (текстур), так что визуальный внешний вид реконструированной 3D-модели не является достаточным. Также, для лучшей точности этот подход требует большого количества характерных точек, что увеличивает вычислительные затраты.
Как следует из вышеприведенного, все описанные подходы имеют один общий недостаток: все они имеют высокую вычислительную сложность, так что их реализация на мобильных платформах, таких как смартфоны или планшетные компьютеры, является невозможной вследствие ограниченной вычислительной производительности такого класса устройств. Для преодоления этого недостатка обычно используют облачную обработку данных. Например, документ US 8941644 B2 описывает методы создания 3D-моделей наборов изображений с использованием доступной по сети (например, облачной) вычислительной службы, а не клиентского мобильного устройства. Этот подход требует доступа в Интернет для пользователя и обычно занимает значительно больше времени, чем 3D-реконструкция на клиентском мобильном устройстве.
Таким образом, существует потребность в методах 3D-реконструкции объектов, которые могли бы быть выполнены с использованием меньшего времени и вычислительных затрат, чем аналоги из уровня техники, а также без использования дополнительного дорогостоящего аппаратного обеспечения.
Раскрытие изобретения
Технический результат, достигаемый с использованием данного изобретения, состоит в возможности быстрого создания высококачественной 3D-модели (3D-сетки и цветной текстуры) объекта в условиях жестких ограничений как на размер хранилища данных, так и на вычислительные затраты.
Согласно первому аспекту, представлено устройство для реконструкции 3D-модели объекта. Это устройство содержит модуль сканирования, блок памяти, по меньшей мере один процессор и модуль отображения. Модуль сканирования выполнен с возможностью сканирования объекта вдоль траектории вокруг объекта и захвата изображений объекта из разных точек на этой траектории. Блок памяти выполнен с возможностью сохранения захваченных изображений объекта. Упомянутый по меньшей мере один процессор выполнен с возможностью осуществления процесса 3D-реконструкции с использованием сохраненных захваченных изображений для формирования 3D-модели объекта. Модуль отображения выполнен с возможностью отображения 3D-модели объекта.
В одном варианте реализации упомянутый по меньшей мере один процессор выполнен с возможностью осуществления процесса 3D-реконструкции посредством: оценки во время сканирования объекта местоположения модуля сканирования, соответствующего каждому из захваченных изображений; передачи оцененных местоположений модуля сканирования к блоку памяти для их сохранения; уточнения, после завершения сканирования объекта, оцененных местоположений модуля сканирования, сохраненных в блоке памяти, с использованием информации о начальной и конечной точках траектории, и передачи уточненных местоположений модуля сканирования к блоку памяти для их сохранения; конструирования карты глубины, соответствующей каждой из уточненных местоположений модуля сканирования и каждому из захваченных изображений; объединения всех карт глубины для генерирования 3D-представления объекта; создания поверхностной сетки объекта на основе 3D-представления; наложение текстур на поверхностной сетке объекта для реконструкции 3D-модели объекта; и передачи 3D-модели объекта к блоку памяти для ее сохранения.
Модуль сканирования выполнен с возможностью сканирования объекта вдоль траектории, которая может быть замкнутым или незамкнутым контуром. Замкнутый или незамкнутый контур может иметь круговую или произвольную форму.
В одном варианте реализации упомянутый по меньшей мере  один процессор выполнен с возможностью оценки местоположений модуля сканирования во время сканирования объекта с использованием метода одновременной навигации и составления карты(Simultaneous Localization and Mapping).
В некоторых вариантах реализации модуль сканирования реализован в виде монокулярной камеры или многовидовой стереокамеры, или датчика глубины, или любой их комбинации.
В одном варианте реализации каждое из местоположений модуля сканирования, оцененное и затем уточненное посредством упомянутого по меньшей мере одного процессора, характеризуется набором параметров, включающим в себя координаты модуля сканирования и ориентацию модуля сканирования в пространстве. Ориентация модуля сканирования может задаваться посредством углов рыскания, наклона и/или крена.
В некоторых других вариантах реализации устройство дополнительно содержит одно или более устройств человеческого интерфейса, позволяющих пользователю управлять процессом сканирования объекта. Упомянутые одно или более устройства человеческого интерфейса могут быть выполнены с возможностью предоставления пользователю возможности настройки угла сканирования и/или времени сканирования. Упомянутые одно или более устройства человеческого интерфейса могут включать в себя одну или более кнопок, один или более микрофонов, громкоговорителей, сенсорный экран или любые их комбинации. Модуль сканирования может быть выполнен с возможностью сканирования объекта, захвата его изображений и/или остановки сканирования и захвата на основе пользовательского речевого сигнала, принятого через микрофон.
В одном варианте реализации модуль отображения дополнительно выполнен с возможностью отображения одного или более промежуточных данных, сохраненных в блоке памяти. Промежуточные данные могут содержать изображения объекта, захваченные посредством модуля сканирования, и местоположения модуля сканирования, оцененные и уточненные посредством упомянутого по меньшей мере одного процессора.
В одном варианте реализации упомянутый по меньшей мере один процессор дополнительно выполнен с возможностью уточнения оцененных местоположений модуля сканирования на основе алгоритма сопровождения Лукаса-Канаде.
В одном варианте реализации устройство дополнительно содержит один или более инерциальных датчиков, и упомянутый по меньшей мере один процессор выполнен с возможностью использования данных от этих инерциальных датчиков вместе с захваченными изображениями объекта для оценки местоположений модуля сканирования.
В одном варианте реализации упомянутый по меньшей мере  один процессор выполнен с возможностью наложения текстур на поверхностной сетке объекта посредством: проверки, из каких местоположений модуля сканирования каждая грань поверхностной сетки является видимой или невидимой, и текстурирования каждой видимой или невидимой грани поверхностной сетки посредством проецирования на нее соответствующего одного из захваченных изображений объекта. Кроме того, упомянутый по меньшей мере один процессор дополнительно выполнен с возможностью, если две или более видимые или невидимые грани поверхностной сетки текстурированы из одного захваченного изображения объекта, коррекции неоднородностей цвета между соседними гранями поверхностной сетки.
Устройство может быть портативным или мобильным устройством, или отдельным персональным компьютером (PC), или может быть реализовано с использованием технологии облачной обработки.
Согласно второму аспекту, представлен способ реконструкции 3D-модели объекта. Этот способ состоит в следующем. Сначала объект сканируют посредством модуля сканирования вдоль траектории вокруг объекта и захватывают изображения объекта из разных точек на этой траектории. Захваченные изображения затем сохраняют в блоке памяти. Далее по меньшей мере один процессор используют для: оценки во время сканирования объекта местоположения модуля сканирования, соответствующего каждому из захваченных изображений; сохранения оцененных местоположений модуля сканирования в блоке памяти; уточнения, после завершения сканирования объекта, оцененных местоположений модуля сканирования, сохраненных в блоке памяти, с использованием информации о начальной и конечной точках траектории, и сохранения уточненных местоположений модуля сканирования в блоке памяти; конструирования карты глубины, соответствующей каждому из уточненных местоположений модуля сканирования и каждому из захваченных изображений; объединения всех карт глубины для генерирования 3D-представления объекта; создания поверхностной сетки объекта на основе 3D-представления; наложения текстур на поверхностной сетке объекта для реконструкции 3D-модели объекта; и сохранения 3D-модели объекта в блоке памяти. Наконец, 3D-модель объекта отображают на модуле отображения.
Согласно третьему аспекту, предоставлена система для реконструкции 3D-модели объекта. Эта система содержит: модуль сканирования, модуль памяти, модуль оценки местоположения, модуль уточнения местоположения, модуль конструирования карты глубины, модуль объединения карт глубины, модуль создания поверхностной сетки, модуль наложения текстур и модуль отображения. Модуль сканирования выполнен с возможностью  сканирования объекта вдоль траектории вокруг объекта и захвата изображений объекта из разных точек этой траектории. Модуль хранения выполнен с возможностью сохранения захваченных изображений объекта. Модуль оценки местоположения выполнен с возможностью оценки во время сканирования объекта местоположений модуля сканирования на основе сохраненных захваченных изображений и передачи оцененных местоположений модуля сканирования в модуль памяти для их сохранения. Модуль уточнения местоположения выполнен с возможностью уточнения после завершения сканирования объекта оцененных местоположений модуля сканирования, сохраненных в модуле памяти, с использованием информации о начальной и конечной точках траектории и передачи уточненных местоположений модуля сканирования в модуль памяти для их сохранения. Модуль конструирования карты глубины выполнен с возможностью конструирования карты глубины, соответствующей каждому из уточненных местоположений модуля сканирования и каждому из захваченных изображений. Модуль объединения карт глубины выполнен с возможностью объединения всех карт глубины, тем самым генерируя 3D-представление объекта. Модуль создания поверхностной сетки выполнен с возможностью создания поверхностной сетки объекта на основе 3D-представления. Модуль наложения текстур выполнен с возможностью наложения текстур на поверхностной сетке объекта для реконструкции 3D-модели объекта и передачи 3D-модели объекта в модуль памяти для ее сохранения. Модуль отображения выполнен с возможностью отображения 3D-модели объекта.
Каждый из вышеуказанных модулей системы может быть реализован посредством одного или более процессоров в зависимости от конкретных применений.
Эта система может быть интегрирована в портативное или мобильное устройство или единственный PC, или может быть реализована с использованием технологии облачной обработки.
Другие признаки и преимущества данного изобретения будут очевидны после прочтения нижеследующего подробного описания и анализа сопроводительных чертежей.
Краткое описание чертежей
Сущность данного изобретения пояснена ниже со ссылкой на сопроводительные чертежи, на которых:
Фиг. 1 показывает иллюстративное применение данного изобретения;
Фиг. 2 показывает функциональную блок-схему всего алгоритма 3D-реконструкции;
Фиг. 3 показывает в общем виде функциональную блок-схему алгоритма оценки местоположения камеры;
Фиг. 4 показывает функциональную блок-схему алгоритма оценки местоположения камеры для каждого кадра;
Фиг. 5 показывает функциональную блок-схему алгоритма разреженного выравнивания изображений (sparse image alignment - SIA);
Фиг. 6 показывает функциональную блок-схему алгоритма разреженного выравнивания характерных точек (sparse feature alignment - SFA);
Фиг. 7 показывает функциональную блок-схему алгоритма локальной групповой коррекции (local bundle adjustment - LBA);
Фиг. 8 показывает функциональную блок-схему алгоритма обновления фильтра глубины;
Фиг. 9 показывает функциональную блок-схему алгоритма уточнения местоположения камеры;
Фиг. 10 показывает функциональную блок-схему алгоритма оценки карты глубины;
Фиг. 11 показывает функциональную блок-схему алгоритма объединения глубин;
Фиг. 12 показывает функциональную блок-схему алгоритма реконструкции поверхности;
Фиг. 13 показывает функциональную блок-схему алгоритма наложения текстур;
Фиг. 14 показывает функциональную блок-схему алгоритма проверки видимости грани с использованием z-буфера;
Фиг. 15 показывает функциональную блок-схему алгоритма маркировки грани;
Фиг. 16 показывает функциональную блок-схему алгоритма заполнения дырок;
Фиг. 17 показывает функциональную блок-схему алгоритма генерирования атласа текстур и параметризации; и
Фиг. 18 показывает принципиальную схему мобильного устройства, в котором могут быть реализованы вышеупомянутые алгоритмы.
Осуществление изобретения
Различные варианты реализации данного изобретения далее описаны более подробно со ссылкой на приложенные чертежи. Однако, данное изобретение может быть осуществлено во многих других формах и не должно толковаться как ограниченное какой-либо определенной структурой или функцией, представленной в нижеследующем описании. Напротив, эти варианты реализации приведены для обеспечения подробности и полноты описания данного изобретения. Согласно данному описанию, специалистам в данной области техники будет очевидно, что объем данного изобретения охватывает любой вариант реализации данного изобретения, который описан здесь, независимо от того, реализован ли этот вариант реализации независимо или совместно с любым другим вариантом реализации данного изобретения. Например, устройство и способ, описанные здесь, могут быть реализованы на практике с использованием любого количества вариантов реализации, представленных здесь. Кроме того, следует понимать, что любой вариант реализации данного изобретения может быть реализован с использованием одного или более элементов и/или этапов, представленных в приложенной формуле изобретения.
Кроме того, один или более вариантов реализации, описанных здесь, могут быть реализованы посредством одной или более программ или команд, которые являются исполняемыми посредством одного или более процессоров. Эти программы или команды могут переноситься в машиночитаемом носителе. Примеры машиночитаемых носителей могут включать в себя, но не ограничиваясь этим, постоянные запоминающие устройства, такие как накопители на жестких дисках, на портативных устройствах. Мобильное устройство может быть любым устройством, обычно достаточно малым, чтобы быть портативным, которое снабжено одним или более процессорами или другими вычислительными блоками. Другие примеры компьютерных носителей информации включают в себя портативные запоминающие устройства, такие как CD- или DVD-диски, флэш-память или твердотельная память (как на многих сотовых телефонах или устройствах потребительской электроники) и магнитная память. Компьютеры, терминалы, сетевые устройства (например, мобильные устройства, такие как сотовые телефоны), все они являются примерами машин и устройств, которые используют процессоры, память и команды, хранящиеся на машиночитаемых носителях. Вдобавок, варианты реализации могут быть реализованы в виде компьютерных программ или используемой компьютерами несущей среде, способной переносить такую программу.
Слово «иллюстративный» используется здесь в смысле «используемый в качестве примера или иллюстрации». Любой вариант реализации, описанный здесь в качестве «иллюстративного», не должен обязательно рассматриваться в качестве предпочтительного или имеющего преимущество перед другими вариантами реализации.
Кроме того, термины, связанные с направлением, такие как «по часовой стрелке», «против часовой стрелки» и т.д., используются со ссылкой на ориентацию описываемой (описываемых) фигуры (фигур). Поскольку компоненты вариантов реализации данного изобретения могут быть ориентированы по-разному, термины, связанные с направлением, используются в целях иллюстрации и не предполагают никакого ограничения. Следует понимать, что могут быть использованы другие варианты реализации, и могут быть выполнены структурные или логические изменения, не выходя за рамки объема данного изобретения.
Фиг. 1 показывает иллюстративное применение данного изобретения. Предположим, что пользователь 100 желает реконструировать 3D-модель интересующего объекта 102, который для примера показан в виде автомобиля. Процесс 3D-реконструкции начинают со сканирования объекта 102 посредством модуля сканирования. В некоторых вариантах реализации модуль сканирования может быть реализован в виде монокулярной камеры или многовидовой стереокамеры, или датчика глубины, или их комбинации. Пользователь 100 может расположить объект 102 на подставке 104 для удобства. Во время сканирования объекта 102 камера портативного устройства 106, такого как, например, мобильный телефон, должна быть всегда направлена на объект 102. В качестве примера пользователь 100 может перемещаться по траектории 108, при этом направляя камеру на объект 102. Хотя траектория 108 показана в виде круговой траектории против часовой стрелки, специалистам в данной области техники должно быть ясно, что этот тип траектории не представляет собой никакого ограничения для данного изобретения, и при необходимости могут быть использованы другие типы траекторий. Например, траектория 108 может быть замкнутым или незамкнутым контуром, а также может иметь круговую или произвольную форму. Кроме того, пользователь 100 может перемещаться в направлении по часовой стрелке, направлении против часовой стрелки или как в направлении по часовой стрелке, так и в направлении против часовой стрелки, во время сканирования объекта 102 в зависимости от конкретных применений.
После завершения сканирования объекта 102 (которое, например, происходит, когда траектория 108 становится замкнутой), пользователь 100 должен остановить захват изображений объекта 102. После остановки захвата выполняют этап постобработки с использованием специального программного обеспечения, установленного на устройстве 106. Результатом этапа постобработки является текстурированная сетка (которая также называется здесь 3D-моделью объекта 102). Операция постобработки будет описана более подробно ниже. Текстурированную сетку сохраняют на устройстве 106 в некотором стандартном формате, и ее можно дополнительно использовать любым подходящим способом.
Фиг. 2 объясняет процесс 3D-реконструкции. Этот процесс может быть разделен на два основных этапа: этап в реальном времени и этап постобработки (которые оба показаны с использованием пунктирных линий). Этап в реальном времени начинается с подэтапа 200, на котором выполняют захват изображений, как показано выше со ссылкой на Фиг. 1. Эти изображения затем используют на подэтапе 202 для оценки местоположений камеры в режиме реального времени. Каждое местоположение камеры может быть охарактеризовано посредством набора разных параметров. Например, такой набор параметров может включать в себя координаты камеры и ориентацию камеры в пространстве. Ориентация камеры может быть задана посредством углов рыскания, наклона и/или крена. Подэтап 202 может быть выполнен с использованием системы одновременной навигации и составления карты (Simultaneous Localization and Mapping - SLAM). Использование координат и ориентации камеры гарантирует, что система SLAM оценивает траекторию камеры, а также ее ориентацию в каждый момент времени. Такой подход позволяет работать при любых условиях съемки, включая, но не ограничиваясь этим, перемещение, вращение, встряхивающие движения и т.д. Этап в реальном времени обычно выполняют на CPU устройства 106.
После завершения этапа в реальном времени процесс переходит к этапу постобработки. Этап постобработки выполняют как на CPU, так и на GPU устройства 106, и этот этап обычно занимает несколько секунд.
Известно, что система SLAM обычно приводит к существенному дрейфу траектории. Например, замкнутая круговая траектория обычно оценивается в качестве незамкнутой дуги. Для улучшения точности оцененных местоположений камеры (как траектории, так и ориентации камеры), используют подэтап 204, на котором уточняют оцененные местоположения камеры. С этой целью используют всю доступную информацию в отношении начальной и конечной точек траектории.
Таким образом, местоположения камеры оценивают в два этапа способом «от грубого к точному». Грубую оценку выполняют во время сканирования объекта 102 с использованием системы SLAM, а оцененные местоположения камеры уточняют на основе информации о начале и конце траектории для обеспечения компенсации смещения, вызванного особенностями конфигурации системы SLAM.
На основе уточненных местоположений камеры и захваченных изображений на подэтапе 206 конструируют карты глубины. Такие карты глубины из разных местоположений камеры объединяют на подэтапе 208. Результатом такого объединения является 3D-представление объекта 102, которое используют на подэтапе 210 для создания поверхностной сетки (также называемой здесь реконструкцией поверхности). Далее на подэтапе 212 накладывают текстуры на поверхностную сетку. Результатом такого отображения является текстурированная сетка (или 3D-модель) 214, которая характеризует объект 102. Результирующую текстурированную сетку показывают на дисплее устройства 106.
Таким образом, быструю реконструкцию 3D-модели обеспечивают за счёт высокоскоростного извлечения карты глубины и объединения карт глубины, реализованных с использованием CPU и GPU устройства 106. Высокое качество результирующей 3D-модели обеспечивают за счёт тщательной реконструкции поверхности и точного наложения текстуры.
Каждый из вышеуказанных подэтапов процесса 3D-реконструкции будет теперь описан более подробно со ссылкой на Фиг. 3-17.
Фиг. 3 показывает в общем виде алгоритм оценки местоположения камеры (подэтап 202).
Подобный подход был предложен в следующем документе - Christian Forster, Matia Pizzoli и Davide Scaramuzza. SVO: Fast semi-direct monocular visual odometry. In Robotics and Automation (ICRA), 2014 IEEE International Conference, страницы 15-22, IEEE, 2014. Главный недостаток алгоритма Форстера состоит в том, что он неудовлетворительно функционирует в случае быстрого вращения вокруг объекта и большого перекрытия. Алгоритм Форстера был разработан для микролетательных устройств (таких как квадрокоптер), которые перемещаются главным образом поступательно.
Алгоритм оценки местоположения камеры начинается с использования первого изображения 300 для инициализации 302 карты. Инициализация 302 карты означает инициализацию оценки местоположения камеры следующим образом. Мировая система координат задаётся совпадающей с системой координат первого изображения. Извлекают ключевые точки из первого изображения 300 с использованием алгоритма FAST, известного из уровня техники (см Edward Rosten и Tom Drummond, “Fusing points and lines for high performance tracking”, In Computer Vision, 2005, ICCV 2005, Tenth IEEE International Conference, том 2, страницы 1508-1515, IEEE, 2005). Назначают среднюю глубину сцены для каждой найденной ключевой точки. Эти ключевые точки вместе с назначенными глубинами сохраняют в базе 304 данных карт. Эта база данных хранит все ключевые точки, оцененные посредством алгоритма FAST. Все ключевые точки в базе данных карт сохраняют в мировой системе координат, которая является той же, что и система координат первого изображения 300.
Все последовательные изображения 306 (которые захватывают посредством камеры устройства 106) используют вместе с картами из базы 304 данных для принятия решения, какие кадры (или изображения) являются ключевыми кадрами (которые используют в целях сопровождения и 3D-реконструкции). Дополнительно местоположения камеры для этих ключевых кадров оценивают 308 вместе с обновлением карт в базе 304 данных. Результатом подэтапа 202 являются ключевые кадры 310 с оцененными местоположениями камеры.
Фиг. 4 объясняет обработку нового изображения 404 в алгоритме оценки местоположения камеры. В алгоритме оценки местоположения камеры используют подход системы SLAM, показанный на Фиг. 3. Оценку траектории камеры, а также ее ориентации в каждый момент времени выполняют с использованием нового подхода (Фиг. 4), включающего в себя этап оценки перемещения и этап проверки (которые оба показаны с использованием пунктирных линий).
Этап оценки перемещения реализуется следующим образом. На подэтапе 400 (который называют разреженным выравниванием изображений) оценивают местоположение камеры, соответствующее новому изображению 404, на основе ключевых точек из карты, сохраненной в базе 304 данных. На этом подэтапе точки из карты проецируют на изображение 404, и алгоритм непосредственного выравнивания изображения (Direct Image Alignment) используют для оценки местоположения камеры, соответствующего изображению 404.
Затем изображение 404 и соответствующее ему местоположение камеры используют на подэтапе 402 (который называют разреженным выравниванием характерных точек). На этом подэтапе точки из карты проецируют на изображение 404, и алгоритм сопровождения Лукаса-Канаде (Lucas Kanade tracker - LKT), известное из уровня техники (см Simon Baker и Iain Matthews, “Lucas-kanade 20 years on: A unifying framework”, International journal of computer vision, 56(3):221-255, 2004) используют для уточнения местоположения каждой точки на изображении. LKT сопровождает фрагмент (прямоугольную область) вокруг проекции точки с использованием метода градиентного спуска.
Далее обработка переходит к подэтапу 408 (который называют локальной групповой коррекцией), где используют изображение 404, соответствующее ему местоположение камеры и список точек карты с уточненными местоположениями. Местоположение камеры вычисляют на основе начальной аппроксимации, полученной на подэтапе 400, координат точек, сохраненных в базе 304 данных карт, и уточненных местоположений камеры, полученных на подэтапе 402. Это является классической задачей внешней калибровки (Perspective-n-Points - PnP). Такое оцененное местоположение камеры назначают для изображения 404 и используют во всех других частях алгоритма 202 оценки местоположения камеры без дополнительных изменений. После уточнения местоположения мировые 3D-координаты точек карты также уточняют.
Затем новое изображение 404 устанавливают в качестве последнего изображения 406 камеры для дальнейшего использования на подэтапах 400 и 402.
После этого новое изображение 404 и соответствующее ему местоположение камеры сохраняют в очереди 410 изображений. Изображения из очереди изображений затем используют на этапе проверки.
На этапе проверки каждое поступающее изображение (такое как изображение 404) проверяют на предмет того, является ли оно ключевым кадром или нет (подэтап 412).
Если изображение 404 является ключевым кадром, то его сохраняют в списке ключевых кадров 310 с оцененными местоположениями и используют на подэтапе 414 для извлечения характерных точек из изображения 404.
Далее выполняют подэтап 420, на котором создают фильтры глубины с использованием оценки глубины, равной текущей средней глубине сцены для каждой характерной точки, и сохраняют их в списке 422 активных фильтров глубины для дополнительного использования. Примеры использования таких фильтров глубины описаны в “Video-based, real-time multi-view stereo”, George Vogiatzis and Carlos Hernandez. Image and Vision Computing, 29(7):434-441, 2011.
Для обеспечения сканирования на 360 градусов фильтры глубины продлевают из предшествующих ключевых кадров. Фрагменты, связанные с фильтрами глубины, которые еще не сошлись, выравнивают на последнем ключевом кадре, и новый фрагмент связывают фильтром глубины для каждого фильтра, в то время как состояние фильтра глубины поддерживают неизменным. Это обеспечивает возможность схождения фрагментов в случае быстрого сканирования, когда фрагменты изменяются быстрее, чем сходятся фильтры глубины.
Если изображение 404 не является ключевым кадром, то обработка переходит к подэтапу 416 (который называют обновлением фильтров глубины). На этом подэтапе используют поиск вдоль эпиполярной линии для выравнивания характерной точки из списка 422 с точкой на новом изображении. Если это выравнивание является успешным, то глубину точки вычисляют с использованием технологий триангуляции. Эту глубину регистрируют в фильтре глубины соответствующей точки.
Затем каждый фильтр глубины проверяют на сходимость (подэтап 418). Если фильтр глубины сошёлся (т.е. изменение глубины является достаточно малым), то соответствующую точку добавляют в базу 304 данных карт и исключают из списка 422 активных фильтров глубины.
Этапы оценки перемещения и проверки выполняют в отношении каждого из захваченных изображений. После обработки всех изображений, полный список ключевых кадров 310 с оцененными местоположениями является доступным для использования на следующем подэтапе 204 (т.е. уточнение местоположения камеры).
Фиг. 5 объясняет подэтап 400 (т.е. разреженное выравнивание изображений).
Сначала извлекают 500 видимые точки для последнего изображения 406 камеры из базы 304 данных карт. Эти точки фильтруют для обеспечения сканирования на 360 градусов. При таких условиях должны быть приняты специальные меры для исключения следующих точек:
- Точки, которые были захвачены в существенно разных направлениях просмотра. В этом случае их изображения сильно отличаются от исходного фрагмента, и сопровождение не может быть надежным.
- Точки, которые перекрыты другими точками. Для фильтрации таких точек используют технологию z-буфера.
Затем фрагменты всех отфильтрованных точек объединяют 502 в один вектор характерных точек. Этот вектор характерных точек затем сопровождают 504 с использованием LKT в новом изображении 404 и получают 506 местоположение камеры нового изображения от средства сопровождения.
Фиг. 6 объясняет подэтап 402 (т.е. разреженное выравнивание характерных точек).
Сначала извлекают 600 видимые точки для последнего изображения 406 камеры из базы 304 данных карт, учитывая оцененное местоположение камеры. Создают 602 фрагмент независимо для каждой точки. Каждый фрагмент сопровождают 604 с использованием LKT в новом изображении 404 и получают 606 для каждой точки обновленное местоположение каждой точки на новом изображении.
Фиг. 7 объясняет подэтап 408 (т.е. локальную групповую коррекцию).
Местоположение 506 камеры нового изображения обновляют 700 с использованием процедуры PnP на основе начальной аппроксимации (полученной на подэтапе 400) и обновленного местоположения 606 каждой точки на новом изображении (полученного на подэтапе 402). Таким образом, получают 706 обновленное местоположение камеры нового изображения. Обновленное местоположение камеры назначают для нового изображения 404 и используют во всех других частях алгоритма 202 оценки местоположения камеры без дополнительных изменений.
Затем точки, которые использовались на подэтапе 402 несколько раз, выбирают 702 для оптимизации структуры. Используют технологию групповой коррекции для обновления 704 мировых 3D-координат этих точек на основе обновленного местоположения 606 каждой точки на изображениях и обновленных местоположений 706 камеры. Такие обновленные мировые 3D-координаты точек затем сохраняют в базе 304 данных карт.
Фиг. 8 объясняет подэтап 416 (т.е. обновление фильтров глубины).
Для каждого изображения неключевого кадра из очереди 410 обновляют фильтры глубины. Для каждого фильтра глубины из списка 422 вычисляют эпиполярную линию на новом изображении. Затем выполняют линейный поиск 800 вокруг оценки глубины вдоль этой эпиполярной линии. Далее LKT находит 802 оптимальное выравнивание точек из фильтра глубины в окрестности минимума поиска с использованием эпиполярной линии. Если LKT не может выполнить это, то тогда фильтр глубины обновляют с использованием флага 808 ошибки. Если LKT достигает успеха в нахождении оптимального выравнивания точек, то тогда находят глубину с использованием процедуры 804 триангуляции. Эту глубину используют для обновления 806 фильтра глубины. Обновление фильтра глубины используют для нахождения нового математического ожидания и дисперсии значения глубины для фильтра глубины.
Фиг. 9 объясняет подэтап 204 (т.е. уточнение местоположения камеры).
К этому моменту пользователем завершен этап в реальном времени, состоящий из подэтапов 200 и 202, и процесс 3D-реконструкции переходит к этапу постобработки, реализуемому с использованием CPU и GPU устройства 106.
Подэтап 204 реализуют с использованием CPU устройства 106. Местоположения камеры, полученные посредством системы SLAM, могут содержать существенное смещение и нуждаются в уточнении перед дополнительной обработкой. Это смещение может быть выражено в виде систематической ошибки в оценке координат x, y, z и углов рыскания, наклона и крена камеры. Уточнение местоположения камеры ориентировано на компенсацию этого смещения, улучшая таким образом общую точность местоположений камеры. Оно использует преимущества предшествующего знания о траекториях. Предположим, что траектория 108 имеет круговую форму. Тогда она имеет естественные точки замыкания контура. После детектирования точки замыкания контура можно оценить суммарное смещение местоположения камеры и скомпенсировать его. Уточнение местоположения камеры состоит из четырех этапов: замыкание (900) контура, коррекция (902) контура, повторное вычисление (904) структуры и групповая коррекция (906).
Этап 900 ориентирован на поиск петлевой точки в траектории. Для каждого принятого ключевого кадра проверяют, является ли петлевая точка подходящей для точки замыкания контура. Для каждого ключевого кадра вычисляют его относительное евклидово расстояние в пространстве SE3 до других ключевых кадров. Если это расстояние меньше порога , то тогда проверяют, сколько общих точек карты имеют ключевые кадры. Если два ключевых кадра  и  имеют более, чем  точек, то тогда вычисляют относительное ограничение расположения  с использованием алгоритма PnP из проекций общих точек. Если два пространственно близких кадра имеют мало или совсем не имеют общих точек, то эту пару кадров рассматривают в качестве подходящей для замыкания контура. Для выполнения замыкания контура необходимо вычислить ограничение местоположения с использованием алгоритма PnP, который требует соответствий между характерными точками. В местоположениях проекций точек из  извлекают набор характерных точек BRISK, известных из уровня техники (см Stefan Leutenegger, Margarita Chli, and Roland Yves Siegwart. Brisk: Binary robust invariant scalable keypoints. In Computer Vision (ICCV), 2011 IEEE International Conference on, страницы 2548-2555. IEEE, 2011), , инвариантных к масштабированию и вращению; из  извлекают набор подобных характерных точек  в местоположениях углов FAST. Характерные точки BRISK имеют ограниченную инвариантность к изменению точек просмотра. Поскольку траектория имеет круговую форму, изменение точки просмотра при повторной проверке той же части траектории является очень малым, и этим недостатком можно пренебречь.
Из этих двух наборов находят соответствия характерных точек. Поскольку 3D-координаты для характерных точек в наборе  известны, местоположение  относительно  может быть вычислено с использованием алгоритма PnP, что даёт в результате прямое ограничение . Ту же процедуру выполняют для , что даёт в результате обратное ограничение . Поиск соответствий между  характерными точками может дать неверные соответствия, что может привести к неверному решению PnP. Для предотвращения включения неверных решений PnP в уточнение местоположений, выполняют обратную проверку: согласно свойствам группы Ли, если существуют два местоположения камеры, не содержащие ошибок, то прямое и обратное ограничения должны соответствовать друг другу: , таким образом, несоответствие между прямым и обратным ограничениями может быть вычислено как
.
Если несоответствие  становится меньше порога , то прямое  и обратное  ограничения добавляют в оптимизацию; иначе, упомянутые два ограничения рассматривают как ошибочные, и их игнорируют.
Ограничения, вычисленные на этапе 900, используют на этапе 902. Вследствие смещения для первого и замыкающего контур (конечного) ключевых кадров прямое и обратное ограничения не соответствуют друг другу. Для компенсации этого дрейфа местоположение камеры, соответствующее каждому ключевому кадру, повторно оценивают таким образом, чтобы эта разница стала распределенной среди кадров. Методика SLAM вычисляет для каждого местоположения камеры его дисперсию. Эта дисперсия указывает на то, до какой степени местоположение камеры искажено шумом измерения и дрейфом камеры. Для ключевых кадров, имеющих высокую дисперсию местоположения, задают более сильную коррекцию местоположения, в то время как для ключевых кадров, имеющих низкую дисперсию, задают меньшую коррекцию местоположения. В результате, точность местоположений камеры улучшается вследствие устранения дрейфа.
Оптимизированные местоположения камеры поступают затем на этап 904, где обновляют 3D-координаты точек вследствие изменений местоположений камеры. Это выполняют таким образом, чтобы глубина (координата z) точки относительно первого ключевого кадра, на котором она была видна, осталась такой же, как перед коррекцией контура.
Далее выполняют этап 906. На этом этапе, выполняют конечное уточнение местоположений камеры для уменьшения шума измерения. Для каждого ключевого кадра , проекцию точки m , полученную посредством выравнивания по методу SLAM, сравнивают теперь с прогнозируемой проекцией, вычисляемой в виде , а ошибку повторного проецирования точки описывают следующим образом: . Общую ошибку повторного проецирования вычисляют в виде
.
Эта ошибка учитывает шум измерения, присутствующий в местоположениях камеры. Групповая коррекция (bundle adjustment) минимизирует общую ошибку повторного проецирования посредством совместной оптимизации местоположений камеры и 3D-координат точек. Это выполняют посредством процедуры гауссовой оптимизации путём итерационной коррекции 3D-координат точек и местоположений камеры в направлении уменьшения ошибки повторного проецирования. После окончания этой оптимизации набор ключевых кадров с уточненными местоположениями камеры подвергают 908 дополнительной обработке.
Фиг. 10 объясняет подэтап 206 (т.е. оценку карты глубины).
Ключевые кадры с уточненными местоположениями камеры (которые получены в результате выполнения подэтапа 204) используют в качестве входных данных на подэтапе 206. Подэтап 206 состоит из следующих этапов. На этапе 1000 (который называют выбором стереопар) для каждого ключевого кадра выбирают другой кадр и образуют нескорректированную стереопару. Выбор второго кадра основан на местоположениях камеры для обеспечения достаточного, но не слишком большого, перемещения между изображениями стереопары. Стереопару и соответствующее местоположение камеры используют для вычисления карты глубины.
Карту глубины вычисляют с использованием пирамидальной методики «от грубого к точному». Сначала выполняют этап 1002 (который называют грубой оценкой глубины), где используют дискретизацию низкого разрешения в отношении изображений из стереопары, что даёт в результате карту глубины низкого разрешения. Карта глубины низкого разрешения может быть дополнительно отфильтрована на этапе 1004 (который называют фильтрацией глубины). Затем на следующем уровне пирамиды используют дискретизацию более высокого разрешения, и результат с низким разрешением из предшествующего этапа масштабируют (этап 1006) и используют в качестве оценки карты глубины текущего уровня. Дополнительно эту грубую оценку уточняют с использованием более точного дискретизированного изображения на текущем уровне пирамиды (этап 1008), и она может быть дополнительно отфильтрована (этап 1004). Эту процедуру дискретизации с повышением разрешения выполняют несколько раз в цикле 1010, пока не будет получена карта глубины необходимого разрешения, или пока не вступят в силу ограничения времени выполнения.
На первом (самом грубом) уровне пирамиды должно быть обработано только малое количество пикселей, так что может быть использован более сложный (а также более точный) способ оценки карты глубины. Например, в случае способов поблочного сравнения или фильтрации объемной целевой функции, может быть использовано окно большего размера, что обычно обеспечивает лучшую точность при затратах большего времени выполнения.
Текущая реализация этапа 1002 (т.е. грубая оценка глубины) состоит из следующих пяти подэтапов: оценки диапазона поиска и дискретизации, вычисления целевой функции согласования, агрегирования целевых функций, оценки диспаратности на основе минимизации целевой функции и триангуляции глубины. Диапазон поиска оценивают из заданных оценок нижнего и верхнего возможных значений глубины для текущего пикселя в первом изображении, которые могут быть получены из разреженного облака точек реконструированной сцены, созданного во время применения подхода SLAM. Эти значения обеспечивают возможность определения сегмента поиска на эпиполярной линии, соответствующего текущему пикселю. Затем дискретизация пикселей может быть использована в отношении сегмента поиска на втором изображении для определения возможных местоположений точки второго изображения, соответствующей текущему пикселю первого изображения. Целевую функцию согласования вычисляют из пиксельного цветового различия или другой метрики расстояния на основе цвета изображения или градиента. Агрегирование целевых функций выполняют посредством взвешенного накопления целевых функций в некоторой области вокруг текущего пикселя. Диспаратность оценивают посредством стратегии минимизации целевой функции «победитель получает все» (winner-takes-all - WTA) вдоль сегментов поиска на эпиполярной линии. Глубину триангулируют из соответствующих местоположений точки на обоих изображениях стереопары с использованием эпиполярных ограничений.
Несмотря на тот факт, что изображения в стереопаре не ректифицированы, текущий алгоритм обеспечивает очень эффективную параллельную реализацию на графическом процессоре (graphical processor - GPU) устройства 106. Потребление ресурсов памяти может быть также уменьшено, поскольку нет необходимости сохранения полной объёмной целевой функции в памяти. Изображение может обрабатываться малыми областями, и для каждой из них значения целевой функции согласования может быть сохранено в локальной памяти GPU.
Поскольку вычисленные карты глубины используют в объединении карт глубины, необходимо отфильтровать неверные оценки карт глубины, насколько это возможно, и оставить только значения глубины, которые являются точными с наивысшей достоверностью, поскольку способы объединения обычно могут хорошо восстанавливать недостающие данные посредством интерполяции или распространения из существующих значений, но являются более чувствительными к сильным отклонениям. Отклонения глубины могут быть эффективно отфильтрованы посредством анализа накопленных отношений целевой функции к ее минимальному значению для текущего пикселя во время минимизации целевой функции WTA. Дополнительная фильтрация может быть выполнена с использованием левой-правой проверки на согласованность. Фильтрация отклонений может быть также включена в стратегию «от грубого к точному», посредством выполнения ее на каждом уровне пирамиды, таким образом уменьшая вычислительные затраты на более точных уровнях пирамиды.
Текущая реализация этапа 1004 (т.е. фильтрация глубины) состоит из следующих двух подэтапов: фильтрации фотометрической неоднозначности и левой-правой проверки на согласованность. Фотометрическую неоднозначность оценивают во время минимизации целевой функции WTA и вычисляют посредством анализа накопленных отношений целевой функции к ее минимальному значению для текущего пикселя. Когда текстура отсутствует или является неоднозначной (периодической вдоль эпиполярной линии), многие целевые функции будут иметь значения, подобные минимуму целевой функции, что даёт отношения, равные, приблизительно, 1, что позволяет отфильтровать эти неоднозначности посредством анализа этих отношений. Левую-правую проверку на согласованность выполняют посредством анализа согласованности карт глубины как для левых, так и для правых изображений в стереопаре. Согласованность определяют посредством проверки ошибок повторного проецирования для каждого пикселя с использованием значений глубины из обеих карт глубины.
Этап фильтрации глубины позволяет существенно уменьшить количество пикселей, подлежащих обработке на следующем уровне пирамиды. Выполнение фильтрации глубины на каждом уровне существенно уменьшает время выполнения, поскольку более точные уровни пирамиды обычно являются значительно более медленными, чем грубые уровни пирамиды.
Текущая реализация обновления карт глубины на следующем уровне пирамиды состоит из следующих двух этапов: масштабирование грубой карты глубины (этап 1006) и уточнение карты глубины (этап 1008). Грубая карта глубины может быть масштабирована с высокой точностью с использованием различных способов фильтрации, таких как фильтрация ближайшего соседа, билинейная фильтрации, фильтрация в окне, гауссовая фильтрации, двусторонняя фильтрации по цветному изображению или другие способы фильтрации с сохранением контура. В настоящее время при масштабировании глубины используют простую билинейную фильтрацию с обработкой недостающих значений в целях обеспечения необходимой производительности. Масштабированную глубину используют в качестве предварительной информации для уточнения глубины (этап 1008), во время которого выполняют несколько этапов поиска с использованием предварительной информации. На каждом этапе повторно оценивают целевую функцию согласования с использованием более мелкой дискретизации (в соответствии с текущим уровнем пирамиды). Находят соответствующую точку из минимизации уточненных значений целевой функции по всем этапам, и опять триангулируют глубину. Уменьшение вспомогательной области для оцениваемого пикселя на каждом более точном уровне пирамиды уменьшает эффект сглаживания и выдает более точные значения глубины.
Результатом подэтапа 206 является набор карт глубины с местоположениями камеры (блок 1012), которые хранят информацию о глубине захваченного объекта для каждого ключевого кадра.
Фиг. 11 объясняет подэтап 208 (т.е. объединение карт глубины).
j
j
Во-первых, выполняют этап 1100 (который называют объемной интеграцией карт глубины), где набор карт глубины с местоположениями камеры, вычисленными на подэтапе 206, обрабатывают для получения объемной интеграции карт глубины или объединения. Результат такого объединения используют для генерирования представления в виде 3D-воксельной гистограммы (этап 1102). Для каждого вокселя приближенное расстояние (со знаком) до поверхностей, созданных посредством карт глубины, вычисляют, ограничивают заданным пользователем порогом, масштабируют в интервале (-1, 1) и сохраняют в виде гистограммы соответствующих частот n. Каждый воксель имеет гистограмму, состоящую из N бинов (элементов гистограммы), вокруг равноудаленного центра бинов c. N-2 бинов используют для представления распределения значений внутри интервала (-1, 1), т.е. вокселей, близких к предлагаемой поверхности. Два отдельных бина резервируют для значений, указывающих на большее расстояние до этой поверхности, причем один бин считает (масштабированные) расстояния, меньшие или равные -1 (перекрытый воксель), и один бин представляет значения, большие, или равные 1 (пустой воксель). Общее количество отсчётов гистограмм ограничено количеством доступных карт глубины.
Во-вторых, во время этапа 1104 (который называют оптимизацией объемной гистограммы), используют вариационную методику. Получают (этап 1106) представление в виде функции расстояния (со знаком) 3D-вокселя посредством итерационной минимизации функции энергии
как это описано в следующем документе: Christopher Zach, “Fast and high quality fusion of depth maps”, In Proceedings of the international symposium on 3D data processing, visualization and transmission (3DPVT), том 1, Citeseer, 2008.
Результатом подэтапа 208 является представление усеченной функции расстояния со знаком (truncated signed distance function - TSDF) захваченного объекта 102, которое является одним из способов представления произвольной 3D-поверхности, широко используемым в компьютерной графике.
Фиг. 12 объясняет подэтап 210 (т.е. реконструкцию поверхности).
Во-первых, выполняют этап представления в виде воксельного октадерева (обозначенный «1200»), на котором представление усеченной функции расстояния со знаком, вычисленное на подэтапе 208, обрабатывают для получения представления в виде воксельного октадерева для объекта 102. Дополнительно, представление в виде воксельного октадерева используют для получения представления в виде усеченной функции расстояния со знаком на основе октадерева (этап 1202). Максимальная глубина октадерева управляет сложностью (количеством многоугольников) 3D-сетки объекта 102.
Во-вторых, во время этапа извлечения изоповерхности (обозначенного «1204»), 3D-сетку (блок 1206) реконструируют, как это описано в следующем документе: Michael Kazhdan, Allison Klein, Ketan Dalal, and Hugues Hoppe, “Unconstrained isosurface extraction on arbitrary octrees”, In Symposium on Geometry Processing, том 7, 2007.
Фиг. 13 объясняет подэтап 212 (т.е. наложение текстуры).
3D-сетку 1206 и ключевые кадры 908 с уточненными местоположениями камеры используют в качестве входных данных на этом подэтапе. Сначала, на этапе 1300 (который называют проверкой видимости грани с использованием z-буфера), проверяют, из каких местоположений камеры каждая грань является видимой. Камеру характеризуют посредством изображения камеры и местоположения камеры - другими словами, ключевого кадра и уточненного местоположения (908), соответственно.
Каждая видимая грань сетки должна быть текстурирована посредством проецирования одного из изображений камеры. На этапе 1302 (который называют маркировкой грани) определяют, какие из изображений камеры будут использованы для этой цели. После этого этапа имеется некоторое количество фрагментов - закрытых областей граней сетки - которые снабжены текстурами из одного изображения. Швы между соседними фрагментами могут быть очень заметными. На этапе 1304, (который называют глобальной настройкой цвета), настраивают неоднородности цвета между соседними фрагментами, обеспечивая меньшую видимость швов.
Этап 1308 (который называют заполнением дырок) используют для создания текстур для невидимых граней сетки.
Последний этап 1310 (который называют генерацией атласа текстуры и параметризацией сетки) используют для создания атласа текстуры из изображений камеры и текстур для невидимых граней. Также параметризацию сетки, т.е. определение координат текстур на атласе текстуры для каждой грани сетки, выполняют для получения текстурированной сетки в качестве результата (подэтап 214).
Фиг. 14 объясняет этап 1300 (т.е. проверку видимости грани с использованием z-буфера).
Как показано, сетка 1206 и ключевые кадры 908 с уточненными местоположениями камеры используют в качестве входных данных на этом этапе. Для каждого местоположения камеры определяют, какие грани сетки являются видимыми из него.
Первой целью является генерация z-буфера (подэтап 1400) - изображения (имеющего тот же размер, что и изображение камеры), каждый пиксель которого содержит минимальную глубину граней, которые проецируют в этот пиксель. Глубина грани сетки является максимальной глубиной её точек (вершин) в координатах текущей камеры.
Далее точки разделяют на видимые и невидимые (подэтап 1402). Точку p маркируют как видимую из местоположения камеры r, если p может быть спроецирована в пиксель pxl на изображении камеры r, и  , где  - глубина p в координатах камеры r,   - значение z-буфера в pxl.
После этого каждая грань  сетки является видимой из местоположения камеры r (подэтап 1408), если все общие точки  являются видимыми из r и  (подэтап 1404), где  - угол между направлением просмотра r и нормалью к грани , иначе, грань  назначают в качестве невидимой из местоположения камеры r (подэтап 1406).
В результате образуют два списка: видимые грани 1410 сетки с информацией, из каких местоположений камеры они являются видимыми, и невидимые грани 1412 сетки.
Фиг. 15 объясняет этап 1302 (т.е. маркировка граней).
Целью этого этапа является вычисление вектора l 1504 маркировки, который определяет для каждой видимой грани  сетки из списка 1410 текстуры из изображения камеры  из ключевых кадров 908. Вектор l маркировки находят посредством минимизации энергии марковского случайного поля (Markov random field - MRF):
.
Первый член определяет качество фрагментов текстуры, используемых для текстурирования. В этом случае, , где  - угол между направлением просмотра  и нормалью к грани .
Второй член определяет видимость швов между соседними фрагментами текстуры. В этом случае, если грани  и  сетки имеет смежную границу , то тогда видимость швов измеряют с использованием интегрального различия цветов  в соответствующих фрагментах текстуры , :
- оператор проецирования для камеры ,  - евклидово расстояние в цветовом пространстве RGB.
На подэтапе 1500, вычисляют унарный и парный потенциалы ( и , соответственно) для всех видимых граней 1410 сетки и изображений камеры из ключевых кадров 908. Используют нормированные потенциалы, так что  показывает компромисс между двумя слагаемыми энергии, который экспериментально устанавливают равным 50.
Далее выполняют (подэтап 1502) алгоритм последовательной передачи повторно взвешенных сообщений (sequential reweighted message passing - SRMP) для решения задачи MRF. В результате, получают вектор l 1504 маркировки, который характеризует маркировки грани.
Дополнительно выполняют этап 1304 (т.е. глобальную настройку цвета). Здесь сетка 1206, ключевые кадры 908 с уточненными местоположениями камеры и вектор 1504 маркировки используют в качестве входных данных. Вектор 1504 маркировки определяет количество фрагментов текстуры, и после выполнения этого этапа швы между ними становятся менее заметными.
Пусть является функцией интенсивности текстуры, соответствующей одному из компонентов RGB. Предполагается, что она является непрерывной на каждом фрагменте текстуры и имеет неоднородности на границах между ними. Целью является нахождение выравнивающей функции , так чтобы  была непрерывной на фрагментах и границах.
Каждую общую точку  шва разделяют на несколько копий:  является текстурированной из ,  является текстурированной из , … - для каждой из , содержащихся в фрагменте. Выравнивающую функцию  находят в каждой общей точке сетки:
,
где  - среднее значение взвешенной суммы цветов вдоль границ шва, содержащего  из изображения камеры . Во взвешенной сумме вес в  равен 1 и линейно уменьшается вдоль границы.
В этом случае задачу решают с использованием метода сопряженных градиентов отдельно для каждого канала RGB. После вычисления значений  для всех общих точек сетки вычисляют значения между общими точками с использованием интерполяции. Наконец, выравнивающую функцию применяют к соответствующим фрагментам изображений камеры - ключевым кадрам 908.
Фиг. 16 объясняет этап 1308 (т.е. заполнение дырок). Он состоит из следующих двух подэтапов: назначения цвета для невидимых точек (как указано посредством 1600-1610) и записи текстур для невидимых граней сетки (как указано посредством 1612).
Цвета невидимых точек вычисляют с использованием интерполяции цветов известных точек. Цвет точки , которая была видимой перед этим этапом, получают из того же изображения камеры, что и для текстурирования грани сетки, которая содержит . Если существуют несколько граней, содержащих , которые маркированы по-разному, то выбирают любую из них.
Сначала все невидимые точки (общие точки невидимых граней сетки из списка 1412) добавляют 1600 в набор для обработки.
Далее выполняют процесс интерполяции, пока набор для обработки не станет пустым 1602.
Во время процесса интерполяции вычисляют 1604 цвета для каждой точки p из набора для обработки, которая имеет более чем одну видимую соседнюю точку. Цвет p получают посредством усреднения 1606 цветов всех ее видимых соседних точек. Каждый из каналов RGB усредняют отдельно. Затем p маркируют в качестве видимой 1608 и удаляют 1610 из набора для обработки. Процесс интерполяции выполняют, пока набор для обработки не станет пустым 1602.
Наконец, конструируют 1612 текстуры 1614 для невидимых граней из блоков размером 5*5 пикселей, один блок для каждой грани. Структура блока показана на Фиг. 17. Ячейки с , ,  имеют цвета общих точек грани (первой, второй и третьей, соответственно), которые были найдены во время процесса интерполяции. Цвета других ячеек вычисляют следующим образом: цвет каждой ячейки является средним значением цветов ячеек, из которых есть стрелки к этой ячейке.
Конечным этапом процесса наложения текстуры (подэтап 212) является этап 1310 (т.е. генерирование атласа текстуры и параметризация). Сначала, для минимальной ограничивающей рамки изображений камеры, выбирают области, которые используют для наложения текстуры. Затем эти части масштабируют и объединяют для создания атласа текстуры некоторого размера, с использованием текстур для невидимых граней из списка 1614. Далее выполняют параметризацию сетки, т.е. вычисление координат текстуры для каждой общей точки грани сетки.
Фиг. 18 схематично иллюстрирует конструктивные элементы устройства 106 согласно одному иллюстративному варианту реализации данного изобретения. Как показано, устройство 106 состоит из следующих элементов: дисплея 1800, центрального процессора (CPU) 1802, одного или более устройств 1804 человеческого интерфейса, памяти 1806, графического процессора (GPU) 1808, аккумуляторной батареи 1810, и камеры 1812.
CPU 1802 и GPU 1808 исполняют вышеописанный процесс 3D-реконструкции. Важно, что процесс 3D-реконструкции может быть выполнен на процессоре с низкой производительностью и энергопотреблением. Следует также отметить, что стадии, подстадии, этапы, подэтапы и другие операции, описанные здесь, могут быть выполнены с использованием одного процессора, или каждая из таких стадий, подстадий, этапов, подэтапов и других операций может быть выполнена с использованием одного или более процессоров одного или разных типов, в зависимости от конкретных применений.
Память 1806 хранит различное программное обеспечение, необходимое для реализации процесса 3D-реконструкции, которое может быть использовано CPU 1802 и GPU 1808. Кроме того, память 1806 может также хранить промежуточные данные и конечные результаты, полученные на каждой или некоторой из стадий, подстадий, этапов, подэтапов, и других операций, описанных здесь. Важно отметить, что вышеописанный процесс 3D-реконструкции может быть реализован с использованием небольшого размера памяти.
Камеру 1812 (которую называют здесь также модулем сканирования) используют для сканирования интересующего объекта 102 и захвата его изображений.
Дисплей 1800 используют для помощи пользователю 100 в корректном указании на объект 102 и для демонстрации результатов выполнения и конечных результатов, например, текстурированной сетки объекта 102.
Устройства 1804 человеческого интерфейса, такие как одна или более кнопок, микрофонов, громкоговорителей и т.д., используют для начала и остановки сканирования и для взаимодействия с текстурированной сеткой объекта 102.
Аккумуляторная батарея 1810 необходима для функционирования устройства 106.
Устройство 106 не ограничено конструкцией, показанной на Фиг. 18. Должно быть ясно, что количество конструктивных элементов и/или их расположение могут быть изменены в зависимости от конкретных применений. В качестве примера, устройство 106 может быть реализовано без устройств 1804 человеческого интерфейса. Вместо этого, дисплей 1800 может быть выполнен в виде сенсорного экрана, отображающего пользовательский интерфейс для управления сканированием объекта 102. Такой пользовательский интерфейс может обеспечить пользователю возможность изменения угла сканирования и/или времени сканирования, или он может быть снабжен другими функциями, необходимыми для процесса 3D-реконструкции.
Согласно одному или более иллюстративным вариантам реализации, устройство 106 может быть соединено, беспроводным способом или посредством проводов, с одним или более средствами печати или с одним или более портативными устройствами, подобными устройству 106. Например, такое средство печати может быть средством 3D-печати, и на нем может быть распечатана текстурированная сетка (3D-модель) объекта 102. В случае соединения с другими портативными устройствами, устройство 106 может передавать им 3D-модель объекта 102 для разных целей.
В качестве примера, во время процесса 3D-реконструкции пользователь 100 может предпринять следующие действия:
1. Пользователь 100 открывает программное обеспечение, установленное на устройстве 106, и запускает сканирование объекта 102 с использованием камеры 1812 и, если доступно, одного или более устройств 1804 человеческого интерфейса (например, сканирование объекта 102 может быть активировано пользовательским речевым сигналом из микрофона);
2. Пользователь перемещается вдоль траектории 108 вокруг объекта 102. Программное обеспечение обеспечивает удобное для пользователя руководство в отношении того, как перемещать камеру вокруг объекта для правильной 3D-реконструкции, с использованием сообщений, показываемых на дисплее 1800. Поток видеоданных захватывают с использованием камеры 1812, оценку местоположения камеры (подэтап 202) реализуют с использованием CPU 1802, и автоматически выбранные ключевые кадры с соответствующими местоположениями камеры сохраняют в памяти 1806;
3. Пользователь останавливает сканирование объекта 102 и касается кнопки «Начать реконструкцию». Постобработку, которая состоит из подэтапов 204, 206, 208, 210, 212, выполняют с использованием CPU 1802 и GPU 1808, при этом сохраняя промежуточные вычислительные результаты в памяти 1806. В результате, пользователь 100 видит 3D-модель 214 объекта 102 на дисплее 1800. Пользователь 100 может поворачивать или масштабировать 3D-модель.
4. Пользователь может запомнить результирующую модель, сохранить ее в цифровом хранилище, передать ее между компьютерами любого типа (персональными, серверными или мобильными), и обрабатывать ее цифровым способом разными путями (например, с использованием рендеринга, изменения текстуры, и т.д.).
Предложенный вариант реализации обеспечивает пользователю способ быстрого и удобного для пользователя захвата объекта вследствие автоматического выбора ключевых кадров, которые используют для 3D-реконструкции. Кроме того, не требуется никакого ручного сохранения изображений или передачи их к облачной вычислительной службе.
Хотя вышеописанные варианты реализации предполагают, что упомянутую постобработку выполняют на устройстве 106, такая реализация не является единственно возможной. Например, может быть использована облачная вычислительная служба для такой постобработки. Это позволяет использовать те же алгоритмы, описанные выше, но выполнять более точную обработку данных. В частности, могут быть увеличены разрешения изображений для обработки карт глубины и наложения текстуры, объемное разрешение для объединения глубин, количество итераций для процедуры групповой коррекции и т.д.
Кроме того, возможна реализация «отдельный PC», когда изображения от устройства 106 передают к PC-хосту в реальном времени, и реализуют на PC-хосте как упомянутую оценку местоположения камеры, так и постобработку.
Изображения, захваченные посредством камеры 1812, являются не единственными возможными данными для упомянутой оценки местоположений камеры (подэтап 202). Например, устройство 106 может иметь некоторые дополнительные устройства, такие как инерциальные датчики, данные из которых могут быть использованы дополнительно к захваченным изображениям.
Согласно заявленному изобретению, текстурированную сетку получают в качестве результата 3D-реконструкции. Существуют два разных режима: основной режим модели объекта и режим модели лица. Основное различие между этими моделями заключается в характере сканирования: в случае основного режима модели объекта выполняют сканирование на 360 градусов, в то время как в случае режима модели лица сканируют только грань объекта при угле сканирования, равном 180 градусам. Однако, возможны любые другие формы представления 3D-модели. Например, для 3D-реконструкции может быть использовано плотное облако 3D-точек. 3D-модель без текстур в виде многоугольной сетки можно использовать для представления и визуализации как объекта, так и среды.
Любые виды мобильных устройств, которые удовлетворяют требованиям, описанным со ссылкой на Фиг. 18, такие как смартфоны, планшетные компьютеры, интеллектуальные часы и т.д., могут быть использованы для вышеописанного процесса 3D-реконструкции.
Одной из возможных реализаций изобретения является 3D-печать (послойное изготовление), когда твердотельные 3D-объекты изготавливают из реконструированной 3D-модели посредством последовательной укладки слоев материала, пока не будет сформирован весь объект.
3D-фотографирование является другим применением данного изобретения, когда реконструированная 3D-модель человеческого лица может быть сохранена в виде цифрового файла для дальнейшего просмотра или совместного использования через Интернет.
Хотя здесь описаны иллюстративные варианты реализации данного изобретения, следует отметить, что в этих вариантах реализации данного изобретения могут быть выполнены любые изменения и модификации, не выходя за рамки объема правовой охраны, который определен формулой изобретения. В приложенной формуле изобретения упоминание элементов в единственном числе не исключает наличия множества таких элементов, если в явном виде не утверждается иное.