Julian Müller

Julian Müller

We study the problem of enumerating Tarski fixed points on finite lattices. We derive query complexity lower bounds for finding three or more Tarski fixed points of isotone maps and the subclasses of increasing and decreasing isotone maps. Specifically, we show that any deterministic or bounded-error algorithm must perform asymptotically as many queries in the worst case as the lattice width for isotone maps, which is exponential for the lattice of binary relations and other relevant lattices. We also present two enumeration algorithms for fixed points of increasing or decreasing isotone maps based on depth-first and flashlight search. Both algorithms run in polynomial space on polynomial-height lattices, but are particularly suitable in terms of applicability and runtime performance on different lattices, as they build on differing properties of the underlying lattice. Finally, we discuss the enumeration of Tarski fixed points on the lattices of binary relations, quasiorders and equivalences, demonstrating that the presented algorithms run in polynomial space on these lattices and perform with polynomial delay whenever the problem of finding three or more fixed points is neither NP-hard nor has an exponential query lower bound. We exemplify how these results can be used to list instances of various models of behavioral or role equivalence, specifically deriving a polynomial-space algorithm that enumerates bisimulations with $\mathcal O(n^3m)$ delay on a transition system with $n$ states and $m$ transitions.

Julian Müller, Andreas Fregin, Klaus Dietmayer

Sliding window approaches have been widely used for object recognition tasks in recent years. They guarantee an investigation of the entire input image for the object to be detected and allow a localization of that object. Despite the current trend towards deep neural networks, sliding window methods are still used in combination with convolutional neural networks. The risk of overlooking an object is clearly reduced compared to alternative detection approaches which detect objects based on shape, edges or color. Nevertheless, the sliding window technique strongly increases the computational effort as the classifier has to verify a large number of object candidates. This paper proposes a sliding window approach which also uses depth information from a stereo camera. This leads to a greatly decreased number of object candidates without significantly reducing the detection accuracy. A theoretical investigation of the conventional sliding window approach is presented first. Other publications to date only mentioned rough estimations of the computational cost. A mathematical derivation clarifies the number of object candidates with respect to parameters such as image and object size. Subsequently, the proposed disparity sliding window approach is presented in detail. The approach is evaluated on pedestrian detection with annotations and images from the KITTI object detection benchmark. Furthermore, a comparison with two state-of-the-art methods is made. Code is available in C++ and Python https://github.com/julimueller/ disparity-sliding-window.

Julian Müller, Klaus Dietmayer

Recent improvements in object detection are driven by the success of convolutional neural networks (CNN). They are able to learn rich features outperforming hand-crafted features. So far, research in traffic light detection mainly focused on hand-crafted features, such as color, shape or brightness of the traffic light bulb. This paper presents a deep learning approach for accurate traffic light detection in adapting a single shot detection (SSD) approach. SSD performs object proposals creation and classification using a single CNN. The original SSD struggles in detecting very small objects, which is essential for traffic light detection. By our adaptations it is possible to detect objects much smaller than ten pixels without increasing the input image size. We present an extensive evaluation on the DriveU Traffic Light Dataset (DTLD). We reach both, high accuracy and low false positive rates. The trained model is real-time capable with ten frames per second on a Nvidia Titan Xp. Code has been made available at https://github.com/julimueller/tl_ssd.