Category Archives: Thesis

Point Cloud Based Room Reconstruction

Download PDF on request.

Pipeline for Point Cloud Processing focused on Room Reconstruction

Scanning and modeling the interior rooms and spaces are important topics in Computer Vision. The main idea is to be able to capture and analyze the geometry of these interior environments.

Despite the considerable amount of work put in indoor reconstruction over the past years, all implementations suffer from various limitation and we still have yet to ?nd a method that will work in any scenario, in our approach we will focus in encoding points to reduce the space taken by point cloud on the disk as well as introducing a 3D meshing techniques that add coherence and readability to the point cloud. This is why we suggest the following approach.

When scanning a closed room, important/main features are the walls; it would be interesting to detect (and compress) the walls, floor and ceiling. Walls, floor and ceiling bound the room and have a high probability to represent high-density of points.

It is relevant to attempt to detect the main planar component in order to determine the boundaries of the point cloud and also we can, in a second step replace them with a more simplistic modelization, like a surface that only takes 4 vertices and 4 edges potentially replacing thousands of points. This will also allow us to filter the points scanned through windows that will be outside the rooms

We can code this 3D Mesh box as a graph since the point cloud might be not complete and suffer from occlusion. A graph-based architecture will make a strong starting point to start developing other features. But in order to do that we will need to detect all relevant planar component in our point cloud, this time we will initiates the segmentation with a region growing method in order to avoid the issue detected in Figure 7, insuring each plane resulting from the plane segmentation is linked to exactly one main planar component fed into the graph approach. Our graph structure is kept to the most simplistic entities so that it can be applied to a wild variety of scenarios (faces for the planes, edges are intersections of two planes, and corners/vertices are intersections of 3 planes.)

After detecting the walls and replacing them with simple faces, we will add them features lost by the plane approximation using height maps that are textures that model the height of the walls of each coordinate (X,Y). The operation opens up the domain of image processing and we are able to generate high-resolution versions of the room as well as low-resolution versions.

Reconstruction of Indoor Environments Using LiDAR and IMU

Today there is a trend towards reconstruction of 3D scenes with movement over time, in both image-based and point cloud based reconstruction systems. The main challenge in point cloud-based systems is the lack of data. Most of the existing data sets are made from 3D-reconstructed meshes, but the density of these constructions is unrealistic.

Point cloud from a fixed LIDAR scan (left) to a LIDAR sweep (right)

In order to do proper research into this field, it must be possible to generate real data sets of high-density point clouds. To deal with this challenge, we have been supplied with a VLP-16 laser scanner and a Tinkerforge IMU Brick 2.0. In our final setup, we position the IMU at the top center of the VLP-16 by utilizing a 3D printed mounting plate. This assembly is fastened to a tripod, in order to move the assembly about well-defined axes. Because most laser scanners acquire points sequentially, these devices do not have the same concept of frame as for images where all data are captured in the same instant. To deal with this issue we divide one scan, i.e., a 360◦ LiDAR sweep, into data packets and transform these data packets using the associated pose to global space. We compensate for mismatch in sampling frequency between the VLP-16 and the IMU by linear interpolation between the acquired orientations. We generate subsets of the environment by changing the laser scanner orientation in static positions and estimate the translation between static positions using point- to-plane ICP. The registration of these subsets is also done using point- to-plane ICP. We conclude that at subset level, our reconstruction system can reconstruct high-density point clouds of indoor environments with a precision that is mostly limited to the inherent uncertainties of the VLP- 16. We also conclude that the registration of several subsets obtained from different positions is able to preserve both visual appearance and reflective intensity of objects in the scene. Our reconstruction system can thus be utilized to generate real data sets of high-density point clouds.

Reducing Packet Loss in Real-Time Wireless Multicast Video Streams with Forward Error Correction

Download PDF.

Average packet loss without and with FEC

Wireless multicast suffers from severe packet loss due to interference and
lack of link layer retransmission. In this work, we investigate whether the
most recent Forward Error Correction (FEC) draft is suitable for realtime wireless multicast live streaming, with emphasis on three main points:
packet reduction effectivity, and latency and overhead impact. We design
and perform an experiment in which we simulate wireless packet loss in
multicast streams with a Gilbert model pattern of ≈ 16% random packet
loss. We check all FEC configurations (L and D values) within several
constraints: maximum 500 milliseconds repair window (latency impact),
66.67% overhead, and a maximum L value of 20. For all these L and D
values we stream the tractor sample three times, to avoid possible outliers
in the data. We show that packet loss reduction in the most recent FEC
draft is effective, at most reducing from ≈ 16% down to ≈ 1.02%. We
also show that low latency streaming can be conducted, but it requires a
minimum of 160 milliseconds additional latency for our stream file. The
overhead for such low latency can be as high as 66.67%.

Implementation of a virtual reality design review application using vision-based gesture recognition technology

Download PDF.

Choosing annotation visibility in the virtual design review application.

Classification societies date back to the second half of the 18th century, where marine insurers developed a system for independent technical assessment of the ships presented to them for insurance cover. Today, a major part of a classification society’s responsibilities is to review the designs of enormous maritime vessels. This usually involves working with big and complex 3D models and 3D tools, but without support to do many of the tasks required in a design review. As a consequence, the workflow is often just partially digital, and many important tasks, such as annotating or commentating on aspects of the models, are done on paper. DNV GL, the world’s largest maritime classification society, is interested in digitalizing this process more, and make it more interactive and efficient by utilizing an application that allows for virtual design review meetings in the 3D models. In these virtual design review meetings, the designer and reviewer could remotely interact, survey the model together, and annotate it instead of model-printouts. As the sense of scale is important in a 3D model review, virtual reality technology is deemed promising as it gives a unique sense of scale and a depth, which is hard to match by regular 2D screens. DNV GL is also interested in alternate interaction methods, as mouse and keyboard can have some limitation when working in 3D environments. Gesture Recognition Technology has been of special interest as this can potentially offer unique approaches to working with 3D models. This thesis implements such a design review application using state-ofthe- art virtual reality- and vision-based gesture recognition technologies, coupled with the Unity game engine, a popular cross-platform game development platform and software framework. After discussing these technologies’ theoretical foundations, the thesis reviews the requirements and design of the design review application, in addition to documenting its implementation and evaluating its performance by conducting user tests. In the implemented design review application the user is able to navigate 3D models, annotate them and perform various other actions, all performed by gestures.

Implementation and initial assessment of VR for scientific visualisation: Extending Unreal Engine 4 to visualise scientific data on the HTC Vive

Download PDF.

In the visualizer: outline (left), depth buffer (middle), stencil buffer (right)

Virtual Reality (VR) for scientific visualization has been researched from the 90s, but there has been little research into the fundamental aspects of VR for scientific visualisation. Questions like “Is VR ready for adoption?”, “How does VR design differ from design for monocular systems?” are two examples of fundamental questions yet to addressed. In this paper a scientific visualiser based on the game engine Unreal Engine 4 (UE4) was developed and tested by educators and researchers. A full ray marcher was successfully implemented and a near zero-cost cutting tool was developed. VR is found to have a lot of potential for improving visualisation of data sets with structural “interleaved complexity”. VR has also been deemed ready for limited mass adoption. Through field testing visualisations of volumetric and geometric models, three major issues are identified:

Current VR hardware lacks adequate input options. Menu and interaction design must be reinvented. Furthermore, 90 FPS is required for comfortable and extended VR use, which makes most current algorithms and data sets incompatible with VR. The conclusion reached through analysis of and feedback regarding the computational cost and design challenges of VR is that VR is best utilised as a tool in already existing monocular visualisation tool kits. By using a monocular system to perform most of the encoding and filtering and then use VR for inspecting the pre-processed model, it is possible to obtain the best of both worlds.

A 3D stateroom editor

Download PDF.

Today’s software systems reach easily hundreds of thousands of lines of code, and such systems do frequently benefit from the use of state machines, which help in managing system complexity by guaranteeing completeness and consistency. To visualize such state machines, statecharts have been introduced, which also offer a formalism for orthogonal and hierarchical states. Many developers use state machines, but even with statecharts as a tool, it is a major challenge to keep an overview of the machine and its effects. Gaining an overview as a newcomer to a project is an even larger challenge. In this paper, we argue that a 3D statechart can alleviate these challenges somewhat, and present an editor for state machines that are given in SCXML, an XML notation for statecharts. This editor allows the user to explore the state machine by navigating freely in a 3D environment and make changes to the machine. The editor is a prototype and incomplete. It is an attempt to reflect the idea of having statecharts presented in 3D space.

A testbed to compare Dynamic Adaptive Streaming over HTTP network configurations

Download PDF.

Streaming video over the internet has become vastly popular over the
past decade. In recent years there have been a shift towards using the
Hypertext Transfer Protocol (HTTP) for delivery of layered, segmented,
video content. These solutions go under the name HTTP Adaptive bit-rate
Streaming (HAS). One of the streaming solutions using this is the recent
international streaming standard Dynamic Adaptive Streaming over HTTP
(DASH). The increased popularity of HAS has significantly increased the
chance that multiple HAS clients will share the same network bottleneck.
Studies show that this can introduce unwanted network characteristics,
but as of today there are no good way of running realistic evaluations of
how different network configurations will impact HAS players sharing the
same bottleneck. To solve this, we have set up a testbed capable of running
automated streaming sessions, and have performed three experiments
using the DASH industry forum’s reference player, DASH.js, to present the
capabilities of the testbed.

Vamsidhar Reddy Gaddam defended his PhD

 

SONY DSC

On Thursday 2 June, Vamsidhar Reddy Gaddam defended his PhD thesis “Next Generation Broadcasting System for Arena Sports: A Football Stadium Scenario”. Vamsi has worked on the Bagadus system which is used at the Alfheim and Ullevaal stadiums.

Read more info from the university and from Simula. The PhD thesis can be found here.

Vamsi is currently an engineer in the Media Processing Group at ARM focusing on mobile graphics.

 

Redundant Data Bundling in TCP

Redundant Data Bundling (RDB) is a mechanism for TCP that aims to reduce the per-packet latency for traffic produced by interactive applications. The master’s thesis Taming Redundant Data Bundling: Balancing fairness and latency for redundant bundling in TCP[1] presents a new implementation in the Linux kernel, along with a detailed set of experiments that show the benefits of RDB. The thesis builds on the original work on RDB[2], and addresses some unresolved issues making the new implementation a candidate for widespread deployment. The paper Latency and Fairness Trade-Off for Thin Streams using Redundant Data Bundling in TCP[3] presented at LCN2015 describes the RDB mechanism in detail.

Paper Abstract

Time-dependent applications using TCP often send thin-stream traffic, characterised by small packets and high intertransmission-times. Retransmissions after packet loss can result in very high delays for such flows as they often cannot trigger fast retransmit. Redundant Data Bundling is a mechanism that preempts the experience of loss for a flow by piggybacking unacknowledged segments with new data as long as the total packet size is lower than the flow maximum segment size. Although successful at reducing retransmission latency, this mechanism had design issues leaving it open for abuse, effectively making it unsuitable for general Internet deployment. In this paper, we have redesigned the RDB mechanism to make it safe for deployment. We improve the trigger for when to apply it and evaluate its fairness towards competing traffic. Extensive experimental results confirm that our proposed modifications allows for inter-flow fairness while maintaining the significant latency reductions from the original RDB mechanism.

Thin streams and latency reducing mechanisms

Applications like online games, remote control systems, high-frequency trading and sensor networks provide a hugely increased utility when their per-packet latencies are at their lowest. They have in common that they produce mostly traffic with thin-stream characteristics, consisting of small packet payloads and high inter-transmission times (ITTs). Table 1 shows some examples of traffic properties for applications producing thin streams.

Application Payload size (B) Packet inter-arrival time (ms) Avg. BW req
avg min max avg med min max 1% 99% pps bps
VNC (from client) 8 1 106 34 8 0 5451 0 517 29.412 17K
Skype (2 users) 236 14 1267 34 40 0 1671 4 80 29.412 69K
SSH text session 48 16 752 323 159 0 76610 32 3616 3.096 2825
Anarchy Online 98 8 1333 632 449 7 17032 83 4195 1.582 2168
World of Warcraft 26 6 1228 314 133 0 14855 0 3785 3.185 2046
Age of Conan 80 5 1460 86 57 0 1375 24 386 11.628 12K

 

Some existing mechanisms in the Linux kernel aimed at reducing latencies for TCP are

  • Thin Linear Timeouts (LT)
  • Modified fast retransmit (mFR)
  • Early Retransmit (ER)
  • Tail Loss Probe (TLP)

These mechanisms are reactive, i.e. they modify how the TCP sender reacts to loss or possible loss by triggering retransmits faster. The problem is that in a best case scenario, they still require at least an RTT of extra delay for the loss signal to reach the sender host before the data is retransmitted. The exception to this is in cases where the TLP packet retransmits the lost packet.

Read more about time-dependent networking (TDN) and earlier work on thin streams and interactive applications.

Redundant Data Bundling

In contrast to the earlier mentioned reactive mechanisms, RDB is a proactive mechanism which tries to prevent unnecessary delays when packet loss occurs. By bundling already sent data with packets containing new data, RDB can be considered a retransmission mechanism that retransmits segments even before any loss signals are present.

An important property of RDB is that it does not produce extra packets on the network, but instead utilizes the “free” space in small TCP packets produced by interactive applications.

ethernet-frame

Figure 1: Example of an Ethernet frame for a TCP packet with 100 bytes payload.

TCP requires that the payload in each packet is sequential, however, a receiver is required to accept any new data in a packet even if some of the data has already been received. RDB takes advantage of this by bundling already sent (but un-ACKed) data segments in packets with new data.

Figure 2 shows an example with four separate data segments (S1-S4) illustrating how RDB organizes the data segments in each packet.

 

frames

Figure 2: Example showing how RDB bundles the data of previously sent packets in packets with new data.

.

Note about “Free” or unused space in Ethernet frames
For small TCP packets with less than 1 * MSS worth of payload, the Ethernet frame will not fill the maximum segment size. “Free” is this context refers to additional space that may be used without increasing the same number of Ethernet frames through the network.

RDB in action

Figure 3 shows a scenario where an application performs write calls to the TCP socket with 365 bytes per call. When two consecutive packets are lost, the lost segments are “recovered” by the third packet which bundles the (new) segments from the previous two packets.

 

rdb_timeline_loss

Figure 3: Packet timeline of a TCP thin stream using RDB.

 

Limiting RDB to thin streams

To ensure only thin streams can use RDB, a mechanism called Dynamic Packets in Flight Limit (DPILF) is used. By specifying a minimum allowed ITT, a maximum packets in flight limit is calculated dynamically based on the current RTT measurements. Figure 4 shows how the DPIFL is calculated for the minimum ITT limits 5, 10, 20 and 30 ms, with different RTTs.

 

Figure 4: Example of DPIFL for different minimum ITT values

Figure 4: Example of DPIFL for different minimum ITT values

For comparison, a Static Packets in Flight Limit (SPILF) of 3 is included in figure 4 to show how the thin stream test currently used in the Linux kernel does not adjust the limit based on RTT measurements.

Experiments and results

A wide range of tests have been performed to evaluate the effects of RDB in regards to reduced latencies, as well as fairness towards competing network traffic. The experiments have been performed in a testbed with Linux (Debian) hosts as depicted in figure 5.

 

Testbed setup

Figure 5: Testbed setup

Tests with uniform loss rate

A set of tests were performed where netem on BRIDGE2 was configured with a uniform loss rate. These tests illustrate the difference in latency between regular TCP and RDB with different bundling rates. In figure 6 we see the result from one of the test sets with a uniform loss rate of 10%. The plot shows the ACK latency for three separate tests, where each test started 20 different TCP streams. One test where only regular TCP was used, and the two other tests with 10 regular TCP streams, and 10 RDB streams, where a limit was imposed on when any redundant data could be bundled. For RDB SPIFL 3, each TCP stream was allowed to bundle only when there were three or fewer packets in flight (PIFs). With an ITT of 30 ms, and a network delay configured with 75 ms in each direction (RTT of 150 ms), each stream would have 5 PIFs as long as it is not congestion limited.

Figure 6: Experiment with uniform loss

Figure 6: Experiment with uniform loss

 

Comparing the latency of the different stream types, we see a significant difference when RDB is enabled. The RDB streams that were allowed to bundle while PIFs <= 7 have a significantly better ACK latency, where 90% of the TCP segments have no extra delay. For the regular TCP streams we see that almost 60% of the TCP segments have a higher ACK latency than the ideal 150 ms, even when only 10% of the packets are lost. This is due to head-of-line blocking causing delays not only for the lost segment, but for every segment transmitted after the lost segment, until a retransmission arrives at the receiver side.

Latency tests with cross traffic over a shared bottleneck

In these experiments a set of RDB-enabled thin streams and regular TCP streams are tested while competing against greedy TCP flows over a shard bottleneck. Each of the following plots show the results from two test runs, one where 20 TCP streams (TCP Reference) compete against 5 greedy TCP flows, and another where 10 RDB-enabled thin streams and 10 TCP thin streams compete against 5 greedy TCP flows. The shared bottleneck is configured with a rate limit of 5Mbit and a pfifo queue of one bandwidth-delay product (63 packets).

Figure 7: Experiment with no bundling limit

Figure 7: Experiment with no bundling limit

 

 

The RDB streams plotted in figure 7 are allowed to bundle any available previous segments as long as the payload does not exceed one MSS. Looking at the latencies we see a significant difference between the RDB streams and the TCP streams, however, comparing the latencies to the TCP reference values we see that the increased bandwidth due to the redundant data causes extra queuing delays which may not be desirable.

Figure 8: Experiment with bundling limit

Figure 8: Experiment with bundling limit

 

 

 

Figure 8 shows the results from a test with the same setup as in figure 7, except for a limitation on the redundancy level for the RDB streams where they are allowed to bundle only one previous segment with each packet. The results show that with the reduced redundancy level, the RDB streams still have a much lower latency that the competing TCP streams, while avoiding the extra queuing delay found in the previous tests.

 

Conclusion

The RDB mechanism uses a proactive approach to reduce latencies for time-dependent traffic over TCP. By continually bundling (retransmitting) data instead of waiting for any loss signals before triggering a retransmission, RDB is able to avoid the extra delay of at least 1 RTT needed for a loss signal to reach the sender host. This results in significantly reduced latencies for thin stream traffic that experience sporadic packet loss.

Main benefits of RDB:

  • RDB is backwards compatible TCP mechanism that requires sender side modifications only. This means that e.g. a Linux server can enable RDB on connections to unmodified TCP receivers. In this case, only the data sent from the server to the client will benefit from RDB, and the data in the reverse path will use regular TCP.
  • RDB does not produce extra packets on the network, and achieves the reduced latencies by using the packets that are already scheduled for transmission.
  • Reduces latencies for RDB enabled streams without unreasonable negative effects on competing traffic .

References

[1] B. R. Opstad, “Taming redundant data bundling” Master’s thesis, University of Oslo, May 2015. (Download PDF)
[2] K. Evensen, A. Petlund, C. Griwodz, and P. Halvorsen, “Redundant bundling in TCP to reduce perceived latency for time-dependent thin streams” Comm. Letters, IEEE, vol. 12, no. 4, pp. 324–326, April 2008.
[3] B. R. Opstad, J. Markussen, I. Ahmed, A. Petlund, C. Griwodz, and P. Halvorsen, “Latency and Fairness Trade-Off for Thin Streams using Redundant Data Bundling in TCP”, IEEE Conference on Local Computer Networks (LCN), Clearwater Beach, Florida, USA, Oct. 2015. (Download PDF)

Kenneth Klette Jonassen’s proposed CDG patch featured in lwn.net

Screenshot 2015-06-05 14.07.20Master student Kenneth Klette Jonassen has spent his thesis exploring congestion controls for low latency and has ported the Caia Delay-Gradient (CDG) algorithm from FreeBSD to Linux. His RFC posting of the CDG code to the netdev list got a lot of attention and was featured on the LWN kernel update last week. His thesis documents significant differences between the behaviour of CDG in Linux and FreeBSD, most likely due to differences in default behaivour (like Linux implementing PRR) and the large difference in timer granularity between the two systems. Kenneth also did work where he updated and improved the Linux kernel’s RTT measurement code for SACK blocks.

Kenneth’s work is research going out to the public for further use and development. We’ll try to follow up on that!

« Older Entries