автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Математические вопросы оптимизации числа ракурсов задач реконструктивной томографии в классе дискретных тел

ВВЕДЕНИЕ 3 1 .ЗАДАЧА МИНИМИЗАЦИИ ДИХОТОМИЧЕСКОЙ

КЛАССИФИКАЦИИ ПО ЧИСЛУ СВОЙСТВ

1.1 Постановка задачи минимизации дихотомической классификации по числу свойств

1.2. Обзор задач дискретной оптимизации, сводящихся к задаче минимизации (0,1)- матрицы

1.3. Решение задачи минимизации дихотомической классификации по числу свойств 23 2. МИНИМИЗАЦИЯ ЧИСЛА РАКУРСОВ В КЛАССИФИКАЦИОННЫХ ЗАДАЧАХ ТОМОГРАФИИ

2.1. Математические постановки основных задач томографии

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

2.3. Единственность реконструкции по конечному числу ракурсов в классе дискретных распределений

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

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

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

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

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

С другой стороны, при эксплуатации рентгеновских томографов стоит важная производственная задача уменьшения времени (а в медицине и степени облучённости объекта) затраченного на получение достаточного количества рентгенограмм и их обработку в расчёте на один исследуемый объект. Кроме того, достаточное для решения поставленной задачи количество разноракурсных рентгенограмм зависит от характера этой задачи, может меняться от задачи к задаче и варьироваться при изменении условий или требований к решению. Естественно и целесообразно производить и использовать меньшее количество рентгенограмм для решения тех задач, где это уменьшение не ухудшает качества и степени достоверности диагноза. Один из путей оптимизации производственных рентгеновских томографических исследований состоит в использовании как можно меньшего количества разноракурсных рентгенограмм, достаточных для решения поставленной задачи.

Следующая задача является одной из основных задач томографии. Пусть задан класс А исследуемых объектов, в котором выделено два непересекающихся подкласса А', А". Условно, ориентируясь на технические приложения, классы А', А" можно именовать классом «качественных» и «бракованных» объектов соответственно, или, ориентируясь на медицинскую тематику, соответственно классом «здоровых» и «больных» объектов.

Упомянутая задача томографии состоит в установлении принадлежности исследуемого объекта Т из класса А, какому либо из указанных двух классов А', А" на основе заданной N - ракурсной рентгеновской томограмме этого объекта. Будем называть ее классификационной задачей томографии.

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

Отметим, что оптимизационная задача предполагает и исходит из того, что томограмма, которая решает задачу классификации предъявлена, и речь идет лишь об уменьшении мощности этой томограммы с сохранением ее основного свойства - классифицировать объекты из классов А', А".

Аналогичные проблемы существуют и в распознавании образов, которые получили название «минимизации описаний».

В первых работах по минимизации описаний задача рассматривалась в следующей интерпретации [2]. Значения всех признаков (как правило, двоичных) выписываются для всех подлежащих различению изображений в некотором стандартном порядке. Образуется таблица, строками которой являются двоичные числа - кодовые комбинации для каждого из изображений. Нужно указать правило вычёркивания наибольшего количества столбцов, т.е. отсева наибольшего количества признаков при условии, что оставшиеся разряды (признаки) обеспечат отличие кодовых комбинаций, относящихся к разным классам, не менее чем в заданном числе разрядов [3].

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

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

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

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

Рассмотренный в диссертации класс дискретных распределений нулевого порядка (т.е. дискретных мер Радона в терминологии Н. Бурбаки) представляет тот модельный класс объектов, для которых преобразования Фурье легко описываются, обладают обозримыми и достаточно хорошо известными аналитическими свойствами. Показано, что для этого класса распределений с ограниченным числом точек носителя основная задача проекционной томографии может быть положительно решена почти наглядным геометро-аналитическим способом. Относительно представительности класса дискретных распределений в классе всех распределений (последний класс является в практическом смысле максимальным и описывает всевозможные физические тела) отметим, что в смысле слабой аппроксимации этот класс всюду плотен в классе всех распределений, так что любое физическое тело может быть сколь угодно близко (в слабом смысле) аппроксимировано дискретными распределениями. Этот класс сохраняет свои аппроксимационные свойства и при рассмотрении различного рода специальных приближений и норм в функциональных Соболевских про- I странствах [5].

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

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

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

Основным результатом второй главы является теорема единственности идентификации любых дискретных тел, число точек носителя которых не превосходит заданного целого числа N. Кроме того, в конце второй главы рас9 смотрен демонстрационный пример, иллюстрирующий взаимодействие результатов и методов первой и второй глав.

Все основные результаты диссертации опубликованы в работах [6-8].

В приложении приведен текст оригинальной компьютерной программы, реализующей алгоритм первой главы.

В завершение хочу выразить благодарность за обсуждение результатов работы кандидату технических наук Б.К. Алабину, доктору физико-математических наук, профессору С.Ф. Кожухову. Особую благодарность выражаю своим научным руководителям доктору физико-математических наук, профессору В.Р. Кирейтову, кандидату технических наук Н.Г. Шевченко.

1. ЗАДАЧА МИНИМИЗАЦИИ ДИХОТОМИЧЕСКОЙ КЛАССИФИКАЦИИ ПО ЧИСЛУ СВОЙСТВ

В заключение приведем основные результаты и выводы работы.

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

2. Написана компьютерная программа реализующая данный алгоритм.

3. Доказана теорема единственности решения задачи томографии для дискретных тел, устанавливающая достаточность 27У" произвольных ракурсов для идентификации произвольных двух дискретных тел, носитель которых состоит не более, чем из Л" точек.

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

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

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

1.Лавреньтев М.М., Кирейтов В.Р., Пикапов В.В., Преображенский Н.Г. Проблемы физической томографии.// Всесоюзный симпозиум по вычислительной томографии, Новосибирск, 19 -23 декабря, 1983 с. 121-122.

2. Файн B.C. Опознавание изображений. М.: Наука, 1970.

3. Блох Э.Л. К вопросу о минимальном описании. Радиотехника, 1960, т. 15, №2.

4. Лаврентьев М.М., Деревцов Е.Ю., Шарафутдинов В.А. Об определении оптического тела, находящегося в однородной среде, по его изображениям. Докл. АН СССР, 1981, т. 260, №4 с.799 803.

5. Соболев С.Л. Введение в теорию кубатурных формул. М.: Наука, 1974.

6. Назин А.Г.«Минимизация классификации по числу свойств с использованием лексикографического порядка.» //Препринт СурГУ, Сургут, 1999, 12 с.

7. Назин А.Г.«0 единственности решения основной задачи томографии в классе распределений дискретного типа». Электронный журнал «Исследовано в России», 87, стр. 952-965,2002 г. http.7/zhurnal.ape.relarn.ru/articles/2002/087.pdf.

8. Алабин. Б.К. Типовые задачи минимизации эмпирических таблиц при обработке геологических данных. Препринт, Магадан, 1987, 18 с.

9. Ю.Горбатов В.А. Фундаментальные основы дискретной математики. М.: Наука, Физматлит, 1999.

10. П.Яблонский C.B. Введение в дискретную математику. М.: Наука, 1986. 12.С. Колдуэлл. Логический синтез релейных устройств. М.: ИЛ., 1962.

11. Appel К., Haken W. Every Planar Map Is Four Colorable. Contemporary Mathematics. Providence (R.I.): Amer. Math Soc., 1989. Vol. 98. 308 p.

12. S.J. Hong, D.L. Ostapko. Generating test examples for heuristic Boolean Minimization. IBM Journal Research and Development, pp 459-464,1974.

13. Еремеев A.B., Заозерская JI.А., Колоколов А.А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования. Дискретный анализ и исследование операций. Сер. 2, 2000, т.7, №2, с.22-46.

14. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

15. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.

16. Стрыгин В. 3. Математическое теоретико-множественное и математико-логическое обоснование решения некоторых NP полных задач полиномиальными алгоритмами. - Препринт ЦАГИ, М., 1994, №106, 35 с.

17. S.J. Hong, R.G. Cain, D.L. Ostapko. MINI: A Heueristic Approach for Logic Minimization. IBM Journal Research and Development, pp 443-458 , 1974.

18. R. K. Brayton, G. D. Hachtel, С. T. McMullen, and A. L. SangiovanniVincentelli, Logic Minimization Algorithms for VLSI Synthesis. Boston, MA, Kluwer Academic Publishers, 1984, 192 p.

19. Hlavicka, J. Fiser, P.: BOOM - a Heuristic Boolean Minimizer.

20. Proc. International Conference on Computer-Aided Design ICC AD 2001, San Jose, California (USA), 4.- 8.11.2001, pp. 439-442.

21. G. D. Hachtel, Somenzi F. Logic synthesis and verification algorithms. Boston, MA, Kluwer Academic Publishers, 1996, 564 p.

22. P.McGeer, J.Sanghavi, R.Brayton and A.Sangiovanni-Vincentelli. ESPRESSO-SIGNATURE: A New Exact Minimizer for Logic Functions. IEEE Transactions on VLSI, 1 (4):432-440, 1993.58

23. Стрыгин В.З. Полиномиальный алгоритм минимизации случайных («почти всех») булевых функций. Препринт ЦАГИ, М., 1992, №56, 8 с.

24. Журавлев Ю.И. Алгоритмы построения минимальных дизъюнктивных нормальных форм для функций алгебры логики. // Дискретная математика и математические вопросы кибернетики. Т.1., М.: Наука, 1974, с.67-98.

25. Андреев. А.Е. О проблеме минимизации дизъюнктивных нормальных форм. Доклады АН СССР 1984, т.274, № 2, с.265-269.

26. Владимиров B.C. Обобщенные функции в математической физике. М.: Наука, 1976.

27. Шабат В.Б. Введение в комплексный анализ. М.: Наука, 1969.59