If it's new territory, up front design is worthless. You've never attempted to create a facial recognition program before. Not too long ago, no one else had either so there wasn't a lot of useful content to study. Your best bet is to try making 1 small useful unit of work, iterate, try again. Fit the pieces you create to achieve a goal. A design is grown from the bottom up. Now you have a better understanding of the problem and may be able to do some design.
Also I refactor as I go (which I learnt about decades later than I should have), striving to get the naturally emerging structure as clear as possible, in every way – data structures, single-purpose functions, variable names etc. That's apart from the general structure I plan initially, but planning things first makes the refactoring infinitely easier. So, for me it's kind of a combination of the two.
To combat the fact that there's no right answer here, the teams that I work in have adopted a couple of strategies.
1. Start out with a reasonable sketch of the high-level design of the system and/or library that is being written. Thinking through this high-level approach lets everyone start with a reasonable shared mental model of how things will look as development proceeds. It also means that some of the complexities of "which of the more complex cases that we're going to come across are we going to solve, and which can be a TODO" be decided up-front.
2. After this initial design exercise, do design is small chunks, iteratively. Take the smallest possible set of functionality, and have a developer in the team (not just the tech lead...) determine the options for design, and propose one as the solution. These small units of design can be informed as the developer wishes -- i.e., they can do prototyping if it makes sense.
3. At all costs, avoid development approaches and team dynamics where refactoring is not considered an option, or discouraged. As you observe in your question, getting the design right might involve understanding more of the problem, or the requirements, and that might need the "oh , we should have solved this like that!" moment that only comes from having implemented something, or watching your users try and use the solution you built entirely differently to how you expected. Ensure that there's a team culture, or an openness to the idea that you definitely won't be right the first time. Perfect is the enemy of "done" or "shipped".
Personally, I prefer to start to think about the problem in an abstract form before coding, because this allows me to separate the consideration of the best way to write maintainable, testable code from the problem of the system, library or application design. Of course, YMMV, but this is what works for me :-)
I could imagine someone with a good feel for the context could do that, I just haven't been able to do so / don't find it helpful to do so.
> What is the right way? I would like to know too. I suspect experience gives you insight into a design that will likely work.