Quadtree Convolutional Neural Networks

Pradeep Kumar Jayaraman, Jianhan Mei, Jianfei Cai, Jianmin Zheng

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


This paper presents a Quadtree Convolutional Neural Network (QCNN) for efficiently learning from image datasets representing sparse data such as handwriting, pen strokes, freehand sketches, etc. Instead of storing the sparse sketches in regular dense tensors, our method decomposes and represents the image as a linear quadtree that is only refined in the non-empty portions of the image. The actual image data corresponding to non-zero pixels is stored in the finest nodes of the quadtree. Convolution and pooling operations are restricted to the sparse pixels, leading to better efficiency in computation time as well as memory usage. Specifically, the computational and memory costs in QCNN grow linearly in the number of non-zero pixels, as opposed to traditional CNNs where the costs are quadratic in the number of pixels. This enables QCNN to learn from sparse images much faster and process high resolution images without the memory constraints faced by traditional CNNs. We study QCNN on four sparse image datasets for sketch classification and simplification tasks. The results show that QCNN can obtain comparable accuracy with large reduction in computational and memory costs.

Original languageEnglish
Title of host publicationComputer Vision – ECCV 2018
Subtitle of host publication15th European Conference Munich, Germany, September 8–14, 2018 Proceedings, Part VI
EditorsVittorio Ferrari, Martial Hebert, Cristian Sminchisescu, Yair Weiss
Place of PublicationCham Switzerland
Number of pages16
ISBN (Electronic)9783030012311
ISBN (Print)9783030012304
Publication statusPublished - 2018
Externally publishedYes
EventEuropean Conference on Computer Vision 2018 - Munich, Germany
Duration: 8 Sep 201814 Sep 2018
Conference number: 15th
https://link.springer.com/book/10.1007/978-3-030-01246-5 (Proceedings)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceEuropean Conference on Computer Vision 2018
Abbreviated titleECCV 2018
Internet address


  • Neural network
  • Quadtree
  • Sparse convolution

Cite this