The State of Health (SOH) of lithium-ion batteries is directly related to their safety and efficiency, yet effective assessment of SOH remains challenging for real-world applications (e.g., electric vehicle). In this paper, the estimation of SOH (i.e., capacity fading) under partial discharge with different starting and final State of Charge (SOC) levels is investigated. The challenge lies in the fact that partial discharge truncates the data available for SOH estimation, thereby leading to the loss or distortion of common SOH indicators. To address this challenge associated with partial discharge, we explore the convolutional neural network (CNN) to extract indicators for both SOH and changes in SOH ($Δ$SOH) between two successive charge/discharge cycles. The random forest algorithm is then adopted to produce the final SOH estimate by exploiting the indicators from the CNNs. Performance evaluation is conducted using the partial discharge data with different SOC ranges created from a fast-discharging dataset. The proposed approach is compared with i) a differential analysis-based approach and ii) two CNN-based approaches using only SOH and $Δ$SOH indicators, respectively. Through comparison, the proposed approach demonstrates improved estimation accuracy and robustness. Sensitivity analysis of the CNN and random forest models further validates that the proposed approach makes better use of the available partial discharge data for SOH estimation.