Assigned Project Topics for 2012-2013 Spring Semestr

Consistent Partitioning and Skeletonization of 3D Mesh Models

Tolga Dispinar and Hasan Balci

 The students develop a program that partitions a given mesh model. They will implement the algorithm introduced in the [1], in which they propose a new technique for partitioning that produces consistent partitioning for different poses of an object. To achieve the consistency, they introduce a new measure called shape diameter function (SDF) which remains oblivious to pose changes of the same object. The SDF is a scalar function defined over mesh surface and it expresses a measure for the diameter of the object's volume for each point in the surface.

Then to partition the mesh model, they exploit the fact that points belonging to a specific part of the object have similiar SDF values. Thus after calculating SDF values, their algorithm consist of two step. First step is soft-clustering of mesh faces to k clusters based on their SDF values. The result of this step for each face is a vector of length k which shows the probability to assign that face to clusters. In second step they try to smooth the boundaries between parts using k-way graph-cut.

References

[1] Lior Shapira, Ariel Shamir, Daniel Cohen-Or, Consistent Mesh Partitioning and Skeletonisation using the Shape Diameter Function, Visual Computer, 2008.

A Voronoi-Based Cell Segmentation Method for Michigan Cancer Foundation-7 (MCF-7) Cell Lines

Can Fahrettin Koyuncu and Murat Acar

Cell image segmentation is an ill-posed problem that needs to be undertaken by means of cutting-edge methods. Biomedical-image processing especially in cancer cell line images is of crucial importance, which necessitates the utilization of efficient methods for segmenting cell images. The ultimate purpose of this project is to propose an efficient method for segmenting these kinds of cell images. We will perform cell segmentation on the images of MCF-7, which is the acronym of Michigan Cancer Foundation-7, breast cancer cell lines. The most distinctive features of these cells are the small rounded body contained in the nucleus of a cell and the brightness of regular halo artifacts surrounding the periphery of the cell membranes.

First, we will apply k-means clustering on the features of RGB color model, and take the darkest group, which corresponds to the dark regions within the cell. Then, we will try to model these dark regions as a Voronoi diagram in order to obtain more robust segmentation with a combination of cell features. We will validate the efficacy of the proposed segmentation method with a well-grounded implementation and comprehensive experiments.

Art Gallery Problem – Guards Have a Vision of 180°

Begum Genc and Mecit Sari

Art gallery problem emerges from a real world problem in which the aim is to guard an art gallery with a number of stationary guards. It is proposed by Klee and Vásek Chvátal in 1973. The original problem they proposed is: What is the minimum number of guards to protect the floor if each guard can see in every direction?

We are going to modify this problem as: How many stationary guards are needed to guard an art gallery if each guard has a vision of 180°? The important points in this problem are:

The problem is equivalent to illumination problem. Illumination problem is searching for the minimum number of light sources in order to fully illuminate a room.

The gallery in the problem can be formulated as a simple polygon with n vertices. Since it is a simple polygon, the room has a flat shape with straight and non-intersecting walls. The original problem has a number of solutions. Chvátal [1] states that guards are needed in order to guard the gallery. Another theorem by Fisk [2] uses triangulation and 3-coloring problem to solve the problem. As a result, he states that at most guards are needed. Those solutions always place the guards on the vertices in other words corners of the gallery. There are different approaches for placing the guards. One of those approaches is placing the guards on the vertices as Chvátal and Fisk used. The other approaches include point guards in which we can place the guard anywhere in the polygon and edge guards. Edge guards have a similar logic to the vertex guards; the guards can only be placed on the edges. The guards will be placed on the edges or the extension of the edges in the proposed project because the rotations will cause a big problem and edges have the perfect geometry for a visibility area of 180°.

The students will develop an interface that will provide the functionality to move the walls between the rooms (with mouse) and arrange the guards interactively according to the new floor plan.

References

[1] V. Chvátal, A Combinatorial Theorem in Plane Geometry, J. Combin. Theory Ser. B 18 (1975) 39-41.

[2] S. Fisk, A Short Proof of Chvátal's Watchman Theorem, J. Combin. Theory Ser. B 24 (1978) 374.

Simulation of Greedy Perimeter Stateless Routing for Wireless Networks by Karp and Kung

Amir Rahimzadeh Ilkhechi

 In this project, a simulation for an algorithm proposed for routing in wireless environments will be implemented.

Algorithm Specifications

In greedy forwarding protocol, it is assumed that the location of destination is known. Also, as nodes know their own position, a node can easily learn the position of its neighbors. Simple beaconing mechanism is used to receive this information from the neighbors. GPSR uses proactive beaconing mechanism. It embeds the location information to the data packets (piggybacking) so a node x that can decode a particular data packet can update the positions of current sender and receiver if any of them is the neighbor of x. By using locations of destination and the neighbors, greedy forwarding sends the packet to the node among neighbors that is closer to the destination. If there are several neighbors that are closer to the destination than the current node, the one that is closest is selected. Figure 1, provides a good example for this protocol. In this case as y is closer to the destination and as it is the closest one, x forwards the packet to the node y.

If there are not any nodes that are closer to the destination than the current node, the packet is forwarded using planar perimeters. Note that even if there is no closer node to the the destination, a neighbor node may have a path that to a node that is closer to the destination. This condition is depicted in Figure 2.

The Right-Hand Rule: Perimeters

In a case like Figure 2, a destination can be reached by routing around the void if the destination -hand rule states that, when arriving a node x from node y, the next edge traversed is the next one sequentially counterclock-wise exterior region of a closed polygonal region (a face) is traversed using this rule. Authors use this explained below.) to move around voids in an intention to bring the message closer to the destination.

Planarized Graphs

Authors point are crossing edges. In their previous work, authors removed crossing edges blindly. However, they state that, this methodology may cause partitions throughout the graph. Hence, they use two existing methods to remove crossing edges and these methods guarantee that they will not cause any extra partitions in the graph. These two methods are summarized below:

Relative Neighbourhood Graph

An edge (u,v) exists between vertices u and v if the distance between them d(u; v), is less than or equal to the distance between every other vertex w, and whichever of u and v is farther from w. This condition can be seen in Figure 3.

Gabriel Graph

An edge (u,v) exists between vertices u and v if no other vertex w present within the circle whose diameter uv. This condition can be seen in Figure 4. Note that in both algorithms an edge is removed only if there exists a third node between them. Hence, if an edge is removed it is guaranteed that there will be an alternative path. As a result, it is guaranteed that these two algorithms do not partition a graph.

Combining Greedy and Planar Perimeters

This is the actual process of GPSR.When a node generates or receives a packet do be delivered whether d is in the communication range. If so, it forwards the packet to the destination. If not, tforward the packet in greedy fashion. As described before, in greedy forwarding if message holder has neighbors that are spatially closer to the destination, the message is forwarded to the neighbor that is closest. In Greedy forwarding, the original graph with all edges (including crossing edges) is used. If there are no neighbors that are closer to the destination, the perimeter forwarding is used. This routing can be explained better on an example. Such an example condition is depicted at Figure 5. Assume node x is performing perimeter forwarding by aiming to send the message to destination D.

First x draws a line between ure). After that, by applying a right hand rule at the xD line, it d the message. When the message is forwarded, it is on an edge of a face. Hereafter, the right hand rule is applied successively until an edge that crosses the xD is encountered. When such an edge is found, the message is not forwarded through that edge. Rather, the message is forwarded to face that is in the direction of xD. In other words, when an edge that coresses xD line is found, it is not forwarded to it, but a new face. Note that the closed polygonal regions were named faces. The presedure above is applied until one of the following two orwarding method is switched to greedy, if the distance of any node to destination along the forwarding path is closer than the distance between x and D. Additionally, the forwarding operations is stopped and the message is dropped if a loop is encountered during forwarding. The edges that are traversed are stored in messages. Hence, if same edge is encountered twice, this can be detected easily. Loops normally occur if the destination is disconnected from the message holder. In this case, at some point, no edge that crosses the x D line can be found. As a result, the message cannot be forwarded to a new face and the right hand rule is applied successively. Thus, the message travels all around the closedpolygonal region and creates a loop.

References [1] B. Karp and H. T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” in International Conference on Mobile Computing and Networking, 2000, pp. 243–254.

Procedurally-generated 2D Map Generation for Computer Games

Arhan Bakan

 The project will focus on generating procedural maps for 2D (top-down camera, xz-plane) computer games. The main goal is to code a “dungeon generator”. The plan is to create a program that will;
  1. Use 2D Voronoi Diagrams to make polygonal regions, which can be used as cave structures.
  2. Use basic geometric shapes and irregular geometric shapes to generate more rooms.
  3. Use Delaunay Triangulation to connect rooms with each other using hallways.
  4. Allow the user to choose the type of next room to be created. Give the user the option to set up random points for creating Voronoi diagrams. Alternatively, the user can give the program the order to create an entire dungeon randomly, by giving parameters like min-max distance between two rooms, number of rooms, categorizing room types from “common” to “rare”, etc.
  5. Contain an easy-to-use UI.
  6. Have the option to “gridify” the final product.

The software will be used in the following way:

  1. The first room that gets placed will be placed in the middle of the map, the second will be placed next to it in a direction that fits best, the third will try to find the next suitable spot, and so on until the dimensions of the map are exceeded. The user will have no control over the placement of rooms.
  2. After the map is finished, hallways will be carved between rooms using Delaunay Triangulation.
  3. Finally, the user is given the option to gridify the map, causing all of the rooms to transform into their blocky versions.

An Efficient Data Structure for Overlapping Multi-scale Regions

Acar Erdinc

 The project is related to remotely sensed imagery in the domain of pattern recognition. It involves very large images in multi channels and the regions generated from these images in different scales and from those different channels separately. This results in very huge data. Working on a very huge data like these requires optimization. Because the datasets are huge in size and frequent accesses to this data is required, the data should be stored in an efficient data structure so that the cost of querying the data structure should be as low as possible. It is very important to mention that the regions have spatial information, which is basically the most valuable information, and they mostly overlap in different scales or in different channels.

The data structure that is going to be used should store spatial, scale and channel information and simlify querying by them. It should also include information regarding the inclusion of different regions so that if a region is completely included in a larger region from a different scale, it should be treated as a child of the larger region. Or, in other words, a constructing element of the larger region.

Fair Partitioning of Convex Polygons

Mehmet Faruk Ongun

 Define a fair partitioning of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. If all the resulting pieces are convex, call it a fair convex partitioning. Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?

If the answer is "Not always," how does one decide the possibility of such a partitioning for a given polygon and a given n? And if a fair convex partition exists for a specific polygon, how does one find a fair partitioning that minimizes the total length of the cut segments, or minimizes the sum of the perimeters of the pieces?

And finally, what could one say about higher dimensional analogs of this question?

Computation and Visualization of 3D Convex Hulls

Tunc Gultekin and Salim Arslan

 The project consists of two stages: first, for a given set of points, either entered via a graphical user interface or read from a batch file, to compute the convex hull; and second, demonstrate the convex hull in a 3D fashion. The motivation is to develop a user-friendly application, in which every operation is handled by user interface on the fly. This tool would be very useful to teach 3D convex hull construction and, from the user point of view, makes it easier to understand convex hulls in 3D environment. In the implementation, Java will be used for computing the convex hull and Java 3D API for visualization.

Minimum Weight Triangulation of a Polygon

Ihsan Mert Ozcelik and Mustafa Ozan Karsavuran

 The minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

The students will implement an algorithm that requires polynomial time to find the minimum weight triangulation of a polygon.

References

[1] Minimum Weight Triangulation, http://en.wikipedia.org/wiki/Minimum-weight_triangulation

[2] Aichholzer, Oswin; Aurenhammer, Franz; Hackl, Thomas; Speckmann, Bettina (2009), "On minimum weight pseudo-triangulations", Computational Geometry Theory and Applications 42 (6-7): 627–631,

Project Requirements

Ugur Gudukbay
March 13, Monday, 10:30:30 EET 2013