The Kalman Filter Hole Filler

By Russell Palmiter

 

Project Description

 

The purpose of my project was to explore the use of a Kalman Filter as a way to predict the shape of missing geometry from an unstructured mesh. This process in general is referred to as hole filling, and to my knowledge this is the first attempt at using a Kalman Filter for that purpose.

 

 

Background Information

 

Hole Filling

 

Hole filling is a really important process in computer graphics because so many other modeling algorithms depend on the manifoldness of a mesh. And besides being a requirement for other algorithms, holes are generally visually displeasing (with exceptions of course) in a model, so being able to accurately fill a hole is a desirable ability.

 

Holes in a mesh can come from various places and are often introduced as an undesirable side affect of another process. Two processes for which the creation or holes is common are that of data acquisition and mesh simplification. Data acquisition is frequently done by modeling tangible items using tools like laser rangefinders. This is done from several vantage points, with the resulting range images integrated into a final model. However, due to many factors including surface reflectance, occlusions, and accessibility limitations, certain areas of the scenes are frequently not fully sampled, leading to holes in the mesh.

 

Kalman Filter

 

The Kalman Filter is a technique for calculating the optimum estimates of process variables in the presence of noise. It works through a process of simultaneous recursion formulas that predict and correct estimates continually over the series of data points. The Kalman Filter is most frequently used to track a time-varying signal in the presence of noise, of which a natural application is digital signal processing. However, if you use the position of points in space as your variable (in the form of a series of discrete data points), and make a prediction for what your missing data points would likely be, it is possible to use a Kalman Filter to estimate what a series of missing geometry likely looked like (within some resemblance anyway).

 

 

 

 

 

Overview

 

Hole filling in general contains three major stages, which can be identified as follows. Please not that these stages are my subjective qualification for what I observed in other hole filling work.

 

Given an unstructured mesh:

 

  1. Find Holes

 

Find the holes by keeping track of the # of faces each edge is connected to, if you have a cycle of edges with only 1 face then those edges make up a hole.

 

A user defined threshold can be made present if one wants to prevent certain holes from being filled. A good heuristic for displeasure of hole is that of the number of edges in the whole. One could also use geometric area of the hole, or cumulative edge length (perimeter). Planarity of the hole is also another useful heuristic in determining which holes the user may want filled, and which he or she may not.

 

  1. Triangulate the Hole

 

This is the process of taking the polygonal hole and turning it into a set of triangles. creating triangles

 

  1. Refine Triangulation

 

This is what my project focused on. This step helps to refine the triangulation and make the geometry created more accurate and visually appealing. More information can be found in the following process section.

 

 

Process

 

To keep the problem as simple as possible while allowing me to explore more thoroughly the use of a Kalman Filter, I took many short cuts in the hole filling process. For example, I didn’t find the hole automatically; I simply had the user define a section of the mesh they wanted to be considered a hole. Then, as a best estimate for the missing area, I simply linearly interpolated between the edges of the missing geometry. I also used a limited number of uniformly distributes sample points.

 

The process in its entirety is really that of an application of a Kalman Filter, for which I will refer you to someone who can explain it better, Greg Walsh [see An Introduction to the Kalman Filter].

 

I’ve outlined the process graphically and presented it in both 2D and 3D below.

 

In 2D

 

I’ve done the process in 2D because it is usefully a demonstration and visualization tool.

 

 

Here is the original geometry (from what would otherwise be a mesh).

 

Original Geometry.

 

 

Here is the original geometry with a section of the graph missing data. The missing data has been linearly interpolated in place and this linearly interpolated data will later be used as an estimate for the Kalman Filter.

 

Missing Geometry aka Hole

(Note: Linear interpolation was used a an initial estimate for the area over the hole)

 

 

 

This next graph shows the Kalman Filter’s prediction for where the geometry should be. The section that corresponds to the hole will be put in place of the linear interpolation.

 

Kalman Filtered Geometry

 

 

The magenta line is the reconstructed geometry using the kalman filter’s estimate in place of the missing data.

 

 

 

 

In 3D

 

Here is the same process again, except in 3D.

The Original Geometry

 

 

Geometry with a Hole

(Please Note: Once again the hole was filled via linear interpolation)

 

This comparison shows the linearly interpolated hole (this is the geometry that’s fed into the filter) vs the Kalman Filtered geometry. Notice the smoothing effect which makes this method also serve as a good geometry smoother.

 

 

Here is the results of the 3D Kalman Filter. Notice the dip in the geometry that wasn’t present in the linearly interpolated fill for the hole. The dip is certainly not perfectly aligned with the original, but it is present which means the Kalman Filter must be doing an alright job.

 

 

 

 

 

 

 

 

 

Presentation

 

My presentation was short and sweet and focused around me speaking to the demo, but in the case that you missed something on one of my slides or weren’t able to attend my demo; I have included the slides here for your viewing pleasure.

 

Results

 

The results for this project have not been measured in a formal way, although I think you will agree that they do show visually appealing results. In completing this project, I have found that the Kalman Filter can not only be used for hole filling, but would also make a very nice geometric smoother.

 

 

 

 

Final Thoughts

 

This project was a great learning experience for me and I’m glad I chose it. I don’t know that I came up with the best hole filler. I think I came up with what looks to be a pretty good geometry smoother more than anything. I think I did prove that it’s possible to fill geometry using this method, and I think that’s quite an accomplishment. In fact, I think applying a Kalman Filter at all is quite an accomplishment. I’m pleased to see that it did an okay job too. I would love a metric to allow me to measure how well I predicted the geometry and the ability to compare it to other methods (like simple linear interpolation). Then I would run that on several different methods with randomly generated and lost geometry and report percentages of improvement.

 

 

Future Work

 

Fully implement the hole filling process, from discovering the hole, to triangulating over the hole, to then refining the triangulation.

 

Use a better estimate for the initial for the missing geometry. Perhaps a more current hole filling method. This would help my Kalman Filter considerable, and with their power combined, there would be no stopping them.

 

Use the Kalman Filter to predict/fill other attributes as well. This should be a relatively simple task for the Kalman Filter, but might require adaptations. Example attributes one might like to predict for the hole are texture data and normal data (as well as many others).

 

Use a heuristic to measure how close the reconstructed geometry is to the original. This could then be used a measure of quality for the hole filler and adjustments and tweaks could be made to the parameters of the Kalman Filter. A good heuristic to use would be the quadric geometric error metric (quadric error metric or qem).

 

Implement the project in C++.

 

 

References

 

Hole Filling

 

http://www.cs.utah.edu/research/techreports/2004/pdf/UUCS-04-019.pdf

http://www.cs.sunysb.edu/~jianning/Jianning_Files/Sib03.pdf

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1240986

http://www.geom.uiuc.edu/docs/forum/hoops_links/khoops.html

 

Kalman Filter

 

http://www.cs.unc.edu/~welch/kalman/

http://en.wikipedia.org/wiki/Kalman_filter

 

Matlab

 

http://www.mathworks.com/academia/student_center/tutorials/launchpad.html

http://www.glue.umd.edu/~nsw/ench250/primer.htm#sec14

http://www.math.utah.edu/lab/ms/matlab/matlab.html

http://www.mit.edu/people/abbe/matlab/main.html

 

 

 

 

[A word document of the material covered by this webpage can be found here]