СПОСОБ АЛФАВИТНОГО ПРЕДСТАВЛЕНИЯ ИЗОБРАЖЕНИЯ
METHOD FOR ALPHABETICAL IMAGE REPRESENTATION

Область техники
Изобретение относится к области обработки цифровых изображений.
Способ предназначен для прямого представления (например, непосредственно с сенсора) входного изображения в семантических единицах типа:
- области постоянной яркости;
- следы прямых и/или границы контуров;
- хаотичные скопления пикселов или шумы.
Такое представление изображения, далее Fas-форма, позволяет эффективно реализовывать процедуры обработки изображения по всем их классам (в скобках указаны наиболее представительные подклассы):
- анализ (распознавание, фильтрация),
- преобразование (сжатие, редакция),
- синтез (анимация, улучшение качества),
- передача по каналам связи с управлением восстановления сигнала на приемнике.
Эффективность определяется тремя параметрами:
- быстродействие за счет ликвидации предварительных процедур,
- простота аппаратной реализации за счет создания однородных и параллельных схем процессирования зон изображения с управляемой схемой понижения неопределенности ячейки Гейзенберга для пары "Плоскость - алфавит как суть амплитуд",
- создание меры семантических подобий как в плоскости изображения, так и между несколькими изображениями за счет выявления и ликвидации избыточностей различных типов (синтактические, геометрические, межплоскостные, межкадровые и т.п.).
Способ имеет аппаратную и программную реализации.
Уровень техники. Аналоги и их недостатки
24
В работах [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.
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mn>0</mn></msubsup></mrow>
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mrow><mi>p</mi><mo>−</mo><mn>1</mn></mrow></msubsup></mrow>
p
Включение рекурсий МЦР на основе 1Fas и 2Fas (р>2) позволяет плоскость представить в координатах вращения (w), носителем которых является pFas, причем точкой этой плоскости, далее
, является квадрат со стороной 3, где р=0…N, где N, наперед заданный этот квадрат, в который вложен габарит исходного изображения. При р=0 (OFas) или точка
вырождается в пиксел, при р>0, на который действует МЦР плоскость разбивается на
независимых точек (квадратов). Параметры ху для Q - это его центр на плоскости изображения.
Таким образом МЦР создает 6-координатное пространство точки Q:
- две координаты декартового измерения (х, у координаты),
- координата измерения вращения (w),
- координата измерения вложенности точки в дерево Q,
- координата измерения размера граней фасета или pFas,
p
11
xy
- координата измерения номера хранения Q  в памяти вычислителя или F.
Причем эти шесть координат измерений могут между собой комбинировать в зависимости от поставленных задач.
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup><mrow><mo>〈</mo><mo>…</mo><mo>〉</mo></mrow><msup><mi>F</mi><mi>p</mi></msup></mrow>
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
p
p
xy
ху
ху
a
a+p
a
Общим для 6 координат является отображение декартовой плоскости в память, при взаимно однозначном отображении точки
в F или формально:
, при р=0, Q->Р; где Р пиксел с декартовыми координатами, а F - отрезок в целых числах как f…f, для
в памяти вычислителя, f - номер
или его номер центра на плоскости.
Важным преимуществом представляемого способа является то, что в изображении, представленном МЦР, выделение площади сегмента изображения по заданному критерию релевантности (т.е. по информационной ценности для наблюдателя) в плоскости изображения (в т.ч. для выделения линий прямых, областей постоянной яркости или цветности, хаотичных скоплений пикселей и др.) выполняют в форме управляемых вложений pFas по параметру р=1…10 в точку зоны интереса релеванта, с точностью р, с помощью представления точки интереса в изображении на основании таблиц преобразования, получаемых по п.1 (1Fas или 2Fas или pFas). И все это не требует применения уравнений местонахождения точки на физическом уровне представления изображения через его габариты.
p
1
Тем самым выполняют прямой доступ (в т.ч. несколькими процессорами независимо) к точке интереса или группам точек интереса изображения по схеме 9, где каждый процессор отрабатывает свое «дерево» из вышеуказанного «леса», при этом доступ выполняется минимальной шириной захвата пикселей 9, или, в зависимости от параметра р=1…10. При этом, процессоры однородны и их количество зависит от габарита входного изображения.
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
p
В представляемом способе эффективно определяют 8-связную окрестность любой точки зоны интереса на изображении, путем использования таблиц преобразований (без средств маскирования): эта 8-связная окрестность определяется для
. При р=0 она превращается в точку, а при р>0 она превращается в окрестность квадрата со стороной 3. Причем окрестность представлена гранями квадрата на основе таблиц преобразования 1Fas и 2Fas, без учета габаритов изображения.
Представляемый способ, по умолчанию, также выполняет сжатие изображения без потерь. Путь (трек) развертки задан от его (квадрата) центра по правилам кривых заполняющих плоскость (КЗП); при р=1 (форма КЗП), изображение, независимо от своих габаритов (w,h), сегментируется на 9 квадратов, каждый из которых сегментируется снова на 9 квадратов или р=2 (направление КЗП). Остальные КЗП (р>2) строятся рекурсивно на длине р=0…10. При р=10 габарит изображения или w,h равны по 59049 пикселов. Формально, многоцентричная развертка (МЦР) выполняет взаимно однозначное отображение xi, yj в rj, где пара xi, yj - декартовые координаты пиксела или Рху, rj - номер из натурального ряда чисел отрезком 1…59049×59049.
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
Шаг 2. Компонентный анализ изображения на монохром, полутон, цвет. Считаем, что любое изображение, пусть даже цветное, состоит из областей, имеющих различные компоненты. Задача этого шага - выявить и зафиксировать эти области точкой
. Анализ ведется для совокупности пикселов, лежащих на pFas. Допускается ее квантование с наперед заданной точностью.
Шаг 3. Разложение МЦР формы в код Грея.
Изображение, представленное МЦР, раскладывают на плоскости в правилах рефлексивного кода Грея. При этом получаем одну плоскость для монохромных, восемь плоскостей для полутоновых и от 24 плоскостей для цветных изображений, в результате каждая плоскость задается алфавитом. Разложение выполняется по следующей схеме:
Пусть А - восьмибитное целое число, представляющее собой субпиксел изображения (компонента R, G или В цветного изображения, или значение яркости Y для полутонового изображения). Определим взаимно однозначное отображение В=В(А) следующим образом:
i
i
где a(b) - i-й бит исходного (выходного) числа, причем первый бит считается самым старшим, восьмой - самым младшим;
знак «плюс в кружке» означает операцию сложения по модулю 2, черта над числом - операцию битовой инверсии.
Данное отображение задает представление числа в коде Грея, получаемого из восьмибитного двоичного рефлексивного кода Грея путем его побитовой инверсии. Обратное отображение А=А(В) определяется следующим образом:
<mrow><msub><mi>a</mi><mn>1</mn></msub><mo>=</mo><mover accent="true"><mrow><msub><mi>b</mi><mn>1</mn></msub></mrow><mo stretchy="true">¯</mo></mover><mo>;</mo><mtext> </mtext><msub><mi>a</mi><mn>2</mn></msub><mo>=</mo><mover accent="true"><mrow><msub><mi>b</mi><mn>1</mn></msub></mrow><mo stretchy="true">¯</mo></mover><mo>⊕</mo><mtext> </mtext><mover accent="true"><mrow><msub><mi>b</mi><mn>2</mn></msub></mrow><mo stretchy="true">¯</mo></mover><mo>;</mo><mtext> </mtext><msub><mi>a</mi><mn>1</mn></msub><mo>=</mo><mover accent="true"><mrow><msub><mi>b</mi><mn>1</mn></msub></mrow><mo stretchy="true">¯</mo></mover><mo>⊕</mo><mtext> </mtext><mo>…</mo><mo>⊕</mo><mover accent="true"><mrow><msub><mi>b</mi><mn>1</mn></msub></mrow><mo stretchy="true">¯</mo></mover><mo>,</mo><mtext> i</mtext><mo>∈</mo><mtext>3</mtext><mtext>,8</mtext></mrow>
Результаты прямого преобразования В=В(А) (в код Грея) и обратного преобразования А=А(В) (из кодов Грея) для всевозможных восьмибитовых чисел декларируются в виде двух 256-элементных таблиц, которые используются для преобразования чисел в программе.
Далее, изображение, представленное МЦР, раскладывают на плоскости с применением кода Грея, получая одну плоскость для монохромных, восемь плоскостей для полутоновых и от 24 плоскостей для цветных изображений; в результате каждая плоскость становится представимой алфавитом, буква которого представляет собой варианты заполнения квадрата 3×3; таким образом каждая буква становится заданной по правилам Г. Фреге, когда денотат буквы есть ее иконика, концепт буквы есть ее символ, знак буквы есть ее число или номер; созданный алфавит семантически представлен тремя следующими подмножествами: компакты (носители постоянных яркостей), регулярности (следы прямых), хаотичные скопления пикселей разной дисперсии.
Шаг 4. Получение алфавита для каждой плоскости в правилах Гейзенберга.
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
<mrow><msubsup><mi>Q</mi><mrow><mi>x</mi><mi>y</mi></mrow><mi>p</mi></msubsup></mrow>
p
p
p
Отметим, что элементы алфавита и их размещение на конкретных областях формируют элемент покрытия в амплитудно-пространственной плоскости, называемой также ячейкой Гейзенберга, которая показывает концентрацию базисных букв алфавита в
точке. Обычно, ячейку Гейзенберга задают в частотно-временной плоскости [4, стр.566]. Однако, в силу особенностей устройства средств зрительного восприятия изображения наблюдателем типа "Человек", выбирают амплитудное растрирование. Стандартная схема этого эксперимента: "Большое вижу на расстоянии.", т.е. частотная компонента этой фабулы не приемлема, просто у нее нет средств сходимости по самоподобию. Дальнейшим развитием является преобразование, где каждая плоскость изображения строится на алфавите, который задается для квадратов МЦР со значением р=1-9 путем построения вектора символов, имеющего 9 букв, т.е. длина алфавита - 512 букв, на основе которого, в темпе сканирования, формируют геометрические базисы в правилах сходимости для снижения неопределенности Гейзенберга, но в отличие от существующих алгоритмов, реализующих это правило, пусть пирамидой Маллата (пространственно-частотное поле), здесь используется пара: пространство - алфавит как суть амплитуд с разной метрикой сходимости, при этом пространственная (плоскостная) пирамида (pFas) является ведомой, а пирамида амплитуд (pJ шкала) - ведущей, причем сходимость по pFas (плоскость) имеет основание 9, а сходимость по pJ имеет основание 4, что обеспечивает прямую навигацию процессора к семантическим единицам (релевантам). По правилу Гейзенберга развитие (расширение) каждой точки
плоскости изображения строится параметром pJ (значения яркостей составляющей под реальное изображение на длине 512), с выявлением доминирующей релеванты над алфавитом по квадрату 9 с последующей поверкой ее содержимого по критериям избыточности для
(изолированная прямая, дуга, контурная линия, постоянная яркость, хаос и т.п.), путем количественного расчета элементов алфавита на квадрате 9. При этом сжатие изображения выполняется за счет ликвидации межплоскостной избыточности между 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.