ВЫРАВНИВАНИЕ УПОРЯДОЧЕННОГО СТЕКА ИЗОБРАЖЕНИЙ ОБРАЗЦА
ALIGNMENT OF ORDERED STACK OF IMAGES OF SAMPLE

2420-183949RU/035
ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ
Настоящее изобретение относится к области техники выравнивания упорядоченного стека изображений образца и более конкретно к способу и устройству для выравнивания упорядоченного стека изображений образца, разделенного на части.
УРОВЕНЬ ТЕХНИКИ ИЗОБРЕТЕНИЯ
Образцы разделяются на части и отображаются в целях анализа, а также обучения. При использовании стека изображений, которые описывают образец, разделенный на части, можно создавать искусственные представления этого образца для анализа структуры и анатомии образца. После нарезки образца в лаборатории, например, из парафинового блока теряется общая система координат образца, разделенного на части, что приводит к рассогласованию в изображениях стека. Этот изъян влечет за собой линейные и угловые расхождения между изображениями стека. Другой источник рассогласования может происходить из подготовки среза, которая основана на этапах, выполняемых вручную. Может происходить линейное смещение, изменение масштаба и растяжение. Кроме того, могут быть обнаружены такие деформации, как растянутая ткань, нарушенная ткань и отсутствующая ткань.
Для выравнивания гистологических срезов образца в цифровом представлении то есть, после отображения, требуется нейтрализовать результаты процесса деформации, а также изъян общей системы координат. Типичным решением для выравнивания является добавление маркеров в виде искусственных проверочных точек в блоке образца во время подготовки, например, посредством помещения маркеров в парафин, которые обнаруживаются после отображения. Затем позиции этих маркеров могут быть использованы для вычисления параметров преобразования. Однако такие дополнительные маркеры влекут за собой дополнительный этап подготовки. Кроме того, объем памяти для хранения изображений после преобразования в цифровую форму увеличивается в связи с тем, что отображается дополнительная область для захвата маркеров, которые добавляются к реальному образцу. Следовательно, желательно выровнять упорядоченный стек изображений без использования дополнительных маркеров в блоке образца.
В статье "Компьютерное выравнивание и реконструкция последовательных сечений", Джон К. Фиэла и Кирстен М. Харрис, Бостонский Университет, журнал Микроскопия и анализ, страницы 5-7, январь 2002, описывается способ выравнивания последовательности изображений без необходимости добавления дополнительных маркеров в блок образца. Для выравнивания изображения преобразуются посредством вычисления из ряда точечных соответствий, введенных пользователем. Для выравнивания последовательности изображений процесс выравнивания повторяется, причем изображение, которое должно быть выровнено следующим, выравнивается с изображением, выровненным непосредственно перед ним.
Дополнительно к вышеупомянутой ссылке, дополнительные ссылки упоминаются в следующих абзацах:
РАСКРЫТИЕ ИЗОБРЕТЕНИЯ
Однако без использования дополнительных маркеров в блоке образца различные локальные деформации, такие как отсутствующая и нарушенная ткани, делают сложным надежное выравнивание каждого изображения образца, разделенного на части.
Учитывая большой размер изображений патологической анатомии, как правило, 64 тыс.×64 тыс. пикселов, для автоматизированного выравнивания становятся критическими требования по вычислениям. Следовательно, очень желательны быстрые процедуры выравнивания, которые упрощают требования по вычислениям.
Предпочтительно достигнуть способа выравнивания упорядоченного стека изображений образца и достигнуть устройства выравнивания, которые позволяют надежное выравнивание упорядоченного стека изображений и которые могут позволить быстрое выравнивание с низкими требованиями по вычислениям.
Для лучшего устранения одной или более из этих проблем в первом аспекте изобретения представлен способ выравнивания упорядоченного стека изображений образца, содержащий последовательные этапы: a) определения, по меньшей мере, для двух уже выровненных изображений упорядоченного стека соответствующих рассогласований с невыровненным изображением, которое должно быть выровнено следующим в упорядоченном стеке; b) выбора в качестве опорного изображения, по меньшей мере, из двух выровненных изображений выровненного изображения, имеющего наименьшую величину рассогласований с невыровненным; и c) выравнивания невыровненного изображения относительно выбранного опорного изображения.
Для дальнейшего устранения одной или более из этих проблем во втором аспекте настоящего изобретения представлено устройство для выравнивания упорядоченного стека изображений образца, содержащее следующие устройства: блок определения для определения, по меньшей мере, для двух уже выровненных изображений упорядоченного стека соответствующих рассогласований с невыровненным изображением, которое должно быть выровнено в упорядоченном стеке следующим; блок выбора для выбора, по меньшей мере, из двух выровненных изображений, в качестве опорного изображения, выровненного изображения, которое имеет наименьшую величину рассогласований с невыровненным изображением; и блок выравнивания для выравнивания невыровненного изображения с выбранным опорным изображением.
Определение, по меньшей мере, двух рассогласований для каждого изображения, которые должны быть выровнены, может обеспечивать надежный способ выравнивания. Выбор в качестве опорного изображения для выравнивания выровненного изображения, обеспечивающего наименьшую величину рассогласований, также может гарантировать надежный способ выравнивания. Одно лишь выравнивание невыровненного изображения с выбранным опорным изображением, что подразумевает исключительно одно затратное в вычислительном отношении преобразование из невыровненного изображения в выровненное изображение, может обеспечить упрощенные требования по вычислениям и, дополнительно, может позволить быстрое выравнивание.
В соответствии, по меньшей мере, с одним вариантом осуществления, соответствующие рассогласования определяются посредством оценки движения так, чтобы каждое рассогласование описывалось посредством области оценочного смещения. Это может позволить быстрое определение соответствующих рассогласований и достигнуть упрощенных требований по вычислениям.
В соответствии, по меньшей мере, с одним вариантом осуществления, область смещения включает в себя, по меньшей мере, один вектор смещения, описывающий то, как сдвинуть пиксели в изображении, которое должно быть выровнено, для выравнивания этого изображения с выбранным опорным изображением. Также это может позволить быстрое определение соответствующих рассогласований и достигнуть упрощенных требований вычислительных ресурсов.
В соответствии, по меньшей мере, с одним вариантом осуществления, выровненные изображения и невыровненное изображение, которое должно быть выровнено следующим, разделяются на блоки, и соответствующие области смещения получаются посредством алгоритма поблочного сравнения. Это может дополнительно повысить надежность выравнивания.
В соответствии, по меньшей мере, с одним вариантом осуществления, соответствующая величина рассогласований вычисляется на основе соответствующей ошибки сравнения между соответствующим выровненным изображением и невыровненным изображением, которое должно быть выровнено следующим, причем соответствующие ошибки вычисляются на основе предварительно определенного критерия сравнения, и причем выровненное изображение, имеющее наименьшую ошибку соответствия, выбирается в качестве опорного изображения. Этот признак также может позволить быстро определять соответствующие рассогласования и достигать упрощенных требований вычислительных ресурсов.
В соответствии, по меньшей мере, с одним вариантом осуществления, выравнивание невыровненного изображения с выбранным опорным изображением включает в себя преобразование невыровненного изображения на основе параметров преобразования, описывающих то, как невыровненное изображение должно быть преобразовано для достижения выравнивания с выбранным опорным изображением, и причем для каждого этапа выравнивания преобразуется исключительно соответствующее невыровненное изображение, выравнивание которого выполняется в настоящий момент. Этот признак может позволить уменьшить затраты на вычислительных ресурсов, связанные с преобразованием невыровненного изображения в изображение, выровненное с выбранным опорным изображением.
В соответствии, по меньшей мере, с одним вариантом осуществления, невыровненное изображение, которое должно быть выровнено следующим, будет удалено из упорядоченного стека изображений, если вся величина определенных рассогласований будет выше заданного порогового значения, и, в таком случае, удаленное изображение может, в некоторых случаях, быть дополнительно заменено посредством интерполирования уже выровненных изображений, и/или выровненное изображение не будет использовано для дальнейших этапов определения рассогласований, если величина его рассогласований на текущем этапе определения рассогласования будет выше заданного порогового значения в отличие от оставшейся величины рассогласований. Этот признак может позволить увеличить надежность выравнивания и уменьшить чувствительность выравнивания относительно локальных деформаций.
В соответствии, по меньшей мере, с одним вариантом осуществления, перед определением соответствующих рассогласований, по меньшей мере, одно из изображений преобразуется в другое пространство сигналов так, чтобы все изображения находились в совместимом пространстве сигналов. Этот признак может позволить выравнивать изображения различной окраски при сохранении простого критерия сравнения. Этот признак также может позволить использовать пространство сигналов, которое позволяет улучшать или дополнительно упрощать определение рассогласований.
В соответствии, по меньшей мере, с одним вариантом осуществления, устройство включает в себя блок оценки движения для определения соответствующих рассогласований посредством оценки движения так, чтобы каждое рассогласование было описано посредством предполагаемой области смещения. Блок оценки движения может позволить быстрое и эффективное в вычислительном отношении определение величины рассогласований.
В соответствии, по меньшей мере, с одним вариантом осуществления, соответствующие рассогласования определяются посредством распознавания объектов. Этот признак может позволить дополнительно увеличить надежность процесса выравнивания.
В соответствии, по меньшей мере, с одним вариантом осуществления, соответствующие рассогласования определяются посредством оценки движения так, чтобы каждое рассогласование было описано как область оценочного смещения, а если неоднократно возникает большая величина рассогласований, то тогда рассогласования определяются посредством распознавания объектов вместо оценки движения. Этот признак может позволить автоматически переключаться между быстрым и простым процессом определения рассогласования, который основан на оценке движения, и более сложным и надежным процессом определения рассогласования, который основан на распознавании объектов так, чтобы соотношение между надежностью и затратами вычислительных ресурсов для выравнивания было оптимизировано при изучении рассогласований, определенных в предшествующих повторениях выравнивания.
Все вышеупомянутые этапы способа предназначены для выполнения их автоматически или, по меньшей мере, частично автоматически.
Дополнительные варианты осуществления получаются посредством комбинирования двух или более отдельных признаков, заявленных в вышеизложенных абзацах, каждый из которых начинается «в соответствии, по меньшей мере, с одним вариантом осуществления». Следовательно, эти вышеизложенные параграфы не должны интерпретироваться так, что вариант осуществления может содержать исключительно отдельные признаки вышеизложенных признаков. Дополнительные варианты осуществления устройства соответствующим образом получаются таким образом, чтобы любое устройство, которое приспособлено для выполнения способа, представляющего вариант осуществления, также являлось вариантом осуществления.
Кроме того, настоящее изобретение относится к компьютерному программному продукту, позволяющему процессору выполнять вышеизложенные этапы способа, и относится к носителю информации, на котором сохраняется такой компьютерный программный продукт.
Эти и другие аспекты изобретения будут очевидны и объяснены со ссылкой на варианты осуществления, описанные далее в настоящем документе.
КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ
Фиг.1 иллюстрирует процесс последовательного выравнивания упорядоченного стека изображений образца.
Фиг.2 является графическим представлением блок-схемы для иллюстрации способа выравнивания упорядоченного стека изображений образца в соответствии, по меньшей мере, с одним вариантом осуществления настоящего изобретения.
Фиг.3 иллюстрирует устройство для выравнивания упорядоченного стека изображений образца в соответствии с вариантом осуществления настоящего изобретения.
ОСУЩЕСТВЛЕНИЕ ИЗОБРЕТЕНИЯ
В следующих вариантах осуществления настоящее изобретение будет более подробно разъяснено в комбинации с сопроводительными чертежами.
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
3
1
0
2
Фиг.1 иллюстрирует процесс последовательного выравнивания упорядоченного стека изображений образца (который является, например, разрезанным образцом). Как показано на Фиг.1, перед выравниванием упорядоченного стека изображений, считается, что стек полностью невыровнен и включает в себя четыре невыровненных изображения c, c, c и c. Посредством последовательного или рекурсивного выравнивания изображений в стеке, которые все еще невыровнены, на основе уже выровненных изображений, как, например, изображенные в середине Фиг.1, которая изображает уже выровненные изображения r и r и изображения, которые все еще должны быть выровнены c и c, причем упорядоченный стек изображений может быть полностью выровнен так, чтобы все изначально невыровненные изображения c, с, с и с были преобразованы в выровненные изображения r, r, r и r. В последующем, обозначение, используемое для Фиг.1, будет использоваться на протяжении всего оставшегося описания: невыровненные изображения будут обозначены посредством ссылочного обозначения c, тогда как уже выровненные изображения будут обозначаться посредством ссылочного обозначения r. Соответствующая позиция изображения (независимо от того, выровненного или невыровненного) в упорядоченном стеке обозначается посредством подстрочного порядкового номера так, чтобы, например, выровненное изображение r было окружено посредством выровненного изображения r и невыровненного изображения c, как иллюстративно изображено в середине Фиг.1.
Фиг.2 является графическим представлением блок-схемы для иллюстрации способа выравнивания упорядоченного стека изображений образца в соответствии с вариантом осуществления настоящего изобретения.
0
0
В начале способа, в соответствии, по меньшей мере, с одним вариантом осуществления, на этапе S10 из Фиг.2, одно невыровненное изображение упорядоченного стека определяется в качестве выровненного изображения r без выравнивающего преобразования: r=с. Следовательно, это изображение выбирается в качестве исходной точки для последовательного выравнивания изображений упорядоченного стека. Несмотря на то, что на этапе S10 из Фиг.2 изображение с порядковым номером 0 выбрано в качестве исходного значения, способ не ограничивается этой исходной позицией. Может быть выбрана любая позиция в упорядоченном стеке изображений, например, позиция в середине стека. Кроме того, начальная позиция может быть определена так, чтобы в качестве исходной точки выбиралось изображение, в котором ожидается наличие наименьшей величины рассогласований вследствие подготовки вручную. Например, это может являться изображением, имеющим наименьшее поперечное сечение, поскольку в нем может ожидаться наименьшая абсолютная величина деформаций. Однако по другим причинам, оно также может являться изображением, покрывающим наибольшую часть разрезанной поверхности.
0
0
1
На этапе S20 затем определяется рассогласование s между выровненным изображением r и изображением c, которое должно быть выровнено следующим. Подходящие способы определения рассогласования s будут обсуждаться ниже.
1
0
0
1
1
i
i
i
i
Затем на этапе s30 изображение c выравнивается с r на основе определенного рассогласования s так, чтобы было выполнено выравнивающее преобразование, которое приводит к c→r. В последующем представление c→r будет использовано для обозначения того, что (прежнее) невыровненное изображение c было преобразовано в выровненное изображение r.
На этапе S35, затем указатель i позиции устанавливается на 0 для установки исходной позиции для рекурсивного способа в соответствии по меньшей мере, с одним вариантом осуществления настоящего изобретения. Подобно вышеприведенному для не рекурсивно выполняемого этапа S10, указатель i позиции также может быть установлен на любое другое подходящее значение. Значение i=0 выбрано исключительно для упрощения последующего объяснения. Не рекурсивно выполняемые этапы S10 к S35 являются лишь произвольными для способа в соответствии, по меньшей мере, с одним вариантом осуществления.
i
i
i+2
i+1
i+1
i+2
Теперь будут разъяснены рекурсивно выполняемые этапы способа последовательного выравнивания упорядоченного стека изображений. На этапе S40 определяется рассогласование s между выровненным изображением rи невыровненным изображением, которое должно быть выровнено следующим c, и рассогласование sмежду выровненным изображением rи невыровненным изображением, которое должно быть выровнено следующим c.
i
i+1
i
i+1
На следующем этапе S50 соответствующие величины рассогласований f(s) и f(s) определяются для рассогласований s и s соответственно. Определение величины рассогласования означает, что величина f(s) получается из рассогласования s так, чтобы величина f(s) могла быть использована для сравнения. В самом простом случае, величина f(s) вычисляется как абсолютная величина рассогласования s. Если рассогласование s представлено в виде вектора, то величина f(s), альтернативно, может быть вычислена как сумма абсолютных значений компонентов вектора (которая является такой же, что и вычисление суммированного абсолютного расхождения (сокращенно SAD) в связи с тем, что рассогласование s уже является вектором расхождения), или как среднеквадратическая ошибка (MSE) числовых значений компонентов вектора.
i
i+1
i
i+1
i
i+2
i
ref
i
i+1
i+1
i+2
i+1
ref
На этапе S70 затем величины рассогласований f(s) и f(s), определенные на этапе S50, сравниваются друг с другом. В случае, когда f(s) меньше, чем f(s), выровненное изображение r является изображением, с которым изображение должно сравниваться следующим c, и имеет наименьшую величину рассогласования, так чтобы выровненное изображение r было выбрано в качестве опорного изображения r на этапе S74. В случае, когда f(s) больше или равно f(s), выровненное изображение rявляется изображением, с которым изображение должно сравниваться следующим c, и имеет наименьшую величину рассогласования, так что выровненное изображение rбудет выбрано в качестве опорного изображения r на этапе S76.
ref
i+2
ref
i+2
i+2
i+2
i+2
i
ref
i+1
ref
После выбора r на этапе S74 или на этапе S76, на этапе S80 изображение, которое должно быть выровнено следующим c, выравнивается с r, включая выравнивающее преобразование cв rтак, чтобы cr. Это выравнивающее преобразование выполняется на основе определенного рассогласования s (если r было выбрано на этапе S74) или определенного рассогласования s(если r было выбрано на этапе S76). После преобразования выравнивания на этапе S80, на этапе S90 проверяется, полностью ли выровнен упорядоченный стек изображений, то есть не осталось ли какого-либо невыровненного изображения c. Если стек еще полностью не выровнен, то все еще существуют изображения, которые должны быть выровнены в стеке, то на этапе S95 указатель позиции i увеличивается на один, а затем выполняется следующая рекурсия (или повторение) выполнения этапов с S40 по S90 для выравнивания следующего изображения. Если на этапе S90 определено, что стек был полностью выровнен, то способ выравнивания заканчивается и дополнительная рекурсия выполняться не будет.
i
i+1
По меньшей мере, в одном варианте осуществления настоящего изобретения соответствующие рассогласования s, sопределяются посредством оценки движения так, чтобы каждое рассогласование описывало область оценочного смещения. Например, область оценочного смещения может содержать, по меньшей мере, один вектор смещения, который описывает, как перемещать пиксели в изображении, которое должно быть выровнено, для выравнивания этого изображения до выбранного опорного изображения. Вектор смещения может описывать все возможные рассогласования, такие как линейное перемещение, вращение, масштабирование и растяжение. Такой вектор смещения также называется вектором движения.
Для выполнения оценки движения для получения векторов смещения или векторов движения, было предложено несколько алгоритмов. Оценка движения может пониматься как проблема оптимизации: иногда комплексная, но обычно простая функция критериев должна быть минимизирована или максимизирована для обнаружения выходного вектора движения. Существуют способы перебора, которые просто пробуют все векторы-кандидаты в предварительно определенном диапазоне, чтобы гарантировать получение глобального оптимума функции критерия. Также существуют эффективные подходы, которые проверяют исключительно наиболее вероятные векторы движения. Эта вероятность обычно определяется посредством пространственной или временной близости, и, следовательно, временные и пространственные векторы прогнозирования могут применяться в эффективных алгоритмах оценки движения. Это может быть выполнено посредством алгоритма трехмерного рекурсивного поиска с использованием поблочного сравнения, как описано в документе Джерарда де Хаана с соавторами "Оценка истинного движения при помощи трехмерно-рекурсивного поиска с использованием поблочного сравнения транзакции IEEE на схемах и системах видеотехники, глава 3, номер 5, октябрь 1993 года. Этот документ полностью включен в состав настоящего документа посредством ссылки. Этот алгоритм разделяет кадр на блоки, например, по 8×8 пикселов и пытается идентифицировать позицию этого блока в следующем кадре. Сравнение этих позиций позволяет присваивать вектор движения каждому блоку пикселов, который содержит отношение замены пикселов блока и время между двумя кадрами. Трехмерный рекурсивный поиск является основанным на блоках алгоритмом оценки движения, использующим небольшое количество кандидатов MV (MV = вектор движения), полученных при помощи пространственно-временного прогнозирования. Алгоритм трехмерного рекурсивного поиска предполагает, что блоки меньше, чем объекты, с тем, чтобы MV из соседнего блока являлся хорошей оценкой для MV-кандидата текущего блока. Блоки обрабатываются в определенном порядке, например слева направо и сверху вниз, так, чтобы некоторые соседние блоки, которые уже были оценены для MV, могли предоставить пространственные MV-кандидаты для текущего блока, в то время как другие блоки, которые не были обработаны, получают MV-кандидата из опорного блока для предоставления временного MV для текущего блока. Для каждого MV-кандидата вычисляется ошибка оценки движения. Вероятный вектор с самой малой ошибкой оценки движения выбирается в качестве выходного вектора движения для этого блока. В алгоритме используется нормальный порядок развертки растра для прохождения через блоки. По меньшей мере, в одном из вариантов осуществления настоящего изобретения используется такой алгоритм поблочного сравнения для получения соответствующих областей смещения. Предпочтительно алгоритм трехмерного рекурсивного поблочного сравнения используется, по меньшей мере, в одном варианте осуществления настоящего изобретения в качестве алгоритма поблочного сравнения. Для малозатратной производительности в реальном времени изобретатель предлагает использовать быстрый рекурсивный блок оценки движения, который обеспечивает пространственно-временные последовательные области смещения, которые используются для выравнивания изображений в стеке. Дополнительные фундаментальные способы определения вектора движения, которые могут быть использованы, по меньшей мере, для одного варианта осуществления настоящего изобретения, описываются в Патентах США Номер 5,072,293 и US2008/0144716A1, каждый из которых включен в состав настоящего документа посредством ссылки.
i
i+i
i
i+1
По меньшей мере, в одном варианте осуществления настоящего изобретения, соответствующие величины рассогласований f(s) вычисляются в контексте соответствующей ошибки сравнения, например, f(s), f(s), f(m), f(m), которая вычисляется на основе предварительно определенного критерия соответствия f. Такой критерий соответствия f, который может быть просто определен, является суммированным абсолютным расхождением(SAD):
где C является исследуемым вектором-кандидатом, вектор X указывает позицию блока B(X), F(x,n) является сигналом яркости, а n является номером изображения или области. Вектор движения, который влечет за собой вывод - по одному вектору на блок - является вектором-кандидатом, который дает самое низкое значение SAD. В качестве альтернативы SAD, в качестве критерия сравнения может быть применена среднеквадратическая ошибка (MSE) посредством возведения в квадрат абсолютных расхождений, а затем их сложения. Подобным образом в качестве критерия f сравнения могут быть применены моменты третьего порядка для достижения выравнивания с выбранным опорным изображением. Параметры t преобразования могут быть получены из определенного рассогласования между невыровненным изображением и выбранным опорным изображением и, в частности, из области смещения, вектора смещения или вектора движения, которые описывают определенное рассогласование. Затратное в вычислительном отношении преобразование выполняется лишь единожды для каждого изображения, которое должно быть выровнено, тогда как незатратное в вычислительном отношении вычисление соответствующих ошибок сравнения выполняется неоднократно для одного изображения, которое должно быть выровнено.
Изображения, которые будут сравниваться, должны находиться в совместимом пространстве сигналов. Однако это не так, если изображения в стеке окрашены различными красителями (например, гематоксилин и эозин (H&E) и иммуногистохимией (IHC)). Посредством преобразования, по меньшей мере, одного из изображений в пространство сигналов других изображений или в совместимое пространство сигналов до минимизации рассогласования или ошибки сравнения, возможно сохранить или получить простой критерий сравнения.
Затем в соответствии, по меньшей мере, с одним вариантом осуществления, невыровненное изображение, которое должно быть выровнено, может быть удалено из упорядоченного стека изображений, если все величины определенных рассогласований s будут превышать заданное пороговое значение. Заданное пороговое значение может являться фиксированным значением или может быть определено адаптивно, например, на основе ранее определенных величин рассогласований. Удаленное изображение может быть заменено посредством интерполированного изображения, сформированного посредством интерполяции выровненных изображений. В качестве входных данных для интерполяции могут быть выбраны выровненные изображения, расположенные в упорядоченном стеке следом за рассогласованным изображением. Кроме того, выровненное изображение не будет использовано для дальнейших этапов определения рассогласования, если величина его рассогласования на текущем этапе определения рассогласования будет выше заданного порогового значения, в то время как оставшиеся величины рассогласований будут ниже заданного порогового значения. Заданное пороговое значение может являться фиксированным значением или может быть определено адаптивно, например, на основе ранее определенных величин рассогласований.
В соответствии, по меньшей мере, с одним вариантом осуществления, соответствующие рассогласования определяются посредством распознавания объектов. По сравнению с алгоритмами поблочного сравнения для сравнения пикселов, для распознавания объекта требуются большие вычислительные затраты. С другой стороны, распознавание объектов работает на дескрипторах более высоко уровня, которые являются более надежными, чем, например, SAD. Однако не все способы распознавания объектов подходят в качестве основы для выравнивания упорядоченного стека изображений. Подходящий способ распознавания объектов является распознаванием объектов из так называемых локальных масштабно-инвариантных признаков. Одна разновидность этого способа называется SHIFT (для масштабно-инвариантного преобразования признаков), и он был представлен в статье "Распознавание объектов из локальных масштабно-инвариантных признаков" Дэвид Г. Лоу, Международная конференция по машинному распознаванию образов, 1999 год, страницы 1150-1157. Очень глубокое описание способа SIFT распознавания объектов описано в статье "Отличительные признаки изображения из масштабно-инвариантных ключевых точек" Дэвид Г. Lowe, Международный журнал по машинному распознаванию образов, 2004 год, страницы 91-110. Оба документа включены в состав настоящего документа посредством ссылки. Способ SIFT преобразует каждую локальную часть изображения в координаты, которые не зависят от масштаба и ориентации изображения. Локальные инвариантные признаки позволяют эффективно сравнивать маленькие части беспорядочных изображений при произвольных вращениях, масштабировании, изменении яркости и контраста и других преобразований. Идея состоит в разбиении изображения на много небольших перекрывающихся частей различного переменного размера, каждая из которых описывается способом, инвариантным к возможным преобразованиям. Затем может быть выполнено отдельное сравнение каждой части, и сравниваемые части проверяются на предмет последовательности. Для сравнения и распознавания изображений сначала извлекаются признаки SIFT из ряда опорных изображений и сохраняются в базе данных. Новое изображение сравнивается посредством отдельного сравнения каждого признака из нового изображения для этой предыдущей базы данных и нахождения кандидата, соответствующего признакам, расположенным в Евклидовом расстоянии их векторов признаков.
В соответствии, по меньшей мере, с одним вариантом осуществления, соответствующие рассогласования определяются исключительно посредством вышеупомянутого распознавания объектов, если неоднократно возникала относительно большая величина рассогласования. В противном случае, если величина рассогласования, в основном, остается ниже заданного порогового значения, то соответствующие рассогласования определяются посредством быстрой и простой в вычислительном отношении оценки движения. Заданное пороговое значение может являться постоянной величиной или может быть определено адаптивно, например, на основе ранее определенных величин рассогласования.
i
i+2
i
i
i+1
i+2
i+1
i+1
i
i+1
i
i+1
i
i+1
i
i
i+1
i+1
i
i+1
i
i+1
i
i+1
ref
ref
ref
i+2
ref
ref
i+2
i+2
i+2
i+2
i+2
i+2
i+3
Фиг.3 иллюстрирует устройство для выравнивания упорядоченного стека изображений разрезанного образца в соответствии, по меньшей мере, с вариантом осуществления настоящего изобретения. Устройство 100 содержит блок 10 определения, блок 20 выбора и блок 30 выравнивания. Блок 10 определения содержит два блока 11 и 12 оценки движения. Блок 11 оценки движения принимает на входе выровненное изображение r и изображение, которое должно быть выровнено следующим c. Блок 11 оценки движения приспособлен для определения на основе этих входных данных рассогласования s и вектора m смещения и их вывода. Подобным образом блок 12 оценки движения принимает на входе выровненное изображение rи изображение, которое должно быть выровнено следующим c, и приспособлен для определения на основе этих входных данных рассогласования sи вектора mсмещения и их вывода. Выходные рассогласования s и sподаются на блок 20 выбора. Выходные рассогласования s и sтакже могут быть выведены в виде соответствующих векторов m и mсмещения соответственно для подачи их на блок 20 выбора (в этом случае s=m и s=m). Блок 20 выбора применяет критерий сравнения, например SAD, MSE или третьего порядка, к рассогласованиям s и s, принятым из блоков 11 и 12 оценки движения. Применение критерия сравнения влечет за собой вычисление ошибок f сравнения f(s) и f(s). Затем блок 20 выбора определяет минимум этих ошибок сравнения и выбирает из векторов m и mсмещения, выведенных из блоков 11 и 12 оценки движения, вектор смещения, имеющий наименьшую ошибку сравнения, в качестве опорного вектора m смещения. Посредством этого опорного вектора m смещения, неявно выбирается опорное изображение r, с которым должно быть выровнено невыровненное изображение c. Затем выбранный опорный вектор m смещения подается из соответствующего блока оценки движения на блок 30 выравнивания. В блоке 30 выравнивания, опорный вектор m смещения преобразуется в конвертере 32 в параметры t преобразования для преобразования невыровненного изображения c. В блоке 30 выравнивания параметры t преобразования выводятся из конвертера 32 на преобразователь 34. Преобразователь 34 использует параметры t преобразования для преобразования невыровненного изображения cв выровненное изображение rтак, чтобы c→r. После завершения одного повторения выравнивания для c, может быть начато следующее повторение для cпри увеличении на 1 счетчика i позиций.
Несмотря на то, что все вышеописанные варианты осуществления основаны на определении двух рассогласований для выравнивания невыровненного изображения, настоящее изобретение не ограничивается определением исключительно двух рассогласований. Для каждого этапа выравнивания может быть определено более двух рассогласований. Опорное изображение может быть выбрано более чем из двух выровненных изображений.
Несмотря на то, что вышеописанные варианты осуществления основаны на определении, по меньшей мере, двух рассогласований между невыровненным изображением и, по меньшей мере, двумя изображениями, непосредственно предшествующими невыровненному изображению, настоящее изобретение не ограничено выбором опорного изображения из выровненных изображений, смежных друг с другом и смежных с невыровненным изображением.
Несмотря на то, что в вышеописанных примерах упорядоченный стек изображений содержит только четыре изображения для объяснения, размер стека этими размерами не ограничен. Упорядоченный стек изображений может содержать любое количество изображений. В пределах концепции изобретения, “блок определения”, “блок выбора”, “блок выравнивания”, “блок оценки движения” должны пониматься широк и должны содержать, например, любой элемент аппаратных средств (такой блок определения, блок выбора, блок выравнивания, блок оценки движения), любую схему или часть схемы, разработанную для выполнения определения, выбора, выравнивания, оценки движения описанным способом, а также любой элемент программных средств (компьютерную программу, или подпрограмму, или ряд компьютерных программ, или программный(е) код(ы)), разработанный или запрограммированный для выполнения определения, выбора, выравнивания, оценки движения, а также любую комбинацию элементов аппаратных средств и программных средств, действующих, по существу, отдельно или в комбинации, без ограничения нижеприведенными иллюстративными вариантами осуществления.
Специалисты в данной области техники поймут, что настоящее изобретение не ограничено тем, что, в частности, было изображено и описано выше. Изобретение заключается во всех без исключения новых отличительных признаках и в каждой комбинации отличительных признаков. Ссылочные позиции в формуле изобретения не ограничивают их объем охраны. Использование глагола “содержать” и его спряжений не исключает наличия элементов, отличных от заявленных в формуле изобретения. Использование признака единственного числа перед элементом не исключает наличия множества таких элементов.
Настоящее изобретение было описано в контексте конкретных вариантов осуществления, которые являются иллюстративными для изобретения и не должны рассматриваться как огранивающие. Изобретение может быть реализовано в аппаратных средствах, программируемом оборудовании, или программных средствах, или в их комбинации. Другие варианты осуществления находятся в пределах объема следующей формулы изобретения.
СПИСОК ССЫЛОЧНЫХ ОБОЗНАЧЕНИЙ
10 блок определения
11 блок оценки движения
12 блок оценки движения
20 блок выбора
30 блоков выравнивания
32 конвертер
34 преобразователь
100 устройство