СПОСОБ АЛФАВИТНОГО ПРЕДСТАВЛЕНИЯ ИЗОБРАЖЕНИЯ Российский патент 2014 года по МПК G06T9/00 G06T3/00 G06K9/36 H04N19/60 

Область техники

Изобретение относится к области обработки цифровых изображений.

Способ предназначен для прямого представления (например, непосредственно с сенсора) входного изображения в семантических единицах типа:

- области постоянной яркости;

- следы прямых и/или границы контуров;

- хаотичные скопления пикселов или шумы.

Такое представление изображения, далее Fas-форма, позволяет эффективно реализовывать процедуры обработки изображения по всем их классам (в скобках указаны наиболее представительные подклассы):

- анализ (распознавание, фильтрация),

- преобразование (сжатие, редакция),

- синтез (анимация, улучшение качества),

- передача по каналам связи с управлением восстановления сигнала на приемнике.

Эффективность определяется тремя параметрами:

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

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

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

Способ имеет аппаратную и программную реализации.

Уровень техники. Аналоги и их недостатки

В работах [1, стр.114] и в [2, стр.153] показана проблема создания общего алфавита для растровых изображений, решение которой не достижимо в силу конструктивного ограничения по длине алфавита. Действительно, в этом случае, размер алфавита содержит, пусть для цветных изображений, до 2²⁴ или 16.78 млн символов, что неперечислимо. В работе [3, стр.162] указан алфавит, состоящий из 48 букв и ориентированный на портретный распознаватель. Его недостаток: входное изображение - монохромное; отсутствие в алфавите букв, формирующих шум; нет управления порогом неопределенности Гейзенберга, т.е. фрагмента плоскости к точке зоны интереса

Прототипы

Создание абсолютного алфавита представления цифрового изображения на сегодня проблематично в силу его растрового представления, т.е. на нем невозможно создать такой алфавит [1,стр.114]. Однако в этом плане есть наработки, ориентированные под специализированные системы [3], в этом случае речь идет об усеченных алфавитах.

Уровень техники

Изобретение относится к области обработки изображений. Его применение - представления изображения в смысловых единицах в темпе сканирования, т.е. без применения средств предобработки, в форме алфавита с соответствующей схемой словообразования. Такой уровень разработки позволяет отказаться от понятия "Пиксел", т.е. изъять из процедур обработки изображения все локальные операторы и перевести их в глобальные.

Описание изобретения

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

Шаг 1. Преобразование входного, например, растрового изображения в МЦР форму.

Шаг 2. Выполнение компонентного анализа изображения на монохром, полутон, цвет.

Шаг 3. Разложение МЦР формы в код Грея.

Шаг 4. Получение алфавита для каждой плоскости в правилах Гейзенберга.

Шаг 1. Получение МЦР формы. Способ преобразования и обработки изображения на основе многоцентричной развертки (МЦР), построенной по правилам кривой, заполняющей плоскость (КЗП), т.е. установкой начала и направления рекурсии, определяется тем, что начальная ячейка МЦР (начало рекурсии) представляет собой дискретный квадрат, состоящий из девяти клеток (3×3=9), имеющий свой центр и свои четыре грани (стороны); развертка начальной ячейки МЦР (направление рекурсии) стартует от центра к краю квадрата и далее с обходом остальных ячеек по кругу (таким образом возможны 16 путей обхода из учета 8 граничных клеток и двух вариантов обхода - по и против часовой стрелки).

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

Такую конструкцию назовем фасетом или pFas, где р - шаг рекурсии, при р=1 имеем описанную выше начальную ячейку (3×3=9).

Для формирования направления рекурсии будем различать четыре типа обхода (фиг.2), необходимые для описания 2Fas:

- описанный ранее обход w1 как начальный (1Fas1);

- обход w2 как зеркальный от 1Fas1 в левую сторону (1Fas2),

- обход w3 как зеркальный от 1Fas2 в верхнюю сторону (1Fas3),

- обход w4 как зеркальный от 1Fas3 в правую сторону.

Для получения рекурсий МЦР построена 2Fas (фиг.3) (р=2, со стороной 9 клеток, т.е. 9×9=81), отвечающая за направление рекурсий, где исходной служит начальная 1Fas, которая (на основе вышеуказанных вращений w) имеет их последовательность с начальным движением в квадрат влево от 1Fas и далее по часовой вокруг 1Fas или путь: w1 w2 w3 w4 w3 w2 w3 w4 w3. Собственно это и порождает направление рекурсий.

Каждая последующая рекурсия pFas (р>2), строится на основе 1Fas и 2Fas. Пример для 3Fas дан на фиг.4.

Включение рекурсий МЦР на основе 1Fas и 2Fas (р>2) позволяет плоскость представить в координатах вращения (w), носителем которых является pFas, причем точкой этой плоскости, далее $$Q_{xy}^p$$ , является квадрат со стороной 3^p, где р=0…N, где N, наперед заданный этот квадрат, в который вложен габарит исходного изображения. При р=0 (OFas) или точка $$Q_{xy}^0$$ вырождается в пиксел, при р>0, на который действует МЦР плоскость разбивается на $$Q_{xy}^{p-1}$$ независимых точек (квадратов). Параметры ху для Q - это его центр на плоскости изображения.

Таким образом МЦР создает 6-координатное пространство точки Q:

- две координаты декартового измерения (х, у координаты),

- координата измерения вращения (w),

- координата измерения вложенности точки в дерево Q,

- координата измерения размера граней фасета или pFas,

- координата измерения номера хранения Q^p _xy в памяти вычислителя или F¹¹.

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

Общим для 6 координат является отображение декартовой плоскости в память, при взаимно однозначном отображении точки $$Q_{xy}^p$$ в F^p или формально: $$Q_{xy}^p\langle \dots \rangle F^p$$ , при р=0, Q_xy->Р_ху; где Р_ху пиксел с декартовыми координатами, а F^p - отрезок в целых числах как f_a…f_a+p, для $$Q_{xy}^p$$ в памяти вычислителя, f_a - номер $$Q_{xy}^p$$ или его номер центра на плоскости.

Важным преимуществом представляемого способа является то, что в изображении, представленном МЦР, выделение площади сегмента изображения по заданному критерию релевантности (т.е. по информационной ценности для наблюдателя) в плоскости изображения (в т.ч. для выделения линий прямых, областей постоянной яркости или цветности, хаотичных скоплений пикселей и др.) выполняют в форме управляемых вложений pFas по параметру р=1…10 в точку зоны интереса релеванта, с точностью р, с помощью представления точки интереса в изображении на основании таблиц преобразования, получаемых по п.1 (1Fas или 2Fas или pFas). И все это не требует применения уравнений местонахождения точки на физическом уровне представления изображения через его габариты.

Тем самым выполняют прямой доступ (в т.ч. несколькими процессорами независимо) к точке интереса или группам точек интереса изображения по схеме 9^p, где каждый процессор отрабатывает свое «дерево» из вышеуказанного «леса», при этом доступ выполняется минимальной шириной захвата пикселей 9¹, или, в зависимости от параметра р=1…10. При этом, процессоры однородны и их количество зависит от габарита входного изображения.

В представляемом способе эффективно определяют 8-связную окрестность любой точки зоны интереса на изображении, путем использования таблиц преобразований (без средств маскирования): эта 8-связная окрестность определяется для $$Q_{xy}^p$$ . При р=0 она превращается в точку, а при р>0 она превращается в окрестность квадрата со стороной 3^p. Причем окрестность представлена гранями квадрата на основе таблиц преобразования 1Fas и 2Fas, без учета габаритов изображения.

Представляемый способ, по умолчанию, также выполняет сжатие изображения без потерь. Путь (трек) развертки задан от его (квадрата) центра по правилам кривых заполняющих плоскость (КЗП); при р=1 (форма КЗП), изображение, независимо от своих габаритов (w,h), сегментируется на 9 квадратов, каждый из которых сегментируется снова на 9 квадратов или р=2 (направление КЗП). Остальные КЗП (р>2) строятся рекурсивно на длине р=0…10. При р=10 габарит изображения или w,h равны по 59049 пикселов. Формально, многоцентричная развертка (МЦР) выполняет взаимно однозначное отображение xi, yj в rj, где пара xi, yj - декартовые координаты пиксела или Рху, rj - номер из натурального ряда чисел отрезком 1…59049×59049.

Шаг 2. Компонентный анализ изображения на монохром, полутон, цвет. Считаем, что любое изображение, пусть даже цветное, состоит из областей, имеющих различные компоненты. Задача этого шага - выявить и зафиксировать эти области точкой $$Q_{xy}^p$$ . Анализ ведется для совокупности пикселов, лежащих на pFas. Допускается ее квантование с наперед заданной точностью.

Шаг 3. Разложение МЦР формы в код Грея.

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

Пусть А - восьмибитное целое число, представляющее собой субпиксел изображения (компонента R, G или В цветного изображения, или значение яркости Y для полутонового изображения). Определим взаимно однозначное отображение В=В(А) следующим образом:

где a_i(b_i) - i-й бит исходного (выходного) числа, причем первый бит считается самым старшим, восьмой - самым младшим;

знак «плюс в кружке» означает операцию сложения по модулю 2, черта над числом - операцию битовой инверсии.

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

$$a_1=\overline{b_1};a_2=\overline{b_1}\oplus \overline{b_2};a_1=\overline{b_1}\oplus \dots \oplus \overline{b_1},\text{ i}\in \text{3}\text{,8}$$

Результаты прямого преобразования В=В(А) (в код Грея) и обратного преобразования А=А(В) (из кодов Грея) для всевозможных восьмибитовых чисел декларируются в виде двух 256-элементных таблиц, которые используются для преобразования чисел в программе.

Далее, изображение, представленное МЦР, раскладывают на плоскости с применением кода Грея, получая одну плоскость для монохромных, восемь плоскостей для полутоновых и от 24 плоскостей для цветных изображений; в результате каждая плоскость становится представимой алфавитом, буква которого представляет собой варианты заполнения квадрата 3×3; таким образом каждая буква становится заданной по правилам Г. Фреге, когда денотат буквы есть ее иконика, концепт буквы есть ее символ, знак буквы есть ее число или номер; созданный алфавит семантически представлен тремя следующими подмножествами: компакты (носители постоянных яркостей), регулярности (следы прямых), хаотичные скопления пикселей разной дисперсии.

Шаг 4. Получение алфавита для каждой плоскости в правилах Гейзенберга.

Отметим, что элементы алфавита и их размещение на конкретных областях формируют элемент покрытия в амплитудно-пространственной плоскости, называемой также ячейкой Гейзенберга, которая показывает концентрацию базисных букв алфавита в $$Q_{xy}^p$$ точке. Обычно, ячейку Гейзенберга задают в частотно-временной плоскости [4, стр.566]. Однако, в силу особенностей устройства средств зрительного восприятия изображения наблюдателем типа "Человек", выбирают амплитудное растрирование. Стандартная схема этого эксперимента: "Большое вижу на расстоянии.", т.е. частотная компонента этой фабулы не приемлема, просто у нее нет средств сходимости по самоподобию. Дальнейшим развитием является преобразование, где каждая плоскость изображения строится на алфавите, который задается для квадратов МЦР со значением р=1-9 путем построения вектора символов, имеющего 9^p букв, т.е. длина алфавита - 512 букв, на основе которого, в темпе сканирования, формируют геометрические базисы в правилах сходимости для снижения неопределенности Гейзенберга, но в отличие от существующих алгоритмов, реализующих это правило, пусть пирамидой Маллата (пространственно-частотное поле), здесь используется пара: пространство - алфавит как суть амплитуд с разной метрикой сходимости, при этом пространственная (плоскостная) пирамида (pFas) является ведомой, а пирамида амплитуд (pJ шкала) - ведущей, причем сходимость по pFas (плоскость) имеет основание 9, а сходимость по pJ имеет основание 4, что обеспечивает прямую навигацию процессора к семантическим единицам (релевантам). По правилу Гейзенберга развитие (расширение) каждой точки $$Q_{xy}^p$$ плоскости изображения строится параметром pJ (значения яркостей составляющей под реальное изображение на длине 512), с выявлением доминирующей релеванты над алфавитом по квадрату 9^p с последующей поверкой ее содержимого по критериям избыточности для $$Q_{xy}^p$$ (изолированная прямая, дуга, контурная линия, постоянная яркость, хаос и т.п.), путем количественного расчета элементов алфавита на квадрате 9^p. При этом сжатие изображения выполняется за счет ликвидации межплоскостной избыточности между i-й и i+1, i-1-й плоскостями путем создания шкалы их взаимного подобия по фасетной мере для полутоновых и цветных изображений. На базе pFas реализуется беспороговая схема выделения контуров на монохромных, полутоновых и цветных изображениях путем сравнения pFas между плоскостями и между компонентами (RGB) по оценке согласно шкале Левенштейна [5, стр.44]. Полный алфавит для любых цифровых изображений дан (фиг.5).

Краткое описание чертежей

На Фиг.1 показана начальная ячейка МЦР, названная 1Fas, которая представляет собой дискретный квадрат, состоящий из девяти клеток (3×3=9), имеющий свой центр и свои четыре грани (стороны); развертка МЦР начальной ячейки стартует от центра с обходом влево от центра и далее по кругу по часовой стрелке.

На Фиг.2 показаны четыре типа обхода квадрата, состоящего из девяти клеток (3×3=9): обход w1 описанный как начальный (1Fas1); обход w2 как зеркальный от 1Fas1 в левую сторону (1Fas2), обход w3 как зеркальный от 1Fas2 в верхнюю сторону (1Fas3), обход w4 как зеркальный от 1Fas3 в правую сторону; эти типы обхода необходимы для получения направления рекурсии МЦР для 2Fas.

На Фиг.3 показано направление рекурсии МЦР для 2Fas (р=2, со стороной 9 клеток, 9×9=81), где исходной служит начальная 1Fas, на основе вышеуказанных вращений w в последовательности с движением в квадрат влево от 1Fas и далее по часовой вокруг 1Fas: w1 w2 w3 w4 w3 w2 w3 w4 w3.

На Фиг.4 показана рекурсия МЦР для 3Fas (p=3, со стороной 27 клеток).

На Фиг.5 показан полный алфавит, построенный согласно заданной МЦР.

Промышленная применимость

Представление цифрового изображения алфавитом, далее Fas форма позволяет:

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

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

- реализовать отношение толерантности к существующим алгоритмам, особенно для частотных представлений изображения (ДКП, ДВП);

- выполнить сжатие изображения (с потерями или без) путем его сегментации на релеванты (области постоянной яркости, линии и хаотичные скопления) с последующей передачи последнего релеванта, пусть под одномерный ДКП;

Способ ориентирован на аппаратную и программную реализации.

Источники информации

1. Д.Сэломон. Сжатие данных, изображений и звука. -М.: Техносфера, 2004.

2. Р.У.Быков, Р.Фрайер и др. Цифровое преобразование изображений М.: "Горячая линия - Телеком", 2003.

3. В.С.Файн. Опознавание изображений. -М.: "Наука", 1970.

4. Р.Гонсалес, Р.Вудс.Цифровая обработка изображений. -М.: Техносфера, 2006.

5. Т.Кохонен. Самоорганизующиеся карты.- М.: БИНОМ. Лаборатория знаний, 2008.

Изобретение относится к вычислительной технике, а именно к области обработки изображений. Техническим результатом является повышение эффективности кодирования изображений. Способ алфавитного представления изображений включает в себя этап первичного преобразования входного изображения в формат многоцентричной развертки (МЦР), построенной по правилам кривой, заполняющей плоскость (КЗП). При этом начальная ячейка МЦР представляет собой дискретный квадрат, состоящий из девяти клеток (3×3=9), имеющий свой центр и свои четыре грани (стороны). Развертку начальной ячейки МЦР выполняют от центра к краю квадрата, с обходом остальных ячеек по кругу. Приоритетным для сканирования и визуализации изображений является путь с направлением обхода влево от центра квадрата и далее по кругу, по часовой стрелке. 2 з.п. ф-лы, 5 ил.

1. Способ алфавитного представления изображений, отличающийся тем, что входное изображение первично преобразуют в формат многоцентричной развертки (МЦР), построенной по правилам кривой, заполняющей плоскость (КЗП), т.е. установкой начала и направления рекурсии, где начальная ячейка МЦР представляет собой дискретный квадрат, состоящий из девяти клеток (3×3=9), имеющий свой центр и свои четыре грани (стороны); развертку начальной ячейки МЦР выполняют от центра к краю квадрата и далее с обходом остальных ячеек по кругу, при этом приоритетным для сканирования и визуализации изображений является путь с направлением обхода влево от центра квадрата и далее по кругу, по часовой стрелке; обозначают такую конструкцию фасетом pFas, где р - шаг рекурсии, при р=1 получают описанную выше начальную ячейку (3×3=9); для построения дальнейших направлений рекурсий различают четыре типа обхода: описанный ранее обход w1 как начальный (1Fas1), обход w2 как зеркальный от 1Fas1 в левую сторону (1Fas2), обход w3 как зеркальный от 1Fas2 в верхнюю сторону (1Fas3), обход w4 как зеркальный от 1Fas3 в правую сторону; для получения направлений рекурсий МЦР, т.е. 2Fas (p=2, со стороной 9 клеток, 9×9=81), где началом является 1Fas (на основе вышеуказанных вращений w), выполняют обход в последовательности с начальным движением в квадрат влево от 1Fas и далее по часовой вокруг 1Fas: w1 w2 w3 w4 w3 w2 w3 w4 w3; все последующие МЦР построения рекурсий pFas (р>2) строят на основе 1Fas и 2Fas; далее, изображение, представленное МЦР раскладывают на плоскости с применением кода Грея, получая одну плоскость для монохромных, восемь плоскостей для полутоновых и 24 плоскости для цветных изображений; в результате каждая плоскость становится представленной одномерно алфавитом; алфавит организуют как набор вариантов заполнения квадрата 3×3; таким образом, каждую букву образуют по правилам Г.Фреге, когда денотат буквы есть ее иконика, концепт буквы есть ее символ, знак буквы есть ее число или номер; созданный алфавит семантически представляют тремя следующими подмножествами: компакты - носители постоянных яркостей, регулярности - следы прямых, хаотичности - скопления пикселей разной дисперсии.

2. Способ по п.1, отличающийся тем, что каждая точка $$Q_{xy}^p$$ плоскости изображения строют параметром pJ (значения яркостной составляющей под реальное изображение на длине 512), с выявлением доминирующей релеванты над алфавитом по квадрату 9^p с последующей поверкой ее содержимого по критериям избыточности для $$Q_{xy}^p$$ (изолированная прямая, дуга, контурная линия, постоянная яркость, хаос) путем количественного расчета элементов алфавита на квадрате 9^p.

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