Recent developments in the computer vision field achieve state-of-the-art performance by utilizing large-scale training datasets and in the absence of that, generating synthetic datasets of said magnitude. Yet, for certain applications, it is not feasible to synthesize high fidelity training data (e.g., biomedical computer vision domain), or to achieve detailed explainability for the program's decisions. Formulating a part-based approach can help alleviate the aforementioned challenges as (i) a scene can naturally be decomposed into a hierarchical part-based structure, and (ii) using domain knowledge by incorporating the object parts' topological and geometrical constraints reduces the complexity of learning and inference, benefiting methods in terms of data efficiency and computational resources. This dissertation investigates multiple applications that benefit from a part-based solution regarding the applications' performance metrics and/or computational efficiency. We develop part-based methods for registration, segmentation, unsupervised object discovery in large-scale image collections, and unsupervised unknown foreground discovery in streaming scenarios.