理工学研究科Graduate School of Science and Engineering
PRI500X3（情報学基礎 / Principles of informatics 500）計算幾何学特論Computational Geometry
古賀 久志Hisashi KOGA
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 理工学研究科Graduate School of Science and Engineering |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | YB026 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 火1/Tue.1 |
| 科目種別Class Type | |
| キャンパスCampus | 小金井 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory | 応用情報工学専攻 |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
Course outline:
The students will learn computational geometry which serves as a theoretical foundation of computer graphics, image processing and geographical information systems. This class explains various standard algorithms in computational geometry with their application areas. Because pattern recognition is one of the application areas, this class refers to Support Vector Machine which is well-known as a pattern classifier.
Learning Objectives:
1. To understand the application areas of computational geometry.
2. To learn standard algorithmic techniques in computational geometry, so that you may implement them as computer programs.
This lecture chooses famous problems in computational geometry and introduces known algorithms to solve them. In order to understand these algorithms well, students will implement them with C++ in practice. Here, at the same time, students will learn how to develop computer programs by making use of software packages like OpenCV.
Learning activities outside of classroom:
Because students are supposed to write programs in C++ in this class, I recommend you to study this programming language in advance. Ideally, the students are expected to get familiar with one of the next two software development environments, i.e., g++ or MS Visual Studio.
Grading Criteria:
The grade of this class is decided from the two elements:
1. (60%) Several reports assigned after some of the lectures which examine how well you understand the contents of them. Sometimes, you need to complete some simple programming task.
2. (40%) The end-term report: Students are mainly required to implement several programs in C++.
授業で使用する言語Default language used in class
日本語 / Japanese
授業の概要と目的（何を学ぶか）Outline and objectives
コンピュータグラフィックス・画像処理・地理情報処理の基礎理論となる計算幾何学を学ぶ。計算幾何学の様々な基本アルゴリズムを教授し、さらに、それらがどのような応用分野で利用されるのかも紹介する。応用分野にはパターン認識も含まれており、代表的なパターン分類器であるSupport Vector Machineについても学ぶ。
到達目標Goal
計算幾何学がどのような応用領域で使われるのかをまず理解し、主要なアルゴリズム設計方法を習得して実装までできるようになることを目標とする。
本講義は、計算幾何学の代表的な問題を取り上げ、それぞれの問題に対するアルゴリズムを紹介する形式で進行する。その過程で、個別の問題に依らない計算幾何学ならではの普遍的なアルゴリズム設計手法を学習する。さらに、実際にアルゴリズムをプログラム実装し、学んだアルゴリズム設計法を確実に習得する。一方で、OpenCVに用意されたライブラリを使ったアルゴリズム実装も経験し、既存ソフトウェアパッケージを使ったプログラム開発の訓練をする。
この授業を履修することで学部等のディプロマポリシーに示されたどの能力を習得することができるか（該当授業科目と学位授与方針に明示された学習成果との関連）Which item of the diploma policy will be obtained by taking this class?
ディプロマポリシーのうち、「DP1」「DP2」「DP3」に関連
授業で使用する言語Default language used in class
日本語 / Japanese
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
講義を中心した授業を行い、必要に応じて、アルゴリズムを実装する課題を出す。プログラミング課題は、C言語を熟知していることを前提とする。また、計算幾何学のアルゴリズムを簡単にライブラリとして使えるOpenCVも紹介する。講義での理解を深めるため、講義時間内に小テストを実施したり、講義後に小レポート課題を課したりする。小テスト、レポート課題に関しては模範回答を授業支援システムで示し、学生が自分の間違いに気付けるようにする。
授業の開講形態は、zoomを利用したリアルタイム開講を想定している。
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
なし / No
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：オンライン/online
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[オンライン/online]：計算幾何学とは
計算幾何学とは何かを紹介する。また、幾何学を計算機で取り扱うことの困難さを理解する。授業理解に必要な平面幾何学についても言及する。
第2回[オンライン/online]：計算幾何学で使用するデータ構造
本講義の理解に必要な基本データ構造（スタック、キューなど）を復習する。本回は学部の授業の復習。
第3回[未定/undecided]：多線分の交差判定
計算幾何学特有のアルゴリズムである平面走査法について講義し、平面走査法ベースの多線分交差判定アルゴリズムを紹介する。
第4回[未定/undecided]：凸包(1) 逐次構成法
凸包とは何かを説明し、それを求めるアルゴリズムを紹介する。計算幾何学における代表アルゴリズムである逐次構成法を説明する。
第5回[オンライン/online]：凸包(2) 分割統治法
凸包を計算する別のアルゴリズムを紹介する。その際、計算幾何学における代表アルゴリズムである分割統治法を説明する。
第6回[オンライン/online]：ボロノイ図
ボロノイ図とは何かを紹介し、それを求めるアルゴリズムを講義する。
第7回[オンライン/online]：ドロネー三角形分割
ボロノイ図の双対データ構造であるドロネー三角形分割について講義する。
第8回[オンライン/online]：OpenCVプログラミングの環境構築
オープンソースのコンピュータビジョンライブラリであるOpenCVを紹介する。実際にノートパソコン上にOpenCVを使える環境を構築する。
第9回[オンライン/online]：施設配置問題
施設配置問題を題材としてボロノイ図の拡張である重心ボロノイ図について勉強する。また、施設配置問題を単純化したクラスタリングも取り扱う。
第10回[オンライン/online]：OpenCVによる画像処理入門
画像は画素集合であるが、OpenCVでどう画素集合を保持しているかを解説する。画素値をプログラムで修正する方法も紹介する。
第11回[オンライン/online]：アレンジメント
複数個の直線による平面分割のことをアレンジメントと呼ぶ。アレンメントに関して成り立つ性質を理解する。
第12回[オンライン/online]：クラスタリングアルゴリズムのプログラム実装
OpenCVの画像処理ライブラリを使い、k-meansクラスタリング法をプログラムで実装する。
第13回[オンライン/online]：パターン認識入門
パターン認識が多次元ベクトルの分類問題であることを理解し、基本的ななパターン認識アルゴリズムについて学ぶ。
第14回[オンライン/online]：OpenCVを使ったパターン認識プログラミング
OpenCVを使ってC++でパターン認識プログラムを実装する方法を学ぶ。さらに認識精度の算出方法も身につける。
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
【本授業の準備・復習時間は、各４時間を標準とします。】
アルゴリズムを実現するための手段を持っていなければ、この授業の効果を十分認識することは困難であるため、プログラミングの能力を向上させておくこと。とくに、OpenCVのプログラミングはC++で行うので、C++について勉強しておくことが望ましい。さらに、Visual Studioあるいはg++を使ってプログラム開発を行うので、この開発環境に事前に慣れておくことをお勧めする。
テキスト（教科書）Textbooks
なし
参考書References
- 計算幾何学 (数理工学ライブラリー), 朝倉書店, 杉原 厚吉[著]
- 計算幾何学入門―幾何アルゴリズムとその応用, 森北出版，譚 学厚, 平田 富夫 (著)
成績評価の方法と基準Grading criteria
以下の２つを総合して成績を評価する。
-学期末レポート課題点40％: 主にOpenCVを使ってプログラミング実装する課題を出す。
-授業時に実施するレポート課題60％： こちらは以前は講義内小テストとして実施していた内容である。オンライン授業では実施が困難なのでレポート課題に変更した。簡単なプログラミング課題も出題することがある。
学生の意見等からの気づきChanges following student comments
授業内の小テスト（今年度はレポート課題）は、講義内容の理解にとても有用なので、実施回数を増やす。
学生が準備すべき機器他Equipment student needs to prepare
各自持参のパソコンを使ってOpenCVのプログラミング環境を構築する。配布資料は授業支援システムを使って配布する。WindowsパソコンであればVisual Studioを開発環境として利用する。MacパソコンやLinuxパソコンであれば、g++で開発することになる。
その他の重要事項Others
小テスト（今年度はレポート課題）を通じて授業の理解状況を測る。その結果に応じてシラバスより授業速度を下げる可能性がある。