How do you detect when an image has been deleted from WordPress media library?

You can use the before_delete_post action hook for this purpose as it triggers just before WordPress deletes a post (or media) which allows you to utilize its ID in time.

function my_plugin_image_deleted( $post_id ) {
    // Ensure type is attachment (could be a page, post, etc. otherwise)
    if ( 'attachment' === get_post_type( $post_id ) ) {
        // Your code here - you have the $post_id to play with!
        // ...
    }
}
add_action( 'before_delete_post', 'my_plugin_image_deleted' );