Change submenu markup

The whole idea of a custom walker class is that you can customize the menu in detail. So, you can also leave the main menu as it is and build the submenus the way you give in the image.

However, as Hareesh indicates in the comments, this does require quite a lot of customization, especially if you want you theme to be widely applicable (meaning you’ll have to take into account errors, such as missing images in the submenu). This might be a nice place to start understanding the walker class.