Team B3: 2D23D

This week I assisted Chakara for the mechanical components of the rotating platform. I helped pick up components of our platform setup and test that they work. Chakara has included a table of the list of parts for his status report so I will avoid repeating that information here. I tested the laser strip diode and it seemed to work with an input voltage between 3 to 5 volts. The laser strip seems to be a bit wider at closer ranges so we will have to put the laser at a good enough distance for the strip to still be bright but not to be so wide as to mess up our laser detection algorithm. The camera also seems to be of a good resolution when we tested it with Facetime on Chakara’s Macbook, and should be good enough for our project. If not, we have a bit under $200 for getting a better camera or laser if needed.

For the mechanical subsystem of our device (see the design report), we will require significant physical pieces to build both the frame, motor components, and holders of the camera and laser line. This week we have gotten access to a bin to store our physical components as we work on them (bin #17). We have also attended the Tech Spark session to prepare us for laser cutting (for a sheet gear) and 3D printing (for the axis gear). If we find that these gears wear down over usage, we may need to allocate an additional part of our remaining budget to buy metal gears.

I also looked into the gear components and will be looking to create the files necessary to laser cut our acrylic piece as well as create the gear piece to fit onto the stepper motor. Throughout spring break, I will be out of town and will not work extensively on the project, as planned in the Gantt chart. However, I will still aim to create the files for the gear piece and the acrylic. I will also start to assemble our testing database by finding free 3D models online that fit our requirements. After break, I will start writing code for the triangulation step as well as ICP and pairwise registration as described in our design report and presentation.

This week I helped work on the design review presentation and design document. I also did a good amount of research into different methods to get their tradeoffs that we discussed in the design review presentation. I helped create a 3D render of what our project would approximately look like and also helped construct the block diagrams and other visuals for the presentation. I did some research into PCL and its tradeoffs, as well as some metrics we could use for the metrics and validation slide. I mainly helped with the overall design review presentation such as coming up with risk factors and unknowns, fixing different visuals and the Gantt chart, etc. The main time sink was just doing a heavy amount of research into considering different scanning methods and sensors, since we settled on using a laser projection with a camera as our sensor and needed some metrics and data to justify this choice, which took a fair bit of effort to find good papers on since most scanning approaches just use digital cameras or depth cameras. This approach will definitely be more challenging than just using a packaged depth camera like the Intel RealSense SR305, but it may be able to provide higher accuracy, since a lot of depth cameras don’t give very specific accuracy numbers. 

I did some research into noise reduction and outlier removal as well this week. Point clouds obtained from 3D scanners with any methods, including laser projection, would regularly be contaminated with lots of noise and outliers. The first step for dealing with raw point cloud data obtained after conversion from laser projection to depth would be to discard outlier samples and denoise the data. Alex mentions removing points in the background and in the foreground on the turntable; this step would come after that where the point cloud is already created. There have been decades of research in denoising point cloud data, which include methods categorized as projecting points to estimated local surfaces, classifying points as outliers with statistical methods, coalescing patches of points with nonlocal means, or local smoothing using other input information, and so on. There are generally three types of outliers: sparse, isolated, and nonisolated. Sparse outliers have low local point density that are obvious erroneous measurements i.e. points that float outside of the rest of the data. Isolated outliers have high local point density but are separated from the rest of the point cloud, i.e. outlier clumps. Nonisolated outliers are the most tricky – they are outliers that are very close to the main point cloud and cannot be easily separated, akin to noise. To remove sparse and isolated outliers, we can use a method that looks at average distance to k-nearest neighbors, then removes that point based on a threshold defined in practice. Let the average distance of point p_i be defined as:

d_i = 1/k * sum(j=1 to k) dist(p_i, q_j)

where q_j is the jth nearest neighbor to point p_i. Then, the local density function of p_i is defined as follows: 

LD(p_i) = 1/k * sum(q_j in kNN(p_i)) exp(-dist(p_i, q_j) / d_i)

with d_i defined earlier. Now we can define the probability that a point belongs to an outlier: 

P_outlier (p_i) = 1 – LD(p_i)

We can then take this probability and if it is above a certain threshold (one paper I read uses P_outlier (p_i) > 0.1 * d_i as their threshold in practice which is dynamic based on d_i), then that point will be removed from the point cloud data (PCD). 

I am certain that the PCL (point cloud library) will have a wide range of functions available for noise reduction and outlier removal but this methodology seems easily implementable and robust. I can implement our own outlier removal method and compare with some open source options available as well looking at the results qualitatively to see how well it removes outlier points from the raw point cloud. I will also need to make sure that I tune the threshold for removing outliers, since archaeological objects tend to have more jagged edges and be more abrupt in shape, so we definitely don’t want to over-smooth the object and lose too much accuracy in the data; the goal should be to increase our accuracy to the ground truth model rather than trying to over-smooth to make something that “looks nicer”. 

My progress is mostly on track, but I will be aiming to start finding and constructing our validation database (my main task from the Gantt chart) and potentially 3D printing some of the ground truth models out, and also start writing and testing the code for filtering the sensor data such as noise reduction and outlier removal, experimenting with the PCL library. I will also look into triangulation using the PCL library as it is too complex and unnecessary for us to implement triangulation ourselves in the scope of the project.

This week, our team mainly worked together on preparing for the Design Presentation and writing the Design Document. 

Currently, the most significant risk that could jeopardize the success of the project is that we ordered our project components later than we planned to. This means that the parts would come later than expected and we would have less time to assemble all the parts together and test the components we ordered. This is a risk factor because we need to make sure that the Line Laser Diode we ordered has enough light intensity and our camera can capture that for our algorithm to work. If not, we would need to order a different laser. Another consequence here is that we are uncertain of the step driver and NVIDIA Jetson integration, so getting the component later means we get to test them together even later. We are managing these risks by adjusting our schedule. We moved up other tasks that could be worked on without the project components such as finding ground-truth, writing code to filter and triangulate point cloud data, and writing testing benchmarks to work on while we are waiting for the project components. 

There were no major changes made to the existing design of the system this week (we will be running with the design that comprises of a laser line projection combined with a camera to scan the object using a rotating platform).

This is the link to our updated schedule: https://docs.google.com/spreadsheets/d/1GGzn30sgRvBdlpad1TIZRK-Fq__RTBgIKN7kDVB3IlI/edit?usp=sharing

This week I have been practicing for the design review presentation, as well as working on the design review document. While we have figured out all of the components of our design prior to this week (the laser, the camera, and the algorithms to compute point clouds), many details needed to be ironed out.

Specifically, I worked out some of the math for the calibration procedures which must be done prior to scanning. First of all, intrinsic camera calibration must be done, which resolves constants related to the cameras lens and polynomial distortion that may have. This calibration helps us convert between pixel space and camera space. Secondly, extrinsic camera calibration must be done, which solves a system of linear equations to find the translation and rotation matrices for the transformation between camera space and world space. This system is made non-singular by having sufficiently many known mappings between camera space and world space (specific identifiable points on the turntable). Thirdly, the axis of rotation for the turntable must be computed in a similar manner to the extrinsic camera parameters. Finally, the plane of the laser line in world space must be computed, which requires the same techniques used in the other calibration steps, but since the laser line is not directly on the turntable, an additional known calibration object must be placed on the turntable.

The method for transformation between pixel space and world space is given by the following equation:

λu=K(Rp+T)

Where K and λ are computed during intrinsic camera calibration, and R and T are computed during extrinsic camera calibration. We can then map the pixel where the center of the turntable is to a point in world space, q, with a fixed z=0, and a rotational direction of +z (relative to the camera perspective).

To calibrate the plane of the laser line, we first need image laser detection. We will compute this by first applying two filters to the image:

1. A filter that intensifies pixels with color similar to the laser’s light frequency
2. A horizontal gaussian filter

Then, for each row, we find the center of the gaussian distribution and that is the horizontal position of the laser line. If no intensity above a threshold is found, then that row does not contain the laser. Note that this solution prevents detection of multiple laser points within a single row, but this case will only occur with high surface curvature and can be resolved by our single-object multiple-scan procedure.

Laser plane calibration then happens by having a flat object on the turntable to allow for image laser detection. This allows us to find a set of points which are on the plane, which we can use to then solve a linear equation to compute the A, B, C, and D parameters of the plane of the laser line in world space. There is a slight caveat here. Since the laser itself is not changing angle or position, the points we capture do not identify a single plane, but rather a pencil of planes. To accommodate this, we will rotate the known calibration object (a checkerboard) to provide a set of non-collinear points. These points will allow us to solve the linear equation.

Calibration parameters will be solved for in the least-squared error sense, to match our recorded points. Global optimization will then be applied to all the parameters to reduce reconstruction error. Our implementation of optimization will probably consist of linear regression.

Once calibration is done, to generate 3D point cloud data we simply perform ray-plane intersection between the ray originating at the world space of the pixel with the laser line away from the camera position towards the laser plane in world space. This point is in world space coordinates, so it must be un-rotated around the rotational axis to get the corresponding point in object space. All such points are computed and aggregated together to form a point cloud. Multiple point clouds can then be combined using pairwise registration, which we will implement using the Iterative Closest Points (ICP) algorithm.

The ICP algorithm aims to compute the transformation between two point clouds by finding matching points between the point clouds. It is an iterative process that may converge on local minima, so it is important that multiple scans are not sufficiently far from each other in terms of angles.

Background points during 3D scanning can be removed if they fall under an intensity threshold in the laser-filtered image, and unrelated foreground points (such as points on the turntable) can be removed by filtering out points with a z coordinate of close to or less than 0.

Since we will not be getting our parts for a while, our next steps are to find ground truth models with which to test, and begin writing our verification code to test similarity between our mesh and the ground-truth. To avoid risk related to project schedule timing (and the lack of significant remaining time), I will be writing the initial prototyping code next week so that once the parts arrive we can begin early testing.

With our updated requirements (an effective Engineering Change Order (ECO) made by our group in a manner parallel to that of the manner by which P6 perhaps accomplished the same goals, with plenty of paper work and cross-team collaboration required), we began the week ready to once and for all tackle the issue that has plagued us for the last two weeks: choosing a specific sensor. From the quantitative results we require for our device to produce, we worked forward in a constructive logical manner to determine which components would be required. Our final project requirements are below:

Requirements

• Accuracy
• • • • 90% of non-occluded points must be within 2% of the longest axis of the object to the ground truth model points.
      • 100% of non-occluded points must be within 5% of the longest axis of the object to the ground truth model points.
• Portability
• • • • Weighs less than 7kg (weight limit of carry-on baggage)
• Usability
• • • • Input object size is 5cm to 30cm along longest axis
        • Weight Limit: using baked clay as example – 0.002kg/cm^3 * (25^3 – 23^3) = 6.91 kg
        • average pottery pot thickness is 0.6-0.9cm – round to 1cm
        • for plastic the weight limit is 4.3kg
        • Our weight limit will be 7kg – round up of the baked clay
      • Output Format
      • All-in-one Device
        • No complex setup needed
• Time Efficiency
• • • • Less than one minute (time to reset the device to scan a new object)
• Affordability
• • • Costs less than $600

Note that the only requirement significantly changed has been that of accuracy. The use case of our device is to be able to capture the 3D geometric data of arbitrary small-scale archeological objects reasonably quickly. We envision groups of gloved explorers with sacks of ancient goodies, wanting to be able to document all of their research in a database of 3D-printable and mixed-reality applicable triangular meshes. To perform scans, they will insert an object into the device, press the scan button, and wait a bit before continuing to the next object. They should not need to be tech experts, nor should they need to already have powerful computers or networks to assist with the computation required. In addition to this, the resulting models should be seen by these archeologists as true to the real thing, so we have adjusted our static accuracy model with a dynamic one, whose accuracy is based on the dimensions of the object to be scanned. We have chosen the 2% accuracy requirement for 90% of points by considering qualitative observational results that may be seen when comparing original objects to their reconstructed meshes. Since archeologists do not have a formal standard by which to assess the correctness of 3D models created for their objects, we took this freedom to use our intuition. 2% of a 5cm object is 1mm, and 2% of a 30cm object is 6mm, both of which seem reasonable to us given what those differences mean for objects of those respective sizes.

We have made an effort this week using these requirements to perform geometric calculations to compute the spatial frequency of our data collection, and in turn the number of points of data that must be collected. From this, we have narrowed down the requirements of our sensor, and began eliminating possibilities. Finally, from those possibilities that remained, our team has chosen a specific sensor to start with: a dual stripe-based depth sensor utilizing a CCD camera. In order to mitigate risk potentially imposed by errors of the sensor, our fallback plan is to add an additional sensor to act as an aid in correcting systematic errors, such as a commercial depth sensor. Since the sensor only costs under $20 + $20 + ~$80 = ~$100 (depending on our choice of camera, it may be more expensive), much less than our project budget, we will be able to add an error-correcting sensor should the need arise for our project.

From the behavior of this sensor, which is a laser triangulation depth sensor, we have derived the various other components of our design, including algorithmic specifications, as well as mechanical components required to capture the intended data (whose specifications have been computed during choosing of the sensor). We have chosen a specific computational device for our project, as well as most of the technologies that will be used. All of these details are covered in our respective status updates (Alex for data specifications and sensor elimination, Jeremy for determining algorithms and technology for computation, Chakara for designing and diagramming mechanical components). The board we have chosen is the NVIDIA Jetson Nano Developer Kit ($90), an on-the-edge computing device with a capable, programmable GPGPU. We will utilize our knowledge of parallel computer architectures to be able to implement the algorithmic components on the GPU with the CUDA library, in an effort to surpass our speed requirement. We will implement initial software utilizing software such as Python and Matlab, then transition into our optimized C++ GPU code to meet the timing requirements as the need arises.

Since we are behind in choosing our sensor and thus ordering components for our project, we have been designing all of the other components in parallel. Regardless of the specific sensor chosen, the mechanical components and the algorithmic pipeline would be similar, albeit with slightly different specifications. This parallel work has allowed us to have a completed design at the time we have chosen the specific sensor. However, much of our algorithmic work was based on camera-based approaches, and since we are utilizing a laser depth sensor, we will not need to perform the first few stages of the pipeline we proposed last week. We still need some additional time to flesh out our approach to translate between camera space coordinates and world space coordinates, as well as algorithms for calibration and error correction based on two lasers. Because of this additional time we are extending the algorithm research portion of our Gantt chart.

The main risk we have right now is that since we are designing our own sensors, it is possible that our sensors might not meet our accuracy requirements. Thus, we might need to have a noise reduction algorithm or might potentially have to buy a second sensor to supplement our sensors. 

Our design changed a little by using a laser instead of a depth-camera. This changes our pipeline a little but doesn’t affect the mechanical design and overall algorithm. 

Below is the link to our updated schedule. 

https://docs.google.com/spreadsheets/d/1GGzn30sgRvBdlpad1TIZRK-Fq__RTBgIKN7kDVB3IlI/edit?usp=sharing