Алгоритм плотной стереореконструкции на основе контрольных точек и разметки плоскостями

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

4. Алгоритм исправления ошибок должен поддерживать исправление максимального количества типов ошибок, и следовательно, алгоритм исправления ошибок может быть сложным, то есть состоять из нескольких алгоритмов, примененных один за другим.

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

Литература

1. Chepurov A., Jenihhin M., Raik J., Repinski U., Ubar R. High-level design error diagnosis using backtrace on decision diagrams. 28th Norchip Conf., Tampere, FINLAND, 2010.

2. Diamond FP7 Project. URL: http://fp7-diamond.eu/ (дата обращения: 4.05.2012).

3. University of Bremen, Faculty of Computer Science. URL: http://www.informatik.uni-bremen.de/agra/eng/forensic.php (дата обращения: 4.05.2012).

4. William K. Lam: Hardware Design Verification. Simulation and Formal Method- Based Approaches. Prentice Hall. Profession Technical Reference, 2005, pp. 1—23.

5. Jadish S. Lecture notes on Design & Analysys of Accountuing Information Systems, URL: http://www.albany.edu/ acc/courses/acc681.fall00/681book/681book.html (дата обращения: 02.03.2012).

6. An approach to animating Z specifications, Xiaoping Jia, Computer Software and Applications Conf., COMPSAC-95. Proceedings., Nineteenth Annual International, 1995, pp. 108-113.

7. Kas'janov V.N. Distinguishing Hammocks in a Directed Graph, Soviet Math. Doklady, 1975, Vol. 16, no. 5, pp. 448-450.

8. Mark Weiser, Program Slicing, IEEE Transactions on Software Engineering, 1984, Vol. SE-10, no. 4, pp. 352-357.

9. Bug Aristotle Analysis System - Siemens Programs, HR Variant, URL: http://pleuma.cc.gatech.edu/aristotle/Tools/subjects/ (дата обращения: 02.03.2012).

10. Debroy V. and Wong W.E. Using Mutation to Automatically Suggest Fixes for Faulty Programs, Software Testing, Verification and Validation (ICST), 3rd International Conf., 2010, pp. 65-74.

11. Kang J., Seth S.C., Yi-Shing Chang, Gangaram V. Efficient Selection of Observation Points for Functional Tests. Quality Electronic Design, ISQED-2008, 9th International Symposium on, 2008, pp. 236-241.

УДК 519.688

АЛГОРИТМ ПЛОТНОЙ СТЕРЕОРЕКОНСТРУКЦИИ НА ОСНОВЕ КОНТРОЛЬНЫХ ТОЧЕК И РАЗМЕТКИ ПЛОСКОСТЯМИ

Г.Р. Кривовязь, аспирант; С.В. Птенцов, студент; А.С. Конушин, к.ф.-м.н., научный сотрудник

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

Ключевые слова: компьютерное зрение, плотное стерео, карта диспаритета, стереопара, контрольные точки, сопоставление изображений.

A DENSE STEREO MATCHING ALGORITHM BASED ON GROUND CONTROL POINTS

AND PLANE LABELING Krivovyaz G.R, Postgraduate; Ptentsov S. V., Student; Konushin AS., Ph.D., Research Associate (Lomonosov Moscow State University, Leninskie Gory, Moscow, 119991, Russia, gkrivovyaz@graphics.cs.msu.ru, sptentsov@rambler. ru, ktosh@graphics.cs.msu. ru) Abstract. In this work a new dense stereo matching algorithm is proposed. The algorithm is based upon a recently introduced idea of non-local cost aggregation on a minimum spanning tree that includes all image pixels. Themainfeatureoftheproposed algorithmisto switchfrom disparity space to plane space: the disparity in each pixel is deduced from equation of a plane assigned to that pixel. A way of estimating the set of planes, which are used to approximate the

scene, is described. For this purpose, ground control points (GCPs) are used. GCPs, derivedas a result of image matching, are also exploited to regularize the solution. Theresultsofalgorithmevaluationononeofthe moderndatasets (published in 2012) are provided. Thedatasetconsistsof 194 streetviewimagepairs. Thediscussion of possiblewaysoffurtheralgorithmimprovement concludes the paper.

Keywords: computer vision, dense stereo matching, disparity map, stereo pair, ground control points, image matching.

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

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

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

Существующие подходы

Все известные алгоритмы бинокулярного стерео можно разбить на две большие группы - локальные и глобальные. В первую входят методы, использующие для вычисления диспаритета в каждой точке информацию лишь с части пикселей изображения, как правило, из окрестности данной точки. Простейший подобный алгоритм подразумевает сравнение квадратных окон по одной из метрик, например SAD (Sum of Absolute Differences - сумма абсолютных значений разностей яркости), и выбор в каждой точке диспаритета, для которого величина сравнения, называемая также стоимостью, минимальна. Более сложные алгоритмы, например [2] и [3], используют окна с

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

Глобальные методы используют информацию со всех пикселей изображения при вычислении решения в каждой точке. Часто решение формулируется в терминах минимизации энергии на графе, вершины которого соответствуют пикселям изображения. Энергия состоит из унарного потенциала, отвечающего за согласованность решения по яркости, и парного потенциала, контролирующего гладкость решения. Подобные алгоритмы различаются структурой графа, видом унарного и парного потенциалов и методом минимизации энергии. Примерами могут служить методы, описанные в работах [4] и [5]. Как правило, результат глобальных алгоритмов превосходит результат локальных, однако время их работы в среднем больше.

Приобретают популярность методы, пытающиеся совместить сильные стороны локальных и глобальных алгоритмов. Решение в каждом пикселе принимается независимо, однако влияние на него оказывают либо все остальные пиксели изображения, либо часть пикселей, не ограниченных локальной окрестностью данной точки. К числу подобных методов относятся алгоритмы, использующие общую идею поиска оптимального решения в каждом пикселе путем применения динамического программирования на дереве [6, 7]. К данной группе относится и подход [8], рассматриваемый в данной работе как базовый, поскольку от него отталкивается предлагаемый алгоритм.

Алгоритм [8] использует понятие минимального покрывающего дерева. Пусть G - некоторый граф с заданными на нем весами ребер. Минимальным покрывающим деревом для графа G называется такое дерево, которое включает в себя все вершины графа и сумма весов ребер которого минимальна. Для вычисления минимального покрывающего дерева известны эффективные алгоритмы, например [9]. Идея алгоритма [8] заключается в агрегации стоимостей присвоения пикселю того или иного диспаритета не по окну, как принято в локальных алгоритмах, а по дереву, покрывающему все изображение. Дерево является минимальным покрывающим деревом для графа

изображения, то есть графа, в котором вершины соответствуют пикселям изображения и соединены ребрами по принципу четырехсвязности, а вес ребра равен абсолютному значению разности яркостей соединяемых им пикселей: wrs= \ Ir—Is \. Расстояние Dpq между двумя произвольными пикселями p и q определяется как сумма весов вдоль кратчайшего пути между соответствующими вершинами дерева. Выражение для агрегированной стоимости присвоения диспаритета d пикселю p

имеет вид EÄpgg

gel CT

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

стоимость: dp = arg min Epss (d).

P d P

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

Предложенный алгоритм

Рассмотрим алгоритм, основывающийся на вычислительно эффективном подходе базового метода, но лишенный указанного выше недостатка. Решение ищется не в пространстве диспарите-тов, а в пространстве плоскостей. Набор плоскостей, присутствующих в сцене, вычисляется по контрольным точкам (ground control points, GCP) -разреженным точкам, для которых с высокой степенью уверенности известно правильное значение диспаритета. Контрольные точки используются также для регуляризации решения.

Представление решения в виде разметки плоскостями. Решение d в каждом пикселе p представим в виде плоскости f в пространстве {x, y, d}: dp = af x + bf y + cf. Такое представление уже встречалось ранее [10]. Пусть F - некоторый на-

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

(/) = ЕА;' ) = X ехр(-^(<).

СТ

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

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

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

1. Вычисление алгоритмом RANSAC [12] параметров плоскости, поддерживаемой наибольшим числом точек из ОСР. Добавление плоскости в множество Е.

2. Исключение поддерживающих плоскость точек из множества ОСР.

3. Повторение шагов 1 и 2, пока существуют плоскости, поддерживаемые достаточным числом точек.

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

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

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

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

ЕАГСР ) = X ехр «),

де/ СТ

где CGCP (d) =

\(<1 - й^сс )2, q е ССР, [о, q г ССР.

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

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

Efp (d) = - ln((1 -n)exp(--

d - dG

Y

Ч +П),

где п и у - параметры функции.

Данный вид штрафной функции в применении к задаче плотной стереореконструкции предложен в работе [11], авторы которой включили E(^p (d) в

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

Итоговая стоимость присвоения плоскости f пикселю p в предлагаемом алгоритме примет вид

Ep (f) = EA/g (dp) + X- Epcp (dp).

Здесь X - параметр, контролирующий степень влияния карты диспаритета DGCP на итоговое решение. В каждом пикселе выбирается плоскость, для которой стоимость Ep(f минимальна.

Основные шаги предложенного алгоритма представлены на рисунке 2.

Экспериментальная оценка

Тестирование предложенного алгоритма проводилось на наборе данных KITTI (Karlsruhe

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

Вычисление регуляризирующего решения D

-О

Рис. 2. Схема предложенного алгоритма

Institute of Technology and Toyota Technological Institute) [13], содержащем 194 пары ректифицированных изображений и эталонные карты диспаритета, полученные путем лазерного сканирования. По сравнению с более популярным на сегодняшний день набором Middlebury [14] тестовый набор KITTI содержит более интересные и более сложные с точки зрения практических задач данные: изображения были получены не в лабораторных условиях, а съемкой с автомобиля при проезде по улицам города. При этом характер представленных в наборе сцен позволяет лучше продемонстрировать преимущества предложенного алгоритма.

Тестирование проходило при следующих значениях параметров алгоритма: ст=0,1, п=0,005, Y=2, Х=40. В роли критерия качества использовался процент пикселей, для которых разница между найденным и эталонным значениями диспаритета превысила порог т при значении т=3. Контрольные точки были получены путем сопоставления ректифицированных изображений с использованием особых точек Харриса [15] и дескрипторов SIFT [16]. В таблице представлены средняя ошибка по всей базе, а также минимальная и максимальная ошибки по всем парам изображений для базового и предложенного алгоритмов.

Результаты сравнения алгоритмов

Ошибка Алгоритм [8] Предложенный алгоритм

Средняя 33,03 % 18,60 %

Минимальная 8,82 % 1,01 %

Максимальная 73,46 % 68,97 %

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

Дальнейшие исследования

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

Другим узким местом алгоритма является шаг вычисления набора плоскостей F. Неточная оценка параметров плоскостей, нахождение лишних или, наоборот, пропуск плоскостей, присутствующих в сцене, приведут к ошибкам в карте диспаритета. Одним из способов устранения данного недостатка может стать итерационное применение алгоритма с дополнительным этапом уточнения параметров плоскостей между итерациями подобно тому, как это делается в работе [10]. Использование алгоритмов геометрического разбора изображений, например [17], позволило бы получить более точный начальный набор плоскостей. Также возможно дополнение множества контрольных точек другими примитивами, например отрезками, для которых найдены надежные соответствия между двумя изображениями. Наконец, применение более сложных, чем описанный жадный алгоритм, методов сегментации плоскостей в облаке трехмерных точек, например на основе работы [18], тоже может дать улучшение результатов.

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

Литература

1. Scharstein D., Szeliski R. A Taxonomy and Evaluation of Dense Two-Frame StereoCorrespondenceAlgorithms, Int. Journ. of Computer Vision, 2002, Vol. 47, no. 1-3, pp. 7-42.

2. Hosni A., Bleyer M., Gelautz M., Rhemann C. Local stereo matching using geodesic support weights, Proc. of the 16th IEEE Int. Conf. on Image Processing (ICIP), 2009, pp. 2093-2096.

3. Hirschmuller H., Innocent P., Garibaldi J. Real-time correlation-based stereo vision with reduced border errors, Int. Journ. of Computer Vision, 2002, Vol. 47, no. 1-3, pp. 229-246.

4. Woodford O., Torr P., Reid I., Fitzgibbon A. Global Stereo Reconstruction under Second-Order Smoothness Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, Vol. 31, no. 12, pp. 2115-2128.

5. Bleyer M., Rother C., Kohli P. Surface Stereo with Soft Segmentation, Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2010, pp. 1570-1577.

6. Hirschmuller H. Stereo processing by semi-global matching and mutual information, IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, Vol. 30, no. 2, pp. 328341.

7. Bleyer M., Gelautz M. Simple But Effective Tree Structures for Dynamic Programming-Based Stereo Matching, Int. Conf. on Computer Vision Theory and Applications (VISAPP), 2008, Vol. 2, pp. 415-422.

8. Yang Q. A Non-Local Cost Aggregation Method for Stereo Matching, Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2012, pp. 1402-1409.

9. Kruskal J. On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. of the American Math. Society, 1956, Vol. 7, no. 1, pp. 48-50.

10. Bleyer M., Rhemann C., Rother C. PatchMatch Stereo -Stereo Matching with Slanted Support Windows, Proc. of the British Machine Vision Conf. (BMVC), 2011, pp. 14.1-14.11.

11. Wang L., Yang R. Global stereo matching leveraged by sparse ground control points, Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 3033-3040.

12. Fischler M., Bolles R. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Transactions of ACM - Graphics and Image Proc. 1981, Vol. 24, pp. 381-395.

13. The KITTI Vision Benchmark Suite. URL: http://www. cvlibs.net/datasets/kitti/eval_stereo_flow.php?benchmark=stereo (дата обращения: 04.08.2012).

14. The Middlebury Stereo Dataset. URL: http://vision.midd-lebury.edu/stereo/ (дата обращения: 04.08.2012).

15. Harris C., Stephens M. A combined corner and edge detector, Proc. of the Fourth Alvey Vision Conf. 1988, pp. 147151.

16. Lowe D.G. Distinctive image features from scale-invariant keypoints, Int. Journ. of Computer Vision, 2004, Vol. 60, no. 2, pp. 91-110.

17. Tretiak E., Barinova O., Kohli P., Lempitsky V. Geometric image parsing in man-made environments, Int. Journ. of Computer Vision, 2012, Vol. 97, no. 3, pp. 305-321.

18. Delong A., Osokin A., Isack H., Boykov Y. Fast Approximate Energy Minimization with Label Costs, Int. Journ. of Computer Vision, 2012, Vol. 96, no. 1, pp. 1-27.

References

1. Scharstein D., Szeliski R., Int. Journ. of Computer Vision, 2002, Vol. 47, no. 1-3, pp. 7-42.

2. Hosni A., Bleyer M., Gelautz M., Rhemann C., Proc. of the 16th IEEE Int. Conf. on Image Processing (ICIP), 2009, pp. 2093-2096.

3. Hirschmuller H., Innocent P., Garibaldi J., Int. Journ. of Computer Vision, 2002, Vol. 47, no. 1-3, pp. 229-246.

4. Woodford O., Torr P., Reid I., Fitzgibbon A., IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, Vol. 31, no. 12, pp. 2115-2128.

5. Bleyer M., Rother C., Kohli P., Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2010, pp. 1570-1577.

6. Hirschmuller H., IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, Vol. 30, no. 2, pp. 328-341.

7. Bleyer M., Gelautz M., Int. Conf. on Computer Vision Theory and Applications (VISAPP), 2008, Vol. 2, pp. 415-422.

8. Yang Q., Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2012, pp. 1402-1409.

9. Kruskal J., Proc. of the American Math. Society, 1956, Vol. 7, no. 1, pp. 48-50.

10. Bleyer M., Rhemann C., Rother C., Proc. of the British Machine Vision Conf. (BMVC), 2011, pp. 14.1-14.11.

11. Wang L., Yang R., Proc. of IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2011, pp. 3033-3040.

12. Fischler M., Bolles R., Transactions of ACM — Graphics and Image Proc. 1981, Vol. 24, pp. 381-395.

13. The KITTI Vision Benchmark Suite, Available at: http://www.cvlibs.net/datasets/kitti/eval_stereo_flow.php?benchma rk=stereo (accessied 04 August 2012).

14. The Middlebury Stereo Dataset, Available at: http://visi-on.middlebury.edu/stereo/ (accessied 04 August 2012).

15. Harris C., Stephens M., Proc. of the Fourth Alvey Vision Conf. 1988, pp. 147-151.

16. Lowe D.G., Int. Journ. of Computer Vision, 2004, Vol. 60, no. 2, pp. 91-110.

17. Tretiak E., Barinova O., Kohli P., Lempitsky V., Int. Journ. of Computer Vision, 2012, Vol. 97, no. 3, pp. 305-321.

18. Delong A., Osokin A., Isack H., Boykov Y., Int. Journ. of Computer Vision, 2012, Vol. 96, no. 1, pp. 1-27.

УДК 519.816

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

М.В. Зенькович, ведущий инженер-программист (ЗАО «Литаформ», просп. Андропова, 22, г. Москва, 115533, Россия, zmv@itqform.ru);

Ю.Г. Древс, д.т.н., профессор

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

Ключевые слова: поддержка принятия решений, оценка эффективности инвестиционных проектов, имитационное моделирование, агрегативная система, формовочная линия.

PROBLEM OF DECISION-MAKING SUPPORT IN ESTIMATION OF INVESTMENT PROJECTS OF FOUNDRY PLANTS ON THE BASIS OF MOULDING LINES

Zenkovich M. V., Leading Engineer-programmer (JSC «Litaform», 22, Andropova Av., Moscow, 115533, Russia, zmv@litaform.ru);

Drevs Yu G., Ph.D., Professor (National Research Nuclear University MEPhI, 31, Kashirskoe highway, Moscow, 115409, Russia, ydrevs@ya.ru) Abstract. Methods and software enabling the estimation of efficiency and the comparisons of alternative designs of foundry plants on the basis of moulding lines are discussed. Problem of estimation of efficiency of investment projects of foundry plants on the basis of moulding lines is formulated in the terms of decision theory. Presented approach is based on the reduction of multicriterion problem of estimation of investment project to one-criterion problem. Set of outcomes of acceptable alternatives, set of vectorial estimations of outcomes, mapping of set of outcomes of acceptable alternatives to set of vectorial estimations of outcomes and structure of decision maker's preferences are described. Decision rule which allows to carry out required operation over the set of acceptable alternatives is formulated. Application of simulation for estimation of technological and constructional decisions, which was made during the plant design, is the central feature of presented approach. Model of moulding line refers to discrete-event class. Object-oriented approach was applied for designing of the model and programming language C++ for its implementation. Application of detailed simulation model of moulding line allows to carry out an accurate estimation of technological and constructional characteristics of involved projects. Presented