Sachverhalt:
A.
A.a. Christian Louboutin, Paris, Frankreich, (Gesuchsteller, Beschwerdeführer) ist Inhaber der internationalen Registrierung Nr. 1'031'242 "rote (Pantone No. 18.1663TP) Damenschuhsohle (Positionsmarke) " mit Basiseintragung im Vereinigten Königreich.
Am 25. März 2010 notifizierte die Organisation Mondiale de la Propriété Intellectuelle (OMPI) diese Registrierung für die Schutzausdehnung auf das Gebiet der Schweiz. Das Warenverzeichnis umfasst nach einer Einschränkung nunmehr die Ware chaussures pour dames à talons hauts der Klasse 25. Die Positionsmarke sieht wie folgt aus:
A.b. Gegen diese Schutzausdehnung erliess das Eidgenössische Institut für Geistiges Eigentum (IGE, Beschwerdegegner) am 15. März 2011 eine vorläufige vollständige Schutzverweigerung mit der Begründung, die rote Farbe auf der Schuhsohle der an sich banalen Warendarstellung werde als rein dekoratives Element wahrgenommen. Dem Zeichen fehle es somit an der konkreten Unterscheidungskraft und es gehöre zum Gemeingut.
A.c. Mit Stellungnahme vom 15. Dezember 2011 reichte der Gesuchsteller etliche Unterlagen ein, um die Verkehrsdurchsetzung des Zeichens glaubhaft zu machen.
Das IGE hielt jedoch an der Schutzverweigerung fest, da es eine Verkehrsdurchsetzung als nicht gegeben erachtete.
A.d. Mit Stellungnahme vom 8. April 2013 schränkte der Gesuchsteller die Markenanmeldung von den ursprünglich beanspruchten chaussures pour dames auf chaussures pour dames à talons hautsein und führte dazu aus, der Marke komme ursprüngliche Unterscheidungskraft zu, da es sich beim angemeldeten Zeichen nicht lediglich um ein dekoratives Element, sondern um eine alle Schutzvoraussetzungen erfüllende Positionsmarke handle.
A.e. Mit Entscheid vom 1. September 2013 verweigerte das IGE der internationalen Markenregistrierung Nr. 1'031'242 für die beanspruchte Ware der Klasse 25 den Schutz in der Schweiz infolge fehlender Unterscheidungskraft.
B.
Der Gesuchsteller erhob am 1. November 2013 beim Bundesverwaltungsgericht Beschwerde gegen die Verfügung des IGE vom 1. September 2013. Er beantragte, es sei die angefochtene Verfügung aufzuheben und es sei der internationalen Markenregistrierung Nr. 1'031'242 in der Schweiz Markenschutz zu gewähren. Dabei hielt er fest, dass er keinen Markenschutz mehr gestützt auf eine Verkehrsdurchsetzung des Zeichens beantrage.
Mit Urteil vom 27. April 2016 wies das Bundesverwaltungsgericht die Beschwerde ab.
C.
Mit Beschwerde in Zivilsachen beantragt Christian Louboutin dem Bundesgericht, es sei das Urteil des Bundesverwaltungsgerichts vom 27. April 2016 aufzuheben und es sei der internationalen Markenregistrierung Nr. 1'031'242 der Schutz in der Schweiz zu erteilen. Eventualiter sei das Verfahren zur Ergänzung des Sachverhalts an die Vorinstanz zurückzuweisen.
Das IGE beantragt die Abweisung der Beschwerde. Die Vorinstanz hat auf eine Vernehmlassung verzichtet.
Der Beschwerdeführer hat dem Bundesgericht eine Replik eingereicht.
Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (Art. 29 Abs. 1 BGG; BGE 140 IV 57 E. 2 S. 59; 139 III 133 E. 1 S. 133; je mit Hinweisen).
1.1. In der vorliegenden Registersache ist nach Art. 72 Abs. 2 lit. b Ziff. 2 BGG die Beschwerde in Zivilsachen das zulässige Rechtsmittel. Als Vorinstanz hat das Bundesverwaltungsgericht entschieden (Art. 75 Abs. 1 BGG). Der Entscheid erging nicht im Rahmen des Widerspruchsverfahrens (Art. 73 BGG). Der Beschwerdeführer ist mit seinen Begehren vor der Vorinstanz unterlegen und hat den gewünschten Markenschutz für sein Zeichen nicht erhalten, womit er zur Beschwerde berechtigt ist (Art. 76 Abs. 1 lit. a und b BGG). Der angefochtene Entscheid schliesst das Verfahren betreffend die internationale Registrierung Nr. 1'031'242 ab und stellt demnach einen Endentscheid dar (Art. 90 BGG). Die Beschwerdefrist von 30 Tagen (Art. 100 Abs. 1 BGG) wurde eingehalten. Der für die Beschwerde in Zivilsachen erforderliche Streitwert ist erreicht (Art. 74 Abs. 1 lit. b BGG; BGE 133 III 490 E. 3).
Auf die Beschwerde ist demnach - unter Vorbehalt einer hinreichenden Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) - einzutreten.
1.2. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist somit weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen oder eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Mit Blick auf die Begründungspflicht der beschwerdeführenden Partei (Art. 42 Abs. 1 und 2 BGG) behandelt es aber grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind; es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (BGE 140 III 115 E. 2 S. 116; 137 III 580 E. 1.3; 135 III 397 E. 1.4). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. Das Bundesgericht prüft eine solche Rüge nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG).
Unerlässlich ist im Hinblick auf Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG, dass die Beschwerde auf die Begründung des angefochtenen Entscheids eingeht und im Einzelnen aufzeigt, worin eine Rechtsverletzung liegt. Die beschwerdeführende Partei soll in der Beschwerdeschrift nicht bloss die Rechtsstandpunkte, die sie im vorinstanzlichen Verfahren eingenommen hat, erneut bekräftigen, sondern mit ihrer Kritik an den als rechtsfehlerhaft erachteten Erwägungen der Vorinstanz ansetzen (BGE 140 III 86 E. 2 S. 89, 115 E. 2 S. 116). Die Begründung hat ferner in der Beschwerdeschrift selbst zu erfolgen und der blosse Verweis auf Ausführungen in anderen Rechtsschriften oder auf die Akten reicht nicht aus. Für die Beschwerdeantwort gelten dieselben Begründungsanforderungen (BGE 140 III 115 E. 2 S. 116).
1.3. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Dazu gehören sowohl die Feststellungen über den streitgegenständlichen Lebenssachverhalt als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, also die Feststellungen über den Prozesssachverhalt (BGE 140 III 16 E. 1.3.1 mit Hinweisen). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 105 Abs. 2 BGG). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (BGE 140 III 115 E. 2 S. 117; 135 III 397 E. 1.5). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein können (Art. 97 Abs. 1 BGG).
Für eine Kritik am festgestellten Sachverhalt gilt das strenge Rügeprinzip von Art. 106 Abs. 2 BGG (BGE 140 III 264 E. 2.3 S. 266 mit Hinweisen). Die Partei, welche die Sachverhaltsfeststellung der Vorinstanz anfechten will, muss klar und substanziiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (BGE 140 III 16 E. 1.3.1 S. 18 mit Hinweisen). Wenn sie den Sachverhalt ergänzen will, hat sie zudem mit präzisen Aktenhinweisen darzulegen, dass sie entsprechende rechtsrelevante Tatsachen und taugliche Beweismittel bereits bei den Vorinstanzen prozesskonform eingebracht hat (BGE 140 III 86 E. 2 S. 90). Genügt die Kritik diesen Anforderungen nicht, können Vorbringen mit Bezug auf einen Sachverhalt, der vom angefochtenen Entscheid abweicht, nicht berücksichtigt werden (BGE 140 III 16 E. 1.3.1 S. 18).
Gemäss Art. 99 Abs. 1 BGG dürfen neue Tatsachen und Beweismittel nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt, was in der Beschwerde näher darzulegen ist (BGE 133 III 393 E. 3 S. 395). Tatsachen oder Beweismittel, die sich auf das vorinstanzliche Prozessthema beziehen, jedoch erst nach dem angefochtenen Entscheid eingetreten oder entstanden sind (sog. echte Noven), sind vor Bundesgericht unbeachtlich (BGE 133 IV 342 E. 2.1 S. 344; Urteile 4A_169/2016 vom 12. September 2016 E. 2.2; 4A_558/2015 vom 25. Februar 2016 E. 1; je mit Hinweisen; Botschaft vom 28. Februar 2001 zur Totalrevision der Bundesrechtspflege, BBl 2001 4340 Ziff. 4.1.4.3 zu Art. 93 E-BGG).
1.4. Diese Grundsätze verkennt der Beschwerdeführer, indem er sich in seinen Ausführungen unter dem Titel "Der Kläger und seine Marke" auf neu eingereichte Beweismittel in Form einer tabellarischen Übersicht über den aktuellen Stand seiner weltweiten Markenregistrierungen sowie eines Entscheids des Gerichtshofs der Europäischen Union (EuGH) vom 12. Mai 2016 betreffend die von ihm eingetragene Gemeinschaftsmarke stützt, bei denen es sich um unzulässige echte Noven handelt. Die dem Bundesgericht ebenfalls neu eingereichte Vergleichsvereinbarung vom 2. März 2016, welche die Anerkennung der Unterscheidungskraft durch ein Konkurrenzunternehmen belegen soll, ist zwar noch vor dem angefochtenen Entscheid entstanden; entgegen der in der Beschwerde vertretenen Ansicht leuchtet jedoch nicht ein, dass erst der angefochtene Entscheid der Vorinstanz zu den neuen Tatsachen bzw. dem neu eingereichten Beweismittel Anlass gegeben hätte, zumal die Frage der Unterscheidungskraft augenscheinlich im Zentrum des vorinstanzlichen Verfahrens stand.
Auch in seiner weiteren Beschwerdebegründung verkennt der Beschwerdeführer die aufgeführten Grundsätze, indem er verschiedentlich von den tatsächlichen Feststellungen des angefochtenen Entscheids abweicht oder diese erweitert, ohne substanziiert Ausnahmen von der Sachverhaltsbindung geltend zu machen. Dies trifft etwa für seine Ausführungen zu den Herstellungskosten verschiedener Schuharten und die Vorbringen hinsichtlich des Datums der vom Beschwerdegegner eingereichten Beweise zu. Der Beschwerdeführer bezeichnet die vorinstanzlichen Feststellungen zwar verschiedentlich als willkürlich, widersprüchlich, offensichtlich unrichtig oder gegen das rechtliche Gehör verstossend, verfehlt mit seinen pauschalen Vorbringen aber die gesetzlichen Begründungsanforderungen an entsprechende Rügen. Die Vorbringen haben unbeachtet zu bleiben.
Rein appellatorisch sind zudem die Vorbringen, mit denen der Beschwerdeführer unter Hinweis auf zahlreiche Eingaben im vorinstanzlichen Verfahren die Beweiswürdigung der Vorinstanz kritisiert und ihr ohne weitere Begründung vorwirft, sie habe die Beweismittel einseitig gewürdigt. Damit ist er nicht zu hören.
2.
Der Beschwerdeführer rügt, die Vorinstanz habe die massgebenden Grundsätze zur Beweislastverteilung und zu den Folgen der Beweislosigkeit missachtet. Aus seinen Vorbringen geht jedoch nicht hervor, hinsichtlich welcher rechtserheblicher Tatsachen die Vorinstanz zu seinen Lasten von der Beweislosigkeit ausgegangen sein soll. Wie sich zeigen wird, ist für die Beurteilung der Unterscheidungskraft des strittigen Zeichens zudem nicht ausschlaggebend, ob im massgeblichen Zeitpunkt auch andere Anbieter hochhackige Damenschuhe mit roten Aussensohlen anboten.
Mit dem Vorbringen, es müsse auf die Verhältnisse im Zeitpunkt der Markenanmeldung bzw. der internationalen Schutzausdehnung abgestellt werden, weshalb die Vorinstanz zu Unrecht Beweismittel berücksichtigt habe, die von einem Zeitpunkt nach der Markenanmeldung stammten, verkennt der Beschwerdeführer, dass der Vergleich eines Zeichens mit den bestehenden Formen bzw. Gestaltungen nach bundesgerichtlicher Rechtsprechung bezogen auf den Zeitpunkt des Entscheids über die Eintragung im Markenregister zu erfolgen hat (BGE 137 III 403 E. 3.3.3 S. 409; 134 III 547 E. 2.3.4).
3.
Der Beschwerdeführer wirft der Vorinstanz vor, sie habe dem angemeldeten Zeichen zu Unrecht die originäre Unterscheidungskraft abgesprochen.
3.1. Die Vorinstanz erwog, für die Frage der Unterscheidungskraft sei ohne Belang, welcher Markenart ein Zeichen zuzuordnen sei. Die zu klärende Rechtsfrage bleibe grundsätzlich dieselbe, wobei Besonderheiten in der Wahrnehmung einer Markenart durch das Publikum grundsätzlich berücksichtigt werden könnten. Positionsmarken, wie die beanspruchte, seien Marken, deren Schutzgegenstand zusätzlich aus der spezifischen Positionierung eines oder mehrerer gleichbleibender zwei- oder dreidimensionaler Zeichenelemente auf der Ware oder auf einem Warenteil hervorgehe. Die Unterscheidungskraft einer Positionsmarke werde dabei durch eine Gesamtbetrachtung der beanspruchten Position und dem oder den zusätzlichen Zeichenelementen eruiert. Das Positionselement trage im Rahmen der erforderlichen Gesamtbetrachtung dann zur Unterscheidungskraft bei, wenn die Markierungsstelle bei den beanspruchten Waren oder deren Verpackung als ungewöhnlich bzw. auffallend erscheine oder sich die Position im Verkehr durchgesetzt habe. Funktional naheliegende Positionen seien freihaltebedürftig. Die Position eines grafischen Elementes auf einem Produkt sei häufig banal und wirke nur dekorativ. Dekorative bzw. banale Elemente könnten nicht originär unterscheidungskräftig sein. Daraus folge, dass insbesondere der für eine bestimmte Ware gängige Gestaltungsschatz ebendieser Ware als nicht unterscheidungskräftig gelten müsse.
Hinsichtlich der für die Beurteilung der Unterscheidungskraft massgeblichen Verkehrskreise führte die Vorinstanz aus, hochhackige Schuhe wiesen keine inhärent grösseren Produktionskosten als andere Schuhe auf und könnten somit in allen Preissegmenten angeboten werden, weshalb nicht davon ausgegangen werden könne, dass hochhackige Schuhe ausschliesslich oder vorwiegend von finanziell bessergestellten Personen erworben bzw. nachgefragt würden. Bezüglich des Alters von Abnehmern hochhackiger Damenschuhe könne aus der vorliegenden Warenliste wohl ausser der physischen Einschränkung bei sehr jungen und sehr alten Trägerinnen hochhackiger Schuhe keine weitere Limitierung des Alters entnommen werden. Entsprechend reiche das Alter der relevanten Verkehrskreise von ziemlich jung bis ziemlich alt. Weiter sei davon auszugehen, dass Schuhe vor dem Kauf zuerst anprobiert würden, womit vornehmlich Frauen zu den relevanten Verkehrskreisen zu zählen seien. Zudem sei anzumerken, dass hochhackige Schuhe vor allem zu festlichen oder formelleren Anlässen getragen würden, bei denen das modische Aussehen eine massgebliche Bedeutung habe; insoweit bestünden die Verkehrskreise aus Personen mit einem zumindest leicht erhöhten Modebewusstsein.
Das zur Diskussion stehende Zeichen beanspruche Markenschutz für die Farbe Rot (Pantone No. 18.1663TP), jeweils angebracht an der ganzen Unterseite der Sohle von hochhackigen Damenschuhen. Die Farbe sei durch die Panton-Skala eindeutig bestimmt, die Grösse des Zeichens ergebe sich aus den Konturen der Untersohle des Schuhs. Diese sei wohl nicht bei jedem Damenschuh genau gleich gross, sie ergebe sich aus funktionalen Gründen aber stets aus dem Verhältnis zum Oberschuh und sei somit klar definiert. Die in der Abbildung dargestellte Unterseite der Sohle als Positionsanspruch sei ebenfalls nicht interpretationsbedürftig, da Schuhe nur auf eine Art getragen werden könnten und die Unterseite somit unstreitig festzumachen sei. Weiter sei die Untersohle gemäss Abbildung leicht geschwungen und weise ein gewisses dreidimensionales Element auf. Nicht beansprucht sei der in der Abbildung gestrichelt dargestellte Oberschuh; dieser diene lediglich zur Illustration und dem besseren Verständnis des beanspruchten Gegenstands.
Die Unterseite einer Damenschuhsohle sei grundsätzlich keine Position, an der das Anbringen einer Marke als ungewöhnlich oder auffallend erscheine, da aus ästhetischen Gründen fast nur die Innen- und Aussensohle von hochhackigen Damenschuhen überhaupt als Ort für eine Platzierung einer Marke in Frage komme. Entsprechend oft finde sich eine Marke an der Unterseite eines hochhackigen Damenschuhs. Bei der beanspruchten Farbe Rot (Pantone No. 18.1663TP), angebracht auf der durch die Sohle definierten Fläche, handle es sich zwar nicht um einen konturlosen Farbanspruch, der nur mittels Verkehrsdurchsetzung schutzfähig wäre, die Konturen einer Schuhsohle erschienen aber im Zusammenhang mit den beanspruchten Waren (hochhackige Damenschuhe) als banal und beschreibend; zudem gehöre rot - auch in einem etwas grelleren Ton wie Pantone No. 18.1663TP - zu den Grundfarben und werde, insbesondere bei Waren aus der Modebranche, oft als dekoratives Element verwendet. Das sich aus einer durch die bei den Zehen beginnende, hin zu der Ferse hochgeschwungenen Fläche ergebende Formelement sei durch die Funktion eines hochhackigen Damenschuhs, wie er vorliegend beansprucht werde, bedingt. Die vom IGE vorgelegten Beweise zeigten, dass hochhackige Damenschuhe mit farblich bearbeiteter Aussensohle von verschiedenen gewerblichen Schuhverkäufern angeboten werden und diese Schuhe im schweizerischen Markt nicht nur vereinzelt auftauchen. Eine farbige und damit auch eine rote Aussensohle bei Damenschuhen weiche nicht vom üblichen bzw. gängigen Gestaltungsschatz im strittigen Warensegment ab. Aufgrund einer Gesamtbetrachtung sei davon auszugehen, dass die massgebenden Verkehrskreise (vornehmlich weibliche Abnehmerinnen mit leicht erhöhtem Modebewusstsein) farbliche bzw. im vorliegenden Fall rote Schuhsohlen bei hochhackigen Damenschuhen primär als dekoratives Element und nicht als Marke wahrnehmen. Dem strittigen Zeichen fehle es daher an der originären Unterscheidungskraft, weshalb es nicht als Marke schutzfähig sei.
3.2. Der Beschwerdeführer bringt im Wesentlichen vor, die Vorinstanz habe bei der Prüfung der originären Unterscheidungskraft des fraglichen Zeichens nicht auf den Gesamteindruck abgestellt, sondern bloss auf die Details der einzelnen Elemente. Seine Positionsmarke, die in einer leuchtend roten Aussensohle an High Heels bestehe, sei gänzlich ungewöhnlich gewesen, als die ersten Schuhe damit markiert worden seien und sie sei es bis heute geblieben. Dies möge erklären, weshalb das IGE und die Vorinstanz zögerlich seien, die Positionsmarke in der Schweiz zum Markenschutz zuzulassen. Trete man aber einen Schritt zurück und betrachte die Marke unter objektiven Gesichtspunkten, so zeige sich, dass es sich bei seiner Positionsmarke im Vergleich zur üblichen Art, Schuhe zu markieren, um eine der innovativsten und einzigartigsten Schuhmarken handle, die in den letzten 25 Jahre geschaffen worden seien. Die leuchtend rote Aussensohle weiche vom Üblichen in bedeutendem Umfang ab und stelle eine unerwartete und originelle Art der Kennzeichnung von High Heels dar. Deswegen hätten die Durchschnittskonsumentinnen diese Kennzeichnung der Produkte des Beschwerdeführers bei ihrer ersten Verwendung als Marke wahrgenommen und nähmen sie auch heute unverändert als Marke wahr.
Aus diesen Gründen sei seine Positionsmarke originär unterscheidungskräftig und ins Schweizer Markenregister einzutragen.
3.3.
3.3.1. Sowohl Art. 5 Abs. 2 des Madrider Abkommens über die internationale Registrierung von Marken (MMA; SR 0.232.112.3; revidiert in Stockholm am 14. Juli 1967) als auch Art. 5 Abs. 1 des vorliegend anwendbaren Protokolls vom 27. Juni 1989 zum MMA (MMP; SR 0.232.112.4) verweisen bezüglich der zulässigen Gründe für eine Schutzverweigerung auf die Pariser Verbandsübereinkunft zum Schutz des gewerblichen Eigentums, revidiert in Stockholm am 14. Juli 1967 (PVÜ; SR 0.232.04). Nach Art. 6quinquies lit. B Ziff. 2 PVÜ ist eine Schutzverweigerung unter anderem in Fällen statthaft, in denen die Marke jeder Unterscheidungskraft entbehrt bzw. als Gemeingut anzusehen ist. Diese zwischenstaatliche Regelung entspricht den in Art. 2 MSchG (SR 232.11) vorgesehenen Ablehnungsgründen, wonach namentlich Zeichen, die zum Gemeingut gehören (lit. a), vom Markenschutz ausgeschlossen sind (BGE 135 III 359 E. 2.5.1; 128 III 454 E. 2; je mit Hinweisen).
3.3.2. Die Gründe für den Schutzausschluss von Zeichen, die dem Gemeingut angehören (Art. 2 lit. a MSchG), liegen entweder im Freihaltebedürfnis oder in der fehlenden Unterscheidungskraft, wobei sich Überschneidungen ergeben können (BGE 139 III 176 E. 2 S. 178; 131 III 121 E. 4.1 S. 126; je mit Hinweisen). Freihaltebedürftig sind Zeichen, auf deren Verwendung der Wirtschaftsverkehr angewiesen ist. Die Unterscheidungskraft geht Zeichen ab, die aufgrund ihres Erscheinungsbildes oder ihres sachlichen resp. beschreibenden Gehalts die markenspezifische Unterscheidungsfunktion nicht erfüllen können (BGE 139 III 176 E. 2 S. 178 mit Hinweis). Nicht schutzfähig sind demnach unter anderem Zeichen, denen in Bezug auf die konkret beanspruchten Produkte die Unterscheidungskraft fehlt, indem sie weder von Anfang an (originär) auf ein bestimmtes - wenn auch dem Publikum nicht unbedingt namentlich bekanntes - Unternehmen hinweisen, noch (derivativ) infolge ihrer Durchsetzung im Verkehr (BGE 137 III 403 E. 3.3.2; vgl. auch BGE 140 III 109 E. 5.3.2 S. 112 f.).
Ob ein Zeichen als Marke in Frage kommt, beurteilt sich nach dem Gesamteindruck, den es bei den massgebenden Adressaten in der Erinnerung hinterlässt (BGE 134 III 547 E. 2.3.1 S. 551; 133 III 342 E. 4 S. 346). Es genügt daher, wenn der Marke als Ganzes (in Kombination aller Einzelelemente) Unterscheidungskraft zukommt bzw. dem Verkehr nicht freihaltebedürftig ist (Urteil 4A_528/2013 vom 21. März 2014 E. 5.1 mit Hinweisen, nicht publ. in: BGE 140 III 109 ff.). Ob die massgebenden Adressaten ein Zeichen für die beanspruchten Produkte als Hinweis auf ein Unternehmen wahrnehmen, ist dabei vor dem Hintergrund der gesamten Umstände zu beurteilen (BGE 137 III 403 E. 3.3.2 S. 409; 134 III 547 E. 2.3 S. 551). Als originär unterscheidungskräftig ist ein Zeichen schützbar, wenn es aufgrund einer minimalen ursprünglichen Unterscheidungskraft geeignet ist, die mit ihr gekennzeichneten Waren und Dienstleistungen zu individualisieren, und es dem Verbraucher dadurch ermöglicht, diese im allgemeinen Angebot gleichartiger Waren und Dienstleistungen wiederzuerkennen (BGE 140 III 109 E. 5.3.2 S. 112; 137 III 403 E. 3.3.2; je mit Hinweisen). Bei der Prüfung, ob diese Schutzvoraussetzung erfüllt ist, ist das Zeichen so zu betrachten, wie es vom Hinterleger angemeldet worden ist. Die Auswirkungen des bereits erfolgten oder künftigen Zeichengebrauchs auf die Wahrnehmung durch die massgeblichen Verkehrskreise müssen ausser Betracht bleiben. Das Zeichen muss aus sich selbst heraus und unabhängig von seinem Gebrauch geeignet sein, die Waren und Dienstleistungen des Markeninhabers von denjenigen anderer Anbieter zu unterscheiden (BGE 140 III 109 E. 5.3.2 S. 112 mit Hinweisen).
Das Bundesgericht prüft grundsätzlich als Rechtsfrage frei, wie der massgebende Adressatenkreis für die beanspruchten Waren oder Dienstleistungen abzugrenzen ist und - bei Gütern des allgemeinen Bedarfs - wie die Adressaten aufgrund der erwarteten Aufmerksamkeit das Zeichen wahrnehmen (BGE 139 III 176 E. 2 S. 179; 137 III 403 E. 3.3.2 S. 409; 134 III 547 E. 2.3 S. 551; 133 III 342 E. 4 S. 347).
3.3.3. Positionsmarken sind im Markenschutzgesetz nicht als eigene Markenkategorie vorgesehen. Nach der Legaldefinition von Art. 1 Abs. 1 MSchG ist jedes Zeichen als Marke schützbar, das geeignet ist, Waren oder Dienstleistungen eines Unternehmens von solchen anderer Unternehmen zu unterscheiden; bei der Bestimmung von Art. 1 Abs. 2 MSchG handelt es sich nicht um eine abschliessende Aufzählung zulässiger Markenformen (BGE 135 III 359 E. 2.4 S. 364). Eine Positionsmarke wird charakterisiert durch ein stets gleichbleibendes Zeichenelement, das immer an derselben genau bezeichneten Warenposition angebracht wird. Bei solchen Marken führt die besondere Art und Weise der Anbringung oder Anordnung eines zwei- oder dreidimensionalen Zeichenelements auf einem Produkt zur Markenfähigkeit (vgl. MATTHIAS STÄDELI, in: Basler Kommentar, Markenschutzgesetz/Wappenschutzgesetz, 3. Aufl. 2017, N. 60 zu Art. 1 MSchG; EUGEN MARBACH, Markenrecht, SIWR Bd. III/1, 2. Aufl. 2009, Rz. 149; IRMGARD KIRSCHNECK, in: Ströbele/Hacker [Hrsg.], Markengesetz, 11. Aufl., Köln 2015, § 3 Rz. 81; PAUL STRÖBELE, in: Ströbele/Hacker [Hrsg.], Markengesetz, 11. Aufl., Köln 2015, § 8 Rz. 323). Gegenstand der Positionsmarke ist nicht die Position allein oder das isolierte Zeichen selbst, sondern die Kombination eines Zeichenelements mit einer bestimmten Position (MICHAEL NOTH/FLORENT THOUVENIN, in: Michael Noth und andere [Hrsg.], Markenschutzgesetz [MSchG], 2009, N. 62 zu Art. 1 MSchG). Der Schutzbereich ist entsprechend auf die Verbindung des graphischen oder kombinierten Zeichenelements mit der Warenposition beschränkt (STÄDELI, a.a.O., N. 60 zu Art. 1 MSchG; PHILIPPE GILLIÉRON, in: Commentaire romand, Propriété intellectuelle, 2013, N. 39 zu Art. 1 MSchG).
Neben der Unterscheidungskraft des Basiszeichens ist demnach die Stärke der Position zu berücksichtigen. Nicht jedem positionierten Zeichen kommt Unterscheidungskraft zu; die Position kann hierzu lediglich beitragen, sofern sie in der Wahrnehmung der massgebenden Verkehrskreiseein hinreichend charakteristisches Element darstellt, mithin stark genug ist, um das Zeichen in einen anderen Kontext zu setzen. Ebenso wie nicht jede beliebige Einfärbung oder grafische Gestaltung ein schutzunfähiges Zeichen hinreichend verändern kann, vermag dies jede beliebige Position zu erreichen. Die Position muss auch tatsächlich ein Verständnis als Herkunftshinweis vermitteln; das positionierte Zeichen muss im Gegensatz zu seinem unpositionierten Gegenstück ein Rätsel aufgeben, das nicht anders gelöst werden kann als durch die Zuordnung der Bedeutung als Herkunftshinweis (FABIAN KLEIN, Schutzvoraussetzungen und Schutzumfang der Positionsmarke, Tübingen 2012, S. 295 f. mit Hinweis). Besteht auf dem betreffenden Warengebiet eine Kennzeichnungsgewohnheit, dürften die dieser Gewohnheit entsprechenden Positionen leichter als Herkunftshinweise verstanden werden. Zudem ist die Position umso stärker einzustufen, je prominenter sie auf dem jeweiligen Positionsträger in den Vordergrund rückt (KLEIN, a.a.O., S. 299 ff., 311). Ob die massgeblichen Verkehrskreise ein Zeichenelement an einer bestimmten Position der Ware als Kennzeichen - und nicht etwa als technisch bedingtes Element oder blosse Zierde - auffassen, ist im Rahmen der Prüfung der Unterscheidungskraft im konkreten Einzelfall zu bestimmen (STÄDELI, a.a.O., N. 61 zu Art. 1 MSchG; NOTH/THOUVENIN, a.a.O., N. 62 zu Art. 1 MSchG).
Wie die Vorinstanz zutreffend ausführt, ist die Einordnung der Positionsmarke (etwa als Bild-, Form- oder sonstige Marke) für die Beurteilung der Unterscheidungskraft unerheblich (vgl. auch Beschluss des EuGH vom 16. Mai 2011 C-429/10 P X Technology Swiss GmbH, Slg. 2011 I-00076 Randnrn. 36 f. mit Verweis auf das Urteil des EuG vom 15. Juni 2010 T-547/08 X Technology Swiss GmbH, Slg. 2010 II-02409 Randnrn. 21, 26). Für die Beurteilung der absoluten Schutzfähigkeit von Positionsmarken gelten in dieser Hinsicht keine Sonderregelungen (STRÖBELE, a.a.O., § 8 Rz. 325; KLEIN, a.a.O., S. 282). Die Wahrnehmung der massgeblichen Verkehrskreise kann jedoch durch die Art des Zeichens beeinflusst werden; so wird insbesondere von Zeichen, die im Erscheinungsbild der Ware selbst bestehen, gewöhnlich nicht auf die betriebliche Herkunft dieser Waren geschlossen (vgl. BGE 137 III 403 E. 3.3.3/3.3.4 mit Hinweisen).
3.3.4. Das eingetragene Basiszeichen besteht unabhängig von seiner Position, die gleichzeitig die Kontur der gewählten Farbe (Pantone No. 18.1663TP) bestimmt, indem sie die gesamte Fläche der Schuhsohle umfasst, lediglich in einem bestimmten Farbton, der als solcher für die beanspruchten Damenschuhe mit hohen Absätzen nicht originär unterscheidungskräftig ist (vgl. zur Farbmarke etwa STÄDELI, a.a.O, N. 52 ff. zu Art. 1 MSchG). Dabei handelt es sich um einen äusserst schwachen Zeichenbestandteil, zumal dem Basiszeichen als solchem keinerlei konkrete Gestaltung zukommt, die originär als Herkunftshinweis verstanden werden könnte. Wie die Vorinstanz zutreffend ausführt, steht zwar nicht ein konturloser Farbanspruch zur Diskussion; die Umrisse von Schuhsohlen sind jedoch als Zeichen für Schuhe banal und beschreibend, indem sie im Erscheinungsbild eines Teils der Ware selbst bestehen. Es wird nicht etwa ein Wort- oder Bildelement auf der Schuhsohle positioniert, wofür auf dem Schuhmarkt eine gewisse Übung und eine entsprechende Gewöhnung der Konsumenten bestehen dürfte. Vielmehr besteht das Zeichen aus einer einfarbigen Darstellung der Unterseite eines hochhackigen Damenschuhs, wodurch es mit dem Erscheinungsbild der Ware selbst verschmilzt. Zeichen, die im Erscheinungsbild der Ware selbst bestehen, werden jedoch gewöhnlich nicht als Hinweis auf die betriebliche Herkunft dieser Waren, sondern lediglich als besondere Gestaltung wahrgenommen (vgl. BGE 137 III 403 E. 3.3.3 mit Hinweisen). Ähnlich der Formmarke kann es im Hinblick auf die originäre Unterscheidungskraft nicht ausreichen, dass sich ein solches Zeichen lediglich nach seiner gefälligen Gestaltung unterscheidet; vielmehr muss es sich von sämtlichen im beanspruchten Warensegment im Zeitpunkt des Entscheids über die Markeneintragung üblichen Gestaltungen auffällig unterscheiden, damit ein Verständnis als Herkunftshinweis in Betracht kommen kann (zur Formmarke: BGE 137 III 403 E. 3.3.3; 134 III 547 E. 2.3.4; 133 III 342 E. 3.3). Die massgebende Vergleichsmenge besteht dabei in den auf dem betroffenen Warensegment tatsächlich vorhandenen Gestaltungen und nicht etwa in erfolgten Markenanmeldungen vergleichbarer Zeichen, wie der Beschwerdeführer anzunehmen scheint.
Die Eigenart des zu beurteilenden Zeichens besteht weder in einer charakteristischen Form noch in einer für sich betrachtet auffälligen Gestaltung, sondern beschränkt sich auf die Wahl einer bestimmten Farbe für einen funktional unabdingbaren und flächenmässig bedeutsamen Teil der beanspruchten Ware. Dass diese Farbe im Gegensatz zu den in der Beschwerde erwähnten schwarzen, braunen oder beigen Aussensohlen für Damenschuhe mit hohen Absätzen nicht gebräuchlich ist, reicht nicht aus, um dem Zeichen in der Gesamtbetrachtung Unterscheidungskraft zu verleihen. Der Beschwerdeführer stellt zu Recht nicht in Abrede, dass die rote Farbe auch in einem etwas grelleren Ton, wie von ihm beansprucht, insbesondere bei Waren aus der Modebranche oft als dekoratives Element verwendet wird. Wie sich aus den vorinstanzlichen Feststellungen ergibt, kommen zudem etwa hochhackige Damenschuhe, deren Aussensohle in grün, gelb, blau, violett oder pink gehalten sind, durchaus vor. Der Umstand, dass ein solcher Damenschuh eine farbige Aussensohle aufweist, kann daher nicht als derart aussergewöhnlich betrachtet werden, dass sich dieses Merkmal in einer Weise von den üblichen Gestaltungen abheben würde, um in seiner auffälligen Eigenart (originär) als Herkunftshinweis in Betracht zu kommen. Die Modebranche zeichnet sich auch bezüglich der beanspruchten Damenschuhe mit hohen Absätzen durch eine grosse Gestaltungsvielfalt aus und schöpferische Entwicklungen werden geradezu erwartet, weshalb die blosse Einfärbung eines Teils der Produktoberfläche in Form der Aussensohle von den angesprochenen Abnehmern der Ware zugeschlagen und nicht als Herkunftshinweis aufgefasst wird.
Die rote Einfärbung (Pantone No. 18.1663TP) der Sohlenunterseite stellt ein ästhetisches Stilelement dar, das sich - losgelöst betrachtet von der bereits erfolgten Benutzung bzw. einer allfälligen Bekanntheit der vom Beschwerdeführer entworfenen und vertriebenen Designerschuhe - von der modischen Gestaltung von Damenschuhen mit hohen Absätzen auch aus Sicht der in der Beschwerde als massgebend erachteten Verkehrskreise (modeorientierte und zahlungskräftige Frauen zwischen 20 und 65 Jahren) gedanklich nicht derart abhebt, dass sie (originär) als zusätzliches Element im Sinne eines Herkunftshinweises aufgefasst würde. Es braucht daher nicht vertieft zu werden, ob die Vorinstanz den massgebenden Verkehrskreis zu weit gefasst hat, wie in der Beschwerde geltend gemacht wird.
3.3.5. Der Vorinstanz ist keine Bundesrechtsverletzung vorzuwerfen, indem sie das strittige Zeichen als nicht originär unterscheidungskräftig erachtete. Dass dem Zeichen infolge ihrer Durchsetzung im Verkehr Unterscheidungskraft zukommen würde, steht im vorliegenden Verfahren nicht zur Diskussion. Die Vorinstanz hat unter diesen Umständen zu Recht offengelassen, ob am fraglichen Zeichen gegebenenfalls ein Freihaltebedürfnis besteht.
4.
4.1. Der Beschwerdeführer macht im Weiteren geltend, das strittige Zeichen sei bereits in ausländische Markenregister eingetragen worden. Es gebe keine rationalen Gründe, die dafür sprechen würden, dass die Schweizer Durchschnittskonsumentin sein Zeichen anders wahrnehme als dies im Rest der Welt der Fall sei; namentlich sei die Wahrnehmung durch Schweizer und europäische Durchschnittskonsumentinnen die gleiche. Insbesondere die Entscheidungen der Instanzen der EU seien auch in der Schweiz zu berücksichtigen.
4.2. Der Beschwerdeführer vermag keine Bundesrechtsverletzung aufzuzeigen. Abgesehen davon, dass er es bei allgemeinen Ausführungen und einem unzulässigen Verweis auf Vorbringen in anderen Rechtsschriften und die Akten bewenden lässt (BGE 140 III 115 E. 2 S. 116), verkennt der Beschwerdeführer, dass nach der Rechtsprechung des Bundesgerichts aufgrund einer ausländischen Eintragung kein Anspruch auf Eintragung in der Schweiz besteht und ausländische Entscheide keine präjudizielle Wirkung haben. Immerhin darf der Umstand, dass ein Zeichen im Ausland eingetragen wurde, bei der Beurteilung des Gemeingutcharakters eines Zeichens mitberücksichtigt werden. Jedes Land prüft die Schutzfähigkeit einer Marke jedoch nach seiner eigenen Gesetzgebung, Rechtsprechung und Verkehrsanschauung. Dabei verfügen die einzelnen Länder über einen grossen Ermessensspielraum und ihre Beurteilung kann demnach unterschiedlich ausfallen (BGE 136 III 474 E. 6.3 S. 483; 135 III 416 E. 2.1; 130 III 113 E. 3.2; 129 III 225 E. 5.5).
Diese Grundsätze wurden von der Vorinstanz beachtet. Entgegen dem, was der Beschwerdeführer anzunehmen scheint, führt zudem die Berücksichtigung eines Beweisstücks mit Auslandsbezug (etwa in Form eines Ausdrucks eines ausländischen Internetshops) nicht dazu, dass die Vorinstanz im Rahmen der Prüfung der Unterscheidungskraft eine ausländische Entscheidung hätte als verbindlich ansehen müssen. Von einer widersprüchlichen oder willkürlichen Beurteilung kann nicht die Rede sein.
5.
Die Beschwerde ist abzuweisen, soweit darauf einzutreten ist. Dem Ausgang des Verfahrens entsprechend wird der Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1 BGG). Dem Beschwerdegegner ist keine Parteientschädigung zuzusprechen (Art. 68 Abs. 3 BGG).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 5'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien und dem Bundesverwaltungsgericht, Abteilung II, schriftlich mitgeteilt.
Lausanne, 7. Februar 2017
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Kiss
Der Gerichtsschreiber: Leemann