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

• ВВЕДЕНИЕ

ГЛАВА 1 ОБЗОР МЕТОДОВ СЖАТИЯ И ВОССТАНОВЛЕНИЯ БАЙЕРОВСКИХ МОЗАИЧНЫХ ИЗОБРАЖЕНИЙ МАТРИЧНЫХ ФОТОПРИЕМНИКОВ (БМИМФ).

1.1 Представление растровых изображений.

1.2 Избыточность растровых изображений.

1.3 Основные подходы к кодированию изображений.

1.4 Формирование Байеровских мозаичных изображений матричных фотоприемников на основе ПЗС.

1.5 Методы восстановления полноцветных изображений из БМИМФ.

1.6 Методы сжатия БМИМФ.

1.6 Выводы. Постановка задачи.

ГЛАВА 2 РАЗРАБОТКА МАТЕМАТИЧЕСКОГО И АЛГОРИТМИЧЕСКОГО ОБЕСПЕЧЕНИЯ ДЛЯ ВОССТАНОВЛЕНИЯ И СЖАТИЯ БАЙЕРОВСКИХ МОЗАИЧНЫХ ИЗОБРАЖЕНИЙ МАТРИЧНЫХ ФОТОПРИЕМНИКОВ.

2.1 Модификация метода восстановления БМИМФ - АИЦП.

2.2 Построение алгоритмов преобразования цветов в БМИМФ.

2.3 Разработка алгоритма понижения корреляции подматриц БМИМФ, содержащих зеленые точки.

2.4 Разработка методов сжатия БМИМФ на основе предложенных алгоритмов цветопреобразований и декорреляции подматриц БМИМФ. ф 2.5 Расчет вычислительной сложности использованных в исследовании преобразований.

2.6 Расчет вычислительной сложности использованных в исследовании методов сжатия БМИМФ.

2.7 Выводы.

ГЛАВА 3 РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ДЛЯ РЕАЛИЗАЦИИ АЛГОРИТМОВ СЖАТИЯ ИЗОБРАЖЕНИЙ.

3.1 Разработка структуры ПСР.

3.2 Описание открытых интерфейсов и структур данных ПСР.

3.3 Структура управляющего файла ПСР.

3.4 Выводы.

ГЛАВА 4 ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ РАЗРАБОТАННЫХ МЕТОДОВ ОБРАБОТКИ БАЙЕРОВСКИХ МОЗАИЧНЫХ ИЗОБРАЖЕНИЙ МАТРИЧНЫХ ФОТОПРИЕМНИКОВ.

4.1 Сравнение разработанных методов сжатия БМИМФ с существующими по критерию зависимости оценок искажений от степени сжатия.

4.2 Сравнение разработанных методов восстановления БМИМФ с существующими с помощью объективных оценок.

4.3 Выводы.

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

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

В большинстве случаев в качестве сенсора используется один матричный фотоприемник с нанесенным на него набором цветовых светофильтров. В этом случае в каждой ячейке изображения захватывается только один компонент цвета. Наибольшее распространение получил так называемый Байеровский набор цветовых светофильтров (БНЦС) [1] и информация, полученная с его помощью, называется Байеровское мозаичное изображение матричных фотоприемников (в дальнейшем БМИМФ). Ячейки мозаики с зеленым светофильтром будем называть зелеными точками. Соответственно, красными и синими точками будем называть ячейки мозаики с красными и синими светофильтрами .

Полноцветное изображение содержит в каждой своей ячейке, именуемой пикселем, три компонента цвета. Для восстановления полноцветных изображений из БМИМФ разработаны специальные алгоритмы. Недостающие в ячейке компоненты цвета восстанавливаются с помощью интерполяции из соседних ячеек. Большинство методов восстановления БМИМФ либо соче-(тает малые вычислительные затраты с неудовлетворительным качеством восстановленного изображения, либо дают хороший результат при огромном росте объема вычислений.

Непрерывное совершенствование изделий микроэлектроники, позволяет повысить разрешающую способность устройств цифровой фото-видео съемки. Это приводит к увеличению размера БМИМФ и, соответственно, требует больших объемов памяти для их хранения. Разработка методов сжатия БМИМФ может существенно уменьшить требования к подсистемам хранения и каналам передачи. Эффективные алгоритмы сжатия БМИМФ позволяют создать устройства цифровой фото-видео съемки на базе одной микросхемы.

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

Цель работы

Целью диссертационной работы является разработка математического, алгоритмического и программного обеспечения универсальной поведенческой модели устройства цифровой фото-видеосъемки на базе матричного фотоприемника с БНЦС. При разработке необходимо получить оптимизированные для аппаратной реализации в виде цифрового автомата алгоритмы, учитывающие особую структуру БМИМФ.

Эффективная аппаратная реализация устройства предполагает малое количество однотипных операций и небольшой объем требуемой оперативной памяти.

В разработанных методах сжатия необходимо использовать преобразования исходных цветов из цветового пространства RGB (далее система цветопредставления RGB) в системы цвето-представления YCbCr, RCT (YCbCr аналогично преобразованию ICT в стандарте JPEG2000 [2-4], RCT - обратимое преобразование цветов, описано в том же стандарте). Данные цветовые преобразования существенно повышают эффективность алгоритмов сжатия.

Для достижения поставленной цели необходимо решить следующие научно-технические задачи:

1. Исследовать существующие методы сжатия и восстановления БМИМФ для выявления их достоинств и недостатков .

2. Провести исследование структуры БМИМФ с целью дальнейшего использования найденных особенностей при сжатии.

3. Разработать методы сжатия БМИМФ с потерями и без потерь, учитывающие особую структуру БМИМФ, заключающуюся в корреляции четных и нечетных зеленых точек, и использующие цветовые преобразования для повышения степени сжатия.

4. Разработать улучшенный метод восстановления БМИМФ, основанный на выборе направления предсказания.

5. Провести сравнение разработанных методов сжатия БМИМФ с методом, использующим при сжатии восстановление БМИМФ до полноцветного изображения и методами, основанными на сжатии подматриц БМИМФ, не требующими перехода к полноцветному изображению.

6. Провести сравнение разработанного метода восстановления цветов с существующими методами.

7. Дать оценки аппаратной реализации в виде поведенческой модели для цифрового автомата предложенных алгоритмов обработки БМИМФ.

Научная новизна

1. Разработан метод сжатия БМИМФ без потерь с применением следующих новых алгоритмов: алгоритм перевода БМИМФ из системы цветопредстав-ления RGB в систему цветопредставления RCT, основанный на интерполяции и не требующий полного восстановления полноцветного изображения; алгоритм, учитывающий особую структуру БМИМФ, заключающуюся в корреляции четных и нечетных зеленых точек БМИМФ, эффективно понижающий эту корреляцию .

2. Разработан метод сжатия БМИМФ с потерями с применением следующих новых алгоритмов:

- алгоритм перевода БМИМФ из системы цветопредставления RGB в систему цветопредставления YCbCr, основанный на интерполяции и не требующий полного восстановления полноцветного изображения;

- алгоритм, учитывающий особую структуру БМИМФ, заключающуюся в корреляции четных и нечетных зеленых точек БМИМФ, эффективно понижающий эту корреляцию .

3. Разработан модифицированный метод восстановления полноцветного изображения из БМИМФ, использующий новый способ восстановления компонентов, для которых возможны два направления предсказания.

Практическая значимость

1. Разработаны и реализованы программно и аппаратно методы и алгоритмы, направленные на сжатие БМИМФ, не требующие перехода к полноцветному изображению.

2. Показано, что разработанные алгоритмы сжатия эффективно реализуются в виде НОЬ-описания цифрового автомата .

3. Полученные математические модели и алгоритмы применяются в разработанном на предприятии ООО «Юник Ай Сиз» компактном устройстве видеосъемки.

4. Модифицирован и реализован метод восстановления полноцветных изображений из БМИМФ.

Внедрение результатов работы

Использование разработанной поведенческой модели устройства цифровой фото-видеосъемки на предприятии ООО «Юник Ай Сиз» позволило определить характеристики проектируемой компактной видеокамеры в виде веб-камеры на базе сенсора, использующего матричный фотоприемник с БНЦС. ф На защиту выносится следующее

1. Разработанное математическое и алгоритмическое обеспечение поведенческой модели устройства цифровой фото-видеосъемки, включающее метод сжатия БМИМФ с потерями имеет следующие характеристики:

- использует алгоритмы необратимого преобразования цветов УСЬСг и понижения корреляции между двумя подматрицами зеленых точек для сжатия БМИМФ;

- не требует полного восстановления полноцветного изображения, что экономит оперативную память;

- приводит к повышению степени сжатия при равных искажениях восстановленных изображений, по сравнению с моделью на базе метода прямого сжатия подматриц БМИМФ;

Ш *

- имеет примерно равное качество восстановленных изображений и требует в два раза меньшее количество операций, по сравнению с моделью на базе метода сжатия, использующего восстановление БМИМФ до полноцветного изображения.

2. Алгоритм понижения корреляции между двумя подматри-^ цами зеленых точек БМИМФ, основанный на предсказании отсчетов одной подматрицы по отсчетам другой подматрицы, улучшает характеристики методов сжатия БМИМФ.

3. Уменьшение количества операций вплоть до двух раз в алгоритмах преобразования цветов ИСТ и УСЬСг в БМИМФ связано с тем, что вычисление новых компонентов цвета в синих и красных ячейках требует интерполяции только одного компонента цвета из соседней ячейки.

4. Сжатие БМИМФ без потерь с использованием алгоритма обратимого преобразования цветов ИСТ и алгоритма понижения корреляции между двумя подматрицами зеленых точек, увеличивает степень сжатия на 5%, при этом вычислительные затраты возрастают на 20-30%.

5. Изменение способа восстановления компонентов цвета, для которых возможны два направления предсказания, путем вычисления взвешенной суммы предсказателей по возможным направлениям в методе восстановления полноцветных изображений из БМИМФ «интерполяция с цветовой коррекцией» позволяет восстанавливать БМИМФ на 5-25% точнее.

Апробация работы

Результаты диссертационной работы докладывались и обсуждались на следующих конференциях:

- 4 Международная конференция и выставка «Цифровая обработка сигналов и ее применение»: М. 2002г;

- Х1Л/ научная конференция МФТИ: М. 2002г;

- международная конференция «Телевидение: передача и обработка изображений»: СПБ. 2003г;

- 5 международная конференция и выставка «Цифровая обработка сигналов и ее применение»: М. 2003г;

- 10 Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика- 2003»: М. 2003г;

- 4 международная конференция «Телевидение: передача и обработка изображений»: СПБ. 2005г.

Публикации

Основные результаты диссертационной работы опубликованы в 13 печатных работах [30,47-58].

Структура и объем диссертации

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

Основные результаты исследований, проведенных в рамках диссертационной работы, состоят в следующем:

1. Разработано математическое и алгоритмическое обеспечение поведенческой модели устройства цифровой фотовидеосъемки.

2. Построены алгоритмы перевода БМИМФ из системы цвето-представления RGB в систему цветопредставления YCbCr (RCT) и обратно, основанные на интерполяции, не требующие полного восстановления полноцветного изображения, что позволяет уменьшить вычислительные затраты до 50%, по сравнению с известными алгоритмами.

3. Разработан алгоритм понижения корреляции между подматрицами четных и нечетных зеленых точек БМИМФ, имеющий следующие особенности:

• не требует дополнительного объема оперативной памяти;

• не использует пространственный сдвиг подматрицы БМИМФ, содержащей четные зеленые точки, относительно подматрицы, содержащей нечетные зеленые точки;

• позволяет увеличить степень сжатия при неизменном качестве сжатых изображений;

• имеет эффективный алгоритм для обратного преобразования .

4. На основе разработанных алгоритмов построены методы сжатия БМИМФ без потерь и с потерями, учитывающие их особую структуру, заключающуюся в корреляции четных и нечетных зеленых точек, с использованием обратимого и необратимого цветового преобразования, имеющие на 3045% большую вычислительную сложность, чем метод сжатия БМИМФ, основанный на раздельной обработке подматриц БМИМФ. Новые методы сжатия приводят к меньшим искажениям изображений в терминах СКО и ВСК0-М2 по сравнению с методом сжатия БМИМФ, использующим раздельную обработку подматриц БМИМФ, при равной степени сжатия.

5. Получен метод сжатия БМИМФ, учитывающий их особую структуру, заключающуюся в корреляции четных и нечетных зеленых точек, без использования цветовых преобразований, имеющий вычислительную сложность равную вычислительной сложности метода сжатия БМИМФ, основанного на раздельной обработке подматриц БМИМФ. Новый метод сжатия приводит к меньшим искажениям изображений в терминах СКО и ВСК0-М2 по сравнению с методом сжатия БМИМФ, использующим раздельную обработку подматриц БМИМФ, при равной степени сжатия.

6. Предложен модифицированный путем изменения способа предсказания в методе АИЦП метод восстановления полноцветных изображений из БМИМФ, который позволяет более точно восстанавливать недостающие компоненты цвета в БМИМФ.

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

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

Разработанные методы сжатия БМИМФ позволили существенно снизить вычислительные затраты и объем оперативной памяти, необходимые для эффективной компрессии БМИМФ. Результаты исследований в виде базовых алгоритмов были применены на предприятии ООО «Юник Ай Сиз» при создании компактной видеокамеры в виде веб-камеры на базе сенсора, использующего матричный фотоприемник с БНЦС.

Заключение

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

1. Пат. 3971065 США МКИ2 H04N 9/24. Color imaging array / Bayer,Bryce E. (США);Eastmen Kodak Company (США).-№555477; Заяв. 05.05.1975; Опубл. 20.07.1976; НКИ 358/41.-10 е., 4 л. ил.

2. ISO/IEC 15444-1 Information technology JPEG 2000 image coding system. Part 1: Core coding system. Введ. 15.12.00. - Switzerland: ISO, 2000. - 218 c.

3. Marcellin M. et all. An Overview of JPEG-2000 // Proc. Data Compression Conference, J.A. Storer and M. Cohn, eds. Snowbird, Utah, Mar. 28-30, 2000. Snowbird, 2000.- pp. 523-541.

4. Taubman D.S., Marcellin M.W. JPEG2000: Image compression fundamentals, standards and practice Boston/Dordrecht/London: Kluwer Academic Publishers, 2002.- 773 p.

5. Pratt W.K. Digital Image Processing: PIKS Inside, 3rd Edition New York : John Wiley & Sons, Inc., 2001. -738 p.

6. Умняшкин С.В. Применение дискретного преобразования Кре-стенсона-Леви в цифровой обработке изображений: дис.канд. физ.-мат. наук: 05.13.01: защищена в 1997 г. / МГИЭТ-ТУ. Москва, 1997. - 198 с.

7. Методы компьютерной обработки изображений/под ред. Сой-фера В.А. М.: ФИЗМАТЛИТ, 2003. - 784 с.

8. Умняшкин С.В. Математические методы и алгоритмы цифровой компрессии изображений с использованием ортогональных преобразований: дис. .докт. физ.-мат. наук: 05.13.11: защищена в 2002 г. / МГИЭТ-ТУ. Москва, 2002. - 382 с.

9. Calderbank A.R., Daubechies I., Sweldens W., Yeo B. Wavelet transforms that map integers to integers // Appl. Comput. Harmon. Anal., 1998, vol. 1.5, №3. pp.332 369.

10. Gray R.M., Neuhov D.L. Quantization // IEEE Transactions on Information Theory, Oct. 1998, vol. 44, №6. -pp. 163.

11. Senoo Т., Giord B. Vector quantization for entropy coding of image subbands // IEEE Trans. Image Proc., 1992, V.1, №4. p. 526-532.

12. Ватолин Д., Ратушняк А., Смирнов M., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГ-МИФИ, 2002. - 384 с.

13. Shannon С.Е. A Mathematical Theory of Communication // The Bell System Technical Journal, Jul., Oct. 1948, vol. 27, pp. 379-423, 623-656.

14. Дмитриев В.И. Прикладная теория информации: Учеб. для студ. вузов. М.: Высш. шк., 1989. - 320 с.

15. Moffat A., Bell Т., Witten I.H. Lossless Compression for Text and Images. // Int. Journal of High Speed Electronics and Systems, 8(1), 1997 pp. 179-231.

16. Семенюк В. В. Экономное кодирование дискретной информации. Монография. СПб: СПб ГИТМО(ТУ), 2001. - 115 с.

17. Быков Р.Е., Фрайер Р., Иванов К.В., Манцветов А.А. Цифровое преобразование изображений. Учеб. пособие для вузов / под редакцией проф. Р.Е. Быкова. М.: Горячая линия - Телеком, 2003 - 228 с.

18. Muresan D.D., Parks T.W. Adaptively Quadratic (AQua) Image Interpolation // IEEE Trans, on Image Proc., 2004, Vol. 13, №5.

19. Gunturk B.K., Altunbasak Y., Mersereau R.M. Color Plane Interpolation Using Alternating Projections // IEEE Trans, on Image Proc., 2002, vol. 11, №9. pp. 9971013.

20. Chan W.C., Au O.C., Fu M.F., Hong Kong A Novel Color Interpolation Framework in Modified YCbCr Domain for Digital Cameras // IEEE Proceedings of the 2003 International Conference on Image Processing (ICIP), September 14-18, vol. 2, 2003.

21. Kimmel R. Demosaicing: Image Reconstruction from Color CCD Samples // IEEE Trans, on Image Proc., 1999, vol. 8, №9, pp. 1221-1228.

22. Xin Li, Orchard M.T. New Edge-Directed Interpolation // IEEE Trans, on Image Proc., Oct. 2001, vol. 10, №10. -pp. 1521-1527.

23. Chang Е., Cheung S., Pan D.Y. Color filter array recovery using a threshold-based variable number of gradients // Proc. SPIE, 1999, vol. 3650.

24. Andreas M.I. Nilsson & Pierre U.W. Nordblom, Interpolation in Color Filter Arrays Master Thesis in Computer Science and Image Processing, Malm University, School of Technology and Society, 2002. - p. 99.

25. Chin Chye Koh, Mukherjee J., Mitra S.K. New Efficient Methods of Image Compression in Digital Cameras with Color Filter Array // IEEE Transactions on Consumer Electronics, 2003, Vol. 49, №4. pp. 1448-1456.

26. Шерешевский Д.И., Мишуровский М.Н., Ковлига И.М., Тишин А.Ю., Фартуков A.M. Аппроксимация функции распределения ДВП цифрового растрового изображения // «XLV научная конференция МФТИ». Тезисы докладов, Москва: МФТИ, 2002.

27. Centen P. CCD Imaging: Concepts for Low Noise and High Bandwidth Eindhoven : Technische Universiteit Eindhoven, 1999. - 216 p.

28. Мишуровский M.H. Разработка математического, алгоритмического и программного обеспечения специализированной САПР устройств сжатия изображений: дис. .канд. техн. наук: 05.12.13: защищена 27.12.04 / МГИЭТ-ТУ. Москва, 2004. - 130 с.

29. Fenwick P.M. Punctured elias codes for variable-length coding of the integers // Tech. report, Dept. of Сотр. Sci., Auckland Univ., 1996. p. 137.

30. Bookstein A. Klein S. T. Is Huffman coding dead? // Computing, Vol. 50, №4, 1993. pp. 279-296.

31. Recommendation T.81 Information technology digital compression and coding of continuous-tone still images-Requirements and guidelines. Введ. 18.09.92. - CCITT, 1992. - 186 c.

32. Said A., Pearlman W.A. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees //

33. EE Transactions on Circuits and Systems for Video Technology, 1996, VI.6. pp.243-250.

34. Tompa D., Morgan J, Jernigan E. Computational imafe quality metrics: A review // Society for Information Display International Symposium Digest of Technical Papers, 1993, Vol.24. pp. 305-308.

35. Ramanath A.R., Snyder B.W., Hinks C.D. Image Comparison Measure for Digital Still Color Cameras // Proceedings IEEE International Conference on Image Processing, Sep. 2002, vol. 1. pp. 629-632.

36. Rao K.R., Narasimhan М.А., Revuluri К. Image data processing by Hadamard-Haar transform // IEEE Trans. Computers, 1975, V.C-23, №9, p. 888-896.

37. Enomoto H., Shibata K. Orthogonal transform coding system for television signals // IEEE Trans. Electromagnetic Compatibility. 1971. - Special issue on Walsh functions. -V. EMC-13. - №3. - p. 11-17.

38. Pratt W.K., Chen W.H., Welch L.R. Slant transform image coding // IEEE Trans. Commun. 1974, V. COM-22, p.1075-1093.

39. Davis G., Nosratinia A. Wavelet-based Image Coding: An Overview // Applied and Computational Control, Signals and Circuits. 1998, vol. 1, №1. - pp. 205-269.

40. Battiato S., Bruna A., Buemi A., Naccari F. Coding Techniques for CFA Data Images // Proceedings of IEEE International Conference on Image Analysis and Processing -pp. 418-423 Mantova, Italy - Sep. 2003.

41. Olsen Т., Strand J.S. An improved image processing chain for mobile terminals Master thesis in Information and Communication Technology, Grimstad, 2002.

42. Ковлига И.М., Шерешевский Д.И., Мишуровский М.Н., Тишин А.Ю., Фартуков A.M. Исследование разностных последовательностей при дифференциальной импульсно-кодовой модуляции изображений // «XLV научная конференция МФТИ». Тезисы докладов, Москва: МФТИ, 2002.

43. Ковлига И.М., Шерешевский Д.И., Мишуровский М.Н., Тишин А.Ю., Фартуков A.M. Автоматизированное построение нормированной оценки качества изображений // «XLV научная конференция МФТИ». Тезисы докладов, Москва: МФТИ, 2002.

44. Ковлига И.М., Миргородский А.Ю. Сжатие мозаичных изображений // «Микроэлектроника и информатика-2003». 10-ая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов, Москва, 2003.