Работа с двумерными полями данных информационных систем с конечными ограничениями

РАБОТА С ДВУМЕРНЫМИ ПОЛЯМИ ДАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМ С КОНЕЧНЫМИ ОГРАНИЧЕНИЯМИ Гарнышев И.Н.1, Казанцев С.В.2, Мальков Р.Ю.3, Семенов И.Д.4,

Юдин С.В.5

1 Гарнышев Игорь Николаевич - сетевой инженер, Отдел администрирования сетей передачи данных,

Тинькофф Банк; 2Казанцев Сергей Владимирович - главный инженер, Департамент сетей передачи данных, Сбербанк;

3Мальков Роман Юрьевич - эксперт, Центр компетенций по облачным решениям, Техносерв, г. Москва;

4Семенов Иван Дмитриевич - старший инженер, Департамент сетей передачи данных, Servers.com Лимассол, Кипр;

5Юдин Степан Вячеславович - администратор сети, Департамент технического обеспечения и развития инфраструктуры информационных систем, Спортмастер, г. Москва

Аннотация: в статье проведен анализ принципов организации двумерных полей с конечными ограничениями. Рассмотрены методы расчета элементов одномерных массивов данных, предложена их модификация для работы с двумерным полем, представленным в виде прямоугольной матрицы с равным количеством строк и столбцов. Разработан базовый алгоритм индексирования и определения условной энтропии двумерного массива составного изображения через применение цепного правила в рамках причинной модели.

Ключевые слова: конечное двумерное поле с ограничениями, составное изображение, допустимая конфигурация, комбинаторная энтропия, причинная модель, цепное правило.

Введение

Двумерные поля данных с конечными ограничениями имеют широкое применение при кодировании простых графических изображений, а также составных изображений (compound image) и видеоматериалов, которые могут быть представлены как наборы двумерных информационных блоков [1-4]. Кроме того, т.к. принцип построения систем хранения информации, как аналоговых, так и цифровых, зачастую базируется на создании двумерных структур на поверхности регистрирующей среды, математический аппарат, в основе которого лежит работа с двумерными полями данных, может быть использован и в случае создание помехоустойчивого кодирования информации, а также восстановления и декодирования с частично поврежденных носителей информации [5-7]. Таким образом, рассмотренные сферы применения двумерных полей указывают на высокую актуальность научного исследования и математического моделирования в области кодирования информации в виде двумерных блоков цифровых данных.

Анализ последних исследований и публикаций в данной области позволил обобщить представления о принципах работы с двумерными полями данных информационных систем, которые характеризуются конечными ограничениями. Рассмотрены особенности оцифровки графических изображений и видеоданных [1-4], а также структурирования регистрирующих сред носителей информации и

восстановления данных с поверхности поврежденных носителей информации [5-7]. Проведен анализ принципов математического моделирования при работе с одномерными блоками цифровых данных, которые могут быть расширены на модель двумерного поля данных с конечными ограничениями [8-14].

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

1. Определение двумерного поля с конечными ограничениями Двумерный блок цифровых данных может быть представлен в виде матрицы элементов а (¿,у) , где I и ] относятся к множеству целых чисел и характеризуются к максимальным значениями I и /, соответственно:

Двумерное поле как матрица с конечными ограничениями, таким образом, является набором из I строк и / столбцов, представляющих из себя одномерные матрицы размерности и соответственно. При прямоугольной организации двумерного поля с конечными ограничениями у каждого элемента , в том

случае, если I,] Ф 1 , I Ф I и ] Ф } есть четыре соседних элемента (рис. 1-а): а(1 - 1 ,]) , а(¿,у — 1 ) , а(¿,у + 1 ) и а(1 + 1 ,]). Но данную организацию двумерного поля можно расширить, например, до гексагональной структуры (рис. 1 -б) в таком случае соседних элементов будет шесть: а(1 — 1 ,]), а(¿,] — 1 ) , а(¿,] + 1 ) , а(1 + 1 ,]), (1 —

1 ,] — 1 ) и а — 1 ,] +1) .

?'-2;>2 1

И;>2 М;/§

ш йИ шяш

¿Ч;>2 л!;/

/+2:7+1 /+2;./'+2

Рис. 1. Прямоугольная (а) и гексагональная (б) организация двумерного поля с конечными

ограничениями

Однако в рамках данного исследования за основу математической модели предлагается взять именно прямоугольную организацию двумерного поля с конечными ограничениями, дополнительно уровняв количество строк и столбцов, и, таким образом получить матрицу размерности / x / элементов а ( i,j) , где i,j £ [ 1 ;/] . Такой неочевидный подход позволит упростить задачу практически до уровня с задач для одномерных матриц и воспользоваться соответствующими наработками. В то же время, полученный математический аппарат в дальнейшем можно будет использовать для работы с алгоритмами, в которых подразумевается другой тип организация двумерного поля с конечными ограничениями.

2. Методы расчета элементов двумерного поля

Допустим, что полный набор возможных конфигураций элементов конечного алфавита может быть представлен в виде матрицы с размерностью .

Характерно, что такая матрица будет включать в себя как множества соответствующие допустимым конфигурациям (admissible set) размерности A x А, так и множества соответствующие запрещенным конфигурациям (forbidden set), а соответственно функция, которая соответствует допустимым конфигурациям, определяется как где .

Данный подход позволяет ввести понятие комбинаторной энтропии (combinatorial entropy) по аналогии с введением данного понятия в рамках методологии работы с одномерными массивами [8-11]:

Нс

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

То, что величина является верхним граничным значением для

любого А, следует доказать отдельно. Заполним сколь угодно большую область J  A x J  А матрицами размерности A x А . Количество возможных комбинаций будет равно . В их число, очевидно, входят и все допустимые

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

log

что позволяет конкретизировать предельное значение для показателя комбинаторной энтропии:

С4)

С другой стороны, если заполнить область /  А х /  А с помощь А матриц размерности {]  А + {] — 1)  В) таким образом, чтобы каждая пара матриц была разделена В символами, то для любых значений А и В , а также случайного выбора допустимой конфигурации А х А можно удовлетворить ограничения двумерного поля, что дает математическое определение нижнего предела комбинаторной энтропии:

HC(A) >

log (F(A)) (A + B)2

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

3. Построение причинной модели при двумерном кодировании

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

Проиндексируем прямоугольную матрицу размерности / x J через одномерный массив элементов , где . В рамках причинной модели (causal

model), которую предлагается использовать при построении математического аппарата, вводится универсальный индекс позволяющий определить связи между элементами по аналогии с причинно-следственными связями. Элемент соответствующей причине определяется через функцию , а элемент соответствующий следствию как Wn (рис. 2).

Такой подход позволяет определить значение условной энтропии на основе цепного правила (chain rule), разработанного для одномерных массивов данных [12-14] :

Переход от равенства к неравенству в (6) связан с тем, что условная энтропия либо увеличивается, либо остается прежней при отмене части условий.

N

N

Н(А) = У H(ап\

аг, а2,... CLn_±

) -» H

Двумерное поле с конечными ограничениями

i; i • • • i J • • • 1 \J

• • •

t; i • • • i'J • • • i;J

• • •

• • • i-j • • • i-j

л- I

4------J

Причинная модель: индексирование

1 2 • •• N

----------.-------------------------------------

¿) Цепное правило

Условная энтропия

N • Н{А) = £ п= H

Рис. 2. Алгоритм индексирования и определения условной энтропии двумерного массива в

рамках причинной модели

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

Выводы

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

Список литературы

1. Lin T. & Hao P., 2005. Compound image compression for real-time computer screen image transmission. IEEE Transactions on Image Processing. 14 (8), 993-1005. doi: 10.1109/tip.2005.849776.

2. Ding W., Lu Y. & Wu F., 2007. Enable Efficient Compound Image Compression in H.264/AVC Intra Coding, 2007 IEEE International Conference on Image Processing. doi: 10.1109/icip.2007.4379161.

3. Zhu W., Ding W., Xiong R., Shi Y. & Yin B., 2012. Compound image compression by multi-stage prediction. 2012 Visual Communications and Image Processing. doi: 10.1109/vcip.2012.6410758

4. Andre J., Owens D.A. & Harvey L.O., 2003. Visual perception: the influence of H.W. Leibowitz. Washington, DC: American Psychological Association.

5. Slovak J., Bornholdt C., Bauer S., Kreissl J., Schlak M. & Sartorius B., 2006. Novel concept for all-optical clock recovery from NRZ format PRBS data streams. 2006 Optical Fiber Communication Conference and the National Fiber Optic Engineers Conference. doi: 10.1109/ofc.2006.215908.

6. Milster T.D. & Kim Y.S., 2017. Adaptive optics for data recovery on optical disk fragments (Conference Presentation). Optical Data Storage 2017: From New Materials to New Systems. doi: 10.1117/12.2277078.

7. Masters G. & Turner P., 2007. Forensic data recovery and examination of magnetic swipe card cloning devices. Digital Investigation, 4, 16-22. doi: 10.1016/j.diin.2007.06.018.

8. Bissiri P. & Walker S., 2018. A Definition of Conditional Probability with Non-Stochastic Information. Entropy, 20 (8), 572. doi:10.3390/e20080572.

9. Yan K., 2015. Conditional entropy and fiber entropy for amenable group actions. Journal of Differential Equations, 259 (7), 3004-3031. doi:10.1016/j.jde.2015.04.013.

10. Zhou X., 2016. A formula of conditional entropy and some applications. Discrete and Continuous Dynamical Systems, 36(7), 4063-4075. doi:10.3934/dcds.2016.36.4063.

11. Zeng Q. & Wang J., 2017. Information Landscape and Flux, Mutual Information Rate Decomposition and Entropy Production. doi:10.20944/preprints201710.0067.v1.

12. Bissiri P. & Walker S., 2018. A Definition of Conditional Probability with Non-Stochastic Information. Entropy, 20 (8), 572. doi:10.3390/e20080572.

13. Yan K., 2015. Conditional entropy and fiber entropy for amenable group actions. Journal of Differential Equations, 259 (7), 3004-3031. doi:10.1016/j.jde.2015.04.013.

14. Zhou X., 2016. A formula of conditional entropy and some applications. Discrete and Continuous Dynamical Systems, 36(7), 4063-4075. doi:10.3934/dcds.2016.36.4063.