Tag: Research

Fully automatic detection of the vertebrae in 2D CT images

FINALLY submitted the paper which we sent to the SPIE Medical Imaging Conference  (and got accepted!)

Abstract:

Knowledge about the vertebrae is a valuable source of information for several annotation tasks. In recent years, the research community spent a considerable effort for detecting, segmenting and analyzing the vertebrae and the spine in various image modalities like CT or MR. Most of these methods rely on prior knowledge like the location of the vertebrae or other initial information like the manual detection of the spine. Furthermore, the majority of these methods require a complete volume scan. With the existence of use cases where only a single slice is available, there arises a demand for methods allowing the detection of the vertebrae in 2D images. In this paper, we propose a fully automatic and parameterless algorithm for detecting the vertebrae in 2D CT images. Our algorithm starts with detecting candidate locations by taking the density of bone-like structures into account. Afterwards, the candidate locations are extended into candidate regions for which certain image features are extracted. The resulting feature vectors are compared to a sample set of previously annotated and processed images in order to determine the best candidate region. In a final step, the result region is readjusted until convergence to a locally optimal position. Our new method is validated on a real world data set of more than 9 329 images of 34 patients being annotated by a clinician in order to provide a realistic ground truth.

More Information and the paper as PDF can be found at my publication site.

PAROS download!

Das Ziel war nobel: Code aufräumen, schöner machen, refactoren und dokumentieren und dann online stellen.

Die Realität war derart, dass es leider wichtigeres zu tun gibt. Daher stelle ich das PAROS-Projekt, das dieses Jahr auf der SIGMOD war so online wie es ist: lauffähig, und vom Softwareengineeringaspekt ziemlich hässlich. Aber vielleicht kann ja jemand etwas damit anfangen – zumindest die kleinen hacks um größere Graphen auch annehmbar schnell zeichnen zu können.

Ausserdem ist es ein schönes Beispiel, wie man JXMapKit und OpenStreetMap (OSM) zu Forschungszwecken im Bereich Datamining, GIS (GeoInformationssysteme) und auch SpatialIndexing  verwenden kann. Auf der Konferenz kannten viele OSM nämlich erstaunlicherweise gar nicht, obwohl sie auf dem Bereich tätig waren.

Und zur nächsten Version muss ich nochmal nachsehen, ob es nach den Google Maps Terms of Services  immernoch verboten ist, Maps in Nicht-Browser-Anwendungen zu integrieren. Wäre natürlich auch sehr nett, oder weiß jemand Bescheid? (Update Jan. 2011: das ist nicht mehr verboten!)

Relevante Links:

Impact of Flash SSDs on Spatial Indexing

Neben Paros war ich auf der SigMod 2010 auch mit einer Veröffentlichung auf dem DaMoN Workshop (Data Management On new Hardware) vertreten. Der Titel der Veröffentlichung war “On the Impact of Flash SSDs on Spatial Indexing“.

Dass SSDs schnell und cool sind, ist ja mittlerweile allseits bekannt. Leider sind sie noch etwas teuer – nichts desto trotz haben sie den unglaublichen Vorteil, dass die Zugriffszeiten bei wahlfreien Lesezugriffen deutlich kleiner sind, da sie nahezu keine Seek-Zeiten aufweisen (also die Zeit in der der Lesearm der regulären Festplatte erst zur richtigen Position gefahren werden muss, bevor gelesen oder geschrieben werden kann). Diese Seek-Zeiten sind gerade bei Datenbankindices einer der bremsenden Faktoren. Da unser Lehrstuhl auf Datenbanken, DataMining und Indexing spezialisiert ist, haben wir uns daher angesehen, wie sich der R*-Baum (einer der Standard-Indices für mehrdimensionale Daten) auf SSDs im Vergleich zu HDDs verhält. Insbesondere, wie die Indices skalieren und wie es mit der Performanz aussieht, wenn höher dimensionale Daten ( > 10 Dimensionen bzw. Spalten) mit einem R*-Baum indexiert werden sollen und wie es sich mit dem Fluch der Dimensionalität verhält.

Fazit: War eine doch recht spannende und vor allem recht praktische Arbeit , da wir nicht einfach nur Modelle durchrechnen wollten, sondern wirklich die Zugriffe auf die Platte sehen und messen wollten – was die Tests auch sehr zeitaufwändig gemacht hat, da Ram und Platte eben doch einen “kleinen” Geschwindigkeitsunterschied haben.

Abstract:

Similarity queries are an important query type in multimedia databases. To implement these types of queries, database systems often use spatial index structures like the R*-Tree. However, the majority of performance evaluations for spatial index structures rely on a conventional background storage layer based on conventional hard drives. Since newer devices like solid-state-disks (SSD) have a completely different performance characteristic, it is an interesting question how far existing index structures proft from these modern storage devices. In this paper, we therefore examine the performance behaviour of the R*-Tree on an SSD compared to a conventional hard drive. Testing various in uencing factors like system load, dimensionality and page size of the index our evaluation leads to interesting insights into the performance of spatial index structures on modern background storage layers.

Die Veröffentlichung kann man auf unserer Website herunterladen: On the Impact of Flash SSDs on Spatial Indexing

SwingX-WS mit JXMapKit auf der SIGMOD 2010 / PAROS: Pareto Optimal Route Selection

Zusammen mit meinen Kollegen haben wir eine Demo auf einer der wichtigsten Datenbank Konferenzen eingereicht, die ich letzte Woche in Indianapolis auf der SIGMOD (ACM Special Interest Group on Management of Data) zeigen durfte. Die Demo firmiert übrigens unter dem Titel PAROS: Pareto Optimal Route Selection.

Im Wesentlichen ging es dabei darum, einen von meinen Kollegen entwickelten Skyline-Algorithmus auf Straßennetzen anzuwenden um damit Wege unter mehreren Einschränkungen zu finden. Die klassische, einfache Wegsuche ist ja zum Beispiel “finde den kürzesten oder schnellsten Weg”. Bei der Skyline-Abfrage, geht es dabei darum, alle die Wege zu finden, die unter mehreren Attributen optimal sind. Also zum Beispiel alle kürzesten und schnellsten Wege, die gleichzeitig möglichst wenig Ampeln enthalten. Es müssen also mehrere Attribute gleichzeitig optimiert werden.

Da Datenmasse in der Wissenschaft oft Mangelware ist, habe ich zusammen mit etwas studentischer Hilfe einen Konverter für OpenStreetMap-Daten geschrieben um beliebig viele Daten erhalten zu können. Visualisiert wurde das Ganze mit Hilfe der JXMapKit-Komponente aus SwingX-WS! Die Gui-Entwicklung ging dank dem NetBeans Gui-Builder wie erwartet erfreulich einfach, so dass ich mich in der knappen Zeit auf die Integration des Algorithmus und auf die Architektur konzentrieren konnte. Die Architektur sollte es ermöglichen, Model und View  möglichst so zu kapseln, dass die Entwicklung und Integration neuer Algorithmen so einfach wie möglich und möglichst Unabhängig von jeglicher GUI-Programmierung ist, so dass auch Studenten schnell und einfach neue Algorithmen entwickeln und testen können.

Ich habe zwar (wie erwartet) nicht den Best-Demo-Preis bekommen, allerdings waren wirklich viele interessierte Leute auf den Demo-Sessions. Überrascht hat mich, dass ich sehr oft gefragt wurde, ob wir die Demo online stellen würden, bzw. ob die Demo OpenSource ist. Nach Rücksprache mit den Kollegen, kamen wir zu dem Schluss, dass das eine gute Idee sei und ich das machen werde. Ich werde in den nächsten Wochen also noch etwas den Code aufräumen, dokumentieren, online stellen und hoffen, dass jemand die Demo interessant und nützlich findet – vielleicht sogar so, dass es die Basis für ein oder mehre Zitationen bringt (ist immer wichtig bei Veröffentlichungen).

UPDATE: endlich ist der – äh – unschöne Code online. Da ich auch in absehbarer Zeit nicht die Zeit habe, ihn schön sauber und dokumentiert zu machen, kann ich ihn auch gleich online stellen. zum Download gehts hier lang.

Relevante Links: